# 2025q1 Homework1 (lab0)
**contributed by `<hahaB7>`**

{%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):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz
    CPU family:           6
    Model:                165
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   16%
    CPU max MHz:          5000.0000
    CPU min MHz:          800.0000
    BogoMIPS:             5199.98
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge m
                          ca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 s
                          s ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc 
                          art arch_perfmon pebs bts rep_good nopl xtopology nons
                          top_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor 
                          ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid 
                          sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer a
                          es xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpu
                          id_fault epb ssbd ibrs ibpb stibp ibrs_enhanced tpr_sh
                          adow flexpriority ept vpid ept_ad fsgsbase tsc_adjust 
                          bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap c
                          lflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dthe
                          rm ida arat pln pts hwp hwp_notify hwp_act_window hwp_
                          epp vnmi pku ospke md_clear flush_l1d arch_capabilitie
                          s
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    192 KiB (6 instances)
  L1i:                    192 KiB (6 instances)
  L2:                     1.5 MiB (6 instances)
  L3:                     12 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-11
Vulnerabilities:          
  Gather data sampling:   Mitigation; Microcode
  Itlb multihit:          KVM: Mitigation: VMX disabled
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Mitigation; Clear CPU buffers; SMT vulnerable
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; Enhanced IBRS
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prct
                          l
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointe
                          r sanitization
  Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditiona
                          l; RSB filling; PBRSB-eIBRS SW sequence; BHI SW loop, 
                          KVM SW loop
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Not affected

