2022q1 Homework1 (lab0)

contributed by < cymizer >

GitHub

開發環境

$ 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

作業要求

Implement queue.[ch]
在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- 可依據前述說明，嘗試整合 tiny-web-server
共筆涵蓋項目
- 修正執行 Address Sanitizer 時會發生的錯誤
- 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
  Image Not Showing Possible Reasons
  - The image file may be corrupted
  - The server hosting the image is unavailable
  - The image path is incorrect
  - The image format is not supported
  Learn More →
  為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)
- 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- 2021q1, 說明 antirez/linenoise 的運作原理，注意到 termios 的運用
指出現有程式的缺陷 (提示: 和 RIO 套件有關)，嘗試強化並提交 pull request

透過 linux style API 實作佇列操作

閱讀及思考 list.h 裡面的 API 相關用法

TODO
container_of()
- TODO
- REF:

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() 將複製 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 的個數

檢查是否為 head 是否為 null，是的話則回傳 0
利用 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 中間的節點

檢查 head 是否為 null，是的話則回傳 false; 如果 list 在 empty 則回傳 false
- 在寫筆記時發現沒有做 list_empty() 的檢查。如果沒有做檢查的話，會造成後面程式執行的 invalid memory access。
- commit 2694889
透過 slow & fast 的方式來找到 mid node
從 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

檢查 head 是否為 null，是的話則回傳 false; 如果 list 在 empty 則回傳 false
透過 list_for_each() 尋訪 list node
因為可能會移除節點，所以除了 next 之外，還特別使用 safe 來保存下下個 node
如果比較結果相同 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 位置而非其值

一樣採用 list_for_each() 尋訪
將兩個相鄰 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 使用 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 分析記憶體問題

執行程式：

$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，搜尋 still reachable

依照錯誤訊息查看相關程式碼

問題一：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 定義

可以發現無相關釋放記憶體的程式碼在其中。所以嘗試在程式碼中搜尋 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. 經由 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

2022q1 Homework1 (lab0)

開發環境

作業要求

透過 linux style API 實作佇列操作

閱讀及思考 list.h 裡面的 API 相關用法

q_new

q_free

q_insert_head / q_insert_tail

q_remove_head / q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

以 Valgrind 分析記憶體問題

執行程式：

錯誤處理：

在 command 新增 `shuffle`, `web_server`

do_shuffle => q_shuffle

問題 and 筆記

為什麼 intrusive linked list 可以達到 Fewer memory allocations 和 Less cache thrashing.

command `it` 可以透過 `it RAND N` N= the number of element

可以透過 `time command` 來對後面的 command 來進行 profiling

2022q1 Homework1 (lab0)

開發環境

作業要求

透過 linux style API 實作佇列操作

閱讀及思考 list.h 裡面的 API 相關用法

q_new

q_free

q_insert_head / q_insert_tail

q_remove_head / q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_sort

以 Valgrind 分析記憶體問題

執行程式：

錯誤處理：

在 command 新增 shuffle, web_server

do_shuffle => q_shuffle

問題 and 筆記

為什麼 intrusive linked list 可以達到 Fewer memory allocations 和 Less cache thrashing.

command it 可以透過 it RAND N N= the number of element

可以透過 time command 來對後面的 command 來進行 profiling

Read more

2021q1 Homework1 (lab0)

FreeRTOS

Calling Convention

Memory Management

在 command 新增 `shuffle`, `web_server`

command `it` 可以透過 `it RAND N` N= the number of element

可以透過 `time command` 來對後面的 command 來進行 profiling