# 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`) 解釋以下巨集的原理

    #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)：

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` 中，只有一行：

/**
 * 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`：

struct rabbit_house_t {
    int kokoa;
    long chino;
    float lize;
};

如果我們像下列方式執行 `offsetof`：

offsetof(struct rabbit_house_t, chino);

首先我們強制將 `0` 轉型成 `struct rabbit_house_t *` 之後去取得 `chino` 並進行取址，如下圖所示：

可以發現我們位移了一段 offset，就是 `chino` 的 offset，又因為我們的 base address 是 `0`，因此 `chino` 所在的位址剛好就和 offset 相等。

### `container_of`

`container_of` 運用了 `offsetof` 來取得 `MEMBER` 原先所在的容器，先看看這個 macro 是怎麼寫的：

/**
 * 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` 運作邏輯很簡單，我給他參數，他會告訴我參數的型態，比如說：

unsigned int x;
typeof(x);

他會告訴我 `x` 屬於 unsigned int。在本段程式碼中，我們用來建立一個新的 const pointer 指向該 type，可以避免意外修改到原先的 `ptr` 之情況發生。

:::warning
待補
:::