2019q1 Homework1 (list)

contributed by < cjwind >

自我檢查清單

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

macro 會在 preprocess 階段被處理。其中 #define name replacement 會在 preprocess 時將程式碼中的 name 都取代為 replacement。指令 cpp 是 C preprocessor。

一般的 function call 需要 push 參數、local variable、return address 等資料到 stack，並且跳到該 function 執行，執行完 function 要再跳回 caller。

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

這類註解可以用相關工具如 Doxygen 自動產生程式碼的文件。

@ 代表 function parameter。Ref

Linux kernel 用 Sphinx 產生文件。

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

list_for_each 註解提到 list 的 node 以及 head 在 iterate 過程中不能修改，否則會導致 undefined behavior。

list_for_each_safe 註解提到在 iterate 過程中可以 delete current node（iterator 所在的那個 node），其他對 list 的修改會造成 undefined behavior。

實作上，這個 doubly linked list 是 circular，而且 head 是不含資料的 node，所以可以把 head 當作 traverse 的終點。

從 tests/list_for_each.c 可以看到兩者的使用方式。差異在 safe 版本可以在 traverse 過程中 delete current node。

for_each 風格的開發方式對程式開發者的影響為何？

可以不用管底層是如何實作就能 traverse，例如 PHP 的 foreach 可以 traverse array 跟 object public attribute。

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

用來確認 list 的各項功能操作是否符合預期。

unit test 是用來確認一個「unit」（可以是 function 或 class 或更大的 module 等）的功能是否符合預期的測試，也可以當作程式碼的使用說明──test 怎麼用，production code 就怎麼用。

軟體開發上，有 unit test 可以確保對程式碼的修改沒有造成原本功能壞掉或製造出 bug（在 test 涵蓋到的範圍內）。一般 unit test 都能一鍵執行，開發人員可以快速知道寫的功能是否符合預期、有沒有改壞東西，縮短開發、測試以及 debug 需要的時間。能快速取得回饋以及得知有無改壞原有功能，對 refactor 有很大幫助。

LIST_POISONING 這樣的設計有何意義？

在 list_del() 裡讓從 list 移除的 node 的 prev 及 next 指向特定 address。從註解看起來，應該是有些系統會定義某些 address 有特定功能，例如 access 某個 address 是非法操作之類的？如果程式去 access 這樣的 address 系統會有對應處理？

這樣做可以避免被移除的 node 依然透過 prev 跟 next 操作 list 中的 node（指向 NULL 也能避免），不過註解也有提到移除的 node 要被當作 uninitialized node，access prev 跟 next 是不安全的。

list_del_init() 則是 list_del() 後再次 initialize node，讓 prev 跟 next 都指向自己。

為什麼不只提供 list_del_init() 就好？要保留會讓 node 處於 uninitialized state 的 list_del()？

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

在 tests/common.h 增加 macro assert_equal()，改進原本 assert(a == b) 的可讀性。

#define assert_equal(expected, actual) assert(expected == actual)

例如檢查 sort 結果的 assert

assert(item->i == values[i]);

可以改寫為

assert_equal(values[i], item->i);

原本想用 function 實作：

void assert_equal(uint16_t expected, uint16_t actual)
{
    assert(expected == actual);
}

但發現這樣做在 assert fail 時印出的訊息會像下面變成印出 common.h 那行，反而不利閱讀。

list_mergesort: tests/common.h:8: assert_equal: Assertion `expected == actual' failed.

用 macro 跟原本一樣會印出比較確切的資訊：

list_mergesort: tests/list_mergesort.c:35: main: Assertion `values[i] == item->i + 1' failed.

Sorting

可先解析 example 目錄下的 insert/quick sort 程式碼

jserv

範例 insertion 跟 sort sort 的 main() 都是先準備 input 資料、做 sort、最後確認 sorting 結果。

Insertion sort

list_insertsort() 把原本 list head 的 node 先放到 list_unsorted，接著一個個從 list_unsorted 拿 item、call list_insert_sorted() 放到 head list 的對應位置。

list_insert_sorted(entry, head) traverse head list，進行比較，找到對應位置時用 list_add_tail() 把 entry 放到找到位置的 item 前面。

list_add_tail() 更 general 來說是「把 node 放到某個 node 前面」。

example 的實作下，worst case 是 sorted list 而非反向的 sorted list。

