# F02: list
contributed by < `afcidk` >
* [F02: list](https://hackmd.io/s/S12jCWKHN)
## 自我檢查事項
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
macro 在編譯時期會被編譯器展開成實際的程式碼，這樣做的好處是可以加速程式的速度。
在進行 function call 的時候，因為我們除了需要把參數 push 到特定的 register 或是 stack 上以外，還需要儲存當前 register 的值到 stack 上。function call 少時，這個影響還看不出來，但是一但數量變大，就會導致程式運作比用 macro 實作時慢。
實際執行一段簡單的[程式碼](https://gist.github.com/afcidk/441abae865be13c599b8f749792908b6)，並用 gnuplot 顯示使用 function call 與 macro 的執行時間差異。
Linux 裡頭許多地方都會使用到 linked list 作為資料結構，因此各種 linked list 的基本操作也會被大量使用。如上段所述，這在 function call 和 macro 實作的效能差異會在量大時顯示出來，這也是為什麼 Linux 會採用 macro 來實作 linked list 的原因之一。
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
我認為使用 linked list 最大的好處是程式開發者不需要在編寫程式時就決定資料的長度。根據這個觀點，我找了下面三個例子
* Process Management
* inode
* Network File System (NFS)
#### linux/sched.h
說到 process management，最常提到的應該就是 `task_struct` 這個結構了。
他定義在 [sched.h](https://github.com/torvalds/linux/blob/master/include/linux/sched.h)，光是定義整個結構就需要 628 行！
因為整份程式碼太龐大，這邊我節錄在 `task_struct` 裡頭紀錄 parent/child 的部份解釋
```clike=753
/*
* Pointers to the (original) parent process, youngest child, younger sibling,
* older sibling, respectively. (p->father can be replaced with
* p->real_parent->pid)
*/
/* Real parent process: */
struct task_struct __rcu *real_parent;
/* Recipient of SIGCHLD, wait4() reports: */
struct task_struct __rcu *parent;
/*
* Children/sibling form the list of natural children:
*/
struct list_head children;
struct list_head sibling;
struct task_struct *group_leader;
```
在 `real_parent` 的前面有一個 `__rcu` 的巨集，全稱叫作 [Read-copy-update](https://en.wikipedia.org/wiki/Read-copy-update)，他可以允許動態分配位址的資料結構（e.g. linked-list）在讀取資料時不需要把整個結構用互斥鎖鎖住。
那麼 `real_parent` 和 `parent` 的差別在哪裡？
根據上方的註解，我們可以知道 `real_parent` 肯定是整個結構的父親，而 `parent` 則是 `SIGCHLD` 還有 `wait4()` 回傳結果的對象。
查看 `man 7 signal` 得到 `SIGCHLD Child stopped or terminated`
可以知道 `SIGCHLD` 是一個 child 暫停或是終止時會發出的訊號。
`wait4()` 是 BSD 風格的函式，和他相近的另一個規範在 POSIX 裡的函式是 `waitpid()`，他們的用途是卡住程式，並等待 child 的狀態改變。
寫了寫現在還是不太明白，目前只知道大概跟 `ptrace` 有關係。
#### inode
inode(index node) 是 Unix-like 系統裡面負責處理檔案系統的資料結構。
我們可以看到 [fs.h](https://github.com/torvalds/linux/blob/master/fs/fs.h) 裡頭的 `inode` 結構也有 `list_head` 的蹤影
```clike=668
struct list_head i_lru; /* inode LRU list */
struct list_head i_sb_list;
struct list_head i_wb_list; /* backing dev writeback list */
```
### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
typeof 允許我們傳入一個變數，代表的會是該變數的型態。
舉例來說：
```clike
int a;
typeof(a) b = 10; // equals to "int b = 10;"
char s[6] = "Hello";
char *ch;
typeof(ch) k = s; // equals to "char *k = s;"
```
`typeof` 大多用在定義巨集上，因為在巨集裏面我們沒辦法知道參數的型態，在需要宣告相同型態的變數時，`typeof` 會是一個很好的幫手。
這邊以 max 的巨集為例子
```clike
#define max(a,b) \
{(typeof(a) _a = a; \
typeof(b) _b = b; \
_a > _b ? _a : _b;)}
```
至於為什麼我們需要那麼麻煩將 max 的巨集寫成這樣的形式呢？難道不可以寫成 `#define max(a,b) (a>b?a:b)` 就好嗎？
這樣的寫法會導致 **Double evaluation** 的問題，顧名思義就是會有某些東西被執行過兩次。
試想如下情況
```clike
#define max(a,b) (a>b?a:b)
void doOneTime() {printf("called doOneTime!\n");}
int f1() {doOneTime(); return 0;}
int f2() {doOneTime(); return 1;}
int result = max(f1(), f2());
```
實際執行後，我們會發現我們竟然呼叫了**三次** `doOneTime` 函式，但是明明在 `max` 的地方我們只期待會呼叫兩次而已不是嗎？
這是因為在巨集展開後，原本的 `max(f1(), f2())` 會被改成這樣的形式
```
int result = (f1()>f2()?f1():f2());
```
為了避免這個問題，我們必須在巨集中先用變數把可能傳入的函式回傳值儲存下來，之後判斷就不要再使用一開始傳入的函式，而是是用後來宣告的回傳值變數。
### 解釋以下巨集的原理
```clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
我們一步一步拆解內容。首先看到的是 `__extension__`，他是一個修飾字，用來防止 gcc 編譯器產生警告。
什麼情況下編譯器會產生警告讓我們想要忽略呢？當我們在編譯時，編譯器可能會提醒我們，程式裏面有使用到非 ANSI C 標準的語句，我們寫的程式在現在的編譯器可能可以過，但是用其他的編譯器可能就不會過了。
在這邊的例子，出問題的地方應該是在開頭的 `({})`(braced-group within expression)，實際編譯過後我們可以看到這樣的警告訊息
```
warning: ISO C forbids braced-groups within expressions [-Wpedantic]
```
事實上這是 gcc 自己擴展的一個 extension，透過這種寫法可以讓我們的 macro 更**安全**。
如果不想要看見這個警告，就可以在最前面加上 `__extension__` 修飾字。
再來的話看到 `__typeof__(((type *) 0)->member) * __pmember` 這段
可以看到我們用 `((type*)0)->member` 的型態再宣告一個新的指標 `__pmember`。
`(type*)0` 代表的是一個被轉型成 `type` 型態的 struct，在這個地方我們不管他是不是一個合法的位址，所以可以直接寫 0 就好。再來我們讓他指向 `member`，因此 `__typeof__(((type*)0)->member)` 代表的便是 `member` 的資料型態。
再往下看到 `(type *) ((char *) __pmember - offsetof(type, member));` 這段比較好解釋，其實就只是把 member 的位址扣除 member 在整個 struct 裡面的偏移後，得到整個 struct 的開頭位址而已。
以圖像的方式會長這樣
### LIST_POISONING 這樣的設計有何意義？
跟 poison 相關的定義可以查看 [linux/poison.h](https://github.com/torvalds/linux/blob/master/include/linux/poison.h)
參考 Stack Overflow 上 Gil Hamilton 針對 [what is the meaning of 0xdead000000000000?](https://stackoverflow.com/questions/27801360/what-is-the-meaning-of-0xdead000000000000) 的回答，list poisoning 的目的應該是為了程式開發者除錯方便而產生的一種寫法。
在使用 linked list 時，當我們需要把一塊元素從 list 中去除，通常需要做兩件事：
1. `free(ptr)`
2. 讓 ptr 指向 `NULL`
但是 LIST_POISONING 的作法卻不是讓指標指向 NULL，他反而讓指標指向另一個違法的位址。
這格作法跟指向 NULL 相同的是，日後在存取到時都會造成程式錯誤。
不同的地方是我們可以大概得知程式到底會什麼為 crash。
在 `poison.h` 裡面的註解中提到
Architectures might want to move the poison pointer offset
into some well-recognized area such as 0xdead000000000000,
that is also not mappable by user-space exploits:
如果指標的前綴是 `0xdead`（這只是其中一個例子，這個值我們可以自己設定，但是需要確定是在非法區段），代表是因為我們手動將空間釋放後才導致錯誤，反之則可能是因為沒有初始化等其他錯誤。
Sign in with Wallet
Connect another wallet