2025q1 Homework1 (lab0)

contributed by < liangchingyun >

Reviewed by Urbaner3

根據作業 review，檢查事項 1, 5, 8 嘗試聚焦並整理程式碼，並加強改進。
6.48 Alternate Keywords 此段落，注意表達的因果關係，我不是很容易直接解釋或是想到他與什麼有關聯，請舉例，並以此為例，再檢查作業一二文章表達通順。
鼓勵根據作業要求、能力，挑戰論文閱讀，設計實驗。為了專題做預備。如果排程器、中斷、線程等名詞有不理解，隨時提出問題，向講師、同學、討論區發問，養成習慣作筆記，保持進步，一定會成功的。

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [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):                   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:   39%
    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 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 aperfmperf pni pclmulqdq dtes64 monitor ds_cpl smx est tm2 ssse3 sdbg fma cx16 xtpr pd
                          cm 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 fsgs
                          base tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify
                           hwp_act_window hwp_epp md_clear flush_l1d arch_capabilities
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 unsupported
  L1tf:                   Mitigation; PTE Inversion
  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_size

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

    int len = 0;
    struct list_head *pos;

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

list_for_each: 走訪雙向鏈結串列中的每個節點

q_new

一開始並沒有初始化list_head，這導致分配的記憶體中list_head結構的成員未被設置為預期的初始值，顯示錯誤：

Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)

修改後正確初始化list_head

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

-    if (new_head != NULL) {
+    if (new_head) {
+        INIT_LIST_HEAD(new_head);
         return new_head;         
     }
     return NULL;
 }

q_insert_head & q_insert_tail

q_insert_head : 將一個新元素插入到佇列的首部。
q_insert_tail : 將一個新元素插入到佇列的尾部。

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

    element_t *new_ele = malloc(sizeof(element_t));
    if (!new_ele)
            return false;
    INIT_LIST_HEAD(&new_ele->list);

    new_ele->value = strdup(s);

    if (!new_ele->value) {
        free(new_ele);  
        return false;
    }

    list_add(&new_ele->list, head);

    return true;
}

q_insert_tail 即是將 list_add 改為 list_add_tail

strdup: 分配記憶體並將字符串複製到該記憶體中

q_free

一開始使用 list_for_each_entry_safe 巨集指令，在commit時遇到問題：

Following files need to be cleaned up:
queue.c
Running static analysis...
queue.c:35:5: error: There is an unknown macro here somewhere. Configuration is required. If list_for_each_entry_safe is a macro then please configure it. [unknownMacro]
    list_for_each_entry_safe (entry, safe, l, list)
    ^

Fail to pass static analysis.

因此我去查標頭檔中對list_for_each_entry_safe 的定義：

#if __LIST_HAVE_TYPEOF
#define list_for_each_entry_safe(entry, safe, head, member)            \
    for (entry = list_entry((head)->next, typeof(*entry), member),     \
        safe = list_entry(entry->member.next, typeof(*entry), member); \
         &entry->member != (head); entry = safe,                       \
        safe = list_entry(safe->member.next, typeof(*entry), member))
#endif

根據 3.4 Options Controlling C Dialect，使用 -ansi 會關閉某些 GCC 特性，因此會禁用 typeof 關鍵字。在 6.48 Alternate Keywords 中提到使用替代關鍵字（如 __asm__ 、__extension__ 、__inline__ 和 __typeof__ ）即可在啟用 -ansi 時使用。然而，若修改標頭檔會出現錯誤訊息，因此改成不使用巨集指令的寫法：

void q_free(struct list_head *l)
{
    if (!l || list_empty(l)) {
        free(l); 
        return;
    }

-    element_t *entry, *safe;
+    struct list_head *pos = l->next;

-    list_for_each_entry_safe (
-        entry, safe, l,
-        list)  
-        q_release_element(entry);
+    while (pos != l) {
+        element_t *entry = list_entry(pos, element_t, list);
+        pos = pos->next;
+        q_release_element(entry);
+    }

    free(l);
    return;
}

