2025q1 Homework1 (lab0)

contributed by <JimmyChongz>

作業書寫規範:

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

安裝 Ubuntu 24.04

在 Windows 11 安裝 Ubuntu 24.04.1 LTS

環境

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 24.04.2 LTS
Release:        24.04
Codename:       noble

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

queue.c 的疑難雜症

q_new

commit: ab7b291

我沒注意記憶體分配失敗的處理。

記憶體配置不能保證成功，而是可能返回 null 指標。若直接使用 malloc 回傳的值而不檢查分配是否成功，則有可能會造成 segmentation fault on the null pointer dereference。

q_free

commit: 1f7493b

怎麼完整 free 掉整個 Linked List 而不會發生 Memory leak ?

使用迴圈來釋放鏈結串列中所有的節點。另外，若 struct 中含有動態配置的記憶體指標，則要先 free 該指標所指向的記憶體空間，再 free 該結構體。還有 head 的結構與節點不同，head 並沒有 element_t 結構，故只需單獨 free。

free(list_entry(tmp, element_t, list)->value);
free(list_entry(tmp, element_t, list));

善用 Linux kernel API q_release_element

commit: 84ee2f1

q_insert

commit: a202b1e

為什麼不能直接 newNode->value = s ？

Ans: 這樣只會讓 newNode->value 指向 s，但不會複製內容，若之後修改 s，那 newNode->value 也會跟著改變。例如：

char *s;
char str[] = "Hello World!";
s = str;
printf("s: %s, str: %s\n", s, str);
strcpy(str, "123");
printf("s: %s, str: %s\n", s, str);

// output
s: Hello World!, str: Hello World!
s: 123, str: 123

又或者當 s 被釋放（即 free(s)），而 s 與 newNode->value 都指向同一塊記憶體空間，此時 newNode->value 就會變成 dangling pointer。如果之後程式碼使用 newNode->value，就會出現不可預期的錯誤。

那怎麼解決？

解決方法：使用 strdup 或 strncpy 來賦值給 newNode->value

• strdup(s) :
  複製傳入參數 s 指向的字串到一塊新的記憶體空間。意思就是說此函數會先 malloc s 指向字串的 size，再透過 memcpy 將 s 指向的字串複製到先前 malloc 的記憶體空間。
  

• strncpy(str1, str2, n) :
  將 str2 的前 n 個字元複製到 str1 中。要注意預留一個 byte 的空間給 null character。
  

那 strdup 跟 strncpy 用哪個會比較好？

strdup 比較好，因為 strdup 會自動分配記憶體，而 strncpy 只是單純複製字串，但仍然需要手動分配記憶體，例如：

newNode->value = malloc(strlen(s) + 1);  // 需要自己分配記憶體
strncpy(newNode->value, s, strlen(s));
newNode->value[strlen(s)] = '\0';  // 確保結尾有 '\0'

q_remove

commit: a202b1e

為什麼參數有 char *sp 跟 size_t bufsize ?

• sp 是一個指向字串緩衝區的指標，若不為 NULL，則函式應將被移除元素之成員 (即 node->value) 複製到這個字串緩衝區。
  用途： 讓使用者可以立刻取得移除節點所儲存的字串，而不需透過訪問回傳的 element_t 結構體取得。
  如果 sp == NULL： 代表 呼叫者 不需要移除節點所儲存的字串，只需要刪除節點並回傳該元素的指標。

• bufsize 是 sp 的最大可用空間（包含 \0 ），避免 緩衝區溢位（buffer overflow）。
  用途： 確保 strncpy() 不會超過 sp 的範圍，並手動添加 \0 來確保字串結尾安全。

q_delete_mid

commit: a8f4303

基於下方的程式碼 deleteMiddle 還有沒有更好的寫法？

int len = 0;
struct ListNode **indirect = &head;
while (*indirect) {
    len++;
    indirect = &(*indirect)->next;
}
int pos = len / 2;
len = 0;
indirect = &head;
while (len != pos) {
    len++;
    indirect = &(*indirect)->next;
}
*indirect = (*indirect)->next;

