---
tags: linux2022
---

# 2022q1 Homework1 (lab0)
contributed by < `jj97181818` >

## queue.c
### q_new
建立新的「空」佇列

在想這裡應該要宣吿指向 `struct list_head` 或是 `element_t` 的 pointer，來回改了幾次，在後面實作到 q_insert_head 的 function 時，看了 list.h 裡面的 list_add function 的實作，要新增在最前面的新節點是接在 head 後面的，所以其實 head 本身不需要是 `element_t`，因為他的目的是要指向第一個節點，不需要存任何 value。

struct list_head *q_new()
{
    struct list_head *node = malloc(sizeof(struct list_head));
    if (!node) {
        return NULL;
    }
    INIT_LIST_HEAD(node);

    return node;
}

### q_free
釋放佇列所佔用的記憶體

先用 `list_for_each_safe` iterate 所有節點，因為該 function 允許刪除節點，然後用 `list_entry` 透過成員位址 node（struct list_head）存取到該節點（element_t）的開頭位址，並用 queue.c 中的 `q_release_element` 來 free 節點的 value 和節點本身。在所有節點的記憶體都釋放之後，再來 free head。

void q_free(struct list_head *l)
{
    struct list_head *node;
    struct list_head *safe;

    list_for_each_safe (node, safe, l) {
        element_t *p = list_entry(node, element_t, list);
        q_release_element(p);
    }
    free(l);
}

### q_insert_head
在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則)

先宣告一個指向 element_t 的指標 node，並配置記憶體給它。然後再配置記憶體給 node 的成員 value，大小為 s 本身的長度再加上 1（'\0'），如果沒有成功就將已配置給該節點的記憶體釋放。複製 s 的值到 node 的成員 value 中，再呼叫 `list_add` 將新節點插入 list 的最前面。

:::info
自己原本 `list_add(&(node->list), head);` 這樣寫 commit 的時候會被 pre-commit hook 拒絕，但是改 `list_add(&node->list, head);` 就會順利過了，但兩個是會做一樣的事情。

Following files need to be cleaned up:
queue.c
queue.c:58:5: error: Memory leak: node [memleak]
    return true;
    ^

Fail to pass static analysis.

> TODO: 寫一個更小且可重現 (reproducible) 的測試案例，提交到 Cppcheck 專案的錯誤追蹤。
> :notes: jserv
:::

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }

    element_t *node = malloc(sizeof(element_t));
    if (!node) {
        return false;
    }

    node->value = malloc((strlen(s) + 1) * sizeof(char));

    if (!node->value) {
        free(node);
        return false;
    }
    strncpy(node->value, s, strlen(s) + 1);
    list_add(&node->list, head);

    return true;
}

### q_insert_tail
在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則)

和 `q_insert_head` 一樣，除了 `list_add` 改成呼叫 `list_add_tail`。

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }

    element_t *node = malloc(sizeof(element_t));
    if (!node) {
        return false;
    }

    node->value = malloc((strlen(s) + 1) * sizeof(char));

    if (!node->value) {
        free(node);
        return false;
    }
    strncpy(node->value, s, strlen(s) + 1);
    list_add_tail(&node->list, head);

    return true;
}

### q_remove_head
在佇列開頭 (head) 移去 (remove) 給定的節點

檢查 head 是否為 NULL 或是 empty。`list_entry` 能取得第一個節點的起始位址，`list_del` 刪除第一個節點的連結。然後將要刪除節點的 value 複製給 sp，再將 sp 的最後一個字元改為 \0。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head)) {
        return NULL;
    }

    element_t *removed_element = list_entry(head->next, element_t, list);
    list_del(head->next);

    if (sp && removed_element->value) {
        strncpy(sp, removed_element->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    return removed_element;
}

### q_remove_tail
在佇列結尾 (tail) 移去 (remove) 給定的節點

和 `q_remove_head` 一樣，除了要刪掉的節點從 `head->next` 改成 `head->prev`。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head == NULL || list_empty(head)) {
        return NULL;
    }

    element_t *removed_element = list_entry(head->prev, element_t, list);
    list_del(head->prev);

    if (sp && removed_element->value) {
        strncpy(sp, removed_element->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    return removed_element;
}

### q_size
計算目前佇列的節點總量

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
移走佇列中間的節點

透過快慢指標，先將 fast 和 slow 的起始位置設定在第一個節點，然後 fast 一次移動兩步，slow 一次移動一步，當 fast 或 fast->next 等於 head 的位址時，slow 所在的位置即為中間節點。先用 `list_del` 移除中間節點的連結，再用 `list_entry` 取得該節點起始位置，呼叫q_release_element 將該節點的值和節點本身的記憶體釋放掉。

bool q_delete_mid(struct list_head *head)
{
    if (head == NULL || list_empty(head)) {
        return false;
    }

    struct list_head *fast = head->next, *slow = head->next;
    
    while (fast != head && fast->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }
    
    list_del(slow);
    element_t *p = list_entry(slow, element_t, list);
    q_release_element(p);

    return true;
}

### q_delete_dup
在已經排序的狀況，移走佇列中具備重複內容的節點

走訪整個 queue，當現在走到的節點與下一個節點的值相同時，就將現在的節點刪除，然後設定 `duplicate = true`。當現在走到的節點與下一個節點不同，且 `duplicate` 的值是 `true` 時，也要將現在走到的節點刪除，這是為了要刪除連續重複節點的最後一個。

bool q_delete_dup(struct list_head *head)
{
    if (!head) {
        return false;
    }

    element_t *cur;
    element_t *safe;
    bool duplicate = false;
    list_for_each_entry_safe (cur, safe, head, list) {
        if (cur->list.next != head &&
            !strcmp(cur->value,
                    list_entry(cur->list.next, element_t, list)->value)) {
            list_del(&cur->list);
            q_release_element(cur);
            duplicate = true;
        } else {
            if (duplicate) {
                list_del(&cur->list);
                q_release_element(cur);
                duplicate = false;
            }
        }
    }
    return true;
}

### q_swap
交換佇列中鄰近的節點

走訪整個 queue，先將節點刪除連結，再將它連結加到下一個節點的後面，然後 `safe` 要成為 `node` 節點的下一位，因為接下來 `node` 會存取 `safe` 的位置，需要讓 `node` 指向兩兩 swap 中的前面那一個。

void q_swap(struct list_head *head)
{
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        if (node->next == head) {
            return;
        }
        list_del(node);
        list_add(node, safe);
        safe = node->next;
    }
}

### q_reverse
以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點

走訪整個 queue，先將節點刪除連結，再將它連結加到原本 queue 的最後一個節點 `last` 後面。一直重複這個動作，直到走訪到 `last` 結束。

void q_reverse(struct list_head *head)
{
    if (!head || !list_empty(head)) {
        return;
    }
    struct list_head *node, *safe;
    struct list_head *last = head->prev;

    list_for_each_safe (node, safe, head) {
        if (node == last) {
            return;
        }
        list_del(node);
        list_add(node, last);
    }
}

### q_sort
以遞增順序來排序鏈結串列的節點

參考了 [你所不知道的 C 語言: linked list 和非連續記憶體](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 Two Sorted Lists 的 indirect pointer 寫法、[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的 merge sort 寫法，以及 [mm0809 的共筆](https://hackmd.io/@2QYhHFatQmWFUgzITEcRjA/B1lsUihy9#q_sort) q_sort 的寫法。

1. 先讓最後一個節點的 `next` 指向 NULL，以 `next` 的方向來看，queue 變成不是 circular。
2. 然後呼叫 `mergeSortList`，找 queue 的中間節點，將 queue 分成兩半，在遞迴呼叫自己，將分開的兩半分別再繼續分成兩半，直到分成只有一個節點的時候（只有自己就是已排序的狀態），開始呼叫 `merge`。
3. `merge` 會將兩個 queue 依據值由小到大合併，一直呼叫 `merge` 直到整個 queue 都被 merge 完成。
4. 因為前面的動作只有專注在節點的 `next` 有連接到對的節點，所以最後需要將 `prev` 修正成對的節點。

struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
    struct list_head *head = NULL;
    struct list_head **ptr = &head;

    for (; l1 && l2; ptr = &(*ptr)->next) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) < 0) {
            *ptr = l1;
            l1 = l1->next;
        } else {
            *ptr = l2;
            l2 = l2->next;
        }
    }
    *ptr = (struct list_head *) ((uintptr_t) l1 | (uintptr_t) l2);
    return head;
}
struct list_head *mergeSortList(struct list_head *head)
{
    if (!head || !head->next) {
        return head;
    }

