# 2025q1 Homework1 (lab0) contributed by <`Zhen-89`> {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 開發環境 ``` $ uname -a Linux ncuesa-GPU 6.8.0-52-generic #53-Ubuntu SMP PREEMPT_DYNAMIC Sat Jan 11 00:06:25 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux $ 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): 16 On-line CPU(s) list: 0-15 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i9-14900K CPU family: 6 Model: 183 Thread(s) per core: 2 Core(s) per socket: 8 Socket(s): 1 Stepping: 1 BogoMIPS: 6374.39 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clfl ush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc rep_go od nopl xtopology tsc_reliable nonstop_tsc cpuid aperfmperf pni pclmulqdq ss se3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes x save avx f16c rdrand hypervisor lahf_lm abm 3dnowprefetch ssbd ibrs ibpb sti bp ibrs_enhanced fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb sha_ni xsaveopt xsavec xgetbv1 xsaves user_shstk a vx_vnni umip waitpkg gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_cl ear serialize ibt flush_l1d arch_capabilities Virtualization features: Hypervisor vendor: Microsoft Virtualization type: full Caches (sum of all): L1d: 384 KiB (8 instances) L1i: 256 KiB (8 instances) L2: 16 MiB (8 instances) L3: 36 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: Unknown: No mitigations Reg file data sampling: Mitigation; Clear Register File Retbleed: Mitigation; Enhanced IBRS Spec rstack overflow: Not affected Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization Spectre v2: Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB- eIBRS SW sequence; BHI BHI_DIS_S Srbds: Not affected Tsx async abort: Not affected ``` ## 文件紀錄 - [ ] [lab0(A) 說明文件](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a) - [ ] [lab0(B) - 以 Valgrind 分析記憶體問題](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-b) - [x] [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) - [x] [2023 年 Linux 核心設計/實作課程第一次作業檢討](https://hackmd.io/@sysprog/linux2023-lab0-review) - [x] [2025 年 Linux 核心設計/實作課程第一次作業檢討](https://hackmd.io/@sysprog/linux2025-homework1) - [ ] [運用 Perf 分析程式效能並改善](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Flinux-perf) - [ ] [詳閱改進 lib/list_sort.c含解說錄影](https://hackmd.io/@sysprog/Hy5hmaKBh) ## 開發流程 ## 實作 queue.[ch] ### `q_new` 觀察 `list.h` 裡面提供 `INIT_LIST_HEAD` 可以用來初始化 `list_head` ，而不用手動分配 `list_head` 中的 `*prev` `*next` 。另外，當 `malloc` 配置記憶體失敗時，有可能返回 `NULL` ，所以另外設置一判斷式，當配置成功時做 `INIT_LIST_HEAD` 初始化，當配置失敗時返回 `NULL` 。 ```cpp struct list_head *q_new() { struct list_head *new = malloc(sizeof(struct list_head)); if(!new) return NULL; INIT_LIST_HEAD(new); return new ; }; ``` ### `q_free` 首先觀察 `list.h` ，裡面實作 `list_for_each` 等四個巨集並檢查裡面的註解 ，`list_for_each_entry_safe` 這個巨集提供 : > `@entry` : Pointer to the structure type, used as the loop iterator. > `@safe` : Pointer to the structure type, storing the next entry for safe > `@head` : Pointer to the list_head structure representing the list head. > `@member` : Name of the list_head member within the structure type of `@entry` . 其中 `safe` 該處另外說明 `*safe removal of the current node (@entry) during iteration by pre-fetching` ，可以暫存下一個 `entry` 而不影響迴圈的執行 ```cpp void q_free(struct list_head *node) { if(!node) return ; element_t *entry, *safe; list_for_each_entry_safe(entry, safe, l, list) q_release_element(entry); free(l) } ``` ### `q_insert_head` \ `q_insert_tail` 此處完成 `q_insert_head` 實作，流程為 : 1. 配置一塊 `element_t` 大小記憶體。 1. 將字串放入該結構體中，不過如果單使用 `node->value = s;` ，僅將指標指向來源字串，如果來源字串被改動，會導致結構體中的字串也被更改，所以使用 `strup(s)` 複製字串並進行空間的分配。 1. 分配前一塊及後一塊結構體的指標，並使用巨集 `list_add` 協助分配指標。 ```cpp bool q_insert_head(struct list_head *head, char *s) { if(!head) return false; element_t *node = malloc(sizeof(element_t)); if(!node) return false; node->value = strdup(s); list_add(&node->list, head); return true; } ``` 由於 `q_insert_head` \ `q_insert_tail` 兩段程式碼結構跟流程近似，嘗試在 `q_insert_tail` 重用 `q_insert_head`，其中本作業的鏈結是雙向的環狀迴圈，所以 `list_head` 的 `perv` 紀錄鏈結的最後一個節點。 ```cpp bool q_insert_tail(struct list_head *head, char *s) { return q_insert_head(head->prev, s); } ``` ### `q_remove_head` \ `q_remove_tail` `strdup` vs `strcpy` vs `strncpy` vs `memcpy` 1. `strdup` * 在堆區用 malloc 配置一塊新記憶體，足夠放下整個字串（含 NUL 結尾 '\0'）。 * 把參數字串的所有字元（含終止符）複製進新配好的區塊，回傳新指標。 2. `strcpy` * 把「來源 C 字串」完整複製到「目標緩衝區」，從首字元到終止符 '\0'，一個都不漏地複製進去。 * buffer 的大小是有限制的。C 標準函式庫提供的 strcpy 無法滿足此需求 3. `strncpy` * 從來源字串複製最多 n 個字元到目標緩衝區，但不保證結果一定以 '\0' 結尾 4. `memcpy` * 按「位元組數」直接從某個記憶體地址拷貝 n 個位元組到另一個地址，不做任何結尾或字串終止檢查。 > list_first_entry(head, type, member) - Get first entry of the list > @head: 指向鏈表「頭節點」的指標 > @type: 包含 list_head 欄位的結構體名稱 > @member: 在上述結構體裡，代表鏈表節點的那個 list_head 欄位名稱 > Return: @type pointer of first entry in list > list_del(node) - Remove a node from a circular doubly-linked list > ```cpp element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if(!head) return NULL; element_t *ret = list_first_entry(head, element_t, list); list_del(&ret->list); // 只做節點移除，但不釋放記憶體 if(sp){ memcpy(sp, ret->value, bufsize); sp[bufsize-1] = '\0'; } return ret; } ``` 另外，注意到 `list_first_entry` 以下方這種方式實作 ```cpp #define list_first_entry(head, type, member) \ list_entry((head)->next, type, member) ``` 所以 `q_remove_head` 需要帶入鏈結的前前一個指標 ```cpp element_t q_remove_tail(struct list_head *head, char *s, size_t bufsize) { return q_remove_head(head->prev->prev, s, bufsize); } ``` ### ### `q_size` 使用巨集 `list_for_each(node, head)` 走訪各節點，並統計節點數量。 ```cpp list_for_each(node, head) size++; ``` ### `q_delete_mid` 在 [leetcode 2095](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/) 當中，中間節點是指對於長度為 n 的鏈結，從起點節點算起(使用 0 為起點索引)的第 $⌊n / 2⌋$ 個節點。 另外考慮到 leetcode 的題目為單向無迴圈，跟本題(雙向迴圈)不同，所以不採用 Floyd Cycle Detection Algorithm ，而使用兩指標分別走訪前後，當兩指標會合時就代表到達中間節點。 ```cpp /* Delete the middle node in queue */ bool q_delete_mid(struct list_head *head) { struct list_head *fnt = head->next, *end = head->prev; if (!head) return false; for(;fnt != end && fnt != end->prev; fnt = fnt->next, end = end->prev); element_t *mid = list_entry(end, element_t, list); list_del(&mid->list); q_release_element(mid); return true; } ``` ### `q_delete_dup` [leetcode 82](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/) 說明給定一個已排序鏈結的起始節點，刪除所有重複出現的節點，只保留原佇列中唯一出現的數字。並返回排序後的佇列。 ```cpp bool q_delete_dup(struct list_head *head) { if(!head) return false; element_t *dup; list_del(); q_release_element(dup); // return true; } ``` ### TODO : `q_swap` 參考 [leetcode 24](https://leetcode.com/problems/swap-nodes-in-pairs/) 普遍解法直接交換節點內部數值，雖然解法直觀、容易實作，但不符合 Linux 鏈結串列設計理念，盡量以指標完成節點間的操作，故使用 `list_move` 交換節點間的順序 ```cpp void q_swap(struct list_head *head) { if(!head || !head->next) return; struct list_head *cur = head->next; // 走訪鏈結串列，兩兩交換相鄰的節點順序。 while(cur != head || cur->next != head) { struct tmp = cur; list_move(cur, tmp->next); cur = cur->next; } } ``` ### `q_reverse` 使用 `list_for_each_safe` 走訪各個節點，將走訪過的節點移到開頭的位置。 ```cpp void q_reverse(struct list_head *head) { if(!head) return; struct list_head *cur, *nxt; list_for_each_safe(cur, nxt, head) list_move(cur, head); } ``` ### `q_reverseK` 同 [leetcode 25](https://leetcode.com/problems/reverse-nodes-in-k-group/) ，以 K 個 node 為一組，做翻轉 ```cpp void q_reverse(struct list_head *head, int k) { if(!head) return; struct list_head *cur, *nxt; list_for_each_safe(cur, nxt, head) list_move(cur, head); } ``` ### TODO : `q_sort` ```cpp ``` ### TODO : `q_ascend` & `q_descend` ```cpp ``` ### `q_mergeTwoList` 同 [leetcode 21](https://leetcode.com/problems/merge-two-sorted-lists/) ， `q_mergeTwoList` 的工作目標是把兩條已經排好序的雙向鏈表「就地」合併成一條，同時計算合併後的節點數。 程式首先檢查傳進來的兩個串列指標是否為空，若有任何一條為空就直接回傳 0。接著它在本地定義了一個臨時頭節點 `ptr`，把這個空串列當作合併結果的暫存容器。 當兩條串列都尚有節點時，程式用 `strcmp` 比較它們目前頭部節點的字串值，然後根據傳入的 `descend` 參數決定是要升序還是降序——選出「較小」或「較大」的節點、從其原本的串列中拔下，接到 `ptr` 的尾端，並把計數器加一。 等其中一條串列先跑完，程式就把另一條還沒合併完的整條剩餘串列，一口氣接到 `ptr` 上。 最後，利用 `list_splice` 把 `ptr` 暫存的所有節點一次性插回到 `list1` 原位，完成「就地」合併，並回傳最終的節點總數。 ```cpp int q_mergeTwoList(struct list_head *list1, struct list_head *list2, int descend) { if(!list1 || !list2) return 0; struct list_head ptr; INIT_LIST_HEAD(&ptr); int size = 0; while(!list_empty(list1) && !list_empty(list2)){ element_t *ele1 = list_first_entry(list1, element_t, list); element_t *ele2 = list_first_entry(list2, element_t, list); int cmp = strcmp(ele1->value, ele2->value); element_t *next = descend ? (cmp > 0 ? ele1 : ele2) : (cmp > 0 ? ele2 : ele1); list_move_tail(&next->list, &ptr); } size += q_size(list1); list_splice_tail_init(list1, &ptr); size += q_size(list2); list_splice_tail_init(list2, &ptr); list_splice(&ptr, list1); return size; } ``` ### `q_merge` `q_merge` 和 [leetcode 23](https://leetcode.com/problems/merge-k-sorted-lists/) 一樣比較多個串列，不過相異的地方是 leetcode 23 使用 stack 紀錄多個佇列，而 `q_merge` 使用 `queue_contex_t` 儲存多個鏈結，要注意操作方式的不同。 以下是 `queue_contex_t` 結構體 ``` queue_contex_t - The context managing a chain of queues * @q: pointer to the head of the queue * @chain: used by chaining the heads of queues * @size: the length of this queue * @id: the unique identification number ``` 由上 `q_merge`，要處理的對象已經不只兩條串列，而是一個串列 head 裡面，每個節點都是一個「隊列上下文」（queue_contex_t），其中封裝了一條子鏈表 q。最終目的是把 head 裡所有這些子鏈表，依序合併到第一個上下文的那條鏈表中。 程式先檢查：如果 head 本身為空，或只含一個上下文，那就不用合併，直接回傳子鏈表的大小；否則先取出第一和第二個上下文。只要第二個上下文的 q 還不是空，程式就呼叫前一段的 q_mergeTwoList，把第二個上下文的那條 q 串列和第一個上下文的 q 串列合併，並把合併後的節點數存到 queue_size。 接著把第二個上下文的 q 指回 NULL（表示它的節點已經移走），再把整個第二個上下文節點本身，用 list_move_tail 挪到 head 這個上下文串列的尾端。此時，原本第三個上下文就成了新的第二個，程式再繼續合併，直到所有子鏈表都被歸併到第一個上下文為止，最後把最後一次合併得到的節點數 queue_size 回傳。 整個流程就是用「兩兩合併並將空的上下文節點移尾」的方式，逐步把多條隊列合成一條。 ```cpp int q_merge(struct list_head *head, bool descend) { if(!head || list_empty(head)) return 0; if(list_is_singular(head)) return q_size(list_first_entry(head, queue_contex_t, chain)->q); int queue_size = 0; queue_contex_t *first, *second; first = list_first_entry(head, queue_contex_t, chain); second = list_entry(first->chain.next, queue_contex_t, chain); while(second->q){ queue_size = q_mergeTwoList(first->q, second->q, descend); second->q = NULL; list_move_tail(&second->chain, head); second = list_entry(first->chain.next, queue_contex_t, chain); } return queue_size; } ``` ## TODO : 以 Valgrind 分析記憶體問題 參考 : [以 Valgrind 分析記憶體問題](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-b) ## 研讀 lib/list_sort.c 參考 : [Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh) Linux Kernel 內的 lib/list_sort.c 以 mergesort 實作，透過研究 timsort 改善排序效能 ### What is timsort > 開發者 Tim Peters 認為在現實世界中的序列大多都是已經部分排序的(partial sorted) 所以，第一步是從序列的左到右開始檢查該序列是否是遞增或是遞減，甚至是嚴格遞增、減 Timsort 的名詞定義 * Runs : 已排序好的子序列 * Natural Run : 未排序序列中的，已排序的子序列 假設有這樣一序列 $$ \{ 3, 5, 9, 11, 7, 3, 4, 6, 8, 9, 20 \} $$ 觀察上面那個序列 $\{ 3, 5, 9, 11\}$ $\{ 3, 4, 6, 8\}$ 都是 Natural Run ，原本便排序好的序列。 而 Run 則表示，透過 Mergesort & Timsort 所排序好的子序列 $\{3, 5, 9, 11 \} \{3, 7 \} \{4, 6, 8, 9, 20 \}$ 不過為了避免合併的效率太差，所以必須設計一個 minrun，減少合併時的步驟，所以實際序列可能拆成這樣，以 minrun = 3 來說 $$ \{3, 5, 9, 11 \} \{7, 3, 4 \} \{6, 8, 9, 20 \} $$ ### 合併的技巧 假設有任意三個相鄰的 run，分別為 $A$, $B$, $C$，只要下面任一個條件不滿足，就將 $B$, $C$ 合併 $$ A >B+C $$ $$ B >C $$ mergesort vs timsort bfs -> deep first search 降低 cache miss ### TODO : mergesort & timsort 在數學上的差異 透過 ANOVA(Analysis of Variance) 分析以下之 $MSTr$ 和 $MSE$ * Execution Time * The number of comparisons * Cache miss ratio > 補充 : > Mean Square Treatment (MSTr)是指「處理組間（treatment/groups 之間）變異的平均平方」，用以衡量不同處理（例如不同排序演算法或不同輸入類型）之間平均效能差異的大小。 > > Mean Square Error (MSE)也稱組內誤差均方（Residual Mean Square），衡量同一組內樣本之間的變異，也即試驗重複測量的隨機波動。 F-value $$ f = \frac{mstr}{mse} $$ ## 閱讀 Dude, is my code constant time 關鍵字 : timing attack, side channel attack, dpa attack ### Introduction Timing attack 是一種被廣泛應用 Side channel attack。意指攻擊者可以不用直接暴力破解金鑰，攻擊者可以透過統計程式執行時間，匯集程式在比對密碼的執行時間、猜測金鑰實際長度，加快密碼破解，參考以下程式碼 : ```python def is_key_correct(inp): if len(inp) != len(SECRET): return False for c1, c2 in zip(inp, SECRET): if c1 != c2: return False return True print(is_key_correct(input())) ``` 儘管程式乍看之下沒有邏輯漏洞，但程式在輸入不同密碼下有不同執行時間，攻擊者可藉機利用程式設計缺陷，並非攻擊密碼解密演算法而造成危害。 因此本文提出方法及提供程式碼 [dudect](https://github.com/oreparaz/dudect)，檢查程式執行時間，測量程式執行時間是否為 $O(1)$，並從中推斷程式在加解密過程中是否會因破解，在透露出破綻之前，以該方法提前發現並避免。 ### Methodology - TOC 以本論文所提供的方法論可拆分為三步，1.測量執行時間 2.對測量時間做資料清洗 3.統計結果，如下 : 1. Measure execution time a. class definition b. cycle counters c. environmental conditions 2. Apply post-processing a. cropping : 去掉某些極端值 b. higher-order preprocessing 3. Apply statistical test a. t-test b. Non-parametric tests ### Measure time - Class definition 分別用兩類(class) input data ，論文中提到的是 fix-vs-random ， fixed class 是為了 corner-case ### Post-Processing - Welch’s t-test ### Discusion ## 亂數研究和 Shuffle 實作 參考 : [在 qtest 提供新的命令 shuffle](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d)