# 2021q1 Homework1 (lab0)
contributed by < `ngokchaoho` >
## 作業要求
需要由學員補完並逐步精進，包含以下:
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* ==`q_sort`==: 「[Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程所新增，以==遞增順序==來排序鏈結串列的元素，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
## 系統環境
* Distributor ID: Ubuntu
* Description: Ubuntu 20.04.1 LTS
* Release: 20.04
* Codename: focal
:::danger
注意共筆書寫規範：中英文間用一個半形空白字元區隔。唯有掌握各項細節，來日才能征服 Linux 核心。
:notes: jserv
:::
## 實作流程
### `q_size`
題目要求q_size是$O(1)$, 所以在queue.t這個struct裡面增加size這個member
```cpp
int q_size(queue_t *q)
{
if (q == NULL || q->head == NULL)
return 0;
return q->size;
}
```
### `q_new`
檢查 malloc 是否成功，這裡可以看到 queue_t 除了 head 和 size, 還有一個 tail 的 member，這是為了可以在 $O(1)$ insert tail 而加的。
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q != NULL) {
q->head = NULL;
q->size = 0;
q->tail = NULL;
}
return q;
}
```
### `q_free`
從 Head 數過去，一個一個釋放。
```cpp
void q_free(queue_t *q)
{
if (q == NULL)
return;
if (q->head != NULL) {
list_ele_t *curr_ele = q->head;
while (curr_ele != NULL) {
free(curr_ele->value);
list_ele_t *prev_ele = curr_ele;
if (curr_ele->next != NULL) {
curr_ele = curr_ele->next;
} else {
free(curr_ele);
break;
}
free(prev_ele);
}
}
free(q);
}
```
### `q_insert_head`
因為要用到兩個 malloc，均有可能失敗，所以要 free 兩次。當只有一個元素時，Head 和 Tail 是指向同一記憶體的。
```cpp
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (q == NULL)
return false;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
newh->value = malloc(strlen(s) + 1);
if (newh->value == NULL) {
free(newh);
return false;
}
strncpy(newh->value, s, strlen(s)+1);
newh->next = q->head;
q->head = newh;
q->size += 1;
if (q->size == 1)
q->tail = q->head;
return true;
}
```
### `q_remove_head`
依照題目指示把 element 中的 value 放入 sp, 限定 bufsize - 1，strncat 會自動加上 terminating null-character. 每次刪除都定義prev_head 為現在的 head 然後移動 q->head 到下一順位，最後類似過河拆橋，釋放prev_head相關的記憶體。雖然此作業沒有q_remove_tail, 因此當變成 empty queue 時將 `q->tail` 指向正確的 NULL，沒有即時需要，但考慮到完整和將來擴展，還是將此行為（empty queue 時將 `q->tail` 指向正確的 NULL）實作。
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || q->head == NULL)
return false;
if (sp != NULL) {
strncat(sp, q->head->value, bufsize - 1);
}
list_ele_t *prev_head = q->head;
q->head = q->head->next;
free(prev_head->value);
free(prev_head);
q->size -= 1;
if (q->size == 0) {
q->tail = NULL;
}
return true;
}
```
### `q_insert_tail`
為了可達成 $O(1)$ 時間複雜度，如上所述地在 queue_t 這個 struct 裡面加入了 tail, 因此如果不是 empty queue 的話只要記得加 size 和 tail 要指向新的記憶體就可以了, 與 insert head 相同，malloc 有可能失敗，所以如果失敗要free兩次。當只有一個元素時，Head 和 Tail 是指向同一記憶體的。這裡一開始使用了不安全的 strcpy, 因為 destination 的空間是由 `malloc(strlen(s+1))` 所配置，如果 malloc 成功，則不會有 overflow 的問題。
然而 git commit hook 不允許 strcpy，因此改用 strncpy。
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (newt == NULL)
return false;
newt->value = malloc(strlen(s) + 1);
if (newt->value == NULL) {
free(newt);
return false;
}
newt->next = NULL;
strncpy(newt->value, s, strlen(s)+1);
q->size += 1;
if (q->size > 1) {
q->tail->next = newt;
q->tail = newt;
} else {
/*from empty queue*/
q->head = newt;
q->tail = newt;
}
return true;
}
```
### `q_reverse`
走訪 queue 的每一個 element 的同時，將 curr_ele 的 next 指向到 prev_ele。prev_ele 初始化為 NULL 以作為新的結束標識。
```cpp
void q_reverse(queue_t *q)
{
if (q == NULL || q->head == NULL)
return;
list_ele_t *curr_ele = q->head;
list_ele_t *prev_ele = NULL;
while (curr_ele != q->tail) {
list_ele_t *next_ele = curr_ele->next;
curr_ele->next = prev_ele;
prev_ele = curr_ele;
curr_ele = next_ele;
}
curr_ele->next = prev_ele;
list_ele_t *tmp = q->head;
q->head = q->tail;
q->tail = tmp;
}
```
### `q_sort`
參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/), 試作了 linked list 的 selection sort，
因為時間複雜度是 $O(N^2)$，所以沒有通過 trace-16-perf, trace-15-perf。預期可以通過改用 merge sort 解決。
Linked List 的 selection sort 想法很單純，就是從 unsorted_head 開始每次去 queue 的尾部加上考慮範圍裡最小的 element（見 j 迴圈部分），考慮範圍從最開始有 q->size 個 element 要考慮到最後剩下一個。為了要把考慮範圍內的 minNode 從其原本的位置移向最後，有必要記錄其前一個 element (變數名為 min_Prev)，將min_Prev 的 next 指向 minNode的 next，以達到跳過的效果。如果 minNode 恰好是 unsorted_head (考慮範圍的開頭)則需要例外處理，將 unsorted_head 替換成其 next，因為 unsorted_head 並沒有被夾在中間，只需要直接將其從考慮範圍中剔除就好。新的 q->head 會是第一個找到的 minNode (最小的元素)，因此將其指定為第一次執行 i 迴圈最後時的 sorted_tail 就好。
```cpp
void q_sort(queue_t *q)
{
if (q == NULL || q->head == NULL || q->size == 1)
return;
list_ele_t *sorted_tail = q->tail;
list_ele_t *unsorted_head = q->head;
list_ele_t *prev = NULL;
list_ele_t *curr = NULL;
list_ele_t *minNode = NULL;
list_ele_t *min_Prev = NULL;
for (int i = q->size; i > 0; i--) {
curr = unsorted_head;
minNode = unsorted_head;
prev = unsorted_head;
min_Prev = unsorted_head;
for (int j = 0; j < i; j++) {
if (strcmp(curr->value, minNode->value) < 0) {
minNode = curr;
min_Prev = prev;
}
curr = curr->next;
if (j != 0)
prev = prev->next;
}
sorted_tail->next = minNode;
sorted_tail = sorted_tail->next;
if (minNode == unsorted_head) {
unsorted_head = unsorted_head->next; // moved comparision windows
} else {
min_Prev->next = minNode->next;
}
sorted_tail->next = NULL;
if (i == q->size)
q->head = sorted_tail;
}
q->tail = sorted_tail;
}
```
#### merge sort q_sort via recursion
用遞迴實現 merge sort 可以視為兩個部分，第一部分是將 linked list 拆分為兩個 sub linked list with head l1,l2 直至到最後剩下一個元素或沒有元素時則回傳自身head, 其他的上層則開始逐層回傳merge(l1, l2)，第二部分是逐層將已經自身排序好的兩個 sub linked list，逐一從兩個開頭 l1,l2 比較，有序地融合，詳情見 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)。
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
if (strcmp(l1->value, l2->value) < 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
list_ele_t *merge_sort_list(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = merge_sort_list(head);
list_ele_t *l2 = merge_sort_list(fast);
return merge(l1, l2);
}
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(queue_t *q)
{
if (q == NULL || q->head == NULL || q->size == 1)
return;
q->head = merge_sort_list(q->head);
list_ele_t *tmp = q->head;
while (tmp->next != NULL)
tmp = tmp->next;
q->tail = tmp;
}
```
此時，使用`make valgrind`可見
>==10673== Process terminating with default action of signal 11 (SIGSEGV)
==10673== Access not within mapped region at address 0x1FFE8010A8
==10673== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==10673== at 0x10E538: merge (queue.c:179)
==10673== If you believe this happened as a result of a stack
==10673== overflow in your program's main thread (unlikely but
==10673== possible), you can try to increase the size of the
==10673== main thread stack using the --main-stacksize= flag.
==10673== The main thread stack size used in this run was 8388608.
==10673== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
推測是用遞迴實作 merge 部分導致了 stack overflow，假設需要 merge 兩個合共有 n 個元素的 sub linked list，則需要 O(n) stack 記憶體。
此外，當行程收到 signal - SIGSEGV 而結束時被不會釋放由 malloc 分配存放於 heap 中的記憶體。
>==12937== 5 bytes in 1 blocks are still reachable in loss record 1 of 36
==12937== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==12937== by 0x10CA22: strsave_or_fail (report.c:230)
==12937== by 0x10D282: parse_args (console.c:192)
==12937== by 0x10D282: interpret_cmd (console.c:243)
==12937== by 0x10DB03: cmd_select (console.c:594)
==12937== by 0x10DDD0: run_console (console.c:667)
==12937== by 0x10C283: main (qtest.c:780)
修改使用 while loop,
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *temp = NULL;
list_ele_t *head = NULL;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) < 0) {
if (temp == NULL) {
temp = l1;
head = l1;
l1 = l1->next;
} else {
temp->next = l1;
temp = l1;
l1 = l1->next;
}
} else {
if (temp == NULL) {
temp = l2;
head = l2;
l2 = l2->next;
} else {
temp->next = l2;
temp = l2;
l2 = l2->next;
}
}
}
if (l1)
temp->next = l1;
if (l2)
temp->next = l2;
return head;
}
```
此時，所有 test-case 都能通過了。
### `開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤`
依照課程指示
> 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
先執行 qtest 再於命令提示列輸入 help 命令，會使 開啟 Address Sanitizer 觸發錯誤，應予以排除
得到錯誤提示
>==13821==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55f5de2143c0 at pc 0x55f5de1fd7dd bp 0x7fff98faa230 sp 0x7fff98faa220
READ of size 4 at 0x55f5de2143c0 thread T0
#0 0x55f5de1fd7dc in do_help_cmd /home/ngokchaoho/linux2021/lab0-c/console.c:307
#1 0x55f5de1fd8f0 in interpret_cmda /home/ngokchaoho/linux2021/lab0-c/console.c:221
#2 0x55f5de1fe0d5 in interpret_cmd /home/ngokchaoho/linux2021/lab0-c/console.c:244
#3 0x55f5de1ff818 in run_console /home/ngokchaoho/linux2021/lab0-c/console.c:660
#4 0x55f5de1fc405 in main /home/ngokchaoho/linux2021/lab0-c/qtest.c:780
#5 0x7f07d05d80b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
#6 0x55f5de1f9bad in _start (/home/ngokchaoho/linux2021/lab0-c/qtest+0x8bad)
可以看出，這是嘗試讀入一個 size 4 的全局變數時，遇到的錯誤。推測該段 size 4 記憶體至少沒有完全分配給此全局變數。
>SUMMARY: AddressSanitizer: global-buffer-overflow /home/ngokchaoho/linux2021/lab0-c/console.c:307 in do_help_cmd
然後，又見總結部分的提示錯誤出現在307行，於是初步猜測為 ` *plist->valp ` 引起的錯誤，因為 int 在 64bits 機器上剛好是4個 byte.
於是前往 ` param_list ` 初始化的地方 ` init_cmd ` ，發現 ` &echo ` 和 ` &simulation ` 兩個指向 bool 變數的指標被轉換成了指向 int 變數。推測此處會發生錯誤，因為 bool 型變數只會被分配 1 byte.
因此，考慮到` *plist->valp `是 int, 所以將 ` &echo ` 和 ` &simulation ` 的定義型態改成 int, 預設值為 0 。
重複上述課程指示，確認錯誤已經消失。
### `運用 Valgrind 排除 qtest 實作的記憶體錯誤`
使用 ` make valgrind ` 可見以下由 linenoise 中為 command history 分配的記憶體沒有被釋放的錯誤。
>#Test of insert_head and remove_head
==94206== 14 bytes in 1 blocks are still reachable in loss record 1 of 3
==94206== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==94206== by 0x4A4E50E: strdup (strdup.c:42)
==94206== by 0x1100CD: linenoiseHistoryAdd (linenoise.c:1236)
==94206== by 0x110C60: linenoiseHistoryLoad (linenoise.c:1325)
==94206== by 0x10C24C: main (qtest.c:769)
==94206==
==94206== 127 bytes in 19 blocks are still reachable in loss record 2 of 3
==94206== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==94206== by 0x4A4E50E: strdup (strdup.c:42)
==94206== by 0x110041: linenoiseHistoryAdd (linenoise.c:1236)
==94206== by 0x110C60: linenoiseHistoryLoad (linenoise.c:1325)
==94206== by 0x10C24C: main (qtest.c:769)
==94206==
==94206== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==94206== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==94206== by 0x11008D: linenoiseHistoryAdd (linenoise.c:1224)
==94206== by 0x110C60: linenoiseHistoryLoad (linenoise.c:1325)
==94206== by 0x10C24C: main (qtest.c:769)
==94206==
前往 linenoise.c 即可發現需要用到 [atexit](http://www.cplusplus.com/reference/cstdlib/atexit/) (linenoiseAtExit)，程式才會在結束時，釋放 history 相關記憶體。而如果有用 linenoise 的 main api，設置 exit 行為的部分就會被運行，因此，當 `./qtest` 手動測試時，不會遇到此記憶體錯誤。
但事實上，當用檔案測試時根本用不到 linenoise，我們不會在測試 trace 裡用到 line editing。因此，解決方案為僅在不提供檔案名時（即執行 `qtest` 並啟動 shell 時)，載入 history 以方便 line editing.
```cpp
if (infile_name == NULL) {
linenoiseHistorySetMaxLen(HISTORY_LEN);
linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */
}
```
### `透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗`
運行`valgrind -q --tool=massif ./qtest -f traces/trace-15-perf.cmd
` 並使用 `massif-visualizer massif.out.9137` 即可得下圖
下列是實際執行的命令（command）
```shell
# Test performance of insert_tail, size, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
size 1000
reverse
sort
size 1000
```
可見上圖符合預期，因為只有在前面做 insert head 或 insert tail 的時候會用malloc獲得 heap 記憶體。留意，如果直接用原本的 qtest 則會出現
```shell=
$ valgrind -q --tool=massif ./qtest -f traces/trace-15-perf.cmd
cmd> # Test performance of insert_tail, size, reverse, and sort
cmd> option fail 0
cmd> option malloc 0
cmd> new
q = []
cmd> ih dolphin 1000000
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
q = [dolphin ... ]
cmd> it gerbil 1000000
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (2 failures total)
```
原因是 ` massif ` 導致的超時錯誤使得 ok==0 而原本的 qtest 是在 ` ok = ok && finish_cmd(); ` 釋放記憶體的。如果 ok == 0, 則 ` finish_cmd ` 在 && 邏輯下將不再執行 ` finish_cmd ` 因此亦不會釋放任何 heap 記憶體。
更改為` ok = finish_cmd() && ok` 可以緩解這個問題，但由於錯誤在 malloc 後發生（e.g. insert_head strncpy），因此分配得到的記憶體並沒有於 queue 中記錄，結果導致程式沒法釋放該類記憶體, 預期可以在 harness 設計一個釋放記錄於 BELE 雙向鏈表的函式進一步主動釋放更多記憶體。
然而，由於 signal 可以在任何地方發生，此舉不能保證所有 system malloc 都有被記錄在雙向鏈表，最後的防線依然在 OS。
## 研讀 Dude, is my code constant time
論文使用 [welch's t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) 去 分辨程式是否有 time-leakage.即量測程式執行時間是否能在常數時間 $O(1)$ 完成。
利用 leakage detection test 測試程式是否是 constant time ，優點是在這個方法下不需要硬體模型，分為以下三個步驟進行
1. Repeatedly measure exeution time
分別用兩類(class) input data ，論文中提到的是 fix-vs-random ， fixed class 可以選擇 corner-case 已達到檢查一些特定的情況是否於隨機的情況有顯著差異，常見於 [A/B test](https://en.wikipedia.org/wiki/A/B_testing)
2. Apply post-processing
- Cropping: 去掉某些極端值，這些極值往往是一些與程式無關的情況引至的,例如 OS interruption
- High-order preprocessing: 由於此論文只是用 t - test 去比較平均時間，亦即 first order mean 的比較，所以並不需要 higher-order preprocessing.
3. Apply statistical test
- null hypothesis: "the two timing distributions are equal"
- if statistical test reject the null hypothesis, then we know it's not run in constant time
- [Welch's t-test](https://en.wikipedia.org/wiki/Welch's_t-test): 本專案使用的測試
### Welch’s t-test
- 先計算出兩個 class (class 0, class 1) 的平均值和變異數
- Welch's t-test defines the statistic t by the following formula:
- $t = \frac{\bar{X_0} - \bar{X_1}}{\sqrt{\frac{Var_0}{N_0} + \frac{Var_1}{N_1}}}$
- $t$ 越接近 0 代表兩組數據的差異越小
- lab0 實作上只有到這裡，然後直接檢查 $t$ 是否大於 `t_threshold_moderate` default = 10
- 改善成用 `t_threshold_moderate` = df from Welch–Satterthwaite equation 對應的 abs(t distribution 0.05 percentile) ，實測 df 遠遠大於 1，因此 default 10 非常寬鬆，然而 Trace - 17 依然經常不通過，可能是由於的沒有 crop 的緣故。
```
double t_compute_df(t_ctx *ctx)
{
double var[2] = {0.0, 0.0};
var[0] = ctx->m2[0] / (ctx->n[0] - 1);
var[1] = ctx->m2[1] / (ctx->n[1] - 1);
double num = pow((var[0] / ctx->n[0] + var[1] / ctx->n[1]), 2);
double den = pow(var[0],2) / (pow(ctx->n[0], 2) * (ctx->n[0] - 1)) +
pow(var[1],2) / (pow(ctx->n[1], 2) * (ctx->n[1] - 1));
double df = num / den;
return df;
}
```
TODO: Cropped t test
Sign in with Wallet
Connect another wallet