2025q1 Homework1 (lab0)

contributed by <Dennis40816>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ 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

文件紀錄

避免過多的個人色彩。不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。
格式維持單純，聚焦在內容本身。

了解。

若標示 "§"，以 C11 規格書章節為準
可搜尋 (待完成)、(有疑問)、(待確認) 定位

LAB

論文

講座

Code

lab0-c/CONTRIBUTING.md (2/22)
- Linux2025q1: lab0-c 貢獻規定速記 (2/22) (有疑問)
Linux2025q1: C-String APIs Write-Up
The Linux Kernel API
How to Write a Git Commit Message (2/22)
lib/list_sort.c
lib/list_sort: optimize number of calls to comparison function

隨堂測驗

課程問答

2025-02-{18,20} 課堂問答簡記 (2/22)
- 留言回覆 rounding to even 捨入方向

演算法

延伸閱讀

工具鏈相關

編譯選項

注意用語！

好的。

LIST_POISONING : 巨集，若被定義執行 list_del 後的節點，其 prev 和 next 指向 NULL，如果意外被調用會觸發記憶體區段錯誤 (Segmentation Fault)。
SANITIZER : 開啟時，能得知 segmantation 相關錯誤觸發位置。

個人新增

Q_MERGE: 0 代表使用樹狀合併(預設)，1 代表使用線性合併。
Q_SHUFFLE_BIAS: 有定義，會採用有偏方法，未定義採用無偏 (預設)。

編譯範例:

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 設定:

"setupCommands": [
    {
        "description": "Ignore SIGALRM signal",
        "text": "handle SIGALRM ignore",
        "ignoreFailures": true
    },
    {
        "text": "backtrace",
        "ignoreFailures": true
    },
]

巨集在前處理期間就被展開，故 gdb 無法像函式一樣使用它們。這對於常用的巨集 (e.g., container_of ) 稍有不便。我們當然能夠在 gdb 裡面暴力打出所有已知資訊，透過類似:

(gdb) p (struct my_container *)((char *)my_member_ptr - offsetof(struct my_container, member))

獲得我們要的 debug 資訊，但我們也能透過 python 的 gdb package 去實作實用的函式，進而降低使用時的複雜度。如果你也想使用客製化且能使用 VSCode 除錯介面的 gdb，請參考〈Linux2025q1: Toolchain Write-Up〉和 commit 8fdbc1a。裡面介紹了如何實作 container_of 等功能，讓你 debug 更輕鬆。

Breakpoint

對中斷點按下右鍵將出現 Edit Condition 的選項，可供輸入判斷條件。假設你希望 node->value 是 "7" 的時候該中斷點才停下，可將中斷點的表達式改成:

(int) strcmp(node->value, "7") == 0

如果沒強制轉型會遇到錯誤:

'strcmp' has unknown return type; cast the call to its declared return type

實作 queue.[ch]

瀏覽 queue.h，將須實作的功能及討論放在本節中。

實作前，列舉概觀注意點及討論點:

環狀雙向鏈結串列使佇列在進行頭尾操作時，時間複雜度為 O(1)，為符合測試要求此種實作是必要的。
思考佇列鏈是否也需要透過環狀雙向鏈結串列實作?為什麼?
A: qtest 提供 prev 和 next 命令在佇列間進行切換，因此為提升 當佇列實例數量很多時， prev 切換時的效能，也應以環狀雙向鏈結串列實作。但這部分是 qtest.c 實作的範圍。
NULL queue 和 empty queue 差異是?
A: Empty queue 具有 head，NULL queue 連 head 都沒有，見下方示意圖。
為符合 linux 鏈結串列的 API 風格，所有有效的鏈結串列都應具有型別為struct list_head 的實例 head，當鏈結串列為空時，head->next 指向 head 本身。
希望 queue_t 的資訊(e.g., size, id, …) 能在 O(1) 內取得，即 size 要由多個 function 共同維護? 此作法會引入額外的複雜度 (包含未來添加新函式時可能也需考量)，是否有價值? 後來查看 queue_contex_t 是用在多佇列的操作上，如 qtest.c 和 q_merge 中，因此佇列基礎功能的實作與之無關。
現有實作與 C Programming Lab 描述有何差異?
A: 差異如下:
- 佇列的尾元素不再指向 NULL，有利減少檢查。

下圖是對應的示意圖，可用於實作時對照查看:
queue_struct

queue_illustration

這張圖以橘色標示所有與 struct list_head 有關的成員或指向操作。圓點代表結構體中成員（通常是指標）的連接點，箭頭的起點必定在圓點上，因為只有指標才具有「指向」的含意。箭頭的終點表示所指向的目標。若目的地仍是圓點，則表示指向另一個成員；若指向邊框，則代表它指向的目標是結構體或是陣列實例 (e.g., struct list_head 實例、字串陣列…) 。

例如，在 queue instance 1 中，next 從圓點出發指向自身所在的邊框，表示它指向包含自身的，型別為 struct list_head 的實例。

~~圖中箭頭連接到圓點表指向特定成員；未連接到圓點上的，則指向結構體。指向型別為 list_head 的指標用橘色標示。~~

藍色底色是本次要實作的部分，紅色底色則主要由 qtest.c 使用。

q_new

commit: 0427310

不要恣意標注 v1，GitHub 會紀錄你的開發過程，你只要標注 commit hash。

了解。

interface 的翻譯是「介面」，而非「接口」，後者不文雅。
參見「資訊科技詞彙翻譯」及「詞彙對照表」。

已修正。

目的
提供建立空佇列 (不含 q_contex_t )的統一介面。

注意用語，你在中學的國文課本中，除了「創建民國」以外，還有哪篇文章出現「創建」。改用新增、建立等詞彙，尊重傳統文化。

已修正。

實作流程

請求 head 大小的記憶體空間(透過 malloc )。
檢查記憶體配置 (memory allocation) 是否成功，並在失敗時返回 NULL。
檢查成功後，使用 INIT_LIST_HEAD 將 prev 和 next 都指向自身，並返回該 head 地址。

流暢的漢語中，不需要頻繁書寫「一個」，你該回想自己在中學國文讀過的經典文學作品，哪篇會頻頻出現「一個」？

已修正。

q_free

commit: 0427310

目的
釋放佇列申請的所有元素 ( element_t ) 記憶體空間，按應釋放的順序依序為字串陣列 ( value 指向的地址)、佇列節點 ( element_t ) 以及佇列的 head。

特殊狀況描述

傳入 head 指向 NULL: 欲釋放不存在的佇列，應盡早返回，避免後續操作 (e.g., head->next ) 對 NULL 解引用。
無返回值。

實作流程

