# 2026q1 Homework1 (warmup)
contributed by < `laneser` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 探討〈資訊科技詞彙翻譯〉
### render 的語意與 Linux 核心中的使用場景
- [ ] "render" 在電腦圖學語境中為何應強調「如實呈現」？「渲染」一詞喪失什麼關鍵意涵？在 Linux 核心原始程式碼中，"render" 出現在哪些場景、語境又有哪些？翻閱詞典 (善用學校圖書館) 並考據詞源
[〈資訊科技詞彙翻譯〉](https://hackmd.io/@sysprog/it-vocabulary)已說明 render 的核心語意是「如實呈現」，而「渲染」帶有「誇大」意涵，與 rendering 的精確計算本質相悖，「算繪」更為貼切。以下針對 Linux 核心原始碼進行實際搜尋驗證。
#### Linux 核心原始碼中的搜尋結果
搜索 Linux 核心原始碼（v6.19），"render" 出現在 340 個檔案中。逐一檢視每個檔案的上下文後，歸納為以下語境：
| 語境 | 檔案數 | 代表檔案 | 用法 |
|------|--------|---------|------|
| GPU 算繪引擎 | 255 | [`drivers/gpu/drm/i915/intel_uncore.c`](https://github.com/torvalds/linux/blob/v6.19/drivers/gpu/drm/i915/intel_uncore.c) | `FORCEWAKE_RENDER`——算繪引擎電源域管理 |
| 使之成為某狀態 | 41 | [`drivers/media/usb/pvrusb2/pvrusb2-hdw.c`](https://github.com/torvalds/linux/blob/v6.19/drivers/media/usb/pvrusb2/pvrusb2-hdw.c)、[`drivers/input/mouse/alps.c`](https://github.com/torvalds/linux/blob/v6.19/drivers/input/mouse/alps.c) | `pvr2_hdw_render_useless()`、"render it inoperable"、"render unusable" 等 |
| 格式化呈現 | 26 | [`fs/proc/array.c`](https://github.com/torvalds/linux/blob/v6.19/fs/proc/array.c)、[`net/ceph/messenger.c`](https://github.com/torvalds/linux/blob/v6.19/net/ceph/messenger.c) | `render_sigset_t()`、"Nicely render a sockaddr as a string" |
| 影音媒體算繪 | 14 | [`drivers/media/common/v4l2-tpg/v4l2-tpg-core.c`](https://github.com/torvalds/linux/blob/v6.19/drivers/media/common/v4l2-tpg/v4l2-tpg-core.c)、[`sound/soc/codecs/hdac_hdmi.c`](https://github.com/torvalds/linux/blob/v6.19/sound/soc/codecs/hdac_hdmi.c) | "speed up rendering"（影像測試圖樣）、"stream rendering to multiple ports"（音訊輸出） |
| 其他 | 4 | [`arch/m68k/kernel/traps.c`](https://github.com/torvalds/linux/blob/v6.19/arch/m68k/kernel/traps.c) 等 | "surrender" 中的子字串、"it renders wrong"（顯示異常）等邊緣用法 |
大多數（255 個，佔 75%）集中在 GPU/DRM 子系統，"render" 專指 GPU 的算繪引擎硬體。第二大類（41 個，佔 12%）是英文動詞 "render" 的本義——「使之成為某種狀態」，如 "render useless"（使其不可用）、"render inoperable"（使其無法運作），散見於驅動程式和子系統的註解中。格式化呈現（26 個）則是將內部資料結構「如實呈現」為人類可讀格式，如 [`fs/proc/array.c`](https://github.com/torvalds/linux/blob/v6.19/fs/proc/array.c) 的 `render_sigset_t()`——完全不涉及圖學。
值得注意的是，`drivers/media/usb/pvrusb2/` 中的三個檔案雖然位於影音媒體目錄，實際用法卻是 `pvr2_hdw_render_useless()`（使裝置不可用），屬於「使之成為某狀態」而非「影音媒體算繪」。同理，`drivers/gpu/drm/nouveau/dispnv04/hw.h` 雖在 GPU 目錄，其用法是 "renders the extended crtc regs impervious"（使暫存器不可讀寫），也屬於狀態轉換而非算繪引擎。這說明不能僅憑目錄判斷語意，必須看實際上下文。
核心原始碼中 render 的四種主要用法——算繪引擎、狀態轉換、格式化呈現、影音處理——共通點都是「忠實地將 A 轉變為 B」，沒有任何「誇大修飾」的語意。
### constant 與 immutable 的差異
- [ ] 說明 constant 與 immutable 的差異，並探討程式設計中的關鍵考量
[〈資訊科技詞彙翻譯〉](https://hackmd.io/@sysprog/it-vocabulary)指出 constant 是「恆久不變」，immutable 是「在特定語境下不可修改」。以下透過實驗找出 C99 中哪些機制是 constant、哪些是 immutable，以及規格書為何如此區分。
#### 編譯期測試：`case` 標籤與 constant expression
撰寫 [`constant_immutable.c`](https://github.com/laneser/warmup/blob/main/constant_immutable.c)，所有編譯期測試以 `#ifdef TEST_*` 控制、由 Makefile 的 `-D` 旗標驅動，runtime 實驗則在 `main()` 中執行。全部以 GCC 七個最佳化等級（`-O0`、`-Og`、`-O1`、`-Os`、`-O2`、`-O3`、`-Ofast`）測試。
C99 §6.8.4.2 第 3 段規定：
> The expression of each `case` label shall be an **integer constant expression**.
而 §6.6 第 6 段定義 integer constant expression 的允許運算元：
> An integer constant expression shall have integer type and shall only have operands that are **integer constants, enumeration constants, character constants, `sizeof` expressions** whose results are integer constants, and floating constants that are the immediate operands of casts.
列舉中沒有 `const` 變數——因此 `const int N = 10; case N:` 違反標準。透過 Makefile 對 §6.6 列出的每種允許運算元逐一測試 `case` 標籤，並以 `-Wvla -Werror=vla` 偵測 `int arr[n]` 是否被視為 VLA：
```
Compile-time: constant expression in case label (C99 6.6, 6.8.4.2)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast case_define: compiled
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast case_enum: compiled
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast case_sizeof: compiled
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast case_cast_float: compiled
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast case_char: compiled
-O0 case_const_int: compile error
-Og, -O1, -Os, -O2, -O3, -Ofast case_const_int: compiled (gcc extension)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast arr[const_int]: VLA warning
```
§6.6 認可的運算元（`#define` 替換後的字面值、`enum`、`sizeof`、浮點數轉型、字元字面值）在全部等級都通過。`const int` 則在 `-O0` 被拒絕，`-Og` 以上卻能編譯——原因是 GCC 在啟用最佳化時，常數折疊（constant folding）提前將 `const int N=10` 的值代入，使前端「看到」的是字面值 10 而非變數。這是 **GCC 的延伸行為**，並非 C99 標準允許，加上 `-pedantic-errors` 後全部等級都正確拒絕。
`int arr[n]` 的 VLA 警告不受最佳化影響，七個等級一致觸發——陣列大小的語意檢查在常數折疊之前就完成了。原本預期「編譯錯誤與最佳化等級無關」，但 `case` 標籤的測試證明 GCC 的最佳化階段會回饋影響前端的接受度，印證了跑完全部最佳化等級的必要性。
#### 編譯期測試：mutability 與 addressability
進一步測試這些機制能否被修改、能否取址：
```
Compile-time: mutability and addressability
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast enum_assign: compile error (expected)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast enum_addr: compile error (expected)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast const_addr: compiled (expected)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast define_redefine: compiled (expected)
```
| 機制 | 能否更改值 | 能否取址 | 有記憶體位置 |
|------|-----------|---------|------------|
| `#define V 10` | 可以（`#undef` 後重新定義） | 不行（前處理後消失） | 沒有 |
| `enum{V=10}` | 不行（`V=20` → lvalue required） | 不行（`&V` → lvalue required） | 沒有 |
| `sizeof(int)` | 不行（編譯期決定） | 不行（不是物件） | 沒有 |
| `'A'`（字元字面值） | 不行（字面值） | 不行 | 沒有 |
| `const int N=10` | 語意上不行，可透過指標繞過（UB） | **可以** | **有** |
§6.6 認可的運算元有一個共通點：**不佔記憶體、不可取址**，因此不存在被修改的可能——這才是 constant。`const int` 有記憶體位置、可取址，保護是語境相關的（全域有 `.rodata` 硬體保護，區域只有編譯器語意檢查），因此只達到 immutable 的層級。
值得注意的是 `#define`：巨集本身可以 `#undef` 後重新定義，同一個名稱在原始碼不同位置可代表不同值。但這發生在前處理階段——替換完成後，每個使用點都成為字面值（integer constant），在 C 語言層級是 constant。
#### 實驗 1：強制修改 `const` 物件是未定義行為
透過指標強制轉型修改 `const int local = 100` 後，觀察透過變數名稱讀取的值（C99 §6.7.3.5）：
```
Experiment 1: modify const local via cast (UB: C99 6.7.3.5)
-O0 local_name=999 local_ptr=999
-Og, -O1, -Os, -O2, -O3, -Ofast local_name=100 local_ptr=999
```
`-O0` 不做最佳化，老實從記憶體讀取，看到被竄改的 999。`-Og` 以上啟用常數傳播（constant propagation），編譯器假設 `const` 物件不會被修改，直接以字面值 100 取代記憶體讀取。同一段原始碼在不同最佳化等級下產生不同結果——這就是未定義行為的具體表現。
#### 實驗 2：全域 `const` 被放入唯讀記憶體
C99 §6.7.3 footnote 114：
> The implementation may place a const object that is not volatile in a read-only region of storage.
透過讀取 `/proc/self/maps` 驗證各變數所在記憶體區段的權限：
```
Experiment 2: memory permissions (C99 6.7.3, footnote 114)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast g_const perms=r--p writable=no
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast g_mutable perms=rw-p writable=yes
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast local_const perms=rw-p writable=yes
```
全域 `const` 被連結器放入 `.rodata`（唯讀區段），作業系統以頁面保護強制不可寫。區域 `const` 在 stack 上，頁面權限是 `rw-p`——硬體不阻擋寫入，保護只來自編譯器的語意檢查。七個最佳化等級結果一致，因為記憶體配置由連結器決定，與最佳化無關。
> 完整程式碼與 Makefile：[laneser/warmup](https://github.com/laneser/warmup)
> 執行 `make constant_immutable_report` 可重現上述結果。
#### 程式設計中的關鍵考量
綜合編譯期測試和 runtime 實驗的發現，C99 中的「不可變」機制可分為兩個層次：
**Constant（§6.6 認可的 constant expression）：** `enum`、`sizeof`、字元字面值、整數字面值（含 `#define` 替換後的結果）、浮點數轉型。這些不佔記憶體、不可取址，值在編譯期確定且無法被任何手段修改——符合 constant「在所有時空都不變」的語意。
**Immutable（`const` 型別修飾）：** `const` 變數有記憶體位置、可取址。C99 規格書中 "immutable" 一詞完全沒有出現，`const` 的意圖接近 constant——規格書對修改 `const` 物件的描述是 undefined behavior（§6.7.3.5），這已是語言規範所能施加的最強約束。但 C 語言允許直接操作記憶體，使得 `const` 的保護是語境相關的：全域 `const` 有 `.rodata` 硬體保護（實驗 2），區域 `const` 只有編譯器語意檢查（實驗 1）。§6.6 不將 `const` 變數列入 constant expression，正是因為它有記憶體位置，理論上存在被修改的可能。
**`const` 的處境是：意圖接近 constant，但因為 C 語言的低階本質（可取址、可透過指標繞過），實際保護效果只達到 immutable 的層級。** 程式設計者使用 `const` 時，應將其理解為語意合約而非硬體保證，並在需要真正的編譯期常數時使用 `enum` 而非 `const int`。
### concurrent 與 parallel 的語意差異
- [ ] 比較 concurrent 與 parallel 的語意差異，並說明為何「並行」較貼近 concurrent 的本意
[〈資訊科技詞彙翻譯〉](https://hackmd.io/@sysprog/it-vocabulary)已詳述 concurrent（時間重疊，不要求物理同時）與 parallel（物理上同時執行）的區別。查閱教育部[《重編國語辭典修訂本》](https://dict.revised.moe.edu.tw/)後，認同「並行」優於「併發」的理由：「[並行](https://dict.revised.moe.edu.tw/dictView.jsp?ID=19762)」強調**持續進行**，「[併發](https://dict.revised.moe.edu.tw/dictView.jsp?ID=19706)」強調**瞬間發生**——concurrent 的語意是多個執行流持續同時推進，而非同時觸發。
### process, thread, task, job 的區分
- [ ] 當我們撰寫 Linux 核心文件，應如何區分 process, thread, task, job 等術語，才能避免跨領域誤解又省去過多的中英並陳？
這四個術語在不同領域有不同意義，撰寫 Linux 核心文件時應以核心原始碼中的實際用法為準。以下從 [`kernel/fork.c`](https://github.com/torvalds/linux/blob/v6.19/kernel/fork.c)、[`include/linux/sched.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/sched.h)、[`include/linux/sched/jobctl.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/sched/jobctl.h) 等檔案歸納各術語在核心中的具體定義。
#### task：核心排程實體的通用結構
`struct task_struct`（定義於 [`include/linux/sched.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/sched.h)）是核心中**所有可排程實體的通用結構**，無論 process 或 thread 都是一個 `task_struct`。
但核心原始碼中 "task" 主要出現在直接操作 `task_struct` 的場合。面向人類閱讀的註解和函式名稱，多數使用語意更明確的 "process" 或 "thread"。例如 [`wake_up_process()`](https://github.com/torvalds/linux/blob/v6.19/kernel/sched/core.c#L4336) 的註解：
```c
/**
* wake_up_process - Wake up a specific process
* @p: The process to be woken up.
*
* Attempt to wake up the nominated process and move it to the
* set of runnable processes.
*/
```
函式名稱叫 `wake_up_process`，註解自然用 "process"——雖然參數型別是 `struct task_struct *`。[`kernel/signal.c`](https://github.com/torvalds/linux/blob/v6.19/kernel/signal.c) 也一樣："Tell a **process** that it has a new active signal"，因為信號傳遞的對象在概念上就是 process。
換言之，核心開發者根據語境選擇最易理解的術語：**明確涉及 `task_struct` 結構操作時用 "task"，描述行為語意時用 "process" 或 "thread"**。這不是術語混亂，而是為了讓原始碼的讀者能快速掌握當下討論的抽象層次。
#### process 與 thread：同一結構，不同旗標
在核心中，process 和 thread 的區別不是結構上的，而是**旗標上的**。兩者都透過 `kernel_clone()` → `copy_process()` → `dup_task_struct()` 建立，差別在 `clone_flags`。以下三段程式碼分布在 [`kernel/fork.c`](https://github.com/torvalds/linux/blob/v6.19/kernel/fork.c) 的不同位置，共同決定 process 與 thread 的區分：
`CLONE_THREAD` 決定是否共享 thread group（[第 2291 行](https://github.com/torvalds/linux/blob/v6.19/kernel/fork.c#L2291)）：
```c
if (clone_flags & CLONE_THREAD) {
p->group_leader = current->group_leader;
p->tgid = current->tgid;
} else {
p->group_leader = p;
p->tgid = p->pid;
}
```
`exit_signal` 在另一個區塊設定，同時處理 `CLONE_PARENT` 的情況（[第 2370 行](https://github.com/torvalds/linux/blob/v6.19/kernel/fork.c#L2370)）：
```c
if (clone_flags & (CLONE_PARENT|CLONE_THREAD)) {
p->real_parent = current->real_parent;
p->parent_exec_id = current->parent_exec_id;
if (clone_flags & CLONE_THREAD)
p->exit_signal = -1;
else
p->exit_signal = current->group_leader->exit_signal;
} else {
p->real_parent = current;
p->parent_exec_id = current->self_exec_id;
p->exit_signal = args->exit_signal;
}
```
行程計數在 `thread_group_leader()` 判斷後遞增（[第 2418 行](https://github.com/torvalds/linux/blob/v6.19/kernel/fork.c#L2418)）：
```c
if (thread_group_leader(p)) {
/* ... attach_pid, signal 初始化 ... */
__this_cpu_inc(process_counts);
} else {
current->signal->nr_threads++;
current->signal->quick_threads++;
atomic_inc(¤t->signal->live);
/* ... */
}
```
而 `thread_group_leader()` 本身定義於 [`include/linux/sched/signal.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/sched/signal.h#L704)：
```c
static inline bool thread_group_leader(struct task_struct *p)
{
return p->exit_signal >= 0;
}
```
**process** = thread group leader（`exit_signal >= 0`，`tgid == pid`），擁有獨立的位址空間、檔案描述子表、`signal_struct`，會遞增 `process_counts`。
**thread** = 非 leader 的 task（`exit_signal == -1`），**借用** process 的資源。`pthread_create` 對應的 `clone()` 帶有 `CLONE_VM | CLONE_FILES | CLONE_SIGHAND | CLONE_THREAD` 等旗標，代表共享位址空間、檔案描述子表、信號處理器，不需要複製這些結構——因此建立 thread 的成本遠低於 process。
雖然兩者都是 `task_struct`，但 `clone_flags` 決定了多少資源需要複製、多少可以共享，這才是 process 與 thread 的本質差異。事後辨識則透過 `thread_group_leader()`（檢查 `exit_signal >= 0`）。
#### job：shell 層級的工作控制
"job" 在核心中**不是一種實體**，而是指 job control 機制。[`include/linux/sched/jobctl.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/sched/jobctl.h) 定義了 `task->jobctl` 的旗標位元：
```c
#define JOBCTL_STOP_SIGMASK 0xffff /* 最後一次 group stop 的信號編號 */
#define JOBCTL_STOP_PENDING_BIT 17 /* task 應為 group stop 而停止 */
#define JOBCTL_TRAP_STOP_BIT 19 /* 為 STOP 設陷阱 */
```
當 shell 按下 Ctrl-Z 送出 `SIGTSTP`，核心透過 `do_signal_stop()`（[`kernel/signal.c`](https://github.com/torvalds/linux/blob/v6.19/kernel/signal.c)）設定 thread group 中所有 task 的 `JOBCTL_STOP_PENDING`，實現整個 process group 的暫停。"job" 在核心中始終與信號和 process group 綁定，不是獨立的排程單位。
#### 排程器操作的對象：`sched_entity`
延伸觀察：排程器實際操作的**不是 `task_struct`**，而是內嵌其中的 `sched_entity`。CFS 排程器的 `pick_task_fair()`（[`kernel/sched/fair.c`](https://github.com/torvalds/linux/blob/v6.19/kernel/sched/fair.c#L8874)）透過 `pick_next_entity()` 選出 `sched_entity`，再透過 `task_of(se)`（即 `container_of`）轉回 `task_struct`。以下擷取關鍵路徑（省略 group scheduling 迴圈和 throttle 處理）：
```c
static struct task_struct *pick_task_fair(struct rq *rq, struct rq_flags *rf)
{
struct sched_entity *se;
/* ... */
do {
se = pick_next_entity(rq, cfs_rq);
cfs_rq = group_cfs_rq(se);
} while (cfs_rq);
p = task_of(se);
return p;
}
```
`task_struct` 透過組合（composition）包含多種排程實體（`sched_entity`、`sched_rt_entity`、`sched_dl_entity`），但排程器只操作對應的子結構。
#### 官方文件中的術語佐證
以上分析來自原始碼，以下從 [docs.kernel.org](https://docs.kernel.org/) 的官方文件交叉驗證這些觀察。核心文件中沒有統一的 glossary 頁面定義這四個術語，但多處文件的用法一致，可作為佐證。
**task = 排程實體的通稱。** [CFS Scheduler](https://docs.kernel.org/scheduler/sched-design-CFS.html) 文件通篇以 "task" 指稱排程單位，並在提到 scheduling entity 時直接等同：
> "It puts the scheduling entity (task) into the red-black tree and increments the nr_running variable."
[SCHED_DEADLINE](https://docs.kernel.org/scheduler/sched-deadline.html) 文件同樣以 "task" 作為排程實體的通稱，不區分 process 或 thread：
> "A SCHED_DEADLINE task should receive 'runtime' microseconds of execution time every 'period' microseconds"
這與原始碼分析一致：排程器層級只認 task（`sched_entity`），不關心它是 process 還是 thread。
**PID 對應 thread，TGID 對應 process（thread group）。** [ftrace](https://docs.kernel.org/trace/ftrace.html) 文件在描述 `record-tgid` 選項時，明確定義了 PID 與 TGID 的對應關係：
> "on each scheduling context switch the Task Group ID of a task is saved in a table mapping the PID of the thread to its TGID."
這段文字的術語選擇非常精確：PID 屬於 "thread"，TGID（Task Group ID）屬於 thread group。對照原始碼中 `fork.c` 的 `p->tgid = current->tgid`（`CLONE_THREAD` 時共享 tgid）和 `p->tgid = p->pid`（新 process 時 tgid 等於自身 pid），文件與實作完全吻合——process 就是 thread group leader，其 pid 即為整個 group 的 tgid。
**`fork()` 建立的是 thread（排程層級）。** [sysctl 文件](https://docs.kernel.org/admin-guide/sysctl/kernel.html)中 `threads-max` 的描述：
> "the maximum number of threads that can be created using fork()"
這裡把 `fork()` 建立的東西稱為 "thread"，乍看似乎與一般認知（`fork()` 建立 process）矛盾。但從核心排程器的視角，每個 `task_struct` 都是一個排程執行緒；`fork()` 建立的新 process 同時也是一個新的排程執行緒（只是它恰好是 thread group leader）。`threads-max` 計算的是系統中所有 `task_struct` 的數量上限，不分 process 或 thread。
#### 撰寫核心文件時的術語選擇
| 術語 | 核心中的意義 | 中文翻譯 |
|------|------------|---------|
| task | `task_struct`，所有可排程實體的通用稱呼 | 直接用 task（無精確對應中文） |
| process | thread group leader（`exit_signal >= 0`） | 行程 |
| thread | 非 leader 的 task（`CLONE_THREAD`） | 執行緒 |
| job | job control 機制，非獨立實體 | 直接用 job control（中文「工作控制」可用但少見） |
"task" 和 "job" 在核心語境中有特定技術含義，直接使用英文原文較不易產生跨領域混淆。"process" 和 "thread" 可用「行程」「執行緒」，但須意識到核心中兩者共用同一個 `task_struct` 結構，差異在於 `clone_flags` 決定的資源共享程度——thread 借用 process 的位址空間和檔案描述子，建立成本較低。
## 細讀〈GNU/Linux 開發工具〉
### 開發環境配置
- [ ] 確保 Linux 系統已正確安裝，且每天使用
目前使用三機架構進行開發與測試：
| 角色 | 硬體 | OS | 用途 |
|------|------|-----|------|
| 主力開發機 | AMD Ryzen 7 9800X3D 8C/16T，16 GiB RAM | Ubuntu 24.04.4 LTS（Docker on WSL2） | 編輯、AI 協作、git 操作 |
| ARM 實體機 (`lab0`) | Raspberry Pi 3 Model B v1.2，Cortex-A53 4C，906 MiB RAM | Debian 13 (trixie)，核心 6.12.62-v8（aarch64） | 跨架構編譯測試 |
| x86 實體機 (`lab-x86`) | Intel Celeron J1800 2C，3.7 GiB RAM | Ubuntu 24.04.1 LTS，核心 6.12.74-patched+（x86_64） | 原生編譯、valgrind、perf |
日常工作流程：在 Docker container 內透過 VS Code Dev Container 開發，需要原生測試時透過 SSH 同步至實體機：
```
rsync -avz --exclude='.git' homework/lab0-c/ lane@lab0:~/lab0-c/
ssh lane@lab0 'cd ~/lab0-c && make && make test'
```
兩台實體機分別提供 ARM 和 x86 環境，可驗證程式在不同架構下的行為差異（如 alignment 要求、endianness、`sizeof` 差異等）。
### HackMD 與 LaTeX
- [ ] 學習 HackMD 的操作，並可正確使用 LaTeX。能夠在 HackMD 筆記中用 LaTeX 語法展現波函數和密度矩陣
HackMD 支援行內公式（`$...$`）和獨立公式（`$$...$$`）。以下整理學習 LaTeX 過程中掌握的語法，並以波函數和密度矩陣為例展示。
#### 常用 LaTeX 語法
| 語法 | 效果 | 說明 |
|------|------|------|
| `x^2` | $x^2$ | 上標（指數） |
| `x_n` | $x_n$ | 下標 |
| `\frac{a}{b}` | $\frac{a}{b}$ | 分數，第一個 `{}` 放分子，第二個放分母 |
| `\sum_{i=1}^{N}` | $\sum_{i=1}^{N}$ | 求和符號 |
| `\partial` | $\partial$ | 偏微分 |
| `\hbar` | $\hbar$ | 約化 Planck 常數（$\hbar = \frac{h}{2\pi}$） |
| `\Psi`, `\psi`, `\rho` | $\Psi$, $\psi$, $\rho$ | 希臘字母 |
| `\langle`, `\rangle` | $\langle$, $\rangle$ | 狄拉克（Dirac）bra-ket 記號的角括號 |
| `\begin{pmatrix} a & b \\ c & d \end{pmatrix}` | $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ | 矩陣，`&` 分欄，`\\` 換行 |
#### 波函數
波函數 $\Psi(x, t)$ 描述量子系統的狀態。$\Psi$ 本身是複數值函式，不直接是機率；$|\Psi(x,t)|^2$ 才是機率密度——在 $[a, b]$ 區間找到粒子的機率為：
$$P(a \leq x \leq b) = \int_a^b |\Psi(x,t)|^2 \, dx$$
歸一化條件要求粒子一定在某處：
$$\int_{-\infty}^{\infty} |\Psi(x,t)|^2 \, dx = 1$$
三維空間中，波函數寫為 $\Psi(\mathbf{r}, t)$，其中 $\mathbf{r} = (x, y, z)$。波函數的時間演化由薛丁格（Schrödinger）方程式決定：
$$i\hbar \frac{\partial}{\partial t} \Psi(\mathbf{r}, t) = \hat{H} \Psi(\mathbf{r}, t)$$
左邊是 $i \cdot \hbar$ 乘以波函數對時間的偏微分（波函數隨時間的變化率），右邊是 Hamilton 運算子 $\hat{H}$（代表系統總能量）作用在波函數上。白話說：波函數怎麼隨時間演化，由系統的能量結構決定。
#### 密度矩陣
波函數只能描述**純態**（確定處於某個量子態）。當系統的狀態不確定——例如只知道「70% 機率處於 $|0\rangle$，30% 機率處於 $|1\rangle$」——這種**混合態**需要密度矩陣來描述。密度矩陣由[馮·諾伊曼](https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%BF%B0%C2%B7%E5%86%AF%C2%B7%E8%AF%BA%E4%BC%8A%E6%9B%BC)（von Neumann）與[列夫·朗道](https://zh.wikipedia.org/wiki/%E5%88%97%E5%A4%AB%C2%B7%E6%9C%97%E9%81%93)（Landau）於 1927 年分別獨立提出。
這裡的 $|0\rangle$（ket）和 $\langle 0|$（bra）是[狄拉克符號](https://zh.wikipedia.org/wiki/%E7%8B%84%E6%8B%89%E5%85%8B%E7%AC%A6%E5%8F%B7)，分別代表行向量和列向量：
$$|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad \langle 0| = \begin{pmatrix} 1 & 0 \end{pmatrix}$$
ket 乘以 bra（外積）得到矩陣，這就是純態的密度矩陣：
$$|0\rangle\langle 0| = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$$
混合態「70% 在 $|0\rangle$，30% 在 $|1\rangle$」的密度矩陣，就是各純態密度矩陣的加權和：
$$\rho = 0.7 |0\rangle\langle 0| + 0.3 |1\rangle\langle 1| = \begin{pmatrix} 0.7 & 0 \\ 0 & 0.3 \end{pmatrix}$$
一般化的混合態密度矩陣定義為：
$$\rho = \sum_i p_i |\psi_i\rangle\langle\psi_i|, \quad \sum_i p_i = 1, \quad p_i \geq 0$$
純態與混合態的差別可透過密度矩陣的非對角元素區分。疊加態 $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ 的密度矩陣含有非零的 $\alpha\beta^*$ 項（coherence），代表量子干涉效應；混合態的 coherence 消失，對角線只剩古典機率。
### Git 操作
- [ ] 學習 git 的操作，依據給定的教學錄影實際練習，並知曉 `git rebase` 一類命令的操作
#### `git rebase` 的運作原理
`git merge` 保留完整的分支歷史，產生 merge commit；`git rebase` 則將一系列 commit 重新套用（replay）到新的基底上，產生線性歷史。以下圖示說明差異：
```
# merge 前
main: A---B---C
\
feature: D---E
# git merge（保留分支結構）
main: A---B---C---M
\ /
feature: D---E
# git rebase（線性化）
main: A---B---C
\
feature: D'---E'
```
`git rebase main` 的實際步驟：
1. 找出 `feature` 分支與 `main` 的共同祖先（B）
2. 將 B 之後的 commit（D、E）暫存為 patch
3. 將 `feature` 的 HEAD 重置到 `main` 的最新 commit（C）
4. 依序將暫存的 patch 重新套用，產生新的 commit（D'、E'）
D' 和 E' 的內容與 D、E 相同，但 commit hash 不同——因為 parent commit 改變了。
#### Interactive rebase
`git rebase -i HEAD~3` 可對最近 3 個 commit 進行互動式操作：
| 指令 | 作用 |
|------|------|
| `pick` | 保留該 commit |
| `reword` | 保留但修改 commit message |
| `squash` | 與前一個 commit 合併，保留兩者的 message |
| `fixup` | 與前一個 commit 合併，丟棄此 commit 的 message |
| `drop` | 刪除該 commit |
在課程作業中，interactive rebase 適合用來整理開發過程中的瑣碎 commit（如 "fix typo"、"debug print"），在提交前合併為語意完整的 commit。
#### 使用限制
`git rebase` 改寫歷史，因此有一條基本原則：**不對已推送到共享分支的 commit 執行 rebase**。若其他人已基於這些 commit 開發，rebase 會導致歷史分歧，造成合併困難。本地尚未推送的分支則可自由 rebase。
## 探討〈解讀計算機編碼〉
### 固定位元寬度的加法等價於 $\mathbb{Z}/2^k\mathbb{Z}$
- [ ] 為何計算機的加法在固定 $k$ 位元下，本質等價於 $\mathbb{Z}/2^k\mathbb{Z}$ 上的加法？
$k$ 位元能表示的值恰好是 $\{0, 1, 2, \ldots, 2^k - 1\}$，共 $2^k$ 個元素。二進位加法若結果超出 $k$ 位元，溢出的高位元被硬體捨棄——這在數學上等於 $\bmod\ 2^k$。
以 $k = 3$ 為例，集合為 $\{0, 1, \ldots, 7\}$，$6 + 5 = 11$，硬體運算為 `110 + 101 = [1]011`，第 4 位元溢出被丟棄，結果為 `011` = 3，即 $11 \bmod 8 = 3$。
這不是巧合，而是硬體的物理限制（只有 $k$ 條線路）自動實現了模除運算。因此 $k$ 位元無號加法與 $\mathbb{Z}/2^k\mathbb{Z}$ 的加法是同一件事——集合相同（$2^k$ 個元素），運算規則相同（加完取 $\bmod 2^k$）。教材以「圓環」比喻：$\mathbb{Z}/2^k\mathbb{Z}$ 是一個有 $2^k$ 個刻度的時鐘，加法是順時針轉圓弧，繞過 $2^k - 1$ 之後回到 $0$。
### 允許溢位保證封閉性
- [ ] 為何「允許溢位」反而保證封閉性？若不允許溢位，會破壞哪些群的性質？
若不允許溢位（例如溢位時報錯中斷），以 $k = 3$ 的集合 $\{0, \ldots, 7\}$ 和普通整數加法來看，阿貝爾群的五項性質中只剩單位元素（$0$）不受影響：
| 性質 | 不允許溢位 | 允許溢位（$\bmod 2^k$） |
|------|-----------|----------------------|
| 封閉性 | 破壞：$6 + 5 = 11 \notin \{0, \ldots, 7\}$ | 保證：結果自動落回集合 |
| 結合律 | 運算不完備，無法對所有元素成立 | 保證 |
| 單位元素 | $0$ 仍有效 | $0$ 仍有效 |
| 反元素 | 不存在：$5$ 的反元素需 $-5$，但 $-5 \notin \{0, \ldots, 7\}$ | 存在：$-a \equiv 2^k - a$（如 $-5 \equiv 3$） |
| 交換律 | 運算不完備時無意義 | 保證 |
反元素的問題比封閉性更根本——不是溢位導致計算中斷，而是反元素**根本不存在於集合中**。正是允許溢位（$\bmod 2^k$）才**創造**了反元素：$5 + 3 = 8 \equiv 0 \pmod{8}$，使 $3$ 成為 $5$ 的反元素。溢位使得二補數的 $-a$ 可定義為 $\neg a + 1$（位元反轉再加 1），也就是 $2^k - a$。
### 費馬小定理與模反元素
- [ ] 在質數模數 $p$ 下，可用 $a^{-1} \equiv a^{p-2} \pmod p$ 計算反元素，解釋該式如何來自有限群理論，並說明為何此性質僅在「非零元素形成群」時成立。從 Linux 核心實作角度分析: 1) 為何必須確保輸入元素為單位？2) 若傳入零因子會造成什麼風險？
#### 從群論推導費馬小定理
教材（〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉）展示 $\{1, 2, 3, 4\}$ 在 $\bmod 5$（質數）下的乘法表：
| $\times$ | 1 | 2 | 3 | 4 |
|----------|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 |
| 2 | 2 | 4 | 1 | 3 |
| 3 | 3 | 1 | 4 | 2 |
| 4 | 4 | 3 | 2 | 1 |
每行每列都是 $\{1, 2, 3, 4\}$ 的排列（Latin square），代表每個元素都有乘法反元素——這就是群。這個 Latin square 性質是費馬小定理的證明基礎：
取集合 $S = \{1, 2, \ldots, p-1\}$，將每個元素乘以 $a$（$a \not\equiv 0$），得到 $\{a, 2a, \ldots, (p-1)a\} \pmod{p}$。因為乘以 $a$ 是排列（Latin square 性質），這個集合恰好是 $S$ 的重排——因數完全相同，只是順序不同。由交換律，兩邊全部乘起來的結果相等：
$$(p-1)! \cdot a^{p-1} \equiv (p-1)! \pmod{p}$$
左邊提出 $a^{p-1}$ 用到結合律和交換律。$(p-1)!$ 的每個因數都在群中，反元素存在，兩邊乘以 $(p-1)!$ 的反元素消去，得到費馬小定理：
$$a^{p-1} \equiv 1 \pmod{p}$$
將 $a^{p-1}$ 拆成 $a \cdot a^{p-2}$：既然 $a \cdot a^{p-2} \equiv 1$，那麼 $a^{p-2}$ 就是 $a$ 的乘法反元素，即 $a^{-1} \equiv a^{p-2} \pmod{p}$。
#### 僅在非零元素成群時成立
上述證明的每一步都依賴群的性質：封閉性（乘以 $a$ 的結果落回集合）、交換律（因數順序不影響乘積）、反元素存在（消掉 $(p-1)!$）。若模數不是質數，這些性質就不成立。
以 $\bmod 4$（非質數）下 $\{1, 2, 3\}$ 的乘法表為例：
| $\times$ | 1 | 2 | 3 |
|----------|---|---|---|
| 1 | 1 | 2 | 3 |
| 2 | 2 | 0 | 2 |
| 3 | 3 | 2 | 1 |
第 2 行是 $\{2, 0, 2\}$——$2 \times 2 \equiv 0 \pmod{4}$，結果落在集合 $\{1, 2, 3\}$ 之外，封閉性不成立，不是排列。證明的第一步（「乘以 $a$ 是排列」）就失敗了，整個推導鏈斷裂，費馬小定理不適用，$a^{p-2}$ 也就無法作為反元素。
#### Linux 核心中的模反元素
**搜尋思路：** 題目問的是 $a^{-1} \pmod{p}$，程式中稱為 modular inverse。C 語言用 snake_case 命名，先搜尋最直覺的 `mod_inv`、`vli_mod_inv` 等變體。進一步擴大搜尋範圍，用 `fermat`、`inverse`、`p - 2`、`mpi.*inv` 等關鍵字掃過整個 `crypto/` 子系統，確認是否有其他實作。
搜尋結果：
- `fermat`——僅出現在 `drivers/net/usb/zaurus.c` 的 "fermat packet mangling"，與數學無關
- `mod_inverse` / `modular_inverse`——無符合結果
- `p - 2`（在 `crypto/`）——僅 `crypto/dh.c` 的範圍檢查 `2 <= y <= p - 2`，不是在計算 $a^{p-2}$
- `mpi.*inv`——找到 `crypto/rsa.c` 的 `key->qinv`（見下方）
核心中**沒有直接用 $a^{p-2}$ 計算反元素的程式碼**——都採用擴展歐幾里得演算法，效率更高（多項式時間 vs 指數冪次）。找到兩處模反元素的使用：
**橢圓曲線密碼：** [`crypto/ecc.c`](https://github.com/torvalds/linux/blob/v6.19/crypto/ecc.c) 的 `vli_mod_inv()`（[第 1039 行](https://github.com/torvalds/linux/blob/v6.19/crypto/ecc.c#L1039)），runtime 計算模反元素，用於 ECDSA 簽章驗證和點座標轉換。
**RSA CRT 加速：** [`crypto/rsa.c`](https://github.com/torvalds/linux/blob/v6.19/crypto/rsa.c) 的 `key->qinv`（[第 350 行](https://github.com/torvalds/linux/blob/v6.19/crypto/rsa.c#L350)），即 $q^{-1} \bmod p$，在金鑰生成時預先計算並儲存於金鑰結構中，用於中國剩餘定理（CRT）加速 RSA 私鑰運算（[第 102 行](https://github.com/torvalds/linux/blob/v6.19/crypto/rsa.c#L102)）。
兩者的數學前提相同：輸入必須是乘法群的元素（非零且與模數互質），反元素才存在。
**為何必須確保輸入為單位？** 觀察 `vli_mod_inv` 對零輸入的處理（[第 1047 行](https://github.com/torvalds/linux/blob/v6.19/crypto/ecc.c#L1047)）：
```c
if (vli_is_zero(input, ndigits)) {
vli_clear(result, ndigits);
return;
}
```
模反元素在數學上是**部分函式**（partial function）——零和與模數不互質的元素沒有定義。但 `vli_mod_inv` 的回傳型別是 `void`，沒有管道回報「此輸入無解」，遇到零輸入只能靜默回傳零。
**若傳入零會造成什麼風險？** 以 ECDSA 簽章驗證（[`crypto/ecdsa.c`](https://github.com/torvalds/linux/blob/v6.19/crypto/ecdsa.c)）為例，驗證流程需要計算 $s^{-1} \bmod n$。呼叫端在計算反元素之前先檢查輸入（[第 34 行](https://github.com/torvalds/linux/blob/v6.19/crypto/ecdsa.c#L34)）：
```c
/* 0 < r < n and 0 < s < n */
if (vli_is_zero(r, ndigits) || vli_cmp(r, curve->n, ndigits) >= 0 ||
vli_is_zero(s, ndigits) || vli_cmp(s, curve->n, ndigits) >= 0)
return -EBADMSG;
```
確認 $s \neq 0$ 且 $s < n$ 後才呼叫 `vli_mod_inv`（[第 44 行](https://github.com/torvalds/linux/blob/v6.19/crypto/ecdsa.c#L44)）。若此檢查被省略，$s = 0$ 會使 $s^{-1}$ 得到 $0$，後續 $u_1 = hash \cdot 0 = 0$、$u_2 = r \cdot 0 = 0$，驗證退化為檢查無窮遠點，簽章驗證邏輯被繞過——攻擊者可偽造任意訊息的合法簽章。
**設計觀察：** `vli_mod_inv` 內部已經檢查了 `vli_is_zero(input)`，但因為回傳 `void`，檢查到了也無法回報，只能靜默回傳零。呼叫端為了安全，又得在呼叫前再做一次零檢查。結果是：若呼叫者有檢查（如 ECDSA），底層的零檢查永遠不會觸發，是多餘的；若呼叫者沒檢查，底層雖然擋住了零但無法通知，等於白查。兩種情境都造成浪費。若函式改為回傳 `int` 錯誤碼，底層一次檢查就能同時完成偵測和通知，呼叫端只需檢查回傳值，無需重複驗證輸入。
不過，回到 ECDSA 的實際情境，即使 `vli_mod_inv` 改為回傳錯誤碼，能省掉的也只有 `vli_is_zero(s)` 這一項。ECDSA 的四個檢查中，`r == 0`、`r >= n` 與 `vli_mod_inv` 完全無關（`r` 不是它的輸入），而 `s >= n` 是 ECDSA 協定層級的約束——`vli_mod_inv` 的擴展 GCD 在 $s \geq n$ 時仍會算出結果（等效於 $(s \bmod n)$ 的反元素），數學上不算錯，但不符合規格要求。因此，`void` 設計的原則性缺陷（部分函式無法回報錯誤）仍然存在，但在此案例中實際影響有限，呼叫端的多數檢查屬於協定層級的驗證，無論如何都不能省略。
### 位元遮罩取餘數僅對 unsigned 安全
- [ ] 為何 $x \mod 2^n \equiv x \& (2^n - 1)$ 僅對 unsigned 或非負整數安全？從 CVE/CWE 找到相關資訊安全的議題
#### 等價性只在非負時成立
$2^n - 1$ 的二進位表示是 $n$ 個 1（例如 $n = 3$ 時為 `111` = 7）。$x \mathbin{\&} (2^n - 1)$ 的效果是清除高位元、只保留最低 $n$ 位元——對 unsigned 整數來說，這與 $x \mod 2^n$ 完全等價。
但對 signed 負數，兩者結果不同。以 $x = -1$（32-bit signed int）、$n = 3$ 為例：
- $(-1) \mod 8 = -1$（C99 §6.5.5：餘數的符號與被除數相同）
- $(-1) \mathbin{\&} 7 = 7$（$-1$ 的二補數全為 1，AND 後保留最低 3 位元）
位元 AND 永遠產生非負結果（高位元被清零，包括符號位元），等於丟失了符號資訊。若程式將 $x \mathbin{\&} mask$ 當作 $x \mod divisor$ 的最佳化替代，遇到負數輸入就會得到錯誤結果。
#### CWE 與 CVE
題目要求「從 CVE/CWE 找到相關資訊安全的議題」。過去只知道 CVE（Common Vulnerabilities and Exposures），查了才發現 CWE（Common Weakness Enumeration）是不同層次的東西：
- **CWE** 是由 [MITRE](https://cwe.mitre.org/) 維護的**軟體弱點分類系統**，描述的是「這一類錯誤的通用模式」。靜態分析工具（Coverity、Clang Static Analyzer）用 CWE 編號標記問題，開發者用它作為常見錯誤的檢查清單。
- **CVE** 是「某個特定產品中的具體漏洞」，每個 CVE 會標注對應的 CWE 分類，說明根因屬於哪一類。
換言之，**CWE 是病名，CVE 是病例**。
#### CWE 分類與 CERT C 規則
對 signed 值使用位元運算子（包含用 `&` 替代 `%`）的問題，對應的業界規範是 SEI CERT C 的 INT13-C 規則 [[1]](https://wiki.sei.cmu.edu/confluence/display/c/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands)：**「位元運算子只應用於 unsigned 運算元」**。該規則指出，對 signed 值做位元運算的結果是 implementation-defined（右移）或可能導致非預期行為（AND、OR 等），可能造成緩衝區溢位甚至任意程式碼執行。
INT13-C 官方映射的 CWE 是 **CWE-682: Incorrect Calculation** [[2]](https://cwe.mitre.org/data/definitions/682.html)——「產生不正確或非預期結果的計算」。這正是 `x & (2^n - 1)` 替代 `x % 2^n` 對 signed 負數算錯的情形：程式設計師假設兩者等價，但對負數輸入 `& mask` 會產生錯誤的非負結果。`x & mask` 中兩個運算元和結果都是 `int`，沒有發生型別轉換，問題純粹是計算本身對負數不成立。
#### 相關 CVE
以各種關鍵字（bitmask modulo signed、signedness bitwise、mask negative 等）搜尋 NVD 和 CWE-682 底下的 CVE，**找不到直接因「`& mask` 替代 `% mod` 對 signed 值算錯」而產生的漏洞**。
#### 核心中的 bitmask-as-modulo 實例
Linux 核心的 [`include/linux/circ_buf.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/circ_buf.h) 是此 pattern 的典型使用：
```c
struct circ_buf {
char *buf;
int head; /* signed */
int tail; /* signed */
};
#define CIRC_CNT(head,tail,size) (((head) - (tail)) & ((size)-1))
```
`CIRC_CNT` 用 `& (size - 1)` 取代 `% size` 來計算環形緩衝區中的元素數量。`head` 和 `tail` 宣告為 `int`（signed），若 `head - tail` 出現負值，bitmask 會產生一個大正數而非正確的負差值。在正常使用中，呼叫者需確保 `head >= tail`（或理解 wrap around 是刻意設計），但這依賴使用者遵守隱含的前提條件。
相對地，核心中許多較新的實作已改用 unsigned 型別避免此問題，例如 BPF hash table（[`kernel/bpf/hashtab.c`](https://github.com/torvalds/linux/blob/v6.19/kernel/bpf/hashtab.c)）使用 `u32 hash` 搭配 `hash & (htab->n_buckets - 1)`。
### Sign extension 僅在跨圓環搬移時才有意義
- [ ] 為何 sign extension 僅在「跨圓環」搬移時才有意義？從數學觀點解釋，要一般化相關證明
〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉「處理器的指令集和數值編碼」一節提出關鍵觀察：
> 在電腦架構中，實際上每種資料都表示一個圓環，假設系統中有 8 位元、16 位元、32 位元等 3 種資料處理模型的話，系統中就存在三個圓環，只有將一個資料從一個圓環放到另一個圓環的指令才會考慮符號⋯⋯同一圓環上進行的運算根本不用考慮符號，因此也就不用提供兩套指令。
以下從數學上解釋為何同一圓環不需區分 signed/unsigned，而跨圓環搬移必須區分，並將教材的 8 → 16 位元範例一般化為任意 $m$ → $n$ 位元。
#### 同一圓環上的運算不需區分符號
$k$ 位元資料構成的圓環是 $\mathbb{Z}/2^k\mathbb{Z}$，有 $2^k$ 個元素 $\{0, 1, \ldots, 2^k - 1\}$。Signed 和 unsigned 只是同一個圓環上兩種不同的**標記方式**：
- Unsigned：選代表元 $\{0, 1, \ldots, 2^k - 1\}$
- Signed（二補數）：選代表元 $\{-2^{k-1}, \ldots, -1, 0, 1, \ldots, 2^{k-1} - 1\}$
兩者都是 $\mathbb{Z}/2^k\mathbb{Z}$ 的完全剩餘系（complete residue system）——每個等價類恰好選一個代表元。對任意 $a, b \in \mathbb{Z}/2^k\mathbb{Z}$：
$$(a + b) \bmod 2^k$$
不論 $a, b$ 被解讀為 signed 或 unsigned，模除之後得到的位元模式（bit pattern）完全相同。原因是 signed 的代表元 $x - 2^k$（負數）和 unsigned 的代表元 $x$ 屬於同一等價類：$x - 2^k \equiv x \pmod{2^k}$。
因此，加法器不需要知道運算元是 signed 還是 unsigned——硬體只做 $\bmod\ 2^k$ 的加法，結果的位元模式相同。減法和乘法同理：$a - b \equiv a + (2^k - b) \pmod{2^k}$、$(a \times b) \bmod 2^k$ 的結果也與解讀方式無關。這就是為什麼 x86 的 `ADD`、`SUB`、`IMUL` 指令不需區分 signed/unsigned——同一圓環上，一套指令即可。
唯一需要區分的同圓環運算是**除法和比較**：除法結果取決於數學值而非位元模式（$(-7) \div 2 = -3$ vs $249 \div 2 = 124$ 在 8-bit 下），因此 x86 分別提供 `DIV`/`IDIV` 和 `JA`（unsigned above）/`JG`（signed greater）。
#### 跨圓環搬移必須區分符號：一般化證明
現在考慮將資料從較小的圓環 $\mathbb{Z}/2^m\mathbb{Z}$ 搬到較大的圓環 $\mathbb{Z}/2^n\mathbb{Z}$（$m < n$）。我們需要一個映射 $\phi$ 使得目標圓環中的元素**保留原始數值**。
定義二補數解讀函式。對 $k$ 位元的位元模式 $x \in \{0, \ldots, 2^k - 1\}$，其 signed 值為：
$$T_k(x) = x - 2^k \cdot x_{k-1}$$
其中 $x_{k-1}$ 是最高位元（sign bit）。當 $x_{k-1} = 0$ 時 $T_k(x) = x$，當 $x_{k-1} = 1$ 時 $T_k(x) = x - 2^k$。
**目標：** 給定 $x \in \{0, \ldots, 2^m - 1\}$，找到 $y \in \{0, \ldots, 2^n - 1\}$ 使得 $T_n(y) = T_m(x)$。
**情況 1：$x_{m-1} = 0$（非負值）**
$T_m(x) = x$，且 $0 \leq x < 2^{m-1} < 2^{n-1}$，因此 $x$ 在 $n$ 位元中同樣是非負值。
取 $y = x$，則 $T_n(y) = y = x = T_m(x)$。✓
位元操作：高位補零（zero extension），$y = \underbrace{0\ldots0}_{n-m}\ x_{m-1}\ x_{m-2}\ \ldots\ x_0$。
**情況 2：$x_{m-1} = 1$（負值）**
$T_m(x) = x - 2^m < 0$。需要 $T_n(y) = x - 2^m$。
因為目標值是負數，$y$ 在 $n$ 位元中也必須是負數（$y_{n-1} = 1$），所以 $T_n(y) = y - 2^n$。
$$y - 2^n = x - 2^m \implies y = x + 2^n - 2^m$$
驗證 $y$ 的範圍：$2^{m-1} \leq x < 2^m$，因此 $2^n - 2^m + 2^{m-1} \leq y < 2^n$，確實落在 $\{0, \ldots, 2^n - 1\}$ 內。✓
位元操作：$2^n - 2^m = \sum_{i=m}^{n-1} 2^i$，其二進位表示是第 $m$ 到第 $n-1$ 位元全為 1。由於 $x < 2^m$，加上 $2^n - 2^m$ 不會影響低 $m$ 位元：
$$y = \underbrace{1\ldots1}_{n-m}\ x_{m-1}\ x_{m-2}\ \ldots\ x_0$$
因為 $x_{m-1} = 1$，高位全部是 sign bit 的複製。這就是 sign extension。
**合併兩種情況：** 無論 $x_{m-1}$ 是 0 或 1，正確的 $n$ 位元表示都是將 $x_{m-1}$ 複製到高位的 $n - m$ 個位元——即 sign extension。$\blacksquare$
**對比 unsigned 的情況：** 若 $x$ 的 unsigned 值就是 $x$ 本身，則 $y = x$（zero extension）。當 $x_{m-1} = 1$ 時，sign extension 得到 $x + 2^n - 2^m$，zero extension 得到 $x$——兩者在目標圓環中是**不同的元素**。例如 $m = 8, n = 16$ 時，位元模式 `11111111`：
- Unsigned 值 $255$：zero extension → `00000000 11111111` = $255$
- Signed 值 $-1$：sign extension → `11111111 11111111` = $65535$（unsigned），$T_{16}(65535) = -1$
在 $\mathbb{Z}/2^{16}\mathbb{Z}$ 圓環上，$255$ 和 $65535$ 位於不同位置。這就是為什麼「跨圓環搬移」必須知道符號——同一個位元模式在源圓環和目標圓環中對應不同位置，正確的對應取決於解讀方式。
#### 為何同圓環不需要、跨圓環才需要：直觀理解
同一圓環上，$x$ 和 $x - 2^k$ 是「同一個點」——它們是同一等價類的兩個名字，運算結果自然一致。跨圓環時，源圓環的一個點必須映射到目標圓環的某個點，而 signed 和 unsigned 的映射規則不同——前者保留數學值（可能是負數），後者保留位元模式。兩種映射把同一個源點送到目標圓環的不同位置，因此硬體必須提供兩套指令（`movsx` vs `movzx`）。
### Unsigned overflow 是 defined behavior，signed overflow 是 undefined behavior
- [ ] 為何 Linux 核心中 unsigned overflow 是 defined behavior，但 signed overflow 是 undefined behavior？
這是 C 語言標準（C99）的規定，不是 Linux 核心自己定義的。核心用 C 寫，自然受此約束。
#### C99 的規定
**Unsigned overflow——defined：** C99 §6.2.5 第 9 段：
> A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.
Unsigned 運算的結果自動取 $\bmod\ (max + 1)$，即 $\bmod\ 2^k$。規格書甚至說「can never overflow」——不是「溢位後 wrapping」，而是「定義上就不存在溢位」，因為結果被數學地定義為模除。
**Signed overflow——undefined：** C99 §3.4.3 將 undefined behavior 定義為「本標準不施加任何要求」的行為，第 3 段直接舉例：
> An example of undefined behavior is the behavior on integer overflow.
此處的 "integer overflow" 指的就是 signed integer overflow（因為 unsigned 已被 §6.2.5 定義為不會溢位）。
#### 為什麼標準要這樣區分
**Unsigned 只有一種表示法。** $k$ 位元 unsigned 就是純二進位，所有平台都一樣。溢位後的位元模式只有一種可能（高位被截斷），等價於 $\bmod\ 2^k$，標準可以安全地將此行為寫死。
**Signed 有三種合法表示法。** C99 §6.2.6.2 規定 signed 整數可以是以下任一種（implementation-defined）：
- Sign and magnitude（符號加絕對值）
- Two's complement（二補數）
- Ones' complement（一補數）
三種表示法的溢位行為不同。以 8-bit 的 `127 + 1` 為例：
| 表示法 | `01111111 + 1` 的位元結果 | 解讀 |
|--------|--------------------------|------|
| Two's complement | `10000000` | $-128$ |
| Ones' complement | `10000000` | $-127$ |
| Sign and magnitude | `10000000` | $-0$ |
同樣的位元操作在三種表示法下產生不同的數學值。若標準硬性規定 signed overflow 必須 wrap（像 unsigned 一樣），就必須指定 wrap 到哪個值——但這會偏袒某種表示法，使其他表示法的硬體無法符合標準，或必須插入額外指令來模擬。C 標準選擇留為 undefined behavior，讓各平台按自身硬體的自然行為處理。
#### Undefined behavior 帶來的編譯器最佳化
將 signed overflow 定為 UB 還有一個效果：編譯器可以**假設 signed overflow 永遠不會發生**，從而進行更激進的最佳化。例如對 signed `int x`：
- 編譯器可假設 `x + 1 > x` 永遠為真（因為若不為真，就是 overflow，而 overflow 是 UB，標準不管 UB 的結果）
- 迴圈 `for (int i = 0; i < n; i++)` 可假設 `i` 不會 wrap 回負數，允許向量化等最佳化
這對一般應用程式有效能好處，但對核心程式可能造成危險——編譯器可能刪掉看似「不可能到達」的溢位檢查。
#### 核心如何因應
Linux 核心在頂層 [`Makefile`](https://github.com/torvalds/linux/blob/v6.19/Makefile#L1090) 加入：
```makefile
# disable invalid "can't wrap" optimizations for signed / pointers
KBUILD_CFLAGS += -fno-strict-overflow
```
這告訴 GCC：不要假設 signed overflow 不會發生，禁止基於此假設的最佳化。核心選擇犧牲部分最佳化空間，換取可預測的行為——因為核心中有些程式碼刻意依賴 signed 的 wrapping 語意（例如序號比較）。
不過，`-fno-strict-overflow` 只是阻止編譯器利用 UB 做最佳化，並不改變 C 標準的定義。Signed overflow 在語言層級仍然是 UB，核心只是透過編譯器旗標將實際行為固定為 two's complement wrapping。
### 為何核心大量使用 unsigned long 作為時間計數器
- [ ] 為何 Linux 核心大量使用 unsigned long 作為時間計數器？
承接上題：unsigned overflow 是 C99 定義的 $\bmod\ 2^k$ wrapping，而時間計數器必然會溢位——選擇 unsigned long 正是利用這個保證。
#### `jiffies`：核心的基本時間單位
核心的全域時間計數器 `jiffies` 宣告於 [`include/linux/jiffies.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/jiffies.h#L86)：
```c
extern unsigned long volatile __cacheline_aligned_in_smp jiffies;
```
每次 timer interrupt 觸發，`jiffies` 加 1。頻率由 `HZ` 決定，[`kernel/Kconfig.hz`](https://github.com/torvalds/linux/blob/v6.19/kernel/Kconfig.hz) 提供 100、250、300、1000 四種選項，預設為 250。在 32-bit 系統上 `unsigned long` 是 32 位元，以預設 `HZ=250` 計算，$2^{32} / 250 / 86400 \approx 198.8$ 天就會 wrap 回 0——溢位是必然發生的事。
若用 signed long，溢位就是 undefined behavior（前述「unsigned 與 signed overflow」），編譯器可能產生非預期的程式碼。用 unsigned long，溢位是標準保證的 $\bmod\ 2^k$，行為完全可預測。
#### `time_after()` 巨集：unsigned 減法 + signed 轉型
核心比較兩個時間點的先後時，不能直接用 `a > b`——因為 wrap 之後數值上 `a < b`，但時間上 `a` 其實在 `b` 之後。[`include/linux/jiffies.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/jiffies.h#L130) 的解法：
```c
#define time_after(a,b) \
(typecheck(unsigned long, a) && \
typecheck(unsigned long, b) && \
((long)((b) - (a)) < 0))
```
運作原理：
1. `(b) - (a)`：兩個 unsigned long 相減，結果是 unsigned，由 C99 保證 $\bmod\ 2^k$
2. `(long)(...)`：轉型為 signed long，利用二補數的 sign bit 判斷方向
3. `< 0`：若結果為負，代表 `a` 在 `b` 之後（即使 `a` 的數值因 wrap 而小於 `b`）
以 32-bit 為例，假設 `b = 0xFFFFFFF0`，`a = 0x00000010`（`a` 已 wrap）：
- `(unsigned)(b - a) = 0xFFFFFFE0`
- `(long)0xFFFFFFE0 = -32`（負數）→ `time_after(a, b)` 為真
這個技巧能正確處理 wrap，前提是兩個時間點的差距不超過 $2^{k-1}$（即 `LONG_MAX`）。
#### 刻意提早 wrap 來抓 bug
[`include/linux/jiffies.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/jiffies.h#L317) 中：
```c
/*
* Have the 32-bit jiffies value wrap 5 minutes after boot
* so jiffies wrap bugs show up earlier.
*/
#define INITIAL_JIFFIES ((unsigned long)(unsigned int) (-300*HZ))
```
注意巨集的雙重轉型：先轉 `(unsigned int)`（32-bit）得到 `0xFFFEDB08`，再轉 `(unsigned long)`。在 32-bit 系統上 `unsigned long` 就是 32 位元，初始值離 $2^{32}$ 只剩 75000 ticks = 300 秒，5 分鐘後就會 wrap。在 64-bit 系統上，`(unsigned int)` 到 `(unsigned long)` 是 zero extension，初始值變成 `0x00000000FFFEDB08`，離 $2^{64}$ 還有 $1.84 \times 10^{19}$ 個 tick——不會 wrap。
這是刻意的設計：64-bit 系統的 `unsigned long` 本身就不會 wrap（23 億年），不需要測試；32-bit 系統才有約 199 天 wrap 的問題，`INITIAL_JIFFIES` 讓它在開機 5 分鐘後就提早觸發，若有驅動程式錯誤地用 `>` 而非 `time_after()` 比較時間，在開發階段就會暴露 bug。
#### 為什麼是 unsigned long 而非 u32 或 u64
- **`unsigned long`** 隨架構變化：32-bit 系統是 32 位元，64-bit 系統是 64 位元。這使得 `jiffies` 在 64-bit 系統上的 wrap 週期變成 $2^{64} / 250 / 86400 / 365.25 \approx 2.3 \times 10^{9}$ 年——實際上不會溢位
- 核心另外維護 `jiffies_64`（`u64`），在 32-bit 系統上需透過 [`get_jiffies_64()`](https://github.com/torvalds/linux/blob/v6.19/include/linux/jiffies.h#L89) 搭配 sequence lock 才能不可再分地讀取，開銷較大
- 大多數驅動程式只需短時間的計時（毫秒到秒級），32-bit 的 `unsigned long` 足夠且存取成本最低，因此成為預設選擇
### 質數模數構成有限域，與 AES 中 $GF(2^8)$ 的關聯
- [ ] 若模數改為質數 $p$，是否可構成有限域？這和 AES 中 $GF(2^8)$ 有何關聯？
#### 群、環、域的層次關係
先釐清代數結構的層次。群只要求**一個運算**滿足四個性質，域則要求**兩個運算**各自形成群，再用分配律連接：
| 結構 | 要求 |
|------|------|
| 群（group） | 一個運算形成群（封閉、結合、單位元素、反元素） |
| 環（ring） | 加法是阿貝爾群 + 乘法有封閉性和結合律 + 分配律 |
| **域（field）** | 加法是阿貝爾群 + **非零元素的乘法也是阿貝爾群** + 分配律 |
域 = 環 + 乘法反元素。有限域（finite field）就是元素數量有限的域，又稱 Galois field（GF），以數學家 Évariste Galois 命名。
#### $\mathbb{Z}/p\mathbb{Z}$ 是有限域
前述「固定位元與模運算」和「允許溢位與封閉性」討論的 $\mathbb{Z}/2^k\mathbb{Z}$ 在加法下是阿貝爾群（加法 $\bmod\ 2^k$），但乘法不是——因為存在零因子（例如 $2 \times 2^{k-1} \equiv 0 \pmod{2^k}$），不是所有非零元素都有乘法反元素。
若模數改為質數 $p$，元素是 $\{0, 1, \ldots, p-1\}$，加法和乘法都是 $\bmod\ p$。$\mathbb{Z}/p\mathbb{Z}$ 的非零元素 $\{1, 2, \ldots, p-1\}$ 在乘法下構成群（前述「費馬小定理與模反元素」已證明——Latin square 性質保證每個元素都有反元素）。加上加法群的性質，$\mathbb{Z}/p\mathbb{Z}$ 滿足域的全部要求：
| 性質 | $\mathbb{Z}/2^k\mathbb{Z}$（$k > 1$） | $\mathbb{Z}/p\mathbb{Z}$（$p$ 為質數） |
|------|--------------------------------------|--------------------------------------|
| $(\mathbb{Z}, +)$ 阿貝爾群 | ✓（$\bmod\ 2^k$） | ✓（$\bmod\ p$） |
| $(\mathbb{Z} \setminus \{0\}, \times)$ 阿貝爾群 | ✗（有零因子） | ✓（費馬小定理保證反元素存在） |
| 分配律 | ✓ | ✓ |
| **是否為域** | **否（環）** | **是（有限域）** |
$2^k$（$k > 1$）永遠不是質數，這正是 $\mathbb{Z}/2^k\mathbb{Z}$ 無法成為域的根本原因。
關鍵差異在於**零因子**：$p$ 為質數時，$ab \equiv 0 \pmod{p}$ 蘊含 $a \equiv 0$ 或 $b \equiv 0$（因為 $p$ 不能被分解為更小的因子）。$2^k$ 不是質數（$k > 1$ 時），所以 $\mathbb{Z}/2^k\mathbb{Z}$ 有零因子，無法成為域。
#### $GF(2^8)$ 不是 $\mathbb{Z}/256\mathbb{Z}$
[AES](https://zh.wikipedia.org/wiki/%E9%AB%98%E7%BA%A7%E5%8A%A0%E5%AF%86%E6%A0%87%E5%87%86) 加密以 byte（8 位元，256 個值）為單位處理資料。AES 的 S-box 需要對每個 byte 計算**乘法反元素**——這要求 256 個元素構成一個**域**。但 $2^8 = 256$ 不是質數，所以 $\mathbb{Z}/256\mathbb{Z}$ 不是域，不能直接用。
有限域理論保證：對任何質數 $p$ 和正整數 $n$，都存在恰好有 $p^n$ 個元素的有限域 $GF(p^n)$。因此存在一個有 $2^8 = 256$ 個元素的有限域 $GF(2^8)$，但構造方式不是用整數模除，而是**多項式模除**。
$GF(2^8)$ 的構造：
- 基礎域：$GF(2) = \{0, 1\}$，即 $\mathbb{Z}/2\mathbb{Z}$（模 2 算術，加法就是 XOR）
- 元素：$GF(2)$ 上次數小於 8 的多項式，如 $x^7 + x^3 + 1$，共 $2^8 = 256$ 個
- 加法：多項式係數逐項 XOR（因為 $GF(2)$ 中 $1 + 1 = 0$）
- 乘法：多項式相乘後模一個**不可約多項式**（irreducible polynomial），使結果保持在次數 < 8 的範圍內
AES 規範（[FIPS 197](https://csrc.nist.gov/pubs/fips/197/final) §4.2）選用的不可約多項式是 $m(x) = x^8 + x^4 + x^3 + x + 1$（十六進位 `0x11b`，需要 9 個位元表示）。「不可約」意味著它在 $GF(2)$ 上無法分解為更低次多項式的乘積——類似於質數在整數中不可分解。這確保了模除後的乘法具有封閉性且每個非零元素都有反元素。不管金鑰長度是 128、192 或 256 位元，所有 AES 變體內部的 byte 運算都在同一個 $GF(2^8)$ 上進行，使用同一個不可約多項式；金鑰長度影響的是輪數（10/12/14 輪）和金鑰排程，不影響域的選擇。
對比：
| | $\mathbb{Z}/p\mathbb{Z}$ | $GF(p^n)$ |
|---|---|---|
| 元素 | 整數 $\{0, \ldots, p-1\}$ | $GF(p)$ 上的多項式 |
| 加法 | 整數加法 $\bmod p$ | 多項式係數逐項 $\bmod p$ |
| 乘法 | 整數乘法 $\bmod p$ | 多項式乘法 $\bmod m(x)$ |
| 保證封閉的機制 | $p$ 是質數 | $m(x)$ 是不可約多項式 |
兩者的共通結構是：用一個「不可分解的東西」做模除，消除零因子，使非零元素在乘法下形成群。
#### AES 為何選擇 $GF(2^8)$
AES 處理的資料單位是 byte（8 位元），恰好是 $GF(2^8)$ 的 256 個元素。$GF(2^8)$ 的兩個運算特性使其適合硬體實作：
- **加法是 XOR**：不需進位，單一時脈週期完成
- **乘以 $x$（即 `0x02`）是左移一位，溢位時 XOR `0x1b`**
Linux 核心的 AES 實作（[`lib/crypto/aes.c`](https://github.com/torvalds/linux/blob/v6.19/lib/crypto/aes.c#L92)）中，`mul_by_x` 正是這個操作：
```c
static u32 mul_by_x(u32 w)
{
u32 x = w & 0x7f7f7f7f;
u32 y = w & 0x80808080;
/* multiply by polynomial 'x' (0b10) in GF(2^8) */
return (x << 1) ^ (y >> 7) * 0x1b;
}
```
`0x7f7f7f7f` 遮罩取出每個 byte 的低 7 位元（可安全左移），`0x80808080` 取出最高位元。若最高位元為 1，左移後會超出 8 位元（等同多項式乘以 $x$ 後次數 $\geq 8$），需 XOR `0x1b`（即模 $m(x)$ 的約化）。注意程式中用的是 `0x1b` 而非完整多項式的 `0x11b`——因為溢位時 $x^8$ 項一定為 1（否則不會溢位），XOR 時 $x^8$ 與 $x^8$ 互消，只需處理低 8 位元 $x^4 + x^3 + x + 1$ = `0x1b`。這個函式同時對 4 個 byte 平行運算，用於 MixColumns 的矩陣乘法（[第 111 行](https://github.com/torvalds/linux/blob/v6.19/lib/crypto/aes.c#L111)）。
S-box 則是 $GF(2^8)$ 乘法反元素加上仿射轉換的查表實作（[第 16 行](https://github.com/torvalds/linux/blob/v6.19/lib/crypto/aes.c#L16)），核心使用預先計算好的 256-byte 查找表，不在 runtime 計算反元素。
### 二補數構成環但非域，對除法的限制
- [ ] 二補數構成環但非域，這對除法有何限制？找出 Linux 核心原始程式碼對應的案例
#### 直接回答：環非域 → 乘法沒有反元素 → 除法不封閉
前述「質數模數與有限域」已證明 $\mathbb{Z}/2^k\mathbb{Z}$ 是交換環但非域——因為存在零因子（例如 $2 \times 2^{k-1} \equiv 0$），不是所有非零元素都有乘法反元素。環的乘法只需要封閉性、結合律和單位元素（么半群），不要求反元素；域則進一步要求非零元素在乘法下構成阿貝爾群（含反元素）。
推論鏈：
> **成環但非域** → 乘法沒有通用的反元素 → 除法 $a \div b = a \times b^{-1}$ 無法對所有非零 $b$ 定義 → **除法不封閉**
除法不封閉的意思是：$a \div b$ 的結果可能落在 $\{0, 1, \ldots, 2^k - 1\}$ 之外（例如 $7 \div 2 = 3.5$，不是整數）。加法和乘法的結果會透過溢位（$\bmod 2^k$）自動落回環內，但除法沒有這種天然機制——核心必須用軟體策略把結果映射回去。
#### 核心原始碼中的對策
列舉 [`include/linux/math.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/math.h)、[`include/linux/math64.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/math64.h)、[`lib/math/div64.c`](https://github.com/torvalds/linux/blob/v6.19/lib/math/div64.c) 中的除法相關 API：
| 核心 API | 對應的限制 | 策略 |
|----------|-----------|------|
| [`mult_frac`](https://github.com/torvalds/linux/blob/v6.19/include/linux/math.h#L135)、[`DIV_ROUND_UP`](https://github.com/torvalds/linux/blob/v6.19/include/uapi/linux/const.h#L51)、[`DIV_ROUND_CLOSEST`](https://github.com/torvalds/linux/blob/v6.19/include/linux/math.h#L92) | 截斷遺失資訊 | 拆商餘組合；補償截斷方向 |
| [`div_s64_rem`](https://github.com/torvalds/linux/blob/v6.19/lib/math/div64.c#L67)、[`div64_s64`](https://github.com/torvalds/linux/blob/v6.19/lib/math/div64.c#L161) | 有號溢位（$\texttt{INT\_MIN} \div (-1)$） | 轉無號再處理符號 |
| [`__div64_const32`](https://github.com/torvalds/linux/blob/v6.19/include/asm-generic/div64.h#L65) | 反元素不存在 | 倒數近似 + 偏置補償 |
| [`do_div`](https://github.com/torvalds/linux/blob/v6.19/include/asm-generic/div64.h#L45)、[`__div64_32`](https://github.com/torvalds/linux/blob/v6.19/lib/math/div64.c#L32) | 32-bit 無 64-bit 除法 | 軟體長除法 |
| [`__iter_div_u64_rem`](https://github.com/torvalds/linux/blob/v6.19/include/vdso/math64.h#L6)、[`DIV_ROUND_UP_POW2`](https://github.com/torvalds/linux/blob/v6.19/include/linux/math.h#L46) | 效能 | 迭代減法；位元遮罩替代 |
### 二補數是否本質上是種 algebraic encoding
- [ ] 二補數的設計是否本質上是種 algebraic encoding？
從題目脈絡——前面幾題已建立群、環、域的概念——推測老師要問的是：二補數是否為一種**保持代數結構的編碼**，即整數到位元模式的對應，是否保持了加法和乘法的運算關係。要回答這個問題，需要先釐清三個層次的定義。
#### 第一層：什麼是代數結構
代數結構（algebraic structure）是一個集合 $S$ 配上若干運算，且運算滿足特定公理。前面幾題已經用到的三種代數結構：
| 結構 | 定義 | 範例 |
|------|------|------|
| 群（group） | $(S, \circ)$：封閉性、結合律、單位元素、反元素 | $(\mathbb{Z}/2^k\mathbb{Z}, +)$（前述「固定位元與模運算」） |
| 環（ring） | $(S, +, \times)$：加法是阿貝爾群 + 乘法有封閉性和結合律 + 分配律 | $(\mathbb{Z}/2^k\mathbb{Z}, +, \times)$（前述「環非域與除法限制」） |
| 域（field） | 環 + 非零元素的乘法也是阿貝爾群 | $\mathbb{Z}/p\mathbb{Z}$、$GF(2^8)$（前述「質數模數與有限域」） |
代數結構的核心是：**集合 + 運算 + 公理**，三者缺一不可。同一個集合配上不同運算或不同公理，就是不同的代數結構。
#### 第二層：什麼是「保持結構」的映射
兩個代數結構之間的映射，若能保持運算關係，稱為**同態**（homomorphism）。
對環同態 $\varphi: (R_1, +, \times) \to (R_2, +, \times)$，要求：
$$\varphi(a + b) = \varphi(a) + \varphi(b), \quad \varphi(a \times b) = \varphi(a) \times \varphi(b)$$
也就是「先運算再映射」和「先映射再運算」的結果相同。
以整數除以 8 為例：$\ldots, -8, 0, 8, 16, \ldots$ 除以 8 餘數都是 0，歸為同一等價類 $[0]$。整數 $\mathbb{Z}$ 被分成 8 個等價類 $[0], [1], \ldots, [7]$，這些等價類本身構成一個新的環——商環 $\mathbb{Z}/8\mathbb{Z}$。記號中的 $/$ 就是「除以」的隱喻：把大的結構除以子結構，得到更小的結構。
#### 第三層：二補數是環同態的直接結果
現在可以回答核心問題了。證明鏈如下：
**步驟 1：** $(\mathbb{Z}, +, \times)$ 是交換環（整數在加法和乘法下的基本性質）。
**步驟 2：** 定義自然投影 $\pi: \mathbb{Z} \to \mathbb{Z}/2^k\mathbb{Z}$，$\pi(a) = a \bmod 2^k$。
**步驟 3：** $\pi$ 是環同態——保持加法和乘法：
$$\pi(a + b) = (a + b) \bmod 2^k = (\pi(a) + \pi(b)) \bmod 2^k$$
$$\pi(a \times b) = (a \times b) \bmod 2^k = (\pi(a) \times \pi(b)) \bmod 2^k$$
這是模運算的基本性質，成立的原因是 $2^k\mathbb{Z}$（所有 $2^k$ 的倍數）構成 $\mathbb{Z}$ 的理想。
**步驟 4：** 商環 $\mathbb{Z}/2^k\mathbb{Z}$ 有 $2^k$ 個等價類。每個等價類可選擇不同的代表元素：
| 等價類 | unsigned 代表元 | signed（二補數）代表元 |
|--------|----------------|---------------------|
| $[0]$ | $0$ | $0$ |
| $[1]$ | $1$ | $1$ |
| $\vdots$ | $\vdots$ | $\vdots$ |
| $[2^{k-1}]$ | $2^{k-1}$ | $-2^{k-1}$ |
| $\vdots$ | $\vdots$ | $\vdots$ |
| $[2^k - 1]$ | $2^k - 1$ | $-1$ |
兩組代表元是同一商環的**不同完全剩餘系**（complete residue system）。Unsigned 選 $\{0, \ldots, 2^k - 1\}$，signed 選 $\{-2^{k-1}, \ldots, 2^{k-1} - 1\}$。
**關鍵：** 代表元的選擇不影響商環的代數結構。對任意 $a, b$ 及其代表元 $a', b'$（可能是 unsigned 的也可能是 signed 的），只要 $[a'] = [a]$ 且 $[b'] = [b]$，就有：
$$[a'] + [b'] = [a] + [b] = [a + b]$$
這就是為什麼同一套加法器電路對 unsigned 和 signed 都正確——電路操作的是等價類（位元模式），不在乎選了哪個代表元。
#### 結論：二補數是 algebraic encoding
二補數不是任意選擇的位元對應方式，而是以下數學結構的直接結果：
1. 硬體的 $k$ 位元限制自然產生商環 $\mathbb{Z}/2^k\mathbb{Z}$（前述「固定位元與模運算」）
2. 自然投影 $\pi$ 是環同態，保證運算在商環中定義良好（前述「允許溢位與封閉性」）
3. 二補數只是在這個商環中選擇了包含負數的代表元——代數結構完全不變
因此，二補數本質上確實是一種 algebraic encoding：它是環同態下的商結構，選擇不同的等價類代表元來表示有號整數。設計者不是在做位元技巧，而是（有意或無意地）遵循了代數結構的自然映射。前面幾節的討論——群性質（「固定位元與模運算」「允許溢位與封閉性」）、反元素存在性（「費馬小定理與模反元素」）、同圓環不需區分符號（「跨圓環搬移與 sign extension」）——全部都是這個代數結構的不同面向。
### $\mathbb{Z}/2^{64}$ 上的系統時間安全極限
- [ ] 若將系統時間設計於 $\mathbb{Z}/2^{64}$ 上，其安全極限為何？
安全極限取決於**時間單位的精度**——同樣是 64 位元，選擇不同的計時單位，wrap 週期差距極大：
| 時間單位 | unsigned $2^{64}$ | signed $2^{63}$ |
|---------|-------------------|-----------------|
| 秒（`time64_t`） | $5.85 \times 10^{11}$ 年 | $2.92 \times 10^{11}$ 年 |
| jiffies（HZ=250） | $2.34 \times 10^{9}$ 年 | $1.17 \times 10^{9}$ 年 |
| 微秒（μs） | $5.85 \times 10^{5}$ 年 | $2.92 \times 10^{5}$ 年 |
| **奈秒（ns，`ktime_t`）** | **585 年** | **292 年** |
以秒為單位，$2^{63}$ 秒約 2920 億年，遠超[宇宙年齡](https://zh.wikipedia.org/wiki/%E5%AE%87%E5%AE%99%E5%B9%B4%E9%BD%A1)（約 138 億年），實務上不會溢位。但核心的高精度計時器 `ktime_t` 是 **signed 64-bit 奈秒**（`s64`），安全極限只有約 **292 年**——這不是天文數字，而是工程上必須處理的限制。
#### 核心如何定義這些型別
`ktime_t` 的定義在 [`include/linux/types.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/types.h#L127)：
```c
typedef s64 ktime_t;
```
`time64_t` 和相關常數定義在 [`include/linux/time64.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/time64.h#L8)：
```c
typedef __s64 time64_t;
typedef __u64 timeu64_t;
#define KTIME_MAX ((s64)~((u64)1 << 63))
#define KTIME_SEC_MAX (KTIME_MAX / NSEC_PER_SEC)
```
`KTIME_MAX` 就是 $2^{63} - 1$（`s64` 的最大值），`KTIME_SEC_MAX` 則是 $\lfloor (2^{63} - 1) / 10^9 \rfloor$ 秒——約 292 年又 3 個月。
#### 核心對 292 年極限的因應措施
核心開發者清楚意識到這個限制。[`include/linux/time64.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/time64.h#L35) 第 35–44 行：
```c
/*
* Limits for settimeofday():
*
* To prevent setting the time close to the wraparound point time setting
* is limited so a reasonable uptime can be accomodated. Uptime of 30 years
* should be really sufficient, which means the cutoff is 2232. At that
* point the cutoff is just a small part of the larger problem.
*/
#define TIME_UPTIME_SEC_MAX (30LL * 365 * 24 *3600)
#define TIME_SETTOD_SEC_MAX (KTIME_SEC_MAX - TIME_UPTIME_SEC_MAX)
```
核心限制 `settimeofday()` 可設定的最大時間為 `KTIME_SEC_MAX - 30 年`，確保即使系統連續運行 30 年，`ktime_t` 也不會 wrap。換算下來，`settimeofday()` 的上限大約是西元 **2232 年**。註解中 "At that point the cutoff is just a small part of the larger problem" 意味著：到了 2232 年，如果人類還在用同一套時間系統，292 年的 `ktime_t` 極限只是眾多需要解決的問題之一。
#### 不同時間型別的設計取捨
核心中的時間型別各有不同的精度與範圍取捨：
| 型別 | 定義 | 單位 | 範圍 | 用途 |
|------|------|------|------|------|
| `ktime_t` | `s64` | 奈秒 | ±292 年 | 高精度計時器（hrtimer） |
| `time64_t` | `__s64` | 秒 | ±2920 億年 | 檔案時間戳、wall clock |
| `jiffies` | `unsigned long` | 1/HZ 秒 | 23 億年（64-bit） | 排程器、粗略計時 |
這體現了 $\mathbb{Z}/2^{64}$ 上的根本取捨：**精度越高，範圍越窄**。奈秒精度讓 `ktime_t` 適合微秒級的計時需求（排程、中斷處理），但代價是 292 年的範圍限制。秒精度的 `time64_t` 範圍幾乎無限，但無法處理亞秒級計時。`jiffies` 則介於兩者之間，用 unsigned 避免 signed overflow 的 UB 問題（前述「unsigned 與 signed overflow」）。
### 證明 $(\mathbb{Z}/2^k\mathbb{Z}, +)$ 為阿貝爾群，但 $(\mathbb{Z}/2^k\mathbb{Z}, \times)$ 非群
- [ ] 證明 $(\mathbb{Z}/2^k\mathbb{Z}, +)$ 為阿貝爾群，但 $(\mathbb{Z}/2^k\mathbb{Z}, \times)$ 非群
#### $(\mathbb{Z}/2^k\mathbb{Z}, +)$ 是阿貝爾群
令 $S = \{0, 1, \ldots, 2^k - 1\}$，加法定義為 $(a + b) \bmod 2^k$。逐一驗證五個性質：
1. **封閉性：** $a, b \in S \implies 0 \leq a + b < 2^{k+1}$，取 $\bmod\ 2^k$ 後結果落在 $\{0, \ldots, 2^k - 1\} = S$。這就是前述「允許溢位與封閉性」討論的：硬體捨棄高位元 = $\bmod\ 2^k$，結果自動落回集合。
2. **結合律：** $((a + b) + c) \bmod 2^k = (a + (b + c)) \bmod 2^k$。成立因為整數加法滿足結合律，而 $\bmod$ 運算與加法的順序無關。
3. **單位元素：** $0 \in S$，且 $(a + 0) \bmod 2^k = a$ 對所有 $a \in S$ 成立。
4. **反元素：** 對任意 $a \in S$，取 $-a \equiv (2^k - a) \bmod 2^k$。當 $a = 0$ 時反元素是 $0$；當 $a \neq 0$ 時 $2^k - a \in \{1, \ldots, 2^k - 1\} \subset S$，且 $(a + (2^k - a)) \bmod 2^k = 2^k \bmod 2^k = 0$。每個元素都有反元素。
5. **交換律：** $(a + b) \bmod 2^k = (b + a) \bmod 2^k$。成立因為整數加法滿足交換律。
五個性質全部滿足，$(\mathbb{Z}/2^k\mathbb{Z}, +)$ 是阿貝爾群。$\blacksquare$
#### $(\mathbb{Z}/2^k\mathbb{Z}, \times)$ 非群
只需找到一個性質不成立即可。以下證明**反元素不存在**。
取 $k > 1$（$k = 1$ 時 $S = \{0, 1\}$，$0$ 沒有反元素，同樣非群）。考慮元素 $2$ 和 $2^{k-1}$，兩者都是 $S$ 的非零元素，但：
$$2 \times 2^{k-1} = 2^k \equiv 0 \pmod{2^k}$$
兩個非零元素相乘得到零——$2$ 和 $2^{k-1}$ 是**零因子**（zero divisor）。
零因子不可能有乘法反元素：假設 $2^{-1}$ 存在，對 $2 \times 2^{k-1} \equiv 0$ 兩邊乘以 $2^{-1}$，得到 $2^{k-1} \equiv 0$，但 $2^{k-1} \neq 0$（因為 $k > 1$ 時 $0 < 2^{k-1} < 2^k$），矛盾。因此 $2$ 沒有乘法反元素。
反元素性質不成立，$(\mathbb{Z}/2^k\mathbb{Z}, \times)$ 不是群。$\blacksquare$
## 探討〈你所不知道的 C 語言：指標篇〉
### 回傳區域變數位址的未定義行為
- [ ] 根據 C99 對 object 的定義，請分析以下程式是否具有未定義行為，並說明理由 `int *foo(void) { int x = 10; return &x; }`
`foo` 中的 `x` 沒有 linkage，也沒有 `static` 修飾，依 C99 §6.2.4¶4：
> An object whose identifier is declared with no linkage and without the storage-class specifier `static` has *automatic storage duration*.
automatic storage duration 的 lifetime 規則定義於 §6.2.4¶5：
> its lifetime extends from entry into the block with which it is associated until execution of that block ends in any way.
`foo` 執行 `return &x;` 後，函式的 block 結束，`x` 的 lifetime 隨之結束。而 §6.2.4¶2 明確指出：
> If an object is referred to outside of its lifetime, the behavior is undefined.
因此 caller 拿到的指標指向一個 lifetime 已結束的 object。對該指標做 dereference，就是在 lifetime 外存取 object——未定義行為。
#### 1. 若改成 `static int x = 10;` 結果是否改變？
改變。加上 `static` 後，`x` 的 storage duration 從 automatic 變為 static。§6.2.4¶3：
> An object whose identifier is declared with ... the storage-class specifier `static` has *static storage duration*. Its lifetime is the entire execution of the program.
`x` 的 lifetime 涵蓋整個程式執行期間，`foo` 回傳後該 object 仍然存在。caller dereference 回傳的指標，存取的是一個仍在 lifetime 內的 object，行為完全合法。
#### 2. 請用 storage duration 與 lifetime 兩個術語解釋差異
兩個版本的 `foo` 差異在於 `x` 的 **storage duration** 不同，導致 **lifetime** 不同，最終決定回傳指標的有效性。
未加 `static` 的 `x` 具有 automatic storage duration（§6.2.4¶4），其 lifetime 在所屬 block 結束時結束（§6.2.4¶5）。`foo` return 後 `x` 的 lifetime 已結束，caller 持有的指標指向一個不再存活的 object，dereference 是未定義行為。
加上 `static` 後，`x` 具有 static storage duration（§6.2.4¶3），其 lifetime 是整個程式執行期。`foo` return 後 `x` 仍然存活，caller dereference 回傳的指標完全合法。
一個關鍵字 `static` 改變了 storage duration 的分類，進而改變了 lifetime 的範圍，使得相同的 `return &x;` 從未定義行為變為合法操作。
#### 3. 為何規格明確指出指標值變為 indeterminate？
> The value of a pointer becomes indeterminate when the object it points to reaches the end of its lifetime.
§6.2.4¶2 已經規定「在 lifetime 外存取 object 是 UB」，但規格額外加上這句話，是因為它針對的不是 dereference，而是**指標本身的值**。一個指向 lifetime 已結束之 object 的指標，其值是 indeterminate——即使不 dereference，僅僅比較或複製該指標，行為也是未定義的。
規格之所以特別強調這一點，是因為實務上 stack 記憶體可能尚未被覆寫，指標「看起來」仍然有效。但 C 語言的語意模型中，lifetime 結束就是結束，與底層記憶體是否已被回收無關。編譯器在最佳化時可以依據此規則，假設程式不會持有指向已結束 lifetime 之 object 的指標，進而產生出乎預期的結果。
### `sizeof` 對 array 與 pointer 的差異
- [ ] 以下程式的輸出為何？ `int a[3] = {1,2,3}; int *p = a; printf("%zu %zu\n", sizeof(a), sizeof(p));`
輸出為 `12 8`（以 `gcc -std=c99 -Wall` 編譯執行驗證）。`sizeof(a)` 量的是陣列本身的大小（3 × 4 = 12 bytes），`sizeof(p)` 量的是指標變數本身的大小（x86-64 上為 8 bytes）。
#### 1. 為何 array 在 expression 中會 decay 成 pointer，但在 `sizeof` 中不會？
C99 §6.3.2.1¶3：
> Except when it is the operand of the **`sizeof`** operator or the unary **`&`** operator, or is a string literal used to initialize an array, an expression that has type "array of *type*" is converted to an expression with type "pointer to *type*" that points to the initial element of the array object and is not an lvalue.
規格以「Except」明確列出三個例外：`sizeof`、`&`、以及用來初始化陣列的字串常量。在這三個情境中，array 保留原本的型別不做轉換。因此 `sizeof(a)` 中的 `a` 維持 `int [3]` 型別，算出 3 × `sizeof(int)` = 12；而 `int *p = a;` 中的 `a` 不在例外清單內，decay 為 `int *`，`sizeof(p)` 量的是指標本身 = 8。
#### 2. 為何 `&a` 與 `a` 的值相同但型別不同？
`a` 在一般 expression 中 decay 為 `int *`（§6.3.2.1¶3），指向陣列的第一個元素。
`&a` 中的 `a` 是 `&` 運算子的運算元——同樣被 §6.3.2.1¶3 的 "Except" 排除，不做 decay，保留 `int [3]` 型別。再依 §6.5.3.2¶3：
> The unary `&` operator yields the address of its operand. If the operand has type "*type*", the result has type "pointer to *type*".
運算元型別為 `int [3]`，所以 `&a` 的型別是 `int (*)[3]`（指向整個陣列的指標）。
兩者的數值相同（都是陣列起始位址），但型別不同，差異體現在 pointer arithmetic 上：
- `a + 1`（`int *`）→ 前進 `sizeof(int)` = 4 bytes，指向 `a[1]`
- `&a + 1`（`int (*)[3]`）→ 前進 `sizeof(int [3])` = 12 bytes，指向整個陣列之後
#### 3. 用 Graphviz 繪製記憶體示意圖說明以上
### Pointer arithmetic 與 strict aliasing
- [ ] 分析： `double x[3]; int *p = (int *)&x[0]; printf("%d\n", *(p+1));`
`x[0]` 的位址被強制轉型為 `int *` 並指派給 `p`。`p+1` 前進 `sizeof(int)` = 4 bytes，指向 `x[0]` 的第 4~7 byte（`double` 佔 8 bytes）。`*(p+1)` 將該記憶體區段的 bit pattern 當作 `int` 印出。
此外 `x[3]` 未初始化，其值為 indeterminate（§6.2.4¶5：automatic storage duration 的 object，初始值是 indeterminate），讀取 indeterminate value 本身即是未定義行為。
即使將 `x[0]` 初始化，這段程式仍有更根本的問題——違反 strict aliasing rule。
#### 1. 為何 pointer arithmetic 的單位取決於 type？
C99 §6.5.6¶8：
> When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression.
規格定義 pointer arithmetic 以「元素」為單位，而非 byte。`p+1` 是指向下一個元素，元素的大小由指標的型別決定。`int *p` 的 `p+1` 前進 `sizeof(int)` bytes，`double *p` 的 `p+1` 前進 `sizeof(double)` bytes。
§6.5.6¶7 進一步指出：
> a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.
指標與陣列在 C 語言中緊密相關，pointer arithmetic 的設計就是為了讓指標能自然地走訪陣列元素。
#### 2. 這是否涉及 strict aliasing 問題？
是。C99 §6.5¶7（即 strict aliasing rule）：
> An object shall have its stored value accessed only by an lvalue expression that has one of the following types:
> - a type compatible with the effective type of the object,
> - a qualified version of a type compatible with the effective type of the object,
> - a type that is the signed or unsigned type corresponding to the effective type of the object,
> - a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
> - an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or
> - a character type.
`x[0]` 的 effective type 是 `double`，但 `*(p+1)` 透過 `int` 型別的 lvalue 去存取——`int` 與 `double` 不是 compatible type，也不是對應的 signed/unsigned 版本，更不是 character type。不在允許清單內，因此是**未定義行為**。
規格唯一允許的「萬用」存取型別是 **character type**（`char`、`unsigned char`、`signed char`），這也是 `memcpy` 能合法運作的原因。
#### 3. 在 ARMv5 或 RISC-V 上可能出現什麼錯誤？
除了 strict aliasing 造成的語言層級 UB 外，不同硬體架構對記憶體存取有不同的 alignment 要求，同一段程式在不同架構上可能產生截然不同的行為。
**ARMv5**（參考 ARM Architecture Reference Manual [[3]](https://developer.arm.com/documentation/ddi0406/c), Appendix ARMv4 and ARMv5 Differences）：
ARMv5 不支援 unaligned memory access。LDR 指令對非 word-aligned 位址的行為：
- 硬體將位址強制對齊（`addr AND NOT 3`），讀取該對齊位址的 word，再對資料做 byte rotation（`ROR (addr AND 3) * 8`）——讀到的不是預期的資料，而是被旋轉過的值
- 若啟用 alignment checking（SCTLR 的 A bit），直接觸發 **alignment fault**，程式收到 bus error
ARMv6 之後才對大部分單一 load/store 指令支援 unaligned access（見 [[3]](https://developer.arm.com/documentation/ddi0406/c) §A3.2.1 Unaligned data access；LDM/STM/LDRD/STRD 在 ARMv6+ 仍要求對齊，見 [[3]](https://developer.arm.com/documentation/ddi0406/c) §A3.2.1 Unaligned data access restrictions）。
**RISC-V**（參考 RISC-V Instruction Set Manual, Privileged Architecture [[4]](https://riscv.github.io/riscv-isa-manual/snapshot/privileged/)）：
RISC-V 的基本整數指令集（RV32I/RV64I）允許實作自行決定是否支援 misaligned access。Privileged spec 定義了 `mcause` 中的 exception cause：
- **Load address misaligned**（cause 4）
- **Store/AMO address misaligned**（cause 6）
多數嵌入式 RISC-V 核心不支援硬體 unaligned access，會觸發 address-misaligned exception，trap 到軟體模擬處理。
### Call-by-value 與指標的指標
- [ ] 解釋為何以下程式不會改變 main 中的 ptrA： `void func(int *p) { p = &B; }` 並分析 `void func(int **p) { *p = &B; }`
C 語言所有的函式參數傳遞都是 call-by-value。呼叫 `func(ptrA)` 時，傳入的是 `ptrA` 的**值**（即 `A` 的位址），而非 `ptrA` 這個變數本身的位址。`func` 內的 `p` 是一份獨立的複本，`p = &B` 只修改了這份複本，`main` 中的 `ptrA` 完全不受影響。
若要在 `func` 內改變 `ptrA` 的指向，必須傳入 `ptrA` 本身的位址，也就是 `func(&ptrA)`。此時 `p` 的型別是 `int **`，存放的是 `ptrA` 的位址。`*p = &B` 透過 `p` 找到 `ptrA`，將其內容改為 `&B`，成功改變了 `main` 中 `ptrA` 的指向。
#### 1. 用 call-by-value 解釋
C99 §6.5.2.2¶4：
> An argument may be an expression of any object type. In preparing for the call to a function, the arguments are evaluated, and each parameter is assigned the value of the corresponding argument.
每個參數都是「被指派」——是值的複製，不是變數的別名。因此：
- `func(int *p)` 中 `p` 收到的是 `ptrA` 的值（`&A`）的複本。修改 `p` 只改了複本，`ptrA` 不變
- `func(int **p)` 中 `p` 收到的是 `&ptrA` 的值的複本。但透過 `*p` 可以間接存取 `ptrA` 本身，`*p = &B` 改變了 `ptrA` 的內容
這不是特例——C 語言沒有 call-by-reference，一切都是 call-by-value。「傳指標」只是把位址當作值來傳，本質上仍是複製。
#### 2. 用 Graphviz 繪製 stack frame 示意圖
`void func(int *p) { p = &B; }` — `p = &B` 只改了 func 的區域變數，`ptrA` 不變：
`void func(int **p) { *p = &B; }` — `*p = &B` 透過 `p` 找到 `ptrA`，改變其指向：
#### 3. 為何「雙指標」這個說法在語意上不精確？
「雙指標」暗示有**兩個指標**，但 `int **p` 是**一個指標**，其 target type 恰好也是指標型別。`*` 的數量描述的是 indirection 的**深度**，不是指標的**個數**：
- `int *p` — 一個指標，指向 `int`
- `int **p` — 一個指標，指向 `int *`
兩者都是一個指標變數，差別只在所指向的型別。此外「雙指標」也容易與 `double *`（指向 `double` 的指標）混淆。精確的說法應為「指標的指標」（pointer to pointer）。
### Function designator 的轉換規則
- [ ] 解釋為何以下程式合法： `int main() { return (********puts)("Hello"); }`
`(********puts)("Hello")` 對 `puts` 做了 8 次 dereference 後呼叫，程式合法且行為與 `puts("Hello")` 完全相同。原因在於 function designator 與 function pointer 之間的自動轉換規則。
撰寫 [`func_designator.c`](https://github.com/laneser/warmup/blob/main/func_designator.c) 驗證（`make func_designator_report`）：
```
puts = 0x73a16094dbe0
*puts = 0x73a16094dbe0
&puts = 0x73a16094dbe0
********puts= 0x73a16094dbe0
fp = 0x73a16094dbe0
*fp = 0x73a16094dbe0
&fp = 0x7ffdb0d4d640
```
`puts`、`*puts`、`&puts`、`********puts` 全部是同一個位址。唯一不同的是 `&fp`——取的是 function pointer **變數**的位址，而非函式的位址。
#### 1. 依據 C99 6.3.2.1 說明 function designator 的轉換規則
C99 §6.3.2.1¶4：
> A function designator is an expression that has function type. Except when it is the operand of the `sizeof` operator or the unary `&` operator, a function designator with type "function returning *type*" is converted to an expression that has type "pointer to function returning *type*".
`puts` 是 function designator，在除了 `sizeof` 和 `&` 以外的所有語境中，自動轉換為 function pointer。
#### 2. 為何 `*` 的數量不影響結果？
每次 `*` dereference 一個 function pointer，得到的是 function designator（function type 的 expression）。而 §6.3.2.1¶4 規定 function designator 會自動轉回 function pointer。這形成一個無限循環：
1. `puts`：function designator → 自動轉成 function pointer
2. `*puts`：dereference function pointer → 得到 function designator → 自動轉回 function pointer
3. `**puts`：同上，再來一次
4. 不管幾個 `*`，結果都是同一個 function pointer
最終 `()` 呼叫運算子作用在 function pointer 上，完成函式呼叫。C 語言中所有的函式呼叫，底層都是 `()` 作用在 function pointer 上——即使寫 `puts("Hello")`，`puts` 也是先自動轉成 function pointer 再呼叫。
#### 3. 若對 function pointer 使用 `&` 會發生什麼？
需要區分對象是 function designator 還是 function pointer 變數：
**對 function designator（如 `puts`）使用 `&`：**
`&` 是 §6.3.2.1¶4 中的例外，`puts` 不做自動轉換，保留 function type。§6.5.3.2¶3 規定 `&` 取其位址，得到 function pointer。值與 `puts` 自動轉換的結果相同。
**對 function pointer 變數（如 `fp`）使用 `&`：**
`fp` 是一個普通的指標變數，`&fp` 取的是該變數在 stack 上的位址，型別為 `int (**)(const char *)`（pointer to function pointer）。值不同於 `fp`，多了一層 indirection。
驗證結果中 `&puts` = `0x...dbe0`（函式位址），而 `&fp` = `0x...d640`（變數位址），兩者不同。
### 儲存-執行模型與指標的本質
- [ ] 從「儲存-執行模型」角度解釋 `int a = 10; char *p = (char *)&a;`
〈[你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer)〉將計算機分為兩類：
1. **儲存-執行模型**（CPU + 記憶體）— 指令與資料皆儲存在記憶體中，CPU 透過位址匯流排存取。通用但間接
2. **特製硬體**（ASIC / FPGA）— 邏輯直接實作在電路中，不需從記憶體讀取指令。高效但不通用
C 語言是為儲存-執行模型設計的。在這個模型中，CPU 無法直接操作記憶體中的數值，必須透過位址存取——這就是指標存在的根本原因。
`int a = 10; char *p = (char *)&a;` 所做的事：將數值 10 寫入記憶體某處，再將該位址存入另一處記憶體。整個過程就是「給定位址，讀寫資料」的重複。
#### 1. CPU 實際做哪些事？
對應的 x86-64 機械碼與組合語言（`gcc -std=c99 -O0` 編譯後以 `objdump -d -M intel` 反組譯）：
```
1b: c7 45 ec 0a 00 00 00 mov DWORD PTR [rbp-0x14],0xa ; int a = 10
22: 48 8d 45 ec lea rax,[rbp-0x14] ; &a
26: 48 89 45 f0 mov QWORD PTR [rbp-0x10],rax ; char *p = ...
```
`(char *)` 強制轉型**不產生任何 CPU 指令**。位址的值不變，轉型只告訴 compiler 後續對 `p` 做 dereference 時按 1 byte（`char`）而非 4 bytes（`int`）存取。型別系統是編譯期的抽象，CPU 只看位址和資料寬度。
#### 2. 為何 C 語言可以被視為 assembly 的語法抽象？
教材原文：
> C 語言本質上就是組合語言的簡化版本，它延續組合語言的邏輯，用指標創造世界。
C 語言的構件幾乎一對一對應到硬體操作：
| C 語言 | 硬體 / 組合語言 |
|:---|:---|
| 變數 | 記憶體位址（stack 或 data segment） |
| 型別 | 決定指令選擇（`add` vs `fadd`）與存取寬度 |
| 指標 | 原始記憶體位址 |
| `*p`（dereference） | 間接定址（indirect addressing） |
| 函式呼叫 | `call` 指令 + stack frame |
其他高階語言（Java、Python）刻意隱藏記憶體位址，提供垃圾回收等抽象層。C 語言選擇不隱藏——它直接暴露儲存-執行模型的運作方式，讓程式設計師以位址（指標）操作一切。這也是為什麼 C 語言適合撰寫作業系統和嵌入式系統：它與硬體之間幾乎沒有中間層。
### Opaque pointer 與 incomplete type
- [ ] 考慮以下程式碼：`struct opaque; struct opaque *create(void); void destroy(struct opaque *);`
`struct opaque;` 是一個 forward declaration，宣告了 `struct opaque` 這個型別存在，但不定義其成員。此時 `struct opaque` 是一個 incomplete type。搭配 `create()` 和 `destroy()` 構成 opaque pointer pattern——client code 只透過指標操作 object，不需知道 struct 的內部結構。
撰寫 [`opaque.c`](https://github.com/laneser/warmup/blob/main/opaque.c) 測試 incomplete type 的限制（`make opaque_report`）：
```
Incomplete type (opaque pointer) test -- gcc 13
Compile-time: what works with incomplete type (C99 6.2.5)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast struct opaque *p: compiled
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast struct opaque x: compile error
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast struct opaque a[3]: compile error
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast sizeof(struct opaque): compile error
Runtime: sizeof pointer to incomplete type
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast sizeof(struct opaque *) = 8
```
結果與最佳化等級無關——這是語言層級的型別規則，不受最佳化影響。
#### 1. 為何可以只 forward declaration？
C99 §6.2.5¶1 定義 incomplete type：
> Types are partitioned into *object types*, *function types*, and *incomplete types* (types that describe objects but lack information needed to determine their sizes).
§6.2.5¶20 允許指標指向 incomplete type：
> A *pointer type* may be derived from a function type, an object type, or an **incomplete type**.
`struct opaque;` 是 incomplete type，但 `struct opaque *` 是一個完整的指標型別——指標本身的大小是固定的（x86-64 上 8 bytes），不依賴 struct 的內容。因此只需 forward declaration 即可宣告並使用指標。
但不能宣告 `struct opaque x;`（compiler 不知道要分配多少記憶體），也不能宣告 `struct opaque a[3];`（§6.2.5 footnote 36：array of incomplete type cannot be constructed），也不能 `sizeof(struct opaque)`（大小未知）。
#### 2. 這如何達成 binary compatibility？
Client code 只看到 `struct opaque *`，編譯後的 binary 只包含指標操作（固定 8 bytes 的存取）。struct 的內部成員完全被隱藏在實作 `create()` 和 `destroy()` 的 library 中。
當 struct 內部需要修改（新增成員、調整順序、改變大小）時，只需重新編譯 library，client code 不用重新編譯——因為 client 的 binary 從未依賴 struct 的大小或佈局，只依賴指標大小。這就是 binary compatibility。
Linux 核心中可以找到這個模式的實例。例如 [`include/linux/cdev.h:10-12`](https://github.com/torvalds/linux/blob/v6.19/include/linux/cdev.h#L10-L12) 以 forward declaration 宣告 `struct file_operations`、`struct inode`、`struct module`，使 `cdev` 子系統的 header 不需引入整個 `fs.h`；[`include/linux/net.h:29-33`](https://github.com/torvalds/linux/blob/v6.19/include/linux/net.h#L29-L33) 同樣 forward declare `struct inode`、`struct file`、`struct net` 等，讓 socket 子系統僅透過指標操作這些型別。
#### 3. 為何 incomplete type 只能搭配 pointer？
因為 incomplete type 缺少「確定大小」的資訊（§6.2.5¶1）。要分配記憶體（宣告變數、建立陣列）或計算大小（`sizeof`），compiler 必須知道型別的完整定義。唯一不需要知道大小的操作就是「存一個位址」——而指標的大小由架構決定，與所指向的型別無關。
### Object lifetime 結束後的 dangling pointer
- [ ] 舉出一個程式碼案例，使得以下得以滿足，並用 C99 對 lifetime 的定義精確解釋：object lifetime 結束、storage 尚未被重用、pointer 仍保留原數值、但 dereference 屬於 UB
最直接的做法是利用 automatic storage duration：函式參數在函式回傳後 lifetime 即結束，但 stack 上的記憶體不一定立刻被覆寫。
```c
int *foo(int x)
{
return &x;
}
```
`x` 是函式參數，沒有 linkage、沒有 `static`，具有 automatic storage duration（§6.2.4¶4）。`foo` 回傳後，`x` 所在的 block 結束，lifetime 隨之結束（§6.2.4¶5）。但 caller 拿到的指標值仍指向 `x` 原本佔用的 stack 位址——該記憶體尚未被其他函式呼叫覆寫（storage 尚未被重用），指標的數值沒有被清除（pointer 仍保留原數值），然而 dereference 該指標就是在 lifetime 外存取 object，屬於 UB（§6.2.4¶2）。
撰寫 [`lifetime_ub.c`](https://github.com/laneser/warmup/blob/main/lifetime_ub.c) 驗證（`make lifetime_ub_report`）：
```
Object lifetime UB test -- gcc 13
v1: foo() direct return (GCC replaces with NULL)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast foo(42) returned: p1 = (nil)
v2: bar() smuggled via output parameter
-O0, -Og *p2 = 42 (UB: lifetime ended)
-O1, -Os, -O2, -O3, -Ofast *p2 = garbage value
v3: after second bar(99) — storage reuse
-O0, -Og *p2 = 99 (storage reused)
-O1, -Os, -O2, -O3, -Ofast *p2 = garbage value
```
程式設計了兩個版本來對比：
- **v1（`foo` 直接 return `&x`）**：GCC 在所有最佳化層級都將 `return &x` 替換為 `return NULL`——compiler 偵測到這是 UB，直接利用它做最佳化。檢視組合語言可確認：
```
foo:
movl $0, %eax ; return NULL, not &x
ret
```
- **v2（`bar` 透過 output parameter 偷渡 `&x`）**：位址透過 `*out = &x` 寫入 caller 的變數，繞過 `-Wreturn-local-addr` 的偵測路徑（GCC 13 仍以 `-Wdangling-pointer` 警告）。
`-O0` 下 `*p2 = 42`——stack 記憶體尚未被覆寫，「看起來正確」，這正是 dangling pointer bug 難以發現的原因。但 `-Og` 以上 `*p2` 不是 42，因為最佳化器將 `bar` inline 後，`x` 根本沒有被寫入 stack 對應位置。
- **v3（第二次呼叫 `bar(99)`）**：`-O0` 下 `*p2` 從 42 變成 99——同一塊 stack storage 被重用，體現了 storage reuse。`-O1` 以上則因最佳化而看到不同的行為，進一步證實這是 UB，結果不可預期。
#### 為何 GCC 可以把 `return &x` 替換為 NULL？
因為回傳 local variable 的位址必然導致 caller 在 lifetime 外存取 object，這是 UB。C99 §6.2.4¶2：
> If an object is referred to outside of its lifetime, the behavior is undefined.
規格對 UB 的定義（§3.4.3）是「behavior ... for which this International Standard imposes **no requirements**」。Compiler 在遇到 UB 時不需要產生任何特定行為，可以自由最佳化。GCC 選擇回傳 NULL——這比回傳一個 dangling pointer 更容易在執行時被偵測（dereference NULL 會 segfault，而 dereference dangling pointer 可能「碰巧正確」而隱藏 bug）。
#### 四個條件如何對應 C99 規格
| 條件 | 規格依據 | 驗證觀察 |
|------|----------|----------|
| object lifetime 結束 | §6.2.4¶5：automatic storage duration 的 lifetime 在 block 結束時結束 | `foo`/`bar` 回傳後，`x` 的 block 結束 |
| storage 尚未被重用 | 規格不保證 stack 何時被覆寫；實務上下一次函式呼叫才會重用 | `-O0` 下 `*p2 = 42`，`bar(99)` 後變為 99 |
| pointer 仍保留原數值 | §6.2.4¶2 指出指標值變為 indeterminate，但實務上位元模式不會自動清除 | `p2` 的位址值在 `bar` 回傳後未改變 |
| dereference 屬於 UB | §6.2.4¶2：在 lifetime 外存取 object 是 UB | `-Og` 以上 `*p2 ≠ 42`；GCC 直接將 `foo` 的 return 替換為 NULL |
### Strict aliasing 與 type punning
- [ ] 以下程式在 `-O2` 下可能輸出什麼？
```c
float f = 1.0f;
int *p = (int *)&f;
*p = 0;
printf("%f\n", f);
```
撰寫 [`strict_alias.c`](https://github.com/laneser/warmup/blob/main/strict_alias.c) 驗證（`make strict_alias_report`）。為了讓 strict aliasing 的效果在實驗中可觀察，程式透過函式邊界隔離 `float*` 和 `int*` 的寫入與讀取：
```c
__attribute__((noinline))
static float alias_violation(float *fp, int *ip)
{
*fp = 1.0f;
*ip = 0; /* UB: int* writing to a float object */
return *fp; /* compiler may return 1.0f from register */
}
```
呼叫時以 `alias_violation(&x, (int *)&x)` 傳入同一位址。
```
Strict aliasing test -- gcc 13
v1: int* alias to float (strict aliasing violation)
-O0, -Og, -O1 alias violation: 0.000000
-Os, -O2, -O3, -Ofast alias violation: 1.000000
v2: memcpy version (well-defined)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast memcpy: 0.000000
v3: unsigned char* version (always legal)
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast uchar*: 0.000000
v4: IEEE 754 bit pattern of 1.0f
-O0, -Og, -O1, -Os, -O2, -O3, -Ofast 1.0f bits = 0x3f800000 (1065353216)
```
`-O2` 下輸出 `1.000000`，不是 `0.000000`。Compiler 依據 strict aliasing rule 假設 `float*` 和 `int*` 不可能指向同一個 object，因此 `*ip = 0` 不會影響 `*fp` 的值，直接從暫存器回傳先前寫入的 `1.0f`。
而 v2（`memcpy`）和 v3（`unsigned char*`）在所有最佳化層級都正確輸出 `0.000000`。
#### 1. 是否違反 strict aliasing？
是。C99 §6.5¶7（strict aliasing rule）列出了允許存取 object 的 lvalue 型別清單：
> An object shall have its stored value accessed only by an lvalue expression that has one of the following types:
> - a type compatible with the effective type of the object,
> - ...
> - a character type.
`f` 的 effective type 是 `float`，透過 `int*` lvalue 寫入——`int` 不在允許清單中（不是 compatible type、不是對應的 signed/unsigned 版本、不是 character type），因此是 UB。
Compiler 利用此規則進行 type-based alias analysis（TBAA）：既然 `float*` 和 `int*` 依規格不能 alias，`*ip = 0` 就不可能改變 `*fp` 所指的 object，因此可以省略重新載入 `*fp`。
#### 2. 若使用 `memcpy` 是否等價？
語意上等價——都是將 `0` 的 bit pattern 寫入 `f` 佔用的記憶體。但法律地位不同：
- `*p = 0`：透過 `int` lvalue 存取 `float` object → **UB**
- `memcpy(&f, &zero, sizeof f)`：`memcpy` 的語意定義為逐 byte 複製（§7.21.2.1），等同透過 `unsigned char*` 操作 → **well-defined**
`memcpy` 之後 compiler 知道 `f` 的 bit pattern 可能已被改變，必須重新載入。這就是為何 v2 在所有最佳化層級都正確輸出 `0.000000`。
在效能方面，以 `gcc -std=c99 -O2 -S strict_alias.c` 產生組合語言，檢視 `memcpy_version` 函式：
```asm
memcpy_version:
pxor %xmm0, %xmm0 ; xmm0 = 0.0f
ret
```
沒有 `call memcpy`，也沒有任何記憶體存取。GCC 將 4-byte `memcpy` 展開為暫存器操作，再常數折疊——既然 `1.0f` 被全零覆寫，結果必為 `0.0f`，直接以 `pxor` 清零 XMM 暫存器回傳。`uchar_version` 同樣被折疊為相同的兩行指令。使用 `memcpy` 做 type punning 既合法又無額外開銷。
#### 3. 為何 C 規格允許 `unsigned char *` 例外？
C 語言需要一種合法方式操作任意 object 的底層位元組表示——序列化、網路封包解析、`memcpy`/`memset` 的實作都依賴這個能力。§6.5¶7 最後一條允許 **character type**（`char`、`unsigned char`、`signed char`）存取任何 object。
**為何是 character type？** 這與 C99 的 object representation model 有關。§6.2.6.1¶4：
> Values stored in non-bit-field objects of any other object type consist of n × CHAR_BIT bits, where n is the size of an object of that type, in bytes.
C 的型別系統中，**任何 object 的值都是由 `unsigned char` 的序列組成的**。這不僅是實作細節，而是規格明確定義的語意模型。`unsigned char` 是 object representation 的基本單位，正如原子是物質的基本單位一樣。
`unsigned char` 被選為這個角色的原因：
- §6.2.6.1¶3 保證 `unsigned char` 沒有 padding bits——每個 bit 都參與值的表示
- §6.2.6.2¶1 保證 `unsigned char` 沒有 trap representation——任何 bit pattern 都是合法值
- 值域恰好覆蓋一個 byte `[0, UCHAR_MAX]`（§5.2.4.2.1 保證 `UCHAR_MAX >= 255`）
這三個性質意味著：透過 `unsigned char*` 走訪 object，每個 byte 都有明確的值，不會觸發 UB，且不遺漏任何 bit。
**深層含義：C 的型別系統有一個設計好的逃逸口。** 高層的 strict aliasing rule 讓 compiler 可以做激進的最佳化（假設不同型別的指標不會 alias），但底層有一個明確的逃逸機制——當你需要操作原始位元組時，透過 `unsigned char*` 下降到 byte 層級，compiler 不得做任何 aliasing 假設。
這使得以下核心設施可以合法實作：
- `memcpy`/`memset`/`memcmp`——標準函式庫的基礎
- 序列化/反序列化——將 struct 轉為 byte stream 傳輸
- 硬體暫存器存取——嵌入式系統中讀寫 memory-mapped I/O
- 密碼學——逐 byte 處理資料，避免 timing side-channel
若沒有 character type 例外，這些操作全部會是 UB，C 語言將無法作為系統語言使用。
#### 4. 在不同架構下是否行為不同？
當 `sizeof(int) == sizeof(float)` 時（ILP32、LP64 平台皆為 4 bytes），`*p = 0` 將 float 的全部 4 bytes 設為零，結果是 IEEE 754 的 `+0.0`，不受架構影響。
但 C 語言的 `int` 大小是跟著架構變動的（§5.2.4.2.1 只保證 `int` 至少 16 bits），而 `float` 幾乎都是 IEEE 754 single-precision 的 4 bytes。在 `sizeof(int) != sizeof(float)` 的平台上（例如 16-bit 架構 `sizeof(int) == 2`），`*p = 0` 只覆寫 float 的前 2 bytes，剩餘 2 bytes 保留原值——結果完全不同且取決於 endianness。
更根本地，strict aliasing violation 本身就是 UB——compiler 在任何架構上都可以產生任意結果，架構差異只是 UB「碰巧表現出來的樣子」不同而已。合法的做法永遠是用 `memcpy` 或 `unsigned char*`。
### Array parameter decay 與 ABI 差異
- [ ] 為何以下二者 ABI 不同？
```c
void f(int a[10]);
void f(int *a);
```
比較：
```c
void g(int (*a)[10]);
```
C99 §6.7.5.3¶7：
> A declaration of a parameter as "array of *type*" shall be adjusted to "qualified pointer to *type*".
§6.7.5.3¶7 的 adjustment 只作用於「array of *type*」形式的參數：`f(int a[10])` 符合，adjust 為 `int *`；`g(int (*a)[10])` 宣告的是指標而非陣列，不適用此規則，型別維持 `int (*)[10]`。
Adjustment 後 `f` 的參數是 `int *`，`g` 的參數是 `int (*)[10]`。根據 C99 §6.7.5.1¶2：
> For two pointer types to be compatible, both shall be identically qualified and both shall be pointers to compatible types.
`int *` 的 referenced type 是 `int`，`int (*)[10]` 的 referenced type 是 `int[10]`——兩者不是 compatible types，因此 `int *` 與 `int (*)[10]` 不 compatible，`f` 和 `g` 的函式型別不同，ABI 也不同。具體差異反映在：
1. **Pointer arithmetic 步幅** — `f` 中 `a+1` 前進 `sizeof(int)` = 4 bytes，`g` 中 `a+1` 前進 `sizeof(int[10])` = 40 bytes
2. **Caller 傳入方式** — `f(arr)` 傳入 decay 後的 `&arr[0]`，`g(&arr)` 傳入整個陣列的位址
3. **跨編譯單元誤用** — 若 header 寫 `f(int *a)` 但定義寫 `f(int (*a)[10])`，linker 不做型別檢查，pointer arithmetic 步幅錯誤，屬 C99 §6.5.2.2¶6 的未定義行為
撰寫 [`array_param.c`](https://github.com/laneser/warmup/blob/main/array_param.c) 驗證（`make array_param_report`）：
```
Array parameter decay test -- gcc 13
arr = 0x7ffd913244e0
sizeof(arr)= 40
[f1] sizeof(a) = 8 [f2] sizeof(a) = 8 [g] sizeof(a) = 8
[f1] sizeof(*a) = 4 [f2] sizeof(*a) = 4 [g] sizeof(*a) = 40
[f1] a+1 delta = 4 [f2] a+1 delta = 4 [g] a+1 delta = 40
```
`f1` 和 `f2` 的行為完全一致——GCC 甚至對 `f1` 產生 `-Wsizeof-array-argument` 警告，提醒 `sizeof(a)` 回傳的是指標大小而非陣列大小，證實 `int a[10]` 已被 adjust 為 `int *a`。
`g` 的 `sizeof(*a)` 是 40（`int[10]`），`a+1` 前進 40 bytes——pointer arithmetic 單位是整個陣列，而非單個 `int`。
#### 1. 為何 `sizeof` 結果不同？
`sizeof(a)` 在 `f` 和 `g` 裡都是 8（都是指標變數）。真正的差異在 `sizeof(*a)`：
- `f` 的 `a` 型別是 `int*`，`*a` 是 `int` → `sizeof(*a)` = 4
- `g` 的 `a` 型別是 `int (*)[10]`，`*a` 是 `int[10]` → `sizeof(*a)` = 40
這直接決定了 pointer arithmetic 的步幅：`a+1` 在 `f` 中前進 4 bytes，在 `g` 中前進 40 bytes。
#### 2. 為何 `&a` 與 `a` 型別差異重大？
在 `f` 中：
- `a` 的型別是 `int*`（指向 int）
- `&a` 的型別是 `int**`（指向指標的指標）
在 `g` 中：
- `a` 的型別是 `int (*)[10]`（指向 10 個 int 的陣列）
- `&a` 的型別是 `int (**)[10]`（指向「指向陣列的指標」的指標）
`&a` 與 `a` 多了一層 indirection，這在任何指標變數上都成立。但更值得注意的是 `a` 與 `*a` 在 `g` 中的差異：
- `a` 是 `int (*)[10]`，`a+1` 前進 40 bytes（整個陣列）
- `*a` 是 `int[10]`，在 expression 中 decay 為 `int*`，`(*a)+1` 前進 4 bytes（單個 int）
同一個指標 `a`，解引用前後的 pointer arithmetic 步幅差了 10 倍。這是 `int (*)[10]` 與 `int*` 在實際使用上最關鍵的差異——若混淆這兩種型別，pointer arithmetic 會產生錯誤的偏移量。
#### 3. 若跨編譯單元宣告不一致會發生什麼？
假設 `a.c` 定義 `void f(int (*a)[10]) { ... a+1 ... }`，而 `b.c` 宣告 `void f(int *a);` 並以 `f(arr)` 呼叫。
Linker 不做型別檢查——它只看 symbol name。`b.c` 傳入 `int*`，`a.c` 當作 `int (*)[10]` 使用。兩者都是 8-byte 指標，呼叫本身不會 crash，但函式內部的 pointer arithmetic 會以 40 bytes 為單位步進，而 caller 預期的是 4 bytes——存取到錯誤的記憶體位置。
C99 §6.5.2.2¶6 規定，若函式呼叫時的型別與函式定義的型別不相容（not compatible），行為是**未定義的**。這是一個不會被 compiler 警告的 UB——只有跨編譯單元才會發生，因為同一個檔案內 compiler 會檢查型別一致性。
---
## 探討〈[linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉
### Linked list 翻譯為「鏈結串列」的詞源考據
- [ ] 從〈[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)〉的角度，探討何以 linked list 翻譯為「鏈結串列」，而非「鏈表」或「連結串列」，而「串列」的詞源又在哪？翻閱詞典和二十世紀出版物來解說
#### 辭典定義
查教育部重編國語辭典確認各字的本義：
- [**鏈**](https://dict.revised.moe.edu.tw/dictView.jsp?ID=3626)（ㄌㄧㄢˋ）：「金屬環相連而成的繩狀物」，如鐵鏈、鎖鏈。強調**環環相扣**的結構。
- [**結**](https://dict.revised.moe.edu.tw/dictView.jsp?ID=5555)（ㄐㄧㄝˊ）：「用繩或線相鉤連」，如結網、結繩。強調**鉤連**動作。
- [**串**](https://dict.revised.moe.edu.tw/dictView.jsp?ID=8652)（ㄔㄨㄢˋ）：「把東西連貫在一起」，如串珠子。強調**依序穿連**成一條。
- [**列**](https://dict.revised.moe.edu.tw/dictView.jsp?ID=3512)（ㄌㄧㄝˋ）：「行次」、「依次排比」，如排列、列隊。強調**有序排列**。
- [**表**](https://dict.revised.moe.edu.tw/dictView.jsp?ID=457)（ㄅㄧㄠˇ）：「分格或分項以列記事物的文件」，如報表、統計表。強調**分格/分項的表格結構**。
- [**連**](https://dict.revised.moe.edu.tw/dictView.jsp?ID=3596)（ㄌㄧㄢˊ）：「接合」，泛指一般性的接合，不特指鏈狀結構。
#### 為何不是「鏈表」？
〈[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)〉明確指出：linked list「不可稱『鏈表』，該資料結構不具備任何『表』的寓意」，並引用教育部辭典「[表](https://dict.revised.moe.edu.tw/dictView.jsp?ID=457)」的定義——「分格或分項以列記事物的文件」。
Linked list 的節點是透過指標逐一串接，沒有行列分格，不是表格結構。用「表」來翻譯 list 是把 list 當成 table。
#### 為何不是「連結串列」？
教育部辭典中「[連結](https://dict.revised.moe.edu.tw/dictView.jsp?ID=64001)」的定義是「互相結合」和「透過網路的傳遞，使分處二地之電腦設備能夠相互的溝通或傳遞訊息」。前者過於泛化，後者指的是網路連線（network connection）。
「鏈結」雖然不是辭典收錄的複合詞，但從構詞法來看：「[鏈](https://dict.revised.moe.edu.tw/dictView.jsp?ID=3626)」（環環相扣的鏈狀物）+「[結](https://dict.revised.moe.edu.tw/dictView.jsp?ID=5555)」（鉤連）精確描述了 linked list 中節點透過指標逐一鉤連的結構——每個 node 的 `next` 指標就是一個「鏈環」，將前後節點「結」在一起。相較之下，「連結」的「[連](https://dict.revised.moe.edu.tw/dictView.jsp?ID=3596)」只表達泛泛的「接合」，缺乏鏈狀結構的意象。
#### 「串列」的詞源
「串列」不在教育部辭典中，是資訊科技領域的術語。拆開來看：
- 「[串](https://dict.revised.moe.edu.tw/dictView.jsp?ID=8652)」= 把東西連貫在一起（依序穿連）
- 「[列](https://dict.revised.moe.edu.tw/dictView.jsp?ID=3512)」= 依次排比（有序排列）
「串列」合起來描述「依序串連排列的結構」，對應英文 list 的「有序序列」語意。國家教育研究院「[樂詞網](https://terms.naer.edu.tw)」的電子計算機名詞中，list 在作為資料結構語境時譯為「串列」。國家教育研究院的前身[國立編譯館](https://zh.wikipedia.org/zh-tw/%E5%9C%8B%E7%AB%8B%E7%B7%A8%E8%AD%AF%E9%A4%A8)（1932 年成立，2011 年併入國家教育研究院）負責審定學術名詞。國立編譯館於 1990 年代投入學術名詞工具書編印，2003 年出版《[資訊與通信術語辭典](https://gpi.culture.tw/books/1009201728)》（楊維楨等編著，ISBN 9570142448，1906 頁），但該辭典屬二十一世紀出版物。「電子計算機名詞」分類的最早審定版本年份，在線上公開資料中查不到。
維基百科的[鏈結串列](https://zh.wikipedia.org/zh-tw/%E9%93%BE%E8%A1%A8)條目以 NoteTA 地區詞轉換確認 `zh-tw:串列` 對應 `zh-cn:列表`（英文 list），`zh-tw:鏈結串列` 對應 `zh-cn:链表`（英文 linked list），佐證「串列」是台灣資訊科技領域的標準用語。
因此「鏈結串列」= 鏈結（以鏈狀鉤連的方式）+ 串列（依序串連的序列），完整對應 linked（以鏈接方式）+ list（序列）。
關於「翻閱二十世紀出版物」的部分：經搜尋維基百科、樂詞網、政府出版品資訊網（GPI）及國家圖書館等線上資料庫，未能找到公開可查閱的二十世紀書籍明確記載「串列」一詞作為 list 的翻譯。國立編譯館的學術名詞審定工作可追溯至二十世紀，但其紙本《電子計算機名詞》的版本歷史並未數位化公開。
### `struct ListNode **indir` 的指標語意
- [ ] 教材中使用 `struct ListNode **indir = &head;`，描述以下:
1. `indir` 的型別語意
2. `*indir` 的語意
3. `&(*indir)->next` 的語意
並說明為何這不是「雙指標」，而是「指標的指標」
1. **`indir`** 的型別是 `struct ListNode **`，即 `head` 的指標的指標
2. **`*indir`** 解參考一層，就是 `head`
3. **`&(*indir)->next`** — 因為 `*indir == head`，所以等同 `&head->next`，即 `head` 內部 `next` 欄位的位址。`next` 的型別是 `struct ListNode *`，取其位址後型別為 `struct ListNode **`，與 `indir` 一致，因此可以 `indir = &(*indir)->next` 推進走訪。C99 §6.5.2 postfix `->` 優先於 §6.5.3 unary `&`，所以 `&(*indir)->next` 等同 `&((*indir)->next)`。
不稱「雙指標」是因為教育部辭典「[雙](https://dict.revised.moe.edu.tw/dictView.jsp?ID=9189)」作量詞指「成對」，暗示對等並存（如 two-pointer technique 的 `left`/`right`）。而 `ListNode **` 是一個指標指向另一個指標，是階層（indirection）關係，應稱「指標的指標」。
### `free` 與 lifetime 分析
- [ ] 考慮 `prev->next = (*indir)->next; free(*indir);`，分析：
1. `*indir` 在哪一行失去 lifetime？
2. 若先 `free` 再改鏈結會發生什麼？
3. 為何 AddressSanitizer 能偵測？
4. 若在 `-O3` 下編譯器是否可能出現指令的 reorder？
1. **`*indir` 在 `free(*indir)` 該行失去 lifetime。** C99 §7.20.3.2 規定 `free` 使所指向的空間被 deallocate，該 object 的 lifetime 於此結束（§6.2.4¶2：allocated storage 的 lifetime 從 allocation 到 deallocation）。
2. **若先 `free(*indir)` 再執行 `prev->next = (*indir)->next`：** `free` 之後 `*indir` 所指的記憶體已被釋放，其 lifetime 已結束。此時 `(*indir)->next` 嘗試存取已釋放的記憶體中的 `next` 欄位——屬於 C99 §6.2.4 的未定義行為（use-after-free）。雖然直覺上「只是讀一個值」，但 free 之後該記憶體可能已被重新配置或其內容被覆寫，存取結果不可預期。
3. **AddressSanitizer（ASan）的偵測機制：** 根據 [[5]](https://www.usenix.org/system/files/conference/atc12/atc12-final39.pdf) §3 Algorithm 的描述，ASan 是 **compile-time 插樁 + runtime 偵測**，不是純靜態分析。編譯時（LLVM/GCC 的 `-fsanitize=address`），compiler 在每次記憶體存取前插入 shadow memory 檢查碼；runtime library 替換 `malloc`/`free`，`free` 時將對應的 shadow memory 標記為 poisoned。後續若有存取命中已 poisoned 的區域，插樁的檢查碼即報告 `heap-use-after-free`。
4. **`-O3` 下是否可能 reorder：** 不會。well-defined 的程式碼中，`prev->next = (*indir)->next` 讀取 `*indir` 指向的記憶體，`free(*indir)` 釋放同一塊記憶體——兩者之間存在資料相依，compiler 必須先完成讀取才能釋放。C99 §5.1.2.3 的 as-if rule 要求 compiler 保持 observable behavior 不變，因此不能將 `free` 提前到讀取之前。只有在程式碼本身已經是 UB（先 free 再讀）的情況下，compiler 的行為才不受約束——但那不是 reorder 的問題，是 UB 本身讓一切都不可預測。
### Hardware prefetcher 與 linked list traversal
- [ ] 為何針對鏈結串列的節點走訪 (linked list traversal) 難以被 hardware prefetcher 預測？若使用 `__builtin_prefetch(node->next);` 是否一定改善效能？請記憶體存取的行為模式來解釋，並從 git log 探討 Linux 核心的 List API 一度採用 prefetcher 又棄置的考量。
#### 1. Hardware prefetcher 為何對 linked list 無效
根據 *Intel® 64 and IA-32 Architectures Optimization Reference Manual* [[6]](https://www.cs.utexas.edu/~hunt/class/2016-spring/cs350c/documents/Intel-x86-Docs/64-ia-32-architectures-optimization-manual.pdf)（Document 248966-031, §2.4.4.2），Intel Core 微架構的 L1 data cache 有兩種 hardware prefetcher：
- **DCU prefetcher**（streaming prefetcher）— 偵測到對最近載入資料的遞增存取時，假設為 streaming 演算法，自動預取下一條 cache line
- **IP-based strided prefetcher** — 追蹤個別 load 指令，若偵測到該指令有**固定的 stride**，就預取 `目前位址 + stride`（可偵測正向或反向，stride 上限 2KB）
這兩種機制對 array 走訪非常有效——元素在記憶體中連續排列，存取模式是可預測的等差數列（固定 stride）。
Linked list 的每個節點透過 `malloc` 分配於 heap 上的任意位置，`next` 指標指向的位址之間沒有固定的 stride。Hardware prefetcher 觀察到的存取序列類似亂數，無法推斷下一個位址，因此**不會預取**。每次 `node = node->next` 都是一次 cache miss，必須等待完整的 DRAM 存取延遲。
#### 2. `__builtin_prefetch(node->next)` 不一定改善效能
`__builtin_prefetch` 是 GCC 的 built-in，編譯為 x86 的 `prefetcht0` 指令（locality=3 時），提示 CPU 將指定位址的 cache line 載入 L1 cache。以下是 GCC `-O2` 產生的組合語言對比：
```c
// 有 prefetch // 沒有 prefetch
for (n = head; n; n = n->next) { for (n = head; n; n = n->next)
__builtin_prefetch(n->next, 0, 3); s += n->val;
s += n->val;
}
```
```
; sum_prefetch 迴圈核心 ; sum_plain 迴圈核心
movq %rdi, %rdx addl (%rdi), %eax
movq 8(%rdi), %rdi movq 8(%rdi), %rdi
addl (%rdx), %eax testq %rdi, %rdi
prefetcht0 (%rdi) jne .L9
testq %rdi, %rdi
jne .L3
```
Prefetch 版本多了 `prefetcht0` 指令，但**效果取決於時機**：要發出 `prefetcht0 (n->next)` 就必須先讀 `n->next` 的值（`movq 8(%rdi), %rdi`），而讀 `n->next` 本身可能就是一次 cache miss。等 cache miss 解決、拿到 `n->next` 的值並發出 prefetch 後，CPU 馬上就要用 `n->next`——prefetch 來不及在存取前完成載入。
此外還有額外成本：
- **指令開銷** — 每次迭代多執行 `prefetcht0`，佔用 instruction cache 和 pipeline 資源
- **`prefetch(NULL)` 的 TLB stall** — 鏈結串列的最後一個節點 `next == NULL`，`prefetcht0 (NULL)` 在部分 Intel 微架構上會觸發 TLB miss，造成 pipeline stall
- **無用的 D$（data cache）活動** — 在 hash table 走訪中，常在鏈的前幾個節點就找到目標，後續節點的 prefetch 浪費 cache bandwidth，甚至可能驅逐有用的 cache line
> D$ 是核心開發者對 data cache 的暱稱——英文 cache 發音近似 cash，因此以 `$` 速記：D$ = Data Cache、I$ = Instruction Cache。Linus 的 commit message 就使用此寫法。
#### 3. Linux 核心 List API 一度採用 prefetch 又棄置的歷程
Linux 核心的 list iteration 巨集曾在每次迭代中隱式呼叫 `prefetch()`。以 `list_for_each` 為例，移除前的版本類似：
```c
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); pos = pos->next)
```
2011 年 5 月 19 日，Linus Torvalds 在兩筆連續的 commit 中移除了所有 list/hlist 巨集中的 `prefetch()`：
**Commit [`e66eed65`](https://github.com/torvalds/linux/commit/e66eed651fd18a961f11cda62f3b5286c8cc4f9f)** — 移除 `list_for_each`、`list_for_each_entry` 等 8 個巨集中的 `prefetch()`。Commit message 寫道：
> normally the downsides are bigger than the upsides
David Miller（networking maintainer）指出網路子系統中大量的 list 經常為空或只有一個 entry，prefetch 只是增加無用的指令。
**Commit [`75d65a42`](https://github.com/torvalds/linux/commit/75d65a425c0163d3ec476ddc12b51087217a070c)** — 移除 `hlist_for_each`、`hlist_for_each_entry` 等巨集中的 `prefetch()`，並附上實測數據：
> On internationally acclaimed benchmarks ("make -j16" on an already fully built kernel source tree) the hlist prefetching slows down the build by up to 1%.
Linus 分析了兩個具體原因：
> - on at least some Intel cores, prefetch(NULL) ends up with some microarchitectural stall due to the TLB miss that it incurs.
> - the prefetch appears to cause more D$ activity, probably because it prefetches hash list entries that are never actually used (because the hash chain walk terminates before we actually reach those entries).
移除後，原本為了避開 prefetch 開銷而存在的 `__list_for_each`（不帶 prefetch 的版本）變得與 `list_for_each` 完全相同，於 2013 年被 Dave Jones 在 commit [`c0d15cc7`](https://github.com/torvalds/linux/commit/c0d15cc7ee8c0d1970197d9eb1727503bcdd2471) 中移除。
現在的 `list_for_each`（[`include/linux/list.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/list.h#L708) 第 708 行）不含任何 prefetch：
```c
#define list_for_each(pos, head) \
for (pos = (head)->next; !list_is_head(pos, (head)); pos = pos->next)
```
核心的 `prefetch()` 基礎設施（[`include/linux/prefetch.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/prefetch.h)）仍然存在，供確知存取模式有利的呼叫端自行使用——但通用的 list iteration 巨集不再隱式 prefetch。
### Linux 的 merge sort 設計
- [ ] 針對 Linux 的 merge sort 設計，回答
1. 為何 list_sort 是 stable？
2. 為何不使用 quicksort？
3. 為何 merge sort 適合 linked list？
Linux 核心的排序實作位於 [`lib/list_sort.c`](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c)，採用 merge sort 變體。以下逐一回答三個子題。
#### 1. 為何 `list_sort` 是 stable
Stable sort 的定義：若兩元素的比較結果相等（`cmp(a, b) == 0`），排序後它們的相對順序與排序前相同。
`list_sort` 的穩定性由 `merge()` 函式保證（[第 19–20 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L19)）：
```c
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
```
當 `cmp` 回傳 `0`（相等）時，取第一引數 `a` 的元素。若 `a` 的元素在原始序列中都先於 `b` 的元素，這就保證等值元素的相對順序不變。
`list_sort` 內部所有合併——無論來自哪個階段——都透過 `merge()` 或 `merge_final()` 執行，兩者採用相同的 `<= 0` 取左邏輯（[第 19–20 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L19)、[第 56–57 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L56)）。以下先建立引理，再對 `list_sort` 的三個階段逐一驗證。
**引理（Merge Lemma）：** 若 `merge(a, b)` 的兩個輸入各自已穩定，且 `a` 的所有元素在原始序列中都先於 `b` 的所有元素，則輸出也是穩定的。
> 證明：考慮任意等值對 $a_i, a_j$（$i < j$ 表示原始順序）：
> - **都在 $a$** → $a$ 已穩定，merge 不改變同一子串列內的相對順序 ✓
> - **都在 $b$** → 同理 ✓
> - **$a_i \in a, a_j \in b$** → `cmp` 回傳 `<= 0` 時取 $a$，$a_i$ 排在 $a_j$ 前 ✓
> - **$a_i \in b, a_j \in a$** → 不可能，因為 $a$ 的元素全部先於 $b$ 而 $i < j$
>
> 四種情況皆滿足。$\blacksquare$
**「第一引數較早」不變量。** 引理的前提要求第一引數包含原始序列中較早的元素。`list_sort` 的三個階段都滿足此條件：
1. **do-while 迴圈**（[第 218–241 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L218)）：元素逐一從輸入取出，prepend 到 pending 前端，因此 pending 中越靠前的子串列，其元素在原始序列中越**晚**。合併時（[第 227–229 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L227)），`a = *tail`（較晚），`b = a->prev`（較早），呼叫 `merge(b, a)` — 較早的 `b` 為第一引數 ✓
2. **for 迴圈**（[第 246–253 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L246)）：`list` 從 pending 前端開始（最晚），`pending` 往 `prev` 走（較早）。呼叫 `merge(pending, list)` — 較早的 `pending` 為第一引數 ✓
3. **merge_final**（[第 255 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L255)）：`pending` 是最後剩餘的最舊子串列，`list` 是較新元素的累積結果。呼叫 `merge_final(pending, list)` — 較早的 `pending` 為第一引數 ✓
**歸納證明：** 令 $P(k)$ 為命題：在第 $k$ 次合併操作完成後，所有已排序的子串列都維持穩定性。
**基底 $P(0)$：** 尚未執行任何合併。`list_sort` 在[第 194 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L194)處理零或一個元素的情況（直接 return）；其餘情況，每個元素被取出為長度 1 的子串列（[第 235–240 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L235)），單一元素不存在等值對，穩定性自明。$P(0)$ 成立。
**歸納步驟：** 假設 $P(k)$ 成立。第 $k+1$ 次合併的兩個輸入子串列各自已穩定（由 $P(k)$），且如上所述滿足「第一引數較早」不變量。由引理，合併結果穩定。$P(k+1)$ 成立。
由數學歸納法，$P(k)$ 對所有 $k \geq 0$ 成立。最終的 `merge_final()` 是最後一次合併操作，同樣滿足引理前提，故 `list_sort` 的輸出是穩定的。$\blacksquare$
#### 2. 為何不使用 quicksort
Quicksort 不適合 linked list 有三個原因：
**（a）pivot 選取需要隨機存取。** Quicksort 的效能高度仰賴 pivot 的選取品質。在 array 中，可用 O(1) 取得中間元素（median-of-three）作為 pivot；linked list 必須循序走訪才能到達中間節點，光是選 pivot 就要 O(n)。
**（b）Quicksort 不是 stable sort。** Partition 過程中，等值元素可能因交換而改變相對順序。核心的 `list_sort` 文件明確要求穩定性（[第 108 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L108)：「list_sort is a stable sort」），quicksort 無法滿足。
**（c）worst case O(n²)。** 核心程式碼不能接受不可預測的效能退化。Merge sort 保證 worst case O(n log n)。
#### 3. 為何 merge sort 適合 linked list
**不需隨機存取。** Merge sort 的兩個核心操作——分割與合併——都只需循序走訪。分割可透過逐一取出元素完成（`list_sort` 的做法），合併則是比較兩個串列的頭部元素並重新串接指標。這與 linked list 的循序存取特性天然吻合。
**不需額外 O(n) 空間。** Array 的 merge sort 需要 O(n) 暫存空間來存放合併結果；linked list 的合併只需改變 `next` 指標，就地（in-place）完成，空間複雜度 O(log n)（遞迴堆疊或 pending list 的開銷）。
**穩定且 worst case O(n log n)。** 如上所述，merge sort 天然支持穩定性，且不論輸入分佈如何都保證 O(n log n)，適合核心中效能需求可預測的場景。
### `list_sort` 的延遲合併與比較次數分析
- [ ] Linux 核心的 `list_sort` 建構方式不同於 fully-eager bottom-up mergesort，回答
* 推導 worst-case comparison 次數
* 說明為何延遲合併可降低比較次數
* 建立數學上界
#### 1. 從 `merge()` 推導單次合併的比較次數
設 `merge()` 的兩個輸入子串列長度分別為 $a$ 和 $b$。觀察其迴圈結構（[第 18–37 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L18)）：每次迭代做恰好 1 次 `cmp()` 比較，從兩個子串列之一取出 1 個元素；當某一邊耗盡（`next` 為 NULL）時，另一邊剩餘元素**不經比較**直接接上。因此比較次數等於迴圈執行次數，即透過比較取出的元素數。
- **Worst case：** 兩邊交錯取出，直到第 $a + b - 1$ 個元素取出時某邊歸零，最後 1 個元素直接接上。比較 $a + b - 1$ 次。
- **Best case：** 較短的子串列中所有元素都小於較長子串列的任何元素，較短邊先耗盡。比較 $\min(a, b)$ 次。
#### 2. 建立合併樹模型與 $n = 2^k$ 時的 worst case
排序 $n$ 個元素需要多次合併，可將整個過程視為一棵**合併樹**（二元樹）：$n$ 個元素為葉節點，每個內部節點代表一次 `merge()` 呼叫。
每次 `merge()` 將 2 個子串列合成 1 個，即每次呼叫減少 1 個子串列。起始有 $n$ 個子串列（每個元素各自一個），最終合成 1 個，因此不論合併順序如何，`merge()` 的呼叫次數固定為 $n - 1$ 次。延遲合併機制只改變合併的時機和順序（即合併樹的形狀），不改變呼叫次數。
每個元素從葉節點到根，每經過一層合併就在 worst case 貢獻一次比較（對應 $a + b$ 的部分），而每次 `merge()` 呼叫有一個 $-1$ 的折扣（最後一個元素直接接上不需比較）。因此：
$$C_{\text{worst}}(n) = \sum_{i} d_i - (n - 1)$$
其中 $d_i$ 是元素 $i$ 在合併樹中的深度，$n - 1$ 是 merge 呼叫的總次數。合併樹的形狀決定 $\sum d_i$ 的大小——**樹越深，$\sum d_i$ 越大，worst case 比較次數越多**。
**$n = 2^k$ 時**，合併樹完美平衡。以 $n = 8$（$k = 3$）為例，合併樹由下往上編號：
```
層 j=2: [1,2,3,4,5,6,7,8] ← 1 次 merge（合併兩個 size-4）
層 j=1: [1,2,3,4] [5,6,7,8] ← 2 次 merge（合併兩個 size-2）
層 j=0: [1,2] [3,4] [5,6] [7,8] ← 4 次 merge（合併兩個 size-1）
葉節點: 1 2 3 4 5 6 7 8
```
第 $j$ 層把大小 $2^j$ 的子串列兩兩合併成長度 $2^{j+1}$ 的子串列，共 $\frac{n}{2^{j+1}}$ 次 merge，每次 worst case $2^{j+1} - 1$ 次比較，第 $j$ 層總比較 $\frac{n}{2^{j+1}} \cdot (2^{j+1} - 1) = n - \frac{n}{2^{j+1}}$。
每個元素經過 $k$ 層（從葉到根），所以 $\sum d_i = kn$。對所有層求和：
$$C(2^k) = \sum_{j=0}^{k-1} \left(n - \frac{n}{2^{j+1}}\right) = kn - n\left(1 - \frac{1}{2^k}\right) = kn - n + 1$$
即 $C(2^k) = n \log_2 n - n + 1$。
#### 3. $n \neq 2^k$ 時：不平衡合併樹的 worst case
$n \neq 2^k$ 時，合併樹無法完美平衡，worst case 取決於樹的形狀。不做延遲時，do-while 迴圈結束後 pending 中殘留的子串列大小不等，清掃階段（[for 迴圈，第 246–253 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L246)）的合併可能嚴重不平衡。
以 $n = 2^k + r$（$0 < r \ll 2^k$）為例。不做延遲時，pending 中會有一個大小 $2^k$ 的子串列和若干小子串列（總大小 $r$），清掃時的最終合併是 $2^k : r$。此時合併樹中：
- $2^k$ 個元素深度 $k + 1$（$k$ 層平衡合併 + 1 層最終合併）
- $r$ 個元素深度 $\lceil \log_2 r \rceil + 1$（自身排序 + 最終合併）
$$C_{\text{no-delay}}(n) = 2^k(k+1) + r(\lceil \log_2 r \rceil + 1) - (n - 1)$$
以 commit [`b5c56e0cdd62`](https://github.com/torvalds/linux/commit/b5c56e0cdd62) 的 $n = 1028$（$2^{10} + 4$）為例：
$$C_{\text{no-delay}}(1028) = 1024 \times 11 + 4 \times 3 - 1027 = 11276 - 1027 = 10249$$
#### 4. 延遲合併規則如何保證 2:1
`list_sort` 的 do-while 迴圈（[第 218–241 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L218)）每次迭代從輸入取出一個元素加入 pending，並透過 `count` 的位元操作決定是否觸發合併：
```c
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
a->prev = b->prev;
*tail = a;
}
```
合併只在 `bits` 非零時發生，即 `count` 達到 $2^k$ 的**奇數倍**（$3 \cdot 2^k, 5 \cdot 2^k, \ldots$）。若 `count` 首次達到 $2^k$（如 `0b0011` → `0b0100`），`bits` 右移後為零，`likely(bits)` 為假，**跳過合併**——這就是延遲。要等到 $3 \cdot 2^k$（確認後面已有 $2^k$ 個元素）才真正合併。
換言之，延遲規則是（[第 133–135 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L133)註解）：
> 延遲合併兩個大小 $2^k$ 的子串列，直到後面已經累積了 $2^k$ 個元素。
這保證到達輸入尾端、開始清掃 pending lists 時，每次合併**最差是 2:1 的比例**。最差情況是某個大小 $2^k$ 的子串列後面恰有 $2^{k+1} - 1$ 個元素（不足以觸發下一層合併），此時比例為 $2^k : (2^{k+1} - 1) \approx 1:2$。
#### 5. 建立 `list_sort` 的數學上界
2:1 平衡保證使合併樹深度不超過 $\lceil \log_2 n \rceil$，每個元素最多經過 $\lceil \log_2 n \rceil$ 層合併。代入公式：
$$C_{\text{list-sort}}(n) \leq n \lceil \log_2 n \rceil - (n - 1) \leq n \lceil \log_2 n \rceil - n + 1$$
以 $n = 1028$ 比較延遲前後的差異：
$$C_{\text{list-sort}}(1028) \leq 1028 \times 11 - 1027 = 11308 - 1027 = 10281$$
與步驟三的無延遲 worst case $C_{\text{no-delay}}(1028) = 10249$ 相比，此例差距不大。但當 $r$ 更小時差距會更顯著——$r = 1$ 時，無延遲的 $2^k$ 個元素全部多經過一層深度 $k+1$ 的合併，而延遲版本可以避免這種退化。
**與 commit 公式的差異。** Commit [`b5c56e0cdd62`](https://github.com/torvalds/linux/commit/b5c56e0cdd62) 引用 Panny & Prodinger (1995) 和 Chen, Hwang & Chen (1999) 的分析，將比較次數表示為：
$$C(n) = n \log_2 n - K \cdot n + O(1)$$
$K$ 越大，比較越少。文獻分析得出 `list_sort` 的 $K \approx 1.207$。
前述推導的上界與此公式有兩處差異，使得該上界正確但不夠緊：
1. **$\lceil \log_2 n \rceil$ vs $\log_2 n$**：合併樹的層數必須是整數，所以前述推導用了上取整。但 $n$ 略超 $2^k$ 時，$\lceil \log_2 n \rceil = k + 1$ 遠大於 $\log_2 n \approx k$，使上界一口氣多了近 $n$ 次比較。實際上合併樹不需要每個元素都經過 $k+1$ 層——延遲規則讓大部分元素只經過 $k$ 層，只有少數元素到第 $k+1$ 層。
2. **每次 merge 都假設 worst case**：前述推導對每次 `merge()` 都用 $a + b - 1$（兩邊完全交錯），但整棵合併樹中不可能每次合併都同時達到 worst case。文獻的分析考慮了合併樹結構對各層比較次數的約束，得出更精確的 $K$ 值。
換算成 $K$ 值，前述上界在 $n = 2^k$ 時對應 $K = 1$（精確），但 $n$ 略超 $2^k$ 時 $K$ 接近 $0$（非常寬鬆）。以 $n = 1028$ 為例，前述上界 $C \leq 10281$ 甚至高於步驟三的無延遲 worst case $10249$——這不代表延遲沒有效果，而是上界不夠緊：它假設所有元素都經過 $\lceil \log_2 n \rceil$ 層，但延遲版的合併樹實際上比這更平衡。
步驟三的深度之和對比（無延遲 $11276$ vs 平衡 $10796$，差 $480$）已展示平衡化在結構上的好處，但前述上界無法精確量化改善幅度。Commit 引用的文獻以更精確的方法分析得出 `list_sort` 的 $K$ 穩定在 $1.207$ 附近，而無延遲版本的平均 $K \approx 1.0$，因此延遲合併平均省下約 $(1.207 - 1.0) \times n \approx 0.2n$ 次比較。
### 鏈結串列 O(1) vs 陣列 O(n)：量化分析
- [ ] 鏈結串列的新增節點的時間複雜度是 O(1)，而陣列 (array) 則是 O(n)，但在實際硬體上，陣列可能更快，解釋為何如此並充分量化分析
#### 成本模型
O(1) 和 O(n) 描述的是「操作次數隨資料量的成長速率」，但隱藏了每次操作的**實際硬體成本**。建立一個統一的成本模型，以三個參數量化插入成本：
- $n$：目前的元素數量（影響搬移量和走訪距離）
- $i$：插入位置（$0 \leq i \leq n$，決定搬移 / 走訪的方向與量）
- $s$：元素大小（bytes，決定每次搬移觸及的資料量）
**陣列插入：** 在位置 $i$ 插入一個元素，涉及兩項成本：(1) 確保空間足夠，(2) 將 $i$ 之後的 $n - i$ 個元素後移。
空間管理策略決定第一項成本：
- **預先配置固定容量**：一次 `malloc` 配置大陣列（如上限 $N_{\max}$），之後插入不再配置。配置成本為 $O(1)$（已攤提），但浪費 $(N_{\max} - n) \times$ 元素大小的記憶體。
- **精確配置**：每次插入都 `realloc` 擴展一個元素。`realloc` 可能需要 `malloc` 新空間 + `memcpy` 全部 $n$ 個元素 + `free` 舊空間，成本 $O(n)$，比搬移本身更昂貴。
- **倍增策略**（如 C++ `std::vector`）：容量不足時加倍。單次 `realloc` 成本 $O(n)$，但 $n$ 次插入的總配置成本為 $O(n)$，amortized 每次 $O(1)$。記憶體浪費最多 $n$ 個元素（最差情況下容量 $= 2n$）。
以下分析採用**倍增策略**，因為它在時間與空間之間取得合理平衡。在此策略下，配置成本 amortized 後可忽略，插入的主要成本來自搬移：
$$C_{\text{arr}}(n, i, s) = (n - i) \times C_{\text{shift}}(s)$$
其中 $C_{\text{shift}}(s)$ 是搬移一個大小 $s$ bytes 的元素的成本。`memmove` 搬移 $(n - i) \times s$ bytes 的連續記憶體，具備空間區域性（spatial locality）。**$s$ 直接進入乘法**：搬移 $n$ 個 128-byte 元素需移動 $128n$ bytes，是 4-byte 元素的 32 倍。以 L1 內的 `memmove` 為例，4 bytes 約 4 個週期，128 bytes 需搬移 2 條快取行（假設 64-byte cache line），成本約 $30$+ 個週期。
三種典型情境：
- **頭部插入**（$i = 0$）：$C_{\text{arr}} = n \times C_{\text{shift}}(s)$，搬移量最大
- **尾部插入**（$i = n$）：$C_{\text{arr}} = 0$，無需搬移
- **隨機位置**（$i$ 均勻分布）：期望值 $E[C_{\text{arr}}] = \frac{n}{2} \times C_{\text{shift}}(s)$
**鏈結串列插入：** 插入本身只需修改 2–3 個指標，但有兩項隱藏成本：
1. **找到插入位置**：O(1) 的前提是「已持有插入位置的指標」。對於頭部和尾部，環狀鏈結串列可透過 `head` 和 `head->prev` 在 $O(1)$ 存取。但對於任意位置 $i$，必須走訪才能找到插入點。雙向鏈結串列可選擇從頭或尾走訪，取較短的方向：
$$C_{\text{traverse}}(n, i) = \min(i,\; n - i) \times C_{\text{node-access}}$$
注意 $C_{\text{traverse}}$ **不依賴 $s$**——走訪只讀取每個節點的 `next`/`prev` 指標，不觸及 payload 資料。這是鏈結串列在大元素時的關鍵優勢：$s$ 從 4 增至 512 bytes，走訪成本不變。$C_{\text{node-access}}$ 在節點分散時約等於一次快取未命中的延遲（$30$–$200$ 個週期，取決於快取層級）。期望走訪距離從單向的 $n/2$ 降為雙向的 $n/4$。
2. **配置新節點**：每次插入都需 `malloc`，且新節點的記憶體位址不保證與既有節點相鄰。
完整的成本模型，一般形式：
$$C_{\text{LL}}(n, i, s) = C_{\text{traverse}}(n, i, s) + C_{\text{malloc}}(s) + C_{\text{ptr-ops}}$$
逐項檢視 $s$ 的影響後可簡化（$C_{\text{ptr-ops}} \approx 10$ 週期，可忽略）：
$$C_{\text{LL}}(n, i, s) \approx C_{\text{traverse}}(n, i) + C_{\text{malloc}}$$
- $C_{\text{traverse}}(n, i, s) \to C_{\text{traverse}}(n, i)$：走訪只讀取每個節點的 `next`/`prev` 指標，不觸及 payload，因此與 $s$ 無關（前段已說明）。
- $C_{\text{malloc}}(s) \to C_{\text{malloc}}$：glibc 在 fast bin 命中時（小物件、無競爭）約 $50$–$150$ 個時脈週期，取 $C_{\text{malloc}} \approx 100$。$s$ 影響配置的 size class，但在常見範圍（$\leq 512$ bytes）內差異不大，視為常數。
**$s$ 從 $C_{\text{LL}}$ 的所有子項中消去**——這是與 $C_{\text{arr}}(n, i, s)$（隨 $s$ 線性成長）最根本的差異，也預測了一個交叉點：$s$ 夠大時，陣列的搬移成本將超過鏈結串列的走訪 + 配置成本。
對於頭部和尾部（$C_{\text{traverse}} = 0$），$C_{\text{LL}} \approx C_{\text{malloc}} \approx 100$ 個週期，是真正的 $O(1)$。但對於任意位置 $i$，走訪成本隨 $i$ 線性成長，且每步都可能是快取未命中——這使得鏈結串列的「$O(1)$ 插入」在實務上**只對已知位置成立**。
**記憶體開銷比較：** 鏈結串列的每個節點除了資料本身，還需儲存指標（雙向鏈結串列為 2 個指標，64 位元系統下共 16 bytes），加上 `malloc` 的 metadata 開銷。陣列（倍增策略）的浪費則是最差一倍容量。兩者的比較取決於**元素大小 $s$**：
| 元素大小 $s$ | 陣列浪費（最差） | 鏈結串列額外開銷 | 哪個省？ |
|-------------|----------------|----------------|---------|
| 4 bytes (int) | $4n$ bytes | $\geq 16n$ bytes（指標） | 陣列 |
| 64 bytes | $64n$ bytes | $16n$ bytes | 差距小 |
| 256+ bytes | $256n$ bytes | $16n$ bytes | 鏈結串列 |
後續實驗以 $s = 4 / 32 / 128 / 512$ bytes 四種 struct size 實測，驗證 $s$ 的不對稱影響。
#### 損益平衡點
**頭部和尾部（已知位置）：** 走訪成本為零，令 $C_{\text{arr}}(n, i, s) = C_{\text{malloc}}$ 求損益平衡：
$$(n - i) \times C_{\text{shift}}(s) = C_{\text{malloc}}$$
以 $s = 4$ bytes、$C_{\text{shift}}(4) \approx 4$ 週期為例：$n - i = 100/4 = 25$。但 $s = 128$ bytes 時 $C_{\text{shift}}(128) \approx 30$ 週期，損益平衡降至 $n - i = 100/30 \approx 3$——幾乎任何規模都是鏈結串列更快。
**任意位置（需走訪）：** 令 $C_{\text{LL}}(n, i, s) = C_{\text{arr}}(n, i, s)$ 求損益平衡：
$$\underbrace{\min(i, n-i) \times C_{\text{node-access}}}_{\text{LL 走訪（不依賴 $s$）}} + C_{\text{malloc}} = \underbrace{(n - i) \times C_{\text{shift}}(s)}_{\text{陣列搬移（$\propto s$）}}$$
以隨機插入（$i$ 均勻分布，期望走訪距離 $n/4$）為例，解 $s$：
$$\frac{n}{4} \times C_{\text{node-access}} + C_{\text{malloc}} = \frac{n}{2} \times C_{\text{shift}}(s)$$
$$C_{\text{shift}}(s) = \frac{n/4 \times C_{\text{node-access}} + C_{\text{malloc}}}{n/2}$$
取 $C_{\text{node-access}} \approx 50$ 週期（L2/L3 命中）、$C_{\text{malloc}} \approx 100$、$n = 20000$：
$$C_{\text{shift}}(s) = \frac{5000 \times 50 + 100}{10000} \approx 25 \text{ 週期}$$
一個元素觸及的快取行數約 $\lceil s / 64 \rceil$，每條快取行搬移約 $4$–$10$ 週期。$C_{\text{shift}}(s) = 25$ 大致對應 $s \approx 128$–$256$ bytes——與實驗中 $s = 128$ 時逆轉的觀察吻合。
| 情境 | $C_{\text{LL}}(n, i, s)$ | $C_{\text{arr}}(n, i, s)$ | 損益平衡 |
|------|------------|---------|---------|
| 頭部（$i = 0$，有指標） | $C_{\text{malloc}} \approx 100$ | $n \times C_{\text{shift}}(s)$ | 解 $n$：$s=4$ 時 $n \approx 25$；$s=128$ 時 $n \approx 3$ |
| 尾部（$i = n$，有指標） | $C_{\text{malloc}} \approx 100$ | $\approx 0$ | 陣列永遠更快 |
| 隨機位置（需走訪） | $\frac{n}{4} C_{\text{node-access}} + C_{\text{malloc}}$ | $\frac{n}{2} C_{\text{shift}}(s)$ | 解 $s$：$n=20000$ 時 $s \approx 128$–$256$ bytes |
#### 實驗驗證
以 [`list_arr_bench.c`](https://github.com/laneser/warmup/blob/main/list_arr_bench.c) 對雙向環狀鏈結串列（每次 `malloc` 配置節點，random insert 採雙向走訪）和動態陣列（倍增策略 + `memmove`）分別插入 $n$ 個 `int` 元素，在三台不同架構的機器上各取 5 次平均：
| 機器 | CPU | 微架構 | 時脈 | L1d | L2 | L3 |
|------|-----|--------|------|-----|----|----|
| Raspberry Pi | Cortex-A53 | ARM in-order | 1.2 GHz | 32 KB | — | — |
| Celeron J1800 | Silvermont | x86 in-order | 2.4 GHz | 48 KB | 1 MB | — |
| DevContainer | Xeon/Core (OoO) | x86 out-of-order | ~4 GHz | 32+ KB | 256+ KB | 數 MB |
**Head insert（$i = 0$）：** 三台機器的趨勢一致——鏈結串列 per-op 成本穩定（不隨 $n$ 變化），陣列呈 $O(n)$ 成長。交叉點在 $n \approx 100$–$200$，與理論損益平衡 $n \approx 25$ 同一量級（差異來自 `memmove` 在小 $n$ 時的函式呼叫固定開銷）。
**Tail insert（$i = n$）：** 沒有走訪成本（`head->prev` 直接存取尾端），兩者都是 $O(1)$。但三台機器表現不同：
| 機器 | LL (ns/op) | Array (ns/op) | LL 週期 | Array 週期 | 結果 |
|------|-----------|--------------|---------|-----------|------|
| Cortex-A53 (in-order) | 175 | 88 | ~210 | ~106 | Array 快 2x |
| Celeron J1800 (in-order) | 63 | 45 | ~152 | ~107 | Array 快 1.4x |
| DevContainer (OoO) | 7.7 | 7.5 | ~31 | ~30 | 幾乎相同 |
差距**純粹來自 `malloc` 的成本**：陣列 tail insert 只做 `data[size++] = val`，不需配置記憶體，三台的 Array 週期數相近（~106 vs ~107 vs ~30）。而 `malloc` 的週期數從 OoO 的 ~31 到 in-order ARM 的 ~210 差距達 7 倍——`malloc` 涉及 pointer chasing（free list）、條件分支、metadata 存取，這些操作在亂序執行中可重疊進行，在循序執行核心上只能逐步等待。
**Random insert（雙向走訪）：** 鏈結串列採雙向走訪（$i \leq n/2$ 從頭，$i > n/2$ 從尾），期望走訪距離 $n/4$。$n = 50000$ 時各機器的陣列 / 鏈結串列速度比：
| 機器 | LL (ns/op) | Array (ns/op) | 陣列快幾倍 |
|------|-----------|--------------|----------|
| Cortex-A53 | 503,681 | 12,977 | 39x |
| Celeron J1800 | 174,928 | 6,742 | 26x |
| DevContainer | 35,329 | 309 | 114x |
三台機器一致顯示陣列遠勝鏈結串列——pointer chasing 的 $C_{\text{node-access}}$ 比連續搬移的 $C_{\text{shift}}$ 大一到兩個數量級。DevContainer 的差距更大（114x），因為 OoO + 大 L3 讓 `memmove` 的每元素成本極低，而 pointer chasing 即使在 OoO 上也無法有效重疊（每步依賴前一步的結果）。
實測結論：以 $s = 4$ bytes 而言，除了頭部插入（已知位置且 $n$ 夠大）外，陣列在所有機器、所有情境都更快。`malloc` 的成本高度依賴微架構（in-order vs OoO 差 7 倍），而 pointer chasing 在任何架構上都是瓶頸。但這只是 $s$ 小時的結果——下節將驗證 $s$ 增大後的逆轉現象。
#### 元素大小的影響
上述實驗以 4-byte `int` 為元素，但 Linux 核心中鏈結串列的元素通常是較大的結構體。從 DevContainer（Linux 6.6, WSL2）的 `/proc/slabinfo` 中篩選**確實作為鏈結串列節點**的結構體：
| slab 名稱 | `objsize` (bytes) | 鏈結串列成員（v6.19） |
|-----------|------------------|------|
| `vm_area_struct` | 176 | `anon_vma_chain`（[`include/linux/mm_types.h:957`](https://github.com/torvalds/linux/blob/v6.19/include/linux/mm_types.h#L957)） |
| `dentry` | 192 | `d_hash`, `d_lru`, `d_sib`, `d_alias`（[`include/linux/dcache.h:96-129`](https://github.com/torvalds/linux/blob/v6.19/include/linux/dcache.h#L96)） |
| `inode_cache` | 624 | `i_hash`, `i_io_list`, `i_lru`, `i_sb_list`, `i_wb_list`（[`include/linux/fs.h:824-856`](https://github.com/torvalds/linux/blob/v6.19/include/linux/fs.h#L824)） |
| `sock_inode_cache` | 832 | 透過內嵌的 `struct inode vfs_inode`（[`include/net/sock.h:1523`](https://github.com/torvalds/linux/blob/v6.19/include/net/sock.h#L1523)）參與上述 inode 鏈結串列 |
| `task_struct` | 11,840 | `tasks`, `children`, `sibling`, `pid_links` 等 7+ 個（[`include/linux/sched.h:957-1098`](https://github.com/torvalds/linux/blob/v6.19/include/linux/sched.h#L957)） |
多數結構體 $\geq 128$ bytes，`task_struct` 更達 11 KB。成本模型預測 $C_{\text{arr}}(n, i, s)$ 隨 $s$ 線性成長而 $C_{\text{LL}}(n, i, s)$ 幾乎不變，以下在三台機器上以 $s = 4 / 32 / 128 / 512$ bytes 實測驗證：
**Head insert（$n = 20000$）：** 三台機器一致顯示 LL 成本不隨 $s$ 變化，Array 成本與 $s$ 成正比。
| $s$ | DevContainer LL / Arr | ARM LL / Arr | x86 LL / Arr |
|-----|----------------------|-------------|-------------|
| 4 B | 8.9 / 253 (28x) | 179 / 9,943 (56x) | 74 / 6,132 (83x) |
| 32 B | 9.5 / 1,942 (204x) | 187 / 104,119 (557x) | 80 / 64,194 (802x) |
| 128 B | 14 / 10,035 (712x) | 181 / 1,279,596 (7,073x) | 129 / 342,420 (2,666x) |
| 512 B | 31 / 43,894 (1,416x) | 186 / 5,356,090 (28,797x) | 143 / 1,611,458 (11,276x) |
LL 在每台機器上的成本幾乎恆定（不隨 $s$ 變化），驗證了 $C_{\text{LL}}(n, i, s)$ 中 $s$ 被消去的推導。Array 成本則隨 $s$ 線性暴增——ARM 上 $s = 512$ 時 Array 比 LL 慢近 29,000 倍。
**Random insert（$n = 20000$）：** 這是最有趣的情境——陣列和鏈結串列都是 $O(n)$，勝負取決於 $s$。
| $s$ | DevContainer | ARM | x86 |
|-----|-------------|-----|-----|
| 4 B | Array 快 73x | Array 快 9.9x | Array 快 13x |
| 32 B | Array 快 11x | Array 快 3.5x | Array 快 6.3x |
| 128 B | Array 快 3.1x | **LL 快 3.6x** | LL ≈ Array |
| 512 B | **LL 快 1.4x** | **LL 快 15x** | **LL 快 4.4x** |
逆轉點因微架構而異：ARM（in-order，無大 L2/L3）在 $s = 128$ 即逆轉；x86 in-order 在 $s = 128$ 持平；DevContainer（OoO + 大 L3）要到 $s = 512$ 才逆轉。原因是 OoO 核心的 `memmove` 效率更高（prefetch + 指令重疊），拉高了陣列的損益平衡 $s$ 值。
Linux 核心常用結構體多數 $\geq 128$ bytes（見上方 slabinfo 表格），處於鏈結串列的優勢區間。
#### 小結
漸近分析只看 $n$ 的成長率，但實際插入成本取決於三個參數 $(n, i, s)$：
1. **$n$（元素數量）** 決定搬移量和走訪距離，但常數因子的差異往往比漸近行為更重要。鏈結串列的 `malloc` 在 in-order 核心上需 ~150–210 週期，在 OoO 核心上 ~30 週期；陣列 `memmove` 的每元素成本在小元素時僅 $\approx 4$ 週期。
2. **$i$（插入位置）** 決定是否需要走訪。O(1) 的前提是「已持有插入位置的指標」。一旦需要走訪定位，$C_{\text{traverse}}(n, i)$ 中 pointer chasing 的常數因子比陣列的連續搬移大一到兩個數量級。
3. **$s$（元素大小）** 是最關鍵的不對稱因子。$C_{\text{arr}}(n, i, s)$ 隨 $s$ 線性成長，$C_{\text{LL}}(n, i, s)$ 幾乎不變。$s = 4$ bytes 時陣列在 random insert 快 73 倍（OoO x86）；$s$ 增大後優勢逐步縮減，$s = 512$ bytes 時逆轉為鏈結串列快 1.4 倍（ARM 上 $s = 128$ 即逆轉）。Linux 核心常用結構體多數 $\geq 128$ bytes（見 slabinfo 表格），處於鏈結串列的優勢區間。
結論並非「陣列永遠比鏈結串列快」，而是取決於 $(n, i, s)$ 三者的組合。小元素 + 已知位置（如 tail pointer）時陣列佔優；大結構體 + 非尾部插入時鏈結串列更快。鏈結串列的另一優勢在於**結構特性**：插入刪除不影響其他元素的位址（不會使指標失效）、不需要連續記憶體區塊。選擇資料結構時，應根據 $(n, i, s)$ 的具體組合，而非僅看漸近複雜度。
### 鏈結串列歷屆測驗分析
- [ ] 逐一分析[第一週教材列出](https://wiki.csie.ncku.edu.tw/linux/schedule)的**題目 1** 到**題目 7**，確認理解題目且充分作答，並指出參考題解的錯誤和待改進之處
#### 題目 1
> 題目：[Linked List 練習題](https://hackmd.io/@sysprog/linked-list-quiz)（含分析）
> 參考題解：[LinYunWen/c-review (week4)](https://github.com/LinYunWen/c-review/tree/master/week4)
##### Q1：環狀雙向鏈結串列（FuncA/FuncB/FuncC）
題目給定環狀雙向鏈結串列（circular doubly-linked list）的結構與三個操作函式，要求推敲其功能並預測執行結果：
```c
struct node {
int data;
struct node *next, *prev;
};
```
**作答**
**FuncA**：在串列尾端插入新節點。開頭的 `if (!*start)` 處理空串列情況（新節點的 `next` 和 `prev` 皆指向自身）；非空時，透過 `(*start)->prev` 取得尾節點 `last`，將新節點接在 `last` 之後、`*start` 之前，維持環狀結構。`*start` 不變，故新節點成為尾節點。
**FuncB**：在串列開頭插入新節點。邏輯與 FuncA 相似——同樣取得 `last = (*start)->prev`，將新節點接在 `last` 之後、`*start` 之前——差異在於最後一行 `*start = new_node` 更新頭指標，使新節點成為新的開頭。
**FuncC**：在值為 `value2` 的節點之後插入值為 `value1` 的新節點。以 `while (temp->data != value2)` 走訪串列找到目標節點，再將新節點插入其後。
**執行結果預測**：
```
FuncA(&start, 51); // start → 51
FuncB(&start, 48); // start → 48 → 51
FuncA(&start, 72); // start → 48 → 51 → 72
FuncA(&start, 86); // start → 48 → 51 → 72 → 86
FuncC(&start, 63, 51); // start → 48 → 51 → 63 → 72 → 86
```
輸出：`Traversal in forward direction: 48 51 63 72 86`
**延伸題——排序所需的額外函式**：
- Bubble sort：需要 swap 函式（交換兩節點的資料或位置）
- Merge sort：需要 split 函式（將串列分成兩半）和 merge 函式（合併兩個已排序串列）
**題目程式碼與參考實作的改進建議**
參考題解的作答（FuncA/FuncB/FuncC 的功能推敲與執行結果預測）正確。以下針對題目程式碼及 [bubble sort 參考實作](https://github.com/LinYunWen/c-review/blob/master/week4/bubble_sort.c)提出 5 項改進建議。
**建議 1：FuncB 建議加入空串列防護**
```c
void FuncB(struct node **start, int value) {
struct node *last = (*start)->prev; /* *start == NULL 時 segfault */
```
第一行直接解引用 `(*start)->prev`，當 `*start == NULL` 時觸發 segmentation fault。FuncA 有 `if (!*start)` 的防護，FuncB 卻沒有。
**建議 2：FuncC 建議加入空串列防護**
```c
struct node *temp = *start;
while (temp->data != value2) /* *start == NULL 時 segfault */
```
與 FuncB 相同的問題——`*start == NULL` 時直接解引用 `temp->data` 導致 segfault。
**建議 3：FuncC 建議處理目標值不存在的情況**
```c
while (temp->data != value2)
temp = temp->next;
```
環狀串列沒有 `NULL` 終止條件。若 `value2` 不存在於串列中，`while` 迴圈會無限走訪。建議改用 `do { ... } while (temp != *start)` 並在迴圈結束後檢查是否找到目標。
**建議 4：exchange() 建議改為交換資料**
```c
void exchange(struct node **left, struct node **right) {
(*left)->next = (*right)->next; /* 覆蓋前未保存原值 */
(*right)->prev = (*left)->prev; /* 同上 */
(*left)->prev = *right;
(*right)->next = *left;
}
```
此函式意圖交換兩個相鄰節點的位置，但有兩個問題：
1. **覆蓋前未保存原值**：第 1 行覆蓋 `(*left)->next` 後，第 2 行讀取的 `(*left)->prev` 仍是舊值（此處恰好沒問題），但 `(*right)->next` 已在第 1 行被間接影響——因為 `*right` 就是原本的 `(*left)->next`。
2. **未更新鄰居指標**：交換後，`(*left)->next` 指向的節點的 `prev`、以及 `(*right)->prev` 指向的節點的 `next` 都未更新，導致鏈結完整性破壞。
對於此題（`data` 為 `int`），更簡潔的做法是**交換資料而非重新鏈結節點**——時間複雜度同為 $O(1)$ 且不涉及指標操作，不會破壞串列結構。
**建議 5：bubble_sort() 建議在每輪外層迴圈重設走訪起點**
```c
void bubble_sort(struct node **start, int length) {
struct node *left = *start;
struct node *right = left->next;
for (int i = 0; i < length - 1; i++) {
for (int j = i + 1; j < length; j++) {
...
left = left->next;
right = right->next;
}
/* left/right 未重設為 *start，下一輪從錯誤位置開始 */
}
}
```
`left` 和 `right` 在 `for (int i = ...)` 之前初始化，但每輪外層迴圈結束後未重設回起點。第二輪開始時，走訪從上一輪結束的位置繼續，導致排序結果錯誤。
修正後的完整實作（交換資料 + 每輪重設起點）見 [`quiz_linked_list/q1/fix_quiz1_q1.c`](https://github.com/laneser/warmup/blob/main/quiz_linked_list/q1/fix_quiz1_q1.c)。
**測試驗證**
使用 [Unity](https://github.com/ThrowTheSwitch/Unity) C 測試框架，對相同的 10 個測試案例分別執行原始版本和建議版本。原始版本使用 `fork()` 隔離執行以捕捉 segfault 和無限迴圈：
```
=== Suggested version (Unity tests) ===
test_FuncB_empty_list:PASS
test_FuncB_prepend:PASS
test_FuncC_empty_list:PASS
test_FuncC_value_not_found:PASS
test_FuncC_insert_after:PASS
test_bubble_sort_basic:PASS
test_bubble_sort_already_sorted:PASS
test_bubble_sort_reverse:PASS
test_bubble_sort_single:PASS
test_bubble_sort_duplicates:PASS
10 Tests 0 Failures 0 Ignored
=== Original version (expected failures) ===
test_FuncB_empty_list:FAIL: crashed (SIGSEGV)
test_FuncB_prepend:PASS
test_FuncC_empty_list:FAIL: crashed (SIGSEGV)
test_FuncC_value_not_found:FAIL: timed out (infinite loop)
test_FuncC_insert_after:PASS
test_bubble_sort_basic:FAIL: assertion failed
test_bubble_sort_already_sorted:FAIL: assertion failed
test_bubble_sort_reverse:FAIL: assertion failed
test_bubble_sort_single:PASS
test_bubble_sort_duplicates:FAIL: assertion failed
10 Tests 7 Failures 0 Ignored
```
測試程式碼：[quiz_linked_list/q1/](https://github.com/laneser/warmup/tree/main/quiz_linked_list/q1)，在 `quiz_linked_list/` 目錄下執行 `make q1_report` 即可產出上述結果。測試函式透過全域函式指標（`impl_FuncB`、`impl_FuncC`、`impl_bubble_sort`）呼叫實作，原始版本和建議版本共用相同的 10 個測試函式，僅在 `main()` 中綁定不同的實作。
##### Q2：單向鏈結串列的環偵測（FuncX）
題目給定單向鏈結串列與 `FuncX`，要求推敲功能並預測 K1–K5 及 count 的輸出。
**作答**
題目原始碼中 `FuncX` 的迴圈本體是 `data++`，但參考題解在分析時將其改為 `(*data)++`，初讀時被參考題解誤導。回頭對照題目原始碼後才注意到：`data` 是 `int *`，`data++` 只是遞增這個 local pointer copy，`*data`（即 `count`）從未被修改。這個差異決定了 count 的最終值。
`FuncX` 的實際行為：從 `head->next` 開始走訪，遇到 `NULL`（非環狀）或回到 `head`（環狀）時停止。回傳 `node - head`：環狀時 `node == head`，回傳 0；非環狀時 `node == NULL`，回傳 `NULL - head`（非零）。
各輸出推導：
| 輸出 | 結構變化 | FuncX 行為 | 結果 |
|------|---------|-----------|------|
| K1 | `head(0)→1→2→3→4→NULL` | `node` 走到 `NULL`，`return NULL - head ≠ 0` | **Yes** |
| K2 | `node3→next = head`，形成環 `head→1→2→3→head` | `node` 走到 `head`，`return 0` | **No** |
| K3 | `head→…→head→next = head→next`，展開後是 no-op | 同 K2 | **No** |
| K4 | `head→next = head`（繞環 2 圈回到 `head`） | `node = head→next = head`，迴圈不執行，`return 0` | **No** |
| K5 | `head→next→data = head→data` | — | **0** |
| count | `data++` 從未修改 `*data` | — | **0** |
**參考題解的改進建議**
1. **`data++` vs `(*data)++`**：題目原始碼是 `data++`（指標遞增），但參考題解在重新貼出程式碼時改為 `(*data)++`（值遞增），導致後續 count 的分析基於錯誤的前提。以題目原始碼為準，count 應為 0。
2. **K1 的 `return NULL - head` 是未定義行為**：C99 6.5.6§9 規定指標相減時兩個指標必須指向同一陣列物件的元素。`NULL` 減去有效指標不符合此條件。實務上多數平台得到非零值（印 "Yes"），但嚴格來說是 UB，參考題解未提及。
#### 題目 2
> 題目：[2020q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz1)（測驗 1：merge sort on singly-linked list）
> 參考題解：[Ryspon](https://hackmd.io/@Ryspon/HJVH8B0XU)、[chses9440611](https://hackmd.io/@chses9440611/Sy5gwE37I)
##### 選擇題作答
題目給定單向鏈結串列的 merge sort 實作（[原始碼](https://hackmd.io/@sysprog/linux2020-quiz1#%E6%B8%AC%E9%A9%97-1)），要求填入 LL0–LL6 七個空格。分為兩段分析：**split** 和 **merge**。
**Split**（LL0）：`left = start` 指向第一個節點，`right = left->next` 指向第二個。要讓 `left` 成為獨立子串列，需切斷 `left->next`：
- LL0 = `left->next = NULL`
**Merge**（LL1–LL6）：merge 迴圈將兩個已排序子串列合併。`merge` 指標追蹤合併結果的尾端，`start` 記錄合併結果的開頭。左右兩側的邏輯完全對稱：
| 空格 | 答案 | 說明 |
|------|------|------|
| LL1 | `start = merge = left` | 第一個合併元素來自 left，同時設定 start 和 merge |
| LL2 | `merge->next = left` | 將 left 接到合併結果尾端 |
| LL3 | `left = left->next` | 推進 left 指標 |
| LL4 | `start = merge = right` | 第一個合併元素來自 right |
| LL5 | `merge->next = right` | 將 right 接到合併結果尾端 |
| LL6 | `right = right->next` | 推進 right 指標 |
兩份參考題解的選擇題答案皆與上述一致。chses9440611 額外指出 LL1 可以只寫 `merge = left`（因為此時 `start == left`），但選項中 `start = merge = left` 更完整。
##### 延伸題 1：程式運作原理
此程式是 top-down recursive merge sort，但 split 策略特殊：每次只切下第一個節點（1 個元素）作為 `left`，剩餘全部（n-1 個元素）作為 `right`。遞迴樹長這樣（以 5 個元素為例）：
```
sort([1,5,3,2,4])
├── sort([1]) ← 1 個
└── sort([5,3,2,4]) ← 4 個
├── sort([5])
└── sort([3,2,4]) ← 3 個
├── sort([3])
└── sort([2,4]) ← 2 個
```
遞迴深度為 n-1。第 k 層 merge 的工作量為 k，總比較次數為 $1+2+\cdots+(n-1) = O(n^2)$。
##### 延伸題 2：改進空間
1. **Split 策略**：使用 fast/slow pointer 對半切（`slow` 每次走一步，`fast` 每次走兩步），遞迴深度降為 $O(\log n)$，每層總 merge 工作量為 $O(n)$，整體回到標準的 $O(n \log n)$。
2. **穩定性**：原始程式的比較條件是 `left->data < right->data`（嚴格小於），相等時走 else 分支取 right，打亂了相等元素的原始順序——排序不穩定。改為 `<=` 即可保證穩定性。Linux 核心的 [`lib/list_sort.c:19-20`](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L19-L20) 明確註明 `/* if equal, take 'a' -- important for sort stability */`。
3. **合併結果未收尾**：merge 迴圈結束後，最後一個被接上的節點的 `next` 仍指向其原本的下一個節點（已被排到其他位置），形成 dangling pointer。應在迴圈結束後加上 `merge->next = NULL`。以 `[2, 1, 3]` 為例：排序 `[1, 3]` 後 `1->next` 指向 `3`；與 `[2]` 合併時，`merge` 最終指向 `3`，但 `3->next` 仍是 merge 前的值——若原始串列更長，這可能指向已被重新鏈結的節點。在此題的 1-vs-(n-1) split 下，恰好因為 right 子串列是遞迴排序過的結果（尾端為 NULL），問題不會顯現；但若改為對半切，此 bug 會導致錯誤。
##### 延伸題 3+4：Circular doubly-linked list 與 list.h 風格
將排序擴充為 circular doubly-linked list，同時依循 Linux 核心 [`include/linux/list.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/list.h) 的設計：資料結構內嵌 `struct list_head`，透過 `container_of` 存取資料，比較函式接受 `struct list_head *` 參數。
策略參考 Linux 核心 [`lib/list_sort.c`](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c) 的做法：
1. 打斷環狀結構，轉為 NULL-terminated singly-linked list（暫時忽略 `prev`）
2. 用 fast/slow pointer 對半切，遞迴 merge sort
3. 排序完成後，重建所有 `prev` 指標並恢復環狀結構
merge 函式使用 `**tail` 技巧（同 `lib/list_sort.c`），避免 dummy node，並以 `<= 0` 比較保證穩定性。完整實作見 [`merge_sort_linux.c`](https://github.com/laneser/warmup/blob/main/quiz_linked_list/q2/merge_sort_linux.c)，對應的精簡版 `list.h` 見 [`list.h`](https://github.com/laneser/warmup/blob/main/quiz_linked_list/q2/list.h)。
##### 延伸題 5：Iterative 版本
將遞迴改為 bottom-up iterative：從寬度 1 開始，每輪將相鄰的兩個子串列合併，寬度倍增直到涵蓋整個串列。不需要遞迴的 call stack，空間複雜度 $O(1)$。完整實作見 [`merge_sort_iterative.c`](https://github.com/laneser/warmup/blob/main/quiz_linked_list/q2/merge_sort_iterative.c)。
##### 測試驗證
使用 [Unity](https://github.com/ThrowTheSwitch/Unity) 測試框架，對四個版本（原始、改進、iterative、list.h 風格）各執行 11 項測試：NULL、單元素、兩元素順序/逆序、已排序、逆序、重複值、全相同、負數、隨機（10 種大小 0–100）、穩定性。
穩定性測試（見 [`test_merge_sort_linux.c`](https://github.com/laneser/warmup/blob/main/quiz_linked_list/q2/test_merge_sort_linux.c) 的 `test_stability`）利用自訂 comparator 只比較低 16 位元，將原始位置編碼在 `data` 的高 16 位元，排序後驗證相同鍵的元素是否維持原始順序。將 [`merge_sort_linux.c:37`](https://github.com/laneser/warmup/blob/main/quiz_linked_list/q2/merge_sort_linux.c#L37) 的 `<=` 改為 `<`，穩定性測試立即失敗：`Expected 0x00010001 Was 0x00030001`（index=3 的元素排到了 index=1 之前）。
測試程式碼：[`quiz_linked_list/q2/`](https://github.com/laneser/warmup/tree/main/quiz_linked_list/q2)，在 `quiz_linked_list/` 目錄下執行 `make q2_report` 即可重現。
#### 題目 3
> 題目：[2020q3 第 1 週測驗題](https://hackmd.io/@sysprog/sysprog2020-quiz1)（測驗 1：singly-linked list 操作）
> 參考題解：[RinHizakura](https://hackmd.io/@RinHizakura/BysgszHNw)
##### 選擇題作答
題目給定 `add_entry`、`find_entry`、`remove_entry`、`swap_pair`、`reverse` 五個函式，要求填入 AA1、AA2、BB1、BB2、CCC 五個空格。
| 空格 | 答案 | 說明 |
|------|------|------|
| AA1 | `assert(new_node)` | malloc 後檢查是否成功 |
| AA2 | `*indirect = new_node` | 將新節點接到串列尾端 |
| BB1 | `node = &(*node)->next->next` | 推進到下一對節點（`->` 優先於 `&`） |
| BB2 | `*node = (*node)->next` | 將 node 指向的位址換成下一個節點 |
| CCC | `head->next = cursor; cursor = head` | 反轉指向後推進 cursor |
與參考題解答案一致。
##### 參考題解評論
此份參考題解寫得相當用心：以 Graphviz 逐步圖解每個函式的指標操作、深入探討 `assert` 的擺放位置（Issue 1）及使用時機（Issue 2）、延伸題全數完成（pointer-to-pointer 改寫、遞迴 reverse、Fisher-Yates shuffle），並針對 `swap_pair` 的兩種實作（交換指標 vs 交換值）做了效能實驗與 Cachegrind 分析。以下提出幾項額外建議。
**1. `assert(new_node)` 在 Linux overcommit 下形同虛設**
參考題解的 Issue 1 和 Issue 2 深入討論了 `assert` 的位置和用途，但在 Linux 預設的 overcommit 模式（`vm.overcommit_memory = 0`）下，`malloc` 幾乎不會回傳 NULL——核心先答應分配（只記帳），等實際存取時記憶體不足才觸發 OOM Killer 直接 `SIGKILL` 殺掉行程。程式碼裡的 `assert` 或 `if` 檢查都來不及執行。
`malloc` 失敗的本質是 OOM（記憶體不足），不是程式 bug，但 `assert` 的語意是「這不可能發生，發生就是 bug」。若要在 userspace 處理 OOM，概念上應該是 `fprintf(stderr, "Out of memory\n"); exit(1);`——不過在 Linux overcommit 下這也幾乎不會被觸發。
**2. `remove_entry` 沒有防護 entry 不在串列中**
```c
while ((*indirect) != entry)
indirect = &(*indirect)->next;
```
若 `entry` 不在串列中，`*indirect` 最終為 NULL，下一次迴圈執行 `&(*indirect)->next` 就是 dereference NULL。而若 `entry` 本身為 NULL，迴圈雖能正常結束，但隨後 `entry->next` 同樣 dereference NULL。
**3. `main` 中 `find_entry` 的回傳值沒有檢查**
```c
node_t *entry = find_entry(head, 101);
remove_entry(&head, entry); /* entry 可能是 NULL */
```
`find_entry` 找不到時回傳 NULL，直接傳給 `remove_entry` 會觸發上述的 NULL dereference。
**4. `recursive_rev` 沒有處理空串列**
```c
void recursive_rev(node_t **head) {
if (!head) /* 檢查的是 pointer-to-pointer，不是串列本身 */
return;
recursive_rev_step(*head, NULL, head); /* *head == NULL 時 crash */
}
```
當串列為空（`*head == NULL`）時，`recursive_rev_step(NULL, ...)` 會在 `curr->next` crash。建議改為 `if (!head || !*head)`。
**5. `shuffle` 中 `srand(time(NULL))` 建議放在 `main`**
`srand` 放在 `shuffle` 函式內，若短時間內多次呼叫，`time(NULL)` 回傳相同秒數，會產生相同的隨機序列。`srand` 應在程式啟動時呼叫一次，或改由呼叫者決定是否重設種子。
**6. 回應參考題解的延伸問題**
參考題解提出兩個延伸問題：如何檢驗 shuffle 是否「足夠亂」，以及是否有更有效率的實作方式。
對於驗證隨機性，可以多次執行 shuffle 後統計每個元素出現在每個位置的頻率，以 chi-squared test 檢驗是否偏離均勻分布。但更根本的問題是 `rand()` 本身——POSIX `rand()` 在某些實作中低位元的隨機性差，且 `rand() % len` 當 `len` 不整除 `RAND_MAX + 1` 時有 modulo bias。如果亂數來源不夠好，shuffle 演算法再正確也無法產生均勻分布的排列。更好的替代包括 `arc4random_uniform()`（無 modulo bias）或讀取 `/dev/urandom`。
效率方面，目前的實作每次隨機選取第 k 個節點需走訪 O(k) 步，總體為 O(n²)。對 singly-linked list 可用 merge-based shuffle 達到 O(n log n)：每層隨機決定每個元素分到左或右子串列，遞迴後合併。
#### 題目 4
> 題目：[2021q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz1)（測驗 1：singly-linked list quicksort）
> 參考題解：[linD026](https://hackmd.io/@linD026/2021q1_quiz1)
##### 選擇題作答
題目給定 singly-linked list 的 quicksort 實作，要求填入 LLL、AAA、BBB、CCC 四個空格。
`list_concat` 的 `while (*left)` 迴圈需將 `left` 推進到串列尾端的 `NULL` 位址。`left` 是 `node_t **`（指標的指標），因此每次迭代要取得「目前節點的 `next` 欄位的位址」：
- LLL = `left = &((*left)->next)`
`quicksort` 的 partition 迴圈中，`n->value > value` 為真時應加入 `right`，反之加入 `left`。`list_add_node_t` 的第一參數是 `node_t **`：
- AAA = `&right`
- BBB = `&left`
排序完成後，依序串接 left、pivot、right：
- CCC = `list_concat(&result, pivot); list_concat(&result, right)`
##### 參考題解評論
linD026 的題解品質很好：以 Graphviz 逐步圖解每個函式的指標操作、實作非遞迴版 quicksort、探討 linux-list 的 `list_qsort` 與題目程式碼的差異、並用 red-black tree 實作 tree sort 做效能比較。老師的四項回饋中：
1. PRNG 缺數學定義與評估標準——題解列出 glibc `random()` 原始碼，但未討論週期長度、均勻性、統計測試等理論面
2. **TCO：編譯器具體做了什麼**——題解提到 tail call optimization 的效益，但未展示編譯器層級的轉換細節（下方深入分析）
3. 「我想像中的 PRNG」措辭不當——技術寫作應以實驗結果和規格說明取代主觀印象
4. 為何 `list_sort` 用 merge sort 而非 tree sort——本報告前文的 [list_sort 分析](#2-為何不使用-quicksort) 有碰觸到此議題：穩定性、worst case O(n log n) 保證、以及 [量化分析](#鏈結串列-O1-vs-陣列-On：量化分析) 中 cache locality 在現代硬體上的影響
以下針對第 2 點展開。
##### 深入 TCO：兩個層次的 tail recursion
> 完整實驗程式碼與 Unity 測試：[`homework/warmup/tco/`](https://github.com/laneser/warmup/tree/main/tco)
>
> 在自己的機器上重現：
> ```shell
> cd tco
> make test # 執行 Unity 測試（52 項）
> make plot # 產生 qsort_O0.csv、qsort_O3.csv、qsort_bench.svg
> ```
> 需要 GCC 和 [uv](https://docs.astral.sh/uv/)（用於執行 `plot_bench.py`，自動安裝 matplotlib）。
「Tail recursion」在 quicksort 語境下有兩個不同層次的意涵，必須區分清楚。
**層次一：演算法層級的手動改寫**
題目的延伸閱讀 [Tail Recursion](https://www.cs.nthu.edu.tw/~wkhon/algo08-tutorials/tutorial2b.pdf)（清大教材）討論的是 quicksort 的 **stack 空間問題**。原始 quicksort 有兩個遞迴呼叫，worst case stack 深度 O(n)。教材提出：
- **Method I**：partition 後比較兩半大小，較大的用迴圈繼續 partition，較小的用遞迴處理。因為每次遞迴的對象保證 ≤ n/2，遞迴深度 O(log n)。
- **Method II**（教材稱之為 "tail recursion"）：持續 partition 直到所有片段 < n/2，才遞迴處理。遞迴深度同樣 O(log n)。
這是程式設計師**手動**決定哪邊遞迴、哪邊迴圈，藉此控制 stack 深度。
**層次二：編譯器自動 TCO**
編譯器的 Tail Call Optimization 是另一回事：當遞迴呼叫位於函式的最後一個操作（tail position），呼叫返回後不需要再做任何運算，編譯器可以將 `call` 替換為 `jmp`，重用當前 stack frame。GCC 透過 `-foptimize-sibling-calls`（`-O2` 以上自動啟用）實現此轉換。
兩者的關聯：手動改寫把一個遞迴呼叫消除為迴圈，這恰好是編譯器 TCO 「會做的事」——只是程式設計師自己做了。差別在於編譯器 TCO 只能處理已經在 tail position 的呼叫，而手動改寫可以重新組織程式邏輯來達成。
##### 四版 quicksort 實驗
為了驗證這兩個層次在 linked list quicksort 上的實際效果，實作四個版本並以 [Unity](https://github.com/ThrowTheSwitch/Unity) 驗證正確性（52 項測試全部通過）：
```c
/* Version 1: 教材原版——兩個遞迴呼叫 */
void qsort_original(node_t **list) {
/* ... partition ... */
qsort_original(&left);
qsort_original(&right);
/* concat left + pivot + right */
}
```
```c
/* Version 2: linD026 的 quicksort_tco——跳過空 partition 的遞迴 */
void qsort_tco(node_t **list) {
/* ... partition ... */
if (!left && right) {
/* 只遞迴 right */
} else if (left && right) {
/* 兩邊都遞迴 */
} else if (left && !right) {
/* 只遞迴 left */
} /* else: 只有 pivot */
}
```
```c
/* Version 3: 清大教材策略——遞迴較小半，迴圈處理較大半 */
void qsort_method2(node_t **list) {
node_t *suffix = NULL;
while (*list) {
/* ... partition, count lc/rc ... */
if (lc <= rc) {
qsort_method2(&left); /* 遞迴小的 */
/* concat + 迴圈繼續 sort right */
} else {
qsort_method2(&right); /* 遞迴小的 */
/* 把 pivot+sorted_right 存入 suffix */
/* 迴圈繼續 sort left */
}
}
*list = suffix; /* 接上暫存的尾段 */
}
```
```c
/* Version 4: 完全無遞迴——顯式 stack (alienryderflex 風格) */
void qsort_iterative(node_t **list) {
node_t *stack[256];
int top = 0;
stack[top++] = *list;
node_t *result = NULL, **rtail = &result;
while (top > 0) {
node_t *sub = stack[--top];
if (!sub->next) { /* 單節點：直接接到 result */
*rtail = sub; rtail = &sub->next;
continue;
}
/* partition, push right/pivot/left (pop 順序 = left/pivot/right) */
}
*list = result;
}
```
Version 3 的 `suffix` 技巧值得說明：當較大半是 left 時，無法用 `list = tail` 的尾端接續技巧（因為 left 在結果前端），改為把「pivot → sorted_right」暫存到 `suffix`，迴圈結束後再接上。
##### 組合語言分析
檢查 GCC 13.3.0 `-O2` 產生的組合語言（`qsort_impl_O2.s`），計算每個版本的 `call` 指令數量：
| 版本 | `call` 指令數 | 說明 |
|------|-------------|------|
| `qsort_original` | 2 | 兩個遞迴，都不在 tail position |
| `qsort_tco` | 4 | if/else 四個分支各有遞迴呼叫 |
| `qsort_method2` | 2 | 兩個分支各一個遞迴（每次只遞迴較小半） |
| `qsort_iterative` | 0 | 完全無遞迴 |
GCC **未對任何版本**自動進行 TCO。每個版本的遞迴函式都有 stack-allocated 區域變數（`left`、`right`、`pivot` 等），GCC 無法在 tail call 前安全釋放 stack frame。對 linked list quicksort 而言，編譯器自動 TCO 實際上**不適用**——必須靠手動改寫。
##### 效能量化
三台機器上各跑 1000 trials（n=10000），每 10 trials 取平均：
三台機器的絕對時間差距很大（Ryzen 9800X3D ~0.6 ms vs RPi 3B ~7 ms），但四個版本的**相對排名在三台機器上完全一致**，且 `-O0` 與 `-O3` 不改變排名：
| 排名 | 版本 | 策略 | Stack 最壞 |
|-----|------|------|-----------|
| 1 | `qsort_iterative` | 顯式 stack，零遞迴 | O(n)* |
| 2 | `qsort_method2` | 遞迴較小半，迴圈較大半 | **O(log n)** |
| 3 | `qsort_original` | 兩邊遞迴 | O(n) |
| 4 | `qsort_tco` | 跳過空 partition | O(n) |
\* `qsort_iterative` 的顯式 stack 大小固定為 256，足以處理 2^256 個元素；實務上等同 O(1)。若搭配 Method I 的「push 較小半」策略，可保證只需 O(log n) 個 stack entries。
`qsort_iterative` 最快的原因：沒有函式呼叫開銷，且用 `result_tail` 指標 O(1) 追加結果，省去 `list_concat` 的走訪。`qsort_tco`（linD026）反而最慢：四個 if/else 分支帶來額外的分支預測壓力和重複的 `list_concat` 呼叫，卻完全沒有減少遞迴深度。
##### 回應老師的問題：GCC 對 TCO 具體做了什麼
老師的回饋要求說明「編譯器具體做了什麼」。答案分兩個層次：
**GCC 自動 TCO 的機制（`-foptimize-sibling-calls`）：** 當遞迴呼叫滿足以下條件時，GCC 將 `call` 替換為 `jmp`，重用當前 stack frame：
1. 呼叫位於 tail position（之後沒有任何操作）
2. 被呼叫函式的參數不引用 caller 的 stack frame
3. caller 的 stack frame 可以安全釋放（無需 stack canary 保護的區域變數）
**對 linked list quicksort 的實際結果：** GCC 的自動 TCO 在此**不適用**。即使手動把第二個遞迴呼叫移到 tail position，函式內的區域變數（`left`、`right`、`pivot` 等）使得 stack frame 無法重用。這意味著 linked list quicksort 的 stack depth 改善**只能靠手動改寫**——正是清大教材 Method I/II 所描述的演算法層級策略。
`qsort_method2` 的實作展示了這一點：透過比較 partition 大小、只遞迴較小半（保證 ≤ n/2），手動確保遞迴深度 ≤ log₂n。這是演算法設計者的責任，不能依賴編譯器。
##### linD026 題解的問題
linD026 將其改寫命名為 `quicksort_tco`，但名稱有誤導：
| | 做了什麼 | 效果 |
|---|---|---|
| **清大教材 Method I/II** | 對較小 partition 遞迴，較大的迴圈處理 | Stack depth O(log n) |
| **GCC 自動 TCO** | 將 tail position 的 `call` 替換為 `jmp` | 重用 stack frame |
| **linD026 `quicksort_tco`** | 分出 left/right 為空的四種情況 | 省掉對空串列的 `call`（early termination） |
linD026 的版本既沒有「選較小 partition 遞迴」（教材策略），也沒有任何 `call` 在 tail position（編譯器 TCO）。它做的只是 early termination——跳過空 partition 的遞迴呼叫——不改變 stack depth 的漸近行為，實測反而因額外的分支判斷而比原版更慢。
題解的效能比較聲稱「迴圈版本自製的 stack，其效能無法與被編譯器最佳化過的其他兩個版本相比」，但此處的「編譯器最佳化」指的是 `-O3` 的一般性改善（inlining、register allocation 等），並非 TCO。本實驗在三台機器上的結果恰好相反：`qsort_iterative`（完全迴圈化）是四個版本中最快的。
---
#### 題目 5
> 題目：[2022q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz1)（測驗 1–4：Two Sum hash table、Remove Duplicates、LRU Cache、Longest Consecutive Sequence）
> 參考題解：[qwe661234](https://hackmd.io/@qwe661234/linux2022-quiz1)
本題涵蓋四個子題，皆圍繞 hash table 與 linked list 的結合應用。參考題解的整體品質不錯：以 Graphviz 圖解資料結構、完成所有延伸問題、用 Valgrind 驗證記憶體洩漏修復、並以 Linux 核心風格的 `hlist` 重新實作測驗四。以下指出兩個程式正確性問題作為改進建議，以及一個筆誤。
##### 建議改進 1：測驗二 circular doubly-linked list 遞迴版本的邏輯錯誤
題解的遞迴版本缺少 `else`，導致重複節點被遞迴處理兩次：
```c
void deleteDuplicates(struct list_head *cur, struct list_head *head)
{
if (cur == head)
return;
if (/* cur 是重複節點 */) {
deleteDuplicates(cur->next, head);
list_del(cur);
}
deleteDuplicates(cur->next, head); /* 無 else → 重複節點多遞迴一次 */
}
```
當 `cur` 滿足重複條件時，先在 `if` 內對 `cur->next` 遞迴，再對同一個 `cur->next` 重複遞迴。更嚴重的是，`list_del(cur)` 將 `cur->next` 設為 NULL，隨後 `dedup_recur_original(cur->next, head)` 等同於 `dedup_recur_original(NULL, head)`——NULL 不等於 `head` 所以不會 return，接著存取 `NULL->next` 直接 segfault。
修正方式是加上 `else` 並調整順序——先保存 `next`，再刪除：
```c
void deleteDuplicates(struct list_head *cur, struct list_head *head)
{
if (cur == head)
return;
struct list_head *next = cur->next;
if ((next != head &&
list_entry(cur, element_t, list)->value ==
list_entry(next, element_t, list)->value) ||
(cur->prev != head &&
list_entry(cur, element_t, list)->value ==
list_entry(cur->prev, element_t, list)->value)) {
deleteDuplicates(next, head);
list_del(cur);
} else {
deleteDuplicates(next, head);
}
}
```
##### 建議改進 2：測驗二 iterative 版本對 sentinel head 做 `container_of`
題解的迭代版本使用 `list_for_each_safe`，但在比較值時未檢查 `safe` 是否為 sentinel head：
```c
list_for_each_safe (cur, safe, head) {
if (list_entry(cur, element_t, list)->value ==
list_entry(safe, element_t, list)->value) {
```
[`list_for_each_safe`](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的展開為：
```c
for (pos = (head)->next, n = pos->next;
!list_is_head(pos, (head));
pos = n, n = pos->next)
```
當 `cur` 是串列中最後一個節點時，`safe == head`。此時 `list_entry(safe, element_t, list)` 對 sentinel head 執行 `container_of`——但 `head` 並非嵌入在 `element_t` 結構內，取出的 `->value` 是任意記憶體內容，屬於未定義行為。
修正方式是在比較前加入 `safe != head` 的檢查：
```c
list_for_each_safe (cur, safe, head) {
if (safe != head &&
list_entry(cur, element_t, list)->value ==
list_entry(safe, element_t, list)->value) {
```
##### 筆誤：測驗四改進版的 `sizeof`
題解的改進版將 `malloc(sizeof(*node))` 寫成 `malloc(sizeof(node))`——前者配置結構體大小（24 bytes），後者只配置指標大小（8 bytes）。以題解貼出的程式碼執行 Valgrind 會報告 55 個 `Invalid write`/`Invalid read` 錯誤，與題解展示的 0 errors 截圖矛盾；補回 `*` 後 Valgrind 結果為 0 errors，與截圖吻合。推論是貼程式碼時漏掉了 `*`。
##### 以 Unity 測試驗證
將上述兩個問題及修正版本分別實作，以 [Unity](https://github.com/ThrowTheSwitch/Unity) 測試框架驗證。完整程式碼見 [`quiz5_hashtable/`](https://github.com/laneser/warmup/tree/main/quiz5_hashtable)，`make report` 一次產出所有結果：
```
$ make report
=== Fixed versions (9 tests) ===
test_dedup_iter_fixed_last_unique:PASS
...
test_dedup_recur_fixed_no_dup:PASS
9 Tests 0 Failures 0 Ignored
=== Original iterative: ASan detects sentinel head UB ===
ERROR: AddressSanitizer: stack-buffer-underflow on address ...
SUMMARY: AddressSanitizer: stack-buffer-underflow dedup.h:68 in dedup_iter_original
=== Original recursive: segfault (NULL deref after list_del) ===
exit code: 139 (139 = segfault)
```
修正版 9 項全數通過；原始 iterative 版被 ASan 偵測到對 sentinel head 做 `container_of` 的越界讀取；原始 recursive 版因 `list_del` 後存取 `NULL->next` 而 segfault。
#### 題目 6
> 題目：[2023q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz1)（測驗 1：Quick sort on linked list、Hybrid sort）
> 參考題解：[yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-quiz1)
- [ ] 引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，量化性能表現並探討不同資料集的影響
- [ ] 嘗試對 Linux 核心提出排序程式碼改進的貢獻
##### Hybrid sort：將 Timsort 的 natural run detection 移植至 `list_sort`
測驗 1 的延伸問題要求引入 hybrid sort 策略。參考題解的 yanjiew1 進一步撰寫了〈[Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort)〉，分析了 Timsort 對 merge sort 的三項改善——cache miss 降低、記憶體使用改善、比較次數減少——並嘗試在 Linux 核心的 linked list 上實作完整 Timsort。以下在 yanjiew1 的研究基礎上出發。
[Timsort](https://en.wikipedia.org/wiki/Timsort) 的核心觀察是：真實資料往往部分有序，包含多段已排序的子序列（稱為 *natural runs*）。若排序演算法能偵測這些 runs 並直接利用，便可將比較次數從 $O(n \log n)$ 降至 $O(n \log r)$，其中 $r$ 是 natural runs 的數量。
Linux 核心的 `list_sort`（[`lib/list_sort.c`](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c)）已是精心設計的 bottom-up merge sort——延遲合併策略保證至少 2:1 平衡、cache 友善、且比較次數接近理論下界。但它每次只將**單一元素**推入 pending stack，沒有利用輸入中既有的有序性。
##### 修改策略
yanjiew1 的研究指出完整 Timsort 在 linked list 上的挑戰：galloping mode 需要 random access、minrun 的 insertion sort 對鏈結串列改善有限、合併策略需維護額外的 runs stack。因此，僅從 Timsort 借用 natural run detection 機制，合併策略維持原本的 bit-counting scheme 不變。具體修改：
1. **掃描 natural run**：每次從輸入取出一段最長的單調子序列，而非單一元素
- 升序 run：`cmp(cur, next) <= 0`（包含相等，維持穩定性）
- **嚴格**降序 run：`cmp(cur, next) > 0`（嚴格不等，反轉後不破壞穩定性）
2. **就地反轉降序 run**：使其成為升序，三指標交換，$O(\text{run\_len})$
3. **整段 run 推入 pending stack**：`count++` 計的是 run 數量而非元素數量
4. **快速路徑**：若整個輸入只有一個 run（已排序或全反序），直接還原雙向鏈結，$O(n)$
完整實作見 [`list_sort_runs.c`](https://github.com/laneser/warmup/blob/main/listsort_timsort/list_sort_runs.c)。`merge()` 和 `merge_final()` 與原版完全相同。
##### 核心程式碼差異
原版 `list_sort` 的主迴圈每次取一個元素：
```c
/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
```
修改後改為掃描整段 run：
```c
run_tail = list;
if (run_tail->next && cmp(priv, run_tail, run_tail->next) > 0) {
/* Strictly descending run */
while (run_tail->next && cmp(priv, run_tail, run_tail->next) > 0)
run_tail = run_tail->next;
/* Reverse in-place */
...
} else {
/* Ascending run */
while (run_tail->next && cmp(priv, run_tail, run_tail->next) <= 0)
run_tail = run_tail->next;
}
next_list = run_tail->next;
run_tail->next = NULL;
/* Push entire run */
list->prev = pending;
pending = list;
list = next_list;
count++;
```
##### 為何不引入完整 Timsort
yanjiew1 在〈[Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort)〉中分析了完整 Timsort 的三大機制：minrun 強制長度（以 insertion sort 補足短 run）、Fibonacci-like invariant 合併策略、以及 galloping mode。他指出在 linked list 上的挑戰：
- **Galloping mode** 需要 random access（二分搜尋），鏈結串列只能循序走訪，無法受益
- **Insertion sort 補短 run** 對鏈結串列的改善有限，反而增加程式碼複雜度
- **合併策略改變** 需要額外的 stack 記錄每個 run 的大小，且會破壞現有 `list_sort` 經驗證的 worst-case 保證
- **記憶體改善**（只合併重疊部分）在 linked list 上不適用——linked list 的 merge 本就是 in-place 操作
因此，保留原本的 bit-counting 合併策略，只加入 run detection，是風險最低且效益明確的改動。
##### Userspace benchmark
為了在提交 kernel patch 之前驗證效果，建立 [standalone userspace benchmark](https://github.com/laneser/warmup/tree/main/listsort_timsort)，從 `lib/list_sort.c` 抽出 vanilla 版和 run detection 版，以 `clock_gettime(CLOCK_MONOTONIC)` 計時。測試四種 pattern：
| Pattern | 說明 |
|---------|------|
| `full_random` | 均勻隨機值（對照基線） |
| `random_asc_runs` | 隨機長度的升序 runs 拼接，runs 之間不保證有序 |
| `random_desc_runs` | 隨機長度的降序 runs 拼接 |
| `random_mixed_runs` | 隨機長度、隨機升序或降序的 runs 拼接 |
每組 (pattern, n, variant) 執行 30 次取平均，`max_run_len` 控制隨機 run 的最大長度。
##### 固定 max_run_len=64 的結果
| Pattern | n=1,000 | n=10,000 | n=100,000 |
|---------|---------|----------|-----------|
| full_random | **-9.4%** | **-5.7%** | **-4.9%** |
| random_asc_runs | **+37.1%** | **+24.6%** | **+18.6%** |
| random_desc_runs | **+34.9%** | **+25.1%** | **+18.6%** |
| random_mixed_runs | **+29.9%** | **+20.7%** | **+15.7%** |
（正數為比較次數減少百分比，負數為 overhead）
Full random 的 overhead 約 5-9%，來自 run boundary detection 的額外比較（每對相鄰元素多一次 `cmp`）。有 natural runs 的資料則獲得 15-37% 的比較次數減少。
##### max_run_len sweep 分析
進一步以 `max_run_len` ∈ {8, 32, 64, 128, 256} 測試，觀察 run 長度對改善的敏感度（n=10,000）：
| max_run_len | random_asc_runs | random_desc_runs | random_mixed_runs |
|-------------|-----------------|------------------|-------------------|
| 8 | +7.4% | +7.3% | +3.4% |
| 32 | +18.6% | +18.7% | +14.7% |
| 64 | +24.6% | +25.1% | +20.7% |
| 128 | +31.3% | +31.7% | +27.2% |
| 256 | +38.8% | +38.6% | +34.5% |
觀察：
- **Run 越長，改善越大**：符合 $O(n \log r)$ 的預測——run 長度增加意味著 run 數量 $r$ 減少
- **Full random overhead 不受 max_run_len 影響**：固定 ~5%，因為隨機資料幾乎沒有長度 > 2 的 natural runs
- **升序與降序改善幾乎相同**：降序 run 的反轉是 $O(\text{run\_len})$ 的指標操作，不涉及比較
- **Mixed runs 改善略低**：升降交界處多一次方向判斷比較
##### 核心中 `list_sort` 的呼叫者分析
要評估此修改是否值得提交 patch，須確認核心中的 `list_sort` 呼叫者是否經常處理部分有序的資料。搜尋 v6.19 原始碼，`list_sort` 有約 30 個呼叫點，按輸入有序性分類：
**高度可能部分有序（檔案系統 metadata、I/O 操作）：**
| 呼叫點 | 排序對象 | 理由 |
|--------|---------|------|
| [`fs/gfs2/lops.c`](https://github.com/torvalds/linux/blob/v6.19/fs/gfs2/lops.c) | buffer data blocks | 交易期間寫入的 block 因 extent-based I/O 而傾向連續 |
| [`fs/btrfs/tree-log.c`](https://github.com/torvalds/linux/blob/v6.19/fs/btrfs/tree-log.c) | extent mappings | inode 的 extent 通常按起始位置有序 |
| [`fs/ext4/fsmap.c`](https://github.com/torvalds/linux/blob/v6.19/fs/ext4/fsmap.c) | metadata extents | 按 group 依序建構，inherent partial order |
| [`fs/xfs/xfs_buf.c`](https://github.com/torvalds/linux/blob/v6.19/fs/xfs/xfs_buf.c) | buffer objects (by block number) | writeout 累積的 buffer 傾向按 block 位址有序 |
| [`fs/ubifs/replay.c`](https://github.com/torvalds/linux/blob/v6.19/fs/ubifs/replay.c) | journal replay entries | 掃描 journal 時已按 sequence number 部分有序 |
| [`drivers/md/raid5.c`](https://github.com/torvalds/linux/blob/v6.19/drivers/md/raid5.c) | stripe operations (by sector) | I/O 模式導致 sector 有局部性 |
**不太可能有序（transaction items、裝置列舉）：**
| 呼叫點 | 排序對象 | 理由 |
|--------|---------|------|
| [`fs/xfs/xfs_trans.c`](https://github.com/torvalds/linux/blob/v6.19/fs/xfs/xfs_trans.c) | log items | 動態加入，順序反映操作時序而非邏輯順序 |
| [`drivers/acpi/nfit/core.c`](https://github.com/torvalds/linux/blob/v6.19/drivers/acpi/nfit/core.c) | DIMM descriptions | 來自 ACPI table，順序任意 |
檔案系統子系統佔了 `list_sort` 呼叫者的多數，而這些場景的資料因 extent-based allocation 和 sequential I/O 模式，天然地傾向部分有序。這意味著 run detection 在實際核心工作負載中確實有改善空間。
##### 核心實際工作負載的 list_sort 輸入分佈
為了驗證 run detection 在實際核心中的效益，在 lab-x86（x86_64, 2 cores, Ubuntu 24.04）上部署了 instrumentation-only patch。此 patch 不修改排序演算法本身，僅在 `list_sort()` 入口前掃描輸入串列的 natural run 數量，並透過 debugfs 介面（`/sys/kernel/debug/list_sort_stats/`）匯出統計資料。完整的 patch 腳本與工作負載測試程式位於 [`kernel_instrumentation_only_patch/`](https://github.com/laneser/warmup/tree/main/listsort_timsort/kernel_instrumentation_only_patch)，包含：
- `apply_instrumentation.sh` — 自動 patch 核心源碼（新增 `lib/list_sort_stats.{c,h}`、修改 `lib/list_sort.c`、`lib/Kconfig.debug`、`lib/Makefile`）
- `run_workload.sh` — 建立 XFS/btrfs loop device 並執行 I/O 工作負載以觸發 `list_sort()`
具體做法：在 `lib/list_sort.c` 的 `list_sort()` 開頭（串列轉為 singly-linked 之前）插入 O(n) 掃描，計算 ascending/descending run 數量，呼叫 `list_sort_stats_record()` 記錄至全域 atomic counter。以 v6.19 核心源碼為基礎，加上 `CONFIG_LIST_SORT_STATS=y` 編譯選項，在 devcontainer（16 cores）編譯後安裝至 lab-x86。
測試方法：建立 512MB loop device，分別以 XFS 和 btrfs 格式化，執行四種工作負載（mass file creation、random writes、metadata scan、mass deletion），每階段 30 秒。初版 instrumentation 僅記錄全域平均值，得到「平均 5 個元素」的結論；但平均值會掩蓋分佈的細節，因此改為 histogram bucket 版本，以 `[0,10)`, `[10,100)`, `[100,1000)`, `[1000,5000)`, `[5000,10000)`, `[10000,+∞)` 六個區間分別記錄呼叫次數、元素數、run 數與 already-sorted 比例。同時將 `__builtin_return_address(0)` 改為 `__builtin_return_address(1)` 以辨識 `list_sort()` 的實際呼叫者（level 0 只會回傳 `list_sort` 自身的位址）。
**XFS 檔案建立階段（30 秒，建立 2,773 個檔案）：**
| 區間 | 呼叫次數 | 總元素數 | 總 runs | already sorted | 平均元素數 |
|------|---------|---------|---------|----------------|-----------|
| [0,10) | 13,871 | 66,344 | 19,380 | 79% | 4 |
| [10,100) | 71 | 767 | 125 | 61% | 10 |
| [100,1000) | 1 | 172 | 73 | 0% | 172 |
| [1000,5000) | 1 | 2,991 | 221 | 0% | 2,991 |
per-caller breakdown：
| 呼叫者 | 呼叫次數 | avg 元素 | avg runs | max 元素 |
|--------|---------|---------|---------|---------|
| `__xfs_trans_commit` | 13,939 | 4 | 1 | 14 |
| `xfs_rmap_update_create_intent` | 3 | 2 | 1 | 3 |
| `xlog_cil_push_work` | 1 | 2,991 | 221 | 2,991 |
| `xfs_buf_delwri_submit_nowait` | 1 | 172 | 73 | 172 |
**XFS 檔案刪除階段：**
| 區間 | 呼叫次數 | 總元素數 | 總 runs | already sorted | 平均元素數 |
|------|---------|---------|---------|----------------|-----------|
| [0,10) | 13,984 | 69,480 | 20,853 | 69% | 4 |
| [10,100) | 15 | 173 | 37 | 26% | 11 |
| [1000,5000) | 2 | 5,816 | 495 | 0% | 2,908 |
per-caller breakdown：
| 呼叫者 | 呼叫次數 | avg 元素 | avg runs | max 元素 |
|--------|---------|---------|---------|---------|
| `__xfs_trans_commit` | 13,995 | 4 | 1 | 15 |
| `xfs_extent_free_create_intent` | 4 | 4 | 1 | 4 |
| `xlog_cil_push_work` | 1 | 2,947 | 306 | 2,947 |
| `xlog_cil_committed` | 1 | 2,869 | 189 | 2,869 |
Histogram 揭示了「平均 5 個元素」的統計假象：99.5% 的呼叫來自 `__xfs_trans_commit`（每次 transaction commit 排序 3-7 個 log items），但少數關鍵呼叫處理的串列規模完全不同：
- **`xlog_cil_push_work`**（CIL checkpoint）：將多筆 transaction 累積的 log vectors 批次排序後寫入 log，一次呼叫處理 ~3,000 個元素、~220-300 個 runs。CIL checkpoint 的觸發頻率取決於 log 緩衝區填滿速度，在密集 I/O 下每數秒觸發一次。
- **`xfs_buf_delwri_submit_nowait`**（buffer writeback）：將 dirty buffer 按 block number 排序後提交 I/O，觀測到 172 個元素、73 個 runs。
- **`xlog_cil_committed`**（CIL commit 完成回呼）：處理 ~2,900 個元素、~189 個 runs。
**btrfs 結果：** 所有工作負載的 `list_sort()` 呼叫次數均為 0。btrfs 的排序由其 B-tree 結構內部處理，v6.19 中 btrfs 的 `list_sort()` 呼叫點（[`tree-log.c`](https://github.com/torvalds/linux/blob/v6.19/fs/btrfs/tree-log.c)、[`raid56.c`](https://github.com/torvalds/linux/blob/v6.19/fs/btrfs/raid56.c)、[`block-group.c`](https://github.com/torvalds/linux/blob/v6.19/fs/btrfs/block-group.c)、[`volumes.c`](https://github.com/torvalds/linux/blob/v6.19/fs/btrfs/volumes.c)）在基本 I/O 操作中不被觸發。
##### 小結
Histogram 版本的 kernel instrumentation 揭示了僅看全域平均值會誤判 run detection 的價值：
**99.5% 的呼叫無關緊要：** `__xfs_trans_commit` 每次只排序 3-7 個 log items，且 79% 已完全有序。對這些呼叫而言，任何改善策略的效果都微乎其微——5 個元素的排序本身只需約 8 次比較。
**少數呼叫是真正的改善目標：** `xlog_cil_push_work` 處理 ~3,000 個元素、~220 個 runs。對此呼叫，run detection 可將比較次數從 $O(n \log n) \approx 3000 \times 11.5 \approx 34{,}500$ 降至 $O(n \log r) \approx 3000 \times \log_2 220 \approx 23{,}000$，減少約 33%。類似地，`xfs_buf_delwri_submit_nowait` 的 172 元素、73 runs 也能從 run detection 獲益。
Natural run detection 的修改量約 30 行（不含 instrumentation），worst case 仍為 $O(n \log n)$ 加上約 5% overhead（O(n) 前掃描）。**Userspace benchmark 的大串列（n=1,000-100,000）驗證了演算法層面的顯著改善；核心 histogram 數據進一步顯示，雖然大多數呼叫的串列過小以致改善有限，但 CIL checkpoint 等低頻大串列呼叫正是 run detection 能發揮作用的場景。**
#### 題目 7
> 題目：[2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)（測驗 2：Timsort 鏈結串列實作）
> 參考題解：[weihsinyeh](https://hackmd.io/@weihsinyeh/ry2RWmNTT)
- [ ] 解釋 Timsort 程式碼的運作原理，提出改進方案並予以實作
- [ ] 將改進過的 Timsort 實作整合進 sysprog21/lab0-c，設計效能評比的測試程式
##### 選擇題作答
測驗 2 的程式碼是基於 Linux 核心 `list_sort` 的 `merge` / `merge_final` 函式，加上 Timsort 的 `find_run` / `merge_collapse` / `merge_force_collapse` 框架。填空處：
- `AAAA`：`&head`（`merge` 中 tail 指標的初始化，指向 head 變數的位址）
- `BBBB`：`&a->next`（取 a 節點的 next 指標位址，作為下一個 tail）
- `CCCC`：`&b->next`（同理，取 b 節點的 next 指標位址）
- `DDDD`：`tail->next`（`build_prev_link` 結尾，最後一個節點的 next 指向 head）
- `EEEE`：`head->prev`（head 的 prev 指向最後一個節點，完成環狀結構）
- `FFFF`：`1`（若 stack 只剩 1 個 run，不需 merge，直接 `build_prev_link` 還原雙向環狀結構）
`AAAA`~`CCCC` 與核心 `lib/list_sort.c` 的 `merge()` 函式（[第 17 行](https://github.com/torvalds/linux/blob/v6.19/lib/list_sort.c#L17)）使用相同的 indirect pointer 技巧：`struct list_head **tail = &head` 讓 `*tail = a` 同時完成「設定 head」和「接續鏈結」兩個動作，不需額外的 if 判斷。
##### 與題目 6 的關係
本題的 Timsort 實作包含完整的 `find_run`（偵測 ascending/descending run 並反轉 descending）、`merge_collapse`（維護 stack 上 runs 的 Fibonacci-like 不變式）、galloping-free 的 `merge`。這與題目 6 中我們將 natural run detection 移植至 `list_sort` 的方向一致，但架構不同：
| 面向 | 題目 6（我們的實作） | 題目 7（本題 Timsort） |
|------|---------------------|----------------------|
| 基礎框架 | 核心 `list_sort` 的 bit-counting merge scheduling | Timsort 的 stack-based merge policy |
| Run 偵測 | 在 `list_sort` 主迴圈中偵測，整段 run 一次推入 | 獨立的 `find_run` 函式 |
| Merge 時機 | 原有的 `count` bit 規則（至少 2:1 平衡） | `merge_collapse` 的三條件不變式 |
| Descending run | 偵測後 in-place 反轉 | 同 |
| Run size 儲存 | 無需額外儲存（已由 merge scheduling 管理） | 將 `len` 塞入 `head->next->prev`（型別雙關） |
兩者本質上都是「偵測 natural runs 以減少不必要的 merge」，差異在於 merge scheduling 策略。核心 `list_sort` 的 bit-counting 方式已證明比較次數接近理論下界（見 [commit b5c56e0](https://github.com/torvalds/linux/commit/b5c56e0cdd62979dd538e5363b06be5bdf735a09) 引用的三篇論文），因此題目 6 選擇保留原有框架並僅加入 run detection，而非替換為完整 Timsort。
##### 參考題解評論
weihsinyeh 的題解對 `find_run`、`run_size`、`merge_at`、`merge_collapse` 的運作原理有詳細的圖解說明，並嘗試實作 Galloping mode 作為改進方案。以下就 Galloping mode 的分析提出兩點補充建議：
**1. Galloping mode 在鏈結串列上失效的根本原因**
weihsinyeh 觀察到 Galloping mode 使比較次數增加而非減少，並歸因於交替出現的 worst case。更根本的原因是：Galloping mode 的設計前提是 O(1) random access——exponential search 需要 $O(\log k)$ 次跳躍找到區間 $[2^{k-1}, 2^k]$，再用 binary search 定位，總計 $O(\log k)$ 次比較即可跳過 $k$ 個元素。然而鏈結串列不支援 O(1) random access，exponential search 的每次「跳躍」實際上需要逐節點走訪，退化為 O(k) 線性掃描，與逐對合併相比沒有減少走訪量，反而因額外的簿記邏輯增加了比較次數。這解釋了為何 weihsinyeh 的 cachegrind 測試中 Linux 原版的 miss 次數反而略少——galloping 的額外指標操作增加了 data cache 壓力，但在鏈結串列的非連續記憶體配置下，差異很小（D1 miss rate 同為 1.3%）。
**2. 若能輔以真實核心工作負載數據，分析會更完整**
weihsinyeh 的分析停留在 userspace benchmark，使用隨機或人工構造的輸入。如題目 6 的 kernel instrumentation histogram 所示，核心中 `list_sort` 的呼叫分佈極度不均：99.5% 的呼叫來自 `__xfs_trans_commit`、只排序 3-7 個元素，但 CIL checkpoint（`xlog_cil_push_work`）單次處理 ~3,000 個元素、~220 個 runs。這類真實數據對於評估改進方案（包括 Galloping mode）的實際效益至關重要——在 n=5 的串列上差異微乎其微，但在 n=3,000 的 CIL checkpoint 上，run detection 可減少約 33% 比較次數。建議未來的改進分析可透過 debugfs instrumentation 收集核心實際呼叫的串列規模和有序程度，作為效能評估的依據。
## 細讀〈[Linux: 作業系統術語及概念](https://hackmd.io/@sysprog/linux-concepts)〉
### 頻繁系統呼叫是否等同於繞過 user/kernel 隔離
- [ ] 若一個惡意應用程式成功觸發多次系統呼叫並頻繁進入核心態，是否等同於繞過 user/kernel 隔離？分析：CPU privilege level、page table 權限位元、系統呼叫機制的作用和考量
答案為**否**——頻繁進入核心態不等於繞過隔離，因為每次系統呼叫的進入和返回都經過硬體強制的權限轉換，呼叫次數多寡不影響隔離的完整性。以下從三個層面分析。
#### CPU privilege level：每次進入都重新建立隔離
x86_64 的 `syscall` 指令將 CPU 從 Ring 3（user mode）切換至 Ring 0（kernel mode），此轉換由硬體執行，軟體無法跳過。在 Linux 核心中，系統呼叫的入口 [`arch/x86/entry/entry_64.S`](https://github.com/torvalds/linux/blob/v6.19/arch/x86/entry/entry_64.S#L88) 第 88-95 行：
```
SYM_CODE_START(entry_SYSCALL_64)
swapgs
movq %rsp, PER_CPU_VAR(cpu_tss_rw + TSS_sp2)
SWITCH_TO_KERNEL_CR3 scratch_reg=%rsp
movq PER_CPU_VAR(cpu_current_top_of_stack), %rsp
```
- `swapgs`（第 92 行）：切換 GS segment base 至核心空間，使核心能存取 per-CPU 資料
- `SWITCH_TO_KERNEL_CR3`（第 95 行）：切換 CR3 暫存器至核心 page table
返回時（同檔案第 159-167 行），`SWITCH_TO_USER_CR3_STACK` 和 `swapgs` 反向執行，恢復使用者態的 page table 和 GS base。這兩個步驟在**每次**系統呼叫的進入和返回都會執行，無論呼叫頻率多高，硬體轉換不可省略。
#### Page table 權限位元：KPTI 確保使用者態看不到核心記憶體
Linux 自 4.15 起實作 Kernel Page Table Isolation（KPTI），維護兩套 page table：核心態用完整 page table，使用者態只能看到使用者空間的映射。`SWITCH_TO_KERNEL_CR3` 的實作位於 [`arch/x86/entry/calling.h`](https://github.com/torvalds/linux/blob/v6.19/arch/x86/entry/calling.h#L167) 第 167-179 行：
```
.macro ADJUST_KERNEL_CR3 reg:req
ALTERNATIVE "", "SET_NOFLUSH_BIT \reg", X86_FEATURE_PCID
andq $(~PTI_USER_PGTABLE_AND_PCID_MASK), \reg
.endm
.macro SWITCH_TO_KERNEL_CR3 scratch_reg:req
ALTERNATIVE "jmp .Lend_\@", "", X86_FEATURE_PTI
mov %cr3, \scratch_reg
ADJUST_KERNEL_CR3 \scratch_reg
mov \scratch_reg, %cr3
.endm
```
`ADJUST_KERNEL_CR3` 透過 `andq` 清除 PTI 位元，將 CR3 指向核心 page table。反之，使用者態的 page table 中核心區域不存在映射——即使惡意程式頻繁觸發系統呼叫，每次返回使用者態後，核心記憶體再次不可見。
進一步地，[`arch/x86/mm/pti.c`](https://github.com/torvalds/linux/blob/v6.19/arch/x86/mm/pti.c#L164) 第 164-166 行還將使用者記憶體在核心 page table 中標記為 NX（不可執行），防止核心意外執行使用者程式碼。
#### 系統呼叫機制的作用和考量：多層過濾與資源限制
隔離不僅依賴硬體權限轉換，核心還在系統呼叫路徑上設置多層軟體防線。[`arch/x86/entry/syscall_64.c`](https://github.com/torvalds/linux/blob/v6.19/arch/x86/entry/syscall_64.c#L87) 第 90 行，**每次**系統呼叫都經過 `syscall_enter_from_user_mode()`，此函式檢查 [`include/linux/entry-common.h`](https://github.com/torvalds/linux/blob/v6.19/include/linux/entry-common.h#L33) 第 33-46 行定義的 7 種過濾旗標：
```c
#define SYSCALL_WORK_ENTER (SYSCALL_WORK_SECCOMP |
SYSCALL_WORK_SYSCALL_TRACEPOINT |
SYSCALL_WORK_SYSCALL_TRACE |
SYSCALL_WORK_SYSCALL_EMU |
SYSCALL_WORK_SYSCALL_AUDIT |
SYSCALL_WORK_SYSCALL_USER_DISPATCH |
ARCH_SYSCALL_WORK_ENTER)
```
其中 **seccomp**（[`kernel/seccomp.c`](https://github.com/torvalds/linux/blob/v6.19/kernel/seccomp.c#L1259) 第 1259 行起的 `__seccomp_filter()`，違規處理於第 1355-1370 行）可限制行程只能呼叫白名單中的系統呼叫，違規直接 `SIGKILL`。容器執行環境（Docker, gVisor）普遍啟用 seccomp 來縮限攻擊面。
針對「多個惡意行程同時發動」的場景，核心的防線不在於限制系統呼叫頻率本身，而是限制系統呼叫能取得的**資源**：
- **`RLIMIT_NPROC`**：[`kernel/fork.c`](https://github.com/torvalds/linux/blob/v6.19/kernel/fork.c#L2091) 第 2091 行，`fork()` 時檢查使用者的行程數上限，超過則回傳 `-EAGAIN`，阻止 fork bomb
- **`RLIMIT_CPU`**：同檔案第 1688 行，限制行程的 CPU 時間，超時送 `SIGKILL`
- **OOM killer**：[`mm/oom_kill.c`](https://github.com/torvalds/linux/blob/v6.19/mm/oom_kill.c) 在記憶體耗盡時選擇並終止佔用最多資源的行程
- **cgroups**：可對 CPU、記憶體、I/O 頻寬設定配額，限制一組行程的整體資源消耗
#### 當系統負載過重時：實務上的限制
惡意行程大量消耗 CPU 或記憶體時，理論上硬體中斷仍會正常觸發，但實務上系統的回應能力會嚴重退化。
**唯一可靠的手段是 Magic SysRq**（[`drivers/tty/sysrq.c`](https://github.com/torvalds/linux/blob/v6.19/drivers/tty/sysrq.c)）：Alt+SysRq+組合鍵直接在中斷上下文中執行核心命令（強制終止所有使用者行程、同步磁碟、重新開機），不需任何 userspace 行程被排程，因此即使系統幾乎無回應也能運作。
其餘手段在高負載下未必有效：
- **SSH 連線**：網路封包的接收確實由硬體中斷觸發，經 softirq 處理後放入 socket buffer（[`net/core/dev.c:7857`](https://github.com/torvalds/linux/blob/v6.19/net/core/dev.c#L7857) 的 `net_rx_action()`）。但 sshd 是普通 userspace 行程，必須被排程器排程才能從 socket `read()` 資料（[`net/core/sock.c:3602`](https://github.com/torvalds/linux/blob/v6.19/net/core/sock.c#L3602) 的 `sock_def_readable()` 僅喚醒行程，不執行它）。在記憶體壓力下，sshd 的記憶體頁可被 swap out（核心無自動保護機制，需行程主動呼叫 `mlockall()`），導致 sshd 被排程後又立刻因 page fault 進入 `io_schedule()` 等待磁碟 I/O（[`mm/filemap.c:1315`](https://github.com/torvalds/linux/blob/v6.19/mm/filemap.c#L1315)）。這就是實務上 swap 壓力大時 SSH 極慢甚至連不上的原因。
- **`CONFIG_PREEMPT`**：允許核心在更多時機點搶佔行程，降低排程延遲。但在 thrashing 場景下無濟於事——所有行程 page fault 後透過 `io_schedule()` 自願讓出 CPU（[`kernel/sched/core.c:7773`](https://github.com/torvalds/linux/blob/v6.19/kernel/sched/core.c#L7773)），瓶頸是磁碟 I/O 延遲而非 CPU 排程延遲，搶佔式排程沒有東西可搶佔。
- **Ctrl-C**：送 `SIGINT` 至前景行程群組，由終端驅動程式處理。對單一前景行程有效，但無法應對系統性的資源耗盡。
真正的威脅不是「頻繁進入核心態」，而是**核心本身的漏洞**——例如 buffer overflow 讓攻擊者在 Ring 0 執行任意程式碼、修改 page table 權限、或停用中斷。這類攻擊繞過的不是系統呼叫機制的隔離，而是利用核心程式碼的缺陷突破隔離邊界本身。
### fork-join 模型的最大並行行程數上界
- [ ] fork 作為並行流程的分岔點。假設一個程式流程包含 $n$ 個 fork 點與 $m$ 個 join 點，推導在最理想無同步成本下，可產生的最大並行行程數上界。
這裡的 $n$ 和 $m$ 是**執行期間**實際發生的 fork/join 次數，不是原始碼中的 fork 呼叫點數量（一個 for 迴圈裡的 fork 可以執行任意多次）。
每次 `fork()` 呼叫由一個行程發起，產生恰好一個新行程（[`kernel/fork.c:2731`](https://github.com/torvalds/linux/blob/v6.19/kernel/fork.c#L2731) 的 `SYSCALL_DEFINE0(fork)` 呼叫 `kernel_clone()`，建立一個 `task_struct`）。因此每次 fork 使行程數淨增 1，每次 join 使行程數淨減 1：
| 事件 | 行程數變化 |
|------|-----------|
| fork | +1 |
| join | −1 |
設起始行程數為 1。經過 $k$ 次 fork 和 $j$ 次 join 後，當下行程數為 $1 + k - j$。要最大化峰值，應將所有 fork 排在所有 join 之前——在最理想的排列下，$n$ 次 fork 全部完成後、尚未發生任何 join 時達到峰值：
$$\boxed{P_{\max} = n + 1}$$
$m$（join 次數）不影響上界——join 只決定程式結束時剩餘的行程數（$1 + n - m$），不影響過程中的峰值。題目納入 $m$ 的用意在於測試能否辨識出它與上界無關。
初始直覺可能認為 $n$ 次 fork 產生 $2^n$ 個行程，但那是將「fork 點」理解為「所有現存行程同時 fork 一輪」。實際上每輪若有 $p$ 個行程同時 fork，消耗的是 $p$ 個 fork 點。例如要從 1 個行程擴展到 $2^k$ 個，需要 $1 + 2 + 4 + \cdots + 2^{k-1} = 2^k - 1$ 個 fork 點，代入上界公式得 $(2^k - 1) + 1 = 2^k$，結果一致。
### Critical path 與 Amdahl's law
- [ ] 若 fork-join 模型可抽象為 DAG，請說明 critical path 長度如何決定 theoretical speedup，以及與 Amdahl's law 的關係
將 fork-join 程式建模為 DAG：每個節點是一個計算單元，邊代表依賴關係。定義兩個量：
- **Work** $T_1$：所有節點的計算量總和（= 單一處理器的執行時間）
- **Span** $T_\infty$：DAG 中最長路徑的長度（= 無限處理器時的執行時間，即 critical path）
以 $p$ 個處理器執行時，執行時間 $T_p$ 受兩個下界約束：
$$T_p \geq T_\infty \quad \text{（critical path 上的節點必須依序執行，無法壓縮）}$$
$$T_p \geq \frac{T_1}{p} \quad \text{（$p$ 個處理器最多分攤 $p$ 倍工作量）}$$
合併得 $T_p \geq \max\!\left(\dfrac{T_1}{p},\; T_\infty\right)$。從這裡推導加速比上界：
$$S_p = \frac{T_1}{T_p}$$
因為 $T_p$ 在分母，$T_p$ 越大則 $S_p$ 越小。取 $T_p$ 的下界（最小值）可得 $S_p$ 的上界（最大值）。分別代入兩個下界：
- 由 $T_p \geq T_\infty$：$S_p = \dfrac{T_1}{T_p} \leq \dfrac{T_1}{T_\infty}$
- 由 $T_p \geq \dfrac{T_1}{p}$：$S_p = \dfrac{T_1}{T_p} \leq \dfrac{T_1}{T_1/p} = p$
兩個上界同時成立，取較緊的：
$$S_p \leq \min\!\left(p,\; \frac{T_1}{T_\infty}\right)$$
$T_1 / T_\infty$ 稱為 DAG 的 **parallelism**（最大可利用並行度）。無論處理器數量多大，加速比不可能超過此值。
**與 Amdahl's law 的關係：** Amdahl's law 是上述 DAG 模型的特例。假設程式中有比例 $f$ 的工作是序列的（只能由一個處理器執行），其餘 $(1-f)$ 可完美並行化。這對應一個特殊的 DAG 結構——序列段接完全並行段再接序列段。
在這個 DAG 中，critical path 長度 $T_\infty = f \cdot T_1$（序列部分無法縮短，並行部分在無限處理器下趨近零）。代入 DAG 上界可直接得到 $p \to \infty$ 的極限：
$$S_\infty \leq \frac{T_1}{T_\infty} = \frac{T_1}{f \cdot T_1} = \frac{1}{f}$$
但 Amdahl's law 更進一步——它的 DAG 結構簡單到可以算出**有限 $p$ 的精確執行時間**，不只是上界。以 $p$ 個處理器執行時：
- 序列部分無法分攤，耗時 $f \cdot T_1$
- 並行部分可完美均分給 $p$ 個處理器，耗時 $(1-f) \cdot T_1 / p$
- 兩段串接，總執行時間 $T_p = f \cdot T_1 + (1-f) \cdot T_1 / p$
因此加速比為精確值（不只是上界）：
$$S_p = \frac{T_1}{T_p} = \frac{T_1}{f \cdot T_1 + (1-f) \cdot T_1 / p} = \frac{1}{f + (1-f)/p}$$
取 $p \to \infty$：$(1-f)/p \to 0$，得 $S_\infty = 1/f$，與 DAG 上界吻合。
DAG 的 work-span 模型更為通用：它不要求並行部分「完美均分」，也適用於遞迴分治、不規則任務圖等任意結構，但只能給出上界。Amdahl's law 因為假設了最簡單的 DAG 結構，所以能給出精確公式。兩者的共同結論是：**加速比受限於不可並行的部分**——在 DAG 模型中是 critical path 長度 $T_\infty$，在 Amdahl's law 中是序列比例 $f$。
### Mach vs. Linux 的排程抽象：從 process-based 到 thread-based
- [ ] Mach microkernel 將 thread 與 task 分離為獨立物件。比較在 NPTL 之前的 Linux 核心與 Mach 的設計，在 scheduling abstraction 上的本質差異，而引入 NPTL 之後又如何讓 Linux 具備現代作業系統的關鍵特徵？
現代作業系統的三大關鍵特徵為：paged virtual memory（3BSD, 1979）、TCP/IP networking（BSD 4.1, 1983）、multiprocessing（Sequent Balance, 1984）。Linux 很早就具備前兩者，但在 NPTL 之前缺乏高效的多執行緒支援，限制了 multiprocessing 能力。問題的核心在於排程抽象：要在 SMP 系統上高效運行多執行緒程式，核心需要**將資源容器（address space、file descriptors）與可排程單位（thread）分離**——同一資源容器內可有多個 thread 共享資源並獨立排程。Mach 從設計之初就實現了這個分離；Linux 則經歷了從 process-based 到 thread-based 的演進。
#### Mach：task 與 thread 是獨立物件
Mach 的 task 不包含正在執行的 thread——thread 是獨立的物件。task 是資源容器（address space、port namespace），thread 是排程單位，兩者分離。一個 task 可包含多個 thread，排程器只看 thread。
#### Pre-NPTL Linux：process 是唯一的抽象
NPTL 出現之前，Linux 把 process 當作最基本的 abstraction——scheduling、context switch 的操作對象都是 process，thread / LWP 只是和別人分享定址空間和資源的 process。
具體而言，glibc 的 LinuxThreads 函式庫用 `clone()` 搭配 `CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND` 建立共享資源的行程來模擬 thread（[`linuxthreads/manager.c:753`](https://sourceware.org/git/?p=glibc.git;a=blob;f=linuxthreads/manager.c;hb=glibc-2.3#l753)）。但核心沒有 thread group 的概念，每個 thread 有獨立 PID、`kill()` 無法送信號給整個 thread group、且需要額外的 manager thread 協調建立和銷毀（[`pthread.c:721`](https://sourceware.org/git/?p=glibc.git;a=blob;f=linuxthreads/pthread.c;hb=glibc-2.3#l721)）。嚴格來說，Linux 只實作一半的 thread——犧牲 thread 的效率，以換取 process 的效率。
#### NPTL：核心加入 thread group，glibc 提供高效 thread library
NPTL（Native POSIX Threads Library）是 glibc 中取代 LinuxThreads 的 thread library，依賴核心的三項機制：
1. **`CLONE_THREAD`**（[`include/uapi/linux/sched.h:19`](https://github.com/torvalds/linux/blob/v6.19/include/uapi/linux/sched.h#L19)）：使新 task 加入父 task 的 thread group，共享 `tgid`（[`kernel/fork.c:2291`](https://github.com/torvalds/linux/blob/v6.19/kernel/fork.c#L2291)）。核心強制 `CLONE_THREAD` → `CLONE_SIGHAND` → `CLONE_VM` 的依賴鏈（[`kernel/fork.c:1993-2002`](https://github.com/torvalds/linux/blob/v6.19/kernel/fork.c#L1993)），因此指定 `CLONE_THREAD` 即隱含共享 address space 和 signal handler。`getpid()` 回傳 `tgid`（[`kernel/sys.c:999`](https://github.com/torvalds/linux/blob/v6.19/kernel/sys.c#L999)），同一 process 內所有 thread 看到相同 PID。
2. **Thread group 信號傳遞**：`kill()` 透過 `PIDTYPE_TGID` 將信號送到整個 thread group（[`kernel/signal.c:1471`](https://github.com/torvalds/linux/blob/v6.19/kernel/signal.c#L1471)），而非單一 task。
3. **`futex`**（[`kernel/futex/syscalls.c:188`](https://github.com/torvalds/linux/blob/v6.19/kernel/futex/syscalls.c#L188)）：即 Fast Userspace muTEX，無競爭時在 userspace 以 atomic 操作完成同步、不需進核心，取代 LinuxThreads 用 signal 實作同步的做法。
#### 對比
| | Mach | Pre-NPTL Linux | Post-NPTL Linux |
|--|------|---------------|----------------|
| 排程抽象 | thread（獨立物件） | process（`task_struct`） | `task_struct`（可為 process 或 thread） |
| 資源容器 | task（獨立物件） | `task_struct`（兼任） | thread group（`tgid`） |
| 分離方式 | 設計時就是兩種物件 | 無分離 | `clone()` 旗標組合 |
Linux 沒有像 Mach 建立兩種獨立的核心物件，而是用 clone flags 讓同一個 `task_struct` 同時扮演 process 和 thread。NPTL 之後，Linux 在排程抽象上達到了與 Mach 等同的能力——資源容器與可排程單位的分離——補齊了 multiprocessing 這項現代作業系統的關鍵特徵。
### VFS / network stack 遷移至 userspace 的影響分析
- [ ] 若將 Linux 的 VFS 或 network stack 遷移至 userspace (類似 microkernel multi-server 模型), 分析: context switch 數量變化, cache locality, fault isolation, worst-case latency
#### Context switch 數量
以 `read()` 為例。在 monolithic 架構中，應用程式發出 `read()` 後（[`fs/read_write.c:722`](https://github.com/torvalds/linux/blob/v6.19/fs/read_write.c#L722)），整個路徑——`ksys_read()` → `vfs_read()` → 具體檔案系統的 `read_iter()`——全部在同一次系統呼叫的核心態中完成，只需 1 次 user→kernel 切換 + 1 次 kernel→user 返回。網路收送亦同：`sock_sendmsg()`（[`net/socket.c:753`](https://github.com/torvalds/linux/blob/v6.19/net/socket.c#L753)）直接在核心態呼叫 `tcp_sendmsg()`（[`net/ipv4/tcp.c:1407`](https://github.com/torvalds/linux/blob/v6.19/net/ipv4/tcp.c#L1407)），一路到網卡驅動，不需額外的 IPC。
若改為 multi-server 模型，VFS server 和 network server 各自是獨立的 userspace 行程。同樣的 `read()` 至少需要：app→kernel（IPC）→VFS server→kernel（IPC）→filesystem server→kernel→app，每經過一個 server 至少多 2 次 domain crossing（進出核心）。
#### Cache locality
每次切換 address space 會導致 TLB flush 和 cache pollution。在 monolithic 架構中，VFS 層和具體檔案系統的程式碼共享核心的 address space，資料在 page cache（[`mm/filemap.c`](https://github.com/torvalds/linux/blob/v6.19/mm/filemap.c)）中可直接存取。Multi-server 模型下，不同 server 有各自的 address space，資料需要透過 IPC 複製或 shared memory mapping 傳遞。
不過 L4 的經驗指出，**極小的核心反而能改善 cache 行為**。Liedtke 在〈µ-kernels Must and Can Be Small〉中指出：更小的核心使用的 cache 自然更小，因 cache miss 帶來的開銷也更小。L4 的目標是讓核心程式碼完全容納於 L1 I-cache 內。2016 年 ARM Cortex-A57 的 48K L1 I-cache 已能容納精簡後的 L4 實作。換言之，cache locality 的損失取決於實作品質，而非架構必然的缺陷。
#### Fault isolation
Fault isolation 是 microkernel 的經典優勢：VFS server 或 network server 崩潰時，核心本身不受影響，理論上可重啟該 server 恢復服務。但課程教材指出一個重要的現實限制：
> 現代硬體難以彰顯 microkernel 當初藉由搬離裝置驅動程式，達到穩定的設計目標。
1980 年代的硬體很「笨」——作業系統直接控制磁碟的扇區和軌道，重啟驅動程式確實能恢復硬體狀態。但現代的儲存裝置、GPU、網路裝置內部就是一台電腦（甚至多處理器），擁有持久的內部狀態，可直接存取系統記憶體。重啟 GPU 驅動程式無法保證 GPU 處於可用狀態。因此，fault isolation 對 VFS 這類純軟體的服務仍有效，但對硬體驅動的保護程度不如預期。
#### Worst-case latency
多次 IPC 增加了請求的最長路徑，worst-case latency 相應增加。但 QNX 的經驗顯示這並非不可克服：Unix 和 Mach 使用同步系統呼叫，而 QNX 使用非同步系統呼叫，使其在即時場景（車載系統、核電站控制）中達到可接受的 worst-case latency，並在車用市場佔有率達到 75%。
對 Linux 的 network stack 而言，接收路徑已有非同步成分——softirq 的 `net_rx_action()`（[`net/core/dev.c:7857`](https://github.com/torvalds/linux/blob/v6.19/net/core/dev.c#L7857)）由軟體中斷觸發處理封包，與應用程式的系統呼叫路徑分離。若遷移至 userspace，原本在核心態 softirq 中一次完成的收包+協定處理，需改為跨 server 的 IPC 傳遞，worst-case latency 勢必增加。但 DPDK 等 userspace networking 方案表明，繞過核心直接在 userspace 處理封包，反而可以降低延遲——不過那是 bypass 而非 microkernel multi-server 架構。
Monolithic 架構的核心優勢在效能——同一 address space 內的函式呼叫遠快於跨行程 IPC。Microkernel 的優勢在結構清晰和 fault isolation。將 VFS 或 network stack 真正拆分為獨立 userspace server 的代價仍然顯著，這也是 Linux 至今維持 monolithic 架構的主因。
### Page fault 存取延遲的期望值模型
- [ ] 若 page fault handler 的平均成本為 $T_{pf}$，page fault 發生機率為 $p$，建立整體存取延遲的期望值模型
每次記憶體存取有兩種情況：
- 機率 $(1-p)$：頁面已在實體記憶體中，存取延遲為 $T_{mem}$（正常記憶體存取時間）
- 機率 $p$：發生 page fault，延遲為 $T_{pf}$
根據期望值定義，整體存取延遲為：
$$E[T] = (1-p) \cdot T_{mem} + p \cdot T_{pf}$$
### Spinlock 保護全域計數器的 scalability 分析
- [ ] scalability 常來自 cache coherence 與 lock 競爭。給定全域計數器使用 spinlock 保護，在 $N$ 核系統中，若每核每秒更新 $f$ 次，估算 coherence traffic 與 lock contention 成長趨勢
#### 前提：spinlock 的運作機制
Linux 的 spinlock（queued spinlock）在 fast path 透過 `atomic_try_cmpxchg_acquire` 嘗試取得鎖（[`include/asm-generic/qspinlock.h:111`](https://github.com/torvalds/linux/blob/v6.19/include/asm-generic/qspinlock.h#L111)），失敗則進入 `queued_spin_lock_slowpath` 排隊（[`kernel/locking/qspinlock.c:130`](https://github.com/torvalds/linux/blob/v6.19/kernel/locking/qspinlock.c#L130)）。`cmpxchg` 是 atomic read-modify-write 操作，硬體必須取得該 cache line 的**獨佔所有權**（MESI 協定的 Exclusive/Modified 狀態），這會觸發 invalidate 訊息讓其他所有持有該 cache line 的核心失效。
#### Coherence traffic
每次一個核心成功取得 spinlock 並更新計數器，涉及兩次寫入（lock acquire + counter write），每次寫入都讓其他核心的 cache line 失效。整個系統每秒共 $N \cdot f$ 次更新，每次更新產生 $O(N)$ 個 invalidate 訊息（通知其餘 $N-1$ 個核心）。因此：
$$\text{coherence traffic} = O(N^2 \cdot f)$$
coherence traffic 隨核心數**平方成長**。這是因為每次寫入的 invalidation 成本與核心數成正比，而寫入次數本身也與核心數成正比。
#### Lock contention
Spinlock 是序列化的——同一時間只有一個核心能持有鎖。設每次取得鎖到釋放鎖的時間為 $T_{hold}$（包含更新計數器的時間），則鎖的最大吞吐量為 $1/T_{hold}$ 次/秒。全系統對鎖的需求為 $N \cdot f$ 次/秒。
當 $N \cdot f \cdot T_{hold} \ll 1$ 時，競爭很少，各核心幾乎不需等待。但隨著 $N$ 增加，$N \cdot f \cdot T_{hold}$ 逐漸趨近 1，等待時間急劇上升。Lock contention（等待鎖的時間佔比）成長趨勢為：
$$\text{contention} = O(N)$$
每多一個核心就多一個競爭者，平均等待佇列長度線性成長。當 $N \cdot f$ 超過 $1/T_{hold}$ 時鎖完全飽和，多出的核心全部在空轉（busy-wait）。
---
## 參考資料
- [1] SEI CERT C Coding Standard, "[INT13-C. Use bitwise operators only on unsigned operands](https://wiki.sei.cmu.edu/confluence/display/c/INT13-C.+Use+bitwise+operators+only+on+unsigned+operands)."
- [2] MITRE, "[CWE-682: Incorrect Calculation](https://cwe.mitre.org/data/definitions/682.html)."
- [3] ARM, *[ARM Architecture Reference Manual, ARMv7-A and ARMv7-R edition](https://developer.arm.com/documentation/ddi0406/c)* (DDI 0406C).
- [4] RISC-V International, *[The RISC-V Instruction Set Manual, Volume II: Privileged Architecture](https://riscv.github.io/riscv-isa-manual/snapshot/privileged/)*.
- [5] K. Serebryany, D. Bruening, A. Potapenko, D. Vyukov, "[AddressSanitizer: A Fast Address Sanity Checker](https://www.usenix.org/system/files/conference/atc12/atc12-final39.pdf)," USENIX ATC, 2012.；LLVM 實作：[`AddressSanitizer.cpp`](https://llvm.org/doxygen/AddressSanitizer_8cpp_source.html)
- [6] Intel, *[Intel® 64 and IA-32 Architectures Optimization Reference Manual](https://www.cs.utexas.edu/~hunt/class/2016-spring/cs350c/documents/Intel-x86-Docs/64-ia-32-architectures-optimization-manual.pdf)* (Document 248966-031), §2.4.4.2 "Data Prefetch to L1 caches," §3.7.2 "Hardware Prefetching for First-Level Data Cache."
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet