HackMD
2025q1 Homework1 (lab0)
contributed by < LinMarc1210 >
開發環境
動手前的學習
學習 list.h
struct list_head: 定義雙向鏈結串列的結構，包含指向下一個節點的*next以及指向上一個節點的*prevcontainer_of(ptr, type, member): 得到ptr在type這個結構裡面的記憶體位置INIT_LIST_HEAD: 初始化節點head，next和prev皆指向自己list_add: 將給定的節點加到head的nextlist_add_tail: 將給定的節點加到head的previouslist_del: 從鏈結串列中移除指定的節點list_del_init: 從鏈結串列中移除指定的節點，並且重新初始化成next和prev都指向自己的節點list_empty: 檢查head的next是否指向自己，如果是，則代表鏈結串列為空，即鏈結串列中除了head沒有其他節點list_is_singular: 檢查鏈結串列是否為空，且head->prev和head->next是否指向同一個節點，如果都是，則鏈結串列為 singularlist_splice: 將給定的鏈結串列所有節點加到head的next，head->next會指向新加入的鏈結串列的第一個節點，head->prev則不變list_splice_tail: 將給定的鏈結串列所有節點加到head的prev，head->prev會指向新加入的鏈結串列的最後一個節點，head->next則不變list_splice_init: 做list_splice並且初始化list為自己指向自己的節點，避免list仍指向原本的鏈結串列list_splice_tail_init: 做list_splice_tail並且初始化list為自己指向自己的節點，避免list仍指向原本的鏈結串列list_cut_position: 將從head_from->next到包含node的所有節點都接給head_to，head_to則不再指向原本head_to所指向的鏈結串列list_move: 用list_del移除指定節點後再加入head所指向的鏈結串列的頭list_move_tail: 用list_del移除指定節點後再加入head所指向的鏈結串列的尾list_entry: 定義為container_of(node, type, member)list_first_entry: 定義為list_entry((head)->next, type, member)，得到head->next，即鏈結串列中第一個節點在type裡面的記憶體位置，回傳一個指向type結構的指標list_last_entry: 定義為list_entry((head)->next, type, member)，得到head->prev，即鏈結串列最後一個節點在type裡面的記憶體位置，回傳一個指向type結構的指標list_for_each: 從head->next開始走訪所有節點list_for_each_entry: 從包含head->next的結構開始走訪所有包含此鏈結串列的結構list_for_each_safe: 從head->next開始走訪所有節點，並且允許移除節點，因為會同時走訪當前節點與當前節點的next所指向的節點list_for_each_entry_safe: 從head->next開始走訪所有所有包含此鏈結串列的結構，並且允許移除結構，因為會同時走訪當前結夠與當前結構裡面節點的next所指向的結構
學習 queue.h
struct
element_t: 佇列裡面的元素，結構包含字元指標value和"list.h"內建的list_head，即雙向鏈結串列的節點queue_contex_t: 包含指向佇列頭部的*q，用來將所有佇列的頭部接起來的chain，佇列長度size與佇列編號id
要實做的 function
q_new: 建一個空佇列，指向頭部的head必須要prev和next都指向自己q_free: 清空佇列所有元素，包含指向頭部的headq_insert_head: 分配記憶體給新插入在佇列頭部的元素，並且把*s的值存進新元素q_insert_tail: 分配記憶體給新插入在佇列尾端的元素，並且把*s的值存進新元素q_remove_head: 取消第一個元素與佇列的鏈結q_remove_tail: 取消最後一個元素與佇列的鏈結q_release_element: 釋放element_t元素的記憶體q_size: 回傳佇列長度q_delete_mid: 刪除中間元素，刪除是連這個元素的記憶體也要被釋放掉，而中間元素是佇列的 \(⌊n / 2⌋^{th}\) 個q_delete_dup: 刪除所有*s相同的元素，只留一個q_swap: 每兩個相鄰的元素兩兩交換，若為奇數個元素則最後一個不用交換q_reverse: 將所有元素順序反轉，且不該額外分配或釋放記憶體q_reverseK: 將佇列中前 k 個元素順序反轉q_sort: 將佇列元素排成升序或降序，根據descend決定q_ascend: 將佇列中指定元素的後面所有比他小的元素，從佇列中移除，並且釋放被移除元素的記憶體q_descend: 將佇列中指定元素的後面所有比他大的元素，從佇列中移除，並且釋放被移除元素的記憶體q_merge: 將所有佇列合併成一個已排序的佇列，根據descend決定升序或降序
修改 queue.c
q_new
首先要初始化一個空的佇列，而空的佇列需要有個指標指著它，即 head 。 head 是個指向 dummy node 的指標，用意在於讓佇列擁有起點，方便查找第一個元素和最後一個元素，而在佇列為空的時候， head->next 和 head->prev 都應該指向 head 自己。
q_free
不需要再使用佇列時，要釋放所有已分配的記憶體，包含了佇列的 head 以及內部所有 element_t 結構的元素。
因此我一開始的想法是先使用 list_del_init 解除每個節點之間的鏈結，並且再分別釋放 element_t 結構內的 list 和 value，最後釋放 element_t 元素本人的記憶體，但這樣會遇到重複釋放已未被使用的記憶體空間而導致錯誤。因此我改使用 "queue.h" 裡面定義的 q_release_element ，可以直接處理好釋放單一 element_t 元素的記憶體。
q_insert_head, q_insert_tail
當我們已經有佇列時，即有 head 指標時， q_insert_head 可以把新的元素插入在第一個元素，也就是 head->next 所指位置， q_insrt_tail 大同小異，改成插入在最後一個位置。
首先應該要先分配一個 element_t 大小的記憶體空間給心元素用，並且將傳入的字元指標 *s 複製到新建的元素的 value，在此如果用 strcpy 在記憶體管理上不太安全，因為 strcpy 在目標指標所指向字串的緩衝區不足以容納來源字串的情況下，會產生未預期的結果，此外在使用前也需先手動分配記憶體給目標字串。因此，我改用 strdup 讓函式自動分配足夠大小的記憶體，避免區段錯誤。
另外在插入元素時要檢查記憶體分配是否成功，若失敗則應回傳 false ，如果是新分配元素 new 的 value 分配失敗了，必須要在 return false 之前將成功分配的 new 給釋放掉，避免佔用記憶體。
而在實作這兩個函式的過程中僅差別在最後要將元素之間鏈結起來，必須透過 element_t 結構內嵌的 struct list_head list ，分別透過 "list.h" 定義好的 list_add 和 list_add_tail 進行插入。
q_remove_head, q_remove_tail
實作移除元素時，只需取消節點與串列的鏈結，而不須釋放記憶體。除了移除元素外，我們還需將移除元素的 value 複製到 sp ，根據 bufsize 的大小複製。 strncpy 可以根據給定的 bufsize 來決定要從哪裡複製多長的字串，而且 *sp 是已經有非配記憶體的空間，只要 sp 不為 NULL ，我們即可將字串用 strncpy 複製到 sp 。
strncpy 並不會自動分配記憶體，也不會在目標字串後面補上 \0 ，因此我們需自行補上：
而 q_remove_head 和 q_remove_tail 的差別只在於要移除第一個還是最後一個元素，因此可以分別用 head->next 和 head->prev 取得，再用 list_entry 得到他們 element_t 結構的元素，最後再用 list_del 移除即可。
q_size
回傳佇列內有幾個元素，若傳進來的 head 為 NULL 或是佇列為空則回傳 0 。
我們只需要用 list_for_each 就可以走訪所有佇列內元素並計數了。
q_delete_mid
在刪除中間元素時，我使用一個整數 index 並且搭配 list_for_each 來紀錄目前走到哪裡，當 index 現在是 \(⌊n / 2⌋^{th}\) 則讓 pos 指向該元素裡面的 list，並且再搭配 list_del 和 q_release_element 進行刪除。
q_delete_dup
考量到 q_delete_dup 傳進來的佇列是已排序的，我們只需要 \(O(n)\) 的時間複雜度，即走訪所有元素一次即可完成重複值刪除，因為重複值都會被連續地排在一起，所以檢測到重複值時就一路刪除元素，直到出現不一樣的元素值。
我使用 list_for_each_safe ，避免當前元素被刪除後，找不到下一個元素，並且使用布林值 duplicate 紀錄現在的元素是重複的還是非重複的。此外在每次迭代取得 next_entry 時，要確保 next != head ，否則在使用 list_entry 時會因為 head 所指向的節點是 dummy node 而發生錯誤。
而在比較兩者的 value 時，為什麼不能用 == 而是必須透過 strcmp ？根據 C語言規格書 6.5.9 的 6. ：
Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space.
代表 == 在兩邊運算元都是指標的情況下，會去比較的是指標所指向的記憶體位址，但 pos_entry->value 和 next_entry->value 兩者即使指向的字串相同，指標所指的記憶體位址也不同，因此直接使用 == 會誤判，若要單純比較字串是否相同或是大小就必須使用 strcmp 。
q_reverse
反轉所有元素時，也就是把當前節點 pos 的 pos->prev 和 pos->next 所指向的節點交換。此外，連 head->prev 和 head->next 所指向的節點也應該交換，才能確保仍然是雙向環狀鏈結串列。
想法：或許可以直接用
list_move來做就好，不用再手動交換指標。
q_reverseK
q_reverseK 使得每 K 個元素反轉一次，若不足 K 個元素則不反轉。首先判斷 head 為 NULL 或佇列只有 0 或 1 個元素，則直接回傳。在每次迭代都把一組元素反轉，因此每次會先找該組的開頭以及結尾。
讓 start 停在 K 個元素的前一個，而 end 停在 K 個元素的後一個。並且走訪中間的 K 個元素，依序將其 next 與 prev 指向的元素交換。中間我加了判斷目前是否為 K 個元素裡的第一個或最後一個，使得反轉完能維持雙向環狀鏈結串列。
最後再更新 start 和 prev 並且進行下一次迭代。
q_sort
想法
根據 q_sort 的要求，排序演算法應該要保持 Stable Sort ，因此我選擇使用 Merge Sort 來實作，在相同元素值被排序後仍可以保持原本的相對順序。
為什麼用 Merge Sort 而不是 Quick Sort ？首先我們需要找一個可以保持 Stable Sort 的演算法，而兩者皆可在實作上確保這一點，但在時間複雜度上， Merge Sort 不管在最佳或是最糟情況都是 \(O(n\,log\,n)\) ，但是 Quick Sort 只在最佳情況是 \(O(n\,log\,n)\) ，在最糟情況，也就是已排序的串列，會來到 \(O(n^2)\) 。
| Best | Average | Worst | |
|---|---|---|---|
| Merge Sort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n\log n)\) |
| Quick Sort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(n^2)\) |
為什麼用 Merge Sort 而不是 Quick Sort ？首先我們需要找一個可以保持 Stable Sort 的演算法，而兩者皆可在實作上確保這一點，但在時間複雜度上， Merge Sort 不管在最佳或是最糟情況都是 \(O(n\log n)\) ，但是 Quick Sort 只在最佳情況是 \(O(n\log n)\) ，在最糟情況，即已排序的串列，會來到 \(O(n^2)\) 。
實作
一開始實作遞迴版 Quick Sort 雖然可正確排序，但在測試效能時會出現警告，分別是 Time Limit Exceed 和記憶體未被釋放的警告，實際上就是因為超過時間了，所以程式沒跑完，因此也沒釋放掉記憶體。
由前面可知，遞迴版的 Quick Sort 時間複雜度上不可行，因此接下來改用 Merge Sort 。
遞迴版 Merge Sort 必須先將串列分成兩半，因此我們使用快慢指標的手法，使得 slow 每次走一步，而 fast 每次走兩步，讓 slow 在最後停在串列的中間元素。
接下來要將佇列分成兩半，因此需要兩個 dummy node ，分別代表兩半的串列，我們需要再另外創建一個 dummy node 來代表前半佇列。注意在這裡是宣告真實的 list_head 節點而不是指標，若宣告指標則會需要有實際的記憶體位址給指標指。切完後再遞迴呼叫，並且使用 merge_two 兩兩合併。
-
那如果是 indirect pointer v.s. dummy node 呢？
即使是 indirect pointer ，最後還是需要另一個新的 dummy node 來指向另一半的佇列頭部。假如我們先借用既有的 dummy node：
struct list_head **left = &head;
這樣的宣告方式會使得後續更改*left時，會連動更改了 head 所指向的地址。
merge_two
merge_two 為輔助 q_sort 的函式，目的在合併兩個給定的佇列並用 head 當作佇列的 dummy node 指標。若我們直接針對給定的 head 和 target 做移動元素，會在用迴圈走訪的時候導致走訪順序亂掉，因此我們另外宣告實際的 list_head 節點 pos 作為 dummy node，在稍後依序存放已排序的節點。
而在迴圈內我們改用 list_first_entry 取代 list_entry ，因為每次都是拿 target 和 head 串列的剩餘第一個元素來比較值，並且放到 &pos 串列，因此用 list_first_entry ，這樣的好處是不用再另外開兩個 struct list_head * 來分別走訪兩個串列，每次取得元素只需要拿 target 和 head 就好。
此外我們將剩餘部份也用 list_splice_tail_init 來貼至 &pos ，注意這邊不能用 list_splice_tail ，這樣在 head 串列沒有節點之後，head 仍會指向已被貼過去的節點，導致最後使用 list_splice(&pos, head) 時，head->next 並沒有指向正確的節點而發生 dereference a NULL pointer。
另外最後不能直接更改 head 為 pos ，而是使用 list_splice 才對，因為 head = &pos 只是改變 head 指向 pos 而已，使得 head 無法實際透過 next 和 prev 走訪我們已排序完的元素。
問題
-
延伸：如果 head 是 null 可是 target 不是呢？
實際上不會發生，因為 target 和 head 是透過快慢指標決定切在哪的，當總長是偶數，兩者一樣長，而當總長是奇數時，後半部會比前半部多一個元素，即
head會比target多一個。 -
延伸：能不能優化
q_sort？根據Merge Sort 與它的變化裡面迭代版與遞迴版的效能分析，首先可將迭代版的 Merge Sort 分成兩階段：分割出好幾個串列，以及合併這些串列。可以得知在 Divide 函式選擇用分割出排序好的串列， Merge 函式選擇用分治法的情況下，在順序打亂、排序好、順序相反的情況下，迭代版 Merge Sort 都比一般遞迴版更快，或許可以改用迭代版本的 Merge Sort 實作
q_sort。
q_ascend, q_descend
q_ascend 和 q_descend 分別是檢查當前節點的所有後面元素，是否有 value 比他小 / 比他大的，若有則刪除當前節點 pos_entry 。這邊講的是刪除，因此除了取消鏈結外，還要釋放記憶體。
我的想法是使用 list_for_each_safe ，這樣可以確保刪除當前節點 pos 後，還是能存取下一個元素，而 pos 內嵌在 pos_entry 裡面的 list_head 結構。此外在檢查當前節點時，另外宣告一個 right 指標指向 &pos->next ，用 right 來走訪後面所有元素，並且在下一次 list_for_each_safe 的迭代重置 right 指向的元素。
需要注意的是，我們需要先取消 pos 與其他節點的鏈結，才可以釋放整個 pos_entry 的記憶體，避免 pos 仍存在於鏈結串列中。
q_ascend 和 q_descend 只差別在於內部 if 的條件判斷。
q_merge
q_merge 要將所有的佇列合併成一個佇列並排序，並且是合併到第一個佇列的 head 。這邊傳進來的 head 並不是用來存取一個 element_t 佇列的，而是存取整個 queue_contex_t 的鏈結串列，可以想像成單一個佇列裡面是由 element_t 作為元素，而所有佇列合起來又是一個大型鏈結串列，其中每個元素為 queue_contex_t 結構，代表一個佇列。
我首先透過 list_first_entry 來取得第一個佇列，並且用 list_for_each_entry_safe 走訪所有 entry ，在這裡每個 entry 不是一個元素，而是一整個佇列，因此在迴圈內就依序將走訪到的佇列之所有元素移至 target 指向的佇列，最後再呼叫 q_sort 將所有元素進行排序。
在將佇列合併的過程中，必須將被合併的佇列之 dummy node 使用 INIT_LIST_HEAD 重新初始化 entry->q ，避免仍指到已經被合併的節點。
- 延伸：先合併再排序，還是邊合併邊排序比較好？
Valgrind + 自動測試程式
透過 Massif 視覺化 simulation 過程中的記憶體使用量
先透過 valgrind 來查看 "queue.c" 的實作狀況，觀察在測資 17 跑的狀況：
實作 percentile 處理前：
原程式透過 malloc_or_fail 和 test_malloc 去分配記憶體，分別在 "report.c" 和 "harness.c" ，用來測試程式是否分配記憶體成功。
實作 percentile 處理後：
doit 在實作後突然就佔用了很多的記憶體，可能是程式裡有未被釋放的記憶體，因此檢查一下可發現我有在 doit 新增 percentile ，也要有相對應的釋放。
重測一次之後 doit 的記憶體用量就下降到低比例了。
亂數
訊息熵 (Entropy)
熵是訊息本身不確定性的量度，對於一個離散型隨機變數 \(X\) ，熵的定義如下：
\(H(X) = \mathsf E_{x \sim X} \left[-\log \mathsf P_X(x) \right] = \sum_{x}- \mathsf P_X \log \mathsf P_X (x)\)
作者在解釋熵之前先用資料壓縮舉例，並說明我們給定一個 \(\epsilon\) ，透過演算法生出的 decoder 解碼錯誤機率應該低於這個數值，並且根據不同的 \(n\) 值探討不同的 encoder 和 decoder 來解釋。一個降低錯誤率至 \(n\) 以下的方法是不斷收集長度不同的序列至集合 \(S^n\) ，直到這些序列出現的總機率超過 \(1-\epsilon\) 。
給定 \(\epsilon \in (0,1)\) 且 \(n \in \Bbb N\) ，稱集合 \(\mathcal{B} (n, \epsilon) \subseteq \mathcal{S}^n\) 為一個 \(\epsilon\)-high probability set 若且唯若
\(\mathsf{Pr} \{ s^n \in \mathcal B (n, \epsilon) \} \overset{(2)} = \sum_{s^n \in \mathcal B(n, \epsilon)} \left( \prod_{i = 1}^n \mathsf P_S(s_i) \right) \ge 1 - \epsilon\)
為了達到error probability小於 \(\epsilon\) ，我們只需要 \(\left| \mathcal B(n, \epsilon) \right|\) 個獨一無二的二進制編碼即可，也就是說，我們一旦找到最小的 \(k\) 使得 \(2^k \ge \left| \mathcal B(n, \epsilon) \right|\) ，即可用 \(k\) 個位元的代價完成一個 error probability 在 \(\epsilon\) 之下的訊息壓縮。
然而筆者提到這樣的方法難以捕捉隨著 \(n\) 變大可達到的壓縮比變化趨勢為何，因此改用大數法則分析。
筆者用丟骰子的粒子很簡單舉例了如果我們丟很多次公正骰子，那將所有點數相加並除以 6 ，其結果剛好會是期望值 3.5 的機率趨近為 1 。套用回壓縮訊息，當 \(n\) 夠大則序列中每個字母出現次數的平均，再與 \(f\) 的期望值相減不超過 \(\delta\) 的機率趨近於 1 。為了讓原本 \(s_n\) 的機率連乘改成機率相加，在等式兩邊取對數即可，因此推導出 Shannon Entropy 的函數，即對於任意 \(n\) 都足夠小的 \(\left| \mathcal B(n, \epsilon) \right|\) ，完成錯誤機率在 \(\epsilon\) 底下的訊息壓縮。因此 entropy 是我們可以達到的最好壓縮比，若 entropy 越大，則越難進行壓縮，也就是所需的資訊量越大，因此可應證「資訊與熵互補，資訊就是負熵」。
觀察 qtest 的 entropy
觀察每個字串的 entropy 可以發現影響字串的熵的因素是字串內出現過多少個字母，比如 ridykbl 和 uynbglfg 雖然長度不同，但都出現 7 個字母，因此其 entropy 是相同的。其計算方式是根據程式內的 shannon_entropy 進行計算。
實作新的命令切換不同的 PRNG
追蹤程式發現 ih RAND 10 會將 need_rand 設置為 true 並呼叫 fill_rand_string ，並且使用內建的 rand 和 randombytes 決定字串長度和填充不同字母。
我在這邊做了一些小更動，改成用 if 來決定要用 Xorshift 還是用內建的亂數產生器來做隨機字串的產生，參考 Xorshift 發現 xorshift 是透過位移和 XOR 運算取得序列中的下一個數字，因此我另外開了一個 "xorshift.h" 和 "xorshift.c" ，在裡面實作使用時間作為種子並且套用 xorshift 的方法產生亂數序列。
並且改一下 Makefile 讓 "qtest.c" 和 "xorshift.c" 可以連結在一起，此外在 "console.c" 加入 option prng ，這個命令可以改變 change_prng 的值，因此可以用 change_prng 來區分現在用的是內建還是 Xorshift 的 PRNG。
- 內建 PRNG
- Xorshift PRNG
透過統計分析 Xorshift 和內建 PRNG 比較
在 qtest 提供新的命令 shuffle
首先在 queue.c 實作 shuffle 的過程，因此我們需要先寫一個函式 q_shuffle ，並且使用 Fisher-Yates Shuffle 演算法的步驟來實作。按照作業說明，演算法有以下三步：
- 先用
q_size取得 queue 的大小len。 - 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第
random個節點，new會指向最後一個未被抽到的節點，將old和new指向的節點的值交換，再將 len - 1。 - 隨著
len大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle就結束。
因此我根據上述步驟在 queue.[ch] 實作 q_shuffle 的宣告與定義，並且在交換兩節點的步驟使用 list_move 來讓程式碼看起來更精簡。
在做完 q_shuffle 之後，要到 "qtest.c" 新增命令，讓使用者可以輸入 shuffle 以對佇列元素進行重新排列，並且透過 do_shuffle 呼叫 q_shuffle 實際進行洗牌，這樣使用者就可以將輸入的命令和洗牌的動作連結起來了。 do_shuffle 的實作方法參考 do_swap ，因為都只吃一個參數、禁止分配額外記憶體、並直接呼叫在 queue.c 裡面的相關函式。
這樣就完成了在 qtest 新增 shuffle 命令，但由於不可更改 "queue.h" ，因此將 qtest 裡的相關變更註解掉，避免發生錯誤。
統計方法驗證 shuffle
使用 lab0(D) 的 Python 測試程式，並且將洗牌次數調整為 100000 ，觀察每種排列出現的次數，會得到以下結果：
根據圖解，排列的出現次數呈現 uniform distribution。此外根據我們排列有 24 種，可得到自由度為 23，而我們的 chi-square sum (\(\chi^2\)) 為 26.64 ，查卡方分佈表可知 p-value 介於 0.1~0.9 ，因為 P value（0.1~0.9）> alpha（0.05），統計檢定的結果不拒絕虛無假說 (\(H_0\)) ，也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻。
研讀論文〈 Dude, is my code constant time? 〉
在 Introduction 中，作者先介紹了 Timing attacks 的興起，攻擊者通過測量加密算法運算時所需的執行時間，從中推測出密鑰或其他機密數據。之後，許多非常數時間的實作就被成功攻擊，而 Timing Attack 的優勢在於只需要測量執行時間變化即可，甚至可以遠端進行。
傳統上，要檢查一段程式碼是否以常數時間運行，需要手動檢查組合語言層面的代碼，觀察是否有基於秘密數據而改變執行路徑的指令（例如分支或記憶體存取），而這樣的手動檢查很耗時間。雖然已有其他工具幫助檢查，但這些方法需要建立硬體模型來預測 CPU 的行為，而實際上 CPU 製造商通常不會公開詳細的內部工作機制，甚至受到微程式更新等影響，使得準確建模變得非常困難。因此作者提出 dudect 工具，以 leakage detection tests 的觀念和對執行時間的統計分析，實作出方法簡單且可以規避如何模擬硬體問題的工具。
Timing Leakage Detection 的方法
基本概念是檢查在不同輸入條件下，執行同一加密函數所耗費的時間分布是否存在統計上的差異，若有顯著不同，則可能存在依賴數據的 Timing Leakage，因此做法在論文中為以下三步：
- Measure execution time : 通過對兩種不同類型輸入（固定與隨機）的大量執行時間測量，來分析並檢測是否存在統計上顯著的差異
- Apply post-processing : 對測量數據進行後處理，過濾掉一些 outlier ，並進行一些數據轉換提高統計檢測的靈敏度
- Apply statistical test : 利用 t-test 來判斷兩組執行時間數據分布是否存在顯著差異，也就是檢測是否存在 timing leakage，並且推翻虛無假說：兩組執行時間分佈是相等的。
程式碼的 simulation 模式與 Student's t-distribution
參考 salmoniscute
lab0-c 的測資 17 檢查程式是否運行在常數時間，打開第 17 筆測資發現第一行為 option simulation 1 ，接著檢查 "qtest.c" 發現 simulation 為 1 時會呼叫 is_insert_tail_const, is_insert_head_const, is_remove_tail_const, is_remove_tail_const ，而在 "fixture.c" 則有定義如下，當我們執行這四個函式，會去呼叫 test_const 測試他們是否為常數時間。
而 test_const 最多會測試 TEST_TRIES 次，每次呼叫 doit 來測試是否為常數時間， doit 會呼叫 maesure 做執行時間的計算，並且再呼叫 update_statistics 來執行 t_push ，也就是做一次 t-test。
Student's t-distribution 通常用於樣本數小且母體標準差未知的情況下的一種連續機率分佈，用於 Student's t-test 進行顯著性測試的基礎，而在 Student's t-test 則有幾個應用，其中的雙樣本 t-test 則是我們會用來檢驗常數時間的檢定，其假說檢定如下，虛無假說為兩母體的變異數相等，當我們拒絕虛無假說時，可說明兩母體之間可能有顯著差異。
- \(H_0\) ：\(\sigma_1^2 = \sigma_2^2\)
- \(H_0\) ：\(\sigma_1^2 \ne \sigma_2^2\)
而 "ttest.c" 所實作的是 Welch's t-test，其放寬母體的條件為母體標準差不一定要相等，並將假說檢定更改如下，而這樣子的檢定更適合對程式執行時間進行統計分析，因為現實情況的執行時間往往受到軟硬體干擾，如論文所述。
- \(H_0\) ：\(\mu_1 = \mu_2\)
- \(H_0\) ：\(\mu_1 \ne \mu_2\)
"ttest.c" 的三個函式說明如下：
t_push：用 Welford Method 更新平均值和累計平方差t_compute：計算 t 值作為檢定的統計量
\[ t = \frac{\bar{x}_1 - \bar{x}_2}{\sqrt{\frac{s_1^2}{n_1} + \frac{s_2^2}{n_2}}} \]t_init：重置計算 t 值所需要的變數
Percentile 的處理
Percentile 的設定是為了達成論文中提及的 Cropping ，即刪除一些導致分佈呈現右偏態的值，這些值通常是受到做作業系統或其他條件影響導致時間變長。在 oreparaz/dutect 中，作者使用以下公式，可以根據樣本的分佈決定閾值要設定多少，再根據閾值進行 Cropping ，此公式隨著 i 增加，值的變化從 0 到 1，再經由 percentile 函式計算該閾值樣本的位置。
最後回到 update_statistics ，只有在 difference 不超過閾值的樣本才會被加到 t-test 進行檢定。
幫 lab0-c 加上 Percentile 處理
根據 oreparaz/dutect ，我們在 "fixture.c" 加入新的函式為 percentile, prepare_percentile, cmp ，並且更新 update_statistics 和 doit ，加上檢查閾值。
doit
update_statistics
完成更新並 push 之後就有看到星之卡比了。
Linux 核心的鏈結串列排序
參考 EricccTaiwan
相關論文
- Bottom-up Mergesort: A Detailed Analysis
- The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules
- Queue-mergesort
研讀並引入 lib/list_sort.c
"list_sort.c" 採用 bottom-up 合併排序的策略，但是改用深度優先取代廣度優先的順序，並且維持 2:1 的合併。其規定是若現在有兩個待合併且長度為 \(2^k\) ，他們會等到又有 \(2^k\) 個元素待合併的時候才會將前兩個串列合併成長度為 \(2^{k+1}\) 的串列。參考 Linux 核心專題：改進 lib/list_sort.c 的解說錄影，才知道這樣做的原因是避免頻繁發生 cache miss，若我們使用如 Linux 核心的合併排序，這樣可確保元素剛被存取過，仍在 cache 的上方時就進行合併，而且每次存取與合併都是 \(3\cdot 2^k\) 元素，也不超過快取大小。
接下來觀察 list_sort 函式的程式碼，其使用 pending 指標紀錄剛剛所說的待合併串列，並且用 count 紀錄合併的時機。核心程式碼的註解有提到 count 所控制的六種狀態，其中 merge 發生在 state 的變化為 2->3 和 4->5 ，我們可以各得到一個長度為 \(2^k\) 的串列，並且在 state 從 5->2 時合併。
There are six states we distinguish. "x" represents some arbitrary
bits, and "y" represents some arbitrary non-zero bits:
0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
(merge and loop back to state 2)
以下則用表格呈現若我們有 7 個元素要排的時候，會分別是什麼樣的狀態：
pending：比如結構為 4 \(\leftarrow\) 2 \(\leftarrow\) 1 ，代表分別有長度為 4, 2, 1 的子串列。count：在pending裡的節點總數state：檢查目前pending的狀態，在程式碼裡為bits- 螢光筆：代表在下一步要合併時，
tail和tail->prev分別指向的位置。
count |
檢查是否 merge | 對應的 state | pending 上面的結構 |
|---|---|---|---|
| 0000 | no | 00x | NULL |
| 0001 | no | 01x | 1 |
| 0010 | no | x10x | 1 \(\leftarrow\) 1 |
| 0011 | yes (state: 2 \(\to\) 3) | x11x | 2 \(\leftarrow\) 1 |
| 0100 | no | y00x | 2 \(\leftarrow\) 1 \(\leftarrow\) 1 |
| 0101 | yes (state: 4 \(\to\) 5) | y01x | 2 \(\leftarrow\) 2 \(\leftarrow\) 1 |
| 0110 | yes (state: 5 \(\to\) 2) | x10x | 4 \(\leftarrow\) 1 \(\leftarrow\) 1 |
| 0111 | yes (state: 2 \(\to\) 3) | x11x | 4 \(\leftarrow\) 2 \(\leftarrow\) 1 |
程式碼則是用以下方式來檢查現在的 state ，尋找 bits 的最低 0 位元，決定接下來是否需要合併，並且更新 tail 的位置來決定要合併 pending 裡面的哪兩個串列。
在 list 的所有節點都被加到 pending 之後，會將所有節點合併起來，此時子串列才有可能出現長度不是 2 的冪，另外由於前面的 do-while 迴圈中都是以單向鏈結串列做合併的，因此在最後要將 pending 整個結構合併起來，並復原成雙向環狀鏈結串列。
效能分析
接下來我們將 list_sort.c 的程式碼也引入到 qtest.c ，新增函式為 q_list_sort，並且在 qtest 新增命令 listsort 來執行 Linux 核心的排序。由於在核心內有 comparator 作為 function pointer 傳入，我們也自行針對作業比較字串的規定寫了一個，並且使用 strcmp 的結果當作回傳值。
在 Bottom-up Mergesort: A Detailed Analysis 有提到對於 Best-case, Worst-case, Average-case 的比較次數是根據單一次 merge 的劃分來做區隔的，論文隨後提供了一個公式說明比較次數 \(c_{n,m}\) 的上下界：
The cost measures \(C_{b,bu}(N)\), \(C_{w,bu}(N)\), and \(C_{a,bu}(N)\) are, of course, ultimately based on the quantities \(c_{n,m}\) ,denoting the number of comparisons in the single (n, m) merge processes.
\[ \min \{n,m\} \leq c_{n,m} \leq n+m-1 \]
這樣的公式是因為 merge 最差情況是兩個子串列元素的值完美交錯
使得每個元素都需要比較，直到只剩一個。而最好情況則是比較時都是較短的子串列被 merge ，那較長的子串列就直接加到後面即可。
- [1,2,3] [4,5,6] 只需 3 次比較即可完成：(1,4), (2,4), (3,4)
- [1,3,5] [2,4,6] 需要 5 次比較才可完成：(1,2), (3,2), (3,4), (5,4), (5,6)
