Try  HackMD Logo HackMD

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 仍可接受其他命令
  • 共筆涵蓋項目
    • 修正執行 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 相關用法

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 的個數
  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
  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

  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 使用 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 ，代表程式結束時仍有記憶體未釋放。

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

  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 定義

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

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

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

Last changed by 
 
YM Chen
0
435

Read more

2021q1 Homework1 (lab0)

contributed by < cymb103u >

Jul 22, 2023
FreeRTOS

Memory Allocation heap Heap Init ,如果沒有使用過的話 xWantSize +=HeapStructSize 和做 alingment heapSTRUCT_SIZE = ( ( sizeof( BlockLink_t ) + ( portBYTE_ALIGNMENT - 1 ) ) & ~portBYTE_ALIGNMENT_MASK );

Jan 25, 2022
Calling Convention

Caller / Callee 的關係，為什麼要分開有 Caller / Callee? 因為函式呼叫牽涉到參數的傳遞, 並不只是單純跳到那個Address執行程式碼再跳回來這麼簡單, 呼叫副程式(callee)的主程式(caller), 需要知道怎麼填參數,副程式才能接到參數後進行處理, 再將結果, 傳給主程式, 所以這段協定, 稱之為Calling Convention(呼叫慣例)。 呼叫慣例 (Calling Convention) 函式的呼叫，在不同的指令集有所差別，透過呼叫慣例 (Calling Convention)規範下，描述了函數的呼叫方式。 例如： caller 或 callee 去分別要負責保存哪些 register

Jan 4, 2022
Memory Management

How to refer memory in a program – Address Binding 決定程式起始位置，即程式要在記憶體的哪個地方開始執行。Binding 有 3 個可能執行的時機，compile time, load time 和 execution time。 Compile Time 程式中的資料、參數等必須要有對應的記憶體位置，早期的作法是在編譯期間，就決定要放在哪裡。Compiler 會將組合語言轉換成實際的記憶體位置 在 compile time 就做 binding 的缺點是若起始地址變更(可能該地址被其他 process 占住)，則需要重新編譯 (recompile)，等於要關閉並重新執行 Load Time Compiler 不會決定實際的記憶體地址，而是會留一個變數(Base Register)，給出相對位置。程式讀取(Load)的時候，確定 memory 哪裡有空位之後，才透過該變數決定真正的地址

Dec 13, 2021
Read more from YM Chen
Published on HackMD