# 2018q3 Homework3 (list)

<contributed by < [`siahuat0727`](https://github.com/siahuat0727) >

[作業 E04: list](https://hackmd.io/s/SyVPDd1cX)

### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

我想這是兩個不同的問題。

一般的 function call 的成本除了需要建 stack frame（包括記錄 return address 和傳入參數等）之外，由於需要 jump，不利於 pipeline 的處理。[Why is there overhead when calling functions?
](https://stackoverflow.com/questions/31779335/why-is-there-overhead-when-calling-functions)

而 macro 只是程式碼的替換，沒有 function call 的這些成本，但缺點是沒有型別檢查，容易發生難以察覺的錯誤。

因此 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 中用了很多 inline function 來對 list 做操作，像是:

static inline void INIT_LIST_HEAD(struct list_head *list)
{
	WRITE_ONCE(list->next, list);
	list->prev = list;
}

**inline** 可以提示 compiler 做 code inlining，效果類似 macro 的展開一樣，沒有 call function 的 overhead，卻有 function 的特性，像是型別檢查、可具有回傳值等等。

而 macro 由於只是程式碼替換，可以做到很多 function 無法做到的事情，比如簡化一些常用的表達，像是：

#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
[Referring to a Type with typeof](https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Typeof.html)

int a;
typeof(a) b; // equivalent to int b

`typeof` 這件事也不完全可以在 compile time 得知，因爲 **dynamic type** 的存在：

void func(int n) {
    int a[n][n];
    typeof(a) b;  // typeof(a) 取決於 n 的大小，compile time 無法得知 
}

[Stack Overflow: typeof operator in C](https://stackoverflow.com/questions/12081502/typeof-operator-in-c)

原本想大致了解實作細節，後來發現這個 `func()` 在不做任何最佳化的情況下被轉成 126 條指令！若少了 `typeof(a) b` 剩下 87 條指令，也就是說 `typeof(a) b` 在這裡用了約 126 - 87 = 39 條指令！
原來平時使用了也沒特別留意的 **dynamic type**，背後是多麼複雜的機制！

`typeof` 使用技巧：

Safe maximum macro

#define max(a,b) \
  ({ typeof (a) _a = (a); \
      typeof (b) _b = (b); \
    _a > _b ? _a : _b; })

舉個例子，執行 `max(x++, ++y)` 時，可確保 increment 的動作只會各別被執行**一次**。

### 解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

先解釋 Compound statement enclosed in parentheses：

int x = ({int x = 0; ++x;}); // x = 1

> The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct. (If you use some other kind of statement last within the braces, the construct has type void, and thus effectively no value.)
詳見 [GCC extension: Statements and Declarations in Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html)

再回到題目，目的是通過偏移量去取得 structure 的指標，正確使用時等價於以下寫法：

#define container_of(ptr, type, member) \
      (type *)((char *)(ptr) - offsetof(type,member))

那爲什麼要先宣告 `__mptr` 來存 `ptr` ，再通過 `__mptr` 去計算位移？

原因爲了讓 compiler 檢查 `ptr` 與 `member` 是否匹配。（即 `ptr` 是否指向與 `member` 同 type 的 variable）

如以下程式碼 include/linux/typecheck.h:

/*
* 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; \
}) 

`typecheck` 檢查 `x` 是否爲 `type` 的型態，如果不是，compiler 將拋出 warning: comparison of distinct pointer types lacks a cast。

而其中 cast 成 void 是爲了避免結果被使用，讓 compiler 在優化時可以進行 dead code elimination。

詳見 [GCC typeof在kernel中的使用](http://deltamaster.is-programmer.com/posts/37253.html)

### Linked list 採用環狀是基於哪些考量

Linked list 在實作上的選擇：
1. singly 或 doubly
+ doubly 覆蓋 singly 的使用情境且沒有顯著的 overhead，再加上有些操作在 doubly 上比較方便，如將兩個 list 連接起來。
2. circular 或 non-circular
+ circular 覆蓋 non-circular 的使用情境。使用 doubly **non**-circular linked list 時需要兩個 pointer 分別指向頭尾，其實也就是下圖 doubly circular linked list 的 head（sentinel node）。前後接起來成環狀（當然需要一樣的結構）可以讓操作更統一（TODO 舉例），而這種 list_head 嵌入 structure 的方式可以讓整個 list 更**通用**。（不管 structure 的 member 是什麼都可以使用同樣的 function 和 macro）
[圖片來源](http://os.51cto.com/art/200912/173868.htm)

[Why are all the linked lists circular in the Linux Kernel?](https://www.quora.com/Why-are-all-the-linked-lists-circular-in-the-Linux-Kernel)

---

## 開發環境

$ lscpu
Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               158
Model name:          Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping:            9
CPU MHz:             826.723
CPU max MHz:         3800.0000
CPU min MHz:         800.0000
BogoMIPS:            5616.00
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
NUMA node0 CPU(s):   0-7