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 ，依據指示著手修改 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 欄位。

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

queue.c

q_free

• 持續釋放每個元素之空間，最後需將 q 本身也釋放。

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 也須更新。

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 是否為空。

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 中的 do_remove_head 的程式碼中理解 *sp 跟 bufsize 的範圍

#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] 來改變

add_param("length", &string_length, "Maximum length of displayed string", NULL);

所以 *sp 的第一個字元與最後一個字元為 \0，其餘皆為 X

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 中用來檢查回傳字串是否正確的 checks 變數，已經先將 checks[string_length] 設為 \0，而 string_length + 1 就是 q_remove_head 中的 bufsize，所以需要讓 sp[busize - 1] = '\0' 才能使 strcmp 通過。

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 的情形中，不能取其成員。

int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

q_reverse

• 可以先從 linked list 的 reverse 開始分析， reverse 中必定要有三個 pointer，分別為當前更新 next 之節點，與其前後兩個節點。
• 參考 gpwork4u 與 ZhuMon 的方法，將沒有使用到的 q->head->next 與 q->tail->next 用來記錄前面與中間的節點。
• 新增 rear 指標指向後方的節點
• 最後須將 q->head 與 q->tail 設定為正確位置

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 的結構

• 進入 while 迴圈前新增 tail 並將尾端相連

• 在 while 迴圈中，執行反轉四步驟

• 再經過一次迴圈，此時 q->head->next == q->tail 跳出迴圈

• 將 q->tail 與 q->head 替換，並將相連部分刪除即可。

q_sort

• 參考 Linked List Sort ，實現 merge sort，排序完後的 q->tail 不一定為尾端節點，故需額外尋找尾端來更新。

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 。

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
來改成更有「品味」的版本，

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

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 的部分出現問題。

add_param("simulation", (int *) &simulation, "Start/Stop simulation mode", NULL);

可以看到 init_cmd() 強制將 1 bytes 的 bool 型態 simulation 轉換為 int 型態，被限制使用的空間會被 Address Sanitizer 檢測出來。

只要將使用到 simulation 的部分改為 int 就行了。

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

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 數量改為固定

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 )。

Student’s t-distribution

Student’s t-distribution 為一種當變異數未知時，用來估計常態分布總體的均值。隨著自由度的增加，該分布會趨近於常態分佈，在做統計檢定時相當有用。

Welch's t-test

t-test 為一種統計檢定，可以用來檢定在變異數未知且取樣數量少時，兩個來自常態分配母體的獨立樣本之期望值的差是否為某一實數。

可以將 t-test 分成 Student's t-test 以及 Welch's t-test，兩者的區別只是在統計量 t 的分母不同，Student's t-test 使用情形在兩母體之變異數近似，而 Welch's t-test 則是在兩母體變異數不同的情況下使用。

根據 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 來檢定，在 dudect 中已經假設兩母體變異數不相等。

我們可以用統計檢定來解釋論文中使用的 t-test

$$\begin{gathered} H_0:{\mu }_0={\mu }_1 \\ {H}_1:{\mu }_0\ne {\mu }_1 \end{gathered}$$

此為一雙尾檢定，設定信賴水準為 95%，變異數未知，使用 Welch's t-test 來檢定。

$$t=\frac{\overline{X_0}-\overline{X_1}}{\sqrt{\frac{s_1^2}{N_1}+\frac{s_2^2}{N_2}}}$$
算出 t 值後，需算出自由度 df，根據 Welch–Satterthwaite equation 來計算，這邊因為只有 2 個 sample variance，故直接將公式展開

$$v\approx \frac{{(\frac{s_1^2}{N_1}+\frac{s_2^2}{N_2})}^2}{\frac{{\left(\frac{s_1^2}{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 中

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 公式，計算 t_value，根據 t_threshold_moderate 決定假設是否成立。

free ( line 22 ~ line 28 )

最後將分配的記憶體釋放，並回傳測試結果。

實作細節

紀錄一些較難理解的地方

randombytes

randombytes用來產生隨機數到指定的記憶體空間裡。但隨機數的是透過讀取 /dev/urandom 這個檔案裡的資料來產生。

不知道 dev/urandom 是幹嘛的，從 man page 裡可以找到

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 頁面中找資料

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 來計算變異數，需先計算 Sum of Squares，寫作

$M_2$。在 struct t_ctx 中用 m2 成員來記錄，而在需要時再轉換為變異數。

$$\begin{gathered} {\mu }_n={\mu }_{n-1}+\frac{x_n-{\mu }_{n-1}}{n} \\ {M}_{2,n}=M_{2,n-1}+(x_n-{\mu }_{n-1})(x_n-{\mu }_n) \\ {s}_n^2=\frac{M_{2,n}}{n-1} \end{gathered}$$

report

report 函式用來檢查假設是否成立。從 report 中並不知道 t_threshold_bananas 的用處，但從論文作者原始碼 fixture.c 就能看到是用來區分 Definitely not constant time 與 Probably not constant time 用的。

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 來運作的

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

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

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

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，Raw Mode 與 Cooked Mode。

Cooked Mode 為一般 linux terminal 的模式，會根據使用者的特定輸入來產生特定行為，例如 Control character。
Raw Mode 則類似 Vim 編輯器一樣，使用者的輸入將全部以 Raw Data 的形式傳給 terminal，而這正是我們想要的。

再來看看 termios 這個 structure，從 man page 裡的說明

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

The termios functions describe a general terminal interface that is provided to control asynchronous communications ports.

可以知道 termios 用來控制終端機介面裡的屬性，在 enableRawMode 函式裡更改相關屬性來達成 Raw Mode。而tcsetattr 與 tcgetattr 分別是用來接收與設置 terminal 當前屬性。

linenoiseEdit

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

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

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，用來處理游標操作。

最後在寫入到標準輸出上，印給使用者觀看。

linenoiseHistory

history 的概念很簡單，用一個 static char **history 來儲存每個歷史記錄內的字串，並呼叫 linenoiseHistoryAdd 來將新字串儲存到 history 中。

另外還提供搭配兩個函式 linenoiseHistorySave 與 linenoiseHistoryLoad 用來將 history 讀寫檔。

而要印出之前的 history，就必須呼叫 linenoiseEditHistoryNext 函式，該函式會在輸入上下鍵時呼叫。

#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 的範例程式，所有觸發相關的條件都必須寫在 callback function 裡。

而 linenoiseAddCompletion 則只儲存 completion 的結果 ，需透過 linenoiseCompletions 這個 structure 來儲存相關資料。

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

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 的範例程式，跟 completion 一樣，跟觸發相關的條件都必須寫在 callback function 裡。接著程式就會在 refresh 時呼叫 refreshShowHints 來顯示提示。

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 部分

while (!block_flag && read_ready()) {
    cmdline = readline();
    interpret_cmd(cmdline);
    prompt_flag = true;
}

注意到這邊 file 與 STDIN 的輸入方式皆使用 readline 來控制，為了要使用 linenoise 需區分這兩種情況

int fd = fname ? open(fname, O_RDONLY) : STDIN_FILENO;
is_file = fname ? true : false;

將 cmd_select 中用到 readline 的部分改成 linenoise

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 結尾。

char *dst = buf;
dst[len] = '\0';

這邊不了解為甚麼使用 readline 就不用加 \0 在結尾，看不出來 readline 與 linenoise 輸出的字串有甚麼差別。

接著實作自動補齊，只要比較目前字串與目標字串相等，Tab 鍵就能持續選擇下個可能的字串。

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);

再來是提示字串，可以簡單提示可輸入的參數

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 中就好了

linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave("history.txt"); /* Save the history on disk. */

開啟 multiline mode (雖然用不太到)

while ((c = getopt(argc, argv, "hv:f:l:m")) != -1) {
    ...
    case 'm':
        linenoiseSetMultiLine(1);
        break;
    ...
}

已知 Bug

• 當接受到 Ctrl_C 或 Ctrl_D 時有錯誤，下個指令會無法處理

現有程式的缺陷

readline 裡面的 read() 有可能會因為 signal 暫時中斷，但程式碼中好像未處理到關於 interrupt 的行為，查詢資料時翻閱到這篇很詳細的解釋 POSIX 中 read() 被 signal 中斷時的處理方式。

但為了要以第一手資料為主，翻閱 linux 裡 signal 的 man page 時看到這段

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 裡又寫道

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 這篇文章與上面提到的 多工作業下的資料讀寫處理事項 所述，我的理解是當已經有資料傳輸後，signal 中斷時 read() 會將已經傳輸的 bytes 數回傳，而尚未傳輸資料時，則回傳 -1 並設置 erron。

目前程式中的 readline 已經可以處理第一種情況，也就是已有資料傳輸時的情形，因為 buf_stack->cnt 會被設置為成功讀取字串的 bytes 數，就算 read 的時候被中斷，在 buf_stack->cnt == 0 時也會重新填補 buffer。

所以只要來應付第二種情況。在回傳值為 -1 時判斷是否為 EINTR 的 interrupt，將 read() 用 while 迴圈來判斷是否為 EINTR 的 error

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