# 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 %}

## 開發環境

$ 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` ，這是我以前時常沒注意到的地方

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` 用到的空間先釋放掉再回傳
* 若在配置記憶體給字串時失敗，在程式結束會顯示尚有記憶體空間未被釋放

    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))

    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` 會指向我們要找的點

    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

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`

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)得到以下結果

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`

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

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` 方法

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`

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

int open(char *filename, int flags, mode_t mode);

* `close`

#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

#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*