2025q1 Homework1 (lab0)

contributed by < rota1001 >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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 字元

Reviewed by `salmoniscute`

「函數」跟「函式」混在一起用了，可以參考資訊科技詞彙翻譯修正。

開發環境

$ gcc --version                               
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                GenuineIntel
  Model name:             13th Gen Intel(R) Core(TM) i7-1360P
    CPU family:           6
    Model:                186
    Thread(s) per core:   2
    Core(s) per socket:   12
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   21%
    CPU max MHz:          5000.0000
    CPU min MHz:          400.0000
    BogoMIPS:             5222.40
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc ar
                          t arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 
                          xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_en
                          hanced tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsavec 
                          xgetbv1 xsaves split_lock_detect user_shstk avx_vnni dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_req hfi vnmi umip pku ospke waitpkg gfni 
                          vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_clear serialize arch_lbr ibt flush_l1d arch_capabilities
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    448 KiB (12 instances)
  L1i:                    640 KiB (12 instances)
  L2:                     9 MiB (6 instances)
  L3:                     18 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-15

針對佇列操作的程式碼實作

以下程式碼省略部份以 ... 表示

q_new

Commit 8262840

用 malloc 分配記憶體，並用 list.h 中提供的 INIT_LIST_HEAD 函式初始化 head

q_free

Commit a18fd45

特判 head 是空指標或佇列是空的情況，否則使用 list.h 中提供的 list_for_each_entry_safe 巨集走訪每個節點，其中 safe 會存著下一個元素的指標，讓我們可以安全的移除節點。在這個過程中去釋放每個元素中所使用的記憶體。
這個函式在實作 q_delete_entry 之後有做修改，將重複的程式碼拉出來實作。

q_insert_head

Commit d513e76

如果 head 是空指標就回傳 false，否則用 malloc 分配一塊空間給新的 element_t，並且用 strdup 複製一份 s 賦值給 e->value。接下來使用 list.h 中的 list_add 函式把新元素中的 list 放進佇列裡面。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    
    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }

    list_add(&e->list, head);
    return true;
}

然而，這樣做 static analysis 過不了，有兩個問題。一個是因為 s 所指向的東西沒被修改，所以可以用 const char * 但又不能修改界面，於是使用 inline suppression 來略過這個檢查。另一個是因為 element_t *e 這個元素被分配出來後，cppcheck 認為我們以後無法存取它了，所以沒有將它 free 掉會造成 memleak （證據是如果加上 free(e) 它就可以通過檢查），但是實際上我們可以通過佇列中的節點和 list.h 中的 list_entry 巨集來存取它，所以也使用 inline suppression 將檢查略過。

+ /* cppcheck-suppress constParameterPointer */
bool q_insert_head(struct list_head *head, char *s)
{
    ...
+    /* cppcheck-suppress memleak */
    return true;
}

這裡加了無用的大括號，在 Commit fbf0b69 修正了：


-   if (!head) {
+   if (!head)
        return false;
-   }

q_insert_tail

Commit d513e76

參考 2023 年同學作業，由於 q_insert_tail 與 q_insert_head 功能相似，在這個佇列非空的情況下，在佇列的尾巴插入等價於將 head 的前一個當作 head 並從頭插入。

q_remove_head

Commit fb51a2b

使用 list.h 提供的 list_first_entry 函式來拿到第一個元素，並且使用 stpncpy 將移除元素的字串複製到指定位置。stpncpy 是在讀 strncpy 的文檔過程中找到的，會回傳最後一個字元的後面一個位置。我們可以直接把那個字元設成 \0，就不用像用 strncpy 那樣多寫一行 sp[bufsize - 1] = '\0'。原本我以為如果空字元被成功複製的話，那它回傳的會是空字元的後面一個位置，但實際上會回傳空字元的位置，所以在 Commit afc9944 修正了。最後，使用 list.h 提供的 list_del 函式在把 e->list 從佇列中移除。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    
    element_t *e = list_first_entry(head, element_t, list);
    if (sp && (e->value))
        *(char *) stpncpy(sp, e->value, bufsize - 1) = '\0';

    list_del(&e->list);
    return e;
}

另外，寫 commit message 時，會顯示 Avoid using non-American English words，於是我去 commit-msg.hook 的第 357 行加了 add_warning 1 $MISSPELLED_WORDS，發現輸出 stpncpy，也就是說這個字被擋掉了。

q_remove_tail

Commit fb51a2b

在佇列非空的情況下，移除尾巴等同於把 head 的前一個的前一個當作 head，然後移除頭。

q_size

Commit 08b10b4

如果是空指標或佇列是空的就回傳 0，否則就走訪佇列並紀錄數量。

q_delete_mid

Commit 95502b5

如果是空指標或佇列是空的就回傳 false，否則分成 left 和 right 兩個相反方向移動的指標，每次相向移動一步，如果在某個時間點兩者重合或交錯就停下來。觀察，不管節點數量是奇數還是偶數，最後 left 總是會停留在 queue.h 中所定義的中間點，接下來就是把它刪掉。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false
    
    struct list_head *left = head->next, *right = head->prev;
    while ((left != right) && (right->next != left)) {
        left = left->next;
        right = right->prev;
    }

    list_del(left);
    element_t *entry = list_entry(left, element_t, list);
    if (entry->value)
        free(entry->value);
    free(entry);

    return true;
}

這個函式在實作 q_delete_entry 之後有做修改，將重複的程式碼拉出來實作。

q_delete_entry

Commit 9c6cb75

做 q_delete_mid 的時候我發現，抹除一個佇列中的元素的程式碼重複太多，於是就寫了這個函式，可以將一個元素從佇列中抹除，並在 Commit 9c6cb75 對先前實作的函式做更改。
另外是我有關注過去有同學的作業使用 queue.h 提供的 q_release_element 來抹除元素，但實際去讀程式碼後發現他是呼叫 test_free，這個看起來是為了要去做記憶體的檢測而去 hook 內建 free 函式的函式，而且註解中也有寫到： This function is intended for internal use only，所以我就沒使用它。
後來，因為它不需要被外面存取，所以加上 static 。

static void q_delete_entry(element_t *entry)
{
    list_del(&entry->list);
    if (entry->value)
        free(entry->value);
    free(entry);
}

以下是一些改動：

q_free

補充說明的一點是不知道為什麼 cppcheck 在這裡沒加大括號的時候會顯示 unknownMacro，於是我讓它跳過了這個檢查，因為它實際上是有引用到這個巨集的。

-list_for_each_entry_safe (entry, safe, head, list) {
-    list_del(&entry->list);
-    if (entry->value)
-        free(entry->value);
-    free(entry);
-}
+/* cppcheck-suppress unknownMacro */
+list_for_each_entry_safe (entry, safe, head, list)
+    q_delete_entry(entry);

q_delete_mid

-list_del(left);
-element_t *entry = list_entry(left, element_t, list);
-if (entry->value)
-    free(entry->value);
-free(entry);
+q_delete_entry(list_entry(left, element_t, list));

q_swap

Commit 8208029

node 初始值是 head，每次考慮 node->next 和 node->next->next，如果兩個都不是 head 就做交換，然後 node 再往下走兩格。可以發現，list.h 中的 list_move 是呼叫 list_del 再呼叫 list_add，list_del 等同於把輸入節點的前後兩節點接起來，list_add 等同於把那個節點接在輸入的 head 後面，所以正好可以用在這個函式。

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *node = head;
    while ((node->next != head) && (node->next->next != head)) {
        list_move(node->next->next, node);
        node = node->next->next;
    }
}

q_reverse

Commit 77cfa31

如果 head 是空指標或佇列是空的就回傳，否則走訪所有節點，把他們的 next 和 prev 交換，最後，把 head 的 next 和 prev 也交換。
至於交換我使用 xor swap，所以我要找到一個算術型別 (arithmetic type) 和指標永遠一樣大的，這件事情在 C99 沒有規範，但在 GNU C 卻有規範，而且它也有規範從指標到整數的轉型。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        *(uintptr_t *) &node->prev ^= (uintptr_t) node->next;
        *(uintptr_t *) &node->next ^= (uintptr_t) node->prev;
        *(uintptr_t *) &node->prev ^= (uintptr_t) node->next;
    }
    *(uintptr_t *) &head->prev ^= (uintptr_t) head->next;
    *(uintptr_t *) &head->next ^= (uintptr_t) head->prev;
    *(uintptr_t *) &head->prev ^= (uintptr_t) head->next;
}

