2023q1 Homework1 (lab0)

--- tags: linux2023 --- # 2023q1 Homework1 (lab0) contributed by < [chiangkd](https://github.com/chiangkd) > :::warning :warning: 留意細節！唯有重視小處並步步為營，方可挑戰原始程式碼達到三千萬行的 Linux 核心 :notes: jserv > Got it! 謝謝老師 ::: ## 作業要求 Request followed [2023 年 Linux 核心設計/實作課程作業 —— lab0](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-f) - [ ] 修改 `queue.[ch]` 以完成 `make test` 自動評分系統的所有項目 - [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，搭配 Massif 視覺化 - [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差 - [ ] 確保 `qtest` 提供的 `web` 命令可以搭配上述佇列使用 - [ ] 新增命令 `shuffle`, 參考 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) - [ ] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10`，觀察亂數字串分佈 - [ ] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。 ## 開發環境 ```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 ``` ## 改進 `queue.c` ### 結構體 `list_head` 為 doubly-linked list 的 node 或 head ```c struct list_head { struct list_head *prev; struct list_head *next; }; ``` ```graphviz digraph list_ele { rankdir=LR; node[shape=record]; head [label="{<left>prev|<right>next}", style=bold]; } ``` `element_t` 為 linked list 的 element ```c typedef struct { char *value; struct list_head list; } element_t; ``` `element_t` 這個結構體，除了要用來找尋 `list` 整體的原因，透過嵌入 `list_head` 給除了 `Head` 可以搭配 `container_or` 巨集也可得知 ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { node [shape=record]; value [label="{value}"]; head [label="{<prev>prev|<next>next}"]; style=bold; label=element_t } } ``` ![](https://i.imgur.com/3b5ra8Q.png) - 參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list) ```c typedef struct { struct list_head head; int size; } queue_chain_t; ``` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { node [shape=record]; head [label="{<prev>prev|<next>next}"]; value [label="{size}"]; style=bold; label=queue_chain_t } } ``` `queue_context_t` 為 chain of queues ```c typedef struct { struct list_head *q; struct list_head chain; int size; int id; } queue_contex_t; ``` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_1 { node [shape=record]; q_1 [label="q|{<prev>prev|<next>next}"]; subgraph cluster_A { chain [label="<label>chain|{<prev>prev|<next>next}"]; s [label="{size}"]; style="dashed,bold"; color=red; label=queue_chain_t } int [label="{int}"]; style=bold; label=queue_context_t } subgraph cluster_2 { node [shape=record]; q_2 [label="q|{<prev>prev|<next>next}"]; subgraph cluster_B { chain_2 [label="<label>chain|{<prev>prev|<next>next}"]; s_2 [label="{size}"]; style="dashed,bold"; color=red; label=queue_chain_t } int_2 [label="{int}"]; style=bold; label=queue_context_t } chain:next->chain_2:label chain_2:prev->chain:label } ``` 在多個 queue 之間的操作，如 `do_queue` 是透過 `chain` 來連接起來的，也因此在 `q_merge` function 中給定的參數為 `list_head *head`，但查看 `do_merge` 之後才會看到這裡傳入的是 `queue_chain_t` 的 `chain`，也是連接各個 queue 的 linked list。 ```c if (current && exception_setup(true)) len = q_merge(&chain.head); ``` 做個驗證，在 `q_merge` 中來測試並呼叫 `merge` command，函式中暫時先撰寫透過傳入的 `chain` 找其所屬 `element_t` 的 value ```c printf("value = %s\n", list_entry(list_entry(head->next, queue_contex_t, chain)->q->next, element_t, list)->value); ``` ```shell cmd> new l = [] cmd> ih Hello l = [Hello] cmd> it CKD l = [Hello CKD] cmd> merge value = Hello ``` - 印出 list 的第一個 `element_t` 的 `value` :::warning 與其複製程式碼，你應揣摩背後的設計考量，特別是你的推理和驗證。 :notes: jserv > 新增示意圖及個人認為設計考量(待補充) ::: :::info 題外話，在化 graphviz 的時候想要虛線功能，但不知道關鍵字是什麼 (加粗為 `bold`，直覺認為是 `dot`)，問了一下 chatGPT 之後它告訴我是 `dotted` ![](https://i.imgur.com/IyEAwvM.png) ::: ### q_new ```c struct list_head *q_new() { struct list_head *q_head = malloc(sizeof(*q_head)); if (!q_head) // If allocate failed return NULL; INIT_LIST_HEAD(q_head); return q_head; } ``` :::warning 改為更精簡的敘述: ```c struct list_head *q_head = malloc(sizeof(*q_head)); ``` 修正程式碼註解用語。 :notes: jserv >Fixed. Thanks! ::: ### q_free ```c void q_free(struct list_head *l) { if(!l) return; element_t *c, *n; list_for_each_entry_safe(c, n, l, list) { list_del(&c->list); q_release_element(c); } free(l); // q_new function has malloced it } ``` ### q_insert_head ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *new_element = malloc(sizeof(element_t)); // new head element if(!new_element) // If allocate failed return false; size_t len = strlen(s) + 1; // plus 1 for `\0` new_element->value = malloc(len * sizeof(char)); if (!new_element->value) { // If allocate failed free(new_element); return false; } memcpy(new_element->value, s, len); list_add(&new_element->list, head); return true; } ``` :::warning 能否避免呼叫 `memcpy` 並精簡程式碼？ :notes: jserv >改為利用 `strdup` ::: 發現在 `harness.c` 中已有定義 `strdup`（`test_strdup`），此函式回傳輸入 string `s` 的指標，並回傳一個具有同樣內容的指標，即複製字串。透過此函式可以直接取代掉原實作方法中的計算長度、分配空間、記憶體複製操作 ```diff bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *new_element = malloc(sizeof(element_t)); // new head element if (!new_element) // allocated failed return false; - size_t len = strlen(s) + 1; // plus 1 for `\0` - new_element->value = malloc(len * sizeof(char)); + new_element->value = strdup(s); if (!new_element->value) { // allocated failed free(new_element); return false; } - memcpy(new_element->value, s, len); list_add(&new_element->list, head); return true; } ``` ### q_insert_tail 和 `q_insert_head` 思路相同, 僅修改 `head` 和 `tail` 的差別 :::warning 既然 `q_insert_tail` 和 `q_insert_head` 存在相似的流程，能否用 `q_insert_head` 來實作 `q_insert_tail` 呢？ :notes: jserv >新增相關敘述 ::: ```c bool q_insert_tail(struct list_head *head, char *s) { if(!head) return false; element_t *new_element = malloc(sizeof(element_t)); // new tail element if(!new_element) // If allocate failed return false; size_t len = strlen(s) + 1; // plus 1 for `\0` new_element->value = malloc(len * sizeof(char)); if(!new_element->value) { // If allocate failed free(new_element); return false; } memcpy(new_element->value, s, len); list_add_tail(&new_element->list, head); return true; } ``` `q_insert_head` 以及 `q_insert_tail` 差異僅在新增節點於給定 `head` 的後一個位置 (`next` 所指方向)，以及前一個位置 (`prev` 所指方向)，故可以透過 `q_insert_head` 來實作 `q_insert_tail` ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; return q_insert_head(head->prev, s); } ``` 翻譯成白話文的意思就是，在 `head` 的前面插入節點等效於在 `head` 的前一個節點的後面插入節點。 ### q_remove_head ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if(!head) return NULL; sp = malloc(bufsize); element_t *rm_element = container_of(head->next, element_t, list); strncpy(sp, rm_element->value, bufsize - 1); sp[bufsize - 1] = '\0'; list_del(head->next); return rm_element; } ``` - `container_of` 這個巨集透過給定成員 (member) 的記憶體地址、結構體的型態，以及成員的名稱, 傳回該結構體的起始地址 ```c #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) ``` 上述雖然可以成功 remove head, 但是產生錯誤訊息 ``` ERROR: Failed to store removed value ``` 查看 `qtest.c` 中 `do_remove` 的實作 ```c removes[string_length + STRINGPAD] = '\0'; if (removes[0] == '\0') { report(1, "ERROR: Failed to store removed value"); ok = false; } ``` :::warning implementation 應翻譯為「實作」，注意[「作」和「做」的落差](https://blog.udn.com/mobile/tsengche/3054517)」。參見 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) 的 "implement" 項目。 :notes: jserv > 已修正，謝謝老師 ::: - `removes[0] = '\0'` 會報此錯誤, 且 `removes` 在 `qtest.c` 已經 `malloc` 如果在 `q_remove` 中再次 `malloc` 一次的話 sp 的地址會被覆蓋掉, 即原先 `removes` 的地址其實並沒有存東西, 所以這裡的 `sp` 不該 `malloc` 在佇列為空時繼續使用命令 `rh` 會造成 segmentation fault, 當佇列為空時僅有 `Head` 一個點, 沒辦法通過 `container_of` 找到對應節點 ``` l = [] cmd> rh Warning: Calling remove head on empty queue Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped) ``` 加入 `list_empty` 來判斷該鏈結串列是不是 empty 以及外部 `removes` 是否有 `malloc` 成功 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *rm_element = container_of(head->next, element_t, list); if (sp) { strncpy(sp, rm_element->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(head->next); return rm_element; } ``` 這裡的 `container_of` 可以用 `list_first_entry` 巨集代替, 增加程式可讀性 (defined in `list.h`) ```c #define list_entry(node, type, member) container_of(node, type, member) #define list_first_entry(head, type, member) \ list_entry((head)->next, type, member) ``` - 接下來的 q_remove_tail 也是一樣可以用 `list_last_entry` 取代 `container_of` ### q_remove_tail 和 `q_remove_head` 思路相同, 僅修改 `head` 和 `tail` 的差別 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if(!head || list_empty(head)) return NULL; element_t *rm_element = list_last_entry(head, element_t, list); if(sp) { strncpy(sp, rm_element->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(head->prev); return rm_element; } ``` ### q_size 走訪整個鏈結串列以計算長度 ```c int q_size(struct list_head *head) { if(!head) return 0; int cnt = 0; struct list_head *n = head->next; // next list node while (n != head) { n = n->next; cnt++; } return cnt; } ``` :::warning TODO: 善用既有的巨集，撰寫出更精簡的程式碼 :notes: jserv > 用 `list_for_each` 取代現有 for loop ::: ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; int cnt = 0; struct list_head *n; list_for_each (n, head) cnt++; return cnt; } ``` 其中 `list_for_ecah` 定義為 ```c #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) ``` ### q_delete_mid :::warning 本例為 circular doubly-linked list，你應該實作更少記憶體操作的程式碼。 :notes: jserv ::: :::info 原先版本使用快慢指標，快指標會走訪整個 list 一圈，慢指標會走一半的 list 找到中間點，總共會走大概 1.5 倍長度的 list，參考 [freshLiver](https://hackmd.io/@freshLiver/2022q1-hw1#%E9%87%9D%E5%B0%8D%E4%BD%87%E5%88%97%E7%9A%84%E6%93%8D%E4%BD%9C) 過往作業使用到兩個指標前後從佇列頭尾迭代，透過交會點/即將交會點來判斷佇列中間點 ::: - 參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List) ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head **indir; indir = &head; for(struct list_head *p = head->prev; (*indir)->next != p && (*indir) != p; ) { indir = &(*indir)->next; p = p->prev; } struct list_head *temp = (*indir)->next; list_del(temp); q_release_element(list_entry(temp, element_t, list)); return true; } ``` 在這邊使用 indirect pointer 看起來沒有特別的優勢，反而在過程多了 `*indir` 這一個記憶體操作 :::warning 對照編譯器輸出的組合語言和 `perf` 來確認你的觀點，否則這個「看來」流於武斷。注意編譯器最佳化的影響 :notes: jserv > 初步分析以補充，待補如果設定編譯器為 `-O0` 後的組合語言差異 ::: ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head *n = head->next; for(struct list_head *p = head->prev; n->next != p && n != p; ) { n = n->next; p = p->prev; } list_del(n); q_release_element(list_entry(n, element_t, list)); return true; } ``` 且如此運算過後 `n` 會正好指向要移除之節點，不需要在額外設定指向要刪除的節點進行操作， #### 編譯器輸出的組合語言用 `objdump -d queue.o` 查看編譯器輸出的組合語言 ```c 00000000000002d3 <q_delete_mid>: 2d3: f3 0f 1e fa endbr64 2d7: 48 85 ff test %rdi,%rdi 2da: 74 52 je 32e <q_delete_mid+0x5b> 2dc: 53 push %rbx 2dd: 48 8b 5f 08 mov 0x8(%rdi),%rbx 2e1: 48 39 df cmp %rbx,%rdi 2e4: 74 4e je 334 <q_delete_mid+0x61> 2e6: 48 8b 17 mov (%rdi),%rdx 2e9: 48 8b 43 08 mov 0x8(%rbx),%rax 2ed: 48 39 d3 cmp %rdx,%rbx 2f0: 74 19 je 30b <q_delete_mid+0x38> 2f2: 48 39 c2 cmp %rax,%rdx 2f5: 74 14 je 30b <q_delete_mid+0x38> 2f7: 48 8b 12 mov (%rdx),%rdx 2fa: 48 89 c3 mov %rax,%rbx 2fd: 48 8b 40 08 mov 0x8(%rax),%rax 301: 48 39 da cmp %rbx,%rdx 304: 74 05 je 30b <q_delete_mid+0x38> 306: 48 39 d0 cmp %rdx,%rax 309: 75 ec jne 2f7 <q_delete_mid+0x24> 30b: 48 8b 13 mov (%rbx),%rdx 30e: 48 89 10 mov %rdx,(%rax) 311: 48 89 42 08 mov %rax,0x8(%rdx) 315: 48 8b 7b f8 mov -0x8(%rbx),%rdi 319: e8 00 00 00 00 call 31e <q_delete_mid+0x4b> 31e: 48 8d 7b f8 lea -0x8(%rbx),%rdi 322: e8 00 00 00 00 call 327 <q_delete_mid+0x54> 327: b8 01 00 00 00 mov $0x1,%eax 32c: 5b pop %rbx 32d: c3 ret 32e: b8 00 00 00 00 mov $0x0,%eax 333: c3 ret 334: b8 00 00 00 00 mov $0x0,%eax 339: eb f1 jmp 32c <q_delete_mid+0x59> ``` 結果上述的兩個版本編譯器編出來的組合語言竟然是一樣的，查看 `makefile` 發現編譯器優化等級設定在 `-O1`，如果禁用優化改成 `-O0` 編譯出來的組合語言才會有差 #### 使用 [perf](https://en.wikipedia.org/wiki/Perf_(Linux)) 確認上述猜測 - 參考 [Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial#%E8%83%8C%E6%99%AF%E7%9F%A5%E8%AD%98)，記得先參考[安裝](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial#%E5%AE%89%E8%A3%9D)章節將權限打開 - 雖然上面已經看到經過編譯器優化後的組合語言相同，可想而知效能一定一樣。 ```shell sudo sh -c " echo -1 > /proc/sys/kernel/perf_event_paranoid" ``` 定義一個測試案例 `trace-demid.cmd` ```shell option fail 0 option malloc 0 new ih RAND 500000 time dm time ``` 輸入命令 ```shell perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-demid.cmd ``` `perf stat` 可以測量單個程序運行時間內的性能係數 - `--repeat 5` 重複 5 次 - `-e` 後面接著 [PMU](https://en.wikipedia.org/wiki/Hardware_performance_counter) 的事件，可以用 `perf list` 查看所有事件結果如下 ``` Performance counter stats for './qtest -f traces/trace-demid.cmd' (5 runs): 1530,3333 cache-misses # 90.230 % of all cache refs ( +- 0.34% ) 1658,7721 cache-references ( +- 1.66% ) 16,8910,5300 instructions # 0.83 insn per cycle ( +- 0.01% ) 19,7202,0142 cycles ( +- 2.88% ) 0.5664 +- 0.0189 seconds time elapsed ( +- 3.34% ) ``` :::spoiler Iteration process 以 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) 舉例 ```graphviz digraph del_mid { node [shape=circle] rankdir=LR node1[label="1", rank=2] node2[label="3"] node3[label="4"] node4[label="7"] node5[label="1"] node6[label="2"] node7[label="6"] // backbone node1 -> node2 -> node3 -> node4 ->node5->node6->node7 head->node1 // mark p [shape=plaintext;label="p"] p->node7[constraint="false"] n [shape=plaintext;label="n"] n->node1[constraint="false"] } ``` ```graphviz digraph del_mid { node [shape=circle] rankdir=LR node1[label="1"] node2[label="3"] node3[label="4"] node4[label="7"] node5[label="1"] node6[label="2"] node7[label="6"] // backbone node1 -> node2 -> node3 -> node4 ->node5->node6->node7 head->node1 // mark p [shape=plaintext;label="p"] p->node6[constraint="false"] n [shape=plaintext;label="n"] n->node2[constraint="false"] } ``` ```graphviz digraph del_mid { node [shape=circle] rankdir=LR node1[label="1"] node2[label="3"] node3[label="4"] node4[label="7"] node5[label="1"] node6[label="2"] node7[label="6"] // backbone node1 -> node2 -> node3 -> node4 ->node5->node6->node7 head->node1 // mark p [shape=plaintext;label="p"] p->node5[constraint="false"] n [shape=plaintext;label="n"] n->node3[constraint="false"] } ``` ```graphviz digraph del_mid { node [shape=circle] rankdir=LR node1[label="1"] node2[label="3"] node3[label="4"] node4[label="7", color="red"] node5[label="1"] node6[label="2"] node7[label="6"] // backbone node1 -> node2 -> node3 -> node4 ->node5->node6->node7 head->node1 // mark p [shape=plaintext;label="p"] p->node4[constraint="false"] n [shape=plaintext;label="n"] n->node4[constraint="false", color=red] } ``` ::: :::spoiler Old version 利用快慢指標 ([Floyd's tortoise and hare](https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare)) 找中間點, 因為在本次作業中已經確保快慢指標 (或龜兔指標) 已經都在環中, 所以設定快指標移動速度為慢指標兩倍, 當快指標繞完一圈時慢指標指向中間點(有 `Head` 節點則差一個節點) ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head **indir; indir = &head; struct list_head *fast = head; while(!(fast->next == head || fast->next->next == head)) { indir = &(*indir)->next; fast = fast->next->next; } q_release_element(list_entry((*indir)->next, element_t, list)); (*indir)->next = (*indir)->next->next; return true; } ``` ``` cmd> dm Segmentation fault occurred. You dereferenced a NULL or invalid pointer Aborted (core dumped) ``` - 這裡如果直接把 `(*indir)->next` 直接 release 掉的話會造成 `(*indir)->next` 指向 `NULL` 這不是我們想要的, 這裡我先用 `list_del((*indir)->next)` 將 `(*indir)` 和 `(*indir)->next->next` linked 起來，在將原先的 `(*indir)->next` release 掉 ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head **indir; indir = &head; struct list_head *fast = head; while (fast->next!= head && fast->next->next != head) { indir = &(*indir)->next; fast = fast->next->next; } struct list_head* temp = (*indir)->next; list_del((*indir)->next); q_release_element(list_entry(temp, element_t, list)); return true; } ``` **Iteration Process** ```graphviz digraph del_mid { node [shape=box] rankdir=LR // backbone node1 -> node2 -> node3 -> node4 head->node1 // mark indir [shape=plaintext;label="indir"] indir->head fast [shape=plaintext;label="fast"] fast->node1 } ``` ```graphviz digraph del_mid { node [shape=box] rankdir=LR // backbone node1 -> node2 -> node3 -> node4 head->node1 // mark indir [shape=plaintext;label="indir"] indir->node1 fast [shape=plaintext;label="fast"] fast->node3 } ``` 以 [2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) 實際演算一次 ```graphviz digraph del_mid { node [shape=circle] rankdir=LR node1[label="1", rank=2] node2[label="3"] node3[label="4"] node4[label="7"] node5[label="1"] node6[label="2"] node7[label="6"] // backbone node1 -> node2 -> node3 -> node4 ->node5->node6->node7 head->node1 // mark indir [shape=plaintext;label="indir"] indir->head[constraint="false"] fast [shape=plaintext;label="fast"] fast->node1[constraint="false"] } ``` ```graphviz digraph del_mid { node [shape=circle] rankdir=LR node1[label="1"] node2[label="3"] node3[label="4"] node4[label="7"] node5[label="1"] node6[label="2"] node7[label="6"] // backbone node1 -> node2 -> node3 -> node4 ->node5->node6->node7 head->node1 // mark indir [shape=plaintext;label="indir"] indir->node1[constraint="false"] fast [shape=plaintext;label="fast"] fast->node3[constraint="false"] } ``` ```graphviz digraph del_mid { node [shape=circle] rankdir=LR node1[label="1"] node2[label="3"] node3[label="4"] node4[label="7"] node5[label="1"] node6[label="2"] node7[label="6"] // backbone node1 -> node2 -> node3 -> node4 ->node5->node6->node7 head->node1 // mark indir [shape=plaintext;label="indir"] indir->node2[constraint="false"] fast [shape=plaintext;label="fast"] fast->node5[constraint="false"] } ``` ```graphviz digraph del_mid { node [shape=circle] rankdir=LR node1[label="1"] node2[label="3"] node3[label="4"] node4[label="7", color="red"] node5[label="1"] node6[label="2"] node7[label="6"] // backbone node1 -> node2 -> node3 -> node4 ->node5->node6->node7 head->node1 // mark indir [shape=plaintext;label="indir"] indir->node3[constraint="false", color="red"] fast [shape=plaintext;label="fast"] fast->node7[constraint="false"] } ``` - remove `(*indir)->next` 節點 ::: ### q_delete_dup 首先思考使用 `list_for_each_entry_safe` 實作，根據描述 >list_for_each_entry_safe - Iterate over list entries and allow deletes 會走訪整個 list 的 entries (`typeof(entry)`) 並允許刪除當前的節點 ```c bool q_delete_dup(struct list_head *head) { if (!head || list_empty(head)) return false; element_t *c, *n; // current and next element bool is_dup = false; list_for_each_entry_safe (c, n, head, list) { // current node (iterator) is allowed to // be removed from the list. if (c->list.next != head && strcmp(c->value, n->value) == 0) // duplicate string detection { list_del(&c->list); // delete node q_release_element(c); is_dup = true; } else if (is_dup) { list_del(&c->list); q_release_element(c); is_dup = false; } } return true; } ``` 執行 `list_for_each_entry_safe` 可以走訪整個 list 但是需要注意在走訪完時 `n` 會指向 `head`，且 `head` 是無法透過 `container_of` 找到節點的，因為它沒有嵌入到結構體中，這時如果對 `n` 取 `contain_of` 會拿到 `NULL` 如果再做取值 `n->value` 會<s>報錯</s> 成為無效的記憶體操作。 > [invalid page fault](https://en.wikipedia.org/wiki/Page_fault) 故在第一個 `if` 條件使用 `c->list.next != head` 來判斷是否來到最後的節點 (雖然 `list_for_each_entry_safe` 本身就有做)，避免在 `strcmp(c->value, n->value) == 0` 時 `n->value` 對 `NULL` 指標取值。 :::warning TODO: 減少記憶體操作的數量 :notes: jserv ::: ### q_swap ```c void q_swap(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *n = head->next; while (n != head && n->next != head) { struct list_head *t = n; list_move(n, t->next); n = n->next; } } ``` 交換佇列中鄰近的節點，將兩個鄰近的節點中的第一個節點移動至以令一個當作 `head` 節點的開頭 (也就是說會放在另一個節點的 `next`)，移動節點可分為兩步驟(刪除以及插入)，對應到 `list_move` 中定義的兩步驟 `list_del` 以及 `list_add` ### q_reverse ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *n, *s, *t; list_for_each_safe (n, s, head) { t = n->next; n->next = n->prev; n->prev = t; } t = head->next; head->next = head->prev; head->prev = t; } ``` 一開始原本是考慮到沒有刪除節點的問題所以使用 `list_for_each` 來走訪 list ，但是在 reverse 的過程中的 `node` 會把 `next` 和 `prev` 做交換，會讓原本定義的巨集出現錯誤，導致無法順利走訪。改用 `list_for_each_safe` ```c #define list_for_each_safe(node, safe, head) \ for (node = (head)->next, safe = node->next; node != (head); \ node = safe, safe = node->next) ``` 在迭代過程中 `safe` 指標會始終維持在 `node` 的下一個節點(沒有 reverse 的)，使用 `node = safe` 以及 `safe = node->next` 確保迭代過程 `node` 不會往回走。 ### q_reverseK 此<s>函數</s> 函式需要將 list 中的 k 個節點進行 reverse，直覺來說會利用到上方已經實作完成的 `q_reverse`，為此在使用時符合 `q_reverse` 參數需求，傳入該 list 的 `head`，故使用 `list_cut_position` 對特定長度的 list 進行分割，並在分割下來的 list 頭部新增 `iter` 作為該 list 的 `head` 供 `q_reverse` 使用 :::warning 注意用語，參見 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)。上述 "reverse" 應有對應的漢語描述 :notes: jserv ::: ```c void q_reverseK(struct list_head *head, int k) { if (!head || list_empty(head)) return; struct list_head *n, *s, iter, *tmp_head = head; int i = 0; INIT_LIST_HEAD(&iter); list_for_each_safe (n, s, head) { i++; if (i == k) { list_cut_position(&iter, tmp_head, n); q_reverse(&iter); list_splice_init(&iter, tmp_head); i = 0; tmp_head = s->prev; } } } ``` - 參考 [25077667](https://hackmd.io/@25077667/lab0-2023#2023q1-Homework1-lab0)，及 [komark06](https://hackmd.io/@komark06/SyCUIEYpj) ### q_sort 實作 merge sort，先將環狀結構斷開後，傳入 `head->next` 進去 `merge_recur` **merge_two_list** - 結合兩個「已排序」的鏈結串列 ```c struct list_head *merge_two_list(struct list_head *left, struct list_head *right) { struct list_head head; struct list_head *h = &head; if (!left && !right) { return NULL; } while (left && right) { if (strcmp(list_entry(left, element_t, list)->value, list_entry(right, element_t, list)->value) < 0) { h->next = left; left = left->next; h = h->next; } else { h->next = right; right = right->next; h = h->next; } } // after merge, there are still one node still not connect yet if (left) { h->next = left; } else if (right) { h->next = right; } return head.next; } ``` :::warning TODO: 撰寫更精簡的程式碼，縮減分支 :notes: jserv ::: **merge_recur** - 利用快慢指標將 list 的中間節點找出來並遞迴處理 :::warning 避免使用含糊的「中點」，應有對應的定義及說明。 :notes: jserv ::: ```c struct list_head *merge_recur(struct list_head *head) { if (!head->next) return head; struct list_head *slow = head; // split list for (struct list_head *fast = head->next; fast && fast->next; fast = fast->next->next) { slow = slow->next; } struct list_head *mid = slow->next; // the start node of right part slow->next = NULL; struct list_head *left = merge_recur(head); struct list_head *right = merge_recur(mid); return merge_two_list(left, right); } ``` **q_sort** - 傳入 `head->next` 進行 merge sort 可以保留原本的 `head` ，在排序過後在進行 `prev` 以及 `circular` 的修補 ```c void q_sort(struct list_head *head) { if (!head || list_empty(head)) return; // disconnect the circular structure head->prev->next = NULL; head->next = merge_recur(head->next); // reconnect the list (prev and circular) struct list_head *c = head, *n = head->next; while (n) { n->prev = c; c = n; n = n->next; } c->next = head; head->prev = c; } ``` ### q_descend 此函數會將**右邊存在有嚴格大於的節點的節點**給移除 (remove) ```c int q_descend(struct list_head *head) { struct list_head *c = head->prev, *n = c->prev; while (n != head) { if (strcmp(list_entry(n, element_t, list)->value, list_entry(c, element_t, list)->value) < 0) { list_del(n); } else { c = n; } n = n->prev; } return q_size(head); } ``` 如果順著 list 方向進行走訪 (以 `next` 指標迭代)，無法確定迭代的過程中會不會遇到嚴格大於的節點(如果遇到則走放過的節點都要移除)，故這邊我以反方向進行迭代(以 `prev` 指標迭代)，找尋下一個節點值只要和當前節點做比較，若下一個節點小於當前節點的話則移除。執行測試案例的時候發現 `trace-06` 過不了，發現是 `descend` 後被消除的 block 沒有被清掉，一開始看到函式敘述用 `remove` 時以為不用刪除 > Remove every node which has a node with a strictly greater value anywhere to the right side of it 但它也沒有存到像 `q_remove` 系列的 `sp` 中，由 `q_test` 負責刪除，故修正在函式內進行記憶體釋放 ```c int q_descend(struct list_head *head) { if (!head) return 0; struct list_head *c = head->prev; element_t *c_ele = list_entry(c, element_t, list); while (c_ele->list.prev != head) { element_t *n_ele = list_entry(c_ele->list.prev, element_t, list); if (strcmp(n_ele->value, c_ele->value) < 0) { list_del(&n_ele->list); q_release_element(n_ele); } else { c_ele = n_ele; } } return q_size(head); } ``` ### q_merge 先看一下 `do_merge` 要我們做什麼 ```c if (current && exception_setup(true)) len = q_merge(&chain.head); exception_cancel(); ``` - 輸入 chain head 回傳長度且在 `do_merge` 中會負責把被 merge 掉的 queue 空間 `free` 掉，接著再檢查是否真的有按照 ascending order 來排序 ```c int q_merge(struct list_head *head) { if (!head) return 0; queue_contex_t *c_cont; queue_contex_t *n_cont; struct list_head *sorted = NULL; list_for_each_entry_safe (c_cont, n_cont, head, chain) { // iterate context c_cont->q->prev->next = NULL; c_cont->q->prev = NULL; sorted = merge_two_list(sorted, c_cont->q->next); INIT_LIST_HEAD(c_cont->q); // reconnect the lists which are moved and // merged to "sorted" list; } LIST_HEAD(tmp); struct list_head *t = &tmp; t->next = sorted; struct list_head *c = t; while (sorted) { sorted->prev = c; c = sorted; sorted = sorted->next; } c->next = t; t->prev = c; int size = q_size(t); // store size before splice to main queue list_splice(t, list_first_entry(head, queue_contex_t, chain)->q); return size; } ``` 實作過程中利用在 merge sort 已經寫好的 `merge_two_list` ，不過須注意的是這邊我的 `merge_two_list` 傳入值為兩個**沒有 `head` 的 list**，也就是每一個節點其對應到的 element 都有數值，且不是環狀 linked list ，實做過程將兩個已經 sorted 好的 list 傳入 function 並回傳將兩個 list merged 完成的 list 的第一個節點地址，此時可以把 merged 好的 list 交給主要的 context (迭代中的) 的 list head (其 element 沒有值的那個) 完成之後會有一個 merged 好的 list，接著將環狀的結構復原 (`prev`被各個佇列的 merge 打亂了，僅有 `next` 為正常順序) 最後把處理好的 list 透過 `list_splice` 交給主要 chain `head` 所屬的 `element` --- ## 研讀論文並改進 dudect - 較細節研讀筆記放在[另外的筆記](https://hackmd.io/@chiangkd/dudect-study) 此節根據〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉修正測試案例 `trace-17-complexity` 檢測程式碼不會常數執行時間的問題，在 `trace-17-complexity` 測試案例中會將 `option simulation` 打開，並執行 insert head (`ih`)、insert tail (`it`)、remove head (`rh`)、remove tail (`rt`) 指令，而在 `qtest.c` 中相對應的 `do_it`、`do_ih`、`do_remove` 都有對應 `simutlation` 開啟狀態下的行為。 ### 解釋 simulation 模式 >下述程式碼已在 [#127](https://github.com/sysprog21/lab0-c/commit/bdcfae37505e671c5ba028b8d95fe0e7e40b2afc) 更新首先查看 `do_ih` ```c if (simulation) { if (argc != 1) { report(1, "%s does not need arguments in simulation mode", argv[0]); return false; } bool ok = is_insert_head_const(); if (!ok) { report(1, "ERROR: Probably not constant time or wrong implementation"); return false; } report(1, "Probably constant time"); return ok; } ``` 在 `simulation` 下，對應到三種結果 - 不需要 argument - 執行測試，且 probably not constant time - 執行測試，且 probably constant time 是否為 constant time 由 `is_insert_head_const()` 函式回傳判斷， `is_##x##_const` 系列函式由前置處理器 [concatenation](https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html) 處理，其中 `insert_head`, `insert_tail`, `remove_head`, `remove_tail` 也都是由前置處理器處理。 :::warning 這技巧稱為 [X macro](https://en.wikipedia.org/wiki/X_Macro) :notes: jserv >Got it! Thanks ::: `constant.c` 中的 `measure` 函式負責判斷 `ih`、`it`、`rh`、`rt` 是否有正常運作 (透過 size 有沒有隨著 insert 以及 remove 正常的變動) `fixture.c` 中的 `report` 函式則負責測量是否為 constant time ```c /* Definitely not constant time */ if (max_t > t_threshold_bananas) return false; /* Probably not constant time. */ if (max_t > t_threshold_moderate) return false; /* For the moment, maybe constant time. */ return true; ``` 此處流程可以參照 [preparaz/dudect](https://github.com/oreparaz/dudect)，中的 **Checking your code for constant time** 節 >`dudect` is distributed as a single-file library for easy building. Steps: >- Copy `dudect.h` to your include directories >- Add #include "`dudect.h`" from your source files. >- See [this minimal example](https://github.com/oreparaz/dudect/blob/master/examples/simple/example.c) for a fully contained example. You'll need to write the following functions: > - `do_one_computation()`, > - `prepare_inputs()` and > - call `dudect_main()` from your main function ### Student's t-distribution 及程式實作原理實作放在 `ttest.c` 相關函式，按照公式計算 `t` 值 $$ t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{s^2_1}{N_1} + \frac{s^2_2}{N_2}}} $$ 其中 `t` 值越小代表兩組分佈越接近，注意這裡的 $\bar{X_i}$ 指的是 [sample mean](https://en.wikipedia.org/wiki/Sample_mean_and_covariance) 首先在進入定義全域變數 `t_constext *t`，結構體定義為 ```c typedef struct { double mean[2]; double m2[2]; double n[2]; } t_context_t; ``` 在每一次測試時 (預設測試 10 次 (`TEST_TRIES=10`))，首先呼叫 `init_once()`，在 `init_once()` 中會將 `t` 的各個元素初始化。接著根據不同的 `mode` (不同的 case 有不同的 mode number) ，進入 `doit` ，在 `prepare_input` 之後進入 `measure` 函式， `measure` 函式根據 `q_size` 判斷 `ih`, `it`, `rh`, `rt` 等操作有沒有順利進行，也計算函式執行時間，以 `insert_head` 為例: ```c before_ticks[i] = cpucycles(); dut_insert_head(s, 1); after_ticks[i] = cpucycles(); ``` 函式若正常執行回傳 `true` 給 `ret`，且更新了 `before_ticks` 以及 `after_ticks` 交給 `differentiate` 進行計算 `exec_time[i] = after_ticks[i] - before_ticks[i]` ，其中 `i` 為每次 `test` 進行的 measurement 次數，預設為 150 次。接著將計算出的 `exec_time` 及 `classes` 送入 `updata_statistics` ，函式內透過 `t_push` 進行 t-test ，`t_push` 需要的參數包含 - `t_context` 本體 `t` - 計算出的 `difference` 也就是對應的 `exec_times[i]` - 對應的 `classes[i]` 在 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 原始碼中有提到可以參考《The Art of Computer Programming, Volume 2 : Seminumerical Algorithms》 (待研究)，看起來是透過取新的 execution time 與當前平均值的差為變化量 (`delta`) 而新的平均值就會是舊平均值加上變化量的平均值 (`delta/n`)，可以避免每次都將所有數值相加取平均的過程，而 `m2` 為變異數尚未平均的值，在後續 `t_compute` 會使用到，每次的 `m2` 更新為舊 `m2` 加上 `delta` 乘上這次的 execution time 與更新過後的平均值的差。在 `ttest.c` 中 ```c void t_push(t_context_t *ctx, double x, uint8_t class) { assert(class == 0 || class == 1); ctx->n[class]++; double delta = x - ctx->mean[class]; ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class]; ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]); } ``` 之後進入 `report` 函式透過 `t_compute` 及取絕對值的 `fabs` 計算 `max_t`， `max_t` 數值就會根據 `t_threshold_xx` 的值來判斷程式是否 constant time，這裡程式的實作如同上述給定的公式 $$ t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{s^2_1}{N_1} + \frac{s^2_2}{N_2}}} $$ 再回傳 `t` 值之後會在透過 `fabs` 取絕對值。 ### 修改以達成 constant time 當前 `lab0-c` 並未實作 percentile 功能，也就是沒有將測量誤差給 crop 掉，將 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中的 percentile 引入後即可順利通過 `trace-17-complexity` [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中的結構體定義和 `lab0-c` 有一些不一樣，原專案中使用 `dudect_state_t` 將 `ttest_ctx_t` (等效 `lab0-c` 中的 `t_context_t`) 及執行時間、輸入資料、等必要資訊定義在一起，但在 `lab0-c` 都是拆開的，在這邊引入 `percentile` 至 `t_context_t` 中 ```diff typedef struct { double mean[2]; double m2[2]; double n[2]; + int64_t *percentiles; } t_context_t; ``` 詳細改動在 [commit](https://github.com/chiangkd/lab0-c/commit/d014538e300e54d5e21e586f23e3e10a561269ee) 中。 --- ## 研讀 list_sort.c 並引入專案 - 研讀筆記放在[這裡](https://hackmd.io/erWlfVMfQqyUe9JVbOLlBA?view#%E7%A0%94%E8%AE%80-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC%E7%9A%84-list_sortc) 將 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 以及 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 引入專案，並新增 `makefile` 的 dependency 以及把無關的 include header 移除 ```diff OBJS := qtest.o report.o console.o harness.o queue.o \ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \ shannon_entropy.o \ - linenoise.o web.o + linenoise.o web.o list_sort.o ``` `list_sort.h` ```diff /* SPDX-License-Identifier: GPL-2.0 */ #ifndef _LINUX_LIST_SORT_H #define _LINUX_LIST_SORT_H -#include <linux/types.h> +#include "stdint.h" +#include "list.h" -struct list_head; typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *); __attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp); #endif ``` ```diff static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head, struct list_head *a, struct list_head *b) { struct list_head *tail = head; - u8 count = 0; + uint8_t count = 0; ... } ``` 編譯後發現 `likely` 以及 `unlikely` 沒有定義，參考 [linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h)，其中的 `__builtin_expect()` 是 gcc 的 built-in function，用來將 branch 的相關資訊提供給 compiler，讓其對程式碼改變分支的順序 - 參考 [6.59 Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) ```c # define likely(x) __builtin_expect(!!(x), 1) # define unlikely(x) __builtin_expect(!!(x), 0) ``` - 參考連結 [Linux Kernel 慢慢學: likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/) 在 `list_sort` 的 prototype 中需要三個參數，`priv`, `head`，以及 `cmp` - `head` 為我們要輸入的 queue 的 `head` - `cmp` 為 compare function，作為函式指標傳入，根據註解 >The comparison function @cmp must return > 0 if @a should sort after @b (“@a > @b” if you want an ascending sort), and <= 0 if @a should sort before @b or their original order should be preserved. It is always called with the element that came first in the input in @a, and list_sort is a stable sort, so it is not necessary to distinguish the @a < @b and @a == @b cases. 1. `cmp` return > 0 (a 排在 b 的後面) 2. `cmp` return <=0 (a 排在 b 的前面或保留原本排列) 3. `list_sort` 是一個 [stable sort](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability)，故不用區分小於 0 或等於 0 不確定這邊的 `priv` 是要幹麻的，不過根據宣告 `priv` 可以為 `NULL` ```c __attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp) ``` 參考 `do_sort` 新增 `do_lsort` 代表 linux 核心原始程式碼的 `list_sort` 並定義 `cmp` ```c int cmp(void *priv, const struct list_head *a, const struct list_head *b) { element_t *a_ele = list_entry(a, element_t, list); // get mother element element_t *b_ele = list_entry(b, element_t, list); return strcmp(a_ele->value, b_ele->value) < 0 ? 0 : 1; } bool do_lsort(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } int cnt = 0; if (!current || !current->q) report(3, "Warning: Calling sort on null queue"); else cnt = q_size(current->q); error_check(); if (cnt < 2) report(3, "Warning: Calling sort on single node"); error_check(); set_noallocate_mode(true); if (current && exception_setup(true)) list_sort(NULL, current->q, cmp); exception_cancel(); set_noallocate_mode(false); bool ok = true; if (current && current->size) { for (struct list_head *cur_l = current->q->next; cur_l != current->q && --cnt; cur_l = cur_l->next) { /* Ensure each element in ascending order */ /* FIXME: add an option to specify sorting order */ element_t *item, *next_item; item = list_entry(cur_l, element_t, list); next_item = list_entry(cur_l->next, element_t, list); if (strcmp(item->value, next_item->value) > 0) { report(1, "ERROR: Not sorted in ascending order"); ok = false; break; } } } q_show(3); return ok && !error_check(); } ``` **提供新命令** `lsort` 在 `qtest.c` 的 `console_init()` 中新增命令 ```c ADD_COMMAND(lsort, "Sort queue in ascending order provided by linux kernel", ""); ``` 結果呈現 ``` cmd> new l = [] cmd> ih RAND 10 l = [xajlhbj zblfv veqfmhw kuwzmcl qzzsyenvi xfsgs bocazny saskszhgd xqjrd igiecysjj] cmd> lsort l = [bocazny igiecysjj kuwzmcl qzzsyenvi saskszhgd veqfmhw xajlhbj xfsgs xqjrd zblfv] cmd> shuffle l = [bocazny kuwzmcl xfsgs igiecysjj veqfmhw saskszhgd zblfv qzzsyenvi xajlhbj xqjrd] cmd> sort l = [bocazny igiecysjj kuwzmcl qzzsyenvi saskszhgd veqfmhw xajlhbj xfsgs xqjrd zblfv] ``` `git commit` 的時候會被擋下來 ```shell list_sort.c:14:23: style: Variable 'head' is not assigned a value. [unassignedVariable] struct list_head *head, **tail = &head; ^ ``` 考慮到不要修正 `list_sort.c` 的原始碼，用 `cppcheck-suppress` 跨過去 ```c // cppcheck-suppress unassignedVariable struct list_head *head, **tail = &head; ``` ### 效能比較使用 `perf` 進行效能比較，參考 [Linux 效能分析工具: Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) ```shell perf stat --repeat 5 -e instructions,cycles ./qtest -f traces/trace-sort.cmd ``` 定義測資 ```shell option fail 0 option malloc 0 new ih RAND 500000 time <sort> time ``` - `<sort>` 可以為原先 `qtest.c` 中撰寫的 `do_sort` 或是引入的 `do_lsort`，透過 `time` 命令獲取 `sort` 執行的時間，設定 `--repeat 5` 重複五次，並透過 `perf` 拿到 `instructions` 以及 `cycles` 的數據 **自行撰寫的 `q_sort`** | **q_sort** | time | | ---------- | ----- | | 1 | 0.487 | | 2 | 0.477 | | 3 | 0.488 | | 4 | 0.486 | | 5 | 0.529 | | Instructions | Cycles | | ------------ | ------------ | | 20,9111,6747 | 36,2842,8338 | **list_sort** | **q_sort** | time | | ---------- | ----- | | 1 | 0.411 | | 2 | 0.417 | | 3 | 0.423 | | 4 | 0.501 | | 5 | 0.460 | | Instructions | Cycles | | ------------ | ------------ | | 21,4157,1467 | 34,1147,9158 | 雖然每次執行這個測試案例時，Instructions 和 Cycles 的數量會些微變動，但整理來看 - Linux kernel 的 `list_sort` 指令較多，Cycles 較少 --- ## 在 qtest 提供新的命令 shuffle - [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) ```c void q_shuffle(struct list_head *head) { if (!head || list_empty(head)) return; int size = q_size(head); // shuffle for (int i = 0; i < size;) { // not iterate i , iterate size struct list_head *start = head->next; int rand_idx = rand() % size; // random number in range 0~ (size-1) for (int j = 0; j < rand_idx; j++) { start = start->next; } list_del(start); list_add_tail(start, head); size--; } return; } ``` 選取一個隨機數，將該位置元素取出後放到尾端，舉例來說 | 隨機範圍 | 隨機數 | 原始數據 | 結果 | | -------- | ------ | -------- | ---- | | | | 12345 | | | 1~5 | 4 | 1235 | 4 | | 1~4 | 3 | 125 | 34 | | 1~3 | 1 | 25 | 134 | | 1~2 | 1 | 5 | 2134 | ### 在命令直譯器中新增命令 shuffle 在 `qtest.c` 中的 `console_init()` 新增 `shuffle` 指令 ```c ADD_COMMAND(shuffle, "Shuffle queue", ""); ``` 查看其巨集定義 ```c #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) ``` 此巨集會將 `cmd` 命令的行為去透過巨集展開 `do_##cmd` 去呼叫對應 handler ，如其他命令 `new` 會去呼叫 `do_new` 函式，故在此定義 `do_shuffle` 函式來 handle `shuffle` 命令 ```c void q_shuffle(struct list_head *head); static bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no argu,emts", argv[0]); //return function error return false; } if (!current || !current->q) report(3, "Warning: Calling shuffle on null queue"); error_check(); if (exception_setup(true)) q_shuffle(current->q); exception_cancel(); set_noallocate_mode(false); q_show(3); return !error_check(); } ``` 參考其他函式 handler 的寫法，有些函式內有定義 `bool ok`，有些則無，觀察到 `ok` 都用在佇列長度有更改或者需要判斷佇列是否為空的情形，所以 `reverse`，`swap` 中不需要 `ok` 來處理佇列長度改變，且對應的 `do_reverse` 以及 `do_swap` 中都有相應的 `if(!head)` 來處理空佇列的問題，綜上所述 `do_shuffle` 不需要有 `bool ok` 定義。 ```shell [!] You are not allowed to change the header file queue.h or list.h ``` - 無法將 `q_shuffle` 宣告加在 `queue.h` 所以就放在 `do_shuffle` 的上面 ```shell cmd> new l = [] cmd> it a l = [a] cmd> it b l = [a b] cmd> it c l = [a b c] cmd> it d l = [a b c d] cmd> it e l = [a b c d e] cmd> shuffle l = [a d b c e] cmd> shuffle l = [c b d e a] cmd> shuffle l = [c e a b d] ``` --- ## 運用 Valgrind 排除 qtest 實作的記憶體錯誤首先嘗試用 `valgrind` 跑跑看 `trace-01-ops.cmd` 測資 ```shell valgrind ./qtest -f ./traces/trace-01-ops.cmd ``` ```shell ==10230== 32 bytes in 1 blocks are still reachable in loss record 1 of 2 ==10230== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==10230== by 0x10CE33: do_new (qtest.c:147) ==10230== by 0x10E099: interpret_cmda (console.c:181) ==10230== by 0x10E64E: interpret_cmd (console.c:201) ==10230== by 0x10EA4F: cmd_select (console.c:610) ==10230== by 0x10F33B: run_console (console.c:705) ==10230== by 0x10D48B: main (qtest.c:1307) ==10230== ==10230== 56 bytes in 1 blocks are still reachable in loss record 2 of 2 ==10230== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==10230== by 0x10F3AF: test_malloc (harness.c:133) ==10230== by 0x10F7B4: q_new (queue.c:17) ==10230== by 0x10CE6C: do_new (qtest.c:151) ==10230== by 0x10E099: interpret_cmda (console.c:181) ==10230== by 0x10E64E: interpret_cmd (console.c:201) ==10230== by 0x10EA4F: cmd_select (console.c:610) ==10230== by 0x10F33B: run_console (console.c:705) ==10230== by 0x10D48B: main (qtest.c:1307) ``` 依據[網站](https://valgrind.org/docs/manual/faq.html#faq.deflost)及作業講解敘述，Valgrind 有 5 種 memory leak - definitely lost: 真的 memory leak - indirectly lost: 間接的 memory leak，structure 本身發生 memory leak，而內部的 member 如果是 allocate 的出來的，一樣會 memory leak，但是只要修好前面的問題，後面的問題也會跟著修復。 - possibly lost: allocate 一塊記憶體，並且放到指標 ptr，但事後又改變 ptr 指到這塊記憶體的中間 - still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數，即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。這裡發生的 still reachable 在 `do_new` 及 `test_malloc` 中，但是如果直接執行，`qtest` 且逐行輸入命令不會有這個問題。沒什麼頭緒，參考 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-lab0#Valgrind-%E8%88%87-Address-Sanitizer-%E8%A8%98%E6%86%B6%E9%AB%94%E6%AA%A2%E6%9F%A5)，上述問題已在 [#121](https://github.com/sysprog21/lab0-c/commit/c7d31497c5845bc0af308bf4601e7636c18f0153), [#122](https://github.com/sysprog21/lab0-c/commit/9dcf3ed44617b2d530c4365dbc60c4437e38e622) 被修正 :::warning TODO: 搞懂別人做了什麼 ::: ## 透過 Massif 視覺化 "simulation" 過程中的記憶體使用量選用 `trace-17-complexity.cmd` 先透過 Valgrind 產生 massif 檔案 ``` valgrind --tool=massif ./qtest -f traces/trace-eg.cmd ``` 再使用 `massif-visualizer` 查看 ``` massif-visualizer ./massif.out.<number> ``` ![](https://i.imgur.com/qL8qQOq.png) - 這邊參考 [alanjiang85](https://hackmd.io/@alanjian85/lab0-2023#%E9%80%8F%E9%81%8E-Massif-%E5%88%86%E6%9E%90%E8%A8%98%E6%86%B6%E9%AB%94%E4%BD%BF%E7%94%A8%E9%87%8F) 的說明改用 `trace-eg.cmd` 進行分析 - >alanjiang85: 要注意的是，挑選適當的測試資料時要避免效能類型的測試，因為以 Valgrind 執行測試程式會比較慢，容易導致出現超過時間限制的狀況。 ## Reference :::warning 參考資料不是讓你發表致謝詞的地方 :notes: jserv > Got it, Thanks! ::: - [komark06 PR#111](https://github.com/sysprog21/lab0-c/commit/ae7c2985b583126dd62ae6378941a93b2f73785f) - [ISO/IEC 9899:1999](https://zh.wikipedia.org/zh-tw/C99) - [3.11 Options That Control Optimization](https://gcc.gnu.org/onlinedocs/gcc-12.2.0/gcc/Optimize-Options.html#Optimize-Options) - [學習 Shell Scripts](https://linux.vbird.org/linux_basic/centos7/0340bashshell-scripts.php) - [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor?type=view) - [ANSI escape code](https://en.wikipedia.org/wiki/ANSI_escape_code)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.