---
tags: linux2022
---

# 2022q1 Homework1 (lab0)
contributed by < [cymizer](https://github.com/cymizer) >
> [GitHub](https://github.com/cymizer/lab0-c)

## 開發環境

$ uname -a
Linux notebook 5.8.0-55-generic #62~20.04.1-Ubuntu SMP Wed Jun 2 08:55:04 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux

$ gcc -v
gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           69
Model name:                      Intel(R) Core(TM) i5-4210U CPU @ 1.70GHz
Stepping:                        1
CPU MHz:                         800.000
CPU max MHz:                     2700.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4788.69
Virtualization:                  VT-x
L1d cache:                       64 KiB
L1i cache:                       64 KiB
L2 cache:                        512 KiB
L3 cache:                        3 MiB
NUMA node0 CPU(s):               0-3

## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
- [x] Implement queue.[ch]
- [x] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [x] 在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
- 共筆涵蓋項目
- [ ] 修正執行 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 時會發生的錯誤
- [ ] 運用 [Valgrind](https://valgrind.org/) 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 解釋 [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)
- [ ] 研讀論文 [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) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 2021q1, 說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request

---
## 透過 linux style API 實作佇列操作
### 閱讀及思考 [list.h](https://github.com/cymizer/lab0-c/blob/master/list.h) 裡面的 API 相關用法
- TODO
- container_of()
- TODO
- REF:
- [Linux的container_of 與 offsetof巨集](https://reurl.cc/12l92X)
- [Linux Kernel: container_of 巨集](http://adrianhuang.blogspot.com/2010/01/linux-kernel-containerof.html)
- [Linux 核心原始程式碼巨集: container_of](https://reurl.cc/LpeEpe)
### q_new
- 此函式的目標為建立一個新的 queue
1. 首先，去 malloc 一個 head node，如果在`分配記憶體空間失敗`，則會回傳 `NULL`.
2. 初始化 head，將 prev, next 都指向自己. 發現到可以使用 `INIT_LIST_HEAD(head)` 來做簡化.

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
+   INIT_LIST_HEAD(head);
-   head->next = head;
-   head->prev = head;
    return head;
}

### q_free
- 去把 queue 所用到的空間的做釋放
1. 先檢查所傳入的 list_head node 是否為 `NULL`
2. 透過 `list_for_each_safe()` 來尋訪 list 之 node 並從 list 中移除，在閱讀 `list.h` 裡面相關的註解，可以知道用此 api 去保證在尋訪 list node 並移除時的安全，因為他多使用了一個 `list_head *safe` 來保存下一個 node.
3. 透過 `container_of` 來得到 entry address，透過 `element_t pointer` 釋放其資源.

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *head = l;
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        list_del(node);
        element_t *ele = container_of(node, element_t, list);
        q_release_element(ele);
    }
    free(head);
}

### q_insert_head / q_insert_tail
- 要將 node 加入 list 的 head or tail
- q_insert_head
1. 檢查傳入的 node 是否為 NULL, 避免 access invalid address
2. 接著 allocate memory 給 `element *ele`，接著檢查是否 allocate 成功
3. 用 [strdup()](https://man7.org/linux/man-pages/man3/strdup.3.html) 將複製 string 給 `ele->value`，再做完之後檢查是否有 allocate 成功。
4. 最後用 `list_add()` 將 node 加入 list 中
- q_insert_tail
- 將 line 17 改成 `list_add_tail()` 即可

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *ele = malloc(sizeof(element_t));
    if (!ele) {
        return false;
    }
    struct list_head *ele_list = &ele->list;

    ele->value = strdup(s);
    if (!ele->value) {
        free(ele);
        return false;
    }
    list_add(ele_list, head);
    return true;
}

### q_remove_head / q_remove_tail
- 將 node 從 head or tail "移除"
- q_remove_head
1. 檢查 list head 為 NULL or list 裡面是 empty，是的話則回傳 NULL
2. 利用 container_of 得到 `head->next` 本身 `element_t` 的 address
3. 將 `head->next` 從 list 的 head 移除
4. 檢查 sp 是否為 NULL, 否的話則會進入。 將 element->val 複製到 sp buff 上。
- 需要注意 len 是否大於 bufsize，以及需要再最後填上 `\0` 當做
- q_remove_tail
- 將 line 5 改為 `*prev = head->prev;` ,和 line 6,7 改動為 `next` => `prev` 即可

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *next = head->next;
    element_t *ele = container_of(next, element_t, list);
    list_del(next);
    // if sp is non-NULL (handling)
    if (sp) {
        int len;
        for (len = 0; *(ele->value + len); len++)
            ;
        if (len > bufsize) {
            strncpy(sp, ele->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        } else {
            strncpy(sp, ele->value, len);
            sp[len] = '\0';
        }
    }
    return ele;
}

### q_size
- 計算 list 中 node 的個數
1. 檢查是否為 head 是否為 null，是的話則回傳 0
2. 利用 `list_for_each()` 尋訪 list ，最後回傳 list 長度

int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    int len = 0;
    struct list_head *node;

    list_for_each (node, head)
        len++;
    return len;
}

### q_delete_mid
- 刪除 list 中間的節點
1. 檢查 head 是否為 null，是的話則回傳 false; 如果 list 在 empty 則回傳 false
- 在寫筆記時發現沒有做 `list_empty()` 的檢查。 如果沒有做檢查的話，會造成後面程式執行的 invalid memory access。
- commit [2694889](https://github.com/cymizer/lab0-c/commit/26948891a6c8deba8c6a969df2c2af212e770964)
2. 透過 slow & fast 的方式來找到 mid node
3. 從 list 中移除 slow node 並釋放其資源後，回傳 ture

bool q_delete_mid(struct list_head *head)
{

    if (!head || list_empty(head))
        return false;
    struct list_head *slow, *fast;
    for (slow = head->next, fast = head->next->next;
         fast != head && fast->next != head;
         slow = slow->next, fast = fast->next->next)
        ;
    element_t *ele_mid = container_of(slow, element_t, list);

    list_del(slow);
    q_release_element(ele_mid);
    return true;
}

### q_delete_dup
- 移除 value 重複的 element

1. 檢查 head 是否為 null，是的話則回傳 false; 如果 list 在 empty 則回傳 false
2. 透過 `list_for_each()` 尋訪 list node
3. 因為可能會移除節點，所以除了 `next` 之外，還特別使用 `safe` 來保存下下個 node
4. 如果比較結果相同 `strcmp = 0` ，則將該 node 移除

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *node;
    list_for_each (node, head) {
        struct list_head *next = node->next;
        element_t *ele_node = container_of(node, element_t, list);
        for (struct list_head *safe = next->next; next != head;
             next = safe, safe = next->next) {
            element_t *ele_next = container_of(next, element_t, list);
            if (!strcmp(ele_node->value, ele_next->value)) {
                list_del(next);
                q_release_element(ele_next);
            } else
                break;
        }
    }
    return true;
}

### q_swap
- 參考 https://leetcode.com/problems/swap-nodes-in-pairs/ 之敘述，交換兩個 node 位置而非其值
1. 一樣採用 `list_for_each()` 尋訪
2. 將兩個相鄰 node 互相交換，要特別注意的是如果是 "奇數" 個 node 要特別處理，避免和 head node 交換造成結果錯誤。

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *node;
    list_for_each (node, head) {
        if (node->next == head)
            break;
        struct list_head *next = node->next;
        node->next = next->next;
        next->next->prev = node;

        next->next = node;
        next->prev = node->prev;

        node->prev->next = next;
        node->prev = next;
    }
}

### q_reverse
- 透過 `list_for_each_safe()` 走訪並將其 node 移到 head 的位置

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return;
    }
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        list_move(node, head);
    }
}

