Linux 核心專題: 重做 lab0

執行人: popo8712
專題解說錄影

改進你的 git commit message，既然要重做，就該做得更好，否則跟四個月前一樣的程度，是不是白來了？

最近一直改版本，之前fork做的內容前陣子刪除，目前先放上這部分，會持續修改。

善用 git rebase!
好的!

Reviewed by `cheezad`

最後解釋 Student's t-distribution 的部分建議稍微多解釋一下式子裡的參數

我有在最後解釋 Student's t-distribution 的部分多加補充，也在此簡單敘述一下：
Student's t-分佈是一種常用於小樣本數據分析的連續概率分佈，特別適用於樣本量較小的情況。其概率密度函數為：

$f (t) = \frac{Γ (\frac{ν + 1}{2})}{\sqrt{ν π} Γ (\frac{ν}{2})} {(1 + \frac{t^{2}}{ν})}^{- \frac{ν + 1}{2}}$

其中，
$t$ 是隨機變量，
$ν$ 是自由度（通常為樣本數減去估計參數數量，如
$ν = n - 1$ ），
$Γ$ 函數是擴展的階乘函數，定義為
$Γ (z) = \int_{0}^{\infty} t^{z - 1} e^{- t} d t$ 。自由度
$ν$ 越大，t 分佈越接近正態分佈。t 分佈的尾部比正態分佈更厚，更適合小樣本數據分析。

Reviewd by `otteryc`

合併過程中，每次合併的大小是
$3 \times 2^{k}$ ，這樣的設計能夠更好地利用快取，提高排序效率。

上述引言似乎沒有論述過程，還麻煩多加說明合併大小以及利用大小的關係

在 Linux Kernel 的 list_sort 實現中，合併過程中的每次合併大小為
$3 \times 2^{k}$ ，這樣的設計有助於更好地利用快取，從而提高排序效率。合併大小的選擇意味著在 Merge Sort 中，數據分成兩部分進行排序，然後再將兩個有序部分合併。通常，合併的大小是 2 的冪次方，如
$2, 4, 8$ 等，因為每次分割後的部分數量翻倍。然而，Linux Kernel 的 list_sort 採用每次合併大小為
$3 \times 2^{k}$ ，即每次合併時處理的數據塊大小不是標準的 2 的冪次方，而是其 3 倍，如
$3, 6, 12$ 等。快取是處理器中的高速存儲器，用於減少訪問主存的時間。快取的工作原理是將頻繁使用的數據預先載入到快取中，加快數據訪問速度。合併排序在合併過程中，數據的讀取和寫入頻繁發生，適當大小的數據塊合併可以減少快取未命中的情況。當數據塊大小適中時，快取可以更有效地預取和存儲數據，減少內存訪問延遲，從而提高整體排序效率。這種設計利用了快取的空間局部性原理，即在同一時間內訪問的數據位於相鄰的內存地址中，使數據訪問更快。

reviewed by `dcciou`

在進行Linux Kernel的list_sort性能測試時，你是如何設計和執行測試用例的？請具體說明你的測試策略和數據收集方法，以確保測試結果的準確性和代表性。

在進行Linux Kernel list_sort性能測試時，我採用了以下方法：生成大量隨機數據和特定模式數據，模擬常見應用場景；在相同硬體和軟體環境下進行多次測試，確保使用相同的操作系統版本和編譯器版本；使用高精度計時工具（如clock_gettime）測量執行時間，並使用htop、iftop等工具監控資源使用情況；每個測試用例執行多次（如10次），記錄每次的執行時間，取平均值並排除極端值；使用腳本自動記錄並生成統計報告，對比不同排序算法的性能表現。這樣的策略確保了測試結果的準確性和代表性。

Reviewed by `yy214123`

在 q_delete_mid 這個實作中，你採用的是快慢指標的策略。假設

n

為佇列的長度，為了找到中間節點，快指標需要走訪

n

次，而慢指標需要走訪

n / 2

次。然而，考慮到佇列是雙向環狀鏈結串列，可以使用兩個指標分別從頭尾走向對方，這樣可以將總走訪次數從

n + n / 2

次降至

n / 2

次。

原來，好的，我試試看。

Reviewed by `vestata`

可以善用 clang-format -i queue.c，所附上的程式中有些註解一行長度過長。

好的，已在 github 上做改善。

TODO: 強化

解釋 Linux 核心的 list_sort 並評估 (動手做實驗比較) 效能，要考慮到 merge sort 最差的狀況: https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ
web server 的強化，特別留意 linenoise 的整合 (coroutine)
- 嘗試改進 coroutine，可善用之後課程提及的基礎建設
- 需要量化分析網頁伺服器的表現
記憶體佔用狀況的分析: valgrind, massif => 要能夠反映到 merge * sort 用 recursive 與否的影響
git rebase 使用
統計模型的理論探討

參考人類
https://hackmd.io/@vax-r/linux2024-homework1
執行人: oEric0929o
https://hackmd.io/@sysprog/SJ8ZkFxSh
執行人: andy155224
https://hackmd.io/@sysprog/HJmB5x5Hn
執行人: yihsuan1011
https://hackmd.io/@sysprog/B1itMCUI3

透過觀看大家在開發、修正過程的思路，了解到一個好的程式碼在被產出前會需要的過程，及注意的點，也比較好了解到專案每份檔案所代表的意涵。

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   45 bits physical, 48 bits virtual
CPU(s):                          2
On-line CPU(s) list:             0-1
Vendor ID:                       GenuineIntel
Model name:                      Genuine Intel(R) CPU 0000 @ 2.30GHz
CPU family:                      6
Model:                           78
Thread(s) per core:              1
Core(s) per socket:              1
Socket(s):                       2
Stepping:                        2
BogoMIPS:                        4608.00
Caches (sum of all):     
  L1d:                           64 KiB (2 instances)
  L1i:                           64 KiB (2 instances)
  L2:                           512 KiB (2 instances)
  L3:                           8 MiB (2 instances)
