# 2021q1 Homework1 (lab0)
contributed by shanlee870502
###### tags: `linux2021`
:::danger
調整下方書寫:
1. 不需要提及時間戳記，畢竟在 GitHub/HackMD 都有編修紀錄
2. 中英文間用一個半形空白字元區隔
:::
> 謝謝老師，已修正!
> 你沒有完全落實「中英文間用一個半形空白字元區隔」這項規範 :notes: jserv

### 作業要求
#### Learning
- [ ] Adress Sanitizer
- [x] Valgrind

#### Implement
- [x] q_new
- [x] q_free
- [x] q_insert_head
- [x] q_insert_tail
- [x] q_remove_head
- [x] q_size
- [x] q_reverse
- [x] q_sort

---

### 常用命令
1. 調整程式縮排: `$ clang-format -i queue.c`
2. Valgrind memeory track: `$ valgrind --tool=<toolname> <program>`
* e.g. `$ valgrind -q --leak-check=full ./case1`
* `$ valgrind --tool=massif ./qtest -f traces/trace-01-ops.cmd`
* `$ ms_print <massif.out> | head -n 50`
3. `./qtest`
new: 建立新的佇列;
ih: 從佇列開頭 (head) 插入一個字串，內容是 "dolphin";
ih: 繼續從佇列開頭插入一個字串，內容是 "bear";
ih: 繼續從佇列開頭插入一個字串，內容是 "gerbil" (沙鼠);
it: 從佇列尾端 (tail) 插入一個字串，內容是 "meerkat" (狐獴);
it: 繼續從佇列尾端 (tail) 插入一個字串，內容是 "bear";
reverse: 將佇列內部的鏈結串列順序予以反向;

### 開發環境
- 使用 linux server

$ cat /etc/os-release
NAME="Ubuntu"
VERSION="16.04.7 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.7 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial

### 開發紀錄
1. 環境安裝
- 自行編譯 cppcheck ([參考此篇筆記](https://hackmd.io/@IID/2020q1-Homework1-lab0)，但此篇筆記make後的安裝命令 ```shell $sudo checkinstall``` 我無法使用，最後以 ```shell $cmake --build . --target install``` 解決)。
* 再次確認版本是否更新 :hammer:

        $ cppcheck --version
        Cppcheck 2.3

2. Valgrind
[Valgrind](https://valgrind.org/) 是個在使用者層級 (user space) 對程式在執行時期的行為提供動態分析的系統軟體框架，具備多種工具，可以用來追蹤及分析程式效能，最為人們所熟知的特性就是幫助使用者偵測記憶體錯誤，諸如使用未初始化的記憶體、不當的記憶體配置、或取消配置記憶體，並加以分析。- [name=jserv]

* user space概念 (參考來源自 [Julia Evans](https://twitter.com/b0rk/status/804200666226900992)):

### queue.c
* q_new: 解決 malloc 回傳 NULL 之情況。
* 想法：若無分配記憶體空間，則回傳 NULL ，若有，初始化 head, tail, size。
* Code:

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

* q_free: 除了釋放 queue 以外，也釋放 list elements, strings的記憶體。
* 想法：先確認 q 非 NULL，再走訪每個節點，free each element，最終再把 queue釋放。
* Code:

    void q_free(queue_t *q)
    {
        if(!q){
            return;
        }
        for(int i=0; i < q->size ; i++){
            list_ele_t *tmp = q->head;
            q->head = q->head->next;
            free(tmp->value);
            free(tmp);
        }
        free(q);
    }

* q_insert_head
* 想法：
* newh 為欲插入 head 的 list_ele_t。
* 考慮 malloc return NULL 之情形： q, newh, newh->value。
* 若q->size = 0，則 q->tail 和 q->head 同為 newh。
* strlcpy 只有在 BSD system 上有，故需要定義 ```strlcpy```，否則會以下錯誤：

         error: implicit declaration of function ‘strlcpy’ [-Werror=implicit-        function-declaration]

定義 ```strlcpy``` 方式 :

        #ifndef strlcpy
        #define strlcpy(dst,src,sz) snprintf((dst), (sz), "%s", (src))
        #endif

參考連結： CERN [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml)
* code:

        bool q_insert_head(queue_t *q, char *s)
        {
            if (!q) {
                return false;
            }
            list_ele_t *newh = malloc(sizeof(list_ele_t));

            if (!newh) {
                return false;
            }
            int s_len = strlen(s) + 1;
            newh->value = (char *) malloc(s_len);
            if (!newh->value) {
                free(newh);
                return false;
            }
            strlcpy(newh->value, s, s_len);
            newh->next = q->head;
            q->head = newh;
            if (q->size == 0) {
                q->tail = newh;
            }
            q->size += 1;
            return true;
        }

* q_insert_tail
* 想法：
* newt 為欲插入 tail 的 list_ele_t。
* 考慮malloc return NULL之情形： q, newt, newt->value。
* 若q->size = 0，則 q->head 和 q->tail 同為 newt。
* code:

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

            list_ele_t *newt = malloc(sizeof(list_ele_t));
            if (!newt) {
                return false;
            }
            int t_len = strlen(s) + 1;  // Including '\x00'
            newt->value = (char *) malloc(t_len);
            if (!newt->value) {
                free(newt);
                return false;
            }
            strlcpy(newt->value, s, t_len);
            newt->next = NULL;
            if (q->size == 0) {
                q->head = newt;
            } else {
                q->tail->next = newt;
            }
            q->tail = newt;
            q->size += 1;
            return true;
        }

* q_remove_head
* 注意要求
> If sp is non-NULL and an element is removed, copy the removed string to *sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)
* 想法：
* 複製 q->head->value 於 ```sp```
* 將 ```*tmp``` 指向 q->head，再將 q->head 更新至 tmp->next ( 也就是q->head->next )
* 釋放 tmp 記憶體
* code:

    bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
    {
        list_ele_t *tmp;
        if (!q || !q->head || q->size == 0) {
            return false;
        }
        if (sp) {
            strlcpy(sp, q->head->value, bufsize);
        }
        tmp = q->head;
        q->head = tmp->next;
        if (tmp == q->tail) {
            q->tail = NULL;
        }
        q->size--;
        free(tmp->value);
        free(tmp);
        return true;
    }

* q_reverse
    * 想法: 

digraph foo {
rankdir=LR;
node [shape=record];
prev [shape="none" label= "prev"];
curr [shape="none" label= "curr"];
next [shape="none" label= "next"];
null [shape="none", label= "NULL"];
prev->null;
curr->a;
next->b[color="green"];
a [label="{ <data> 12 | <ref> }"];
b [label="{ <data> 99 | <ref> }"];
c [label="{ <data> 37 | <ref> }"];
d [label="{ <data> 21 | <ref> }"];
a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}

    ---

digraph foo {
rankdir=LR;
node [shape=record];
prev [shape="none" label= "prev"];
curr [shape="none" label= "curr"];
next [shape="none" label= "next"];
null [shape="none", label= "NULL"];
prev->a[color="blue"];
curr->b[color="purple"];
next->c[color="green"];
a [label="{ <data> 12 | <ref> }"];
b [label="{ <data> 99 | <ref> }"];
c [label="{ <data> 37 | <ref> }"];
d [label="{ <data> 21 | <ref> }"];
a:ref:c ->null[color="red" arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}

    ---

digraph foo {
rankdir=LR;
node [shape=record];
prev [shape="none" label= "prev"];
curr [shape="none" label= "curr"];
next [shape="none" label= "next"];
null [shape="none", label= "NULL"];
prev->b[color="blue"];
curr->c[color="purple"];
next->d[color="green"];
a [label="{ <data> 12 | <ref> }"];
b [label="{ <data> 99 | <ref> }"];
c [label="{ <data> 37 | <ref> }"];
d [label="{ <data> 21 | <ref> }"];
a:ref:c ->null[arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref:c -> a [color="red" arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}

    以此類推
    * code:

void q_reverse(queue_t *q)
{
if(!q){
return;
}
list_ele_t *prev, *curr, *next;
prev = NULL;
curr = q->head;

while(curr){
next = curr->next;//green
curr->next = prev; //red
prev = curr; //blue
curr = next; //purple
}
q->tail = q->head;
q->head = prev;
}

* q_sort
參考[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
參考[Floyid Cycle Detection Algorithm](https://matthung0807.blogspot.com/2020/04/floyd-cycle-detection-algorithm-floyd.html)
* code:

---

#### 問題集:
1. q_insert_tail not constant time $O(1)$
原版:
* 修正想法:
    * 確認程式碼邏輯( No loop as possible b.c. need constant time) :ok: 
    * 思考較耗時的函式: malloc() / strlcpy() / free() 這些是否有錯誤的使用或理解
    -> malloc() V
    -> free() V
    -> strlcpy() X
   **```strlcpy()```的使用方式認知可能有誤!** 

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

list_ele_t *newt = malloc(sizeof(list_ele_t));
if (!newt) {
return false;
}
int t_len = strlen(s) + 1; // Including '\x00'
newt->value = (char *) malloc(t_len);
if (!newt->value) {
free(newt);
return false;
}
strlcpy(newt->value, s, t_len);
newt->next = NULL;
if (q->size == 0) {
q->head = newt;
} else {
q->tail->next = newt;
}
q->tail = newt;
q->size += 1;
return true;
}

strlcpy, strncpy竟然時間上差那麼多?!! 太不可思議了吧...

* trace-15-perf.cmd 修正想法
    * 實際測試，發現執行 sort 時會發生 segmentation fault 之情形。
    * 使用命令 ```$ make valgrind``` 查看記憶體的狀況，發現有 stack overflow, SIGSEGV

+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
==24271== Stack overflow in thread #1: can't grow stack to 0xffe801000
==24271== Stack overflow in thread #1: can't grow stack to 0xffe801000
==24271== Can't extend stack to 0xffe8010a8 during signal delivery for thread 1:
==24271== no stack segment
==24271==
==24271== Process terminating with default action of signal 11 (SIGSEGV)
==24271== Access not within mapped region at address 0xFFE8010A8
==24271== Stack overflow in thread #1: can't grow stack to 0xffe801000
==24271== at 0x405264: merge (queue.c:186)
==24271== If you believe this happened as a result of a stack
==24271== overflow in your program's main thread (unlikely but
==24271== possible), you can try to increase the size of the
==24271== main thread stack using the --main-stacksize= flag.
==24271== The main thread stack size used in this run was 8388608.

    * 使用命令 `$ ./scripts/debug.py -d`，發現於 `queue.c` 的第 186 行發生 Segmentation fault

cmd> new
q = []
cmd> ih h 1000000
q = [h h h h h h h h h h h h h h h h h h h h h h h h h h h h h h ... ]
cmd> sort

Program received signal SIGSEGV, Segmentation fault.
0x0000000000405264 in merge (left=left@entry=0x4319d00, right=0x260bc80)
at queue.c:186
186 if(strcmp(left->value, right->value)<0){

    
    嘗試將 merge 由遞迴換為迭代作法，通過！

list_ele_t *merge(list_ele_t *left, list_ele_t *right) {
list_ele_t *head, *tmp;
if(strcmp(left->value, right->value) < 0){
head = left;
left = left->next;
} else {
head = right;
right = right->next;
}
tmp = head;
while (left && right) {
if (strcmp(left->value, right->value) < 0){
tmp->next = left;
tmp = tmp->next;
left = left->next;
} else {
tmp->next = right;
tmp = tmp->next;
right = right->next;
}
}
if (left) {
tmp->next = left;
}
if (right) {
tmp->next = right;
}

### Valgrind
![](https://i.imgur.com/uCouaE6.png)

:::warning
貼圖不解說，此風不可長
:notes: jserv
:::