利用「快慢指標」，讓 fast 指標以兩倍速在遍歷整個鏈結串列，slow 則以一倍速遍歷鏈結串列，當 fast 完成遍歷整個鏈結串列時，slow 指標剛好會停在中間的位置。例如：

struct ListNode *fast = head;
struct ListNode *slow = head;
while (fast && fast->next) {
    fast = fast->next->next;
    slow = slow->next;
}
slow = slow->next;

q_delete_dup

commit: a8f4303

思路：用巢狀迴圈，外層迴圈用於檢測兩兩節點的值是否相同，若相同則進入第二層迴圈，在第二層迴圈中刪除重複的節點。

還有改進空間嗎？

用 Hash Table …

q_swap

commit: 244dc15

思路：利用 list_for_each(cur, head) 去遍歷整個鏈結串列，再透過 list_move(cur, cur->next)，由此一來每一輪的 cur->next 都會被插入到 cur 前面，又執行完 list_move 後，cur 無形中會自動跑到下一個節點，如下圖所示：

依照上述做法會出現問題，當鏈結串列長度為奇數時，會多換一次，導致最後一個節點被移到最前面，怎麼解決？

多加一個判斷式，當 cur->next == head 時，就 break迴圈，避免發生交換即可。

commit: 8904527

當完成 q_reverseK 時，即可將 q_swap 寫成：

q_reverseK(head, 2);

q_reverse

commit: 244dc15

作法：利用 list_for_each_safe(cur, next, head) 去遍歷整個鏈結串列，再透過 list_move(cur, head) 將每一個點都重新插入 head，即可完成 reverse 操作。

q_reverseK

commit: fcd4d2c

作法：先得出鏈結串列的長度 count，當 count 大於 K 時，準備 prev 跟 next 兩個輔助指標做 Reverse K-group，做完後要 count -= k。

q_descend

commit: 13ffad8

我最一開始的思路是現找出串列中的最大值 max，再利用遞迴找出 max->next 子串列的最大值回傳給 max->next，如下程式碼所示，但會 Time out 時間複雜度為

$O(n^2)$ 等級，表示還有更好的做法。怎麼做？

用兩個指標來進行反向遍歷：

• max：追蹤目前反向遍歷過程中遇到的最大值節點（初始指向 head->prev，即尾部節點）。
• cur：負責遍歷 max 前方的節點（初始指向 max->prev ）。

遍歷過程：

• 如果 cur 所指的值小於或等於 max，則刪除該節點。
• 如果 cur 所指的值大於 max，則更新 max 為 cur，確保 max 始終指向目前反向遍歷過程中遇到的最大值。
• 移動 cur 到 prev，繼續遍歷。

如此一來就可以有效地保留遞減序列的節點，並刪除不符合條件的節點。

q_ascend

commit: 13ffad8

作法與 q_descend 相似，一樣是透過反向遍歷的思路，差別在遍歷過程的條件，q_ascend 要刪除大於等於 min 的值，若 cur 所指的值小於 min，則更新 min 為 cur，以確保 min 始終指向目前反向遍歷過程中遇到的最小值。如此一來就可以有效地 保留遞增序列的節點，並刪除不符合條件的節點。

q_sort

commit: e5f1033

我原先參考了 第二周測驗一 的 list_quicksort 實作，我將其轉換成 Linux kernel 風格的鏈結串列：

struct list_head list_less, list_greater;
element_t *pivot;
element_t *item = NULL, *is = NULL;

INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);

pivot = list_first_entry(head, element_t, list);
list_del(&pivot->list);

if (!descend) {
    list_for_each_entry_safe (item, is, head, list) {
        if (strcmp(item->value, pivot->value) < 0)
                list_move_tail(&item->list, &list_less);
        else
                list_move_tail(&item->list, &list_greater);
    }

    q_sort(&list_less, false);
    q_sort(&list_greater, false);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
}

使用 quick sort 為什麼會超時？

因為在 Worst Case 的情況下，Quick Sort 的時間複雜度會來到

$O(n^2)$ 等級。例如在全部節點值都相同的情況下，使用 Singely-Linked-List 示意：

