2025q1 Homework1 (lab0)

contributed by < EricccTaiwan >

作業書寫規範:

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

$ 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):                 8
On-line CPU(s) list:    0-7
Vendor ID:              GenuineIntel
Model name:             Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
CPU family:             6
Model:                  142
Thread(s) per core:     2
Core(s) per socket:     4
Socket(s):              1
Stepping:               11
CPU(s) scaling MHz:     92%
CPU max MHz:            3900.0000
CPU min MHz:            400.0000
BogoMIPS:               3600.00
Virtualization:         VT-x
L1d cache:              128 KiB 
L1i cache:              128 KiB 
L2 cache:               1 MiB 
L3 cache:               6 MiB
NUMA node0 CPU(s):      0-7

在作業開發中，我使用 oh-my-zsh 做為主要 Shell 環境，有許多實用的功能(e.g. zsh-autosuggestions)和美觀的 UI 界面！

實作 queue.c

`q_new`

Commit 7446f52

宣告一個指標 new_qhead，其型別為 struct list_head *，並使用 malloc 分配 sizeof(struct list_head) 大小的記憶體空間。
使用 INIT_LIST_HEAD 初始化新分配的記憶體，確保其被正確設置為一個空的鏈結串列。

`q_free`

Commit 0e45a1f

用 list_for_each_safe 走訪鏈結串列，並依序從鏈結串列中移除和釋放記憶體空間。起初沒有 list_del 下，make test是沒有問題的 (現在也是沒有問題)，當下沒有多想，越往下寫越對於 free 感到疑惑，free 可以在 harness.h中看到被巨集定義成 test_free ，點進去看能發現 test_free 其實是在釋放 block_element_t ( malloc 也是分配 block_element_t )，可以看到下方程式碼， test_free 是將欲釋放的 block_element_t 移出其所在的鏈結串列。

但我這邊的疑惑是，free 並沒有將 list_head 節點移出其所在的佇列中，為什麼能還順利的釋放？ TBD…

/* Unlink from list */
block_element_t *bn = b->next;
block_element_t *bp = b->prev;
if (bp)
    bp->next = bn;
else
    allocated = bn;
if (bn)
    bn->prev = bp;

free(b);

void q_free(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *cur, *tmp;
    list_for_each_safe (cur, tmp, head) {
+       list_del(cur);
        free(list_entry(cur, element_t, list)->value);
        free(list_entry(cur, element_t, list));
    }
    free(head);
}

`q_insert_head` & `q_remove_head`

Commit a4cdde9

使用 malloc 分配大小為 element_t 的記憶體空間，並利用 C 標準函式庫的 strdup 複製字串，將其存入 element_t 的 value 成員中。
接著，透過 INIT_LIST_HEAD 初始化鏈結節點，確保其鏈結狀態正確，最後使用 list_add 或 list_add_tail，分別將新建立的 element 插入至佇列的首端或尾端。

`q_remove_head` & `q_remove_tail`

Commit 2f3213a

使用 C 標準函式庫的 snprintf 來安全地將刪除的 element_t->value 複製到 sp ，避免緩衝區溢位 (buffer overflow)，並確保字串正確終止 (\0)。

`q_size`

Commit 4769b2c

利用 list_for_each 走訪鏈結串列並計算節點個數。

`q_delete_mid`

Commit 551ce22

利用快慢指針找出中間的節點，從其鏈結串列中移除和釋放記憶體空間。

`q_delete_dup`

Commit 66e7e15

使用 list_for_each_safe 來走訪整個鏈結串列，確保在刪除節點時不會影響迴圈的執行。如果當前節點的value與下一個節點的value相同，則刪除當前節點，並標記 dup=true 。在下一次迴圈中，續檢查並刪除所有與該值相同的節點，直到所有相同的節點都被移除。

`q_swap`

Commit bbf456c

使用 list_for_each_safe 來確保在修改結構時的安全性，並對鏈結串列中的相鄰節點進行兩兩交換。調整指標以維持正確的鏈結結構，確保遍歷時不影響整體鏈結的完整性。

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head)) return;
    struct list_head *cur, *tmp;
    list_for_each_safe (cur, tmp, head) {
        // 略: 兩兩節點 next, prev指向反轉
    }
    return;
}

在與[森哥]討論後，我們發現 q_swap 本質上與 q_reverseK(head, 2) 是相同的，當 k=2 時， q_reverseK 也會實現相同的兩兩節點交換效果。然而，目前尚未深入分析直接實作兩兩交換與呼叫 q_reverseK 來達成相同效果之間的優缺點，這部分仍待進一步探討。 TBD…

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head)) return;

    q_reverseK(head, 2);
    return;
}

`q_reverse`

Commit 12dc9a5

使用 list_for_each_safe 來確保在修改結構時的安全性，並將當前節點的指針 next 和 prev變換方向，當走訪結束時，再將 head 的 next 和 prev依序變換方向即可。

同q_swap，q_reverse 本質上與 q_reverseK(head, q_size(head)) 無異，優缺點仍待進一步討論。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head)) return;

    q_reverseK(head, q_size(head));
    return;
}

`q_reverseK`

Commit 9cc973e

透過一個 for 迴圈，程式會每次取出 k 個節點進行處理，包括將這些節點從原鏈結串列中切割出來、反轉 (q_reverse)，然後將結果串接至新的頭節點 new_head。
迴圈中止條件是當迴圈變數 i 超過 size - k 時停止執行，確保每次處理的區間包含 k 節點。當剩餘節點不足 k 個時，不會再執行反轉操作，迴圈就會結束。最終，已反轉的節點會被拼接回原始鏈結串列，完成整個處理流程。

