2019q1 Homework1 (list)

contributed by < yunchi0921 >

tags: linux_kernel

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

macro 在 compile 之前，preprocessor 會進行文字的替換，執行時不像 function 運用 stack 的 push & pop，是類似空間換取時間的概念。

如何證明macro是使用空間換取時間？

這邊參考 ChiAnLin0607同學的共筆，透過指令分別對macro與function部份進行objdump反組譯，可以看出macro佔用空間較多。

時間部份寫了小程式測試，實測出macro在時間上是稍短於function

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#ifdef MACRO
#define add(a,b) a+b
#define sub(a,b) a-b
#define mul(a,b) a*b
#else
int add(a,b){return a+b;}
int sub(a,b){return a-b;}
int mul(a,b){return a*b;}
#endif

int main(){
		add(6,6);
		sub(6,6);
		mul(6,6);
		add(6,6);
		sub(6,6);
		mul(6,6);
		add(6,6);
                    .
                    .
                    .
		add(6,6);
		sub(6,6);
		mul(6,6);
		printf("Elapsed Time :%f sec",(double)clock()/CLOCKS_PER_SEC);
		return 0;
                    
        

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

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

typeof是GNU於標準C上的擴充，用於傳回object的type類型。

There are two ways of writing the argument to typeof: with an expression or with a type. Here is an example with an expression:

typeof (x[0](1))

儲存 array of pointer to function 回傳的 type。

typeof (int *)

儲存 type 為 pointer to int 。

typeof is often useful in conjunction with statement expressions . Here is how the two together can be used to define a safe “maximum” macro which operates on any arithmetic type and evaluates each of its arguments exactly once:

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

這裡使用了typeof得知a與b的type，也解決了macro沒有typechecking的問題。

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 的起始位置。

以下利用一個例子試試看:

#include<stddef.h>
#include<stdio.h>
#include<stdlib.h>
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

struct grade{
        int math;
        int eng;
        int chi;
};
int main(){
        struct grade yunchi;
        yunchi.math=80;
        yunchi.eng=90;
        yunchi.chi=30;
        int* ptr=&yunchi.eng;

        struct grade *pos;
        pos= container_of(ptr,struct grade, eng);

        printf("Compute result:%p\nBegin of struture:%p\n",pos,&yunchi);

}

結果

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

list move:
移動一個node到一個list的開頭。
list_splice:
加入一系列的lists nodes 到另一個list上。

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

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                                                                                                                                        
}  

在 linux/poison.h 的註解當中

These are non-NULL pointers that will result in page faults
under normal circumstances, used to verify that nobody uses
non-initialized list entries.

當list_del執行的時候，將會把node的prev&next指向一個特定的位置，當access到這個位置時，會產生pagefault。

至於是為什麼，不曉得是否跟0xDEADBEAF 一樣是magic number有待查證。

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

環狀的 linked list 可以使每個節點都做一樣的事，不用考慮head及tail的問題。

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

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

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

list_for_each_safe 額外多儲存一個safe，儲存當前的下下個位置，當如果當前的下個node被移除時，不會找不到當前的node要link哪個位置。

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

可以增加程式可讀性 。

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

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

確保每一個function的功能性及邏輯上正確，以減少Debug時，專案過大而不知道錯誤從何開始。

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

MergeSort Implement

在實做mergesort時，因為在list.h已經有很多function or macro 可以直接使用，所以與其是說要做出一個mergesort，不如說很像是在了解linux kernel circular doubly linked list 的實做方式。

這裡是我的實做code

實作時參考ldotrg的共筆。

它提到使用龜兔賽跑演算法去判斷list的中間值，只要設定兔子跑得速度是烏龜的兩倍就可以在兔子跑完一圈的時候，烏龜正好在中間值，值得注意的是要如何判斷是奇數或是偶數?

A:只要判斷說它離終點也就是head還有一步還是兩步的距離即可。

while ((fast->next->next != head) && (fast->next != head))

其中有遇到一些困難是，不知道為什麼要使用＆(address of)，而不使用*(pointer)，因為在unitTest上面測試都是使用＆來傳遞參數，所以我就照著做，不過我使用pointer會造成segmentation fault。

後來發現不是不用pointer call，只是要多一步malloc的步驟，所以使用&(address of)可以直接由process配置，不確定是不是只有這個目的，還是有更進一步的行為。