# 2025q1 Homework1 (lab0)
contributed by < `Hande1004` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
~$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
供應商識別號： AuthenticAMD
Model name: AMD Ryzen 9 7940HS w/ Radeon 780M Graphics
CPU 家族： 25
型號： 116
每核心執行緒數： 2
每通訊端核心數： 8
Socket(s): 1
製程： 1
Frequency boost: enabled
CPU(s) scaling MHz: 32%
CPU max MHz: 5263.0000
CPU min MHz: 400.0000
BogoMIPS: 7985.24
Virtualization features:
虛擬： AMD-V
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 8 MiB (8 instances)
L3: 16 MiB (1 instance)
NUMA:
NUMA 節點： 1
NUMA node0 CPU(s)： 0-15
```
## 針對佇列操作的程式碼實作
### q_new
使用 `list_head` 指標 `head` 指向一個大小等於 `list_head` 結構體的記憶體空間，然後透過 Linux 提供的 `INIT_LIST_HEAD()` 巨集，將 `head` 的 `next `和 `prev` 指向自身，以初始化為一個空的佇列。
### q_free
使用兩個 `list_head` 指標 `pos` 和 `safe`，並透過 `list_for_each_safe()` 巨集走訪佇列中的每個節點。在走訪過程中，先使用 `list_del()` 將當前節點從鏈結中移除，然後調用 `q_release_element()` 釋放該節點的記憶體。最後，釋放 `head` 所佔用的記憶體。
### q_insert_head
使用 `strdup()` 函式將指標 `s` 所指向的字串複製到 `node->value`（即 `element_t *node` 所指向的記憶體空間）。接著，透過 `list_add()` 將此節點插入到 `head` 之後，使其成為鏈結串列的第一個元素。
### q_insert_tail
使用 `strdup()` 函式將指標 `s` 所指向的字串複製到 `node->value`（即 `element_t *node` 所指向的記憶體空間）。接著，透過 `list_add()` 將此節點插入到 `head` 之前，使其成為鏈結串列的最後一個元素。
### q_remove_head
使用 `list_del()` 斷開此鏈結串列的第一個元素，然後將 `node->value`（即 `element_t *node` 所指向的記憶體空間） 所指向的字串複製最多 `bufsize - 1` 個字元到 `sp` 所指向的字串中，最後將 `sp[bufsize - 1]` 設置為 `'\0'` 以確保字串結尾。
### q_remove_tail
使用 `list_del()` 斷開此鏈結串列的最後一個元素，然後將 `node->value`（即 `element_t *node` 所指向的記憶體空間） 所指向的字串複製最多 `bufsize - 1` 個字元到 `sp` 所指向的字串中，最後將 `sp[bufsize - 1]` 設置為 `'\0'` 以確保字串結尾。
### q_size
用 `list_for_each()` 走訪每個節點，用計數器 `n` 來計算走過幾個節點，最後得到這個鏈結串列的總共元素數目。
### q_delete_mid
計算 `(q_size(head) - 1) >> 1` 來獲取走訪至鏈結串列中點所需的步數。接著，使用 `list_for_each()` 走訪節點，當走訪次數達到計算出的中點位置時，刪除該節點。
### q_delete_dup
使用 `list_for_each_safe()` 走訪鏈結串列，透過 `pos` 來走訪節點並用 `safe` 記錄下一個節點以防止刪除節點後影響迭代，同時使用 `dup` 變數來標記是否處於重複區間，當發現當前節點與下一個節點相同時，設定 `dup = true` 並刪除當前節點，而當 `dup == true` 且當前節點與下一個節點不同時，則代表重複區間結束，需要刪除該區間最後一個重複的節點，最後若 `dup == true`，則再刪除最後一個重複的節點，以確保鏈結串列中不再存在重複元素。
### q_swap
透過 `pos` 走訪節點並用 `safe` 記錄下一個節點，當 `pos` 和 `safe` 都未到達 `head` 時，則刪除 `pos` 並將其插入到 `safe` 之前，依此方式逐步交換相鄰節點，最終實現兩兩交換鏈結串列中的元素。
### q_reverseK
使用 `q_size(head)` 計算節點數 `num`，確保只反轉完整的 `k` 組節點，並將 `pos` 設為 `head->next` 開始反轉每組反轉時先紀錄 `first` 作為該組的第一個節點以便後續連接，再記錄 `first_prev` 以確保反轉後能重新串接，並透過指標的指標 `first_next` 指向 `first->next`來確保第一個節點能夠，然後使用 `m` 來追蹤當前 `k` 組內的節點索引。
```c
struct list_head *pos = head->next, *safe, *first, *first_prev;
int num = q_size(head);
for (int i = 0; i < num / k; i++) {
struct list_head **first_next = NULL;
int m = 0;
for (safe = pos->next; m < k; pos = safe, safe = pos->next, m++) {
```
當 `m == 0`；
每組反轉時先紀錄 `first` 作為該組的第一個節點以便後續連接，再記錄 `first_prev` 以確保此組的最後一個節點反轉後可以接到正確的 `prev`，並透過指標的指標 `first_next` 指向 `first->next`來確保走訪到此組最後一個節點時，第一個節點能夠更改 `next`的地址。
```c
struct list_head *next = pos->next;
struct list_head *prev = pos->prev;
if (m == 0) {
first = pos;
first_prev = prev;
first_next = &pos->next;
pos->prev = next;
continue;
}
```
當`0 < m < k-1` 的過程中；
`pos->prev`指向 `next`、`pos->next` 指向 `prev` 來進行反轉。
```c
if (0 < m && m < k - 1) {
pos->prev = next;
pos->next = prev;
continue;
}
```
直到 `m == k-1` 時完成該組反轉；
將 `pos->prev` 指向 `first_prev` 和`first_prev->next`指向`pos`以確保此組新的第一個節點與前一組的最後一個節點相互鏈結；`first_next` 指向 `next` 讓此組新的最後一個節點能正確連接到下一組的第一個節點且`next->prev` 指向 `first` 以確保雙向鏈結正確，最後將 `pos` 移動到 `next` 以進入下一組的反轉。
```c
if (m == k - 1) {
pos->next = prev;
pos->prev = first_prev;
*first_next = next;
first_prev->next = pos;
next->prev = first;
pos = next;
break;
}
```
### q_sort
這部分我原先是用 insert sort 的方式去做，可惜過不了 `make test` 的時間複雜度測試，後來改用老師給的參考資料 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 中的 merge 演算法來做，其中分為三個函式，分別為 `q_sort()` 、 `mergeSortList()` 、 `merge()`。
第一步 `void q_sort(struct list_head *head, bool descend)` (以降序為例):
我將原本環狀的鏈結串列切成雙向非環狀的鏈結串列，好讓後面 `merSortList()` 函式在做分割的時候可以更好找到截止點，且用非環狀的鏈結串列去比照老師的參考資料也比較好理解(參考資料為單向非環狀的鏈結串列)。
```c
struct list_head *first_node = head->next;
struct list_head *last_node = head->prev;
first_node->prev = NULL;
last_node->next = NULL;
struct list_head *merge_pos = mergeSortList(first_node, descend);
```
第二步 `struct list_head *mergeSortList(struct list_head *node, bool descend)` :
使用快慢指標將鏈結串列的中點找到，從中點將其拆分成兩個部分，接著用函式遞迴的方式不斷的拆分此鏈結串列，直到無法繼續拆分為止(只剩下單一節點)，最後將這些拆分後的節點與鏈結串列傳入 `merge()` 中。
```c
struct list_head *fast = node->next;
struct list_head *slow = node;
// split list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
if (fast) {
fast->prev = NULL;
}
// sort each list
struct list_head *l1 = mergeSortList(node, descend);
struct list_head *l2 = mergeSortList(fast, descend);
return merge(l1, l2, descend);
```
第三步 `struct list_head *merge(struct list_head *l1,
struct list_head *l2,
bool descend)` :
使用一個變數 `struct list_head` `tmp` 來當作此鏈結串列暫時的頭，`*tail = &tmp` 為用來排序時的過度指標，接著將傳入進來的`l1` 和 `l2` 所指向的第一個元素比大小，`value` 比較大的節點會成為 `tail` 指向的位置，接著更新 `tail` 的 `next` 指向 `value` 較大的節點，而 `value` 較大的節點的 `prev` 指向 `tail` ，接著 `value` 大的節點則更新指向其 `next` 的位置。
進入下一輪的比較，重複一樣的動作，直到 `l1` 或 `l2` 其中一個指標指向 `NULL` 就跳出迴圈。
```c
while (l1 && l2) {
const element_t *node1 = list_entry(l1, element_t, list);
const element_t *node2 = list_entry(l2, element_t, list);
if (strcmp(node1->value, node2->value) >= 0) {
tail->next = l1;
l1->prev = tail;
tail = tail->next;
l1 = l1->next;
} else {
l2->prev = tail;
tail->next = l2;
tail = tail->next;
l2 = l2->next;
}
}
```
這時還會剩下最後一個節點沒有被鏈結，所以要把 tail 跟指向最後一個節點的指標相互鏈結，最後把 tmp.next(此排序好的鏈結串列的第一個節點的指標) 回傳。
```c
if (l1) {
tail->next = l1;
l1->prev = tail;
}
if (l2) {
tail->next = l2;
l2->prev = tail;
}
return tmp.next;
```
最後一步 `void q_sort(struct list_head *head, bool descend)` :
將 `head` 重新鏈結，還原成環狀的雙向鏈結串列。
```c
struct list_head *merge_pos = mergeSortList(first_node, descend);
head->next = merge_pos;
merge_pos->prev = head;
while (merge_pos->next) {
merge_pos = merge_pos->next;
}
merge_pos->next = head;
head->prev = merge_pos;
```
### q_ascend
使用 `list_for_each_safe()` 這個巨集，`pos` 從 `head->prev`（最後一個節點）開始向前走訪，並透過 `safe` 記錄 `pos->prev` 以確保刪除節點後不影響繼續走訪，接著取得 `pos` 所對應的 `element_t *node`，若 `node->value` 大於 `mini_value`（代表該節點值比後方節點大），則使用 `list_del(pos)` 將 `pos` 從鏈結串列中移除並釋放記憶體 `q_release_element(node)`，否則更新 `mini_value = node->value`，確保後續的比較基準維持遞增順序。
### q_descend
`pos` 從 `head->prev`（最後一個節點）開始向前走訪，並透過 `safe` 記錄 `pos->prev` 以確保刪除節點後不影響後續走訪，接著取得 `pos` 所對應的 `element_t *node`，若 `node->value` 小於 `max_value`（代表該節點值比後方節點小），則使用 `list_del(pos)` 將 `pos` 從鏈結串列中移除並釋放記憶體 `q_release_element(node)`，否則更新 `max_value = node->value`，確保後續的比較基準維持遞減順序。
### q_merge
將所傳進來的 k 個 queue 中的鏈結串列依序的接在第一個 queue 的鏈結串列後面，然後使用 q_sort() 對整個 queue做排序。
```c
queue_contex_t *atx = NULL,
*first = list_first_entry(head, queue_contex_t, chain);
list_for_each_entry (atx, head, chain) {
if (atx == first)
continue;
if (atx && atx->q) {
list_splice_tail_init(atx->q, first->q);
first->size += atx->size;
atx->size = 0;
}
}
q_sort(first->q, descend);
```
## 研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c#L1)
在 Linux kernel 中的 `list_sort()` 函式，是一個針對 doubly-linked list 的穩定排序實作，其核心採用一種特殊的 bottom-up merge sort。
在了解他的程式碼之前需要先去理解他的設計哲學。
### 資料結構不變式（Data Structure Invariants）
1. 所有 sublist 都是單向串列（singly linked）
每一個排序好的 sublist 節點中使用 `next` 指標串接，並以 `NULL` 結尾。
在排序的中間過程，`prev` 指標並不會被維護。
1. `pending` 是一個「子鏈結串列的鏈結串列」
用 `prev` 把每一個 sublist 的開頭節點串起來。
pending 本身是一條由「已排序 sublist」所組成的鍊表。
1. 每個 sublist 的大小都是 2 的冪次方
例如：size = 1, 2, 4, 8, ...
這讓我們可以用 `count` 的位元來表示各種大小 sublist 的狀態。
1. `pending` 中的 sublist 依照「從小到大」且「新的在上面」排列
這讓每次要 merge 時，可以用最上層兩個 sublist 直接合併成更大的。
1. 同一種大小最多只會同時存在兩個 sublist\
一旦第三個相同大小的 sublist 加進來，馬上觸發合併。
1. merge 是根據 `count` 的 bit pattern 來決定何時觸發
每次 `count++` 時，若某個 bit（例如 bit 2）從 1 ➝ 0，表示你已經有兩個 size = 4 的 sublist → 觸發 merge 。
這保證每次 merge 的比例不會超過 2:1（最差情況），提升 cache locality 與效率。
7. `count` 的位元表示 sublist 狀態
`count` 是一個整數，每次新增元素時就會加一。它的二進位表示可以直接反映 `pending` 中有哪些大小的 sublist。
每個 bit 表示一個大小為 2^k 的 sublist 是否存在。
bit 為 1 表示有一個該大小的 sublist；最多只會有兩個 → 出現兩個時會觸發合併。
例子：
若 count = 0110（十進位為 6）：
bit1 = 1 → 有一個 size=2 的 sublist
bit2 = 1 → 有一個 size=4 的 sublist
其他 bit = 0 → 無其他大小的 sublist
這表示目前 pending 裡有兩個 sublist，大小分別為 2 和 4。
### `list_sort()` 實作
在 `list_sort()` 中有兩個函式，一個是 `merge()` 負責做 sublist 的單向的合併排序，他會把元素依由小到大的順序排好，並用 `next` 接好；另一個函式是 `merge_final()` 這個函式會把傳進來的鏈結串列的 `next` 和 `prev` 兩個指標都接好，並在最後透過 `tail->next = head;` 和 `head->prev = tail;` 把傳進來的鏈結串列接回成環狀雙向的鏈結串列。
`list_sort()` :
排序過程會把原本 `list` 一個節點取出，並用當前結點的下個節點的 `prev` 指向由`pending` 指向的當前結點 。
`pending` 是一個以排序 sublists 的串列。
用 `prev` 指標將各 sublist 串成一條單向鏈結串列。
每個 sublist 本身是單向、`NULL` 結尾的鍊表（`next` 指標構成）。
```C
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
在每一輪中會先去確認這輪需不需要合併以及要合併哪兩個 sublist ，因為根據設計的規則，每個 sublist 需要是 2 的冪，也就是說如果要合併也必須先確定合併後的 sublist 的數量是 2 的冪；接著要判斷要合併哪兩個 sublist ，根據設計規則最多只能有兩個相同數量的 sublist 所以當出現兩個相同數量的 sublist 時，下次合併就必須先合併這兩個 sublist，而這些判斷的方法就是靠 `bits` 的 `and` 操作，這段程式碼會找出 `count` 最低位的 0，代表該位以下已累積兩個 sublist，因此找出這兩個 sublist 並合併之。
```c
struct list_head **tail = &pending;
...
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
找到該合併的兩個 sublist 後，會對其進行合併排序，並把排序好的 sublist 新的開頭節點接回原本舊的開頭節點接到的地方 ( `a->prev = b->prev` )，再用 `*tail` 去連接這個 sublist 跟 `pending` 的連結。
```c
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
}
```
由於程式為了實現最差合併狀況數量比例 2:1 及 避免 cache thrashing 的問題有了這樣 `pending` 的實作，但即使 `pending` 的部分就能做合併排序了，他依然是遵照 `count` 來判斷是否合併的，所以是有可能出現跳出迴圈後，並沒有將所有的 sublist 全部合併成一個鏈結串列的問題，所以需要在跳出迴圈後補完整個合併的實作。
```c
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
但即使如此依然沒有將 `prev` 接好，以及接回環狀，因此，這段程式碼保留了第一段 sublist 跟剩餘的 `list` 做最後的合併排列，在這個合併排列中會把這個鏈結串列接回環狀雙向的。
```c
merge_final(priv, cmp, head, pending, list);
```
## 在 qtest 提供新的命令 shuffle
使用老師給的參考資料[Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)所使用的方法來實作 shuffle 這個指令。
### 運作方式說明:
假設總共有 i 個節點。
1. 先從這 i 個節點中隨機找出一個第 1 個到第 i - 1 的 的節點。
2. 將這個節點與第 i 個節點交換。
3. i = i - 1
4. 重複以上階段 1 、2、3 直到做到 i = 1 就結束。
### 程式實作:
`i_pos` 當作要被交換的節點。
`j_pos` 為隨機取第 `1` 個節點到第 `i - 1` 個的節點。
接著來要判斷兩個是否相鄰，若兩者不相鄰需要使用兩次 `list_move()` 將 `j_pos` 與 `i_pos` 分別移動至對方指向的位置；但如果兩者相鄰，那做兩次 `list_move()` 將無意義，因為會換回原本的位置，所以只須做一次 `list_move()` 即可。
```c
struct list_head *j_prev = j_pos->prev;
struct list_head *i_prev = i_pos->prev;
if (i_prev == j_pos) {
list_move(j_pos, i_pos);
} else {
list_move(i_pos, j_pos);
list_move(j_pos, j_prev);
}
```
### 統計方法驗證 `shuffle`
> 參考老師的作業的[2025 年 Linux 核心設計課程作業 —— lab0 (D)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d)
>
因為 [Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 能檢驗虛無假說（Null hypothesis），所以可以由此來驗證我的 shuffle 函式是否符合 Uniform distribution。
+ $H_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
+ $H_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同
#### 1. 計算 chi-squared test statistic $X^2$
$$
X^2 = \sum_{i=1}^n {(O_i - E_i)^2 \over E_i}
$$
+ $X^2$: Pearson's cumulative test statistic
+ $O_i$: the number of observations of type i
+ $E_i$: the expected count of type i
```
Expectation: 41666
Observation: {'1234': 41324, '1243': 41704, '1324': 41676, '1342': 41627, '1423': 41643, '1432': 41792, '2134': 41805, '2143': 41490, '2314': 41791, '2341': 41378, '2413': 41372, '2431': 41737, '3124': 41460, '3142': 41780, '3214': 41581, '3241': 41821, '3412': 41724, '3421': 41477, '4123': 42010, '4132': 41631, '4213': 41774, '4231': 41774, '4312': 41719, '4321': 41910}
chi square sum: 16.98694379110066
```
$X^2$ = 16.98694379110066
#### 2. 決定自由度（degrees of freedom）
因為 4! = 24 ，所以自由度為 23（可自由變換的變數只有 23 個）。
#### 3. 選擇顯著水準
+ [顯著水準（Significance level）](https://en.wikipedia.org/wiki/Statistical_significance) α = P(拒絕 $H_0$ | $H_0$ 為真)
alpha 設定為常見的 0.05。
[Table: Chi-Square Probabilities](https://people.richland.edu/james/lecture/m170/tbl-chi.html) 我的自由度為 23 ， 14.842 < $X^2$ = 16.98694379110066 < 32.007 ，故 P value 介於0.9 和 0.1 之間。
#### 4. 統計檢定的結果不拒絕虛無假說
因為P value（0.9~0.1）> alpha（0.05），統計檢定的結果不拒絕虛無假說（$H_0$）
### 測試程式
測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖：
由此可知 shuffle 確實呈現均勻分佈
## 設計一組新的 PRNG 命令
為了設計一組新的命令可以用來切換不同 PRNG 的實做，需要先了解原指令的 `ih RAND 10` 是怎樣實做出來的，原先我對於這部份該怎樣做是沒想法的，後來參考了 [wurrrrrrrrrr](https://hackmd.io/@Guanchun0803/linux2025-homework1#%E6%AF%94%E8%BC%83%E4%BA%82%E6%95%B8%E7%94%A2%E7%94%9F%E5%99%A8-Xorshift-vs-%E5%85%A7%E5%BB%BA-%E7%9A%84%E5%93%81%E8%B3%AA) 的分析後了解到要將 `ih RAND 10` 這串指令實做有幾個重要的函式。
### 如何拆解一組命令
首先是 `interpret_cmd()` 這串指令會將傳進來的命令用 `parse_args()` 來拆解成不同的字串，並用 `argv[]` 這個指標去指向拆解下來的不同字串，再把這些不同的字串指標的指標傳進 `interpret_cmda()` 裡面去執行每個命令（console.c)。
`static bool interpret_cmd(char *cmdline)` :
```c
char **argv = parse_args(cmdline, &argc);
bool ok = interpret_cmda(argc, argv);
```
`static char **parse_args(char *line, int *argcp)`:
這段函式將傳進來的整段命令做分解，並透過空白的字串去判斷哪些部份是需要被拆開的，把拆開的部份用 `\0` 做取代。
```c
while ((c = *src++) != '\0') {
if (isspace(c)) {
if (!skipping) {
/* Hit end of word */
*dst++ = '\0';
skipping = true;
}
} else {
if (skipping) {
/* Hit start of new word */
argc++;
kipping = false;
}
*dst++ = c;
}
}
```
接著把用 `\0` 做區分好的字串依序存入新開好的記憶體空間，並 `argv[]` 這個指標來存取。
```c
for (int i = 0; i < argc; i++) {
argv[i] = strsave_or_fail(src, "parse_args");
src += strlen(argv[i]) + 1;
}
```
也就是說會將 `ih RAND 10` 這個命令拆解成 `ih` 、`RAND` 、 `10` 三個字串，並依序用 `argv[0]` 、 `argv[1]` 、 `argv[3]` 三個指標來指向。
`static bool interpret_cmda(int argc, char *argv[])` :
將整段命令處理好後，此函式就是要將每個命令依序去執行，首先要先判斷使用者輸入的第一個字串是否是屬於在原先設定的命令集裡面，因此要去判斷 `arg[0]` 是否等於命令集中的某個命令。
```c
while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
next_cmd = next_cmd->next;
```
如果有在命令集中，也就是使用者輸入的命令正確，那就會將裡面的命令執行
```c
if (next_cmd) {
ok = next_cmd->operation(argc, argv);
if (!ok)
record_error();
}
```
### 實際執行命令
了解完電腦如何拆解命令後，需要知道怎樣讓這些命令實際運作，這裡也有幾個函式來達成這件事。
`static bool queue_insert(position_t pos, int argc, char *argv[])` :
在這個函式中會去判斷使用者是否有輸入 `RAND` 如果有那就會將 `need_rand` 設為 `true`。
```c
if (!strcmp(inserts, "RAND")) {
need_rand = true;
inserts = randstr_buf;
}
```
接著如果 `need_rand` 為 `true` 就會調用 `fill_rand_string` 來隨機填充字串。
```c
if (need_rand)
fill_rand_string(randstr_buf, sizeof(randstr_buf));
```
`static void fill_rand_string(char *buf, size_t buf_size)` :
這段函式會先去設定隨機的字串長度
```c
len = rand() % buf_size
```
接著調用 `randombytes()` 來得到一個隨機數，此隨機數主要是用 linux `<sys/random.h>` 中的函式 `getrandom()` 來實做的。
透過隨機數除餘的方法將每個字元隨機填入 a 到 z 來達到生成隨機字串的方法。
```c
static const char charset[] = "abcdefghijklmnopqrstuvwxyz"
...
for (size_t n = 0; n < len; n++)
buf[n] = charset[randstr_buf_64[n] % (sizeof(charset) - 1)];
buf[len] = '\0';
```
在 `q_show` 中，有去判斷是否要用`shannon_entropy.c` 來計算隨機生成字串的熵，如果使用者有輸入 `option entropy 1` 就會將 `show_entropy` 設定為 `1` 。
```c
if (show_entropy) {
report_noreturn(
vlevel, "(%3.2f%%)",
shannon_entropy((const uint8_t *) e->value));
}
```
### Xorshift
了解隨機生成字串的命令跟實做後，便可以真正得來新增指令了，為了新增指令，我額外新增了一個檔案，`xorshigt.c` 來負責實做新的指令，我的新指令是將原本 `linux_getrandom()` 的部份額外增加了 `xorshift` 的操作，之所以採用這種方式，是因為 xorshift 在執行時需要一個起始的隨機值。若改用 rand() 或其他隨機來源，會導入額外變因，導致與原始 getrandom() 的隨機性比較不再公平。
為了保持比較的一致性與公平性，我選擇在 `linux_getrandom()` 所產生的隨機數上進行 `xorshift()` 處理，這樣可以確保兩者僅有「是否經過額外處理」這一個變數，從而更純粹地比較是否能提升或影響隨機性。
```c
for (int i = 0; i < chunk / sizeof(uint64_t); i++) {
uint64_t *x = (uint64_t *) buf;
x[i] ^= (x[i] << 13);
x[i] ^= (x[i] >> 7);
x[i] ^= (x[i] << 17);
}
```
在原先的 `queue_insert()` 中去增加 `xorshift` 的判斷
```c
if (!strcmp(inserts, "xorshift")) {
need_rand = true;
inserts = xorshiftstr_buf;
}
```
並參考原先的 `fill_rand_string()` 的方式，來新增 `fill_rand_string_xorshift` 以填充字串。
再去判斷使用者輸入的是哪個命令，來調用 `fill_rand_string()` 或 `fill_rand_string_xorshift`
```c
if (need_rand) {
if (inserts == randstr_buf) {
fill_rand_string(randstr_buf, sizeof(randstr_buf));
} else if (inserts == xorshiftstr_buf) {
fill_rand_string_xorshift(xorshiftstr_buf, sizeof(xorshiftstr_buf));
}
}
```
最後順利實做出能夠切換兩個 `PRNG` 的指令
```
cmd> new
l = []
cmd> option entropy 1
cmd> ih RAND 10
l = [zxgnqillh(35.94%) foevg(26.56%) dtnwspo(32.81%) nmxjvtmt(29.69%) llwnksm(29.69%) romzqnusa(37.50%) fsdsx(21.88%) phciq(26.56%) xrtryph(29.69%) dpydskf(29.69%)]
cmd> free
l = NULL
cmd> new
l = []
cmd> option entropy 1
cmd> ih xorshift 10
l = [rcmlxrp(29.69%) jtuixphs(35.94%) tyscvln(32.81%) izngzv(26.56%) zsmhcowy(35.94%) fjdqiz(29.69%) eeurynhcm(35.94%) pgwfc(26.56%) efjout(29.69%) ohsqrqwtp(35.94%)]
```
### 用統計工具 [dieharder](https://github.com/seehuhn/dieharder) 檢測兩個 PRNG 命令
為了比較兩種隨機數產生方式的品質，我分別用 `linux_getrandom()` 和自己實作的 `xorshift()` ，各自產生 10,000 筆二進位隨機資料（共約 10MB），再透過 Dieharder 工具進行測試。Dieharder 提供超過 100 種統計測試，會輸出 p-value 判斷是否隨機。我根據各自通過的測試數與 p-value 的分布，評估哪一種方法更具隨機性。
### 測試結果彙整表
| 隨機數產生器 | PASSED | WEAK | FAILED | 總測試數 |
|--------------|--------|------|--------|-----------|
| linux_getrandom | 63 | 15 | 36 | 114 |
| xorshift | 59 | 16 | 39 | 114 |
由實驗結果可見，原本的 `linux_getrandom()` 隨機數產生器整體表現略優於經過 `xorshift()` 擴充後的版本。雖然兩者在 Dieharder 測試中的通過數相差不大，但 `xorshift()` 結果中 `FAILED` 次數略多，顯示其隨機性並未因為加入後處理而提升。
值得注意的是，本次 `xorshift()` 的實作其實是建立在 `linux_getrandom()` 所產生的資料上，再進一步對這些資料進行簡單的 `xorshift()` 運算處理。然而，這樣的後處理不但未能增加隨機性，反而在部分測試中造成更多失敗。
推測原因：原本的 `getrandom()` 產生的隨機數更為隨機，加上 `xorshift` 應用反而破壞了原本的隨機性。
這顯示：將一個品質已高的 PRNG 輸出再次加工，未必能提升隨機性，反而可能因為額外的數學運算引入偏差，降低其統計測試的通過率。
## 用Valgrind分析記憶體問題
當我寫完 `queue.c` 後，我就開始測試 `make test` 但出現了這樣的錯誤訊息：
```
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-13-malloc 0/6
```
這讓我花了滿多時間，因為一開始我不知道這個究竟是錯在程式碼的哪邊，後來我就使用 Valgrind 這個工具幫我分析 `make valgrind` 得到這樣的提示：
```
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
==15555== Invalid write of size 8
==15555== at 0x10FF89: INIT_LIST_HEAD (list.h:88)
==15555== by 0x10FF89: q_new (queue.c:18)
==15555== by 0x10D18F: do_new (qtest.c:155)
==15555== by 0x10E929: interpret_cmda (console.c:181)
==15555== by 0x10EEEE: interpret_cmd (console.c:201)
==15555== by 0x10F17D: cmd_select (console.c:593)
==15555== by 0x10FA5B: run_console (console.c:673)
==15555== by 0x10DD18: main (qtest.c:1494)
==15555== Address 0x8 is not stack'd, malloc'd or (recently) free'd
```
接著我去看了我的 `q_new` 才意識到我漏掉題目的一個關鍵條件：
```
Return: NULL for allocation failed
```
但我的程式碼當時並沒有
```c
if (!head)
return NULL;
```
因此就發生錯誤了。
### Massif 視覺化 "simulation" 過程中的記憶體使用量
> 在這邊參考 [HenryChaing](https://hackmd.io/@Henry0922/linux2025-homework1#%E9%81%8B%E7%94%A8-Address-Sanitizer-%E9%99%A4%E9%8C%AF) 測試 traces/trace-017-complexity.cmd 這個檔案。
```
MB
1.535^ #
| @ @ @ :#
| @ @ @ @ @ :#
| @ @ @: @ @ :#
| : @ @ @ @ @: : @ @ :#
| : @: @ @ @ @: : @ @ :#
| : @: @ : @ @ @: : @ : @:::#
| : @: @ : @ @ @: : : @ ::@:::#
| :: @::: @ : :: @ @ :@: : : @: ::@:::#
| :: @:: @ : :: ::::@ @ :@: : : @::::@:::#
| :: @:: @ : : : ::: @ @::@: : ::@::::@:::#
| :: @:: @ : @ : : : : ::: @ @::@: : ::@::::@:::#
| ::: @:: @ : @ : : : : ::: @ @::@::: ::@::::@:::#
| ::: @:: :@ : : @ :: : : : : :::: @ @::@::: ::@::::@:::#
| ::: @:: :@ : : @ ::: : : : :: : : :::: @: @::@::::::@::::@:::#
| ::: @:: :@ : : @ ::: :: ::::::: : : :::: @::@::@::::::@::::@:::#
| ::: @:: :@ : : @ @:::::: ::::::: : : :::: @::@::@:::::@@::::@:::#
| ::::@:: :@@: ::@ @::::::@:::::::::: ::::::: @::@::@:::::@@::::@:::#
|:: ::::@:: :@@:::::@:@::::::@:::::::::: ::::::: @::@::@:::::@@::::@:::#
|::::::::@:: :@@:: ::@:@::::::@:::::::::: ::::::: @::@::@:::::@@::::@:::#
0 +----------------------------------------------------------------------->Gi
0 62.36
Number of snapshots: 89
Detailed snapshots: [8, 12, 13, 18, 20, 27, 47, 50, 57, 67, 69, 79, 87 (peak)]
```
觀察最高記憶體的 snapshot（87） 發現
```
89.54% (1,441,027B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->69.40% (1,116,934B) 0x10FBC2: alloc (harness.c:146)
| ->69.40% (1,116,934B) 0x10FD15: test_malloc (harness.c:176)
| ->39.71% (639,168B) 0x11010D: q_insert_head (queue.c:42)
```
heap allocation functions 中佔了最高的記憶體。
## 研讀論文[〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf)
### 研究動機
現代的加密程式或安全性相關程式，若在執行速度上「會隨著密鑰或秘密資料而改變」，就會暴露出潛在的「時間側通道攻擊（Timing Side-Channel Attack）」風險。
在這類攻擊中，攻擊者僅透過量測目標程式的「執行時間」就可能推測到程式內部的秘密資訊。因此，許多密碼函式都強調必須實作為「常數時間」：也就是不論輸入或密鑰是什麼，整個程式的執行速度都應該「幾乎」相同。
驗證一個程式究竟是否真「常數時間」並不容易。因為現代CPU的微架構（cache、分支預測、管線、微碼更新…）都可能造成執行時間的微小變動。
因此，作者提出名為 dudect 的工具，來自動且統計式地檢測一段程式在真實硬體上執行時，是否具有可觀測的「執行時間差異 (timing leakage)」。
此作法不是用靜態分析或硬體模型，而是直接在目標平台上對程式進行大量測試，並且應用統計檢定來檢查是否存在對「輸入資料」敏感的時間差異。
### 核心原理
該論文主張的檢測流程可以總結為「三步驟」
1. 測量執行時間
在同一個平台、同一個執行環境下，對欲測試的函式進行大量次的呼叫，每次呼叫都記錄「起始時間」與「結束時間」，計算出該次呼叫的執行週期或毫秒數。
為了檢測時間是否因「輸入資料」而改變，他們會準備「兩類」輸入:
第一類：固定輸入（例如全 0、或某固定模式）
第二類：隨機輸入（每次都重新生成隨機值）
2. 預處理
先將「測得的時間」做一些預處理，例如「過濾掉極端大值」。目的是盡量讓後續的統計檢定更穩定，更能聚焦在「執行時間是否與輸入有關」。
3. 統計檢定
最常用的是 Welch’s t-test：檢驗「這兩組測量（固定輸入 vs. 隨機輸入）」在平均值上是否具有顯著差異。
若統計結果顯示差異顯著，代表程式的執行時間很有可能因輸入而有所不同；也就是說它「可能不是真正的常數時間」。
若未觀察到顯著差異，則在某個信心水平下，可以暫時認為程式在該平台可能是常數時間 — 但要注意，這是統計檢定，並不是絕對保證。
### lab 0
在此作業中，使用的是Welch's t-test的方法。
輸入為兩類的執行時間:
執行時間 = 結束時間 - 起始時間
```c
static void differentiate(dudect_ctx_t *ctx)
{
for (size_t i = 0; i < N_MEASURES; i++)
ctx->exec_times[i] = ctx->after_ticks[i] - ctx->before_ticks[i];
}
```
類 1 : $X_1, X_2, \dots, X_{n_1}$ (固定輸入， class = 0)
類 2 : $Y_1, Y_2, \dots, Y_{n_2}$ (隨機輸入， class = 1)
m2 為累積平方和偏差。
n 為每組的樣本數。
```c
void t_init(t_context_t *ctx)
{
for (int class = 0; class < 2; class ++) {
ctx->mean[class] = 0.0;
ctx->m2[class] = 0.0;
ctx->n[class] = 0.0;
}
return;
}
```
### 分別計算平均值:
$$\bar{X} = \frac{1}{n_1} \sum_{i=1}^{n_1} X_i, \quad
\bar{Y} = \frac{1}{n_2} \sum_{j=1}^{n_2} Y_j$$
### 用 Welford’s method 線上更新累積平方和偏差(用來計算變異數):
delta : $\delta = x - \bar{m}$
新的平均：$\bar{m}' = \bar{m} + \frac{\delta}{n}$
更新$M2' = M2 + \delta \times (x - \bar{m}')$
```c
void t_push(t_context_t *ctx, double x, uint8_t class)
{
assert(class == 0 || class == 1);
ctx->n[class]++;
/* Welford method for computing online variance
* in a numerically stable way.
*/
double delta = x - ctx->mean[class];
ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
}
```
### 計算 Welch’s t-test 的 t 線上統計量
1. 計算變異數:
$$s_X^2 = \frac{m2[0]}{n[0] - 1}, \quad s_Y^2 = \frac{m2[1]}{n[1] - 1}.$$
1. 計算Welch’s t-test 的 t 值:
$$
t_{\text{online}} =
\frac{\bar{X}_{\text{(so far)}} - \bar{Y}_{\text{(so far)}}}
{\sqrt{\frac{s_X^2}{n_1} + \frac{s_Y^2}{n_2}}}
$$
若 $∣t∣$ 足夠大（大於一個臨界值），可拒絕「兩組平均相等」的假設（null hypothesis），表示兩組數據之間具有顯著差異。
在程式應用中，程式會不斷收集新測量值，對固定輸入 (class=0) 與隨機輸入 (class=1) 分別計算目前累積下來的平均與變異數。每次更新後，都可立刻算出一個新的 t-value。
隨著測量次數 $n1 + n2$ 的增加，$|t_{online}|$ 是否越來越大。若是越來越大且超過門檻，代表確實存在顯著差異；若始終維持在小範圍，則暫時無法排除它是常數時間（或差異極微小，以至需要更多測量才能看出）。
```c
double t_compute(t_context_t *ctx)
{
double var[2] = {0.0, 0.0};
var[0] = ctx->m2[0] / (ctx->n[0] - 1);
var[1] = ctx->m2[1] / (ctx->n[1] - 1);
double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;
return t_value;
}
```
### 判斷是否為常數時間
藉由比較算出來的 $t$ 值與判定常數時間的臨界值來決定是否為常數時間。
臨界值 :
```c
/* threshold values for Welch's t-test */
enum {
t_threshold_bananas = 500, /* Test failed with overwhelming probability */
t_threshold_moderate = 10, /* Test failed */
};
```
判定是否為常數時間 :
```c
double max_t = fabs(t_compute(t));
/* Definitely not constant time */
if (max_t > t_threshold_bananas)
return false;
/* Probably not constant time. */
if (max_t > t_threshold_moderate)
return false;
/* For the moment, maybe constant time. */
```
### 使程式碼具備 percentile 的處理
在原本的 `lab 0` 中是不具備 percentile 的處理，而 percentile 在原作者的 `dudtect` 中的應用是為了去除極端大值，讓後續的統計檢定更穩定。
所以在這個部份我將 percentile 的應用加入至此作業中。
[Percentile](https://en.wikipedia.org/wiki/Percentile)（百分位數）在統計學中指的是「將一組數值依大小排序之後，取出某一百分比位置所對應的數值」。
例如：
第 50 個百分位數（50th percentile, 也稱為中位數）就是那個使得「有一半（50%）的樣本值都小於等於它」的數值。
而此論文的方法是計算多個百分數位(目前設定為100)，並將這些百分數位設為不同的閥值，每個閥值會去儲存低於這個百分數位的執行時間。如此就等於同時做100 種裁剪門檻。
之所以要這麼設定是因為 :
某些門檻太低時，將捨棄掉大量量測，可能很快收斂於可檢測出差異；也可能不夠樣本數。
某些門檻太高時，捨棄量偏少，不容易清除雜訊。
因次，會去進行挑選哪個百分位數是最適合的。
而此文挑選的方法是去選擇哪個百分位能夠算出最大的 $t$ 值 :
```c
static ttest_ctx_t *max_test(dudect_ctx_t *ctx) {
size_t ret = 0;
double max = 0;
for (size_t i = 0; i < DUDECT_TESTS; i++) {
if (ctx->ttest_ctxs[i]->n[0] > DUDECT_ENOUGH_MEASUREMENTS) {
double x = fabs(t_compute(ctx->ttest_ctxs[i]));
if (max < x) {
max = x;
ret = i;
}
}
}
return ctx->ttest_ctxs[ret];
}
```
而在這個 dudect 的程式碼中會用 `percentile()` 來計算百分位數並回傳至`prepare_percentiles()` 裡的 `ctx->percentiles[i]` 儲存起來。
跟 `lab 0` 不同的是 `update_statistics()` 也需要更新閥值內的成員:
```c
int64_t difference = ctx->exec_times[i];
// t-test on the execution time
t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]);
// 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]);
}
}
```
另一個重點改動是會將 lab 0 實施的主程式增加預處理 `prepare_percentiles()` 後才 `update_statistics()`
```c
if (first_time) {
// throw away the first batch of measurements.
// this helps warming things up.
prepare_percentiles(ctx);
} else {
update_statistics(ctx);
ret = report(ctx);
}
```
經過這些改動後遍能夠使原本的 lab 0 有去掉極端大值的功能了。
Sign in with Wallet
Connect another wallet