2025q1 Homework1 (lab0)

contributed by < LinMarc1210 >

作業書寫規範:

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

$ 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):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                GenuineIntel
  Model name:             12th Gen Intel(R) Core(TM) i7-1260P
    CPU family:           6
    Model:                154
    Thread(s) per core:   2
    Core(s) per socket:   12
    Socket(s):            1
    Stepping:             3
    CPU(s) scaling MHz:   21%
    CPU max MHz:          4700.0000
    CPU min MHz:          400.0000
    BogoMIPS:             4992.00
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge m
                          ca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 s
                          s ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc 
                          art arch_perfmon pebs bts rep_good nopl xtopology nons
                          top_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq 
                          dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma c
                          x16 xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_de
                          adline_timer aes xsave avx f16c rdrand lahf_lm abm 3dn
                          owprefetch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_e
                          nhanced tpr_shadow flexpriority ept vpid ept_ad fsgsba
                          se tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed 
                          adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsav
                          ec xgetbv1 xsaves split_lock_detect user_shstk avx_vnn
                          i dtherm ida arat pln pts hwp hwp_notify hwp_act_windo
                          w hwp_epp hwp_pkg_req hfi vnmi umip pku ospke waitpkg 
                          gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_c
                          lear serialize arch_lbr ibt flush_l1d arch_capabilitie
                          s
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    448 KiB (12 instances)
  L1i:                    640 KiB (12 instances)
  L2:                     9 MiB (6 instances)
  L3:                     18 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-15
Vulnerabilities:          
  Gather data sampling:   Not affected
  Itlb multihit:          Not affected
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Not affected
  Reg file data sampling: Mitigation; Clear Register File
  Retbleed:               Not affected
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prct
                          l
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointe
                          r sanitization
  Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditiona
                          l; RSB filling; PBRSB-eIBRS SW sequence; BHI BHI_DIS_S
  Srbds:                  Not affected
  Tsx async abort:        Not affected

動手前的學習

學習 list.h

struct list_head: 定義雙向鏈結串列的結構，包含指向下一個節點的 *next 以及指向上一個節點的 *prev
container_of(ptr, type, member): 得到 ptr 在 type 這個結構裡面的記憶體位置
INIT_LIST_HEAD: 初始化節點 head ， next 和 prev 皆指向自己
list_add: 將給定的節點加到 head 的 next
list_add_tail: 將給定的節點加到 head 的 previous
list_del: 從鏈結串列中移除指定的節點
list_del_init: 從鏈結串列中移除指定的節點，並且重新初始化成 next 和 prev 都指向自己的節點
list_empty: 檢查 head 的 next 是否指向自己，如果是，則代表鏈結串列為空，即鏈結串列中除了 head 沒有其他節點
list_is_singular: 檢查鏈結串列是否為空，且 head->prev 和 head->next 是否指向同一個節點，如果都是，則鏈結串列為 singular
list_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: 清空佇列所有元素，包含指向頭部的 head
q_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 ⌋^{t h}$ 個
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 元素的記憶體。

list_for_each_safe (pos, next, head) {
    element_t *entry = list_entry(pos, element_t, list);
-    list_del_init(pos);
-    free(pos);
-    free(entry->value);
-    free(entry);
+    q_release_element(entry);
}
free(head);

q_insert_head, q_insert_tail

當我們已經有佇列時，即有 head 指標時， q_insert_head 可以把新的元素插入在第一個元素，也就是 head->next 所指位置， q_insrt_tail 大同小異，改成插入在最後一個位置。

首先應該要先分配一個 element_t 大小的記憶體空間給心元素用，並且將傳入的字元指標 *s 複製到新建的元素的 value，在此如果用 strcpy 在記憶體管理上不太安全，因為 strcpy 在目標指標所指向字串的緩衝區不足以容納來源字串的情況下，會產生未預期的結果，此外在使用前也需先手動分配記憶體給目標字串。因此，我改用 strdup 讓函式自動分配足夠大小的記憶體，避免區段錯誤。

- strcpy(new->value, s);
+ new->value = strdup(s);

另外在插入元素時要檢查記憶體分配是否成功，若失敗則應回傳 false ，如果是新分配元素 new 的 value 分配失敗了，必須要在 return false 之前將成功分配的 new 給釋放掉，避免佔用記憶體。

if (!new->value) {
    free(new);
    return false;
}

而在實作這兩個函式的過程中僅差別在最後要將元素之間鏈結起來，必須透過 element_t 結構內嵌的 struct list_head list ，分別透過 "list.h" 定義好的 list_add 和 list_add_tail 進行插入。

list_add(&new->list, head);
list_add_tail(&new->list, head);

q_remove_head, q_remove_tail

實作移除元素時，只需取消節點與串列的鏈結，而不須釋放記憶體。除了移除元素外，我們還需將移除元素的 value 複製到 sp ，根據 bufsize 的大小複製。 strncpy 可以根據給定的 bufsize 來決定要從哪裡複製多長的字串，而且 *sp 是已經有非配記憶體的空間，只要 sp 不為 NULL ，我們即可將字串用 strncpy 複製到 sp 。

strncpy 並不會自動分配記憶體，也不會在目標字串後面補上 \0 ，因此我們需自行補上：

sp[bufsize - 1] = '\0';

而 q_remove_head 和 q_remove_tail 的差別只在於要移除第一個還是最後一個元素，因此可以分別用 head->next 和 head->prev 取得，再用 list_entry 得到他們 element_t 結構的元素，最後再用 list_del 移除即可。

q_size

回傳佇列內有幾個元素，若傳進來的 head 為 NULL 或是佇列為空則回傳 0 。

if (!head || list_empty(head)) {
    return 0;
}

我們只需要用 list_for_each 就可以走訪所有佇列內元素並計數了。

list_for_each (pos, head) {
    size++;
}

q_delete_mid

在刪除中間元素時，我使用一個整數 index 並且搭配 list_for_each 來紀錄目前走到哪裡，當 index 現在是

⌊ n / 2 ⌋^{t h}

則讓 pos 指向該元素裡面的 list，並且再搭配 list_del 和 q_release_element 進行刪除。

list_for_each (pos, head) {
    if (index == q_size(head) / 2) {
        break;
    }
    index++;
}
element_t *entry = list_entry(pos, element_t, list);
list_del(pos);
q_release_element(entry);

q_delete_dup

考量到 q_delete_dup 傳進來的佇列是已排序的，我們只需要

O (n)

的時間複雜度，即走訪所有元素一次即可完成重複值刪除，因為重複值都會被連續地排在一起，所以檢測到重複值時就一路刪除元素，直到出現不一樣的元素值。

我使用 list_for_each_safe ，避免當前元素被刪除後，找不到下一個元素，並且使用布林值 duplicate 紀錄現在的元素是重複的還是非重複的。此外在每次迭代取得 next_entry 時，要確保 next != head ，否則在使用 list_entry 時會因為 head 所指向的節點是 dummy node 而發生錯誤。

- const element_t *next_entry = list_entry(next, element_t, list);
+ const element_t *next_entry =
+     (next == head) ? NULL : list_entry(next, element_t, list);

而在比較兩者的 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 。

- if (pos_entry->value == next_entry->value)
+ if (strcmp(pos_entry->value, next_entry->value) == 0)

q_reverse

反轉所有元素時，也就是把當前節點 pos 的 pos->prev 和 pos->next 所指向的節點交換。此外，連 head->prev 和 head->next 所指向的節點也應該交換，才能確保仍然是雙向環狀鏈結串列。

想法：或許可以直接用 list_move 來做就好，不用再手動交換指標。

q_reverseK

q_reverseK 使得每 K 個元素反轉一次，若不足 K 個元素則不反轉。首先判斷 head 為 NULL 或佇列只有 0 或 1 個元素，則直接回傳。在每次迭代都把一組元素反轉，因此每次會先找該組的開頭以及結尾。

for (end = start->next; end != head && counter < k;
     end = end->next, counter++)
    ;

讓 start 停在 K 個元素的前一個，而 end 停在 K 個元素的後一個。並且走訪中間的 K 個元素，依序將其 next 與 prev 指向的元素交換。中間我加了判斷目前是否為 K 個元素裡的第一個或最後一個，使得反轉完能維持雙向環狀鏈結串列。

while (pos != end) {
    struct list_head *tmp = pos->next;
    if (pos->prev != start)
        pos->next = pos->prev;
    else
        pos->next = end;
    if (tmp != end)
        pos->prev = tmp;
    else
        pos->prev = start;
    pos = tmp;
}

