2021q1 Homework1 (lab0)

contributed by < toastcheng >

tags: `linux2021`

TODO

函式實作
開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
- 先執行 qtest 再於命令提示列輸入 help 命令，會使開啟 Address Sanitizer 觸發錯誤，應予以排除
運用 Valgrind 排除 qtest 實作的記憶體錯誤
並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
在 qtest 中實作 coroutine，並提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- 可嘗試整合 tiny-web-server，將 FORK_COUNT 變更為 0，並以 coroutine 取代原本的 fork 系統呼叫
解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)
說明 antirez/linenoise 的運作原理，注意到 termios 的運用
研讀論文 Dude, is my code constant time?，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
指出現有程式的缺陷 (提示: 和 RIO 套件有關)，嘗試強化並提交 pull request

0. 環境

首先來設置作為開發的環境，手邊較為方便的電腦有一台 Macbook Air，雖和 Linux 同是 Unix-like 的作業系統，但許多相關套件都略有出入，因此最初想使用 Virtualbox 來使用虛擬機，後來考量電腦負擔太重，轉而嘗試以容器化的方式可以更為輕量，因此用 docker 來準備需要的 linux 環境。

FROM ubuntu:20.04
RUN apt update
RUN apt install \
  -y \
  --no-install-recommends \
  build-essential \
  git \
  clang-format \
  cppcheck \
  aspell \
  colordiff \
  valgrind

build 完 docker image 後將需要的檔案掛載到容器中 (-v <host path>/<container path>) 執行 bash 便能開始進行開發。

$ docker build . -t lab0
$ docker run -v /Users/tushicheng/development/:/data -it lab0 bash
# uname -a
Linux 988da3fcde51 4.19.121-linuxkit #1 SMP Tue Dec 1 17:50:32 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

1. 函式實作

首先嘗試將尚未實作的函式完成，讓這個專案的基本功能可以運作。觀察 queue.h 可以一覽我們期望這個佇列 (queue) 資料結構 queue_t 的長相（此將註解省略）：








typedef struct {
    list_ele_t *head;
} queue_t;

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

queue_t 為一個含有連結串列 list_ele_t 的結構體，每個節點的值是字元指標，或俗稱的 C-style string，queue_t 應該支援的函式如下：

q_new 初始化，建構函式
q_free 解構函式
q_insert_head 在連結串列的開頭插入一個節點
q_insert_tail 在連結串列的尾巴插入一個節點
q_remove_head 移除連結串列的開頭節點
q_size 回傳連結串列的節點個數 (大小)
q_reverse 將連結串列的順序倒排
q_sort 將連結串列的節點依值的順序排序

`q_size`

commit: Add members to queue_t and impl insert head/tail

先從較為簡單的函式開始，q_size 需要回傳此佇列的大小，在最單純的情況，若我們只有連結串列的開頭 head，則必定需要花

O (n)

的時間走訪各個節點直到最後一個節點的 next 為 NULL，方能知道佇列的大小。

但每一次花費線性時間來取得佇列大小並不合理，最直接的方式是用一個額外的整數變數 size 來將佇列的大小資訊暫存起來，若佇列大小因為操作而改變（如 q_insert_head、q_remove_head），則我們一併修改 size 即可。

將 size 加入 queue_t ：




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

則 q_size 只需要將佇列的 size 回傳即可。




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

但若是佇列 q 為空，硬是去對其取值會引發 segmentation fault。

cmd> free
q = NULL
cmd> size
Warning: Calling size on null queue
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
Aborted

因此需要做一次額外的檢查，若 q 根本沒有初始化，也回傳 0。




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

// TODO inconsistence

`q_insert_tail`

q_insert_tail 將字串 s 加進佇列q 的尾巴。最單純的實作是先從佇列開頭一路走訪到最後一個節點，再將新節點加入，但這會跟 q_size 有一樣的問題，僅僅是加入一個節點卻要

O (n)

的時間複雜度。用相同的概念，我們可以再次在 queue_t 加入新變數 tail 來紀錄最後一個節點的位址，如此便省略從頭走訪的時間。





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

q_insert_tail 的主要實作很單純：將新的節點 newt (new tail) 指派給目前佇列的最後一個節點 q->tail->next = newt。

但其中有許多要注意的狀況：

q 若為空值需要回傳 false。
新節點 newt 若因為 malloc 失敗而為空值要回傳 false。
複製字串 s 時若失敗要回傳 false，並將本來已分配給 newt 的記憶體回收。
若佇列 q 尚無任何節點，q->head 和 q->tail 同為空值，則要將兩者都指派為 newt。
更新佇列的大小 q->size++。






























