2021q1 Homework1 (lab0)

contributed by < XDEv11 >

GitHub
lab0

queue.[ch] 實作

queue_t 結構定義

為了能實作出 O(1) 的 q_size 與 q_insert_tail，這邊直接紀錄佇列的大小與尾端。
並且定義常數 QUEUE_STRLEN_MAX 來限制字串最大長度，方便後面使用 *n* 的函式，避免 <string.h> 中某些不安全的函式。
CERN Common vulnerabilities guide for C programmers。

#define QUEUE_STRLEN_MAX 255
typedef struct {
    list_ele_t *head; /* Linked list of elements */
	
    int size;
    list_ele_t **tail;
} queue_t;

tail 是指標的指標，指向 head

或是尾端節點的 next。

因此要在尾端放入新節點，只需要指定新節點的指標到 *tail 即可。

例外處理

若傳入參數為 NULL 佇列，則依據函式要求做特殊處理。(e.g., No effect or Return false)

q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q) {
        q->head = NULL;
        q->size = 0;
        q->tail = &(q->head);
    }
    return q;
}

q_free

void q_free(queue_t *q)
{
    if (!q)
        return;
    while (q->head) {
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

輔助函數

這邊先寫一個輔助函數，建立新的節點，並把 s 中的字串複製過去。這邊使用 *n* 的函式，避免造成緩衝區溢位 (buffer overflow) 的問題。

static inline list_ele_t *ele_new(char *s)
{
    if (!s)
        return NULL;
    list_ele_t *newe = malloc(sizeof(list_ele_t));
    if (!newe)
        return NULL;
    size_t slen = strnlen(s, QUEUE_STRLEN_MAX);
    char *news = malloc((slen + 1) * sizeof(char));
    if (!news) {
        free(newe);
        return NULL;
    }
    strncpy(news, s, slen);
    news[slen] = '\0';
    newe->value = news;
    return newe;
}

q_insert_head

對空佇列加入元素時，由上圖例可知，需要特別去修改 q->tail。

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh = ele_new(s);
    if (!newh)
        return false;
    newh->next = q->head;
    if (!q->head)
        q->tail = &(newh->next);
    q->head = newh;
    q->size += 1;
    return true;
}

q_insert_tail

q->tail 改為指向新元素的 next。

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newt = ele_new(s);
    if (!newt)
        return false;
    newt->next = NULL;
    *(q->tail) = newt;
    q->tail = &(newt->next);
    q->size += 1;
    return true;
}

q_remove_head

這邊一樣使用 *n* 的函式來進行字串複製。

跟 q_insert_head 一樣需要注意的是，當它變為空佇列時，需要特別去修改 q->tail。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;
    if (sp && bufsize) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    if (!q->head)
        q->tail = &(q->head);
    q->size -= 1;
    free(tmp->value);
    free(tmp);
    return true;
}

q_size

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

q_reverse

逐步地把每個元素加入 newh 的前端即可，最後要先把 q->tail 指向 q->head (即新的尾端) 的 next。

void q_reverse(queue_t *q)
{
    if (!q || !q->head)
        return;
    list_ele_t *newh = NULL;
    list_ele_t *p = q->head;
    while (p) {
        list_ele_t *tmp = p;
        p = p->next;
        tmp->next = newh;
        newh = tmp;
    }
    q->tail = &(q->head->next);
    q->head = newh;
}

q_sort

這邊使用 merge sort 演算法來實作 q_sort，時間複雜度是

$\theta (n\log n$)，較為穩定。

這邊的 strcmp 就沒有使用 *n* 的函式，因為在程式中可以確保節點裡面的字串會是 null-terminated。

