2025q1 Homework1 (lab0)

contributed by < Max042004 >

Review by Denny0097

commits 格式不一致

只有 commit 915f77 的 title 在最後加上 "in queue.c"，
而在 c0bc6e8 ~ a372995 的 commits 都有另外加上 "functions"，建議統一。
整體很完整，已收藏，感謝。

Review by rota1001

1. 在 q_new 的實作中，根據 CONTRIBUTTING.md，使用 early return 技巧把 if 中的程式碼搬出來可以讓程式碼更簡潔。
2. 在 q_delete_mid 中，可以發現要移除的東西永遠和 backward 相同，所以可以把兩者合併。

list_for_each_safe (forward, n_forward, head) {
    if (forward == backward || n_forward == backward) {
        tmp = list_entry(backward, element_t, list);
        list_del(backward);
        q_release_element(tmp);
        break;
    }
    backward = backward->prev;
}

作業書寫規範:

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

開發環境

$ 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):                   4
  On-line CPU(s) list:    0-3
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz
    CPU family:           6
    Model:                142
    Thread(s) per core:   2
    Core(s) per socket:   2
    Socket(s):            1
    Stepping:             9
    CPU(s) scaling MHz:   27%
    CPU max MHz:          3600.0000
    CPU min MHz:          400.0000
    BogoMIPS:             4599.93
    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 art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmp
                          erf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtp
                          r pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx 
                          f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb pti ssbd ibrs ibpb stibp 
                          tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2
                           erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 x
                          saves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp vnmi md_cle
                          ar flush_l1d arch_capabilities
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    64 KiB (2 instances)
  L1i:                    64 KiB (2 instances)
  L2:                     512 KiB (2 instances)
  L3:                     4 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-3
Vulnerabilities:          
  Gather data sampling:   Mitigation; 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

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

目前總分95，trace17未通過

q_new

    struct list_head *q_new()
{
    struct list_head *new_q = malloc(sizeof(struct list_head));

    if (new_q) {
        INIT_LIST_HEAD(new_q);
        return new_q;
    } else
        return new_q;
}

以 malloc 分配記憶體，用 INIT_LIST_HEAD 初始化雙向鏈結串列的 head ，使其指標均指向自己
然而另一個巨集 LIST_HEAD 也能建立並初始化一個 struct list_head 的物件，那為什麼不能使用巨集 LIST_HEAD 來建立一個 list_head 呢？ 從 Leorium 的解釋得知了答案，因為 LIST_HEAD 所建立的物件屬於 q_new 的 stack memory，所以一旦離開 q_new 後，所屬的 stack memory 被釋放後就無法再存取。

q_free

void q_free(struct list_head *head)
{
    if (!head)
        return;

    element_t *curr = NULL, *n;
    list_for_each_entry_safe (curr, n, head, list) {
        list_del(&curr->list);
        q_release_element(curr);
    }
    free(head);
}

走訪每一個節點並一一釋放記憶體的方法，要使用 list_for_each_entry_safe 而非 list_for_each_entry ，因為後者會在走訪上一個節點之後才存取下一個節點的地址，因此當我釋放上一個節點後，就無法存取下一個節點的地址。而前者會在走訪上一個節點的時候就先存取下一個節點的地址，避免了存取不到地址的問題。

走訪的過程用 q_release_element 釋放記憶體，因為 element_t 的成員包含指向佔有記憶體空間的字串指標，因此需要先釋放字串的記憶體才可以釋放 element_t 的記憶體，否則會造成字串的記憶體洩漏。此外 q_release_element 使用 test_free 對記憶體做更多必要的檢查和防護機制，防止不當的釋放行為，也能在發現記憶體被修改時發出警告，並透過一個雙向鏈結串列紀錄使用的記憶體。這樣的設計在除錯和檢測記憶體洩漏或損壞時非常有用。

因為 list_for_each_entry_safe 並不會走訪 head，所以最後需要特別釋放 head ，在 commit 7833122 引入 harness.h ， free 會自動替換成 test_free 。

q_insert_head

bool q_insert(struct list_head *head,
              const char *s,
              void (*op)(struct list_head *, struct list_head *))
{
    if (!head || !s)
        return false;

    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;

    new_element->value = strdup(s);
    if (!new_element->value) {
        free(new_element);
        return false;
    }
    op(&new_element->list, head);
    /* cppcheck-suppress memleak */
    return true;
}

bool q_insert_head(struct list_head *head, char *s)
{
    return q_insert(head, s, list_add);
}

藉由實作 q_insert 減少重複的程式碼，參考楊志璿的作法，使用函式指標減少多餘的if-else判斷。而後來 commit 的時候出現 cppcheck memleak 的警告， cppcheck 以為這塊記憶體之後無法再被存取，但實際上透過 list_add 將節點連接上雙向鏈結串列以後，可以經由前後節點的指標存取到，所以並不是記憶體洩漏。參考陳麒升的作法加上 cppcheck-suppress memleak
引入 harness.h 以後， strdup 會被 test_strdup 取代，差別是後者在實作中分配記憶體時呼叫 test_malloc
後來在做第二周作業的時候，回過頭來改善程式碼時，從陳麒升提示，發現 harness 是用來在測試階段引入用來快速偵錯的，不能把include harness push 到上去。
後續跟 Leorium 的討論中，嘗試將 queue.h 中 include harness.h 移除，測試看看 harness 裡面的 test_malloc 和 test_test 對於效能的影響，於是使用 Valgrind Massif 工具測量記憶體用量與執行時間。我同樣測量之前測過 trace 14