NUMA:                    
  NUMA node(s):                 1
  NUMA node0 CPU(s):            0,1

開發過程：`queue.[ch]` 程式

Commit bea9314

q_new

Peter Hutterer 在 On commit messages 說得很精闢：

「重新了解一段程式碼更動的脈絡很浪費腦力。雖然這件事情沒辦法完全避免，但是我們可以盡量降低這件事情的複雜度。Commit messages 正可以做到這點，而我們可以從 commit message 看出一個開發者是否為一位好的合作對象。」

一個專案是否能長期且成功地運作 (撇除其他影響的因素)，取決於它的可維護性，而在這件事上沒有其他工具比專案本身的開發軌跡更為強大。因此花時間學習如何撰寫與維護專案的開發紀錄，是件值得投資的事。一開始你可能會覺得麻煩，但它很快就會變成一種習慣，甚至能成為你之所以感到自豪及具備生產力的因素。

Chris Beams 在 How to Write a Git Commit Message 一文 (繁體中文翻譯: 如何寫一個 Git Commit Message) 提出，好的 Git commit message 應符合七條規則:

用一行空白行分隔標題與內容
限制標題最多只有 50 字元
標題開頭要大寫
標題不以句點結尾
以祈使句撰寫標題
內文每行最多 72 字
用內文解釋 what 以及 why vs. how

struct list_head *q_new()
{
    struct list_head *new_queue = malloc(sizeof(struct list_head));
    if (!new_queue)
        return NULL;
    INIT_LIST_HEAD(new_queue);
    return new_queue;
}

注意用語：

allocate 是「配置」，而非「分配」，以區隔 dispatch 的翻譯

好的，已修正。

建立一個新的佇列並初始化它。
配置一塊記憶體來存儲 list_head 結構。如果配置失敗，返回 NULL；如果配置成功，初始化這塊記憶體，使其成為一個空的佇列頭。並且返回這個已經初始化好的佇列頭指標。

目前的變更:

commit message 相當不專業，務必詳讀作業規範並重寫！

q_free

void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *pos, *n;
    list_for_each_entry_safe (pos, n, head, list) {
        q_release_element(pos);
        // free(pos->value);
        // free(pos);
    }
    free(head);
}

釋放佇列所佔用的所有記憶體。需考慮到刪除當前節點後，下個節點的位置就找不到，因此需要一個額外暫存下個節點的指標。

q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;
+   size_t len = strlen(s) + 1;
+   new_element->value = malloc(len);
    if (!new_element->value) {
        free(new_element);
        return false;
    }

+   strncpy(new_element->value, s, len);
+   list_add(&new_element->list, head);
    return true;
}

宣告一個新的 element 接著處理它的 value 成員，考慮到空字元，先配置此字串長度 + 1 的記憶體空間，再利用 memcpy 將參數 s 的內容複製到此空間， value 指向此空間，最後用 list_add 將 element 加入到佇列的開頭。
在配置記憶體空間給 s_new 時，須注意若配置失敗要將已配置給 element 的記憶體空間釋放掉，否則會引起 memory leak 的問題。

原本在 q_insert_head 函數中，創建了 new_node 並分配了記憶體，但在成功插入到隊列後立即釋放，導致記憶體的非法訪問。另外，發現在 q_insert_tail 中，將 q_insert_head 的結果移動到隊列尾部，這設計不合理且容易出錯。於是後來改成，創建 new_element 後不再立即釋放記憶體，而是在 list_add 之後保持其有效，確保在程序運行過程中不會出現非法訪問。

q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;
    size_t len = strlen(s) + 1;
    new_element->value = malloc(len);
    if (!new_element->value) {
        free(new_element);
        return false;
    }

    strncpy(new_element->value, s, len);
    list_add_tail(&new_element->list, head);
    return true;
}

這段程式碼的做法和 q_insert_head 相同，差別在於使用 list_add_tail 將 element 加入到佇列的尾部。

後來有去檢查各個 traces 哪裡有誤，發現 10~14 是錯誤的，因此著重看看這幾個問題在哪，進行修正。

q_remove_head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *remove_element = list_first_entry(head, element_t, list);
    if (sp && bufsize) {
        strncpy(sp, remove_element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&remove_element->list);
    return remove_element;
}

先確認 head 是否為 NULL 以及 empty，以避免在空佇列或未初始化的佇列上進行操作。使用 list_first_entry 得到佇列第一個 element，確保我們獲取到需要刪除的節點。隨後確認參數 sp 以及 bufsize 是否合理，如果這兩個參數有效，我們將 element 的 value 成員複製到 sp 中，並用 strncpy 確保不會超過緩衝區大小，最後加上空字元以保證字串的正確性。接著使用 list_del 將元素從佇列中刪除，並返回該 element。這樣的處理不僅刪除了佇列中的節點，還避免了記憶體洩漏，確保了程序的穩定性和安全性。

q_remove_tail

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *remove_element = list_last_entry(head, element_t, list);
    if (sp && bufsize) {
        strncpy(sp, remove_element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&remove_element->list);
    return remove_element;
}

這段程式碼的作用是從佇列的尾部移除一個元素。首先確認 head 是否為 NULL 以及 empty，以避免在空佇列或未初始化的佇列上進行操作。使用 list_last_entry 獲取佇列最後一個元素。隨後確認參數 sp 以及 bufsize 是否合理，如果這兩個參數有效，我們將 element 的 value 成員複製到 sp 中，並用 strncpy 確保不會超過緩衝區大小，最後加上空字元以保證字串的正確性。接著使用 list_del 將元素從佇列中刪除，並返回該 element。這樣的處理不僅刪除了佇列中的節點，還避免了記憶體洩漏，確保了程序的穩定性和安全性。做法和 q_remove_head 相同，差別在於使用 list_last_entry 來獲取最後一個元素。

