2022q1 Homework1 (lab0)

contributed by < jackhong12 >

作業要求

實驗環境

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

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   43 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      23
Model:                           17
Model name:                      AMD Ryzen 5 2400G with Radeon Vega Graphics
Stepping:                        0
Frequency boost:                 enabled
CPU MHz:                         285.818
CPU max MHz:                     3600.0000
CPU min MHz:                     1600.0000
BogoMIPS:                        7186.57
Virtualization:                  AMD-V
L1d cache:                       128 KiB
L1i cache:                       256 KiB
L2 cache:                        2 MiB
L3 cache:                        4 MiB
NUMA node0 CPU(s):               0-7

修改 queue.c

q_new

Create empty queue. Return NULL if could not allocate space.

透過 INIT_LIST_HEAD 初始 list_head 中的 prev 和 next 指標。

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (!q)
        return NULL;
    INIT_LIST_HEAD(q);
    return q;
}

q_free

Free all storage used by queue

因為要刪除 list 中的節點,所以要使用 safe 版本的 macro list_for_each_entry_safe

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *ptr, *safe;
    list_for_each_entry_safe (ptr, safe, l, list) {
        free(ptr->value);
        free(ptr);
    }
    free(l);
}

q_insert_head

Attempt to insert element at head of queue.

透過 list_add 在 queue 的開頭插入新的節點。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;

    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }

    list_add(&e->list, head);
    return true;
}

q_insert_tail

Attempt to insert element at tail of queue.

透過 list_add_tail 在 queue 的結尾插入節點。

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;

    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }

    list_add_tail(&e->list, head);
    return true;
}

q_remove_head

Attempt to remove element from head of queue.

利用 list_del_init 移除節點,接著透過 list_entry 取得 element_t 的指標。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *ptr = head->next;
    list_del_init(ptr);
    element_t *e = list_entry(ptr, element_t, list);
    if (sp && bufsize > 0) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return e;
}

q_remove_tail

Attempt to remove element from tail of queue.

利用 list_del_init 移除節點,接著透過 list_entry 取得 element_t 的指標。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *ptr = head->prev;
    list_del_init(ptr);
    element_t *e = list_entry(ptr, element_t, list);
    if (sp && bufsize > 0) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return e;
}

q_size

Return number of elements in queue.

利用 list_for_each 遍尋所有的節點來計算點的數量。

int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    struct list_head *ptr;
    int num = 0;
    list_for_each (ptr, head)
        num++;
    return num;
}

q_delete_mid

Delete the middle node in list.

透過快慢指標取得中間節點的指標,在利用 list_del 將節點從 queue 中移除。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

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

    list_del(slow);
    element_t *e = list_entry(slow, element_t, list);
    free(e->value);
    free(e);
    return true;
}

q_delete_dup

Delete all nodes that have duplicate string, leaving only distinct strings from the original list.

先計算相同值得起點和結束,最後在一個迴圈將所有資源釋放。

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    for (struct list_head *ptr = head->next; ptr != head;) {
        struct list_head *start = ptr;
        char *start_value = list_entry(start, element_t, list)->value;

        for (ptr = ptr->next;
             ptr != head &&
             !strcmp(start_value, list_entry(ptr, element_t, list)->value);)
            ptr = ptr->next;

        for (struct list_head *safe = start->next; start != ptr;
             start = safe, safe = start->next) {
            list_del(start);
            element_t *e = list_entry(start, element_t, list);
            free(e->value);
            free(e);
        }
    }
    return true;
}

q_swap

Attempt to swap every two adjacent nodes.

odd 指標指向基數節點,even 指標指向偶數節點,每次迴圈都將兩個指標對調。

void q_swap(struct list_head *head)
{
    for (struct list_head *odd = head->next, *even = odd->next;
         odd != head && even != head;) {
        struct list_head *prev = odd->prev;
        struct list_head *next = even->next;
        prev->next = even;
        even->prev = prev;
        even->next = odd;
        odd->prev = even;
        odd->next = next;
        next->prev = odd;

        odd = next;
        even = odd->next;
    }
}

q_reverse

Reverse elements in queue.

透過 LIST_HEAD 產生一個暫時的 queue 存放所有節點,在將所有節點反向加入原本的 queue 中。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    LIST_HEAD(tmp);
    list_splice(head, &tmp);
    INIT_LIST_HEAD(head);

    while (!list_empty(&tmp)) {
        struct list_head *ptr = tmp.next;
        list_del_init(ptr);
        list_add(ptr, head);
    }
}

q_sort

Sort elements of queue in ascending order.

下方是用來比較字串大小的 function。

bool cmp(char *str1, char *str2)
{
    for (; *str1 && *str2; str1++, str2++) {
        if (*str1 < *str2)
            return true;
        else if (*str1 > *str2)
            return false;
    }
    if (*str1)
        return false;
    return true;
}

q_sort 的部份我是實作 merge sort。
merge_sort 會將原本的 queue 分成兩個 queue 並呼叫下一層的 merge_sort,當 queue 只有一個節點時為遞迴的中止條件。

void merge_sort(struct list_head *head)
{
    if (list_is_singular(head))
        return;

    struct list_head *mid = head->next;
    for (struct list_head *fast = mid;
         fast->next != head && fast->next->next != head;
         fast = fast->next->next) {
        mid = mid->next;
    }

    LIST_HEAD(tmp);
    list_cut_position(&tmp, mid, head->prev);
    merge_sort(head);
    merge_sort(&tmp);
    merge(head, &tmp);
}

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