可以看到與之前記憶體用量相比，用量少了大概 1/3 ，但時間也有減少

n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
68    300,406,603       61,285,272       30,161,187    31,124,085            0
69  1,181,674,062       61,285,272       30,161,187    31,124,085            0

然而 commit hook 限制不得更改 .h 的檔案，所以我不確定 harness 的使用範圍是？

q_insert_tail

Commit 7dd8042

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 *tmp;
    tmp = list_first_entry(head, element_t, list);
    if (sp)
        snprintf(sp, bufsize, "%s", tmp->value);
    list_del(&tmp->list);
    return tmp;
}

先使用 snprintf 複製字串 。
之後要比較 snprintf 和 strncpy, memcpy 的差異性

q_remove_tail

將 list_first_entry 改為 list_last_entry ，其他部分一樣。

q_size

commit b458c98

用 list_for_each 走訪每一個節點的同時用 len 紀錄節點數目

q_delete_mid

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

    element_t *tmp;
    struct list_head *forward, *n_forward, *backward = head->prev;

    list_for_each_safe (forward, n_forward, head) {
        if (forward == backward) {
            tmp = list_entry(forward, element_t, list);
            list_del(forward);
            q_release_element(tmp);
            break;
        } else if (n_forward == backward) {
            tmp = list_entry(n_forward, element_t, list);
            list_del(n_forward);
            q_release_element(tmp);
            break;
        }
        backward = backward->prev;
    }
    return true;
}

用兩個指標，forward 從head 的下一個節點為起點順著走訪每一個節點，backward 從head 的上一個節點為起點逆著走訪每一個節點，forward 使用list_for_each_safe走訪，用 n_forward 儲存 forward 的下一個節點。當 forward 和 backward 指向同一個節點時，此節點為佇列最中間的節點，用 list_entry 取得容器結構體的地址，先將節點移除再釋放記憶體；當節點個數為偶數的時候，處理的是 backward 和 n_forward 同時指向的節點。

q_delete_dul

後續使用三元運算子改善了 if-else 中重複的程式碼

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

    element_t *curr = NULL, *next = NULL;
-   bool dul = false;
-   list_for_each_entry_safe (curr, next, head, list) {
-       if (curr->list.next != head && strcmp(curr->value, next->value) == 0) {
-           list_del(&curr->list);
-           q_release_element(curr);           dul = true;        } 
-       else if (dul) {
-           list_del(&curr->list);
-           q_release_element(curr);
-           dul = false;
-        }
-    }
+    element_t *curr = NULL, *next = NULL;
+    bool dul = false, is_same = false;
+    list_for_each_entry_safe(curr, next, head, list) {
+        is_same = (curr->list.next != head && strcmp(curr->value, next->value) == 0)? true : false;
+        if (is_same || dul) {
+            list_del(&curr->list);
+            q_release_element(curr);
+        }
+        dul = is_same;


    return true;
}

q_reverse

Commit 77a1c13

q_reverseK

起初作法用 i 記錄目前走訪的是第幾個節點，然後對以 k 為模對 i 取餘數

void q_reverseK(struct list_head *head, int k)
{
...
int i = 0
list_for_each_safe (curr, next, head) {
        i++;
        if (i % k == 0) {
            list_cut_position(&dummy, tmp, curr);
            q_reverse(&dummy);
            list_splice_init(&dummy, tmp);
            tmp = next->prev;
        }
    }
}

後來參考komark06的作法，發現上述作法在累加 i 的過程可能造成溢位，所以改以 i==k 比對，並在每一次比對後將 i 設為0，以避免整數潛在的溢位風險

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head) || k < 1)
        return;
    struct list_head *curr, *next, *tmp = head;
    int i = 0;

    LIST_HEAD(dummy);

    list_for_each_safe (curr, next, head) {
        i++;
        if (i == k) {
            list_cut_position(&dummy, tmp, curr);
            q_reverse(&dummy);
            list_splice_init(&dummy, tmp);
            tmp = next->prev;
            i = 0;
        }
    }
}

q_swap

Commit 77a1c13

採用老師上課講解的作法， q_swap 為 reverseK 在 k = 2 的特例

q_sort

起初參照你所不知道的 C 語言: linked list 和非連續記憶體中遞迴版的 Quick sort 實作，但後來發現測試要求是 stable sort ，所以改為 merge sort
實作一個 helper function _merge 依照升序或降序合併兩個鏈結串列。
然而卻無法通過 trace14 ，從 ./qtest 的執行結果推測是 q_sort 時間複雜度不通過。
參考巫冠君的實作，推測也可能也是因為遞迴造成stack overflow，但在massif的檢查中，stack 用量顯示 0 ，記憶體用量均來自 heap ，所以跟 stack overflow 無關。
所以比較有可能是時間複雜度不通過的問題

