2024q1 Homework1 (lab0)

contributed by < paul90317 >

開發環境

升級 Ubuntu Linux 版本，否則後續作業無法進行。

已升級

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ 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-9300H CPU @ 2.40GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    BogoMIPS:            4800.01

環境暫時使用 docker 建立

指定的佇列操作

`q_swap`

void q_swap(struct list_head *head)
{
    struct list_head *node1, *node2, *safe, *temp;
    for (node1 = head->next, node2 = node1->next, safe = node2->next;
         node1 != head && node2 != head;
         node1 = safe, node2 = node1->next, safe = node2->next) {
        temp = node1->next;
        node1->next = node2->next;
        node2->next = temp;
        temp = node1->prev;
        node1->prev = node2->prev;
        node2->prev = temp;
    }
}

access 的翻譯是「存取」，而非「訪問」(visit)

好

迴圈的設計是參考 list_for_each_safe，用 safe 來存下兩個要存取的節點的起始節點。在當前要存取的兩個節點中: node1 是原本鏈結串列中左邊的節點，node2 是原本鏈結串列中右邊的節點。

我們要做的是就是將兩個交換，而以上程式碼所採用的方式是將 node1 與 node2 的 next 互換且 node1 與 node2 的 prev 互換。

但程式碼測試結果是錯誤的，如下

l = [e d c b a]
cmd> swap
l = [e c a]

他只讀到奇數節點 (node1)，這是因為要讓他們在鏈結串列中互換，還需要將 node1 的前一個節點的下一節點指標指向 node2 且 node2 的下一個節點的前一節點指標指向 node1。

所以最後我用 list.h 中的函式對程式碼做改進，如下

void q_swap(struct list_head *head)
{
    struct list_head *node1, *node2, *safe;
    for (node1 = head->next, node2 = node1->next, safe = node2->next;
         node1 != head && node2 != head;
         node1 = safe, node2 = node1->next, safe = node2->next) {
-       temp = node1->next;
-       node1->next = node2->next;
-       node2->next = temp;
-       temp = node1->prev;
-       node1->prev = node2->prev;
-       node2->prev = temp;
+       list_del(node1);       
+       list_add(node1, node2);
    }
}

程式碼順利運作

`q_reverse`

void q_reverse(struct list_head *head) {
    struct list_head *node, *temp;
    list_for_each (node, head) {
        temp = node->next;
        node->next = node->prev;
        node->prev = temp;
    }
}

測試結果:

l = [a b c]
cmd> reverse
無窮迴圈

這裡是 infinite loop，直譯是「無窮迴圈」，而非「死」的循環，請詳閱 Wikipedia 說明。工程人員說話要精準。

好

這個其實是我忘記使用 list_for_each_safe 的結果，但我們還是可以分析會造成無窮迴圈的原因。經過肉眼追蹤程式碼後，要完成 reverse 命令，會先執行函式 q_reverse，再來會呼叫 is_circular，檢查該鏈結串列正不正常，其中反向檢查的程式碼會造成無窮迴圈，因為 q_reverse 交換 a 的 next 與 prev 之後，a->next 會指向 head，這會觸發 list_for_each 的終止條件，完成 q_reverse，而此時 a->prev 會指向 b，這會是觸發後續 is_circular 無窮迴圈的關鍵，因為當 a, b 被存取完之後，b 的下一節點又是 a。

當然以上錯誤都是因為 list_for_each 沒辦法在修改完當前節點後，正確的存取我們想要的下一節點，改成 list_for_each_safe，它會在我們對當前節點修改前，就將下一節點存到 safe，這樣在修改結束後，就可以將 node 指定為 safe，也就是原本串列的下一節點。

另外如果要反轉整條序列，也要交換 head 的 prev 跟 next。

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫。
~~已改進~~

不要過早說「已改進」，持續落實流暢的漢語表達。

好

以下是正確的程式碼

