# 2025q1 Homework1 (lab0) contributed by < `yy214123` > ### Reviewed by `Andrushika` #### q_insert_head, q_insert_tail > commit [f63c3aa](https://github.com/yy214123/lab0-c/commit/f63c3aa1d09f6ab0fe7e9cf94167013f346dd09d) & [4123e63](https://github.com/yy214123/lab0-c/commit/4123e63d780c4e071b05c96d8dbcccf859daa7e0) 此處在 malloc 新的 `element_t` 後，直接指定 `new_elem->value = s`： ```c element_t *new_elem = malloc(sizeof(element_t)); if (!new_elem) return false; new_elem->value = s; ``` 然而，這樣的方法很容易造成 dangling pointer：因為 `s` 是由傳進函式的 `char*`，身為函式的實作者，沒辦法保證函式呼叫者之後會不會對 `s` 做其他處置。如果函式呼叫者將 `s` 的記憶體空間釋放（或做其他修改），後續就會發生 use after free 或存取的值和預想中不同的問題。 比較好的作法，是將 `s` 先 copy 一份後放進 `value`： ```c new_elem->value = strdup(s); ``` #### q_ascend & q_descend q_reverse 版本 > commit [d6d8c49](https://github.com/yy214123/lab0-c/commit/d6d8c492977dc0bcdd06e2096c8b22b7c64380a4) & commit [bd72375](https://github.com/yy214123/lab0-c/commit/bd7237530da7b27e516438406d6ce8e409ff082a) 你先前使用 `q_reverse` 來簡化操作，後來發現錯誤。先假設這樣的實作是正確的，也會存在效能的問題。`q_reverse` 的時間複雜度是 $O(n)$，所以 `q_descend` 會比 `q_ascend` 多一次對鏈結串列的走訪。雖然兩者在 big-O notation 下都是 $O(n)$，但 $n$ 前方的常數會有所差異。 > 對，這的確是我當下沒考量到的細節，多執行一次 `q_reverse` 的確會造成額外的效能損失。 [name=yy214123] #### HackMD 的小問題 可以將各標題層級、內文的結構分清楚一些，目前「研讀〈Dude, is my code constant time?〉」被和 `queue.c` 相關說明放在一起，但兩者似乎沒有太大相關；「處理 commit message 遺失 Change-Id 的錯誤」也可以獨立寫成一個標題，方便查找。 > 感謝你的建議，我已經對排版進行了修改。關於「研讀〈Dude, is my code constant time?〉」，我將其獨立為新的標題。而對於「處理 commit message 遺失 Change-Id 的錯誤」，相關的內容我已移至[額外問題紀錄](##額外問題紀錄)中進行描述。若有其他排版建議也歡迎提出，我希望能使整體筆記排版更精美。 [name=yy214123] {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 開發環境 ```shell $ hostnamectl Operating System: Ubuntu 24.04.2 LTS Kernel: Linux 6.11.0-17-generic $ gcc --version gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.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): 20 On-line CPU(s) list: 0-19 Vendor ID: GenuineIntel Model name: 13th Gen Intel(R) Core(TM) i5-13600KF CPU family: 6 Model: 183 Thread(s) per core: 2 Core(s) per socket: 14 Socket(s): 1 Stepping: 1 CPU(s) scaling MHz: 29% CPU max MHz: 5100.0000 CPU min MHz: 800.0000 BogoMIPS: 6988.80 L1d: 544 KiB (14 instances) L1i: 704 KiB (14 instances) L2: 20 MiB (8 instances) L3: 24 MiB (1 instance) NUMA node(s): 1 NUMA node0 CPU(s): 0-19 ``` ## 前置作業 這是我第二次選修這門課，因此去年已經有相同的 repository。我利用 GitHub 網站提供的 `import repository` 功能，將原先的 repository 重新命名為 [lab0-c_2024](https://github.com/yy214123/lab0-c_2024)，接著，我使用 GitHub 提供的 `sync fork` 功能來初始化 [lab0-c](https://github.com/yy214123/lab0-c)。 :::danger 課程教材會反覆出現，你不用特別提，除非你要指出其中關鍵描述。 > 收到。 ::: ## 指定的佇列操作 在實作 `queue.c` 中的任意函式之前，應先仔細閱讀對應的標頭檔 queue.h，理解其中對各函式的說明。此外，可輔以 [The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) 中的相關巨集來實現功能。 依據作業指示，在執行 `git commit` 前，須先執行 `clang-format -i queue.c`，來排除程式碼排版和風格檢查的錯誤。 在共筆紀錄中須附上對應的 commit message 連結，輸入下方命令可以節省前往 GitHub 複製的時間： ```shell $ git log -1 --pretty=format:"commit [%h](https://github.com/yy214123/lab0-c/commit/%H)" | xsel --clipboard --input ``` ### q_size > commit [55ed393](https://github.com/yy214123/lab0-c/commit/55ed393b53f006500875832d94c1890f62b45b34) :::danger 既然是作業描述，就沒必要特別放超連結。你該探討作業要求背後的因應措施。 > 收到。 ::: :::danger 上面程式碼沒有討論的必要，不用列出，你該回顧自己的 commit message 是否有長進。 > 回顧去年的 commit [97f2a53](https://github.com/yy214123/lab0-c_2024/commit/97f2a539a3f001814f9db0616462f1ebca9be220)，當時的 commit message 雖然詳細，但過於冗長，包含了不必要的細節（如 list_for_each 的具體行為），此外，標題使用了 "Refactor"，這個單字適用於優化程式架構或提高程式可讀性，而 `q_size` 原先總是回傳 `-1`，這顯然是錯誤的實作，故使用 "Fix" 更為恰當。 > > 我認為今年的 commit message 比較好，準確描述了問題與修正內容，使讀者能快速理解。 ::: ### q_new > commit [0a99902](https://github.com/yy214123/lab0-c/commit/0a999021edfb88e15570468e2233ab6bb67a1e8f) 首先，使用 `malloc` 為 `head` <s>分配</s> 配置記憶體空間。然而，由於 `malloc` 可能會失敗，因此在配置後應進行檢查。 若記憶體配置成功，則可使用 `list.h` 中的 `INIT_LIST_HEAD` 來初始化節點，並將其回傳。 :::danger allocate 譯作「配置」，避免和 dispatch 的翻譯混淆。 注意空白字元。 > 已修正。 ::: ### q_free > commit [a17ec8e](https://github.com/yy214123/lab0-c/commit/a17ec8e26f69c36fff4387abf0e037818f0032b2) 在釋放佇列之前，應先檢查 `head` 是否存在，若 `head` 為空，則表示佇列不存在，無需進一步處理。 接著，檢查佇列是否僅包含 `head` 節點而無其他元素，若確實如此，則直接釋放 `head` 的記憶體空間即可。 若佇列內仍有其他元素，則應使用 `list_for_each_safe` 巨集 <s>遍歷</s> 逐一走訪每個節點佇列中的所有節點，並透過 `q_release_element` 釋放每個元素佔用的記憶體。最後，再釋放 `head` 節點的記憶體，以確保佇列被完全釋放 :::danger 注意用語！參見「[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)」及「[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)」 > 已修正用語，traverse every node 的合理翻譯應為 "逐一走訪每個節點"，而非 "遍歷每個節點"。 ::: ### q_insert_head & q_insert_tail > commit [a7b2431](https://github.com/yy214123/lab0-c/commit/a7b24311a9422e94e74511948b33bb0a920abcd0) & commit [2deb4b2](https://github.com/yy214123/lab0-c/commit/2deb4b28b084b62b5fd81d4be8437ec7405ba7bc) > 我檢查 commit message 時發現，這兩則 commit message 的結尾沒有正確顯示 Change-Id，我不知道問題發生的原因。 > > $\to$ 使用 `git rebase -i`，修改 commit message，接著 Git hooks 應該就會生效 > > 問題已解決，我先嘗試 `git rebase -i` 的方式，但沒有效果，後來使用 `git reset --hard HEAD~2` 將這兩則 commit message 刪除後重新 push ，參見 [額外問題紀錄-處理 commit message 遺失 Change-Id 的錯誤](##額外問題紀錄)。 #### 執行 qtest 時發現錯誤 > commit [a61a1d0](https://github.com/yy214123/lab0-c/commit/a61a1d04c519c0a7f9d61ccce643241dae3e4757) 專案中的 `qtest` 執行檔提供了方便的測試工具，可用於驗證各函式實作的正確性，對應 `q_insert_head` 及 `q_insert_tail` 的命令分別為 `ih` 及 `it`： ```shell $ ./qtest cmd> new l = [] cmd> ih xxx ERROR: Need to allocate and copy string for new queue element l = [xxx] cmd> it xxx ERROR: Need to allocate and copy string for new queue element l = [$��� xxx] ``` 從結果可以看出，出現了錯誤訊息 "ERROR: Need to allocate and copy string for new queue element"，而且佇列元素還出現了亂碼。為了確定這個錯誤訊息出現在程式碼的哪個部分，我使用 grep 命令進行搜尋： ```shell $ grep -rn "ERROR: Need to allocate and copy" grep: qtest: binary file matches qtest.c:247: "ERROR: Need to allocate and copy string for new " grep: qtest.o: binary file matches ``` 在 `qtest.c` 中： ```c if (!cur_inserts) { report(1, "ERROR: Failed to save copy of string in queue"); ok = false; } else if (r == 0 && inserts == cur_inserts) { report(1, "ERROR: Need to allocate and copy string for new " "queue element"); ok = false; break; } else if (r == 1 && lasts == cur_inserts) { report(1, "ERROR: Need to allocate separate string for each " "queue element"); ok = false; break; } lasts = cur_inserts; ``` `inserts` 變數存放 argv[1] 的記憶體位址（即 ih xxx 的 xxx）；而 `cur_inserts` 會在指定的佇列插入操作完成後，使用 `list_last_entry` 或 `list_first_entry` 讀取特定佇列節點中結構體的 value 值的記憶體位址。 而我原先的實作如下： ```c new_elem->value = s; ``` 這會導致 `inserts` 與 `cur_inserts` 相等，進而觸發對應的錯誤資訊，我進行修改： ```diff bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *new_elem = malloc(sizeof(element_t)); if (!new_elem) return false; - new_elem->value = s; + new_elem->value = malloc(sizeof(strlen(s) + 1)); + if (!new_elem->value) + return false; + strcpy(new_elem->value, s); list_add(&new_elem->list, head); return true; } ``` 但當執行 `git commit -a` 時出現下方資訊： ```shell Following files need to be cleaned up: queue.c Dangerous function detected in /home/boju/Linux2025/lab0-c/queue.c 51: strcpy(new_elem->value, s); 67: strcpy(new_elem->value, s); Read 'Common vulnerabilities guide for C programmers' carefully. https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml Running static analysis... queue.c:48:47: warning: Found calculation inside sizeof(). [sizeofCalculation] new_elem->value = malloc(sizeof(strlen(s) + 1)); ^ queue.c:64:47: warning: Found calculation inside sizeof(). [sizeofCalculation] new_elem->value = malloc(sizeof(strlen(s) + 1)); ^ Fail to pass static analysis. ``` 於是我再次修改，我將 `+1` 移出： ```diff bool q_insert_head(struct list_head *head, char *s) { ... - new_elem->value = malloc(sizeof(strlen(s) + 1)); + new_elem->value = malloc(sizeof(strlen(s)) + 1); ... } ``` 再次執行 `git commit -a` 時出現下方資訊： ```shell Following files need to be cleaned up: queue.c Dangerous function detected in /home/boju/Linux2025/lab0-c/queue.c 51: strcpy(new_elem->value, s); 67: strcpy(new_elem->value, s); Read 'Common vulnerabilities guide for C programmers' carefully. https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml Running static analysis... ``` 根據 [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 的描述： > The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp. 並且提到最佳的解決方式是使用 `strlcpy`。 ### q_remove_head & q_remove_tail > commit [f63c3aa](https://github.com/yy214123/lab0-c/commit/f63c3aa1d09f6ab0fe7e9cf94167013f346dd09d) ＆ commit [4123e63](https://github.com/yy214123/lab0-c/commit/4123e63d780c4e071b05c96d8dbcccf859daa7e0) 首先根據 `queue.h` 的描述，要注意這邊只是 remove 而非 delete，兩者差異如下： * remove：從佇列中移除指定的元素，但不釋放該元素所佔用的記憶體空間。 * delete：不僅從佇列中移除指定的元素，還會釋放其所佔用的記憶體空間。 > commit [2c2d15f](https://github.com/yy214123/lab0-c/commit/2c2d15fe588fa9c8424ab8c0a2cfd92c17adb965) 現有的實作存在瑕疵，導致在執行 `make test` 時出現以下的警告資訊： ```shell +++ TESTING trace trace-07-string: # Test of truncated strings: 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', and 'q_sort' ERROR: copying of string in remove_head overflowed destination buffer. ERROR: copying of string in remove_head overflowed destination buffer. ERROR: copying of string in remove_head overflowed destination buffer. ERROR: copying of string in remove_head overflowed destination buffer. ERROR: copying of string in remove_head overflowed destination buffer. Error limit exceeded. Stopping command execution, and quitting --- trace-07-string 0/6 ``` 首先搜尋相關的程式碼段落位置： ```shell $ grep -rn "copying of string in remove_head overflowed destination buffer" grep: qtest: binary file matches grep: qtest.o: binary file matches ``` 相關的程式碼如下： STRINGPAD 被定義為 1024，string_length 也被靜態宣告為 1024。 先為指標變數 `remove` 分配記憶體空間，大小為 1024 + 1024 + 1： ```c char *removes = malloc(string_length + STRINGPAD + 1); ``` 接下來看到這三行程式碼： ```c removes[0] = '\0'; memset(removes + 1, 'X', string_length + STRINGPAD - 1); removes[string_length + STRINGPAD] = '\0'; ``` 此時 `remove` 會被填充為 `\0XX,....XX\0`，然後透過下方的 `while` 迴圈檢查原先填充至 `STRINGPAD` 區段的 `X` 總數是否有變動，以判斷是否發生溢出： ```c /* Check whether padding in array removes are still initial value 'X'. * If there's other character in padding, it's overflowed. */ int i = string_length + 1; while ((i < string_length + STRINGPAD) && (removes[i] == 'X')) i++; if (i != string_length + STRINGPAD) { report(1, "ERROR: copying of string in remove_head overflowed " "destination buffer."); ok = false; } else { report(2, "Removed %s from queue", removes); } ``` 看到下方的程式碼，之前提過 string_length 被靜態宣告為 1024。 ```c re = pos == POS_TAIL ? q_remove_tail(current->q, removes, string_length + 1) : q_remove_head(current->q, removes, string_length + 1); ``` 因此我之前實作的錯誤在於，我不小心覆蓋了 caller 的 buffersize，應進行如下修正： ```diff element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; struct list_head *rm_node = head->next; element_t *rm_elem = list_entry(rm_node, element_t, list); - bufsize = strlen(rm_elem->value) + 1; strlcpy(sp, rm_elem->value, bufsize); list_del(rm_node); return rm_elem; } ``` #### 註解修正 > [sysprog21 #218](https://github.com/sysprog21/lab0-c/pull/218) 在 `queue.h` 中可以看到本作業各個函式的細節說明，我注意到： ```c /** * q_insert_head() - Insert an element in the head * @head: header of queue * @s: string would be inserted * ... */ bool q_insert_head(struct list_head *head, char *s); /** * q_insert_tail() - Insert an element at the tail * @head: header of queue * @s: string would be inserted * ... */ bool q_insert_tail(struct list_head *head, char *s); /** * q_remove_head() - Remove the element from head of queue * @head: header of queue * @sp: string would be inserted * @bufsize: size of the string * ... */ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize); /** * q_remove_tail() - Remove the element from tail of queue * @head: header of queue * @sp: string would be inserted * @bufsize: size of the string ... */ element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize); ``` 其中對於 `sp` 的描述與 q_insert_head 及 q_insert_head 中對於 `s` 的描述相同，但實際上 `sp` 並沒有進行插入的動作，詢問授課老師後，可提交 pull request 以修正此錯誤。 由於我沒有提交 pull request 的經驗，授課老師提供 [About pull requests](https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests?fbclid=IwZXh0bgNhZW0CMTAAAR2Z4ULHt9q_xnnR7lFconZ1q_BYXTKwjSYviUs6OZPxf2GhW7W7u2Lw3u4_aem_wnQXwBYyCBFe5u2hnxC09g) 指南，讓我進一步熟悉相關流程。 根據指南描述： > A pull request is a proposal to merge a set of changes from one branch into another. In a pull request, collaborators can review and discuss the proposed set of changes before they integrate the changes into the main codebase. Pull requests display the differences, or diffs, between the content in the source branch and the content in the target branch. 目前的分支包含了 queue.c 內所有函式的功能修改。如果在此分支上進行註解修改並提交 pull request，這些變更也會一併提交，因此應該建立一個新的分支。 ```shell $ git remote -v origin git@github.com:yy214123/lab0-c.git (fetch) origin git@github.com:yy214123/lab0-c.git (push) ``` 目前只有我 forked 的 repository，輸入下列命令新增： ```shell $ git remote add upstream git@github.com:sysprog21/lab0-c.git ``` 此時就會看到： ```shell $ git remote -v origin git@github.com:yy214123/lab0-c.git (fetch) origin git@github.com:yy214123/lab0-c.git (push) upstream git@github.com:sysprog21/lab0-c.git (fetch) upstream git@github.com:sysprog21/lab0-c.git (push) ``` 接著在這個乾淨的 repository 新增分支： ```shell $ git checkout -b fix-comment-errors upstream/master branch 'fix-comment-errors' set up to track 'upstream/master'. Switched to a new branch 'fix-comment-errors' ``` 切換到這個分支後，本地端的檔案會恢復乾淨： ```shell $ git diff ``` 此時就可以進行對應的註解修正。 但當我想要提交時遇到下方問題： ```shell $ git commit -a Following files need to be cleaned up: queue.h [!] You are not allowed to change the header file queue.h or list.h ``` 詢問授課老師後，老師指出須產生新的 SHA-1 checksum。 原始的 SHA-1 checksum 如下： ```shell $ git show HEAD:queue.h | sha1sum db6784ff3917888db4d1dceaa0570d99ed40e762 ``` 我修改 `queue.h` 後其 SHA-1 checksum 如下： ```shell $ git hash-object queue.h bcd1088ee2066de45069ea164f67fac5e93119c0 ``` 使用 `grep` 命令搜尋： ```shell $ grep -R "db6784ff3917888db4d1dceaa0570d99ed40e762" . ./scripts/checksums:db6784ff3917888db4d1dceaa0570d99ed40e762 queue.h ``` 對 `checksum` 檔案進行修改： ```diff - db6784ff3917888db4d1dceaa0570d99ed40e762 queue.h + bcd1088ee2066de45069ea164f67fac5e93119c0 queue.h 9be9666430f392924f5d27caa71a412527bf9267 list.h 3bb0192cee08d165fd597a9f6fbb404533e28fcf scripts/check-commitlog.sh ``` 此時提交依然出現： ```shell $ git commit -a Following files need to be cleaned up: queue.h [!] You are not allowed to change the header file queue.h or list.h ``` 後來發現是我用於查詢修改後的 SHA-1 checksum 有誤，不應該使用： ```shell $ git hash-object queue.h ``` 而是： ```shell $ sha1sum queue.h ok 07:44:03 PM 45da6585400a15237f09d896bbb807f85f449e92 queue.h ``` 再次修改 `checksum` 檔案： ```diff - bcd1088ee2066de45069ea164f67fac5e93119c0 queue.h + 45da6585400a15237f09d896bbb807f85f449e92 queue.h 9be9666430f392924f5d27caa71a412527bf9267 list.h 3bb0192cee08d165fd597a9f6fbb404533e28fcf scripts/check-commitlog.sh ``` 此時執行 `git commit -a` 就不會出現相關警告了，撰寫完 commit message 後，須先提交這個分支： ```shell $ git push origin fix-comment-errors ``` 再用此分支發 pull request 到 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c)。 ### q_delete_mid 根據 [LeetCode 2095](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/description/) 的說明，中間節點定義為第 $\lfloor \frac{n}{2} \rfloor$ 個節點，其中 n 為佇列長度，並且是基於 0-based indexing。 - [ ] 方法一 > [程式碼](https://gist.github.com/yy214123/ee1f039c391e812f39f7b2033ba83980) 最基本的方式是先取得佇列的長度（可使用 q_size 函式 <s>函數</s>）。接著，使用除法運算計算欲刪除的元素索引，然後逐一走訪佇列，最終刪除對應的佇列元素。 :::danger 詳閱[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)，以得知 function 的翻譯。 > 已修正，應該使用函式而非函數 ::: - [ ] 方法二 > [程式碼](https://gist.github.com/yy214123/c17b16705af55ab9fbda2081cae82bf8) 另一個策略是使用快慢指標。慢指標每次走訪一個節點，而快指標每次走訪兩個節點。當快指標到達佇列的最後一個節點時，慢指標會恰好位於要刪除的中間節點。計算走訪次數如下： 快指標：$n$ 次 慢指標：$\frac {n}{2}$ 次 總共：$\frac {3n}{2}$ 次 - [ ] 方法三 > commit [684ea99](https://github.com/yy214123/lab0-c/commit/684ea99efae6625c0f0bde158c3029389d5edc1b) :::danger "access" 譯作「存取」，而非「訪問」(visit)。 > 已修正。 ::: > commit [4555913](https://github.com/yy214123/lab0-c/commit/4555913abece0072be87a283d8d45b67f950dba4) 在 3 月 27 日的直播課程中獲得了老師的建議，由於在合併排序演算法中也需要使用搜尋中間節點的操作，因此我將相關程式碼邏輯獨立出來成為一個函式，這樣可以實現程式碼的重用。 考慮到使用的資料結構是環狀雙向鏈結串列，我們可以使用兩個指標：一個指標每次存取 <s>訪問</s> 下一個元素，另一個指標則返回到前一個元素。如下圖所示： ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3; 4; 5; } { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> 4 -> 5 -> head [dir=both]; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; p1 -> 1 [color=red]; p2 -> 5 [color=red]; } ``` ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3; 4; 5; } { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> 4 -> 5 -> head [dir=both]; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; p1 -> 2 [color=red]; p2 -> 4 [color=red]; } ``` ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3; 4; 5; } { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> 4 -> 5 -> head [dir=both]; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; p1 -> 3 [color=red]; p2 -> 3 [color=red]; } ``` 再次計算其走訪次數： 指標 1：$\frac {n}{2}$ 次 指標 2：$\frac {n}{2}$ 次 總共：$n$ 次 相比之前快慢指標的策略，走訪總次數減少了 $\frac {n}{2}$ 次。 在實作過程中，需要特別考慮到佇列元素為偶數的情況。在這種情況下，兩個指標不會指向同一個佇列節點，而是會交錯，如下所示： ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3; 4;} { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> 4 -> head [dir=both]; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; p1 -> 1 [color=red]; p2 -> 4 [color=red]; } ``` ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3; 4;} { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> 4 -> head [dir=both]; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; p1 -> 2 [color=red]; p2 -> 3 [color=red]; } ``` ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3; 4;} { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> 4 -> head [dir=both]; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; p1 -> 3 [color=red]; p2 -> 2 [color=red]; } ``` 因此，我在實作中使用了以下邏輯進行判斷： ```ｃ while ((access_next != access_prev) && (access_prev->next != access_next)) { access_next = access_next->next; access_prev = access_prev->prev; } ``` 這樣不論佇列中元素的總數是奇數還是偶數，都能夠正確地實現其功能。 #### TODO：效能比較 目前上述各種方法均是基於理論分析提出，授課老師在 3 月 20 日的直播課程中指出，可以進行相應的效能分析。直播課程提到可以將額外的程式碼使用 GitHub Gist 展示，我將會提交方法一和方法二的程式碼（已更新於上方）。 根據去年的經驗，在 `qtest` 中使用的 `q_show` 會顯著影響效能分析的結果：若開啟 `q_show`，執行結果為： ```shell $ ./qtest cmd> new l = [] cmd> time it xxx 10000000 l = [xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx ... ] Delta time = 0.791 cmd> time dm l = [xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx xxx ... ] Delta time = 0.496 ``` 若關閉q_show，執行結果為： ```shell $ ./qtest cmd> new cmd> time it xxx 10000000 Delta time = 0.613 cmd> time dm Delta time = 0.143 ``` 因此，我另準備了一個分支，將 `q_show` 註解掉以便於實驗進行： ```diff - q_show(3); + // q_show(3); ``` 我先寫了一個 `Python` 檔案來生成測試資料： ```py import random import os os.makedirs("cmds", exist_ok=True) for i in range(1000): size = random.randint(100000, 1000000) with open(f"cmds/rand_dm_{i}.cmd", "w") as f: f.write(f"new\n") f.write(f"it xxx {size}\n") f.write(f"time dm\n") f.write(f"free\n") ``` 這將生成 1000 筆尺寸在 100K 至 1000K 之間的佇列，最低從 100K 開始是因為若低於 100K，顯示的時間會為 0 秒，經過篩選發現只有大於 100K的數據才會顯示時間。接著，我用一個腳本去執行這些檔案，並將結果記錄於 CSV 中。 ```shell #!/bin/bash mkdir -p results_10F echo "run_id,queue_size,time_s" > results_10F/timing_v3.csv results=() for i in $(seq 0 999); do cmdfile="cmds/rand_dm_${i}.cmd" [ -f "$cmdfile" ] || continue output=$(./qtest -f "$cmdfile") size=$(grep "it xxx" "$cmdfile" | awk '{print $3}') time=$(echo "$output" | grep -E "Delta time" | awk '{print $4}') if [[ -z "$time" ]]; then time="-1" fi results+=("$i,$size,$time") done for line in "${results[@]}"; do echo "$line" done >> results_10F/timing_v3.csv ``` 隨後，我使用 `gnuplot` 將三種方法的執行時間呈現如下圖： ![q_delete_mid_perf](https://hackmd.io/_uploads/Bkc1tUW6kg.png) 從結果來看，方法三是最穩定且平均執行時間最低的。不過，有一部分引起了我的好奇，藍色和綠色的部分隨著佇列尺寸增大而發散的情況愈加明顯，在佇列尺寸相近的情況下，時間上卻有兩倍的差距，我尚未搞懂原因。 ![q_delete_mid_perf_v1v2](https://hackmd.io/_uploads/r1Mw5UWaJl.png) 目前的時間顯示精度只到小數點後三位，於是我嘗試放大精度： ```diff static bool do_time(int argc, char *argv[]) { double delta = delta_time(&last_time); bool ok = true; if (argc <= 1) { double elapsed = last_time - first_time; - report(1, "Elapsed time = %.3f, Delta time = %.3f", elapsed, delta); + report(1, "Elapsed time = %.3f, Delta time = %.10f", elapsed, delta); } else { ok = interpret_cmda(argc - 1, argv + 1); if (block_flag) { block_timing = true; } else { delta = delta_time(&last_time); - report(1, "Delta time = %.3f", delta); + report(1, "Delta time = %.10f", delta); } } return ok; } ``` ![q_delete_mid_perf_10](https://hackmd.io/_uploads/SkAnD_bpJx.png) 接著，我使用 [taskset](https://man7.org/linux/man-pages/man1/taskset.1.html) 將程式碼的執行限制於給定的 CPU 核，這時發現發散幾乎消失，三種方法均非常穩定，並未隨佇列尺寸增大而出現震盪： ![q_delete_mid_perf](https://hackmd.io/_uploads/S1ALCd-aJl.png) 為進一步推導起因，我使用 `perf` 進行分析，比較開關 `taskset` 對效能指標的具體影響，這裡我隨意選了一個樣本數較多的測試資料，各進行 `10` 次測試觀察結果。 * 未開 taskset 的執行結果如下： ```shell $ for i in {1..10}; do perf stat -e cache-references,cache-misses,cycles,instructions ./qtest -f cmds/rand_dm_555.cmd 2>> perf_no_taskset.log done ``` | run | cache_references | cache_misses | cache_miss_rate | cycles | instructions | ipc | time_elapsed | user_time | sys_time | |---------|------------------|---------------|------------------|-----------|---------------|------|---------------|------------|----------| | 1 | 17241656 | 9892382 | 57.37 | 826228499 | 1923288981 | 2.33 | 0.339832 | 0.179012 | 0.191972 | | 2 | 14612480 | 8109421 | 55.50 | 795509847 | 1700698307 | 2.14 | 0.356477 | 0.204828 | 0.185673 | | 3 | 23332294 | 12157972 | 52.11 |1107577268 | 2504119125 | 2.26 | 0.335217 | 0.201407 | 0.163024 | | 4 | 19864791 | 11531163 | 58.05 | 930359706 | 2187284696 | 2.35 | 0.340756 | 0.194819 | 0.175354 | | 5 | 17080863 | 10516592 | 61.57 | 836851854 | 1979001851 | 2.36 | 0.339477 | 0.186157 | 0.185172 | | 6 | 16963089 | 10041551 | 59.20 | 815348651 | 1933153510 | 2.37 | 0.338824 | 0.181302 | 0.189109 | | 7 | 16047071 | 10110594 | 63.01 | 782730855 | 1884546384 | 2.41 | 0.341982 | 0.195674 | 0.177970 | | 8 | 16136009 | 10222131 | 63.35 | 780970954 | 1873592083 | 2.40 | 0.347788 | 0.191405 | 0.191768 | | 9 | 16059625 | 8368806 | 52.11 | 877706813 | 1839762446 | 2.10 | 0.353229 | 0.199560 | 0.185950 | | 10 | 17805306 | 10371304 | 58.25 | 809727991 | 1909271619 | 2.36 | 0.342096 | 0.200188 | 0.174454 | * 開 `taskset` 的執行結果如下：： ```shell $ for i in {1..10}; do taskset -c 0 perf stat -e cache-references,cache-misses,cycles,instructions ./qtest -f cmds/rand_dm_555.cmd 2>> perf_with_taskset.log done ``` | run | cache_references | cache_misses | cache_miss_rate | cycles | instructions | ipc | time_elapsed | user_time | sys_time | |---------|------------------|---------------|------------------|-------------|---------------|------|---------------|------------|----------| | 1 | 32026149 | 6741449 | 21.05 | 1446414938 | 2584233584 | 1.79 | 0.268393 | 0.188281 | 0.078488 | | 2 | 32269571 | 6576403 | 20.38 | 1444059468 | 2583152521 | 1.79 | 0.268202 | 0.167397 | 0.098835 | | 3 | 32133614 | 6689984 | 20.82 | 1448809063 | 2583787717 | 1.78 | 0.269490 | 0.173320 | 0.093786 | | 4 | 31761274 | 6846540 | 21.56 | 1442830213 | 2582785998 | 1.79 | 0.267744 | 0.177639 | 0.088509 | | 5 | 31735067 | 7403465 | 23.33 | 1448393784 | 2583511397 | 1.78 | 0.269289 | 0.179936 | 0.087251 | | 6 | 31906122 | 6534310 | 20.48 | 1433374836 | 2579936789 | 1.80 | 0.266988 | 0.170548 | 0.093753 | | 7 | 32207039 | 6501005 | 20.19 | 1440156894 | 2583018317 | 1.79 | 0.268275 | 0.186147 | 0.079369 | | 8 | 31717134 | 6502431 | 20.50 | 1438018532 | 2577943850 | 1.79 | 0.267203 | 0.172772 | 0.092433 | | 9 | 31970193 | 6832129 | 21.37 | 1447859351 | 2580957381 | 1.78 | 0.269134 | 0.183556 | 0.083528 | | 10 | 31956559 | 6654394 | 20.82 | 1443032754 | 2580864068 | 1.79 | 0.269123 | 0.183641 | 0.082409 | 對比結果顯示，開啟 `taskset` 後的 miss rate 顯著下降，並且觀察到兩個表格中執行時間的部分： | taskset | min | max | 波動 | | -------- | -------- | -------- | -------- | | 關閉 | 0.335217 | 0.356476 | 0.0213 | | 打開 | 0.266988 | 0.269489 | 0.0025 | 可以看到，震蕩幅度相差接近 10 倍，這也就是為何實驗初期出現嚴重的發散情況。 #### 註解修正 > [sysprog21 #219](https://github.com/sysprog21/lab0-c/pull/219) ```shell /** * q_delete_mid() - Delete the middle node in queue * @head: header of queue * * The middle node of a linked list of size n is the * ⌊n / 2⌋th node from the start using 0-based indexing. * If there're six elements, the third member should be returned. * * Reference: * https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ * * Return: true for success, false if list is NULL or empty. */ bool q_delete_mid(struct list_head *head); ``` 此函示為布林型別，會根據是否成功刪除佇列的中間節點來回傳 ture 或 false，在原先的註解有一處錯誤："If there're six elements, the third member should be returned." 應該將 returned 改為 deleted 才正確，因為該節點僅被刪除並沒有作為函式的回傳對象。 ### q_delete_dup > commit [2f84552](https://github.com/yy214123/lab0-c/commit/2f84552c32f396bfa90aae8201b31fd4bf31d5a8) 我一開始的想法如下： ```c bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head || list_empty(head)) return false; struct list_head *curr_1,*curr_2; list_for_each(curr_1,head){ curr_2 = curr_1->next; list_for_each(curr_2,head){ if(list_entry(curr_1, element_t, list)->value == list_entry(curr_2, element_t, list)->value){ list_del(curr_2); q_release_element(list_entry(curr_2, element_t, list)); } } } return true; } ``` 但這邊有個致命性的錯誤，我在內層迴圈使用了 `list_for_each`，這會導致佇列中的重複字串若是相鄰節點，則刪除後會導致無法繼續存取下一個元素，並且我宣告了 `curr_2 = curr->next`，這個行為也沒有意義，因為查看 ` list_for_each` 可知： ```c #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) ``` 該巨集會初始化為 `head->next`，如此會造成 Segmentation fault。應該要搭配 for 迴圈來實作。 使用 `qtest` 進行測試時我發現奇怪的地方，當重複的節點是相鄰的： ```shell $ ./qtest cmd> new l = [] cmd> it 1 l = [1] cmd> it 1 l = [1 1] cmd> it 2 l = [1 1 2] cmd> it 2 l = [1 1 2 2] cmd> dedup l = [] ``` 此時沒有問題，但當重複節點不是相鄰的： ```shell cmd> it 1 l = [1] cmd> it 2 l = [1 2] cmd> it 1 l = [1 2 1] cmd> it 2 l = [1 2 1 2] cmd> dedup ERROR: Duplicate strings are in queue or distinct strings are not in queue l = [] ``` 最後的結果雖正確，但卻先出現了 "ERROR: Duplicate strings are in queue or distinct strings are not in queue" 這段警告訊息。 詢問授課老師後，此題目有預設佇列已排序好，所以我的實作有改善空間，目前使用內外兩層迴圈去走訪節點刪除，時間複雜度為：$O(n^2)$，但考慮到佇列已排序，可以優化使時間複雜度降為：$O(n)$。 ### q_swap > commit [09d310d](https://github.com/yy214123/lab0-c/commit/09d310de7e8a53af78d7caf988eea3005673f919) 其實這個作法是 `q_reversek` 的一個特例，因此我們可以直接調用 `q_reversek`，並將 `k` 設定為 `2` 即可。 ### q_reverse > commit [075d580](https://github.com/yy214123/lab0-c/commit/075d580743d9060a0f3d6a3e826d95d300049610) > commit [641e410](https://github.com/yy214123/lab0-c/commit/641e410ddc9684281f5c3639dca19372d1857831) > 使用了 list_move 來簡化程式碼。 在實作 shuffle 時獲得了一個啟發，原先的交換方式是去改變串列節點的結構來達成此實作，而既然每個節點都內嵌在 `element_t` 這個結構體，可不可以只對值做交換而不去改變串列節點的結構呢？於是我做了以下的實驗。 > [程式碼](https://gist.github.com/yy214123/ca9a571d5da6a478587bd6fca084d9c2) 測試資料準備： 隨機生成 100 個長度介於 1000000 ~ 10000000 間的佇列，其中每個佇列元素的字串均相同（16個字元），並紀錄其執行 `reverse` 時所花的時間。且有使用 taskset 將程式碼的執行限制於給定的 CPU 核。 結果： ![comparison](https://hackmd.io/_uploads/Hk-n44nT1l.png) 以結果來看，僅對值交換一定程度上有改善執行時間，且觀察後可發現會隨著佇列尺寸變大，兩者間的差距也逐漸變大。 ### q_reverseK > commit [069f235](https://github.com/yy214123/lab0-c/commit/069f235a8e87b43be94bd582b459be997045d90e) > commit [774d3bf](https://github.com/yy214123/lab0-c/commit/774d3bfa1bf0735e74fe85c7a9be298714f7de4d) > 此次更新對於 k 的某些邊緣情況進行了優化，當 k 等於 1 時，函式將直接結束；而當 k 與佇列的長度相符時，將調用 q_reverse。 > ### q_ascend & q_descend > commit [d6d8c49](https://github.com/yy214123/lab0-c/commit/d6d8c492977dc0bcdd06e2096c8b22b7c64380a4) & commit [bd72375](https://github.com/yy214123/lab0-c/commit/bd7237530da7b27e516438406d6ce8e409ff082a) > 我先完成了 `q_ascend` 的實作，基本上這邊的整體程式架構與 `q_delete_dup` 雷同，我們可以注意到一系列數字若是以降序排列，反轉後將會變成升序。因此，我們可以首先使用 `q_reverse` 將佇列反轉，接著呼叫 `q_ascend` 來進行排序，最後再呼叫一次 `q_reverse` 就能實現所需的功能。 > commit [4fd07ed](https://github.com/yy214123/lab0-c/commit/4fd07edace0e2e523a8a0136ee74161fde378a08) > 對程式碼進行優化，使檢查提早結束，不需要每次都走訪到最後一個節點。gi > commit [27345e0](https://github.com/yy214123/lab0-c/commit/27345e08da41c9ef29aeb146c887af15c4d30c54) 先前的實作有缺陷，並不能透過調用佇列反轉及 `q_ascend`，來實現 `q_descend`，假設現有一個佇列：`3 -> 1 -> 2`，原因如下： `q_ascend` 定義（從左到右看）： > 移除任何一個節點，如果該節點右側存在一個比它更小的數字。 | 節點 | 右邊節點 | 是否右邊有更小的數字 | 是否刪除 | | -------- | ------- | -------- | -------- | | 3 | 1,2 | 有，1<3 | 刪除 | | 1 | 2 | 無 | 不刪除 | | 2 | no | 無 | 不刪除 | 正確結果：`1 -> 2` `q_descend` 定義（從左到右看）： > 移除任何一個節點，如果該節點右側存在一個比它更大的數字。 | 節點 | 右邊節點 | 是否右邊有更小的數字 | 是否刪除 | | -------- | ------- | -------- | -------- | | 3 | 1,2 | 無 | 不刪除 | | 1 | 2 | 有，2>1 | 刪除 | | 2 | no | 無 | 不刪除 | 正確結果：`3 -> 2` 按照原先的程式邏輯，首先先將佇列反轉，變成 `2 -> 1 -> 3`，執行 `q_ascend`： | 節點 | 右邊節點 | 是否右邊有更小的數字 | 是否刪除 | | -------- | ------- | -------- | -------- | | 2 | 1,3 | 有，1<2 | 刪除 | | 1 | 3 | 無 | 不刪除 | | 3 | no | 無 | 不刪除 | 結果為：`1 -> 3`，在執行一次佇列反轉：`3 -> 1`，與正確結果不符合。 ### q_sort > commit [b484286](https://github.com/yy214123/lab0-c/commit/b484286db17ac2702adc9f100183fd5645113bec) 去年直接將 `merge sort`、`tim sort` 等排序算法的實作寫在 `queue.c` 中，但發現這樣會使程式碼變得很混亂，因此今年額外新增了 `sort.c` 檔案。 > commit [49e47aa](https://github.com/yy214123/lab0-c/commit/49e47aa5332e02b5277d94ef85d2900ed5568449) 引入 lib/list_sort.c到 lab0-c 專案 > commit [39829a8](https://github.com/yy214123/lab0-c/commit/39829a8a4d2c2de1c80cb526ea26894a4b8124fe) > 實作非遞迴版本的合併排序。 #### TODO：排序法效能比較 ##### 準備測試資料 去年在進行這個作業時，我在這一部分卡住了，讓我有許多好奇的點：測試資料的準備以及相關的統計分析。我為什麼設計了1000筆測試資料，而每筆又是由長度介於5到15的隨機字串組成，數量從1K到1000K，會不會其實不需要這麼多？ **隨機字串長度設計：** 隨機字串的長度我參考了[《Introduction to Information Retrieval》](https://nlp.stanford.edu/IR-book/information-retrieval-book.html)這本書的第五章第二節，書中提到英文中一個詞的平均長度約為八個字符，因此我將隨機字串的長度設為8，字元範圍為A到Z以及小寫字母a到z。 **單一樣本的元素數目：** 至於單一樣本的元素數量，我參考了論文[《Engineering a Sort Function》](https://gallium.inria.fr/~maranget/X/421/09/bentley93engineering.pdf)中關於比較排序的段落： :::info To assess timing, we ran the programs on computers of disparate architectures: a VAX 8550 and a 40MHz MIPS R3000 (with 64-kilobyte data and instruction caches and a sec- ondary cache of one megabyte), compiling with lcc on both. Table II reports times in sec- onds to sort 10,000 integers chosen randomly from the range 0 to 999,999 on each of the testbed’s six input types. Each time is the average of ten runs. ::: 該段描述了他們在不同架構的電腦上運行程序來測試時間，包括VAX 8550和40MHz MIPS R3000，結果顯示在範圍 0 到 999,999 中隨機選擇 10000 個整數進行排序的時間。我決定將元素數量提高到 1000K，因為相較於當時的設備，我的 CPU 效能更強。 在實驗中我遇到了一些問題，當使用list_sort時可以順利記錄時間，但切換到merge_sort時出現了： ```shell ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient ``` 不過這個情況僅在元素數量為 1000K 時發生，降低到 500K 後就沒有這個警報，由於需要進一步分析，我只能暫時降低這個數字。這也意味著我目前的 merge_sort 在效率上還有很大的改進空間，雖然理論上的時間複雜度與 list_sort 相同，但實際效率卻有差異。 **樣本數：** 根據中央極限定理，當樣本數量大於等於 30 時，樣本的分佈相對穩定。因此我決定將樣本數設為 100。 ##### 結果 > 所有測試均使用taskset執行。 ![image](https://hackmd.io/_uploads/HyPDOS9pyl.png) | 排序法 | 平均值 | 標準差 | 變異數 | -------- | -------- | -------- | -------- | | list_sort | 0.189545 s | 0.007821 s | 0.000061 | | merge_sort | 0.719091 s | 0.017078 s | 0.000292 | 可以明顯看到，list_sort 比 merge_sort來得更快，平均僅需 26% 的時間，且 list_sort的穩定性也較高。 接下來，我考慮不同分佈的測試資料，這次使用已排序好的資料進行測試： ![image](https://hackmd.io/_uploads/HJNIXI9pkg.png) | 排序法 | 平均值 | 標準差 | 變異數 | -------- | -------- | -------- | -------- | | list_sort | 0.248384 s | 0.007395 s | 0.000055 | | merge_sort | 0.108697 s | 0.004558 s | 0.000021 | 這裡顯示 merge_sort 在已排序資料下更快且穩定，這現象的原因在於我對 merge_sort 加入了額外的判斷邏輯，如下： ```c static int is_list_sorted(struct list_head *head, list_cmp_func_t cmp) { if (list_empty(head) || list_is_singular(head)) return 1; struct list_head *node = head->next; while (node->next != head) { if (cmp(node, node->next) > 0) return 0; node = node->next; } return 1; } ``` 我們可以將這次的 list sort 結果與前一個實驗 list sort 結果疊加來看： ![image](https://hackmd.io/_uploads/Sk2jSL561l.png) 從這邊可以發現有議題值得討論： * 此結果顯示 list_sort 對這種特例並未進行優化，若對 list_sort 進行已排序資料的優化，則每次排序前都需先遍歷一次，這對隨機資料的效能會有什麼影響呢？ ### q_merge > commit [6ab9c8f](https://github.com/yy214123/lab0-c/commit/6ab9c8f7149d83c33c3a7814f530b15ffbfccc5d) 這邊一開始在實作時，使用測試程式時一直出現錯誤資訊，原先的程式碼如下： ```c /* Merge all the queues into one sorted queue, which is in ascending/descending * order */ int q_merge(struct list_head *head, bool descend) { // https://leetcode.com/problems/merge-k-sorted-lists/ if (!head) return 0; if (head->next == head) return q_size(list_entry(head, queue_contex_t, chain)->q); struct list_head *queue = head->next; queue_contex_t *curr_1 = list_entry(queue, queue_contex_t, chain); while (queue!= head) { queue_contex_t *curr_2 = list_entry(queue->next, queue_contex_t, chain); list_splice_tail_init(curr_2->q, curr_1->q); queue = queue->next; } curr_1->size = q_size(curr_1->q); q_sort(curr_1->q, descend); return curr_1->size; } ``` 思考後發現是迴圈中止條件的設定有誤，假設目前有三個佇列需要合併。 - [ ] 第一次迭代時： ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3;} { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> head [dir=both]; p1 [label="*curr1", shape=box]; p2 [label="*curr2", shape=box]; p3 [label="*queue", shape=box]; p1 -> 1 [color=red]; p2 -> 2 [color=red]; p3 -> 1 [color=blue]; } ``` 這邊用加號來代表完成合併 ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3;} { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> head [dir=both]; p1 [label="*curr1+*curr2", shape=box]; p2 [label="*curr2", shape=box]; p3 [label="*queue", shape=box]; p1 -> 1 [color=red]; p2 -> 2 [color=red]; p3 -> 1 [color=blue]; } ``` - [ ] 第二次迭代時： ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3;} { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> head [dir=both]; p1 [label="*curr1+*curr2", shape=box]; p2 [label="*curr2", shape=box]; p3 [label="*queue", shape=box]; p1 -> 1 [color=red]; p2 -> 3 [color=red]; p3 -> 2 [color=blue]; } ``` ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3;} { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> head [dir=both]; p1 [label="*curr1+*curr2+*curr3", shape=box]; p2 [label="*curr2", shape=box]; p3 [label="*queue", shape=box]; p1 -> 1 [color=red]; p2 -> 3 [color=red]; p3 -> 2 [color=blue]; } ``` - [ ] 第三次迭代時： ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3;} { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> head [dir=both]; p1 [label="*curr1+*curr2+*curr3", shape=box]; p2 [label="*curr2", shape=box]; p3 [label="*queue", shape=box]; p1 -> 1 [color=red]; p2 -> head [color=red]; p3 -> 3 [color=blue]; } ``` 這邊會把 `head` 也加進來，但實際上 `head` 並沒有嵌入 `q_context_t` 結構體，所以會出現錯誤。 ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3;} { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> head [dir=both]; p1 [label="*curr1+*curr2+*curr3", shape=box]; p2 [label="*curr2", shape=box]; p3 [label="*queue", shape=box]; p1 -> 1 [color=red]; p2 -> head [color=red]; p3 -> 3 [color=blue]; } ``` 此處實作有優化的空間，Merge k Sorted Lists，還在參考 [案例探討: LeetCode 21. Merge Two Sorted Lists](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 進行改善中。 ## 研讀 〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉 在完成前面數個指定的佇列操作後，此時執行 `make test`，其分數顯示如下： ```shell $ make test ... +++ TESTING trace trace-17-complexity: # Test if time complexity of 'q_insert_tail', 'q_insert_head', 'q_remove_tail', and 'q_remove_head' is constant ERROR: Probably not constant time or wrong implementation ERROR: Probably not constant time or wrong implementation Probably constant time Probably constant time --- trace-17-complexity 0/5 --- TOTAL 95/100 make: *** [Makefile:62: test] Error 1 ``` 目前還沒有辦法獲得滿分，先追蹤專案中相關的程式碼以便確認問題所在處。 ### lab0-c 相關程式碼追蹤 從 `test_const` 開始： ```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; } ``` 看到外層迴圈，在這邊因為 `TEST_TRIES` 被定義為 10，所以針對個別指定的佇列操作常數時間判定，最多會有十輪，每輪中會進行多次測量，已確保樣本數充沛（內層的迴圈）。 如何測量時間呢？我們進一步追蹤 `doit` 這個函式： ```c static bool doit(int mode) { int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t)); int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t)); int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t)); uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t)); uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t)); if (!before_ticks || !after_ticks || !exec_times || !classes || !input_data) { die(); } prepare_inputs(input_data, classes); bool ret = measure(before_ticks, after_ticks, input_data, mode); differentiate(exec_times, before_ticks, after_ticks); update_statistics(exec_times, classes); ret &= report(); free(before_ticks); free(after_ticks); free(exec_times); free(classes); free(input_data); return ret; } ``` 這邊總共有幾個關鍵步驟，我們依序追蹤，首先是 `prepare_input`： ```c void prepare_inputs(uint8_t *input_data, uint8_t *classes) { randombytes(input_data, N_MEASURES * CHUNK_SIZE); for (size_t i = 0; i < N_MEASURES; i++) { classes[i] = randombit(); if (classes[i] == 0) memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE); } for (size_t i = 0; i < N_MEASURES; ++i) { /* Generate random string */ randombytes((uint8_t *) random_string[i], 7); random_string[i][7] = 0; } } ``` 每次測試都準備 N_MEASURES 筆資料，並隨機分類（class 0 或 class 1），第一個 for 迴圈與此次指定佇列的操作次數有關： `input_data` 會指向連續的記憶體空間，分為 150 個 chuck(每個 chuck 的大小為 2)。示意圖如下： ```graphviz digraph arrays { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray, fontname="Courier New"]; array0 [label="{chuck0 | { | }}"]; array1 [label="{chuck1 | { | }}"]; array2 [label="{chuck148 | { | }}"]; array3 [label="{chuck149 | { | }}"]; } ``` 接著會呼叫 `randombytes` 將這 300 bytes 進行填充： ```graphviz digraph arrays { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray, fontname="Courier New"]; array0 [label="{chunk0 | { 0x5F | 0x12 }}"]; array1 [label="{chunk1 | { 0xAC | 0xDE }}"]; array2 [label="{chunk148 | { 0x3D | 0xC1 }}"]; array3 [label="{chunk149 | { 0x88 | 0x0A }}"]; } ``` 接著會對每個 chunk 進行分類，若被分派程 class 0 則將其 2 bytes 清為 0，關鍵程式碼如下： ```c memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE); ``` ```graphviz digraph arrays { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray, fontname="Courier New"]; array0 [label="{chunk0（class 1） | { 0x5F | 0x12 }}"]; array1 [label="{chunk1 （class 0）| { 0x00 | 0x00 }}"]; array2 [label="{chunk148 （class 1）| { 0x3D | 0xC1 }}"]; array3 [label="{chunk149 （class 0）| { 0x00 | 0x00 }}"]; array0 -> array1 -> array2 -> array3 [style=invis]; } ``` 而第二個迴圈生成的就是這筆樣本插入的隨機字串。 下一個呼叫的函式是 `measure`，這邊假設我們進行的是 q_insert_head： ```c case DUT(insert_head): for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) { char *s = get_random_string(); dut_new(); dut_insert_head( get_random_string(), *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000); int before_size = q_size(l); before_ticks[i] = cpucycles(); dut_insert_head(s, 1); after_ticks[i] = cpucycles(); int after_size = q_size(l); dut_free(); if (before_size != after_size - 1) return false; } break; ``` 可以看到 `dut_insert_head` 有兩個傳入參數： > 參數一：透過 `get_random_string()` 去獲得該樣本對應的隨機字串（對應到 `prepare_inputs` 中第二個 for 迴圈）。 > 參數二：將個別 chunk 裡面的 2 bytes % 10000，可以得到介於 0~9999 的數值。 用 chunk 0 來舉例，就會是插入某個隨機字串至佇列頭部 0x5F12 % 10000 次。過程中透過 `before_tick` 與 `after_tick` 來紀錄起始與結束時間。 下一個呼叫的函式是 `differentiate`，其實就只是紀錄 `before_tick` 與 `after_tick` 間的差值，就是該樣本的執行時間。 ```graphviz digraph arrays { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray, fontname="Courier New"]; array0 [label="{before_tic | { 5s|...| 3s }}"]; array1 [label="{after_tick | { 6s |...| 9s }}"]; array2 [label="{exec_time | {6-5 |...| 9-3 }}"]; } ``` 最後呼叫的函式是 `update_statistics`： ```c static void update_statistics(const int64_t *exec_times, uint8_t *classes) { for (size_t i = 0; i < N_MEASURES; i++) { int64_t difference = exec_times[i]; /* CPU cycle counter overflowed or dropped measurement */ if (difference <= 0) continue; /* do a t-test on the execution time */ t_push(t, difference, classes[i]); } } ``` 呼叫 `t_push` 來將各個執行時間依序放入對應的資料結構中： ```c void t_push(t_context_t *ctx, double x, uint8_t class) { assert(class == 0 || class == 1); ctx->n[class]++; /* Welford method for computing online variance * in a numerically stable way. */ double delta = x - ctx->mean[class]; ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class]; ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]); } ``` 在各類別中，會獨立保存各自的平均值及平方差總和，這邊使用的是 Welford 演算法，不需要紀錄歷史資料即可更新： >當有新資料加入，先計算 delta：新資料值 - 過去歷史平均值， >接著更新平均值，新的平均值 = 過去歷史平均值 + delta / 資料總數。 舉例如下： * 假設現有資料為 4,8,12，則平均為 8，新加入了 16 這筆資料，先算 $delta = 16 - 8 = 8$。 * 更新平均值：$avg(new)= 8+8/4=10$，與實際平均值相同。 平方差總和同理： * 現有資料的平方差總和為 32，新加入了 16 這筆資料。 * 更新平方差總和： $\begin{split} m^2(new)&=32+8\cdot(16-10)=80 \\&= (4 - 10)^2 +(8 - 10)^2+(12 - 10)^2+(16 - 10)^2 \end{split}$ 經過上述步驟，我們現在擁有這些資料： 1. 這次 150 個樣本中被分派到 class 0 的平均值及平方差總和。 2. 這次 150 個樣本中被分派到 class 1 的平均值及平方差總和。 有了這些資料，在 `report` 中： ```c static bool report(void) { double max_t = fabs(t_compute(t)); double number_traces_max_t = t->n[0] + t->n[1]; double max_tau = max_t / sqrt(number_traces_max_t); printf("\033[A\033[2K"); printf("measure: %7.2lf M, ", (number_traces_max_t / 1e6)); if (number_traces_max_t < ENOUGH_MEASURE) { printf("not enough measurements (%.0f still to go).\n", ENOUGH_MEASURE - number_traces_max_t); return false; } /* max_t: the t statistic value * max_tau: a t value normalized by sqrt(number of measurements). * this way we can compare max_tau taken with different * number of measurements. This is sort of "distance * between distributions", independent of number of * measurements. * (5/tau)^2: how many measurements we would need to barely * detect the leak, if present. "barely detect the * leak" = have a t value greater than 5. */ printf("max t: %+7.2f, max tau: %.2e, (5/tau)^2: %.2e.\n", max_t, max_tau, (double) (5 * 5) / (double) (max_tau * max_tau)); /* Definitely not constant time */ if (max_t > t_threshold_bananas) return false; /* Probably not constant time. */ if (max_t > t_threshold_moderate) return false; /* For the moment, maybe constant time. */ return true; } ``` 這邊會透過 `t_compute` 去計算先前兩個類別的變異數： ```c double t_compute(t_context_t *ctx) { double var[2] = {0.0, 0.0}; var[0] = ctx->m2[0] / (ctx->n[0] - 1); var[1] = ctx->m2[1] / (ctx->n[1] - 1); double num = (ctx->mean[0] - ctx->mean[1]); double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]); double t_value = num / den; return t_value; } ``` 我統計非常爛，所以得先搞懂變異數是什麼，根據維基百科的描述，我的總結如下： :::danger 翻閱統計學教科書 > 已在下方說明。 ::: 變異數（Variance）是用來衡量一組數據的離散程度或波動幅度。換句話說，它告訴你： → 整體資料「偏離平均值有多遠」。 在這個實驗中，資料被分為兩個類別（class 0 與 class 1）： - 所以統計上可以視為來自**同個母體（populations）的兩個不同樣本** 兩個樣本的統計結構如下： | 類別 | Class 0 | class 1 | | -------- | -------- | -------- | | 樣本數 | $n_1$ | $n_2$ | | 樣本平均值 | $\bar{x}_1$ | $\bar{x}_2$ | Class 0 中有 $x_1,x_2,...x_{n_1}$ 筆資料 Class 1 中有 $x_1,x_2,...x_{n_2}$ 筆資料 因此，兩組樣本的平均值分別為： $\bar{x}_1 =\frac{1}{n_1} \sum_{i=1}^{n_1} x_i$ $\bar{x}_2 =\frac{1}{n_2} \sum_{i=1}^{n_2} x_i$ 有了平均值，就能計算平方差，兩組樣本的各個樣本點的平方差分別為： $\forall i \in \{1, 2, \dots, n_1\}, \quad (x_i - \bar{x}_1)^2$ $\forall i \in \{1, 2, \dots, n_2\}, \quad (x_i - \bar{x}_2)^2$ >為什麼要平方呢？ 舉例來說： 有三個數字分別是 $1,2,3$，其平均是 $2$，各值與平均相減為： $1-2=-1$ $2-2=0$ $3-2=1$ 直接加總會抵銷為 $0$，所以才須對各樣本點的差值取平方再加總。 所以兩組樣本的平方差總和為： $SSD_1=\sum_{i=1}^{n_1} (x_i - \bar{x}_1)^2$ $SSD_2=\sum_{i=1}^{n_2} (x_i - \bar{x}_2)^2$ 有了上述的資料，我們就可以進一步計算變異數，平方差總和是一個母體中所有樣本的總體偏離程度，那麼變異數可以視為個別樣本點的每筆資料的平均偏離程度。 所以兩組樣本的樣本變異數為： ${S_1}^2 = SSD_1 /(n_1-1)$ ${S_2}^2 = SSD_2 /(n_2-1)$ > 為什麼分母是樣本數 -1 而非樣本數呢？ > 因為後續要做 t test，所以將一個母體分成了兩個樣本，所以我們計算的是樣本變異數。 接著進行 Welch’s t-test > 這個檢定方式來自於 Student's t-test 的改良，當要進行比較的兩個樣本其樣本數或變異數不一致，就可以使用 Welch’s t-test 來計算兩組樣本的差異性，程式當初在分組是隨機的，顯然 Class 0 與 Class 1 的樣本數不一致。 公式如下： $t = \frac{\bar{x}_1 - \bar{x}_2} {\sqrt{ \frac{S_1^2}{n_1} + \frac{S_2^2}{n_2} }}$ 以上就是 t_compute 這個函式的背景知識，最後會將 t 值回傳，回到 report 這個函式： ```c double max_t = fabs(t_compute(t)); ``` 宣告一個 max_t 變數儲存剛剛的 t 值。 > 取絕對值的原因在於會因為出來的 t 值有負有正，這取決於兩組樣本的大小，不過這不是我們關注的地方，我們只關注差距有多大。 接著要進行正歸化： ```c double max_tau = max_t / sqrt(number_traces_max_t); ``` 宣告一個 max_tau 變數儲存正歸化後的 t 值。 > 原因在於前面提到的 Welch’s t-test 公式，觀察分母不難得知會因為樣本數變大而使 t 值變大，我們需要將這個部份的影響抵銷。 最後進行比較： ```c if (max_t > 500) return false; if (max_t > 10) return false; ``` 對應原始 dudect 專案： ```c static void update_statistics(dudect_ctx_t *ctx) { for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) { int64_t difference = ctx->exec_times[i]; if (difference < 0) { continue; // the cpu cycle counter overflowed, just throw away the measurement } // t-test on the execution time t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]); // t-test on cropped execution times, for several cropping thresholds. for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) { if (difference < ctx->percentiles[crop_index]) { t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]); } } // second-order test (only if we have more than 10000 measurements). // Centered product pre-processing. if (ctx->ttest_ctxs[0]->n[0] > 10000) { double centered = (double)difference - ctx->ttest_ctxs[0]->mean[ctx->classes[i]]; t_push(ctx->ttest_ctxs[1 + DUDECT_NUMBER_PERCENTILES], centered * centered, ctx->classes[i]); } } } ``` 其實進行了多次的測試，第一組與目前專案相同，直接使用原始的執行時間進行 t test，這會得到一個 t 值，接著第二階段是會對執行時間進行裁剪，舉一個簡單的範例說明： class [0] = [0,0,0,0,0,0,0,0,0,0] class [1] = [1,2,3,4,5,6,7,8,9,10] 第一階段直接進行 t test 得到 t1。 第二階段會設計裁剪門檻，並分成 10 個 bucket，並為每個 bucket 設定門檻值： 門檻值計算公式： $p_i = 1 - 0.5^{(i + 1)}$ $bucket(0) ： p_0 =0.5$ $index = \lfloor{10 * 0.5}\rfloor = 5$ class[1] 中索引為 5 的是 6，所以 bucket[0] 會搜集所有比 6 小的數： > 1,2,3,4,5 依此類推，並拿各個 bucket 與 class[0] 進行 t test 這也會求算出多個 t 值（t2,...,t11）。 最後從 t1,...,t11 中取最大的 t 值，作為 constant time 的判斷結果，由此可以發現，原專案的精神更像是「寧可錯殺，也不錯放」。 我們可以將這個裁剪策略引進 lab0 中，我們可以先看看原始方式的執行時間分佈： > 下圖所呈現的是執行 `make test` 時，經統計檢定後有顯著差異的總體資料分佈。 ![download](https://hackmd.io/_uploads/SJtZIkP6kg.png) 對這些資料，我們套用先前提過的裁剪方式，經裁剪後的分佈如下： ![download](https://hackmd.io/_uploads/BkXewJD6yl.png) 這邊的實驗有一點問題，正在排除中。 > commit [83077d6](https://github.com/yy214123/lab0-c/commit/f8e9d8a8335b4e345cc0893f618f4414399841ea) > 有其他學員導入原始 dudect 專案的裁剪策略，現在執行 lab0-c 的 `make test` 時可通過 `trace trace-17-complexity`。 ```shell +++ TESTING trace trace-17-complexity: # Test if time complexity of 'q_insert_tail', 'q_insert_head', 'q_remove_tail', and 'q_remove_head' is constant Probably constant time Probably constant time Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 100/100 ``` 也順利的在 Actions 出現可愛的卡比： ![image](https://hackmd.io/_uploads/S1x2Z-_T1e.png) ## 研讀 Linux 核心原始程式碼的 lib/list_sort.c ## 整合網頁伺服器 去年我也沒有完成這部份，應該說我一直不懂這個部份到底要幹麻，不像是其他佇列指定操作那麼具體，雖然作業截止期限已過，但我還是決定在進行作業六之前，嘗試解決這個部份。 在 `qtest` 中也有提供 `web` 命令，如下輸入後會等待 port 9999 的輸入： ```shell $ ./qtest cmd> web listen on port 9999, fd is 3 ``` 此時開啟另一個終端機，當輸入： ```shell $ curl http://localhost:9999/new ``` 此時第一個終端機會如同正常使用 `qtest` 初始化一個佇列： ```shell $ ./qtest cmd> web listen on port 9999, fd is 3 cmd> l = [] ``` 接著進行一連串的佇列操作： ```shell $ curl http://localhost:9999/it/1 $ curl http://localhost:9999/it/2 $ curl http://localhost:9999/it/3 ``` 當然剛剛初始化的佇列也會完成對應的操作： ```shell $ ./qtest cmd> web listen on port 9999, fd is 3 cmd> l = [] cmd> l = [1] cmd> l = [1 2] cmd> l = [1 2 3] ``` 在 `qtest` 中的命令都會對應到一個 do_xxx 函式，搜尋 `do_web` 後會發現其實作在 `console.c` 中： ```c static bool do_web(int argc, char *argv[]) { int port = 9999; if (argc == 2) { if (argv[1][0] >= '0' && argv[1][0] <= '9') port = atoi(argv[1]); } web_fd = web_open(port); if (web_fd > 0) { printf("listen on port %d, fd is %d\n", port, web_fd); line_set_eventmux_callback(web_eventmux); use_linenoise = false; } else { perror("ERROR"); exit(web_fd); } return true; } ``` 這邊可以看到，將 9999 作為參數傳入 `web_open` 函式，其實作在 `web.c` 中： ```c int web_open(int port) { int listenfd, optval = 1; struct sockaddr_in serveraddr; /* Create a socket descriptor */ if ((listenfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) return -1; /* Eliminates "Address already in use" error from bind. */ if (setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, (const void *) &optval, sizeof(int)) < 0) return -1; // 6 is TCP's protocol number // enable this, much faster : 4000 req/s -> 17000 req/s if (setsockopt(listenfd, IPPROTO_TCP, TCP_CORK, (const void *) &optval, sizeof(int)) < 0) return -1; /* Listenfd will be an endpoint for all requests to port on any IP address for this host */ memset(&serveraddr, 0, sizeof(serveraddr)); serveraddr.sin_family = AF_INET; serveraddr.sin_addr.s_addr = htonl(INADDR_ANY); serveraddr.sin_port = htons((unsigned short) port); if (bind(listenfd, (struct sockaddr *) &serveraddr, sizeof(serveraddr)) < 0) return -1; /* Make it a listening socket ready to accept connection requests */ if (listen(listenfd, LISTENQ) < 0) return -1; server_fd = listenfd; return listenfd; } ``` 在 [CS:APP 第 11 章重點提示](https://hackmd.io/@sysprog/CSAPP/https%3A%2F%2Fhackmd.io%2Fs%2FByPlLNaTG) 有介紹到 client 及 server 的細節： 1. 呼叫 getaddrinfo() 解析位址並取得 struct addrinfo，其中包含 IP、通訊埠與服務名稱等資訊 2. 接著透過 socket() 建立通訊端，回傳一個檔案描述子；此步驟僅建立端點，不會觸發網路傳輸 3. server 呼叫 bind() 將 socket 與指定 IP 與通訊埠連結 (位於核心空間) 4. server 進入監聽狀態並呼叫 listen()，等待 client 連線 5. server 使用 accept() 接受連線並為該 client 建立新的 socket 6. client 端則在 connect() 發出連線要求並等待 server accept 7. 連線建立後，雙方透過 read／write (或封裝如 rio，reliable I/O)進行資料交換 8. 當 client 結束會送出 EOF，server 接收後關閉對該 client 的 socket 9. server 關閉後可選擇再接受下一個 client，或關閉整體服務 追蹤程式的執行順序： 第 1 步： 在 `qtest.c` 的 `main` 函式，接近末端的部份會呼叫 `run_console()`。 第 2 步： 因為在 `console.c` 中會把變數 `use_linenoise` 設為 false，所以在 run_console() 中，一旦 CLI 輸入命令 web 時，另一個 client 的終端機會執行下面的程式區塊： ```c if (!use_linenoise) { while (!cmd_done()) cmd_select(0, NULL, NULL, NULL, NULL); } ``` 第 3 步，在 `cmd_select` 中會呼叫 `linenoise()`，而接著又呼叫 `line_raw()`： ```c /* This function calls the line editing function line_edit() using * the STDIN file descriptor set in raw mode. */ static int line_raw(char *buf, size_t buflen, const char *prompt) { if (buflen == 0) { errno = EINVAL; return -1; } if (enable_raw_mode(STDIN_FILENO) == -1) return -1; int count = line_edit(STDIN_FILENO, STDOUT_FILENO, buf, buflen, prompt); disable_raw_mode(STDIN_FILENO); printf("\n"); return count; } ``` 而由於在 `do_web()` 中會： ```c line_set_eventmux_callback(web_eventmux); ``` 所以此時　eventmux_callback　為　web_eventmux。而回到 `line_ediｔ()` 中： ```c if (eventmux_callback != NULL) { int result = eventmux_callback(l.buf, l.buflen); if (result != 0) return result; } ``` 第 4 步，在 `web_eventmux` 實現 accept()，其中 `web_recv` 會解析我們輸入的 client 命令： ```c curl http://localhost:9999/new ``` ## 在 `qtest` 提供新的命令 shuffle > commit [1729ab3](https://github.com/yy214123/lab0-c/commit/1729ab36b9235ab8281738045c87b28c38da7db7) 在 `qtest.c` 中，可以觀察到各個 `do_xxx` 函式與 `console_init` 中的 `ADD_COMMAND` 是成對出現的： ```c static bool do_free(int argc, char *argv[]) { ... } static bool do_new(int argc, char *argv[]) { ... } ... static void console_init() { ADD_COMMAND(new, "Create new queue", ""); ADD_COMMAND(free, "Delete queue", ""); ... } ``` `shuffle` 並不需要額外參數，在命令列中應該輸入 shuffle 就能執行對應的操作，所以可以模仿其他函式進行錯誤警告的實作： ```c if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!current) { report(3, "Warning: Try to shuffle null queue"); return false; } ``` 結果當我執行 `qtest` 時： ```shell $ ./qtest cmd> new l = [] cmd> it RAND 100 l = [rfxvub erkbcmqy khphreco ufbtmy ciwwwqvd mslfbza lglwjtlqc drorzqted vqjhtf xiebqselp gauonpxm sznzaef nkilnoysx vovqrvkfu skxoxte nacllgf bvlbrb eysxaneo mkdxqw jdaxhd bgzgoyv caijpch oinxah jgibwiyp vanadkls wvyowlqg kwihxzx bwkapu hnvjvx qppvhoi ... ] cmd> shuffle ERROR: Queue is not doubly circular ``` 回顧我目前的 [實作](https://gist.github.com/yy214123/ca021ceff47fc9a4472399752d8e2bd4)，我發現我的程式碼有一個致命的問題： ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3; 4; 5; } { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> 4 -> 5 -> head [dir=both]; p1 [label="old", shape=box]; p2 [label="new", shape=box]; p1 -> 1 [color=red]; p2 -> 5 [color=red]; } ``` 在這種狀況下交換是沒有問題的，但是當 `old` 與 `new` 相鄰時： ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3; 4; 5; } { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> 4 -> 5 -> head [dir=both]; p1 [label="old", shape=box]; p2 [label="new", shape=box]; p1 -> 4 [color=red]; p2 -> 5 [color=red]; } ``` 我原先的實作又用了兩個指標去指向 `old->prev` 及 `new->prev`： ```graphviz digraph G { graph [ nodesep=0.8, ranksep=0.8 ]; { rank=same; head; 1; 2; 3; 4; 5; } { rank=same; p1 [label="*p1", shape=box]; p2 [label="*p2", shape=box]; } head -> 1 -> 2 -> 3 -> 4 -> 5 -> head [dir=both]; p1 [label="old", shape=box]; p2 [label="new", shape=box]; p3 [label="old->prev", shape=box]; p4 [label="new->prev", shape=box]; p1 -> 4 [color=red]; p2 -> 5 [color=red]; p3 -> 3 [color=red]; p4 -> 4 [color=red]; } ``` 接著透過 list_move 來完成交換，這樣會發生 `list_move(old,old)`，而 list_move 本身的實作是透過 list_del 及 list_add 來完成，所以才會出錯。 所以我後來額外實作一個用於交換兩個指定節點的 [swap](https://gist.github.com/yy214123/3684f551b55fac78d57674ac5aa3b59a) 函式。再次執行 `qtest` 驗證： ```shell $ ./qtest cmd> new l = [] cmd> it RAND 10 l = [rmnqgw ipjdadbzo kiifcpvo zeprnzjxd chvtmir hudomvao dzmqjgxrf oasrjacv rjdkwjbkm viuaiyi] cmd> shuffle l = [kiifcpvo chvtmir rjdkwjbkm zeprnzjxd viuaiyi rmnqgw hudomvao dzmqjgxrf oasrjacv ipjdadbzo] ``` 在實作的過程中，我意識到一個問題： :::warning 實際上，交換兩個節點的值未必得進行節點的移動。可以直接利用 `list_entry` 來獲取內嵌的 `element_t `結構體的值，僅需進行簡單的值交換。這個思路或許可以進一步應用於 `q_reverse`、`q_reverseK` 和 `q_swap` 等函式中，仍待驗證。 ::: ## rebase 根據 [N03: review](https://hackmd.io/@sysprog/linux2025-review) 檢查事項 3，須利用 `git rebase` ，將先前的已提交的 commit 移至 3 月 18 日或之後的更新之上。 首先加入上游的 branch： ```shell $ git remote add upstream https://github.com/sysprog21/lab0-c.git ``` 用 rebase 把自己的 commit 移到最新 upstream 後面： ```shell $ git rebase upstream/main Auto-merging scripts/check-repo.sh Auto-merging scripts/checksums CONFLICT (content): Merge conflict in scripts/checksums Auto-merging scripts/commit-msg.hook Auto-merging scripts/common.sh Auto-merging scripts/install-git-hooks CONFLICT (content): Merge conflict in scripts/install-git-hooks Auto-merging scripts/prepare-commit-msg.hook error: could not apply 1e6e0c0... Utilize common script when possible hint: Resolve all conflicts manually, mark them as resolved with hint: "git add/rm <conflicted_files>", then run "git rebase --continue". hint: You can instead skip this commit: run "git rebase --skip". hint: To abort and get back to the state before "git rebase", run "git rebase --abort". Could not apply 1e6e0c0... Utilize common script when possible ``` 首先看到衝突出現在 scripts/checksums ```c <<<<<<< HEAD bff0704601c8197ae6b847647b4167664b7d6abc queue.h b26e079496803ebe318174bda5850d2cce1fd0c1 list.h ======= 398b59c23f699ff1bf1e73a94503a9a91caa9207 queue.h 9be9666430f392924f5d27caa71a412527bf9267 list.h >>>>>>> 1e6e0c0 (Utilize common script when possible) 1029c2784b4cae3909190c64f53a06cba12ea38e scripts/check-commitlog.sh ``` 根據先前提交 pull request 的經驗，這邊選擇保留 upsteam 的版本。 ```diff - <<<<<<< HEAD bff0704601c8197ae6b847647b4167664b7d6abc queue.h b26e079496803ebe318174bda5850d2cce1fd0c1 list.h - ======= - 398b59c23f699ff1bf1e73a94503a9a91caa9207 queue.h - 9be9666430f392924f5d27caa71a412527bf9267 list.h - >>>>>>> 1e6e0c0 (Utilize common script when possible) 1029c2784b4cae3909190c64f53a06cba12ea38e scripts/check-commitlog.sh ``` 接著： ```shell $ git add scripts/checksums $ git status ok 16:12:09 interactive rebase in progress; onto 5223a1d Last commands done (11 commands done): pick 075d580 Implement q_reverse pick 1e6e0c0 Utilize common script when possible (see more in file .git/rebase-merge/done) Next commands to do (23 remaining commands): pick a82c116 Change 'commit_msg_lines' to 'COMMIT_MSG_LINES' pick eee3f39 Utilize common script for pre-commit hook (use "git rebase --edit-todo" to view and edit) You are currently rebasing branch 'master' on '5223a1d'. (fix conflicts and then run "git rebase --continue") (use "git rebase --skip" to skip this patch) (use "git rebase --abort" to check out the original branch) Changes to be committed: (use "git restore --staged <file>..." to unstage) modified: scripts/checksums Unmerged paths: (use "git restore --staged <file>..." to unstage) (use "git add <file>..." to mark resolution) both modified: scripts/install-git-hooks ``` 這邊顯示還有另一個檔案的衝突須處理，也是保留 upsteam 版本的 `scripts/install-git-hooks`，將所有的衝突解決後最後再用： ```shell $ git push origin master --force ``` 如此即完成指定的檢查項目。 :::danger 留意 git rebase 操作，預期: ![image](https://hackmd.io/_uploads/rkO48itnkx.png) > 已修正，目前的 [commit 歷史](https://github.com/yy214123/lab0-c/commits/master/) 已符合預期了。 ::: 在 3 月 20 日的直播中，授課老師檢查了我的 rebase 情況，發現了一些錯誤。我的解決方式如下： 首先檢查我自己所提交的 commit： ```shell $ git log --oneline --author=yy214123 ``` 切換到一個與 upstream 相同的乾淨分支，利用 cherry-pick 將之前的 commit 合併到這個乾淨的分支上： ```shell $ git cherry-pick f591d8a 8b6b5dc 6e45da5 0dbc29a f78288d e0515ae 6bbdec7 ddb885b bec2a7b da25fce a56881b 6c2c172 c37bc7f 681806a 341fbed a8e6d35 724a562 0384b18 9794565 fb7fbaa 0d3d3e4 d40f772 8f2422c aaaea07 ``` 接著切換回 master 分支： ```shell $ git checkout master ``` 並將 master 的內容完全重設為剛才乾淨的內容： ```shell $ git reset --hard clean-rebase ``` 最後，再次執行 pus： ```shell $ git push origin master --force ``` ## review 根據信件，指定我回顧及審查的學員有以下 5 位： 1. [SimonLiu423](https://hackmd.io/@SimonLiu423/linux2025-homework1) 2. [vicLin8712](https://hackmd.io/iHzaFhtcSAGg39j1AjKQgQ?view) 3. [dingsen-Greenhorn](https://hackmd.io/@q36134289/linux2025-homework1) 4. [Hlunlun](https://hackmd.io/@clh/linux2025-homework1) 5. [bevmmf](https://hackmd.io/@bevmmf/linux2025-homework1) ## [N04: kxo](https://hackmd.io/@sysprog/linux2025-kxo/%2F%40sysprog%2Flinux2025-kxo-a) 為什麼不存浮點數？ 用 arm 架構舉例，平常做 context switch 時只要保存 cpsr 及 spsr 內容即可，若要存浮點數，則須額外依賴 vfp(一個 double 8 bytes，需要額外 8 * 16 bytes 空間)。 ## 額外問題紀錄 ### 處理 commit message 遺失 Change-Id 的錯誤 使用 `git rebase -i` 來解決上方 Change-Id 不正確顯示的問題。由於出現問題的是最新兩則 commit message，故使用下方命令： ```shell $ git rebase -i HEAD~2 pick a7b2431 Implement q_insert_head pick 2deb4b2 Implement q_insert_tail # Rebase dfb08dd..2deb4b2 onto dfb08dd (2 commands) # # Commands: # p, pick <commit> = use commit # r, reword <commit> = use commit, but edit the commit message # e, edit <commit> = use commit, but stop for amending # s, squash <commit> = use commit, but meld into previous commit # f, fixup [-C | -c] <commit> = like "squash" but keep only the previous # commit's log message, unless -C is used, in which case # keep only this commit's message; -c is same as -C but # opens the editor # x, exec <command> = run command (the rest of the line) using shell # b, break = stop here (continue rebase later with 'git rebase --continue') # d, drop <commit> = remove commit # l, label <label> = label current HEAD with a name # t, reset <label> = reset HEAD to a label # m, merge [-C <commit> | -c <commit>] <label> [# <oneline>] # create a merge commit using the original merge commit's # message (or the oneline, if no original merge commit was # specified); use -c <commit> to reword the commit message ``` 因為我只要修改 commit message，並沒有要修改 commit 的程式碼，所以此處選擇 reword。 ```diff - pick a7b2431 Implement q_insert_head - pick 2deb4b2 Implement q_insert_tail + reword a7b2431 Implement q_insert_head + reword 2deb4b2 Implement q_insert_tail ``` 此時會開啟這兩則 commit message，我進行小幅度修改後，接著： ```shell $ git push --force-with-lease origin master ``` > commit [012fc82](https://github.com/yy214123/lab0-c/commit/012fc82e6abe467a85f2af539de69ed79516c0ea) ＆ commit [98d66c4](https://github.com/yy214123/lab0-c/commit/98d66c4d1f13b5d0f6e6c27231a5bc1a558f6cc9) > 檢查新的 commit message 還是沒有觸發 Git hooks。 隨後我刪除這兩次 commit： ```shell $ git reset --hard HEAD~2 $ git push --force ``` > commit [f63c3aa](https://github.com/yy214123/lab0-c/commit/f63c3aa1d09f6ab0fe7e9cf94167013f346dd09d) ＆ commit [4123e63](https://github.com/yy214123/lab0-c/commit/4123e63d780c4e071b05c96d8dbcccf859daa7e0) > 重新 clone 專案並修改程式碼，再重新 `git push` 一次，檢查 commit message 後發現 Change-Id 遺失的問題已解決。