# 2023q1 Homework1 (lab0)
contributed by < [`yanjiew1`](https://github.com/yanjiew1) >
> [GitHub](https://github.com/yanjiew1/lab0-c)
## 開發與實驗環境
```bash
$ 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)
```c
/* 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` 釋放鏈結串列所配置的記憶體空間。。
```c
/* 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);
}
```
#### 開發過程記錄
一開始程式碼如下:
```c
/* 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` 裡面的一個成員。於是變更如下:
```diff
@@ -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` ,修改如下:
```diff
@@ -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` ,就可以安全操作。最後變更如下:
```diff
@@ -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)
```c
/* 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` 。
```c
/* 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` 來完成字串拷貝。
```c
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` 來做。
```c
/* 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` 變數的值即為所求。
```c
/* 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`
這裡充份利用雙向鏈結串列的特性,從頭尾開始走訪節點,直到二個指標碰面時,即取得中間的節點。最後再把中間節點所代表的元素刪除。
```c
/* 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` 來刪除它。
```c
/* 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` 允許對目前走訪的節點移動位置。因為是往前移到開頭,故不會因為節點移動而改變走訪次序或是重複走訪。
```c
/* 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
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` 已在反轉的過程中移動位置了。
```c
/* 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` 的程式 。
```c
/* 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` 。
```c
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` 合併。
```c
/* 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` 巨集不在前者出現。若有它則可以用它來實作。
```c
/* 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 進行合併。
```c
/* 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` 的程式複製一份來用,把中間的 `<` 改為 `>` 即可。
```c
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;` 使下面釋放記憶體的程式沒辦法執行。把這行拿掉後就正常了。
```diff
--- 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 就解決了。
```diff
--- 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 的版本。
```bash
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` 實作合併時,由大到小排序。其中迴圈內在選擇要哪一個元素放到合併後的串列時,做了些更動,如下:
```diff
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` 函式宣告改為:
```c
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` ,但正負號相反,如下:
```c
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` ,再選擇適當的比較函式。
```c
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` 比較函式作為比較大小用。我的實作如下:
```c
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
:::
```c
static int use_ksort = 0;
```
```c
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)$ ,故我採取不同的策略。
我先建立一個存放所有節點的指標陣列,如下所示:
```c
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)
:::
把所有節點的位址放入陣列中:
```c
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]$ 之間的數。
```c
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 地方加入:
```c
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 。
```c
#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++` 亂數品質測試
執行下面命令來測試亂數品質,可得到這個報告
```shell
./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, 可說是相當高。
#### 系統內建亂數測試
```bash
$ ./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 。
```c
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`
```c
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
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`
:::