static void _merge(struct list_head *li1, struct list_head *li2, bool descend)
{
    LIST_HEAD(tmp);

    while (!list_empty(li1) && !list_empty(li2)) {
        element_t *ele_1 = list_first_entry(li1, element_t, list);
        element_t *ele_2 = list_first_entry(li2, element_t, list);
        int cmp = strcmp(ele_1->value, ele_2->value);

        if (descend) {
            if (cmp >= 0)
                list_move_tail(&ele_1->list, &tmp);
            else
                list_move_tail(&ele_2->list, &tmp);
        } else {
            if (cmp <= 0)
                list_move_tail(&ele_1->list, &tmp);
            else
                list_move_tail(&ele_2->list, &tmp);
        }
    }
    if (!list_empty(li1))
        list_splice_tail_init(li1, &tmp);
    if (!list_empty(li2))
        list_splice_tail_init(li2, &tmp);

    list_splice_init(&tmp, li1);
}

/* Merge sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    int size = 0;
    struct list_head *pos;
    list_for_each (pos, head) {
        size++;
    }
    if (size < 2)
        return;

    int mid = size / 2;

    LIST_HEAD(left);
    LIST_HEAD(right);

    for (int i = 0; i < mid; i++) {
        list_move_tail(head->next, &left);
    }
    list_splice_init(head, &right);

    q_sort(&left, descend);
    q_sort(&right, descend);

    _merge(&left, &right, descend);

    list_splice_init(&left, head);
}

後來發現因為以下的操作過於沒效率，可以用 list_cut_position 改善，改善後就通過 trace14了

--for (int i = 0; i < mid; i++) {
--        list_move_tail(head->next, &left);
--    }
++ list_cut_position(&left, head, slow);

q_ascend

題目要求為： Remove every node which has a node with a strictly less value anywhere to the right side of it
從環狀雙向鏈結串列尾部、也就是 head->prev 作為起點逆向走訪，用 strcmp 比對當前節點和其 prev 節點的 value ，如果回傳小於0，代表當前的節點比較小，因此前一個節點必須移除。藉由環狀的特性，不斷的走訪並比對。

int q_ascend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    struct list_head *curr = head->prev;
    while (curr->prev != head) {
        if (strcmp(list_entry(curr, element_t, list)->value,
                   list_entry(curr->prev, element_t, list)->value) < 0) {
            struct list_head *tmp = curr->prev;
            list_del(tmp);
            q_release_element(list_entry(tmp, element_t, list));
        } else {
            curr = curr->prev;
        }
    }

    return q_size(head);
}

q_descend

一樣的實作，只更改判斷 strcmp 的回傳值是否大於0。

Commit 61ad05e

q_merge

在 queue.h 可以看到 queue_contex_t 的定義，以雙向鏈結串列指標 q 指向佇列的 head ，並且使用 chain 與其他佇列串連在一起，用 size 紀錄這個佇列的長度
作法參考komark06
不過目前 qtest 並未提供以降序合併所有佇列

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return 0;

    queue_contex_t *queue_head;
    if (descend) {
        queue_head = container_of(head->prev, queue_contex_t, chain);

        for (struct list_head *curr = head->prev->prev; curr != head;
             curr = curr->prev) {
            queue_contex_t *queue = container_of(curr, queue_contex_t, chain);
            _merge(queue_head->q, queue->q, descend);
            INIT_LIST_HEAD(queue->q);
            queue->size = 0;
        }
    } else {
        queue_head = container_of(head->next, queue_contex_t, chain);
        for (struct list_head *curr = head->next->next; curr != head;
             curr = curr->next) {
            queue_contex_t *queue = container_of(curr, queue_contex_t, chain);
            _merge(queue_head->q, queue->q, descend);
            INIT_LIST_HEAD(queue->q);
            queue->size = 0;
        }
    }

    return q_size(queue_head->q);
}

Valgrind 分析記憶體使用狀況

在這裡，我參考 I-HSIN Cheng 使用 massif 分析 trace14 的記憶體用量，分析的過程中產生了許多不符合預期的結果，後續發現只是因為一小部份的程式碼不夠有效率。
用 massif 追蹤改善前後的執行時間差別

改善前

改善後

雖然改善後記憶體用量增加，不過我最主要追蹤的是執行時間

 n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
44    431,239,849       93,377,256       81,349,711    12,027,545            0

45  1,104,822,993       93,377,256       81,349,711    12,027,545            0

 n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
39    403,500,525       85,931,520       74,864,307    11,067,213            0

40    980,985,081       85,931,520       74,864,307    11,067,213            0

在兩次 screen shot 之間的時間差對應 trace 14 執行 reverse 和 sort 的過程，在我改善 sort 的實作後，這段執行時間從大約 670,000,000 下降到 580,000,000。

自動測試程式

signal 是一種處理程式例外情況的功能，當引發 signal (比如按 ctrl-c ) ，行程一定要停下手上的工作，優先處理 signal 。 引發 signal 後有預設行為，比如終止行程，也可以自行定義：

static void q_init()
{
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegv_handler);
    signal(SIGALRM, sigalrm_handler);
}

void sigsegv_handler(int sig)
{
    // self defined function
    report(1,
           "Segmentation fault occurred.  You dereferenced a NULL or invalid "
           "pointer");
    /* Raising a SIGABRT signal to produce a core dump for debugging. */
    abort();
}

使用 signal ，我用很簡單的程式練習如何使用 signal

