# 2025q1 Homework1 (lab0)
contributed by < `davidshiao55` >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ 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):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             10
    CPU(s) scaling MHz:   19%
    CPU max MHz:          4500.0000
    CPU min MHz:          800.0000
    BogoMIPS:             5199.98
    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 pni pclmulqdq dtes64 monitor 
                          ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid 
                          sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer a
                          es xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpu
                          id_fault epb pti ssbd ibrs ibpb stibp tpr_shadow flexp
                          riority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 
                          smep bmi2 erms invpcid mpx rdseed adx smap clflushopt 
                          intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida ara
                          t pln pts hwp hwp_notify hwp_act_window hwp_epp vnmi m
                          d_clear flush_l1d arch_capabilities
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    192 KiB (6 instances)
  L1i:                    192 KiB (6 instances)
  L2:                     1.5 MiB (6 instances)
  L3:                     12 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-11
Vulnerabilities:          
  Gather data sampling:   Mitigation; Microcode
  Itlb multihit:          KVM: Mitigation: VMX disabled
  L1tf:                   Mitigation; PTE Inversion; VMX conditional cache flush
                          es, SMT vulnerable
  Mds:                    Mitigation; Clear CPU buffers; SMT vulnerable
  Meltdown:               Mitigation; PTI
  Mmio stale data:        Mitigation; Clear CPU buffers; SMT vulnerable
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; IBRS
  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; IBRS; IBPB conditional; STIBP conditional;
                           RSB filling; PBRSB-eIBRS Not affected; BHI Not affect
                          ed
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Not affected

## 針對佇列操作的程式碼實作

