F02: list

contributed by < afcidk >

F02: list

自我檢查事項

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

macro 在編譯時期會被編譯器展開成實際的程式碼，這樣做的好處是可以加速程式的速度。

在進行 function call 的時候，因為我們除了需要把參數 push 到特定的 register 或是 stack 上以外，還需要儲存當前 register 的值到 stack 上。function call 少時，這個影響還看不出來，但是一但數量變大，就會導致程式運作比用 macro 實作時慢。

實際執行一段簡單的程式碼，並用 gnuplot 顯示使用 function call 與 macro 的執行時間差異。

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 →

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，光是定義整個結構就需要 628 行！

因為整份程式碼太龐大，這邊我節錄在 task_struct 裡頭紀錄 parent/child 的部份解釋


















/*
 * 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，他可以允許動態分配位址的資料結構（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 裡頭的 inode 結構也有 list_head 的蹤影



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 有何作用？在程式碼中扮演什麼角色？

typeof 允許我們傳入一個變數，代表的會是該變數的型態。
舉例來說：

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 的巨集為例子

#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 的問題，顧名思義就是會有某些東西被執行過兩次。

試想如下情況

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

為了避免這個問題，我們必須在巨集中先用變數把可能傳入的函式回傳值儲存下來，之後判斷就不要再使用一開始傳入的函式，而是是用後來宣告的回傳值變數。

解釋以下巨集的原理

#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 的開頭位址而已。

以圖像的方式會長這樣

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 →

LIST_POISONING 這樣的設計有何意義？

跟 poison 相關的定義可以查看 linux/poison.h

參考 Stack Overflow 上 Gil Hamilton 針對 what is the meaning of 0xdead000000000000? 的回答，list poisoning 的目的應該是為了程式開發者除錯方便而產生的一種寫法。

在使用 linked list 時，當我們需要把一塊元素從 list 中去除，通常需要做兩件事：

free(ptr)
讓 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（這只是其中一個例子，這個值我們可以自己設定，但是需要確定是在非法區段），代表是因為我們手動將空間釋放後才導致錯誤，反之則可能是因為沒有初始化等其他錯誤。