2025q1 Homework1 (lab0)

contributed by < Hande1004 >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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 字元

開發環境

~$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
架構：                    x86_64
  CPU 作業模式：          32-bit, 64-bit
  Address sizes:          48 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   16
  On-line CPU(s) list:    0-15
供應商識別號：            AuthenticAMD
  Model name:             AMD Ryzen 9 7940HS w/ Radeon 780M Graphics
    CPU 家族：            25
    型號：                116
    每核心執行緒數：      2
    每通訊端核心數：      8
    Socket(s):            1
    製程：                1
    Frequency boost:      enabled
    CPU(s) scaling MHz:   32%
    CPU max MHz:          5263.0000
    CPU min MHz:          400.0000
    BogoMIPS:             7985.24
Virtualization features:  
  虛擬：                  AMD-V
Caches (sum of all):      
  L1d:                    256 KiB (8 instances)
  L1i:                    256 KiB (8 instances)
  L2:                     8 MiB (8 instances)
  L3:                     16 MiB (1 instance)
NUMA:                     
  NUMA 節點：             1
  NUMA node0 CPU(s)：     0-15

針對佇列操作的程式碼實作

q_new

使用 list_head 指標 head 指向一個大小等於 list_head 結構體的記憶體空間，然後透過 Linux 提供的 INIT_LIST_HEAD() 巨集，將 head 的 next 和 prev 指向自身，以初始化為一個空的佇列。

q_free

使用兩個 list_head 指標 pos 和 safe，並透過 list_for_each_safe() 巨集走訪佇列中的每個節點。在走訪過程中，先使用 list_del() 將當前節點從鏈結中移除，然後調用 q_release_element() 釋放該節點的記憶體。最後，釋放 head 所佔用的記憶體。

q_insert_head

使用 strdup() 函式將指標 s 所指向的字串複製到 node->value（即 element_t *node 所指向的記憶體空間）。接著，透過 list_add() 將此節點插入到 head 之後，使其成為鏈結串列的第一個元素。

q_insert_tail

使用 strdup() 函式將指標 s 所指向的字串複製到 node->value（即 element_t *node 所指向的記憶體空間）。接著，透過 list_add() 將此節點插入到 head 之前，使其成為鏈結串列的最後一個元素。

q_remove_head

使用 list_del() 斷開此鏈結串列的第一個元素，然後將 node->value（即 element_t *node 所指向的記憶體空間）所指向的字串複製最多 bufsize - 1 個字元到 sp 所指向的字串中，最後將 sp[bufsize - 1] 設置為 '\0' 以確保字串結尾。

q_remove_tail

使用 list_del() 斷開此鏈結串列的最後一個元素，然後將 node->value（即 element_t *node 所指向的記憶體空間）所指向的字串複製最多 bufsize - 1 個字元到 sp 所指向的字串中，最後將 sp[bufsize - 1] 設置為 '\0' 以確保字串結尾。

q_size

用 list_for_each() 走訪每個節點，用計數器 n 來計算走過幾個節點，最後得到這個鏈結串列的總共元素數目。

q_delete_mid

計算 (q_size(head) - 1) >> 1 來獲取走訪至鏈結串列中點所需的步數。接著，使用 list_for_each() 走訪節點，當走訪次數達到計算出的中點位置時，刪除該節點。

q_delete_dup

使用 list_for_each_safe() 走訪鏈結串列，透過 pos 來走訪節點並用 safe 記錄下一個節點以防止刪除節點後影響迭代，同時使用 dup 變數來標記是否處於重複區間，當發現當前節點與下一個節點相同時，設定 dup = true 並刪除當前節點，而當 dup == true 且當前節點與下一個節點不同時，則代表重複區間結束，需要刪除該區間最後一個重複的節點，最後若 dup == true，則再刪除最後一個重複的節點，以確保鏈結串列中不再存在重複元素。

q_swap

透過 pos 走訪節點並用 safe 記錄下一個節點，當 pos 和 safe 都未到達 head 時，則刪除 pos 並將其插入到 safe 之前，依此方式逐步交換相鄰節點，最終實現兩兩交換鏈結串列中的元素。

q_reverseK

使用 q_size(head) 計算節點數 num，確保只反轉完整的 k 組節點，並將 pos 設為 head->next 開始反轉每組反轉時先紀錄 first 作為該組的第一個節點以便後續連接，再記錄 first_prev 以確保反轉後能重新串接，並透過指標的指標 first_next 指向 first->next來確保第一個節點能夠，然後使用 m 來追蹤當前 k 組內的節點索引。

struct list_head *pos = head->next, *safe, *first, *first_prev;
int num = q_size(head);
for (int i = 0; i < num / k; i++) {
    struct list_head **first_next = NULL;
    int m = 0;
    for (safe = pos->next; m < k; pos = safe, safe = pos->next, m++) {

當 m == 0；
每組反轉時先紀錄 first 作為該組的第一個節點以便後續連接，再記錄 first_prev 以確保此組的最後一個節點反轉後可以接到正確的 prev，並透過指標的指標 first_next 指向 first->next來確保走訪到此組最後一個節點時，第一個節點能夠更改 next的地址。

struct list_head *next = pos->next;
struct list_head *prev = pos->prev; 
if (m == 0) {
    first = pos;
    first_prev = prev;
    first_next = &pos->next;
    pos->prev = next;
    continue;
}

當0 < m < k-1 的過程中；
pos->prev指向 next、pos->next 指向 prev 來進行反轉。

if (0 < m && m < k - 1) {
    pos->prev = next;
    pos->next = prev;
    continue;
}

直到 m == k-1 時完成該組反轉；
將 pos->prev 指向 first_prev 和first_prev->next指向pos以確保此組新的第一個節點與前一組的最後一個節點相互鏈結；first_next 指向 next 讓此組新的最後一個節點能正確連接到下一組的第一個節點且next->prev 指向 first 以確保雙向鏈結正確，最後將 pos 移動到 next 以進入下一組的反轉。

if (m == k - 1) {
    pos->next = prev;
    pos->prev = first_prev;
    *first_next = next;
    first_prev->next = pos;
    next->prev = first;
    pos = next;
    break;
}

q_sort

這部分我原先是用 insert sort 的方式去做，可惜過不了 make test 的時間複雜度測試，後來改用老師給的參考資料 Linked List Sort 中的 merge 演算法來做，其中分為三個函式，分別為 q_sort() 、 mergeSortList() 、 merge()。

第一步 void q_sort(struct list_head *head, bool descend) (以降序為例):
我將原本環狀的鏈結串列切成雙向非環狀的鏈結串列，好讓後面 merSortList() 函式在做分割的時候可以更好找到截止點，且用非環狀的鏈結串列去比照老師的參考資料也比較好理解(參考資料為單向非環狀的鏈結串列)。

 struct list_head *first_node = head->next;
    struct list_head *last_node = head->prev;
    first_node->prev = NULL;
    last_node->next = NULL;
    struct list_head *merge_pos = mergeSortList(first_node, descend);

第二步 struct list_head *mergeSortList(struct list_head *node, bool descend) :

使用快慢指標將鏈結串列的中點找到，從中點將其拆分成兩個部分，接著用函式遞迴的方式不斷的拆分此鏈結串列，直到無法繼續拆分為止(只剩下單一節點)，最後將這些拆分後的節點與鏈結串列傳入 merge() 中。

 struct list_head *fast = node->next;
    struct list_head *slow = node;
    // split list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    if (fast) {
        fast->prev = NULL;
    }

    // sort each list
    struct list_head *l1 = mergeSortList(node, descend);
    struct list_head *l2 = mergeSortList(fast, descend);
    return merge(l1, l2, descend);

第三步 struct list_head *merge(struct list_head *l1, struct list_head *l2, bool descend) :
使用一個變數 struct list_head tmp 來當作此鏈結串列暫時的頭，*tail = &tmp 為用來排序時的過度指標，接著將傳入進來的l1 和 l2 所指向的第一個元素比大小，value 比較大的節點會成為 tail 指向的位置，接著更新 tail 的 next 指向 value 較大的節點，而 value 較大的節點的 prev 指向 tail ，接著 value 大的節點則更新指向其 next 的位置。
進入下一輪的比較，重複一樣的動作，直到 l1 或 l2 其中一個指標指向 NULL 就跳出迴圈。

while (l1 && l2) {
            const element_t *node1 = list_entry(l1, element_t, list);
            const element_t *node2 = list_entry(l2, element_t, list);
            if (strcmp(node1->value, node2->value) >= 0) {
                tail->next = l1;
                l1->prev = tail;
                tail = tail->next;
                l1 = l1->next;
            } else {
                l2->prev = tail;
                tail->next = l2;
                tail = tail->next;
                l2 = l2->next;
            }
        }

這時還會剩下最後一個節點沒有被鏈結，所以要把 tail 跟指向最後一個節點的指標相互鏈結，最後把 tmp.next(此排序好的鏈結串列的第一個節點的指標) 回傳。

if (l1) {
    tail->next = l1;
    l1->prev = tail;
}
if (l2) {
    tail->next = l2;
    l2->prev = tail;
}
return tmp.next;

最後一步 void q_sort(struct list_head *head, bool descend) :

將 head 重新鏈結，還原成環狀的雙向鏈結串列。

struct list_head *merge_pos = mergeSortList(first_node, descend);
head->next = merge_pos;
    merge_pos->prev = head;
    while (merge_pos->next) {
        merge_pos = merge_pos->next;
    }
    merge_pos->next = head;
    head->prev = merge_pos;

q_ascend

使用 list_for_each_safe() 這個巨集，pos 從 head->prev（最後一個節點）開始向前走訪，並透過 safe 記錄 pos->prev 以確保刪除節點後不影響繼續走訪，接著取得 pos 所對應的 element_t *node，若 node->value 大於 mini_value（代表該節點值比後方節點大），則使用 list_del(pos) 將 pos 從鏈結串列中移除並釋放記憶體 q_release_element(node)，否則更新 mini_value = node->value，確保後續的比較基準維持遞增順序。

q_descend

pos 從 head->prev（最後一個節點）開始向前走訪，並透過 safe 記錄 pos->prev 以確保刪除節點後不影響後續走訪，接著取得 pos 所對應的 element_t *node，若 node->value 小於 max_value（代表該節點值比後方節點小），則使用 list_del(pos) 將 pos 從鏈結串列中移除並釋放記憶體 q_release_element(node)，否則更新 max_value = node->value，確保後續的比較基準維持遞減順序。

q_merge

將所傳進來的 k 個 queue 中的鏈結串列依序的接在第一個 queue 的鏈結串列後面，然後使用 q_sort() 對整個 queue做排序。

queue_contex_t *atx = NULL,
                   *first = list_first_entry(head, queue_contex_t, chain);
list_for_each_entry (atx, head, chain) {
    if (atx == first)
        continue;
    if (atx && atx->q) {
        list_splice_tail_init(atx->q, first->q);
        first->size += atx->size;
        atx->size = 0;
    }
}
q_sort(first->q, descend);

研讀 lib/list_sort.c

在 qtest 提供新的命令 shuffle

使用老師給的參考資料Fisher–Yates shuffle所使用的方法來實作 shuffle 這個指令。

運作方式說明:

假設總共有 i 個節點。

先從這 i 個節點中隨機找出一個第 1 個到第 i - 1 的的節點。
將這個節點與第 i 個節點交換。
i = i - 1
重複以上階段 1 、2、3 直到做到 i = 1 就結束。

程式實作:

i_pos 當作要被交換的節點。
j_pos 為隨機取第 1 個節點到第 i - 1 個的節點。

接著來要判斷兩個是否相鄰，若兩者不相鄰需要使用兩次 list_move() 將 j_pos 與 i_pos 分別移動至對方指向的位置；但如果兩者相鄰，那做兩次 list_move() 將無意義，因為會換回原本的位置，所以只須做一次 list_move() 即可。

struct list_head *j_prev = j_pos->prev;
struct list_head *i_prev = i_pos->prev;
if (i_prev == j_pos) {
    list_move(j_pos, i_pos);
} else {
    list_move(i_pos, j_pos);
    list_move(j_pos, j_prev);
}

統計方法驗證 `shuffle`

參考老師的作業的2025 年 Linux 核心設計課程作業 —— lab0 (D)

因為 Pearson's chi-squared test 能檢驗虛無假說（Null hypothesis），所以可以由此來驗證我的 shuffle 函式是否符合 Uniform distribution。

$H_{0}$ （虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
$H_{1}$ （對立假說）: shuffle 的結果發生的機率至少有一個不同

1. 計算 chi-squared test statistic
$X^{2}$

X^{2} = \sum_{i = 1}^{n} \frac{(O_{i} - E_{i})^{2}}{E_{i}}

$X^{2}$ : Pearson's cumulative test statistic
$O_{i}$ : the number of observations of type i
$E_{i}$ : the expected count of type i

Expectation:  41666
Observation:  {'1234': 41324, '1243': 41704, '1324': 41676, '1342': 41627, '1423': 41643, '1432': 41792, '2134': 41805, '2143': 41490, '2314': 41791, '2341': 41378, '2413': 41372, '2431': 41737, '3124': 41460, '3142': 41780, '3214': 41581, '3241': 41821, '3412': 41724, '3421': 41477, '4123': 42010, '4132': 41631, '4213': 41774, '4231': 41774, '4312': 41719, '4321': 41910}
chi square sum:  16.98694379110066

X^{2}

= 16.98694379110066

2. 決定自由度（degrees of freedom）

因為 4! = 24 ，所以自由度為 23（可自由變換的變數只有 23 個）。

3. 選擇顯著水準

顯著水準（Significance level） α = P(拒絕
$H_{0}$ |
$H_{0}$ 為真)
alpha 設定為常見的 0.05。
Table: Chi-Square Probabilities 我的自由度為 23 ， 14.842 <
$X^{2}$ = 16.98694379110066 < 32.007 ，故 P value 介於0.9 和 0.1 之間。

4. 統計檢定的結果不拒絕虛無假說

因為P value（0.9~0.1）> alpha（0.05），統計檢定的結果不拒絕虛無假說（

H_{0}

）

測試程式

測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖：
Figure_1
由此可知 shuffle 確實呈現均勻分佈

設計一組新的 PRNG 命令

為了設計一組新的命令可以用來切換不同 PRNG 的實做，需要先了解原指令的 ih RAND 10 是怎樣實做出來的，原先我對於這部份該怎樣做是沒想法的，後來參考了 wurrrrrrrrrr 的分析後了解到要將 ih RAND 10 這串指令實做有幾個重要的函式。

如何拆解一組命令

首先是 interpret_cmd() 這串指令會將傳進來的命令用 parse_args() 來拆解成不同的字串，並用 argv[] 這個指標去指向拆解下來的不同字串，再把這些不同的字串指標的指標傳進 interpret_cmda() 裡面去執行每個命令（console.c)。