bool q_insert_tail(queue_t *q, char *s)
{
    // case 1.
    if (q) {
        list_ele_t *newt = malloc(sizeof(list_ele_t));
        // case 2.
        if (newt) {
            newt->next = NULL;
            size_t size = strlen(s) + 1;
            newt->value = malloc(sizeof(char) * size);
            // case 3.
            if (newt->value) {
                snprintf(newt->value, size, "%s", s);
                // case 4.
                if (!q->tail) {
                    q->head = newt;
                    q->tail = newt;
                } else {
                    q->tail->next = newt;
                    q->tail = newt;
                }
                // case 5.
                q->size++;
                return true;
            }
            free(newt);
        }
    }
    return false;
}

一開始並沒有顧及 malloc 回傳值為空的狀況，閱讀 man page malloc (3) 可以知道若是想分配的記憶體超過 RLIMIT_AS 或 RLIMIT_DATA 便會引發 ENOMEM 記憶體不足的錯誤，雖然在現代的電腦開發環境，很難觸碰到這個極限，但許多嵌入式系統的開發中，因為資源較為有限，因此這個限制會低得許多。

calloc(), malloc(), realloc(), and reallocarray() can fail with
the following error:
    ENOMEM Out of memory.  Possibly, the application hit the
    RLIMIT_AS or RLIMIT_DATA limit described in getrlimit(2).

那在我的機器上需要跟 malloc 要求多少記憶體才會引發 ENOMEM 呢？按照 man page的說明，繼續去找 getrlimit (2) 發現可以用 getrlimit 來使用系統呼叫：









#include <sys/resource.h>

int main() {
    struct rlimit rlp;
    getrlimit(RLIMIT_NPROC, &rlp);
    printf("max: %lu\n", rlp.rlim_max);
    printf("cur: %lu\n", rlp.rlim_cur);
    ...
}

rlimit 是一個帶有 soft limit、hard limit 的結構體。使用 getrlimit 時第一個參數傳入不同的 flag 便能得到 kernel 對不同資源的限制為何（結果會放在 rlimit 中）。

例如在這個作業中我想知道一個 process 允許被分配多少記憶體，就帶入 RLIMIT_NPPROC 這個 flag 即可。結果為：

max: 18446744073709551615
cur: 18446744073709551615

為一個非常大的值，這個值也剛好是

2^{64} - 1

。

但就算 malloc 成功，並不代表記憶體真的夠用，繼續閱讀 malloc (3) 會知道，kernel 有 overcommit 的機制，當要讀寫時發現記憶體真的不夠用時，process 便會被 OOM killer (Out of memory killer) 終止。

另外還有幾點實作的考量：

strlen

本來的實作是一個一個 byte 讀取，直到讀到 \0 終止。



size_t size = 1;
for (char *it = s; *it != '\0'; it++)
    size++;

起初很確信必然得這樣才能知道字串的長度（畢竟也沒有別的資訊了），但在你所不知道的 C 語言：數值系統篇中發現 strlen 還是比較快的實作方式，因為我們確實不必一次只讀一個 byte，可以一次讀 4 byte 再檢查其中有無 \0！

strcpy

strcpy 已被指出是不安全的函式，Common vulnerabilities guide for C programmers 中說明 strcpy 的問題在於沒有指出 buffer size 大小，如果字串複製的目的地太小，那複製後可能會蓋到其他的記憶體區段，也就是 Buffer overflow。








char str1[10];
char str2[]="abcdefghijklmn"; // size: 15
strcpy(str1,str2);
printf("str1: %s\n", str1);
printf("%s\n", str2);

printf("%lu\n", strlen(str1));
printf("%lu\n", strlen(str2));

str1: abcdefghijklmn
str2: klmn
size 1: 14
size 2: 4

這裡的問題在於 str1 的長度只有 10，str2 多出來的 5 字元寫到了自己所在的空間。

strcpy 後 str2 的記憶體空間被竄改了。

這也是為什麼 strlen(str2) 會變成 4，因為 \0 被寫到 str2 的第五個字元，後面的字元便被截掉了。

按照 CERN 的建議，換成 snprintf 即可有較為安全可預測的行為，第二個參數明顯的確保不會寫超過 10 bytes：








char str1[10];
char str2[]="abcdefghijklmn"; // size: 15
snprintf(str1, 10, "%s", str2);
printf("str1: %s\n", str1);
printf("%s\n", str2);

printf("%lu\n", strlen(str1));
printf("%lu\n", strlen(str2));

str1: abcdefghi
str2: abcdefghijklmn
size 1: 9
size 2: 14

當然如果故意把 buffer size 設超過 str1 的大小也是會有同樣 buffer overflow 問題，。


snprintf(str1, 15, "%s", str2);

`q_insert_head`

