# 2022 lab0
contributed by < [maromasamsa](https://github.com/maromaSamsa) >
###### tags: `linux2022`
> [作業說明](https://hackmd.io/@sysprog/linux2022-lab0)
## 安裝環境
```shell=
$gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 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: 158
Model name: Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz
Stepping: 9
CPU MHz: 3400.000
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 6799.81
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
```
## 開發前的準備
- 學習 [git](https://hackmd.io/qB62WY7WT0qDpp0sIRtiqw) 的使用
- 先從 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c) 為自己的 repo
- 之後在本機的終端機使用 git clone <myRepoLink> 將檔案下載下來
- 後在該目錄 (directory) 中使用 make check 確定程式可以正常運作，但缺少相應的功能需要補足
```shell=
$./qtest
cmd>
```
- 在開發過程中可以使用 gdb 與 valgrind 去除錯與分析不當的記憶體使用
```shell=
$gdb ./qtest
GNU gdb (Ubuntu 9.2-0ubuntu1~20.04.1) 9.2
Copyright (C) 2020 Free Software Foundation, Inc.
......
Reading symbols from ./qtest...
## 幾個常用的指令
(gdb) run // 執行./qtest
(gdb) b <filename>:<l> // 於目標 file 的第 l 行設置斷點
(gdb) p <var> // 印出 var
(gdb) bt // backtrace 堆疊追蹤，顯示出從 main 至當前執行的呼叫函式
```
```shell=
$valgrind -q ./qtest
cmd> // 後像一般執行程式一樣操作即可，若記憶體發生不當存取會跳出訊息
```
### 專案中的資料結構設計
```graphviz
digraph {
rankdir = "LR";
node [shape="record"];
header [label="<top>element_t|NULL|<n>list_head"];
a [label="<top>element_t|value|<n>list_head"];
b [label="<top>element_t|value|<n>list_head"];
c [label="<top>element_t|value|<n>list_head"];
header:n -> a:n
a:n -> header:n
a:n -> b:n
b:n -> a:n
b:n -> c:n
c:n -> b:n
c:n -> header:n
header:n -> c:n
"*head" -> header:n
}
```
在 `list.h` 中我們可以看到如下的結構:
```c=
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
而在 `queue.h` 中，我們是使用以下的資料結構:
```c=
typedef struct {
char *value;
struct list_head list;
} element_t;
```
而設計成如此可以將功能細部分化，使程式碼撰寫的彈性更高， `list.h` 只負責實作 doubly linked circular list 以及相關的鏈結指標操作，其餘需要開發者自行定義。例如我今天欲自行設計一個新的 doubly linked circular queue ，每一個節點會儲存兩筆資料，那我只需要引入 `list.h` ，其餘的結構內容自己設計即可。
翻看需要補齊功能的 `queue.c` 中，許多只需要進行鏈結指標操作的函式，因為不需要動用到結點內部指向的字串資料，都是將 `list_head` 做為參數引入，如若在上述的情況下需要取得 `element_t` 的地址，則可以使用 linux kernel 中的 `container_of()` ，這部分在 `list.h` 中亦有相關的實作:
[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
```c=
/// in list.h
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#else
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
...
// 不太明白為何要改名的理由，用意何在?
#define list_entry(node, type, member) container_of(node, type, member)
```
## 對於一些駐列 (queue) 操作的實作
以下未特別標註的程式碼均於 queue.c 中實作。
### q_size
> Get the size of the queue
> @head: header of queue
> Return: the number of elements in queue, zero if queue is NULL or empty
```c=
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head){
len++
}
return len;
}
```
`list_for_each` 在 list.h 中的程式碼如下，因為 doubly linked circular list 的特性，這個巨集 (macro) 會在呼叫他的地方，展開為一個走訪全部節點的 for loop
```c=
// in list.h
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
### q_new
> Create an empty queue whose next and prev pointer point to itself
Return: NULL for allocation failed
```c=
struct list_head *q_new()
{
element_t *q = malloc(sizeof(element_t));
if (!q) {
return NULL;
}
q->value = NULL;
INIT_LIST_HEAD(&q->list);
return &q->list;
}
```
```c=
// in list.h
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
一開始很納悶為什麼回傳的型別不是 `element_t*` ，這樣後續要如何存取字串資料呢？直到了解 `container_of` 的存在之後， 彷彿開啟新世界大門。只要有目標結構其中任意成員的位址，便可以找到該結構的開頭地址，因此我們不需要特地在 `element_t` 中建立一個成員指向下一個 `element_t` 節點，只需在定義 `element_t` 時引入 `list_head` ，便可以「繼承」已經實作的 `list_head` ，使 `element_t` 具有 doubly linked circular list 的特性。
### q_free
> Free all storage used by queue, no effect if header is NULL
>@head: header of queue
```c=
void q_free(struct list_head *l)
{
if (!l) {
// that means l == NULL
return;
}
struct list_head *node = l->next;
while (node != l) {
element_t *e = container_of(node, element_t, list);
node = node->next;
q_release_element(e);
}
element_t *head = container_of(l, element_t, list);
free(head);
}
```
:::info
$man malloc
RETURN VALUE 中我們可以發現以下敘述
The malloc() and calloc() functions return a pointer to the allocated memory, which is suitably aligned for any built-in type. <span style="color:red">On error, these functions return NULL.</span>
可以做為判別該節點是否已經進行過動態記憶體配置的依據
:::
:::warning
有一個目前想不明白的問題，我以為這兩種寫法是等價的，但看起來特別加註 struct 是表示宣告一個不完整的類別類型
```c=
element_t *e = container_of(node, element_t, list);
// 編輯器會提醒以下寫法錯誤
struct element_t *e = container_of(node, struct element_t, list);
```
不得使用不完整的類別類型 "struct element_t" 指標C/C++(393)
:::
```c=
// in queue.h
static inline void q_release_element(element_t *e)
{
test_free(e->value);
test_free(e);
}
```
先確認該節點已經進行過動態記憶體配置，再進入該節點執行走訪與釋放記憶體的工作，使用 `container_of` 找到實際的整個節點的頭地址，再進行釋放，要注意 head 並不存有資料字串，因此不能使用提供的 `q_release_element` ，需要單獨處理。
### q_insert_head, q_insert_tail
> Argument s points to the string to be stored.
> The function must explicitly allocate space and copy the string into it.
> Return: true for success, false for allocation failed or queue is NULL
```c=
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *q = malloc(sizeof(element_t));
if (!q) {
return false;
}
q->value = strdup(s);
if (!q->value) {
free(q);
return false;
}
list_add(&q->list, head);
return true;
}
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *q = malloc(sizeof(element_t));
if (!q) {
return false;
}
q->value = strdup(s);
if (!q->value) {
free(q);
return false;
}
list_add_tail(&q->list, head);
return true;
}
```
一樣先確認 head 是否為 NULL，然後進行 `element_t` 記憶體配置，將複製到新空間的字串連結，最後將一個完整的 `element_t` 透過 `list.h` 內實作的方法連結到駐列中。
```c=
// in list.h
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
### q_remove_head, q_remove_tail
```c=
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head) {
return NULL;
}
if (list_empty(head)) {
return NULL;
}
element_t *q = container_of(head->next, element_t, list);
list_del(head->next);
strncpy(sp, q->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
return q;
}
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head) {
return NULL;
}
if (list_empty(head)) {
return NULL;
}
element_t *q = container_of(head->prev, element_t, list);
list_del(head->prev);
strncpy(sp, q->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
return q;
}
```
之後測試發現若是刪除節點而不回傳字串時會出錯
```shell=
l = [r]
cmd> rhq
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
使用 gdb backtrace 發現這種情況下傳入的 `sp` 為 NULL 並非指向字元陣列，因而報錯，最後改為:
```c=10
...
if(sp) {
strncpy(sp, q->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
...
```
### q_delete_mid
[leetcode reference](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
> Delete the middle node in queue
> The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing.
> e.g. If there're six element [0...5], the third member [2] should be return.
> Return: true for success, false if list is NULL or empty.
```c=
bool q_delete_mid(struct list_head *head)
{
if (!head) {
return false;
}
if (list_empty(head)) {
return false;
}
struct list_head *mid = head->next;
struct list_head *end = head->next;
bool step = false;
while (end != head) {
end = end->next;
if (step) {
mid = mid->next;
}
step = !step;
}
list_del(mid);
q_release_element(container_of(mid, element_t, list));
return true;
}
```
最直接的思維是設立兩個指標初始指向第一個元素，第一個指標每走兩步另一個指標只走一步，當第一個指標走完時，釋放當前第二個指標指向的元素。後來觀摩其他人的做法後，得知因為是雙向環形結構，也可以一個往前走一個往後走，直到雙方相遇亦可以實現。不管什麼方法，都需要考慮元素個數為偶數時的問題。
### q_delete_dup (list is sorted)
[leetcode reference](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
```c=
bool q_delete_dup(struct list_head *head)
{
if (!head) {
return false;
}
if (head->prev == head->next) {
// if list is singular or empty, return true with doing nothing
return true;
}
struct list_head *trash = q_new();
struct list_head *start;
bool isDup = false;
element_t *q_iter;
element_t *q_safe;
list_for_each_entry_safe (q_iter, q_safe, head, list) {
if (&q_safe->list != head &&
strcmp(q_iter->value, q_safe->value) == 0) {
if (!isDup) {
start = &q_iter->list;
isDup = true;
}
} else {
if (isDup) {
struct list_head *trash_first = trash->next;
struct list_head *head_first = start->prev;
trash->next = start;
start->prev = trash;
head_first->next = &q_safe->list;
q_safe->list.prev = head_first;
q_iter->list.next = trash_first;
trash_first->prev = &q_iter->list;
isDup = false;
}
}
}
q_free(trash);
return true;
}
```
因為是排序過的，重複的字串元素必定相鄰，我希望盡量做越少次指標鏈結的更動越好，因此會只會將重複的元素串去頭去尾，加入新創建的 header `trash` 中，最後再使用 `q_free` 將接入 `trash` 的全部元素銷毀。其中使用了 `list_for_each_entry_safe` 協助存取當前走訪的指標與下一個指標 (雖然他原先設計的目的似乎不希望開發者用到 `q_safe` )，我推測這樣子可能在某些情況下運行速度會比一個一個銷毀來的快 (例如有巨量相同的重複字串)，需要做實驗驗證。
### q_sort
- 第一版為遞迴版本的 Quick sort 效能測試理所當然的失敗
```c=
static void quick_sort(struct list_head *start, struct list_head *end)
{
if (start == end) {
return;
}
struct list_head *pivot = start;
struct list_head *head = pivot;
char *pStr = list_entry(pivot, element_t, list)->value;
while (start != end) {
char *sStr = list_entry(start, element_t, list)->value;
start = start->next;
if (strcmp(pStr, sStr) <= 0) {
// to pivot right (next), do nothing
} else {
// to pivot left (prev)
list_move_tail(start->prev, head);
head = head->prev;
}
}
quick_sort(head, pivot); // pivot left
quick_sort(pivot->next, end); // pivot right
}
void q_sort(struct list_head *head)
{
if (!head || head->prev == head->next ) {
return;
}
quick_sort(head->next, head);
}
```
:::danger
Worst case of quick sort bigO = O(n^2)
e.g.
cmd>ih tiger 10000
cmd>ih zoo 10000
:::
- 閱讀 [老師提供的教材](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 之後，試著寫出符合分治法精神的遞迴版 Merge sort
```c=
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if (!head || head->prev == head->next) {
/*
* if there is no init list or list is singular
* or list is empty
*/
return;
}
//1. uncircular the list
head->prev->next = NULL;
// 2. sorting, we not consider prev link when sorting
struct list_head *sorted;
sorted = merge_sort(head->next, q_size(head));
// 3. reconstract to doubly linked circular queue
head->next = sorted;
struct list_head *tmp = head;
while (tmp->next) {
tmp->next->prev = tmp;
tmp = tmp->next;
}
tmp->next = head;
head->prev = tmp;
}
```
因為想不到如何在維持 doubly linked circular queue 下使用 Merge sort ，我在做完一些例外判斷之後，將整個排序流程分成三大部份：
##### 1. 解除尾端鍊接
忽略 `prev` 的連接關係，在解除了尾端鍊接之後，便可以將目前的 `queue` 看作 singular linked queue
##### 2. 使用遞迴版 Merge sort
閱讀 [lambert](https://hackmd.io/@lambert-wu) 同學在討論區分享的 [自撰筆記](https://hackmd.io/@lambert-wu/modified-merge-sort#%E9%81%9E%E8%BF%B4%E7%89%88) 所紀錄下的結論，可以知道迭代風格的 merge sort 會有更好的效能，不過因為寫起來並不易讀，且需要考慮要用動態記憶體配置或是固定陣列除存分割的節點，以及更重要的主因 ( 我還不太會寫 ) ，這邊展示的是遞迴版的實作。我在分割的速度上引入當前佇列長度，可以稍微優化執行速度。
以下說明排序實作程式碼：
```c=
static struct list_head *merge_sort(struct list_head *li, size_t n)
{
if (n == 1) {
li->next = NULL;
return li;
}
struct list_head *mid = li;
for (int i = 0; i < n / 2; ++i) {
mid = mid->next;
}
mid->prev->next = NULL;
struct list_head *left = merge_sort(li, n / 2);
struct list_head *right = merge_sort(mid, n / 2 + (n % 2));
return merge_two_list(left, right);
}
```
:::info
使用遞迴的方式將當前佇列平分成兩等分（ 嚴格來說，是分割成差距比例不超過 1:2 的佇列，在當前佇列數量為 3 時會出現此極值，隨著數量越多，分割的比例會越趨近於 1:1，若初始佇列數量為偶數，則分割比例永遠是 1:1 ），直到無法分割為止，每一層會紀錄下分割位置，後用於呼叫合併排序 `merge_two_list();`，並將排序後的結果回傳。
e.g. 當初始佇列數量為 5, `li` : `mid` = 2:3：
> <span style="color:red"> mid->prev->next = NULL </span>;
```graphviz
digraph {
rankdir = "LR";
node0[label = "0", xlabel = "li"];
node1[label = "1"];
node2[label = "2", xlabel = "mid"];
node3[label = "3"];
node4[label = "4"];
node0->node1;
node1->node2[color = red];
node2->node3;
node3->node4;
}
```
> left = merge_sort(li, 2);
> right = merge_sort(mid, 3);
:::
因為每一層遞迴函式都可以確保兩邊佇列長度差不多，根據分治法的觀念可以知道遞迴呼叫深度為
**log<sub>2</sub><sup>n</sup>** ， **n** 為初始佇列長度。在另一方面，因為有傳入長度作為依據，找尋中間斷點的走訪次數可以從 **n** 縮短一半變為 **n/2**，
:::info
雖然量級不變， Merge sort 分割階段的時間複雜度暫時分析為 **O($\frac{n}{2}$*log<sub>2</sub><sup>n</sup>)***
:::
合併排序實作程式碼，這裡使用雙重指標去操作指標 `sorted` 去做融合排序，並回傳結果。
```c=
static struct list_head *merge_two_list(struct list_head *left,
struct list_head *right)
{
struct list_head *sorted = NULL;
struct list_head **ptr = &sorted;
for (; left && right; ptr = &(*ptr)->next) {
char *lVal = list_entry(left, element_t, list)->value;
char *rVal = list_entry(right, element_t, list)->value;
if (strcmp(lVal, rVal) <= 0) {
*ptr = left;
left = left->next;
} else {
*ptr = right;
right = right->next;
}
}
*ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);
return sorted;
}
```
因為前面的分割階段可以確保佇列 `left` 與 `right` 長度差不多，一樣根據分治法的觀念可以知道遞迴呼叫深度為 **log<sub>2</sub><sup>n</sup>** ，每一層中佇列兩兩合併，時間複雜度為 **O(n)**
:::info
由此可以解釋 Merge sort 合併階段的時間複雜度為 **O(n*log<sub>2</sub><sup>n</sup>)***
:::
:::success
這確保了在一些特殊情況下，不像是 Quick sort 的時間複雜度會淪落到 **O($n^2$)** ， Merge sort 的時間複雜度都可控制在 **O($\frac{n}{2}$*log<sub>2</sub><sup>n</sup> + n*log<sub>2</sub><sup>n</sup>)*** = **O($\frac{3n}{2}$*log<sub>2</sub><sup>n</sup>)*** = **O(n*log<sub>2</sub><sup>n</sup>)***
:::
##### 3. 將排序好的佇列變回 doubly linked circular queue
將處理過後的佇列連接回 `head` ，並且重新梳理已經因為重新排序而錯亂的 `prev` 連接關係
## 與 Linux kernel 實作的 [list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 進行比較
## 於 qtest.c 中新增指令以及功能
### shuffle
> 允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
使用 **gdb** 觀察其中一個已經實作的功能是如何被呼叫的，這裡以 `q_swap` 為例：
```shell=
$ gdb ./qtest
...
...
$ (gdb) b queue.c:q_swap
Breakpoint 1 at 0x6f02: file queue.c, line 200.
$ (gdb) run
$ cmd> swap
Warning: Try to access null queue
Breakpoint 1, q_swap (head=0x0) at queue.c:200
$ (gdb) bt
#0 q_swap (head=0x0) at queue.c:200
#1 0x0000555555557052 in do_swap (argc=<optimized out>, argv=<optimized out>) at qtest.c:721
#2 0x00005555555594f9 in interpret_cmda (argc=argc@entry=1, argv=argv@entry=0x555555566ea0) at console.c:184
#3 0x0000555555559a45 in interpret_cmd (cmdline=<optimized out>, cmdline@entry=0x5555555669c0 "swap")
at console.c:204
#4 0x000055555555a525 in run_console (infile_name=<optimized out>) at console.c:644
#5 0x00005555555589f0 in main (argc=1, argv=0x7fffffffdc08) at qtest.c:1010
```
其中 #2 中的 `interpret_cmda` 的程式碼如下：
```c=
/* Execute a command that has already been split into arguments */
static bool interpret_cmda(int argc, char *argv[])
{
if (argc == 0)
return true;
/* Try to find matching command */
cmd_ptr next_cmd = cmd_list;
bool ok = true;
while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
next_cmd = next_cmd->next;
if (next_cmd) {
ok = next_cmd->operation(argc, argv);
if (!ok)
record_error();
} else {
report(1, "Unknown command '%s'", argv[0]);
record_error();
ok = false;
}
return ok;
}
```
可以發現當我們在終端機輸入命令之後會被拆解成 `argc` 和`*argv[]`，命令的第一個字串 `argv[0]` （ 在這裡是 `"swap"` ）會與命令清單 `cmd_list` 逐一比較，若是有相符則執行該命令 `next_cmd->operation(argc, argv)` （在這裡會執行 `do_swap` ），因此要新增功能需要在 `cmd_list` 中新增一個命令節點。
對 `cmd_list` 使用 `find all refference` ，可以發現新增命令節點的區塊被放在這裡：
```c=
// in console.c
/* Add a new command */
void add_cmd(char *name, cmd_function operation, char *documentation)
{
cmd_ptr next_cmd = cmd_list;
cmd_ptr *last_loc = &cmd_list;
while (next_cmd && strcmp(name, next_cmd->name) > 0) {
last_loc = &next_cmd->next;
next_cmd = next_cmd->next;
}
cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
ele->name = name;
ele->operation = operation;
ele->documentation = documentation;
ele->next = next_cmd;
*last_loc = ele;
}
```
新增命令之後 `makefile` ，
```c=
// in qtest.c
static void console_init()
{
...
ADD_COMMAND(shuffle, " | shuffle list randomly");
...
}
```
```c=
// in console.h
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
```c=
// in qtest.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");
return true;
}
error_check();
set_noallocate_mode(true);
if (exception_setup(true)) {
for (int i = lcnt; i > 0; --i) {
int roll = rand() % i;
struct list_head *it = l_meta.l->next;
for (int j = 0; j < roll; j++)
it = it->next;
list_move_tail(it, l_meta.l);
}
}
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
### web
> 提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
> 可依據前述說明，嘗試整合 [tiny-web-server](https://github.com/7890/tiny-web-server)
Sign in with Wallet
Connect another wallet