Try   HackMD

2021q1 Homework1 (lab0)

contributed by < akamayu-ouo >

Environment

$ uname -a
Linux ... 5.10.15-1-MANJARO #1 SMP PREEMPT Wed Feb 10 10:42:47 UTC 2021 x86_64 GNU/Linux
$ gcc --version | head -1
gcc (GCC) 10.2.0
$ valgrind --version
valgrind-3.16.1

Overview

  • C programming lab
  • Fix qtest
  • Use Massif to visualize "simulation"
  • Add coroutine into qtest
  • Explain the use of "select" in this program
  • Explain how linenoise works
  • Read the paper
  • Find defect in the system, then try to fix it

C Programming Lab

Memory management

將記憶體管理集中以減少重複的程式碼，出錯時也容易檢查。在這份作業中 queue_t 以及 list_ele_t 都需要動態配置記憶體，前者的記憶體管理由 q_new 和 q_free 兩個函式負責；後者由我自己增加的兩個函式負責。分別是：

  1. list_ele_t *new_element(char *, list_ele_t *):
    配置記憶體並初始化新的 list_ele_t* ，若輸入的字串為 NULL 或有其他錯誤，都輸出 NULL。











inline static list_ele_t *new_element(char *s, list_ele_t *next)
{
    list_ele_t *new_ele = NULL;
    if (!s || !(new_ele = malloc(sizeof(list_ele_t))) 
           || !(new_ele->value = strdup(s)))
        free(new_ele);
        return NULL;
    }
    new_ele->next = next;
    return new_ele;
}
  1. list_ele_t *del_element(list_ele_t *e):
    釋放 e 與 e->value 的記憶體，回傳 e->next 以方便使用。這個函式假設輸入不會是 NULL







inline static list_ele_t *del_element(list_ele_t *e)
{
    list_ele_t *next = e->next;
    free(e->value);
    free(e);
    return next;
}

值得注意的是根據 free(3)

The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc(), or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior occurs. If ptr is NULL, no operation is performed.

free 在輸入為 NULL 時不會出問題，因此不做檢查。

queue_t structure

增加兩個變數： size 與 tail

struct {
    size_t size;
    list_ele_t *head;
    list_ele_t **tail;
} queue_t;

動態地更新 size 與 tail 以達成常數時間的 q_size 以及 q_insert_tail。

q_new 與 q_free

q_new 只有在配置記憶體成功的時候初始化內容。q_free 則從 head 開始依序使用 del_element 返還記憶體，最後再釋放佇列本身的空間。

Element Insertion

定義一個 static 函數來簡化實做。參數 link 指向「要新增元素的記憶體位置」。

  • 備份 *link
  • 嘗試取得新的元素
    • 失敗：恢復 *link 並回傳 false
    • 成功：更新佇列大小與 tail，回傳 true












inline static bool insert_at(queue_t *q, list_ele_t **link, char *s)
{
    list_ele_t *orig = *link;
    if (!(*link = new_element(s, orig))) {
        *link = orig;
        return false;
    }
    ++q->size;
    if (*q->tail)
        q->tail = &(*q->tail)->next;
    return true;
}

如此一來， q_insert_head 與 q_insert_tail 都能簡化成一行









bool q_insert_head(queue_t *q, char *s)
{
    return q && insert_at(q, &q->head, s);
}
bool q_insert_tail(queue_t *q, char *s)
{
    return q && insert_at(q, q->tail, s);
}

Element Removal

q_remove_head 將佇列的第一個元素去除，並交由 del_element 釋放其空間。並在 sp 不為 NULL 的時候將元素中的字串複製過去。

這邊有個地方不是很清楚，當 sp 不為 NULL 但元素字串是 NULL 時應該將 sp 更新為 NULL 、空字串 \0 抑或是完全不動它呢？還是我們能保證字串一定存在？但插入函式也都沒有定義字串不存在時的行為？

我目前的想法是：只要我保證佇列的 API 不會產生沒有字串的 list_ele_t ，那遇到這個情形就一定是使用者亂搞，什麼都不動就好。

附上原始的註解如下：

If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.














bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (0 == q_size(q))
        return false;
    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    q->head = del_element(q->head);
    if (--q->size <= 1)
        q->tail = (q->head) ? &q->head->next : &q->head;
    return true;
}