- int time = size / k;
- for(int i = 0;i < k ; i++){
+ for (int i = 0; i <= size - k; i += k) {
     int j = 0;
     list_for_each (tail, head) {
         if (j >= k)
             break;
         j++;
     }
     list_cut_position(&tmp, head, tail->prev);
     q_reverse(&tmp);
     list_splice_tail_init(&tmp, &new_head);
 }
 list_splice_init(&new_head, head);

`q_sort`, `merge_sort` & `merge_two_list`

Commit 855dffa

起初用quicksort實做，但在進行make test中發現，q_sort要求必須為stable sort，因此採用merge sort來實踐，q_sort會叫輔助函數static void merge_sort()和static void merge_two_list()，使用static是因為這兩個函數僅供q_sort，為了清楚理解static的定義，翻閱C99規格書，

C99 (6.2.1.4)

… If the declarator or type specifier that declares the identifier appears outside of any block or list of parameters, the identifier has file scope, which terminates at the end of the translation unit. …

C99 (6.2.2.3)

If the declaration of a file scope identifier for an object or a function contains the storage-class specifier static, the identifier has internal linkage.

由此可知，static的作用域為文件作用域 (file scope) ，即該標識符 (identifier) 的作用範圍僅限於當前翻譯單元 (translation unit) ，並且內部連結 (internal linkage) 確保該標識符無法被其他翻譯單元引用。

在實做merge_sort中，透過快慢指針找出中間的節點，使用linux API進行list的切割成，但卻在靜態分析中，遇到了下方的警告，因為對於 const 也是一知半解，所以一樣去翻閱C99規格書

    struct list_head *mid = head;
    // Variable 'fast' can be declared as pointer to const [constVariablePointer]
-   struct list_head *fast = head->next;
-   for (; fast != head && fast->next != head; fast = fast->next->next)
-        mid = mid->next;

+   const struct list_head *fast = (const struct list_head *) head->next;
+   while (fast != (const struct list_head *) head &&
+          fast->next != (const struct list_head *) head) {
+       mid = mid->next;
+       fast = (const struct list_head *) fast->next->next;
+   }

C99 (6.7.3.5)

If an attempt is made to modify an object defined with a const-qualified type through use of an lvalue with non-const-qualified type, the behavior is undefined.

這段標準表示，當某個變數被 const 修飾後，若透過非 const 型別的左值 (lvalue) 來修改該變數，則行為是未定義的 (undefined behavior)。也就是說，被 const 修飾的變數，只能用來讀取，不能透過非 const 型別的指標來修改其內容。在這段程式碼中，fast只是用來走訪整個雙向鏈結串列，不需要修改任何list_head的內容，用const限制不能修改其值，且因為head->next的型別為struct list_head *，因此需要強制轉型。

`q_ascend` & `q_descend`

Commit 56cbacb

實作升冪/降冪排序的想法是，透過從鏈結串列的尾端 head->prev 開始往 head 的方向移動，對於升冪排序，用 minVal 去維持當前的最小值，若當前節點大於 minVal ，將此節點移出鏈結串列並釋放其空間，反之，保留節點並更新 minVal ; 對於降冪排序也是一樣的邏輯，用 maxVal 去維持當前最大值。但卻在靜態分析中，遇到了下方的警告，因為對於 const 也是一知半解，所以一樣去翻閱C99規格書

// Variable 'elem' can be declared as pointer to const [constVariablePointer]
-    element_t *elem = list_entry(cur, element_t, list);
+    const element_t *elem = list_entry(cur, element_t, list);

// Variable 'minVal' can be declared as pointer to const [constVariablePointer]
-    char *minVal = elem->value;
+    const char *minVal = elem->value;

C99 (6.7.3.5)

If an attempt is made to modify an object defined with a const-qualified type through use of an lvalue with non-const-qualified type, the behavior is undefined.

這段標準表示，當某個變數被 const 修飾後，若透過非 const 型別的左值 (lvalue) 來修改該變數，則行為是未定義的 (undefined behavior)。也就是說，被 const 修飾的變數，只能用來讀取，不能透過非 const 型別的指標來修改其內容。因此，在這段程式碼中，指針 elem 和 minVal 都不應該被修改，而僅用來讀取鏈結串列的內容，所以它們可以安全地被宣告為 const，以強化程式的安全性與可讀性。

`q_merge`

Commit 6268965

因為需要兩兩合併要求出 ceil(size/2)) 的值，為了避免使用除法運算，因此下方的程式碼透過位元操作去計算向上取整。

- int m = size % 2 ? size/2+1 : size/2 ;
+ int m = (size >> 1) + (size & 1);

透過 merge sort 的概念，逐步合併兩個佇列的方式，不斷減少佇列的數量，直到只剩下最終合併完成的佇列，最後若處理是否需要反轉

static void merge_sort(struct list_head *head)
{
    ...
    for (int i = 0; i < m; i++) {
        queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
        queue_contex_t *second =
            list_entry(first->chain.next, queue_contex_t, chain);

        while (!list_empty(first->q) && !list_empty(second->q)) {
-           merge_two_list(head, first->q, second->q);
+           merge_two_list(first->q, first->q, second->q);
            list_move_tail(&second->chain, head);
            first = list_entry(first->chain.next, queue_contex_t, chain);
            second = list_entry(first->chain.next, queue_contex_t, chain);
    }
    

    ...
}

為了避免新增一個函數僅供q_merge使用，因此調用了先前的 merge_two_list ，但在呼叫時出現了以下的問題，

static void merge_two_list(struct list_head *head,
                           struct list_head *left,
                           struct list_head *right){略};

static void merge_sort(struct list_head *head)
{
    // 找出中間節點，分割鏈結串列 (略)
    merge_sort(&left);
    merge_sort(&right);
    merge_two_list(head, &left, &right);
}
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head)) return;
    merge_sort(head);
    if (descend) q_reverse(head);
    return;
}

先回顧q_sort的程式碼，在 merge_sort 中調用的 merge_two_list 是將 left 和 right 的已排序後的鏈結串列合併到 head 後方，最終 head 就是指向排序後的整個鏈結串列。

由此可知，merge_two_list 的第一個參數應該是目標位置，也就是合併後的結果會存放在哪個鏈結串列裡。因此，在merge_sort的 while 迴圈中，目標是要把 second->q 的節點合併到 first->q 裡，第一個參數就應該是 first->q，而不是 head。
與 charliechiou 討論後，這邊用5組鏈結串列 a, b, c, d, e 作為例子，為了方便解釋，預設其大小已按照升冪排序，( )表示排序後的鏈結串列，

i=0 : 
    第一次 while : (a,b), c, d, e
    第二次 while : (a,b), (c, d), e -> 跳出 while 迴圈
i=1 : 
    第一次 while : (a, b, c, d), e -> 跳出 while 迴圈
i=2 : 
    第一次 while : (a, b, c, d, e) -> 跳出 while 迴圈
i=3 :
    跳出 for 迴圈

Valgrind + 自動化測試程式

Commit f4f99dc

運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗

$ # install massif-visualizer
$ sudo apt install massif-visualizer -y

可以新增下方的程式到 ./Makefile 中，若想測試其他的 trace ，把 traces/trace-massif.cmd 改掉就好，最後會用 massif-visualizer 輸出 .massif.out 。

+massif: qtest
+    valgrind --tool=massif --massif-out-file=.massif.out ./$< -v 3 -f traces/trace-massif.cmd
+    massif-visualizer .massif.out
+    ms_print .massif.out

新增 traces/trace-massif.cmd，因為作業要求提及到「視覺化 "simulation" 過程中的記憶體使用量」，因此內容直接複製 trace-17-complexity 來改就好，以下以 q_insert_tail 為例進行分析，

# Test if time complexity of 'q_insert_tail' is constant
option simulation 1
it
option simulation 0

開啟終端機輸入，

$ make massif

輸出如下，

