Try   HackMD

2019q1 Homework1 (list)

contributed by <MetalheadKen>

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
題目出處

自我檢查清單

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

  • macro
    • 用法：#define macro_name replacement-list new-line
    • 用 #define 來定義一個常數或指令
    • 在編譯前，preprocessor 會把 macro_name 替換為先前定義好的常數或指令
    • 沒有 function call 在執行時期的成本，但會增加 code size，且比起 function 的寫法較不易 debug 和維護
  • function
    • 用法
    • 由於在執行時期呼叫 function 時，需要將 return address 和 function parameter 藉由 push 和 pop 進 stack 裡，因此在執行時期會耗費大量時間成本
  • TODO
    • 比較 macro、function 和 inline function 的 code size 和 execution time

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

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

  • typeof 會回傳參數內的資料型態
  • 例如： 
    ​​int x[10];
​​typeof(x) y;    // 相當於 int y[10];
​​typeof(x[0]) z; // 相當於 int z;
  • 在 GCC manual 中的範例可以看到使用了 typeof 可以依參數內的變數來動態的去調整其資料型態，可以讓程式變得更有彈性以及更容易維護 
    ​​#define max(a, b) \
​​    ({ typeof(a) _a = (a); \
​​       typeof(b) _b = (b); \
​​       _a > _b ? _a : _b; )})

解釋 container_of 巨集的原理

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

  • container_of

    • 為藉由結構體中的成員的記憶體位址，找到該結構體最一開始的記憶體位址

  • __extension__

    • 根據 GCC manual 中提到，在編譯的參數裡添加 -pedantic 或 -ansi 的話，編譯器會對所有使用到 GNU extension 的地方提出警告，但是並不會對包含在 __extension__ 的運算式產生警告

      You can prevent such warnings within one expression by writing __extension__ before the expression. __extension__ has no effect aside from this.

  • __typeof__

    • 根據 GCC manual 中提到，若想要在 ISO C 程式中可以相容的話，可以把 typeof 改寫為 __typeof__

      If you are writing a header file that must work when included in ISO C programs, write __typeof__ instead of typeof.

  • __typeof__(((type *) 0)->member)

    • 一般來說對 0 作 dereference 應該會造成 segmentation fault，但是在 GCC manual 中提到在使用 typeof 時只有在執行時期才能確定的 expression 才會去求值

      The operand of typeof is evaluated for its side effects if and only if it is an expression of variably modified type or the name of such a type.

  • const __typeof__(((type *) 0)->member) *__pmember = (ptr);

    • 宣告一個指向結構體中的成員 member 的資料型態的指標 __pmember，並指派一個變數 ptr
    • 若程式設計師在使用 container_of 時傳進去的參數其 ptr 的資料型態與 member 的資料型態不相符時，在編譯期間會輸出 error: initialization from incompatible pointer type 的錯誤訊息，可藉此在 compile time 檢查出人為上的疏失

  • offsetof

    • size_t offsetof(type, member)
    • 依據 man pages 說明，offsetof 巨集會回傳在結構體 type 中，成員 member 的位址偏移量

  • (type *) ((char *) __pmember - offsetof(type, member));

    • 先把 __pmember 轉型成 pointer to char 的資料型態，藉此讓之後的 pointer arithmetics 時的 offset 位移量可以為 n * sizeof(char)

      Ref: cplusplus.com

    • 之後把 __pmember 與 member 在結構體 type 中的位址偏移量相減即可得到該結構體最一開始的記憶體位址

  • ({...})

    • 在 GCC manual 的第 6.1 章說明此寫法為一個 GNU extension，並提及最終會回傳在 compound statement (大括號) 內最後一個 expression 的計算後的結果

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

  • list_add 和 list_add_tail
    • 若有 LIFO 的需要可以使用 list_add，而若有 FIFO 的需求則可以使用 list_add_tail
  • list_del_init
    • 與一般的 list_del 不同的是，list_del_init 在呼叫 list_del 來把節點從 list 移除後，還會呼叫 INIT_LIST_HEAD 來對已經移除的節點再作一次初始化
    • 用意為因為在 list_del 中並未對已移除的節點其 prev 和 next 做初始化，有可能會對已移除的節點造成誤用的情況發生
  • list_empty
    • 檢查 list 中的 head 是否沒有任何節點連接
  • list_is_singular
    • 檢查 list 中的 head 是否只有一個節點連接
  • list_splice 系列
    • 把兩條 list 連接在一起，不需一直呼叫 list_add 來把一個個的節點連接上去，增加效率
  • list_cut_position
    • 已某個節點為基準點來切割成兩個 list
  • list_move 系列
    • 把 list 中的某一個節點移到最前頭或最後頭
  • list_entry 系列
    • 在 list.h 可以看到 doubly linked list 的定義為 
      ​​​​struct list_head {
​​​​    struct list_head *prev;
​​​​    struct list_head *next;
​​​​};
      而在使用時可以定義如下 
      ​​​​struct listitem {
​​​​    int val;
​​​​    struct list_head list;
​​​​};
​​​​struct listitem *item;
      並在走訪整個 doubly linked list 時可撰寫為 
      ​​​​struct list_head *node;