Queue size

可以利用 q_size(q)<n 將「佇列不存在」與「佇列長度小於 n 」的檢查合而為一，讓 edge cases 的處理更加簡潔。

Reverse

先將 linked list 反轉，再更新 head 與 tail。

Sort

基本上使用 merge sort 實做（一開始嘗試用 quick sort 硬幹，但忘記它最差情況會需要花

O(n2) 的時間，測試直接爆掉）。主要分為三個步驟：

  1. 將 linked list 分為兩段
    使用類似 龜兔賽跑 的方法，從 head 出發，當兔子跑過整條 linked list 的時候烏龜會停在 linked list 中央。
  2. 分別進行排序（遞迴呼叫）
  3. 將兩段排序好的 linked list 合成一條

實做中另外定義了一個 struct range_t





struct {
    list_ele_t* head;
    list_ele_t** tail;
} range_t;

這樣在傳遞參數的時候比較簡潔，程式碼也比較整齊。




















































inline static bool too_close(list_ele_t *const head,
                             list_ele_t *const *const tail)
{
    /* Order matters, the first clause ensures `head` 
     * would not be NULL */
    return head == *tail || &head->next == tail;
}

inline static range_t split(list_ele_t *const head,
                            list_ele_t *const *const tail)
{
    list_ele_t *slow = head;
    for (list_ele_t *fast = head->next; !too_close(fast, tail);) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return (range_t){.head = slow->next, .tail = &slow->next};
}

inline static range_t merge(range_t r1, range_t r2)
{
    list_ele_t *merged = NULL, **tail = NULL;
    for (tail = &merged; r1.head && r2.head; tail = &((*tail)->next)) {
        list_ele_t **source =
            (cmp_elem(r1.head, r2.head) < 0) ? (&r1.head) : (&r2.head);
        *tail = *source;
        *source = (*source)->next;
    }
    range_t *result = r1.head ? &r1 : &r2;
    *tail = result->head;
    result->head = merged;
    return *result;
}

static range_t merge_sort(list_ele_t *head, list_ele_t **tail)
{
    if (too_close(head, tail))
        return (range_t){.head = head, .tail = tail};
    range_t slit = split(head, tail);
    *slit.tail = *tail = NULL;
    return merge(merge_sort(head, slit.tail), merge_sort(slit.head, tail));
}

void q_sort(queue_t *q)
{
    if (q_size(q) <= 1)
        return;
    range_t range = merge_sort(q->head, q->tail);
    q->head = range.head;
    q->tail = range.tail;
}

Fix qtest

Sanitizer

問題敘述

用 make SANITIZER=1 編譯 qtest 。再於 qtest 中執行 help 得到了以下的錯誤：















































=================================================================
==4193211==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5590791906c0 at pc 0x55907917a112 bp 0x7ffeb4778e10 sp 0x7ffeb4778e00
READ of size 4 at 0x5590791906c0 thread T0
    #0 0x55907917a111 in do_help_cmd /.../sysprog21/Week1/lab0-c/console.c:306
    #1 0x55907917a225 in interpret_cmda /.../sysprog21/Week1/lab0-c/console.c:220
    #2 0x55907917a9f3 in interpret_cmd /.../sysprog21/Week1/lab0-c/console.c:243
    #3 0x55907917c0ca in run_console /.../sysprog21/Week1/lab0-c/console.c:659
    #4 0x559079178da3 in main /.../sysprog21/Week1/lab0-c/qtest.c:783
    #5 0x7f8a969a1b24 in __libc_start_main (/usr/lib/libc.so.6+0x27b24)
    #6 0x5590791765ed in _start (/.../sysprog21/Week1/lab0-c/qtest+0x85ed)

0x5590791906c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x5590791906c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /.../sysprog21/Week1/lab0-c/console.c:306 in do_help_cmd
Shadow bytes around the buggy address:
  0x0ab28f22a080: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
  0x0ab28f22a090: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x0ab28f22a0a0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
  0x0ab28f22a0b0: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x0ab28f22a0c0: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ab28f22a0d0: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
  0x0ab28f22a0e0: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x0ab28f22a0f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab28f22a100: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab28f22a110: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab28f22a120: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==4193211==ABORTING

從輸出第四行可知錯誤發生在 console.c 的第 306 行，並且是錯誤地存取了在 echo 這個變數的附近的地址。






