# 2020q3 Homework1 (lab0)
contributed by < `hankluo6` >
## 環境
```
$ uname -a
Linux hank-VirtualBox 5.3.0-61-generic #55~18.04.1-Ubuntu SMP Mon Jun 22 16:40:20 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 1
On-line CPU(s) list: 0
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
Stepping: 10
CPU MHz: 2304.002
BogoMIPS: 4608.00
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 8192K
NUMA node0 CPU(s): 0
```
詳細閱讀 [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf) ，依據指示著手修改 queue.[ch] 。
* `q_new`: 建立新的空佇列
* `q_free`: 釋放佇列中所有空間
* `q_insert_head`: 在佇列前端插入新元素
* `q_insert_tail`: 在佇列後端插入新元素
* `q_remove_head`: 刪除佇列前端元素
* `q_size`: 計算佇列中元素數量
* `q_reverse`: 倒轉佇列中元素
* `q_sort`: 排序佇列中元素(遞增排序)
## 開發過程
### `queue.h`
#### `queue_t`
要在 $O(1)$ 內完成 `q_insert_tail` 與 `q_size` 的話，必須在 `queue_t` 中加入 `size` 與 `tail` 欄位。
```c
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### `queue.c`
#### `q_free`
* 持續釋放每個元素之空間，最後需將 `q` 本身也釋放。
```c
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
#### `q_insert_head`
* 先配置好需要的空間，使用 `free()` 在 `NULL` 中無作用的特性，將釋放記憶體的部分寫在同區塊內，保持整潔與易讀性。
* 需注意 `strlen()` 不會計算結尾 `\0` 字元，故使用 `malloc` 分配記憶體時，需額外給予 **one byte** 大小來容納 `\0` 字元。
* 使用 `strncpy` 時的長度須含括 `*s` 中所有字元，包含 `\0` ，理由同上。
* 須更新 `q->head` ，如果為第一個element，則 `q->tail` 也須更新。
```c
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh = malloc(sizeof(list_ele_t));
char *news = malloc(strlen(s) * sizeof(char) + 1);
if (!q || !newh || !news) {
free(newh);
free(news);
return false;
}
strncpy(news, s, strlen(s) + 1);
newh->value = news;
newh->next = q->head;
q->head = newh;
if (!q->tail)
q->tail = newh;
++q->size;
return true;
}
```
`strlen()`的計算方式在 man page 中有清楚解釋
>The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').
如果 `strncpy` 只複製字串長度 `strlen(s)` 的話，會造成 `*news` 字串中沒有結尾符號 `\0` ，取值時將會產生未定義行為。如 trace-03 出現以下亂碼。
```
ERROR: Removed value dolphin���� != expected value dolphin
ERROR: Removed value bear���� != expected value bear
ERROR: Removed value gerbil���� != expected value gerbil
```
* #### `q_insert_tail`
* 與 `q_insert_head` 大致相同，須注意 `q->tail` 的更新需先檢查 `q` 是否為空。
```c
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh = malloc(sizeof(list_ele_t));
char *news = malloc(strlen(s) * sizeof(char) + 1);
if (!q || !newh || !news) {
free(newh);
free(news);
return false;
}
strncpy(news, s, strlen(s) + 1);
newh->value = news;
newh->next = NULL;
if (q->tail)
q->tail->next = newh;
else
q->head = newh;
q->tail = newh;
++q->size;
return true;
}
```
#### `q_remove_head`
* 注意 `*sp` 的範圍，可以從 [qtest.c](https://github.com/sysprog21/lab0-c/blob/master/qtest.c) 中的 `do_remove_head` 的程式碼中理解 `*sp` 跟 `bufsize` 的範圍
```c
#define MAXSTRING 1024
#define STRINGPAD MAXSTRING
static int string_length = MAXSTRING;
...
char *removes = malloc(string_length + STRINGPAD + 1);
...
removes[0] = '\0';
memset(removes + 1, 'X', string_length + STRINGPAD - 1);
removes[string_length + STRINGPAD] = '\0';
...
q_remove_head(q, removes, string_length + 1);
```
而 `string_length` 可以透過 qtest 直譯器指令 `option length [value]` 來改變
```c
add_param("length", &string_length, "Maximum length of displayed string", NULL);
```
所以 `*sp` 的第一個字元與最後一個字元為 `\0`，其餘皆為 `X`
```c
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *del = q->head;
q->head = q->head->next;
if (sp) {
strncpy(sp, del->value, bufsize);
sp[bufsize - 1] = '\0';
}
free(del->value);
free(del);
--q->size;
if (!q->size)
q->tail = NULL;
return true;
}
```
如果不加上 `sp[bufsize - 1] = '\0'` 的話，在 trace-06 會出現
```
ERROR: Removed value meerkat_panda_squirrel_vulture_XXXXXXXXX... != expected value meerkat_panda_squirrel_vulture
```
原因是因為 [qtest.c](https://github.com/sysprog21/lab0-c/blob/master/qtest.c) 中用來檢查回傳字串是否正確的 `checks` 變數，已經先將 `checks[string_length]` 設為 `\0`，而 `string_length + 1` 就是 `q_remove_head` 中的 `bufsize`，所以需要讓 `sp[busize - 1] = '\0'` 才能使 `strcmp` 通過。
```c
if (check) {
strncpy(checks, argv[1], string_length + 1);
checks[string_length] = '\0';
}
...
if (ok && check && strcmp(removes, checks)) {
report(1, "ERROR: Removed value %s != expected value %s", removes,
checks);
ok = false;
}
```
#### `q_size`
* 特別注意 `*q` 為 `NULL` 的情形中，不能取其成員。
```c
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
#### `q_reverse`
* 可以先從 linked list 的 reverse 開始分析， reverse 中必定要有三個 pointer，分別為當前更新 `next` 之節點，與其前後兩個節點。
* 參考 [gpwork4u](https://hackmd.io/-k6KIJ8GRSen7NUdVBt0AQ) 與 [ZhuMon](https://hackmd.io/@ZhuMon/lab0-c) 的方法，將沒有使用到的 `q->head->next` 與 `q->tail->next` 用來記錄前面與中間的節點。
* 新增 `rear` 指標指向後方的節點
* 最後須將 `q->head` 與 `q->tail` 設定為正確位置
```c
void q_reverse(queue_t *q)
{
if (!q || q->size < 2) {
return;
}
list_ele_t *rear = q->head->next->next;
q->tail->next = q->head;
while (q->head->next != q->tail) {
q->head->next->next = q->tail->next;
q->tail->next = q->head->next;
q->head->next = rear;
rear = rear->next;
}
q->tail = q->head;
q->head = q->head->next;
q->tail->next = NULL;
}
```
* 此為目前 `queue` 的結構
```graphviz
digraph linked_list{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <ref> }"]
b [label="{ <data> b | <ref> }"];
c [label="{ <data> c | <ref> }"];
d [label="{ <data> d | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> NULL [arrowhead=vee, arrowtail=dot,
dir=both, tailclip=false]
head [shape=box];
head -> a;
tail [shape=box];
tail -> d;
}
```
* 進入 `while` 迴圈前新增 `tail` 並將尾端相連
```graphviz
digraph linked_list{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <ref> }"]
b [label="{ <data> b | <ref> }"];
c [label="{ <data> c | <ref> }"];
d [label="{ <data> d | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> a [arrowhead=vee, arrowtail=dot,
dir=both, tailclip=false]
head [shape=box];
head -> a;
tail [shape=box];
tail -> d;
rear [shape=box];
rear -> c;
}
```
* 在 `while` 迴圈中，執行反轉四步驟
```graphviz
digraph linked_list{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <ref> }"]
b [label="{ <data> b | <ref> }"];
c [label="{ <data> c | <ref> }"];
d [label="{ <data> d | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, style=invis];
b:ref:c -> a:data [label=<<font color="blue"><font point-size="18"><b>1.</b></font></font>>, arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=blue, penwidth=2];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> a [arrowhead=vee, arrowtail=dot,
dir=both, tailclip=false]
head [shape=box];
head -> a;
tail [shape=box];
tail -> d;
rear [shape=box];
rear -> c;
}
```
```graphviz
digraph linked_list{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <ref> }"]
b [label="{ <data> b | <ref> }"];
c [label="{ <data> c | <ref> }"];
d [label="{ <data> d | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, style=invis];
b:ref:c -> a:data [label=1., arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> b [label=<<font color="red"><font point-size="18"><b>2.</b></font></font>>, arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=red, penwidth=2];
d:ref:c -> b [arrowhead=vee, arrowtail=dot,
dir=both, tailclip=false, style=invis]
head [shape=box];
head -> a;
tail [shape=box];
tail -> d;
rear [shape=box];
rear -> c;
}
```
```graphviz
digraph linked_list{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <ref> }"]
b [label="{ <data> b | <ref> }"];
c [label="{ <data> c | <ref> }"];
d [label="{ <data> d | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, style=invis];
a:ref:c -> c:data [label=<<font color="purple"><font point-size="18"><b>3.</b></font></font>>, arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, color=purple, penwidth=2];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, style=invis];
b:ref:c -> a:data [label=1., arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> b [label=2., arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> b [arrowhead=vee, arrowtail=dot,
dir=both, tailclip=false, style=invis]
head [shape=box];
head -> a;
tail [shape=box];
tail -> d;
rear [shape=box];
rear -> c;
}
```
```graphviz
digraph linked_list{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <ref> }"]
b [label="{ <data> b | <ref> }"];
c [label="{ <data> c | <ref> }"];
d [label="{ <data> d | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, style=invis];
a:ref:c -> c:data [label=3., arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, style=invis];
b:ref:c -> a:data [label=1., arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> b [label=2., arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> b [arrowhead=vee, arrowtail=dot,
dir=both, tailclip=false, style=invis]
head [shape=box];
head -> a;
tail [shape=box];
tail -> d;
rear [shape=box];
rear -> d [label=<<font color="brown"><font point-size="18"><b>4.</b></font></font>>, color=brown, penwidth=2];
rear -> c [style=invis];
}
```
* 再經過一次迴圈，此時 `q->head->next == q->tail` 跳出迴圈
```graphviz
digraph linked_list{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <ref> }"]
b [label="{ <data> b | <ref> }"];
c [label="{ <data> c | <ref> }"];
d [label="{ <data> d | <ref> }"];
a:ref:c -> d:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head [shape=box];
head -> a;
tail [shape=box];
tail -> d;
rear -> c;
}
```
* 將 `q->tail` 與 `q->head` 替換，並將相連部分刪除即可。
```graphviz
digraph linked_list{
rankdir=LR;
node [shape=record];
a [label="{ <data> a | <ref> }"]
b [label="{ <data> b | <ref> }"];
c [label="{ <data> c | <ref> }"];
d [label="{ <data> d | <ref> }"];
b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
head [shape=box];
head -> d;
tail [shape=box];
tail -> a;
rear -> c;
}
```
#### `q_sort`
* 參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) ，實現 merge sort，排序完後的 `q->tail` 不一定為尾端節點，故需額外尋找尾端來更新。
```c
void q_sort(queue_t *q)
{
if (!q || q->size < 2)
return;
q->head = merge_sort(q->head);
list_ele_t *tmp = q->tail;
while (tmp->next)
tmp = tmp->next;
q->tail = tmp;
}
```
#### `merge_sort`
* 以遞迴方式實作 merge sort 。
```c
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = merge_sort(head);
list_ele_t *l2 = merge_sort(fast);
list_ele_t *newh = NULL;
list_ele_t **tmp = &newh;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
*tmp = l1;
l1 = l1->next;
} else {
*tmp = l2;
l2 = l2->next;
}
tmp = &((*tmp)->next);
}
if (l1)
*tmp = l1;
else if (l2)
*tmp = l2;
return newh;
}
```
每次 `merge_sort` 都要回傳新的 head，可以使用 pointer to pointer
來改成更有「品味」的版本，
```c
void merge_sort(list_ele_t **head)
{
if (!(*head) || !(*head)->next)
return;
list_ele_t *fast = (*head)->next;
list_ele_t *slow = *head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t **front = head;
list_ele_t **back = &fast;
merge_sort(front);
merge_sort(back);
list_ele_t *newh = NULL;
list_ele_t **tmp = &newh;
while (*front && *back) {
if (strcmp((*front)->value, (*back)->value) < 0) {
*tmp = *front;
*front = (*front)->next;
} else {
*tmp = *back;
*back = (*back)->next;
}
tmp = &((*tmp)->next);
}
if (*front)
*tmp = *front;
else if (*back)
*tmp = *back;
*head = newh;
}
```
而 `merge_sort` 就不需要回傳 head
```c
void q_sort(queue_t *q) {
if (!q || q->size < 2)
return;
merge_sort(q->head);
list_ele_t *tmp = q->tail;
while (tmp->next)
tmp = tmp->next;
q->tail = tmp;
}
```
## Address Sanitizer
開啟 Address Sanitizer 後，在 trace17 會有記憶體錯誤的問題，從出現的檔案與其他檔案內容對照來看，大致推測為 `simulation` 的部分出現問題。
```c
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode", NULL);
```
可以看到 `init_cmd()` 強制將 1 bytes 的 `bool` 型態 `simulation` 轉換為 `int` 型態，被限制使用的空間會被 Address Sanitizer 檢測出來。
只要將使用到 `simulation` 的部分改為 `int` 就行了。
```c
int simulation = 0;
```
## Valgrind
#### debug queue.c
上述 `q_insert_head` 或是 `q_remove_head` 中的 `strncpy` 少結尾字元的情形 Valgrind 能夠辨識出來
```
==3665== 32 bytes in 1 blocks are still reachable in loss record 1 of 25
==3665== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3665== by 0x10B490: malloc_or_fail (report.c:189)
==3665== by 0x10BFA2: add_cmd (console.c:123)
==3665== by 0x10C083: init_cmd (console.c:93)
==3665== by 0x10ACAC: main (qtest.c:759)
```
忘記釋放空間等常見錯誤也能發現，如 `q_free` 中忘記釋放 `*q` 時會顯示
```
==4046== 64 bytes in 1 blocks are still reachable in loss record 1 of 1
==4046== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4046== by 0x10C793: test_malloc (harness.c:137)
==4046== by 0x10CB60: q_new (queue.c:14)
==4046== by 0x10A99F: do_new (qtest.c:124)
==4046== by 0x10B992: interpret_cmda (console.c:220)
==4046== by 0x10BF06: interpret_cmd (console.c:243)
==4046== by 0x10C4D4: cmd_select (console.c:569)
==4046== by 0x10C71C: run_console (console.c:628)
==4046== by 0x10AE41: main (qtest.c:772)
```
#### simulation
```c
if (mode == test_insert_tail) {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
char *s = get_random_string();
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
before_ticks[i] = cpucycles();
dut_insert_tail(s, 1);
after_ticks[i] = cpucycles();
dut_free();
}
} else {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
before_ticks[i] = cpucycles();
dut_size(1);
after_ticks[i] = cpucycles();
dut_free();
}
}
```
從程式碼中可看到，simulation 模式會持續分配大量記憶體 (`q_insert_head`)，再量測 cpu 時間，最後釋放所有空間。
所以 massif 產生的記憶體使用量應為許多峰值的圖。
```
valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd
```
與預期結果不同，仔細看每段峰值橫跨不同的 snapshot，但 `dut_insert_head` 應該不會慢到橫跨不同的 snapshot。推測是 massif 的 snapshot 數量太少，將 snapshot 與 detailed snapshots 數量開到最大。
```
valgrind --tool=massif --max-snapshots=1000 --depth=200 ./qtest -f traces/trace-17-complexity.cmd
```
完美！每次 `dut_insert_head` 都將大量分配記憶體，計算完時間後立刻釋放，產生這種起伏巨大的圖。
起伏劇烈的原因可能為每次 queue 配置的記憶體大小不同，
實驗將 `measure` 裡 `test_insert_tail` 與 `test_size` 的 `malloc` 數量改為固定
```c
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
char *s = get_random_string();
dut_new();
dut_insert_head(
get_random_string(),
100);
before_ticks[i] = cpucycles();
dut_insert_tail(s, 1);
after_ticks[i] = cpucycles();
dut_free();
}
```
可以看到後半段檢驗 `q_size` 的記憶體大小幾乎一樣，而前半段還是有高低起伏，推測是 snapshot 的時間不是剛好在 `dut_insert_tail` 結束的時間，所以每次紀錄的 heap size 都會變化。但可以知道劇烈起伏有很大的因素是 `dut_insert_head` 裡配置的記憶體大小影響的。
## Dude, is my code constant time?
實驗是基於對執行時間的 Timing Leakage Detection，測量兩個不同 classes 的 input data，檢查是否有顯著性差異 ( [statistically different](https://en.wikipedia.org/wiki/Statistical_significance) )。
### Student’s t-distribution
[Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 為一種當變異數未知時，用來估計常態分布總體的均值。隨著自由度的增加，該分布會趨近於常態分佈，在做統計檢定時相當有用。
### Welch's t-test
[t-test](https://en.wikipedia.org/wiki/Student%27s_t-test) 為一種統計檢定，可以用來檢定在變異數未知且取樣數量少時，兩個來自常態分配母體的獨立樣本之期望值的差是否為某一實數。
可以將 t-test 分成 Student's t-test 以及 [Welch's t-test](https://en.wikipedia.org/wiki/Welch's_t-test)，兩者的區別只是在統計量 `t` 的分母不同，Student's t-test 使用情形在兩母體之變異數近似，而 Welch's t-test 則是在兩母體變異數不同的情況下使用。
::: info
根據 wikipedia 所述：All such tests are usually called Student's t-tests, though strictly speaking that name should only be used if the variances of the two populations are also assumed to be equal。
變異數相同時稱為 Student's t-test ，不同時則必須稱為 Welch's t-test。
:::
事實上，兩母體變異數是否有差異可以用 [F-test](https://en.wikipedia.org/wiki/F-test) 來檢定，在 dudect 中已經假設兩母體變異數不相等。
我們可以用統計檢定來解釋論文中使用的 t-test
$$
\large H_{0} : \mu_{0} = \mu_{1} \\
\large H_{1} : \mu_{0} \neq \mu_{1}
$$
此為一雙尾檢定，設定信賴水準為 95%，變異數未知，使用 Welch's t-test 來檢定。
$$
\large t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{s^2_1}{N_1} + \frac{s^2_2}{N_2}}}
$$
算出 t 值後，需算出自由度 df，根據 [Welch–Satterthwaite equation](https://en.wikipedia.org/wiki/Welch's_t-test) 來計算，這邊因為只有 2 個 sample variance，故直接將公式展開
$$
\large v \approx \frac{\left(\frac{s^{2}_{1}}{N_{1}}+\frac{s^{2}_{2}}{N_{2}}\right)^2}{\frac{\left(\frac{s^{2}_{1}}{N_{1}}\right)^2}{N_{1} - 1}+\frac{\left(\frac{s^{2}_{2}}{N_{2}}\right)^2}{N_{2} - 1}}
$$
注意自由度可能為小數，可以四捨五入或是無條件捨去(保守作法)。
最後查表看對應的自由度與 t value，只要 t value 落在信賴區間外(圖中紅色區域)，表示拒絕虛無假設，也可以說是我們沒有足夠的證據證明兩者平均數相等。
### 程式碼分析
在 dudect 中，主要計算時間的函式為 `doit`，我們將重點放在 `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;
}
```
#### `variable`
* `t` 為 `struct t_ctx` 類型，用來記錄分布中的平均值、變異數與測試個數
* `number_measurements` 為測試的總數量
* `before_ticks` 與 `after_ticks` 用來記錄測試前時間與測試後時間
* `exec_times` 紀錄時間差
* `classes` 紀錄目前為論文中的 `fix class` 還是 `random class`
* `input_data` 儲存 `random class` 中 `q_insert` 要使用多少個 node
將 `doit` 分成幾個區塊，方便理解：
#### `allocate` ( line 0 ~ line 13 )
前 14 行都在配置記憶體，特別注意 `input_data` 中每個測試資料皆有 `chuck_size` bytes 的位置來儲存隨機數
#### `prepare_inputs` ( line 15 )
`prepare_inputs` 會呼叫 `randombytes` 來產生隨機數，並將結果放在 `input_data` 中。
也會呼叫 `randombit` 來產生 0 或 1，並放入 `classes[i]` 中，如果為 0 則將 input_data 裡的該部分清除，此動作在實現論文中 `fix class` 的部分，而 `class[i] == 1` 則為論文中 `random class` 的部分。
此函式也會隨機產生 `random_string` 裡的值。
#### `measure` ( line 17 )
`measure` 則是實際計算運行時間的部分，`i` 表示每一次的測試，透過 `dut_insert_head` 裡的第二個參數 `*(uint16_t *) (input_data + i * chunk_size) % 10000)` 來決定要 insert 多少個 node。
* 當 `class[i] == 0` 時，該參數為 0，為 `fix class` 的部分
* 當 `class[i] == 1` 時，該參數為 0 ~ 9999 的隨機數，為 `random class` 的部分
再來就是計算要測量的函式時間，將運行前時間與運行後時間放在 `before_ticks` 與 `after_ticks` 中，並記得釋放記憶體。
#### `differentiate` and `update_statistics` ( line 18 ~ line 19 )
這兩個函式只是計算每次測試 `i` 的時間差，並將結果與對應的 class 一起 push 至 `t` 中計算平均值與變異數。
#### `report` ( line 20 )
套用 [Welch’s test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 公式，計算 `t_value`，根據 `t_threshold_moderate` 決定假設是否成立。
#### `free` ( line 22 ~ line 28 )
最後將分配的記憶體釋放，並回傳測試結果。
### 實作細節
紀錄一些較難理解的地方
#### `randombytes`
`randombytes`用來產生隨機數到指定的記憶體空間裡。但隨機數的是透過讀取 `/dev/urandom` 這個檔案裡的資料來產生。
不知道 `dev/urandom` 是幹嘛的，從 man page 裡可以找到
:::info
The character special files /dev/random and /dev/urandom (present since
Linux 1.3.30) provide an interface to the kernel's random number gener‐
ator.
:::
再從 [wikipedia](https://en.wikipedia.org/wiki//dev/random) 頁面中找資料
:::info
A counterpart to /dev/random is /dev/urandom ("unlimited"/non-blocking random source) which reuses the internal pool to produce more pseudo-random bits. This means that the call will not block, but the output may contain less entropy than the corresponding read from /dev/random.
:::
原來 linux 核心中是依據環境噪聲產生 entropy，並放入 entropy pool，而 `dev/urandom` 就是從 entropy pool 中產生亂數的地方，且安全性比 `dev/random` 還低。
之後的 `while` 迴圈就很好理解，只要將隨機數讀到指定的記憶體就行了，特別注意 `x += i` 為指標的加法，用意是將指標位置從已經放完資料的地方移動到未賦值的地方。
#### `t_push`
`t_push` 使用 online 版本來計算平均值與變異數，可以防止 overflow 的問題。
使用 [Welford's online algorithm](https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Weighted_batched_version) 來計算變異數，需先計算 [Sum of Squares](https://www.investopedia.com/terms/s/sum-of-squares.asp)，寫作 $M_{2}$。在 `struct t_ctx` 中用 `m2` 成員來記錄，而在需要時再轉換為變異數。
$$
\mu_{n} = \mu_{n-1} + \frac{x_n-\mu_{n-1}}{n} \\
M_{2,n} = M_{2,n-1} + \left(x_n - \mu_{n-1}\right)\left(x_n - \mu_{n}\right) \\
s^{2}_{n} = \frac{M_{2,n}}{n - 1}
$$
#### `report`
`report` 函式用來檢查假設是否成立。從 `report` 中並不知道 `t_threshold_bananas` 的用處，但從論文作者原始碼 [fixture.c](https://github.com/oreparaz/dudect/blob/master/src/fixture.c) 就能看到是用來區分 Definitely not constant time 與 Probably not constant time 用的。
```c
if (max_t > t_threshold_bananas) {
printf(" Definitely not constant time.\n");
exit(0);
}
if (max_t > t_threshold_moderate) {
printf(" Probably not constant time.\n");
}
if (max_t < t_threshold_moderate) {
printf(" For the moment, maybe constant time.\n");
}
```
### 討論
#### threshold 的選擇
threshold 的設計可以再更精準，需先計算自由度，再透過查表或計算 p value 來決定是否有顯著差異，可參考上方 Welch's t-test 的部分。
#### Higher-order preprocessing
在論文中提到
>when a t-test is coupled with cropping pre-processing, one is no longer
testing only for equality of means but also for higher order
statistical moments since the cropping is a non-linear transform
而在我們的 dudect 程式中，只有計算到 1st order statistical moments，需再增加 higher-order 的分析。
## linenoise
### 程式碼分析
linenoise 的操作都是基於 `linenoiseState` 來運作的
```c
struct linenoiseState {
int ifd; /* Terminal stdin file descriptor. */
int ofd; /* Terminal stdout file descriptor. */
char *buf; /* Edited line buffer. */
size_t buflen; /* Edited line buffer size. */
const char *prompt; /* Prompt to display. */
size_t plen; /* Prompt length. */
size_t pos; /* Current cursor position. */
size_t oldpos; /* Previous refresh cursor position. */
size_t len; /* Current edited line length. */
size_t cols; /* Number of columns in terminal. */
size_t maxrows; /* Maximum num of rows used so far (multiline mode) */
int history_index; /* The history index we are currently editing. */
};
```
接著來一個個分析裡面的函式
#### `linenoise`
```c
char *linenoise(const char *prompt) {
char buf[LINENOISE_MAX_LINE];
int count;
if (!isatty(STDIN_FILENO)) {
...
} else if (isUnsupportedTerm()) {
...
} else {
count = linenoiseRaw(buf,LINENOISE_MAX_LINE,prompt);
if (count == -1) return NULL;
return strdup(buf);
}
}
```
linenoise 函式會在內部呼叫 `linenoiseRaw` 用來做編輯等處理，並回傳處理完的字串，也就是打完字按 Enter 後的內容，參數 `prompt` 的內容為一開始要輸出在 cmd 上的字串， (如 `cmd>`)。
#### `linenoiseRaw`
```c
static int linenoiseRaw(char *buf, size_t buflen, const char *prompt) {
int count;
if (buflen == 0) {
errno = EINVAL;
return -1;
}
if (enableRawMode(STDIN_FILENO) == -1) return -1;
count = linenoiseEdit(STDIN_FILENO, STDOUT_FILENO, buf, buflen, prompt);
disableRawMode(STDIN_FILENO);
printf("\n");
return count;
}
```
可以看到先運行 `enableRawMode` 函式，並進入 `linenoiseEdit` ，最後再關閉 `RawMode`。
#### `enableRawMode`
```c
static int enableRawMode(int fd) {
struct termios raw;
if (!isatty(STDIN_FILENO)) goto fatal;
if (!atexit_registered) {
atexit(linenoiseAtExit);
atexit_registered = 1;
}
if (tcgetattr(fd,&orig_termios) == -1) goto fatal;
...
if (tcsetattr(fd,TCSAFLUSH,&raw) < 0) goto fatal;
rawmode = 1;
return 0;
fatal:
errno = ENOTTY;
return -1;
}
```
先來了解兩種 [terminal mode](https://en.wikipedia.org/wiki/Terminal_mode)，Raw Mode 與 Cooked Mode。
Cooked Mode 為一般 linux terminal 的模式，會根據使用者的特定輸入來產生特定行為，例如 [Control character](https://en.wikipedia.org/wiki/Control_character)。
Raw Mode 則類似 Vim 編輯器一樣，使用者的輸入將全部以 [Raw Data](https://en.wikipedia.org/wiki/Raw_data) 的形式傳給 terminal，而這正是我們想要的。
再來看看 `termios` 這個 structure，從 [man page](https://man7.org/linux/man-pages/man3/termios.3.html) 裡的說明
:::info
termios, tcgetattr, tcsetattr, tcsendbreak, tcdrain, tcflush, tcflow, cfmakeraw, cfgetospeed, cfgetispeed, cfsetispeed, cfsetospeed, cfset‐ speed - get and set terminal attributes, line control, get and set baud rate
:::
:::info
The termios functions describe a general terminal interface that is provided to control asynchronous communications ports.
:::
可以知道 `termios` 用來控制終端機介面裡的屬性，在 `enableRawMode` 函式裡更改相關屬性來達成 Raw Mode。而`tcsetattr` 與 `tcgetattr` 分別是用來接收與設置 terminal 當前屬性。
#### `linenoiseEdit`
```c
static int linenoiseEdit(int stdin_fd, int stdout_fd, char *buf, size_t buflen, const char *prompt)
{
struct linenoiseState l;
...
if (write(l.ofd,prompt,l.plen) == -1) return -1;
while(1) {
char c;
int nread;
char seq[3];
nread = read(l.ifd,&c,1);
if (nread <= 0) return l.len;
if (c == 9 && completionCallback != NULL) {
c = completeLine(&l);
/* Return on errors */
if (c < 0) return l.len;
/* Read next character when 0 */
if (c == 0) continue;
}
switch(c) {
...
}
}
return l.len;
```
`linenoiseEdit` 為主要操控游標的函式，先宣告 `linenoiseState` 變數，並將相關資訊放入到結構中。
接著進入 `while` 迴圈，除了 `Enter` 與 `Ctrl_C` 等字元外，其他左右移動，歷史紀錄等等操作皆在此迴圈中進行。
`switch` 以輸入字元 `c` 來選擇對應的行為。
#### `linenoiseEditInsert`
```c
int linenoiseEditInsert(struct linenoiseState *l, char c) {
if (l->len < l->buflen) {
if (l->len == l->pos) {
l->buf[l->pos] = c;
l->pos++;
l->len++;
l->buf[l->len] = '\0';
if ((!mlmode && l->plen+l->len < l->cols && !hintsCallback)) {
/* Avoid a full update of the line in the
* trivial case. */
char d = (maskmode==1) ? '*' : c;
if (write(l->ofd,&d,1) == -1) return -1;
} else {
refreshLine(l);
}
} else {
memmove(l->buf+l->pos+1,l->buf+l->pos,l->len-l->pos);
l->buf[l->pos] = c;
l->len++;
l->pos++;
l->buf[l->len] = '\0';
refreshLine(l);
}
}
return 0;
}
```
`linenoiseEditInsert` 為在 `switch` 裡 `c` 為非特定字元時會呼叫，用來插入字元到現在的字串中。依照游標是否在當前字串結尾分成兩種情況，相關操作都很直覺，看程式碼就能理解。要注意插入完字元後，需呼叫 `refreshLine` 來更新畫面上的字串。
#### `refreshSingleLine`
```c
static void refreshSingleLine(struct linenoiseState *l) {
...
struct abuf ab;
...
abInit(&ab);
/* Cursor to left edge */
snprintf(seq,64,"\r");
abAppend(&ab,seq,strlen(seq));
/* Write the prompt and the current buffer content */
abAppend(&ab,l->prompt,strlen(l->prompt));
if (maskmode == 1) {
while (len--) abAppend(&ab,"*",1);
} else {
abAppend(&ab,buf,len);
}
/* Show hits if any. */
refreshShowHints(&ab,l,plen);
/* Erase to right */
snprintf(seq,64,"\x1b[0K");
abAppend(&ab,seq,strlen(seq));
/* Move cursor to original position. */
snprintf(seq,64,"\r\x1b[%dC", (int)(pos+plen));
abAppend(&ab,seq,strlen(seq));
if (write(fd,ab.b,ab.len) == -1) {} /* Can't recover from write error. */
abFree(&ab);
}
```
`refreshLine` 分成 `SingleLine` 與 `MultLine` 兩種，這邊介紹 `SingleLine` 版本。
函式前半段的 `while` 迴圈用來控制當終端機上的字元數過多時的情況，印出新的字元並將最舊的字元移除。
接著可以看到 `abuf` 這個 structure，當作 append buffer，用來記錄 `refresh` 中游標的所有移動，再一次性印到 terminal 上。
`seq` 用來儲存將要寫入的字串，之後進入 `abAppend` 將字串 push 到目前 append buffer 的尾端，在 `snprintf` 中寫入的字串稱為 [ANSI escape code](https://en.wikipedia.org/wiki/ANSI_escape_code)，用來處理游標操作。
最後在寫入到標準輸出上，印給使用者觀看。
#### `linenoiseHistory`
`history` 的概念很簡單，用一個 `static char **history` 來儲存每個歷史記錄內的字串，並呼叫 `linenoiseHistoryAdd` 來將新字串儲存到 `history` 中。
另外還提供搭配兩個函式 `linenoiseHistorySave` 與 `linenoiseHistoryLoad` 用來將 `history` 讀寫檔。
而要印出之前的 `history`，就必須呼叫 `linenoiseEditHistoryNext` 函式，該函式會在輸入上下鍵時呼叫。
```c
#define LINENOISE_HISTORY_NEXT 0
#define LINENOISE_HISTORY_PREV 1
void linenoiseEditHistoryNext(struct linenoiseState *l, int dir) {
if (history_len > 1) {
/* Update the current history entry before to
* overwrite it with the next one. */
free(history[history_len - 1 - l->history_index]);
history[history_len - 1 - l->history_index] = strdup(l->buf);
/* Show the new entry */
l->history_index += (dir == LINENOISE_HISTORY_PREV) ? 1 : -1;
if (l->history_index < 0) {
l->history_index = 0;
return;
} else if (l->history_index >= history_len) {
l->history_index = history_len-1;
return;
}
strncpy(l->buf,history[history_len - 1 - l->history_index],l->buflen);
l->buf[l->buflen-1] = '\0';
l->len = l->pos = strlen(l->buf);
refreshLine(l);
}
}
```
前兩行的 `free` 與 `strdup` 是為了將當前螢幕上的字串 `l->buf` 放入 `history` 中，並把接下來要印出來的字串從 `history` 中移除。也就是說當呼叫 `linenoiseEditHistoryNext` 後出現的字串，就已經不會儲存在 `history` 當中，這樣可以保證新輸入的字串會被放到 `history` 的尾端，而不是還儲存在 `history` 中間。
接著再透過 `history_index` 來選擇現在只向哪個 `history` 字串，並複製到 `l->buf` 就完成了。
#### `completeLine`
要使用 `completeLine` 前須先使用 `linenoiseSetCompletionCallback` 註冊 callback function，callback function 的寫法可參考 [example.c](https://github.com/antirez/linenoise/blob/master/example.c) 的範例程式，所有觸發相關的條件都必須寫在 callback function 裡。
而 `linenoiseAddCompletion` 則只儲存 completion 的**結果** ，需透過 `linenoiseCompletions` 這個 structure 來儲存相關資料。
```c
typedef struct linenoiseCompletions {
size_t len;
char **cvec;
} linenoiseCompletions;
void linenoiseAddCompletion(linenoiseCompletions *lc, const char *str) {
size_t len = strlen(str);
char *copy, **cvec;
copy = malloc(len+1);
if (copy == NULL) return;
memcpy(copy,str,len+1);
cvec = realloc(lc->cvec,sizeof(char*)*(lc->len+1));
if (cvec == NULL) {
free(copy);
return;
}
lc->cvec = cvec;
lc->cvec[lc->len++] = copy;
}
```
可以看到 `lc->cvec` 跟上面的 `history` 一樣用一個 pointer to pointer 來儲存每個 completion string。
最後，當輸入 Tab 鍵時，呼叫 `completeLine`
```c
static int completeLine(struct linenoiseState *ls)
linenoiseCompletions lc = { 0, NULL };
int nread, nwritten;
char c = 0;
completionCallback(ls->buf,&lc);
if (lc.len == 0) {
linenoiseBeep();
} else {
size_t stop = 0, i = 0;
while(!stop) {
/* Show completion or original buffer */
if (i < lc.len) {
struct linenoiseState saved = *ls;
ls->len = ls->pos = strlen(lc.cvec[i]);
ls->buf = lc.cvec[i];
refreshLine(ls);
ls->len = saved.len;
ls->pos = saved.pos;
ls->buf = saved.buf;
} else {
refreshLine(ls);
}
nread = read(ls->ifd,&c,1);
if (nread <= 0) {
freeCompletions(&lc);
return -1;
}
switch(c) {
case 9: /* tab */
i = (i+1) % (lc.len+1);
if (i == lc.len) linenoiseBeep();
break;
case 27: /* escape */
/* Re-show original buffer */
if (i < lc.len) refreshLine(ls);
stop = 1;
break;
default:
/* Update buffer and return */
if (i < lc.len) {
nwritten = snprintf(ls->buf,ls->buflen,"%s",lc.cvec[i]);
ls->len = ls->pos = nwritten;
}
stop = 1;
break;
}
}
}
freeCompletions(&lc);
return c; /* Return last read character */
```
內部會呼叫 callback function，並將可以 completion 的字串通通放入 `lc` 當中，並進入 `while` 迴圈。`while` 迴圈會印出目前 completion 的字串，但是還**不會**把結果存入 `ls` 當中，而是進入 `switch` 等待下個輸入。
當下個輸入不是 Tab 或跳脫字元時，才會將結果寫入到 `ls` 中。
如果下個輸入是 Tab 的話，會依照 `lc->cvec` 裡的順序依序印出。
#### `refreshShowHints`
`refreshShowHints` 用來提示接下來可能的輸入，類似 linux 下按兩下 tab。要使用前一樣需先註冊 callback function，可 [example.c](https://github.com/antirez/linenoise/blob/master/example.c) 的範例程式，跟 completion 一樣，跟觸發相關的條件都必須寫在 callback function 裡。接著程式就會在 `refresh` 時呼叫 `refreshShowHints` 來顯示提示。
```c
void refreshShowHints(struct abuf *ab, struct linenoiseState *l, int plen) {
char seq[64];
if (hintsCallback && plen+l->len < l->cols) {
int color = -1, bold = 0;
char *hint = hintsCallback(l->buf,&color,&bold);
if (hint) {
int hintlen = strlen(hint);
int hintmaxlen = l->cols-(plen+l->len);
if (hintlen > hintmaxlen) hintlen = hintmaxlen;
if (bold == 1 && color == -1) color = 37;
if (color != -1 || bold != 0)
snprintf(seq,64,"\033[%d;%d;49m",bold,color);
else
seq[0] = '\0';
abAppend(ab,seq,strlen(seq));
abAppend(ab,hint,hintlen);
if (color != -1 || bold != 0)
abAppend(ab,"\033[0m",4);
/* Call the function to free the hint returned. */
if (freeHintsCallback) freeHintsCallback(hint);
}
}
}
```
看程式碼應該就能理解，`*hint` 會傳需要提示的字串，更改顏色後透過 `struct abuf` 來添加到 append buffer 裡，這邊 `ab` 就是從 `refresh` 時宣告的 `ab` 傳來的，更新完 append buffer 後回到 `refresh` 函式就會將結果印到 terminal 上。
### 改寫 qtest
先找到 qtest 裡面 parse command 的地方，追蹤後發現在 console.c 裡 `cmd_select` 的 `readline` 部分
```c
while (!block_flag && read_ready()) {
cmdline = readline();
interpret_cmd(cmdline);
prompt_flag = true;
}
```
注意到這邊 file 與 STDIN 的輸入方式皆使用 `readline` 來控制，為了要使用 `linenoise` 需區分這兩種情況
```c
int fd = fname ? open(fname, O_RDONLY) : STDIN_FILENO;
is_file = fname ? true : false;
```
將 `cmd_select` 中用到 `readline` 的部分改成 `linenoise`
```c
while (!is_file && !block_flag &&
(cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
prompt_flag = true;
linenoiseFree(cmdline);
}
```
實際測試會發現出現類似 `newԆU` 的隨機亂碼，debug 後發現 `parse_args` 中 `*dst` 沒有設置結尾字元，所以將 `\0` 手動新增到 `*dst` 結尾。
```c
char *dst = buf;
dst[len] = '\0';
```
:::warning
這邊不了解為甚麼使用 `readline` 就不用加 `\0` 在結尾，看不出來 `readline` 與 `linenoise` 輸出的字串有甚麼差別。
:::
接著實作自動補齊，只要比較目前字串與目標字串相等，Tab 鍵就能持續選擇下個可能的字串。
```c
void completion(const char *buf, linenoiseCompletions *lc)
{
if (!strlen(buf))
return;
if (!strncmp("new", buf, strlen(buf))) {
linenoiseAddCompletion(lc, "new");
}
if (!strncmp("ih", buf, strlen(buf))) {
linenoiseAddCompletion(lc, "ih");
}
if (!strncmp("it", buf, strlen(buf))) {
linenoiseAddCompletion(lc, "it");
}
if (!strncmp("rh", buf, strlen(buf))) {
linenoiseAddCompletion(lc, "rh");
}
...
}
linenoiseSetCompletionCallback(completion);
```
再來是提示字串，可以簡單提示可輸入的參數
```c
char *hints(const char *buf, int *color, int *bold) {
if (!strcasecmp(buf, "ih")) {
*color = 33;
*bold = 1;
return " str [n]";
}
if (!strcasecmp(buf, "it")) {
*color = 33;
*bold = 1;
return " str [n]";
}
...
return NULL;
}
linenoiseSetHintsCallback(hints);
```
最後是歷史紀錄，只要在輸入字串後記錄到 `history` 中就好了
```c
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave("history.txt"); /* Save the history on disk. */
```
開啟 multiline mode (雖然用不太到)
```c
while ((c = getopt(argc, argv, "hv:f:l:m")) != -1) {
...
case 'm':
linenoiseSetMultiLine(1);
break;
...
}
```
#### 已知 Bug
* 當接受到 Ctrl_C 或 Ctrl_D 時有錯誤，下個指令會無法處理
## 現有程式的缺陷
`readline` 裡面的 `read()` 有可能會因為 signal 暫時中斷，但程式碼中好像未處理到關於 interrupt 的行為，查詢資料時翻閱到[這篇](http://rocksaying.tw/archives/2159383.html)很詳細的解釋 POSIX 中 `read()` 被 signal 中斷時的處理方式。
但為了要以第一手資料為主，翻閱 linux 裡 signal 的 [man page](https://man7.org/linux/man-pages/man7/signal.7.html) 時看到這段
:::info
read(2) calls on "slow" devices. A "slow" device is one where the I/O call may block for an indefinite time, for example, a terminal, pipe, or socket. (A disk is not a slow device according to this definition.) If an I/O call on a slow device has already transferred some data by the time it is interrupted by a signal handler, then the call will return a success status (normally, the number of bytes transferred).
:::
而在 `read(2)` 的 [man page](https://linux.die.net/man/2/read) 裡又寫道
:::info
On error, -1 is returned, and errno is set appropriately. In this case it is left unspecified whether the file position (if any) changes.
:::
兩者似乎對回傳值的定義有些不同(?)，只好翻閱網路上的資料，根據 [Linux 系統程式設計 - read()、write() 與 page cache](https://blog.jaycetyle.com/2019/01/linux-read-write/) 這篇文章與上面提到的 [多工作業下的資料讀寫處理事項](http://rocksaying.tw/archives/2159383.html) 所述，我的理解是當已經有資料傳輸後，signal 中斷時 `read()` 會將已經傳輸的 bytes 數回傳，而尚未傳輸資料時，則回傳 -1 並設置 `erron`。
目前程式中的 `readline` 已經可以處理第一種情況，也就是已有資料傳輸時的情形，因為 `buf_stack->cnt` 會被設置為成功讀取字串的 bytes 數，就算 `read` 的時候被中斷，在 `buf_stack->cnt == 0` 時也會重新填補 buffer。
所以只要來應付第二種情況。在回傳值為 -1 時判斷是否為 EINTR 的 interrupt，將 `read()` 用 `while` 迴圈來判斷是否為 EINTR 的 error
```c
if (buf_stack->cnt <= 0) {
/* Need to read from input file */
while (buf_stack->cnt = read(buf_stack->fd, buf_stack->buf, RIO_BUFSIZE) < 0) {
if (errno == EINTR)
continue;
else
return NULL;
}
buf_stack->bufptr = buf_stack->buf;
...
}
```
###### tags: `linux2020`
Sign in with Wallet
Connect another wallet