q_merge_two

Commit a02c5af

由於 q_merge 和 q_sort 均需使用此函式的功能，因此將其實作。原設計為合併兩個具有 head 節點的佇列，但基於情境考量（即在 q_sort 中無需為每個鏈結串列額外建立 head），調整為合併兩個 head 即為首節點，且尾節點之 next 指向 NULL 的鏈結串列。

首先，建立一個新的環狀佇列，每次從兩條鏈結串列中選取應該放較前面的，依序添加至環狀佇列尾端。當其中一條鏈結串列耗盡後，若另一條仍有剩餘節點，則直接將其所有節點連接至環狀佇列。最後，將環狀佇列尾節點的 next 設為 NULL，並回傳 head.next。

static struct list_head *q_merge_two(struct list_head *head1,
                                     struct list_head *head2,
                                     bool descend)
{
    if (!head1 && !head2)
        return NULL;

    LIST_HEAD(head);
    while (head1 && head2) {
        char *str1, *str2;
        str1 = list_entry(head1, element_t, list)->value;
        str2 = list_entry(head2, element_t, list)->value;
        struct list_head **it =
            (((strcmp(str1, str2)) < 0) ^ descend) ? (&head1) : (&head2);
        struct list_head *safe = (*it)->next;
        list_add_tail(*it, &head);
        *it = safe;
    }

    *(uintptr_t *) &head1 ^= (uintptr_t) head2;
    while (head1) {
        struct list_head *safe = head1->next;
        list_add_tail(head1, &head);
        head1 = safe;
    }

    head.prev->next = NULL;
    return head.next;
}

由於 q_sort 在後來的改良中，會用到 prev 將子串列連成一個鏈結串列，所以如果可以再沒有壞處的情況下在 q_merge_two 維護這件事情會讓 q_sort 的程式碼更乾淨。而且，在效率上，因為維護單向鏈結串列的成本是比雙向鏈結串列更低的，移除沒有必要的雙向結構對效率也有好處。
這裡使用指向 head 的間接指標 indir 來做插入，這樣甚至能不去處理 head1 和 head2 都是 NULL 的情況。

Commit 0d706d1

-if (!head1 && !head2)
-    return NULL;

-LIST_HEAD(head);
+struct list_head *head = NULL, **indir = &head;
while (head1 && head2) {
    ...
-   list_add_tail(*it, &head);
+   *indir = *it;
+   indir = &(*indir)->next;
    *it = safe;
}
...
while (head1) {
    struct list_head *safe = head1->next;
-   list_add_tail(head1, &head);
+   *indir = head1;
+   indir = &(*indir)->next;
    head1 = safe;
}

q_sort

Commit 7f12999

這是一個迭代版本的 merge sort。維護一個堆疊，放的是鏈結串列的第一項，並且每次從上面放入大小為 1 的鏈結串列，每當出現大小相等的鏈節串列就從上往下合併。很簡單的發現它等價於每次觀察最上面的兩個元素是否大小相等，如果是就合併，並且繼續往下檢查。另外，因為元素都是兩兩相同大小的合併，所以每個元素大小會是 2 的冪，如果 35 格的話就可以接受最多

Σ_{i = 0}^{34} 2^{i} = 2^{35} - 1

個元素，比起 int 的範圍還大，由於 q_size 回傳 int，判斷此程式不預期使用者建立超出 2147483647 個節點。

void q_sort(struct list_head *head, bool descend)
{
    struct list_head *stack[35], *node, *safe;
    unsigned int size[35];
    if (!head || list_empty(head))
        return;

    int sp = 0;
    list_for_each_safe (node, safe, head) {
        node->next = NULL;
        stack[sp++] = node;
        size[sp - 1] = 1;
        while ((sp > 1) && (size[sp - 1] == size[sp - 2])) {
            stack[sp - 2] = q_merge_two(stack[sp - 1], stack[sp - 2], descend);
            size[sp - 2] <<= 1;
            sp--;
        }
    }

    while ((sp--) > 1)
        stack[sp - 1] = q_merge_two(stack[sp], stack[sp - 1], descend);

    INIT_LIST_HEAD(head);
    for (node = stack[0], safe = node->next;
         (node) && ((safe = node->next) || 1); node = safe)
        list_add_tail(node, head);
}

後來我發現，這樣的合併方式就是二進位的進位方式，對於每個大小（二的羃）可以對應到在一個數中的一個位元，譬如 1 對應到第 0 個位元，4 對應到第 2 個位元。兩個相同次數的數字合併，增加一個高一次的數字，其實就等價於進位，所以可以想成每次都加 1，遇到進位就合併。這樣就不須要使用 size 陣列來紀錄元素的大小。

另外，由於 int 的上界是

2^{31} - 1

，所以我把 stack 的大小壓到了 31，共剛好可以放到

2^{31} - 1

個元素。

-struct list_head *stack[35], *node, *safe;
-unsigned int size[35];
+struct list_head *stack[31], *node, *safe;
+unsigned int bit = 0;
if (!head || list_empty(head))
    return;
int sp = 0;
list_for_each_safe (node, safe, head) {
    node->next = NULL;
    stack[sp++] = node;
-    size[sp - 1] = 1;
-    while ((sp > 1) && (size[sp - 1] == size[sp - 2])) {
+    for (unsigned int i = 1; (sp > 1) && (bit & i); i <<= 1, sp--)
        stack[sp - 2] = q_merge_two(stack[sp - 1], stack[sp - 2], descend);
-        size[sp - 2] <<= 1;
-        sp--;
-    }
+    bit++;
}

去讀 qtest.c 的程式碼後，發現它有定義最多 100000 個節點。

在讀過 Linux 中的 list_sort 後，發現第一個可以融合進來的點是它利用每個節點的 prev 當作另一個維度的鏈結串列的 next，將一堆鏈結串列接起來，於是我利用這點，在 Commit 35d446d 將我的 stack 改成使用 prev 接起來的鏈節串列，這樣就不用多耗費記憶體。雖然行數變多了，因為 q_merge_two 中沒有維護 prev 的功能，但造成了對應的好處。

- struct list_head *stack[31], *node, *safe;
+ struct list_head *sp = NULL, *node, *safe;
...
list_for_each_safe (node, safe, head) {
    node->next = NULL;
-    stack[sp++] = node;
-    for (unsigned int i = 1; (sp > 1) && (bit & i); i <<= 1, sp--)
-        stack[sp - 2] = q_merge_two(stack[sp - 1], stack[sp - 2], descend);
+    node->prev = sp;
+    sp = node;
+    for (unsigned int i = 1; sp->prev && (bit & i); i <<= 1) {
+        struct list_head *a = sp;
+        sp = sp->prev->prev;
+        a = q_merge_two(a, a->prev, descend);
+        a->prev = sp;
+        sp = a;
+    }
    bit++;
}

- while ((sp--) > 1)
-     stack[sp - 1] = q_merge_two(stack[sp], stack[sp - 1], descend);
+ while (sp->prev) {
+    struct list_head *a = sp;
+    sp = sp->prev->prev;
+    a = q_merge_two(a, a->prev, descend);
+    a->prev = sp;
+    sp = a;
+}

在 q_merge_two 做了一些更改，讓鏈結串列中的節點的 prev 不會被改動。所以我先讓 a 變成 sp->prev，接下來讓 sp->prev 和 a->prev 都是 sp->prev->prev。因為合併完之後的開頭一定是他們的其中一個，所以它開頭的 prev 一定是一開始的 sp->prev->prev。因為修改過瑣碎，這裡只列出部份以示意。

Commit 6542272

- struct list_head *a = sp;
- sp = sp->prev->prev;
- a = q_merge_two(a, a->prev, descend);
- a->prev = sp;
- sp = a;
+ struct list_head *a = sp->prev;
+ sp->prev = a->prev;
+ sp = q_merge_two(sp, a, descend);

q_delete_dup

Commit a71c2e0

用兩個指標 l 、r，在走訪過程中，讓 r 移到元素字串值和 l 一樣的元素裡最右邊的元素的 next，而如果 r 是 l 的下一個的話就代表這個字串只有一個，就不刪除，否則就沿路刪除。另外，由於 r 紀錄的東西剛好是下一個 l，可以充當 safe 的角色，所以中間東西是可以安全刪除的。