while (plist) {
    report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
           plist->documentation);
    plist = plist->next;
}

變數 echo 宣告在第 59 行。

static bool echo = 0;

檢查程式碼，發現在 init_cmd 中 bool* 被轉成 int* ，造成之後在印出時被當作 int 讀取，讀到沒有配置的空間。

void init_cmd()
{
    ...
    add_param("simulation", (int *) &simulation, "Start/Stop simulation mode", NULL);
    add_param("verbose", &verblevel, "Verbosity level", NULL);
    add_param("error", &err_limit, "Number of errors until exit", NULL);
    add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
    ...
}

會需要轉成 int* 的原因推測是因為 PELE 中的 valp 是整數指標。

typedef struct PELE param_ele, *param_ptr;
struct PELE {
    char *name;
    int *valp;
    char *documentation;
    /* Function that gets called whenever parameter changes */
    setter_function setter;
    param_ptr next;
};

解決方法

除了 echo 以外，還有一個變數 simulation 也有同樣的情況。將它們都改宣告為 int ，並移除型別轉換就好了。

然而這顯現了另一個問題，若將上述的兩個變數設定成其他整數，程式也不會出錯。但既然是「開關」行為的變數，值域應該只有 0 與 1。要解決這個問題，可以在 parse 命令的時候檢查，也可以對有 bool 數值的選項另外增加 struct，但這兩個選項都會需要更動很多地方。

Valgrind

問題敘述

測試後發現當 .cmd_history 有東西的時候使用 qtest -f <FILENAME> 會出現 memory leak 。

$ cat .cmd_history
quit
$ cat dummy_input
$ valgrind ./qtest -f dummy_input
Freeing queue
==4063868== 5 bytes in 1 blocks are still reachable in loss record 1 of 2
==4063868==    at 0x483E77F: malloc (vg_replace_malloc.c:307)
==4063868==    by 0x4A4A5FE: strdup (in /usr/lib/libc-2.33.so)
==4063868==    by 0x10F992: linenoiseHistoryAdd (linenoise.c:1240)
==4063868==    by 0x110488: linenoiseHistoryLoad (linenoise.c:1329)
==4063868==    by 0x10BD9A: main (qtest.c:770)
==4063868==
==4063868== 160 bytes in 1 blocks are still reachable in loss record 2 of 2
==4063868==    at 0x483E77F: malloc (vg_replace_malloc.c:307)
==4063868==    by 0x10F952: linenoiseHistoryAdd (linenoise.c:1228)
==4063868==    by 0x110488: linenoiseHistoryLoad (linenoise.c:1329)
==4063868==    by 0x10BD9A: main (qtest.c:770)
==4063868==

錯誤發生原因

從錯誤訊息推測是 history 沒有被釋放。也能發現出問題的記憶體是由 linenoiseHistoryAdd 配置。

有可能會釋放 history 的函式只有 linenoise.c 中的 freeHistory 以及前文提到的 linenoiseHistorySetMaxLen 。後者只有在 history 不為 NULL 時會重新配置記憶體，而它在主程式中被呼叫時 history 還未被初始化，因此它並不會對記憶體進行操作，僅僅是更新 history_max_len 而已。因此只有可能是 freeHistory 沒有被呼叫造成錯誤。














ine linenoiseHistorySetMaxLen(int len) 
{
    char **new;
    ...
    if(history) {
        ...
        new = malloc(sizeof(char *) * len);
        ...
        free(history);
        history = new;
    }
    ...
}







%0


cluster1

linenoise.c


cluster2

console.c


cluster3

main.c



freeHistory

freeHistory



linenoiseAtExit

linenoiseAtExit



freeHistory->linenoiseAtExit





enableRawMode

enableRawMode



linenoiseAtExit->enableRawMode





linenoiseRaw

linenoiseRaw



enableRawMode:e->linenoiseRaw:w





linenoisePrintKeyCodes

linenoisePrintKeyCodes



enableRawMode:e->linenoisePrintKeyCodes:w





linenoise

linenoise



linenoiseRaw:e->linenoise:w





run_console

run_console



linenoise->run_console





main

main



run_console->main:w

上圖是有機會執行到 freeHistory 的函式的函式 ，橢圓形表示該函式是 static 函式。

