# 2022q1 Homework1 (lab0)
contributed by < `Kevin-Shih` >
## 開發環境
```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): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
Stepping: 9
CPU MHz: 2500.000
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 4999.90
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-3
```
:::danger
注意作業書寫規範：中英文間用一個半型空白字元區隔。留意細節。
:notes: jserv
:::
## 作業要求
- [x] `q_new`
- [x] `q_free`
- [x] `q_insert_head`
- [x] `q_insert_tail`
- [x] `q_remove_head`
- [x] `q_remove_tail`
- [x] `q_size`
- [x] `q_delete_mid`
- [x] `q_delete_dup`
- [x] `q_swap`
- [x] `q_reverse`
- [x] `q_sort`
- [x] `qtest` 提供新的命令 `shuffle`
- [ ] `qtest` 提供新的命令 `web`
- [x] 詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」並應用裡頭提及的手法，例如 pointer to pointer (indirect pointer)，讓程式碼更精簡且有效
- [x] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
- [x] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 qtest 執行過程中的錯誤
- [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點
- [ ] 研讀論文〈[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
## Queue 實做
### 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;
}
```
若 `head` 為 `NULL` 則直接返回 0 ，否則以 `list_for_each` 遍歷整個 queue 來計算 size (其中 `len` 變數作為計數器)。
:::warning
不要只張貼程式碼，你應該解釋程式碼運作原理，並提及你認為後續如何改進。
:notes: jserv
:::
### q_new
```c
//ver 2
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
"malloc return null pointer when allocate failed or allocate zero space."
因此當 q 為 `NULL` 時直接 return `NULL` 以避免後續 `INIT_LIST_HEAD()` 嘗試對其初始化
### q_insert_head 及 q_insert_tail
```c
element_t *q_new_element(char *s)
{
element_t *q = malloc(sizeof(element_t));
if (!q)
return NULL;
q->value = malloc(strlen(s) + 1);
if (!q->value) {
free(q);
return NULL;
}
strncpy(q->value, s, strlen(s) + 1);
return q;
}
bool q_insert_head(struct list_head *head, char *s)
{
element_t *ele = q_new_element(s);
if (!ele)
return false;
list_add(&ele->list, head);
return true;
}
```
由於 `q_insert_head` 及 `q_insert_tail` 都需要為新的 `element` 及 `element->value` 分配各自的空間，因此將這部份獨立出來以 `q_new_element` 處理並將輸入的字串複製到 `element->value` 指向的空間。
:::info
參閱 CERN [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml "CERN") 中建議避免使用 strcpy 等涵式，故採用 CERN 提及的替代方案 strncpy 處理字串複製。
:::
### q_reverse
```c
void q_reverse(struct list_head *head)
{
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
node->next = node->prev;
node->prev = safe;
}
safe = head->prev;
head->prev = head->next;
head->next = safe;
}
```
使用 `list_for_each_safe()` 實做，避免修改 `node->next` 時導致無法正常遍歷整個 queue 以及修改 `node->prev` 時無法使用。 (`list_for_each_safe()` 會將 `node->next` 先暫存在 `safe`)
### q_free
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
}
```
為避免 NULL queue operation 先判斷 `l` 是否為 `NULL` ，若不是才繼續以 `list_for_each_entry_safe()` 遍歷 queue 中所有 element 並以 `q_release_element()` 釋放所佔用的記憶體。
### q_remove_head 及 q_remove_tail
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL; // Queue is NULL or empty
element_t *ele = list_entry(head->next, element_t, list);
head->next->next->prev = head;
head->next = head->next->next;
if (sp) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0'; // Ensure the string is null terminate
}
return ele;
}
```
使用 `list_entry` 取得 queue 中首個 entry 的指標 (由於接下來會修改 `head->next` 故須先取得其指標)，接者重新調整下個 node 的 `prev` 指向 `head` 及 `head->next` 指向下個 node ，來繞過被 remove 的 entry 。
當 `sp` 不是 `NULL` 時，從被 remove 的 entry 複製最多 bufsize - 1 個字元到 `sp` 。
### q_delete_mid
```c
// ver 1
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || head->next == head)
return NULL; // Queue is NULL or empty
int mid = q_size(head) / 2;
struct list_head *pos = head->next;
for (int i = 0; i < mid; i++) // pos will stop at middle node
pos = pos->next;
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
q_release_element(list_entry(pos, element_t, list));
return true;
}
```
一開始的想法很直覺的以 `q_size` 取得 queue 中有多少個 node ，再計算 mid 的位置後，以迴圈將 `pos` 指標移動到該 node 。 調整前後 node 的指標來繞過該 node ，最後以 list_entry 搭配 q_release_element 釋放該 entry 佔用的記憶體空間。
:::warning
TODO
在以 `q_size` 取得 queue 中有多少個 node 時須以迴圈形式遍歷整個 queue ，接者在移動 `pos` 時又再次使用迴圈，考慮將兩者整合為使用一次迴圈來改善效能。
另外，詳閱「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)」!
:::
### q_swap
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || q_size(head) < 2)
return; // Queue is NULL or less than 2 node (0,1)
for (struct list_head *slow = head->next, *fast = head->next->next;
fast != head && fast != head->next;
slow = slow->next, fast = slow->next) {
slow->prev->next = fast;
fast->next->prev = slow;
slow->next = fast->next;
fast->prev = slow->prev;
slow->prev = fast;
fast->next = slow;
}
}
```
`slow` 及 `fast` 分別指向相鄰的兩個 node ，並將兩者交換(next 及 prev 重新指向正確的 node)，交換完後 `slow` 及 `fast` 會指向下兩個 node 準備交換，重複直到 `fast` 再次指向 `head` 或 `head->next`。
:::warning
下次不用說「待補」，而是明確說出你的規劃和準備。
:notes: jserv
:::
### q_delete_dup
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
struct list_head *slow = head->next, *fast = head->next->next, *del = NULL,
*tmp = NULL;
for (; fast != head && fast != head->next;
slow = slow->next, fast = slow->next) {
if (strcmp(list_entry(slow, element_t, list)->value,
list_entry(fast, element_t, list)->value) == 0) {
while (fast->next != head &&
strcmp(list_entry(fast, element_t, list)->value,
list_entry(fast->next, element_t, list)->value) == 0)
fast = fast->next;
// slow:node before duplicate sub queue
// fast:node after duplicate sub queue
slow = slow->prev;
fast = fast->next;
// release duplicate nodes
for (del = slow->next; del != fast; del = tmp) {
tmp = del->next;
q_release_element(list_entry(del, element_t, list));
}
// link `slow` and `fast`
slow->next = fast;
fast->prev = slow;
}
}
return true;
}
```
`slow` 及 `fast` 兩個 pointer 用來指向相鄰的 node 並比較兩者是否 duplicate 直到首次出現 duplicate 的情形後 `fast` 會繼續向前，停在 duplicate 情形結束的 node ，而 `slow` 則停在 duplicate 情形開始前的 node ，接者依序釋放 `slow` 及 `fast` 間的 node 所佔用的記憶體空間，並將 `slow` 接上 `fast` 的 node 。
:::warning
TODO
補上 q_delete_dup 的改善方法。
:::
### q_sort
```c
// ver 1 iterative
struct list_head *merge_2_Queue(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node = NULL;
for (; L1 && L2; ptr = &(*ptr)->next, *node = (*node)->next) {
node = strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) < 0
? &L1
: &L2;
*ptr = *node;
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
void q_sort(struct list_head *head)
{
if (!head || q_size(head) < 2)
return; // Queue is NULL or less than 2 node
// devide
int queueSize = 0;
struct list_head *queue[10000] = {NULL};
for (struct list_head *tmp = head->next->next; tmp != head->next;
tmp = tmp->next) {
tmp->prev->next = NULL;
tmp->prev->prev = NULL;
queue[queueSize++] = tmp->prev;
}
// merge and sort
while (queueSize > 1) {
for (int i = 0, j = queueSize - 1; i < j; i++, j--)
queue[i] = merge_2_Queue(queue[i], queue[j]);
queueSize = (queueSize + 1) / 2;
}
// repair prev links and circular
head->next = queue[0];
struct list_head *tmp = head;
for (; tmp->next != NULL; tmp = tmp->next)
tmp->next->prev = tmp;
tmp->next = head;
head->prev = tmp;
}
```
最初使用 iterative 方式實做的 q_sort ，在標注 `devide` 的部份先以迴圈方式將除了 head 以外的 entry 分割為獨立的 entry (`prev`, `next` 都設為 null) 再存入 `queue` 指標陣列中，視為單一一個 sorted list。這也造成目前最大的問題， line 22 宣告的 list_head 陣列 `queue` 大小有限，無法排序較大的 queue。 (`queue` 用於存放分割後的單一個 entry ，以便後續 merge)
參考 [kdnvt 的開發紀錄](https://hackmd.io/@5ux520T8Sd-OoYfdxZR55Q/SyzDKJ9y9#q_sort "title")，q_sort 的部份提到使用每個 sorted list 的 tail->next 指向下個 sorted list ，預計以這樣思路改寫並維持 iterative 的方式。
```c
// ver 2
struct list_head *merge_2_queue(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node = NULL;
for (; L1 && L2; ptr = &(*ptr)->next, *node = (*node)->next) {
node = strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) < 0
? &L1
: &L2;
*ptr = *node;
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
// repair prev links and circular
struct list_head *tmp = head;
for (; tmp->next != NULL; tmp = tmp->next)
tmp->next->prev = tmp;
head->prev = tmp;
return head;
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return; // Queue is NULL or less than 2 node
// devide
struct list_head *pos;
list_for_each(pos, head)
pos->prev = pos;
// pointer `first` point to first sorted list
struct list_head *first = head->next;
INIT_LIST_HEAD(head);
// merge sorted lists till only one sorted list left
while (first->prev->next != head) {
struct list_head **list = &first;
struct list_head *next_list = (*list)->prev->next;
struct list_head *next_next_list = next_list->prev->next;
while (*list != head && next_list != head) {
// mark the sorted list's tail
(*list)->prev->next = NULL;
next_list->prev->next = NULL;
(*list) = merge_2_queue((*list), next_list);
// make merged sorted list's tail point its next to next sorted list
list = &(*list)->prev->next;
*list = next_next_list;
next_list = (*list)->prev->next;
next_next_list = next_list->prev->next;
}
}
list_add_tail(head, first);
}
```
實做上述作法後，發現雖然可以正確排序，但由於處理大佇列時仍然過慢 (很可能是在 `merge_2_queue` 修補 `prev` 時需重新遍歷，拖累速度)，因此仍過不了 `trace_14` 。
```c
// ver 3 solve it recursively
struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head;
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow->next;
slow->next = NULL;
struct list_head *left = merge_sort(head), *right = merge_sort(mid);
return merge_2_queue(left, right);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return; // Queue is NULL or less than 2 node
// mark queue's tail
head->prev->next = NULL;
head->next = merge_sort(head->next);
// repair prev links and make it circular
struct list_head *ptr;
for (ptr = head; ptr->next; ptr = ptr->next)
ptr->next->prev = ptr;
ptr->next = head;
head->prev = ptr;
}
```
最後採用最典型的 merge sort 解法，將其視為 singly linked list 做完 recursive 的 merge sort 後在一一走訪節點，修復 `prev` 以及 circular 的特性。這種作法的速度足以通過 `trace_14` 。
:::warning
TODO
補上 q_sort 改善方法。
:::
## 研讀 Linux 核心的 lib/list_sort.c
根據 lib/list_sort.c 中的註解可以發現在做 merge 時是將 list 視為 null terminate 的 singly linked list 的藉此省去了每次合併時修復 `prev` 的操作，而只在最後一次合併時才改為呼叫 merge_final 以修復 `prev` 並維持 circular 特性。而在 merge 的過程中 `prev` 則用來連排序好的 sub list 。
在讀對應的 [commit massage](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 時 George Spelvin 提到 top-down 的方式雖然可以很好的分割 sublist 來達到 balance 的 merge 但由於需要知道 linked list 的 size 需要一一走訪每個節點，當 list 超過 L1 cache size 時更會造成大量的 cache miss。
lib/list_sort.c 採用的是 buttom-up 的方式，然而並非完全的遵照 depth-first order ，儘管 depth-first order 可以很好的善用 L1 cache ，通常只有最後幾次 merge 為超出 L1 的大小而產生 cache miss。 但當 n 比 2 的冪次稍大時(例如:1028)，最後的 merge 將會不平衡。 George Spelvin 提到為了避免這樣的情形發生，合併時將會盡可能維持最差 2:1 的合併比例。
### 嘗試引入 lab0-c 並比較與自己實做的 merge sort 的成果。
#### 定義 list_cmp_func_t
```c
typedef int
__attribute__((nonnull(2, 3))) (*list_cmp_func_t)(void *,
struct list_head const *,
struct list_head const *);
```
定義一個 function pionter `list_cmp_func_t` 稍後指向自定義的 compare function ，其中這個 compare function 應是 (pointer, pointer to struct list_head const, pointer to struct list_head const) 並 return int 的形式。
>參考[研讀 Linux 核心的 lib/list_sort.c 原始程式碼](https://hackmd.io/@DokiDokiPB/SJfES914O#list_sort)中關於自訂 compare function 的方式。
:::spoiler compare function
```c
int cmp_func(void *priv, struct list_head const *a, struct list_head const *b)
{
return strcmp(list_entry(a, element_t, list)->value,
list_entry(b, element_t, list)->value);
}
```
:::
:::spoiler list sort (full)
除定義 compare function 及補上 define likely 和 unlikely 外均與 lib/list_sort.c 中相同。
```c
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
/*
* Define list_cmp_func_t as a pointer to function
* which return int.
*/
typedef int
__attribute__((nonnull(2, 3))) (*list_cmp_func_t)(void *,
struct list_head const *,
struct list_head const *);
/* Define the cmp function to use in kernel sort */
int cmp_func(void *priv, struct list_head const *a, struct list_head const *b)
{
return strcmp(list_entry(a, element_t, list)->value,
list_entry(b, element_t, list)->value);
}
/*
* Returns a list organized in an intermediate format suited
* to chaining of merge() calls: null-terminated, no reserved or
* sentinel head node, "prev" links not maintained.
*/
__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)
{
struct list_head *head = NULL, **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;
}
/*
* Combine final list merge with restoration of standard doubly-linked
* list structure. This approach duplicates code from merge(), but
* runs faster than the tidier alternatives of either a separate final
* prev-link restoration pass, or maintaining the prev links
* throughout.
*/
__attribute__((nonnull(2, 3, 4, 5))) static void merge_final(
void *priv,
list_cmp_func_t cmp,
struct list_head *head,
struct list_head *a,
struct list_head *b)
{
struct list_head *tail = head;
uint8_t count = 0;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
tail->next = a;
a->prev = tail;
tail = a;
a = a->next;
if (!a)
break;
} else {
tail->next = b;
b->prev = tail;
tail = b;
b = b->next;
if (!b) {
b = a;
break;
}
}
}
/* Finish linking remainder of list b on to tail */
tail->next = b;
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
/* And the final links to make a circular doubly-linked list */
tail->next = head;
head->prev = tail;
}
/* Linux kernel 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;
/*
* Data structure invariants:
* - All lists are singly linked and null-terminated; prev
* pointers are not maintained.
* - pending is a prev-linked "list of lists" of sorted
* sublists awaiting further merging.
* - Each of the sorted sublists is power-of-two in size.
* - Sublists are sorted by size and age, smallest & newest at front.
* - There are zero to two sublists of each size.
* - A pair of pending sublists are merged as soon as the number
* of following pending elements equals their size (i.e.
* each time count reaches an odd multiple of that size).
* That ensures each later final merge will be at worst 2:1.
* - Each round consists of:
* - Merging the two sublists selected by the highest bit
* which flips when count is incremented, and
* - Adding an element from the input as a size-1 sublist.
*/
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);
/* 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);
}
```
:::
#### 比較兩者的 compare 數
採用 K 值作為比較基準，其中 K 值定義如下：
$C(n) = n log_2 (n) - K n+O(1)$
$K = log_2 (n) - (C(n)-1)/n$
自行定義的測試命令中，由於該 commit 提到當 n 比 2 的冪次稍大時，最後的 merge 會非常不平衡，因此決定測試 n 到 1.25n 間的平均 K 值來了解兩個實做間的差異。 (一方面也是節省測試所需時間)
```c
static bool do_avg_k(int argc, char *argv[]){
if (argc != 3) {
report(1, "%s needs 2 arguments", argv[0]);
return false;
}
list_cmp_func_t list_cmp_func = &cmp_func;
if (l_meta.l)
q_free(l_meta.l);
int big_n = (int)(atoi(argv[2]) * 1.25);
double avg_k = 0;
for (int n = atoi(argv[2]); n < big_n; n++) {
l_meta.l = q_new();
for (int j = 0; j < n; j++) {
char randstr_buf[MAX_RANDSTR_LEN];
fill_rand_string(randstr_buf, sizeof(randstr_buf));
q_insert_head(l_meta.l, randstr_buf);
}
if (strcmp(argv[1], "lksort") == 0)
list_sort(NULL, l_meta.l, list_cmp_func);
else
q_sort(l_meta.l);
avg_k += log2(n) - (double) (cmp_count-1) / n;
q_free(l_meta.l);
}
l_meta.l = NULL;
avg_k /= (big_n - atoi(argv[2]));
printf("K = %f\n", avg_k);
return true;
}
```
寫完測試程式後忽然想起，我自己實做的版本是 Top-down 的方式，取得 list size 後從中間對半切再遞迴呼叫 merge_sort ，因此理論上會有較好的 K 值，但實際計時時應該會被取得 list size 時走訪個節點的耗時(及很有可能發生的 cache miss)拖累，相較 list_sort 慢上不少。
以下為實際測試結果:
```
cmd> avg_k sort 512
K = 1.249437
cmd> avg_k sort 1024
K = 1.247953
cmd> avg_k sort 2048
K = 1.249297
cmd> avg_k lksort 512
K = 1.221241
cmd> avg_k lksort 1024
K = 1.218282
cmd> avg_k lksort 2048
K = 1.216285
```
果不其然，自己實做的版本 K 值稍大，約 0.03 左右，接者來測試實際執行時間。
#### 比較實際執行時間
使用 qtest 中的 time 命令來測試兩者在 50,000 和 100,000 及 500,000 隨機字串下排序的耗時。
50,000 隨機字串耗時:
```
cmd> new
l = []
cmd> ih RAND 50000
l = [nxcmts nwsgzcxho jrtcrl kdzwo bqdhrik axtxp tbmjsw gvnxgy kqlrztev pijiudmwb jgluxhcyj yywtr bjgjzsq bbjlelpu lnesvutv tgeiq rhcockda mihxsmgde gmyqlsi jsychrqmr hmhnmii gnbkx mprptofxr ucgabvt hpbjr qbcuoebg umwtgxmq rpztgc hlmela bzsztku ... ]
cmd> time sort
l = [aaabpmi aaaetwqt aaalw aaarmdvp aabpygyxe aabtnczlf aaclieo aacluheb aacyxvd aaczkvyay aadel aadjjnp aadlyxase aadpksyut aadttfggw aadvq aaeafdy aaebbf aaebqkyi aaefnlrw aaeha aaeyqfdn aafto aafyxrcj aagiqlgy aagmoa aagosr aahoyc aajmsuje aajric ... ]
Delta time = 0.052
cmd> new
Freeing old queue
l = NULL
l = []
cmd> ih RAND 50000
l = [usrlest plbgfzsbc zojyvta uvmuq popsy jqlwgnzg dzysya xdvcuuegc nvlocc tdwnxcc epyami xbfpksu ezpnpwss noyfi iukcwewmr qnigadjp zdqknec veqlvcn fnblkop fqwwsxsn wyemfur lhzkeagfv kodto lslngq dyubuzu xuijyygd ftpcmcp mojwvd tprjeox uxmsewtqv ... ]
cmd> time lksort
l = [aaajbzp aaajveqz aaaky aaasvpvh aaauu aabrlcd aacjrgieq aaclt aacux aadczkbq aadkjios aadlz aadnlq aaech aaefcsrpn aaejavm aaenpo aaeqnh aafvfjebu aafwzfha aaglkqrf aagmcrx aagnagnh aagzjyrrr aahegullk aaiamt aaigrv aaimcx aaiocb aaiqgbzyf ... ]
Delta time = 0.036
```
100,000 隨機字串耗時:
```
cmd> new
l = []
cmd> ih RAND 100000
l = [lkvypp vxjxfgvfo ktjfpkwwd ingtawlk szlmxqs ggbfbw qfuqkpiln dwmribtx icvoqryt anzkhnzpy clxgku qbxfm lpgldf sexxgztlc ftpixd vozeozox hwcwwcca ztnvod jjyyi aeescb oezdf kntlnwj sgrcp inddfjgnz nlgzady aijpikje jqpvsqeb uaqmn shnzar cldxkzvm ... ]
cmd> time sort
l = [aaabuvsu aaaeds aaaenlr aaagohoqa aaahbwkdp aaaic aaajqu aabbvkezr aabqxmerk aabxac aabzql aaccuryx aacik aackrzo aaclavxbj aacmtx aacrkh aacucrr aacvr aacyn aadamo aadbn aadbw aadfut aadir aadwhhefq aadxb aadxdwenu aadxrhgy aadybuynb ... ]
Delta time = 0.121
cmd> new
l = []
cmd> ih RAND 100000
l = [xqmbtdzj nlxgj eecvqvl tsxepebar rmqohtlxx lvnbobp auktzxlx bleaaxwt pyfmmgyco bfkqi ixqypqut uoymqg pdgke soqywenec sgrahh gyjajrxtt noigyaa hccxol dfnhykwu sehri mjfqf jlcquouzk afxxdj qdpew hjmcd xvwwjemc ouxgawlqv qahnylwv qgxfozrot wilet ... ]
cmd> time lksort
l = [aaaecdh aaagk aaahwwc aaamgaz aaanexne aaanumr aaarjj aaawolix aabep aabgf aabgpyf aabjpdqcw aabpgt aabyii aacajsw aacfh aacgzl aacmarur aacmbkjss aacpkqu aacxqjclo aacyx aadbgnv aadiwmjgp aadkl aaechhu aaeuvokk aaevyq aaexeo aaezd ... ]
Delta time = 0.099
```
500,000 隨機字串耗時:
```
cmd> new
l = []
cmd> ih RAND 500000
l = [jiafjwmf pjhdw pspdvfp nyoxivz vrzdo lwkiu jwizaobii qpvckk htcqbgtxx nvizb suqabm vjdncjhcb jxmer eapnhfw zrtesy awyrtsv uojpmo sohnfz avdpunqvq rtdhtjxu bexoryir ytxamnx xakqaeq rdwlm inxfscsov slbdtjr xgtotuh jhzmnyvf zthpcpcqi oonsc ... ]
cmd> time sort
l = [aaaadfbwi aaaaeed aaabpyg aaabue aaacnuld aaadsyog aaaegd aaaeljz aaahyhedq aaairzcv aaajkc aaakb aaakloc aaakneem aaamte aaamtf aaamx aaaqqaawi aaarsgjl aaasos aaatrmkx aaaucpsh aaaukg aaaulrww aaavxeb aaavydi aaawj aaayuzx aaazq aaazqrdj ... ]
Delta time = 0.720
cmd> new
l = []
cmd> ih RAND 500000
l = [wzwwo qefgjv ypidqrzsy xmpiwp besaqzxd zgbplp qthhhx xlgvnb qfmomtp dnobrmpcd fwqkwc rvajlwhf kwvbymj ioczki chmspww hkrzrh tyrugg ijogiedhj wdmnqeqp vxfxsptw qnsbzcd eafjxh hjxara kmjas fxazip zvxwsid ocvkqg pyovfprln gnkgvxj qllec ... ]
cmd> time lksort
l = [aaaaemb aaaafbd aaaav aaadnrok aaafmk aaafqm aaafz aaaght aaagjktjb aaags aaahb aaahjn aaahrc aaaid aaajelv aaaklwdi aaalc aaamzzxkq aaaoaw aaaqn aaarbh aaasy aaatjdrg aaaupw aaauwtsze aaavffvd aaawnoj aaawz aaaxi aaayfm ... ]
Delta time = 0.451
```
比較成果：
|Sort |50,000 time (s)|100,000 time (s)|500,000 time (s)|
|----------|------------|------------|------------|
|自行實做 |0.052 |0.121 |0.720 |
|list_sort |0.036 |0.099 |0.451 |
折線圖:
在比較實際執行時間時，top-down 作法的劣勢馬上顯現出來，3 種測試的佇列長度執行時間都比 list_sort 慢上不少。
:::warning
TODO
研讀維持 2:1 的 code 究竟是如何達成。
:::
## 在 qtest 中新增 shuffle 命令
```c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return; // Queue is NULL or less than 2 node
int n = q_size(head), rand_num = 0;
struct list_head *dest = head, *cur;
srand(time(NULL));
for(int i = n - 1; i > 0; i--){
cur = head->next;
rand_num = rand() % (i + 1);
for(int j = 0; j < rand_num; j++)
cur = cur->next;
list_move_tail(dest->prev, cur);
list_move_tail(cur, dest);
dest = dest->prev;
}
}
```
在閱讀 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法後，發現交換兩個 node 位置可以藉由兩次 `list_move_tail` 來完成，先將 `cur` 指向第 j 個 node (其中 j 以隨機亂數得到)，`dest` 指向要交換的 node 的下一個 node 。 接者將 `dest->prev` 透過 `list_move_tail` 移到 `cur` 之前，再以 `list_move_tail` 將 `cur` 移到 `dest` 之前的位置。
Shuffle 前:
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 1 | <ref2> }"];
c [label="{ <ref1> | <data> 2 | <ref2> }"];
d [label="{ <ref1> | <data> 3 | <ref2> }"];
d:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
假設第一次選中 `1` :
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 1 | <ref2> }"];
c [label="{ <ref1> | <data> 2 | <ref2> }"];
d [label="{ <ref1> | <data> 3 | <ref2> }"];
cur;
dest;
d:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cur -> b:n [arrowhead=vee];
dest -> a:n [arrowhead=vee];
}
```
如上圖所示當選中 `1` 時 `cur` 會指向該 node ， `dest` 則指向 `head`。
第一次 `list_move_tail` 後:
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 3 | <ref2> }"];
c [label="{ <ref1> | <data> 1 | <ref2> }"];
d [label="{ <ref1> | <data> 2 | <ref2> }"];
cur;
dest;
d:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cur -> c:n [arrowhead=vee];
dest -> a:n [arrowhead=vee];
}
```
呼叫 `list_move_tail(dest->prev, cur)` 將 `dest->prev` (即 node `3`) 移到 `cur` 的 `prev` 處，如上圖所示。
第二次 `list_move_tail` 後:
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 3 | <ref2> }"];
c [label="{ <ref1> | <data> 2 | <ref2> }"];
d [label="{ <ref1> | <data> 1 | <ref2> }"];
cur;
dest;
d:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
cur -> d:n [arrowhead=vee];
dest -> a:n [arrowhead=vee];
}
```
呼叫 `list_move_tail(cur, dest)` 將 `cur` (即 node `1`) 移到 `dest` 的 `prev` 處，如上圖所示。 最後將 `dest` 改為指向 `dest->prev` 即完成一次交換。
最後將 `dest` 改為指向 `dest->prev`:
```graphviz
digraph "Doubly Linked List" {
rankdir=LR;
node [shape=record];
a [label="{ <ref1> | <data> head | <ref2> }"]
b [label="{ <ref1> | <data> 3 | <ref2> }"];
c [label="{ <ref1> | <data> 2 | <ref2> }"];
d [label="{ <ref1> | <data> 1 | <ref2> }"];
dest;
d:data:s -> a:ref1:s [arrowhead=dot, arrowtail=vee, dir=both, headclip=false];
a:ref2:c -> b:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref2:c -> d:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref2:n -> a:data:n [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
d:ref1:c -> c:data:s [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
dest -> d:n [arrowhead=vee];
}
```
`cur` 會在下次選中 node 時重新指向該 node 。
>graphviz 參考資料：
https://stackoverflow.com/questions/70441786/draw-doubly-linked-list-using-graphviz
以及:
[kdnvt 的開發紀錄](https://hackmd.io/@5ux520T8Sd-OoYfdxZR55Q/SyzDKJ9y9#q_sort "title")
## 在 qtest 加入 web 命令
首先將 `tiny.c` 放入 lab0-c，並修改 makefile 來編譯它。
```c
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
linenoise.o tiny.o
```
接著修改 `tiny.c` ，刪去其中部份用不到的 function ，並修改 `main`。
```c
void tiny_create(int argc, char **argv)
{
if (argc > 1 && (!strcmp(argv[1], "-h") || !strcmp(argv[1], "--help"))) {
print_help();
return;
}
int default_port = DEFAULT_PORT;
char buf[256];
char *path = getcwd(buf, 256);
if (argc == 2) {
if (argv[1][0] >= '0' && argv[1][0] <= '9') {
default_port = atoi(argv[1]);
} else {
path = argv[1];
if (chdir(path) != 0) {
perror(path);
exit(1);
}
}
} else if (argc == 3) {
default_port = atoi(argv[2]);
path = argv[1];
if (chdir(path) != 0) {
perror(path);
exit(1);
}
}
printf("serve directory '%s'\n", path);
listenfd = open_listenfd(default_port);
if (listenfd > 0) {
printf("listen on port %d, fd is %d\n", default_port, listenfd);
} else {
perror("ERROR");
exit(listenfd);
}
// Ignore SIGPIPE signal, so if browser cancels the request, it
// won't kill the whole process.
signal(SIGPIPE, SIG_IGN);
return;
}
```
讓 `main` 僅負責啟動 server 並將 socket 對應的 fd 寫入 listenfd。 另外也修改 `parse_request` 如下。
```c
void parse_request(int fd, struct sockaddr_in *clientaddr, http_request *req)
{
rio_t rio;
char buf[MAXLINE], method[MAXLINE], uri[MAXLINE];
int status = 200;
req->offset = 0;
req->end = 0; /* default */
#ifdef LOG_ACCESS
printf("accept request, fd is %d, pid is %d\n", fd, getpid());
#endif
rio_readinitb(&rio, fd);
rio_readlineb(&rio, buf, MAXLINE);
sscanf(buf, "%1023s %1023s", method, uri); /* version is not cared */
/* read all */
while (buf[0] != '\n' && buf[1] != '\n') { /* \n || \r\n */
rio_readlineb(&rio, buf, MAXLINE);
if (buf[0] == 'R' && buf[1] == 'a' && buf[2] == 'n') {
sscanf(buf, "Range: bytes=%64lu-%64lu",
(unsigned long *) &req->offset, (unsigned long *) &req->end);
// Range: [start, end]
if (req->end != 0) {
req->end++;
}
}
}
char *filename = uri;
if (uri[0] == '/') {
filename = uri + 1;
int length = strlen(filename);
if (length == 0) {
filename = ".";
} else {
int i = 0;
for (; i < length; ++i) {
if (filename[i] == '?') {
filename[i] = '\0';
break;
}
}
}
}
url_decode(filename, req->filename, MAXLINE);
// replace all the `\` in `req->filename`
// to `space` and put it back.
strncpy(buf, req->filename, strlen(req->filename) + 1);
char *p = buf;
while ((p = strchr(p, '/')))
*p++ = ' ';
strncpy(req->filename, buf, strlen(buf) + 1);
#ifdef LOG_ACCESS
log_access(status, clientaddr, req);
#endif
}
```
修改後的 `parse_request` 除了取得 request 內容外，也將 `req->filename` 處理為 cmdline 的格式(替換所有 `\` 為 `space`)，並印出 LOG_ACCESS 。
接著為了方便接入 `qtest` ，將 `tiny.c` 中用的到的 function 放到自行建立的 `tiny_web.h` 供 `qtest` 呼叫。
```c
#ifndef TINY_WEB_H
#define TINY_WEB_H
#include <sys/types.h>
extern int listenfd;
/* Simplifies calls to bind(), connect(), and accept() */
typedef struct sockaddr SA;
typedef struct {
char filename[512];
off_t offset; /* for support Range */
size_t end;
} http_request;
/*
* Launch tiny_web_server
* The fd will write to `listenfd`
*/
void tiny_create(int argc, char **argv);
/*
* Process http request and print out LOG_ACCESS
* req->filename has been processed to macth
* cmdline format
*/
void parse_request(int fd, struct sockaddr_in *clientaddr, http_request *req);
#endif
```
>建立 `tiny_web.h` 參考：
[laneser的開發紀錄](https://hackmd.io/@laneser/linux2022_lab0#%E5%9C%A8-qtest-%E6%8F%90%E4%BE%9B%E6%96%B0%E7%9A%84%E5%91%BD%E4%BB%A4-web)
接著在 `qtest` 中加入 `web` 指令，並實做 `do_web` function。
```c
static bool do_web(int argc, char *argv[])
{
if (listenfd) {
report(3, "web already launched.");
return false;
} else {
// if web not launch yet, launch it.
tiny_create(argc, argv);
// set the fd to non-blocking mode
int flags = fcntl(listenfd, F_GETFL);
fcntl(listenfd, F_SETFL, flags | O_NONBLOCK);
return true;
}
}
```
>根據[作業要求](https://hackmd.io/@sysprog/linux2022-lab0#%E6%95%B4%E5%90%88-tiny-web-server):
先將 socket 改為 non-blocking，防止程式停止接收使用者輸入。
由於作業要求透過 `select()` 讓 `qtest` 在 `web` 或 `commandline` 輸入命令時就會執行相對應的命令，因此接下來就以[作業要求](https://hackmd.io/@sysprog/linux2022-lab0#%E6%95%B4%E5%90%88-tiny-web-server)中 `linenoiseEdit()` 的範本來修改。
`linenoiseEdit()` 中關於 `select()` 及處理 web 命令的部份：
```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;
switch (rv) {
case -1:
perror("select"); /* an error occurred */
continue;
case 0:
printf("timeout occurred\n"); /* a timeout occurred */
continue;
default:
if (listenfd && FD_ISSET(listenfd, &set)) {
connfd = accept(listenfd, (SA *) &clientaddr, &clientlen);
http_request req;
parse_request(connfd, &clientaddr, &req);
strncpy(buf, req.filename, strlen(req.filename) + 1);
return strlen(buf);
} else if (FD_ISSET(stdin_fd, &set)) {
nread = read(l.ifd, &c, 1);
if (nread <= 0)
return l.len;
/*
* 原先處理 cmdline 自動完成等功能的部份
* 由於 code 較多在此省略。
*/
}
}
```
在處理接收到的 request 改採先前修改的 `parse_request()` 取得以處理過得 `req.filename` 並將其複製到 `buf` 中作為該次 command。此外，這邊將關閉 `connfd` 延後，方便 command 完成後將執行結果回傳給 web 端。
修改 `report.c` 中顯示執行結果的 `report()` 及 `report_noreturn()`，當 `connfd` 未被重設為 `0` 時，將結果回傳給 web 端。
```c
/*
* report() 中加入下方的 code
* report_noreturn() 中則不回傳 "\n"
*/
if (connfd) {
int bufsize = 1024;
char buf[bufsize];
va_start(ap, fmt);
vsnprintf(buf, bufsize, fmt, ap);
va_end(ap);
if (write(connfd, buf, strlen(buf)) < 0)
printf("Write web error");
if (write(connfd, "\n", 1) < 0)
printf("Write web error");
}
```
最後修改 `console.c` 中的 `run_console()` ，讓程式在執行完該次 command 後，若有 `connfd` 則關閉該 fd 避免 web 端持續等待回應。
```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;
extern int connfd;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
/* 若該次 command 有開啟 connfd 則關閉它並重設為 0
* (即來自 web 的 command)
*/
if (connfd) {
close(connfd);
connfd = 0;
}
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
return err_cnt == 0;
}
```
:::spoiler 執行成果
server 端：
```c
$ valgrind ./qtest
// start web server
cmd> web
serve directory '/home/user/Senior/linux2022/lab0-c'
listen on port 9999, fd is 3
// command from cmdline
cmd> new
l = []
// command from cmdline
cmd> it RAND 5
l = [ofwqnitbv ipdzlgrm acknrh jycttdrb btkmbdaui]
// command from web
cmd> accept request, fd is 4, pid is 16507
127.0.0.1:50072 200 - 'sort'
l = [acknrh btkmbdaui ipdzlgrm jycttdrb ofwqnitbv]
// command from web
cmd> accept request, fd is 4, pid is 16507
127.0.0.1:50074 200 - 'reverse'
l = [ofwqnitbv jycttdrb ipdzlgrm btkmbdaui acknrh]
// command from web
cmd> accept request, fd is 4, pid is 16507
127.0.0.1:50076 200 - 'it RAND 10'
l = [ofwqnitbv jycttdrb ipdzlgrm btkmbdaui acknrh aiinqxw kqwvtr kiovxf gzqtpppf vrcnnx oysupaa einlywct deskm tjrnarq zgsykomo]
// command from web
cmd> accept request, fd is 4, pid is 16507
127.0.0.1:50078 200 - 'rt'
Removed zgsykomo from queue
l = [ofwqnitbv jycttdrb ipdzlgrm btkmbdaui acknrh aiinqxw kqwvtr kiovxf gzqtpppf vrcnnx oysupaa einlywct deskm tjrnarq]
// command from cmdline
cmd> shuffle
l = [kqwvtr aiinqxw einlywct oysupaa acknrh jycttdrb deskm kiovxf btkmbdaui ipdzlgrm gzqtpppf tjrnarq ofwqnitbv vrcnnx]
// command from cmdline
cmd> quit
Freeing queue
```
client 端：
```c
$ curl --http0.9 http://localhost:9999/sort
l = [acknrh btkmbdaui ipdzlgrm jycttdrb ofwqnitbv]
$ curl --http0.9 http://localhost:9999/reverse
l = [ofwqnitbv jycttdrb ipdzlgrm btkmbdaui acknrh]
$ curl --http0.9 http://localhost:9999/it/RAND/10
l = [ofwqnitbv jycttdrb ipdzlgrm btkmbdaui acknrh aiinqxw kqwvtr kiovxf gzqtpppf vrcnnx oysupaa einlywct deskm tjrnarq zgsykomo]
$ curl --http0.9 http://localhost:9999/rt
Removed zgsykomo from queue
l = [ofwqnitbv jycttdrb ipdzlgrm btkmbdaui acknrh aiinqxw kqwvtr kiovxf gzqtpppf vrcnnx oysupaa einlywct deskm tjrnarq]
```
:::
:::warning
TODO
解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。
:::
## 研讀論文〈Dude, is my code constant time?〉
論文中提到以 Welch's t-test 來檢定兩個不同 class 的測試資料的實際執行時間(如: cycle 數)是否來自(平均執行時間)不同的母體。其中一個 class 是固定的 input ，另一個 class 則是隨機的 input，在 `lab0-c` 中即對長度等於 input 長度的佇列進行操作(ih, it, rh, rt)。
Welch's t-test 是一種對於 student's t test 的修正，對兩樣本的變異數不同且(或)樣本數不同的情形下更為可靠。 (由於`執行時間`屬於變異數未知的資料故採用 Welch's t-test)
由於這篇論文所提出的方式是以實驗收集不同輸入條件下的執行時間來進行統計分析(檢定)，因此收集到的資料好壞、樣本數大小非常重要，當樣本數不足時可能無法辨別兩個 class input 的執行時間是否屬於不同母體(即非常數時間)。此外，這樣的統計分析所得到的結果也僅限於當前收集到的 $n$ 筆資料，無法進一步推斷 $n+1$ 時是否會是相同的結果(哪怕 $n$ 再怎麼趨近無窮大)。
其中關於資料的好壞，在 `lab0-c` 的實做中與論文中同樣為避免準備測試資料等待測的 `function` 以外的因素干擾，準備測試條件及資料的時間並未被記入。下方以測試 `ih` 為例：
```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;
```
:::warning
TODO
`drop_size` 作用？
:::
在 `lab0-c` 的實做中存在一些疑點，相較於論文中的實測往往達到幾十萬、百萬筆資料，`lab0-c` 中 `#define enough_measure 10000` 定義**足夠的測資**為 1 萬筆資料是否足夠，值得思考。
## 使用 valgrind 排除 qtest 實作的記憶體錯誤
- 使用 valgrind 檢測直接由 cmdline 輸入的情形
```c
$ valgrind -q --leak-check=full ./qtest
cmd> new
l = []
cmd> it 5
l = [5]
cmd> it RAND 5
l = [5 zbwdtd srnxrsku futritxj iprlaavt dcfhvyxc]
cmd> sort
l = [5 dcfhvyxc futritxj iprlaavt srnxrsku zbwdtd]
cmd> reverse
l = [zbwdtd srnxrsku iprlaavt futritxj dcfhvyxc 5]
cmd> shuffle
l = [futritxj srnxrsku zbwdtd dcfhvyxc iprlaavt 5]
cmd> rt
Removed 5 from queue
l = [futritxj srnxrsku zbwdtd dcfhvyxc iprlaavt]
cmd> free
l = NULL
cmd> new
l = []
cmd> dm
l = []
cmd> quit
Freeing queue
```
該情形下並未產生錯誤，經測試以 `ctrl + c` 中止 `qtest` 也無錯誤。
::: spoiler `ctrl + c` 中止
```c
$ valgrind -q --leak-check=full ./qtest
cmd> new
l = []
cmd> it RAND 10
l = [voofjnusv aadlsuk hcefnmw xvmaqkasn awfjfjqnz ybqblwa zudrh tbvdhh freetxhgt ohhhny]
cmd> // ctrl + c
Freeing queue
```
:::
- 使用 valgrind 測試當 `qtest` 以 -f 的方式讀入 `trace-xx-ops.cmd` 執行的情形
::: spoiler 測試結果
```c
$ valgrind -q --leak-check=full ./qtest -f traces/trace-05-ops.cmd
cmd> # Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
cmd> option fail 0
cmd> option malloc 0
cmd> new
l = []
cmd> ih dolphin
l = [dolphin]
cmd> ih bear
l = [bear dolphin]
cmd> ih gerbil
l = [gerbil bear dolphin]
cmd> reverse
l = [dolphin bear gerbil]
cmd> size
Queue size = 3
l = [dolphin bear gerbil]
cmd> it meerkat
l = [dolphin bear gerbil meerkat]
cmd> it bear
l = [dolphin bear gerbil meerkat bear]
cmd> it gerbil
l = [dolphin bear gerbil meerkat bear gerbil]
cmd> size
Queue size = 6
l = [dolphin bear gerbil meerkat bear gerbil]
cmd> rh dolphin
Removed dolphin from queue
l = [bear gerbil meerkat bear gerbil]
cmd> reverse
l = [gerbil bear meerkat gerbil bear]
cmd> size
Queue size = 5
l = [gerbil bear meerkat gerbil bear]
cmd> sort
l = [bear bear gerbil gerbil meerkat]
cmd> it fish
l = [bear bear gerbil gerbil meerkat fish]
cmd> swap
l = [bear bear gerbil gerbil fish meerkat]
cmd> reverse
l = [meerkat fish gerbil gerbil bear bear]
cmd> rh meerkat
Removed meerkat from queue
l = [fish gerbil gerbil bear bear]
cmd> rh fish
Removed fish from queue
l = [gerbil gerbil bear bear]
cmd> rh gerbil
Removed gerbil from queue
l = [gerbil bear bear]
cmd> rh gerbil
Removed gerbil from queue
l = [bear bear]
cmd> rh bear
Removed bear from queue
l = [bear]
cmd> rh bear
Removed bear from queue
l = []
cmd> size
Queue size = 0
l = []
cmd> free
l = NULL
Freeing queue
```
:::
該情形下並未產生錯誤，查看 git log 時發現是 commit #d39497 中修復了在讀取檔案作為輸入時不必要的初始化了 linenoise 相關功能。
```diff
- /* Trigger call back function(auto completion) */
- linenoiseSetCompletionCallback(completion);
+ /* Initialize linenoise only when infile_name not exist */
+ if (!infile_name) {
+ /* Trigger call back function(auto completion) */
+ linenoiseSetCompletionCallback(completion);
+
+ linenoiseHistorySetMaxLen(HISTORY_LEN);
+ linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
+ }
- linenoiseHistorySetMaxLen(HISTORY_LEN);
- linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
```
run_console():
```c
if (!has_infile) {
char *cmdline;
extern int connfd;
while ((cmdline = linenoise(prompt)) != NULL) {
interpret_cmd(cmdline);
linenoiseHistoryAdd(cmdline); /* Add to the history. */
linenoiseHistorySave(HISTORY_FILE); /* Save the history on disk. */
linenoiseFree(cmdline);
if (connfd) {
close(connfd);
connfd = 0;
}
}
} else {
while (!cmd_done())
cmd_select(0, NULL, NULL, NULL, NULL);
}
```
未修正前由於 `run_console()` 會進入下方 cmd_select() 的部份，並不會執行到 `linenoiseFree()` 因此導致 linenoise 初始化讀入的 history 未被釋放。
另外，在該 commit 也修正了當命令執行失敗時應先執行 `finish_cmd()` 釋放佇列所佔用的記憶體。(原先若 `ok == false` 就不會再執行 `finish_cmd()`)
```diff
- ok = ok && finish_cmd();
+
+ /* Do finish_cmd() before check whether ok is true or false */
+ ok = finish_cmd() && ok;
```
- 使用 valgrind 測試當 `qtest` 以 `<` 導入 `trace-xx-ops.cmd` 中命令的情形
```c
$ valgrind -q --leak-check=full ./qtest < traces/trace-01-ops.cmd
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
Removed dolphin from queue
l = [bear gerbil]
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
Freeing queue
==20927== 51 bytes in 9 blocks are still reachable in loss record 1 of 3
==20927== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==20927== by 0x4A5250E: strdup (strdup.c:42)
==20927== by 0x112791: linenoiseHistoryAdd (linenoise.c:1269)
==20927== by 0x113565: linenoiseHistoryLoad (linenoise.c:1358)
==20927== by 0x10E425: main (qtest.c:1382)
==20927==
==20927== 131 bytes in 11 blocks are still reachable in loss record 2 of 3
==20927== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==20927== by 0x4A5250E: strdup (strdup.c:42)
==20927== by 0x112791: linenoiseHistoryAdd (linenoise.c:1269)
==20927== by 0x1100E3: run_console (console.c:652)
==20927== by 0x10E3CA: main (qtest.c:1395)
==20927==
==20927== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==20927== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==20927== by 0x1127DD: linenoiseHistoryAdd (linenoise.c:1257)
==20927== by 0x113565: linenoiseHistoryLoad (linenoise.c:1358)
==20927== by 0x10E425: main (qtest.c:1382)
==20927==
```
由於不是以 -f 方式輸入檔名，而是 `<` 重新導向的方式讀入命令，因此前述關於讀檔時 `linenoise` 不做初始化的修改便失去效用了，參考 [freshLiver 的開發紀錄](https://hackmd.io/@freshLiver/2022q1-hw1#%E4%BD%BF%E7%94%A8-Valgrind-%E5%B0%8D-qtest-%E9%80%B2%E8%A1%8C%E5%88%86%E6%9E%90)以 `<` 重新導向會讓 linenoise 進入 linenoiseNoTTY 函式而其中並未與 `enableRawMode()` 中一樣指定在程式離開時要執行的函式。
```c
// Register a function to be called when `exit' is called
if (!atexit_registered) {
atexit(freeHistory); // free history at exit
atexit_registered = 1;
}
```
修正後重新測試，valgrind 不再回報錯誤:
```c
$ make
CC linenoise.o
LD qtest
$ valgrind -q --leak-check=full ./qtest < traces/trace-01-ops.cmd
l = []
l = [gerbil]
l = [bear gerbil]
l = [dolphin bear gerbil]
Removed dolphin from queue
l = [bear gerbil]
Removed bear from queue
l = [gerbil]
Removed gerbil from queue
l = []
Freeing queue
```
Sign in with Wallet
Connect another wallet