int main(){
    printf("Hello ");
    signal(SIGALRM, signalrm_handler);
    alarm(1);  //after 1 second, send SIGALRM
    for(int i = 0; i < 100000; i ++){
        for(int j = 0; j < 100000; j++);
    }
    printf("World!\n");
}

void signalrm_handler(int sig){
    printf("\nexeceed 1 second");
    exit(1);  //terminate this process
}

/* output:
*  Hello 
*  execeed 1 second
*/

閱讀到 report_event 時，注意到以前沒看過的語法

void report_event(message_t msg, char *fmt, ...)
{
    va_list ap;
    bool fatal = msg == MSG_FATAL;
    char *msg_name = msg == MSG_WARN
                         ? "WARNING"
                         : msg == MSG_ERROR ? "ERROR" : "FATAL ERROR";
    int level = msg == MSG_WARN ? 2 : msg == MSG_ERROR ? 1 : 0;
    ...

上述程式碼使用兩層三元運算子
在 ISO/IEC 9899 6.5.15寫到：

代表三元運算子允許巢狀結構

命令列直譯器：
我一開始以為 add_cmd 用單向鏈結串列儲存命令，並且將以字典順序排列，是確保不會出現 strcmp 沒有比對完全，僅尋找到前面 n 個字元相符就回傳 0 的情況。
但後來查看 man page 和實驗後，發現 strcmp 只會在兩個字串完全相同才會回傳 0 。
是 strncmp 會比對給定的前 n 個字元，一樣就回傳 0 ，不管剩下的尚未比對的部份。

檢測非預期的記憶體操作或程式執行逾時：
exception_setup 會在首次呼叫走 else，設定 alarm(time_limit) ，一旦超過 time_limit 但該行程還沒結束時，會送出 SIGALRM ，然後立刻跳回 signal handler。signal handler 會印出錯誤訊息，並進行 siglongjmp 跳到 exception_setup 並且走 if ，然後回傳 false ，結束該測試。

    if (exception_setup(true)) {
        for (r = 0; ok && r < reps; r++) {
            bool rval = q_insert_tail(q, inserts);
            ...
        }
    }
    exception_cancel();

exception_setup 透過 sigsetjmp 的設計而執行兩次。

bool exception_setup(bool limit_time)
{
    if (sigsetjmp(env, 1)) {
        /* Got here from longjmp */
        jmp_ready = false;
        if (time_limited) {
            alarm(0);
            time_limited = false;
        }
        if (error_message) {
            report_event(MSG_ERROR, error_message);
        }
        error_message = "";
        return false;
    } else {
        /* Got here from initial call */
        jmp_ready = true;
        if (limit_time) {
            alarm(time_limit);
            time_limited = true;
        }
        return true;
    }
}

實作 shuffle 命令

我原先用陣列儲存佇列的地址以減少迴圈次數，並且透過更改字串的指標實現節點更改順序的效果，但struct的記憶體配置把成員相鄰地放在一起，依據連續的存放位置進行讀取，所以我誤認為讀取該struct時依舊是讀取原本的成員。不過後來在寫自我評量的過程中查詢規格書學習到：假如結構體的成員是指標，則指標所指向的記憶體並不是與結構體排列在一起，所以我原本的想法是可行的，我又回過頭來除錯本來的程式，並且把宣告陣列改成動態記憶體配置，然後成功實現 shuffle

bool q_shuffle(struct list_head *head)
{
    if(!head || list_empty(head) || list_is_singular(head)) return false;
	
    int len = q_size(head), i = 0;
--    struct list_head *arr[1000000] = {};
++  element_t **arr = malloc(len*sizeof(element_t));
    struct list_head *curr = NULL, *old = NULL, *new = NULL;
    element_t *old_ele, *new_ele;
    char *tmp;
--    list_for_each(curr, head) {
--        arr[i] = curr;
--	i++;
--   }
++  list_for_each(curr, head) {
++      arr[i++] = list_entry(curr, element_t, list);
++  }


--    new = head->prev;
--    for(len; len == 1; len--) { 
--        srand(time(NULL));
--        int random = rand() % (len);
--	old = arr[random];
--	old_ele = list_entry(old, element_t, list);
--	new_ele = list_entry(old, element_t, list);
--	tmp = old_ele->value;
--	old_ele->value = new_ele->value;
--	new_ele->value = tmp;
--
--	new = new->prev;
--    }
++    for (int k = len-1; k > 0; k--) {
++        int j = rand() % k;
++        // exchange the value pointer of arr[k] and arr[j]
++        char *tmp = arr[k]->value;
++        arr[k]->value = arr[j]->value;
++        arr[j]->value = tmp;
++    }

++    free(arr);

    return true;
}

接下來發現程式碼涉及兩塊記憶體的值的原地交換，於是嘗試練習老師上課教的 bitop 並根據你所不知道的 C 語言：bitwise 操作以及 ISO/IEC 9899 6.5.11：

Each of the operands shall have integer type.

必須先將原本的 char * 型態轉換成 integer ，考慮到有號整數容易發生意外，所以選擇將型態轉換為 unsigned int 。也實現 shuffle

for (int k = len - 1; k > 0; k--) {
        int j = rand() % k;
        // exchange the value pointer of arr[k] and arr[j]
--      char *tmp = arr[k]->value;
--      arr[k]->value = arr[j]->value;
--      arr[j]->value = tmp;
++      arr[k]->value =
++            (char *) ((u_int64_t) arr[k]->value ^ (u_int64_t) arr[j]->value);
++      arr[j]->value =
++            (char *) ((u_int64_t) arr[k]->value ^ (u_int64_t) arr[j]->value);
++      arr[k]->value =
++            (char *) ((u_int64_t) arr[k]->value ^ (u_int64_t) arr[j]->value);
    }

接下來利用作業說明提供的python程式碼驗證 shuffle 的亂度，在實際執行時，程式碼在重複執行
input += "shuffle\n" 時會造成程式碼卡住，所以我將程式碼改成可以一次性輸入洗牌次數：

static bool do_shuffle(int argc, char *argv[])
{
++    if (argc != 2) {
++        report(1, "Usage: shuffle <times>");
++        return false;
++    }
    ...
++    int n = atoi(argv[1]);
++    for (int i = 0; i < n; i++) {
        if (exception_setup(true))
            q_shuffle(current->q);
        exception_cancel();
        q_show(3);
++    }
    return 1;
}

python腳本改成

input += "shuffle " + str(test_count) + "\n"

執行的結果如下

Expectation:  4166
Observation:  {'1234': 10048, '1243': 14952, '1324': 0, '1342': 0, '1423': 0, '1432': 0, '2134': 0, '2143': 10048, '2314': 0, '2341': 0, '2413': 0, '2431': 14952, '3124': 14952, '3142': 0, '3214': 0, '3241': 0, '3412': 0, '3421': 10048, '4123': 0, '4132': 0, '4213': 0, '4231': 0, '4312': 25000, '4321': 0}
chi square sum:  283703.1128180509

顯然並沒有達成真正的洗牌，非常多的結果一次都沒有出現，全部集中在少數結果，接下來我要細查原因
於是我更改python腳本，參考陳麒升的作法，使用字串乘法的方式，使得執行 shuffle 的命令彼此分開
執行結果如下：

Expectation:  4166
Observation:  {'1234': 6364, '1243': 2741, '1324': 1805, '1342': 2142, '1423': 9246, '1432': 2703, '2134': 7335, '2143': 5472, '2314': 5968, '2341': 893, '2413': 0, '2431': 5331, '3124': 2740, '3142': 5070, '3214': 787, '3241': 8684, '3412': 893, '3421': 6827, '4123': 4382, '4132': 0, '4213': 3160, '4231': 3265, '4312': 14192, '4321': 0}
chi square sum:  66845.07777244359

測試結果雖然較上次平均，但結果依舊不理想，我猜測這與亂數種子的設定有關，於是我將 srand(time(NULL)) 移動到 qtest.c 的 int main() 裡頭，然後再做一次測試：

Expectation:  4166
Observation:  {'1234': 4245, '1243': 4187, '1324': 4168, '1342': 4219, '1423': 4164, '1432': 4212, '2134': 4077, '2143': 4102, '2314': 4151, '2341': 4176, '2413': 4142, '2431': 4171, '3124': 4117, '3142': 4265, '3214': 4051, '3241': 4155, '3412': 4247, '3421': 4224, '4123': 4251, '4132': 4120, '4213': 4228, '4231': 4147, '4312': 4100, '4321': 4081}
chi square sum:  20.441190590494475

終於得到較為理想的亂數分佈，而這時我好奇一開始在 qtest 提供的一次性輸入洗牌次數的命令是否為影響結果的變因，於是我把程式碼更改後再做一次測試，得到的結果：

chi square sum:  39.48631781084974

發現第一次測試的兩份結果在 chi square sum 有顯著差異，於是後續我繼續分別測試三次兩種不同方式的結果
採用字串乘法：

chi square sum:  16.030244839174266
chi square sum:  40.73259721555449
chi square sum:  33.253000480076814

一次行輸入洗牌次數：

chi square sum:  22.10561689870379
chi square sum:  37.63466154584734
chi square sum:  50.411425828132494

根據結果推測兩種不同的執行方式對於亂數分佈的影響並不顯著

統計方法驗證 shuffle

接下來使用統計方法驗證洗牌結果，在開始之前我想先了解何謂統計方法驗證結果
這份教材第五頁解釋 hypothesis testing 的目的：

The objective of hypothesis testing is to decide, based on
sample information, if the alternative hypotheses is actually
supported by the data.

這份教材則說明統計驗證方法的流程

在統計驗證中，比如檢測新藥的實驗，要證明新推出的藥物對於降低血壓有效，會將虛無假說定為「新藥對於降低血壓無效」，對立假說為「新藥能使血壓降低」，當統計檢定發現數據出現的情況在虛無假說下發生的可能性非常低（例如，p值低於預先設定的顯著水準），我們便會拒絕虛無假說，從而支持對立假說。
這兩個假設構成了假設檢定的基礎，目的是用來判斷數據提供的證據是否足以說明研究主張（即對立假說）比隨機變異更可能解釋觀察到的現象。而在本實驗，我們期望的目標則是不拒絕虛無假說。
顯著水準是在假設檢定中預先設定的臨界值（常見的有 0.05 或 0.01）。它代表當虛無假說（H₀）為真時，我們願意接受的「犯型一錯誤」的最大機率，也就是說，如果觀察到的數據出現的機率低於這個 α 值，就認為數據與虛無假說不符，因此有足夠的證據拒絕虛無假說。
p 值是在假設虛無假說為真時，觀察到「與實際結果一樣極端或更極端」數據的機率。簡單來說，p 值量化了數據與虛無假說相容的程度；當 p 值很小時（通常小於事前設定的顯著水準 α），意味著在虛無假說下觀察到這樣的數據的可能性極低，因而我們傾向於拒絕虛無假說。

在此份檢驗：

1. 宣稱打亂結果符合 uniform distribution
2. ${𝐻}_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
   
   ${𝐻}_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同
3. 顯著水準採用0.05
   檢驗方式採用 Pearson's chi-squared test 檢驗某特定事件在樣本中觀察到的頻率分佈是否與特定理論分佈一致
4. shuffle 命令採用一次輸入洗牌次數，但是根據python腳本計算出來的 chi square value ，在23自由度下的 p 值，四次結果有三次無法拒絕虛無假說。
   因此為了驗證是否有足夠證據拒絕虛無假說，我將測試增加到100次，並把 p 值的結果繪製出來：

python腳本在 commit 340c789

從結果可以看到 p 值大部分集中於0.9到0.1的區間，並且平均數為0.4698，明顯大於0.05，所以沒有足夠證據推翻虛無假說，因此不拒絕虛無假說

而在實作過程，發現 q_test.c 的 int main 函式已定義亂數種子：
srand(os_random(getpid() ^ getppid())); 所以上面的測試不是以 srand(time(NULL)) 生成的。
於是我重新用 srand(time(NULL)) 再生成一次結果：

平均數為0.3711，與先前的測試並沒有很大的差距，結論依然能得到不拒絕虛無假說

1. 那我好奇使用 srand(os_random(getpid() ^ getppid())); 的必要性在哪，有更好的測試能看出差距嗎？
2. 目前的統計方式檢驗是否足夠好？

亂度

在 qtest 提供顯示熵的指令，我把它打開來看看

cmd> option entropy 1
l = [aaaaaa(0.00%) pneumonoultramicroscopicsilicovolcanoconiosis(43.75%) 
beautiful(35.94%) cat(17.19%) ab(10.94%) aa(0.00%) a(0.00%)]

根據 lab0(D)
Entropy在資訊理論的定義是某個隨機事件平均每個結果發生時所能傳達出的資訊量，當我們預期某個事件發生的機率很高，而他真的發生的時候，我們獲得的資訊其實沒有變多
從上述結果可以看到，當字串重複率很高，entropy 就小，當字串長度越長並且重複性低， entropy 就越高

$S=-\sum _{i=1}^{n}P(x_i)lo{g}_{b}P(x_i)=\sum _{i=1}^{n}P(x_i)I(x_i)$

對於一分佈而言，因

$\sum _{i=1}^{n}P(x_i)=1$
，Entropy 的極大值發生在

$P(x_1)=P(x_2)=...=P(x_n)=\frac{1}{n}$ 時

$(S=lo{g}_{b}n)$ ，因此分佈即爲 uniform distribution
所以將熵用於評估亂度在於計算當前訊息的熵與其最大可能熵的差距有多大
比如1 byte char 的大小為

$2^8$，則最大的 entropy 為

$S={\log }_2(2^8)=8$，而如果我們蒐集一個亂數產生器產生的100000個8 bits 字串的，計算出每一種結果出現的機率，就能使用熵公式計算出熵（熵只需要

$P(x_i)$就能計算）

熵的用途除了計算亂度以外，另一個用途是根據訊息的機率分布去計算訊息編碼所需要的平均編碼長度。
比如單純由英文字母組成的字串，每一個字母出現的次數乘以其編碼所需的 bits 數，再除以總長度，就是對訊息編碼所需的平均長度（就是熵的公式）。這是資訊壓縮的原理
而檢驗亂數的方法也包含平均值檢定、蒙地卡羅法計算 Pi 值、及序列相關係數 (可檢驗序列上每個值前後的相關性)

為什麼需要這麼多不同的方式檢驗亂度

再來我好奇為什麼 Linux 對亂度如此要求，並且亂數被用在哪裡，如何實作的？
在這兩篇 LWN.net ，LWN.net 文章有解釋：
對於作業系統而言，產生足夠亂的亂數對於系統安全至關重要
要產生足夠亂的亂數，必須確保熵足夠，那麼 Linux 究竟如何得到足夠的熵呢？
對於某些情形不需要非常亂的亂數，可以由 /dev/urandom 提供，而某些需要非常亂的亂數，比如加密金鑰等，熵要由環境中隨機事件蒐集，比如敲鍵盤的頻率，硬碟中斷的時間點等等，這些實作來自 /dev/random。
然而從環境蒐集熵就碰到一些問題，比如一些嵌入式設備， headless device ，或是才剛初始化的作業系統，要如何從環境蒐集足夠的熵？

在作業中的檔案 random.c 的 linux_getrandom 函式會系統呼叫 getrandom ，將一個 buffer 填滿隨機字串 ，並且透過 flags 控制熵的來源，在 random.c 實作中 flags 是0，代表從預設的 /dev/urandom 取得熵，而非 /dev/random （flags 是 bit mask）。
假如不存在系統呼叫 getrandom ，則呼叫 linux_urandom ，使用 /dev/urandom 生成隨機數，並且當 /dev/urandom 的熵不夠時，回傳 -1

可以找到 flags bitmask 的定義的位置，在我的電腦 /usr/include/x86_64-linux-gnu/sys ，但我更想知道系統呼叫 getrandom 的實作，從 random.c 可知其屬於 glibc ，但接下來我無法從 glibc 找到 getrandom 確切實作的位置，僅僅在這個網站看到相關的實作

研讀 Dude, is my code constant time?

研讀的時候搭配 Chatgpt Deep research 。

常數時間是一種時間複雜度，它表示某個演算法求出解答的時間在固定範圍內，而不依照問題輸入資料大小變化。比如用索引值存取陣列元素

時序攻擊是從執行時間推敲金鑰或密碼,攻破許多 variable time implementation
有的防範方式是從組合語言，編譯過的高階語言檢查是否有 memory indices 或 branches 是否 secret dependent。但這種方法對於檢查稍微大型的程式會非常費時。
而有些工具可以分析程式碼和 execution traces (a complete record of the computation) ，這些工具仰賴對於硬體的建模，但電腦實際執行過程很複雜，並且許多處理器公司並不會公佈微架構的細節，因此硬體建模難度很高。
這篇論文避免了硬體建模，也不仰賴靜態分析，而是從 side-channel evaluation 下手，收集多次測量時間的結果，並用統計方法分析執行時間是否是常數時間。
分析方式很簡單，檢查執行時間在兩個不同的輸入是否有統計上的差異。
輸入資料採取 fix-vs-random ，即一份是常數資料（可能用來引發 corner case），另一份是隨機資料。

corner case 與 edge case 定義上不同，前者含多個變數，後者僅代表某個極端變量

測量時間的方式使用 CPU 提供的 Cycle counters， x86 環境使用 RDTSC instruction (Read Time-Stamp Counter)
為了減少像作業系統中斷的環境干擾，常數資料和隨機資料會在隨機排序下進行測量。

處理測量資料：
在真實電腦上執行的結果，執行時間通常呈現長尾分佈，也就是執行時間較長的極端值會比較多，比如因為 系統中斷, scheduler noise, or cache effects 。這些極端值會造成統計分佈向較長執行時間偏移。所以傾向切除執行時間較長的極端數據（不過在 Dudect 的實作中也會考慮原始分佈）

Welch's t-test defines the statistic t by the following formula:

$t=\frac{\overline{X_0}-\overline{X_1}}{\sqrt{\frac{Va{r}_0}{N_0}+\frac{Va{r}_1}{N_1}}}$
從公式可以看到：
t 越接近 0 代表兩組數據差距越小
樣本數越多，t 越大
分佈的平均數差距越大，t 越大
分佈的變異數越大，t 越小
可以設想這樣的情況幫助理解：假設平均數有一定程度的差距，此時如果變異數越小，代表分佈越集中，那麼兩組數據的差距會很明顯，但是如果變異數很大，分佈很分散，那麼差距就會不明顯。
常見的標準是 t 大於 4.5 代表有統計上的顯著差異

Student's t-test assumes that the sample means being compared for two populations are normally distributed, and that the populations have equal variances. Welch's t-test is designed for unequal population variances, but the assumption of normality is maintained.

接下來我看不懂 Higher-order preprocessing 在做什麼，也看不懂檢定方法

第一個案例：記憶體比對，比對輸入的密碼是否正確
這邊不懂smoke test
分析的時候，視角分為 white-box ：得知實作細節，和 black-box 。
虛無假說為兩種分佈是一樣的，對立假說為兩種分佈不一樣。
首先測試 memcmp ，理論上是非常數時間的函數，因為它會在比對到第一個不同的值後回傳。

可以看到 Fig. 1 在 fix 和 random 顯示出明顯的 timing leakage ，對於 fix 而言，特別設定成必須比對到最後的 corner case ，而 random 則有機率會提早比對到不符合然後回傳，所以 random 的累積分佈函數會上升的比 fix 還要快。

t 值遠大於 4.5 ，即使只有數千次的樣本也超過。

接下來換作 black box ，也就是在不知道哪樣的 fix 可以比對到最後一位的情況下，將 fix 隨便設定，論文裡設定成 0 。結果在累積分佈函數無法看到顯著差異。

然而在 t 值就能看到，當樣本數夠大，大部分的結果超過 4.5 的門檻，顯示有統計上的差異。

接著進行理論上常數時間的實作

累積函數看起來一樣

t 值均小於 4.5 門檻，並且沒有樣本數多而變大的趨勢，因此統計結果不拒絕虛無假說，符合理論預期。

lab0 的實作，使用 cpucycles() 獲得時間
，計算的時候，使用了 double ， sqrt ，fabs()。

追溯程式碼，從 differentiate 得知 N_MEASURES 等於 150，再找到 constant.c 中 measure 的 after_ticks[] 的指派：

case DUT(insert_head):
        for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
            char *s = get_random_string();
            dut_new();
            dut_insert_head(
                get_random_string(),
                *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
            int before_size = q_size(l);
            before_ticks[i] = cpucycles();
            dut_insert_head(s, 1);
            after_ticks[i] = cpucycles();
            int after_size = q_size(l);
            dut_free();
            if (before_size != after_size - 1)
                return false;
        }
        break;

for 迴圈的執行減去兩個 DropSize 後總共執行 110 次 insert_head，也就是每次 t 檢定的分佈樣本每一批是 110 個執行 insert 的執行時間，每一批新的數據藉由 t_push 更新分佈的平均數和變異數。
所以會在執行 measure 的時候，把 110 筆執行時間儲存下來。然後 differentiate 會把每一筆 execution times 計算出來。
classes 代表順序，其為 110 個 insert 的輸入資料的 fix 和 random 的隨機排列

t_push 的用意在於更新樣本分佈的平均數和變異數。
t_compute 每次會計算當前兩個分佈的 t 值。又因為 t_push 會在每次執行 insert 後，把新一筆執行時間長度的資料納入分佈，算出新的平均值和變異數並更新回分佈的數據中。所以每次 t_compute 的執行都代表更大樣本數下的 t 值。不過 t_compute 並不是在每次 t_push 執行一次就跟著執行一次，t_compute 位於 report 中，所以當 t_compute 執行一次之前， t_push 在 update_statistics 已經執行 N_MEASURES 次。所以 t_compute 每隔一次計算，樣本分佈的平均值和變異數已經更新了 N_MEASURES 次，也就是樣本數一次增加 N_MEASURES 個。將程式執行速度放慢也可以看到 still to go 是以每次減少 110 的速度下降。

measure:    0.00 M, not enough measurements (6260 still to go).

bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
ret &= report();

report 中會確認樣本數是否足夠，如果不夠就會回傳 false ，繼續執行下去。
所以如果把每一次 t_compute 計算出來的 t 值繪製出來，可以得到一個統計圖，如果這個圖的 t 值在測試進行而樣本數越來越大時會顯著超過設定的門檻 ，那就表示待測的程式不是常數時間。

在修改前執行的話，會有這行

Testing insert_tail...(0/10)

static bool test_const(char *text, int mode)
{
    bool result = false;
    t = malloc(sizeof(t_context_t));

    for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
        printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
        init_once();
        for (int i = 0; t->n[0] + t->n[1] < ENOUGH_MEASURE; ++i)
            result = doit(mode);
        printf("\033[A\033[2K\033[A\033[2K");
        if (result)
            break;
    }
    free(t);
    return result;
}

