contributed by < Risheng1128
>
首先 Linux kernel 的 merge sort 主要由三個函式 list_sort()
、 merge()
及 merge_final()
組成,以下開始分析每個函式所做的功能
在分析函式之前,先了解函式的 prototype ,每個函式的宣告都擁有函式屬性 __attribute__((nonnull()))
,參考 __attribute__((nonnull))
function attribute 可以得知 nonnull
是用來使特定函數的引數為 NULL
時,編譯器會發出警告
This function attribute specifies function parameters that are not supposed to be null pointers. This enables the compiler to generate a warning on encountering such a parameter.
以下為 list_sort()
的定義及引數
__attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
@priv: private data, opaque to list_sort(), passed to @cmp
@head: the list to sort
@cmp: the elements comparison function
這邊根據原始碼對 cmp
做一些分析
cmp
的資料型態 list_cmp_func_t
,根據 include/linux/list_sort.h
可以找到,可以得知 cmp
其實是一個函式指標,指向回傳型態為 int
,且引數有 void *
及 2 個 const struct list_head *
的函式
cmp
回傳大於 0 時,表示執行 ascending sortcmp
回傳小於等於 0 時,表示執行 descending sort 或是保留原本順序接著來到分析 merge sort 在 Linux kernel 的實際樣貌,這邊參考前人的精華及原始碼搭配分析
首先查看註解的部份,可以得知該 merge sort 的鏈節串列總是保持 2:1 ,即比較長的 linked list 至少要是短的 2 倍長。假設有兩個 2k 大小的 linked list , merge sort 不會選擇直接合併,而是會等到有第 3 個長度為 2k 的 linked list 才會開始合併,變成 2k+1 及 2k 兩個 linked list ,並符合前面所說的 2:1
如果前述所說的這 3 個 linked list ,都可以被放進 cache 裡,則可以避免 Cache thrashing 的問題,即不會發生 cache miss
由上述的註解可以歸納出以下幾點:
count
用來計算在 pending list 的 element
總數count
加 1
後,會將第 k
個位元設為 1
,而 k-1
到 0
位元,則會被清為 0
count
達到 2k 的奇數倍時發生,且 merge 發生兩次後會產生 2 個 2k+1 大小的 linked list本來想先從註解開始理解,但上方的註解實在是太難懂了..,因此決定從程式碼一起理解
首先可以看到 Linux kernel 在排序之前將 linked list 環狀的部份切開
接著開始尋找變數 count
位於最低位元的 clear bit 位置
再來出現了一個巨集函式 likely()
,可以在 /include/linux/compiler.h 找到定義
發現一共有兩種定義
分析整個標頭檔的邏輯後,可以發現要選擇第一種還是第二種的 likely()
是由 CONFIG_TRACE_BRANCH_PROFILING
、 DISABLE_BRANCH_PROFILING
及 __CHECKER__
作決定 (由以下原始碼得知)
首先分析第一種的定義,出現了幾個沒看過得巨集函式 __branch_check__()
、__builtin_constant_p()
,繼續往下尋找
可以在 /include/linux/compiler.h 找到 __branch_check__()
的定義
嗯…有點難懂,不過慢慢查後還是可以得知一些訊息,首先是 __aligned
及 __section
,可以在 include/linux/compiler_attributes.h
找到定義
再來是 __func__
、 __FILE__
及 __LINE__
都是 gcc 的預設巨集,從 __func__
可以參考 Function Names as Strings , __LINE++
及 __FILE__
可以參考 Standard Predefined Macros
__FILE__
This macro expands to the name of the current input file, in the form of a C string constant. This is the path by which the preprocessor opened the file, not the short name specified in ‘#include’ or as the input file name argument. For example, "/usr/local/include/myheader.h" is a possible expansion of this macro.
__LINE__
This macro expands to the current input line number, in the form of a decimal integer constant. While we call it a predefined macro, it’s a pretty strange macro, since its “definition” changes with each new line of source code.
接著是很重要的 __builtin_expect()
,這個巨集也是 gcc 的預設巨集,參考Other Built-in Functions Provided by GCC可以更清楚的知道 __builtin_expect()
的意義
__builtin_expect()
You may use __builtin_expect to provide the compiler with branch prediction information. In general, you should prefer to use actual profile feedback for this (-fprofile-arcs), as programmers are notoriously bad at predicting how their programs actually perform. However, there are applications in which this data is hard to collect.
最後是函式 ftrace_likely_update()
,可以在 kernel/trace/trace_branch.c
找到該函式的實作,至於程式碼的邏輯及目的目前還沒有很清楚 (先做標記)
接著換第二種情況,第二種就單純很多,只有呼叫巨集函式 __builtin_expect()
,跟第一種實作的方式一樣
從以上的分析可以得到 likely()
主要的功能
__builtin_expect(!!(x), 1)
會告訴編譯器 !!(x)
為 1
的機率很高,因此編譯器可以根據這樣的訊息對程式碼做優化,加速執行速度!!(x)
為 1
, 表示 x
為非 0
的數字bits
的最低位元的 clear bit 後, bits
仍不為 0
,則會進行 merge 的動作回到 list_sort()
原始碼,這邊則是依據前面提到的 likely()
決定是否要做 merge 的動作,而 merge 是利用 a
和 b
合併兩個 linked list 後面會有流程圖做更詳細的解釋
接著在每一次的迭代都會增加一個節點到 pending list 裡,原始碼如下所示
可以將上述的過程簡單的做個流程圖,每張圖表示 do while
一開始的時候
count = 0
node1
為 head
count = 1
node2
) 加到 pending list ,如下圖表示, node2
已經被加到 pending list進入下列原始碼,由於 count = 1
,因此會進入一次迴圈,使 tail
指到 node2
的 prev
,如下圖所示
count = 2
node3
已被加進 pending list接著由於一開始下列程式碼的影響,將原本指到 node2->prev
的 tail
改指回 pending
的位置,如下圖
一樣執行上述的迴圈,出迴圈後 bits
為 2
,這時接著執行 if (likely(bits))
,由於 bits
已經不為 0
,因此會執行 merge 的動作 (a
指向 node3
,且 b
指向 node2
),下圖為合併結束的樣子 (假設位置不變), node2
已經接回 node3
count = 3
count = 4
count = 3
的最後將 list
移到了 NULL
的位置,因此此時已經離開迴圈,下圖為離開迴圈前的最後狀態由上述的流程圖可以得知所有的節點已經被加到 pending list ,接著的步驟就是將所有的 pending list 合併在一起,原始碼如下
最後一個步驟也就是把已經斷掉的 prev
重新接回去
最後發現了一個巨集函式 EXPORT_SYMBOL()
,參考Linux驅動開發——EXPORT_SYMBOL的使用,可以得知 EXPORT_SYMBOL()
的目的及使用方法
為了更清楚的說明了整個 linked list 合併的狀態,做出以下的表格
state | merge | count | pending list 的狀態 (在迴圈一開始的地方) | pending list 的狀態 (在迴圈結束的地方) |
---|---|---|---|---|
0 | X | 0b0000(0) | NULL | [1] |
0 | X | 0b0001(1) | [1] | [1,1] |
1 | O | 0b0010(2) | [1,1] | [2,1] |
1 | X | 0b0011(3) | [2,1] | [2,1,1] |
2 | O | 0b0100(4) | [2,1,1] | [2,2,1] |
2 | O | 0b0101(5) | [2,2,1] | [4,1,1] |
3 | O | 0b0110(6) | [4,1,1] | [4,2,1] |
3 | X | 0b0111(7) | [4,2,1] | [4,2,1,1] |
4 | O | 0b1000(8) | [4,2,1,1] | [4,2,2,1] |
4 | O | 0b1001(9) | [4,2,2,1] | [4,4,1,1] |
5 | O | 0b1010(10) | [4,4,1,1] | [4,4,2,1] |
5 | O | 0b1011(11) | [4,4,2,1] | [8,2,1,1] |
2 | O. | 0b1100(12) | [8,2,1,1] | [8,2,2,1] |
2 | O | 0b1101(13) | [8,2,2,1] | [8,4,1,1] |
3 | O | 0b1110(14) | [8,4,1,1] | [8,4,2,1] |
3 | X | 0b1111(15) | [8,4,2,1] | [8,4,2,1,1] |
這邊先附上整個 merge()
的程式碼
merge()
merge()
的實作就比 list_sort()
單純很多,首先建立一個指向 struct list_head
的指標 head
,接著建立一個指標的指標 tail
,指向 head
接著進入無限迴圈,使用 cmp
來決定下一個節點要從 a
還是 b
取得
→ cmp
回傳 ≤ 時選擇 a
,回傳 > 時則選擇 b
當 linked list a
已經沒有節點時,直接接上 linked list b
,反之則接上 linked list a
這邊附上整個 merge_final()
的程式碼
merge_final()
將所有的 prev
接回前一個節點
list_sort.c
研讀 Linux 核心的 lib/list_sort.c 原始程式碼
Standard Predefined Macros
Function Names as Strings
Other Built-in Functions Provided by GCC