# 2021q1 Homework1 (lab0)
contributed by < `Nahemah1022` >
## Reviewed by Chialiang86
Merge Sort 本身是一個 [stable](https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important) (two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted) 的排序演算法，考慮以下 `merge_sort` 的實作片段

list_ele_t **indirect = &result;
// compare and merge list
while (lhs && rhs) {
    if (strcasecmp(lhs->value, rhs->value) < 0) {
        *indirect = lhs;
        lhs = lhs->next;
    } else {
        *indirect = rhs;
        rhs = rhs->next;
    }
    indirect = &(*indirect)->next;
}

- 由 `strcasecmp(lhs->value, rhs->value) < 0)` 可以發現，當 `strcasecmp(lhs->value, rhs->value) == 0` 時，會執行 `else` 區塊，讓 `rhs` 的元素加到要 merge 的 list 中，此時會違反 stable ，建議的改進方式如下：

list_ele_t **indirect = &result;
// compare and merge list
while (lhs && rhs) {
    if (strcasecmp(lhs->value, rhs->value) > 0) {
        *indirect = rhs;
        rhs = rhs->next;
    } else {
        *indirect = lhs;
        lhs = lhs->next;
    }
    indirect = &(*indirect)->next;
}

- 此時就算 `strcasecmp(lhs->value, rhs->value) == 0` ，也會將 lhs 優先加入要 merge 的 list 中，符合 stable 的原則

---

## Reviewed by gyes00205
q_sort 的部分可以改成這樣就為精簡，從 `q->size` 判斷串列大小，再決定需不需要排序。
另外在更新 `q->tail` 的地方，我的作法是從原本的 `q->tail` 繼續尋找排序過後的串列尾端 。因為排序後的 `q->tail` 雖然不是指向真正的尾端，但會比從 `q->head` 開始搜尋還要快速。