static bool interpret_cmd(char *cmdline) :

char **argv = parse_args(cmdline, &argc);
bool ok = interpret_cmda(argc, argv);

static char **parse_args(char *line, int *argcp):
這段函式將傳進來的整段命令做分解，並透過空白的字串去判斷哪些部份是需要被拆開的，把拆開的部份用 \0 做取代。

while ((c = *src++) != '\0') {
    if (isspace(c)) {
        if (!skipping) {
            /* Hit end of word */
            *dst++ = '\0';
            skipping = true;
        }
    } else {
        if (skipping) {
            /* Hit start of new word */
            argc++;
            kipping = false;
        }
        *dst++ = c;
    }
}

接著把用 \0 做區分好的字串依序存入新開好的記憶體空間，並 argv[] 這個指標來存取。

for (int i = 0; i < argc; i++) {
    argv[i] = strsave_or_fail(src, "parse_args");
    src += strlen(argv[i]) + 1;
}

也就是說會將 ih RAND 10 這個命令拆解成 ih 、RAND 、 10 三個字串，並依序用 argv[0] 、 argv[1] 、 argv[3] 三個指標來指向。

static bool interpret_cmda(int argc, char *argv[]) :
將整段命令處理好後，此函式就是要將每個命令依序去執行，首先要先判斷使用者輸入的第一個字串是否是屬於在原先設定的命令集裡面，因此要去判斷 arg[0] 是否等於命令集中的某個命令。

