# 2022q1 Homework1 (lab0)
contributed by < [gougon](https://github.com/gougon) >
> [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
## 實驗環境
```shell
$ 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: 39 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: GenuineIntel
CPU family: 6
Model: 140
Model name: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
Stepping: 1
CPU MHz: 1306.503
CPU max MHz: 4200.0000
CPU min MHz: 400.0000
BogoMIPS: 4838.40
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 128 KiB
L2 cache: 5 MiB
L3 cache: 8 MiB
NUMA node0 CPU(s): 0-7
```
## 開發過程
:::info
作業要求
- [x] q_new: 建立新的「空」佇列
- [x] q_free: 釋放佇列所佔用的記憶體
- [x] q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
- [x] q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
- [x] q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點
- [x] q_release_element: 釋放特定節點的記憶體空間
- [x] q_size: 計算目前佇列的節點總量
- [x] q_delete_mid: 移走佇列中間的節點
- [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
- [x] q_swap: 交換佇列中鄰近的節點
- [x] q_reverse: 以反向順序重新排列鏈結串列，該函數不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
- [x] q_sort: 以遞增順序來排序鏈結串列的節點
- [ ] 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [x] 在 qtest 提供新的命令 shuffle，允許藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
- [ ] 在 qtest 提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- [ ] 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
- [x] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量
- [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點
- [ ] 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度
- [ ] 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處
:::
### q_new
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(*head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
使用 `INIT_LIST_HEAD` 來初始化 `list_head *`，令 `list_head` 的 `prev` 及 `next` 皆指向自己。
### q_free
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *node = NULL, *safe = NULL;
list_for_each_entry_safe (node, safe, l, list)
q_release_element(node);
free(l);
}
```
由於 `q_free` 實際上要釋放記憶體的物件是包含 `list_head` 的 `element_t` ，因此我們首先查找使用到 `container_of` 的巨集
```c
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
發現 `list_entry` 這個巨集只是將`container_of` 再包裝了一次，因此查找使用到 `list_entry` 的巨集，發現了用來疊代的 `list_for_each_entry` 及 `list_for_each_entry_safe`，觀察程式碼後得知 safe 版本的巨集使用了 temporal pointer 來避免刪除時會導致錯誤的操作。
```c
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
```
在查閱 `list.h` 中的巨集時發現了 `list_del` 這個函數，由於此操作是刪除全部的佇列，因此不會在使用到其中的 `element_t`，因此沒有必要使用這個函數。
### q_insert_head
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return false;
int len = strlen(s) + 1;
ele->value = malloc(len);
if (!ele->value) {
free(ele);
return false;
}
strncpy(ele->value, s, len);
list_add(&ele->list, head);
return true;
}
```
此操作是在佇列最前端新增一個 `element_t`，初始化 `element_t` 需要多步驟的 `malloc`，這是由於 `element_t` 內部還有 pointer 需要被分配未知的記憶體空間。
將新的 `element_t` 新增到佇列的最前端可利用 `list_add` 這個函數來達成。
```c
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;
}
```
:::info
__memcpy vs strncpy__
`memcpy` 可用於任何類型的數據上，`strncpy` 則是只能用在字串上
:::
在實作 `q_insert_tail` 的程式碼時，發現可將新增 `element_t` 的操作抽出去，重構後的程式如下所示：
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = new_element(s);
if (!ele)
return false;
list_add(&ele->list, head);
return true;
}
```
### q_insert_tail
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ele = new_element(s);
if (!ele)
return false;
list_add_tail(&ele->list, head);
return true;
}
```
其概念與 `q_insert_head` 相同，不同之處僅在最後將 `list_add` 改為 `list_add_tail`。
為了避免 copy & paste ，因此增加了額外的函數，將新增 `element_t` 的操作抽出來並命名為 `new_element`，如下所示：
```c
element_t *new_element(char *s)
{
element_t *ele = malloc(sizeof(element_t));
if (!ele)
return NULL;
int len = strlen(s) + 1;
ele->value = malloc(len);
if (!ele->value) {
free(ele);
return NULL;
}
strncpy(ele->value, s, len);
return ele;
}
```
### q_remove_head
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!q_size(head))
return NULL;
struct list_head *next = head->next;
element_t *ret = container_of(next, element_t, list);
list_del(next);
if (sp) {
int len = strlen(sp) > bufsize - 1 ? bufsize - 1 : strlen(sp);
strncpy(sp, ret->value, len);
sp[len - 1] = '\0';
}
return ret;
}
```
首先利用 `q_size` 函數來檢查是否為空佇列，或是佇列長度為0。接著利用 `container_of` 來尋找第一個 `element_t` 的 pointer，並將它從佇列中移除(此處的移除僅代表斷開 node 間的連結，並沒有進行記憶體釋放的動作)。最後，檢查 `sp` 是否有值，若是有則將被移除元素的 `value` 複製過來，注意，由於限制 `value` 的長度不可大於 `bufsize`，因此運用三元運算子指定複製的長度。
在實作後續程式碼時，上方的移除操作可重複使用，因此將其提出：
```c
element_t *remove_element(struct list_head *pos, char *sp, size_t bufsize)
{
element_t *target = list_entry(pos, element_t, list);
list_del_init(pos);
if (sp) {
size_t len = strlen(target->value) + 1;
len = len > bufsize ? bufsize : len;
strncpy(sp, target->value, len);
sp[len - 1] = '\0';
}
return target;
}
```
此時 `q_remove_head` 程式碼僅需要一行即可完成：
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
return head && !list_empty(head) ? remove_element(head->next, sp, bufsize)
: NULL;
}
```
### q_remove_tail
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
return head && !list_empty(head) ? remove_element(head->prev, sp, bufsize)
: NULL;
}
```
由於有了 `remove_element`，因此與 `q_remove_head` 相同，僅需一行即可完成。
### q_size
```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;
}
```
### q_delete_mid
```c
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;
struct list_head *fwd = head->next, *bwd = head->prev;
while (fwd != bwd && fwd->next != bwd) {
fwd = fwd->next;
bwd = bwd->prev;
}
q_release_element(remove_element(bwd, NULL, 0));
return true;
}
```
由於佇列是 circular doubly-linked list，因此使用 forward/backward pointer 取代 fast/slow pointer 來找到中點。
藉由 `q_release_element` 搭配 `remove_element` 可完整地達成刪除節點的操作。
### q_delete_dup
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
if (list_is_singular(head))
return true;
element_t *prev = NULL, *cur = NULL;
list_for_each_entry_safe (prev, cur, head, list) {
if (&cur->list == head)
break;
char *pval = prev->value;
char *cval = cur->value;
size_t plen = strlen(pval), clen = strlen(cval);
if (plen == clen && !strncmp(pval, cval, plen))
q_release_element(remove_element(&prev->list, NULL, 0));
}
return true;
}
```
若是佇列長度僅有一個元素，則不需要做交換可直接返回，可利用 `list_is_singular` 進行檢查。
```c
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
若有多個元素，則利用 `list_for_each_entry_safe` 安全地刪除重複的節點。
參閱 [Leetcode 82.](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 後，發現此函數並不會保留一個重複的值，而是全部刪掉，如下所示：
```
ex. a a a a b b b c
(x) a b c
(o) c
```
因此將程式修改為下方程式碼：
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
if (list_is_singular(head))
return true;
bool is_dup = false;
element_t *prev = NULL, *cur = NULL;
list_for_each_entry_safe (prev, cur, head, list) {
if (&cur->list == head)
break;
char *pval = prev->value;
char *cval = cur->value;
size_t plen = strlen(pval), clen = strlen(cval);
if (plen == clen && !strncmp(pval, cval, plen)) {
is_dup = true;
q_release_element(remove_element(&prev->list, NULL, 0));
} else if (is_dup) {
is_dup = false;
q_release_element(remove_element(&prev->list, NULL, 0));
}
}
if (is_dup)
q_release_element(remove_element(&prev->list, NULL, 0));
return true;
}
```
利用 `is_dup` 判斷是否為最後一個重複的值，並進行刪除，這邊要注意的是，由於 `head` 無法提取出來進行比較，因此我們提前結束了迴圈，這會導致最後一個元素沒辦法被刪除，所以我們需要在最後利用 `is_dup` 來判斷是否為重複值，並進行刪除。
### q_swap
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (list_is_singular(head))
return;
struct list_head *first = head->next, *second = head->next->next;
struct list_head *front = first, *back = first->next;
do {
if (front == first || back != second) {
list_del(back);
list_add_tail(back, head);
}
list_del(front);
list_add_tail(front, head);
front = head->next;
back = front->next;
} while (front != first && back != first);
}
```
對每一對節點執行以下 4 個步驟的操作來達成交換的功能
```
1 2 3 4 5 6
```
1. `list_del(back)`：將後方的節點提取出來
```
2
1 3 4 5 6
```
2. `list_add_tail(back, head)`：將後方的節點放到佇列的最後
```
1 3 4 5 6 2
```
3. `list_del(front)`：將前方的節點提取出來
```
1
3 4 5 6 2
```
4. `list_add_tail(front, head)`：將前方的節點放到佇列的最後
```
3 4 5 6 2 1
```
可看到經過上述的 4 個步驟後，`1 2` 這對節點已被交換並且放到佇列的最尾端，因此我們只需要對每一對節點重複以上動作便可達成交換的功能。
但若是考慮奇數個數，則會出現最後一個元素無法成對的情況，因此在這種情況下不將 `back` 節點刪除，僅刪除 `front` 節點，而在普通情況下，可表示為 `!(front != first && back == second)`，可藉由 __De-Morgan's Theorem__ 進行如下化簡：
```c
A = front != first
B = back == second
!(A && B) = !A || !B
!A = front == first
!B = back != second
!A || !B = (front == first) || (back != second)
```
### q_reverse
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *tail = head->prev;
for (struct list_head *cur = tail->prev; cur != head; cur = tail->prev)
list_move_tail(cur, head);
}
```
倒序的概念十分簡單，我們只需要從 `tail` 開始，不斷向前疊代，並將每個元素移動到最尾端即可，並且由於 circular doubly-linked list 的關係，時間複雜度只需要 $O(n)$ 即可達成。
### q_sort
```c
void q_sort(struct list_head *head)
{
if (!head || !head->next)
return;
// Delete circular & Take out head
struct list_head *first = head->next, *last = head->prev;
last->next = NULL;
head->prev = NULL;
first->prev = NULL;
head->next = NULL;
first = mergesort_list(first);
last = first;
while (last->next)
last = last->next;
head->next = first;
head->prev = last;
first->prev = head;
last->next = head;
}
```
利用 merge sort 實作，由於在 linux kernel 中的佇列是 circular doubly-linked list，與一般常見的 linked list 不同，因此以算法必須要做出一些改動，其中最麻煩的莫過於 circular 無法透過 `node->next == NULL` 這類操作來判斷是否到達佇列的尾巴，因此，一個簡單的想法是將 circular 解除，等到排序完成後，再將頭尾相連。
綜上所述，此演算法的步驟為：
1. 斷開 circular 的連結，並且將 `head` 節點取出，以簡化演算法
2. 進行 merge sort
3. 加入 `head` 節點，並將頭尾相連
其中的 merge sort 演算法程式碼如下：
```c
struct list_head *mergesort_list(struct list_head *node)
{
if (!node || !node->next)
return node;
struct list_head *slow = node;
for (struct list_head *fast = node->next; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow->next;
slow->next = NULL;
mid->prev = NULL;
struct list_head *left = mergesort_list(node);
struct list_head *right = mergesort_list(mid);
return merge_two_lists(left, right);
}
```
由於佇列與陣列不同，無法直接利用 `left + right / 2` 來得到 `mid`，因此在這邊通過使用快慢指標來達成相同的目的。
此演算法為遞迴版本，因此會在函數內重複呼叫 `mergesort_list` 自身，並在回傳值呼叫 `merge_two_lists` 結合左右兩個佇列。
```c
struct list_head *merge_two_lists(struct list_head *l, struct list_head *r)
{
struct list_head *head = NULL, **ptr = &head, *pprev = NULL, **node = NULL;
for (; l && r; *node = (*node)->next) {
char *lval = list_entry(l, element_t, list)->value;
char *rval = list_entry(r, element_t, list)->value;
int llen = strlen(lval), rlen = strlen(rval);
int n = llen > rlen ? llen : rlen;
node = (strncmp(lval, rval, n) > 0) ? &r : &l;
*ptr = *node;
(*ptr)->prev = pprev;
ptr = &(*ptr)->next;
pprev = *node;
}
*ptr = l ? l : r;
(*ptr)->prev = pprev;
return head;
}
```
在測試時遇到了以下錯誤：
```shell
ERROR: Not sorted in ascending order
```
查閱 `qtest.c` 後，發現以下程式碼：
```c
bool ok = true;
if (l_meta.size) {
for (struct list_head *cur_l = l_meta.l->next;
cur_l != l_meta.l && --cnt; cur_l = cur_l->next) {
/* Ensure each element in ascending order */
/* FIXME: add an option to specify sorting order */
element_t *item, *next_item;
item = list_entry(cur_l, element_t, list);
next_item = list_entry(cur_l->next, element_t, list);
if (strcasecmp(item->value, next_item->value) > 0) {
report(1, "ERROR: Not sorted in ascending order");
ok = false;
break;
}
}
}
```
可以得知在測試程式中是不會比較字串的大小寫的，因此將原始 `merge_two_lists` 程式中的字串比較部分修改為如下即可通過測試：
```c
// int llen = strlen(lval), rlen = strlen(rval);
// int n = llen > rlen ? llen : rlen;
// node = (strncmp(lval, rval, n) > 0) ? &r : &l;
node = (strcasecmp(lval, rval) > 0) ? &r : &l;
```
### 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
執行以下指令：
```shell
$ make SANITIZER=1
$ ./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
Options:
echo 1 Do/don't echo commands
error 5 Number of errors until exit
fail 30 Number of times allow queue operations to return false
length 1024 Maximum length of displayed string
malloc 0 Malloc failure probability percent
simulation 0 Start/Stop simulation mode
verbose 4 Verbosity level
cmd>
Freeing queue
```
:::warning
TODO: 沒有訊息產生，不清楚發生了什麼事?
:::
### 運用 Valgrind 排除 qtest 實作的記憶體錯誤
運行 `make valgrind` 指令，發現以下錯誤重複出現：
```shell
==463375== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==463375== by 0x4A4A50E: strdup (strdup.c:42)
==463375== by 0x110DE6: linenoiseHistoryAdd (linenoise.c:1236)
==463375== by 0x111979: linenoiseHistoryLoad (linenoise.c:1325)
==463375== by 0x10CAE7: main (qtest.c:1074)
==463375==
==463375== 112 bytes in 19 blocks are still reachable in loss record 2 of 3
```
粗略看了一下，發現錯誤大多都發生在 `linenoiseHistoryAdd` 中，觀察此函數發現使用 `strdup` 所分配的記憶體最後是被放到了 `history` 這個變數內。
```c
int linenoiseHistoryAdd(const char *line)
{
...
linecopy = strdup(line);
if (!linecopy)
return 0;
if (history_len == history_max_len) {
free(history[0]);
memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
history_len--;
}
history[history_len] = linecopy;
history_len++;
return 1;
}
```
追查 `free(history)` 的程式碼，找到 `freeHistory` 這個函數負責釋放 `history` 的記憶體，繼續向前追查得知在 `enableRawMode` 的函數內會將 `linenoiseAtExit` 註冊為程式終止時執行的函數，而 `enableRawMode` 會分別在 `linenoiseRaw` 以及 `linenoisePrintKeyCodes` 中被調用，而 `linenoiseRaw` 這個函數又會在 `linenoise` 中被調用，此外，`linenoise` 函數被調用的地方正是在 `run_console` 內，為此我們檢查 `run_console` 程式碼：
```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 ((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);
}
return err_cnt == 0;
}
```
很明顯的，可以看到若是 `!has_infile` 成立，則會註冊 `linenoiseAtExit` 這個函數，反之，就會發生 memory leak，因此下一步我們要做的就是明白 `has_infile` 究竟是做甚麼的。
透過 `push_file` 可以得知 `has_infile` 是取決於 `infile_name` 有沒有值的，因此追查回 `qtest.c` 中的主函數，發現 `infile_name` 是在命令列帶有 `f` 時才會有值的，因此可以推斷在執行 `make valgrind` 時使用到了帶有 `f` 的參數，打開 `Makefile` 確認：
```cmake
...
valgrind_existence:
@which valgrind 2>&1 > /dev/null || (echo "FATAL: valgrind not found"; exit 1)
valgrind: valgrind_existence
# Explicitly disable sanitizer(s)
$(MAKE) clean SANITIZER=0 qtest
$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
cp qtest $(patched_file)
chmod u+x $(patched_file)
sed -i "s/alarm/isnan/g" $(patched_file)
scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
@echo
@echo "Test with specific case by running command:"
@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"
...
```
看到在執行 `make valgrind` 時，會使用到 `driver.py`，繼續追查，在 `driver.py` 的 `runTrace` 中發現了 `-f` 這個參數：
```python
def runTrace(self, tid):
if not tid in self.traceDict:
self.printInColor("ERROR: No trace with id %d" % tid, self.RED)
return False
fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = self.command + ["-v", vname, "-f", fname]
try:
retcode = subprocess.call(clist)
except Exception as e:
self.printInColor("Call of '%s' failed: %s" % (" ".join(clist), e), self.RED)
return False
return retcode == 0
```
至此，確定是由於執行 `make valgrind` 時，其中的 `f` 參數連帶使得 `has_infile` 為 `true` 所引發的問題，而實際上的問題點是在 `has_infile` 的過程中沒有將 `linenoiseAtExit` 註冊為終止時要執行的函數。
解決方法為將 `lineoniseHistoryLoad` 這個函數從 `qtest.c` 內移動到 `console.c`，並放置於 `!has_infile` 的 `if` 條件內，因為只有在沒有檔案時才會需要對 `history` 進行操作。
```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;
linenoiseHistoryLoad(HISTORY_FILE);
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);
}
return err_cnt == 0;
}
```
解決完上述問題後，發現仍會報以下錯誤：
```shell
==543813== 40 bytes in 1 blocks are still reachable in loss record 29 of 29
==543813== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==543813== by 0x10D180: malloc_or_fail (report.c:191)
==543813== by 0x10DC84: add_param (console.c:110)
==543813== by 0x10CAC5: console_init (qtest.c:925)
==543813== by 0x10CAC5: main (qtest.c:1068)
```
追查後發現在 `add_param` 這裡會分配記憶體給 `param_ptr`：
```c
void add_param(char *name, int *valp, char *documentation, setter_function setter)
{
param_ptr next_param = param_list;
param_ptr *last_loc = ¶m_list;
while (next_param && strcmp(name, next_param->name) > 0) {
last_loc = &next_param->next;
next_param = next_param->next;
}
param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
ele->name = name;
ele->valp = valp;
ele->documentation = documentation;
ele->setter = setter;
ele->next = next_param;
*last_loc = ele;
}
```
接著追查釋放記憶體的程式碼，發現是在執行 `do_quit` 時會釋放記憶體，`do_quit` 是被放在 `finish_cmd` 中的，而 `finish_cmd` 又在 `qtest.c` 的主程式中被呼叫到：
```c
int main(int argc, char *argv[])
{
...
bool ok = true;
ok = ok && run_console(infile_name);
ok = ok && finish_cmd();
return ok ? 0 : 1;
}
```
這邊推測是由於 `ok` 為 `false`，因此不執行後續的 `finish_cmd`，因此將程式修改為如下，讓 `finish_cmd` 優先被執行：
```c
int main(int argc, char *argv[])
{
...
bool ok = true;
ok = ok && run_console(infile_name);
ok = finish_cmd() && ok;
return ok ? 0 : 1;
}
```
修改後錯誤訊息就消失了！
### 新增 shuffle 指令
在 `qtest.c` 中可以看到新增命令的程式碼位於 `console_init` 中：
```c
static void console_init()
{
ADD_COMMAND(new, " | Create new queue");
ADD_COMMAND(free, " | Delete queue");
ADD_COMMAND(
ih,
" str [n] | Insert string str at head of queue n times. "
"Generate random string(s) if str equals RAND. (default: n == 1)");
ADD_COMMAND(
it,
" str [n] | Insert string str at tail of queue n times. "
"Generate random string(s) if str equals RAND. (default: n == 1)");
...
}
```
在 `console.h` 中，我們可以找到 `ADD_COMMAND` 這個巨集，如下所示：
```c
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
參閱 [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor?type=view)，`#` 的作用是 stringification，讓一個表示式變成字串，而 `##` 的作用則是 concatenation，用來將巨集展開。
可以得知此巨集要求我們的指令函數的名稱必須要對應到指令的名字，因此我們除了在 `console_init` 中加入指令外，還必須要在 `qtest.c` 中加入一個對應的 `do_shuffle` 函示。
```c
static void console_init()
{
ADD_COMMAND(shuffle, " | Shuffle nodes in queue");
...
}
```
本次實作 shuffle 的演算法為 `Fisher–Yates shuffle`，其概念可以想像為有一組撲克牌，每次都將最後一張牌取出，並將此卡與剩餘未洗牌的隨機一張卡牌進行交換。
其步驟為：
1. 生成 1~(n-1) 中的隨機數字 k
2. 將第 k 個元素與第 (n-1) 個元素進行交換
3. 進行下一輪疊代，生成 1~(n-2) 中的隨機數字 k，疊代次數為 (n-1) 次
4. 得到最終洗牌後的結果
Pseudo code：
```c
-- 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]
```
實作：
```c
void swap_nodes(struct list_head *lhs, struct list_head *rhs)
{
if (!lhs || !rhs || lhs == rhs)
return;
struct list_head *lprev = lhs->prev, *lnext = lhs->next;
struct list_head *rprev = rhs->prev, *rnext = rhs->next;
lhs->next = rnext;
lhs->prev = rprev;
rhs->next = lnext;
rhs->prev = lprev;
rnext->prev = lhs;
rprev->next = lhs;
lnext->prev = rhs;
lprev->next = rhs;
}
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();
int i = l_meta.size;
struct list_head *swap;
for (struct list_head *ptr = l_meta.l->prev; --i; ptr = swap->prev) {
int k = rand() % (i + 1);
swap = l_meta.l->next;
for (int j = 0; j < k; j++)
swap = swap->next;
if (swap == ptr)
continue;
swap_nodes(swap, ptr);
}
show_queue(3);
return true;
}
```
依照 Pseudo code 進行實作，在交換節點的部分利用 `swap_nodes` 函數進行交換，然而實測後發現這種方法僅能夠交換 2 個不相鄰的節點，若是 2 個節點相鄰，會造成 `prev` 或是 `next` 接回自身的狀況。
參閱 [2020leon](https://hackmd.io/@6649/linux2022-lab0) 的共筆後得到啟發，可以利用 `list_move_tail` 操作來進行節點的交換，這種跳脫固有觀念的想法相當值得學習借鑑！
以下為修改後的程式碼：
```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();
int i = l_meta.size;
for (struct list_head *ptr = l_meta.l, *swap; --i; ptr = swap) {
swap = l_meta.l->next;
for (int j = 0; j < rand() % (i + 1); j++)
swap = swap->next;
list_move_tail(ptr->prev, swap);
list_move_tail(swap, ptr);
}
show_queue(3);
return true;
}
```
執行結果：
```shell
$ ./qtest
cmd> new
l = []
cmd> it a
l = [a]
cmd> it b
l = [a b]
cmd> it c
l = [a b c]
cmd> it d
l = [a b c d]
cmd> it e
l = [a b c d e]
cmd> shuffle
l = [a e d c b]
cmd> shuffle
l = [a b c e d]
cmd> shuffle
l = [b a e d c]
cmd> shuffle
l = [d a e b c]
cmd> shuffle
l = [b e c d a]
```
### 新增 web 指令
跟前面一樣，我們首先在 `console_init` 中增加以下命令：
```c
static void console_init()
{
ADD_COMMAND(web, " | Open tiny-web-server")
ADD_COMMAND(shuffle, " | Shuffle nodes in queue");
ADD_COMMAND(new, " | Create new queue");
...
}
```
由於我們希望實現在開啟 web 的同時，還能夠接受其他指令，因此在 `main` 函數中尋找等待命令輸入的迴圈，發現其位於 `linenoise.c` 中的 `linenoiseEdit` 內。
```c
/lab0-c/qtest.c
int main(int argc, char *argv[])
{
...
bool ok = true;
ok = ok && run_console(infile_name);
ok = ok && finish_cmd();
return ok ? 0 : 1;
}
/lab0-c/console.c
bool run_console(char *infile_name)
{
...
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);
}
}
...
}
/lab0-c/linenoise.c
static int linenoiseEdit(int stdin_fd, int stdout_fd,
char *buf, size_t buflen, const char *prompt)
{
...
while (1) {
...
switch (c) {
case ENTER: /* enter */
history_len--;
free(history[history_len]);
if (mlmode)
linenoiseEditMoveEnd(&l);
if (hintsCallback) {
/* Force a refresh without hints to leave the previous
* line as the user typed it after a newline. */
linenoiseHintsCallback *hc = hintsCallback;
hintsCallback = NULL;
refreshLine(&l);
hintsCallback = hc;
}
return (int) l.len;
case CTRL_C: /* ctrl-c */
errno = EAGAIN;
return -1;
case BACKSPACE: /* backspace *
...
}
...
```
:::warning
TODO
:::
## 參考資料
1. [共筆示範](https://hackmd.io/@cccccs100203/linux2020-lab0)
Sign in with Wallet
Connect another wallet