--- tags: linux2023 --- # 2023q1 Homework1 (quiz1) contributed by < `linhoward0522` > > [2023q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz1) > 參考 [`list.h`](https://github.com/sysprog21/lab0-c/blob/master/list.h) 與 [`The Linux Kernel API`](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) ### 測驗 `1` ```c if (list_empty(head) || list_is_singular(head)) return; struct list_head list_less, list_greater; INIT_LIST_HEAD(&list_less); INIT_LIST_HEAD(&list_greater); ``` - 先確認 `list` 有無排序的必要後再往下執行，判斷 `list` 是否沒有節點或是只有一個節點 - 先宣告 `list_less`, `list_greater` ， `INIT_LIST_HEAD` 後， `list_less`, `list_greater` 分別用來當比 `pivot` 小以及比 `pivot` 大 `list` 的 `head` ```c struct item { uint16_t i; struct list_head list; }; ``` ```c struct item *pivot = list_first_entry(head, AAA, BBB); list_del(&pivot->list); ``` - 根據結構體的定義，以及 [`list_first_entry`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L355) 的定義 - 把 `list` 中的第一個元素當作 `pivot` ，用 `list_first_entry` 來取出元素，所以 `AAA` 為 `struct item` , `BBB` 為 `list` - 接著再把 `pivot` 先從 `list` 中移除，因為 `pivot` 並不用跟著遞迴 ```c CCC (itm, is, head, list) { if (cmpint(&itm->i, &pivot->i) < 0) DDD (&itm->list, &list_less); else EEE (&itm->list, &list_greater); } ``` - `CCC` 為 [`list_for_each_entry_safe`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L425) 用來走訪整個 `list` - 接著已經給定用以對節點內含值比較的函式 [`cmpint`](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-1) 來判斷節點數值跟 `pivot` 的大小 - 若是節點的數值小於 `pivot` ，則會將該節點移動到 `list_less` 的尾端 - 若是節點的數值大於等於 `pivot` ，則會將該節點移動到 `list_greater` 的尾端 - 所以 `DDD` 與 `EEE` 應皆為 [`list_move_tail`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L330) ```c list_sort(&list_less); list_sort(&list_greater); ``` - 接著需要透過遞迴不斷將直到分割不出串列為止 ```c list_add(&pivot->list, head); list_splice(&list_less, head); FFF(&list_greater, head); ``` - 最後我們要將串列合併回來 - 比 `pivot` 數值小的節點都放在 `pivot` 前面，數值大的節點都放在 `pivot` 後面 - 首先先用 `list_add` 將 `pivot` 節點加入 `head` - [`list_splice`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L193) 從定義可以看出是用來將節點加到開頭，所以將 `list_less` 串接到 `head` - 最後應該要把 `list_greater` 串接到尾端，所以 `FFF` 應為 [`list_splice_tail`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L219) ，即可得到一個排序過後的 `list` :::danger 避免張貼完整程式碼，善用 GitHub 來保存及管理。 :notes: jserv ::: --- ### 測驗 `2` ```c #define MAX_DEPTH 512 static void list_sort_nr(struct list_head *head) { if (list_empty(head) || list_is_singular(head)) return; struct list_head stack[MAX_DEPTH]; for (int i = 0; i < MAX_DEPTH; i++) INIT_LIST_HEAD(&stack[i]); int top = -1; list_splice_init(head, &stack[++top]); ``` - 先確認 `list` 有無排序的必要後再往下執行，判斷 `list` 是否沒有節點或是只有一個節點 - 由上方的 `define` 可知，先宣告一個大小為 512 的 `stack` ，接著用 [`INIT_LIST_HEAD`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L82) 做初始化 ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; head [label="head|{<prev>prev|<next>next}"]; head:next:e -> head:e head:prev:w -> head:w } ``` - [`list_splice_init(head, &stack[++top])`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L248) 會把 `head` 節點的資料移動到 `stack[0]` ， 然後初始化 `head` ```c struct list_head partition; INIT_LIST_HEAD(&partition); ``` - 宣告 `partition` 並將它初始化 ```c INIT_LIST_HEAD(&partition); list_splice_init(&stack[top--], &partition); ``` - 進入迴圈後先將 `partition` 初始化，再把 `stack[top]` 的資料移動到 `partition` ， 然後初始化 `stack[top]` ，最後因為從 `stack[top]` 拿出資料，所以 `TOP` 減一 ```c if (!list_empty(&partition) && !list_is_singular(&partition)) { struct list_head list_less, list_greater; INIT_LIST_HEAD(&list_less); INIT_LIST_HEAD(&list_greater); ``` - 首先判斷 `partition` 所指向的 `list` 有節點且不只有一個節點 - 接著宣告 `list_less`, `list_greater` ， `INIT_LIST_HEAD` 後， `list_less`, `list_greater` 分別用來當比 `pivot` 小以及比 `pivot` 大 `list` 的 `head` ```c struct item *pivot = list_first_entry(&partition, struct item, list); list_del(&pivot->list); INIT_LIST_HEAD(&pivot->list); ``` - 把 `list` 中的第一個元素當作 `pivot` ，用 `list_first_entry` 來取出元素 - 接著再把 `pivot` 先從 `list` 中移除，因為 `pivot` 並不用跟著遞迴 - 最後再初始化 `pivot` 節點 ```c struct item *itm = NULL, *is = NULL; GGGG (itm, is, &partition, list) { list_del(&itm->list); if (cmpint(&itm->i, &pivot->i) < 0) list_move(&itm->list, &list_less); else list_move(&itm->list, &list_greater); } ``` - `GGGG` 為 [`list_for_each_entry_safe`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L425) 用來走訪整個 `list` - 接著已經給定用以對節點內含值比較的函式 [`cmpint`](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-1) 來判斷節點數值跟 `pivot` 的大小 - 若是節點的數值小於 `pivot` ，則會將該節點移動到 `list_less` - 若是節點的數值大於等於 `pivot` ，則會將該節點移動到 `list_greater` :::info 其中 `list_del(&itm->list)` 應該可以不用，根據 [`list_move`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L317) 的定義，會先做 [`list_del`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L134) 來將節點刪除 ::: ```c HHHH (&pivot->list, &list_less); if (!list_empty(&list_greater)) list_splice_tail(&list_greater, IIII); if (!list_empty(&list_less)) list_splice_tail(&list_less, JJJJ); ``` - 應要將 `pivot` 移動到 `list_less` 的尾端，所以 `HHHH` 為 `list_move_tail` - 接著判斷如果 `list_greater` , `list_less` 不為空，就把它們串接到 `stack[++top]` 尾端 - 所以 `IIII`,`JJJJ` 皆為 `stack[++top]` ```c else { top++; list_splice_tail(&partition, &stack[top]); while (top >= 0 && list_is_singular(&stack[top])) { struct item *tmp = list_first_entry(&stack[top], struct item, list); list_del(&tmp->list); INIT_LIST_HEAD(KKKK); list_add_tail(&tmp->list, head); } } ``` - 若判斷 `partition` 所指向的 `list` 沒有節點或是只有一個節點，則會進入 `else` - 把 `partition` 串接到 `stack[top]` 尾端 - 進入迴圈後則是當 `stack[top]` 裡面只有一個節點時，就把 `stack[top]` 的節點加到 `head` 的尾端並初始化 - 所以 `KKKK` 應為 `&stack[top--]` :::info 其中 `list_del(&tmp->list)` 與 `list_add_tail(&tmp->list, head)` 可以根據 [`list_move_tail`](https://github.com/sysprog21/lab0-c/blob/master/list.h#L330) 的定義改成 `list_move_tail(&tmp->list, head);` ::: - 根據 38 到 41 行，可以得知 `stack` 是從數值大放到數值小的，也就是 `TOP` 會放最小值 - 所以當 `stack` 中只有一個節點，就表示為當前的最小值，並會進入 `else` 把該節點加到 `head` 的尾巴 ### 實驗結果 - 根據自己 [`lab0-c`](https://hackmd.io/@linhoward/lab0-2023) 量測 `merge_sort` 的 `Perf` 實驗，來實驗 `recursive` , `non-recursive` 版本 `qucik sort` 的效能 - **`recursive`** | # node | cache-misses | branches | instructions | context-switches | time | |:------:|:-----------:|:--:|:--:|:--:|:--:| |1000|1941|77,9096|527,1670|0|0.0009604| |10000|5036|613,9708|4443,3334|1|0.0056116| |100000|115,6576|6397,8997|4,6220,5173|0|0.070447| |1000000|7964,9292|6,7530,3741|48,1683,4390|4|1.23062| - **`non-recursive`** | # node | cache-misses | branches | instructions | context-switches | time | |:------:|:-----------:|:--:|:--:|:--:|:--:| |1000|1361|85,0934|575,9383|0|0.0009421| |10000|3604|696,6615|5004,3747|0|0.006474| |100000|120,2711|7312,8727|5,2320,1918|0|0.078943| |1000000|8768,6011|7,6389,7122|54,3217,4602|0|1.4274| --- ### 測驗 `3` - `xor_node_t` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; cmp [label="cmp"]; } ``` - `xor_list_t` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { count [label="{count}"]; head [label="{head}|{<cmp>cmp}"]; tail [label="{tail}|{<cmp>cmp}"]; label=xor_list_t } } ``` - `test_node` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { value [label="{value}"]; cmp [label="{xornode}|{<cmp>cmp}"]; label=test_node; } } ``` - 參考 [`XOR linked list`](https://en.wikipedia.org/wiki/XOR_linked_list) - `uintptr_t` 可以將指標儲存為整數 - C99 [7.18.1.4] Integer types capable of holding object pointers >The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer - 從 [`stdint.h`](https://sites.uclouvain.be/SystInfo/usr/include/stdint.h.html) 中可以發現對 `uintptr_t` 的定義 - 在 64 位元機器上， `intptr_t` 為 `long int` ， `uintptr_t` 為 `unsigned long int` - 非 64 位元機器上， `intptr_t` 為 `int` ， `uintptr_t` 為 `unsigned int` :::spoiler `stdint.h` ```c /* Types for `void *' pointers. */ #if __WORDSIZE == 64 # ifndef __intptr_t_defined typedef long int intptr_t; # define __intptr_t_defined # endif typedef unsigned long int uintptr_t; #else # ifndef __intptr_t_defined typedef int intptr_t; # define __intptr_t_defined # endif typedef unsigned int uintptr_t; #endif ``` ::: :::warning 列出 C 語言規格書相關的描述。 :notes: jserv ::: ```c #define XOR_COMP(a, b) ((xor_node_t *) (LLLL)) ``` - 可以得知這是一個要做 `XOR` 運算的函式，但我們必須要將 `a` , `b` 做 `casting` - 所以 `LLL` 應為 `(uintptr_t) a ^ (uintptr_t) b` ```c int main(void) { xor_list_t list; xor_node_t *p1, *p2; XORLIST_INIT(list); for (int i = 0; i < 1000; i++) { struct test_node *new = malloc(sizeof(struct test_node)); xornode_init(&new->xornode); new->value = i; xorlist_add(&list, &new->xornode); if (i == 5) p1 = &new->xornode; if (i == 6) p2 = &new->xornode; } ``` - 我們先看到 `main` - 首先會先初始化 `list` ，以及 `malloc` 一個 `test_node` ，接著將他們傳入 `xorlist_add` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { count [label="{count = 0}"]; {rank=same; count} head [label="{head}|{<cmp>cmp}"]; {rank=same; head} tail [label="{tail}|{<cmp>cmp}"]; {rank=same; tail} label=list } head:cmp -> tail:w tail:cmp -> head:e } ``` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { value [label="{value}"]; cmp [label="{xornode}|{<cmp>cmp}"]; label=new; } cmp:cmp -> null; } ``` ```c int xorlist_add(xor_list_t *list, xor_node_t *n) { xor_node_t *real_next; if (!n) return ENOMEM; xor_node_t *real_prev = &list->head; xor_node_t *node = real_prev->cmp; ``` - 接著看到 `xorlist_add` 來插入節點 - `real_prev` 指向 `list` 的 `head` - `node` 指向 `real_prev` 所指向 `head` 的 `cmp` 所指向的地方，也就是指向 `tail` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { count [label="{count = 0}"]; {rank=same; count} head [label="{head}|{<cmp>cmp}"]; {rank=same; head} tail [label="{tail}|{<cmp>cmp}"]; {rank=same; tail} label=list } node_[shape=plaintext] real_prev[shape=plaintext] head:cmp -> tail:w tail:cmp -> head:e real_prev -> head node_ -> tail } ``` ```c if (node == &list->tail) real_next = MMMM; else real_next = node; ``` - `node` 在初始狀態的話 `real_next` 就應是 `&list->tail` - 所以 `MMMM` 為 `&list->tail` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { count [label="{count = 0}"]; {rank=same; count} head [label="{head}|{<cmp>cmp}"]; {rank=same; head} tail [label="{tail}|{<cmp>cmp}"]; {rank=same; tail} label=list } node_[shape=plaintext] real_prev[shape=plaintext] real_next[shape=plaintext] head:cmp -> tail:w tail:cmp -> head:e real_next -> tail real_prev -> head node_ -> tail } ``` ```c real_prev->cmp = n; ``` - 首先將 `real_prev` 的 `cmp` 指向 `n` ，其中 - `n` 指向要加入的新節點 - `real_prev` 就是 `list` 的 `head` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { count [label="{count = 0}"]; {rank=same; count} head [label="{head}|{<cmp>cmp}"]; {rank=same; head} tail [label="{tail}|{<cmp>cmp}"]; {rank=same; tail} label=list } cmp [label="{new}|{<cmp>cmp}"]; n[shape=plaintext] node_[shape=plaintext] real_prev[shape=plaintext] real_next[shape=plaintext] head:cmp -> cmp tail:cmp -> head:w real_prev -> head node_ -> tail real_next -> tail n -> cmp cmp:cmp -> null } ``` ```c n->cmp = XOR_COMP(real_prev, real_next); ``` - 接著要計算 `n` 所指向節點的記憶體位址，存放到 `cmp` - 將前面一個節點的位址與後面一個節點的位址做 `XOR` - 假設 `head` 的位址為 `A` , `tail` 的位址為 `B` ，新節點的位址為 `C` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { count [label="{count = 0}"]; {rank=same; count} head [label="{head}|{<cmp>cmp}"]; {rank=same; head} tail [label="{tail}|{<cmp>cmp}"]; {rank=same; tail} label=list } cmp [label="{C}|{<cmp>A ⊕ B}"]; n[shape=plaintext] node_[shape=plaintext] real_prev[shape=plaintext] real_next[shape=plaintext] head:cmp -> cmp tail:cmp -> head:w real_prev -> head node_ -> tail real_next -> tail n -> cmp } ``` ```c real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP)); list->count++; return 0; } ``` - 接著要計算下一個節點 `cmp` 要存放的位址，其中 `real_prev` 要先和 `PPPP` 做 `XOR` 是為了要將 `head` 的位址消除掉，所以 `PPPP` 應為 `real_next->cmp` - $C \oplus (A \oplus A) = (A \oplus B) \oplus (A \oplus A) = (A \oplus B) = C$ - 最後 `count++` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { count [label="{count = 1}"]; {rank=same; count} head [label="{head}|{<cmp>cmp}"]; {rank=same; head} tail [label="{tail}|{<cmp>cmp}"]; {rank=same; tail} label=list } cmp [label="{C}|{<cmp>A ⊕ B}"]; n[shape=plaintext] node_[shape=plaintext] real_prev[shape=plaintext] real_next[shape=plaintext] head:cmp -> cmp tail:cmp -> cmp real_prev -> head node_ -> tail real_next -> tail n -> cmp } ``` [程式碼](https://github.com/linhoward0522/linux2023-quiz/tree/master/quiz1)