2021q1 Homework1 (lab0)

contributed by < idoleat >

進度

• 實做 queue.[ch]
• 開啟 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

進行中

• 使用 Address Sanitizer 修正 qtest 錯誤
• 說明 antirez/linenoise 的運作原理，注意到 termios 的運用

實做 Queue

new

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

一個 queue struct 有三個 member：一個指標指向第一個 element、一個指標指向後一個 element，一個 int 紀錄 queue 的大小。所以在新增一個 queue 的時候，只要能成功分配到記憶體空間，就分別將大小設為 0 ，及指標初始化為 NULL，初始化為 NULL 可以作為之後 queue 裡面有沒有內容的判斷。

free queue

由於平時寫程式沒在做記憶體管理（都是讓程式結束執行全部清除，真糟糕），自然不熟悉 free()，以為 free() 會神奇的遞迴的（recursively）釋放指標所指的記憶體位置。但是實做時閱讀註解給的提示時發現似乎並不是這麼回事。

一個 queue 裡面的 element 結構如下：

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

list_ele_t *element = malloc(sizeof(list_ele_t));

經嘗試後發現 free(element) 和 free(element->value) 並 free(element) 的差別在於前者不會釋放 value 指標所指的字串，所以 free 一個 element 也要記得 free 裡面的字串，否則會造成記憶體洩漏。

所以要清除一個 queue 需要先自行遍歷過整個 queue ，並在確保 queue 本身不為 NULL 後清除每個 element 直到 head 為 NULL，記得連 value 指向的內容都清除掉，如下：

void q_free(queue_t *q)
{
    if (q == NULL)
        return;

    list_ele_t *it = q->head;
    while (it != NULL) {
        list_ele_t *next = it->next;
        free(it->value);
        free(it);
        it = next;
    }
    free(q);
}

insert head

要從頭插入 element 可以分兩種狀況：queue 裡面有東西，以及 queue 裡面沒東西。newh 為 new head，根據兩種狀況分析：

• queue 裡面沒東西

  1. 建立一個新的 element newh
  2. size++
  3. newh->next = NULL
     ( 其實直接 = head 就可以了，head 本來就是 NULL)
  4. head = newh
  5. tail = newh

• queue 裡面有東西

  1. 建立一個新的 element newh
  2. size++
  3. newh->next = head
  4. head = newh

建立一個新的 element 方式如下，首先檢查 queue 本身是否為 NULL，再來配置記憶體空間給 newh ，以及 newh 的字串內容，注意如果無法成功配置字串空間，記得也要連同原本的 newh 也釋放。這邊值得注意的一點是 strlen() 回傳的長度不包含空結尾的 '\0' ，所以配置及複製空間時要 +1，否則字串會沒有 '\0' 結尾，便會包含到接續記憶體中的內容，進而產生非預期中字元或亂碼。

if (q == NULL)
    return false;

list_ele_t *newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
    return false;

char *d = malloc(strlen(s) + 1);
if (d == NULL) {
    free(newh);
    return false;
}
strncpy(d, s, strlen(s) + 1);

比對 queue 裡面有東西及沒東西的狀況，只差在沒東西的時候要多一個 tail = newh，所以就在按照以上流程把 newh 接進 queue 裡面的時候多加一個判斷是否原本為空（以 size 判斷）決定是否需要 tail = newh。

newh->value = d;
newh->next = q->head;
q->size++;
if (q->size == 1)
    q->tail = newh;
q->head = newh;
return true;

insert tail

基本邏輯與 insert head 相同，一樣分兩種狀況分析，newt 為 new tail

• queue 裡面沒東西

  1. 建立一個新的 element newh
  2. size++
  3. newt->next = NULL
  4. head = newt
  5. tail = newt

• queue 裡面有東西

  1. 建立一個新的 element newh
  2. size++
  3. newt->next = NULL
  4. tail->next = newt
  5. tail = newt

建立一個新的 element 方式與 insert head 相同，在此略過。比對 queue 裡面有東西及沒東西的狀況，兩者在第四點有所差異，因此一樣透過判斷 size 大小決定行為，如下：

newt->value = d;
newt->next = NULL;
q->size++;
if (q->size == 1)
    q->head = newt;
else
    q->tail->next = newt;
q->tail = newt;
return true;

reverse

我總共用了三個 list_ele_t * 型態的物件來協助反轉 list: prev, current, look ahead。 current 會指向要修改 next 的 element。主要的操作是 current->next = prev，prev 會指向 current 前一個。但是如果單純這樣的話會斷了往下一個 element 的路徑（next 指向前者了），所以會需要一個提前在路還沒被斷之前往前跑的指標 look ahead 先記住下一個 element 的位置，稍後 current 才能移過去。而在 current 移往 look ahead 的位置之前 prev 必須先到 current 的位置，因為 prev 已經不再指向原先的下一個位置。

