HackMD
2025q1 Homework1 (lab0)
contributed by < Max042004 >
開發環境
$ 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
- 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
可以看到與之前記憶體用量相比，用量少了大概 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();
}
實作 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 值很小時（通常小於事前設定的顯著水準 α），意味著在虛無假說下觀察到這樣的數據的可能性極低，因而我們傾向於拒絕虛無假說。
在此份檢驗：
- 宣稱打亂結果符合 uniform distribution
- 顯著水準採用0.05
檢驗方式採用 Pearson's chi-squared test 檢驗某特定事件在樣本中觀察到的頻率分佈是否與特定理論分佈一致 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，與先前的測試並沒有很大的差距，結論依然能得到不拒絕虛無假說
- 那我好奇使用
srand(os_random(getpid() ^ getppid()));的必要性在哪，有更好的測試能看出差距嗎？- 目前的統計方式檢驗是否足夠好？
亂度
在 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 就越高
對於一分佈而言，因
，Entropy 的極大值發生在
所以將熵用於評估亂度在於計算當前訊息的熵與其最大可能熵的差距有多大
比如1 byte char 的大小為
熵的用途除了計算亂度以外，另一個用途是根據訊息的機率分布去計算訊息編碼所需要的平均編碼長度。
比如單純由英文字母組成的字串，每一個字母出現的次數乘以其編碼所需的 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 越接近 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()。
發現在 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 百分位數的數據。
tiny-web-server
這是一個小型的 server 實作，於是我好奇 server 的底層運作原理是什麼。我請 Chatgpt Deep Research 給我快速的講解:
