2025q1 Homework1 (lab0)

contributed by < tsaiiuo >

作業書寫規範:

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

開發環境

$ uname -a
Linux iantsai-P30-F5 6.8.0-41-generic #41-Ubuntu SMP PREEMPT_DYNAMIC Fri Aug  2 20:41:06 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux

$ 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):                   8
  On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
    CPU family:           6
    Model:                94
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             3
    CPU(s) scaling MHz:   52%
    CPU max MHz:          4000.0000
    CPU min MHz:          800.0000
    BogoMIPS:             6799.81
    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 sysc
                          all nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pcl
                          mulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadli
                          ne_timer xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb pti ssbd ibrs ibpb stibp tpr_shadow flexpriority ep
                          t vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec x
                          getbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp vnmi md_clear flush_l1d arch_capabilities
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    128 KiB (4 instances)
  L1i:                    128 KiB (4 instances)
  L2:                     1 MiB (4 instances)
  L3:                     8 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-7
Vulnerabilities:          
  Gather data sampling:   Vulnerable: No microcode
  Itlb multihit:          KVM: Mitigation: VMX disabled
  L1tf:                   Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable
  Mds:                    Mitigation; Clear CPU buffers; SMT vulnerable
  Meltdown:               Mitigation; PTI
  Mmio stale data:        Mitigation; Clear CPU buffers; SMT vulnerable
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; IBRS
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:             Mitigation; IBRS; IBPB conditional; STIBP conditional; RSB filling; PBRSB-eIBRS Not affected; BHI Not affected
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Mitigation; TSX disabled

開發指定的佇列操作

`q_new`

commit 8becfda

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

    return head;
}

利用malloc配置一個新的head，並在INIT_LIST_HEAD前檢查是否配置記憶體成功。
配置成功，則配合INIT_LIST_HEAD去初始化 head 的指標。

`q_free`

commit 0e39ef3

void q_free(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node = NULL;
    struct list_head *safe = NULL;
    list_for_each_safe (node, safe, head) {
        element_t *curr = list_entry(node, element_t, list);
        q_release_element(curr);
    };
    free(head);
    return;
}

透過list_for_each_safe這個功能走訪整個佇列，並對各個佇列成員透過list_entry獲取屬於佇列成員的 element_t 指標，再透過q_release_element配合獲取到的 element_t 指標釋放記憶體位置，最後再釋放 head。

`q_insert_head`

commit 3c17bdc

bool q_insert_head(struct list_head *head, char *s)
{
    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(&(new_element->list), head);
    return true;
}

利用malloc配置一個新的 element_t ，透過strdup複製 s 字串回傳新的記憶體指標給 element_t ，但同時strdup若配置失敗會回傳 NULL ，因此需檢查是否配置成功，配置成功的話再透過list_add這個功能新增新配置的 element_t 增至佇列的 head。

commit e536ea3

if (!head || !s)
    return false;

新增檢查 head 和 s 合不合法。

`q_insert_tail`

commit fc15053

