# 2019q1 Homework1 (list)
contributed by < `yunchi0921` >
###### tags: `linux_kernel`
## 1. 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
macro 在 compile 之前，preprocessor 會進行文字的替換，執行時不像 function 運用 stack 的 push & pop，是類似空間換取時間的概念。
>如何證明macro是使用空間換取時間？[color=#ad2016][color=#e00f04]
這邊參考 [ChiAnLin0607同學的共筆](https://hackmd.io/Hwtv4V-zT1GzT3EoG9lZTg?view)，透過指令分別對macro與function部份進行objdump反組譯，可以看出macro佔用空間較多。
時間部份寫了小程式測試，實測出macro在時間上是稍短於function
```clike=
#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](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html)是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 解釋以下巨集原理
```clike=
#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 的起始位置。
以下利用一個例子試試看:
```clike=
#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.
```clike=
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](https://github.com/yunchi0921/linux-list/tree/master/mergesort)
實作時參考[ldotrg](https://hackmd.io/s/SJ61s6g84?fbclid=IwAR13VneIAmylABJnftDUpFDALCfgMHh1z12qa4Qufb4KRsuJ6tyKoiLtV7w#Implementation-Merge-Sort)的共筆。
它提到使用[龜兔賽跑演算法](http://www.csie.ntnu.edu.tw/~u91029/Function.html#4)去判斷list的中間值，只要設定兔子跑得速度是烏龜的兩倍就可以在兔子跑完一圈的時候，烏龜正好在中間值，值得注意的是要如何判斷是奇數或是偶數?
A:只要判斷說它離終點也就是head還有一步還是兩步的距離即可。
```clike=
while ((fast->next->next != head) && (fast->next != head))
```
其中有遇到一些困難是，不知道為什麼要使用＆(address of)，而不使用*(pointer)，因為在unitTest上面測試都是使用＆來傳遞參數，所以我就照著做，不過我使用pointer會造成segmentation fault。
>>後來發現不是不用pointer call，只是要多一步malloc的步驟，所以使用&(address of)可以直接由process配置，不確定是不是只有這個目的，還是有更進一步的行為。
Sign in with Wallet
Connect another wallet