87.51% (1,131,446B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->86.37% (1,116,641B) 0x10F96B: alloc (harness.c:146)
| ->86.37% (1,116,641B) 0x10FABE: test_malloc (harness.c:176)
|   ->49.39% (638,592B) 0x1100F8: q_insert_head (queue.c:37)
|   | ->49.39% (638,592B) 0x110C3B: measure (constant.c:100)
|   |   ->49.39% (638,592B) 0x1111E3: doit (fixture.c:172)
|   |     ->49.39% (638,592B) 0x1111E3: test_const (fixture.c:203)
|   |       ->49.39% (638,592B) 0x111320: is_insert_tail_const (fixture.c:216)
|   |         ->49.39% (638,592B) 0x10CCD8: queue_insert (qtest.c:192)
|   |           ->49.39% (638,592B) 0x10D0F0: do_it (qtest.c:288)
|   |             ->49.39% (638,592B) 0x10E7AD: interpret_cmda (console.c:181)
|   |               ->49.39% (638,592B) 0x10ED72: interpret_cmd (console.c:201)
|   |                 ->49.39% (638,592B) 0x10F001: cmd_select (console.c:593)
|   |                   ->49.39% (638,592B) 0x10F8DF: run_console (console.c:673)
|   |                     ->49.39% (638,592B) 0x10DB9C: main (qtest.c:1459)
|   |                       
|   ->36.97% (477,929B) 0x10FC7F: test_strdup (harness.c:231)
|   | ->36.96% (477,881B) 0x110114: q_insert_head (queue.c:41)
|   | | ->36.96% (477,881B) 0x110C3B: measure (constant.c:100)
|   | |   ->36.96% (477,881B) 0x1111E3: doit (fixture.c:172)
|   | |     ->36.96% (477,881B) 0x1111E3: test_const (fixture.c:203)
|   | |       ->36.96% (477,881B) 0x111320: is_insert_tail_const (fixture.c:216)
|   | |         ->36.96% (477,881B) 0x10CCD8: queue_insert (qtest.c:192)
|   | |           ->36.96% (477,881B) 0x10D0F0: do_it (qtest.c:288)
|   | |             ->36.96% (477,881B) 0x10E7AD: interpret_cmda (console.c:181)
|   | |               ->36.96% (477,881B) 0x10ED72: interpret_cmd (console.c:201)
|   | |                 ->36.96% (477,881B) 0x10F001: cmd_select (console.c:593)
|   | |                   ->36.96% (477,881B) 0x10F8DF: run_console (console.c:673)
|   | |                     ->36.96% (477,881B) 0x10DB9C: main (qtest.c:1459)
|   | |                       
|   | ->00.00% (48B) in 1+ places, all below ms_print's threshold (01.00%)
|   | 
|   ->00.01% (120B) in 1+ places, all below ms_print's threshold (01.00%)
|   
->01.15% (14,805B) in 13 places, all below massif's threshold (1.00%)

可以看到其中 heap 的使用資源佔用了 86.37 % ，而 test_strdup 佔了其中的 36.97%。
這次把 test_malloc 和 test_free 註解掉，重新測試，

51.01% (334,262B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->36.61% (239,856B) 0x1100F8: q_insert_head (queue.c:37)
| ->36.61% (239,856B) 0x110C2B: measure (constant.c:100)
|   ->36.61% (239,856B) 0x1111D3: doit (fixture.c:172)
|     ->36.61% (239,856B) 0x1111D3: test_const (fixture.c:203)
|       ->36.61% (239,856B) 0x111310: is_insert_tail_const (fixture.c:216)
|         ->36.61% (239,856B) 0x10CCD8: queue_insert (qtest.c:192)
|           ->36.61% (239,856B) 0x10D0F0: do_it (qtest.c:288)
|             ->36.61% (239,856B) 0x10E7AD: interpret_cmda (console.c:181)
|               ->36.61% (239,856B) 0x10ED72: interpret_cmd (console.c:201)
|                 ->36.61% (239,856B) 0x10F001: cmd_select (console.c:593)
|                   ->36.61% (239,856B) 0x10F8DF: run_console (console.c:673)
|                     ->36.61% (239,856B) 0x10DB9C: main (qtest.c:1459)
|                       
->12.14% (79,561B) 0x4A0335E: strdup (strdup.c:42)
| ->12.14% (79,553B) 0x11010C: q_insert_head (queue.c:41)
| | ->12.14% (79,553B) 0x110C2B: measure (constant.c:100)
| |   ->12.14% (79,553B) 0x1111D3: doit (fixture.c:172)
| |     ->12.14% (79,553B) 0x1111D3: test_const (fixture.c:203)
| |       ->12.14% (79,553B) 0x111310: is_insert_tail_const (fixture.c:216)
| |         ->12.14% (79,553B) 0x10CCD8: queue_insert (qtest.c:192)
| |           ->12.14% (79,553B) 0x10D0F0: do_it (qtest.c:288)
| |             ->12.14% (79,553B) 0x10E7AD: interpret_cmda (console.c:181)
| |               ->12.14% (79,553B) 0x10ED72: interpret_cmd (console.c:201)
| |                 ->12.14% (79,553B) 0x10F001: cmd_select (console.c:593)
| |                   ->12.14% (79,553B) 0x10F8DF: run_console (console.c:673)
| |                     ->12.14% (79,553B) 0x10DB9C: main (qtest.c:1459)
| |                       
| ->00.00% (8B) in 1+ places, all below ms_print's threshold (01.00%)
| 
->01.47% (9,656B) 0x10E345: malloc_or_fail (report.c:215)
| ->01.25% (8,216B) 0x10EA4E: push_file (console.c:460)
| | ->01.25% (8,216B) 0x10F7B9: run_console (console.c:651)
| |   ->01.25% (8,216B) 0x10DB9C: main (qtest.c:1459)
| |     
| ->00.22% (1,440B) in 1+ places, all below ms_print's threshold (01.00%)
| 
->00.79% (5,189B) in 1+ places, all below ms_print's threshold (01.00%)

可以看到 heap allocation 的使用量從 87.51% (1,131,446B) 降至 51.01% (334,262B) ，且使用 strdup 僅佔用了 12.14% (79,561B) ，相比 test_strdup 佔用的 36.97% (477,929B) 少了很多，但也可以發現有 malloc_or_fail 產生，至於原因為何，TBD。

整合網頁伺服器

參考 charliechiou

在 console.c 中 do_web() 是一個開啟 Web 伺服器的函式，參考作業說明 lab0 (C) 的操作，開啟兩個終端機

$ ./qtest # Terminal 1
cmd> web
listen on port 9999, fd is 3

在終端機 2 中輸入 curl http://localhost:9999/new ，可以預期在終端機 1 呼叫 q_new()，此時打開瀏覽器輸入 http://localhost:9999/new ，卻在終端機 1 中看到下方的錯誤訊息，

cmd> 
Unknown command 'favicon.ico'
cmd> 
l = []

解決 `favicon.ico`

Commit f2e261d

為了解決 favicon.ico 所產生的問題，根據老師的步驟修改，同時我加上了 "<h1>Good Job, Eric!</h1>"，可以預期成功用瀏覽器 request 後，應該要出現 Good Job, Eric! 的字眼。

        char *p = web_recv(web_connfd, &clientaddr);
-       char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
+       char *buffer = 
+           "HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
+           "Content-Type: text/html\r\n\r\n" "<html><head><style>"
+           "body{font-family: monospace; font-size: 13px;}"
+           "td {padding: 1.5px 6px;}"
+           "</style><link rel=\"shortcut icon\" href=\"#\">"
+           "<h1>Good Job, Eric!</h1>"
+           "</head><body><table>\n";
        web_send(web_connfd, buffer);

修正後，重新在瀏覽器輸入 curl http://localhost:9999/new，便能成功透過瀏覽器發出 request 和見到下方的字樣。仔細觀察終端機的輸出，Chrome 發送了兩次 request ，因此可以看到終端機輸出了兩次的l = []，至於如何解決此問題， TBD 。

判斷 request 來源

Commit 40d8775

此時，在先前的終端機 2 中輸入 curl http://localhost:9999/new ，會顯示一長串的 html 檔案的內容。

$ curl http://localhost:9999/new # Terminal 2
<html><head><style>body{font-family: monospace; font-size: 13px;}td {padding: 1.5px 6px;}</style><link rel="shortcut icon" href="#"><h1>Good Job, Eric!</h1></head><body><table>

可以由此判斷，網頁伺服器無法判斷 request 的來源，可以在 parse_request 中，把透過接收的 request 用終端機輸出，如下，

$ # Request from curl
User-Agent: curl/8.5.0 
$ # Request from Chrome broswer
User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/133.0.0.0 Safari/537.36

透過 request 的資訊可以看出 User-Agent 的差異，我們能以此判斷 request 是否來自 curl ，可以注意到我只有使用 Chrome 發出 request ，但回傳了一長串的 User-Agent ，其中的關鍵字包含 Mozilla 和 Safari ，即是 User agent spoofing ，簡言之 Chrome 的 User-Agent 包含了 Mozilla 和 Safari 是歷史相容性需求，同時瀏覽器可以透過 User-Agent 欺騙老舊的網站，讓老舊網站認為 Chrome 是支援的瀏覽器; 但好像沒法判別是 Mozilla 或是 Chrome 所發出的，益或是也無此必要性，TBD…

在 parse_request 儲存將 User-Agent 的資訊，

typedef struct {
    char filename[512];
    off_t offset; /* for support Range */
    size_t end;
+   char user_agent[256]; /* User-Agent */
} http_request_t;

    while (buf[0] != '\n' && buf[1] != '\n') { /* \n || \r\n */
        ...
+       if (strncmp(buf, "User-Agent:", 11) == 0) {
+           strncpy(req->user_agent, buf + 12, sizeof(req->user_agent) - 1);
+           req->user_agent[sizeof(req->user_agent) - 1] = '\0';
+       }
    }

並在 web_recv 中判斷 user_agent 中的資訊是否包含 "curl"，

- char *web_recv(int fd, struct sockaddr_in *clientaddr)
+ char *web_recv(int fd, struct sockaddr_in *clientaddr, int *is_curl)
  {
     http_request_t req;
     parse_request(fd, &req);

+     *is_curl = 0;
+     if (strstr(req.user_agent, "curl") != NULL)
+        *is_curl = 1;


     char *p = req.filename;
     ...
 }

最後於 web_eventmux 中對於判斷 request 來源，進行了下方的修改，

int web_eventmux(char *buf)
{
    fd_set listenset;
+   int is_curl = 0;

    ...
    if (server_fd > 0 && FD_ISSET(server_fd, &listenset)) {
        ...
-       char *p = web_recv(web_connfd, &clientaddr);
+       char *p = web_recv(web_connfd, &clientaddr, &is_curl);
-       char *buffer =
-          "HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
-          "Content-Type: text/html\r\n\r\n"
-          "<html><head><style>"
-          "body{font-family: monospace; font-size: 13px;}"
-          "td {padding: 1.5px 6px;}"
-          "</style><link rel=\"shortcut icon\" href=\"#\">"
-          "<h1>Good Job, Eric!</h1>"
-          "</head><body><table>\n";
+       char *buffer = NULL;
+       if (is_curl) {
+           buffer =
+               "HTTP/1.1 200 OK\r\n"
+               "Content-Type: text/plain\r\n\r\n"
+               "Good Job, Eric! Request from curl.\n";
+       } else {
+           buffer =
+               "HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
+               "Content-Type: text/html\r\n\r\n"
+               "<html><head><style>"
+               "body{font-family: monospace; font-size: 13px;}"
+               "td {padding: 1.5px 6px;}"
+               "</style><link rel=\"shortcut icon\" href=\"#\">"
+               "<h1>Good Job, Eric! Request from browser.</h1>"
+               "</head><body><table>\n";
+       }
        web_send(web_connfd, buffer);
        ...
    }

最後用終端機來驗證，如下圖呈現，但對於瀏覽器為何會發出兩次的 reqeust ， TBD 。

Request from curl
Request from browser

User-Agent Switcher and Manager 的擴充功能，可以任意的切換 User-Agent 內容，因此我在 Chrome 中，輸入 curl 的 User-Agent string，或是在原本的 User-Agent 後方加上 "Curl" ，都可以看到下方的結果。

User-Agent spoofing 的優點已在上述提及，至於會有什麼樣的問題? TBD 。

研讀 `select()`

解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示

上面的 code 改完後，才發現並沒有詳讀 select ，參考 Integrate linenoise with web server #162 ，看到下方的程式碼片段，可以理解 web_eventmux() 在處理來自伺服器和終端機的 mutex 問題，因此查閱了 select(2)，先去理解各個 interface 的用意。

`select()`

allows a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation (e.g., read(2), or a sufficiently small write(2)) without blocking.

select()允許程式同時監聽多個檔案描述符（file descriptors, FDs），並在其中至少有一個變為「可讀」、「可寫」或發生異常時返回，避免程式進入不必要的阻塞狀態。

`fd_set`

A structure type that can represent a set of file descriptors. According to POSIX, the maximum number of file descriptors in an fd_set structure is the value of the macro FD_SETSIZE.

fd_set 是用來存放文件描述 (fd, file descriptors)集合的結構體，通常用在 select()中，來監聽多個 fd 的狀態。 line 3 即透過 fd_set 宣告 listenset。

`FD_ZERO()`

This macro clears (removes all file descriptors from) set. It should be employed as the first step in initializing a file descriptor set.

FD_ZERO() 是一個用來初始化 fd_set 的巨集，作用是清空 fd_set， line 4 便是初始化 listenset。

`FD_SET()`

This macro adds the file descriptor fd to set. Adding a file descriptor that is already present in the set is a no-op, and does not produce an error.

FD_SET() 是用來將指定的FD加入 fd_set 的巨集，如果 line 5 就是將標準輸入（STDIN）加入 fd_set，讓 select() 監聽它是否可讀; 如果 server_fd 存在，江 server_fd 加入 fd_set。 max_fd 則是計算所有 FD 的最大值。

`FD_ISSET()`

select() modifies the contents of the sets according to the rules described below. After calling select(), the FD_ISSET() macro can be used to test if a file descriptor is still present in a set. FD_ISSET() returns nonzero if the file descriptor fd is present in set, and zero if it is not.

用來檢查 fd_set 內某個 FD 是否還在 select() 返回的結果中。

`FD_CLR`

This macro removes the file descriptor fd from set. Removing a file descriptor that is not present in the set is a no-op, and does not produce an error.

FD_SET() 是從 fd_set 來移除指定的FD的巨集，讓 select() 不再監聽。

line 17 if (server_fd > 0 && FD_ISSET(server_fd, &listenset)) 檢查 server_fd 是否有新的連線，如果有，用 FD_CLR 先移除，避免影響下次的 select() ，接著就是使用上面新增的 is_curl 來判斷此連線的來源。





















int web_eventmux(char *buf)
{
    fd_set listenset;

    FD_ZERO(&listenset);
    FD_SET(STDIN_FILENO, &listenset);
    int max_fd = STDIN_FILENO;
    if (server_fd > 0) {
        FD_SET(server_fd, &listenset);
        max_fd = max_fd > server_fd ? max_fd : server_fd;
    }
    int result = select(max_fd + 1, &listenset, NULL, NULL, NULL);
    if (result < 0)
        return -1;

    int is_curl = 0;
    if (server_fd > 0 && FD_ISSET(server_fd, &listenset)) {
        FD_CLR(server_fd, &listenset);
        struct sockaddr_in clientaddr;
        socklen_t clientlen = sizeof(clientaddr);
        ...

console.c 實做 & RIO 套件

可對照參考 CS:APP 第 10 章重點提示

console.c 的目的為實做 command line interface (CLI) ，允許從標準輸入 stdin 或網路 request 接收指令。
其中 select() 負責同時監聽標準輸入 (STDIN_FILENO) 和網路請求 (web_fd)，以及當其中一個 FD 可讀時，執行對應的處理。

`cmd_select()`

在 cmd_select() 中，當 stdin 有輸入時，系統會執行 readline() 來讀取輸入內容，然後交由 interpret_cmd() 解析並執行相應的命令。然而，傳統 readline() 每次讀取輸入時可能會頻繁呼叫 read()，這會導致效能低下，特別是當輸入來源是檔案或 socket 時，每個字元都可能觸發 read() 系統呼叫，使 I/O 成本大幅增加。因此，為了提升效能並減少 read() 次數，console.c 引入 RIO（Robust I/O）緩衝機制來優化 readline()，透過 rio_read() 來管理讀取流程。

`readline()`

當 buf_stack->count == 0 時，readline() 才會執行 read()：
* 一次性讀取 8192 bytes (RIO_BUFSIZE)。
* 之後的讀取直接來自 buffer，不再執行 read()，直到 buffer 耗盡。
這樣避免了每讀取一個字元就調用 read()，提升效能。

if (buf_stack->count <= 0) {  
    buf_stack->count = read(buf_stack->fd, buf_stack->buf, RIO_BUFSIZE);
    buf_stack->bufptr = buf_stack->buf;
}

如果 readline() 讀到 EOF，它會從 buf_stack 內彈出 (pop) 上一層 buffer，這讓 readline() 可以讀取不同來源的輸入，而不會頻繁執行 read() 。

if (buf_stack->count <= 0) {
    pop_file();
}

亂數

Fisher-Yates shuffle

Commit02d154d
參考 willwillhi

參考作業說明 lab0 (D) 實做 q_shuffle 和 willwillhi 對於 queue.h 和 qtest.c 的修改，因為 queue.h 是不能修改，因此在下方做上註記。

queue.h

  int q_merge(struct list_head *head, bool descend);
+ void q_shuffle(struct list_head *head);
  #endif /* LAB0_QUEUE_H */

測試腳本

Commit 8484015

參考作業說明 lab0 (D) 新增測試腳本 test_shuffle.py。

統計方法驗證

參考lab0 (D)

補充: test_shuffle.py 會跑有點久，平均一次 13 分鐘左右

$ python3 test_shuffle.py
Expectation:  41666
Observation:  {'1234': 41665, '1243': 41891, '1324': 41722, '1342': 41489, '1423': 41649, '1432': 41608, '2134': 41424, '2143': 41662, '2314': 41396, '2341': 41575, '2413': 41655, '2431': 41365, '3124': 41986, '3142': 41774, '3214': 41848, '3241': 41730, '3412': 42060, '3421': 41784, '4123': 41765, '4132': 41240, '4213': 41498, '4231': 41732, '4312': 41900, '4321': 41582}
chi square sum:  22.20851533624538

	觀察到的頻率	期待的頻率	$\frac{(O_{i} - E_{i})^{2}}{E_{i}}$
[1,2,3,4]	41665	41666	0.0000240004
[1,2,4,3]	41891	41666	1.2150194400
[1,3,2,4]	41722	41666	0.0752652042
[1,3,4,2]	41489	41666	0.7519080305
[1,4,2,3]	41649	41666	0.0069361110
[1,4,3,2]	41608	41666	0.0807372918
[2,1,3,4]	41424	41666	1.4055584890
[2,1,4,3]	41662	41666	0.0003840061
[2,3,1,4]	41396	41666	1.7496279940
[2,3,4,1]	41575	41666	0.1987471800
[2,4,1,3]	41655	41666	0.0029040465
[2,4,3,1]	41365	41666	2.1744587910
[3,1,2,4]	41986	41666	2.4576393220
[3,1,4,2]	41774	41666	0.2799404790
[3,2,1,4]	41848	41666	0.7949887198
[3,2,4,1]	41730	41666	0.0983055729
[3,4,1,2]	42060	41666	3.7257236120
[3,4,2,1]	41784	41666	0.3341813469
[4,1,2,3]	41765	41666	0.2352277636
[4,1,3,2]	41240	41666	4.3554936880
[4,2,1,3]	41498	41666	0.6773868382
[4,2,3,1]	41732	41666	0.1045456727
[4,3,1,2]	41900	41666	1.3141650270
[4,3,2,1]	41582	41666	0.1693467095
Total			22.20851533624538

X^{2}

= 22.20851533624538
本次實驗的排列組合有

4!

= 24種，所以自由度是 23，透過查尋卡方分布表，可以查到 P value 位於 0.1 ~ 0.9 的區間，因為 P value(0.1 ~ 0.9) > alpha (0.05) ，統計檢定的結果不拒絕虛無假說 (

H_{0}

) 也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻，可以看到下方的圖片， shuffle 的頻率是大致符合 Uniform distribution 的。

亂度

What is random?

包含以下性質 : Unpredictability, Uniformity, Independence, 和 High Entropy

How to measure the randomness?

用
$E n t r o p y$

What is random

隨機（randomness）是一種無法預測的現象，通常具有以下關鍵特性：

不可預測性（Unpredictability）
- 如果一個事件是隨機的，那麼在沒有任何額外資訊的情況下，無法準確預測它的下一個結果。
- 例如，擲骰子時，理論上無法預測下一次擲出的數字。
均勻性（Uniformity）
- 在理想的隨機情況下，每個可能結果的發生機率應該相等，例如均勻分佈（Uniform Distribution）。
- 以擲骰子為例，
  $1$ 到
  $6$ 各個數字應該有相等的
  $\frac{1}{6}$ 機率發生。
獨立性（Independence）
- 事件之間應該是獨立的，即前一個事件的結果不應影響下一個事件的機率分佈。
- 例如，擲硬幣時，不論上一次結果是正面還是反面，下一次擲出的機率仍然是 50%。
高資訊熵（High Entropy）
- 亂數應該具有最大的資訊熵（Entropy），因為這表示我們能從過去的數據中獲取的資訊最少（即最難預測）。
- 當所有事件的機率都相等時，Entropy 取最大值，即代表最隨機的狀態；若某些結果比其他結果更容易發生，則 Entropy 會降低

How to measure the randomness

透過

E n t r o p y

來測亂度。

Self-information
- 每個隨機事件發生時所傳遞的資訊量
  $I (x_{i})$ 與該事件的機率
  $P (x_{i})$ 成反比，定義如下：
  
  $I (x_{i}) = l o g_{b} (\frac{1}{P (x_{i})}) = - \log_{b} P (x_{i})$
- 當事件發生的機率
  $P (x_{i})$ 越低時，其資訊量
  $I (x_{i})$ 就越高，因為這類事件更罕見，因此提供更多的資訊。
Entropy
- 資訊熵
  $S$ 是隨機變數所有可能結果的平均資訊量，定義為：
  
  $S = - \sum_{i = 1}^{n} P (x_{i}) l o g_{b} P (x_{i}) = \sum_{i = 1}^{n} P (x_{i}) I (x_{i})$
- Entropy 衡量了隨機變數的不確定性，當所有可能事件的機率均等時，Entropy 取最大值，表示最難以預測的情況。

實做 - ent 亂度

安裝 ent，此工具 ent 可計算一輸入字串的Entropy。

$ sudo apt-get install ent

根據作業說明，嘗試計算 linux 內建的 PRNG /dev/random

$ head -c 10M /dev/random | ent
Entropy = 7.999982 bits per byte.

Optimum compression would reduce the size
of this 10485760 byte file by 0 percent.

Chi square distribution for 10485760 samples is 268.02, and randomly
would exceed this value 27.54 percent of the times.

Arithmetic mean value of data bytes is 127.5092 (127.5 = random).
Monte Carlo value for Pi is 3.143029458 (error 0.05 percent).
Serial correlation coefficient is 0.000093 (totally uncorrelated = 0.0).

可以看到，因為 /dev/random 的內容隨機，因此每一個位元的資料量較大，同時 1 byte char 的大小為

2^{8}

，所以最大的 entropy 是

S = l o g_{2} (2^{8}) = 8

，對照上方的 Entropy = 7.999982 bits per byte.，與理論值無異。

實做 - qtest 亂度

在 ./qtest 中執行 option entropy 1 並搭配 it RAND 10 來計算每個字串的 shannon entropy ，其輸出結果如下

$ ./qtest
cmd> new
l = []
cmd> option entropy 1
cmd> it RAND 10
l = [wewgqrne(29.69%) akrfem(29.69%) ljwxio(29.69%) quvmmsno(32.81%) tnftbit(25.00%) wccwf(17.19%) zewuflwh(32.81%) msbyjtb(29.69%) pbrjq(26.56%) eckrxnmys(37.50%)]

這些字串的熵是透過 shannon_entropy.c 所計算的，因此查看程式碼，

...
for (uint32_t i = 0; i < BUCKET_SIZE; i++) {
    if (bucket[i]) {
        uint64_t p = bucket[i];
        p *= LOG2_ARG_SHIFT / count;
        entropy_sum += -p * log2_lshift16(p);
    }
}
entropy_sum /= LOG2_ARG_SHIFT;
return entropy_sum * 100.0 / entropy_max;

這邊的計算遵循著先前計算

S

的公式，並正規化輸出。
針對第一筆 wewgqrne(29.69%) 進行分析，

char	times	p(x)	$l o g_{2} p (x)$	$- p (x) l o g_{2} p (x)$
w	2	2/8 = 0.25	-2	0.5
e	2	2/8 = 0.25	-2	0.5
g	1	1/8 = 0.125	-3	0.375
q	1	1/8 = 0.125	-3	0.375
r	1	1/8 = 0.125	-3	0.375
n	1	1/8 = 0.125	-3	0.375
$S_{s u m}$				2.5

S_{s u m} = 2.5

，計算 1byte 編碼下的 entropy =

\frac{2.5}{8} \times 100 % = 31.25 %

，實際值只有

5 %

的誤差。

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

論文
 oreparaz/dudect
參考 I-HSIN Cheng， Yiwei Lin

作者提出 dudect 工具，用於檢測程式碼的時間複雜度是否為 constant time 。論文中 Step3: Apply statistical test 是本次實做的關鍵，透過量測程式在兩筆不同輸入（如 fix-vs-random ）時的執行時間分佈，並應用 Welch’s t-test來判斷分佈差異，試圖推翻「兩個時間分佈相等」的虛無假設 (null hypothesis,

H_{0}

)。

虛無假設 (null hypothesis,

$H_{0}$ )
論文將此解釋為 "the two timing distributions are equal" ，若兩組測資的執行時間分佈是相等的，更精準的說若兩個樣本的變異數相等，代表程式碼的時間複雜度即是 constant-time。

Student’s t-test 假設兩個樣本均值來自正態分佈（normally distributed）的母體，並且母體的變異數相等。而 Welch’s t-test 是 Student’s t-test 的變體，適用於變異數不等的情況，但仍然保持正態分佈的假設。因此，本作業測試 constant time implementation 時，使用的是 Welch's t-test，而非 Student’s t-test。

解釋本程式的 "simulation" 及程式實作的原理。

Commit 709516f

可以在 ./qtest.c 中找到 simulation ，當值為 1 時會檢查 queue_insert 和 queue_remove 是否符合 constant time 。
先從 queue_insert 看起，可以發現 is_insert_tail_const() 是判斷是否符合 const time 的函式，用 ctrl + 滑鼠左鍵此函式後，會跳到 ./dudect/fixture.h，但卻找不到 is_insert_tail_const() 的介面，觀察到了下方的註解， /* Interface to test if function is constant */ ，可以預期是透過 #define _(x) bool is_##x##_const(void); 去定義剛剛找不到的介面。

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

#endif

再點開上方的DUT_FUNCS會跳到./dudect/constant.h，

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

#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};
...

首先，因為 fixture.h 中有 #include "constant.h" ，所以預處理器 (preprocessor) 會先展開 constant.h 的巨集，接著才是 fixture.h ，
到這邊開始看不懂了，為了看懂需要釐清兩個觀念：巨集的展開，和 ## 的用意。

巨集展開

是時候來查閱規格書了，首先我看不懂 #define _(x) bool is_##x##_const(void);的用意？

C99 (6.10.3.10)

A preprocessing directive of the form
# define identifier lparen identifier-listopt ) replacement-list new-line
# define identifier lparen … ) replacement-list new-line
# define identifier lparen identifier-list , … ) replacement-list new-line
defines a function-like macro with parameters, whose use is similar syntactically to a
function call.

由規格書可以理解這條巨集的格式如下，

//# define identifier ( identifier-listopt )  replacement-list            new-line
  # define _          ( x                  )  bool is_##x##_const(void);

其實這條巨集和 #define ADD(a,b) a+b 沒有差別，只是第一次看到 identifier 是 _ (底線)，原地嚇到。

The `##` operator

參考 Linux 核心原始程式碼巨集: max, min ，## 在 C 語言前置處理器的作用是 concatenation (即連結、接續的意涵)。

C99 (6.10.3.3.2)

If, in the replacement list of a function-like macro, a parameter is immediately preceded or followed by a ## preprocessing token, the parameter is replaced by the corresponding argument’s preprocessing token sequence;

GNU 3.5 Concatenation

This is called token pasting or token concatenation. The ## preprocessing operator performs token pasting. When a macro is expanded, the two tokens on either side of each ## operator are combined into a single token, which then replaces the ‘##’ and the two original tokens in the macro expansion.

根據 C99 規範，當 function-like macro 的參數前後緊鄰 ## 運算子時，該參數會被對應的引數替換，並與 ## 兩側的標識符連結。因此，在 #define _(x) bool is_##x##_const(void); 中 x 會被 arugment 取代，而 is_ 和 _const(void); 會分別連結到其前後，最終形成有效的函式宣告。例如，當傳入 insert_head 時，展開結果將為 bool is_insert_head_const(void);。

Preprocessing














// ./dudect/constant.h
#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)

#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};

首先在 line 1 的 DUT_FUNCS 會被展開成

_(insert_head) _(insert_tail) _(remove_head) _(remove_tail)

展開 line 8 的 DUT(x) 巨集，到此 line 為止還沒有使用到此巨集。
展開 line 11 的 #define _(x) DUT(x), 巨集，會變成

// _(x)           => DUT(x)
// _(insert_head) => DUT(insert_head)

DUT(insert_head), DUT(insert_tail), DUT(remove_head), DUT(remove_tail),

line 11 的 DUT(x) 又會被 line 8 的巨集 #define DUT(x) DUT_##x 展開，

// DUT(x)           => DUT_##x
// DUT(insert_head) => DUT_insert_head 

DUT_insert_head, DUT_insert_tail, DUT_remove_head, DUT_remove_tail,

line 12 取消 _ 的定義。
了解至此，把上述程式碼複製到 test.c 對於巨集依序進行測試，並輸入 $ gcc -E -P test.c -o output.c，便可以在 output.c 中看到預處理後的結果，最後 enum 的成員如下，

enum {
    DUT_insert_head, DUT_insert_tail, DUT_remove_head, DUT_remove_tail,
};

現在回到 dudect/fixture.h 中，

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

#define _(x) bool is_##x##_const(void); 實際上定義了四個函式原型

bool is_insert_head_const(void); 
bool is_insert_tail_const(void); 
bool is_remove_head_const(void); 
bool is_remove_tail_const(void);

在 dudect/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 _

則定義了函式的實作

bool is_insert_head_const(void) { return test_const("insert_head", DUT(insert_head)); }
bool is_insert_tail_const(void) { return test_const("insert_tail", DUT(insert_tail)); }
bool is_remove_head_const(void) { return test_const("remove_head", DUT(remove_head)); }
bool is_remove_tail_const(void) { return test_const("remove_tail", DUT(remove_tail)); }

參考作者在 update_statistics中 discard the first few measurements ，因此做了以下更動

-    for (size_t i = 0 ; i < N_MEASURES; i++) {
+    for (size_t i = 10 ; i < N_MEASURES; i++) {

觀察 dudect_main 中，在呼叫 update_statics 前會先呼叫 prepare_percentile ，先對測量到的執行時間數據進行預處理，以確保統計分析的準確性。我認為這樣的處理就是論文中的 Step2. Apply post-processing ，此步驟實做去掉某些極端值 (Cropping) 和 High-order preprocessing。因此將採用作者的原始碼，新增以下段落，並針對 fixture.c 進行了對應的修改。

/*
* Reference : https://github.com/oreparaz/dudect/blob/master/src/dudect.h#L203
*/
static int cmp(const int64_t *a, const int64_t *b) {
    if (*a == *b)
        return 0;
    return (*a > *b) ? 1 : -1;
}

/*
* Reference : https://github.com/oreparaz/dudect/blob/master/src/dudect.h#L209
*/
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.
* Reference : https://github.com/oreparaz/dudect/blob/master/src/dudect.h#L221
*/
static void prepare_percentiles(int64_t *exec_times)
{
    qsort(exec_times, N_MEASURES, sizeof(int64_t),
        (int (*)(const void *, const void *)) cmp);
    for (size_t i = 0; i < N_MEASURES; i++) {
        exec_times[i] = percentile(
            exec_times, 1 - (pow(0.5, 10 * (double) (i + 1) / N_MEASURES)),
            N_MEASURES);
    }
}

做完改動後，就可以在 action 首次看到卡比了。

解釋 Student's t-distribution

TBD…

Linux核心 lib/list_sort.c




























void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
    ...
    do {
        size_t bits;
        struct list_head **tail = &pending;

        /* Find the least-significant clear bit in count */
        for (bits = count; bits & 1; bits >>= 1)
            tail = &(*tail)->prev;
        /* Do the indicated merge */
        if (likely(bits)) {
            struct list_head *a = *tail, *b = a->prev;

            a = merge(priv, cmp, b, a);
            /* Install the merged result in place of the inputs */
            a->prev = b->prev;
            *tail = a;
        }

        /* Move one element from input list to pending */
        list->prev = pending;
        pending = list;
        list = list->next;
        pending->next = NULL;
        count++;
    } while (list);
    ... // continue

用表格紀錄我最一開始的理解，下方的表格對應 list_sort 程式碼中的 do-while 迴圈 (line 4~27) ， line 9 判斷當前的 count 的 MSB 和 LSB 中，只要有 1 個 0-bit， line 12 就會對於 pending 進行 merge, line 21 - 26 再把節點從 list 拉一個到 pending 上，直到 list 上沒有節點，同時也結束 合併:不合併 = 2:1 的原則。

表格為了輸出美觀，因此省了一些字

表格左上的 # 代表 節點總數;
count 二進位欄位中，pending上 有
$3 \times 2^{k}$ 個節點，省略了 pending 上
[ ] 代表欲合併的數個節點
// 代表合併後，pending 新增的節點，

#	count 變化	count 二進位	merge	pending 上的節點
1	0 $\to$ 1	0000 $\to$ 0001	no（ $2^{0}$ ）	1
2	1 $\to$ 2	0001 $\to$ 0010	no（ $2^{1}$ ）	1 $\leftarrow$ 1
2+1	(過程)	有 $3 \times 2^{0}$ 個節點合併前 $2 \times 2^{0}$ 個節點		[1* $\leftarrow$ 1] // $\leftarrow$ 1
3	2 $\to$ 3	0010 $\to$ 0011	yes	(2) $\leftarrow$ 1
4	3 $\to$ 4	0011 $\to$ 0100	no（ $2^{2}$ ）	2 $\leftarrow$ 1 $\leftarrow$ 1
4+1	(過程)	有 $3 \times 2^{0}$ 個節點合併前 $2 \times 2^{0}$		2 $\leftarrow$ [1* $\leftarrow$ 1] // $\leftarrow$ 1
5	4 $\to$ 5	0100 $\to$ 0101	yes	2 $\leftarrow$ (2) $\leftarrow$ 1
5+1	(過程)	有 $3 \times 2^{1}$ 個節點 (一個 2, 一個2, 一個(1',1')) 合併前 $2 \times 2^{1}$ 個節點		[2* $\leftarrow$ 2*] $\leftarrow$ 1' // $\leftarrow$ 1'
6	5 $\to$ 6	0101 $\to$ 0110	yes	(4) $\leftarrow$ 1 $\leftarrow$ 1
6+1	(過程)	有 $3 \times 2^{0}$ 個節點合併前 $2 \times 2^{0}$ 個節點		4 $\leftarrow$ [1* $\leftarrow$ 1] // $\leftarrow$ 1
7	6 $\to$ 7	0110 $\to$ 0111	yes	4 $\leftarrow$ (2) $\leftarrow$ 1

截至目前，對於這種合併方式有個疑問，以7個節點為例，操作完 do-loop 後， pending 明顯沒合併完成阿，再跟 charliechiou 討論並詳閱 list_sort 後，才發現 line 30 - 39 就是從尾端把部份合併完成的 pending 上的每個節點，兩兩進行合併，直到全數合併完， line 41 再建構回原本的雙向鏈結串列。
















    ...
    /* End of input; merge together all the pending lists. */
    list = pending;
    pending = pending->prev;
    for (;;) {
        struct list_head *next = pending->prev;

        if (!next)
            break;
        list = merge(priv, cmp, pending, list);
        pending = next;
    }
    /* The final merge, rebuilding prev links */
    merge_final(priv, cmp, head, pending, list);
} // end of list_sort
EXPORT_SYMBOL(list_sort);

至此，也終於是稿懂了 list_sort 的程式碼了，因此就將 list_sort, merge 和 merge_final 做了簡單的修改，補進去 queue.c 中，就能執行了。

Pull Request

Ensure repetitions input is at least 1 #244

雖然只是很小的 debug ，但很開心能貢獻程式碼。

測試時發現 it test -10 竟然沒有報錯，原來在 qtest.c 中，只會判斷 reps 是否為整數，所以負數和 0 都能通過檢查，雖然不影響程式運行，但對於使用者不太直觀。

$ ./qtest
cmd> new
l = []
cmd> it test -10
l = []
cmd>

因此補進了負數和 0 的除錯判斷後，

-if (!get_int(argv[2], &reps)) {
+if (!get_int(argv[2], &reps) || reps < 1) {
     report(1, "Invalid number of insertions '%s'", argv[2]);
     return false;
 }

再次進行測試，便能正常報錯了，提交的 PR 已被 merge !

$ ./qtest
cmd> new
l = []
cmd> it test -10
Invalid number of insertions '-10'
cmd>

Fix console hang after exceeding input limit #248

這次的 patch 與 charliechiou 一同協作

這邊做個實驗，開啟 ./qtest 後連續輸入 5 次的 unkown command ，

$ ./qtest
cmd> ak # 任意錯誤指令
Unknown command 'ak'
cmd> bk
Unknown command 'bk'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
Error limit exceeded.  Stopping command execution.
cmd> quit # 沒用
cmd> # 只能使用 `Ctrl` + c 跳出

這次的 bug 是接續上面的測試後，意外發現的，在原本的 console.c 中，當輸入的錯誤超過了錯誤上限 err_limit ，會讓設 quit_flag = true ，這會導致 interpret_cmd 因為判斷到 quit_flag == True 直接返回 flase。

static void record_error()
{
    err_cnt++;
    if (err_cnt >= err_limit) {
        report(1, "Error limit exceeded.  Stopping command execution");
        quit_flag = true;
    }
}
...
static bool interpret_cmd(char *cmdline)
{
    if (quit_flag)
        return false;
    ...
}

簡單來說，一旦錯誤輸入達到了上限，任何 command 都不再允許，包括 quit ，只能輸入 CTRL + c 強制離開，這會導致可能的記憶體洩漏，起初我們做了以下的改動，預先宣告 do_quit 的函式，就可以再不更動程式的結構下，讓 record_error 呼叫，一旦輸入錯誤超過錯誤上限，便強制 quit 。

+static bool do_quit(int argc, char *argv[]);
static void record_error()
{
    err_cnt++;
    if (err_cnt >= err_limit) {
        report(
            1,
-            "Error limit exceeded.  Stopping command execution");
+            "Error limit exceeded.  Stopping command execution, and quitting");
+        do_quit(0, NULL);
    }
}

後來便收到了 jserv 老師的回覆，根據此回覆我們引入了一個 helper function force_quit 給 do_quit 和 record_error 使用，

+/* Handles forced console termination for record_error and do_quit */
+static bool force_quit(int argc, char *argv[])
+{
+    cmd_element_t *c = cmd_list;
+    bool ok = true;
+    while (c) {
+        cmd_element_t *ele = c;
+        c = c->next;
+        free_block(ele, sizeof(cmd_element_t));
+    }
+
+    param_element_t *p = param_list;
+    while (p) {
+        param_element_t *ele = p;
+        p = p->next;
+        free_block(ele, sizeof(param_element_t));
+    }
+
+    while (buf_stack)
+        pop_file();
+
+    for (int i = 0; i < quit_helper_cnt; i++) {
+        ok = ok && quit_helpers[i](argc, argv);
+    }
+
+    quit_flag = true;
+    return ok;
+}
+
 static void record_error()
 {
     err_cnt++;
         report(
             1,
             "Error limit exceeded.  Stopping command execution, and quitting");
-        do_quit(0, NULL);
+        force_quit(0, NULL);
     }
 }
 
 /* Built-in commands */
 static bool do_quit(int argc, char *argv[])
 {
-    cmd_element_t *c = cmd_list;
-    bool ok = true;
-    while (c) {
-        cmd_element_t *ele = c;
-        c = c->next;
-        free_block(ele, sizeof(cmd_element_t));
-    }
-
-    param_element_t *p = param_list;
-    while (p) {
-        param_element_t *ele = p;
-        p = p->next;
-        free_block(ele, sizeof(param_element_t));
-    }
-
-    while (buf_stack)
-        pop_file();
-
-    for (int i = 0; i < quit_helper_cnt; i++) {
-        ok = ok && quit_helpers[i](argc, argv);
-    }
-
-    quit_flag = true;
-    return ok;
+    return force_quit(argc, argv);
 }

經過這樣的更動，當使用者輸入的錯誤指令超越 err_limit 時, record_error() 會直接call force_quit 強制終止，此 PR 也已經被 merge !

$ ./qtest
cmd> ak # 任意錯誤指令
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
cmd> ak
Unknown command 'ak'
Error limit exceeded.  Stopping command execution, and quitting
Freeing queue
$

Improve log command feedback #252

Before: Ambiguous log command feedback

$ ./qtest
cmd> log
No log file given
cmd> log temp.txt
cmd> new
l = []
cmd> quit
Freeing queue
$

After: Clear and informative log command messages

$ ./qtest
cmd> log
No log file given. Use 'log <file>' 
cmd> log temp.txt
Logging enabled: temp.txt 
cmd> new
l = []
cmd> quit
Freeing queue
$ cat temp.txt
l = []
Freeing queue
$

Improve source command feedback #253

static bool do_source(int argc, char *argv[])
{
    if (argc < 2) {
-       report(1, "No source file given");
+       report(1, "No source file given. Use 'source <file>'.");
        return false;
    }

    if (!push_file(argv[1])) {
        report(1, "Could not open source file '%s'", argv[1]);
        return false;
    }

    return true;
}

Before: Ambiguous log command feedback

$ cat src.txt
new
free
quit
$./qtest
cmd> source
No source file given
cmd> source src.txt
cmd> new
l = []
cmd> free
l = NULL
cmd> quit
Freeing queue
$

After: Clear and informative log command messages

$ ./qtest
cmd> source
No source file given. Use 'source <file>'.
cmd> source src.txt
cmd> new
l = []
cmd> free
l = NULL
cmd> quit
Freeing queue
$

Not yet

Test trailer

test trailer                                                       

Co-authored-by:                   Eric Chou        <mail>
Acked-by:Charlie<mail>
Signed-off-by:                    jserv       <mail>

更改前

$ git add .             
$ git commit
Running static analysis...
[fix-format 7fc257f] Test trailer
 1 file changed, 1 insertion(+), 1 deletion(-)
$ git log -1 | cat
commit 7fc257fe67ef4db95967d9794ac1d19acdb5a51a
Author: Eric Chou <yphbchou0911@gmail.com>
Date:   Mon Mar 10 20:23:49 2025 +0800

    Test trailer
    
    test trailer
    
    Co-authored-by:                   Eric Chou        <mail>
    Acked-by:Charlie<mail>
    Signed-off-by:                    jserv       <mail>
    Change-Id: I9662301f035e952ed09a7bdc174d723bcf638436
$

更改後

$ git add .    
$ git commit
Running static analysis...
[fix-format c27cbf2] Test trailer
 1 file changed, 52 insertions(+), 8 deletions(-)
$ git log -1 | cat
commit c27cbf2546b74daa4e1d906dbea403bfdea73b42
Author: Eric Chou <yphbchou0911@gmail.com>
Date:   Mon Mar 10 20:27:32 2025 +0800

    Test trailer
    
    test trailer
    
    Co-authored-by: Eric Chou <mail>
    Acked-by: Charlie <mail>
    Signed-off-by: jserv <mail>
    Change-Id: I59822e10fe0527329e9fbaff7cf24354cdfb4a13
$

2025q1 Homework1 (lab0)

開發環境

實作 queue.c

q_new

q_free

q_insert_head & q_remove_head

q_remove_head & q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort, merge_sort & merge_two_list

C99 (6.2.1.4)

C99 (6.2.2.3)

C99 (6.7.3.5)

q_ascend & q_descend

C99 (6.7.3.5)

q_merge

Valgrind + 自動化測試程式

整合網頁伺服器

解決 favicon.ico

判斷 request 來源

研讀 select()

select()

fd_set

FD_ZERO()

FD_SET()

FD_ISSET()

FD_CLR

console.c 實做 & RIO 套件

cmd_select()

readline()

亂數

Fisher-Yates shuffle

queue.h

測試腳本

統計方法驗證

亂度

What is random

How to measure the randomness

實做 - ent 亂度

實做 - qtest 亂度

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

解釋本程式的 "simulation" 及程式實作的原理。

巨集展開

C99 (6.10.3.10)

The ## operator

C99 (6.10.3.3.2)

GNU 3.5 Concatenation

Preprocessing

解釋 Student's t-distribution

Linux核心 lib/list_sort.c

Pull Request

Ensure repetitions input is at least 1 #244

Fix console hang after exceeding input limit #248

Improve log command feedback #252

Improve source command feedback #253

Not yet

Read more

移除 Linux

2025q1 Homework5 (assessment)

2025q1 Homework3

2025 年 Linux 核心設計課程作業 - Eric

`q_new`

`q_free`

`q_insert_head` & `q_remove_head`

`q_remove_head` & `q_remove_tail`

`q_size`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseK`

`q_sort`, `merge_sort` & `merge_two_list`

`q_ascend` & `q_descend`

`q_merge`

解決 `favicon.ico`

研讀 `select()`

`select()`

`fd_set`

`FD_ZERO()`

`FD_SET()`

`FD_ISSET()`

`FD_CLR`

`cmd_select()`

`readline()`

The `##` operator