表示整個測試會重複執行 10 次，如果這 10 次沒有一次 t 值小於 10 的話(lab0選擇10作為門檻），也就是當樣本數達到 ENOUGH_MEASURE 後的兩個分佈有顯著差異，就斷定待測程式不是常數時間。

發現在 lab0 的實作，並沒有採取如論文中，用 p 百分位數切除較大的極端值，反而只計算未切除的數據
論文的程式碼有做切除：

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

但問題是要切除多少百分位。參考 rota1001的實驗 ，他選擇切除大於 50 百分位數的數據。
所以如果要把極端數值移除，就必須將所有的 execution times 排序，然後取百分位數。然後再將執行時間超過設定的百分位數的值跳過 t_push

tiny-web-server

這是一個小型的 server 實作，於是我好奇 server 的底層運作原理是什麼。我請 Chatgpt Deep Research 給我快速的講解

我在測試的時候，發現程式碼已具備同時接受命令列輸入以及網頁伺服器輸入的功能。
追溯程式碼發現，在 console.c 的 do_web 中，會將 eventmux_callback 設為 web_eventmux，因此在 ./qtest 輸入 web 命令，就能同時接受命令列和網頁伺服器的輸入。
以下解釋 web_eventmux 如何運作的
首先將命令列和伺服器兩個 file descriptor 加入 listenset

fd_set listenset;

    FD_ZERO(&listenset);
    FD_SET(STDIN_FILENO, &listenset);
    int max_fd = STDIN_FILENO;
    if (server_fd > 0) {
        FD_SET(server_fd, &listenset);
        max_fd = max_fd > server_fd ? max_fd : server_fd;
    }

再來使用 select() 等待 set 中 fd 的輸入

int result = select(max_fd + 1, &listenset, NULL, NULL, NULL);
if (result < 0)
    return -1;

在 linenoise.c 的 line_edit 可以看到：
event_callback 初始化為 NULL ，只有當呼叫 do_web 時才會設為 web_eventmux 。所以未呼叫 do_web 時，linenoise 使用 read 來接受輸入。

while (1) {
        signed char c;
        int nread;
        char seq[5];

        if (eventmux_callback != NULL) {
            int result = eventmux_callback(l.buf);
            if (result != 0)
                return result;
        }

        nread = read(l.ifd, &c, 1);
        if (nread <= 0)
            return l.len;

如果輸入未包含特定字元，比如 ctrl-c, ESC 等，line_edit 會直接回傳輸入的字串。當包含上述之類的特定字元，會繼續執行 line_edit 後續程式碼將特定字元移除。

然而在 do_web 的程式碼，包含將 use_linenoise 設為 false ，但在 run_console 中， 當 use_linenoise 為 false 時，會呼叫 cmd_select ，但在 cmd_select 中，依然透過呼叫 linenoise 來接受輸入，而運作依然符合預期的原因是 linenoise 會呼叫 line_raw 而後者會再呼叫 line_edit ，同時因為 eventmux_callback 被設為 web_eventmux ，後者程式碼有使用 select
因此 cmd_select 似乎是非必要的程式碼，我將 use_linenoise = false; 註解掉依然運作正常。