bool q_insert_tail(struct list_head *head, char *s)
{
    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_insert_head的操作一樣，只是最後是使用list_add_tail功能將新配置的 element_t 增至佇列的 tail。

commit e536ea3

if (!head || !s)
    return false;

新增檢查 head 和 s 合不合法。

`q_remove_head`

commit 91c88ba

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    element_t *remove_element = list_entry(head->next, element_t, list);
    list_del(head->next);

    if (sp) {
        strncpy(sp, remove_element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return remove_element;
}

先透過 head->next 和list_entry找出對應的 element_t ，再利用list_del刪除 head->next ，最後利用strncpy將 element_t 的字串複製到 sp 中，最後再將最後一個字元補上 \0 。

commit 835819e

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

新增檢查 head 合不合法，並且透過list_empty檢查是否佇列為空。

`q_remove_tail`

commit 5d117c0

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    element_t *remove_element = list_entry(head->prev, element_t, list);
    list_del(head->prev);
    
    if (sp) {
        strncpy(sp, remove_element->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return remove_element;
}

先透過 head->prev 和list_entry找出對應的 element_t ，再利用list_del刪除 head->prev ，最後利用strncpy將 element_t 的字串複製到 sp 中，最後再將最後一個字元補上 \0 。

commit 835819e

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

新增檢查 head 合不合法，並且透過list_empty檢查是否佇列為空。

`q_size`

commit e6e724f

int q_size(struct list_head *head)
{
    if (!head) {
        return 0;
    }

    int len = 0;
    struct list_head *node = NULL;

    list_for_each (node, head) {
        len++;
    };

    return len;
}

利用list_for_each進行 len 的運算。

`q_size`

commit e6e724f

int q_size(struct list_head *head)
{
    if (!head) {
        return 0;
    }

    int len = 0;
    struct list_head *node = NULL;

    list_for_each (node, head) {
        len++;
    };

    return len;
}

利用list_for_each進行 len 的運算。

`q_delete_mid`

commit 59e0c83

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *slow = head->next;
    struct list_head *fast = head->next;
    for (; fast != head && fast->next != head;
         fast = fast->next->next, slow = slow->next) {
    }

    list_del(slow);
    element_t *mid = list_entry(slow, element_t, list);
    q_release_element(mid);
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    return true;
}

利用快慢指標找到位於中間的元素，再進行list_del和q_release_element移除該元素和釋放記憶體。

`q_delete_dup`

commit 137350d

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *curr = head->next;
    struct list_head *curr_next = NULL;
    for (; curr != head;) {
        bool check = false;
        const char *value = list_entry(curr, element_t, list)->value;
        for (curr_next = curr->next; curr_next != head;) {
            element_t *next_node = list_entry(curr_next, element_t, list);
            if (strcmp(value, next_node->value) == 0) {
                struct list_head *temp = curr_next->next;
                list_del(curr_next);
                q_release_element(next_node);
                curr_next = temp;
                check = true;
            } else {
                break;
            }
        }
        if (check) {
            element_t *curr_node = list_entry(curr, element_t, list);
            list_del(curr);
            q_release_element(curr_node);
            curr = curr_next;
            continue;
        }
        curr = curr->next;
    }
 
    return true;
}
}

利用 curr 去儲存當下檢查字串的指標，並使用 curr_next 去檢查兩個指標的數值是否相等，若相等透過list_del和q_release_element去釋放記憶體和刪除該元素，不相等則檢查是否有兩個指標相等的紀錄，有的話需要刪除 curr 這個元素。

`q_swap`

commit 9c086e5

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *curr = head->next;
    while (curr != head && curr->next != head) {
        struct list_head *temp = curr;
        list_move(curr, temp->next);
        curr = curr->next;
    }
    // https://leetcode.com/problems/swap-nodes-in-pairs/
}

利用 curr 去儲存兩點交換的第一個元素，並利用list_move將 curr 移動到原先 curr 的下一個指標，交換後的 curr 的下一個指標就會是原先 curr 的下下個指標。

因此curr = curr->next配合迴圈可以實現兩兩交換。

`q_reverse`

commit e17ab56

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return;
    }
    struct list_head *temp;
    for (struct list_head *next_ptr = head->next->next; next_ptr != head;
         next_ptr = temp) {
        temp = next_ptr->next;
        list_move(next_ptr, temp);
    }
}

這邊是list_move(next_ptr, head)，我那時候打錯了，也沒檢查過功能就 push 上來，深刻檢討不會再犯。
透過將第二個點之後的每個點利用list_move移動到 head 之後這樣就能完成佇列反轉。

commit 4367ac9

void q_reverse(struct list_head *head)
{
    struct list_head *curr, *safe;
    list_for_each_safe (curr, safe, head) {
        list_move(curr, head);
    }
}

改用list_for_each_safe對每個點移動到 head 之後，這樣寫法更精簡。

`q_reverseＫ`

commit f09418a

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || k == 1 || list_empty(head)) {
        return;
    }
    struct list_head *curr, *safe;
    struct list_head *temp = head;
    LIST_HEAD(dummy);
    int count = 0;
    list_for_each_safe (curr, safe, head) {
        count++;
        if (count == k) {
            list_cut_position(&dummy, temp, curr);
            q_reverse(&dummy);
            count = 0;
        }
        temp = safe->prev;
    }
}

commit 6e2e5ec
這邊commit message寫錯了，沒提到fix q_reverseK

if (count == k) {
    list_cut_position(&dummy, temp, curr);
    q_reverse(&dummy);
+   list_splice_init(&dummy, temp);
    count = 0;
}

透過list_cut_position將每 k 個元素轉移致一個 dummy 佇列上，進行反轉後再透過list_splice_init插入致 temp 後。

`merge sort using merge_two_queue`

commit 8c1b2f5

