2023q1 Homework1 (lab0)

contributed by < dodo920306 >

開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           165
Model name:                      Intel(R) Core(TM) i5-10300H CPU @ 2.50GHz
Stepping:                        2
CPU MHz:                         2717.418
CPU max MHz:                     4500.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4999.90
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        8 MiB
NUMA node0 CPU(s):               0-7

開發過程

「開發過程」著重在你的思緒、描述過程中遇到的各式問題，以及你如何克服，並非讓你張貼大量程式碼的地方。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

q_new

~~queue head 以 malloc 來配置 struct list_node，INIT 後回傳。~~
使用 malloc 函數配置一個 struct list_node 結構作為 queue 頭節點，完成初始化後將其回傳。

改進漢語表達。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

q_free

結合上面的 q_new 實作，最後一行將對應 free queue head。
其他 node 呼叫 list.h 中的 q_release_element 釋出。

錯誤紀錄: 一開始將 element_t*->list 也 free。
但這其實挺蠢，list 不是指標。
release_element 內將 element_t 本身 free 時，list 將同時被釋出。
錯誤紀錄: 未呼叫 free 將 queue head 釋放，查看 q_new 實作後發現。

q_insert_head/tail

與 q_new 不同的是，此時 create 的 node 需要 entry element_t 以協帶資料。
因此，在確認 head 的 validity 後，以 malloc 來配置 element_t。
而 element_t 內帶有的 value 也需要配置 strlen(parameter string) + 1 長度的記憶體。
最後以 strncpy 將 value 寫入，便可將 node add list head/tail。

錯誤紀錄: 與 q_free 錯誤雷同，malloc element_t 同時即會配置其下 list，不需為其另進行配置。
錯誤紀錄: 呼叫 strcpy 是不安全的，需以 strncpy 或 memcpy 取代
FIXME: make test 顯示此兩函式未為 constant time 實作，有待改良。

q_remove_head/tail

在確認 head 的 validity 後，呼叫 list_entry 來取得 element_t。
以 strncpy 將 element_t 內帶有的 value 寫入 parameter string。
最後，呼叫 list_del 將 node "remove"。

錯誤紀錄: remove 不同於 delete，只需要將目標 "unlink" 於 queue，此函式不需呼叫任何 free。
錯誤紀錄: sp 參數不需要被 malloc 配置記憶體即可寫入。
錯誤紀錄: sp[bufsize - 1] = '\0'; 需加入此函式中，否則 qtest 收到的 remove value 結束點會不正確。
FIXME: make test 顯示此兩函示未為 constant time 實作，有待改良。

q_delete_mid

實作方式如下:

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *rabbit = head->next, *turtle = head->next;
    while (rabbit != head && rabbit->next != head) {
        rabbit = rabbit->next->next;
        turtle = turtle->next;
    }
    element_t *mid = list_entry(turtle, element_t, list);
    // report(1, "%s\n", mid->value);
    list_del(turtle);
    q_release_element(mid);

    return true;
}

藉由 Tortoise and Hare Algorithm 來判斷，當 rabbit 回到 head ( node 數量(不含 head )為偶數)，或 head->prev (node 數量(不含 head )為奇數)時，turtle 所在即為 mid node，將其刪除( delete )即可。

q_delete_dup

實作方式如下:

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    struct list_head *node, *safe;
    element_t *el;
    list_for_each_safe (node, safe, head) {
        if (safe == head)
            break;
        if (!strcmp(list_entry(node, element_t, list)->value,
                    list_entry(safe, element_t, list)->value)) {
            int len = strlen(list_entry(node, element_t, list)->value) + 1;
            char *dup = (char *) malloc(len);
            strncpy(dup, list_entry(node, element_t, list)->value, len);
            while (safe != head &&
                   !strcmp(dup, list_entry(safe, element_t, list)->value)) {
                el = list_entry(node, element_t, list);
                list_del(node);
                q_release_element(el);
                node = safe;
                safe = safe->next;
            }
            el = list_entry(node, element_t, list);
            list_del(node);
            q_release_element(el);
            free(dup);
        }
    }
    return true;
}

