###### tags: `linux2019`

# 2019q1 Homework1 (list)
contributed by < `ambersun1234` >

## 環境

$ uname -a
Linux 4.15.0-45-generic #48~16.04.1-Ubuntu SMP Tue Jan 29 18:03:48 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc -v
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.11)

## 說明
+ [作業說明](https://hackmd.io/s/S12jCWKHN)

## Sorting algorithm:
+ 在 GitHub 上 fork [linux-list](https://github.com/sysprog21/linux-list) 並學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，進而實作出 merge sort
+ 附上你的修改過程，也需要讓 `qtest` 得以支援
+ 可將 [dict](https://hackmd.io/s/B1Bq5Jat7) 裡頭的測試資料拿來作效能分析的輸入
+ 思考提升排序效率的方法，需要做平均和最壞狀況的分析
+ 排序演算法 時間複雜度
|Case|Insertion sort|Quick sort|Merge sort|
|--|--|--|--|
|Average case|$O(n^2)$|$O(nlogn)$|$O(nlogn)$|
|Worst case|$O(n^2)$|$O(n^2)$|$O(nlogn)$|
### Average case 實驗
+ `make averagePlot`
+ 
+ 其實可以發現，quick sort 以及 merge sort 在 average case 的表現下並不會差太多
### Worst case 實驗
+ `make worstPlot`
+ 
+ 值得一提的是，當我在跑 worst case 的測試時，會出現 `segmentation fault`。後來在追蹤時發現到是在 quick sort 60000 的時候發生；結果是因為 stack size 不夠大所導致，使用 `ulimit -s 65536` 更改 stack size 即可解決

## 自我檢查事項:

### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
+ macro 是在編譯階段進行展開的，根據 `man gcc` 裡面的提到
> `-E` Stop after the preprocessing stage;
> do not run the compiler proper.
> The output is in the form of preprocessed source code,
> which is sent to the standard output.

在 compile 的時候加上 -E 這個參數即可以觀察到展開巨集之後的程式碼，就可以發現到說 macro 全部被展開到程式碼裡面( 我覺得是類似 find and replace )
+ function call 編譯完成後並不會像 macro 一樣全部展開到程式碼之中，而是在記憶體中實際佔有空間的。在演算中有學到 , 每次的 function call 都是要對 stack 進行 push pop 的，而這樣的操作是很耗時間的
+ 綜合以上， macro 不會發生 function call 的 push pop 的操作，可以減少時間成本，但相對的，由於是展開巨集，所以會造成空間的浪費
+ 那 linux 會採用 macro 實做 linked list 我想很大的原因是要避免 stack 的 push pop 造成多消耗時間
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
#### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
+ 先上程式碼

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

`typeof` 是 gnu c extension，它可以取得參數的型態，比如說

    int a;
    typeof(a) b;

則上述第二行會變成 `int b;`，typeof 會返回參數的類型，a 為 int 型態，因此 typeof(a) 會變成 int
上述 max 的 macro 即是可以針對各種型態的數字進行比較，傳回較大者，需要注意的是，實際上在用 typeof 的時候必須要寫成 \_\_typeof\_\_ 才可以編譯成功
### 解釋以下巨集的原理

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

+ 在解釋 container_of 之前必須要先看 offsetof
>[offsetof macro](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/include/linux/stddef.h)

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

+ offsetof 的 macro 是定義在 include/linux/stddef.h 中，其功用為計算 struct 成員在 struct 中的偏移量。
+ 在 offsetof 的 macro 中，它會把 0 強制轉型至 TYPE 指標型態，以此為 TYPE 的起始位置，得到 MEMBER 的位置，由於 0 視為該 TYPE 的起點，因此就會得到 MEMBER 在 TYPE 中的偏移量。考慮以下程式碼:

    #include <stdio.h>

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

    typedef struct mdata {
        int a, b, c;
        char *hello; 
        struct mdata *next;
    } data;

    int main() {
        printf("-- a = %d --\n", offsetof(data, a));
        printf("-- b = %d --\n", offsetof(data, b));
        printf("-- c = %d --\n", offsetof(data, c));
        printf("-- hello = %d --\n", offsetof(data, hello));
        printf("-- next = %d --\n", offsetof(data, next));

        return 0;
    }

其輸出結果為

    -- a = 0 --
    -- b = 4 --
    -- c = 8 --
    -- hello = 16 --
    -- next = 24 --

a 的偏移量是 0，因為他是該 TYPE 的起點，b 跟 c 的偏移量分別是 4, 8(int 大小為 4 byte)，hello 的偏移量為 16(char * 的大小為 8 byte, 位置 12 無法被 8 整除，所以要新增 padding 變成 16)
> [struct alignment](https://stackoverflow.com/questions/4306186/structure-padding-and-packing)
+ 回到 container_of
> [reference container_of](https://adrianhuang.blogspot.com/2010/01/linux-kernel-containerof.html)

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

+ \_\_extension\_\_
> GCC uses the __extension__ attribute when using the -ansi flag to avoid warnings in headers with GCC extensions. This is mostly used in glibc with function declartions using long long
+ 它宣告了一個型態為 `((type *)0)->member` 的指標變數 `__pmember` 並將 `ptr` 指派給 `__pmember`
+ 再將 \_\_pmember 扣掉 member 的偏移量，即可得到該 TYPE 的位置

### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
+ [linux/list.h](https://github.com/torvalds/linux/blob/2c45e7fbc962be1b03f2c2af817a76f5ba810af2/include/linux/list.h)
+ 多人開發時，為避免重造輪子，於是團隊開發出一系列 API 提供團隊自己使用。
### `LIST_POISONING` 這樣的設計有何意義？
+ `LIST_POISONING` 一系列定義於 [linux/poison.h](https://github.com/torvalds/linux/blob/master/include/linux/poison.h) 中。該檔案定義了許多的 magic number ，這些 magic number 被用在許多的地方 e.g. mm, arch, drivers, kernel 等。我有找到一篇 [what is the meaning of 0xdead000000000000?](https://stackoverflow.com/questions/27801360/what-is-the-meaning-of-0xdead000000000000/27806246) 是在探討這些 magic number 的設計考量點。
+ 對於非法的 linked list 節點，一般的作法是將其設為 NULL；在龐大的系統中，一定不只有一個 linked list，如果要對其進行除錯的時候，會變得相對困難，因為全部都是 NULL；而有了 `LIST_POISONING`，可以很快速的辨別是哪裡出錯
### linked list 採用環狀是基於哪些考量？
+ circular linked list 在結構上是屬於環狀的，也就是說它沒有一個特定的頭尾，相比 singly 或 doubly linked list，circular 的結構較為單純；在實做上，可以不用考慮一些 corner case 比如刪掉頭或刪掉尾巴，circular 僅須考慮 linked list 是否沒有連接上的問題
### 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
+ 作業系統實做上一定會面臨到排程問題，電腦上的任務也會時常進行刪減，所以是以 linked list 進行實做；排程工作又會面臨到執行先後順序的問題，因此排程也會需要進行排序的工作
### 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？

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

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

+ safe 的版本相較於普通的 for_each 來說，最大的不同就是增加一個變數 `safe`，去紀錄當前 node 的下一個。直播中有提到，如果 head 不見了，那麼就會出錯，由於 linux kernel 的 linked list 是屬於 `circular` ，當 head 在執行的時候被刪除了，safe 這個變數可以先將 head 的下一個保存起來，確保執行順利
> [reference 你所不知道的 C 語言：linked list 和非連續記憶體操作 1:19:00](https://www.youtube.com/watch?v=0B0GNPv02zg&t=2404s)
### for_each 風格的開發方式對程式開發者的影響為何？
+ 提示：對照其他程式語言，如 Perl 和 Python
+ 一般而言，如果要針對特定資料型態(e.g. binary tree，linked list)進行走訪，在程式上就必須要了解資料底層如何實做，才能寫出走訪。
+ 在一些程式語言，如 python, c++ 都有提供 foreach 可以使用。對於特殊資料型態，都不需要對走訪的程式碼進行變動，很大的一個原因是他們都是 ADT(Abstract Data Type, 抽象資料型態)；我們可以不用考慮資料底層的實做方式，進而實現資料封裝。
### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
+ 提示: 對照看 Doxygen
+ `Doxygen` 是一個可以將程式裡的特定註解轉換成 Document 的產生工具
+ `@` 是告訴 Doxygen 說這一行要轉換成為 Document，比方說
+ @param a description
+ @param b description
+ @return return a + b
+ 在開發的過程中可以將註解與開發文件整合，我覺得是一個不錯的功能，在未來的開發過程中，我會試著將這一個工具實際應用在專案上面
> [Doxygen 簡介 reference](https://blog.xuite.net/jesonchung/scienceview/93545213-%E7%B0%A1%E4%BB%8BDoxygen)
### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
+ unit test , 單元測試。測試是為軟體工程中相當重要的一個環節，它可以確保程式的行為是符合預期的，確保程式碼的品質。單元測試是針對程式中的最小單元，也就是 function 進行測試，通過了單元測試即表示該 function 的行為是合理的。
+ 實務上軟體開發，每天都會收到各種的更新提交，程式碼的把關是每個團隊需要面對的事情，現在已經有很多服務可以整合測試這件事情，像是 travis-ci 與 jenkins 都有與 github 進行整合，在 push 之後立刻啟動相關測試，如此一來，可以節省許多在驗證程式碼的人力的這個部份
### `tests/` 目錄的 unit test 可如何持續精進和改善呢？