最後再更新 start 和 prev 並且進行下一次迭代。

q_sort

想法

根據 q_sort 的要求，排序演算法應該要保持 Stable Sort ，因此我選擇使用 Merge Sort 來實作，在相同元素值被排序後仍可以保持原本的相對順序。

為什麼用 Merge Sort 而不是 Quick Sort ？首先我們需要找一個可以保持 Stable Sort 的演算法，而兩者皆可在實作上確保這一點，但在時間複雜度上， Merge Sort 不管在最佳或是最糟情況都是

O (n l o g n)

，但是 Quick Sort 只在最佳情況是

O (n l o g 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})$

O (n \log n)

，但是 Quick Sort 只在最佳情況是

O (n \log n)

，在最糟情況，即已排序的串列，會來到

O (n^{2})

。

# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected 
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass

實作

一開始實作遞迴版 Quick Sort 雖然可正確排序，但在測試效能時會出現警告，分別是 Time Limit Exceed 和記憶體未被釋放的警告，實際上就是因為超過時間了，所以程式沒跑完，因此也沒釋放掉記憶體。

+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Freed queue, but 4000000 blocks are still allocated
---	trace-14-perf	0/6

由前面可知，遞迴版的 Quick Sort 時間複雜度上不可行，因此接下來改用 Merge Sort 。
遞迴版 Merge Sort 必須先將串列分成兩半，因此我們使用快慢指標的手法，使得 slow 每次走一步，而 fast 每次走兩步，讓 slow 在最後停在串列的中間元素。

int count = q_size(head) / 2;
struct list_head *slow = head, *fast = head->next;
for (; count; slow = slow->next, fast = fast->next->next, count--)
    ;

接下來要將佇列分成兩半，因此需要兩個 dummy node ，分別代表兩半的串列，我們需要再另外創建一個 dummy node 來代表前半佇列。注意在這裡是宣告真實的 list_head 節點而不是指標，若宣告指標則會需要有實際的記憶體位址給指標指。切完後再遞迴呼叫，並且使用 merge_two 兩兩合併。

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

那如果是 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 就好。

- struct list_head *l = target->next;
- struct list_head *r = head->next;

while (!list_empty(head) && !list_empty(target)) {
-     element_t *l_entry = list_entry(l, element_t, list);
-     element_t *r_entry = list_entry(r, element_t, list);
+     element_t *l_entry = list_first_entry(target, element_t, list);
+     element_t *r_entry = list_first_entry(head, element_t, list);
    ...
}

此外我們將剩餘部份也用 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 = &pos;
+ list_splice(&pos, head);

問題

延伸：如果 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 指向的元素。














list_for_each_safe (pos, pos_safe, head) {
    struct list_head *right = pos->next;
    element_t *pos_entry = list_entry(pos, element_t, list);

    while (right != head) {
        const element_t *right_entry = list_entry(right, element_t, list);
        if (strcmp(pos_entry->value, right_entry->value) > 0) {
            list_del(pos);
            q_release_element(pos_entry);
            break;
        }
        right = right->next;
    }
}

需要注意的是，我們需要先取消 pos 與其他節點的鏈結，才可以釋放整個 pos_entry 的記憶體，避免 pos 仍存在於鏈結串列中。

list_del(pos);
q_release_element(pos_entry);

q_ascend 和 q_descend 只差別在於內部 if 的條件判斷。

if (strcmp(pos_entry->value, right_entry->value) > 0) // q_ascend
if (strcmp(pos_entry->value, right_entry->value) < 0) // q_descend

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 ，避免仍指到已經被合併的節點。

if (entry != target && entry->q && !list_empty(entry->q)) {
    list_splice_tail(entry->q, target->q);
    INIT_LIST_HEAD(entry->q);
}

延伸：先合併再排序，還是邊合併邊排序比較好？

Valgrind + 自動測試程式

透過 Massif 視覺化 simulation 過程中的記憶體使用量

先透過 valgrind 來查看 "queue.c" 的實作狀況，觀察在測資 17 跑的狀況：

$ valgrind --tool=massif ./qtest -f ./traces/trace-17-complexity.cmd

$ massif-visualizer massif.out.<pid>

實作 percentile 處理前：

原程式透過 malloc_or_fail 和 test_malloc 去分配記憶體，分別在 "report.c" 和 "harness.c" ，用來測試程式是否分配記憶體成功。

實作 percentile 處理後：

doit 在實作後突然就佔用了很多的記憶體，可能是程式裡有未被釋放的記憶體，因此檢查一下可發現我有在 doit 新增 percentile ，也要有相對應的釋放。

free(before_ticks);
free(after_ticks);
free(exec_times);
free(classes);
free(input_data);
+ free(percentile);

重測一次之後 doit 的記憶體用量就下降到低比例了。

亂數

訊息熵 (Entropy)

由大數法則理解訊息熵 (entropy) 的數學意義

熵是訊息本身不確定性的量度，對於一個離散型隨機變數

X

，熵的定義如下：

H (X) = E_{x \sim X} [- \log P_{X} (x)] = \sum_{x} - P_{X} \log P_{X} (x)

作者在解釋熵之前先用資料壓縮舉例，並說明我們給定一個

ϵ

，透過演算法生出的 decoder 解碼錯誤機率應該低於這個數值，並且根據不同的

n

值探討不同的 encoder 和 decoder 來解釋。一個降低錯誤率至

n

以下的方法是不斷收集長度不同的序列至集合

S^{n}

，直到這些序列出現的總機率超過

1 - ϵ

。

給定
$ϵ \in (0, 1)$ 且
$n \in N$ ，稱集合
$B (n, ϵ) \subseteq S^{n}$ 為一個
$ϵ$ -high probability set 若且唯若

$\Pr {s^{n} \in B (n, ϵ)} \overset{(2)}{=} \sum_{s^{n} \in B (n, ϵ)} (\prod_{i = 1}^{n} P_{S} (s_{i})) \geq 1 - ϵ$

為了達到error probability小於
$ϵ$ ，我們只需要
$| B (n, ϵ) |$ 個獨一無二的二進制編碼即可，也就是說，我們一旦找到最小的
$k$ 使得
$2^{k} \geq | B (n, ϵ) |$ ，即可用
$k$ 個位元的代價完成一個 error probability 在
$ϵ$ 之下的訊息壓縮。

然而筆者提到這樣的方法難以捕捉隨著

n

變大可達到的壓縮比變化趨勢為何，因此改用大數法則分析。

筆者用丟骰子的粒子很簡單舉例了如果我們丟很多次公正骰子，那將所有點數相加並除以 6 ，其結果剛好會是期望值 3.5 的機率趨近為 1 。套用回壓縮訊息，當

n

夠大則序列中每個字母出現次數的平均，再與

f

的期望值相減不超過

δ

的機率趨近於 1 。為了讓原本

s_{n}

的機率連乘改成機率相加，在等式兩邊取對數即可，因此推導出 Shannon Entropy 的函數，即對於任意

n

都足夠小的

| B (n, ϵ) |

，完成錯誤機率在

ϵ

底下的訊息壓縮。因此 entropy 是我們可以達到的最好壓縮比，若 entropy 越大，則越難進行壓縮，也就是所需的資訊量越大，因此可應證「資訊與熵互補，資訊就是負熵」。

觀察 qtest 的 entropy

cmd> option entropy 1
cmd> ih RAND 10
l = [gzbrgpjhi(35.94%) psxzoa(29.69%) aqzce(26.56%) yyznkg(26.56%) imqkzw(29.69%) hvghnlr(29.69%) egoxpo(26.56%) ftxutyyh(29.69%) bgxpn(26.56%) xmbykcfz(35.94%)]

觀察每個字串的 entropy 可以發現影響字串的熵的因素是字串內出現過多少個字母，比如 ridykbl 和 uynbglfg 雖然長度不同，但都出現 7 個字母，因此其 entropy 是相同的。其計算方式是根據程式內的 shannon_entropy 進行計算。

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);
    }
}

實作新的命令切換不同的 PRNG

追蹤程式發現 ih RAND 10 會將 need_rand 設置為 true 並呼叫 fill_rand_string ，並且使用內建的 rand 和 randombytes 決定字串長度和填充不同字母。

while (len < MIN_RANDSTR_LEN)
    len = rand() % buf_size;
