# 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不翻轉
- 
```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>
```
## 提供新的命令 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 公式：
$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)
### 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）時特別有用。
- 適用：樣本數不多的情況下進行估計與假設檢定
> 小整理 
- 參考作業 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 判定可能遺失
```
### 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 更安全、更可控、更適用於網路場景。
- 與其他比較
- 為何需要 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
- 比較
- 例子
- 等待 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
- _IO_file_doallocate：一開始有印一些東西，屬於這
- doit: dudect/fixture.c來測試的func，會隨著測資越來越大佔用記憶體越多
- 參考：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
Sign in with Wallet
Connect another wallet