2025q1 Homework1 (lab0)

contributed by < PigeonSir >

作業書寫規範:

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

$ lscpu
架構：                                x86_64
CPU 作業模式：                         32-bit, 64-bit
Byte Order:                          Little Endian
Address sizes:                       39 bits physical, 48 bits virtual
CPU(s):                              6
On-line CPU(s) list:                 0-5
每核心執行緒數：                        1
每通訊端核心數：                        6
Socket(s):                           1
NUMA 節點：                           1
供應商識別號：                         GenuineIntel
CPU 家族：                            6
型號：                                158
Model name:                          Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz
製程：                                10
CPU MHz：                            2800.000
CPU max MHz:                         4000.0000
CPU min MHz:                         800.0000
BogoMIPS:                            5599.85
虛擬：                                VT-x
L1d 快取：                            192 KiB
L1i 快取：                            192 KiB
L2 快取：                             1.5 MiB
L3 快取：                             9 MiB
NUMA node0 CPU(s)：                   0-5

修改 queue.c

q_new

分配 list_head 的空間，再透過 INIT_LIST_HEAD 將 prev 和 next 指向自身。

struct list_head *q_new()
{
    struct list_head *obj = malloc(sizeof(struct list_head));
    if (!obj)
        return NULL;
    INIT_LIST_HEAD(obj);
    return obj;
}

後來加入對 malloc 失敗時做處置， c 語言規格書 ISO/IEC 9899:2024 7.24.3 節的第一段提到

If the space cannot be allocated, a null pointer is returned.

在後續的實作中遇到 malloc 都要這麼做

q_insert_head/q_insert_tail

commit d95ee65

再新增節點時需要字串的複製，作業解說提到的 strcpy 屬於危險的操作，原因如下

The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.
CERN Compter Security

故選擇使用 strncpy ，需注意當愈複製的長度小於目標地址配置的大小時會自動補 '\0' ，反之則會被截斷，所以複製完後再強制將最後一個字節設為 '\0'

constant time 測試

後續發現以上方法未能通過 constant time 測試，初步推測為 strlen() 和 strncpy() 造成的，因為這兩個函式會隨著字串的長度增加執行時間

在 csappE3 5.4 節中提到 strlen() 對執行時間的影響，並給出 strlen() 的簡單版本如下：
size_t strlen(const char *s)
{
    long length = 0;
    while (*s != '\0') {
        s++;
        length++;
    }
    return length;
}
而觀看手冊中 strncpy 的實現方式，其執行時間亦會使用 strlen，故推測這兩個函式造成 insert_head 和 insert_tail 無法通過 constant time 測試。

待後續閱讀論文以及研究 simulaion 的測試條件後再著手改善

精簡程式碼

commit 6530b15

研究關於字串複製的方式，發現 strdup 可以更精簡程式碼，但還是無法通過 constant time 的測試

queue_del_mid

commit 785ea1b

參考你所不知道的 C 語言: linked list 和非連續記憶體當中對於快慢指標的操作，在節點個數 $n$ 為偶數時移除第 $n / 2 + 1$ 個節點

圖解流程

前置檢查

如果 head 為 NULL 或 queue 為空，直接返回 false。
初始化 temp 為 head->next 的指標的指標，作為慢指標。
初始化 fast 指標為 head->next，作為快指標。
圖片中為了畫面整潔暫忽略 head->prev 和 node5->next

進行迴圈

在迴圈內部更新 temp : *temp 為下一個節點的記憶體位置，故 temp = &(*temp)->next 會將 temp 指向下一個節點的 next
每一輪執行完更新 fast : 執行 fast = fast->next->next 讓 fast 指向下下一個節點
fast 為最後一個節點或 head 時跳出迴圈
圖片中 fast 和 temp 的下標 0, 1, 2 代表各輪執行後的狀態

移除節點

此時 temp 指向 node2 的 next，所以移除的節點是 *temp，但要先定義另一個節點 del 指向 *temp ，才能使用 list_del 和 q_release_element 移除 del

q_swap, q_reverse, q_reverseK

commit b99d99b

在課堂上有提到 q_swap 和 q_reverse 都只是 q_reverseK 的特例，實現 q_reserveK 後 q_swap 和 q_reserve 分別只要將 K 代入 2 和 queue size 即可

void q_swap(struct list_head *head) {
    q_reverseK(head, 2);
}
void q_reverse(struct list_head *head) {
    q_reverseK(head, q_size(head));
}

mergeTwo

commit 9b1be79

新增函式 mergeTwo 以合併兩個已經排序完成的 queue ，在 q_sort 和 q_merge 中都需要使用到 mergeTwo ，參考教材中的實作方式合併兩個斷開且單向的鏈結串列並在過程中僅維護 next 指標，升序排列的合併流程如下

圖解流程

輸入參數
struct list_head * L, R : 分別指向兩個生序排列的鍊結串列的第一個節點
bool descend : 為 true 時使用降序合併，此範例中為 false
初始化

temp 最初為 NULL，它將存儲合併後的新鍊結串列的起始節點。
indirect 是一個指標的指標，用來追蹤新鏈表的尾端，以便逐步建立新的鏈表。

進入迴圈

node 是指標的指標，其值為 &left 或 &right，指向該輪中應該接到 indirect 上的節點
根據 strcmp 的結果選擇節點，範例中 strcmp 結果為負，因此在升序排列的情況下，node 和 indirect 指向 L
首次執行時，indirect 存放的是 temp 的記憶體位置，因此 *indirect = *node 等價於 temp = L，後續操作中 temp 的值將不再改變

迴圈中更新指標

先更新 indirect 指向合併完的節點的 next 的記憶體位置
迴圈結束後再更新 *node （即更新 L ）指向該鍊結串列的下一個節點

接上剩餘的節點

反覆合併到 L 或 R 為 NULL 後跳出迴圈

最後將 L 或 R 中剩餘的節點接上 indirect 並返回 temp

q_merge

commit49bd087

q_merge 會用到結構體 queue_contex_t ，其中保存了 queue 的 size, id 和 queue 的 head ，並透過 chain 鍊結。

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

含有兩個 queue 的示意圖如下

先透過最容易實現的方法實做，將每一個 queue 都和第一個 queue 執行 mergeTwo

頭尾合併

研讀並引入 lib/list_sort.c

list_srot 內包含三個函式： merge, merge_final 和 list_sort ，將這些函式修改後加入 queue.c

研讀並加入 list_sort

unlikely

#ifndef likely
#define likely(x)   __builtin_expect(!!(x), 1)
#endif

#ifndef unlikely
#define unlikely(x) __builtin_expect(!!(x), 0)
#endif

比較函式

在 list_sort.c 中，cmp 參數是一個比較函式的指標，被定義於 list_sort.h：

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(
    void *, const struct list_head *, const struct list_head *);

上述程式碼定義了一種函式指標類型 list_cmp_func_t 指向一個接收三個參數並回傳 int 的函式：

attribute((nonnull(2,3))) 指示編譯器第二和第三個參數不能為 NULL
void *：用來傳遞額外資訊
兩個 const struct list_head *：指向被比較的節點

這樣做是為了在呼叫 list_sort() 時，傳遞不同的比較函式來決定排序方式。而我選擇直接在 queue.c 中定義比較函式為一個全域的函式，直接在排序的過程中呼叫它，參考 list_sort.c 中對於比較函式的描述：

The comparison function cmp must return > 0 if a should sort after b (”a > b” if you want an ascending sort), and <= 0 if a should sort before b or their original order should be preserved. It is always called with the element that came first in the input in a, and list_sort is a stable sort, so it is not necessary to distinguish the a < b and a == b cases.

The comparison function must adhere to specific mathematical properties to ensure correct and stable sorting: - Antisymmetry: cmp(a, b) must return the opposite sign of cmp(b, a). - Transitivity: if cmp(a, b) <= 0 and cmp(b, c) <= 0, then cmp(a, c) <= 0.

This is compatible with two styles of cmp function: - The traditional style which returns <0 / =0 / >0, or - Returning a boolean 0/1. The latter offers a chance to save a few cycles in the comparison (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).

考量 cmp (a, b)

回傳值 <= 0 : a 排在 b 之前
回傳值 > 0 : a 排在 b 之後

當 a > b

升序時 (ascending) 要回傳正值
降序時（descending) 要回傳零或負值

若先計算 ret = a - b ，升序時回傳 ret (正數) 因為 a 要排在後面，而降序時回傳 -ret (負數)，實作細節如下

int cmp (struct list_head *a, struct list_head *b, bool descend) {
    element_t *A = list_entry(a, element_t, list);
    elsment_t *B = list_entry(b, element_t, list);
    int ret = strcmp(A->value, B->value);
    return descend ? -ret : ret
}

list_sort

修改 qtest.c

commit af0ee40

在 console_init() 中新增命令 listSort ，並新增函式 do_listSort ，其內容和 do_sort 相同。

ADD_COMMAND(listSort, "");

比較執行時間

撰寫比較兩個排序法執行時間用的 command file

option fail 0
option malloc 0
new
ih RAND <10000 50000 100000 500000>
time
<listSort / sort>
time
reverse
time
<listSort / sort>
time
free

此測試會對四種不同數量的元素（10,000 / 50,000 / 100,000 / 500,000）執行排序，並計算：