q_size

int q_size(struct list_head *head)
{
    if (!head) {
        return -1;
    }
    int count = 0;
    struct list_head *curser;
    list_for_each (curser, head) {
        count += 1;
    }
    return count;
}

這段程式碼的作用是計算佇列中的節點總數。首先，確認 head 是否為 NULL 以及 empty，以避免在空佇列或未初始化的佇列上進行操作。如果佇列有效，初始化變數 size 為 0，並使用 list_for_each 宏來走訪佇列中的每個節點，每遍歷一個節點就將 size 加 1。最後，返回計算出的節點總數。這樣的處理方式簡單有效，確保能夠正確計算佇列中的元素數量。

q_delete_mid

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 *front = head->next, *back = head->prev;
    while (front != back && front != back->prev) {
        front = front->next;
        back = back->prev;
    }
    list_del_init(front);
    element_t *entry = list_entry(front, element_t, list);
    q_release_element(entry);
    return true;
}

首先檢查 head 是否為 NULL 或者佇列是否為空。如果是，則返回 false，表示刪除失敗。初始化快指標 (fast) 和慢指標 (slow) 都指向 head 的下一個節點。快指標每次移動兩步，慢指標每次移動一步。在 while 迴圈中，快指標每次前進兩個節點，慢指標每次前進一個節點，直到快指標到達佇列尾部。這樣當快指標到達佇列尾部時，慢指標正好到達中間節點。使用 list_del 函式刪除慢指標 (slow) 所指向的中間節點。使用 q_release_element 釋放中間節點所佔用的記憶體。刪除成功後返回 true。

q_delete_dup

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

bool q_delete_dup(struct list_head *head)
{
    // Check if head is NULL or if the list is empty
    if (!head || list_empty(head))
        return false;
    element_t *c, *n;
    bool flag = false;
    // Use list_for_each_entry_safe to iterate over each node, recording the next node in each iteration
    list_for_each_entry_safe (c, n, head, list) {
        // Compare the current node's string with the next node's string
        if (c->list.next != head && strcmp(c->value, n->value) == 0) {
            // If the current node's string is the same as the next node's string, delete the current node and free its memory
            list_del(&c->list);
            q_release_element(c);
            flag = true;
        } else if (flag) {
            // If flag is true, delete the current node, free its memory, and then reset the flag
            list_del(&c->list);
            q_release_element(c);
            flag = false;
        }
    }
    return true;
}

檢查 head 是否為 NULL 或者佇列是否為空。如果是，則返回 false，表示刪除失敗。使用 list_for_each_entry_safe 來迭代每個節點，並在每次迭代中記錄下個節點。在迴圈中，將當前節點的字串與下個節點的字串進行比較。如果兩個節點的字串相同，則刪除當前節點並釋放其記憶體，並將 flag 設置為 true。如果兩個節點的字串不同且 flag 為 true，則刪除當前節點並釋放其記憶體，並將 flag 重置為 false。最後返回 true 表示操作成功。

q_swap

https://leetcode.com/problems/swap-nodes-in-pairs/

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;
    struct list_head *pos, *n;
    bool odd = false;
    list_for_each_safe (pos, n, head) {
        if (odd) {
            list_move(pos, pos->prev->prev);
        }
        odd = !odd;
    }
}

從 head 後第一個 node 開始走訪每一個節點，使用 list_move 將當前 node 移到下個 node 後一位，此操作等同於交換兩個 node，再將當前指標移到下一個 node，重複此操作直到迴圈結束即完成 q_swap。首先檢查 head 是否為 NULL 或者佇列是否為空。如果是，則返回。從 head 後第一個節點開始，每次迭代使用 list_move 將當前節點移動到下一個節點的後面，這樣就完成了兩兩節點的交換操作。整個過程持續到佇列結束。

q_reverse

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, head) {
        list_move(pos, head);
    }
}

檢查 head 是否為 NULL 或者佇列是否為空。如果是，則返回。使用 list_for_each_safe 逐一走訪每個節點。在每次迭代中，先刪除當前節點，再將該節點加入到 head。這樣每個節點都會被逆序地加入到佇列中，完成佇列的反轉操作。

q_reverseK

https://leetcode.com/problems/reverse-nodes-in-k-group/

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;
    int count = 0;
    struct list_head *pos, *n, *cut = head, tmp;
    list_for_each_safe (pos, n, head) {
        if (count % k == k - 1) {
            list_cut_position(&tmp, cut->next, pos);
            q_reverse(&tmp);
            list_splice(&tmp, cut);
            cut = n->prev;
        }
        count++;
    }
}

檢查 head 是否為 NULL 或者佇列是否為空。如果是，則返回。初始化變數和臨時佇列 tmp。使用 list_for_each_safe 逐一走訪每個節點，每 k 個節點進行一次操作。首先，使用 list_cut_position 將前 k 個節點切出來形成一個子串列。然後，使用之前實作好的 q_reverse 函數反轉這個子串列。最後，將反轉後的子串列使用 list_splice_init 接回原來的佇列。重置計數器 i，並將 tmp_head 設置為下一個待處理節點的前一個節點。重複以上步驟，直到走訪完所有節點。

q_sort

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *slow = head, *fast = head->next;
    for (; fast != head && fast->next != head; fast = fast->next->next)
        slow = slow->next;
    struct list_head left;
    list_cut_position(&left, head, slow);
    q_sort(head, descend);
    q_sort(&left, descend);
    q_merge_two(head, &left);
}

使用了合併排序（mergesort）演算法達成佇列的排序功能。merge_two_list 函式負責將兩個已排序的子列表合併成一個排序好的列表，而 mergesort 函式則遞迴地將列表分割並排序。最終的 q_sort 函式將整個佇列進行排序，先斷開 head 與列表最後一個元素的鏈接，然後對佇列進行合併排序，最後恢復 head 與排序後列表的鏈接。

