2025q1 Homework1 (lab0)

contributed by <hahaB7>

作業書寫規範:

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

$ 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-10750H CPU @ 2.60GHz
    CPU family:           6
    Model:                165
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   16%
    CPU max MHz:          5000.0000
    CPU min MHz:          800.0000
    BogoMIPS:             5199.98
    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 est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid 
                          sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer a
                          es xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpu
                          id_fault epb ssbd ibrs ibpb stibp ibrs_enhanced tpr_sh
                          adow flexpriority ept vpid ept_ad fsgsbase tsc_adjust 
                          bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap c
                          lflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dthe
                          rm ida arat pln pts hwp hwp_notify hwp_act_window hwp_
                          epp vnmi pku ospke md_clear flush_l1d arch_capabilitie
                          s
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:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Mitigation; Clear CPU buffers; SMT vulnerable
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; Enhanced 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; Enhanced / Automatic IBRS; IBPB conditiona
                          l; RSB filling; PBRSB-eIBRS SW sequence; BHI SW loop, 
                          KVM SW loop
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Not affected

實作指定佇列操作

`q_new`

commit 30eaeb8

在實作 q_new 時，我對於鏈結列表的初始化方式有些疑問。在 Linux Kernel 的 list.h 中，提供了兩種方式來初始化鏈結列表，分別是 INIT_LIST_HEAD 和 LIST_HEAD。然而，觀察去年作業的實作方式，發現大多數人選擇使用 INIT_LIST_HEAD 來進行初始化。為了理解其中的原因，我進一步分析了這兩種方法的區別，並整理了對應的程式碼如下。

LIST_HEAD

在 q_new 函式內部，若使用 LIST_HEAD 來初始化鏈結列表，將會導致區域變數作用域的問題，進而引發未定義行為（Undefined Behavior）。

#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

struct list_head *q_new()
{    
    return &LIST_HEAD(head)
}

head 是區域變數
由於 LIST_HEAD 只是定義了一個區域變數 head，所以當 q_new 函式執行結束後，head 變數將會被釋放，導致回傳的指標 &LIST_HEAD(head) 指向已無效的記憶體空間，進而造成程式錯誤或未定義行為。
LIST_HEAD 無法用於動態分配的變數
LIST_HEAD 只能在編譯時定義變數，因此它無法用於 malloc 動態分配的記憶體，而 q_new 需要回傳一個可長期使用的鏈結串列，因此 LIST_HEAD 無法滿足需求，所以最終使用INIT_LIST_HEAD實作。

`q_free`

commit 30eaeb8

`q_insert_head` / `q_insert_tail`

commit 9a2a3ff

實作這兩個函式時，需要配置新的記憶體區段給 element_t 以及其成員 value 使用，並且使用 strncpy 來複製的字串到指定位置，這邊只所以使用 strncpy 而非 strcpy 是基於以下分析。

strcpy 的問題
在字串處理時，strncpy 相較於 strcpy 更為安全，主要是因為 strcpy 不會檢查目標緩衝區的大小，可能導致緩衝區溢位，進而覆蓋鄰近的記憶體，造成未定義行為或安全性漏洞。
strncpy 的優勢
strncpy 允許指定最大複製長度，因此可以防止目標緩衝區溢位，且如果來源字串長度小於指定長度，strncpy 會用 '\0' 填滿剩餘空間

q_insert_tail

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

q_insert_tail 的實作重用 q_insert_head，因兩者在初始化 element_t 的過程完全一致，操作上的差異只在插入位置，故對於 q_insert_tail 則傳入 head->prev 以插入佇列尾端。

`q_remove_head` / `q_remove_tail`

commit c053470

`q_size`

commit e213e16

`q_delete_mid`

commit d7ea727

`q_delete_dup`

commit d537d7c

`q_swap`

commit 5c07ba0

`q_reverse` / `q_reverseK`

commit 7ed08d4

`q_ascend` / `q_descend`

commit 831d138

`q_sort`

commit f9c61ca

modify

commit 2f1c7a0

`q_merge`

commit 35f9038

Valgrind + 自動測試程式

待完成

整合網頁伺服器

待完成

實作 `shuffle` 命令

reference

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

`make test` 測試失敗的問題分析

在執行所有指定的佇列操作後，運行 make test 命令時，我發現最後一項測試無法通過。
主要原因是 q_insert_head / tail 及 q_remove_head / tail 這些函式未能通過「是否能夠在常數時間內執行」的測試。問題出在 dudect 功能尚未完善。

在實際實作前，我參考了過去學長的做法，我發現許多人都採用此方法。然而，當我深入分析這份程式碼時，發現了一個重大問題。

觀察其主要新增的函式

首先，觀察 percentile 以及 prepare_percentiles 這兩個函式的實作：

static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
  size_t array_position = (size_t)((double)size * (double)which);
  assert(array_position < size);
  return a_sorted[array_position];
}

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

以及它的呼叫方式

static bool doit(int mode)
{
    int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
    uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
    uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));


    if (!before_ticks || !after_ticks || !exec_times || !classes ||
        !input_data) {
        die();
    }

    prepare_inputs(input_data, classes);

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

    free(before_ticks);
    free(after_ticks);
    free(exec_times);
    free(classes);
    free(input_data);

    return ret;
}

問題分析

問題出在 update_statistics，該函式根據輸入的 exec_times 及對應的類別（隨機 vs. 固定）來動態更新不同類別的統計數據。

