---
# System prepended metadata

title: 2022q1 Homework1 (lab0)
tags: [linux2022]

---

# 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` 個別節點的地址

![](https://i.imgur.com/tIFqHMI.png)


### 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
```

![](https://i.imgur.com/2j5o3z6.png)

## 在 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)