# 2024q1 Homework1 (lab0)
contributed by < `max890808` >
### Reviewed by `mesohandsome`
敘述函式新增或修改什麼部分，可以貼出對應的關鍵程式碼，可善用 diff。
```diff
- strcpy()
+ strncpy()
```
有些 commit 沒有連結到正確的 github，例如 `q_insert_head` 實作中的這兩個
> commit [8354a3d](8354a3db4d6ac5ee2c13cf9b9bfeebb017e34d2b), commit [39a124d](39a124d90c83c68c521190595be938fae0170403)
研讀 lib_sort.c 並引入到 lab0-c 章節中，只有看到比較，沒有研讀？
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 94
Model name: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
Stepping: 3
CPU MHz: 2600.000
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 5199.98
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## 指定的佇列實作
### `q_new`
> commit [ac06e12](https://github.com/max890808/lab0-c/commit/ac06e1286e379e1016f175a0e5125aef83e55914)
:::danger
Chris Beams 在 [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/) 一文 (繁體中文翻譯: [如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)) 提出，好的 Git commit message 應符合七條規則:
1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. 標題開頭要大寫
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how
你沒有依循上述規範，請詳讀作業說明，以 `git rebase -i` 改正。
:::
使用 `malloc()` 配置 list_head 記憶體，並透過 `INIT_LIST_HEAD` 初始化 head 。
### `q_free`
> commit [92f4f21](https://github.com/max890808/lab0-c/commit/92f4f2143ecc67d53f7203cf3536d0d6e0e93f89)
:::danger
Chris Beams 在 [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/) 一文 (繁體中文翻譯: [如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)) 提出，好的 Git commit message 應符合七條規則:
1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. 標題開頭要大寫
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how
你沒有依循上述規範，請詳讀作業說明，以 `git rebase -i` 改正。
:::
使用 `list_for_each_entry_safe` 走訪每一個結構體，並透過 `q_release_element` 釋放結構體所在的記憶體位置。
### `q_insert_head` `q_insert_tail`
> commit [8354a3d](https://github.com/max890808/lab0-c/commit/8354a3db4d6ac5ee2c13cf9b9bfeebb017e34d2b), commit [39a124d](https://github.com/max890808/lab0-c/commit/39a124d90c83c68c521190595be938fae0170403)
:::danger
Chris Beams 在 [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/) 一文 (繁體中文翻譯: [如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)) 提出，好的 Git commit message 應符合七條規則:
1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. 標題開頭要大寫
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how
你沒有依循上述規範，請詳讀作業說明，以 `git rebase -i` 改正。
:::
一開始在撰寫程式碼時使用 `strcpy` 處理複製字串的部份，在 `git commit` 時跳出 ==Dangerous function== 通知，經查閱[2024 年 Linux 核心設計/實作課程作業 —— lab0](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a)和 [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 後，將 `strcpy` 改用 `strncpy` 實作，但還是需要注意字串結尾字元 `'\0'` 的問題。
:::danger
The `strcpy` built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: `strcpy`, `strcat` and `strcmp`.
:::
```c
strncpy(str1,str2, BUFFER_SIZE); /* limit number of characters to be copied */
// We need to set the limit to BUFFER_SIZE, so that all characters in the buffer
// are set to '\0'. If the source buffer is longer than BUFFER_SIZE, all the
// '\0' characters will be overwritten and the copy will be truncated.
```
### `q_remove_head` `q_remove_tail`
> commit [64fe21b](64fe21b4ca087f3f0d2a4deb86f0cd7307878cd1), commit [d0df781](d0df781ae078f7589669bb910b2fbe3d916e271a)
:::danger
Chris Beams 在 [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/) 一文 (繁體中文翻譯: [如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)) 提出，好的 Git commit message 應符合七條規則:
1. 用一行空白行分隔標題與內容
2. 限制標題最多只有 50 字元
3. 標題開頭要大寫
4. 標題不以句點結尾
5. 以祈使句撰寫標題
6. 內文每行最多 72 字
7. 用內文解釋 what 以及 why vs. how
你沒有依循上述規範，請詳讀作業說明，以 `git rebase -i` 改正。
:::
使用 `list_first_entry` 或 `list_last_entry` 找到第一個結構體或最後一個結構體，之後使用 `list_del` 移除目標結構體。
### `q_delete_mid`
> commit [6cb8616](https://github.com/max890808/lab0-c/commit/6cb86163d19aa0424d5adf372ad7f70216d9ef25) commit [a9964f8](https://github.com/max890808/lab0-c/commit/a9964f84dc9cef40aa14e9cb10d4680ddaa3c17e)
使用快慢指標的方法找出中間的結構體，之後使用 `q_release_element` 將結構體刪除。
使用 List API 中的 `list_del` 精簡程式碼。
```diff
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
- struct list_head **indir = &head->next, *prev = NULL;
+ struct list_head **indir = &head->next;
for (struct list_head *fast = head->next;
fast != head && fast->next != head; fast = fast->next->next) {
- prev = *indir;
indir = &(*indir)->next;
}
- struct list_head *next = (*indir)->next;
+
element_t *mid_element = list_entry(*indir, element_t, list);
+ list_del(*indir);
q_release_element(mid_element);
- prev->next = next;
- next->prev = prev;
return true;
}
```
:::warning
TODO: 使用 List API，撰寫出更精簡的程式碼。
:::
### `q_delete_dup`
> commit [7477ca9](https://github.com/max890808/lab0-c/commit/7477ca916cab29bc6a7f473b428febb4fad58c63)
使用兩層迴圈實作，程式碼不精簡，應使用一個變數紀錄目前是否為最後一個相同值的結構體，並搭配 List API 撰寫更精簡的程式碼，之後還需要作修改。
### `q_swap`
> commit [d125b96](https://github.com/max890808/lab0-c/commit/d125b96d86513321d9c1bd8c60964c71cfa3c91a)
運用指標的指標和 `list_move` 實作
### `q_reverse`
> commit [05c88a6](https://github.com/max890808/lab0-c/commit/05c88a67d0f186f5824030628e1c25a584d1472f)
逐一走訪每個節點，將節點的 `prev` 和 `next` 交換。
### `q_reverseK`
> commit [9bc9849](https://github.com/max890808/lab0-c/commit/9bc9849b1765404e51a96ce4823fa39e28b5e0a7)
使用 `list_cut_position` 將要反轉的鏈結串列移動到新的空佇列上，接著使用 `q_reverse` 將鏈結串列作反轉，最後使用 `list_splice_init` 將反轉完的鏈結串列移動回原本的佇列。
### `q_sort`
> commit [16cf13f](https://github.com/max890808/lab0-c/commit/16cf13fd72dffe76833919b7e430da98e5d0f2f5)
使用 merge sort 實作，採用遞迴呼叫，搭配快慢指標將鏈結串列左右對半切分，直到分割成單一節點再使用 `merge` 合併成排序好的鏈結串列。
### `q_ascend` `q_descend`
> commit [2e0d815](https://github.com/max890808/lab0-c/commit/2e0d81545a04d6dc6852227628f857ab584f885a)
使用`list_for_each_safe` 走訪每個節點並判斷在此節點前是否存在比此節點較大或較小的節點，若存在則使用 `list_del` 和 `q_release_element` 刪除節點。
### `q_merge`
> commit [ab45163](https://github.com/max890808/lab0-c/commit/ab45163a6eeba7270d538000a1178c59cf7a505b)
先將所有佇列合併到第一個佇列，再使用 `q_sort` 排序。
目前在 github 上分數為95分，下一步將閱讀 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
## 論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
這篇論文提出了一種可以檢測程式執行時間是否為常數時間的工具 [dudect](https://github.com/oreparaz/dudect)，此技術是基於 ==leakage detection techniques==，不需要硬體模型，並且可以使用在 black-box testing。
接著作者說明如何實作 `TIMING LEAKAGE DETECTION`
*Step 1: Measure execution time*
使用兩種資料，分別為 fix-vs-random， fixed value 是為了要觸發 `corner-case`。
*Step 2: Apply post-processing*
對所收集的資料進行後處理，有2種方式
+ *Cropping:* Timing distributions 會往執行時間較長的方向偏移，可能是因為測量工具，或是主程式被作業系統或其它不相關的程式所中斷造成的，所以需要裁切過大的數值。
+ *Higher-order preprocessing:* 不懂。
*Step 3: Apply statistical test*
反駁 null hypothesis “the two timing distributions are equal”
+ *t-test [(Welch’s t-test)](https://en.wikipedia.org/wiki/Welch's_t-test)*
+ *Non-parametric tests*
### 實作改進 lab0-c
> commit [3010009](https://github.com/max890808/lab0-c/commit/30100091d94dd693d20163ee054082fefbfdda38)
在比較 [dudect](https://github.com/oreparaz/dudect) 原始程式碼和 [lab0-c](https://github.com/sysprog21/lab0-c) 後，發現 `lab0-c` 缺少 `percentile` 的部份，因此我在`lab0-c`中加入 `cmp` 、 `percentile` 和 `prepare_percentiles` 函式計算 `NUMBER_PERCENTILES(這裡為100)` 個閾值(thresholds)，接著透過 `update_statistics` 過濾執行時間超過閾值的資料，符合條件的資料會放入對應該閾值的 `t[crop_index]`，`max_test` 函式會從 `t[crop_index]` 計算最大的 t 值回傳。`report` 函式比較 t 值和 `t_threshold_bananas` `t_threshold_moderate` 判斷程式執行是否為常數時間。
在 [dudect](https://github.com/oreparaz/dudect) 的 `update_statistics` 函式中，有捨棄前十筆資料，在一開始改進 lab0-c 時我也只有將 `update_statistics` 函式中的 i 改成10，但在參考 [nosba0957](https://hackmd.io/@chucknos/linux2024-homework1#%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89) 同學的實作後發現這樣改是錯的，lab0-c 原先就有在 `measure` 函式中加入 `DROP_SIZE`，但這樣在 `differentiate` 函式計算執行時間時會導致開頭和結尾的地方都是 0。因此應該要在 `measure` 時紀錄全部的時間，在`update_statistics` 再將頭尾值刪除。執行上述改進後 `make test` 就能得到滿分了。
## 使用 Valgrind 排除記憶體錯誤
輸入 `make valgrind` 檢查是否發生記憶體錯誤
:::spoiler 測試結果
```
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
--- trace-05-ops 6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
--- trace-06-ops 6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
--- trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
--- trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
--- trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
:::
由測試結果可以可以發現目前的實作 valgrind 沒有發出任何的警告
## 研讀 Linux 核心原始程式碼 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並引入到 lab0-c 專案
### 引入 lib/list_sort.c 到 lab0-c
> commit [37715dc](https://github.com/max890808/lab0-c/commit/37715dc1bd93bf24a315167bbd7037a71f5d501f)
參考[ Risheng1128 ](https://hackmd.io/DVj7BfjzTcurWqQyC1HJaA?view#%E7%A0%94%E8%AE%80-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A2%BC-list_sortc)的作法，將 lib/list_sort.c 引入 lab0-c 專案
### 比較自己實作的 merge sort 和 Linux 核心程式碼
使用[ Risheng1128 ](https://hackmd.io/DVj7BfjzTcurWqQyC1HJaA?view#%E7%A0%94%E8%AE%80-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A2%BC-list_sortc)的方法，建立一個用來量測排序時間的測試檔 `trace-time-measure.cmd`
```
option fail 0
option malloc 0
new
ih RAND 100000
time
sort
time
```
| 資料總數 | `q_sort` 第一次 (s) | `q_sort` 第二次 (s) | `q_sort` 第三次 (s) | `q_sort` 平均 (s) |`list_sort` 第一次 (s) | `list_sort` 第二次 (s) | `list_sort` 第三次 (s) | `list_sort` 平均 (s) |
| ------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- |
| 100000 | 0.093 | 0.090 | 0.086 | 0.090 |0.093 | 0.082 | 0.089 | 0.088 |
| 200000 | 0.202 | 0.204 | 0.203 | 0.203 |0.199 | 0.199 | 0.204 | 0.200 |
| 300000 | 0.333 | 0.358 | 0.360 | 0.350 |0.322 | 0.325 | 0.322 | 0.323 |
| 400000 | 0.496 | 0.492 | 0.485 | 0.491 |0.448 | 0.454 | 0.388 | 0.430 |
| 500000 | 0.642 | 0.628 | 0.631 | 0.634 |0.563 | 0.578 | 0.583 | 0.575 |
從平均的結果可以看到 `list_sort` 的執行時間比 `q_sort` 短，但幅度不大。接著使用[ perf ](https://perf.wiki.kernel.org/index.php/Main_Page)工具進一步分析效能
輸入命令 `perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-time-measure.cmd`
→ 程式會執行 5 次，並且自動平均，其中每次測試的資料數都設定為 500000 ，以下為 `q_sort` 及 `list_sort` 執行的結果
`list_sort`
```shell
Performance counter stats for './qtest -f traces/trace-time-measure.cmd' (5 runs):
4981,3140 cache-misses # 62.649 % of all cache refs ( +- 0.41% )
7947,5959 cache-references ( +- 0.14% )
23,1425,8918 instructions # 0.60 insn per cycle ( +- 0.07% )
38,2314,6420 cycles ( +- 0.33% )
1.39582 +- 0.00995 seconds time elapsed ( +- 0.71% )
```
`q_sort`
```shell
Performance counter stats for './qtest -f traces/trace-time-measure.cmd' (5 runs):
5715,4304 cache-misses # 58.633 % of all cache refs ( +- 0.85% )
9665,6148 cache-references ( +- 0.37% )
23,8540,9426 instructions # 0.58 insn per cycle ( +- 0.06% )
41,2860,8108 cycles ( +- 0.23% )
1.4561 +- 0.0103 seconds time elapsed ( +- 0.71% )
```
| | `q_sort` | `list_sort` |
| ---------------- | ------------ | ------------ |
| cycles | 41,2860,8108 | 38,2314,6420 |
| instructions | 23,8540,9426 | 23,1425,8918 |
| cache-references | 9665,6148 | 7947,5959 |
| cache-misses | 5715,4304 | 4981,3140 |
| insn per cycle | 0.58 | 0.60 |
從[ perf ](https://perf.wiki.kernel.org/index.php/Main_Page)的分析結果可以看到， `list_sort` 發生 cache miss 的次數比 `q_sort` 來的少，可以對應到[ Linux 核心的鏈結串列排序](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-e) 裡提到的「用 bottom up 實作 merge sort 對 cache 較友善，可避免大量的 [cache trashing](https://en.wikipedia.org/wiki/Thrashing_(computer_science))」
## 確保 qtest 提供的 web 命令得以搭配上述佇列實作使用
Sign in with Wallet
Connect another wallet