2021q1 Homework1 (lab0)

contributed by < tinyynoob >

作業說明

Quick Guide

• 2021q1 Homework1 (lab0)
  • Quick Guide
  • 開發環境
  • 實作流程
    • queue.h
    • queue.c
    • Address Sanitizer

開發環境

$ uname -a
Linux tinyynoob-home 5.11.0-43-generic #47~20.04.2-Ubuntu SMP Mon Dec 13 11:06:56 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

實作流程

進度	內容敘述
1	q_new()
1	q_free()
1	q_insert_head()
1	q_insert_tail()
1	q_remove_head()
1	q_size()
1	q_reverse()
1	q_sort()
0	開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
0	運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
0	在 qtest 中實作 coroutine，並提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
0	說明 antirez/linenoise 的運作原理，注意到 termios 的運用
0	研讀論文 Dude, is my code constant time?，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案
0	指出現有程式的缺陷 (提示: 和 RIO 套件 有關)，嘗試強化並提交 pull request

queue.h

• 加入指標變數 tail 幫助快速找到結尾以利 q_insert_tail() 實作。
• 為了能在
  $O(1)$ 時間內返回 queue 的大小，因此於 queue 的結構中加入一個 int 變數 size 防止每次都要遍歷 queue 求解。

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

queue.c

q_new()

配置空間後先檢查是否有成功配置，接著為結構成員進行初始化

• 將 head 及 tail 預設為 NULL 防止不當操作
• 將 size 預設為0

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

q_free()

從 head 指到的元素開始逐一將 queue 中的節點刪除，刪除時將節點內的字串及節點本身釋放。

before

after each step

void q_free(queue_t *q)
{
    while (q->head) {
        list_ele_t *temp = q->head;
        q->head = temp->next;
        free(temp->value);
        free(temp);
    }
    free(q);
}

由於在測試中遇到錯誤訊息

Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
中止 (核心已傾印)

因此在 while 之前加入以下兩行程式碼，避免 doubly free 的問題

if (!q)  // prevent doubly free
    return;

q_insert_head()

配置 list_ele_t 結構空間及字串空間，若配置失敗則立即跳離函式並回傳false；若順利配置則將新節點插入最前方，如果是唯一節點將需要設定 q 中的 tail 成員。

目前不知如何解決 strlen() 若讀不到 '\0' 的問題

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    int s_size = strlen(s) + 1;  // strlen() may not be safe if there is no '\0'
    char *s_in_ele = (char *) malloc(sizeof(char) * s_size);
    if (!s_in_ele) {
        free(newh);
        return false;
    }
    for (int i = 0; i < s_size; i++)  // copy the string including '/0'
        s_in_ele[i] = s[i];
    newh->value = s_in_ele;
    newh->next = q->head;
    q->head = newh;
    if (!q->tail)  // if newh is the only element
        q->tail = newh;
    q->size++;
    return true;
}

q_insert_tail()

作法與 q_insert_head() 類似，但注意到須將原先的尾節點接到新的尾節點，如下方程式碼第 18 行。

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newt = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newt)
        return false;
    int s_size = strlen(s) + 1;
    char *s_in_ele = (char *) malloc(sizeof(char) * s_size);
    if (!s_in_ele) {
        free(newt);
        return false;
    }
    for (int i = 0; i < s_size; i++)  // copy the string including '/0'
        s_in_ele[i] = s[i];
    newt->value = s_in_ele;
    newt->next = NULL;
    if (q->tail)
        q->tail->next = newt;
    q->tail = newt;
    if (!q->head)  // if newt is the only element
        q->head = newt;
    q->size++;
    return true;
}

q_remove_head()

先檢查 queue 是否為空，之後執行

1. 若 sp 為 non-NULL ，將目標節點內的字串複製至 sp
2. 將目標節點從 queue 中移除
3. 更新 q->size 及 q->head
4. 若移除節點後 queue 為空，將 tail 成員指向 NULL

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q)
        return false;
    else if (!q->size)
        return false;
    char *it = q->head->value;
    size_t sp_size = 0;
    while (!*it && sp_size < bufsize) {  // compute sp_size
        it++;
        sp_size++;
    }
    if (sp) {  // If sp is non-NULL
        sp = (char *) malloc(sizeof(char) * sp_size);
        if (!sp)
            return false;
        for (size_t i = 0; i < sp_size; i++)  // copy the removed string to sp
            sp[i] = q->head->value[i];
    }
    if (sp_size == bufsize)  // if the maximum is achieved
        sp[bufsize - 1] = '\0';
    free(q->head->value);
    list_ele_t *toDelete = q->head;
    q->head = q->head->next;
    free(toDelete);
    q->size--;
    if (!q->size)
        q->tail = NULL;
    return true;
}

