2018q1 Homework3 (list)
===
contributed by < [Jyun-Neng](https://github.com/Jyun-Neng) >
## 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* macro
* 優點：執行速度快，沒有 stack 的 push 和 pop 動作的需要，減少時間的耗損。
* 缺點：macro 被呼叫多次以後，會耗損存放及使用大量的記憶體空間。
:::info
macro 的維護成本較高，而且編譯器無法充分檢查型態和誤用的狀況
:notes: jserv
:::
* function
* 優點：即使 function 被呼叫多次，在記憶體中仍只有一份實體，較節省記憶體空間。能節省存放及使用的記憶體空間。
* 缺點：執行速度較慢，需花費時間在 stack 的 push 和 pop 動作上。
## Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
## GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* typeof(x) 會回傳 x 的資料型態。
:::info
使用案例呢？
:notes: jserv
:::
### linux kernal 中的型態檢查
[include/linux/typecheck.h](https://github.com/torvalds/linux/blob/master/include/linux/typecheck.h)
```clike=
/*
* Check at compile time that something is of a particular type.
* Always evaluates to 1 so you may use it easily in comparisons.
*/
#define typecheck(type,x) \
({ type __dummy; \
typeof(x) __dummy2; \
(void)(&__dummy == &__dummy2); \
1; \
})
/*
* Check at compile time that 'function' is a certain type, or is a pointer
* to that type (needs to use typedef for the function type.)
*/
#define typecheck_fn(type,function) \
({ typeof(type) __tmp = function; \
(void)__tmp; \
})
```
`typecheck` 用於檢查 `x` 是否為 `type` 型態，若不是，則在編譯時期會拋出一個 warning。
```shell
warning: comparison of distinct pointer types lacks a cast
```
`typecheck_fn` 用於檢查 `function` 是否為 `type` 型態，若不是，則在編譯時期會拋出一個 warning。
```shell
warning: initialization from incompatible pointer type
```
## 解釋以下巨集的原理
```Clike=
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
[Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)
### offsetof macro
* offset macro 的目的是用於計算結構中成員相對於資料結構起始位址的位移量。
```C=
#include <stdio.h>
#include <stddef.h>
struct obj {
char dataA;
char dataB;
struct obj *next;
} obj;
int main() {
printf("%ld\n", sizeof(obj));
printf("%ld\n", offsetof(struct obj, dataA));
printf("%ld\n", offsetof(struct obj, dataB));
printf("%ld\n", offsetof(struct obj, next));
}
```
輸出結果為：
```shell
16
0
1
8
```
:::info
我將上面參考連結的 offset 實作中的資料結構成員改成兩個 `char` 型態，在這發現了最後再算 `next` 這個成員的位址時理應是 2 才對，但結果卻是 8。
此外若將成員改成一個是 `int` 一個是 `char` 則兩個成員的位址都會是對齊 `int` 也就是輸出結果會變為：
```shell
0
4
8
```
並沒有 1 的位移量。
:::
:::success
[C – Structure Padding](https://fresh2refresh.com/c-programming/c-structure-padding/) 根據這篇可以知道，電腦一次是存取一個 word，而我所使用的是 64 bits 的處理器，因此一個 word 為 64 bits (8 bytes)，所以為了對齊 `next` 的位移量才會是 8。
:::
### containter_of macro
* container_of macro 的目的為計算資料結構的起始位址，也就是說我們若只給資料結構的成員便可由此成員的位址推得其所載資料結構的位址。
* 第三行程式碼給定一個變數 `pmember`，其形態為給定的資料結構中 `member` 的型態並為常數型態，並將 `ptr` 的位址 assign 給 `pmember`。
:::info
`((type *) 0)->member` 還是不理解為什麼需要 0 這個位址。
:::
:::success
此目的是將 0 強制轉成 pointer to type，並以 0 此 type 的起始位址。
:::
:::info
為什麼要強制轉成 pointer to character，不論是否轉型態 pointer 的 size 應當都是 4 bytes 或 8 bytes，只需將最後算得的位址強制轉成 pointer to type 就好了才對。
:::
:::success
[The (char *) casting in container_of() macro in linux kernel](https://stackoverflow.com/questions/20421910/the-char-casting-in-container-of-macro-in-linux-kernel)
根據這篇的回答，目的是為了在 byte-level 的位址進行計算，因為 offset macro 得到的位移量是以 byte 來計算的。
:::
```C
/**
* container_of() - Calculate address of object that contains address ptr
* @ptr: pointer to member variable
* @type: type of the structure containing ptr
* @member: name of the member variable in struct @type
*
* Return: @type pointer of object containing ptr
*/
```
## 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
## `LIST_POISONING` 這樣的設計有何意義？
`LIST_POISONING` 用於刪除 entry 的時候。將被刪除的 entry 所指向的 `next` 及 `prev` 都改為指向不合法的記憶體位址，之後存取到這個 entry 會產生 page fault。
[list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)
```C=
/**
* list_del - deletes entry from list.
* @entry: the element to delete from the list.
* Note: list_empty() on entry does not return true after this, the entry is
* in an undefined state.
*/
static inline void __list_del_entry(struct list_head *entry)
{
if (!__list_del_entry_valid(entry))
return;
__list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
```
[poinson.h](https://github.com/spotify/linux/blob/master/include/linux/poison.h)
```C=
/*
* 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 *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
```
`0x00100100` 及 `0x00200200` 這兩個記憶體位址分別代表不合法的 next pointer 及 prev pointer。
## linked list 採用環狀是基於哪些考量？
## `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
* `list_for_each_safe` 會額外將下一個 node 也記錄下來，可避免刪除該 node 後會找不下一個 node。
```C
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
## for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
## 程式註解裡頭大量存在 `@` 符號，這有何意義？
* 主要是用於文件生成，此為文件生成的格式。
* [Linux Kernel Documentation](https://www.kernel.org/doc/html/v4.9/kernel-documentation.html) 是用 [Sphinx](http://www.sphinx-doc.org/en/master/) 來產生文件。
註解的格式如下：
```C=
/**
* foobar() - Brief description of foobar.
* @arg: Description of argument of foobar.
*
* Longer description of foobar.
*
* Return: Description of return value of foobar.
*/
int foobar(int arg)
```
## `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
## `tests/` 目錄的 unit test 可如何持續精進和改善呢？
Sign in with Wallet
Connect another wallet