    struct list_head *fast = head->next, *slow = head;

    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = slow->next;
    slow->next = NULL;
    slow = head;

    struct list_head *l1 = mergeSortList(slow);
    struct list_head *l2 = mergeSortList(fast);

    return merge(l1, l2);
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return;
    }

    head->prev->next = NULL;
    head->next = mergeSortList(head->next);

    struct list_head *cur = head->next;
    struct list_head *prev = head;

    while (cur != NULL) {
        cur->prev = prev;
        prev = cur;
        cur = cur->next;
    }
    prev->next = head;
    head->prev = prev;
}

## 引入 lib/list_sort.c
先將 [`lib/list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 和 [`include/linux/list_sort.h`](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 放到 lab0 的專案下，然後在 `Makefile` 加入要編譯的 list_sort.c。

### 切換 sort
宣告一個 sortmode 變數，用來切換要執行的 sort 函式。

/* original written sort: 0, lib/list_sort.c: 1 */
static int sortmode = 0;

在 `qtest.c` 中加入 option 參數 sort，根據不同的 sortmode，來切換 sort。

add_param("sort", &sortmode,
          "Switch between lib/list_sort.c and the original written sort", NULL);

原本執行 q_sort 的地方，根據 sortmode 來確定要執行原本自己寫的 sort 或 `lib/list_sort.c`。
因為實作 compare function 時不會用到 list_sort 的第一個參數，所以第一個參數為 NULL，第二個參數和原本呼叫 q_sort 傳入的參數一樣，第三個是放 compare function 的 function pointer。

if (exception_setup(true)) {
+    if (sortmode == 0) {
        q_sort(l_meta.l);
+    }
+    else {
+        list_sort(NULL, l_meta.l, cmp);
+    }
}

### compare function
在 `list_sort.h` 有定義 compare function 回傳值必須為整數，參數有三個，第一個是 priv，但用不到，第二、第三個參數為指向 struct list_head 的指標，透過這兩個指標所在節點的值去比大小。

typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *,
		const struct list_head *, const struct list_head *);

實作出的 compare function：(在 `qtest.c`)

static int cmp(void * priv, const struct list_head *a, const struct list_head *b) {
    return strcmp(list_entry(a, element_t, list)->value, 
                  list_entry(b, element_t, list)->value);
}

### likely 和 unlikely 巨集
`lib/list_sort.c` 有用到在 [linux/compiler.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 下的巨集：likely, unlikely，將兩個巨集直接搬到 `list_sort.c` 當中：

# define likely(x)	__builtin_expect(!!(x), 1)
# define unlikely(x)	__builtin_expect(!!(x), 0)

### 將型別 u8 -> uint8_t
在 `merge_final` 中會用到型別 `u8`，因為未定義 `u8` 所以會錯誤，將其改成 `uint8_t`，並加上標頭檔 `#include <stdint.h>` 即可。

### 移除不需要的程式碼
將原本 linux 相關的標頭檔刪除

然後移除：

EXPORT_SYMBOL(list_sort);

### 抑制 cppcheck 檢查
cppcheck 認定變數 head 沒有指派任何值，但是 head 在後面是有被指派值的。

list_sort.c:18:23: style: Variable 'head' is not assigned a value. [unassignedVariable]
    struct list_head *head, **tail = &head;
                      ^

Fail to pass static analysis.

解決方法是在該變數宣告的上一行加上：

// cppcheck-suppress unassignedVariable
struct list_head *head, **tail = &head;

抑制 cppcheck 檢查該行 unassigned 變數。

## 比較 lib/list_sort.c 與自己實作 sort 的效能
分別測試自己寫的 sort 和引入到本專案的 `lib/list_sort.c` 各自 sort 字串，並測試 5 次做平均。
+ `trace-original-sort.cmd`：

# original sort
option verbose 1
option sort 0
new
ih RAND 1000000
time sort
free

+ `trace-kernel-sort.cmd`：

# lib/list_sort.c
option verbose 1
option sort 1
new
ih RAND 1000000
time sort
free

執行 `./qtest -f traces/trace-original-sort.cmd && ./qtest -f traces/trace-linux-sort.cmd`

得到的結果：

| sort 的字串數量 | original sort | linux sort |
| -------- | -------- | -------- |
| 100000 | 0.029(s) | 0.024(s) |
| 1000000 | 0.637(s) | 0.489(s) |

kernel 的 sort 表現得比較好，分別快了 20.8% 和 30.2%。

## 研讀 Linux 核心原始程式碼的 lib/list_sort.c
+ 用 buttom up 實作 merge sort 對 cache 較友善，因為過程中就是一直合併，cache 被參照到的機會是更大的。
+ 而 top down 是會先做 partition 再來 merge，但 partition 本身對 cache 不友善，在 cache 移進移出（內容不斷更新），導致 cache thrashing。
### 合併方式
合併方式是當有 $3 * 2^k$ 個節點時，合併前兩個 $2^k$ 變成 $2^{k + 1}$，並留下一個 $2^k$ 不動，維持著合併：不合併為 2 : 1 的比例，因為只要 $3 * 2^k$ 可以放得進 L1 cache，可以避免 cache thrashing。

`count` 為 pending list 中節點的數量，在 `count` 變 `count + 1` 後，可以觀察到第 `k` 個 bit 會改為 1，0 ~ `k - 1` 個 bit 會變 0，此時會將 2 個 $2^k$ 合併，並留下一個 $2^k$。

### 何時合併
每當 `count + 1`，可能會有兩種情況：
#### 1. 當 `count + 1` 後為 $2^k$，就不合併（只有 leading 1 是 1，其餘都為 0）
+ 例子：
`count` = 1（$0001_2$）
`count + 1` = 2（$0010_2$）
因為 `count + 1` 為 2 是 2 的倍數，所以此種情況不合併。

#### 2. 當 count + 1 後不為 $2^k$，就合併
+ 例子：
`count` = 2（$0010_2$）
`count + 1` = 3（$0011_2$）
因為 `count + 1` 為 3 不是 2 的倍數，所以此種情況要合併。
+ 可以觀察到在 `count` 變 `count + 1` 後，第 k 個 bit 會改為 1，0 ~ `k - 1` 個 bit 會變 0。而這裡的 k 為 0，所以會將 2 個 $2^0$ 合併，並留下一個 $2^0$，也就是合併 2 個 1 為 2，留一個 1 不合併。

以下是 count 從 0 一直加到 16 merge 的狀況：
（括號內是當次被合併的節點加起來的節點數量，用加號來分隔尚未合併的節點，黃色底則是告知此次合併的是 1 + 1, 2 + 2 或 4 + 4 等。）
| count 變化 | count 二進位 | merge | pending 上的節點|
| -------- | -------- | -------- | -------- |
| 0 -> 1 | 0000 -> 0001 | no（$2^0$） | 1 |
| 1 -> 2 | 0001 -> 0010 | no（$2^1$） | 1 + 1 |
| 2 -> 3 | 0010 -> 001==1== | yes | (2) + 1 |
| 3 -> 4 | 0011 -> 0100 | no（$2^2$） | 2 + 1 + 1 |
| 4 -> 5 | 0100 -> 010==1== | yes | 2 + (2) + 1|
| 5 -> 6 | 0101 -> 01==1==0 | yes | (4) + 1 + 1|
| 6 -> 7 | 0110 -> 011==1== | yes | 4 + (2) + 1|
| 7 -> 8 | 0111 -> 1000 | no（$2^3$） | 4 + 2 + 1 + 1|
| 8 -> 9 | 1000 -> 100==1== | yes | 4 + 2 + (2) + 1|
| 9 -> 10 | 1001 -> 10==1==0 | yes | 4 + (4) + 1 + 1|
| 10 -> 11 | 1010 -> 101==1== | yes | 4 + 4 + (2) + 1|
| 11 -> 12 | 1011 -> 1==1==00 | yes | (8) + 2 + 1 + 1|
| 12 -> 13 | 1100 -> 110==1== | yes | 8 + 2 + (2) + 1|
| 13 -> 14 | 1101 -> 11==1==0 | yes | 8 + (4) + 1 + 1|
| 14 -> 15 | 1110 -> 111==1== | yes | 8 + 4 + (2) + 1|
| 15 -> 16 | 1111 -> 10000 | no（$2^4$） | 8 + 4 + 2 + 1 + 1 |

### list_sort

__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
	struct list_head *list = head->next, *pending = NULL;
	size_t count = 0;	/* Count of pending */

	if (list == head->prev)	/* Zero or one elements */
		return;

	/* Convert to a null-terminated singly-linked list. */
	head->prev->next = NULL;

+ priv: 從 `merge` 函式可以看到 priv 會被當作 cmp 的參數傳入，在其他地方不會用到。
+ head: 傳入指向 struct list_head 的指標，和原本自己寫的 `q_sort` 傳入的參數一樣
+ cmp: compare function，以 function pointer 的型別傳入
cmp 參數有考慮到通用性，但會增加 function call 的成本。

list 指向 head 的第一個節點，pending 指向 NULL，先檢查是否沒有任何元素或只有一個元素，然後將 head 前一個節點指向的下一個位置指向 NULL，將雙向 linked list 變成單向的。

	do {
		size_t bits;
		struct list_head **tail = &pending;

		/* Find the least-significant clear bit in count */
		for (bits = count; bits & 1; bits >>= 1)
			tail = &(*tail)->prev;
		/* Do the indicated merge */
		if (likely(bits)) {
			struct list_head *a = *tail, *b = a->prev;

			a = merge(priv, cmp, b, a);
			/* Install the merged result in place of the inputs */
			a->prev = b->prev;
			*tail = a;
		}

		/* Move one element from input list to pending */
		list->prev = pending;
		pending = list;
		list = list->next;
		pending->next = NULL;
		count++;
	} while (list);

在 while 迴圈中，會先讓 tail 往前移動到待 merge 的節點，然後在 if 判斷是否需要 merge，最後移動 pending 和 list 的位置，直到 list 沒有節點。pending 從沒有節點，然後一次次將節點從 list 中搬到 pending，等到 list 沒有節點就代表現階段結束了。

	/* End of input; merge together all the pending lists. */
	list = pending;
	pending = pending->prev;
	for (;;) {
		struct list_head *next = pending->prev;

		if (!next)
			break;
		list = merge(priv, cmp, pending, list);
		pending = next;
	}
	/* The final merge, rebuilding prev links */
	merge_final(priv, cmp, head, pending, list);
}
EXPORT_SYMBOL(list_sort);

### merge

__attribute__((nonnull(2, 3, 4))) static struct list_head *
merge(void *priv, list_cmp_func_t cmp, struct list_head *a, struct list_head *b)
{
    // cppcheck-suppress unassignedVariable
    struct list_head *head, **tail = &head;

    for (;;) {
        /* if equal, take 'a' -- important for sort stability */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = &a->next;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

當 `cmp(priv, a, b) <= 0` 表示 a 的值小於 b，因為由小排序到大，所以先接 a 再接 b，`cmp(priv, a, b) > 0` 表示 a 的值大於 b，則是先接 b 再接 a。
其中 `head` 會在排序過 list 的最前面，並回傳回去。

### 排序過程圖示
以 4, 3, 2, 1 的 list 為例做 list_sort 排序，隨著 `count` 增加，`pending` 內節點數量漸漸增加，而 `list` 內的節點數量漸漸減少：
#### count = 0 -> count = 1
+ list 指向 head->next：

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
   
    head:right:e -> node4:w
    node4:left:w -> head:e
    node4:right:e -> node3:w
    node3:left:w -> node4:e
    node3:right:e -> node2:w
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node4:n
}

+ 因為 bits 為 0，不需 merge。`list->prev = pending` 因為 pending 為 NULL，所以 list->prev 也指向 NULL：

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
   
    head:right:e -> node4:w
    node4:right:e -> node3:w
    node3:left:w -> node4:e
    node3:right:e -> node2:w
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node4:n
}

+ pending 節點數量 + 1，list 節點數量 - 1，count + 1，`pending->next = NULL`：

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
    
   
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:left:w -> node4:e
    node3:right:e -> node2:w
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node3:n
    pending -> node4:n
    tail -> pending:n
}

#### count = 1 -> count = 2

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
    
   
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:left:w -> node4:e
    node3:right:e -> node2:w
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node3:n
    pending -> node4:n
    tail -> node4:left:s
}

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    
   
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:left:w -> node4:e
    node3:right:e -> node2:w[color="white"]
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node2:n
    pending -> node3:n
}

#### count = 2 -> count = 3

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
    a [label="a", style="normal", color="white"]
    b [label="b", style="normal", color="white"]
   
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:left:w -> node4:e
    node3:right:e -> node2:w[color="white"]
    node3:right:e -> node4:e
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node2:n
    pending -> node3:n
    tail -> pending
    a -> node3:n
    b -> node4:n
}

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
    a [label="a", style="normal", color="white"]
    b [label="b", style="normal", color="white"]
   
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:right:e -> node2:w[color="white"]
    node3:right:e -> node4:e
    node2:left:w -> node3:e
    node2:right:e -> node1:w
    node1:left:w -> node2:e
    list -> node2:n
    pending -> node3:n
    tail -> pending
    a -> node3:n
    b -> node4:n
}

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
   
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:right:e -> node2:w[color="white"]
    node3:right:s -> node4:e
    node2:left:w -> node3:e
    node2:right:e -> node1:w[color="white"]
    node1:left:w -> node2:e
    list -> node1:n
    pending -> node2:n
    tail -> pending
}

#### count = 3 -> count = 4

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
   
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:right:e -> node2:w[color="white"]
    node3:right:s -> node4:e
    node2:left:w -> node3:e
    node2:right:e -> node1:w[color="white"]
    node1:left:w -> node2:e
    list -> node1:n
    pending -> node2:n
    tail -> node3:left:s
}

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
   
    head:right:e -> node4:w
    node4:right:e -> node3:w[color="white"]
    node3:right:e -> node2:w[color="white"]
    node3:right:s -> node4:e
    node2:left:w -> node3:e
    node2:right:e -> node1:w[color="white"]
    node1:left:w -> node2:e
    pending -> node1:n
    tail -> node3:left:s
}

#### count = 4

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
    next [label="next", style="normal", color="white"]
    a [label="a", style="normal", color="white"]
    b [label="b", style="normal", color="white"]
   
    head:right:e -> node1:w
    node4:right:e -> node3:w[color="white"]
    node3:right:e -> node2:w[color="white"]
    node3:right:s -> node4:e
    node2:left:w -> node3:e
    node1:left:w -> head:e
    pending -> node2:n
                     next -> node3:n
    list -> node1:n
    a -> node2:n
    b -> node1:n
}

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
    next [label="next", style="normal", color="white"]
    a [label="a", style="normal", color="white"]
    b [label="b", style="normal", color="white"]
   
    head:right:e -> node1:w
    node4:right:e -> node3:w[color="white"]
    node3:right:e -> node2:w[color="white"]
    node3:right:s -> node4:e
    node2:left:w -> node3:e
    node1:left:w -> head:e
    pending -> node2:n
                     next -> node3:n
    list -> node1:n
    tail -> node1:n
    a -> node2:n
    b -> node2:n
}

digraph ele_list {
    rankdir=LR
    node[shape=record]
    
    head [label="head|{<left>prev|<right>next}", style="bold"]
    node4 [label="4|{<left>prev|<right>next}", style="bold"]
    node3 [label="3|{<left>prev|<right>next}", style="bold"]
    node2 [label="2|{<left>prev|<right>next}", style="bold"]
    node1 [label="1|{<left>prev|<right>next}", style="bold"]
    list [label="list", style="normal", color="white"]
    pending [label="pending", style="normal", color="white"]
    tail [label="tail", style="normal", color="white"]
    next [label="next", style="normal", color="white"]
    a [label="a", style="normal", color="white"]
    b [label="b", style="normal", color="white"]
   
    // head:left -> node4
    // head:right -> node1
    // node1:left -> head
    // node1:right -> node2
    // node2:left -> node1
    // node2:right -> node3
    // node3:left -> node2
    // node3:right -> node4
    // node4:left -> node3
    // node4:right -> head
    // pending -> node2:n
    // next -> node3:n
    // list -> node1:n
    // tail -> node1:n
    // a -> node2:n
    // b -> node2:n
    head:right:e -> node1:w
    node1:left:w -> head:e
    node1:right:e -> node2:w
    node2:left:w -> node1:e
    node2:right:e -> node3:w
    node3:left:w -> node2:e
    node3:right:e -> node4:w
    node4:left:w -> node3:e
    list -> node1:n
    pending -> node2:n
    a -> node2:n
    b -> node4:n
    tail -> node4:n
}

## 在 qtest 提供新的命令 shuffle
### 實作
在 qtest.c 中的 `console_init()` 加入：

ADD_COMMAND(shuffle,
                "                | Shuffle nodes in queue");

然後另外宣告一個 `do_shuffle()`：

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();

    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();

    show_queue(3);
    return !error_check();
}

在 queue.c 中宣告 `shuffle()`：
利用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法來實作洗牌（shuffle）

1. 先用 `q_size` 取得 queue 的大小 `len`。
2. 隨機從 0 ~ (len - 1) 中抽出一個數字 `random`，然後 `old` 將指向從前面數來第 random 個節點，`new` 會指向最後一個未被抽到的節點，將 `old` 和 `new` 指向的節點的值交換，再將 len - 1。
3. 隨著 len 大小變小，已經被抽到過，並交換值到 queue 後面的會愈來愈多，直到所有的節點都已經被抽到過，shuffle 就結束了。

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return;
    }

    struct list_head *node;
    struct list_head *last = head;

    for (int len = q_size(head); len > 0; len--) {
        int random = rand() % len;
        node = head->next;

        for (int i = 0; i < random; i++) {
            node = node->next;
        }
        last = last->prev;

        element_t *choose_entry = list_entry(node, element_t, list);
        element_t *last_entry = list_entry(last, element_t, list);

        char *temp = choose_entry->value;
        choose_entry->value = last_entry->value;
        last_entry->value = temp;
    }
}

### 統計方法驗證 shuffle
[Pearson's chi-squared test](https://en.wikipedia.org/wiki/Pearson%27s_chi-squared_test) 能檢驗虛無假說（Null hypothesis），即某特定事件在樣本中觀察到的頻率分佈與特定理論分佈一致，事件必須是互斥且機率為 1。

如果要 shuffle 三個不同的數字，會出現六種可能的結果，彼此是互斥的，且發生機率加起來為 1。那假設 shuffle 是公平的（六種結果發生的機率相同），並遵守 Uniform distribution，那虛無假說為：

+ $H_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
+ $H_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同

接下來透過 Pearson's chi-squared test 來驗證 shuffle 三個數字的頻率是符合 Uniform distribution:

#### 1. 先計算 chi-squared test statistic $X^2$

$$
X^2 = \sum_{i=1}^n {(O_i - E_i)^2 \over E_i}
$$

+ $X^2$: Pearson's cumulative test statistic
+ $O_i$: the number of observations of type i
+ $E_i$: the expected count of type i

E:  166666
O:  {'abc': 166391, 'bac': 166829, 'bca': 166807, 'acb': 166790, 'cab': 166862, 'cba': 166321}
0.45375181500726003
0.15941463765855063
0.11928647714590858
0.0922563690254761
0.23049692198768795
0.7141528566114265
sum:  1.76935907743631

在測試 shuffle 1000000 次後，六種結果各自的頻率如下表：
|| 觀察到的頻率| 期待的頻率 |${(O_i - E_i)^2 \over E_i}$|
| -------- | -------- | -------- |---|
| [1, 2, 3] | 166391 | 166666 |0.45375181500726003|
| [2, 1, 3] | 166829 | 166666 |0.15941463765855063|
| [2, 3, 1] | 166807 | 166666 |0.11928647714590858|
| [1, 3, 2] | 166790 | 166666 |0.0922563690254761|
| [3, 1, 2] | 166862 | 166666 |0.23049692198768795|
| [3, 2, 1] | 166321 | 166666 |0.7141528566114265|
|Total|||1.76935907743631|

$X^2$ = 1.76935907743631

#### 2. 決定自由度（degrees of freedom）
對於 N 個隨機樣本而言，自由度為 N - 1。我們 shuffle 3 個數字會有六種結果，因為加起來機率為 1 ，所以實際上可以自由變換的變數只有五個，其中一個結果的機率為 1 減去另外五個結果發生的機率，所以自由度為 5。

#### 3. 選擇顯著水準
+ [顯著水準（Significance level）α](https://en.wikipedia.org/wiki/Statistical_significance) 代表在虛無假說（$H_0$）為真下，錯誤地拒絕 $H_0$ 的機率，即型一錯誤發生之機率。
α = P(拒絕 $H_0$ | $H_0$ 為真)
我們 alpha 設定為常見的 0.05。
+ [P value](https://zh.wikipedia.org/wiki/P%E5%80%BC)
從[卡方分布表](https://zh.wikipedia.org/wiki/%E5%8D%A1%E6%96%B9%E5%88%86%E4%BD%88)找我們的 P value，我們的自由度為 5，$X^2$ 為 1.76935907743631，因為 1.61 < 1.76935907743631 < 2.34，於是 P value 介於 0.9 和 0.8 之間。


#### 4. 統計檢定的結果不拒絕虛無假說
對於要拒絕的虛無假說（$H_0$），觀察到的結果必須具有統計顯著性，即觀察到的 P value 小於預先指定的顯著水準 α。

因為 P value（0.8~0.9）> alpha（0.05），統計檢定的結果不拒絕虛無假說（$H_0$）
也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻。

從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的。

### 測試程式
看到在 `scripts/driver.py` 有用到 `subprocess.call()` 來產生新 process 執行指定的命令，然後等待命令完成後取得 return code，後續再檢查 return code 是否為 0 來得知測試是否成功。

因為這裡的測試我想取得 stdout，所以改用 [`subprocess.run()`](https://docs.python.org/3/library/subprocess.html#subprocess.run) ，會執行參數中指定的命令，然後等待命令完成後，會回傳一個 CompletedProcess instance。
取得 `CompletedProcess.stdout` 再做編碼後，可以得到 stdout 的字串。
後續再將得到的輸出字串取出 shuffle 過後的結果，放到 `nums` 變數中。

:::spoiler python script

import subprocess
import re
import random
from itertools import permutations
import random

# 測試 shuffle 次數
test_count = 1000000
input = "new\nit 1\nit 2\nit 3\nit 4\n"
for i in range(test_count):
    input += "shuffle\n"
input += "free\nquit\n"

# 取得 stdout 的 shuffle 結果
command='./qtest -v 3'
clist = command.split()
completedProcess = subprocess.run(clist, capture_output=True, text=True, input=input)
s = completedProcess.stdout
startIdx = s.find("l = [1 2 3 4]") 
endIdx = s.find("l = NULL")
s = s[startIdx + 14 : endIdx]
Regex = re.compile(r'\d \d \d \d')
result = Regex.findall(s)

def permute(nums):
    nums=list(permutations(nums,len(nums)))
    return nums

def chiSquared(observation, expectation):
    return ((observation - expectation) ** 2) / expectation 

# shuffle 的所有結果   
nums = []
for i in result:
    nums.append(i.split())

# 找出全部的排序可能
counterSet = {}
shuffle_array = ['1', '2', '3', '4']
s = permute(shuffle_array)

# 初始化 counterSet
for i in range(len(s)):
    w = ''.join(s[i])
    counterSet[w] = 0

# 計算每一種 shuffle 結果的數量
for num in nums:
    permutation = ''.join(num)
    counterSet[permutation] += 1
        
# 計算 chiSquare sum
expectation = test_count // len(s)
c = counterSet.values()
chiSquaredSum = 0
for i in c:
    chiSquaredSum += chiSquared(i, expectation)
print("Expectation: ", expectation)
print("Observation: ", counterSet)
print("chi square sum: ", chiSquaredSum)

產生直方圖的程式：

import matplotlib.pyplot as plt
import numpy as np
permutations = counterSet.keys()
counts = counterSet.values()

x = np.arange(len(counts))
plt.bar(x, counts)
plt.xticks(x, permutations)
plt.xlabel('permutations')
plt.ylabel('counts')
plt.title('Shuffle result')
plt.show()

:::

測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖：

:::info
藉由測試程式發現自己最初寫的 shuffle 程式寫錯了，在所有 shuffle 組合中，只有其中 2 ~ 3 種組合會大量的出現，猜想是因為我在每次 shuffle 時都重設亂數種子，而亂數種子是根據時間當作參數，測試時會在短時間跑很多次，因為時間很短，所以很多次的 shuffle 都會取得一樣的時間參數，導致跑出來的只有少少的幾種組合。

把重設亂數種子刪除後，跑出來的結果就正常了，較平均地出現每種組合。
:::

## 在 qtest 提供新的命令 web
有參考 [PinLin 的 web 實作](https://hackmd.io/@PinLin/linux2022-lab0#%E6%96%B0%E5%A2%9E%E5%91%BD%E4%BB%A4-web)

先試跑 [tiny-web-server](https://github.com/7890/tiny-web-server) 專案，可以在瀏覽器看到跑該專案的目錄下有什麼檔案
，預設的 port 為 9999。


先按照[整合 tiny-web-server](https://hackmd.io/@sysprog/linux2022-lab0#%E6%95%B4%E5%90%88-tiny-web-server)的引導，有三種方法，其中第三種方法最符合我們的需求。

### 一、嘗試用 select() 同時處理 stdin 及 socket

#### 在 `linenoiseEdit` 中加入以下程式碼：

while (1) {
    char c;
    int nread;
    char seq[3];

    fd_set set;
    
    FD_ZERO(&set);
    FD_SET(listenfd, &set);
    FD_SET(stdin_fd, &set);
    int rv = select(listenfd + 1, &set, NULL, NULL, NULL);
    struct sockaddr_in clientaddr;
    socklen_t clientlen = sizeof clientaddr;
    int connfd;

    switch (rv) {
    case -1:
        perror("select"); /* an error occurred */
        continue;
    case 0:
        printf("timeout occurred\n"); /* a timeout occurred */
        continue;
    default: 
        if (FD_ISSET(listenfd, &set)) {
            connfd = accept(listenfd,(SA *) &clientaddr, &clientlen);
            char *p = process(connfd, &clientaddr);
            strncpy(buf, p, strlen(p) + 1);
            close(connfd);
            free(p);
            return strlen(p);
        } else if (FD_ISSET(stdin_fd, &set)) {
            nread = read(l.ifd, &c, 1);
            if (nread <= 0)
                return l.len;
        }
        break;
    }
}

int select(int nfds, fd_set *restrict readfds,
           fd_set *restrict writefds, fd_set *restrict exceptfds,
           struct timeval *restrict timeout);

+ 查詢 [select(2)](https://man7.org/linux/man-pages/man2/select.2.html) ，可得知 select 這個 system call 有五個參數：
+ nfds: 要被設為三組（readfds, writefds, exceptfds）中 file descriptor 最高編號再加 1
+ readfs: 集合中的 file descriptors 會被監看是否準備好被 read
+ writefds: 集合中的 file descriptors 會被監看是否準備好被 write
+ exceptfds: 集合中的 file descriptors 會被監看是否準備好例外情況
+ timeout: 是 timeval 結構，指定 `select()` 要等一個 file descriptor 變成 ready 多少時間。如果 timeout 設定為 NULL，`select()` 將會無限期的等待一個 file descriptor 變成 ready。

int accept(int sockfd, struct sockaddr *restrict addr,
           socklen_t *restrict addrlen);

+ 查詢 [accept(2)](https://man7.org/linux/man-pages/man2/accept.2.html) ，可得知 accept 這個 system call 有三個參數：
+ sockfd: 監聽中的 socket file descriptor
+ addr: 連線進來的 client 位址
+ addrlen: addr 的長度

ssize_t read(int fd, void *buf, size_t count);

+ 查詢 [read(2)](https://man7.org/linux/man-pages/man2/read.2.html)，可得知 accept 這個 system call 有三個參數：
+ fd: 從 file descriptor 讀取
+ buf: 將讀入的 bytes 讀進緩衝區 buf
+ count: 讀取 count bytes

這個無限迴圈中，先宣告一個 fd_set 的 `set`，然後先用 `FD_ZERO` 將該 `set` 中的 file descriptor 移除，也就是初始化這個 file descriptor set。再用 `FD_SET` 將 `listenfd` 和 `stdin_fd` 加到 `set` 中。

用 `select` 來監視 `set` 中的 `FD_SET` 將 `listenfd` 是否準備好被讀取了，回傳值 `rv` 如果是 -1 代表有錯誤發生，0 則代表超過設置的等待時間，成功時，則為三個集合中包含的 file descriptor 數量。

`FD_ISSET` 會檢查 file descriptor 是否在 `set` 中。

+ 當 `listenfd` 在 `set` 中：
因為已經用 `select()` 檢查過 file descriptor 是否可讀，可讀代表有新的連線正在等待被 `accept()`，`accept()` 會回傳一個新的 file descriptor `connfd` 作為後續新的連線，原本的還是會留著用 `accept()` 接受新的連線。
將 `connfd` 和 `clientaddr` 當作參數傳入 `process()`，並回傳一個字串 `p`，並用 `strncpy()` 複製 `p` 的字串內容到 `buffer`，然後結束與 client 的連線，用 `close()` 來關閉。

+ 當 `listenfd` 在 `set` 中：
讀取 stdin file descriptor 1 byte 的大小到 c 裡面，如果 read 回傳的數字小於等於 0，就回傳目前 edited line 的長度。

### 二、嘗試修改 console.c，讓程式讀到 web 命令後手動按下 Enter 鍵繼續
+ 將 socket 改為 non-blocking，防止程式停止接收使用者輸入：

int flags = fcntl(listenfd, F_GETFL);
fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);

+ 修改 run_console()：

if (!has_infile) {
    char *cmdline;
    while ((cmdline = linenoise(prompt)) != NULL) {
        int connfd = accept(*listenfd, (SA *)&clientaddr, &clientlen);
        if (connfd == -1) {
            interpret_cmd(cmdline);
            linenoiseHistoryAdd(cmdline);       /* Add to the history. */
            linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
            linenoiseFree(cmdline);
        }
        else {
            cmdline = process(connfd, &clientaddr);
            interpret_cmd(cmdline);
            free(cmdline);
            close(connfd);
        }
    }
} else {
    while (!cmd_done())
        cmd_select(0, NULL, NULL, NULL, NULL);
}

+ 透過 HTTP 的 GET method 來傳送想要執行的 function，process() 處理 URL 字串並將 function name 與 parameter 以跟 cmdline 一樣的格式回傳 ([function name][space][parameter])：

char *process(int fd, struct sockaddr_in *clientaddr) {
#ifdef LOG_ACCESS
    printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
    http_request req;
    parse_request(fd, &req);
    int status = 200;
    handle_request(fd, req.function_name);

    char *p = req.function_name;
    /* Change '/' to ' ' */
    while (*p && (*p) != '\0') {
        ++p;
        if (*p == '/') {
            *p = ' ';
        }
    }
#ifdef LOG_ACCESS
    log_access(status, clientaddr, &req);
#endif
    char *ret = malloc(strlen(req.function_name) + 1);
    strncpy(ret, req.function_name, strlen(req.function_name) + 1);

    return ret;
}

### 三、在分析完 console.c 後，發現使用 cmd_select() 能夠滿足需求

#### 1. 先將 tiny-web-server 的 `tiny.c` 加入專案中
+ 改名為 `tinyweb.c`，並編輯 `Makefile`，將 `tinyweb.o` 也變成需要的目標檔：

OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
-       linenoise.o 
+       linenoise.o tinyweb.o

#### 2. 更改 `tinyweb.c` 中的 `process` 函式，其中的 `function_name` 改成 `filename`

char *process(int fd, struct sockaddr_in *clientaddr) {
#ifdef LOG_ACCESS
    printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
    http_request req;
    parse_request(fd, &req);
    int status = 200;
    handle_request(fd, req.function_name);

    char *p = req.function_name;
    /* Change '/' to ' ' */
    while (*p && (*p) != '\0') {
        ++p;
        if (*p == '/') {
            *p = ' ';
        }
    }
#ifdef LOG_ACCESS
    log_access(status, clientaddr, &req);
#endif
    char *ret = malloc(strlen(req.function_name) + 1);
    strncpy(ret, req.function_name, strlen(req.function_name) + 1);

    return ret;
}

#### 3. 因為我們需要同時控制 web 輸入及使用者輸入，必須關閉 linenoise API 才能達成，在輸入 web 命令後將 linenoise 關閉，並儲存監聽的 file descriptor：

在 `console.c` 加入：

static bool do_web(int argc, char *argv[])
{
    listenfd = socket_init();
    noise = false;
    return true;
}

在 `console.c` 中的 `init_cmd()` 加入 web command：

ADD_COMMAND(web, " [port]         | Read commands from a tiny-web-server");

#### 4. 更改 `console.c` 的 `run_console()` ，依照 linenoise 開啟與否來選擇要使用 `linenoise()` 還是 `cmd_select()`

有兩種得到命令（command）的方式，一種是 standard input，從終端機輸入 command，另一種是讀檔，例如：執行 `make check` 的時候會執行一些範例測試，就會需要讀檔。

是標準輸入時，會看 noise 來決定要用 `linenoise()` 或是 `cmd_select()`。

// 讀 standard input 
if (!has_infile) {
    char *cmdline;
    // 使用 linenoise()
    while (noise && (cmdline = linenoise(prompt)) != NULL) {
        interpret_cmd(cmdline);
        linenoiseHistoryAdd(cmdline); /* Add to the history. */
        linenoiseHistorySave(
            HISTORY_FILE); /* Save the history on disk. */
        linenoiseFree(cmdline);
    }
    // 使用 cmd_select()
    if (!noise) {
        while (!cmd_done()) {
            cmd_select(0, NULL, NULL, NULL, NULL);
        }
    }
// 要讀檔案
} else {
    while (!cmd_done()) {
        cmd_select(0, NULL, NULL, NULL, NULL);
    }
}

#### 5. 更改 `console.c` 的 `cmd_select()`，新增對應的處理

如果 readfds 為 NULL，那就給它一個集合 `local_readset`，然後將 `readfds` 初始化，再將 standard input 的 file descriptor `infd` 加到 `readfds` 集合裡。如果 web 還沒準備好 listen，就將 listen 的 file descriptor `listenfd` 也加到 `readfds`。

在 `console.c` 的 `push_file()` 中，stdin 的 file descriptor 設定為 `STDIN_FILENO`，所以當 `infd` 為 `STDIN_FILENO` 時，代表是 stdin 的情況，這裡先將 prompt 的內容：`cmd> ` 輸出，再將緩衝區的內容都輸出。

然後 `nfds` 和系統呼叫 `select()` 一樣，要是 `infd` 和 `listenfd` 中數字比較大的再加一。使用 `select()` 去監視，如果在任何一個 file descriptor 準備好之前時間就到期了，會回傳 0，出現錯誤是回傳 -1。

+ 如果 `infd` 在 `readfds` 中，就是用 cmdline 取得 command。
先將 `infd` 從 `readfds` 中移除，然後讀取一行內容，將它放進 `interpret_cmd()` 中，`interpret_cmd()` 會將讀到字串解析成 command line，然後執行命令。
+ 如果 `listenfd` 在 `readfds` 中，就是用 socket 的方式取得 command。
先將 `listenfd` 從 `readfds` 中移除，然後使用系統呼叫 `accept()` 取得一個新的 file descriptor `connfd` 做後續的連線。然後在 `process()` 中處理連線得到的 URL 字串，將 request 的 filename 轉成和 cmdline 的格式相同，然後一樣放進 `interpret_cmd()` 執行。

int cmd_select(int nfds,
           fd_set *readfds,
           fd_set *writefds,
           fd_set *exceptfds,
           struct timeval *timeout)
{
    int infd;
    fd_set local_readset;

    if (cmd_done())
        return 0;
        
    if (!block_flag) {
        /* Process any commands in input buffer */
        if (!readfds)
            readfds = &local_readset;

        /* Add input fd to readset for select */
        infd = buf_stack->fd;
+       FD_ZERO(readfds);
        FD_SET(infd, readfds);

+       /* If web not ready listen */
+       if (listenfd != -1)
+           FD_SET(listenfd, readfds);

        if (infd == STDIN_FILENO && prompt_flag) {
            printf("%s", prompt);
            fflush(stdout);
            prompt_flag = true;
        }

        if (infd >= nfds)
            nfds = infd + 1;
+       if (listenfd >= nfds)
+           nfds = listenfd + 1;
    }
    if (nfds == 0)
        return 0;
        
    int result = select(nfds, readfds, writefds, exceptfds, timeout)
    if (result <= 0)
        return result;

    infd = buf_stack->fd;
    if (readfds && FD_ISSET(infd, readfds)) {
        /* Commandline input available */
        FD_CLR(infd, readfds);
        result--;
-       if (has_infile) {
        char *cmdline;
        cmdline = readline();
        if (cmdline)
            interpret_cmd(cmdline);
-       }
+    } else if (readfds && FD_ISSET(listenfd, readfds)) {
+       FD_CLR(listenfd, readfds);
+       result--;
+       int connfd;
+       struct sockaddr_in clientaddr;
+       socklen_t clientlen = sizeof(clientaddr);
+       connfd = accept(listenfd,(SA *) &clientaddr, &clientlen);

+       char *p = process(connfd, &clientaddr);
+       if (p)
+           interpret_cmd(p);
+       free(p);
+       close(connfd);
+   }
    return result;
}

#### 6. 修正讓程式編譯的過
+ 將 `tinyweb.c` 的 `main()` 移除
避免專案中有兩個 main function 的定義

+ 新增 `tinyweb.c` 的標頭檔：`tinyweb.h`

#ifndef TINYWEB_H
#define TINYWEB_H

#include <netinet/in.h>

/* Simplifies calls to bind(), connect(), and accept() */
typedef struct sockaddr SA;

int open_listenfd(int port);

char *process(int fd, struct sockaddr_in *clientaddr);

#endif 

+ 在 `console.c` 引入 `tinyweb.h`

#include "tinyweb.h"

+ 將 `tinyweb.c` 中 `process()` 以下這行移除

handle_request(fd, req.filename); 

+ `console.c` 中更改 do_web 的部分

+ int noise = true;
+ int listenfd;
static bool do_web(int argc, char *argv[])
{

+   int port = 9999;
-   listenfd = socket_init();
+   listenfd = open_listenfd(port);
    noise = false;
    return true;
}

修改到這裡，目前功能是在我們下 `web` 指令的時候，將 `linenoise` 關掉，改用 `cmd_select()`。
而且還會再多輸出一次 `cmd> web`

cmd> web
cmd> web

+ 在 `console.c` 的 `cmd_select()` 加入

set_echo(0);

讓他不要多輸出一次 `cmd> web`

+ 更改 `console.c` 的 `do_web()`

static bool do_web(int argc, char *argv[])
{
    int port = 9999;

    if (argc == 2) {
        if (argv[1][0] >= '0' && argv[1][0] <= '9') {
            port = atoi(argv[1]);
        }
    }

    listenfd = open_listenfd(port);

    if (listenfd > 0) {
        printf("listen on port %d, fd is %d\n", port, listenfd);
        noise = false;
    } else {
        perror("ERROR");
        exit(listenfd);
    }

    return true;
}

#### 7. 用 curl 下 command
用 curl 下 command 是正常運作。

$ curl http://localhost:9999/new
$ curl http://localhost:9999/ih/1
$ curl http://localhost:9999/ih/2
$ curl http://localhost:9999/ih/3
$ curl http://localhost:9999/sort
$ curl http://localhost:9999/quit


#### 8. 用瀏覽器下 command
+ 要解決沒有回傳給 client 的問題

因為 server 沒有回傳任何東西給 client 就結束連線了，所以會發生瀏覽器以為是網路問題，多次重送 request 給 server。所以要來寫給 client 的 response。

在 tiny-web-server 專案中的 `tiny.c` ，有個處理 request 的 function： `handle_directory_request()`，參考它來實作要回傳給 client 的 response。

在 `tinyweb.c` 中加入的 `send_response()`。

void send_response(int out_fd)
{
    char *buf = 
        "HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
        "Content-Type: text/html\r\n\r\n" "<html><head><style>"
        "body{font-family: monospace; font-size: 13px;}"
        "td {padding: 1.5px 6px;}"
        "</style></head><body><table>\n";
    writen(out_fd, buf, strlen(buf));
}

然後在 `tinyweb.c` 中的 `process()` 去呼叫 `send_response()`：

send_response(fd);

就可以解決上述問題了。

+ 要解決 favicon.ico 的問題


從瀏覽器發 request 後，可以看到上圖 favicon.ico 的 status 是 404。因為部分瀏覽器會要求 request 中要提供網頁圖案的對應資訊，而我上面的 response 沒有提供。

在 [I'm getting favicon.ico error](https://stackoverflow.com/questions/31075893/im-getting-favicon-ico-error) 有提供做法，就是將下面這行加進去 head 裡面即可：

<link rel="shortcut icon" href="#">

因此修改 `send_response()`，將上面的程式加進去：

void send_response(int out_fd)
{
    char *buf = 
        "HTTP/1.1 200 OK\r\n%s%s%s%s%s%s"
        "Content-Type: text/html\r\n\r\n" "<html><head><style>"
        "body{font-family: monospace; font-size: 13px;}"
        "td {padding: 1.5px 6px;}"
        "</style><link rel=\"shortcut icon\" href=\"#\">"
        "</head><body><table>\n";
    writen(out_fd, buf, strlen(buf));
}

再次嘗試，就都是 200 OK 了！


### 檢驗是否正確

:::spoiler testWeb.c

#include <arpa/inet.h>
#include <netinet/in.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>

#define TARGET_HOST "127.0.0.1"
#define TARGET_PORT 9999

/* length of unique message (TODO below) should shorter than this */
#define MAX_MSG_LEN 1024
static const char *msg_dum = "GET /new HTTP/1.1\n\n";

int main(void)
{
    int sock_fd;
    char dummy[MAX_MSG_LEN];
    //struct timeval start, end;

    sock_fd = socket(AF_INET, SOCK_STREAM, 0);
    if (sock_fd == -1) {
        perror("socket");
        exit(-1);
    }

    struct sockaddr_in info = {
        .sin_family = PF_INET,
        .sin_addr.s_addr = inet_addr(TARGET_HOST),
        .sin_port = htons(TARGET_PORT),
    };

    if (connect(sock_fd, (struct sockaddr *) &info, sizeof(info)) == -1) {
        perror("connect");
        exit(-1);
    }
    send(sock_fd, msg_dum, strlen(msg_dum), 0);
    recv(sock_fd, dummy, MAX_MSG_LEN, 0);

    shutdown(sock_fd, SHUT_RDWR);
    close(sock_fd);

    printf("%s\n", dummy);

    int count = 0, last_pos = 0;
    for (int i = 0; i < strlen(dummy); i++) {
        if (dummy[i] == '\n') {
            count++;
        }
        if (count == 3) {
            last_pos = i + 1;
            break;
        }
    }

    char *answer = "l = []";
    // printf("%s", dummy + last_pos);
    printf("%ld %ld\n", strlen(answer), strlen(dummy + last_pos));

    // if (strncmp(answer, dummy + last_pos, strlen(dummy + last_pos))) {
    //     puts("message validation failed");
    //     exit(-1);
    // }
    // else {
    //     puts("success");
    // }

    return 0;
}

:::

更改 [bench.c](https://github.com/sysprog21/kecho/blob/master/bench.c)，傳送 HTTP request 給開著的 web server，並接收 HTTP response，查看是否與預期的結果相同。

在 testweb.c 中，傳送 new 的命令，但是回傳回來除了執行結果還多了換行和一個隨機的字元...

HTTP/1.1 200 OK
Content-Type: text/plain

l = []
v

:::spoiler report 和 report_noreturn

extern int connfd;
void report(int level, char *fmt, ...)
{
    if (!verbfile)
        init_files(stdout, stdout);

    int bufferSize = 4096;
    char buffer[bufferSize];
    if (level <= verblevel) {
        va_list ap;
        va_start(ap, fmt);
        vfprintf(verbfile, fmt, ap);
        fprintf(verbfile, "\n");
        fflush(verbfile);
        va_end(ap);

        if (logfile) {
            va_start(ap, fmt);
            vfprintf(logfile, fmt, ap);
            fprintf(logfile, "\n");
            fflush(logfile);
            va_end(ap);
        }
        va_start(ap, fmt);
        vsnprintf(buffer, bufferSize, fmt, ap);
        va_end(ap);
    }
    if (connfd) {
        int len = strlen(buffer);
        buffer[len] = '\n';
        buffer[len + 1] = '\0';
        send_response(connfd, buffer);
    }
}

void report_noreturn(int level, char *fmt, ...)
{
    if (!verbfile)
        init_files(stdout, stdout);

    int bufferSize = 4096;
    char buffer[bufferSize];
    if (level <= verblevel) {
        va_list ap;
        va_start(ap, fmt);
        vfprintf(verbfile, fmt, ap);
        fflush(verbfile);
        va_end(ap);

        if (logfile) {
            va_start(ap, fmt);
            vfprintf(logfile, fmt, ap);
            fflush(logfile);
            va_end(ap);
        }
        va_start(ap, fmt);
        vsnprintf(buffer, bufferSize, fmt, ap);
        va_end(ap);
    }
    if (connfd) {
        send_response(connfd, buffer);
    }
}

:::

因為原本的 web 實作中，HTTP 的 body 只會回傳 ok，現在要將原本輸出到標準輸出的結果也當作 HTTP response 傳回給 client。

在 `qtest.c` 的 do_operation 系列的函式，常常呼叫 report.c 的 `report` 和 `report_noreturn`，為了將執行結果輸出到標準輸出，其中兩者差別在是否有輸出換行，輸出後有需要換行就會呼叫 `report`，不需要會呼叫 `report_noreturn`。

在 `report` 和 `report_noreturn` 檢查是否有連線，如果有連線，就將結果一起寫進 response 中，如此一來即可回傳執行結果。

## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
參考 [AmyLin0210](https://hackmd.io/@AmyLin0210/rJpekw9kc#%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) 的思路

執行 `make valgrind` 會出現（節錄部分輸出）：

---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==186384== 11 bytes in 1 blocks are still reachable in loss record 1 of 3
==186384==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==186384==    by 0x4A4B3BE: strdup (strdup.c:42)
==186384==    by 0x110A1A: linenoiseHistoryAdd (linenoise.c:1236)
==186384==    by 0x1115AD: linenoiseHistoryLoad (linenoise.c:1325)
==186384==    by 0x10C765: main (qtest.c:972)
==186384==
==186384== 102 bytes in 19 blocks are still reachable in loss record 2 of 3
==186384==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==186384==    by 0x4A4B3BE: strdup (strdup.c:42)
==186384==    by 0x11098E: linenoiseHistoryAdd (linenoise.c:1236)
==186384==    by 0x1115AD: linenoiseHistoryLoad (linenoise.c:1325)
==186384==    by 0x10C765: main (qtest.c:972)
==186384==
==186384== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==186384==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==186384==    by 0x1109DA: linenoiseHistoryAdd (linenoise.c:1224)
==186384==    by 0x1115AD: linenoiseHistoryLoad (linenoise.c:1325)
==186384==    by 0x10C765: main (qtest.c:972)
==186384==
---	trace-01-ops	5/5

在輸出訊息中有看到 `still reachable`，在 [K01: lab0 的 Valgrind 使用案例](https://hackmd.io/@sysprog/linux2022-lab0#Valgrind-%E4%BD%BF%E7%94%A8%E6%A1%88%E4%BE%8B) 中有提到：
> still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數

查看發生錯誤訊息的路徑：
+ 在 `qtest.c` 中第 972 行，呼叫到 `linenoiseHistoryLoad` function：

linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */

+ 在 `linenoise.c` 中第 1325 行（在 `linenoiseHistoryLoad` function），有呼叫到 `linenoiseHistoryAdd` function：

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;
}

+ 在 `linenoise.c` 中第 1224 和 1236 行（在 `linenoiseHistoryAdd` function）會出現問題：

在 history 為 NULL 時，配置記憶體給 history，然後將傳進來的 line 參數用 strdup 複製出新的字串，再將新字串放到 history 裡面。

從 manual 可以看到 strdup 是用 malloc 配置新字串的記憶體：

>DESCRIPTION
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).

`static char **history = NULL;`，history 是 static 靜態變數，存放在記憶體的固定位置，不會隨函數的結束而被回收。因此要自行將 history 回收，而 `linenoise.c` 中有 `freeHistory` 這個 function，只有被 `linenoiseAtExit` 呼叫到，因為只有在要離開、不需要用到了才會將 history 回收。

/* This is the API call to add a new entry in the linenoise history.
 * It uses a fixed array of char pointers that are shifted (memmoved)
 * when the history max length is reached in order to remove the older
 * entry and make room for the new one, so it is not exactly suitable for huge
 * histories, but will work well for a few hundred of entries.
 *
 * Using a circular buffer is smarter, but a bit more complex to handle. */
int linenoiseHistoryAdd(const char *line)
{
    char *linecopy;

    if (history_max_len == 0)
        return 0;

    /* Initialization on first call. */
    if (history == NULL) {
        history = malloc(sizeof(char *) * history_max_len);
        if (history == NULL)
            return 0;
        memset(history, 0, (sizeof(char *) * history_max_len));
    }

    /* Don't add duplicated lines. */
    if (history_len && !strcmp(history[history_len - 1], line))
        return 0;

    /* 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;
}

回來看 `qtest.c` 可以發現 `main` 函式會呼叫到 `run_console`，但因為最初執行 `make valgrind` 就是要讀檔測試的，例如：`traces/trace-01-ops.cmd`，而不是直接從 command line 輸入，所以在 `run_console` 中，我們會執行 21~25 行的部分，是用 `cmd_select` 而不會呼叫到 linenoise 的函式。

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) { // 讀 standard input
        char *cmdline;
        while (noise && (cmdline = linenoise(prompt)) != NULL) {
            interpret_cmd(cmdline);
            linenoiseHistoryAdd(cmdline);       /* Add to the history. */
            linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
            linenoiseFree(cmdline);
        }
        if (!noise) {
            while (!cmd_done()) {
                cmd_select(0, NULL, NULL, NULL, NULL);
            }
        }
    } else { // 要讀檔案
        while (!cmd_done()) {
            cmd_select(0, NULL, NULL, NULL, NULL);
        }
    }

    return err_cnt == 0;
}

但是在 `qtest.c` 中我們無論是用讀檔的方式或是從 command line 輸入的方式，都會呼叫到 linenoise 相關的函式，所以應該改成在沒有檔案的時候，才去呼叫 linenoise 相關的函式，才能避免讀檔會發生記憶體洩漏的情況：在 `qtest.c` 的 `main` 呼叫了 `linenoiseHistoryLoad`，卻又沒能在 `run_console` 中使用 linenoise 釋放記憶體。因此改成以下即可解決：

int main(int argc, char *argv[])
{
    ...
+   if (!infile_name) {
        /* Trigger call back function(auto completion) */
        linenoiseSetCompletionCallback(completion);
        linenoiseHistorySetMaxLen(HISTORY_LEN);
        linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
+   }
    ...
}

再來是測試複雜度的測試中，如果失敗，輸出訊息中也會看到 `still reachable` 的提示：

+++ 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
Probably constant time
ERROR: Probably not constant time
Probably constant time
Probably constant time
==26260== 32 bytes in 1 blocks are still reachable in loss record 1 of 30
==26260==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==26260==    by 0x10DF36: malloc_or_fail (report.c:189)
==26260==    by 0x10EA5D: add_cmd (console.c:90)
==26260==    by 0x10EDE7: init_cmd (console.c:431)
==26260==    by 0x10D67C: main (qtest.c:965)
==26260== 

在 `add_cmd()` 中會透過 `malloc_or_fail()` 配置記憶體給新的 command，然後在 `finish_cmd()` 中呼叫 `do_quit()` 將記憶體釋放，所以可能是因為沒有順利呼叫到 `finish_cmd()` 導致記憶體沒有被順利釋放。

只要在 `qtest.c` 以下改成：

bool ok = true;
    ok = ok && run_console(infile_name);
-   ok = ok && finish_cmd();
+   ok = finish_cmd() && ok;

原本當 `ok` 為 false 時，就不會呼叫到 `finish_cmd()`，因此改變 `ok` 和 `finish_cmd()` 的順序，就一定能順利呼叫到 `finish_cmd()`。

### Massif
用 Massif 來測量執行程式會需要用到多少 heap memory，並透過它來看記憶體洩漏的情況。

+ 在終端機輸入：
`valgrind -v --tool=massif ./qtest -f traces/trace-01-ops.cmd`
會得到 `massif.out.18935` 的檔案，每次執行後面的五位數字都會不一樣

+ 在終端機輸入：
`massif-visualizer ./massif.out.18935`
就可以透過 `massif-visualizer` 來看剛剛產生出來的檔案

+ 可以看到原本動態記憶體是沒有被釋放完全的，沒有歸零。

+ 在修改之後，動態記憶體最終歸零了。

## dudect
dudect 中的 `cpucycles.h` 是使用 rdtsc 取得 timestamp：

#include <stdint.h>
static inline int64_t cpucycles(void)
{
#if defined(__i386__) || defined(__x86_64__)
    unsigned int hi, lo;
    __asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi));
    return ((int64_t) lo) | (((int64_t) hi) << 32);

#elif defined(__aarch64__)
    uint64_t val;
    asm volatile("mrs %0, cntvct_el0" : "=r"(val));
    return val;
#else
#error Unsupported Architecture
#endif
}

在 dudect 中的 `constant.c` 有使用到 `cpucycles.h` 中定義的 cpucycles：

...
case test_insert_head:
        for (size_t i = drop_size; i < n_measure - drop_size; i++) {
            char *s = get_random_string();
            dut_new();
            dut_insert_head(
                get_random_string(),
                *(uint16_t *) (input_data + i * chunk_size) % 10000);
            before_ticks[i] = cpucycles();
            dut_insert_head(s, 1);
            after_ticks[i] = cpucycles();
            dut_free();
        }
        break;
...

因為 rdtsc 只會給 timestamp，沒辦法告訴我們一個操作需要花多少時間，所以這裡是在 `dut_insert_head(s, 1)` function 執行前，先取得 timestamp，在 function 離開後再取得一次 timestamp，即可得知相對的時間變化，粗略得知該 function 執行多少時間。

先將程式[鎖定到一個 CPU 執行](https://hackmd.io/suYZlvVVSNOjdmy4JzZU6A?view#%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90)，降低 CPU 的干擾因素。

嘗試使用 `clock_gettime` 代替 `rdtsc`，各自執行十次，幾乎都是非 constant time。
下表為按照 insert_head, insert_tail, remove_head, remove_tail 順序，測試出來是否為 constant time：(1: True, 0: False)

| | rdtsc | clock_gettime() |
| -------- | -------- | -------- |
| 1 | 1010 | 1010 |
| 2 | 1110 | 1010 |
| 3 | 1111 | 1100 |
| 4 | 1110 | 1010 |
| 5 | 1110 | 1110 |
| 6 | 1000 | 1010 |
| 7 | 1000 | 1010 |
| 8 | 1100 | 1011 |
| 9 | 1000 | 1110 |
| 10 | 1000 | 1110 |

因為不確定自己寫的 insert_head, insert_tail, remove_head, remove_tail function 是不是常數時間，後來有換成將這些 function 內容直接改成 return 0（因為一定會是常數時間），然後分別用 rdtsc 和 clock_gettime() 測試，但是跑出來的結果也幾乎都辨識為非常數時間

有在想 function 直接 return 0 是否速度會太快，會影響到測試之類的，有再將 insert_head, insert_tail, remove_head, remove_tail function 改成執行 10000 次的迴圈，但跑出來也是有非常數時間。

有想過不直接看最後結果是否為常數時間，直接拿 rdtsc 和 clock_gettime() 所執行的時間，各自做一些簡單的統計，像是平均、標準差（如果標準差較小，可能比較穩定（？）），然後將時間分佈做個直方圖來比較，但不確定這麼做是否有意義。

查看即時 CPU 的頻率：
`watch -n.1 "grep \"^[c]pu MHz\" /proc/cpuinfo"`

使用的 CPU 是 2.9 GHz，換算 rdtsc 的 cycle 變成 ns：
1 / 2.9G * $10^9$(ns / cycle) $\approx$ 0.3448(ns / cycle)

+ `test_tries` 跑一次會測量特定 function 91 * 110（頭尾個去掉 20） = 10010 次，下圖是測量 insert_head 10010 次每次的執行時間，大部分都落在 100~200 ns。
但有時候會出現 outlier，像是開頭的執行時間 1991 ns。

+ 紀錄 fix class 和 random class 兩者執行時間的分佈：

crop 的大小
$1 - 0.5^{(\frac{10x}{100})}$ = $1 - 0.5^{(\frac{x}{10})}$