Linux Linked List

Material

2021q1 第 1 週測驗題
 GitHub

Introduction

linux/list.h 是 Linux 作業系統中相當實用的 doubly linked list 封裝，只要在自定義的結構中加入 struct list_head，就可以搭配 Linux 中一系列的 linked list 操作(詳見The Linux Kernel API - List Management Functions) 來建立自定義結構的 linked list。在撰寫 kernel module 時會有機會跟其打交道。除了會使用到相關的 API 之外，其中的實作細節也很值得我們細細品味，因此，何嘗不是個好注意呢來看看程式碼呢?

Start From Simple

我們可以先從 linux-list，由成大的黃敬群(jserv) 教授所建立的專案來一探究竟。這是一個和 Linux linked list 很相似的實作，但做了適當的簡化，並只留下一部分函數。

Code Explanation

`container_of()`

#if defined(__GNUC__)
#define __LIST_HAVE_TYPEOF 1
#endif

#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#else
#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif

如果 GNUC extension 為開啟狀態(#if defined(__GNUC__))，
__LIST_HAVE_TYPEOF 會被設為 1
__extension__: 根據 3.4 Options Controlling C Dialect，當語法被要求和 ANSI C 相容時(如 gcc 中加入 -ansi 參數)，像是 typeof 等 gcc extension 將不能被使用。而在 6.48 Alternate Keywords 則提到可以用替換關鍵字的方法實作沒有 extension 時的替代方案。但意思就是這種設計會存在用到 extension 和沒用到的兩種實作，編譯器會對於使用到 extension 的部份扔出警告，可以透過 __extension__ 避免警告的產生。
使用 extension 的實作版本:
- ({ ... }) 是 statement expression 的語法
- 透過 ((type *) 0)->member 取得目標 member 的 instance，typeof 會取得其型別。(注意到 pointer 0 沒有被 dereference 且 instance 沒被 access，所以合法)，於是可以得到正確型別的 ptr 指標，存入 __pmember
  - 此步驟是為了做 type checking，確保輸入的 ptr 是 type 中的 member 型別之指標
- 將 __pmember 減去該成員在 struct 中的偏移就可以得到 struct 的開頭位址
  - offsetof 定義在 stddef.h 中
- 計算 offset 時要轉成 char *，以確保 address 的計算符合預期(可參考 The (char *) casting in container_of() macro in linux kernel 的說明)
不使用 extension 的實作版本:
- 直接省略 type checking

`LIST_HEAD()` / `INIT_LIST_HEAD()`

#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

初始化 struct list_head，先將 next 和 prev 都指向自己
head 的 next 所指代表 linked list 結構的開頭而 prev 則指向結構的結尾

`list_add` / `list_add_tail`

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}

將指定的 node 插入 linked list head 的開頭或者結尾

`list_del`

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif
}

將 node 從其所屬的 linked list 結構中移除
需注意 node 本體甚至是包含 node 的結構所分配的記憶體皆未被釋放，僅僅是將 node 從其原本的 linked list 連接移除
LIST_POISONING 使得被刪除的 node 對於 next 或者 prev 的存取會引發 build time 的 invalid memory access(如果系統禁止 predefined memory access)

`list_del_init`

static inline void list_del_init(struct list_head *node)
{
    list_del(node);
    INIT_LIST_HEAD(node);
}

基於 list_del，但移除的 node 會額外呼叫 INIT_LIST_HEAD 把 prev 和 next 指向自己

`list_empty`

static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

檢查 head 的 next 是否指向自己，確認 list 是否為 empty 狀態

`list_singular`

static inline int list_is_singular(const struct list_head *head)
{
    return (!list_empty(head) && head->prev == head->next);
}

如果 head 非 empty 狀態且 prev 和 next 是同一個節點，表示 linked list 只有一個節點

`list_splice` / `list_splice_tail`

static inline void list_splice(struct list_head *list, struct list_head *head)
{
    struct list_head *head_first = head->next;
    struct list_head *list_first = list->next;
    struct list_head *list_last = list->prev;

    if (list_empty(list))
        return;

    head->next = list_first;
    list_first->prev = head;

    list_last->next = head_first;
    head_first->prev = list_last;
}

static inline void list_splice_tail(struct list_head *list,
                                    struct list_head *head)
{
    struct list_head *head_last = head->prev;
    struct list_head *list_first = list->next;
    struct list_head *list_last = list->prev;

    if (list_empty(list))
        return;

    head->prev = list_last;
    list_last->next = head;

    list_first->prev = head_last;
    head_last->next = list_first;
}

將 list 的所有 node 都插入到 head 的開始 / 結束位置中
注意 list 本身仍維持原貌

`list_spice_init` / `list_splice_tail_init`

static inline void list_splice_init(struct list_head *list,
                                    struct list_head *head)
{
    list_splice(list, head);
    INIT_LIST_HEAD(list);
}

static inline void list_splice_tail_init(struct list_head *list,
                                         struct list_head *head)
{
    list_splice_tail(list, head);
    INIT_LIST_HEAD(list);
}

和 list_splice / list_splice_tail 類似，但移除的 list 會額外呼叫 INIT_LIST_HEAD 把 prev 和 next 指向自己

`list_cut_position`

static inline void list_cut_position(struct list_head *head_to,
                                     struct list_head *head_from,
                                     struct list_head *node)
{
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    head_from->next = node->next;
    head_from->next->prev = head_from;

    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

將從 head_from 的第一個節點到 node 間的一系列節點都移動到 head_to 上
head_to 必須是 empty 狀態(next 和 prev 都指向自己)，否則可能發生 memory leak

`list_move` / `list_move_tail`

static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

static inline void list_move_tail(struct list_head *node,
                                  struct list_head *head)
{
    list_del(node);
    list_add_tail(node, head);
}

將 node 從原本的 linked list 移動到另一個 linked list head 的開頭或尾端

`list_entry`

#define list_entry(node, type, member) container_of(node, type, member)

container_of 等價的 wrapper

`list_first_entry` / `list_last_entry`

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

#define list_last_entry(head, type, member) \
    list_entry((head)->prev, type, member)

取得 linked list 的開頭或者結尾的 entry

`list_for_each`

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

linear 遍歷整個 linked list
node 和 head 不能在迴圈中被更改，否則行為不可預期

`list_for_each_entry`

#ifdef __LIST_HAVE_TYPEOF
#define list_for_each_entry(entry, head, member)                       \
    for (entry = list_entry((head)->next, __typeof__(*entry), member); \
         &entry->member != (head);                                     \
         entry = list_entry(entry->member.next, __typeof__(*entry), member))
#endif

遍歷包含 struct list_head 的另外一個結構之 entry
node 和 head 不能在迴圈中被更改，否則行為不可預期
因為 typeof 之限制，只能在 GNUC 下使用

`list_for_each_safe` / `list_for_each_entry_safe`

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)
         
#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

透過額外的 safe 紀錄每個 iteration 所操作的節點(entry)的下一個節點(entry)，因此刪除目前的節點(entry)是可被允許的，其他操作則同為不可預期行為

Example

Quicksort

我們可以從一些範例來看實際的使用。例如在專案中的 quick-sort.c 程式碼。

static void list_qsort(struct list_head *head)
{
    struct list_head list_less, list_greater;
    struct listitem *pivot;
    struct listitem *item = NULL, *is = NULL;

    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

先確認 head 所承載的 linked list 有兩個以上 entry，否則就返回，不需要被排序
先以 INIT_LIST_HEAD 初始化另外兩個 list 結構，它們分別是用來插入 entry 中比 pivot 小或者其他的節點

    pivot = list_first_entry(head, struct listitem, list);
    list_del(&pivot->list);

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot->i) < 0)
            list_move_tail(&item->list, &list_less);
        else
            list_move(&item->list, &list_greater);
    }

透過 list_first_entry 取得第一個 entry 選為 pivot
list_del 將該 pivot entry 從 linked list 中移除
遍歷整個 linked list，cmpint 回傳兩個指標中的值相減的數值，因此小於零表 item->i 的值比 pivot 的值小，加入 list_less，反之則同理

    list_qsort(&list_less);
    list_qsort(&list_greater);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
}

