# 2018q3 Homework3 (list)
contributed by < [`letticee`](https://github.com/letticee) >

- [ ] 自我檢查事項:

* 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* 若在程式中使用到多次 macro ，在進行編譯前，前置處理器會進行取代的動作，因此較費時一點
* 呼叫函式在執行時，必須跳到函式所在處，待執行完再返回原呼叫處的下一個敘述，花時間在 stack 的 pop 和 push
* macro 執行時間較快，但程式空間加長

* Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
1. [linux/mm/page_alloc.c](https://github.com/torvalds/linux/blob/bab5c80b211035739997ebd361a679fa85b39465/mm/page_alloc.c#L2789)

        /*
         * Free a list of 0-order pages
         */
        void free_unref_page_list(struct list_head *list)
        {
            struct page *page, *next;
            unsigned long flags, pfn;
            int batch_count = 0;

            /* Prepare pages for freeing */
            list_for_each_entry_safe(page, next, list, lru) {
                pfn = page_to_pfn(page);
                if (!free_unref_page_prepare(page, pfn))
                    list_del(&page->lru);
                set_page_private(page, pfn);
            }

            local_irq_save(flags);
            list_for_each_entry_safe(page, next, list, lru) {
                unsigned long pfn = page_private(page);

                set_page_private(page, 0);
                trace_mm_page_free_batched(page);
                free_unref_page_commit(page, pfn);

                /*
                 * Guard against excessive IRQ disabled times when we get
                 * a large list of pages to free.
                 */
                if (++batch_count == SWAP_CLUSTER_MAX) {
                    local_irq_restore(flags);
                    batch_count = 0;
                    local_irq_save(flags);
                }
            }
            local_irq_restore(flags);
        }

* 0-order pages ([Allocating Pages](https://www.kernel.org/doc/gorman/html/understand/understand009.html#tab:%20Physical%20Pages%20Allocation%20API))
* 只有單個(2^0) page
* 這個函式用來 free 掉一串的 page，這串 page 是以一個 list 儲存
2. 123
3. 233

* GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* 當程式可接收多種型態的資料時，typeof 可以用來取得變數的型態
* typeof 的參數可以是兩種形式
* an expression
* typeof (a)
* a type
* typeof (int *)
* e.g. typeof (*x) y;
將 y 宣告為 x 指到的型態

* 解釋以下巨集的原理

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

* 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
* `list.h` 中還定義了以下的操作：
* 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_splice_tail_init：把一個 list 的所有節點移到另一個 list 結尾，並且把第一個 list 的 head 做 INIT_LIST_HEAD
* list_cut_position：將一個 list 的開頭的一部分節點移到另一個 list
* list_move：把一個指定的節點移到 list 的開頭
* list_move_tail：把一個指定的節點移到 list 的尾端

* `LIST_POISONING` 這樣的設計有何意義？
* linked list 採用環狀是基於哪些考量？
*
* `list_for_each_safe` 和 `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)

* `list_for_each`

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

* for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
* 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
* `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* `tests/` 目錄的 unit test 可如何持續精進和改善呢？