# 2019q3 Homework3 (list)
contributed by <`davinais`>
###### tags: `sysprog` `sysprog2019`
:::success
剛好以前在修作業系統的時候有研究過 Linux 核心中實作的 Linked List,看到了不少技巧所以也在[自己的作業系統的 Project](https://github.com/Davinais/MumiChat) 中使用了一下
:::
## 作業要求
* 回答 [「Linux 風格的 linked list」](/@sysprog/S12jCWKHN#Linux-%E9%A2%A8%E6%A0%BC%E7%9A%84-linked-list)裡頭「自我檢查清單」的所有問題,需要附上對應的參考資料和必要的程式碼
* [x] 為何 Linux 採用 macro 來實作 linked list?一般的 function call 有何成本?
- macro 是字面代換,而一般的 function call 還有呼叫堆疊的成本。而為了擁有型態檢查,Linux 也同時使用了 static inline 期望編譯器於編譯時可以對其做 inline 最佳化。
* [x] [[Link]](###什麼時候會用到Linked-List?) Linux 應用 linked list 在哪些場合?舉三個案例並附上對應程式碼,需要解說,以及揣摩對應的考量
* [x] [[Link]](###那麼`typeof`在幹嘛?) GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用?在程式碼中扮演什麼角色?
* [x] [[Link]](###`container_of`) 解釋以下巨集的原理
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
* [x] 除了你熟悉的 add 和 delete 操作,`list.h` 還定義一系列操作,為什麼呢?這些有什麼益處?
- 比如說 `replace` 、 `move` 、 `swap` 或者 `list_for_each` 等,對於我們如果要另外設計加入其他的演算法,比如 sort 之類的會非常方便。而 `list_for_each` 可以讓我們不用在意 list 的內部結構而直接進行迭代。
* [x] `LIST_POISONING` 這樣的設計有何意義?
- 使用 `LIST_POISONING` 來取代掉 `NULL`,不但可以避免使用 `NULL` 而不小心發生的意外操作,我們也能很容易地確認存取越界時是否是在 `list_del()` 處出錯。
* [x] linked list 採用環狀是基於哪些考量?
- 採用 circular 的一大特點是可以只使用單一的 `struct type` 便能建立一個 list。如果採用的是普通的 Doubly Linked-List,為了能夠對 `insert_to_tail()` 加速,可能會採取紀錄 head 以及 tail 指標的作法,這個紀錄的節點不但與一般的 node 結構相仿,而且其實這就跟 circular 沒什麼兩樣了。那麼我們不如一開始就直接採用 circular,並且 reuse 我們的 node 架構,如此一來甚至還不用處理 head 和 node 是不同 type 的問題。
* [x] 什麼情境會需要對 linked list 做排序呢?舉出真實世界的應用,最好在作業系統核心出現
- 基本上我認為只要能夠有大小這種屬性的東西就一定能拿來排序,那什麼時候需要對 linked list 做排序?當然就是如果我是使用 linked list 做儲存的時候了。
* [x] 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢?又,你打算如何實作?
- ~~這好像是 CLSR 的經典問題之一~~,舉例像是在 quick sort 中在選 pivot 的時候,我們就能藉由這種方法選到最適合的 pivot。
* [x] `list_for_each_safe` 和 `list_for_each` 的差異在哪?"safe" 在執行時期的影響為何?
- 於 "safe" 版本中,我們多使用一個指標 `n` 先行指向目前元素的下一個元素 (`pos->next`),如此一來可以確定在刪除元素時不會有問題。
- 而 "safe" 版本也是因為還要額外去更動 `n` 指標的指向,會比一般版本還要慢一些。
* [x] for_each 風格的開發方式對程式開發者的影響為何?
* 提示:對照其他程式語言,如 Perl 和 Python
- 我認為最重要的是影響迭代的執行方式,以前還需要先了解該資料結構才能夠進行迭代,而以 for_each 的方式,我們不必在意資料內部結構就能夠進行迭代了。
* [ ] 程式註解裡頭大量存在 `@` 符號,這有何意義?你能否應用在後續的程式開發呢?
* 提示: 對照看 Doxygen
* [x] `tests/` 目錄底下的 unit test 的作用為何?就軟體工程來說的精神為何?
- unit test 的作用主要在於檢查每個功能是否都能正常運行,而不用等到之後編譯完再自己慢慢餵測資。
* [ ] `tests/` 目錄的 unit test 可如何持續精進和改善呢?
* 在 GitHub 上 fork [linux-list](https://github.com/sysprog21/linux-list) 並學習裡頭的技巧,包含裡頭 unit test 的設計,透過給定的 linked list 操作,進而實作出 merge sort
* [ ] 附上你的修改過程,也需要讓 `qtest` 得以支援
* [ ] 可將 [dict](https://hackmd.io/s/B1Bq5Jat7) 裡頭的測試資料拿來作效能分析的輸入
* [ ] 思考提升排序效率的方法,需要做平均和最壞狀況的分析
::: success
我先在 [2019q3 Homework4 (quiz4)](/@Davinais/r1n0U2MKB#Timsort) 的部分寫完了 merge sort 的優化版本 tim sort,待移植。
:::
## 前情提要
### 什麼時候會用到Linked-List?
首先,Linked List 做為資料結構有個好處,它是一個可以於任何位置動態插入以及刪除的列表,並且我們並不需要先決定元素的個數。舉凡 array 如果要做動態插入或刪除,基本上要更動所有元素的位置,而且大小還需要事先決定;queue 以及 stack 原則上只能於 head 以及 tail 做更動;而如果用到 tree 的話,其實也能以多個 Linked List 組合而成。因此 Linked List 在動態維護上是相對有優勢的。
那麼 Linux 有在哪裡用到它呢?比方說有關於檔案系統的 [`fs/mount.h`](https://github.com/torvalds/linux/blob/master/fs/mount.h):
```c
struct mount {
...
struct list_head mnt_mounts; /* list of children, anchored here */
struct list_head mnt_child; /* and going through their mnt_child */
struct list_head mnt_instance; /* mount instance on sb->s_mounts */
const char *mnt_devname; /* Name of device e.g. /dev/dsk/hda1 */
struct list_head mnt_list;
struct list_head mnt_expire; /* link in fs-specific expiry list */
struct list_head mnt_share; /* circular list of shared mounts */
struct list_head mnt_slave_list;/* list of slave mounts */
struct list_head mnt_slave; /* slave list entry */
...
} __randomize_layout;
```
因為我們並不知道有多少檔案系統需要被掛載,也不確定會目前的檔案系統有多少個子檔案系統等,因此我們採用簡單的 Doubly Linked-List 來動態維護這些訊息,雙向結構也為存取帶來一些方便。
而除了 Doubly Linked-List,Linux 其實還有一個專門為 hash table 設計的 `hlist`,同樣放在[`linux/list.h`](https://github.com/torvalds/linux/blob/master/include/linux/list.h#L731),不過 `hlist` 的 head 便是單向的結構了。這是由於 hash table 本身就是為了在大量資料中快速查找而使用的架構,如果使用了 Doubly Linked-List ,hash table 又相當巨大的話,光是 Linked-List 的 head 會耗掉不少記憶體空間,因此 Linux 在 head 的部分只保留單向,但是在 node 的部分仍舊是保存雙向。值得注意的是 `hlist` 中 node 的 `pprev` 並不是指向上一個元素,而是指向上一個元素的 `next` 指標,這使得我們就算是刪除最開頭的元素時,也只要使用 `*pprev = next` 即可簡單修改指標的指向。
Linux 的 pid 就有相關的應用,比如說 [`linux/pid.c`](https://github.com/torvalds/linux/blob/master/kernel/pid.c#L215) 中,我們可以看到 pid 裏頭的 tasks 就是使用 hlist 所保存的。
## 閱讀 `list.h`
在了解 Linux 的 Linked List 之前一定要先介紹以下兩個巨集 `offsetof` 以及 `container_of` ,基本上正是因為有這兩個巨集,我們才可以使用侵入式的資料結構來存取資料。
### `offsetof`
`offsetof` 巨集相當簡單,被定義在 `stddef.h` 中,只有一行:
```c
/**
* Get offset of a member
*/
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
```
不過從這邊我可們就可以看出轉型的妙用。在這個 macro 中我們需要提供兩個參數: `TYPE` 以及 `MEMBER`,我們用他來找出一個 struct 中,某一 member 與 struct 本身的位址相差多少。其中 `TYPE` 便是指包含 `MEMBER` 的 struct type,`MEMBER` 便是我們想要知道的 member 名稱。
首先我們先將 `0` 強制轉型成 `TYPE *`,如此一來我們便能夠以對待 `TYPE *` 的方式來與這個 `0` 互動。我們隨後使用這個指標透過 `->` 運算子(C99 [6.5.2.3])來存取 `MEMBER`,最後再對 `MEMBER` 使用 `&` 運算子進行取址,得到一個 address。由於我們初始的指標位址指向 `0`,而我們透過 `->` 運算子取得 `MEMBER` 時,我們依照 struct 中 `MEMBER` 位址與 struct 本身的差距來位移並且取得該 `MEMBER` 的值,**也就是我們會位移 `MEMBER` 的 offset**。
最後進行取址,由於我們初始位址是 `0`,根據我們對 base address 位移 offset 寫出算式: $0 + \text{offset of MEMBER} = \text{offset of MEMBER}$,即可取得 `MEMBER` 的 offset。最後轉型成 `size_t` 以代表這是**大小**。
舉個例子,假設這裡有一個 `struct`:
```c
struct rabbit_house_t {
int kokoa;
long chino;
float lize;
};
```
如果我們像下列方式執行 `offsetof`:
```c
offsetof(struct rabbit_house_t, chino);
```
首先我們強制將 `0` 轉型成 `struct rabbit_house_t *` 之後去取得 `chino` 並進行取址,如下圖所示:
![](https://i.imgur.com/ZxJu1pf.png)
可以發現我們位移了一段 offset,就是 `chino` 的 offset,又因為我們的 base address 是 `0`,因此 `chino` 所在的位址剛好就和 offset 相等。
### `container_of`
`container_of` 運用了 `offsetof` 來取得 `MEMBER` 原先所在的容器,先看看這個 macro 是怎麼寫的:
```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
*/
#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#else
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif
```
`container_of` 需要提供三個參數: `ptr` 、 `type` 以及 `member`。`type` 與 `member` 代表的意義與 `offsetof` 相同,我們也能在 macro 中看到對 `offsetof` 的直接調用,而 `ptr` 是一個指向 `type` 中 `member` 成員的指標。這個 macro 的目標正是為了找到裝 `ptr` 的容器,並且回傳指向該容器的指標,以便我們進行後續操作。
由於 `typeof` 為 GNU Extension,我們這裡使用 `__LIST_HAVE_TYPEOF` 來實作有 `typeof` 以及沒有 `typeof` 的版本。這兩個版本唯一的差別,就是有 `typeof` 的版本,我們另外複製了一個 `const` 的 pointer 來進行操作,而沒有 `typeof` 的則是直接使用 `ptr` 進行操作。
先來解釋只有 `typeof` 版本才有的第一行 `const __typeof__(((type *) 0)->member) *__pmember = (ptr);`。其實這就是宣告一個指向 `*ptr` 的 const pointer,我們透過`__typeof__(((type *) 0)->member)` 來取得 `member` 的 type,並且由此建立一個 `__pmember` 指標。
隨後就是兩者共通的 `((type *) ((char *) (ptr) -offsetof(type, member)))`,在有 `typeof` 版本中 `ptr` 被換成 `__pmember` 但其實大同小異。我們將 `ptr` 強制轉型成 `char *`,如此一來如果對該指標進行增減,便是以 1 byte 的單位變化。再來我們對該 `ptr` 減去 `offsetof(type, member)` 的值,**原本指向 `member` 的指標,在減去 `member` 的 offset 之後,就指向了裝著該 `member` 的容器**,再轉型成 `type *`,我們便能取得指向容器的指標了。
### 那麼`typeof`在幹嘛?
`typeof` 運作邏輯很簡單,我給他參數,他會告訴我參數的型態,比如說:
```c
unsigned int x;
typeof(x);
```
他會告訴我 `x` 屬於 unsigned int。在本段程式碼中,我們用來建立一個新的 const pointer 指向該 type,可以避免意外修改到原先的 `ptr` 之情況發生。
:::warning
待補
:::