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 的最前面。

自己原本 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 專案的錯誤追蹤。

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

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 和非連續記憶體中， Merge Two Sorted Lists 的 indirect pointer 寫法、Linked List Sort 的 merge sort 寫法，以及 mm0809 的共筆 q_sort 的寫法。

先讓最後一個節點的 next 指向 NULL，以 next 的方向來看，queue 變成不是 circular。
然後呼叫 mergeSortList，找 queue 的中間節點，將 queue 分成兩半，在遞迴呼叫自己，將分開的兩半分別再繼續分成兩半，直到分成只有一個節點的時候（只有自己就是已排序的狀態），開始呼叫 merge。
merge 會將兩個 queue 依據值由小到大合併，一直呼叫 merge 直到整個 queue 都被 merge 完成。
因為前面的動作只有專注在節點的 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 和 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 下的巨集：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 -> 0011	yes	(2) + 1
3 -> 4	0011 -> 0100	no（ $2^{2}$ ）	2 + 1 + 1
4 -> 5	0100 -> 0101	yes	2 + (2) + 1
5 -> 6	0101 -> 0110	yes	(4) + 1 + 1
6 -> 7	0110 -> 0111	yes	4 + (2) + 1
7 -> 8	0111 -> 1000	no（ $2^{3}$ ）	4 + 2 + 1 + 1
8 -> 9	1000 -> 1001	yes	4 + 2 + (2) + 1
9 -> 10	1001 -> 1010	yes	4 + (4) + 1 + 1
10 -> 11	1010 -> 1011	yes	4 + 4 + (2) + 1
11 -> 12	1011 -> 1100	yes	(8) + 2 + 1 + 1
12 -> 13	1100 -> 1101	yes	8 + 2 + (2) + 1
13 -> 14	1101 -> 1110	yes	8 + (4) + 1 + 1
14 -> 15	1110 -> 1111	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：

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

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

count = 1 -> count = 2

count = 2 -> count = 3

count = 3 -> count = 4

count = 4

在 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 演算法來實作洗牌（shuffle）

先用 q_size 取得 queue 的大小 len。
隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。
隨著 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 能檢驗虛無假說（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} \frac{(O_{i} - E_{i})^{2}}{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 次後，六種結果各自的頻率如下表：

	觀察到的頻率	期待的頻率	$\frac{(O_{i} - E_{i})^{2}}{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）α 代表在虛無假說（
$H_{0}$ ）為真下，錯誤地拒絕
$H_{0}$ 的機率，即型一錯誤發生之機率。
α = P(拒絕
$H_{0}$ |
$H_{0}$ 為真)
我們 alpha 設定為常見的 0.05。
P value
從卡方分布表找我們的 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() ，會執行參數中指定的命令，然後等待命令完成後，會回傳一個 CompletedProcess instance。
取得 CompletedProcess.stdout 再做編碼後，可以得到 stdout 的字串。
後續再將得到的輸出字串取出 shuffle 過後的結果，放到 nums 變數中。

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 次的直方圖：

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

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

在 qtest 提供新的命令 web

有參考 PinLin 的 web 實作

先試跑 tiny-web-server 專案，可以在瀏覽器看到跑該專案的目錄下有什麼檔案
，預設的 port 為 9999。

先按照整合 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) ，可得知 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) ，可得知 accept 這個 system call 有三個參數：
- sockfd: 監聽中的 socket file descriptor
- addr: 連線進來的 client 位址
- addrlen: addr 的長度

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

查詢 read(2)，可得知 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 有提供做法，就是將下面這行加進去 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 了！

檢驗是否正確

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，傳送 HTTP request 給開著的 web server，並接收 HTTP response，查看是否與預期的結果相同。

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

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

l = []
v

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 的思路

執行 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 使用案例中有提到：

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 執行，降低 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{10 x}{100})}

1 - {0.5}^{(\frac{x}{10})}