--- tags: linux2023 --- # 2023q1 Homework1 (quiz1) contributed by < [chiangkd](https://github.com/chiangkd) > ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz CPU family: 6 Model: 158 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 9 CPU max MHz: 3800.0000 CPU min MHz: 800.0000 BogoMIPS: 5599.85 ``` ## 測驗一 **延伸問題** - [ ] 解釋程式碼運作原理 - [ ] 針對 [Quick sort](https://en.wikipedia.org/wiki/Quicksort) 提出程式碼的改進方案並實作 - [ ] 引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響 - [ ] ==BONUS==: 嘗試對 Linux 核心提出排序程式碼改進的貢獻 <s>快速排序法原本並不是一個 stable sort ，而是 unstable sort</s> 根據 [Wikipedia](https://en.wikipedia.org/wiki/Quicksort)，一般常見的 quicksort 並不是 stable sort，例如 [Lomuto partition scheme](https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme)，[Hoare partition scheme](https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme)，但是也可以透過進行 [out-of-place](https://en.wikipedia.org/wiki/In-place_algorithm)，進行 stable 版本的 quick sort 實作，與一般需要 $O(nlogn)$ 空間複雜度的 in-place 版本不同，out-of-place 需要 $O(n)$ 的空間來儲存資訊，文中也提到可以透過 linked list 實作 stable sort 版本的 quick sort，但是此時是否有 [random access](https://en.wikipedia.org/wiki/Random_access) 就會非常重要。 >Although quicksort can be implemented as a stable sort using linked lists, it will often suffer from poor pivot choices without random access. :::warning 這句不精準，其實不是演算法設計的問題，而是實作手段，可參照 Wikipedia (要看英文版，避免讀中文詞條，後者充斥許多錯誤) 的解釋。 :notes: jserv >Fix it, Thanks! ::: **結構體** ```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` 的用途以及變數的宣告，可知 `AAA` = `item`，`BBB` = `list` ```c CCC (itm, is, head, list) { if (cmpint(&itm->i, &pivot->i) < 0) DDD (&itm->list, &list_less); else EEE (&itm->list, &list_greater); } ``` 根據 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的定義，可以放入 4 個引數的僅有 `list_for_each_entry_safe` = `CCC` ，且 `DDD`、`EEE` 負責根據當前迭代到的值大於或是小於 `pivot` 來進行節點交換 - 當迭代到的值小於 `pivot` 的值 (`if` 條件滿足) 則將該節點移動至 `list_less` 節點後面，若否，則移動到 `list_greater` 節點後面 - `DDD` = `EEE` = `list_move_tail` 透過遞迴的方式繼續對 `list_less`、 `list_greater` 做一樣的處理，此時注意到最後兩行為 ```c list_add(&pivot->list, head); list_splice(&list_less, head); FFF(&list_greater, head) ``` 代表每次回傳都是將已經排序好的 list 接在 `head` 後面，其中，首先將 `pivot` 放在 `head` 後，再將代表比 `pivot` 小的 `list_less` 放在 `head` 後面，最後一部將比 `pivot` 大的 `list_greater` 放在 `pivot` 右側，也就是目前由 `head` 開頭的 list 的最後面，故得知 `list_splice_tail` = `FFF`. ```graphviz digraph g{ node [shape=box]; pivot[shape=plaintext] head[label=head][shape=circle] 5[label=5]; 4[label=4]; 2[label=2]; 3[label=3]; 1[label=1]; less[label=less][shape=plaintext] greater[label=greater][shape=plaintext] none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] subgraph cluster_0 { style=invis; { rank=same; head->5->4->2->3->1; } } pivot -> 5; subgraph less { { rank=same; less->none1; } } subgraph greater { { rank=same; greater->none2 } } } ``` ```c struct item *pivot = list_first_entry(head, AAA, BBB); list_del(&pivot->list); ``` ```graphviz digraph g{ node [shape=box]; pivot[shape=plaintext] head[label=head][shape=circle] 5[label=5]; 4[label=4]; 2[label=2]; 3[label=3]; 1[label=1]; less[label=less][shape=plaintext] greater[label=greater][shape=plaintext] none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] subgraph cluster_0 { style=invis; { rank=1; head->4->2->3->1; } } pivot -> 5; subgraph less { { rank=1; less->none1; } } subgraph greater { { rank=1; greater->none2 } } } ``` ```c struct item *itm = NULL, *is = NULL; list_for_each_entry_safe (itm, is, head, list) { if (cmpint(&itm->i, &pivot->i) < 0) list_move_tail(&itm->list, &list_less); else list_move_tail(&itm->list, &list_greater); } ``` ```graphviz digraph g{ node [shape=box]; pivot[shape=plaintext] head[label=head][shape=circle] 5[label=5]; 4[label=4]; 2[label=2]; 3[label=3]; 1[label=1]; less[label=less][shape=plaintext] greater[label=greater][shape=plaintext] none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] subgraph cluster_0 { style=invis; { rank=1; head->none1; } } pivot -> 5; subgraph less { { rank=1; less->4->2->3->1; } } subgraph greater { { rank=1; greater->none2 } } } ``` ```c list_sort(&list_less); ``` ```graphviz digraph g{ node [shape=box]; pivot[shape=plaintext] head[label=head][shape=circle] 4[label=4]; 2[label=2]; 3[label=3]; 1[label=1]; less[label=less][shape=plaintext] greater[label=greater][shape=plaintext] none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] subgraph cluster_0 { style=invis; { rank=same; head->4->2->3->1; } } pivot -> 4; subgraph less { { rank=same; less->none1; } } subgraph greater { { rank=same; greater->none2 } } } ``` ```graphviz digraph g{ node [shape=box]; pivot[shape=plaintext] head[label=head][shape=circle] 4[label=4]; 2[label=2]; 3[label=3]; 1[label=1]; less[label=less][shape=plaintext] greater[label=greater][shape=plaintext] none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] subgraph cluster_0 { style=invis; { rank=1; head->none1; } } pivot -> 4; subgraph less { { rank=1; less->2->3->1; } } subgraph greater { { rank=1; greater->none2 } } } ``` ```graphviz digraph g{ node [shape=box]; pivot[shape=plaintext] head[label=head][shape=circle] 2[label=2]; 3[label=3]; 1[label=1]; less[label=less][shape=plaintext] greater[label=greater][shape=plaintext] none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] subgraph cluster_0 { style=invis; { rank=1; head->none1; } } pivot -> 2; subgraph less { { rank=1; less->1; } } subgraph greater { { rank=1; greater->3 } } } ``` 以此類推最後透過 ```c list_add(&pivot->list, head); list_splice(&list_less, head); list_splice_tail(&list_greater, head); ``` 先把節點放進去，比節點大的放右邊，比節點小的放左邊，完成排序 ```graphviz digraph g{ node [shape=box]; head[label=head][shape=circle] 2[label=2]; 3[label=3]; 1[label=1]; none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] subgraph cluster_0 { style=invis; { rank=same; head->1->2->3; } } } ``` ```graphviz digraph g{ node [shape=box]; head[label=head][shape=circle] 4[label=4]; 2[label=2]; 3[label=3]; 1[label=1]; none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] subgraph cluster_0 { style=invis; { rank=same; head->1->2->3->4; } } } ``` ```graphviz digraph g{ node [shape=box]; head[label=head][shape=circle] 5[label=5]; 4[label=4]; 2[label=2]; 3[label=3]; 1[label=1]; none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] subgraph cluster_0 { style=invis; { rank=same; head->1->2->3->4->5; } } } ``` --- ## 測驗二 **延伸問題** - [ ] 解釋程式碼運作原理，指出設計和實作的缺失 - [ ] 比較測驗 `1` 和測驗 `2` 的程式碼，設計實驗來分析二者效能，解釋為何非遞迴的實作未能總是比遞迴的實作快 - [ ] 提出效能改進方案，特別是避免依賴 `MAX_DEPTH` - [ ] 引入 [Introsort](https://en.wikipedia.org/wiki/Introsort), 也就是 quick sort 和 heap sort (或其他可避免前者 $O(n^{2})$ 最差時間複雜度的演算法)。加入 heapsort 的原因為，當 quicksort 迭代 $2 \times \log n$ 次後還排序完成，那就很可能會得到 $O(n^{2})$ 時間複雜度。此時切換為 heap sort 能將其時間複雜度控制在 $O(n \log n)$ 首先根據 [Optimized QuickSort](https://alienryderflex.com/quicksort/) 的所提及的方法與原版(這裡原版指的是網站指出的 wikipeida 版本)比較，包含了以下幾個優點 - 避免使用 function call ，減少 CPU 花在進入 function、離開 function 的時間 - 不使用 stack 來儲存資料，文中提及雖然 recursive 版本的 quick sort 看起來直觀簡單，但是會使用大量的 private stack 來儲存資料，會比起直接使用 `beg[]`、 `end[]` arrau 來的慢，且有機會造成 stack overflow，而文中提及的方法透過設定 `MAX_LEVELS` 來回傳 `NO` 來避免產生 failure - 在每一輪中，原版會 `swap` 非常多次，但文中版本僅 swap pivot 以及某個節點一次 - 其他像是多次移動同個物件、冗餘的移動、和自己進行 swap 都在文中新版本有所改善 測驗 2 給定具有 `MAX_DEPTH = 512` 的 stack 來模擬遞迴的過程且使用 `INIT_LIST_HEAD` 來初始化 `head` (此處上端為 `stack[0]` 依次往下遞增為 `stack[1], stack[2] ... stack[MAX_DEPTH-1]`) ```c struct list_head stack[MAX_DEPTH]; for (int i = 0; i < MAX_DEPTH; i++) INIT_LIST_HEAD(&stack[i]); ``` ```graphviz digraph list_head { rankdir=LR node[shape=record, style=bold]; stack [label="stack|{<prev1>prev|<next1>next}|{<prev2>prev|<next2>next}|...|{<prevn>prev|<nextn>next}"]; {rank=same; stack:prev1; stack:next1;} {rank=same; stack:prev2; stack:next2;} {rank=same; stack:prevn; stack:nextn;} stack:next1:e -> stack:prev1:w[arrowhead=normal, arrowtail=normal, dir=both]; stack:next2:e -> stack:prev2:w[arrowhead=normal, arrowtail=normal, dir=both]; stack:nextn:e -> stack:prevn:w[arrowhead=normal, arrowtail=normal, dir=both]; } ``` 把尚未排序好的 list 放進 stack 中 ```c int top = -1; list_splice_init(head, &stack[++top]); ``` ```graphviz digraph list_head { rankdir=LR node[shape=record, style=bold]; 4[label=4]; 5[label=5]; 6[label=6]; 2[label=2]; 8[label=8]; 3[label=3]; 1[label=1]; 7[label=7]; stack [label="stack|{<prev1>prev|<next1>next}|{<prev2>prev|<next2>next}|...|{<prevn>prev|<nextn>next}"]; {rank=same; stack:prev1; stack:next1;} {rank=same; stack:prev2; stack:next2;} {rank=same; stack:prevn; stack:nextn;} stack:next1:e ->4->5->3->6->2->8->1->7 stack:next2:e -> stack:prev2:w[arrowhead=normal, arrowtail=normal, dir=both]; stack:nextn:e -> stack:prevn:w[arrowhead=normal, arrowtail=normal, dir=both]; } ``` - 執行完上述程式碼時時 `top` 為 `0`，進入 `while` 迴圈 ```c INIT_LIST_HEAD(&partition); list_splice_init(&stack[top--], &partition); ``` ```graphviz digraph g{ node [shape=record]; rankdir=LR partition[label=partition][shape=plaintext] 4[label=4]; 5[label=5]; 6[label=6]; 2[label=2]; 8[label=8]; 3[label=3]; 1[label=1]; 7[label=7]; partition->4->5->6->2->8->3->1->7 } ``` - 執行完上述程式碼時時 `top` 為 `-1`，且符合第一個 `if` 條件，進入 `if` 迴圈 ```c struct list_head list_less, list_greater; INIT_LIST_HEAD(&list_less); INIT_LIST_HEAD(&list_greater); struct item *pivot = list_first_entry(&partition, struct item, list); list_del(&pivot->list); INIT_LIST_HEAD(&pivot->list); ``` ```graphviz digraph g{ rankdir=LR node [shape=box]; pivot[shape=plaintext] partition[label=partition][shape=plaintext] 4[label=4]; 5[label=5]; 6[label=6]; 2[label=2]; 8[label=8]; 3[label=3]; 1[label=1]; 7[label=7]; less[label=less][shape=plaintext] greater[label=greater][shape=plaintext] none1[label=""][shape=plaintext] none2[label=""][shape=plaintext] pivot->4 partition->5->6->2->8->3->1->7 less->none1 greater->none2 } ``` 首先把 `head` 當我 pivot ，從對 list 左邊開始找，找到小於 pivot 的值就會放入，(文中使用 `beg[]`， `end[]` 紀錄比較過程)， linked list 則透過與測驗 1 一樣的 `list_less`、`list_greater` 來儲存資訊。 ```c GGGG (itm, is, &partition, list) { ... } ``` - 與測驗一相同， `GGGG` 為 `list_for_each_entry_safe` 將各個節點和 `pivot` 比大小並將對應結果分別放到 `list_less` 以及 `list_greater` ```c list_for_each_entry_safe(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); } ``` ```graphviz digraph g{ rankdir=LR node [shape=box]; pivot[shape=plaintext] partition[label=partition][shape=plaintext] 4[label=4]; 5[label=5]; 6[label=6]; 2[label=2]; 8[label=8]; 3[label=3]; 1[label=1]; 7[label=7]; less[label=less][shape=plaintext] greater[label=greater][shape=plaintext] none1[label=""][shape=plaintext] pivot->4 partition->none1 less->1->3->2 greater->7->8->6->5 } ``` 接著將 `pivot` 如同測驗 1 一樣在將 `less` 和 `greater` 合併時 `pivot` 會在中間，所以根據題目是將 `pivot` 放在 `less` 的某處，應為 `less` 的尾端 ```c HHHH (&pivot->list, &list_less); ``` - 故 `HHHH` 為 `list_move_tail` ```graphviz digraph g{ rankdir=LR node [shape=record]; 4[label=4]; 5[label=5]; 6[label=6]; 2[label=2]; 8[label=8]; 3[label=3]; 1[label=1]; 7[label=7]; less[label=less][shape=plaintext] greater[label=greater][shape=plaintext] less->1->3->2->4 greater->7->8->6->5 } ``` 再來就是和測驗 1 不同的部份，透過 `stack` 取代遞迴的過程，故將 `less` 以及 `greater` 放進去 `stack` (記得在此處 `top` 為 `-1`，為原本放未排序的 list 的地方，取出來做處理得時候有 -1)，在推進去 `stack` 時為 `&stack[++top]` - 考試的時候寫成 `&stack[top++]`，不夠細心 ```c if (!list_empty(&list_greater)) list_splice_tail(&list_greater, IIII); if (!list_empty(&list_less)) list_splice_tail(&list_less, JJJJ); ``` - `IIII` = `JJJJ` = `&stack[++top]` ```graphviz digraph list_head { rankdir=LR node[shape=record, style=bold]; 4[label=4]; 5[label=5]; 6[label=6]; 2[label=2]; 8[label=8]; 3[label=3]; 1[label=1]; 7[label=7]; stack [label="stack|{<prev1>prev|<next1>next}|{<prev2>prev|<next2>next}|...|{<prevn>prev|<nextn>next}"]; {rank=same; stack:prev1; stack:next1;} {rank=same; stack:prev2; stack:next2;} {rank=same; stack:prevn; stack:nextn;} stack:next1:e ->7->8->6->5; stack:next2:e ->1->3->2->4; stack:nextn:e -> stack:prevn:w[arrowhead=normal, arrowtail=normal, dir=both]; } ``` 因為 `top` 值在推送進 stack 時有增加，所以 `while` 迴圈會持續運作，接著會對 `1 -> 3 -> 2 -> 5` 這個 list 做上述一樣的動作，持續到第一個 `if` 條件不滿足，也就是不滿足 ```c if (!list_empty(&partition) && !list_is_singular(&partition)) ``` - 代表從 `stack` 取出的節點為空或者是只有一個節點，此時進入 `else` 條件， 在第一次進入 `else` 前的 `stack` 樣子為 ```graphviz digraph list_head { rankdir=LR node[shape=record, style=bold]; 4[label=4]; 5[label=5]; 6[label=6]; 2[label=2]; 8[label=8]; 3[label=3]; 1[label=1]; 7[label=7]; partition[label=partition][shape=plaintext] stack [label="stack| {<prev1>prev|<next1>next}| {<prev2>prev|<next2>next}| {<prev3>prev|<next3>next}| {<prev4>prev|<next4>next}| {<prev5>prev|<next5>next}| ...| {<prevn>prev|<nextn>next}"]; stack:next1:e ->7->8->6->5; stack:next2:e ->3->2->4; partition->1; } ``` 偵測到 `stack` 的最頂端 (尚未從 `stack` 取出的圖中最下面)，僅有一個節點 `1`，取出後 (此時的 `top` 會在指向 `3->2->4` 的位置，因為在切出 `partition` 的時候有做 `top--` 的動作)進入 `else` 條件首先要先 `top++` push `top` 一格 ```c 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` 放回 `stack[top]`，注意到題目中進行 `list_del(&tmp->list)` 且後面有 `list_add_tail(&tmp->list, head)`，代表已經將該節點放到 `head` 後面，以完成排序的部份，故 `KKKK` 必須對 `stack` pop 一格，`KKKK` = `&stack[top--]` 總結進入到 `else` 才會透過 `list_add_tail(&tmp->list, head);` 將排序好的節點放到 `head` 後面，且進入 `else` 的條件為此時 `stack[top]` 的位置僅有一個節點，且根據上述過程，`stack[top]` 必為未排序的 list 中最小的那個節點 (在推進去 `stack` 的時候是先推 `greater` 後再推 `less`，所以比較小的節點會在上面)，以此依序將最小的節點接在 `head` 後面完成排序。 --- ## 測驗三 **延伸問題** - [ ] 解釋上述程式碼運作原理，指出其實作缺陷並改進 - [ ] 在上述 XOR linked list 的基礎，實作測驗 `1` 和 `2` 提及的快速排序演算法，注意要引入你改進效能的版本 - [ ] 修改 `xorlist_destroy`，使其不急著釋放記憶體，而搭配 [atexit(3)](https://man7.org/linux/man-pages/man3/atexit.3.html) 並在程式即將結束執行時，才批次處理資源釋放 在關鍵巨集中 ```c #define XOR_COMP(a, b) ((xor_node_t *) (LLLL)) ``` 根據函式名稱以及在程式內的用途知其為將 `a` 和 `b` 做 exclusive or 運算 - `LLLL` = `(uintptr_t)(a) ^ (uintptr_t)(b)` 另一個常用函式為 `address_of`，在透過 `assert` 確認 `n1`、`n2` 都為非 0 值後搭配 `XOR_COMP` 巨集進行 exclusive or 運算回傳下一個節點地址。 ```c static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2) { assert(n1 && n2); return XOR_COMP(n1, n2); } ``` XOR List 的迭代過程透過前一個的地址以及這一格的 `link` 進行 `xor` 運算來獲得下一格的位址，也就是說當前位置的 `link` 可以透過前後兩個點的地址進行 `xor` 運算得到 根據上述，程式內也定義了 `xor_list_t` 來代表 list 所需的資訊 ```c typedef struct _xor_list_struct { xor_node_t head, tail; uint32_t count; } xor_list_t; ``` - 根據前面敘述，要拿到當前節點的 `link` ，需要前後兩個點的地址，所以在這裡也直接定義了 `head` 以及 `tail` 代表 `list` 的頭尾 ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { node [shape=record]; head [label="{head}"]; tail [label="{tail}"]; count [label="count"][shape=plaintext]; style=bold; label=list } } ``` 查看 `xorlist_for_each` 巨集 ```c #define xorlist_for_each(node, rp, rn, list) \ for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \ rn = address_of(rp, node->cmp), rp = node, node = rn) ``` - 可以看到在迭代的過程中 `rn` 為下一個節點的地址，是透過 `rp` (前一個節點的地址) 和 `node->cmp` (當前節點的 link) 做 `xor` 運算得到。 在 `main` 中，先將 0~100 的值透過 `xorlist_add` 加入到 `list` 中， ```c xornode_init(&new->xornode); new->value = i; xorlist_add(&list, &new->xornode); ``` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; null[shape=plaintext] subgraph cluster_0 { node [shape=record]; head [label="{head}"]; tail [label="{tail}"]; count [label="count"][shape=plaintext]; style=bold; label=list } subgraph cluster_1 { label="new node 1" value[label=value] xornode[label="xornode|{<cmp>cmp}" ] } head->xornode:cmp xornode:cmp->null } ``` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; null[label=null][shape=plaintext] subgraph cluster_0 { node [shape=record]; head [label="{head}"]; tail [label="{tail}"]; count [label="count"][shape=plaintext]; style=bold; label=list } subgraph cluster_1 { label="new node 1" value[label=value] xornode[label="<label>xornode|{<cmp>cmp}" ] } subgraph cluster_2 { label="new node 2" value2[label=value] xornode2[label="<label>xornode|{<cmp>cmp}" ] } head->xornode:label xornode:cmp->xornode2:label xornode2:cmp->null } ``` 這裡的 `cmp` 若是要取得下一個節點的地址則需要與前一個節點地址做 `xor` 考慮題目及，題目給的參考執行輸出， ```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; if (node == &list->tail) real_next = MMMM; else real_next = node; real_prev->cmp = n; n->cmp = XOR_COMP(real_prev, real_next); real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP)); list->count++; return 0; } ``` - 題目 `MMMM` 用以處理初始的條件，在進入 `xorlist_add` 之前已經呼叫過 `XORLIST_INIT(h)` 巨集，將 `head` 以及 `tail` 的 `cmp` 互相設定為對方，在初始條件下 `real_next` 即為 `list_tail`，故 `MMMM` = `&list->tail`，此時這個 `if-else` 條件似乎顯得沒必要? 可直接使用 `real_next` = `node` 做取代 (待驗證) 考慮到若 `if` 條件滿足，則代表 `node = real_prev->cmp` 為 `&list->tail`，此時 `node` 等價於 `&list_tail` ，因為是將新的節點 `n` 插入至 list 的第一個節點，且 `node` 指向 `real_prev` 的壓縮地址 (`cmp`)，因為是 `head` 的關係所以壓縮地址必為下一個節點地址，同時 `node` 也會是，故直接省略 `if` 條件也可以正常執行 ```diff 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; - if (node == &list->tail) - real_next = MMMM; - else - real_next = node; + real_next = node; real_prev->cmp = n; n->cmp = XOR_COMP(real_prev, real_next); real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP)); list->count++; return 0; } ``` 根據題目顯示，`list_add` 是新增節點在 list 的頭 進入 `list_add` 初始狀態如圖 `A`、`B` 為該節點地址 ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; head[label="A|{<cmp>cmp=B}"]; tail[label="B|{<cmp>cmp=A}"]; head:cmp->tail:cmp[dir=both] } ``` 在初始狀態新增一個節點地址為 `C` 後的結果應為 ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; head[label="A|{<cmp>cmp=B}"]; tail[label="B|{<cmp>cmp=C}"]; node1[label="C|{<cmp>cmp=A \oplus B}"] n[label="n"][shape=plaintext] rn[label="real_next"][shape=plaintext] rp[label="real_prev"][shape=plaintext] head:cmp->node1:cmp[dir=both] node1:cmp->tail:cmp[dir=both] n->node1 rn->tail rp->head } ``` - 而 `PPPP` 用以更新 `real_next->cmp` 的值，從 xor-list 的方法知道該節點的 `cmp` 為前後節點地址做 `xor` 運算 ```c real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP)); ``` 此時要讓 `real_next->cmp` 從 A 更新為 C，進行運算 $C \oplus (A\oplus PPPP)$，此時 `PPPP` 應為 A ，用以消除 A (因為 $A\oplus A = 0$)，故 `PPPP` 為 `real_next->cmp`
Last changed by  
 
坤諦江
390

Read more

2023q1 Homework1 (lab0)

contributed by < chiangkd > :::warning :warning: 留意細節！唯有重視小處並步步為營，方可挑戰原始程式碼達到三千萬行的 Linux 核心 :notes: jserv Got it! 謝謝老師 ::: 作業要求

3/24/2024
將現有的 Raspberry PI 系統備份

踩了不少雷，紀錄一下

12/6/2023
Run FreeRTOS on VexRiscv and Measure/Tweak context switch overhead

Github : FreeRTOS-on-VexRiscv Requirement and Expectation :::warning Reproduce Run FreeRTOS and multitasking on VexRiscv with FreeRTOS 202212.00 released or latest Study Reference Link to understand how to measure FreeRTOS context switch Understand how to accurately measure cycle count and related latencyInclude timer interrupt. Run above at simulator and quantify the performence about context switch

5/29/2023
2023q1 Homework7 (ktcp)

作業說明 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ lscpu

5/11/2023
Read more from 坤諦江
Published on HackMD