while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
        next_cmd = next_cmd->next;

如果有在命令集中，也就是使用者輸入的命令正確，那就會將裡面的命令執行

if (next_cmd) {
    ok = next_cmd->operation(argc, argv);
    if (!ok)
        record_error();
}

實際執行命令

了解完電腦如何拆解命令後，需要知道怎樣讓這些命令實際運作，這裡也有幾個函式來達成這件事。

static bool queue_insert(position_t pos, int argc, char *argv[]) :
在這個函式中會去判斷使用者是否有輸入 RAND 如果有那就會將 need_rand 設為 true。

if (!strcmp(inserts, "RAND")) {
    need_rand = true;
    inserts = randstr_buf;
}

接著如果 need_rand 為 true 就會調用 fill_rand_string 來隨機填充字串。

if (need_rand) 
    fill_rand_string(randstr_buf, sizeof(randstr_buf));

static void fill_rand_string(char *buf, size_t buf_size) :
這段函式會先去設定隨機的字串長度

len = rand() % buf_size

接著調用 randombytes() 來得到一個隨機數，此隨機數主要是用 linux <sys/random.h> 中的函式 getrandom() 來實做的。

透過隨機數除餘的方法將每個字元隨機填入 a 到 z 來達到生成隨機字串的方法。

static const char charset[] = "abcdefghijklmnopqrstuvwxyz"
...
for (size_t n = 0; n < len; n++)
    buf[n] = charset[randstr_buf_64[n] % (sizeof(charset) - 1)];