可以使用 list_for_each_entry_safe 先獲取 entry，因為涉及刪除，所以要使用 safe。
由於整條佇列都將被釋放，因此似乎不需要先移出 queue，可以直接刪除?
假設所有 entry 的成員 value 皆為非 NULL，雖然將 NULL 作為 free 的參數不會發生任何事 (C11 §7.22.3.2 - 2) :

If ptr is a null pointer, no action occurs.
根據上一條，雖不影響，~~但是否會影響效能( free() 內部的處理邏輯)需要再探討~~，觀察 test_free，在進行 NULL 的返回前，僅做是否允許配置的檢查( noallocate_mode )。
以下敘述待實驗 (待完成): 除非使用者非常頻繁在可配置和不可配置間切換，否則 CPU 分支預測錯誤造成管線清除 (pipeline flush) 的消耗近乎 0，實際情況未來用 perf 觀察。

談及 CPU 時，pipeline 譯作「管線」，而非「流水線」，後者用於工廠製造。

注意詞彙，論點都該有明確的第一手材料出處。

還在準備實驗中。(待完成)

assign 和 assignment 不該偷懶的翻譯成「賦值」，你在中學英語用過這翻譯詞嗎？
可改寫為「entry 會被變更」，關鍵的概念不是「值」的「賦予」，而是「使用」和「變更」

之前沒想到這層面，日後會改用變更或更新。

按照上述描述 (1), (2), (4) ，可得以下實作:





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 更精簡:

-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);
 }

q_insert_head

commit: e0ec110

目的

建立新的佇列元素，將給定字符串複製至其 value 的陣列中，value 陣列需自行配置記憶體，長度可透過 strlen() 取得。
將配置並賦值完的元素插入至 head 和 head->next 間。

特殊狀況描述

當透過 malloc 申請配置失敗時，要返回 false
當傳入的佇列是 NULL，返回 false

實作流程

假設使用者提供的字符串是有效的，不包含 NULL 和沒有 \0 結尾等情況。
目的 (2) 可透過 list_add 完成。
配置記憶體流程: 配置佇列元素、字元陣列 ➝ 確保兩者皆有效 ➝ 將佇列元素的 value 指向字元陣列。
配置失敗發生時，要將已經配置的記憶體釋放，避免洩漏。

根據 (3), (4) 的實作如下:

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。

延伸閱讀是書寫教材時的用語，這裡是「開發紀錄」，當然要反映你看了哪些，既然投入時間，就探討，沒必要說「延伸閱讀」。

了解。

關於第一點，在 §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) :

Preceding an expression by a parenthesized type name converts the value of the
expression to the named type. This construction is called a cast¹⁰⁴.

¹⁰⁴⁾ 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 * 某些情況上是一樣的，但一時之間沒找到在規格書的哪一章節，之後補)。

避免說「某種程度」，這裡應該是「某些情況」。用你的中學國文來書寫，不要因為看了詞不達意的簡體中文內容，就忘了漢語該如何書寫。

好的。

因此上方程式修改後如下:

-size_t csize = strlen(s) + 1UL;
-char *cp = malloc(csize);
+char *cp = strdup(s);
 if (!cp)
     return false;
-memcpy(cp, s, csize);

另外應注意在 C++ 中 void * 的隱式轉換是被禁止的，例如:

int *a = malloc(4);

上例的編譯結果是 invalid conversion from ‘void*’ to ‘int*’ [-fpermissive]，因為隱式轉換成 void * 並非類型安全的。有關更多 C 字串的 API 請參考 string(3) — Linux manual page。

避免書寫 v1 和 v2 這樣無助於溝通的話，你只要標注 commit hash

已移除。

討論

觀察 insert 過程中都牽涉到佇列元素的記憶體配置，相對刪除 (非移除) 佇列元素有 q_release_element，為何不實作 q_new_element 增加程式重複利用率? (待完成)
參考 v0103 的實作，可以進一步讓程式縮短，且佔用的函式堆疊尺寸會比較小(沒有 cp )，但程式可讀性略為下降。

q_insert_tail

commit: e0ec110

目的
與 q_insert_head 類似，僅插入位置改為尾端。

特殊狀況描述
同 q_insert_head。

實作流程
由於內容與 q_insert_head 非常類似，僅需調整與鏈結串列相關的 API 即可。

討論
未來討論方向可著重在程式重用上。 (待完成)

q_remove_head

commit: e0ec110

目的

移出佇列中第一個元素，並返回該元素的地址。
若使用者給定一有效字元指標 sp ，且 目的(1) 已完成，複製移出元素的值到 sp 中，可容納的字元長度由使用者給定 bufsize ，允許的最大字串長度為 bufsize - 1 確保最後總是 \0。

特殊狀況描述

sp 是 NULL: 不將元素的值(字串) 複製到 sp 內。
~~移出失敗: 理論上不存在此種情況。~~
head 是 NULL: 直接返回 NULL。
head 指向空佇列: 直接返回 NULL。

實作流程

僅在移出成功後，才複製字串到 sp。
可用 list_empty 檢查是否為空佇列。
複製字串可用 strncpy，該函式返回值是 sp，不需要承接。

討論
乍看 strncpy 是很好的選擇，因其具備兩點特點:

長度限制，避免誤寫入非法記憶體區域
幫忙補 \0

透過 man strncpy 可看可能的實作:

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。 (待完成)

q_remove_tail

commit: e0ec110

目的
同 q_remove_head，僅操作元素改為尾部。

特殊狀況描述
同 q_remove_head。

實作流程
由於內容與 q_remove_head 非常類似，僅需調整與鏈結串列相關的 API 即可。

討論
未來討論方向可著重在程式重用上。 (待完成)

q_size

commit: 421b720

目的
透過走訪 (tranverse) 所有元素，以統計目前的元素數量。

特殊狀況描述
當 head 為 NULL 或為空佇列 : 返回 0。

實作流程
透過 list_for_each 走訪佇列中元素的每個 list 成員，每當該成員的地址與 head 地址不一樣，就將佇列大小加上 1，直到再次遇到 head。

討論
目前方法的時間複雜度為 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)。

盲目追求

O (1)

是不智的，你該確保應用情境有其必要。

需思考在 homework1 及其後續作業中，是否有相應的應用場景。

老師在課堂中 (3/9) 提到，鏈結佇列關注的是快速動態記憶體管理，即記憶體塊間的連接關係，因此可能會牽涉到多執行緒甚至多行程對鏈結佇列的修改。實際去思考，在頻繁的修改下，維護長度的意義不大，反而可能有 race condition 等麻煩。

q_delete_mid

commit: cca7225

目的
擦除(含記憶體釋放)佇列中第

