2023q1 Homework1 (lab0)

# 2023q1 Homework1 (lab0) contributed by < [`yanjiew1`](https://github.com/yanjiew1) > > [GitHub](https://github.com/yanjiew1/lab0-c) ## 開發與實驗環境 ```bash $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ 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) i5-8250U CPU @ 1.60GHz CPU family: 6 Model: 142 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 10 CPU max MHz: 3400.0000 CPU min MHz: 400.0000 BogoMIPS: 3600.00 ``` ## 進度記錄以下複製自「作業要求」 - [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c) - [x] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。 - [x] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差 * [x] 研讀 Linux 核心 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 原始程式碼的並引入自己的專案 * [x] 比較效能落差 - [ ] 確保 `qtest` 提供的 `web` 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 `linenoise` 套件就無法使用，請提出改善機制 - [x] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」 - [x] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10` 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 `qtest` 切換不同的 PRNG 的實作 (可選定 [Xorshift](https://en.wikipedia.org/wiki/Xorshift))，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質 - [ ] 研讀論文〈[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) 及程式實作的原理。 * [x] 注意：現有實作存在若干致命缺陷，請討論並提出解決方案 * [ ] 解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) * 在 [oreparaz/dudect](https://github.com/oreparaz/dudect) 的程式碼具備 percentile 的處理，但在 [lab0-c](https://github.com/sysprog21/lab0-c) 則無。 - [ ] 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request - [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2023-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下: * [ ] 詳閱第 1 週所有教材及作業描述 [(一)](/@sysprog/linux2023-lab0-a), [(二)](/@sysprog/linux2023-lab0-b), [(三)](/@sysprog/linux2023-lab0-c), [(四)](/@sysprog/linux2023-lab0-d), [(五)](/@sysprog/linux2023-lab0-e)，記錄你的啟發和疑惑 * [x] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤 * [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗 * [ ] 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) ## 改進 `queue.c` ### `q_new` 透過 `malloc` 來配置記憶體，使用 `list.h` 裡面提供的 `INIT_LIST_HEAD` 來初始化 `struct list_head` 。 > commit [0f09bf6](https://github.com/yanjiew1/lab0-c/commit/0f09bf6ab87795c13f8aae2e6f773e48ce41eb0a) ```c /* Create an empty queue */ struct list_head *q_new() { struct list_head *new = malloc(sizeof(struct list_head)); if (!new) return NULL; INIT_LIST_HEAD(new); return new; } ``` ### `q_free` 使用 `list.h` 內提供的 `list_for_each_entry_safe` 來走訪每一個節點。使用的過程中，`safe` 會存放下一個節點，而 `it` 節點可以從 linked list 移除，不影響 `list_for_each_entry_safe` 運作。故在這裡，可以直接在走訪的過程中釋放每一個節點。最後再呼叫 `free` 釋放鏈結串列所配置的記憶體空間。。 ```c /* Free all storage used by queue */ void q_free(struct list_head *l) { if (!l) return; element_t *safe, *it; list_for_each_entry_safe (it, safe, l, list) q_release_element(it); free(l); } ``` #### 開發過程記錄一開始程式碼如下： ```c /* Free all storage used by queue */ void q_free(struct list_head *l) { struct list_head *safe; struct list_head *it; list_for_each_safe (it, safe, l) { list_del(it); free(it); } free(l); } ``` 隨後很快發現，應該要釋放 `element_t` 才對，因為 `struct list_head` 是包含在 `element_t` 裡面的一個成員。於是變更如下： ```diff @@ -5,8 +5,10 @@ void q_free(struct list_head *l) struct list_head *it; list_for_each_safe (it, safe, l) { + element_t *elem = list_entry(it, element_t, list); list_del(it); - free(it); + free(elem->value); + free(elem); } free(l); ``` 但因為釋放 `element_t` 很常被用到，所以後來我寫一個獨立函式 `q_free_elem` 來做。最後又發現 `queue.h` 有提供 `q_release_element` ，最後改成用 `q_release_element` ，修改如下： ```diff @@ -1,14 +1,12 @@ /* Free all storage used by queue */ void q_free(struct list_head *l) { - struct list_head *safe; - struct list_head *it; + element_t *safe; + element_t *it; - list_for_each_safe (it, safe, l) { - element_t *elem = list_entry(it, element_t, list); - list_del(it); - free(elem->value); - free(elem); + list_for_each_entry_safe (it, safe, l, list) { + list_del(&it->list); + q_release_element(it); } free(l); ``` 後來又仔細研究 `list_for_each_entry_safe` 巨集後，發現 `list_del` 可以不用做。此巨集的特性是我們可以把 `it` 直接釋放，只要不要動到 `safe` ，就可以安全操作。最後變更如下： ```diff @@ -1,13 +1,12 @@ /* Free all storage used by queue */ void q_free(struct list_head *l) { - element_t *safe; - element_t *it; + if (!l) + return; - list_for_each_entry_safe (it, safe, l, list) { - list_del(&it->list); + element_t *safe, *it; + list_for_each_entry_safe (it, safe, l, list) q_release_element(it); - } free(l); } ``` ### `q_new_elem` 配合 `q_insert_head` 和 `q_insert_tail` 要新增元素，新增此函式，用來建立 `element_t` 。使用 `malloc` 來配置記憶體空間。使用 `strdup` 來配置字串空間並拷貝字串。過程中如果配置失敗，則回傳 `NULL` 。 > commit [1e56bd7](https://github.com/yanjiew1/lab0-c/commit/1e56bd7b5c02c5dcc2710b7ba90f3ccd294814c9) ```c /* Create a new element with the provided string */ static inline element_t *q_new_elem(char *s) { element_t *elem = malloc(sizeof(element_t)); if (!elem) return NULL; char *tmp = strdup(s); if (!tmp) { free(elem); return NULL; } elem->value = tmp; return elem; } ``` ### `q_insert_head` 和 `q_insert_tail` 一開始要檢查 `head` 是否為 `NULL` ，若為 `NULL` 則不進行任何操作。使用前面建立的 `q_new_elem` 來建立 `element_t` 。並且透過 `list_add` 或 `list_add_tail` 來把節點串上去。若過程中失敗則回傳 `false` 。 ```c /* Insert an element at head of queue */ bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *elem = q_new_elem(s); if (!elem) return false; list_add(&elem->list, head); return true; } /* Insert an element at tail of queue */ bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *elem = q_new_elem(s); if (!elem) return false; list_add_tail(&elem->list, head); return true; } ``` ### `q_copy_string` 在 `q_remove_head` 和 `q_remove_tail` 需要複製字串，且 buffer 的大小是有限制的。C 標準函式庫提供的 `strcpy` 無法滿足此需求，故在此實作另一個函式 `q_copy_string` 來完成字串拷貝。 ```c static inline void q_copy_string(char *dest, size_t size, const char *src) { size_t i; for (i = 0; i < size - 1 && src[i] != '\0'; i++) dest[i] = src[i]; dest[i] = '\0'; } ``` :::warning 此函式是否必要？其通用的程度如何？ :notes: jserv > 謝謝老師，已改用 `strncpy` 來處理 > Commit [5b8c553](https://github.com/yanjiew1/lab0-c/commit/5b8c5537b832e02c045c65deba88578993999dad) ::: ### `q_remove_head` 和 `q_remove_tail` 這裡實作從佇列中移走開頭或尾端。利用 `list_first_entry` 和 `list_last_entry` 來取得要移除的元素。使用 `list_del` 來移除元素。題目要求要把移除元素的字串值拷貝到 `sp` 這個 buffer ，並且 buffer 大小為 `bufsize` ，就透過前面實作的 `q_copy_string` 來做。 ```c /* Remove an element from head of queue */ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *elem = list_first_entry(head, element_t, list); list_del(&elem->list); if (sp && bufsize) q_copy_string(sp, bufsize, elem->value); return elem; } ``` <s>`q_remove_tail` 程式碼相似，就不佔用版面了。</s> :::warning 正因程式碼相似度高，你更該思索如何簡化程式碼，從而降低維護的程式碼。 :notes: jserv > 已讓 `q_remove_tail` 和 `q_insert_tail` 重用 `q_remove_head` 和 `q_insert_head` 程式碼。謝謝老師 > Commit [bc97533](https://github.com/yanjiew1/lab0-c/commit/bc97533e3e2726eca6cf822d3e7550ca38792fca) ::: ### `q_size` 實作很簡單：直接使用 `list.h` 提供的 `list_for_each` 來走訪每一個節點。每走訪一個節點就遞增 `count` 變數，最後再回傳 `count` 變數的值即為所求。 ```c /* Return number of elements in queue */ int q_size(struct list_head *head) { if (!head) return 0; int count = 0; struct list_head *it; list_for_each (it, head) count++; return count; } ``` ### `q_delete_mid` 這裡充份利用雙向鏈結串列的特性，從頭尾開始走訪節點，直到二個指標碰面時，即取得中間的節點。最後再把中間節點所代表的元素刪除。 ```c /* Delete the middle node in queue */ bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return false; struct list_head *left = head->next; struct list_head *right = head->prev; while (left != right && left->next != right) { left = left->next; right = right->prev; } list_del(right); element_t *elem = list_entry(right, element_t, list); q_release_element(elem); return true; } ``` ### `q_delete_dup` 我的作法是先宣告 `cut` 變數，其內容固定存放「目前走訪元素往前看，第一個其元素值與目前元素不同的元素」。此外另外宣告一個 ~~`trash`~~ `pending` 作為暫時放置待移除元素的地方，要移除的元素都會先放在這裡，最後再一起清掉。 :::warning "trash" 命名不精準，可用 pending list 一類的詞彙。 :notes: jserv > 已修改。 Commit [a725fcc](https://github.com/yanjiew1/lab0-c/commit/a725fcc2c8b58c9e8d661ff15c978e79552d4fda) ::: 在走訪元素的過程中， ~~`&safe->list != head && strcmp(safe->value, it->value) == 0`~~ `&safe->list != head && !strcmp(safe->value, it->value)` 會去判斷下一個元素跟目前元素的值是否相同。若相同時，就繼續走訪，直到遇到下個元素 `safe` 與目前元素 `it` 值不同時，再來進行接下來操作，如下：當下個元素 `safe` 與目前元素 `it` 不同時，會先去檢查 `cut` 變數，是不是指向前一個元素。若是指向前一個元素，代表目前元素跟前一個元素不同，則不用處置，因為目前元素 `it` 跟前一個元素沒有重複；若 `cut` 不是指向前一個元素，則代表 `cut` 指向更之前的元素，且 $(cut, it]$ 元素其值均相同，故把 $(cut, it]$ 元素全部~~丟到 `trash`~~ 放到 `pending` 中。迴圈最後 `cut = safe->list.prev;` 這敘述，因為目前元素 `it` 與下一個元素值 `safe` 不同 (若相同就不會執行到此，故更新 `cut` 為目前元素後，再進行下個迴圈。迴圈結束 `q_delete_dup` 要返回前。要清除 ~~`trash`~~ `pending` 裡的~~垃圾~~元素。用 `list_for_each_entry_safe` 來走訪每一個 ~~`trash`~~ `pending` 中的元素，並用 `q_release_element` 來刪除它。 ```c /* Delete all nodes that have duplicate string */ bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) return false; LIST_HEAD(pending); element_t *it, *safe; struct list_head *cut = head; list_for_each_entry_safe (it, safe, head, list) { if (&safe->list != head && !strcmp(safe->value, it->value)) continue; /* Detect duplicated elements */ if (it->list.prev != cut) { LIST_HEAD(tmp); list_cut_position(&tmp, cut, &it->list); list_splice(&tmp, &pending); } cut = safe->list.prev; } /* Process pending list */ list_for_each_entry_safe (it, safe, &pending, list) q_release_element(it); return true; } ``` :::warning 將 `strcmp(safe->value, it->value) == 0` 改為 `!strcmp(safe->value, it->value)` 可縮減程式碼。 :notes: jserv > 已修改 Commit [bd9253a](https://github.com/yanjiew1/lab0-c/commit/bd9253aa92b0673b3805ae815fd0dc72332e5f59) ::: ### `q_reverse` 這裡的實作很簡單，就是用 `list_for_each_safe` 走訪每一個節點。走訪過程中，用 `list_move` 把每一個節點移到開頭，這樣子順序就反過來了。 `list_for_each_safe` 允許對目前走訪的節點移動位置。因為是往前移到開頭，故不會因為節點移動而改變走訪次序或是重複走訪。 ```c /* Reverse elements in queue */ void q_reverse(struct list_head *head) { if (!head) return; struct list_head *it, *safe; /* Iterate the list and move each item to the head */ list_for_each_safe (it, safe, head) list_move(it, head); } ``` #### 變更記錄把 `list_for_each_safe` 大括號拿掉，按照 Coding Style ，這裡不用放大括號。 ```diff diff --git a/queue.c b/queue.c diff --git a/queue.c b/queue.c struct list_head *it, *safe; /* Iterate the list and move each item to the head */ - list_for_each_safe (it, safe, head) { + list_for_each_safe (it, safe, head) list_move(it, head); - } } ``` ### `q_reverseK` 使用 `count` 來記錄已走訪幾個節點，一開始把 `count` 設為 `k` ，每走訪一個節點就把 `count` 減去 1 。當走訪 `k` 個節點時 (`--count` 變成 0)，就會把 `cut` 記錄的切點到目前走訪的節點(不包含 `cut` 但包含 `it`，即 `(cut, it]`)切下，放到 `tmp` 上，再重用前面實作好的 `q_reverse` ，對 `tmp` 做反轉，再用 `list_splice` 把 `tmp` 接回來。最後設定 `safe->prev` 為新的 `cut` 。這裡不能用 `it` 是因為 `it` 已在反轉的過程中移動位置了。 ```c /* Reverse the nodes of the list k at a time */ void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head || list_empty(head)) return; struct list_head *it, *safe, *cut; int count = k; cut = head; list_for_each_safe (it, safe, head) { if (--count) continue; LIST_HEAD(tmp); count = k; list_cut_position(&tmp, cut, it); q_reverse(&tmp); list_splice(&tmp, cut); cut = safe->prev; } } ``` :::warning 追加 `list_empty()` 的檢查。 :notes: jserv > 已修正 > Commit [b536d66](https://github.com/yanjiew1/lab0-c/commit/b536d66e3dbdab1503169324b5247b7b541bb2f7) ::: ### `q_swap` `swap` 就是二個二個一組進行 `reverse` ，故直接重用 `q_reverseK` 的程式。 ```c /* Swap every two adjacent nodes */ void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ q_reverseK(head, 2); } ``` ### `q_merge_two` 因為 `q_sort` 和 `q_merge` 都會需要合併二個串列。故新增一個 `q_merge_two` 用來合併二個串列。參考 `alanjian85` 同學的實作。合併的方式是每次從輸入的二個串列中，取較小的，放到一個暫存串列中 `tmp` ，之後再把串列接回 `first` 。 ```c static int q_merge_two(struct list_head *first, struct list_head *second) { if (!first || !second) return 0; int count = 0; LIST_HEAD(tmp); while (!list_empty(first) && !list_empty(second)) { element_t *f = list_first_entry(first, element_t, list); element_t *s = list_first_entry(second, element_t, list); if (strcmp(f->value, s->value) <= 0) list_move_tail(&f->list, &tmp); else list_move_tail(&s->list, &tmp); count++; } count += q_size(first) + q_size(second); list_splice(&tmp, first); list_splice_tail_init(second, first); return count; } ``` ### `q_sort` 採用 merge sort 遞迴演算法。一開始運用雙向鏈結串列的特性，從頭尾開始往中間找到中間節點，找到後，把 (`head`, `mid`] 留在 `head` 並把 (`mid`, `head`) 切下來加到 `second` 中。再針對 `head` 、 `second` 分別遞迴呼叫 `q_sort` ，對子串列進行排序。最後再把排序好的 `head` 和 `second` 透過 `q_merge_two` 合併。 ```c /* Sort elements of queue in ascending order */ void q_sort(struct list_head *head) { /* Try to use merge sort*/ 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; /* Divide into two part */ LIST_HEAD(second); list_cut_position(&second, mid, head->prev); /* Conquer */ q_sort(head); q_sort(&second); /* Merge */ q_merge_two(head, &second); } ``` :::warning 若要改為迭代的實作，你預計怎麼做？ :notes: jserv > 在還沒看到 Linux kernel 排序演算法前，我會傳統資料結構教科書內 bottom-up 方式實作。看到 Linux 排序演算法後，很明顯發現它比傳統教科書方式聰明。之後我會研究 Python 內的 Timsort 來實作。把 Timsort 實作出來後，新增一個 `sort` option ，來切換排序演算法。 ::: #### 更新記錄原本串列合併的程式直接寫在 `q_sort` 裡，後來把它移到獨立的函式中。 > Commit [09de13c](https://github.com/yanjiew1/lab0-c/commit/09de13c7234b40731030f571198ffeab7a06a999) ### `q_descend` 我的想法就是從尾到頭掃過一次。在掃的過程中，會判斷下一個節點(`prev`)是否小於~~等於~~目前節點(`cur`)，若是就把下一個節點(`prev`)刪除再重複迴圈，直到下一個節點是大於目前節點時，才會把 `cur` 移動到下一個節點，並且 `cnt` (計數器) 加 1 。目前 `lab0-c` 內建的 `list.h` 標頭檔和 Linux 核心原始程式碼 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 存在一些差距，後者的 `list_for_each_prev` 巨集不在前者出現。若有它則可以用它來實作。 ```c /* Remove every node which has a node with a strictly greater value anywhere to * the right side of it */ int q_descend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head)) return 0; /** * Traverse from the last entry and remove the element that is * smaller or equal to its right. Also count the number of elements. */ int cnt = 1; element_t *cur = list_last_entry(head, element_t, list); while (cur->list.prev != head) { element_t *prev = list_last_entry(&cur->list, element_t, list); if (strcmp(prev->value, cur->value) < 0) { list_del(&prev->list); q_release_element(prev); } else { cnt++; cur = prev; } } return cnt; } ``` :::warning 針對呼叫 `strcmp` 的那行敘述，若搭配使用 `break` 或 `continue` 關鍵字，可進一步縮減程式碼。 :notes: jserv ::: ### `q_merge` 採用 [Strategies for Stable Merge Sorting](https://arxiv.org/pdf/1801.04641.pdf) 這篇論文中的 2-merge 演算法來實作。用此演算法，使合併二個 queue 時，其二個 queue 元素數量差距不要太大。其運作原理是這樣： 1. pending list 為一類似 stack 的結構，意即先加入它的 queue 會在後面才取出來。 2. 每次迴圈加入 1 個 queue 進入 pending list ，直到沒有未加入 pending list 的 queue。若 pending list 個數大於 3 個時，判斷是否合併： - 從 pending list 依序取出 `x`, `y`, `z` 。若 `|y| < 2|x|` 則按下步驟進行合併，若否，則繼續進行 2. 迴圈 - 若 `|x| < |z|` 則將 `x` 和 `y` 合併，否則 `y` 和 `z` 合併 - 合併後需要再重新取出 `x` 、 `y` 、 `z` ，判斷是否符合需要合併的條件 4. 把 pending list 中未合併的 queue 進行合併。 ```c /* Merge all the queues into one sorted queue, which is in ascending order */ int q_merge(struct list_head *head) { // 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; /* Use 2-merge algorithm in https://arxiv.org/pdf/1801.04641.pdf */ LIST_HEAD(pending); LIST_HEAD(empty); int n = 0; while (!list_empty(head)) { list_move(head->next, &pending); n++; while (n > 3) { queue_contex_t *x, *y, *z; x = list_first_entry(&pending, queue_contex_t, chain); y = list_first_entry(&x->chain, queue_contex_t, chain); z = list_first_entry(&x->chain, queue_contex_t, chain); if (y->size >= z->size << 1) break; if (x->size < z->size) { y->size = q_merge_two(y->q, x->q); list_move(&x->chain, &empty); n--; } else { z->size = q_merge_two(z->q, y->q); list_move(&y->chain, &empty); n--; } } } /* Merge remaining list */ while (n > 1) { queue_contex_t *x, *y; x = list_first_entry(&pending, queue_contex_t, chain); y = list_first_entry(&x->chain, queue_contex_t, chain); y->size = q_merge_two(y->q, x->q); list_move(&x->chain, &empty); n--; } /* Move the last queue and empty queue to head */ list_splice(&empty, head); list_splice(&pending, head); return list_first_entry(head, queue_contex_t, chain)->size; } ``` #### 更新記錄原本是這重用前面實作的 `q_sort` 。我把所有鏈結串列接在一起，然後呼叫 `q_sort` 排序好，放回第一個串列。後來變更實作，改成直接進行合併，並且合併時，透過一些策略降低二個 queue 要合併時的長度差異。 > Commit [f6568be](https://github.com/yanjiew1/lab0-c/commit/f6568bed251b77837fa0ab2b87ff2642adef718b) ### `q_ascend` 這是後來 `lab-0` 加上的函式，跟 `q_descend` 很像。故把 `q_descend` 的程式複製一份來用，把中間的 `<` 改為 `>` 即可。 ```c int q_ascend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head)) return 0; /** * Traverse from the last entry and remove the element that is * smaller or equal to its right. Also count the number of elements. */ int cnt = 1; element_t *cur = list_last_entry(head, element_t, list); while (cur->list.prev != head) { element_t *prev = list_last_entry(&cur->list, element_t, list); if (strcmp(prev->value, cur->value) > 0) { list_del(&prev->list); q_release_element(prev); } else { cnt++; cur = prev; } } return cnt; } ``` --- ## Valgrind 與 Address Sanitizer 記憶體檢查 ### Makefile 中關於 `make valgrind` 的內容分析 ``` valgrind: valgrind_existence # Explicitly disable sanitizer(s) $(MAKE) clean SANITIZER=0 qtest $(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX)) cp qtest $(patched_file) chmod u+x $(patched_file) sed -i "s/alarm/isnan/g" $(patched_file) scripts/driver.py -p $(patched_file) --valgrind $(TCASE) @echo @echo "Test with specific case by running command:" @echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>" ``` 裡面看到很神奇的部份，就是在用 Valgrind 執行時，會把 `qtest` 執行檔中，所有 `alarm` 改為 `isnan` 。我的猜測是因為 Valgrind 會使程式執行速度變慢，導致一些操作會超過時間限制。我把這行拿掉 `sed -i "s/alarm/isnan/g" $(patched_file)` ，執行 `make valgrind` ，果然就出現超時訊息。查詢 C 標準函式庫可知，[isnan(3p)](https://man7.org/linux/man-pages/man3/isnan.3p.html) 是用來檢查傳入的浮點數是否為 NaN ，會選用這個函數來取代 `alarm` ，估計是因為它跟 `alarm` 一樣函式名稱都是 5 個字元，此外 `isnan` 沒有任何 side effects ，故剛好可以拿來用。為了測試，我嘗試把 `isnan` 替換成 `asinf` 看看能不能運作。實測的結果如預期，可以正常運作。 ### 使用 Valgrind 執行 `make valgrind` ，產生了很多 Memory leak 的訊息。以下為節錄的訊息： ``` +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head ==30743== 32 bytes in 1 blocks are still reachable in loss record 1 of 2 ==30743== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==30743== by 0x10CBE6: do_new (qtest.c:146) ==30743== by 0x10DE12: interpret_cmda (console.c:181) ==30743== by 0x10E3C7: interpret_cmd (console.c:201) ==30743== by 0x10E7C8: cmd_select (console.c:610) ==30743== by 0x10F0B4: run_console (console.c:705) ==30743== by 0x10D204: main (qtest.c:1228) ==30743== ``` 我先用 `valgrind ./qtest` 的方式測試，發現只要在結束前沒有把所有的 queue 釋放，就會產生上述訊息。後來發現在 `q_quit` 裡面，在第一行是 `return true;` 使下面釋放記憶體的程式沒辦法執行。把這行拿掉後就正常了。 ```diff --- a/qtest.c +++ b/qtest.c @@ -1059,7 +1059,6 @@ static void q_init() static bool q_quit(int argc, char *argv[]) { - return true; report(3, "Freeing queue"); if (current && current->size > BIG_LIST_SIZE) set_cautious_mode(false); ``` 但若是使用 `valgrind ./qtest < traces/trace-01-ops.cmd` 的方式來執行，仍然會出現下面訊息： ``` ==33817== 130 bytes in 10 blocks are still reachable in loss record 1 of 3 ==33817== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==33817== by 0x49FE60E: strdup (strdup.c:42) ==33817== by 0x1121B9: line_history_add (linenoise.c:1275) ==33817== by 0x113014: line_hostory_load (linenoise.c:1360) ==33817== by 0x10D332: main (qtest.c:1215) ==33817== ==33817== 130 bytes in 10 blocks are still reachable in loss record 2 of 3 ==33817== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==33817== by 0x49FE60E: strdup (strdup.c:42) ==33817== by 0x1121B9: line_history_add (linenoise.c:1275) ==33817== by 0x10F10C: run_console (console.c:692) ==33817== by 0x10D2D7: main (qtest.c:1227) ==33817== ==33817== 160 bytes in 1 blocks are still reachable in loss record 3 of 3 ==33817== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==33817== by 0x112205: line_history_add (linenoise.c:1263) ==33817== by 0x113014: line_hostory_load (linenoise.c:1360) ==33817== by 0x10D332: main (qtest.c:1215) ==33817== ``` 從上述訊息可以看出是 linenoise 中處理 history 的部份出錯。分析了一下 linenoise.c 的程式碼，發現 `line_atexit` 只會在 `enable_raw_mode` 函式裡被註冊為 atexit function ，但是在 stdin 不為 tty 的情況下 `enable_raw_mode` 不會被呼叫到。故把註冊 `line_atexit` 的程式移到 `linenoise` function 就解決了。 ```diff --- a/linenoise.c +++ b/linenoise.c @@ -243,10 +243,6 @@ static int enable_raw_mode(int fd) { if (!isatty(STDIN_FILENO)) goto fatal; - if (!atexit_registered) { - atexit(line_atexit); - atexit_registered = true; - } if (tcgetattr(fd, &orig_termios) == -1) goto fatal; @@ -1189,6 +1185,11 @@ char *linenoise(const char *prompt) { char buf[LINENOISE_MAX_LINE]; + if (!atexit_registered) { + atexit(line_atexit); + atexit_registered = true; + } + if (!isatty(STDIN_FILENO)) { /* Not a tty: read from file / pipe. In this mode we don't want any * limit to the line size, so we call a function to handle that. */ ``` 至此，所有 `make valgrind` 會產生的記憶體問題都解決了。 ### 使用 address sanitizer 重新編譯有開啟 address sanitizer 的版本。 ```bash make clean make SANITIZER=1 ``` 之後執行 `make test` ，沒有出現任何記憶體相關錯誤訊息。至此檢查通過。 --- ## 加入 option `descend` `lab-0` 在 Commit [0fcefb0](https://github.com/sysprog21/lab0-c/commit/0fcefb0b3da3a4a33cad00e7e68248ab909e348a) 加入了 `descend` option ，故把上游版本 `sysprog21/lab0-c` 合併進來時，也需要一併實作 option `descend` 。 ### 修改 `q_merge_two` 因為 `q_sort` 和 `q_merge` 都會用到 `q_merge_two` 來合併二個串列。故在 `q_merge_two` 實作合併時，由大到小排序。其中迴圈內在選擇要哪一個元素放到合併後的串列時，做了些更動，如下： ```diff element_t *f = list_first_entry(first, element_t, list); element_t *s = list_first_entry(second, element_t, list); - if (strcmp(f->value, s->value) <= 0) + int cmp = strcmp(f->value, s->value); + if (descend) + cmp = -cmp; + if (cmp <= 0) list_move_tail(&f->list, &tmp); else list_move_tail(&s->list, &tmp); ``` 而 `q_merge_two` 函式宣告改為： ```c static int q_merge_two(struct list_head *first, struct list_head *second, bool descend) ``` 針對 `descend` 為 `true` 的清況，正負號反轉，即可實現大到小排序，且也維持 `q_sort` 和 `q_merge` 的穩定排序特性。 ### 修改 `q_sort` 和 `q_merge` 而 `q_sort` 和 `q_merge` 則是修改成：呼叫 `q_merge_two` 時會多傳入 `descend` 參數，來決定是否要由大到小排序。 ### 修改 `q_ksort` `q_ksort` 是使用 Linux 核心的 `list_sort` 排序演算法。`list_sort` 會傳入比較函式 `cmp` 作為參數。故我實作一個比較函式 `q_cmp_descend` ，它會呼叫原本的比較函式 `q_cmp` ，但正負號相反，如下： ```c static int q_cmp_descend(void *priv, const struct list_head *a, const struct list_head *b) { return -q_cmp(priv, a, b); } ``` 再把 `q_ksort` 改成判斷 `descend` 是否為 `true` ，再選擇適當的比較函式。 ```c void q_ksort(struct list_head *head, bool descend) { if (!head || list_empty(head) || list_is_singular(head)) return; list_cmp_func_t cmp = descend ? q_cmp_descend : q_cmp; list_sort(NULL, head, cmp); } ``` --- ## Linux 核心 Linked List 排序研究 ### 整合 Linux 核心的 `list_sort` 將 Linux 核心原始程式碼的 `list_sort.c` 和 `list_sort.h` 複製到 `lab0-c` 專案中，進行些許修改讓它可以成功在這個專案中編譯。主要是把 `u8` 改為 `uint8_t` (並加入 `stdint.h`) 、移除不必要的 `#include` 。之後修改 `Makefile` 加入 `list_sort.o` 後，確認用 `make` 命令可以正常編譯。接下來是額外撰寫一份用 Linux kernel 排序的程式。因為 `queue.h` 不能更動，我決定把這個程式放在另一個檔案 `ksort.c` 並且有對應的標頭檔 `ksort.h` 。此也在 `Makefile` 內加入 `ksort.o` 。因為 Linux kernel 實作需傳入 `cmp` 比較函式作為比較大小用。我的實作如下： ```c static int q_cmp(void *priv, const struct list_head *a, const struct list_head *b) { // cppcheck-suppress nullPointer element_t *elem_a = list_entry(a, element_t, list); // cppcheck-suppress nullPointer element_t *elem_b = list_entry(b, element_t, list); return strcmp(elem_a->value, elem_b->value); } ``` 我新增了一個 option `ksort` ，可以用來切換排序實作。在 `qtest.c` 按照原本定義 option 的格式新增下方程式在 `console_init` 中。此外也加入一個全域變數來記錄目前要使用的排序實作。 :::warning 未來或許會有多款排序的實作，設計選項時，應予以考慮，亦即你可用 `option sort 0` (預設), `option sort 1` (上述來自 Linux 核心原始程式碼的 `list_sort`), `option sort 2` (未來實作的排序程式碼) 來切換。 :notes: jserv ::: ```c static int use_ksort = 0; ``` ```c add_param("ksort", &use_ksort, "Whether to use Linux kernel sorting algorithm", NULL); ``` ### 效能分析在開始分析效能前。看到 Linux 核心的 `list_sort` 是以 bottom-up 方式實作 merge sort 並且合併方式是用對 cache 較友善的方式。即 $3 \times 2^k$ 就合併，大概可以猜測 Linux 的排序實作效能會比較好。我用以下的命令序列來分析排序效能: ``` new option ksort 1/0 <= 跟據要測試的排序實作進行切換 ih RAND 2000000 shuffle time sort <= 執行 10 次取平均，中間以 shuffle 間隔 ``` 為了避免出現 Time out 的問題。開始測試前會先 patch ./qtest，即 `sed -i "s/alarm/isnan/g"`。測試的結果如下表： | 我的排序 | Linux Kernel 排序 | | -------- | ----------------- | | 2.8899 | 2.1537 | 可以看到我的 top-down 排序演算法花的時間是 Linux 核心 `list_sort` 實作的 1.341 倍。即比 Linux 排序演算法慢 34% 左右。 ### Linux Kernel Linked List 排序演算法探索 Linux 核心是使用 bottom-up 的 merge sort ，但是它合併的方式跟傳統教科書不一樣。 :::info **TODO** 補完此節 ::: --- ## `web` 命令/網頁伺服器改善 :::info TODO ::: --- ## 亂數研究及 shuffle 實作 ### 程式實作在作業說明裡面，每次抽到的數字後，都要從最前面開始往後數，這樣子會讓時間複雜度最壞情況至 $O(n^2)$ ，故我採取不同的策略。我先建立一個存放所有節點的指標陣列，如下所示： ```c struct list_head **entries = malloc(sizeof(struct list_head *) * size); ``` :::warning 可變更為 `malloc(sizeof(*entries) * size)` 以縮減程式碼。 :notes: jserv > 已修改。 Commit [92d98c6](https://github.com/yanjiew1/lab0-c/commit/92d98c6902dcc681297d2485141a51508100f6a3) ::: 把所有節點的位址放入陣列中： ```c int i = 0; list_for_each (node, head) entries[i++] = node; ``` 取得隨機數先直接使用 C 語言標準函式庫提供的 `rand` 函數取得隨機數。因為 `rand` 的範圍是 `[0, RAND_MAX]` ， `RAND_MAX` 不一定可以被候選數個數整除。故使用一個迴圈，丟棄任何會大於 `RAND_MAX - (RAND_MAX % k)` 的數值，使得取得的隨機數最大值可被候選數個數整除。讓每一個候選數被選中的機率是一樣的。以下是相關程式碼片段。這裡要取得 $[0, i]$ 之間的數。 ```c int n; do { n = rand(); } while (n >= RAND_MAX - (RAND_MAX % (i + 1))); n %= i + 1; ``` :::warning 對照看 `random.[ch]` 程式碼。 :notes: jserv ::: :::info 這樣的實作缺點是需要使用 `malloc` 來配置額外空間。無法做到空間複雜度 $O(1)$ 。目前還沒想到能在時間複雜度為 $O(n)$ 情況下，空間複雜度為 $O(1)$ 的方式。 ::: ### Fisher–Yates shuffle 亂度分析分析方式為建立一個 queue ，並分別新增 a, b, c, d 至 queue 中。執行 shuffle 1000000 次，並統計每種排列方式出現的次數。直接使用作業說明提供的程式來分析。把作業說明的 Python 程式複製到 `script/shuffle.py` ，並修改改用 a, b, c, d 來進行 shuffle 測試。 | 排列 | 出現次數 | 期待次數 | ${(O_i - E_i)^2 \over E_i}$ | |------|----------|----------|-----------| | abcd | 41451 | 41666.67 | 1.1162907 | | abdc | 41827 | 41666.67 | 0.6169627 | | acbd | 41722 | 41666.67 | 0.0734827 | | acdb | 41524 | 41666.67 | 0.4884907 | | adbc | 41707 | 41666.67 | 0.0390427 | | adcb | 41439 | 41666.67 | 1.2439707 | | bacd | 41937 | 41666.67 | 1.7539227 | | badc | 41628 | 41666.67 | 0.0358827 | | bcad | 42129 | 41666.67 | 5.1300507 | | bcda | 41591 | 41666.67 | 0.1374107 | | bdac | 41626 | 41666.67 | 0.0396907 | | bdca | 41709 | 41666.67 | 0.0430107 | | cabd | 41418 | 41666.67 | 1.4840427 | | cadb | 41500 | 41666.67 | 0.6666667 | | cbad | 41712 | 41666.67 | 0.0493227 | | cbda | 41794 | 41666.67 | 0.3891307 | | cdab | 41439 | 41666.67 | 1.2439707 | | cdba | 42090 | 41666.67 | 4.3010667 | | dabc | 41767 | 41666.67 | 0.2416027 | | dacb | 41190 | 41666.67 | 5.4530667 | | dbac | 41823 | 41666.67 | 0.5865627 | | dbca | 41679 | 41666.67 | 0.0036507 | | dcab | 41625 | 41666.67 | 0.0416667 | | dcba | 41673 | 41666.67 | 0.0009627 | | Total| | | 25.17992 | 使用[此線上工具](https://www.socscistatistics.com/pvalues/chidistribution.aspx)計算 P 值，計算出來為 **0.34** 左右，故無法拒絕 Fisher–Yates shuffle 不是 Uniform Distribution。 ### Entropy 觀察跟據作業要求，執行以下命令來觀察 entropy。 ``` option entropy 1 new it RAND 10 ``` ```! l = [haiowq(29.69%) wncthutns(32.81%) yhzrx(26.56%) dfjqntag(35.94%) whgushb(29.69%) ciahh(21.88%) oidgffg(26.56%) pmeqkxou(35.94%) xffww(17.19%) nrgavix(32.81%)] ``` 大致上可以發現，在相同字串長度下，不重複的字母數愈多，其 entropy 愈高。例如： `ciahh(21.88%)`, `xffww(17.19%)` ，也就是代表其亂度愈高。從 entropy 公式可以發現，若字串中每一個字母其出現機率愈一致（即字串愈亂)，且一字串所包含的不同字母數愈多 (即每個字母出現的機率一致)，其 entropy 愈高，符合作業說明所說的。不過到這裡，我還是沒有完全理解 entropy 的意義，目前的理解是：它用來表達一個訊息內容有多亂。之後還要再研讀。 ### 加入 Xoshiro256++ 亂數產生器並比較系統提供之亂數產生器 `qtest` 亂數產生器存放在 `random.c` ，可以看到此亂數產生器是直接使用 Linux 核心提供的亂數產生器。我跟據作業提供的 Wikipedia Xorshift [參考連結](https://en.wikipedia.org/wiki/Xorshift)，並參考了相關的變形實作。我決定引進 Xoshiro256++ 來作為另一套亂數產生器。因為原本的 Xorshift 跟據維基百科說明，在統計上可能有些瑕疵。而其變種 Xoshiro256++ 在[作者官網](https://prng.di.unimi.it/)介紹中感覺看不出有瑕疵。 > Xorshift 是 [Linear-feedback shift register](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) (LFSR) 的子集合作者在他的網站上[提供了 Xoshiro256++ 的程式碼](https://prng.di.unimi.it/xoshiro256plusplus.c)，故我就直接使用作者網站提供的程式碼，再做點修改。此外作者建議使用 SplitMix64 作為初始化 Xoshiro256++ 的內部狀態，同樣也在他的網站上[提供程式碼](https://prng.di.unimi.it/splitmix64.c)，我也直接把它拿來用。把上述程式結合，再做點修改後，Xoshiro256++ 亂數產生器程式放在 [xoshiro.c 檔案](https://github.com/yanjiew1/lab0-c/blob/master/xoshiro.c)內。另外再建立一個 [`qrandom.c` 檔案](https://github.com/yanjiew1/lab0-c/blob/master/qrandom.c)，這裡是亂數產生器的單一入口，會再透過全域變數 `qrandom_impl` 來決定要使用的亂數產生器。而 `qrandom_impl` 可用 `option random` 來控制。目前設定是 `qrandom_impl == 0` 時使用系統提供的亂數產生器， `qrandom_impl != 1` 時就用 Xoshiro256++。此外，我在 `qtest.c` 內實作 `-r`　選項，可讓 `qtest` 直接使用內部的亂數產生器，產生隨機 raw bytes 並輸出到 stdout 。`-r 0` 為使用內建的亂數產生器，`-r 1` 為使用 xoshiro256++ ，搭配作業說明 `ent` 工具來評估亂數產生器的品質。在 `main` 函式處理命令列選項的 switch-case 地方加入： ```c case 'r': char *endptr; errno = 0; qrandom_impl = strtol(optarg, &endptr, 10); if (errno != 0 || endptr == optarg) { fprintf(stderr, "Invalid random number generator\n"); exit(EXIT_FAILURE); } generate_randombytes(); break; ``` 另外也新增一個函式 `generate_randombytes` ，來把亂數輸出到 stdout 。 ```c #define RANDOM_BYTES 1048576 static void generate_randombytes(void) { uint8_t *buf = malloc(RANDOM_BYTES); if (!buf) exit(1); do { qrandombytes(buf, RANDOM_BYTES); } while (fwrite(buf, RANDOM_BYTES, 1, stdout)); exit(0); } ``` #### `Xoshiro256++` 亂數品質測試執行下面命令來測試亂數品質，可得到這個報告 ```shell ./qtest -r 1 | head -c 10M | ent Entropy = 7.999998 bits per byte Optimum compression would reduce the size of this 104857600 byte file by 0 percent. Chi square distribution for 104857600 samples is 264.69, and randomly would exceed this value 32.52 percent of the times. Arithmetic mean value of data bytes is 127.4997 (127.5 = random). Monte Carlo value for Pi is 3.142157713 (error 0.02 percent). Serial correlation coefficient is 0.000097 (totally uncorrelated = 0.0). ``` 卡方檢定的結果 p 值為 32.52% ，離 5% 遙遠，故此亂數產生器產生的亂數可能是 Uniform Distribution 的。此外 entropy 值為 7.99998 bits per byte, 可說是相當高。 #### 系統內建亂數測試 ```bash $ ./qtest -r 0 | head -c 10M | ent Entropy = 7.999983 bits per byte. Optimum compression would reduce the size of this 10485760 byte file by 0 percent. Chi square distribution for 10485760 samples is 248.23, and randomly would exceed this value 60.75 percent of the times. Arithmetic mean value of data bytes is 127.4847 (127.5 = random). Monte Carlo value for Pi is 3.141642434 (error 0.00 percent). Serial correlation coefficient is -0.000522 (totally uncorrelated = 0.0). ``` 卡方檢定的結果 p 值為 60.75% ，離 5% 遙遠，故此亂數產生器產生的亂數可能是 Uniform Distribution 的。此外 entropy 值為 7.999983 bits per byte, 也是相當高。故二種亂數產生器均能產生品質不錯的亂數。原本想要用 `dieharder` 測試，但跑了很久都沒有結束，所以後來就先提供 `ent` 報告結果。 :::warning 你若對這主題感興趣，可對照閱讀 [Uniting the Linux random-number devices](https://lwn.net/Articles/884875/)，亂數產生器的品質，是近期 Linux 核心的重要開發方針之一。 :notes: jserv ::: --- ## 研讀論文〈Dude, is my code constant time?〉 > [論文](https://eprint.iacr.org/2016/1123.pdf) ### `dudect` 統計原理 `dudect` 會以二種不同類型的資料作為輸入，對待測的程式進行多次時間量測，並分別觀察二種資料作為輸入時其執行時間的分布，進行比較。這二種不同類型的資料分別是： - 固定資料 - 隨機資料若固定輸入資料與隨機輸入資料的時間分布有顯著差異，則可以證明待測的程式其執行時間不是常數時間。反之則其執行時間可能是常數時間（即無法拒絕其為常數時間）執行 `dudect` 分為三步驟： 1. 量測執行時間：對二種不同類型的資料進行多次量測。論文建議不要進行一類量測再進行另外一類，避免數值受環境干擾。建議的方式是：每次隨機任一類資料，進行執行時間量測。 2. 量測後的資料處理： - Cropping 因為執行時，作業系統或硬體中斷都可能打斷正在執行中的程式，這會讓量測不準確。此外資料會偏向較長執行時間一方。故可以透過 Cropping 手法來裁剪執行時間較長的部份。 - Higher-order preprocessing ：尚未理解這部份 4. 進行統計分析：透過統計方法拒絕虛無假說「二種輸入類型執行時間分佈一致」。若成功拒絕此虛無假說，則可說明程式執行不是常數時間。論文中提到二種檢測方式，其中 `dudect` 是用 Welch’s t-test - [Welch’s t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) - Non-parametric tests [這份文件](https://hackmd.io/@RinHizakura/S1PfuxJkv)有其他人寫的論文說明也可供參考 :::info **需要再研讀** 目前還是不懂 Welch’s t-test 和 Student's t-test 的原理，還需要再研究。 ::: ### 目前 `lab0-c` 內 `dudect` 缺陷我發現 `lab0-c` 裡 `dudect` 有許多嚴重錯誤會導致偏差 - 跟據作業說明：「在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無。」經過檢查 `lab0-c` 的程式碼，發現的確沒有 percentile 相關程式。在原始的 oreparaz/dudect 會先計算 percentile 並把極端值除去。故在 `lab-0` 裡沒有正確實作這部份。 - `constants.c` 裡的 `prepare_inputs` 和 `measure` 設計錯誤。 `prepare_inputs` 裡的字串產生程式沒有辦法產生長度一致的字串，因為 randombytes 可能會讓字串中間有 `'\0'` ，此外 `prepare_inputs` 沒有跟據「固定資料」產生固定字串。 - `prepare_inputs`　雖然一開始產生隨機資料放在 `input_data` 中，但這份資料沒有在 `measure` 使用 `dudect` 是直接用 `rdtsc` 指令來計算花費週期數，但計算的結果會包含程式執行到一半可能會被中斷去執行，因為系統上不是只有待測程式在執行。 ### 對 `lab-0` 中 `dudect` 的改進改進方法如下： - 嘗試直接把 [oreparaz/dudect](https://github.com/oreparaz/dudect) 引入 lab0-c 中，解決沒有 percentile 相關程式的問題。且 [oreparaz/dudect](https://github.com/oreparaz/dudect) 內的統計相關程式比較完整。 - 重寫準備輸入資料和待測程式碼（也就是 dudect 會呼叫量測時間的程式），改善上節提到的缺陷。 1. 我直接把 [`dudect.h`](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 引入我的程式，但把它拆成 `dudect.c` 和 `dudect.h` 。 2. 把 `dudect.c` 內的 `randombytes` 和 `randombit` 的函式移除，因此在 `random.c` 就有提供相同的函式了。 3. `dudect` 原本是設計一個 binary 只能有一種測試，因為它會直接呼叫 `prepare_inputs` 和 `do_one_computation` 這二個由使用者實作的函式，但因為 `lab0-c` 有四個待測物，故我把 `dudect_config_t` 內加入 `prepare` 和 `compute` 二個存放 function pointer 欄位，然後把原本呼叫 `prepare_inputs` 和 `do_one_computation` 改成呼叫 `dudect_config_t` 內的 function pointer 。 ```c typedef struct __dudect_config dudect_config_t; typedef void (*dudect_prepare_func_t)(void *priv, dudect_config_t *conf, uint8_t *input_data, uint8_t *classes); typedef uint8_t (*dudect_compute_func_t)(void *priv, size_t size, uint8_t *data); struct __dudect_config { size_t chunk_size; size_t number_measurements; void *priv; dudect_prepare_func_t prepare; dudect_compute_func_t compute; }; ``` 4. 增加 `DUDECT_NOT_ENOUGHT_MEASUREMENTS` 這個狀態。並修改 `report` 在還沒收集足夠資料時，回傳 `DUDECT_NOT_ENOUGHT_MEASUREMENTS` 。而 `dudect_main` 函式中，預設也是在還沒測試時回 `DUDECT_NOT_ENOUGHT_MEASUREMENTS` ```c typedef enum { DUDECT_LEAKAGE_FOUND = 0, DUDECT_NO_LEAKAGE_EVIDENCE_YET, DUDECT_NOT_ENOUGHT_MEASUREMENTS, } dudect_state_t; ``` 5. 實作 [`measure.c`](https://github.com/yanjiew1/lab0-c/blob/master/dudect/measure.c) 和 [`measure.h`](https://github.com/yanjiew1/lab0-c/blob/master/dudect/measure.h) ，放置待測程式及 `dudect_config_t` 的相關設定。並且也實作 `is_##op_const` 巨集用來產生 `is_xxx_const` 函數供 `qtest.c` 內的程式呼叫。此外把 `CHUNK_SIZE` 提升到 640 使測試更準確。因為版面有限，就不把程式碼貼出來，可點連結觀看。 6. 為了測試看看 dudect 是不是能正常偵測時間差異，我故意把固定資料那組測資的字串長度改成 0，確實 dudect 就能發現非常數時間。確認功能正常後就回復原本設定。完成以上步驟後，`make test` 的結果正確回報為執行時間為常數時間。 :::warning 請提交 pull request。 :notes: jserv ::: :::info **可再進一步實驗** 1. 嘗試用 `perf_event_open` 搭配 `config = PERF_COUNT_HW_CPU_CYCLES` 量測時間。看看能不能更能排除待測程式執行時被中斷的執行時間。 2. 嘗試對原本的 `labc-0` 中的 `dudect` 程式做修正，而不是直接引入上游最新版和重寫測試程式。 ::: --- ## 貢獻與程式改進記錄 ### 修正 GitHub Action 問題我檢視我的 repository 的 GitHub Action 有無正常運作時，發現 GitHub Action 在 `Run webfactory/ssh-agent@v0.7.0` 這個步驟時就失敗了。於是我就看了一下原始的 `sysprog21/lab0-c` repository 。裡面的 GitHub Action 可以運作成功。發現原來 `Run webfactory/ssh-agent@v0.7.0` 是用來載入 ssh private key 讓原始 `sysprog21/lab0-c` repository 在沒有 `queue.c` 的解答情況下，能從另一個 private repository 拷貝 `queue.c` 來使用，使原始的 `sysprog21/lab0-c` repository 的 GitHub 在沒解答情況下也可以測試。但是在 fork 之後的 repository ，不會有 ssh private key 。導致在 `Run webfactory/ssh-agent@v0.7.0` 步驟就失敗，以致後面的 `make check` 、 `make test` 等步驟都不會執行。我看了 GitHub 的文件後，發現可以把 GitHub Action 某個步驟標示為即使失敗仍然能繼續執行。故我在 `.github/workflows/main.yml` 裡進行小修正，針對 `webfactory/ssh-agent@v0.7.0` 這個步驟加入 `continue-on-error: true` 來讓它失敗時，也可以往下執行其他 GitHub Action ，使得即便沒有 ssh private key ， GitHub Action 也能有作用。我為此建了一個 [pull request](https://github.com/sysprog21/lab0-c/pull/112) 來提交我的改動，目前已經被 merge 了。 ```diff diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml index 56c7d9e..6ed0b93 100644 --- a/.github/workflows/main.yml +++ b/.github/workflows/main.yml @@ -8,6 +8,7 @@ jobs: steps: - uses: actions/checkout@v3.3.0 - uses: webfactory/ssh-agent@v0.7.0 + continue-on-error: true with: ssh-private-key: ${{ secrets.SSH_PRIVATE_KEY }} - name: install-dependencies ``` ### 其他貢獻 - [#121 Remove `return true;` in `q_quit` function](https://github.com/sysprog21/lab0-c/pull/121) 原本的程式 `q_quit` 一開始就 `return true;` 導致後面記憶體釋放的程式沒有執行，以致於觸發 valgrind memory leak。此 pull request 改善此問題 - [#122 Register `line_atexit` in `linenoise` function](https://github.com/sysprog21/lab0-c/pull/122) `line_atexit` 內會呼叫 `free_history` 釋放記憶體。但在 stdin 非 tty 時， `line_atexit` 不會被註冊，以致於使用檔案輸入指令時，沒辦法釋放 `linenoise` 記憶體，導致 `linenoise` 出現 memory leak 。此 pull request 修正此問題。 - [#127 `Merge do_i(h|t)` into a single function](https://github.com/sysprog21/lab0-c/pull/127) - [#130 Fix warning message in do_descend](https://github.com/sysprog21/lab0-c/pull/130) :::info **TODO** 放 GitHub Pull requests ::: --- ## 其他記錄 ### cppcheck 問題要 commit 時發現在 `report.c` 中的 `static char *msg_name_text[N_MSG]` 變數宣告會觸發 cppcheck 錯誤。原本打算把此行改為 `static char * const msg_name_text[N_MSG]` ，但後來發現 GitHub 有更新新的程式碼加入 `// cppcheck-suppress constVariable` 修正此問題，因此我直接在 GitHub 網頁介面上操作 sync fork 取得更新的程式至自己 fork 出來的 repository 。因為自己只寫了一點點程式，故直接捨棄本地端的 commit，用 GitHub 上新的程式覆寫本地的 repository 。 :::warning 可善用 `git rebase` :notes: jserv > 謝謝老師，我會嘗試練習 `git rebase` :::

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.