void q_sort(queue_t *q)
{
-   if (!q || !q->head || !q->head->next) {
+   if (!q || q->size <= 1) {
        return;
    }

    merge_sort(&(q->head));
-   list_ele_t *tmp = q->head;
-   while (tmp->next) {
-       tmp = tmp->next;
-   }
-   q->tail = tmp;
+   while (q->tail->next)
+       q->tail = q->tail->next;
}

---
###### tags: `linux2021`

- [x] 實做 queue 相關的程式檔案，說明如何逐步達到自動評分程式的要求
- [x] Address Sanitize 修正 qtest
- [ ] 運用 Valgrind 排除 qtest 的記憶體錯誤，並透過 Massif 視覺化
- [ ] 在 qtest 中實作 coroutine

---

## 一、實做 queue 相關的程式檔案，說明如何逐步達到自動評分程式的要求
> [GitHub](https://github.com/Nahemah1022/lab0-c)

### 1. q_new
- 由 `malloc` 取得 `queue_t` 所需的記憶體空間，指向他並初始化 members 為 `NULL`
- 若記憶體配置失敗則 `return NULL`

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

### 2. q_free
- 從 head 開始 `free` node 中 `value` 指向的字串、以及 node 本身
- 最後 `free` queue 本身

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

### 3. q_insert_head
- 新增一個 node 並與原來的 `head` 連接
- 若新增失敗則 `return false`
- 若只有一個 node 則將 `tail` 也指向新 node

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

### 4. q_insert_tail
- 新增一個 node 並與原來的 `tail` 連接
- 若新增失敗則 `return false`
- 若只有一個 node 則將 `head` 也指向新 node

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

### 5. q_remove_head
- 用 `memcpy` 將 `head->value` 搬移至 `sp`
- 若 `head->value` 的長度小於 `bufsize - 1`，則只複製 `head->value` 的長度到 `sp`
- 否則複製完整 `bufsize - 1` 長度到 `sp`
- 在 `sp` 的最後加上 `\0` 即可

    if (!q || !q->head) {
        return false;
    }

    if (sp) {
        size_t minlen = (strlen(q->head->value) < bufsize - 1)
                            ? strlen(q->head->value)
                            : bufsize - 1;
        memcpy(sp, q->head->value, minlen);
        *(sp + minlen) = '\0';
    }
    list_ele_t *n = q->head;
    q->head = n->next;
    free(n->value);
    free(n);
    (q->size)--;
    return true;
}

### 6. q_size

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

### 7. q_reverse

void q_reverse(queue_t *q)
{
    if (!q || !q->head || !q->head->next) {
        return;
    }

    q->tail = q->head;
    list_ele_t *prev = NULL, *cur = q->head, *next;
    while (cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    q->head = prev;
}

### 8. q_sort
- 利用 merge sort 演算法，找到 linked list index 的中位數，切割為左右兩個區段後再次遞迴
- 將兩區段比較並排序

void merge_sort(list_ele_t **list)
{
    if (!(*list) || !(*list)->next) {
        return;
    }

    list_ele_t *slow = *list, *fast = (*list)->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_ele_t *lhs = *list, *rhs = slow->next, *result = NULL;
    slow->next = NULL;
    merge_sort(&lhs);
    merge_sort(&rhs);

    list_ele_t **indirect = &result;
    // compare and merge list
    while (lhs && rhs) {
        if (strcasecmp(lhs->value, rhs->value) < 0) {
            *indirect = lhs;
            lhs = lhs->next;
        } else {
            *indirect = rhs;
            rhs = rhs->next;
        }
        indirect = &(*indirect)->next;
    }
    // concatenate remaining nodes
    if (lhs) {
        *indirect = lhs;
    } else if (rhs) {
        *indirect = rhs;
    }

    *list = result;
}

void q_sort(queue_t *q)
{
    if (!q || !q->head || !q->head->next) {
        return;
    }

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

:::warning
在實做 Mergesort 演算法前，我有嘗試用我寫的 [Non-Recursive Quicksort](https://github.com/Nahemah1022/Linux2021-quizzes/blob/main/quiz1/optimized-non-recur-linkedlist-qsort.c) 方法來實做，但由在 qtest 中的 `trace-15-perf`、`trace-16-perf` 一直無法通過，經過追蹤發現問題如下：
- `trace-15-perf` 的測資接近 `quicksort` 演算法的 worst case，時間複雜度接近 $O(n^2)$
- 為了滿足 worst case 可能會需要的 stack capacity，程式中用來模擬 stack 實做的 `beg[]、end[]` 兩 array 需宣告的大小為 queue 本身的 size，造成記憶體耗盡

由於無法避免 Quicksort 演算法的 worst case，因此我改用 Mergesort 實做即可將時間複雜度控制在 $O(log\ n)$，解決此問題並通過 `qtest` 評分
:::

## 二、修正 Address Sanitize 中的 qtest 錯誤
原錯誤訊息如下：

nahemah@nahemah:~/Programs/linux2021/lab0-c$ ./qtest 
cmd> help
Commands:
        #        ...            | Display comment
        free                    | Delete queue
        help                    | Show documentation
        ih       str [n]        | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
        it       str [n]        | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
        log      file           | Copy output to file
        new                     | Create new queue
        option   [name val]     | Display or set options
        quit                    | Exit program
        reverse                 | Reverse queue
        rh       [str]          | Remove from head of queue.  Optionally compare to expected value str
        rhq                     | Remove from head of queue without reporting value.
        show                    | Show queue contents
        size     [n]            | Compute queue size n times (default: n == 1)
        sort                    | Sort queue in ascending order
        source   file           | Read commands from source file
        time     cmd arg ...    | Time command execution
Options:
=================================================================
==182478==ERROR: AddressSanitizer: global-buffer-overflow on address 0x560db9011400 at pc 0x560db8ffa90f bp 0x7fffa1567bc0 sp 0x7fffa1567bb0
READ of size 4 at 0x560db9011400 thread T0
    #0 0x560db8ffa90e in do_help_cmd /home/nahemah/Programs/linux2021/lab0-c/console.c:307
    #1 0x560db8ffaa22 in interpret_cmda /home/nahemah/Programs/linux2021/lab0-c/console.c:221
    #2 0x560db8ffb207 in interpret_cmd /home/nahemah/Programs/linux2021/lab0-c/console.c:244
    #3 0x560db8ffc94a in run_console /home/nahemah/Programs/linux2021/lab0-c/console.c:660
    #4 0x560db8ff9531 in main /home/nahemah/Programs/linux2021/lab0-c/qtest.c:788
    #5 0x7f99f727e0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x560db8ff6b8d in _start (/home/nahemah/Programs/linux2021/lab0-c/qtest+0x8b8d)

0x560db9011401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x560db9011400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/nahemah/Programs/linux2021/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
  0x0ac2371fa230: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x0ac2371fa240: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x0ac2371fa250: f9 f9 f9 f9 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9
  0x0ac2371fa260: 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9
  0x0ac2371fa270: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ac2371fa280:[01]f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
  0x0ac2371fa290: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x0ac2371fa2a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac2371fa2b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac2371fa2c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ac2371fa2d0: 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
==182478==ABORTING

### 1. 如何追蹤到錯誤
1. 觀察錯誤訊息的 `34` 行發現錯誤偵測點在 `console.c` 中 `do_help_cmd` fucntion 的 `307` 行，該行內容如下，由於錯誤訊息中明確寫出 `do_help_cmd` 而不是 `report` function，因此可以推測錯誤點就在 `report` function 的參數傳遞中，而非 `report` function 的內部

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

2. 因此進一部追蹤參數 `plist` 的由來，來自於同樣在 `console.c` 檔案的 `static` 變數 `param_ptr param_list`
3. 追蹤到 `param_list` 變數是在 `add_param` function 中被賦值，觀察後推測 `add_param` function 的功能是建立一個新的 node `param_ptr next_param` ，將其按照字典順序插入原有的 `param_list` linked list 中，並對該 node 賦值

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

4. 追蹤 `add_param` function 的呼叫點，發現在 `init_cmd` function 中的下方數行，問題源頭即在 `simulation`、`echo` 兩 global 變數在宣告時的型態為 `bool` (1 byte)， cast 成 `int` 型態 (4 byte)，因此被 Address Sanitizer 判定其跨越原來所屬的記憶體空間 (global-buffer-overflow) 而報錯

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

:::warning
**出錯時機：為何到了 `do_help_cmd` function 時才被偵測到**
因為在執行到 `do_help_cmd` function 之前，`simulation` 與 `echo` 兩變數都是用 `int *` 的 pointer 的型態在傳遞變數位址，而在程式中無論型態，每一個 pointer 變數的 size 都是相等的，因此不會有跨越原來所屬的記憶體空間的狀況發生。
但到了 `do_help_cmd` function 中指標初次被 `*plist->valp` 直接造訪到其指向地點，因此一個僅有 1 byte 大小的空間被程式視作 4 byte 大小，跨越原來所屬的記憶體空間才被 Address Sanitizer 偵測出來而報錯。
:::

### 2. 解決方式
解決方式為 ==不要將型態為 `bool` 的變數 cast 成 `int`== 即可，但上方的 params 各有各自的型態，在 C 語言中也不支援類似 OOP 中 function overloading 的實作，因此我認為對程式運行最有利的方法是 **為不同型態的 param 設計不同的 function 來處理**，如下方程式：

add_bool_param("simulation", &simulation, "Start/Stop simulation mode", NULL);
add_int_param("verbose", &verblevel, "Verbosity level", NULL);
add_int_param("error", &err_limit, "Number of errors until exit", NULL);
add_bool_param("echo", &echo, "Do/don't echo commands", NULL);

/* Add a new parameter */
void add_int_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, 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_int_param");
    ele->name = name;
    ele->valp = valp;
    ele->documentation = documentation;
    ele->setter = setter;
    ele->next = next_param;
    *last_loc = ele;
}

void add_bool_param(char *name,
               bool *valp,
               char *documentation,
               setter_function setter)
{
    param_ptr next_param = param_list;
    param_ptr *last_loc = &param_list;
    while (next_param && strcmp(name, 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_bool_param");
    ele->name = name;
    ele->valp = (int *) malloc_or_fail(sizeof(int), "add_bool_param");
    *(ele->valp) = valp ? 1 : 0;
    ele->documentation = documentation;
    ele->setter = setter;
    ele->next = next_param;
    *last_loc = ele;
}

:::info
若直接將 `bool` 型態全部改寫成 `int`，也可修正此錯誤，但會有以下兩個缺點：
- 將原本只須佔用 1 byte 的變數擴增為 4 byte，會造成不必要的記憶體浪費
- 其中 `simulation` 是需 extern 至 `qtest.c` 中的變數，若擅自修改其型態可能會連帶造成其他地方的錯誤，且難以追蹤與維護
:::