2021q1 Homework1 (lab0)

# 2021q1 Homework1 (lab0) contributed by < [`tinyynoob`](https://github.com/tinyynoob) > > [作業說明](https://hackmd.io/@sysprog/linux2021-lab0#) ## Quick Guide [TOC] ## 開發環境 ``` $ uname -a Linux tinyynoob-home 5.11.0-43-generic #47~20.04.2-Ubuntu SMP Mon Dec 13 11:06:56 UTC 2021 x86_64 x86_64 x86_64 GNU/Linux $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 Copyright (C) 2019 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. ``` ## 實作流程 | 進度 | 內容敘述 | |:-:|:--| |1| q_new() | |1| q_free() | |1| q_insert_head() | |1| q_insert_tail() | |1| q_remove_head() | |1| q_size() | |1| q_reverse() | |1| q_sort() | |0| 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤 | |0| 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗 | |0| 在 `qtest` 中實作 [coroutine](https://en.wikipedia.org/wiki/Coroutine)，並提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令 | |0| 說明 [antirez/linenoise](https://github.com/antirez/linenoise) 的運作原理，注意到 [termios](http://man7.org/linux/man-pages/man3/termios.3.html) 的運用| |0| 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案 | |0| 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關)，嘗試強化並提交 pull request | ### queue.h - 加入指標變數 `tail` 幫助快速找到結尾以利 `q_insert_tail()` 實作。 - 為了能在 $O(1)$ 時間內返回 queue 的大小，因此於 `queue` 的結構中加入一個 `int` 變數 `size` 防止每次都要遍歷 `queue` 求解。 ```c /* Queue structure */ typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; int size; } queue_t; ``` ### queue.c #### q_new() 配置空間後先檢查是否有成功配置，接著為結構成員進行初始化 - 將 `head` 及 `tail` 預設為 `NULL` 防止不當操作 - 將 `size` 預設為0 ```c= 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() 從 `head` 指到的元素開始逐一將 `queue` 中的節點刪除，刪除時將節點內的字串及節點本身釋放。 ##### before ```graphviz digraph q_free0 { node [shape=record]; rankdir=LR; node_0 -> node_1 -> dots -> node_n; q:f0 -> node_0; q:f1 -> node_n; q [label="<f0> head|<f1> tail|<f2> size"]; dots [shape=none label="。。。" fontsize=20]; } ``` ##### after each step ```graphviz digraph q_free1 { node [shape=record]; rankdir=LR; node_0 -> node_1 -> dots; dots -> node_n; q:f0 -> node_0 [style=dashed]; q:f0 -> node_1; q:f1 -> node_n; temp -> node_0 [rankdir=TB]; q [label="<f0> head|<f1> tail|<f2> size"]; temp [shape=diamond]; dots [shape=none label="。。。" fontsize=20]; } ``` ```c= void q_free(queue_t *q) { while (q->head) { list_ele_t *temp = q->head; q->head = temp->next; free(temp->value); free(temp); } free(q); } ``` 由於在測試中遇到錯誤訊息 ``` Segmentation fault occurred. You dereferenced a NULL or invalid pointer 中止 (核心已傾印) ``` 因此在 while 之前加入以下兩行程式碼，避免 doubly free 的問題 ```c if (!q) // prevent doubly free return; ``` #### q_insert_head() 配置 `list_ele_t` 結構空間及字串空間，若配置失敗則立即跳離函式並回傳false；若順利配置則將新節點插入最前方，如果是唯一節點將需要設定 `q` 中的 `tail` 成員。 :::warning 目前不知如何解決 strlen() 若讀不到 ``'\0'`` 的問題 ::: ```c= bool q_insert_head(queue_t *q, char *s) { if (!q) return false; list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t)); if (!newh) return false; int s_size = strlen(s) + 1; // strlen() may not be safe if there is no '\0' char *s_in_ele = (char *) malloc(sizeof(char) * s_size); if (!s_in_ele) { free(newh); return false; } for (int i = 0; i < s_size; i++) // copy the string including '/0' s_in_ele[i] = s[i]; newh->value = s_in_ele; newh->next = q->head; q->head = newh; if (!q->tail) // if newh is the only element q->tail = newh; q->size++; return true; } ``` #### q_insert_tail() 作法與 `q_insert_head()` 類似，但注意到須將原先的尾節點接到新的尾節點，如下方程式碼第 18 行。 ```graphviz digraph insert_tail { node [shape=record]; rankdir=LR; nodes -> dots; dots -> old_tail; old_tail -> new_tail[color=salmon]; tail -> old_tail[style=dashed]; tail -> new_tail; tail[shape=diamond]; dots [shape=none label="。。。" fontsize=20]; } ``` ```c= bool q_insert_tail(queue_t *q, char *s) { if (!q) return false; list_ele_t *newt = (list_ele_t *) malloc(sizeof(list_ele_t)); if (!newt) return false; int s_size = strlen(s) + 1; char *s_in_ele = (char *) malloc(sizeof(char) * s_size); if (!s_in_ele) { free(newt); return false; } for (int i = 0; i < s_size; i++) // copy the string including '/0' s_in_ele[i] = s[i]; newt->value = s_in_ele; newt->next = NULL; if (q->tail) q->tail->next = newt; q->tail = newt; if (!q->head) // if newt is the only element q->head = newt; q->size++; return true; } ``` #### q_remove_head() 先檢查 queue 是否為空，之後執行 1. 若 `sp` 為 non-NULL ，將目標節點內的字串複製至 `sp` 2. 將目標節點從 queue 中移除 3. 更新 `q->size` 及 `q->head` 4. 若移除節點後 `queue` 為空，將 `tail` 成員指向 `NULL` ```c= bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q) return false; else if (!q->size) return false; char *it = q->head->value; size_t sp_size = 0; while (!*it && sp_size < bufsize) { // compute sp_size it++; sp_size++; } if (sp) { // If sp is non-NULL sp = (char *) malloc(sizeof(char) * sp_size); if (!sp) return false; for (size_t i = 0; i < sp_size; i++) // copy the removed string to sp sp[i] = q->head->value[i]; } if (sp_size == bufsize) // if the maximum is achieved sp[bufsize - 1] = '\0'; free(q->head->value); list_ele_t *toDelete = q->head; q->head = q->head->next; free(toDelete); q->size--; if (!q->size) q->tail = NULL; return true; } ``` 我認為這裡題目的原意有些不清，原先誤以為需要為 `sp` 分配空間，理解後重新修改程式，並用更易理解的版本寫 `sp` 的部份，其中 `min` 函式使用 macro 完成。 :::warning 不知道為何將下方程式第 5 行及第 6 行合併會發生錯誤 ::: ```c= bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q || !q->size) return false; size_t sp_size = min(strlen(q->head->value), bufsize - 1); sp_size = sp_size + 1; if (sp) { // if sp is non-NULL for (size_t i = 0; i < sp_size - 1; i++) // copy the string sp[i] = q->head->value[i]; sp[sp_size - 1] = '\0'; } free(q->head->value); list_ele_t *toDelete = q->head; q->head = q->head->next; free(toDelete); if (!q->head) q->tail = NULL; q->size--; return true; } ``` #### q_size() ```c int q_size(queue_t *q) { if (!q) return 0; return q->size; } ``` #### q_reverse() 使用三個 `list_ele_t` 指標一起向後遍歷整個 list 來完成反轉。 \ 概念上等同於依序將節點 push 進一個新的 stack 。 ```c= void q_reverse(queue_t *q) { if (!q || q->size == 0 || q->size == 1) return; q->tail = q->head; list_ele_t *prev = q->head; list_ele_t *temp = q->head->next->next; q->head = q->head->next; q->head->next = prev; while (temp) { prev = q->head; q->head = temp; temp = temp->next; q->head->next = prev; } q->tail->next = NULL; } ``` #### q_sort() 第一個版本額外宣告了一組 array of pointers to elements 來幫助排序 ```c= void q_sort(queue_t *q) { if (!q || !q->size) return; list_ele_t **array = (list_ele_t **) malloc(sizeof(list_ele_t *) * q->size); // array of pointers list_ele_t *temp = q->head; for (int i = 0; i < q->size; i++) { array[i] = temp; temp = temp->next; } q_sort_recur(array, 0, q->size - 1, string_compare); /* relink the list with the result */ for (int i = 0; i < q->size - 1; i++) array[i]->next = array[i + 1]; q->head = array[0]; q->tail = array[q->size - 1]; free(array); } ``` 配合遞迴函式 ```c= void q_sort_recur(list_ele_t **array, int left, int right, int (*cmp)(char *, char *)) { if (left >= right) return; /*choose array[right] as pivot*/ list_ele_t *temp; int i = left; for (int j = left; j < right; j++) { if (cmp(array[j]->value, array[right]->value) < 0) { /* exchange array[i] and array[j] */ temp = array[i]; array[i] = array[j]; array[j] = temp; /* end exchange */ i++; } } /* exchange array[i] and array[right] */ temp = array[i]; array[i] = array[right]; array[right] = temp; /* end exchange */ q_sort_recur(array, left, i - 1, cmp); q_sort_recur(array, i + 1, right, cmp); } ``` 在測試時發現題目並不允許使用 malloc() 。後來我參考了 [quiz 1](https://hackmd.io/@sysprog/linux2021-quiz1) ，意識到在 quick sort 中，往下遞迴時元素的順序並不是很重要，只要求與 pivot 的相對大小。因此 linked list 就有天然的結構，完全不需要額外使用一組指標陣列。於是重新寫出第二版本： ```c= void q_sort(queue_t *q) { if (!q || !q->size) return; q->head = sortList(q->head, strcmp); list_ele_t *it; for (it = q->head; it->next; it = it->next) ; q->tail = it; } ``` 同樣額外建構了一個方便遞迴的 quick sort 函式 ```c= list_ele_t *sortList(list_ele_t *head, int (*cmp)(const char *, const char *)) { if (!head || !head->next) return head; const char *pivot = head->value; list_ele_t *left = NULL, *right = NULL, *it = head->next; while (it) { list_ele_t *temp = it->next; push(cmp(it->value, pivot) > 0 ? &right : &left, it); it = temp; } left = sortList(left, cmp); right = sortList(right, cmp); if (left) { for (it = left; it->next; it = it->next) ; it->next = head; } head->next = right; return left ? left : head; } ``` 及 ```c void inline push(list_ele_t **head, list_ele_t *newNode) { newNode->next = *head; (*head) = newNode; } ``` 在這個過程中，我最有心得的是 ternary operator 跟 pointer to poiner 在 list 操作中的妙用。然而，使用這個版本進行測試，會發現效率並不符合題目的要求。測試結果如下： ```shell= scripts/driver.py -c --- Trace Points +++ TESTING trace trace-01-ops: # Test of insert_head and remove_head --- trace-01-ops 6/6 +++ TESTING trace trace-02-ops: # Test of insert_head, insert_tail, and remove_head --- trace-02-ops 6/6 +++ TESTING trace trace-03-ops: # Test of insert_head, insert_tail, reverse, and remove_head --- trace-03-ops 6/6 +++ TESTING trace trace-04-ops: # Test of insert_head, insert_tail, size, and sort --- trace-04-ops 6/6 +++ TESTING trace trace-05-ops: # Test of insert_head, insert_tail, remove_head, reverse, size, and sort --- trace-05-ops 5/5 +++ TESTING trace trace-06-string: # Test of truncated strings --- trace-06-string 6/6 +++ TESTING trace trace-07-robust: # Test operations on NULL queue --- trace-07-robust 6/6 +++ TESTING trace trace-08-robust: # Test operations on empty queue --- trace-08-robust 6/6 +++ TESTING trace trace-09-robust: # Test remove_head with NULL argument --- trace-09-robust 6/6 +++ TESTING trace trace-10-malloc: # Test of malloc failure on new --- trace-10-malloc 6/6 +++ TESTING trace trace-11-malloc: # Test of malloc failure on insert_head --- trace-11-malloc 6/6 +++ TESTING trace trace-12-malloc: # Test of malloc failure on insert_tail --- trace-12-malloc 6/6 +++ TESTING trace trace-13-perf: # Test performance of insert_tail --- trace-13-perf 6/6 +++ TESTING trace trace-14-perf: # Test performance of size --- trace-14-perf 6/6 +++ TESTING trace trace-15-perf: # Test performance of insert_tail, size, reverse, and sort ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient Segmentation fault occurred. You dereferenced a NULL or invalid pointer --- trace-15-perf 0/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 ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient ERROR: Not sorted in ascending order ERROR: Freed queue, but 19022 blocks are still allocated ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient ERROR: Not sorted in ascending order ERROR: Freed queue, but 118568 blocks are still allocated ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient ERROR: Not sorted in ascending order Error limit exceeded. Stopping command execution --- trace-16-perf 0/6 +++ TESTING trace trace-17-complexity: # Test if q_insert_tail and q_size is constant time complexity Probably constant time Probably constant time --- trace-17-complexity 5/5 --- TOTAL 88/100 ``` 因此，改以 merge sort 來實作 `q_sort()` ，以下為第三個版本： ```c= void q_sort(queue_t *q) { if (!q || !q->size) return; q->head = sortList(q->head, strcmp); list_ele_t *it; for (it = q->head; it->next; it = it->next) ; q->tail = it; } ``` 在 linked list 版本的 merge sort 中，需要將原 list 分割成為兩個 sublist 進行遞迴， `truncate_and_findMid()` 即為進行分割之函式。 ```c= list_ele_t *sortList(list_ele_t *head, int (*cmp)(const char *, const char *)) { if (!head || !head->next) return head; list_ele_t *mid = truncate_and_findMid(head); head = sortList(head, cmp); mid = sortList(mid, cmp); return mergeSorted(head, mid, cmp); } ``` ```graphviz digraph truncate{ //node [shape=record]; rankdir=LR; dots1 -> toTruncate; toTruncate -> slow [style=dashed]; toTruncate -> null [dir=none]; slow ->dots2; toTruncate [shape=record]; slow [shape=record]; dots1 [shape=none label="。。。" fontsize=20]; dots2 [shape=none label="。。。" fontsize=20]; graph [] { rank=same; null [style=invis label="" width="0" height="0"]; null_ [style=invis label="" width="0" height="0"]; null -> null_ [arrowhead=teetee]; } } ``` ```c= /* split the list and return a pointer to the mid element */ list_ele_t *truncate_and_findMid(list_ele_t *const head) { /* the list should be guarantee to have at least 2 elements */ list_ele_t *fast = head->next; list_ele_t *slow = head; list_ele_t *toTruncate = NULL; while (fast) { /* fast forwards 2 place and slow forwards 1 place each iteration */ if (fast->next) fast = fast->next->next; else fast = fast->next; toTruncate = slow; slow = slow->next; } toTruncate->next = NULL; return slow; } ``` 而 `sortList()` 中第 8 行有函式 `mergeSorted()` ，功能為將兩個已排序的 linked list 合而為一。 ```c= list_ele_t *mergeSorted(list_ele_t *first, list_ele_t *second, int (*cmp)(const char *, const char *)) { list_ele_t *ans; pop(cmp(first->value, second->value) < 0 ? &first : &second, &ans); list_ele_t *it = ans; while (1) { if (!first) { it->next = second; break; } else if (!second) { it->next = first; break; } else { pop(cmp(first->value, second->value) < 0 ? &first : &second, &it->next); it = it->next; } } return ans; } ``` 為使 `mergeSorted()` 更為簡潔，我們引入 `pop()` inline ，該函式從 `stack` 的最前方移除一個元素交給 `receiver` 。 ```c void inline pop(list_ele_t **stack, list_ele_t **receiver) { *receiver = *stack; *stack = (*stack)->next; } ``` 至第三版本終於通過自動評分機制，完成 `queue.c` 的實作。 ```shell --- TOTAL 100/100 ``` ### Address Sanitizer 首先我們看到以下錯誤訊息 ```shell= ================================================================= ==36384==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55ded5195400 at pc 0x55ded517e8ff bp 0x7ffc09e411a0 sp 0x7ffc09e41190 READ of size 4 at 0x55ded5195400 thread T0 #0 0x55ded517e8fe in do_help_cmd /home/tinyynoob/code/lab0/console.c:307 #1 0x55ded517ea12 in interpret_cmda /home/tinyynoob/code/lab0/console.c:221 #2 0x55ded517f1f7 in interpret_cmd /home/tinyynoob/code/lab0/console.c:244 #3 0x55ded518093a in run_console /home/tinyynoob/code/lab0/console.c:660 #4 0x55ded517d521 in main /home/tinyynoob/code/lab0/qtest.c:788 #5 0x7f76380ae0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #6 0x55ded517ab7d in _start (/home/tinyynoob/code/lab0/qtest+0x8b7d) 0x55ded5195401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55ded5195400) of size 1 SUMMARY: AddressSanitizer: global-buffer-overflow /home/tinyynoob/code/lab0/console.c:307 in do_help_cmd Shadow bytes around the buggy address: 0x0abc5aa2aa30: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 0x0abc5aa2aa40: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9 0x0abc5aa2aa50: f9 f9 f9 f9 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9 0x0abc5aa2aa60: 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9 0x0abc5aa2aa70: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 =>0x0abc5aa2aa80:[01]f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 0x0abc5aa2aa90: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00 0x0abc5aa2aaa0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0abc5aa2aab0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0abc5aa2aac0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x0abc5aa2aad0: 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 ==36384==ABORTING ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.