## **實作指定佇列操作**
### `q_new`
> commit [30eaeb8](https://github.com/hahaB7/lab0-c/commit/30eaeb8daedc022864f0e384b1d68693ebbd240c)

在實作 `q_new` 時，我對於鏈結列表的初始化方式有些疑問。在 Linux Kernel 的 `list.h` 中，提供了兩種方式來初始化鏈結列表，分別是 `INIT_LIST_HEAD` 和 `LIST_HEAD`。然而，觀察去年作業的實作方式，發現大多數人選擇使用 `INIT_LIST_HEAD` 來進行初始化。為了理解其中的原因，我進一步分析了這兩種方法的區別，並整理了對應的程式碼如下。

**`LIST_HEAD`**

在 `q_new` 函式內部，若使用 `LIST_HEAD` 來初始化鏈結列表，將會導致區域變數作用域的問題，進而引發未定義行為（Undefined Behavior）。

#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

struct list_head *q_new()
{    
    return &LIST_HEAD(head)
}

1. `head` 是區域變數
由於 `LIST_HEAD` 只是定義了一個區域變數 `head`，所以當 `q_new` 函式執行結束後，`head` 變數將會被釋放，導致回傳的指標 `&LIST_HEAD(head)` 指向已無效的記憶體空間，進而造成程式錯誤或未定義行為。
2. `LIST_HEAD` 無法用於動態分配的變數
`LIST_HEAD` 只能在編譯時定義變數，因此它無法用於 `malloc` 動態分配的記憶體，而 `q_new` 需要回傳一個可長期使用的鏈結串列，因此 `LIST_HEAD` 無法滿足需求，所以最終使用`INIT_LIST_HEAD`實作。

### `q_free`
> commit [30eaeb8](https://github.com/hahaB7/lab0-c/commit/30eaeb8daedc022864f0e384b1d68693ebbd240c)

### `q_insert_head` / `q_insert_tail`
> commit [9a2a3ff](https://github.com/hahaB7/lab0-c/commit/9a2a3ff337292b988c562c15cdb150932ea74a85)

實作這兩個函式時，需要配置新的記憶體區段給 `element_t` 以及其成員 `value` 使用，並且使用 `strncpy` 來複製的字串到指定位置，這邊只所以使用 `strncpy` 而非 `strcpy` 是基於以下分析。

1. **`strcpy` 的問題**
在字串處理時，`strncpy` 相較於 `strcpy` 更為安全，主要是因為 `strcpy` 不會檢查目標緩衝區的大小，可能導致緩衝區溢位，進而覆蓋鄰近的記憶體，造成未定義行為或安全性漏洞。
2. **`strncpy` 的優勢**
`strncpy` 允許指定最大複製長度，因此可以防止目標緩衝區溢位，且如果來源字串長度小於指定長度，strncpy 會用 ``'\0'`` 填滿剩餘空間

**`q_insert_tail`**

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head || !s) {
        return false;
    }
    return q_insert_head(head->prev, s);
}

`q_insert_tail` 的實作重用 `q_insert_head`，因兩者在初始化 `element_t` 的過程完全一致，操作上的差異只在插入位置，故對於 `q_insert_tail` 則傳入 `head->prev` 以插入佇列尾端。

### `q_remove_head` / `q_remove_tail`
> commit [c053470](https://github.com/hahaB7/lab0-c/commit/c053470c25aa171a543a96d2a08ace693463a0bd)

### `q_size`
> commit [e213e16](https://github.com/hahaB7/lab0-c/commit/e213e16cc288f82b916b0f64a6649ff584316468)

### `q_delete_mid`
> commit [d7ea727](https://github.com/hahaB7/lab0-c/commit/d7ea72725853246ba7045268e84085a2b71b982d)

### `q_delete_dup`
> commit [d537d7c](https://github.com/hahaB7/lab0-c/commit/d537d7c0b2e7e3536607456337175b2901277f70)

### `q_swap`
> commit [5c07ba0](https://github.com/hahaB7/lab0-c/commit/5c07ba0e17fef67693b8733f1c4f29e3929d2313)

### `q_reverse` / `q_reverseK`
> commit [7ed08d4](https://github.com/hahaB7/lab0-c/commit/7ed08d4748960189733263cd46f3e49f97de892d)

### `q_ascend` / `q_descend`
> commit [831d138](https://github.com/hahaB7/lab0-c/commit/831d13870fa28dc31d574e1049a0fcd72529cedc)

### `q_sort`
> commit [f9c61ca](https://github.com/hahaB7/lab0-c/commit/f9c61ca46b8696d954a9942875e2918c1f9d3102)

modify
> commit [2f1c7a0](https://github.com/hahaB7/lab0-c/commit/2f1c7a0e7ee8b03e6145d60093762425a0264138)

### `q_merge`
> commit [35f9038](https://github.com/hahaB7/lab0-c/commit/35f9038b4c70367356b8bb925e29864d6df5b54b)

## **Valgrind + 自動測試程式**
> 待完成
## **整合網頁伺服器**
> 待完成
## 實作 `shuffle` 命令

[reference](https://hackmd.io/@alanjian85/lab0-2023#Valgrind-%E8%88%87-Address-Sanitizer-%E8%A8%98%E6%86%B6%E9%AB%94%E6%AA%A2%E6%9F%A5)

## **研讀論文〈Dude, is my code constant time?〉**
### `make test` 測試失敗的問題分析

在執行所有指定的佇列操作後，運行 `make test` 命令時，我發現最後一項測試無法通過。
主要原因是 `q_insert_head / tail` 及 `q_remove_head / tail` 這些函式未能通過「是否能夠在常數時間內執行」的測試。問題出在 `dudect` 功能尚未完善。

在實際實作前，我參考了過去學長的[做法](https://hackmd.io/@yehsudo/linux2024-homework1#%E9%96%B1%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89)，我發現許多人都採用此方法。然而，當我深入分析這份程式碼時，發現了一個重大問題。

### 觀察其主要新增的函式

首先，觀察 `percentile` 以及 `prepare_percentiles` 這兩個函式的實作：

static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
  size_t array_position = (size_t)((double)size * (double)which);
  assert(array_position < size);
  return a_sorted[array_position];
}

static void prepare_percentiles(dudect_ctx_t *ctx) {
  qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
  for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
    ctx->percentiles[i] = percentile(
        ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
        ctx->config->number_measurements);
  }
}

以及它的呼叫方式

static bool doit(int mode)
{
    int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
    uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
    uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));


    if (!before_ticks || !after_ticks || !exec_times || !classes ||
        !input_data) {
        die();
    }

    prepare_inputs(input_data, classes);

    bool ret = measure(before_ticks, after_ticks, input_data, mode);
    differentiate(exec_times, before_ticks, after_ticks);
    prepare_percentiles(exec_times);
    update_statistics(exec_times, classes);
    ret &= report();

    free(before_ticks);
    free(after_ticks);
    free(exec_times);
    free(classes);
    free(input_data);

    return ret;
}

### 問題分析

問題出在 `update_statistics`，該函式根據輸入的 `exec_times` 及對應的類別（隨機 vs. 固定）來動態更新不同類別的統計數據。

`exec_times` 中的每個值都是透過其索引，對應到 `classes` 中相同索引的類別。然而，在執行 `update_statistics` 之前，`exec_times` 會先經過 `prepare_percentiles` 處理，而 `prepare_percentiles` 內部會對 `exec_times` 進行排序。
這導致 `exec_times` 的索引順序發生改變，使得 `update_statistics` 在更新統計數據時對應錯誤，進而導致錯誤的分析結果。

### 進一步分析

為什麼排序後的 `exec_times` 反而可以通過常數時間檢測呢？

這與 `classes` 的隨機性有關。假設 `exec_times` 是某種測試過程中獲得的執行時間序列，其中每個執行時間對應到一個類別（隨機或固定）。然而，在 `prepare_percentiles` 內部，`exec_times` 被排序，這改變了執行時間與其原始類別之間的關聯。

補充：問題
如果將一串排序過後的數列中的每一項都隨機分到兩個類別中的其中一個，在完成分配後，兩個類別的平均數會有什麼現象？

>By ChatGPT
>1. **兩類的平均數接近整體平均數**
>- 由於數列是排序過的，但分配是**隨機**的，兩類的數值分布仍然會趨向於數列的整體分布。因此，兩類的平均數**大致**會接近整體數列的平均數。
>2. **兩類的平均數波動較大**（相較於原始無序數列
>- 由於數列是排序後的，隨機分配可能會導致某一類中較多極端值（最大或最小值），造成類別間的平均數有較大的波動。特別是數列長度較短時，這種波動會更明顯
>3. **數列極端值影響較大**
>- 若數列包含極端值（例如長尾分布），隨機分配可能導致其中一類獲得較多極端值，使其平均數偏離整體平均數更明顯
>4. **當數列長度夠長時，兩類平均數趨於相等**
>- 根據**大數法則**，當數列長度夠大，隨機分配後，兩類中的數據分布會更接近整體數列的分布，因此兩類的平均數會更加接近整體數列的平均數，平均數之間的差距會減小。

### 改善

綜上所述，我目前參考[其他版本](https://hackmd.io/@yanjiew/linux2023q1-lab0#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89)並對其進行修改，但因我對於常數時間檢驗的理解與其實作方式有所不同。我認為，檢驗 `q_insert_head / tail` 以及 `q_remove_head / tail` 是否符合常數時間執行的核心在於 **佇列長度變化時，執行時間是否仍能維持恆定**。也就是說，當佇列長度發生改變時，這些操作是否仍能在固定的時間內完成。

然而，其實作方式則是透過 **檢測在相同長度的佇列上，對相同長度的隨機字串與固定字串的操作是否能以常數時間執行**。該方法的核心在於：比較固定輸入與隨機輸入的執行時間是否存在顯著差異，來判斷演算法是否符合常數時間特性。

此外，其文中也提到，若固定字串的長度與隨機字串不同，則檢測結果將顯示該操作並非常數時間執行，這進一步證明了輸入的長度確實會影響執行時間。因此，在調整為我的測試目標時，也需特別注意字串長度需保持固定，以免混淆真正的測試重點——**佇列長度對執行時間的影響**。

### 與原實作差異分析

在這個分析中，我比較了兩種不同的方式來設定佇列長度，並在測量CPU週期進行佇列操作時進行比較。這兩種方法分別對應原版本及改善版本：

1. **預先準備的佇列**：在測量開始之前，佇列會先被初始化為隨機確定的長度。
2. **即時初始化**：佇列長度會在進行測量操作之前動態確定並填充。

目標是了解佇列準備方法是否會影響CPU週期測量的準確性和一致性。

> By ChapGPT
> #### 1. 預先準備的佇列
> - 由於佇列在測量之前已經填充了隨機長度，因此唯一被計時的操作是單一的插入或移除操作。
> - 減少了測量中的變異性，因為佇列在計時開始前已經處於預期狀態。
> - 確保 CPU 週期的測量主要集中於所要測量的操作，最小化了記憶體分配或列表重構的影響。
>
> #### 2. 即時初始化
> - 佇列長度在測量之前動態確定並填充。
> - 這會在計時開始之前引入額外的操作，可能會導致不一致性。
> - 測量的 CPU 週期不僅包括主要操作（插入/移除），還可能受到任何來自動態調整佇列大小的開銷。
>
> #### 單一操作時間的觀察與理論影響
> - **使用預先準備的佇列**時，測量僅專注於目標操作，從而更清楚地評估佇列長度如何影響執行時間。
> - **使用即時初始化**時，測量中會受到額外處理的影響，這使得更難單獨分析佇列長度對操作執行時間的影響。

雖然預先準備佇列可以使測試結果正確，但卻會造成總測試時間變得非常長，約20分鐘，相對原版本非常慢，尚未對原因進行詳細分析，待補

### 改良原版本
> commit [5892896](https://github.com/hahaB7/lab0-c/commit/589289680eeb1fb9286069561abb908bd4f4f5d1)

本地端測試可通過，但上傳 github 無法成功通過，或許是因為 `usleep` 的參數是根據經驗設定，這不是個好方案。
[參考](https://hackmd.io/@alanjian85/lab0-2023#%E6%94%B9%E9%80%B2-dudect-%E5%AF%A6%E4%BD%9C)

## 研讀 Linux 核心原始程式碼的 lib/list_sort.c
[參考](https://hackmd.io/@chiangkd/BJBB9rnzq)
[參考](https://hackmd.io/@weihsinyeh/ry2RWmNTT#%E7%A0%94%E8%AE%80-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC%E7%9A%84-liblist_sortc)
先根據目前閱讀紀錄下一個推論

討論三種合併排序的變體，分別是
1. Top Down Merge sort
2. Bottom Up Merge sort
3. Queue-Mergesort

對於 1 與 3兩者具有會具有最少的比較次數，而 2 對 cache 最友善。
而 Linux kernel 的做法是對 Bottom Up Merge sort 的合併策略進行改良使其可以具有更少的比較次數(2:1)