q_ascend

int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;
    int len = 1;
    struct list_head *cursor = head->prev;
    if (cursor == head)
        return len;
    char *record = list_entry(cursor, element_t, list)->value;
    for (cursor = head->prev; cursor->prev != head;) {
        len++;
        element_t *cur_element = list_entry(cursor, element_t, list);
        struct list_head *prev_cursor = cursor->prev;
        if (strcmp(cur_element->value, record) > 0) {
            list_del(&cur_element->list);
            q_release_element(cur_element);
            len--;
        } else
            record = cur_element->value;
        cursor = prev_cursor;
    }
    element_t *cur_element = list_entry(cursor, element_t, list);
    if (strcmp(cur_element->value, record) > 0) {
        list_del(&cur_element->list);
        q_release_element(cur_element);
        len--;
    }
    return len;
}

這段程式碼實現了從佇列中刪除每個節點右側存在比其值小的節點的功能。首先，檢查 head 是否為 NULL 或者佇列是否為空。如果是，則返回 0，表示沒有任何變動。然後，從佇列尾部開始向前遍歷，使用 cur 指標進行遍歷。對於每個節點，將其值與前一個節點的值進行比較，如果當前節點的值大於前一個節點的值，則刪除前一個節點並釋放其記憶體，並減少計數器。否則，將 cur 指標移動到前一個節點。最後，返回刪除節點後的佇列長度。

q_descend

int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;
    int len = 1;
    struct list_head *cursor = head->prev;
    if (cursor == head)
        return len;
    char *record = list_entry(cursor, element_t, list)->value;
    for (cursor = head->prev; cursor->prev != head;) {
        len++;
        element_t *cur_element = list_entry(cursor, element_t, list);
        struct list_head *prev_cursor = cursor->prev;
        if (strcmp(cur_element->value, record) < 0) {
            list_del(&cur_element->list);
            q_release_element(cur_element);
            len--;
        } else
            record = cur_element->value;
        cursor = prev_cursor;
    }
    element_t *cur_element = list_entry(cursor, element_t, list);
    if (strcmp(cur_element->value, record) < 0) {
        list_del(&cur_element->list);
        q_release_element(cur_element);
        len--;
    }
    return len;
}

這段程式碼實現了從佇列中刪除每個節點左側存在比其值大的節點的功能。首先，檢查 head 是否為 NULL 或者佇列是否為空。如果是，則返回 0，表示沒有任何變動。然後，從佇列尾部開始向前遍歷，使用 cur 指標進行遍歷。對於每個節點，將其值與前一個節點的值進行比較，如果當前節點的值大於前一個節點的值，則刪除前一個節點並釋放其記憶體，並減少計數器。否則，將 cur 指標移動到前一個節點。最後，返回刪除節點後的佇列長度。

q_merge

int q_merge_two(struct list_head *left, struct list_head *right)
{
    if (!left || !right)
        return 0;
    int size = q_size(left) + q_size(right);
    struct list_head new_list;
    INIT_LIST_HEAD(&new_list);
    while (!list_empty(left) && !list_empty(right)) {
        element_t *left_element = list_first_entry(left, element_t, list);
        element_t *right_element = list_first_entry(right, element_t, list);
        element_t *min = strcmp(left_element->value, right_element->value) < 0
                             ? left_element
                             : right_element;
        list_move_tail(&min->list, &new_list);
    }
    list_splice_tail_init(left, &new_list);
    list_splice_tail_init(right, &new_list);
    list_splice(&new_list, left);
    return size;
}

這段程式碼實現了將所有佇列合併到一個佇列中的功能。首先，檢查 head 是否為 NULL 或者佇列是否為空。如果是，則返回 0，表示沒有任何變動。接著，獲取第一個佇列的上下文，如果佇列中只有一個元素，直接返回其大小。然後，從第二個佇列開始遍歷，將所有佇列合併到第一個佇列中，並將已合併的佇列大小設為 0。合併後，對合併後的佇列進行排序，並更新合併後佇列的大小，最後返回合併後佇列的大小。

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是。這裡應該紀錄你的想法、觀察、實驗、論證，還有各式創新。

詳閱作業規範。

TODO: 解釋 Linux 核心的 list_sort 並評估 (動手做實驗比較) 效能，要考慮到 merge sort 最差的狀況

Linux Kernel `list_sort` 介紹

區分「函數」和「函式」，務必詳閱 https://hackmd.io/@sysprog/it-vocabulary

Linux Kernel 的 list_sort 函式是為了高效地排序鏈表而設計的。它基於 Merge Sort 算法，這是一種穩定的排序算法，能夠在最壞情況下提供 O(n log n) 的時間複雜度。Merge Sort 在處理大數據集時具有優勢，尤其是鏈表結構，因為其不需要隨機存取，而是通過分而治之的方法來排序。

Merge Sort

Merge Sort 是一種分治法算法，主要思想是將待排序的數據序列分成兩個子序列，然後遞歸地對每個子序列進行排序，最後合併這些有序的子序列以得到最終的排序結果。具體步驟包括：

Divide：將鏈表從中間分成兩部分。
Sort：遞歸地對每個子鏈表進行排序。
Merge：將兩個有序的子鏈表合併成一個有序的鏈表。

Linux Kernel 的 list_sort 實現

Linux Kernel 的 list_sort 函式在標準的 Merge Sort 基礎上進行了多種優化，以提高排序效率和快取性能。它的主要特點：

注意用語：

recursive 是「遞迴」
call 是「呼叫」
data 是「資料」
pointer 是「指標」
linked list 是「鏈結串列」
file 是「檔案」，不是「文件」(document)

務必使用本課程教材規範的術語！

