# 2021q1 Homework1 (lab0)
contributed by < `robertlin0401` >
###### tags: `linux2021`
> [作業說明](https://hackmd.io/@sysprog/linux2021-lab0)
> [github repository](https://github.com/robertlin0401/lab0-c)
---
## queue 實作
### queue 結構
```c
/* Linked list element */
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
/* Queue structure */
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
* `list_ele_t` 用於表示 queue 中的元素，其中：
* `value` 存放字元指標，即 C 語言的字串，此為 queue 中元素的內容
* `next` 為 `list_ele_t` 的指標，指向 queue 中的下一個元素
* `queue_t` 用於表示 queue 本身，其中：
* `head` 為指向 queue 中第一個元素的指標
* `tail` 為指向 queue 中最後一個元素的指標
* `size` 紀錄 queue 中元素個數
* 圖示如下：
### queue operations
* q_new：建立一個空 queue
* q_free：釋放 queue 所占用的記憶體空間，包含其元素內容之字串所使用的空間
* q_insert_head：將元素加入 queue 的前端
* [q_insert_tail](#q_insert_tail)：將元素加入 queue 的尾端
* q_remove_head：將 queue 最前端的元素移除
* [q_size](#q_size)：取得 queue 中的元素個數
* q_reverse：將 queue 中的元素順序反轉
* [q_sort](#q_sort)：將 queue 中的元素以遞增順序進行排序
以下針對部分 operations 之實作進行詳述：
### q_insert_tail
```c=
static inline bool ele_new(char *s, list_ele_t **newh, char **value)
{
*newh = malloc(sizeof(list_ele_t));
*value = strdup(s); /* Allocate space for the string and copy it */
/* If either call to malloc returns NULL */
if (*newh == NULL || *value == NULL) {
if (*newh)
free(*newh);
if (*value)
free(*value);
return false;
}
return true;
}
/*
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
*/
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newh;
char *value;
if (!ele_new(s, &newh, &value))
return false;
/* set up the element and insert at the tail of the queue */
newh->value = value;
newh->next = NULL;
if (q->tail != NULL)
q->tail->next = newh;
else
q->head = newh;
q->tail = newh;
q->size++;
return true;
}
```
* 第 35-39 行程式碼實作出將元素 `newh` 加入 queue 尾端的功能
* 若 `queue_t` 內未包含 `tail` 指標，則該段程式碼須改為以下實作，其中的 while 迴圈將達到 $O(n)$ 的時間複雜度
```c
list_ele_t *tail = q->head;
if (tail != NULL) {
while (tail->next != NULL)
tail = tail->next;
tail->next = newh;
} else
q->head = newh;
```
* 因此，我們需要使用 `tail` 指標增進程式的效能，以達到 $O(1)$ 時間複雜度
### q_size
```c=
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(queue_t *q)
{
if (q == NULL || q->head == NULL)
return 0;
else
return q->size;
}
```
* 若 `queue_t` 內未紀錄 `size` ，則第 10 行程式碼須改為以下實作來計算 size，其中的 while 迴圈將達到 $O(n)$ 的時間複雜度
```c
{
int size = 0;
list_ele_t *ptr = q->head;
while (ptr != NULL) {
size++;
ptr = ptr->next;
}
return size;
}
```
* 因此，我們需要在 `queue_t` 紀錄 `size` 以達到 $O(1)$ 時間複雜度
### q_sort
#### 版本一：遞迴式 quick sort
> 參考 [2021 年春季 Linux 核心設計課程 quiz1 quicksort 實作](https://hackmd.io/@robertlin0401/2021q1-Homework-quiz1#quicksort-%E5%AF%A6%E4%BD%9C)
```c
/*
* Sort elements of linked list in ascending order using recursive quick sort
* @param head - a pointer to the pointer to head of the list
* @param tail - a pointer to the pointer to tail of the list
*/
void q_ele_quicksort(list_ele_t **head, list_ele_t **tail)
{
if (*head == *tail)
return;
list_ele_t *pivot, *left = NULL, *right = NULL;
list_ele_t *target, *left_end = NULL, *right_end = NULL;
pivot = *head;
target = pivot->next;
pivot->next = NULL;
while (target != NULL) {
if (strcmp(target->value, pivot->value) <= 0) {
if (left == NULL)
left = target;
else
left_end->next = target;
left_end = target;
target = target->next;
left_end->next = NULL;
} else {
if (right == NULL)
right = target;
else
right_end->next = target;
right_end = target;
target = target->next;
right_end->next = NULL;
}
}
q_ele_quicksort(&left, &left_end);
q_ele_quicksort(&right, &right_end);
if (left != NULL) {
*head = left;
left_end->next = pivot;
} else {
*head = pivot;
}
pivot->next = right;
*tail = (right_end == NULL) ? pivot : right_end;
}
```
* 問題描述：在 trace-15 測資發生 TLE（Time Limit Exceeded）錯誤
* 推測原因
* 觀察 trace-15 測資可發現，欲排序的 queue 中元素為 [a a a ... a b b b ... b]（a、b 各 1000000 個），對於 quick sort 而言，此為時間複雜度分析上的 worst case
* 在此 quick sort 實作中，此測資的 partition 如下
```graphviz
digraph {
node1 [shape=none; label=<
<table>
<tr>
<td
border="0"
colspan="1"
port="left"
></td>
<td
border="0"
colspan="1"
>a a a ... a b b b ... b </td>
<td
border="0"
colspan="1"
port="right"
></td>
</tr>
<tr><td
border="0"
colspan="3"
> （a is pivot）</td></tr>
</table>>
];
node2 [shape=none; label=<
<table>
<tr>
<td
border="0"
colspan="1"
port="left"
></td>
<td
border="0"
colspan="1"
>a a a ... a </td>
<td
border="0"
colspan="1"
port="right"
></td>
</tr>
<tr><td
border="0"
colspan="3"
> （a is pivot）</td></tr>
</table>>
];
node3 [shape=none; label=<
<table>
<tr>
<td
border="0"
colspan="1"
port="left"
></td>
<td
border="0"
colspan="1"
>b b b ... b </td>
<td
border="0"
colspan="1"
port="right"
></td>
</tr>
<tr><td
border="0"
colspan="3"
> （b is pivot）</td></tr>
</table>>
];
node4 [shape=none; label=<
<table>
<tr>
<td
border="0"
colspan="1"
port="left"
></td>
<td
border="0"
colspan="1"
>a a a ... a </td>
<td
border="0"
colspan="1"
port="right"
></td>
</tr>
<tr><td
border="0"
colspan="3"
> （a is pivot）</td></tr>
</table>>
];
node5 [shape=none; label=<
<table border="0">
<tr><td>NULL</td></tr>
</table>>
];
node6 [shape=none; label=<
<table>
<tr>
<td
border="0"
colspan="1"
port="left"
></td>
<td
border="0"
colspan="1"
>b b b ... b </td>
<td
border="0"
colspan="1"
port="right"
></td>
</tr>
<tr><td
border="0"
colspan="3"
> （b is pivot）</td></tr>
</table>>
];
node7 [shape=none; label=<
<table border="0">
<tr><td>NULL</td></tr>
</table>>
];
node8 [shape=none; label=<
<table border="0">
<tr><td><b>.<br/>.<br/>.</b></td></tr>
</table>>
];
node9 [shape=none; label=<
<table border="0">
<tr><td>NULL</td></tr>
</table>>
];
node12 [shape=none; label=<
<table border="0">
<tr><td><b>.<br/>.<br/>.</b></td></tr>
</table>>
];
node13 [shape=none; label=<
<table border="0">
<tr><td>NULL</td></tr>
</table>>
];
node_invis1 [shape=none; label=""];
node_invis2 [shape=none; label=""];
node_invis3 [shape=none; label=""];
node_invis4 [shape=none; label=""];
node_invis5 [shape=none; label=""];
node1 -> node_invis1 [style=invis];
node2 -> node_invis2 [style=invis];
node3 -> node_invis3 [style=invis];
node4 -> node_invis4 [style=invis];
node6 -> node_invis5 [style=invis];
node1:left -> node2;
node1:right -> node3;
node2:left -> node4;
node2:right -> node5;
node3:left -> node6;
node3:right -> node7;
node4:left -> node8;
node4:right -> node9;
node6:left -> node12;
node6:right -> node13;
}
```
* 時間複雜度分析
* 令 $n$ 為輸入 queue 的元素個數
* 左 partition 遞迴的時間複雜度為 $O(\dfrac{n}{2}-1)+O(\dfrac{n}{2}-2)+\ ...\ +O(1)=O(n^{2})$，右 partition 則為 $O(\dfrac{n}{2})+O(\dfrac{n}{2}-1)+\ ...\ +O(1)=O(n^{2})$
* 總時間複雜度 $T(n)=O(n^{2})+O(n^{2})+cn$，$c$ 為常數，故 $T(n)=O(n^{2})$，確實為 quick sort 之 worst case 的時間複雜度
* 實際遞迴呼叫行為分析
* 由圖示可推知，左 partition 遞迴呼叫深度為 999999，右 partition 則為 1000000，最大遞迴深度達到 $\dfrac{n}{2}$
* 每次遞迴需要針對其左、右兩 partition 分別呼叫，所以左、右兩 partition（最上層的）總共向下遞迴呼叫了 $999999\times2\ +\ 1000000\times2\ =\ 3999998$ 次，加上最初針對左、右兩 partition 的遞迴呼叫，故總遞迴呼叫次數為 $4000000$ 次，甚至達到了 $n$ 的兩倍
* 綜上分析，在此情況下，quick sort 是極度費時且浪費 stack 空間的方法，故不適合應用於此
* <span id="radix_sort_discussion">如何解決問題</span>
* 根據上述分析可知，我們必須選擇其他排序演算法，以避免在遇到 worst case 的情形下，會耗費特別多資源的問題，意即需要選擇 worst case 之時間複雜度與 best case 是相同的演算法，常見的包含 [merge sort](https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F)、[heap sort](https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F) 與 [radix sort](https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F)
* 接著，我們從輸入字串進行分析，來決定使用何種排序法
* 首先，可以從 qtest.c 觀察到輸入字串僅由小寫的 a-z 組成，共 26 個字母
```c=66
static const char charset[] = "abcdefghijklmnopqrstuvwxyz";
```
* 字串的排序邏輯為從第一個字元開始比較，若可以比較出大小，則該字串的大小便以此為依據，反之則比較第二個字元，以此類推
* 結合上述兩點，我們可以使用 radix sort 的觀念來實作排序
1. 準備 27 個 buckets，分別表示 26 個字母以及終止字元 '\0'
2. 從第一個字元開始，每回合取一個字元為依據，依此將字串放入所屬 bucket 中
3. 檢查各 bucket（除 '\0' 以外），若存在多於一個字串則針對該 bucket 內容進行下一回合的 radix sort
4. 最後，以 '\0' 的 bucket 最優先，接著按照 a-z 的順序，將字串以 FIFO 順序自 buckets 中取出，取出後的結果便會是排序完成的結果
* 時間分析
1. 由於 buckets 數量為一常數，故此排序之時間複雜度僅與需比較之最大字串長度（令 $k$）與輸入字串個數（令 $n$）相關
2. 又因字串之比較，若發現一字元可比較出大小，則無需比較剩餘字元，故僅在 $k \geq n$ 且前 $k-1$ 個字元皆相同的情況下，其時間複雜度會達到 $O(n^{2})$ 以上，其餘情況下皆為 $O(n)$ 的時間複雜度
:::info
就實務上而言，時間複雜度達到 $O(n^{2})$ 以上的情形是會發生的，但要在 $n$ 為足夠大的數時，才會構成費時過多的問題，然而實際應用中並不會發生，原因如下：
1. 若字串用作雜湊值，則因為 $k$ 位數的 26 個字母之排列組合，共有 $26^{k}$ 種可能性，因此 $k$ 取值無需過大即足夠，相對地，在發生時間複雜度達到 $O(n^{2})$ 以上的情形時，$n$ 也不會很大
2. 若字串為有意義之單詞，則其長度本就受到限制，故同理，$n$ 也不會很大
:::
#### 版本二：遞迴式 radix sort
```c
/*
* Sort elements of linked list in ascending order using recursive radix sort
* @param head - a pointer to the pointer to head of the list
* @param tail - a pointer to the pointer to tail of the list
* @param index - the index of character in string now checking
*/
void q_ele_radixsort(list_ele_t **head, list_ele_t **tail, int index)
{
if (*head == *tail)
return;
list_ele_t *bucket_head[27], *bucket_tail[27];
list_ele_t *target = *head;
for (int iter = 0; iter < 27; ++iter)
bucket_head[iter] = bucket_tail[iter] = NULL;
while (target != NULL) {
int charCode = (int)(target->value[index]);
charCode = (charCode == 0) ? 0 : charCode - 'a' + 1;
if (bucket_head[charCode] == NULL)
bucket_head[charCode] = target;
else
bucket_tail[charCode]->next = target;
bucket_tail[charCode] = target;
target = target->next;
bucket_tail[charCode]->next = NULL;
}
for (int iter = 1; iter < 27; ++iter) {
if (bucket_head[iter] != bucket_tail[iter])
q_ele_radixsort(&bucket_head[iter], &bucket_tail[iter], index + 1);
}
bool isHead = true;
for (int iter = 0; iter < 27; ++iter) {
if (bucket_head[iter] != NULL) {
if (isHead) {
*head = bucket_head[iter];
isHead = false;
} else {
(*tail)->next = bucket_head[iter];
}
*tail = bucket_tail[iter];
}
}
}
```
* 基於上述 [radix sort 討論](#radix_sort_discussion)實作出此 function，經測試後可符合此問題之時間效率需求
* 是否需更改為非遞迴版本？
* 已知遞迴呼叫會花費較多的資源，故在效率議題上可以考慮將其改為非遞迴版本
* 然而，此實作中之遞迴呼叫次數存在限制，以下說明
* 每回合之遞迴呼叫最多會有 26 次，即針對 a-z 共 26 個 buckets
* 每次遞迴呼叫之最大深度即為需比較之最大字串長度（令 $k$）少 1，且上述討論已得到 $k$ 為有限數之結論
* 故最大遞迴總次數約為 $26^{k-1}$ 次，其發生條件為資料個數達到 $c\cdot 26^{k-1}$ 個，$1\lt c\leq 26$，且每層遞迴中，各 bucket 內的資料個數需相近
* 換言之，此情形之排序意義相似於：排序以 26 個字母任意排列的長度 k 之所有可能字串。而實務上此情況發生時，k 並不會是很大的數
* 綜上所述，在一般情形下並不至於發生如 stack overflow 等問題，因此我暫時選擇使用遞迴版本
#### 版本三：非遞迴式 merge sort
> 參考：`bobhsiao0306` 同學的[開發紀錄](https://hackmd.io/@Ow6SGrn-Tdetp7wHt4Npcg/HkTk1rUf_)
```c
/*
* Sort elements of linked list in ascending order using non-recursive merge sort
* @param q - a pointer to the queue
*/
void q_ele_mergesort(queue_t *q)
{
for (int i = 1; i < q->size; i *= 2) {
list_ele_t *ptr = q->head;
list_ele_t *buf = q->head;
bool init = true;
while (ptr != NULL) {
list_ele_t *a = ptr, *a_tail = NULL;
for (int j = 0; j < i - 1; j++) {
if (ptr->next == NULL)
break;
ptr = ptr->next;
}
a_tail = ptr;
ptr = ptr->next;
list_ele_t *b = ptr, *b_tail = NULL;
if (ptr != NULL) {
for (int j = 0; j < i - 1; j++) {
if (ptr->next == NULL)
break;
ptr = ptr->next;
}
b_tail = ptr;
ptr = ptr->next;
}
int a_count = 0, b_count = 0;
while (a_count < i && b_count < i && a != NULL && b != NULL) {
if (strcmp(a->value, b->value) <= 0) {
if (init) {
q->head = a;
init = false;
} else {
buf->next = a;
}
buf = a;
a = a->next;
a_count++;
} else {
if (init) {
q->head = b;
init = false;
} else {
buf->next = b;
}
buf = b;
b = b->next;
b_count++;
}
}
if (a_count == i) {
if (b != NULL) {
buf->next = b;
buf = b_tail;
q->tail = b_tail;
q->tail->next = NULL;
}
} else {
if (a != NULL) {
buf->next = a;
buf = a_tail;
q->tail = a_tail;
q->tail->next = NULL;
}
}
}
}
}
```
* 觀察其他人的[開發紀錄](https://hackmd.io/@sysprog/linux2021-homework1)可以發現大部分人是使用 merge sort 進行實作，以上取自 `bobhsiao0306` 同學的非遞迴式實作並進行簡單改良
* 接著，我們可以從各項議題上與版本二的 radix sort 相比較
* TODO
---
## 修正 `qtest` 之錯誤
### 運用 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)
* 問題描述：開啟 Address Sanitizer 後，先執行 `qtest`，再於命令提示列輸入 `help` 命令，會產生 global buffer overflow
```shell
$ make SANITIZER=1
$ ./qtest
cmd> help
```
* 何謂 global buffer overflow？
* 針對全域資料的存取超出合法存取範圍之問題，可能導致未定義行為、程式崩潰，甚至有資訊安全之疑慮
> 參考：[global buffer overflow](https://blog.gypsyengineer.com/en/security/global-buffer-overflows.html)
* 觀察問題來源
* 觀察藍字的錯誤訊息可發現，執行過程中自記憶體位址 `0x55e5e09a5400` 存取了 4 個位元組
* 觀察綠字的錯誤訊息可知在該記憶體位址的為一全域變數 `echo`，其定義之大小為 1 個位元組，因此存取記憶體位址 `0x55e5e09a5401` 以右的位元組之行為為 overflow，並且在 `console.c` 的第 59 行可以找到該變數的宣告，其宣告為一 `bool` 型態的變數
* 接著從其 traceback 去檢查其使用問題所在
* traceback #0 顯示在 `do_help_cmd` 第 307 行存取 `param_list` 指向的物件 — `plist` 之成員時發生錯誤
```c
param_ptr plist = param_list;
report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
plist->documentation);
```
* 檢查 `param_list` 與 `echo` 之關聯：`echo` 的指標在 `init_cmd` 中作為參數，強制轉型為整數指標傳入 `add_param`，並在 `add_param` 中賦值給 `param_list` 中物件之成員 `valp` 使用
```c
void add_cmd()
{
...
add_param("echo", (int *) &echo, "Do/don't echo commands", NULL);
...
}
void add_param(char *name, int *valp, ...)
{
...
param_ptr ele = (param_ptr)malloc_or_fail(sizeof(param_ele), "add_param");
ele->valp = valp;
...
}
```
* 解決方法
* 既然需要將其作為 4 個位元組的變數使用，則概念上只需將 `bool` 型態進行位元延伸，使其成為 4 個位元組的整數型態，並且以整數 0 或 1 表示 `false` 或 `true`
* 所以實作上將 `echo` 改成整數宣告，即可解決問題
* 此外，全域變數 `simulation` 也有同樣問題，同理，也可以用此方法解決
:::warning
:bell: `simulation` 為一 [`extern`](https://en.wikipedia.org/wiki/External_variable#Definition,_declaration_and_the_extern_keyword) 變數，故 header file 之宣告與 source file 之定義皆須做修改
:::
### 運用 [Valgrind](https://valgrind.org/)
* 問題描述：使用 valgrind 進行執行時期的記憶體檢測可以發現有部分配置的記憶體空間未被釋放，以下為 trace-01 之執行的錯誤訊息
```shell
$ make
$ valgrind ./qtest -v 1 -f traces/trace-01-ops.cmd
```
:::warning
:bell: 為了更有彈性的進行測試，我嘗試手動輸入測資，卻發現此方法不會觸發錯誤，故能夠推斷此錯誤產生的原因與讀檔進行輸入相關，此資訊應該會在後續分析有所幫助
:::
* 觀察錯誤訊息可以發現，未被釋放的記憶體是在 `linenoiseHistoryAdd` 函式中（分別在 linenoise.c:1224 與 linenoise.c:1236）被配置的，其用途為記錄命令列的輸入歷史
* 配置字元指標的空間，用於指向各條歷史紀錄
```c=1224
history = malloc(sizeof(char *) * history_max_len);
```
* 使用 `strdup` 複製字串，即各條命令本身內容
```c=1236
linecopy = strdup(line);
```
* 後續將複製的字串存入歷史紀錄中（交由前面配置的指標所指）
```c=1244
history[history_len] = linecopy;
```
* 接著，由於前面已經發現僅在讀檔進行輸入時未將此記憶體空間釋放，故必存在用於釋放歷史紀錄的記憶體空間的程式片段，找到它並進行追蹤
* 記憶體空間會在 `freeHistory` 函式中進行釋放
```c=1190
static void freeHistory(void)
{
if (history) {
int j;
for (j = 0; j < history_len; j++)
free(history[j]);
free(history);
}
}
```
* `freeHistory` 僅在 `linenoiseAtExit` 函式中被呼叫
```c=1202
static void linenoiseAtExit(void)
{
disableRawMode(STDIN_FILENO);
freeHistory();
}
```
* `linenoiseAtExit` 僅在首次呼叫 `enableRawMode` 函式時會被 `atexit` 註冊，若被註冊則當程序正常終止時便會執行該函式。`enableRawMode` 函式之目的為開啟 raw mode，以改變特定按鍵輸入的行為，例如：改變 tab 鍵的行為以此實作命令自動補齊的功能，關於 raw mode 在此段落不進行深入討論，詳見 [linenoise 運作原理](#linenoise-運作原理) 段落
```c=237
static int enableRawMode(int fd)
{
struct termios raw;
if (!isatty(STDIN_FILENO))
goto fatal;
if (!atexit_registered) {
atexit(linenoiseAtExit);
atexit_registered = 1;
}
...
}
```
> 參考 [atexit man page](https://man7.org/linux/man-pages/man3/atexit.3.html)
* 由於讀檔進行輸入不需要切換成 raw mode（因為輸入來自檔案，故不需要改變按鍵輸入的行為），故不會呼叫到 `enableRawMode` 函式，因此歷史紀錄的記憶體空間不會被釋放
* 解決方法
* 找到判別檔案輸入或命令列輸入的分支處，其位於 console.c 的 `run_console` 函式中，處理檔案輸入的部分為 `else` block 中的程式碼
```c=657
if (!has_infile) {
char *cmdline;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
```
* 向下追蹤 `cmd_done` 與 `cmd_select` 的內容卻發現其中並無操作歷史紀錄的程式碼，故回頭檢查檔案輸入前後的歷史紀錄，發現檔案輸入的內容確實沒有被記錄，未被釋放的空間所存放的歷史紀錄是在執行 `run_console` 以前就載入完成的過往執行的紀錄
* 又因為檔案輸入的內容並不會記錄，故當使用檔案輸入時其實不需要載入過往的紀錄，因此找到載入歷史紀錄的函式呼叫，並加入讀檔與否的判斷式即可修正此問題，該段程式碼位於 qtest.c 的 `main` 函式中
```diff=777
- linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
+ if (!infile_name)
+ linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```
---
## linenoise 運作原理
TODO
<!--
history：
* 20210415 15:57 - 暫置，先進行其他進度
-->
Sign in with Wallet
Connect another wallet