/* Merge two list */
struct list_head *merge_two_queue(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL;
    struct list_head **indirect = &head;

    for (; L1 && L2; indirect = &(*indirect)->next) {
        if (strcmp(list_entry(L1, element_t, list)->value,
                   list_entry(L2, element_t, list)->value) > 0) {
            (*indirect) = L1;
            L1 = L1->next;
        } else {
            (*indirect) = L2;
            L2 = L2->next;
        }
    }
    *indirect = (struct ListNode *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}
/* Use merge_two_queue to implement mergesort */
struct list_head *merge_sort_queue(struct list_head *head)
{
    if (!head || list_empty(head))
        return head;


    struct list_head *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }


    struct list_head *mid = slow->next;
    slow->next = NULL;


    struct list_head *left = mergeSortList(head);
    struct list_head *right = mergeSortList(mid);


    return merge_two_queue(left, right);
}

先前我實作你所不知道的 C 語言: linked list 和非連續記憶體中的程式碼，在這邊直接拿來用，透過雙指標的操作實做merge_two_queue再透過遞迴達成merge_sort_queue。

commit bc8a940
這邊 commit message 應該為 Fix 而非 Implement

merge_two_queue

-   *indirect = (struct ListNode *) ((uintptr_t) L1 | (uintptr_t) L2);
+   *indirect = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);

更改為正確的資料結構。

merge_sort_queue

-   struct list_head *left = mergeSortList(head);
-   struct list_head *right = mergeSortList(mid);
+   struct list_head *left = merge_sort_queue(head);
+   struct list_head *right = merge_sort_queue(mid);

更改為正確的函式名稱。

commit fdc9a03

merge_two_queue

for (; L1 && L2; indirect = &(*indirect)->next) {
    if (strcmp(list_entry(L1, element_t, list)->value,
-                  list_entry(L2, element_t, list)->value) > 0) {
+                  list_entry(L2, element_t, list)->value) <= 0) {
        (*indirect) = L1;
        L1 = L1->next;
    } else {
        (*indirect) = L2;
        L2 = L2->next;
    }
}

更改為降序排列

merge_sort_queue

-if (!head || list_empty(head))
+if (!head || !head->next)

結束條件應檢查 head->next 而非 head 是否為空

`q_sort`

commit edff487

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return;
    head->prev->next = NULL;
    head->next = merge_sort_queue(head->next);
    struct list_head *start = head;

    for (; start->next; start = start->next) {
        start->next->prev = start;
    }
    start->next = head;
    head->prev = start;
    if (!descend)
        q_reverse(head);
}

一開始想說利用merge_sort_queue進行降序排列，再透過判斷 descend 去進行反轉佇列，但這樣假設進行升序排列會耗費多餘的時間。

commit fdc9a03

參考 Jackiempty

-   struct list_head *start = head;

-   for (; start->next; start = start->next) {
-       start->next->prev = start;
-   }
+if (!descend) {
+        struct list_head *prev = head, *curr = head->next;
+        while (curr) {
+            curr->prev = prev;
+            prev = curr;
+            curr = curr->next;
+        }
+        prev->next = head;
+        head->prev = prev;
+    } else {
+        struct list_head *prev = head, *curr = head->next,
+                         *next = head->next->next;
+        while (next) {
+            curr->next = prev;
+            curr->prev = next;
+            prev = curr;
+            curr = next;
+            next = next->next;
+        }
+        curr->next = prev;
+        curr->prev = head;
+        head->next = curr;
+        head->prev = head->next;
+    }
-    start->next = head;
-    head->prev = start;
-    if (!descend)
-        q_reverse(head);

原先是透過迴圈將每一個的 prev 連結上再進行後續的佇列反轉，現在更改為在merge_sort_queue後，直接根據 descend 的值進行 descend/ascend 正確方向的連結，無需額外的佇列反轉。

`q_ascend`

commit aa7c8c7

int q_ascend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    struct list_head *p = head->next, *pp = p->next;
    for (; pp != head; pp = pp->next) {
        element_t *temp = list_entry(pp, element_t, list);
        if (strcmp(temp->value, list_entry(p, element_t, list)->value) < 0) {
            list_del(pp);
            q_release_element(temp);
        } else {
            p = pp;
        }
    }
    return q_size(head);
}

原先希望透過前後指標檢查大小，若後指標的 value 字典序比前指標小，刪除後指標並釋放，但我這樣的寫法會導致先釋放指標後，下一輪迴圈就無法透過原先的指標進行下一輪的判斷，
因為指標被提早釋放了。

commit 6e2e5ec

