HackMD
2025q1 Homework1 (lab0)
contributed by <hahaB7>
開發環境
$ 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 命令
研讀論文〈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)