其中函式 enableRawMode 將 linenoiseAtExit 交給 atexit 註冊

if(!atexit_registered) {
    atexit(linenoiseAtExit);
    atexit_registered = 1;
}

根據 man page ，經由 atexit 註冊的函式會在主程式正常結束時被呼叫。

The atexit() function registers the given function to be called at normal process termination, either via exit(3) or via return from the program's main(). Functions so registered are called in the reverse order of their registration; no arguments are passed.

換句話說，若要將 history 釋放掉，程式執行期間至少要呼叫 enableRawMode 一次。否則 linenoiseAtExit 不會被註冊，主程式結束時也不會將空間歸還，造成 memory leak。

因為 enableRawMode 只有透過 linenoisePrintKeyCodes 或 linenoise 才能呼叫到，但前者沒有在任何地方被呼叫，後者只被 run_console 呼叫。然而run_console 只在沒有輸入檔案時會呼叫到 linenoise。

bool run_console(char *infile_name)
{
    ...
    if (!has_infile) {
        char *cmdline;
        while ((cmdline = linenoise(prompt)) != NULL) {
            ...
        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }
    return err_cnt == 0;
}

驗證

以下是使用 gprof 紀錄到被呼叫的函式名稱（輸入內容都是 ./trace-13-perf.cmd）。

  • 以檔案輸入: $ ./qtest -f <FILENAME>
  [25] add_cmd                [41] finish_cmd             [49] q_free
  [30] add_param              [29] free_array             [11] q_insert_head
  [36] add_quit_helper        [20] free_block             [15] q_insert_tail
  [37] allocation_check       [22] free_string            [16] q_new
  [28] calloc_or_fail         [32] get_int                 [9] q_reverse
   [1] cmd_select             [42] init_cmd               [50] queue_quit
  [38] delta_time             [43] init_time              [31] report
  [39] do_comment_cmd          [2] interpret_cmd          [19] report_noreturn
   [8] do_insert_head          [3] interpret_cmda          [4] run_console
  [12] do_insert_tail         [24] linenoiseHistoryAdd    [34] set_cautious_mode
  [14] do_new                 [44] linenoiseHistoryLoad   [51] set_echo
  [33] do_option_cmd          [45] linenoiseHistorySetMaxLen [35] set_noallocate_mode
  [40] do_quit_cmd            [46] linenoiseSetCompletionCallback [52] set_verblevel
   [7] do_reverse             [21] malloc_or_fail          [6] show_queue
  [17] error_check            [10] new_element            [23] strsave_or_fail
  [26] exception_cancel       [47] pop_file               [18] test_free
  [27] exception_setup        [48] push_file              [13] test_malloc
  • 從 STDIN 輸入: $ cat <FILENAME> | ./qtest
  [24] add_cmd                [19] free_block             [51] q_free
  [32] add_param              [22] free_string            [10] q_insert_head
  [38] add_quit_helper        [34] get_int                [14] q_insert_tail
  [39] allocation_check       [44] init_cmd               [15] q_new
  [28] calloc_or_fail         [45] init_time               [7] q_reverse
  [40] delta_time              [1] interpret_cmd          [52] queue_quit
  [41] do_comment_cmd          [2] interpret_cmda         [33] report
   [8] do_insert_head         [27] linenoise              [18] report_noreturn
  [11] do_insert_tail         [30] linenoiseFree           [3] run_console
  [13] do_new                 [21] linenoiseHistoryAdd    [36] set_cautious_mode
  [35] do_option_cmd          [46] linenoiseHistoryLoad   [53] set_echo
  [42] do_quit_cmd            [31] linenoiseHistorySave   [37] set_noallocate_mode
   [5] do_reverse             [47] linenoiseHistorySetMaxLen [54] set_verblevel
  [16] error_check            [48] linenoiseSetCompletionCallback [6] show_queue
  [25] exception_cancel       [20] malloc_or_fail         [23] strsave_or_fail
  [26] exception_setup         [9] new_element            [17] test_free
  [43] finish_cmd             [49] pop_file               [12] test_malloc
  [29] free_array             [50] push_file

可以看到前者沒有呼叫到 linenoise。

解決方法

若讀檔作為輸入，那就沒有紀錄歷史的必要，也不需要自動補全命令。在 qtest.c 中不呼叫自動補全以及跟歷史紀錄有關的設定。只要不拿記憶體，就不會有忘記釋放的問題。












-    /* Trigger call back function(auto completion) */
-    linenoiseSetCompletionCallback(completion);
+    if (!infile_name) {
+        /* Trigger call back function(auto completion) */
+        linenoiseSetCompletionCallback(completion);
+        linenoiseHistorySetMaxLen(HISTORY_LEN);
+        linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
+    }

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

伴程（Coroutine）

TODO

解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點

我們先來看 select 的用途。根據 select(2) ， select 是用於等待 檔案描述符（File descriptor）可動作的函式。

select() allows a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation (e.g., read(2), or a sufficiently small write(2)) without blocking.

select() 能在時限（參數 timeout ）中等待「讀」、「寫」以及「例外」三組檔案描述符（分別為參數 readfds 、 writefds 與 exceptfds ），而變數 nfd 則是那三組描述符的數值上界。

當 select() 執行完成時，三組描述符中都只會剩下可動作的描述符（使用巨集 FD_ISSET 確認），回傳值則是總共可動作的描述符的數目。

console.c 中的 cmd_select() 是 select() 的 wrapper 。 它將 buf_stack 最上層的檔案描述符加入 readfds，再使用 select() 確認其是否準備好了。若該描述符已經可以被讀取，當下又是在讀取檔案的話，cmd_select 會直接讀取並執行命令。

而 readline() 顧名思義就是從檔案描述符中讀取命令的函式。其中使用到與 CS:APP RIO 套件相同的邏輯——每次使用核心函式取得一塊輸入，暫存在記憶體中，在用完前都在 user space 讀取，不夠再去跟核心要資料，達到減少呼叫核心函式的目的。
























static char *readline()
{
...
    for (cnt = 0; cnt < RIO_BUFSIZE - 2; cnt++) {
        /* 暫存的輸入都用完了 */
        if (buf_stack->cnt <= 0) {
            /* 使用核心函式 `read` 讀取輸入 */
            buf_stack->cnt = read(buf_stack->fd, buf_stack->buf, RIO_BUFSIZE);
            buf_stack->bufptr = buf_stack->buf;
...
        }

        /* 暫存區還有輸入 */
        c = *buf_stack->bufptr++;
        *lptr++ = c;
        buf_stack->cnt--;
        if (c == '\n')
            break;
    }
...
    return linebuf;
}

測試

使用 strace 來觀察程式呼叫核心函式的行為









$ wc --bytes ./traces/trace-13-perf.cmd
125 ./traces/trace-13-perf.cmd 
$ strace -e trace=read ./qtest -v 0 -f ./traces/trace-13-perf.cmd
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\200\272\0\0\0\0\0\0"..., 832) = 832
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\20\35\2\0\0\0\0\0"..., 832) = 832
read(3, "# Test performance of insert_tai"..., 8192) = 125
read(3, "", 8192)                       = 0
+++ exited with 0 +++

先忽略輸出的前兩行，可以看到共呼叫 read 兩次，第一次讀取了 125 個位元組，這與輸入檔案的大小相同。而 8192 則是暫存區大小（定義於 console.c 的第 39 行）。

前兩行的 read 是動態載入器（ dynamic loader ）在載入動態函式庫。









$ strace ./qtest -v 0 -f ./traces/trace-13-perf.cmd
...
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libm.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\200\272\0\0\0\0\0\0"..., 832) = 832
...
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\20\35\2\0\0\0\0\0"..., 832) = 832
...

其中 libm.so.6 是數學函式庫； libc.so.6 是 GNU 的 C 函式庫。檔案內容中的 ELF 來自「Executable and Linking Format」，是 Unix 與 類 Unix 系統的執行檔格式。

自製終端命令解譯器

TODO

參考資料

To Be Continued …

Last changed by 
 
akamayu-ouo
ハロ　ハワユ
0
560

Read more

2021q1 Homework1 (quiz1)

contributed by < akamayu-ouo > &#x7B2C;&#x4E00;&#x5468;&#x6E2C;&#x9A57;&#x984C; #define LLL left = &((*left)->next) #define AAA &right #define BBB &left #define CCC \ list_concat(&result, pivot); \ list_concat(&result, right)

Mar 1, 2021
Read more from akamayu-ouo
Published on HackMD