2019q1 Homework1 (list)

contributed by < ChihAnLin0607 >

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

每一個 function call 之前都需要先將當下的狀態(暫存器) push 進 stack 中保存，然後才能跳至函式內部執行。執行完後也需要再將 stack 中的狀態 pop 出來還原。

而 macro 在編譯階段，就將呼叫 macro 的位置用定義好的敘述展開，所以不需要先 push 狀態，結束後再 pop 狀態。

所以總結來說， macro 作法是用空間換取時間，雖然少了狀態保存與恢復的動作與時間，但是會增加程式碼的長度； function call 則是用時間換取空間，雖然每一次的呼叫都需要狀態切換的時間成本，但是不論呼叫多少次，都是執行記憶體空間內的同一段代碼。

為了驗證以上論點，我做了以下兩支程式：macro.c和func_call.c，他們行為很簡單，就是呼叫 foo() 110000 次，然後 foo() 會將一個全域變數 i 的值增加 1：

//macro.c
#define foo() i++

int i = 0;

int main()
{
    // 一共 22 * 5000 個 foo()
    foo();foo():foo();foo():foo();foo();
    foo();foo():foo();foo():foo();foo();
    foo();foo():foo();foo():foo();foo();
                     .
                     .
                     .
    
    printf("Elapsed Time: %f sec.\n", (double)clock()/CLOCKS_PER_SEC);
    return 0;
}

func_call.c 和 macro.c 很像只是將 foo 改成函式：

//func_call.c
int i = 0;

void foo()
{
    i++;
}

int main()
{
    // 一共 22 * 5000 個 foo()
    foo();foo():foo();foo():foo();foo();
    foo();foo():foo();foo():foo();foo();
    foo();foo():foo();foo():foo();foo();
                     .
                     .
                     .
                     
    printf("Elapsed Time: %f sec.\n", (double)clock()/CLOCKS_PER_SEC);
    return 0;
}

clock() 會回傳程序執行開始到被呼叫時，CPU 花在該程序的 clock 數，除上定義於 time.h 中的 CLOCKS_PER_SEC 就可以得到呼叫 clock 之前花了多少時間。

分別將兩者編譯成 macro 和 func_call:

$ gcc macro.c -o macro
$ gcc func_call -o func_call

若上方推論正確，應該可以得到以下結果：

• macro會比func_call佔用更多空間
• macro的執行速度會比func_call快

對兩者分別測試20次的結果如下(單位為秒)：

macro：
0.009456、0.009505、0.009262、0.009319、0.009517、0.009465、0.009251、0.009339、0.008269、0.009556、0.010748、0.009442、0.009563、0.009321、0.007704、0.009247、0.009625、0.009290、0.007781、0.004047

func_call：
0.012496、0.018345、0.012943、0.013356、0.012168、0.013422、0.014048、0.012483、0.011679、0.015657、0.015038、0.015581、0.015448、0.014399、0.013235、0.015658、0.007988、0.012845、0.014701、0.016542

雖然其實應該要用統計方法(虛無假設)決定兩者所花時間一不一樣，但我決定先寫其他題目，這邊先用肉眼判斷 macro 所花時間明顯比 func_call 少。

至於原因，可以利用objdump看出其中端倪：

$objdump -D macro > macro.lst
$objdump -D func_call > func_call.lst

以下是 macro.lst 的部份內容：

00000000004004d6 <main>:
  4004d6:   55                      push   %rbp
  4004d7:   48 89 e5                mov    %rsp,%rbp
  4004da:   8b 05 54 cb 1b 01       mov    0x11bcb54(%rip),%eax        # 15bd034 <i>
  4004e0:   83 c0 01                add    $0x1,%eax
  4004e3:   89 05 4b cb 1b 01       mov    %eax,0x11bcb4b(%rip)        # 15bd034 <i>
  4004e9:   8b 05 45 cb 1b 01       mov    0x11bcb45(%rip),%eax        # 15bd034 <i>
  4004ef:   83 c0 01                add    $0x1,%eax
  4004f2:   89 05 3c cb 1b 01       mov    %eax,0x11bcb3c(%rip)        # 15bd034 <i>
  4004f8:   8b 05 36 cb 1b 01       mov    0x11bcb36(%rip),%eax        # 15bd034 <i>
  4004fe:   83 c0 01                add    $0x1,%eax
  400501:   89 05 2d cb 1b 01       mov    %eax,0x11bcb2d(%rip)        # 15bd034 <i>