### q_sort
- 使用 merge sort ，並採用遞迴的方式來完成，參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 使用 list.h 來做改寫
- 共分為兩階段 ( divide and conquer )
- Split
- 用 slow & fast 的方法將 list 切半。並將其各自從 head list 加到 left, right list 中，並透過遞迴的方式將其分割到只剩一個 node 在透過 Merge 來做合併。
- Merge
- 尋訪 left 和 right list，兩兩 node 互相比較把值比較小的從 list 中移除加到 head list tail 直到其中一個 list 為空沒有 node。並使用 list_splice_tail() 將還不為空的 list 加到 head list tail。
- 在寫 Merge 時, 在要去寫`移除的節點`並`加入 head` 時會發生錯誤。如果使用原本的 code，會讀取到 head list 中的下個 node ，而非原本的所預期的 l or r 的 list node 中所指向的下個 node。將 line 1, 9, 10 移除，改成 line 10 才會符合預期情況。

        - struct list_head *l = left.next, *r = right.next;
        while (!list_empty(&left) && !list_empty(&right)) {
        +   struct list_head *l = left.next, *r = right.next;
            element_t *ele_l = container_of(l, element_t, list);
            element_t *ele_r = container_of(r, element_t, list);
            if (strcmp(ele_l->value, ele_r->value) <= 0) {
                list_del(l);
                list_add_tail(l, head);
        -       l = l->next;
            } else {
                list_del(r);
                list_add_tail(r, head);
        -       r = r->next;
            }
        }

- 完整 q_sort

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    // split
    struct list_head *slow, *fast;
    for (slow = head->next, fast = head->next->next;
         fast != head && fast->next != head;
         slow = slow->next, fast = fast->next->next)
        ;

    LIST_HEAD(left);
    LIST_HEAD(right);
    list_cut_position(&left, head, slow);
    // check node is odd or even
    fast = fast != head ? fast : fast->prev;
    list_cut_position(&right, head, fast);
    q_sort(&left);
    q_sort(&right);
    // Merge
    while (!list_empty(&left) && !list_empty(&right)) {
        struct list_head *l = left.next, *r = right.next;
        element_t *ele_l = container_of(l, element_t, list);
        element_t *ele_r = container_of(r, element_t, list);
        // strcmp  1: str1 > str2, 0: equal, -1: str1 < str2
        if (strcmp(ele_l->value, ele_r->value) <= 0) {
            list_del(l);
            list_add_tail(l, head);
        } else {
            list_del(r);
            list_add_tail(r, head);
        }
    }
    if (!list_empty(&left))
        list_splice_tail(&left, head);
    if (!list_empty(&right))
        list_splice_tail(&right, head);
}

## 以 [Valgrind](https://valgrind.org/) 分析記憶體問題
### 執行程式：

$make valgrind

會執行 `Makefile` 裡面`valgrind` 的部份