exec_times 中的每個值都是透過其索引，對應到 classes 中相同索引的類別。然而，在執行 update_statistics 之前，exec_times 會先經過 prepare_percentiles 處理，而 prepare_percentiles 內部會對 exec_times 進行排序。
這導致 exec_times 的索引順序發生改變，使得 update_statistics 在更新統計數據時對應錯誤，進而導致錯誤的分析結果。

進一步分析

為什麼排序後的 exec_times 反而可以通過常數時間檢測呢？

這與 classes 的隨機性有關。假設 exec_times 是某種測試過程中獲得的執行時間序列，其中每個執行時間對應到一個類別（隨機或固定）。然而，在 prepare_percentiles 內部，exec_times 被排序，這改變了執行時間與其原始類別之間的關聯。

補充：問題
如果將一串排序過後的數列中的每一項都隨機分到兩個類別中的其中一個，在完成分配後，兩個類別的平均數會有什麼現象？

By ChatGPT

兩類的平均數接近整體平均數

由於數列是排序過的，但分配是隨機的，兩類的數值分布仍然會趨向於數列的整體分布。因此，兩類的平均數大致會接近整體數列的平均數。

兩類的平均數波動較大（相較於原始無序數列

由於數列是排序後的，隨機分配可能會導致某一類中較多極端值（最大或最小值），造成類別間的平均數有較大的波動。特別是數列長度較短時，這種波動會更明顯

數列極端值影響較大

若數列包含極端值（例如長尾分布），隨機分配可能導致其中一類獲得較多極端值，使其平均數偏離整體平均數更明顯

當數列長度夠長時，兩類平均數趨於相等

根據大數法則，當數列長度夠大，隨機分配後，兩類中的數據分布會更接近整體數列的分布，因此兩類的平均數會更加接近整體數列的平均數，平均數之間的差距會減小。

改善

綜上所述，我目前參考其他版本並對其進行修改，但因我對於常數時間檢驗的理解與其實作方式有所不同。我認為，檢驗 q_insert_head / tail 以及 q_remove_head / tail 是否符合常數時間執行的核心在於 佇列長度變化時，執行時間是否仍能維持恆定。也就是說，當佇列長度發生改變時，這些操作是否仍能在固定的時間內完成。

然而，其實作方式則是透過 檢測在相同長度的佇列上，對相同長度的隨機字串與固定字串的操作是否能以常數時間執行。該方法的核心在於：比較固定輸入與隨機輸入的執行時間是否存在顯著差異，來判斷演算法是否符合常數時間特性。

此外，其文中也提到，若固定字串的長度與隨機字串不同，則檢測結果將顯示該操作並非常數時間執行，這進一步證明了輸入的長度確實會影響執行時間。因此，在調整為我的測試目標時，也需特別注意字串長度需保持固定，以免混淆真正的測試重點——佇列長度對執行時間的影響。

與原實作差異分析

在這個分析中，我比較了兩種不同的方式來設定佇列長度，並在測量CPU週期進行佇列操作時進行比較。這兩種方法分別對應原版本及改善版本：

預先準備的佇列：在測量開始之前，佇列會先被初始化為隨機確定的長度。
即時初始化：佇列長度會在進行測量操作之前動態確定並填充。

目標是了解佇列準備方法是否會影響CPU週期測量的準確性和一致性。

By ChapGPT

1. 預先準備的佇列

由於佇列在測量之前已經填充了隨機長度，因此唯一被計時的操作是單一的插入或移除操作。

減少了測量中的變異性，因為佇列在計時開始前已經處於預期狀態。

確保 CPU 週期的測量主要集中於所要測量的操作，最小化了記憶體分配或列表重構的影響。

2. 即時初始化

佇列長度在測量之前動態確定並填充。

這會在計時開始之前引入額外的操作，可能會導致不一致性。

測量的 CPU 週期不僅包括主要操作（插入/移除），還可能受到任何來自動態調整佇列大小的開銷。

單一操作時間的觀察與理論影響

使用預先準備的佇列時，測量僅專注於目標操作，從而更清楚地評估佇列長度如何影響執行時間。

使用即時初始化時，測量中會受到額外處理的影響，這使得更難單獨分析佇列長度對操作執行時間的影響。

雖然預先準備佇列可以使測試結果正確，但卻會造成總測試時間變得非常長，約20分鐘，相對原版本非常慢，尚未對原因進行詳細分析，待補

改良原版本

commit 5892896

本地端測試可通過，但上傳 github 無法成功通過，或許是因為 usleep 的參數是根據經驗設定，這不是個好方案。
參考

研讀 Linux 核心原始程式碼的 lib/list_sort.c

參考
 參考
先根據目前閱讀紀錄下一個推論

討論三種合併排序的變體，分別是

Top Down Merge sort
Bottom Up Merge sort
Queue-Mergesort

對於 1 與 3兩者具有會具有最少的比較次數，而 2 對 cache 最友善。
而 Linux kernel 的做法是對 Bottom Up Merge sort 的合併策略進行改良使其可以具有更少的比較次數(2:1)

2025q1 Homework1 (lab0)

開發環境

實作指定佇列操作

q_new

q_free

q_insert_head / q_insert_tail

q_remove_head / q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse / q_reverseK

q_ascend / q_descend

q_sort

q_merge