---
title: Linux 核心風格 Linked List 應用案例
tags: C 語言筆記
---
## Linux 核心風格 Linked List 應用案例
### Quick sort
* [ sysprog21/linux-list 專案中的 quick-sort.c](https://github.com/sysprog21/linux-list/blob/master/examples/quick-sort.c)
```c=
static void list_qsort(struct list_head *head)
{
// less 存放比 pivot 小的 node
// greater 存放比 pivot 大的 node
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
// 如果 list 為空或者只有一點就直接 return
if (list_empty(head) || list_is_singular(head))
return;
// 把 less、greater 的 next、prev 指向自己(circular)
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
// 令第一個點為 pivot，並把該 pivot 從 list 中移除
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
// 利用 macro 來走訪整個 list，分類出 less 和 greater
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_tail(&item->list, &list_greater);
}
// 對分類出來的 less 和 greater 遞迴做 quick sort，得到排序好的 less 和 greater
list_qsort(&list_less);
list_qsort(&list_greater);
// 最後就是合併 less + pivot + greater
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
* 用上述的做法實作在 singly linked list
* node1(head) -> node2 -> node3 -> ...
```c=
node_t *quicksort(node_t *head)
{
if (!head || !head->next) return head;
node_t *pivot = head;
int pivot_val = pivot->val;
node_t **cur = &(pivot->next);
node_t *less_head = NULL;
node_t **less_cur = &less_head;
node_t *greater_head = NULL;
node_t **greater_cur = &greater_head;
while (*cur) {
if ((*cur)->val <= pivot_val) {
*less_cur = *cur;
*cur = (*cur)->next;
less_cur = &(*less_cur)->next;
*less_cur = NULL;
}
else {
*greater_cur = *cur;
*cur = (*cur)->next;
greater_cur = &(*greater_cur)->next;
*greater_cur = NULL;
}
}
less_head = quicksort(less_head);
greater_head = quicksort(greater_head);
node_t *ret = less_head ? less_head : pivot;
if (less_head) {
node_t *tmp;
for (tmp = less_head; tmp->next;) tmp = tmp->next;
tmp->next = pivot;
}
pivot->next = greater_head;
return ret;
}
```
### WRITE_ONCE 探討
* ```list_add``` 的實作中
```c=
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``` 加上處理 race condition
* ```WRITE_ONCE``` 的定義:
```c=
#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; \
})
```
* 借用 union 的 ```type-punning```，簡單來說就是可以用 ```char __c[1]``` 來代表 ```val``` 的位址，當作 ```val``` 的指標來用
* ```__write_once_size``` 的定義
```c=
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();
}
}
```
* 使用 ``` __may_alias__ ``` 來告知編譯器此型別允許 [aliasing](http://clhjoe.blogspot.com/2012/06/gcc-strict-aliasing.html) 的發生，避免激進的最佳化導致非預期的程式行為
* 簡單來說就是依照 ```size``` 來做 assign
* 然後有加上 ```volatile``` 告訴編譯器這個值可能會有變動，不要做優化
* 最後的 ```default``` 就是其他大小的處理，```barrier()``` 意思就是告訴編譯器不能把 ```barrier()``` 前的 load/store 移動到 ```barrier()``` 後，反之同理
### Linux 核心的 list_sort 實作
* linux 的 ```list_sort``` 是採用了 merge sort
* ```list_sort``` 有效利用了 ```doubly linked list``` 中的 ```prev``` 與 ```next``` 指標
* 但只是單純的 merge 會產生 unbalanced 的問題，如 1028 個節點時，merge sort 做到結束時會產生 1024 個已排序的 ```linked list``` 與 4 個未排序的 ```linked list```，此時最差的情況就是四個都在 1024 個 list 的最後才找到
* 所以 ```list_sort``` 提出一種 worst-case optimal 的方法來避免這種不平衡的 merge
* 大概的做法就是用一個 ```count``` 來負責甚麼時候要做 merge
* 如果要產生 2^k+1^ 的 linked list 的話，便需要==兩個長度為 2^k^==
的 linked list，與長度為 ==2^k−1^,...,2^1^== 的 linked list 各一個，此時 merge 完後的 linked list 長度各為 ==2^k+1^, 2^k−1^,..., 2^1^==
* 如果這時已經到 linked list 的結尾的話，只需要將最後一個節點從 2^1^ merge 到 2^k+1^ 即完成 merge sort
* 可以發現中間 merge 的數量比例最多只會為 2:1（長度為 2^1^ 與 1 及 2^k+1^ 與 2^k^ 做 merge 的時候)
| count | Merge | while-loop 開始時的 pending list | merge 後的 pending list |
|:-----:|:-----:|:--------------------------------:|:-----------------------:|
| 0 = (0)~2~ | No | NULL | x |
| 1 = (1)~2~ | No | 1 | x |
| 2 = (10)~2~ | Yes | 1-1 | 2 |
| 3 = (11)~2~ | No | 1-2 | x |
| 4 = (100)~2~ | Yes | 1-1-2 | 2-2 |
| 5 = (101)~2~ | Yes | 1-2-2 | 1-4 |
| 6 = (110)~2~ | Yes | 1-1-4 | 2-4 |
| 7 = (111)~2~ | No | 1-2-4 | x |
| 8 = (1000)~2~ | Yes | 1-1-2-4 | 2-2-4 |
| 9 = (1001)~2~ | Yes | 1-2-2-4 | 1-4-4 |
| 10 = (1010)~2~ | Yes | 1-1-4-4 | 2-4-4 |
| 11 = (1011)~2~ | Yes | 1-2-4-4 | 1-2-8 |
| 12 = (1100)~2~ | Yes | 1-1-2-8 | 2-2-8 |
| 13 = (1101)~2~ | Yes | 1-2-2-8 | 1-4-8 |
| 14 = (1110)~2~ | Yes | 1-1-4-8 | 2-4-8 |
| 15 = (1111)~2~ | No | 1-2-4-8 | x |
| 16 = (10000)~2~ | Yes | 1-1-2-4-8 | 2-2-4-8 |
* 實作
* ```priv``` 是一個 pointer，可以用來傳輸 ```cmp``` 需要的參數
* ```head``` 要被排序的 list
* ```cmp``` 是比較自定義大小的 function pointer
* ```__attribute__((nonnull))``` 讓 compiler 可以對指定位置的 pointer (在此例中是第 2、3 個參數，```head``` 跟 ```cmp```) 是 NULL 時發出警告
```c=
__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;
// 破壞掉 linked list 的 circular 結構，最後的節點(head->prev) 的 next 指向 NULL
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_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);
```
* merge 的實作，就正常地把 ```a```、```b``` merge 起來
```c=
__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;
}
```
* 最後的 ```list_sort``` 程式碼，就是在做把剩下的 list 全都 merge 起來
```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_func)cmp, pending, list);
pending = next;
}
/* The final merge, rebuilding prev links，回復至 circular linked list 的狀態 */
merge_final(priv, (cmp_func)cmp, head, pending, list);
}
```
Sign in with Wallet
Connect another wallet