# 2019q1 Homework1 (list)
contributed by < `LiunuXXX` >
###### tags: `LinuxkernelClass`
==[作業說明直播錄影](https://youtu.be/HlvvnRXzleQ)==
## 預期目標
* 學習 Linux 核心原始程式碼的資料結構
* 資料封裝和 C 語言程式設計技巧
* 設計 unit test
## Linux 風格的 linked list
閱讀 [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf) 共筆和觀看解說錄影。
```shell
$ git clone https://github.com/sysprog21/linux-list
$ cd linux-list
$ make
```
預期會得到以下輸出:
```
CC tests/containerof.o
LD tests/containerof
*** Validating tests/containerof ***
[ Verified ]
...
CC tests/list_cut_position.o
LD tests/list_cut_position
*** Validating tests/list\_cut\_position ***
[ Verified ]
```
其中 `include/list.h` 學習 Linux 核心原始程式碼的 linked list 資料結構實作程式碼。
- [ ] 自我檢查事項:
* 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
* GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* 解釋以下巨集的原理
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
* 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
* `LIST_POISONING` 這樣的設計有何意義？
* linked list 採用環狀是基於哪些考量？
* 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
* 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？
* `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
* for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
* 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
* `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* `tests/` 目錄的 unit test 可如何持續精進和改善呢？
## 作業要求
* 回答上述「Linux 風格的 linked list」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
* 在 GitHub 上 fork [linux-list](https://github.com/sysprog21/linux-list) 並學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，進而實作出 merge sort
* 附上你的修改過程，也需要讓 `qtest` 得以支援
* 可將 [dict](https://hackmd.io/s/B1Bq5Jat7) 裡頭的測試資料拿來作效能分析的輸入
* 思考提升排序效率的方法，需要做平均和最壞狀況的分析
## 作業區
## 自我檢查事項
---
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
首先我們看看 macro 和 funtion 的功能和運作方式
* macro: 也稱作巨集，利用 `#define` 語法在編譯前就展開成定義，只是單純的文字替換，是一種利用空間換取時間的作法，不會有 funtion call 跳躍至函式的行為，也不會有函式呼叫需要的 stack 相關行為。
例如 [list.h](https://github.com/sysprog21/linux-list/blob/master/include/list.h) 內的
```clike
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
```
* funtion: 即一般所稱的函式，執行時期才會 funtion call 呼叫函式，套至函式執行點，並且利用 stack push or pop 等行為記錄目前所執行的資料、返回點等，缺點是時間長，但不像 macro 每次遇到都要展開佔用空間。
## Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
## GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* typeof(x) 會回傳 x 型別，其中 x 可以是變數或是型別。
例如:
```clike
int x;
type of(x) y; // declare y as type of x (int)
```
## 解釋以下巨集的原理
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
`__extension__`:
加在 expresion 前避免 GNU C extensions 編譯時產生 warning
`(type *) 0)->member`：
將 0 轉型為 pointer to type 並指向 member
`__typeof__(((type *) 0)->member)`：
用 `typeof` 取得 member 的 type
`__typeof__(((type *) 0)->member) *__pmember`:
declare `__pmember` as pointer to `type of member`
`__typeof__(((type *) 0)->member) *__pmember = (ptr)`:
將 `ptr` 的位址 assign 給 `__pmember`
## 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
```clike
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
剪取一段 linked list，方便在資料的分離使用
```clike
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
用以確認 liked list 是否只有一個 node
## `LIST_POISONING` 這樣的設計有何意義？
在 list.h 中提到
```clike
* LIST_POISONING can be enabled during build-time to provoke an invalid memory
* access when the memory behind the next/prev pointer is used after a list_del.
* This only works on systems which prohibit access to the predefined memory
* addresses.
*/
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
其目的是防止，`list_del()` 刪除 list 之後， `prev` 和 `next` 仍被使用，除了可能造成程式運作錯誤以外，還可能有其他資安問題，因此利用 LIST_POISONING 將其指向特殊位址。
## linked list 採用環狀是基於哪些考量?
* reliability:
若從某一個節點斷開，不至於像非環狀可能失去一整段 list，可靠度較高。
## 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
## 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？
## `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
## for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
## 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
## `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
## `tests/` 目錄的 unit test 可如何持續精進和改善呢？
Sign in with Wallet
Connect another wallet