我認為這裡題目的原意有些不清，原先誤以為需要為 sp 分配空間，理解後重新修改程式，並用更易理解的版本寫 sp 的部份，其中 min 函式使用 macro 完成。

不知道為何將下方程式第 5 行及第 6 行合併會發生錯誤

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->size)
        return false;
    size_t sp_size = min(strlen(q->head->value), bufsize - 1);
    sp_size = sp_size + 1;
    if (sp) {                                     // if sp is non-NULL
        for (size_t i = 0; i < sp_size - 1; i++)  // copy the string
            sp[i] = q->head->value[i];
        sp[sp_size - 1] = '\0';
    }
    free(q->head->value);
    list_ele_t *toDelete = q->head;
    q->head = q->head->next;
    free(toDelete);
    if (!q->head)
        q->tail = NULL;
    q->size--;
    return true;
}

q_size()

int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}

q_reverse()

使用三個 list_ele_t 指標一起向後遍歷整個 list 來完成反轉。
概念上等同於依序將節點 push 進一個新的 stack 。

void q_reverse(queue_t *q)
{
    if (!q || q->size == 0 || q->size == 1)
        return;
    q->tail = q->head;
    list_ele_t *prev = q->head;
    list_ele_t *temp = q->head->next->next;
    q->head = q->head->next;
    q->head->next = prev;
    while (temp) {
        prev = q->head;
        q->head = temp;
        temp = temp->next;
        q->head->next = prev;
    }
    q->tail->next = NULL;
}

q_sort()

第一個版本額外宣告了一組 array of pointers to elements 來幫助排序

void q_sort(queue_t *q)
{
    if (!q || !q->size)
        return;
    list_ele_t **array = (list_ele_t **) malloc(sizeof(list_ele_t *) *
                                                q->size);  // array of pointers
    list_ele_t *temp = q->head;
    for (int i = 0; i < q->size; i++) {
        array[i] = temp;
        temp = temp->next;
    }
    q_sort_recur(array, 0, q->size - 1, string_compare);

    /* relink the list with the result */
    for (int i = 0; i < q->size - 1; i++)
        array[i]->next = array[i + 1];
    q->head = array[0];
    q->tail = array[q->size - 1];
    free(array);
}

配合遞迴函式

void q_sort_recur(list_ele_t **array,
                  int left,
                  int right,
                  int (*cmp)(char *, char *))
{
    if (left >= right)
        return;
    /*choose array[right] as pivot*/
    list_ele_t *temp;
    int i = left;
    for (int j = left; j < right; j++) {
        if (cmp(array[j]->value, array[right]->value) < 0) {
            /* exchange array[i] and array[j] */
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            /* end exchange */
            i++;
        }
    }
    /* exchange array[i] and array[right] */
    temp = array[i];
    array[i] = array[right];
    array[right] = temp;
    /* end exchange */
    q_sort_recur(array, left, i - 1, cmp);
    q_sort_recur(array, i + 1, right, cmp);
}

在測試時發現題目並不允許使用 malloc() 。

後來我參考了 quiz 1 ，意識到在 quick sort 中，往下遞迴時元素的順序並不是很重要，只要求與 pivot 的相對大小。因此 linked list 就有天然的結構，完全不需要額外使用一組指標陣列。

於是重新寫出第二版本：

void q_sort(queue_t *q)
{
    if (!q || !q->size)
        return;
    q->head = sortList(q->head, strcmp);
    list_ele_t *it;
    for (it = q->head; it->next; it = it->next)
        ;
    q->tail = it;
}

同樣額外建構了一個方便遞迴的 quick sort 函式

list_ele_t *sortList(list_ele_t *head, int (*cmp)(const char *, const char *))
{
    if (!head || !head->next)
        return head;
    const char *pivot = head->value;
    list_ele_t *left = NULL, *right = NULL, *it = head->next;
    while (it) {
        list_ele_t *temp = it->next;
        push(cmp(it->value, pivot) > 0 ? &right : &left, it);
        it = temp;
    }
    left = sortList(left, cmp);
    right = sortList(right, cmp);

    if (left) {
        for (it = left; it->next; it = it->next)
            ;
        it->next = head;
    }
    head->next = right;
    return left ? left : head;
}

及

void inline push(list_ele_t **head, list_ele_t *newNode)
{
    newNode->next = *head;
    (*head) = newNode;
}

在這個過程中，我最有心得的是 ternary operator 跟 pointer to poiner 在 list 操作中的妙用。