...
randombytes((uint8_t *) randstr_buf_64, len * sizeof(uint64_t));
for (size_t n = 0; n < len; n++)
    buf[n] = charset[randstr_buf_64[n] % (sizeof(charset) - 1)];

我在這邊做了一些小更動，改成用 if 來決定要用 Xorshift 還是用內建的亂數產生器來做隨機字串的產生，參考 Xorshift 發現 xorshift 是透過位移和 XOR 運算取得序列中的下一個數字，因此我另外開了一個 "xorshift.h" 和 "xorshift.c" ，在裡面實作使用時間作為種子並且套用 xorshift 的方法產生亂數序列。

static uint64_t xorshift64_state = 0;

void xorshift64_init(uint64_t seed) {
    if (seed == 0) seed = (uint64_t)time(NULL);;
    xorshift64_state = seed;
}

uint64_t xorshift64_rand(void) {
    xorshift64_state ^= xorshift64_state << 13;
    xorshift64_state ^= xorshift64_state >> 7;
    xorshift64_state ^= xorshift64_state << 17;
    return xorshift64_state;
}

並且改一下 Makefile 讓 "qtest.c" 和 "xorshift.c" 可以連結在一起，此外在 "console.c" 加入 option prng ，這個命令可以改變 change_prng 的值，因此可以用 change_prng 來區分現在用的是內建還是 Xorshift 的 PRNG。

內建 PRNG

cmd> option entropy 1
cmd> new
l = []
cmd> ih RAND 10
l = [yomqwi(29.69%) fhyxui(29.69%) etupzn(29.69%) kubgrpjum(35.94%) cyzedyt(29.69%) wrcvn(26.56%) tphts(21.88%) bfkfevea(29.69%) jeidxh(29.69%) tubvjx(29.69%)]

Xorshift PRNG

cmd> option prng 1
PRNG switched to Xorshift
cmd> new
l = []
cmd> ih RAND 10
l = [ufvldhtg(35.94%) jqrbqwse(32.81%) wwgwxgn(21.88%) pzwtxrgcq(37.50%) pbyuk(26.56%) bzcsxlyr(35.94%) uxghilvxv(32.81%) ombtojz(29.69%) gxjofkb(32.81%) qwwuanzg(32.81%)]

透過統計分析 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 來讓程式碼看起來更精簡。

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

    int len = q_size(head) - 1;
    struct list_head *tail = head->prev;
    for (int j = len; j > 0; j--) {
        int random = rand() % (j + 1);
        struct list_head *pos = NULL;
        for (pos = head; random >= 0; random--)
            pos = pos->next;
        if (pos == tail)
            continue;

        struct list_head *tmp = pos->prev;
        list_move(pos, tail);
        list_move(tail, tmp);
        tail = pos;
    }
}

在做完 q_shuffle 之後，要到 "qtest.c" 新增命令，讓使用者可以輸入 shuffle 以對佇列元素進行重新排列，並且透過 do_shuffle 呼叫 q_shuffle 實際進行洗牌，這樣使用者就可以將輸入的命令和洗牌的動作連結起來了。 do_shuffle 的實作方法參考 do_swap ，因為都只吃一個參數、禁止分配額外記憶體、並直接呼叫在 queue.c 裡面的相關函式。

+ ADD_COMMAND(shuffle, "Shuffle nodes in queue randomly", "");

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!current || !current->q) {
        report(3, "Warning: Calling shuffle on null queue");
        return false;
    }
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();

    set_noallocate_mode(false);

    q_show(3);
    return !error_check();
}

這樣就完成了在 qtest 新增 shuffle 命令，但由於不可更改 "queue.h" ，因此將 qtest 裡的相關變更註解掉，避免發生錯誤。

統計方法驗證 `shuffle`

使用 lab0(D) 的 Python 測試程式，並且將洗牌次數調整為 100000 ，觀察每種排列出現的次數，會得到以下結果：

Expectation:  4166
Observation:  {'1234': 4214, '1243': 4225, '1324': 4085, '1342': 4170, '1423': 4162, '1432': 4141, '2134': 4320, '2143': 4186, '2314': 4182, '2341': 4164, '2413': 4137, '2431': 4158, '3124': 4037, '3142': 4144, '3214': 4191, '3241': 4181, '3412': 4154, '3421': 4040, '4123': 4096, '4132': 4331, '4213': 4190, '4231': 4101, '4312': 4192, '4321': 4199}
chi square sum:  26.63706192990879