-    struct list_head *p = head->next, *pp = p->next;
-    for (; pp != head; pp = pp->next) {
-        element_t *temp = list_entry(pp, element_t, list);
-        if (strcmp(temp->value, list_entry(p, -element_t, list)->value) < 0) {
-            list_del(pp);
-            q_release_element(temp);
-        } else {
-            p = pp;
-        }
+    struct list_head *p = head->next;
+    element_t *p_ele = list_entry(p, element_t, list);
+    while (p_ele->list.next != head) {
+        element_t *pp_ele = list_entry(p_ele->list.next, element_t, list);
+        if (strcmp(pp_ele->value, p_ele->value) < 0) {
+            list_del(&pp_ele->list);
+            q_release_element(pp_ele);
+        } else {
+            p = pp;
+            p_ele = pp_ele;
+        }
+    }

更新為透過 element_t 為單位進行迴圈判斷，並且現在是以前指標的下一個指標作為終止條件，就不會有後指標被釋放後找不到的問題。

`q_descend`

commit aa7c8c7

與q_ascend的作法相同，只需將 next 改為 prev。

commit 6e2e5ec

與q_ascend的作法相同，只需將 next 改為 prev。

`q_merge`

commit 023261e

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;
    struct list_head *f_ptr = list_entry(head->next, queue_contex_t, chain)->q;
    for (struct list_head *c = head->next->next; c != head; c = c->next) {
        queue_contex_t *n = list_entry(c, queue_contex_t, chain);
        list_splice_init(n->q, f_ptr);
        n->size = 0;
    }
    queue_contex_t *f = list_entry(head->next, queue_contex_t, chain);
    q_sort(f_ptr, descend);
    f->size = q_size(f_ptr);
    
    return f->size;
}

將多個佇列的串列的第一個元素當作後續連結所有佇列的第一個元素，並透過多個佇列的串列的指標配合迴圈將各個佇列利用list_spoce_init進行連結，並且更新 size 為 0 ，最後再將連結所有佇列的指標去執行先前創建的函式q_sort。

亂數實做+分析

實做 shuffle 功能

使用 Fisher–Yates shuffle 來實做洗牌，主要利用 rand 函式隨機找出洗牌對象，再讓洗牌對象與 tail 做互換。

commit bcf3096

void q_shuffle(struct list_head *head)
 {
     int len = q_size(head);
     if (len <= 1)
         return;
     struct list_head *curr = head->prev;
     struct list_head *prev = NULL;
     for (int i = len - 1; i > 0; i--) {
         int ran = rand() % (i + 1);
         struct list_head *node;
         list_for_each(node, head) {
             if (ran == 0)
                 break;
             ran--;
         }
         prev = node->prev;
         list_move(node, curr);
         list_move(curr, prev);
         curr = node->prev;
     }
 }

首先在 queue.c 中創建q_shuffle函式，利用list_for_each搭配list_move，完成尾巴的元素與被隨機挑選到的元素進行互換，總共做佇列長度-1次。

+ extern void q_shuffle(struct list_head *head);

由於沒有更改 queue.h ，因此需要在 qtest.c 中透過 extern 獲取 q_shuffle 函式。

static bool do_shuffle(int argc, char *argv[])
 {
     if (argc != 1) {
         report(1, "%s takes no arguments", argv[0]);
         return false;
     }
 
     if (!current || !current->q)
         report(3, "Warning: Calling shuflle on null queue");
     error_check();
 
     set_noallocate_mode(true);
     if (current && exception_setup(true))
         q_shuffle(current->q);
     exception_cancel();
 
     set_noallocate_mode(false);
     q_show(3);
     return !error_check();
 }

在 qtest.c 中創建do_shuffle函式，並且與其他 qtest.c 內的函式一樣先檢查 argc 和 current 的合法性，確認合法後執行q_shuffle。

+ ADD_COMMAND(shuffle, "Shuffle the queue by Fisher Yates algorithm", "");

在 qtest.c 中透過 ADD_COMMAND 巨集新增指令。

分析亂數實做結果

commit 3b08440

首先參考2025 年 Linux 核心設計課程作業 —— lab0 (D)中提供的 code 進行擴充，額外呈現了 p-value 和 Chi-square-stat 的結果圖表。
測試設定為對長度為4的佇列進行1000000次的 shuffle 查看結果的分布狀況是否符合預期。

執行完後的統計結果如下：