buf[len] = '\0';

在 q_show 中，有去判斷是否要用shannon_entropy.c 來計算隨機生成字串的熵，如果使用者有輸入 option entropy 1 就會將 show_entropy 設定為 1 。

if (show_entropy) {
    report_noreturn(
    vlevel, "(%3.2f%%)",
    shannon_entropy((const uint8_t *) e->value));
}

Xorshift

了解隨機生成字串的命令跟實做後，便可以真正得來新增指令了，為了新增指令，我額外新增了一個檔案，xorshigt.c 來負責實做新的指令，我的新指令是將原本 linux_getrandom() 的部份額外增加了 xorshift 的操作，之所以採用這種方式，是因為 xorshift 在執行時需要一個起始的隨機值。若改用 rand() 或其他隨機來源，會導入額外變因，導致與原始 getrandom() 的隨機性比較不再公平。
為了保持比較的一致性與公平性，我選擇在 linux_getrandom() 所產生的隨機數上進行 xorshift() 處理，這樣可以確保兩者僅有「是否經過額外處理」這一個變數，從而更純粹地比較是否能提升或影響隨機性。

for (int i = 0; i < chunk / sizeof(uint64_t); i++) {
    uint64_t *x = (uint64_t *) buf;
    x[i] ^= (x[i] << 13);
    x[i] ^= (x[i] >> 7);
    x[i] ^= (x[i] << 17); 
}

在原先的 queue_insert() 中去增加 xorshift 的判斷

if (!strcmp(inserts, "xorshift")) {
    need_rand = true;
    inserts = xorshiftstr_buf;
}

並參考原先的 fill_rand_string() 的方式，來新增 fill_rand_string_xorshift 以填充字串。
再去判斷使用者輸入的是哪個命令，來調用 fill_rand_string() 或 fill_rand_string_xorshift

if (need_rand) {
    if (inserts == randstr_buf) {
        fill_rand_string(randstr_buf, sizeof(randstr_buf));
    } else if (inserts == xorshiftstr_buf) {
        fill_rand_string_xorshift(xorshiftstr_buf, sizeof(xorshiftstr_buf));
    }
}

最後順利實做出能夠切換兩個 PRNG 的指令

