# 2022q1 Homework1 (lab0)
contributed by < [2020leon](https://github.com/2020leon) >
## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
- 參閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/git-with-github) ^附教學影片^
- [x] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
- 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
- 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [x] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [x] 在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令
- 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2022-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
- 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 觸發錯誤，應予以排除
- 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)
- 研讀論文〈[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) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案;
- [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
## 環境
```shell
$ uname -a
Linux leon-ubuntu-20 5.13.0-28-generic #31~20.04.1-Ubuntu SMP Wed Jan 19 14:08:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
cc (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.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 36 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 58
Model name: Intel(R) Core(TM) i5-3570 CPU @ 3.40GHz
Stepping: 9
CPU MHz: 2100.000
CPU max MHz: 3800.0000
CPU min MHz: 1600.0000
BogoMIPS: 6784.49
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-3
```
## 開發紀錄
### 事先準備
1. 將 [sysprog21/lab0-c](https://github.com/sysprog21/lab0-c) fork 至自己的 GitHub 帳號下並 pull 至本地端
2. **開啟 [GitHub Actions](https://github.com/features/actions) 功能**
若未開啟 GitHub Actions 則在嘗試 `make` 時會出現以下輸出：
```shell
$ make
Fatal: GitHub Actions MUST be activated.
Check this article: https://docs.github.com/en/actions/managing-workflow-runs/disabling-and-enabling-a-workflow
Then, execute 'make' again.
make: *** [Makefile:34: .git/hooks/applied] Error 1
```
依據指示開啟後則會有以下輸出（Git hooks 亦會同時被安裝）：
```shell
$ make
GitHub Actions has been activated
Git hooks are installed successfully.
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC linenoise.o
LD qtest
```
### 實做佇列（ `queue.c` ）
#### `q_new`
1. 藉由 `malloc` 分配記憶體空間，並確認 `malloc` 的回傳值
2. 藉 `INIT_LIST_HEAD` 初始化 `struct list_head` 物件的成員
```c
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
struct list_head *q_new()
{
/* Malloc queue. */
struct list_head *const q = malloc(sizeof(struct list_head));
/* Initialize queue if `q` is not NULL. */
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
後發現有更簡潔的寫法。
```c
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
struct list_head *q_new()
{
/* Malloc queue. */
struct list_head *const q = malloc(sizeof(struct list_head));
/* Initialize queue if `q` is not NULL. */
if (q)
INIT_LIST_HEAD(q);
return q;
}
```
#### `q_free`
1. 遍歷佇列，將屬於佇列的 element 提出
2. 藉 `q_release_element` 釋放空間
3. 釋放變數 `l` 所指向的空間
```c
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
element_t *element;
if (!l)
return;
for (struct list_head *i = l->next, *next; i != l; i = next) {
element = list_entry(i, element_t, list);
/* `next` as a temporary variable to save the next `list_head` */
next = element->list.next;
q_release_element(element);
}
free(l);
}
```
:::info
注：需注意的是，要在記憶體空間被釋放前取得所指向的下一個 `list_head`
:::
> 善用 `list_for_each` 一類的巨集來改寫程式碼
> :notes: jserv
隨後利用 `list_for_each_entry_safe` 巨集改寫程式碼，結果精簡許多。
```c
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
element_t *i, *tmp;
if (!l)
return;
list_for_each_entry_safe (i, tmp, l, list)
q_release_element(i);
free(l);
}
```
#### `q_size`
`q_size` 的實做可見於 [K01: lab0](https://hackmd.io/@sysprog/linux2022-lab0) 中。
1. 遍歷佇列並累計其 element 的數量
```c
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(struct list_head *head)
{
int len = 0;
struct list_head *li;
if (!head || list_empty(head))
return 0;
list_for_each (li, head)
len++;
return len;
}
```
#### `q_insert_head`
在實做 `q_insert_head` 時，注意到下方亦有功能類似的函式（即 [`q_insert_tail`](#q_insert_tail)），因此在實做時，將其共同部份提取出來，待未來供 `q_insert_tail` 使用。
提取出來的函式名為 `alloc_helper` ，實做如下：
:::warning
注： `ele_alloc_helper` 原先的名稱為 `_new_element` ，為求函式名稱簡潔明瞭而改成 `ele_alloc_helper` 。
> 或直接寫 `alloc_helper`，因為是採 static 宣告的函式，簡潔清晰
> :notes: jserv
後又改為 `alloc_helper` 以求簡潔清晰。
:::
```c
/*
* Create an element with string initialized.
* Return NULL if could not allocate space or `s` is NULL.
*/
static element_t *alloc_helper(const char *s)
{
element_t *element;
size_t slen;
if (!s)
return NULL;
element = malloc(sizeof(element_t));
if (!element)
return NULL;
INIT_LIST_HEAD(&element->list);
slen = strlen(s) + 1;
element->value = malloc(slen);
if (!element->value) {
free(element);
return NULL;
}
memcpy(element->value, s, slen);
return element;
}
```
藉由上方的函式，可大幅簡化 `q_insert_head` 的實做程式碼。
1. 由 `alloc_helper` 分配並初始化 `element_t` 結構
2. 插入佇列的頭端
```c
/*
* Attempt to insert element at head 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.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_head(struct list_head *head, char *s)
{
element_t *element;
if (!head)
return false;
element = alloc_helper(s);
if (!element)
return false;
list_add(&element->list, head);
return true;
}
```
#### `q_insert_tail`
1. 由 `alloc_helper` 分配並初始化 `element_t` 結構
2. 插入佇列的尾端
```c
/*
* 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.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *element;
if (!head)
return false;
element = alloc_helper(s);
if (!element)
return false;
list_add_tail(&element->list, head);
return true;
}
```
#### `q_swap`
依據 `struct list_head` 的特性，可以寫出簡短的程式碼。其原理便是將索引為偶數的節點之 `next` 移至其前方，直到僅剩一個節點或全部的節點都交換完為止。
:::info
注：索引值從零開始
:::
```c
/*
* Attempt to swap every two adjacent nodes.
*/
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
for (struct list_head *i = head->next; i != head && i->next != head;
i = i->next)
list_move_tail(i->next, i);
}
```
#### `q_reverse`
依據 `struct list_head` 的特性，亦可寫出簡短的程式碼。原理便是每次將節點從佇列的最尾端移至 `i` 的前方，而 `i` 總是指向前一步被移動的節點。
```c
/*
* Reverse elements in queue
* No effect if q is NULL or empty
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.
*/
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
for (struct list_head *i = head; i->next != head->prev; i = i->next)
list_move(head->prev, i);
}
```
#### `q_remove_head`
剩下尚未實做的函式（即 `q_remove_head` 、 `q_remove_tail` 、 `q_delete_dup` 、 `q_delete_mid` ）大多需要從佇列中移除節點，因此將其共同部份提取出來，待未來供以上函式使用。
提取出來的函式名為 `my_q_remove` ，實做如下：
```c
/*
* Attempt to remove node from a queue.
* Return target element.
* Return NULL if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
*/
static element_t *my_q_remove(struct list_head *node, char *sp, size_t bufsize)
{
element_t *const element = list_entry(node, element_t, list);
list_del_init(node);
if (sp && bufsize) {
size_t min = strlen(element->value) + 1;
min = min > bufsize ? bufsize : min;
memcpy(sp, element->value, min);
sp[min - 1] = '\0';
}
return element;
}
```
在 `my_q_remove` 中，亦提供 `sp` 、 `bufsize` 等參數可供 `q_remove_head` 、 `q_remove_tail` 等需將字串複製至 `sp` 所指向位置的函式使用。值得注意的地方為 `min` 變數，其確保能以最少的複製來達成複製字串的目的。
藉由上方的函式，可大幅簡化 `q_remove_head` 的實做程式碼，只需判斷佇列是否為空即可。
```c
/*
* Attempt to remove element from head of queue.
* Return target element.
* Return NULL if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
*
* NOTE: "remove" is different from "delete"
* The space used by the list element and the string should not be freed.
* The only thing "remove" need to do is unlink it.
*
* REF:
* https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
*/
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
return !head || list_empty(head) ? NULL
: my_q_remove(head->next, sp, bufsize);
}
```
#### `q_remove_tail`
`q_remove_tail` 的實做與 `q_remove_head` 大同小異，只差所移除的節點不同。
```c
/*
* Attempt to remove element from tail of queue.
* Other attribute is as same as q_remove_head.
*/
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
return !head || list_empty(head) ? NULL
: my_q_remove(head->prev, sp, bufsize);
}
```
#### `q_delete_dup`
1. 比較相鄰的節點字串
2. 若相鄰的節點字串相同，將節點自佇列中移除並釋放之
```c
/*
* Delete all nodes that have duplicate string,
* leaving only distinct strings from the original list.
* Return true if successful.
* Return false if list is NULL.
*
* Note: this function always be called after sorting, in other words,
* list is guaranteed to be sorted in ascending order.
*/
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
struct list_head *i, *j;
if (!head)
return false;
i = head->next;
for (j = i->next; j != head; j = j->next) {
if (strcmp(((element_t *) list_entry(i, element_t, list))->value,
((element_t *) list_entry(j, element_t, list))->value) ==
0) {
// Remove j from the queue and release it
q_release_element(my_q_remove(j, NULL, 0));
// Assign i to j after j is deleted
// For the next loop, j == i->next
j = i;
} else {
i = i->next;
}
}
return true;
}
```
:::warning
注：由於 `aspell` 工具會阻擋含有「 dup 」單字的 commit message ，因此若 commit message 中有提及該函式，需在 `aspell-pws` 檔案中加入「 dup 」單字。
:::
後又仔細研讀 [LeetCode 82](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 所提供的例子及 [#73](https://github.com/sysprog21/lab0-c/pull/73) 可知以上實做不符要求。
根據以上二者， list `[a, a, b]` 在經過本函式後應為 `[b]` 而非 `[a, b]` 。修改起來很簡單，僅需再加數行即可。
```diff
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
struct list_head *i, *j;
+ bool is_i_dup = false;
if (!head)
return false;
i = head->next;
for (j = i->next; j != head; j = j->next) {
if (strcmp(((element_t *) list_entry(i, element_t, list))->value,
((element_t *) list_entry(j, element_t, list))->value) ==
0) {
+ is_i_dup = true;
// Remove j from the queue and release it
q_release_element(my_q_remove(j, NULL, 0));
// Assign i to j after j is deleted
// For the next loop, j == i->next
j = i;
} else {
i = i->next;
+ // Delete the last node whose string was duplicated
+ if (is_i_dup) {
+ q_release_element(my_q_remove(i->prev, NULL, 0));
+ is_i_dup = false;
+ }
}
}
return true;
}
```
上述改動可通過測資，但並非正確實做。其未考慮到如 `[a, b, b]` 之例，上述函式會錯誤地將 list 改為 `[a, b]` ，而實應為 `[a]` 。因此做出最後改動。
```diff
bool q_delete_dup(struct list_head *head)
{
...
+ if (is_i_dup)
+ q_release_element(my_q_remove(i, NULL, 0));
return true;
}
```
隨後又發現 `container_of` 巨集會返回其相關型別的指標型別，因此將類似 `((element_t *) list_entry(i, element_t, list))->value` 的語句改為 `list_entry(i, element_t, list)->value` ，下方 [`q_sort`](#q_sort) 亦同不再贅述。
#### `q_delete_mid`
`q_delete_mid` 及 `q_sort` 均需將中間值提出，將提取中間值作為一個函式，待未來供 `q_sort` 使用。
提取出來的函式名為 `get_mid_node` ，實做如下：
```c
/*
* Get the middle node in list.
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six element, the third member should be return.
* Return the middle node.
*
* Note: `head` must not be empty
*/
static struct list_head *get_mid_node(const struct list_head *head)
{
struct list_head *i = head->next, *j = head->prev;
while (i != j && i->next != j)
i = i->next, j = j->prev;
return j;
}
```
藉由上方的函式，可大幅簡化 `q_delete_mid` 的實做程式碼。
```c
/*
* Delete the middle node in list.
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six element, the third member should be return.
* Return true if successful.
* Return false if list is NULL or empty.
*/
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head))
return false;
q_release_element(my_q_remove(get_mid_node(head), NULL, 0));
return true;
}
```
#### `q_sort`
利用「合併排序」實作排序。
1. 將佇列分二半
2. 分二半的佇列各自排序
3. 將被分出去的另一半逐項插回原佇列
```c
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(struct list_head *head)
{
// Merge sort
struct list_head *i, *j, *tmp;
LIST_HEAD(new_head);
if (!head || list_empty(head) || list_is_singular(head))
return;
// Split the list
list_cut_position(&new_head, head, get_mid_node(head)->prev);
// Call recursively
q_sort(&new_head);
q_sort(head);
// Insert nodes in new_head to head
i = head->next;
for (j = new_head.next; !list_empty(&new_head); j = tmp) {
while (i != head &&
strcmp(((element_t *) list_entry(i, element_t, list))->value,
((element_t *) list_entry(j, element_t, list))->value) <
0) {
i = i->next;
}
if (i == head) {
// All of the remaining elements in new_head is greater than i
list_splice_tail_init(&new_head, i);
} else {
tmp = j->next;
list_del_init(j);
list_add_tail(j, i);
// i->prev == j
}
}
}
```
#### 引入 [`lib/list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
引入該檔的作法參考 [SmallHanley](https://hackmd.io/@SmallHanley/linux2022-lab0) 。
首先在 `qtest.c` 新增一個 option 名為「 sort 」。新增選項的目的為待未來測試時能夠在不調整程式碼重新編譯的情況下快速切換自行實做的排序法及 `lib/list_sort.c` 中的排序函式。
```diff
...
+static int kernelsort = 0;
...
static void console_init()
{
...
+ add_param("sort", &kernelsort, "Enable/disable kernel version sort", NULL);
...
}
```
接著直接至 linux 核心複製 `lib/list_sort.c` 及 `include/linux/list_sort.h` 至 `lab0-c` 專案下並加以修改。需修改的地方如下。
1. 所引入的標頭檔
- 因 `lib/list_sort.c` 所引入的標頭檔均為 linux 核心相關的的標頭檔，若欲在 user mode 運作需修改相關標頭
2. `likely(x)` 及 `unlikely(x)` 巨集
- 上述二巨集定義於 `include/linux/compiler.h` 中，其功能為藉由搬動程式碼使更為常用的區塊能夠相鄰，使 cache hit rate 上升
3. 使 `cppcheck` 忽略 `merge` 函式中的 `struct list_head *head, **tail = &head;` 「 unassignedVariable 」錯誤
- 事實上 `head` 會在往後的迴圈中藉 `tail` 賦值，但 `cppcheck` 未能偵測，藉 `// cppcheck-suppress unassignedVariable` 抑制錯誤
4. 型別 `u8` 更為 `uint8_t`
- `u8` 為定義於 `include/linux/types.h` 的資料型態，藉引入 `stdint.h` 改為 `uint8_t`
複製後，記得修改 `Makefile` 。
`list_sort.c` 中的 `list_sort` 函式原型可簡化如下。
```c
typedef int (*list_cmp_func_t)(void *,
const struct list_head *,
const struct list_head *);
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
```
分析其函式原型，可知其須傳入三個參數。
1. `priv` ：為未來會傳入 `cmp` 的第一個參數，可協助 `cmp` 排序
2. `head` ：欲排序的 list
3. `cmp` ：比較函式，回傳 `int` 型別
在此先實做比較函式。
```c
static int list_cmp(void *_,
const struct list_head *a,
const struct list_head *b)
{
return strcmp(list_entry(a, element_t, list)->value,
list_entry(b, element_t, list)->value);
}
```
再修改 `do_sort` 函式即完成。
```diff
bool do_sort(int argc, char *argv[])
{
...
set_noallocate_mode(true);
- if (exception_setup(true))
+ if (exception_setup(true)) {
+ if (kernelsort)
+ list_sort(NULL, l_meta.l, list_cmp);
+ else
q_sort(l_meta.l);
+ }
exception_cancel();
set_noallocate_mode(false);
...
}
```
#### 比較效能落差
嘗試新增批次命令檔 `traces/trace-sort.cmd` 以達自動化測試。
```txt
option echo 0
option verbose 1
# user-version sort
option sort 0
new
it RAND 262144
time sort
# kernel-version sort
option sort 1
new
it RAND 262144
time sort
```
其中一次結果如下：
```shell
$ ./qtest -f traces/trace-sort.cmd
cmd> option echo 0
# user-version sort
Delta time = 0.148
# kernel-version sort
Delta time = 0.204
```
原因自己的合併排序較核心的排序法快而竊喜，然在修改 `traces/trace-sort.cmd` 後再執行一次。
```shell
$ ./qtest -f traces/trace-sort.cmd
cmd> option echo 0
# user-version sort
Delta time = 0.146
Delta time = 0.244
# kernel-version sort
Delta time = 0.213
Delta time = 0.215
```
由上可發現，第一次排序會**莫名**快，目前仍未找出原因。
因此在前方加入一假排序。
```shell
./qtest -f traces/trace-sort.cmd
cmd> option echo 0
# dummy sort
Delta time = 0.156
# user-version sort
Delta time = 0.250
Delta time = 0.262
# kernel-version sort
Delta time = 0.214
Delta time = 0.217
```
最後使各排序法排序已排序的 list ，並使各排序法排序五次。
```shell
$ ./qtest -f traces/trace-sort.cmd
cmd> option echo 0
# dummy sort
Delta time = 0.156
# user-version sort
Delta time = 0.250
Delta time = 0.262
Delta time = 0.261
Delta time = 0.260
Delta time = 0.261
# sort sorted list
Delta time = 0.201
# kernel-version sort
Delta time = 0.214
Delta time = 0.217
Delta time = 0.218
Delta time = 0.216
Delta time = 0.216
# sort sorted list
Delta time = 0.164
```
結果發現自己實做的排序較核心版本的排序慢約 19.7% 。對已排序的 list 做排序則慢約 22.6% 。
### 實做洗牌（ `shuffle` ）
依據作業要求，需根據 Fisher-Yates shuffle 演算法，對佇列中所有節點進行洗牌，因此在 `qtest.c` 中以名為 `q_shuffle` 的函式實做洗牌。
```c
static void q_shuffle(struct list_head *head)
{
// Fisher-Yates shuffle
int size;
if (!head || list_empty(head))
return;
size = q_size(head);
for (struct list_head *i = head, *j; size > 0; i = j, size--) {
j = head->next;
for (int k = rand() % size; k > 0; k--)
j = j->next;
// Swap i->prev and j
list_move_tail(i->prev, j);
list_move_tail(j, i);
}
}
```
上方的函式利用英語維基所提及的 [morden algorithm](https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#The_modern_algorithm) 實作其~~偽代碼~~虛擬碼如下：
```txt
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
```
接下來實做 `do_shuffle` 對 `q_shuffle` 進行包裝。
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Try to access null queue");
error_check();
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
show_queue(3);
return !error_check();
}
```
`do_shuffle` 參考 `q_test.c` 中眾多 `do_*` 函式實做，使 `shuffle` 成為一個不接受任何參數、呼叫 `q_shuffle` 的命令。
最後在 `console_init` 函式中註冊 `shuffle` 命令即大功告成。
```diff
static void console_init()
{
...
ADD_COMMAND(swap,
" | Swap every two adjacent nodes in queue");
+ ADD_COMMAND(shuffle, " | Shuffle nodes in queue");
add_param("length", &string_length, "Maximum length of displayed string",
NULL);
...
}
```
### 實做伺服器（ `web` ）
伺服器並非一蹴可及，因此先新增一個命令 `web` ，待未來實做伺服器後再賦予其實際功能。
```c
static bool do_web(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
return true;
}
```
```diff
static void console_init()
{
...
ADD_COMMAND(shuffle, " | Shuffle nodes in queue");
+ ADD_COMMAND(web, " | Response to web client");
add_param("length", &string_length, "Maximum length of displayed string",
NULL);
...
}
```
由於網頁伺服器並不是由簡單的三言兩語能夠描述的，因此獨立出二個檔案（分別為標頭檔 `tinyserver.h` 和實做 `tinyserver.c` ）來實現網頁伺服器。
首先，在標頭檔中，須對於全域變數進行宣告，以供其他檔案存取。
```c
extern int listenfd;
extern bool noise;
```
參考 [K01: lab0](https://hackmd.io/@sysprog/linux2022-lab0#%E6%95%B4%E5%90%88-tiny-web-server) 及 [7890/tiny-web-server](https://github.com/7890/tiny-web-server) 來實做自己的 `process` 函式，其功能為在收到請求後，將 URL 的斜線替為空格，並在終端機及網頁上印出相對應的字串。
```c
char *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);
char *p = req.function_name;
/* Change '/' to ' ' */
while ((*p) != '\0') {
++p;
if (*p == '/')
*p = ' ';
}
#ifdef LOG_ACCESS
log_access(status, clientaddr, &req);
#endif
char *ret = malloc(strlen(req.function_name) + 1);
strncpy(ret, req.function_name, strlen(req.function_name) + 1);
writen(fd, req.function_name, strlen(req.function_name));
printf("web> %s\n", req.function_name);
return ret;
}
```
其中許多的自定義函式實做均在 7890/tiny-web-server 可見，惟部份函式須稍做更動以符合本作業的規範。
Makefile 也要做出相對應的更動。
```diff
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
- linenoise.o
+ linenoise.o tinyserver.o
deps := $(OBJS:%.o=.%.o.d)
```
接著參考 K01: lab0 編輯 `console.c` 中的 `cmd_select` 函式及 `run_console` 函式，以使其能處理多個檔案描述符及根據 `noise` 旗標來決定要執行 `linenoise()` 或 `cmd_select()` 。詳細的改動可以參考 K01: lab0 ，在此不多贅述。
再來是新增取得檔案描述符的函式，此函式僅為對 `open_listenfd` 函式的封裝，而 `open_listenfd` 函式實做可見於 7890/tiny-web-server。
```c
int get_listenfd()
{
int default_port = DEFAULT_PORT;
listenfd = open_listenfd(default_port);
if (listenfd > 0) {
printf("listen on port %d, fd is %d\n", default_port, listenfd);
} else {
perror("ERROR");
exit(listenfd);
}
return listenfd;
}
```
緊接著是 `tinyserver.c` 中的最後一個函式： `tiny_server_init` ，其功能為忽略 `SIGPIPE` 訊號，並會在主函式中被呼叫。當瀏覽器因故取消請求時，便會發出 `SIGPIPE` 訊號。該訊號的預設行為為中止（ terminate ）程序。未避免程序中止，在訊號發出時直接忽略它。
```c
void tiny_server_init()
{
// Ignore SIGPIPE signal, so if browser cancels the request, it
// won't kill the whole process.
signal(SIGPIPE, SIG_IGN);
}
```
實踐伺服器的最後一里路就是回到 `do_web` 函式，新增以下二行！
```diff
static bool do_web(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
+ listenfd = get_listenfd();
+ noise = false;
return true;
}
```
然在編譯實測後，發現仍有不足，遇到的問題如下：
1. 輸入第二次 `web` 命令後會使程序直接中斷
2. 在發出請求後，會再印出一次指令
以下是依據以上問題所提出的解決方案，即：
1. 檢查 `listenfd` ，若已開啟則不再呼叫 `get_listenfd` 。
2. `set_echo(false)`
```diff
static bool do_web(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
+ if (listenfd == -1) {
listenfd = get_listenfd();
noise = false;
+ set_echo(false);
return true;
+ } else {
+ report(1, "web server is already turned on");
+ return false;
+ }
}
```
#### HTTP header
上述之伺服器並未回傳任何 HTTP header ，也就是本伺服器在回覆時並未明確定義狀態碼、 HTTP 版本、資料格式等，在此簡單實做回傳 HTTP header 的函式。
```c
static void writen_header(int out_fd)
{
char buf[256];
snprintf(buf, sizeof(buf), "HTTP/1.1 200 OK\r\nAccept-Ranges: bytes\r\n");
snprintf(buf + strlen(buf), sizeof(buf) - strlen(buf),
"Cache-Control: no-cache\r\n");
snprintf(buf + strlen(buf), sizeof(buf) - strlen(buf),
"Content-type: text/plain\r\n\r\n");
writen(out_fd, buf, strlen(buf));
}
```
並在 `process` 函式中呼叫。
```diff
char *process(int fd, struct sockaddr_in *clientaddr)
{
...
+ writen_header(fd);
writen(fd, req.function_name, strlen(req.function_name));
...
}
````
#### `favicon.ico` 問題
實際上部份瀏覽器在發出請求的時候，若未在 HTML 的 `head` 段落中明確定義 favicon ，瀏覽器會順帶發出 `http://xxx/favicon.ico` 的請求。若要避免瀏覽器發出該請求，可在 `head` 段落中加入 `<link rel="shortcut icon" href="#">` 即可。
嘗試在承接之前的程式碼下解決問題，因此簡單實做回覆 HTML 格式的函式。
```c
static void writen_content(int out_fd, const char *content)
{
char buf[1024];
// Prevent browser sending favicon.ico request
snprintf(buf, sizeof(buf),
"<!DOCTYPE html>"
"<html>"
"<head>"
"<link rel=\"shortcut icon\" href=\"#\">"
"</head>"
"<body>%s</body>"
"</html>",
content);
writen(out_fd, buf, strlen(buf));
}
```
並修改 MIME 類別。
```diff
static void writen_header(int out_fd)
{
...
snprintf(buf + strlen(buf), sizeof(buf) - strlen(buf),
- "Content-type: text/plain\r\n\r\n");
+ "Content-type: text/html\r\n\r\n");
...
}
````
最後在 `process` 函式中呼叫即可。
```diff
char *process(int fd, struct sockaddr_in *clientaddr)
{
...
writen_header(fd);
- writen(fd, req.function_name, strlen(req.function_name));
+ writen_content(fd, req.function_name);
...
}
````
### 修正錯誤（ Address Sanitizer ）
期望藉 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 修正錯誤，事實上該錯誤已於 [#60](https://github.com/sysprog21/lab0-c/pull/60) 解決。
在此嘗試重現錯誤。
1. `git revert` 並修復衝突
```shell
git revert 8fbc1
```
2. `make`
```shell
make clean # optional
make SANITIZER=1
```
3. 執行 `qtest` 並鍵入 `help` ，錯誤訊息如下
```shell
$ ./qtest
cmd> help
Commands:
# ... | Display comment
dedup | Delete all nodes that have duplicate string
dm | Delete middle node in queue
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.
rt [str] | Remove from tail of queue. Optionally compare to expected value str
show | Show queue contents
shuffle | Shuffle nodes in queue
size [n] | Compute queue size n times (default: n == 1)
sort | Sort queue in ascending order
source file | Read commands from source file
swap | Swap every two adjacent nodes in queue
time cmd arg ... | Time command execution
web | Response to web client
Options:
=================================================================
==449409==ERROR: AddressSanitizer: global-buffer-overflow on address 0x559904fd1d40 at pc 0x559904fb7b84 bp 0x7ffcaa133e50 sp 0x7ffcaa133e40
READ of size 4 at 0x559904fd1d40 thread T0
#0 0x559904fb7b83 in do_help /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:271
#1 0x559904fb79bf in interpret_cmda /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:185
#2 0x559904fb835e in interpret_cmd /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:208
#3 0x559904fb9daf in run_console /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:669
#4 0x559904fb666e in main /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/qtest.c:1135
#5 0x7fad9f4480b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x559904fb2ccd in _start (/home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/qtest+0x9ccd)
0x559904fd1d41 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x559904fd1d40) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/leon/Documents/NCKU/Linux_Kernel/hw0/lab0-c/console.c:271 in do_help
Shadow bytes around the buggy address:
0x0ab3a09f2350: f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9
0x0ab3a09f2360: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
0x0ab3a09f2370: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
0x0ab3a09f2380: 04 f9 f9 f9 f9 f9 f9 f9 00 00 00 00 00 00 00 00
0x0ab3a09f2390: 00 00 f9 f9 f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9
=>0x0ab3a09f23a0: 01 f9 f9 f9 f9 f9 f9 f9[01]f9 f9 f9 f9 f9 f9 f9
0x0ab3a09f23b0: 04 f9 f9 f9 f9 f9 f9 f9 04 f9 f9 f9 f9 f9 f9 f9
0x0ab3a09f23c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab3a09f23d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab3a09f23e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab3a09f23f0: 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
==449409==ABORTING
```
### 修正錯誤（ Valgrind ）
直接執行主程式並未發現任何可觸發錯誤的地方。範例如下。
```shell
$ valgrind ./qtest
cmd> new
l = []
cmd> it a
l = [a]
cmd> it z
l = [a z]
cmd> swap
l = [z a]
cmd> sort
l = [a z]
cmd> free
l = NULL
cmd>
Freeing queue
```
然若餵檔則會出錯。
```shell
$ valgrind ./qtest -f ./traces/trace-eg.cmd
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
l = NULL
cmd> # Create empty queue
cmd> new
l = []
cmd> # See how long it is
cmd> size
Queue size = 0
l = []
cmd> # Fill it with some values. First at the head
cmd> ih dolphin
l = [dolphin]
cmd> ih bear
l = [bear dolphin]
cmd> ih gerbil
l = [gerbil bear dolphin]
cmd> # Now at the tail
cmd> it meerkat
l = [gerbil bear dolphin meerkat]
cmd> it bear
l = [gerbil bear dolphin meerkat bear]
cmd> # Reverse it
cmd> reverse
l = [bear meerkat dolphin bear gerbil]
cmd> # See how long it is
cmd> size
Queue size = 5
l = [bear meerkat dolphin bear gerbil]
cmd> # Delete queue. Goes back to a NULL queue.
cmd> free
l = NULL
cmd> # Exit program
cmd> quit
Freeing queue
==450650== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==450650== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==450650== by 0x4A5250E: strdup (strdup.c:42)
==450650== by 0x111024: linenoiseHistoryAdd (linenoise.c:1236)
==450650== by 0x111BB7: linenoiseHistoryLoad (linenoise.c:1325)
==450650== by 0x10CC9B: main (qtest.c:1124)
==450650==
==450650== 97 bytes in 19 blocks are still reachable in loss record 2 of 3
==450650== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==450650== by 0x4A5250E: strdup (strdup.c:42)
==450650== by 0x110F98: linenoiseHistoryAdd (linenoise.c:1236)
==450650== by 0x111BB7: linenoiseHistoryLoad (linenoise.c:1325)
==450650== by 0x10CC9B: main (qtest.c:1124)
==450650==
==450650== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==450650== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==450650== by 0x110FE4: linenoiseHistoryAdd (linenoise.c:1224)
==450650== by 0x111BB7: linenoiseHistoryLoad (linenoise.c:1325)
==450650== by 0x10CC9B: main (qtest.c:1124)
==450650==
```
發現均為 `linenoiseHistoryLoad` 所呼叫的 `linenoiseHistoryAdd` 中直接或間接呼叫的 `malloc` 未釋放。
追查後發現，有一 `freeHistory` 函式會負責釋放 `history` 相關物件，其會間接被註冊為當程序結束時的函式（ `atexit` ）。 `atexit` 其在有輸入檔的情況下並不會被呼叫到。見下方函式實做。
```c
bool run_console(char *infile_name)
{
if (!push_file(infile_name)) {
report(1, "ERROR: Could not open source file '%s'", infile_name);
return false;
}
if (!has_infile) {
char *cmdline;
while (noise && (cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
}
if (!noise)
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
即，當沒有輸入檔時， `has_infile` 為非，函式會直接執行 `else` 部份，而不會執行到會間接呼叫到 `atexit()` 的 `linenoise()` 。
欲避免此情形解法至少有二。
1. 無論如何強制呼叫 `atexit`
2. 在沒有輸入檔的情況下不在主函式呼叫類 `linenoiseHistoryLoad` 的函式
其中第二種作法較為合理。因此嘗試改寫主函式。
```diff
int main(int argc, char *argv[])
{
...
+ if (!infile_name) {
/* Trigger call back function(auto completion) */
linenoiseSetCompletionCallback(completion);
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
+ }
...
}
```
再次編譯後發現錯誤被解決了。
隨後根據 [AmyLin0210](https://hackmd.io/@AmyLin0210/rJpekw9kc) 的開發紀錄及 [#74](https://github.com/sysprog21/lab0-c/pull/74) ，發現我尚未考慮到在錯誤檔名下亦會有記憶體洩漏。根據上述連結，再次更改主函式的部份實做。
```diff
int main(int argc, char *argv[])
{
...
- ok = ok && finish_cmd();
+ ok = finish_cmd() && ok;
...
}
```
如此一來便解決目前已發現的記憶體洩漏問題了。
#### 視覺化記憶體用量（ Massif ）
在此針對修正前及修正後的記憶體用量做出觀察，在此以 `./qtest -f ./traces/trace-eg.cmd` 指令作為範例。
以下為修正前的數據。
- 運用 `ms_print` 工具所印出的圖表
```txt
--------------------------------------------------------------------------------
Command: ./qtest -f ./traces/trace-eg.cmd
Massif arguments: (none)
ms_print arguments: massif.out.564249
--------------------------------------------------------------------------------
KB
12.08^ @#
| :@:::@:::@#
| ::@::::::@@:::@:: @#:
| ::@::::::@@:::@:: @#:
| ::@::::::@@:::@:: @#:
| ::@::::::@@:::@:: @#:
| ::@::::::@@:::@:: @#:
| ::@::::::@@:::@:: @#:
| ::@::::::@@:::@:: @#:
| ::@::::::@@:::@:: @#:
| ::::@::::::@@:::@:: @#:
| ::::@::::::@@:::@:: @#:
| ::::@::::::@@:::@:: @#:
| ::::@::::::@@:::@:: @#:
| ::::@::::::@@:::@:: @#:
| ::::@::::::@@:::@:: @#:
| ::::@::::::@@:::@:: @#:
| ::::@::::::@@:::@:: @#:
| ::::@::::::@@:::@:: @#:@
| :@::::@::::::@@:::@:: @#:@
0 +----------------------------------------------------------------------->ki
0 362.6
Number of snapshots: 80
Detailed snapshots: [4, 22, 43, 48, 57, 67, 68 (peak), 78]
```
- 運用 [Massif.js](https://boutglay.com/massifjs/) 所視覺化的圖表。
由此二圖可見末端未完全歸零。
以下為修正後的數據。
- 運用 `ms_print` 工具所印出的圖表
```txt
--------------------------------------------------------------------------------
Command: ./qtest -f ./traces/trace-eg.cmd
Massif arguments: (none)
ms_print arguments: massif.out.564872
--------------------------------------------------------------------------------
KB
11.45^ #
| : :::@:::#:
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| ::@:@::::::::::@:: #::
| @::@:@::::::::::@:: #:::
0 +----------------------------------------------------------------------->ki
0 353.3
Number of snapshots: 66
Detailed snapshots: [3, 11, 19, 45, 52, 55 (peak), 65]
```
- 運用 Massif.js 所視覺化的圖表
由此二圖可見末端完全歸零。
Sign in with Wallet
Connect another wallet