此函式完成後 q_new, q_insert_head 和 q_insert_tail 均得以通過 make test

struct list_head: 鏈結串列的節點
element_t: 是包含鏈結節點的結構體
list_entry: 一個巨集，用來從鏈結節點指標（pos）回推「擁有這個節點的結構體」

q_romove_head & q_romove_tail

q_romove_head : 將佇列的首部的元素移除。
q_romove_tail : 將佇列的尾部的元素移除。

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

    element_t *first_entry = list_first_entry(head, element_t, list);

    if (sp != NULL) {
-       sp = strncpy(sp, first_entry->value, bufsize - 1);
+       strncpy(sp, last_entry->value, bufsize - 1);
        sp[bufsize - 1] = '\0'; // Ensure the string is null-terminated
    }

    list_del(&first_entry->list);  

    return first_entry;
}

strncpy 函數已經將 first_entry->value 中的內容複製到 sp 中，因此不需要將 sp 重新賦值。

first_entry->list: first_entry 節點中用來鏈接到其他節點的鏈結串列指針。

然而，此作法無法通過 trace-17-complexity。因為這個函數沒有處理 first_entry->value 可能為 NULL 的情況。如果 value 為 NULL，在使用 strncpy 時可能會導致未定義行為。

    if (sp != NULL) {
+       if (first_entry->value != NULL) {
            strncpy(sp, first_entry->value, bufsize - 1);
            sp[bufsize - 1] = '\0';  // Ensure the string is null-terminated
+       } else {
+           sp[0] = '\0'; 
+       }
    }

修改後即可通過 trace-17-complexity。
q_remove_tail 即是將 first_entry 改為 last_entry 。

q_swap

原本的程式碼：

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

    struct list_head *iterator = head->next;
    struct list_head *temp;

    while (iterator != head && iterator->next != head) {
        temp = iterator->next;
        
        iterator->prev->next = temp;
        temp->prev = iterator->prev;
        iterator->next = temp->next;
        if (temp->next != head) {
            temp->next->prev = iterator;
        }
        temp->next = iterator;
        iterator->prev = temp;

        iterator = iterator->next->next;
    }
}

因為 q_swap 是 q_reverseK 在 K=2 時的特例，因此改為以下程式碼:

void q_swap(struct list_head *head)
{ 
    q_reverseK(head, 2);
}

q_delete_mid

將節點從鏈結串列中刪除後，需要手動釋放這些節點所佔用的記憶體，因此做了以下修正：

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    struct list_head *ptr_1 = head->next;
    struct list_head *ptr_2 = head->next;
    while (ptr_1 != head && ptr_1->next != head) {
        ptr_1 = ptr_1->next->next;
        ptr_2 = ptr_2->next;
    }
+   element_t *mid = list_entry(ptr_2, element_t, list);
    list_del(ptr_2);
+   free(mid->value);
+   free(mid);
    return true;
}

q_delete_dup

參考 2095. Delete the Middle Node of a Linked List 的其中一個解法

使用 strcmp 比較兩個節點的 value 是否相同

q_reverse

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

    struct list_head *cur = head->next;
    struct list_head *temp = NULL;

    while (cur != head) {
        temp = cur->next;      
        cur->next = cur->prev;   
        cur->prev = temp;      
        cur = temp;             
    }

    temp = head->next;
    head->next = head->prev;
    head->prev = temp;
}

q_reverseK

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head) {
        return;
    }

    int split_time = q_size(head) / k;
    struct list_head *tail;

    LIST_HEAD(tmp);
    LIST_HEAD(new_head);

    for (int i = 0; i < split_time; i++) {
        int j = 0;
        list_for_each (tail, head) {
            if (j >= k) {
                break;
            }
            j++;
        }
        list_cut_position(&tmp, head, tail->prev);
        q_reverse(&tmp);
        list_splice_tail_init(&tmp, &new_head);
    }
    list_splice_init(&new_head, head);
}

