# Intrusive Linked List in Linux Kernel
**本文適合讀者：熟悉基本 Linked List 原理、熟悉 C 語法與指標概念。**
這一切源自於研究所考試時，OS 科出了一題：請解釋 instrusive linked list 相比於 traditional linked list 的好處，考試時是我第一次聽到這東西，答案也就隨意亂掰，可想而知那一題大概 15 分我八成是 1 分都沒拿到 XD。
兩個半月後，OS 課出了關於 CPU Scheduling 的作業，因為作業環境是採用 Unix-like 的 xv6，作業實作中就碰巧需要使用到 instrusive linked list API。剛開始看到的時候我還認不出這就是 Intrusive Linked List，認真研究一波後才發現原來這又是一次我跟 Intrusive Linked List 命運的相遇哈哈哈，所以決定來徹底搞懂它，順便寫成一篇文件。
---
## Intrusive Linked List 起手式：它長什麼樣子?
[linux/list.h in GitHub](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 實作了 Intrsuive Linked List 的大部分內容，但生啃 kernel code 對菜鳥如我來說實在是吃不消，所以以下我會循序漸進地拆解各個部分講解，再組合起來一次理解整個觀念。
先來看看你我都熟悉的 **Traditional Linked List** 常見的 Implementation:
```cpp=
/* C code: Traditional Linked List Example */
// 這是某個你自己需要用到的 Structure
typedef struct student {
int id;
char *name;
} Student;
// 然後才會有一個 Node Structure，讓每個 Node 代表一個 Student
typedef struct student_node {
Student *stu;
struct student_node *prev;
struct student_node *next;
} StudentNode;
// 當你想宣告一個 student node，你就會
Student stu = { .id=1, .name="MyName" };
StudentNode *student = { .stu=&stu, .prev=NULL, .next=NULL };
// 因此你就可以用 student->prev->stu 之類的來找到該 student node 前後的 student。
```
- 示意圖如下：每個 Node 包著一個 object pointer pointing to 你真正需要的 object。
(Source: https://www.data-structures-in-practice.com/intrusive-linked-lists/)
**Intrusive Linked List** 就完全不一樣了，以下我從 xv6/list.h 拼貼出一段 Intrusive Linked List 的例子：
```cpp=
/* C code: Intrusive Linked List Example */
// 先定義一個 struct list_head，這個 list_head 將會被用來埋在實際的 object struct 中
struct list_head {
struct list_head *next, *prev;
};
// 這是主要的 object struct，這裡以 thread 為例
struct thread {
void (*fp)(void *arg); // thread function
void *arg; // function arguments
...
struct list_head thread_list; // Intrusive Linked List
...
};
```
如此一來，每個 `struct thread` 之間就會有一條 pointer，而所有 `struct thread` 則會形成一條 linked list。
- 示意圖如下：每個 object 自帶一個 `struct list_head`，而該 `list_head` 有個 pointer pointing to 下一個 object 的 `list_head`。
(Source: https://www.data-structures-in-practice.com/intrusive-linked-lists/)
那你可能會想：欸這樣的話，假設現在我有一個 linked list of `struct thread`，而 `struct list_head head` 是指向這條 linked list 的頭的指標，**那我要怎麼拿到這條 linked list 的第一支 thread（也就是 head 指向的 thread）呢？**
`head->next` 似乎行不通，因為 `struct list_head` 的 member 只有 `prev` 跟 `next`，並沒有你想要的 `thread` 資料。這時候就要讀讀下面關於 `container_of`（或 `list_entry`）的講解啦！
---
## `container_of`/`list_entry` 說明
延續上面的問題，要拿到 `head` 的下一個 `thread`，正確作法是：
```cpp
struct thread *th = list_entry(head->next, typeof(*th), thread_list);
```
其中，`list_entry(...)` 是一個 macro，相關定義如下：
```cpp
#define list_entry(ptr, type, member) container_of(ptr, type, member)
```
由此可知 `list_entry` 只是 `container_of` 的 alias。`container_of` 定義如下：
```cpp
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) ); \
})
```
先不要被這串妖魔鬼怪嚇到，我們逐一來分解它。
- 首先是最外面的 **`({...})`**，這是 [statement expression](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) 語法，最後一行 evaluate 後的值會回傳並賦值給 `th`。
- **`typeof`** 是 GNU C 的 extension 語法，如果是在 standard C 下的話需要改為 `__typeof__`。`typeof(a)` 會替換成 `a` 的型別，通常用在宣告變數時，如：假設 `a` 是一個 `int` ，則 `typeof(a) b = 0;` 基本上等價於 `int b = 0;`。
- 注意觀察 **`((type *)0)->member`**，這應該是整段 #define 最難理解的地方。這句話的意思是我先把 `0` 型別轉換成指向 `type` 的指標，再從這個指標把 `member` 這個 member 提取出來。這整句話並沒有違法，因為我們沒有 dereference 它，也沒有 access 它，我們只是想知道這個東東的型別是什麼（外面包的一層 `typeof()`）。
到目前為止你如果用心的 trace 一下 code，可以發現第一句的 `typeof( ((type *)0)->member )`，其實就等於你的 Intrusive Linked List 的型別 `struct list_head`。之所以那麼拐彎抹角，其實只是在檢查型別有沒有正確而已。因此第一句執行完，我們相當於宣告了一個型別為 `struct list_head` 的 `*__mptr`，而且它的值跟 `ptr` 一樣。
接下來，只要把 `__mptr` 減掉適當的 offset，就可以獲得 `ptr` 所在的那個 `thread` 並賦值給 `th`，也就是我們的所求 `head` 的下一個 `thread`。什麼意思呢？請參考示意圖：
(Source: https://www.data-structures-in-practice.com/intrusive-linked-lists/)
將整個大長方形視為一個 object，這個 object 的 memory 從 `0x10` 開始，而從 `0x18` 開始紀錄的則是 `struct list_head` 的部分，對應到上面的 `__mptr`。因此，這之間的差距 `offset = 8` ，只要把 `__mptr` 減掉 8 就可以拿到這個 object 的起始位址（i.e. 指標）。注意我們在相減之前還有先把 `__mptr` 轉成 `char*`，這樣 `__mptr - 8` 才會是減掉 8 bytes（一個 char 剛好 1 byte）。
原本的 `container_of` macro 中還有另一個 macro `offsetof` 就是拿來計算這個 offset 是多少的，這個 macro 被定義在 `stddef.h` 中，基本上只要知道它的用處是什麼即可，這邊就不再深究下去，有興趣的人可以到 [wiki](https://en.wikipedia.org/wiki/Offsetof) 跟這篇 [stackoverflow](https://stackoverflow.com/questions/18554721/how-to-understand-size-t-type-0-member) 瞧瞧。
---
讀到這邊，理論上應該可以對整個 intrusive linked list 還有操作的語法有一定的掌握度了，而事實上 [linux/list.h ](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 裡還有許多依照此語法衍伸的各種實用 macro，如在 linked list 後方加入 object 的 `list_add`、用於 traverse 整條 linked list 的 `list_for_each` 等等，在理解這篇文說明的基本語法後，應該就可以更容易地看懂這些 Intrusive Linked List 操作 API 了吧！
## Reference
- https://www.data-structures-in-practice.com/intrusive-linked-lists/
- https://github.com/torvalds/linux/blob/master/include/linux/list.h#L167
- https://hackmd.io/@RinHizakura/HkEuhNwGO#Linux-Linked-List
Sign in with Wallet
Connect another wallet