圖解

1. 初始狀態

2. current 所指的 element 將 next 改指向 prev

3. prev 指到 current 目前指的位置，current 指到 look_ahead 目前指的位置

4. look_ahead 往前看一個

5. 重複 2~4 直到 current 走完所有 element

實做

if (q == NULL)
    return;
if (q->head == NULL)
    return;

list_ele_t *prev = NULL, *current = q->head, *look_ahead;

q->tail = q->head;
while (current != NULL) {
    look_ahead = current->next;
    current->next = prev;
    prev = current;
    current = look_ahead;
}
q->head = prev;

個人感覺可以在更簡潔，或是更有「品味」一些，現在的寫法看起來有點視覺上的饒舌。例如使用 list_ele_t ** 可能會有更好的作法，有空來去觀摩一下其他同學的作法

size

在 queue 中新增一個 int 變數儲存 queue 的大小，在每次做 insert 及 remove 的時候修改，便可在之後直接查詢大小不必重新計算。

討論區中有 同學提問 為什麼不用 size_t 就好？反正大小不會是負的。老師給予 解釋，這邊簡短摘錄：

儘管 q_size() 回傳值應該要大於等於 0，但實際的行為可能涉及到對多個 queue 進行 q_size() 運算，例如比較 2 個 queue 的內部元素個數，除了運用大於、等於，和小於這樣的運算子，也可能被改寫 (無論是人為抑或編譯器最佳化) 為減法運算，即 q_size(Q1) - q_size(Q2)

感謝同學提問，同時讓我思考之前沒思考過的問題。

sort

使用哪種排序演算法？

我們必須考慮目前 list 的使用情景，可以被插入任意字串，沒有例如限定範圍、不能重複、已部份排序等限制，所以我們需要的是一個 general case 平均速度最快的，在我學過得排序演算法中 merge sort 及 quick sort 的平均複雜度 O(nlogn) 為最佳，但是 quick sort 無法保證每次都是 O(nlogn)，其 worst case 為 O(n²)，無法提供穩定可預期的執行時間，若在需要嚴格管控執行時間的環境執行可能會有無法預期之狀況，所以在此選用 merge sort 作為排序演算法。

實做過程

過程中寫 merge sort 寫一寫有點卡住 ( 天哪連大一都不如 )，參照老師給的 實做參考 寫了一個會用到 malloc 的版本，結果執行測試發現 malloc 在 sort 裡面是不允許的（目前先把他 push 到另一個 branch 上了）。把傳遞參數的界面修改一下之後發現其實也還真的用不到 malloc，所以平時可能有時候只是貪圖方便所以多使用了記憶體，之後配置記憶體前應該要多考一下是否真的必要。 實做參考中 merge_sort() 中把一個 list 切成兩個 list 的作法個人覺得十分簡潔好懂，值得學習。

q_sort() 為使用界面，merge_sort 本身應該另外實做

void q_sort(queue_t *q)
{
    if (q == NULL)
        return;
    if (q->head == NULL || q->size == 1)
        return;

    q->head = merge_sort(q->head);
    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}

實做 merge sort

list_ele_t *merge_sort(list_ele_t *head)
{
    if (head == NULL || head->next == NULL)
        return head;

    // split a list into two
    list_ele_t *left = head, *right = head->next; 
    while (right && right->next) {
        left = left->next;
        right = right->next->next;
    }
    right = left->next;
    left->next = NULL;

    return merge(merge_sort(head), merge_sort(right));
}

list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
    list_ele_t *head = NULL, *currrent = NULL;

    // attach head
    size_t LL = strlen(left->value);
    size_t RR = strlen(right->value);
    if (strncmp(left->value, right->value, LL > RR ? LL : RR) < 0) {
        currrent = left;
        left = left->next;
    } else {
        currrent = right;
        right = right->next;
    }
    head = currrent;

    while (left != NULL && right != NULL) {
        size_t L = strlen(left->value);
        size_t R = strlen(right->value);
        if (strncmp(left->value, right->value, L > R ? L : R) < 0) {
            currrent->next = left;
            left = left->next;
        } else {
            currrent->next = right;
            right = right->next;
        }
        currrent = currrent->next;
    }

    if (left != NULL)
        currrent->next = left;
    else
        currrent->next = right;

    return head;
}

後來經過測試發現有幾個 case 過不了，仔細看每個指令執行的紀錄發現是忘了重新指定 tail 的位置，tail 指在 queue 中間某個地方，一但 insert tail 就會從中間錯誤的 tail 位置把 queue 切斷然後接上新的 list element。目前沒有想到邊 merge 還維護 tail 的方法，所以就在 sort 完之後讓 q->tail 重新走到最後。隨機參照了一下 同學 的作法也是如此。

