# 2021q1 Homework1 (lab0)
contributed by < `idoleat` >
## 進度
- [x] 實做 queue.[ch]
- [ ] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
- [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 在 `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
## 進行中
* 使用 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 修正 qtest 錯誤
* 說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
## 實做 Queue
### new
```c
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q != NULL) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
一個 `queue` struct 有三個 member：一個指標指向第一個 element、一個指標指向後一個 element，一個 `int` 紀錄 queue 的大小。所以在新增一個 queue 的時候，只要能成功分配到記憶體空間，就分別將大小設為 0 ，及指標初始化為 NULL，初始化為 NULL 可以作為之後 queue 裡面有沒有內容的判斷。
### free queue
由於平時寫程式沒在做記憶體管理（都是讓程式結束執行全部清除，真糟糕），自然不熟悉 `free()`，以為 `free()` 會神奇的遞迴的（recursively）釋放指標所指的記憶體位置。但是實做時閱讀註解給的提示時發現似乎並不是這麼回事。
一個 queue 裡面的 element 結構如下：
```c
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t
list_ele_t *element = malloc(sizeof(list_ele_t));
```
經嘗試後發現 `free(element)` 和 `free(element->value)` 並 `free(element)` 的差別在於前者不會釋放 `value` 指標所指的字串，所以 free 一個 element 也要記得 free 裡面的字串，否則會造成記憶體洩漏。
所以要清除一個 queue 需要先自行遍歷過整個 queue ，並在確保 queue 本身不為 NULL 後清除每個 element 直到 head 為 NULL，記得連 value 指向的內容都清除掉，如下：
```c
void q_free(queue_t *q)
{
if (q == NULL)
return;
list_ele_t *it = q->head;
while (it != NULL) {
list_ele_t *next = it->next;
free(it->value);
free(it);
it = next;
}
free(q);
}
```
### insert head
要從頭插入 element 可以分兩種狀況：queue 裡面有東西，以及 queue 裡面沒東西。`newh` 為 new head，根據兩種狀況分析：
* **queue 裡面沒東西**
1. 建立一個新的 element `newh`
2. `size++`
3. `newh->next = NULL`
( 其實直接 = head 就可以了，head 本來就是 NULL)
2. `head = newh`
3. `tail = newh`
* **queue 裡面有東西**
1. 建立一個新的 element `newh`
2. `size++`
3. `newh->next = head`
4. `head = newh`
建立一個新的 element 方式如下，首先檢查 queue 本身是否為 NULL，再來配置記憶體空間給 newh ，以及 newh 的字串內容，注意如果無法成功配置字串空間，記得也要連同原本的 newh 也釋放。這邊值得注意的一點是 **`strlen()` 回傳的長度不包含空結尾的 `'\0'`** ，所以配置及複製空間時要 +1，否則字串會沒有 `'\0'` 結尾，便會包含到接續記憶體中的內容，進而產生非預期中字元或亂碼。
```c
if (q == NULL)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
char *d = malloc(strlen(s) + 1);
if (d == NULL) {
free(newh);
return false;
}
strncpy(d, s, strlen(s) + 1);
```
比對 queue 裡面有東西及沒東西的狀況，只差在沒東西的時候要多一個 `tail = newh`，所以就在按照以上流程把 `newh` 接進 queue 裡面的時候多加一個判斷是否原本為空（以 `size` 判斷）決定是否需要 `tail = newh`。
```c
newh->value = d;
newh->next = q->head;
q->size++;
if (q->size == 1)
q->tail = newh;
q->head = newh;
return true;
```
### insert tail
基本邏輯與 insert head 相同，一樣分兩種狀況分析，`newt` 為 new tail
* **queue 裡面沒東西**
1. 建立一個新的 element `newh`
2. `size++`
3. `newt->next = NULL`
4. `head = newt`
5. `tail = newt`
* **queue 裡面有東西**
1. 建立一個新的 element `newh`
2. `size++`
3. `newt->next = NULL`
4. `tail->next = newt`
5. `tail = newt`
建立一個新的 element 方式與 insert head 相同，在此略過。比對 queue 裡面有東西及沒東西的狀況，兩者在第四點有所差異，因此一樣透過判斷 `size` 大小決定行為，如下：
```c
newt->value = d;
newt->next = NULL;
q->size++;
if (q->size == 1)
q->head = newt;
else
q->tail->next = newt;
q->tail = newt;
return true;
```
### reverse
我總共用了三個 `list_ele_t *` 型態的物件來協助反轉 list: `prev`, `current`, `look ahead`。 `current` 會指向要修改 `next` 的 element。**主要的操作是 `current->next = prev`**，`prev` 會指向 `current` 前一個。但是如果單純這樣的話會斷了往下一個 element 的路徑（`next` 指向前者了），所以會需要一個提前在路還沒被斷之前往前跑的指標 `look ahead` 先記住下一個 element 的位置，稍後 `current` 才能移過去。而在 current 移往 `look ahead` 的位置之前 prev 必須先到 `current` 的位置，因為 `prev` 已經不再指向原先的下一個位置。
#### 圖解
1. 初始狀態
```graphviz
digraph list{
rankdir=LR;
a,b,c [shape=box]
" " [color=white]
" " [color=white]
a->b;
b->c;
c->" ";
prev [label="prev\n(null)"]
current->a
look_ahead->b
}
```
2. `current` 所指的 element 將 `next` 改指向 `prev`
```graphviz
digraph list{
rankdir=LR;
a,b,c [shape=box]
" " [color=white]
" " [color=white]
a->prev;
b->c;
c->" ";
prev [label="prev\n(null)"]
current->a
look_ahead->b
}
```
3. `prev` 指到 `current` 目前指的位置，`current` 指到 `look_ahead` 目前指的位置
```graphviz
digraph list{
rankdir=LR;
a,b,c [shape=box]
" " [color=white]
" " [label="null", color=white]
a->" ";
b->c;
c->" ";
prev->a
current->b
look_ahead->b
}
```
4. `look_ahead` 往前看一個
```graphviz
digraph list{
rankdir=LR;
a,b,c [shape=box]
" " [color=white]
" " [label="null", color=white]
a->" ";
b->c;
c->" ";
prev->a
current->b
look_ahead->c
}
```
5. 重複 2~4 直到 `current` 走完所有 element
#### 實做
```c
if (q == NULL)
return;
if (q->head == NULL)
return;
list_ele_t *prev = NULL, *current = q->head, *look_ahead;
q->tail = q->head;
while (current != NULL) {
look_ahead = current->next;
current->next = prev;
prev = current;
current = look_ahead;
}
q->head = prev;
```
個人感覺可以在更簡潔，或是更有「品味」一些，現在的寫法看起來有點視覺上的饒舌。例如使用 `list_ele_t **` 可能會有更好的作法，有空來去觀摩一下其他同學的作法 :thinking_face:
### size
在 queue 中新增一個 `int` 變數儲存 queue 的大小，在每次做 insert 及 remove 的時候修改，便可在之後直接查詢大小不必重新計算。
討論區中有 [同學提問](https://www.facebook.com/groups/system.software2021/permalink/857285641781160/) 為什麼不用 `size_t` 就好？反正大小不會是負的。老師給予 [解釋](https://www.facebook.com/groups/system.software2021/permalink/857285641781160/?comment_id=857312008445190)，這邊簡短摘錄：
> 儘管 q_size() 回傳值應該要大於等於 0，但實際的行為可能涉及到對多個 queue 進行 q_size() 運算，例如比較 2 個 queue 的內部元素個數，除了運用大於、等於，和小於這樣的運算子，也可能被改寫 (無論是人為抑或編譯器最佳化) 為減法運算，即 q_size(Q1) - q_size(Q2)
感謝同學提問，同時讓我思考之前沒思考過的問題。
### sort
#### 使用哪種排序演算法？
我們必須考慮目前 list 的使用情景，可以被插入任意字串，沒有例如限定範圍、不能重複、已部份排序等限制，所以我們需要的是一個 general case 平均速度最快的，在我學過得排序演算法中 merge sort 及 quick sort 的平均複雜度 O(nlogn) 為最佳，但是 quick sort 無法保證每次都是 O(nlogn)，其 worst case 為 O(n^2^)，無法提供穩定可預期的執行時間，若在需要嚴格管控執行時間的環境執行可能會有無法預期之狀況，所以在此選用 merge sort 作為排序演算法。
#### 實做過程
過程中寫 merge sort 寫一寫有點卡住 ( 天哪連大一都不如 )，參照老師給的 [實做參考](https://npes87184.github.io/2015-09-12-linkedListSort/) 寫了一個會用到 malloc 的版本，結果執行測試發現 malloc 在 sort 裡面是不允許的（目前先把他 push 到另一個 branch 上了）。把傳遞參數的界面修改一下之後發現其實也還真的用不到 malloc，所以**平時可能有時候只是貪圖方便所以多使用了記憶體，之後配置記憶體前應該要多考一下是否真的必要。** 實做參考中 `merge_sort()` 中把一個 list 切成兩個 list 的作法個人覺得十分簡潔好懂，值得學習。
q_sort() 為使用界面，merge_sort 本身應該另外實做
```c
void q_sort(queue_t *q)
{
if (q == NULL)
return;
if (q->head == NULL || q->size == 1)
return;
q->head = merge_sort(q->head);
while (q->tail->next) {
q->tail = q->tail->next;
}
}
```
實做 merge sort
```cpp
list_ele_t *merge_sort(list_ele_t *head)
{
if (head == NULL || head->next == NULL)
return head;
// split a list into two
list_ele_t *left = head, *right = head->next;
while (right && right->next) {
left = left->next;
right = right->next->next;
}
right = left->next;
left->next = NULL;
return merge(merge_sort(head), merge_sort(right));
}
list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
list_ele_t *head = NULL, *currrent = NULL;
// attach head
size_t LL = strlen(left->value);
size_t RR = strlen(right->value);
if (strncmp(left->value, right->value, LL > RR ? LL : RR) < 0) {
currrent = left;
left = left->next;
} else {
currrent = right;
right = right->next;
}
head = currrent;
while (left != NULL && right != NULL) {
size_t L = strlen(left->value);
size_t R = strlen(right->value);
if (strncmp(left->value, right->value, L > R ? L : R) < 0) {
currrent->next = left;
left = left->next;
} else {
currrent->next = right;
right = right->next;
}
currrent = currrent->next;
}
if (left != NULL)
currrent->next = left;
else
currrent->next = right;
return head;
}
```
後來經過測試發現有幾個 case 過不了，仔細看每個指令執行的紀錄發現是忘了重新指定 tail 的位置，tail 指在 queue 中間某個地方，一但 insert tail 就會從中間錯誤的 tail 位置把 queue 切斷然後接上新的 list element。目前沒有想到邊 merge 還維護 tail 的方法，所以就在 sort 完之後讓 q->tail 重新走到最後。隨機參照了一下 [同學](https://hackmd.io/@gyes00205/2021q1_lab0#q_sort) 的作法也是如此。
這部分開發耗時最久，其中還包括一些低級又浪費時間的錯誤，像是該傳入 `left` 的地方竟多打成 `left->next`，完全沒有邏輯的錯誤追查起來特別耗時。希望可以更謹慎小心不要再犯這種錯誤。
最後基本測試結果都有通過，接下來開始修正 qtest 錯誤及延伸問題
## 使用 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 修正 qtest 錯誤 (WIP)
## 說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用 (WIP)
### 閱讀要點
* 優點、缺點
* 抽絲剝繭
* 風格(設計原則)
* 重要實做手法
* 可以改進之處
可嘗試單獨功能抽離做實驗
### 流程
由幾個 core function 和一些 helper function 組成，呼叫`linenoise()` 之後會先判斷是否為 tty ( 可能為檔案輸入或是其他命令 pipe 過來 ) 以及是否為支援的 terminal 來進行個別處理，若是 tty 也是支援的 terminal，則開啟 RAW mode ，使用 `termios` 設定與 terminal 互動界面的參數 ( 詳細見下方說明 )，例如輸入時不要 parity check、輸出時不要 post processing、指定一個 char 為 8 bit等。
接著執行 `linenoiseEdit()` 並新增目前輸入為最新的歷史命令，裡面有個無限迴圈等待使用者輸入，同時也處理 linenoise 支援的各種快捷鍵 ( 但是他的快捷鍵沒什麼邏輯又跟 vim 不一樣到底有誰要用？除了 `ctrl_C` ) 及 Escape Sequence。若為正常字元輸入則呼叫 `linenoiseEditInsert()` 顯示字元到 terminal 中。
假設過程中沒有發生錯誤等到使用者按下 ENTER 時，則結束 `linenoiseEdit()` ，關閉 RAW mode（還原原本 terminal 互動界面的參數），把使用者輸入的字串從 buffer 中複製一份回傳。
:::danger
待解決問題
* 為何要指定一個 char 為 8 bit？ 本來不是嗎？有可能不是嗎？
> 有！詳見 [What platforms have something other than 8-bit char?](https://stackoverflow.com/questions/2098149/what-platforms-have-something-other-than-8-bit-char)，你可見到若干機器的設定中，1 byte 可能是 9 bits (Honeywell 的主機, DEC PDP-10), 6 bits (DEC 早期機種), 16 bits (Texas Instruments C54x DSP, 至今仍廣泛使用)
> :notes: jserv
* 那個 escape sequence 怎麼用還看不是很懂
* `linenoiseEditInsert()`
* 為啥會有 `l->len >= l->buflen` 和 `l->plen + l->len >= l->cols` 的情形？
* `refreshSingleLine()`
* 前兩個 while 在幹麻？處理 `l->plen + l->len >= l->cols` 嗎？
* `getColumn()` 在幹麻？註解說：Use the ESC \[6n escape sequence to query 是什麼？
* `getCursorPosition()` 在幹麻？
* `enableRawMode()` 上的註解：Raw mode: 1960 magic shit. 是什麼意思？
:::
簡易流程圖 (WIP) (目前先用 drawio 快速打稿，之後在轉成 Graphiz)
### 架構
幾個 core function 和一些 helper function
### termios 的使用
首先我們需要先認識 terminal，以我的電腦為例，我透過 `$ echo $TERM` 可以得知我的 terminal 是 `xterm-256color`。現在所指的 terminal 都是指 terminal emulator，亦即模擬 [terminal](https://en.wikipedia.org/wiki/Computer_terminal#Text_terminals) 的一個程式，早期的 terminal 是一種連接電腦 (computer) 或計算系統 (computing system) 的獨立電子裝置，型態從電傳打字機 (teletype) 到顯示器加鍵盤組合包都有。早在獨立電子裝置的 terminal 的時期，為了要提供更進階的功能例如移動游標 (cursor) 到任意位置、清除部份螢幕顯示、顯示特殊字元等，便需使用 escape sequences, control characters 或 `termios` functions 完成文字輸入以外的特殊操作。現今 terminal emulators 大多也依然保有這些操作。而我電腦上的 [xterm](https://en.wikipedia.org/wiki/Xterm) 是 [X window system](https://en.wikipedia.org/wiki/X_Window_System) 上的 terminal emulator。
Linux kernel 內的 [<termios.h>](http://man7.org/linux/man-pages/man3/termios.3.html) 提供了一些函式讓使用者描述與 terminal 互動的方式。`termios` structure 內的 member 如下:
```c
tcflag_t c_iflag; /* input modes */
tcflag_t c_oflag; /* output modes */
tcflag_t c_cflag; /* control modes */
tcflag_t c_lflag; /* local modes */
cc_t c_cc[NCCS]; /* special characters */
```
我們可以看到 `linenoise` 中 `enableRawMode()` ，對每個 flag 都進行了設置，其中 `tcflag_t` 是 `unsigned integer` bit mask 用來表示各種 flag。
input mode
output mode
control mode
local mode
special character
flush input?
termios 本身也有個設置 raw mode 的函式
cfmakeraw(): "raw" mode of the old Version 7 terminal driver
(更深入的細節和功能先暫時省略，不然把背後一大串相關資訊拉起來會討論不完)
Sign in with Wallet
Connect another wallet