2025q1 Homework1 (lab0)

contributed by: <Beethovenjoker> (章元豪) Github

作業要求

在 GitHub 上 fork lab0-c。
依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差，也該嘗試改進針對鏈結串列排序實作的效能。
在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」。
在 qtest 中執行 option entropy 1 並搭配 ih RAND 10 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 qtest切換不同的 PRNG 的實作 (可選定 Xorshift)，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質。
研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。
指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request。

開發環境

$ 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):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             10
    CPU(s) scaling MHz:   53%
    CPU max MHz:          4600.0000
    CPU min MHz:          800.0000
    BogoMIPS:             6399.96
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge m
                          ca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 s
                          s ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc 
                          art arch_perfmon pebs bts rep_good nopl xtopology nons
                          top_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor 
                          ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm p
                          cid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_tim
                          er aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch
                           cpuid_fault epb pti ssbd ibrs ibpb stibp tpr_shadow f
                          lexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 a
                          vx2 smep bmi2 erms invpcid mpx rdseed adx smap clflush
                          opt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida
                           arat pln pts hwp hwp_notify hwp_act_window hwp_epp vn
                          mi md_clear flush_l1d arch_capabilities
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    192 KiB (6 instances)
  L1i:                    192 KiB (6 instances)
  L2:                     1.5 MiB (6 instances)
  L3:                     12 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-11
Vulnerabilities:          
  Gather data sampling:   Mitigation; Microcode
  Itlb multihit:          KVM: Mitigation: VMX disabled
  L1tf:                   Mitigation; PTE Inversion; VMX conditional cache flush
                          es, 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 prct
                          l
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointe
                          r sanitization
  Spectre v2:             Mitigation; IBRS; IBPB conditional; STIBP conditional;
                           RSB filling; PBRSB-eIBRS Not affected; BHI Not affect
                          ed
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Mitigation; TSX disabled




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.

雙系統設置

先安裝Windows / Ubuntu 雙系統

先將電腦磁碟分割一部分給Ubuntu24.04作業系統。
將Ubuntu24.04映像檔掛載到空的隨身碟。
重啟電腦並在開機時按F12和Delete鍵，進入BIOS畫面。
選擇隨身碟掛載的Ubuntu24.04然後安裝好作業系統。

開發佇列操作

結構體

list_head為雙向鏈結串列的一個節點。

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

element_t為包含value和list_head的結構體，所以雙向鏈結跟儲存的值是分開的結構體，後面使用巨集的時候要小心。

typedef struct {
    char *value;
    struct list_head list;
} element_t;

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

q_new()

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

先配置記憶體給node，我原本還在想malloc和free的使用方法，後來回憶起前者是c語言的用法，而後者是c++的。接者判斷是否有成功配置記憶體，如果記憶體不夠，就直接回傳NULL值。

然後要將雙向鏈結指向自己，一開始沒發現有INIT_LIST_HEAD()的巨集可以使用，所以在開發佇列操作之前應詳細閱讀list.h和queue.h，最後回傳此節點。

q_free()

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

先判斷佇列有沒有節點，沒有的話直接回傳。
然後看到list_for_each_safe（）的巨集可以用來逐一走訪整個list並且可以移除節點。
我們要釋放整個佇列結構的記憶體，所以使用q_release_element()。
因為要釋放element_t，而list_for_each_safe（）非直接釋放整個element_t，所以用container_of()來包。

$ ./qtest
cmd> new
l = []
cmd> free
l = NULL
ERROR: There is no queue, but 1 blocks are still allocated
cmd>

使用./qtest來測試，結果顯示記憶體沒釋放乾淨，繼續除錯。

-    struct list_head *node = NULL, *safe = NULL;
-    list_for_each_safe (node, safe, head) {
-        q_release_element(container_of(node, element_t, list))
+    element_t *entry = NULL, *safe;
+    list_for_each_entry_safe (entry, safe, head, list) {
+        list_del(&entry->list);
+        q_release_element(entry);
     }
+    free(head);

list_for_each_entry_safe（）要使用element_t的資料型別，才能訪問value和list，然後必須先用list_del()來斷開鏈結，才能釋放element_t佔的記憶體空間。最後，head的指標也要釋放。

q_insert_head()

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

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

    node->value = strdup(s);
    if (!node->value) {
        free(node);
        return false;
    }

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

首先檢查head是否存在，然後給新的節點element_t配置記憶體。接著利用strdup()為element_t的value配置記憶體，如果沒有成功配置value，那剛剛創建的element_t都要釋放。最後用list_add的巨集把節點加入到佇列開頭。

q_insert_tail()

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    return q_insert_head(head->prev, s);
}

