# 2024q1 Homework1 (lab0)
contributed by < [youjiaw](https://github.com/youjiaw/lab0-c) >
:::danger
留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。
> 好的
:::
### Reviewed by `yu-hsiennn`
```diff
// Add remaining elements
- if (!list_empty(head1))
- list_splice_tail_init(head1, &merged);
- if (!list_empty(head2))
- list_splice_tail_init(head2, &merged);
+ (!list_empty(head1)) ? list_splice_tail_init(head1, &merged) : list_splice_tail_init(head2, &merged);
```
改寫程式碼 ( q_sort )，使其更為精簡。
:::warning
感謝提醒，已修改。
:::
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 46 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i9-10900X CPU @ 3.70GHz
CPU family: 6
Model: 85
Thread(s) per core: 2
Core(s) per socket: 10
Socket(s): 1
Stepping: 7
CPU max MHz: 4700.0000
CPU min MHz: 1200.0000
BogoMIPS: 7399.70
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 320 KiB (10 instances)
L1i: 320 KiB (10 instances)
L2: 10 MiB (10 instances)
L3: 19.3 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-19
```
## 指定的佇列操作
<s>實做 queue</s>
:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement
「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
### `q_new`
配置記憶體，並用 `INIT_LIST_HEAD` 初始化。
### `q_free`
一開始實作時，沒有確認 `head` 是否有成功配置到記憶體，在 `make test` 的 "Test of malloc failure on new" 會出現錯誤。
```diff
void q_free(struct list_head *head)
{
+ if (!head)
+ return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, head, list)
q_release_element(entry);
free(head);
}
```
### `q_insert_head`, `q_insert_tail`
原本未檢查記憶體配置情況，在 `make test` 的 "Test of malloc failure on insert_head, insert_tail" 出現錯誤。
```diff
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
new->value = strdup(s);
+ if (!new->value) {
+ free(new);
+ return false;
+ }
```
### `q_remove_head`, `q_remove_tail`
使用 API 的 `list_entry` 取得開頭的 `element` ，將值複製到 `sp` 並從佇列移除。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
struct list_head *node = head->next;
element_t *element = list_entry(node, element_t, list);
if (sp) {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(node);
return element;
}
```
`q_remove_tail` 的做法相同，但改取尾端的 `element`。
```diff
- struct list_head *node = head->next;
+ struct list_head *node = head->prev;
```
### `q_size`
使用[教材](https://hackmd.io/@sysprog/linux2024-lab0-a#%E7%89%9B%E5%88%80%E5%B0%8F%E8%A9%A6)提供的做法。
:::danger
列出程式碼的目的是討論和檢討，倘若你沒有如此的舉措，就不用列出。
> 好的，已修正。
:::
### `q_delete_mid`
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
> 好的，謝謝老師提醒。
:::
我原本的做法如下，除了沒有考慮到 `q_size` 逐一走訪每個節點的成本，使用 indirect pointer 來實作此函式的優缺點也需討論。
```c
int mid_node = q_size(head) / 2;
struct list_head **indir = &head;
for (int i = 0; i <= mid_node; i++)
indir = &((*indir)->next);
element_t *element = list_entry(*indir, element_t, list);
list_del(*indir);
q_release_element(element);
```
在參考 [chun61205](https://hackmd.io/H2fpkPChSkuRw88H4bt_XQ?view#q_delete_mid) 以及 [yanjiew1](https://hackmd.io/@komark06/SyCUIEYpj#q_delete_mid-%E5%AF%A6%E4%BD%9C) 的建議後，決定使用兩個指標，從頭尾往中間找，以此減少記憶體的存取次數。
> commit [85a19ba](https://github.com/youjiaw/lab0-c/commit/85a19babc45540b0532aa275ceadf1b746fe0f2c)
```c
struct list_head *left = head->next, *right = head->prev;
while (!(left == right) && !(right->next == left)) {
left = left->next;
right = right->prev;
}
list_del(left);
q_release_element(list_entry(left, element_t, list));
```
### `q_delete_dup`
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
由於是傳入已排序的佇列，因此，只需檢查相鄰節點的值是否相同。
使用 `list_for_each_entry_safe` 逐一走訪每個節點，若 `current` 與 `next` 的值相同，就刪除 `current`，而 `flag` 的作用為刪除最後一個重複的節點。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
element_t *current, *next;
bool flag = false;
list_for_each_entry_safe (current, next, head, list) {
if (current->list.next == head)
break;
if (strcmp(current->value, next->value) == 0) {
list_del(¤t->list);
q_release_element(current);
flag = true;
} else if (flag) {
list_del(¤t->list);
q_release_element(current);
flag = false;
}
}
return true;
}
```
目前發現 `make test` 有時後會出現以下錯誤：
ERROR: Duplicate strings are in queue or distinct strings are not in queue
在經過 `./qtest` 測試不同測資後，發現如果最後一個節點有重複的話，會直接被跳過，因此加入檢查程式碼。
> commit [bb834f2](https://github.com/youjiaw/lab0-c/commit/bb834f2fb39f86fd469119c091e7ec9c925ae037)
```diff
- if (current->list.next == head)
+ if (current->list.next == head) {
+ if (flag) {
+ list_del(¤t->list);
+ q_release_element(current);
+ }
break;
+ }
```
### `q_swap`
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
使用 `list_for_each` 逐一走訪每個節點。
使用 `list_move` 將 `next` 移到 `prev` 後方，等同於將 `current` 與 `next` 交換位置。
```c
struct list_head *current;
list_for_each (current, head) {
if (current->next == head)
break;
list_move(current->next, current->prev);
}
```
### `q_reverse`
用指標 `first` 指向開頭節點，並不斷將 `next` 移動至 `head` 後方。
```c
struct list_head *first = head->next;
while (first->next != head)
list_move(first->next, head);
```
### `q_reverseK`
參考 [koty6069](https://hackmd.io/UJQfmB61SkuVMoKR7dcYVA?view#q_reverseK) 的做法，以每 k 個節點為一組執行 `q_reverse`。
```c
struct list_head *current, *safe, *ptr = head;
int cnt = 0;
list_for_each_safe (current, safe, head) {
if (++cnt == k) {
LIST_HEAD(tmp);
list_cut_position(&tmp, ptr->next, current);
q_reverse(&tmp);
list_splice(&tmp, ptr);
ptr = safe->prev;
cnt = 0;
}
}
```
### `q_sort`
分為 `q_sort` 及 `list_merge`。
1. `q_sort`
* 使用快慢指標及 `list_cut_position` 將佇列對半切。
* 不斷遞迴，直到所有節點被分割成單一節點，再進行 `list_merge`。
```c
struct list_head *fast = head->next, *slow = head;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
struct list_head second_half;
list_cut_position(&second_half, head, slow);
q_sort(head, descend);
q_sort(&second_half, descend);
list_merge(head, &second_half, descend);
```
2. `list_merge`
* 比較兩個佇列的開頭節點值，依照結果和排序方式將指定節點移動到 `merged` （用來存放排序過的節點）。
* 當其中一個佇列空了，就將另一個移動到 `merged` 尾端。
```c
static void list_merge(struct list_head *head1,
struct list_head *head2,
bool descend)
{
struct list_head merged;
INIT_LIST_HEAD(&merged);
while (!list_empty(head1) && !list_empty(head2)) {
int compare_result =
strcmp(list_entry(head1->next, element_t, list)->value,
list_entry(head2->next, element_t, list)->value);
if ((descend && compare_result > 0) ||
(!descend && compare_result < 0)) {
struct list_head *tmp = head1->next;
list_move_tail(tmp, &merged);
} else {
struct list_head *tmp = head2->next;
list_move_tail(tmp, &merged);
}
}
// Add remaining elements
if (!list_empty(head1))
list_splice_tail_init(head1, &merged);
if (!list_empty(head2))
list_splice_tail_init(head2, &merged);
INIT_LIST_HEAD(head1);
list_splice(&merged, head1);
}
```
:::danger
你如何確認目前的測試程式已涵蓋排序演算法的最差狀況？
:::
### `q_ascend`
由尾端向 `head` 走訪，並比較當前與前一個節點的 `value`：
1. 若 `prev` 大於 `current`，就刪除 `prev`。
```graphviz
digraph q_ascend {
rankdir=LR
node [shape=circle, fontsize=12];
3 [fillcolor="#f9a7a7", style=filled]
Head [shape=box, fontsize=12]
Head -> 5 -> 2 -> 13 -> 3 -> 8 [arrowhead=normal, arrowtail=normal ,dir=both];
current [fontsize=15, shape=plain, fontcolor=red]
current -> 8 [style=dashed, color=red];
{ rank=same; current;8 };
}
```
2. 其餘情況，則 `current` 指向 `prev`。
```graphviz
digraph q_ascend {
rankdir=LR;
node [shape=circle, fontsize=12];
Head [shape=box, fontsize=12]
Head -> 5 -> 2 -> 13 -> 8[arrowhead=normal, arrowtail=normal ,dir=both];
current [fontsize=15, shape=plain, fontcolor=red]
current -> 13 [color=red];
{rank=same; current;13};
}
```
```c
struct list_head *current = head->prev;
while (current->prev != head) {
struct list_head *prev = current->prev;
if (strcmp(list_entry(current, element_t, list)->value,
list_entry(prev, element_t, list)->value) <= 0) {
list_del_init(prev);
q_release_element(list_entry(prev, element_t, list));
} else
current = current->prev;
}
```
<!--  -->
### `q_descend`
想法與 `q_ascend` 相同，但將條件改為：若 `prev` 小於 `current`，就刪除 `prev`。
```diff
- if (strcmp(list_entry(current, element_t, list)->value,
- list_entry(prev, element_t, list)->value) <= 0) {
+ if (strcmp(list_entry(current, element_t, list)->value,
+ list_entry(prev, element_t, list)->value) >= 0) {
list_del_init(prev);
q_release_element(list_entry(prev, element_t, list));
}
```
由下圖可發現，若由尾端向左邊走訪，只需紀錄最大值，並將小於當前最大值的節點移除即可。
### `q_merge`
目前作法是將所有佇列接起來，再執行 `q_sort`。
```c
if (list_is_singular(head))
return q_size(head);
queue_contex_t *cur = NULL,
*qhead = list_first_entry(head, queue_contex_t, chain);
list_del_init(&qhead->chain);
list_for_each_entry (cur, head, chain) {
list_splice_init(cur->q, qhead->q);
qhead->size += cur->size;
}
list_add(&qhead->chain, head);
q_sort(qhead->q, descend);
// https://leetcode.com/problems/merge-k-sorted-lists/
return qhead->size;
```
:::danger
改進你的漢語表達。
:::
## 分析記憶體問題
執行 `make valgrind` 以及開啟 `Address Sanitizer` 後，都沒有偵測到記憶體錯誤。
## 在 qtest 提供新的命令 shuffle
### `make` 時產生 eror
:::danger
directory 的翻譯是「目錄」，而非「資料夾」(folder)
> 好的，已修正。
:::
我在寫完 shuffle 函式後，做了以下幾個步驟：
1. 在 `scripts` <s>資料夾</s> 目錄中新增一個 python 檔，內容為教材提供的[測試程式](https://hackmd.io/@sysprog/linux2024-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)。
2. 在終端機確認是否有安裝 python。
3. 執行 `make`。
接著就出現數行錯誤訊息，以下節錄其中兩行做紀錄
```shell
/usr/bin/ld: /home/webber/linux2024/lab0-c/qtest.c:884: undefined reference to `__asan_report_load8'
/usr/bin/ld: /home/webber/linux2024/lab0-c/qtest.c:887: undefined reference to `__asan_report_load8'
```
:::danger
這與 Address Sanitizer 有關，查閱 GCC 手冊。
> 好，謝謝老師提醒。
:::
就我的觀察，所有的 `.c` 檔均有產生此錯誤，內容格式為
```shell
/usr/bin/ld: [路徑名稱]: undefined reference to `xxx`
```
嘗試解決：
首先，刪除測試的 Python 檔案和 shuffle 函式，確保在 Visual Studio Code 的版本控制中，沒有任何更改過的項目（版本與成功執行 make valgrind 時一致）。但仍有相同的錯誤訊息。
在老師提醒這與 Address Sanitizer 有關後，我嘗試執行 `make clean` 及 `make SANITIZER=0` 來關閉它，隨後便可順利執行 `make test`。
### 統計方法驗證 shuffle
函式按照 Fisher–Yates shuffle 演算法來實作，以下為測試 [1, 2, 3, 4] 做 shuffle 1,000,000 次的直方圖。
## 論文〈Dude, is my code constant time?〉
### 閱讀論文
Dudect 使用 leakage detection tests 在目標平台上進行統計分析，以決定該程式是否能在常數時間內完成，此方法解決了相關研究中，需要對硬體進行建模的困難。
我的疑惑是，為什麼兩種輸入資料的執行時間分佈相同時，就代表此演算法可以在常數時間內完成？
在查閱了 leakage detection 的論文後得知，在兩種輸入資料下，如果演算法的執行時間分佈在統計上沒有顯著差異，則代表演算法的性能不受輸入資料分佈的影響，即時間複雜度為常數時間。
### 解釋本程式的 "simulation" 模式
由 [trace-17-complexity.cmd](https://github.com/sysprog21/lab0-c/blob/d43e0723a034586e2200cfae0263657304ffcd02/traces/trace-17-complexity.cmd#L2) 可得知，在測試 it, ih, rh 及 rt 是否為常數時間時，會開啟 simulation 模式，讓 `qtest.c` 的 [queue_insert()](https://github.com/sysprog21/lab0-c/blob/d43e0723a034586e2200cfae0263657304ffcd02/qtest.c#L184) 與 [queue_remove()](https://github.com/sysprog21/lab0-c/blob/d43e0723a034586e2200cfae0263657304ffcd02/qtest.c#L291C13-L291C25) 函式可以使用 `dudect` 目錄中的 [test_const()](https://github.com/sysprog21/lab0-c/blob/d43e0723a034586e2200cfae0263657304ffcd02/dudect/fixture.c#L154C13-L154C23) 進行測試。
`test_const()` 會依照預先設定的測試次數，持續呼叫 `doit()` 來獲得測試結果，此函式可分為三個部分，分別對應到 `dudect` 中的 `dudect_init()`, `dudect_main()` 及`dudect_free()`。
### 處理 percentile
```c
if (first_time) {
// throw away the first batch of measurements.
// this helps warming things up.
prepare_percentiles(ctx);
} else {
update_statistics(ctx);
ret = report(ctx);
}
```
在 `dudect_main()` 裡，會捨棄部份的第一批測量結果，根據論文所述，大於閾值 p 的測量值會被捨棄，目的是要讓結果與測量值的分佈盡可能的相符，我目前還不是很理解此意思。
若不是第一次測試，會呼叫 `update_statistics()`，可以發現在 `dudect` 中的函式會捨棄前 10 次的結果，而 `lab0-c` 則是沒有捨棄。
```c
// dudect
for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {
// lab0-c
for (size_t i = 0; i < N_MEASURES; i++) {
```
因此，我們要改進的部份如下：
* 將處理 percentile 的函式加入 lab0-c。
* 更改 update_statistics() 的迴圈走訪範圍。
做完上述的改進後（commit [cb0eb09](https://github.com/youjiaw/lab0-c/commit/cb0eb09fb67c93b7465a81a499c8da252f086a48)），`make test` 的 `trace-17-complexity` 就可以順利通過了。
## 嘗試引入 lib/list_sort.c 引入到 lab0-c 專案
Sign in with Wallet
Connect another wallet