func_call.lst 部份內容如下：

00000000004004d6 <foo>:
  4004d6:   55                      push   %rbp
  4004d7:   48 89 e5                mov    %rsp,%rbp
  4004da:   8b 05 54 eb c7 00       mov    0xc7eb54(%rip),%eax        # 107f034 <i>
  4004e0:   83 c0 01                add    $0x1,%eax
  4004e3:   89 05 4b eb c7 00       mov    %eax,0xc7eb4b(%rip)        # 107f034 <i>
  4004e9:   90                      nop
  4004ea:   5d                      pop    %rbp
  4004eb:   c3                      retq

00000000004004ec <main>:
  4004ec:   55                      push   %rbp
  4004ed:   48 89 e5                mov    %rsp,%rbp
  4004f0:   b8 00 00 00 00          mov    $0x0,%eax
  4004f5:   e8 dc ff ff ff          callq  4004d6 <foo>
  4004fa:   b8 00 00 00 00          mov    $0x0,%eax
  4004ff:   e8 d2 ff ff ff          callq  4004d6 <foo>
  400504:   b8 00 00 00 00          mov    $0x0,%eax
  400509:   e8 c8 ff ff ff          callq  4004d6 <foo>

由上面兩個 objdump 出的內容可以看出，macro 的 main 函式中，會將 foo() 換成以下三行組合語言代碼：

mov    0x11bcb54(%rip),%eax        # 15bd034 <i>
add    $0x1,%eax
mov    %eax,0x11bcb4b(%rip)        # 15bd034 <i>

簡單來說就是把 i 的值放進 eax 中，然後把 eax 的值增加一，再把新的 eax 值存回 i 中來完成 i++。

而func_call則是把foo()翻成：

mov    $0x0,%eax
callq  4004d6 <foo>

直接跳去 foo 函式所在的記憶體位置，而foo函式內容除了有剛剛 macro.lst 中看到的三行 i++ 編譯而成的組語外，還多包含了五行指令：

<foo>:
    push   %rbp                       # 這裡
    mov    %rsp,%rbp                  # 這裡

    #以下三行由 i++ 編譯而來
    mov    0xc7eb54(%rip),%eax        # 107f034 <i>
    add    $0x1,%eax
    mov    %eax,0xc7eb4b(%rip)        # 107f034 <i>

    nop                               # 這裡
    pop    %rbp                       # 這裡
    retq                              # 這裡

而 func_call 這多的五行指令就是造成其執行時間較 macro 的原因。

而觀察objdump輸出的同時也能看出，空間的佔用大小， macro 將每一個 foo() 都編譯程三行組語代碼； func_call 將每個 foo() 都編譯兩行組語代碼，外加一個八行組語代碼的空間存放 foo 函式本身。結果就是每一次的 foo() 呼叫增加 macro 和 func_call 的代碼大小差異，呼叫愈多次 foo()，macro 會比func_call 大得愈多。

以上的結果證實了一開始的推論是正確的。

參考來源：自己

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

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

typeof 的作用

typeof 有三種樣貌，分別為 typeof 、 __typeof__ 、__typof。解釋他們區別之前要先知道 GNU C 和標準 C 的差別：

• 標準 C：簡單來說就是被某個組織定義出來的C， ANSI C ,ISO C, Standard C C89 C99 C11這些其實都是標準C，只是不同時間定義出來的不同版本。
• GNU C：GNU以標準C為基礎，擴增其他功能實作出來的C。而typeof就是GNU C做的其中一個擴充。

所以如果要標準C的編譯器去認得這些擴充，就必須要在這些擴充的功能名稱前面加上兩個底線「__ 」， __typeof__ 和 __typeof 就是這樣來的。所以三者的功能其實一樣，就是編譯器會在編譯階段將 typeof(n) (或其他兩者)換成 n 的資料型態，也就是說若 n 為一 char 的變數名稱，那 typeof(n) 就會被換成 char。

下方有個測試能看出實際狀況：

// test.c
#include<stdio.h>