遞迴呼叫將 list_less 和 list_greater 排序
在 list_for_each_entry_safe 中，list_move_tail 和 list_move 會將所有原本在 head 中的節點移出，因此首先 list_add 加入 pivot，再把已經排好的 list_less 放在 pivot 前 list_greater 放在 pivot 後，完成排序

Quicksort Without Recursive Call

上面的程式碼是由 jserv 老師所實作，有了對其的理解後，我們也可以自己來實際使用一下相關的 API。這裡我用 2021q1 第 1 週測驗題的作業要求作為範例，參考 Optimized QuickSort — C Implementation (Non-Recursive)，嘗試一下基於 Linux like 的 linked list 實作類似的非遞迴 quick sort。

static void list_qsort_no_recursive(struct list_head *head)
{
    struct listitem *begin[MAX_LEN], *end[MAX_LEN], *L, *R;
    struct listitem pivot;
    int i = 0;

    begin[0] = list_first_entry(head, struct listitem, list);
    end[0] = list_last_entry(head, struct listitem, list);

begin 和 end 表示在 linked list 中的排序目標的開頭和結尾，因此最初是整個 linked list 的頭至尾

    while (i >= 0) {
        L = begin[i];
        R = end[i];

begin 和 end 的效果類似 stack，會填入每一輪要處理的節點開頭至結尾，因此先取出該輪的頭尾至 L 和 R

        if (L != R && &begin[i]->list != head) {
            // pivot is the actual address of L
            pivot = *begin[i];
            if (i == MAX_LEN - 1) {
                assert(-1);
                return;
            }

接著，以最開頭的節點作為 pivot
i == MAX_LEN - 1 的目的是額外檢查這輪如果填入 begin 和 end 是否會超出原本給定的陣列大小，因為我們所給予的空間是有限的

            while (L != R) {
                while (R->i >= pivot.i && L != R)
                    R = list_entry(R->list.prev, struct listitem, list);
                if (L != R) {
                    L->i = R->i;
                    L = list_entry(L->list.next, struct listitem, list);
                }

                while (L->i <= pivot.i && L != R)
                    L = list_entry(L->list.next, struct listitem, list);
                if (L != R) {
                    R->i = L->i;
                    R = list_entry(R->list.prev, struct listitem, list);
                }
            }

否則的話，從結尾的點(R)一直往 prev 前進，找到比 pivot 值更小的節點的話就將其值移到開頭的 L 去
同理，從開頭的點(L)一直往 next 前進，找到比 pivot 值更大的節點的話，就將其值移到結尾的 R 去
L != R 則負責判斷當 L 往 next 而 R 往 prev 移動碰在一起時，當 L == R 時，不再做上述的操作，離開迴圈

            L->i = pivot.i;
            begin[i + 1] = list_entry(L->list.next, struct listitem, list);
            end[i + 1] = end[i];
            end[i++] = L;

此時 L 所在地方是 pivot 的值應在的正確位置，因此將 pivot 的值填入 L
此時需要被處理的排序是 pivot 往後到結尾的一段，兩個點分別是 L 的 next，和這輪的 end[i]
另一段則是 pivot 以前從原本的 begin[i] 到 L 一段

        } else
            i--;
    }
}

如果 L == R 或者 &begin[i]->list == head，表示此段 linked list 已經不需要再做處理，i-- 類似於 pop stack 的概念

Some issue:

原本表示此實作在 array 下效能有可能較好，那麼在 doubly linked list 條件下，這個非遞迴的實作會有比較好的效能嗎
上面的實作中，用交換 list entry 中的內容的方式來實現，但考慮到整個 entry 的結構如果變得巨大，有沒有可能改成調成 link 方式來交換會比較有效率，要如何改寫?

Compare to Linux

比較 linux-list 與 linux/list.h 的實作，會發現最大的差異在於 WRITE_ONCE macro 的使用。

我們可以比較 list_add 來探討差異的細節

linux-list

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

linux/list.h

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
    if (!__list_add_valid(new, prev, next))
        return;

    next->prev = new;
    new->next = next;
    new->prev = prev;
    WRITE_ONCE(prev->next, new);
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

乍看之下，如果把 WRITE_ONCE(prev->next, new) 替換成 prev->next = new，兩者其實不是也沒甚麼差異嗎?