然而，使用這個版本進行測試，會發現效率並不符合題目的要求。測試結果如下：

scripts/driver.py -c
---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
---     trace-05-ops    5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
---     trace-06-string 6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---     trace-07-robust 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---     trace-10-malloc 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---     trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---     trace-12-malloc 6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---     trace-13-perf   6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
---     trace-14-perf   6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
---     trace-15-perf   0/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Freed queue, but 19022 blocks are still allocated
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Freed queue, but 118568 blocks are still allocated
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
Error limit exceeded.  Stopping command execution
---     trace-16-perf   0/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---     TOTAL           88/100

因此，改以 merge sort 來實作 q_sort() ，以下為第三個版本：

void q_sort(queue_t *q)
{
    if (!q || !q->size)
        return;
    q->head = sortList(q->head, strcmp);
    list_ele_t *it;
    for (it = q->head; it->next; it = it->next)
        ;
    q->tail = it;
}

在 linked list 版本的 merge sort 中，需要將原 list 分割成為兩個 sublist 進行遞迴， truncate_and_findMid() 即為進行分割之函式。

list_ele_t *sortList(list_ele_t *head, int (*cmp)(const char *, const char *))
{
    if (!head || !head->next)
        return head;
    list_ele_t *mid = truncate_and_findMid(head);
    head = sortList(head, cmp);
    mid = sortList(mid, cmp);
    return mergeSorted(head, mid, cmp);
}

/* split the list and return a pointer to the mid element */
list_ele_t *truncate_and_findMid(list_ele_t *const head)
{
    /* the list should be guarantee to have at least 2 elements */
    list_ele_t *fast = head->next;
    list_ele_t *slow = head;
    list_ele_t *toTruncate = NULL;
    while (fast) {
        /* fast forwards 2 place and slow forwards 1 place each iteration */
        if (fast->next)
            fast = fast->next->next;
        else
            fast = fast->next;
        toTruncate = slow;
        slow = slow->next;
    }
    toTruncate->next = NULL;
    return slow;
}

而 sortList() 中第 8 行有函式 mergeSorted() ，功能為將兩個已排序的 linked list 合而為一。

list_ele_t *mergeSorted(list_ele_t *first,
                        list_ele_t *second,
                        int (*cmp)(const char *, const char *))
{
    list_ele_t *ans;
    pop(cmp(first->value, second->value) < 0 ? &first : &second, &ans);
    list_ele_t *it = ans;
    while (1) {
        if (!first) {
            it->next = second;
            break;
        } else if (!second) {
            it->next = first;
            break;
        } else {
            pop(cmp(first->value, second->value) < 0 ? &first : &second,
                &it->next);
            it = it->next;
        }
    }
    return ans;
}

為使 mergeSorted() 更為簡潔，我們引入 pop() inline ，該函式從 stack 的最前方移除一個元素交給 receiver 。

void inline pop(list_ele_t **stack, list_ele_t **receiver)
{
    *receiver = *stack;
    *stack = (*stack)->next;
}

至第三版本終於通過自動評分機制，完成 queue.c 的實作。

---     TOTAL           100/100

Address Sanitizer

首先我們看到以下錯誤訊息

=================================================================
==36384==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55ded5195400 at pc 0x55ded517e8ff bp 0x7ffc09e411a0 sp 0x7ffc09e41190
READ of size 4 at 0x55ded5195400 thread T0
    #0 0x55ded517e8fe in do_help_cmd /home/tinyynoob/code/lab0/console.c:307
    #1 0x55ded517ea12 in interpret_cmda /home/tinyynoob/code/lab0/console.c:221
    #2 0x55ded517f1f7 in interpret_cmd /home/tinyynoob/code/lab0/console.c:244
    #3 0x55ded518093a in run_console /home/tinyynoob/code/lab0/console.c:660
    #4 0x55ded517d521 in main /home/tinyynoob/code/lab0/qtest.c:788
    #5 0x7f76380ae0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x55ded517ab7d in _start (/home/tinyynoob/code/lab0/qtest+0x8b7d)

0x55ded5195401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55ded5195400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/tinyynoob/code/lab0/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
  0x0abc5aa2aa30: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x0abc5aa2aa40: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x0abc5aa2aa50: f9 f9 f9 f9 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9
  0x0abc5aa2aa60: 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9
  0x0abc5aa2aa70: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0abc5aa2aa80:[01]f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x0abc5aa2aa90: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x0abc5aa2aaa0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0abc5aa2aab0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0abc5aa2aac0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0abc5aa2aad0: 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
==36384==ABORTING