# 2026q1 Homework3 (basics)
> contributed by < [Shaoen-Lin](https://github.com/Shaoen-Lin) >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 細讀〈[浮點數運算](https://hackmd.io/@sysprog/c-floating-point)〉
### Q1
- [ ] IEEE 754 的表示法與運算陷阱中，catastrophic cancellation (二個相近數值相減導致有效位數大幅流失) 尤為重要。作業二分析 MIPS FPU 軟體模擬器的 sticky-bit 截斷與 round-to-even，以及 `float32_to_float16` 的 denormalized 路徑。以此為出發點：
* (a) Linux 核心的計時子系統以 `s64` (帶號 64 位元整數) 儲存奈秒級時間戳。`ktime_sub()` 計算二個時間戳的差值時，定點數減法不會出現 catastrophic cancellation，因為整數減法的相對誤差為零 (結果精確)。證明此性質：對 $a, b \in \mathbb{Z}$，$a - b$ 在整數算術下精確無誤差，而 IEEE 754 浮點數減法 $\text{fl}(a - b)$ 在 $|a - b| \ll |a|$ 時相對誤差可達 $O(1)$。以此解釋為何 Linux 核心的時間子系統選擇整數奈秒而非浮點秒
* (b) subnormal numbers 在某些處理器上造成 denormal penalty (Intel 的 SSE 路徑可能降速 100 倍)。閱讀 [`arch/x86/kernel/fpu/xstate.c`](https://github.com/torvalds/linux/blob/master/arch/x86/kernel/fpu/xstate.c) 的 FPU context switch 機制，說明 `fpstate` 如何儲存與恢復 MXCSR 暫存器 (含 FTZ/DAZ 旗標)。設計實驗：撰寫使用者空間程式分別在 FTZ=0 (denormal 正常處理) 與 FTZ=1 (denormal flush to zero) 模式下執行大量 subnormal 運算，以 `perf stat` 量測 cycles 差異，並驗證核心的 FPU context switch 正確恢復每個行程獨立的 MXCSR 設定
### Q2
- [ ] USS Yorktown 癱瘓、Ariane 5 爆炸等真實案例說明數值錯誤的嚴重後果。作業二分析 Boeing 787 的 32 位元計數器在約 248 天 overflow。從 Linux 核心的角度延伸：
* (a) 閱讀 [`kernel/time/clocksource.c`](https://github.com/torvalds/linux/blob/master/kernel/time/clocksource.c) 的 `clocks_calc_mult_shift()`，此函式在給定的 `from` (Hz)、`to` (Hz) 與 `maxsec` (最大不溢位秒數) 約束下選擇最大的 `shift` 值以最大化定點精度。推導 `mult` 與 `shift` 的選擇如何決定「在不溢位的前提下可表示的最長時間間隔」，並以 TSC 頻率 3 GHz、`maxsec = 600` 為例，計算最佳的 `mult`/`shift` 值與對應的奈秒精度。此設計與 IEEE 754 的 exponent/fraction 位元分配有粗略的類比，兩者都是在固定位元預算下的精度與範圍的權衡
* (b) 設計一份 Linux 核心中可能受數值精度問題影響的子系統清單 (至少涵蓋 scheduler、timekeeping、networking、DRM/KMS)，針對每個子系統記錄其數值表示法的選擇與精度保證，以及在 git log 中是否存在因數值問題而修正的 commit
### Q3
- [ ] Linux 核心的 `lib/math/div64.c` 在 32 位元平台上處理 64÷32 除法。閱讀 `div_u64_rem()` 的實作：在 64 位元平台上直接以原生除法完成，但在 32 位元平台上退化至 `__div64_32()` 的軟體模擬路徑。追蹤 `__div64_32()` 的演算法，它將 64 位元被除數拆為高 32 位元與低 32 位元，以兩次 32 位元除法完成計算。分析此拆解的數學基礎：設 $N = N_H \cdot 2^{32} + N_L$，$D$ 為 32 位元除數，則 $\lfloor N / D \rfloor = \lfloor N_H / D \rfloor \cdot 2^{32} + \lfloor ((N_H \bmod D) \cdot 2^{32} + N_L) / D \rfloor$。證明此恆等式成立，並說明為何第二次除法的被除數 $(N_H \bmod D) \cdot 2^{32} + N_L$ 保證不超過 $D \cdot 2^{32} - 1$，使得商能以 32 位元表示。進一步探討以 Newton-Raphson reciprocal approximation 加速除法的可能性：推導 Newton-Raphson 迭代 $x_{n+1} = x_n (2 - D \cdot x_n)$ 如何以乘法逼近 $1/D$，每次迭代將精度位元數翻倍
## 細讀〈[並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency-sched)〉
### Q1
- [ ] 從 coroutine 出發逐步建構排程器的設計原理：以 `setjmp`/`longjmp` 與 `ucontext` 實作使用者空間 context switch。作業一分析 fork-join 模型的 DAG 表示與 Amdahl's law 的關係，以及 `int *foo(void) { int x = 10; return &x; }` 的未定義行為與 storage duration。以此為出發點：
* (a) C99 §7.13.2.1 規定 `longjmp` 後，自動儲存期 (auto storage duration) 且未宣告為 `volatile` 的區域變數，若在 `setjmp` 與 `longjmp` 之間被修改，其值 indeterminate。撰寫測試程式在 `-O0` 與 `-O2` 下驗證此行為差異 (提示: 編譯器可能將區域變數快取於暫存器，`longjmp` 恢復暫存器後其值回到 `setjmp` 時的狀態)。解釋 Linux 核心為何以 `switch_to()` 巨集 (定義於 `arch/x86/include/asm/switch_to.h`) 而非 `setjmp`/`longjmp` 實作 context switch，因為核心需要精確控制 FPU 狀態、TLS (`fs` 段暫存器)、per-CPU 變數、以及 stack canary 的切換，`setjmp` 僅儲存 callee-saved registers，無法涵蓋這些需求
* (b) 閱讀 `arch/x86/include/asm/switch_to.h` 的 `__switch_to_asm` 與 [`arch/x86/kernel/process_64.c`](https://github.com/torvalds/linux/blob/master/arch/x86/kernel/process_64.c) 的 `__switch_to()`，列出 context switch 過程中依序切換的所有 CPU 狀態 (sp、ip、FPU、segment registers、per-CPU 基底位址、debug registers)，並估算每項切換操作的 cycles 成本
#### 1.
根據 C99 7.13.2.1
>All accessible objects have values, and all other components of the abstract machine have state, as of the time the longjmp function was called, except that the values of objects of automatic storage duration that are local to the function containing the invocation of the corresponding setjmp macro that do not have volatile-qualified type and have been changed between the setjmp invocation and longjmp call are indeterminate.
可知在 setjmp 與 longjmp 之間被修改的非 volatile 區域變數，其值會是 indeterminate (未定)。我們可以用以下程式碼來觀察這個現象：
```c
#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>
jmp_buf env;
int main(void) {
int normal_var = 10;
volatile int volatile_var = 10;
if (setjmp(env) == 0) {
/* 第一次執行 setjmp，回傳 0 */
printf("[Before setjmp] normal_var = %d, volatile_var = %d\n", normal_var, volatile_var);
// 在 setjmp 與 longjmp 之間修改變數
normal_var = 20;
volatile_var = 20;
printf("[Before longjmp] normal_var = %d, volatile_var = %d\n", normal_var, volatile_var);
// 跳轉回去
longjmp(env, 1);
} else {
/* 從 longjmp 跳回來，回傳非 0 值 */
printf("[After longjmp] normal_var = %d, volatile_var = %d\n", normal_var, volatile_var);
}
return 0;
}
```
分別使用 -O0 跟 -O2 觀察輸出：
```c
PS C:\Users\User\Desktop\Linux> gcc -O0 test.c -o test
PS C:\Users\User\Desktop\Linux> ./test.exe
[Before setjmp] normal_var = 10, volatile_var = 10
[Before longjmp] normal_var = 20, volatile_var = 20
[After longjmp] normal_var = 20, volatile_var = 20
PS C:\Users\User\Desktop\Linux> gcc -O2 test.c -o test
PS C:\Users\User\Desktop\Linux> ./test.exe
[Before setjmp] normal_var = 10, volatile_var = 10
[Before longjmp] normal_var = 20, volatile_var = 20
[After longjmp] normal_var = 10, volatile_var = 20
```
根據輸出，我們可以知道主要得差距在於 longjmp 後， normal_var 在 -O0 下是 10 且在 -O2 下是 20。兩者輸出不一致，分析如下：
* 在 -O0 下，編譯器不會把 normal_var 放在暫存器中，而是乖乖地放在 Stack 記憶體裡。longjmp 只會恢復暫存器的狀態，不會去動 Stack 上的資料。因此修改後的 20 依然保留在記憶體中。
* 在 -O2 下，編譯器發現 normal_var 經常被使用，為了加速，將其配置到 Callee-saved register (ex. rbx) 中。
* setjmp 執行時，把當時 %rbx 的值 (10) 存進 jmp_buf。
* 程式將暫存器 %rbx 改為 20。
* longjmp 執行時，從 jmp_buf 把舊的值 (10) 蓋回 %rbx。
* 結果 normal_var 就變回 10 了。而 volatile_var 因為被強制寫入記憶體，所以不受 longjmp 恢復暫存器的影響。
因為 setjmp 通常只會幫我們存取 callee-saved integer，並且也不保證底下：
* TLS (Thread Local Storage)、Stack canary：如果不切換 fs，兩個執行緒會共用同一個 errno 變數或相同的 Stack Canary，這會造成災難性的安全漏洞。
* FPU / SSE / AVX 狀態：這些暫存器較大，存一次要花很多時間，如果切換的任務都在執行例如浮點數的運算，那核心在切換「任務」時必須確保每個 thread 的數學計算將會互相干擾。
因此 Linux 核心才以 switch_to() 巨集去實作 Context switching。
#### 2.
Linux 核心在 x86_64 架構下的 Context Switch 主要被拆分為兩個階段：
1. [`__switch_to_asm`](https://github.com/torvalds/linux/blob/master/arch/x86/entry/entry_64.S) (組合語言)：負責最底層的 Stack pointer (%rsp) 與 Callee-saved 暫存器切換。
2. [`__switch_to()`](https://https://github.com/torvalds/linux/blob/master/arch/x86/kernel/process_64.c) (C 語言)：負責處理 FPU、TLS、Per-CPU 等複雜的硬體與系統狀態
**Step 1：存取 Callee-saved Registers**
在 [`__switch_to_asm`](https://github.com/torvalds/linux/blob/master/arch/x86/entry/entry_64.S)，會先幫我們存取的暫存器有：
* sp (Stack Pointer)：替換 %rsp 暫存器。
* ip (Instruction Pointer)：透過跳轉指令隱式切換 %rip。
* Callee-saved 暫存器：%rbp, %rbx, %r12 ~ %r15。
```asm
SYM_FUNC_START(__switch_to_asm)
ANNOTATE_NOENDBR
/*
* Save callee-saved registers
* This must match the order in inactive_task_frame
*/
pushq %rbp
pushq %rbx
pushq %r12
pushq %r13
pushq %r14
pushq %r15
/* switch stack */
movq %rsp, TASK_threadsp(%rdi)
movq TASK_threadsp(%rsi), %rsp
#ifdef CONFIG_STACKPROTECTOR
movq TASK_stack_canary(%rsi), %rbx
movq %rbx, PER_CPU_VAR(__stack_chk_guard)
#endif
/*
* When switching from a shallower to a deeper call stack
* the RSB may either underflow or use entries populated
* with userspace addresses. On CPUs where those concerns
* exist, overwrite the RSB with entries which capture
* speculative execution to prevent attack.
*/
FILL_RETURN_BUFFER %r12, RSB_CLEAR_LOOPS, X86_FEATURE_RSB_CTXSW
/* restore callee-saved registers */
popq %r15
popq %r14
popq %r13
popq %r12
popq %rbx
popq %rbp
jmp __switch_to
SYM_FUNC_END(__switch_to_asm)
```
Cycle Count 約為：約 10 ~ 20 Cycles
**Step 2-1：存取 FPU (浮點運算單元)、TLS (Thread Local Storage) 與 Per-CPU 變數**
```c
__switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
struct thread_struct *prev = &prev_p->thread;
struct thread_struct *next = &next_p->thread;
int cpu = smp_processor_id();
WARN_ON_ONCE(IS_ENABLED(CONFIG_DEBUG_ENTRY) &&
this_cpu_read(hardirq_stack_inuse));
switch_fpu(prev_p, cpu);
/* We must save %fs and %gs before load_TLS() because
* %fs and %gs may be cleared by load_TLS().
*
* (e.g. xen_load_tls())
*/
save_fsgs(prev_p);
/*
* Load TLS before restoring any segments so that segment loads
* reference the correct GDT entries.
*/
load_TLS(next, cpu);
...
}
```
Cycle Count 約為：約 60 ~ 450 Cycles
**Step 2-2：Per-CPU 變數與 Stack Canary**
```c
raw_cpu_write(current_task, next_p);
raw_cpu_write(cpu_current_top_of_stack, task_top_of_stack(next_p));
```
Cycle Count 約為：約 < 5 Cycles
### Q2
- [ ] [Google 的 ghOSt 框架](https://research.google/pubs/ghost-fast-and-flexible-user-space-delegation-of-linux-scheduling/)將 CPU 排程決策從核心模式移至使用者空間。作業一提到若將 VFS 或 network stack 遷移至 userspace 時的 context switch 數量變化、cache locality、fault isolation 與 worst-case latency。將此分析框架套用至 ghOSt：
* (a) ghOSt 的使用者空間 CPU 排程器透過 eBPF hook 與共享記憶體佇列 (status word) 與核心互動，每次排程決策需要至少一次核心→使用者空間→核心的往返。以作業一的延遲模型為基礎，推導 ghOSt 的排程延遲下界 $T_{ghost} \geq T_{ctx} \cdot 2 + T_{decision}$，其中 $T_{ctx}$ 為單次 context switch 成本、$T_{decision}$ 為使用者空間排程策略的計算時間，並分析在 $T_{decision}$ 極小時，此額外延遲是否仍可容忍
* (b) 作業二分析 PELT 使用 EWMA 並以 `mul_u64_u32_shr()` 完成定點數乘法。從 Linux v0.01 的 150ms timeslice round-robin 到 CFS 的 `vruntime` 再到 EEVDF 的 eligible/deadline 計算，追蹤排程器精度需求的演進。閱讀 [`kernel/sched/fair.c`](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c) 中 EEVDF 的 `pick_eevdf()` 與 `entity_eligible()`，以作業一探討的 lag 有界性證明 ($\sum_i \text{Lag}_i(t) = 0$) 為基礎，說明 EEVDF 如何以 deadline 排序取代 CFS 的純 `vruntime` 排序來改善 tail latency
### Q3
- [ ] CFS 的 `vruntime` 以 `u64` 奈秒計數器記錄每個排程實體的虛擬執行時間。分析 `vruntime` wraparound 問題：$2^{64}$ 奈秒約為 $2^{64} / (10^9 \times 3600 \times 24 \times 365.25) \approx 584.5$ 年，實務上不會溢位，但排程器內部仍以帶號差值比較 `vruntime`。閱讀 [`kernel/sched/fair.c`](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c) 的 `min_vruntime()` 與 `max_vruntime()`，說明其如何以 `(s64)(vruntime - min_vruntime) < 0` 的帶號比較處理潛在的 wraparound。注意當前 mainline 的 `entity_before()` 已改為比較 EEVDF 的 `deadline` 而非 `vruntime`，但 `vruntime` 的帶號差值比較仍存在於 `min_vruntime()` 等輔助函式中。此技巧的數學基礎在於二補數減法的 modular arithmetic 性質：只要任意二個 `vruntime` 的差距不超過 $2^{63}$，帶號比較即能正確判定大小關係。證明此不變量在正常排程運作下成立 (提示：`min_vruntime` 持續推進，所有就緒態行程的 `vruntime` 與 `min_vruntime` 的差距受權重比與排程週期約束，遠小於 $2^{63}$)。進一步追蹤 `entity_before()` 在 EEVDF 中如何以相同的帶號比較技巧作用於 `deadline` 欄位，並分析 `avg_vruntime()` → `update_entity_lag()` → `entity_eligible()` → `pick_eevdf()` 的完整呼叫鏈
Linux Kernel 中的 wraparound 機制，`(s64)(vruntime - min_vruntime) < 0` 使「在發生溢位的情況下，依然能正確比較大小」，證明如下：
在軟體內部 vruntime - min_vruntime，其實是 vruntime - min_vruntime(mod $2^{64}-1$)，底下分成兩個情況討論：
* 情況一（無溢位，$v > m$）：$v - m$ 是一個正數，其二進位最高位元（Sign Bit）為 0。轉型為 s64 後仍為正數，因此 (s64)(v - m) < 0 為 False，正確表示 $v$ 不在 $m$ 之前（$v \ge m$）。
* 情況二（發生溢位，$v$ 繞回起點）：例如 $v=2$, $m=2^{64}-2$。此時 $v - m = 2 - (2^{64}-2) = 4 - 2^{64}$。在 u64 的模運算下，$4 - 2^{64} \equiv 4 \pmod{2^{64}}$。結果 4 是一個正數（最高位元為 0）。強制轉型為 s64 後為 4。此時 (s64)(v - m) < 0 仍為 False，正確判定了數值為 $2$ 的 $v$ 其實是在 $m$ 之後出現的。
此證明看似正確，但成立的數學前提是：兩個數值的「真實距離」不能超過數線總長度的一半（即 $2^{63}$），然而 Linux Kernel 中保持了此前提的成立：
* 當一個睡眠很久的任務醒來時，核心會檢查它的 vruntime。如果落後 min_vruntime 太多，核心會強行將它提升到 min_vruntime 附近（通常扣除一個 sysctl_sched_latency 的差額）。這確保了落後者的距離不會拉得太遠。
* 一個任務如果一直佔用 CPU，它的 vruntime 會不斷增加。當它增加到不再是佇列中「最小」的時候，排程器就會觸發搶佔（Preemption）換人跑，從而讓 min_vruntime 繼續推進，追上領先者。
==EEVDF 未看==
## 細讀〈[C 語言: 函式呼叫](https://hackmd.io/@sysprog/c-function)〉
### Q1
- [ ] System V AMD64 ABI 的 calling convention 與 stack frame 配置。作業一分析 `int *foo(void) { int x = 10; return &x; }` 的未定義行為、`void f(int a[10])` 與 `void f(int *a)` 的 ABI 差異，以及 call-by-value 的機制。以此為出發點：
* (a) 函式 prologue (`push rbp; mov rbp, rsp; sub rsp, N`) 建立 stack frame。在 Linux 核心中，`CONFIG_FRAME_POINTER` 啟用時 GCC 以 `-fno-omit-frame-pointer` 保留 frame pointer chain，但此選項增加暫存器壓力 (x86-64 損失 `rbp`)。核心自 v4.14 引入 ORC unwinder (`CONFIG_UNWINDER_ORC`)，以編譯期產生的 `.orc_unwind` section 取代執行期 frame pointer chain。閱讀 [`scripts/orc/`](https://github.com/torvalds/linux/tree/master/scripts) 的 ORC 產生工具與 [`arch/x86/kernel/unwind_orc.c`](https://github.com/torvalds/linux/blob/master/arch/x86/kernel/unwind_orc.c) 的 unwinder 實作，說明 ORC 如何以查表 (每個指令位址對應一組 sp/fp 偏移) 取代 frame pointer traversal，並從 git log 找出 ORC 引入的 commit 以了解其在核心 profiling (`perf record`) 中的精確度改善
* (b) Linux 核心的系統呼叫以 `struct pt_regs` 傳遞暫存器狀態。閱讀 [`arch/x86/entry/entry_64.S`](https://github.com/torvalds/linux/blob/master/arch/x86/entry/entry_64.S) 的 `entry_SYSCALL_64`，追蹤使用者空間的 `rdi`, `rsi`, `rdx`, `r10`, `r8`, `r9` 如何被儲存至 `pt_regs` 結構體，以及 `SYSCALL_DEFINE` 巨集 (定義於 [`include/linux/syscalls.h`](https://github.com/torvalds/linux/blob/master/include/linux/syscalls.h)) 如何展開為系統呼叫的進入點，以及 x86 架構特有的 `pt_regs` wrapper (定義於 `arch/x86/include/asm/syscall_wrapper.h`) 如何從 `struct pt_regs` 擷取參數並轉交給泛型的系統呼叫函式。注意 x86-64 的 syscall ABI 使用 `r10` 而非 `rcx` 作為第四個參數 (因為 `syscall` 指令以 `rcx` 儲存返回位址)，此差異如何反映在 `pt_regs` 的欄位順序中
### Q2
- [ ] `setjmp`/`longjmp` 可跨越多個函式邊界執行非區域跳躍。作業一分析 strict aliasing rule 與 type punning 的安全性。在 Linux 核心中，`setjmp` 的角色被 `switch_to()` + `schedule()` 取代，但核心的 kprobes 機制 ([`kernel/kprobes.c`](https://github.com/torvalds/linux/blob/master/kernel/kprobes.c)) 以 `setjmp`-like 的方式儲存暫存器狀態以實現動態追蹤。閱讀 `arch/x86/kernel/kprobes/core.c` 的 `kprobe_int3_handler()`，說明其如何儲存 `pt_regs` 並在探測點觸發 callback 後恢復原始執行流程。對比 `setjmp`/`longjmp` 僅儲存 callee-saved registers，kprobes 需要完整的 `pt_regs` 快照。從 `perf probe` 的角度，設計實驗以 kprobes 追蹤 `vfs_read()` 的呼叫次數與參數值
## 細讀〈[C 語言: 前置處理器應用](https://hackmd.io/@sysprog/c-preprocessor)〉
### Q1
- [ ] C 前置處理器的 stringification、token pasting、`_Generic`，以及 Linux 核心中巨集的大量應用。作業二分析 `BIT(N)`/`GENMASK(h, l)` 如何避免有號位移的未定義行為、`BUILD_BUG_ON_ZERO` 的位元欄位技巧，以及 `container_of` 的 object model 假設。以此為出發點：
* (a) `__stringify(x)` 巨集需要兩層展開 (`#define __stringify_1(x...) #x` + `#define __stringify(x...) __stringify_1(x)`)，原因在於 C 語言規格要求 `#` 運算子在參數替換之前執行 stringification，因此若只有一層，巨集參數不會被展開。撰寫測試程式驗證此行為 (`#define FOO 42` 後 `__stringify(FOO)` 應產生 `"42"` 而非 `"FOO"`)，並從 C99 §6.10.3.2 引述規範性文字
* (b) 閱讀 Linux 核心 v6.x 中重新設計的 [`include/linux/minmax.h`](https://github.com/torvalds/linux/blob/master/include/linux/minmax.h)，追蹤 `__types_ok()` 如何以 `__builtin_choose_expr` 與 `__is_constexpr()` 在編譯期偵測 signed/unsigned 混合比較，此設計直接呼應作業二分析的 signed/unsigned 隱式轉型陷阱 (CWE-195)。從 git log 找出此巨集重新設計的 commit (提示: 2024 年 Linus Torvalds 親自重寫 `min()`/`max()`)，分析舊版 `min_t()` 強制轉型可能吞噬的 warning
#### 1.
根據 C99 6.10.3.1
> After the arguments for the invocation of a function-like macro have been identified, argument substitution takes place. A parameter in the replacement list, unless preceded by a # or ## preprocessing token or followed by a ## preprocessing token, is replaced by the corresponding argument after all macros contained therein have been expanded.
又根據 C99 6.10.3.2
>If, in the replacement list, a parameter is immediately preceded by a # preprocessing token, both are replaced by a single character string literal preprocessing token that contains the spelling of the preprocessing token sequence for the corresponding argument.
當前置處理器掃描巨集替換列表時，如果遇到 #（Stringification）或 ##（Token Pasting）運算子，它會立即對傳入的參數執行字串化或拼接，而不會先去展開該參數本身的巨集定義。
觀察下列程式碼：
```c
#include <stdio.h>
#define FOO 42
/* 單層：直接字串化 */
#define __stringify_1(x) #x
/* 雙層：先展開參數，再字串化 */
#define __stringify(x) __stringify_1(x)
int main(void) {
printf("單層展開: %s\n", __stringify_1(FOO));
printf("雙層展開: %s\n", __stringify(FOO));
return 0;
}
```
其輸出結果為：
```c
單層展開: FOO
雙層展開: 42
```
搭配上述的 C99 規範，可以推論
1. `__stringify_1(FOO)` 時，當參數 x 在替換清單中緊跟在 # 運算子之後時，前置處理器會跳過對該引數（FOO）的巨集展開（Expansion），並將其轉換為字串字面量 "FOO"。
2. `__stringify` 時，分成兩個階段：
* 第一階段：FOO 被展開為其定義的值 42。
* 第二階段：展開後的結果 42 才被傳遞進 `__stringify_1`，其後產生字串 "42"。
#### 2.
根據 [Git commit 867046cc7027](https://github.com/torvalds/linux/commit/867046cc7027703f60a46339ffde91a1970f2901)
```diff
- #define __types_ok(x, y) \
- (__is_signed(x) == __is_signed(y) || \
- __is_signed((x) + 0) == __is_signed((y) + 0))
+ /* True for a non-negative signed int constant */
+ #define __is_noneg_int(x) \
+ (__builtin_choose_expr(__is_constexpr(x) && __is_signed(x), x, -1) >= 0)
+ #define __types_ok(x, y) \
+ (__is_signed(x) == __is_signed(y) || \
+ __is_signed((x) + 0) == __is_signed((y) + 0) || \
+ __is_noneg_int(x) || __is_noneg_int(y))
```
在舊版 min() macro 中會嚴格要求兩參數型別一致，否則編譯器舊版 `__types_ok` 會噴出 warning。為了消除 warning，開發者常常濫用 min_t(type, a, b) 來強制轉型，但這樣的結果總會造成錯誤，例如：`unsigned int copy_len = min_t(unsigned int, size, 256);` 會造成當 size 是負數時，會 wrap around 成一個超大的正數，導致 copy_len 為 256，此舉引發嚴重的安全性漏洞（CWE-195）。
然而在修改後，讓 min() 可以接受無號數與非負常數的比較是絕對安全的，導致可以濾到剩下一個 warning 條件是必為「其中一個變數型態保證為非負的常數」。
* 其中 `__is_noneg_int(x)` 的主要原理為：
* `__is_constexpr(x)` 用來判斷 x 是否為一個 「編譯器已知的常數表達式」。
* `__builtin_choose_expr(condition, x, y)`是 GCC 的內建函數，類似於編譯時期的 if-else。若條件為真，則選擇 x；若條件為真，則選擇 y。
* 在把 x 分成 3 種數值進行討論：
* 情境一：傳入正整數常數 `__is_noneg_int(40)`，最終判斷 40 >= 0，結果為 True。
* `__is_constexpr(40)` 是 真，且 `__is_signed(40)` 是 Ture。
* `__builtin_choose_expr` 選擇了第一個路徑，結果變成了 42。
* 結論： 40 是個「保證非負的有號整數常數」。
* 情境二：傳入負整數常數 `__is_noneg_int(-10)`，最終判斷 -10 >= 0，結果為 False。
* `__is_constexpr(-10)` 是 真，且 `__is_signed(-10)` 是 Ture。
* `__builtin_choose_expr` 選擇了第一個路徑，結果變成了 -10。
* 結論： -10 雖然是常數，但它是負數，不安全。
* 情境三：傳入一個變數 `__is_noneg_int(my_len)`，最終判斷 -1 >= 0，結果為 False。
* `__is_constexpr(my_len)` 是 False 因為變數在編譯時數值不確定。
* `__builtin_choose_expr` 選擇了第二個路徑，結果變成了 -1。
* 結論： 變數是不安全的，因為編譯器無法保證它執行時會不會是負數。
### Q2
- [ ] 以巨集實現物件導向設計模式。作業一探討 Linux 核心的 VFS 與 network stack 如何以抽象層支撐演化。從 VFS 層出發：`struct file_operations` 以函式指標模擬 vtable，各檔案系統以 designated initializer (`.read = ext4_file_read_iter`) 填入實作。閱讀 [`fs/ext4/file.c`](https://github.com/torvalds/linux/blob/master/fs/ext4/file.c) 的 `ext4_file_operations` 定義，追蹤 `vfs_read()` 如何透過 `f->f_op->read_iter` 間接呼叫。此模式等效於 C++ 的虛擬函式分派 (virtual dispatch)，但以 C 語言的前置處理器與結構體手動實現。設計實驗：撰寫核心模組 (或使用者空間模擬)，以函式指標表實現兩種不同的「檔案系統」讀取行為，以 `perf stat -e branch-misses` 量測間接呼叫 (`f->f_op->read`) 的 branch prediction 命中率與直接呼叫的差異
## 細讀〈[C 語言: goto 和流程控制](https://hackmd.io/@sysprog/c-control-flow)〉
### Q1
- [ ] `goto` 在 Linux 核心中的合理使用，主要用於集中式錯誤處理與資源釋放。作業一分析 `free(ptr)` 後指標值變為 indeterminate 的 UB，以及物件生命週期結束後解參考指標的未定義行為。以此為出發點：
* (a) Linux 核心的驅動程式典型 `goto` 模式：`goto err_free_irq; ... err_free_irq: free_irq(irq, dev); err_free_mem: kfree(dev);` 以反向順序釋放資源。此模式的正確性依賴標籤的嚴格反向排列，若開發者在 `err_free_irq` 後意外跳至 `err_free_mem` 之前的位置 (遺漏一層釋放)，會造成記憶體洩漏。從 git log 搜尋 `goto` 相關的 resource leak 修正 (提示: `drivers/` 下以 "fix leak" 與 "goto" 為關鍵字)，找出至少二個實際案例，分析錯誤模式並說明 Coccinelle semantic patch (`scripts/coccinelle/free/`) 如何自動偵測此類缺陷
* (b) Linux 核心自 v6.x 引入的 `guard()` 巨集 (定義於 [`include/linux/cleanup.h`](https://github.com/torvalds/linux/blob/master/include/linux/cleanup.h)) 以 `__attribute__((cleanup))` 實現 scope-based 鎖釋放，可取代 `goto err_unlock` 模式。閱讀 `cleanup.h` 的 `DEFINE_GUARD()` 展開式，說明其如何在變數離開作用域時自動呼叫 `mutex_unlock()`，以及此設計在 C 語言 (而非 C++) 中的侷限，因為 C 沒有析構子語意，`__attribute__((cleanup))` 是 GCC extension
#### 1.
根據 [Commit -24defbe194b6](https://github.com/torvalds/linux/commit/24defbe194b650218680fcd9dec8cd103537b531)
```c
if (clk_data->freq > MAX_FREQ) {
pr_err("Frequency too high\n");
return -EINVAL;
}
```
在之前版本，流程中插入了一段硬體狀態檢查或參數校驗，一旦發現錯誤，就直接寫下 `return -EINVAL;` 或 `return -ENODEV;`，但忽略了程式執行到這一步時，前面已經成功分配了記憶體(或註冊了中斷、取得了鎖等等)。直接 return 會讓這些資源永遠無法被釋放，直到系統重啟。
因此修改後必須強制遵守統一的錯誤出口。將 return -EINVAL; 改為賦值給 ret 並透過 goto 離開。
```c
if (clk_data->freq > MAX_FREQ) {
pr_err("Frequency too high\n");
ret = -EINVAL;
goto err_free_mem;
}
```
另一個例子，根據 [Commit -00ffb3724ce7](https://github.com/torvalds/linux/commit/00ffb3724ce743578163f5ade2884374554ca021)
```diff
if (!eth_filter->port[i].bmap) {
ret = -ENOMEM;
+ kvfree(eth_filter->port[i].loc_array);
goto free_eth_finfo;
}
free_eth_finfo:
while (i-- > 0) {
bitmap_free(eth_filter->port[i].bmap);
kvfree(eth_filter->port[i].loc_array);
}
kfree(eth_filter_info);
free_eth_filter:
kfree(eth_filter);
return ret;
```
在之前版本(沒有 `kvfree(eth_filter->port[i].loc_array);`)，如果直接 goto err_free_array，底下的清理迴圈只會清理由 0 到 i-1 的 filter。局部的 'f' 就會因為沒有被記錄在陣列中，也沒有被顯式釋放，造成了 memory leak。因此修改後，必須在跳轉前，先將當前的資源 f 釋放掉。
根據 [Coccinelle semantic patch](https://github.com/torvalds/linux/blob/master/scripts/coccinelle/free/devm_free.cocci)
```c
@safe depends on context || org || report exists@
expression x;
position p;
@@
(
* kfree@p(x)
|
* free_irq@p(x)
|
...
)
...
(
kfree@p(x)
|
kfree_sensitive@p(x)
|
...
)
```
當中，會去定義並記錄安全的釋放路徑。
1. 先尋找變數 x 被賦值的地點，(如 x = kmalloc() 等)。
2. 沿著程式碼的執行路徑往下走（...）。
3. 如果在這條路徑上，遇到了對這個 x 進行釋放的函式（如 kfree(x) 等），代表這是一條合法且成對的分配與釋放路徑。)。
之後再找出程式碼中所有的釋放動作，如果它「不在」剛剛收集的安全名單內，就報警告。
```c
@pb@
expression r.x;
position p != safe.p;
@@
(
* kfree@p(x)
|
* free_irq@p(x)
|
...
```
#### 2.
==TODO==
### Q2
- [ ] computed goto (GCC `&&label` 擴充) 與 Duff's device。作業二分析 SWAR 技巧中的 loop unrolling 與 branchless 設計。以此為出發點：
* (a) Linux 核心的 BPF 直譯器 ([`kernel/bpf/core.c`](https://github.com/torvalds/linux/blob/master/kernel/bpf/core.c)) 使用 computed goto 實作 dispatch table，每個 BPF opcode 對應一個 `&&label`，直譯器以 `goto *jumptable[opcode]` 分派。相較於 `switch-case`，computed goto 避免集中式跳轉表查詢，每個 opcode handler 的結尾直接 `goto *jumptable[next_op]`，使分支預測器對每個 handler→handler 的轉移建立獨立的預測紀錄。閱讀 `___bpf_prog_run()` 的 dispatch 邏輯 (搜尋 `CONT` 或 `goto select_insn` 等控制流巨集)，說明其展開後的控制流程。設計實驗：撰寫使用者空間的簡易 bytecode 直譯器，分別以 `switch-case` 與 computed goto 實作 dispatch，以 `perf stat -e branch-misses` 量測 1M 次 dispatch 的 branch miss rate 差異
* (b) Simon Tatham 的 `switch-case` coroutine 技巧，本質上是 stackless coroutine 的手動實作。C 語言規格允許 `case` 標籤出現在 `switch` 內任何子語句中 (包含 `while` 或 `for` 迴圈內)。從 Linux 核心找出使用此技巧或類似手法的非同步 I/O 路徑 (提示: `fs/cifs/connect.c` 的 `cifs_demultiplex_thread` 或 `drivers/` 下的 state machine)，分析其如何跨越函式呼叫保存狀態
#### 1.
根據 [`kernel/bpf/core.c`](https://github.com/torvalds/linux/blob/master/kernel/bpf/core.c)
```c
#define BPF_INSN_3_LBL(x, y, z) [BPF_##x | BPF_##y | BPF_##z] = &&x##_##y##_##z
static const void * const jumptable[256] __annotate_jump_table = {
[0 ... 255] = &&default_label,
BPF_INSN_MAP(BPF_INSN_2_LBL, BPF_INSN_3_LBL),
[BPF_JMP | BPF_CALL_ARGS] = &&JMP_CALL_ARGS,
[BPF_JMP | BPF_TAIL_CALL] = &&JMP_TAIL_CALL,
...};
#define CONT ({ insn++; goto select_insn; })
#define CONT_JMP ({ insn++; goto select_insn; })
select_insn:
goto *jumptable[insn->code];
/* ALU (shifts) */
#define SHT(OPCODE, OP) \
ALU64_##OPCODE##_X: \
DST = DST OP (SRC & 63); \
CONT; \
ALU_##OPCODE##_X: \
DST = (u32) DST OP ((u32) SRC & 31); \
CONT; \
ALU64_##OPCODE##_K: \
DST = DST OP IMM; \
CONT; \
ALU_##OPCODE##_K: \
DST = (u32) DST OP (u32) IMM; \
CONT;
/* ALU (rest) */
...
```
可觀察到 CONT 巨集展開後的控制流是：`insn++` → `goto select_insn` → `goto *jumptable[insn->code]`。
設計以下實驗：
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define OP_INC 0
#define OP_DEC 1
#define OP_LOOP 2
#define OP_HALT 3
void generate_random_bytecode(int *code, int len, int iterations) {
srand(time(NULL));
for (int i = 0; i < len - 3; i++) {
code[i] = rand() % 2;
}
code[len - 3] = OP_LOOP;
code[len - 2] = iterations;
code[len - 1] = OP_HALT;
}
#ifdef USE_COMPUTED_GOTO
void run_vm(int *code, int len) {
static const void *dispatch_table[] = { &&do_inc, &&do_dec, &&do_loop, &&do_halt };
int pc = 0;
long acc = 0;
goto *dispatch_table[code[pc]];
do_inc:
acc++; pc++;
goto *dispatch_table[code[pc]];
do_dec:
acc--; pc++;
goto *dispatch_table[code[pc]];
do_loop:
if (acc < code[pc + 1]) {
pc = 0;
} else {
pc += 2;
}
goto *dispatch_table[code[pc]];
do_halt:
printf("VM Done (Computed Goto). Acc: %ld\n", acc);
return;
}
#else
void run_vm(int *code, int len) {
int pc = 0;
long acc = 0;
while (1) {
switch (code[pc]) {
case OP_INC: acc++; pc++; break;
case OP_DEC: acc--; pc++; break;
case OP_LOOP:
if (acc < code[pc + 1]) pc = 0;
else pc += 2;
break;
case OP_HALT:
printf("VM Done (Switch-Case). Acc: %ld\n", acc);
return;
}
}
}
#endif
int main() {
int len = 1000; /
int *code = malloc(sizeof(int) * len);
generate_random_bytecode(code, len, 1000000);
run_vm(code, len);
free(code);
return 0;
}
```
並編譯：
```c
gcc -O2 test.c -o switch
gcc -O2 -DUSE_COMPUTED_GOTO test.c -o goto
perf stat -e branches,branch-misses ./switch
perf stat -e branches,branch-misses ./goto
```
得到結果為：
```c
Performance counter stats for './switch':
168,191,146,366 branches
516,410 branch-misses # 0.00% of all branches
13.493962217 seconds time elapsed
13.487750000 seconds user
0.000000000 seconds sys
```
和
```c
Performance counter stats for './goto':
2,960,702,785 branches
7,436,004 branch-misses # 0.25% of all branches
1.646419366 seconds time elapsed
1.645064000 seconds user
0.001000000 seconds sys
```
雖然數據顯示 computed goto 的預測錯誤率（0.25%）高於 switch-case（0.00%）。但 switch-case 版本產生了破千億次的分支指令，這是因為每次 Dispatch 都必須經歷 break、檢查 while 迴圈條件、重新進入 switch 並查表。相對地，computed goto 版本實現了 Branchless。所以即便執行時間較短，其單位時間內執行的有效 Opcode 數量遠高於前者。
#### 2.
根據 [`drivers/bluetooth/hci_h5.c`](https://github.com/torvalds/linux/blob/master/drivers/bluetooth/hci_h5.c)
```c
enum {
H5_WAKEUP,
H5_SYNC_INIT,
H5_SYNC_RESP,
H5_INITIALIZED,
H5_ACTIVE,
};
/* 非同步接收回呼函式 */
static int h5_rx_3wire(struct hci_uart *hu, unsigned char c)
{
struct h5 *h5 = hu->priv;
/* 每次進入函式，透過 switch 判斷上次停在哪個階段 */
switch (h5->rx_state) {
case H5_WAKEUP:
if (c == 0xc0) {
h5->rx_state = H5_SYNC_INIT;
}
break;
case H5_RX_ESC:
/* 處理邏輯... */
h5->rx_state = H5_RX_PAYLOAD;
break;
case H5_RX_PAYLOAD:
/* 處理邏輯... */
h5->rx_skb->data[h5->rx_skb->len++] = c;
if (h5->rx_skb->len == h5->rx_pending) {
h5->rx_state = H5_RX_CRC;
}
break;
case H5_RX_CRC:
/* 處理邏輯... */
h5_rx_pkt_csum(hu);
h5->rx_state = H5_WAKEUP;
break;
default:
/* 處理邏輯... */
break;
}
return 0; // Non-Blocking
}
```
對照程式碼旁邊的註解，可以觀察到其核心精神在於利用 switch case 的標籤能跳到程式的任何地方，這使得單一函式可以在 Non-blocking 的情況下 return 交出 CPU 控制權，並在下次被呼叫時，透過 switch (state) 直接「跳躍」回上次中斷的邏輯中，達到 stackless co-routinue 的功能。
## 細讀〈[C 語言程式設計技巧](https://hackmd.io/@sysprog/c-trick)〉
### Q1
- [ ] 以 C 語言實現 OOP、`__attribute__((cleanup))` 的 RAII 模式、designated initializer，以及 `container_of`，這些技巧在 Linux 核心中隨處可見。作業二分析 `container_of` 的 object model 依賴，以及 `typeof`、`offsetof` 在核心中的角色。以此為出發點：
* (a) Linux 核心的裝置模型以「繼承式結構體」搭配 `container_of` 實現多型，例如 `struct pci_dev` 内嵌 `struct device`，`struct device` 内嵌 `struct kobject`。閱讀 [`drivers/base/core.c`](https://github.com/torvalds/linux/blob/master/drivers/base/core.c) 的 `device_release()`，追蹤 `kobject_put()` 如何透過 `kobj->ktype->release` 間接呼叫上層結構體的釋放函式，此呼叫路徑需要從 `kobject *` 反向取得 `struct device *` (經由 `container_of`)，再從 `struct device *` 取得 `struct pci_dev *`。繪製記憶體布局圖說明 `container_of` 的指標算術，並與 C++ 的多重繼承 vptr 機制在指標調整上進行對比
* (b) `__attribute__((cleanup))` 實現 RAII。閱讀 [`include/linux/cleanup.h`](https://github.com/torvalds/linux/blob/master/include/linux/cleanup.h) 的 `__free()` 巨集以及 `guard(mutex)` 的展開式，設計實驗：在核心模組中分別以傳統 `goto err_unlock` 與 `guard(mutex)` 實現臨界區保護，比較二者的組合語言輸出，觀察 `guard()` 是否引入額外的 function call overhead (cleanup handler)？在 hot path 上此開銷是否可量測？
#### 1.
根據 [`drivers/base/core.c`](https://github.com/torvalds/linux/blob/master/drivers/base/core.c)
```c
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type, member) );})
```
結構宣告如下：
```c
struct kobject;
struct kobj_type {
void (*release)(struct kobject *kobj);
};
struct kobject {
struct kobj_type *ktype;
};
struct device {
int device_id;
struct kobject kobj; // 繼承 kobject
void (*release)(struct device *dev);
};
struct pci_dev {
int vendor_id;
struct device dev; // 繼承 device
};
```
已知繼承關係： `struct pci_dev` (子類) -> 包含 `struct device` (父類) -> 包含 `struct kobject` (基底類別)。
釋放關係如下：
```c
void pci_release_dev(struct device *dev) {
// container_of：從 device 找回 pci_dev 位址
struct pci_dev *pdev = container_of(dev, struct pci_dev, dev);
free(pdev);
}
void device_release(struct kobject *kobj) {
// container_of：從 kobject 找回 device 位址
struct device *dev = container_of(kobj, struct device, kobj);
if (dev->release) // 多型
dev->release(dev);
else if ...
}
static const struct kobj_type device_ktype = {
.release = device_release,
.sysfs_ops = &dev_sysfs_ops,
.namespace = device_namespace,
.get_ownership = device_get_ownership,
};
```
釋放流程：
1. 呼叫 `kobject_put(kobj)`。
2. kobject 底層會呼叫其所屬類別的釋放函式：`kobj->ktype->release(kobj)`。這裡的 release 是一個函式指標。
3. 對於 struct device，這個指標通常被設定為 `drivers/base/core.c` 中的 `device_release(struct kobject *kobj)`。
4. `device_release` 只有 `kobj` 的指標，它必須透過 `container_of(kobj, struct device, kobj)` 來「反向」推出 `struct device` 的起始記憶體位置。
5. 取得 `struct device *dev` 後，再呼叫 `dev->release(dev)`。這時若裝置是 PCI 裝置，該函式指標就會指向 PCI 子系統的釋放函式（如 `pci_release_dev`），該函式再用一次 `container_of` 取得 `struct pci_dev *` 並進行最終的記憶體釋放。
下面是圖表顯示：
```graphviz
digraph container_of_memory_layout {
// 緊湊佈局設定
rankdir=LR;
nodesep=0.3; // 縮減水平間距
ranksep=0.5; // 縮減垂直距離
// 全域字體縮小
node [shape=none, fontname="Courier New", fontsize=12];
edge [fontname="Helvetica", fontsize=11];
// 記憶體布局表格 (更小的內距)
memory_block [label=<
<table border="0" cellborder="1" cellspacing="0" cellpadding="4">
<tr><td bgcolor="#555555"><font color="white" point-size="12"><b>Low Address</b></font></td></tr>
<tr><td port="pci_start" align="left" bgcolor="#f2dede">
<font point-size="12"><b>struct pci_dev {</b><br/>
<i>(pci_dev member)</i></font>
</td></tr>
<tr><td port="dev_start" align="left" bgcolor="#dff0d8">
<font point-size="12"> <b>struct device dev {</b><br/>
<i>(device member)</i></font>
</td></tr>
<tr><td port="kobj_start" align="left" bgcolor="#d9edf7">
<font point-size="12"> <b>struct kobject kobj {</b><br/>
<i>(kobject member)</i></font>
</td></tr>
<tr><td align="left" bgcolor="#dff0d8">
<font point-size="12"> <i>(device member)</i><br/>
<b>}</b></font>
</td></tr>
<tr><td align="left" bgcolor="#f2dede">
<font point-size="12"> <b>}</b></font>
</td></tr>
<tr><td bgcolor="#555555"><font color="white" point-size="12"><b>High Address</b></font></td></tr>
</table>
>];
// 指標節點 (縮小 margin)
kobj_ptr [shape=box, style=filled, fillcolor="#d9edf7", fontname="Helvetica", fontsize=12, margin=0.1, label="kobj_ptr"];
dev_ptr [shape=box, style=filled, fillcolor="#dff0d8", fontname="Helvetica", fontsize=12, margin=0.1, label="dev_ptr"];
// 箭頭
kobj_ptr -> memory_block:kobj_start [color="#31708f", penwidth=1.5, label=" 指向內部"];
dev_ptr -> memory_block:dev_start [color="#3c763d", penwidth=1.5, label=" 算出起始"];
{rank=same; kobj_ptr; dev_ptr}
}
```
==還沒有對比 c++ vptr==
### Q2
- [ ] 匿名結構體/union 在型別設計中的應用。作業一探討 Linux 核心的 abstraction preservation。閱讀 [`include/linux/skbuff.h`](https://github.com/torvalds/linux/blob/master/include/linux/skbuff.h) 的 `struct sk_buff`，找出其匿名 union 如何讓同一記憶體區域在不同網路層 (L2/L3/L4) 提供不同的 header 存取介面 (如 `skb->protocol` vs. `ip_hdr(skb)->saddr`)。以 `pahole` 工具分析 `struct sk_buff` 的完整記憶體布局，計算其 padding 浪費與 cache line 佔用情況，並從 git log 找出近年縮減 `sk_buff` 大小的 commit
## 細讀〈[Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)〉
* `rb_node` 結構與紅黑樹的實作細節。作業一探討 linked list traversal 的 cache locality 問題，作業二分析 hlist 的 `pprev` pointer tagging 設計。以此為出發點：
* (a) `rb_node` 將 parent pointer 與 color bit 打包在 `unsigned long __rb_parent_color` 中，利用 `struct rb_node` 的 alignment 保證最低位元為零。作業二分析此 pointer tagging 技巧在紅黑樹中的應用。延伸證明：設 `struct rb_node` 包含至少一個指標成員，故在 64 位元架構上 `sizeof(struct rb_node) >= 8`，`alignof(struct rb_node) >= 8`。從 C11 §6.2.8 的 alignment 規則出發，證明任何 `rb_node *` 的值 modulo 8 必為 0，因此低 3 位元皆可安全使用 (核心實際只使用 bit 0 存放顏色)。若某假想架構以 `packed` 屬性將 `rb_node` 壓縮至 1-byte alignment，此技巧如何失效？以 `__attribute__((packed))` 撰寫測試程式驗證
* (b) 作業一分析 linked list 的 O(1) 插入在實際硬體上可能比陣列慢 (cache 效應)。將此分析延伸至樹狀結構：紅黑樹的每次查詢沿路徑走訪 $O(\log n)$ 個節點，每個節點可能不在同一 cache line。Linux 核心在 VMA 管理中以 [Maple Tree](https://docs.kernel.org/core-api/maple_tree.html) 取代紅黑樹。Maple Tree 以 B-tree 風格將多個 entry 打包在單一節點 (每個 node 佔一至二個 cache line)，大幅提升 cache locality。從 git log 找出 Maple Tree 取代 rbtree 的 commit series (提示: 2022 年 Liam Howlett 的 patchset)，閱讀 [`include/linux/maple_tree.h`](https://github.com/torvalds/linux/blob/master/include/linux/maple_tree.h) 的 `struct maple_node`，分析其 slot 數量如何對應 cache line 大小。設計實驗：以使用者空間實作簡化版的 rbtree 與 B-tree (fan-out = 16)，以隨機查詢 $10^6$ 個元素的 latency 分布 (以 `perf stat -e cache-misses` 量測) 驗證 cache 行為差異
* 作業二分析 `hlist_head`/`hlist_node` 的 `pprev` 設計如何消除刪除首節點的特殊情況，正如 Linus Torvalds 所強調的 "good taste"。閱讀 `lib/rbtree.c` 的 `__rb_erase_augmented()`，分析紅黑樹刪除後的平衡修復 (`____rb_erase_color`) 中是否仍存在無法消除的特殊情況。紅黑樹的修復需區分四種 case (兄弟節點為紅/黑、侄子節點的顏色組合)，且左右子樹對稱，核心以 `__rb_rotate_set_parents()` 統一處理旋轉以減少重複程式碼。分析此設計是否達到「消除特殊情況」的目標，或只是將特殊情況以對稱性壓縮
* Linux 核心的 augmented rbtree 機制用於 interval tree ([`include/linux/interval_tree.h`](https://github.com/torvalds/linux/blob/master/include/linux/interval_tree.h))。在標準紅黑樹中，查詢「所有與 $[lo, hi]$ 重疊的區間」需走訪全部 $n$ 個節點 ($O(n)$)。interval tree 在每個節點額外維護 `__subtree_last` 欄位，記錄該子樹中所有區間右端點的最大值。閱讀 [`include/linux/interval_tree_generic.h`](https://github.com/torvalds/linux/blob/master/include/linux/interval_tree_generic.h) 的 `INTERVAL_TREE_DEFINE` 巨集，追蹤 `interval_tree_iter_first()` 與 `interval_tree_iter_next()` 的查詢邏輯：當節點的 `__subtree_last < lo` 時，整棵子樹可被剪枝。分析此剪枝如何將查詢時間從 $O(n)$ 降至 $O(\log n + k)$，其中 $k$ 為實際重疊的區間數。推導此複雜度界限的數學證明 (提示：在平衡樹上，每層至多走訪常數個不含結果的節點 (因為 `__subtree_last` 的傳播保證若左子樹無結果則可跳過)。從 `mm/interval_tree.c` 找出此資料結構在 VMA 管理中的應用場景 (如 `anon_vma_interval_tree` 用於 reverse mapping)
## 細讀〈[C 編譯器原理和案例分析](https://hackmd.io/@sysprog/c-compiler-construction)〉
* AMaCC (不到 2000 行的自我編譯 C 編譯器) 為案例，涵蓋 lexer、parser、中間表示、以及 ARM 程式碼產生。作業二分析 GCC 的 `-fstrict-aliasing`/`-fno-strict-overflow` 如何影響編譯結果，以及 UBSan 的位移檢查。以此為出發點：
* (a) AMaCC 這類簡易編譯器不進行 type-based alias analysis 或 value range propagation，因此不會因 UB 產生令人意外的最佳化，UB exploitation 是 SSA-based 最佳化 (如 GCC 的 tree-ssa 與 LLVM 的 InstCombine) 的產物。設計一段 C 程式碼包含有號溢位 UB (`int x = INT_MAX; x + 1`)，分別以 AMaCC (或其他簡易編譯器如 `tcc`) 與 GCC `-O2` 編譯執行，觀察行為差異，並從 compiler theory 的角度解釋為何 SSA 的 value numbering 與 range propagation 是觸發 UB exploitation 的必要條件
* (b) Linux 核心的 eBPF JIT ([`arch/x86/net/bpf_jit_comp.c`](https://github.com/torvalds/linux/blob/master/arch/x86/net/bpf_jit_comp.c)) 將 BPF bytecode 轉譯為原生 x86-64 指令，屬於三種執行模型中的 JIT 路徑。閱讀 `do_jit()` 的翻譯迴圈，追蹤 `BPF_ALU64_REG(BPF_ADD, ...)` 如何映射至 x86 `add` 指令。與 AMaCC 的 codegen 比較：AMaCC 從 AST 直接產生機械碼，eBPF JIT 從已驗證的 bytecode 翻譯，後者的安全性來自 verifier 的前置靜態檢查。從 Spectre v1 防禦的角度，說明 eBPF JIT 如何在條件分支後插入 `lfence` 或以 array index masking 防止推測執行越界存取 (提示: 搜尋 `opt_hard_wire_dead_code_branches` 與 `fixup_bpf_calls`)
* 符號表與 ELF 重定位。作業二探討 CRC 計算的 $\text{GF}(2)$ 多項式運算。Linux 核心模組 (`.ko`) 以 ELF relocatable object 的形式存在，`insmod` 時由 [`kernel/module/main.c`](https://github.com/torvalds/linux/blob/master/kernel/module/main.c) 的模組載入器執行重定位。閱讀 `apply_relocate_add()` (架構相關，如 `arch/x86/kernel/module.c`) 的重定位邏輯，說明 `R_X86_64_PC32` 與 `R_X86_64_PLT32` 重定位型別的計算方式。`CONFIG_MODVERSIONS` 以 `genksyms` 工具為每個 exported symbol 計算 CRC 校驗碼 (儲存於 `__versions` section)，模組載入時核心比對此 CRC 確保 ABI 相容。從 `scripts/genksyms/` 的原始碼追蹤 CRC 的計算方法，說明其與作業二分析的 CRC 多項式運算的關係，以及為何 struct layout 變更會改變 CRC 值
## 細讀〈[C 語言: 未定義行為](https://hackmd.io/@sysprog/c-compiler-optimization)〉
* 現代編譯器利用 UB 進行激進最佳化。作業二深入分析 strict aliasing (C99 6.5 §7)、有號位移溢位 (C99 6.5.7 §4)、以及 `-fno-strict-aliasing`/`-fno-strict-overflow` 在核心中的必要性。以此為出發點：
* (a) C99 引入的 `restrict` 關鍵字告知編譯器二個指標不重疊，允許更激進的最佳化 (如向量化)。Linux 核心極少使用 `restrict`。閱讀 `lib/string.c` 的 `memcpy()` 與 `memmove()` 實作，說明兩者的語意差異 (前者假設不重疊、後者處理重疊)。在核心語境下，若函式簽名加上 `restrict` 但呼叫端意外傳入重疊指標，行為為 UB，編譯器可能假定不重疊而省略安全的反向複製路徑。以 GCC `-O2 -ftree-vectorize` 編譯一段含 `restrict` 的 `memcpy` 替代品，觀察是否產生 SIMD 指令，並對比不含 `restrict` 時的差異
* (b) 核心的 [`include/linux/compiler.h`](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h) 以 `__builtin_unreachable()` 標記不應到達的路徑 (如 `switch` 的 `default` case)。閱讀 `BUG()` 巨集的展開式：在 `CONFIG_BUG` 啟用時觸發 `ud2` (x86 非法指令)，停用時退化為 `unreachable()`。設計程式碼展示 `unreachable()` 的危險：若標記實際可到達的路徑，GCC 會省略後續所有程式碼 (dead code elimination)，導致控制流落入相鄰函式的機械碼中。以 `objdump -d` 驗證此行為
### 1.
在 [lib/string.c](https://github.com/torvalds/linux/blob/master/lib/string.c) 中
```c
void *memcpy(void *dest, const void *src, size_t count)
{
char *tmp = dest;
const char *s = src;
while (count--)
*tmp++ = *s++;
return dest;
}
```
可以發現 `memcpy` 的邏輯比較直覺簡單，使得這段程式碼很容易被識別並替換成高度最佳化的 SIMD 指令，但其有個巨大的前提保證 dest 和 src 參考到的資料不能重疊。
接者再來看看 `memmove` 的程式碼：
```c
void *memmove(void *dest, const void *src, size_t count)
{
char *tmp;
const char *s;
if (dest <= src) {
tmp = dest;
s = src;
while (count--)
*tmp++ = *s++;
} else {
tmp = dest;
tmp += count;
s = src;
s += count;
while (count--)
*--tmp = *--s;
}
return dest;
}
```
會發現功能與 `memcpy` 一致，但在實作上卻多了一組 if-else 判斷邏輯，目的就是即使在 資料重疊 的情況下也能正確發揮功能，討論如下：
* `if (d < s)`：如果目的地在左邊，來源在右邊，從左往右搬運時，覆寫的區域一定是來源指標已經讀取過、不需要的區域，所以安全，也就是不重疊的情形。
* `else if (d > s)`：目的地在右邊。為了保護 src 尾部的資料不被 src 頭部的資料蓋掉，它會先把指標跳到 src + n 與 dest + n 的位置，然後使用 --d 和 --s 倒退的方式來複製與賦值。
根據 C99 6.7.3
> An object that is accessed through a restrict-qualified pointer has a special association with that pointer. This association, defined in 6.7.3.1 below, requires that all accesses to that object use, directly or indirectly, the value of that particular pointer.
> During each execution of B, let L be any lvalue that has &L based on P. IfL is used to access the value of the object X that it designates, and X is also modified (by any means), then the following requirements apply: T shall not be const-qualified. Every other lvalue used to access the value of X shall also have its address based on P.
如果在函數簽名中加了 `restrict` (例如上述的 `void *memcpy(void *restrict dest, const void *restrict src, size_t n)`)，且意外傳入了重疊的指標，使得存取到位址不是基於 src 的資料，這就是未定義行為 (UB)。
觀察下方程式碼：
```c
#include <stddef.h>
// 沒有 restrict：編譯器必須考慮 dest 和 src 可能重疊
void copy_no_restrict(int *dest, const int *src, size_t n) {
for (size_t i = 0; i < n; i++) {
dest[i] = src[i];
}
}
// 有 restrict：編譯器假設不重疊
void copy_with_restrict(int * restrict dest, const int * restrict src, size_t n) {
for (size_t i = 0; i < n; i++) {
dest[i] = src[i];
}
}
```
並用 GCC 最佳化進行編譯
```
gcc -O2 -ftree-vectorize -S -masm=intel copy_test.c
```
輸出分析：
1.在 `copy_no_restrict` 中：
由於沒有 restrict，編譯器必須假設 dest (rcx) 與 src (rdx) 可能重疊。因此多了以下這段程式碼
```assembly
copy_no_restrict:
...
lea rax, -4[rcx]
sub rax, rdx
cmp rax, 8
jbe .L10
...
.L4:
movdqu xmm0, XMMWORD PTR [rdx+rax]
movups XMMWORD PTR [rcx+rax], xmm0
...
```
這段程式碼在計算 dest 和 src 的位址差距。如果差距小於等於 8，意味著可能重疊就會跳轉到 .L10，其 .L10 為每次只搬運 4 bytes (一個 int)，避免資料損毀。
如果確認沒有重疊，才會進入 .L4 迴圈，使用 movdqu xmm0 和 movups 這些 128-bit SIMD 指令，一次搬運 4 個 int (16 bytes)，發揮向量化的高效能。
因此在這沒有 restrict 時，程式碼體積膨脹，且每次呼叫都必須付出額外的計算成本來檢查指標位置。
2. 在`copy_with_restrict` 中：
```assembly
copy_with_restrict:
test r8, r8
je .L21
sal r8, 2 # 計算 size
jmp memcpy # 直接跳轉去執行 memcpy！
```
這裡完全沒有指標距離的計算與 cmp 判斷，也沒有傳統的 for 迴圈，而是直接計算複製範圍，直接跳轉去執行 memcpy。
編譯器信任開發者直接捨棄所有安全檢查，極致 SIMD 去優化程式碼的同時，將可能導致不可預期的資料損毀。
### 2.
* SSA 形式在常數傳播與死碼消除中扮演關鍵角色。作業二的 `int_size_is_w` 函式展示有號位移 UB 如何導致條件分支被消除。設計一組最小化 C 程式碼 (每段不超過 10 行)，展示 GCC `-O2` 下至少三種不同類型的 UB exploitation：
* (a) 有號溢位，`if (x + 1 > x)` 被最佳化為 `if (true)`
* (b) 空指標解參考，`int *p = ...; int val = *p; if (p == NULL) { /* 此分支被消除 */ }`
* \(c) 位移超出範圍，`1 << 32` 在 32 位元 `int` 上。對每段程式碼以 `gcc -O2 -S` 產生組合語言，標示被消除或改變的指令，並對照 C99 規格書中對應的條款 (6.5 §5 有號溢位、6.5.3.2 §4 空指標解參考、6.5.7 §3 位移範圍)。進一步分析：Linux 核心的 `-fno-strict-overflow` 與 `-fwrapv` 能防禦 (a) 但無法防禦 \(c)，只有 `BIT()` 巨集搭配 `unsigned long` 才是位移 UB 的正解
## 細讀〈[錯誤更正碼 (ECC) 介紹和實作考量](https://hackmd.io/@sysprog/linux-ecc)〉
* 從 Shannon 的資訊理論出發：Hamming code、BCH code、Reed-Solomon code 的數學基礎。作業一探討有限域 $\text{GF}(2^8)$ 與 AES 的關聯，作業二分析 CRC 在 $\text{GF}(2)$ 上的多項式除法與 SWAR 實作。以此為出發點：
* (a) CRC 以 $\text{GF}(2)[x]$ 上的多項式模運算偵錯，Reed-Solomon 以 $\text{GF}(2^8)[x]$ 上的多項式糾錯。兩者的代數結構差異在於底層的 coefficient field：$\text{GF}(2)$ 只有 $\{0, 1\}$ 二個元素，運算極為簡單 (XOR/AND)；$\text{GF}(2^8)$ 有 256 個元素，乘法需要多項式乘法再模不可約多項式。閱讀 [`lib/reed_solomon/reed_solomon.c`](https://github.com/torvalds/linux/blob/master/lib/reed_solomon/reed_solomon.c) 的 `init_rs_gfp()` 與底層的 `init_rs_internal()`，追蹤其如何以 `rs->index_of[]` (log table) 與 `rs->alpha_to[]` (antilog table) 將乘法轉為加法 ($a \cdot b = \alpha^{\log_\alpha a + \log_\alpha b}$)，避免逐位元的多項式乘法。撰寫使用者空間程式以此查表法實作 $\text{GF}(2^8)$ 乘法，並驗證 $a \cdot a^{-1} = 1$ 對所有非零 $a$ 成立
* (b) 作業一提到 `hweight_long()` (Hamming weight) 的次可加性 $\text{hw}(a \oplus b) \leq \text{hw}(a) + \text{hw}(b)$。Hamming distance $d(x, y) = \text{hw}(x \oplus y)$ 決定碼的錯誤偵測/更正能力：最小距離 $d_{min}$ 的碼可偵測 $d_{min} - 1$ 個錯誤、更正 $\lfloor (d_{min} - 1)/2 \rfloor$ 個錯誤。閱讀 `include/linux/bitops.h` 的 `hweight_long()` SWAR 實作 (作業二已分析 SWAR 原理)，設計實驗：以 `hweight_long()` 計算隨機 (7,4) Hamming code 字碼間的距離分布，驗證最小距離確為 3
* EDAC (Error Detection And Correction) 子系統用於監控硬體 ECC 記憶體錯誤。閱讀 [`drivers/edac/edac_mc.c`](https://github.com/torvalds/linux/blob/master/drivers/edac/edac_mc.c) 的 `edac_mc_handle_error()`，追蹤 correctable error (CE) 與 uncorrectable error (UE) 的計數與通報路徑 (經由 `edac_raw_mc_handle_error()` 累加至 `mci->ce_count`/`mci->ue_count`)。以作業一探討的機率模型為基礎：假設 CE 發生率為 $\lambda_{ce}$ (events/hour)，且 CE 為 UE 的前兆 (研究顯示出現 CE 的 DIMM 之 UE 機率增加 $10 \times$)，建立 DIMM 失效的連續時間 Markov 模型 (healthy → CE → UE 三態)，推導 UE 發生前的期望時間，並說明 Linux 的 `ras-daemon` 如何以 CE 頻率趨勢觸發預防性 DIMM 替換
* NAND flash 的 ECC 需求與 BCH 碼。Linux 核心的 `drivers/mtd/nand/` 子系統以 BCH (Bose-Chaudhuri-Hocquenghem) 碼保護 NAND flash 資料完整性。BCH 碼的糾錯能力 $t$ (可糾正的錯誤位元數) 與碼字長度 $n = 2^m - 1$ 及所需 parity 位元數 $r$ 之間滿足關係 $r \leq m \cdot t$。閱讀 [`lib/bch.c`](https://github.com/torvalds/linux/blob/master/lib/bch.c) 的 `bch_init()`，追蹤其如何依據使用者指定的 $m$ (Galois field order) 與 $t$ (糾錯強度) 建構生成多項式 $g(x)$。對於典型的 NAND flash 配置，如 512 位元組 (4096 位元) 資料頁面配 4-bit ECC ($m = 13, t = 4$)，計算所需的 parity 位元數 $r = m \cdot t = 52$ 位元 (7 位元組)，驗證 spare area 是否足夠容納。說明 BCH 碼的設計保證 (designed distance)：$t$-bit 糾錯碼的最小距離至少為 $d_{min} \geq 2t + 1$。此為 BCH bound，不同於適用所有線性碼的 Singleton bound $d \leq n - k + 1$。分別以 BCH bound 與 Singleton bound 計算上述 $m=13, t=4$ 配置的理論極限。進一步比較 BCH 與 Reed-Solomon 在 NAND flash 場景的取捨：BCH 以位元為單位糾錯、RS 以符號 (symbol) 為單位。當錯誤模式為隨機位元翻轉 (如 MLC/TLC NAND 的 retention error) 時，BCH 的效率較高；當錯誤為突發型 (burst error) 時，RS 的符號糾錯更具優勢
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet