# 2022q1 Homework1 (lab0)
contributed by < [jackhong12](https://github.com/jackhong12) >
> [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
## 實驗環境
```
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 43 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 23
Model: 17
Model name: AMD Ryzen 5 2400G with Radeon Vega Graphics
Stepping: 0
Frequency boost: enabled
CPU MHz: 285.818
CPU max MHz: 3600.0000
CPU min MHz: 1600.0000
BogoMIPS: 7186.57
Virtualization: AMD-V
L1d cache: 128 KiB
L1i cache: 256 KiB
L2 cache: 2 MiB
L3 cache: 4 MiB
NUMA node0 CPU(s): 0-7
```
## 修改 `queue.c`
### q_new
> Create empty queue. Return NULL if could not allocate space.
透過 INIT_LIST_HEAD 初始 list_head 中的 prev 和 next 指標。
```c
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
### q_free
> Free all storage used by queue
因為要刪除 list 中的節點，所以要使用 safe 版本的 macro `list_for_each_entry_safe`。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *ptr, *safe;
list_for_each_entry_safe (ptr, safe, l, list) {
free(ptr->value);
free(ptr);
}
free(l);
}
```
### q_insert_head
> Attempt to insert element at head of queue.
透過 list_add 在 queue 的開頭插入新的節點。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
list_add(&e->list, head);
return true;
}
```
### q_insert_tail
> Attempt to insert element at tail of queue.
透過 list_add_tail 在 queue 的結尾插入節點。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *e = malloc(sizeof(element_t));
if (!e)
return false;
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
list_add_tail(&e->list, head);
return true;
}
```
### q_remove_head
> Attempt to remove element from head of queue.
利用 list_del_init 移除節點，接著透過 list_entry 取得 element_t 的指標。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
struct list_head *ptr = head->next;
list_del_init(ptr);
element_t *e = list_entry(ptr, element_t, list);
if (sp && bufsize > 0) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return e;
}
```
### q_remove_tail
> Attempt to remove element from tail of queue.
利用 list_del_init 移除節點，接著透過 list_entry 取得 element_t 的指標。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
struct list_head *ptr = head->prev;
list_del_init(ptr);
element_t *e = list_entry(ptr, element_t, list);
if (sp && bufsize > 0) {
strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return e;
}
```
### q_size
> Return number of elements in queue.
利用 list_for_each 遍尋所有的節點來計算點的數量。
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
struct list_head *ptr;
int num = 0;
list_for_each (ptr, head)
num++;
return num;
}
```
### q_delete_mid
> Delete the middle node in list.
透過快慢指標取得中間節點的指標，在利用 list_del 將節點從 queue 中移除。
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *slow = head->next;
for (struct list_head *fast = slow;
fast->next != head && fast->next->next != head;
fast = fast->next->next)
slow = slow->next;
list_del(slow);
element_t *e = list_entry(slow, element_t, list);
free(e->value);
free(e);
return true;
}
```
### q_delete_dup
> Delete all nodes that have duplicate string, leaving only distinct strings from the original list.
先計算相同值得起點和結束，最後在一個迴圈將所有資源釋放。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
for (struct list_head *ptr = head->next; ptr != head;) {
struct list_head *start = ptr;
char *start_value = list_entry(start, element_t, list)->value;
for (ptr = ptr->next;
ptr != head &&
!strcmp(start_value, list_entry(ptr, element_t, list)->value);)
ptr = ptr->next;
for (struct list_head *safe = start->next; start != ptr;
start = safe, safe = start->next) {
list_del(start);
element_t *e = list_entry(start, element_t, list);
free(e->value);
free(e);
}
}
return true;
}
```
### q_swap
> Attempt to swap every two adjacent nodes.
odd 指標指向基數節點，even 指標指向偶數節點，每次迴圈都將兩個指標對調。
```c
void q_swap(struct list_head *head)
{
for (struct list_head *odd = head->next, *even = odd->next;
odd != head && even != head;) {
struct list_head *prev = odd->prev;
struct list_head *next = even->next;
prev->next = even;
even->prev = prev;
even->next = odd;
odd->prev = even;
odd->next = next;
next->prev = odd;
odd = next;
even = odd->next;
}
}
```
### q_reverse
> Reverse elements in queue.
透過 LIST_HEAD 產生一個暫時的 queue 存放所有節點，在將所有節點反向加入原本的 queue 中。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
LIST_HEAD(tmp);
list_splice(head, &tmp);
INIT_LIST_HEAD(head);
while (!list_empty(&tmp)) {
struct list_head *ptr = tmp.next;
list_del_init(ptr);
list_add(ptr, head);
}
}
```
### q_sort
> Sort elements of queue in ascending order.
下方是用來比較字串大小的 function。
```c
bool cmp(char *str1, char *str2)
{
for (; *str1 && *str2; str1++, str2++) {
if (*str1 < *str2)
return true;
else if (*str1 > *str2)
return false;
}
if (*str1)
return false;
return true;
}
```
q_sort 的部份我是實作 merge sort。
merge_sort 會將原本的 queue 分成兩個 queue 並呼叫下一層的 merge_sort，當 queue 只有一個節點時為遞迴的中止條件。
```c
void merge_sort(struct list_head *head)
{
if (list_is_singular(head))
return;
struct list_head *mid = head->next;
for (struct list_head *fast = mid;
fast->next != head && fast->next->next != head;
fast = fast->next->next) {
mid = mid->next;
}
LIST_HEAD(tmp);
list_cut_position(&tmp, mid, head->prev);
merge_sort(head);
merge_sort(&tmp);
merge(head, &tmp);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
merge_sort(head);
}
```
merge 的部份，我先用一個暫時的 queue tmp 儲存排序後的節點，最後在將 tmp 的內容移到 queue l1。
```c
void merge(struct list_head *l1, struct list_head *l2)
{
LIST_HEAD(tmp);
while (!list_empty(l1) && !list_empty(l2)) {
element_t *e1 = list_entry(l1->next, element_t, list);
element_t *e2 = list_entry(l2->next, element_t, list);
struct list_head *ptr;
if (cmp(e1->value, e2->value))
ptr = l1->next;
else
ptr = l2->next;
list_del(ptr);
list_add_tail(ptr, &tmp);
}
while (!list_empty(l1)) {
struct list_head *ptr = l1->next;
list_del(ptr);
list_add_tail(ptr, &tmp);
}
while (!list_empty(l2)) {
struct list_head *ptr = l2->next;
list_del(ptr);
list_add_tail(ptr, &tmp);
}
list_splice(&tmp, l1);
}
```
### trace-17-complexity
第 17 筆測資在實驗室的電腦和 Github Action 上的可以跑過，但不知道為什麼在我自己的電腦中有高機率會失敗，每次失敗的項目可能不同，有可能第一次是 q_insert_tail，下一次換成 q_insert_head，之後在研究看看是什麼原因造成的。
## 實作 Fisher–Yates shuffle 演算法
在 qtest.c 中加入 shuffle command。
```c
ADD_COMMAND(shuffle, " | Shuffle the nodes in the queue");
```
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
show_queue(3);
return !error_check();
}
```
我用另一個 result queue 先紀錄隨機選出的節點，最後在將結果放回 head 中。
```c
static void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
LIST_HEAD(result);
for (int len = q_size(head); len > 0; len--) {
int random = rand() % len + 1;
struct list_head *ptr = head;
for (int i = 0; i < random; i++)
ptr = ptr->next;
struct list_head *tail = head->prev;
list_del(tail);
if (ptr != tail) {
tail->next = ptr->next;
ptr->next->prev = tail;
tail->prev = ptr->prev;
ptr->prev->next = tail;
}
list_add_tail(ptr, &result);
}
list_splice(&result, head);
}
```
## 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
### valgrind 錯誤訊息
當執行 `make valgrind` 會頻繁出現以下錯誤訊息，推測是 strdup allocate 的記憶體在程式結束前沒有被釋放。
```
==2215669== 119 bytes in 20 blocks are still reachable in loss record 1 of 2
==2215669== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2215669== by 0x4A6950E: strdup (strdup.c:42)
==2215669== by 0x113FF1: linenoiseHistoryAdd (linenoise.c:1236)
==2215669== by 0x114350: linenoiseHistoryLoad (linenoise.c:1325)
==2215669== by 0x10CF4B: main (qtest.c:993)
```
在 `linenoise.c` 中有對應一段程式碼在釋放 history。
```c
static void freeHistory(void)
{
if (history) {
int j;
for (j = 0; j < history_len; j++)
free(history[j]);
free(history);
}
}
```
用 gdb 設段點在 freeHistory 上，發現其實 freeHistory 有被執行。
```
(gdb) bt
#0 freeHistory () at linenoise.c:1191
#1 0x000055555555ff19 in linenoiseAtExit () at linenoise.c:1205
#2 0x00007ffff7ca1a27 in __run_exit_handlers (status=0,
listp=0x7ffff7e43718 <__exit_funcs>, run_list_atexit=run_list_atexit@entry=true,
run_dtors=run_dtors@entry=true) at exit.c:108
#3 0x00007ffff7ca1be0 in __GI_exit (status=<optimized out>) at exit.c:139
#4 0x00007ffff7c7f0ba in __libc_start_main (main=0x555555558ce8 <main>, argc=1,
argv=0x7fffffffdb08, init=<optimized out>, fini=<optimized out>,
rtld_fini=<optimized out>, stack_end=0x7fffffffdaf8) at ../csu/libc-start.c:342
#5 0x00005555555568ce in _start ()
```
在 enableRawMode 這個函釋中有透過 atexit 註冊 linenoiseAtExit，當程式結束前會執行 linenoiseAtExit 清除 history。
```c
atexit(linenoiseAtExit);
```
但查看 run_console 後發現有分成兩種情況，一種是有輸入檔案，另一種沒有沒有輸入檔案，其中沒有輸入檔案的狀況才會呼叫到 enableRawMode。
```c
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);
}
```
在使用 gdb 設段點在 freeHistory 上，並指定輸入檔案 `traces/trace-01-ops.cmd`，但這次並不會執行到 freeHistory。
```bash
$ gdb -ex 'handle SIGALRM ignore' -ex 'b freeHistory' -ex 'run -f traces/trace-01-ops.cmd' ./qtest./qtest
```
所以只要在有在 cmd_select 前用 atexit 註冊 linenoiseAtExit 並能正常執行。
```c
} else {
registerLinenoiseAtExit();
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
```
```c
void registerLinenoiseAtExit(void)
{
atexit(linenoiseAtExit);
}
```
## 提供 web 伺服器功能
Google Drive
Gist
Clipboard
Sign in with Wallet