int main()
{
    int a;

    __typeof__(int) b;
    &a == &b;

    __typeof(int) c;
    &a == &c;

    typeof(int) d;
    &a == &d;

    return 0;
}

會將兩變數的位址做比較是因為若兩者的類型不一樣，就會丟出 warning: comparison of distinct pointer types lacks a cast 的信息 ，所以如果沒有丟出，就表示typeof有照著預期的行為走。

現在將他編譯，因為我的GCC版本為5.4.0，所以若不設定參數，預設是使用 gnu11 的標準：

$gcc test.c
$

結果並沒有跳出任何訊息，表示編譯器有順利地將 typeof(int) 換成 int 。現在試試看用 C99 標準的 C 編譯看看：

test.c: In function ‘main’:
test.c:14:5: warning: implicit declaration of function ‘typeof’ [-Wimplicit-function-declaration]
     typeof(int) d;
     ^
test.c:14:12: error: expected expression before ‘int’
     typeof(int) d;
            ^
test.c:14:17: error: expected ‘;’ before ‘d’
     typeof(int) d;
                 ^
test.c:15:12: error: ‘d’ undeclared (first use in this function)
     &a == &d;
            ^
test.c:15:12: note: each undeclared identifier is reported only once for each function it appears in

#2果然跳出 warning 訊息，警告說 typeof 沒有被定義。

typeof 在程式碼中扮演的角色

typeof 被大量運用在 macro 之中，因為 macro 本身並不像函式一樣，能限制參數的資料型態，它只是很單純的做程式碼的代換或展開，但如果在 macro 中使用 typeof 宣告出和參數擁有一樣型態的變數，然後再用利用上述提到的不同指標間比較會丟出 warning的技巧，就可以在 macro 的參數不符合期待時，丟出 warning信號。以下是 Linux kernel 中運用的例子：

//linux/include/linux/overflow.h

/*
 * For simplicity and code hygiene, the fallback code below insists on
 * a, b and *d having the same type (similar to the min() and max()
 * macros), whereas gcc's type-generic overflow checkers accept
 * different types. Hence we don't just make check_add_overflow an
 * alias for __builtin_add_overflow, but add type checks similar to
 * below.
 */
#define check_add_overflow(a, b, d) ({		\
	typeof(a) __a = (a);			\
	typeof(b) __b = (b);			\
	typeof(d) __d = (d);			\
	(void) (&__a == &__b);			\
	(void) (&__a == __d);			\
	__builtin_add_overflow(__a, __b, __d);	\
})

#define check_sub_overflow(a, b, d) ({		\
	typeof(a) __a = (a);			\
	typeof(b) __b = (b);			\
	typeof(d) __d = (d);			\
	(void) (&__a == &__b);			\
	(void) (&__a == __d);			\
	__builtin_sub_overflow(__a, __b, __d);	\
})

註解部份也有提到，在做 overflow 的檢查前，他們會先確定 a 、 b 、 *d的 type 一樣。為了達到這目的，會先利用 typeof 宣告類型和 a 一樣的 __a 、 類型和 b 一樣的 __b 、類型和 d 一樣的 __d ，並拿 &__a 和 &__b 比較、 &__a 和 __d，若 a 、 b 和 *d 類型一樣，那就不會丟出 warning 訊息。

參考來源：

1. Referring to a Type with typeof
   
2. __typeof__() 、 __typeof（） 、 typeof（）的區別

4. 解釋巨集原理

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

這巨集分為以下兩個步驟：
1. const __typeof__(((type *) 0)->member) *__pmember = (ptr);

這裡宣告一個指標 __pmember ，其型態和 type 的 member 成員一樣，然後將 ptr 的值指定給 __pmemeber。

從這裡就可以得到幾個訊息：

• type 的型態必須是 struct ，否則會丟出類似以下錯誤：
  error: request for member ‘$(member)’ in something not a structure or union

• member 必須是 type 的成員。若不是的話會丟出類似以下錯誤：
  error: ‘$(type)’ has no member named ‘$(member)’

• ptr 的類型要跟 type 的 member 成員的類型一樣，否則會出現類似以下警告：
  warning: initialization from incompatible pointer type

2. (type *) ((char *) __pmember - offsetof(type, member));

