# 2022q1 Homework1 (lab0)
contributed by < [`chengingx`](https://github.com/chengingx) >
###### tags: `linux2022`
## 實驗環境
```shell
uname -a
Linux chenging 5.13.0-30-generic #33~20.04.1-Ubuntu SMP Mon Feb 7 14:25:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux
```
```shell
$ gcc --version
gcc (Ubuntu 7.5.0-6ubuntu2) 7.5.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): 6
On-line CPU(s) list: 0-5
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-8500 CPU @ 3.00GHz
Stepping: 10
CPU MHz: 3989.562
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 6000.00
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 9 MiB
NUMA node0 CPU(s): 0-5
```
## 相關巨集
### offsetof
在 [linux/stddef.h](https://github.com/torvalds/linux/blob/6f2b76a4a384e05ac8d3349831f29dff5de1e1e2/include/linux/stddef.h) 中定義了 `offsetof` 的實作，在較新的 GCC 中對應有效的 `__compiler_offsetof` 巨集
```c
#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER) __compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#endif
```
:::info
`(size_t)&((TYPE *)0)->MEMBER` 原理是將 TYPE 型態結構體的地址變更為 0，然後再加上成員 `MEMBER` 的偏移量
:::
[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof) 以下面程式碼作為舉例
```c
#include <stdio.h>
struct data {
short a;
char b;
double c;
};
int main() {
struct data x = {.a = 25, .b = 'A', .c = 12.45};
char *p = (char *) &x;
printf("a=%d\n", *((short *) p));
p += sizeof(short);
printf("b=%c\n", *((char *) p));
p += sizeof(char);
printf("c=%lf\n", *((double *) p));
return 0;
}
```
欲求 c 的正確位址可以使用
```c
p = (char *) &x + offsetof(struct data, c); // method 1
p = (char *) &x + offsetof(typeof(x), c); // method 2
```
在 [linux/compiler_types.h](https://github.com/torvalds/linux/blob/6f38be8f2ccd9babf04b9b23539108542a59fcb8/include/linux/compiler_types.h) 中定義了 `__compiler_offsetof`
```c
#define __compiler_offsetof(a, b) __builtin_offsetof(a, b)
```
### container_of
```c
/* container_of() - Calculate address of object that contains address ptr
* @ptr: pointer to member variable
* @type: type of the structure containing ptr
* @member: name of the member variable in struct @type
*
* Return: @type pointer of object containing ptr
*/
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
* 透過 `__typeof__` 得到 `type` 成員中 `member` 的型別，並將 `ptr` assign 給 `__pmember`，`__pmember` 指向 `member` 地址
* 本作業用到 `type` 為 `element_t` 其中 `member` 為 `list_head *`, e.g., `list_entry(ptr, element_t, list)`
* 由 `(char *) __pmember` 減去 `offsetof(type, member)` 得到此 `type` 結構體的起始位址
這裡將解釋為何要轉型成 `(char *)` ，在 [The (char *) casting in container_of() macro in linux kernel](https://stackoverflow.com/questions/20421910/the-char-casting-in-container-of-macro-in-linux-kernel) 舉了一個例子，定義一個稱為 `demo` 的結構
```c
struct demo {
int foo;
float bar;
};
```
接著宣告一個名為 `test` 的 `demo` 結構，`intptr` 為指向 `test` 中 `bar` 的指標
```c
struct demo test;
float *intptr = &test.bar;
```
由 `container_of` 就可以得到指向 `test` 的指標
```c
struct demo *owner = container_of(intptr, struct demo, bar);
```
可以展開為
```c=
struct demo *owner = {(
const typeof( ((struct demo*)0)->bar) *__mptr = (intptr);
(struct demo*)( (char *)__mptr - offsetof(struct demo,bar) );})
```
* 由第二行可見 `__mptr` 型態為 `float *`，為 `intptr` 的複本
* 由第三行可見將 `__mptr` 型態轉型為 `char *`，再作減去在 `struct demo` 中 `bar` 的 offset 運算
* 在這假設 `sizeof(int)` 為 4，那這 offset 就為 4
* 如果不轉型，那 4 會被解讀為 `float` 形式，由於 `sizeof(float)` 為 4，在這就會 back up 到 16 bytes
* 因此 `char *` 轉型是為了 ==get byte-level addresses for the calculation==
## 作業要求
[lab0](https://hackmd.io/@sysprog/linux2021-lab0) : 完成 queue.c 中尚未實作的介面
- [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`: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
- [x] `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
- [x] `q_swap`: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
- [x] `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
- [x] `q_sort`: 以==遞增順序==來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法
## 相關工具
* 程式撰寫風格
* 由 clang-format 達成一致的程式撰寫風格
```
$ clang-format -i *.[ch]
```
* [Git hook](https://www.atlassian.com/git/tutorials/git-hooks) 在 pre-commit 與 pre-push 進行 C/C++ 程式碼風風審查
* Git Commit Message
* git commit -a 透過編譯器調整 git commit message，不使用 git commit -m
* 靜態程式碼檢查
* 透過 [Cppcheck](http://cppcheck.sourceforge.net/) 進行靜態程式碼檢查
* 動態程式碼檢查
* 透過[Valgrind](https://valgrind.org/)分析使用者偵測記憶體錯誤資訊
## 開發過程
[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof) 提到 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的兩個關鍵概念為
1. 在自定義的結構中嵌入 `struct list_head`
2. 再藉由巨集指令 `container_of` 得到 `list` 個別節點的地址
### q_new
#### 實作
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
#### 實作軌跡
`list.h` 中 `INIT_LIST_HEAD` 可用於初始化 head 節點，可以先 malloc 一段記憶體空間給 head 在丟入此函式
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
`LIST_HEAD` 巨集則會生成 local variable 的 head
```c
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
```
使用 `qtest` 中的 `new` 測試
```shell
$ ./qtest
cmd> new
l = []
```
### q_free
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *cur, *next;
list_for_each_entry_safe(cur, next, head, list)
q_release_element(cur);
free(head);
}
```
#### 實作軌跡
`list_entry` 與 `container_of` 等價，當我們有佇列中節點的 `list_head` 地址以及節點的型態即可透過 `list_entry` 得到此節點地址
```c
#define list_entry(node, type, member) container_of(node, type, member)
```
`list_del` 可用於 `remove` 節點，但沒有 `delete` 掉
```c
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
定義 `LIST_POISONING` 時，會將刪除的節點的 `prev` 與 `next` 指向一個特定位址，當再次存取此節點時會產生例外狀況。
>TODO，這個位址怎麼定義的?
若要刪除所有節點，可以使用 `list_for_each_entry_safe` ， `safe` 會儲存下一個 `entry`
> TODO，巨集 `list_for_each_entry_safe` 留下了這句話 FIXME: remove dependency of __typeof__ extension
```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))
```
### q_insert_head
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *q_node = malloc(sizeof(element_t));
if (!q_node)
return false;
q_node->value = strdup(s);
if (!q_node->value) {
q_release_element(q_node);
return false;
}
list_add(&q_node->list, head);
return true;
}
```
#### 實作軌跡
`list_add` 函數定義在 `list.h` 中
```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;
}
```
[strcpy vs. strdup](https://stackoverflow.com/questions/14020380/strcpy-vs-strdup/14021039#14021039) 提到 strdup 與以下程式碼等價
```c
ptr2 = malloc(strlen(ptr1)+1);
strcpy(ptr2,ptr1);
```
> However, that is somewhat sub-optimal because both strlen and strcpy need to find the length of the string by checking if each character is a \0
但是 `strlen` 與 `strcpy` 都會確認每個字元是否為 `\0`，因此使用 `strdup` 較快，是 `memcpy` 版本
```c
char *strdup(const char *src) {
size_t len = strlen(src) + 1;
char *s = malloc(len);
if (s == NULL)
return NULL;
return (char *)memcpy(s, src, len);
}
```
使用 `./qtest` 進行測試 `q_new`、`q_insert_head`、`q_free`
```shell
$ ./qtest
cmd> new
l = []
cmd> ih apple
l = [apple]
cmd> ih banana
l = [banana apple]
cmd> ih cat
l = [cat banana apple]
cmd> free
l = NULL
```
### q_insert_tail
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *q_node = malloc(sizeof(element_t));
if (!q_node)
return false;
q_node->value = strdup(s);
if (!q_node->value) {
q_release_element(q_node);
return false;
}
list_add_tail(&q_node->list, head);
return true;
}
```
### q_remove_head
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *removed_node = list_first_entry(head, element_t, list);
list_del_init(&removed_node->list);
if (sp) {
strncpy(sp, removed_node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return removed_node;
}
```
#### 實作軌跡
`list_first_entry` 用於找尋 `list` 中的第一個 `entry`
```c
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
`list_del()` 可以 `remove` 節點，並沒有 `free` 掉內容，且狀態是 `uninitialized`
> The node has to be handled like an uninitialized node. Accessing the next or prev pointer of the node is not safe.
而 `list_del_init` 多了 initialize 步驟
```c
static inline void list_del_init(struct list_head *node)
{
list_del(node);
INIT_LIST_HEAD(node);
}
```
### q_release_element
```c
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
### 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)
{
if (!head || list_empty(head))
return false;
struct list_head *fast_ptr = head->next;
struct list_head *slow_ptr = head->next;
while (fast_ptr != head && fast_ptr != head->prev){
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
element_t *mid_node = list_entry(slow_ptr, element_t, list);
list_del_init(&mid_node->list);
q_release_element(mid_node);
return true;
}
```
#### 實作軌跡
參考 [Find the middle of a given linked list](https://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/) 的 two pointers 解法，分別為 `fast_ptr` 與 `slow_ptr`
### q_delete_dup
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
q_sort(head);
element_t *slow = NULL, *fast = NULL;
list_for_each_entry_safe (slow, fast, head, list) {
if (slow->list.next != head && strcmp(slow->value, fast->value) == 0) {
list_del_init(&slow->list);
q_release_element(slow);
}
}
return true;
}
```
### q_swap
```c
void q_swap(struct list_head *head)
{
if (!head)
return;
for (struct list_head *node = head->next;
(node != head) && (node->next != head); node = node->next) {
struct list_head *next_node = node->next;
list_move(node, next_node);
}
}
```
#### 實作軌跡
`list_move` 用於 remove `node` 原先位置，並將其加入在以 `head` 為首中 `list` 的第一個位置
```c
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
```
`list_add` 的實作如下，可以看見 `node` 被插入在原先 `head` 與 `head->next` 之間
```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;
}
```
### q_reverse
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node = NULL, *safe = NULL;
list_for_each_safe (node, safe, head)
list_move(node, head);
}
```
#### 實作軌跡
基於 `list_move` 的概念，traverse 整個 `list`，並將每次走訪到的 `node`，使之成為 `list` 中的第一個點，因此走到最後一個 `node` 時就是反向的
### q_sort
```c
struct list_head *mergeTwoLists(struct list_head *left, struct list_head *right)
{
struct list_head *head = NULL, **ptr = &head, **node = NULL;
for (; left && right; *node = (*node)->next) {
node = (strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) < 0)
? &left
: &right;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((__UINTPTR_TYPE__) left |
(__UINTPTR_TYPE__) right);
return head;
}
struct list_head *mergesort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *fast = head, *slow = head, *mid;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
mid = slow;
slow->prev->next = NULL;
struct list_head *left = mergesort(head);
struct list_head *right = mergesort(mid);
return mergeTwoLists(left, right);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
head->prev->next = NULL;
head->next = mergesort(head->next);
struct list_head **ptr = &head;
for (; (*ptr)->next != NULL; ptr = &((*ptr)->next)) {
(*ptr)->next->prev = *ptr;
}
(*ptr)->next = head;
head->prev = *ptr;
}
```
#### 實作軌跡
[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)提到如何撰寫 linked list sorting 問題，這裡需要使用到 merge sort 版本
## Valgrind分析
[lab0-c](https://github.com/sysprog21/lab0-c) 整合 [Valgrind](https://valgrind.org/) 可以找出記憶體相關問題，像是 memory leak, buffer overflow, dangling pointer 等問題，使用下面命令進行測試
```shell
$ valgrind -q --leak-check=full ./qtest -f traces/trace-01-ops.cmd
```
> -f IFILE Read commands from IFILE
輸出為
```shell
cmd> # Test of insert_head and remove_head
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih gerbil
l = [gerbil]
cmd> ih bear
l = [bear gerbil]
cmd> ih dolphin
l = [dolphin bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
l = [bear gerbil]
cmd> rh bear
Removed bear from queue
l = [gerbil]
cmd> rh gerbil
Removed gerbil from queue
l = []
cmd>
Freeing queue
==42518== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==42518== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==42518== by 0x4A8650E: strdup (strdup.c:42)
==42518== by 0x11033E: linenoiseHistoryAdd (linenoise.c:1236)
==42518== by 0x110EF4: linenoiseHistoryLoad (linenoise.c:1325)
==42518== by 0x10C27A: main (qtest.c:951)
==42518==
==42518== 100 bytes in 19 blocks are still reachable in loss record 2 of 3
==42518== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==42518== by 0x4A8650E: strdup (strdup.c:42)
==42518== by 0x1102B7: linenoiseHistoryAdd (linenoise.c:1236)
==42518== by 0x110EF4: linenoiseHistoryLoad (linenoise.c:1325)
==42518== by 0x10C27A: main (qtest.c:951)
==42518==
==42518== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==42518== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==42518== by 0x110303: linenoiseHistoryAdd (linenoise.c:1224)
==42518== by 0x110EF4: linenoiseHistoryLoad (linenoise.c:1325)
==42518== by 0x10C27A: main (qtest.c:951)
==42518==
```
:::info
* `strdup` 內容如下
```c
char *strdup(const char *s);
```
The strdup() function returns a pointer to a new string which is a duplicate of the string s. Memory for the new string is obtained with malloc(3), and can be freed with free(3).
* still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數
* 整合 linenoise 的好處是有自動補齊功能，也就是可以用 tab 鍵補齊命令，也可以使用上下鍵進行切換歷史紀錄
:::
根據發生 still reachable 提示知道發生在 `main` 函式中的 951 行
```c
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```
HISTORY_FILE 定義在 `console.h` 中
```c
#define HISTORY_FILE ".cmd_history"
```
`linenoiseHistoryLoad` 的函式定義如下
```c
int linenoiseHistoryLoad(const char *filename)
{
FILE *fp = fopen(filename, "r");
char buf[LINENOISE_MAX_LINE];
if (fp == NULL)
return -1;
while (fgets(buf, LINENOISE_MAX_LINE, fp) != NULL) {
char *p;
p = strchr(buf, '\r');
if (!p)
p = strchr(buf, '\n');
if (p)
*p = '\0';
linenoiseHistoryAdd(buf);
}
fclose(fp);
return 0;
}
```
它會呼叫到 `linenoiseHistoryAdd`，在 `linenoise.c` 的 1236 行為對應為下面程式碼第 7 行
```c=
int linenoiseHistoryAdd(const char *line)
{
...
/* Add an heap allocated copy of the line in the history.
* If we reached the max length, remove the older 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;
}
```
### -f 的影響
`qtest.c` 的 `main` 函式中定義以下三個 `object`
```c
char buf[BUFSIZE];
char *infile_name = NULL;
int c;
```
並透過 loop 讀取使用者命令
```c
while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
switch (c) {
case 'h':
usage(argv[0]);
break;
case 'f':
strncpy(buf, optarg, BUFSIZE);
buf[BUFSIZE - 1] = '\0';
infile_name = buf;
break;
...
}
}
```
接著解析使用者的輸入，一般呼叫流程為
:::info
main → run_console → cmd_select → interpret_cmd → parse_args
:::
`bool run_console(char *infile_name)` 中可以看見假如 `has_infile` 為 `true` 會執行 `else` 條件的指令
```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);
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
}
```
* 沒有 `-f` 會透過 `linenoise` 讀取 command
* 有 -f 會透過指定檔案 .cmd 內容
由此可以發現，當使用者不加上 `-f` 就不會呼叫到 `linenoiseFree` 來釋放掉 `history`，個人認為 Load the history at startup 可以不需使用到，接著再次進行測試
### finish_cmd() 問題
```shell
$ make valgrind
```
產生了新的問題
```shell
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
==48339== 32 bytes in 1 blocks are still reachable in loss record 1 of 28
==48339== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==48339== by 0x10C8F4: malloc_or_fail (report.c:189)
==48339== by 0x10D313: add_cmd (console.c:89)
==48339== by 0x10D6BE: init_cmd (console.c:408)
==48339== by 0x10C08F: main (qtest.c:944)
```
在 `console.c` 的 `init_cmd` 中有寫到
```c
ADD_COMMAND(help, " | Show documentation");
```
其中 `ADD_COMMAND` 定義在 `console.h`
```c
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
`add_cmd` 使用到 `malloc_or_fail`
```c
malloc_or_fail(sizeof(cmd_ele), "add_cmd");
```
這些產生的變數，包括 `cmd_list` 與 `param_list`，最後交由 `finish_cmd` 進行釋放，其中發生錯誤的關鍵為 `do_quit`
```c
bool ok = true;
if (!quit_flag)
ok = ok && do_quit(0, NULL);
```
`do_quit` 部份程式碼如下
```c
for (int i = 0; i < quit_helper_cnt; i++) {
ok = ok && quit_helpers[i](argc, argv);
}
```
其中 `quit_helpers` 為在 `queue.c` 中的 `queue_quit`，節錄其中程式碼如下
```c
size_t bcnt = allocation_check();
if (bcnt > 0) {
report(1, "ERROR: Freed queue, but %lu blocks are still allocated",
bcnt);
return false;
}
```
參考 [Laneser](https://hackmd.io/@laneser/linux2022_lab0#%E9%81%8B%E7%94%A8-Valgrind-%E6%8E%92%E9%99%A4-qtest-%E5%AF%A6%E4%BD%9C%E7%9A%84%E8%A8%98%E6%86%B6%E9%AB%94%E9%8C%AF%E8%AA%A4) 解法，原本 `qtest.c` 的 `main` 函式最後寫到
```c
ok = ok && finish_cmd();
```
當 `ok` 為 `false` 時，`finish_cmd()` 就不會被呼叫，因此改為
```c
ok = finish_cmd() && ok;
```
### Massif 測試
採用 `trace-15-perf.cmd` 進行測試
```shell
$ valgrind --tool=massif ./qtest -f traces/trace-15-perf.cmd
```
`trace-15-perf.cmd` 內容如下
```shell
option fail 0
option malloc 0
new
ih RAND 10000
sort
reverse
sort
free
new
ih RAND 50000
sort
reverse
sort
free
new
ih RAND 100000
sort
reverse
sort
free
```
```shell
$ massif-visualizer massif.out.76479
```
## 在 qtest 提供新的命令 shuffle
由前面描述可以知道，要提供新的命令需加入在 `console_init` 中，並以以下方式做新增
```c
ADD_COMMAND(new, " | Create new queue");
```
其中 `ADD_COMMAND` 為
```c
#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)
```
而 `add_cmd` 主要是利用 `CELE` 結構進行新增命令，定義在 `console.h` 中
```c
struct CELE {
char *name;
cmd_function operation;
char *documentation;
cmd_ptr next;
};
```
是以 linked list 形式表示，`operation` 就是定義新的函式關鍵，在開始實作以前先介紹 Fisher-Yates algorithm
### Fisher-Yates algorithm
#### Version 1
為闡述此演算法概念，先使用 Python 進行撰寫
```python
def shuffle1(arr):
shuffled = []
while len(arr) > 0:
rand_index = random.randrange(0, len(arr))
shuffled.append(arr[rand_index])
arr.pop(rand_index)
arr = shuffled
return arr
```
#### Version 2
```python
def shuffle2(arr):
rand_values = [random.random() for i in range(len(arr))]
rand_indexes = [i for i in range(len(arr))]
rand_indexes.sort(key=lambda i: rand_values[i])
arr = [arr[i] for i in rand_indexes]
return arr
```
時間複雜度主要受 sorting algorithm 影響，使用 merge sort 的時間複雜度為 $O(nlogn)$
#### Version 3
此版本為 modern version of Fisher-Yates algorithm，將要做的事情建立在同一 array 上，並分成 unshuffled 與 shuffled 兩部份
```python
def shuffle3(arr):
last_index = len(arr)-1
while last_index > 0:
rand_index = random.randint(0, last_index)
temp = arr[last_index]
arr[last_index] = arr[rand_index]
arr[rand_index] = temp
last_index -= 1
return arr
```
| Solution | Time complexity | Space complexity
| :------: | :------: | :------: |
| Fisher-Yates (old version) | $O(n^2)$ | $O(n)$ |
| Sorting according to assigned random values | $O(nlogn)$ | $O(n)$ |
| Fisher-Yates (modern version) | $O(n)$ | $O(1)$ |
來源 [How to shuffle an array (Fisher-Yates algorithm) - Inside code](https://www.youtube.com/watch?v=4zx5bM2OcvA)
### 實作
在 `qtest.c` 的 `main` 函式中加入
```c
ADD_COMMAND(shuffle, " | Shuffle nodes in queue");
```
接著實作 `q_shuffle`，參考 [Risheng](https://hackmd.io/@Risheng/linux2022-lab0#%E5%9C%A8-qtest-%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-shuffle) 實作 Fisher-Yates (modern version) 演算法
```c
static bool q_shuffle(struct list_head *head)
{
if (!head)
return false;
int size = q_size(head);
while (size) {
int number = rand() % size;
struct list_head *tmp = head->next;
for (int i = 0; i < number; i++)
tmp = tmp->next;
list_del(tmp);
list_add_tail(tmp, head);
size--;
}
return true;
}
```
測試結果
```shell
cmd> sort
l = [apple banana cat dog effort]
cmd> shuffle
l = [dog effort cat apple banana]
```
## 參考資料
* [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
* [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
* [Find the middle of a given linked list](https://www.geeksforgeeks.org/write-a-c-function-to-print-the-middle-of-the-linked-list/)
* [How to shuffle an array (Fisher-Yates algorithm) - Inside code](https://www.youtube.com/watch?v=4zx5bM2OcvA)
Sign in with Wallet
Connect another wallet