merge 的部份,我先用一個暫時的 queue tmp 儲存排序後的節點,最後在將 tmp 的內容移到 queue l1。

void merge(struct list_head *l1, struct list_head *l2)
{
    LIST_HEAD(tmp);
    while (!list_empty(l1) && !list_empty(l2)) {
        element_t *e1 = list_entry(l1->next, element_t, list);
        element_t *e2 = list_entry(l2->next, element_t, list);
        struct list_head *ptr;
        if (cmp(e1->value, e2->value))
            ptr = l1->next;
        else
            ptr = l2->next;
        list_del(ptr);
        list_add_tail(ptr, &tmp);
    }

    while (!list_empty(l1)) {
        struct list_head *ptr = l1->next;
        list_del(ptr);
        list_add_tail(ptr, &tmp);
    }

    while (!list_empty(l2)) {
        struct list_head *ptr = l2->next;
        list_del(ptr);
        list_add_tail(ptr, &tmp);
    }
    list_splice(&tmp, l1);
}

trace-17-complexity

第 17 筆測資在實驗室的電腦和 Github Action 上的可以跑過,但不知道為什麼在我自己的電腦中有高機率會失敗,每次失敗的項目可能不同,有可能第一次是 q_insert_tail,下一次換成 q_insert_head,之後在研究看看是什麼原因造成的。

實作 Fisher–Yates shuffle 演算法

在 qtest.c 中加入 shuffle command。

    ADD_COMMAND(shuffle, "                | Shuffle the nodes in the queue");
static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();

    show_queue(3);
    return !error_check();
}

我用另一個 result queue 先紀錄隨機選出的節點,最後在將結果放回 head 中。

static void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    LIST_HEAD(result);

    for (int len = q_size(head); len > 0; len--) {
        int random = rand() % len + 1;
        struct list_head *ptr = head;
        for (int i = 0; i < random; i++)
            ptr = ptr->next;

        struct list_head *tail = head->prev;
        list_del(tail);
        if (ptr != tail) {
            tail->next = ptr->next;
            ptr->next->prev = tail;
            tail->prev = ptr->prev;
            ptr->prev->next = tail;
        }
        list_add_tail(ptr, &result);
    }
    list_splice(&result, head);
}

開啟 Address Sanitizer,修正 qtest 執行過程中的錯誤

valgrind 錯誤訊息

當執行 make valgrind 會頻繁出現以下錯誤訊息,推測是 strdup allocate 的記憶體在程式結束前沒有被釋放。

==2215669== 119 bytes in 20 blocks are still reachable in loss record 1 of 2                   
==2215669==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2215669==    by 0x4A6950E: strdup (strdup.c:42)                          
==2215669==    by 0x113FF1: linenoiseHistoryAdd (linenoise.c:1236)                             
==2215669==    by 0x114350: linenoiseHistoryLoad (linenoise.c:1325)
==2215669==    by 0x10CF4B: main (qtest.c:993) 

linenoise.c 中有對應一段程式碼在釋放 history。

static void freeHistory(void)
{
    if (history) {
        int j;

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

用 gdb 設段點在 freeHistory 上,發現其實 freeHistory 有被執行。

(gdb) bt
#0  freeHistory () at linenoise.c:1191
#1  0x000055555555ff19 in linenoiseAtExit () at linenoise.c:1205
#2  0x00007ffff7ca1a27 in __run_exit_handlers (status=0, 
    listp=0x7ffff7e43718 <__exit_funcs>, run_list_atexit=run_list_atexit@entry=true, 
    run_dtors=run_dtors@entry=true) at exit.c:108
#3  0x00007ffff7ca1be0 in __GI_exit (status=<optimized out>) at exit.c:139
#4  0x00007ffff7c7f0ba in __libc_start_main (main=0x555555558ce8 <main>, argc=1, 
    argv=0x7fffffffdb08, init=<optimized out>, fini=<optimized out>, 
    rtld_fini=<optimized out>, stack_end=0x7fffffffdaf8) at ../csu/libc-start.c:342
#5  0x00005555555568ce in _start ()

在 enableRawMode 這個函釋中有透過 atexit 註冊 linenoiseAtExit,當程式結束前會執行 linenoiseAtExit 清除 history。

atexit(linenoiseAtExit);

但查看 run_console 後發現有分成兩種情況,一種是有輸入檔案,另一種沒有沒有輸入檔案,其中沒有輸入檔案的狀況才會呼叫到 enableRawMode。

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

在使用 gdb 設段點在 freeHistory 上,並指定輸入檔案 traces/trace-01-ops.cmd,但這次並不會執行到 freeHistory。

$ gdb -ex 'handle SIGALRM ignore' -ex 'b freeHistory' -ex 'run -f traces/trace-01-ops.cmd' ./qtest./qtest

所以只要在有在 cmd_select 前用 atexit 註冊 linenoiseAtExit 並能正常執行。

    } else {
        registerLinenoiseAtExit();
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }
void registerLinenoiseAtExit(void)
{
    atexit(linenoiseAtExit);
}

提供 web 伺服器功能

Select a repo