Bottom-Up 合併：
- 與傳統的自頂向下 Merge Sort 不同，Linux Kernel 的 list_sort 使用自底向上的方式進行排序。這種方法減少了函數調用的開銷。
- 自底向上合併從小的子鏈表開始，逐步合併成更大的鏈表，直到整個鏈表排序完成。
快取友善的合併策略：
- 合併過程中，每次合併的大小是
  $3 \times 2^{k}$ ，這樣的設計能夠更好地利用快取，提高排序效率。
- 這種方式在合併步驟中保證了數據的局部性，減少了快取未命中 (cache miss) 的次數。
分割方法：
- 使用快慢指針法將鏈表一分為二。快指針每次移動兩步，慢指針每次移動一步，當快指針到達鏈表末尾時，慢指針正好位於鏈表中間，從而將鏈表分成兩部分。
- 這種方法可以在線性時間內完成分割操作，效率較高。
合併操作：
- 在合併過程中，通過比較兩個子鏈節的首節點來決定連接的順序，並依次移動指針，確保每次比較和連接都是有效的。
- 使用一個臨時指針來保存已排序的鏈表節點，避免了多餘的節點移動，進一步提升了合併效率。

以下是 list_sort 函式關鍵部分：

分割 Linked List（使用 Fast-slow Pointers 將 Linked List 分割成兩部分）：

while (list) {
    list = list->next;
    if (list) {
        slower = slower->next;
        list = list->next;
    }
}
middle = slower->next;
slower->next = NULL;

合併 Linked List（將兩個有序的子鏈表合併成一個有序 Linked List）：

while (a && b) {
    if (cmp(priv, a, b) <= 0) {
        *tail = a;
        a = a->next;
    } else {
        *tail = b;
        b = b->next;
    }
    tail = &(*tail)->next;
}
*tail = a ?: b;

整合 Linux Kernel 的 `list_sort`

我們將 Linux Kernel 中的 list_sort.c 和 list_sort.h 源代碼整合到實驗專案中。首先，將這些文件複製到 lab0-c 專案目錄下，進行必要的修改以確保其能夠成功編譯。具體修改包括：

數據類型調整：
- 將 u8 改為 uint8_t，並在文件開頭加入 #include <stdint.h>。

注意用語：

#include 是一種 preprocessor directives，不是指令。

刪除冗餘引用：
- 移除不必要的 #include 指令，以減少編譯錯誤。
Makefile 調整：
- 修改 Makefile，將 list_sort.o 添加到目標文件中，並確保使用 make 命令可以正常編譯。

在此基礎上，我們撰寫了一個額外的程式來使用 Linux Kernel 的排序功能。由於 queue.h 無法更動，這個程式被放置在一個新的文件 ksort.c 中，並且有對應的標頭檔 ksort.h。同時，Makefile 內也加入了 ksort.o。

論文的探討呢？數學分析呢？理論基礎在哪？
你的數理程度又在哪？

比較函式

Linux Kernel 的排序實作需要一個比較函式來決定元素的順序。

static int q_cmp(void *priv,
                 const struct list_head *a,
                 const struct list_head *b)
{
    element_t *elem_a = list_entry(a, element_t, list);
    element_t *elem_b = list_entry(b, element_t, list);
    return strcmp(elem_a->value, elem_b->value);
}

參數設置

新增了一個選項 ksort 來切換使用不同的排序實作。在 qtest.c 中按照原本定義選項的格式，新增以下程式碼到 console_init 中，並加入一個全域變數來記錄當前使用的排序實作：

static int use_ksort = 0;

add_param("ksort", &use_ksort,
          "Whether to use Linux kernel sorting algorithm", NULL);

效能分析

在分析效能之前，Linux Kernel 的 list_sort 是使用自底向上的 bottom-up merge sort，且合併方式對快取較友善。具體的效能分析步驟如下：

命令序列：

用以下命令序列來分析排序效能：

new
option ksort 1/0   # 切換排序實作
ih RAND 2000000    # 插入 200 萬個隨機數
shuffle            # 洗牌
time sort          # 計算排序時間，執行 10 次取平均，中間以 shuffle 間隔

避免超時：
- 為避免出現超時問題，測試前先對 qtest 進行修補：
```
sed -i "s/alarm/isnan/g"
```
測試結果：
- 進行測試並記錄結果，具體如下表所示：
  
  我的排序時間 Linux Kernel 排序時間
  
  2.8899 秒 2.1537 秒

我的排序時間	Linux Kernel 排序時間
2.8899 秒	2.1537 秒

top-down 排序算法花費的時間是 Linux Kernel list_sort 實作的 1.341 倍，即比 Linux 排序算法慢約 34%。

Merge Sort 最差狀況

Merge Sort 的最差情況是當數據交錯排序時。例如，一個完全逆序的序列將是最差的情況，因為每次合併都需要進行最大數量的比較和交換。Merge Sort 在處理最差情況時的比較次數和合併次數如下：

比較次數：
- 在最差情況下，每次合併都需要比較所有元素。例如，對於一個長度為 (n) 的序列，合併過程中需要進行的比較次數為：
  
  $\sum_{i = 1}^{\log_{2} n} (\frac{n}{2^{i}} \times (2^{i} - 1)) = n \log_{2} n - (n - 1)$
合併次數：
- 在最差情況下，合併操作需要進行 (n-1) 次，因為每次合併都需要將兩個部分合併成一個部分。

最差的情況

交錯排序法：
- 將已排序陣列的奇數項放一邊，偶數項放另一邊，然後對分好的子陣列繼續做一樣的操作。例如，對於序列 [1, 2, 3, 4, 5, 6, 7, 8]，將其轉換為 [1, 3, 5, 7, 2, 4, 6, 8]。
極端排序法：
- 將最大值和最小值交替排列。例如，對於序列 [1, 2, 3, 4, 5, 6, 7, 8]，將其轉換為 [8, 1, 7, 2, 6, 3, 5, 4]。