因為是雙向鏈結串列，所以可以使用q_insert_head()去實作，直接訪問head上一個節點就是tail，然後插入節點即可。

-     if (!head)
-         return false;

q_insert_head()已經檢查過head是否存在，更新程式碼並且刪除多餘判斷式。

q_size()

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

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

如果head為空的話，就回傳0。此佇列不為空的話，就用len來記錄佇列的長度，然後用li來逐一走訪此佇列，最後就能算出長度。

q_remove_head()

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    
    element_t *node = list_entry(head->next, element_t, list);
    strncpy(sp, node->value, bufsize);
    list_del(&node->list);

    return node;
}

先檢查head是否存在，接者初始化node，並且用巨集list_entry()，然後node來接要移除掉的節點。

利用strncpy()將value複製到sp，最多複製bufsize的字元，最後利用list_del()巨集來移除node。

-   if (!head)
+   if (!head || list_empty(head))
        return NULL;
    element_t *node = list_entry(head->next, element_t, list);
-   strncpy(sp, node->value, bufsize);
+   if (sp && bufsize > 0) {
+       strncpy(sp, node->value, bufsize - 1);
+       sp[bufsize - 1] = '\0';
+   }

後來沒過截斷測試、佇列為空測試和時間複雜度測試。
發現是因為如果 node->value 的字串長度大於或等於 bufsize，strncpy 不會自動在最後補上 '\0'。還有新增檢查佇列是否為空、sp是否為空指標、bufsize是否大於0。

q_remove_tail()

    element_t *node = list_entry(head->prev, element_t, list);

依樣畫葫蘆，只是要移除的節點為head->prev，也就是tail。










-   if (!head || list_empty(head))
-       return NULL;
-   element_t *node = list_entry(head->prev, element_t, list);
-   if (sp && bufsize > 0) {
-       strncpy(sp, node->value, bufsize - 1);
-       sp[bufsize - 1] = '\0';
-   }
-   list_del(&node->list);
-   return node;
+   return q_remove_head(head->prev->prev, sp, bufsize);

善用已經寫過的函式q_remove_head()。

q_delete_mid()

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

    struct list_head *left = head->prev;
    struct list_head *right = head->next;
    while (left != right && left->prev != right) {
        left = left->prev;
        right = right->next;
    }
    list_del(right);
    q_release_element(container_of(right, element_t, list));
    return true;
}

利用一個往左的指標從佇列的尾巴往左走，一個往右的指標從佇列的頭往右走，
兩個指標相遇就是中間節點。
然後迴圈處理奇數和偶數節點的情況，最後就像q_free()釋放element_t的方式一樣，先斷開鏈結，再釋放element_t。

q_delete_dup()

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

    bool del = false;
    struct list_head *node, *safe ;
    list_for_each_safe(node, safe, head) {
        element_t *cur = list_entry(node, element_t, list);
        if (safe != head && strcmp(cur->value, list_entry(safe, element_t, list)->value) == 0) {
            del = true;
            list_del(node);
            q_release_element(cur);
        } else if (del) {
            del = false;
            list_del(node);
            q_release_element(cur);
        }
    }

    return true;
}

一開始檢查佇列是否有節點，然後用del來紀錄連續一樣value的節點的最後一個是否要刪除，接者用巨集來訪問每一個節點。如果node還沒跑到尾巴，然後目前節點頷下個節點的value一樣，就紀錄del為true，然後釋放目前訪問節點的記憶體空間。如果目前訪問節點和下個節點的value不一樣，判斷del的布林值，如果為true就把連續一樣value的節點的最後一個解開鏈結並且釋放掉記憶體空間。

q_swap()