### q_free
> commit: [81544d6](https://github.com/davidshiao55/lab0-c/commit/81544d6cf0fa1d182fccfd1783106f37ae6960bd)

實作 `q_free` 函式，以正確地釋放佇列所佔用的所有記憶體資源。透過使用 `list_for_each_entry_safe` 巨集，我們可以安全地遍歷鏈結串列，並在迴圈中呼叫 `q_release_element` 來釋放每個元素的記憶體。迴圈結束後，使用 `free` 函式釋放 `list_head` 結構體本身，確保沒有記憶體洩漏。

> commit: [f25c599](https://github.com/davidshiao55/lab0-c/commit/f25c59959cc4576d8205ed0100a27415bcf37c87)

void q_free(struct list_head *head)
 {
+    if (!head)
+        return;
+
     element_t *entry = NULL, *safe = NULL

為 `q_free` 函式新增了對空指標的檢查，以避免對空指標執行 `free` 操作。具體修改如下：

### q_insert_head
> commit: [54f1e93](https://github.com/sysprog21/lab0-c/commit/54f1e930fbb01b42e1eb062e5dec89e1cc5ef144)

首先，對 `head` 進行空指標檢查，以確保傳入的佇列有效。接著，分配記憶體空間給新的 `element`，若記憶體分配失敗則直接回傳 `false`。隨後，使用 `test_strdup` 分配記憶體並複製 `s` 到 `element` 結構體中的字串，確保新節點的內容正確。最後，使用 `list_add` 將新節點加入佇列的開頭，並回傳 `true`，表示插入成功。

> commit: [aec8cf5](https://github.com/davidshiao55/lab0-c/commit/aec8cf5188fd5cd1bb9eb8fa9c1a646f55f3149c)

 void q_free(struct list_head *head)
 /* Insert an element at head of queue */
 bool q_insert_head(struct list_head *head, char *s)
 {
-    if (!head)
+    if (!head || !s)
         return false;
 
     element_t *e = malloc(sizeof(element_t));
     if (!e)
         return false;
 
-    e->value = test_strdup(s);
+    size_t len = strlen(s) + 1;
+    e->value = malloc(len);
+    if (!e->value) {
+        free(e);
+        return false;
+    }
+    strlcpy(e->value, s, len);
     list_add(&e->list, head);
 
     return true;

對 `q_insert_head` 函式進行了以下改進：

1. 加入對 `s` 的空指標檢查：在插入新元素時，首先檢查字串指標 `s` 是否為空，以避免對空指標進行操作，確保程式的穩定性。
2. 改用 `strlcpy` 取代 `test_strdup`：在 `harness.c` 中發現註解標註該檔案屬於測試支援程式碼（test support code）。在閱讀 CERN 相關文獻後，決定改用 `strlcpy` 來實作字串複製，以提高記憶體管理的安全性。
3. 避免記憶體洩漏：在檢測到 `e->value` 的記憶體分配失敗時，新增對 `e` 的記憶體釋放操作，以避免記憶體洩漏問題的發生。

### q_insert_tail
> commit: [7629631](https://github.com/davidshiao55/lab0-c/commit/7629631497c36190a4b3bd5bc41b3eb5970eb376)
> commit: [aec8cf5](https://github.com/davidshiao55/lab0-c/commit/aec8cf5188fd5cd1bb9eb8fa9c1a646f55f3149c)

同 `q_insert_head` 的實作，但將 `list_add` 換成 `list_add_tail`。

### q_remove_head
> commit: [d2f60aa](https://github.com/davidshiao55/lab0-c/commit/d2f60aabc7811c9c8318df3c9d8ee5a8ebc32ec2)

首先，檢查 `head` 是否為空指標，或佇列是否為空，若是則直接回傳 `NULL`。接著，使用 `list_first_entry` 取得佇列的第一個元素 `e`，若提供了字串指標 `sp`，則使用 `strlcpy` 將元素的值複製到 `sp`，確保不超過 `bufsize`。然後，使用 `list_del` 將元素從佇列中移除，最後回傳指向已移除元素的指標 `e`。

### q_remove_tail
>commit: [7629631](https://github.com/davidshiao55/lab0-c/commit/7629631497c36190a4b3bd5bc41b3eb5970eb376)

同 `q_remove_head` 的實作，但將 `list_first_entry` 換成 `list_last_entry` 。

### q_size
> commit: [7bad176](https://github.com/davidshiao55/lab0-c/commit/7bad1769d72b135d9c869e88d599a3e0d1b2ada5)

首先，檢查 `head` 是否為空指標或佇列是否為空，若是則回傳 0。接著，使用 `list_for_each` 巨集遍歷佇列，計算元素數量並回傳。

### q_delete_mid
>commit: [30c06e1](https://github.com/davidshiao55/lab0-c/commit/30c06e179006558c68cb31c484226cc4e709c2b5)

在閱讀完[分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT)後，使用快慢指標的方式實作，以更有效地利用時間局部性。首先，對 `head` 做空指標及空佇列檢查，若為空則回傳 `false`。接著，利用快慢指標法遍歷佇列，直到快指標到達佇列末尾，慢指標即指向中間節點。最後，使用 `list_del` 刪除該中間節點並釋放記憶體。

### q_delete_dup
>commit: [db08bab](https://github.com/davidshiao55/lab0-c/commit/db08bab12a38c0d022ecdb8b262503450841b336)

此題跟 leetcode 最大的差異是鏈結串列並非排序好的，在理解題目後考慮了兩種實作方法：
1. 使用雜湊表實作，時間複雜度：$O(n)$，空間複雜度：$O(n)$
2. 使用巢狀迴圈實作，時間複雜度：$O(n^2)$，空間複雜度：$O(1)$

考慮到 C 語言沒有原生雜湊表實作，選擇使用巢狀迴圈。考慮到刪除重複節點可能會刪除到下一個節點不適合使用 `list_for_each_safe` 巨集，改使用 `list_for_each` 巨集，並在內層迴圈中使用一個 `runner` 指標去刪除重複節點並檢測當前節點是否重複，若當前節點是重複節點則在外層迴圈再刪除此節點。

> commit: [bec3e6a](https://github.com/davidshiao55/lab0-c/commit/bec3e6aa775bb15262d190a338609a5acc044bc3)

$./qtest 
cmd> new
l = []
cmd> it a
l = [a]
cmd> it b
l = [a b]
cmd> it c
l = [a b c]
cmd> it a
l = [a b c a]
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = [b c]
cmd> size
ERROR: Computed queue size as 2, but correct value is 4
l = [b c]

在發現以上測資會出錯後，閱讀 `qtest.c` 中 `do_dedup` 的實作，發現我錯誤理解題意，此題只需移除相鄰重複節點。時間複雜度：$O(n)$ ，空間複雜度 $O(1)$

bool q_delete_dup(struct list_head *head)
     if (!head || list_empty(head))
         return false;
 
-    struct list_head *node = head->next;
-
-    while (node != head) {
+    struct list_head *node;
+    list_for_each (node, head) {
         element_t *e = list_entry(node, element_t, list);
         bool dup = false;
 
-        struct list_head *safe = node->next;
-        // safe find the first non-duplicated value
-        while (safe != head) {
-            struct list_head *next = safe->next;
-            element_t *s = list_entry(safe, element_t, list);
-            if (!strcmp(s->value, e->value)) {
+        struct list_head *runner = node->next;
+        while (runner != head) {
+            struct list_head *next = runner->next;
+
+            element_t *r = list_entry(runner, element_t, list);
+            if (!strcmp(e->value, r->value)) {
                 dup = true;
-                list_del(&s->list);
-                q_release_element(s);
-            } else {
-                break;
+                list_del(&r->list);
+                q_release_element(r);
             }
-            safe = next;
+            runner = next;
         }
         if (dup) {
+            struct list_head *next = node->next;
             list_del(&e->list);
             q_release_element(e);
+            node = next;
         }
-        node = safe;
     }
     return true;
 }

新的實作使用一個 `safe` 指標指向第一個與此節點結構體中字串相異的節點，若有找到相同節點則刪除相同節點和此節點。

### q_reverse
>commit: [9bbf5f2](https://github.com/davidshiao55/lab0-c/commit/9bbf5f29a8a6fdb7c768c82e9b1fb9d0134789a0)

首先，檢查 `head` 是否為空指標，或佇列是否為空，接著從 `head` 遍歷各節點，將個解點中 `next` 和 `prev` 指向的節點交換。

### q_reverseK
>commit: [c84a603](https://github.com/davidshiao55/lab0-c/commit/c84a6039fd0b4daa878b33cd078e595a98de661e)

首先，檢查 `head` 是否為空指標，佇列是否為空或佇列是否只有一個元素，若是則直接返回。然後，遍歷佇列，對每組 k 個節點進行反轉操作。對於每組節點，首先找到第 k 個節點，若不足 k 個則不進行反轉。接著，反轉這 k 個節點的指標方向。最後，調整前一組的最後一個節點與當前組的第一個和第 k 個節點，以及下一組的第一個節點之間的指標關係，以維持雙向鏈結串列的結構。

### q_sort
>commit: [0e31de7](https://github.com/davidshiao55/lab0-c/commit/0e31de76a317759e3d5b99494193596e588a76f3)

首先，將環狀鏈結串列轉換為非環狀的雙向鏈結串列。接著，使用快慢指標將串列分割為兩部分，並遞迴地對每部分進行合併排序。最後，將排序後的串列重新連接到頭節點。此實作中包含兩個輔助函式：`merge_sort_dlist` 使用快慢指標將串列分割為兩部分；`merge_two_sorted` 則為遞迴函式，用於合併兩個已排序的雙向鏈結串列。

`merge_sort_dlist` 中快慢指標偏移 `fast` 指標使得在偶數節點數的時候會選擇第一個中間節點，使得在節點數為二的時候叫容易處理分割。

static struct list_head *merge_sort_dlist(struct list_head *head, bool descend)
{
    ...
    struct list_head *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    ...
}

> commit : [309a9ba](https://github.com/davidshiao55/lab0-c/commit/309a9badee706b945ec3ad32414a094cc60b3399)

參照[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)將 `merge_two_sorted` 函式從遞迴實作改為使用 indirect pointer ，類似於合併單向鏈結串列的方法，並添加額外的指標以維持雙向鏈結串列的結構。此更改有助於提高函式的效率，避免遞迴帶來的額外開銷。

/*  merges two sorted (non-circular) doubly linked lists */
static struct list_head *merge_two_sorted(struct list_head *left,
                                          struct list_head *right,
                                          bool descend)
{
    struct list_head *head = NULL, **ptr = &head, **node, *prev = NULL;

    for (node = NULL; left && right; *node = (*node)->next) {
        const element_t *l = list_entry(left, element_t, list);
        const element_t *r = list_entry(right, element_t, list);
        bool cmp = (descend) ? (strcmp(l->value, r->value) >= 0)
                             : (strcmp(l->value, r->value) <= 0);
        node = (cmp) ? &left : &right;
        *ptr = *node;
        (*node)->prev = prev;
        prev = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);
    (*ptr)->prev = prev;
    return head;
}

>commit: [4dde27f](https://github.com/davidshiao55/lab0-c/commit/4dde27f8441870c1ec58689f4938a72f5a71caa3)

在實作 `q_merge` 後新增了兩個輔助函式，因此更精簡化了程式碼。

void q_sort(struct list_head *head, bool descend)
         return;
 
     // Break the the list into normal doubly-linked list
-    struct list_head *first = head->next;
-    struct list_head *last = head->prev;
-    first->prev = NULL;
-    last->next = NULL;
+    struct list_head *first = break_ring(head);
 
     struct list_head *sorted = merge_sort_dlist(first, descend);
-    struct list_head *tail = sorted;
-    while (tail->next)
-        tail = tail->next;
-
-    // Link the head back
-    head->next = sorted;
-    head->prev = tail;
-    sorted->prev = head;
-    tail->next = head;
+    recirc(head, sorted);
 }

### q_ascend
>commit: [8d19670](https://github.com/davidshiao55/lab0-c/commit/8d1967051fb1683634172f21879b0f45d77e0616)

首先，檢查 `head` 是否為空指標、佇列是否為空或僅有一個元素，若是則回傳佇列大小。接著，從佇列尾部開始向前遍歷，追蹤目前的最小值，移除所有大於該最小值的節點，並在找到新的最小值時更新。此方法確保了剩餘的節點按遞增順序排列。

### q_descend
>commit: [83f6e33](https://github.com/davidshiao55/lab0-c/commit/83f6e334bce418afb9d26c3cf528f122ef69aab6)

同 `q_ascend` ，但將最小值換成最大值。

### q_merge
>commit: [526c2da](https://github.com/davidshiao55/lab0-c/commit/526c2dade43a633ce49638e768dbf95c505a3653)

包含三個輔助函式：
1. `break_ring`：將具有哨兵頭節點的環狀鏈結串列轉換為標準的雙向鏈結串列。
2. `recirc`：將標準的雙向鏈結串列重新構造成環狀鏈結串列，並加入 `head` 節點。
4. `merge_two_sorted`：從 `q_sort` 中提取出來的函式，用於合併兩個已排序的雙向鏈結串列。

在 `q_merge` 函式中遍歷節點，首先使用 `break_ring` 轉換環狀鏈結串列，接著透過 `merge_two_sorted` 合併該個和第一個已排序的佇列，最後使用 `recirc` 重新構造環狀鏈結串列。

## 研讀 Linux 核心原始程式碼的 lib/list_sort.c
`list_sort.c` 有別於傳統 top-down 的 merge sort，採取了 bottom-up 的策略，更有效率的利用快取。

### 將 list_sort.c 引入 lab0
> commit: [824efeb](https://github.com/davidshiao55/lab0-c/commit/824efeb2641fa1aacee5298dbb8ee31eb93e97ff)

直接將 `list_sort.c` 引入 `queue.c` 中，再多加入 `cmp_func` 和 `sort_arg`，尚未比較效能。

+#define likely(x) __builtin_expect(!!(x), 1)
+#define unlikely(x) __builtin_expect(!!(x), 0)
+
+struct sort_arg {
+    bool descend;
+};
+
+static int cmp_func(void *priv,
+                    const struct list_head *a,
+                    const struct list_head *b)
+{
+    const struct sort_arg *arg = priv;
+    const element_t *ea = list_entry(a, element_t, list);
+    const element_t *eb = list_entry(b, element_t, list);
+
+    int cmp = strcmp(ea->value, eb->value);
+    if (!arg->descend) {
+        return cmp;  // normal ascending
+    } else {
+        // just flip the sign
+        return -cmp;
+    }
+}
+
+typedef int (*list_cmp_func_t)(void *,
+                               const struct list_head *,
+                               const struct list_head *);
@@ -333,11 +591,16 @@  void q_sort(struct list_head *head, bool descend)
     if (!head || list_empty(head) || list_is_singular(head))
         return;
 
-    // Break the the list into normal doubly-linked list
-    struct list_head *first = break_ring(head);
+    // Build an 'arg' struct with the chosen ordering
+    struct sort_arg arg = {
+        .descend = descend,
+    };
 
-    struct list_head *sorted = merge_sort_dlist(first, descend);
-    recirc(head, sorted);
+    // Then just call list_sort. It will:
+    // 1) break the ring,
+    // 2) do a mergesort in place,
+    // 3) re-circularize the list.
+    list_sort(&arg, head, cmp_func);
 }

## 實作q_shuffle
實驗1,000,000次 shuffle 實驗結果如下：

$python3 scripts/shuffle.py 
Expectation:  41666
Observation:  {'1234': 41450, '1243': 41577, '1324': 41709, '1342': 41571, '1423': 41283, '1432': 41835, '2134': 41623, '2143': 41725, '2314': 41279, '2341': 41439, '2413': 41830, '2431': 41689, '3124': 41762, '3142': 41821, '3214': 41754, '3241': 41692, '3412': 41610, '3421': 41708, '4123': 41979, '4132': 41775, '4213': 41825, '4231': 41522, '4312': 41699, '4321': 41843}
chi square sum:  17.030672490759855

自由度為 4! - 1 = 23，P value = 0.7951，P value > apla (0.05)，統計檢定的結果不拒絕虛無解說，不拒絕 shuffle 的結果遵循 Uniform distribution。

## dudect 論文
這篇論文主要描述透過 fix-vs-random leakage detection 的方式不用透過硬體，依靠執行時間的統計分析判斷程式是否是常數執行時間。

[wurrrrrrrrrr的開發紀錄](https://hackmd.io/@Guanchun0803/linux2025-homework1#研讀論文%E3%80%88Dude-is-my-code-constant-time〉)提到他對在 `constant.c` 中對 fix class 的 constant 做變動得到的不同結果，在我自己實驗後也復現了同樣結果，在 constant 為 0 時會過不了 trace-17 但在 0xAA, 0xCC, 0xFF 都過得了。
我對這個實驗結果的解釋是當我們把 fix class 固定填入 0 時，`strlen` 這類遇到第一個 `\0` 就會停止的函式的的執行時間就會非常短，造成 False positive 的非常數執行時間，是 fix input 單方面造成的並沒有任何 secret-dependency，巫同學的實驗結果也看出這個現象。

         if (classes[i] == 0)
-            memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);
+            memset(input_data + (size_t) i * CHUNK_SIZE, 0xff, CHUNK_SIZE);