# 2018q3 Homework3 (list)

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

## 自我檢查清單

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

* 參考 [Macro vs Function in C](https://stackoverflow.com/questions/9104568/macro-vs-function-in-c) ：

* Macro：在 pre-process 時會將 macro 直接展開取代掉原程式碼，因此執行時不需要 function call 的時間，但多次呼叫時比起 function 會佔用更多記憶體空間，通常適合簡短且頻繁出現的函式。

* Function：在執行時需要將目前位址存入 stack，再跳躍到 function 所在的記憶體處，因此速度較慢，但因為在記憶體中 function 只會存在一個地方，如果多次呼叫的話比起 macro 可以節省許多空間，適合用在較長的函式。

* 因為 linked list 的函式大多簡短且頻繁使用，因此才會選擇使用 macro，犧牲掉一些記憶體空間來加快執行速度。

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

* [Linux kernel 排程機制](https://tampub.uta.fi/bitstream/handle/10024/96864/GRADU-1428493916.pdf)

* 以下為部份 runqueue 的資料結構，其中第 19 行便是使用到 list.h 中定義的 circular doubly linked list

        #define MAX_USER_RT_PRIO 100
        #define MAX_RT_PRIO (MAX_USER_RT_PRIO + 1)
        #define ISO_PRIO (MAX_RT_PRIO)
        #define NORMAL_PRIO (MAX_RT_PRIO + 1)
        #define IDLE_PRIO (MAX_RT_PRIO + 2)
        #define PRIO_LIMIT ((IDLE_PRIO) + 1)
        /* There can be only one */
        static struct global_rq grq;
        /*
        * The global runqueue data that all CPUs work off. Data is protected
        * either by the global grq lock, or the discrete lock that precedes the
        * data in this struct.
        */
        struct global_rq {
             raw_spinlock_t lock;
             unsigned long nr_running;
             unsigned long nr_uninterruptible;
             …
             struct list_head queue[PRIO_LIMIT];
             DECLARE_BITMAP(prio_bitmap, PRIO_LIMIT + 1);
             u64 niffies; /* Nanosecond jiffies */
        }

* GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？

* 可以宣告一個與其他變數相同資料型態的變數，例如：

        int a;
        typeof（a) b;

* 可以使函式依據傳入變數的 type 的不同而產生不同的行為，以下列 `max()` 函式為例：

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

* 解釋以下巨集的原理

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

* 根據 [Alternate Keywords](https://gcc.gnu.org/onlinedocs/gcc-3.0.1/gcc_5.html#SEC109)，某些 [GNU C extensions](https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html) 的關鍵字會因為編譯參數 `-traditional`、`-ansi`、`-std=c99` 等而失效，解決的方法是可以如上方的程式碼一樣，在關鍵字的前後加上 `__`，變成 `__extension__` 和 `__extension__`。

* `container_of()` 這個 macro 的功能是當我們只知道一個結構中某成員的位址時，即可透過這個 macro 得到這個結構的起始位址。

* 輸入的三個參數中，`ptr` 表示某個成員的位址，`type` 為成員所屬的結構，`member` 則是成員的名稱。

* 在函式中首先使用 `((type *) 0)->member` 表示一個位址在 `0` 的 `type` 結構中，名稱為 `member` 的成員，主要目的是使用 `__typeof__` 函數來取得那個成員的資料型態，並且宣告一個指向同資料型態的指標 `__pmember` 並指向 `ptr`。

* 根據 [Linux Programmer's Manual](http://man7.org/linux/man-pages/man3/offsetof.3.html)， `offsetof(type, member)` 可以回傳某個成員 `member` 與 `type` 結構的起始位址間的 offset。

* 接下來會將 `__pmember` 轉型為 `char *`，並減掉藉由 `offsetof()` 求得的 offset，來取得結構的起始位址，並轉型為指向結構的指標 `type *`。

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

* `list.h` 中還定義了以下的操作：

* LIST_HEAD：宣告一個 list 並初始化
* INIT_LIST_HEAD：初始化一個空的 list
* list_add_tail：在 list 的尾端插入新節點
* list_del_init：刪除節點並將其初始化，可以避免之後錯誤的操作
* list_empty：回傳 list 是否是空的
* list_is_singular：回傳是否只有一個節點
* list_splice：把一個 list 的所有節點插入到另一個 list 開頭
* list_splice_tail：把一個 list 的所有節點插入到另一個 list 結尾
* list_splice_init：把一個 list 的所有節點插入到另一個 list 開頭，並且把第一個 list 的 head 做 INIT_LIST_HEAD
* list_cut_position：將一個 list 的開頭移到另一個 list
* list_move：把一個指定的節點移到 list 的開頭
* list_move_tail：把一個指定的節點移到 list 的尾端

* 許多操作都有針對頭尾的兩種不同版本，可以使 list 在使用上更為便利且有效率。

* `LIST_POISONING` 這樣的設計有何意義？

* list.h 中的 `list_del()` 有這段註解及操作：

        /**
         * 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.
         */

        #ifdef LIST_POISONING
            node->prev = (struct list_head *) (0x00100100);
            node->next = (struct list_head *) (0x00200200);
        #endif

* 因為在執行 `list_del()` 時，節點只是從 list 上被移掉，並不是真的被刪除，因此當 `LIST_POISONING` 被定義的時候，會將被移掉節點的 `prev` 和 `next` 指向預先定義的位址，以避免非法的存取。

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

* 環狀 linked list 的優勢主要就是不需要特別記錄及處理尾端的指標，使得在操作上更為容易，搭配上 doubly linked list 的話，可以允許從 linked list 上任意節點朝任意方向 traverse 整個 list，增加了許多使用上的彈性與效率。

* [參考資料](https://www.quora.com/Why-are-all-the-linked-lists-circular-in-the-Linux-Kernel)

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

* 最主要的差異是在 `list_for_each_safe` 中多使用了一個指標 `safe` 指向目前 `node` 所指向的節點的下一個節點。

* 在 `list_for_each_safe` 的執行時期中，`node` 所指向的節點在是可以被移除的，因為會有 `safe` 保存下一個節點的位址，而不會產生未定義行為。

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

* Perl 中的 for 迴圈：

        foreach $a (@list) {
            print "$a\n";
        }

* Python 中的 for 迴圈：

        for a in list:
            print(a)

* for_each 風格的開發方式可以使程式碼變得更為簡潔，可讀性也較高。

* 在 C 語言 for 迴圈的寫法中，可以自訂變數的初始動作、條件、以及每次迴圈後的操作，這使它的彈性比較大，但寫法也顯得較為複雜，較不具可讀性。

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

* [Doxygen](https://en.wikipedia.org/wiki/Doxygen) 是一個可以抓取程式的內容與註解，來自動產生說明文件的工具。

* Doxygen 有定義了許多[指令](http://www.stack.nl/~dimitri/doxygen/manual/commands.html)來幫助生成說明文件，而 `@` 或 `\` 就是用來表示指令的開頭，例如 `＠brief` 可以用於 function 的簡易說明，`＠return` 則可以用來說明函數的回傳值。

* 使用 Doxygen 生成的 list.h 的說明文件：


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

* tests/ 中有許多用來測試的檔案，用來檢驗 list.h 中的 macro 是否正確運作，如果運作失敗或結果不符合預期會被 `assert()` 擋下來。

* 根據[維基百科](https://en.wikipedia.org/wiki/Unit_testing)的解釋， unit test 指的是隔離程式各個部份的實做，並測試這些小部份函式或程式碼是否可以正確執行，目的是為了快速定位並修復錯誤，並使得在軟體開發過程的早期就確保程式碼的正確性。