如果 node 與 safe 所協帶之 element_t 之 value 相等，將此相等值以 dup 存起，藉由 while loop 將 safe 一路迭代至 queue head 或值不再與 dup 相等之節點，同時， node 所在將被釋放，並持續跟在 safe 的前一節點。
因此，只要 node 與 safe 值相等，它們必定為所有帶有該值之節點的前兩個。而當跳出迴圈時，node 必依然為該相等值(即 dup )，為了將所有帶有此值之節點釋放，node 所在亦需被釋放；而後，因為 list_for_each_safe 的 AFTERTHOUGHT 會將 node 與 safe 再遞進一次，最後 node 與 safe 的位置必為帶有刪除值的最後節點的後兩個。
屆時，如果 node 與 safe 所帶有的值又相等，將再次進入以上步驟。
如果是因為 safe == head 而跳出迴圈，則在再一次遞進後 node 會與 head 相等，list_for_each_safe 將自行跳出。
如果最後一節點為一非重複值， safe 會與 head 相等，因為一開始的 if 判斷而跳出迴圈。

q_swap

x, y, z, and z->next 原依序是四個 queue 中比鄰非 head 節點，將 y->next 連至 x，x->next 連至 z->next (∵z 和 z->next 還會再交換)，將 x->y->z->(z->next) 換成 y->x->(z->next)->z，最後 x, y, and z 再遞進至原 z 開始的三節點(即 x' = z, y' = z->next，因 z 和 z->next 非 head，因此 x 和 y 不需檢查為 head)。
若 z 或 z->next 為 head，z 不需進行任何動作，x 與 y 交換後，x 連至 z 即可。

q_reverse

與 swap 不同的是，採取的是"遍歷 –- 逐一走訪所有節點，將其 next 與 prev 對調"的方式。

注意資訊科技詞彙翻譯

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

此處放上實作以與接下來的 reverseK 進行比較:

void q_reverse(struct list_head *head)
{
    struct list_head *tmp;
    for (struct list_head *node = head->next, *safe; node != head;
         node = safe) {
        safe = node->next;
        tmp = node->prev;
        node->prev = node->next;
        node->next = tmp;
    }
    tmp = head->prev;
    head->prev = head->next;
    head->next = tmp;
}

q_reverseK

實作方式如下:

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    struct list_head *tmp, *node = head->next, *safe = node->next, *last = head;
    int len = q_size(head);
    for (int j = 0; j < (len / k); j++) {
        for (int i = 0; i < k; i++) {
            safe = node->next;
            tmp = node->prev;
            node->prev = node->next;
            node->next = tmp;
            if (i < k - 1)
                node = safe;
        }
        tmp = last->next;
        last->next = node;
        node->prev = last;
        tmp->next = safe;
        safe->prev = tmp;
        last = tmp;
        node = safe;
        // element_t *el;
        // list_for_each_entry(el, head, list) {
        //     report(1, "%s", el->value);
        // }
        // report(1, "---");
    }
}

第二層 for-loop 內容幾乎與 q_reverse 相同，但為了讓上一 group 有辦法接上，以 last 保持紀錄上一 group 最後節點，並在每次迴圈結束時進行串接。
最後一次迴圈(即 i = k - 1)不 assign safe to node，使 node 保持為此 group 最後 reverse 的節點(即 reverse 後該 group 首節點)，safe 為下一 group 未 reverse 前首節點。因此需將 last(上一 group reverse 後末節點)連至 node，原 last->next(reverse 前此 group 首節點)連至 safe。

q_sort

q_sort 採用三個函式實作 merge sort:

struct list_head *q_mergeTwo(struct list_head *q1, struct list_head *q2);
struct list_head *q_mergeSort(struct list_head *head);
void q_sort(struct list_head *head);

q_sort 將 queue 去環去頭化，並傳入 q_mergeSort 內，取得回傳值後再將最終 tail 取回，與 head 一同接回原 head。

錯誤紀錄: 雖然 q_mergeSort 的回傳 queue 以正向迭代(即 ->next 方向)是對的，但在反向迭代(->prev 方向)是亂的。
需要加上以下段落:

