# 2024q1 Homework1 (lab0)
contributed by < [st10740](https://github.com/st10740) >
### Reviewed by `Terry7Wei7`
:::warning
> [name=Terry7Wei7]
> TODO : 研讀論文〈Dude, is my code constant time?〉
> 完成指令論文的閱讀和實驗
:::
### Reviewed by `SuNsHiNe-75`
- <s>沒有太大的問題及該提醒的地方，唯實作進度太慢。</s>
- `q_free` 的實作內容上運用到了兩個 `free` 函式，而 [queue.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/queue.h) 中已有相關操作之巨集 `q_release_element`，可善用之，以便寫出更簡潔易讀的程式碼。
- `q_reverse` 的實作上，可善用 [list.h](https://github.com/SuNsHiNe-75/lab0-c/blob/master/list.h) 中的 `list_move` 相關巨集進行指標調整。搭配上 `list_for_each_safe` 可以 2-3 行就完成此函式之實作，簡潔有力。
> 與其談「心法」，不如設想「如果我是你」，我會怎麼做，示範一次給同學看，而且檢討自己哪裡沒做好，從而呼應原本學員的不足處。
> 參閱學員提交的 git commits 嗎？例如 [commit 03e708d](https://github.com/sysprog21/lab0-c/commit/03e708da7530466bb3b6cd1598be6a831da8b5d1) 就值得檢討，一來混合多項不直接相關的程式碼變更，造成日後追蹤和 rebase 的困難，二來關於程式碼變更的動機和考量因素也沒探討。[軟體工程師要學會說故事](https://ruddyblog.wordpress.com/2016/06/18/)，本作業要求學員從良性詳盡的批評開始。繼續檢討！
> :notes: jserv
### Reviewed by `stevendd543`
* 在提供一樣的標頭檔下，簡化程式碼是否會破壞程式碼的一致性，如果沒有提供相關註解，反而會覺得更複雜。
* queue.h 中有提供 `q_release_element` 來安全地釋放節點占用的記憶體，可參考使用。
> 避免不精準的詞彙。在若干情境，受限於漢語的表達，"consistency" 被稱為一致性、"consensus" 也喚作一致性，"coherence" 翻譯成一致性，而 "congruent" 也翻譯為一致性，以至於當我們提及「一致性」，務必聲明其場景。反之，若你沒有探討前述領域的意圖，就不要用「一致性」。 :notes: jserv
## 開發環境
### 安裝 Win 10 + Ubuntu 雙系統
因為花了很長一段時間把雙系統裝起來，紀錄一下安裝流程、遇到的問題和解決方法。
安裝步驟主要是參考：
- [輕鬆學會 Windows / Ubuntu 雙系統安裝](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBks3DypY-)
- [如何在Windows 10系統安裝Linux雙系統](https://medium.com/hunter-cheng/%E5%A6%82%E4%BD%95%E5%9C%A8windows-10%E7%B3%BB%E7%B5%B1%E5%AE%89%E8%A3%9Dlinux%E9%9B%99%E7%B3%BB%E7%B5%B1-85ed07813270)
#### 硬體設備
可以透過按鍵盤 `Win + R` 鍵開啟 `執行`，並輸入 `msinfo32`，以查看系統資訊。
```
系統製造廠商：Acer
系統型號：Swift SF314-56G
系統類型：x64 PC
處理器：Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz，1800 Mhz，4 個核心，8 個邏輯處理器
BIOS 模式：UEFI
```
#### 安裝 Ubuntu 版本
> Ubuntu Linux 22.04.4 LTS
#### 安裝步驟
詳細設定方法可參考上文提及的參考資料，下方只列出簡短步驟：
1. 備份資料
2. 分割磁碟
我分割出 50 GB 的未配置磁碟空間給 Ubuntu，因為我的裝置只有固態硬碟 (SSD)，所以分配給 Ubuntu 的硬碟空間皆為固態硬碟。
3. 關閉 `開啟快速啟動`
可至 `系統 > 電源與睡眠 > 其他電源設定 > 選擇按下電源按鈕的行為` 頁面，點選 `變更目前無法使用的設定`，並將 `開啟快速設定` 的勾取消掉。
4. 進入 Bios 關閉 `Fast Boot` 和 `Secure Boot`
5. 製作開機碟
(1) 下載 [ubuntu-22.04.4-desktop-amd64.iso](https://releases.ubuntu.com/jammy/) 桌機映像檔。
(2) 利用 [Rufus](https://rufus.ie/zh_TW/) 製作開機碟。
6. 進入 Bios，設定通用序列匯流排 (USB) 為優先開機
7. 重新開機， 點選開機列表選項中的 `Try or Install Ubuntu`，進行 Ubuntu 的安裝
安裝類型我選擇的是 `將 Ubuntu 與 Windows Boot Manager 安裝在一起`，此方法不需要自行分配子目錄如 `\` 和 `\home` 等的磁碟空間。
#### 遇到的問題
##### Intel RST
通過上述步驟進行 Ubuntu 安裝時遇到了 `Intel Rapid Storage Technology (RST)` 的問題。由於本裝置使用的 SATA 控制器模式為 `Intel Rapid Storage Technology`，然而 Ubuntu 22.04.4 與之不兼容，因此需至 Bios 修改 `SATA` 選項，將之改成可兼容 Ubuntu 的 `AHCI`，並再次進行安裝。
然而，修改 `SATA 控制器模式` 為 `AHCI` 會導致 Win10 無法正常開機，因此需透過以下 [步驟](https://support.thinkcritical.com/kb/articles/switch-windows-10-from-raid-ide-to-ahci) 讓 Win10 從使用 Intel RST 改成使用 AHCI：
1. 以系統管理員身分執行「命令提示字元」
2. 輸入命令 `$ bcdedit /set {current} safeboot minimal`
3. 重新開機進入 Bios，將 `SATA 控制器模式` 原先的 `Intel RST` 改為 `AHCI`
4. 儲存變更後離開，Win10 系統會自動進入安全模式
5. 再次以系統管理員身分執行「命令提示字元」
6. 輸入命令 `$ bcdedit /deletevalue {current} safeboot`
7. 再次重新開機 Win10 就能自動開啟 AHCI 的驅動程式
##### Ubuntu 開機輸出錯誤訊息
Ubuntu 開機到進入系統前，會有一段黑屏並輸出大量錯誤訊息，如下所示：
````
...
[ 2.848273] r8152-cfgselector 1-4: can't set config #2, error -71
[ 3.336460] r8152-cfgselector 1-4: Failed to set configuration 1
[ 3.832347] r8152-cfgselector 1-4: Failed to set configuration 1
[ 4.336543] r8152-cfgselector 1-4: Failed to set configuration 1
...
````
其中，`Failed to set configuration 1` 訊息大量出現，雖仍能成功進入系統，但嚴重影響開機速度。
一開始我在進入 Ubuntu 系統時裝置皆有插著網路線轉 USB 接頭，在這個情境下此問題不斷重複發生，後來我將其改插至其他 USB 孔，上述提及的問題才解決，且原本進入系統時無法使用有線網路的問題有跟著解決，進一步原因有待釐清。
### 開發環境資訊
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 12
CPU max MHz: 3900.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
```
## 佇列操作實作
### `q_new` 和 `q_free`
`q_new`
在鏈結串列節點的初始化方法中，需要先確認是否能順利透過 `malloc` 方法取得可用的記憶體空間再進行其他步驟，若無法取得則直接回傳 `NULL`。
```c
struct list_head *q_new()
{
struct list_head *l = malloc(sizeof(struct list_head));
if(!l)
return NULL;
INIT_LIST_HEAD(l);
return l;
}
```
`q_free`
我利用`list.h` 提供的 `list_for_each_entry_safe` 來走訪佇列中的每個節點並分別釋放他們的記憶體空間，此方法可避免指標指向被釋放的記憶體空間而無法往前走訪串列的問題。此外，因為使用的結構是雙向環狀鏈結串列，為了避免發生無窮迴圈，中止條件為鏈結串列中剩下一個 `head` 指標指到的節點即停止，所以最後仍須釋放 `head` 指向的記憶體空間才算全部釋放完成。
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *item, *tmp;
list_for_each_entry_safe(item, tmp, head, list) {
free(item->value);
free(item);
}
free(head);
}
```
我參考了 [SuNsHiNe-75](https://hackmd.io/@8gdFdQxMR8O0u3u7xLQmxA/r1V9YJI26) 和 [stevendd543](https://hackmd.io/@stevennnnnn/linux2024-homework1) 同學提供的 review 建議，利用 `queue.h` 中提供的 `q_release_element` 方法釋放節點的記憶體空間，其他方法中可以使用到 `q_release_element`的地方我也一併做修改。
> [commit 28b8333](https://github.com/st10740/lab0-c/commit/28b833382be19182fd2671eaa46adf201fa220bf)
```diff!
list_for_each_entry_safe(item, tmp, head, list) {
- free(item->value);
- free(item);
+ q_release_element(item);
}
```
### `q_insert_head` 和 `q_insert_tail`
> [commit 03e708d](https://github.com/sysprog21/lab0-c/commit/03e708da7530466bb3b6cd1598be6a831da8b5d1)
`q_insert_head` 和 `q_insert_tail` 都需要先動態配置新記憶體空間給新產生的節點，接著再分別插入到鏈結串列中的不同位置，插入的方式可以使用 `list.h` 提供的 `list_add` 和 `list_add_tail` 方法，因此將實作相同方法的部份抽出成新的函式`q_insert`，再利用函式的指標將 `list_add` 和 `list_add_tail` 分別傳入。
```c
bool q_insert_head(struct list_head *head, char *s)
{
return q_insert(head, s, list_add);
}
bool q_insert_tail(struct list_head *head, char *s)
{
return q_insert(head, s, list_add_tail);
}
```
### `q_remove_head` 和 `q_remove_tail`
> [commit 03e708d](https://github.com/sysprog21/lab0-c/commit/03e708da7530466bb3b6cd1598be6a831da8b5d1)
`q_remove_head` 和 `q_remove_tail` 方法分別需要將串列中的第一個節點和最後一個節點從串列中移除，第一個節點可以透過 `head->next` 取得，而最後一個節點則可以透過 `head->prev` 取得，取得節點後可以透過另外抽出的函式 `q_remove` 將該節點移除。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
return q_remove(head, head->next, sp, bufsize);
}
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
return q_remove(head, head->prev, sp, bufsize);
}
```
在 `q_remove` 函式中，需要將移除掉的節點 `value` 字串複製到 `sp` 中，原先我的作法是利用 `strncpy(sp, removed_ele->value, bufsize);` 的方式進行複製，但是根據 C 語言規格書 C99 7.21.2.4 描述：
> The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1.
我未考慮到 `removed_ele->value` 字串長度比 `bufsize` 長的情況，導致從 `removed_ele` 中複製了 `bufsize` 個字元到 `sp` 中，但是沒有加上空字元 (null character) ，因此我進行了以下的修正。
```diff
- strncpy(sp, removed_ele->value, bufsize);
+ strncpy(sp, removed_ele->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
```
> [commit 5fe4b10](https://github.com/sysprog21/lab0-c/commit/5fe4b103ec253aa4ecf5f299e68cd076eb7c01e1)
### `q_delete_mid`
> [commit 859b3e7](https://github.com/sysprog21/lab0-c/commit/859b3e73c0cecd275d681d80acf76f58a3501662)
我參考龜兔賽跑演算法，做法是先找到中間節點再將其刪除，其中找中間節點的方法為利用兩個指標 `slow` 和 `fast` 走訪整個鏈結串列，`slow`節點每次走一步到下個節點，而 `fast` 則每次走兩步到下下個節點，兩者的速度相差 2 倍，因此當 `fast` 到達串列的終點時，`slow` 指向的節點即為欲刪除的中間節點。
在實作時發現到，不能直接針對動態配置空間的結構體中的成員變數進行動態記憶體釋放 `free`，會引發 `Segmentation fault` 。利用 Valgrint 觀察發現會引發如下的錯誤訊息：
```shell
$ valgrind -q --leak-check=full ./qtest
cmd> new
l = []
cmd> ih a
l = [a]
cmd> ih b
l = [b a]
cmd> ih c
l = [c b a]
cmd> dm
ERROR: Attempted to free unallocated block. Address = 0x4b83de8
ERROR: Attempted to free unallocated or corrupted block. Address = 0x4b83de8
==4110== Invalid read of size 8
...
```
`ERROR: Attempted to free unallocated block. Address = 0x4b83de8` 訊息表示欲釋放的記憶體位址並沒有藉由 `malloc` 動態配置出來，推測與 `test_malloc` 的實作方式有關，因為 `slow` 指標指向位於 `element_t` 結構體中的 `list` 成員變數，該成員變數所在的記憶體空間是透過對 `element_t` 結構體進行動態配置一同配置而來的，`test_malloc` 實作方法中只有紀錄到 `element_t` 結構體的位址，因此無法單獨釋放成員變數的記憶體空間，須直接釋放整個結構體的空間。
（TODO : 探討原先 `malloc`, `free` 實作原理是否也是用類似機制）
```diff
- free(slow);
+ list_del(slow);
+ element_t *entry = list_entry(l, element_t, list);
+ free(slow_entry->value);
+ free(slow_entry);
```
### `q_delete_dup`
> [commit db7450e](https://github.com/sysprog21/lab0-c/commit/db7450e13dfe47676dfdc4604be82674246a86f1)
我利用兩個指標偵測相鄰節點的成員變數 `value` 是否有重複值的情形，若有則將其中一個指標指向出現重複值的子串列中的第一個節點，另外一個指標指向最後一個節點，接著將該子串列利用 `list.h` 中的`list_cut_position` 移至用來刪除節點的新串列 `del_q` 中，最後再一次釋放 `del_q` 的記憶體空間。
```c
for (prev = head->next, cur = prev->next; cur != head && prev != head;
prev = cur, cur = cur->next) {
while (cur != head &&
strcmp(list_entry(cur, element_t, list)->value,
list_entry(prev, element_t, list)->value) == 0) {
cur = cur->next;
}
if (prev->next != cur) {
list_cut_position(del_q, prev->prev, cur->prev);
}
}
```
雖然這個方法寫起來簡潔，利用到 `list.h` 提供的巨集和已經寫好的 `q_free()` 方法，然而因為需要將重複值的子串列移至新的串列中再一次釋放，效能相對邊偵測重複值的節點邊釋放該節點的方法差。
跑了測試項目 `trace-06-ops.cmd` 發現到，在執行了下列的佇列操作命令後遇到了 `ERROR: There is no queue, but 10 blocks are still allocated` 的錯誤，表示有記憶體空間未釋放完全，經後續一個個插入新字串測試後才發現到，我寫的 `q_delete_dup` 方法只能成功釋放掉一種重複出現字串，當出現兩種以上重複出現字串就沒辦法釋放完全。
```shell
cmd> new
cmd> ih RAND 4
cmd> it gerbil 3
cmd> it lion 2
cmd> it zebra 2
cmd> sort
cmd> dedup
cmd> free
```
原因是我利用 `list_cut_position` 將待刪除的節點移至 `del_q`，但 `list_cut_position` 會將原本已經接在 `del_q` 上的串列斷開改接新加入的串列，因此被斷開的串列在最後無法被釋放到。因此，我改成利用 `list_cut_position` 將待刪除的節點移至新建立的 `tmp_del` head 上，再利用 `list_splice` 將該串列移到 `del_q` 串列的末端。
```diff
- list_cut_position(del_q, prev->prev, cur->prev);
+ LIST_HEAD(tmp_del);
+ list_cut_position(&tmp_del, prev->prev, cur->prev);
+ list_splice(&tmp_del, del_q);
```
後來，我考慮到這樣的作法在效能和程式碼簡潔程度上沒有比起邊偵測重複節點邊刪除的方式來得好，所以我將實作方法改成後者，並且有參考 [vax-r](https://hackmd.io/@vax-r/linux2024-homework1) 的作法。過程中利用 `list_for_each_entry_safe` 將走訪過的重複節點刪掉，因最後還會遺留下一個屬於重複節點但未被刪除的節點，因此有利用一個布林值變數紀錄刪除行為何時開始何時結束，來判斷是否刪除該節點。
> [commit eae51ae](https://github.com/sysprog21/lab0-c/commit/eae51aee96049ae35ba57dc58df5a45f21596d4a)
### `q_swap`
> [commit d4c83b2](https://github.com/sysprog21/lab0-c/commit/d4c83b27b72735ed75d90aed3e1a098d11f50086)
這個方法的目的是將兩兩相連的節點變換位置，因此我的作法是利用 `list.h` 中的 `list_move` 將前一個節點取下，移動到下一個節點之後，減少因自行操作指標易發生的錯誤。
```c
struct list_head *cur, *next;
for (cur = head->next, next = cur->next; cur != head && next != head;
cur = cur->next, next = cur->next) {
list_move(cur, next);
}
```
這邊值得注意的是，`cur` 指標的更新方式為 `cur = cur->next`，其中 `cur` 指向欲交換位置的兩個節點中的前一個節點， `next` 指向後一個節點，直觀來想 `cur` 的位置更新需要往後走兩格，因為每一個單位為兩個節點，但因為兩兩節點交換了位置，`cur` 指標所指向的節點被移動到後面，所以只需要走一步就能指到下一個單位的正確位置。
### `q_reverse`
> [commit de19049](https://github.com/sysprog21/lab0-c/commit/de19049255990d3b218b2a5db0940406c911b551)
由於 `q_reverse` 方法需要將兩兩節點的 `next` 和 `prev` 方向反轉，需要使用額外的指標紀錄下一個前往的節點位置，因此利用 `list.h` 中的 `list_for_each_safe` 走訪，以 `safe` 紀錄下一個前進的位置。
```c
struct list_head *cur, *prev, *safe, *list_tail = head->prev;
list_for_each_safe (cur, safe, head) {
prev = cur->prev;
cur->next = prev;
prev->prev = cur;
}
cur->next = list_tail;
list_tail->prev = cur;
```
### `q_reverseK`
> [commit c0e8030](https://github.com/sysprog21/lab0-c/commit/c0e80303d8d42fc1d3f91dbb5360c36162b9e326)
我利用兩個指標 `headK` 和 `tailK` 分別指向欲反轉的 k 個節點子串列的頭和尾，再利用額外寫的 `q_reverse_position` 方法將子串列中兩兩節點的 `next` 和 `prev` 指標反轉，最後再將反轉後的子串列接回原本的鏈結串列中。
其中 `headK` 和 `tailK` 指標定位的方式是先讓 `headK` 指到正確的節點，再將 `tailK` 以 `headK` 指到的節點為開頭往後走 k 個節點，過程中會判斷是否超出整個鏈結串列的最後一個節點，若超出則根據題意不做反轉。
```c
int tmpK = k - 1;
bool break_flag = false;
while (tmpK--) {
if (tailK == head) {
break_flag = true;
break;
}
tailK = tailK->next;
}
if (break_flag || tailK == head)
break;
```
然而，這種先找到頭尾再做反轉的方法寫起來沒那麼簡潔，如上面程式碼所示，速度也沒有比邊找子串列的尾端節點邊反轉指標來得快，因為需要跑整個串列兩次，而邊找邊反轉的方式只需要跑整個串列一次，因此我之後想改成上述提及的方法來實作。
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
### `q_ascend` 和 `q_descend`
> [commit 9e1ffd6](https://github.com/sysprog21/lab0-c/commit/9e1ffd65ecc9249fcadb53619fe197a777cc00d0)
這個方法我參考了 [Leetocde Solution](https://leetcode.com/problems/remove-nodes-from-linked-list/solutions/4152665/beats-99-using-iterative-approach/) 的做法，他的想法為從串列的尾端走訪至前端，若是 `q_ascend` 則走訪的過程中節點的值應為遞減，若中間出現節點打破遞減的規則則將它從串列中移除，`q_descend` 方法反之亦然。
此外，因為 Leetcode 上的題目為單向的鏈結串列，需要先做反轉再做上述處理，最後還需要再反轉回來，但因為這邊使用的是雙向的鏈結串列，所以可以直接透過 `head->prev` 取得尾端的節點，不需要多做反轉的動作。
我在跑了測試程式 `trace-06-ops.cmd` 後發現，題目的要求是移除掉的節點記憶體空間需要釋放掉，但原本實作中未做這個部份，導致測試過不了，因此我利用下面的 commit 進行修正：
> [commit 515ba4f](https://github.com/sysprog21/lab0-c/commit/515ba4f4da33543fde204a2d94d28882bb015250)
### `q_sort`
> [commit 79c47c4](https://github.com/sysprog21/lab0-c/commit/79c47c403479f554a7ae6d35841569cb5cbc60a5)
起初我在實作這個方法並測試時觸發了 `FATAL ERROR: Calls to malloc disallowed` 的錯誤，看了 `qtest.c` 才知道測試不允許 `q_sort` 的實作利用 malloc 動態配置新的節點，而觸發錯誤訊息的原因是我利用合併排序法進行排序，需要產生新節點分別用來接左右兩半的子串列。後來我參考 [jujuegg](https://hackmd.io/@jujuegg/HkYOnnBn6) 的做法才想到其實可以透過 `list.h` 的 `LIST_HEAD` 靜態配置新的節點，因為新產生的節點只是用來當作子串列的 head，不用存值，所以不需要使用動態配置的方式，過去太過依賴利用動態配置的方式產生新節點了。
:::danger
在 Linux 核心中，優先考慮 in-place 演算法。
:::
此外起初在實作 `q_sort` 時，我的做法為一個個操作每一步指標指向的位置，沒有使用 `list.h` 提供的巨集，複雜的邏輯使我除錯相當不易，因此在參考 jujuegg 的做法後發現透過 `list.h` 中的巨集可以完成許多合併排序法中複雜的邏輯，所以最後我也改成利用巨集中的方法來實作。
:::danger
你如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::
### `q_merge`
> [commit 0edc246](https://github.com/sysprog21/lab0-c/commit/0edc246afa74dd47171bb72c1dc7df1101792503)
實作這個方法需要參考 `queue.h` 中的結構體：
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
`q_merge` 的目標是將多條已排序的串列合併成一條串列，`queue_context_t` 中 `chain` 的目的是利用鏈結串列串接多條串列，而 `q` 則是指向該串列的 head。因此可以透過走訪 `chain` 來走訪每條串列。
合併多條串列的方式我參考 〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉中的 Merge Two Sorted Lists 案例探討中的「頭跟尾兩兩合併」方法，此方法透過不斷合併頭尾兩兩串列的方式將全部串列合併成一條，透過頭尾合併的方式能讓兩兩待合併串列的長度比起利用單一串列不斷與其他串列合併的方式來得平衡，可以合併得更快。
這邊分別比較「利用單一串列不斷與其他串列合併」和「頭跟尾兩兩合併」的方法進行鏈結串列合併的時間複雜度：
假設共有 $5$ 條串列需合併，長度分別為 $n_1, n_2, n_3, n_4, n_5$，若利用「單一串列不斷與其他串列合併」的方式，則第一輪要合併 $n_1$ 和 $n_2$，最差情況下需要花 $O(n_1+n_2)$ 的時間複雜度走訪過兩者，接著第二輪要將合併後的 $n_1$ 和 $n_2$ 與 $n_3$ 合併起來，故需要花 $O(n_1 + n_2 + n_3)$ 的時間，以此類推，最後總共需要花上：
$O((n_1 + n_2) + (n_1 + n_2 + n_3) + (n_1 + n_2 + n_3 + n_4) + (n_1 + n_2 + n_3 + n_4 + n_5))$
$=O(4n_1 + 4n_2 + 3n_3 + 2n_4 + n_5)$
的時間複雜度。
若是採用「頭跟尾兩兩合併」的方法進行合併，則第一輪合併 $n_1$ 和 $n_5$，需要花 $O(n_1+n_5)$ 的時間複雜度；第二輪合併 $n_2$ 和 $n_4$，需要花 $O(n_2+n_4)$ 的時間複雜度；第三輪合併 $n_1$ 和 $n_5$ 合併後的串列與 $n_2$ 和 $n_4$ 合併後的串列，需要花 $O(n_1+n_2+n_4+n_5)$ 的時間複雜度；第四輪將 $n_3$ 也合併進來，需要花 $O(n_1+n_2+n_3+n_4+n_5)$ 的時間複雜度，故總共需花上：
$O((n_1 + n_5) + (n_2 + n_4) + (n_1 + n_2 + n_4 + n_5) + (n_1 + n_2 + n_3 + n_4 + n_5))$
$=O(3n_1 + 3n_2 + n_3 + 3n_4 + 3n_5)$
由上面結果可以發現到，利用「單一串列不斷與其他串列合併」的方式會使第一個串列長度佔整體時間複雜度的權重最大，隨後慢慢遞減；而利用「頭跟尾兩兩合併」的方法各條串列的長度佔整體時間複雜度的權重較平均，因此會推測當所有要合併的子串列長度差異不大，或是排序比較前面的子串列長度較長時，使用「頭跟尾兩兩合併」的方式速度較快，但如果是排序比較前面的子串列長度較短，越後面越長的情況下，結果可能不一定，需要再做實驗確認。
:::danger
用數學分析來量化合併多個鏈結串列的記憶體操作成本。
> 了解
:::
因為原文中是利用陣列的方式紀錄每條串列的 head，可以直接透過索引的方式取得欲進行合併的串列，這邊則是使用鏈結串列，因此在取得串列的方式上略有不同。我分別利用 `first` 和 `second` 兩個指標指向待合併的頭尾串列，在每一輪中不斷把 `first` 往 `next` 方向移動，把 `second` 往 `prev` 方向移動，直到 `first` 和 `second` 發生交錯為止，即第 5 行。當發生交錯時代表要進行下一輪的合併，假設本輪的串列數為 $chain_size$，下輪的總合併串列數降至 $\lfloor \dfrac{(chain_size\ +\ 1)}{2} \rfloor$，此時需將 `first` 指回第一個串列，`second` 則不需要更動，因為當發生交錯時其指向的串列已是下一輪欲合併的串列中的最後一個。
```c=
int chain_size = q_size(head);
struct list_head *first = head->next, *second = head->prev;
while (chain_size > 1) {
for (;; first = first->next, second = second->prev) {
if (first == second || first->prev == second) {
first = head->next;
break;
}
// ...
}
chain_size = (chain_size + 1) / 2;
}
```
---
## 研讀 Linux 核心原始程式碼的 lib/list_sort.c
### 程式碼理解
`list_sort` 利用另外一個鏈結串列 `pending` 來處理待進行合併的節點，傳入的串列 `list` 和 `pending` 皆利用 `list_head` 結構體來實作。不過有趣的是，`pending` 上的元素可以視為一個子串列並利用 `prev` 串接起來，子串列內的節點皆已排序過，利用 `next` 串接起來，這樣的作法可以善用結構體上的每一個指標，也讓我體悟到 `list_head` 不一定都要拿來實作雙向鏈結串列。
其中，判斷是否有可以合併的子串列的方法為判斷 `pending` 中是否存在 $3\times2^k$ 個節點 （不一定要剛好 $3\times2^k$ 個節點），合併前兩個 $2^k$ 個節點構成的子串列，留下剩下一個 $2^k$。其在程式碼中的實作方式說明如下：
利用 `count` 存 `pending` 中的節點數，當 `count` 變成 `count + 1` 時，第 k 個位元會變為 $1$，第 $0$ ~ $(k - 1)$ 個位元皆為 $0$，接著會判斷 `count + 1` 的值是否為 $2^k$，若不是則合併兩個長度為 $2^k$ 的子串列，且合併的子串列正好為 `pending` 中的第 $k$ 個和第 $(k + 1)$ 個子串列。
`tail` 會不斷更新指向的節點，最後會指向待合併的子串列，也就是 for 迴圈會執行 $k$ 次，因為目標是找從 `count` 變成 `count + 1` 時第幾個位元會變成 $1$，所以可以透過判斷 `count` 位元值為 $0$ 的最低位元是第幾位元來得到 $k$ 。
```c
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;
```
我對於上面如何找到 $k$ ，且 $k$ 正好可以滿足「存在 $3\times2^k$ 個節點」的實作方式理解是，當排除了 `count + 1` 的值正好為 $2^k$ 的情況後，必定存在第 $m$ 個位元，且 $m > k$ ，使得第 $m$ 的位元為 $1$，在最差情況下 $m = k + 1$，此時必定存在 $2^{k+1} + 2^k$ 個節點，即 $3\times2^k$ 個節點，因此透過這樣的方式可以確保找到的 $k$ 滿足可以合併的節點數。
閱讀程式碼時，注意到 `likely(bits)` 的寫法，其為 Linux 核心原始程式碼提供的巨集，`__builtin_expect` 是 GCC 提供的函式，根據 [Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的說法，`__builtin_expect` 會提供分支預測的資訊給編譯器，而決定 `__builtin_expect` 的回傳值為 `true` 的機率是受到 GCC 中的參數 `builtin-expect-probability` 所控制。另外注意到 `!!(x)` 的寫法，因為 `__builtin_expect` 會比較兩個參數的值是否相同，且必須為整數值，故透過 `!!(x)` 可以確保結果為 0 或 1。
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
另外觀察到 `list_sort` 函式上面有 `__attribute__((nonnull(2,3)))` 的寫法，首先觀察到 `nonnull`，它是 GCC 提供的一個 attribute，作用是限定哪些傳入的指標參數不能為空值 (NULL)，此外編譯器也可以透過得知哪些參數不能為空值的資訊進行最佳化。因此下方的程式碼指定 `head` 和 `cmp` 不能為空值。
```c
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
```
#### 圖解
### 引入到 `lib0` 專案
> [commit 9d85eae](https://github.com/st10740/lab0-c/commit/9d85eaeccc75d08ce40bed22d97fa6fc34f8984d)
我將 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 和 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 檔案從 `linux` 中複製到 `lib0` ，並將其用來引用 linux 內部函式庫的 `#include` 指示詞移除，並根據需求補上相關方法。以外，我也將 `list_sort.c` 最後一行的 `EXPORT_SYMBOL(list_sort)` 移除，該方法的目的是將 Linux 核心模組中的函式對整個核心公開，讓其他核心模組調用，因此此處不需要使用。
`list_sort.h`
```diff
- #include <linux/types.h>
+ #include "list.h"
```
`list_sort.c`
```diff
- #include <linux/kernel.h>
- #include <linux/bug.h>
- #include <linux/compiler.h>
- #include <linux/export.h>
- #include <linux/string.h>
- #include <linux/list_sort.h>
- #include <linux/list.h>
+ #include <stdint.h>
+ #include "list_sort.h"
+ #define likely(x) __builtin_expect(!!(x), 1)
+ #define unlikely(x) __builtin_expect(!!(x), 0)
...
__attribute__((nonnull(2, 3, 4, 5))) static void merge_final(
void *priv,
list_cmp_func_t cmp,
struct list_head *head,
struct list_head *a,
struct list_head *b)
{
struct list_head *tail = head;
- u8 count = 0;
+ uint8_t count = 0;
...
- EXPORT_SYMBOL(list_sort);
```
由於 Git pre-commit hook 限制不能修改 `queue.h`，因此無法加入新的命令專門給 list_sort 使用，於是我將 list_sort 整合進 `queue.c` 的 `q_sort` 方法中，為了方便後續比較自己實作的 Merge sort 和 list_sort 之間的效能落差，我利用條件編譯的方式決定要編譯 `list_sort` 還是 `merge_sort` 方法，當 `lsort` 設定為 1 時即編譯 `list_sort`，當設定為其他值時則編譯 `merge_sort`。
```c
#define lsort 1
...
void q_sort(struct list_head *head, bool descend)
{
#if (lsort == 1)
list_sort(&descend, head, cmp);
#else
merge_sort(head, descend);
#endif
}
```
`q_sort` 方法可以決定排序結果是遞增或遞減，為了使 `list_sort` 達到這個目的，我注意到 `list_sort` 可以傳入指標 `priv` 當作參數，其在 `list_sort` 中的作用是傳入用來比較待合併的兩個元素的`cmp` 方法中，因此我將 `descend` 的位址傳入，利用它來判斷合併時應該先接值較小的元素還是大的元素，不過不知道這樣的作法會不會有什麼副作用？
```c
int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
bool descend = *(bool *) priv;
char *a_val = list_entry(a, element_t, list)->value;
char *b_val = list_entry(b, element_t, list)->value;
return descend ? strcmp(b_val, a_val) : strcmp(a_val, b_val);
}
```
### 比較自行實作的 Merge sort 和 list_sort 之間的效能落差
我參考 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#%E6%95%88%E8%83%BD%E6%AF%94%E8%BC%83) 的作法，利用 `perf` 進行效能評估測試，並參考 [Linux 效能分析工具: Perf](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 的介紹。
我將以下命令存成 `trace-sort-1000.cmd` 檔進行測試：
```shell
new
ih RAND 1000
sort
```
並利用以下命令分析以上操作的 CPU cycles 和 cache miss 事件，這邊的 `sort` 是使用我自行實作的 Merge sort 方法，`--repeat 5` 代表執行 `./qtest -f traces/trace-sort-1000.cmd` 五次再取它的平均值和標準差。
```shell
$ perf stat --repeat 5 -e cycles,cache-misses ./qtest -f traces/trace-sort-1000.cmd
...
Performance counter stats for './qtest -f traces/trace-sort-1000.cmd' (5 runs):
4,208,462 cycles ( +- 1.02% )
17,340 cache-misses ( +- 31.48% )
0.002624 +- 0.000160 seconds time elapsed ( +- 6.09% )
```
接著我分別將 Merge sort 和 list_sort 實作在不同長度的資料上，並進行 CPU cycles 和 cache misses 的分析，分析結果如下圖：
> [commit 0655681](https://github.com/sysprog21/lab0-c/commit/0655681849a3ca9c65cb67761c3a371505ba9cf1)
觀察結果發現，Merge sort 和 list_sort 在資料量較少的時候 CPU cycles 和 cache misses 的結果不會差距太大，但隨著資料量增加，Merge sort 的 cache misses 次數和 CPU cycles 數量皆超過 list_sort，且差距越來越大。原因是我實作的 Merge sort 是採用 top-down 的策略，因為需要先進行分割再進行合併，導致分割過程中被放進快取的資料若沒有馬上被拿來合併，有機會再次被移出快取，對快取不友善；而 list_sort 在設計合併方法上有考慮到快取，並且是採用 bottom-up 的機制，因此在 cache misses 上有較好的表現，連帶使得 CPU cycles 數量較少。
Sign in with Wallet
Connect another wallet