2019q1 Homework1 (list)

contributed by < zodf0055980 >

tags: Linux 核心設計

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

Macro 在編譯之前，preprocessor 把有利用到 Macro 的地方做替換，所以相同的程式碼會重複出現在程式各個地方，使的程式的 code section 空間較大，但再執行時間並不需要做函式的切換，可以減少執行時間。
而 function 使用透過執行時期利用 stack 做函式的切換，而因為使用相同的函式都會對應相同的位置，因此空間的需求較小，但也因此造成有程式做切換的時間成本。而另一個好處是能利用函式位址把函式當參數。
而 Linux 有很多利用 linked list 的基本操作，因此為了效能， Linux使用 macro。

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

3. GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色

typeof() 用來回傳輸入變數的 type，在一些常用的 function 或是 macro 中，可以利用 typeof() 使我們可以不需要為了因為不同的 type 而需要另外寫一個 function 或 macro。
例如:

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

便可以利用 type 讓 max 能比較多種 type 的變數。

4. 解釋以下巨集的原理

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

參考這篇文章的說明，如果我們只知道只知道 struct 其中一個 member 的位置，我們便能用 container_of() 找到該 struct 的起始位置。
而再往下拆解這個程式碼的意義:
extension 是用來告訴 GCC 不要產生警告。
再利用

__typeof__(((type *) 0)->member) 

去取得 member 的 type 並建立一 pointer pmember 指向 ptr。
再利用 offsetof() 這個 macro 取得 struct 的成員相對於該結構起始位址的偏移量( offset )。因此只要把 pmember 減去偏移量 即可知道該 struct 的起始位置。
而 offsetof 的 macro 如下:

#define offsetof(TYPE, MEMBER)  ((size_t)&((TYPE *)0)->MEMBER)

先把 0 強制轉型成 TYPE 型別的指標，所以 TYPE的起始位置為 0X0 ，再指向該 member ((TYPE *)0)->MEMBER ，因為起始位置為 0 ，因此指向 member 所得的位置就是偏移量了。

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

去查查 list.h 有寫到:

/*
 * Simple doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */

當我們已經知道 next/prev entries，便可以利用他去產生更好的程式碼，而非使用 generic single-entry routines。

6. LIST_POISONING這樣的設計有何意義

在 list.h 可以發現:

static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

當做 list 移除時，會把 prev/next 指向特殊的位置。
因此再到 poison.h 查詢，可發現:

/*
 * These are non-NULL pointers that will result in page faults
 * under normal circumstances, used to verify that nobody uses
 * non-initialized list entries.
 */
#define LIST_POISON1  ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x200 + POISON_POINTER_DELTA)

利用 LIST_POISON1、LIST_POISON2 讓沒有初始化或已刪除得節點變得不可訪問，如果存取到 LIST_POISON1、LIST_POISON2 這兩個位置，會產生 page faults。

7. linked list 採用環狀是基於哪些考量？

在 list.h 中可知 linux 使用 Circular double-linked list，放便資料做各種存取，沒有 head 和 tail 的區別。而 Circular double-linked list 在 merge 兩個不同的 list 比 沒有環狀得 list 方便且快速。

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

linux 排班 由 linked list 做各個工作的排班，在以前 OS 課程所學到的 Multilevel Queue、SRTF 等，都需要對 linked list 做排序，以方便找到優先權高得工作作執行。

列出 Linux 或其他真實存在的程式碼 (當然要是開放原始碼的實作)，分析並探討

jserv

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

我如果給定一個尚未排序的資料，我會想要利用 quickselect 演算法去找第 k 大/小元素

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

在老師的影片有提到，在 list_for_each 我們可以進行各種操作，也包含刪除節點。如果我們刪除 pos 節點，在list_for_each 中如果刪除 pos，會使 pos = pos->next 出錯，因此 list_for_each_safe 使用 n 去儲存下下個節點的資料，pos = n, n = pos->next，以防錯誤。

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

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

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

Doxygen 是一個document generator，可以將程式中的註解轉換成為說明文件。如果在寫註解的時候能依據某種格式，接著就可以透過document generator產生出漂亮的文件。這也是為什麼看 linux 程式註解都按照一定的標準的緣故。
而使用 @parameter：parameter 的說明，方便其他使用者作查詢。

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

對一個個函式作測試，藉由自動化測試方便檢驗程式是否有問題。
藉由一個個函式檢驗，可以避免由於函式錯誤而造成的程式錯誤導致能以找到程式出錯的地方。

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