# 2021q1 Homework1 (lab0)
contributed by < [`toastcheng`](https://github.com/toastcheng) >
###### tags: `linux2021`
## TODO
- [x] 函式實作
- [x] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
- [x] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤
- [ ] 並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- [x] 在 `qtest` 中實作 [coroutine](https://en.wikipedia.org/wiki/Coroutine)，並提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
* 可嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)，將 `FORK_COUNT` 變更為 `0`，並以 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 取代原本的 fork 系統呼叫
- [ ] 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) :arrow_forward: 為避免「舉燭」，請比照 `qtest` 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)
- [ ] 說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
- [ ] 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request
## 0. 環境
首先來設置作為開發的環境，手邊較為方便的電腦有一台 Macbook Air，雖和 Linux 同是 Unix-like 的作業系統，但許多相關套件都略有出入，因此最初想使用 Virtualbox 來使用虛擬機，後來考量電腦負擔太重，轉而嘗試以容器化的方式可以更為輕量，因此用 docker 來準備需要的 linux 環境。
```dockerfile
FROM ubuntu:20.04
RUN apt update
RUN apt install \
-y \
--no-install-recommends \
build-essential \
git \
clang-format \
cppcheck \
aspell \
colordiff \
valgrind
```
build 完 docker image 後將需要的檔案掛載到容器中 (`-v <host path>/<container path>`) 執行 bash 便能開始進行開發。
```bash
$ docker build . -t lab0
$ docker run -v /Users/tushicheng/development/:/data -it lab0 bash
# uname -a
Linux 988da3fcde51 4.19.121-linuxkit #1 SMP Tue Dec 1 17:50:32 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
```
## 1. 函式實作
首先嘗試將尚未實作的函式完成，讓這個專案的基本功能可以運作。觀察 `queue.h` 可以一覽我們期望這個佇列 (queue) 資料結構 `queue_t` 的長相（此將註解省略）：
```c=
typedef struct {
list_ele_t *head;
} queue_t;
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
```
`queue_t` 為一個含有連結串列 `list_ele_t` 的結構體，每個節點的值是字元指標，或俗稱的 C-style string，`queue_t` 應該支援的函式如下：
1. `q_new` 初始化，建構函式
2. `q_free` 解構函式
3. `q_insert_head` 在連結串列的開頭插入一個節點
4. `q_insert_tail` 在連結串列的尾巴插入一個節點
5. `q_remove_head` 移除連結串列的開頭節點
6. `q_size` 回傳連結串列的節點個數 (大小)
7. `q_reverse` 將連結串列的順序倒排
8. `q_sort` 將連結串列的節點依值的順序排序
### `q_size`
commit: [Add members to queue_t and impl insert head/tail](https://github.com/ToastCheng/lab0-c/commit/6f9288c63c8839785dd0b3c2c265914953bb98c7)
先從較為簡單的函式開始，`q_size` 需要回傳此佇列的大小，在最單純的情況，若我們只有連結串列的開頭 `head`，則必定需要花 $O(n)$ 的時間走訪各個節點直到最後一個節點的 `next` 為 `NULL`，方能知道佇列的大小。
但每一次花費線性時間來取得佇列大小並不合理，最直接的方式是用一個額外的整數變數 `size` 來將佇列的大小資訊暫存起來，若佇列大小因為操作而改變（如 `q_insert_head`、`q_remove_head`），則我們一併修改 `size` 即可。
將 `size` 加入 `queue_t` ：
```c=
typedef struct {
list_ele_t *head;
int size;
} queue_t;
```
則 `q_size` 只需要將佇列的 `size` 回傳即可。
```c=
int q_size(queue_t *q)
{
return q->size;
}
```
但若是佇列 `q` 為空，硬是去對其取值會引發 segmentation fault。
```
cmd> free
q = NULL
cmd> size
Warning: Calling size on null queue
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
Aborted
```
因此需要做一次額外的檢查，若 `q` 根本沒有初始化，也回傳 0。
```c=
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
`// TODO inconsistence`
### `q_insert_tail`
`q_insert_tail` 將字串 `s` 加進佇列`q` 的尾巴。最單純的實作是先從佇列開頭一路走訪到最後一個節點，再將新節點加入，但這會跟 `q_size` 有一樣的問題，僅僅是加入一個節點卻要 $O(n)$ 的時間複雜度。用相同的概念，我們可以再次在 `queue_t` 加入新變數 `tail` 來紀錄最後一個節點的位址，如此便省略從頭走訪的時間。
```c=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
`q_insert_tail` 的主要實作很單純：將新的節點 `newt` (new tail) 指派給目前佇列的最後一個節點 `q->tail->next = newt`。
但其中有許多要注意的狀況：
1. `q` 若為空值需要回傳 `false`。
2. 新節點 `newt` 若因為 malloc 失敗而為空值要回傳 `false`。
3. 複製字串 `s` 時若失敗要回傳 `false`，並將本來已分配給 `newt` 的記憶體回收。
4. 若佇列 `q` 尚無任何節點，`q->head` 和 `q->tail` 同為空值，則要將兩者都指派為 `newt`。
5. 更新佇列的大小 `q->size++`。
```c=
bool q_insert_tail(queue_t *q, char *s)
{
// case 1.
if (q) {
list_ele_t *newt = malloc(sizeof(list_ele_t));
// case 2.
if (newt) {
newt->next = NULL;
size_t size = strlen(s) + 1;
newt->value = malloc(sizeof(char) * size);
// case 3.
if (newt->value) {
snprintf(newt->value, size, "%s", s);
// case 4.
if (!q->tail) {
q->head = newt;
q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
// case 5.
q->size++;
return true;
}
free(newt);
}
}
return false;
}
```
一開始並沒有顧及 `malloc` 回傳值為空的狀況，閱讀 man page [malloc (3)](https://man7.org/linux/man-pages/man3/malloc.3.html) 可以知道若是想分配的記憶體超過 `RLIMIT_AS` 或 `RLIMIT_DATA` 便會引發 `ENOMEM` 記憶體不足的錯誤，雖然在現代的電腦開發環境，很難觸碰到這個極限，但許多[嵌入式系統的開發](https://stackoverflow.com/questions/9101597/under-what-circumstances-can-malloc-return-null#:~:text=1-,Yes.,you%20might%20write%20in%20it.)中，因為資源較為有限，因此這個限制會低得許多。
```
calloc(), malloc(), realloc(), and reallocarray() can fail with
the following error:
ENOMEM Out of memory. Possibly, the application hit the
RLIMIT_AS or RLIMIT_DATA limit described in getrlimit(2).
```
那在我的機器上需要跟 `malloc` 要求多少記憶體才會引發 `ENOMEM` 呢？按照 man page的說明，繼續去找 [getrlimit (2)](https://man7.org/linux/man-pages/man2/getrlimit.2.html) 發現可以用 `getrlimit` 來使用系統呼叫：
```c=
#include <sys/resource.h>
int main() {
struct rlimit rlp;
getrlimit(RLIMIT_NPROC, &rlp);
printf("max: %lu\n", rlp.rlim_max);
printf("cur: %lu\n", rlp.rlim_cur);
...
}
```
`rlimit` 是一個帶有 soft limit、hard limit 的結構體。使用 `getrlimit` 時第一個參數傳入不同的 flag 便能得到 kernel 對不同資源的限制為何（結果會放在 `rlimit` 中）。
例如在這個作業中我想知道一個 `process` 允許被分配多少記憶體，就帶入 `RLIMIT_NPPROC` 這個 flag 即可。結果為：
```shell
max: 18446744073709551615
cur: 18446744073709551615
```
為一個非常大的值，這個值也剛好是 $2^{64}-1$。
但就算 `malloc` 成功，並不代表記憶體真的夠用，繼續閱讀 [malloc (3)](https://man7.org/linux/man-pages/man3/malloc.3.html) 會知道，kernel 有 overcommit 的機制，當要讀寫時發現記憶體真的不夠用時，process 便會被 OOM killer (Out of memory killer) 終止。
另外還有幾點實作的考量：
1. `strlen`
本來的實作是一個一個 byte 讀取，直到讀到 `\0` 終止。
```c=
size_t size = 1;
for (char *it = s; *it != '\0'; it++)
size++;
```
起初很確信必然得這樣才能知道字串的長度（畢竟也沒有別的資訊了），但在 [你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics) 中發現 `strlen` 還是比較快的實作方式，因為我們確實不必一次只讀一個 byte，可以一次讀 4 byte 再檢查其中有無 `\0`！
2. `strcpy`
`strcpy` 已被指出是不安全的函式，[Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 中說明 `strcpy` 的問題在於沒有指出 buffer size 大小，如果字串複製的目的地太小，那複製後可能會蓋到其他的記憶體區段，也就是 Buffer overflow。
```c=
char str1[10];
char str2[]="abcdefghijklmn"; // size: 15
strcpy(str1,str2);
printf("str1: %s\n", str1);
printf("%s\n", str2);
printf("%lu\n", strlen(str1));
printf("%lu\n", strlen(str2));
```
```shell
str1: abcdefghijklmn
str2: klmn
size 1: 14
size 2: 4
```
這裡的問題在於 `str1` 的長度只有 10，`str2` 多出來的 5 字元寫到了自己所在的空間。
```graphviz
digraph G {
rankdir=LR;
node [shape=record]
N [label="{<s1>||||||||||<s2>a|b|c|d|e|f|...|n|\\0}"]
s1 [label="str1" shape=plaintext]
s2 [label="str2" shape=plaintext]
s1 -> N:s1;
s2 -> N:s2;
}
```
`strcpy` 後 `str2` 的記憶體空間被竄改了。
```graphviz
digraph G {
rankdir=LR;
node [shape=record]
N [label="{<s1>a|b|c|d|e|f|g|h|i|j|<s2>k|l|m|n|\\0|f|...|n|\\0}"]
s1 [label="str1" shape=plaintext]
s2 [label="str2" shape=plaintext]
s1 -> N:s1;
s2 -> N:s2;
}
```
這也是為什麼 `strlen(str2)` 會變成 4，因為 `\0` 被寫到 `str2` 的第五個字元，後面的字元便被截掉了。
按照 CERN 的建議，換成 `snprintf` 即可有較為安全可預測的行為，第二個參數明顯的確保不會寫超過 10 bytes：
```c=
char str1[10];
char str2[]="abcdefghijklmn"; // size: 15
snprintf(str1, 10, "%s", str2);
printf("str1: %s\n", str1);
printf("%s\n", str2);
printf("%lu\n", strlen(str1));
printf("%lu\n", strlen(str2));
```
```shell
str1: abcdefghi
str2: abcdefghijklmn
size 1: 9
size 2: 14
```
當然如果故意把 buffer size 設超過 `str1` 的大小也是會有同樣 buffer overflow 問題，。
```c=
snprintf(str1, 15, "%s", str2);
```
### `q_insert_head`
`q_insert_head` 將字串 `s` 加進佇列`q` 的開頭，跟 `q_insert_tail` 的實作相似
。函式的邏輯：將新的節點 `newh` (new head) 的 `next` 指向佇列當前的 `head`，並將佇列的 `head` 更新為 `newh`。
須要注意的地方跟 `q_insert_tail` 相似，因此不再贅述。
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (q) {
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (newh) {
size_t size = strlen(s) + 1;
newh->value = malloc(sizeof(char) * size);
if (newh->value) {
snprintf(newh->value, size, "%s", s);
newh->next = q->head;
q->head = newh;
if (!q->tail)
q->tail = newh;
q->size++;
return true;
}
free(newh);
}
}
return false;
}
```
### `q_new`
這個函式將初始化一個佇列 `queue_t`，並將其變數也一併初始化並回傳，若沒有將指標 `head` 和 `tail` 設為空值，預設會是不確定 (indeterminate)，可以見這篇[討論](https://stackoverflow.com/questions/12253191/is-it-necessary-to-call-pointer-null-when-initializing)。因此後續確認節點存不存在的操作如 `if (q->head) { ... }` 實際上是會執行的，也就是說會認為 `q->head` 是有值的，而嘗試去 dereference 而發生錯誤。
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
return NULL;
}
```
### `q_free`
將 `q` 所使用的記憶體釋放掉，也要將其管理的連結串列一併釋放，包括每個節點的字串。
```c=
void q_free(queue_t *q)
{
if (q) {
list_ele_t *it = q->head;
while (it) {
list_ele_t *tmp = it;
it = it->next;
free(tmp->value);
free(tmp);
}
free(q);
}
}
```
### `q_remove_head`
`q_remove_head` 這個函式將第一個節點移除、釋放其記憶體空間，並將該節點的字串複製到給定的字元指標 `sp`。最一開始我沒有想太多，利用 `memcpy` 來處理 `bufsize` 空間不夠的狀況，為了滿足 `sp` 為一個大小最大為 `bufsize - 1` 的字串，將前 `bufsize - 1` 個字元複製過去，最後再補上終止字符 `\0`。
```c=
size_t size = strlen(q->head->value) + 1;
if (size > bufsize) {
memcpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
memcpy(sp, q->head->value, size);
}
```
但後來參考了前面提及的 `snprintf`，可以將其改寫成較為簡潔的形式：
```c=
size_t size = strlen(q->head->value) + 1;
snprintf(sp, size > bufsize ? bufsize : size, "%s", q->head->value);
```
最後將開頭的節點釋放記憶體，並減少佇列的大小 `q->size--`。
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q && q->size > 0) {
if (sp) {
size_t size = strlen(q->head->value) + 1;
snprintf(sp, size > bufsize ? bufsize : size, "%s", q->head->value);
}
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
return false;
}
```
### `q_reverse`
`q_reverse` 將連結串列的順序顛倒。首先將原本的 `head` 及 `tail` 保存下來，另外宣告兩個指標 `prev` 和 `cur`。用 `cur` 從 `head` 開始走訪各個節點， `prev` 則是如其名「跟在」 `cur` 後面，`cur` 將每個走訪到的節點的 `next` 都指向 `prev`，以此達到顛倒順序的效果，最後再將 `q->head` 及 `q->tail` 對調。
```c=
void q_reverse(queue_t *q)
{
if (q) {
list_ele_t *h = q->head;
list_ele_t *t = q->tail;
list_ele_t *prev = NULL;
list_ele_t *cur = q->head;
while (cur) {
list_ele_t *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
q->head = t;
q->tail = h;
}
}
```
### `q_sort`
`q_sort` 對連結串列做遞增排序。一開始我使用 quicksort 實作，但發現測試的條件有隨機的輸入以及「遞減」的輸入，對於 quicksort 來說如果 pivot 選擇不當，會讓 divide and conquer 效果大大降低，最壞情況是 $O(n^2)$ 的時間複雜度，並不適合這個情境，因此我考量使用 merge sort 來實作，無論是平均或是最壞情況都有 $O(n \log n)$ 的複雜度。
`q_sort` 將連結串列交由 `mergesort` 進行排序，排序完後再從新的 `head` 開始找到最後一個節點，將其指派給 `tail`。而對於 `q` 為空值或是大小小於 2 不會做任何操作。
```c=
void q_sort(queue_t *q)
{
if (q && q->size > 1) {
mergesort(&q->head);
list_ele_t *tmp = q->head;
while (tmp->next) {
tmp = tmp->next;
}
q->tail = tmp;
}
}
```
`mergesort` 利用快慢指標，找到連結串列位於中間的節點，將其一分為二遞迴地執行，最後再將兩個連結串列用 `merge` 組合成排序完成的新串列。
```c=
void mergesort(list_ele_t **head)
{
if ((*head)->next) {
list_ele_t *fast = *head;
list_ele_t *slow = *head;
list_ele_t *prev = NULL;
while (fast && fast->next) {
fast = fast->next->next;
prev = slow;
slow = slow->next;
}
if (prev)
prev->next = NULL;
mergesort(head);
mergesort(&slow);
list_ele_t *result = NULL;
merge(&result, *head, slow);
*head = result;
}
}
```
`merge` 則是真正進行合併的地方，將兩個連結串列從頭一一比對，`*result` 指向值較小的節點，並前進到下一個節點，較大的節點將繼續做下一輪的比較。直到其中一個連結串列走到盡頭，將連結串列`*result` 依序指向另一個連結串列剩下的節點。
```c=
void merge(list_ele_t **result, list_ele_t *left, list_ele_t *right)
{
while (left && right) {
if (strcmp(left->value, right->value) > 0) {
*result = right;
right = right->next;
} else {
*result = left;
left = left->next;
}
result = &((*result)->next);
}
while (left) {
*result = left;
left = left->next;
result = &((*result)->next);
}
while (right) {
*result = right;
right = right->next;
result = &((*result)->next);
}
}
```
### 改進 merge sort
一開始我用了陣列的方式去思考，很習慣地在 `merge` 函式中、用
```c=
while (left) {
*result = left;
left = left->next;
result = &((*result)->next);
}
while (right) {
*result = right;
right = right->next;
result = &((*result)->next);
}
```
去處理剩餘的節點，但驚覺這裡可以優化，多虧連結串列的彈性，我能直接將剩餘的連結串列直接接在 `*result` 之後：
```c=
*result = right ? right : left;
```
短短一行便能完成，簡潔多了。
實作完以上函式，跑 `make test` 便能通過所有測試！
```shell
$ make test
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
--- trace-05-ops 5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
## 2. 透過 AddressSanitizer 分析
加入 `SANITIZER=1` 的 flag 重新 `make` 一次，在 `qtest` 裡下 `help` 後給出錯誤：
```shell
==574==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55e284086400 at pc 0x55e28406f7bd bp 0x7ffdc7839ca0 sp 0x7ffdc7839c90
READ of size 4 at 0x55e284086400 thread T0
#0 0x55e28406f7bc in do_help_cmd /data/week1/lab0-c/console.c:307
#1 0x55e28406f8d0 in interpret_cmda /data/week1/lab0-c/console.c:221
#2 0x55e2840700b5 in interpret_cmd /data/week1/lab0-c/console.c:244
#3 0x55e2840717f8 in run_console /data/week1/lab0-c/console.c:660
#4 0x55e28406e3e5 in main /data/week1/lab0-c/qtest.c:780
#5 0x7f94ca40b0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x55e28406bb8d in _start (/data/week1/lab0-c/qtest+0x8b8d)
0x55e284086401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55e284086400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /data/week1/lab0-c/console.c:307 in do_help_cmd
```
錯誤訊息中寫到 `echo` 這個全域變數似乎跟某個位在 `0x55e284086401` 的局域變數碰撞上了，很可能是 buffer overflow 所致，在某個 buffer 寫入超過其大小的 byte。
觀察 `echo`，宣告在 59 行：
```c=
static bool echo = 0;
```
其他被使用的方式只有正常的讀寫，除了 108 行：
```c=
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
將布林指標轉型成整數指標，兩種指標指向的記憶體位址大小不同，很可能是在寫入 `echo` 時溢出了，考量到 `echo` 接受來自命令列的輸入，將之設成 `int` 也不會影響其使用，因此便將宣告改成：
```c=
static int echo = 0;
```
重跑 `make SANITIZER=1`，得到新的錯誤訊息：
```shell
==2691==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55b42e086620 at pc 0x55b42e06d7b7 bp 0x7fff80b42ca0 sp 0x7fff80b42c90
READ of size 4 at 0x55b42e086620 thread T0
#0 0x55b42e06d7b6 in do_help_cmd /data/week1/lab0-c/console.c:307
#1 0x55b42e06d8ca in interpret_cmda /data/week1/lab0-c/console.c:221
#2 0x55b42e06e0af in interpret_cmd /data/week1/lab0-c/console.c:244
#3 0x55b42e06f7f5 in run_console /data/week1/lab0-c/console.c:660
#4 0x55b42e06c3e5 in main /data/week1/lab0-c/qtest.c:780
#5 0x7fce78de30b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x55b42e069b8d in _start (/data/week1/lab0-c/qtest+0x8b8d)
0x55b42e086621 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x55b42e086620) of size 1
'simulation' is ascii string ''
```
這次將焦點放在 `simulation` 上，同樣為一個布林變數，但 `simulation` 並非靜態變數，意思是在其他目標檔中這個變數也是可見的，所以需要連同 `console.h` 中的宣告一併修改，改成 `int simulation` 之後再 `make SANITIZER=1` 一次，問題便解決了。
[AddressSanitizer Algorithm](https://github.com/google/sanitizers/wiki/AddressSanitizerAlgorithm) 上針對 AddressSanitizer 的幾個核心功能做的簡短說明
## 3. 透過 Valgrind 分析
用 `make valgrind` 來使用 Valgrind 分析，可以發現到很多 still reachable 的記憶體區塊。
```shell
scripts/driver.py -p /tmp/qtest.Uu8zU3 --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==2786== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==2786== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2786== by 0x4A3E50E: strdup (strdup.c:42)
==2786== by 0x1100D3: linenoiseHistoryAdd (linenoise.c:1236)
==2786== by 0x110C66: linenoiseHistoryLoad (linenoise.c:1325)
==2786== by 0x10C22C: main (qtest.c:769)
==2786==
==2786== 80 bytes in 19 blocks are still reachable in loss record 2 of 3
==2786== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2786== by 0x4A3E50E: strdup (strdup.c:42)
==2786== by 0x110047: linenoiseHistoryAdd (linenoise.c:1236)
==2786== by 0x110C66: linenoiseHistoryLoad (linenoise.c:1325)
==2786== by 0x10C22C: main (qtest.c:769)
==2786==
==2786== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==2786== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2786== by 0x110093: linenoiseHistoryAdd (linenoise.c:1224)
==2786== by 0x110C66: linenoiseHistoryLoad (linenoise.c:1325)
==2786== by 0x10C22C: main (qtest.c:769)
==2786==
--- trace-01-ops 6/6
...
```
為避免被輸出訊息淹沒，可以分別跑不同的測試：
```shell
scripts/driver.py --valgrind -t 01
```
使用不同的測試資料，都是出現 `still reachable` 的訊息，可能意味著記憶體並沒有釋放。可以感受到 Valgrind 非常強大，在執行時期檢查記憶體使用情形，還能精確給出發生問題的行數。根據輸出資訊發現每一個測試結果是類似的，都是
1. `linenoiseHistoryAdd`
```c=
history = malloc(sizeof(char *) * history_max_len);
```
2. `strdup`
```c=
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older line. */
linecopy = strdup(line);
```
看起來都是跟 `history` 有關，所以先從 `history` 被釋放的地方找起，可以發現只有 `freeHistory` 這個函式會釋放記憶體，所幸釋放的路徑沒有太複雜，呼叫 `freeHistory` 的也只有 `linenoiseAtExit` 一個函式。
繼續觀察會發現整個函式呼叫的順序如下：
```
linenoise --> linenoiseRow --> enableRawMode --> atexit(linenoiseAtExit)
```
而 [atexit(3)](https://man7.org/linux/man-pages/man3/atexit.3.html) 是用來註冊當程式結束時要執行的函式。因此只要這個函式被呼叫到，`history` 應該要能被釋放。
```c=
static int enableRawMode(int fd)
{
struct termios raw;
if (!isatty(STDIN_FILENO))
goto fatal;
if (!atexit_registered) {
atexit(linenoiseAtExit);
...
}
static void linenoiseAtExit(void)
{
disableRawMode(STDIN_FILENO);
freeHistory();
}
```
直到看到 `run_console` 便豁然開朗，在 `has_infile = true` 的情況下，是不會去呼叫到 `linenoise` 的。
```c=
bool run_console(char *infile_name)
{
...
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
解決的方式有二，一是將 `history` 正確釋放，二是不要去分配記憶體給他。前者因為 `history` 及對應的釋放函式都是 `static` 屬性，要改動 `linenoise.c` 及 `linenoise.h`，相對牽動的檔案比較多，而且跑檔案並沒有明顯紀錄歷史操作的需求，因此採取後者：若是跑檔案的模式 (`-f`)，則不分配記憶體給 `history`。
```c=
if (!infile_name) {
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
}
```
這樣便能順利通過 `make valgrind`。
```shell
(... 上略)
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.Nv2TGq --valgrind -t <tid>
```
### 使用 `massif` 視覺化觀察
`valgrind --tool=massif ./qtest -f traces/trace-01-ops.cmd`
在 simulation 模式下，只會執行 `is_insert_tail_const` 及 `is_size_const` 這兩個函式，搭配 `trace-17-complexity.cmd` 來觀察：
`// TODO`
## 4. 實作 web server 及 coroutine
先試著玩玩 `tiny-web-server`。
```shell
root@35b88cfa2929:/data/week1/tiny-web-server# make
cc -Wall -O2 -o tiny tiny.c
root@35b88cfa2929:/data/week1/tiny-web-server# ./tiny
serve directory '/data/week1/tiny-web-server'
listen on port 9999, fd is 3
child pid is 25
child pid is 26
child pid is 27
child pid is 28
```
看看 localhost:9999，可以發現伺服器正常運作！
首先找出 `tiny-web-server` 監聽 port 9999 上流量以及對應 handler 的部分。
很快可以把範圍縮小到 `process`、`handle_directory_request` 函式。
觀賞一下 `process` 函式：
```c=
void process(int fd, struct sockaddr_in *clientaddr) {
#ifdef LOG_ACCESS
printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
http_request req;
parse_request(fd, &req);
struct stat sbuf;
int status = 200, ffd = open(req.filename, O_RDONLY, 0);
if(ffd <= 0) {
status = 404;
char *msg = "File not found";
client_error(fd, status, "Not found", msg);
} else {
fstat(ffd, &sbuf);
if(S_ISREG(sbuf.st_mode)) {
if (req.end == 0) {
req.end = sbuf.st_size;
}
if (req.offset > 0) {
status = 206;
}
serve_static(fd, ffd, &req, sbuf.st_size);
} else if(S_ISDIR(sbuf.st_mode)) {
status = 200;
handle_directory_request(fd, ffd, req.filename);
} else {
status = 400;
char *msg = "Unknow Error";
client_error(fd, status, "Error", msg);
}
close(ffd);
}
#ifdef LOG_ACCESS
log_access(status, clientaddr, &req);
#endif
}
```
開頭 3 行是寫入 log，第 4 行將請求剖析成可用的結構體。第 8 行之後是將使用者的請求路徑用 `open` 打開，`S_ISREG` 查詢 man page [inode (7)](https://man7.org/linux/man-pages/man7/inode.7.html) 中意思是 `is it a regular file?`。 可以知道這裡是判斷該檔案合不合法的邏輯，若是合法檔案則由 `serve_static` 來處理，若是目錄，則由 `handle_directory_request` 處理。
接著看一下 `serve_static` 是如何處理客戶端的請求：
```c=
void serve_static(int out_fd, int in_fd, http_request *req,
size_t total_size) {
char buf[256];
if (req->offset > 0) {
sprintf(buf, "HTTP/1.1 206 Partial\r\n");
sprintf(buf + strlen(buf), "Content-Range: bytes %lu-%lu/%lu\r\n",
req->offset, req->end, total_size);
} else {
sprintf(buf, "HTTP/1.1 200 OK\r\nAccept-Ranges: bytes\r\n");
}
sprintf(buf + strlen(buf), "Cache-Control: no-cache\r\n");
// sprintf(buf + strlen(buf), "Cache-Control: public, max-age=315360000\r\nExpires: Thu, 31 Dec 2037 23:55:55 GMT\r\n");
sprintf(buf + strlen(buf), "Content-length: %lu\r\n",
req->end - req->offset);
sprintf(buf + strlen(buf), "Content-type: %s\r\n\r\n",
get_mime_type(req->filename));
writen(out_fd, buf, strlen(buf));
off_t offset = req->offset; /* copy */
while(offset < req->end) {
if(sendfile(out_fd, in_fd, &offset, req->end - req->offset) <= 0) {
break;
}
#ifdef LOG_ACCESS
printf("offset: %d \n\n", (unsigned int)offset);
#endif
close(out_fd);
break;
}
}
```
簡單來說，`serve_static` 會拿到一個 file descriptor `out_fd`，這是給客戶端的回應所使用的 file descriptor，先是在 `buf` 寫入回應的 header 以及內容，最後再一次用 `writen` 寫進 `out_fd` 並關檔。
這裡的情境並不需要開關檔，只需專注在如何在伺服器端讀取客戶端的請求，因此將 `process` 改寫並加上 `handle_command` 函式：
```c=
void process(int fd, struct sockaddr_in *clientaddr) {
#ifdef LOG_ACCESS
printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
http_request req;
parse_request(fd, &req);
handle_command(fd, req.filename);
}
```
而 `handle_command` 先把它做成很簡單的 echo server 來試試：
```c=
void handle_command(int out_fd, char *cmd) {
printf("receiving command: %s\n", cmd);
char buf[256];
sprintf(buf, "HTTP/1.1 200 OK\r\n");
sprintf(buf + strlen(buf), "Content-Type: text/plain\r\n\r\n");
sprintf(buf + strlen(buf), "%s\r\n", cmd);
writen(out_fd, buf, strlen(buf));
close(out_fd);
}
```
這樣一來便能成功從客戶端接收指令！
```shell
accept request, fd is 4, pid is 69
receiving command: new
```
請求和回應可以順利改動之後，把焦點轉移到程式如何同時服務多個來自客戶的請求，在 `main` 中可以看到 `fork` 的使用：
```c=
int i=0;
for(; i < FORK_COUNT; i++) {
int pid = fork();
if (pid == 0) { // child
while(1) {
connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
process(connfd, &clientaddr);
close(connfd);
}
} else if (pid > 0) { // parent
printf("child pid is %d\n", pid);
} else {
perror("fork");
}
}
while(1) {
connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
process(connfd, &clientaddr);
close(connfd);
}
```
在 for 迴圈中 parent 會產出 `FORK_COUNT` 個 child，而他們會陷進 while 迴圈接受請求，而 parent 自己在產完 child 之後也會進入最下方的 while 迴圈開始等待請求。
而在進入 for 迴圈之前有個有趣的地方：
```c=
// Ignore SIGPIPE signal, so if browser cancels the request, it
// won't kill the whole process.
signal(SIGPIPE, SIG_IGN);
```
查詢了 man page [pipe (7)](https://man7.org/linux/man-pages/man7/pipe.7.html)：
```
If all file descriptors referring to the read end of a pipe have been closed,
then a write(2) will cause a SIGPIPE signal to be generated for the calling process.
If the calling process is ignoring this signal, then write(2) fails with the error EPIPE.
```
如果客戶端在伺服器寫完之前就關掉瀏覽器或是關閉 socket 連線，那會導致 `write` 發生錯誤而收到 `SIGPIPE` signal。預設會讓 process 直接終止，這邊把他忽略掉。
接著將之整合進 `qtest`，首先將 `tiny.c` 整理出需要的函式，並新增 header 檔 `tiny.h`，在這我一併將 `main()` 更名成 `start_server()` 以供 `qtest` 使用。
`qtest.c` 中，加入命令 `web`：
```c=
#include "tiny.h"
static bool do_web(int argc, char *argv[]);
void start_server() {
struct sockaddr_in clientaddr;
int default_port = DEFAULT_PORT,
listenfd,
connfd;
socklen_t clientlen = sizeof clientaddr;
listenfd = open_listenfd(default_port);
if (listenfd > 0) {
printf("listen on port %d, fd is %d\n", default_port, listenfd);
} else {
perror("ERROR");
exit(listenfd);
}
int i=0;
for(; i < FORK_COUNT; i++) {
int pid = fork();
if (pid == 0) { // child
while(1) {
connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
process(connfd, &clientaddr);
close(connfd);
}
} else if (pid > 0) { // parent
printf("child pid is %d\n", pid);
} else {
perror("fork");
}
}
while(1) {
connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
process(connfd, &clientaddr);
close(connfd);
}
}
static void console_init()
{
...
add_cmd("web", do_web, " | Start a web server");
...
}
static bool do_web(int argc, char *argv[])
{
report(3, "start server..");
start_server();
return true;
}
```
也要在 `Makefile` 中加入 `tiny.o` 才能連結到目標：
`Makefile` 中新增 `tiny.o`：
```makefile
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
linenoise.o \
tiny.o
```
重新 `make` 過後就成功加入新功能！
```shell
root@35b88cfa2929:/data/week1/lab0-c# make
CC tiny.o
LD qtest
root@35b88cfa2929:/data/week1/lab0-c# ./qtest
cmd> web
start server..
listen on port 9999, fd is 3
child pid is 379
child pid is 380
child pid is 381
child pid is 382
```
接下來的問題是，如何將收到的請求轉換成命令執行。目前的程式碼依靠 `linenoise` 將命令列的命令讀取出來，再交由 `interpret_cmd` 執行，以及存入歷史等，詳細可以參見 `run_console` 函式：
```c=
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
```
我希望可以重複使用 `interpret_cmd`，讓它也能處理來自使用者的請求，因此將其加入 `console.h` ，從 static 函式改為一般的函式供其他檔案 (`qtest.c`) 使用。而我希望使用者可以從伺服器的回應看見佇列的資訊，但所有的命令都是透過 `report` 函式將訊息呈現在命令列，一時間難以全面支援伺服器版本，因此新增函式 `void write_queue_info(char *buf)` 來將 `show_queue` 的資訊寫入 buffer，再由 `handle_command` 將該資訊回應給使用者。
```c=
void handle_command(int out_fd, char *cmd)
{
printf("receiving command: %s\n", cmd);
interpret_cmd(cmd);
char info[QUEUE_INFO_LEN];
write_queue_info(info);
char buf[RESP_BUF_LEN];
snprintf(buf, RESP_BUF_LEN - strlen(buf) - 1, "HTTP/1.1 200 OK\r\n");
snprintf(buf + strlen(buf), RESP_BUF_LEN - strlen(buf) - 1,
"Content-Type: text/plain\r\n\r\n");
snprintf(buf + strlen(buf), RESP_BUF_LEN - strlen(buf) - 1, "%s\r\n", info);
writen(out_fd, buf, strlen(buf));
close(out_fd);
}
```
在將 `tiny.c` 加入的同時發現它並不符合 commit hook 的規範，所以也順便將其改寫，避免使用 `sprintf` 而用 `snprintf` 加上 buffer size，以防 buffer overflow。
對應的 Github commit: [Add tiny-web-server to qtest](https://github.com/ToastCheng/lab0-c/commit/185c250362133bf3ecfa904ed5b9df9d34722292)。
```shell
root@35b88cfa2929:/data/week1/lab0-c# ./qtest
cmd> web
start server..
listen on port 9999, fd is 3
receiving command: new
q = []
receiving command: ih hello
q = [hello]
```
最後試著用 coroutine 的方式改寫 `web` 命令。先 `#include <setjmp.h>` 來使用 `setjmp`、`longjmp`。想了一些方式實作 coroutine，但先從簡單的命令列和伺服器切換開始，coroutine 跟 multithread 的差異之一是，切換工作時是「自發的」，也就是說一個 coroutine 在讓出 cpu 的時間點是事先設計好的，例如 Golang 中的 goroutine (coroutine) 設計在引發 function call 的時候讓出 cpu。
因為我的實作中伺服器和命令列執行命令會是執行相同的函式，所以我使用了一個變數 `is_cmd` 來決定現在要換成誰執行，然後用兩個 `jmp_buf` 來管理伺服器和命令列兩邊的 context。
```c=
static bool is_cmd = true;
static jmp_buf cmd_buf;
static jmp_buf web_buf;
```
在 server 接受連線前 `setjmp`：
```c=
if (setjmp(web_buf) > 0)
report(3, "back to server, serving..");
connfd = accept(listenfd, (SA *) &clientaddr, &clientlen);
handle_command(connfd);
close(connfd);
```
然後讓出 cpu 的時間點，簡單起見我只在 `insert_head` 和 `insert_tail` 執行完時設定 `longjmp`：
```c=
is_cmd = !is_cmd;
longjmp(is_cmd ? cmd_buf : web_buf, 1);
```
有一個須要注意的點，在 `longjmp` 回到當初 `setjmp` 處時，局域變數的值會改變！這一點會造成不可預期的錯誤，以此為例：`listenfd` 是伺服器創造的 socket descriptor，伺服器會重複使用它來接受一個又一個的連線，但當從 `longjmp` 跳躍回來時，它的值卻
```shell
cmd> web
start server..
listen on port 9999, fd is 3
listen fd: 3
receiving command: new
q = []
cmd> it 9
q = [9]
back to server, serving..
listen fd: 80923806
```
因此將 `listenfd` 放置在全域讓其在 coroutine 切換時不會改變，更標準一點的做法應該是可以有一個 context 結構，保存這些重要資訊，其中包含 `jmp_buf`。
最後重新 `make` 便能得到支援 coroutine 切換的版本。對應的 Github commit: [Implement coroutine to execute both cmd and server](https://github.com/ToastCheng/lab0-c/commit/84dd11678bf0c8b6b0cd6cf64440467e40465c49)
```shell
root@35b88cfa2929:/data/week1/lab0-c# ./qtest
cmd> web
start server..
listen on port 9999, fd is 3
receiving command: new
q = []
cmd> ih 9
q = [9]
back to server, serving..
receiving command: ih 8
q = [8 9]
back to command line..
cmd>
```
## 5. 分析 `console.c` 實作及 select 系統呼叫
`// TODO`
## 6. 分析 `antirez/linenoise`
`// TODO`
## 7. 分析 simulation 模式
`// TODO`
## 8. 分析現有程式缺陷
`// TODO`
Sign in with Wallet
Connect another wallet