2024q1 Homework1 (lab0)

# 2024q1 Homework1 (lab0) contributed by < [`ssheep773`](https://github.com/ssheep773/lab0-c) > ### Reviewed by `SuNsHiNe-75` <s> - 請把完整程式碼移除，如要討論才將要討論之部分「重點列出」。 - 注意標點符號的使用，有些地方都沒有「句號」。 - 進度太慢。 - 可善用 Valgrind 工具來追蹤記憶體使用狀況。 </s> > 你的洞見呢？與其談「心法」，不如設想「如果我是你」，我會怎麼做，示範一次給同學看，而且檢討自己哪裡沒做好，從而呼應原本學員的不足處。 > 清楚標示學員的 git commits 和敘述的不足處，予以檢討。 > [軟體工程師要學會說故事](https://ruddyblog.wordpress.com/2016/06/18/)，本作業要求學員從良性詳盡的批評開始。繼續檢討！ > :notes: jserv ### Reviewed by `stevendd543` * q_ascend 中按照你的程式邏輯，是從左向右尋找並檢查，所花的複雜度高達 $O(n^2)$ ，可以嘗試換方向思考從右邊開始處理，可讓複雜度降到 $O(n)$。 > 感謝你的建議，我已於筆記新增修改後程式的開發過程 > [commit 98a4c46](https://github.com/ssheep773/lab0-c/commit/98a4c46988a2c9ae281477a82df5ccc3b382e118) ### Reviewed by `st10740` * `q_swap` 中交換兩兩節點位置的方法可以使用 `list.h` 提供的 `list_move` 方法取代 `list_del_init` 和 `list_add`，可以達到一樣的效果且更簡潔。 > 感謝建議，已修改成更精簡的程式 > [commit 98a4c46](https://github.com/ssheep773/lab0-c/commit/98a4c46988a2c9ae281477a82df5ccc3b382e118) * 有些 commit 未利用 commit messages 說明該次變更的內容, 原因和做法，可以將其補上方便他人理解程式碼的變更。 ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 $ 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): 32 On-line CPU(s) list: 0-31 Vendor ID: GenuineIntel Model name: 13th Gen Intel(R) Core(TM) i9-13900 CPU family: 6 Model: 183 Thread(s) per core: 2 Core(s) per socket: 24 Socket(s): 1 Stepping: 1 CPU max MHz: 5600.0000 CPU min MHz: 800.0000 BogoMIPS: 3993.60 Virtualization features: Virtualization: VT-x Caches (sum of all): L1d: 896 KiB (24 instances) L1i: 1.3 MiB (24 instances) L2: 32 MiB (12 instances) L3: 36 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-31 ``` ## 指定的佇列操作 ### `q_new` 使用 `list.h` 中的 `INIT_LIST_HEAD` 來初始化 `struct list_head` ```c struct list_head *q_new() { struct list_head *new_head = malloc(sizeof(struct list_head)); if (!new_head) return NULL; INIT_LIST_HEAD(new_head); return new_head; } ``` ### `q_free` 使用 `list.h` 中的 `list_for_each_entry_safe(entry, safe, head, member)` 走訪每個節點。在走訪的過程中，可以對 `entry` 作任意操作，且不影響後續節點的走訪，利用這個特性逐個節點刪除。  目前的例子中則是透過 `element_t` 中的`struct list_head list` ```c void q_free(struct list_head *head) { if (!head) return; element_t *current, *next; list_for_each_entry_safe (current, next, head, list) { q_release_element(current); } free(head); } ``` ### `q_insert_head`  * 使用`list.h` 中的 `list_add()` 函式，將新增的節點添加在佇列的開頭 * 使用 `strdup()` 可以動態配置字串的記憶體空間，沒有使用 `strncpy()` 的原因是需要另外計算字串長度 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *new = malloc(sizeof(element_t)); if (!new) return false; new->value = strdup(s); if (!new->value) { free(new); return false; } list_add(&new->list, head); return true; } ``` ### `q_insert_tail` 作法與 `q_insert_head()` 差異在於節點插入的位置不同，使用 `list_add_tail()` 函式將節點新增在尾端。 [commit](https://github.com/ssheep773/lab0-c/commit/a25d6fd095bb2a3a5e4daf0d0118e4d050d07685) ```diff - list_add(&new->list, head); + list_add_tail(&new->list, head); ```  ### `q_remove_head` 使用到 `list.h` 中的函式 * `list_first_entry()` 回傳 head 的第一個節點 * `list_del()` 雖然名稱有 del 但並沒有將節點刪除，而是將節點 node 從 linked list 上 **remove**，成為單獨的節點 ```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_node = list_first_entry(head, element_t, list); list_del(&rm_node->list); if (sp != NULL) { strncpy(sp, rm_node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return rm_node; } ``` ### `q_remove_tail` 作法與 `q_remove_head` 差異在於移除節點的位置不同，使用`list_last_entry()` 函式獲取鏈結串列的尾端節點 ```diff - element_t *rm_node = list_first_entry(head, element_t, list); + element_t *rm_node = list_last_entry(head, element_t, list); ``` ### `q_delete_mid` 使用 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C) 中提到的快慢指標，找到中間的節點並刪除 ```c bool q_delete_mid(struct list_head *head) { if (!head || !head->next) return false; struct list_head *slow = head->next; for (struct list_head *fast = head->next; fast != head && fast->next != head; fast = fast->next->next) { slow = slow->next; } list_del(slow); q_release_element(list_entry(slow, element_t, list)); return true; } ``` ### `q_delete_dup` 參考 [Risheng](https://hackmd.io/kZtEa_LdSGKVQGg8jczrLQ?view#q_delete_dup) 進行實作函式假設： `*head` 是排序好的鏈結串列變數說明： `cur` : 指向當前節點的指標 `next` : 指向 `cur` 下一個節點的指標 `flag` : 表示是否發生資料相同的情況因為 `head` 是排序好的串列使用，所以加入 `!strcmp(cur_entry->value, nxt_entry->value)` 作為迴圈中止的條件  :::danger 減少非必要的項目縮排 (即 `* `)，使用清晰、明確，且流暢的漢語書寫。 > 好的老師 ::: ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head || list_empty(head) || list_is_singular(head)) return false; struct list_head *cur = head->next, *next = cur->next; bool flag = false; while (cur != head && next != head) { element_t *cur_entry = list_entry(cur, element_t, list); element_t *nxt_entry = list_entry(next, element_t, list); while (next != head && !strcmp(cur_entry->value, nxt_entry->value)) { list_del(next); q_release_element(nxt_entry); next = cur->next; nxt_entry = list_entry(next, element_t, list); flag = true; } if (flag) { list_del(cur); q_release_element(cur_entry); flag = false; } cur = next; next = next->next; } return true; } ``` ### `q_swap` :::danger 避免非必要的項目縮排 (即 `* `, `- ` 或數字)，以清晰、明確，且流暢的漢語書寫。授課教師在大學教書十餘年，見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。為此，要求學員書寫開發紀錄，並隨時做好「當主管問起，就能清晰解釋自己的投入狀況」，是強調讓學員「翻身」的本課程所在意的事。濫用條列 (或說 bullet) 來展現，乍看很清爽，但在面試的場合中，就很難用流暢的話語說明。反之，若平日已有這方面的練習，則面試過程中，才可充分展現自己專業之處。 ::: 建立兩個指標 `first` 和 `second` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="A"] e2 [label="B"] e3 [label="C"] e4 [label="D"] e5 [label="..."] first [shape=plaintext;label="first"] second [shape=plaintext;label="second"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 first -> e1 [color=green] second -> e2 [color=blue] } ``` 使用 `list_del_init` 將 `first` 指向的節點從 `linked list` 取出 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="A"] e2 [label="B"] e3 [label="C"] e4 [label="D"] e5 [label="..."] first [shape=plaintext;label="first"] second [shape=plaintext;label="second"] // next 方向 head -> e2 // e1 -> e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> head // pointer 初始化 first -> e1 [color=green] second -> e2 [color=blue] } ``` 使用 `list_add(first, second)` 將 `first` 指向節點加到 `second` 節點指向的下一個節點位置，達到兩節點交換位置 ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="A"] e2 [label="B"] e3 [label="C"] e4 [label="D"] e5 [label="..."] first [shape=plaintext;label="first"] second [shape=plaintext;label="second"] // next 方向 head -> e2 e1 -> e3 e2 -> e1 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 e1 -> e2 e2 -> head // pointer 初始化 first -> e1 [color=green] second -> e2 [color=blue] } ``` `first` 指向 node C 結束這次的迴圈 ```c void q_swap(struct list_head *head) { if (!head) return; struct list_head *first = head->next; while (first != head && first->next != head) { struct list_head *second = first->next; list_del_init(first); list_add(first, second); first = first->next; } } ``` 經由 `st10740` 的建議我再次查看 `list_del_init` 、`list_add` 、 `list_move` 這三個函式，我發現 `list_move` 的操作跟 `list_del_init` 加 `list_add` 的操作相比，只是少了過程中移除 `node` 後的節點初始化，而在 `swap` 的過程中我們其實不需要將移除的節點初始化，因為我們馬上會在後續的 `list_add` 為其分派指標位置 ```diff - list_del_init(first); - list_add(first, second); + list_move(first, second) ``` ### `q_reverse` 使用 `list_for_each_safe` 走訪原始的鏈結串列，並使用 `list_move` 將節點移至串列的開頭，結束後即可得到反轉的鏈結串列 ```c void q_reverse(struct list_head *head) { if (!head) return; struct list_head *cur, *safe; list_for_each_safe (cur, safe, head) { list_move(cur, head); } } ``` ### `q_reverseK` `cut` : 指向未完成反轉的串列 `count` ：紀錄訪問節點個數每當訪問 K 個節點，就將那 K 個節點透過 `list_cut_position(&tmp, cut, node)` 切出來放到 `tmp` ，並透過 `q_reverse()` 反轉，使用 `list_splice(&tmp, cut)` 把 `tmp` 接回 `cut` ，最後更新 `cut` 指向未完成反轉的串列 ```c void q_reverseK(struct list_head *head, int k) { if (!head || list_empty(head)) return; struct list_head *node, *safe, *cut = head; LIST_HEAD(tmp); int count = 0; list_for_each_safe (node, safe, head) { count++; if (count == k) { list_cut_position(&tmp, cut, node); q_reverse(&tmp); count = 0; list_splice(&tmp, cut); cut = safe->prev; } } } ``` ### `q_merge_two` 參考 [王彥傑](https://github.com/yanjiew1/lab0-c/commit/9c894d366bf99f0a8f92846397c90be5d9b36805) 同學進行實作，發現在決定排序的程式碼可進行優化透過真值表說明 `descend` 與 `cmp <= 0` 的關係是**互斥或 ( XOR )** `descend` ：決定串列是否遞減 `cmp <= 0` ：表示 L1 數值較小 `list_move_tail()` : 將節點新增到串列中 | descend | cmp <= 0 | list_move_tail() | | -------- | -------- | -------- | | True | True | **L2** | | True | False | **L1** | | False | True | **L1** | | False | False | **L2** | ```diff static int q_merge_two(struct list_head *L1, struct list_head *L2, bool descend) { if (!L1 || !L2) return 0; int count = 0; LIST_HEAD(tmp); while (!list_empty(L1) && !list_empty(L2)) { element_t *L1_entry = list_first_entry(L1, element_t, list); element_t *L2_entry = list_first_entry(L2, element_t, list); int cmp = strcmp(L1_entry->value, L2_entry->value); - if (descend) - cmp = -cmp; - if (cmp <= 0) - list_move_tail(&L1_entry->list, &tmp); + if (descend ^ cmp <= 0)) + list_move_tail(&L1_entry->list, &tmp); else list_move_tail(&L2_entry->list, &tmp); count++; } count += q_size(L1) + q_size(L2); list_splice(&tmp, L1); list_splice_tail_init(L2, L1); return count; } ``` ### `q_sort` 參考 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_sort) 同學進行實作，同時改成使用快慢指標來尋找中間節點 :::danger 你如何確認目前的測試方式/資料已涵蓋排序演算法的最差狀況？ ::: ```diff void q_sort(struct list_head *head, bool descend) { if (!head || list_empty(head) || list_is_singular(head)) return; /* Find middle point */ - struct list_head *mid, *left, *right; - left = right = head; - do { - left = left->next; - right = right->prev; - } while (left != right && left->next != right); - mid = left; + struct list_head *slow, *fast, *mid; + slow = fast = head; + do { + slow = slow->next; + fast = fast->next->next; + } while (fast != head && fast->next != head); mid = slow; LIST_HEAD(second); list_cut_position(&second, mid, head->prev); /* Conquer */ q_sort(head, descend); q_sort(&second, descend); /* Merge */ q_merge_two(head, &second, descend); } ``` 若要實作分治法（Divide and conquer）則需要尋找串列的中間節點，我首先想到可以使用 `q_delete_mid` 中找中點的方法，然而在`q_sort` 上卻會出錯 ```c struct list_head *slow = head->next; for (struct list_head *fast = head->next; fast != head && fast->next != head; fast = fast->next->next) { slow = slow->next; } ``` 實作下列的修改後雖然可以執行，但是 `mid` 的數值都是等於串列的第一個節點，由此推斷在原先的迴圈結束後 `slow` 會等於 `head` ```diff - mid = slow; + mid = slow->next; ``` 修改初始值 `*fast = head->next->next` ，則可以成功執行，但其中的緣由還在釐清當中 ```diff struct list_head *slow = head->next; - for (struct list_head *fast = head->next; + for (struct list_head *fast = head->next->next; fast != head && fast->next != head; fast = fast->next->next) { slow = slow->next; } ``` ### `q_ascend` / `q_descend` `q_ascend` 和 `q_descend` 使用相同的方法，差異只在其中 `strcmp()` 比較節點資訊的是大於還是小於這裡以 `q_descend` 作範例說明 :::danger 避免非必要的項目縮排 (即 `* `, `- ` 或數字)，以清晰、明確，且流暢的漢語書寫。授課教師在大學教書十餘年，見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。為此，要求學員書寫開發紀錄，並隨時做好「當主管問起，就能清晰解釋自己的投入狀況」，是強調讓學員「翻身」的本課程所在意的事。濫用條列 (或說 bullet) 來展現，乍看很清爽，但在面試的場合中，就很難用流暢的話語說明。反之，若平日已有這方面的練習，則面試過程中，才可充分展現自己專業之處。 ::: 我們會走訪串列的每個節點，並且同時檢查它右邊節點是否大於目前的節點，若成立則表示目前的節點需要刪除，才能滿足串列是遞減的，並使用 `flag` 紀錄目前節點需要刪除，在後續的程式碼中刪除此節點。 ```c int q_ascend(struct list_head *head) { if (!head) return 0; struct list_head *cur = head->next; while (cur != head && cur->next != head) { struct list_head *nxt = cur->next; element_t *cur_entry = list_entry(cur, element_t, list); bool flag = false; while (nxt != head) { element_t *nxt_entry = list_entry(nxt, element_t, list); if (strcmp(cur_entry->value, nxt_entry->value) > 0) { flag = true; break; } nxt = nxt->next; } struct list_head *tmp = cur->next; if (flag) { list_del(cur); q_release_element(cur_entry); } cur = tmp; } return q_size(head); } ``` 開發紀錄：原先沒有使用 `tmp` 先儲存 `cur->next` ，造成讀取到遭刪除的 `cur` ```diff + struct list_head *tmp = cur->next; if (flag) { list_del(cur); q_release_element(cur_entry); } - cur = cur->next; + cur = tmp; ``` 在除錯過程中發現，因為編譯器會執行程式的最佳化，使程式的執行不是如程式碼一樣線性的執行，所以我在除錯過程中，有先關閉編譯器最佳化 ```diff /* Makefile */ - CFLAGS = -O1 -g -Wall -Werror -Idudect -I. + CFLAGS = -g -Wall -Werror -Idudect -I. ``` 經由 `stevendd543` 的建議，我將複雜度降到 $O(n)$ ，我首先使用 `cur` 與 `next` 指向目前節點與目前節點的前一個節點，因為我們要倒著走訪整個鏈結串列，在走訪的過程中我們會比較目前的節點與前一個節點的值，若目前的節點較大，等於是說在串列中有一個節點比它後面的節點小，這樣就違反遞增的條件需要刪除，而若是符合遞增條件，則將會往下一個節點走訪。原本的作法的複雜度會是 $O(n^2)$ ，因為每個節點的走訪都是獨立的，每次都需要重新走訪所有目前節點的所有右邊的節點，等於是我們重複走訪最後一個節點 n-1 次而目前方法則是用 `cur` 紀錄目前值最大節點，因為若是節點符合條件，則表示他是目前最大的節點，透過走訪刪除不符合的節點或是更新目前的最大節點，來達到嚴格遞減的串列 ```c int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head) return 0; struct list_head *cur = head->prev; struct list_head *next = cur->prev; while (next != head) { element_t *cur_entry = list_entry(cur, element_t, list); element_t *next_entry = list_entry(next, element_t, list); if (strcmp(cur_entry->value, next_entry->value) > 0){ list_del(next); q_release_element(next_entry); } else { cur = next; } next = next->prev; } return q_size(head); } ``` 上面程式在 make test 的過程中，會出現存取 NULL 指標的錯誤情況出現，我分析是因為當 `next` 被刪除後，又在後續執行 `next = next->prev` 時存取`next` ，所以我將程式修改如下，改成透過不會被刪除的 `cur` 執行走訪 ```diff int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head) return 0; struct list_head *cur = head->prev; - struct list_head *next = cur->prev; + struct list_head *next; - while (next != head) { + while (cur->prev != head) { + next = cur->prev; element_t *cur_entry = list_entry(cur, element_t, list); element_t *next_entry = list_entry(next, element_t, list); if (strcmp(cur_entry->value, next_entry->value) > 0){ list_del(next); q_release_element(next_entry); } else { cur = next; } - next = next->prev; } return q_size(head); } ``` ### `q_merge` 首先了解要合併的資料格式，是由許多 `queue_contex_t` 串接而成，我們要合併的佇列是在 `queue_contex_t->q` 我使用的方法事先將所有的 `q` 都取出來存在 `tmp` 最後再對 `tmp` 作排序，以及計算他的長度 ```c typedef struct { struct list_head *q; struct list_head chain; int size; int id; } queue_contex_t; ``` ```c int q_merge(struct list_head *head, bool descend) { // https://leetcode.com/problems/merge-k-sorted-lists/ if (!head || list_empty(head)) { return 0; } if (list_is_singular(head)) { return list_first_entry(head, queue_contex_t, chain)->size; } LIST_HEAD(tmp); queue_contex_t *cur, *safe; queue_contex_t *first = list_first_entry(head, queue_contex_t, chain); list_for_each_entry_safe (cur, safe, head, chain) { list_splice_init(cur->q, &tmp); } int size = q_size(&tmp); list_splice_init(&tmp, first->q); q_sort(first->q, descend); return size; } ``` 在 `make test` 測試時，trace-17-complexity.cmd 無法每次檢測都通過，目前推測是無法在常數時間內完成 ``` +++ TESTING trace trace-17-complexity: # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant Probably constant time ERROR: Probably not constant time or wrong implementation Probably constant time Probably constant time --- trace-17-complexity 0/5 --- TOTAL 95/100 make: *** [Makefile:60: test] Error 1 ``` --- ## Valgrind + 自動測試程式使用 massif 得到分析數據，會得到行程在記憶體使用狀況的 snapshot 。 ```shell $ valgrind --tool=massif ./qtest -f <trace file> ``` 使用 massif-visualizer 圖形化數據 ```shell $ massif-visualizer massif.out.<pid> ``` 使用 Valgrind 驗證程式後，並沒有出現記憶體使用錯誤的狀況，但仍然會有錯誤訊息 `ERROR: Probably not constant time or wrong implementation` ``` xsheep@xsheep-super-computer:~/linux2024/lab0-c$ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd # Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant Probably constant time ERROR: Probably not constant time or wrong implementation Probably constant time Probably constant time Freeing queue ``` 運行 trace-017-complexity ![Screenshot from 2024-03-03 15-20-45](https://hackmd.io/_uploads/HJuIlzQAa.png) 在指令運行階段，此時佔用堆積最主要的函式是 test_malloc ，也就是在運行 `q_insert_head()` 和 `q_insert_tail()` 時會用來分配記憶體的函式  --- ## 實作 `shuffle` 命令 <s>指令</s> :::danger command 是「命令」，而非「指令」(instruction) ::: ### 實作 Fisher-Yates shuffle Algorithm 透過閱讀 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 來實作亂數演算法 >[commit 1152bc0](https://github.com/ssheep773/lab0-c/commit/1152bc0af921da7b2aa23a3044fee293283097d7) 其中因為無法更改 `queue.h` ，我另外新建 `shuffle.c` ，當我要 commit `shuffle.c` 時，會出現錯誤 ``` shuffle.c:25:30: error: Null pointer dereference: (struct element_t*)0 [nullPointer] element_t *newnode = list_entry(new, element_t, list); ^ Fail to pass static analysis. ``` 我在參考 [SHChang-Anderson](https://github.com/sysprog21/lab0-c/commit/26fafd698f4d692298b835a4f49d7666d3afd93d) 同學的 commit 後，加入註解 `// cppcheck-suppress nullPointer` 就可以忽略警告，詳細可以看 ~~[cppcheck.net](https://cppcheck.net/manual.html)~~(網址待更新) ```c element_t *oldnode = list_entry(old, element_t, list); // cppcheck-suppress nullPointer ``` ### 統計方法驗證利用 [lab0-d](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) 提供的程式碼測試亂度 ``` Expectation: 41666 Observation: {'1234': 41827, '1243': 41665, '1324': 41542, '1342': 41630, '1423': 41859, '1432': 41759, '2134': 41789, '2143': 41974, '2314': 41851, '2341': 41778, '2413': 41641, '2431': 41381, '3124': 41769, '3142': 41289, '3214': 41437, '3241': 41520, '3412': 41863, '3421': 41710, '4123': 41678, '4132': 41705, '4213': 41514, '4231': 41478, '4312': 41652, '4321': 41689} chi square sum: 15.7246195939135 ``` 從圖表來看 shuffle 的頻率大致符合 Uniform distribution ![Figure_2](https://hackmd.io/_uploads/SJ52XVXAT.png) ## 論文閱讀〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉這邊論文的目的是評估一段程式碼是否是常數時間執行。而常數時間執行的程式，可以確保程式或系統的安全性，避免有心人的攻擊，像是常見的旁路攻擊 (Side-channel attack) 會用於破譯密碼，通過分析執行加密演算法所花費的時間來嘗試破解密碼系統。論文提出的方法是從使用者的角度或者是說從攻擊者個角度出發，因為當我們無法通過不斷執行程式，達到嘗試破譯密碼時，其實就算是達到常數時間執行，讓使用者無法推測出程式的執行邏輯。這個方法與現有常數時間檢測方法的差異在於不需要模擬硬體設備。 TIMING LEAKAGE DETECTION 實驗的理論是根據執行時間的 leakage detection test ，透過觀察兩個不同測資的執行時間分布是否有顯著的差異。 step 1. Measure execution time 使用 fix-vs-random tests 的方法測試，這種方法是使用兩組測資，一組是每次都固定的測資，另一組是每次都會隨機產生的測資。 step 2. Apply post-processing 典型的時間分佈會向較長的執行時間方向傾斜，這是因為當主程式執行時，可能會被作業系統中斷，造成**測量誤差** (measurement artifacts)，我覺得這步驟主要是彌補沒有對硬體進行模擬。 step 3. Apply statistical test 使用 Welch's t-test 的統計分析，這個方法的特點是可以對樣本大小與資料具有不同變異數的資料進行分析。兩次測試即使一開始設定相同的樣本的大小，也會因為後處理導致最後的樣本數出現差異，這時使用 Welch's t-test 就十分適合。我比較論文提供的程式 [dudect](https://github.com/oreparaz/dudect/tree/master) 與 lab0 程式碼沒有 step 2 的後處理處理測量誤差 [commit 5bf3fe0](https://github.com/ssheep773/lab0-c/commit/5bf3fe02e1d7ab47964b2318ab964cc124df91ee)   --- ## 研讀並嘗試引入 Linux 核心原始程式碼的 lib/list_sort.c [老師的講解筆記](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-e#%E8%97%89%E7%94%B1%E6%B7%B7%E5%90%88%E5%BC%8F%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95%E4%BE%86%E6%94%B9%E9%80%B2%E6%95%88%E8%83%BD) 我所使用的 merge sort 方法是 top-down ，雖然使用更改串列連結的方式，可以改善原有方法對於 cache 的不友善，然而使用遞迴的方式可能會造成 stack overflow Linux kernel 中 list_sort 所使用的方法是 bottom-up ，他是 in-place 直接在原始的數據上實作，使用到 cache 的 Temporal Locality ，畢竟鏈結串列應該是較難發生 Spatial Locality list sort 主要是要處理原本 bottom-up 在合併時，需要較多比較次數，而因為比較是需要透過呼叫 cmp 函式，較多的比較次數也就代表需要更多的函式呼叫成本。 list sort 透過改變合併規則，確保每次合併的兩個子串列的大小比例不超過 2:1，以提高排序效率。 ### 嘗試引入 `lib/list_sort.c` 首先，將 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 和 [linux/list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 引入本專案中首先刪除程式碼中不必要的 include 並發現程式碼中 `u8` 並未定義。而原本是在 linux/types.h 中被定義為 `uint8_t`，而 `uint8_t` 是由 stdint.h 所提供。因此在 list_sort.h 中新增 `#include "stdint.h"` ，並將 `u8` 更改為`uint8_t`，以確保相關型別的定義正確。 ```diff /* list_sort.h */ + #include "stdint.h" ``` ```diff /* list_sort.c */ - u8 count = 0; + uint8_t count = 0; ``` 接著編譯時出現 `implicit declaration of function ‘unlikely’` 發現程式碼中的 likely 與 unlikely 並未被定義，這裡參考 [[Linux Kernel慢慢學]likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/) 中的說明：在 Linux kernel 2.6 之後提供了 likely, unlikely 這兩個巨集，被定義在 /include/linux/compiler.h 中，用於告訴編譯器程式碼中哪個分支轉跳的機率高，幫助編譯器作優化。將 likely, unlikely 這兩個巨集的定義加入 list_sort.h ```diff /* list_sort.h */ + #define likely(x) __builtin_expect(!!(x), 1) + #define unlikely(x) __builtin_expect(!!(x), 0) ``` 最後我們還會遇到 `error: data definition has no type or storage class` 是在 lisy_sort.c 的最後一行，目的是要使`list_sort` 可以在 kernel 內部自由的呼叫使用，但我們並不需要這個功能所以刪除。 ```diff - EXPORT_SYMBOL(list_sort); ``` 其中 list_sort 的呼叫須傳入比較函式 cmp ，我參考 [chiangkd](https://github.com/chiangkd/lab0-c/commit/575c5fdfe6a709fbb659d642d3c79a6eaea693d7) 同學的實作，在 qtest.c 中新增一個比較函式 cmp ，並以此為參數傳入 list_sort。 ### 效能比較參考 [chiangk](https://hackmd.io/@chiangkd/2023spring-lab0-c#%E6%95%88%E8%83%BD%E6%AF%94%E8%BC%83) 的比較方法，並使用 [pref](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 分析執行狀態 ``` perf stat --repeat 5 -e instructions,cycles ./qtest -f traces/trace-sort.cmd ``` trace-sort.cmd ``` option fail 0 option malloc 0 new ih RAND 500000 time sort time ``` #### 執行時間比較我實作的 q_sort 執行時間表： | 測試次數 | 執行時間（秒） | | -------- | -------- | | 1 | 0.45127 | | 2 | 0.46406 | | 3 | 0.46809 | | 4 | 0.46880 | | 5 | 0.45892 | | Instructions | Cycles | | -------- | -------- | | 2,410,251,144 | 2,605,468,924 | linux 的 list_sort 執行時間表： | 測試次數 | 執行時間（秒） | | -------- | -------- | | 1 | 0.44600 | | 2 | 0.43859 | | 3 | 0.44770 | | 4 | 0.44346 | | 5 | 0.44078 | | Instructions | Cycles | | -------- | -------- | | 2,350,066,317 | 2,392,634,305 | 根據上述實驗結果，相較於我自己實作的排序演算法，list_sort 在執行時間呈現出更佳的效能表現。 ## ttt 1.將 Linux 核心的 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 標頭檔與 [jserv/ttt](https://github.com/jserv/ttt) 中 list.h 相關的程式碼抽出，成為 `hlist.h` 我在查看 linux/list.h 時發現，linux kernel 有使用 `READ_ONCE` `WRITE_ONCE` 來實作 lockless contexts 避免 load-tearing (後續要查看 `READ_ONCE` `WRITE_ONCE` 功能) 2.我將原有的 `ttt/main.c` 改寫成 ttt_main.[ch] 方便之後在 qtest.c 中呼叫在引入的過程中仿照 dudect 的方式將 agents 加入 Makefile ，而在 commit 時會出現出現許多 `[constVariable]` 與 `[variableScope]` 的修正提示 ```diff /* mt19937-64.c */ uint64_t mt19937_rand(void) { uint64_t x; - int i if (mti >= NN) { /* generate NN words at one time */ + int i; + const static uint64_t mag01[2] = {0ULL, MATRIX_A}; - static uint64_t mag01[2] = {0ULL, MATRIX_A}; ``` 並使用 Monte Carlo tree search (MCTS) 演算法，確保使用定點數來取代原本 jserv/ttt 的浮點數運算。

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.