# 2021q1 Homework1 (lab0)
contributed by < `Nahemah1022` >
## Reviewed by Chialiang86
Merge Sort 本身是一個 [stable](https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important) (two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted) 的排序演算法,考慮以下 `merge_sort` 的實作片段
```c=
list_ele_t **indirect = &result;
// compare and merge list
while (lhs && rhs) {
if (strcasecmp(lhs->value, rhs->value) < 0) {
*indirect = lhs;
lhs = lhs->next;
} else {
*indirect = rhs;
rhs = rhs->next;
}
indirect = &(*indirect)->next;
}
```
- 由 `strcasecmp(lhs->value, rhs->value) < 0)` 可以發現,當 `strcasecmp(lhs->value, rhs->value) == 0` 時,會執行 `else` 區塊,讓 `rhs` 的元素加到要 merge 的 list 中,此時會違反 stable ,建議的改進方式如下:
```c=
list_ele_t **indirect = &result;
// compare and merge list
while (lhs && rhs) {
if (strcasecmp(lhs->value, rhs->value) > 0) {
*indirect = rhs;
rhs = rhs->next;
} else {
*indirect = lhs;
lhs = lhs->next;
}
indirect = &(*indirect)->next;
}
```
- 此時就算 `strcasecmp(lhs->value, rhs->value) == 0` ,也會將 lhs 優先加入要 merge 的 list 中,符合 stable 的原則
---
## Reviewed by gyes00205
q_sort 的部分可以改成這樣就為精簡,從 `q->size` 判斷串列大小,再決定需不需要排序。
另外在更新 `q->tail` 的地方,我的作法是從原本的 `q->tail` 繼續尋找排序過後的串列尾端 。因為排序後的 `q->tail` 雖然不是指向真正的尾端,但會比從 `q->head` 開始搜尋還要快速。
```diff=
void q_sort(queue_t *q)
{
- if (!q || !q->head || !q->head->next) {
+ if (!q || q->size <= 1) {
return;
}
merge_sort(&(q->head));
- list_ele_t *tmp = q->head;
- while (tmp->next) {
- tmp = tmp->next;
- }
- q->tail = tmp;
+ while (q->tail->next)
+ q->tail = q->tail->next;
}
```
---
###### tags: `linux2021`
- [x] 實做 queue 相關的程式檔案,說明如何逐步達到自動評分程式的要求
- [x] Address Sanitize 修正 qtest
- [ ] 運用 Valgrind 排除 qtest 的記憶體錯誤,並透過 Massif 視覺化
- [ ] 在 qtest 中實作 coroutine
---
## 一、實做 queue 相關的程式檔案,說明如何逐步達到自動評分程式的要求
> [GitHub](https://github.com/Nahemah1022/lab0-c)
### 1. q_new
- 由 `malloc` 取得 `queue_t` 所需的記憶體空間,指向他並初始化 members 為 `NULL`
- 若記憶體配置失敗則 `return NULL`
```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;
}
```
### 2. q_free
- 從 head 開始 `free` node 中 `value` 指向的字串、以及 node 本身
- 最後 `free` queue 本身
```c=
void q_free(queue_t *q)
{
if (q) {
list_ele_t *e = q->head;
while (e) {
free(e->value);
list_ele_t *n = e->next;
free(e);
e = n;
}
free(q);
}
}
```
### 3. q_insert_head
- 新增一個 node 並與原來的 `head` 連接
- 若新增失敗則 `return false`
- 若只有一個 node 則將 `tail` 也指向新 node
```c=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q || !create_node(&newh, s))
return false;
newh->next = q->head;
q->head = newh;
if (!((q->size)++))
q->tail = newh;
return true;
}
```
### 4. q_insert_tail
- 新增一個 node 並與原來的 `tail` 連接
- 若新增失敗則 `return false`
- 若只有一個 node 則將 `head` 也指向新 node
```c=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q || !create_node(&newh, s))
return false;
if ((q->size)++) {
q->tail->next = newh;
} else {
q->head = newh;
}
q->tail = newh;
return true;
}
```
### 5. q_remove_head
- 用 `memcpy` 將 `head->value` 搬移至 `sp`
- 若 `head->value` 的長度小於 `bufsize - 1`,則只複製 `head->value` 的長度到 `sp`
- 否則複製完整 `bufsize - 1` 長度到 `sp`
- 在 `sp` 的最後加上 `\0` 即可
```c=
if (!q || !q->head) {
return false;
}
if (sp) {
size_t minlen = (strlen(q->head->value) < bufsize - 1)
? strlen(q->head->value)
: bufsize - 1;
memcpy(sp, q->head->value, minlen);
*(sp + minlen) = '\0';
}
list_ele_t *n = q->head;
q->head = n->next;
free(n->value);
free(n);
(q->size)--;
return true;
}
```
### 6. q_size
```c=
int q_size(queue_t *q)
{
if (!q) {
return 0;
}
return q->size;
}
```
### 7. q_reverse
```c=
void q_reverse(queue_t *q)
{
if (!q || !q->head || !q->head->next) {
return;
}
q->tail = q->head;
list_ele_t *prev = NULL, *cur = q->head, *next;
while (cur) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
q->head = prev;
}
```
### 8. q_sort
- 利用 merge sort 演算法,找到 linked list index 的中位數,切割為左右兩個區段後再次遞迴
- 將兩區段比較並排序
```c=
void merge_sort(list_ele_t **list)
{
if (!(*list) || !(*list)->next) {
return;
}
list_ele_t *slow = *list, *fast = (*list)->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
list_ele_t *lhs = *list, *rhs = slow->next, *result = NULL;
slow->next = NULL;
merge_sort(&lhs);
merge_sort(&rhs);
list_ele_t **indirect = &result;
// compare and merge list
while (lhs && rhs) {
if (strcasecmp(lhs->value, rhs->value) < 0) {
*indirect = lhs;
lhs = lhs->next;
} else {
*indirect = rhs;
rhs = rhs->next;
}
indirect = &(*indirect)->next;
}
// concatenate remaining nodes
if (lhs) {
*indirect = lhs;
} else if (rhs) {
*indirect = rhs;
}
*list = result;
}
void q_sort(queue_t *q)
{
if (!q || !q->head || !q->head->next) {
return;
}
merge_sort(&(q->head));
list_ele_t *tmp = q->head;
while (tmp->next) {
tmp = tmp->next;
}
q->tail = tmp;
}
```
:::warning
在實做 Mergesort 演算法前,我有嘗試用我寫的 [Non-Recursive Quicksort](https://github.com/Nahemah1022/Linux2021-quizzes/blob/main/quiz1/optimized-non-recur-linkedlist-qsort.c) 方法來實做,但由在 qtest 中的 `trace-15-perf`、`trace-16-perf` 一直無法通過,經過追蹤發現問題如下:
- `trace-15-perf` 的測資接近 `quicksort` 演算法的 worst case,時間複雜度接近 $O(n^2)$
- 為了滿足 worst case 可能會需要的 stack capacity,程式中用來模擬 stack 實做的 `beg[]、end[]` 兩 array 需宣告的大小為 queue 本身的 size,造成記憶體耗盡
由於無法避免 Quicksort 演算法的 worst case,因此我改用 Mergesort 實做即可將時間複雜度控制在 $O(log\ n)$,解決此問題並通過 `qtest` 評分
:::
## 二、修正 Address Sanitize 中的 qtest 錯誤
原錯誤訊息如下:
```shell=
nahemah@nahemah:~/Programs/linux2021/lab0-c$ ./qtest
cmd> help
Commands:
# ... | Display comment
free | Delete queue
help | Show documentation
ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
log file | Copy output to file
new | Create new queue
option [name val] | Display or set options
quit | Exit program
reverse | Reverse queue
rh [str] | Remove from head of queue. Optionally compare to expected value str
rhq | Remove from head of queue without reporting value.
show | Show queue contents
size [n] | Compute queue size n times (default: n == 1)
sort | Sort queue in ascending order
source file | Read commands from source file
time cmd arg ... | Time command execution
Options:
=================================================================
==182478==ERROR: AddressSanitizer: global-buffer-overflow on address 0x560db9011400 at pc 0x560db8ffa90f bp 0x7fffa1567bc0 sp 0x7fffa1567bb0
READ of size 4 at 0x560db9011400 thread T0
#0 0x560db8ffa90e in do_help_cmd /home/nahemah/Programs/linux2021/lab0-c/console.c:307
#1 0x560db8ffaa22 in interpret_cmda /home/nahemah/Programs/linux2021/lab0-c/console.c:221
#2 0x560db8ffb207 in interpret_cmd /home/nahemah/Programs/linux2021/lab0-c/console.c:244
#3 0x560db8ffc94a in run_console /home/nahemah/Programs/linux2021/lab0-c/console.c:660
#4 0x560db8ff9531 in main /home/nahemah/Programs/linux2021/lab0-c/qtest.c:788
#5 0x7f99f727e0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x560db8ff6b8d in _start (/home/nahemah/Programs/linux2021/lab0-c/qtest+0x8b8d)
0x560db9011401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x560db9011400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/nahemah/Programs/linux2021/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:
0x0ac2371fa230: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ac2371fa240: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ac2371fa250: f9 f9 f9 f9 00 00 00 00 04 f9 f9 f9 f9 f9 f9 f9
0x0ac2371fa260: 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9 f9 f9
0x0ac2371fa270: 01 f9 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ac2371fa280:[01]f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ac2371fa290: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ac2371fa2a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac2371fa2b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac2371fa2c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ac2371fa2d0: 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
==182478==ABORTING
```
### 1. 如何追蹤到錯誤
1. 觀察錯誤訊息的 `34` 行發現錯誤偵測點在 `console.c` 中 `do_help_cmd` fucntion 的 `307` 行,該行內容如下,由於錯誤訊息中明確寫出 `do_help_cmd` 而不是 `report` function,因此可以推測錯誤點就在 `report` function 的參數傳遞中,而非 `report` function 的內部
```c=
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp, plist->documentation);
```
2. 因此進一部追蹤參數 `plist` 的由來,來自於同樣在 `console.c` 檔案的 `static` 變數 `param_ptr param_list`
3. 追蹤到 `param_list` 變數是在 `add_param` function 中被賦值,觀察後推測 `add_param` function 的功能是建立一個新的 node `param_ptr next_param` ,將其按照字典順序插入原有的 `param_list` linked list 中,並對該 node 賦值
```c=
void add_param(char *name,
int *valp,
char *documentation,
setter_function setter)
{
param_ptr next_param = param_list;
param_ptr *last_loc = ¶m_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;
}
```
4. 追蹤 `add_param` function 的呼叫點,發現在 `init_cmd` function 中的下方數行,問題源頭即在 `simulation`、`echo` 兩 global 變數在宣告時的型態為 `bool` (1 byte), cast 成 `int` 型態 (4 byte),因此被 Address Sanitizer 判定其跨越原來所屬的記憶體空間 (global-buffer-overflow) 而報錯
```c=
add_param("simulation", (int *) &simulation, "Start/Stop simulation mode",NULL);
add_param("verbose", &verblevel, "Verbosity level", NULL);
add_param("error", &err_limit, "Number of errors until exit", NULL);
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
```
:::warning
**出錯時機:為何到了 `do_help_cmd` function 時才被偵測到**
因為在執行到 `do_help_cmd` function 之前,`simulation` 與 `echo` 兩變數都是用 `int *` 的 pointer 的型態在傳遞變數位址,而在程式中無論型態,每一個 pointer 變數的 size 都是相等的,因此不會有跨越原來所屬的記憶體空間的狀況發生。
但到了 `do_help_cmd` function 中指標初次被 `*plist->valp` 直接造訪到其指向地點,因此一個僅有 1 byte 大小的空間被程式視作 4 byte 大小,跨越原來所屬的記憶體空間才被 Address Sanitizer 偵測出來而報錯。
:::
### 2. 解決方式
解決方式為 ==不要將型態為 `bool` 的變數 cast 成 `int`== 即可,但上方的 params 各有各自的型態,在 C 語言中也不支援類似 OOP 中 function overloading 的實作,因此我認為對程式運行最有利的方法是 **為不同型態的 param 設計不同的 function 來處理**,如下方程式:
```c=
add_bool_param("simulation", &simulation, "Start/Stop simulation mode", NULL);
add_int_param("verbose", &verblevel, "Verbosity level", NULL);
add_int_param("error", &err_limit, "Number of errors until exit", NULL);
add_bool_param("echo", &echo, "Do/don't echo commands", NULL);
```
```c=
/* Add a new parameter */
void add_int_param(char *name,
int *valp,
char *documentation,
setter_function setter)
{
param_ptr next_param = param_list;
param_ptr *last_loc = ¶m_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_int_param");
ele->name = name;
ele->valp = valp;
ele->documentation = documentation;
ele->setter = setter;
ele->next = next_param;
*last_loc = ele;
}
void add_bool_param(char *name,
bool *valp,
char *documentation,
setter_function setter)
{
param_ptr next_param = param_list;
param_ptr *last_loc = ¶m_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_bool_param");
ele->name = name;
ele->valp = (int *) malloc_or_fail(sizeof(int), "add_bool_param");
*(ele->valp) = valp ? 1 : 0;
ele->documentation = documentation;
ele->setter = setter;
ele->next = next_param;
*last_loc = ele;
}
```
:::info
若直接將 `bool` 型態全部改寫成 `int`,也可修正此錯誤,但會有以下兩個缺點:
- 將原本只須佔用 1 byte 的變數擴增為 4 byte,會造成不必要的記憶體浪費
- 其中 `simulation` 是需 extern 至 `qtest.c` 中的變數,若擅自修改其型態可能會連帶造成其他地方的錯誤,且難以追蹤與維護
:::