令

$n$ 表示傳入的串列長度，第一個節點當作 pivot

再將剩餘的

$n-1$ 個節點做分割，比 pivot 小的節點插入到 list_less 串列中，反之則插入 list_greater 串列中。在此例中，當執行完 list_for_each_entry_safe 迴圈後，並無法分割串列，因為全部的節點都相同，因此都會被插入到 list_greater 中，還是得到長度為

$n-1$ 的子串列。

再遞迴呼叫 q_sort，所以都是透過設 pivot 在做分割串列，每回合只切一個節點，由此可推得時間函數式為

$T(n)=T(n-1)+cn$ ，其中

$c$ 為常數，

$cn$ 表示執行 list_for_each_entry_safe 迴圈的時間，經化簡後得

$T(n)=O(n^2)$

$$\begin{array}{c}T(n)=T(n-1)+cn\\ =T(n-2)+n+(n-1)\\ =T(n-3)+cn+c(n-1)+c(n-2)\\ ......\\ =T(0)+cn+c(n-1)+c(n-2)+...+c\\ \because T(0)=0\\ \therefore T(n)=c[n+(n-1)+(n-2)+...+1]\\ =\frac{cn(n-1)}{2}=O(n^2)\end{array}$$
故無法滿足時間複雜度

$O(nlogn)$ 的要求。

如何優化？

改用 Merge Sort ，因為不管在什麼情況下，時間複雜度皆為

$O(nlogn)$ 等級。

參考 Linked List Sort 之 Merge Sort

這樣寫 Merge Sort，會出現 Segmentation Fault，是什麼問題？

if (!head || list_empty(head) || list_is_singular(head))
        return;

struct list_head *fast = head->next;
struct list_head *slow = head->next;

while (fast != head && fast->next != head) {
    fast = fast->next->next;
    slow = slow->next;
}

LIST_HEAD(left);
list_cut_position(&left, head, slow);

q_sort(head, descend);
q_sort(&left, descend);

struct list_head *merged = mergeTwoLists(&left, head, descend);
INIT_LIST_HEAD(head);
list_splice(merged, head);

使用 Valgrind 分析，執行以下命令：

$ valgrind -q --leak-check=full ./qtest -v 3 -f traces/trace-04-ops.cmd

發現是 Stack Overflow ，看起來是第 248 列的遞迴沒寫好。

cmd> sort
==4012223== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4012223== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4012223== Can't extend stack to 0x1ffe8010b8 during signal delivery for thread 1:
==4012223==   no stack segment
==4012223== 
==4012223== Process terminating with default action of signal 11 (SIGSEGV)
==4012223==  Access not within mapped region at address 0x1FFE8010B8
==4012223== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==4012223==    at 0x1104B2: q_sort (queue.c:248)

先用簡單的例子來追蹤程式碼：

在執行完 while loop 後：

TODO: Explain how list_cut_position(&left, head, slow) exactly do …

將 head 到 slow (包含 slow) 的節點接到 left 上，若 left 不為空的話，則會將其原本的節點都覆蓋過去，即原本節點都會被 "Remove"。

在執行完 list_cut_position(&left, head, slow); 後：

此時，再執行 q_sort(&left, descend); 時，會發現 left 就是原本的 head，根本沒切到，導致無限遞迴，造成 Stack Overflow !

修正：

把 list_cut_position(&left, head, slow); 修改即可。

- list_cut_position(&left, head, slow);
+ list_cut_position(&left, head, slow->prev);

接著，Merge Sort 會用到 merge_two_lists 輔助函數，用來合併由 q_sort 函數切割成兩半的子串列，比較特別的是要「 做 ascending / descending 的判斷 」。其中，為了要確保是 Stable Sorting，因此當遇到重複的數字時應保持原排列順序，以 ascending 為例，當目前左半子串列的值小於等於當前右半子串列的值時，應優先合併左半子串列的值。

q_merge

commit: 3e931f4

先了解 queue_contex_t 結構體定義：