先來看看 offsetof 的作用，以下為 wiki 的解釋：

It evaluates to the offset (in bytes) of a given member within a struct or union type, an expression of type size_t.

也就是說 offsetof(type, member) 會得到 member 在 type 中的偏移量。另外因為有上述第一步驟，所以可以確定 member 一定是 type 的成員。

所以 contain_of 第二步驟就是拿這個「值和 ptr 一樣」的 __pmember 去扣掉 member 在 type 中的相對位置，結果會得到 ptr 所在的 struct 的記憶體起始位置。以下為舉例和圖解。

現在有一個 struct 定義與宣告如下：

struct Node {
    int data;
    struct list_head list;  
} node;

另外我透過別的 list_head 的 next 指標知道 node 底下的 list 記憶體位置(假定其為 node_list ， 型態為 struct list_head* )。 node 的記憶體配置示意圖如下(64位元系統)：

這時若我想用 node_list 反推 node 的記憶體位置，就可以使用 contain_of(node_list, struct Node, list):

首先第一步驟會宣告一個 __pmember，方法如下：
const __typeof__(((struct Node*)0)->list) __pmember = node_list;

__pmember 其實就是 node_list的分身，他們有一樣的型態、指向一樣的記憶體位置。

第二步驟則是：
(struct Node *) ((char *) __pmember - offsetof(struct Node*, list));

由上方的 node 記憶體配置圖可以知道， list 在 node 中的偏移量為 8 ，也就是說 offsetof(struct Node*, list) 等於 8 。而 __pmember 指向的是 X+8 ，扣掉偏移量 8 後，就會得到 node 的記憶體起始位置。

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

list.h 定義許多 macro 來打包許多特定行為，像是 list_for_each 用來走遍 list 內所有資料、 list_first_entry 用來取得 list 的第一筆資料等等。這些打包起來的 macro 能讓許多行相通目的的程式碼變成單行 macro ，提供開發人員更直觀、更高層次的方式來維護與開發。除此之外，也較能減少錯誤的出現。

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

在 list.h 中若 LIST_POISONING 啟動，被刪除的 struct list_head 實體的 next 和 prev 就會指向一個 kernel 無法存取的記憶體位置。在這個指定的過程中是沒有問題的，不論是編譯階段或是執行階段都不會有錯誤出現，但是當有人試著對這段記憶體做操作時，就會出現記憶體區段錯誤的信息。見以下範例：

// poison_test.c
#include<stdio.h>
#define POISON 0x00100100

int main()
{

    int* a = (int *) (0x00100100);

    printf("Next step will do '*a = 0'\n");
    *a = 10;
    return 0;
}
~        

編譯與執行結果：

$gcc poison_test.c
$./a.out
Next step will do '*a = 0'
程式記憶體區段錯誤 (core dumped)

將被從 list 中移除的 list_node實體的 next 和 prev 指向這麼一個非法的記憶體位置，就能夠確保他們不會被使用，一旦真的被使用，就會出現錯誤。

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

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

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

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

/**
 * list_for_each - iterate over list nodes
 * @node: list_head pointer used as iterator
 * @head: pointer to the head of the list
 *
 * The nodes and the head of the list must must be kept unmodified while
 * iterating through it. Any modifications to the the list will cause undefined
 * behavior.
 */
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

/**
 * list_for_each_safe - iterate over list nodes and allow deletes
 * @node: list_head pointer used as iterator
 * @safe: list_head pointer used to store info for next entry in list
 * @head: pointer to the head of the list
 *
 * The current node (iterator) is allowed to be removed from the list. Any
 * other modifications to the the list will cause undefined behavior.
 */
#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

list_for_each_safe 會同時記住當下的 node 和下一個 node，這樣做的目的其實註解裡也有提到，這樣能夠允許當下的 node 被刪除，因為下一個已經被 safe 記下，不會因為當下的 node 被移除，而遺失指向下一個 node 的指標。所以 safe 能夠降低執行時期發生 Memory leak 的可能。

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

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

12. 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？ (提示: 對照看 Doxygen)

@ 是個讓 Doxygen 抓取的標籤特徵。只要熟悉 Doxygen 的分析規則，在後續的程式開發中都依照其規則撰寫註解，這樣就能隨時利用 Doxygen 來快速地產生程式說明檔。