WRITE_ONCE 定義在 linux/tools/include/linux/compiler.h 路徑下，我們可以從註解中對其作用進行理解:

Prevent the compiler from merging or refetching reads or writes. The compiler is also forbidden from reordering successive instances of READ_ONCE and WRITE_ONCE, but only when the compiler is aware of some particular ordering. One way to make the compiler aware of ordering is to put the two invocations of READ_ONCE or WRITE_ONCE in different C statements.

簡而言之，通過 WRITE_ONCE 和 READ_ONCE 的使用，可以避免編譯器合併、切割、甚至重排特定的記憶體讀寫操作。下面是 WRITE_ONCE 的定義:

#define WRITE_ONCE(x, val)				\
({							\
	union { typeof(x) __val; char __c[1]; } __u =	\
		{ .__val = (val) }; 			\
	__write_once_size(&(x), __u.__c, sizeof(x));	\
	__u.__val;					\
})

我們可以再次看到 statement expression 技巧的應用。此外，可以看到 WRITE_ONCE 把 val 被寫入 union 結構中，使其與一個 char _c[1] 共享空間。藉由以 union 為基礎的 type-punning 技巧，可避免違反 strict aliasing 規則，使得 __c 能作為這個 union 的指標來使用，從而允許編譯器最佳化。

需注意 type tunning 的方式有不同類型，而在 gcc 中，使用 union 進行 type punning 的方式被作為語言的擴展並合法(詳見 gcc: nonbugs)，該方式不會違反 gcc 的 strict aliasing 規則。但在其他編譯器中則可能因為違反規則導致 undefined behavior。

延伸閱讀:

What is the strict aliasing rule?

Unions and type-punning

關鍵的 __write_once_size 的任務則是把 __val 寫入至 x 中，但通過巧妙的設計避免了編譯器將其做錯誤的優化，細節請見下面的 __write_once_size 說明

typedef __u8  __attribute__((__may_alias__))  __u8_alias_t;
typedef __u16 __attribute__((__may_alias__)) __u16_alias_t;
typedef __u32 __attribute__((__may_alias__)) __u32_alias_t;
typedef __u64 __attribute__((__may_alias__)) __u64_alias_t;

在深入 __write_once_size 之前，先來看看這個型別定義。

首先需要了解何謂 aliasing: 其所指為同一個位置可被多個 symbol 存取時，這種情形會造成編譯器優化上的難處。根據 Options That Control Optimization， -fstrict-aliasing 參數會讓編譯器預設程式撰寫者不會將相似類型(例如 int 和 unsigned int) 以外的 pointer 指向同一個記憶體位置，以允許做更激進的優化，這個參數在 -O2、-O3、-Os 下會預設開啟。

但我們可以根據 Specifying Attributes of Types 中所提到，使用 __may_alias__ 告知編譯器此型別允許 aliasing 的發生，避免對此的過度優化導致非預期的程式行為，至於 Linux 這裡特別定義 *_alias_t 的目的可以參考註解:

Following functions are taken from kernel sources and break aliasing rules in their original form.

While kernel is compiled with -fno-strict-aliasing, perf uses -Wstrict-aliasing=3 which makes build fail under gcc 4.4. Using extra __may_alias__ type to allow aliasing in this case.

static __always_inline void __write_once_size(volatile void *p, void *res, int size)
{
	switch (size) {
	case 1: *(volatile  __u8_alias_t *) p = *(__u8_alias_t  *) res; break;
	case 2: *(volatile __u16_alias_t *) p = *(__u16_alias_t *) res; break;
	case 4: *(volatile __u32_alias_t *) p = *(__u32_alias_t *) res; break;
	case 8: *(volatile __u64_alias_t *) p = *(__u64_alias_t *) res; break;
	default:
		barrier();
		__builtin_memcpy((void *)p, (const void *)res, size);
		barrier();
	}
}

對於 1 / 2 / 4 / 8 bytes 的變數，可以直接搭配 volatile 的使用提示編譯器不要優化這個寫入操作。volatile 所考慮的情境在於: 變數的值即使從程式中乍看不會改變，在每一次存取時實際則有可能被更動(例如該變數可能指向某個 memory map I/O，會被硬體更動值，或者被 signal handler 和 main program 共用的 global variable)，因此可以避免寫入操作被錯誤優化。