void q_swap(struct list_head *head)
{
    if (!head || head->next == head || head->next->next == head)
        return;

    struct list_head *first = head->next;
    struct list_head *second = first->next;
    while (first != head && second != head) {
        first->prev->next = second;
        second->next->prev = first;

        first->next = second->next;
        second->prev = first->prev;
        first->prev = second;
        second->next = first;

        first = first->next;
        second = first->next;
    }
    return;
}

先檢查有沒有兩個以上的節點，然後用兩個指標來進行兩兩交換。
先把first前面和second後面的指標接好，然後再將first和next互相連接的指標斷開接好，接者就可以交換順序，最後指標前進，進行下一組的準備。

-   struct list_head *first = head->next;
-   struct list_head *second = first->next;
-   while (first != head && second != head) {
-      first->prev->next = second;
-      second->next->prev = first;
-       first->next = second->next;
-      second->prev = first->prev;
-       first->prev = second;
-       second->next = first;
-       first = first->next;
-       second = first->next;
+   struct list_head *cur = head->next;
+   struct list_head *tmp = NULL;
+   while (cur->next != head) {
+       tmp = cur->next;
+       list_move(tmp, cur->prev);
+       if (cur != head && cur->next != head)
+           cur = cur->next;
    }
-   return;
}

後來用巨集改寫程式，我發現用巨集才能讓別人比較好看得懂你的程式，也讓它看起來精簡許多。
不用巨集的話直接去寫Leetcode就好了。

q_reverse()

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || head->next->next == head)
        return;

    struct list_head *cur = head->next;
    struct list_head *tmp = NULL;
    while (cur != head) {
        tmp = cur->next;
        cur->next = cur->prev;
        cur->prev = tmp;
        cur = tmp;
    }
    tmp = head;
    head->next = tmp->prev;
    head->prev = tmp->next;
    return;
}

先檢查有沒有兩個以上的節點，然後用cur來逐一走訪每個節點，用tmp來紀錄下次逐一走訪的位置。
接者就是基本的節點反轉，最後再將head的指標也反轉。

    while (cur != head) {
        tmp = cur->next;
-       cur->next = cur->prev;
-       cur->prev = tmp;
+       list_move(cur, head);
        cur = tmp;
    }
-   tmp = head;
-   head->next = tmp->prev;
-   head->prev = tmp->next;
-   return;
}

多使用Linux Kernel的巨集來簡短程式碼，list_move()可以將逐一走訪的節點加到開頭，就等於反轉整個節點

-   struct list_head *cur = head->next;
-   struct list_head *tmp = NULL;
-   while (cur != head) {
-       tmp = cur->next;
-       list_move(cur, head);
-       cur = tmp;
+   struct list_head *node = NULL, *safe;
+   list_for_each_safe (node, safe, head) {
+   list_move(node, head);
    }
}

後來又想到可以用list_for_each_safe()來走訪每個點，讓我的reverse()只剩五行，這個是我最滿意的函式，有時間多多研究如何用巨集精簡其他函式。

q_reversek()

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head) || k < 2)
        return;

    struct list_head *node  = head->next;
    struct list_head *group_head = NULL;
    int counts = 0;

    while (node != head) {
        counts++;

        if (counts == 1)
            group_head = node;
        node = node->next;
        if (counts == k) {
            struct list_head *group_tail = node->prev;
            struct list_head *prev_group = group_head->prev;
            struct list_head *next_group = node;
            struct list_head group;
            INIT_LIST_HEAD(&group);
            list_cut_position(&group, prev_group, group_tail);
            q_reverse(&group);
            list_splice(&group, prev_group);
            counts = 0;
            node = next_group;
        }
    }
}

首先檢查初始條件，接著走訪每個節點，用counts來紀錄走訪到這組的第幾個節點。接者，紀錄這組的第一個節點，然後繼續走訪到這組最後一個節點，就開始建立一個新的佇列來反轉這組的節點。反轉後，再接回去原本的佇列，最後繼續走訪下去。

q_sort()

