2019q1 Homework1 (list)

contributed by < guojiun >

自我檢查清單

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

  依據 function-call overhead… real? or not?

  ​​​​#include <stdio.h>
  ​​​​#include <sys/time.h>
  
  ​​​​#define macro_test(a, b) ((a) + (b))
  
  ​​​​int func_test(int a, int b) {
  ​​​​    return a + b;
  ​​​​}
  
  ​​​​void show_time(char *str, struct timeval *tv) {
  ​​​​    printf("%s: %d.%06d\n", str, tv->tv_sec, tv->tv_usec);
  ​​​​}
  
  ​​​​int main(void) {
  ​​​​    struct timeval tv;
  ​​​​    unsigned int i;
  ​​​​    int val;
  
  ​​​​    gettimeofday(&tv, NULL);
  ​​​​    show_time("function time start", &tv);
  ​​​​    for(i = 0; i < 4000000;++i)
  ​​​​        val = func_test(1, 1);
  ​​​​    gettimeofday(&tv, NULL);
  ​​​​    show_time("function time end", &tv);
  
  ​​​​    gettimeofday(&tv, NULL);
  ​​​​    show_time("macro time start", &tv);
  ​​​​    for(i = 0;i < 4000000;++i)
  ​​​​        val = macro_test(1, 1);
  ​​​​    gettimeofday(&tv, NULL);
  ​​​​    show_time("macro time end", &tv);
  
  ​​​​    return 0;
  ​​​​}
  

  • 實驗結果:

    • 當 i = 4000000 時
    ​​​​​​​​function time start: 1551182903.339022
    ​​​​​​​​function time end:   1551182903.353053
    ​​​​​​​​macro time start:    1551182903.353066
    ​​​​​​​​macro time end:      1551182903.361425
    

    • 當 i = 8000000 時
    ​​​​​​​​function time start: 1551183911.109517
    ​​​​​​​​function time end:   1551183911.137761
    ​​​​​​​​macro time start:    1551183911.137773
    ​​​​​​​​macro time end:      1551183911.154081
    

    • 當 i = 16000000 時
    ​​​​​​​​function time start: 1551183955.172073
    ​​​​​​​​function time end:   1551183955.225101
    ​​​​​​​​macro time start:    1551183955.225111
    ​​​​​​​​macro time end:      1551183955.258338
    

使用 gnuplot 製圖，視覺化展現

jserv

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

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

  • typeof 簡單來說就是 Referring to the type of the expression，在預編譯時得以知道 type 的訊息。這樣的訊息可以如何來利用呢？先來看看 typeof 使用的場景吧。
  • 在 linux 的 typecheck.h 中，有如下 macro:
    ​​​​​​​​#define typecheck(type,x) \
    ​​​​​​​​({  type __dummy; \
    ​​​​​​​​    typeof(x) __dummy2; \
    ​​​​​​​​    (void)(&__dummy == &__dummy2); \
    ​​​​​​​​    1; \
    ​​​​​​​​})
    

    • 如果型態不一致時，編譯器會有 typecheck.c:4:20: warning: comparison of distinct pointer types lacks a cast (void)(&_dummy == &dummy2); 的警告

• 解釋以下巨集的原理

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

  參考資料ㄧ

  • (type*) 0 : take the integer zero and cast it to a pointer to type
  • ((type*) 0)->member : deferences that pointer to point to structure member member
  • _ _ typeof_ _ (((type*) 0)->member) : get the type information
  • 總體來說，上述第三行程式碼，是為了 type checking
  • offsetof(type, member) 現改為編譯器的 builtin function
  • 將 __pmember 指標先轉型為 pointer to char，如此一來，再扣除其偏移量時，才能以 byte 為單位進行指標運算。
  • 最後，作完指標運算後，再轉回到 struct type。注意不是原來 __pmember 的 type 喔。

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

  • 摘要 Linux kernel design patterns - part 2

    • All of the other macros use the "prefetch" function to suggest that the CPU starts fetching the ->next pointer at the start of each iteration so that it will already be available in cache when the next iteration starts (though the "safe" macros actually fetch it rather than prefetch it).

    • 安全性

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

  • While this will normally improve performance, there are cases when it will slow things down. (prefetch 不一定對提昇效能有所幫助)
  • When the walk of the list will almost always abort very early - usually only considering the first item - the prefetch will often be wasted effort. In these cases (currently all in the networking code) the __list_for_each() macro is available. (在只考慮 list 中第一個 item 的使用情境下，prefetch 就可能適得其反了)
  • In these cases (currently all in the networking code) the __list_for_each() macro is available.

• LIST_POISONING 這樣的設計有何意義？

  • 除錯
    • 如果程式發生 a dangling pointer reference 時，透過設定 LIST_POISONING 的方式，藉此得確認 dangling pointer 是否由已 removed node 所引起，還是再其它地方。參考資料
  • 能清楚地反映出程式中對已經 unlinked node 存在不當的操作
    • 此外，通常也會將 LIST_POISONING 給 enable 起來，如果之後這個 poisoned pointer 不小心被deferenced 的話，則可以透過 poison value 方便識別問題所在。參考資料

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

思考 for_each macro 對於靜態分析的幫助

jserv

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

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

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

作業要求