# 2025q1 Homework1 (lab0)
contributed by < [otischung](https://github.com/otischung/) >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```bash
❯ uname -a
Linux scream-Ubuntu-24 6.11.0-17-generic #17~24.04.2-Ubuntu SMP PREEMPT_DYNAMIC Mon Jan 20 22:48:29 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
❯ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-linux-gnu/13/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 13.3.0-6ubuntu2~24.04' --with-bugurl=file:///usr/share/doc/gcc-13/README.Bugs --enable-languages=c,ada,c++,go,d,fortran,objc,obj-c++,m2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-13 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/libexec --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-bootstrap --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-libstdcxx-backtrace --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=release --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --enable-cet --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-13-fG75Ri/gcc-13-13.3.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-13-fG75Ri/gcc-13-13.3.0/debian/tmp-gcn/usr --enable-offload-defaulted --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu --with-build-config=bootstrap-lto-lean --enable-link-serialization=2
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 13.3.0 (Ubuntu 13.3.0-6ubuntu2~24.04)
❯ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 24
On-line CPU(s) list: 0-23
Vendor ID: GenuineIntel
Model name: 13th Gen Intel(R) Core(TM) i7-13700
CPU family: 6
Model: 183
Thread(s) per core: 2
Core(s) per socket: 16
Socket(s): 1
Stepping: 1
CPU(s) scaling MHz: 21%
CPU max MHz: 5200.0000
CPU min MHz: 800.0000
BogoMIPS: 4224.00
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse3
6 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb r
dtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopolog
y nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 mon
itor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm sse4_1 sse4_
2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lah
f_lm abm 3dnowprefetch cpuid_fault ssbd ibrs ibpb stibp ibrs_enhanced
tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2
smep bmi2 erms invpcid rdseed adx smap clflushopt clwb intel_pt sha_ni
xsaveopt xsavec xgetbv1 xsaves split_lock_detect user_shstk avx_vnni
dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_
req hfi vnmi umip pku ospke waitpkg gfni vaes vpclmulqdq rdpid movdiri
movdir64b fsrm md_clear serialize pconfig arch_lbr ibt flush_l1d arch
_capabilities
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 640 KiB (16 instances)
L1i: 768 KiB (16 instances)
L2: 24 MiB (10 instances)
L3: 30 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-23
Vulnerabilities:
Gather data sampling: Not affected
Itlb multihit: Not affected
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Not affected
Reg file data sampling: Mitigation; Clear Register File
Retbleed: Not affected
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Spectre v2: Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling;
PBRSB-eIBRS SW sequence; BHI BHI_DIS_S
Srbds: Not affected
Tsx async abort: Not affected
```
## 整理程式碼現有架構設計
參考 [Dennis Liu](https://hackmd.io/@dennis40816/linux2025-homework1) 的解說圖片
https://hackmd.io/@dennis40816/linux2025-homework1?stext=7939%3A146%3A0%3A1741066532%3Aiu6nSC
我們將 `list.h`, `queue.h` 現有的 API 定義與實作做討論
```cpp
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
可以發現，這個 `list_head` 只有雙向鏈結串列的部份，並沒有定義存放資料的欄位。
> Both node and head share the same struct type.
因此，我們接者看單一節點 (node/element) 是如何定義的
```cpp
typedef struct {
char *value;
struct list_head list;
} element_t;
```
現在，我們再回頭看 `struct list_head` 的定義
> The `prev` pointer of the list head points to the last list node of the list.
> The `next` points to the first list node of the list.
> For an empty list, both member variables point to the head.
對於一個空的 queue，我們已經有以下此函式可呼叫
```cpp
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
所以，對於一個 queue，我們有
- 一個 `struct list_head *head`
- 若干個 `element_t e_0, e_1, ...`
- `head->next` 指向第一個 element `e0` 的 `struct list_head list`
- `head->prev` 指向最後一個 element `e_{N-1}` 的 `struct list_head list`
- N 是 element 數量。
因此，我們會需要 [container of](https://hackmd.io/@sysprog/linux-macro-containerof) 經由 `struct list_head list` 的位址，回推該 node `element_t` 的位址。
現在，我們已經了解 [container of](https://hackmd.io/@sysprog/linux-macro-containerof) 如何應用於單一 queue，現在我們可以來看如何建立起多個 queues，這些 queues 也是由雙向鏈結串列所組成。
```cpp
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
透過 `qtest.c`，我們可以知道如何操作以上所有的 struct。
```cpp
static bool do_new(int argc, char *argv[])
{
...
if (exception_setup(true)) {
queue_contex_t *qctx = malloc(sizeof(queue_contex_t));
list_add_tail(&qctx->chain, &chain.head);
qctx->size = 0;
qctx->q = q_new();
qctx->id = chain.size++;
current = qctx;
}
...
}
```
- `q` 是此 queue 的 `list_head *`，根據 `list_head` 定義
- 如果該 queue 有 node，
- 走訪 `next` 會得到第一個元素
- 走訪 `prev` 會得到最後一個元素。
- 如果該 queue 沒有有 node，則 `next` 與 `prev` 均指向 `list_head` 自己。
- `chain` 是 queue 自身的雙向鏈結串列，由此走訪上一個或下一個 queue，同樣用 [container of](https://hackmd.io/@sysprog/linux-macro-containerof) 回推 `queue_contex_t`。
- `size` 是此 queue 有幾個 node。
- `id` 是此 queue 的編號。
## 針對佇列操作的程式碼實作
### `q_new`
commit: [cc22da8](https://github.com/otischung/lab0-c/commit/cc22da8c88af3ba42b9a2cdf0d49e8d1dff95fe4)
用途就如同 `qtest.c` 內的 `q_new()`，根據 `list_head` 定義，透過 `INIT_LIST_HEAD()` 初始化。
### `q_free`
commit: [ae04274](https://github.com/otischung/lab0-c/commit/ae0427472a0d4a67b4ad0497708732ffe4223459)
首先，我們需要 `free` `element_t`，而我們發現在 `queue.h` 內就有實作 `q_release_element()`
```cpp
static inline void q_release_element(element_t *e)
{
test_free(e->value);
test_free(e);
}
```
接下來，我們需要走訪每一個 `element_t`，這需要以下操作
- 對於每個 `list_head` 經由 [container of](https://hackmd.io/@sysprog/linux-macro-containerof) 回推 `element_t`
- 由於我們要做刪除，所以我們要額外定義一個 `element_t *` 指向下一個物件，才能安全將目前 iterator 指向的物件刪除
- iterator 指向下一個 `list_head`，直到回到 head 本身
這些複雜的迴圈設定，在 `list.h` 已經有定義 macro
```cpp
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
```
因此，檢查完 `struct list_head *head` 不是 `NULL` 之後，定義 iterator 與 safe 指標，代入 macro 展開迴圈，移除 element，最後移除 `head` 即可。
### `q_insert_head`
commit: [52745fd](https://github.com/otischung/lab0-c/commit/52745fd70989f6afe1e601eea397dfe3c242b0a7)
在這裡，我們需要建立一個 `element_t` 的記憶體空間做存取，由於我們對於所有 node 都是透過 `list_head` 間接操作，因此不需要特別儲存每一個`element_t` 的記憶體位址。
又因為 `element_t` 的記憶體空間完成配置後需要被保留以供後續操作，因此，我們需要使用指標，透過 `malloc()` 的方式配置，這樣離開此函式之後，該記憶體位置不會被刪除。
配置 `element_t` 的記憶體空間後，我們使用 `strdup()` 來複製字串到指定記憶體位置，詳見 [Manual Page](https://man7.org/linux/man-pages/man3/strdup.3.html)
剩下的 linked-list 部份，在 `list.h` 已經有實作 `list_add()`
```cpp
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
**注意**：因為我們是透過 [container of](https://hackmd.io/@sysprog/linux-macro-containerof) 操作 node，直接看此函式必定會有 memory leak 的疑慮，因此<font color=FF0000>**我們在此關閉 `pre-commit.hook`**</font>。
### `q_insert_tail`
commit: [52745fd](https://github.com/otischung/lab0-c/commit/52745fd70989f6afe1e601eea397dfe3c242b0a7)
觀察 `list_add()` 的實作，他會將 node 插入到 `head->next` 之前。
而 `q_insert_tail()` 應當要將 node 插入到 `head` 之前，這兩者之間差一個 `next`。
因此，將 `head` 代入 `head->prev` 即可重用 `q_insert_head()`。
:::info
**注意**：在 `make test` 中，我的 `q_insert_head` 與 `q_insert_tail` 一直回報可能不是 constant time
:::
> ERROR: Probably not constant time or wrong implementation
:::success
在 merge 了[源頭 upstream ](https://github.com/sysprog21/lab0-c/tree/599de0f32ae8ec9541e7de8053e7549272220999)的新的 [commit](https://github.com/otischung/lab0-c/tree/12872c8f9282d15eec0168de90ee4970a7bb2465) 之後，此問題已解決
:::
可以經由以下指令得到目前合併了 upstream 的哪個 commit:
```bash
git remote add upstream https://github.com/sysprog21/lab0-c.git
git fetch upstream
git merge-base HEAD upstream/master
```
### `q_remove_head`
commit: [fa8ff8b](https://github.com/otischung/lab0-c/commit/fa8ff8b06d6f8e435d9b5da4ccbd7914bd339aab)
檢查 queue 是否有至少一個 node，這包含 2 種情況
- `head == NULL`
- `head` 剛被初始化
- 特性是 `prev` 與 `next` 會等於 `head`
- `list.h` 已經有 `list_empty()` 的實作
```cpp
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
接下來，我們需要找到第一個 node，`list.h` 已經有 `list_first_entry()` 的 macro
```cpp
#define list_entry(node, type, member) container_of(node, type, member)
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
找到之後，予以刪除，`list.h` 已經有 `list_del()` 的實作
```cpp
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
}
```
最後，使用 `strncpy()` 將欲 remove 的 node 的字串複製出來，最後回傳欲 remove 的 node 的記憶體位址。
注意：remove 與 delete 不同，remove 僅有移出 queue，並未完全刪除該 node 的記憶體空間
### `q_remove_tail`
commit: [fa8ff8b](https://github.com/otischung/lab0-c/commit/fa8ff8b06d6f8e435d9b5da4ccbd7914bd339aab)
與 `q_insert_tail` 相似，將 `head` 代入 `head->prev` 即可重用 `q_remove_head()`。
### `q_size`
commit: [463c4c4](https://github.com/otischung/lab0-c/commit/463c4c415a6c56781f12af92694b767fa4236a07)
`list.h` 已經有 `list_for_each()` 的 macro
```cpp
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
設定一個計數器，走訪完畢即可。
### `q_delete_mid`
commit: [2fd563d](https://github.com/otischung/lab0-c/commit/2fd563d5be944d1202b20d5276abace83dd6c834)
此函式與此 [leetcode](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/) 題目相似。
我們可以利用[快慢指標](https://hackmd.io/@sysprog/ry8NwAMvT)來找到中間點，簡單來說就是，一開始慢指標與快指標皆指向第一個 node，也就是 `head->next`，之後每次慢指標走一步，且快指標的下一個不會回到開頭，則快指標就走兩步，如此一來，我們的慢指標必定會指到第 $\lfloor n / 2 \rfloor$ 個 node，n 為總 node 數量。
### `q_delete_dup`
commit: [a91339f](https://github.com/otischung/lab0-c/commit/a91339fa1bcb382ecc2d971e14b3cebe438165e7)
此函式與此 [leetcode](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 題目相似。
需留意此函式要求對於一個已排序的 linked-list，刪除**所有**有重複的 node，即只要有重複，皆不予保留，例如：
`[1, 1, 1, 2, 3, 4, 5, 5]`
執行過 `q_delete_dup`，預計變成
`[2, 3, 4]`
`1` 將被完全刪除。
我們需要一個 traverse pointer，還有一個慢一個 node 的 previous pointer。
一開始，`prev == NULL`
```
1 1 1 2 3 4 5 5
p c
```
當 `prev != NULL` 時，開始判斷 node 是否重複
- 若重複，則 delete `prev` node。
```
1 1 1 2 3 4 5 5
p c
```
- 若不重複，則
- 若前一次為重複，則需刪除位於前一個該種最後一個 node
```
1 1 1 2 3 4 5 5
p c
```
- 若前一次不重複，則不處理
```
1 1 1 2 3 4 5 5
p c
```
- 最後一個需要特別判斷
- 若前一次為重複，則需刪除位於前一個該種最後一個 node
```
1 1 1 2 3 4 5 5
p c
```
- 若前一次不重複，則不處理
```
1 1 1 2 3 4 5 5 6
p c
```
### `q_swap`
commit: [2e91e6f](https://github.com/otischung/lab0-c/commit/2e91e6fecd20defc9bbcaa6d63655cb0829e27e1)
此函式與此 [leetcode](https://leetcode.com/problems/swap-nodes-in-pairs/) 題目相似。
我們先從如何交換 2 個 node 開始，原本我的想法過於複雜，需要同時考量前一個與後一個 node，總共 4 個 node。但是其實這樣看似複雜的操作，其實等價於把前一個 node 移除 (remove, not delete)，然後再將其插入至後一個 node 之後，`list.h` 已經有 `list_for_each()` 的函式
```cpp
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
```
接著，我們再看 `list_for_each`
```cpp
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
雖然這個函式的註解有說明
> The current node (iterator) is allowed to be removed from the list. Any other modifications to the the list will cause undefined behavior.
不過，考量以下程式的意義
```cpp
for (node = (head)->next; node != (head); node = node->next)
{
if (node->next == head)
break;
list_move(node, node->next);
}
```
我們就可以達到以下結果
```
Beginning
1 2 3 4
n
list_move
2 1 3 4
n
Next Iteration
2 1 3 4
n
list_move
2 1 4 3
n
```
### `q_reverse`
commit: [d4ff6ca](https://github.com/otischung/lab0-c/commit/d4ff6ca77420cddea14594c45cdd5fc399d7301d)
我們要反轉一個 queue，只需要逐一將所有 node 重新插入至 queue 的開頭即可
我們看一下 `list.h` 裡面的 `list_for_each_safe`
```cpp
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
這裡由於 `node = safe`，所以更改 node 並不影響 traverse 的順序
### `q_reverseK`
commit: [68b430e](https://github.com/otischung/lab0-c/commit/68b430e5ddfb6df012fd88ea7a5dcdd9d71afd0e)
此函式與此 [leetcode](https://leetcode.com/problems/reverse-nodes-in-k-group/) 題目相似。
首先確認目前指向的 node 後面還有沒有 k 個 nodes (包含自身)，若有，則對於這些 k 個 nodes 做反轉，方法與 `q_reverse` 類似，只是由於只走訪 k 個，因此沒有 macro 可以套用，要自己寫。
### `q_sort`
commit: [1156c9c](https://github.com/otischung/lab0-c/commit/1156c9c1ac0e7eb527950c175155680fd13ab47a)
我們使用 Merge sort 來實作此函式。
Merge sort 有以下需要考量
1. 將目前的 list 切成一半
2. 遞迴解左右兩邊的 list，預計返回後會得到左右兩個各自排序完成的兩個 list
3. 將兩個已排序的 list 合併成一個排序的 list
#### 將目前的 list 切成一半 (divide)
我們需要分割 list，在 `list.h` 已經有實作 `list_cut_position()`
```cpp
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
```
這會將 `*head_from` 從頭到 `*node` (含 `*node` 本身)，都移到 `*head_to`。
切一半的事情，可以使用**快慢指標**找到中間的 node。
因此，我們定義一個新的 `list_head left`，將原本的 list 從頭到中間的 node 都搬移到 `left`，即可完成第一項任務。
#### 遞迴解
現在，我們有新的 `left` 與原本的 `head`，分別遞迴求解即可。
#### 合併 list (conquer)
我們建立一個新的函式 `q_merge_two()` 來完成此項目。
首先，建立一個暫存 list `temp_head`。
接著，對於左右兩陣列皆有元素的時候，比較雙方的開頭所儲存的值的大小。
假設定義由小到大排序 (ascending)，那麼就是將小的那一方移到暫存 list。
```
left: 1 3 5 7 9 11
head: 2 4 6 8 10
temp: NULL
-------------------
left: 3 5 7 9 11
head: 2 4 6 8 10
temp: 1
-------------------
...
```
此操作完成之後，若其中一方還有 node，那麼代表這些 node 所存的值都比暫存還大，所以直接搬移即可。
```
left: 11
head: NULL
temp: 1 2 3 4 5 6 7 8 9 10
-----------------------------
left: NULL
head: NULL
temp: 1 2 3 4 5 6 7 8 9 10 11
-----------------------------
...
```
最後，將 temp 搬移到 `left` 就完成操作。
`list.h` 已經有 `list_splice[_tail][_init]` 函式，專門複製整個 list 到另一個 list。
### `q_ascend` 和 `q_descend`
commit: [bfda729](https://github.com/otischung/lab0-c/commit/bfda729bd8f7b78fa11a19280a6e7307e5a8c47f)
`q_descend`與此 [leetcode](https://leetcode.com/problems/remove-nodes-from-linked-list) 題目相似。
移除每個 node，若其右側的任何位置存在值更大的 node。
因此，我們需要走訪所有的 node，從每一個 node 中，往回刪除所有左側比當前走訪的 node 還要小的數字。
以下做示範，p 代表 prev，c 代表 current
```
[head, 5, 2, 13, 3, 8]
p c
```
現在發現 $13 > 2$，所以將 2 刪除，並繼續左移，直到 `prev == head`。
```
[head, 13, 3, 8]
p c
```
以此類推，最後此 list 將剩下 `[13, 8]`。
若是解 `q_ascend`，則移除每個 node，若其右側的任何位置存在值更**小**的 node。
以此類推，最後此 list 將剩下 `[2, 3, 8]`。
### `q_merge`
commit: [c54469e](https://github.com/otischung/lab0-c/commit/c54469e41720507cd8bea565d58e00f84ed75e2c)
此函式與此 [leetcode](https://leetcode.com/problems/merge-k-sorted-lists/) 題目相似。
我們先看一下 `q_merge` 在 `qtest.c` 是如何被使用的
```cpp
typedef struct {
struct list_head head;
int size;
} queue_chain_t;
static queue_chain_t chain = {.size = 0};
static bool do_merge(int argc, char *argv[])
{
...
if (current && exception_setup(true))
len = q_merge(&chain.head, descend);
...
}
```
接著，我們看一下要求
> There is no need to free the 'queue_contex_t' and its member 'q' since they will be released externally. However, q_merge() is responsible for making the queues to be NULL-queue, except the first one.
這個 merge 的要求與之前實作 Merge sort 的 `q_merge_two()` 相同，因此我們重用此函式。
我們首先使用 `list_for_each_entry_safe` 這個 macro 走訪每一個 queue，特別處理第一個 queue 並記錄其位址，之後依序使用 `q_merge_two()` 將後續每一個 queue 都 merge 到第一個 queue，將 merge 完成的 NULL queue 搬移到開頭，這樣就不會影響後續走訪的進行。
完成走訪後，first queue 會位於最後一個 queue，其前面都是 NULL queue (如果原本有 2 個 queues 以上)，因此，再把 first queue 搬回第一個即可。
## 其他疑問
### 同步 repository
同步來源：[commit](https://github.com/sysprog21/lab0-c/commit/3c7c7b3251e50475a317e73f4517a181b60dcc2d)
完成同步到我的 repo：[commit](https://github.com/otischung/lab0-c/commit/5aef7d12ed988b21b8ecc9674735d76571354a29)
我在同步 repository 之後，發現 `make test` 一直跑不過，仔細檢查後發現 `scripts/check_repo.sh` 在抓取 upstream hash 時，會有 rate limited 的問題，因此發了 [issue](https://github.com/sysprog21/lab0-c/issues/243)。
Sign in with Wallet
Connect another wallet