void q_reverse(struct list_head *head)
{
-   struct list_head *node, *temp;
+   struct list_head *node, *safe, *temp;
-   list_for_each (node, head) {
+   list_for_each_safe (node, safe, head) {
        temp = node->next;
        node->next = node->prev;
        node->prev = temp;
    }
+   temp = head->next;
+   head->next = head->prev;
+   head->prev = temp;
}

你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」

我以後會盡量不直接貼程式碼，轉而用漢語表達

`q_reverseK`















void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    struct list_head *node, *safe;
    for (node = head->next; node != head; node = safe) {
        int n;
        for (n = 0, safe = node; n < k && safe != head; ++n) {
            safe = safe->next;
        }
        while (n--) {
            list_del(node->next);
            list_add_tail(node->next, safe);
        }
    }
}

這段程式碼一樣無法順利運作，因為 node 是我們要倒轉的群組裡的第一個節點，但第 11 行卻是 node->next。順便一提，就算真的要移除 node->next 並且加到 safe 左端，也會出錯，因為經過 list_del(node->next) 後 node 的 next 已經被修改了。

10~13 的 while 迴圈其實不能達到反轉的效果。要達成反轉，我們當然可以使用 q_reverse 把所有節點的 next 與 prev 交換，但因為這題是一段一段反轉，會造成寫程式上面的困難。所以我選擇使用堆疊將所有節點從每個群組的頭部取出依序放入堆疊，再把節點依序從堆疊中拿出依序放入群組尾部，最後群組就會是反轉的。

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫。

授課教師要求學員提升漢語表達的動機之一，是見到不少學生在課堂表現不俗，但在面試場合卻無法清晰地闡述自己的成果和獨到的成就，從而錯過躋身一流資訊科技企業的機會。

隨時做好展現自身專業的準備。

好 !

`q_delete_dup`

這題依照 leetcode 上的描述，佇列的節點會依照升序排列，也就是說我們只要遍歷整條佇列並刪除那些與下一個節點具有相同資料的節點就好。然而題目的要求是把出現一次以上的節點刪除，也就是要完全刪除，而如果依照上述方法還會剩下一個，所以我又宣告了一個布林值，他表示上一個元素是否與當前元素相同，如果是的話節點就會被刪除，因為這個布林值，程式不需要額外再比較，維護布林值的方法也很簡單，只要在當前節點與下一節點相同時把布林值設成真否則設為假，存取下一節點時若看到布林值為真就會把自己刪除。

我在實作的過程中犯了一個錯誤，我沒有考慮到下一節點可能是 head，導致記憶體區段錯誤。

`q_ascend`

根據題目描述，我們需要刪掉特定節點，這些節點右邊存在至少一個較小的節點。我的做法是採取反向遍歷，持續維護到目前為止的最小節點，只要當前節點大於目前為止的最小節點就會移除當前節點。接著要來證明該演算法的合理性，其實 "大於右邊最小的節點" 與 "大於右邊至少一節點" 是等價的，因為大於最小節點代表一定只少大於一節點，而至少大於一節點，那這些節點之中必有最小的。

在我的程式碼有一個步驟是用 strcmp 比較兩條字串是大於、等於還是小於，如果新的節點比當前節點小就要更新最小值並將回傳值加一；如果比較大就要移除；等於就將回傳值加一，這樣的操作需要重複的 strcmp，所以作了以下修改，先宣個一個變數 cmp 將其指派以 strcmp 的回傳值，修改如下:

-if (!min_str || strcmp(element->value, min_str))
+int cmp = strcmp(element->value, min_str);
+if (!min_str || cmp < 0) {`

然而 !min_str || ... 是用來檢測當前最小字串 min_str 是否已經被指派，如果已經被指派過才會執行或者後面的程式碼，也就是 strcmp，而經過修改後 strcmp 就必定會執行，會導致嘗試比較未指派的字串 min_str 而導致記憶體區段錯誤。於是為了避免這個問題，我進行以下修改:

-int cmp = strcmp(element->value, min_str);
+int cmp = min_str ? strcmp(element->value, min_str) : -1;
-if (!min_str || cmp < 0) {`
+if (cmp < 0) {

`q_sort`

我採用 buttom-up 合併排序，首先建立一個堆疊，其最大長度為欲排序佇列的長度轉成二進位後所占用的位元數，也就是 $\lceil\log\text{佇列長度}\rceil+1$。

接下來遍歷整條佇列，把節點當作長度為 1 的佇列放入堆疊中，每次放到堆疊中後，都會檢查堆疊最上面的兩個節點，如果相同就合併為一條排序多的序列，直到無法合併，才會存取下一節點。最後堆疊還會有一些佇列，由堆疊頂部往下合併最後剩下一個已排序佇列，就是結果。

這裡我想要舉例說明為什麼堆疊最大長度是欲排序佇列長度轉乘而進位後的占用位元數，例如佇列長度是 8，轉成二進位是 1000，而我們從上述可得知，堆疊中住列的長度只會是二的冪，也就是說從 0 ~ 1000(8) 所經歷的數字中，有最多 1 的是 111(7)，這會讓佇列長度最大，而我們的演算法會先將新的長度為 1 佇列放入堆疊後再合併，所以堆疊最長會是 $[4,2,1,1]$，也就是 4；那麼如果是非 2 的冪例如 10001(17)，所經歷多 1 的二進位數是 1111(15)，堆疊最大長度是 4 + 1 也就是 4，成立。所以我們可以歸納一個得出最大堆疊長度的作法，假設給定欲排序佇列長度 n，我們會先算出其轉成二進位的佔用位元數 $k=\lceil\log_2 n\rceil+1$，再看看 $[0,n)$ 所經歷的數字中，轉成二進位後有最多 1 的數字所占用的位元數是 $k-1=\lceil\log_2 n\rceil$，且因為演算法是先放入堆疊再合併，所以長度會再加一 $\lceil\log_2 n\rceil+1$。

與 top-down 的合併排序相比，切割子問題方式有所不同，但合併的順序是相同的都是 cache-friendly。

:bug: Bugs
在實作過程中發生一點錯誤，為了方便合併，我定義一個函數

static struct list_head merge(struct list_head *a, struct list_head *b);

我下意識的以為只要回傳的是佇列的值而非指標，因為被釋放的只有指標指的記憶體，指標的值會先被複製並且回傳，這樣就可以在外面安全接到這個回傳的佇列，然而我發現，雖然值會回傳，但是 perv, next 都會指向自己在函式中已經被釋放的記憶體，再做後續的操作就會導致記憶體區段錯誤。

typedef struct {
    int size;
    struct list_head list;
} list_t;

static void merge_tail_init(list_t *list, list_t *head);

於是我重新定義一個新的函式，他會把 list 的節點合併到 head。

另外 list_splice (list, head) 與 list_splice_init (list, head) 有所不同，list_splice 只會把 list 的節點加到 head，並不會對 list 做初始化，list_splice_init 則會。

`q_merge`

commit 0894f74

題目會給定多條已排序佇列，我們要做的是就是把它合併，且合併後的佇列依舊是已排序的。函式參數只會有一個 struct list_head 的指標，名稱為 head，當作 queue_context_t 的佇列。head 是 queue_chain_t 的容器。

我的作法是將所有的已排序佇列放到堆積裡面，每次要合併時，就從堆積中拿取長度最小的佇列。接著我會用 buttom-up 的解法，每次迭代時，都從堆積中拿取最小的兩條佇列將其合併並放回堆積中，直到推積只剩一條佇列。

拿最短兩個佇列做合併的原因是因為如果我們在合併兩條佇列的過程中，最糟情況是對佇列的每個節點都進行比較，在最糟的情況下會有最少的比較次數。那為甚麼會最少，我引入霍夫曼樹來證明:

霍夫曼樹又稱最優二元樹，是一種帶權路徑長度最短的二元樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點爲0層，葉結點到根結點的路徑長度爲葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記爲 $\text{WPL}=(W_1*L_1+W_2*L_2+W_3*L_3+...+W_n*L_n)$，N 個權值 $W_i(i=1,2,...n)$ 構成一棵有 N 個葉結點的二元樹，相應的葉結點的路徑長度爲$L_i(i=1,2,...n)$。可以證明霍夫曼樹的 WPL 是最小的。

~~> [霍夫曼編碼 - Wiki](https://zh.wikipedia.org/zh-tw/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81)~~

電腦技術的詞目不要參照中文的 Wikipedia，因為內容通常會過時。改參照英語 Wikipedia 條目或者對應的教科書。

權重在我們的演算法裡就是起始佇列長度，而 WPL 就是比較的次數。假定有一個霍夫曼樹 T，我們讓它任意兩個佇列交換得到 T'，較長的佇列被移到下層，其實也就意味著它會參與合併越多次，自然有更多的比較次數，在公式中也是如此。

:bug: Bugs
這裡我在實作 heapify 函式的時候發生意外，heapify 的參數是堆積的一個節點，如果該節點與自己的子節點相比不是最小，就會與最小的子節點交換，持續到自己是最小的。但可以看到我的程式碼只檢查當前節點 curr 是否超過邊界，而沒有檢查最小的子節點 down，從而導致記憶體區段錯誤，經過修改方可運作。

static void heapify(list_t *heap, int heap_size, int curr)
{
    while (curr < heap_size) {
        int left = 2 * curr + 1, right = 2 * curr + 2;
+       left = left < heap_size ? left : curr;
+       right = right < heap_size ? right : curr;
        if (heap[curr].size <= heap[left].size &&
            heap[curr].size <= heap[right].size) {
            break;
        }
        int down = heap[left].size <= heap[right].size ? left : right;
        swap(heap + down, heap + curr);
        curr = down;
    }
}

:bulb: Tips
前面提到我們需要從堆積中拿出兩條佇列，合併後再放到堆積中，但是放入堆積這個操作需要額外定義 buttom-up 的 heapify 函式，相當繁瑣，所以想到一個辦法，先交換最短佇列 heap[0] 與陣列末尾佇列 heap[heap_size]，對最頂部 heap[0] 做 heapify 後，最頂部就會是第二短的佇列，再把最小合併到最頂部 (heap[heap_size] 合併到 heap[0])，再對最頂部做 heapify，就可以不用進行插入操作，從而避免 buttom-up 的 heapify。

swap(heap + --heap_size, heap);
heapify(heap, heap_size, 0);
merge_tail_init(heap + heap_size, heap);
heapify(heap, heap_size, 0);

分數: 95/100, 差最後的常數時間測試。

整合網頁伺服器

方法 1: 開啟 web 時關閉 linenoise

commit: b62b9e
commit: bc5d89

這個方法是說當程式收到 web 命令時，為轉換為讀取網路請求的模式，此時 linenoise 會被關閉，但使用者仍然可以使用 stdin 輸入命令。

我發現這個方法是 lab0 內建的方法，所以我這裡選擇理解他的實作並且對使用者體驗加以改進。

當 Chrome 請求網頁時，都會順便透過 (/favicon.ico) 請求網頁縮圖，但是 lab0 的網頁伺服器並不認得這個請求，就會回報錯誤，解決辦法是將請求網頁縮圖的命令導向到其他命令，我發現 /show 並不會對伺服器做任何修改，很適合做為導向目標。實作方法是在回應給 Chrome 的 <head> 標籤裡插入:

<link rel="shortcut icon" href="show">

再來我對終端機收到網頁請求後的顯示很有意見

cmd> l = []
cmd> Current queue ID: 0
l = []
cmd> Current queue ID: 0
l = []

可以看到 cmd> 後面顯示的是網路請求命令的結果，而不是網路命令本身，我希望可以變成:

web> new
l = []
web> show
Current queue ID: 0
l = []
web> show
Current queue ID: 0
l = []

要解決這個問題，首先必須知道 cmd> 是如何產生的，透過追蹤程式碼，我發現 console.c 有一段全域定義 static char *prompt = "cmd> ";，接著看看誰用到它，發現都是用在 cmd_select，而當程式收到 web 命令後，在 run_console 中，會從 linenoise 模式切換到網路請求和沒有 linenoise 的終端機輸入的混合模式，混合模式就是透過 cmd_select 來處理命令的，而解決方法也很簡單，就是當 cmd_select 發現命令來自網路請求時，印出 \rweb> [cmdline]\n，\r 回到行首可以把前面的 cmd> 覆蓋。

還有一個問題是超文本的換行是 <br/>，但函式 report 所回傳的換行是 \n，解決辦法就是讓 report 回傳給 web_fd 的換行改成 <br/> 就好。

方法 2: 將 web 整合進 linenoise

commit: a2b687

linenoise->line_raw->line_edit，透過肉眼追蹤程式碼，這個函式用來完成自動補完功能，以及其他特別鍵盤事件的處理。這個函式用一個迴圈來讀取一列命令的字元，起初我式這麼理解的，然而我發先不論它讀到甚麼，都會直接跳出迴圈，所以你可以把這個函式想像成讀取一個字元，如果是一些特別的鍵盤事件會優先處理，否則就是只會插入字元。最後會由 linenoise 這個外部函式回傳目前的命令列，交給 run_console->interpret_cmd 做處理。

知道 line_edit 在幹甚麼後，要做的修改很簡單了，就是透過 select 同時監控網路請求和標準輸入兩個檔案描述符，如果來自網路就直接插入，反之透過 line_edit 原本的程式碼處理。

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() 會搭配檔案描述符集合 (fd_set) 一起使用，用來定義欲監測的檔案描述符，並且當 select() 回傳之後，可以用 FD_ISSET 得知是哪個檔案描述符被觸發，如下:

if (FD_ISSET(listenfd, &set)) {
    connfd = accept(listenfd,(SA *) &clientaddr, &clientlen);
    char *p = process(connfd, &clientaddr);
    strncpy(buf, p, strlen(p) + 1);
    close(connfd);
    free(p);
    return strlen(p);
}

當發現是由網路請求觸發後，直接解析網路封包，得出指令。

我看題目要求提供的程式碼其中一列:

int rv = select(listenfd + 1, &set, NULL, NULL, NULL);

看不懂就說看不懂，不要不懂裝懂說「不是很懂」

看不懂 listenfd + 1 是甚麼意思，查了 man page 才知道所有檔案描述符都是自然數，而 listenfd + 1 就是最大欲監控的檔案描述符加一，也就是告訴作業系統我們只要監控到哪個數字就好。

nfds This argument should be set to the highest-numbered file
descriptor in any of the three sets, plus 1. The
indicated file descriptors in each set are checked, up to
this limit (but see BUGS).

以 Valgrind 分析記憶體問題

valgrind 是個可以在使用者層級動態追蹤並分析執行時期程式的行為的軟體，優點是即便是在所用的函式庫裡頭配置的記憶體，也可偵測到；缺點是與 cppcheck 不同，沒有執行到的就無法偵測。

valgrind 使用方式

先用 -g 參數編譯出二進位可執行檔

gcc -g -o <executable> <source>

再用 valgrind 執行可執行檔

$ valgrind <executable>

由於 valgrind 是動態追蹤，可能會從給定的二進位可執行檔追蹤到 glibc (GNU C library)，為了更好的分析效果，需要安裝對應包含除錯訊息的套件:

$ sudo apt install libc6-dbg

valgrind 運作原理

valgrind 會透過 dynamic binary instrumentation (DBI) 框架追蹤程式的行為並統整，再將得到的資訊透過 dynamic Binary Analysis (DBA) 工具加以分析，想要用 DBA 進行分析，需要對作業系統資源 (暫存器、主記憶體、檔案描述符…) 進行 shadow，這也是為什麼 valgrind 會執行緩慢的原因。

那麼 valgrind 的 DBI 框架是如何達到 shodow 並讓 DBA 工具得以運作呢? 其實就是透過 JIT 技術，動態將二進位指令轉成中間語言，插入一些分析程式碼，讓當 DBA 工具感興趣的事件 (例如記憶體配置) 發生時，就會跳躍到對應的 DBA 工具進行處理。最後再將更改後的中間語言編譯回機械碼。

valgrind 使用案例

想要檢驗記憶體存取，需要在 valgrind 加 –leak-check=full 參數:

$ valgrind -q --leak-check=full ./case1

案例 1: Memory Leak

memory lost 分成幾種類型：

definitely lost: 一般的 memory leak
indirectly lost: 間接的 memory leak，structure 如果是 definitely lost，那其中的 member 如果有配置記憶體，就會發生 indirectly lost，會稱作 indirectly lost 是因為如果 structure 本身的 definitely lost 修好，那 member 的 indirectly lost 就不會發生。
possibly lost: 當一塊記憶體其中的位址有被指標指到，但最低位址沒被指標指到。
still reachable: 函式結束時仍有指標指向記憶體，但該記憶體不在該函示內配置，這其實是滿常見的一件事，不需要處理。

案例 2: 越界存取 (in heap)
這個通常發生在透過指標位移存取到指標所指到的記憶體以外的記憶體，我們先看 heap 的越界存取，也就是用 malloc 回傳的指標。

#include <stdlib.h>
int main() {
    int *a = malloc(2 * sizeof(int)), *b = malloc(2 * sizeof(int));
    int diff = b - a;
    a[diff] = 1;
    return b[0];
}

==92114== 8 bytes in 1 blocks are definitely lost in loss record 1 of 2
==92114==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==92114==    by 0x10915E: main (beyond_heap_test.c:3)
==92114== 
==92114== 8 bytes in 1 blocks are definitely lost in loss record 2 of 2
==92114==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==92114==    by 0x10916C: main (beyond_heap_test.c:3)

由於 malloc 的指標不保證連續，所以我用指標減法來確保 $a[diff] == $b[0]。用 valgrind 測試後除了 definely lost 外沒有錯誤，因為 a, b 都是 malloc 配置的記憶體。

案例 3: 越界存取 (in stack)

int main() {
    int a[2] = {0}, b[2] = {0};
    a[2] = 1;
    return a[0];
}

這個程式會回傳 1，valgrind 同樣無法檢測其錯誤，因為即便越界仍然沒有超過 stack，需要借助其他工具 (例如 cppcheck) 才能。

$ cppcheck beyond_stack_test.c 
Checking beyond_stack_test.c ...
beyond_stack_test.c:3:6: error: Array 'a[2]' accessed at index 2, which is out of bounds. [arrayIndexOutOfBounds]
    a[2] = 1;
     ^

案例 4: 存取已經釋放的記憶體







#include <stdlib.h>
int main(){
	int *a = malloc(2 * sizeof(int));
	a[0] = 123;
	free(a);
	return a[0];
}

==8282== Invalid read of size 4
==8282==    at 0x10919D: main (free_test.c:6)
==8282==  Address 0x4a8b040 is 0 bytes inside a block of size 8 free'd
==8282==    at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==8282==    by 0x109198: main (free_test.c:5)
==8282==  Block was alloc'd at
==8282==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==8282==    by 0x10917E: main (free_test.c:3)

可以看到雖然沒有 memory lost，但是在第六行存取到第五行釋放的記憶體

案例 5: uninitialised value

int main() {
    int a[1];
    if(a[0])
        return a[0];
}

==89495== Conditional jump or move depends on uninitialised value(s)
==89495==    at 0x109169: main (undefined.c:3)

這個案例是因為讀取到未初始化的值。

案例 6: 檔案描述符
如果檔案描述符沒有關閉也可以被檢測只要加上 –track-fds=yes 參數就好。

總和以上 6 種案例，因為 valgrind 是動態追蹤，所以只要有執行到都可以輸出其錯誤，但沒有就不行。因為 valgrind 追蹤方式是追蹤執行檔，所以檢驗越界存取的方式是看存取是否跨越欲存取的記憶體區段 (segmentation)，所以大部分越界存取是無法被檢驗的，需要仰賴其他工具 (例如 cppchek) 除錯。

用 valgrind 分析 lab0

commit: dd25b20

==72189== Invalid read of size 8
==72189==    at 0x4852AF8: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==72189==    by 0x10FB68: memcpy (string_fortified.h:29)
==72189==    by 0x10FB68: q_remove_head (queue.c:78)
==72189==    by 0x10C734: queue_remove (qtest.c:353)
==72189==    by 0x10C8DC: do_rh (qtest.c:410)
==72189==    by 0x10DFEB: interpret_cmda (console.c:189)
==72189==    by 0x10E599: interpret_cmd (console.c:209)
==72189==    by 0x10E9CD: cmd_select (console.c:617)
==72189==    by 0x10F2D0: run_console (console.c:726)
==72189==    by 0x10D3E3: main (qtest.c:1258)

可以看到發生 invalid read，移動到 q_remove_head 定義，發現這行程式碼 memcpy(sp, element->value, bufsize - 1);，為什麼我要這樣寫，這是因為根據 q_remove_head 的宣告的註解。

/**
 * q_remove_head() - Remove the element from head of queue
 * @head: header of queue
 * @sp: string would be inserted
 * @bufsize: size of the string
 *
 * If sp is non-NULL and an element is removed, copy the removed string to *sp
 * (up to a maximum of bufsize-1 characters, plus a null terminator.)
 *
 * NOTE: "remove" is different from "delete"
 * The space used by the list element and the string should not be freed.
 * The only thing "remove" need to do is unlink it.
 *
 * Reference:
 * https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
 *
 * Return: the pointer to element, %NULL if queue is NULL or empty.
 */

bufsize 是字串長度，這會讓人以為是來源字串的長度，但應該是 sp 的大小才對，所以 sp 超過來源字串長度才會非法讀取，這邊改成

strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = 0;

第二行補空字元是因為如果來源字串太大，目標字串結尾不會補 0，可以參考 man page 的 strncpy 的偽代碼

// A simple implementation of strncpy() might be:

char *
strncpy(char *dest, const char *src, size_t n)
{
    size_t i;

   for (i = 0; i < n && src[i] != '\0'; i++)
        dest[i] = src[i];
    for ( ; i < n; i++)
        dest[i] = '\0';

   return dest;
}

下一個錯誤如下:

==12683== 72 bytes in 1 blocks are definitely lost in loss record 1 of 2
==12683==    at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==12683==    by 0x1101E8: q_merge (queue.c:342)
==12683==    by 0x10BD82: do_merge (qtest.c:823)
==12683==    by 0x10DFEB: interpret_cmda (console.c:189)
==12683==    by 0x10E599: interpret_cmd (console.c:209)
==12683==    by 0x10E9CD: cmd_select (console.c:617)
==12683==    by 0x10F2D0: run_console (console.c:726)
==12683==    by 0x10D3E3: main (qtest.c:1258)

找到 q_merge 後發現 list_t *heap = calloc(heap_size, sizeof(list_t)); 所配置的記憶體並沒有被釋放，然而在我的印象中 calloc 應該是使用 stack 的記憶體，於是我查找 man page 中關於 calloc 的定義:

Crashes in malloc(), calloc(), realloc(), or free() are almost always related to heap corruption, such as overflowing an allocated chunk or freeing the same pointer twice.

以上這段話雖沒明確說明 calloc 用甚麼配置，但肯定是要用 heap 配置才可以講出以上的話。

如果要解決以上問題，最簡單的方式就是將記憶體配置在 stack 上，也就是改成 list_t *stack[33];，會這樣修改一部份的原因是因為在 q_sort 禁止使用 free 釋放記憶體，然而想實現非遞迴排序，一定要有模擬 function stack 的手段，而我這邊使用堆疊，所以只能靜態配置大小。

論文閱讀 Dude

解釋 Student's t-test

首先在閱讀論文之前，先來理解論文中用到的統計測試 Student's t-test，其虛無假設是兩個機率分布一樣，其目的是為了檢驗兩個分布是否有差別。

雖然 Student's t-test 在這篇論文中是使用雙樣本作檢驗，但為了方便理解甚麼是統計檢定，我會先說明單一樣本 Student's t-test。

單一樣本 Student's t-test 的第一步是會算出 t-value，也就是 $\textbf{t}=\cfrac{\bar{\textbf{X}}-\mu}{s/\sqrt{n}}$，其中 $\bar{\textbf{X}}$ 是多個獨立同分布樣本 $\textbf{X}_\textbf{i}$ 的平均，也就是 $\cfrac{\textbf{X}_\textbf{1}+\textbf{X}_\textbf{2}+...+\textbf{X}_\textbf{n}}{n}$，所以可以想像 $\textbf{t}$ 會是一個隨機變數，而 $\mu$、$s$ 是抽樣母體的平均和標準差，也就是說 $\textbf{t}$ 會是一個將樣本平均抽樣後經過標準化的隨機變數，而 Student's t-test 假設樣本來自母體，也就是其虛無假設的由來，而因為 $\textbf{t}$ 是隨機變數，他會有自己的機率分布，根據中央極限定理，當 $n$ 越大，$\textbf{t}$ 會趨近於標準常態分佈。所以如果我們令 $n=1000$，我們每次抽樣 1000 個樣本算出 $t$，這些不同的 $t$ 會構成標準常態分佈，那如果不是標準常態分布，則代表說虛無假設被推翻，樣本不來自母體，而統計檢定的意義就在於 $t$ 太難算了，所以只算一次，然後看看這個 $t$ 落在標準常態分佈的哪裡，也就是透過查表去看標準常態分佈產生 $t$ 的機率是多少，這就是 p-value，如果太小，我們就可以說虛無假設被推翻是統計顯著的，也就是說兩者是樣本不來自母體。

那如果是雙樣本情況，我們則會做出兩次樣本平均，然後計算出 t-value，也就是將 $\mu$ 換成 $\bar{\textbf{Y}}$，典型的使用方法是我們令 $\textbf{Y}$ 為在 $\textbf{X}$ 之上應用一些操作變因的隨機變數，然檢驗這個變因會不會改變結果。

dudect 程式碼分析

github: oreparaz/dudect
paper: dude, is my code constant time?

先來講使用方式，第一步是定義以下函式:

prepare_inputs()
初始化一組輸入資料及他們的類別 (0 or 1)。
do_one_computation()
對一個輸入資料進行運算。

然後你需要在你的程式碼中實作以下代碼來進行測試

    dudect_init(&ctx, &config);
    dudect_state_t state = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
    while (state == DUDECT_NO_LEAKAGE_EVIDENCE_YET) {
        state = dudect_main(&ctx);
    }
    dudect_free(&ctx);

講解完如何使用後，來講 dudect_main() 的實作，每次呼叫時，都會呼叫 prepare_inputs() 準備一組資料，接這對每個資料呼叫 do_one_computation() 計算並記錄用時。當第一次呼叫時，會呼叫 prepare_percentiles() 準備 precentiles，這個待會會提到，其他都是呼叫 update_statistics() 線上更新 t-value，並用 report() 回傳這組資料的結果。

接這來說說 percentile，以下文字節錄自論文

Typical timing distributions are positively skewed towards larger execution times. This may be caused by measurement artifacts, the main process being interrupted by the OS or other extraneous activities. In this case, it may be convenient to crop the measurements (or discard measurements that are larger than a fixed, class-independent threshold)

以上文字說明因為外在因素會影響測試結果，所以會將樣本中較高執行時間的部分切除。因為我們不知道要從哪裡切，所以我們每個百分比都切切看，排除掉高位後計算不同百分比的 t-value。在實作中為了減少型二錯誤 (增加召回率 recall)，以最有可能推翻虛無假設的 t-value 作為這回合的回傳。

lab0 的實作

在 lab0 中 dudect 主要用來測試 insert, remove 是否是常數時間。檢定的方式是將產生固定 0 以及隨機 0 ~ 65536 兩類資料，而運用資料進行計算的方式是在進行插入及移除操作前先執行 $D_i\mod 10000$ 次同樣的操做，然後計算最後一次操作的時間。所以虛無假設被推翻，其實就是在暗示已經配置的記憶體數量會影響操作的時間複雜度。

實作 percentiles

commit: 1ab052c

在實作 percentiles 之後，我發現程式依然無法通過常數時間複雜度的測試，但這也在意料之內，畢竟召回率增加了，也就是對於常數時間判定會變得更嚴格。於是出於好奇我做了一件事，我讓兩個類別都變成固定的，也就是兩個類別將在記憶體幾乎沒被占用的情況下進行操作並測試時間，不測還好一測嚇一跳，虛無假設竟然被推翻了，於是我跑了 dudect 中關於 AES32 的演算法，我發現結果並非常數時間，在回到插入和移除，我似乎就不感覺意外了，接下來我想就是改善插入及移除的實作不然就是處理亂數的部分。

2024q1 Homework1 (lab0)

開發環境

指定的佇列操作

q_swap

q_reverse

q_reverseK

q_delete_dup

q_ascend

q_sort

q_merge