---
# System prepended metadata

title: 2021q1 Homework1 (lab0)
tags: [linux2021]

---

# 2021q1 Homework1 (lab0)
contributed by < `WayneLin1992` >
###### tags: `linux2021`
## 作業要求
- [x] fork 到自己的 GitHub 上
- [x] 修正 queue 及 連帶檔案
- [x] 使用 `make test` 跑分數並修正錯誤
- [x] Address Sanitize 修正 `qtest`
- [ ] 運用 Valgrind 排除 `qtest` 的記憶體錯誤，並透過 Massif 視覺化
- [ ] 在 `qtest` 中實作 coroutine

## 修正 queue 及相關檔案
執行環境介紹
```shell
$ uname -a
Linux wayne-ThinkPad-T14s-Gen-1 5.8.0-38-generic #43~20.04.1-Ubuntu SMP Tue Jan 12 16:39:47 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux
$ cat /proc/version
Linux version 5.8.0-38-generic (buildd@lgw01-amd64-060) (gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0, GNU ld (GNU Binutils for Ubuntu) 2.34) #43~20.04.1-Ubuntu SMP Tue Jan 12 16:39:47 UTC 2021
```

以下是待修正的檔案
- [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`

### `queue_t`
```cpp
typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;
```

`head` 指向頭部 `tail` 指向尾部 `size` 存 list 數量，確保在之後實作中`q_insert_tail` 及 `q_size` 能在 O(1) 的時間複雜度能完成。

### `q_new`
```cpp
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`
```cpp=
void q_free(queue_t *q)
{
    if (!q)
        return;
    list_ele_t *tmp = q->head;
    while (q->head) {
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
        tmp = q->head;
    }
    free(q);
}
```


### `q_insert_head`
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0)
        q->tail = newh;
    q->size = q->size + 1;
    return true;
}
```

### `q_insert_tail`
```cpp=
bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s) + 1);
    newh->next = NULL;
    if (q->size == 0) {
        q->head = newh;
    } else {
        q->tail->next = newh;
    }
    q->tail = newh;
    q->size = q->size + 1;
    return true;
}
```
首先，先 `malloc`  `newh` 一個記憶體空間，並將 s `strncpy` 至 `newh->value` 中。
```graphviz
digraph list_add_node_t {
    node [shape=record];
    struct1 [label="<f0> head|<f1> size|<f2> tail"];
    struct2 [label="<f0> newh value|<f2> next"];
    struct3 [label="<f0> tail value|<f2> next"];
    struct4 [label="<f0> head value|<f2> next"];
    struct1:f2->struct3:f0;
    struct1:f0->struct4:f0;
    struct4:f2->struct3:f0;
}  
```
並將 `tail->next = newh;` , 再把 `q->tail = newh;` ，最後還要記得 `q->size+1`, 這樣就完成了 `q_insert_tail` 由於 `queue` 有指標指向 `tail` 省去搜索需要的時間，才能保持在時間複雜度 O(1) 的情況下。
```graphviz
digraph list_add_node_t {
    rankdir = "LR"
    node [shape=record];
    struct1 [label="<f0> head|<f1> size|<f2> tail"];
    struct2 [label="<f0> newh value|<f2> next"];
    struct3 [label="<f0> tail value|<f2> next"];
    struct4 [label="<f0> head value|<f2> next"];
    struct1:f2->struct2:f1;
    struct1:f0->struct4:f0;
    struct4:f2->struct3:f0;
    struct3:f2->struct2:f0;
}  
```
:::info
注意 使用 malloc 及 strncpy 時，要在 strlen(s)+1 確保在有空間把 '\0' 寫入
:::

### `q_size`
```cpp=
int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}
```
因為 `queue` 有紀錄， `size` 使他能在 O(1) 時間複雜度完成。

### `q_remove_head`
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || q->size == 0) {
        return false;
    }
    int spc;
    list_ele_t *rme = q->head;
    if (bufsize < (strlen(rme->value) + 1)) {
        spc = bufsize - 1;
    } else {
        spc = strlen(rme->value) + 1;
    }
    if (sp) {
        strncpy(sp, rme->value, spc);
        sp[spc] = '\0';
    } else {
        return false;
    }
    q->head = q->head->next;
    rme->next = NULL;
    free(rme->value);
    free(rme);
    q->size = q->size - 1;
    return true;
}
```
:::info
:bell: remove 特定的元素，要把記憶體空間釋放，這樣測試才能得到分數。
:::

### `q_reverse`
```cpp=
void q_reverse(queue_t *q)
{
    if (!q || q->size == 0)
        return;
    list_ele_t *prv = q->head;
    list_ele_t *curr = q->head;
    list_ele_t *next = q->head->next;
    curr->next = NULL;
    q->tail = curr;
    while (next) {
        curr = next;
        next = next->next;
        curr->next = prv;
        prv = curr;
    }
    q->head = curr;
}
```
有先設定三個指標，分別為 `prv` `curr` `next` ，分別代表前一個、目前、下一個，`prv` 和 `curr` 一開始指向 `head` ， `next` 指向 `head->next` 並將 `head->next = NULL` 並將 `tail = curr`  ， 

```graphviz
digraph q_reverse {
    rankdir = "LR"
    node [shape=record];
    struct1 [label="<f0> head|<f1> size|<f2> tail"];
    struct2 [label="<f0> node3 value|<f2> next"];
    struct3 [label="<f0> node2 value|<f2> next"];
    struct4 [label="<f0> node1 value|<f2> next"];
    struct1:f2->struct2:f1;
    struct1:f2->struct4:f0;
    struct3:f2->struct2:f0;
    node [shape=circle];
    prv->struct4:f0;
    curr->struct4:f0;
    next->struct3:f0;
}
```
之後使用 `while` 邊界條件設為 `next = NULL` ， `curr = next` ， `next = next->next` `curr->next = prv` ， 第一迴圈結束後如下圖
```graphviz
digraph q_reverse {
    rankdir = "LR"
    node [shape=record];
    struct1 [label="<f0> head|<f1> size|<f2> tail"];
    struct2 [label="<f0> node3 value|<f2> next"];
    struct3 [label="<f0> node2 value|<f2> next"];
    struct4 [label="<f0> node1 value|<f2> next"];
    struct1:f2->struct2:f1;
    struct1:f2->struct4:f0;
    struct3:f2->struct4:f0;
    node [shape=circle];
    prv->struct3:f0;
    curr->struct3:f0;
    next->struct2:f0;
}
```
第二迴圈，如下圖，因為 `next = NULL` 使得迴圈結束。
```graphviz
digraph q_reverse {
    rankdir = "LR"
    node [shape=record];
    struct1 [label="<f0> head|<f1> size|<f2> tail"];
    struct2 [label="<f0> node3 value|<f2> next"];
    struct3 [label="<f0> node2 value|<f2> next"];
    struct4 [label="<f0> node1 value|<f2> next"];
    struct1:f2->struct2:f1;
    struct1:f2->struct4:f0;
    struct3:f2->struct4:f0;
    struct2:f2->struct3:f0;
    node [shape=circle];
    prv->struct2:f0;
    curr->struct2:f0;
    next->NULL;
}
```
:::info
:bell: 最後還需要將 `head = curr` 即可完成
:::
```graphviz
digraph q_reverse {
    rankdir = "LR"
    node [shape=record];
    struct1 [label="<f0> head|<f1> size|<f2> tail"];
    struct2 [label="<f0> node3 value|<f2> next"];
    struct3 [label="<f0> node2 value|<f2> next"];
    struct4 [label="<f0> node1 value|<f2> next"];
    struct1:f0->struct2:f0;
    struct1:f2->struct4:f0;
    struct3:f2->struct4:f0;
    struct2:f2->struct3:f0;
}
### `merge`
```cpp=
list_ele_t *merge(list_ele_t *p1, list_ele_t *p2)
{
    list_ele_t *head = NULL;
    list_ele_t **tmp = &head;
    while (p1 && p2) {
        if (strcmp(p1->value, p2->value) < 0) {
            *tmp = p1;
            p1 = p1->next;
        } else {
            *tmp = p2;
            p2 = p2->next;
        }
        tmp = &((*tmp)->next);
    }
    if (p1) {
        *tmp = p1;
    } else {
        *tmp = p2;
    }
    return head;
}
```
### `merge_sort`
```cpp=
list_ele_t *merge_sort(list_ele_t *head)
{
    if (!head || !head->next)
        return head;
    list_ele_t *fast = head->next;
    list_ele_t *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    list_ele_t *p1 = merge_sort(head);
    list_ele_t *p2 = merge_sort(fast);
    return merge(p1, p2);
}
```


