# 2022q1 Homework1 (lab0)
contributed by < [Eric-liau](https://github.com/Eric-liau) >

## 實驗環境

$ 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。

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)`。

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` 中

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` 中

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` 移除

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` 移除

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
未做更動

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

### q_size
整個 list 走過一遍即可算出 size

int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;
    list_for_each (li, head)
        len++;

    return len;
}

### q_delete_mid
利用快慢指標找到中間的 node

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` 全部刪除。

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 每兩個依序前後交換

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` 進行交換

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 上的仍無法通過。

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` 。
- 再次上傳後成功通過效能測試

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]` 。

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

- 修改後的程式碼

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)` 巨集定義。

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

4. 在 `list_sort.c` 中新增 `listcmp()` 函式。

    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`

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

- 於終端機輸入 `$ cppcheck --inline-suppr list_sort.c`

6. 修改 `qtest.c` ，新增一個 option 以便於在 `list_sort` 及自己實作的排序法間做切換。
- 加入 option

        ...
        static int listsort = 0;
        ...
        static void console_init()
        {
        ...
            add_param("listsort", &listsort, "Use list_sort or not", NULL);
        }

- 修改 `do_sort()` 函式

        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]

實作之程式碼如下：

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()` 需要進行修改，這部份稍後再提

#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`

bool noise;
int listenfd;

修改 `linenoiseEdit()` ，在 `while(1)` 裡加入以下程式碼

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`

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 端輸入的處理

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` 的命令格式

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` 開啟後從使用者端輸入指令會重複印出的情形

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

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()` 中完成。

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 。