---
tags: Linux Kernel 2022 spring, linux2023
---
# 研讀 Linux 核心原始程式碼的 list_sort.c
## 待辦
- [ ] 研讀 [lib/list_sort: optimize number of calls to comparison function](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09)
- [ ] 參考 [kdnvt的筆記](https://hackmd.io/@kdnvt/linux2022_lab0#%E7%A0%94%E8%AE%80-liblist_sortc) 進行 `list_sort` 分析
## 參考筆記
[RinHizakura](https://hackmd.io/@RinHizakura/HkEuhNwGO#list_sort)
[laneser](https://hackmd.io/@laneser/linux2022_lab0#q_sort)
[Risheng](https://hackmd.io/@Risheng/list_sort)
[freshLiver](https://hackmd.io/@freshLiver/2022q1-hw1#%E9%87%9D%E5%B0%8D%E4%BD%87%E5%88%97%E7%9A%84%E6%93%8D%E4%BD%9C)
首行
```c
// SPDX-License-Identifier: GPL-2.0
```
參考 [GNU 通用公共許可證](https://en.wikipedia.org/wiki/GNU_General_Public_License)
## #include
[Where exactly is the file linux/kernel.h?](https://unix.stackexchange.com/questions/434136/where-exactly-is-the-file-linux-kernel-h)
> The `linux/kernel.h` header which gets used for module builds is the header which is part of the kernel source. When modules are built in the kernel source tree, that’s the version which is used.
## \_\_attribute\_\_
```c
__attribute__((nonnull(2,3,4)))
```
**其中2、3、4代表第二、三、四個引數不能為空**
參考 [GNU C \_\_attribute\_\_ 機制簡介](https://huenlil.pixnet.net/blog/post/26078382)
>`__attribute__` 可以設置函數屬性（Function Attribute）、變量屬性（Variable Attribute）和類型屬性（Type Attribute）
其中**函數屬性(Function Attribute)中**講到
>函數屬性可以幫助開發者把一些特性添加到函數聲明中，從而可以使編譯器在錯誤檢查方面的功能更強大。__attribute__機制也很容易同非GNU應用程序做到兼容之功效。
參考 [9.40 __attribute__((nonnull)) function attribute](https://www.keil.com/support/man/docs/armcc/armcc_chr1359124976631.htm)
>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.
### Syntax
>`__attribute__((nonnull[(arg-index, ...)]))`
Where `[(arg-index, ...)]` denotes an optional argument index list.
If no argument index list is specified, all pointer arguments are marked as nonnull.
## 函式code，typedef解析
`list_sort.c` 中一共有三個函式，分別為 `merge` ，`merge_final` 以及 `list_sort`
### `merge`
:::info
* Returns a list organized in an intermediate format suited
* to chaining of merge() calls: null-terminated, no reserved or
* sentinel head node, "prev" links not maintained.
:::
```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;
}
```
首先設定2,3,4的引數不能是 `NULL`
在 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 中查找相關 `typedef`
參考 [[C語言] function pointer的應用[三]: 使用 typdef 來定義函數指標以增加程式的可讀性](https://medium.com/@racktar7743/c%E8%AA%9E%E8%A8%80-function-pointer%E7%9A%84%E6%87%89%E7%94%A8-%E4%B8%89-%E4%BD%BF%E7%94%A8-typdef-%E4%BE%86%E5%AE%9A%E7%BE%A9%E5%87%BD%E6%95%B8%E6%8C%87%E6%A8%99%E4%BB%A5%E5%A2%9E%E5%8A%A0%E7%A8%8B%E5%BC%8F%E7%9A%84%E5%8F%AF%E8%AE%80%E6%80%A7-7a26857e3e00)
在 `list_sort.h` 中查找 `list_cmp_func_t` 相關定義
```c
/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
#define _LINUX_LIST_SORT_H
#include <linux/types.h>
struct list_head;
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
const struct list_head *, const struct list_head *);
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif
```
發現 `cmp` 是一個函式指標，回傳 `int` 型態，有三個參數，分別為 `void*` 以及兩個 `const struct list_head*` ，由 `__attribute__((nonnull(2,3)))` 定義第二個以及第三個參數不為`null`
根據程式註解
>The comparison function @cmp must return > 0 if @a should sort after
@b ("@a > @b" if you want an ascending sort), and <= 0 if @a should sort before @b *or* their original order should be preserved. It is always called with the element that came first in the input in @a, and list_sort is a stable sort, so it is not necessary to distinguish the @a < @b and @a == @b cases.
1. `cmp` return > 0 (升冪排列a排在b後面)
2. `cmp` return <= 0 (升冪排列a排在b前面) ==或== 原本的排序保留
3. `list_sort` 是一個stable sort, 不必區分小於或等於0的分別
### `merge_final`
:::info
Combine final list merge with restoration of standard doubly-linked list structure. This approach duplicates code from merge(), but runs faster than the tidier alternatives of either a separate final prev-link restoration pass, or maintaining the prev links throughout.
:::
:::info
此函式恢復雙向鍊結串列的鍊結結構，且由 `merge()` 而來，但是運算較在最終回複 `prev` 的鍊結或是持續維持 `prev` 的鍊結還要快
:::
```c
__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;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
```
在註解中提到如果是非常不平衡的 merge ，像是輸入已經排序好了，這個迴圈會經過非常多次的迭代儘管根本不需要，所以這裡提到 `cmp()` 可以週期性的調用 `cond_resched()`
參考[laneser](https://hackmd.io/@laneser/linux2022_lab0#q_sort)同學提供的連結[[Linux Kernel慢慢學]likely and unlikely macro](https://meetonfriday.com/posts/cecba4ef/)
>在Linux kernel 2.6之後提供了likely, unlikely 這兩個macro，他們被定義在/include/linux/compiler.h中
>```c
># define likely(x) __builtin_expect(!!(x), 1)
># define unlikely(x) __builtin_expect(!!(x), 0)
>```
其中 `__built_expect()` 是gcc的內建function，用來將branch的相關資訊提供給compiler，告訴compiler設計者期望的比較結果，以便對程式碼改變分支順序來進行優化，==也就是說我告訴它這個 `if` 發生的的機率是多少，它會幫我優化==
參考[Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
而 `!!(x)` 這樣的寫法是因為
- 透過兩次NOT op來確保值一定是0 或 1
- 因為if內邏輯敘述的值可以是0或是非0的整數的，所以如果不做 `!!(x)` 就無法確保值一定是0或1
- 使用 `likely` macro表示這段敘述(x)為 `true` 的機率比較大(比較常發生)，告訴compiler將 `x==true` 的對應執行程式碼接在判斷後面
- 使用 `unlikely` macro表示這段敘述(x)為 `true` 的機率比較小(不常發生)，告訴compiler將 `x==false` 的對應執行程式碼接在判斷後面
### `list_sort`
此段感謝[RinHizakura](https://hackmd.io/@RinHizakura/HkEuhNwGO#list_sort)的筆記
:::info
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.
:::
這邊提到要保持兩個被merge的list至少是2:1，這可以降低比較的次數。一般的fully-eager bottom-up mergesort只要出現兩個大小為 $2^{k}$ 大小的list就會進行排序並合併，而這裡的方法是在==出現兩個大小為$2^{k}$大小的list的時候，不立即合併，而是等到下一個$2^{k}$的list被蒐集起來時，前者的兩個linked list才會被合併。==
參考閱讀
[ [RESEND PATCH v2 5/5] lib/list_sort: Optimize number of calls to comparison function](https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1957556.html)
:::info
Thus, it will avoid cache thrashing as long as $3*2^{k}$ elements can fit into the cache. Not quite as good as a fully-eager bottom-up mergesort, but it does use $0.2*n$ fewer comparisons, so is faster in the common case that everything fits into L1.
:::
只要這2:1的list ($3*2^{k}$的list) 可以完全被放到cache裡，就可以避免 [cache thrashing](http://www.wowotech.net/memory_management/458.html)
:::info
The merging is controlled by "count", the number of elements in the pending lists. This is beautifully simple code, but rather subtle.
Each time we increment "count", we set one bit (bit k) and clear bits k-1 .. 0. Each time this happens (except the very first time for each bit, when count increments to $2^{k}$), we merge two lists of size $2^{k}$ into one list of size $2^{k+1}$.
:::
- merging 的過程由 count 紀錄 pending 的節點數量
- 每次 count 增加，設定第 k 個 bit 為 1 且將 k-1 ~ 0 的bit清空
- 每次發生時會 merge 2 個 $2^{k}$ 的 list 成為一個 $2^{k+1}$
:::info
This merge happens exactly when the count reaches an odd multiple of $2^{k}$, which is when we have $2^{k}$ elements pending in smaller lists, so it's safe to merge away two lists of size $2^{k}$.
:::
每次 count 達到 $2^{k}$ 的奇數倍會發生 merge
:::info
After this happens twice, we have created two lists of size $2^{k+1}$, which will be merged into a list of size $2^{k+2}$ before we create a third list of size $2^{k+1}$, so there are never more than two pending.
:::
在發生兩次 merge 之後 產生兩個 $2^{k+1}$ 的 list 且會 merge 成一個 $2^{k+2}$，這發生在產生第三個$2^{k+1}$ 的 list 之前，==所以永遠不會超過兩個 pending==
```
* The number of pending lists of size 2^k is determined by the
* state of bit k of "count" plus two extra pieces of information:
*
* - The state of bit k-1 (when k == 0, consider bit -1 always set), and
* - Whether the higher-order bits are zero or non-zero (i.e.
* is count >= 2^(k+1)).
*
* There are six states we distinguish. "x" represents some arbitrary
* bits, and "y" represents some arbitrary non-zero bits:
* 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k
* 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k
* 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
* (merge and loop back to state 2)
*
* We gain lists of size 2^k in the 2->3 and 4->5 transitions (because
* bit k-1 is set while the more significant bits are non-zero) and
* merge them away in the 5->2 transition. Note in particular that just
* before the 5->2 transition, all lower-order bits are 11 (state 3),
* so there is one list of each smaller size.
*
* When we reach the end of the input, we merge all the pending
* lists, from smallest to largest. If you work through cases 2 to
* 5 above, you can see that the number of elements we merge with a list
* of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to
* 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1).
```
**結構體**
```c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = 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);
```
**查找 `likely` 定義**
[compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h)
```c
// first
# ifndef likely
# define likely(x) (__branch_check__(x, 1, __builtin_constant_p(x)))
# endif
# ifndef unlikely
# define unlikely(x) (__branch_check__(x, 0, __builtin_constant_p(x)))
# endif
// second
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
由 `compiler.h` 中的第 15、16 行決定該要定義哪一種
```c
#if defined(CONFIG_TRACE_BRANCH_PROFILING) \
&& !defined(DISABLE_BRANCH_PROFILING) && !defined(__CHECKER__)
```
第二種定義可以參考本篇前面的章節，現在來分析第一種定義
兩個巨集函式 `__branch_check__()` 以及 `__builtin_const_p()`
在第 23 行提到定義
```c=
#define __branch_check__(x, expect, is_constant) ({ \
long ______r; \
static struct ftrace_likely_data \
__aligned(4) \
__section("_ftrace_annotated_branch") \
______f = { \
.data.func = __func__, \
.data.file = __FILE__, \
.data.line = __LINE__, \
}; \
______r = __builtin_expect(!!(x), expect); \
ftrace_likely_update(&______f, ______r, \
expect, is_constant); \
______r; \
})
```
在這之中又隱含兩個巨集，可以在 [compiler_attributes.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler_attributes.h) 找到定義
```c
#define __aligned(x) __attribute__((__aligned__(x)))
#define __section(section) __attribute__((__section__(section)))
```
接著參考 [C 之 attribute 用法](https://www.twblogs.net/a/5c5afff3bd9eee06ef36c370)
>大致有六個參數值可以被設定，即：aligned, packed, transparent_union, unused, deprecated 和 may_alias 。
在使用 `__attribute__` 參數時，你也可以在參數的前後都加上 `__` （兩個下劃線），例如，使用 `__aligned__` 而不是 `aligned` ，這樣，你就可以在相應的頭文件裏使用它而不用關心頭文件裏是否有重名的宏定義。
**該屬性設定一個指定大小的對齊格式（以==字節==爲單位）**
接著參考 [attribute 用法 section 部分](https://www.twblogs.net/a/5cfdf1fbbd9eee14644e7f97)
>要了解Linux Kernel代碼的分段信息，需要了解一下gcc的 `__attribute__` 的編繹屬性， `__attribute__` 主要用於改變所聲明或定義的函數或 數據的特性，它有很多子項，用於改變作用對象的特性。比如對函數，noline將禁止進行內聯擴展、noreturn表示沒有返回值、pure表明函數除 返回值外，不會通過其它（如全局變量、指針）對函數外部產生任何影響。但這裏我們比較感興趣的是對代碼段起作用子項section。
**Syntax**
```c
__attribute__((section("section_name")))
```
**其作用是將作用的函數或數據放入指定名爲 "section_name" 輸入段。**
```c
int var __attribute__((section(".xdata"))) = 0;
```
這樣定義的變量 `var` 將被放入名爲 `.xdata` 的輸入段，（注意： `__attribute__` 這種用法中的括號好像很嚴格，這裏的幾個括號好象一個也不能少。）
>輸入段和輸出段是相對於要生成最終的elf或binary時的Link過程說的，Link過程的輸入大都是由源代碼編繹生成的目標文件.o，那麼這些.o 文件中包含的段相對link過程來說就是輸入段
`line 4` to `line 9`
**\_\_func\_\_**
[6.50 Function Names as Strings](https://gcc.gnu.org/onlinedocs/gcc/Function-Names.html)
```c
static const char __func__[] = "function-name";
```
**\_\_FILE\_\_**
>原始檔名
>
**\_\_LINE\_\_**
>所在行數
[3.7.1 Standard Predefined Macros](https://gcc.gnu.org/onlinedocs/cpp/Standard-Predefined-Macros.html)
`line 11`
`__builtin_expect` 可以查找本篇前段說明
`line 12`
```c
ftrace_likely_update(&______f, ______r, \
expect, is_constant);
```
定義於 [linux/kernel/trace/trace_branch.c](https://github.com/torvalds/linux/blob/master/kernel/trace/trace_branch.c) `Line 205`
### 程式碼分析
==**本節程式碼行數提醒 `line xx` 依照[原始碼](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)行數定義**==
**首先研讀註解**
```
/*
* Data structure invariants:
* - All lists are singly linked and null-terminated; prev
* pointers are not maintained.
* - pending is a prev-linked "list of lists" of sorted
* sublists awaiting further merging.
* - Each of the sorted sublists is power-of-two in size.
* - Sublists are sorted by size and age, smallest & newest at front.
* - There are zero to two sublists of each size.
* - A pair of pending sublists are merged as soon as the number
* of following pending elements equals their size (i.e.
* each time count reaches an odd multiple of that size).
* That ensures each later final merge will be at worst 2:1.
* - Each round consists of:
* - Merging the two sublists selected by the highest bit
* which flips when count is incremented, and
* - Adding an element from the input as a size-1 sublist.
*/
```
- 所有 lists 是單向鍊結且最後指向 `NULL` 且 `prev` pointer 沒有維持
- `pending` 這個 list 是 `prev-linked` 的排序過後等待 merging 的子 lists `list of lists`
- 每個排序好的子 lists 是 size of $2^{k}$
- 子 lists 是根據時間，大小，新舊進行排序
- 每個大小都會有 0~2 個子 lists
- 當 count 到 size 的奇數倍的時候會 merge，確保最差也會有 2:1
- 每一輪包含
- 融合兩個 sublists (由高位選擇)
- 從 input 新增 element (size - 1 的子 list)
---
斷開環狀鍊結
```c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
掃過整個 lists
- **`for` 迴圈用以找出最 `tail` 中最左不為 0 的 bits**
- **`if` 迴圈在 `bits` MSB 為 0 ( MSB 不為 0 時必進 `for` 迴圈) 時且在其他位置有非 0 值時進入，代表有合併要進行**
- **這邊特別注意在執行完 `do-while` 迴圈之後其實最後的兩個 element 還是 unsorted 的**
- **剩餘得的部份會在下一段進行 sorted**
```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);
```
最後尾端的 element 進行 merge (過程中會 sort)
```c
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
最後把兩個 sublists 合併起來
```c
/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);
```
最後一行
```c
EXPORT_SYMBOL(list_sort);
```
可以參考[談 EXPORT_SYMBOL 使用](https://www.twblogs.net/a/5b810c712b71772165aabfcc)
>EXPORT_SYMBOL標籤內定義的函數或者符號對全部內核代碼公開，不用修改內核代碼就可以在您的內核模塊中直接調用，即使用EXPORT_SYMBOL可以將一個函數以符號的方式導出給其他模塊使用。
以及 [Linux驅動開發——EXPORT_SYMBOL的使用](http://www.unixlinux.online/unixlinux/linuxjc/linuxjs/201703/91672.html)
## 圖解 `list_sort.c`
假設輸入的 linked list 為(已將環狀結構斷開)
```graphviz
digraph ll{
rankdir=LR //橫的
node [shape=record] //方框
h [label = "<ref>head |{<refp>prev |<refn>next}|<data> value"]; // 分割方塊
1 [label = "<ref>node 2 |{<refp>prev|<refn>next}|<data> 5"];
2 [label = "<ref>node 3 |{<refp>prev|<refn>next}|<data> 3"];
3 [label = "<ref>node 4 |{<refp>prev|<refn>next}|<data> 1"];
4 [label = "<ref>node 5 |{<refp>prev|<refn>next}|<data> 2"];
NULLEND[shape = plaintext, label = "NULL"]
edge[weight=2]
h:refn -> 1:ref [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> 2:ref [arrowhead=vee];
1:refp -> h:ref [arrowhead=vee];
2:refn -> 3:ref [arrowhead=vee];
2:refp -> 1:ref [arrowhead=vee];
3:refn -> 4:ref [arrowhead=vee];
3:refp -> 2:ref [arrowhead=vee];
//4:refn -> h:ref [arrowhead=vee];
4:refp -> 3:ref [arrowhead=vee];
4:refn -> NULLEND
edge[weight=0];
}
```
根據程式註解 ==prev pointers are not maintained.==
為了讓圖解結構清細，接下來除了重要的 `prev` 指標之外不再繪製 `prev` 的指向，且 `next` 指向下一個節點在圖上會指向 `prev` ，實則指向該 node 的位置
上述輸入排序完應為
```graphviz
digraph ll{
rankdir=LR //橫的
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULLEND[shape = plaintext, label = "NULL"]
edge[weight=2]
h:refn -> 3:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
3:refn -> 4:refp [arrowhead=vee];
4:refn -> 2:refp [arrowhead=vee];
2:refn -> 1:refp [arrowhead=vee];
1:refn -> NULLEND
edge[weight=1];
}
```
---
**開始分析**
在 `line 187` 中定義
```c
struct list_head *list = head->next, *pending = NULL;
```
在 `line 216` 中定義，可知在 `do-while` 迴圈中，每進入一次新的 `do`，`tail` 會追著 `pending`
```c
struct list_head **tail = &pending;
```
可以得到
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULLEND[shape = plaintext, label = "NULL"]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> 2:refp [arrowhead=vee];
2:refn -> 3:refp [arrowhead=vee];
3:refn -> 4:refp [arrowhead=vee];
4:refn -> NULLEND
/*----------*/
node [shape=none]
list -> 1:ref
pending->NULL;
tail -> pending;
edge[weight=0];
}
```
---
進入 `do-while` 迴圈
`bits` 會追著 `count` 定義
第一次迭代時
`count = 0`
不會進入 `for` 迴圈 也不會進入 `if(likely(bits))` 迴圈
接著進行 ==**`list` 和 `pending` 的推移**==
```c
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
==**到下一 `do` 的 `for` 迴圈之前**==
可以得到
==**count = 1**==
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULLEND[shape = plaintext, label = "NULL"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 3:refp [arrowhead=vee];
3:refn -> 4:refp [arrowhead=vee];
4:refn -> NULLEND
/*----------*/
pending->1:ref;
list -> 2:ref
tail -> pending;
edge[weight=0];
}
```
==**接著下來的每一次迭代作圖基本上都以 `do` 以後 `for` 以前 作為作圖的分界，若有不一樣的操作則詳細繪製**==
---
==**count = 1**==
進入 `for` 迴圈，執行
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
```
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULLEND[shape = plaintext, label = "NULL"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 3:refp [arrowhead=vee];
3:refn -> 4:refp [arrowhead=vee];
4:refn -> NULLEND
/*----------*/
pending->1:ref;
list -> 2:ref
tail -> NULL3;
edge[weight=0];
}
```
沒有進入 `if(likely(bits))` ，執行接下來的程式碼
到下一個 `do` 之後 `for` 之前，可得
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULLEND[shape = plaintext, label = "NULL"]
list[shape = plaintext, label = "list"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> NULL3 [arrowhead=vee];
2:refp -> 1 [arrowhead=vee];
3:refn -> 4:refp [arrowhead=vee];
4:refn -> NULLEND
/*----------*/
pending->2:ref;
list -> 3
tail -> pending;
edge[weight=0];
}
```
==**count=2**==
---
==**count=2**==
不會進入 `for` 迴圈，進入 `if(likely(bits))` 迴圈
由`line 232` 定義
```c
struct list_head *a = *tail, *b = a->prev;
```
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULLEND[shape = plaintext, label = "NULL"]
list[shape = plaintext, label = "list"]
tail[shape = plaintext, label = "tail(a)"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> NULL3 [arrowhead=vee];
2:refp -> 1 [arrowhead=vee];
3:refn -> 4:refp [arrowhead=vee];
4:refn -> NULLEND
/*----------*/
pending->2:ref;
list -> 3
tail -> pending [color=red];
b->1 [color=red];
edge[weight=0];
}
```
進入 `merge`
```c
a = merge(priv, cmp, b, a);
/* Install the merged result in place of the inputs */
a->prev = b->prev;
*tail = a;
```
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULLEND[shape = plaintext, label = "NULL"]
list[shape = plaintext, label = "list"]
tail[shape = plaintext, label = "tail(a)"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 1 [arrowhead=vee];
2:refp -> NULL3 [arrowhead=vee];
3:refn -> 4:refp [arrowhead=vee];
4:refn -> NULLEND
/*----------*/
pending->2:ref;
list -> 3
tail -> pending [color=red];
edge[weight=0];
}
```
進行 ==**`list` 和 `pending` 的推移**==
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULL4[shape = plaintext, label = "NULL"]
NULLEND[shape = plaintext, label = "NULL"]
list[shape = plaintext, label = "list"]
tail[shape = plaintext, label = "tail"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 1 [arrowhead=vee];
2:refp -> NULL3 [arrowhead=vee];
3:refn -> NULL4 [arrowhead=vee];
3:refp -> 2 [color=red]
4:refn -> NULLEND
/*----------*/
pending->3:ref;
list -> 4
tail -> pending ;
edge[weight=0];
}
```
==**count=3**==
---
==**count=3**==
進入 `for` 迴圈 (迭代兩圈)
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULL4[shape = plaintext, label = "NULL"]
NULLEND[shape = plaintext, label = "NULL"]
list[shape = plaintext, label = "list"]
tail[shape = plaintext, label = "tail"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 1 [arrowhead=vee];
2:refp -> NULL3 [arrowhead=vee];
3:refn -> NULL4 [arrowhead=vee];
3:refp -> 2
4:refn -> NULLEND
/*----------*/
pending->3:ref;
list -> 4
tail -> NULL3 [color=red];
edge[weight=0];
}
```
進行 ==**`list` 和 `pending` 的推移**==
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULL4[shape = plaintext, label = "NULL"]
NULL5[shape = plaintext, label = "NULL"]
NULLEND[shape = plaintext, label = "NULL"]
list[shape = plaintext, label = "list"]
tail[shape = plaintext, label = "tail"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 1 [arrowhead=vee];
2:refp -> NULL3 [arrowhead=vee];
3:refn -> NULL4 [arrowhead=vee];
3:refp -> 2
4:refn -> NULL5
4:refp -> 3
/*----------*/
pending->4:ref;
list -> NULLEND
tail -> NULL3;
edge[weight=0];
}
```
==**count=4**==，且 `list= NULL` 跳出 `do-while` 迴圈
---
此時發現原本的 linked list 變成由 `prev` 連接的 linked list 且 `node4` 以及 `node5` 還沒有進行排序
執行最後節點的排序
```c
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
```
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULL4[shape = plaintext, label = "NULL"]
NULL5[shape = plaintext, label = "NULL"]
list[shape = plaintext, label = "list"]
tail[shape = plaintext, label = "tail"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 1 [arrowhead=vee];
2:refp -> NULL3 [arrowhead=vee];
3:refn -> NULL4 [arrowhead=vee];
3:refp -> 2
4:refn -> NULL5
4:refp -> 3
/*----------*/
pending->3[color=red];
list -> 4[color=red]
tail -> NULL3;
edge[weight=0];
}
```
進入 `for(;;)` 迴圈
```c
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
```
```graphviz
digraph ll{
node [shape=record] //方框
h [label = "{<ref>head|<refp>prev }|{<data> value |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<refp>prev }|{<data> 5|<refn>next}"];
2 [label = "{<ref>node 3 |<refp>prev }|{<data> 3|<refn>next}"];
3 [label = "{<ref>node 4 |<refp>prev}|{<data> 1|<refn>next}"];
4 [label = "{<ref>node 5 |<refp>prev } |{<data> 2|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULL4[shape = plaintext, label = "NULL"]
NULL5[shape = plaintext, label = "NULL"]
list[shape = plaintext, label = "list"]
tail[shape = plaintext, label = "tail"]
next[shape = plaintext, label = "next"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 1 [arrowhead=vee];
2:refp -> NULL3 [arrowhead=vee];
3:refn -> NULL4 [arrowhead=vee];
3:refp -> 2 [color=blue]
4:refn -> NULL5
4:refp -> 3
/*----------*/
next-> 2 [color=red]
pending->3;
list -> 4
tail -> NULL3;
edge[weight=0];
}
```
由上圖，經過 `for(;;)` 變為下圖
由`line 247`
```c
list = merge(priv, cmp, pending, list);
```
將 `list` 移至 `pending` 的位置，且對 `node4` 及 `node5` 排序
由`line 248`
```c
pending = next;
```
將 `pending` 移至 `node3` 得位置
```graphviz
digraph ll{
node [shape=record] //方框
h [label = "{<ref>head|<refp>prev }|{<data> value |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<refp>prev }|{<data> 5|<refn>next}"];
2 [label = "{<ref>node 3 |<refp>prev }|{<data> 3|<refn>next}"];
3 [label = "{<ref>node 4 |<refp>prev}|{<data> 1|<refn>next}"];
4 [label = "{<ref>node 5 |<refp>prev } |{<data> 2|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
NULL4[shape = plaintext, label = "NULL"]
NULL5[shape = plaintext, label = "NULL"]
list[shape = plaintext, label = "list"]
tail[shape = plaintext, label = "tail"]
next[shape = plaintext, label = "next"]
node [shape=none]
edge[weight=2]
h:refn -> 1:refp [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 1 [arrowhead=vee];
2:refp -> NULL3 [arrowhead=vee];
3:refn -> 4 [color=red][arrowhead=vee];
3:refp -> 2
4:refn -> NULL5
/*----------*/
next-> 2
pending->2[color=blue];
list -> 3[color=red]
tail -> NULL3;
edge[weight=0];
}
```
且在執行下一次迭代時就會經過
```c
struct list_head *next = pending->prev;
```
進而 `break` 迴圈
---
此時可以發現有兩個 sublists
- 一個由 `list` 指向 `node4` 指向 `node5`
- 一個由 `pending` 指向 `node3` 指向 `node2`
最後執行
```c
merge_final(priv, cmp, head, pending, list);
```
得到
```graphviz
digraph ll{
rankdir=LR
node [shape=record] //方框
h [label = "{<ref>head|<data> value }|{<refp>prev |<refn>next}"]; // 分割方塊
1 [label = "{<ref>node 2 |<data> 5 }|{<refp>prev|<refn>next}"];
2 [label = "{<ref>node 3 |<data> 3 }|{<refp>prev|<refn>next}"];
3 [label = "{<ref>node 4 |<data> 1 }|{<refp>prev|<refn>next}"];
4 [label = "{<ref>node 5 |<data> 2 } |{<refp>prev|<refn>next}"];
NULL1[shape = plaintext, label = "NULL"]
NULL2[shape = plaintext, label = "NULL"]
NULL3[shape = plaintext, label = "NULL"]
node [shape=none]
edge[weight=2]
h:refn -> 3 [arrowhead=vee];
//h:refp -> 4:ref [arrowhead=vee];
1:refn -> NULL1 [arrowhead=vee];
1:refp -> NULL2
2:refn -> 1 [arrowhead=vee];
2:refp -> NULL3 [arrowhead=vee];
3:refn -> 4 [color=red][arrowhead=vee];
3:refp -> h:data
4:refn -> 2
4:refp -> 3:data
/*----------*/
edge[weight=0];
}
```
==**完成排序！**==
## list_sort 深入分析最佳化
拜讀 [kdnvt](https://hackmd.io/@kdnvt/linux2022_lab0#%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) 的筆記之後發現了自己不足的部份，並嘗試理解同學們提到的部份
### 研讀 [lib/list_sort: optimize number of calls to comparison function](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09)
文中提到目前的 merge sort 有 $n* log2(n) - K * n + O(1)$ 個比較，
Sign in with Wallet
Connect another wallet