# 2020q1 Homework1 (lab0)
contributed by < [OscarShiang](https://github.com/OscarShiang) >
###### tags: `linux2020`
## 測試環境
```shell
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="18.04.4 LTS (Bionic Beaver)"
$ cat /proc/version
Linux version 5.3.0-40-generic (buildd@lcy01-amd64-024)
(gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1))
```
### 設定自動格式檢驗
在閱讀 [clang-format 的文件](https://clang.llvm.org/docs/ClangFormat.html)時，發現加入以下的程式碼後
```shell
function! Formatonsave()
let l:formatdiff = 1
pyf ~/llvm/tools/clang/tools/clang-format/clang-format.py
endfunction
autocmd BufWritePre *.h,*.cc,*.cpp call Formatonsave()
```
可以在使用 vim 寫入檔案的時候直接執行 clang-format 來修改格式
但是在家目錄並沒有類似的檔案，所以在查看[這個網站](https://askubuntu.com/questions/730609/how-can-i-find-the-directory-to-clang-format)後發現在`/usr/share/vim/addons/syntax/`有對應的`clang-format.py`可以做使用，所以將`.vimrc`中對應的路徑換為`/usr/share/vim/addons/syntax/clang-format.py`後，就可以在寫入檔案時修改格式
:::warning
請提交一個 pull request，關於 vim 和 clang-format 自動排版整合的建議，附於 `README.md` 檔案中
:notes: jserv
:::
> 已提交 pull request
> [name= Oscar][color= orange]
## 作業要求
* [ ] 修改 queue.[ch] 的相關實作
* [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* [ ] 研讀論文 [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) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
* [ ] 參照 [antirez/linenoise](https://github.com/antirez/linenoise)，強化 `qtest` 命令列功能，使其支援單行或多行編輯、歷史命令處理、命令自動補完 (例如輸入 `h` 之後按下 Tab 按鍵，自動接續補上 `elp`，成為完整的 `help` 命令)。除了整合程式碼外，應當說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
## 實作 queue
### 定義 `queue_t`
根據作業要求，為了讓 `q_insert_tail` 與 `q_size` 的實作能在時間複雜度為 $O(1)$ 的條件下完成，所以我在 `queue_t` 的結構中增加：
- `tail` 來記錄 `queue` 的最後一個元素的記憶體位置
- `size` 來儲存 `queue` 的元素個數
```cpp
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### 實作 `q_new()`
根據 Linux Programmer's Manual 對 `malloc` 回傳值的描述：
> The malloc() and calloc() functions return a pointer to the allocated
memory, which is suitably aligned for any built-in type. On error,
these functions return NULL. NULL may also be returned by a successful
call to malloc() with a size of zero, or by a successful call to cal‐
loc() with nmemb or size equal to zero.
可以知道 `malloc` 會在取得長度為 0 或是在取得記憶體發生錯誤時回傳 `NULL`
所以我們可以透過檢查 `malloc` 的回傳值來確認是否取得成功
如果成功取得 `queue_t` 的空間，就將 `head` 與 `tail` 初始化為 `NULL` ， `size` 則初始化為 0
```c=
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_size()`
根據作業描述中的實作，直接回傳 `q->size` 的數值來確保函式能在 $O(1)$ 也就是常數時間內完成
如果 `q` 或是 `q->head` 尚未取得記憶體位置時，直接回傳 0
```cpp
int q_size(queue_t *q)
{
if (!q || !q->head)
return 0;
return q->size;
}
```
:::warning
改寫為以下等價但簡潔的形式:
```cpp
int q_size(queue_t *q)
{
if (!q || !q->head)
return 0;
return q->size;
}
```
:notes: jserv
:::
> 已針對程式碼進行修改
> [name=Oscar][color=orange]
### 實作 `q_insert_head()`
先確認 `q` 不是 `NULL` ，如果不是 `NULL` 的話就 `malloc` 元素的空間，如果 `malloc` 失敗就 `return false`
如果 `malloc` 成功，接著 `malloc` 字串的空間，並將字串的內容複製進入，最後將新的元素連接在 `queue` 上，並更新 `q->size` 的數值
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
char *str;
int len = strlen(s);
// allocate the memory
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
str = malloc(len + 1);
if (!str) {
free(newh);
return false;
}
// connect the link
newh->next = q->head;
q->head = newh;
if (!q->tail)
q->tail = newh;
// copy the string
strncpy(str, s, len);
str[len] = '\0';
newh->value = str;
q->size++;
return true;
}
```
### 實作 `q_insert_tail()`
因為這個函式必須在常數時間（就是 $O(1)$ 的複雜度）內完成，所以我透過在 `queue_t` 的結構上宣告額外的 `tail` 指標來記錄最後一個元素的位置，達到快速插入元素的目的
如果這是 `queue` 中插入的第一個元素的話，就要額外更新 `q->head` 的值為 `newt` 以確保在執行其他操作的時候不會導致操作到 `q->head == NULL` 的情況發生
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
char *str;
int str_len = strlen(s);
// alocate memory
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
str = malloc(str_len + 1);
if (!str) {
free(newt);
return false;
}
// connect the list
newt->next = NULL;
if (!q->head)
q->head = newt;
else {
list_ele_t *tail = q->tail;
tail->next = newt;
}
q->tail = newt;
// cpoy the string
strncpy(str, s, str_len);
str[str_len] = '\0';
newt->value = str;
q->size++;
return true;
}
```
### 實作 `q_free()`
利用 `while` 來走訪整個 `queue` 的結構，先將字串的空間釋放之後，再將該元素的空間也釋放出來，最後將 `q` 的空間也釋放
```cpp
void q_free(queue_t *q)
{
/* Free queue structure */
if (!q)
return;
if (q->head) {
list_ele_t *pos = q->head;
list_ele_t *next;
while (pos) {
if (pos->value) {
free(pos->value);
}
next = pos->next;
free(pos);
pos = next;
}
}
free(q);
}
```
### 實作 `q_reverse()`
根據 `queue.c` 中對於 `q_reverse()` 函式的描述
> This function should not allocate or free any list elements
> (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
> It should rearrange the existing ones.
所以我們可以利用 `while` 從頭開始走訪每個元素，並將當前拜訪的元素接在 `tail` 之後的方式，將整個 `queue` 反轉過來
最後將 `q->head` 與 `q->tail` 的值換成過來
```c=
void q_reverse(queue_t *q)
{
if (!q)
return;
if (!q->head)
return;
list_ele_t *o_head = q->head;
list_ele_t *o_tail = q->tail;
list_ele_t *prev = q->head;
list_ele_t *next, *pos = q->head->next;
q->head->next = NULL;
while (pos) {
next = pos->next;
pos->next = prev;
prev = pos;
pos = next;
}
q->head = o_tail;
q->tail = o_head;
}
```
### 實作 `q_remove_head()`
在 `queue.c` 中有提到 `q_remove_head` 對於要刪除的字串所要進行的處理
> If sp is non-NULL and an element is removed, copy the removed string to *sp
> (up to a maximum of bufsize-1 characters, plus a null terminator.)
所以在我們調整 `queue` 的同時，如果需要將字串儲存起來的話，也要對字串進行處理，根據 Linux Programmer's Manual 對 `strncpy` 的說明：
> 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.
雖然在字串長度小於 `strncpy` 所輸入的參數 `n` 時會以 `'\0'` 填補，但為了避免 `n` 小於字串大小的情況發生，所以我一律在字串的最後額外指定為 `'\0'`
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
// break the connection of the head element
list_ele_t *rm = q->head;
q->head = q->head->next;
// copy string into sp if sp is non-NULL
if (sp && rm->value) {
strncpy(sp, rm->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
// free the element
free(rm->value);
free(rm);
q->size--;
return true;
}
```
### 實作 q_sort()
在排序演算法的部分，我使用 `merge sort` 來實作排序，因為 `merge sort` 的時間複雜度可以控制在 $O(n\ log\ n)$ 避免超出自動測試程式的時間限制
merge sort 的部分根據 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 所示範的來進行實作
在測試的過程中發現使用遞迴呼叫的 `merge sort` 會超出測試環境的 stack 大小發生 stack overflow 的狀況，因此將 `merge` 改為迭代實作
以 `merge` 將拆開的 `queue` 進行合併：
```c=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
list_ele_t *curr, *head;
if (strnatcmp(l1->value, l2->value) < 0) {
head = l1;
l1 = l1->next;
} else {
head = l2;
l2 = l2->next;
}
curr = head;
while (l1 && l2) {
if (strnatcmp(l1->value, l2->value) < 0) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
if (l1)
curr->next = l1;
if (l2)
curr->next = l2;
return head;
}
```
為了能夠使用 natural sort 來排序 `queue` ，我將 strnatcmp.[ch] 放入，並在 Makefile 中進行以下修改：
```Makefile
...
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
...
clean:
rm -f $(OBJS) $(deps) *~ qtest /tmp/qtest.*
rm -rf .$(DUT_DIR) .$(NAT_DIR)
rm -rf *.dSYM
(cd traces; rm -f *~)
```
並以 `mergeSort` 來將 `queue` 切割並排序，最後回傳新的 `queue` 的開頭位置
```c=
list_ele_t *mergeSort(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) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
// sort each list
list_ele_t *l1 = mergeSort(head);
list_ele_t *l2 = mergeSort(fast);
// merge sorted l1 and l2
return merge(l1, l2);
}
```
最後以 `q_sort` 作為主要的入口，並在排序結束後更新 `q->tail` 的位置
```c=
void q_sort(queue_t *q)
{
if (!q)
return;
else if (q->head == NULL)
return;
else if (q->size <= 1)
return;
q->head = mergeSort(q->head);
list_ele_t *tail = q->head;
while (tail->next)
tail = tail->next;
q->tail = tail;
}
```
參考 `traces` 目錄中的測試檔案並利用 natsort 所提供的 `sorted-words` 來打亂成下列的狀態，以 `qtest` 讀入檔案進行測試
```=
new
it pic02000
it pic05
it pic2
it pic120
it pic121
it tom
it x2-g8
it x2-y08
it x2-y7
it x8-y8
it 1-02
it 1-2
it 1-20
it 10-20
it fred
it jane
it pic01
it pic02
it pic02a
it pic3
it pic4
it pic100
it pic100a
sort
show
free
quit
```
但在進行測試時發現，自動測試系統會誤判 natural sort 的排序而印出下列訊息，而排序的情況則與 `sorted-words` 相同
```shell
ERROR: Not sorted in ascending order
```
:::warning
這是本作業要求相當特別的地方，實際需要從 [Natural sort order](https://en.wikipedia.org/wiki/Natural_sort_order) 去考量亂數字串產生器的設計
:notes: jserv
:::
> 已在下方新增以 natural sort 進行排序的設定
> [name=Oscar][color=orange]
#### 檢測是否使用 natural sort 排序
在 `qtest.c` 的 `do_sort` 函式中，會使用 `strcasecmp` 來檢測字串排序的正確性，但是本次作業使用 natural sort 進行排序，雖不影響自動評分系統的檢測，但仍可在設定中加入選項，以利自動評分系統檢測字串排序的正確性
如同 `simulation` 這個參數的設定一般，我在 `console.c` 中利用 `add_params` 函式設定使用 natural sort 的開關
在 `console.c` 的 `add_params` 中加入：
```c
add_param("natsort", (int *) &natsort, "Do/don't sort with natural sort", NULL);
```
讓 `qtest` 在讀到 `option natsort` 時可以更改 `natsort` 的數值
透過 `console.c` 更改 `natsort` 的值後，為了在 `qtest.c` 中判斷是否要使用 natural sort 進行檢測，我在 `console.h` 中加入：
```c
extern bool natsort;
```
讓 `qtest` 可以根據 `natsort` 的數值決定是否開啟 natural sort 來檢測
並將 `do_sort` 函式改為
```c=
bool do_sort(int argc, char *argv[])
{
...
if (q) {
for (list_ele_t *e = q->head; e && --cnt; e = e->next) {
/* Ensure each element in accurate order */
if (natsort) {
if (strnatcmp(e->value, e->next->value) > 0) {
report(1, "ERROR: Not sorted in natural order");
ok = false;
break;
}
} else {
if (strcasecmp(e->value, e->next->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
}
show_queue(3);
return ok && !error_check();
}
```
讓 `qtest` 可以判斷 `queue` 是否以 natural sort 進行排序
### 使用 valgrind 檢測記憶體空間管理
在執行自動測試程式的第 11 筆時候發現有記憶體未被釋放的錯誤訊息，使用 valgrind 進行測試，得到以下訊息：
```
==8149== 32 bytes in 1 blocks are still reachable in loss record 1 of 24
==8149== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8149== by 0x10B436: malloc_or_fail (report.c:189)
==8149== by 0x10BF48: add_cmd (console.c:123)
==8149== by 0x10C029: init_cmd (console.c:93)
==8149== by 0x10AC52: main (qtest.c:757)
...
```
根據訊息指出未被釋放的空間應該是 `malloc` 失敗之後才產生，因此修改 `q_insert_head` 與 `q_insert_tail` 中對於 `malloc` 失敗的字串空間進行釋放，解決 memory leak 的問題
### 使用 massif-visualizer 視覺化記憶體使用情形
為了能夠使用 massif ，須將 `--show-leak-kind=all` 這個指令刪除，並執行
```shell
valgrind --tool=massif ./qtest -f <test-data>
```
並將輸出之 `massif.out` 檔案以下列方式開啟
```shell
massif-visualizer <massif.out file>
```
在設定好 massif-visualizer 後，進行以下實驗：
在同樣進行以下檔案的指令時
```
new
ih head 20
ih tail 10
sort
rh test
rhq
rhq
free
quit
```
正常的記憶體用量應該回到 0 KB 的使用量，也就是如下圖所示
也就是在程式結束的時候， `Total Memory Heap Consumption` 的使用會回到 0
但是當程式未將所有的記憶體空間歸還時就會發生 `Total Memory Heap Consumption` 最後沒有回到 0 的情況發生，也就是如下圖所示
所以從實驗可知，利用 massif-visualizer 可以幫助我們利用視覺化的圖表來檢視程式的記憶體使用過程，並透過圖表分析是否有 `memory leak` 的情況產生
## dudect 實作原理
根據 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 所提到的 `dudect` 是利用重複測量函式在執行不同測資時的 CPU 循環時間，並利用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 分析資料是否有相同的母體平均值來判斷是否函式的執行複雜度是否為 $O(1)$
利用 [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 來分析程式的時間複雜度的好處是不會因為硬體差異而導致分析結果不同
程式實作的部分，在 `dudect/constant.c` 中的 `measure` 函式就是用來實作計算 CPU cycle 的，可以從程式碼中看到：
```c=
void measure(int64_t *before_ticks,
int64_t *after_ticks,
uint8_t *input_data,
int mode)
{
assert(mode == test_insert_tail || mode == test_size);
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();
}
}
}
```
在執行測試函式的前後利用 `cpucycles()` 記錄數字來計算，並將計算的結果記錄在 `before_ticks` 與 `after_ticks` 的陣列中，以利進一步的統計分析
而在 `cpucycle.h` 的參考資料 [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) 中有提到：
因為 Intel CPU 有計算 CPU cycle 的 counter ，所以在實作上就利用呼叫 `rdtsc` 來取得 `cycle_high` 與 `cycle_low` 的數值，並透過 bitwise 的操作將這兩個數值存在一個 64 bit 的 int 中
```c=
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 cycle 的測試資料後，透過在 `fixture.c` 的 `doit()` 函式的呼叫進行微分與 t test 的運算，如果計算後的 `t` 小於 `t_moderate_threshold` 時，表示執行時間符合 $O(1)$ 的限制，回傳 `true`
在 `fixture.c ` 中預設進行嘗試的最大次數為 10 次，如果在 10 次的測試中，統計結果符合限制的話，就會跳出測試的迴圈並回傳結果，也就是 `Probably constant time` 的輸出結果
## 解釋 `select` 使用方法
根據 Linux Programmer's Manual 中的說明：
> select() and pselect() allow a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for
> some class of I/O operation (e.g., input possible).
而在程式中的使用是在 `console.c` 中的 `cmd_select` 函式，用來控制程式能在可讀取或寫入的狀態下才執行
在 `run_console` 函式中就在 `cmd_done()` 不成立的時候執行 `cmd_select` 來監測並等待直到可以執行
## 利用 [antirez/linenoise](https://github.com/antirez/linenoise) 強化 `qtest` 功能
### 實作過程
在 linenoise 的範例程式 `example.c` 中所示範的是利用 `linenoise` 這個函式來讀取整行的輸入
透過在 `console.c` 中尋找關於 `cmd>` 相關的輸出後發現在 `run_console` 函式中有 `qtest` 執行時等待輸入的相關函式迴圈：
```c=
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;
}
```
在 `cmd_select` 函式中發現程式是透過 `readline()` 取得輸入字串，並執行 `interpret_cmd` 直譯輸入字串
```c=
int cmd_select(int nfds,
fd_set *readfds,
fd_set *writefds,
fd_set *exceptfds,
struct timeval *timeout)
{
...
if (readfds && FD_ISSET(infd, readfds)) {
/* Commandline input available */
FD_CLR(infd, readfds);
result--;
cmdline = readline();
if (cmdline)
interpret_cmd(cmdline);
}
return result;
}
```
所以為了引進 `linenoise` 我將該迴圈置換為：
```c=
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
/* original version
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
return err_cnt == 0;
*/
char *line;
while ((line = linenoise(prompt))) {
interpret_cmd(line);
free(line);
}
}
```
但發現透過測試發現出現下列錯誤：
```
cmd> help
cmd> help
Unknown command 'helprU'
```
我認為是 `interpret_cmd` 在進行參數切割的時候出現錯誤，且因為每次執行測試的時候所錯誤的指令後面都會帶有兩個不固定的字元(例如上述 `rU` 等等)，所以我認為是在切割字串的時候可能沒有將記憶體空間初始化所造成的。
```c=
static char **parse_args(char *line, int *argcp)
{
/*
* Must first determine how many arguments there are.
* Replace all white space with null characters
*/
size_t len = strlen(line);
/* First copy into buffer with each substring null-terminated */
char *buf = malloc_or_fail(len + 1, "parse_args");
char *src = line;
char *dst = buf;
bool skipping = true;
int c;
int argc = 0;
while ((c = *src++) != '\0') {
if (isspace(c)) {
if (!skipping) {
/* Hit end of word */
*dst++ = '\0';
skipping = true;
```
在查看 `parse_args` 函式後，發現上列程式碼的第 9 行所取得記憶體空間，也就是接下來要將輸入分析與複製的空間沒有先清空
在該處加上 `memset(buf, 0, len + 1)` 後，程式可正常執行
</br>
但是在測試時發現改用 `linenoise` 作為輸入後，無法透過 `-f` 參數或是執行 `source` 指令將檔案讀入。
再次看 `run_console` 函式後發現 `qtest` 會透過 `push_file` 重新設定 RIO 的 `fd` 等參數，並利用相同的迴圈與 `cmd_select` 函式將資料讀入，但在 `linenoise.c` 中可見：
```c=
char *linenoise(const char *prompt) {
char buf[LINENOISE_MAX_LINE];
int count;
if (!isatty(STDIN_FILENO)) {
/* Not a tty: read from file / pipe. In this mode we don't want any
* limit to the line size, so we call a function to handle that. */
return linenoiseNoTTY();
} else if (isUnsupportedTerm()) {
size_t len;
printf("%s",prompt);
fflush(stdout);
if (fgets(buf,LINENOISE_MAX_LINE,stdin) == NULL) return NULL;
len = strlen(buf);
while(len && (buf[len-1] == '\n' || buf[len-1] == '\r')) {
len--;
buf[len] = '\0';
}
return strdup(buf);
} else {
count = linenoiseRaw(buf,LINENOISE_MAX_LINE,prompt);
if (count == -1) return NULL;
return strdup(buf);
}
}
```
`linenoise.c` 中所預設使用的為 `STDIN_FILENO` 這個 file descriptor 所以導致無法將檔案內容讀入
所以我在 `linenoise.c` 裡加入新的 `int` 變數 `readfds` 儲存當前所使用的 file descriptor 並加入新的函式 `linenoiseSetDescriptor` ：
```c=
void linenoiseSetDescriptor(int fd)
{
readfds = fd;
}
```
透過呼叫 `linenoiseSetDescriptor` 來變更 `linenoise` 所使用的 file descriptor
回到 `console.c` 中修改 `push_file` 以呼叫 `linenoiseSetDescriptor`
```c=
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;
/* the original one
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;
*/
linenoiseSetDescriptor(fd);
return true;
}
```
可是程式依然無法正常讀取檔案的內容。經過 gdb 檢查後發現使用檔案的 file descriptor 時， linenoise 無法將檔案的 file descriptor 以 `enableRow` 函式正常開啟，所以導致無法輸入
因為 `linenoise` 在不支援的 Terminal 上執行時會利用 `fgets` 從 `stdin` 取得輸入，所以透過將 `linenoise` 修改為：
```c=
char *linenoise(const char *prompt)
{
char buf[LINENOISE_MAX_LINE];
int count;
if (!isatty(STDIN_FILENO)) {
/* Not a tty: read from file / pipe. In this mode we don't want any
* limit to the line size, so we call a function to handle that. */
return linenoiseNoTTY();
} else if (isUnsupportedTerm()) {
size_t len;
printf("unsupported %s", prompt);
fflush(stdout);
// add readf pointer to the parameter of fgets
if (fgets(buf, LINENOISE_MAX_LINE, stdin) == NULL)
return NULL;
len = strlen(buf);
while (len && (buf[len - 1] == '\n' || buf[len - 1] == '\r')) {
len--;
buf[len] = '\0';
}
return strdup(buf);
} else if (readfds != STDIN_FILENO) {
/* if the file descriptor is not STDIN_FILENO */
size_t len;
printf("%s", prompt);
fflush(stdout);
// add readf pointer to the parameter of fgets
if (fgets(buf, LINENOISE_MAX_LINE, readf) == NULL) {
fclose(readf);
readfds = STDIN_FILENO;
return NULL;
}
len = strlen(buf);
while (len && (buf[len - 1] == '\n' || buf[len - 1] == '\r')) {
len--;
buf[len] = '\0';
}
return strdup(buf);
} else {
count = linenoiseRaw(buf, LINENOISE_MAX_LINE, prompt);
if (count == -1)
return NULL;
return strdup(buf);
}
}
```
將檔案的輸入引進 `linenoise` 中，並回傳每一行的指令，使得 `-f` 參數與 `source` 指令得以執行
根據原始的 `qtest` 之行為，在執行 `source` 指令後不會因為讀取完畢而結束程式，所以加入 `run_source` 這個 `bool` 變數來確保檔案讀取完畢後可以再度切換為原本的輸入模式
### 使用 valgrind 檢測記憶體使用
為了測試在加入 `linenoise` 套件之後是否有 memory leak 的問題發生，使用 `make valgrind` 檢測發現問題發生
```
...
==8738== 1,295 bytes in 84 blocks are still reachable in loss record 3 of 3
==8738== at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==8738== by 0x52779B9: strdup (strdup.c:42)
==8738== by 0x10F208: linenoiseHistoryAdd (linenoise.c:1245)
==8738== by 0x10FF41: linenoiseHistoryLoad (linenoise.c:1334)
==8738== by 0x10C8A8: init_cmd (console.c:152)
==8738== by 0x10B272: main (qtest.c:757)
```
從輸出訊息研判 memory leak 發生的原因在使用 `linenoiseHistoryAdd` 所取得的記憶體未被釋放，因此我檢查 `linenoiseHistoryAdd` ：
```c=
int linenoiseHistoryAdd(const char *line)
{
char *linecopy;
if (history_max_len == 0)
return 0;
/* Initialization on first call. */
if (history == NULL) {
history = malloc(sizeof(char *) * history_max_len);
if (history == NULL)
return 0;
memset(history, 0, (sizeof(char *) * history_max_len));
}
/* Don't add duplicated lines. */
if (history_len && !strcmp(history[history_len - 1], line))
return 0;
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older line. */
linecopy = strdup(line);
if (!linecopy)
return 0;
if (history_len == history_max_len) {
free(history[0]);
memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
history_len--;
}
history[history_len] = linecopy;
history_len++;
return 1;
}
```
在該函式中可以看到， linenoise 主要是透過管理一個長度為 history_max_len 的字元指標陣列來存取從檔案中取得的記憶體位置的，但在程式結束後並沒有將對應的記憶體位置歸還，進而導致 memory leak 的情況發生
而在 `linenoise.c` 中也有對應的函式可以將這些記憶體空間釋放，在文件中有提到：
```c=
/* Free the history, but does not reset it. Only used when we have to
* exit() to avoid memory leaks are reported by valgrind & co. */
static void freeHistory(void) {
if (history) {
int j;
for (j = 0; j < history_len; j++)
free(history[j]);
free(history);
// printf("history released\n");
}
}
```
根據說明，在程式使用 exit() 結束時，會呼叫該函式來釋放記憶體空間
為了確定程式是否會正常呼叫，透過在 `freeHistory` 函式中加入輸出來測試，發現在使用檔案輸入時， `freeHistory` 並不會被正常執行
所以我利用強制在 `console.c` 的 `run_console` 函式要執行完畢前呼叫 `linenoiseAtExit` ，來確保記憶體空間都已被釋放
### 運作原理
#### 輸入實作
在輸入的操作上，原來的 `console.c` 與 `linenoise` 都是利用 `open` 來操作對應的 file descriptor ，如透過 stdin 輸入的 file descriptor: `STD_FILENO` 或是從檔案進行輸出的 file descriptor。
而在輸入的判斷上面，因為 `console.c` 中所使用的機制是利用 `RIO_ELE` 來儲存目前使用的 file desciptor 以及建立 buffer 空間，所以可以透過改變 file descriptor 的方式讓 `qtest` 得以自鍵盤或是檔案中取得輸入，並透過同一個迴圈，來處理不同方式的輸入
但在 `linenoise.c` 中，因為 `linenoise` 透過 `termios` 管理 terminal 的行為，而在 `linenoiseRaw()` 中，因為會透過 `eableRawMode` 開啟 `termios` 並進行設定
```c=
/* Raw mode: 1960 magic shit. */
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;
raw = orig_termios; /* modify the original mode */
/* input modes: no break, no CR to NL, no parity check, no strip char,
* no start/stop output control. */
raw.c_iflag &= ~(BRKINT | ICRNL | INPCK | ISTRIP | IXON);
/* output modes - disable post processing */
raw.c_oflag &= ~(OPOST);
/* control modes - set 8 bit chars */
raw.c_cflag |= (CS8);
/* local modes - choing off, canonical off, no extended functions,
* no signal chars (^Z,^C) */
raw.c_lflag &= ~(ECHO | ICANON | IEXTEN | ISIG);
/* control chars - set return condition: min number of bytes and timer.
* We want read to return every single byte, without timeout. */
raw.c_cc[VMIN] = 1; raw.c_cc[VTIME] = 0; /* 1 byte, no timer */
/* put terminal in raw mode after flushing */
if (tcsetattr(fd,TCSAFLUSH,&raw) < 0) goto fatal;
rawmode = 1;
return 0;
fatal:
errno = ENOTTY;
return -1;
}
```
在 `enableRawMode` 這段程式碼中， `termios` 透過 bitwise 的方式，也就是透過操作 `&=` 進行設定，最後使用 `linenoiseEdit` 來啟動 `history`, `move cursor`, `completion` 等功能
```c=
static int linenoiseEdit(int stdin_fd, int stdout_fd, char *buf, size_t buflen, const char *prompt)
{
struct linenoiseState l;
/* Populate the linenoise state that we pass to functions implementing
* specific editing functionalities. */
l.ifd = stdin_fd;
l.ofd = stdout_fd;
l.buf = buf;
l.buflen = buflen;
l.prompt = prompt;
l.plen = strlen(prompt);
l.oldpos = l.pos = 0;
l.len = 0;
l.cols = getColumns(stdin_fd, stdout_fd);
l.maxrows = 0;
l.history_index = 0;
/* Buffer starts empty. */
l.buf[0] = '\0';
l.buflen--; /* Make sure there is always space for the nulterm */
/* The latest history entry is always our current buffer, that
* initially is just an empty string. */
linenoiseHistoryAdd("");
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;
/* Only autocomplete when the callback is set. It returns < 0 when
* there was an error reading from fd. Otherwise it will return the
* character that should be handled next. */
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) {
case ENTER: /* enter */
history_len--;
free(history[history_len]);
if (mlmode) linenoiseEditMoveEnd(&l);
if (hintsCallback) {
/* Force a refresh without hints to leave the previous
* line as the user typed it after a newline. */
linenoiseHintsCallback *hc = hintsCallback;
hintsCallback = NULL;
refreshLine(&l);
hintsCallback = hc;
}
return (int)l.len;
case CTRL_C: /* ctrl-c */
errno = EAGAIN;
return -1;
...
default:
if (linenoiseEditInsert(&l,c)) return -1;
break;
...
}
}
return l.len;
```
而其中輸入的功能就是在第 33 行的地方，利用 `read` 函式將 `STD_FILENO` 的每一個字元輸入讀取進來，利用 `linenoiseEditInsert` 加進字串中，並根據不同的按鍵輸入進行不同的行為，最後在按下 `Enter` 離開這個函式。最後將字串的指標回傳出來。
#### 操作歷史記錄
歷史記錄的部分則可以透過 `linenoiseHistoryAdd` 可以得知
```c=
int linenoiseHistoryAdd(const char *line) {
char *linecopy;
if (history_max_len == 0) return 0;
/* Initialization on first call. */
if (history == NULL) {
history = malloc(sizeof(char*)*history_max_len);
if (history == NULL) return 0;
memset(history,0,(sizeof(char*)*history_max_len));
}
/* Don't add duplicated lines. */
if (history_len && !strcmp(history[history_len-1], line)) return 0;
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older line. */
linecopy = strdup(line);
if (!linecopy) return 0;
if (history_len == history_max_len) {
free(history[0]);
memmove(history,history+1,sizeof(char*)*(history_max_len-1));
history_len--;
}
history[history_len] = linecopy;
history_len++;
return 1;
}
```
`linenoise` 透過一個名為 `history` 的這個指標的指標來管理一個長度為 `history_max_len` 的字元指標陣列，而這個一維陣列中所存放的就是利用 `strdup` 所儲存的之前使用的指令。
如果要加入一個新的歷史記錄在一個已經到達 `history_max_len` 大小的 `history` 陣列時，就會執行第 20 行之後的指令，也就是利用 `memmove` 將第 1 ~ `history_max_len` 個元素往前搬，將第 0 個元素覆蓋掉，並將新的指令存在 `history[history_max_len]` 的位置，也就是只會記錄最新的前 `history_max_len` 個指令
而在呼叫 `linenoiseHistorySave` 的時候就是將 `history` 所管理的陣列利用 `fopen` 開啟並用 `fwrite` 寫入
#### 自動補全
自動補全的機制在 `linenoise/README.markdown` 中有提到，透過呼叫 `linenoiseSetCompletionCallback(completion)` 將下列函式的指標指派給 `linenoise`
```c
void completion(const char *buf, linenoiseCompletions *lc) {
if (buf[0] == 'h') {
linenoiseAddCompletion(lc,"hello");
linenoiseAddCompletion(lc,"hello there");
}
}
```
而在使用者進行輸入時， `linenoiseEdit` 將會呼叫我們所寫的 `completion` 函式，而根據輸入的結果，也就是根據 `*buf` 內容的不同，將不同的補全結果以 `linenoiseCompletions` 的形式儲存起來， `linenoiseCompletions` 的形式如下：
```c=
typedef struct linenoiseCompletions {
size_t len;
char **cvec;
} linenoiseCompletions;
```
而在 `linenoise.c` 中是透過 `linenoiseCompletion *lc` 來管理一個動態長度的陣列，而跟據 `*buf` 目前的輸入，將 `completion` 函式中對應的補全結果加入到 `*lc` 中，在使用者按下 `Tab` 的時候，就將 `*lc` 中所儲存的結果輸出在螢幕上
## 參考資料
1. [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c)
2. [Clang 11 documentation](https://clang.llvm.org/docs/ClangFormat.html)
3. [Dude, is my code constant](https://eprint.iacr.org/2016/1123.pdf)
4. [Welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)
5. [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)
6. [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution)
7. [antirez/linenoise](https://github.com/antirez/linenoise)
Sign in with Wallet
Connect another wallet