q_insert_head 將字串 s 加進佇列q 的開頭，跟 q_insert_tail 的實作相似
。函式的邏輯：將新的節點 newh (new head) 的 next 指向佇列當前的 head，並將佇列的 head 更新為 newh。
須要注意的地方跟 q_insert_tail 相似，因此不再贅述。






















bool q_insert_head(queue_t *q, char *s)
{
    if (q) {
        list_ele_t *newh = malloc(sizeof(list_ele_t));
        if (newh) {
            size_t size = strlen(s) + 1;
            newh->value = malloc(sizeof(char) * size);
            if (newh->value) {
                snprintf(newh->value, size, "%s", s);

                newh->next = q->head;
                q->head = newh;
                if (!q->tail)
                    q->tail = newh;
                q->size++;
                return true;
            }
            free(newh);
        }
    }
    return false;
}

`q_new`

這個函式將初始化一個佇列 queue_t，並將其變數也一併初始化並回傳，若沒有將指標 head 和 tail 設為空值，預設會是不確定 (indeterminate)，可以見這篇討論。因此後續確認節點存不存在的操作如 if (q->head) { ... } 實際上是會執行的，也就是說會認為 q->head 是有值的，而嘗試去 dereference 而發生錯誤。











queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q) {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
        return q;
    }
    return NULL;
}

`q_free`

將 q 所使用的記憶體釋放掉，也要將其管理的連結串列一併釋放，包括每個節點的字串。













void q_free(queue_t *q)
{
    if (q) {
        list_ele_t *it = q->head;
        while (it) {
            list_ele_t *tmp = it;
            it = it->next;
            free(tmp->value);
            free(tmp);
        }
        free(q);
    }
}

`q_remove_head`

q_remove_head 這個函式將第一個節點移除、釋放其記憶體空間，並將該節點的字串複製到給定的字元指標 sp。最一開始我沒有想太多，利用 memcpy 來處理 bufsize 空間不夠的狀況，為了滿足 sp 為一個大小最大為 bufsize - 1 的字串，將前 bufsize - 1 個字元複製過去，最後再補上終止字符 \0。







size_t size = strlen(q->head->value) + 1;
if (size > bufsize) {
    memcpy(sp, q->head->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
} else {
    memcpy(sp, q->head->value, size);
}

但後來參考了前面提及的 snprintf，可以將其改寫成較為簡潔的形式：


size_t size = strlen(q->head->value) + 1;
snprintf(sp, size > bufsize ? bufsize : size, "%s", q->head->value);

最後將開頭的節點釋放記憶體，並減少佇列的大小 q->size--。


















bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q && q->size > 0) {
        if (sp) {
            size_t size = strlen(q->head->value) + 1;
            snprintf(sp, size > bufsize ? bufsize : size, "%s", q->head->value);
        }

        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);

        q->size--;
        return true;
    }
    return false;
}

`q_reverse`

q_reverse 將連結串列的順序顛倒。首先將原本的 head 及 tail 保存下來，另外宣告兩個指標 prev 和 cur。用 cur 從 head 開始走訪各個節點， prev 則是如其名「跟在」 cur 後面，cur 將每個走訪到的節點的 next 都指向 prev，以此達到顛倒順序的效果，最後再將 q->head 及 q->tail 對調。



