struct list_head *it = head, *cur = head->next;
while (cur != head) {
    if (!cur)
        return;
    cur->prev = it;
    cur = cur->next;
    it = it->next;
}
cur->prev = it;
cur = head->prev;
while (cur != head) {
    if (!cur)
        return;
    cur = cur->prev;
}

來重建 ->prev 關係。
修正後的 q_sort 為:

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *tail = head->prev;
    head->prev = NULL;
    tail->next = NULL;  // decyclize
    head->next = q_mergeSort(head->next);
    // retake the tail now
    struct list_head *node = head->next;
    while (node) {
        tail = node;
        node = node->next;
    }
    tail->next = head;
    head->prev = tail;

    struct list_head *it = head, *cur = head->next;
    while (cur != head) {
        if (!cur)
            return;
        cur->prev = it;
        cur = cur->next;
        it = it->next;
    }
    cur->prev = it;
    cur = head->prev;
    while (cur != head) {
        if (!cur)
            return;
        cur = cur->prev;
    }

    return;
}

q_mergeSort 藉由前面提過的 Tortoise and Hare Algorithm 來取 mid，將前後兩段 queue 各自傳入 q_mergeSort 形成遞迴，取得回傳值即排序好的兩段 queue 傳入 q_mergeTwo 進行 merge 後回傳。
因此，比較大小實在 q_mergeTwo 執行:

struct list_head *q_mergeTwo(struct list_head *q1, struct list_head *q2)
{
    struct list_head *prehead = NULL, **indirect = &prehead;
    while (q1 && q2) {
        element_t *e1 = list_entry(q1, element_t, list);
        element_t *e2 = list_entry(q2, element_t, list);
        if (strcmp(e1->value, e2->value) <= 0) {
            *indirect = q1;
            q1 = q1->next;
        } else {
            *indirect = q2;
            q2 = q2->next;
        }
        indirect = &(*indirect)->next;
    }
    *indirect = (struct list_head *) ((uintptr_t) q1 | (uintptr_t) q2);
    return prehead;
}

改良紀錄: 使用 indirect pointer 進行串接。
錯誤紀錄: 此處使用遞迴法在節點數 10⁶ 數量級時會崩潰，卻在改用 while-loop 後即不再發生。

q_descend

採用與 q_delete_dup 雷同作法，只是迴圈條件從兩字串相等改為 >=0，將 safe 迭代至與左節點值 (即 dup) 相比較大(<0)之節點，若 safe 不為 head，從 dup 所在節點(即 node)開始直到 safe 以前所有節點全刪除；若 safe == head，代表從 node 開始所有節點所帶值皆非嚴格遞減，不採取任何動作。

q_merge

遍歷 –- 逐一走訪所有 chain 的所有 node 依序併入 head->next，再呼叫 q_sort head->next 即可。

TODO: 由於所有 chain 皆 sorted，與其叫 q_sort sort 帶有所有 node 的單鏈，不如倆倆合併最後併回 head->next。

研讀 lib/list_sort.c

linux/list_sort.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_LIST_SORT_H
/* define content */
#endif

根據 SPDX ，SPDX-License-Identifier: GPL-2.0 全名為 GNU General Public License v2.0 only，且「…the GNU General Public License is intended to guarantee your freedom to share and change free software–to make sure the software is free for all its users. …」。
如果 _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);

attribute可以用以規範 Function Attribute, Variable Attribute, and Type Attribute.
__attribute__((nonnull(2,3)))表示第二與第三參數不得為 NULL。
因此 list_cmp_func_t 中後兩const struct list_head *不得為NULL，合理推斷為須比較之兩者。
list_sort() 內，head 與 cmp 不得為 NULL，合理推斷即用以比較的function pointer 與欲排序之 list_head 本身。

list_sort.c

list_sort

接下來來看 list_sort.c 內這個 list_sort() 的註解說明:

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

與推論相同。

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.

