# 2019q1 Homework1 (list)
contributed by < `Naetw` >
# 自我檢查清單
## 1. 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
看到 macro / function 後最直覺的想法就是，要使用到 macro / function 一定是多段程式碼有其共通性，也就是要把相同的邏輯抽出來，透過 macro / function 做代表，不僅簡化程式碼、更好維護（有問題的話只需修改一個地方），也能用清楚、簡單的名稱來代表一小段程式碼。
兩者的差異：
- macro 只對人有差異，對機器本身沒有差異，因為在經過前置處理器後，macro 會被展開，展開後的模樣基本上就跟自己把好幾行重複的程式碼塞到有寫 macro 的地方一樣。
- function 的話就好比經濟學學到的專業分工，某個人（function）專門負責某件事（code block），也就是當程式中不管哪邊需要處理特定事件的時候，就把該事件所需的資料準備好，交給特定的函式去做處理，事情做好後，若需要則會把結果丟回來。
- 根據上面描述，函式存在著一些額外的成本
- 把事件所需的資料準備好，交給特定的函式（參數傳遞）
- 若需要則會把結果丟回來（回傳值）
- 實際上還有隱藏的成本在上面的描述中。試想不同的人（函式）要工作，為避免工作環境（stack frame）混亂，在切換不同的人（函式）工作時，會需要額外找空間（stack frame）來給下一個人（函式）使用，使用完畢後也必須歸還。
- [Function Prologue & Epilogue](https://en.wikipedia.org/wiki/Function_prologue)
- [TODO] 若有時間可補充行為細節與可能的安全議題
稍微看過 `list.h` 後，最明顯的感受是：透過 macro 包裝並將程式碼抽象化，像是將常見的 for each 行為的程式碼用 macro `list_for_each` 做代替；將常用的對 list 頭、尾的存取行為以 `list_first_entry`, `list_last_entry` 來表示，讓整體對於 list 的操作更加清晰，可以一看見就知道這邊在做什麼樣的事情。
## 2. Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
1. `wait_queue` in [`<linux/wait.h>`](https://github.com/torvalds/linux/blob/master/include/linux/wait.h)
```clike=
/*
* A single wait-queue entry structure:
*/
struct wait_queue_entry {
unsigned int flags;
void *private;
wait_queue_func_t func;
struct list_head entry;
};
struct wait_queue_head {
spinlock_t lock;
struct list_head head;
};
typedef struct wait_queue_head wait_queue_head_t;
```
不同的行程進入 sleep 的時機、需要被叫醒的條件與時間長度不同，使用 linked list 可以很簡單地新增以及移除整串中間任一節點。此外行程數量也不會是固定的，使用 linked list 可以增加彈性。
2. perf 中對於 event 的管理 in [`parse_events.c`](https://github.com/torvalds/linux/blob/master/tools/perf/util/parse-events.c#L487)
```clike=
static int add_tracepoint(struct list_head *list, int *idx,
const char *sys_name, const char *evt_name,
struct parse_events_error *err,
struct list_head *head_config)
{
struct perf_evsel *evsel;
evsel = perf_evsel__newtp_idx(sys_name, evt_name, (*idx)++);
if (IS_ERR(evsel)) {
tracepoint_error(err, PTR_ERR(evsel), sys_name, evt_name);
return PTR_ERR(evsel);
}
if (head_config) {
LIST_HEAD(config_terms);
if (get_config_terms(head_config, &config_terms))
return -ENOMEM;
list_splice(&config_terms, &evsel->config_terms);
}
list_add_tail(&evsel->node, list);
return 0;
}
```
perf 預設是觀察 cycles，但是可以透過參數去指定說要監控哪些事件，而事件的長度非固定，透過 list 可以彈性的管理。
3. singly linked list in [`select.c`](https://github.com/torvalds/linux/blob/master/fs/select.c#L831)
```clike=
struct poll_list {
struct poll_list *next;
int len;
struct pollfd entries[0];
};
```
在撰寫網路應用程式時，常需要透過 `poll` / `select` 來對既有的連線做管理，同樣的 list 可以做到彈性管理，像是突然有新的連線或是舊有連線離開的操作都可以很簡單透過 list 達成。
## 3. GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
可以獲得運算式的型別。
1. `container_of`
- 編譯時期能夠做到型別檢查很重要的一環，可見下方第四個問題。
3. `list_for_each_entry` 系列
- list 的設計讓它能夠廣泛被各種情況去使用，別的結構只需要擁有成員 `struct list_head` 就能夠去做串聯。然而不同結構中 `list_head` 型別的成員會位在不同位置。此巨集系列的作用為走訪各個 entry，顧名思義我們需要利用 entry 型別裡的成員 `list_head` 去做走訪，同時走訪過程中的操作是對於 entry 本身，也就是需要去拿到不同節點的 entry 開頭位址，這個位址可以利用上面提到的 `container_of` 來去獲得，而要使用 `container_of` 的很重要的一個參數就是需要提供整個結構的型別，`typeof` 可以幫忙做到這件事。
## 4. 解釋巨集 `container_of` 的原理
```clike=
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
`container_of` 透過成員位址來推算出物件的開頭位址。
1. 三個參數代表的意義：
- `ptr` - 指向成員的指標，也就是描述中的「成員位址」
- `type` - 包含該成員的結構型別
- `member` - 成員變數名稱
2. `__extension__` 用途
GNU C 支援了很多 extensions，若編譯參數裡有加上 `pedantic` 的話，編譯器會警告所有違反標準 C 語言的寫法。若在運算式（expression）前加上 `__extension__` 便可以達到白名單的效果。
3. Statements and Declarations in Expressions
在 `__extension__` 後有個奇怪的結構 - `({})`，可以將括號內整體視作一個運算式，這同樣是 GNU C 的 extension，加上括號後我們可以在 compound statements 中加入像是迴圈、switch，或是區域變數的使用；此外，它會以區塊中最後一個陳述式的作為此運算式的結果。
4. 第一條陳述式解讀
```clike=
const __typeof__(((type *) 0)->member) *__pmember = (ptr);
```
首先來看 `__pmember` 的型別，它是一個 pointer to xxxx that is const，而 xxxx 就是 `__typeof__()` 所獲得的型別，`typeof` 的運算子簡單來說就是 `type` 這個型別中的成員 `member` 的型別。因此，正常來說 `__pmember` 這個指標所指向的型別「應該」要與 `ptr` 是相同的。
如此一來疑問就來了，這行陳述式存在的意義？實際上就如同上面所描述的：「它們兩個所指向的型別應該要相同」，因為我們無法保證傳入的參數是正確的，而這個指派的動作可以讓編譯器去做型別檢查。若程式設計師的參數不小心寫錯了，那麼在編譯時期就能夠找到這個錯誤，進而去修正。
5. 第二條陳述式解讀
`__pmember` 在正常情況下就會是某個型別中的某成員位址，透過標準函式庫中的 `offsetof` 來獲得該成員相對於整個物件的偏移，將這個偏移量扣除，就能夠獲得物件的開頭位址。需特別注意的部分是強制轉型為 `(char *)` 的部分，因為想要達成的操作是純量的減法，所以需要將它的做轉型為 pointer to 某個大小為 1 byte 的型別，若沒有強制轉型，減法做完會是往前 `offsetof` 個原型別物件的位址。
## 5. 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
- `list_del_init`
- 執行 `list_del` 後，被解除連結的節點空間並不會被釋放與重新設定，若之後不小心直接使用到該節點，有可能會動到不該動的資料，於是有了 `list_del_init` 的設計，這個函式除了執行 `list_del` 外，還會將被刪除的節點重新設定成初始狀態。
- `list_empty`
- 將 `head->next == head` 的行為做包裝，讓程式碼能夠更一目瞭然。
- `list_is_singular`
- 判斷是否只擁有一個節點。不清楚用意。
- `list_splice` 系列
- 將兩條 list A, B 串接在一起，方式是將 A 接到 B 的頭或尾。
- 搜尋了一下 Linux 核心原始碼，在 [pmu.c](https://github.com/torvalds/linux/blob/master/tools/perf/util/pmu.c#L491) 底下找到此函式的使用，情境是可能有一條 list A 在某個條件下是會被整條加進去 B，但是若其中有節點符合某些條件，那就不會有任一個點被加進 B 中。在這樣的情況下，直接一個個慢慢加進 B 中，若遇到問題再來移除是很沒效率的，因此先用另一個 list C 串聯節點，若完全符合特定條件再整條加進 B 中。此函式將兩條串聯的邏輯包裝起來，使用上可以更清楚地表達意義。
- 後綴加上 `init` 的會將來源的節點重新設定，避免誤用。
- `list_cut_position`
- 以某個節點為斷點去切割 list。目前沒有想到什麼使用情境。
- 剩下一些蠻常用的操作，像是搬移特定的節點到頭或尾（是實做 [LRU](https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)) 常會用到的操作）；獲取 list 的頭尾物件；以及像是 iterator 的巨集。
整體來說，就是將常用到的操作給抽象化，讓程式碼寫起來更為簡潔且清楚。
## 6. LIST_POISONING 這樣的設計有何意義？
```clike=
/*
* 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.
*/
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
```
故意給個有問題的記憶體位址，若之後直接使用到沒有好好重新設定的節點，會觸發 segmentation fault。個人認為設計用意是：與其讓不安全且不確定的行為可以繼續往下執行，不如讓它發生錯誤。
:::warning
思考透過 gdb/kgdb 除錯時，POISONING 的幫助，核心已經考慮進去了
:notes: jserv
:::
選擇 `0x00100100` 的用意可參考 [kernel debugging wiki](https://wiki.litmus-rt.org/litmus/KernelDebugging)。
使用 gdb 除錯時，若使用 `print` 指令印出變數內容時，看到特別的數值（像是上方的 `0x00100100`）查閱手冊就可以知道遇到什麼問題，不同數值代表不同的錯誤操作。
## 7. linked list 採用環狀是基於哪些考量？
## 9. 什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？
打算使用 quick select 的方式，並搭配選擇中位數作為 pivot 避免最糟情況。
## 10. `list_for_each_safe` 和 `list_for_each` 的差異在哪？“safe” 在執行時期的影響為何？
多使用一個變數來儲存下一個節點。沒有 safe 的設計限制不能對 list 有任何的修改，有了 safe 的幫助可以做到刪除當前節點的動作。
幫助紀錄下一個節點位址，需要幫忙的原因：
- 使用 `list_del` 做刪除
- 若節點是通過 glibc 的 `malloc` 來獲得空間的話，並有透過 `free` 釋放空間時，glibc 內部管理 heap 是有特別的機制的，像是 `fastbin`, `smallbin` 等等，在這套機制的使用下，節點的內容在被釋放後是會被修改的，也因此無法保證在刪除並釋放空間後內部的資訊還是跟之前一樣。heap 機制可參考 [Heap Exploitation by Angelboy](https://www.slideshare.net/AngelBoy1/heap-exploitation-51891400)。
- 使用 `list_del_init` 做刪除
- 這個會重新設定 `list_head` 結構，若沒有 safe 的幫助，便拿不到下一個節點的位址。
## 13. tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
針對程式碼中各個模組做正確性檢驗。有了 unit test，往後若需要重構時，能夠確保修改後的程式碼運行結果跟之前的一樣。
# Merge Sort
在撰寫上方的自我檢查清單時，即便能理解行為但對於整個 linked list 的設計仍十分的不習慣與陌生，導致在寫程式的時候常常是把類似的行為做到一半或做完才想到可以用 `list.h` 提供的一系列操作。
## Recursion 版本
基本上就跟一般的合併排序實作一樣，列出幾個差異：
### 切半行為
合併排序需要將整個序列不斷對半切成較小的子問題來處理，最後再將結果做合併 (divide & conquer)。這對一般的陣列來說十分簡單，只需要求得陣列長度並做單純的運算即可，但是 linked list 需要實際去走訪總長度並獲得中間節點。
獲得總長度與獲得中間節點看似需要兩次走訪，實際上不用，利用共筆 - [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/s/SkE33UTHf)裡所提到的[龜兔賽跑 (Floyd’s algorithm)](http://www.csie.ntnu.edu.tw/~u91029/Function.html#4)，可以很簡單的找到 list 長度，同時又能獲得中間節點的位址。
兔子 (fast) 一次走兩格，烏龜 (slow) 一次走一格，兔子只需要花 $\dfrac{1}{2}$ N 個迴圈次數便可以走完 list，而烏龜此時剛好就只走了 $\dfrac{1}{2}$ N，也就是我們需要的中間節點。
跳離迴圈後，使用 `list.h` 提供的 `list_cut_position` 來對串列切半，接著用 `list_splice` 來轉移後半段子串列擁有權。
```clike=
static void split_front_back(struct list_head *head,
struct list_head *front,
struct list_head *back)
{
struct list_head *fast, *slow;
slow = head->next;
fast = slow->next;
while (fast != head) {
fast = fast->next;
if (fast == head) {
slow = slow->next; // make slow ((n / 2) + 1)th element (1-based)
break;
}
slow = slow->next;
fast = fast->next;
}
list_cut_position(front, head, slow->prev);
list_splice(head, back);
}
```
### 合併行為
- 一般陣列合併
- 將前半與後半段子陣列額外複製一份來進行比較
- 任一半段用光後，需要將另一半剩下的資料一個個搬移
- 鏈結串列合併
- **不需要**額外複製，直接利用 `list_move_tail` 來做節點的擁有權轉移即可
- **不需要**一個個搬移剩下的資料，直接利用 `list_splice_tail` 轉移整條擁有權。
```clike=
static void merge(struct list_head *head,
struct list_head *front,
struct list_head *back)
{
struct listitem *left, *right;
INIT_LIST_HEAD(head);
left = list_first_entry(front, struct listitem, list);
right = list_first_entry(back, struct listitem, list);
while (!list_empty(front) && !list_empty(back)) {
if (cmpint(&left->i, &right->i) < 0) {
list_move_tail(&left->list, head);
left = list_first_entry(front, struct listitem, list);
} else {
list_move_tail(&right->list, head);
right = list_first_entry(back, struct listitem, list);
}
}
list_splice_tail(!list_empty(front) ? front : back, head);
}
```
## 效能分析
### 工具準備
在使用 gnuplot 前，修改了 lab0-c 的 driver.py 來自動跑三種排序演算法並產生出相對應的資料：
```shell=
» scripts/driver.py
Size merge-sort quick-sort insert-sort
10000 0.007699 0.006204 0.211774
20000 0.011354 0.007267 1.185317
30000 0.014276 0.012529 3.145712
40000 0.017808 0.022158 6.241908
50000 0.021843 0.030662 10.108960
```
接著撰寫 gnuplot 腳本。
首先是設定圖的標示，可以使用 `xlabel`, `ylabel` 來設定 x, y 軸的名稱、設定 x 軸的刻度間距，以及 `title` 來設定標題，最後是輸出檔案的檔名：
```gnuplot=
reset
set ylabel "time (sec)"
set xlabel "size"
set xtics 10000
set title "Time Comparison (random input)"
set output "normal.png"
```
還有其他設定可以進入 gnuplot 後輸入指令 `help` 來查詢，或是參考共筆 [gnuplot 語法解說和示範](https://hackmd.io/c/rJKbX1pFZ/https%3A%2F%2Fhackmd.io%2Fs%2FSkwp-alOg)。
接著是繪圖相關的指令，`plot` 為繪圖的指令，後面需接上各種參數來描述怎麼取出資料並以什麼種類的圖來呈現，首先來看語法：
```=
syntax:
plot {<ranges>} <plot-element> {, <plot-element>, <plot-element>}
```
以下方腳本來說明：
```gnuplot=
plot [:][:]'normal.txt' \
using 1:2 with linespoints linewidth 2 title 'merge', \
'' using 1:3 with linespoints linewidth 2 title 'quick', \
'' using 1:4 with linespoints linewidth 2 title 'insert'
```
- `[:][:]`
- 對應到語法中的 ranges，根據 manual，它的順序會是 `plot [<xrange>][<yrange>][<x2range>][<y2range>] ...`
- 由於 gnuplot 會自己去判斷上下界自動選擇適當的刻度，這邊若沒有特別需求可以直接空白
- 像下圖就是沒有特別設定自動產生的，可以看到 merge-sort 與 quick-sort 基本上是 0.x 秒內就跑完的
- 若覺得跟 x 軸重合很醜，可以設定 y 軸起點為 -1 `[-1:]`
- `'normal.txt'`
- 對應到語法中的 plot-element，plot-element 可以是很多種東西，像是數學函數或是資料檔等等，這邊選擇的就是資料檔
- `using 1:2`
- 這是專門用來給資料檔的指令，它告訴 gnuplot 要萃取檔案中哪一個 column 來繪圖，這裡 `1:2` 代表 x 軸使用 1st column 而 y 軸使用 2nd column 的資料
- 也可以寫成 `using (column("merge-sort")):(column(1))` 或是 `using "Size":"merge-sort"`
- `with linespoints linewidth 2`
- 一樣是對應到語法中的 plot-element，屬於裡面的細節，用來描述要以什麼樣的方式來呈現資料
- 可以是 histogram（直方圖）或是這邊使用的 linespoints（折線圖）
- 完整的選項可以進入 gnuplot 下指令 `help plot style` 查看第一手資料！
- `plot` 指令需要是單一行指令，可以利用反斜線來增加可讀性，就像上方那樣分行
- 另外如果是取用同一個資料檔，那後面可以單獨使用 `''` 就相當於一開始的 `'normal.txt'`
### 玄妙的 Makefile
首先是安裝 git hook：
```make=
GIT_HOOK := .git/hooks/applied
$(GIT_HOOK): scripts/install-git-hooks
@$<
@echo
```
- 指派變數 `GIT_HOOK` 為某個檔案路徑，用來作為 target
- 仔細去看 `scripts/install-git-hooks` 可以看到在安裝到最後會創建一個空的檔案 `.git/hooks/applied` 用來代表成功安裝。
- target `$(GIT_HOOK)` 中利用 Makefile 的 magic 變數 `$<` 來執行安裝腳本
- `$<` 代表的是 first prerequisite
- `@` 是一個指令前綴，代表的是：不要印出指令本身
接著是一些比較簡單的設定：
```make=
.PHONY: all check clean
all: $(GIT_HOOK) check
.DEFAULT_GOAL := all
include common.mk
CFLAGS = -I./include
CFLAGS += -std=c99 -pedantic -Wall -W -Werror
```
- 利用 `.PHONY` 來指定 target 為 fake 項目，如此一來 `make` 才不會去檢查該目錄中是否存在該 target 名稱的檔案
- target `all` 的前置條件為 Git hook 與 check 的執行
- 利用 `.DEFAULT_GOAL` 來指定沒有加任何參數的純 `make` 指令所需要執行的 target（預設會是最上面的 target）
- `include` 就跟 C 裡面見到的差不多，可以引入其他的 Makefile
- `CFLAGS` 變數設定
關於主要的單元測試檔案相關變數設定：
```make=
TESTS = \
containerof \
...
list_splice \
list_splice_tail \
list_splice_init \
list_splice_tail_init \
list_cut_position
TESTS := $(addprefix tests/,$(TESTS))
# dependency of source files
deps := $(TESTS:%:%.o.d)
```
- `TESTS` 就是一連串巨集 / 函式的名稱所組成的字串（以空白為區隔）
- 接著利用 Makefile 語法中用於檔名的函式 `addprefix` 幫現有的 `TESTS` 變數裡面的所有名稱加上 prefix `'tests/'`
- 語法為 `$(addprefix prefix,names…)`
- names 可以用空白區隔不同名稱，整個函式做完的回傳值為 names 加上 prefix 並以空白連接的字串
- 詳見 [8.3 Functions for File Names](https://www.gnu.org/software/make/manual/html_node/File-Name-Functions.html)
- 這邊 `deps` 變數的用法翻了翻 GNU make 的手冊翻不太到，跑去翻了 git log，看起來應該是寫錯？第二個 `:` 應該要是 `=`？
目前的用法，若直接用 `echo` 來看他的內容是空的
- 發了個 [issue](https://github.com/sysprog21/linux-list/issues/3) 確認
- 確認是筆誤，也發了個 [pull request](https://github.com/sysprog21/linux-list/pull/4) 修正。
- 所以整句 `deps := $(TESTS:%=%.o.d)` 的作用是，將 `$(TESTS)` 中所有內容加上 suffix `.o.d`。這種用法稱為 [Substitution References](https://www.gnu.org/software/make/manual/html_node/Substitution-Refs.html#Substitution-Refs)
- `deps` 只有在最後一行被 `include` 指令使用，詳見下方的「[自動產生相依性項目](https://hackmd.io/s/HkWEohML4#自動產生相依性項目)」
預設規則的主軸：
```make=
TESTS_OK = $(TESTS:=.ok)
check: $(TESTS_OK)
$(TESTS_OK): %.ok: %
$(Q)$(PRINTF) "*** Validating $< ***\n"
$(Q)./$< && $(PRINTF) "\t$(PASS_COLOR)[ Verified ]$(NO_COLOR)\n"
@touch $@
```
- 延續上面提到的 Substitution References，這邊也是同樣的，這邊雖省略了 `%` 但效果是相同的，也就是將 `TESTS` 變數裡的所有名稱加上 suffix `.ok`
- 訂定 target check 的相依性項目，check 同時也是預設規則 all 的主要行為
- 接著是一種 [Static Pattern Rule](https://www.gnu.org/software/make/manual/make.html#Static-Pattern)，語法：
```
targets …: target-pattern: prereq-patterns …
recipe
…
```
簡單來說就是能夠提供一個 targets 列表，接著利用 target-pattern 去篩選並獲得想要的資訊，然後再重組成相依性項目。
在這邊的例子是利用 `'%'` 來獲得 targets 的 stem，也就是 `xxx.ok` 中的 `xxx`，然後把這個 `xxx` 當作相依性項目。所以實際上我們相當於擁有下列規則：
```make=
containerof.ok: containerof
# recipes
list_entry.ok: list_entry
# recipes
# ...
```
- 變數 Q 是定義在另一個 makefile `common.mk` 中，與變數 VECHO 都是用來決定 verbosity，簡單來說就是決定輸出的資訊量多寡，而變數 PRINTF 內容為因應不同環境使用該環境的 printf 指令
- 第二行 recipe 就是去執行單元測試，然後依據回傳值來印出驗證是否成功
- 最後是創建 `xxx.ok` 來表示驗證完成
確定了上方 `$(TESTS_OK)` targets 的相依性項目都是各個函式或巨集的單元測試執行檔，那最後就是這些執行檔是怎麼被 make 出來的：
```make=
# standard build rules
.SUFFIXES: .o .c
.c.o:
$(VECHO) " CC\t$@\n"
$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF $@.d $<
$(TESTS): %: %.o
$(VECHO) " LD\t$@\n"
$(Q)$(CC) -o $@ $^ $(LDFLAGS)
```
- 這裡使用的是比較舊的用法 (old fashioned)，新的等價用法是：`%.o: %.c`，利用 Pattern Rules 中的 `'%'` 符號來獲得 "stem"
- 印出資訊
- 一些編譯器的選項
- `-c` 不要跑連結器 (linker)
- `-MMD` 閱讀手冊發現其實它等價於 `-MM -MF file`，`-MMD` 會透過 `-o` 所指定的檔名去加上 suffix `.d` 來當作 `-MF file` 中的 file
- `-MF file` 當使用 `-M` / `-MM` 來讓編譯器產生 Makefile 的相依性項目時，可以使用此選項指定要把相依性項目的內容寫到特定檔案
- 最後就是 line 7 的規則，透過此規則的相依性項目，來去使用上方定義的 recipes 編譯出需要的目的檔，然後再在這裡的 recipes 中使用連結器 (linker) 把目的檔們連結成最終的執行檔，讓上一段的 target `$(TESTS_OK)` 去跑測試
#### 自動產生相依性項目
> 整理自官方手冊 [4.14 Genereating Prerequistes Automatically](https://www.gnu.org/software/make/manual/html_node/Automatic-Prerequisites.html#Automatic-Prerequisites)
平常對自己的 C 專案撰寫 Makefile 時，常常都是人工慢慢新增或刪除相依性項目 (prerequisite)，如此一來當專案規模增大時，是十分麻煩且容易出錯的。
在過去，一般會利用編譯器的選項 `-M` 來產生原始碼所需要的 Makefile rules，並在主要的 Makefile 中用 target depend 來完成這件事，最後用 `include` 指令來把產生的 depend 檔案（是一種 Makefile）引入。
舉例來說（假設 main.c 裡面沒有引入任何檔案）：
```shell
cc -M main.c
```
會產生如下面的輸出：
```shell
main.o: main.c
```
若 `main.c` 中有引入其他檔案，則輸出就會增加有引入的所有檔案。
現今在 GNU make 的官網建議是：針對每個原始碼檔案 `name.c` 都有各自的一個 Makefile `name.d` 對應，內容就是目的檔 `name.o` 與 Makefile `name.d` 的相依檔案列表，如此一來，只有當原始碼有更動到，才需要去更新此特定的 Makefile。
下方是用來產生相依性項目檔案（本質上是個 Makefile）的 pattern rule：
```make=
%.d: %.c
@set -e; \
rm -f $@; \
$(CC) -M $(CPPFLAGS) $< > $@.$$$$; \
sed 's,\($*\)\.o[ :]*,\1.o $@ : ,g' < $@.$$$$ > $@; \
rm -f $@.$$$$
```
編號即代表各行數的指令。
1. 一種 [pattern rule](https://www.gnu.org/software/make/manual/html_node/Pattern-Rules.html#Pattern-Rules)
2. 設定只要後面列出來的指令有任一個出錯就會讓 shell 直接離開
3. 移除舊有的 `.d` Makefile（註：`$@` 代表的是 target name）
4. 編譯某個 `.c` 檔，並用前面提到的 `-M` 選項產生相依性項目，最後寫入 `<target>.$$$$`（註：`$<` 代表相依性項目中的第一個項目，在這裡就是被編譯的檔案名稱）
- 若是使用 GNU C 編譯器，可以使用 `-MM`，這個選項不會把系統的標頭檔也一起寫進相依性項目中
5. 根據這篇SO - [Why can s command of sed can be followed by a comma?
](https://stackoverflow.com/questions/17877060/why-can-s-command-of-sed-can-be-followed-by-a-comma)，`sed` 可以使用任意字元作為 delimiter 來避免讓實際要做替換的字串太過複雜（需要一堆反斜線）。在這邊就是使用 `,` 作為 delimiter。
- 關於這個正規表達式 `$*`，手冊翻了很久、Google 也查不太到。最後發現去年底發佈的 4.6 版本有除錯模式，直接拿來看執行細節，試了幾次後，嚴重懷疑那段是寫錯的。根據取代中的 `\1` 的使用，推測 `\($*\)\.o` 中的 `.o` 前面的行為是想要去抓到 `.o` 前的所有字串，後面再用 `\1` 去做 back reference，但是其實根本不需要。sed 這邊的取代行為基本上跟 vim 裡面一樣，可以直接用 `\.o[ :]*` 取代成 `\.o $@ : ` 也會有一樣的效果。被這個沒有用途又應該是寫錯的語法雷了好久 Orz
簡單來說 5. 想做到的事情是將下列的 Makefile 內容作改寫：
```make=
main.o : main.c defs.h
```
改成：
```make=
main.o main.d : main.c defs.h
```
簡單來說就是在 `.o` 跟 `:` 中插入 `$@` (target name)，因此第 4 行的 `sed` 指令可以改成：
```shell=
sed 's,\.o[ :]*,.o $@ : ,g' < $@.$$$$ > $@;
```
6. 移除暫存檔
到此已經產生好專屬的 Makefile `main.d`，裡面包含了 `main.o` 的 remake 規則（當 `main.c` or `defs.h` 有更動時要更新），而 `main.d` 也具有同樣的 remake 規則。這時透過 Makefile 中的 `include` 指令，將此 Makefile `main.d` 引入進去，`make` 就能夠自動判斷什麼時候要重新製作關於 `main.o` 的相依性項目，同時也會更新 `main.d`，使用者再也不需要手動處理。
# 之後再整理
- Compound statement
- [variably modified type](http://port70.net/~nsz/c/c11/n1570.html#6.7.6p3)
- 指的是 variable length array
- typeof 的運算子只有在它是 expression / name of variably modified type 才會去做求值的行為
- 也因此可以搭配 compound statement 來做「安全」的巨集
Sign in with Wallet
Connect another wallet