⌊ n + 1 ⌋

個元素，以 0^th 作為元素的第一個索引 (index)。注意是擦除節點，要先移出元素後才釋放。

特殊狀況描述
head 是 NULL 或空佇列 : 返回 false

實作流程
使用兩指標 tail、front 指向 head->prev、head->next後作為起點，front 朝後移動，tail 朝前移動。

當指標相遇時 (元素個數為奇數) 或 tail 剛好超過 front 一個節點時 (元素個數為偶數)，front 必然指向要刪除的節點。

討論

修改該函式(返回類型、不要釋放記憶體)，便可完成獲取中間值的功能，可能應用場景為:
- 在已排序鏈結串列中取中值。
分析「快慢指標」一文中提到，快慢指標較單一指標具備教好的時間局部性(降低 CPU 快取錯失)，那首尾指標和快慢指標是否有類似現象。按照邏輯，後者的時間局部性比前者好，那單一指標的時間局部性有可能比首尾指標好嗎?未來可用 perf 驗證這個想法。 (待完成)

q_delete_dup

commit: 25053d2

目的
比較佇列元素與兩側的字串是否重複，如果重複就擦除。

特殊狀況描述

head 是 NULL 或空佇列 : 返回 false
當下一個元素的 list 就是 head : 判斷字串是否重複，會用到下個元素的成員 value ， head 並未被包含在 element_t 實例中。故遇到下一個元素是 head，不能解引用 value (所以該判斷要被放在字串比較前) ，僅需再判斷當前元素是否需要被擦除。

實作流程

list_for_each_entry_safe 中的停止條件是當當前元素的 list 與 head 地址相同時。當目前元素字串和下個元素字串相同，則先移出當前元素，後釋放其記憶體。
需要記住當前元素是否已經是重複元素，如果是，要移動至下一個元素前要先擦除該元素。

其中 list_for_each_entry_safe 的判斷式如下:

// 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 狀態，就能得到更精簡的程式:

-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;
 }

討論

遇到以下靜態檢查錯誤: (有疑問)

queue.c:155:5: style: Label 'int' is not used. [unusedLabel]
list_for_each_entry_safe (entry, safe, head, list) {

先前編譯未出現此錯誤，

q_swap

commit: e0ac6f8

目的
以兩個元素為一組進行位置交換，完成後換下一組，直到下一個元素是未成對節點(剩一個節點)或是佇列的 head。

特殊狀況描述
head 是 NULL 或空佇列: 直接返回。

實作流程

一開始初始化兩個指標，l1、l2。
交換指標時，遵循以下順序循環:
1. l1 初始值為 head->next，l2初始值為 head->next->next。之後更新是 l1 指向 l1->next，l2 指向 ~~l1->next->next~~ 新的 l1->next，因為 l1 已更新。
2. 檢查 l1、l2 的地址不是 head，否則結束。
3. 先斷開 l1->next 和 l2->prev，因為知道這兩個指標最後指向 l1、l2。
4. 將 l2->prev 指向 l1->prev，l1->next 指向 l2->next，該步驟將 l1 和 l2 的對左右兩側鏈結設定完畢。
5. 設定左右兩側對 l1 和 l2 成新的關係，l1->next->prev 指向 l1，l2->prev->next 指向 l2。
6. 剩下 l1->prev 和 l2->next 指向彼此，即 l1->prev 指向 l2，l2->next 指向 l1。
結束並返回

得到的實作如下:

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 下一個移動 (避免循環賦值時跑回上一個元素)

故上述可用以下代替:

list_for_each_safe (l1, l2, head) {
    if(l2 != head)
    {
        list_del(l1);
        list_add(l1, l2);
        l2 = l1->next;
    }
}

討論
目前的交換並非執行緒安全的，是否有改進空間? (待完成)

q_reverse

commit: 2eef976

目的
反轉佇列內所有元素順序。

特殊狀況描述

禁止任何記憶體配置相關操作( malloc、free )，如 q_new 、q_insert_head 和 q_insert_tail。
當 head 是 NULL，或元素數量是 0 或者 1: 直接返回。

實作流程
只要我們知道原本最後一個元素的 list 地址 ( tail )，則只要透過 ~~list_for_each_safe~~ list_for_each_safe_prev 重複將 node 移動到 tail 的下一個元素就好了。移動可用 list_move 完成。

或者，可以固定第一個節點不動，剩下的節點都往前移動。

討論
透過首尾指標指向要彼此互換的元素後進行互換? (待確認)

CPU 快取的時間局部性 (temporal locality) 如何變化?

時間局部性應該會變差。 (待確認)
走訪節點的數量會上升? 會更快嗎?

q_reverseK

commit: 82a841f

目的
從頭開始以 K 元素分組，將每組內的元素反轉後，按原組別順序串接。

特殊狀況描述

head 為 NULL 、空佇列或單一元素佇列: 直接返回。
k 為 1 : 不需反轉，直接返回。

實作流程

不要濫用「邏輯」一詞，這裡只是闡述「流程」。

已更正。

當描述節點或資料單元間的關係時，head 譯作「開頭」，而非「頭」，後者是生理詞彙。

了解。

如果使用兩個額外的鏈結串列開頭 ( struct list_head ) 元素( final 和 tmp )，作為暫時節點使用 (out-of-place 的方法)，首先可利用 list_cut_position 分割想要的串列到 tmp 之中。之後，使用先前實作的 q_reverse 反轉 tmp 內節點，並串接到 final 的尾部。最終，將 final 串接到 head 開頭處 (避免有殘存節點)。

討論

q_ascend

commit: c4a4f03

目的
透過擦除佇列中元素達到升冪排列(可允許元素值相同)，注意與 q_sort 使用排序方法不同。

特殊狀況描述

前元素~~須嚴格小於後面所有元素~~ 不可大於後面所有元素。題幹中:

has a node with a strictly less value anywhere to the right side of it。

表示要有嚴格小於當前元素的值才需擦除當前節點。換句話說，如果右邊的值跟當前值相同，不用擦除。
如果後面有更小的元素，則前面所有比他大的元素都要被刪除。
若是 head 是 NULL、空佇列，直接返回 0 ;若是單一元素佇列返回 1 。

實作流程
根據特殊狀況描述 - 2，我們應該從鏈結串列的尾部開始，以最後一個元素的值當作上限參考值，逐漸往前移動，當遇到目前節點的值大於等於上限參考值，移除該節點，否則更新當前值為新上限參考值。

我參考了 list_last_entry 去實作:

使用一個變數 bound_val (pointer to char) 儲存當前的上限值地址，初始值為最後一個元素的 value 地址。
起始的 node 和 safe 分別是倒數第二個元素和第三個元素，已經排除只有單一元素的情況，故僅需判斷 node 是否是 head 當作結束條件。
使用 strcmp 比較 node->value 和 bound_val，只有結果大於 0 要移除當前節點 ( 返回值可參考 strcmp(3) — Linux manual page)。
若 (3) 為非，則 size 加 1 ，並更新上限值為當前的 node->value。

討論

起初想到的做法是透過 list_for_each_entry_safe 往後走訪，比較 node 和 safe 值得大小，如果 node 比 safe 大就刪除 node，但發現這種做法不符合題意，且在以下情況出錯:
```
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 大所以被刪除了
```
後改用逆向走訪的方式。
由於目前的 list.h 中沒有逆向走訪的 API，但是在 linux/list.h 是有實作 list_for_each_prev_safe 和 list_for_each_entry_safe_reverse，可引為參考。

q_descend

commit: c4a4f03

目的
類似 q_ascend，只是要求前元素不可小於後面任一元素。

特殊狀況描述
同 q_ascend 。

實作流程
似 q_ascend。

討論

q_ascend 和 q_descend 只差在 strcmp 時一個是大於一個是小於。可透過巨集 (e.g., Q_ASCEND ) 搭配 cmp function 陣列，將只要 A 就擦除目前節點的邏輯合併在同一個函式中重用，只需要傳入一個不同的 cmp function (參考 C++ 允許使用者定義 cmp 函式) 。初步構想如下 (待完成) :

#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])
    /* ... */
}

