# 2018q3 E04

* 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
* GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* 解釋以下巨集的原理

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

* 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
* `LIST_POISONING` 這樣的設計有何意義？
* linked list 採用環狀是基於哪些考量？
* `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
* for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
* 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen
* `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* `tests/` 目錄的 unit test 可如何持續精進和改善呢？

## ```__GNUC__```
[```__GNUC__```](https://hamisme.blogspot.com/2013/03/gcc.html)

#if defined(__GNUC__)

原來判斷編譯器是否為 GCC 可以用這種判斷方法，如果是的話會被定義。

## ```__typeof__```
根據 [gnu 網站](https://gcc.gnu.org/onlinedocs/gcc-4.8.3/gcc/Typeof.html)
> If you are writing a header file that must work when included in ISO C programs, write ```__typeof__``` instead of typeof.
>
這是 GNUC 的 extension，可以用來決定一個變數的型態。下面是一個比大小的實際應用：

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

假設 a 為 float ，那```typeof(a) _a```將會等價於，```float _a```。
## Linux 應用 linked list 在哪些場合？
檔案系統
## 解釋以下巨集的原理

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

假設 member 是 int 型態。那上面那串將會被代換成

也就是一個指標與 member 同型態，並指向 ptr 所指的位置。

這樣就可以理解成

也就是想取得 structure 的地址。
為什麼要先轉成 char * 在轉成 type * 呢？
是因為 offset 的關係。

#include<stdio.h>

int main(){
	int i = 0;
	int* j = &i;
	printf("before: %x\n",j);
	j++;
	printf("after:  %x\n",j);
	char a = '0';
	char* b = &a;
	printf("before: %x\n",a);
	a++;
	printf("after:  %x\n",a);
} 

你會發現指標的四則運算是建立在型態上面的，唯有 char * 才能進行一單位的地址加減運算，也才能得到 structure 的真正地址。
## 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
參考[這裡](https://www.kernel.org/doc/html/v4.10/doc-guide/kernel-doc.html#how-to-format-kernel-doc-comments)
> The following special patterns are recognized in the kernel-doc comment descriptive text and converted to proper reStructuredText markup and Sphinx C Domain references.
> @parameter
Name of a function parameter. (No cross-referencing, just formatting.)
>
藉由使用這種註解方式，許多程式便可以利用這種註解自動產生 documentation ，不用在刻意寫一次。
## `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
}

仔細觀察上面程式碼，會發現 list node 的刪除就只有把上一個 node 的 next 指標指到下一個，並沒有真實釋放記憶體。把釋放記憶體的 node 的指標指向固定的地方可以防止再度存取已經被刪除的 node。假設有一個指標現在停在被刪除的節點上面，那當此節點被刪除之後，便無法在存取上一個與下一個節點因此停在此點的指標將無法使用，完成刪除的功能。

## `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)
    
#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

因為把下一個的下一個節點存起來了，當在此迴圈內將 node 刪除，還是可以繼續往下走，不會因為此節點的 next 消失而失敗，不論是否開啟```LIST_POISONING```。

## for_each 風格的開發方式對程式開發者的影響為何？
在 python 中，最常用到迴圈的方法是

a = [1,2,3,4,5]
for data in a:
    print(data)

data 變成在 a 中每個元素的別名，在每次迴圈中操作。如此一來，就不需要利用 c 中的

int a[5] = [1,2,3,4,5]
int i;
for (i = 0;i < 5;i++){
    printf("%d\n", a[i])
}

必須利用數字來存取矩陣的內容，還必須時時注意 index number 是否有超過矩陣的範圍。不過，這也是 C 把我們當負責任的大人來看待的一種表現吧。
## `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？

Unit test，常常出現在各式軟體工程內，當作 testbench 來測試軟體的各種面向，確保在任何時候都不會出錯。通常在寫程式真正的時間是一等分的話，花在測試的時間就應該是10等分。確保軟體能正常運作，並且 robust 是軟體工程是最重要的責任與使命。

## `tests/` 目錄的 unit test 可如何持續精進和改善呢？
一般來說， test 是軟體工程最困難的部份。好的 testbench 應該會測試到極端情況，例如 stackoverflow 的可能性，輸入錯誤的可能性。並且每個 if 的分支都必須要測試過，達到 code_coverage 100% ，另外也可以利用有限狀態機等觀念，來進行 testbench 的撰寫，並且測試是否每個狀態都有走過。 此外，testbench 也是一個優化程式的很好的機會，可以觀察是否有沒用到的變數或者偵測 IO Bound 或者 CPU Bound 等。