串列組合	測試的頻率	期望的頻率	串列組合	測試的頻率	期望的頻率
1 2 3 4	41941	41667	3 1 2 4	41408	41667
1 2 4 3	41817	41667	3 1 4 2	41481	41667
1 3 2 4	41668	41667	3 2 1 4	41787	41667
1 3 4 2	41554	41667	3 2 4 1	41816	41667
1 4 2 3	41731	41667	3 4 1 2	41615	41667
1 4 3 2	41557	41667	3 4 2 1	41646	41667
2 1 3 4	41634	41667	4 1 2 3	41781	41667
2 1 4 3	41695	41667	4 1 3 2	41882	41667
2 3 1 4	41714	41667	4 2 1 3	41475	41667
2 3 4 1	41772	41667	4 2 3 1	41531	41667
2 4 1 3	41712	41667	4 3 1 2	41537	41667
2 4 3 1	41738	41667	4 3 2 1	41508	41667

Shuffle_Result_Distribution

Chi-square sum:  10.725536
Degrees of freedom:  23
p-value:  0.9858176742388471

參考 Victor FU 所提供的卡方分佈表

根據卡方分布表，在自由度為 23 的情況下，所得的 P-value 值介於 0.97 到 0.99 之間，遠大於常見的顯著性水準 P = 0.05。因此，我們無法拒絕虛無假設（

𝐻 0

），表示目前的測試樣本不足以證明 shuffle 的結果並非均勻分布這可能是因為測試次數不足，意味著樣本資料不拒絕 shuffle 函式的結果，或是 shuffle 函式本身確實為 Uniform distribution 。此外，從上方長條圖可見，24項數據之間的差異不大，整體分佈較接近常態分布。

Chi-square_Distribution
藉由 chi2 將卡方分佈視覺化，p-value = 0.986 代表：如果真的是服從這個卡方分布，出現「比 10.73 更大」的統計量的機率有 98.6%。這次測試的結果，卡方統計量 10.73 在這個分布下是「很常見」的（因為有 98.6% 的機率可以比它更大），並不算是一個「極端值」。

亂度

What is random?

這邊在閱讀完2025 年 Linux 核心設計課程作業 —— lab0 (D)可以得出老師所講述的結論是

每個隨機事件的發生機率相同
每個事件發生的機率互相獨立

How to measure the randomness?

利用 Entropy 來衡量亂度

S = - \sum_{i = 1}^{n} P (x_{i}) l o g_{b} P (x_{i})

Entropy 的數學意義是某個隨機事件的每個結果發生時所能傳達出的資訊量，我覺得更好的李解釋隨機變數各個可能結果的平均信息量。

詳細解釋是隨著事件發生的可能性越大，該事件所傳達的訊息越少，這也對映著 Entropy 內

P (x_{i})

- l o g_{b} P (x_{i})

兩者的關係。

利用 `ent` 和 Linux 內建的 `/dev/random` 實做

一步步執行以下程式碼

$ head -c 2048 /dev/random > random.txt

$ yes "ian" | head -c 2048 > nonrandom.txt

$ ent random.txt
Entropy = 7.906482 bits per byte.

Optimum compression would reduce the size
of this 2048 byte file by 1 percent.

Chi square distribution for 2048 samples is 269.00, and randomly
would exceed this value 26.16 percent of the times.

Arithmetic mean value of data bytes is 124.6680 (127.5 = random).
Monte Carlo value for Pi is 3.343108504 (error 6.41 percent).
Serial correlation coefficient is -0.035103 (totally uncorrelated = 0.0).

$ ent nonrandom.txt
Entropy = 2.000000 bits per byte.

1 byte char 的大小為

2^{8}

，而Entropy 的極大值發生在

P (x_{1}) = P (x_{2}) = . . . = P (x_{n}) = \frac{1}{n}

時

(S = l o g_{b} n)

，則最大的 entropy 為

S = \log_{2} (2^{8}) = 8

，可觀察到這次取出的結果 7.906… 相當接近這個理論值。

也可以觀察若將值域設在 ian 則理論上要是這表示每次產生一個字元時平均能傳達大約 2 個位元的資訊量，因為 yes "ian" 除了 ian 之外還會產生 \0 換行
，所以實際上是4個字元，而這次 Entropy 的結果也確實是2，符合理論。

接下來用卡方來檢驗我們的資料是否符合 Uniform distrubution，卡方檢定的虛無假設如下

H_{0} : p_{i} = p_{i 0}, i = 1, . . ., k

H_{1} : 不 是 所 有 p_{i} 都 等 於 p_{i 0}

在自由度為 2047 的情況下，所得的 P-value 值為 1 ，遠大於常見的顯著性水準 P = 0.05。因此，我們無法拒絕虛無假設（

