2019q1 Homework1 (list)

contributed by < ChienHisang >

tags: linux_kernel

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

電腦執行 function call 的方式將程式當前狀態暫時儲存在stack中，之後跳到function所在的記憶體位置執行完操作後，再跳回來（從stack pop）繼續執行。耗費記憶體尋址過程所需的時間，若程式中頻繁的呼叫function，則累積起來的時間成本不容小覷。macro的方式是當程式在編譯時會把主程式中呼叫函式的操作展開以至於主程式佔用的記憶體空間變大但相對的省下尋找記憶體位址的時間成本.
查了一下資料，在 c 語言中，使用inline關鍵字來實現 macro 的操作方式或是直接用 define 來實現,不同的是 inline 可以將函式呼叫的時間與函式包含的計算邏輯所需時間作比較,若計算邏輯所需時間大於函式呼叫時間,則編譯器並不會將此函式在主程式中展開,我們可以導出一個結論,macro使用情境為當函式中的負載相當輕量且大量出現在主程式中.

define 使用情況

#define afun(a) a+1

int main(void){
    
    printf("%d",afun(10));
    return 0;
}

inline 使用情況

inline int bfun(int x);

int main(void){
    printf("%d",bfun(10));
    return 0;
}

int bfun(int x){
    return ++x;
}

使用 inline 時遇到的錯誤

inline.c:

inline int bfun(int x){
    return ++x
}

int main(void){
    printf("%d",bfun(10));
    return 0;
}

complie:

# gcc inline.c -o inline

or

# gcc -O0 inline.c -o inline

error:得到以下錯誤

/tmp/ccA3bki9.o: In function `main':
inline.c:(.text+0xa): undefined reference to `bfun'
collect2: error: ld returned 1 exit status

此種直接在函數面前加上inline的寫法,必須要用O1以上的優化編譯才能順利通過,可是網路上一堆這種寫法… 原因待查中.

測試macro效果

1.大量呼叫函式:

int main(void){
    fun(10);fun(10);fun(10);fun(10);fun(10);
    fun(10);fun(10);fun(10);fun(10);fun(10);
                    .
                    .
                    .
}

結果為
使用 define | 使用 function call | 使用inline

0.000848 sec  0.001650 sec  0.001133 sec

define效果最好,inline次之,function call最差

推論: inline 效能比 define 差的原因可能是多了一個是否需展開程式碼的判斷.

2.使用for大量呼叫函式:

int main(void){
    for(int i = 0 ; i < 90000000 ; i++){
        fun(10);
    }
    return 0;
}

結果為
使用 define | 使用 function call | 使用inline

0.211242 sec 0.210119 sec 0.210430 sec

三者差不多
推論:
1.macro 可能在回圈之中不會將程式展開
2.macro會展開但是大部分的時間花在for回圈本身記憶體尋址與條件判斷,因此macro效果不明顯

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

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

typeof 是 gcc 提供的擴展,主要功能是獲取括號內的型別.
typeof的參數可以是表達式或是類型.

使用情境1:

int a;
typeof(a)b;      //等同於 int b
typeof(&a)c;    //等同於int* c

使用情境2:

typeof(int*)a,b; //等同於 int* a , int* b;

使用情境3:

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

此方式可以解決macro帶來的型別不確定

4.解釋以下巨集的原理

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

• (type *) 0)
  將0轉型成 pointer to type
• (((type *) 0)->member)
  將轉型為pointer to type 0 指向 member
• __typeof__(((type *) 0)->member) *__pmember = (ptr);
__pmember利用typeof取得該type，並餵ptr給該指標。
• offsetof(type,member)
  取得該member在type這個structure內的offset
• (type *) ((char *) __pmember - offsetof(type, member));
  將pmember(指向member的pointer to type)，減去掉這個member在type中的offset，就是type這個structure 的起始位置。

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

待補…

6.LIST_POISONING 這樣的設計有何意義？

待補…

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

可以在不增加tail指標（紀錄list結尾）的情況下,在尾端以O(1) insert data node.

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

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

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

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

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

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

提示: 對照看 Doxygen

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

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

---

Merge Sort Implement