# 2018q3 Homework3 (list)
contributed by < [`dange0`](https://github.com/dange0) >
###### tags: `sysprog2018`
## 自我檢查事項:
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* macro
* 會在前置時期將 macro 展開，並且替換調原本程式碼中所有有使用到 macro 的地方
* 優點：省去對 stack frame 的操作，執行較有效率，是以空間換取時間的操作
* 缺點：如果呼叫次數過多的話，會佔用較多記憶體空間
* function call
* 在執行時期，需要用到該 function 時才跳過去使用
* 優點：
* 即使需要多次呼叫該 function，只需要放一份 function code 於記憶體中，可以節省記憶體空間，是以時間換取空間的方式。
* function call 會對 parameter 做型態的檢查
* 缺點：每次使用 function 時，都必須先為他創立一個 stack frame，比較耗時
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
*
### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* `typeof` 會將物件的類型返回
* A typeof construct can be used anywhere a typedef name can be used. For example, you can use it in a ==declaration, in a cast, or inside of sizeof or typeof==.
一個 typeof 的範例
```C
#define max(a,b) \
({ typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; })
```
因為在前置時期，還無法判斷 a 與 b 的型態，因此透過 `typeof` 的兩個特性：
* 可以動態返回物件類型的特性，
* 可以使用於 `declaration`
使得 `max` 可以在執行時期才去決定 `_a` 的型態要宣告為何
### 解釋以下巨集的原理
```C
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
這個巨集可以拆為
- `__extension__`
- `__typeof__(((type *) 0)->member) *__pmember = (ptr)`
- `offsetof`
- `(type *) ((char *) __pmember - offsetof(type, member))`
去看：
* `__extension__`
:::info
[**Gcc gnu online docs 6.46 Alternate Keywords**](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html)
-pedantic and other options cause warnings for many GNU C extensions. You can prevent such warnings within one expression by writing \_\_extension\_\_ before the expression. \_\_extension\_\_ has no effect aside from this.
:::
* 主要是 ISO C 與 GNU C 在一些關鍵字有不同的表示法，如 `asm`,`typeof`,`inline` 等等，因此加上 `__extension__` 就可以避免於編譯時期產生警告訊息
* `((type *) 0)->member) *__pmember = (ptr);`
* `((type *) 0)`：將 0 強制轉型為 pointer to type
* `__typeof__(((type *) 0)->member))`：透過 `__typeof__` 取出 member 的型態
* `const __typeof__(((type *) 0)->member) *__pmember = (ptr)`：利用 member 的型態宣告 `*__pmember`
* `offsetof`
* 於 `stddef.h` 中有定義 `offsetof` 如下：
```clike
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
```
* `&` 的關係，marco 2結果為 member 的地址
* `(TYPE *)0` 的關係，該 struct 的起始位置為 0，因此 member 的地址，也就成了 member 位於這個 struct 的偏移量
* `(type *) ((char *) __pmember - offsetof(type, member))`
* 將 `__pmember` 的位置減掉 member 於 struct 中的偏移量，就會得到整個 strcut 的起始位置
* 利用 `(char *)` 將 `__pmember` 強制轉型是因為 pointer type 在做加減法時，會依照其型態決定一次 offset 多少，將其型態轉為 char 可以確保以 `1 byte` 為單位做加減法[^1]
:::warning
:question: Question：
為什麼 `__pmember` 要先宣告為為 `(type *) 0)->member)*` 再強制轉型為 `char*` 呢？何不一開始就宣告為 `char*`？
:::
[^2]
### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
*
### `LIST_POISONING` 這樣的設計有何意義？
在 linux kernel 中，在 list_del 時，會將 node 的 next 與 prev 分別指向 `LIST_POISON1` 與 `LIST_POISON2`
[**linux/list.h**](https://github.com/torvalds/linux/blob/master/include/linux/list.h#L123)
```clike
#include <linux/poison.h>
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
```
`LIST_POISON1` 與 `LIST_POISON2` 被定義於 `poison.h` 中
[**linux/poison.h**](https://github.com/torvalds/linux/blob/master/include/linux/poison.h#L18)
```clike
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x200 + POISON_POINTER_DELTA)
```
`poison.h` 中說明了指到 `LIST_POISON1` 與 `LIST_POISON2` 是為了要偵測 page fault 的發生
透過這樣的方式，linux kernel 可以更精確的掌握錯誤情況：[^3]
- 錯誤發生於 `->next` 與 `->prev` 都指向 `NULL` 的情況，代表該 node 尚未初始
- 錯誤發生於 `->next` 與 `->prev` 分別指向 `LIST_POISON1` 與 `LIST_POISON2`，代表有 `Use after free` 發生
### linked list 採用環狀是基於哪些考量？
:::info
[**Linux Device Drivers 3/e, ch11**](https://static.lwn.net/images/pdf/LDD3/ch11.pdf)
==To reduce the amount of duplicated code==, the kernel developers have created a standard implementation of circular, doubly linked lists; others needing to manipulate lists are encouraged to use this facility.
...
Since Linux lists are circular, ==the head of the list is not generally different from any other entry==.
:::
- 減少重複的程式碼
- 不用特別去紀錄 linked list 的開頭
### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
```clike
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
- 利用 list_for_each 做刪除時， `node->prev = (struct list_head *) (0x00100100)` 與 `node->next = (struct list_head *) (0x00200200)` 會將 node->next 改變，導致在做 `node = node->next` 時會出錯
```clike
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
- 透過 safe 紀錄 node->next，使刪除節點可以順利進行
- 在刪除 node 時，雖然改變 node->next 的值，但是 safe 已經先將其記錄，因此不會有影響
### for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
* 代表會走訪所有的物件，類似 python 中的 `for ... in ...`
### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
* 在 Doxygen[^4] 中， `@` 代表的是 command 的開始，可以與 `\` 做替換
### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* 單元測試（英語：Unit Testing）又稱為模組測試, 是針對程式模組（軟體設計的**最小單位**）來進行正確性檢驗的測試工作。[^5]
### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
*
## lab-list
### 預期目標
- 包含 unit test 的設計
- 改為doubly-linked list 且充分考慮到 circular
- 讓 `qtest` 得以支援
- 可將 [dict](https://hackmd.io/s/B1Bq5Jat7) 裡頭的測試資料拿來作效能分析的輸入
[^1]: [Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)
[^2]: [Rationale behind the container_of macro in linux/list.h - Stackoverflow](https://stackoverflow.com/questions/6083734/rationale-behind-the-container-of-macro-in-linux-list-h)
[^3]: [What is the role of LIST_POISON1 and LIST_POISON2?
](https://lists.kernelnewbies.org/pipermail/kernelnewbies/2016-March/015879.html)
[^4]: [Doxygen](https://www.stack.nl/~dimitri/doxygen/manual/commands.html)
[^5]: [wiki 單元測試](https://zh.wikipedia.org/wiki/%E5%8D%95%E5%85%83%E6%B5%8B%E8%AF%95)
Sign in with Wallet
Connect another wallet