void merge(struct list_head *left, struct list_head *right, bool descend)
{
    struct list_head dummy;
    INIT_LIST_HEAD(&dummy);
    const element_t *tmp1 = NULL, *tmp2 = NULL;
    while (!list_empty(left) && !list_empty(right)) {
        tmp1 = list_first_entry(left, element_t, list);
        tmp2 = list_first_entry(right, element_t, list);
        bool useLeft = (descend ^ (strcmp(tmp1->value, tmp2->value) < 0));

        if (useLeft) {
            list_move_tail(left->next, &dummy);
        } else {
            list_move_tail(right->next, &dummy);
        }
    }

    if (list_empty(left)) {
        list_splice_tail_init(right, &dummy);
    } else {
        list_splice_tail_init(left, &dummy);
    }
    list_splice_tail_init(&dummy, left);
}

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || head->next->next == head)
        return;

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

    struct list_head *mid = slow; 
    struct list_head left;
    list_cut_position(&left, head, mid);

    q_sort(&left, descend);
    q_sort(head, descend);
    merge(head, &left, descend);
}

目前對於top_down的遞迴merge_sort寫法比較熟悉，雖然效率沒有比bottom_up的方式好，但是比較容易撰寫和直觀。
q_sort()的用途就是來分開左和右兩個鏈結串列。首先用快慢指標可以訪問整個鏈結串列的中間節點，不用q_size()是因為效率很差，接者從中間分割，左邊跟右邊的鏈結串列放進遞迴式，然後再用merge()將兩邊合併起來。
merge()的實作方法是先將宣告一個dummy節點，用來串接兩邊排序好的結果，然後用迴圈和一個flag來判斷是否將左邊還是右邊的鏈結串列取出來。接下來將左邊還沒走訪完畢或是右邊還沒走方完畢的鏈結串列串接到排好的鏈結串列後面。最後再將排序好的串接回原本的鏈結串列。

q_ascend()

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

    int counts = 1;

    struct list_head *node = head->prev;
    element_t *entry = list_entry(node, element_t, list);
    const char *min = entry->value;

    node = node->prev;
    while (node != head) {
        entry = list_entry(node, element_t, list);
        struct list_head *tmp = node->prev;

        if (strcmp(entry->value, min) > 0) {
            list_del(node);
            q_release_element(entry);
        } else {
            if (strcmp(entry->value, min) < 0)
                 min = entry->value;
            counts++;
        }
        node = tmp;
    }
    return counts;
}

因為我是照leetcode的寫法，所以先寫完descend()。
邏輯基本上都一樣，就是紀錄最大值變成紀錄最小值，然後比較方向注意一下。

q_descend()

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

    int counts = 1;

    struct list_head *node = head->prev;
    element_t *entry = list_entry(node, element_t, list);
    const char *max = entry->value;

    node = node->prev;
    while (node != head) {
        entry = list_entry(node, element_t, list);
        struct list_head *tmp = node->prev;

        if (strcmp(entry->value, max) < 0) {
            list_del(node);
            q_release_element(entry);
        } else {
            if (strcmp(entry->value, max) > 0)
                max = entry->value;
            counts++;
        }
        node = tmp;
    }
    return counts;
}

我的想法是從list的尾巴往前訪問，先紀錄第一個節點為最大值和list的節點數，接者進入迴圈訪問每個節點。如果節點的value值比較大，就留著這個節點並將最大值更新為這個節點的value，然後節點數加一;反之節點的的value值比較小，就刪除這個節點並釋放記憶體。最後，回傳這個list的節點數。
不用q_size()來回傳節點數是因為它會再走訪一遍所有節點，所以用counts來紀錄比較有效率。

q_merge()

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

    if (list_is_singular(head))
        return q_size(list_entry(head->next, queue_contex_t, chain)->q);

    queue_contex_t *first = list_entry(head->next, queue_contex_t, chain);
    struct list_head *node = head->next->next;

    while (node != head) {
        queue_contex_t *cur = list_entry(node, queue_contex_t, chain);
        if (cur->q) {
            merge(first->q, cur->q, descend);
        }
        node = node->next;
    }
    return first->size;
}

最後一個函式其實並不複雜，首先先檢查邊緣條件，然後用first來紀錄要合併佇列的主佇列，然後用node來走訪每一個chain的節點。用cur來紀錄要合併到主佇列的佇列，接者用之前寫好的merge()來合併。最後直接回傳主佇列的大小即可。