static list_ele_t *merge(list_ele_t *p1, list_ele_t *p2)
{
    if (!p1 && !p2)
        return NULL;
    else if (!p1)
        return p2;
    else if (!p2)
        return p1;

    list_ele_t *res = NULL, **pp = &res;
    while (p1 || p2) {
        if (!p2 || (p1 && strcmp(p1->value, p2->value) <= 0)) {
            *pp = p1;
            p1 = p1->next;
        } else {
            *pp = p2;
            p2 = p2->next;
        }
        pp = &((*pp)->next);
    }
    return res;
}

透過 mid 每次移動一步以及 tail 每次移動二步來尋找鏈結串列的中心， mid 及 tail 皆為指標的指標，不過這邊的意義比較不同，代表的位置不是指向的節點 (*mid / *tail)，而是當指向某個節點的 next (或是 head)，實際上就是代表在那個節點 (或是在 head)，因此 tail 可以透過 *tail 判斷是否有下一個節點，也就是是否到達尾端。

一開始 mid 跟 tail 都在 head 上，

移動二次後，

可以看到此時 mid 剛好在前半部的尾端，指標的指標在這裡除了可以得到後半部的前端 (*mid)，也是為了方便把二部分分開 (*mid = NULL;)。

merge_sort 的參數 list 也使用指標的指標，直接修改真正的指標，一方面因為經過排序後，舊的指標沒有什麼代表意義及用途，另一方面也避免新的指標未被記錄而造成記憶體流失 (Memory leak)。

static void merge_sort(list_ele_t **pp)
{
    if (!(*list) || !(*list)->next)
        return;
    // Split into two halves
    list_ele_t **mid = list, **tail = list;
    while (*tail) {
        tail = &((*tail)->next);  // Move tail twice
        if (*tail)
            tail = &((*tail)->next);
        mid = &((*mid)->next);  // Move mid once
    }
    list_ele_t *L = *list, *R = *mid;
    *mid = NULL;

    merge_sort(&L);
    merge_sort(&R);
    *list = merge(L, R);
}

呼叫 merge_sort 進行排序後，需重新找一次尾端節點，並把 q->tail 指向它的 next。

void q_sort(queue_t *q)
{
    if (!q)
        return;

    merge_sort(&(q->head));
    q->tail = &(q->head);
    while (*(q->tail))
        q->tail = &((*(q->tail))->next);
}

SANITIZER

透過 $ make SANITIZER=1 開啟 Address Sanitizer 後，
執行 $ make test，得到以下錯誤，

==1968==ERROR: AddressSanitizer: global-buffer-overflow on address 0x561845b335e0 at pc 0x561845b1bb08 bp 0x7ffd6eb9cc40 sp 0x7ffd6eb9cc30
READ of size 4 at 0x561845b335e0 thread T0
    #0 0x561845b1bb07 in do_option_cmd /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:369
    #1 0x561845b1a8f0 in interpret_cmda /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:221
    #2 0x561845b1b0d5 in interpret_cmd /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:244
    #3 0x561845b1c301 in cmd_select /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:594
    #4 0x561845b1c87b in run_console /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:667
    #5 0x561845b19405 in main /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/qtest.c:780
    #6 0x7f386810c0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #7 0x561845b16bad in _start (/mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/qtest+0x8bad)

0x561845b335e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x561845b335e0) of size 1
  'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:369 in do_option_cmd

執行 qtest 再於命令提示列輸入 help 命令，得到以下錯誤，

==1954==ERROR: AddressSanitizer: global-buffer-overflow on address 0x56493755b3c0 at pc 0x5649375447dd bp 0x7ffded617170 sp 0x7ffded617160
READ of size 4 at 0x56493755b3c0 thread T0
    #0 0x5649375447dc in do_help_cmd /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:307
    #1 0x5649375448f0 in interpret_cmda /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:221
    #2 0x5649375450d5 in interpret_cmd /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:244
    #3 0x564937546818 in run_console /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:660
    #4 0x564937543405 in main /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/qtest.c:780
    #5 0x7fd4c631e0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x564937540bad in _start (/mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/qtest+0x8bad)

