# 2025q1 Homework1 (lab0) contributed by <`Dennis40816`> {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 開發環境 ```shell $ uname -a Linux dennis-laptop 6.8.0-53-generic #55-Ubuntu SMP PREEMPT_DYNAMIC Fri Jan 17 15:37:52 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux $ gcc --version gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0 Copyright (C) 2023 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ ldd --version ldd (Ubuntu GLIBC 2.39-0ubuntu8.4) 2.39 Copyright (C) 2024 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Written by Roland McGrath and Ulrich Drepper. $ 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): 16 On-line CPU(s) list: 0-15 Vendor ID: GenuineIntel Model name: 12th Gen Intel(R) Core(TM) i5-12500H CPU family: 6 Model: 154 Thread(s) per core: 2 Core(s) per socket: 12 Socket(s): 1 Stepping: 3 CPU(s) scaling MHz: 47% CPU max MHz: 4500.0000 CPU min MHz: 400.0000 BogoMIPS: 6220.80 ``` ## 文件紀錄 :::warning 避免過多的個人色彩。不要濫用 `:::info`, `:::success`, `:::warning` 等標示，儘量用清晰的文字書寫。 格式維持單純，聚焦在內容本身。 >了解。 ::: - 若標示 "§"，以 C11 規格書章節為準 - 可搜尋 **(待完成)**、**(有疑問)**、**(待確認)** 定位 **LAB** - [x] [lab0 說明文件](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a) - [x] [GNU/Linux 開發工具](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fr1Psrf0KW) (2/21) - [x] [運用 Perf 分析程式效能並改善](https://hackmd.io/@sysprog/linux-perf) (2/22-2/23 瀏覽), - [ ] [Linux2025q1: Perf Write-Up](https://hackmd.io/@dennis40816/linux2025q1-perf-writeup) - [x] [Address/Thread/Memory Sanitizer](https://www.slideshare.net/slideshow/sanitizer-cppcon-russia/45521414) - [x] [A look into the sanitizer family](https://www.slideshare.net/slideshow/a-look-into-the-sanitizer-family-asan-ubsan-by-akul-pillai/135506952) - [x] [Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation](https://valgrind.org/docs/valgrind2007.pdf) **論文** - [x] [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) - [ ] [Bottom-up Mergesort: A Detailed Analysis](https://doi.org/10.1007/BF01294131) - [ ] [The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules](https://www.sciencedirect.com/science/article/abs/pii/S0196677498909865?via%3Dihub) - [ ] [Queue-Mergesort](https://doi.org/10.1016/0020-0190(93)90088-q) **講座** - [x] [你所不知道的 C 語言: linked list 和非連續記憶體 ▶️](https://hackmd.io/@sysprog/c-linked-list) (2/21 瀏覽), - [ ] [Linux2025q1: Linked-List Write-Up](https://hackmd.io/@dennis40816/linux2025q1-linked-list-writeup) - [x] [你所不知道的 C 語言: 浮點數運算](https://hackmd.io/@sysprog/c-floating-point) - [ ] [ IEEE 754 Floating Point (2/22 - )](https://hackmd.io/@dennis40816/ieee754-floating-point-notes) (有疑問) - [ ] [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization) - [ ] [你所不知道的 C 語言：函式呼叫篇](https://hackmd.io/@sysprog/c-function) - [ ] [你所不知道的 C 語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion) - [ ] [你所不知道的C語言: Stream I/O, EOF 和例外處理](https://hackmd.io/@sysprog/c-stream-io) - [ ] [你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer) - [ ] [Linux2025q1: Pointer Write-Up (2/22 - )](https://hackmd.io/@dennis40816/linux2025q1-pointer-writeup) (有疑問) - [ ] [Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh) - [x] [2023 年 Linux 核心設計課程第一次作業檢討 ▶️](https://hackmd.io/@sysprog/linux2023-lab0-review) **Code** - [x] [lab0-c/CONTRIBUTING.md](https://github.com/Dennis40816/lab0-c/blob/master/CONTRIBUTING.md) (2/22) - [x] [Linux2025q1: lab0-c 貢獻規定速記](https://hackmd.io/@dennis40816/linux2025q1-lab0c-contributing-writeup) (2/22) (有疑問) - [ ] [Linux2025q1: C-String APIs Write-Up](https://hackmd.io/@dennis40816/linux2025q1-cstring-api-writeup) - [ ] [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) - [x] [How to Write a Git Commit Message](https://cbea.ms/git-commit/) (2/22) - [ ] [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) - [ ] [lib/list_sort: optimize number of calls to comparison function](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) **隨堂測驗** - [x] [2025q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz1) - [x] [Linux2025q1: Quiz 1 Write-Up](https://hackmd.io/@dennis40816/linux2025-homework2) - [x] [2025q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz2) - [x] [Linux2025q1: Quiz 2 Write-Up](https://hackmd.io/@dennis40816/linux2025-homework2) **課程問答** - [x] [2025-02-{18,20} 課堂問答簡記](https://hackmd.io/2jXewm-kQBSDHwWVEZBg2w) (2/22) - [留言回覆](https://hackmd.io/2jXewm-kQBSDHwWVEZBg2w?comment=4f368898-de14-4384-a9e1-683b447fb7ce&utm_source=comment-card&utm_medium=icon) rounding to even 捨入方向 **演算法** **延伸閱讀** - [x] [Entropy (information theory)](https://en.wikipedia.org/wiki/Entropy_(information_theory)) - [x] [如何理解資訊熵](https://www.youtube.com/watch?v=s7o-UpsZcw8) ▶️ - [x] [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) - [x] [Student's t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) - [ ] [亂數: Diehard tests](https://en.wikipedia.org/wiki/Diehard_tests) **PR** - [x] [Clear where non-American English appears #209](https://github.com/sysprog21/lab0-c/pull/209) - [x] [Refine trace command descriptions #213](https://github.com/sysprog21/lab0-c/pull/213) - [x] [Fix commit hook breakage #220](https://github.com/sysprog21/lab0-c/pull/220) - [x] [Add missing parameter hints #231](https://github.com/sysprog21/lab0-c/pull/231) - [x] [Fix incorrect do_size argument usage #238](https://github.com/sysprog21/lab0-c/pull/238) ## 工具鏈相關 ### 編譯選項 :::danger 注意用語！ >好的。 ::: - `LIST_POISONING` : 巨集，若被定義執行 `list_del` 後的節點，其 `prev` 和 `next` 指向 `NULL`，如果意外被調用會觸發記憶體區段錯誤 (Segmentation Fault)。 - `SANITIZER` : 開啟時，能得知 segmantation 相關錯誤觸發位置。 **個人新增** - `Q_MERGE`: 0 代表使用樹狀合併(預設)，1 代表使用線性合併。 - `Q_SHUFFLE_BIAS`: 有定義，會採用有偏方法，未定義採用無偏 (預設)。 編譯範例: ```bash make SANITIZER=1 -D LIST_POISONING=1 Q_MERGE=0 Q_SHUFFLE_BIAS= ``` ### VSCode gdb 在 lab0-c 中，直接使用 gdb 對 qtest 除錯會遇到 ++SIGALRM++ 導致超時。而透過 `python scripts/debug.py -d` 則可以啟動已經忽略 ++SIGALRM++ 的 gdb。同理我們也能在 `.vscode/launch.json` 的 `setupCommands` 設定: ```json "setupCommands": [ { "description": "Ignore SIGALRM signal", "text": "handle SIGALRM ignore", "ignoreFailures": true }, { "text": "backtrace", "ignoreFailures": true }, ] ``` 巨集在前處理期間就被展開，故 gdb 無法像函式一樣使用它們。這對於常用的巨集 (e.g., `container_of` ) 稍有不便。我們當然能夠在 gdb 裡面暴力打出所有已知資訊，透過類似: ```c (gdb) p (struct my_container *)((char *)my_member_ptr - offsetof(struct my_container, member)) ``` 獲得我們要的 debug 資訊，但我們也能透過 python 的 gdb package 去實作實用的函式，進而降低使用時的複雜度。++如果你也想使用客製化且能使用 VSCode 除錯介面的 gdb++，請參考 [〈Linux2025q1: Toolchain Write-Up〉](https://hackmd.io/@dennis40816/linux2025q1-toolchain-writeup) 和 [ commit 8fdbc1a](https://github.com/Dennis40816/lab0-c/commit/8fdbc1a764b29669923357f7eb82cd3af24c988f)。裡面介紹了如何實作 `container_of` 等功能，讓你 debug 更輕鬆。 ### Breakpoint 對中斷點按下右鍵將出現 `Edit Condition` 的選項，可供輸入判斷條件。假設你希望 `node->value` 是 "7" 的時候該中斷點才停下，可將中斷點的表達式改成: ```c (int) strcmp(node->value, "7") == 0 ``` 如果沒強制轉型會遇到錯誤: ```bash 'strcmp' has unknown return type; cast the call to its declared return type ``` ## 實作 queue.[ch] 瀏覽 `queue.h`，將須實作的功能及討論放在本節中。 實作前，列舉概觀注意點及討論點: 1. 環狀雙向鏈結串列使佇列在進行頭尾操作時，時間複雜度為 O(1)，為符合測試要求此種實作是必要的。 1. 思考佇列鏈是否也需要透過環狀雙向鏈結串列實作?為什麼? A: `qtest` 提供 `prev` 和 `next` 命令在佇列間進行切換，因此為提升 ++**當佇列實例數量很多時**++， `prev` 切換時的效能，也應以環狀雙向鏈結串列實作。但這部分是 `qtest.c` 實作的範圍。 1. NULL queue 和 empty queue 差異是? A: Empty queue 具有 head，NULL queue 連 `head` 都沒有，見下方示意圖。 1. 為符合 linux 鏈結串列的 API 風格，所有**有效的**鏈結串列都應具有型別為`struct list_head` 的實例 `head`，當鏈結串列為空時，`head->next` 指向 `head` 本身。 1. ~~希望 `queue_t` 的資訊(e.g., size, id, ...) 能在 O(1) 內取得，即 `size` 要由多個 function 共同維護? 此作法會引入額外的複雜度 (包含未來添加新函式時可能也需考量)，是否有價值?~~ 後來查看 `queue_contex_t` 是用在多佇列的操作上，如 `qtest.c` 和 `q_merge` 中，因此佇列基礎功能的實作與之無關。 1. 現有實作與 [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf) 描述有何差異? A: 差異如下: - 佇列的尾元素不再指向 `NULL`，有利減少檢查。 下圖是對應的示意圖，可用於實作時對照查看: ![queue_struct](https://hackmd.io/_uploads/SJQA1q_5yg.png) ![queue_illustration](https://hackmd.io/_uploads/rJ55siO5Jl.png) 這張圖以++橘色++標示所有與 `struct list_head` 有關的成員或指向操作。圓點代表結構體中成員（通常是指標）的連接點，箭頭的起點必定在圓點上，因為只有指標才具有「指向」的含意。箭頭的終點表示所指向的目標。若目的地仍是圓點，則表示指向另一個成員；若指向邊框，則代表它指向的目標是結構體或是陣列實例 (e.g., `struct list_head` 實例、字串陣列...) 。 例如，在 `queue instance 1` 中，`next` 從圓點出發指向自身所在的邊框，表示它指向包含自身的，型別為 `struct list_head` 的實例。 ~~圖中箭頭連接到圓點表指向特定成員；未連接到圓點上的，則指向結構體。指向型別為 `list_head` 的指標用 ++**橘色**++ 標示。~~ 藍色底色是本次要實作的部分，紅色底色則主要由 `qtest.c` 使用。 ### q_new > commit: [0427310](https://github.com/Dennis40816/lab0-c/commit/04273100105513d8b71f50f010097b2c3c109745) :::danger 不要恣意標注 `v1`，GitHub 會紀錄你的開發過程，你只要標注 commit hash。 >了解。 ::: :::danger interface 的翻譯是「介面」，而非「接口」，後者不文雅。 參見「[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)」及「[詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)」。 >已修正。 ::: <!-- 目的 START --> **目的** 提供建立++空佇列++ (不含 `q_contex_t` )的統一介面。 :::danger 注意用語，你在中學的國文課本中，除了「創建民國」以外，還有哪篇文章出現「創建」。改用新增、建立等詞彙，尊重傳統文化。 >已修正。 ::: <!-- 目的 END --> <!-- 限制與狀況 START --> <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 1. 請求 `head` 大小的記憶體空間(透過 `malloc` )。 2. 檢查記憶體配置 (memory allocation) 是否成功，並在失敗時返回 `NULL`。 3. 檢查成功後，使用 `INIT_LIST_HEAD` 將 `prev` 和 `next` 都指向自身，並返回該 `head` 地址。 :::danger 流暢的漢語中，不需要頻繁書寫「一個」，你該回想自己在中學國文讀過的經典文學作品，哪篇會頻頻出現「一個」？ >已修正。 ::: <!-- 實作流程 END --> ### q_free > commit: [0427310](https://github.com/Dennis40816/lab0-c/commit/04273100105513d8b71f50f010097b2c3c109745) <!-- 目的 START --> **目的** 釋放佇列申請的所有元素 ( `element_t` ) 記憶體空間，按應釋放的順序依序為字串陣列 ( `value` 指向的地址)、佇列節點 ( `element_t` ) 以及佇列的 `head`。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. 傳入 `head` 指向 `NULL`: 欲釋放不存在的佇列，應盡早返回，避免後續操作 (e.g., `head->next` ) 對 `NULL` 解引用。 2. 無返回值。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 1. 可以使用 `list_for_each_entry_safe` 先獲取 `entry`，因為涉及刪除，所以要使用 `safe`。 1. 由於整條佇列都將被釋放，因此似乎不需要先移出 `queue`，可以直接刪除? 1. 假設所有 entry 的成員 `value` 皆為非 `NULL`，雖然將 `NULL` 作為 `free` 的參數不會發生任何事 (C11 §7.22.3.2 - 2) : <br> >If ptr is a null pointer, no action occurs. 1. 根據上一條，雖不影響，~~但是否會影響效能( `free()` 內部的處理邏輯)需要再探討~~，觀察 `test_free`，在進行 `NULL` 的返回前，僅做是否允許配置的檢查( `noallocate_mode` )。 ++以下敘述待實驗 **(待完成)**++: 除非使用者非常頻繁在可配置和不可配置間切換，否則 CPU 分支預測錯誤造成管線清除 (pipeline flush) 的消耗近乎 0，實際情況未來用 `perf` 觀察。 :::danger 談及 CPU 時，pipeline 譯作「管線」，而非「流水線」，後者用於工廠製造。 注意詞彙，論點都該有明確的第一手材料出處。 > 還在準備實驗中。**(待完成)** ::: :::danger assign 和 assignment 不該偷懶的翻譯成「賦值」，你在中學英語用過這翻譯詞嗎？ 可改寫為「`entry` 會被變更」，關鍵的概念不是「值」的「賦予」，而是「使用」和「變更」 >之前沒想到這層面，日後會改用變更或更新。 ::: 按照上述描述 (1), (2), (4) ，可得以下實作: ```c= element_t *entry, *safe; list_for_each_entry_safe (entry, safe, head, list) { free(entry->value); free(entry); } ``` 在第 3、4 行會出現 ++Cppcheck 錯誤: 使用未初始化變數++，但在 `list_for_each_entry_safe` 中 `entry` 和 `safe` 都會被變更。測試直接展開 `list_for_each_entry_safe` 是可通過 Cppcheck 檢查的。暫時解決方案是將兩個指標都先指向 `NULL` 。而釋放元素記憶體可通過 `q_release_element` 更精簡: ```diff -element_t *entry, *safe; +element_t *entry = NULL, *safe = NULL; list_for_each_entry_safe (entry, safe, head, list) { - free(entry->value); - free(entry); + q_release_element(entry); } ``` <!-- 實作流程 END --> ### q_insert_head > commit: [e0ec110](https://github.com/Dennis40816/lab0-c/commit/e0ec110949bf6efcf8539e1c7854673750854adf) <!-- 目的 START --> **目的** 1. 建立新的佇列++元素++，將給定字符串++複製++至其 `value` 的陣列中，`value` 陣列需自行配置記憶體，長度可透過 `strlen()` 取得。 2. 將配置並賦值完的元素插入至 `head` 和 `head->next` 間。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. 當透過 `malloc` 申請配置失敗時，要返回 `false` 2. 當傳入的佇列是 `NULL`，返回 false <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 1. 假設使用者提供的字符串是++有效的++，不包含 `NULL` 和沒有 `\0` 結尾等情況。 2. 目的 (2) 可透過 `list_add` 完成。 3. 配置記憶體流程: 配置佇列元素、字元陣列 ➝ 確保兩者皆有效 ➝ 將佇列元素的 `value` 指向字元陣列。 4. 配置失敗發生時，要將已經配置的記憶體釋放，避免洩漏。 根據 (3), (4) 的實作如下: ```c size_t csize = strlen(s) + 1UL; char *cp = malloc(csize); if (!cp) return false; memcpy(cp, s, csize); element_t *entry = malloc(sizeof(element_t)); if (!entry) { free(cp); return false; } entry->value = cp; ``` 觀察記憶體配置流程中，存在程式簡化空間。在 `harness.h` 透過巨集宣告 `strdup` (實際為 `test_strdup`)，跟上方實作接近，只差在兩點: - 承接 `malloc()` 返回值的型別使用 `void*` 而非 `char*`。 - 配置失敗時返回 `NULL` 而非 `false`。 :::danger 延伸閱讀是書寫教材時的用語，這裡是「開發紀錄」，當然要反映你看了哪些，既然投入時間，就探討，沒必要說「延伸閱讀」。 >了解。 ::: 關於第一點，在 §6.3.2.3 - 1 中提到: > A pointer to void may be converted to or from a pointer to any object type. 其中，轉換 (conversion) 分為顯式 (explicit) / 隱式 (implicit) 兩種，前者也稱為強制轉型操作 (cast operation)，在 §6.3 - 1 有提及: > This subclause specifies the result required from such an implicit conversion, as well as those that result from a **cast operation (an explicit conversion)**. §6.5.4 - 5 定義了在物件前添加小括號 `(target-type)` 的轉型行為，稱為強制轉型，且強制轉型的返回的結果並不是[定位器值 (locator value, lvalue)](https://hackmd.io/@sysprog/c-pointer#Lvalue-%E7%9A%84%E4%BD%9C%E7%94%A8) : >Preceding an expression by a parenthesized type name converts the value of the expression to the named type. This construction is called a cast^104^. >^104)^ A cast does not yield an lvalue. Thus, a cast to a qualified type has the same effect as a cast to the unqualified version of the type. 從上文可推斷 `void*` 可以顯式或隱式轉換成任意物件型別 (object type) 的指標，而本實作使用到 `void*` 的隱式轉換。 **(待完成)** 另外，... (我記得 `void *` 和 `char *` 某些情況上是一樣的，但一時之間沒找到在規格書的哪一章節，之後補)。 :::danger 避免說「某種程度」，這裡應該是「某些情況」。用你的中學國文來書寫，不要因為看了詞不達意的簡體中文內容，就忘了漢語該如何書寫。 >好的。 ::: 因此上方程式修改後如下: ```diff -size_t csize = strlen(s) + 1UL; -char *cp = malloc(csize); +char *cp = strdup(s); if (!cp) return false; -memcpy(cp, s, csize); ``` 另外應注意在 C++ 中 `void *` 的隱式轉換是被禁止的，例如: ```cpp int *a = malloc(4); ``` 上例的編譯結果是 `invalid conversion from ‘void*’ to ‘int*’ [-fpermissive]`，因為隱式轉換成 `void *` 並非類型安全的。有關更多 C 字串的 API 請參考 [string(3) — Linux manual page](https://man7.org/linux/man-pages/man3/string.3.html)。 :::danger 避免書寫 v1 和 v2 這樣無助於溝通的話，你只要標注 commit hash >已移除。 ::: **討論** - 觀察 `insert` 過程中都牽涉到佇列元素的記憶體配置，相對刪除 (非移除) 佇列元素有 `q_release_element`，為何不實作 `q_new_element` 增加程式重複利用率? **(待完成)** - 參考 [v0103 的實作](https://hackmd.io/@v0103/hw1#q_insert_head)，可以進一步讓程式縮短，且佔用的函式堆疊尺寸會比較小(沒有 `cp` )，但程式可讀性略為下降。 <!-- 實作流程 END --> ### q_insert_tail > commit: [e0ec110](https://github.com/Dennis40816/lab0-c/commit/e0ec110949bf6efcf8539e1c7854673750854adf) <!-- 目的 START --> **目的** 與 `q_insert_head` 類似，僅插入位置改為尾端。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 同 `q_insert_head`。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 由於內容與 `q_insert_head` 非常類似，僅需調整與鏈結串列相關的 API 即可。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 未來討論方向可著重在程式重用上。 **(待完成)** <!-- 討論 END --> ### q_remove_head > commit: [e0ec110](https://github.com/Dennis40816/lab0-c/commit/e0ec110949bf6efcf8539e1c7854673750854adf) <!-- 目的 START --> **目的** 1. 移出佇列中第一個元素，並返回該元素的地址。 2. 若使用者給定一++有效++字元指標 `sp` ，且 **目的(1)** 已完成，複製移出元素的值到 `sp` 中，可容納的字元長度由使用者給定 `bufsize` ，允許的最大字串長度為 `bufsize - 1` 確保最後總是 `\0`。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. `sp` 是 `NULL`: 不將元素的值(字串) 複製到 `sp` 內。 2. ~~移出失敗: 理論上不存在此種情況。~~ 3. `head` 是 `NULL`: 直接返回 `NULL`。 4. `head` 指向空佇列: 直接返回 `NULL`。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 1. 僅在移出成功後，才複製字串到 `sp`。 2. 可用 `list_empty` 檢查是否為空佇列。 3. 複製字串可用 `strncpy`，該函式返回值是 `sp`，不需要承接。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 乍看 `strncpy` 是很好的選擇，因其具備兩點特點: - 長度限制，避免誤寫入非法記憶體區域 - 幫忙補 `\0` 透過 `man strncpy` 可看可能的實作: ```c char * strncpy(char *restrict dst, const char *restrict src, size_t dsize) { stpncpy(dst, src, dsize); return dst; } char * stpncpy(char *restrict dst, const char *restrict src, size_t dsize) { size_t dlen; dlen = strnlen(src, dsize); return memset(mempcpy(dst, src, dlen), 0, dsize - dlen); // ⭠⭠⭠ here } ``` 但試想遇到使用者給定了++超長的緩衝區++，而要複製的字串++很短++時，`strncpy` 依舊會將後面全部的記憶體都 `memset` 成 `\0`，而其實只需要添加單一 `\0` 即可，是否有更好的方法? 初步的 benchmark 記錄在 [compiler explorer](https://godbolt.org/z/7sdT9Wjaz)。 **(待完成)** <!-- 討論 END --> ### q_remove_tail > commit: [e0ec110](https://github.com/Dennis40816/lab0-c/commit/e0ec110949bf6efcf8539e1c7854673750854adf) <!-- 目的 START --> **目的** 同 `q_remove_head`，僅操作元素改為尾部。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 同 `q_remove_head`。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 由於內容與 `q_remove_head` 非常類似，僅需調整與鏈結串列相關的 API 即可。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 未來討論方向可著重在程式重用上。 **(待完成)** <!-- 討論 END --> ### q_size > commit: [421b720](https://github.com/Dennis40816/lab0-c/commit/421b7206decf4f1c55f7988370623f2ce1fd1b46) <!-- 目的 START --> **目的** 透過 ++走訪 (tranverse)++ 所有元素，以統計目前的元素數量。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 當 `head` 為 `NULL` 或為空佇列 : 返回 `0`。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 透過 `list_for_each` 走訪佇列中元素的每個 `list` 成員，每當該成員的地址與 `head` 地址不一樣，就將佇列大小加上 `1`，直到再次遇到 `head`。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 目前方法的時間複雜度為 O(n)，是否存在 O(1) 的寫法? 在 `q_contex_t` 中有成員為 `size`，可以紀錄大小，我認為可以實現 `q_element_xxx` APIs，這些 API 調用 `q_xxx` APIs 並會負責管理 `q_contex_t` 的內容，這樣 `q_size` (或說 `q_element_size` ) 能以常數時間返回。但就現階段而言，無法達到 O(1)。**(待確認)** 註: 這樣會增加增刪等操作的複雜度 (要維護 `size`)。 :::danger 盲目追求 $O(1)$ 是不智的，你該確保應用情境有其必要。 >需思考在 homework1 及其後續作業中，是否有相應的應用場景。 >老師在課堂中 (3/9) 提到，鏈結佇列關注的是快速動態記憶體管理，即記憶體塊間的連接關係，因此可能會牽涉到多執行緒甚至多行程對鏈結佇列的修改。實際去思考，在頻繁的修改下，維護長度的意義不大，反而可能有 race condition 等麻煩。 ::: <!-- 討論 END --> ### q_delete_mid > commit: [cca7225](https://github.com/Dennis40816/lab0-c/commit/cca72252278c46689732d10cf6b789261ac4ae0c) <!-- 目的 START --> **目的** 擦除(含記憶體釋放)佇列中第 $\lfloor n + 1 \rfloor$ 個元素，以 0^th^ 作為元素的第一個索引 (index)。注意是擦除節點，要先移出元素後才釋放。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** `head` 是 `NULL` 或空佇列 : 返回 `false` <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 使用兩指標 `tail`、`front` 指向 `head->prev`、`head->next`後作為起點，`front` 朝後移動，`tail` 朝前移動。 當指標相遇時 (元素個數為奇數) 或 `tail` 剛好超過 `front` 一個節點時 (元素個數為偶數)，`front` 必然指向要刪除的節點。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** - 修改該函式(返回類型、不要釋放記憶體)，便可完成獲取中間值的功能 ，可能應用場景為: - 在已排序鏈結串列中取中值。 - [分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT) 一文中提到，快慢指標較單一指標具備教好的時間局部性(降低 CPU 快取錯失)，那首尾指標和快慢指標是否有類似現象。按照邏輯，後者的時間局部性比前者好，那單一指標的時間局部性有可能比首尾指標好嗎?未來可用 `perf` 驗證這個想法。 **(待完成)** <!-- 討論 END --> ### q_delete_dup > commit: [25053d2](https://github.com/Dennis40816/lab0-c/commit/25053d23a4cea73aa2ea53a1a909903f087bd7e1) <!-- 目的 START --> **目的** 比較佇列元素與++兩側++的字串是否重複，如果重複就擦除。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. `head` 是 `NULL` 或空佇列 : 返回 `false` 2. 當下一個元素的 `list` 就是 `head` : 判斷字串是否重複，會用到下個元素的成員 `value` ， `head` 並未被包含在 `element_t` 實例中。故遇到下一個元素是 `head`，不能解引用 `value` (所以該++判斷要被放在字串比較前++) ，僅需再判斷++當前元素是否需要被擦除++。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 1. `list_for_each_entry_safe` 中的停止條件是當當前元素的 `list` 與 `head` 地址相同時。當目前元素字串和下個元素字串相同，則先移出當前元素，後釋放其記憶體。 2. 需要記住當前元素是否已經是重複元素，如果是，要移動至下一個元素++前++要先擦除該元素。 其中 `list_for_each_entry_safe` 的判斷式如下: ```c // do strcmp only if next list is not head // or safe->value might cause segmentation fault if (&safe->list != head && !strcmp(entry->value, safe->value)) { list_del(&entry->list); q_release_element(entry); last_dup = true; } else if (last_dup) { list_del(&entry->list); q_release_element(entry); last_dup = false; } ``` 觀察兩個分支刪除操作有重複的程式，是否能使其更精簡? 進一步分析 `last_dup` 會改變的情境只有以下兩點: - 擦除第一個重複元素後 ( `false` to `true` ) - 擦除最後一個重複元素後 ( `true` to `false` ) 而判斷式 `&safe->list != head && !strcmp(entry->value, safe->value)` 正決定 `last_dup` 的狀態。所以如果我們將判斷式先賦值到 `cur_dup`，當符合 `cur_dup` 或 `last_dup` 都要刪除，並更新 `last_dup` 狀態，就能得到更精簡的程式: ```diff -if (&safe->list != head && !strcmp(entry->value, safe->value)) { +bool cur_dup = (&safe->list != head && !strcmp(entry->value, safe->value)); + +if (cur_dup || last_dup) { list_del(&entry->list); q_release_element(entry); - last_dup = true; -} else if (last_dup) { - list_del(&entry->list); - q_release_element(entry); - last_dup = false; + last_dup = cur_dup; } ``` <!-- 實作流程 END --> <!-- 討論 START --> **討論** 1. 遇到以下靜態檢查錯誤: **(有疑問)** ```bash queue.c:155:5: style: Label 'int' is not used. [unusedLabel] list_for_each_entry_safe (entry, safe, head, list) { ``` 先前編譯未出現此錯誤， <!-- 討論 END --> ### q_swap > commit: [e0ac6f8](https://github.com/Dennis40816/lab0-c/commit/e0ac6f82c4d8fbabc41170cac0117e56d14de13a) <!-- 目的 START --> **目的** 以兩個元素為一組進行位置交換，完成後換下一組，直到下一個元素是未成對節點(剩一個節點)或是佇列的 `head`。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** `head` 是 `NULL` 或空佇列: 直接返回。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 1. 一開始初始化兩個指標，`l1`、`l2`。 2. 交換指標時，遵循以下順序循環: 1. `l1` 初始值為 `head->next`，`l2`初始值為 `head->next->next`。之後更新是 `l1` 指向 `l1->next`，`l2` 指向 ~~`l1->next->next`~~ ==新的== `l1->next`，因為 `l1` 已更新。 3. 檢查 `l1`、`l2` 的地址不是 `head`，否則結束。 4. 先斷開 `l1->next` 和 `l2->prev`，因為知道這兩個指標最後指向 `l1`、`l2`。 5. 將 `l2->prev` 指向 `l1->prev`，`l1->next` 指向 `l2->next`，該步驟將 `l1` 和 `l2` 的對左右兩側鏈結設定完畢。 6. 設定左右兩側對 `l1` 和 `l2` 成新的關係，`l1->next->prev` 指向 `l1`，`l2->prev->next` 指向 `l2`。 7. 剩下 `l1->prev` 和 `l2->next` 指向彼此，即 `l1->prev` 指向 `l2`，`l2->next` 指向 `l1`。 3. 結束並返回 得到的實作如下: ```c for (l1 = head->next, l2 = head->next->next; l1 != head && l2 != head; l1 = l1->next, l2 = l1->next) { l1->next = l2->next; l2->prev = l1->prev; l1->next->prev = l1; l2->prev->next = l2; l1->prev = l2; l2->next = l1; } ``` 進一步觀察，上述的過程是將 `l1` 先移出鏈結串列後，並移到以 `l2` 為開頭的鏈結串列中，最後移動 `l2` 指向 `l1` 的下一個元素。可以使用 `list_for_each_safe` 當作走訪循環，其會檢查 `l1` 是否與 `head` 重合，並將 `l1` 賦值 `l2`。因此，我們僅需額外做: - 判斷 `l2` 是否是 `head` (奇數個元素時) - 將 `l2` 往 `l1` 下一個移動 (避免循環賦值時跑回上一個元素) 故上述可用以下代替: ```c list_for_each_safe (l1, l2, head) { if(l2 != head) { list_del(l1); list_add(l1, l2); l2 = l1->next; } } ``` <!-- 實作流程 END --> <!-- 討論 START --> **討論** 目前的交換並非執行緒安全的，是否有改進空間? **(待完成)** <!-- 討論 END --> ### q_reverse > commit: [2eef976](https://github.com/Dennis40816/lab0-c/commit/2eef976c076511b2c1ac06550d63b9c73e09e5b7) <!-- 目的 START --> **目的** 反轉佇列內所有元素順序。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. ++禁止++任何記憶體配置相關操作( `malloc`、`free` )，如 `q_new` 、`q_insert_head` 和 `q_insert_tail`。 2. 當 `head` 是 `NULL`，或元素數量是 0 或者 1: 直接返回。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 只要我們知道原本最後一個元素的 `list` 地址 ( `tail` )，則只要透過 ~~`list_for_each_safe`~~ `list_for_each_safe_prev` 重複將 `node` 移動到 `tail` 的下一個元素就好了。移動可用 `list_move` 完成。 或者，可以固定第一個節點不動，剩下的節點都往前移動。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 透過首尾指標指向要彼此互換的元素後進行互換? **(待確認)** - CPU 快取的時間局部性 (temporal locality) 如何變化? <br> >時間局部性應該會變差。 **(待確認)** - 走訪節點的數量會上升? 會更快嗎? <!-- 討論 END --> ### q_reverseK > commit: [82a841f](https://github.com/Dennis40816/lab0-c/commit/82a841fa3a4ad041520a7a88d7febcce86918f46) <!-- 目的 START --> **目的** 從頭開始以 K 元素分組，將每組內的元素反轉後，按原組別順序串接。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. `head` 為 `NULL` 、空佇列或單一元素佇列: 直接返回。 1. `k` 為 `1` : 不需反轉，直接返回。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** :::danger 不要濫用「邏輯」一詞，這裡只是闡述「流程」。 >已更正。 ::: :::danger 當描述節點或資料單元間的關係時，head 譯作「開頭」，而非「頭」，後者是生理詞彙。 >了解。 ::: 如果使用兩個額外的鏈結串列開頭 ( `struct list_head` ) 元素( `final` 和 `tmp` )，作為暫時節點使用 (out-of-place 的方法)，首先可利用 `list_cut_position` 分割想要的串列到 `tmp` 之中。之後，使用先前實作的 `q_reverse` 反轉 `tmp` 內節點，並串接到 `final` 的尾部。最終，將 `final` 串接到 `head` 開頭處 (避免有殘存節點)。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** <!-- 討論 END --> ### q_ascend > commit: [c4a4f03](https://github.com/Dennis40816/lab0-c/commit/c4a4f037723e426fcfdcb05ee8c60608371abc06) <!-- 目的 START --> **目的** 透過 ++擦除++ 佇列中元素達到升冪排列(可允許元素值相同)，注意與 `q_sort` 使用排序方法不同。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. 前元素~~須++嚴格小於++後面所有元素~~ ++不可++ 大於後面所有元素。題幹中: > has a node with a strictly less value anywhere to the right side of it。 表示要有++嚴格小於++當前元素的值才需擦除當前節點。換句話說，如果右邊的值跟當前值相同，++不用擦除++。 1. 如果後面有更小的元素，則前面所有比他大的元素都要被刪除。 1. 若是 `head` 是 `NULL`、空佇列，直接返回 `0` ;若是單一元素佇列返回 `1` 。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 根據 ++特殊狀況描述 - 2++，我們應該從鏈結串列的++尾部++開始，以最後一個元素的值當作++上限++參考值，逐漸往前移動，當遇到目前節點的值++大於等於++上限參考值，移除該節點，否則更新當前值為新上限參考值。 我參考了 [list_last_entry](https://github.com/torvalds/linux/blob/76544811c850a1f4c055aa182b513b7a843868ea/include/linux/list.h#L622C1-L623C39) 去實作: 1. 使用一個變數 `bound_val` (pointer to char) 儲存當前的上限值地址，初始值為最後一個元素的 `value` 地址。 2. 起始的 `node` 和 `safe` 分別是倒數第二個元素和第三個元素，已經排除只有單一元素的情況，故僅需++判斷 `node` 是否是 `head` 當作結束條件++。 3. 使用 `strcmp` 比較 `node->value` 和 `bound_val`，只有結果++大於 `0`++ 要移除當前節點 ( 返回值可參考 [strcmp(3) — Linux manual page](https://www.man7.org/linux/man-pages/man3/strcmp.3.html))。 4. 若 (3) 為非，則 `size` 加 `1` ，並更新上限值為當前的 `node->value`。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 1. 起初想到的做法是透過 `list_for_each_entry_safe` 往後走訪，比較 `node` 和 `safe` 值得大小，如果 `node` 比 `safe` 大就刪除 `node`，但發現這種做法++不符合題意++，且在以下情況出錯: ```bash l = [1 2 4 3 7 8 1] cmd> ascend ERROR: At least one node violated the ordering rule l = [1 2 3 7 1] # 8 比 1 大所以被刪除了 ``` 後改用逆向走訪的方式。 2. 由於目前的 `list.h` 中沒有逆向走訪的 API，但是在 `linux/list.h` 是有實作 [list_for_each_prev_safe](https://github.com/torvalds/linux/blob/76544811c850a1f4c055aa182b513b7a843868ea/include/linux/list.h#L729) 和 [list_for_each_entry_safe_reverse](https://github.com/torvalds/linux/blob/76544811c850a1f4c055aa182b513b7a843868ea/include/linux/list.h#L903C9-L903C41)，可引為參考。 <!-- 討論 END --> ### q_descend > commit: [c4a4f03](https://github.com/Dennis40816/lab0-c/commit/c4a4f037723e426fcfdcb05ee8c60608371abc06) <!-- 目的 START --> **目的** 類似 `q_ascend`，只是要求前元素不可 ++小於++ 後面任一元素。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 同 `q_ascend` 。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 似 `q_ascend`。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 1. `q_ascend` 和 `q_descend` 只差在 `strcmp` 時一個是大於一個是小於。可透過巨集 (e.g., `Q_ASCEND` ) 搭配 cmp function 陣列，將只要 A 就擦除目前節點的邏輯合併在同一個函式中重用，只需要傳入一個不同的 cmp function (參考 C++ 允許使用者定義 cmp 函式) 。初步構想如下 **(待完成)** : ```c #define Q_ASCEND (0) #define Q_DESCEND (1) typedef bool (cmp_fp*)(void* a, void* b); static cmp_fp cmp_f[2] = {cmp_f1, cmp_f2}; bool cmp_f1(void* a, void* b) { return strcmp((char*)a, (char*)b) > 0; } bool cmp_f2(void* a, void* b) { return strcmp((char*)a, (char*)b) < 0; } bool q_remove_at(void* a, void* b, cmp_fp cmp) { if (cmp(a, b)) { /* remove element here */ return true; } return false; } int q_ascend(struct list_head *head) { /* ... */ if (q_remove_at(node->value, bound_val), cmp_f[Q_ASCEND]) /* ... */ } ``` 2. 對於已知長度的節點值比較 (e.g., `int`) ，使用 `void*` 作為參數型別可以增加通用性，那是否能直接比較 `void*`，其實有 `memcmp` 可以選擇。但在比較函式內還是建議強制轉型成原本的型別，避免在不同位元組順序 (endianness) 的機器上，比較結果++不一致++。 舉個例子，`0x1234` 和 `0x1333` 若使用 `memcmp` 比較，在大位元組順序 (big endian) 機器的結果會是 `0x1335` 會比較大( `0x13` > `0x12` )，但在小位元組順序時會是 `0x1234` 比較大 ( `0x34` > `0x33` )。可以查看 compiler explorer 的[示例](https://godbolt.org/z/9s4hbae6e)。 <!-- 討論 END --> ### q_merge_two > commit: [311e580](https://github.com/Dennis40816/lab0-c/commit/311e580036495d2967107291c7016e76b2b34569) <!-- 目的 START --> **目的** 該函式是 `q_merge` 的輔助函式，專注於合併兩個佇列，並確保返回時，是第一個佇列 `l1` 擁有所有元素。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. 不允許 heap allocation。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** ```c static int q_merge_two(struct list_head *l1, struct list_head *l2, bool descend) { if (!l1 || !l2) { struct list_head *valid = l1 ? l1 : l2; if (l1 != valid) { list_splice(valid, l1); } return q_size(valid); } ``` 首先檢查 `l1` 和 `l2` 是否是 `NULL`，如果其中一個是 `NULL`，將所有元素移動到 `l1` 上。但有幾個錯誤: - 未考慮 self-splice 的情況 ( `list_splice` 不能 self-splice，帶值進去看可知 )。 - 當 `l1` 是 `NULL`， `list_splice` 會對 `NULL` 解引用。 故修正如下: ```diff static int q_merge_two(struct list_head *l1, struct list_head *l2, bool descend) { - if (!l1 || !l2) { - struct list_head *valid = l1 ? l1 : l2; - if (l1 != valid) { - list_splice(valid, l1); - } - return q_size(valid); + /* no heap allocation; return size if one list is NULL */ + if (!l1 || !l2) + return q_size(l1 ? l1 : l2); + + /* if a list is empty, splice l2 into l1 (if l1 is empty) to avoid + * self-splice */ + if (list_empty(l1) || list_empty(l2)) { + if (list_empty(l1)) + list_splice(l2, l1); + return q_size(l1); } ``` 接著看到主要邏輯，當兩個佇列都為非空時，根據 `descend` 獲取對應的節點地址並放到 `dummy` 的尾部: ```c int size = 0, cmp; LIST_HEAD(dummy); element_t *node1, *node2, *next; for (; !list_empty(l1) && !list_empty(l2); ++size) { node1 = list_first_entry(l1, element_t, list); node2 = list_first_entry(l2, element_t, list); cmp = strcmp(node1->value, node2->value); next = descend ? (cmp > 0 ? node1 : node2) : (cmp > 0 ? node2 : node1); list_move_tail(&next->list, &dummy); } ``` 對此有個疑問，要將變數放在外面還是環圈內部呢?透過 [compiler explorer](https://godbolt.org/z/dhhf9cc9f) 我們知道現代編譯器並不會在迴圈內重複進行 stack allocation，只會在進行函式時進行。此外，對於某些 ABI (e.g., x86_64 SysV ABI)，當所用的區域變數大小不大時(對於 x86_64 SysV ABI 為 128 bytes 內)，因為每個函式有紅區 (red zone)，所以 stack allocation [不會發生](https://godbolt.org/z/on64T95KP)，即不會對 `rsp` 進行 `sub` 指令。 因此秉持著當變數使用才宣告，應該在++迴圈中才宣告或定義迴圈內變數++: ```diff -int size = 0, cmp; +int size = 0; LIST_HEAD(dummy); -element_t *node1, *node2, *next; for (; !list_empty(l1) && !list_empty(l2); ++size) { - node1 = list_first_entry(l1, element_t, list); - node2 = list_first_entry(l2, element_t, list); - cmp = strcmp(node1->value, node2->value); - next = descend ? (cmp > 0 ? node1 : node2) : (cmp > 0 ? node2 : node1); + element_t *node1 = list_first_entry(l1, element_t, list); + element_t *node2 = list_first_entry(l2, element_t, list); + int cmp = strcmp(node1->value, node2->value); + element_t *next = + descend ? (cmp > 0 ? node1 : node2) : (cmp > 0 ? node2 : node1); list_move_tail(&next->list, &dummy); } ``` 剩下的流程是將剩下的那個佇列全部元素貼到 `dummy` 尾部，++注意要使用 `list_splice_tail_init`++，避免 `l1` 被貼到 `dummy` 後變成無效的 `head`，致使下一個步驟變成未定義行為。最後再將 `dummy` 所有元素貼到 `l1` 後面，即可返回。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 暫無。 <!-- 討論 END --> ### q_merge > commit: [311e580](https://github.com/Dennis40816/lab0-c/commit/311e580036495d2967107291c7016e76b2b34569) <!-- 目的 START --> **目的** 將 `head` 所指向的佇列鏈 (queue chain) 中所有的佇列按給定的規則 (升/降冪) 合併至該鏈的第一個佇列中。佇列鏈中所有元素都被++保證++是依給定規則排列的。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. 若佇列鏈中佇列個數 ( `q_contex_t` 實例個數) 為 `1`，直接返回該佇列的元素個數。 2. 若佇列鏈頭部是 `NULL`，直接返回 `0`。 3. ++不允許++ 記憶記憶體配置。 4. 需負責釋放++除第一個佇列++外，所有佇列使用的記憶體 (此時應只包含 `struct list_head` 實例)，並在釋放後更改該 `q_contex_t` 的成員 `q` 指向 `NULL`。但我對這點存疑，因為 `q_merge` 在測試時是不允許釋放記憶體，直接改成 `NULL` 會讓 `head` 記憶體洩漏。 5. 需統計合併完後的總元素數量，並返回。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** `q_merge` 可以使用 `q_merge_two` 方式將兩佇列合併。但問題在於，應該使用哪種?線性還是樹狀合併呢? 經過 ++討論 (2)++ 後，決定實作兩者，以利後續比較。 不同方法在前面做的事情即先排除 **特殊狀況描述** (1-2)。 **Tree-like merge** 先統計有幾個佇列，並記為 `q_count` ，稍後的合併間隔只能++小於++ `q_count` ( `q_count - 1` 是合併間隔的最長距離)。接著用兩層迴圈進行合併過程，第一層迴圈只做一件事情: 計算合併間隔 ( `iter_diff` ) 新的值，循環持續條件為 `iter < q_count`。 `iter_diff` 從 `1` 開始，為 2 的冪，因此可能左移代替乘法。 下一層迴圈則透過整數變數 `bias` 記憶目前走訪過程離第一個有效節點( `head->next` ) 的距離，當該值超過 `q_count`，迴圈結束，每次循環時 `bias += (iter_diff << 1)`，累積上一輪中已經移動的距離去進行判斷。 在迴圈內部移動兩個佇列指標，並透過 `list_iter_n` 移動 `iter_diff` 的距離，注意 `list_iter_n` 設計為當碰到 `head` 的時候會返回 `head`，避免超過 `head` 的窘況。移動順序是前指標從後指標位置執行 `list_iter_n`，後指標再從++新的++前指標執行 `list_iter_n`，以避免每次都從頭走訪的成本，來達到++討論 (2)++ 說的每輪合併的走訪成本是 $O(n)$。 **Sequential merge** 與上述不同主要在如何找到目標上，本方法只需保留最前面的佇列，以及 `next` 的佇列，持續往後移動 `next` 從頭到尾走訪過一次，就能達成目標。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 1. 由於 ++特殊狀況描述 (2)++，使用變數儲存每個佇列的首元素值是不合適的 (heap based merging)。而每次都使用走訪每個佇列的首元素找尋最小值又太沒效率。[jimmylu890303 的實作中](https://hackmd.io/@jimmylu0303/linux2024-homework1#q_merge)提到可建立 `mergeTwoLists` 將併入過程拆成兩個佇列的合併。<br> 在使用陣列紀錄佇列開頭時，合併兩個佇列的方式有兩種，++線性合併++和++樹狀合併++。前者是先合併 0^th^ 和 1^th^，再來合併 0^th^ 和 2^th^，不過會隨 0^th^ 佇列長度越來越長導致平均合併時間越來越久。 後者是將所有佇列都先兩兩分組，將 0^th^、 1^th^ 合併至 0^th^，2^th^、3^th^ 合併至 2^th^，依此類推，最終 0^th^ 和 n^th^/2 合併至 0^th^ 。該方式的優勢在合併前的平均佇列長度較前方法更短，因此平均的耗時會較低。故陣列實作通常採用後者。但對鏈結串列是否依然如此呢?老師說要多使用數學，所以下面嘗試用數學進行分析:**(待確認)**<br> **++前提假設++** - 每個佇列都是有序的。 - 佇列的長度分布均勻。 **++符號定義++** $n$ : 佇列數量 ( `q_contex_t` 實例數量)。 $L$ : 佇列平均元素長度。 **++複雜度組成++** 由於鏈結串列的存取時間複雜度跟陣列不同，因此除了合併的複雜度外，應該額外探討對 ++找到下一個++ 合併目標的時間複雜度。 **++線性合併複雜度分析++** 該法對找到下一個合併目標是++有利的++，因為只需持續向後走訪就能知道下一個合併的目標是誰，且走訪完一次就已經完成合併，故++佇列鏈時間複雜度++為 $O(n)$。 而對於++合併時間複雜度++，在第一輪為 $O(L+L)$，第二輪為 $O(2L+L)$，最後則為 $O(nL)$ ，其總和可用以下函數表示: $$ T_{seq} = \sum^{n-1}_{i=1} O((i+1)L) = O(L\sum^{n-1}_{i=1} (i+1))=O( \frac{n^2+2n-1}{2}L) $$ 總時間複雜度為: $$ O(\frac{n^2 + 4n - 1}{2}L) $$ **++樹狀合併複雜度分析++** 對於++佇列鏈時間複雜度++，每次走訪完整個佇列鏈會將目前佇列鏈的有效元素減半，故長度為 $n$ 的佇列鏈共需走訪 $\log_2 (n)$ 次，時間複雜度記為 $O(\log (n))$ 。每次走訪完整鏈結串列的時間複雜度為 $O(n)$，因此合計為 $O(n \log(n))$。 對於合併而言，在第一輪有 $n/2$ 對，每對的合併複雜度為 $O(2L)$，故第一輪的時間複雜度為 $O(\frac{n}{2} \times 2L)$。第二輪則有 $n/4$ 對，每對的合併複雜度為 $O(4L)$，第二輪時間複雜度與第一輪同。總共有 $\log n$ 輪，故合併複雜度可記為: $$ O(nL \log (n)) $$ 總複雜度為: $$ O(n \log(n)) + O(nL \log (n)) = O(n \log n(L+1)) $$ **++總結++** 在數據量較大時，無疑樹狀合併較優，但還是要==注意是否有 edge case==，例如原始的佇列長度極度不均勻(全都集中在第一個佇列上)，或是佇列長度很短 ( $L$ 為 1，在 $n$ 從 1 到 3 區間，樹狀合併較慢 )。最後提供兩者複雜度在 desmos 上的 [繪製結果](https://www.desmos.com/calculator/jroxrck7q6)。其中紅色是線性合併，綠色是樹狀合併，設定 L = 5。 <iframe src="https://www.desmos.com/calculator/jroxrck7q6?embed" width="500" height="500" style="border: 1px solid #ccc" frameborder=0></iframe> 1. 是否能為 ++討論(2)++ 添加實驗證明? 並添加 cache 比較? **(待完成)** 1. 樹狀合併的迴圈結束條件是否能更精簡? **(待確認)** <!-- 討論 END --> ### q_sort > commit: [b82b952](https://github.com/Dennis40816/lab0-c/commit/b82b9523a7d85808cc27c3c49c77d5c412d21367) <!-- 目的 START --> **目的** 排序給定佇列，順序依照 `descend` 的值決定。 <!-- 目的 END --> <!-- 限制與狀況 START --> **特殊狀況描述** 1. 時間複雜度須在 $O(n \log n)$ 級別以通過 100, 000 個元素的測試。 2. 若 `head` 是 `NULL`、空佇列、或單元素佇列，直接返回。 <!-- 限制與狀況 END --> <!-- 實作流程 START --> **實作流程** 由於在 `q_merge` 中，我們已經實作了 `q_merge_two` 用來合併兩個有序的佇列，也有 `list_iter_n` 來返回目前節點下面 `n` 個的節點地址。我們能基於已有函式實作 merge sort。 流程如下: 1. 計算當佇列的總元素數量，該值影響 `iter_diff` 的上限。 2. 同 `q_merge`，`iter_diff` 從 `1` 開始，為 `2` 的冪，當 `iter_diff` 小於總元素數量，外層迴圈繼續。 3. 外層迴圈定義了 `new_head`，用來儲存每輪排序好的元素。 4. 內層迴圈在 `head` 不為空 (元素還沒被移到 `new_head` )時，從 `head` 開始，每次拿取前 `iter_diff` 個元素放到 `left`，再繼續擷取 `iter_diff` 個放到 `right`，拿取過程藉由 `list_cut_n` 函式完成。 5. 將切完的 `left` 和 `right` 透過 `q_merge_two` 合併到 `left` 中，因為 `iter_diff` 從 `1` 開始，因此可確保進入的佇列都符合 `q_merge_two` 的要求，即 ++兩個佇列都已依照 `descend` 排序++ (因為從單元素佇列開始，沒有順序問題)。 6. 將 `left` 接到 `new_head` 後，判斷內迴圈是否結束，未結束就回到 (4)。 7. 內迴圈結束 (`head` 為空) 時，將 `new_head` 元素移回 `head`，並判斷外迴圈是否結束，未結束回到 (3)。 上述步驟完成後便已經完成排序。且複雜度是 $O(n \log n)$。 <!-- 實作流程 END --> <!-- 討論 START --> **討論** 1. 目前在迴圈部分與 `q_merge` 有部分相似，能否簡化? **(待完成)** <!-- 討論 END --> 至此，作業中有關佇列操作的函式已完成實作，是時候研讀在 linux 中 ## 新增 shuffle 命令與 prng 選項 在本節中，預計達成以下目標: - 新增 `shuffle` 命令，使當前佇列進行++洗牌++。 - 新增 `prng` 選項，讓使用 `ih RAND xx` 時，使用者可選擇調用預設的 syscall 還是 - 分析不同 PRNG 對 `ih RAND` 指令的影響，指標可使用香農熵 (Shannon entropy) 評估。 以下先探討 lab0-c 的如何新增命令，接著探討 Fisher–Yates shuffle 和 PRNG，並了解目前 lab0-c 預設的隨機字串是如何產生的。了解後研討如何設計相關界面來達成上述目標，最終透過香農熵輔以其他統計手段分析結果與差異性。 ### 如何為 lab0-c 增加新的命令? 在 `console.h` 中提供了 `ADD_COMMAND` 巨集，對應到 `add_cmd` 函式，其宣告如下: ```c #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) void add_cmd(char *name, cmd_func_t operation, char *summary, char *param) { ``` 最關鍵的是 `operation`，透過巨集會自動被展開成 `do_<cmd>`，所以只需實現 `do_xxx` 並透過 `ADD_COMMAND` 註冊 `xxx` ，就能在命令行界面中看到 `xxx` 嘍! `cmd_func_t` 的定義是: ```c typedef bool (*cmd_func_t)(int argc, char *argv[]); ``` 當要解析在命令行中的命令並執行是透過 `interpret_cmd` 達成的，其中呼叫 `interpret_cmda` 是真正調用 `do_xxx` 所在，該函式也會根據 `do_xxx` 的返回值進行 `report`。 ### Fisher–Yates shuffle 最初的 Fisher-Yates 演算法在 1938 年被提出，後在 1964 年為計算機進行改良，並隨後在《 The Art of Computer Programming 》以 Algorithm P 的形式亮相。該算法期望每一種排序結果的機率是平均且一致的。 如果基於長度為 `n` 的陣列 `a` 來說明，1964 年算法的核心想法並不複雜: 1. 設定變數 `i`，初始值為 `n-1`，另產生 ++隨機數++ `j` ，其範圍是從 `0` 到 `i`，該隨機數將作為要交換的索引。 2. 交換 `a[i]` 和 `a[j]`，也就是把選出來的數丟到尾部。 3. `i--` 後重複 (1)，直到 `i` 小於 `0`。 :::info 維基百科的說明中，我們應++格外留意++ [Potential sources of bias](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Potential_sources_of_bias)，這些錯誤可能讓部分結果永遠不可能出現，進而破壞該演算法的隨機性。 ::: 針對鏈結串列的洗牌演算法複雜度進行分析: 該算法主要的時間複雜度取決++走訪++目標節點的過程。與陣列是 $O(1)$ 不同，由於鏈結串列走訪至第 `n` 個節點的時間複雜度就是 $O(n)$，因此基於鏈結串列的洗牌算法理論時間複雜度是 $O(n^2)$級別。更精確的說，假設產生隨機數的函式「夠隨機」，則每個節點被選中的機率是相同的。因此每一輪走訪成本期望值是: $$ E[X_k] = \frac{1}{k} \sum^k_{i=1}i= \frac {k+1}{2} $$ 其中 $k$ 是剩餘節點數量。整個演算法花在走訪的成本是: $$ E[T]= \sum^n_{k=1} E[X_k]= \sum^n_{k=1} \frac{k+1}{2} \underset{\text{Sum of an arithmetic series}}{=}\frac{n(n+3)}{4} $$ 因此具體時間複雜度是 $O(\frac{n(n+3)}{4})$。當然，可以藉由計算從開頭走訪還是從尾部走訪進一步減少，但量級依舊為 $O(n^2)$，而非 $O(n)$。 ### PRNG (Pseudo Random Number Generators) PRNG 具有若以相同種子傳入，能得出相同亂數序列的特性。換言之，其亂數過程是明確且具重複性的，這有利於對產生序列的亂度分析。 lab0-c 中提供 `it RAND XX`，若有 `RAND` 將變更 `need_rand` 的值為真，進而呼叫 `fill_rand_string`。 `fill_rand_string` 有兩處用到隨機數: - 產生隨機字串長度時，使用 stdlib 的 `rand`。需要注意，++`srand` 在 `main` 中已經被呼叫++。 - `randombytes` 中，呼叫 `linux_getrandom` ➞ `getrandom`，後者是系統呼叫。 查閱 2.39 版的 glibc/stdlib/rand.c 發現，`rand` 呼叫 `__random(&unsafe_state, ...)` ➞ `__random_r`，後者在 `random_r.c` 中。`unsafe_state` 是靜態變數，預設 `rand_type` 是 `TYPE3`，`TYPEx` 定義如下: ```c /* Linear congruential. */ #define TYPE_0 0 #define BREAK_0 8 #define DEG_0 0 #define SEP_0 0 /* x**7 + x**3 + 1. */ #define TYPE_1 1 #define BREAK_1 32 #define DEG_1 7 #define SEP_1 3 /* x**15 + x + 1. */ #define TYPE_2 2 #define BREAK_2 64 #define DEG_2 15 #define SEP_2 1 /* x**31 + x**3 + 1. */ #define TYPE_3 3 #define BREAK_3 128 #define DEG_3 31 #define SEP_3 3 /* x**63 + x + 1. */ #define TYPE_4 4 #define BREAK_4 256 #define DEG_4 63 #define SEP_4 1 ``` 所以預設使用的是 $x^{31} + x^3 + 1$ 這組。除了 `TYPE 0` 是 LCG 其他都是 LAFM（Linear Additive Feedback Method）。因此網路上說 `rand` 使用 LCG 實現是不符合預設情況的。 接著，透過 `man getrandom` 可知，其預設行為是從 urandom 源 (/dev/urandom) 獲取。值得一提的是，`getrandom` 是 CSPRNG (Cryptographically Secure Pseudorandom Number Generators)，為密碼學安全的，其內部的熵池會隨著中斷等不停改變，這也導致 `getrandom` 很難複現。但由於演算法依然是確定的，所以依然是 PRNG，只是種子的熵值非常高，且無法由用戶態保存種子。 Linux 有提供許多 user space 能使用的隨機數源，可參考[〈初探 Linux kernel 亂數產生器 – random generator 〉](https://szlin.me/2016/10/05/%E5%88%9D%E6%8E%A2-linux-kernel-%E4%BA%82%E6%95%B8%E7%94%A2%E7%94%9F%E5%99%A8-random-generator/)。 ### 實作 - [Blog: xoroshiro generators and the PRNG shootout](https://prng.di.unimi.it/) (未來可增加) - [Paper: Fast Random Integer Generation in an Interval](https://arxiv.org/abs/1805.10941) (提到 OpenBSD 的作法) - [Paper: Xorshift](https://www.jstatsoft.org/article/download/v008i14/916) (裡面提到為甚麼選擇這幾個數字) 本節可分為 **shuffle** 和 **prng**，不過在這之前，先來探討兩者共用的部份 ── ++**隨機數**++。 產生隨機數的程式可以單獨分離成一個部分，放置在 `random.[ch]` 中。分離後， `q_shuffle` 和產生隨機字串的函式 `fill_rand_string` 能夠重複使用，減少冗餘程式。可以實作的選項包含 Xorshift、PCG 等。所有隨機數函式的界面應該統一為: ```c typedef int (*rand_func_t)(uint8_t* buf, size_t n); ``` 該界面與當前的 `randombytes` 一致(也與 `getrandom` 一致)，具有較好的兼容性，且後續可實作 `prng` 選項選用特定的 PRNG。 目前 Xorshift 已經被實作在 `random.c`，初始狀態使用 `2463534242UL`。 > commit: [af1273f](https://github.com/Dennis40816/lab0-c/commit/af1273f646d02bfd5bab7e70db438425fd0157aa) #### shuffle > commit: [0d63c0e](https://github.com/Dennis40816/lab0-c/commit/0d63c0e8e3cc2d4e06e7374b396a07bf26cb54b4) 在第一次完成實作後，檢查實作中是否參雜違維基百科中提到的可能偏差。其中提到使用取餘需要考慮被餘數是否能整除餘數，如果不能，則靠前的數字會比靠後的數字選中的機率高 (modulo bias) 。舉個例子，`rand() % 9` 中，假設 `rand` 產生的範圍是 0 - 100，99 和 100 的結果會是 0 和 1，會使這兩個數字比其他數字多一次可能被選到: ```c uint32_t j; prng_funcs[prng]((uint8_t *) &j, sizeof(uint32_t)); j = j % i; ``` 為修正該偏差，引入並修改 OpenBSD 的方法: ```c static uint32_t unbias(uint32_t upper, rand_func_t func) { // Calculate threshold value to eliminate bias. uint32_t t = (-upper) % upper; uint32_t x; do { func((uint8_t *) &x, sizeof(uint32_t)); } while (x < t); return x % upper; } ``` 其中用到 `-upper` 其實代表 `UINT32_MAX + 1`，也就代表隨機數所有可能的數量總和 ( `0` ~ `UINT32_MAX` )，接著對 `upper` 取餘，得到的結果是該集合中會多出幾個元素。假設結果 `t` 是 `2`，就代表 `0` 和 `1` (都是從 `0` 開始算)會多一組，所以要替除。因此當 `x < t`，也就是骰出來的 ++隨機數 `x`++ 是 `0` 或 `1` 時，`x` 要重骰一次。 同時，為確保 `q_shuffle` 能夠放在 `queue.h`，更新了 `chechsum.sh` 中 `queue.h` 的 `sha1sum`。 > 若能在 queue.h 包含 `q_shuffle(void*)` API ，可以方便大家利用 void pointer casting 實作，同時避免 rebase 的時候要改 checksum。 #### prng > commit: [af1273f](https://github.com/Dennis40816/lab0-c/commit/af1273f646d02bfd5bab7e70db438425fd0157aa) 現透過 `option prng 1` 可以設定採用 Xorshift， `0` 為預設，使用 `getrandom`。值得注意的是，原本程式中使用 `randombytes` 並未修改，因此不受 `prng` 影響。所以該選項目前只影響 `fill_rand_string` 和 `q_shuffle` 的行為。 ### 結果分析 > commit: [522a327](https://github.com/Dennis40816/lab0-c/commit/522a32788aeea48626f32f2b256094cf48c494e6) - improve `source` > commit: [0653289](https://github.com/Dennis40816/lab0-c/commit/06532890e1656165aeb6ef1f8f995b1468a3dd13) - add shuffle related trace files > commit: [e93e959](https://github.com/Dennis40816/lab0-c/commit/e93e95975e6f419ebcf05d41cde7b36c7a88bcf9) - shuffle analyzer 為測試 `shuffle` 命令，我擴展了 `source` 的功能，使其能多接收參數 `n` 作為要 `source` 同檔案幾次。為避免 `n` 太大導致超過 `FD_SET` 出現錯誤，我添加了字元陣列 `cached_cmd` ，當已經不能再 `push_file`，則先暫存剩餘的 `source` 命令。當暫存命令長度為不 `0` 時，先執行暫存的命令。最終可搭配類似命令蒐集數據: ```cmd # The enter point for shuffle verification option echo 0 new log <log-name>.log ih RAND 10 # start shuffle * 4000000 source traces/shuffle_once.cmd 4000000 ``` 雖然現在依然有待改進之處，但已經能進行初步數據蒐集工作: 1. 有時候會遇到 timeout 2. 目前做不到: ```cmd ## This file is traces/shuffle.cmd log a.txt source traces/shuffle_once.cmd 1000000 log b.txt source traces/shuffle_once.cmd 1000000 # 大部分資料會被寫到 b.txt 中 ``` - 推測是因為 `cmd_done` 迴圈會把所有 fd 都讀完。以上面為例，當 `log a.txt` 被執行完，下一句是 `source traces/shuffle_once.cmd 1000000`，因為數量很大所以 `cached_cmd` 被啟用。接著進入 `cmd_done` 迴圈，當這次所有被推入 `buf_stack` 的 `shuffle_once.cmd` 被處理完後，`shuffle.cmd` 就是下一個 `buf_stack` 儲存的 cmd，所以 `log b.txt` 就被 `readline` 讀出並執行了。這就是為什麼目前多次 `source` 不會遵循順序執行的原因。 - 要解決該問題，需要紀錄當 `cached_cmd` 被使用到 (當前情況下，只有 `source` 命令可能用到) 時，其根 stack_buf (此例為 `shuffle.cmd` 所在的 stack_buf ) 為何，並變更 `cmd_done` 判斷條件，當目前使用了 `cached_cmd` 時，執行到被記錄的根 `stack_buf` 就要停止，進入下一輪，讓 `cached_cmd` 繼續被推入 stack_buf 中，直到 `cached_cmd` 結束。 3. 有時候會遇到 dereference NULL pointer。 #### shuffle 實驗比較了兩種隨機數生成方法：Xorshift 與預設的 `getrandom`。這兩種方法皆在取得隨機數後採用 OpenBSD 的餘數偏差移除技術，以確保生成的數值分佈更為均勻。為了評估這兩種方法在洗牌演算法中的效果，我們各自進行了兩次實驗，每次對一組長度為 10 的隨機字串連續進行 4,000,000 次洗牌，並以 100,000 次為一組，將整個洗牌過程劃分為 40 個區塊。這樣的設計可以幫助我們觀察在不同區塊中，洗牌結果是否存在系統性的偏差，並進一步分析隨機數序列與洗牌結果之間的關聯性。 > python script commit: [e93e959](https://github.com/Dennis40816/lab0-c/commit/e93e95975e6f419ebcf05d41cde7b36c7a88bcf9) - shuffle analyzer 首先，透過 AI 協助，將分析工具分類成解析器、統計工具、繪圖工具和主程式四個部分。 parser 模組將原始日誌檔案解析為結構化的二維資料。具體而言，檔案開頭的一行(例如 `l = [A B C D E F G H I J]` )會被解析為候選亂數列表。隨後，在 `# start shuffle` 之後，每一筆洗牌結果都被依據區塊 ( `section` ) 劃分，且在每個區塊中，我們分別統計了每個關鍵字在不同位置上的出現次數，形成如下的資料結構： > section[n]["keyword"][k] 這表示第 `n` 個區塊中，關鍵字在第 `k` 個位置的累計次數。這種結構可以精確保留每個區塊內不同位置的統計數據，從而避免將各位置數據混合後因正負偏差抵消而看不到局部異常的情況。 在統計分析階段，我們採用了兩種策略: 1. **固定位置統計**：針對每個關鍵字在其原始位置上的出現次數進行統計，藉此觀察其是否在預定位置上與理論預期（即每個 cell 的預期值）相符。 2. **全分布統計**：針對每個關鍵字在所有 10 個位置上的數據分別計算誤差（觀察值減去預期值），然後依據各位置計算出最大、最小、平均及標準差等統計參數。由於直接將各位置的誤差彙總後會因正負抵消使平均值接近 0，我們採取了分位置計算的方法，並最終從所有位置中選取最極端的誤差指標（例如最大絕對偏差）作為該關鍵字的代表值。 為了進一步驗證數據的隨機性，我們引入了卡方檢定。卡方檢定的基本思想是將觀察到的頻數與理論預期頻數進行比較。具體來說，對於每個關鍵字在各個位置上，我們先計算出每個 cell 的預期出現次數（理論上，每個 cell 的預期值為 section_size 除以關鍵字總數）。然後，我們將實際觀察到的數據與該預期值進行比較，並計算出每個 cell 的偏差程度。這些偏差經過標準化處理後累加起來，就可以得到一個卡方統計量，該統計量反映了觀察數據與理論分布之間的總體偏差大小。換句話說，若隨機數生成與洗牌過程完全符合均勻分布的假設，則卡方統計量應當落在合理範圍內；若存在系統性偏差，則該統計量會顯著偏離理論值。這種方法可以讓我們在統計上驗證兩種隨機數生成方法是否達到理想狀態，或者是否因某些因素導致數據分布出現異常。分析工具的啟動命令如下: ```bash python scripts/shuffle/main.py --file <filename>.log ``` 擷取第一次實驗的結果，Xorshift 的結果如下: ![xorshift_error_series](https://hackmd.io/_uploads/Hye3dGIikl.png) ![xorshift_error_overall](https://hackmd.io/_uploads/rk7huGLskx.png) `getrandom` 結果如下: ![getrandom_series](https://hackmd.io/_uploads/B1Pp_G8syg.png) ![getrandom_overall](https://hackmd.io/_uploads/HJtTOMIi1e.png) 卡方統計結果如下: | String | Chi² (Xorshift) | p-value (Xorshift) | Chi² (getrandom) | p-value (getrandom) | | --------- | --------------- | ------------------ | ---------------- |:-------------------:| | uxestph | 369.21 | 0.8550 | 326.68 | 0.9966 | | fbkjruh | 394.86 | ==0.5491== | 355.96 | 0.9404 | | hjdyqnksp | 307.39 | 0.9998 | 397.77 | ==0.5080== | | nusalxs | 316.50 | 0.9991 | 299.60 | 0.9999 | | lhgql | 327.05 | 0.9965 | 338.82 | 0.9869 | | jkykzvz | 397.79 | ==0.5077== | 363.88 | 0.8958 | | nodkakeh | 371.10 | 0.8384 | 383.28 | 0.7055 | | vnffsisqc | 330.59 | 0.9946 | 357.43 | 0.9335 | | zvnaojc | 390.45 | 0.6108 | 359.81 | 0.9210 | | qmceo | 353.86 | 0.9493 | 350.44 | 0.9617 | 其中，Chi² 是卡方統計量，衡量觀察到的頻數分布與理論預期分布（均勻分布）之間的偏差。若數值越大，表示實際數據與預期數據之間的差距越大，意味著該位置或該方法產生的分布偏離理論上的均勻性越明顯；反之，數值較小則表示偏差較小，分布較接近均勻分布。而 `p-value` 則能反映在虛無假設下（假設數據符合均勻分布）的情況下，觀察到當前或更極端結果的機率。`p-value` 越接近 1，表示數據與均勻分布越吻合，也就是隨機性越高。 此處的虛無假設是均勻分布，而大部分的 `p-value` 都較靠近 1，故表示無法拒絕虛無假設。 **數據討論** 1. 對於標準差雖然都大約是 1 %，但 Xorshift 更小(集中)。 2. 以 `p-value` 比較，`getrandom` 表現更佳，且 `getrandom` 出現數值較低 (~ 0.5) 的可能性較小。 3. 以理論值 (10, 000) 為基準，兩者最大誤差都在 4 % 左右，但 Xorshift 的最大誤差更低些。 從上述的分析中並不能明確的看出哪一種更為隨機，但從 `p-value` 可知它們都更偏向均勻的隨機分佈，且偏離理想值最糟糕情況僅約有 4 %。 #### 香農熵比較 在 lab0-c 中，隨機字串是由小寫英文組成的，並未使用到全部的 8 bits，因此其上限的香農熵值為: $$ \log_2(26) \approx 4.70 (\text{bits}) \approx 58.75 \% $$ 其上限百分比則為 $\frac{4.7}{8} \approx 58.76 \%$。但實際透過 `it RAND 10` 觀察後，熵的平均居然只有 30 % 左右，與理論值相差甚遠，這中間發生了什麼? 香農熵定義為: $$ H(p)= - \sum^m_{i=1}p_i \log_2 p_i \tag{1} $$ 其中 $p_i$ 是概率。當我們採用最大概似估計 (MLE) 時，當第 $i$ 個事件出現 $n$ 次，而事件總和數為 $N$，概率的估計值為: $$ \hat p_i = \frac{n_i}{N} \tag{2} $$ 將 $(1)$ 帶入 $(2)$ 得香農熵的估計值為: $$ \hat H_{MLE} = - \sum^m_{i=1} \hat p_i \log_2{\hat p_i} = - \sum^m_{i=1} \frac{n_i}{N} \log_2{\frac{n_i}{N}} $$ 但由於 ++有限樣本的影響++，$\hat H_{MLE}$ 的期望值 $E [\hat H_{MLE}]$ 會和真實的 $H$ 有偏差，偏差值可從以下過程推導。 首先定義 $f(\hat p_i) = -\hat p_i \log_2{\hat p_i}$ 並進行泰勒展開式如下: $$ f(\hat{p}_i) \;\approx\; f(p_i) \;+\; f'(p_i)\,\bigl(\hat{p}_i - p_i\bigr) \;+\; \frac{1}{2}\,f''(p_i)\,\bigl(\hat{p}_i - p_i\bigr)^{2} $$ 其中，導數結果如下: $$ f'(x) \;=\; -\,\frac{1}{\ln 2}\,\bigl(\ln x + 1\bigr), \quad f''(x) \;=\; -\,\frac{1}{x\,\ln 2} $$ 當對 $f(\hat{p}_i)$ 取期望值 $E[f(\hat{p}_i)]$ 時，由於線性(一次項)的期望值是 0，故直接省略: $$ E[f(\hat{p}_i)] \;\approx\; f(p_i) \;+\; \frac{1}{2}\,f''(p_i)\,E[\bigl(\hat{p}_i - p_i\bigr)^{2}] \ \tag{3} $$ 又 $$ \text{Var}(\hat{p}_i) = E[\bigl(\hat{p}_i - p_i\bigr)^{2}] = \frac{p_i(1-p_i)}{N} $$ 所以 $(3)$ 可改寫為: $$ E\!\bigl[f(\hat{p}_i)\bigr] \;\approx\; -\,p_i\,\log_{2} p_i \;+\; \frac{1}{2}\,\biggl(-\,\frac{1}{p_i\,\ln 2}\biggr)\, \frac{p_i\,(1 - p_i)}{N} $$ 簡化後為: $$ E\!\bigl[f(\hat{p}_i)\bigr] \;\approx\; -\,p_i\,\log_{2} p_i \;-\; \frac{1 - p_i}{2\,N\,\ln 2} \tag{4} $$ 將 $(4)$ 的結果帶入 $E[\hat H_{MLE}]$: $$ E[\hat H_{MLE}] \;=\; \sum_{i=1}^{m} E\!\bigl[f(\hat{p}_i)\bigr] \;\approx\; -\,\sum_{i=1}^{m} p_i\,\log_{2} p_i \;-\; \frac{1}{2\,N\,\ln 2} \;\sum_{i=1}^{m} \bigl(1 - p_i\bigr) $$ 其中 $$ \sum_{i=1}^{m} \bigl(1 - p_i\bigr) \;=\; m - 1 $$ 所以，化簡可得下式: $$ E[\hat{H}] \;\approx\; H \;-\; \frac{m - 1}{2\,N\,\ln 2} $$ 我們共有 26 種事件(字元集)，故 $m = 26$，而 $N$ 代表一個字串的樣本數。lab0-c 預設情況下，ㄧ個隨機字串的長度 ($N$) 介於 5 ~ 10 之間，所以經過有限樣本偏差平均的香農熵 $E[\hat{H}]$ 為: $$ \begin{align} E[\hat{H}] &= 4.70 - \sum^{10}_{N = 5} \frac{26 - 1}{2N \ln 2} \\ &\approx 4.70 - \frac{3.61 + 3.01 + 2.58 + 2.26 + 2.00 + 1.81}{6} \\ &= 2.16 (\text{bits}) \end{align} $$ 換算下來約 27 %，這就與我們的實驗結果相近許多了! 另外，如果我們修改 `MIN_RANDSTR_LEN` 為 9，`MAX_RANDSTR_LEN` 保持為 10，使用預設的 `getrandom` 搭配以下命令: > commit: [67e2fdb](https://github.com/Dennis40816/lab0-c/commit/67e2fdbed44d86e09b4acfffc9992b09ef652ddb) ```cmd ## shannon_entropy.cmd # Test PRNG by shannon entropy option entropy 1 option prng 0 option echo 0 log shannon_entropy_getrandom.log source traces/random_once.cmd 10000 ## random_once.cmd new ih RAND 30 free ``` 運行後統計所有 entropy 資訊: ```bash python scripts/shannon_entropy/main.py --file shannon_entropy_getrandom.log Number of samples: 300000 Average Entropy: 34.62% Minimum Entropy: 15.62% Maximum Entropy: 37.50% Standard Deviation: 2.73% ``` 可以發現平均的熵為 34.62 %，和理論值 $N$ 為 9 ~ 10 的平均 2.795 bits，換算成百分比為 34.9 %，非常接近。但是 5 ~ 6、6 ~ 7、7 ~ 8、8 ~ 9，都是實驗出來的值比理論值更高。因此 5 ~ 10 的字串長度才會高於理想的 27 %。 工程學上常將 5 % 誤差作為成本與精度間的考量，那隨機字串的長度要設定成多少才能符合 5 % 這個區間 ($\ge 53.76 \%$) 呢? 實際計算後，我們可知當 $N \ge 77$ 時，能剛好在小寫英文隨機字串的情境達到 5% 的下界。於是我們將字串長度限定在 76 ~ 77 之間，實際測試結果是: ``` Number of samples: 300000 Average Entropy: 53.69% Minimum Entropy: 48.44% Maximum Entropy: 56.25% Standard Deviation: 1.03% ``` 符合探討的結果，也證明 `getrandom` 這個 CSPRNG 產生的亂數接近香農熵的上界，進一步表示其亂度是足夠的。同個測試中，Xorshift 的表現非常類似: ``` Number of samples: 300000 Average Entropy: 53.69% Minimum Entropy: 48.44% Maximum Entropy: 56.25% Standard Deviation: 1.02% ``` 因此得出結論，==在當前數量級，使用 Xorshift 和 `getrandom` 並無明顯差異==。 註: 為確認是否 `.cmd` 設定錯，使用到同個 PRNG，有特別開啟 debugger，確認不同 `prng` 確實呼叫了不同的 PRNG。 ## 〈 Dude, is my code constant time? 〉之 dudect 實驗與探討 >實驗可以參考以下 commit: > [aa2a489](https://github.com/Dennis40816/lab0-c/commit/aa2a489a9f56c49c975b61248598d7b4f5f7587a) ~ [dc73dec](https://github.com/Dennis40816/lab0-c/commit/dc73dec83ed349a5ce34bab645d4c33d9fd5f6b4) `queue.c` 等檔案有被修改，皆為測試用。 > commit: []() 修正先前修改處，保留論文中的分析方法，但恢復 `queue.c` 等檔案為實驗前的實作。同時，恢復優化等級為 `O1` ### Paper 1. 量測執行時間: - 將輸入分為兩個類別，固定(定值)和隨機，每次輸入前隨機決定要選用哪種輸入類別，並進行多次量測。 - 使用 CPU cycle register (e.g., TSC register) 來計算所耗費的週期數。 2. 後處理: - 由於ㄧ般未後處理的執行時間通常會比實際執行時間長 (positively skewed towards larger execution times)，這是由於有作業系統中斷等干擾。因此會定義一個閾值，超過閾值的數據將被丟棄。 - 應用如 centered product 的高階統計方法，揭露可能存在的統計相依性。 3. 統計檢定: - 利用引入統計檢定，當虛無假設 (null hypothsis) 為兩種類別的執行時間分布是均勻的，藉由統計檢定可知道是否能拒絕此虛無假設。 - 常用的是 Welch's t-test。 後面提到用 CDF 可以看出不同 class 的執行分布是否一致，如果不一致，就不是 constant time。 ### Welch's t-test V.S. Student's t-test 這兩者都是用於驗證兩組數據的平均值++是否存在顯著差異++。 Student's t-test: 假設兩組資料的母體變異數 (variances) 相同。 $$ t = \frac{\bar X_1 - \bar X_2}{s_p \sqrt{\frac{1}{n_1} + \frac{1}{n_2}}} $$ 其中 $$ s_p = \sqrt{\frac{(n_1 - 1) {s_1}^2 + (n_2 - 1) {s_2}^2}{n_1 + n_2 - 2}} $$ 而 Welch's t-test 則不假設兩者相同: $$ t = \frac{\bar{X}_1 - \bar{X}_2}{\sqrt{\frac{s_1^2}{n_1} + \frac{s_2^2}{n_2}}} $$ 前者就像預設了兩隊的球員的平均水平差不多 (使用了合併標準差 $s_p$)，但對於後者假設他們不同因此沒有合併，而大多數據都的分布都是不同的，因此後者的假設更為相符。當 $t$ 值越大，平均相異性越高。 ### What is simulation mode? `simulation` 的功用是指定特定功能進行常數時間的檢查，在 `queue_insert` 和 `queue_remove` 中使用。以 `queue_insert` 為例，會以傳入的位置決定是執行 `is_insert_tail_const()` 還是 `is_insert_head_const()`。但藉由搜尋我們並未找到這些函式。 原因是他們使用預處理，要展開後才能得到的函式宣告。在 `fixture.h` 中，展開預處理器可以得到以下結果: ```c _Bool is_insert_head_const(void); _Bool is_insert_tail_const(void); _Bool is_remove_head_const(void); _Bool is_remove_tail_const(void); ``` 另外在 `fixture.c` 可以找到他們的實作: ```c #define DUT_FUNC_IMPL(op) \ bool is_##op##_const(void) \ { \ return test_const(#op, DUT(op)); \ } #define _(x) DUT_FUNC_IMPL(x) DUT_FUNCS #undef _ ``` 所以所有 `is_xxx_const` 最終都會呼叫到 `test_const`。 現在的 VSCode 巨集擴展可以直接看到 `DUT_FUNCS` 會在 `_(x)` 巨集中進一步擴展。如果想透過 gcc 進一步觀察，可以參考 [vax-r homework1](https://hackmd.io/@vax-r/linux2024-homework1)。 ### Code tracing 讓我們先用幾句話總結作者在幹嘛，這樣比較好看懂下面的分析: 1. 透過大量測量，收集在不同輸入下的執行時間數據。 2. 使用多個裁剪門檻（同一組數據產生多個 t-test 統計上下文，`ttest_ctxs`）搭配 Welch’s t-test，分別檢查原始數據與不同裁剪後的數據是否存在顯著差異。理論上會有 `DUDECT_NUMBER_PERCENTILES + 2` 個 `ttest_ctxs`，多出來的 2 是原始+二階共兩個上下文。 3. `ttest_ctxs` 透過 `t_push` 以 `execute_time` 和 `class` 為參數更新裡面的平均和 $M2$，這兩個值會影響到 $t$ 值。 4. 從所有統計上下文中計算 $t$ (一個上下文裡面的數據都是陣列，長度為 2，表示 null hypothsis 和 alternative hypothsis，也就是 class 0 和 class 1 的對應數據，用class 0 和 class 1 對應的數據去算出純量值 $t$ ) 5. 挑選出 $t$ 值最大的那一組，並將其 $t$ 值與預設的閾值比較 ( `t_threshold_moderate`，屬於經驗參數)；超過閾值，就判定程式++可能++並非 constant time，如果超過 `t_threshold_banana` 就鐵定不是 constant time。 以下是對原始程式的分析: ```c static void t_push(ttest_ctx_t *ctx, double x, uint8_t clazz) { assert(clazz == 0 || clazz == 1); ctx->n[clazz]++; /* estimate variance on the fly as per the Welford method. this gives good numerical stability, see Knuth's TAOCP vol 2 */ double delta = x - ctx->mean[clazz]; ctx->mean[clazz] = ctx->mean[clazz] + delta / ctx->n[clazz]; ctx->m2[clazz] = ctx->m2[clazz] + delta * (x - ctx->mean[clazz]); } ``` 在 `t_push` 中，使用 Welford 方法在線更新平均和變異數: $$ \mu_n = \frac{1}{n}\sum_{i=1}^{n} x_i,\quad M2_n = \sum_{i=1}^{n} (x_i - \mu_n)^2. $$ 當第 n+1 個數據 $x_{n+1}$ 到來時，我們希望能以遞增的方式更新平均值和 $M2$，而不必重新計算所有數據。 1. **更新平均值** 定義 $$ \delta = x_{n+1} - \mu_n. \tag{1} $$ 那麼新的平均值 $\mu_{n+1}$ 可以寫成 $$ \mu_{n+1} = \mu_n + \frac{\delta}{n+1}. \tag{2} $$ 2. **更新累計平方差 ($M2$)** 我們需要計算更新後的累計平方差: $$ M2_{n+1} = \sum_{i=1}^{n+1} (x_i - \mu_{n+1})^2. $$ 通過推導可以證明，這個更新可以寫為: $$ M2_{n+1} = M2_n + \delta \left( x_{n+1} - \mu_{n+1} \right). $$ 注意到： $$ x_{n+1} - \mu_{n+1} = x_{n+1} - \left( \mu_n + \frac{\delta}{n+1} \right) = \delta - \frac{\delta}{n+1} = \frac{n}{n+1}\delta. $$ 代入上式得: $$ M2_{n+1} = M2_n + \delta \cdot \frac{n}{n+1}\delta = M2_n + \frac{n}{n+1}\delta^2. \tag{3} $$ 作者使用 $(1)、(2)、(3)$ 對++平均++和++累積平方差++進行及時更新。 以下是重頭戲，有關 percentile 和統計數據的處理: ```c static int64_t percentile(int64_t *a_sorted, double which, size_t size) { size_t array_position = (size_t)((double)size * (double)which); assert(array_position < size); return a_sorted[array_position]; } /* set different thresholds for cropping measurements. the exponential tendency is meant to approximately match the measurements distribution, but there's not more science than that. */ static void prepare_percentiles(dudect_ctx_t *ctx) { qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp); for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) { ctx->percentiles[i] = percentile( ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)), ctx->config->number_measurements); } } 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]); } } } ``` `percentile` 有變數 `which`，介於 0.0 到 1.0 間，即要選第幾 % 的元素返回，例如 0.95 就是第 95% 的那個元素。 `prepare_percentiles` 只在第一次量測結束後對 `exec_times` 進行排序 (只有在 `first_time` 為真時呼叫 )。隨後透過公式 $f$ 決定閾值: $$ f = 1 - 0.5^{10 \times \frac{i+1}{N}} $$ 對於 `update_statistics` 則需要注意幾件事情: 1. 從第 10 個測量值開始，而不是第 1 個，避免起始的波動影響判斷結果。 2. second order 不進行剪裁，而使用更高階的統計方法。 3. first order 會使用 `ctx->percentiles[crop_index]` 作為閾值進行剪裁，若超過閾值則 ==不進入 t_push==。 4. 全部的測試都會被 `t_push` 並納入 `ctx->ttest_ctxs[0]` 的統計範圍中，所以`ctx->ttest_ctxs[0]` 相當於++原始數據的統計結果++。 **小結** 作者首先利用第一次量測得到的 execution time 分布來決定一組固定的百分位門檻值，根據所有執行時間數據進行排序，然後依據公式 $f$ 計算出不同 percentile index (0 ~ 99) 對應的門檻值。這些門檻值代表「保留」的數據比例，所以用 1 減去該值就是「被剪裁」的數據百分比。越高的 percentile index 表示保留的數據比例越接近 100%，幾乎所有數據都會被保留。 舉個例子，假設第一次量測共有 10000 個元素，只在第一次量測中會呼叫 `prepare_percentiles`。若我們要知道第 11%（也就是當 i+1 = 11）對應的剪裁閾值，依照公式可算得 $$ \text{percent} = 1 - 0.5^{10 \times \frac{11}{100}} \approx 1 - 0.4665 = 0.5335 \quad (53.35\%), $$ 然後從排序後的數據中取第 5335 個元素（10000 × 0.5335 ≈ 5335），假設該值為 3.5 秒，那麼第 11% 的剪裁閾值就是 3.5 秒，即若 `difference` 高於 3.5 秒就不會進入 `t_push`。以第一次量測結果而言，有 46.65% 的數據不會進入 `t_push`。 下圖展示以第一次量測結果為輸入 (假設 percentile 已經由第一次結果得出)，隨著 percentile index 增加，沒有進到 `t_push` 而被剪裁掉的數據百分比的變化情形。 ![crop_perctiles](https://hackmd.io/_uploads/HyQhloS3yx.png) 隨著 percentile index 越高，被剪裁的數據百分比會越低，因為保留的數據比例接近 100%，幾乎沒有數據被忽略，大部分都進入 `t_push`。而進入 `t_push` 意味著更新了該上下文的對應的 class 的數據，包含平均和 $M2$。 需要特別注意，++這些裁剪閾值是根據第一次量測的分布確定的++，之後所有後續的測試都會使用這組固定的閾值。即使隨後的測量數據分布可能有所變化，裁剪操作仍然依照第一次量測時的基準來進行。 ### lab0-c 和原作差別在哪? 分析那麼多，lab0-c 和原本論文到底差別在哪? 1. lab0-c 僅維護一組名為 `t` 的 `t_context_t`，照理來說要有 `DUDECT_NUMBER_PERCENTILES + 2` 組。 2. 沒有先行排序，也沒有進行數據裁減，全部都被送進 `t_push` 了。這也表示極端值++沒有被裁剪++，畢竟沒有實現 `percentile` 和 `prepare_percentiles` 等函式 。 3. 測量數值定義為 `N_MEASURES`，數值為 150。 4. 真正實施 `measure` 時，不是從 `0` 開始，而是從 `DROP_SIZE` 開始，而且量測也只有到 `N_MEASURES - DROP_SIZE`。所以量測結果 ( `exec_time` ) 頭尾合計有 40 個 `0`。但根據 (2)，這些 `0` 都會進入 `update_statistics`，這明顯會造成影響。 5. 未拋棄第一次資料。 接著，觀察他人的實作 (見參考) ，大部分人的作法是在 `update_statistics` 前添加 `prepare_percentiles`，但我認為不正確: 原作者只在++首次進入++時進行 `prepare_percentiles`，這也是為什麼它不用管 `classes` 和 `exec_times` 對應關係的原因，因為這筆數據++稍後會被拋棄++，不會進入 `t_push`。但如果每次都執行 `prepare_percentiles`，則 `classes` 順序也要跟 `exec_times` 一起被排序，否則 `classes` 跟對應到的 `exec_times` 將與原始對應關係不一致，相當於將 class 0 和 class 1 混在一起，所以兩邊的分布當然會更靠近。這樣++喪失區分兩個 class 的意義++。 若考量 `classes` 和 `exec_times` 的對應關係，則++該種作法依然不會通過++。 所以在引入了原論文中的作法後 (參考 hungyuhang 同學) 最後受好奇驅使，實作分析數據相關的工具。 ### 分析數據 :::info - 以下的執行時間單位為 cpu cycles - 優化等級為 `O0` ::: 首先，按照論文的思路，決定繪製出 CDF 圖。在測試中將量測所得的執行時間和對應的 class 記錄在日誌中。不過在這之前，讀者應該了解一件重要的事情，就是 ++class 0 和 class 1 的差別++。 以 `insert_head` 為例，其實兩個 class 使用的隨機字串的長度都固定為 8 bytes (包含 `\0`)，且是共用的集合。他們相異的點在 `prepare_input` 可以查明。 `inputs` 以兩個 bytes 的長度當作 chunk，每個 chunk 儲存的是預先對 list 操作的數量。對於 class 0， chunk 都設定為 0，而 class 1 的 chunk 則是 `randombytes`。 這在 `insert_head` 代表著，要量測單個插入所消耗的 CPU cycle 前，對於 class 0 會先在 list 中插入 0 個元素(不做事情)，而 class 1 會先插入 `chunk % 10000 `，也就是 0 ~ 9999 個元素在 list 中。 回到 CDF 圖，透過 python 進行分析: ```bash python scripts/deduct/deduct_analyzer.py ``` 運行後得到 CDF、長條圖和 KDE 圖。下方兩張圖分別是 `insert_head` 和 `remove_head` 的 CDF 對比。 ![cdf_insert_head](https://hackmd.io/_uploads/rJJxZjSh1e.png) ![cdf_remove_head](https://hackmd.io/_uploads/B1XBWsrnkl.png) 可以觀察到 `insert` 比 `remove` 的分布差異性更高，$t$ 值也更高，因此 `remove` 也比較容易通過 constant time 檢查。 而當我 ==移除== `q_insert_head` 中用到的 `strdup`， 只保留 `element_t` 的 `malloc` 和 `list_add` 時，神奇的事情發生了! ![cdf_insert_head](https://hackmd.io/_uploads/Hk8PboHh1x.png) 兩者的分佈居然趨向一致，但照常理，class 0 和 class 1 理論上都進行了一樣長度的 `strdup`，在 lab0-c 中即 `test_strdup`，該函式由 `strlen`、 `malloc` 和 `memcpy` 組成。而這三者對於定長度的執行時間應該是固定的?但事實證明並非如此。 因此，現在討論的目標從怎麼修正常數時間的測試系統變成++為何目前的實作不是常數時間++? 註: 在本實驗中使用了 `-O0` 方便除錯，並提醒各位要記得 `make clean`，否則有時程式會出現 bug。 `insert_head` 中，每個部分表面看起來對於++固定長度++的字串傳入時，具有常數時間的執行時間 ( `strdup`、 `malloc`、 `list_add` ) 。但為什麼 list 裡面的元素數量改變，`strdup` 會有這麼大的差據? 後來我又將 `strdup` 換成 `malloc`，具有同樣的問題，所以是 `malloc` 造成的問題。 推測在測試過程中，`malloc` 可能出現了++記憶體碎片化++ **(待確認)**。 `malloc` 很少次時，該問題不明顯，因此 `malloc` 可被視為 constant time (對應到 class 0) 。但當有許多小碎片時，可能會讓搜尋可用空間時的時間變長？ 為驗證我的猜測，設計了以下 `malloc` 實驗 (實作 `alloc_test` 命令) : 仿照 `insert_head`，先量測只 `malloc` 一組固定長度 (設定為 32 bytes) 的記憶體空間，並使用 `cpucycles()` 的方法測出消耗的 CPU 週期，記為 `SingleAlloc1Cycles`。測量完後釋放，接著進行 `r` 次的 `malloc`，`r` 是透過 `rand() % 10000` 得出的隨機次數，模擬已經有記憶體被分配的記憶體池，接著執行一次 `malloc`，並量測該值記為 `SingleAlloc2Cycles`。 從下圖可以看出分布並不一樣: ```bash ./qtest alloc_test quit # plot python scripts/deduct/deduct_memory.py ``` ![alloc_test_random_dual_kde](https://hackmd.io/_uploads/r1xFZoH3yx.png) ```bash SingleAlloc1Cycles Statistics: count 1000.000000 mean 22.097000 std 9.729144 min 17.000000 25% 20.000000 50% 20.000000 75% 20.000000 max 120.000000 Name: SingleAlloc1Cycles, dtype: float64 SingleAlloc2Cycles Statistics: count 1000.000000 mean 37.098000 std 12.552688 min 23.000000 25% 32.000000 50% 34.000000 75% 37.000000 max 332.000000 Name: SingleAlloc2Cycles, dtype: float64 Skewness for SingleAlloc1Cycles: 4.6163 Skewness for SingleAlloc2Cycles: 13.9660 SingleAlloc1Cycles is positively skewed. SingleAlloc2Cycles is positively skewed. ``` 藍色是一開始就 `malloc`，模擬 class 0，橘色則是模擬先隨機多次 `malloc` 後，再多一次 `malloc` 並量測該次時間，模擬 class 1 的 `malloc` 場景。透過統計數據可知，class 0 的 `malloc` 會比 class 1 的平均耗費時間更少 (22 V.S. 37)，且更集中 (std 9.7 V.S. 12.5)，以及更均勻 (skewness 較小)。這與以下 `q_insert_head` 的測試結果的 KDE 趨勢符合: - 原始實作 ```c char *cp = strdup(s); if (!cp) return false; ``` ![kde_insert_head](https://hackmd.io/_uploads/rkrWQsH3kg.png) ➜ 極高機率無法通過 constant time - 模擬 constant time malloc on stack ```c // the input string length in constant time test // is fixed to 8 (including '\0') char cp[8]; memcpy(cp, s, 8); // if (!cp) // return false; ``` ![kde_insert_head](https://hackmd.io/_uploads/Hk4QmiBnJx.png) ➜ 每次都通過 lab0-c constant time 測試 (大約在 6 or 7 次嘗試時會通過)，但是論文中說只要有沒通過的，就算沒通過，lab0-c 比較寬松。 - 完全刪除字串相關操作 (剩下 `malloc element_t` 和 `list_add` ) ![kde_insert_head](https://hackmd.io/_uploads/HyIIXjHnkx.png) 這三張圖的結果可以看出 `malloc` 的多寡對 `q_insert_head` 會影響其執行時間分布，進而使 class 0 和 class 1 的分布差距過大，因此++不該被忽略++。 ### 總結 :::info :warning: 後發現當使用 `O1` 則 `alloc_test` 無法重複模擬結果，隨機預先 `malloc` 模擬的 class 1 和 class 0 的分布是一致的。是還有其他因素 (e.g., cache miss ...) 影響了 deduct 測試結果但還沒被找出，還是僅因測試過於簡單被優化了? 目前能確認的是與 `strdup` 有關 **(待確認)** ::: 到此，我認為依照作者的觀點，不應該在每一個 `doit` 都執行 `prepare_percentiles`，因為該函式預設只對執行時間排序，導致 class 混在一起。依照作者說明，應該討論原始數據、一階 (cropping)、二階的 $t$ 值，都應該小於訂定的 threshold，才能說++可能是時間常數++。因此當前的實作或許本來就不會通過 deduct 的測試，因為++記憶體配置上並非時間常數++。所以如果原始數據沒有通過測試，則應該先思考並驗證目前實作是否真正符合常數的運行時間。 ### Reference - [SuNsHiNe-75 homework1 (jujuegg 協作)](https://hackmd.io/@SuNsHiNe-75/r1V9YJI26) - [vax-r homework1](https://hackmd.io/@vax-r/linux2024-homework1) - [25077667 homework1](https://hackmd.io/@25077667/SkpLspWnT) - [jychen0611 homework1](https://hackmd.io/@jychen0611/linux2024-homework1) - [hungyuhang homework1](https://hackmd.io/@hungyuhang/linux2024-homework1) ## 研讀 select 和 console.c 中的 RIO ### What is select? 在 lab0-c 中，只有兩處地方用到 `select.h` 相關的功能。 第一處在 `console.c` 中，第二處在 `web.c`，只有後者使用到了 `select` 系統呼叫。 在 `web_eventmux` 中，使用了同一個 `fd_set` 去監聽 `STDIN_FILENO` 和 `server_fd`，並僅在 `server_fd` 觸發 `select` 時回覆 HTTP 200 的成功訊息。進一步追蹤，可知道 `server_fd` 是當初在 bind port 時的 `listen_fd`。故當有設備來連結伺服器時，就會喚醒 `web_eventmux` 中阻塞的 `select`。 select 是 POSIX 的一部分，也是 Linux 的系統調用之一，可用於監測多個檔案描述符的狀態變化。當受監測的檔案集有一者受監測的狀態變更時，select 會被觸發並返回。select 可以設置 timeout，也可以設定為阻塞模式，lab0-c 採用後者。select 可以監測檔案描述符可讀、可寫和異常狀態，在 `web_eventmux` 主要用於監聽 `server_fd` 是否可讀。 實際查看 `linux/fs/select.c`，select system call 執行函式 [kern_select](https://github.com/torvalds/linux/blob/2a520073e74fbb956b5564818fc5529dcc7e9f0e/fs/select.c#L722) : ```c static int kern_select(int n, fd_set __user *inp, fd_set __user *outp, fd_set __user *exp, struct __kernel_old_timeval __user *tvp) { struct timespec64 end_time, *to = NULL; struct __kernel_old_timeval tv; int ret; if (tvp) { if (copy_from_user(&tv, tvp, sizeof(tv))) return -EFAULT; to = &end_time; if (poll_select_set_timeout(to, tv.tv_sec + (tv.tv_usec / USEC_PER_SEC), (tv.tv_usec % USEC_PER_SEC) * NSEC_PER_USEC)) return -EINVAL; } ret = core_sys_select(n, inp, outp, exp, to); return poll_select_finish(&end_time, tvp, PT_TIMEVAL, ret); } ``` `web_eventmux` 中未傳入有效的 `struct timeval` 指標，故直接進入 `core_sys_select`。該函式通過內核空間中的位元圖來模擬和管理多個檔案描述符的狀態，並依靠 `do_select` 進行事件等待與檢查 (該進程被排程器丟到等待隊列中)，最終將結果反映回用戶空間。具體阻塞處是 `poll_schedule_timeout` 中的 `schedule_hrtimeout_range(expires, ...)`。 ### What is RIO? RIO (Robust IO) 是在 IO 系統調用上 (e.g., read, write) 又多一層的封裝。該種 IO 實作專注於以下 IO 痛點: 1. 容易受到++中斷干擾++: 只要受到中斷或其他非 IO 錯誤的干擾，`read` 或 `write` 可能在未完成指定進度前就返回，儘管可能跟目前正操作的檔案無關，但由於系統呼叫已中斷，我們獲得的結果就是不完整的。所以往往要檢查返回值，確保與預期行為一致。但若使用 RIO 的 unbuffered API (e.g.,`readn` ) 則不用擔心此事。 2. 提供 buffered function: 為避免非必要多次呼叫系統呼叫，RIO 封裝內含一塊 buffer，配合 buffered function (e.g., `readline` in `console.c` )，他會先嘗試一次性 IO 該 buffer 能承載的最大長度 (8190 bytes，保留 `\n\0` 位置)，並嘗試尋找 `\n`， 在下一次被呼叫後根據 `count` 選擇要從 buffer 操作( `count > 0` ) 還是執行新的 read。如此，可以有最低的系統呼叫次數。 3. 執行緒安全: 傳統的 buffered 函式都是直接讀到類似 `linebuf` 靜態變數中，如果有不同的執行緒對相同 fd 呼叫相同的 buffered 函式，`linebuf` 資料就會被破壞。但 RIO 因為有內部 buffer，所以不論先後順序，都會按照原檔案順序讀進 buffer (執行緒共享文件偏移量)，因此是相同的 buffered function 呼叫變成執行緒安全的。但還是要注意讀取是二進制還是文字形式，因為兩者共享偏移量。 透過以上三點增強，RIO 封裝能夠降低我們寫程式對 IO 需要考量的因素，進而能達到簡化程式的效果。另外，lab0-c 中藉單向簡易鏈表( `prev` 指標) 實作 stack，讓檔案描述符能以 stack 方式操作。 ## By the way ### 靜態內嵌函式 (Static Inline Function) `static inline` 在 `lab0-c/list.h` 中被多次使用，僅僅放在++標頭檔++中的時候才可確定生效 (對於 GCC 而言)。之所以放在標頭檔是為了讓內嵌函式的實作出現在編譯單元 (translation unit) 中。這樣才能將實作展開到呼叫處。如果實作放在其他源文件中，則不能確保每個編譯單元中，實作都存在。對於實作不存在的編譯單元將導致無法內嵌。 :::danger 注意術語！ > inline 從內聯改成內嵌；header file 從頭文件改成標頭檔。 ::: :::danger 文章通常有標題，不要書寫「這篇文章」，這無助於溝通。 >了解。 ::: 為甚麼非 `static` 不可呢?根據[〈我有所不知的 static inline function〉](https://medium.com/@hauyang/%E6%88%91%E6%9C%89%E6%89%80%E4%B8%8D%E7%9F%A5%E7%9A%84-static-inline-b363892b7450)知道要去 [GNU Manual 中 (GCC version 13.3.0)](https://gcc.gnu.org/onlinedocs/gcc-13.3.0/gcc/Inline.html) 尋找答案，在 6.45 An Inline Function is As Fast As a Macro 中有以下敘述: >When an inline function is not static, then the compiler must assume that there may be calls from other source files; since a global symbol can be defined only once in any program, the function must not be defined in the other source files, so the calls therein cannot be integrated. **Therefore, a non-static inline function is always compiled on its own in the usual fashion.** 如果沒有 `static` 又想展開內嵌函式，則可能遇到以下情況: 該函式可見性並不僅侷限於當前的編譯單元，因此存在被其他編譯單元調用的可能。由於非靜態函式符號在全域僅能存在唯一定義(實作)，此時若還是展開內嵌，則其他編譯單元調用該內嵌函式處也將出現另一個相同的實作。這兩個實作致使該全域符號有多處被定義，最終導致++連結階段錯誤 (link error)++。 為防止這種情況，GCC 會將沒有 `static` 關鍵字的內嵌函式 100% 當作正常函式調用。 ## Reference :::danger 不要說「可能」，當你參考到，就列出，否則不要裝忙。 > 好的。 ::: **作業** - [2024 homework1 開發紀錄](https://hackmd.io/@sysprog/linux2024-homework1) - [yeh-sudo](https://hackmd.io/@yehsudo/linux2024-homework1): 關於 sort (timsort) 的分析可以參考 - [jimmylu890303](https://hackmd.io/@jimmylu0303/linux2024-homework1): sort 分析, linux/list_sort.c - [chiangkd (2023q1)](https://hackmd.io/@chiangkd/2023spring-lab0-c): 作業完成度參照 (希望至少) - [Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh) :::danger 你現在還沒有能力評價「作業完成度高」，唯有當你充分投入並超越你要評價的作品時，你才有立場充分評價「完成度」。 >已修正措辭。 :::