2019q1 Homework1 (list)

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

macro 是由 gcc toolchain 中的 preprocesser 提供的一個語言特性，會在編譯時期將代碼中的 macro 展開，而不是使用 function call，就如同 inline function 一樣。function call 相較於 macro 多出了兩個階段

• function prolologe
• function epologe

分別是用於建立與摧毀 function 存放區域變數所需的 stack frame，過程中會對 stack 進行讀寫(push, pop)，造成記憶體讀寫的時間開銷。所以若是沒有需要維護 function 中的區域變數時，或許可以改採用 macro 的形式來寫作，而 linux kernel 中的 linked list 操作就是如此 (在後方問題中會詳細說明)。

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

struct list_head

struct list_head {
	struct list_head *next, *prev;
};

和一般撰寫程式時直接利用該 struct 的指標操作不同，linux kernel 中的 linked list 實作多是這種單一作用的元件，配合 container_of macro 讓 linked list 變成是一個能夠被模組化的特性，也就不必為每個 struct 寫不同的 linked list 操作函式，我認為這是相當值得借鑒的。

include/linux/sched.h

struct task_struct {
	...
	struct list_head children;
	struct list_head sibling;
	...
}

在 task_struct 中利用 list_head 來建立 parent, children 的樹狀關係

GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
解釋以下巨集的原理

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

先給個用法:

struct task_struct *ts = container_of(p, struct task_struct, children);

看起來很複雜，總之先一步步拆解

__extension__

翻閱 gcc 文件中的 Alternative Keywords 提到

You can prevent such warnings within one expression by writing __extension__ before the expression. __extension__ has no effect aside from this.

看來是為了 surpress 可能的警告訊息，不過有趣的是翻閱目前的 linux kernel v5.0-rc8 版本中，所有的 container_of 定義都沒有用到這個 gcc 擴展。

__typeof__

一樣在 gcc 文件中的 Alternative Keywords 可以得知__是為了相容性考量而加的，作用和 keyword typeof 相同，在 Typeof 章節中可以得知 typeof 是用來獲取變數的型別。

((type *) 0)->member

照理來說 NULL pointer dereference 應該會出錯，不過在這裡的寫法行得通的原因我認為是使用了 typeof 的緣故，Typeof 章節中提到參數只有在特殊情況下(type 在編譯時期無法確定)才會被 evaluate。

The operand of typeof is evaluated for its side effects if and only if it is an expression of variably modified type or the name of such a type.

offsetof

給出 macro 定義

#define offsetof(type, member) ((size_t) &((type *)0)->member)

這裡的 &((TYPE *)0)->MEMBER 並不是求值後取地址，struct 中的成員變數地址是相對於 struct 的初始地址的，並且編譯時期就可以確定也就沒必要在運行時求值了，所以在此得到的是 0 + offset of MEMBER in struct

{}

第一次看到時覺得很奇怪，這 macro 到底要怎麼 return(廣義上的) 結果阿?
gcc docs 的 Statement-Exprs 章節中提到，這被稱為 compound statement 且回傳值是最後一個 expression 的結果

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.)

拼湊起來

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

首先宣告一個和 member 型別相同的指標 __pmember = ptr，將他扣除 member 在 type 中的 offset，回傳上述的值。

疑問

總覺得中間那行有些多此一舉，畢竟一開始就有 ptr 了，最後操作前也會被轉型成 char *

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        (type *) ((char *) ptr - offsetof(type, member));          \
    })

結果寫完才發現 list.h 裡面有這個版本，一個想法是支援 typeof extension 的話就可以在編譯時檢查型別，進而避免一些錯誤。

除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？

LIST_POISONING 這樣的設計有何意義？

這是資安上的考量，list_del() 的上方的註解敘述中提到這是為了防止 node 被移除後 next/prev pointer 仍被拿來使用的情況，以資安術語來說就是防止 UAF (Use-After-Free)，也降低 memory address leak 的可能。

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.

在 Google 開發的 javascript 引擎 V8 中也可以看到類似的做法。

額外補充

提到 linked list 跟資訊安全，當然就要拿出 glibc 來參考XD

glibc 是以 C 語言撰寫的通用函式庫，平常寫 C 程式在最上面 #include <stdio.h> 就是引入了 glibc，其中 malloc.c 當中多是用於管理動態配置記憶體的相關函式。
這裡稍微簡介一下 malloc.c 中的動態記憶體管理方式:

malloc.c 實作中 chunk 是 malloc/free 操作的基本單元，除了 user 要求的 size 以外，還會多配置一些空間用於儲存 metadata 如大小, 配置的方式…等

free 時會將不同大小的 chunk 放入各自的 linked list (也就是 bins) 中由 glibc 負責維護，下一次 malloc 時若是有大小相同的 chunk 就可以直接將其 return 給 user。

為了防止許多在操作 linked list 時可能出現的安全漏洞，例如上述的 UAF 情形下，其用來移除 chunk 所使用的 function unlink_chunk() 就加上不少檢查，例如以下就是檢查要被從 list 中刪除的節點 p，它的 prev->next, next->prev 是否都等於自己

  mchunkptr fd = p->fd;
  mchunkptr bk = p->bk;
  ...
  if (__builtin_expect (fd->bk != p || bk->fd != p, 0))
    malloc_printerr ("corrupted double-linked list");

當然也會有方式繞過這些檢查，有興趣的人可以自行 Google 關鍵字 heap exploit XD

linked list 採用雙向環狀是基於哪些考量？

採用環狀 linked list 的優勢在於…我不知道 (繼續思考)

雙向 linked list 可以讓多個相同結構的 linked list 中的任一節點移除操作只需要藉由一個指標即可完成，時間複雜度

$O(1)$，且不需要知道需要移除的節點在哪一個 linked list 上。

什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現

/lib/list_sort.c 中的 list_sort

什麼情境會需要找到 第 k 大/小元素 呢？又，你打算如何實作？

list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？

for_each 風格的開發方式對程式開發者的影響為何？
提示：對照其他程式語言，如 Perl 和 Python

程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
提示: 對照看 Doxygen

tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？

tests/ 目錄的 unit test 可如何持續精進和改善呢？