q_sort

參考同學寫法，使用 MergeTwoLists

• 將 descend ^ (strcmp(e1->value, e2->value) < 0) 定義成 bool condition，精簡了 node 的指派邏輯。
• 改寫了 fast 和 slow 指標的初始化方式，並將 for 循環改為 while 進行快慢指標的移動。
• 因為 e1 及 e2 的值不會遭變更，因此加上 const

void mergeTwoLists(struct list_head *L1, struct list_head *L2, bool descend)
{
    if (!L1 || !L2)
        return;
    struct list_head head;
    INIT_LIST_HEAD(&head);
    while (!list_empty(L1) && !list_empty(L2)) {
-       element_t *e1 = list_first_entry(L1, element_t, list);
-       element_t *e2 = list_first_entry(L2, element_t, list);
-       struct list_head *node = (descend ^ (strcmp(e1->value, e2->value) < 0))
-                                    ? L1->next
-                                    : L2->next;
+       const element_t *e1 = list_first_entry(L1, element_t, list);
+       const element_t *e2 = list_first_entry(L2, element_t, list);
+       bool condition = (descend ^ (strcmp(e1->value, e2->value) < 0));
+       struct list_head *node = condition ? L1->next : L2->next;
        list_move_tail(node, &head);
    }
    list_splice_tail_init(list_empty(L1) ? L2 : L1, &head);
    list_splice(&head, L1);
}

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    // https://hackmd.io/IKsnn85aRHGMrNcRP7BJ1Q?view#2024q1-Homework1-lab0
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *slow = head;
-   const struct list_head *fast = NULL;
+   struct list_head *fast = head->next;

-   for (fast = head->next; fast != head && fast->next != head;
-        fast = fast->next->next)
-       slow = slow->next;
+   while (fast != head && fast->next != head) {
+       slow = slow->next;
+       fast = fast->next->next;
+   }

    struct list_head left;
    list_cut_position(&left, head, slow);
    q_sort(&left, descend);
    q_sort(head, descend);
    mergeTwoLists(head, &left, descend);
}

q_ascend & q_descend

簡化了走訪邏輯，直接用 pos 來控制位置，讓程式看起來更直觀。

int q_ascend(struct list_head *head)
 {
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
         return 0;

-   element_t *right = list_entry(head->prev, element_t, list);
-   element_t *left = list_entry(head->prev->prev, element_t, list);
-   while (&left->list != head) {


+   struct list_head *pos = head->prev;
+   while (pos != head && pos->prev != head) {
+       const element_t *right = list_entry(pos, element_t, list);
+       element_t *left = list_entry(pos->prev, element_t, list);

        if (strcmp(right->value, left->value) > 0) {
-           left = list_entry(left->list.prev, element_t, list);
-           right = list_entry(right->list.prev, element_t, list);
+           pos = pos->prev;
        } else {
            list_del(&left->list);
            free(left->value);
            free(left);
-           left = list_entry(right->list.prev, element_t, list);
        }
    }
    return q_size(head);
}
 }

q_descend 即是將 strcmp(right->value, left->value) > 0 改成 strcmp(right->value, left->value) < 0

q_merge

原本 queue_to_merge 是在迴圈外部宣告，但這個變數只在迴圈中使用，把它移進迴圈內。

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

    queue_contex_t *base_queue = list_first_entry(head, queue_contex_t, chain);
    if (list_is_singular(head)) {
        return base_queue->size;
    }

-   queue_contex_t *queue_to_merge;
    struct list_head *pos, *next;

    list_for_each_safe (pos, next, head) {
        if (pos == &base_queue->chain) {
            continue;
        }
-       queue_to_merge = list_entry(pos, queue_contex_t, chain);
+       queue_contex_t *queue_to_merge = list_entry(pos, queue_contex_t, chain);
        list_splice_tail_init(queue_to_merge->q, base_queue->q);
        base_queue->size += queue_to_merge->size;
    }

    q_sort(base_queue->q, descend);
    return base_queue->size;
}

