# 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
```
Sign in with Wallet
Connect another wallet