cmd> new
l = []
cmd> option entropy 1
cmd> ih RAND 10
l = [zxgnqillh(35.94%) foevg(26.56%) dtnwspo(32.81%) nmxjvtmt(29.69%) llwnksm(29.69%) romzqnusa(37.50%) fsdsx(21.88%) phciq(26.56%) xrtryph(29.69%) dpydskf(29.69%)]
cmd> free
l = NULL
cmd> new
l = []
cmd> option entropy 1
cmd> ih xorshift 10
l = [rcmlxrp(29.69%) jtuixphs(35.94%) tyscvln(32.81%) izngzv(26.56%) zsmhcowy(35.94%) fjdqiz(29.69%) eeurynhcm(35.94%) pgwfc(26.56%) efjout(29.69%) ohsqrqwtp(35.94%)]

用統計工具 dieharder 檢測兩個 PRNG 命令

為了比較兩種隨機數產生方式的品質，我分別用 linux_getrandom() 和自己實作的 xorshift() ，各自產生 10,000 筆二進位隨機資料（共約 10MB），再透過 Dieharder 工具進行測試。Dieharder 提供超過 100 種統計測試，會輸出 p-value 判斷是否隨機。我根據各自通過的測試數與 p-value 的分布，評估哪一種方法更具隨機性。

測試結果彙整表

隨機數產生器	PASSED	WEAK	FAILED	總測試數
linux_getrandom	63	15	36	114
xorshift	59	16	39	114

由實驗結果可見，原本的 linux_getrandom() 隨機數產生器整體表現略優於經過 xorshift() 擴充後的版本。雖然兩者在 Dieharder 測試中的通過數相差不大，但 xorshift() 結果中 FAILED 次數略多，顯示其隨機性並未因為加入後處理而提升。

值得注意的是，本次 xorshift() 的實作其實是建立在 linux_getrandom() 所產生的資料上，再進一步對這些資料進行簡單的 xorshift() 運算處理。然而，這樣的後處理不但未能增加隨機性，反而在部分測試中造成更多失敗。

推測原因：原本的 getrandom() 產生的隨機數更為隨機，加上 xorshift 應用反而破壞了原本的隨機性。

這顯示：將一個品質已高的 PRNG 輸出再次加工，未必能提升隨機性，反而可能因為額外的數學運算引入偏差，降低其統計測試的通過率。

用Valgrind分析記憶體問題

當我寫完 queue.c 後，我就開始測試 make test 但出現了這樣的錯誤訊息：

+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer---     trace-13-malloc 0/6

這讓我花了滿多時間，因為一開始我不知道這個究竟是錯在程式碼的哪邊，後來我就使用 Valgrind 這個工具幫我分析 make valgrind 得到這樣的提示：

+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
==15555== Invalid write of size 8
==15555==    at 0x10FF89: INIT_LIST_HEAD (list.h:88)
==15555==    by 0x10FF89: q_new (queue.c:18)
==15555==    by 0x10D18F: do_new (qtest.c:155)
==15555==    by 0x10E929: interpret_cmda (console.c:181)
==15555==    by 0x10EEEE: interpret_cmd (console.c:201)
==15555==    by 0x10F17D: cmd_select (console.c:593)
==15555==    by 0x10FA5B: run_console (console.c:673)
==15555==    by 0x10DD18: main (qtest.c:1494)
==15555==  Address 0x8 is not stack'd, malloc'd or (recently) free'd

接著我去看了我的 q_new 才意識到我漏掉題目的一個關鍵條件：

Return: NULL for allocation failed

但我的程式碼當時並沒有

if (!head)
    return NULL;

因此就發生錯誤了。

研讀論文〈Dude, is my code constant time?〉

研究動機

現代的加密程式或安全性相關程式，若在執行速度上「會隨著密鑰或秘密資料而改變」，就會暴露出潛在的「時間側通道攻擊（Timing Side-Channel Attack）」風險。
在這類攻擊中，攻擊者僅透過量測目標程式的「執行時間」就可能推測到程式內部的秘密資訊。因此，許多密碼函式都強調必須實作為「常數時間」：也就是不論輸入或密鑰是什麼，整個程式的執行速度都應該「幾乎」相同。