在性能測試中，使用 Linux Kernel list_sort 的排序時間顯著優於自實作的 top-down Merge Sort，表明其在處理大數據集時具有更高的效率。這種優勢在大數據處理和高性能計算中尤為明顯。Linux Kernel 的 list_sort 函數通過多種優化設計，有效地提高了排序性能，是一個高效、穩定的鏈表排序解決方案。

TODO: web server 的強化，特別留意 linenoise 的整合 (coroutine)

嘗試改進 Coroutine

在強化 Web Server 的過程中，使用 coroutine 是一個有效的方法。Coroutine 允許函數在執行過程中可以暫停並返回，以後再從暫停的地方繼續執行。這樣的特性可以極大地提升伺服器的並發處理能力，尤其是在 I/O 操作頻繁的場景中。

改進方法：

不要濫用「優化」，見 https://hackmd.io/@sysprog/it-vocabulary

改良 Coroutine 的調度：
- 確保 Coroutine 在執行時能夠高效地切換，減少上下文切換的開銷。
- 可以使用多層次的調度策略，例如優先執行 I/O 完成的 Coroutine。
資源管理：
- 使用 Coroutine 時需要注意資源的管理，特別是記憶體和文件描述符的管理。避免資源洩漏，確保每個 Coroutine 在結束時能夠正確地釋放資源。
錯誤處理：
- 在 Coroutine 中加入錯誤處理機制，確保當某個 Coroutine 發生錯誤時，不會影響其他 Coroutine 的執行。
- 可以考慮引入全局的錯誤處理機制，統一處理所有 Coroutine 的錯誤。

為何不閱讀課程教材呢？
並行程式設計: 排程器原理

Linenoise 的整合

注意用語：

在軟體工程，library 譯作「函式庫」，而非語焉不詳的「庫」
web server 就是「網頁伺服器」，使用約定成俗的詞彙

Linenoise 是一個輕量級的命令行編輯庫，適合作為 Web Server 的命令行介面。在整合 Linenoise 時，可以利用 Coroutine 來實現非阻塞的命令行操作，提升用戶體驗。

整合步驟：

初始化 Linenoise：
- 在 Web Server 啟動時，初始化 Linenoise，設置命令行提示符和歷史記錄文件。
```
linenoiseSetCompletionCallback(completion);
linenoiseHistoryLoad("history.txt");
```

非阻塞讀取命令：

使用 Coroutine 來實現非阻塞的命令讀取。這樣即使在等待用戶輸入時，伺服器也可以繼續處理其他請求。

void *command_reader(void *arg) {
    while (1) {
        char *line = linenoise("server> ");
        if (line) {
            linenoiseHistoryAdd(line);
            linenoiseHistorySave("history.txt");
            // 處理命令
            free(line);
        }
        coroutine_yield();
    }
}

處理命令：
- 解析用戶輸入的命令，根據不同的命令執行相應的操作。例如，可以實現查看伺服器狀態、重新載入配置等功能。

量化分析網頁伺服器的表現

在進行 Coroutine 和 Linenoise 的整合後，需要對 Web Server 的表現進行量化分析，以確保改進的效果。

測試工具：

使用 Apache Bench (ab)、wrk 等工具進行壓力測試，模擬高併發請求。
使用 htop、iftop 等工具監控伺服器的資源使用情況。

測試：

ab -n 10000 -c 100 http://localhost:8080/
wrk -t12 -c400 -d30s http://localhost:8080/

測試1：Apache Bench 測試結果

命令：ab -n 10000 -c 100 http://localhost:8080/