Valgrind 分析記憶體問題

作業要求

運用 Valgrind 排除 qtest 實作的記憶體錯誤

執行 $ make valgrind 後，得到以下訊息：

# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/liangchingyun/linux2025/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o list_sort.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d .list_sort.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  CC    qtest.o
  CC    report.o
  CC    console.o
  CC    harness.o
  CC    queue.o
  CC    random.o
  CC    dudect/constant.o
  CC    dudect/fixture.o
  CC    dudect/ttest.o
  CC    shannon_entropy.o
  CC    linenoise.o
  CC    web.o
  CC    list_sort.o
  LD    qtest
make[1]: Leaving directory '/home/liangchingyun/linux2025/lab0-c'
cp qtest /tmp/qtest.fRLs65
chmod u+x /tmp/qtest.fRLs65
sed -i "s/alarm/isnan/g" /tmp/qtest.fRLs65
scripts/driver.py -p /tmp/qtest.fRLs65 --valgrind 
---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---     trace-05-ops    6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
---     trace-06-ops    6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---     trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---     trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---     trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---     trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---     trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
Warning: Skip checking the stability of the sort because the number of elements 2000000 is too large, exceeds the limit 100000.
---     trace-14-perf   6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---     trace-15-perf   6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---     trace-16-perf   6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           100/100

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.fRLs65 --valgrind -t <tid>

結果顯示程式通過所有測試，也沒有發生 Memory Leak 、 Invalid Memory Access 等問題。

透過 Massif 視覺化 simulation 過程中的記憶體使用量

整合網頁伺服器

研讀 lib/list_sort.c 並嘗試改進

作業要求

這段程式碼涉及到三個核心函數：

1. merge() - 合併兩個已排序的單向鏈結串列，並返回排序後的鏈結串列
2. merge_final() - 進行最終合併並恢復雙向鏈結串列
3. list_sort() - 主排序函數，負責將鏈結串列拆分並合併排序

它使用空結尾的單向鏈結串列來合併子串列，最後再還原為雙向鏈結串列，提高效能。時間複雜度為 O(n log n)，適合排序大型鏈結串列。

流程舉例

在 list_sort() 中，排序過程透過 Bottom-Up 的方式進行合併：

1. 初始狀態：每個節點視為獨立的排序單元（1 個元素的區塊）
   e.g., [4] [2] [5] [3] [1]
2. 合併相鄰的兩個區塊，確保每個合併後的區塊仍然有序
   [4] + [2] → [2,4]
[5] + [3] → [3,5]
[1] (單獨保留，因為目前沒有另一個可合併的區塊)
3. 繼續合併已排序的區塊
   [2,4] + [3,5] → [2,3,4,5]
[1] 保留
4. 最終合併
   [2,3,4,5] + [1] → [1,2,3,4,5]

將 list_sort.c 加入 lab0-c 專案

Commit: 0c1203d

將 Linux 核心原始程式碼的 list_sort.c 和 list_sort.h 複製到 lab0-c 專案中，並且為了成功編譯做了以下修改：

• list_sort.h 與 list.h 路徑修正。
• 刪掉 EXPORT_SYMBOL(list_sort)
• 將 u8 改成 uint8_t 作為 count，並加入 #include <stdint.h>
• 移除不必要的 #include，手動加入 likely 和 unlikely 的定義。

在 queue.h 、 queue.c 中加入對應程式碼後，於 Makefile 中新增 list_sort.o 。另外，我在 qtest.c 中新增 option ksort ，用來切換原本的 q_sort 與新的 q_ksort 。

static int sort_option = 0;

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

if (current && exception_setup(true))
-   q_sort(current->q, descend);
+   sort_option ? q_ksort(current->q, descend) : q_sort(current->q, descend);
exception_cancel();

