# 2025q1 Homework1 (lab0)
contributed by <```weiso131```>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
# 開發環境
```
$ 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
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
供應商識別號： GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz
CPU 家族： 6
型號： 140
每核心執行緒數： 2
每通訊端核心數： 4
Socket(s): 1
製程： 1
CPU(s) scaling MHz: 19%
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 5606.40
```
# 開發過程
## q_new
當函式遇到記憶體分配失敗時，應回傳 NULL。
根據 C 語言標準（7.20.3）：
> 若無法分配記憶體，則回傳空指標（NULL）。
可以根據 `malloc` 的結果，決定是否對物件進行初始化，最後直接回傳物件指標。
## q_free
此函式的目標是釋放佇列所佔用的所有記憶體。
可以使用 `list.h` 提供的 `list_for_each_entry_safe` 來走訪所有節點，並使用 `q_release_element` 釋放它們，最後再釋放 `list_head`。
## q_insert_head / q_insert_tail
這兩個函式分別負責在佇列的頭部或尾部插入一個節點，並將輸入的字串 `s` 複製到節點的 `value` 成員。
如果記憶體分配失敗或佇列為 `NULL`，則回傳 `false`。
### 字串複製
1. 使用 `strlen` 計算字串長度。
2. 為 `value` 成員分配長度 +1 的記憶體空間。
3. 使用 `strncpy` 將輸入字串 `s` 複製過去。
### 插入頭/尾
使用 `list.h` 提供的 `list_add` 或 `list_add_tail` 即可完成此操作。
### 共用函式 `__q_insert`
由於 `q_insert_head` 與 `q_insert_tail` 具有相似功能，可以建立一個通用函式，透過傳入 `list_add` 或 `list_add_tail` 來決定插入的位置。
## q_remove_head / q_remove_tail
此函式負責從佇列的頭部或尾部移除一個元素，並回傳該元素。
如果佇列為 `NULL` 或為空，則回傳 `NULL`。
若 `sp` 不為 `NULL`，則將元素的 `value` 字串最多 `bufsize - 1` 個字元複製到 `sp` 中。
### 實作流程
1. 確認佇列不為 `NULL` 且不為空，這可透過 `list.h` 提供的 `list_empty` 來檢查。
2. 若符合條件，則使用 `list_del` 移除元素。
3. 若 `sp` 不為 `NULL`，則執行字串複製。
## q_size
實作一個函式回傳佇列的元素數量。
可以利用 `list_for_each` 走訪整個佇列來計算元素個數。
## q_delete_mid
實作一個函式刪除佇列中間的元素。
這裡使用[快慢指標](https://hackmd.io/@sysprog/ry8NwAMvT)來尋找中間節點。
相比其他方法，這種方式具有更好的時間局部性。
## q_delete_dup
實作一個函式能刪除所有重複的元素。
- 輸入的佇列必須是已排序的。
- 若成功執行回傳 `true`。
- 若佇列為 `NULL` 或空，則直接回傳 `false`。
- 若佇列只有一個元素，則直接回傳 `true`。
此函式會走訪整個串列的所有節點。
若當前節點與下一個節點相同，則刪除當前節點，並標記下一個節點為刪除目標。
若其後的節點不同，則刪除標記的節點。
## q_swap
實作一個函式，使佇列中的元素兩兩交換。
觀察可發現，`q_reverseK(head, 2)` 即可實現該功能。
[參考 2025-02-25 問答簡記](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg#Cheng5840)
## q_reverse
實作一個函式，使佇列中的元素顛倒排列。
### `__reverse`
額外實作一個函式處理顛倒排列的功能，以便與 `q_reverseK` 共用。
使用兩個 `list_head` 指標 `start` 和 `next`。
`next` 被設為 `head->next`，然後交換這兩個節點的關係。
重複此過程，直到 `start` 走到 `end`。
在 `q_reverse` 中，`start` 與 `end` 皆設為佇列的 `head`，因為起點與終點都是 `head`。
```c
void __reverse(struct list_head *start, struct list_head *end)
{
struct list_head *next = start->next, *prev = NULL;
do {
prev = start;
start->prev = next;
start = next;
next = next->next;
start->next = prev;
} while (start != end);
}
```
## q_reverseK
實作一個函式，使佇列中的元素每 K 個進行顛倒排列。
### 顛倒操作
我實作了一個函式 `__reverse_k`，專門負責處理此功能。
該函式接受目標區間的起點 `start` 和終點 `end` 作為輸入，並利用 `__reverse` 來執行顛倒操作。
顛倒後，還需調整節點的鏈結關係，使 `end` 移至前方，`start` 移至後方，具體操作如下：
```c
struct list_head *l = start->prev, *r = end->next;
__reverse(start, end);
l->next = end;
end->prev = l;
r->prev = start;
start->next = r;
```
### 取得需要進行顛倒操作的區間
使用兩個指標 `start` 和 `end` 來標記區間的起點與終點，並每次將這兩個指標移動 K 步。
為了實現 K 步移動的功能，我實作了一個函式 `__move_k`，其主要功能如下：
- 負責將指標向前移動 K 步。
- 回傳實際移動的步數。
- 若未滿 K 步，則表示途中遇到了 `head`，可用來判斷何時終止迴圈。
由於在 `__reverse_k` 執行完顛倒操作後，`start` 和 `end` 在佇列上的位置將與原本相反，因此需要事先儲存下一個 `start` 和 `end`，以便在迴圈結束時進行更新。
```c
void q_reverseK(struct list_head *head, int k)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
struct list_head *start = head->next, *end = head;
int i = __move_k(head, &end, k);
while (i == k) {
struct list_head *next_start = start, *next_end = end;
__move_k(head, &next_start, k);
i = __move_k(head, &next_end, k);
__reverse_k(start, end);
start = next_start;
end = next_end;
}
}
```
## q_sort
此函式使用合併排序法來對鍊結串列進行排序。
在排序開始前，會先解除環狀鍊結串列的狀態，使頭尾不再指向 `head`。
排序完成後，則會重新將頭尾接回。
### `__merge`
我額外實作了 `__merge` 來合併兩個已排序的鍊結串列。
該函式的參數如下：
- `l`、`r`：分別代表兩個鍊結串列。
- `decend`：用來決定排序方式。
此實作參考了[linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 中 `MergeTwoList` 的方法，並嘗試使用間接指標來簡化邏輯。
以下是幾個優化設計：
- 使用 `tmp` 儲存目前元素的下一項指標，即 `&(*tmp)->next`，可避免 `head` 為 `NULL` 時的特判。
- `indir` 用於存放當前優先度較高的串列開頭元素。
- 為了維護雙向鏈結的特性，使用 `last` 來儲存上一個元素的位址。
```c
struct list_head *__merge(struct list_head *l, struct list_head *r, bool decend)
{
struct list_head *head = NULL, **tmp = &head, *last = head;
while (l != NULL && r != NULL) {
char *l_value = list_entry(l, element_t, list)->value,
*r_value = list_entry(r, element_t, list)->value;
struct list_head **indir =
((strcmp(l_value, r_value) > 0) == decend) ? &l : &r;
(*indir)->prev = last;
*tmp = *indir;
last = *tmp;
*indir = (*indir)->next;
tmp = &(*tmp)->next;
}
struct list_head *tail = (l != NULL) ? l : r;
*tmp = tail;
tail->prev = last;
return head;
}
```
### `__merge_sort`
此外，我也實作了 `__merge_sort` 來遞迴處理鍊結串列的切分，並透過 `__merge` 進行合併。
此函式的參數如下：
- `l`：鍊結串列的 `head`。
- `decend`：決定排序方式。
若 `l` 為 `NULL` 或 `l->next` 為 `NULL`，則直接回傳 `l`。
## q_ascend / q_descend
實作函式 `q_ascend` 和 `q_descend`，與元素右側（`next` 之後）的元素比較，若較小/較大則刪除，最終使佇列形成遞增/遞減序列。
該函式回傳一個 `int`，代表剩餘元素數量。
- 若佇列為 `NULL` 或為空，則直接回傳 `0`。
- 若佇列只有一個元素，則直接回傳 `1`。
由於兩個函式的功能類似，我額外實作了一個函式 `__monotonic` 來統一實現其功能。
該函式透過改變 `decend` 參數的 `true` 或 `false`，來決定是遞增或遞減。
此函式需與右側所有元素進行比較，因此可以反向走訪所有節點，紀錄當前的最小/最大值，並與目前元素進行比較。（目前的 `list.h` API 並未提供反向走訪功能）
```c
for (struct list_head *node = (head)->prev, *safe = node->prev;
node != (head); node = safe, safe = node->prev) {
element_t *entry = list_entry(node, element_t, list);
int cmp = strcmp(entry->value, last);
if ((cmp < 0) != descend || cmp == 0) {
last = entry->value;
count++;
} else {
list_del(&entry->list);
q_release_element(entry);
}
}
```
## q_merge
實作一個函式，將多條已排序的佇列合併至第一條佇列中。
- 函式應回傳合併後佇列的長度。
- 若 head 為 NULL 或 chain 為空，則直接回傳 0。
### 舊的實作方法
與 q_sort 相同，合併過程使用 __merge，因此須先解除鏈結串列的環狀結構，待所有佇列合併完成後再接回。
採用兩兩合併的方式，此方法能使各佇列長度較為均衡，相較於逐一合併，通常能提升效能。
```c
int q_merge(struct list_head *head, bool descend)
{
if (head == NULL || list_empty(head))
return 0;
int chain_size = q_size(head), cnt = 0, chain_cnt = 0;
struct list_head *chain[1000];
struct list_head *q_head = list_first_entry(head, queue_contex_t, chain)->q;
queue_contex_t *chain_entry = NULL;
list_for_each_entry (chain_entry, head, chain) {
chain[chain_cnt] = chain_entry->q->next;
__cut_head(chain_entry->q);
INIT_LIST_HEAD(chain_entry->q);
cnt += chain_entry->size;
chain_cnt++;
}
for (int i = 1; i < chain_size; i = i << 1)
for (int j = 0; j < chain_size; j += i << 1)
chain[j] = __merge(chain[j], chain[j + i], descend);
__link_head(q_head, chain[0]);
return cnt;
}
```
### 重新實作
舊的實作方式需要在 stack 上建立一個大小為 1000 的陣列來儲存多條佇列，這會帶來兩個問題：
1. 佔用過多的 stack 空間
2. 若佇列數量超過 1000，將導致錯誤
新的實作方式參考了 Linux 核心的做法，利用 list_head 的 next 指標來維護單向鏈結串列，合併的部分則直接使用 list_sort 中的 merge 演算法。
根據[實驗結果](https://hackmd.io/FJE2SPSHQTebmpHjHtgNVw?view#%E5%AF%A6%E9%A9%9759)， list_sort 的 merge 函式看似隴長，但它其實比原本透過間接指標儲存比較結果的方式，效能高了將近一倍。
與 list_sort 的概念類似，在合併過程中，list_head 的 prev 指標則被用來維護佇列的前後關係。
使用兩個 struct list_head 物件 r0 和 r1，分別代表待合併的佇列與合併後的結果。
反覆執行合併操作並交換 r0 與 r1，直到 r0 只剩一條佇列且 r1 為空，即代表合併完成。
此方法與舊方法一樣是採用兩兩合併以維持良好的合併效率，但它能夠處理任意數量的佇列，且不會因為佇列數量增加而額外佔用更多記憶體。
>[5e6b79d
](https://github.com/weiso131/lab0-c/commit/5e6b79d611c3616718ae262d5da715fb3823d6d9)
### 使用 `merge_final`
`JeffBla` 提到我的 `q_merge` 其實可以利用 `merge_final` 提高效率，對此我進行了實驗並進行 t-test
```
✅ Welch's t-test 結果：
t 值：19.7091
p 值：0.0000 （顯著）
Cohen's d 效果量：0.8814
效能提升倍率：1.0545
```
不出意外的效能確實提高了
# 亂數+論文閱讀
## 在 qtest 提供新的命令 shuffle
### 實作 Fisher–Yates shuffle
- 初始化 ```struct list_head *new_node = head``` ， 讓它儲存最後一個被抽到的節點
- ```struct list_head *old_node``` 儲存這輪被抽到的節點
- ```new_node = new_node->prev``` ， 代表被抽到的節點增加
- 若 ```old_node == new_node``` 直接進入下一輪
- 利用自訂的函式 ```__entry_swap()``` ， 交換 ```old_node``` 與 ```new_node``` 的 ```entry value```
### 亂度驗證程式
使用[作業說明](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d)提供的程式來進行測試
然而，由於字串加法本身不是 $O(1)$ 的操作，進行 ```1000000``` 會耗費非常多的時間
因此我將資料蒐集的程式進行了一些調整
```python
nums = []
test_count = 1000000
t_count = 1000
i_char = ['1', '2', '3', '4']
for t in range(t_count):
if t % 100 == 0:
print(f"testing {t}/{t_count}")
# 測試 shuffle 次數
input = f"new\nit {i_char[0]}\nit {i_char[1]}\nit {i_char[2]}\nit {i_char[3]}\n"
for i in range(test_count // t_count):
input += "shuffle\n"
input += "free\nquit\n"
# 取得 stdout 的 shuffle 結果
command='./qtest -v 3'
clist = command.split()
completedProcess = subprocess.run(clist, capture_output=True, text=True, input=input)
s = completedProcess.stdout
startIdx = s.find(f"l = [{i_char[0]} {i_char[1]} {i_char[2]} {i_char[3]}]")
for i in result:
nums.append(i.split())
i_char = nums[len(nums) - 1]
```
- 將 1000000 分成 1000 次執行，避免對超長的字串做字串加法花費大量時間
- ```i_char``` 儲存上一輪最後一次 ```shuffle``` 的結果，確保與原本的程式效果相同
### 驗證自己實作的 Fisher–Yates shuffle
#### 測試結果
```
Expectation: 41666
Observation: {'1234': 41478, '1243': 41641, '1324': 41868, '1342': 41911, '1423': 41819, '1432': 41891, '2134': 41827, '2143': 41549, '2314': 41984, '2341': 41397, '2413': 41918, '2431': 41421, '3124': 41629, '3142': 41389, '3214': 41694, '3241': 41686, '3412': 41694, '3421': 41560, '4123': 41741, '4132': 41988, '4213': 41533, '4231': 41472, '4312': 41520, '4321': 41390}
chi square sum: 21.621561944991118
```
#### 分析
1234 總共有 24 種組合，只要知道其中 23 組的資料就能得到最後 1 組的，因此自由度為 23
以 0.05 作為顯著水準查表得 $\chi^2_{23,0.05}=35.1725$
$21.62 < 35.1725$，因此無證據說明這個實作不是隨機的
## Dude, is my code constant time?
### 論文閱讀
本篇論文透過統計方法探討程式是否能夠在常數時間內完成任務，以此避免時序攻擊。
研究中使用兩種不同類別的輸入數據來測量程式的執行時間：
- **random class**：每次測量時隨機選擇輸入數據。
- **fix class**：固定輸入為某個常數值。
接著，記錄程式在這兩種類別下的 CPU 執行時間，並利用 Welch’s t-test 來檢驗程式是否具有常數時間執行特性。
### Lab0 實作
在終端機輸入以下指令：
```
./qtest
cmd> option simulation 1
cmd> new
l = []
cmd> it
```
可能會顯示：
```
ERROR: Probably not constant time or wrong implementation
```
在 `qtest.c` 搜尋此訊息，可以發現當 `simulation` 設為 1 時，程式會根據 `pos` 來執行 `is_insert_tail_const()` 或 `is_insert_head_const()`。
這兩個函式由 `dudect/fixture.h` 定義的巨集封裝，真正的測試函式則實作於 `dudect/fixture.c` 中的 `test_const()`。
該函式的核心邏輯由 `doit()` 負責，它的主要目標是驗證測試函式是否為常數時間運行。
### 主要函式解析
#### `prepare_inputs()`
`doit()` 執行的第一個函式，負責隨機初始化 `classes` 與 `input_data`。
此步驟對應論文中 `Step 1: Measure execution time` 的 `(c) Environmental conditions`，其主要作用如下：
1. **隨機排列 fix 與 random 的順序**（fix 設為 0，random 設為 1）。
2. **決定測試類別與輸入數據**，分為以下兩種情況：
- fix: `input_data[i] = 0`
- random: `input_data[i] = 隨機整數`
#### `measure()`
此函式負責測量 CPU 執行時間，具體步驟如下：
1. 根據 `input_data` 內容，在佇列中插入一定數量的隨機字串（類別 0 不會插入字串）。
2. 執行目標測試函式，並在執行前後記錄 CPU 時間。
#### `differentiate()`
該函式計算函式實際消耗的時間，並將結果記錄到 `exec_times` 中。
#### `update_statistics()`
利用 `t_push()` 蒐集測試數據，並記錄各類別的數量、平均值及偏差平方和 ($S_{xx}$)。
#### `report()`
在 `t_compute()` 中，根據 Welch’s t-test 公式：
$$
\frac{\overline{X_1} - \overline{X_2}}{\sqrt{\frac{s_1^2}{N_1} + \frac{s_2^2}{N_2}}}
$$
計算 t 值，並與 `t_threshold_bananas` 及 `t_threshold_moderate` 進行比較。
若結果顯示 $H_0$ 假設顯著，則表示函式執行時間可能不是常數時間。
### q_insert_head/q_insert_tail 非常數時間問題
在 make test 中，插入節點的功能總是被認為不是常數時間完成
在實際追蹤測試程式之前，我原本以為可能跟 ```strncpy``` 有關
然而不管在 fix 還是 random 類別，字串的長度都是隨機的
後來我受到 ```rota1001``` 開發紀錄的提示，得知了問題出在 ```malloc```
#### 實驗
我在能穩定通過測試的 ```q_remove_head``` 中加入原先不存在的記憶體分配
```c
char *trash = malloc(sizeof(char) * 10);
if (trash) {
free(trash);
}
```
再執行 ```qtest``` 並輸入以下命令
```
cmd> new
cmd> option simulation 1
cmd> rh
```
最後得到
```
ERROR: Probably not constant time or wrong implementation
```
紀錄測試的類別與時間，利用 python 畫出的累積百分比圖如下
- 加入記憶體分配之前
- 加入記憶體分配之後
#### malloc重用釋放記憶體的特性
參考[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory#glibc-%E7%9A%84-mallocfree-%E5%AF%A6%E4%BD%9C)
```malloc``` 在分配記憶體時，會先嘗試從 bin 尋找是否有合適的區塊可直接使用
來加速記憶體分配
我就猜測，現在遇到的 malloc 問題是否與此有關連
可能 ```input_data``` 較小時能直接從 bin 取得合適的區快來加速分配
```input_data``` 較大時，開始進行測量的時候 bin 裡面已經沒有任何可用區塊
於是我在 ```constant.c``` 的 measure 函式中，在開始測量時間之前
先在佇列的頭插入一個節點再釋放
```c
dut_insert_head(get_random_string(), 1);
element_t *e = q_remove_head(l, NULL, 0);
q_release_element(e);
```
觀察這是否能解決 ```malloc``` 的問題
然而
```
cmd> new
l = []
cmd> option simulation 1
cmd> it
Probably constant time
cmd> it
Probably constant time
cmd> it
Probably constant time
cmd> it
ERROR: Probably not constant time or wrong implementation
```
這個方法雖然增加了通過機率，但沒能完全解決 ```malloc``` 的問題
下方累積百分比圖也顯示了，此操作並非完全有效(讓兩個類別的曲線在低於 60% 前重合)
- 加上操作之前
- 加上操作之後
#### malloc 時間與 input_data 的關聯
參考[ rota1001 開發紀錄](https://hackmd.io/@rota1001/linux2025-homework1#%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89)
提到 ```input_data``` 與 ```malloc``` 時間呈現正相關
於是我在 dudect/constant.c 做以下更改並實驗，紀錄 input_data 與 exec_times
```diff
- dut_insert_head(
- get_random_string(),
- *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
+ element_t *big_trash = malloc(sizeof(element_t) * (*(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000));
int before_size = q_size(l);
before_ticks[i] = cpucycles();
- dut_insert_tail(s, 1);
+ char *trash = strdup(s);
after_ticks[i] = cpucycles();
int after_size = q_size(l);
+ free(trash);
+ free(big_trash);
dut_free();
- if (before_size != after_size - 1)
+ if (before_size != after_size)
```
可發現 malloc 時間確實與 ```input_data``` 呈現正相關
於是將 input_data 的上限調成 1000
```diff
- *(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
+ *(uint16_t *) (input_data + i * CHUNK_SIZE) % 1000);
```
它能夠通過了測試
而對於非常數時間的實作也能確實的辨認出來
- 常數時間實作
- 非常數時間實作(從第一項走訪直到找到最後一項再進行操作)
至於這是否真的代表能防範 side-channel attack
我原本對此有些質疑
然而，在跟 ```rota1001``` 討論之後，他提出以下論點
在實驗中可得知只要記憶體的佔用量增加， malloc 的速度就會慢慢下降
這跟佇列內實際存在多少元素不完全有關係
因此，攻擊者無法藉由 side-channel attack 確切得知佇列內的元素數量
### 移除DROP_SIZE
#### DROP_SIZE
在追蹤這段程式碼的時候，我發現了一個奇怪的問題
在 ```fixture.c``` 進行統計量計算與更新 (differentiate 與 update_statistics)時，其範圍是從 ```0``` 到 ```N_MEASURES```
然而在 ```constant.c``` 測量數據的時候，其範圍是從 ```DROP_SIZE``` 到 ```N_MEASURES - DROP_SIZE```
這可能會導致會在計算 ```t``` 值的時候，會計算到根本不是測量數據的數值
然而當初發現時嘗試藉由修改來解決 ```q_insert``` 問題不成
就認為它可能沒有實際影響，因此沒將這次修改提交
#### q_remove_head 問題
當我將 Input_data 的上限調整為 1000 (參考:[malloc 時間與 input_data 的關聯](https://hackmd.io/FJE2SPSHQTebmpHjHtgNVw?both#q_insert_headq_insert_tail-%E9%9D%9E%E5%B8%B8%E6%95%B8%E6%99%82%E9%96%93%E5%95%8F%E9%A1%8C)) ，在本地端拿到測試程式的滿分並推送至 github 上之後，發現 github 上的測試只拿到 95 分，看詳細紀錄才發現，我的 ```q_remove_head``` 功能每次都不能通過測試，這在本地端的測試中從未發生過。
#### 提交修改
在3月4號上課前，我跟 ```Ian-Yen``` 與 ```rota1001``` 討論 ```q_remove_head``` 的問題，在過程中 ```Ian-Yen``` 提起了 ```DROP_SIZE``` 的問題，這才知道認為那個 DROP_SIZE 的功能很奇怪的不只我，現在的就該思考，應該要統一使用 ```DROP_SIZE``` ， 還是統一移除。
在經過一番討論之後，認為如果要將數據移除，應該要先根據 ```exec_time``` 做排序再去除極端值，因此最後選擇了將 ```DROP_SIZE ``` 全數移除。
而在提交此次修改後，我成功的在 github 上的測試程式拿到 100 ，獲得卡比一隻。
然而，在之後的 github action ，仍然可見到同樣的問題再次發生
其結果仍存在不確定因素
# Linux 核心的鏈結串列排序
## 程式碼閱讀
### 第一階段合併
#### 尋找 count 二進位表示式 第一個0
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
這段程式會反覆執行直到 bits 的最低位變成0
- bits 作為下方判斷式的條件
- tail 作為下方合併的位置依據
若 bits 到最高位都是 1 (像是: 1, 3, 7)，在迴圈執行完畢後會變成0， 此時就不會滿足下方的判斷條件
相反情況的話， bits 在迴圈執行完畢後不為 0，滿足下方的判斷條件，此時 tail 會指向需要進行合併的第一項
以 8 個元素為例子:
| count |count 二進位| bits 二進位表達式 | 是否合併 | 合併後狀態 |
| -------- |-| -------- | -------- | - |
| 0 |0 | 0 | 否 | |
| 1 |1 | 0 | 否 | 1 |
| 2 |10 | 10 | 是 | 2 |
| 3 |11 | 0 | 否 | 2 -> 1 |
| 4 |100 | 100 | 是 | 2 -> 2 |
| 5 | 101 | 10 | 是| 4 -> 1 |
| 6 |110 | 110 | 是 | 4 -> 2 |
| 7 |111 | 0 | 否 | 4 -> 2 -> 1 |
| 8 |1000 | 1000 | 是 | 4 -> 2 -> 2 |
#### likely 巨集
這個巨集定義在 ```linux/include/linux/compiler.h``` 裡面
相關程式如下
```c
void ftrace_likely_update(struct ftrace_likely_data *f, int val,
int expect, int is_constant);
#if defined(CONFIG_TRACE_BRANCH_PROFILING) \
&& !defined(DISABLE_BRANCH_PROFILING) && !defined(__CHECKER__)
#define likely_notrace(x) __builtin_expect(!!(x), 1)
#define unlikely_notrace(x) __builtin_expect(!!(x), 0)
#define __branch_check__(x, expect, is_constant) ({ \
long ______r; \
static struct ftrace_likely_data \
__aligned(4) \
__section("_ftrace_annotated_branch") \
______f = { \
.data.func = __func__, \
.data.file = __FILE__, \
.data.line = __LINE__, \
}; \
______r = __builtin_expect(!!(x), expect); \
ftrace_likely_update(&______f, ______r, \
expect, is_constant); \
______r; \
})
/*
* Using __builtin_constant_p(x) to ignore cases where the return
* value is always the same. This idea is taken from a similar patch
* written by Daniel Walker.
*/
# ifndef likely
# define likely(x) (__branch_check__(x, 1, __builtin_constant_p(x)))
# endif
# ifndef unlikely
# define unlikely(x) (__branch_check__(x, 0, __builtin_constant_p(x)))
# endif
```
可得知 likely 背後有個 ```__branch_check__``` 巨集
由於我真的看不懂這段程式碼，我選擇將其複製，要 chatGPT 解釋並附上規格書資料
這才知道這是 GCC 提供的擴充功能
- [__builtin_expect (long exp, long c)](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
>You may use __builtin_expect to provide the compiler with branch prediction information.
>The return value is the value of exp, which should be an integral expression. The semantics of the built-in are that it is expected that exp == c. For example:
```c
if (__builtin_expect (x, 0))
foo ();
```
這說明了這個函式用來提供編譯器 ```exp``` 出現機率較高的值，來幫助做編譯優化。最後仍會回傳 ```exp``` ，對應到原始碼， ```___r``` 就是 ```x``` 。
- [({ ... }) 語法](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html)
>A compound statement enclosed in parentheses may appear as an expression in GNU C. This allows you to use loops, switches, and local variables within an expression.
>The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct.
這說明了這個語法可以定義一個表達式包含任何需要的東西，而這個表達是的最後一條語句則代表整個表達式的值。
對應到原始碼， ```___r``` 即是最後的值。
結論就是，這個巨集主要是幫助編譯器優化，不影響遠本的值。
### merge 函式
這邊其實我不太理解為什麼不用一個間接指標儲存比較結果來將程式碼簡潔化
此外，最後將尾巴接上的方法，可以藉由轉型與位元運算來節省分支
我的想法實作出來如下
```c
struct list_head *one_way_merge(struct list_head *l,
struct list_head *r,
bool descend)
{
struct list_head *new_head = NULL, **tmp = &new_head, **indir = NULL;
while (l != NULL && r != NULL) {
char *l_value = list_entry(l, element_t, list)->value,
*r_value = list_entry(r, element_t, list)->value;
indir = ((strcmp(l_value, r_value) > 0) == descend) ? &l : &r;
*tmp = *indir;
tmp = &(*tmp)->next;
*indir = (*indir)->next;
}
*tmp = (struct list_head *) ((uintptr_t) l | (uintptr_t) r);
return new_head;
}
```
### 第二階段合併
將多個佇列合併到 ```list``` ， 最後會剩下兩個佇列: ```list``` 和 ```pending``` ， 交由 ```merge_final``` 做最後的合併
### 將佇列恢復成雙向環狀鍊結串列
原始碼的作法是 ```final_merge``` 合併最後兩個佇列，同時維護雙向的特性，後面再用迴圈尋找尾巴的位置，維護環狀特性
我自己的作法是在第二階段合併時就把佇列合併完成，最後再跑迴圈維護雙向特性並找到尾巴，最後再接上 ```head``` 維護環狀特性。我認為這個作法少了一個迴圈另外尋找尾巴，應該要更快，之後會做實驗比較。
## 實驗
### 數據蒐集方法
#### 計錄排序的 cpu 時間
在 q_test.c 做以下更改，儲存使用的 cpu 時間到 output.csv
```diff
if (current && exception_setup(true)) {
+ int64_t _start = cpucycles();
q_sort(current->q, descend);
+ int64_t _end = cpucycles();
+ FILE *file = fopen("output.csv", "a"); // 以附加模式 (append) 開啟檔案
+ if (file == NULL) {
+ perror("無法開啟檔案");
+ exit(EXIT_FAILURE);
+ }
+ fprintf(file, "%ld\n", _end - _start); // 將文字寫入檔案
+ fclose(file); // 關閉檔案
}
```
#### 數據蒐集腳本
```python
import subprocess
# shuffle 的所有結果
nums = []
t_count = 1000
_input = f"new\nih RAND {100000}\nsort\nfree\n"
# 取得 stdout 的 shuffle 結果
for i in range(t_count):
if (i % 100 == 0):
print(i + 1)
command='./qtest -v 3'
clist = command.split()
completedProcess = subprocess.run(clist, capture_output=True, text=True, input=_input)
completedProcess = subprocess.run(clist, capture_output=True, text=True, input="quit\n")
```
### 比較原本的 top-down 實作與模仿 list_sort 的實作
由於差距明顯，不使用 t-test 去檢定平均是否不同
在作業說明中有提到， top-down mergesort 雖然會需要遞迴或額外的記憶體做 user stack，但它有最少的 average case、worst case 的 comparison 次數
而 list_sort 的實作屬於 Bottom-up mergesort，有著各種變形中最多的比較次數
#### merge 使用 linux 核心的實作
參考 [```rota1001``` 的開發紀錄](https://hackmd.io/cWJXo6kVRi2jAnU0JqYmPw#%E6%95%88%E8%83%BD%E6%AF%94%E8%BC%83)，有提到[利用間接指標儲存比較結果](https://hackmd.io/FJE2SPSHQTebmpHjHtgNVw?both#merge-%E5%87%BD%E5%BC%8F)的方法，相較 linux 核心的方法耗費時間
將 linux 核心的 merge 做點修改
```diff
- static struct list_head *merge(void *priv, list_cmp_func_t cmp,
- struct list_head *a, struct list_head *b)
+ struct list_head *linux_merge(struct list_head *a,
+ struct list_head *b,
+ bool descend)
...
+ char *l_value = list_entry(a, element_t, list)->value,
+ *r_value = list_entry(b, element_t, list)->value;
- if (cmp(priv, a, b) <= 0) {
+ if ((strcmp(l_value, r_value) > 0) == descend) {
...
```
接著進行實驗
由於差距明顯，不使用 t-test 去檢定平均是否不同
沒想到 merge 方法的差距能造成如此明顯的差距
使用 perf 執行數據蒐集腳本 (只蒐集 100 個)，觀察不同合併方法對效能的影響
- linux 原本的 merge
- cpu cycle
- 組合語言
- 使用間接指標儲存比較結果
- cpu cycle
- clock cycle
- cache miss
上方結果能明顯看出， q_sort 函式的佔用量都是 1.4% 左右，然而，兩種合併方法的佔用時間相差了一倍，與上方累積百分比圖的結果吻合
觀察組合語言指令的佔用時間，間接指標儲存比較值的方法
```
mov -0x8(%rbp),%rsi
mov -0x8(%rbx),%rdi
```
也就是將 ```l_value``` 與 ```r_value``` 作為參數傳遞時
花了更多的時間
:::info
為甚麼指令相同但效率不同
:::
#### 使用 linux 的 final_merge 與否
使用[作業二自訂記憶體配置器](https://hackmd.io/p6i9MFQ3RiW3PxDsagfAWw?both#%E5%98%97%E8%A9%A6%E6%B8%9B%E5%B0%91-find_free_tree-%E4%BD%BF%E7%94%A8) 的 t test 程式
輸出
```
✅ Welch's t-test 結果：
t 值：73.2370
p 值：0.0000 （顯著）
Cohen's d 效果量：3.2759
效能提升倍率：1.3971
```
如 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的註解
> Combine final list merge with restoration of standard doubly-linkedlist structure. This approach duplicates code from merge(), but
runs faster than the tidier alternatives of either a separate final
prev-link restoration pass, or maintaining the prev links
throughout.
使用 final_merge 比起額外執行一次還原 prev 鍊結串列的方法快
重新觀察程式碼，發現 merge_final 的作法是一邊進行 merge 一邊維護 prev ， 並且用 tail 儲存最後一個被維護到的節點 ， 最後在從 tail 往後維護。
這樣的作法比起額外執行一次還原 prev 鍊結串列的方法，可減少重新存取節點的次數。在鍊結串列很長的時候，如果在合併完成後再重新存取節點維護 prev ，有可能因為節點的資料已經不在 cache 裡面，造成 cache-miss 導致速度下降，可以藉由 perf 工具觀察相關函式的 cache-miss 次數。
- 有 final merge
- 沒有 final merge
- 查看 cache miss 最多的位置，正是在重新維護 prev 的程式
提交修改
>
在我嘗試推測這個實驗結果的解釋原因之後，想到昨天有跟 `JeffBla` 討論這件事情，打開 discord 想告訴他我的想法，結果發現他稍早已經傳訊息給我，說的就是這件事情，這讓我更確信這個想法是對的，之後也在 perf 的結果得到驗證。
此外，他也發現我的 `q_merge` 其實可以利用 `merge_final` 提高效率，對此我進行了[實驗](https://hackmd.io/FJE2SPSHQTebmpHjHtgNVw#%E4%BD%BF%E7%94%A8-merge_final)。
Sign in with Wallet
Connect another wallet