思路：首先，新增一個指標指向第一條 queue，作為合併的目標。接下來，將其餘所有 queue 依序合併到第一條 queue 中。我使用 list_for_each_entry_safe 遍歷從第二條開始的每一條 queue，並透過 merge_two_lists 將當前遍歷到的 queue 合併至第一條 queue。同時，需即時更新第一條 queue 的 size。當所有 queue 都合併完成後，回傳第一條 queue 的最終 size。

如何驗證 queue.c 實作的 method？

在終端機輸入 make test 後，會發生什麼？

實際就是執行 scripts/driver.py 這個 Python 程式。快速瀏覽發現這個自動評分程式就是將 traces/trace-XX-CAT.cmd 這樣形式的命令序列提供給 qtest.c 內建的命令直譯器，然後依據給定的檢驗標準，逐一判定該給測試者多少分數。

shuffle 實作

q_shuffle

commit: 484b7ea

參考 你所不知道的 C 語言：Fisher–Yates shuffle 演算法實作，透過 Pencil-and-paper method 對 Linux Kernel 的環狀雙向鏈結串列進行隨機洗牌，每次隨機選取一個節點並將其移動到 new 串列，直到所有節點都被移動。

do_shuffle

commit: 484b7ea

在 qtest.c 中新增 do_shuffle 函數，參考 do_swap 寫法，將 q_swap(current->q); 改成 q_shuffle(current->q);。詳細流程我還要弄清楚。

分析 q_shuffle 是否 Uniform distribution

透過統計方法驗證 shuffle，利用作業提供的測試檔測試，結果如下：

$ python3 test_shuffle.py 
Expectation:  41666
Observation:  {'1234': 70538, '1243': 5611, '1324': 33258, '1342': 13650, '1423': 15627, '1432': 5872, '2134': 79863, '2143': 82082, '2314': 50809, '2341': 31226, '2413': 17591, '2431': 54725, '3124': 25432, '3142': 66487, '3214': 52806, '3241': 7783, '3412': 39009, '3421': 62571, '4123': 46892, '4132': 35171, '4213': 85991, '4231': 7836, '4312': 58659, '4321': 50511}
chi square sum:  363008.4137186195

測試出來感覺不太均勻，無法拒絕的虛無假說，需要調整。
TODO: 搞懂 Pearson's chi-squared test

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

參考作業提供的 論文重點提示

I. 引言

從引言的敘述中，推測 Timing Leakage 指的是程式執行時間與秘密數據之間的關聯性，導致攻擊者可以透過測量加密實作的執行時間來推測出機密資訊，例如：在 1996 年 Paul Kocher 發現 RSA 私鑰解密的運算執行時間取決於私鑰位元值，所以攻擊者就可以透過測量解密運算的執行時間來逐步恢復私鑰。這也是為什麼要探討 is my code constant time 的重要原因，以確保程式碼在不同輸入條件下的執行時間是固定的，以減少被 side-channel attacks 的可能性。

什麼是 Compiler Flag ?

程式語言編譯之參數，包括最佳化參數（eg. -O0（無最佳化), -O1（基本最佳化) etc.)、除錯與錯誤檢查參數等等。

詳細參考：Compiler Flags and Options

II. Our Approach

作者使用動態偵測。

lab0-c 中的 Welch's test 測試項目

參考 課程作業：Welch’s t-test

用 GBD backtrace test_constant:

Macro 中的 ## 是什麼？

參考規格書對 ## operator 的敘述：

得知 ## 是在巨集中的「token 連接符號」，在 C 的預處理器中，## 可以將兩個 token 合併成一個 token，當參數為空時，C 預處理器會插入 placemarker，它最終會被刪除，不會影響程式碼的執行結果，例如：

#include <stdio.h>
#define A(x) Value_##x
#define B(x, y) x##y

int main(int argc, const char * argv[]) {
    int A(1) = 9;
    int A(a) = 21;
    printf("%d, %d\n", Value_1, Value_a);
    
    int B(a, 1) = 21;
    int B(b, 1) = 9;
    printf("%d, %d\n", a1, b1);
    printf("%d\n", B(123, )); // 空參數由 placemarker 代替
}

//output
9, 21
21, 9
123
Program ended with exit code: 0