bool q_delete_dup(struct list_head *head)
{
    struct list_head *l, *r;
    if (!head || list_empty(head))
        return false;

    for (l = head->next, r = l->next; l != head; l = r, r = l->next) {
        while ((r != head) && !strcmp(list_entry(l, element_t, list)->value,
                                      list_entry(r, element_t, list)->value))
            r = r->next;
        if (r == l->next)
            continue;
        for (struct list_head *safe = l->next; l != r; l = safe, safe = l->next)
            q_delete_entry(list_entry(l, element_t, list));
    }
    return true;
}

q_descend

Commit 3f2ce92

這個函式要刪除所有在後面有比它大的節點的節點，等價於留下所有是後綴最大值的節點。所以我從最後一個元素往前跑，紀錄後綴最大值，如果此節點的值大於等於最大值就更新最大值，否則刪除節點。另外，用一個 safe 來紀錄現在節點的 prev，讓我在中間可以安全的刪除節點。

int q_descend(struct list_head *head)
{
    const char *greatest = NULL;
    struct list_head *node, *safe;
    int cnt = 0;

    if (!head || list_empty(head))
        return 0;

    for (node = head->prev, safe = node->prev; node != head;
         node = safe, safe = node->prev) {
        element_t *entry = list_entry(node, element_t, list);
        if (!greatest || strcmp(entry->value, greatest) >= 0) {
            cnt++;
            greatest = entry->value;
            continue;
        }
        q_delete_entry(entry);
    }

    return cnt;
}

這在之後與 q_ascend 的實作合併了

q_reverseK

Commit 1df3dfd

這個程式要把每 K 個節點做反轉。使用兩個指標 l 、r，l 代表每次迴圈所考慮的區間左界的前一格，r 一開始在左界，並且一直往右跑，如果遇到 head 就結束，否則最後總共會移動 k 格，也就是現在考慮區間右界的下一格。換句話說，每次考慮的區間是

(l, r)

。如果到這裡還沒結束，就會反轉

(l, r)

區間，方式是建一個暫時的 head，並且使用 list_cut_position 將區間移過去，使用 q_reverse 做反轉後再用 list_splice 將反轉完的節點移回來。另外，r 同時是下一次迴圈要考慮的區間左界，也同時是下一次 r 要開始跑的起點，可以當作 safe 的作用，讓區間內可以做刪除。

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;
    struct list_head *l = head, *r = head->next;
    for (;; l = r->prev) {
        for (int i = 0; i < k; i++, r = r->next)
            if (r == head)
                return;
        LIST_HEAD(tmp);
        list_cut_position(&tmp, l, r->prev);
        q_reverse(&tmp);
        list_splice(&tmp, l);
    }
}

q_merge

Commit c45ab9d

此函式輸入一個佇列，每個元素中都有一個佇列的 head，把這些佇列合併。首先，從 qtest.c 中呼叫 q_new 的地方可以發現，最外面是一個型別為 queue_chain_t 的 chain，裡面放了一個 head，代表一個佇列的頭，這個佇列把一堆型別為 queue_contex_t 的東西串起來，裡面有一個元素 q，代表一個佇列的頭。所以可以得知，包在輸入的參數外面的型別是 queue_context_t ，而其中的 struct list_head 元素是 chain。

queue_contex_t *qctx = malloc(sizeof(queue_contex_t));
list_add_tail(&qctx->chain, &chain.head);

qctx->size = 0;
qctx->q = q_new();
qctx->id = chain.size++;

current = qctx;

這個程式之後讀完一些資料後會再回來做些改良，現在只是單純的把串列一個一個合併起來。

在 Commit 7c2224a，我引入了 Powersort 到這個函式裡，讓它能以更接近 top-down merge 的分割方式進行合併。對於此方法的解釋我放在 ideas

q_descend_ascend

Commit bba369f

由於 q_descend 和 q_ascend 的功能太像了，所以例外獨立實作出 q_descend_ascend 函式，帶入一個布林參數 descend 來決定使用哪個。至於比較方面，如果 descend 是 0 的話相當於 strcmp 的結果不會動，如果 descend 是 1 的話相當於取二補數。

q_descend_ascend

...
- strcmp(entry->value, greatest) >= 0
+ (strcmp(entry->value, greatest) ^ -descend) + descend <= 0
...

q_descend

int q_descend(struct list_head *head)
{
    return q_ascend_descend(head, 1);
}

q_ascend

int q_ascend(struct list_head *head)
{
    return q_ascend_descend(head, 0);
}

亂數

shuffle 命令實作

Commit 87de389

首先在 console_init 中註冊一個新的命令 shuffle:

ADD_COMMAND(shuffle, "Shuffle the nodesd of the queue", "");

接下來實作 do_shuffle，觀察 do_sort 的實作，current->q 是現在在處理的佇列，而另外， exception_setup 和 exception_cancel 是 harness.c 提供，拿來處理意外狀況的。一開始，在 q_init 中設定不同訊號的 handler 函式，在這個函式如果收到訊號會呼叫 trigger_exception。exception_setup 第一次進入時會先初始化，並且回傳 true，當 trigger_exception 被觸發時，會使用 siglongjump 跳到 exception_setup 中，並且這時會處理錯誤，並且如果不是致命錯誤的話會 return false，回到一開始呼叫 exception_setup 的地方。最後，再 exception_cancel，回到沒有在處理意外狀況未出始化的情況。

static bool do_shuffle(int argc, char *argv[])
{
    ...
    if (current && exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();
    q_show(3);
    return 1;
}

然後是使用 Fisher-Yates shuffle algorithm 實現 q_shuffle，我先定義固定的就是在尾部我們以後都不會再動的節點，每次的迴圈，我們會從所有還沒固定的節點中選一個和還沒固定的節點中最右邊的節點交換（自己和自己交換就是不動），並將它固定，直到有 len - 1 個節點固定了，最後一個節點也就固定了。

static void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    int len = q_size(head);
    struct list_head *l, *r = head;
    for (; len > 1; len--, r = r->prev) {
        int choose = rand() % len;
        if (choose == len - 1)
            continue;
        l = head;
        while (choose--)
            l = l->next;
        list_move_tail(l->next, r);
        list_move(r->prev->prev, l);
    }
}

統計方式驗證 shuffle

這裡使用範例所提供的 python 程式碼進行實驗（只把在迴圈中做字串加法的部份改成將字串做乘法，否則太慢），分析 4 個元素進行 shuffle 是否符合 Uniform distribution，也就是分佈是平均的。首先提出須假說：

$H_{0}$ （虛無假說）：各種結果發生的次數符合 Uniform distributin
$H_{1}$ （對立假說）：至少一種結果發生的次數與其他不同

此為資料適合度分析，測試資料是否符合某種比例，使用 Pearson's chi-squared test，計算卡方值：

χ^{2} = \sum_{i = 1}^{n} \frac{(O_{i} - E_{i})^{2}}{E_{i}}

其中，

O_{i}

表示的是此種結果的實際觀察值，

E_{i}

表示的是在假設的比例上，此種結果數量的期望值。

1. 計算卡方值

這裡是做了 1000000 次 shuffle 後，所得到的期望值與卡方值：

Expectation:  41666
Observation:  {'1234': 41641, '1243': 41362, '1324': 41920, '1342': 41622, '1423': 41968, '1432': 41759, '2134': 41686, '2143': 41622, '2314': 41391, '2341': 41645, '2413': 41851, '2431': 41685, '3124': 41824, '3142': 41681, '3214': 41490, '3241': 41514, '3412': 41675, '3421': 41304, '4123': 41806, '4132': 41701, '4213': 41679, '4231': 41886, '4312': 41639, '4321': 41649}
chi square sum:  15.675610809772957

總共有

4!

種結果，可以發現

41666

實際上就是

⌊ \frac{1000000}{4!} ⌋

。
這裡由於有 24 種結果，太長了就不以表格表示。

2. 決定自由度

總共有 24 種結果，所以有 23 個變數是可以自由變動的，自由度是 23

3. 選擇顯著水準

這裡用顯著使用的顯著水準是 0.05，代表在

H_{0}

成立的情況下，錯誤拒絕

H_{0}

的機率小於 0.05，就會拒絕虛無假說

H_{0}

。也就是卡方值太大，大到大於此卡方值的機率小於 0.05。
於是對應卡方分布表，可以使用 python 來獲得

P

值：

from scipy.stats import chi2

# print(chi2.ppf(0.05, 23))
# 35.17246162690806
# 可以看出自由度為 23 時，卡方值要多大才能讓大於此卡方值出現的機率小於 0.05

