2022q1 Homework1 (lab0)

# 2022q1 Homework1 (lab0) contributed by < [Eric-liau](https://github.com/Eric-liau) > ## 實驗環境 ```shell $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 39 bits physical, 48 bits virtual CPU(s): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 94 Model name: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz Stepping: 3 CPU MHz: 900.002 CPU max MHz: 3500.0000 CPU min MHz: 800.0000 BogoMIPS: 5199.98 Virtualization: VT-x L1d cache: 128 KiB L1i cache: 128 KiB L2 cache: 1 MiB L3 cache: 6 MiB NUMA node0 CPU(s): 0-7 ``` ## [作業要求](https://hackmd.io/@sysprog/linux2022-lab0) 依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。 - [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c) - [x] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 ``$ make test` 自動評分系統的所有項目。 - [x] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差 - [x] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作 - [x] 在 `qtest` 提供新的命令 `web`，提供 web 伺服器功能，注意: web 伺服器運作過程中，`qtest` 仍可接受其他命令 - [ ] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤 - 先執行 `qtest` 再於命令提示列輸入 `help` 命令，會使開啟 Address Sanitizer 觸發錯誤，應予以排除 - [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗 - [x] 解釋 [select](https://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/CSAPP-ch10) - [x] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案; - [ ] 指出現有程式的缺陷 (提示: 和 [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request :::danger 針對 2022 年作業要求，更新上述列表 :notes: jserv ::: :::success 已更新 ::: ## queue.c ### q_new - `INIT_LIST_HEAD(head)`: 將 head 的 *\*prev* 和 *\*next* 分別指向 head。 ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` ### q_free 想法：從 head node 開始，依序把每個`node` free 掉。 - temp : 因為 `container` 會被 free 掉，而 `current` 包含在 `container` 中，所以需要一個 `struct list_head` 來暫存 `current` 的值。 - `free(l)`: `list_for_each` 不會經過 `head` ，所以在迴圈結束後需要把 `head` free 掉。 - 在寫 `q_insert_head` 時提示 memory leak ，檢查後發現` container->value` 並未 free 掉，故加入 `free(container->value)`。 ```c void q_free(struct list_head *l) { struct list_head *current, temp; element_t *container; list_for_each(current, l){ container = list_entry(current, element_t, list); temp = *current; free(container->value); free(container); current = &temp; } free(l); } ``` ### q_insert_head 1. 檢查 `head` 是否為 `null` 2. 分配空間給 `new` 並檢查是否成功分配 3. 分配空間給 `new->value` 並檢查是否成功分配 4. 複製 s 到 `new->value` 5. 將 `new` insert 到 `queue` 中 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *new = malloc(sizeof(element_t)); if (!new) return false; new->value = malloc(strlen(s) + 1); if (!new->value) { free(new); return false; } strncpy(new->value, s, strlen(s) + 1); list_add(&new->list, head); return true; } ``` ### q_insert_tail 1. 檢查 `head` 是否為 `null` 2. 分配空間給 `new` 並檢查是否成功分配 3. 分配空間給 `new->value` 並檢查是否成功分配 4. 複製 s 到 `new->value` 5. 將 `new` insert 到 `queue` 中 ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *new = malloc(sizeof(element_t)); if (!new) return false; new->value = malloc(strlen(s) + 1); if (!new->value) { free(new); return false; } strncpy(new->value, s, strlen(s) + 1); list_add_tail(&new->list, head); return true; } ``` ### q_remove_head 1. 檢查 `head` 是否為 `NULL` 或 `empty` 2. 檢查 `sp` 是否為 `NULL` 3. 比較 `strlen(node->value) + 1` 和 `bufsize` 大小 - 若後者較大則把 `node->value` 完整複製到 `sp` 中 - 反之則只把 `node->value` 的前 `bufsize - 1` 個字元複製到 `sp`，並在 `sp` 的第 `bufsize` 個字元填上 `'\0' 4. 將 `head->next` 移除 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head) return NULL; if (list_empty(head)) return NULL; element_t *node = list_entry(head->next, element_t, list); if (!sp) { list_del_init(head->next); return node; } char *str = node->value; int len = strlen(str) + 1; if (len <= bufsize) strncpy(sp, str, len); else { strncpy(sp, str, bufsize - 1); *(sp + bufsize - 1) = '\0'; } list_del_init(head->next); return node; } ``` ### q_remove_tail 1. 檢查 `head` 是否為 `NULL` 或 `empty` 2. 檢查 `sp` 是否為 `NULL` 3. 比較 `strlen(node->value) + 1` 和 `bufsize` 大小 - 若後者較大則把 `node->value` 完整複製到 `sp` 中 - 反之則只把 `node->value` 的前 `bufsize - 1` 個字元複製到 `sp`，並在 `sp` 的第 `bufsize` 個字元填上 `'\0' 4. 將 `head->prev` 移除 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head) return NULL; if (list_empty(head)) return NULL; element_t *node = list_entry(head->prev, element_t, list); if (!sp) { list_del_init(head->prev); return node; } char *str = node->value; int len = strlen(str) + 1; if (len <= bufsize) strncpy(sp, str, len); else { strncpy(sp, str, bufsize - 1); *(sp + bufsize - 1) = '\0'; } list_del_init(head->prev); return node; } ``` ### q_release_element 未做更動 ```c void q_release_element(element_t *e) { free(e->value); free(e); } ``` ### q_size 整個 list 走過一遍即可算出 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 利用快慢指標找到中間的 node ```c struct list_head *find_mid(struct list_head *head) { struct list_head *slow = head->next; for (struct list_head *fast = head->next; fast != head && fast->next != head; fast = fast->next->next) { slow = slow->next; } return slow; } bool q_delete_mid(struct list_head *head) { if (!head) return false; if (list_empty(head)) return false; struct list_head *mid = find_mid(head); mid->prev->next = mid->next; mid->next->prev = mid->prev; element_t *node = list_entry(mid, element_t, list); free(node->value); free(node); return true; } ``` ### q_delete_dup 若 `current node` 的值等於 `first` 的值就把 `last` 指標移到 `current node` ，若不等於就檢查 `first` 和 `last` 是否為同一個 `node` ，若不是就把 `first` 和 `last` 之間的 `node` 全部刪除。 ```c bool q_delete_dup(struct list_head *head) { if (!head) return false; if (list_empty(head)) return true; element_t *current, *first = list_entry(head->next, element_t, list), *last = first; list_for_each_entry (current, head, list) { if (!strcmp(current->value, first->value)) last = current; else { if (first != last) { first->list.prev->next = last->list.next; last->list.next->prev = first->list.prev; while (first != current) { element_t *temp = list_entry(first->list.next, element_t, list); q_release_element(first); first = temp; } } first = current; last = current; } } if (first != last) { first->list.prev->next = last->list.next; last->list.next->prev = first->list.prev; while (first != current) { element_t *temp = list_entry(first->list.next, element_t, list); q_release_element(first); first = temp; } } return true; } ``` ### q_swap 把 list 的 node 每兩個依序前後交換 ```c void q_swap(struct list_head *head) { if (!head) return; for (struct list_head *first = head->next, *second = head->next->next; first != head && second != head; first = first->next, second = first->next) { struct list_head *prev = first->prev; struct list_head *next = second->next; prev->next = second; second->prev = prev; second->next = first; first->prev = second; next->prev = first; first->next = next; } } ``` ### q_reverse 把每個 node 的 `next` 和 `prev` 進行交換 ```c void q_reverse(struct list_head *head) { if (!head) return; struct list_head *current, *safe; list_for_each_safe (current, safe, head) { struct list_head *prev = current->prev; struct list_head *next = current->next; current->next = prev; current->prev = next; } struct list_head *prev = head->prev; struct list_head *next = head->next; head->next = prev; head->prev = next; } ``` ### q_sort #### 遞迴版本使用遞迴的 merge sort ，因為傳入的 list 有一個不存資料的 `head` ，所以宣告一個 `new_head` 作為切下來另一半 list 的 `head node`。在自己電腦的效能測試過了，但 github 上的仍無法通過。 ```c struct list_head *merge(struct list_head *left, struct list_head *right) { struct list_head head, **temp, *l = left->next, *r = right->next; INIT_LIST_HEAD(&head); while (l != left && r != right) { if (strcmp(list_entry(l, element_t, list)->value, list_entry(r, element_t, list)->value) < 0) temp = &l; else temp = &r; *temp = (*temp)->next; list_move_tail((*temp)->prev, &head); } (l == left) ? list_splice_tail_init(right, &head) : list_splice_tail(left, &head); list_splice_tail(&head, right); return right; } void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *mid = find_mid(head); struct list_head new_head; INIT_LIST_HEAD(&new_head); list_cut_position(&new_head, head, mid->prev); q_sort(&new_head); q_sort(head); merge(&new_head, head); return; } ``` - 參考[這篇筆記](https://hackmd.io/@laneser/linux2022_lab0#q_sort)懷疑是 stackoverflow 導致效能測試無法通過 - 思考為什麼會發生 stackoverflow ，猜測是因為每次遞迴都會宣告一次 `new_head` 所導致的 - 改寫 mergesort ，讓 merge 的時候不考慮 `head node` ，如此就不需要每次遞迴都宣告一個 `new_head` 。 - 再次上傳後成功通過效能測試 ```c struct list_head *merge(struct list_head *left, struct list_head *right) { struct list_head *head = NULL, **temp = &head; while (left && right) { if (strcmp(list_entry(left, element_t, list)->value, list_entry(right, element_t, list)->value) <= 0) { *temp = left; left = left->next; } else { *temp = right; right = right->next; } temp = &(*temp)->next; } *temp = left ? left : right; return head; } struct list_head *merge_sort(struct list_head *head) { if (!head) return head; if (!head->next) return head; struct list_head *fast = head, *slow = head; while (1) { if (!fast) break; if (!fast->next) break; slow = slow->next; fast = fast->next->next; } slow->prev->next = NULL; head = merge_sort(head); slow = merge_sort(slow); return merge(head, slow); } void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; head->prev->next = NULL; head->next = merge_sort(head->next); struct list_head *current, *prev; for (current = head->next, prev = head; current; current = current->next, prev = prev->next) current->prev = prev; prev->next = head; head->prev = prev; return; } ``` #### 非遞迴版本依序將 list 裡的 node 存進 `space` 陣列中，當第 `space[i]` 與 `space[i-1]` 擁有同樣的 node 數（lsit 的長度一樣）時，將兩者進行 merge 並存到 `space[i-1]` 。 ```c void merge_sort_iter(struct list_head *head) { int num = q_size(head); num = log2(num) + 1; int stack[num]; struct list_head *space[num]; head->prev->next = NULL; head->prev = NULL; struct list_head *node = head->next; int i = 0; while (node) { space[i] = node; stack[i] = 0; struct list_head *tmp = node; node = node->next; tmp->next = NULL; int j = i - 1; while (j >= 0) { if (stack[j] == stack[j + 1]) { space[j] = merge(space[j], space[j + 1]); stack[j]++; j--; i--; } else break; } i++; } i--; while (i) { space[i - 1] = merge(space[i - 1], space[i]); i--; } head->next = space[0]; struct list_head *current, *prev; for (current = head->next, prev = head; current; current = current->next, prev = prev->next) current->prev = prev; prev->next = head; head->prev = prev; return; } ``` ### 研讀 [linux/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) - 需要傳入 `list_sort()` 的三個參數 1. `priv` : 傳輸 `cmp` 所需參數的 pointer 2. `head` : 要排序的 list 3. `cmp` : 比較自定義大小的 function pointer，當 `a` 須置於 `b` 之後時會回傳大於 0 的值 - 以升序排列為例，當 `a` > `b` 時便會回傳大於 0 的值 - `list_sort` 為 stable sort ，故不必區分小於或等於 0 的分別 - `list_sort` 跟一般的 `bottom-up mergesort` 不同，後者每當出現 2 個 $2^k$ 大小的 list 時就會進行合併，前者則是當第 3 個 $2^k$ 大小的 list 出現時才進行合併。這樣做的好處是避免了 worst case 的出現，當要排序的 list 大小只比 $2^k$ 大一點點時，`bottom-up mergesort` 的最後一次合併就會出現極端的情況。舉個例子，當 list 大小為 9 時， `bottom-up mergesort`最後一次合併的 2 個 list 大小分別會是 8 和 1；而 `list_sort` 則會是 4 和 5 ，後者很明顯地會優於前者。事實上，不論要排序的 list 大小為何， `list_sort` 的合併都不會出現比 2 : 1 還糟糕的情況。 - 從 `list_sort` 的程式碼中，我發現了幾個自己實作的 merge sort 可以改進的地方 - sort 過的 list 可以用 `struct list_head()` 的 `prev` 指標來串聯，如此就不須宣告新的空間去存放 - 試著只用一個 integer `count` 去控制 list 的合併 - 上述兩點可以使 sort 少走訪一次整個 list (不必在一開始計算 list 的 node 數) - 在最後一次的合併就把整個 list 的 `prev` 連接回去 - 可以使 sort 少走訪一次 list - 修改後的程式碼 ```c void final_merge(struct list_head *left, struct list_head *right, struct list_head *head) { struct list_head **temp = &head; while (left && right) { if (strcmp(list_entry(left, element_t, list)->value, list_entry(right, element_t, list)->value) <= 0) { left->prev = *temp; (*temp)->next = left; left = left->next; } else { right->prev = *temp; (*temp)->next = right; right = right->next; } temp = &(*temp)->next; } (*temp)->next = left ? left : right; while ((*temp)->next) { (*temp)->next->prev = *temp; temp = &(*temp)->next; } (*temp)->next = head; head->prev = *temp; return; } void merge_sort_iter(struct list_head *head) { struct list_head *pending = NULL; struct list_head *list = head->next; head->prev->next = NULL; head->prev = NULL; int count = 0; while (list) { list->prev = pending; pending = list; list = list->next; pending->next = NULL; struct list_head **tail = &pending; for (int bits = count;; bits >>= 1) { if (bits & 1) { struct list_head *a = *tail, *b = a->prev; a = merge(b, a); a->prev = b->prev; *tail = a; } else break; } count++; } list = pending; pending = pending->prev; while (pending) { struct list_head *next = pending->prev; if (!next) break; list = merge(pending, list); pending = next; } final_merge(pending, list, head); return; } ``` - 測試兩者間效能差異 - 測試用的命令檔（由於第一次 sort 測出來的時間會跟之後的有明顯落差，故皆不採記第一次的結果） ``` option echo 0 option verbose 1 # fault new it RAND 300000 time sort # 1 new it RAND 300000 time sort # 2 new it RAND 300000 time sort # 3 new it RAND 300000 time sort # 4 new it RAND 300000 time sort # 5 new it RAND 300000 time sort ``` - 測試結果 - 原始版本 ``` ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest -f traces/test1.cmd cmd> option echo 0 # fault Delta time = 0.242 # 1 Delta time = 0.381 # 2 Delta time = 0.396 # 3 Delta time = 0.391 # 4 Delta time = 0.386 # 5 Delta time = 0.383 ``` - 修改後 ``` ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest -f traces/test1.cmd cmd> option echo 0 # fault Delta time = 0.207 # 1 Delta time = 0.325 # 2 Delta time = 0.327 # 3 Delta time = 0.333 # 4 Delta time = 0.333 # 5 Delta time = 0.330 ``` - 把修改後的 5 次測試時間加起來除以原始版本的 5 次測試時間，得出來的值約為 0.85 ，效能提昇了 15％左右 ### 引入 [linux/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 引入方法參考自 [2020leon](https://hackmd.io/@6649/linux2022-lab0#%E5%AF%A6%E5%81%9A%E4%BD%87%E5%88%97%EF%BC%88-queuec-%EF%BC%89) 1. 將 `list_sort.c` 和 `list_sort.h` 複製到 lab0-c 專案中。 - `list_sort.c` 直接從 [linux/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 複製。 - `list_sort.h` 從 linux 核心中的 include/linux/list_sort.h 複製。 2. 將型別 `u8` 更改為 `uint8_t`。 - 必須引入標頭檔 `stdint.h`。 3. 在 `list_sort.h` 加入 `likely(x)` 及 `unlikely(x)` 巨集定義。 ```c # define likely(x) __builtin_expect(!!(x), 1) # define unlikely(x) __builtin_expect(!!(x), 0) ``` 4. 在 `list_sort.c` 中新增 `listcmp()` 函式。 ```c int listcmp(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); } ``` 5. 使 cppcheck 忽略 `list_sort.c` 中 `merge` 函式產生的 `head` 未賦值錯誤 - 加入 `// cppcheck-suppress unassignedVariable` ```c // cppcheck-suppress unassignedVariable struct list_head *head, **tail = &head; ``` - 於終端機輸入 `$ cppcheck --inline-suppr list_sort.c` 6. 修改 `qtest.c` ，新增一個 option 以便於在 `list_sort` 及自己實作的排序法間做切換。 - 加入 option ```c ... static int listsort = 0; ... static void console_init() { ... add_param("listsort", &listsort, "Use list_sort or not", NULL); } ``` - 修改 `do_sort()` 函式 ```c bool do_sort(int argc, char *argv[]) { ... if (exception_setup(true)){ if(!listsort) q_sort(l_meta.l); else list_sort(NULL, l_meta.l, cmp); ... } ``` 測試 list sort 和自己的排序法效能落差，測出來自己的排序法慢了大概 10％ ``` ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest -f traces/test.cmd cmd> option echo 0 # fault Delta time = 0.273 # user version Delta time = 0.376 Delta time = 0.408 Delta time = 0.390 Delta time = 0.377 Delta time = 0.374 # list sort Delta time = 0.358 Delta time = 0.342 Delta time = 0.340 Delta time = 0.342 Delta time = 0.344 ``` 而如果是用參考 list sort 後所修改的版本則大約快了 5％ ``` ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest -f traces/test.cmd cmd> option echo 0 # fault Delta time = 0.207 # user version Delta time = 0.323 Delta time = 0.321 Delta time = 0.327 Delta time = 0.336 Delta time = 0.333 # list sort Delta time = 0.344 Delta time = 0.348 Delta time = 0.344 Delta time = 0.343 Delta time = 0.343 ``` 我還蠻意外會比 list sort 快的，具體比較快的原因待驗證 ## qtest.c ### 實作 shuffle 演算法使用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，該演算法之 pseudocode 如下： ``` -- To shuffle an array a of n elements (indices 0..n-1): for i from n−1 downto 1 do j ← random integer such that 0 ≤ j ≤ i exchange a[j] and a[i] ``` 實作之程式碼如下： ```c static void shuffle(struct list_head *head) { int num = q_size(head); struct list_head *tmp, *current; for(tmp = head->prev; num > 0; num--){ current = head; for(int i = rand() % num; i >= 0; i--) current = current->next; char *value = list_entry(current, element_t, list)->value; list_entry(current, element_t, list)->value = list_entry(tmp, element_t, list)->value; list_entry(tmp, element_t, list)->value = value; } } 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(1, "list is null"); return false; } else if (list_empty(l_meta.l)) { report(1, "list is empty"); return false; } else if (list_is_singular(l_meta.l)) { report(1, "no need to shuffle"); return false; } shuffle(l_meta.l); show_queue(3); return true; } ``` 最後在 `console_init()` 添加指令： ``` ADD_COMMAND(shuffle, " | Shuffle the list"); ``` ### 提供 web 命令因為要整合 [tiny-web-server](https://github.com/7890/tiny-web-server) ，所以先試著引入 `tiny.c` ，並分一個 `tiny.h` 出來存放其他檔案會用到的部份。 - 其中的 `process()` 需要進行修改，這部份稍後再提 ```c #ifndef __TINY_H #define __TINY_H #include <arpa/inet.h> /* inet_ntoa */ #include <dirent.h> #include <errno.h> #include <fcntl.h> #include <netinet/in.h> #include <netinet/tcp.h> #include <signal.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/sendfile.h> #include <sys/socket.h> #include <sys/stat.h> #include <sys/types.h> #include <time.h> #include <unistd.h> typedef struct { char filename[512]; off_t offset; /* for support Range */ size_t end; } http_request; /* Simplifies calls to bind(), connect(), and accept() */ typedef struct sockaddr SA; int open_listenfd(int port); char *process(int fd, struct sockaddr_in *clientaddr); void parse_request(int fd, http_request *req); #endif /* __TINY_H */ ``` 然後把 `tiny.c` 和 `tiny.h` 加到 `Makefile` 裡，在 `OBJS := `後面加入 `tiny.o` ``` OBJS := console.o qtest.o report.o harness.o queue.o \ random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \ linenoise.o tiny.o ``` 接著基本上就照著[作業說明](https://hackmd.io/@sysprog/linux2022-lab0#%E6%95%B4%E5%90%88-tiny-web-server)完成首先在 `linenoise.h` 中加入變數 `noise` 和 `listenfd` ```c bool noise; int listenfd; ``` 修改 `linenoiseEdit()` ，在 `while(1)` 裡加入以下程式碼 ```c if (listenfd) { fd_set set; FD_ZERO(&set); FD_SET(listenfd, &set); FD_SET(stdin_fd, &set); struct sockaddr_in clientaddr; socklen_t clientlen = sizeof(clientaddr); int rv = select(listenfd + 1, &set, NULL, NULL, NULL); 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; } } else { nread = read(l.ifd, &c, 1); if (nread <= 0) return l.len; } ``` 修改 `run_console()` ，讓其依照 `linenoise` 開啟與否決定要用 `linenoise` 還是 `cmd_select` ```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) { 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; } ``` 修改 `cmd_select()` ，新增對於 web 端輸入的處理 ```c 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--; 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; } ``` 修改 `tiny.c` 中的 `process()` ， `process()` 會處理 http 請求，將其轉換成符合 `cmd` 的命令格式 ```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; char *p = req.filename; /* Change '/' to ' ' */ while (*p && (*p) != '\0') { ++p; if (*p == '/') { *p = ' '; } } #ifdef LOG_ACCESS log_access(status, clientaddr, &req); #endif char *ret = malloc(strlen(req.filename) + 1); strncpy(ret, req.filename, strlen(req.filename) + 1); return ret; } ``` 最後在 `qtest.c` 中新增 `do_web()` 函式和 `web` 指令 - 加入 `set_echo(false);` 是為了避免在 `web` 開啟後從使用者端輸入指令會重複印出的情形 ```c static bool do_web(int argc, char *argv[]) { noise = false; set_echo(false); listenfd = open_listenfd(9999); printf("listen on port 9999, fd is %d\n", listenfd); return true; } ``` ```c ADD_COMMAND(web, " | Open web server"); ``` 執行結果 ``` ericliau@ericliau-GL502VML:~/linux2022/lab0-c$ ./qtest cmd> web listen on port 9999, fd is 3 cmd> accept request, fd is 4, pid is 53178 127.0.0.1:58584 200 - 'new' (text/plain) l = [] cmd> accept request, fd is 4, pid is 53178 127.0.0.1:58586 200 - 'ih a' (text/plain) l = [a] cmd> accept request, fd is 4, pid is 53178 127.0.0.1:58588 200 - 'ih b' (text/plain) l = [b a] cmd> accept request, fd is 4, pid is 53178 127.0.0.1:58590 200 - 'ih c' (text/plain) l = [c b a] cmd> ih d l = [d c b a] cmd> ih e l = [e d c b a] cmd> accept request, fd is 4, pid is 53178 127.0.0.1:58592 200 - 'sort' (text/plain) l = [a b c d e] ``` ## 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤 `qtest` 執行後並未發生錯誤，尚在尋找原因 ## select 系統呼叫 `select` 的功用是同時監測多個 `file descriptor` ，直到其中一個準備好要進行 I/O 。而 `lab0` 使用 `select` 的地方在函式 `cmd_select()` 中，透過實作 `web` 指令，可以得知其主要用來偵測是由使用者端還是從 web 端輸入指令。 ## 分析 console.c 先說結論 : 使用 RIO 套件可以在讀 cmd 檔的時候減少呼叫系統指令 `read` 的次數。因為 RIO 套件支援 buffered I/O ，在讀行時只需要呼叫 1 次 `read` 系統指令將一個 buffer 大小的資料存進 buffer ，再從 buffer 中一個字一個字的尋找換行符即可。如果不使用 buffer ，因為需要尋找換行符的緣故，每次呼叫 `read` 只能讀一個字元，導致需要頻繁的呼叫 `read` 指令，使得 OS 必須不斷地在 kernel-mode 和 user-mode 間做切換。 ## 研讀論文〈Dude, is my code constant time?〉這篇論文使用 [dudect](https://github.com/oreparaz/dudect) 這個程式來測量某個程式執行時間是否為 constant time 。其中使用的 [Student’s t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 為一種估計期望值的統計學方法，用於樣本量不大且不知道標準差的情況。該論文使用 leakage detection test ，因為是透過統計模型來推斷是否為 constant time，使得此方法並不局限於特定的 CPU 硬體，方法步驟如下: 1. 分別用固定和隨機的輸入資料進行多次測試 2. 去掉極端值然後進行 high-order preprocessing 3. 用統計方法判定是否符合常態時間，本專案使用 [Welch's t-test](https://en.wikipedia.org/wiki/Welch's_t-test) ### lab0 實作 lab0 檢查是否 constant time 的函式主要位於 `dudect/` 中，其呼叫路徑為 `is_XXX_const() -> TEST_CONST() -> doit()` ，測試步驟基本在 `doit()` 中完成。 ```c static bool doit(int mode) { int64_t *before_ticks = calloc(n_measure + 1, sizeof(int64_t)); int64_t *after_ticks = calloc(n_measure + 1, sizeof(int64_t)); int64_t *exec_times = calloc(n_measure, sizeof(int64_t)); uint8_t *classes = calloc(n_measure, sizeof(uint8_t)); uint8_t *input_data = calloc(n_measure * chunk_size, sizeof(uint8_t)); if (!before_ticks || !after_ticks || !exec_times || !classes || !input_data) { die(); } prepare_inputs(input_data, classes); measure(before_ticks, after_ticks, input_data, mode); differentiate(exec_times, before_ticks, after_ticks); update_statistics(exec_times, classes); bool ret = report(); free(before_ticks); free(after_ticks); free(exec_times); free(classes); free(input_data); return ret; } ``` `prepare_inputs()` 產生多個長度為 7 bytes 的隨機字串 (加上 `\0` 為 8 bytes)，並將資料分成兩個 class。 `measure()` 將 `prepare_inputs()` 產生的字串根據不同操作進行測量，測量方式為分別記錄執行該操作前後當下的 cycle 數。 `differentiate()` 計算兩者 cycle 數的差值，即該操作執行所花費的 cycle 數。 `update_statistics()` 再用得到的執行 cycle 數分別算出兩個 class 的平均數和變異數。 `report()` 將所求出的值用 Welch’s t-test 算出 `t` 值，並判斷對應操作是否為 constant time 。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.