對於其他長度的變數，則可以透過 memory barriers 搭配 memcpy 的方法來寫入。barrier() 如同其名稱是個屏障，告訴編譯器不能 barrier() 前的 load/store 移動到 barrier() 後，反之亦然。

值得一題的是，Linux 中採用了這種 "volatile access" 而非直接將 object 標註為 volitile 屬性，在 doc: volatile considered evil 中有提及後者可能隱藏的問題。

延伸閱讀: Nine ways to break your systems code using volatile

list_sort

在 linux/list_sort.c 中，可以看到 linux 特別針對系統層級的考量所設計的 linked list sort。在最頂端 GitHub 連結中也可以看到整合至使用者層級的實作。接下來，嘗試探討其中的設計原理和可能的考量。

/**
 * list_sort - sort a list
 * @priv: private data, opaque to list_sort(), passed to @cmp
 * @head: the list to sort
 * @cmp: the elements comparison function
 *

感謝詳細的註解，我們可以不必貿然的挑戰程式碼，先探討其中的實作內容。首先是需要的三個參數

priv 是一個 pointer，可以用來傳輸 cmp 需要的參數
head 要被排序的 list
cmp 是比較自定義大小的 function pointer

/*... 
 * The comparison funtion @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.
 *
 * This is compatible with two styles of @cmp function:
 * - The traditional style which returns <0 / =0 / >0, or
 * - Returning a boolean 0/1.
 * The latter offers a chance to save a few cycles in the comparison
 * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
 *
 * A good way to write a multi-word comparison is::
 *
 *	if (a->high != b->high)
 *		return a->high > b->high;
 *	if (a->middle != b->middle)
 *		return a->middle > b->middle;
 *	return a->low > b->low;

註解中說明了在比較 a b 時，如果 a 需至於 b 的之後，則 cmp 需回傳大於 0 的值。list_sort 是 stable sort，所以不必區分小於或等於 0 的分別。

最後則展示了一個簡單的 multi-word comparision。

/* 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.
 *
 * 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.

接著，註解中提到這裡的 merge sort 實作重點。方法會保持兩個要被 merge 的 list 至少是 2 : 1 的狀態(比較大的 list 至多是小的的兩倍)，這可以有效的降低比較的次數。list_sort 與一般的 fully-eager bottom-up mergesort 方法不同，後者只要出現兩個 2^k 大小的 list，就會立刻被合併。而前者的方法是在出現兩個

2^{k}

大小的 list 的時候，不立即合併，反之，一直等到下一個 2^k 的 list 被蒐集起來時，前者的這兩個 linked list 才會被合併起來。只要這 2 : 1 的 list 可以完全被放到 cache 裡，就可以避免 cache thrashing。

在 [RESEND PATCH v2 5/5] lib/list_sort: Optimize number of calls to comparison function
可以看到更完整的敘述。

/* The merging is controlled by "count", the number of elements in the
 * pending lists.  This is beautiully 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).

那麼前述的規則該怎麼維持呢? 方法中會透過一個 count 來紀錄 pending 的節點數量。當目前的 count + 1 後，會設置第 k 個 bit 為 1，k-1 至 0 bit 為 0 時(除了 count 為

2^{k} - 1

的情境)，我們就把兩個

2^{k}

長度的 list 做合併。細節在後面探討程式碼時會再嘗試說明得更清楚。

後續註解有點掌握不到意思(~~菜英文~~)，所以下面直接從程式碼的部份做理解並解釋。













__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head,
		int (*cmp)(void *priv, struct list_head *a,
			struct list_head *b))
{
    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;

首先破壞掉 linked list 的 circular 結構，最後的節點(head->prev) 的 next 指向 NULL。

__attribute__((nonnull)) 讓 compiler 可以對指定位置的 pointer 是 NULL 時發出警告



























    ...

    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_func)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);

這裡我們可以先來觀察 count 與 merge 的進行之規律。注意到這裡的格式中，左邊是在該 count 的 iter 開始時的狀態，右邊則是經可能的 merge 後把自己加入 pending list 後的狀態。

$2^{0}$ -> count = 1 =
$1_{2}$ ->
$2^{0}$ +
$2^{0}$ (no merge)
$2^{0}$ +
$2^{0}$ -> count = 2 =
$10_{2}$ ->
$2^{1}$ +
$2^{0}$ (將
$10_{2}$ 加 1 的話 set bit 0，merge to 2^1)
$2^{1}$ +
$2^{0}$ -> count = 3 =
$11_{2}$ ->
$2^{1}$ +
$2^{0}$ +
$2^{0}$ (no merge)
$2^{1}$ +
$2^{0}$ +
$2^{0}$ -> count = 4 =
$100_{2}$ -> 2 *
$2^{1}$ +
$2^{0}$ (將
$100_{2}$ 加 1 的話 set bit 0->merge to 2^1)
2 *
$2^{1}$ +
$2^{0}$ -> count = 5 =
$101_{2}$ ->
$2^{2}$ +
$2^{0}$ +
$2^{0}$ (將
$101_{2}$ 加 1 的話 set bit 1->merge to 2^2)
$2^{2}$ +
$2^{0}$ +
$2^{0}$ -> count = 6 =
$110_{2}$ ->
$2^{2}$ +
$2^{1}$ +
$2^{0}$ (將
$110_{2}$ 加 1 的話 set bit 0->merge to 2^1)

可以觀察到，count 的最小位元的 0 假設在位置 k，根據規則就要 merge 出

2^{k + 1}

的 list (除了 count 為

2^{k} - 1

)。而後面為 1 的 bit k - 1, k - 2 … 0 可以代表 pending 裡有

2^{k - 1}, 2^{k - 2} . . . . . . 2^{0}

大小的 Llist 各一個，且因為 *tail 一開始就指向

2^{0}

的那個 list，所以 *tail 往 prev 走 k 步就會找到

2^{k}

大小的 list A，而 A 的 prev 是另一個

2^{k}

大小的 list B，我們要把兩者 merge 在一起。

再回到程式碼，for 迴圈中透過 count 最低位元的連續 1 找到此輪要 merge 的兩個 list，且 bits 若不為 0 剛好會等同於我們提到要 merge 的 count。最後。每一輪的 list 會把自己的 next 設為 NULL 而 prev 指向 pending，並更新成原本的 next 所指向的下一個 node 繼續流程。

下面看一下 merge 具體的實作:

__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, cmp_func 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;
}

merge 接受參數的兩個 list_head a / b 後，tail 初始時指向一個 dummy pointer。然後 for 迴圈比較 a / b。如果 a 應該在 b 之前，則 *tail 改指向 a，並且 tail 被更新以指向 "指向 a 的下個節點的 pointer"(注意這裡沒多打一個指向XD)，這個步驟等同把 a 加到一個新的 linked list 中，然後下一次改成比 a 的 next 和 b，反之也是類似道理。直到 a 或 b 的 next 為 NULL 時，把另一個加入 *tail 則完成。

繼續來看 list_sort 的實作。














    /* 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_func)cmp, pending, list);
        pending = next;
    }
    /* The final merge, rebuilding prev links */
    merge_final(priv, (cmp_func)cmp, head, pending, list);
}

當所有的節點都被加入 pending 後，把所有的 pending 都 merge 在一起。刻意留下 pending 中的其一 pending 和其他的 pending merge 在一起的 list 去做 merge_final，後者的目的是因為 merge 只有做單向(next)的鏈結，需要把 prev 也接去正確的點上，並且回復至 circular linked list 的狀態。

Reference

WRITE_ONCE in linux kernel lists

Linux内核中的READ_ONCE和WRITE_ONCE宏

编译乱序

TODO

閱讀 A comparative study of linked list sorting algorithms 並將其落實於 linux-list 中

Linux Linked List

Material

Introduction

Start From Simple

Code Explanation

container_of()

LIST_HEAD() / INIT_LIST_HEAD()

list_add / list_add_tail

list_del

list_del_init

list_empty

list_singular

list_splice / list_splice_tail

list_spice_init / list_splice_tail_init

list_cut_position

list_move / list_move_tail

list_entry

list_first_entry / list_last_entry

list_for_each

list_for_each_entry

list_for_each_safe / list_for_each_entry_safe