2025q1 Homework1 (lab0)

contributed by <alanhc>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

加油！

由於寫到後面幾週心態有點崩，這些東西怎麼之前都不知道，有幾句話想做精神喊話：

你不必非常出色，只要在很長的時間內，保持比其他人聰明一點點就夠了 - 查理蒙格

誠實的面對自己 - Jserv

青春很貴，你也知道實習會發生什麼事，公司不會指派重要的工作給你，他們只會指派低風險的工作，你學習到的東西並不會比你現在多。你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。

學習方法 - 小林說學習 YT
- 找到複雜東西的結構 > 結構化的理解
- 流程的思維模式

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: 編譯後執行測試程式

環境

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;
視覺化：

紫色是指標

Queue.[ch]

參考過往lab0 好的範例 -> yanjiew1/lab0-c hackmd
使用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





static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

新增一個










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被定義











#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釋放





static inline void q_release_element(element_t *e)
{
    test_free(e->value);
    test_free(e);
}

test_free 是被定義在 harness.c ，有安全釋放的技巧




































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











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 產生字串副本














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定義









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













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 準則);










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


















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定義


#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)
















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反推








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++


#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)














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 為要刪除的節點。




















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




























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_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;

list_for_each_safe: 安全遍歷的marco, safe代表安全儲存的下個節點
list_move: 將迭代的it移到head
TODO: 如果是雙向應該可以直接翻轉










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不翻轉



















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


























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 移除較小的節點

























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]






















































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 值，來決定是否要「拒絕虛無假說」。

檢定流程簡圖

設定
$H_{0}$ （虛無假說）與
$H_{1}$ （對立假說）
選擇適當的檢定方式（t 檢定、卡方檢定等）
設定顯著水準
$α$ （例如 0.05）
計算
$p$ 值
如果
$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} \frac{(O_{i} - E_{i})^{2}}{E_{i}}

如果洗牌是公平的，實際出現次數應該接近理論值（均勻）
Chi-squared test 幫你比較這兩者差異

若差異太大（p 值太小），代表可能不是公平洗牌 → 拒絕虛無假說

若差異合理（p 值夠大），代表沒足夠證據說這個 shuffle 有問題 → 不拒絕虛無假說

補充
什麼情況不能用這方法？
當可能的排列太多（像長度為 10 的陣列會有 3628800 種），你幾乎無法跑夠多次來覆蓋所有排列。 → 這時可以轉而分析「位置分布是否均勻」等簡化的統計特徵。

如何知道p value 是否夠大？
p大代表統計具有顯著性，可以藉由查表 https://en.wikipedia.org/wiki/Chi-squared_distribution#Table_of_χ2_values_vs_p-values
degrees of freedom
- 對於 N 個隨機樣本而言，自由度為 N - 1。我們 shuffle 3 個數字會有六種結果，因為加起來機率為 1 ，所以實際上可以自由變換的變數只有五個，其中一個結果的機率為 1 減去另外五個結果發生的機率，所以自由度為 5。
自由度為5 在經過實驗

實驗

參考 https://hackmd.io/@dennis40816/linux2025-homework1#新增-shuffle-命令與-prng-選項
新增cmd
console.h
- ADD_COMMAND marco

#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

#cmd 並不是保留字，也不需要在其他地方定義。它是 C 預處理器中的一個特殊語法，稱為字符串化操作符（stringizing operator）。當你在宏中使用 # 時，預處理器會將後面的參數轉換為字符串。

console.c
- 呼叫
- 其中 operation 是一個function pointer 在console.h被定義


    void add_cmd(char *name, cmd_func_t operation, char *summary, char *param)
{

console.h


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

PRNG (Pseudo Random Number Generators)

測試亂數均勻分佈

https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#測試程式
 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
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.
2. Step 2: Apply post-processing
  - Apply pre-processing (e.g., cropping outliers) to refine measurements.
3. 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



#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

_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








#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

Definitely lost（明確遺失）
- 定義：你配置了記憶體（malloc），但之後再也沒有指標指向它，也沒釋放。
- 代表你真的忘記 free()，而且這段記憶體永遠找不回來。

void leak() {
    char *p = malloc(100);
    p = NULL;  // 把指標蓋掉了
    // malloc 的那段記憶體就找不回來了
}

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

Still reachable（仍可存取）
- 記憶體仍有變數指向，還能 free，但你沒 free。
- 常發生在 global 變數或 static buffer 沒手動釋放。

char *global_buf;

int main() {
    global_buf = malloc(1024);  // 程式結束時仍指向記憶體
    return 0;                   // global_buf 還在，但沒釋放
}

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 為例

在console.c新增function

bool do_hello(int argc, char *argv[])
{
    return (bool) printf("Hello, World\n");
}

在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 套件
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，否則會讀滿為止。
  1. 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() 是一種 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 秒內是否有標準輸入可讀，如果有，就馬上回應。


















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: 表示是使用者輸入觸發的，但函式這裡並沒有真的讀入使用者的輸入內容



































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#改善-web-命令
為何有效？
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-系統呼叫在本程式的使用方式
 https://hackmd.io/@charliechiu/linux2025-homework1#整合網頁伺服器
 https://hackmd.io/@Guanchun0803/linux2025-homework1#解釋-select-系統
 https://hackmd.io/@Potassium-chromate/H1pgXhu5Jl#解釋-select-系統
 https://hackmd.io/@Potassium-chromate/H1pgXhu5Jl#解釋-select-系統
 https://hackmd.io/@ericisgood/linux2025-homework1#研讀-select
https://hackmd.io/@ibat10clw/linux2025-homework1#select-系統呼叫
 https://hackmd.io/@Max042004/linux2025-homework1#tiny-web-server
https://hackmd.io/@DboOgKS6RtOmMLCltFsBig/linux2025-homework1#整合網頁伺服器
 https://hackmd.io/@BigMickey/linux2025-homework1#整合-tiny-web-server-與-web-命令

透過 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，會隨著測資越來越大佔用記憶體越多