# 2023q1 Homework1 (lab0)
contributed by < [`yanjiew1`](https://github.com/yanjiew1) >

> [GitHub](https://github.com/yanjiew1/lab0-c)

## 開發與實驗環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         3400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00

## 進度記錄

以下複製自「作業要求」

- [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] 研讀 Linux 核心 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 原始程式碼的並引入自己的專案
* [x] 比較效能落差
- [ ] 確保 `qtest` 提供的 `web` 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 `linenoise` 套件就無法使用，請提出改善機制
- [x] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」
- [x] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10` 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 `qtest` 切換不同的 PRNG 的實作 (可選定 [Xorshift](https://en.wikipedia.org/wiki/Xorshift))，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質
- [ ] 研讀論文〈[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) 及程式實作的原理。
* [x] 注意：現有實作存在若干致命缺陷，請討論並提出解決方案
* [ ] 解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution)
* 在 [oreparaz/dudect](https://github.com/oreparaz/dudect) 的程式碼具備 percentile 的處理，但在 [lab0-c](https://github.com/sysprog21/lab0-c) 則無。
- [ ] 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2023-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* [ ] 詳閱第 1 週所有教材及作業描述 [(一)](/@sysprog/linux2023-lab0-a), [(二)](/@sysprog/linux2023-lab0-b), [(三)](/@sysprog/linux2023-lab0-c), [(四)](/@sysprog/linux2023-lab0-d), [(五)](/@sysprog/linux2023-lab0-e)，記錄你的啟發和疑惑
* [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](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/H1TtmVTTz)

## 改進 `queue.c`

### `q_new`

透過 `malloc` 來配置記憶體，使用 `list.h` 裡面提供的 `INIT_LIST_HEAD` 來初始化 `struct list_head` 。
> commit [0f09bf6](https://github.com/yanjiew1/lab0-c/commit/0f09bf6ab87795c13f8aae2e6f773e48ce41eb0a)

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    if (!new)
        return NULL;

    INIT_LIST_HEAD(new);

    return new;
}

### `q_free`

使用 `list.h` 內提供的 `list_for_each_entry_safe` 來走訪每一個節點。使用的過程中，`safe` 會存放下一個節點，而 `it` 節點可以從 linked list 移除，不影響 `list_for_each_entry_safe` 運作。故在這裡，可以直接在走訪的過程中釋放每一個節點。最後再呼叫 `free` 釋放鏈結串列所配置的記憶體空間。。

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    if (!l)
        return;

    element_t *safe, *it;
    list_for_each_entry_safe (it, safe, l, list)
        q_release_element(it);

    free(l);
}

#### 開發過程記錄

一開始程式碼如下：

/* Free all storage used by queue */
void q_free(struct list_head *l)
{
    struct list_head *safe;
    struct list_head *it;

    list_for_each_safe (it, safe, l) {
        list_del(it);
        free(it);
    }

    free(l);
}

隨後很快發現，應該要釋放 `element_t` 才對，因為 `struct list_head` 是包含在 `element_t` 裡面的一個成員。於是變更如下：

@@ -5,8 +5,10 @@ void q_free(struct list_head *l)
     struct list_head *it;
 
     list_for_each_safe (it, safe, l) {
+        element_t *elem = list_entry(it, element_t, list);
         list_del(it);
-        free(it);
+        free(elem->value);
+        free(elem);
     }
 
     free(l);

但因為釋放 `element_t` 很常被用到，所以後來我寫一個獨立函式 `q_free_elem` 來做。最後又發現 `queue.h` 有提供 `q_release_element` ，最後改成用 `q_release_element` ，修改如下：

@@ -1,14 +1,12 @@
 /* Free all storage used by queue */
 void q_free(struct list_head *l)
 {
-    struct list_head *safe;
-    struct list_head *it;
+    element_t *safe;
+    element_t *it;
 
-    list_for_each_safe (it, safe, l) {
-        element_t *elem = list_entry(it, element_t, list);
-        list_del(it);
-        free(elem->value);
-        free(elem);
+    list_for_each_entry_safe (it, safe, l, list) {
+        list_del(&it->list);
+        q_release_element(it);
     }
 
     free(l);

後來又仔細研究 `list_for_each_entry_safe` 巨集後，發現 `list_del` 可以不用做。此巨集的特性是我們可以把 `it` 直接釋放，只要不要動到 `safe` ，就可以安全操作。最後變更如下：

@@ -1,13 +1,12 @@
 /* Free all storage used by queue */
 void q_free(struct list_head *l)
 {
-    element_t *safe;
-    element_t *it;
+    if (!l)
+        return;
 
-    list_for_each_entry_safe (it, safe, l, list) {
-        list_del(&it->list);
+    element_t *safe, *it;
+    list_for_each_entry_safe (it, safe, l, list)
         q_release_element(it);
-    }
 
     free(l);
 }

### `q_new_elem`

配合 `q_insert_head` 和 `q_insert_tail` 要新增元素，新增此函式，用來建立 `element_t` 。

使用 `malloc` 來配置記憶體空間。使用 `strdup` 來配置字串空間並拷貝字串。過程中如果配置失敗，則回傳 `NULL` 。
> commit [1e56bd7](https://github.com/yanjiew1/lab0-c/commit/1e56bd7b5c02c5dcc2710b7ba90f3ccd294814c9)

/* Create a new element with the provided string */
static inline element_t *q_new_elem(char *s)
{
    element_t *elem = malloc(sizeof(element_t));
    if (!elem)
        return NULL;

    char *tmp = strdup(s);
    if (!tmp) {
        free(elem);
        return NULL;
    }

    elem->value = tmp;
    return elem;
}

### `q_insert_head` 和 `q_insert_tail`

一開始要檢查 `head` 是否為 `NULL` ，若為 `NULL` 則不進行任何操作。

使用前面建立的 `q_new_elem` 來建立 `element_t` 。並且透過 `list_add` 或 `list_add_tail` 來把節點串上去。 若過程中失敗則回傳 `false` 。

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *elem = q_new_elem(s);
    if (!elem)
        return false;

    list_add(&elem->list, head);

    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *elem = q_new_elem(s);
    if (!elem)
        return false;

    list_add_tail(&elem->list, head);

    return true;
}

### `q_copy_string`

在 `q_remove_head` 和 `q_remove_tail` 需要複製字串，且 buffer 的大小是有限制的。C 標準函式庫提供的 `strcpy` 無法滿足此需求，故在此實作另一個函式 `q_copy_string` 來完成字串拷貝。

static inline void q_copy_string(char *dest, size_t size, const char *src)
{
    size_t i;
    for (i = 0; i < size - 1 && src[i] != '\0'; i++)
        dest[i] = src[i];

    dest[i] = '\0';
}

:::warning
此函式是否必要？其通用的程度如何？
:notes: jserv
> 謝謝老師，已改用 `strncpy` 來處理
> Commit [5b8c553](https://github.com/yanjiew1/lab0-c/commit/5b8c5537b832e02c045c65deba88578993999dad)
:::

### `q_remove_head` 和 `q_remove_tail`

這裡實作從佇列中移走開頭或尾端。

利用 `list_first_entry` 和 `list_last_entry` 來取得要移除的元素。使用 `list_del` 來移除元素。題目要求要把移除元素的字串值拷貝到 `sp` 這個 buffer ，並且 buffer 大小為 `bufsize` ，就透過前面實作的 `q_copy_string` 來做。

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *elem = list_first_entry(head, element_t, list);
    list_del(&elem->list);

    if (sp && bufsize)
        q_copy_string(sp, bufsize, elem->value);

    return elem;
}

<s>`q_remove_tail` 程式碼相似，就不佔用版面了。</s>
:::warning
正因程式碼相似度高，你更該思索如何簡化程式碼，從而降低維護的程式碼。
:notes: jserv
> 已讓 `q_remove_tail` 和 `q_insert_tail` 重用 `q_remove_head` 和 `q_insert_head` 程式碼。謝謝老師
> Commit [bc97533](https://github.com/yanjiew1/lab0-c/commit/bc97533e3e2726eca6cf822d3e7550ca38792fca)
:::

### `q_size`

實作很簡單：直接使用 `list.h` 提供的 `list_for_each` 來走訪每一個節點。每走訪一個節點就遞增 `count` 變數，最後再回傳 `count` 變數的值即為所求。

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int count = 0;
    struct list_head *it;

    list_for_each (it, head)
        count++;

    return count;
}

### `q_delete_mid`

這裡充份利用雙向鏈結串列的特性，從頭尾開始走訪節點，直到二個指標碰面時，即取得中間的節點。最後再把中間節點所代表的元素刪除。

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *left = head->next;
    struct list_head *right = head->prev;

    while (left != right && left->next != right) {
        left = left->next;
        right = right->prev;
    }

    list_del(right);
    element_t *elem = list_entry(right, element_t, list);
    q_release_element(elem);

    return true;
}

### `q_delete_dup`

我的作法是先宣告 `cut` 變數，其內容固定存放「目前走訪元素往前看，第一個其元素值與目前元素不同的元素」。

此外另外宣告一個 ~~`trash`~~ `pending` 作為暫時放置待移除元素的地方，要移除的元素都會先放在這裡，最後再一起清掉。
:::warning
"trash" 命名不精準，可用 pending list 一類的詞彙。
:notes: jserv
> 已修改。 Commit [a725fcc](https://github.com/yanjiew1/lab0-c/commit/a725fcc2c8b58c9e8d661ff15c978e79552d4fda)
:::

在走訪元素的過程中， ~~`&safe->list != head && strcmp(safe->value, it->value) == 0`~~ `&safe->list != head && !strcmp(safe->value, it->value)` 會去判斷下一個元素跟目前元素的值是否相同。若相同時，就繼續走訪，直到遇到下個元素 `safe` 與目前元素 `it` 值不同時，再來進行接下來操作，如下：

當下個元素 `safe` 與目前元素 `it` 不同時，會先去檢查 `cut` 變數，是不是指向前一個元素。若是指向前一個元素，代表目前元素跟前一個元素不同，則不用處置，因為目前元素 `it` 跟前一個元素沒有重複；若 `cut` 不是指向前一個元素，則代表 `cut` 指向更之前的元素，且 $(cut, it]$ 元素其值均相同，故把 $(cut, it]$ 元素全部~~丟到 `trash`~~ 放到 `pending` 中。

迴圈最後 `cut = safe->list.prev;` 這敘述，因為目前元素 `it` 與下一個元素值 `safe` 不同 (若相同就不會執行到此，故更新 `cut` 為目前元素後，再進行下個迴圈。

迴圈結束 `q_delete_dup` 要返回前。要清除 ~~`trash`~~ `pending` 裡的~~垃圾~~元素。用 `list_for_each_entry_safe` 來走訪每一個 ~~`trash`~~ `pending` 中的元素，並用 `q_release_element` 來刪除它。

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;

    LIST_HEAD(pending);
    element_t *it, *safe;
    struct list_head *cut = head;

    list_for_each_entry_safe (it, safe, head, list) {
        if (&safe->list != head && !strcmp(safe->value, it->value))
            continue;
        /* Detect duplicated elements */
        if (it->list.prev != cut) {
            LIST_HEAD(tmp);
            list_cut_position(&tmp, cut, &it->list);
            list_splice(&tmp, &pending);
        }
        cut = safe->list.prev;
    }

    /* Process pending list */
    list_for_each_entry_safe (it, safe, &pending, list)
        q_release_element(it);

    return true;
}

:::warning
將 `strcmp(safe->value, it->value) == 0` 改為 `!strcmp(safe->value, it->value)` 可縮減程式碼。
:notes: jserv
> 已修改 Commit [bd9253a](https://github.com/yanjiew1/lab0-c/commit/bd9253aa92b0673b3805ae815fd0dc72332e5f59)
:::

### `q_reverse`

這裡的實作很簡單，就是用 `list_for_each_safe` 走訪每一個節點。走訪過程中，用 `list_move` 把每一個節點移到開頭，這樣子順序就反過來了。 `list_for_each_safe` 允許對目前走訪的節點移動位置。因為是往前移到開頭，故不會因為節點移動而改變走訪次序或是重複走訪。

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *it, *safe;
    /* Iterate the list and move each item to the head */
    list_for_each_safe (it, safe, head)
        list_move(it, head);
}

#### 變更記錄

把 `list_for_each_safe` 大括號拿掉，按照 Coding Style ，這裡不用放大括號。

diff --git a/queue.c b/queue.c
diff --git a/queue.c b/queue.c
     struct list_head *it, *safe;
     /* Iterate the list and move each item to the head */
-    list_for_each_safe (it, safe, head) {
+    list_for_each_safe (it, safe, head)
         list_move(it, head);
-    }
 }

### `q_reverseK`

使用 `count` 來記錄已走訪幾個節點，一開始把 `count` 設為 `k` ，每走訪一個節點就把 `count` 減去 1 。當走訪 `k` 個節點時 (`--count` 變成 0)，就會把 `cut` 記錄的切點到目前走訪的節點(不包含 `cut` 但包含 `it`，即 `(cut, it]`)切下，放到 `tmp` 上，再重用前面實作好的 `q_reverse` ，對 `tmp` 做反轉，再用 `list_splice` 把 `tmp` 接回來。

最後設定 `safe->prev` 為新的 `cut` 。這裡不能用 `it` 是因為 `it` 已在反轉的過程中移動位置了。

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_empty(head))
        return;
    struct list_head *it, *safe, *cut;
    int count = k;
    cut = head;
    list_for_each_safe (it, safe, head) {
        if (--count)
            continue;
        LIST_HEAD(tmp);
        count = k;
        list_cut_position(&tmp, cut, it);
        q_reverse(&tmp);
        list_splice(&tmp, cut);
        cut = safe->prev;
    }
}

:::warning
追加 `list_empty()` 的檢查。
:notes: jserv
> 已修正
> Commit [b536d66](https://github.com/yanjiew1/lab0-c/commit/b536d66e3dbdab1503169324b5247b7b541bb2f7)
:::

### `q_swap`

`swap` 就是二個二個一組進行 `reverse` ，故直接重用 `q_reverseK` 的程式 。

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    q_reverseK(head, 2);
}

### `q_merge_two`

因為 `q_sort` 和 `q_merge` 都會需要合併二個串列。故新增一個 `q_merge_two` 用來合併二個串列。參考 `alanjian85` 同學的實作。合併的方式是每次從輸入的二個串列中，取較小的，放到一個暫存串列中 `tmp` ，之後再把串列接回 `first` 。

static int q_merge_two(struct list_head *first, struct list_head *second)
{
    if (!first || !second)
        return 0;

    int count = 0;
    LIST_HEAD(tmp);
    while (!list_empty(first) && !list_empty(second)) {
        element_t *f = list_first_entry(first, element_t, list);
        element_t *s = list_first_entry(second, element_t, list);
        if (strcmp(f->value, s->value) <= 0)
            list_move_tail(&f->list, &tmp);
        else
            list_move_tail(&s->list, &tmp);
        count++;
    }
    count += q_size(first) + q_size(second);
    list_splice(&tmp, first);
    list_splice_tail_init(second, first);

    return count;
}

### `q_sort`

採用 merge sort 遞迴演算法。一開始運用雙向鏈結串列的特性，從頭尾開始往中間找到中間節點，找到後，把 (`head`, `mid`] 留在 `head` 並把 (`mid`, `head`) 切下來加到 `second` 中。再針對 `head` 、 `second` 分別遞迴呼叫 `q_sort` ，對子串列進行排序。最後再把排序好的 `head` 和 `second` 透過 `q_merge_two` 合併。

/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    /* Try to use merge sort*/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    /* Find middle point */
    struct list_head *mid, *left, *right;
    left = right = head;
    do {
        left = left->next;
        right = right->prev;
    } while (left != right && left->next != right);
    mid = left;

    /* Divide into two part */
    LIST_HEAD(second);
    list_cut_position(&second, mid, head->prev);

    /* Conquer */
    q_sort(head);
    q_sort(&second);

    /* Merge */
    q_merge_two(head, &second);
}

:::warning
若要改為迭代的實作，你預計怎麼做？
:notes: jserv
> 在還沒看到 Linux kernel 排序演算法前，我會傳統資料結構教科書內 bottom-up 方式實作。看到 Linux 排序演算法後，很明顯發現它比傳統教科書方式聰明。之後我會研究 Python 內的 Timsort 來實作。把 Timsort 實作出來後，新增一個 `sort` option ，來切換排序演算法。
:::

#### 更新記錄

原本串列合併的程式直接寫在 `q_sort` 裡，後來把它移到獨立的函式中。
> Commit [09de13c](https://github.com/yanjiew1/lab0-c/commit/09de13c7234b40731030f571198ffeab7a06a999)

### `q_descend`

我的想法就是從尾到頭掃過一次。在掃的過程中，會判斷下一個節點(`prev`)是否小於~~等於~~目前節點(`cur`)，若是就把下一個節點(`prev`)刪除再重複迴圈，直到下一個節點是大於目前節點時，才會把 `cur` 移動到下一個節點，並且 `cnt` (計數器) 加 1 。

目前 `lab0-c` 內建的 `list.h` 標頭檔和 Linux 核心原始程式碼 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 存在一些差距，後者的 `list_for_each_prev` 巨集不在前者出現。若有它則可以用它來實作。

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    /**
     * Traverse from the last entry and remove the element that is
     * smaller or equal to its right. Also count the number of elements.
     */
    int cnt = 1;
    element_t *cur = list_last_entry(head, element_t, list);
    while (cur->list.prev != head) {
        element_t *prev = list_last_entry(&cur->list, element_t, list);
        if (strcmp(prev->value, cur->value) < 0) {
            list_del(&prev->list);
            q_release_element(prev);
        } else {
            cnt++;
            cur = prev;
        }
    }

    return cnt;
}

:::warning
針對呼叫 `strcmp` 的那行敘述，若搭配使用 `break` 或 `continue` 關鍵字，可進一步縮減程式碼。
:notes: jserv
:::

### `q_merge`

採用 [Strategies for Stable Merge Sorting](https://arxiv.org/pdf/1801.04641.pdf) 這篇論文中的 2-merge 演算法來實作。用此演算法，使合併二個 queue 時，其二個 queue 元素數量差距不要太大。

其運作原理是這樣：
1. pending list 為一類似 stack 的結構，意即先加入它的 queue 會在後面才取出來。
2. 每次迴圈加入 1 個 queue 進入 pending list ，直到沒有未加入 pending list 的 queue。
若 pending list 個數大於 3 個時，判斷是否合併：
- 從 pending list 依序取出 `x`, `y`, `z` 。 若 `|y| < 2|x|` 則按下步驟進行合併，若否，則繼續進行 2. 迴圈
- 若 `|x| < |z|` 則將 `x` 和 `y` 合併，否則 `y` 和 `z` 合併
- 合併後需要再重新取出 `x` 、 `y` 、 `z` ，判斷是否符合需要合併的條件
4. 把 pending list 中未合併的 queue 進行合併。

/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;

    if (list_is_singular(head))
        return list_first_entry(head, queue_contex_t, chain)->size;

    /* Use 2-merge algorithm in https://arxiv.org/pdf/1801.04641.pdf */
    LIST_HEAD(pending);
    LIST_HEAD(empty);
    int n = 0;
    while (!list_empty(head)) {
        list_move(head->next, &pending);
        n++;

        while (n > 3) {
            queue_contex_t *x, *y, *z;
            x = list_first_entry(&pending, queue_contex_t, chain);
            y = list_first_entry(&x->chain, queue_contex_t, chain);
            z = list_first_entry(&x->chain, queue_contex_t, chain);

            if (y->size >= z->size << 1)
                break;

            if (x->size < z->size) {
                y->size = q_merge_two(y->q, x->q);
                list_move(&x->chain, &empty);
                n--;
            } else {
                z->size = q_merge_two(z->q, y->q);
                list_move(&y->chain, &empty);
                n--;
            }
        }
    }

    /* Merge remaining list */
    while (n > 1) {
        queue_contex_t *x, *y;
        x = list_first_entry(&pending, queue_contex_t, chain);
        y = list_first_entry(&x->chain, queue_contex_t, chain);
        y->size = q_merge_two(y->q, x->q);
        list_move(&x->chain, &empty);
        n--;
    }

    /* Move the last queue and empty queue to head */
    list_splice(&empty, head);
    list_splice(&pending, head);

    return list_first_entry(head, queue_contex_t, chain)->size;
}

#### 更新記錄

原本是這重用前面實作的 `q_sort` 。我把所有鏈結串列接在一起，然後呼叫 `q_sort` 排序好，放回第一個串列。後來變更實作，改成直接進行合併，並且合併時，透過一些策略降低二個 queue 要合併時的長度差異。

> Commit [f6568be](https://github.com/yanjiew1/lab0-c/commit/f6568bed251b77837fa0ab2b87ff2642adef718b)

### `q_ascend`

這是後來 `lab-0` 加上的函式，跟 `q_descend` 很像。故把 `q_descend` 的程式複製一份來用，把中間的 `<` 改為 `>` 即可。

int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    /**
     * Traverse from the last entry and remove the element that is
     * smaller or equal to its right. Also count the number of elements.
     */
    int cnt = 1;
    element_t *cur = list_last_entry(head, element_t, list);
    while (cur->list.prev != head) {
        element_t *prev = list_last_entry(&cur->list, element_t, list);
        if (strcmp(prev->value, cur->value) > 0) {
            list_del(&prev->list);
            q_release_element(prev);
        } else {
            cnt++;
            cur = prev;
        }
    }

    return cnt;
}

---

## Valgrind 與 Address Sanitizer 記憶體檢查

### Makefile 中關於 `make valgrind` 的內容分析

valgrind: valgrind_existence
	# Explicitly disable sanitizer(s)
	$(MAKE) clean SANITIZER=0 qtest
	$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
	cp qtest $(patched_file)
	chmod u+x $(patched_file)
	sed -i "s/alarm/isnan/g" $(patched_file)
	scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
	@echo
	@echo "Test with specific case by running command:" 
	@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"

裡面看到很神奇的部份，就是在用 Valgrind 執行時，會把 `qtest` 執行檔中，所有 `alarm` 改為 `isnan` 。我的猜測是因為 Valgrind 會使程式執行速度變慢，導致一些操作會超過時間限制。我把這行拿掉 `sed -i "s/alarm/isnan/g" $(patched_file)` ，執行 `make valgrind` ，果然就出現超時訊息。查詢 C 標準函式庫可知，[isnan(3p)](https://man7.org/linux/man-pages/man3/isnan.3p.html) 是用來檢查傳入的浮點數是否為 NaN ，會選用這個函數來取代 `alarm` ，估計是因為它跟 `alarm` 一樣函式名稱都是 5 個字元，此外 `isnan` 沒有任何 side effects ，故剛好可以拿來用。為了測試，我嘗試把 `isnan` 替換成 `asinf` 看看能不能運作。實測的結果如預期，可以正常運作。

### 使用 Valgrind

執行 `make valgrind` ，產生了很多 Memory leak 的訊息。以下為節錄的訊息：

+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==30743== 32 bytes in 1 blocks are still reachable in loss record 1 of 2
==30743==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==30743==    by 0x10CBE6: do_new (qtest.c:146)
==30743==    by 0x10DE12: interpret_cmda (console.c:181)
==30743==    by 0x10E3C7: interpret_cmd (console.c:201)
==30743==    by 0x10E7C8: cmd_select (console.c:610)
==30743==    by 0x10F0B4: run_console (console.c:705)
==30743==    by 0x10D204: main (qtest.c:1228)
==30743== 

我先用 `valgrind ./qtest` 的方式測試，發現只要在結束前沒有把所有的 queue 釋放，就會產生上述訊息。後來發現在 `q_quit` 裡面，在第一行是 `return true;` 使下面釋放記憶體的程式沒辦法執行。把這行拿掉後就正常了。

--- a/qtest.c
+++ b/qtest.c
@@ -1059,7 +1059,6 @@ static void q_init()
 
 static bool q_quit(int argc, char *argv[])
 {
-    return true;
     report(3, "Freeing queue");
     if (current && current->size > BIG_LIST_SIZE)
         set_cautious_mode(false);

但若是使用 `valgrind ./qtest < traces/trace-01-ops.cmd` 的方式來執行，仍然會出現下面訊息：

==33817== 130 bytes in 10 blocks are still reachable in loss record 1 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x49FE60E: strdup (strdup.c:42)
==33817==    by 0x1121B9: line_history_add (linenoise.c:1275)
==33817==    by 0x113014: line_hostory_load (linenoise.c:1360)
==33817==    by 0x10D332: main (qtest.c:1215)
==33817== 
==33817== 130 bytes in 10 blocks are still reachable in loss record 2 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x49FE60E: strdup (strdup.c:42)
==33817==    by 0x1121B9: line_history_add (linenoise.c:1275)
==33817==    by 0x10F10C: run_console (console.c:692)
==33817==    by 0x10D2D7: main (qtest.c:1227)
==33817== 
==33817== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==33817==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==33817==    by 0x112205: line_history_add (linenoise.c:1263)
==33817==    by 0x113014: line_hostory_load (linenoise.c:1360)
==33817==    by 0x10D332: main (qtest.c:1215)
==33817== 

從上述訊息可以看出是 linenoise 中處理 history 的部份出錯。分析了一下 linenoise.c 的程式碼，發現 `line_atexit` 只會在 `enable_raw_mode` 函式裡被註冊為 atexit function ，但是在 stdin 不為 tty 的情況下 `enable_raw_mode` 不會被呼叫到。故把註冊 `line_atexit` 的程式移到 `linenoise` function 就解決了。

--- a/linenoise.c
+++ b/linenoise.c
@@ -243,10 +243,6 @@ static int enable_raw_mode(int fd)
 {
     if (!isatty(STDIN_FILENO))
         goto fatal;
-    if (!atexit_registered) {
-        atexit(line_atexit);
-        atexit_registered = true;
-    }
     if (tcgetattr(fd, &orig_termios) == -1)
         goto fatal;
 
@@ -1189,6 +1185,11 @@ char *linenoise(const char *prompt)
 {
     char buf[LINENOISE_MAX_LINE];
 
+    if (!atexit_registered) {
+        atexit(line_atexit);
+        atexit_registered = true;
+    }
+
     if (!isatty(STDIN_FILENO)) {
         /* Not a tty: read from file / pipe. In this mode we don't want any
          * limit to the line size, so we call a function to handle that. */

至此，所有 `make valgrind` 會產生的記憶體問題都解決了。

### 使用 address sanitizer

重新編譯有開啟 address sanitizer 的版本。

make clean
make SANITIZER=1

之後執行 `make test` ，沒有出現任何記憶體相關錯誤訊息。至此檢查通過。

---

## 加入 option `descend`

`lab-0` 在 Commit [0fcefb0](https://github.com/sysprog21/lab0-c/commit/0fcefb0b3da3a4a33cad00e7e68248ab909e348a) 加入了 `descend` option ，故把上游版本 `sysprog21/lab0-c` 合併進來時，也需要一併實作 option `descend` 。

### 修改 `q_merge_two`

因為 `q_sort` 和 `q_merge` 都會用到 `q_merge_two` 來合併二個串列。故在 `q_merge_two` 實作合併時，由大到小排序。其中迴圈內在選擇要哪一個元素放到合併後的串列時，做了些更動，如下：

         element_t *f = list_first_entry(first, element_t, list);
         element_t *s = list_first_entry(second, element_t, list);
-        if (strcmp(f->value, s->value) <= 0)
+        int cmp = strcmp(f->value, s->value);
+        if (descend)
+            cmp = -cmp;
+        if (cmp <= 0)
             list_move_tail(&f->list, &tmp);
         else
             list_move_tail(&s->list, &tmp);

而 `q_merge_two` 函式宣告改為：

static int q_merge_two(struct list_head *first,
                       struct list_head *second,
                       bool descend)

針對 `descend` 為 `true` 的清況，正負號反轉，即可實現大到小排序，且也維持 `q_sort` 和 `q_merge` 的穩定排序特性。

### 修改 `q_sort` 和 `q_merge`

而 `q_sort` 和 `q_merge` 則是修改成：呼叫 `q_merge_two` 時會多傳入 `descend` 參數，來決定是否要由大到小排序。

### 修改 `q_ksort`

`q_ksort` 是使用 Linux 核心的 `list_sort` 排序演算法。`list_sort` 會傳入比較函式 `cmp` 作為參數。故我實作一個比較函式 `q_cmp_descend` ，它會呼叫原本的比較函式 `q_cmp` ，但正負號相反，如下：

static int q_cmp_descend(void *priv,
                         const struct list_head *a,
                         const struct list_head *b)
{
    return -q_cmp(priv, a, b);
}

再把 `q_ksort` 改成判斷 `descend` 是否為 `true` ，再選擇適當的比較函式。

void q_ksort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    list_cmp_func_t cmp = descend ? q_cmp_descend : q_cmp;

    list_sort(NULL, head, cmp);
}

---

## Linux 核心 Linked List 排序研究

### 整合 Linux 核心的 `list_sort`

將 Linux 核心原始程式碼的 `list_sort.c` 和 `list_sort.h` 複製到 `lab0-c` 專案中，進行些許修改讓它可以成功在這個專案中編譯。主要是把 `u8` 改為 `uint8_t` (並加入 `stdint.h`) 、移除不必要的 `#include` 。之後修改 `Makefile` 加入 `list_sort.o` 後，確認用 `make` 命令可以正常編譯。

接下來是額外撰寫一份用 Linux kernel 排序的程式。因為 `queue.h` 不能更動，我決定把這個程式放在另一個檔案 `ksort.c` 並且有對應的標頭檔 `ksort.h` 。 此也在 `Makefile` 內加入 `ksort.o` 。

因為 Linux kernel 實作需傳入 `cmp` 比較函式作為比較大小用。我的實作如下：

static int q_cmp(void *priv,
                 const struct list_head *a,
                 const struct list_head *b)
{
    // cppcheck-suppress nullPointer
    element_t *elem_a = list_entry(a, element_t, list);
    // cppcheck-suppress nullPointer
    element_t *elem_b = list_entry(b, element_t, list);

    return strcmp(elem_a->value, elem_b->value);
}

我新增了一個 option `ksort` ，可以用來切換排序實作。在 `qtest.c` 按照原本定義 option 的格式新增下方程式在 `console_init` 中。此外也加入一個全域變數來記錄目前要使用的排序實作。
:::warning
未來或許會有多款排序的實作，設計選項時，應予以考慮，亦即你可用 `option sort 0` (預設), `option sort 1` (上述來自 Linux 核心原始程式碼的 `list_sort`), `option sort 2` (未來實作的排序程式碼) 來切換。
:notes: jserv
:::

static int use_ksort = 0;

add_param("ksort", &use_ksort,
          "Whether to use Linux kernel sorting algorithm", NULL);

### 效能分析

在開始分析效能前。看到 Linux 核心的 `list_sort` 是以 bottom-up 方式實作 merge sort 並且合併方式是用對 cache 較友善的方式。即 $3 \times 2^k$ 就合併，大概可以猜測 Linux 的排序實作效能會比較好。我用以下的命令序列來分析排序效能:

new
option ksort 1/0 <= 跟據要測試的排序實作進行切換
ih RAND 2000000
shuffle
time sort        <= 執行 10 次取平均， 中間以 shuffle 間隔

為了避免出現 Time out 的問題。開始測試前會先 patch ./qtest，即 `sed -i "s/alarm/isnan/g"`。

測試的結果如下表：

| 我的排序 | Linux Kernel 排序 |
| -------- | ----------------- |
| 2.8899 | 2.1537 |

可以看到我的 top-down 排序演算法花的時間是 Linux 核心 `list_sort` 實作的 1.341 倍。即比 Linux 排序演算法慢 34% 左右。

### Linux Kernel Linked List 排序演算法探索

Linux 核心是使用 bottom-up 的 merge sort ，但是它合併的方式跟傳統教科書不一樣。

:::info
**TODO** 補完此節
:::

---

## `web` 命令/網頁伺服器改善

:::info
TODO
:::

---

## 亂數研究及 shuffle 實作

### 程式實作

在作業說明裡面，每次抽到的數字後，都要從最前面開始往後數，這樣子會讓時間複雜度最壞情況至 $O(n^2)$ ，故我採取不同的策略。

我先建立一個存放所有節點的指標陣列，如下所示：

struct list_head **entries = malloc(sizeof(struct list_head *) * size);

:::warning
可變更為 `malloc(sizeof(*entries) * size)` 以縮減程式碼。
:notes: jserv
> 已修改。 Commit [92d98c6](https://github.com/yanjiew1/lab0-c/commit/92d98c6902dcc681297d2485141a51508100f6a3)
:::

把所有節點的位址放入陣列中：

int i = 0;
list_for_each (node, head)
    entries[i++] = node;

取得隨機數先直接使用 C 語言標準函式庫提供的 `rand` 函數取得隨機數。因為 `rand` 的範圍是 `[0, RAND_MAX]` ， `RAND_MAX` 不一定可以被候選數個數整除。故使用一個迴圈，丟棄任何會大於 `RAND_MAX - (RAND_MAX % k)` 的數值，使得取得的隨機數最大值可被候選數個數整除。讓每一個候選數被選中的機率是一樣的。以下是相關程式碼片段。這裡要取得 $[0, i]$ 之間的數。

int n;
do {
    n = rand();
} while (n >= RAND_MAX - (RAND_MAX % (i + 1)));
n %= i + 1;

:::warning
對照看 `random.[ch]` 程式碼。
:notes: jserv
:::

:::info
這樣的實作缺點是需要使用 `malloc` 來配置額外空間。無法做到空間複雜度 $O(1)$ 。目前還沒想到能在時間複雜度為 $O(n)$ 情況下，空間複雜度為 $O(1)$ 的方式。
:::

### Fisher–Yates shuffle 亂度分析

分析方式為建立一個 queue ， 並分別新增 a, b, c, d 至 queue 中。執行 shuffle 1000000 次，並統計每種排列方式出現的次數。

直接使用作業說明提供的程式來分析。把作業說明的 Python 程式複製到 `script/shuffle.py` ，並修改改用 a, b, c, d 來進行 shuffle 測試。

| 排列 | 出現次數 | 期待次數 | ${(O_i - E_i)^2 \over E_i}$ |
|------|----------|----------|-----------|
| abcd | 41451 | 41666.67 | 1.1162907 |
| abdc | 41827 | 41666.67 | 0.6169627 |
| acbd | 41722 | 41666.67 | 0.0734827 |
| acdb | 41524 | 41666.67 | 0.4884907 |
| adbc | 41707 | 41666.67 | 0.0390427 |
| adcb | 41439 | 41666.67 | 1.2439707 |
| bacd | 41937 | 41666.67 | 1.7539227 |
| badc | 41628 | 41666.67 | 0.0358827 |
| bcad | 42129 | 41666.67 | 5.1300507 |
| bcda | 41591 | 41666.67 | 0.1374107 |
| bdac | 41626 | 41666.67 | 0.0396907 |
| bdca | 41709 | 41666.67 | 0.0430107 |
| cabd | 41418 | 41666.67 | 1.4840427 |
| cadb | 41500 | 41666.67 | 0.6666667 |
| cbad | 41712 | 41666.67 | 0.0493227 |
| cbda | 41794 | 41666.67 | 0.3891307 |
| cdab | 41439 | 41666.67 | 1.2439707 |
| cdba | 42090 | 41666.67 | 4.3010667 |
| dabc | 41767 | 41666.67 | 0.2416027 |
| dacb | 41190 | 41666.67 | 5.4530667 |
| dbac | 41823 | 41666.67 | 0.5865627 |
| dbca | 41679 | 41666.67 | 0.0036507 |
| dcab | 41625 | 41666.67 | 0.0416667 |
| dcba | 41673 | 41666.67 | 0.0009627 |
| Total| | | 25.17992 |

使用[此線上工具](https://www.socscistatistics.com/pvalues/chidistribution.aspx)計算 P 值，計算出來為 **0.34** 左右，故無法拒絕 Fisher–Yates shuffle 不是 Uniform Distribution。

### Entropy 觀察

跟據作業要求，執行以下命令來觀察 entropy。

option entropy 1
new
it RAND 10

l = [haiowq(29.69%) wncthutns(32.81%) yhzrx(26.56%) dfjqntag(35.94%) whgushb(29.69%) ciahh(21.88%) oidgffg(26.56%) pmeqkxou(35.94%) xffww(17.19%) nrgavix(32.81%)]

大致上可以發現，在相同字串長度下，不重複的字母數愈多，其 entropy 愈高。例如： `ciahh(21.88%)`, `xffww(17.19%)` ，也就是代表其亂度愈高。

從 entropy 公式可以發現，若字串中每一個字母其出現機率愈一致（即字串愈亂)，且一字串所包含的不同字母數愈多 (即每個字母出現的機率一致)，其 entropy 愈高，符合作業說明所說的。

不過到這裡，我還是沒有完全理解 entropy 的意義，目前的理解是：它用來表達一個訊息內容有多亂。之後還要再研讀。

### 加入 Xoshiro256++ 亂數產生器並比較系統提供之亂數產生器

`qtest` 亂數產生器存放在 `random.c` ，可以看到此亂數產生器是直接使用 Linux 核心提供的亂數產生器。

我跟據作業提供的 Wikipedia Xorshift [參考連結](https://en.wikipedia.org/wiki/Xorshift)，並參考了相關的變形實作。我決定引進 Xoshiro256++ 來作為另一套亂數產生器。因為原本的 Xorshift 跟據維基百科說明，在統計上可能有些瑕疵。而其變種 Xoshiro256++ 在[作者官網](https://prng.di.unimi.it/)介紹中感覺看不出有瑕疵。
> Xorshift 是 [Linear-feedback shift register](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) (LFSR) 的子集合

作者在他的網站上[提供了 Xoshiro256++ 的程式碼](https://prng.di.unimi.it/xoshiro256plusplus.c)，故我就直接使用作者網站提供的程式碼，再做點修改。此外作者建議使用 SplitMix64 作為初始化 Xoshiro256++ 的內部狀態，同樣也在他的網站上[提供程式碼](https://prng.di.unimi.it/splitmix64.c)，我也直接把它拿來用。

把上述程式結合，再做點修改後，Xoshiro256++ 亂數產生器程式放在 [xoshiro.c 檔案](https://github.com/yanjiew1/lab0-c/blob/master/xoshiro.c)內。

另外再建立一個 [`qrandom.c` 檔案](https://github.com/yanjiew1/lab0-c/blob/master/qrandom.c)，這裡是亂數產生器的單一入口，會再透過全域變數 `qrandom_impl` 來決定要使用的亂數產生器。而 `qrandom_impl` 可用 `option random` 來控制。目前設定是 `qrandom_impl == 0` 時使用系統提供的亂數產生器， `qrandom_impl != 1` 時就用 Xoshiro256++。

此外，我在 `qtest.c` 內實作 `-r`　選項，可讓 `qtest` 直接使用內部的亂數產生器，產生隨機 raw bytes 並輸出到 stdout 。`-r 0` 為使用內建的亂數產生器，`-r 1` 為使用 xoshiro256++ ，搭配作業說明 `ent` 工具來評估亂數產生器的品質。

在 `main` 函式處理命令列選項的 switch-case 地方加入：

case 'r':
    char *endptr;
    errno = 0;
    qrandom_impl = strtol(optarg, &endptr, 10);
    if (errno != 0 || endptr == optarg) {
        fprintf(stderr, "Invalid random number generator\n");
        exit(EXIT_FAILURE);
    }
    generate_randombytes();
    break;

另外也新增一個函式 `generate_randombytes` ，來把亂數輸出到 stdout 。

#define RANDOM_BYTES 1048576
static void generate_randombytes(void)
{
    uint8_t *buf = malloc(RANDOM_BYTES);
    if (!buf)
        exit(1);

    do {
        qrandombytes(buf, RANDOM_BYTES);
    } while (fwrite(buf, RANDOM_BYTES, 1, stdout));

    exit(0);
}

#### `Xoshiro256++` 亂數品質測試

執行下面命令來測試亂數品質，可得到這個報告

./qtest -r 1 | head -c 10M | ent
Entropy = 7.999998 bits per byte

Optimum compression would reduce the size
of this 104857600 byte file by 0 percent.

Chi square distribution for 104857600 samples is 264.69, and randomly
would exceed this value 32.52 percent of the times.

Arithmetic mean value of data bytes is 127.4997 (127.5 = random).
Monte Carlo value for Pi is 3.142157713 (error 0.02 percent).
Serial correlation coefficient is 0.000097 (totally uncorrelated = 0.0).

卡方檢定的結果 p 值為 32.52% ，離 5% 遙遠，故此亂數產生器產生的亂數可能是 Uniform Distribution 的。

此外 entropy 值為 7.99998 bits per byte, 可說是相當高。

#### 系統內建亂數測試

$ ./qtest -r 0 | head -c 10M | ent
Entropy = 7.999983 bits per byte.

Optimum compression would reduce the size
of this 10485760 byte file by 0 percent.

Chi square distribution for 10485760 samples is 248.23, and randomly
would exceed this value 60.75 percent of the times.

Arithmetic mean value of data bytes is 127.4847 (127.5 = random).
Monte Carlo value for Pi is 3.141642434 (error 0.00 percent).
Serial correlation coefficient is -0.000522 (totally uncorrelated = 0.0).

卡方檢定的結果 p 值為 60.75% ，離 5% 遙遠，故此亂數產生器產生的亂數可能是 Uniform Distribution 的。

此外 entropy 值為 7.999983 bits per byte, 也是相當高。

故二種亂數產生器均能產生品質不錯的亂數。

原本想要用 `dieharder` 測試，但跑了很久都沒有結束，所以後來就先提供 `ent` 報告結果。

:::warning
你若對這主題感興趣，可對照閱讀 [Uniting the Linux random-number devices](https://lwn.net/Articles/884875/)，亂數產生器的品質，是近期 Linux 核心的重要開發方針之一。
:notes: jserv
:::

---

## 研讀論文〈Dude, is my code constant time?〉

> [論文](https://eprint.iacr.org/2016/1123.pdf)

### `dudect` 統計原理

`dudect` 會以二種不同類型的資料作為輸入，對待測的程式進行多次時間量測，並分別觀察二種資料作為輸入時其執行時間的分布，進行比較。這二種不同類型的資料分別是：
- 固定資料
- 隨機資料

若固定輸入資料與隨機輸入資料的時間分布有顯著差異，則可以證明待測的程式其執行時間不是常數時間。反之則其執行時間可能是常數時間 （即無法拒絕其為常數時間）

執行 `dudect` 分為三步驟：
1. 量測執行時間：對二種不同類型的資料進行多次量測。論文建議不要進行一類量測再進行另外一類，避免數值受環境干擾。建議的方式是：每次隨機任一類資料，進行執行時間量測。
2. 量測後的資料處理：
- Cropping 因為執行時，作業系統或硬體中斷都可能打斷正在執行中的程式，這會讓量測不準確。此外資料會偏向較長執行時間一方。故可以透過 Cropping 手法來裁剪執行時間較長的部份。
- Higher-order preprocessing ：尚未理解這部份
4. 進行統計分析：透過統計方法拒絕虛無假說「二種輸入類型執行時間分佈一致」。若成功拒絕此虛無假說，則可說明程式執行不是常數時間。論文中提到二種檢測方式，其中 `dudect` 是用 Welch’s t-test
- [Welch’s t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)
- Non-parametric tests

[這份文件](https://hackmd.io/@RinHizakura/S1PfuxJkv)有其他人寫的論文說明也可供參考

:::info
**需要再研讀** 目前還是不懂 Welch’s t-test 和 Student's t-test 的原理，還需要再研究。
:::

### 目前 `lab0-c` 內 `dudect` 缺陷

我發現 `lab0-c` 裡 `dudect` 有許多嚴重錯誤會導致偏差

- 跟據作業說明：「在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無。」經過檢查 `lab0-c` 的程式碼，發現的確沒有 percentile 相關程式。在原始的 oreparaz/dudect 會先計算 percentile 並把極端值除去。故在 `lab-0` 裡沒有正確實作這部份。
- `constants.c` 裡的 `prepare_inputs` 和 `measure` 設計錯誤。 `prepare_inputs` 裡的字串產生程式沒有辦法產生長度一致的字串，因為 randombytes 可能會讓字串中間有 `'\0'` ，此外 `prepare_inputs` 沒有跟據「固定資料」產生固定字串。
- `prepare_inputs`　雖然一開始產生隨機資料放在 `input_data` 中，但這份資料沒有在 `measure` 使用

`dudect` 是直接用 `rdtsc` 指令來計算花費週期數，但計算的結果會包含程式執行到一半可能會被中斷去執行，因為系統上不是只有待測程式在執行。

### 對 `lab-0` 中 `dudect` 的改進

改進方法如下：

- 嘗試直接把 [oreparaz/dudect](https://github.com/oreparaz/dudect) 引入 lab0-c 中，解決沒有 percentile 相關程式的問題。且 [oreparaz/dudect](https://github.com/oreparaz/dudect) 內的統計相關程式比較完整。
- 重寫準備輸入資料和待測程式碼（也就是 dudect 會呼叫量測時間的程式），改善上節提到的缺陷。

1. 我直接把 [`dudect.h`](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 引入我的程式，但把它拆成 `dudect.c` 和 `dudect.h` 。
2. 把 `dudect.c` 內的 `randombytes` 和 `randombit` 的函式移除， 因此在 `random.c` 就有提供相同的函式了。
3. `dudect` 原本是設計一個 binary 只能有一種測試，因為它會直接呼叫 `prepare_inputs` 和 `do_one_computation` 這二個由使用者實作的函式，但因為 `lab0-c` 有四個待測物，故我把 `dudect_config_t` 內加入 `prepare` 和 `compute` 二個存放 function pointer 欄位，然後把原本呼叫 `prepare_inputs` 和 `do_one_computation` 改成呼叫 `dudect_config_t` 內的 function pointer 。

typedef struct __dudect_config dudect_config_t;

typedef void (*dudect_prepare_func_t)(void *priv,
                                      dudect_config_t *conf,
                                      uint8_t *input_data,
                                      uint8_t *classes);

typedef uint8_t (*dudect_compute_func_t)(void *priv,
                                         size_t size,
                                         uint8_t *data);

struct __dudect_config {
    size_t chunk_size;
    size_t number_measurements;
    void *priv;
    dudect_prepare_func_t prepare;
    dudect_compute_func_t compute;
};

4. 增加 `DUDECT_NOT_ENOUGHT_MEASUREMENTS` 這個狀態。並修改 `report` 在還沒收集足夠資料時，回傳 `DUDECT_NOT_ENOUGHT_MEASUREMENTS` 。而 `dudect_main` 函式中，預設也是在還沒測試時回 `DUDECT_NOT_ENOUGHT_MEASUREMENTS`

typedef enum {
    DUDECT_LEAKAGE_FOUND = 0,
    DUDECT_NO_LEAKAGE_EVIDENCE_YET,
    DUDECT_NOT_ENOUGHT_MEASUREMENTS,
} dudect_state_t;

5. 實作 [`measure.c`](https://github.com/yanjiew1/lab0-c/blob/master/dudect/measure.c) 和 [`measure.h`](https://github.com/yanjiew1/lab0-c/blob/master/dudect/measure.h) ，放置待測程式及 `dudect_config_t` 的相關設定。並且也實作 `is_##op_const` 巨集用來產生 `is_xxx_const` 函數供 `qtest.c` 內的程式呼叫。此外把 `CHUNK_SIZE` 提升到 640 使測試更準確。因為版面有限，就不把程式碼貼出來，可點連結觀看。
6. 為了測試看看 dudect 是不是能正常偵測時間差異，我故意把固定資料那組測資的字串長度改成 0，確實 dudect 就能發現非常數時間。確認功能正常後就回復原本設定。

完成以上步驟後，`make test` 的結果正確回報為執行時間為常數時間。
:::warning
請提交 pull request。
:notes: jserv
:::

:::info
**可再進一步實驗**
1. 嘗試用 `perf_event_open` 搭配 `config = PERF_COUNT_HW_CPU_CYCLES` 量測時間。看看能不能更能排除待測程式執行時被中斷的執行時間。
2. 嘗試對原本的 `labc-0` 中的 `dudect` 程式做修正，而不是直接引入上游最新版和重寫測試程式。
:::

---

## 貢獻與程式改進記錄

### 修正 GitHub Action 問題

我檢視我的 repository 的 GitHub Action 有無正常運作時，發現 GitHub Action 在 `Run webfactory/ssh-agent@v0.7.0` 這個步驟時就失敗了。

於是我就看了一下原始的 `sysprog21/lab0-c` repository 。裡面的 GitHub Action 可以運作成功。發現原來 `Run webfactory/ssh-agent@v0.7.0` 是用來載入 ssh private key 讓原始 `sysprog21/lab0-c` repository 在沒有 `queue.c` 的解答情況下，能從另一個 private repository 拷貝 `queue.c` 來使用，使原始的 `sysprog21/lab0-c` repository 的 GitHub 在沒解答情況下也可以測試。

但是在 fork 之後的 repository ，不會有 ssh private key 。導致在 `Run webfactory/ssh-agent@v0.7.0` 步驟就失敗，以致後面的 `make check` 、 `make test` 等步驟都不會執行。

我看了 GitHub 的文件後，發現可以把 GitHub Action 某個步驟標示為即使失敗仍然能繼續執行。故我在 `.github/workflows/main.yml` 裡進行小修正，針對 `webfactory/ssh-agent@v0.7.0` 這個步驟加入 `continue-on-error: true` 來讓它失敗時，也可以往下執行其他 GitHub Action ，使得即便沒有 ssh private key ， GitHub Action 也能有作用。

我為此建了一個 [pull request](https://github.com/sysprog21/lab0-c/pull/112) 來提交我的改動，目前已經被 merge 了。

diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
index 56c7d9e..6ed0b93 100644
--- a/.github/workflows/main.yml
+++ b/.github/workflows/main.yml
@@ -8,6 +8,7 @@ jobs:
     steps:
     - uses: actions/checkout@v3.3.0
     - uses: webfactory/ssh-agent@v0.7.0
+      continue-on-error: true
       with:
           ssh-private-key: ${{ secrets.SSH_PRIVATE_KEY }}
     - name: install-dependencies

### 其他貢獻

- [#121 Remove `return true;` in `q_quit` function](https://github.com/sysprog21/lab0-c/pull/121)
原本的程式 `q_quit` 一開始就 `return true;` 導致後面記憶體釋放的程式沒有執行，以致於觸發 valgrind memory leak。此 pull request 改善此問題
- [#122 Register `line_atexit` in `linenoise` function](https://github.com/sysprog21/lab0-c/pull/122)
`line_atexit` 內會呼叫 `free_history` 釋放記憶體。但在 stdin 非 tty 時， `line_atexit` 不會被註冊，以致於使用檔案輸入指令時，沒辦法釋放 `linenoise` 記憶體，導致 `linenoise` 出現 memory leak 。此 pull request 修正此問題。
- [#127 `Merge do_i(h|t)` into a single function](https://github.com/sysprog21/lab0-c/pull/127)
- [#130 Fix warning message in do_descend](https://github.com/sysprog21/lab0-c/pull/130)
:::info
**TODO** 放 GitHub Pull requests
:::

---

## 其他記錄

### cppcheck 問題

要 commit 時發現在 `report.c` 中的 `static char *msg_name_text[N_MSG]` 變數宣告會觸發 cppcheck 錯誤。原本打算把此行改為 `static char * const msg_name_text[N_MSG]` ，但後來發現 GitHub 有更新新的程式碼加入 `// cppcheck-suppress constVariable` 修正此問題，因此我直接在 GitHub 網頁介面上操作 sync fork 取得更新的程式至自己 fork 出來的 repository 。

因為自己只寫了一點點程式，故直接捨棄本地端的 commit，用 GitHub 上新的程式覆寫本地的 repository 。
:::warning
可善用 `git rebase`
:notes: jserv
> 謝謝老師，我會嘗試練習 `git rebase`
:::