# 2019q3 Homework3 (list)
contributied by <`nckuoverload`>
###### tags: `sysprog2019`

## 自我檢查清單
- [x] 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
- [x] Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
- [x] GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
- [x] 解釋以下巨集的原理

#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` 這樣的設計有何意義？提示: 和 [Linux 核心記憶體管理](https://hackmd.io/@sysprog/rJBXOchtE)有關
- [ ] linked list 採用環狀是基於哪些考量？
- [ ] 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
- [ ] 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？
- [ ] `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
- [x] for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
- [ ] 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
- [ ] `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
- [ ] `tests/` 目錄的 unit test 可如何持續精進和改善呢？

---
### 1. 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
首先可以參考 [macro vs linked list](https://stackoverflow.com/questions/9104568/macro-vs-function-in-c) 。總結來說，這篇的第一個回覆者覺得各有好壞， macro 並沒有型態檢查 (type checking) ，因此可以當作多型 (polymorphic type) 來使用。

第二個回覆者，針對這兩個方式做了比較，可以整理成下表:
| macro | function |
|-|-|
|Macro is Preprocessed|Function is Compiled|
|No Type Checking|Type Checking is Done|
|Code Length Increases | Code Length remains Same
|Use of macro can lead to side effect | No side Effect
|Speed of Execution is Faster | Speed of Execution is Slower
|Before Compilation macro name is replaced by macro value | During function call, Transfer of Control takes place
|Useful where small code appears many time | Useful where large code appears many time
|Macro does not Check Compile Errors | Function Checks Compile Errors

第二個部分可以討論 **sied effect**:
首先可以參考[這篇問答](https://stackoverflow.com/questions/32284073/what-are-expressions-with-side-effects-and-why-should-they-be-not-passed-to-a-ma)第一個回覆者有舉些例子，例子主要在說明有些情況下，使用 macro 會造成的副作用，例如:
`#define MAX(a, b) ((a) > (b) ? (a) : (b))` 這個 macro 程式碼在 `C99 §6.10.3.5` 也有出現，如果將它寫成

#define MAX(a, b) ((a) > (b) ? (a) : (b))
int x = 5;
int y = 7;
int z = MAX(x++, y++);

y 的部分會累加兩次，解構成 `int z = ((x++) > (y++) ? (x++) : (y++));` ，在前半比較部分就會先累加一次，在三元運算子後又會再累加一次。

第三部分可以探討執行速度 (Speed of Execution):
在編譯階段，編譯器就會將 程式碼中有 macro 的部分替換成 macro 的程式碼，因此在執行階段，程式不需要透過 function call 去跳到函式的所在位址，也就少了呼叫函式的 overhead。

#### 小結:
在 Linux 中會大量使用到 linked-list，如果使用 macro 可以在執行速度上表現較佳。另外在多型方面也較符合 reusable 的精神。
:::info
不確定這邊是否有用到多型的概念?
:::

#### 比較:
如果執行 10000 次作業中的 `merge-sort.c` ，分別引入有 `inline` 和沒有的版本，會如圖所示。
`inline` 平均為 1167 (ticks)
`noinline` 平均為 1208 (ticks)

詳細上來看其實差異並不大，整體沒有使用 `inline` 會較大，

### 2. Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

1. [`linux/net/netfilter/nf_conncount.c`](https://github.com/torvalds/linux/blob/9c7db5004280767566e91a33445bf93aa479ef02/net/netfilter/nf_conncount.c)
netfilter 可以參考自 [Wikipedia](https://en.wikipedia.org/wiki/Netfilter) 的解釋，是一個網路相關操作的框架。
這份程式碼主要是用來計算配對(連結)到一個點所需要的連結數。 `count the number of connections matching an arbitrary key.`

/* we will save the tuples of all connections we care about */
struct nf_conncount_tuple {
	struct list_head		node;
	struct nf_conntrack_tuple	tuple;
	struct nf_conntrack_zone	zone;
	int				cpu;
	u32				jiffies32;
};

在網路中，因為連結點會動態的增減，適合使用 linked-list 這種不需要事先宣告大小的資料型態。

2. [`linux/drivers/watchdog/watchdog_pretimeout.c`](https://github.com/torvalds/linux/blob/2f4c53349961c8ca480193e47da4d44fdb8335a8/drivers/watchdog/watchdog_pretimeout.c)
3. [`linux/fs/dcookies.c`](https://github.com/torvalds/linux/blob/9c7db5004280767566e91a33445bf93aa479ef02/fs/dcookies.c#L3)

### 3. for_each 風格的開發方式對程式開發者的影響為何？
Java 中有個 [Iterator Interface](https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html) 用法和這邊的 foreach 有類似的行為。

當一個開發者需要去探訪每一個節點時方便使用，`for_each` 行為上類似 `hasNext()`、`Next()`等。當一個開發者需要探訪某一個集合或是資料結構底層時，不需要了解對應的結構，只要會善用這種函式就可以輕易的走訪每個節點。

### 4. 解釋 container_of 巨集的原理
首先參考這篇[Linux Kernel: container_of 巨集](http://adrianhuang.blogspot.com/2010/01/linux-kernel-containerof.html)。主要是用來方便程式取得某一個結構的起始位址。

`__extension__`: 參考自[Alternate Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#Alternate-Keywords)，GCC 在ANSI C 上做一些擴展，使用 `__` 這類型的就是避免編譯器對這些擴展拋出警告。

`__typeof__`: 依照 [Wikipedia](https://en.wikipedia.org/wiki/Typeof) 的敘述，主要是用來指定某個變數的型別，透過傳入的 1. 表示式 2. 類別 來決定。在 macro 中，因為 macro 無法指定型別，透過這個函式可以用來將型別指定為傳入的參數。

`offset()`: 計算該變數在這個結構上的偏移值。下列程式碼中，`test` 的偏移量為 0 ，`a` 的偏移量為10 byte。

struct node {
    char test[10];
    int a;
};

`container_of` 搭配 linked-list 的 `head` 可以很輕鬆地得到整個 list 的起始位址。它會用 `list_entry` 包裝，並且搭配 `list_first_entry` 和 `list_last_entry` 使用。

`head` 為這個串列的 head，它的 *next 即為這個串列的第一個節點的起始位址。

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

反之，可以得到串列的最後一個節點的起始位址。

#define list_last_entry(head, type, member) \
    list_entry((head)->prev, type, member)

## implement merge sort
### 1. 切割
程式碼第 26 ~ 45 行，主要是使用遞迴將程式碼切割成左和右。
36~37: 為了避免弄亂排序，左邊的部分從頭開始依序加入，右邊的部分則反向從尾巴開始依序加入。
38~41: 如果串列剩下一個值，無法切割左右，則加入到左邊。
44~45: 遞迴處理。

    struct list_head list_left, list_right;
    INIT_LIST_HEAD(&list_left);
    INIT_LIST_HEAD(&list_right);
    
    struct listitem *left_item = NULL, *right_item = NULL;
    while (!list_empty(head)) {
        left_item = list_first_entry(head, struct listitem, list);
        right_item = list_last_entry(head, struct listitem, list);
        list_del(&left_item->list);
        list_del(&right_item->list);
        list_add(&right_item->list, &list_right);
        list_add_tail(&left_item->list, &list_left);
        if (list_is_singular(head)) {
            left_item = list_first_entry(head, struct listitem, list);
            list_del(&left_item->list);
            list_add_tail(&left_item->list, &list_left);
        }
    }
    list_mergesort(&list_left);
    list_mergesort(&list_right);

### 2. 比較合併
遞迴完成後，將左邊和右邊比較並且插入插入串列中。
48~54: 當左或右其中一個串列已經為空時，將未空的串列剩下的節點全數直接貼到目標串列中。
59~64: 先取出左右串列中第一個值，並且比較後將較小的貼到目標串列中。

    while (!list_empty(&list_left) || !list_empty(&list_right)) {
        if (list_empty(&list_left)) {
            list_splice_tail(&list_right, head);
            break;
        } else if (list_empty(&list_right)) {
            list_splice_tail(&list_left, head);
            break;
        }
        struct listitem *l =
                            list_first_entry(&list_left, struct listitem, list),
                        *r = list_first_entry(&list_right, struct listitem,
                                              list);
        if (cmpint(&l->i, &r->i) < 0) {
            list_del(&l->list);
            list_add_tail(&l->list, head);
        } else {
            list_del(&r->list);
            list_add_tail(&r->list, head);
        }
    }

###