2025q1 Homework1 (lab0)

contributed by < BrotherHong >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ 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

建立一個空的 queue
- 需要注意的點是在要 head 的記憶體空間時有可能會因為失敗而回傳 NULL ，這是我以前時常沒注意到的地方

if (head) {
    INIT_LIST_HEAD(head);
}

q_free

commit 4962106

釋放掉所有被 queue 使用到的記憶體
- 若 head 本身為 NULL 直接結束
- 使用 list.h 中的 list_for_each_entry_safe 將所有 element_t 用到的記憶體釋放掉
- 最後釋放掉 head 本身使用的記憶體

q_insert_head, q_insert_tail

commit f61b5c5, cf81496

插入一個 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)
- 使用 strdup 取代自行配置空間並用 strcpy 複製字串 (commit e0cff8c)

    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }

q_remove_head, q_remove_tail

commit a439e04, 71211e2

從 queue 的頭/尾移除一個 element ，並回傳被 remove 的 element
- 檢查 queue 是否為 NULL 或 empty
- 若 sp 為 non-NULL，將 value 複製至 sp
- 最後，從 queue 中 remove 該 element 並回傳

q_size

commit 60c86c8

計算 queue 中有多少個 element 存在
- 迭代過每個元素，同時使用 len 來記錄數量

q_delete_mid

commit 32977aa

刪除 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

將 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

把 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

把 queue 中的元素順序反轉
- 將每個節點(包含head)的 next 和 prev 分別指向 prev 和 next 指到的節點就能達成
- 這邊利用 list.h 中的 list_for_each_safe 會保存下一個節點的特性，直接對每個節點做上述的操作
- 最後還要對 head 也做一樣的操作，因為迴圈不包含它

q_reverseK

commit b0d2f49

對 queue 中的元素由前往後每 K 個一組並反轉其順序，不足 K 個則維持原樣
- 對 reverse 的想法：由後往前依序將每個元素插入尾端即能完成反轉
- 實作：建立一個迴圈
  - 從 queue 的前端開始找 K 個元素，並依照由後往前的順序移除並插入 queue 的尾端
  - 若遇到最後不足 K 個元素，則依照原順序移除並插入尾端
細節的處理方法
- 如何知道哪些元素尚未被操作過?
  - 一開始利用 last 紀錄尾端的元素
  - 若操作到 last 則代表已到尾端

q_sort

commit 18b65b8

依照 ascending/descending 排序 queue 的元素
- 以 merge sort 來實現
- 用 fast-slow pointer 找到中間點，把左半邊放到 list_left ，右半邊繼續放在 head
- 遞迴排序完左右半邊後合併
  - 有另外新增 q_merge_two 將兩個 list 合併

q_ascend q_descend

commit 0314025

刪除所有右方存在小於/大於自己的元素，使 queue 中的元素呈現單調遞增/遞減的樣子
- 假想 queue 為一個 stack，令前端為 stack 的底部，node 指向 stack 的 top
- 讓 node 從第一個元素持續往尾端前進，每次移動時就像是往 stack push 一個元素
- 在放入 stack 之前，持續檢查 top 的元素是否大於/小於自己，若成立則將元素 pop 出來，也就是將此元素 delete 掉
- 持續將元素放入 stack 並遵照上述操作直到所有元素都被操作過

q_merge

commit bbbce6f

將 k 個 sorted list 合併成一個 sorted list
- 透過 function 參數的 head 找出該鏈結串列所有節點所在的 queue_context
- 利用已寫好的 sub-function q_merge_two 一個一個合併到第一個 list 中

在 `qtest` 提供新的命令 `shuffle`

commit 7b9debb

實作 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`

執行測試程式得到以下結果

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

想要知道這個 shuffle 的結果是否是 Uniform distribution，所以進行以下假設檢定：

$H_{0}$ (虛無假設)：此 shuffle 的每一種方式的機率皆相同，遵照 Uniform distribution
$H_{1}$ (對立假設)：此 shuffle 的機率至少有一個不同

由以上程式計算已知 $χ^{2} = 16.27883646138338$
自由度 $d f = 23$ (總共 24 種排列方式且所有方式的機率總和為1)
令顯著水準 $α = 0.05$ ，並透過查表計算得到 $p = 0.8431 > 0.05$
結論：結果並不顯著，因此不拒絕虛無假設 $H_{0}$ ，換句話說，沒有證據說明此 shuffle 不是 Uniform distribution

研讀論文〈Dude, is my code constant time?〉

簡介

論文提出了一種方法可以檢測一支程式是否以常數時間 (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) 做洩漏檢測。

問題

為何對執行時間做洩漏檢測就能判斷是否是以常數時間來執行？
怎樣的實驗結果才算是時間洩漏 (timing leakage)？
時間洩漏 (timing leakage) 的定義是什麼？

實現方法可以分為三個步驟：

測量執行時間 (Measure execution time)
a. Classes definition
b. Cycle counter
c. Environmental condition
資料後處理 (Apply post-processing)
a. Cropping
b. Higher-order preprocessing
統計分析 (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 次，目前還不知到為何會這樣設定
  
  最終結果?
  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

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