𝐻 0

）

from scipy import stats
a = 1 - stats.chi2.pdf(269.00, 2047)
print(a)

>>1.0

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

論文提出一套量測標準 dudect ，來測量是否程式能在常數時間完成，主要有下貢獻:

不依賴靜態分析，而是依靠對目標平台上執行時間測量的統計分析。避免對底層硬體(CPU)的架構問題。
借用了硬體側信道領域中的概念並將其應用到量測的情境中。具體來說，方法是基於洩漏檢測測試。

TIMING LEAKAGE DETECTION

該如何準確的執行 TIMING LEAKAGE DETECTION ，根據論文又能歸納為幾個步驟

利用 cycle counters 進行測量執行時間的計算
分為分別用兩類(class) input data ，論文中提到的是 fix-vs-random ， fixed class 是為了 corner-case

Typically, in a fix-vs-random leakage detection
test, the first class input data is fixed to a constant value,
and the second class input data is chosen at random for each
measurement. The fixed value might be chosen to trigger certain
“special” corner-case processing
要進行後處理，因為典型的計時分佈往往呈現正偏斜，這可能是由於測量產生的假象、主進程被作業系統中斷或其他外部活動所引起，因此後處理就是捨棄超過某個固定且與類別無關閾值的測量數據，來提升量測的正確性。
統計測試，在這邊使用 Welch’s t-test ，老師也有詳細介紹，這裡就不寫了。

觀察 dudect 的原始碼並修改

一步步觀察原始碼

/*
set different thresholds for cropping measurements.
the exponential tendency is meant to approximately match
the measurements distribution, but there's not more science
than that.
*/

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

這邊註解有詳細說明這程式碼的用意，主要是針對 cropping 的量測制定不同的標準，但這裡也有說明目前是使用指數趨勢能大致吻合量測的分佈，但沒有更多的科學支持。

這個程式碼也在 dudect_main 中有做使用

dudect_state_t dudect_main(dudect_ctx_t *ctx) {
  prepare_inputs(ctx->config, ctx->input_data, ctx->classes);
  measure(ctx);

  bool first_time = ctx->percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;

  dudect_state_t ret = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
  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);
  }

  return ret;
}

根據註解可以知道他是想要將第一批量測修正，根據數據的分佈來排除極端值，因為先前提到的正偏斜的關係。

除此之外在更新統計值的函式，也沒有採計前幾個量測，以提高準確度。

static void update_statistics(dudect_ctx_t *ctx) {
  for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {
    int64_t difference = ctx->exec_times[i];

    if (difference < 0) {
      continue; // the cpu cycle counter overflowed, just throw away the measurement
    }

    // t-test on the execution time
    t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]);

    // t-test on cropped execution times, for several cropping thresholds.
    for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
      if (difference < ctx->percentiles[crop_index]) {
        t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
      }
    }

    // second-order test (only if we have more than 10000 measurements).
    // Centered product pre-processing.
    if (ctx->ttest_ctxs[0]->n[0] > 10000) {
      double centered = (double)difference - ctx->ttest_ctxs[0]->mean[ctx->classes[i]];
      t_push(ctx->ttest_ctxs[1 + DUDECT_NUMBER_PERCENTILES], centered * centered, ctx->classes[i]);
    }
  }
}

commit eb76706

看完原始碼之後就開始對我們原先 fixture.c 的更改，首先先創建 prepare_percentiles 相關的函式，並且修改為正確的資料結構，接著跟原始碼一樣捨棄前幾個量測，最後在 doit 函式中使用 prepare_percentiles 。

2025q1 Homework1 (lab0)

開發環境

開發指定的佇列操作

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseＫ

merge sort using merge_two_queue

q_sort

q_ascend

q_descend

q_merge

亂數實做+分析

實做 shuffle 功能

分析亂數實做結果

亂度

What is random?

How to measure the randomness?

利用 ent 和 Linux 內建的 /dev/random 實做

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

TIMING LEAKAGE DETECTION

觀察 dudect 的原始碼並修改

Read more

2025q1 Homework2 (quiz1+2)

2025q1 Homework1 (ideas)

`q_new`

`q_free`

`q_insert_head`

`q_insert_tail`

`q_remove_head`

`q_remove_tail`

`q_size`

`q_size`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseＫ`

`merge sort using merge_two_queue`

`q_sort`

`q_ascend`

`q_descend`

`q_merge`

利用 `ent` 和 Linux 內建的 `/dev/random` 實做