void q_reverse(queue_t *q)
{
    if (q) {
        list_ele_t *h = q->head;
        list_ele_t *t = q->tail;

        list_ele_t *prev = NULL;
        list_ele_t *cur = q->head;

        while (cur) {
            list_ele_t *next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        q->head = t;
        q->tail = h;
    }
}

`q_sort`

q_sort 對連結串列做遞增排序。一開始我使用 quicksort 實作，但發現測試的條件有隨機的輸入以及「遞減」的輸入，對於 quicksort 來說如果 pivot 選擇不當，會讓 divide and conquer 效果大大降低，最壞情況是

O (n^{2})

的時間複雜度，並不適合這個情境，因此我考量使用 merge sort 來實作，無論是平均或是最壞情況都有

O (n \log n)

的複雜度。

q_sort 將連結串列交由 mergesort 進行排序，排序完後再從新的 head 開始找到最後一個節點，將其指派給 tail。而對於 q 為空值或是大小小於 2 不會做任何操作。











void q_sort(queue_t *q)
{
    if (q && q->size > 1) {
        mergesort(&q->head);
        list_ele_t *tmp = q->head;
        while (tmp->next) {
            tmp = tmp->next;
        }
        q->tail = tmp;
    }
}

mergesort 利用快慢指標，找到連結串列位於中間的節點，將其一分為二遞迴地執行，最後再將兩個連結串列用 merge 組合成排序完成的新串列。























void mergesort(list_ele_t **head)
{
    if ((*head)->next) {
        list_ele_t *fast = *head;
        list_ele_t *slow = *head;
        list_ele_t *prev = NULL;

        while (fast && fast->next) {
            fast = fast->next->next;
            prev = slow;
            slow = slow->next;
        }
        if (prev)
            prev->next = NULL;

        mergesort(head);
        mergesort(&slow);

        list_ele_t *result = NULL;
        merge(&result, *head, slow);
        *head = result;
    }
}

merge 則是真正進行合併的地方，將兩個連結串列從頭一一比對，*result 指向值較小的節點，並前進到下一個節點，較大的節點將繼續做下一輪的比較。直到其中一個連結串列走到盡頭，將連結串列*result 依序指向另一個連結串列剩下的節點。

























void merge(list_ele_t **result, list_ele_t *left, list_ele_t *right)
{
    while (left && right) {
        if (strcmp(left->value, right->value) > 0) {
            *result = right;
            right = right->next;
        } else {
            *result = left;
            left = left->next;
        }
        result = &((*result)->next);
    }

    while (left) {
        *result = left;
        left = left->next;
        result = &((*result)->next);
    }

    while (right) {
        *result = right;
        right = right->next;
        result = &((*result)->next);
    }
}

改進 merge sort

一開始我用了陣列的方式去思考，很習慣地在 merge 函式中、用











while (left) {
    *result = left;
    left = left->next;
    result = &((*result)->next);
}

while (right) {
    *result = right;
    right = right->next;
    result = &((*result)->next);
}

去處理剩餘的節點，但驚覺這裡可以優化，多虧連結串列的彈性，我能直接將剩餘的連結串列直接接在 *result 之後：


*result = right ? right : left;

短短一行便能完成，簡潔多了。

實作完以上函式，跑 make test 便能通過所有測試！

$ make test
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
---	trace-05-ops	5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---	trace-17-complexity	5/5
---	TOTAL		100/100

2. 透過 AddressSanitizer 分析

加入 SANITIZER=1 的 flag 重新 make 一次，在 qtest 裡下 help 後給出錯誤：

==574==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55e284086400 at pc 0x55e28406f7bd bp 0x7ffdc7839ca0 sp 0x7ffdc7839c90
READ of size 4 at 0x55e284086400 thread T0
    #0 0x55e28406f7bc in do_help_cmd /data/week1/lab0-c/console.c:307
    #1 0x55e28406f8d0 in interpret_cmda /data/week1/lab0-c/console.c:221
    #2 0x55e2840700b5 in interpret_cmd /data/week1/lab0-c/console.c:244
    #3 0x55e2840717f8 in run_console /data/week1/lab0-c/console.c:660
    #4 0x55e28406e3e5 in main /data/week1/lab0-c/qtest.c:780
    #5 0x7f94ca40b0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x55e28406bb8d in _start (/data/week1/lab0-c/qtest+0x8b8d)

0x55e284086401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55e284086400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /data/week1/lab0-c/console.c:307 in do_help_cmd

錯誤訊息中寫到 echo 這個全域變數似乎跟某個位在 0x55e284086401 的局域變數碰撞上了，很可能是 buffer overflow 所致，在某個 buffer 寫入超過其大小的 byte。

觀察 echo，宣告在 59 行：


static bool echo = 0;

其他被使用的方式只有正常的讀寫，除了 108 行：


add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);

將布林指標轉型成整數指標，兩種指標指向的記憶體位址大小不同，很可能是在寫入 echo 時溢出了，考量到 echo 接受來自命令列的輸入，將之設成 int 也不會影響其使用，因此便將宣告改成：


static int echo = 0;

重跑 make SANITIZER=1，得到新的錯誤訊息：

==2691==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55b42e086620 at pc 0x55b42e06d7b7 bp 0x7fff80b42ca0 sp 0x7fff80b42c90
READ of size 4 at 0x55b42e086620 thread T0
    #0 0x55b42e06d7b6 in do_help_cmd /data/week1/lab0-c/console.c:307
    #1 0x55b42e06d8ca in interpret_cmda /data/week1/lab0-c/console.c:221
    #2 0x55b42e06e0af in interpret_cmd /data/week1/lab0-c/console.c:244
    #3 0x55b42e06f7f5 in run_console /data/week1/lab0-c/console.c:660
    #4 0x55b42e06c3e5 in main /data/week1/lab0-c/qtest.c:780
    #5 0x7fce78de30b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x55b42e069b8d in _start (/data/week1/lab0-c/qtest+0x8b8d)

0x55b42e086621 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x55b42e086620) of size 1
  'simulation' is ascii string ''