效能分析

我執行 ./qtest 並使用以下的命令來分析排序效能:

new
option ksort 1/0 <= (1: q_ksort; 0: q_sort)
ih RAND 100000
time sort        

執行結果如下：

q_sort	q_ksort
0.111	0.089

因為不能變更 queue.h ，所以 commit 時將以下程式刪除，並註解掉相關部份：

void q_ksort(struct list_head *head, bool descend);

開發 Timsort 排序程式

參考資料：Linux 核心專題: 改進 lib/list_sort.c、Timsort 研究與對 Linux 核心貢獻嘗試、最貼近現實的排序演算法- Timsort、linux23q1-timsort

liangchingyun/Sorts-main

正確處理空指針的情況：

size_t get_run_size(struct list_head *run_head)
{
-   return run_head ? 0 : (size_t)(run_head)->next->prev;
+   if (run_head == NULL || run_head->next == NULL ||
+       run_head->next->prev == NULL) {
+       return 0;
+   }
+   return (size_t)(run_head->next->prev);
}

縮小變數作用範圍：

static inline void list_rotate_left(struct list_head *head)
{
-   struct list_head *first;

	if (!list_empty(head)) {
-   	first = head->next;
+       struct list_head *first = head->next;
		list_move_tail(first, head);
	}
} 

將沒有被修改的變數宣告為 const 指標

static inline int list_empty_careful(const struct list_head *head)
{
-   struct list_head *next = head->next;
+   const struct list_head *next = head->next;
	return (next == head) && (next == head->prev);
}

將 head 初始化為 NULL

static struct list_head *merge(void *priv, list_cmp_func_t cmp,
			       struct list_head *a, struct list_head *b)
{
-   struct list_head *head, **tail = &head;
+   struct list_head *head = NULL, **tail = &head;

刪掉沒被使用的變數

static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
			struct list_head *a, struct list_head *b)
{
	struct list_head *tail = head;
-   uint8_t count = 0;

指標 tp 指向 stk - 1 導致未定義行為的修正

void shiverssort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
	struct list_head *list = head->next;
-   struct run stk[MAX_MERGE_PENDING], *tp = stk - 1;
+   struct run stk[MAX_MERGE_PENDING], *tp = stk;

	if (head == head->prev)
		return;

	/* Convert to a null-terminated singly-linked list. */
	head->prev->next = NULL;