valgrind: valgrind_existence
     # Explicitly disable sanitizer(s)
     $(MAKE) clean SANITIZER=0 qtest
     $(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
     cp qtest $(patched_file)
     chmod u+x $(patched_file)
     sed -i "s/alarm/isnan/g" $(patched_file)
     scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
     @echo
     @echo "Test with specific case by running command:" 
     @echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"

會產生以下相關錯誤訊息

# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
...
cp qtest /tmp/qtest.pK4SCR
chmod u+x /tmp/qtest.pK4SCR
sed -i "s/alarm/isnan/g" /tmp/qtest.pK4SCR
scripts/driver.py -p /tmp/qtest.pK4SCR --valgrind 
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==85920== 6 bytes in 1 blocks are still reachable in loss record 1 of 3
==85920==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==85920==    by 0x4A4E50E: strdup (strdup.c:42)
==85920==    by 0x110B86: linenoiseHistoryAdd (linenoise.c:1236)
==85920==    by 0x111719: linenoiseHistoryLoad (linenoise.c:1325)
==85920==    by 0x10C77C: main (qtest.c:975)
==85920== 
==85920== 126 bytes in 19 blocks are still reachable in loss record 2 of 3
==85920==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==85920==    by 0x4A4E50E: strdup (strdup.c:42)
==85920==    by 0x110AFA: linenoiseHistoryAdd (linenoise.c:1236)
==85920==    by 0x111719: linenoiseHistoryLoad (linenoise.c:1325)
==85920==    by 0x10C77C: main (qtest.c:975)
==85920== 
==85920== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==85920==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==85920==    by 0x110B46: linenoiseHistoryAdd (linenoise.c:1224)
==85920==    by 0x111719: linenoiseHistoryLoad (linenoise.c:1325)
==85920==    by 0x10C77C: main (qtest.c:975)
==85920== 
---     trace-01-ops    5/5
...
==86183== 40 bytes in 1 blocks are still reachable in loss record 30 of 32
==86183==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==86183==    by 0x10CE21: malloc_or_fail (report.c:189)
==86183==    by 0x10D925: add_param (console.c:110)
==86183==    by 0x10C75A: console_init (qtest.c:826)
==86183==    by 0x10C75A: main (qtest.c:969)
...
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.pK4SCR --valgrind -t <tid>

### 錯誤處理：
錯誤訊息告訴我們記憶體 `still reachable` ，代表程式結束時仍有記憶體未釋放。
- 可以參考 [valgrind manual](https://valgrind.org/docs/manual/mc-manual.html#mc-manual.errormsgs)，搜尋 still reachable

依照錯誤訊息查看相關程式碼
1. 問題一 ：linenoiseHistoryLoad()
- qtest.c

    linenoiseHistorySetMaxLen(HISTORY_LEN);
    linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */

- linenoise.c

int linenoiseHistoryLoad(const char *filename)
{
    FILE *fp = fopen(filename, "r");
    char buf[LINENOISE_MAX_LINE];

    if (fp == NULL)
        return -1;

    while (fgets(buf, LINENOISE_MAX_LINE, fp) != NULL) {
        char *p;

        p = strchr(buf, '\r');
        if (!p)
            p = strchr(buf, '\n');
        if (p)
            *p = '\0';
        linenoiseHistoryAdd(buf);
    }
    fclose(fp);
    return 0;
}

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

它做的事情是將 `HISTORY_FILE = .cmd_history` 的資料載入到在 `linenoise.c:132` 的 `static char **history`。

> 註： HISTORY_FILE 可以用 `grep -r HISTORY_FILE` 找到在 `console.c` 定義
> [color=#3a9613]

可以發現無相關釋放記憶體的程式碼在其中。所以嘗試在程式碼中搜尋 `free` 關鍵字可以找到 `freeHistory` 。以 `freeHistory` 為關鍵字搜尋可以找到在 `linenoiseAtExit` 被使用。

呼叫關係為 run_console() => linenosie() => linenoiseRaw() => enableRawMode() => atexit(linenoiseAtExit()) => freeHistory()，其中 `atexit()` 是去註冊在程序離開結束被調用指定的函數。

所以將 main.c:975 => 移到 console.c:651 更為合理，在有 infile 的時候才會去載入`HISTORY_FILE`
- qtest.c

    linenoiseHistorySetMaxLen(HISTORY_LEN);
-   linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */

- console.c

bool run_console(char *infile_name)
{
    if (!push_file(infile_name)) {
        report(1, "ERROR: Could not open source file '%s'", infile_name);
        return false;
    }

    if (!has_infile) {
        char *cmdline;
        while ((cmdline = linenoise(prompt)) != NULL) {
            interpret_cmd(cmdline);
            linenoiseHistoryAdd(cmdline);       /* Add to the history. */
+           linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
            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;
}

2. 問題2. 經由 `console_init()` init 的 cmd_list 沒有被 release 掉

- 因為在使用 `make valgrind` 的時候會造成運算速度下降導致 不是`constant time`，近而造成 `ok` 這個 flag 變成 `false`，因為使用 `&&` 連帶影響到不會執行`finish_cmd()`。所以將其順序調換就可以進行 `finish_cmd()` 的動作。

- qtest.c

    bool ok = true;
    ok = ok && run_console(infile_name);
+   ok = finish_cmd() && ok;
-   ok = finish_cmd() && ok;

## 在 command 新增 `shuffle`, `web_server`
### do_shuffle => q_shuffle

## 問題 and 筆記
### 為什麼 intrusive linked list 可以達到 Fewer memory allocations 和 Less cache thrashing.
- REF: [Intrusive linked lists](https://reurl.cc/dX8eL2)
-
### command `it` 可以透過 `it RAND N` N= the number of element
### 可以透過 `time command` 來對後面的 command 來進行 profiling