這裡講述了 list_cmp_func_t 的詳細規範，基本上與 strcmp 或其他比較函式規則雷同。a 為前參數，b 為後。
不太一樣的是裡面說...list_sort is a stable sort, so it is not necessary to distinguish the @a < @b and @a == @b cases.，這間接說明了 stable 的定義:

A sorting algorithm is said to be stable if two objects with equal keys appear 
in the same order in sorted output as they appear in the input data set.

此差異也由下一段補足說明:

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

(compatible (a.) 相容的)
舉例之前者即為傳統類 strcmp 函式，後者則簡單布林判斷大於與否， (trivially) 後者效率較高。

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 為 multi-word 的比較法，基本上就是由高位比較起。若不為 multi-word，應直接 return a > b; 即可。

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

此段表示此 mergesort 的切法應是 merge 部分與剩餘長度維持 2:1，因此當有 2 條 2^k 長度 lists，它們應在第三條「即將(following)」出現時合併。

Thus, it will avoid cache thrashing as long as 32^k elements can fit into the cache. Not quite as good as a fully-eager bottom-up mergesort, but it does use 0.2n fewer comparisons, so is faster in the common case that everything fits into L1.

此處提到一名詞 cache thrashing，thrashing 的 Wikipedia定義為:

In computer science, thrashing occurs when a computer's virtual memory resources are overused, leading to a constant state of paging and page faults,
inhibiting most application-level processing.

因此，此段闡述指明，只要

3 \times 2^{k}

個元素能存入 cache，就能有效避免 thrashing；且與以往將東西全部塞進 L1 cache 相比，此策略能有效減少 0.2*n 次比較。

The merging is controlled by "count", the number of elements in the
pending lists. This is beautifully simple code, but rather subtle.

(subtle (a.) 微妙的)

count 為等待序列內的元素個數，以此控制 merge 進行。

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 和 merge 運作方式，當 count 要增加時便 set 第 k bit 並 clear 前面的 bits。而當此增加發生時，除第一次增加至 2^k 時以外，將會 merge 2個大小為 2^k 的 lists，產生一大小為 2^(k + 1) 的 list。
先跳過幾段，直接看 states 會比較清楚:

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)

如果有 state 6的話，他應該會像是「 y10x: 2 pending of size 2^k; 2^k + x pending of sizes < 2^k 」，此 state 與 state 2重疊，因為此時，「至少為 x110x，至少3個 2^k 大小的 lists 存在」，因此可以將「 2 pending of size 2^k 」合併，所以 count 變回 x10x。
因此，第一次進入 state 2，不會進行合併，但往後如果第 k bit 又在經歷一次「 clear and set again 」的過程(即 state 4 ~ 6(即2))，那就代表有奇數個 2^k 大小的 lists 存在。
(簡單來說，將第 k bit 看作 number of size 2^k 除以2的餘數。)
接著看回 states 前說明:

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.

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.

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

意思與上述說明差不多，最後說明了只有當第 k - 1 bit set 且當count >= 2^(k+1)(表非第一次第 k bit set)，才會判定前面的 2^k 大小的 lists 為 pending (即 state 2~3 或 4~5)。

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

注意到: state5~2 的 merge 觸發條件還有一個: 所有 lower bits 都得 set，才會在 count 加一後成功進位。
註解結束。

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

list_sort開始，先進行一般的 check emtry/singular list 及將 list 去環化。

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

補充:

<linux/compiler.h>
# define likely(x)	__builtin_expect(!!(x), 1)

(!!(x) 可確保一定為 0/1)
來看看這個迴圈程式碼:

count = 0b00，
1. for-loop 直接被跳出，bits = 0；if 被跳過。
2. head->next->prev = NULL；
3. pending = head->next；
4. list = head->next->next；
5. head->next->next = NULL；
6. count = 0b01。

0 pending of size 2⁰; 0 pending of sizes < 2⁰

count = 0b01，
1. for-loop跳出時，bits = 0；tail = NULL；if 被跳過。
2. head->(2)next->prev = head->next；
3. pending = head->(2)next；
4. list = head->(3)next；
5. head->(2)next->next = NULL；
6. count = 0b10。

