---
tags: Linux
---
# 2021q1 Homework1 (lab0)
contributed by < `Chialiang86` >

## 預期目標
* [C 語言程式設計](https://hackmd.io/@sysprog/c-programming) 議題，如[不定個數參數的處理](https://en.wikibooks.org/wiki/C_Programming/stdarg.h), [signal](https://en.wikibooks.org/wiki/C_Programming/signal.h), [setjmp/longjmp](https://en.wikibooks.org/wiki/C_Programming/setjmp.h) 和記憶體管理;
* 學習 [GNU/Linux 開發工具](https://hackmd.io/@sysprog/gnu-linux-dev)
- [Cppcheck](http://cppcheck.sourceforge.net/): 靜態程式碼分析工具
- [Valgrind](https://valgrind.org/): 動態程式分析工具
* 學習使用 Git 與 GitHub
* 樹立一致且易於協作的程式開發規範
* 研究自動測試機制
* 接觸 [Linux Programming Interface](http://man7.org/tlpi/)
* 學習 [coroutine](https://en.wikipedia.org/wiki/Coroutine)^New^

## 開發環境基本資訊

$ uname -a
Linux chialiang86-System-Product-Name 5.8.0-44-generic #50~20.04.1-Ubuntu SMP Wed Feb 10 21:07:30 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version | head -1
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

## 環境設定
- 安裝必要的開發工具套件

 $ sudo apt install build-essential git-core valgrind
 $ sudo apt install cppcheck clang-format aspell colordiff

- HackMD 筆記上視覺化展現

$ sudo apt install graphviz

## 作業目標

實作 `queue` 的介面設計(包含 `queue.h` 及 `queue.c` )，搭配 [GNU/Linux 開發環境](https://hackmd.io/@sysprog/gnu-linux-dev)，及學習 [Git](https://git-scm.com/) 進行版本控制，同時也整合 [Valgrind](https://valgrind.org/) 動態程式分析工具，作精準的記憶體分析和除錯。

此外，也要求程式開發要養成良好的 coding style ，檢查程式碼和 C/C++ 原始程式碼的風格是否一致，並透過 [Cppcheck](http://cppcheck.sourceforge.net/) 進行靜態程式碼檢查。

[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
- [x] `q_new`: 建立新的「空」佇列;
- [x] `q_free`: 釋放佇列所佔用的記憶體;
- [x] `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
- [x] `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
- [x] `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的元素。
- [x] `q_size`: 計算佇列中的元素數量。
- [x] `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
- [x] `q_sort`: 以==遞增順序==來排序鏈結串列的元素

### TODO
- [ ] `q_sort` 分析 recursive v.s. non-recursive recursive 版本的差異
- [x] valgrind 結果分析
- [ ] 一些 case 使用 graphviz 來圖像化講解。

## 實做細節

### :point_right: Data structure
- 為求可以用時間複雜度 O(1) 求得佇列大小、及插入元素到佇列尾端，對原始資料結構做一些修改如下：
- 新增 `tail` 來指向 `queue_t` 的最後一個元素
- `size` 來紀錄 `queue_t` 中 linked list 所包含的元素個數

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

### :point_right: q_new
- **命令** : new
- **描述** :
- 建立一個空的佇列
- 動態記憶體配置成功則回傳空的佇列
- 動態記憶體配置失敗則回傳 `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;
}

### :point_right: add_ele (自行設計的函數)
- **描述** :
- 把動態配置一個 `list_ele_t` 元素的細節（包含 pointer 的記憶體配置、記憶體配置失敗的處理）隱藏起來。
- 讓 `q_insert_head` 及 `q_insert_tail` 的程式碼專注處理插入新元素的細節。
- 提高程式碼的可讀性和可維護性。
- (待補充 : memory leak issue)

list_ele_t *add_ele(const char *str)
{
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    // issue : memory leak
    if (!newh)
        return NULL;

    char *s = malloc(sizeof(char) * (strlen(str) + 1));
    if (!s) {
        free(newh);
        newh = NULL;
        return NULL;
    }

    strncpy(s, str, strlen(str) + 1);
    newh->next = NULL;
    newh->value = s;
    return newh;
}

### :point_right: q_insert_head
- **命令** : ih
- **描述** :
- 插入一個新的元素至佇列的起始位置。
- 出入成功則回傳 `true`
- 回傳 `false` 當佇列為 `NULL` 或 記憶體配置失敗。

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newh = add_ele(s);

    if (!newh)
        return false;

    newh->next = q->head;
    q->head = newh;
    q->tail = q->size == 0 ? newh : q->tail;
    q->size++;

    return true;
}

### :point_right: q_insert_tail
- **命令** : it
- **描述** :
- 插入一個新的元素至佇列的尾端。
- 插入成功回傳 `true` 。
- 回傳 `NULL` 當佇列為 `NULL` 或 記憶體配置失敗。
- 由於直接使用 `q->tail` 來操作，不需從 `q->head` 來走訪整個 queue 到末端再進行插入，故時間複雜度從 O(n) 變成 O(1)。

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newh = add_ele(s);

    if (!newh)
        return false;

    if (!q->size) {
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;

    return true;
}

### :point_right: q_free
- **命令** : free
- **描述** :
- 釋放整個 queue 所佔用的記憶體空間。
- 使用 `while` 來走訪整個 queue 來逐步釋放記憶體。
- (待補充)

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

### :point_right: q_remove_head
- **命令** : rh
- **描述** :
- 刪除 queue 前端的元素，若 `sp != NULL` 則要將 queue 前端 `bufsize - 1` 個字元複製到 `sp` 中，並在 `sp` 的末端加入空字元 `\0` 。
- 採用 string.h 的 strncpy 來實作有指定大小的字串複製。
- 只有`q` 或 `q->head` 為 `NULL` 會回傳 `false` ，其他狀況皆回傳 `true` 。
- **猜測** :
- 本以為 `q_remove_head` 的參數 (parameter) 這樣設計是為了要確保 queue 前端的元素所指向的字串和參數中的 `sp` 所指向的字串一致才會進行刪除，但經過研究 `make test` 和 `./qtest` 執行的狀況，發現測資不會故意將錯誤的字串刪除，例如 `queue->head->value` 所指向的字串為 `"dog"` ，測資不會故意刪除 `"cat"` 或其他非 `"dog"` 的字串。
- 因此個人猜測參數這樣設計是為了測試方便，若 `queue->head->value` 複製給 `sp` 的字串經過檢查，發現和預期的字串不一致代表是 queue 在操作的過程中有誤(如 reverse 或 sort 的結果不如預期等)。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;

    list_ele_t *del_node = q->head;

    if (!del_node->value) {
        sp = NULL;
    } else {
        if (sp) {
            strncpy(sp, del_node->value, bufsize);
            sp[bufsize - 1] = '\0';
        }
        q->head = del_node->next;
        free(del_node->value);
    }
    free(del_node);
    q->size--;
    return true;
}

### :point_right: q_size
- **命令** : size
- **描述** :
- 計算 queue 中有幾個 element
- 若 `q` 或 `q->head` 為 `NULL` 則回傳 `0` ; 否則回傳 `q->size` 。
- 因為 `q->size` 始終記錄著 queue 裡面的元素個數，因此在 queue 非空時直接回傳即可，時間複雜度為 O(1) 。

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

### :point_right: q_reverse
- **命令** : reverse
- **描述** :
- 將 queue 的 linked list 反向。
- 若 queue 為空或是 queue 中的元素個數沒有大於 1 ，則不需要做反向、直接回傳。
- (待補充：圖示)

void q_reverse(queue_t *q)
{
    if (!q || q->size <= 1)
        return;

    list_ele_t *pre = NULL, *pivot = q->head, *post = q->head->next;
    q->tail = pivot;
    while (post) {
        pivot->next = pre;
        pre = pivot;
        pivot = post;
        post = post->next;
    }
    pivot->next = pre;
    q->head = pivot;
}

### :point_right: q_sort
- **命令** : sort
- **描述** :
- 依照 `strcasecmp` 函數來進行字串比對，將字串進行遞增排序。
- 作業要求要實現時間複雜度 O(n log n) 的算法，考量排序演算法的各種選項，決定以 merge sort 來實作排序，主要原因是因為他的時間複雜度 average case 和 worst case 皆一樣是 O(n log n) ，同時也是 [stable](https://www.geeksforgeeks.org/stability-in-sorting-algorithms/) 的排序演算法，且若不使用 recursive 的方式實作，空間複雜度也可以控制在 O(1)。
- **non-recursive 版本的 merge sort 實作如下：**
- 時間複雜度 ： O(n log n)
- 空間複雜度 ： O(1)

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

    list_ele_t *lpart, *rpart;
    list_ele_t *tmp;
    for (unsigned long len = 1; len < q->size; len *= 2) {
        list_ele_t *last_tail = NULL, *tail;
        list_ele_t *last_tmp = tmp;
        tmp = q->head;
        while (tmp) {
            // add element to left queue
            lpart = tmp;
            for (unsigned long i = 0; i < len && tmp; i++, tmp = tmp->next)
                last_tmp = tmp;
            last_tmp->next = NULL;

            // add element to right queue
            rpart = tmp;
            for (unsigned long i = 0; i < len && tmp; i++, tmp = tmp->next)
                last_tmp = tmp;
            last_tmp->next = NULL;

            list_ele_t *res = merge(lpart, rpart, &tail);
            if (!last_tail)
                q->head = res;
            else
                last_tail->next = res;

            last_tail = tail;
        }
        q->tail = tail;
    }
}

list_ele_t *merge(list_ele_t *lpart, list_ele_t *rpart, list_ele_t **end)
{
    if (!lpart || !rpart)
        return lpart ? lpart : NULL;

    list_ele_t *res_head = NULL, *res_tail;

    if (strcasecmp(lpart->value, rpart->value) > 0) {
        res_head = rpart;
        rpart = rpart->next;
    } else {
        res_head = lpart;
        lpart = lpart->next;
    }

    res_tail = res_head;
    while (lpart || rpart) {
        if (lpart && rpart) {
            if (strcasecmp(lpart->value, rpart->value) > 0) {
                res_tail->next = rpart;
                res_tail = res_tail->next;
                rpart = rpart->next;
            } else {
                res_tail->next = lpart;
                res_tail = res_tail->next;
                lpart = lpart->next;
            }
        } else {
            while (lpart) {
                res_tail->next = lpart;
                res_tail = res_tail->next;
                lpart = lpart->next;
            }
            while (rpart) {
                res_tail->next = rpart;
                res_tail = res_tail->next;
                rpart = rpart->next;
            }
        }
    }
    *end = res_tail;
    return res_head;
}

- **recursive 版本的 merge sort 實作如下：**
- 時間複雜度 ： O(n log n)
- 空間複雜度 ： O(n) -> 主要用在 merge 遞迴呼叫

list_ele_t *merge(list_ele_t *l, list_ele_t *r)
{
    if (!l || !r)
        return l ? l : (r ? r : NULL);

    list_ele_t *head;

    if (strcasecmp(l->value, r->value) > 0) {
        head = r;
        head->next = merge(l, r->next);
    } else {
        head = l;
        head->next = merge(l->next, r);
    }

    return head;
}

list_ele_t *merge_sort(list_ele_t *head)
{
    if (!head)
        return NULL;
    if (!head->next)
        return head;

    list_ele_t *slow = head;
    list_ele_t *fast = head->next;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    fast = slow->next;
    slow->next = NULL;

    slow = merge_sort(head);
    fast = merge_sort(fast);

    head = merge(slow, fast);

    return head;
}

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

    q->head = merge_sort(q->head);

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

### 關於 strcasecmp 函數
- `int strcasecmp(const char *s1, const char *s2);`
- 從 [stackoverflow](https://stackoverflow.com/questions/31127260/strcasecmp-a-non-standard-function) 可得知，此函數並不是定義在 c/c++ 標準當中，引文如下：
> strcasecmp is not in the C or C++ standard. It's defined by POSIX.1-2001 and 4.4BSD.
- [The Open Group Publications Catalog](https://pubs.opengroup.org/onlinepubs/009696799/functions/strcasecmp.html) 對此函數的解釋 :
1. Description
> The strcasecmp() function shall compare, while ignoring differences in case, the string pointed to by s1 to the string pointed to by s2. The strncasecmp() function shall compare, while ignoring differences in case, not more than n bytes from the string pointed to by s1 to the string pointed to by s2.

>In the POSIX locale, strcasecmp() and strncasecmp() shall behave as if the strings had been converted to lowercase and then a byte comparison performed. The results are unspecified in other locales.

2. Return Value
> Upon completion, strcasecmp() shall return an integer greater than, equal to, or less than 0, if the string pointed to by s1 is, ignoring case, greater than, equal to, or less than the string pointed to by s2, respectively.

>Upon successful completion, strncasecmp() shall return an integer greater than, equal to, or less than 0, if the possibly null-terminated array pointed to by s1 is, ignoring case, greater than, equal to, or less than the possibly null-terminated array pointed to by s2, respectively.
- **回傳值**：若 `s1` 較大回傳大於零的值、反之小於零， `s1`, `s2` 一樣大則回傳 0 。
- **大小的意義**：由引文可得知，比較字串的「大小」是先忽略英文字母大小寫，再一個一個 byte 進行比對，兩字串同個位置上的值一樣則往下一個字元比，直到有一方 byte 位置上的值較另一方大，或已至字串結尾，才回傳比較結果。
- **字串長度不一的情況**：假設 `s1` 長度為 `n1` 、字串 `s2` 長度為 `n2` 較 `n1` 長，若 `s2` 的前 `n1` 個 byte 都和 `s1` 一樣，則此時 `s2` 會被判定比 `s1` 大。
- 範例：
1. sort 前

q = [a 2222222222222222 110 2a 24 23 11 10 1]

2. sort 後

q = [1 10 11 110 2222222222222222 23 24 2a a]

## 使用 Valgrind 動態程式分析工具
- Valgrind 是個在使用者層級 (user space) 對程式在執行時期的行為提供動態分析的系統軟體框架，具備多種工具，可以用來追蹤及分析程式效能，最為人們所熟知的特性就是幫助使用者偵測記憶體錯誤，諸如使用未初始化的記憶體、不當的記憶體配置、或取消配置記憶體，並加以分析。所有工具都包含在 valgrind 套件中，可以透過以下命令執行
- 為何要找出 memory leak ？
- 小型程式（記憶體使用量低、程式生命週期短）或許還不至於因為少量的 memory leak 造成嚴重的問題。但對於記憶體用量大、生命週期長（如 server 等）的大型程式來說，些許的 memory leak 長期累積下來相當有可能造成可用記憶體空間不足的情況，且那些已無法使用的記憶體空間（ 如 c 語言的 pointer 已無法存取的記憶體位址）會長期佔用著資源、也沒有任何功用，因此成為嚴重的問題，可見找出並解決 memory leak 是開發者相當要緊的工作。

### 使用方式
#### **1. 自動測試**

$ make valgrind

- 此方式可以檢查 17 個測資的記憶體使用狀況
- 輸出結果（僅擷取部分）：

+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
==11665== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==11665==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11665==    by 0x4A5050E: strdup (strdup.c:42)
==11665==    by 0x1101A1: linenoiseHistoryAdd (linenoise.c:1236)
==11665==    by 0x110D34: linenoiseHistoryLoad (linenoise.c:1325)
==11665==    by 0x10C28F: main (qtest.c:777)
==11665== 
==11665== 111 bytes in 19 blocks are still reachable in loss record 2 of 3
==11665==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11665==    by 0x4A5050E: strdup (strdup.c:42)
==11665==    by 0x110115: linenoiseHistoryAdd (linenoise.c:1236)
==11665==    by 0x110D34: linenoiseHistoryLoad (linenoise.c:1325)
==11665==    by 0x10C28F: main (qtest.c:777)
==11665== 
==11665== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==11665==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11665==    by 0x110161: linenoiseHistoryAdd (linenoise.c:1224)
==11665==    by 0x110D34: linenoiseHistoryLoad (linenoise.c:1325)
==11665==    by 0x10C28F: main (qtest.c:777)
==11665== 
---	trace-15-perf	6/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
==11685== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==11685==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11685==    by 0x4A5050E: strdup (strdup.c:42)
==11685==    by 0x1101A1: linenoiseHistoryAdd (linenoise.c:1236)
==11685==    by 0x110D34: linenoiseHistoryLoad (linenoise.c:1325)
==11685==    by 0x10C28F: main (qtest.c:777)
==11685== 
==11685== 111 bytes in 19 blocks are still reachable in loss record 2 of 3
==11685==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11685==    by 0x4A5050E: strdup (strdup.c:42)
==11685==    by 0x110115: linenoiseHistoryAdd (linenoise.c:1236)
==11685==    by 0x110D34: linenoiseHistoryLoad (linenoise.c:1325)
==11685==    by 0x10C28F: main (qtest.c:777)
==11685== 
==11685== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==11685==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11685==    by 0x110161: linenoiseHistoryAdd (linenoise.c:1224)
==11685==    by 0x110D34: linenoiseHistoryLoad (linenoise.c:1325)
==11685==    by 0x10C28F: main (qtest.c:777)
==11685== 
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
==11686== 7 bytes in 1 blocks are still reachable in loss record 1 of 3
==11686==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11686==    by 0x4A5050E: strdup (strdup.c:42)
==11686==    by 0x1101A1: linenoiseHistoryAdd (linenoise.c:1236)
==11686==    by 0x110D34: linenoiseHistoryLoad (linenoise.c:1325)
==11686==    by 0x10C28F: main (qtest.c:777)
==11686== 
==11686== 111 bytes in 19 blocks are still reachable in loss record 2 of 3
==11686==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11686==    by 0x4A5050E: strdup (strdup.c:42)
==11686==    by 0x110115: linenoiseHistoryAdd (linenoise.c:1236)
==11686==    by 0x110D34: linenoiseHistoryLoad (linenoise.c:1325)
==11686==    by 0x10C28F: main (qtest.c:777)
==11686== 
==11686== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==11686==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==11686==    by 0x110161: linenoiseHistoryAdd (linenoise.c:1224)
==11686==    by 0x110D34: linenoiseHistoryLoad (linenoise.c:1325)
==11686==    by 0x10C28F: main (qtest.c:777)
==11686== 
---	trace-17-complexity	5/5
---	TOTAL		100/100

- （待補充： [`still reachable`](https://stackoverflow.com/questions/3840582/still-reachable-leak-detected-by-valgrind) ）

#### **2. 指定工具及測試程式**：

$ valgrind --tool=<toolname> <program>

- 範例1：使用 qtest 測試、透過 massif 視覺化

valgrind --tool=massif ./qtest 

- qtest 使用的命令如下

option fail 0
option malloc 0
new
ih RAND 10000
sort
free

- 測試結束後，在終端機打 `ls` 可以找到輸出檔 massif.out.PID(PID 會在執行後給定)
- 分析結果：

ms_print massif.out.23473


- 上圖為檔案列出的一部分，以圖形化的方式呈現個時間點的記憶體用量分析（橫軸為時間、縱軸為記憶體用量）
- 各符號代表的意義：

":"  Normal snapshots
"@"  Information about where allocations happened are recorded for these snapshots
"#"  The peak snapshot is a detailed snapshot, and records the point where memory consumption was greatest.

- 範例2：使用 qtest 測試 trace-16-perf.cmd 測資、透過 massif-visualizer 視覺化

$ valgrind --tool=massif ./qtest -f ./trace/trace-16-perf.cmd

- 同樣在測試結束後，找到輸出檔 massif.out.PID，再打以下命令 (PID 為 23046)

$ massif-visualizer massif.out.23046

- 產生結果圖：


- trace-16-perf.cmd 主要為測試三種 size 的 sort ，可以看見上圖大致有三個峰值，分別對應了 size 為 10000, 50000, 100000 的記憶體配置，並在 sort 完成執行 free，圖中可見記憶體釋放時佔用的空間急速下降。