0x56493755b3c1 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x56493755b3c0) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /mnt/e/SF/Linux_Kernel_Internals/homework1/lab0-c/console.c:307 in do_help_cmd

可以看到程式在 console.c:369 以及 console.c:307 出問題，程式碼如下，

int oldval = *plist->valp;

report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
    plist->documentation);

可以發現都與 plist 有關，型態是 param_ptr，到 console.h 中可找到相關型態定義，

/* Integer-valued parameters */
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;
};

而錯誤訊息中也發現是跟 simulation 以及 echo 二個變數有關，來看看 console.c 中相關的部分。

bool simulation = false;

static bool echo = 0;

add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",
          NULL);

add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);

那再來看看 add_param 到底在幹嗎？

/* Add a new parameter */
void add_param(char *name,
               int *valp,
               char *documentation,
               setter_function setter)
{
    param_ptr next_param = param_list;
    param_ptr *last_loc = &param_list;
    while (next_param && strcmp(name, 412 next_param->name) > 0) {
        last_loc = &next_param->next;
        next_param = next_param->next;
    }

    param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
    ele->name = name;
    ele->valp = valp;
    ele->documentation = documentation;
    ele->setter = setter;
    ele->next = next_param;
    *last_loc = ele;
}

原來它就是在 param_list 的尾端加入一個新的參數，但是 valp 的型態為 int *，而呼叫時被直接轉型，導致後續透過 int 的指標 dereference 時發生記憶體錯誤。

為了不改變其它結構定義與函數原型，最簡單的解決辦法就是把二個 bool 變數改為 int 型態。

VALGRIND

執行 $ make valgrind，會得到以下訊息。

---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==3151== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==3151==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3151==    by 0x4A4A50E: strdup (strdup.c:42)
==3151==    by 0x110092: linenoiseHistoryAdd (linenoise.c:1236)
==3151==    by 0x110C25: linenoiseHistoryLoad (linenoise.c:1325)
==3151==    by 0x10C24C: main (qtest.c:769)
==3151==
==3151== 5 bytes in 1 blocks are still reachable in loss record 2 of 3
==3151==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3151==    by 0x4A4A50E: strdup (strdup.c:42)
==3151==    by 0x110006: linenoiseHistoryAdd (linenoise.c:1236)
==3151==    by 0x110C25: linenoiseHistoryLoad (linenoise.c:1325)
==3151==    by 0x10C24C: main (qtest.c:769)
==3151==
==3151== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==3151==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==3151==    by 0x110052: linenoiseHistoryAdd (linenoise.c:1224)
==3151==    by 0x110C25: linenoiseHistoryLoad (linenoise.c:1325)
==3151==    by 0x10C24C: main (qtest.c:769)
==3151==
---     trace-01-ops    6/6
---     TOTAL           6/6

qtest.c:769 呼叫 linenoiseHistoryLoad()，又會呼叫 linenoiseHistoryAdd()，在 linenoise.c:1224 附近可以看到以下的程式碼，

/* 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));
}

配置了記憶體給 history。

而在 linenoise.h 中，我們可以看到 freeHistory() 這個函式， linenoise.c 中的程式碼如下，

/* ================================ History ================================= */

/* Free the history, but does not reset it. Only used when we have to
 * exit() to avoid memory leaks are reported by valgrind & co. */
static void freeHistory(void)
{
    if (history) {
        int j;

        for (j = 0; j < history_len; j++)
            free(history[j]);
        free(history);
    }
}

可以得知應透過這個函式來釋放 history 的記憶體。

先看一下 freeHistory() 會在哪邊被呼叫，追蹤過程中可以看到 atexit()。

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

在 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. */
            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;
}

只有 Raw mode 的時候會呼叫到 linenoise()，也只有這時候需要用到 history 的相關函式，因此把 qtest.c:769 附近程式碼改成，

if (!infile_name) {
	linenoiseHistorySetMaxLen(HISTORY_LEN);
	linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
}

即可解決問題。

tags: linux2021