---
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).”：

至於為何要保持 2:1 的比例，如果合併的狀況為 1024:4，合併效率會很差（甚至 1024:1 會比較好，這裡原文是寫 1204，應該是筆誤了？詳情請見[文章](https://www.mail-archive.com/[e-mail]/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)。
## 程式碼解析
程式碼的部分，首先整理一下各段落的動作：

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，但是卻可以合併。理解後整理成動畫就清楚多了：


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/[e-mail]/msg1957556.html)的註解有提到 count 的排列組合，文字說明太難懂了，這裡我直接用圖去演示。
#### 初始化
首先做初始化：

struct list_head *list = head->next, *pending = NULL;
size_t count = 0;
head->prev->next = NULL;

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：

list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;

#### count = 1
同樣執行三個動作，預先說明 count = 1 不會做合併，所以同樣 `**tail` 指向哪裡（動作 1）其實不用在意。
`for (bits = count; bits & 1; bits >>= 1)` 經過 for 迴圈後，bits = 0，故動作 2 `if (likely(bits))` 為 false，不執行合併。
直接跳到動作 3，加入節點。
#### 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 的規則。

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 指向的地方，因為不重要。
#### count = 3
與 count 為 1 的狀況相同， `for (bits = count; bits & 1; bits >>= 1)` 經過 for 迴圈後，雖然重定向了 `**tail`，但是 bits = 0，故動作 2 `if (likely(bits))` 為 false，不執行合併，所以 `**tail` 指向哪裡就不重要。
直接跳到動作 3，加入節點。

#### count = 4
與 count 為 2 的狀況相同，node 5 在這個 iteration 結束後會被加入到 pending 底下，所以比例仍可以保持 2:1。

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

#### 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;`。

2. node3->node4 與 node2->node1 執行合併。並確保合併後的頭節點 的 prev 指標（藍色），指向上一個合併的頭節點（NULL）。並將 `*tail` （前一個 link list 的頭節點）指向合併後的頭節點（node3），確保整個鏈結串列不會亂掉。

4. 執行動作 3，將 node6 納入到準備排序中（黃），next 指向 null，綠色表示這輪執行合併的鏈結串列。
這時 `*list` 指向 NULL 跳出 do-while 迴圈。結束動作 1~3。
### 合併剩餘鏈結串列
將 `*pending`, `*list` 指回前一個 link list 後。進入 for 迴圈。

for (;;) {
    struct list_head *next = pending->prev;

    if (!next)
        break;
    list = merge(priv, cmp, pending, list);
    pending = next;
}

這時要合併的對象變為 `*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`）。
當 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)的後半部。

## 參考資料
[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)