---
# System prepended metadata

title: 圖解 Linux 核心原始程式碼 list_sort.c
tags: [linux2023]

---

---
tags: linux2023
---

# 圖解 Linux 核心原始程式碼 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
嘗試靠圖解的方式來徹底了解 Linux 核心原始程式碼中 lib/list_sort.c 的作法。
##  合併方式及原理
合併方式是當有 $3 \times 2^k$ 個節點時，合併前兩個 $2^k$ 變成 $2^{k + 1}$，並留下一個 $2^k$ 不動，維持著合併：不合併為 2 : 1 的比例，因為只要 $3 * 2^k$ 可以放得進 L1 cache，可以避免 cache thrashing。參考動畫如下，首先每個節點都視為一個獨立的 link list，另外可以注意到，最優先合併的都是最左邊的 link list，對應原文 “This cache-friendly depth-first merge order depends on us merging the
beginning of the input as much as possible before we've even seen the
end of the input (and thus know its size).”：
![Jan-06-2024 13-24-07](https://hackmd.io/_uploads/SJTV4PU_6.gif)

至於為何要保持 2:1 的比例，如果合併的狀況為 1024:4，合併效率會很差（甚至 1024:1 會比較好，這裡原文是寫 1204，應該是筆誤了？詳情請見[文章](https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1957556.html)），假如是 3:2 的比例，第二次合併會變為 9:4，少於 2:1，繼續合併下去整個比例差距會更懸殊，詳情請見[文章](https://hackmd.io/@sysprog/linux2023-lab0-e#%E7%82%BA%E4%BB%80%E9%BA%BC-list_sort-%E4%B8%AD%E4%B8%B2%E5%88%97%E5%A4%A7%E5%B0%8F%E7%9A%84%E6%AF%94%E4%BE%8B%E5%B7%AE%E8%B7%9D%E9%99%90%E5%88%B6%E6%98%AF%E4%BA%8C%E6%AF%94%E4%B8%80)。
## 程式碼解析
程式碼的部分，首先整理一下各段落的動作：
```c
void list_sort(){
    初始化;
    do {
        選擇要排序的兩條 link list;
        執行合併;
        添加一個元素到準備排序區;
    } while(結束)
    for (;;){
        合併剩餘的 link list 直到剩下兩個 link list
    }
    最後合併剩下的兩個 link list，並把個節點的 prev 串好;
}
```
### do-while迴圈
在do-while迴圈中，要特別留意的是先進行排序，然後再加入新節點。在進行排序的判斷時，**可以將尚未加入的節點視為待排序的一部分**，這是因為如果該節點不存在，會先跳出 while 迴圈，不會執行到這個步驟。
我之前忽略了這個順序，所以一直想不透為何在 count = 5 時，準備合併的節點數有 5 個，執行合併會不滿足 2:1，但是卻可以合併。理解後整理成動畫就清楚多了：

![Jan-05-2024 11-44-50](https://hackmd.io/_uploads/H1JUsgHu6.gif)

1. count = 5 時，即將加進來的節點也算入待排序，所以待排序的比例為（2:2:1:1），剛好能夠形成 2:1（4:(1+1)）的比例，所以 node3->node4 與 node2->node1 執行合併。
3. 合併完成後，再實際將 node6 加入到待排序的隊伍中，count = 6。

規則知道了，接著說明該如何實現以及控制這個流程，首先分析之前提過的 3 個動作：
1. 選擇要排序的兩條 link list
2. 執行合併
3. 添加一個元素到準備排序區

動作3是最簡單的，每次執行時都不需要進行判斷。
而動作 1 和 2 只需透過一個整數計數器 count 就能夠判斷是否執行，count 記錄了待排序隊伍的數量。可以注意到排序為兩兩一組，使得整數的二進位能夠很好的控制以及表示目前排序的情況。在[原文](https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1957556.html)的註解有提到 count 的排列組合，文字說明太難懂了，這裡我直接用圖去演示。
#### 初始化
首先做初始化：
```c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0;
head->prev->next = NULL;
```
![image](https://hackmd.io/_uploads/HyZ3ijYPp.png)
pending 底下的 node 代表準備排序的節點，而 list 底下的 node 代表尚未準備排序的節點。因為準備排序的節點為零，所以 count = 0 (0b00)。這裡的顏色我配合上面的動畫（綠：準備合併、黃：等待合併、紅：未加入合併）
#### count = 0
1. 首先進入判斷動作 1 的環節：
`for (bits = count; bits & 1; bits >>= 1)` 0 & 1 = 0，故 `struct list_head **tail = &pending;` 因為實際不用執行合併，所以 `**tail` 指向哪裡其實不用在意。
2. 接著判斷動作 2，是否執行合併：
`if (likely(bits))` 關於 likely() 是編譯優化用，作用為告訴編譯器與 CPU 高機率會走哪個分支，避免指令被 flush 的狀況，詳情請參照此篇[文章](https://zhuanlan.zhihu.com/p/357434227)。所以這個判斷式純粹判斷 bits 是否為 0，為 0 就不進行合併。
3. 執行動作 3，將節點納入到準備排序中（黃），將準備排序中的節點視做獨立的 link list，所以尾端的 next 都指向 null：
```c
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
![截圖 2023-12-27 下午9.48.35](https://hackmd.io/_uploads/rkZUioFwp.png)
#### count = 1
同樣執行三個動作，預先說明 count = 1 不會做合併，所以同樣 `**tail` 指向哪裡（動作 1）其實不用在意。
`for (bits = count; bits & 1; bits >>= 1)` 經過 for 迴圈後，bits = 0，故動作 2 `if (likely(bits))` 為 false，不執行合併。
直接跳到動作 3，加入節點。
![image](https://hackmd.io/_uploads/rkoj0iYwT.png)
#### count = 2
1. 首先進入判斷動作 1 的環節：
`for (bits = count; bits & 1; bits >>= 1)` 0b10 & 1 = 0，故 `struct list_head **tail = &pending;` 因為要執行合併，所以 `**tail` 指向哪裡就很重要。這裡需要執行合併的原因，如同前文提過的，雖然等待合併的區域裡只有兩個節點，然而這一個 iteration 最後新增進來的節點（橘色 node 3）也要算進去，所以當 node 1 合併 node 2 後，等待合併的區域能夠遵守 2:1 的規則。
![image](https://hackmd.io/_uploads/BygCkhFvT.png)

2. 接著判斷動作 2，確定執行合併，這時候出動`struct list_head *a = *tail, *b = a->prev;
` 兩個指標指向要合併的兩個 link list。合併完成後的兩個動作很重要：
    1. `a->prev = b->prev;` pending 的 link list 是靠 prev 串起，所以確保合併後的 link list 的 prev 要指向上一個合併好的鏈結，因為現階段未有合併好的鏈結，所以 a->prev = b->prev = NULL。
    2. `*tail = a;` 將 pending 指向合併好的鏈結的頭，讓待會新進來的 node3 的 prev 能夠指到這個合併好的鏈結的頭。
    
    a, b 合併後的動作很像我上一篇在 q_sort 所做的[動畫](https://hackmd.io/@jerrychuang/jerry_lab0-c#q_sort)前半部。
3. 執行動作 3，將 node3 納入到準備排序中（黃），next 指向 null，綠色表示這輪執行合併的鏈結串列。這裡省略了其餘 prev 指向的地方，因為不重要。
![image](https://hackmd.io/_uploads/Byt9B2Yv6.png)
#### count = 3
與 count 為 1 的狀況相同， `for (bits = count; bits & 1; bits >>= 1)` 經過 for 迴圈後，雖然重定向了 `**tail`，但是 bits = 0，故動作 2 `if (likely(bits))` 為 false，不執行合併，所以 `**tail` 指向哪裡就不重要。
直接跳到動作 3，加入節點。
![image](https://hackmd.io/_uploads/HkpDNdLO6.png)

#### count = 4
與 count 為 2 的狀況相同，node 5 在這個 iteration 結束後會被加入到 pending 底下，所以比例仍可以保持 2:1。
![截圖 2024-01-06 下午2.38.27](https://hackmd.io/_uploads/B1GYBOUO6.png)


1. `**tail` 不需要重定向（0b100），`struct list_head **tail = &pending;`。
2. node4 與 node3 合併。確保合併後的頭節點 prev 指向上一個合併的頭節點 node2。
3. 執行動作 3，將 node5 納入到準備排序中（黃），next 指向 null，綠色表示這輪執行合併的鏈結串列。
![image](https://hackmd.io/_uploads/rJ1CE_IuT.png)

#### count = 5
狀況較為特殊（0b101），此輪需要被合併，且 tail 也會移動。
node 6 在這個 iteration 結束後會被加入到 pending 底下，所以兩個長度為 2 的綠色的 link list 可以合併，合併後的比例能夠遵守 2:1 規則（4:(1+1)）。
1. `**tail` 需要重定向，初始 `struct list_head **tail = &pending;`。因為動作 1 的判斷，執行一次`tail = &(*tail)->prev;`。
![image](https://hackmd.io/_uploads/Hk-jXTFv6.png)

2. node3->node4 與 node2->node1 執行合併。並確保合併後的頭節點 的 prev 指標（藍色），指向上一個合併的頭節點（NULL）。並將 `*tail` （前一個 link list 的頭節點）指向合併後的頭節點（node3），確保整個鏈結串列不會亂掉。
![image](https://hackmd.io/_uploads/BkBrVTYva.png)

4. 執行動作 3，將 node6 納入到準備排序中（黃），next 指向 null，綠色表示這輪執行合併的鏈結串列。
![image](https://hackmd.io/_uploads/rJrMUTYPp.png)
這時 `*list` 指向 NULL 跳出 do-while 迴圈。結束動作 1~3。
### 合併剩餘鏈結串列
將 `*pending`, `*list` 指回前一個 link list 後。進入 for 迴圈。
```c
for (;;) {
    struct list_head *next = pending->prev;

    if (!next)
        break;
    list = merge(priv, cmp, pending, list);
    pending = next;
}
```
![image](https://hackmd.io/_uploads/B1FCEIqP6.png =70%x)
這時要合併的對象變為 `*pending`, `*list` 指向的兩個 link list，因為合併後順序可能會亂掉（如果 node6 變為合併後 link list 的頭，那此頭的 prev 指向錯誤的 node5），所以額外指派了一個 `*next` 指向待會要合併的 link list，就不仰賴頭的 prev 指標（同 for_each_safe 的用法）。
當合併完成後 `*list` 保持不動，只需改變 `pending = next;` ，即可更新下一輪合併的對象。
可以發現，就算`*pending`, `*list` 沒有串連在一起，都能夠找到要合併的兩個 link list（`*pending`, `*list`）。
![image](https://hackmd.io/_uploads/rkwfdU5Da.png =70%x)
當 next 指向 NULL 時跳出 for 迴圈。意味著只剩下兩條 link list 需要被合併，接著執行最後的指令 `merge_final()`。
### merge_final
`merge_final` 的任務很單純，就是將其餘的兩組 link list 合併，並將各自節點的 prev 指標指向正確的位置，最後頭尾串接在一起，得到排序完成的 `*head`。如同q_sort [動畫](https://hackmd.io/@jerrychuang/jerry_lab0-c#q_sort)的後半部。
![截圖 2023-12-28 下午9.28.54](https://hackmd.io/_uploads/r1fNulow6.png =30%x)





## 參考資料
[list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
[研讀 Linux 核心的 lib/list_sort.c 原始程式碼](https://hackmd.io/@RinHizakura/HkEuhNwGO#list_sort)
[研讀 Linux 核心原始程式碼 list_sort.c](https://hackmd.io/eZmZf4XxQgWzS56UpHjhzw?view)
[C++关键字之likely和unlikely](https://zhuanlan.zhihu.com/p/357434227)