	do {
-   	    tp++;
            /* Find next run */
            tp->list = list;
            list = find_run(priv, list, &tp->len, cmp);
            tp = merge_collapse(priv, cmp, stk, tp);
+           tp++;
	} while (list);

+   tp--;

移除冗餘的運算
(*tp).len –> tp->len
&(*(tp->next)) –> ->next
&(*(tp)) –> tp

測試結果:

Implementation	Elapsed time	Comparisons
Linux	184876	19646345
shiverssort	137262	14339471
timsort	152536	15254864

實作 shuffle 命令

作業要求
Commit: 7023f89

實作 Fisher-Yates shuffle Algorithm

從鏈結串列的尾端開始反向走訪，pos 表示目前尚未被抽取的最後一個節點，而 pick 則是從 pos 往前數的第 r 個節點，最後將 pos 和 pick 進行位置交換。

static inline void swap(struct list_head *a, struct list_head *b)
{
    if (a->prev != b) {
        list_move(b, a->prev);
    }
    list_move(a, b->prev);
}

void q_shuffle(struct list_head *head)
{
    if (!head || list_is_singular(head))
        return;

    for (int len = q_size(head); len > 1; len--) {
        struct list_head *pos = head->prev;
        struct list_head *pick = head->prev;
        for (int r = rand() % len; r > 0; r--)
            pick = pick->prev;
        if (pick != pos)
            swap(pos, pick);
    }
}

因為不能變更 queue.h ，所以 commit 時將以下程式刪除，並註解掉相關部份：

void q_shuffle(struct list_head *head);

統計方法驗證

用測試腳本進行測試，結果如下：

Expectation:  41666
Observation:  {'1234': 41815, '1243': 41822, '1324': 41755, '1342': 41791, '1423': 41971, '1432': 41786, '2134': 41630, '2143': 41593, '2314': 41318, '2341': 41660, '2413': 41525, '2431': 41724, '3124': 41846, '3142': 41996, '3214': 42002, '3241': 41622, '3412': 41620, '3421': 41955, '4123': 41415, '4132': 41530, '4213': 41545, '4231': 41340, '4312': 41384, '4321': 41355}
chi square sum:  25.175106801708825

結果大致符合 uniform distribution。

亂數產生器

作業要求

嘗試計算 linux 內建的 PRNG /dev/random

$ head -c 10M /dev/random | ent
Entropy = 7.999980 bits per byte.

Optimum compression would reduce the size
of this 10485760 byte file by 0 percent.

Chi square distribution for 10485760 samples is 288.33, and randomly
would exceed this value 7.42 percent of the times.

Arithmetic mean value of data bytes is 127.4672 (127.5 = random).
Monte Carlo value for Pi is 3.142315347 (error 0.02 percent).
Serial correlation coefficient is -0.000074 (totally uncorrelated = 0.0).

研讀論文

〈Dude, is my code constant time?〉

作業要求

dudect 的檢測流程包含三個步驟：

1. 測量執行時間
   針對不同的 輸入類別（input classes），測量其執行時間：
   • 固定輸入（fixed class）：輸入值固定不變。
   • 隨機輸入（random class）：每次測試時隨機選擇輸入值。
     使用現代 CPU 提供的 cycle counter（如 x86 的 TSC 計數器或 ARM 的 systick）來測量執行時間。
2. 進行後處理
   • 裁剪（cropping）： 為了減少環境雜訊影響，過大的測量值可以被丟棄。
   • 高階處理（higher-order preprocessing）： 有時可以使用類似於 DPA 攻擊的方式進行數據處理，以提高檢測能力。
3. 進行統計測試
   • Welch’s t-test（t 檢定）：檢測兩組輸入的執行時間分布是否有統計學上的顯著差異。
   • Kolmogorov-Smirnov（K-S 檢定）：非參數檢定，適用於更廣泛的時間變異性分析。

Bottom-up Mergesort: A Detailed Analysis

The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules

Queue-Mergesort

Git 實作

Commit & Push

clang-format -i *.[ch]
git commit -a
git push

Config 設定

git config --global user.name "liangchingyun"
git config --global user.email "[e-mail]"

fetch

git remote add sysprog21 https://github.com/sysprog21/lab0-c.git
git fetch sysprog21
git remote remove sysprog21

rebase

• git branch ：查看本地分支
• git branch -r ：查看遠端倉庫分支
• git remote show origin ：查看本地與遠端的關係
• git status ：檢查本地與遠端是否同步
• git pull origin master ：更新本地分支（拉取遠端的最新變更）
• git push origin master ：推送本地變更到遠端
• git commit --amend ：修改最後一次 Commit 的訊息
• git rebase -i HEAD~N：查看最新的 N 個 Commit
• git branch -d branch-name：刪除本地分支
• git branch -D branch-name：強制刪除本地分支
• git push origin --delete branch-name：刪除遠端分支
• git commit --amend --author="user-name <user-email>"：修改最近一次 commit 的作者資訊
• git rebase --abort: 放棄剛才的 rebase

git checkout origin
git rebase sysprog21/master

// 解決衝突
git add queue.c
git rebase --continue

// 更新到本地 branch
git reset --hard 7034022c
git pull origin master

git pull origin master --force

建立 Pull Request

git remote add upstream https://github.com/sysprog21/vcam.git
git fetch upstream
git checkout upstream/main
git checkout -b new-branch
git add .
git commit -m "Commit message"
git push origin new-branch