# 2020q1 Homework1 (lab0)
contributed by < [`KYG-yaya573142`](https://github.com/KYG-yaya573142/lab0-c) >
> [H01: lab0](https://hackmd.io/JSFDnHn0Rpe0V7d-AqLAXA?view)
## 預期目標
* [C 語言程式設計](https://hackmd.io/@sysprog/c-programming) 議題，如[不定個數參數的處理](https://en.wikibooks.org/wiki/C_Programming/stdarg.h), [signal](https://en.wikibooks.org/wiki/C_Programming/signal.h), [setjmp/longjmp](https://en.wikibooks.org/wiki/C_Programming/setjmp.h) 和記憶體管理
* 學習 [GNU/Linux 開發工具](https://hackmd.io/@sysprog/gnu-linux-dev)
- [Cppcheck](http://cppcheck.sourceforge.net/): 靜態程式碼分析工具
- [Valgrind](https://valgrind.org/): 動態程式分析工具
* 學習使用 Git 與 GitHub
* 樹立一致且易於協作的程式開發規範
* 研究自動測試機制
* 接觸 [Linux Programming Interface](http://man7.org/tlpi/)
## 作業要求
* `q_new`: 建立新的「空」佇列
* `q_free`: 釋放佇列所佔用的記憶體
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則)
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則)，時間複雜度須為 $O(1)$
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素
* `q_size`: 計算佇列中的元素數量，時間複雜度須為 $O(1)$
* `q_reverse`: 以反向順序重新排列鏈結串列 (此函式不該配置或釋放任何鏈結串列元素)
* `q_sort`: 以遞增順序來排序鏈結串列的元素 (此函式不該配置或釋放任何鏈結串列元素)
## 開發流程
### queue.h
題目要求 `q_insert_tail` 和 `q_size` 的時間複雜度須為 $O(1)$，因此先修改 queue.h 中的 `struct queue_t`，新增 `list_ele_t *tail` 及 `int size`
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
### `q_size`
直接回傳 `q->size` 即可
```cpp=
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
### `q_new`
先確認是否成功 malloc，再初始化 queue
```cpp=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### `q_free`
須注意在 `q_insert_head` 與 `q_insert_tail` 中，除了配置 elements 的記憶體之外，還會再配置記憶體來儲存字串，因此釋放記憶體的順序應該是
1. 用來儲存字串的空間
2. linked list elements
3. queue
```cpp=
void q_free(queue_t *q)
{
if (!q) /* ignore NULL queue */
return;
/* Free queue structure */
list_ele_t *tmp = q->head;
while (tmp) {
q->head = tmp->next;
if (tmp->value) /* free the string if existed */
free(tmp->value);
free(tmp);
tmp = q->head;
}
free(q);
}
```
### `q_insert_head` & `q_insert_tail`
這兩個 function 寫起來非常相似，先配置 element 的記憶體空間，再配置 element 中用來儲存字串的空間 (記得確認 malloc 是否成功)，儲存字串至 element 內，最後將 element 插入 queue 的頭/尾並把 `q->size` 加 1
實作上有幾點需特別注意：
* `strlen` 回傳的長度**不包含** null terminator，因此 length 記得要加 1 回去
```shell
$ man strlen
...
DESCRIPTION
The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').
...
```
* 若在 malloc 字串所需空間時才失敗，記得要釋放 element 的空間再 return
* 若為 empty queue 時，需特別處理 `q->head` 或 `q->tail` (使兩者皆指向目前新增的唯一 element)
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
if (!q) /* ignore NULL queue */
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
/* allocate space for the string and copy it */
int length = strlen(s) + 1;
newh->value = malloc(length * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, length);
/* insert element at head of queue */
if (q->head == NULL) /* queue is empty */
q->tail = newh;
newh->next = q->head;
q->head = newh;
(q->size)++;
return true;
}
bool q_insert_tail(queue_t *q, char *s)
{
if (!q) /* ignore NULL queue */
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
/* allocate space for the string and copy it */
int length = strlen(s) + 1;
newh->value = malloc(length * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, length);
/* insert element at tail of queue */
if (q->head == NULL) { /* no element in the queue */
q->head = newh;
q->tail = newh;
} else {
q->tail->next = newh;
q->tail = q->tail->next;
}
q->tail->next = NULL;
(q->size)++;
return true;
}
```
### `q_remove_head`
釋放記憶體的邏輯類似 `q_free`，釋放 elements 配置的記憶體前，需先處裡並釋放 element 中字串使用的空間
實作上需注意複製字串至 sp 的這個步驟，由於有最大空間為 bufsize 的限制，應該使用 `strncpy` 而非 `strcpy`，使用前先查閱說明 `man strncpy`
> The strcpy() function copies the string pointed to by src, **including** the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy. **Beware of buffer overruns!**
> The strncpy() function is similar, except that at most n bytes of src are copied. **Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.**
> If the length of src is less than n, strncpy() writes additional null bytes to dest to ensure that a total of n bytes are written.
因此當 bufsize 小於字串長度時，將不會複製到 null terminator，要記得手動將其補上
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head) /* ignore NULL and empty queue */
return false;
list_ele_t *tmp = q->head;
q->head = q->head->next;
if (tmp->value) {
if (sp != NULL) {
strncpy(sp, tmp->value, (bufsize - 1));
sp[bufsize - 1] = '\0';
}
free(tmp->value);
}
free(tmp);
(q->size)--;
return true;
}
```
### `q_reverse`
實作上可以分為以下步驟
1. 建立 `new` 指標，用來指向已經分類完成的 elements
2. `q->tail` 可以先指向 `q->head`，因為最後順序會反轉
3. 依序將 element 從原先的 queue 取出
4. 總是將取出的 element 放到 `new` 的**頭**，來達到反轉順序的目的
5. 最後將 `new` 指標接回去 `q->head` 即可
```c=
void q_reverse(queue_t *q)
{
if (!q || !q->head) /* ignore NULL and empty queue */
return;
if (!q->head->next)
return;
list_ele_t *tmp;
list_ele_t *new = NULL;
q->tail = q->head;
while (q->head) {
/* detach element from the head */
tmp = q->head;
q->head = q->head->next;
/* reverse the queue */
tmp->next = new;
new = tmp;
}
q->head = new;
}
```
### `q_sort`
根據作業說明的共筆中提供的資料，可以使用 bubble sort、insertion sort、selection sort、merge sort 等方式來排序 (將 `sort_method` 的部分替換成欲使用的演算法名稱即可，例如 `merge_sort`)
```c=
void q_sort(queue_t *q)
{
if (!q || !q->head) /* ignore NULL and empty queue */
return;
if (!q->head->next)
return;
q->head = sort_method(q->head);
while (q->tail->next) { /* update the tail pointer */
q->tail = q->tail->next;
}
}
```
至於題目中所謂的*以遞增順序來排序鏈結串列的元素*要怎麼做呢? 其實直接觀察 qtest.c 就可以知道答案了，其中 `do_sort` 這個方程式中很明確的使用 `strcasecmp` 來檢驗 `q_sort` 的結果，因此在我們的 `q_sort` 中一樣使用 `strcasecmp` 來排序就可以了
#### merge sort
概念上可以分為拆分 (`merge_sort`) 及合併 (`merge`) 兩個部分
拆分 `merge_sort`:
1. 將原先的 list 從中間分為兩半
2. 將分出來的兩個 list 再各自從中間分為兩半
3. 重複步驟 2 直到整個 list 都被拆成單一 element
```c=
list_ele_t *merge_sort(list_ele_t *head)
{
/* merge sort */
if (!head || !head->next)
return head;
list_ele_t *slow = head;
list_ele_t *fast = head->next;
/* split list */
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
/* sort each list */
list_ele_t *l1 = merge_sort(head);
list_ele_t *l2 = merge_sort(fast);
/* merge sorted l1 and sorted l2 */
return merge(l1, l2);
}
```
合併 `merge`
1. 排序兩個單一 element 並合併為一個 list
2. 把兩個上述步驟產生的 list 排序並接合為一個 list
3. 重複步驟 2 直到接合所有 list
以下我分別使用不同的方式來實作 `merge` 的部分
**方式 1 - 使用遞迴的方式 merge**
這個方式的優點是程式碼很簡潔，但遞迴呼叫的方式導致記憶體使用量更龐大。
最明顯的例子就是當測試 traces-15-perf.cmd 時，因為配置的 elements 數非常龐大 (size = 2,000,000)，會出現 segmentation fault (使用 AddressSanitizer 可以知道問題是 stack overflow)
註：後續會再使用 valgrind 來分析此問題
```shell
$ make SANITIZER=1
$ make test
...
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
ASAN:DEADLYSIGNAL
=================================================================
==9205==ERROR: AddressSanitizer: stack-overflow on address 0x7ffcd0a27fd8 (pc 0x7f703599965e bp 0x7ffcd0a28840 sp 0x7ffcd0a27fa0 T0)
...
```
```c=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l1)
return l2;
if (!l2)
return l1;
if (strcasecmp(l1->value, l2->value) < 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
```
**方式2 - pseudo head**
常見的 pseudo head 是先 malloc 一個空間來連接已經排序完成的 element，但在本作業中不允許在 `q_sort` 內呼叫 malloc，因此我改為使用指標的方式實作，如此一來在 traces-15-perf.cmd 時就不會錯誤
```c=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l1)
return l2;
if (!l2)
return l1;
list_ele_t *head = NULL; /* pseudo head */
list_ele_t *tmp = NULL;
/* decide the first element and use it as pseudo head */
if (strcasecmp(l1->value, l2->value) < 0) {
head = l1;
l1 = l1->next;
} else {
head = l2;
l2 = l2->next;
}
/* merge remaining elements to pseudo head */
tmp = head;
while (l1 && l2) {
if (strcasecmp(l1->value, l2->value) < 0) {
tmp->next = l1;
l1 = l1->next;
} else {
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
if (l1)
tmp->next = l1;
if (l2)
tmp->next = l2;
return head;
}
```
## 變更排序所用的函式為 natural sort
為了使用 [natural sort](https://github.com/sourcefrog/natsort)，需先修改 Makefile 來將 strnatcmp.[ch] 加入
(相關的 dependency 會放在 .natsort 內)
```
...
NAT_DIR := natsort
...
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
natsort/strnatcmp.o
...
%.o: %.c
@mkdir -p .$(DUT_DIR)
@mkdir -p .$(NAT_DIR)
$(VECHO) " CC\t$@\n"
$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
...
clean:
rm -f $(OBJS) $(deps) *~ qtest /tmp/qtest.*
rm -rf .$(DUT_DIR)
rm -rf .$(NAT_DIR)
rm -rf *.dSYM
(cd traces; rm -f *~)
```
接著需要修改 queue.c 中使用的排序方式及 `make test` 時驗證 `q_sort` 結果的部分，也就是 queue.c 與 qtest.c 這兩個檔案的部分內容
* queue.c:
實際需要修改的地方是 merge sort 使用的 `merge`，將原先使用的 `strcasecmp` 修改為 `strnatcmp` 即可
* qtest.c:
字串排序結果是在 `do_sort` 中驗證的，將原先使用的 `strcasecmp` 修改為 `strnatcmp` 即可
至此已將排序函式變更為 natural sort，然而編譯時 Cppcheck 會報錯，如下
```shell
natsort/strnatcmp.c:112:14: style: The scope of the variable 'ca' can be reduced. [variableScope]
nat_char ca, cb;
^
natsort/strnatcmp.c:112:18: style: The scope of the variable 'cb' can be reduced. [variableScope]
nat_char ca, cb;
^
natsort/strnatcmp.c:170:0: style: The function 'strnatcasecmp' is never used. [unusedFunction]
^
Fail to pass static analysis.
```
直接觀察 strnatcmp.c 相關的部分，區域變數 ca 和 cb 的用途是用來儲存接下來要比較的字元，但由於整個比較的過程都不會 (也不該) 修改到原本的字串，因此其實不用多宣告這兩個區域變數，也就是捨棄原本先宣告 `ca = a[ai]` 再使用 ca 的作法，改為直接使用 a[ai] 即可，修改完成後就可以正常編譯了
```c=
static int strnatcmp0(nat_char const *a, nat_char const *b, int fold_case)
{
int ai = 0;
int bi = 0;
int fractional, result;
while (1) {
/* skip over leading spaces or zeros */
while (nat_isspace(a[ai]))
++ai;
while (nat_isspace(b[bi]))
++bi;
/* process run of digits */
if (nat_isdigit(a[ai]) && nat_isdigit(b[bi])) {
fractional = (a[ai] == '0' || b[bi] == '0');
if (fractional) {
if ((result = compare_left(a + ai, b + bi)) != 0)
return result;
} else {
if ((result = compare_right(a + ai, b + bi)) != 0)
return result;
}
}
if (!a[ai] && !b[bi]) {
/* The strings compare the same. Perhaps the caller
will want to call strcmp to break the tie. */
return 0;
}
if (fold_case) {
if (nat_toupper(a[ai]) < nat_toupper(b[bi]))
return -1;
if (nat_toupper(a[ai]) > nat_toupper(b[bi]))
return +1;
} else {
if (a[ai] < b[bi])
return -1;
if (a[ai] > b[bi])
return +1;
}
++ai;
++bi;
}
}
```
最後是驗證的部分，原先在測試 `q_sort` 正確性的 trace files 中，無論是使用 `strcasecmp` 或是 `strnatcmp` 都會給出一樣的結果，因此根據 natural sort 提供的測試排序文件 [test-word](https://github.com/sourcefrog/natsort/blob/master/test-words) 來寫一個專門測試 natural sort 是否正確運作的 [traces/trace-18-natsort.cmd](https://github.com/KYG-yaya573142/lab0-c/blob/master/traces/trace-18-natsort.cmd)，實測結果也顯示正確
```
strcasecmp strnatcmp
1-02 | 1-02
1-2 | 1-2
1-20 | 1-20
10-20 | 10-20
fred | fred
jane | jane
pic01 | pic01
pic02 | pic02
pic02000 | pic02a
pic02a | pic02000
pic05 | pic05
pic100 | pic2
pic100a | pic3
pic120 | pic4
pic121 | pic100
pic2 | pic100a
pic3 | pic120
pic4 | pic121
tom | tom
x2-g8 | x2-g8
x2-y08 | x2-y08
x2-y7 | x2-y7
x8-y8 | x8-y8
```
## 以 Valgrind 分析記憶體問題
先前使用遞迴的方式 merge 時遇到的問題一樣可以用 valgrind 分析，錯誤訊息明確的指出 stack overflow
```
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
==27612== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==27612== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==27612== Can't extend stack to 0x1ffe8010a8 during signal delivery for thread 1:
==27612== no stack segment
==27612==
==27612== Process terminating with default action of signal 11 (SIGSEGV)
```
## Valgrind - Massif
### 使用介紹
[Massif](https://valgrind.org/docs/manual/ms-manual.html) 可以分析程式執行過程 heap 的使用狀態，使用的方法為
```shell
$ valgrind --tool=massif ./qtest
```
以本作業來說，也可以選擇製作或使用已有的 trace file 來進行分析
```shell
$ valgrind --tool=massif ./qtest -f trace
```
註：最初使用時會報錯 `Unknown option: --show-leak-kinds=all`，將 .valgrindrc 裡面 `--show-leak-kinds=all` 刪掉即可 (.valgrindrc 裡面紀錄的是預設使用的參數)
分析結果預設存於同目錄下的 massif.out.\<pid\> 檔案中 (可以使用參數 `--massif-out-file` 指定不同的檔案)，得到分析結果後，可以進一步將其圖像化
```shell
$ ms_print massif.out.<pid>
```
圖像中的 `:` 代表一般記錄點、`@` 代表詳細記錄點、`#` 代表峰值位置，y 軸為 heap 使用量，x 軸預設為 instruction 的執行數量，可使用參數 `--time-unit=<i|ms|B>` 更改
```
--time-unit=<i|ms|B> [default: i]
The time unit used for the profiling.
There are three possibilities:
1. instructions executed (i), which is good for most cases;
2. real (wallclock) time (ms, i.e. milliseconds), which is sometimes useful;
3. bytes allocated/deallocated on the heap and/or stack (B), which is useful for very short-run programs, and for testing purposes, because it is the most reproducible across different machines.
```
Massif 可配合不同的參數調整分析的方式，詳見 [Manual](https://valgrind.org/docs/manual/valgrind_manual.pdf)
### 實測 heap 使用量
接下來分別以 `--time-unit=i`(預設) 與 `--time-unit=B` 兩種參數來分析以下自訂指令
```
new
ih head 100000
it tail 100000
reverse
sort
size
quit
```
觀察 `--time-unit=i` 的分析結果，可以看到程式的過程一共約執行了 429.1 Mi，然而峰值在位置 83.6 Mi 時就出現了，這是因為我們執行的指令實際上只有 `ih head 100000` 和 `it tail 100000` 會大量增加 heap 的使用量，其餘的 `reverse` `sort` `quit` 主要改變的是 stack 而不是 heap，這也是為何到達峰值後，heap 的使用量幾乎都維持一致直到程式結束
```
$ ms_print massif.out.32595
--------------------------------------------------------------------------------
Command: ./qtest
Massif arguments: (none)
ms_print arguments: massif.out.32595
--------------------------------------------------------------------------------
MB
24.42^ #
| :#:::::::::::::::::::::::::::::::::::::::::::::::::::::
| ::#: ::
| ::#: :::
| :::#: :::
| @:::#: :::
| @:::#: :::
| :@:::#: ::::
| :@:::#: ::::
| ::@:::#: :::::
| @::@:::#: :::::
| :@::@:::#: :::::
| :@::@:::#: :::::
| ::@::@:::#: :::::
| :::@::@:::#: ::::::
| @::@::@:::#: ::::::
| :@::@::@:::#: ::::::
| :@::@::@:::#: :::::::
| ::@::@::@:::#: :::::::
|:::@::@::@:::#: :::::::
0 +----------------------------------------------------------------------->Mi
0 429.1
Number of snapshots: 53
Detailed snapshots: [8, 9, 17, 26, 34 (peak)]
```
觀察 `--time-unit=B` 的分析結果，可以發現 heap 先線性成長到峰值，接著再線性下降直到程式結束，這是因為 `ih head 100000` 和 `it tail 100000` 實質上就是重複 100000 次相同指令，所以是線性成長，接著 `quit` 時會使用 `q_free` 將記憶體逐一釋放，所以是線性下降
另外，原先 `--time-unit=i` 的分析結果在峰值後會出現一段 heap 用量幾乎沒有變動的區域，這個區域在改用 `--time-unit=B` 分析後會直接消失，這是因為此時 x 座標是 heap 的使用/釋放量，既然 heap 用量沒有改變，x 座標就不會移動
```
$ ms_print massif.out.32584
--------------------------------------------------------------------------------
Command: ./qtest
Massif arguments: --time-unit=B
ms_print arguments: massif.out.32584
--------------------------------------------------------------------------------
MB
24.42^ #
| ::#::
| :::#: :
| :::::#: :::
| :@: :::#: :: :
| :::@: :::#: :: ::::
| :: :@: :::#: :: ::::::
| :::: :@: :::#: :: :::::@:
| ::::: :@: :::#: :: :::::@:::
| :::::::: :@: :::#: :: :::::@:::::
| :::: ::::: :@: :::#: :: :::::@::::::
| :: :: ::::: :@: :::#: :: :::::@:::::::::
| ::::: :: ::::: :@: :::#: :: :::::@:::::::::::
| :: ::: :: ::::: :@: :::#: :: :::::@::::::::::::
| :::: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@
| :: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@:
| ::::: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@::::
| :::: :: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@::::::
| :: :: :: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@::::::@
| :::: :: :: :: ::: :: ::::: :@: :::#: :: :::::@:::::::::::::@::::::@::
0 +----------------------------------------------------------------------->MB
0 48.47
Number of snapshots: 71
Detailed snapshots: [1, 23, 28 (peak), 38, 55, 65]
```
Massif 的結果會顯示峰值所在的 snapshot，分別是兩種分析結果的 34 及 28 這兩筆，挑選出來後直接比對，可以發現 heap 的使用量確實是一模一樣的，差別僅在 x 軸的不同
```
--time-unit=i
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
34 83,560,433 25,610,648 20,210,167 5,400,481 0
--time-unit=B
--------------------------------------------------------------------------------
n time(B) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
28 25,611,112 25,610,648 20,210,167 5,400,481 0
```
Massif 在特定的 snapshot 會做詳細的紀錄 (同時也是圖像上的 `@` 與 `#` 所在的位置)，其中 heap 的總量可再被分為兩種
* useful-heap
程式執行時向系統請求的 heap 量
* extra-heap
heap 用來記錄管理資訊的空間 (header 與 footer)、以及為了alignment 而增加的空間，這兩個也就是所謂的 internal fragmentation
挑選峰值的紀錄觀察，可以發現只有 78.91% 的 heap 使用量是 useful-heap，這代表 internal fragmentation 相對明顯
接著看下方的樹狀圖，先觀察前兩階的數據，可以發現 `q_insert_head` 與 `q_insert_tail` 都使用了 21.87% 與 17.57% 的用量，而它們的用量加起來幾乎就是 useful-heap 的總量，這符合前面觀察到的結果，因為整個測試過程中只有 `ih` 和 `it` 會新增 elements
```
--------------------------------------------------------------------------------
n time(B) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
26 24,457,704 24,457,240 19,300,056 5,157,184 0
27 24,951,528 24,951,064 19,689,714 5,261,350 0
28 25,611,112 25,610,648 20,210,167 5,400,481 0
78.91% (20,210,167B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->78.87% (20,200,064B) 0x10C6E9: test_malloc (harness.c:137)
| ->21.87% (5,600,000B) 0x10CC56: q_insert_head (queue.c:58)
| | ->21.87% (5,600,000B) 0x10A77F: do_insert_head (qtest.c:213)
| | ->21.87% (5,600,000B) 0x10B8E8: interpret_cmda (console.c:220)
| | ->21.87% (5,600,000B) 0x10BE5C: interpret_cmd (console.c:243)
| | ->21.87% (5,600,000B) 0x10C5CB: cmd_select (console.c:609)
| | ->21.87% (5,600,000B) 0x10C672: run_console (console.c:630)
| | ->21.87% (5,600,000B) 0x10AD97: main (qtest.c:771)
| |
| ->21.87% (5,600,000B) 0x10CCF5: q_insert_tail (queue.c:89)
| | ->21.87% (5,600,000B) 0x10A4F8: do_insert_tail (qtest.c:298)
| | ->21.87% (5,600,000B) 0x10B8E8: interpret_cmda (console.c:220)
| | ->21.87% (5,600,000B) 0x10BE5C: interpret_cmd (console.c:243)
| | ->21.87% (5,600,000B) 0x10C5CB: cmd_select (console.c:609)
| | ->21.87% (5,600,000B) 0x10C672: run_console (console.c:630)
| | ->21.87% (5,600,000B) 0x10AD97: main (qtest.c:771)
| |
| ->17.57% (4,500,000B) 0x10CC7C: q_insert_head (queue.c:63)
| | ->17.57% (4,500,000B) 0x10A77F: do_insert_head (qtest.c:213)
| | ->17.57% (4,500,000B) 0x10B8E8: interpret_cmda (console.c:220)
| | ->17.57% (4,500,000B) 0x10BE5C: interpret_cmd (console.c:243)
| | ->17.57% (4,500,000B) 0x10C5CB: cmd_select (console.c:609)
| | ->17.57% (4,500,000B) 0x10C672: run_console (console.c:630)
| | ->17.57% (4,500,000B) 0x10AD97: main (qtest.c:771)
| |
| ->17.57% (4,500,000B) 0x10CD1B: q_insert_tail (queue.c:94)
| | ->17.57% (4,500,000B) 0x10A4F8: do_insert_tail (qtest.c:298)
| | ->17.57% (4,500,000B) 0x10B8E8: interpret_cmda (console.c:220)
| | ->17.57% (4,500,000B) 0x10BE5C: interpret_cmd (console.c:243)
| | ->17.57% (4,500,000B) 0x10C5CB: cmd_select (console.c:609)
| | ->17.57% (4,500,000B) 0x10C672: run_console (console.c:630)
| | ->17.57% (4,500,000B) 0x10AD97: main (qtest.c:771)
| |
| ->00.00% (64B) in 1+ places, all below ms_print's threshold (01.00%)
|
->00.04% (10,103B) in 1+ places, all below ms_print's threshold (01.00%)
```
### 記憶體對齊
從 [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory?type=view) 可以知道在 64-bit 的系統下，malloc 會以 16 bytes 進行對齊，而原先 heap block 用來記錄管理資訊的空間 header 與 footer 會共佔 8 bytes，也就是說如果 elements 中儲存的字串低於 8 個字 (含 null terminator)，一律會因為 alignment 要求而實際 malloc 8 bytes，同理當字串長度為 9~24 個字時皆會 malloc 24 bytes
這個現象也可以用 massif 觀察，使用以下的指令進行實驗，主要目的是驗證使用字串為 "h" 與 "t" 時的 heap 使用量其實與字串為 "head" 與 "tail" 時一樣
```
new
ih h 100000
it t 100000
free
new
ih head 100000
it tail 100000
quit
```
從結果可以看到 heap 總使用量根本一樣，而字串為 "head" 與 "tail" 時，因為程式實際索取的記憶體大小較大，產生的 useful-heap 也確實比較高
```
string: "h", "t"
--------------------------------------------------------------------------------
n time(B) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
18 25,611,112 25,610,648 19,610,164 6,000,484 0
76.57% (19,610,164B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
string: "head", "tail"
--------------------------------------------------------------------------------
n time(B) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
28 25,611,112 25,610,648 20,210,167 5,400,481 0
78.91% (20,210,167B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
```
最後再追加一個比較，目的是呈現當字串長度為 9~24 個字時會 malloc 24 bytes
註：massif 沒辦法同時抓取複數峰值，因此只呈現圖像結果
```
new
ih h 100000
it t 100000
free
new
ih head 100000
it tail 100000
free
new
ih headhead 100000
it tailtail 100000
quit
```
結果很明顯，字串長度 8 以內 heap 的使用量都一樣，字串長度一到 9 bytes 就能觀察到 heap 使用量提升
```
MB
27.48^ #
| #
| :#
| @ :: ::#:
| :@: :: ::#::
| :@: :: : :::#::
| @:@::: :: : @:::#:::
| @:@:: :::: :: @:::#::::
| :@:@:: @ : :: ::: :@:::#::::
| :@:@:: @ :: :: ::: ::@:::#:::::
| :::@:@:: @: :: :: :::: ::@:::#::::::
| : :@:@:: @:: ::: :: ::::: :::@:::#:::::@
| :: :@:@:: @:: ::: :: :::::@ ::::@:::#:::::@:
| :: :@:@:: @::: :::: :: :::::@ :::::@:::#:::::@::
| ::: :@:@:: @::: ::::: :: :::::@: :::::@:::#:::::@::
| :::: :@:@:: @::::: :::::: :: :::::@ @:::::@:::#:::::@:::
| :::: :@:@:: @:::: ::::::: :: :::::@ : @:::::@:::#:::::@::::
| :::: :@:@:: @:::: ::::::: :: :::::@ : @:::::@:::#:::::@::::
| :::::: :@:@:: @:::: : :::::::: :: :::::@ :: :@:::::@:::#:::::@:::::
|:: :::: :@:@:: @:::: :: @::::::: :: :::::@ ::@ ::@:::::@:::#:::::@::::::
0 +----------------------------------------------------------------------->MB
0 152.0
```
## 分析 Makefile
閱覽 Makefile 有助於了解整個程式的架構，然而點開 Makefile 後發現~~根本看不懂~~需要花點時間來理解內容，以下會分段逐步理解 Makefile 的內容，許多用法在 [Makefile 語法和示範](https://hackmd.io/@sysprog/SySTMXPvl) 中已經有詳細示範，將不再重複說明
[完整的 Makefile 請參照 Github](https://github.com/KYG-yaya573142/lab0-c/blob/master/Makefile)
* 首次執行 `make` 會自動安裝 git hook:
直接 `make` 預設會執行第一個 target，也就是 `all` 這個項目，所以除了編譯 `qtest` 之外，還會執行安裝 git hook 的腳本
```
all: $(GIT_HOOKS) qtest
$(GIT_HOOKS):
@scripts/install-git-hooks
@echo
```
* `make VERBOSE=1` 可以顯示詳細編譯訊息
* `@` 的作用是該行的指令不會被顯示
* `@true` 則追加該行指令直接被視為成功的作用
* 因此 `" LD\t$@\n"` 這行如果前面從 `@printf` 改為 `@` 會出錯，需要追加 `true` 讓這行直接視為執行成功 (這個例來說就是該行直接無效但不出錯)
```
# Control the build verbosity
ifeq ("$(VERBOSE)","1")
Q :=
VECHO = @true
else
Q := @
VECHO = @printf
endif
qtest: $(OBJS)
$(VECHO) " LD\t$@\n"
$(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm
```
* Dependency 的部分相當有趣，查資料後發現本作業中使用類似 [Auto-Dependency Generation](http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/) 的方法來處理 dependency 的問題
* `deps := $(OBJS:%.o=.%.o.d)` 使用自動變數替換，也就是每個 dependency 檔案名稱都是物件檔結尾加上 .d
* `-MMD` 代表僅考慮 user header files 不包含 system head files，`-MF` 是指定輸出 dependency 檔案的名稱
* `-include $(deps)` 須放置在檔案的最後，告訴 `make` 需要 dependency 檔案的名稱，前置的 `-` 代表就算執行失敗也不強制結束 `make` 的執行
```
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
deps := $(OBJS:%.o=.%.o.d)
%.o: %.c
@mkdir -p .$(DUT_DIR)
$(VECHO) " CC\t$@\n"
$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF .$@.d $<
-include $(deps)
```
* sanitizer 的支援
* 很單純的加入相關的編譯參數
```
# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
# https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
LDFLAGS += -fsanitize=address
endif
```
* valgrind 的支援
* `2>&1` 指的是將 stderr 的輸出重新導向到 stdout
* `/dev/null` 概念類似黑洞，進去的東西都會消失
* `||` 代表若左邊執行出錯，就執行右邊的內容
* 因此 `valgrind_existence` 執行的意思就是 "檢查 valgrind 版本 (但無論成功失敗都不列出結果)，如果檢查失敗就顯示右邊的錯誤訊息"
* `$(MAKE)` 代表將這行當作 make 來執行，詳見 [Manual](https://www.gnu.org/software/make/manual/html_node/MAKE-Variable.html)
* `$(eval expression)` 會先將 expression 展開，接著再將 expression 的內容視為 Makefile 的一部分並執行，與直接將 expression 寫在 Makefile 的差別為，後面的 shell 指令 `mktemp` 只有在 `make valgrind` 時才會執行並取得檔案名稱，詳見 [Manual](https://www.gnu.org/software/make/manual/html_node/Eval-Function.html)
* `sed -i "s/alarm/isnan/g" $(patched_file)`，其中 `s/alarm/isnan/g` 不是路徑，是 `sed` 用來替換內容的表示法，這裡的意思是 "將 `$(patched_file)` 中的所有的 alarm 替換成 iasnan"，詳見 [Manual](https://www.gnu.org/software/sed/manual/html_node/The-_0022s_0022-Command.html)
* 由於 valgrind 會大幅度的增加程式的執行時間，將 `alarm` 去除可以避免在 `qtest` 中設置 timer，去除原先對執行時間的限制
* 相關的語法可以參閱 [sed - stream editor](http://manpages.ubuntu.com/manpages/precise/en/man1/plan9-sed.1.html) 以及 [the s command](https://www.gnu.org/software/sed/manual/html_node/The-_0022s_0022-Command.html) (感謝 [Randy870819](https://hackmd.io/@randy870819/system-prog-lab0) 提供)
```
valgrind_existence:
@which valgrind 2>&1 > /dev/null || (echo "FATAL: valgrind not found"; exit 1)
valgrind: valgrind_existence
# Explicitly disable sanitizer(s)
$(MAKE) clean SANITIZER=0 qtest
$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
cp qtest $(patched_file)
chmod u+x $(patched_file)
sed -i "s/alarm/isnan/g" $(patched_file)
scripts/driver.py -p $(patched_file) --valgrind
@echo
@echo "Test with specific case by running command:"
@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"
```
## [dudect](https://github.com/oreparaz/dudect)
dudect 以兩種不同類別的資料來測試程式的執行時間，再以統計的方式分析兩者的執行時間的平均值是否有差異，若無法證明平均值有差異，則程式的執行時間可能為常數 (constant time)
dudect 的優點是不需要執行平台的硬體資訊 (這也是本題可以使用虛擬機跑的原因之一)。執行的過程可以分為三個步驟
1. 量測執行時間
使用的資料分為固定資料及隨機資料兩種 (fix-vs-random test)，同時為了降低環境因素的影響，每次量測選定的資料種類也是隨機的，執行時間則是根據 CPU cycle 來計算
3. 後處理
每次量測時間後，可以在統計分析前先進行後處理，例如去除一定數值以外的資料 (cropping)，來避免因程式執行過程中被系統插斷造成的正偏差。另外，可以根據後面想執行的統計分析，先在此步驟先進行資料處理
5. 統計分析
dudect 使用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch's_t-test) 來分析兩種資料的結果，如果檢定結果無法否定 "兩種資料具有相同的平均數" 這個零假設 (null hypothesis)，就代表兩種資料很有可能具有一樣的平均數，也就是程式執行時間很可能是常數
#### t-test
* t-test 是一種假說檢定 (statistical hypothesis test)，指零假設 (null hypothesis) 成立時的任一檢定統計會具有 Student’s t-distribution
* Student's t-test 和 Welch's t-test 皆為雙樣本的 t-test 應用，Student's t-test 同時假設兩個母體 (population) 具有相同的變異數，Welch's t-test 則無此假設
* 本作業中使用的是 Welch's t-test，因為我們沒辦法得知母體的變異數
#### [Student’s t-distribution](https://zh.wikipedia.org/wiki/%E5%AD%A6%E7%94%9Ft-%E5%88%86%E5%B8%83#%E5%AD%A6%E7%94%9Ft-%E5%88%86%E5%B8%83%E7%BD%AE%E4%BF%A1%E5%8C%BA%E9%97%B4%E7%9A%84%E6%8E%A8%E5%AF%BC)
* 用於根據小樣本來估計 "呈常態分布且變異數未知的總體" 的平均值
* 自由度 $\nu$ 越大，t-distribution 越接近常態分佈
* 也簡稱為 t-distribution
### 分析本作業中如何實作 dudect
從 qtest.c 裡面可以看到使用 `is_insert_tail_const` 與 `is_size_const` 來判斷，其函數的定義在 dudect/fixture.c 內，由於整個程式的架構非常複雜，現階段先釐清整體實作的架構，許多輔助函數的實作之後再探討
#### `is_size_const`
```c=
bool is_size_const(void)
{
bool result = false;
t = malloc(sizeof(t_ctx));
for (int cnt = 0; cnt < test_tries; ++cnt) {
printf("Testing size...(%d/%d)\n\n", cnt, test_tries);
init_once();
for (int i = 0;
i <
enough_measurements / (number_measurements - drop_size * 2) + 1;
++i)
result = doit(1);
printf("\033[A\033[2K\033[A\033[2K");
if (result == true)
break;
}
free(t);
return result;
}
```
* `t_ctx` 是一個儲存統計用資料的資料結構，相關的意義可以在後續的 `t-push` 中得知
* mean 是平均值
* m2 是離均差之合 (aggregates of squared distance from the mean)
* n 是資料數量
```
typedef struct {
double mean[2];
double m2[2];
double n[2];
} t_ctx;
```
* 第一個迴圈 `for (int cnt = 0; cnt < test_tries; ++cnt)` 代表最多會進行 10 次測試，如果結果為真，會直接跳離迴圈 (也就是結果顯示為 constant time)
* `init_once` 會將 `t` 的所有資料成員初始化為 `0.0`，`q` 初始化為 `NULL`
* 實際的計算與量測在 `doit` 中實施
* `doit` 一次會進行 `(number_measurements - drop_size * 2)` 次的測試，而統計需求共需 `enough_measurements = 10000` 次測試數據
#### `doit`
```c=
static bool doit(int mode)
{
int64_t *before_ticks = calloc(number_measurements + 1, sizeof(int64_t));
int64_t *after_ticks = calloc(number_measurements + 1, sizeof(int64_t));
int64_t *exec_times = calloc(number_measurements, sizeof(int64_t));
uint8_t *classes = calloc(number_measurements, sizeof(uint8_t));
uint8_t *input_data =
calloc(number_measurements * chunk_size, sizeof(uint8_t));
if (!before_ticks || !after_ticks || !exec_times || !classes ||
!input_data) {
die();
}
prepare_inputs(input_data, classes);
measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
bool ret = report();
free(before_ticks);
free(after_ticks);
free(exec_times);
free(classes);
free(input_data);
return ret;
}
```
* `prepare_inputs(input_data, classes)`
* 總共準備 `number_measurements = 150` 個資料
* classes 的內容只會是 0 和 1 ，用來區分兩種資料類別
* `input_data` 的每個成員大小為 `chunk_size * sizeof(uint8_t)`，也就是 16 bytes
* class 0 的 `input_data` 的前兩個 bytes 會被設置為 0
* 在此函數內會一同隨機設置用來測試的字串 `static char random_string[100][8]`
* 產生隨機數值的方法應該是從[這裡](https://bench.cr.yp.to/tips.html)偷過來的
* `measure`
* `assert` 是一個保護函數 [(man assert)](http://man7.org/linux/man-pages/man3/assert.3.html)
* 根據 `mode` 的數值來判斷是要分析 `q_size` 還是 `q_insert_tail` ，另外這裡有用到 anonymous enum 的技巧 `enum { test_insert_tail, test_size }`
* 從 `for (size_t i = drop_size; i < number_measurements - drop_size; i++)` 可以看出實際使用的資料會從頭尾再扣除 `drop_size = 20`，查閱[原始 Github 專案](https://github.com/oreparaz/dudect/tree/master/src)並比對內容，這麼做的目的就是 dudect 步驟二的 cropping，只是本作業中有對 cropping 的時間點稍作修改
* 原始 Github 專案共使用 first order uncropped、cropped、second order uncropped 三種方式來計算最大 t 值，本作業中大幅度省略至只使用單一閥值來 cropping
* 為了避免和主測試函數的內容混淆，同時維持測試環境的一致性，這邊會先使用 `dut_new` 與 `dut_insert_head` 做出測試用的 linked-list
* 實際測試時間的函數被包在 `before_ticks[i] = cpucycles()` 與 `after_ticks[i] = cpucycles()` 之間，執行時間以 CPU clock cycles 當基準計算
* 由 `*(uint16_t *) (input_data + i * chunk_size) % 10000)` 可以看出字串插入的隨機數量是根據 `input_data` 的前兩個 bytes 決定，而且最多不超過 10000。同時由此可以看出 class 0 的數據實際上根本不會插入字串
* `differentiate`
* 計算執行時間 `exec_times[i] = after_ticks[i] - before_ticks[i]`
* `update_statistics`
* 選定納入使用的數據，並呼叫 `t-push` 對其進行前處理
* CPU cycle counter overflowed 的資料與 `drop_size` 涵蓋的資料會在此被過濾掉
* `t-push`
* 使用 [Welford's online algorithm](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm) 計算實行 Welch's t-test 所需的資料，計算結果儲存於 `t` 指向的資料結構中
* `report`
* 使用 `t_compute` 計算出 t 值，判斷是否在閥值範圍內並回傳判斷結果
#### `cpucycles`
```cpp=
static inline int64_t cpucycles(void)
{
#if defined(__i386__) || defined(__x86_64__)
unsigned int hi, lo;
__asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi));
return ((int64_t) lo) | (((int64_t) hi) << 32);
#else
#error Unsupported Architecture
#endif
}
```
* 執行時間以 CPU clock cycles 當基準計算
* 詳細方法可參閱 [Code Execution Times: IA-32/IA-64 Instruction Set Architecture](https://www.intel.com/content/www/us/en/embedded/training/ia-32-ia-64-benchmark-code-execution-paper.html) (現階段我還看不太懂 [asm](https://linux.die.net/man/3/inline_asm) 的用法)
#### `t_compute`
```c=
double t_compute(t_ctx *ctx)
{
double var[2] = {0.0, 0.0};
var[0] = ctx->m2[0] / (ctx->n[0] - 1);
var[1] = ctx->m2[1] / (ctx->n[1] - 1);
double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;
return t_value;
}
```
* 實際計算 [Welch’s t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 的函式
* 計算檢定量 $t \quad = \quad {\; \overline{X}_1 - \overline{X}_2 \; \over \sqrt{ \; {s_1^2 \over N_1} \; + \; {s_2^2 \over N_2} \quad }}$
* $\bar{X}$ 為平均值，也就是 `ctx->mean`
* $s^2$ 為標準差平方，也就是 `ctx->m2`
* $N$ 為資料數量，也就是 `ctx->n`
* 本作業直接以固定的 t 值 `t_threshold_moderate = 10` 進行雙尾檢定 (two-tail test)，也就是判斷 t 的絕對值是否在接受範圍內，來判斷是否為 constant time
* 閥值越大，[I 型錯誤](https://zh.wikipedia.org/wiki/%E7%AC%AC%E4%B8%80%E5%9E%8B%E5%8F%8A%E7%AC%AC%E4%BA%8C%E5%9E%8B%E9%8C%AF%E8%AA%A4) (執行時間被誤認為非常數) 的機率會降低，但 [II 型錯誤](https://zh.wikipedia.org/wiki/%E7%AC%AC%E4%B8%80%E5%9E%8B%E5%8F%8A%E7%AC%AC%E4%BA%8C%E5%9E%8B%E9%8C%AF%E8%AA%A4) (執行時間被誤認為常數) 的機率會增加
* 原先的 Welch’s t-test 需再算出自由度 $\nu$ 來獲得對應的 t-distribution，根據設定的信賴區間及 t-distribution 決定 t 的閥值，再進行雙尾檢定
$\nu \quad \approx \quad {{\left( \; {s_1^2 \over N_1} \; + \; {s_2^2 \over N_2} \; \right)^2 } \over{ \quad {s_1^4 \over N_1^2 \nu_1} \; + \; {s_2^4 \over N_2^2 \nu_2 } \quad }},\quad\nu_1 = N_1-1,\quad\nu_2 = N_2-1$
## RIO 套件 (Robust I/O)
[RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf)是 CS:APP 中提供的一種 system I/O [wrapper](https://en.wikipedia.org/wiki/Wrapper_library) 套件，其內容建立於原本的 `read` 與 `write` 之上，原始內容可詳見 [csapp.c](http://csapp.cs.cmu.edu/3e/ics3/code/src/csapp.c) 與 [csapp.h](http://csapp.cs.cmu.edu/2e/ics2/code/include/csapp.h)
RIO 套件具有以下特點
* 被 signal handler 中斷後 (會導致 [EINTR](http://man7.org/linux/man-pages/man2/read.2.html) 錯誤)，會自動嘗試重新執行，直到遇到 EOF 或是達到指定的讀取大小
* 具有 application-level buffer，可大幅降低實際呼叫 system call 的次數，進而提升效能
* 可以方便的用於 socket
* thread-safe (之後研讀 CS:APP 第 12 章會再探討並補充進來)
RIO 套件的精隨在於 `rio_read` 以及對應的 rio 結構體 `rio_t`
```cpp
#define RIO_BUFSIZE 8192
typedef struct {
int rio_fd; /* Descriptor for this internal buf */
int rio_cnt; /* Unread bytes in internal buf */
char *rio_bufptr; /* Next unread byte in internal buf */
char rio_buf[RIO_BUFSIZE]; /* Internal buffer */
} rio_t;
/*
* rio_read - This is a wrapper for the Unix read() function that
* transfers min(n, rio_cnt) bytes from an internal buffer to a user
* buffer, where n is the number of bytes requested by the user and
* rio_cnt is the number of unread bytes in the internal buffer. On
* entry, rio_read() refills the internal buffer via a call to
* read() if the internal buffer is empty.
*/
static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n)
{
int cnt;
while (rp->rio_cnt <= 0) { /* Refill if buf is empty */
rp->rio_cnt = read(rp->rio_fd, rp->rio_buf,
sizeof(rp->rio_buf));
if (rp->rio_cnt < 0) {
if (errno != EINTR) /* Interrupted by sig handler return */
return -1;
}
else if (rp->rio_cnt == 0) /* EOF */
return 0;
else
rp->rio_bufptr = rp->rio_buf; /* Reset buffer ptr */
}
/* Copy min(n, rp->rio_cnt) bytes from internal buf to user buf */
cnt = n;
if (rp->rio_cnt < n)
cnt = rp->rio_cnt;
memcpy(usrbuf, rp->rio_bufptr, cnt);
rp->rio_bufptr += cnt;
rp->rio_cnt -= cnt;
return cnt;
}
```
* 在使用 RIO 套件前，會先建立並初始化一個 `rio_t` 物件
* `rio_read` 在被呼叫後，會先檢查 `rio_t` 物件中的 buffer 是否還有內容可以被使用
* 若有 - 直接讀取 `rio_buf`
* 若無 - 呼叫 `read` 讀取最多至 8192 bytes 的內容至 `rio_buf`
* 也就是說使用者呼叫 `rio_read` 取得的內容總是會從 `rio_buf` 取得，`rio_read` 同時會負責更新 `rio_buf` 的內容
### `qtest` 使用 RIO 套件的考量點
`qtest` 使用 RIO 套件的優勢會體現於 trace files 的讀取，若使用無緩衝的 `read` 來讀取指令，需要重複以 `read` 讀取單個字元直到遇到 `\n` 為止，如此一來會因為頻繁的 system call 造成效能低落
改用 RIO 套件的方法後，會將整個 trace file 的內容存入 `rio_buf`，接著 `readline` 會從 `rio_buf` 內讀出指令來執行，只有當 `rio_buf` 內容都使用完畢 (也就是跑完整個 trace file 的內容)，才會再次將下一個 trace file 的內容完整存入 `rio_buf`
### `qtest` 實際使用 RIO 套件的方式
觀察 qtest.c 及 console.c 可歸納出整體的呼叫順序，`qtest` 首先會在 `run_console` 初始化 `rio_t` 物件的空間，接著 `cmd_select` 會負責從 `rio_buf` 取得輸入的字串並交給後續的 `interpret_cmd` 執行指令，`cmd_select` 中的 `readline` 則是實際讀取與更新 buffer 的函數 (等同於 RIO 套件的 `rio_read`)
```
main → run_console → cmd_select → interpret_cmd → parse_args
```
#### `run_console`
```cpp
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
return err_cnt == 0;
}
static bool push_file(char *fname)
{
int fd = fname ? open(fname, O_RDONLY) : STDIN_FILENO;
if (fd < 0)
return false;
if (fd > fd_max)
fd_max = fd;
rio_ptr rnew = malloc_or_fail(sizeof(rio_t), "push_file");
rnew->fd = fd;
rnew->cnt = 0;
rnew->bufptr = rnew->buf;
rnew->prev = buf_stack;
buf_stack = rnew;
return true;
}
```
* `rio_t` 物件在 `push_file` 內產生，但此時 `rio_buf` 還沒有內容
* 最後將產生的物件以 linked list 的方式插入 `buf_stack` 所指向 list
* 觀察 console.c 中定義的 `rio_t` 資料結構以及 `buf_stack` 指標的使用方式，可以發現 console 將每個 `rio_t` 物件以 stack 的邏輯在管理，這也是為何新增及刪除 `rio_t` 物件的函式名稱分別叫做 `push_file` 及 `pop_file`
```cpp
#define RIO_BUFSIZE 8192
typedef struct RIO_ELE rio_t, *rio_ptr;
struct RIO_ELE {
int fd; /* File descriptor */
int cnt; /* Unread bytes in internal buffer */
char *bufptr; /* Next unread byte in internal buffer */
char buf[RIO_BUFSIZE]; /* Internal buffer */
rio_ptr prev; /* Next element in stack */
};
static rio_ptr buf_stack;
```
#### `cmd_select`
流程略為複雜，直接以 flowchart 呈現其運作邏輯，`select` 的部分可參閱[下個章節的討論](#解釋-select-系統呼叫在本程式的使用方式)
```flow
st=>start: cmd_select
cond1=>condition: read_ready:
complete line
in rio_buf?
cond2=>condition: cmd_done:
buf_stack?
sub1=>subroutine: readline
(from rio_buf)
sub2=>subroutine: readline
(from file)
op1=>operation: select
op2=>operation: interpret_cmd
op3=>operation: interpret_cmd
op4=>operation: interpret_cmd
e=>end: end
st->cond1
cond1(yes)->sub1->op4(left)->cond1
cond1(no)->cond2(yes)->op1->sub2->op2->e
cond2(no)->e
```
* `interpret_cmd` 會呼叫 `parse_args` 來將 `readline` 回傳的內容解析為指令及參數，最後根據指令及參數呼叫 `interpret_cmda` 來執行該指令內容
* 執行命令的部分，[作業導讀](https://hackmd.io/@sysprog/linux2020-lab0#qtest-%E5%91%BD%E4%BB%A4%E7%9B%B4%E8%AD%AF%E5%99%A8%E7%9A%84%E5%AF%A6%E4%BD%9C)的部分已經說明得很清楚了
#### `readline`
```flow
st=>start: readline
cond1=>condition: rio_buf?
cond2=>condition: rio_buf?
cond3=>condition: \n?
op1=>operation: read:
update rio_buf
op2=>operation: read a char
from rio_buf
op3=>operation: test
op4=>operation: EOF:
pop_file
e=>end: end
st(right)->cond1
cond1(no, bottom)->op1->cond2
cond1(yes, right)->op2(right)->cond3
cond3(no)->cond1
cond3(yes)->e
cond2(no)->op4->e
cond2(yes)->op2
```
* 邏輯類似 RIO 套件的 `rio_read`
* 與 RIO 套件不同的地方是，被 signal 中斷而未讀取任何資料時 (`EINTR`)，**不會**自動重新執行 `read`，而會被判斷成 `EOF`
## 解釋 `select` 系統呼叫在本程式的使用方式
```cpp
int select(int nfds,
fd_set *readfds, fd_set *writefds, fd_set *exceptfds,
struct timeval *timeout);
```
`fd_set` 是一種儲存 file descriptor (以下簡稱為 fd) 編號的集合，例如 fd 集合為 {0, 2, 7} 的 `fd_set` 以 binary 顯示會是 10000101。`fd_set` 須配合下面幾種 macro 來管理
* `FD_ZERO(fd_set *set)` - 清空 set 內容
* `FD_SET(int fd, fd_set *set)` - 新增 fd 至 set
* `FD_CLR(int fd, fd_set *set)` - 將 fd 從 set 移除
* `FD_ISSET(int fd, fd_set *set)` - 確認 fd 是否可用 (在 `select` 返回後使用)
`select` 會暫停程式並監測 `fd_set` 清單中紀錄的 fd，直到其中至少有一個 fd 變成可使用的狀態，返回 "可用 fd 的數量"，並將相對應的 `fd_set` 清單內容修改為 "可用 fd 清單" (因此每次呼叫 `select` 前都須 `FD_ZERO` 初始化清單)
* 監測至最大編號為 nfds 的 fd
* 監測 readfds 中紀錄的 fd 是否可讀
* 監測 writefds 中紀錄的 fd 是否可寫
* 監測 exceptfds 中紀錄的 fd 是否有特殊狀態
* timeout 可以設定 `select` 要等待多久 [(詳見 man select)](http://man7.org/linux/man-pages/man2/select.2.html)
本作業中 `select` 使用在 `cmd_select` 內，當 `read_ready` 確認 `rio_buf` 無內容可用後，`select` 會暫停程式直到以下兩種情況發生
* 使用者輸入指令 (具體來說是按下的 ENTER 鍵)
* trace file 可被讀取 (**想不到哪種情況會產生這個情況**)
最後 `readline` 才會根據 `select` 的結果決定是否能從 fd 讀取資料
### `select` 於本作業中的必要性
以下列程式碼進行實驗
```cpp
int main(int argc, char *argv[])
{
int fds = STDIN_FILENO;
int nfds = fds + 1;
int result = 0;
fd_set readfds;
char line[10];
memset(line, 0x0, 10);
while (1) {
FD_ZERO(&readfds);
FD_SET(fds, &readfds);
select(nfds, &readfds, NULL, NULL, NULL);
if (FD_ISSET(fds, &readfds)) {
result = read(fds, line, 10);
line[result] = '\0';
printf("input: %s", line);
}
}
}
```
執行結果如下
```shell
test
input: test
hello
input: hello
```
但其實如果把 `select` 的部份去掉，輸出結果是一樣的，差別是
* 使用 `select` 時，程式會在 `select` 等待輸入，輸入後 `read` 會直接讀取剛剛輸入的數值
* 單獨使用 `read` 時，程式會在 `read` 等待，直到鍵入 ENTER 才會結束
同時我還進行了另一個實驗，目的是想要知道如果 `fork` 後 parent 和 child 都使用 `read` 來讀取輸入，會不會造成 race condition。測試的方式是執行程式後，等待一秒以上再輸入文字 (因為 parent 會先 `sleep(1)`)，此時 parent 與 child 皆執行到 `read` 的位置，且 child 比 parent 先執行 `read`
```cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/select.h>
#include <sys/types.h>
#include <unistd.h>
int main(int argc, char *argv[])
{
int fds = STDIN_FILENO;
int nfds = fds + 1;
int result = 0;
pid_t pid;
fd_set readfds;
char line[10];
memset(line, 0x0, 10);
if ((pid = fork()) == 0) { /* child runs the job */
FD_ZERO(&readfds);
FD_SET(fds, &readfds);
result = read(fds, line, 10);
line[result] = '\0';
printf("child input: %s", line);
} else { /* parent */
sleep(1);
FD_ZERO(&readfds);
FD_SET(fds, &readfds);
result = read(fds, line, 10);
line[result] = '\0';
printf("parent input: %s", line);
}
}
```
執行結果如下
```
child
child input: child
parent
parent input: parent
```
因此就算同時有兩個程式對同個 file descriptor 進行 `read`，不使用 `select` 仍不會產生混淆的狀態
根據上面的結果，我認為 `qtest` 中無需使用 `select`，單獨使用 `read` 也能達到一樣的結果
### 移除 qtest 中的 `select`
直接修改 console.c:598 將 `select` 的部分移除，測試結果發現無論是 `make test` 的分數，或是手動輸入指令測試，程式執行結果都找不到差別
```cpp=598
int result = 1; /* remove the usage of select() */
if (result <= 0)
return result;
infd = buf_stack->fd;
if (1) {
/* Commandline input available */
result--;
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
}
return result;
```
### 使用 `select` 的情境
在 [GNU - Waiting for Input or Output](https://www.gnu.org/software/libc/manual/html_node/Waiting-for-I_002fO.html) 中有提到 `select` 可以使用的情境，這同時可以說明為何 qtest 中不須使用 `select`，因為輸入端只有一個鍵盤，如果有額外的輸入端才必須使用 `select`
> **Sometimes a program needs to accept input on multiple input channels** whenever input arrives. For example, some workstations may have devices such as a digitizing tablet, function button box, or dial box that are connected via normal asynchronous serial interfaces.
> You cannot normally use read for this purpose, because this blocks the program until input is available on one particular file descriptor; input on other channels won’t wake it up. You could set nonblocking mode and poll each file descriptor in turn, but this is very inefficient.
> A better solution is to use the select function. This blocks the program until input or output is ready on a specified set of file descriptors, or until a timer expires, whichever comes first.
## 使用 [antirez/linenoise](https://github.com/antirez/linenoise) 強化 `qtest` 命令列功能
### linenoise 使用說明
linenoise 的 API 非常簡單，閱覽 [Github 的範例](https://github.com/antirez/linenoise/blob/master/example.c)就可以非常快上手
* 主要的 API，會將 `prompt` 的內容列出在 terminal，並把處理過後的輸入以字串的型態回傳
* 回傳的字串使用過後需 `free`
```cpp
char *linenoise(const char *prompt);
```
* 多行編輯功能
* `linenoiseSetMultiLine(0)` 為單行編輯
* `linenoiseSetMultiLine(1)` 為多行編輯
```cpp
linenoiseSetMultiLine(1);
```
* 歷史紀錄功能，讓使用者可以用上下鍵使用曾經輸入過的內容
* `linenoiseHistoryAdd` 將字串紀錄到歷史紀錄中
* `linenoiseHistorySetMaxLen` 可以設置歷史紀錄最大的長度
* `linenoiseHistoryLoad` 開啟儲存歷史紀錄的檔案，儲存歷史紀錄於檔案前須先開啟該檔案
* `linenoiseHistorySave` 儲存歷史紀錄於檔案
```cpp
int linenoiseHistoryAdd(const char *line);
int linenoiseHistorySetMaxLen(int len);
int linenoiseHistoryLoad(const char *filename);
int linenoiseHistorySave(const char *filename);
```
* 命令自動補完，使用者可以按下 `<TAB>` 鍵來根據已輸入的部分自動補完命令
* 在使用前需先以 `linenoiseSetCompletionCallback(completion)` 註冊 callback funtion
* 被註冊為 callback 的函式有規定的格式，同時內容包含自動補完的判斷依據，如下
```cpp
void completion(const char *buf, linenoiseCompletions *lc) {
if (buf[0] == 'h') {
linenoiseAddCompletion(lc,"hello");
linenoiseAddCompletion(lc,"hello there");
}
}
```
### 整合並應用 linenoise
#### 將 linenoise.[ch] 納入lab0
會特別提到這點是因為 git hook 的所有設定也會套用到 linenoise，也就是說執行 `git commit` 前會先對 linenoise.[ch] 做 clang-format 和 cppcheck，前者沒什麼問題，直接 `clang-format -i linenoise.[ch]` 就可以解決，後者則會需要對原始碼進行修改，為了節省時間我選擇直接修改腳本讓 cppcheck 忽略 linenoise.[ch]，scripts/pre-commit.hook 的修改內容如下
```
...
CPPCHECK_IGNORE="-ilinenoise/"
...
# static analysis
$CPPCHECK $CPPCHECK_IGNORE $CPPCHECK_OPTS >/dev/null
if [ $? -ne 0 ]; then
...
```
#### 在 qtest 中使用 linenoise
原本的 `cmd_select` 會先 `select` 確認 fd 是否可用，然後才使用 `readline` 讀取指令。如果直接改成使用 `select` + `linenoise` 會導致指令需要輸入兩次 (準確來說是第一次的輸入會被 `linenoise` 捨棄)，因此若要維持 `select` 的作用並同時使用 `linenoise`，勢必要修改 `linenoise` 的原始碼。根據[前面的討論結果](#select-於本作業中的必要性)，我決定當 fd 為 stdin 時，不使用 `select` 並直接 `linenoise` 來讀取輸入的指令 (雖然這樣就失去 `cmd_select` 本來名稱所代表的用途)
實作時有幾點注意事項
* 需將 linenoise 回傳的字串結尾改成 `\n\0` (因為原本的 lab0 會根據 `\n` 來判斷是否為完整的輸入，而 linenose 預設結尾不含 `\n`)
* linenoise 回傳的字串是使用 [`strdup`](http://man7.org/linux/man-pages/man3/strdup.3p.html) 產生的，記得 `free`
* 也可以不使用 `linenoiseHistorySave`，只是這樣每次執行 qtest 時不會有上次的歷史紀錄
```cpp
int cmd_select(int nfds,
fd_set *readfds,
fd_set *writefds,
fd_set *exceptfds,
struct timeval *timeout)
{
...
/* need to read command from fd */
infd = buf_stack->fd;
if (infd != STDIN_FILENO) { /* use trace files */
/* prepare necessary data for select */
if (!readfds)
readfds = &local_readset;
FD_SET(infd, readfds);
if (infd >= nfds)
nfds = infd + 1;
if (nfds == 0)
return 0;
int result = select(nfds, readfds, writefds, exceptfds, timeout);
if (result <= 0)
return result;
if (readfds && FD_ISSET(infd, readfds)) {
/* Commandline input available */
FD_CLR(infd, readfds);
result--;
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
}
return result;
} else { /* use linenoise (stdin) */
cmdline = linenoise(prompt);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(
"linenoise/history.txt"); /* Save the history on disk. */
int len = strlen(cmdline);
if (len >= (RIO_BUFSIZE - 2)) /* prevent overflow */
len = RIO_BUFSIZE - 2;
memcpy(linebuf, cmdline, len + 1); /* copy content to inter buffer */
/* the original string got from linenoise is ended with \0,
* change it to \n\0. */
linebuf[len] = '\n';
linebuf[len + 1] = '\0';
free(cmdline); /* free the memory allocated by linenoise */
cmdline = len ? linebuf : NULL;
if (cmdline)
interpret_cmd(cmdline);
}
return 0;
}
```
自動補完與歷史紀錄的功能需在使用前先設定好 callback，這個部分寫在 qtest.c 中，於 `run_console` 前執行
```cpp
void completion(const char *buf, linenoiseCompletions *lc)
{
if (buf[0] == 'f') {
linenoiseAddCompletion(lc, "free");
}
if (buf[0] == 'h') {
linenoiseAddCompletion(lc, "help");
}
...
if (buf[0] == 't') {
linenoiseAddCompletion(lc, "time");
}
}
static void linenoise_init()
{
/* Set the completion callback. This will be called every time the
* user uses the <tab> key. */
linenoiseSetCompletionCallback(completion);
/* Load history from file. The history file is just a plain text file
* where entries are separated by newlines. */
linenoiseHistoryLoad(
"linenoise/history.txt"); /* Load the history at startup */
}
int main(int argc, char *argv[])
{
...
queue_init();
init_cmd();
console_init();
linenoise_init();
...
ok = ok && run_console(infile_name);
...
}
```
## 現有程式的缺陷
在繪製 `readline` 的流程圖的時候，我發現 `readline` 不像 RIO 套件有考慮到被 signal 中斷的狀況 (可參考 [RIO 套件](#RIO-套件-Robust-IO)中的 `rio_read`)，這會造成一個邏輯問題
* 被 signal 中斷而**未讀取任何資料**時 (`EINTR`)，**不會**自動重新執行 `read`，而會被判斷成 `EOF`
## 實作小型終端機命令解譯器 (待補)
我認為可以將此次作業的經驗用於改善以前寫的 [CS:APP shell lab](https://hackmd.io/1sOTAV6DRVm5E7UpYdBk1g)，但短時間內沒辦法完成
TODO list:
* 改善 git commit 的使用方式 (也應該考量如何加入 [git-good-commit](https://github.com/tommarshall/git-good-commit))
* 改善 signal handler 的使用方式 (例如考量使用 `siglongjmp`)，我覺得我原先寫的 signal handler 肯定爛透了，整體的流程也該重新考慮
* 應該更詳細理解 [Asynchronous Signal Safety](http://man7.org/linux/man-pages/man7/signal-safety.7.html) 如何達成
* 重新編輯筆記，使之具有更高的可讀性
## 參考資料 (待整理)
[flowchart.js](https://github.com/adrai/flowchart.js)
###### tags: `linux 2020` `csapp`
Google Drive
Gist
Clipboard
Sign in with Wallet