這部分開發耗時最久，其中還包括一些低級又浪費時間的錯誤，像是該傳入 left 的地方竟多打成 left->next，完全沒有邏輯的錯誤追查起來特別耗時。希望可以更謹慎小心不要再犯這種錯誤。

最後基本測試結果都有通過，接下來開始修正 qtest 錯誤及延伸問題

使用 Address Sanitizer 修正 qtest 錯誤 (WIP)

說明 antirez/linenoise 的運作原理，注意到 termios 的運用 (WIP)

閱讀要點

• 優點、缺點
• 抽絲剝繭
• 風格(設計原則)
• 重要實做手法
• 可以改進之處

可嘗試單獨功能抽離做實驗

流程

由幾個 core function 和一些 helper function 組成，呼叫linenoise() 之後會先判斷是否為 tty ( 可能為檔案輸入或是其他命令 pipe 過來 ) 以及是否為支援的 terminal 來進行個別處理，若是 tty 也是支援的 terminal，則開啟 RAW mode ，使用 termios 設定與 terminal 互動界面的參數 ( 詳細見下方說明 )，例如輸入時不要 parity check、輸出時不要 post processing、指定一個 char 為 8 bit等。

接著執行 linenoiseEdit() 並新增目前輸入為最新的歷史命令，裡面有個無限迴圈等待使用者輸入，同時也處理 linenoise 支援的各種快捷鍵 ( 但是他的快捷鍵沒什麼邏輯又跟 vim 不一樣到底有誰要用？除了 ctrl_C ) 及 Escape Sequence。若為正常字元輸入則呼叫 linenoiseEditInsert() 顯示字元到 terminal 中。

假設過程中沒有發生錯誤等到使用者按下 ENTER 時，則結束 linenoiseEdit() ，關閉 RAW mode（還原原本 terminal 互動界面的參數），把使用者輸入的字串從 buffer 中複製一份回傳。

待解決問題

• 為何要指定一個 char 為 8 bit？ 本來不是嗎？有可能不是嗎？

  有！詳見 What platforms have something other than 8-bit char?，你可見到若干機器的設定中，1 byte 可能是 9 bits (Honeywell 的主機, DEC PDP-10), 6 bits (DEC 早期機種), 16 bits (Texas Instruments C54x DSP, 至今仍廣泛使用)
  

  jserv

• 那個 escape sequence 怎麼用還看不是很懂
• linenoiseEditInsert()
  • 為啥會有 l->len >= l->buflen 和 l->plen + l->len >= l->cols 的情形？
• refreshSingleLine()
  • 前兩個 while 在幹麻？處理 l->plen + l->len >= l->cols 嗎？
• getColumn() 在幹麻？註解說：Use the ESC [6n escape sequence to query 是什麼？
• getCursorPosition() 在幹麻？
• enableRawMode() 上的註解：Raw mode: 1960 magic shit. 是什麼意思？

簡易流程圖 (WIP) (目前先用 drawio 快速打稿，之後在轉成 Graphiz)

架構

幾個 core function 和一些 helper function

termios 的使用

首先我們需要先認識 terminal，以我的電腦為例，我透過 $ echo $TERM 可以得知我的 terminal 是 xterm-256color。現在所指的 terminal 都是指 terminal emulator，亦即模擬 terminal 的一個程式，早期的 terminal 是一種連接電腦 (computer) 或計算系統 (computing system) 的獨立電子裝置，型態從電傳打字機 (teletype) 到顯示器加鍵盤組合包都有。早在獨立電子裝置的 terminal 的時期，為了要提供更進階的功能例如移動游標 (cursor) 到任意位置、清除部份螢幕顯示、顯示特殊字元等，便需使用 escape sequences, control characters 或 termios functions 完成文字輸入以外的特殊操作。現今 terminal emulators 大多也依然保有這些操作。而我電腦上的 xterm 是 X window system 上的 terminal emulator。

Linux kernel 內的 <termios.h> 提供了一些函式讓使用者描述與 terminal 互動的方式。termios structure 內的 member 如下:

tcflag_t c_iflag;      /* input modes */
tcflag_t c_oflag;      /* output modes */
tcflag_t c_cflag;      /* control modes */
tcflag_t c_lflag;      /* local modes */
cc_t     c_cc[NCCS];   /* special characters */

我們可以看到 linenoise 中 enableRawMode() ，對每個 flag 都進行了設置，其中 tcflag_t 是 unsigned integer bit mask 用來表示各種 flag。

input mode
output mode
control mode
local mode
special character

flush input?

termios 本身也有個設置 raw mode 的函式
cfmakeraw(): "raw" mode of the old Version 7 terminal driver

(更深入的細節和功能先暫時省略，不然把背後一大串相關資訊拉起來會討論不完)