print(1 - chi2.cdf(15.675610809772957, 23))
# 0.8687996682513008

這個套件預設的是左尾，也就是從 0 開始算面積得到的值，所以用 1 減掉它就是大於此卡方值的機率。

4. 結論

計算出的

P

值是 0.8687996682513008，大於顯著水準 0.05，所以不拒絕虛無假說

H_{0}

熵（Entropy）

根據由大數法則理解訊息熵(entropy)的數學意義，熵可以這樣解釋，對於某個在 1 附近的下界

1 - ϵ

，我都可以找到一個

ϵ

-high-probability set 是字元集

S^{n}

的子集，使得在

S^{n}

中在特定機率分佈下選擇時落在

ϵ

-high-probability set 裡面的機率大於

1 - ϵ

。至於選法是使用

\log \circ P

函數（其中

\log

以

2

為底，而

P

是機率質量函數），依據弱大數法則如果一個函數由

S

映射到實數且對於特定隨機分佈的期望值為有限實數的話，那麼取樣

n

個，當

n

趨近於無限的時候，函數的平均會趨近於期望值。既然趨近於平均值，就等價於對於任意的

δ

，都可以存在一個

n_{0}

，使得當

n \geq n_{0}

　時，

\log \circ P

　的取樣平均和

E [f (S)]

　距離小於　

δ

　的機率大於

1 - ϵ

。所以，選擇

ϵ

-high-probability set 的方式可以透過與

\log \circ P

期望值距離小於某個值來判斷。至於為何使用這個函數呢？這是因為獨立事件的機率是相乘的，如果我把個別的機率取

\log

之後去做平均，那麼在

\log

中就會變成相乘的，剛好就是在字元集

S

中取長度為

n

的字串

s^{n}

出現的機率。

E [\log (P (s))] - δ <= \frac{1}{n} \sum_{i} \log (P (s_{i})) = \frac{1}{n} \log (\prod_{i} P (s_{i})) = \frac{1}{n} \log (P (s^{n}))

這裡補充說明一下變數意思：

$s$ ：一個從
$S$ 字元集中以機率質量函數
$P$ 分佈的隨機變數
$P (s_{i})$ ：取出某個特定變數的機率
$P (s = s_{i})$
$P (s^{n})$ ：取出
$n$ 個字元組成的字串為特定字串的機率

這個證明說明了兩點東西：

第一點，對於

S^{n}

中的某個元素而言，把它歸在

ϵ

-high-probability set 內的標準是他的每個字元經過

\log \circ P

之後的平均值與

E [f (s)]

的距離小於

δ

，而且他們形成的集合確實會符合

ϵ

-high-probability set 的定義。

第二點，從

S^{n}

中隨機取一個元素時（亦即長度為

n

的字串），恰好與某個特定元素相等的機率，在

n

夠大時會接近

2^{n E [l o g (P (s))]}

。假設每種結果發生的機率是相等的，那麼總共會有

2^{- n E [l o g (P (s))]}

種結果，也就是說

n

個字元總共的資訊量是

- n E [l o g (P (s))]

位元，一個字元的資訊量是

- E [l o g (P (s))]

位元。這時我們把期望值展開，會發現一件事：

- E [l o g (P (s))] = - \sum_{i} P (s_{i}) \log (P (s_{i}))

這剛好就是熵的公式

H (s)

論文〈Dude, is my code constant time?〉

閱讀論文

為了防範 Timing attack，必須要有方法測試程式對於不同輸入的執行時間穩定性，不希望由時間洩漏出資訊。以往的分析方式需要對硬體建模，然而這並不容易，所以本文提供了一種經由洩漏測試與對結果的統計得到結論的方式。首先是定義 fix 和 random 兩種類別，fix 是一種極端特例，random 是對每次測量都隨機的。量完時間後，要經過一些預處理。去除被外部因素中斷或執行太長時間的，用某種 higher-order pre-processing 使得數據次方數提高（非線性，但未了解是什麼，要看程式碼才清楚）。接下來要以某個百分位數

p

去除右尾的資料，因為他們受到比較多與輸入資料無關的外界因素影響，而另外會使用不同

p

值去進行測試。最後，進行統計。

$H_{0}$ ：兩者的分佈是相同的
$H_{1}$ ：兩者的分佈不相同

兩組獨立樣本，異質性檢定，只知道樣本標準差的情況，使用 t-test 。

程式碼分析

首先觀察到，第 17 筆測試資料一開始輸入 option simulation 1，於是我使用這個選項後使用 gdb 進行動態分析，這裡使用的是有裝 pwndbg 插件的 gdb。在 option simulation 1，的情況下，斷點下在 interpret_cmda，執行 it 命令。一直往下走到執行 next_cmd->operation 之後叫了 do_it、queue_insert，會發現它如果在 simulation 模式會呼叫 is_insert_tail_const。

 ► 0x57fdbab05dd4 <queue_insert+61>    jne    queue_insert+136            <queue_insert+136>
 
   0x57fdbab05dd6 <queue_insert+63>    call   is_insert_tail_const        <is_insert_tail_const>

在裡面會去呼叫 test_const，第一個參數是 "insert_tail" 字串，第二個參數是 1

 ► 0x57fdbab0a13b <is_insert_tail_const+20>    call   test_const                  <test_const>
        rdi: 0x57fdbab0d725 ◂— 'insert_tail'
        rsi: 1

到這裡，已經可以簡單的去追蹤程式碼了。
在 constrant.h 中，定義了：

#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)
    
#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};

在 fixture.c 中定義了：

#define DUT_FUNC_IMPL(op) \
    bool is_##op##_const(void) { return test_const(#op, DUT(op)); }

#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _

展開後等同於：

bool is_insert_head_const(void) { return test_const("insert_head", 0); }
bool is_insert_tail_const(void) { return test_const("insert_tail", 1); }
...

在 test_const 中，會去呼叫 doit，原本以為這裡有問題，但讀完後面理解了。他的 doit 的回傳值來自 report，而當 report 沒有得到 ENOUGH_MEASURE 那麼多的資料的話就會回傳 false，而它每次會丟棄前後各 DROP_SIZE 個，加起來會超過 ENOUGH_MEASURE，而 result 就是取最後一個 doit 的結果。

for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
    ++i)
    result = doit(mode);

接下來是 doit 中呼叫的函式：

measure：執行程式，測量開始與結束時間
differentiate：計算執行時間
update_statistics：更新各類別資料
report: 進行統計

這裡來看看拿來統計的函式 t_push 和 t_compute 是怎麼計算的。
首先是 t_push，這個平均數更新的方式實際上就是將每個變數減掉原本的平均數後，做平均，再把舊的平均數加回來，這樣的好處是原本的數在計算時能變 0：

{\overset{―}{X}}_{n e w} = {\overset{―}{X}}_{o l d} + \frac{0 \times n_{o l d} + (x - {\overset{―}{X}}_{o l d})}{n_{n e w}}

而 m2 指的就是離均差平方和

S_{X X}

static void t_push(ttest_ctx_t *ctx, double x, uint8_t clazz) {
  assert(clazz == 0 || clazz == 1);
  ctx->n[clazz]++;
  /*
   estimate variance on the fly as per the Welford method.
   this gives good numerical stability, see Knuth's TAOCP vol 2
  */
  double delta = x - ctx->mean[clazz];
  ctx->mean[clazz] = ctx->mean[clazz] + delta / ctx->n[clazz];
  ctx->m2[clazz] = ctx->m2[clazz] + delta * (x - ctx->mean[clazz]);
}

然後是 t_compute，可以發現，t 值是

\frac{\overset{―}{X_{1}} - \overset{―}{X_{2}}}{\sqrt{\frac{S_{1}^{2}}{n_{1}} + \frac{S_{2}^{2}}{n_{2}}}}

static double t_compute(ttest_ctx_t *ctx) {
  double var[2] = {0.0, 0.0};
  var[0] = ctx->m2[0] / (ctx->n[0] - 1);
  var[1] = ctx->m2[1] / (ctx->n[1] - 1);
  double num = (ctx->mean[0] - ctx->mean[1]);
  double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
  double t_value = num / den;
  return t_value;
}

接下來看下 github 上的程式碼和這裡的程式碼有什麼差異吧。
它使用了 dudect_ctx_t 這個結構體把東西裝起來：

typedef struct {
  int64_t *ticks;
  int64_t *exec_times;
  uint8_t *input_data;
  uint8_t *classes;
  dudect_config_t *config;
  ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
  int64_t *percentiles;
} dudect_ctx_t;