### `q_sort`
```cpp=
void q_sort(queue_t *q)
{
    if (!q || q->size < 2) {
        return;
    }
    q->head = merge_sort(q->head);
    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}
```

### `make test`後測驗結果
```
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100
```
:::info
:bell: 要記得每個 function 操作前要先注意 q 是否是 empty 或 NULL，要不然 test 不會得到分數
:::

`$ make SANITIZER=1` 之後 `make test` 的錯誤

```
==6545==ERROR: AddressSanitizer: global-buffer-overflow on address 0x557dee1c75e0 at pc 0x557dee1afae8 bp 0x7fff8a9985b0 sp 0x7fff8a9985a0
READ of size 4 at 0x557dee1c75e0 thread T0
    #0 0x557dee1afae7 in do_option_cmd /home/wayne/linux2020/lab0-c/console.c:369
    #1 0x557dee1ae8d0 in interpret_cmda /home/wayne/linux2020/lab0-c/console.c:221
    #2 0x557dee1af0b5 in interpret_cmd /home/wayne/linux2020/lab0-c/console.c:244
    #3 0x557dee1b02e1 in cmd_select /home/wayne/linux2020/lab0-c/console.c:594
    #4 0x557dee1b085b in run_console /home/wayne/linux2020/lab0-c/console.c:667
    #5 0x557dee1ad3e5 in main /home/wayne/linux2020/lab0-c/qtest.c:780
    #6 0x7fc45f8010b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #7 0x557dee1aab8d in _start (/home/wayne/linux2020/lab0-c/qtest+0x8b8d)

0x557dee1c75e1 is located 0 bytes to the right of global variable 'simulation' defined in 'console.c:21:6' (0x557dee1c75e0) of size 1
  'simulation' is ascii string ''
SUMMARY: AddressSanitizer: global-buffer-overflow /home/wayne/linux2020/lab0-c/console.c:369 in do_option_cmd
Shadow bytes around the buggy address:
  0x0ab03dc30e60: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab03dc30e70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab03dc30e80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab03dc30e90: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x0ab03dc30ea0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
=>0x0ab03dc30eb0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9
  0x0ab03dc30ec0: f9 f9 f9 f9 00 00 00 00 01 f9 f9 f9 f9 f9 f9 f9
  0x0ab03dc30ed0: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
  0x0ab03dc30ee0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0ab03dc30ef0: 00 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
  0x0ab03dc30f00: 01 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
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
==6545==ABORTING
---	trace-17-complexity	0/5
---	TOTAL		95/100
```
```cpp=
/* Some global values */
bool simulation = false;
```
`simulation` 原本 `bool` 要被轉成 `int` , 從1 byte->4 bytes (因為 `sizeof(int)` 為 4 bytes) 產生的 global-buffer-overflow 
`add_param("simulation",(int *) &simulation, "Start/Stop simulation mode", NULL)`

觀察一下 `add_param`
```cpp=
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;
}
```
並觀察 `param_ptr` `struct`
```cpp=
/* Integer-valued parameters */
typedef struct PELE param_ele, *param_ptr;
struct PELE {
    char *name;
    int *valp;
    char *documentation;
    /* Function that gets called whenever parameter changes */
    setter_function setter;
    param_ptr next;
};
```
想到的方式
- [ ] 方法一 將 simulation 轉成 int 時用 bitwase 將多餘的 bit 化為 0 
- [x] 方法二 將 simulation declare 從 `bool` 到 `int`
- [ ] 方法三 將int bool 經過判斷後 丟入不同 function進行處裡

方法一:
假如 type 為 bool 時就要將 valp 轉值,可以試試直接做 bitwise 操作，使其得到正確的值 valp & 5 再將 valp 寫進 ele 當中
:::info
& 5 是因為 `int err_limit = 5` 
:::
:::danger
結果失敗!! 這樣會將原本的存在其他記憶體的資料刪掉
:::
方法二:
但也可以一開始就將 simulation declare 為 int ， 經測試後能順利過關

方法三
可以透過 [_Generic(x)](https://en.cppreference.com/w/c/language/generic) 來知道 parameter type 並放入對應的 function 中，得到答案，默認參數 type 為 int。
:::info
:bell: _Generic(x) 是 C11 才新增的關鍵字
:::
```cpp
#define FORMAT(x) \
    _Generic((x), \
        default: add_int_param, \ 
        bool: add_bool_param,\
        )("simulation", x, "Start/Stop simulation mode",
              NULL)
```
因此你要對應的寫下兩個 function `add_int_param` 及 `add_bool_param` 可以參考 [Nahemah1022](https://hackmd.io/@Nahemah1022/SJ4kLLCf) 同學的實作。
## Valgrind 使用 massif 繪圖
```shell
$ valgrind --tool=massif ./qtest -f ./traces/trace-17-ops.cmd
$ massif-visualizer massif.out.7709
```
trace 17 和 simulation 相關，下圖為 massif 繪圖出的狀況
```cpp
# Test if q_insert_tail and q_size is constant time complexity
option simulation 1
it
size
option simulation 0
```
![](https://i.imgur.com/yrdmbRE.png)
:::info
TODO simulation test
:::

## 實作 coroutine
### 什麼是 coroutine
Coroutine(協作): 透過 yield 讓出資源(並會記錄讓出時當下的狀態)，執行其他程式，等到時機又能 Resume 恢復至之前執行的狀態繼續執行，因此可以透過 coroutine 達到並行化( concurrency )，也可以透過 cororutine 使 non-preemptive 讓出資源出來。

Subcoroutines vs. Coroutines
subcoroutine 可以視為 coroutine 的其中一種，因為coroutine 不強調一定要傳回數值，也可以什麼都不回傳，也可以 yield 讓出給其他程式，如下圖所示
![](https://i.imgur.com/tkGIXYb.jpg)


:::info
參考資料:
[Wikipedia Coroutine](https://en.wikipedia.org/wiki/Coroutine)
[Stackoverflow What is a coroutine?](https://stackoverflow.com/questions/553704/what-is-a-coroutine)
[Coroutine](https://hackmd.io/@YLowy/HkT8-S20D)
:::
### tiny-web-server 
首先先用用看 [tiny-web-server](https://github.com/7890/tiny-web-server) 
```shell
listen on port 9999, fd is 3
child pid is 7126
child pid is 7127
child pid is 7128
child pid is 7129
```
http://localhost:9999/
accept request, fd is 4, pid is 7126
由 accept request 對應到 tiny.c
```shell
void process(int fd, struct sockaddr_in *clientaddr) {
#ifdef LOG_ACCESS
	printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
	http_request req;
	parse_request(fd, &req);

	struct stat sbuf;
	int status = 200, ffd = open(req.filename, O_RDONLY, 0);
	if(ffd <= 0) {
		status = 404;
		char *msg = "File not found";
		client_error(fd, status, "Not found", msg);
	} else {
		fstat(ffd, &sbuf);
		if(S_ISREG(sbuf.st_mode)) {
			if (req.end == 0) {
				req.end = sbuf.st_size;
			}
			if (req.offset > 0) {
				status = 206;
			}
			serve_static(fd, ffd, &req, sbuf.st_size);
		} else if(S_ISDIR(sbuf.st_mode)) {
			status = 200;
			handle_directory_request(fd, ffd, req.filename);
		} else {
			status = 400;
			char *msg = "Unknow Error";
			client_error(fd, status, "Error", msg);
		}
		close(ffd);
	}
#ifdef LOG_ACCESS
	log_access(status, clientaddr, &req);
#endif
}
```

### qtest 中實作 coroutine
:::info
TODO
:::