# 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 :::