2020q1 Homework1 (lab0)

contributed by < OscarShiang >

tags: linux2020

測試環境

$ 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 的文件時，發現加入以下的程式碼後

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 來修改格式

但是在家目錄並沒有類似的檔案，所以在查看這個網站後發現在/usr/share/vim/addons/syntax/有對應的clang-format.py可以做使用，所以將.vimrc中對應的路徑換為/usr/share/vim/addons/syntax/clang-format.py後，就可以在寫入檔案時修改格式

請提交一個 pull request，關於 vim 和 clang-format 自動排版整合的建議，附於 README.md 檔案中

jserv

已提交 pull request
Oscar[color= orange]

作業要求

• 修改 queue.[ch] 的相關實作
• 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
• 研讀論文 Dude, is my code constant time?，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
• 參照 antirez/linenoise，強化 qtest 命令列功能，使其支援單行或多行編輯、歷史命令處理、命令自動補完 (例如輸入 h 之後按下 Tab 按鍵，自動接續補上 elp，成為完整的 help 命令)。除了整合程式碼外，應當說明 antirez/linenoise 的運作原理，注意到 termios 的運用

實作 queue

定義 queue_t

根據作業要求，為了讓 q_insert_tail 與 q_size 的實作能在時間複雜度為

$O(1)$ 的條件下完成，所以我在 queue_t 的結構中增加：

• tail 來記錄 queue 的最後一個元素的記憶體位置
• size 來儲存 queue 的元素個數

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

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

int q_size(queue_t *q)
{
    if (!q || !q->head)
        return 0;
    return q->size;
}

改寫為以下等價但簡潔的形式:

int q_size(queue_t *q)
{
    if (!q || !q->head)
        return 0;
    return q->size;
}

jserv

已針對程式碼進行修改
Oscar

實作 q_insert_head()

先確認 q 不是 NULL ，如果不是 NULL 的話就 malloc 元素的空間，如果 malloc 失敗就 return false
如果 malloc 成功，接著 malloc 字串的空間，並將字串的內容複製進入，最後將新的元素連接在 queue 上，並更新 q->size 的數值

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 的情況發生

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 的空間也釋放

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 的值換成過來

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'

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(nlogn)$ 避免超出自動測試程式的時間限制

merge sort 的部分根據 Linked List Sort 所示範的來進行實作

在測試的過程中發現使用遞迴呼叫的 merge sort 會超出測試環境的 stack 大小發生 stack overflow 的狀況，因此將 merge 改為迭代實作

以 merge 將拆開的 queue 進行合併：

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 中進行以下修改：

...

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 的開頭位置

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 的位置

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 相同

ERROR: Not sorted in ascending order

這是本作業要求相當特別的地方，實際需要從 Natural sort order 去考量亂數字串產生器的設計

jserv

已在下方新增以 natural sort 進行排序的設定
Oscar

檢測是否使用 natural sort 排序

在 qtest.c 的 do_sort 函式中，會使用 strcasecmp 來檢測字串排序的正確性，但是本次作業使用 natural sort 進行排序，雖不影響自動評分系統的檢測，但仍可在設定中加入選項，以利自動評分系統檢測字串排序的正確性

如同 simulation 這個參數的設定一般，我在 console.c 中利用 add_params 函式設定使用 natural sort 的開關
在 console.c 的 add_params 中加入：

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 中加入：

extern bool natsort;

讓 qtest 可以根據 natsort 的數值決定是否開啟 natural sort 來檢測
並將 do_sort 函式改為

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 這個指令刪除，並執行

valgrind --tool=massif ./qtest -f <test-data>

並將輸出之 massif.out 檔案以下列方式開啟

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? 所提到的 dudect 是利用重複測量函式在執行不同測資時的 CPU 循環時間，並利用 Welch's t-test 分析資料是否有相同的母體平均值來判斷是否函式的執行複雜度是否為

$O(1)$

利用 Student’s t-distribution 來分析程式的時間複雜度的好處是不會因為硬體差異而導致分析結果不同

程式實作的部分，在 dudect/constant.c 中的 measure 函式就是用來實作計算 CPU cycle 的，可以從程式碼中看到：

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 中有提到：
因為 Intel CPU 有計算 CPU cycle 的 counter ，所以在實作上就利用呼叫 rdtsc 來取得 cycle_high 與 cycle_low 的數值，並透過 bitwise 的操作將這兩個數值存在一個 64 bit 的 int 中

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 強化 qtest 功能

實作過程

在 linenoise 的範例程式 example.c 中所示範的是利用 linenoise 這個函式來讀取整行的輸入
透過在 console.c 中尋找關於 cmd> 相關的輸出後發現在 run_console 函式中有 qtest 執行時等待輸入的相關函式迴圈：

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 直譯輸入字串

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 我將該迴圈置換為：

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 等等)，所以我認為是在切割字串的時候可能沒有將記憶體空間初始化所造成的。

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) 後，程式可正常執行

但是在測試時發現改用 linenoise 作為輸入後，無法透過 -f 參數或是執行 source 指令將檔案讀入。
再次看 run_console 函式後發現 qtest 會透過 push_file 重新設定 RIO 的 fd 等參數，並利用相同的迴圈與 cmd_select 函式將資料讀入，但在 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("%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 ：

void linenoiseSetDescriptor(int fd)
{
    readfds = fd;
}

透過呼叫 linenoiseSetDescriptor 來變更 linenoise 所使用的 file descriptor
回到 console.c 中修改 push_file 以呼叫 linenoiseSetDescriptor

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 修改為：

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 ：

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 中也有對應的函式可以將這些記憶體空間釋放，在文件中有提到：

/* 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 並進行設定

/* 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 等功能

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 可以得知

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

void completion(const char *buf, linenoiseCompletions *lc) {
    if (buf[0] == 'h') {
        linenoiseAddCompletion(lc,"hello");
        linenoiseAddCompletion(lc,"hello there");
    }
}

而在使用者進行輸入時， linenoiseEdit 將會呼叫我們所寫的 completion 函式，而根據輸入的結果，也就是根據 *buf 內容的不同，將不同的補全結果以 linenoiseCompletions 的形式儲存起來， linenoiseCompletions 的形式如下：

typedef struct linenoiseCompletions {
  size_t len;
  char **cvec;
} linenoiseCompletions;

而在 linenoise.c 中是透過 linenoiseCompletion *lc 來管理一個動態長度的陣列，而跟據 *buf 目前的輸入，將 completion 函式中對應的補全結果加入到 *lc 中，在使用者按下 Tab 的時候，就將 *lc 中所儲存的結果輸出在螢幕上

參考資料

1. sysprog21/lab0-c
2. Clang 11 documentation
3. Dude, is my code constant
4. Welch's t-test
5. Code Execution Times: IA-32/IA-64 Instruction Set Architecture
6. Student’s t-distribution
7. antirez/linenoise