dudect_init 是拿來初始化 ctx 的，而 dudect_main 是拿來執行一次的測量，我們追進去 dudect_main 看。會發現，程式流程與 doit 中大致相同（當然 doit 是在裡面才初始化資料，但不太重要的差異在以下都省略），只有他在 first_time 是 true 的時候會執行 prepare_percentiles，其他時候去統計資料。

if (first_time) {
  // throw away the first batch of measurements.
  // this helps warming things up.
  prepare_percentiles(ctx);
} else {
  update_statistics(ctx);
  ret = report(ctx);
}

看 prepare_percentiles，它做的事情是先將 exec_times 排序，然後分別挑選前

1 - {0.5}^{\frac{i}{10}}, i = 1, 2, . . ., 100

比例的數字，放進 percentiles 陣列中

static void prepare_percentiles(dudect_ctx_t *ctx) {
  qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
  for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
    ctx->percentiles[i] = percentile(
        ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
        ctx->config->number_measurements);
  }
}

看 update_statistics 會發現，lab-0 中的 update_statistics 並沒有做 crop 和 second-order test，而 github 上的專案有，而且他的 ttest_ctxs 是好幾組的資料，分別是一個不做預處理的，DUDECT_NUMBER_PERCENTILES 個做完 crop 的，和最後面是做完 second-order test 的。
根據作業提示：

注意：現有實作存在若干致命缺陷，請討論並提出解決方案
在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無。當你改進後，可提交 pull request，務必提供對應的數學分析

而 crop 實際做的就是對於每個 crop_index 把小於每個對應的 percentiles 的 exec_times 去除掉，所以能推斷，這裡必須去將 crop 的預處理方式移植進來。

追進去 report 中的 max_test 中，會發現他在 ctx 的 ttest_ctxs 中找到最大 t 值的那個資料，並且使用它。

static ttest_ctx_t *max_test(dudect_ctx_t *ctx) {
  size_t ret = 0;
  double max = 0;
  for (size_t i = 0; i < DUDECT_TESTS; i++) {
    if (ctx->ttest_ctxs[i]->n[0] > DUDECT_ENOUGH_MEASUREMENTS) {
      double x = fabs(t_compute(ctx->ttest_ctxs[i]));
      if (max < x) {
        max = x;
        ret = i;
      }
    }
  }
  return ctx->ttest_ctxs[ret];
}

然而，這裡有個疑問，論文中會選擇

p

是因為執行時間較長的較容易受到非輸入資料的影響，然而專案中卻是在各種不同的

p

篩選的資料中，選

t

值最大的。這樣的話，如果右尾是因環境因素影響而造成兩者的分佈不同，這樣他的

t

值更容易比較大，也就比較可能被採納，那這樣真的能達到去除極端值的效果嗎？基於這個緣故，在我發現這樣的處理方式的合理性之前，只會根據論文中的概念，用一個適合的比例去切割資料，並且用實驗佐證這樣的比例是合理的。

We discard measurements that are larger than the p percentile, for various values of p. The rationale here is to test a restricted distribution range, especially the lower cycle count tail. The upper tail may be more influenced by data-independent noise.

到這裡，整個程式的流程都清楚了，可以開始改程式碼了。

程式碼改善

這裡去畫了 remove_head 中，兩個 class 的執行時間累積分佈函數的圖，可以發現他們在達到總比例的 0.6 之前都是幾乎重合的。

但是，我們應該要考慮他們即使在 cpu cycle 比較大的情況下也是因為輸入資料的不同而造成差異的可能性，所以下面會做一個實驗。

可以發現，在 prepare_inputs 中，假如是在 fix 這個類別的 input_data 會全被設為 0。

for (size_t i = 0; i < N_MEASURES; i++) {
        classes[i] = randombit();
        if (classes[i] == 0)
            memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);
    }

至於，這個 input_data 會被用在哪呢？它會決定在執行每個函式之前會執行多少次 insert_head，而其他所有的輸入字串都是隨機的。

dut_new();
dut_insert_head(
    get_random_string(),
    *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);

根據前面的數據，這個 input_data 是會對執行時間造成影響的，然而，我們要分辨出這個影響是影響環境還是因為它影響了佇列的長度造成函式的執行時間變長。於是舉了一個極端例子：