Doxygen 是一個開發輔助工具，他能就將程式內部特定格式的註解轉成 html 等特定檔案格式，自動生成程式碼的說明文件。而 @ 就是剛剛所提到的特定格式。

舉例來說，若 doxygen 讀到以下格式的註解：

/** @mainpage

    This is the mainpage.

*/

那 doxygen 就會在輸出文件中建立一頁 mainpage ，內文為「 This is the mainpage. 」。

而這所謂的特定註解格式其實就是用 /** 和 */ 包含在內的註解。然後在這樣格式的註解內容就可以使用許多 doxygen 預設的標籤，用法跟 html 的標籤有點像，只是名字不一樣，也不需要結束標籤。所以回到剛剛 mainpage 的例子，這例子的標籤就是 @mainpage ，當 doxygen 讀到這個標籤，他就會建立一個 mainpage ，然後把同註解內後面全部的內容都放入其中。而那個 @ 就是 doxygen 的標籤特徵，另外除了 @ 外， \ 也能達到一樣的效果，也就是說 @mainpage 和 \mainpage是一樣的。

現在來看一個比較完整的例子：

// doxygen_test.c

/** @file

    Here is the Detail Description. 
*/

#include<stdio.h>

/** @mainpage

This is a main page.

Here is a blod @b word. 

*/


int global; /** This is a global var. */


/** Here should be the description of foo()

  @param i This number will increase by 1.
*/
void foo(int* i)
{
    (*i)++;
}

/** Here should be the description of main()

*/
int main()
{
    int i = 0;
    foo(&i);

    printf("i = %d\n", i);

    return 0;
}

針對上面範例做一點說明：
@file ：標示該文件給 doxygen 標示，如果文件開頭沒有 @file 標籤，那就算該文件在 doxygen 的輸入資料夾內， doxygen也會選擇忽略。

@b　：能讓此標籤後面的一個單字在輸出說明檔中變成粗體字。

@parm：函式或變數上方的註解會被 doxygen 認為是在解釋該函式或變數，而 @parm 後方的單字會被認為是該函式的參數，單字後方的一句話則會被當成是該參數的說明。

現在要來用 doxygen 產生上方 doxygen_test.c 的說明文件：

    $ls
    doxygen_test.c
    $doxygen -g
    $ls
    Doxyfile doxygen_test.c
    $doxygen Doxyfile
    Doxyfile doxygen_test.c html latex
    $gnome-open html/index.html

#3 會在工作目錄下產生 Doxyfile 的預設設定檔 Doxyfile ，內有許多設定可以修改，但這裡示範就直接使用預設值，而預設值就是分析工作目錄內所有的程式碼，並將結果輸出到工作目錄下。
#5 指令是使用叫 doxygen 用 Doxyfile 內的設定值開始分析註解並且產出說明檔，共會產出兩個資料夾 html 和 latex。
#8 點選 html 內的 index.html 就能用瀏覽器來看 doxygen_test.c 的說明檔了。

結果如下：

參考來源：

1. Doxygen - All Commands簡易說明(未完成) | 給姆喇低賽
2. 21世紀C語言之27: doxygen

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

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

Merge Sort

程式碼：merge_sort.c

思路：

1. 讀取cities.txt內的九萬多筆資料，並用此建立 testlist 。
2. 同時用陣列 values 存取一樣內容、一樣順序的資料。
3. 利用 merge sort 演算法排序 testlist 內的資料。
4. 使用 qsort 排序 values 內的資料。
5. 依順序一一比較兩者內資料順序是否一致。是的話表示 merge sort 成功。

空間利用：

• 為了節省空間，所以一筆資料只建立一個記憶體實體，不論是 testlist 中的 item 或是 values 都只是紀錄該筆資料的記憶體位置而已。
• 這樣的好處除了節省空間外，在最後一步驟 testlist 和 values 內資料比較時，也可以直接比較其指標指向的記憶體位置是否一樣就好，而不用真的比較其字串內容。

時間：
將 Dict 內的測試當成輸入，比較資料由少到高的所需時間變化：

可以看出雖然資料數量由一增加到九萬多，但所花時間只增加到 0.045 秒左右而已。符合時間複雜度 \(O(nlgn)\) 的結果。