# 2025q1 Homework1 (lab0)
contributed by < `BrotherHong` >
## Reviewed by BennyWang1007
1. 在 `q_insert_head`、`q_insert_tail` 中，修正未完全釋放記憶體的 commit，考慮呼叫 `free()` 的條件是 `!e`，也就是 `e` 為 NULL，此時沒有必要呼叫 `free()`。\
(根據 ISO C 標準 (ISO/IEC 9899:1999, §7.20.3.2), If ptr is a null pointer, no action occurs.)
2. 在 `q_sort` 中，判斷選擇哪個鏈結串列時，可以考慮不要使用乘法。
3. 筆記和 commit message 寫得很詳盡，很不錯。
4. 缺乏的部分如 tiny web server 等，有空可以慢慢補上。
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 13th Gen Intel(R) Core(TM) i7-13620H
CPU family: 6
Model: 186
Thread(s) per core: 2
Core(s) per socket: 10
Socket(s): 1
Stepping: 2
CPU(s) scaling MHz: 10%
CPU max MHz: 4900.0000
CPU min MHz: 400.0000
BogoMIPS: 5836.80
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 416 KiB (10 instances)
L1i: 448 KiB (10 instances)
L2: 9.5 MiB (7 instances)
L3: 24 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
```
## 針對佇列操作的程式碼實作
### q_new
> commit [726f122](https://github.com/BrotherHong/lab0-c/commit/726f1229caa88983711ba474ba521dd417ff8c21)
* 建立一個空的 queue
* 需要注意的點是在要 `head` 的記憶體空間時有可能會因為失敗而回傳 `NULL` ，這是我以前時常沒注意到的地方
```c
if (head) {
INIT_LIST_HEAD(head);
}
```
### q_free
> commit [4962106](https://github.com/BrotherHong/lab0-c/commit/4962106b2728de6342df467d3a47a530f86ffb4a)
* 釋放掉所有被 `queue` 使用到的記憶體
* 若 `head` 本身為 `NULL` 直接結束
* 使用 `list.h` 中的 `list_for_each_entry_safe` 將所有 `element_t` 用到的記憶體釋放掉
* 最後釋放掉 `head` 本身使用的記憶體
### q_insert_head, q_insert_tail
> commit [f61b5c5](https://github.com/BrotherHong/lab0-c/commit/f61b5c5cffc6acca35962b57730f74d79f38fa79), [cf81496](https://github.com/BrotherHong/lab0-c/commit/cf81496d9fffba981e82ea87071ed470e2237279)
* 插入一個 `element` 到 `queue` 的頭/尾
* 若 `head` 本身為 `NULL` 直接回傳 `false`
* 配置記憶體給 `element` 用，並初始化 `list`
* 若配置失敗則回傳 `false`
* 配置記憶體給字串 `value` 用
* 若配置失敗則**先釋放** `element` 的記憶體，再回傳 `false`
* 若以上記憶體配置都成功，將字串複製進 `value` 中
* 最後將 `list` 放入 `queue` 完成插入操作
* 程式碼片段：配置記憶體給字串，並將字串複製進 `value`
* 此份程式碼沒有考慮到要先將 `element` 用到的空間先釋放掉再回傳
* 若在配置記憶體給字串時失敗，在程式結束會顯示尚有記憶體空間未被釋放
```c
size_t len = strlen(s);
if (!(e->value = malloc(sizeof(char) * (len + 1))))
return false;
strncpy(e->value, s, len);
e->value[len] = '\0';
```
* 之後重新把 `insert` 操作重寫並簡化了字串複製操作
* 修正未完全釋放記憶體 (commit [a173291](https://github.com/BrotherHong/lab0-c/commit/a173291fade44ae2f04e57efebe7a5664a229546))
* 使用 `strdup` 取代自行配置空間並用 `strcpy` 複製字串 (commit [e0cff8c](https://github.com/BrotherHong/lab0-c/commit/e0cff8cd97fb793dbc6a0dd585891d6af7aa1e03))
```c
e->value = strdup(s);
if (!e->value) {
free(e);
return false;
}
```
### q_remove_head, q_remove_tail
> commit [a439e04](https://github.com/BrotherHong/lab0-c/commit/a439e043243123bb993830d005d6585917a0dc07), [71211e2](https://github.com/BrotherHong/lab0-c/commit/71211e26d6c07ba1434e21dca606f4e5f6e3df21)
* 從 `queue` 的頭/尾移除一個 `element` ，並回傳被 **remove** 的 `element`
* 檢查 `queue` 是否為 `NULL` 或 `empty`
* 若 `sp` 為 `non-NULL`，將 `value` 複製至 `sp`
* 最後，從 `queue` 中 **remove** 該 `element` 並回傳
### q_size
> commit [60c86c8](https://github.com/BrotherHong/lab0-c/commit/60c86c828430dcd9dc0401b067b165fc3af03637)
* 計算 `queue` 中有多少個 `element` 存在
* 迭代過每個元素，同時使用 `len` 來記錄數量
### q_delete_mid
> commit [32977aa](https://github.com/BrotherHong/lab0-c/commit/32977aa703ba464978bd6c23bce00fbab742e366)
* 刪除 `queue` 中位於中間的 `element`
* 更精確地說，若 `queue` 的長度為 `n` 則刪除第 `⌊n / 2⌋` 個 `element` (**0-based indexing**)
* 換個想法，對於奇數數量元素的 `queue` 要刪除的點就是中間那個；偶數數量則是切半後右半邊最靠近中間的點
* 奇數例如：`0 1 2 3 4` 刪除的是 `2`
* 偶數例如：`0 1 2 3 4 5` 刪除的是 `3`
* 這邊使用的方式是利用雙向鏈結串列的好處，使用 `front` 和 `back` 指標分別由前和後同時往中間移動，直到兩者指向**同個元素**或**相鄰**為止
* 找到中間的元素後，將它從 `queue` 中移除並釋放與其相關的記憶體
* 程式碼片段：尋找中間的元素
* `while` 迴圈結束後，`back` 會指向我們要找的點
```c
struct list_head *front = head->next, *back = head->prev;
while (front != back && front->next != back) {
front = front->next;
back = back->prev;
}
```
### q_delete_dup
> commit [576aa75](https://github.com/BrotherHong/lab0-c/commit/576aa75a34faff172b1edd4d4e17bce7ee761adc)
* 將 `queue` 中所有連續且 `value` 相同的元素全部刪除
* 例如：`1 2 2 4 3 4 4 4 5` 會變成 `1 4 3 5`
* 首先建立一個 local 的 `list` `tmp_head`，用來記錄要保留的元素
* 再來從 `queue` 的前端往後找 `value` 相同的元素直到不相同為止
* 令 `node` 指向第一個元素，並使用 `last` 指標來記錄連續相同元素的尾端**的下一個元素**
* 例如：`1 1 1 2(<last) 3`
* 若 `node->next == last` 代表沒有重複發生
* 將 `node` 放入 `tmp_head`
* 若 `node->next != last` 代表有連續重複的元素
* 持續從前端刪除元素直到遇到 `last`
* 當 `head` 為空時表示已經將所有連續重複的元素都移除並存在 `tmp_head` 裡面，最後利用 `list_splice` 把所有元素移至 `head` 完成操作
### q_swap
> commit [03e540e](https://github.com/BrotherHong/lab0-c/commit/03e540e7dc0c389871aff6687a4ea15cf805edec)
* 把 `queue` 中由前往後兩兩相鄰的元素不重疊地互換位置，多餘的則維持原樣
* 比如說，`1 2 3 4 5 6 7` 經過操作後會變成 `2 1 4 3 6 5 7`
* 這邊使用指標的指標 `node` 來指向**指向**兩兩相鄰的第一個節點
* 後來想想使用指標也能有同樣效果，也能少宣告一個指標變數
* 用 `node1` 和 `node2` 分別表示相鄰的左和右節點
* 將 `node1` 用 `list_del` 把它從 `queue` 中移除，再把它插入在 `node2` 後面
* 如此就完成一組的交換，下一組的左節點即是目前 `node1` 的下一個節點
* 重複以上操作即可完成 `q_swap` 的要求
### q_reverse
> commit [6853cdb](https://github.com/BrotherHong/lab0-c/commit/6853cdb5cf4bc0280d67855b17f305a720e5dce2)
* 把 `queue` 中的元素順序反轉
* 將每個節點(包含`head`)的 `next` 和 `prev` 分別指向 `prev` 和 `next` 指到的節點就能達成
* 這邊利用 `list.h` 中的 `list_for_each_safe` 會保存下一個節點的特性，直接對每個節點做上述的操作
* 最後還要對 `head` 也做一樣的操作，因為迴圈不包含它
### q_reverseK
> commit [b0d2f49](https://github.com/BrotherHong/lab0-c/commit/b0d2f49f2fcec84ac06b995e472a13d121693b8a)
* 對 `queue` 中的元素由前往後每 `K` 個一組並反轉其順序，不足 `K` 個則維持原樣
* 對 `reverse` 的想法：由後往前依序將每個元素插入尾端即能完成反轉
* 實作：建立一個迴圈
* 從 `queue` 的前端開始找 `K` 個元素，並依照由後往前的順序移除並插入 `queue` 的尾端
* 若遇到最後不足 `K` 個元素，則依照原順序移除並插入尾端
* 細節的處理方法
* 如何知道哪些元素尚未被操作過?
* 一開始利用 `last` 紀錄尾端的元素
* 若操作到 `last` 則代表已到尾端
### q_sort
> commit [18b65b8](https://github.com/BrotherHong/lab0-c/commit/18b65b82d305f84761a853d68abe1d4f11355495)
* 依照 ascending/descending 排序 `queue` 的元素
* 以 `merge sort` 來實現
* 用 `fast-slow pointer` 找到中間點，把左半邊放到 `list_left` ，右半邊繼續放在 `head`
* 遞迴排序完左右半邊後合併
* 有另外新增 `q_merge_two` 將兩個 `list` 合併
### q_ascend q_descend
> commit [0314025](https://github.com/BrotherHong/lab0-c/commit/0314025106b138c4bde6e31e7b6a480924e9a62d)
* 刪除所有**右方存在小於/大於自己**的元素，使 `queue` 中的元素呈現單調**遞增/遞減**的樣子
* 假想 `queue` 為一個 stack，令前端為 stack 的底部，`node` 指向 stack 的 top
* 讓 `node` 從第一個元素持續往尾端前進，每次移動時就像是往 stack push 一個元素
* 在放入 stack 之前，持續檢查 top 的元素是否**大於/小於**自己，若成立則將元素 pop 出來，也就是將此元素 delete 掉
* 持續將元素放入 stack 並遵照上述操作直到所有元素都被操作過
### q_merge
> commit [bbbce6f](https://github.com/BrotherHong/lab0-c/commit/bbbce6fe3d2232ac9a9160ddb05fa4fd62653476)
* 將 `k` 個 `sorted list` 合併成一個 `sorted list`
* 透過 function 參數的 `head` 找出該鏈結串列所有節點所在的 `queue_context`
* 利用已寫好的 sub-function `q_merge_two` 一個一個合併到第一個 `list` 中
## 在 `qtest` 提供新的命令 `shuffle`
> commit [7b9debb](https://github.com/BrotherHong/lab0-c/commit/7b9debb7a6c1e409cca06b053f2c311443b51502)
### 實作 Fisher-Yates shuffle
```c
void q_shuffle(struct list_head *head)
{
int len = q_size(head);
struct list_head *new = head->prev;
while (len) {
int random = rand() % len;
struct list_head *old = head->next;
while (random--) {
old = old->next;
}
/* Swap value */
element_t *old_entry = list_entry(old, element_t, list);
element_t *new_entry = list_entry(new, element_t, list);
char *tmp = old_entry->value;
old_entry->value = new_entry->value;
new_entry->value = tmp;
len--;
new = new->prev;
}
}
```
### 新增指令到 `qtest`
```c
ADD_COMMAND(shuffle, "Shuffle the nodes of the queue", "");
```
### 統計方法驗證 `shuffle`
執行[測試程式](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d#%E6%B8%AC%E8%A9%A6%E7%A8%8B%E5%BC%8F)得到以下結果
```sh
Expectation: 41666
Observation: {'1234': 41553, '1243': 41674, '1324': 41688, '1342': 41988, '1423': 41841, '1432': 41575, '2134': 41667, '2143': 41670, '2314': 41819, '2341': 41410, '2413': 41431, '2431': 41861, '3124': 41531, '3142': 41824, '3214': 41577, '3241': 41697, '3412': 41595, '3421': 41622, '4123': 41437, '4132': 41476, '4213': 41477, '4231': 41821, '4312': 42022, '4321': 41744}
chi square sum: 16.27883646138338
```
使用 `matplotlib` 繪製成圖表如下
想要知道這個 shuffle 的結果是否是 Uniform distribution，所以進行以下假設檢定：
* $H_0$ (虛無假設)：此 shuffle 的每一種方式的機率皆相同，遵照 Uniform distribution
* $H_1$ (對立假設)：此 shuffle 的機率至少有一個不同
1. 由以上程式計算已知 $\chi^2 = 16.27883646138338$
2. 自由度 $df=23$ (總共 24 種排列方式且所有方式的機率總和為1)
3. 令**顯著水準** $\alpha = 0.05$，並透過[查表計算](https://datatab.net/tutorial/chi-square-distribution)得到 $p=0.8431 \gt 0.05$
4. 結論：結果並不顯著，因此不拒絕虛無假設 $H_0$ ，換句話說，沒有證據說明此 shuffle 不是 Uniform distribution
## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
### 簡介
論文提出了一種方法可以檢測一支程式是否以**常數時間** (constant time) 執行，並且此種方法是基於**洩漏檢測** (leakage detection) 的方式，有別於以往許多方法需要以模擬硬體的方式來實現 (如：`ctgrind`，`ctverif`)。
### 實現方法：`TIMING LEAKAGE DETECTION`
> Our approach in a nutshell is to perform a leakage detection test on the execution time.
簡單來說，論文使用的方法就是對程式的**執行時間** (execution time) 做洩漏檢測。
>[!Note]問題 :thinking_face:
>為何對執行時間做洩漏檢測就能判斷是否是以常數時間來執行？
>怎樣的實驗結果才算是時間洩漏 (timing leakage)？
>時間洩漏 (timing leakage) 的定義是什麼？
實現方法可以分為三個步驟：
1. 測量執行時間 (Measure execution time)
a. Classes definition
b. Cycle counter
c. Environmental condition
2. 資料後處理 (Apply post-processing)
a. Cropping
b. Higher-order preprocessing
3. 統計分析 (Apply statistical test)
a. t-test
b. Non-parametric tests
> TODO...
### `qtest` 的 simulation 實作
主要執行測試的起點在 `fixture.c` 中的 `test_const` 方法
* 一些 macro 的值如下
* `TEST_TRIES = 10`
* `ENOUGH_MEASURE = 10000`
* `N_MEASURES = 150`
* `DROP_SIZE = 20`
```c
static bool test_const(char *text, int mode)
{
bool result = false;
t = malloc(sizeof(t_context_t));
for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
init_once();
for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
++i)
result = doit(mode);
printf("\033[A\033[2K\033[A\033[2K");
if (result)
break;
}
free(t);
return result;
}
```
* 各個變數用途
* `mode` : 分辨測試的操作是哪一個 (insert/remove head/tail)
* `t` : 用來儲存 t-test 所需要的資料
* 每一次 TEST_TRY 都會在 `init_once` 被初始化
* `result` : 紀錄測試結果是否為 constant time
* 運作流程
* `test_const` 提供了 `TEST_TRIES` 次機會來檢測該指定操作的執行時間是否是 constant time
* 每一次機會都會在 `doit` 這個方法中測量(measure)並檢驗結果**數次**，將最終(?)結果存在 `result`
>這邊的數次是寫成 `ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1` 次，直接展開的話會是 `10000 - (150 / 20 * 2) + 1 = 9986` 次，目前還不知到為何會這樣設定 :thinking_face:
>[!Note]最終結果?
>`result = doit(mode);` 這行程式碼表示只要迴圈最後一圈的結果為 `true` 就好了？
* 只要有一次檢驗結果為 `true` 即代表此操作程式**可能是**常數執行時間
>在這邊只要至少有一次過， `make test` 就會讓你拿到分
* `fixture.c` : **doit** 方法
* **prepare_inputs**：預處理 input 資料
* **measure**：實際測量執行時間，並將執行前後的 `cpu cycles` 分別存在 `before_ticks` 和 `after_ticks`
* **differentiate**：計算 `before_ticks` 和 `after_ticks` 的差來得到執行時間 `exec_times`
* **update_statistics**：使用測量出來的 `execc_times` 更新統計分析所需的相關參數
* **report**：根據統計分析回報此次檢驗是否可能是 constant time
```c
static bool doit(int mode)
{
/* Allocate memory */
// ...
prepare_inputs(input_data, classes);
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
ret &= report();
/* Deallocate memory */
// ...
return ret;
}
```
* `constant.c` : `measure` 方法
```c
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
char *s = get_random_string();
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
int before_size = q_size(l);
before_ticks[i] = cpucycles();
dut_insert_head(s, 1);
after_ticks[i] = cpucycles();
int after_size = q_size(l);
dut_free();
if (before_size != after_size - 1)
return false;
}
```
## 研讀並嘗試引入 `lib/list_sort.c` 到 `lab0-c`
## Rio 套件
> [book](https://csapp.cs.cmu.edu/2e/ch10-preview.pdf)
### Unix I/O
> A Unix file is a sequence of $m$ bytes:
> $$
> B_0, B_1, \dots, B_k, \dots, B_{m-1}
> $$
所有 I/O 裝置，像是網路、硬碟、終端機都被當程式一個 file，所有對裝置的 input/output，都是透過對檔案做 reading/writing 來達成的。
* `open`
```c
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int open(char *filename, int flags, mode_t mode);
```
* `close`
```c
#include <unistd.h>
int close(int fd);
```
* `read` `write`
回傳值為實際讀取/寫入 bytes 數量
* 有幾種情況會使回傳值與要求的數量不同 (*short counts*)
* 讀到 EOF
* 從終端機讀取時，一次只會讀一行
* 讀取和寫入 networking socket 時 (內部 buffering 限制、網路延遲過長)
> size_t 被定義為 unsigned int
> ssize_t 是 signed size ，被定義為 int
```c
#include <unistd.h>
ssize_t read(int fd, void *buf, size_t n);
ssize_t write(int fd, const void *buf, size_t n);
```
如果想要建造一個可依賴的網路應用程式 (如：Web servers)，就必須處理好每次 `read` `write` 遇到的 *short counts* 。
### Rio (Robust I/O) Package
可以自動化解決 *short counts* 的問題
RIO 提供兩種 functions
* *Unbuffered input and output functions*
* 可直接在 memory 和 file 之間轉換資料
* `rio_readn`、`rio_writen`
* *Buffered input functions*
Sign in with Wallet
Connect another wallet