dut_new();
dut_insert_head(
    get_random_string(),
    *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
before_ticks[i] = cpucycles();
do_nothing();
after_ticks[i] = cpucycles();

其中，這個 do_nothing 函式是這樣的：

void do_nothing()
{
}

他是名副其實的 do nothing，然而，統計出來的圖表長這樣：
do_nothing

我們另外可以去嘗試觀察函式和 input_data 有關會發生什麼事，我將 dut_insert_head 塞進去測時間，它的執行時間和 input_data 的關係是線性的：

before_ticks[i] = cpucycles();
dut_insert_head(
    get_random_string(),
    *(uint16_t *) (input_data + i * CHUNK_SIZE) % 100);
after_ticks[i] = cpucycles();

可以發現，他們在左尾的差距就極大。

由此，可以推斷出，這兩者在 cpu cycle 較長的這些比例上，造成的差異是由環境因素造成的。並且，因為他們在 cpu cycle 較短的那些比例上都很明顯分佈相似，我們為將某個百分位數以上的數據去除來比較。然而，如果依照文中的方式，因為差異大的 t 值也會較大，最後會取到的 t 值會是在 p 值較大而留下比較多右尾的數據，所以我取 50 百分位數，在這裡，連 do_nothing 都開始分叉了，代表環境因素已經開始影響執行時間了。

於是，開始改程式碼：

Commit 3daf4ce

增加一個 percentiles 變數，第一次使用 prepare_percentiles 初始化。

static bool doit(int mode)
{
    ...
+   int64_t percentiles = 0;
    ...
-   update_statistics(exec_times, classes);
+   if (!percentiles)
+       prepare_percentiles(&percentiles, exec_times);
    
+   update_statistics(exec_times, classes, percentiles);
}

在 update_statistics 中，將 exec_times 小於等於 percentiles 的資料丟棄。

static void update_statistics(...)
{
    ...
-   t_push(t, difference, classes[i]);
+   if (difference < percentiles)
+       t_push(t, difference, classes[i]);
}

prepare_percentiles 就是把 exec_times 從小到大排之後取中位數。

void prepare_percentiles(int64_t *p, int64_t *exec_times)
{
    qsort(exec_times, N_MEASURES, sizeof(int64_t), cmp);
    *p = exec_times[N_MEASURES >> 1];
}

這樣做之後看一下 insert_head 和 remove head 的累積分佈函數，可以發現他們的 fix 和 random 幾乎都重合了。
ih_after
rh_after

這個時候，我們來試一下，如果去測試 dut_insert_head(s, input) 這個

O (n)

的插入會發生什麼:
這個時候意外發生了，

O (n)

的 insert 通過了常數的檢查，後來發現是我在排序的時候把兩種類別一起排序了，元素混在一起，於是在 Commit 68df51d 修正了。
這裡出現另一個問題，insert_head 和 insert_tail 的常數測試不會過，去看了圖表後發現他們在 cpu cycle 很小的時候就和 fix 類別有所差異。由於他們前面會經過一個最多 9999 次的插入操作，我在思考是否是 malloc 的影響，於是做了實驗。用一個與 input_data 有關系的 malloc，來測量前面 malloc 空間為隨機大小與固定大小（0）時，對於單一一個固定空間的 malloc 執行時間是否有影響。

void *k = malloc((*(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000) * sizeof(element_t));
before_ticks[i] = cpucycles();
malloc(sizeof(element_t));
after_ticks[i] = cpucycles();
free(k);

由下圖可以看到，它明顯的造成了影響：
malloc

於是，在 Commit e4f28ec 我將前面 malloc 的範圍從 10000 改成了 1000。此時，如果去檢查

O (n)

的插入函式的話，那麼結果如下：
On_after

發現他還是可以清楚的將

O (n)

的函式分辨出來的，而經過這樣的修改，可以在 github 上看到卡比了。

看到 weiso131 開發紀錄使用了上述方式進行討論，並且下了以下結論：

然而，這仍無法根本解決 malloc 的問題，程式仍然有受到時序攻擊的風險

我當時有思考過這個問題，但因為實驗結論是前面使用的 malloc 數量會對程式的執行時間造成影響，所以它能透過單一一個 q_insert_head 執行的時間來測量程式中所使用的 malloc 數量。我認為這個問題不需要解決，原因有以下兩點。第一點，因為這個程式中可能有多個佇列，所以它就算能推出裡面被分配多少空間還是推不出這個佇列的大小，換言之就是相同資訊所能代表的東西太多了。第二點，如果說是以不想讓對方獲得不預期他獲得的任何資訊的觀點的話，那麼這樣的修改不符合比例。因為沒辦法更快了，只能讓跑得快的那些跑得慢一些，而對於一個危害很低的東西卻犧牲很多的效率（畢竟 q_insert_head 是一個很基礎的操作），我認為不值得。

與 weiso131 討論後，發現 doit 中呼叫的 measure 會在頭尾各去掉 DROP_SIZE 個資料，但是 differentiate 和 update_statistics 卻不會把他們去掉。去掉頭尾各 DROP_SIZE 的資料是為了要把測量資料的頭尾去掉，但依照它原本的寫法是會少測量 2 * DROP_SIZE 個東西，然後用陣列的初始直去進行處理，會有非預期行為，所以我在 Commit 257c0c9 將 measure 變成從 1 到 N_MEASURES，而其他的去頭去尾。

Linux 核心的鏈結串列排序

首先，我們要來理解 linux 中的 list_sort 是怎麼做的。

操作流程

定義可以合併的狀態是 3 個一組的 1 或者是 2 個一組的

2^{k}, k > 0

，數字比較小的優先級比較高。一開始，陣列是空的，每次會放一個 1 進來，並且如果有可以合併的數字就選優先級最高的一組數字做一次合併，合併的定義是從裡面拿兩個出來組合成他們的相加，譬如 2, 2 會合併成 4。以下舉例子：

陣列數字總和	合併前	合併後	解釋
1	1	1	沒有可合併的
2	1, 1	1, 1	沒有可合併的
3	1, 1, 1	2, 1	有 3 個 1，合併兩個 1
4	2, 1, 1	2, 1, 1	沒有可合併的
5	2, 1, 1, 1	2, 2, 1	有 3 個 1，合併兩個 1。因為只合併一次，所以雖然有兩個 2 但不合併
6	2, 2, 1, 1	4, 1, 1	有 2 個 2，合併為一個 4

而怎麼快速確認現在要合併那個東西呢？利用二進位的特性，合併策略可以轉換為以下，定義

n

為陣列數字總和，我們有一個合併前的陣列和

n

時，先檢查

n

是否為 2 的羃，如果是的話就不合併，否則如果

n

的

l o w b i t

是

2^{k}

的話，那就合併兩個

2^{k}

變成

2^{k + 1}

，以下將上述例子轉換成這種解釋方式：

$n$	合併前	合併後	解釋
1	1	1	$n = 2^{0}$ ，所以不合併
2	1, 1	1, 1	$n = 2^{1}$ ，所以不合併
3	1, 1, 1	2, 1	$n$ 的 $l o w b i t$ 是 $2^{0}$ ，所以合併兩個 $2^{0}$ 為 $2^{1}$
4	2, 1, 1	2, 1, 1	$n = 2^{2}$ ，所以不合併
5	2, 1, 1, 1	2, 2, 1	$n$ 的 $l o w b i t$ 是 $2^{0}$ ，所以合併兩個 $2^{0}$ 為 $2^{1}$
6	2, 2, 1, 1	4, 1, 1	$n$ 的 $l o w b i t$ 是 $2^{1}$ ，所以合併兩個 $2^{1}$ 為 $2^{2}$

然而，這樣的理解肯定是不夠的，在朋友 bir 的啟發下，我得到了以下這種直觀的對於這種轉換的理解：
首先，如果是在考慮第 0 個位元是 1 的情況的話很簡單，這個時候

n

一定是奇數，而因為只要大於等於 3 個 1 就會在之前被合併，所以不會出現 5 個以上的狀況。而因為每次把兩個 1 合併為 2 都會留下一個 1，所以拿到多一個 1 的時候，除非沒有合併過 2，否則一定至少有 2 個 1，所以它一定有恰 3 個 1。沒有合併過 2 而第 0 個位元是 1 有兩種情況，如果是

n = 1

的話他是 2 的羃，

n = 3

的話它明顯是 3 個 1。所以，除了

n = 1

以外的

l o w b i t

是

2^{0}

的情況下，都可以合併兩個

2^{0}

為

2^{1}

。
接下來，考慮

l o w b i t

是

2^{k}, k > 0

的情況（假設小於

k

的狀況都正確）。出現第一次

l o w b i t

為

2^{k}

的是

n = 2^{k}

，這個時候陣列裡有一個

1

和一些一定小於

2^{k}

的數，所以無法對

2^{k}

做合併。接下來考慮非 2 的羃且

n

的

l o w b i t

為

2^{k}

的情況，因為上一個

l o w b i t

為

2^{k - 1}

的數一定不是

2^{k - 1}

（這件事情很顯然，他是

2^{k} + 2^{k - 1}

或之後的數字），所以一定會合併出一個

2^{k}

。接下來，我們來討論一下以下的某種循環的特性，注意到對於

2^{k}

這個數的合併，高位是不重要的，我用 ... 表示（雖然這裡一開始是 0，但因為表示不重要，我從頭到尾都寫 ...）。而 X 是一個長度為

k - 1

的由 0 組成的序列。以下這些情況是從第一次出現

l o w b i t

為

2^{k}

開始的每次出現

l o w b i t

為

2^{k}

或

2^{k - 1}

的情況：

...10X：
$l o w b i t$ 為
$2^{k}$
這是第一次出現
$l o w b i t$ 為
$2^{k}$ 的
$n$ ，是 2 的羃
...11X：
$l o w b i t$ 為
$2^{k - 1}$
這個時候，因為
$l o w b i t$ 為
$2^{k - 1}$ ，會合併兩個
$2^{k - 1}$ ，此時有一個
$2^{k}$
...01X：
$l o w b i t$ 為
$2^{k - 1}$
因為在
$2^{k - 1}$ 進位時，
$2^{k}$ 也跟著進為了，所以下一個出現的
$l o w b i t$ 為
$2^{k - 1}$ 。此時，會合並出一個
$2^{k}$ ，共有兩個
$2^{k}$
...10X：
$l o w b i t$ 為
$2^{k}$
這時，有兩個
$2^{k}$ ，合併成一個
$2^{k + 1}$
...11X：等同於第 2 種狀態

由以上的解釋，可以簡單的理解，每個非 2 的羃且

l o w b i t

為

2^{k}

的

n

都會落在第 4 種狀態中，所以都會有且僅有兩個

2^{k}

可以合併為

2^{k + 1}

這裡提供另一個性質，是在後面看實作時思考出來的，就是當我在某個時刻可以對兩個

2^{k}, k > 0

做合併的時候，在合併前必定是 2 個 1，從

2^{1}

到

2^{k - 1}

的數都只有恰 1 個（如果左界小於右界就是沒有任何數）。當

k = 1

的時候很顯然，因為前一次一定是有 3 個 1，其中 2 個合併成一個 2，這時候再插進 1 個 1 就會是 2 個 1。對於

k > 1

，在小於

k

這個性質都成立的狀況下，如果這次可以合併兩個

2^{k}

代表其中一個最新生成的

2^{k}

會是某次由兩個

2^{k - 1}

合成的，而這組

2^{k - 1}

合成時要滿足 1 有 2 個且從

2^{1}

到

2^{k - 2}

的數都恰 1 個，在這種情況下，只要補一個 1 進來，就會從低位開始出現可以合併的東西，而且每次生成一個高一位的東西就會使他的數量變成 2，所以可以保證一定有一個

2^{k - 1}

會在

2^{k}

被合併之前被合併一個出來，同理對於

2^{k - 1}

而言，如果

k - 2 > 0

的話，那在它被合成出來後也會保證有一個

2^{k - 2}

會被合成出來，以此類推。最後會到保證了一個

2^{1}

會被合併出來，而他是被 2 個 1 合併出來的，代表這個時候合併完只剩下 1 個 1，所以再拿一個 1 進來的時候 1 的數量恰 2 個，而從

2^{1}

到

2^{k - 1}

的數都恰 1 個，這個時候會將兩個

2^{k}

合併成

2^{k + 1}

。

到這裡，我才了解一開始說的，合併方式是有

3 \times 2^{k}

時，合併前兩個

2^{k}

變成

2^{k + 1}

，這句話的意思。

合併方式是當有
$3 \times 2^{k}$ 個節點時，合併前兩個
$2^{k}$ 變成
$2^{k + 1}$ ，並留下一個
$2^{k}$ 不動，維持著合併：不合併為 2 : 1 的比例，因為只要
$3 \times 2^{k}$ 可以放得進 L1 cache，可以避免 cache thrashing。

而我覺得這句話這樣講會較清楚：「合併方式是當大小小於等於

2^{k}

的子串列中，恰有

3 \times 2^{k}

個節點時，合併前兩個

2^{k}

變成

2^{k + 1}

，並留下一個

2^{k}

不動，維持著合併：不合併為 2 : 1 的比例，因為只要

3 \times 2^{k}

可以放得進 L1 cache，可以避免 cache thrashing。」，這樣才能包含所有合併的情況。
於是，換成這樣的思考模式後，前述的例子可以這樣思考：

陣列數字總和	合併前	合併後	解釋
1	1	1	沒有任何 $k$ 符合條件
2	1, 1	1, 1	沒有任何 $k$ 符合條件
3	1, 1, 1	2, 1	小於等於 $2^{0}$ 的有 $3 \times 2^{0}$ 個，所以合併兩個 $2^{0}$
4	2, 1, 1	2, 1, 1	沒有任何 $k$ 符合條件
5	2, 1, 1, 1	2, 2, 1	小於等於 $2^{0}$ 的有 $3 \times 2^{0}$ 個，所以合併兩個 $2^{0}$
6	2, 2, 1, 1	4, 1, 1	小於等於 $2^{1}$ 的有 $3 \times 2^{1}$ 個，所以合併兩個 $2^{1}$

實作方式

這個程式最巧妙的一點是它利用了雙向鏈結串列在變成單向鏈結串列使用時沒用到的 prev，將它變成另一個維度的鏈節串列的 next，並且將一大堆鏈結串列連起來。

list 是現在處理到的鏈結串列節點，每次會從那裡取一個節點加進來，pending 是現在已經加進來的鏈節串列們用 prev 所連成的鏈結串列，count 是已經加入 pending 的節點總數。

struct list_head *list = head->next, *pending = NULL;
size_t count = 0;	/* Count of pending */

在還沒將 count 更新前，從最低位開始找到第一個不是 1 的位元，代表當 count++ 之後的

l o w b i t

，而 tail 也跟往下走。tail 是一個間接指標，一開始指向 pending。在 pending 裡面，存著再做這次插入之前，所有已經被插入的鏈結串列由數量小到數量大，譬如如果 count 是 5 的話，那它裡面就是 1 -> 2 -> 2。因為 pending 一開始指向的是這個鏈節串列中的第 0 個（這裡約定使用 0-index），如果 count++ 後的

l o w b i t

是

2^{0}

且非 2 的羃次的情況，那 tail 會移動 0 步，*tail 和 (*tail)->prev 剛好指向兩個要合併的東西。而如果 count++ 後的

l o w b i t

是

2^{k}, k > 0

的話，那代表只有一個

1

，而且比

k

還要低位的都只有 1 個（這件事在上面證明過了），所以 tail 移動 k 步，*tail 和 (*tail)->prev 也剛好指向兩個要合併的東西。所以它將兩個合併起來後，再把它接在 tail 的前面。

do {
    size_t bits;
    struct list_head **tail = &pending;
    /* Find the least-significant clear bit in count */
    for (bits = count; bits & 1; bits >>= 1)
        tail = &(*tail)->prev;
    /* Do the indicated merge */
    if (likely(bits)) {
        struct list_head *a = *tail, *b = a->prev;
        a = merge(priv, cmp, b, a);
        /* Install the merged result in place of the inputs */
        a->prev = b->prev;
        *tail = a;
    }
    /* Move one element from input list to pending */
    list->prev = pending;
    pending = list;
    list = list->next;
    pending->next = NULL;
    count++;
} while (list);

最後，將在 pending 裡面的東西全部接起來，然後把雙向鏈結串列的性質重新維護好。

list = pending;
pending = pending->prev;
for (;;) {
	struct list_head *next = pending->prev;
	if (!next)
		break;
	list = merge(priv, cmp, pending, list);
	pending = next;
}
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);

效能比較

首先在 qtest.c 中引入 PERFTEST 巨集，可以對指定函式與參數測試執行時經過的 cpucycles 數量。

#define PERFTEST(func, ...)  \
    ({                       \
        int64_t start, end;  \
        start = cpucycles(); \
        func(__VA_ARGS__);   \
        end = cpucycles();   \
        end - start;         \
    })

我將 list_sort 在傳入參數的部份做一定程度的改變後，做了這樣的測試。我將兩個 sort 函式傳進來後，在中間會交錯的呼叫 sort_test_once 測試兩個函式的時間，之所以交錯是因為要將環境因素盡可能相同。

static void sort_test(sort_t sort[2], int n)
{
	FILE *file[2];
	file[0] = fopen("file0.txt", "w");
	file[1] = fopen("file1.txt", "w");
	uint64_t data[NUMBER];
    for(int i = 0; i < NUMBER; i++)
        data[i] = file[i & 1], "%ld\n", sort_test_once(sort[i & 1], n);
	for(int i = 0; i < NUMBER; i++)
		fprintf(file[i & 1], "%ld\n", data[i]);
	fclose(file[0]);
	fclose(file[1]);
}

在 sort_test_once 中，會去使用 PERFTEST 巨集測量 sort 執行的 cpucycle

static uint64_t sort_test_once(sort_t sort, int n)
{
    char randstr_buf[10];
    struct list_head *tmp = q_new();
    for(int i = 0; i < n; i++){
        fill_rand_string(randstr_buf, sizeof(randstr_buf));
        q_insert_tail(tmp, randstr_buf);
    }
    element_t *entry, *safe;

    uint64_t ret = PERFTEST(sort, tmp, 0);

    list_for_each_entry_safe (entry, safe, tmp, list)
        assert(&safe->list == tmp || strcmp(entry->value, safe->value) <= 0);
    
    q_free(tmp);
    return ret;
}

我是另外寫了一個測試的檔案，在 main 中呼叫 sort_test。

int main()
{
    sort_test((sort_t[2]){q_sort, list_sort}, 10000);
}

這裡因為這個排序中間比較的是字串，所以比較慢，很難去對各種不同的

n

做測試，這裡使用

n = 10000

做 100 次測試，即使如此，還是肉眼可見的差異。可以看到，list_sort 幾乎都在

6 \times 10^{6}

個 CPU cycle 之內就執行完了。
sort

這裡同樣能用 t 檢定來驗證 q_sort 的執行時間母體平均比 list_sort 的執行時間長，但由於差異過於明顯，這裡不做這件事。

我將 list_sort 的合併方式放進 q_sort 中，但發現情況並沒有改善太多：
sort2

我將 list_sort 所使用的 merge 方式也移植進來了，發現效率有明顯的改善。
sort3

於是，以下來研究一下 linux 的 merge 和我的 q_merge_two 差在哪吧
經過反覆的測試，發現兩者效率的差異在以下這段程式碼（q_merge_two 中原本是寫三元運算子，但是由於效率差不多，這基於讓兩個程式比較的目的替換為 if-else）：

merge

if (((strcmp(str1, str2)) < 0) ^ descend) {
    *indir = head1;
    indir = &(*indir)->next;
    head1 = head1->next;
} else {
    *indir = head2;
    indir = &(*indir)->next;
    head2 = head2->next;
}

q_merge_two

struct list_head **it;
if (((strcmp(str1, str2)) < 0) ^ descend)
    it = &head1;
else    
    it = &head2;
*indir = *it;
indir = &(*indir)->next;
*it = *indir;

看程式碼可能沒有什麼感覺，這裡經過編譯後看一下指令次數的比較。（這裡會是基於這台機器上的編譯器來討論的）
我覺得說不定讀懂它可以看出些什麼，於是開始讀它。以下都會以 <+n> 表示相對於函式的偏移量是 n 的指令。

首先是 q_merge_two 的部份：

   0x6051ba1ebf75 <q_merge_two+17>:	mov    QWORD PTR [rsp+0x8],rdi
   0x6051ba1ebf7a <q_merge_two+22>:	mov    QWORD PTR [rsp],rsi
   ...
   0x6051ba1ebf9a <q_merge_two+54>:	lea    r13,[rsp+0x10]
   0x6051ba1ebf9f <q_merge_two+59>:	lea    r15,[rsp+0x8]
   0x6051ba1ebfa4 <q_merge_two+64>:	mov    r14,rsp
   ...
   0x6051ba1ebfac <q_merge_two+72>:	mov    rbp,QWORD PTR [rsp]
   ...

以下分段解釋：

rbp 和 rbx 存的分別是 head1 和 head2，對應的字串位置放到 rsi 和 rdi 中，strcmp 完後回傳值在 eax，將它右移 31 位。

   0x5f3b04a13fb5 <q_merge_two+81>:	mov    rsi,QWORD PTR [rbp-0x8]
   0x5f3b04a13fb9 <q_merge_two+85>:	mov    rdi,QWORD PTR [rbx-0x8]
   0x5f3b04a13fbd <q_merge_two+89>:	call   0x5f3b04a0e860 <strcmp@plt>
   0x5f3b04a13fc2 <q_merge_two+94>:	shr    eax,0x1f

如果看往最上面看，會發現 rsp 和 rsp + 8 這兩個位置所存的東西分別是 head1 和 head2（rsi、rdi），而中間又讓 r15 存著 rsp + 8，r14 存著 rsp。然後 r12b 是 r12 的低位，存的是 descend。這段程式碼會讓如果 descend == (strcmp(str1, str2) >> 31) 時，代表 head1 要放在前面， rbx 存著 head1 ，而 rdx 存著 head1 的記憶體位置。否則的話，他們本來就存著 head2 和存著 head2 的記憶體位置。

   0x5f3b04a13fc5 <q_merge_two+97>:	mov    rdx,r15
   0x5f3b04a13fc8 <q_merge_two+100>:	cmp    r12b,al
   0x5f3b04a13fcb <q_merge_two+103>:	cmove  rbx,rbp
   0x5f3b04a13fcf <q_merge_two+107>:	cmove  rdx,r14

r13 一直存的是 indir（一個在堆疊上的位置），首先在 <+111> 會先把 indir 所指向的值變成 rbx，也就是要插入的節點的記憶體位置，也就是 *indir = *it。在 <+115>，因為 rbx 存著一個 struct list_head 開頭的位置，所以 rbx + 8 這個位置存的是那個結構的 next，在這個指令把它存進 r13 中，也就是 indir = &(*indir)->next。<+119> 和 <+123> 做的就是 *it = *indir（結果上來說是這樣）。接下來把 rbx 回復成 rsp + 8 存的值。

   0x5f3b04a13fd3 <q_merge_two+111>:	mov    QWORD PTR [r13+0x0],rbx
   0x5f3b04a13fd7 <q_merge_two+115>:	lea    r13,[rbx+0x8]
   0x5f3b04a13fdb <q_merge_two+119>:	mov    rax,QWORD PTR [rbx+0x8]
   0x5f3b04a13fdf <q_merge_two+123>:	mov    QWORD PTR [rdx],rax
   0x5f3b04a13fe2 <q_merge_two+126>:	mov    rbx,QWORD PTR [rsp+0x8]

最後，這裡會看 rbx 是不是變 0，如果不是的話就繼續迴圈。

   0x5f3b04a13fe7 <q_merge_two+131>:	test   rbx,rbx
   0x5f3b04a13fea <q_merge_two+134>:	jne    0x5f3b04a13fac <q_merge_two+72>

數字方面，在 cmp 之下 test 之上共有 7 個指令。

接下來是 merge 的部份：
在 cmp 之後直接分成兩個分支。

   0x5bf39702bfbd <merge+89>:	mov    rsi,QWORD PTR [rbp-0x8]
   0x5bf39702bfc1 <merge+93>:	mov    rdi,QWORD PTR [rbx-0x8]
   0x5bf39702bfc5 <merge+97>:	call   0x5bf397026860 <strcmp@plt>
   0x5bf39702bfca <merge+102>:	shr    eax,0x1f
   0x5bf39702bfcd <merge+105>:	cmp    r13b,al
   0x5bf39702bfd0 <merge+108>:	je     0x5bf39702bfac <q_merge_two+72>

首先是第一個分支，r12 是 indir，<+110> 做的是 *indir = head2。<+114> 將 rbx + 8 這個值存入 r12 中，也就是 indir = &(*indir)->next。然後 <+118> 就是把 rbx + 8 所存的值，也就是 next ，存入 rbx，也就是 head2 = head2->next。

   0x5bf39702bfd2 <merge+110>:	mov    QWORD PTR [r12],rbx
   0x5bf39702bfd6 <merge+114>:	lea    r12,[rbx+0x8]
   0x5bf39702bfda <merge+118>:	mov    rbx,QWORD PTR [rbx+0x8]
   0x5bf39702bfde <merge+122>:	test   rbx,rbx
   0x5bf39702bfe1 <merge+125>:	jne    0x5bf39702bfbd <q_merge_two+89>

另一個分支就只是把上面的 head2 改成 head1 而已。

   0x5bf39702bfac <merge+72>:	mov    QWORD PTR [r12],rbp
   0x5bf39702bfb0 <merge+76>:	lea    r12,[rbp+0x8]
   0x5bf39702bfb4 <merge+80>:	mov    rbp,QWORD PTR [rbp+0x8]
   0x5bf39702bfb8 <merge+84>:	test   rbp,rbp
   0x5bf39702bfbb <merge+87>:	je     0x5bf39702bfa6 <q_merge_two+66>
   0x5bf39702bfbd <merge+89>:	mov    rsi,QWORD PTR [rbp-0x8]
   0x5bf39702bfc1 <merge+93>:	mov    rdi,QWORD PTR [rbx-0x8]

可以發現他在 cmp 之下 test 之上共用了 4 個指令，比起 q_merge_two 少了 3 個。而且如果去除掉 je 這個指令的話，它每行程式碼都用一個指令就完成了。

兩個程式的差異在 merge 中 rbp 和 rbx 從頭到尾分別都代表 head1 和 head2 中的同一個，而 q_merge_two 中，只有 rbx 會被拿來中間做操作，最後再去堆疊上把值（或新的值）取回來。另外，他的間接指標 it 是一個存著堆疊上位置的 rdx，可以透過修改 rdx 所存的位置上的值來修改 it 指向的位置的值。

雖然我不知道編譯器是怎麼做的，但是依照歸納可以得出一個結論，使用間接指標去合併兩個分支可能會造成負面效果，因為編譯器真的會去實現間接指標這件事，在這裡的處理方式是使用一個存著堆疊上記憶體位置的暫存器去修改堆疊上的值，再讓其他暫存器去堆疊上面取新的值，這樣會造成多餘的操作，除非編譯器有對此做特別的改良。

於是這裡把 q_sort 和 q_merge_two 都更新了。

Commit be13d7b
Commit bdc32dd

Eric Lin

2025/03/03 13:01:53

使用 list_for_each_safe 搭配 container_of 可以符合 Linux 核心中將 list_head 封裝在結構體中的實作風格

陳麒升

2025/03/03 14:03:42

如果要每次要走訪每個包含節點（list_head）的結構體都要使用 list_for_each_safe 再使用 list_entry 去取得結構體的話，那 list.h 中提供list_for_each_entry_safe 的目的是什麼？

2025/03/03 14:13:18

會這樣寫是因為當我在閱讀被提供的文件時，並沒有發現到相關的規範，只有提供在 list.h 中的各種函數與巨集的說明，於是我選擇了可以使用這些巨集情況下最少行數的方法。 https://www.kernel.org/doc/html/latest/core-api/kernel-api.html (Edited)

2025q1 Homework1 (lab0)

Reviewed by salmoniscute

開發環境

針對佇列操作的程式碼實作

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_entry

q_free

q_delete_mid

q_swap

q_reverse

q_merge_two

q_sort

q_delete_dup

q_descend

q_reverseK

q_merge

q_descend_ascend

q_descend_ascend

q_descend

q_ascend

亂數

shuffle 命令實作

統計方式驗證 shuffle

1. 計算卡方值

2. 決定自由度

3. 選擇顯著水準

4. 結論

熵（Entropy）

論文〈Dude, is my code constant time?〉

閱讀論文

程式碼分析

程式碼改善

Linux 核心的鏈結串列排序

操作流程

實作方式

效能比較

Read more

Linux 核心的紅黑樹程式碼解讀

kxo

如何 debug riscv 架構的 user program

2025q1 Homework2 (quiz1+2)

Reviewed by `salmoniscute`