對於已知長度的節點值比較 (e.g., int) ，使用 void* 作為參數型別可以增加通用性，那是否能直接比較 void*，其實有 memcmp 可以選擇。但在比較函式內還是建議強制轉型成原本的型別，避免在不同位元組順序 (endianness) 的機器上，比較結果不一致。
舉個例子，0x1234 和 0x1333 若使用 memcmp 比較，在大位元組順序 (big endian) 機器的結果會是 0x1335 會比較大( 0x13 > 0x12 )，但在小位元組順序時會是 0x1234 比較大 ( 0x34 > 0x33 )。可以查看 compiler explorer 的示例。

q_merge_two

commit: 311e580

目的
該函式是 q_merge 的輔助函式，專注於合併兩個佇列，並確保返回時，是第一個佇列 l1 擁有所有元素。

特殊狀況描述

不允許 heap allocation。

實作流程

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 解引用。

故修正如下:

 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 的尾部:

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 我們知道現代編譯器並不會在迴圈內重複進行 stack allcation，只會在進行函式時進行。此外，對於某些 ABI (e.g., x86_64 SysV ABI)，當所用的區域變數大小不大時(對於 x86_64 SysV ABI 為 128 bytes 內)，因為每個函式有紅區 (red zone)，所以 stack allocation 不會發生，即不會對 rsp 進行 sub 指令。

因此秉持著當變數使用才宣告，應該在迴圈中才宣告或定義迴圈內變數:

-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 後面，即可返回。

討論
暫無。

q_merge

commit: 311e580

目的
將 head 所指向的佇列鏈 (queue chain) 中所有的佇列按給定的規則 (升/降冪) 合併至該鏈的第一個佇列中。佇列鏈中所有元素都被保證是依給定規則排列的。

特殊狀況描述

若佇列鏈中佇列個數 ( q_contex_t 實例個數) 為 1，直接返回該佇列的元素個數。
若佇列鏈頭部是 NULL，直接返回 0。
不允許記憶記憶體配置。
需負責釋放除第一個佇列外，所有佇列使用的記憶體 (此時應只包含 struct list_head 實例)，並在釋放後更改該 q_contex_t 的成員 q 指向 NULL。但我對這點存疑，因為 q_merge 在測試時是不允許釋放記憶體，直接改成 NULL 會讓 head 記憶體洩漏。
需統計合併完後的總元素數量，並返回。

實作流程
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 從頭到尾走訪過一次，就能達成目標。

討論

由於特殊狀況描述 (2)，使用變數儲存每個佇列的首元素值是不合適的 (heap based merging)。而每次都使用走訪每個佇列的首元素找尋最小值又太沒效率。jimmylu890303 的實作中提到可建立 mergeTwoLists 將併入過程拆成兩個佇列的合併。

在使用陣列紀錄佇列開頭時，合併兩個佇列的方式有兩種，線性合併和樹狀合併。前者是先合併 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 。該方式的優勢在合併前的平均佇列長度較前方法更短，因此平均的耗時會較低。故陣列實作通常採用後者。但對鏈結串列是否依然如此呢?老師說要多使用數學，所以下面嘗試用數學進行分析:(待確認)

前提假設
- 每個佇列都是有序的。
- 佇列的長度分布均勻。
符號定義

$n$ : 佇列數量 ( q_contex_t 實例數量)。

$L$ : 佇列平均元素長度。

複雜度組成
由於鏈結串列的存取時間複雜度跟陣列不同，因此除了合併的複雜度外，應該額外探討對找到下一個合併目標的時間複雜度。

線性合併複雜度分析
該法對找到下一個合併目標是有利的，因為只需持續向後走訪就能知道下一個合併的目標是誰，且走訪完一次就已經完成合併，故佇列鏈時間複雜度為
$O (n)$ 。
而對於合併時間複雜度，在第一輪為
$O (L + L)$ ，第二輪為
$O (2 L + L)$ ，最後則為
$O (n L)$ ，其總和可用以下函數表示:

$T_{s e q} = \sum_{i = 1}^{n - 1} O ((i + 1) L) = O (L \sum_{i = 1}^{n - 1} (i + 1)) = O (\frac{n^{2} + 2 n - 1}{2} L)$

總時間複雜度為:

$O (\frac{n^{2} + 4 n - 1}{2} L)$

樹狀合併複雜度分析
對於佇列鏈時間複雜度，每次走訪完整個佇列鏈會將目前佇列鏈的有效元素減半，故長度為
$n$ 的佇列鏈共需走訪
$\log_{2} (n)$ 次，時間複雜度記為
$O (\log (n))$ 。每次走訪完整鏈結串列的時間複雜度為
$O (n)$ ，因此合計為
$O (n \log (n))$ 。

對於合併而言，在第一輪有
$n / 2$ 對，每對的合併複雜度為
$O (2 L)$ ，故第一輪的時間複雜度為
$O (\frac{n}{2} \times 2 L)$ 。第二輪則有
$n / 4$ 對，每對的合併複雜度為
$O (4 L)$ ，第二輪時間複雜度與第一輪同。總共有
$\log n$ 輪，故合併複雜度可記為:

$O (n L \log (n))$

總複雜度為:

