# 2025q1 Homework1 (lab0)
> contributed by <[Nsly0204](https://github.com/Nsly0204)>
### Reviewed by horseface1110
> 在了解宣告的組成之後繼續翻閱規格書，了解到因為 fasr 只會走訪點，並不會對節點的值進行更改，在此情況下宣告成 ptr_to_constant 可以避免 fast 指標不小心更動所指到的變數。
其中的`fasr`打錯字
> 在 harness.h 中可以找到被定義的巨集，兩種方式其實是一樣的，特別定義成 test_free 目的是為了做之後的記憶體用量偵測。
`t_free`中，`test_free`用來檢測記憶體用量的部分在harness.c中，透過`allocated_count--` 來追蹤當前已分配的區塊數量，還增加了檢測記憶體損壞
[作業要求](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-f)
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell!
$ 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: 44 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 4600H with Radeon Graphics
CPU family: 23
Model: 96
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU(s) scaling MHz: 76%
CPU max MHz: 3000.0000
CPU min MHz: 1400.0000
BogoMIPS: 5988.20
Flags: ......
Virtualization features:
Virtualization: AMD-V
Caches (sum of all):
L1d: 192 KiB (6 instances)
L1i: 192 KiB (6 instances)
L2: 3 MiB (6 instances)
L3: 8 MiB (2 instances)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-11
```
## Git
參考[為什麼該接觸 GNU/Linux 開發工具](https://hackmd.io/@sysprog/gnu-linux-dev/Fr1Psrf0KW)，紀錄下之後可能會用到的語法。
### Set up
以下命令的更動可以在`git ~/.gitconfig`找到
```shell
git config --global core.editor vim #設定常用的編輯器
git config --global merge.tool vimdiff #設定常用的編輯器
git config --global alias.st status #設定status縮寫為st
git config --global alias.co checkout #設定checkout縮寫為co
```
### Add and commit
```shell!
git status # 查看各資料status
git add <file> # 將檔案加入commit stage
git reset HEAD <file> # 將檔案變成untracked
git commit -a # commit所有更動過的檔案
```
### Ignore Files
撰寫`.gitignore`可以忽略特定不需要被 commit 的檔案，下`git status`時也會一並忽略。
```shell!
vim .gitignore
<file1> # 忽略所有子目錄下同名檔案
\file2 # 只忽略現目錄檔案
```
### Branch
如果在 commit 也想對不同的檔案版本做分類，可以從主幹`master`創建分支（branch），在個分支中的commit互相獨立，所有對檔案的更改只有在合併分支（merge）的時候合併。
* `HEAD`可以想成一個指向 commit 的指標，所有的`git`操作都會在`HEAD`指向的 commit 後面做延伸，包含`merge`、`branch`、`rebase`等，詳細內容可以看[Git 教學系列 - Branch and Merge](https://www.youtube.com/watch?v=qUfT-4bNtwY)。
```
git checkout # move HEAD
git checkout -b <branch> # 創建新的分支後 move HEAD 到該分支
git branch -d <branch> # 刪除目標名稱分支
git merge <branch> # 將head所在分支合併進入目標分支
```
>*Fast Foward (ff)*
在執行 merge 時若系統偵測到目前 HEAD 所指向的分支不須更動即可以 merge 這時系統在執行 merge 時會自動跳過 commit 的階段，稱之為 fast forward 。若要避免可以下 `$ git merge <branch> --no-ff`
當合併分支的時候會顯示出檔案中有衝突的地方，每個有衝突的區塊會用以下的形式標示：
```
<<<<<<< HEAD
/* your code in commit HEAD */
=======
/* your code in branch */
>>>>>>> branch
```
下`git merge <branch>`時會要求把所有有衝突的地方合併，亦即刪去`<<<<<<< HEAD`、`=======`、`>>>>>>> branch`、和所有不需要留下的程式碼。編輯完之後可以到`git status`查看待 commit 檔案狀況，最後再commit即完成分支的合併。
### Rebase
`rebase`與`merge`都需要解決不同 branch 中檔案版本發生衝突（conflict）的情況，主要的差別在於後者不能對 commit 進行修改，能做的是僅僅根據現有的 commit 對檔案內容進行修改而後合併，注意到這邊的合併（merge）需要將最終的檔案版本進行額外的 commit ，相反`rebase`主要的用途是移動 commit ，而 rebase 途中遇到衝突只需要直接修正檔案`<<<<<<< HEAD ======= >>>>>>> branch`部份即可，不需要額外的 commit。
```shell
$ git checkout <branch>
# 移動HEAD指標到需要修改的分支
$ git --onto <new_base> <old_base> <branch>
# 以old_base為基底把branch內的commit接到new_base上
$ vim <conflicted_file>
# 修改所有發生衝突的檔案
$ git rebase --continue
# 持續continue直到所有衝突都被解決即成功
```
`＄ git rebase -i`是非常強的功能，主要協助開發者進行 commit 的管理，功能涵蓋修改順序及內容、合併或分開 commit 等等。
```shell
$ git rebase -i
#對該分支進行所有上述所有提到的commit操作
```
由於`＄ git rebase`功能的強大，同常在進行該操作時有以下規範：
* 因為`＄ git rebase -i`涉及 commit 歷史的改變，已經公開到遠端的 commit 不建議更改
* 盡可能避免跨越分支進行`＄ git rebase -i`
* 做好備份分支後再進行`＄ git rebase -i`
這裡舉一個在我尚不理解 git 是怎麼運作也不了解其各命令所進行的操作時遇到的困難：背景是我已經在本地端打了一些程式碼，有一些已經 commit 有一些還沒，而在已經 commit 過得程式碼中更有分為有`git pull`到遠端和沒有到遠端的。
此時我打開 github 發現有`sync fork`的驚嘆號，想都沒想就按下去之後一路選擇預設選項，結果就是因為 git 無法同步我的程式碼而直接詢問我是否捨棄當前的 commit ，而我也大膽的選下了`Discard`。
然後我到本地端就接收到了`pull request`，下命令後就得到了以下的報錯：
```shell
$ git pull
remote: Enumerating objects: 58, done.
remote: Counting objects: 100% (28/28), done.
remote: Compressing objects: 100% (11/11), done.
Unpacking objects: 100% (58/58), 32.65 KiB | 857.00 KiB/s, done.
remote: Total 58 (delta 18), reused 17 (delta 17), pack-reused 30 (from 2)
From github.com:Nsly0204/lab0-c
+ 6eca37b...e3d96b3 master -> origin/master (forced update)
hint: You have divergent branches and need to specify how to reconcile them.
hint: You can do so by running one of the following commands sometime before
hint: your next pull:
hint:
hint: git config pull.rebase false # merge
hint: git config pull.rebase true # rebase
hint: git config pull.ff only # fast-forward only
hint:
hint: You can replace "git config" with "git config --global" to set a default
hint: preference for all repositories. You can also pass --rebase, --no-rebase,
hint: or --ff-only on the command line to override the configured default per
hint: invocation.
fatal: Need to specify how to reconcile divergent branches.
```
查看`git status`得到以下說明：
```shell
$ git status
On branch master
Your branch and 'origin/master' have diverged,
and have 2 and 18 different commits each, respectively.
(use "git pull" if you want to integrate the remote branch with yours)
Changes not staged for commit:
(use "git add <file>..." to update what will be committed)
(use "git restore <file>..." to discard changes in working directory)
modified: queue.c
Untracked files:
(use "git add <file>..." to include in what will be committed)
e -i <6eca37b>
no changes added to commit (use "git add" and/or "git commit -a")
```
可以看到我電腦本地端有一些尚未 commit 的程式碼，但由於剛才的`sync fork`讓我刪除了遠端的 commit ，造成遠端、本地 commit 、本地未 commit 三種版本不相符，造成我無法`git pull`、也無法`git commit`。
```shell
$ git pull --rebase
error: cannot pull with rebase: You have unstaged changes.
error: Please commit or stash them.
```
後來學習了`git rebase`之後，先把本地端所有程式碼完成 commit ，再`$ git pull --rebase`成功把現有的本地 commit 嫁接到遠端commit 後面。
## 可用工具
### GDB
```shell
$ gcc file.c -g -o gdb_test
$ gdb ./gdb_test
(gdb) help
```
在開始偵錯之前我們通常需要用 `break` 設定中斷點， `run` 開始執行除錯，`list` 展開程式碼方便觀察和操作。
```shell
(gdb) b <#_of_line> # 設定執行到特定行數後暫停，只能有一個暫停點
(gdb) b main # 以function作為中斷點，這裡用main舉例
(gdb) b *main+10 # 以地址作為中斷點，main後10行
(gdb) r # 開始執行
(gdb) l # 查看現在可用gdb做操作的程式碼範圍
```
若要查看 object 在記憶體中所佔用區域的起始位址可以使用`print &object` 的指令，注意這只包含現在 scope 可見的變數，這也回應了我們設定中斷點的用意。更多可以參考 [GDB print 詳解](https://blog.csdn.net/matrix_laboratory/article/details/8771120)。
```shell
(gdb) p &i
$1 = (int *) 0x7fffffffe23c
(gdb) p sizeof(i)
$2 = 4
```
之後可參考 [老師的使用範例](https://hackmd.io/@sysprog/c-pointer?type=view&stext=20885%3A6%3A0%3A1741708018%3A-mgJv0) 、 [基本gdb](http://www.study-area.org/cyril/opentools/opentools/x1253.html) 、 [進階gdb](http://www.study-area.org/cyril/opentools/opentools/x1265.html)
### Valgrind
## 實作指定佇列操作
### q_new
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head) {
return NULL;
}
INIT_LIST_HEAD(head);
return head;
}
```
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
#### TODO:
了解 linux 核心中對於值的讀取和寫入都需要使用巨集`WRITE_ONCE` `READ_ONCE`背後的原理及考量。
### q_free
在`list_for_each_entry_safe`中用到了`container_of`巨集，閱讀[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof#Linux-container_of) 後了解到 linux 核心如何利用 `offsetof` 反向找出包含目標成員結構體的地址，這可以說是 `list_head` 結構體的精髓，讓我們可以藉由把 `list_head` 嵌入到另一個結構體，但還是能使用現成 `list.h` 中定義的所有函數和巨集做到如 traversal 、 swap 、 delete 、 sort 等方便且高效的函數，我想這也是本次作業的目的。
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
q_release_element(entry);
}
free(head);
return;
}
```
可以看到程式碼中使用了 `test_free` 和 `free` 兩種釋放記憶體的方式：
```c
static inline void q_release_element(element_t *e)
{
test_free(e->value);
test_free(e);
}
```
在 `harness.h` 中可以找到被定義的巨集，兩種方式其實是一樣的，特別定義成 `test_free` 目的是為了做之後的記憶體用量偵測。
```c
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define calloc test_calloc
#define free test_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_sort
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return;
if (list_is_singular(head))
return;
struct list_head *slow = head;
struct list_head *fast = NULL;
for (fast = head->next; fast != head && fast->next != head;
fast = fast->next->next)
slow = slow->next;
struct list_head left;
list_cut_position(&left, head, slow);
q_sort(&left, descend);
q_sort(head, descend);
mergeTwoLists(head, &left, descend);
}
```
這裡參考了 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023) 和 [vax-r](https://hackmd.io/@vax-r/linux2024-homework1#2024q1-Homework1-lab0) 實作 merge sort（stable sort），在靜態檢查時遇到錯誤：
```shell
$ git commit
Running static analysis...
queue.c:295:23: style: Variable 'fast' can be declared as pointer to const [constVariablePointer]
struct list_head *fast = NULL;
^
Fail to pass static analysis.
```
到這裡我發現我對C語言中變數的宣告組成的無知，於是查閱 C11 `§ 6.7 Declarations` 了解到基本的宣告其實可以歸列成以下形式：
>**§ 6.7 Declarations**
*—Syntax—*
*declaration-specifiers:*
*declaration-specifiers init-declarator-list*
`init-declarator-list` 可以想成一個或是一連串的變數名稱（更清楚的說是 *identifier* ），而其中 `declaration-specifiers` 包含 `storage-class-specifer` (e.g. static, etc.) 、 `type-specifier` (e.g. int, char, etc.)、`type-qualifier` (e.g. const, etc.) 、 `function-specifier` (e.g. inline, etc.) 、 `alignment-specifier`。
在了解宣告的組成之後繼續翻閱規格書，了解到因為 `fasr` 只會走訪點，並不會對節點的值進行更改，在此情況下宣告成 ptr_to_constant 可以避免 `fast` 指標不小心更動所指到的變數。
>**§ 6.7.6.1 Pointer declarators**
>考慮以下兩種宣告形式：
const int *ptr_to_constant;
int *const constant_ptr;
>解釋：
The contents of any object pointed to by **ptr_to_constant** shall not be modified through that pointer,
but **ptr_to_constant** itself may be changed to point to another object. Similarly, the contents of the int pointed to by constant_ptr may be modified, but constant_ptr itself shall always point to the same location.
### q_ascend / q_descend
### q_merge
## 研讀論文〈 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 〉
### 先備知識
在沒有任何背景知識下，參考〈[解讀計算機編碼 - 第三部分：在資訊安全的應用](https://hackmd.io/@sysprog/binary-representation#第三部分：在資訊安全的應用)〉了解時序攻擊法 (Timing attack) 是旁路攻擊 (side channel) 常見的一種攻擊方法，主要透過偵測程式的運行時間獲取有用訊息，也就是所謂的資訊洩漏 (leakage)。
### 論文整理
論文提供的常數時間測試可以分成三個步驟，分別是 Measure execution time / Apply post-processing / Apply statistical test ，以下是論文摘錄:
1. Measure execution time
* fix vs random test 將測試資料進行分組，固定部分測資為已知的常數時間測資，另一部分為隨機測資，是一種很常見的偵測洩漏(leakage detection)方式。
+ 已知的常數時間測資會特別設計，想辦法觸發一些會影響運算時間的特例，如論文中的 low-weight input in arithmetic operators
+ TODO: 驗證或透過第一手資料查找特例，像是 low-weight 乘法是否會跳過某些步驟，與 branch 預測是否相關?
* 使用 CPU 內建的 cycle counter 以獲得更精準的時間紀錄。
+ 引入 TSC (Time Stamp Counter)除了可以更精準的以指令 (instruction)為單位計算時間以外，更可以移殖到不同的 cpu 架構。
+ 以指令 (instruction)為單位計算時間是比較精準且合理的原因來自於可以換算回 clock （處理器最基礎的時間單位），如老師上課所述，在面對一些情境如超頻時，單純紀錄時間單位（如微秒）並沒有實際的物理意義。
```c
static inline int64_t cpucycles(void)
{
#if defined(__i386__) || defined(__x86_64__)
unsigned int hi, lo;
__asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi));
return ((int64_t) lo) | (((int64_t) hi) << 32);
#elif defined(__aarch64__)
...
```
* 需要避免把準備輸入資料的時間被加入常數時間的計算，我們需要先把上述的輸入資料準備好在開始進行 cpu cycle 計算和測試，可以從 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 看到確實 `preparation task` 被放在時間測試之前。
2. Apply post-processing
* 基於實務上測量需要面臨作業系統介入之類的強迫中斷或是測量困難，作者提出對測量資料進行 crop ，目的是去除被干擾太嚴重的幾筆資料。注意，這裡並沒有數學支持，實作為直接忽略設定閾值 p 比例的資料。
* higher-order processing 本篇僅有提及沒有實作。
3. Apply statistical test
* 利用 Welch's t-test 檢查固定測資和隨機測資兩者分布的平均數是否相等，若相等則支持虛無假說，證明兩者執行時間一致，本程式是為常數時間實作。
**Welch's t-test**
又名【不同變異數獨立樣本平均值檢定】，目的為比較兩個不同取樣的分布是否具有相似的統計特性。顧名思義，相對於取樣來自常數分布的 Student's t-test 在面對母體具有不同變異數的常態分布時更可靠，這也是本次實作採用 Welch's t-test 的考量。
* 虛無假說(H0): 兩(多)組資料的平均數相等
**程式碼實作**
## 亂數
### 測試用程式
[Commit 8ee635d](https://github.com/sysprog21/lab0-c/commit/8ee635d959d19dfb7b3231638c526fa00d9a1849) 先在資料夾中新增測試用檔案，方便以後下 `$ python3 test_shuffle.py` 進行測試。
新增新 command 前參考 [lab0 (三)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d) 搞懂各個檔案的關係，了解到 `console.[ch]` 負責 command-line interface 的實作，其中就包含了新增命令的函數：
```c
/* Add a new command */
void add_cmd(char *name, cmd_func_t operation, char *summary, char *param)
...
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
在 `init_cmd()` 的地方可以看到預設新增未知指令＃後會直接呼叫 `do_comment_cmd` 的函式，由此可知我們新增命令需要三個步驟：
* 利用巨集 ADD_COMMAND 新增命令
* 實作 shuffle 命令會自動呼叫的 do_shuffle
* 實作 q_shuffle 以提供給 do_shuffle 進行操作
```c
void init_cmd()
{
cmd_list = NULL;
param_list = NULL;
err_cnt = 0;
quit_flag = false;
ADD_COMMAND(help, "Show summary", "");
ADD_COMMAND(option,
"Display or set options. See 'Options' section for details",
"[name val]");
ADD_COMMAND(quit, "Exit program", "");
ADD_COMMAND(source, "Read commands from source file", "");
ADD_COMMAND(log, "Copy output to file", "file");
ADD_COMMAND(time, "Time command execution", "cmd arg ...");
ADD_COMMAND(web, "Read commands from builtin web server", "[port]");
add_cmd("#", do_comment_cmd, "Display comment", "...");
add_param("simulation", &simulation, "Start/Stop simulation mode", NULL);
...
}
```
### 新增 shuffle 命令
[commit e498635](https://github.com/sysprog21/lab0-c/commit/e49863510fece145a61b427ec49fc8aa4dcc4fc2)
現在我們知道需要先依照 `console.[ch]` 規定的方式在 q_test 新增命令：
```c
static void console_init()
{
...
+ ADD_COMMAND(shuffle, "Do Fisher-Yates shuffle", "");
ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time",
"[K]");
add_param("length", &string_length, "Maximum length of displayed string",
NULL);
...
}
```
**實作 do_shuffle**
由於所需要的輸入和返回型態都一樣，直接參考 do_ascend 進行實作：
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current || !current->q)
report(3, "Warning: Calling shuffle on null queue");
error_check();
set_noallocate_mode(true);
if (current && exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
q_show(3);
return !error_check();
}
```
**實作 q_shuffle 函數**
根據作業要求，使用 Fisher-Yates shuffle algorithm 進行實作。
本段 shuffle 程式碼學習 [weihsinyeh](https://hackmd.io/@weihsinyeh/SJUVTnEn6) 精簡程式碼的方式，但在執行後發現無法達成特定排列，後來發現是因為 `rand() % (cnt--)` 對應到的值域是 [0,N-1] 但我們所需要的位移次數是 [1,N] ，故做了以下修正：
```c
if (!head || list_empty(head) || list_is_singular(head))
return;
int cnt = q_size(head);
struct list_head *entry = head->prev;
struct list_head *safe = entry->prev;
for (; cnt > 0; entry = safe, safe = safe->prev) {
int idx = rand() % (cnt--);
struct list_head *tmp = head;
- for (; idx > 0; idx--) {
+ for (; idx >= 0; idx--) {
tmp = tmp->next;
}
if (tmp != entry) // skip swap fatal
list_swap(tmp, entry);
```
```
Expectation: 41666
Observation: {'1234': 83865, '1243': 0, '1324': 0, '1342': 82934, '1423': 83561, '1432': 0, '2134': 0, '2143': 82983, '2314': 83503, '2341': 0, '2413': 0, '2431': 83397, '3124': 83209, '3142': 0, '3214': 0, '3241': 83662, '3412': 83024, '3421': 0, '4123': 0, '4132': 82991, '4213': 83509, '4231': 0, '4312': 0, '4321': 83362}
chi square sum: 1000040.4228867661
```
後來新增 [Commit 3796bda](https://github.com/sysprog21/lab0-c/commit/3796bda9d86fdb3853a5e3e524ac97d4a1efcdf4) 把 q_shiffle 移到 q_test 解決 queue.h 不能被更動的困擾。
### 統計驗證
```Shell
$ python3 test_shuffle.py
Expectation: 41666
Observation: {'1234': 41474, '1243': 41397, '1324': 41783, '1342': 41601, '1423': 41665, '1432': 41751, '2134': 42012, '2143': 41842, '2314': 41659, '2341': 41652, '2413': 41414, '2431': 41809, '3124': 41807, '3142': 41367, '3214': 41641, '3241': 41634, '3412': 41517, '3421': 42308, '4123': 41831, '4132': 41655, '4213': 41947, '4231': 41441, '4312': 41529, '4321': 41264}
chi square sum: 30.045024720395524
```
重複實驗後發現 chi square sum 大多落在區間 [15, 35]，參考自由度等於所有組合度 24 的[卡方分佈表](https://www.obhrm.net/index.php/%E5%8D%A1%E6%96%B9%E5%88%86%E5%B8%83%E8%A1%A8_Chi-Square_Probabilities)得到 P_value 屬於 [0.1, 0.9] > $\alpha$ = 0.05 。統計結果沒有達到顯著水準 $\alpha$ ，不具有統計顯著性，因此無法拒絕 shuffle 結果為 uniform distribution 的虛無假說（H0）。
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
研讀完 [lab0 (E)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-e#研讀-Linux-核心原始程式碼的-liblist_sortc) 後，可以發現這真的是一段精簡且強大的程式碼。以下我會先依照我的理解說明程式大綱，並歸列出幾個我認為重要且值得學習的地方進行說明。
### 看懂程式碼
可以發現`lib/list_sort.c`在執行 while 迴圈時把所有節點分為三類：
* 未處理（list）: 節點保持雙向鏈結，迴圈不會更改到這部份的節點。
* 待處理（pending）： 節點被更改為單向鏈結，其中 next 指向 NULL， prev 指向上一個子串列（sublist）。注意，這裡所指的只包含各以排序子串列的 head，其他已排序非子串列頭節點的 prev 指向 NULL。
* 已處理（merged）： 節點為已排序的單向鏈結串列，不同的是 next 指向比自己小的下一個節點， prev 指向 NULL。
```c
do {
size_t bits;
struct list_head **tail = &pending;
/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
/* Do the indicated merge */
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;
}
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list);
```
根據原程式註解分析從小排到大的流程：
1. 把 tail 移動到需要被 merge 的節點。
2. `a = merge(priv, cmp, b, a);`
3. `a->prev = b->prev;` 使子串列最後一個節點的 prev 指向 NULL，又因為是從長度為1的子串列開始合併，因此到最後會把所有已排序的子串列節點的 prev 都指向 NULL。
4. 把指標 `*tail` 移動到合併後子串列的 head ，好習慣確保 tail 不會指向空指標。
5. 新增一個未處理（list）節點到待處理（pending）節點，過程需要把 next 指向 NULL。
**摘要**
* bottom up 實作 merge sort 避免 cache trash。
* `for (bits = count; bits & 1; bits >>= 1)` 可以發現程式碼巧妙的發現**等長度**合併的過程其實就是一種二進位，待合併的串列長度等同 `count` 最低位的1代表的值，將計算 tail 移動的過程用位元運算捨棄四則運算。
* 完美利用雙向鏈結串列有兩個指標的優勢，在已知單向鏈結串列即可以表達一種資料結構的前提下，賦予兩種指標 `prev`、`next` 不同的資料結構意義。
* 參考以下 merge 程式碼，指標的指標（pointer to a pointer）再次在需要對節點進行移動的場合發揮作用，若不使用則會在子串列 a 、 b 其中一邊走到底時需要特別應對，而程式碼中的`if (!a) { *tail = b; break;}` 相對簡單且有效率，具有"品味"。
```c
__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
struct list_head *head, **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
**詳細探討合併規則**
為了理解合併邏輯我去參考 `lib/list_sort.c` 的註解：
>This mergesort is as eager as possible while always performing at least
2:1 balanced merges. ==Given two pending sublists of size 2^k, they are
merged to a size-2^(k+1) list as soon as we have 2^k following elements.==
可以看到目標是在第三個 $2^k$ 出現的時候馬上合併，呼應老師的講義
>合併方式是當有 $3×2^𝑘$ 個 $2^k$ 節點時，合併前兩個變成 $2^k + 1$，並留下一個 $2^k$ 不動，維持著合併：不合併為 2 : 1 的比例，因為只要 $3×2^k$ 可以放得進 L1 cache，可以避免 cache thrashing。
從老師在 lab0 的註解，可以猜測與 cache trashing 有關，已知 merge sort 在兩兩長度相等時存在最佳效率，參考以下不用進位的例子。
| count 變化 | count 二進位 | merge | pending 上的節點 |
|-----------|------------|-------|----------------|
| 15 → 16 | 1111 → 10000 | no (2⁴) | 8 ← 4 ← 2 ← 1 ← 1 |
想像今天存在一個最大容量為15個節點的快取，最晚發生 page fault 的節點情況為`8 ← 4 ← 2 ← 1`，其中此快取內無法再進行任何等長度合併，而為了達成這種類似堆積木的結構(以下簡稱堆疊)，2：1的合併規則因此誕生。
然而很簡單的可以發現現有的合併方法並非唯一能達成此種堆疊的合併方法，舉例來說，可以在每次新增節點時，都去搜尋所有可以等長合併的子串列，如下所示:
| count 變化 | count 二進位 | pending 上的節點 |
|-----------|-----------|----------------|
| 0 → 1 | 0000 → 0001 | 1 |
| 1 → 2 | 0001 → 0010 | (2) |
| 2 → 3 | 0010 → 0011 | (2) ← 1 |
| 3 → 4 | 0011 → 0100 | (4) |
| 4 → 5 | 0100 → 0101 | (4) ← 1 |
但這種合併需要花時間尋找待合併子串列的個數和位置合併效率明顯低落。
Sign in with Wallet
Connect another wallet