這次將焦點放在 simulation 上，同樣為一個布林變數，但 simulation 並非靜態變數，意思是在其他目標檔中這個變數也是可見的，所以需要連同 console.h 中的宣告一併修改，改成 int simulation 之後再 make SANITIZER=1 一次，問題便解決了。

AddressSanitizer Algorithm 上針對 AddressSanitizer 的幾個核心功能做的簡短說明

3. 透過 Valgrind 分析

用 make valgrind 來使用 Valgrind 分析，可以發現到很多 still reachable 的記憶體區塊。

scripts/driver.py -p /tmp/qtest.Uu8zU3 --valgrind
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==2786== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==2786==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2786==    by 0x4A3E50E: strdup (strdup.c:42)
==2786==    by 0x1100D3: linenoiseHistoryAdd (linenoise.c:1236)
==2786==    by 0x110C66: linenoiseHistoryLoad (linenoise.c:1325)
==2786==    by 0x10C22C: main (qtest.c:769)
==2786==
==2786== 80 bytes in 19 blocks are still reachable in loss record 2 of 3
==2786==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2786==    by 0x4A3E50E: strdup (strdup.c:42)
==2786==    by 0x110047: linenoiseHistoryAdd (linenoise.c:1236)
==2786==    by 0x110C66: linenoiseHistoryLoad (linenoise.c:1325)
==2786==    by 0x10C22C: main (qtest.c:769)
==2786==
==2786== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==2786==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2786==    by 0x110093: linenoiseHistoryAdd (linenoise.c:1224)
==2786==    by 0x110C66: linenoiseHistoryLoad (linenoise.c:1325)
==2786==    by 0x10C22C: main (qtest.c:769)
==2786==
---	trace-01-ops	6/6
...

為避免被輸出訊息淹沒，可以分別跑不同的測試：

scripts/driver.py --valgrind -t 01

使用不同的測試資料，都是出現 still reachable 的訊息，可能意味著記憶體並沒有釋放。可以感受到 Valgrind 非常強大，在執行時期檢查記憶體使用情形，還能精確給出發生問題的行數。根據輸出資訊發現每一個測試結果是類似的，都是

linenoiseHistoryAdd


history = malloc(sizeof(char *) * history_max_len);

strdup



/* Add an heap allocated copy of the line in the history.
 * If we reached the max length, remove the older line. */
linecopy = strdup(line);

看起來都是跟 history 有關，所以先從 history 被釋放的地方找起，可以發現只有 freeHistory 這個函式會釋放記憶體，所幸釋放的路徑沒有太複雜，呼叫 freeHistory 的也只有 linenoiseAtExit 一個函式。

繼續觀察會發現整個函式呼叫的順序如下：

linenoise --> linenoiseRow --> enableRawMode --> atexit(linenoiseAtExit)

而 atexit(3) 是用來註冊當程式結束時要執行的函式。因此只要這個函式被呼叫到，history 應該要能被釋放。
