0 pending of size 2⁰; 0 pending of sizes < 2⁰

count = 0b10，
1. for-loop 直接被跳出，bits = 2；tail = head->(2)next；進入 if。
2. a = head->(2)next； b = head->next；
3. a = merge(priv, cmp, b, a)；
4. head->(2)next->prev = head->next->prev = NULL；
5. tail = head->(2)next；
6. head->(3)next->prev = head->(2)next；
7. pending = head->(3)next；
8. list = head->(4)next；
9. head->(3)next->next = NULL；
10. count = 0b11。

2 pending of size 2⁰; 0 pending of sizes < 2⁰
merge(第-1 bit 永遠視為1)

count = 0b11，
1. for-loop跳出時，bits = 0；tail = head->next；if 被跳過。
2. head->(4)next->prev = head->(3)next；
3. pending = head->(4)next；
4. list = head->(5)next；
5. head->(4)next->next = NULL；
6. count = 0b100。

1 pending of size 2⁰; 0 pending of sizes < 2⁰
0 pending of size 2¹; 0 pending of sizes < 2¹

count = 0b100，
1. for-loop直接跳出，bits = 4；tail = head->(4)next；進入if。
2. a = head->(4)next； b = head->(3)next；
3. a = merge(priv, cmp, b, a)；
4. head->(4)next->prev = head->(3)next->prev = head->(2)next；
5. tail = head->(4)next；
6. head->(5)next->prev = head->(4)next；
7. pending = head->(5)next；
8. list = head->(6)next；
9. head->(5)next->next = NULL；
10. count = 0b101。

2 pending of size 2⁰; 0 pending of sizes < 2⁰
merge(第-1 bit 永遠視為1)
2 pending of size 2¹; 0 pending of sizes < 2¹

count = 0b101，
1. for-loop跳出時，bits = 2；tail = head->(4)next；進入if。
2. a = head->(4)next； b = head->(2)next； (注意 head->(4)next->prev 此時已不為 head->(3)next->prev。)
3. a = merge(priv, cmp, b, a)；
4. head->(4)next->prev = head->(2)next->prev = NULL；(非 head->next。)
5. tail = head->(4)next；
6. head->(6)next->prev = head->(5)next；
7. pending = head->(6)next；
8. list = head->(7)next；
9. head->(6)next->next = NULL；
10. count = 0b110。

1 pending of size 2⁰; 0 pending of sizes < 2⁰
2 pending of size 2¹; 2⁰ pending of sizes < 2¹
merge

count = 0b110，
1. for-loop直接跳出，bits = 6；tail = head->(6)next；進入if。
2. a = head->(6)next； b = head->(5)next；
3. a = merge(priv, cmp, b, a)；
4. head->(6)next->prev = head->(5)next->prev = head->(4)next；
5. tail = head->(6)next；
6. head->(7)next->prev = head->(6)next；
7. pending = head->(7)next；
8. list = head->(8)next；
9. head->(7)next->next = NULL；
10. count = 0b111。

2 pending of size 2⁰; 0 pending of sizes < 2⁰
merge
1 pending of size 2¹; 0 pending of sizes < 2¹

count = 0b111，
1. for-loop跳出時，bits = 0；tail = head->(2)next；if跳過。
2. head->(8)next->prev = head->(7)next；
3. pending = head->(8)next；
4. list = head->(9)next；
5. head->(8)next->next = NULL；
6. count = 0b1000。

1 pending of size 2⁰; 0 pending of sizes < 2⁰
1 pending of size 2¹; 2⁰ pending of sizes < 2¹

count = 0b1000，
1. for-loop直接跳出，bits = 8；tail = head->(8)next；進入if。
2. a = head->(8)next； b = head->(7)next；
3. a = merge(priv, cmp, b, a)；
4. head->(8)next->prev = head->(7)next->prev = head->(6)next；
5. tail = head->(8)next；
6. head->(9)next->prev = head->(8)next；
7. pending = head->(9)next；
8. list = head->(10)next；
9. head->(9)next->next = NULL；
10. count = 0b1001。