驗證一個程式究竟是否真「常數時間」並不容易。因為現代CPU的微架構（cache、分支預測、管線、微碼更新…）都可能造成執行時間的微小變動。

因此，作者提出名為 dudect 的工具，來自動且統計式地檢測一段程式在真實硬體上執行時，是否具有可觀測的「執行時間差異 (timing leakage)」。

此作法不是用靜態分析或硬體模型，而是直接在目標平台上對程式進行大量測試，並且應用統計檢定來檢查是否存在對「輸入資料」敏感的時間差異。

核心原理

該論文主張的檢測流程可以總結為「三步驟」

測量執行時間
在同一個平台、同一個執行環境下，對欲測試的函式進行大量次的呼叫，每次呼叫都記錄「起始時間」與「結束時間」，計算出該次呼叫的執行週期或毫秒數。

為了檢測時間是否因「輸入資料」而改變，他們會準備「兩類」輸入:
第一類：固定輸入（例如全 0、或某固定模式）
第二類：隨機輸入（每次都重新生成隨機值）
預處理
先將「測得的時間」做一些預處理，例如「過濾掉極端大值」。目的是盡量讓後續的統計檢定更穩定，更能聚焦在「執行時間是否與輸入有關」。
統計檢定
最常用的是 Welch’s t-test：檢驗「這兩組測量（固定輸入 vs. 隨機輸入）」在平均值上是否具有顯著差異。
若統計結果顯示差異顯著，代表程式的執行時間很有可能因輸入而有所不同；也就是說它「可能不是真正的常數時間」。
若未觀察到顯著差異，則在某個信心水平下，可以暫時認為程式在該平台可能是常數時間 — 但要注意，這是統計檢定，並不是絕對保證。

lab 0

在此作業中，使用的是Welch's t-test的方法。

輸入為兩類的執行時間:

執行時間 = 結束時間 - 起始時間

static void differentiate(dudect_ctx_t *ctx)
{
    for (size_t i = 0; i < N_MEASURES; i++)
        ctx->exec_times[i] = ctx->after_ticks[i] - ctx->before_ticks[i];
}

類 1 :

X_{1}, X_{2}, \dots, X_{n_{1}}

(固定輸入， class = 0)
類 2 :

Y_{1}, Y_{2}, \dots, Y_{n_{2}}

(隨機輸入， class = 1)

m2 為累積平方和偏差。
n 為每組的樣本數。

void t_init(t_context_t *ctx)
{
    for (int class = 0; class < 2; class ++) {
        ctx->mean[class] = 0.0;
        ctx->m2[class] = 0.0;
        ctx->n[class] = 0.0;
    }
    return;
}

分別計算平均值:

\bar{X} = \frac{1}{n_{1}} \sum_{i = 1}^{n_{1}} X_{i}, \bar{Y} = \frac{1}{n_{2}} \sum_{j = 1}^{n_{2}} Y_{j}

用 Welford’s method 線上更新累積平方和偏差(用來計算變異數):

delta :

δ = x - \bar{m}

新的平均：

{\bar{m}}^{'} = \bar{m} + \frac{δ}{n}

更新

M 2^{'} = M 2 + δ \times (x - {\bar{m}}^{'})

void t_push(t_context_t *ctx, double x, uint8_t class)
{
    assert(class == 0 || class == 1);
    ctx->n[class]++;

    /* Welford method for computing online variance
     * in a numerically stable way.
     */
    double delta = x - ctx->mean[class];
    ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
    ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
}

計算 Welch’s t-test 的 t 線上統計量

計算變異數:

$s_{X}^{2} = \frac{m 2 [0]}{n [0] - 1}, s_{Y}^{2} = \frac{m 2 [1]}{n [1] - 1} .$
計算Welch’s t-test 的 t 值:

$t_{online} = \frac{{\bar{X}}_{(so far)} - {\bar{Y}}_{(so far)}}{\sqrt{\frac{s_{X}^{2}}{n_{1}} + \frac{s_{Y}^{2}}{n_{2}}}}$

若

