2025q1 Homework1 (lab0)

# 2025q1 Homework1 (lab0) contributed by <`alanhc`> {%hackmd NrmQUGbRQWemgwPfhzXj6g %} {%hackmd TDGjUnHqRlSwffjXulBnrw %} ## Goal ### C 語言進階議題與實作能力 - 掌握 C 語言深層機制：像是 setjmp/longjmp、signal 處理、記憶體管理（malloc/free 等），都是系統級程式設計不可或缺的能力。 - 理解變數參數處理（如 va_list 等）：讓你能撰寫更通用的 API。 - Linux 核心資料結構實作：例如雙向鏈結串列 (list_head) 與 queue.c 的高效操作，並強調 O(1) 的時間複雜度需求。 ### 系統設計與除錯觀念 - 記憶體錯誤偵測工具：如 Valgrind、ASan（Address Sanitizer）不只幫助除錯，也是訓練你養成可靠程式開發的工具。 - Cppcheck & 靜態分析訓練：培養你「在編譯前就能預測錯誤」的能力。 - 強化程式風格與一致性：透過 clang-format 與 Git hook 強化開發流程的規範。 ### 效能與安全驗證導向的實作訓練 - 使用 dudect 進行時間複雜度的實驗性驗證：這比單純的 Big-O 理論更實際，老師可能希望你們跳脫紙上談兵，開始關心實際效能差異。 - CERN 的安全編碼建議：移除如 gets/sprintf/strcpy 等危險函式，建立「預防性安全意識」。 ### 開發工具與工作流程導入 - Git 實務操作：不只是基本操作，而是要學會 branch 管理、hook、自動化測試整合，甚至在 pre-push 時驗證程式碼品質。 - 良好 commit message 的建立：結合 git-good-commit，希望你們習慣撰寫清楚、具描述性的提交訊息——這對開源貢獻或團隊協作都極其重要。 - Makefile 模組化：訓練你寫出可維護、可擴充的建構系統。 - 這們課的學習內容非常多及扎實，為了記憶方便及長久能靈活運用，先試著猜測這個作業的task目標與其意義 - 學習目標 - 機率統計 - 目的: 數學基礎養成及分析程式效能 - 方式 - shuffle的 - DSA - 目的: Linux 底層很多指標，好的資料結構可用於 - DevOps/CICD - Git pre-commit hook - Linter - clang-format: 一一致的程式風格 - GNU Aspell: 拼字檢查 - Code Quality - Cppcheck: 靜態程式碼分析 - Valgrind: 動態程式分析 - Testing - 除錯 - Address Sanitizer - Linked List 會有很多機會遇到 - 創新 - 目的: - 方式 - 閱讀paper ## File ### 程式結構與功能 - Makefile：定義了構建規則和測試目標（如 check 和 valgrind）。支持多平台構建（如 macOS 和 Linux）。 - harness.h：提供自定義內存分配函數（如 test_malloc 和 test_free）。支持檢測內存分配錯誤和限制內存分配模式。 - console.c：實現了命令行解析和執行。提供了命令添加功能（如 add_cmd）。 - qtest.c：初始化測試環境（如隨機數種子、命令行歷史）。提供交互式命令行和測試功能。 ### 快速開始熟悉隊列接口：查看 queue.h，理解需要實現的函數和數據結構。構建與運行測試：使用 make 構建項目，並運行 qtest 測試程序。增量開發與測試：修改 queue.c，逐步實現功能，並使用 driver.py 驗證。內存檢查：使用 valgrind 確保內存分配和釋放正確。 ### Lab - https://github.com/sysprog21/lab0-c - OS: Ubuntu 24.04 - Files - queue.c - q_{function}: 待實作 - Makefile: 編譯及如何執行 - ./qtest: 編譯後執行測試程式 ## Links - [作業需求](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-f) - [2025 作業參考](https://hackmd.io/@sysprog/linux2025-homework1) - [N03: review](https://hackmd.io/@sysprog/linux2025-review) ## 環境 ```bash alanhc@alanhc:~/lab0-c$ uname -a Linux alanhc 6.8.0-55-generic #57-Ubuntu SMP PREEMPT_DYNAMIC Wed Feb 12 23:42:21 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux alanhc@alanhc:~/lab0-c$ hostnamectl Static hostname: alanhc Icon name: computer-desktop Chassis: desktop 🖥️ Machine ID: 85df47c270b342f3b43b1b02b90d3c16 Boot ID: a64d2aee6fcd432f91d013489094b858 Operating System: Ubuntu 24.04.2 LTS Kernel: Linux 6.8.0-55-generic Architecture: x86-64 Hardware Vendor: ASUSTeK COMPUTER INC. Hardware Model: Pro WS W680-ACE IPMI Firmware Version: 3901 Firmware Date: Fri 2024-09-27 Firmware Age: 5month 1w 4d alanhc@alanhc:~/lab0-c$ 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. alanhc@alanhc:~/lab0-c$ ldd --version ldd (Ubuntu GLIBC 2.39-0ubuntu8.4) 2.39 Copyright (C) 2024 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. Written by Roland McGrath and Ulrich Drepper. alanhc@alanhc:~/lab0-c$ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 46 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 28 On-line CPU(s) list: 0-27 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i7-14700 CPU family: 6 Model: 183 Thread(s) per core: 2 Core(s) per socket: 20 Socket(s): 1 Stepping: 1 CPU(s) scaling MHz: 17% CPU max MHz: 5400.0000 CPU min MHz: 800.0000 BogoMIPS: 4224.00 ``` ## 開發紀錄 ### 間接指標 (indirect pointer) - https://hackmd.io/@sysprog/c-linked-list - 程式：`Node **indirect = &list->head;` - 視覺化： ```mermaid graph LR subgraph linked list head==>node1==>node2 end subgraph pointer to pointer indirect==>head end ``` - 紫色是指標 ### Queue.[ch] - 參考過往lab0 好的範例 -> [yanjiew1/lab0-c](https://github.com/yanjiew1/lab0-c) [hackmd](https://hackmd.io/@yanjiew/linux2023q1-lab0) - 使用indirect pointer讓指標更有效 #### q_new: 建立新的「空」佇列; - 根據 cppreference, 要記憶體要使用malloc：`void *malloc( size_t size );` - 可使用 `list.h` 裡面的 INIT_LIST_HEAD - inline: 告訴編譯器將這個函式展開，直接將函式內容插入呼叫它的地方，而不是執行標準的函式呼叫（call 和 return）。 | 關鍵字 | 作用 | 為何使用？ | | -------- | -------- | -------- | | static | 限制作用範圍 | 只在當前編譯單元內可見，避免命名衝突 | | inline | 提高執行效率 | 內聯展開，減少函式呼叫開銷 | | void | 無返回值 | 只執行初始化操作，無需返回值 | - 解釋：INIT_LIST_HEAD將雙向指標的next及prev都指向 list的head ```clike= static inline void INIT_LIST_HEAD(struct list_head *head) { head->next = head; head->prev = head; } ``` - 新增一個 ```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_for_each_entry_safe在list.h被定義 ```clike= #if __LIST_HAVE_TYPEOF #define list_for_each_entry_safe(entry, safe, head, member) \ for (entry = list_entry((head)->next, typeof(*entry), member), \ safe = list_entry(entry->member.next, typeof(*entry), member); \ &entry->member != (head); entry = safe, \ safe = list_entry(safe->member.next, typeof(*entry), member)) #else #define list_for_each_entry_safe(entry, safe, head, member) \ for (entry = safe = (void *) 1; sizeof(struct { int : -1; }); \ ++(entry), ++(safe)) #endif ``` - `#define list_for_each_entry_safe(entry, safe, head, member) \` - entry → 當前遍歷的節點（對應 element_t *） - safe → 儲存下一個節點的指標，確保刪除當前節點後仍能繼續遍 - head → 指向 list_head 的頭節點 - member → 結構內的 list_head 成員變數（在 element_t 內就是 list） - 遍歷到直到回到head - queue.h 裡面的 q_release_element釋放 ```clike= static inline void q_release_element(element_t *e) { test_free(e->value); test_free(e); } ``` - test_free 是被定義在 harness.c ，有安全釋放的技巧 ```clike= void test_free(void *p) { if (noallocate_mode) { report_event(MSG_FATAL, "Calls to free disallowed"); return; } if (!p) return; block_element_t *b = find_header(p); size_t footer = *find_footer(b); if (footer != MAGICFOOTER) { report_event(MSG_ERROR, "Corruption detected in block with address %p when " "attempting to free it", p); error_occurred = true; } b->magic_header = MAGICFREE; *find_footer(b) = MAGICFREE; memset(p, FILLCHAR, b->payload_size); /* Unlink from list */ block_element_t *bn = b->next; block_element_t *bp = b->prev; if (bp) bp->next = bn; else allocated = bn; if (bn) bn->prev = bp; free(b); allocated_count--; } ``` - noallocate_mode: 是否允許釋放記憶體 - MAGICFOOTER: 驗證記憶體是否完整 - magic_header、find_footer 標記MAGICFREE代表已經釋放 - free() 釋放 - 更新分配計數 allocated_count ```cpp= void q_free(struct list_head *l) { if (!l) return; element_t *safe, *it; list_for_each_entry_safe (it, safe, l, list) q_release_element(it); free(l); } ``` #### q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則); - 用malloc初始化記憶體記憶體 - 用strdup 產生字串副本 ```clike= static inline element_t *q_new_elem(char *s) { element_t *elem = malloc(sizeof(element_t)); char *tmp = strdup(s); if (!elem || !tmp) { free(elem); free(tmp); return NULL; } elem->value = tmp; return elem; } ``` - list_add 將指標加入List - list_add 由 list.h定義 ```clike= static inline void list_add(struct list_head *node, struct list_head *head) { struct list_head *next = head->next; next->prev = node; node->next = next; node->prev = head; head->next = node; } ``` ```clike= bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *elem = q_new_elem(s); if (!elem) return false; list_add(&elem->list, head); return true; } ``` #### q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則); ```clike= static inline void list_add_tail(struct list_head *node, struct list_head *head) { struct list_head *prev = head->prev; prev->next = node; node->next = head; node->prev = prev; head->prev = node; } ``` - 使用list.h定義的list_add_tail ```clike= bool q_insert_tail(struct list_head *head, char *s) { if (!head || !s) return false; element_t *new_element = malloc(sizeof(element_t)); if (!new_element) return false; new_element->value = strdup(s); if (!new_element->value) { free(new_element); return false; } list_add_tail(&new_element->list, head); return true; } ``` #### q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點; - list.h定義 ```clike= #define list_first_entry(head, type, member) \ list_entry((head)->next, type, member) ``` ```clike= element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *elem = list_first_entry(head, element_t, list); list_del(&elem->list); if (!sp || !bufsize) return elem; strncpy(sp, elem->value, bufsize); sp[bufsize - 1] = '\0'; return elem; } ``` #### q_remove_tail: 在佇列尾端 (tail) 移去 (remove) 給定的節點; - 由於是雙向Linked List因此可藉由q_remove_head反推 ```clike= element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; return q_remove_head(head->prev->prev, sp, bufsize); } ``` #### q_size: 計算目前佇列的節點總量; - 如果head=NULL, 長度0 - 使用 `list.h` 定義好的marco list_for_each 去迭代，讓len++ ```clike= #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) ``` - ```clike= int q_size(struct list_head *head) { if (!head) return 0; int len = 0; struct list_head *li; list_for_each (li, head) len++; return len; } ``` #### q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List - 左右指標相遇即爲中間點 - 元素個數奇數及偶數要不同處理方式 - 當 left == right 或 left->next == right 時，代表 right 指向的就是中間節點 - 奇數個元素時：最後 left == right，right 就是要刪除的節點。 - 偶數個元素時：最後 left->next == right，選擇 right 為要刪除的節點。 ```clike= bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return false; struct list_head *left = head->next; struct list_head *right = head->prev; while (left != right && left->next != right) { left = left->next; right = right->prev; } list_del(right); element_t *elem = list_entry(right, element_t, list); q_release_element(elem); return true; } ``` #### q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II - 解釋流程： - head → A → A → B → C → C → D → NULL - 刪除重複元素的過程如下： 1. A 和 A 相同，標記 cut。 2. B 不等於 A，所以 list_cut_position 把 A → A 移到 pending。 3. C 和 C 相同，標記 cut。 4. D 不等於 C，所以 list_cut_position 把 C → C 移到 pending。 5. 遍歷 pending，釋放 A → A → C → C 的記憶體。 - head → B → D → NULL - LIST_HEAD(pending); ：暫存重複元素 - if (&safe->list != head && !strcmp(safe->value, it->value)) 找出重複元素 - Detect duplicated elements：將重複元素切到pending ```clike= bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) return false; LIST_HEAD(pending); element_t *it, *safe; struct list_head *cut = head; list_for_each_entry_safe (it, safe, head, list) { if (&safe->list != head && !strcmp(safe->value, it->value)) continue; /* Detect duplicated elements */ if (it->list.prev != cut) { LIST_HEAD(tmp); list_cut_position(&tmp, cut, &it->list); list_splice(&tmp, &pending); } cut = safe->list.prev; } /* Process pending list */ list_for_each_entry_safe (it, safe, &pending, list) q_release_element(it); return true; } ``` #### q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs - 使用 [q_reverseK](#q_reverseK-類似-q_reverse，但指定每-k-個節點為一組，進行反向順序排列，詳見-LeetCode-25-Reverse-Nodes-in-k-Group) #### q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點; - list_for_each_safe: 安全遍歷的marco, safe代表安全儲存的下個節點 - list_move: 將迭代的it移到head - TODO: 如果是雙向應該可以直接翻轉 ```clike= void q_reverse(struct list_head *head) { if (!head) return; struct list_head *it, *safe; /* Iterate the list and move each item to the head */ list_for_each_safe (it, safe, head) list_move(it, head); } ``` #### q_reverseK: 類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列，詳見 LeetCode 25. Reverse Nodes in k-Group - Goal: 每k個翻轉一次，最後不足k不翻轉 - ![截圖 2025-03-16 上午10.07.22-1](https://hackmd.io/_uploads/rJquzhm21x.jpg) ```clike= void q_reverseK(struct list_head *head, int k) { // https://leetcode.com/problems/reverse-nodes-in-k-group/ if (!head || list_empty(head)) return; struct list_head *it, *safe, *cut; int cnt = k; cut = head; list_for_each_safe (it, safe, head) { if (--cnt) continue; LIST_HEAD(tmp); cnt = k; list_cut_position(&tmp, cut, it); q_reverse(&tmp); list_splice(&tmp, cut); cut = safe->prev; } } ``` #### q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法; - 9-14 是在找中間節點 - list_cut_position：將list透過中間節點分成 head及second - 利用分治法(Conquer) q_sort - q_merge_two: 將head及second按照給定順序（descend）合併 - merge 過程可以參考 [NeetCode講解Merge Sorted Array - Leetcode 88 - Python](https://www.youtube.com/watch?v=P1Ic85RarKY) ```clike= void q_sort(struct list_head *head, bool descend) { /* Try to use merge sort*/ if (!head || list_empty(head) || list_is_singular(head)) return; /* Find middle point */ struct list_head *mid, *left, *right; left = right = head; do { left = left->next; right = right->prev; } while (left != right && left->next != right); mid = left; /* Divide into two part */ LIST_HEAD(second); list_cut_position(&second, mid, head->prev); /* Conquer */ q_sort(head, descend); q_sort(&second, descend); /* Merge */ q_merge_two(head, &second, descend); } ``` #### q_ascend 及 q_descend: 參閱 LeetCode 2487. Remove Nodes From Linked List，注意節點間的順序 - 從尾端開始，**移除比右邊小或相等** 的節點 - 13-14 找前一個節點 - 15-21 移除較小的節點 ```clike= int q_ascend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head)) return 0; /** * Traverse from the last entry and remove the element that is * smaller or equal to its right. Also count the number of elements. */ int cnt = 1; element_t *cur = list_last_entry(head, element_t, list); while (cur->list.prev != head) { element_t *prev = list_last_entry(&cur->list, element_t, list); if (strcmp(prev->value, cur->value) > 0) { list_del(&prev->list); q_release_element(prev); } else { cnt++; cur = prev; } } return cnt; } ``` #### q_merge: 合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 LeetCode 23. Merge k Sorted Lists - 2-merge 優化：小 queue 優先合併，大 queue 先不動，避免「大吃小」，讓合併的 cost 分攤得更平均。 - pending：用來存放還沒合併的 queue。 - empty：用來存放被合併完的 queue_contex_t（可視為空）。 - 18-23: 每當 pending 有超過 3 個 queue，檢查前三個 queue 的 size。 - 24-25: 若 y 已經大於等於 z 的 2 倍，暫不合併，直接 break。 - 27-35: 合併 - 如果 x 比 z 小，就把 x merge 到 y。 - 否則就把 y merge 到 z。 - 被 merge 掉的 queue_contex_t（空殼）丟到 empty，n–。 - 收尾 - 40-47: 最後 pending 只剩 1~2 個 queue，直接硬合併剩下的。 - 為何有效率？ - 跟傳統的「直接從 k 個 queue 依序合併」相比，這個 2-merge 策略可以讓每次合併時的兩個 queue size 差距較小，減少單次 merge 的成本（不會讓小 queue 一下子被 merge 到超大 queue 裡面）。 - 例子解釋 ``` q1: [1] -> [4] -> [6] q2: [2] -> [5] q3: [3] -> [7] ``` 答案： ``` [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] ``` - 比較合併 - x 的大小為 3，z 的大小為 2。 - 因為 x 比 z 大，所以我們將 x 和 y 合併。 - 合併後，我們將合併結果放入 empty 中，並從 pending 中移除 x 和 y。 - 因此 q1 + q2 -> [1] -> [2] -> [4] -> [5] (這是合併結果) pending: [q3] empty: [1] -> [2] -> [4] -> [5] - 第二次合併 - 現在 pending 中只有 q3，所以 pending 中剩下的只有一個 queue，不需要再進行進一步的合併。 ``` empty: [1] -> [2] -> [4] -> [5] q3: [3] -> [7] ``` ```clike= int q_merge(struct list_head *head, bool descend) { // https://leetcode.com/problems/merge-k-sorted-lists/ if (!head || list_empty(head)) return 0; if (list_is_singular(head)) return list_first_entry(head, queue_contex_t, chain)->size; /* Use 2-merge algorithm in https://arxiv.org/pdf/1801.04641.pdf */ LIST_HEAD(pending); LIST_HEAD(empty); int n = 0; while (!list_empty(head)) { list_move(head->next, &pending); n++; while (n > 3) { queue_contex_t *x, *y, *z; x = list_first_entry(&pending, queue_contex_t, chain); y = list_first_entry(&x->chain, queue_contex_t, chain); z = list_first_entry(&x->chain, queue_contex_t, chain); if (y->size >= z->size << 1) break; if (x->size < z->size) { y->size = q_merge_two(y->q, x->q, descend); list_move(&x->chain, &empty); n--; } else { z->size = q_merge_two(z->q, y->q, descend); list_move(&y->chain, &empty); n--; } } } /* Merge remaining list */ while (n > 1) { queue_contex_t *x, *y; x = list_first_entry(&pending, queue_contex_t, chain); y = list_first_entry(&x->chain, queue_contex_t, chain); y->size = q_merge_two(y->q, x->q, descend); list_move(&x->chain, &empty); n--; } /* Move the last queue and empty queue to head */ list_splice(&empty, head); list_splice(&pending, head); return list_first_entry(head, queue_contex_t, chain)->size; } ``` - strdup(s): 建立s的copy - 參考 https://hackmd.io/@Henry0922/linux2025-homework1#運用-Valgrind-排除-qtest-實作的記憶體錯誤 ## 運用 Address Sanitizer 除錯 - 可以參考：https://github.com/google/sanitizers/wiki/AddressSanitizerFlags - 在Makefile裡面有加入 ``` CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common LDFLAGS += -fsanitize=address ``` make SANITIZER=1 ## 運用 Valgrind 排除 qtest 實作的記憶體錯誤 - 分析記憶體問題：https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b#以-Valgrind-分析記憶體問題 - 使用時機：如果有 Segmentation fault occurred. - 用法：valgrind -q --leak-check=full ./qtest ## 運用 Valgrind Massif 觀察 simulation 之記憶體使用情形 ``` valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd ``` - 會在此目錄新增massif.out.<pid> ``` massif-visualizer massif.out.<pid> ``` ![image](https://hackmd.io/_uploads/rkT63V86yx.png) ## 提供新的命令 shuffle ### Background - 這邊內容有參考：https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d - 虛無假說：「沒有差別、沒有影響、一切照舊」的說法。在統計檢定中，我們通常是假設某件事沒發生，然後用數據來看看「是否有足夠證據推翻這個假設」。 #### Definition: 虛無假說（Null Hypothesis）：用符號表示為 H₀，指的是「我們希望用資料來推翻的初始假設」。對應的對立假說（Alternative Hypothesis，H₁ 或 Hₐ），就是你想證明的新觀點。 - 實際例子 1：藥物實驗問題：這個新藥物真的能有效降低血壓嗎？ - 虛無假說 H₀：這個新藥「對血壓沒有影響」。 - 對立假說 H₁：這個新藥「能有效降低血壓」。然後我們收集數據（比如 100 個人服藥後的血壓變化），計算 p 值，來決定是否要「拒絕虛無假說」。 #### 檢定流程簡圖 1. 設定 $H_0$（虛無假說）與 $H_1$（對立假說） 2. 選擇適當的檢定方式（t 檢定、卡方檢定等） 3. 設定顯著水準 $α$（例如 0.05） 4. 計算 $p$ 值 5. 如果 $p < α$ → 拒絕 $H_0$，接受 $H_1$ > 常見誤解 ❌ 「接受虛無假說」≠「虛無假說正確」 ✅ 正確說法應該是：「目前沒有足夠證據拒絕虛無假說」 #### 想驗證什麼？這個洗牌演算法真的有把每種排列弄得一樣機會出現嗎？這就是你的虛無假說（H₀）： H₀：每一種排列出現的機率相同（符合均勻分布）對立假說（H₁）則是： H₁：至少有一種排列出現的機率不同（不均勻） #### 為何使用 Pearson's Chi-squared Test? - Chi-squared test 是用來比較「實際出現次數 vs. 預期次數」的一種方法，非常適合做這種「分布是否均勻」的檢定。假設你跑洗牌 10,000 次，陣列長度是 3：所有可能排列為 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 每一種應該出現約 1,667 次（= 10000 / 6）你實際記錄每一種出現的次數，代入 Chi-squared test 公式： ![image](https://hackmd.io/_uploads/Hy68xhCp1g.png) $X^2 = \sum_{i=1}^n {(O_i - E_i)^2 \over E_i}$ - 如果洗牌是公平的，實際出現次數應該接近理論值（均勻） - Chi-squared test 幫你比較這兩者差異若差異太大（p 值太小），代表可能不是公平洗牌 → 拒絕虛無假說若差異合理（p 值夠大），代表沒足夠證據說這個 shuffle 有問題 → 不拒絕虛無假說 > 補充什麼情況不能用這方法？當可能的排列太多（像長度為 10 的陣列會有 3628800 種），你幾乎無法跑夠多次來覆蓋所有排列。 → 這時可以轉而分析「位置分布是否均勻」等簡化的統計特徵。 - 如何知道p value 是否夠大？ - p大代表統計具有顯著性，可以藉由查表 https://en.wikipedia.org/wiki/Chi-squared_distribution#Table_of_%CF%872_values_vs_p-values - degrees of freedom - 對於 N 個隨機樣本而言，自由度為 N - 1。我們 shuffle 3 個數字會有六種結果，因為加起來機率為 1 ，所以實際上可以自由變換的變數只有五個，其中一個結果的機率為 1 減去另外五個結果發生的機率，所以自由度為 5。 - 自由度為5 在經過[實驗](#%E5%AF%A6%E9%A9%97) ### 實驗 - 參考 https://hackmd.io/@dennis40816/linux2025-homework1#%E6%96%B0%E5%A2%9E-shuffle-%E5%91%BD%E4%BB%A4%E8%88%87-prng-%E9%81%B8%E9%A0%85 - 新增cmd - console.h - ADD_COMMAND marco ```cpp! #define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param) ``` > #cmd 並不是保留字，也不需要在其他地方定義。它是 C 預處理器中的一個特殊語法，稱為字符串化操作符（stringizing operator）。當你在宏中使用 # 時，預處理器會將後面的參數轉換為字符串。 - console.c - 呼叫 - 其中 operation 是一個function pointer 在console.h被定義 ```cpp= void add_cmd(char *name, cmd_func_t operation, char *summary, char *param) { ``` - console.h ```cpp= typedef bool (*cmd_func_t)(int argc, char *argv[]); - 因此所有 console.c 裡面 do_OOO的會被initlize (參考 console.c>init_cmd()>ADD_COMMAND用法) ``` ### Fisher-Yates algorithm - [How to shuffle an array (Fisher-Yates algorithm) - Inside code](https://youtu.be/4zx5bM2OcvA) ![image](https://hackmd.io/_uploads/Byub4pjaJe.png) ### PRNG (Pseudo Random Number Generators) ### 測試亂數均勻分佈 https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F https://github.com/HenryChaing/lab0-c/blob/master/queue.c https://github.com/Dennis40816/lab0-c/commit/0d63c0e8e3cc2d4e06e7374b396a07bf26cb54b4 - https://hackmd.io/@Jackiempty/linux2025-homework1 - 測試程式 - 自由度 4!-1 = 12-1 = 11 ``` --- trace-16-perf 6/6 +++ TESTING trace trace-17-complexity: # Test if time complexity of 'q_insert_tail', 'q_insert_head', 'q_remove_tail', and 'q_remove_head' is constant ERROR: Probably not constant time or wrong implementation ERROR: Probably not constant time or wrong implementation Probably constant time Probably constant time --- trace-17-complexity 0/5 --- TOTAL 95/100 ``` ## 研讀論文並改進 dudect ### Bakcground - 使用一些樣本來測試程式複雜度是否是常數時間，可使用Student’s t-distribution ### Student’s t-distribution - 解釋：Student’s t-distribution 是一種機率分布，用來描述「樣本平均值與母體平均值之間的差異」在標準化後的行為，當母體標準差未知，且樣本數較小（例如 n < 30）時特別有用。 - 適用：樣本數不多的情況下進行估計與假設檢定 > 小整理 ![image](https://hackmd.io/_uploads/S1F_1aR6yg.png) - 參考作業 https://hackmd.io/@vax-r/linux2024-homework1#解釋-simulation-做法 ### Dude, is my code constant time? - [Pleeplexity Summary](https://www.perplexity.ai/search/summarize-this-file-eWWSaWzpQUGOKBE1zr.79Q) - Dudect, a tool designed to assess whether a piece of code runs in constant time on a given platform. - - 論文方法 1. Step 1: Measure execution time - Measure execution time repeatedly using CPU cycle counters or high-resolution timers. 3. Step 2: Apply post-processing - Apply pre-processing (e.g., cropping outliers) to refine measurements. 5. Step 3: Apply statistical test - Use statistical tests (e.g., Welch’s t-test) to determine if timing variability exists. - 參考 - https://hackmd.io/@vax-r/linux2024-homework1#解釋-simulation-做法 - code - qtest.c - is_insert_head_const - fixture.h - bool is_##x##_const(void); - DUT_FUNCS - gcc -E -P dudect/fixture.h ```cpp= #define _(x) bool is_##x##_const(void); DUT_FUNCS #undef _ ``` 展開會變成 ``` bool is_DUT_insert_head_const(void); bool is_DUT_insert_tail_const(void); bool is_DUT_remove_head_const(void); bool is_DUT_remove_tail_const(void); ``` 用gcc -E -P看 ``` enum { DUT_insert_head, DUT_insert_tail, DUT_remove_head, DUT_remove_tail, }; ``` - fixture.c ```cpp! _Bool is_insert_head_const(void); _Bool is_insert_tail_const(void); _Bool is_remove_head_const(void); _Bool is_remove_tail_const(void); ``` 主要測試func. ``` test_const ... result = doit(mode); ``` - https://github.com/oreparaz/dudect/blob/dc269651fb2567e46755cfb2a13d3875592968b5/src/dudect.h#L303 - 要丟掉前幾個，因此改fixture.c - doit - update_statistics ## 分析記憶體問題 - valgrind ### Memory Leak ```cpp= #include <stdlib.h> void func(void) { char *buff = malloc(10); } int main(void) { func(); return 0; } ``` ``` alanhc@alanhc-NUC7i7DNHE:~/workspace$ valgrind -q --leak-check=full ./case1 ==198677== 10 bytes in 1 blocks are definitely lost in loss record 1 of 1 ==198677== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==198677== by 0x10915E: func (case1.c:3) ==198677== by 0x109172: main (case1.c:6) ==198677== ``` - memory lost 1. Definitely lost（明確遺失） - 定義：你配置了記憶體（malloc），但之後再也沒有指標指向它，也沒釋放。 - 代表你真的忘記 free()，而且這段記憶體永遠找不回來。 ``` void leak() { char *p = malloc(100); p = NULL; // 把指標蓋掉了 // malloc 的那段記憶體就找不回來了 } ``` 2. Indirectly lost（間接遺失） - 定義：有一個記憶體區塊被 malloc，但它是透過另一塊記憶體間接存取；而當「父記憶體」也 lost 時，這塊記憶體也失去參考。 ``` typedef struct { char *data; } Wrapper; void leak() { Wrapper *w = malloc(sizeof(Wrapper)); w->data = malloc(100); // 這段也會被 valgrind 當作 indirectly lost free(w); // 忘了 free(w->data); } ``` 3. Still reachable（仍可存取） - 記憶體仍有變數指向，還能 free，但你沒 free。 - 常發生在 global 變數或 static buffer 沒手動釋放。 ``` char *global_buf; int main() { global_buf = malloc(1024); // 程式結束時仍指向記憶體 return 0; // global_buf 還在，但沒釋放 } ``` 4. Possibly lost（可能遺失） - 定義：記憶體指標有點奇怪，Valgrind 無法確定是不是 lost。 - 例如：偏移了原本指標、複製錯誤或多次 free()。 ``` char *p = malloc(100); free(p + 1); // ❌ 錯誤釋放，導致 Valgrind 判定可能遺失 ``` ![image](https://hackmd.io/_uploads/rJyUtVGJlg.png) ### Invalid memory acc - Invalid memory access 有時不會立即造成 segmentation fault，所以不會有 core dump 可分析 ``` alanhc@alanhc-NUC7i7DNHE:~/workspace$ valgrind -q --leak-check=full ./case2 ==199461== Invalid write of size 4 ==199461== at 0x1091AD: main (case2.c:7) ==199461== Address 0x4a7e043 is 3 bytes inside a block of size 4 alloc'd ==199461== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==199461== by 0x10919E: main (case2.c:6) ==199461== ==199461== Invalid read of size 4 ==199461== at 0x1091D6: main (case2.c:12) ==199461== Address 0x4a7e0a0 is 13 bytes after a block of size 3 alloc'd ==199461== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==199461== by 0x1091C9: main (case2.c:11) ==199461== ==199461== Invalid read of size 4 ==199461== at 0x1091FE: main (case2.c:16) ==199461== Address 0x4a7e090 is 0 bytes inside a block of size 3 free'd ==199461== at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==199461== by 0x1091F9: main (case2.c:13) ==199461== Block was alloc'd at ==199461== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==199461== by 0x1091C9: main (case2.c:11) ==199461== ==199461== Invalid free() / delete / delete[] / realloc() ==199461== at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==199461== by 0x109221: main (case2.c:19) ==199461== Address 0x4a7e090 is 0 bytes inside a block of size 3 free'd ==199461== at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==199461== by 0x1091F9: main (case2.c:13) ==199461== Block was alloc'd at ==199461== at 0x4846828: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so) ==199461== by 0x1091C9: main (case2.c:11) ==199461== ``` - Invalid write of size 4 ### 分析記憶體使用狀況 - Massif 可分析 Heap blocks Heap administration blocks Stack sizes. ## 添加cmd - q_test - main → run_console → cmd_select → interpret_cmd → parse_args - 因此新增cmd步驟，以hello 為例 1. 在console.c新增function ``` bool do_hello(int argc, char *argv[]) { return (bool) printf("Hello, World\n"); } ``` 2. 在init_cmd新增 `ADD_COMMAND(hello, "Print hello message", "");` ## 網頁伺服器 - linenoise.c - linenoise()->line_raw()->line_edit() 裡面的while(1) - 用 read()會阻塞 - e.g. nread = read(l.ifd, &c, 1); - [CS:APP RIO 套件](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-f%3Fstext%3D3579%253A14%253A0%253A1745243327%253AC1lvfM) - RIO - Unbuffered input and output functions. : no application-level buffering. - Buffered input functions: buffered RIO input functions are thread-safey - 《CS:APP》設計的一個 I/O 套件，用來解決「Unix I/O 在網路程式或多執行緒環境中容易出現的短讀（short count）與不安全問題」。 - RIO 原理 1. Unbuffered I/O（無緩衝） - 函式： rio_readn() 與 rio_writen() - 功能：直接在使用者記憶體與檔案描述符間傳輸資料（類似 read/write），但會自動處理短讀／短寫（short count）。 - 場景：適合傳送／接收 binary 資料（尤其是網路 socket），如 Web 伺服器的檔案傳送。 - 考量點： - 使用者無需處理迴圈讀寫。 - 自動處理 read()/write() 被 signal 中斷（EINTR）的情況。 - 遇 EOF 才返回 short count，否則會讀滿為止。 2. Buffered I/O（有緩衝） - 函式： rio_readlineb() 與 rio_readnb()（要搭配 rio_readinitb() 初始化） - 原理： - 使用一個應用層的 buffer（rio_t 結構體），先將資料讀入 buffer，再從中提供給使用者。 - 可以有效避免每個 byte 都陷入 kernel（陷入開銷大，會拖慢效能）。 - 特點： - Thread-safe（多執行緒安全）。 - 可混合讀取文字與 binary。 - 支援行為單位讀取，適合處理文字協議（如 HTTP）。 - 考量點： - 適合文字協定處理（例如 HTTP 的 header 行）及變動格式的讀取。 - 不建議與 rio_readn() 混用在同一個檔案描述符上，否則緩衝會混亂。 - 設計目標之一是比 C 標準 I/O 更安全、更可控、更適用於網路場景。 - 與其他比較 ![image](https://hackmd.io/_uploads/HJGyf0mJxe.png) - 為何需要 RIO？ 1. 網路讀寫的不可預測性：你可能只收到一部分封包，所以必須「堅持讀到完整資料」。 2. C 標準函式庫有 static buffer，非 thread-safe。 3. 低階 Unix I/O 不緩衝、也不處理 short count，要自己寫迴圈處理。 4. RIO 把這些都包好，保證讀寫的 robustness。 ### 解釋 select 系統呼叫在本程式的使用方式 - 什麼是select? - [select()](http://man7.org/linux/man-pages/man2/select.2.html) 是一種 multiplexing I/O（多工 I/O）技術，可以 **同時監控多個檔案描述符（file descriptor）是否準備好做 I/O 操作**。 - 常見用途 - 製作簡易 TCP server - 建立聊天室服務 - 撰寫 shell 或交互式工具 - 取代 read() 阻塞操作，提高反應性 - 技術重點 - fd_set 是個位元集合（bit mask），由 FD_ZERO、FD_SET、FD_ISSET 來操作。 - select() 是一個阻塞式系統呼叫，直到： 1. 有指定的 fd 準備好（可讀／可寫） 2. 或者發生錯誤 3. 或者 timeout - 比較 ![image](https://hackmd.io/_uploads/HkonQC71ex.png) - 例子 - 等待 5 秒內是否有標準輸入可讀，如果有，就馬上回應。 ```cpp= fd_set rfds; struct timeval tv; int retval; FD_ZERO(&rfds); // 清空集合 FD_SET(0, &rfds); // 加入標準輸入 (fd=0) tv.tv_sec = 5; // 等待 5 秒 tv.tv_usec = 0; retval = select(1, &rfds, NULL, NULL, &tv); if (retval == -1) perror("select()"); else if (retval) printf("有輸入可以讀取！\n"); else printf("超時，沒輸入。\n"); ``` - `console.c` > do_web - web_eventmux: 事件多工的處理函式 - web.c > web_eventmux - 3-11 設定要監聽哪些fd - 12-14: - 如果有輸入或連線進來，select() 會喚醒（否則會阻塞） - 若發生錯誤（如訊號中斷），回傳 -1 - 16-20: - 使用 FD_ISSET() 判斷是否是 server_fd 被觸發 - 使用 accept() 接收該連線，得到新的 socket web_connfd - 23-30 - 呼叫 web_recv() 讀取 client 的請求內容（可能是 HTTP GET） - 把接收到的訊息儲存到 buf 中回傳 - 33-34: 表示是使用者輸入觸發的，但函式這裡並沒有真的讀入使用者的輸入內容 ```cpp= int web_eventmux(char *buf, size_t buflen) { fd_set listenset; FD_ZERO(&listenset); FD_SET(STDIN_FILENO, &listenset); int max_fd = STDIN_FILENO; if (server_fd > 0) { FD_SET(server_fd, &listenset); max_fd = max_fd > server_fd ? max_fd : server_fd; } int result = select(max_fd + 1, &listenset, NULL, NULL, NULL); if (result < 0) return -1; if (server_fd > 0 && FD_ISSET(server_fd, &listenset)) { FD_CLR(server_fd, &listenset); struct sockaddr_in clientaddr; socklen_t clientlen = sizeof(clientaddr); int web_connfd = accept(server_fd, (struct sockaddr *) &clientaddr, &clientlen); char *p = web_recv(web_connfd, &clientaddr); char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n"; web_send(web_connfd, buffer); strncpy(buf, p, buflen); buf[buflen] = '\0'; free(p); close(web_connfd); return strlen(buf); } FD_CLR(STDIN_FILENO, &listenset); return 0; } ``` - https://hackmd.io/@Henry0922/linux2025-homework1#%E6%94%B9%E5%96%84-web-%E5%91%BD%E4%BB%A4 - 為何有效？ 1. 有連線來 → accept() 得到 web_connfd 2. select(web_connfd, stdin) 如果 stdin 有輸入 → 回傳 0，主程式去處理 CLI 如果 socket 有資料 → 執行 web_recv() 結果是： - 如果使用者想按 Ctrl+C、輸入 quit、status 等指令，可以立即響應 - 如果 socket 端遲遲不送資料（例如爛 client），你的伺服器不會卡在 read()，而是繼續工作 - 主要改進20-23行，問題： ``` int connfd = accept(...); // 成功了！但對方不送資料怎麼辦？ char *p = web_recv(connfd); // 卡住了（阻塞）！ ``` - https://hackmd.io/@salmonii/linux2025-homework1#select-%E7%B3%BB%E7%B5%B1%E5%91%BC%E5%8F%AB%E5%9C%A8%E6%9C%AC%E7%A8%8B%E5%BC%8F%E7%9A%84%E4%BD%BF%E7%94%A8%E6%96%B9%E5%BC%8F https://hackmd.io/@charliechiu/linux2025-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8 https://hackmd.io/@Guanchun0803/linux2025-homework1#%E8%A7%A3%E9%87%8B-select-%E7%B3%BB%E7%B5%B1 https://hackmd.io/@Potassium-chromate/H1pgXhu5Jl#%E8%A7%A3%E9%87%8B-select-%E7%B3%BB%E7%B5%B1 https://hackmd.io/@Potassium-chromate/H1pgXhu5Jl#%E8%A7%A3%E9%87%8B-select-%E7%B3%BB%E7%B5%B1 https://hackmd.io/@ericisgood/linux2025-homework1#%E7%A0%94%E8%AE%80-select https://hackmd.io/@ibat10clw/linux2025-homework1#select-%E7%B3%BB%E7%B5%B1%E5%91%BC%E5%8F%AB https://hackmd.io/@Max042004/linux2025-homework1#tiny-web-server https://hackmd.io/@DboOgKS6RtOmMLCltFsBig/linux2025-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8 https://hackmd.io/@BigMickey/linux2025-homework1#%E6%95%B4%E5%90%88-tiny-web-server-%E8%88%87-web-%E5%91%BD%E4%BB%A4 ### 透過 Massif 視覺化 simulation 過程中的記憶體使用 - 閱讀與分析這張 Heap 記憶體消耗圖 (Memory Chart) - X 軸：時間刻度 time in i - 單位 i = CPU 指令數 (instructions executed)，Massif 以「程式執行到第幾條指令」作為時間基準。 - 數字範圍常呈指數級，例如從 0 → 1e11 → 2e11。 - Y 軸：Heap 大小 - 右側附加刻度顯示對應的 KiB / MiB。 - 例：圖頂寫 Peak of 1.1 MiB at snapshot #1，表示最高峰的有效佔用 (in‑use) 為 1.1 MiB，出現在 snapshot #1。 - 不可用address senitizer編譯過的qtest ![image](https://hackmd.io/_uploads/HJ58X1V1eg.png) - _IO_file_doallocate：一開始有印一些東西，屬於這 - doit: dudect/fixture.c來測試的func，會隨著測資越來越大佔用記憶體越多 ![image](https://hackmd.io/_uploads/ry9FDJNkgl.png) - 參考：https://github.com/HenryChaing/lab0-c/commit/bce61aedfb93c864d2543dcf387d3e1357d1e1fe#diff-cf7858c6453d2ea6c3b0262388a7865d1b3417170da73c701663b14679b56f85 - https://hackmd.io/@alanjian85/lab0-2023#%E5%AF%A6%E4%BD%9C-shuffle-%E5%91%BD%E4%BB%A4

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.