2022q1 Homework1 (lab0)

--- 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。 ```c 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。 ```c 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 ::: ```c 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`。 ```c 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。 ```c 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`。 ```c 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 計算目前佇列的節點總量 ```c int q_size(struct list_head *head) { if (!head) return 0; int len = 0; struct list_head *li; list_for_each (li, head) len++; return len; } ``` ### q_delete_mid 移走佇列中間的節點透過快慢指標，先將 fast 和 slow 的起始位置設定在第一個節點，然後 fast 一次移動兩步，slow 一次移動一步，當 fast 或 fast->next 等於 head 的位址時，slow 所在的位置即為中間節點。先用 `list_del` 移除中間節點的連結，再用 `list_entry` 取得該節點起始位置，呼叫q_release_element 將該節點的值和節點本身的記憶體釋放掉。 ```c 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` 時，也要將現在走到的節點刪除，這是為了要刪除連續重複節點的最後一個。 ```c 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 中的前面那一個。 ```c 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` 結束。 ```c 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` 修正成對的節點。 ```c 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 函式。 ```c /* original written sort: 0, lib/list_sort.c: 1 */ static int sortmode = 0; ``` 在 `qtest.c` 中加入 option 參數 sort，根據不同的 sortmode，來切換 sort。 ```c 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。 ```diff 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 的指標，透過這兩個指標所在節點的值去比大小。 ```c typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *); ``` 實作出的 compare function：(在 `qtest.c`) ```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` 當中： ```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 相關的標頭檔刪除然後移除： ```c 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. ``` 解決方法是在該變數宣告的上一行加上： ```c // 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`： ```bash # original sort option verbose 1 option sort 0 new ih RAND 1000000 time sort free ``` + `trace-kernel-sort.cmd`： ```bash # 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 ```c __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 變成單向的。 ```c 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 沒有節點就代表現階段結束了。 ```c /* 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 ```c __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： ```graphviz 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： ```graphviz 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`： ```graphviz 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 ```graphviz 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 } ``` ```graphviz 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 ```graphviz 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 } ``` ```graphviz 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 } ``` ```graphviz 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 ```graphviz 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 } ``` ```graphviz 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 ```graphviz 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 } ``` ```graphviz 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 } ``` ```graphviz 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()` 加入： ```c ADD_COMMAND(shuffle, " | Shuffle nodes in queue"); ``` 然後另外宣告一個 `do_shuffle()`： ```c static bool do_shuffle(int argc, char *argv[]) { if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } if (!l_meta.l) report(3, "Warning: Try to access null queue"); error_check(); 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 就結束了。 ```c 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 之間。 ![](https://i.imgur.com/GDtpa8I.png) #### 4. 統計檢定的結果不拒絕虛無假說對於要拒絕的虛無假說（$H_0$），觀察到的結果必須具有統計顯著性，即觀察到的 P value 小於預先指定的顯著水準 α。因為 P value（0.8~0.9）> alpha（0.05），統計檢定的結果不拒絕虛無假說（$H_0$）也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻。從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的。 ![](https://i.imgur.com/uwrfQA1.png) ### 測試程式看到在 `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 ```python 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) ``` 產生直方圖的程式： ```python 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 次的直方圖： ![](https://i.imgur.com/p9TYxio.png) :::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。 ![](https://i.imgur.com/rH1YJSf.png) 先按照[整合 tiny-web-server](https://hackmd.io/@sysprog/linux2022-lab0#%E6%95%B4%E5%90%88-tiny-web-server)的引導，有三種方法，其中第三種方法最符合我們的需求。 ### 一、嘗試用 select() 同時處理 stdin 及 socket #### 在 `linenoiseEdit` 中加入以下程式碼： ```c 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; } } ``` ```c 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。 ```c 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 的長度 ```c 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，防止程式停止接收使用者輸入： ```c int flags = fcntl(listenfd, F_GETFL); fcntl(listenfd, F_SETFL, flags | O_NONBLOCK); ``` + 修改 run_console()： ```c 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])： ```c 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` 也變成需要的目標檔： ```diff 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` ```c 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` 加入： ```c static bool do_web(int argc, char *argv[]) { listenfd = socket_init(); noise = false; return true; } ``` 在 `console.c` 中的 `init_cmd()` 加入 web command： ```c 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()`。 ```c // 讀 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()` 執行。 ```diff=546 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` ```c #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` ```c #include "tinyweb.h" ``` + 將 `tinyweb.c` 中 `process()` 以下這行移除 ```c handle_request(fd, req.filename); ``` + `console.c` 中更改 do_web 的部分 ```diff + 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()` 加入 ```c set_echo(0); ``` 讓他不要多輸出一次 `cmd> web` + 更改 `console.c` 的 `do_web()` ```c 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 是正常運作。 ```shell $ 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 ``` ![](https://i.imgur.com/Mggb0AY.png) #### 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()`。 ```c 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()`： ```c send_response(fd); ``` 就可以解決上述問題了。 + 要解決 favicon.ico 的問題 ![](https://i.imgur.com/pcXczr1.png) 從瀏覽器發 request 後，可以看到上圖 favicon.ico 的 status 是 404。因為部分瀏覽器會要求 request 中要提供網頁圖案的對應資訊，而我上面的 response 沒有提供。在 [I'm getting favicon.ico error](https://stackoverflow.com/questions/31075893/im-getting-favicon-ico-error) 有提供做法，就是將下面這行加進去 head 裡面即可： ```c <link rel="shortcut icon" href="#"> ``` 因此修改 `send_response()`，將上面的程式加進去： ```c 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 了！ ![](https://i.imgur.com/8WZ59gx.png) ### 檢驗是否正確 :::spoiler testWeb.c ```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 ```c 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： ```c=972 linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */ ``` + 在 `linenoise.c` 中第 1325 行（在 `linenoiseHistoryLoad` function），有呼叫到 `linenoiseHistoryAdd` function： ```c=1309 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 回收。 ```c=1208 /* 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 的函式。 ```c= bool run_console(char *infile_name) { if (!push_file(infile_name)) { report(1, "ERROR: Could not open source file '%s'", infile_name); return false; } if (!has_infile) { // 讀 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 釋放記憶體。因此改成以下即可解決： ```diff 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` 以下改成： ```diff 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` 來看剛剛產生出來的檔案 + 可以看到原本動態記憶體是沒有被釋放完全的，沒有歸零。 ![](https://i.imgur.com/eszhS49.png) + 在修改之後，動態記憶體最終歸零了。 ![](https://i.imgur.com/ujIz76v.png) ## dudect dudect 中的 `cpucycles.h` 是使用 rdtsc 取得 timestamp： ```c #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： ```c ... 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。 ![](https://i.imgur.com/CY8I93d.png) 但有時候會出現 outlier，像是開頭的執行時間 1991 ns。 ![](https://i.imgur.com/byifFBA.png) + 紀錄 fix class 和 random class 兩者執行時間的分佈： ![](https://i.imgur.com/UFe5tfr.png) crop 的大小 $1 - 0.5^{(\frac{10x}{100})}$ = $1 - 0.5^{(\frac{x}{10})}$ ![](https://i.imgur.com/Et5SiC3.png)

Read more

2022q1 Homework3 (quiz3)

2022q1 Homework3 (fibdrv)

2022q1 Homework2 (quiz2)