2019q3 Homework3 (list)

contributed by < uccuser159 >

自我檢查清單

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

使用 macro 可以在程式被編譯前就先處理定義的函式或數值，例如：

#define POWER(x) (x)*(x)*(x) 

• 使用 macro 會占用較多的記憶體，但程式的控制權不用轉移(即不需要 stack 的push 或 pop)，所以程式執行速度較快，有儲存空間的成本。
• 使用 function call 會占用較少的記憶體，但程式的控制權需要轉移(即需要 stack 的push 或 pop)，所以程式執行速度較慢，有執行時間的成本。

因為 linked list 要用到很多函式來執行一個 task ，所以適合使用 macro 來定義函式來增加執行效率。

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

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

gcc manual [6.7] 提到 Another way to refer to the type of an expression is with typeof

typeof 會參考表示式的型態，其宣告方式有兩種：

• With an expression
  typeof (x[0](1))
  假設 x 為陣列透過指標的方式傳入function中，則得到 function 回傳值的 type

• With a type
  typeof (int *)
  得到的 type 是 pointers to int

因為macro本身沒辦法做型態檢查，只是單純的將值帶入並展開，使用 typeof 的話可以讓 macro 在不同 type 的變數皆可以使用，會變得更有彈性。

• 解釋以下巨集的原理

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

container_of可以在 struct 中只知道某一 struct 成員的位址的情況下，抓出此 struct 的起始位址。例如：

/* The student structure definition */
typedef struct student {
     char name[16];
     int id;
     char addr[64];
     char phone_num[16];
}STUDENT, *STUDENT_PTR;

根據上面的 struct ，若我們知道的是某個 student 的 phone_num，要找出此為 student 和 id ，就可以使用container_of：

void print_id (char *phone){
    STUDENT_PTR someone = NULL;    
    someone = container_of(phone,struct student,phone_num);
    return;
}

在 print_id 函式中， phone 即為某學生的電話，而container_of做了以下這些事：

(type *) 0)->member：
將 0 轉成指向 "student" 這個 struct 型態的 pointer，並將 poniter 指向 phone_num

__typeof__(((type *) 0)->member)：
取得 phone_num 的 type

__typeof__(((type *) 0)->member) *__pmember:
宣告一個型態為 phone_num 的指標 __pmember

__typeof__(((type *) 0)->member) *__pmember = (ptr):
__pmember 得到 phone 的位址

• offsetof 定義在 </include/linux/stddef.h> 中，用來計算某一個 struct 的成員相對於該結構起始位址的偏移量( offset )

offsetof(type, member)：
計算 struct 開頭到 phone_num 這個成員的偏移量

(type *) ((char *) __pmember - offsetof(type, member))
得到 struct 的起始位置，並轉成 "student" 這種 struct 型態

• Reference
  -Linux Kernel: container_of 巨集

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

list.h 內都是 macro 或是 static inline 的宣告，都可以降低時間複雜度，讓執行效能增加，且可以簡化程式設計，像一個功能塊，例如想要檢查一個 linked list 是否為空的，就可以使用list_empty，註解提到 Return: 0 - list is not empty !0 - list is empty

/**
 * list_empty() - Check if list head has no nodes attached
 * @head: pointer to the head of the list
 *
 * Return: 0 - list is not empty !0 - list is empty
 */
static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

• LIST_POISONING 這樣的設計有何意義？
  在list_del()中：

/**
 * list_del() - Remove a list node from the list
 * @node: pointer to the node
 *
 * The node is only removed from the list. Neither the memory of the removed
 * node nor the memory of the entry containing the node is free'd. The node
 * has to be handled like an uninitialized node. Accessing the next or prev
 * pointer of the node is not safe.
 *
 * Unlinked, initialized nodes are also uninitialized after 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.
 */
static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

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

表示當我們在刪除 linked list 的某個 node 時，因為此 node 只是脫離原本的 linked list，記憶體沒有被釋放掉，反而指向LIST_POISONING這個位址，用意為防止讓程式設計者在已被移除的 node 再被用來執行 linked list 相關操作。

• Linked list 採用環狀是基於哪些考量？

使用環狀 linked list 演算法較一般的 linked list 來的容易，彈性也較大，因為沒有第一個或是最後一個的問題，操作環狀 linked list 並不因為操作位置的不同而需要有不同的解決方法，例如list_del並不會因為 node 的位置不同，而有不同的操作。

• 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
• 什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？
• list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？

這兩個巨集都是走訪 linked list 用的，但是delete 這項操作只能在 list_for_each_safe 中：

/**
 * list_for_each_safe - iterate over list nodes and allow deletes
 * @node: list_head pointer used as iterator
 * @safe: list_head pointer used to store info for next entry in list
 * @head: pointer to the head of the list
 *
 * The current node (iterator) is allowed to be removed from the list. Any
 * other modifications to the the list will cause undefined behavior.
 */
#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_safe 會預先儲存當前 node 的下一個 node(safe node)，所以即使在當回的迴圈中將 node 才 linked list 中移除，也可以繼續走訪到下一個節點(safe node)

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

for_each 這種風格的開發方式就像目前深度學習工具 Keras 一樣，有許多的API 可供程式開發者使用，可以把原本很複雜的東西用成一個 function 變的簡單易懂，從簡單到複雜，都一步步的指引與解釋。

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

unit test 的作用即是在測試每個 list.h 所定義的功能是否執行正確，以list_del.c為例，即是在測試 list.h 的 list_del()：

#include <assert.h>
#include "list.h"

#include "common.h"

int main(void)
{
    struct list_head testlist;
    struct listitem item;

    INIT_LIST_HEAD(&testlist);
    assert(list_empty(&testlist));

    list_add(&item.list, &testlist);
    assert(!list_empty(&testlist));

    list_del(&item.list);
    assert(list_empty(&testlist));

    return 0;
}

此精神即是"Divide and conquer"，將 list.h 的每個 function 先個別拿出來做測試。

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

• 參考資料
  rex662624, e94046165 的共筆