---
tags:sysprog2018
---

# list

contributed by <`plusline`>

---

#### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？[Macro vs Function in C](https://stackoverflow.com/questions/9104568/macro-vs-function-in-c)

macro 的執行速度比較快, 使用 function 需要呼叫，而 macro 直接替代文字，所以多了需要呼叫的時間還有空間成本。
但也不應該濫用 macro ，macro 也有許多缺點，macro 沒有拼字檢查，而且在文句替換的過程中，容易產生語意上的錯誤。

#define square(a) a*a
square(1+2) 

我們會期望輸出3*3但實際展開會是1+2*1+2

#define add(a,b,c) a++; b++; c++;
while(count--)
    add(k,l,m)

我們期待 k, l, m 可以加上 count 的次數，但實際上 l++; m++; 只會被執行一次

-----
#### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

- in `list_lru.h` for spinlook implementation
- in `amdgpu_bo_list.c` for avoidance multiple allocations for the head and the array
- `client-buffers.c`

-----
#### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？[typeof operator in C](https://stackoverflow.com/questions/12081502/typeof-operator-in-c)

typeof 可以知道變數的型態，並且可當關鍵字，用來宣告變數。

int a;
typeof(a) b

-----
#### 解釋以下巨集的原理[ Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

* __typeof__　是 macro ，應該是轉換成 `typeof` 可以把 `((type *) 0)->member`　的型態當作一個型態宣告的關鍵字。

* `((type *) 0)`以輸入的型態創建在位置 0 的地方
* `*__pmember` 是變數名稱，而且加了指標，用來貯存 typeof(type->member)　型態的的位置。以命名方式猜測，應也是 macro　。
* offsetof 定義在 [stddef.h](https://github.com/torvalds/linux/blob/master/include/linux/stddef.h)，用來算結構跟成員的位移量。
* `(char *) __pmember - offsetof(type, member)` 以__pmember　減掉偏移量就能得到起點

-----
#### 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
盡量避免刪除新增和遍歷節點，並且保持函式的封閉性。

-----
#### LIST_POISONING 這樣的設計有何意義？

故意讓不應該讀取的位置設成一個不能被讀取的位置，進而在程式執行時讀取到該值能夠直接引起程式崩潰，避免日後讀取到該值後造成不明的後果。

:::info
為什麼 list.h 中的 LIST_POISONING 要指向0x0010010或是0x00200200 這兩個地址有什麼意義嗎？
:::

-----
#### Linked list 採用環狀是基於哪些考量？[Why does the Linux kernel use circular doubly linked lists to store the lists of processes?](https://stackoverflow.com/questions/46089965/why-does-the-linux-kernel-use-circular-doubly-linked-lists-to-store-the-lists-of)
circular linked list 可以在知道搜尋的值靠前或是靠後時，利用 macor 改變搜尋的方向，進而加快搜尋速度。

-----
#### list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？[Why do we need list_for_each_safe() in for deleting nodes in kernel linked list?](https://stackoverflow.com/questions/9207850/why-do-we-need-list-for-each-safe-in-for-deleting-nodes-in-kernel-linked-list)

pos 在 foreach　的過程中會指向其他的值，而做後如果會呼叫 dele 或是 free 都會造成 pos 不存在，因此先用一個變數將 pos 的值先存起來，最後在還原。

-----
#### for_each 風格的開發方式對程式開發者的影響為何？