# 2020q1 Homework1 (lab0)
contributed by < `gagachang` >
###### tags: `linux2020`
* [H01: lab0](https://hackmd.io/@sysprog/linux2020-lab0)

## 實作環境
* 作業系統：Ubuntu 18.04.3 LTS in VirtualBox VM
* Kernel version：5.3.0-40-generic
* gcc version：8.3.0
* RAM size：8GB

## 作業要求

* 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
* 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
* ==詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)== ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式。
* 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
* 不用理會 [Autolab](http://www.autolabproject.com/) 和檔案下載的描述，這兩者都是 CMU 專屬
* 修改排序所用的比較函式，變更為 [natural sort](https://github.com/sourcefrog/natsort)，在 "simulation" 也該做對應的修改，得以反映出 [natural sort](https://github.com/sourcefrog/natsort) 的使用。
* 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2020-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理;
* 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) :arrow_forward: 為避免「舉燭」，請比照 `qtest` 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)
* 挑戰題
* 參照 [antirez/linenoise](https://github.com/antirez/linenoise)，強化 `qtest` 命令列功能，使其支援單行或多行編輯、歷史命令處理、命令自動補完 (例如輸入 `h` 之後按下 Tab 按鍵，自動接續補上 `elp`，成為完整的 `help` 命令)。除了整合程式碼外，應當說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
* 思考如何預設開啟 AddressSanitizer，卻又能滿足效能測試所需 (可能需要兩種以上的 build target)
* 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request
* 截止日期：
* Mar 2, 2020 (含) 之前
* 越早在 GitHub 上有動態、越早接受 code review，評分越高

## 實作歷程
我主要照著 `driver.py` 吃測資的順序，來實作此份作業。
`q_new`, `q_insert_head`, `q_insert_tail`, `q_remove_head`, `q_reverse` 很快地就在一個下午內實作完成。

以下記錄實作時發生的一些問題：

### Fault 1 : test case No.15 and No.17
實作好 `q_insert_tail`，並執行 `make test` 時，發現無法通過第 15 及 17 筆測資。

:::danger
文字訊息不要用圖片展現
:notes: jserv
:::
此時的測試截圖如下：

此時的 `q_insert_tail` 程式碼如下:

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    size_t length;

    if (!q) {
        return false;
    }

    newt = malloc(sizeof(list_ele_t));
    if (!newt) {
        return false;
    }

    length = strlen(s);
    newt->value = malloc(length + 1);
    if (!newt->value) {
        free(newt);
        return false;
    }

    memset(newt->value, 0, length + 1);  // Clear the allocated memory to zero
    strncpy(newt->value, s, length);

    newt->next = NULL;
    q->tail->next = newt;
    q->tail = newt;
    q->size++;

    /* if there is only one element in queue, set the newt as q->head too */
    if (q->size == 1) {
        q->head = newt;
    }

    return true;
}

因為執行 `make test` 不會印出問題所在，此時使用 valgrind 單獨測試第 17 筆測資，發現是 `queue.c` 第 125 行出錯，馬上前往程式碼查看



當場發現這行是個 BUG，假若 queue 一開始為空的，且馬上呼叫 `q_insert_tail`，因為此時的 `q->tail = NULL`，因此這行程式碼就會變成 `NULL->next`，才會產生 invalid write !!

後來更改正確的程式碼，檢查 `q->tail` 是否為 NULL，即解決此 BUG。

### Fault 2 : valgrind --tool=massif error
使用 valgrind 並帶入 massif 工具參數進行測試 `qtest` 會發生下圖錯誤：


解決方法：將目錄下 `.valgrindrc` 檔案中的 `--show-leak-kinds=all` 移到 `--memcheck:leak-check=full` 前面。

### Fault 3 : test case NO.15
最後只剩下第 15 個 test case 沒過，如下圖：


決定先照著 `traces/trace-15-perf.cmd` 跑一遍測試，發現似乎是 `sort` 出問題：


嘗試執行 `valgrind --tool=massif ./qtest`，並將第 15 筆測資餵進去分析，結果發現 massif 無法成功執行，如下圖：


執行 `make valgrind` 分析記憶體行為，可發現有 Stack overflow 發生


看起來像是 Stack 空間滿了，發生在執行 `nat_isspace` 時，這是在排序中的比較函式 `strnatcmp` 中會呼叫到的函式，可見應該是在進行排序時讓 Stack 滿了，因為此時我實作的排序使用了[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)的 recursive 版本，因此勢必要將 recursive 改掉。