2 pending of size 2⁰; 0 pending of sizes < 2⁰
merge(第-1 bit 永遠視為1)
2 pending of size 2¹; 0 pending of sizes < 2¹

count = 0b1001，
1. for-loop跳出時，bits = 4；tail = head->(8)next；進入if。
2. a = head->(8)next； b = head->(6)next；
3. a = merge(priv, cmp, b, a)；
4. head->(8)next->prev = head->(6)next->prev = head->(4)next；
5. tail = head->(8)next；
6. head->(10)next->prev = head->(9)next；
7. pending = head->(10)next；
8. list = head->(11)next；
9. head->(10)next->next = NULL；
10. count = 0b1010。

1 pending of size 2⁰; 0 pending of sizes < 2⁰
2 pending of size 2¹; 2⁰ pending of sizes < 2¹
merge

count = 0b1010，
1. for-loop直接跳出，bits = 10；tail = head->(10)next；進入if。
2. a = head->(10)next； b = head->(9)next；
3. a = merge(priv, cmp, b, a)；
4. head->(10)next->prev = head->(9)next->prev = head->(8)next；
5. tail = head->(10)next；
6. head->(11)next->prev = head->(10)next；
7. pending = head->(11)next；
8. list = head->(12)next；
9. head->(11)next->next = NULL；
10. count = 0b1011。

2 pending of size 2⁰; 0 pending of sizes < 2⁰
merge
1 pending of size 2¹; 0 pending of sizes < 2¹
2 pending of size 2²; 2¹ pending of sizes < 2²
merge嗎? No, 注意要「所有 lower bits 皆1」才會 merge。

count = 0b1011，
1. for-loop跳出時，bits = 2；tail = head->(8)next；進入if。
2. a = head->(8)next； b = head->(4)next；
3. a = merge(priv, cmp, b, a)；
4. head->(8)next->prev = head->(4)next->prev = NULL；
5. tail = head->(8)next；
6. head->(12)next->prev = head->(11)next；
7. pending = head->(12)next；
8. list = head->(13)next；
9. head->(12)next->next = NULL；
10. count = 0b1100。

1 pending of size 2⁰; 0 pending of sizes < 2⁰
1 pending of size 2¹; 2⁰ pending of sizes < 2¹
2 pending of size 2²; 2¹ + 2⁰ pending of sizes < 2²
merge

裡面的 for-loop 以白話解釋就是: 「當 count 的第 k bit 為1，代表2^k大小的 list 有1個，此時 tail 往回跳以跳過這一個list；若為0，且count縮到這位時尚不為0，代表2^k大小的 list 有2個，此時 merge，且tail剛好也會在兩個 lists 的後者。」
就在這時，list == NULL，head->(13)next 不存在，因此跳脫 while-loop。

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

此時 pending 裡面還有 2 個長度為 2⁰ 的 lists (head->(11)next and head->(12)next)，1 個長度為 2¹ 的 list (head->(10)next)，和 1 個長度為 2³ 的 list (head->(8)next)。
來看看 for-loop 程式碼:

merge head->(11)next and head->(12)next
merge head->(10)next and head->(12)next

pending = head->(8)next；list = head->(12)next；
進入 merge_final，list_sort結束。

merge_final

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;
			}
		}
	}

首先將 a b 做比較，依序將節點接回 head。
如果 b 先接完，則令 b = a；使得剩下未接完的 list 一定為 b。

	/* 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;
}

unlikely(!++count) 除非溢位(255)不然一定是 true，這將會造成週期性地呼叫 cmp，且其實沒必要(cmp(priv, b, b)並沒有意義)。
但是，這樣的呼叫可以允許使用者在 cmp 內實作呼叫 cond_resched()，將核心主動釋出，避免行程拖累系統。
最後將 iterator 接回 head，使 head 變回 circular。

注意作業書寫規範：中英文間用一個空白字元區隔。以一致的風格排版程式碼，善用 clang-format

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

merge

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;
}

類似於 merge_final，只是更簡單。將 a b 兩 lists 節點依序比較後重排。
prev的關係並不被維持。