∣ t ∣

足夠大（大於一個臨界值），可拒絕「兩組平均相等」的假設（null hypothesis），表示兩組數據之間具有顯著差異。

在程式應用中，程式會不斷收集新測量值，對固定輸入 (class=0) 與隨機輸入 (class=1) 分別計算目前累積下來的平均與變異數。每次更新後，都可立刻算出一個新的 t-value。

隨著測量次數

n 1 + n 2

的增加，

| t_{o n l i n e} |

是否越來越大。若是越來越大且超過門檻，代表確實存在顯著差異；若始終維持在小範圍，則暫時無法排除它是常數時間（或差異極微小，以至需要更多測量才能看出）。

double t_compute(t_context_t *ctx)
{
    double var[2] = {0.0, 0.0};
    var[0] = ctx->m2[0] / (ctx->n[0] - 1);
    var[1] = ctx->m2[1] / (ctx->n[1] - 1);
    double num = (ctx->mean[0] - ctx->mean[1]);
    double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
    double t_value = num / den;
    return t_value;
}

判斷是否為常數時間

藉由比較算出來的

t

值與判定常數時間的臨界值來決定是否為常數時間。

臨界值 :

/* threshold values for Welch's t-test */
enum {
    t_threshold_bananas = 500, /* Test failed with overwhelming probability */
    t_threshold_moderate = 10, /* Test failed */
};

判定是否為常數時間 :

double max_t = fabs(t_compute(t));
/* Definitely not constant time */
if (max_t > t_threshold_bananas)
    return false;

/* Probably not constant time. */
if (max_t > t_threshold_moderate)
    return false;

/* For the moment, maybe constant time. */

使程式碼具備 percentile 的處理

在原本的 lab 0 中是不具備 percentile 的處理，而 percentile 在原作者的 dudtect 中的應用是為了去除極端大值，讓後續的統計檢定更穩定。
所以在這個部份我將 percentile 的應用加入至此作業中。

Percentile（百分位數）在統計學中指的是「將一組數值依大小排序之後，取出某一百分比位置所對應的數值」。

例如：
第 50 個百分位數（50th percentile, 也稱為中位數）就是那個使得「有一半（50%）的樣本值都小於等於它」的數值。

而此論文的方法是計算多個百分數位(目前設定為100)，並將這些百分數位設為不同的閥值，每個閥值會去儲存低於這個百分數位的執行時間。如此就等於同時做100 種裁剪門檻。
之所以要這麼設定是因為 :
某些門檻太低時，將捨棄掉大量量測，可能很快收斂於可檢測出差異；也可能不夠樣本數。
某些門檻太高時，捨棄量偏少，不容易清除雜訊。
因次，會去進行挑選哪個百分位數是最適合的。

而此文挑選的方法是去選擇哪個百分位能夠算出最大的

t

值 :

static ttest_ctx_t *max_test(dudect_ctx_t *ctx) {
  size_t ret = 0;
  double max = 0;
  for (size_t i = 0; i < DUDECT_TESTS; i++) {
    if (ctx->ttest_ctxs[i]->n[0] > DUDECT_ENOUGH_MEASUREMENTS) {
      double x = fabs(t_compute(ctx->ttest_ctxs[i]));
      if (max < x) {
        max = x;
        ret = i;
      }
    }
  }
  return ctx->ttest_ctxs[ret];
}

而在這個 dudect 的程式碼中會用 percentile() 來計算百分位數並回傳至prepare_percentiles() 裡的 ctx->percentiles[i] 儲存起來。

跟 lab 0 不同的是 update_statistics() 也需要更新閥值內的成員:

int64_t difference = ctx->exec_times[i];
// 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]);
    }
}

另一個重點改動是會將 lab 0 實施的主程式增加預處理 prepare_percentiles() 後才 update_statistics()

if (first_time) {
    // throw away the first batch of measurements.
    // this helps warming things up.
    prepare_percentiles(ctx);
} else {
    update_statistics(ctx);
    ret = report(ctx);
}

經過這些改動後遍能夠使原本的 lab 0 有去掉極端大值的功能了。