Quick sort

建立兩個 list list_less 跟 list_greater，分別放小於 pivot 的 item 跟大於等於 pivot 的 item。

拿 head list 的第一個 item 當 pivot，並且將 pivot item 從 head list 移除。

traverse head list 的 entry，比較 enty 與 pivot，使用 list_move_tail() 及 list_move() 將 entry 分別移到 list_less 跟 list_greater。traverse 結束後，head list 會變成 empty。

recursive 對 list_less 及 list_greater 做排序，之後兩者皆為 sorted。

最後先把 pivot 放回 head list。接著將 list_less 所有 node 接到 head list 前面，所以 pivot 會在所有小於它的 item 後面。再把 list_greater 所有 node 接到 head list 的後面，也就是 pivot 後面，完成排序。

效能

三種 sort 的 time complexity：

	Insertion	Quick	Merge
Avg	$\mathrm{\Theta }(n^2)$	$\mathrm{\Theta }(nlogn)$	$\mathrm{\Theta }(nlogn)$
Worst	$O(n^2)$	$O(n^2)$	$O(nlogn)$

測量方式

以 gettimeofday() 取得執行 sort 前後的時間計算各 sort 所需時間。

struct timeval stop, start;
gettimeofday(&start, NULL);
sort(list);
gettimeofday(&stop, NULL);

average case 以相同 random data 作為 input 執行三種 sort。

worst case 則以反向 sorted data 作為 input。insertion sort 最簡單的 worst case 是反向的 sorted data (Wiki)，但以 example 的實作而言是已經排好的 sorted data。

測量結果

Insertion Sort 的 average case 與 worst case：

Quick Sort 的 average case 與 worst case：

Merge Sort 的 average case 與 worst case：

merge sort 的 worst case 效能比 average case 好，顯然反向 sorted data 不是 merge sort 的 worst case。

三種 sort 的 average case 與 worst case：

quick sort 及 merge sort 在 average case 差不多，而 insertion sort 明顯比較差。但到了 worst case，反而是 quick sort 所需時間的增長較多。

Improve Quick Sort

example 的 quick sort 挑 pivot 都挑 list 的第一個 item，在 sorted data 的情況會挑到最大或最小的，導致在分成「比 pivot 大」跟「比 pivot 小」兩堆時 item 都在某一堆、沒有分堆的作用。

如果修改成從第一個 item、最後一個 item、中間 item 三個中選中間值的 item 當作 pivot，可以避免總是挑到最大或最小的 item 當 pivot。如此修改後，再以反向 sorted data （sequential input）以及 random data 當作 input 的結果如下：

可以看到 sequential input 的 performance 變好，random input 也跟之前差不多。

只看 merge sort 跟改進後 quick sort，兩者變得接近：

當然，對於修改後的 quick sort，sequential data 已經不是它的 worst case，反而是相對好的 case，因為選中間 item 會選到可以將 item 分成差不多大小兩邊的 pivot。如果不幸三個 item 正好是最大、次大、第三大的 item（最小亦然），效能提升便不顯著。

Trace Note

list 使用上先 initialize 一個 type 為 struct list_head 的 head node，它不含資料。list 的各項操作都會使用這個 head node。

封裝：自訂 struct 放資料及 struct list_head，如 struct listitem，就可以讓自訂的 struct 成為 list node。

list splice 系列

void list_splice(struct list_head *list, struct list_head *head)

list 跟 head 分別是兩個 list 的 head。

list_splice() 把 list 的所有 node 接到 head 的最前面，但是 list 這個 node 不會被修改、會變成 uninitialized node。

list_splice_init() 先做了 list_splice() 再 initialize list node。

list_splice_tail() 是把 list 的 node 接到 head 的最後面。

list_cut_position

head_to 如果不是空的 list，cut 完原本 head_to list 裡的 node 會沒有 head。test 也沒有這種用法。

作業要求

• Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
• GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
• 解釋以下巨集的原理

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

• 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
• linked list 採用環狀是基於哪些考量？
• 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
• 什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？
• 從 linux-list 學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，實作出 merge sort
  • 附上你的修改過程，也需要讓 qtest 得以支援
  • 可將 dict 裡頭的測試資料拿來作效能分析的輸入
  • 思考提升排序效率的方法，需要做平均和最壞狀況的分析

tags: Linux 核心設計 2019