# 2019q1 Homework1 (list)
contributed by < `Shengyuu` >
## 自我檢查事項
* ### 為何 Linux 採用 macro 來實作 linked list ? 一般的 function call 有何成本？
* #### macro 是什麼
* macro 會在程式被編譯之前執行，將使用者定義的名詞進行轉換
```clike=+
#include<stdio.h>
#define A 10
int main()
{
printf("%d",A);
return 0;
}
```
經過編譯之後可以發現 A 直接被代換掉了
**``` gcc -E macro.c```**
* #### macro 要注意的事
* 參考[Macros vs Functions](https://www.geeksforgeeks.org/macros-vs-functions/)
* #### macro v.s function
* macro 會直接將程式碼做文字替換，會增加指令空間的大小，但可以省略掉呼叫 function call 時對 stack 的操作，當 function call 重複較多次時，用 macro 代替可以節省許多時間
:::warning
之後補上反組譯分析及效能分析
:::
* ### Linux 應用 linked list 在哪些場合？
* ### GNU extension 的 typeof 有何作用
* typeof 可以回傳變數的型態，因為 macro 中無法給定變數型態，所以在 macro 中 typeof 被大量使用以確保型態正確
:::warning
增加程式碼範例
:::
* ### 解釋以下巨集的原理
* 觀察題目要求的巨集 container_of 可以發現當中用了另一個巨集 "offset" ，它被定義在 <linux/stddef.h> 中，可以用來計算某一個 struct 結構的成員相較於該結構起始位置的偏移量
```clike
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
```
>此段程式碼把數值 0 強制轉換成 TYPE 指標類型，拿取該 struct 指定成員後，對此成員取址，最後回傳一個型態為 size_t 的數。
>[color=#ffff93]
>
**驗證：**
```clike=+
#include<stdlib.h>
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
struct test{
int a;
int b;
int c;
};
int main(){
struct test *t;
size_t size1,size2;
size1 = offsetof(struct test, b);
size2 = offsetof(struct test, c);
}
```
```
(gdb) p sizeof(*t)
$1 = 12
(gdb) p sizeof(int)
$2 = 4
(gdb) p size1
$3 = 4
(gdb) p size2
$4 = 8
(gdb)
```
* 了解巨集 offset 後，我們可以進一步來看題目所要求的巨集 container_of ，它被定義在 <linux/lernel.h> 中，這個巨集的作用是可以得到某個 struct 的起始點，只要我們知道該結構任意一個成員的地址就可以用 containner_of 算出該集夠的起始位置
```clike=+
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
>此段程式碼前半部先宣告一個型態和 member 相同的指標 __pmember 並取得 member 得所在位址 ptr ，第二部份將 member 所在的位址減去 offset 後即可得到該結構的初始位址
>[color=#ffff93]
>
** 驗證：**
```clike=+
#include<stdlib.h>
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
struct test{
int a;
int b;
int c;
};
int main(){
struct test *ptr, t;
size_t size1,size2;
size1 = offsetof(struct test, b);
size2 = offsetof(struct test, c);
ptr = container_of(&(t.b), struct test, b);
}
```
```
(gdb) p ptr
$1 = (struct test *) 0x7fffffffde0c
(gdb) p &t
$2 = (struct test *) 0x7fffffffde0c
```
>由 gdb 輸出結果可看出變數 t 的位址和用巨集 containner_of 取得的位址一樣
>
**補充：** container_of 還有一個值得探討的地方是它將參數 __parameter 強制轉換成 char* 型態再和 offset 做減法，原因是指標在做運算時會依據所指向型態的大小而有所不同，而 char 型態的大小剛好本來就是1，所以將指標強制轉換成 char pointer 再跟 size_t 型態的變數做運算就不會產生問題
**驗證：**
```clike=+
#include<stdlib.h>
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
struct test{
int a;
int b;
int c;
};
int main(){
struct test t, *ptr1, *ptr2;
size_t size1;
char *a1;
int *a2;
a1 = (char *) (&(t.b));
a2 = (int * ) (&(t.b));
size1 = offsetof(struct test, b);
ptr1 = (struct test *) (a1 - size1);
ptr2 = (struct test *) (a2 - size1);
}
```
```
(gdb) p a1
$5 = 0x7fffffffde10 ""
(gdb) p a2
$6 = (int *) 0x7fffffffde10
(gdb) p size1
$7 = 4
(gdb) p ptr1
$8 = (struct test *) 0x7fffffffde0c
(gdb) p ptr2
$9 = (struct test *) 0x7fffffffde00
(gdb)
(gdb) p sizeof(int)
$10 = 4
```
> a1 和 a2 是用不同型態的指標存取 &(t.b)，由 gdb 的結果可看出他們的數值原本是一樣的，但同樣對 size1 做減法後的 ptr1、ptr2 的值卻有所差異。從 $9 可以看出 ptr2 和原本的 a2 差了16，而16剛好是 sie1*4 的大小，驗證了 int 的大小是4個 Byte (<s>依不同編譯器版本會不同</s>）
>
**參考 [Jinyo的隨便寫寫](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)**
:::warning
不是「依不同編譯器版本會不同」，而是 ABI (Application Binary Interface) 有關，參見 [64-bit data models](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models)
儘量讀第一手材料。
:notes: jserv
:::
* ### 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
* 很多時候我們要操作得對象是整個 list 而不只是一個 entry ，如果多在標頭檔內多定義一些操作整個 list 的 function ，在實作的時候就可以使程式碼更簡潔、更有效率。在 list.h 標頭檔中最前面的註解其實也有寫到
```clike
/*
* Simple doubly linked list implementation.
*
* Some of the internal functions ("__xxx") are useful when
* manipulating whole lists rather than single entries, as
* sometimes we already know the next/prev entries and we can
* generate better code by using them directly rather than
* using the generic single-entry routines.
*/
```
* ### LIST_POISONING 這樣的設計有何意義？
* 先來找找哪裡用到了poison
```clike
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
```
>觀察上面的程式碼可以發現 list 再做刪除的時候會把刪除的節點內的 next、prev 分別指向兩個 LIST_POISON，而 LIST_POISIN 是定義在一個 poison.h 的標頭檔中，所以我們再去看看 poison.h
>[color=#ffff93]
```clike
/*
* Architectures might want to move the poison pointer offset
* into some well-recognized area such as 0xdead000000000000,
* that is also not mappable by user-space exploits:
*/
#ifdef CONFIG_ILLEGAL_POINTER_VALUE
# define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
#else
# define POISON_POINTER_DELTA 0
#endif
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x200 + POISON_POINTER_DELTA)
```
>這段程式碼的註解告訴我們 LIST_POISON1、LIST_POISON2 是兩個會造成 page faults 的 non-NULL pointers，因此可推論出 list_del 將 prev、next 指向 LIST_POISON 是防止已被刪除的節點被違規存取的狀況
>[color=#ffff93]
>>至於為什麼不直接將 next、prev 指向 NULL 呢？
>>可以參考 [what is the meaning of 0xdead000000000000](https://stackoverflow.com/questions/27801360/what-is-the-meaning-of-0xdead000000000000)
>>留言中有提到一句話："Using 0xdead000000000000 as the base value just makes it easier to distinguish an explicitly poisoned value from one that was initialized with zero or got overwritten with zeroes. "
>>可見使用 poison 是為了在 debug 時可以更快速、清楚的知道問題出在哪邊
>>[color=#ff5151]
* ### linked list 採用環狀是基於哪些考量？
* 對比於非環狀的 list 需要一個指標指向 list 的開頭，當操作 list 時還要多考慮操作的 node 是否為 head 的特殊狀況，環狀 linked list 則不需要一個特別的指標紀錄 list head 的位置，這使得操作 list 的 function 更為簡潔，對於每個 function 也可以減少一個判斷是否為 head 的 if case
* 在需要多次重複尋訪 list 的狀況下，環狀 list 也能發揮其特點增加執行的效率，若為非環狀的 list 每次尋訪時都需要一個 if case 判斷 node->next 是否為 NULL，而環狀的 list 因為每個 node 都可以當作 head，尋訪時可以避免這個判斷。在作業系統中常常把正在執行的多個程式放在一個 list 中，尋訪到哪個程式就執行哪個程式，在這過程中就需要大量的重複尋訪
>參考[Circular Linked List](https://www.geeksforgeeks.org/circular-linked-list/)
* ### 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
* ### 什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？
* ### list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？
* 若我們在 for 迴圈可能改變到 list 我們就需要用到有 safe 的版本，有 safe 的版本會在我們動作之前先紀錄 list 的下一個 element ，防止我們在操作到時不小心將 element 刪除或改變，倒置錯誤結果
```clike
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
```
>變數 n 在 pos 初始話的時候就先把 pos->next 紀錄起來，防止進入 for 迴圈之後 pos 被改變導致 pos->next 消失或錯誤
>[color=#ffff93]
* ### for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
* ### 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
* 在函式的註解中使用 @ 符號加在 parameter 前面，讓使用者可以一眼就分辨出註解中哪些指的是參數
* ### tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* ### tests/ 目錄的 unit test 可如何持續精進和改善呢？
## Merge Sort
參考[lineagech](https://hackmd.io/s/ByPuvlTBN)同學 git hub 上的程式碼改寫
```clike=1
void list_split(struct list_head *head,
struct list_head *left,
struct list_head *right)
{
struct list_head *a = head->next;
struct list_head *b = head->next;
while(b != head && b->next != head)
{
a = a->next;
b = b->next->next;
}
list_cut_position(left, head, a->prev);
list_cut_position(right, head, (b == head ? head->prev : b));
}
```
> 函式 list_split 中用了[你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf)的龜兔賽跑演算法，這個演算法的好處能夠讓我們用一個 while 迴圈就得到 mid 的位址，如果沒有用這樣的演算法，可能就得先用一個迴圈得到 list 的總長度，在用另一個迴圈取得 list 中間的位址
>
* 函式中的 list_cut_position 是定義在 list.h 內的一個 function，它的作用是擷取一個 list 的一段給另一個 list
```clike
/**
* list_cut_position() - Move beginning of a list to another list
* @head_to: pointer to the head of the list which receives nodes
* @head_from: pointer to the head of the list
* @node: pointer to the node in which defines the cutting point
*
* All entries from the beginning of the list @head_from to (including) the
* @node is moved to @head_from.
*
* @head_to is replaced when @head_from is not empty. @node must be a real
* list node from @head_from or the behavior is undefined.
*/
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
>函式中從擷取 head_from 的 node 的位置開始到最後一個 node 給 head_to
>[color=#ffff93]
* main function 的邏輯並不難，大概就是產生一個 random 的 array ，再用 for 迴圈將 array 裡的資料一個一個放入新建立的 testlist 當中， list 創建完成後分別拿去 quick_sort 和我們自己寫的 merge_sort 排序，最後在依依筆對結果
```clike
random_shuffle_array(values, (uint16_t) ARRAY_SIZE(values));
```
>產生 random array 的函式定義在 common.h 中
>[Todo] 解析此標頭檔
>
###### tags: `Linux 核心設計 2019`
Sign in with Wallet
Connect another wallet