根據圖解，排列的出現次數呈現 uniform distribution。此外根據我們排列有 24 種，可得到自由度為 23，而我們的 chi-square sum (

χ^{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 測試他們是否為常數時間。

#define DUT_FUNC_IMPL(op) \
    bool is_##op##_const(void) { return test_const(#op, DUT(op)); }

而 test_const 最多會測試 TEST_TRIES 次，每次呼叫 doit 來測試是否為常數時間， doit 會呼叫 maesure 做執行時間的計算，並且再呼叫 update_statistics 來執行 t_push ，也就是做一次 t-test。

bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
ret &= report();

Student's t-distribution 通常用於樣本數小且母體標準差未知的情況下的一種連續機率分佈，用於 Student's t-test 進行顯著性測試的基礎，而在 Student's t-test 則有幾個應用，其中的雙樣本 t-test 則是我們會用來檢驗常數時間的檢定，其假說檢定如下，虛無假說為兩母體的變異數相等，當我們拒絕虛無假說時，可說明兩母體之間可能有顯著差異。

$H_{0}$ ：
$σ_{1}^{2} = σ_{2}^{2}$
$H_{0}$ ：
$σ_{1}^{2} \neq σ_{2}^{2}$

而 "ttest.c" 所實作的是 Welch's t-test，其放寬母體的條件為母體標準差不一定要相等，並將假說檢定更改如下，而這樣子的檢定更適合對程式執行時間進行統計分析，因為現實情況的執行時間往往受到軟硬體干擾，如論文所述。

$H_{0}$ ：
$μ_{1} = μ_{2}$
$H_{0}$ ：
$μ_{1} \neq μ_{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 函式計算該閾值樣本的位置。

1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)

最後回到 update_statistics ，只有在 difference 不超過閾值的樣本才會被加到 t-test 進行檢定。

// t-test on cropped execution times, for several cropping thresholds.
for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
    if (difference < ctx->percentiles[crop_index]) {
        t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
    }
}

幫 lab0-c 加上 Percentile 處理

根據 oreparaz/dutect ，我們在 "fixture.c" 加入新的函式為 percentile, prepare_percentile, cmp ，並且更新 update_statistics 和 doit ，加上檢查閾值。

doit

+ int64_t *percentile = calloc(N_MEASURES, sizeof(int64_t));
...
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
+ prepare_percentiles(exec_times, percentile);
update_statistics(exec_times, percentile, classes);
ret &= report();

update_statistics

- if (difference <= 0)
+ if (difference >= percentiles[i])
    continue;

完成更新並 push 之後就有看到星之卡比了。

Linux 核心的鏈結串列排序

參考 EricccTaiwan

研讀並引入 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 裡面的哪兩個串列。

for (bits = count; bits & 1; bits >>= 1)
    tail = &(*tail)->prev;
if (likely(bits)) {
    // ... do merge
}

在 list 的所有節點都被加到 pending 之後，會將所有節點合併起來，此時子串列才有可能出現長度不是 2 的冪，另外由於前面的 do-while 迴圈中都是以單向鏈結串列做合併的，因此在最後要將 pending 整個結構合併起來，並復原成雙向環狀鏈結串列。

/* 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);

效能分析

接下來我們將 list_sort.c 的程式碼也引入到 qtest.c ，新增函式為 q_list_sort，並且在 qtest 新增命令 listsort 來執行 Linux 核心的排序。由於在核心內有 comparator 作為 function pointer 傳入，我們也自行針對作業比較字串的規定寫了一個，並且使用 strcmp 的結果當作回傳值。

int compare(void *priv, struct list_head *q1, struct list_head *q2)
{
    if (q1 == q2)
        return 0;
    element_t *e1 = list_entry(q1, element_t, list);
    element_t *e2 = list_entry(q2, element_t, list);
    return strcmp(e1->value, e2->value);
}

在 Bottom-up Mergesort: A Detailed Analysis 有提到對於 Best-case, Worst-case, Average-case 的比較次數是根據單一次 merge 的劃分來做區隔的，論文隨後提供了一個公式說明比較次數

c_{n, m}

的上下界：

The cost measures
$C_{b, b u} (N)$ ,
$C_{w, b u} (N)$ , and
$C_{a, b u} (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)