$O (n \log (n)) + O (n L \log (n)) = O (n \log n (L + 1))$

總結
在數據量較大時，無疑樹狀合併較優，但還是要注意是否有 edge case，例如原始的佇列長度極度不均勻(全都集中在第一個佇列上)，或是佇列長度很短 (
$L$ 為 1，在
$n$ 從 1 到 3 區間，樹狀合併較慢 )。最後提供兩者複雜度在 desmos 上的繪製結果。其中紅色是線性合併，綠色是樹狀合併，設定 L = 5。
是否能為討論(2) 添加實驗證明? 並添加 cache 比較? (待完成)
樹狀合併的迴圈結束條件是否能更精簡? (待確認)

q_sort

commit: b82b952

目的
排序給定佇列，順序依照 descend 的值決定。

特殊狀況描述

時間複雜度須在
$O (n \log n)$ 級別以通過 100, 000 個元素的測試。
若 head 是 NULL、空佇列、或單元素佇列，直接返回。

實作流程
由於在 q_merge 中，我們已經實作了 q_merge_two 用來合併兩個有序的佇列，也有 list_iter_n 來返回目前節點下面 n 個的節點地址。我們能基於已有函式實作 merge sort。

流程如下:

計算當佇列的總元素數量，該值影響 iter_diff 的上限。
同 q_merge，iter_diff 從 1 開始，為 2 的冪，當 iter_diff 小於總元素數量，外層迴圈繼續。
外層迴圈定義了 new_head，用來儲存每輪排序好的元素。
內層迴圈在 head 不為空 (元素還沒被移到 new_head )時，從 head 開始，每次拿取前 iter_diff 個元素放到 left，再繼續擷取 iter_diff 個放到 right，拿取過程藉由 list_cut_n 函式完成。
將切完的 left 和 right 透過 q_merge_two 合併到 left 中，因為 iter_diff 從 1 開始，因此可確保進入的佇列都符合 q_merge_two 的要求，即兩個佇列都已依照 descend 排序 (因為從單元素佇列開始，沒有順序問題)。
將 left 接到 new_head 後，判斷內迴圈是否結束，未結束就回到 (4)。
內迴圈結束 (head 為空) 時，將 new_head 元素移回 head，並判斷外迴圈是否結束，未結束回到 (3)。

上述步驟完成後便已經完成排序。且複雜度是

O (n \log n)

。

討論

目前在迴圈部分與 q_merge 有部分相似，能否簡化? (待完成)

至此，作業中有關佇列操作的函式已完成實作，是時候研讀在 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 函式，其宣告如下:

#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 的定義是:

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 年算法的核心想法並不複雜:

設定變數 i，初始值為 n-1，另產生隨機數 j ，其範圍是從 0 到 i，該隨機數將作為要交換的索引。
交換 a[i] 和 a[j]，也就是把選出來的數丟到尾部。
i-- 後重複 (1)，直到 i 小於 0。

維基百科的說明中，我們應格外留意 Potential sources of bias，這些錯誤可能讓部分結果永遠不可能出現，進而破壞該演算法的隨機性。

針對鏈結串列的洗牌演算法複雜度進行分析:

該算法主要的時間複雜度取決走訪目標節點的過程。與陣列是

O (1)

不同，由於鏈結串列走訪至第 n 個節點的時間複雜度就是

O (n)

，因此基於鏈結串列的洗牌算法理論時間複雜度是

O (n^{2})

級別。更精確的說，假設產生隨機數的函式「夠隨機」，則每個節點被選中的機率是相同的。因此每一輪走訪成本期望值是:

E [X_{k}] = \frac{1}{k} \sum_{i = 1}^{k} i = \frac{k + 1}{2}

其中

k

是剩餘節點數量。整個演算法花在走訪的成本是:

E [T] = \sum_{k = 1}^{n} E [X_{k}] = \sum_{k = 1}^{n} \frac{k + 1}{2} \underset{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 定義如下:

/* 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 〉。

實作

Blog: xoroshiro generators and the PRNG shootout (未來可增加)
Paper: Fast Random Integer Generation in an Interval (提到 OpenBSD 的作法)
Paper: Xorshift (裡面提到為甚麼選擇這幾個數字)

本節可分為 shuffle 和 prng，不過在這之前，先來探討兩者共用的部份 ── 隨機數。

產生隨機數的程式可以單獨分離成一個部分，放置在 random.[ch] 中。分離後， q_shuffle 和產生隨機字串的函式 fill_rand_string 能夠重複使用，減少冗餘程式。可以實作的選項包含 Xorshift、PCG 等。所有隨機數函式的界面應該統一為:

typedef int (*rand_func_t)(uint8_t* buf, size_t n);

該界面與當前的 randombytes 一致(也與 getrandom 一致)，具有較好的兼容性，且後續可實作 prng 選項選用特定的 PRNG。

目前 Xorshift 已經被實作在 random.c，初始狀態使用 2463534242UL。

commit: af1273f

shuffle

commit: 0d63c0e

在第一次完成實作後，檢查實作中是否參雜違維基百科中提到的可能偏差。其中提到使用取餘需要考慮被餘數是否能整除餘數，如果不能，則靠前的數字會比靠後的數字選中的機率高 (modulo bias) 。舉個例子，rand() % 9 中，假設 rand 產生的範圍是 0 - 100，99 和 100 的結果會是 0 和 1，會使這兩個數字比其他數字多一次可能被選到:

uint32_t j;
prng_funcs[prng]((uint8_t *) &j, sizeof(uint32_t));
j = j % i;

為修正該偏差，引入並修改 OpenBSD 的方法:

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

現透過 option prng 1 可以設定採用 Xorshift， 0 為預設，使用 getrandom。值得注意的是，原本程式中使用 randombytes 並未修改，因此不受 prng 影響。所以該選項目前只影響 fill_rand_string 和 q_shuffle 的行為。

結果分析

commit: 522a327 - improve source
commit: 0653289 - add shuffle related trace files
commit: e93e959 - shuffle analyzer

為測試 shuffle 命令，我擴展了 source 的功能，使其能多接收參數 n 作為要 source 同檔案幾次。為避免 n 太大導致超過 FD_SET 出現錯誤，我添加了字元陣列 cached_cmd ，當已經不能再 push_file，則先暫存剩餘的 source 命令。當暫存命令長度為不 0 時，先執行暫存的命令。最終可搭配類似命令蒐集數據:

# 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

雖然現在依然有待改進之處，但已經能進行初步數據蒐集工作:

有時候會遇到 timeout
目前做不到:
```
## 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 結束。
有時候會遇到 dereference NULL pointer。

shuffle

實驗比較了兩種隨機數生成方法：Xorshift 與預設的 getrandom。這兩種方法皆在取得隨機數後採用 OpenBSD 的餘數偏差移除技術，以確保生成的數值分佈更為均勻。為了評估這兩種方法在洗牌演算法中的效果，我們各自進行了兩次實驗，每次對一組長度為 10 的隨機字串連續進行 4,000,000 次洗牌，並以 100,000 次為一組，將整個洗牌過程劃分為 40 個區塊。這樣的設計可以幫助我們觀察在不同區塊中，洗牌結果是否存在系統性的偏差，並進一步分析隨機數序列與洗牌結果之間的關聯性。

python script commit: e93e959 - shuffle analyzer

首先，透過 AI 協助，將分析工具分類成解析器、統計工具、繪圖工具和主程式四個部分。 parser 模組將原始日誌檔案解析為結構化的二維資料。具體而言，檔案開頭的一行(例如 l = [A B C D E F G H I J] )會被解析為候選亂數列表。隨後，在 # start shuffle 之後，每一筆洗牌結果都被依據區塊 ( section ) 劃分，且在每個區塊中，我們分別統計了每個關鍵字在不同位置上的出現次數，形成如下的資料結構：

section[n]["keyword"][k]

這表示第 n 個區塊中，關鍵字在第 k 個位置的累計次數。這種結構可以精確保留每個區塊內不同位置的統計數據，從而避免將各位置數據混合後因正負偏差抵消而看不到局部異常的情況。

在統計分析階段，我們採用了兩種策略:

固定位置統計：針對每個關鍵字在其原始位置上的出現次數進行統計，藉此觀察其是否在預定位置上與理論預期（即每個 cell 的預期值）相符。
全分布統計：針對每個關鍵字在所有 10 個位置上的數據分別計算誤差（觀察值減去預期值），然後依據各位置計算出最大、最小、平均及標準差等統計參數。由於直接將各位置的誤差彙總後會因正負抵消使平均值接近 0，我們採取了分位置計算的方法，並最終從所有位置中選取最極端的誤差指標（例如最大絕對偏差）作為該關鍵字的代表值。

為了進一步驗證數據的隨機性，我們引入了卡方檢定。卡方檢定的基本思想是將觀察到的頻數與理論預期頻數進行比較。具體來說，對於每個關鍵字在各個位置上，我們先計算出每個 cell 的預期出現次數（理論上，每個 cell 的預期值為 section_size 除以關鍵字總數）。然後，我們將實際觀察到的數據與該預期值進行比較，並計算出每個 cell 的偏差程度。這些偏差經過標準化處理後累加起來，就可以得到一個卡方統計量，該統計量反映了觀察數據與理論分布之間的總體偏差大小。換句話說，若隨機數生成與洗牌過程完全符合均勻分布的假設，則卡方統計量應當落在合理範圍內；若存在系統性偏差，則該統計量會顯著偏離理論值。這種方法可以讓我們在統計上驗證兩種隨機數生成方法是否達到理想狀態，或者是否因某些因素導致數據分布出現異常。分析工具的啟動命令如下:

python scripts/shuffle/main.py --file <filename>.log

擷取第一次實驗的結果，Xorshift 的結果如下:
xorshift_error_series
xorshift_error_overall

getrandom 結果如下:

getrandom_series
getrandom_overall

卡方統計結果如下:

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 %，但 Xorshift 更小(集中)。
以 p-value 比較，getrandom 表現更佳，且 getrandom 出現數值較低 (~ 0.5) 的可能性較小。
以理論值 (10, 000) 為基準，兩者最大誤差都在 4 % 左右，但 Xorshift 的最大誤差更低些。

從上述的分析中並不能明確的看出哪一種更為隨機，但從 p-value 可知它們都更偏向均勻的隨機分佈，且偏離理想值最糟糕情況僅約有 4 %。

香農熵比較

在 lab0-c 中，隨機字串是由小寫英文組成的，並未使用到全部的 8 bits，因此其上限的香農熵值為:

\log_{2} (26) \approx 4.70 (bits) \approx 58.75 %

其上限百分比則為

\frac{4.7}{8} \approx 58.76 %

。但實際透過 it RAND 10 觀察後，熵的平均居然只有 30 % 左右，與理論值相差甚遠，這中間發生了什麼?

香農熵定義為:

\begin{matrix} (1) & H (p) = - \sum_{i = 1}^{m} p_{i} \log_{2} p_{i} \end{matrix}

其中

p_{i}

是概率。當我們採用最大概似估計 (MLE) 時，當第

i

個事件出現

n

次，而事件總和數為

N

，概率的估計值為:

\begin{matrix} (2) & {\hat{p}}_{i} = \frac{n_{i}}{N} \end{matrix}

將

(1)

帶入

(2)

得香農熵的估計值為:

{\hat{H}}_{M L E} = - \sum_{i = 1}^{m} {\hat{p}}_{i} \log_{2} {\hat{p}}_{i} = - \sum_{i = 1}^{m} \frac{n_{i}}{N} \log_{2} \frac{n_{i}}{N}

但由於有限樣本的影響，

{\hat{H}}_{M L E}

的期望值

E [{\hat{H}}_{M L E}]

會和真實的

H

有偏差，偏差值可從以下過程推導。

首先定義

f ({\hat{p}}_{i}) = - {\hat{p}}_{i} \log_{2} {\hat{p}}_{i}

並進行泰勒展開式如下:

f ({\hat{p}}_{i}) \approx f (p_{i}) + f^{'} (p_{i}) ({\hat{p}}_{i} - p_{i}) + \frac{1}{2} f^{″} (p_{i}) ({\hat{p}}_{i} - p_{i})^{2}

其中，導數結果如下:

f^{'} (x) = - \frac{1}{\ln 2} (\ln x + 1), f^{″} (x) = - \frac{1}{x \ln 2}

當對

f ({\hat{p}}_{i})

取期望值

E [f ({\hat{p}}_{i})]

時，由於線性(一次項)的期望值是 0，故直接省略:

\begin{matrix} (3) & E [f ({\hat{p}}_{i})] \approx f (p_{i}) + \frac{1}{2} f^{″} (p_{i}) E [({\hat{p}}_{i} - p_{i})^{2}] \end{matrix}

又

Var ({\hat{p}}_{i}) = E [({\hat{p}}_{i} - p_{i})^{2}] = \frac{p_{i} (1 - p_{i})}{N}

所以

(3)

可改寫為:

E [f ({\hat{p}}_{i})] \approx - p_{i} \log_{2} p_{i} + \frac{1}{2} (- \frac{1}{p_{i} \ln 2}) \frac{p_{i} (1 - p_{i})}{N}

簡化後為:

\begin{matrix} (4) & E [f ({\hat{p}}_{i})] \approx - p_{i} \log_{2} p_{i} - \frac{1 - p_{i}}{2 N \ln 2} \end{matrix}

將

(4)

的結果帶入

E [{\hat{H}}_{M L E}]

E [{\hat{H}}_{M L E}] = \sum_{i = 1}^{m} E [f ({\hat{p}}_{i})] \approx - \sum_{i = 1}^{m} p_{i} \log_{2} p_{i} - \frac{1}{2 N \ln 2} \sum_{i = 1}^{m} (1 - p_{i})

其中

\sum_{i = 1}^{m} (1 - p_{i}) = 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{aligned} E [\hat{H}] & = 4.70 - \sum_{N = 5}^{10} \frac{26 - 1}{2 N \ln 2} \\ \approx 4.70 - \frac{3.61 + 3.01 + 2.58 + 2.26 + 2.00 + 1.81}{6} \\ = 2.16 (bits) \end{aligned}

換算下來約 27 %，這就與我們的實驗結果相近許多了! 另外，如果我們修改 MIN_RANDSTR_LEN 為 9，MAX_RANDSTR_LEN 保持為 10，使用預設的 getrandom 搭配以下命令:

commit: 67e2fdb

## 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 資訊:

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 % 這個區間 (

\geq 53.76 %

) 呢? 實際計算後，我們可知當

N \geq 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 ~ dc73dec
queue.c 等檔案有被修改，皆為測試用。

commit: 修正先前修改處，保留論文中的分析方法，但恢復 queue.c 等檔案為實驗前的實作。同時，恢復優化等級為 O1

Paper

量測執行時間:
- 將輸入分為兩個類別，固定(定值)和隨機，每次輸入前隨機決定要選用哪種輸入類別，並進行多次量測。
- 使用 CPU cycle register (e.g., TSC register) 來計算所耗費的週期數。
後處理:
- 由於ㄧ般未後處理的執行時間通常會比實際執行時間長 (positively skewed towards larger execution times)，這是由於有作業系統中斷等干擾。因此會定義一個閾值，超過閾值的數據將被丟棄。
- 應用如 centered product 的高階統計方法，揭露可能存在的統計相依性。
統計檢定:
- 利用引入統計檢定，當虛無假設 (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 中，展開預處理器可以得到以下結果:

_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 可以找到他們的實作:

#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。

Code tracing

讓我們先用幾句話總結作者在幹嘛，這樣比較好看懂下面的分析:

透過大量測量，收集在不同輸入下的執行時間數據。
使用多個裁剪門檻（同一組數據產生多個 t-test 統計上下文，ttest_ctxs）搭配 Welch’s t-test，分別檢查原始數據與不同裁剪後的數據是否存在顯著差異。理論上會有 DUDECT_NUMBER_PERCENTILES + 2 個 ttest_ctxs，多出來的 2 是原始+二階共兩個上下文。
ttest_ctxs 透過 t_push 以 execute_time 和 class 為參數更新裡面的平均和
$M 2$ ，這兩個值會影響到
$t$ 值。
從所有統計上下文中計算
$t$ (一個上下文裡面的數據都是陣列，長度為 2，表示 null hypothsis 和 alternative hypothsis，也就是 class 0 和 class 1 的對應數據，用class 0 和 class 1 對應的數據去算出純量值
$t$ )
挑選出
$t$ 值最大的那一組，並將其
$t$ 值與預設的閾值比較 ( t_threshold_moderate，屬於經驗參數)；超過閾值，就判定程式可能並非 constant time，如果超過 t_threshold_banana 就鐵定不是 constant time。

以下是對原始程式的分析:

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 方法在線更新平均和變異數:

μ_{n} = \frac{1}{n} \sum_{i = 1}^{n} x_{i}, M 2_{n} = \sum_{i = 1}^{n} (x_{i} - μ_{n})^{2} .

當第 n+1 個數據

x_{n + 1}

到來時，我們希望能以遞增的方式更新平均值和

M 2

，而不必重新計算所有數據。

更新平均值
定義

$\begin{matrix} (1) & δ = x_{n + 1} - μ_{n} . \end{matrix}$
那麼新的平均值
$μ_{n + 1}$ 可以寫成

$\begin{matrix} (2) & μ_{n + 1} = μ_{n} + \frac{δ}{n + 1} . \end{matrix}$
更新累計平方差 (
$M 2$ )
我們需要計算更新後的累計平方差:

$M 2_{n + 1} = \sum_{i = 1}^{n + 1} (x_{i} - μ_{n + 1})^{2} .$
通過推導可以證明，這個更新可以寫為:

$M 2_{n + 1} = M 2_{n} + δ (x_{n + 1} - μ_{n + 1}) .$
注意到：

$x_{n + 1} - μ_{n + 1} = x_{n + 1} - (μ_{n} + \frac{δ}{n + 1}) = δ - \frac{δ}{n + 1} = \frac{n}{n + 1} δ .$
代入上式得:

$\begin{matrix} (3) & M 2_{n + 1} = M 2_{n} + δ \cdot \frac{n}{n + 1} δ = M 2_{n} + \frac{n}{n + 1} δ^{2} . \end{matrix}$

作者使用

(1) 、 (2) 、 (3)

對平均和累積平方差進行及時更新。

以下是重頭戲，有關 percentile 和統計數據的處理:

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 則需要注意幾件事情:

從第 10 個測量值開始，而不是第 1 個，避免起始的波動影響判斷結果。
second order 不進行剪裁，而使用更高階的統計方法。
first order 會使用 ctx->percentiles[crop_index] 作為閾值進行剪裁，若超過閾值則不進入 t_push。
全部的測試都會被 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）對應的剪裁閾值，依照公式可算得

percent = 1 - {0.5}^{10 \times \frac{11}{100}} \approx 1 - 0.4665 = 0.5335 (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

隨著 percentile index 越高，被剪裁的數據百分比會越低，因為保留的數據比例接近 100%，幾乎沒有數據被忽略，大部分都進入 t_push。而進入 t_push 意味著更新了該上下文的對應的 class 的數據，包含平均和

M 2

。

需要特別注意，這些裁剪閾值是根據第一次量測的分布確定的，之後所有後續的測試都會使用這組固定的閾值。即使隨後的測量數據分布可能有所變化，裁剪操作仍然依照第一次量測時的基準來進行。

lab0-c 和原作差別在哪?

分析那麼多，lab0-c 和原本論文到底差別在哪?

lab0-c 僅維護一組名為 t 的 t_context_t，照理來說要有 DUDECT_NUMBER_PERCENTILES + 2 組。
沒有先行排序，也沒有進行數據裁減，全部都被送進 t_push 了。這也表示極端值沒有被裁剪，畢竟沒有實現 percentile 和 prepare_percentiles 等函式。
測量數值定義為 N_MEASURES，數值為 150。
真正實施 measure 時，不是從 0 開始，而是從 DROP_SIZE 開始，而且量測也只有到 N_MEASURES - DROP_SIZE。所以量測結果 ( exec_time ) 頭尾合計有 40 個 0。但根據 (2)，這些 0 都會進入 update_statistics，這明顯會造成影響。
未拋棄第一次資料。

接著，觀察他人的實作 (見參考) ，大部分人的作法是在 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 同學) 最後受好奇驅使，實作分析數據相關的工具。

分析數據

以下的執行時間單位為 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 進行分析:

python scripts/deduct/deduct_analyzer.py

運行後得到 CDF、長條圖和 KDE 圖。下方兩張圖分別是 insert_head 和 remove_head 的 CDF 對比。

cdf_insert_head

cdf_remove_head

可以觀察到 insert 比 remove 的分布差異性更高，

t

值也更高，因此 remove 也比較容易通過 constant time 檢查。

而當我移除 q_insert_head 中用到的 strdup，只保留 element_t 的 malloc 和 list_add 時，神奇的事情發生了!

cdf_insert_head

兩者的分佈居然趨向一致，但照常理，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。

從下圖可以看出分布並不一樣:

./qtest
alloc_test
quit

# plot
python scripts/deduct/deduct_memory.py

alloc_test_random_dual_kde

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 趨勢符合:

原始實作

char *cp = strdup(s);
if (!cp)
    return false;

kde_insert_head

➜ 極高機率無法通過 constant time

模擬 constant time malloc on stack

// 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

➜ 每次都通過 lab0-c constant time 測試 (大約在 6 or 7 次嘗試時會通過)，但是論文中說只要有沒通過的，就算沒通過，lab0-c 比較寬松。

完全刪除字串相關操作 (剩下 malloc element_t 和 list_add )

kde_insert_head

這三張圖的結果可以看出 malloc 的多寡對 q_insert_head 會影響其執行時間分布，進而使 class 0 和 class 1 的分布差距過大，因此不該被忽略。

總結

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

後發現當使用 O1 則 alloc_test 無法重複模擬結果，隨機預先 malloc 模擬的 class 1 和 class 0 的分布是一致的。是還有其他因素 (e.g., cache miss …) 影響了 deduct 測試結果但還沒被找出，還是僅因測試過於簡單被優化了? 目前能確認的是與 strdup 有關 (待確認)

到此，我認為依照作者的觀點，不應該在每一個 doit 都執行 prepare_percentiles，因為該函式預設只對執行時間排序，導致 class 混在一起。依照作者說明，應該討論原始數據、一階 (cropping)、二階的

t

值，都應該小於訂定的 threshold，才能說可能是時間常數。因此當前的實作或許本來就不會通過 deduct 的測試，因為記憶體配置上並非時間常數。所以如果原始數據沒有通過測試，則應該先思考並驗證目前實作是否真正符合常數的運行時間。

Reference

研讀 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 :

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 痛點:

容易受到中斷干擾: 只要受到中斷或其他非 IO 錯誤的干擾，read 或 write 可能在未完成指定進度前就返回，儘管可能跟目前正操作的檔案無關，但由於系統呼叫已中斷，我們獲得的結果就是不完整的。所以往往要檢查返回值，確保與預期行為一致。但若使用 RIO 的 unbuffered API (e.g.,readn ) 則不用擔心此事。
提供 buffered function: 為避免非必要多次呼叫系統呼叫，RIO 封裝內含一塊 buffer，配合 buffered function (e.g., readline in console.c )，他會先嘗試一次性 IO 該 buffer 能承載的最大長度 (8190 bytes，保留 \n\0 位置)，並嘗試尋找 \n，在下一次被呼叫後根據 count 選擇要從 buffer 操作( count > 0 ) 還是執行新的 read。如此，可以有最低的系統呼叫次數。
執行緒安全: 傳統的 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) 中。這樣才能將實作展開到呼叫處。如果實作放在其他源文件中，則不能確保每個編譯單元中，實作都存在。對於實作不存在的編譯單元將導致無法內嵌。

注意術語！

inline 從內聯改成內嵌；header file 從頭文件改成標頭檔。

文章通常有標題，不要書寫「這篇文章」，這無助於溝通。

了解。

為甚麼非 static 不可呢?根據〈我有所不知的 static inline function〉知道要去 GNU Manual 中 (GCC version 13.3.0) 尋找答案，在 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

不要說「可能」，當你參考到，就列出，否則不要裝忙。

好的。

作業

2024 homework1 開發紀錄
- yeh-sudo: 關於 sort (timsort) 的分析可以參考
- jimmylu890303: sort 分析, linux/list_sort.c
- chiangkd (2023q1): 作業完成度參照 (希望至少)
- Linux 核心專題: 改進 lib/list_sort.c

你現在還沒有能力評價「作業完成度高」，唯有當你充分投入並超越你要評價的作品時，你才有立場充分評價「完成度」。

已修正措辭。

Jim Huang

2025/02/27 09:29:31

的，則指向結構體。指向型別為 list_head 的指針用橘色

Dennis Liu

2025/02/27 11:44:44

已重新編排圖的說明文字。

2025/02/27 15:56:46

可替換使其更精簡

使用 git diff 或 diff -up 來產生用於張貼到筆記的程式碼變動

2025/02/27 16:06:38

已完成更動

2025q1 Homework1 (lab0)

開發環境

文件紀錄

工具鏈相關

編譯選項

VSCode gdb

Breakpoint

實作 queue.[ch]

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_ascend

q_descend

q_merge_two

q_merge

q_sort

新增 shuffle 命令與 prng 選項

如何為 lab0-c 增加新的命令?

Fisher–Yates shuffle

PRNG (Pseudo Random Number Generators)

實作

shuffle

prng

結果分析

shuffle

香農熵比較

〈 Dude, is my code constant time? 〉之 dudect 實驗與探討

Paper

Welch's t-test V.S. Student's t-test

What is simulation mode?

Code tracing

lab0-c 和原作差別在哪?

分析數據

總結

Reference

研讀 select 和 console.c 中的 RIO

What is select?

What is RIO?

By the way

靜態內嵌函式 (Static Inline Function)

Reference

Read more

Linux2025q1: Quiz 2 Write-Up

2025q1 Homework1 (ideas)

Linux2025q1: Toolchain Write-Up

Linux2025q1: Perf Write-Up