[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的另一版本為使用 pseudo node，但第 15 個測資無法 malloc 新的 element 使用，所以最後寫了最 naive 的版本 (程式碼紀錄在下節)，成功滿分！


:::info
有個奇怪的點是，執行 `make test` 有時候無法通過第 15 個測資，會只拿到 94 分，看起來跟程式效能有關連？猜測是因為執行分析而造成程式運作太久 alarm 到期 (不知是否為挑戰題第二部分)；而執行 `make valgrind` 則可以通過拿到滿分，以下是截圖證明。

make test (執行多次有時候會滿分)

make valgrind

:::
## 實作程式碼
打開 `queue.h`，發現裡面定義了我們要實作的資料結構以及函式。

### 主要資料結構
* **list_ele_t**

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

* **queue_t**

原先只有 head 這個指標變數，為了達成能在 $O(1)$ 的時間複雜度之下完成 `q_insert_tail` 和 `q_size`，新增了 tail 指標指向 queue 的尾端，以及一個 integer size，用來記錄目前 queue 的長度。

  typedef struct {
      list_ele_t *head;    // Pointer to the head of queue
      list_ele_t *tail;    // Pointer to the tail of queue
      int size;            // The size of queue
  } queue_t;

### **q_new**
宣告一個 queue 資料結構，並為其分配記憶體，若無法取得記憶體空間，則回傳 NULL；若成功取得記憶體，則初始化 q 的結構成員，並回傳 q 的位址。

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

:::success
在研讀老師的講座與實作此份作業之前，我並不知道 `malloc` 也會有失敗的時候，以後我會養成檢查 `malloc` 是否有成功的好習慣！
:::

### **q_free**

void q_free(queue_t *q)
{
    list_ele_t *temp;

    if (!q) {
        return;
    }

    while ((temp = q->head) != NULL) {
        if (temp->value) {
            free(temp->value);
        }
        q->head = q->head->next;
        free(temp);
    }

    free(q);
}

### **q_insert_head**

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    size_t length;

    if (!q) {
        return false;
    }

    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }

    length = strlen(s);
    newh->value = malloc(length + 1);
    if (!newh->value) {
        free(newh);
        newh = NULL;
        return false;
    }

    strncpy(newh->value, s, length);
    newh->value[length] = '\0';

    newh->next = q->head;
    q->head = newh;
    q->size++;

    /* if there is only one element in queue, set the newh as q->tail too */
    if (!q->tail) {
        q->tail = newh;
    }

    return true;
}

### **q_inset_tail**

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    size_t length;

    if (!q) {
        return false;
    }

    newt = malloc(sizeof(list_ele_t));
    if (!newt) {
        return false;
    }

    length = strlen(s);
    newt->value = malloc(length + 1);
    if (!newt->value) {
        free(newt);
        newt = NULL;
        return false;
    }

    strncpy(newt->value, s, length);
    newt->value[length] = '\0';

    newt->next = NULL;

    if (q->tail) {
        q->tail->next = newt;
    }
    q->tail = newt;
    q->size++;

    /* if there is only one element in queue, set the newt as q->head too */
    if (q->size == 1) {
        q->head = newt;
    }

    return true;
}

### **q_remove_head**

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    list_ele_t *original_head;

    if (!q || q->size == 0) {
        return false;
    }

    if (sp && q->head->value) {
        size_t length;
        length = strlen(q->head->value);
        length = length <= bufsize - 1 ? length : bufsize - 1;
        strncpy(sp, q->head->value, length);
        sp[length] = '\0';
    }

    original_head = q->head;
    q->head = q->head->next;

    if (original_head->value) {
        free(original_head->value);
    }
    free(original_head);
    q->size--;

    /* if there is no element in queue, just set the q->tail to NULL too */
    if (q->size == 0) {
        q->tail = NULL;
    }
    return true;
}

### **q_size**

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

### **q_reverse**
使用兩個指標進行 linked list 的反轉

void q_reverse(queue_t *q)
{
    if (!q || q->size == 0 || q->size == 1) {
        return;
    }

    list_ele_t *former, *latter;
    former = q->head;
    latter = NULL;

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

### **q_sort**
使用 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的 merge sort 版本實作 sorting

void q_sort(queue_t *q)
{
    if (!q || q->head == NULL || q->size < 2) {
        return;
    }

    q->head = merge_sort_list(q->head);

    // find the new q->tail
    list_ele_t *tail = q->head;
    while (tail->next) {
        tail = tail->next;
    }
    q->tail = tail;
}

list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
    // merge with recursive
    if (!right)
        return left;
    if (!left)
        return right;

    list_ele_t *head, *temp;

    // find the head of the two splitted lists
    if (strnatcmp(left->value, right->value) < 0) {
        head = left;
        left = left->next;
    } else {
        head = right;
        right = right->next;
    }

    // keep sorting
    temp = head;

    while (left && right) {
        if (strnatcmp(left->value, right->value) < 0) {
            temp->next = left;
            left = left->next;
        } else {
            temp->next = right;
            right = right->next;
        }
        temp = temp->next;
    }

    // check if there is a rest element
    if (left)
        temp->next = left;
    if (right)
        temp->next = right;

    return head;
}

list_ele_t *merge_sort_list(list_ele_t *head)
{
    if (!head || !head->next)
        return head;

    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

    // split list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    // sort each list
    list_ele_t *left = merge_sort_list(head);
    list_ele_t *right = merge_sort_list(fast);

    // merge
    return merge(left, right);
}

## Massif 視覺化 “simulation”
* 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗

## dudect 與 simulation 模式原理
* 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理;

## 解釋 select 原理
* 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz) :arrow_forward: 為避免「舉燭」，請比照 `qtest` 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)

## 挑戰題
* 參照 [antirez/linenoise](https://github.com/antirez/linenoise)，強化 `qtest` 命令列功能，使其支援單行或多行編輯、歷史命令處理、命令自動補完 (例如輸入 `h` 之後按下 Tab 按鍵，自動接續補上 `elp`，成為完整的 `help` 命令)。除了整合程式碼外，應當說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用

* 思考如何預設開啟 AddressSanitizer，卻又能滿足效能測試所需 (可能需要兩種以上的 build target)

* 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request