# 2024q1 Homework1 (lab0) contributed by < [`SuNsHiNe-75`](https://github.com/SuNsHiNe-75) > ### Reviewed by `teresasa0731` 1. 關於函式的參考資料盡量以原始來源/官方為主（如`strncpy` 可以查閱 [strncpy](https://en.cppreference.com/w/c/string/byte/strncpy)） ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 Copyright (C) 2021 Free Software Foundation, Inc. $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 45 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz CPU family: 6 Model: 158 Thread(s) per core: 1 Core(s) per socket: 1 Socket(s): 4 Stepping: 10 BogoMIPS: 5184.00 Caches (sum of all): L1d: 128 KiB (4 instances) L1i: 128 KiB (4 instances) L2: 1 MiB (4 instances) L3: 48 MiB (4 instances) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-3 ``` ## 針對佇列操作的程式碼實作 ### `q_new` > commit [65ec12a](https://github.com/SuNsHiNe-75/lab0-c/commit/65ec12ae1116193a9b128e6dcbb7a61e415f61c6)。 :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。 > 收到，<s>已修改</s>。 > 不要急著說「已修改」，你的行文真的做到「清晰、明確，且流暢」嗎？這是很困難的事，值得我們反覆推敲。 ::: 此函式的定義為－建立新的「空」佇列。 我的初步想法是，配置一塊記憶體，將所有指標都指向此「記憶體」。注意其資料結構為環狀雙向鏈結串列。 實作上，我使用 `malloc` 來配置記憶體空間，檢查空間是否配置成功，若配置失敗則回傳 NULL。最後透過 [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 中的 `INIT_LIST_HEAD` API 來初始化 `list_head`。 > 不能用 `calloc`，其會配置連續記憶體空間，通常為陣列應用。 > Description of `INIT_LIST_HEAD`：Initializes the list_head to point to itself. If it is a list header, the result is an empty list. ### `q_free` > commit [bcb223f](https://github.com/SuNsHiNe-75/lab0-c/commit/bcb223f44195c60948234ddaff2cd9beb8927cae)。 此函式的定義為－釋放佇列所佔用的記憶體，若 head 原已指向 NULL，則無影響。 我的初步想法是，走訪所有節點（`list_for_each`），一個一個釋放（`free`）其佔用的記憶體。 然而，後來細讀 [list.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/list.h) 後，發現若使用 `list_for_each` 來釋放記憶體會有問題，原因為「其沒有紀錄下一個節點的資訊」，其原文註解也提到： > "The nodes and the head of the list must be kept unmodified while iterating through it. Any modifications to the the list will cause undefined behavior." 因此需另尋走訪所有節點的方法。 實作上，改用 `list_for_each_entry_safe` 來走訪節點，循序釋放記憶體空間。另需使用 [queue.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/queue.h) 中定義的 `element_t` 結構體，來協助實作 `safe` 及 `entry` 的相關操作。 > `list_for_each_entry_safe` 的介紹提到了 "...**allow deletes**" 及 "The current node (iterator) is **allowed to be removed** from the list."，是因為多了 `safe` 指標來儲存下一個 `entry` 的資料。 ```diff // 240226 ... + q_release_element(entry); -if (entry->value) { - free(entry->value); - } - free(entry); ... ``` > 用巨集 `q_release_element` 來釋放記憶體即可。 ```diff // 240226 ... -if (!(l && !list_empty(l))) +if (!l) return; ... ``` > 空佇列也會佔記憶體空間！因此也要釋放掉。 ### `q_insert_head` > commit [bea9db3](https://github.com/SuNsHiNe-75/lab0-c/commit/bea9db3a304c6055243ef67fc1e5011bc13d3429)。 此函式的定義為，在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)，若成功則回傳 "true"；否則表配置失敗或佇列為空，回傳 "false"。 我的初步想法是，配置一記憶體空間，先將此新節點的 next 指到舊 head 節點；將此新節點的 prev 指到舊 head 節點的 prev 所指之節點；變更舊 head 節點的 prev 指向新節點；將舊 head 節點的 prev 所指之節點的 next 指向新節點，最後將 head 指標指向此新節點，並將字串丟入新節點即可。 > 後來發現 [list.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/list.h) 中的 `list_add` 已實作此過程。 程式實作上，先用 `malloc` 去配置一 element_t 的空間大小，使用 string.h 中的 [`strdup`](https://man7.org/linux/man-pages/man3/strdup.3.html) 函式，將字串內容複製進新節點，最後使用 `list_add`將新節點插入佇列頭。 > 呼叫 `strdup` 時，其會自動配置該字串大小的記憶體空間，再將該字串複製進去此記憶體之位址，最後回傳的是該「位址」。要注意的是，需使用 `free` 來釋放。 :::danger 關於 `strdup`，應援引 Linux man-page 作為第一手材料，也就是說，該提及 https://man7.org/linux/man-pages/ 的超連結。 > 收到，已更改。 ::: > 240226，Test 11 有錯。 ```diff // 240227 ... +if (!new->value) { + free(new); + return false; +} ... ``` > 注意 s 為 NULL（沒傳入資料），會導致 new->value 也為 NULL，需要直接釋放記憶體並中斷執行！ :::danger 改進你的漢語表達，工程人員說話要精準，什麼叫做「沒東西」和「沒吃到資料」？ > 收到。 ::: ### `q_insert_tail` > commit [bea9db3](https://github.com/SuNsHiNe-75/lab0-c/commit/bea9db3a304c6055243ef67fc1e5011bc13d3429)。 此函式的定義為，在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)，若成功則回傳 "true"；否則表配置失敗或佇列為空，回傳 "false"。 我的初步實作概念同 `q_insert_head`。 實作上，概念同 `q_insert_head`，差別在要用 `list_add_tail` 將新節點插到佇列尾。 > 240226，Test 12 有錯。 ```diff // 240227 ... +if (!new->value) { + free(new); + return false; +} ... ``` > 注意 s 為 NULL（沒傳入資料），會導致 new->value 也為 NULL，需要直接釋放記憶體並中斷執行！ ### `q_remove_head` > commit [79df68a](https://github.com/SuNsHiNe-75/lab0-c/commit/79df68a54d2af2d515b52f6514f55e8c5db0b010)。 此函式的定義為，在佇列開頭 (head) 移去 (remove) 給定的節點，與 delete 不同的是，remove 只需 "unlink" 該節點，用於該元素及字串的空間不能被釋放。另外，若 sp 為 non-NULL 且有元素被 remove，要將該被 removed 的字串複製進 `*sp`。 一開始我想的是，要先把資料先複製過去，否則調整完指標後，會抓不到該資料，之後就先調整「舊 head 節點的前一個節點」的 next 指標，再調整「舊 head 節點的下一個節點」的 prev 指標，最後將 head 指標指到其下一個節點成為 head，即可進一步將 links 斷乾淨。 > [list.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/list.h) 中有巨集 `list_del` 可執行 unlink！ 實作上，先用 [list.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/list.h) 中的 `list_first_entry` 去找要被移除的頭節點，並用 string.h 的 [`strncpy`](https://skylinelimit.blogspot.com/2018/02/c-2.html) 來複製字串進 sp，最後用 `list_del` 來 unlink 即可。 > 為何不用 `strcpy`？ > 因會有 "Buffer overflow" 的問題，詳細可參考上方`strncpy` 之超連結。 ```diff // 240226 ... +sp[bufsize-1] = '\0'; ... ``` > 否則若 `strncpy` 兩字串的長度不同，後面會有多餘的字串殘留。 > 240227，Test 17 有錯：`Segmentation fault occurred. You dereferenced a NULL or invalid pointer.` ```diff // 240227 ... + if (sp != NULL) { strncpy(sp, rmv_element->value, bufsize); sp[bufsize - 1] = '\0'; + } ... ``` > 要看一下 sp 到底有沒有資料，沒有的話就不用複製了。 > Test 17 終於過了！ ### `q_remove_tail` > commit [79df68a](https://github.com/SuNsHiNe-75/lab0-c/commit/79df68a54d2af2d515b52f6514f55e8c5db0b010)。 此函式的定義為，在佇列尾端 (tail) 移去 (remove) 給定的節點。 想法概念同 `q_remove_head`。 實作方式同 `q_remove_head`，差別在要用 `list_last_entry`來找要被移除的尾節點。 ```diff // 240226 ... +sp[bufsize-1] = '\0'; ... ``` > 否則若 `strncpy` 兩字串的長度不同，後面會有多餘的字串殘留。 ```diff // 240227 ... + if (sp != NULL) { strncpy(sp, rmv_element->value, bufsize); sp[bufsize - 1] = '\0'; + } ... ``` > 要看一下 sp 到底有沒有資料，沒有的話就不用複製了。 > Test 17 終於過了！ ### `q_size` > commit [75b9ff4](https://github.com/SuNsHiNe-75/lab0-c/commit/75b9ff492de7dca5e024fa38054ad099170b398b)。 此函式的定義為，計算目前佇列的節點總量，若佇列為空或 NULL 的話，回傳 0。 初步的想法是，使用一指標從 head 開始走訪所有節點，設定一變數紀錄節點總數，走回 head 時結束並回傳總數。 若要判斷佇列是否為空，可用 `list_empty` 巨集。這裡走訪節點用 `list_for_each` 即可，畢竟沒有要修改節點。搭配 cnt 變數計算節點總數。 ### `q_delete_mid` > commit [063c865](https://github.com/SuNsHiNe-75/lab0-c/commit/063c865f2d4b0eee8a86c0faaaf53007bcd1a8b3)。 移走佇列中間的節點。設佇列長度為 n，則中間的節點即為 $\lfloor\dfrac{n}{2}\rfloor$ 索引的點（假設索引從 0 開始）。成功則回傳 "true"；佇列為空或 NULL 則回傳 "false"。 > 詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)。 :::danger 何謂「LeetCode 解法」？你打開 LeetCode 網站，就會出現「解法」嗎？ > 確實闡述得不好，之後注意！ ::: <s>與 LeetCode 解法類似</s> ，先走訪整條 List，數長度 = n；算 $\lfloor \frac n 2 \rfloor$ 來抓中間節點，調整其「前/後節點」的指標，最後釋放其記憶體。 函式實作上，呼叫先前已定義好的 `q_size` 來得知節點總數，使用 `list_for_each_entry_safe` 來走訪所有節點，若找到中間節點時，透過 `list_del` 調整 link，並使用 `free` 將中間節點的資料及記憶體位置釋放掉。 > 有一些更好的解法是應用 [快/慢指標（Fast-slow Pointers）](https://hackmd.io/@Hsins/fast-slow-pointers)或是頭尾設兩個指標來互相接近以尋找中間節點，能進一步降低時間複雜度。 > <s>我目前的解法比較土法煉鋼。</s> > 明確闡述現有作法的缺失，不要濫用成語。 :notes: jserv ### `q_delete_dup` > commit [17ba18c](https://github.com/SuNsHiNe-75/lab0-c/commit/17ba18c083f6b092cb6a6daf3ce5813520dc2edf)。 此函式的定義為，在已經排序的狀況，移走佇列中具備重複內容的節點。只能留「資料不重複」的節點。 > 詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/)。 解完 LeetCode 的題目再來實作此函式－不另外先建一個 Dummy node 了；走訪所有節點，透過兩個「一前一後的指標」來檢查資料有無重複，若發現重複了，則直接斷掉目前的節點並釋放其記憶體。 使用 `list_for_each_entry_safe` 來走訪節點，因 `entry` 即當前節點；`safe` 即下一個節點，所以有利於我們執行比較。而字串的比較則使用 string.h 中的 `strcmp` 即可。值得注意的是，還需一變數 `dup` 來紀錄是否重複。 > 後來發現 [queue.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/queue.h) 有 `q_release_element` 的巨集可以協助釋放記憶體。 ### `q_swap` > commit [8d3ad73](https://github.com/SuNsHiNe-75/lab0-c/commit/8d3ad73265f81f4f6a3eb8a75aae5556ca91aca2)。 交換佇列中鄰近的節點。 > 詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/description/)。 LeetCode 的題目談到不能動到節點的資料，故還是只能動指標。那大致作法就是要去找看看有無已定義好的巨集，以更方便地執行兩個節點間的指標調整。 參照 [fewletter](https://hackmd.io/@fewletter/lab0-c) 的 `q_swap` 圖片分析，可以透過 [list.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/list.h) 提供的 `list_del` 及 `list_add` 巨集來迭代調整 links，簡潔有力。 > 之後又發現此二巨集已被整合為 `list_move` 巨集，但需注意參數的使用。 ### `q_reverse` > commit [73c77b2](https://github.com/SuNsHiNe-75/lab0-c/commit/73c77b2783014fdbd0b4c990fa4de16e87cead6c)。 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點。 想法是走訪所有節點，一個一個調整其指標，最後移動 head 指標即可。 即透過 `list_move` 逐一將節點加到佇列頭即可。 > 注意不能用 `list_for_each_entry` 來走訪節點，因其不允許當前節點的修改。 ### `q_reverseK` > commit [abd5209](https://github.com/SuNsHiNe-75/lab0-c/commit/abd5209084bbddc3858e23419aba0471242ce718)。 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列。 > 詳見 [LeetCode 25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/description/) (Hard)。 用兩個指標指在「要反轉的佇列頭」及「要反轉的佇列尾」，呼叫 `q_reverse` 來反轉此段佇列，以此類推。 > 問題：`q_reverse` 是固定 head 的，在呼叫它之前，要先調整先前的兩個指標所指向節點的 next 與 prev，使其成為一 Circular Linked List。 可用 `list_cut_position` 將該段要反轉的佇列先丟到另一空佇列（透過 `LIST_HEAD`），再行 `q_reverse` 以解決要調整指標的繁瑣問題（如此，head 指標也不用動來動去）。反轉好的佇列段先使用 `list_splice_tail_init` 暫存到另一個佇列的後端，待 head 佇列清空後，再將整個暫存佇列以 `list_splice_init` 丟回 head 佇列。 > 截至 240227，該功能是最後一個寫的，測試的分數為 **94** 分。 ```shell= Probably constant time --- trace-17-complexity 5/5 --- TOTAL 94/100 make: *** [Makefile:60: test] Error 1 ss75@ss75:~/linux2024/lab0-c$ ``` :::danger 文字訊息請避免用圖片來表示，否則不好搜尋和分類 > 收到。 ::: ### `q_sort` > commit [3391913](https://github.com/SuNsHiNe-75/lab0-c/commit/339191328253b78bc9da36dc9c4bfce2ade50aa7)。 以遞增順序來排序鏈結串列的節點。若佇列為空或 NULL，此排序無影響；若佇列只有一個元素，無事發生。透過傳入的 `Descend` 參數來判斷要遞增/遞減排序。 > 可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法。 > （Bubble sort、Insertion sort、Selection sort、Merge sort） 鑒於上文提到的前三種排序法的時間複雜度的 Average case 皆要 $O(n^2)$；因此選擇 Merge sort（時間複雜度 Average case 僅為 $O(nlog_2n)$）。[上文](https://npes87184.github.io/2015-09-12-linkedListSort/) 的 Merge sort 實作架構是透過遞迴，其中使用快慢指標來分割串列（slow 抓到串列中間節點後，fast = slow->next 來當右邊串列的新 head，以此類推）；另撰寫一 `merge` 遞迴地將分割好的串列逐步 merge 起來。 > 要注意的是，該 Merge sort 實作的是遞增順序的串列。 在 `q_sort`，分割串列的部分透過快慢指標協助實作－找到中間節點後，先用 `LIST_HEAD` 建兩個 next 與 prev 都指向自己的 head，接著透過 `list_splice_tail_init` 及 `list_cut_position` 將原串列拆成兩條串列（函式內都將指標調整好了）。接著即可遞迴執行 `q_sort`，最後合併。決定升序/降序的地方在 `merge2list` 函式，值得注意的是用 `strcmp` 比較數值大小時，要小心誰比較小的時候先放入 list 的順序，可用 `list_move_tail` 將節點放到尾端。最後若左/右某邊的 list 已清空，剩下的 list 即是以排好且比已完成的 list 都還大的數，直接透過 `list_splice_tail_init` 將整串 list 插到尾端即完成排序。 > 參考 [@itiscaleb](https://hackmd.io/@ItisCaleb/linux2023-lab0#q_sort) 的想法。 > qtest 中測試 `sort` 時，會報錯：`Segmentation fault (core dumped)`！報錯原因待釐清... ```diff //240226 void merge2list(struct list_head *l_head, struct list_head *r_head, struct list_head *head) { ... + if (strcmp(ele1->value, ele2->value) <= 0) + list_move_tail(l_head->next, head); + else + list_move_tail(r_head->next, head); - int cmp_result; - if (descend) - cmp_result = strcmp(ele1->value, ele2->value); - else - cmp_result = strcmp(ele2->value, ele1->value); - if ((descend && cmp_result >= 0) || (!descend && cmp_result <= 0)) - list_move_tail(l_head->next, head); - else - list_move_tail(r_head->next, head); ... } void q_sort(struct list_head *head, bool descend) { + if (!head || list_empty(head) || list_is_singular(head)) - if (!head || list_empty(head)) return; ... + if (descend) + q_reverse(head); } ``` > 找出問題為無判斷「是否為單元素串列」，此種串列不能執行 `q_sort` 遞迴。 > 修改遞減順序的實作方法，原程式單純實作遞增順序，若判斷為 descend，則用 `q_reverse` 反轉即可。 ```diff //240227 +void q_sort_asc(struct list_head *head) +{ + ... +} /* Sort elements of queue in ascending/descending order */ void q_sort(struct list_head *head, bool descend) { + q_sort_asc(head); if (descend) q_reverse(head); } ``` > 錯誤執行 `q_reverse`，因此先包裝前置 ascending 演算法，不讓 `q_reverse` 也進去遞迴。 ### `q_ascend` > commit [22ef866](https://github.com/SuNsHiNe-75/lab0-c/commit/22ef86656a58e338e3179a09c445363fc5bf6b1d)。 以遞增順序來排序鏈結串列的節點。最後要回傳佇列長度。 實作概念同 `q_descend`，差別在要調整字串比較大小於方向。 ### `q_descend` > commit [b181b2e](https://github.com/SuNsHiNe-75/lab0-c/commit/b181b2efb144da017098b90e7b36a7cb18761bcf)。 以遞減順序來排序鏈結串列的節點。最後要回傳佇列長度。 > 參閱 [LeetCode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/description/)。 :::danger 標註你參考標的的人名或代稱，不要說「別人」 > 收到。 ::: > 參考 [Not In My Back Yard 網友的 LeetCode 解題思維](https://home.gamer.com.tw/artwork.php?sn=5818544)。 簡單來說：每個節點往右邊所有節點看，若有任一比自己的值還大的節點值，則該節點要被刪除。將串列反轉，是因為由右往左走訪單向連結串列有其不方便性，且該題也能視為「由右往左來數的嚴格遞增串列」。在實作上，就是以由右往左的方式移除較小的元素，最後再反轉回來即為所求。 :::danger 何謂「白話來說」？難到原本文章用文言文書寫嗎？ > 用詞不佳，會再注意。 ::: 由尾端往後找，找到下一個更大的節點值後，替換目前最大節點值，並將中間的節點全部刪除掉。最後即會留下一嚴格遞減串列。 > 在作答 LeetCode 題目的當下，誤解題目意思，因此想出的方法都會 WA，故尋求網友大神的解答紀錄，以便學習。閱讀理解完後，才過來想 `q_descend` 的實作。理解題目的能力有待加強。 實作原理其實就是在實作反方向的 `list_for_each_entry_safe` 的概念。字串數值的比較，需使用 [`strcmp`](https://www.ibm.com/docs/zh-tw/uax?topic=functions-strcmp) 函式來實作。最後可直接用先前定義的 `q_size` 來回傳節點數。 ### `q_merge` > commit [e930c65](https://github.com/SuNsHiNe-75/lab0-c/commit/e930c654918bde51410f15b7992e43f240a6a4ce)。 合併所有已排序的佇列，並合而為一個新的已排序佇列。 > 詳見 [LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/description/) (Hard)。 > 240310 回頭寫完此最後一函式，測試的分數已 **100** 分。 ```shell= Probably constant time Probably constant time Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 100/100 ``` --- ## 使用 `select` 改善 Web 與 Linenoise 之衝突問題 ### linenoise 理解 :::danger ChatGPT 適合用來改進你的書寫內容，但不該拿來查詢專業議題。 > 了解。 ::: 它是一個簡單的 C 函式庫，用來處理命令列單行輸入。其還支援自動補齊命令和命令歷史記錄功能，間接讓命令列應用程式的開發變得更便利。此外，其還支援跨平台使用，包括 Linux、macOS 和 Windows 等作業系統。 套用到我們現時的使用場景，簡單來說，我們在 Linux 終端命令列進行命令操作時，會一直使用到 linenoise 函式庫，最常見的就是「命令的輸入」、「按 Tab 鍵自動補全檔案名稱」與「按上/下箭頭鍵來查找曾經輸入過的命令」等...... :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。 > 收到。 ::: linenoise.c 中，**相關重要函式之深入理解**： - `*linenoise`：linenoise 函式庫的主要 API。它首先透過檢查「Stupid terminals 的黑名單」來==檢查終端是否具有基本功能==。根據結果，擇一執行下二動作： 1. 呼叫「行編輯函式」（即下方 `line_edit`） 2. 使用一個 dummy `fgets` 函式，確保在最不利的情況下，使用者還是能輸入命令。 - `line_raw`：這個函式==使用「設置為 raw mode 的 STDIN 檔案描述子」來呼叫行編輯函式 `line_edit`==。 > Raw mode：輸入的資料將不會被緩衝，而是直接傳遞給應用程序，同時輸出的資料會直接發送到終端，而不經過作業系統的進一步處理。 > STDIN_FILENO：即 stdin 的檔案描述子，其值為 0。 > STDOUT_FILENO：即 stdout 的檔案描述子，其值為 1。 > 呼叫 `line_edit(STDIN_FILENO, STDOUT_FILENO, buf, buflen, prompt)`。 - `line_edit`：行編輯能力的核心。它期望 'fd' 已經處於 "raw mode"，這樣每按一個鍵都會立即回傳給 `read` 函式。當使用者輸入 enter 或 ctrl+d 時，「結果字串」將被放入 'buf' 中，最後回傳「當前緩衝區的長度」。 > `write(l.ofd, prompt, l.plen)` 參考 [write(2)](https://man7.org/linux/man-pages/man2/write.2.html)，其將資料寫入到檔案描述子對應的檔案，可在終端機代替 printf 輸出對應 prompt。 > `read(l.ifd, &c, 1)` 參考 [read(2)](https://man7.org/linux/man-pages/man2/read.2.html)，其在檔案描述子對應的檔案中讀取資料，可取代 scanf 在命令列讀取資料。 ### `select` 理解 :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。 > 收到。 ::: 閱讀 [select(2)](https://man7.org/linux/man-pages/man2/select.2.html) 後，理解如下。 `select` 允許程式==監視多個檔案描述子，等待其中一個或多個檔案描述子「就緒」，以進行 I/O 操作==。如果可以執行相應的 I/O 操作（例如，`read(2)` 或足夠小的 `write(2)`）而不會被阻擋，則檔案描述子就是「就緒」的狀態。 **fd_set** 是一種能夠==表示一組檔案描述子的結構類型==。 **File descriptor sets** 相關－`select` 函式的主要參數是 ==「三個檔案描述子」的集合==（用 fd_set 宣告），允許呼叫者等待「特定檔案描述子集合上的三種事件」。如果不需要監視某種事件，可以將該 fd_set 參數設成 NULL。 - `FD_ZERO`：該巨集**移除所有檔案描述子**。可初始化檔案描述子集合。 - `FD_SET`：該巨集**將檔案描述子 fd 添加到集合中**。 - `FD_CLR`：該巨集**從集合中移除檔案描述子 fd**。 - `FD_ISSET`：該巨集用來**測試檔案描述子是否仍存在於集合中**。若存在，回傳非零值；如果不存在，則回傳 0。 而 `select` 的參數理解如下。 - `readfds`：此集合中的檔案描述子用於**檢查它們是否「準備好進行讀取（讀取時不會被阻擋）」**。另外，檔案描述子在達到檔案結尾時也會「就緒」。在 `select` 回傳後，`readfds` 會**清除所有「未準備好被讀取」的檔案描述子**。 - `writefds`：此集合中的檔案描述子用於**檢查它們是否「準備好進行寫入（寫入時不會被阻擋）」**。但是，即使檔案描述子顯示為可寫入，一個 "Large write" 仍可能會被阻擋。在 `select` 回傳後，`writefds` 會**清除所有「未準備好寫入」的檔案描述子**。 - `exceptfds`：此集合中的檔案描述子用於**檢查是否存在「異常條件（參閱 [poll(2) 中有關 POLLPRI 的討論](https://man7.org/linux/man-pages/man2/poll.2.html)）」**。在 `select` 回傳後，`exceptfds` 會**清除所有「未發生異常」的檔案描述子**。 - `nfds`：此參數應設置為任一集合中「最大檔案描述子的數字加 1」。 - `timeout`：此參數是一個 timeval 結構，可設定 `select` 應該被阻檔，且「等待檔案描述子變為就緒」的間隔。阻擋直到發生以下條件之一： 1. 檔案描述子變為「就緒」 2. 呼叫被信號處理程式中斷 3. timeout 過期 最後，回傳值方面： 若成功，回傳 **`readfds`、`writefds` 和 `exceptfds` 中被設置的檔案描述子數量**。如果在任何檔案描述子變為就緒之前「timeout 過期」，則回傳值可能為 0；失敗的話，回傳 **-1**，且檔案描述子集保持不變，timeout 變為未定義。 :::danger 使用繁體中文和台灣慣用詞彙！ 參見： * [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) * [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries) > 收到。 ::: ### console.c 理解 整理 console.c 的函式功能後，可大概看出，與命令列及 linenoise 互動相關的函式可能為 `do_web`、`cmd_select`、`completion`、`run_console`。 :::danger 避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。 > 收到。 ::: 以下針對這些函式作**深入理解**： - `do_web`：首先預設 port 為 9999，呼叫 web.c 中的 `web_open` 函式來建立網頁伺服器，若成功，則輸出相關訊息、設定 web_fd 為 '**1**'，並「設定 `use_linenoise` 參數為 false」，失敗則 `perror("ERROR")`。 - `cmd_select`：用 `select` 執行命令處理。類似 `select`，但會先檢查命令輸入是否「存在於內部緩衝區」或「從命令輸入中可讀取」。如果沒被阻擋的話，把緩衝區中的 fd 加入到 select 的 readset 中，如果 web 還沒準備好監聽，也把 web_fd 加入到 readset 中，最後調整 nfds 參數。呼叫 `select` 函式指定給 result 參數，然後看一下哪個檔案運算子還在 readset 中，分別執行對應操作，最後回傳 result 值。 - `completion`：（大致瀏覽後，發現此函式在該題的討論中較不重要。） - `run_console`：該函式會呼叫一堆 linenoise.c 中定義的 API，值得注意的是也會判斷先前定義的 use_linenoise 參數的布林值，若為 "true"，才會進一步提供命令自動補齊、歷史紀錄等操作。 那麼重點來了，難道開啟網頁伺服器（`do_web`）時，順手**將 `use_linenoise` 參數設定為 "false"** 的操作，就是 `run_console` 時，終端命令列端無法執行 linenoise 的元兇嗎？若是，在 `do_web` 函式將 use_linenoise 參數設定為 "false" 的用意為何？能否強制將其設為 "true" 並執行成功？ > 嘗試將 use_linenoise 設為 true 後，發現 qtest 端終端機能正常運行 linenoise 套件；然而若在另一終端機執行 `curl http://localhost:9999/命令` 則會發現發送 HTTP request 給 Web server 的過程直接卡住了。 > 此外，若將 `run_console` 中 `while` 判斷中的 use_linenoise 參數移除，也會有如上結果。 ### 解決 linenoise 與 socket 之衝突 ```c= bool run_console(char *infile_name) { if (!push_file(infile_name)) { report(1, "ERROR: Could not open source file '%s'", infile_name); return false; } if (!has_infile) { char *cmdline; while (use_linenoise && (cmdline = linenoise(prompt))) { interpret_cmd(cmdline); line_history_add(cmdline); /* Add to the history. */ line_history_save(HISTORY_FILE); /* Save the history on disk. */ line_free(cmdline); while (buf_stack && buf_stack->fd != STDIN_FILENO) cmd_select(0, NULL, NULL, NULL, NULL); has_infile = false; } if (!use_linenoise) { while (!cmd_done()) cmd_select(0, NULL, NULL, NULL, NULL); } } else { while (!cmd_done()) cmd_select(0, NULL, NULL, NULL, NULL); } return err_cnt == 0; } ``` 這邊把 `run_console` 之原程式碼秀出來以方便對照理解。 先討論一下哪邊在作 socket；哪邊在作 stdin。 前面 `do_web` 的時候把 use_linenoise 設成 false，所以此處第 19 行在處理 socket；第 10 行的 `while` 則在處理命令列輸入。 ```c= int web_connfd; static int cmd_select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout) { int infd; fd_set local_readset; if (cmd_done()) return 0; if (!block_flag) { /* Process any commands in input buffer */ if (!readfds) readfds = &local_readset; /* Add input fd to readset for select */ infd = buf_stack->fd; FD_ZERO(readfds); FD_SET(infd, readfds); /* If web not ready listen */ if (web_fd != -1) FD_SET(web_fd, readfds); if (infd == STDIN_FILENO && prompt_flag) { printf("%s", prompt); fflush(stdout); prompt_flag = true; } if (infd >= nfds) nfds = infd + 1; if (web_fd >= nfds) nfds = web_fd + 1; } if (nfds == 0) return 0; int result = select(nfds, readfds, writefds, exceptfds, timeout); if (result <= 0) return result; infd = buf_stack->fd; if (readfds && FD_ISSET(infd, readfds)) { /* Commandline input available */ FD_CLR(infd, readfds); result--; set_echo(0); char *cmdline = readline(); if (cmdline) interpret_cmd(cmdline); } else if (readfds && FD_ISSET(web_fd, readfds)) { FD_CLR(web_fd, readfds); result--; struct sockaddr_in clientaddr; socklen_t clientlen = sizeof(clientaddr); web_connfd = accept(web_fd, (struct sockaddr *) &clientaddr, &clientlen); char *p = web_recv(web_connfd, &clientaddr); char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n"; web_send(web_connfd, buffer); if (p) interpret_cmd(p); free(p); close(web_connfd); } return result; } ``` 再把 `cmd_select` 之原程式碼秀出來以方便對照理解。 第 47 行這邊的 `if` 是在判斷是否有 input 的檔案描述子，若有，則作 stdin；第 56 行這邊的 `if` 則在檢查有無 web 檔案描述子，有的話才作 socket。 :::info 將這兩函式重點列出並理解後，想說能否嘗試解決 linenoise 與 socket 的衝突： 原本流程是這樣－`do_web` 把 use_linenoise 設 "false" 了，所以 `run_console` 那邊（上述第 19 行）會作 socket 的相關操作，也就不會有 linenoise 的運作了。 那既然 stdin 及 socket 都會執行 `cmd_select`，那我在 `cmd_select` 中直接引入 linenoise 套件，說不定就能同時運作了？ ::: 試試看這樣： ```diff=53 ... - char *cmdline = readline(); + char *cmdline = linenoise(prompt); ... ``` 發現如此更改，在 `line_edit` 中的 `read` 被阻塞時，linenoise 套件會不能運作。 實驗中會變成：輸入 web 命令後，會先不能用 linenoise，待 另一終端機下任一 curl 命令後，回原終端機按 Enter 後，linenoise 方可運作。 > 參考 [vax-r](https://hackmd.io/@vax-r/linux2024-homework1#%E6%88%90%E5%8A%9F%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8%E8%88%87-linenoise-%E5%A5%97%E4%BB%B6) 的詮述－ > 若將 `linenoise` 擺在 `select` 之後才執行，也就是確認是 std input file descriptor 變為 ready 時才使用，則會導致我們必須按下兩次 ENTER 才能正確執行一次命令，因為第一次 ENTER 用來通知 `select` 這個 fd 的狀態改變，第二次 ENTER 則是用來跳出 `line_edit` 函式。 想法可以這樣變，既然最後一步都是 `line_edit`，何不將 `select` 挪到該函式中，同時監控 stdin 之檔案描述子 或 socket 之檔案描述子就好？在 `cmd_select` 端只需要將兩方命令傳入 `linenoise` 函式，最後送進 `line_edit` 處理 `select` 即可。 **GitHub 之 commit 紀錄**：[Integrate the linenoise function with socket](https://github.com/SuNsHiNe-75/lab0-c/commit/cc15382ed0d4b377c9dfe2ad41a28f5246eb81c5)。 > 參考自 [@vax-r](https://hackmd.io/@vax-r/linux2024-homework1#%E6%88%90%E5%8A%9F%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8%E8%88%87-linenoise-%E5%A5%97%E4%BB%B6) 將原 `cmd_select` 下面的 `select` socket 相關操作概念移到 `line_edit` 執行，先判斷如果有 Web 在監聽，就直接作 socket 操作並回傳即可；若無，則繼續執行 `line_edit` 下方原有的行編輯操作。 如此，實驗中，若命令列端有任何字元輸入（未 Enter），Web 端 curl 後則會等待命令列端完成原命令輸入後，才會執行 Web curl。 :::info TODO：探尋將 linenoise 之歷史紀錄功能整合進 Web server 的方法。 > 目前是 qtest 後，只會記錄到輸入 web 命令前的命令歷史紀錄。 ::: --- ## 命令 shuffle 之實作 ### Fisher–Yates Shuffle 演算法 僅參考 [Fisher–Yates Shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 及相關介紹影片。 其分為 Original version 及 Modern version，下面以陣列運作的例子解說： - **Original version**：設今有一陣列 `arr = {1, 2, 3, 4}` 及一空陣列 `rst = {}`，要作 Fisher–Yates Shuffle，首先因目前有 4 個數字仍未洗牌，因此每個數字的選取機率皆為 $\frac{1}{4}$，設選中 2，則將其從 `arr` 移除，並插到 `rst[0]` 的位置：`rst = {2}`；繼續，目前 arr 剩 3 個數字，則每個數字的選中機率為 $\frac{1}{3}$，設選中 4，比照辦理操作，陣列變為 `rst = {2, 4}` 及 `arr = {1, 3}`；以此類推，直到 `arr` 陣列為空，則洗牌完成。 - **Modern version**：同上例子，只是實作方式變為「只用 `arr`，首輪隨機選取完數字後，將其與 `arr[0]` 之數字交換，接著進入第二輪循環（隨機選完數字後，與 `arr[1]` 交換）」。Modern version 比起 Original version 的優點在於時間/空間複雜度的降低－時間複雜度由 $O(n^2)$ 降為 $O(n)$；空間複雜度則由 $O(n)$ 降為 $O(1)$。 > 根據 [在 qtest 提供新的命令 shuffle](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d#%E5%9C%A8-qtest-%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-shuffle) ，本次作業即要實作 **Modern version** 的 Fisher–Yates Shuffle 演算法。 ### 實作 查看 [qtest.c](https://github.com/SuNsHiNe-75/lab0-c/blob/master/qtest.c) 中的 `console_init` 發現其還未包含 shuffle 命令，若要在 qtest 實作 shuffle 命令，需要將其加入到命令列表中。 觀察 [console.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/console.h) 中有這段描述： ```c /* Add a new command */ void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter); #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) ``` 所以我們要在 `console_init` 中新增命令 shuffle，並建立 `do_shuffle` 函式，以偵錯並呼叫在 [shuffle.h](https://github.com/SuNsHiNe-75/lab0-c/blob/e624fa849b70b3f92580ef00ed6ac28c496d0994/shuffle.h) 中的 `q_shuffle` 函式： ```diff static void console_init() { ... ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time", "[K]"); + ADD_COMMAND(shuffle, "Do the Fisher–Yates Shuffle algorithm", ""); add_param("length", &string_length, "Maximum length of displayed string", NULL); ... } ``` ```c static bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!current || !current->q) report(3, "Warning: Calling shuffle on null queue"); error_check(); if (q_size(current->q) < 2) report(3, "Warning: Calling shuffle on single queue"); error_check(); if (exception_setup(true)) q_shuffle(current->q); q_show(3); return !error_check(); } ``` > 若「佇列為空」或「佇列只有一個元素」，會跳警告。 > 沒問題則呼叫 `q_shuffle`。 鑒於 queue.h 修改後會無法 commit，故建兩新檔案 [shuffle.c](https://github.com/SuNsHiNe-75/lab0-c/blob/e624fa849b70b3f92580ef00ed6ac28c496d0994/shuffle.c) 及 [shuffle.h](https://github.com/SuNsHiNe-75/lab0-c/blob/e624fa849b70b3f92580ef00ed6ac28c496d0994/shuffle.h)，來實作 shuffle 命令，並將其一 include 到 qtest.c 中，詳細程式碼請看*下方的 commit 紀錄*。 **GitHub 之 commit 紀錄**：[Implement a new command - shuffle](https://github.com/SuNsHiNe-75/lab0-c/commit/e624fa849b70b3f92580ef00ed6ac28c496d0994) > **`q_shuffle`**：運作原理即我上面分析的 Modern version 演算法，唯要注意實作場景改為 Circular Linked List 資料結構。先用 `q_size` 算佇列長度，然後 `rand` 一個隨機數。使用一 `*current` 指向「已完成 shuffle 佇列的下一個元素」、一 `*selected` 指向「選定要 swap 的隨機數」、用一 `*completed` 指向「已完成 shuffle 佇列的尾端」方便調整 `*current` 的位置。基本上就是先將 `*selected` 指到 `rand` 到的索引元素，並 `swap` `*current` 與 `*selected` 所指元素，調整 `*completed` 及 佇列長度變數，直到佇列長度變數為 0，即完成洗牌。 > **`swap`**：使用 `list_move_tail` 去實作。特別注意「兩節點相同」及「兩節點相鄰」的特殊情況即可。 ### 測試程式分析 前置步驟要先安裝 python3, pip, matplotlib。 使用 [測試程式](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F) 中的 [driver.py](https://github.com/SuNsHiNe-75/lab0-c/blob/e624fa849b70b3f92580ef00ed6ac28c496d0994/driver.py) 去分析我的 shuffle 實作，測試 shuffle 次數為 1,000,000 次，根據下方之輸出及直方圖的呈現結果可知，Fisher–Yates Shuffle 演算法是 **Uniform Distribution** 的。 ```shell Expectation: 41666 Observation: {'1234': 41550, '1243': 41713, '1324': 41566, '1342': 41736, '1423': 41914, '1432': 41481, '2134': 41399, '2143': 41589, '2314': 41535, '2341': 41490, '2413': 41668, '2431': 41962, '3124': 41953, '3142': 41714, '3214': 42001, '3241': 41723, '3412': 41644, '3421': 41679, '4123': 41759, '4132': 41634, '4213': 41600, '4231': 41478, '4312': 41762, '4321': 41450} chi square sum: 15.487783804540873 ``` ![圖片](https://hackmd.io/_uploads/SJ1gyXfTp.png) --- ## 引入 `lib/list_sort.c` > 本處與 @jujuegg 協作。 ### 解釋 Linux 核心的 `lib/list_sort.c` #### `merge` 在 `merge` 函式中，我上面的方法是使用 `list_move` 來移動比較過後的節點，但 Linux 卻只使用了三行程式碼來完成，且運用到了 pointer to pointer 的概念。且它並不是一次只移動一個節點到 `head`，而是將該節點所在串列==移動==到 `head` 的尾端。以下是部分程式碼： ```c struct list_head *head, **tail = &head; // a and b are two sotred list heads if (cmp(priv, a, b) <= 0) { *tail = a; tail = &a->next; a = a->next; if (!a) { *tail = b; break; } } ``` 我們是需要自己去定義 `cmp` 的。而對於 `priv` 的解釋則是參考 [vax-r](<https://hackmd.io/@vax-r/linux2024-homework1#%E7%A0%94%E8%AE%80-liblist_sortc-%E4%B8%A6%E5%98%97%E8%A9%A6%E6%94%B9%E9%80%B2>) 同學的解釋： > 可以注意到函式的第一個參數 priv ，可以在 [/lib/test_list_sort.c](<https://github.com/torvalds/linux/blob/master/lib/test_list_sort.c>) 當中看到 priv 是用來使得 check 這個函式經過 KUnit 測試後可以 failed。 #### `merge_final` 再來看到 `merge_final`，他比起 `merge` 多了下面這個步驟，`b` 是當其中一個串列為空時，剩下的串列所在的位置。這看起來是很沒必要的行為，因為是拿同一個節點進行比較，但凡事都有原因。 ``` c do { if (unlikely(!++count)) cmp(priv, b, b); b->prev = tail; tail = b; b = b->next; } while (b); ``` 註解提到： > If the merge is highly unbalanced (e.g. the input is already sorted), this loop may run many iterations. Continue callbacks to the client even though no element comparison is needed, so the client's cmp() routine can invoke cond_resched() periodically. 如果其中一個串列還剩很多節點，持續呼叫 `cmp` 可以週期性的呼叫 `cond_resched`，這個函式與 Kernel 安排 CPU time 有關。 #### `list_sort` 如果有兩個尚未合併的 $2^k$ 大小的串列，==等到下一個也是 $2^k$ 大小的串列出現，前兩個就會合併==。 只要這 $3*2^k$ 個節點可以全部放到快取中，就可以避免 [cache thrashing](<http://www.wowotech.net/memory_management/458.html>)，簡單來說就是一直重複替換快取中某個地方的資料，非常浪費時間。 count 會持續記錄尚未合併的節點數量，當達到 $2^k$ 的奇數倍時，就會啟動合併。 發生 2 次合併後，所產生的 2 個 $2^{k+1}$ 大小的串列會在第 3 個串列出現前合併，所以永遠不會有過多沒有合併的串列。 **程式碼分析：** - 變數結構： - `*list = head->next`：要排序的串列的第一個節點 - `*pending = NULL` ：還沒合併的串列 - `count = 0`：`pending` 中節點的數量 - `**tail = &pending`：指向 `pending` 指標的指標，它的作用是尋找 `pending` 中要做合併的位置，並且會指向該合併點尾端的指標 在整個過程中，`list->prev` 會持續指向 `pending`。 有趣的是，在第一行，程式就把串列變為暫時的==單向鏈結串列==。但卻沒有更動頭的 `prev`。 ```c /* Convert to a null-terminated singly-linked list. */ head->prev->next = NULL; ``` 當 `count` 的 LSB 是 1 的時候，才會進入迴圈，並且持續右移，直到有 0 出現。這邊在尋找要合併的位置。 ```c /* Find the least-significant clear bit in count */ for (bits = count; bits & 1; bits >>= 1) tail = &(*tail)->prev; ``` 這邊的意思是，如果 `bits` 裡面還有剩餘的 1 的話，就會啟動合併。換言之，如果目前 ==`count + 1` 為 2 的冪，則不合併==。合併後的串列會儲存在 `a`，後續再修改 `pending (*tail)` 來指到剛合併完的串列。 一開始在追蹤程式碼的時候可能會覺得很奇怪，因為 `pending` 一開始是只有藉由 `prev` 連接的==單向鏈結串列==，而下面是將 `tail` 所在位置與 `tail->prev` 進行合併，而在第一次呼叫 `merge` 之後才會將 `pending` 中的 `next` 指標接好。 ```c if (likely(bits)) { struct list_head *a = *tail, *b = a->prev; a = merge(priv, cmp, b, a); /* Install the merged result in place of the inputs */ a->prev = b->prev; *tail = a; } ``` #### 推論： 使用 bottom up 的方法實作 merge sort 相較於 top down 方法省去了 partition 的步驟，由於合併的過程是與相鄰的串列進行，這方法會讓最近被合併過的資料，在不久後馬上跟附近的串列合併，在快取中的使用率會相對地頻繁。 ### 引入 `list_sort` 到 lab0-c 當中 #### `list_sort.c` - 修改 `include` ```diff #include <linux/kernel.h> - #include <linux/bug.h> - #include <linux/compiler.h> - #include <linux/export.h> #include <linux/string.h> - #include <linux/list_sort.h> - #include <linux/list.h> + #include <list_sort.h> + #include "queue.h" ``` - 新增 `likely` 與 `unlikely` 巨集 ```c # define likely(x) __builtin_expect(!!(x), 1) # define unlikely(x) __builtin_expect(!!(x), 0) ``` - 把變數型態宣告 `u8` 改成 `uint8_t` ```diff - u8 count = 0; + uint8_t count = 0; ``` - 新增 `cmp` 函式，把 `priv` 移除，並加入指定 `descend` 功能，記得要修改 `nonnull` 的變數位置 ```c int cmp(const struct list_head *a, const struct list_head *b, bool descend) { element_t *a_entry = list_entry(a, element_t, list); element_t *b_entry = list_entry(b, element_t, list); if (!descend) return strcmp(a_entry->value, b_entry->value) < 0 ? 0 : 1; else return strcmp(a_entry->value, b_entry->value) > 0 ? 0 : 1; } ``` - 把最後面的 `EXPORT_SYMBOL` 移除，暫時用不到 #### `q_test.c` - 新增標頭檔 ```diff + #include "queue.h" + #include "list_sort.h" ``` - 新增 `do_lsort` 命令，我是直接參考裡面的 `do_sort` 寫法，沒有更改太多東西。 #### `Makefile` ```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 ``` ### 比較效能落差 我們可以藉由三種數據來比較各個排序演算法之間的差異： - Execution time - The number of comparisons - Cache miss ratio 我選擇比較執行時間的差距，在 [Dude, is my code constant time?](<https://eprint.iacr.org/2016/1123.pdf>) 中提到，可以測量程式的 CPU cycle 來做為時間的依據。但我就沒有再執行後續更嚴謹的步驟，也就是設立虛無假說和計算 F 值。 #### 使用 [Linux 效能分析工具 perf](<https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial>) 進行計算 以下設計是參考去年 [chiangkd](<https://hackmd.io/duPg38XOTL-XKa7_h0Ielw?view#%E7%A0%94%E8%AE%80-list_sortc-%E4%B8%A6%E5%BC%95%E5%85%A5%E5%B0%88%E6%A1%88>) 同學的方法，我預計使用隨機生成且不同大小的測資，測量 **10** 次來取平均。大概測到 500 萬左右個節點的時候就滿了。 :::danger command 是「命令」，而非「指令」(instruction) > 收到。 ::: 執行以下命令： ```shell $ sudo perf stat --repeat 10 ./qtest -f traces/trace-sort.cmd ``` #### 自己實作的 `q_sort` | Data Size | Average Time (Sec) | | --------- | ------------------ | | 50000 | 0.0206 | | 100000 | 0.0632 | | 500000 | 0.5023 | | 1000000 | 1.0857 | #### Linux 的 `list_sort` | Data Size | Average Time (Sec) | | --------- | ------------------ | | 50000 | 0.0169 | | 100000 | 0.0586 | | 500000 | 0.4323 | | 1000000 | 0.9429 | 確實有比較快的趨勢。 --- ## 研讀論文〈Dude, is my code constant time?〉 > 本處與 @jujuegg 協作。 在一些已經存在的方法中，需以某種方式對硬體進行模擬，而 CPU 的訊息並不是完全公開的，在實現上難度很高，這是它們共同的缺點。 而 dudect 是基於 leakage 偵測，來判斷程式碼的複雜度是否為 constant time 的一種工具。 ### 解釋 Simulation 當設定 `simulation` 為 1 後，在呼叫 `it`, `ih`, `rt`, `rh` 這 4 種命令時，會呼叫相對用來測試是否為 constant time 的函式： ```c bool ok = pos == POS_TAIL ? is_insert_tail_const() : 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; ``` 但我怎麼都找不到這些函式被定義在哪邊，直到我看到 [var-x](<https://hackmd.io/@vax-r/linux2024-homework1#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89>) 同學提到它寫在 `fixure.h` 中才知道。 :::danger 參閱課程教材！ ::: ```c #define _(x) bool is_##x##_const(void); DUT_FUNCS #undef _ ``` 總歸來說，最終呼叫的是 `test_const` 這個函式，並用 `mode` 來區分目前是測試哪個命令。其中會持續的使用 `doit` 來測試，只要有一次通過，程式就會中斷並判定為 constant time。相對的，如果跑了足夠多次並且都沒有成功，則宣布不是 constant time。 ```c static bool test_const(char *text, int mode) { bool result = false; t = malloc(sizeof(t_context_t)); for (int cnt = 0; cnt < TEST_TRIES; ++cnt) { printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES); init_once(); for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1; ++i) result = doit(mode); printf("\033[A\033[2K\033[A\033[2K"); if (result) break; } free(t); return result; } ``` 在 `doit` 裡面，以下為主要測試區塊的程式碼 ```c bool ret = measure(before_ticks, after_ticks, input_data, mode); differentiate(exec_times, before_ticks, after_ticks); update_statistics(exec_times, classes); ret &= report(); ``` - `measure` ： 被定義在 `constant.c` 中，它的測量方法是先插入一個字串，之後再測量插入/刪除另一個字串的時間。 - `differentiate`：計算 `before_ticks` 與 `after_ticks` 的差值。 - `update_statistics`：檢測測量數據的平均值。 - `report`：藉由檢查 t 統計值 `max_t` 是否超過閾值來判斷 ### 解釋 Student's t-distribution ### 新增 percentile 處理 仿照 [dudect.h](<https://github.com/oreparaz/dudect/blob/master/src/dudect.h>) 對 lab0-c 做處理。詳細程式碼請見 [Apply percentiles to make dudect better](https://github.com/SuNsHiNe-75/lab0-c/commit/5f8b60d6fe4df9ae9f64ef587c2c4343757d6686)。 - 在 `t_context_t` 結構中新增 `percentiles`，方便統一管理。 - 捨棄第一次測量的 batch，並執行 `prepare_percentile`。 - 在 [`update_statistics`](<https://github.com/oreparaz/dudect/blob/master/src/dudect.h#L298C1-L298C51>) 中，這個迴圈省去了前面 10 筆的資料，我也仿照它的作法。 --- ## Tic-tac-toe ### 引入 hlist.h 參照 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)，透過 Ctrl + F 搜尋 hlist 相關程式碼，將他們複製到新建的 [hlist.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/hlist.h) 內即可。 > 注意包含相關函式庫。 ### 新增 `ttt` 命令 在 [qtest.c](https://github.com/SuNsHiNe-75/lab0-c/blob/master/qtest.c) 中的 `console_init` 新增 `ADD_COMMAND` ，並另寫一函式 `do_ttt` 以呼叫主要執行函式。另需包含 [game.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/game.h) 以獲取相關函式之訊息。最後，在 Makefile 也須新增編譯 game.o。 > 在實作 shuffle 命令已練習過。 > 此時，我在 `do_ttt` 中先呼叫 game.c 中的 `draw_board` 函式來測試。 至此步驟，已可運行 `ttt` 命令，並產生棋盤；但打如 `a3` 等命令仍未定義。 ### 整合 jserv/ttt 完畢 > commit [afe377f](https://github.com/SuNsHiNe-75/lab0-c/commit/afe377f33072f5ea2624bf2dc89b63c83ffb8e4a)。 先將 mt19937-64.[ch]、zobrist.[ch]、negamax.[ch] 整合到 lab0-c 中，qtest 中記得包含 negamax.h，另外 Makefile 需新增編譯上述檔案。 其中 main 的運作過程寫在 `do_ttt` 內，以完善程式運作，並**成功整合運行**。。 > 其中 mt19937-64 是 Mersenne Twister 偽隨機數生成器的 64 位元版本。 > 參考 [Zobrist Hashing](https://en.wikipedia.org/wiki/Zobrist_hashing)。zobrist 實現了一個基於 Zobrist key 的 hash table，用來儲存棋譜或遊戲狀態的得分及最佳下法。該檔案提供了初始化、查找、插入和清空的功能。 > 參照 [Negamax](https://en.wikipedia.org/wiki/Negamax)。negamax 是一種用在賭博遊戲中的 Minimax 搜尋演算法，特別適用於雙人遊戲的 [zero-sum](https://en.wikipedia.org/wiki/Zero-sum_game) 特性。 commit 過程發現很多 cppcheck 錯誤，需一一自行修正。 ```shell zobrist.c:64:21: error: Null pointer dereference: (struct zobrist_entry_t*)0 [nullPointer] entry = hlist_entry(hash_table[i].first, zobrist_entry_t, ht_list); ^ nofile:0:0: information: Cppcheck cannot find all the include files (use --check-config for details) [missingInclude] ``` > 因一直無法解決此 cppcheck 報錯，故直接將其忽略檢查，在 pre-commit.hook 檔案中加上 `--suppress=nullPointer:zobrist.c` 即可。 ### 用定點數取代浮點數運算 #### Monte Carlo Tree Search（MCTS）理解 參照 [Monte Carlo Tree Search 解說](https://www.youtube.com/watch?v=J3I3WaJei_E) 及 [Monte Carlo Tree Search - Tic-Tac-Toe Visualization](https://www.youtube.com/watch?v=ghhznqBoESY)。 以下黑白棋為例，套用 Monte Carlo Tree Search 讓電腦在下每一步棋時都會去估算其「下哪步棋勝率最高（即最佳解，但要注意的是，執行此演算法時**不會算出全部行動的所有延伸結果**，所以此最佳解不是實質意義上的最佳解！）」，簡介步驟如下（節點有「勝率」及「比賽場數」等參數）： - Select Leaf Node：往當前 Upper Confidence Bound (UCB) 最高的節點方向找（若 UCB 相同，則按左到右的順序找），直到找到的點沒有左/右子點。 > UCB 可達成 Exploitation（選擇已知最好策略） 與 Exploration（選擇探索其他路線）的平衡，有興趣的可再自行深入了解。 - Expand / Rollout： - 若為新節點（尚未更新過），則執行 Rollout－以該節點為起點，模擬完整場遊戲直到結束，並獲得比賽結果。 - 若該節點已更新過，則執行 Expand－往下生成兩個新節點。 - BackPropagate：Rollout 結束後，往上更新所有相關節點的結果。 可看出，雖然對比 DFS 等演算法，運算資源及時間都優化很多；但是其算出的只是「還不錯的結果」來操作下一步棋，因此若對手故意引導電腦往較差的結果下，電腦是有機率輸的。 其實作在 [agents/mcts.c](https://github.com/jserv/ttt/blob/main/agents/mcts.c) 中。 #### 浮點數之深入探討 研讀 [agents/mcts.c](https://github.com/jserv/ttt/blob/main/agents/mcts.c) 可發現，其 `double score` 相關的操作皆為浮點數運算，我首先想針對它，進行定點數運算的取代。 實作前，需先理解浮點數與定點數「對電腦來說的位元儲存方式」等的區別。 `double` 本身是 64-bit 的雙精度浮點數資料型態，參考 [IEEE 754 的「64位元雙精度」](https://zh.wikipedia.org/wiki/IEEE_754#64%E4%BD%8D%E9%9B%99%E7%B2%BE%E5%BA%A6) 小節與 [雙精度浮點數](https://zh.wikipedia.org/wiki/%E9%9B%99%E7%B2%BE%E5%BA%A6%E6%B5%AE%E9%BB%9E%E6%95%B8)，雙精度浮點數的格式呈現如下： ![IEEE_754_Double_Floating_Point_Format.svg](https://hackmd.io/_uploads/Skjm2_VAa.png) 其有 1-bit 的符號位、11-bit 的指數位及 52-bit 的有效數位。 要特別注意的是，為了方便比較大小，其指數部分是使用「偏正值」形式表示；而非使用「二補數」表示。如此，指數部分通常用一個**無符號的正數值**儲存。 > 偏正值 = 實際的指數大小 + 固定值（64-bit 為 1023）。 #### 定點數之深入探討 定點數方面，參照 [Linux 核心的浮點數運算－定點數](https://hackmd.io/@sysprog/linux2024-ttt#%E5%AE%9A%E9%BB%9E%E6%95%B8) 及 [定點數運算](https://zh.wikipedia.org/zh-tw/%E5%AE%9A%E9%BB%9E%E6%95%B8%E9%81%8B%E7%AE%97)。 首先我們要知道，為何 Linux 核心會偏好定點數的實作－定點數的運算比浮點數要快，需要的硬體也比較少。假如要計算的數值範圍事先就已知道，而且限制在較小的範圍內，定點數運算可以有效的使用其位元（誤差較小）。 另外，使用定點數運算的程式，不會受到是否有浮點運算器（FPU）的影響，可移植性比浮點數要高；且並非所有 Linux 支援的硬體都具備 FPU... 種種因素，使 Linux 核心在實務上，較建議使用定點數運算。 定點數表示法中，小數部份和整數部份一樣，也會表示為**進制底數 $b$ 的冪次**，不過是以負數冪次來表示。即若儲存了 n-bit 的小數，其數值一定是 $b^{−n}$ 的整數倍。 定點數類型的值其實就是個整數，但需要額外作**比例進位**，而進多少位，則需要根據具體的定點數類型決定。如二進制定點數下的負數常常會用二補數型式下的有號整數表示，其中隱含著**縮放係數**（或小數長度）。 > 舉個例子，8-bit 二進制有號整數 $(11110101)_2 = −11$，若分別配合 -3, +5 及 +12 的縮放位元，它們的數值即為 $\frac{−11}{2^{−3}} = −88$、$\frac{−11}{2^5} = −0.34375$，和 $\frac{−11}{2^{12}} = −0.002685546875$。 這也印證了作業文獻中，定點數運算的常見規格： - 定點數加法與減法 - 可直接進行 - 定點數乘法 - 結果須再**除 $b^n$** (b 為進制，n 為小數位數) - 定點數除法 - 結果須再**乘 $b^n$** (b 為進制，n 為小數位數) #### 縮放係數（Scaling Factor）的討論及選擇 縮放係數簡單來說，就是用來確定「小數點的位置在該整數型態的哪一位」，即 **fractional bits**。其是沒有標準格式的，需要因應系統需求，由開發人員自行設定。 一般來說，我們會希望縮放係數越大越好，因為這樣可以增加定點數的範圍和精度。但同時，縮放係數越大，「可以表示的小數部分就越少」，這可能會導致運算過程中的精度損失。 > 以十進制來舉個例子：假設我們需要處理一組數據，這些數據的範圍在 0 到 1000 之間，並且需要保留至**小數點後兩位**。我們可以把這些數據「乘以 100」來將它們轉換為定點數，這樣可以將小數點移動兩位，讓數據成為整數。 -- 設**縮放係數為 100**，那把原始數據乘以 100 後，好處是可以保留到小數點後兩位的精度；但同時，整數部分的範圍是 0 到 100000，如果超出了這個範圍，則會造成 [溢位](https://zh.wikipedia.org/zh-tw/%E5%AE%9A%E9%BB%9E%E6%95%B8%E9%81%8B%E7%AE%97#%E6%BA%A2%E4%BD%8D)。 -- 設**縮放係數為 1000**，那把原始數據乘以 1000 後，雖然擴大整數部分的範圍；但同時，我們只能保留到小數點後一位的精度，因為我們將小數點向右移動了一位。 鑒於 double 為 64-bit，且定點數即為整數型態，實作上我想用 [stdint.h](https://zh.wikipedia.org/zh-tw/Stdint.h) 中定義的 `uint64_t` 型態來取代原 `score` 的 `double` 型態。另設定縮放位元有 12-bit，即縮放係數為 $2^{12}$。 前面提到，縮放係數越大越好，且觀察了相關運算函式（`uct_score` 及其中的 `log` 等）後，覺得這樣設定的精度已很夠用，且不會有溢位的問題。 #### 實作定點數操作 首先要先引入 stdint.h，並將相關變數設為 `uint64_t`。 之後在 [game.h](https://) 中定義「縮放位元」。 ```diff + #define FIXED_SCALING_BITS 12 ``` 先改 game.c 中的 `calculate_win_value` 函式，其本來的功能很簡單－贏了回傳 `1`；輸了回傳 `0`；否則平手，回傳 `0.5`。只需將其改成定點數的表示數值即可。注意函式回傳值為 `uint64_t`。 ```diff uint64_t calculate_win_value(char win, char player) { if (win == player) + return 1ULL << FIXED_SCALING_BITS; - return 1.0; if (win == (player ^ 'O' ^ 'X')) + return 0ULL; - return 0.0; + return 1ULL << (FIXED_SCALING_BITS - 1); - return 0.5; } ``` > commit [4978029](https://github.com/SuNsHiNe-75/lab0-c/commit/49780295e6ac24f7b86885ee65c842d65c10e31c)。 接著分別將 `select_move`、`simulate`、`backpropagate` 及 `mcts` 等函式之 `double` 相關變數改為 `uint64_t`。 最後來處理最麻煩的 `uct_score` 的相關定點數運算－最主要是需要實作**定點數的 `sqrt` 及 `log` 函式**。 ##### sqrt 該函式我用「[二分搜尋（逼近）法](https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%88%86%E6%B3%95_(%E6%95%B8%E5%AD%B8))」來實現。 作法如下： ```c uint64_t fixed_sqrt(uint64_t x) { if (x <= 1) return x; uint64_t low = 0ULL; uint64_t high = x; uint64_t precision = 1ULL << (FIXED_SCALING_BITS - 2); while (high - low > precision) { uint64_t mid = (low + high) / 2; uint64_t square = (mid * mid) >> FIXED_SCALING_BITS; if (square < x) { low = mid; } else { high = mid; } } return (low + high) / 2; } ``` ##### log 實作 log 的方法有很多種，鑒於不可能用查表法，只能使用相關的**近似算法**，如牛頓插值法、或泰勒級數展開等。 我使用較廣為使用也較易實現的「[泰勒級數展開](https://zh.wikipedia.org/zh-tw/%E6%B3%B0%E5%8B%92%E7%BA%A7%E6%95%B0)」來實作定點數的 `log` 運算。 > 泰勒展開式，是將一個函數「以多項式來表示」的一種方式。 一多項式函數 $f(x)$ 在 $x = a$ 時，$n$ 階的泰勒展開式 $P_n(x)$ 是： $P_n(x) = f(a) + \frac{f^{(1)}(a)}{1!}(x-a)^1 + \frac{f^{(2)}(a)}{2!}(x-a)^2 +...+ \frac{f^{(n)}(a)}{n!}(x-a)^n + R_n(x)$ 而對於對數函數，我們可以使用「自然對數」的泰勒展開式來近似計算。 $ln(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \frac{x^4}{4} +......$ ```c static uint64_t fixed_log(uint64_t x) { uint64_t fixed_x = x << SCALING_BITS; if (x == 0) return UINT64_MAX; if (x == 1) return 0ULL; uint64_t result = 0; for (int i = 1; i <= 16; ++i) { if (i % 2 == 0) { result -= fixed_power_int(fixed_x, FIXED_SCALING_BITS, i) / i; } else { result += fixed_power_int(fixed_x, FIXED_SCALING_BITS, i) / i; } fixed_x = (fixed_x * (x << SCALING_BITS)) >> SCALING_BITS; } return result; } ``` > 對於「$x$ 的冪次部分」，我借用 [fixed_power_int](https://hackmd.io/@sysprog/linux2024-ttt#fixed_power_int) 函式來實現，並修改為 64-bit 的版本以符合情境。 > commit [2cd0bf3](https://github.com/SuNsHiNe-75/lab0-c/commit/2cd0bf3f325d9a536a5c10547d03aeafb3b112f8)。 :::info TODO: 驗證其正確性，並與 negamax 比較。 測試後發現我的定點樹版本 MCTS 有問題，沒有實作完全 MCTS 的邏輯，在猜想是否為「變數型態（位元數）」的問題？ ::: ### 電腦 vs. 電腦 在 `qtest` 中加入藉由 option 命令來調整為電腦 vs. 電腦的選項： ```c // global variable int ai_vs_ai = 0; // in console_init() add_param("AI_vs_AI", &ai_vs_ai, "Let AI and AI play Tic-Tac-Toe", NULL); ``` 在原本是玩家的回合中，檢測目前是否為電腦 vs. 電腦，如是，則讓 AI 決定下一步： ```diff if (turn == ai) { int move = negamax_predict(table, ai).move; if (move != -1) { table[move] = ai; record_move(move); } } else { + if (ai_vs_ai) { // AI vs. AI + int move = negamax_predict(table, turn).move; + if (move != -1) { + table[move] = turn; + record_move(move); + } } else { // Player vs. AI draw_board(table); int move; while (1) { move = get_input(turn); if (table[move] == ' ') { break; } printf("Invalid operation: the position has been marked\n"); } table[move] = turn; record_move(move); } } ``` 經過我反覆測試發現，每次的電腦 vs. 電腦對局的過程都會一模一樣。為了讓此對局有變化性，我決定讓先手的電腦隨機選擇第一步。 由 `get_input` 函式可以知道，玩家輸入的==英文字母==及==數字==會被轉變為 { `0` ~ `BOARD_SIZE * BOARD_SIZE - 1` } 之間的數字，所以我讓電腦在第一步時隨機選擇範圍內的數字。 ```c bool first_move = true; if (first_move) { move = rand() % (BOARD_SIZE * BOARD_SIZE - 1); first_move = false; } ``` 最後再加入顯示時間的功能，此部分參考 [vax-r](<https://github.com/vax-r/lab0-c/commit/9410e7e93ec2ddd4af77932f58444b8a05c86eb6#diff-30e0b0c63d44b7571412ebe2b28cef8f96c61f4dcd032950982d7bf985ad4a2cR555>) 同學的程式碼： ```c draw_board(table); time_t timer = time(NULL); struct tm *tm_info = localtime(&timer); char buffer[26]; strftime(buffer, 26, "%Y-%m-%d %H:%M:%S", tm_info); puts(buffer); ```