第一次排序的時間 (隨機插入)
反轉 queue 後再次排序的時間

測試結果如下：

第一次排序

資料數	q_sort	list sort
10000	0.0044	0.0034
50000	0.0454	0.0362
100000	0.1230	0.090
500000	0.7658	0.5580

反轉後排序

資料數	q_sort	list sort
10000	0.0028	0.0012
50000	0.0530	0.0418
100000	0.1442	0.1052
500000	0.9460	0.6144

發現 list sort 在各個資料數下都快於 q_sort

使用 perf

接下來運用效能分析工具 pref 分析此效能
，執行 500000 個元素的排序五次，監控 instructions, cycles 和 branches

$ sudo perf stat --repeat 5 -e instructions,cycles,branches ./qtest -f traces/traceTest.cmd

list sort

 Performance counter stats for './qtest -f traces/traceTest.cmd' (5 runs):

     4,092,947,424      instructions              #    0.51  insn per cycle           ( +-  0.08% )
     8,109,857,850      cycles                                                        ( +-  0.38% )
       554,107,769      branches                                                      ( +-  0.14% )

            2.1554 +- 0.0183 seconds time elapsed  ( +-  0.85% )

q_sort

 Performance counter stats for './qtest -f traces/traceTest.cmd' (5 runs):

     4,134,313,258      instructions              #    0.43  insn per cycle           ( +-  0.02% )
     9,322,393,713      cycles                                                        ( +-  1.02% )
       577,098,583      branches                                                      ( +-  0.02% )

            2.5141 +- 0.0267 seconds time elapsed  ( +-  1.06% )

從 cycles 來看，q_sort 需要更多的 CPU cycle，且執行時間比 list sort 長。

cmp 呼叫次數

為了分析兩種排序法進行比較的次數，更新 q_sort 的比較方式為呼叫 cmp

commit 4c2ac8b

透過 perf probe 加入觀察點於 cmp

$ sudo perf probe -x ./qtest cmp

但加入觀察點後執行 record 發現次數為 0

$ sudo perf record -e probe_qtest:cmp -aR ./qtest -f traces/traceTest.cmd
... ...
$ sudo perf script | grep cmp | wc -l
0

發現 cmp 的呼叫次數為 0，表示 perf probe 未能成功攔截 cmp，需要進一步調查問題可能的原因

在 qtest 提供新的命令 shuffle

研讀論文＆ simulaion 的測試條件

研讀 Dude, is my code constant time?

該論文介紹了名為 dudect 的工具，主要用來檢測某段程式碼是否以 constant-time 執行，有別於傳統檢測方式，dudect 採用的是「統計分析」的方法而非傳統的「靜態分析」，具體步驟如下：

step 1 : Measure execution time

定義輸入類別 (class)
第一類 fix：輸入固定為某個常數值。
第二類 random ：輸入為每次隨機選擇的數據。
使用 CPU 週期計數器或計時器測量執行時間
隨機選擇輸入類別，降低環境影響

step 2 : Apply post-processing

過濾異常數據（Cropping），避免系統中斷、測量誤差影響分析結果
應用高階預處理（Higher-order preprocessing），利用更精細的統計方法增強時間洩漏的檢測能力

step 3 : Apply statistical test

使用統計檢定來驗證「兩組執行時間分佈是否相同」
t-test & Non-parametric tests

simulation

在 qtest.c 中函式 queue_insert 和 queue_remove 都會依據全域變數 simulation 決定是否進行 constant time 檢查，且檢查都是發生在實際插入/移除節點之前，檢查方式如下

// in queue_insert
bool ok = pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const();
// in queue_remove
bool ok = pos == POS_TAIL ? is_remove_tail_const() : is_remove_head_const();

定義於 dudect/constant.h

#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)

/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _

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

2025q1 Homework1 (lab0)

開發環境

修改 queue.c

q_new

q_insert_head/q_insert_tail

constant time 測試

精簡程式碼

queue_del_mid

圖解流程

q_swap, q_reverse, q_reverseK

mergeTwo

圖解流程

q_merge

頭尾合併

研讀並引入 lib/list_sort.c

研讀並加入 list_sort

unlikely

比較函式

list_sort

修改 qtest.c

比較執行時間

使用 perf

cmp 呼叫次數

在 qtest 提供新的命令 shuffle

研讀論文 ＆ simulaion 的測試條件

研讀 Dude, is my code constant time?

step 1 : Measure execution time

step 2 : Apply post-processing

step 3 : Apply statistical test

simulation

Read more

2025q1 Homework2 (quiz1+2)

2025q1 Homework1 (ideas)

2024q1 Homework2 (quiz1+2)

研讀論文＆ simulaion 的測試條件