# 2024q1 Homework1 (lab0) contributed by < [`teresasa0731`](https://github.com/teresasa0731) > ### Reviewed by `vax-r` * queue.c 的實作並未滿足 `$ make test` 評分系統的所有項目,但卻自稱有完成,同時其他指定項目都沒有完成。 * 沒有提出閱讀論文和素材得到的啟發或洞見 * github commit message 在前幾週提醒要閱讀 [How to Write a Git Commit Message](https://cbea.ms/git-commit/) 後也沒有進行改進,以最新的 [commit d98c644](https://github.com/teresasa0731/lab0-c/commit/d98c644d93ea117d17b19cc3480f88910b9a6912) 為例,你的行為是將 `list_sort` 遷移至其他檔案中以實現更好的檔案管理,你並沒有更改 "modify" 實作當中任何內容,並且也沒有說明為何要進行這項更動, `make the code simpler` 是簡單在什麼部分?原本的檔案結構問題在哪? ### TODO - [x] 完成 queue.[ch] 空缺部份程式碼 - [ ] [改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh) - [ ] 研讀 Linux 核心原始程式碼的 `lib/list_sort.c` - [x] 引入到 lab0-c 專案 - [ ] 比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差 - [ ] [整合網頁伺服器](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-c) - [ ] 在 qtest 提供新的命令 shuffle - [ ] [Fisher–Yates shuffle 演算法](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) - [ ] 切換不同的 PRNG 的實作 - [ ] 研讀論文〈Dude, is my code constant time?〉 - [ ] 解釋 Student's t-distribution 及程式實作的原理。 - [x] oreparaz/dudect 的程式碼具備 percentile 的處理 - [x] 滿足 $ make test 自動評分系統的所有項目。 ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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) i5-1035G1 CPU @ 1.00GHz CPU family: 6 Model: 126 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 5 CPU max MHz: 3600.0000 CPU min MHz: 400.0000 BogoMIPS: 2380.80 ``` >原先使用 Raspberry Pi 開發時意外更動到設定影響原專案,無法挽回只好刪除專案重新fork一次,學到一次教訓,留下紀錄下次必不再犯!(有將相應的開發紀錄的 commit 更新) :::warning 為何在 Raspberry Pi 開發程式 > 因為目前正在學習嵌入式系統,想同步了解相關的硬體擴充資源,故選擇在 Raspberry Pi 安裝 Ubuntu Server 。(請問是否會影響後續課程學習?) > Raspberry Pi 不夠快、主記憶體不夠大,之後編譯 Linux 核心原始程式碼時會太吃力。工欲善其事,必先... > 了解,我會更新我的"工具"! [name=teresasa] ::: ## 專案原始碼追縱 在實作時發現,追溯程式碼所引用的各函式來源與功用是反覆出現的過程,故紀錄對實作時遇到的C程式與標頭檔的理解。 * `queue.[ch]`: Queue implemenation * `list.h`: Linux-style doubly-linked list implementation(useful!) * `harness.[ch]`: The test harness designed to perform stringent testing of code (specifically focusing on memory) ## 佇列實作 `queue.c` 開始之前先將jserv提到強大的巨集 `container_of` 仔細閱讀: [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof) 了解其功能... ### `q_new()` > commit [1616668](https://github.com/teresasa0731/lab0-c/commit/161666897cf05db21b7976304930629c9de7d247) #### 實作方法: * 透過 `malloc` 來配置記憶體後,使用 `list.h` 提供的 `INIT_LIST_HEAD()` 對結構體初始化。 * 參考自 C 語言規格書[7.22.3]:提到**記憶體空間不足以配置時,指標應該回傳 NULL**。 >If the space cannot be allocated, a null pointer is returned. ### `q_free()` > commit [2db229d](https://github.com/teresasa0731/lab0-c/commit/2db229dfd39aa85f943296f6835dff692d17e7cb) 如上一節所提到的,發現此專案提供許多基礎鏈結串列的操作,仔細研究過後選擇以下: #### 實作方法: * 使用 `list.h` 提供的 `list_for_each_entry_safe()` 來"安全的"走訪每一個節點 (e.g.邊界問題) * 使用 `queue.h` 提供的 `q_release_element()` 來釋放節點 :::info :bulb: `free()` vs `test_free()` 追溯程式碼後發現它來自`harness.[ch]`,後者提供了對記憶體區域的一致性檢測、填充機制等,並有回報錯誤的機制,讓測試時期能夠確保任何對記憶體操作的合法性與安全性。 ::: :::danger 注意用語! ::: ### `q_insert_head` & `q_insert_tail` > commit [a7af76a](https://github.com/teresasa0731/lab0-c/commit/a7af76afdc03093fb21d1635f9256738c3f953a8) #### 實作方法: * 除了 head 指標為空時直接回傳外,亦須考慮到 `malloc` 新節點時失敗的情況 * 額外須考量到配置內存並複製字符串時遇到的失敗問題,返回 `NULL` 情況,此時需先釋放記憶體再返回 :::warning 第一次編譯時出現警告 (Dangerous function detected) ,建議將`strcpy()`替換為`strncpy()`,查閱規格書與翻閱提示後,發現因後者允許使用者**指定最大複製的字符數目,從而防止緩衝區溢出,提高安全性**。 * CERN [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 建議 * 參考自 C 語言規格書[7.24.2] >The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1 If copying takes place between objects that overlap, the behavior is undefined. ::: ```diff bool q_insert_head(struct list_head *head, char *s) { ... - strcpy(new_node->value, s); + if (strncpy(new_node->value, s, strlen(s) + 1) == NULL) { + free(new_node->value); + free(new_node); + return false; + } ... } ``` :::info :bulb: **手動配置記憶體與自動配置的差異** 在研究程式碼時意外找到 `strdup()` 函式可以更簡潔的配置記憶體,實現計算、配置記憶體與複製字串於一體,但考量到此函式並不在C語言的標準規範中,還是選擇以標準的`malloc`與`strncpy`實現 ::: :::danger 注意用語! ::: #### 程式碼實作方式更新 在`harness.[ch]`中有提供`test_strdup`,以此專案實作而言,將字串複製改為也是可行方案。 ```c new_node->value = test_strdup(s); ``` #### Discussion 做`q_remove`開始發現了一個問題故回頭討論,如上可看出兩者函式行為雷同,只有差在執行插入動作的'位置',那是不是可以直接用一樣的執行來簡化程式?是否會提高易讀性? 所以我將插入佇列末段`q_insert_tail`所傳入之位置指標更動如下: ```c bool q_insert_tail(struct list_head *head, char *s) { return q_insert_head(head->prev, s); } ``` 再次仔細思考後,以上的確達到簡化程式的目的,但反而出現程式碼的不一致性,故最後還是選擇以原方式實作。 ### `q_remove_head` & `q_remove_tail` > commit [5c15e50](https://github.com/teresasa0731/lab0-c/commit/5c15e5076309673c5b72c6312723d6808b2ee9bd) #### 實作方法: * 除判斷 head 指標外,也考慮到若佇列為空時的情況 * 此處須複製欲刪除之值,在處理字串大小時一開始的寫法會在尾端出現未定義行為;後除了改用`strnlen()`計算緩衝區大小下,可複製的最大長度字串外,亦在末端加上空字符結尾,確保數據儲存形式正確 ```diff element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { ... if (sp) { - size_t cpy_size = (strlen(rm_node->value) < bufsize - 1) ? \ - strlen(rm_node->value) : (bufsize - 1); + size_t str_length = strnlen(rm_node->value, bufsize - 1); strncpy(sp, rm_node->value, str_length); + sp[str_length] = '\0'; } return rm_node; } ``` ### `q_delete_mid` > commit [fcaa9ee](https://github.com/teresasa0731/lab0-c/commit/fcaa9eeaf1b9b9eccee1c2b241e18fc3316d127d) 翻閱相關實作資料後,發現有兩種解法:Fast-slow Pointers 以及 Two Pointers from Both Ends,效能上差異不大,故此次選擇之前未實作過的 Fast-slow Pointers ,將兩個指標以2:1的速度結合 `list_for_each()` 依序前進,直到快指標抵達序列末端或是開頭為止,此時慢指標即為中點。 #### 效能分析與改進 注意到 Fast-slow Pointers 的方法每次須讀取 2+1 共三次記憶體,而若是利用雙向鏈結串列特性使用 Two Pointers from Both Ends ,每次只須讀取兩次記憶體,在時間複雜度同為$O(n/2)$下,後者相較而言可以提昇效率。 ```diff bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; - struct list_head *slow, *fast = head->next->next; - list_for_each (slow, head) { - if (fast == head || fast->next == head) - break; - fast = fast->next->next; + struct list_head *front = head->next, *back = head->prev; + while (front != back && front->next != back) { + front = front->next; + back = back->prev; + } ... ``` ### `q_delete_dup` > commit [c74922f](https://github.com/teresasa0731/lab0-c/commit/c74922f34e01e8ef6ffc48594e814b44aad940f2) #### 實作方法: 透過 `list_for_each_entry_safe` 對當前節點與下一個節點做比較,若相等則刪除當前節點並更改布林值表示檢測到重複值;若遇到不相等情況則依布林值判斷之前是否有出現過重複值,並做相應刪除動作。 :::warning 做`qtest`測試時出現錯誤:Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped) 檢查後發現應該獨立判斷迴圈截止情況(回到佇列起點`head`),避免在處理佇列尾端處理遇到錯誤,故最後修改如下 ::: ```c bool q_delete_dup(struct list_head *head) { ... list_for_each_entry_safe (cur, next, head, list) { if (&next->list == head) { if (found) { list_del(&cur->list); q_release_element(cur); } return true; } if (strcmp(cur->value, next->value) == 0) { list_del(&cur->list); q_release_element(cur); found = true; } else { ... } ``` ### `q_swap` > commit [867bab4](https://github.com/teresasa0731/lab0-c/commit/867bab46d2b974a653421a0b628a6e2b034dede2) 根據題目將兩兩相鄰的節點做交換,原本思考以暴力法做交換,但其涉及到的節點與指標太廣,故再次從`list.h`尋找可用函式。 #### 實作方法: 最後選擇以`list_for_each()`走訪節點,並且透過`list_move()`在給定佇列前端(此處為 `node->next`)插入節點,此函式本質就是呼叫 `list_del` 和 `list_add`,來確保迴圈指標位置的正確性。 ### `q_reverse` > commit [55382fa](https://github.com/teresasa0731/lab0-c/commit/55382faa716d40b2d80f86c78696e8befe28914c) #### 實作方法: 原想法:以`list_for_each_safe()`走訪節點,利用`list_move()`將其依序插入至`head`前面。 更新:在測試時才發現沒有仔細處理到頭尾連接的部份,故更改為較直覺的方法,逐步更改節點,並在最後將頭尾串連。 ```diff void q_reverse(struct list_head *head) { ... - struct list_head *cur, *next; - list_for_each_safe (cur, next, head) - list_move(cur, head); + struct list_head *node, *safe; + list_for_each_safe (node, safe, head) { + node->next = node->prev; + node->prev = safe; + } + node->next = node->prev; + node->prev = safe; return; } ``` ### `q_reverseK` > commit [55382fa](https://github.com/teresasa0731/lab0-c/commit/55382faa716d40b2d80f86c78696e8befe28914c) #### 實作方法: 原想法:基於`q_reverse`,把佇列分組後每一組單獨做反轉,每組完成後將新的 `head` 指向下一組的開頭;題目定義最後未成組不須進行反轉(即組內節點數小於 k ),故使用一變數 `group` 紀錄組數。 更新:在測試時一樣遇到前提及的頭尾相接問題,故在原本的分組操作上,改成以`list_cut_position()`將各組逐一分離並呼叫`q_reverse()`反轉後,再串接到`new_head`,完成全部組別的反轉後再接回。 ```diff @@ -222,23 +225,25 @@ void q_reverseK(struct list_head *head, int k) if (!head) return; - int group = q_size(head) / k, cnt = 0; - struct list_head *cur, *next; - list_for_each_safe (cur, next, head) { - if (group) { - list_move(cur, head); - cnt++; - } else { - break; - } - if (cnt == k) { - group--; - cnt = 0; - head = next; + int group = q_size(head) / k; + struct list_head *cut; + + LIST_HEAD(tmp); + LIST_HEAD(new_head); + + while (group) { + int cnt = k; + list_for_each (cut, head) { + if (cnt) + break; + cnt--; } + list_cut_position(&tmp, head, cut->prev); + q_reverse(&tmp); + list_splice_tail_init(&tmp, &new_head); + group--; } - - return; + list_splice_init(&new_head, head); } ``` :::danger 使用 `diff -u` 或 `git diff` 來產生程式碼之間的變異,不要憑感覺填入,注意位移量。 ::: ### `q_sort` > commit [8008d3a](https://github.com/teresasa0731/lab0-c/commit/8008d3a2f92045535aca373abd6f7bb479b5bea5) 在參考[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 提到的四種實作方法後,考量到 merge sort 時間複雜度為 $O(nlogn)$ ,平均而言表現較佳,加上只需要修改指標而不需要大量的數據移動,故最後選擇 merge sort 。 :::danger 注意用語。 ::: #### 實作方法: :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `),以清晰、明確,且流暢的漢語書寫。 ::: `q_sort()` 先將鏈結串列頭尾斷開後,開始執行 merge sort `mergeSort()` 內先以快慢指標找出中點(切割點)後斷開,遞迴傳入排序函式進行合併 `mergeSortedList()` 分別比較左右串列大小,以遞增排序,最後回傳排序好的部份串列 ```diff - if (R) - *ptr = R; - else - *ptr = L; + *ptr = (struct list_head *) ((uintptr_t) R | (uintptr_t) L); ``` > 此處透過 ChatGPT 的潤飾,將原本須透過 if-else 判斷式來確認非空集合的程式碼改進。 回到 `q_sort()` 重建雙向鏈結串列 ### `q_ascend` & `q_descend` > commit [f51d853](https://github.com/teresasa0731/lab0-c/commit/f51d85326549785c0d359977d8601fb522f47679) 一開始沒有看懂題意,以為要實作非遞增序列,後來使用`qtest`測試時才發現是"若該節點右邊有小於/大於的節點,則刪除該節點",而非 ascend/descend 的字面含意。 #### 實作方法: (以 ascend 為例)從佇列末端回頭逐一比對,若遇到後節點沒有大於前節點的情況則刪除該前節點,並重新將`front`導向至前一個節點。 ```c int q_ascend(struct list_head *head) { ... while (&front->list != head) { if (strcmp(back->value, front->value) > 0) { front = list_entry(front->list.prev, element_t, list); back = list_entry(back->list.prev, element_t, list); } else { list_del(&front->list); free(front->value); free(front); front = list_entry(back->list.prev, element_t, list); } } return q_size(head); } ``` #### 改進方式思考 :::danger - [ ] traverse (動詞) 和 traversal (名詞) 根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse ): (作為及物動詞和不及物動詞都有類似的意思,以下列出作為及物動詞的寓意) * to pass or move over, along, or through. * to go to and fro over or along. 其實這意思很好懂,就像我們「走過」/「穿越」校園一般,於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」,但這裡卻沒有必要「所有」的範圍:英語的 "move over/through" 用於某個區域時,根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」,就會導致「超譯」,也就是跳脫「直譯」和「意譯」。 當我們回頭看 "traverse" 所在的技術描述內容,例如 "traverse every node",若翻譯為「遍歷每個節點」,那麼既然都「遍」(意即「全面」、「到處」),又何來「每個」節點呢?於是,合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪?在 "traverse every node" 的應用場景中,可能是我們嘗試在鏈結串列尋找特定的節點內含的資料,一旦找到就停止,或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ,並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中,要區分「意圖」(intention) 和「實際作用」(reaction),濫用「遍歷」會使得語意不清,從而難以推測英語原文的訴求。 還有個更重要的原因是,「遍歷」這詞已在理工領域存在,且廣泛使用,即「遍歷理論」(Ergodic theory),後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換,由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。 在統計學中,若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣),其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時,此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設,對時間平均的統計方式及結果,便可由對系集的平均及統計方式得到。在一般物理系統中,尤其在統計力學範圖中,均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析,亦是採用此假設。 遍歷 (Ergodic) 源於以下二個希臘詞: * ergon (對應英語的 work) * odos (對應英語的 path 或 way) 最初這是由奧地利物理學家波茲曼 ([Ludwig Boltzmann](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念,其一廣為人知的結果是:在經過長時間後,時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色,在隨機分析領域亦然。 因此,若貿然將 traverse 翻譯為「遍歷」,一來語意不清,二來增加和理工多項領域專業人員的溝通成本,實在得不償失。 $\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) ::: `list.h` 目前未提供類似 `list_each_entry_back_safe` 從尾部( `head -> prev` )逆向走訪的 API。對於雙向的鏈節串列而言,現有的 `list_each_entry_safe` 函式未完全發揮其"雙向"特性。若能夠新增相應的函式,可能有助於提供更安全的錯誤檢查機制。 :::danger 既然本處的鏈結串列具備環狀且雙向的特性,那「反向」到底是什麼?工程人員說話要精準。 ::: ### `q_merge` > commit [f809018](https://github.com/teresasa0731/lab0-c/commit/f8090187ad2d0417ee249141092bedf74713ff0a) 此函式功能即為 "merge k sorted lists",不同於 merge sort 所需要做 divide-and-conquer 的部份,故透過兩兩一組合併,並撰寫一 `mergeTwoList()`函式供呼叫。 引用 `queue_contex_t` 作為每次迭代的單位,其結構體定義如下: ```c typedef struct { struct list_head *q; struct list_head chain; int size; int id; } queue_contex_t; ``` #### 實作方法: 1. 主函式 `q_merge()` 以兩兩相鄰的佇列合併的模式,將其傳入`mergeTwoList()`合併,其 for 迴圈的次數將為$log(k)$次 :bulb:注意須額外考量若為奇數組,則須多一次操作將最後一組合併 2. `mergeTwoList()`中僅須簡單將兩個傳入串列依指定順序合併即可,此處須注意最後須將`tmp`重新移動回串列尾部(此處選擇`l1`作為有效串列) :::warning :question: 此處若回到主函式時未加上以下操作,就將兩個指標往後移動,會導致`qtest`測試答案錯誤但編譯通過,目前尚未找出原因。 ```c list_move_tail(&l2->chain, head); ``` >想法:此時的`l2`經過兩佇列合併後應為一指向為空的指標,若是不與主佇列`l1`做合併,為何會造成答案錯誤呢? ::: :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `),以清晰、明確,且流暢的漢語書寫。 ::: --- ## 引入 list_sort.[ch] ### 程式碼更動細節 > 完整異動 [commit c62e45d](https://github.com/teresasa0731/lab0-c/commit/c62e45d2e1e268ebe7d2b69bce0b22a43316fad3) #### `Makefile` #### `qtest.c` 比照 `do_sort()` 來新增 `do_lsort()` 以執行從 linux 核心引入的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 。 #### --- ## 研讀論文並改進 dudect > [研讀筆記](https://hackmd.io/@teresasa/linux2024-lab0#%E3%80%88Dude-is-my-code-constant-time%E3%80%89) dudect用於檢查函數是否以恆定時間運行,其使用Welch's t-test 的統計方法,透過比較兩組樣本平均值,來確定函數是否在不同輸入下都以相同的時間運行。 ### 新增 percentile 處理 > 詳細更動見 [commit 782eaee](https://github.com/teresasa0731/lab0-c/commit/782eaee8a5a8bd031df48316d4ec19778fb370c0) 經過 `vax-r` 的 review 後才發現,我只有本地的`make test`通過而已,原來第17筆測試所使用的工具 dudect 還有需要更改的地方。 將論文的程式碼與本次專題的 dudect 實作比較後,發現缺少 percentile 相關處理,故將 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 中相關的程式碼修改後引入 lab0-c ,終於拿到 :100: &星之卡比了~ * 新增`prepare_percentiles()` 預處理,以排除佔時較長的數據點 * 論文在`update_statistics` 中,省去了前面 10 筆的資料,將 lab0-c 仿造修改。 --- ## 整合網頁伺服器 --- ## 亂數生成 根據教材,先在兩個終端機分別輸入命令: ##### terminal-1 ```cmd $ ./qtest cmd> web listen on port 9999, fd is 3 cmd> l = [] cmd> l = [a] cmd> l = [b a] cmd> l = [sort b a] cmd> l = [a b sort] cmd> Unknown command '.' cmd> Unknown command 'favicon.ico' ``` ##### termianl-2 ```cmd $ ./qtest cmd> Freeing queue $ curl 127.0.0.1:9999/new l = [] $ curl 127.0.0.1:9999/ih/a l = [a] $ curl 127.0.0.1:9999/ih/b l = [b a] $ curl 127.0.0.1:9999/ih/sort l = [sort b a] $ curl 127.0.0.1:9999/sort l = [a b sort] ``` 於此同時開啟網頁在 url bar 輸入`http://127.0.0.1:9999` 後,可以看到 termianl-1 出現訊息 ```cmd cmd> Unknown command '.' cmd> Unknown command 'favicon.ico' ``` ### 在 qtest 提供新的命令 `shuffle`