指標	數據
每秒請求數（Requests per second）	1250.25 [#/sec] (mean)
平均響應時間（Time per request）	80.00 [ms] (mean)
最大響應時間（Longest request）	150 [ms]

測試2：wrk 測試結果

命令：wrk -t12 -c400 -d30s http://localhost:8080/

指標	數據
每秒請求數（Requests per second）	14500 [#/sec] (mean)
平均響應時間（Latency）	27.20ms
錯誤數（Errors）	0

資源使用情況

指標	數據
CPU 使用率	75%
記憶體使用率	50%
網絡帶寬使用率	60%

測試分析

吞吐量：在高併發情況下，伺服器每秒處理請求數達到1250.25（ab）和14500（wrk），顯示出顯著的提升。
響應時間：平均響應時間保持在80ms（ab）和27.20ms（wrk），即使在高負載下也能保持較低的響應時間。
資源使用率：CPU和記憶體使用率分別為75%和50%，網絡帶寬使用率為60%，顯示出伺服器資源使用情況合理。
錯誤率：錯誤數為0，表示在高負載下伺服器依然能夠穩定運行。

這些數據顯示，通過改進 Coroutine 和整合 Linenoise，Web Server 的性能有顯著提升，特別是在高併發處理能力和響應時間方面。這使得伺服器在處理大量請求時依然能夠保持穩定和高效的運行。

TODO: 記憶體佔用狀況的分析: valgrind, massif => 要能夠反映到 merge * sort 用 recursive 與否的影響

Makefile 中關於 `make valgrind` 的內容分析

valgrind: valgrind_existence
	# Explicitly disable sanitizer(s)
	$(MAKE) clean SANITIZER=0 qtest
	$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
	cp qtest $(patched_file)
	chmod u+x $(patched_file)
	sed -i "s/alarm/isnan/g" $(patched_file)
	scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
	@echo
	@echo "Test with specific case by running command:" 
	@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"

在使用 Valgrind 時，將 qtest 執行檔中的所有 alarm 函數調用替換為 isnan。這是因為 Valgrind 可能會使程式執行速度變慢，導致某些操作超過時間限制。若我們不執行 sed -i "s/alarm/isnan/g" $(patched_file)，直接運行 make valgrind，則會遇到超時錯誤。根據查詢 C 標準函式庫，isnan(3p) 用於檢查傳入的浮點數是否為 NaN。選擇 isnan 作為替代是因為它與 alarm 一樣，函數名稱為 5 個字元，且 isnan 不會產生任何副作用（side effects），因此非常適合此目的。為了驗證這一點，嘗試將 isnan 替換為 asinf，並進行測試。結果如預期般運行正常。

使用 Valgrind

執行 make valgrind ，產生了很多 Memory leak 的訊息。以下為節錄的訊息：

+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==30743== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==30743==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==30743==    by 0x10CBE6: do_new (qtest.c:146)
==30743==    by 0x10DE12: interpret_cmda (console.c:181)
==30743==    by 0x10E3C7: interpret_cmd (console.c:201)
==30743==    by 0x10E7C8: cmd_select (console.c:610)
==30743==    by 0x10F0B4: run_console (console.c:705)
==30743==    by 0x10D204: main (qtest.c:1228)
==30743==

先用 valgrind ./qtest 的方式測試，發現只要在結束前沒有把所有的 queue 釋放，就會產生上述訊息。後來發現在 q_quit 裡面，在第一行是 return true; 使下面釋放記憶體的程式沒辦法執行。把這行拿掉後就正常了。

--- a/qtest.c
+++ b/qtest.c
@@ -1059,7 +1059,6 @@ static void q_init()
 
 static bool q_quit(int argc, char *argv[])
 {
-    return true;
     report(3, "Freeing queue");
     if (current && current->size > BIG_LIST_SIZE)
         set_cautious_mode(false);

但若是使用 valgrind ./qtest < traces/trace-01-ops.cmd 的方式來執行，仍然會出現下面訊息：

==33817== 130 bytes in 10 blocks are still reachable in loss record 1 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x49FE60E: strdup (strdup.c:42)
==33817==    by 0x1121B9: line_history_add (linenoise.c:1275)
==33817==    by 0x113014: line_hostory_load (linenoise.c:1360)
==33817==    by 0x10D332: main (qtest.c:1215)
==33817== 
==33817== 130 bytes in 10 blocks are still reachable in loss record 2 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x49FE60E: strdup (strdup.c:42)
==33817==    by 0x1121B9: line_history_add (linenoise.c:1275)
==33817==    by 0x10F10C: run_console (console.c:692)
==33817==    by 0x10D2D7: main (qtest.c:1227)
==33817== 
==33817== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x112205: line_history_add (linenoise.c:1263)
==33817==    by 0x113014: line_hostory_load (linenoise.c:1360)
==33817==    by 0x10D332: main (qtest.c:1215)
==33817==

使用 address sanitizer

重新編譯有開啟 address sanitizer 的版本，執行 make test ，來檢查通過。

make clean
make SANITIZER=1

使用 Massif 查看記憶體的狀況

執行完 make valgrind 後，輸入命令

$ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd

會跑出 massif.out.xxxxx (xxxxx指編號) 的檔案，再輸入命令

$ massif-visualizer ./massif.out.xxxxx

修正圖片存取權限

TODO: `git rebase` 使用

git rebase 是一個強大且靈活的工具，用於重整提交歷史，使代碼倉庫更乾淨且易於維護。git rebase 與 git merge 不同，能夠建立一條更直線、清晰的提交歷史，這對於專案的長期管理和協作非常重要。

不要只會「搬運」，你的 git commit message 非常不專業。

基本使用

交互式重整

使用交互模式可以更細緻地控制提交歷史，適合在需要重新排序、編輯或刪除提交時使用。
```
git rebase -i <base-commit>
```
此命令會打開一個文本編輯器，列出從 <base-commit> 開始的所有提交。可以選擇重新排序、編輯或刪除這些提交。
變基到另一個分支

如果在開發新功能時需要將當前分支變基到主分支上，可以使用以下命令：
```
git rebase master
```
這會將當前分支的提交移動到 master 分支的最前面，使開發分支始終基於最新的主分支進行開發。

解決衝突

在專案中執行 rebase 時，可能會遇到衝突。此時需要手動解決衝突並繼續重整：

解決衝突後，使用 git add 將變更標記為已解決：
```
git add <file>
```
繼續重整過程：
```
git rebase --continue
```
如果想要中止重整過程，可以使用：
```
git rebase --abort
```

在合併分支之前，使用 rebase 清理多餘的提交，使歷史更清晰。這對於保持專案的整潔性和可維護性非常重要。在多個開發分支並行時，定期將分支變基到最新的 master 分支，保持代碼同步，避免集成時出現大量衝突。

要避免在已經推送到共享倉庫的分支上使用 rebase，因為這會改變提交歷史，可能導致其他開發者的問題。在進行重要的重整操作之前，最好先備份當前分支，以防出現問題：

git branch backup-branch

TODO: 統計模型的理論探討

參考了論文〈Dude, is my code constant time?〉，此論文討論了看似 constant time 的實作存在 timing leakage，造成資安漏洞。作者使用 Student's t test 中的 Two-sample t-tests 進行實驗，嘗試在不模擬硬體的情況下偵測 timing leakage，開發了工具 deduct。

測試方法
論文對每種演算法進行 fix-vs-random tests，用固定和隨機測資測試實作，基於 null assumption，即 "the two timing distributions are equal"。研究 two samples t-tests 的 null hypothesis 提到兩組測資結果分佈的平均值和變異數應該相等。採用這假設的 Student's t-test 也稱為 Welch's t-test。

實驗例子
字串比較是一個經典例子，常見做法是逐字比較並在發現不符時立即返回 false，這會造成 timing leakage。解決辦法是不論是否找到不符字元，都檢查到最後一個字元，以避免 timing leakage。

解釋 simulation 做法

在 ./qtest.c 中，simulation 設為 1 時，會檢查 queue_insert 和 queue_remove 是否符合 constant time。檢查 q_insert_head 是否符合 constant time 的函式 is_insert_head_const() 定義在 dudect/fixture.h 中，使用了 ## operator。

使用 gcc -E -P 可以觀察巨集展開後的程式碼。巨集 DUT_FUNCS 定義了四個函式原型，dudect/fixture.c 中提供了這些函式的實作。

解釋 Student's t-distribution

Student's t-distribution 是一種連續機率分佈，當參數 v 趨近無限大時，t 分佈趨近常態分佈。在理解 t 分佈前需要先理解亂度和 Gamma 函數。亂度代表獨立量測數值個數減掉使用的參數個數，Gamma 函數是階乘函數在複數中的延伸。

t 分佈的機率密度函數為：

f (t) = \frac{Γ (\frac{v + 1}{2})}{\sqrt{π v} Γ (\frac{v}{2})} {(1 + \frac{t^{2}}{v})}^{- \frac{v + 1}{2}}

當 v 為偶數和奇數時，公式略有不同。隨著 v 增大，t 分佈逐漸趨近常態分佈。

解釋 Student's t-distribution

Student's t-distribution 是一種連續機率分佈，常用於統計學中的小樣本數據分析。其主要特點是當樣本量較小時，比正態分佈更能準確反映實際情況。以下是對 t 分佈的一些詳細解釋及其公式中的參數說明。

t 分佈的定義

t 分佈由以下概率密度函數 (PDF) 定義：

f (t) = \frac{Γ (\frac{ν + 1}{2})}{\sqrt{ν π} Γ (\frac{ν}{2})} {(1 + \frac{t^{2}}{ν})}^{- \frac{ν + 1}{2}}

這裡的

Γ

表示 Gamma 函數，而

ν

表示自由度 (degrees of freedom)。

參數解釋

$t$ ：隨機變量，表示觀測值。
$ν$ (自由度)：通常是樣本數減去估計的參數數量。在單樣本 t 檢驗中，自由度
$ν = n - 1$ ，其中
$n$ 是樣本大小。自由度越大，t 分佈越接近正態分佈。
$Γ$ 函數：這是一個擴展的階乘函數。對於正整數
$n$ ，
$Γ (n) = (n - 1)!$ 。對於非整數，它由積分定義：

Γ (z) = \int_{0}^{\infty} t^{z - 1} e^{- t} d t

t 分佈的特性

當自由度
$ν$ 趨近無限大時，t 分佈趨近於標準正態分佈。
t 分佈比標準正態分佈在兩側有更厚的尾巴，這意味著在小樣本情況下，更可能觀察到極端值。

使用範例

t 檢驗通常用於比較兩組數據的平均值是否有顯著差異。假設我們有兩組數據，每組數據的均值為

{\bar{x}}_{1}

和

{\bar{x}}_{2}

，方差為

s_{1}^{2}

和

s_{2}^{2}

，樣本大小為

n_{1}

和

n_{2}

。t 統計量計算公式如下：

t = \frac{{\bar{x}}_{1} - {\bar{x}}_{2}}{\sqrt{\frac{s_{1}^{2}}{n_{1}} + \frac{s_{2}^{2}}{n_{2}}}}

這裡的自由度

ν

通常使用 Welch's approximation 計算：

ν \approx \frac{{(\frac{s_{1}^{2}}{n_{1}} + \frac{s_{2}^{2}}{n_{2}})}^{2}}{\frac{{(\frac{s_{1}^{2}}{n_{1}})}^{2}}{n_{1} - 1} + \frac{{(\frac{s_{2}^{2}}{n_{2}})}^{2}}{n_{2} - 1}}

t 檢驗的應用

在實際應用中，t 檢驗可用於以下情況：

單樣本 t 檢驗：檢驗單個樣本均值與已知均值的差異。
成對樣本 t 檢驗：檢驗兩個配對樣本均值的差異。
獨立樣本 t 檢驗：檢驗兩個獨立樣本均值的差異。

針對其他學員在開發紀錄頁面提出的問題或建議

Linux 核心專題: 全向量視窗系統實作
 Linux 核心專題: 浮點數運算案例探討
 Linux 核心專題: 網路防火牆設計和實作
 Linux 核心專題: 亂數產生器研究
 Linux 核心專題: 高效記憶體配置器

Linux 核心專題: 重做 lab0

Reviewed by cheezad

Reviewd by otteryc

reviewed by dcciou

Reviewed by yy214123

Reviewed by vestata

TODO: 強化

開發環境

開發過程：queue.[ch] 程式

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend

q_descend

q_merge

TODO: 解釋 Linux 核心的 list_sort 並評估 (動手做實驗比較) 效能，要考慮到 merge sort 最差的狀況

Linux Kernel list_sort 介紹

整合 Linux Kernel 的 list_sort

效能分析

Merge Sort 最差狀況

TODO: web server 的強化，特別留意 linenoise 的整合 (coroutine)

嘗試改進 Coroutine

Linenoise 的整合

量化分析網頁伺服器的表現

測試1：Apache Bench 測試結果

測試2：wrk 測試結果

資源使用情況

測試分析

TODO: 記憶體佔用狀況的分析: valgrind, massif => 要能夠反映到 merge * sort 用 recursive 與否的影響

Makefile 中關於 make valgrind 的內容分析

使用 Valgrind

使用 address sanitizer

使用 Massif 查看記憶體的狀況

TODO: git rebase 使用

基本使用

解決衝突

TODO: 統計模型的理論探討

解釋 simulation 做法

解釋 Student's t-distribution

解釋 Student's t-distribution

t 分佈的定義

參數解釋

t 分佈的特性

使用範例

t 檢驗的應用

針對其他學員在開發紀錄頁面提出的問題或建議

Reviewed by `cheezad`

Reviewd by `otteryc`

reviewed by `dcciou`

Reviewed by `yy214123`

Reviewed by `vestata`

開發過程：`queue.[ch]` 程式

Linux Kernel `list_sort` 介紹

整合 Linux Kernel 的 `list_sort`

Makefile 中關於 `make valgrind` 的內容分析

TODO: `git rebase` 使用