​​​​struct list_head *curr = item->list;
​​​​for (node = curr->next; node != curr; node = node->next) { ... }
      從上述程式碼中可以發現到，在走訪時我們只能取得到 struct listitem 中的 struct list_head 也就是其節點，但無法取得到節點中的資料 val，但利用 list_entry 和其巨集內使用的 container_of 可以取得到 struct listitem 的最一開始的記憶體位址也跟著可以取得到節點中的資料 val 了

總體來說，藉由定義了一系列操作，並將所有常用的操作用巨集或函式包裝起來，可以

  • 不必再重新造輪子，加速開發時程

  • 使其抽象化，讓程式可讀性增加

    • Linux kernel coding style 中提到函式的寫法要又短又甜而且只做一件事，並且內容要可以在一兩頁內顯示完畢

      Functions should be short and sweet, and do just one thing. They should fit on one or two screenfuls of text (the ISO/ANSI screen size is 80x24, as we all know), and do one thing and do that well.

    • Robert C. Martin, Clean Code: A Handbook of Agile Software Craftsmanship

      The first rule of functions is that they should be small. The second rule of functions is that they should be smaller than that.

LIST_POISONING 這樣的設計有何意義？

在 list.h 的函式 list_del 的註解中提到在節點移除後，會將該節點的 prev 和 next 指向一個非法存取的記憶體位置，若之後有任何程式想要去存取已經移除掉的節點的話，即造成 segmentation fault，可藉此用來在除錯階段得知哪裡有誤

/**
 * list_del() - Remove a list node from the list
 * 
 * ...
 *
 * 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
}

根據 LITMUS wiki 中可以得知 0x00100100 和 0x00200200 為 Well-known addresses，目的為可以在 kernel oops 的時候發現是何種錯誤，因而挑選的一個特殊的位址

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

  • 從任何一個節點皆可以走訪整個 list

  • 若想存取該節點的前一個節點無須從頭開始走訪

  • 在刪除某一節點時，其時間複雜度可為

    O(1) 而不是 singly linked list 的
    O(n)

  • Linux Device Driver 3/e 提到若 linked list 是環狀的，那麼每一個節點的操作都是一樣的，因此不用像 singly linked list 一樣要去維護 head 和 tail

    Since Linux lists are circular, the head of the list is not generally differnet from any other entry.

什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現

什麼情境會需要找到 第 k 大/小的元素 呢？又，你打算如何實作？

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

/**
 * list_for_each - iterate over list nodes
 * @node: list_head pointer used as iterator
 * @head: pointer to the head of the list
 *
 * The nodes and the head of the list must must be kept unmodified while
 * iterating through it. Any modifications to the the list will cause undefined
 * behavior.
 */
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

/**
 * 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)
  • 差別在於多了一個變數 safe 來預先儲存下一個節點
  • 當使用 list_del_init 或是使用 LIST_POISONING 來對移除的節點作初始化時，需要多一個變數來預先儲存下一個的節點，否則在移除節點後，因已經移除的節點的 prev 和 next 已經被改變了，故在執行 node = node->next 時會造成不預期的結果

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

  • 提示︰對照其他程式語言，如 Perl 和 Python

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

  • 提示︰對照看 Doxygen

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

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

Last changed by 
 
Ken Dai
0
297
Published on HackMD