static int enableRawMode(int fd)
{
    struct termios raw;

    if (!isatty(STDIN_FILENO))
        goto fatal;
    if (!atexit_registered) {
        atexit(linenoiseAtExit);
    ...
}

static void linenoiseAtExit(void)
{
    disableRawMode(STDIN_FILENO);
    freeHistory();
}

直到看到 run_console 便豁然開朗，在 has_infile = true 的情況下，是不會去呼叫到 linenoise 的。


















bool run_console(char *infile_name)
{
    ...
    if (!has_infile) {
        char *cmdline;
        while ((cmdline = linenoise(prompt)) != NULL) {
            interpret_cmd(cmdline);
            linenoiseHistoryAdd(cmdline);       /* Add to the history. */
            linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
            linenoiseFree(cmdline);
        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }

    return err_cnt == 0;
}

解決的方式有二，一是將 history 正確釋放，二是不要去分配記憶體給他。前者因為 history 及對應的釋放函式都是 static 屬性，要改動 linenoise.c 及 linenoise.h，相對牽動的檔案比較多，而且跑檔案並沒有明顯紀錄歷史操作的需求，因此採取後者：若是跑檔案的模式 (-f)，則不分配記憶體給 history。





if (!infile_name) {
    linenoiseSetCompletionCallback(completion);
    linenoiseHistorySetMaxLen(HISTORY_LEN);
    linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
}

這樣便能順利通過 make valgrind。

(... 上略)

---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---	trace-17-complexity	5/5
---	TOTAL		100/100

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.Nv2TGq --valgrind -t <tid>

使用 `massif` 視覺化觀察

valgrind --tool=massif ./qtest -f traces/trace-01-ops.cmd
在 simulation 模式下，只會執行 is_insert_tail_const 及 is_size_const 這兩個函式，搭配 trace-17-complexity.cmd 來觀察：

// TODO

4. 實作 web server 及 coroutine

先試著玩玩 tiny-web-server。

root@35b88cfa2929:/data/week1/tiny-web-server# make
cc -Wall -O2 -o tiny tiny.c
root@35b88cfa2929:/data/week1/tiny-web-server# ./tiny
serve directory '/data/week1/tiny-web-server'
listen on port 9999, fd is 3
child pid is 25
child pid is 26
child pid is 27
child pid is 28

看看 localhost:9999，可以發現伺服器正常運作！

首先找出 tiny-web-server 監聽 port 9999 上流量以及對應 handler 的部分。
很快可以把範圍縮小到 process、handle_directory_request 函式。

觀賞一下 process 函式：





































void process(int fd, struct sockaddr_in *clientaddr) {
#ifdef LOG_ACCESS
	printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
	http_request req;
	parse_request(fd, &req);

	struct stat sbuf;
	int status = 200, ffd = open(req.filename, O_RDONLY, 0);
	if(ffd <= 0) {
		status = 404;
		char *msg = "File not found";
		client_error(fd, status, "Not found", msg);
	} else {
		fstat(ffd, &sbuf);
		if(S_ISREG(sbuf.st_mode)) {
			if (req.end == 0) {
				req.end = sbuf.st_size;
			}
			if (req.offset > 0) {
				status = 206;
			}
			serve_static(fd, ffd, &req, sbuf.st_size);
		} else if(S_ISDIR(sbuf.st_mode)) {
			status = 200;
			handle_directory_request(fd, ffd, req.filename);
		} else {
			status = 400;
			char *msg = "Unknow Error";
			client_error(fd, status, "Error", msg);
		}
		close(ffd);
	}
#ifdef LOG_ACCESS
	log_access(status, clientaddr, &req);
#endif
}

開頭 3 行是寫入 log，第 4 行將請求剖析成可用的結構體。第 8 行之後是將使用者的請求路徑用 open 打開，S_ISREG 查詢 man page inode (7) 中意思是 is it a regular file?。可以知道這裡是判斷該檔案合不合法的邏輯，若是合法檔案則由 serve_static 來處理，若是目錄，則由 handle_directory_request 處理。

接著看一下 serve_static 是如何處理客戶端的請求：































void serve_static(int out_fd, int in_fd, http_request *req,
				  size_t total_size) {
	char buf[256];
	if (req->offset > 0) {
		sprintf(buf, "HTTP/1.1 206 Partial\r\n");
		sprintf(buf + strlen(buf), "Content-Range: bytes %lu-%lu/%lu\r\n",
				req->offset, req->end, total_size);
	} else {
		sprintf(buf, "HTTP/1.1 200 OK\r\nAccept-Ranges: bytes\r\n");
	}
	sprintf(buf + strlen(buf), "Cache-Control: no-cache\r\n");
	// sprintf(buf + strlen(buf), "Cache-Control: public, max-age=315360000\r\nExpires: Thu, 31 Dec 2037 23:55:55 GMT\r\n");

	sprintf(buf + strlen(buf), "Content-length: %lu\r\n",
			req->end - req->offset);
	sprintf(buf + strlen(buf), "Content-type: %s\r\n\r\n",
			get_mime_type(req->filename));

	writen(out_fd, buf, strlen(buf));
	off_t offset = req->offset; /* copy */
	while(offset < req->end) {
		if(sendfile(out_fd, in_fd, &offset, req->end - req->offset) <= 0) {
			break;
		}
#ifdef LOG_ACCESS
		printf("offset: %d \n\n", (unsigned int)offset);
#endif
		close(out_fd);
		break;
	}
}

簡單來說，serve_static 會拿到一個 file descriptor out_fd，這是給客戶端的回應所使用的 file descriptor，先是在 buf 寫入回應的 header 以及內容，最後再一次用 writen 寫進 out_fd 並關檔。

這裡的情境並不需要開關檔，只需專注在如何在伺服器端讀取客戶端的請求，因此將 process 改寫並加上 handle_command 函式：








void process(int fd, struct sockaddr_in *clientaddr) {
#ifdef LOG_ACCESS
	printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
	http_request req;
	parse_request(fd, &req);
	handle_command(fd, req.filename);
}

而 handle_command 先把它做成很簡單的 echo server 來試試：









void handle_command(int out_fd, char *cmd) {
	printf("receiving command: %s\n", cmd);
	char buf[256];
	sprintf(buf, "HTTP/1.1 200 OK\r\n");
	sprintf(buf + strlen(buf), "Content-Type: text/plain\r\n\r\n");
	sprintf(buf + strlen(buf), "%s\r\n", cmd);
	writen(out_fd, buf, strlen(buf));
	close(out_fd);
}

這樣一來便能成功從客戶端接收指令！

accept request, fd is 4, pid is 69
receiving command: new

請求和回應可以順利改動之後，把焦點轉移到程式如何同時服務多個來自客戶的請求，在 main 中可以看到 fork 的使用：





















int i=0;
for(; i < FORK_COUNT; i++) {
    int pid = fork();
    if (pid == 0) {		 //  child
        while(1) {
            connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
            process(connfd, &clientaddr);
            close(connfd);
        }
    } else if (pid > 0) {   //  parent
        printf("child pid is %d\n", pid);
    } else {
        perror("fork");
    }
}

while(1) {
    connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
    process(connfd, &clientaddr);
    close(connfd);
}

在 for 迴圈中 parent 會產出 FORK_COUNT 個 child，而他們會陷進 while 迴圈接受請求，而 parent 自己在產完 child 之後也會進入最下方的 while 迴圈開始等待請求。

而在進入 for 迴圈之前有個有趣的地方：



// Ignore SIGPIPE signal, so if browser cancels the request, it
// won't kill the whole process.
signal(SIGPIPE, SIG_IGN);

查詢了 man page pipe (7)：

If all file descriptors referring to the read end of a pipe have been closed, 
then a write(2) will cause a SIGPIPE signal to be generated for the calling process.
If the calling process is ignoring this signal, then write(2) fails with the error EPIPE.

如果客戶端在伺服器寫完之前就關掉瀏覽器或是關閉 socket 連線，那會導致 write 發生錯誤而收到 SIGPIPE signal。預設會讓 process 直接終止，這邊把他忽略掉。

接著將之整合進 qtest，首先將 tiny.c 整理出需要的函式，並新增 header 檔 tiny.h，在這我一併將 main() 更名成 start_server() 以供 qtest 使用。

qtest.c 中，加入命令 web：

























































#include "tiny.h"

static bool do_web(int argc, char *argv[]);

void start_server() {

	struct sockaddr_in clientaddr;
	int default_port = DEFAULT_PORT,
		listenfd,
		connfd;
	socklen_t clientlen = sizeof clientaddr;


	listenfd = open_listenfd(default_port);
	if (listenfd > 0) {
		printf("listen on port %d, fd is %d\n", default_port, listenfd);
	} else {
		perror("ERROR");
		exit(listenfd);
	}

	int i=0;
	for(; i < FORK_COUNT; i++) {
		int pid = fork();
		if (pid == 0) {		 //  child
			while(1) {
				connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
				process(connfd, &clientaddr);
				close(connfd);
			}
		} else if (pid > 0) {   //  parent
			printf("child pid is %d\n", pid);
		} else {
			perror("fork");
		}
	}

	while(1) {
		connfd = accept(listenfd, (SA *)&clientaddr, &clientlen);
		process(connfd, &clientaddr);
		close(connfd);
	}
}

static void console_init()
{
    ...
    add_cmd("web", do_web, "                | Start a web server");
    ...
}

static bool do_web(int argc, char *argv[])
{
    report(3, "start server..");
    start_server();
    return true;
}

也要在 Makefile 中加入 tiny.o 才能連結到目標：
Makefile 中新增 tiny.o：

OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        linenoise.o \
		tiny.o

重新 make 過後就成功加入新功能！

root@35b88cfa2929:/data/week1/lab0-c# make
  CC	tiny.o
  LD	qtest
root@35b88cfa2929:/data/week1/lab0-c# ./qtest
cmd> web
start server..
listen on port 9999, fd is 3
child pid is 379
child pid is 380
child pid is 381
child pid is 382

接下來的問題是，如何將收到的請求轉換成命令執行。目前的程式碼依靠 linenoise 將命令列的命令讀取出來，再交由 interpret_cmd 執行，以及存入歷史等，詳細可以參見 run_console 函式：







char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
    interpret_cmd(cmdline);
    linenoiseHistoryAdd(cmdline);       /* Add to the history. */
    linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
    linenoiseFree(cmdline);
}

我希望可以重複使用 interpret_cmd，讓它也能處理來自使用者的請求，因此將其加入 console.h ，從 static 函式改為一般的函式供其他檔案 (qtest.c) 使用。而我希望使用者可以從伺服器的回應看見佇列的資訊，但所有的命令都是透過 report 函式將訊息呈現在命令列，一時間難以全面支援伺服器版本，因此新增函式 void write_queue_info(char *buf) 來將 show_queue 的資訊寫入 buffer，再由 handle_command 將該資訊回應給使用者。















void handle_command(int out_fd, char *cmd)
{
    printf("receiving command: %s\n", cmd);
    interpret_cmd(cmd);
    char info[QUEUE_INFO_LEN];
    write_queue_info(info);

    char buf[RESP_BUF_LEN];
    snprintf(buf, RESP_BUF_LEN - strlen(buf) - 1, "HTTP/1.1 200 OK\r\n");
    snprintf(buf + strlen(buf), RESP_BUF_LEN - strlen(buf) - 1,
             "Content-Type: text/plain\r\n\r\n");
    snprintf(buf + strlen(buf), RESP_BUF_LEN - strlen(buf) - 1, "%s\r\n", info);
    writen(out_fd, buf, strlen(buf));
    close(out_fd);
}

在將 tiny.c 加入的同時發現它並不符合 commit hook 的規範，所以也順便將其改寫，避免使用 sprintf 而用 snprintf 加上 buffer size，以防 buffer overflow。

對應的 Github commit: Add tiny-web-server to qtest。

root@35b88cfa2929:/data/week1/lab0-c# ./qtest
cmd> web
start server..
listen on port 9999, fd is 3
receiving command: new
q = []
receiving command: ih hello
q = [hello]

最後試著用 coroutine 的方式改寫 web 命令。先 #include <setjmp.h> 來使用 setjmp、longjmp。想了一些方式實作 coroutine，但先從簡單的命令列和伺服器切換開始，coroutine 跟 multithread 的差異之一是，切換工作時是「自發的」，也就是說一個 coroutine 在讓出 cpu 的時間點是事先設計好的，例如 Golang 中的 goroutine (coroutine) 設計在引發 function call 的時候讓出 cpu。

因為我的實作中伺服器和命令列執行命令會是執行相同的函式，所以我使用了一個變數 is_cmd 來決定現在要換成誰執行，然後用兩個 jmp_buf 來管理伺服器和命令列兩邊的 context。



static bool is_cmd = true;
static jmp_buf cmd_buf;
static jmp_buf web_buf;

在 server 接受連線前 setjmp：





if (setjmp(web_buf) > 0)
        report(3, "back to server, serving..");
connfd = accept(listenfd, (SA *) &clientaddr, &clientlen);
handle_command(connfd);
close(connfd);

然後讓出 cpu 的時間點，簡單起見我只在 insert_head 和 insert_tail 執行完時設定 longjmp：


is_cmd = !is_cmd;
longjmp(is_cmd ? cmd_buf : web_buf, 1);

有一個須要注意的點，在 longjmp 回到當初 setjmp 處時，局域變數的值會改變！這一點會造成不可預期的錯誤，以此為例：listenfd 是伺服器創造的 socket descriptor，伺服器會重複使用它來接受一個又一個的連線，但當從 longjmp 跳躍回來時，它的值卻

cmd> web
start server..
listen on port 9999, fd is 3
listen fd: 3
receiving command: new
q = []
cmd> it 9
q = [9]
back to server, serving..
listen fd: 80923806

因此將 listenfd 放置在全域讓其在 coroutine 切換時不會改變，更標準一點的做法應該是可以有一個 context 結構，保存這些重要資訊，其中包含 jmp_buf。

最後重新 make 便能得到支援 coroutine 切換的版本。對應的 Github commit: Implement coroutine to execute both cmd and server

root@35b88cfa2929:/data/week1/lab0-c# ./qtest
cmd> web
start server..
listen on port 9999, fd is 3
receiving command: new
q = []
cmd> ih 9
q = [9]
back to server, serving..
receiving command: ih 8
q = [8 9]
back to command line..
cmd>

5. 分析 `console.c` 實作及 select 系統呼叫

// TODO

6. 分析 `antirez/linenoise`

// TODO

7. 分析 simulation 模式

// TODO

8. 分析現有程式缺陷

// TODO

2021q1 Homework1 (lab0)

tags: linux2021

TODO

0. 環境

1. 函式實作

q_size

q_insert_tail

q_insert_head

q_new

q_free

q_remove_head

q_reverse

q_sort

改進 merge sort

2. 透過 AddressSanitizer 分析

3. 透過 Valgrind 分析

使用 massif 視覺化觀察

4. 實作 web server 及 coroutine

5. 分析 console.c 實作及 select 系統呼叫

6. 分析 antirez/linenoise

7. 分析 simulation 模式

8. 分析現有程式缺陷

Read more

Leetcode category

2021q1 Homework3 (quiz3)

2021q1 Homework2 (quiz2)

2021q1 Homework1 (quiz1)

tags: `linux2021`

`q_size`

`q_insert_tail`

`q_insert_head`

`q_new`

`q_free`

`q_remove_head`

`q_reverse`

`q_sort`

使用 `massif` 視覺化觀察

5. 分析 `console.c` 實作及 select 系統呼叫

6. 分析 `antirez/linenoise`