---
tags: linux2026
---
# [2026q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 3 週測驗題
> [作答表單](https://forms.gle/h2qMnZccTiTzLfFf7)
:::warning
:warning: 回答延伸問題時，務必優先以[課程教材](https://wiki.csie.ncku.edu.tw/linux/schedule)為主要出處，隨後參照 C 語言規格書、Linux 核心原始程式碼及其 git log 和 LKML (Linux Kernel Mailing-List)，和權威素材 (如 GCC 和 glibc 手冊，但絕對不是 CSDN 或者尋常的網路日誌/筆記)
AI 工具是輔助性質，可用來撰寫測試程式碼和收集資訊，但主要的推測、查證、分析，和討論，都該由人類進行。
:::
## Problem A: Pointer Arithmetic and Memory Layout
- [ ] Part 1: array decay、`sizeof` 與 `&` 運算子的規格分析
C99 6.3.2.1 §3 規定：在大多數 expression 語境下，型別為「N 個 T 的陣列」的運算式會轉換為「指向 T 的指標」，並指向陣列的首元素；但有三個例外不觸發此轉換：`sizeof` 運算子、一元 `&` 運算子，以及字串常數初始化陣列的情形。
以下程式在 Arm64 Linux (LP64) 上編譯執行:
```c
#include <stdio.h>
int a[5] = {10, 20, 30, 40, 50};
int *p = a; /* array decay */
int main(void)
{
printf("%zu\n", sizeof(a)); /* A01 */
printf("%zu\n", sizeof(p)); /* A02 */
printf("%zu\n", sizeof(*p)); /* A03 */
/* &a 與 a 的數值相同，但 C99 6.3.2.1 §3 的例外使型別不同 */
printf("%d\n", &a == (void *) a); /* 印出 1，但二者型別不同 */
return 0;
}
```
針對 Arm64 Linux (LP64) 回答:
* `sizeof(a)` = __ A01 __，因為 `sizeof` 作用於整個陣列物件，不觸發 decay。
* `sizeof(p)` = __ A02 __，因為 `p` 是指標，其大小與 `int *` 相同。
* `sizeof(*p)` = __ A03 __，因為 `*p` 取值 (dereference) 後得到 `int` 物件。
* `&a` 的型別為 __ A04 __，而 `a` (decay 後)的型別為 `int *`；二者數值相同但型別不同。
* 根據 C99 6.5.6 §8，在指標算術中 `(&a + 1)` 和 `(p + 5)` 的數值相同，但前者的步進大小為 __ A05 __ bytes，後者為 __ A06 __ bytes。
- [ ] Part 2: 指標算術邊界與 `ptrdiff_t`
C99 6.5.6 §9 規定：二個指標相減的結果型別為 `ptrdiff_t` (有號整數，定義於 `<stddef.h>`)；僅當二個指標指向同一陣列物件的元素 (或末尾後一位)時，相減才具有定義行為，否則屬於未定義行為 (C99 6.5.6 §9)。
Linux 核心 `include/linux/overflow.h` 利用指標差值計算結構欄位偏移，程式碼節錄如下：
```c
/* 計算 type 中 member 成員至尾端的大小，用於 flexible array 邊界檢查 */
#define struct_size_t(p, member, n) \
(sizeof(*(p)) + (n) * sizeof(*(p)->member))
```
獨立指標算術練習：
```c
int arr[4] = {1, 2, 3, 4};
int *pi = arr;
int *end = arr + 4; /* 合法：指向末尾後一位 */
char *pc = (char *) arr;
ptrdiff_t d1 = end - pi;
ptrdiff_t d2 = (char *)end - (char *)pi;
```
* `d1` = __ A07 __，型別為 `ptrdiff_t`，單位是元素的數量
* `d2` = __ A08 __，單位是 bytes，因為算術基於 `char *`。
* 若改為 `(pi + 4) - (pi + 1)`，結果為 __ A09 __，合法因為二者指向同一陣列。
* 若 `pi` 和另一個不相關陣列的指標相減，根據 C99 6.5.6 §9，屬於 __ A10 __。
* C99 並未規定 `ptrdiff_t` 必須能容納所有指標差值；在 Linux 核心中，Arm64 LP64 的實作使 `PTRDIFF_MAX` 等於 __ A11 __ (使用 C 語言規格的巨集名稱)，實際能涵蓋半個定址空間的差值。
> 邊界案例：在 32-bit 架構 (`PTRDIFF_MAX = 2^{31} - 1 ≈ 2 GiB`) 下，若配置一個 3 GiB 的 `char` 陣列 (`size_t` 合法，`SIZE_MAX ≈ 4 GiB`)，`end - begin` 的數學差值為 $3 \times 2^{30}$ bytes，超出 `PTRDIFF_MAX`；C99 6.5.6 §9 規定此差值無法以 `ptrdiff_t` 表示時屬於未定義行為。glibc 因此在 `malloc`、`calloc`、`realloc` 中強制將物件大小上限設為 `PTRDIFF_MAX`，以迴避此 UB。[CVE-2019-7309](https://nvd.nist.gov/vuln/detail/cve-2019-7309) 即為 `memcmp` 在超過 `SSIZE_MAX` 大小的物件上使用帶號比較指令而引發的漏洞。
- [ ] Part 3: `container_of` 的型別安全性與 `offsetof`
Linux v6.x 的 `include/linux/container_of.h` 透過 `__builtin_types_compatible_p` 在編譯時期捕捉型別不匹配的狀況：
```c
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
static_assert(__builtin_types_compatible_p(typeof(*(ptr)), \
typeof(((type *)0)->member)), \
"pointer type mismatch in container_of()"); \
((type *)(__mptr - offsetof(type, member))); })
```
`static_assert` 展開後等同 `_Static_assert` (C11 6.7.10)，確保 `*(ptr)` 的型別與 `((type *)0)->member` 的型別相容。`((type *)0)->member` 不對空指標取值，僅作為編譯時期型別查詢。
給定結構： (假設 Arm64 LP64：int = 4 bytes，指標 = 8 bytes，無 padding)
```c
struct task_struct_demo {
int pid;
int prio;
struct list_head run_list; /* 含 next(8 bytes) + prev(8 bytes) */
char comm[16];
};
```
針對 Arm64 Linux 回答：
* `offsetof(struct task_struct_demo, run_list)` = __ A12 __。
* 若 `ptr` 指向 `run_list` 成員，`container_of` 中 `__mptr - offsetof(...)` 使指標向低位址移動，還原為 `struct task_struct_demo *`
* `static_assert` 若傳入 `int *` 而非 `struct list_head *` 作為 `ptr`，將在編譯時期出錯，錯誤訊息為 `"pointer type mismatch in container_of()"`
* `((type *) 0)->member` 是合法的 C99 expression，根據 C99 6.5.2.3 §4，`->` 成員存取在 `NULL` 指標上僅作為 __ A13 __ (C 語言規格術語，6 個字元) 使用且不用來取值，編譯器只取其型別資訊
> Linux v6.2 引入 `container_of_const`，以 C11 `_Generic` 在編譯時期保留輸入指標的 `const` 限定符：傳入 `const struct member *` 時，回傳型別為 `const type *`；否則退化為標準 `container_of`。傳統 `container_of` 中 `void *__mptr = (void *)(ptr)` 的轉型會靜默丟棄 `const`，使回傳的親代結構指標可寫，違反 const 正確性。核心文件明確建議新程式碼一律優先使用 `container_of_const`。
`container_of` 的演進階段對照：
| 演進階段 | 實作策略 | 主要優點 | 缺點 |
|---|---|---|---|
| 樸素指標減法 | `(type *)((char *)(ptr) - offsetof(type, member))` | 僅需標準 C | 零型別安全；傳入錯誤指標型別時靜默造成記憶體毀損 |
| Statement expression | `({ const typeof(((type *)0)->member) *__mptr = (ptr); ... })` | 單次求值、隱式型別檢查 | 依賴 GNU C 擴充；無法嚴格保留 `const` 修飾子 |
| `_Generic` const 正確性 | `_Generic(ptr, const typeof(*(ptr)) *: ...)` | 編譯時期強制型別吻合並繼承 `const` | 高度依賴 C11 語法；錯誤訊息冗長 |
- [ ] Part 4: strict aliasing、`-fno-strict-aliasing` 與核心的 type punning
C99 6.5 §7 規定，物件只能透過以下型別的 locator value 存取，否則屬於未定義行為：
* 物件的宣告型別或其 qualified/signed/unsigned 版本
* 包含上述型別的 aggregate 或 union
* `char` 或 `unsigned char`
Linux 核心 `Makefile` 加入 `-fno-strict-aliasing` 以允許核心廣泛使用的 type punning 手法。以下為 `include/linux/filter.h` 中的典型 union 型別 punning： (節錄，BPF 指令暫存器存取)
```c
union bpf_attr;
/* 核心以 union 合法地在 u32 和 float 之間轉換 */
union { u32 u; float f; } cv;
cv.u = raw_bits;
float result = cv.f; /* C99 6.5.2.3 §3：union member access；C11 明確合法 */
```
不使用 union 的直接指標轉型：
```c
float f = 3.14f;
int *ip = (int *)&f; /* (A) */
unsigned char *cp = (unsigned char *)&f; /* (B) */
int i;
memcpy(&i, &f, sizeof(int)); /* \(C) */
```
回答以下：
* (A) 透過 `int *` 讀取 `float` 物件，違反 C99 6.5 §7 的 __ A14 __ 規則，屬於未定義行為；GCC 在 `-O2` 以上可能消除此讀取
* (B) 合法，C99 6.5 §7 明確允許以 __ A15 __ (規格書原文術語) 的指標存取任意物件。
* \(C) 合法，`memcpy` 在語意上等同以 `unsigned char` 逐 byte 複製，不違反 aliasing 規則；且 GCC 的 `__builtin_memcpy` 在來源對齊時可能最佳化為一道 load/store 指令：x86-64 為 `mov`，Arm64 為 `ldr`/`str` / 多條純量搬移指令。
* Linux 核心使用 `-fno-strict-aliasing` 而不是全面改用 `union`，是因為核心中 `container_of`、`hlist` 間接指標等手法會將指標型別跨越 C99 規格允許的範圍；若啟用 strict aliasing，編譯器可能錯誤地重新排序這些存取，從而破壞正確性。
:::success
延伸問題
* C99 6.3.2.1 §3 列出三種不觸發 array decay 的例外情境。在 Linux 核心原始程式碼中 (及 git log)，找出至少二處利用 `sizeof` 作用於整個陣列 (而非 decay 後的指標) 來計>算陣列長度的巨集或函式，並說明為何核心偏好 `ARRAY_SIZE(arr)` 而非手動 `sizeof(arr)/sizeof(arr[0])`。搭配 git log 舉出因錯誤使用 `sizeof` 導致 bug 的案例
* `container_of` 從 v2.6 的樸素指標減法演化至 v6.2 的 `container_of_const`。從 C 語言規格書 (C99 6.5.2.3、C11 6.5.1.1) 的角度，逐步說明各演進階段倚賴的語言特性 (statement expression、`_Static_assert`、`_Generic`)，並分析哪些屬於 ISO C 標準、哪些屬於 GNU extension。設計實驗驗證在 `-std=c11 -pedantic` 下，哪些版本無法通過編譯
* C99 6.5 §7 的 strict aliasing rule 列舉了合法的存取型別。Linux 核心以 `-fno-strict-aliasing` 全域停用此規則。回答以下:
* 在 Linux 核心的 git log 找出因啟用 strict aliasing 而導致編譯器錯誤最佳化的具體案例，說明哪段程式碼被錯誤重排
* 若未來 Linux 核心嘗試移除 `-fno-strict-aliasing`，`container_of`、`hlist` 的 `pprev` 間接指標、BPF JIT 等子系統需要做哪些修改？以 C11 的 `memcpy` 型別轉換或 C23 提案為基礎，提出可行的遷移策略
* `ptrdiff_t` 在 32-bit 架構下可能無法表示超過 2 GiB 的指標差值。分析 glibc 如何在 `malloc` 中以 `PTRDIFF_MAX` 作為物件大小上限，並在 Linux 核心的 git log 找出類似的防護措施。教材提及 CVE-2019-7309 涉及 `memcmp` 在超過 `SSIZE_MAX` 大小的物件上使用帶號比較指令。分析該漏洞的根本成因 (提示：x32 ABI 下 `RDX` 暫存器高位元未清零)，並說明此問題為何僅影響特定 ABI 而非所有 32-bit 架構。設計測試程式展示 `ptrdiff_t` 溢位在一般 32-bit 環境下的未定義行為
* 教材提及 `((type *)0)->member` 不解參考空指標，僅作為 lvalue 使用。從 C99 6.5.2.3 §4 和 6.3.2.1 §1 的角度，嚴格論證此運算式為何合法。在 C11 和 C23 規格中，此技巧的合法性是否有變化？若有，說明對 `offsetof` 巨集實作的影響
* `container_of` 的指標算術 `(char *)ptr - offsetof(type, member)` 依賴結構體記憶體佈局的連續性。給定結構體 `struct S { char a; int b; long c; struct list_head d; }` 在 LP64 平台，以 C99 6.7.2.1 的對齊規則，推導每個成員的 offset (考慮 padding)。建立通用公式：給定成員型別序列 $T_1, T_2, \ldots, T_n$ 及各自的 alignment requirement $a_i$，第 $k$ 個成員的 offset $o_k = \lceil o_{k-1} + \text{sizeof}(T_{k-1}) \rceil_{a_k}$ (上取整至 $a_k$ 的倍數)。以此公式驗證 `offsetof` 的正確性，並分析 `__attribute__((packed))` 如何改變此公式
:::
---
## Problem B: Indirect Pointers and Linux Kernel Usage
- [ ] Part 1: 間接指標刪除與 `WRITE_ONCE` 的 SMP 正確性
以下為使用間接指標刪除鏈結串列節點的手法，對應 Linux 核心中 `kernel/kprobes.c` 等多處的相同模式： (簡化示意)
```c
typedef struct probe_node {
unsigned long addr;
struct probe_node *next;
} probe_node_t;
typedef struct { probe_node_t *head; } probe_list_t;
void remove_probe(probe_list_t *list, probe_node_t *target)
{
probe_node_t **pp = &list->head; /* (A) 取 head 欄位的位址 */
while (*pp && *pp != target)
pp = __B01__; /* (B) 前進至下一個間接指標位置 */
if (*pp) {
WRITE_ONCE(*pp, target->next); /* (C) atomic 覆寫，防止 tear */
/* free(target) 在 RCU grace period 後才安全 */
}
}
```
* `(B)` 應填 __ B01 __：取目前節點 `next` 欄位的位址，使 `pp` 始終指向「存放下一個節點指標的記憶體位置」
* 相較於傳統 `prev->next = curr->next` 指標手法，此間接指標版本消除刪除開頭節點的特殊 `if` 分支，原因是 `pp` 指向 `head` 欄位時，`*pp = target->next` 等同修改 `head`，與修改中間節點的 `next` 語法上完全一致
* `(C)` 使用 `WRITE_ONCE` 而非直接指派，是因為在 SMP 環境下若其他 CPU 同時以 `READ_ONCE(*pp)` 讀取，直接指派可能引發三類編譯器違規：1) store tearing (拆分為多次 store); 2) store fusing (多次寫入合併為一次); 3) invented store (先寫推測值再覆寫)。`WRITE_ONCE` 透過 `*(volatile typeof(*pp) *)&(*pp) = ...` 確保 single-copy atomicity
* 根據 C99 6.2.4 §2，`target` 被 `free` 後其 lifetime 結束，此後任何透過 `target->next` 的存取屬於 __ B02 __ (引用 C99 6.2.4 §2 用語)。
- [ ] Part 2: `hlist_add_head` 與間接指標的統一插入
Linux `include/linux/list.h` 的 `hlist_add_head` 利用 `pprev` 間接指標使插入和刪除均不需要區分「首節點」的特殊情況：
```c
static inline void hlist_add_head(struct hlist_node *n,
struct hlist_head *h)
{
struct hlist_node *first = h->first;
WRITE_ONCE(n->next, first);
if (first)
WRITE_ONCE(first->pprev, &n->next);
WRITE_ONCE(h->first, n);
WRITE_ONCE(n->pprev, &h->first); /* (A) */
}
static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
WRITE_ONCE(*pprev, next); /* (B) */
if (next)
WRITE_ONCE(next->pprev, pprev);
}
```
三種串列抽象的記憶體佔用與指標語意對照：
| 串列抽象 | 主要結構 | 所含指標 | 核心典型用途 | 刪除複雜度 |
|---|---|---|---|---|
| 標準串列 | `struct list_head` | `next`、`prev` | 環狀佇列、行程任務、一般走訪 | $O(1)$ |
| hash 串列開頭 | `struct hlist_head` | `first` | hash table bucket，記憶體極度受限 | N/A |
| hash 串列節點 | `struct hlist_node` | `next` 和 `**pprev` | 分布於 hash bucket 中的元素 | $O(1)$ |
`hlist_head` 僅含一個指標 (8 bytes)，而 `list_head` 含兩個 (16 bytes)；對有 $2^{20}$ 個 bucket 的 hash table，節省 8 MiB 記憶體，同時減少 CPU cache 污染。
分析 `insert_sorted` (以鍵值排序的 `hlist` 插入)各邊界情況的 `pprev` 連結狀態，完成下表填空：
| 情況 | `pp` 指向何處 | 插入後 `n->pprev` 指向 |
|---|---|---|
| `hlist` 為空 | `&h->first` | __ B03 __ |
| 插入開頭 | `&h->first` | __ B04 __ |
| 插入尾端 | 末節點 (即新節點的上一個節點 (predecessor))的 `&tail->next` | __ B05 __ |
| 插入中間 | 上一個節點的 `&prev->next` | __ B06 __ |
* `__hlist_del` 的 `(B)` 行 `*pprev = next` 透過間接指標就地 (in-place) 修改上一個節點 (或 head) 的 `next` / `first` 欄位，達成 O(1) 刪除；若改用 `pprev` 儲存上一個節點的指標而非 `next` 欄位的位址，則刪除開頭節點時需額外分支，因為 `hlist_head` (僅含 `first`) 與 `hlist_node` (含 `next`、`**pprev`) 為不同結構，無法以統一的指派修改上一個節點的 `next` 或 head 的 `first`
* loop invariant：`insert_sorted_hlist` 迴圈維持「`pp` 始終指向存放下一個待比較節點指標的記憶體位置」，使 `*pp = n; n->pprev = pp;` 一次指派能統一處理 __ B07 __ 種邊界情況，無需額外分支。
- [ ] Part 3: `hlist_add_behind` 的插入順序與 SMP 安全性
`hlist_add_behind` 在指定節點 `prev` 之後插入新節點 `n`，須以精確順序呼叫 `WRITE_ONCE`，確保 SMP 讀者在任何瞬間都能看到合法的連結狀態：
```c
static inline void hlist_add_behind(struct hlist_node *n,
struct hlist_node *prev)
{
WRITE_ONCE(n->next, prev->next); /* (A) 先複製上一個節點的 next */
WRITE_ONCE(prev->next, n); /* (B) 再讓上一個節點指向 n */
WRITE_ONCE(n->pprev, &prev->next); /* (C) 設 n 的 pprev */
if (n->next)
WRITE_ONCE(n->next->pprev, &n->next); /* (D) 更新後繼節點的 pprev */
}
```
回答以下：
* `(A)` 必須在 `(B)` 之前執行：RCU 資料發布的核心原則是「節點內容完全就緒後，才讓其他 CPU 看到指向該節點的指標」。若 `(B)` 先讓 `prev->next` 指向 `n`，其他 CPU 透過 `READ_ONCE(prev->next)` 取得 `n` 後繼續走訪 `n->next`，但此時 `n->next` 尚未初始化，存取到 indeterminate value，導致核心 panic
* `(B)` 使用 `WRITE_ONCE` 而非普通指派，防止編譯器將 64-bit 指標 store 拆分為兩次 32-bit 寫入 (即 store tearing)，確保其他 CPU 以 `READ_ONCE` 讀取時取得完整指標值
* `(D)` 僅在 `n->next != NULL` 時執行，因為插入尾端時後繼為空，無節點需更新 `pprev`；此條件與 `hlist_add_head` 中 `if (first) WRITE_ONCE(first->pprev, &n->next)` 的邏輯相同
:::success
延伸問題
* 間接指標 (`probe_node_t **pp`) 消除刪除首節點的特殊分支。用 Graphviz 繪製以下三種情境的指標關係圖，標註每步 `pp` 和 `*pp` 的值：(a) 刪除首節點；(b) 刪除中間節點；(c) 刪除尾節點。對照傳統 `prev->next = curr->next` 手法，計算兩種實作的條件分支數量差異
* `WRITE_ONCE` 透過 `volatile` 語意防止 store tearing、store fusing、invented store。從 C11 5.1.2.3 的 observable behavior 定義和 C11 6.7.3 §6 的 `volatile` 語意出發，說明為何 C 標準的 `volatile` 不足以保證 SMP 環境下的 memory ordering，以及 Linux 核心為何仍需搭配 `smp_wmb()` 或 `smp_store_release()` 等 barrier
* `hlist_add_behind` 的四步 `WRITE_ONCE` 順序 (A→B→C→D) 是 RCU 發布語意的關鍵。假設將 (B) 和 (A) 對調 (先讓 `prev->next` 指向 `n`，再設定 `n->next`)，>設計一個具體的 SMP 交錯執行序列 (interleaving)，說明讀者 CPU 如何在此錯誤順序下讀到 indeterminate value。以 Linux 核心的 `tools/memory-model/litmus-tests/` 格式描述此 litmus test
* `hlist` 的 `pprev` 設計使 `hlist_head` (8 bytes) 與 `hlist_node` (16 bytes) 為不同結構。在 Linux 核心的 git log 找出至少二個子系統 (如 networking、filesystem) 從 `list_head` 遷移至 `hlist` 以節省記憶體的 commit，分析其記憶體節省量和效能影響
* C99 6.2.4 §2 規定物件 lifetime 結束後，透過指標存取屬於 undefined behavior。在 RCU 語境下，`free(target)` 必須延遲至 grace period 結束。說明 `call_rcu()` 和 `kfree_rcu()` 如何確保讀者在 grace period 內仍能安全存取即將釋放的節點，並從 C 語言規格的角度分析 RCU 的記憶體模型假設
* 設 hash table 有 $m$ 個 bucket、$n$ 個節點均勻分布，每個 bucket 以 `hlist` 串接。建立數學模型：間接指標刪除的期望指標解參考次數為何？與經典手法相比，在 bucket chain 長度 $\lambda = n/m$ 下，兩種手法的期望比較次數差異為何？以 $\lambda = 1, 4, 16$ 代入驗證。在 Linux 核心的 git log 找出因缺少 `WRITE_ONCE` 或 `READ_ONCE` 導致 store tearing / load tearing 的實際 bug (提示：`kernel/locking/` 和 `net/` 子系統)，分析該 bug 的 race condition 是否可在 C11 memory model 下形式化描述
:::
---
## Problem C: Linux Kernel List API and Merge Sort
- [ ] Part 1: `list_head` 侵入式設計、記憶體開銷與 `list_is_singular`
Linux `<linux/list.h>` 的侵入式雙向環狀鏈結串列將 `struct list_head` 嵌入資料結構中，相較於 C++ `std::list` 等容器型串列，每個節點不需額外配置包裝器：
```c
struct list_head {
struct list_head *next, *prev;
};
static inline int list_empty(const struct list_head *head)
{
return READ_ONCE(head->next) == head; /* (A) 利用 READ_ONCE 防止 tear */
}
static inline int list_is_singular(const struct list_head *head)
{
return !list_empty(head) && (head->next == __C01__);
}
```
應用案例 (include/linux/netdevice.h 大幅簡化)
```c
struct net_device {
char name[IFNAMSIZ];
struct list_head dev_list; /* 鏈結全域 net->dev_base_head */
/* ... 其他欄位 ... */
};
```
* 一個空的 `LIST_HEAD(head)` 初始化後，`head.next` 與 `head.prev` 均等於 __ C02 __ (指向自身)，`list_empty` 回傳 __ C03 __ (非零 / 零)。
* 填空 __ C01 __ 的判斷邏輯：當串列中恰好只有一個元素時，`head->next` 和 `head->prev` 指向同一個節點 (非 head)，以此條件確認「恰好一個元素」。
* `list_empty` 中的 `READ_ONCE` 作用是防止編譯器將此讀取 load hoisting，在 lockless 走訪中確保每次都從記憶體讀取最新值。
* 與 `std::list<net_device>` 相比，侵入式設計的優點在於：一個 `net_device` 物件可同時加入多個不同的 `list_head`，只需在結構中定義多個 `list_head` 成員。
- [ ] Part 2: `__list_add` 的指標操作順序與 SMP 可見性
```c
/* include/linux/list.h */
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
if (IS_ENABLED(CONFIG_DEBUG_LIST))
__list_add_valid_or_report(new, prev, next);
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new); /* (A) 最後才讓其他 CPU 可見此新節點 */
}
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1; /* (B) 0xDEADBEEF...，毒化指標 */
entry->prev = LIST_POISON2;
}
```
* `WRITE_ONCE(prev->next, new)` 放在最後，是因為其他 CPU 若以 `list_for_each` 走訪串列，它們第一個看到的是 `prev->next` 的改變。若此行先執行而 `new->next` 尚未設定，其他 CPU 讀到 `new->next` 為 indeterminate value，導致走訪時出現錯誤
* `LIST_POISON1` (`0x100 + POISON_POINTER_DELTA`；設定 `CONFIG_ILLEGAL_POINTER_VALUE` 後在 Arm64 通常為 `0xDEAD000000000100`) 是核心故意設定的毒化 (poison) 值，若被刪除節點被誤用後存取 `entry->next`，將觸發 segmentation fault，便於偵測 use-after-free
* `list_add(new, head)` 呼叫 `__list_add(new, head, head->next)`，將 `new` 插入 `head` 之後，適合實作 stack (每次從開頭讀取)
* `list_add_tail(new, head)` 呼叫 `__list_add(new, head->prev, head)`，將 `new` 插入 `head` 之前；對同一 `head` 交替呼叫 `list_add_tail` 和 `list_del_init(head->next)`，可實作 FIFO 佇列
- [ ] Part 3: `list_for_each_entry_safe` 的 `LIST_POISON` 防護
```c
/* include/linux/list.h */
#define list_for_each_entry_safe(pos, n, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member), \
n = list_next_entry(pos, member); \
!list_entry_is_head(pos, head, member); \
pos = n, n = list_next_entry(n, member))
/* include/linux/poison.h (Arm64) */
#define LIST_POISON1 ((void *) 0xDEAD000000000100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0xDEAD000000000122 + POISON_POINTER_DELTA)
```
一個典型的刪除走訪：
```c
struct work_item {
int id;
struct list_head list;
};
LIST_HEAD(work_queue);
void flush_completed(void)
{
struct work_item *pos, *tmp;
list_for_each_entry_safe(pos, tmp, &work_queue, list) {
if (pos->id < 0) {
list_del(&pos->list); /* 刪除後 pos->list.next = LIST_POISON1 */
kfree(pos);
}
}
}
```
* 此巨集增加 `tmp` 參數，在迴圈更新時先 `pos = tmp`、再 `tmp = list_next_entry(tmp, list)`，確保即使刪除 `pos` 後，`tmp` 仍為迴圈起始時預先儲存的 __ C04 __
* 若改用 `list_for_each_entry` (不帶 `_safe`)，在迴圈體中呼叫 `list_del(&pos->list)` 後，迴圈更新表示式 `pos = list_next_entry(pos, list)` 等同存取 `(struct work_item *)pos->list.next`，而此時 `pos->list.next = LIST_POISON1 = 0xDEAD...`，取值 (dereference) 後產生 segmentation fault
* `list_entry_is_head(pos, head, member)` 判斷 `pos` 是否走回哨兵節點，利用環狀鏈結串列以 __ C05 __ 作為終止哨兵 (無需計數器或 NULL)。
* 假設 `work_queue` 有 $n$ 個節點，此走訪的時間複雜度為 O( __ C06 __ )；若需要依 `id` 快速尋找，應搭配 __ C07 __ + hash table，以達到 $O(1)$ 期望時間。
- [ ] Part 4: `lib/list_sort.c` 的合併計數器策略
Linux `lib/list_sort.c` 採用仿 Timsort 的 pending list 策略，關鍵邏輯如下 (節錄並加入註解)：
```c
/* lib/list_sort.c */
void list_sort(void *priv, struct list_head *head,
list_cmp_func_t cmp)
{
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* 已接收但尚未最終合併的節點計數 */
/* ... 拆分為單節點 ... */
do {
size_t bits;
struct list_head **tail = &pending;
/* 找到 pending 串列中應合併的位置 */
for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev; /* (A) 沿 pending 串列前進 */
/* 若 count 的第 k 個位元為 0，在此處插入新的 run */
if (likely(bits)) {
struct list_head *a = *tail, *b = a->prev;
a = merge(priv, cmp, b, a);
a->prev = b->prev;
*tail = a;
}
/* 將新節點加入 pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;
} while (list != head);
/* 最終將 pending 中所有 run 合併 */
/* ... */
}
```
* `for (bits = count; bits & 1; bits >>= 1)` 迴圈在 `bits` 的 __ C08 __ (最低有效位 / 最高有效位)連續為 1 時持續前進，等效於找到 `count` 的二進位表示中最低的 0 位元的位置
* 這使得每次加入新節點後，若 `count` 的二進位末端有連續 1 (如 `...10111`)，for 迴圈跳過 3 個已佔用槽位後在最低 0 位元處觸發 __ C09 __ 次合併，使 pending 串列中各 run 長度始終是 2 的冪，避免最壞情況下 $O(n^2)$ 的比較次數。 (若 `count` 恰好為純全 1 二進位，如 `0b0111`，則 `bits` 歸零，該迭代不觸發合併)
* `list_sort` 的比較次數上界為 $n\lceil \lg n \rceil - 2^{\lceil \lg n \rceil} + 1$，與標準 bottom-up merge sort 的上界 $n\lceil \lg n \rceil$ 相比，在 $n$ 非 2 的冪時，前者較小；差距 $2^{\lceil \lg n \rceil} - 1$ 在 $n$ 恰好為 2 的冪時縮小為 $n - 1$，在 $n$ 略大於 2 的冪時最大化
* `list_sort` 保證 stable 的關鍵在於 `merge()` 函式使用 `cmp(a, b) <= 0` 時優先選擇 `a`；若改為 `< 0`，則相等元素的相對順序可能顛倒
* 相較 quicksort，merge sort 更適合鏈結串列的根本原因是：quicksort 的 partition 需要 $O(1)$ 的隨機存取以找到中點或第 $k$ 個元素，而鏈結串列的讀取僅支援序列存取，找中點需要 $O(n)$。
:::success
延伸問題
* `list_for_each_entry_safe` 預存 `tmp` 以允許在迴圈體中刪除當前節點。但若迴圈體中同時刪除 `tmp` 指向的下一個節點，此巨集是否仍然安全？提出程式碼片段展示此邊界情況，並說明 Linux 核心中 `list_for_each_entry_safe_from` 和 `list_safe_reset_next` 如何處理此問題
* `LIST_POISON1` 和 `LIST_POISON2` 使用非零毒化值 (如 `0xDEAD000000000100`) 而非 `NULL`。從 Linux 核心的 memory layout 和 page fault 處理的角度，說明為何選擇此特定位址範圍。在 git log 找出因 use-after-free 觸發 `LIST_POISON` 而被偵測到的 bug 案例
* `lib/list_sort.c` 的合併策略使用 `count` 的二進位表示來決定合併時機。以 $n = 13$ 為例，逐步追蹤 `count` 從 0 到 12 的過程中，每步的 `bits` 值、`for` 迴圈執行次數、以及 pending 串列中各 run 的長度。用表格呈現，並驗證合併次數是否符合 $n\lceil \lg n \rceil - 2^{\lceil \lg n \rceil} + 1$ 的上界
* `list_sort` 的 `merge()` 以 `cmp(a, b) <= 0` 確保 stable sort。從 C 語言規格的比較函式契約 (三向比較、反對稱性、遞移律) 出發，說明若使用者提供的 `cmp` 函式違反遞移律，`list_sort` 可能產生什麼後果。在 Linux 核心的 git log 找出因比較函式不當而導致排序錯誤的案例
* 侵入式串列 (`struct list_head` 嵌入資料結構) 允許同一物件加入多條串列。設計實驗比較侵入式串列與容器式串列 (如 `std::list`) 在以下情境的 cache miss rate：(a) 依序走訪 $10^6$ 個節點；(b) 隨機插入/刪除。使用 `perf stat -e cache-references,cache-misses` 測量，並以數學模型解釋觀察到的差異
* `__list_add` 將 `WRITE_ONCE(prev->next, new)` 放在最後一步。若 Linux 核心編譯時未啟用 `CONFIG_DEBUG_LIST`，此函式沒有任何 memory barrier。在 Arm64 弱順序記憶體模型下，說明為何 `list_add` 在非 RCU 語境下仍需搭配適當的鎖機制，並分析 `list_add_rcu` 與 `list_add` 的差異
:::
---
## Problem D: CPU Scheduler Concepts and Implementation
- [ ] Part 1: CFS `vruntime`、`prio_to_weight` 與 `rb_root_cached`
Linux CFS (Completely Fair Scheduler) 的核心資料結構定義於 `kernel/sched/fair.c`，以 `vruntime` 量化任務對 CPU 的使用量：
$$
\text{vruntime}_\text{delta} = \Delta t_{\text{real}} \times \frac{\text{NICE_0_LOAD}}{\text{weight}}
$$
```c
/* prio_to_weight 以 nice=0 (索引 [20])為基準，呈等比分布，公比 ≈ 1.25 */
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
struct cfs_rq {
struct load_weight load;
struct rb_root_cached tasks_timeline; /* (A) leftmost 快取 */
struct sched_entity *curr;
u64 min_vruntime; /* runqueue 的虛擬時鐘基準 */
};
```
回答以下：
* `NICE_0_LOAD = prio_to_weight[20] = __ D01 __`，為 2 的 __ D02 __ 次方，便於以位元移位取代除法
* `rb_root_cached` 比 `rb_root` 多快取 __ D03 __ (leftmost / rightmost)節點，使 CFS 找到下一個執行任務的時間複雜度降至 $O(1)$ (而非 $O(\log n)$ 的樹走訪)。
* nice 值每差 1，weight 約為前者的 __ D04 __ 倍 (十進位小數，小數點後一位) (`prio_to_weight` 設計為等比數列，公比 ≈ 1.25)。以 nice=0 和 nice=1 為例 ≈ __ D05 __ (十進位小數，小數點後二位)
* 新任務 (首次 `fork`) 的 `vruntime` 初始化為 `cfs_rq->min_vruntime`，避免其因 `vruntime = 0` 而長期獨占 CPU。Linux v6.6 以後改用 EEVDF，喚醒任務的 `vruntime` 以 `avg_vruntime(cfs_rq)` 為基準，再減去其 lag (`place_entity()` 計算 `se->vruntime = avg_vruntime - lag`)；`se->vlag` 在任務睡眠期間保持不變 —— `se->vlag` 是相對於系統平均虛擬時鐘的靜態差值，喚醒時直接以 `se->vruntime = avg_vruntime(cfs_rq) - lag` 還原，長眠任務不因此積累額外排程優先。
- [ ] Part 2: `__calc_delta` 的定點乘除與溢位防護
```c
/* kernel/sched/fair.c */
static u64 __calc_delta(u64 delta_exec, unsigned long weight,
struct load_weight *lw)
{
u64 fact = scale_load_down(weight); /* (A) 將 weight 縮放至適合 u32 的範圍 */
u32 fact_hi = (u32)(fact >> 32);
int shift = 32;
/*
* 避免 64×64 → 128-bit 中間結果：
* 若 fact_hi 非零，右移 fact 直到 fact_hi == 0，
* 同時累積 shift，最後右移補回。
*/
if (unlikely(fact_hi)) {
shift += fls(fact_hi); /* (B) */
fact >>= shift - 32;
}
/*
* 此時 fact 已保證 <= 32 bits，
* 以 mul_u64_u32_shr 計算 delta_exec * fact * lw->inv_weight >> shift
*/
return mul_u64_u32_shr(delta_exec,
mul_u32_u32(fact, lw->inv_weight),
WMULT_SHIFT + shift - 32); /* (C) */
}
```
回答以下：
* `scale_load_down(weight)` 在 `CONFIG_SMP` 開啟時 (SMP 幾乎覆蓋所有 Arm64/x86-64 配置)將 weight 右移 `SCHED_FIXEDPOINT_SHIFT` (= 10)位，目的是將 `prio_to_weight` 的值從 `NICE_0_LOAD<<10 = 1048576` 縮回 __ D06 __，使乘積不會超出 32 位元範圍
* `fls(fact_hi)` 回傳 `fact_hi` 中最高有效位元的位置 (從 1 算起)，用於計算需要多少額外右移才能使 `fact` 縮入 32 位元
* `mul_u32_u32(fact, lw->inv_weight)` 計算二個 `u32` 的乘積，結果為 __ D07 __ 位元，不需 128-bit 算術；`lw->inv_weight = 2^32 / lw->weight`，因此 `fact * inv_weight >> 32 ≈ `fact / lw->weight` (即 `fact / lw->weight`，`fact` 在此語境下代表已縮放的 entity weight)
* `WMULT_SHIFT = 32`，加上額外 `shift - 32`，合計最終右移 `32 + shift - 32 = __ D08 __` 位元，抵銷 `inv_weight` 中的 $2^{32}$ 因子
- [ ] Part 3: `preempt_count` 的精確位元佈局
`include/linux/preempt.h` 以一個 per-task 整數打包所有搶占相關計數器：
```c
/* include/linux/preempt.h */
#define PREEMPT_BITS 8
#define SOFTIRQ_BITS 8
#define HARDIRQ_BITS 4
#define NMI_BITS 4 /* 注意：NMI_BITS = 4，非 1 */
#define PREEMPT_SHIFT 0
#define SOFTIRQ_SHIFT (PREEMPT_SHIFT + PREEMPT_BITS) /* = 8 */
#define HARDIRQ_SHIFT (SOFTIRQ_SHIFT + SOFTIRQ_BITS) /* = 16 */
#define NMI_SHIFT (HARDIRQ_SHIFT + HARDIRQ_BITS) /* = 20 */
#define PREEMPT_MASK ((1UL << PREEMPT_BITS) - 1) /* = 0x000000FF */
#define SOFTIRQ_MASK ((1UL << SOFTIRQ_BITS) - 1) << SOFTIRQ_SHIFT /* (A) */
#define HARDIRQ_MASK ((1UL << HARDIRQ_BITS) - 1) << HARDIRQ_SHIFT
#define NMI_MASK ((1UL << NMI_BITS) - 1) << NMI_SHIFT
#define hardirq_count() (preempt_count() & HARDIRQ_MASK)
#define softirq_count() (preempt_count() & SOFTIRQ_MASK)
#define irq_count() (preempt_count() & (HARDIRQ_MASK | SOFTIRQ_MASK | NMI_MASK))
#define in_interrupt() (irq_count())
#define in_softirq() (softirq_count())
#define in_hardirq() (hardirq_count())
```
回答以下：
* `SOFTIRQ_MASK` 的十六進位值為 __ D09 __ (展開 `SOFTIRQ_SHIFT = 8`，`SOFTIRQ_BITS = 8`)。
* `NMI_MASK` 的十六進位值為 __ D10 __ (`NMI_SHIFT = 20`，`NMI_BITS = 4`)。
* `in_nmi()` 應以 `__ D11 __` 實作 (使用已定義的 mask 巨集)。
* `local_bh_disable()` 將 `SOFTIRQ_DISABLE_OFFSET = 2 << SOFTIRQ_SHIFT = __ D12 __` (十進位) 加至 `preempt_count`，使 `softirq_count()` 非零 (`SOFTIRQ_DISABLE_OFFSET = 2 * SOFTIRQ_OFFSET`，與 `in_serving_softirq()` 所用的 `SOFTIRQ_OFFSET` 不同)；`local_bh_enable()` 則減回相同值。
* 若一個 CPU 同時處理 2 層巢狀 hardirq，`hardirq_count()` 的值為 __ D13 __ (十六進位)，因為 `HARDIRQ_OFFSET = 1 << HARDIRQ_SHIFT = 0x10000`，二層即 `2 * 0x10000`。
:::success
* CFS 的 `prio_to_weight` 表以等比數列設計，公比約 1.25。從數學角度推導：為何公比選擇 1.25 (而非 1.5 或 2.0) 能讓 nice 值每差 1 單位，CPU 分配比例變化>約 10%？建立數學模型，計算 nice=0 與 nice=5 任務在雙任務系統中的 CPU 時間比例，並以 Linux 核心實際的 weight 值驗證
* `__calc_delta` 使用 `inv_weight = 2^32 / weight` 將除法轉換為乘法加右移。從數值分析的角度，推導此定點數近似的最大相對誤差，並說明 `WMULT_SHIFT = 32` 的選擇如何平衡精度與溢位風險。在 Linux 核心的 git log 找出因 `__calc_delta` 精度不足或溢位而修正的 commit
* Linux v6.6 以 EEVDF 取代傳統 CFS。從 `kernel/sched/fair.c` 的 git log，分析 EEVDF 的 `place_entity()` 如何以 `vlag` 處理睡眠任務的喚醒公平性。與傳統 CFS 的 `min_vruntime` 補償機制相比，EEVDF 在以下情境的行為有何差異：(a) 短暫睡眠 (<1 ms)；(b) 長時間睡眠 (>10 s)？
* `preempt_count` 以單一整數打包四層計數器 (preempt、softirq、hardirq、NMI)。從位元操作的角度，說明為何 `in_interrupt()` 使用三個 mask 的 OR 而非逐一檢查。若未來新增第五層計數器 (如 hypothetical "secirq")，現有的 24-bit 佈局是否足夠？分析 `preempt_count` 的 bit 分配在 Linux 核心歷史中的演變 (搭配 git log)
* `rb_root_cached` 快取 leftmost 節點使 CFS 選擇下一個任務的時間複雜度降為 $O(1)$。設計實驗比較 `rb_root` 和 `rb_root_cached` 在以下工作負載下的效能差>異：不同數量的可執行任務 ($N = 10, 100, 1000, 10000$)。使用 perf 測量 `pick_next_entity` 的延遲，並以數學模型預測 $O(\log N)$ 與 $O(1)$ 的交叉點
:::
---
## Problem E: Hash Tables and Hash Functions
- [ ] Part 1: `hlist` 記憶體佈局、`pprev` 的 O(1) 刪除證明
Linux `include/linux/hashtable.h` 定義：
```c
/* include/linux/hashtable.h */
#define DEFINE_HASHTABLE(name, bits) \
struct hlist_head name[1 << (bits)] = \
{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
/* include/linux/list.h */
struct hlist_head { struct hlist_node *first; };
struct hlist_node { struct hlist_node *next, **pprev; };
static inline void hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
WRITE_ONCE(*pprev, next); /* (A) 就地修改上一個節點 (或 head)的 next/first */
if (next)
WRITE_ONCE(next->pprev, pprev);
}
```
* `hlist_head` 只有 `first` 一個指標 (8 bytes)，而相較之下，`list_head` 有 `next` 和 `prev` 二個指標 (16 bytes)。對於有 $2^{20}$ (約 100 萬) 個 bucket 的雜湊表，二者的記憶體差距為 __ E01 __ MiB。
* `hlist_node.pprev` 的型別為 `struct hlist_node **` (指向指標的指標)，對於串列首節點，`pprev` 指向 __ E02 __；對於中間節點，`pprev` 指向 __ E03 __。
* `hlist_del(n)` 的 `(A)` 行 `*pprev = next`，透過間接指標就地修改上一個節點 (或 head)的 `next`/`first` 欄位，無需區分首節點與中間節點的特殊情況。此統一操作使刪除時間複雜度為 __ E04 __，不需要走訪搜尋上一個節點
* `DEFINE_HASHTABLE(inode_hashtable, 12)` 在核心的 `fs/inode.c` 中定義了 $2^{12} = 4096$ 個 bucket 的 inode hash table；bucket 索引以 `hash_32(i_ino ^ i_dev, 12)` 計算，其中取高 12 位元的操作等同 `>> __ E05 __`。
- [ ] Part 2: `hash_32` 乘法雜湊的數學基礎
```c
/* include/linux/hash.h */
#define GOLDEN_RATIO_32 0x61C88647u
#define GOLDEN_RATIO_64 0x61C8864680B583EBull
/* Knuth 乘法雜湊：取乘積高位 */
static inline u32 hash_32(u32 val, unsigned int bits)
{
/* 0x61C88647 = 2^32 - floor(2^32 / φ) */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
static inline u64 hash_64(u64 val, unsigned int bits)
{
return val * GOLDEN_RATIO_64 >> (64 - bits);
}
```
* `GOLDEN_RATIO_32 = 0x61C88647`；精確公式為 $2^{32} - \lfloor 2^{32} / \varphi \rfloor$ 其中 $\varphi = (1+\sqrt5)/2$。驗算: $\lfloor 2^{32} / 1.618... \rfloor = \lfloor 4294967296 / 1.618... \rfloor = 2654435769 = \mathtt{0x9E3779B9}$，因此 `0x61C88647` $= 2^{32} - \mathtt{0x9E3779B9} =$ __ E06 __ (mod $2^{32}$，以 hex 驗算)
* `0x9E3779B9` 是 Fibonacci hashing 的標準常數，也出現在 AES key schedule 中；`0x61C88647` 是其加法反元素 mod $2^{32}$
* 乘法雜湊的均勻性依賴 `GOLDEN_RATIO_32` 與 $2^{32}$ 的最大公因數為 __ E07 __ (因為 `0x61C88647` 是奇數)；若常數為偶數 (如 `0x61C88646`)，其 $\gcd$ 與 $2^{32}$ 為 2，使 32 位元乘積的像集 (image)僅涵蓋一半的可能值 (均為偶數)，雖然取高 `bits` 位元後仍可覆蓋全部 $2^{\text{bits}}$ 個 bucket，但每個 bucket 對應的輸入僅為奇數常數時的一半，分布均勻性降低。
* `hash_32(val, 6)` 對 $2^{32}$ 個輸入應均勻對映到 $2^6 = 64$ 個 bucket；理論上每個 bucket 的期望輸入數為 $2^{E08}$
- [ ] Part 3: `jhash` 的 finalisation mix 與雪崩效應
Linux `include/linux/jhash.h` 實作 Jenkins hash，其 finalisation mix 針對短鍵值確保雪崩效應：
```c
/* include/linux/jhash.h */
#define __jhash_final(a, b, c) \
{ \
c ^= b; c -= rot32(b, 14); \
a ^= c; a -= rot32(c, 11); \
b ^= a; b -= rot32(a, 25); \
c ^= b; c -= rot32(b, 16); \
a ^= c; a -= rot32(c, 4); \
b ^= a; b -= rot32(a, 14); \
c ^= b; c -= rot32(b, 24); \
}
static inline u32 jhash(const void *key, u32 length, u32 initval)
{
u32 a, b, c;
const u8 *k = key;
a = b = c = JHASH_INITVAL + length + initval;
/* 每輪處理 12 bytes，使用 mix 函式 */
while (length > 12) { /* ... mix(a, b, c) ... */ length -= 12; k += 12; }
/* 處理最後 <= 12 bytes */
switch (length) {
case 12: c += ((u32)k[11]) << 24; /* falls through */
/* ... */
case 1: a += k[0]; break;
case 0: return c;
}
__jhash_final(a, b, c); /* (A) 確保短鍵值的雪崩效應 */
return c;
}
```
* `__jhash_final` 中每步都混合 `xor`、`subtract` 和 `rotate`，確保輸入的任意 1 個位元改變，輸出平均改變約 __ E09 __ 個位元 (嚴格雪崩準則，SAC)。
* `rot32(x, k)` 為 `(x << k) | (x >> (32 - k))` (循環左移)；若直接使用線性移位 (`x << k`)而不旋轉，高位元接收輸入的影響路徑更長，雪崩效應需要更多輪次。
* `JHASH_INITVAL` 定義於 `include/linux/jhash.h`，為 `0xDEADBEEF`，其用途是使空鍵值 (`length = 0`)的輸出非 __ E10 __，避免 `jhash(NULL, 0, seed)` 恆回傳可預測值。
* 若不執行 `__jhash_final` (僅做前段 mix)，長度為 1 byte 的鍵值在 `a += k[0]` 後其他位元 `b`、`c` 完全未受輸入影響，回傳的 `c` 僅反映 `JHASH_INITVAL + length + initval`，雜湊品質極差
- [ ] Part 4: 負載因子、生日悖論與 `inode_hashtable` 的 bucket 選擇
```c
/* fs/inode.c */
static unsigned int i_hash_mask __read_mostly;
static unsigned int i_hash_shift __read_mostly;
static struct hlist_head *inode_hashtable __read_mostly;
void __init inode_init(void)
{
unsigned int loop;
/* 根據記憶體大小動態決定 bucket 數 */
inode_hashtable = alloc_large_system_hash("Inode-cache",
sizeof(struct hlist_head),
ihash_entries, /* 使用者可調參數 */
14, /* 預設：記憶體的 1/2^14 */
HASH_ZERO,
&i_hash_shift,
&i_hash_mask, /* = (1 << i_hash_shift) - 1 */
0,
0);
/* i_hash_mask = 2^i_hash_shift - 1，確保 bucket 索引以位元運算取模 */
}
```
設 bucket 數 $m = 2^{i\_hash\_shift}$，已存 inode 數 $n$，負載因子 $\alpha = n/m$：
* 在均勻雜湊假設下，某特定 bucket 的期望節點長為 $\alpha$；當 $\alpha = 1$ 時，平均搜尋一個 inode 需走訪 __ E11 __ 個節點 (期望值)
* 生日悖論：在 $m$ 個 bucket 中插入 $n$ 個元素，至少發生一次碰撞的機率 $\approx 1 - e^{-n(n-1)/(2m)}$；當 $n \approx 1.18\sqrt{m}$ 時碰撞機率達到 __ E12 __ (近似值)
* `i_hash_mask = (1 << i_hash_shift) - 1` 使 bucket 索引計算 `hash & i_hash_mask` 等同 `hash % (2^i_hash_shift)`，但以位元運算取模比整數除法快，原因是 DIV 需多個 cycle，AND 需 1 cycle
* 若系統有 $2^{27}$ bytes (128 MiB) 可用，預設以 $1/2^{14}$ 分配 inode hash table，則 bucket 數為 $2^{27} / 2^{14} / \text{sizeof}(\text{hlist\_head}) = 2^{E13}$ (假設 `sizeof(hlist_head) = 8 bytes`)
:::success
* 設計實驗程式 (C 或 Python)，以 key 範圍 0~10000、bucket 數量 1024，比較以下四個常數的 hash 分布：`0x61C88647`、`0x9E3779B9`、`0x80000000`、`0x12345678`。繪製 bucket occupancy 分布圖，分析 collision rate 和 clustering 程度，並以 $\chi^2$ 檢定驗證均勻性
* `GOLDEN_RATIO_64 = 0x61C8864680B583EB` 在環 $R = \mathbb{Z}/2^{64}\mathbb{Z}$ 中是否為 unit (可逆元素)？給出判定條件 (提示：奇偶性與 $\gcd(C, 2^{64})$)。若可逆，以擴展歐幾里得演算法求出 $C^{-1} \bmod 2^{64}$。隨後解釋：即使乘法在 $R$ 中可逆，為何 `hash_64(val, bits)` 依然不可逆？指出右移取高位元等價於丟棄資訊，並說明丟棄的位元數量與 preimage 集合大小的關係
* `jhash` 的 finalisation mix 使用 `xor`, `subtract`, `rotate` 三種運算。從密碼學的角度，分析此 mix 為何能達到嚴格雪崩準則 (SAC)。設計實驗：對 $10^6$ >個隨機輸入，統計每個輸入位元翻轉後輸出位元的翻轉機率，繪製 32×32 的雪崩矩陣熱力圖
* 若攻擊者可控制 hash table 的輸入 key (如 HTTP header 或網路封包欄位)，刻意製造大量 hash collision，將查詢時間從 $O(1)$ 退化為 $O(n)$。分析此 HashDoS 攻擊的數學條件：給定 hash 函式 $h$ 和 $m$ 個 bucket，攻擊者需產生多少個碰撞 key 才能使單一 bucket 的 chain 長度達到 $L$？從機率角度，比較 Jenkins hash (非密碼學) 與 SipHash (PRF) 在抗碰撞攻擊上的安全性差異。在 Linux 核心的 git log 找出 SipHash 引入的相關 commit (提示：`lib/siphash.c` 與 `include/linux/siphash.h` 首次出現的 commit，以及 `net/core/` 中從 `jhash` 遷移至 `siphash` 的後續 commit)，分析哪些子系統因 HashDoS 風險而優先遷移，並說明其防禦策略
* `inode_hashtable` 的 bucket 數量由 `alloc_large_system_hash` 根據可用記憶體動態決定。從 `/proc/slabinfo` 或 `dmesg` 輸出中找出實際系統的 inode hash table 大小，計算其在典型工作負載下的負載因子 $\alpha$，並以 Poisson 近似預測最長 bucket chain 的期望長度
:::
---
## Problem F: Bitwise Operations and Advanced C Techniques
- [ ] Part 1: `is_power_of_2`、`roundup_pow_of_two` 與 SLUB 頁面配置
```c
/* include/linux/log2.h */
static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
return (n != 0 && ((n & (n - 1)) == 0));
}
/* 計算 >= x 的最小 2 的冪 */
static inline __attribute__((const))
unsigned long roundup_pow_of_two(unsigned long x)
{
return x == 1 ? 1 : 1UL << fls_long(x - 1);
/* fls_long: find last set bit，回傳位置 (從 1 算起)*/
}
```
SLUB allocator 在 `mm/slub.c` 中以此計算 slab 頁面數：
```c
/* mm/slub.c (節錄) */
static int calculate_order(unsigned int size)
{
unsigned int order = get_order(size); /* round up to power of 2 pages */
if (order > MAX_ORDER)
return -E2BIG;
/* ... */
return order;
}
```
回答以下：
* `n & (n - 1)` 清除 `n` 的最低有效位 (Least Significant Set Bit)。直覺解釋：`n - 1` 會將 `n` 最低的 1 位元清為 0，且其低位全變為 1；與 `n` AND 後，恰好消去這個 1 位元而保留其餘高位元
* `fls_long(x - 1)` 回傳 `x - 1` 的最高有效位位置 (1-indexed)；`1UL << fls_long(x - 1)` 即 $2^{\lfloor \log_2(x-1) \rfloor + 1}$，對 `x = 100` 結果為 __ F01 __
* 若 `x = 1`，`roundup_pow_of_two(1) = 1`，因為 `x == 1` 分支直接回傳 `1`；若不做此特殊處理，Linux 核心定義的 `fls_long(0)` 回傳 __ F02 __ (核心明確定義此行為；但若直接使用 GCC `__builtin_clzl(0)`，則屬於未定義行為)
* SLUB 以 `order = get_order(size)` 計算每個 slab 佔用的頁面數 ($2^{\text{order}}$ pages)。對 `size = 64` bytes，在 page = 4 KiB 系統中 `get_order(64)` 回傳 __ F03 __，即 SLUB 為此 cache 配置 1 頁 (4096 bytes)，內部碎片率為 __ F04 __
- [ ] Part 2: `GENMASK`、`BIT`、`BUILD_BUG_ON` 與 C99 未定義行為
```c
/* include/linux/bits.h */
#define BIT(nr) (UL(1) << (nr))
#define BIT_ULL(nr) (ULL(1) << (nr))
#define GENMASK(h, l) \
(GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
#define __GENMASK(h, l) \
(((~UL(0)) - (UL(1) << (l)) + 1) & \
((~UL(0)) >> (BITS_PER_LONG - 1 - (h))))
/* GENMASK_INPUT_CHECK 使用 BUILD_BUG_ON_ZERO 在編譯期檢查 l > h 和 h >= BITS_PER_LONG */
#define GENMASK_INPUT_CHECK(h, l) \
(BUILD_BUG_ON_ZERO((l) > (h)) + \
BUILD_BUG_ON_ZERO((h) >= BITS_PER_LONG))
```
回答以下：
* `BIT(n)` 使用 `UL(1)` (即 `1UL`) 而非 `1` 或 `1U`，是因為 C99 6.5.7 §3 規定：位移量 $\ge$ 被移值的型別寬度時行為未定義；`int` 寬度為 32，故 `BIT(32)` 若使用 `int` 即為 __ F05 __，而 `1UL << 32` 在 64-bit `unsigned long` 上合法。
* `GENMASK(7, 4)` 展開後結果為 __ F06 __ (十六進位)，對應 bit 4~7 的連續遮罩。
* `BUILD_BUG_ON_ZERO(e)` 展開為 `(sizeof(struct { int:(-!!(e)); }))` = 0 (條件：假) 或編譯錯誤 (條件：真)；`GENMASK_INPUT_CHECK` 若傳入 `h = 3, l = 5` (`l > h`) 將在編譯時期出錯
* `~UL(0)` 相較於字面值 `0xFFFFFFFFFFFFFFFF` 的優點是在 32/64-bit 平台上自動適應 `unsigned long` 的寬度，確保 `BITS_PER_LONG` 個位元全為 1
- [ ] Part 3: `INT_MIN` 的 C 規格 UB 與核心的安全算術
根據 C99 7.20.6.1 §2：「若 `abs` 或 `labs` 的結果無法表示，行為未定義 」(The behavior is undefined if the result cannot be represented)，因此 `abs(INT_MIN)` 本身是未定義行為，而非 implementation-defined。
```c
/* include/linux/overflow.h */
/* 安全的整數減法：計算 a - b，若溢位則回傳 true 並仍將截斷值存入 *d */
#define check_sub_overflow(a, b, d) __builtin_sub_overflow(a, b, d)
/* 安全的絕對值 (核心不直接使用 abs(INT_MIN))*/
static inline long abs_safe(long x)
{
return x < 0 ? (x == LONG_MIN ? LONG_MAX : -x) : x;
/* 注意：LONG_MIN 的 abs 無法精確表示，此處以 LONG_MAX 近似 */
}
```
回答以下：
* 在 32 位元二補數 (two's complement)中，`INT_MIN = -2^{31} = -2147483648`，`INT_MAX = 2^{31} - 1 = 2147483647`；$|INT\_MIN| - INT\_MAX =$ F07，說明有號整數範圍非對稱。
* 在「二個操作元同號但結果異號」時發生有號溢位 (signed overflow)。`check_sub_overflow(INT_MIN, 1, &d)` 回傳 __ F08 __ (true / false)，同時將 `d` 設為 __ F09 __ (截斷值)。
* `__builtin_sub_overflow(a, b, d)` 的行為保證：無論是否溢位，`*d` 均被設為 `(a - b)` 的數學結果模 `2^{sizeof(*d)*8}` 的值；這是 GCC 的保證，而非 C 標準所規定，C99 對有號溢位的規定是 __ F10 __。
* `abs(INT_MIN)` 按 C99 7.20.6.1 §2 屬於未定義行為；在 GCC `-O2` 下若開啟 `-fstrict-overflow`，編譯器可能假設 `x > 0` (因為 `x == INT_MIN` 走 abs 路徑是 UB)，從而刪除 `abs()` 呼叫
- [ ] Part 4: `time_after` 的模運算正確性分析
```c
/* include/linux/jiffies.h */
#define time_after(a, b) \
(typecheck(unsigned long, a) && \
typecheck(unsigned long, b) && \
((long)((b) - (a)) < 0))
/* 語意：time_after(a, b) 回傳 true 當且僅當 a 在時間上晚於 b */
/* 等效為：(long)(b - a) < 0，即 b 比 a 更早 (a 更新) */
```
> 數學基礎：C99 §6.2.5¶9 規定 `unsigned` 算術定義為模 $2^N$ 運算，對應代數結構 $\mathbb{Z}/2^N\mathbb{Z}$ (整數模 $2^N$ 的環)。此結構在加法下構成阿貝爾群 (Abelian group)，滿足封閉性、結合律、交換律、單位元 (0)及反元素 ($2^N - x$)；其關鍵性質為：即使計數器跨越 $2^N$ 邊界，兩點之間的差值 $(a - b) \bmod 2^N$ 仍保留正確的「距離」資訊。將此無號差值轉型為 `long` 後，若差值 $< 2^{N-1}$ 則最高有效位為 0 (正數，$b$ 在 $a$ 之後)；若差值 $\geq 2^{N-1}$ 則最高有效位為 1 (轉譯為負數，$a$ 在 $b$ 之後)。此機制在時間差 $|a - b| < 2^{N-1}$ 的條件下始終正確；一旦差值達到或超過 $2^{N-1}$ (32-bit jiffies 在 1000 HZ 下約 24.8 天)，符號位元翻轉，`time_after` 給出相反結論。
* `time_after(a, b)` 利用 `(long)((b) - (a)) < 0` 判斷「a 是否比 b 更晚」。首先 `(b) - (a)` 以 `unsigned long` 算術 (模 $2^{32}$ 或 $2^{64}$)，再轉型為 `long`；若結果為負，代表 a 在 b 之後
* 假設 32-bit jiffies，`a = 0x00000100`，`b = 0xFFFFFF00`：`b - a` (無號 32-bit 截斷)= __ F11 __ (十六進位)；轉型為 `long` (32-bit signed) 後為 __ F12 __ (正 / 負，填值)；因此 `time_after(a, b)` 回傳 __ F13 __ (true / false)，代表 a 晚於 b。
* `typecheck(unsigned long, a)` 的作用是：若傳入 `int` 型別的 `a` (負值會符號擴充)，在 64-bit 系統上 `(unsigned long)(int)-1 = 0xFFFFFFFFFFFFFFFF`，使 `time_after` 計算錯誤。`include/linux/typecheck.h` 中的 `typecheck` 展開為 `(void)(&__dummy == &__dummy2)` 的指標比較 (`__dummy` 宣告為 `type`，`__dummy2` 以 __ F14 __ 宣告)，若型別不匹配，編譯器發出 "comparison of distinct pointer types" 警告。
* `time_after` 正確性的嚴格邊界：設時間差 $\Delta T = |a - b|$，當 $\Delta T < 2^{N-1}$ (32-bit jiffies 在 1000 HZ 下約 24.8 天) 時，巨集結果正確；當 $\Delta T \geq 2^{N-1}$ 時，$(b - a) \bmod 2^N$ 的最高有效位元翻轉，`time_after` 給出相反的結論 (誤判 a 早於 b)。這是核心文件要求 timeout 差值不得超過 `MAX_JIFFY_OFFSET` (= `LONG_MAX / 2`) 的根本原因。
- [ ] Part 5: `READ_ONCE`、`WRITE_ONCE` 與 `smp_store_release` 的語意邊界
```c
/* include/linux/compiler.h */
#define READ_ONCE(x) \
({ union { typeof(x) __val; char __c[1]; } __u; \
__read_once_size(&(x), __u.__c, sizeof(x)); \
smp_read_barrier_depends(); __u.__val; })
#define WRITE_ONCE(x, val) \
({ union { typeof(x) __val; char __c[1]; } __u = \
{ .__val = (__force typeof(x)) (val) }; \
__write_once_size(&(x), __u.__c, sizeof(x)); \
__u.__val; })
/* include/asm-generic/barrier.h */
#define smp_store_release(p, v) \
do { smp_mb(); WRITE_ONCE(*p, v); } while (0)
#define smp_load_acquire(p) \
({ typeof(*p) ___p = READ_ONCE(*p); smp_mb(); ___p; })
```
回答以下：
* `READ_ONCE(x)` 透過 `union` + `__read_once_size` 的技巧，強制編譯器對 `x` 產生單次非可選讀取 (non-elided load)，防止 load hoisting 和 CSE 將多次讀取合併為一次。
* `smp_store_release(p, v)` 在 `WRITE_ONCE(*p, v)` 之前插入 `smp_mb()` (完整 memory barrier)，確保 `v` 被 store 之前，所有先前的 store 已對其他 CPU 可見；而 `WRITE_ONCE` 本身不提供此 CPU 間的 ordering 保證。
* Arm64 採用弱順序 (weakly-ordered) 記憶體模型，`smp_store_release` 必須發出 CPU memory barrier；`smp_mb()` 在 Arm64 上展開為 `dmb ish` 指令，其中 `ish` 指 inner shareable domain，確保 barrier 對同一 cluster 內所有 CPU 可見。相較之下，x86-64 的 TSO (Total Store Order)模型中 store 隱含 release 語意，`smp_store_release` 僅需 compiler barrier 而無需 CPU fence 指令。
* 下列核心程式碼說明典型使用情境：
```c
/* producer: 更新 buffer 後發布指標 */
smp_store_release(&shared_ptr, buffer); /* (A) 發布指標前確保 buffer 已寫入 */
/* consumer: 取得指標後讀取 buffer */
p = smp_load_acquire(&shared_ptr); /* (B) 取得指標後才讀 buffer */
if (p) use(p->data);
```
若將 (A) 改為 `WRITE_ONCE(&shared_ptr, buffer)` 而不加 `smp_mb()`，在 ARM64 上 consumer 可能看到 `shared_ptr` 已更新但 `buffer` 的內容尚未可見，此種 bug 稱為 memory ordering violation。
:::success
* `is_power_of_2(n)` 使用 `n & (n - 1) == 0` 的技巧。給出嚴格的數學證明：對所有正整數 $n$，$n \& (n-1) = 0$ 若且唯若 $n$ 為 2 的冪。在 Linux 核心中找出至少三個不同子系統利用 power-of-two 性質的情境 (如 SLUB、buddy allocator、ring buffer)，說明為何 power-of-two 對系統效能特別重要
* `GENMASK(h, l)` 的展開式使用 `~UL(0)` 而非字面值常數。從 C99 6.5.7 和 6.2.6.2 的角度，說明 `~UL(0)` 在 32-bit 和 64-bit 平台上的值差異，以及為何此寫>法比 `0xFFFFFFFF` 或 `0xFFFFFFFFFFFFFFFF` 更具可攜性。在 Linux 核心的 git log 找出因硬編碼位元遮罩導致跨平台 bug 的案例
* `time_after(a, b)` 的正確性依賴 $|a - b| < 2^{N-1}$ 的約束。在 32-bit jiffies 且 `HZ = 1000` 的配置下，$2^{31}$ 個 jiffies 對應約 24.8 天。說明以下情境:
* 為何 Linux 核心定義 `MAX_JIFFY_OFFSET` 限制最大 timeout？從 `include/linux/jiffies.h` 找出其定義
* 在 git log 找出因 jiffies 溢位導致的 bug，分析 64-bit jiffies (`jiffies_64`) 是否完全解決此問題
* 設計測試程式，在使用者空間模擬 `time_after` 在邊界條件 ($\Delta T = 2^{31} - 1$ 和 $\Delta T = 2^{31}$) 下的行為
* `abs(INT_MIN)` 依 C99 為 undefined behavior。在 Linux 核心中找出所有 `abs`、`labs`、`llabs` 的使用情境，分析是否存在傳入 `INT_MIN` 的風險。`include/linux/overflow.h` 的 `check_sub_overflow` 如何避免此問題？從 GCC 的 `__builtin_sub_overflow` 實作角度，說明其在 x86-64 和 Arm64 上展開的機器碼
* `READ_ONCE` 和 `WRITE_ONCE` 使用 `union` + `__read_once_size` 的技巧。從 C11 6.5.2.3 §3 (union member access，footnote 95 明確提及 type punning) 的角度，分析此技巧的合法性。在 Linux v6.x 的 git log 找出 `READ_ONCE`/`WRITE_ONCE` 的演進過程，說明從 `ACCESS_ONCE` 到 `READ_ONCE`/`WRITE_ONCE` 的變遷原因
:::
---
## Problem G: 比例分享排程與機率統計
- [ ] Part 1: EEVDF 公平性指標與虛擬時間
Linux v6.6 引入 EEVDF (Earliest Eligible Virtual Deadline First) 排程器，以下數學模型節錄自 `kernel/sched/fair.c`：
$$
\text{lag}_i(t) = w_i \cdot (V(t) - V(t_0)) - s_i(t_0, t)
$$
$$
V(d_i) = V(e_i) + \frac{r_i}{w_i}
$$
其中 $V(t)$ 為系統虛擬時鐘 ($dV/dt = 1/\sum_j w_j$)，$w_i$ 為 weight，$r_i$ 為 timeslice，$s_i$ 為實際已獲得 CPU 時間 (以虛擬時間單位計)。
```c
/* kernel/sched/fair.c */
struct sched_entity {
u64 vruntime; /* 虛擬執行時間 */
u64 deadline; /* V(d_i) = V(e_i) + slice / weight */
u64 slice; /* request length r_i */
s64 vlag; /* lag：正值表示服務不足 */
};
```
回答以下：
* $\text{lag}_i > 0$ 代表任務 $i$ 的實際 CPU 服務不足理想服務，EEVDF 應優先排程此類任務以恢復公平性 (fairness)
* EEVDF 從所有 eligible ($V(t) \geq V(e_i)$)任務中選擇 virtual deadline 最小的任務執行
* 若任務 weight 倍增 ($2w_i$)，相同 $r_i$ 下 virtual deadline 偏移量 $r_i/w_i$ 變為 $r_i / (2w_i)$，使高優先權任務的 deadline 更快到期
* 對 N 個 nice=0 ($w=1024$)任務，CFS vruntime delta 公式為 $\Delta t_\text{real} \times \text{NICE\_0\_LOAD} / w$；代入 `NICE_0_LOAD = w = 1024`，各任務 vruntime 增速等於 $\Delta t$ (真實時間 / 1/N 倍真實時間)
- [ ] Part 2: Little's Law 與排程延遲
Linux 傳統 CFS (v6.5 之前)排程期 (scheduling period)公式，作為 EEVDF (v6.6+，`sysctl_sched_base_slice`) 的背景知識，仍是理解 CPU 排程延遲的基礎：
$$
T_{\text{period}} = \max(\texttt{sched\_latency\_ns},\ N \times \texttt{sched\_min\_granularity\_ns})
$$
假設 `sched_latency_ns = 6 ms`，`sched_min_granularity_ns = 0.75 ms`。
Little's Law：$L = \lambda W$ ($L$ = 平均佇列長度，$\lambda$ = 到達率，$W$ = 平均等待時間)。
* 若 $\lambda = 80$ 任務/秒，每任務平均等待 $W = 25$ ms，則平均 run queue 長度 $L =$ __ G01 __
* $N = 8$ 個等權任務：$T_{\text{period}} = \max(6\ \text{ms},\ 8 \times 0.75\ \text{ms}) =$ __ G02 __ ms；每任務 quantum = __ G03 __ ms (十進位小數，小數點後二位)
* $N = 12 > 8$ 時 (超出固定 period 範圍)，$T_{\text{period}} =$ __ G04 __ ms，每任務固定 quantum = __ G05 __ ms (十進位小數，小數點後二位)
* 當 $N$ 在 $T_{\text{period}}$ 固定的範圍內 ($N \leq 8$)倍增時，每任務 quantum 與 $N$ 呈線性反比關係。
- [ ] Part 3: 機率分析——hash 碰撞與負載分布
在均勻雜湊 (uniform hashing) 假設下，$n$ 個鍵值分配至 $m$ 個 bucket：
* 特定 bucket 有 0 個鍵值的機率 $(1 - 1/m)^n$；當 $m = n \to \infty$ 時趨近 $e^{-1}$
* Poisson 近似下，$\alpha = n/m = 1$ 時 $P(k\ \text{entries}) = e^{-1} / k!$；$P(2) = e^{-1}/2! \approx$ __ G06 __ (四捨五入至三位有效數字)。
* 成功搜尋的期望比較次數 $= 1 + \alpha/2$ (含找到目標的 1 次成功比較)；$\alpha = 1$ 時為 __ G07 __。失敗搜尋需走訪整條 chain 而不命中，期望比較次數 $= \alpha =$ __ G08 __
* 在 $m = n$ 均勻雜湊下，最長 bucket chain 期望長度的漸進上界 ($m \to \infty$)為 $\Theta(\ln m / \ln \ln m)$
:::success
* EEVDF 的 $\text{lag}_i(t)$ 量化任務的公平性偏差。以三個任務 (weight 分別為 1024、512、2048) 為例，建立數學模型，計算在 100 ms 的排程視窗內各任務的理>想 CPU 時間、實際 CPU 時間和 lag 值。與 CFS 的 vruntime 機制相比，EEVDF 在哪些情境下能更快恢復公平性？
* Little's Law ($L = \lambda W$) 假設系統處於穩態 (steady state)。在 Linux CPU scheduler 的語境下，說明以下情境為何違反穩態假設：(a) 大量行程同時 fork>；(b) CPU hotplug 事件。從 `kernel/sched/` 的 git log 找出處理這些非穩態情境的機制
* 教材給出 hash 碰撞的 Poisson 近似。設計實驗程式，以 $n = m = 10^4$ 驗證：(a) 空 bucket 比例是否趨近 $e^{-1} \approx 0.368$；(b) 最長 chain 長度是否符合 $\Theta(\ln m / \ln \ln m)$ 的漸進上界。分別以 `hash_32` (golden ratio) 和簡單模運算 (`key % m`) 進行比較，繪製分布直方圖
* CFS 排程期公式 $T_{\text{period}} = \max(\texttt{sched\_latency\_ns}, N \times \texttt{sched\_min\_granularity\_ns})$ 在任務數極大時，每任務的 quantum 趨近 `sched_min_granularity_ns`。從 context switch 的成本角度，分析為何不能無限制地縮小 quantum。設計實驗測量不同 quantum 下的 context switch overhead (使用 `perf stat -e context-switches,task-clock`)，找出 quantum 與 throughput 的最佳平衡點
* 生日悖論指出 $n \approx 1.18\sqrt{m}$ 時碰撞機率達 50%。在 Linux 核心的 dentry cache (`fs/dcache.c`) 中，典型系統的 dentry hash table 有多少 bucket？從 `/proc/sys/fs/dentry-state` 讀取實際 dentry 數量，計算碰撞機率，並評估是否需要 resize
:::
---
## Problem H: 排序演算法數學分析
- [ ] Part 1: lib/sort.c Bottom-Up Heapsort
Linux 核心 `lib/sort.c` 實作 bottom-up heapsort (Wegener 1993 演算法)，相較標準 heapsort 降低平均比較次數：
```c
/* lib/sort.c — bottom-up heapsort */
static void sift_down(void *base, size_t root, size_t child, ...)
{
/*
* 1. 從 root 沿較小子節點路徑走到 leaf (不比較親代和子代節點)
* 2. 從 leaf 向上找正確插入位置 (bottom-up search)
* 3. Shift 值以維持 heap 性質
*/
}
```
比較次數分析 ($n$ 個元素)：
* 標準 heapsort sift-down：每層需 __ H01 __ 次比較 (選較小子節點 1 次 + 與親代節點比較 1 次)
* Bottom-up heapsort 平均：$n \log_2 n + 0.37n + o(n)$；最壞：$1.5 n \log_2 n + O(n)$
Bottom-up 最佳化的主體思路：先走完整條 leaf path (不比較)，再從 leaf 向上回溯找插入位置；由於實際插入點通常在靠近 leaf 的位置，回溯路徑短，因此節省比較次數。
* 對 $n = 1024 = 2^{10}$，平均比較次數 $\approx 1024 \times 10 + 0.37 \times 1024 =$ __ H02 __
* 核心 `lib/sort.c` 選用 heapsort 而非 quicksort，根本原因是 heapsort 最壞情況仍為 $O(n \log n)$，而 quicksort 最壞為 $O(n^2)$，在核心無法控制輸入的情境下不可接受。
* `lib/sort.c` 排序連續記憶體陣列；`lib/list_sort.c` 排序 `struct` __ H03 __ (結構體名稱)
- [ ] Part 2: Timsort Merge Invariants
Timsort 維護 pending stack (由底至頂依序為 $\ldots, C, B, A$，$A$ 在頂端為最新推入的 run)，須持續滿足：
* Invariant 1：$|C| > |B| + |A|$ (底部 run 長度大於其上兩個 run 之和)
* Invariant 2：$|B| > |A|$ (次頂 run 長度大於頂部 run)
這確保各 run 長度從頂到底至少以 Fibonacci 數列速度成長，保證 stack 深度 $O(\log N)$。
* 若 stack 頂端三 run 長度為 $[A=5, B=3, C=3]$ ($A$ 在頂)，哪些 invariant 被違反？二者違反
* Fibonacci 數列保證：若 $N = F_k$ (第 $k$ 個 Fibonacci 數)，則 stack 深度 $\leq k$；故 stack 深度的漸進上界為 $\log_\varphi N \approx 1.44 \log_2 N$
* Gallop mode 觸發條件：連續 __ H04 __ 次從同一 run 取出元素 (`MIN_GALLOP = 7`)，切換至指數搜尋以加速高預排序資料的合併。
* 合併長度 $M$ 與 $N$ 的有序串列：最壞情況 (完全交錯)需 $M + N - 1$ 次比較；最好情況 ($A$ 的所有元素均小於 $B[0]$，或反之) 需 $\min(M, N)$ 次比較。
- [ ] Part 3: list_sort 比較次數精確分析
`lib/list_sort.c` 的比較次數上界：
$$
C(n) = n\lceil \lg n \rceil - 2^{\lceil \lg n \rceil} + 1
$$
回答以下：
* $n = 8 = 2^3$：$C(8) = 8 \times 3 - 8 + 1 =$ __ H05 __
* $n = 9$：$\lceil \lg 9 \rceil = 4$，$C(9) = 9 \times 4 - 16 + 1 =$ __ H06 __
* 排序 $n = 8$ 個元素的資訊理論下界 (information-theoretic lower bound)：$\lceil \log_2(8!) \rceil = \lceil \log_2 40320 \rceil =$ __ H07 __ 次比較
* `list_sort` 對 $n = 8$ 的上界與資訊理論下界相差 __ H08 __ 次，說明此實作接近比較最優 (comparison-optimal)。
:::success
* `lib/sort.c` 的 bottom-up heapsort 先沿 leaf path 走到底再回溯。設計實驗，以 $n = 10^4, 10^5, 10^6$ 比較標準 heapsort 和 bottom-up heapsort 的實際比>較次數，驗證是否符合 $n \log_2 n + 0.37n$ 的理論預測。使用 perf 測量 branch miss rate，說明 bottom-up 策略對 branch predictor 的影響
* Timsort 的 merge invariant ($|C| > |B| + |A|$ 且 $|B| > |A|$) 確保 stack 深度為 $O(\log N)$。證明：若所有 invariant 皆滿足，stack 中 run 長度從頂到底至少以 Fibonacci 數列增長。當 invariant 被違反時，Timsort 選擇合併 $A$ 和 $B$ 還是 $B$ 和 $C$？說明此選擇如何影響合併的穩定性
* `list_sort` 的比較次數上界 $C(n) = n\lceil \lg n \rceil - 2^{\lceil \lg n \rceil} + 1$ 在 $n$ 恰好為 2 的冪時與 $n\lceil \lg n \rceil - n + 1$ 相同。推導此公式，並與 bottom-up merge sort 的上界 $n\lceil \lg n \rceil$ 比較，說明 `list_sort` 節省比較次數的數學原因。在 $n$ 略大於 2 的冪時 (如 $n = 2^k + 1$)，`list_sort` 的比較次數與標準 merge sort 的差距最大化，以數學推導說明原因
* Linux 核心為何同時維護 `lib/sort.c` (陣列 heapsort) 和 `lib/list_sort.c` (鏈結串列 merge sort) 兩套排序實作？從 cache locality、記憶體存取模式和最壞>情況保證的角度，分析在以下情境應選用哪一套：(a) 排序 `struct page` 陣列；(b) 排序 `struct dentry` 鏈結串列；(c) 排序 `struct inode` 需要 stable sort。>在 git log 找出選用 `list_sort` 而非 `sort` 的 commit，說明決策依據
* Gallop mode 在連續 `MIN_GALLOP = 7` 次從同一 run 取出元素後觸發。設計實驗，以不同程度的預排序輸入 (完全排序、90% 排序、50% 排序、完全隨機)，測量 gallop mode 的觸發頻率和合併效率。說明 gallop mode 使用指數搜尋 (binary search on exponentially growing range) 的時間複雜度，以及為何此策略對 nearly-sorted 資料特別有效
* 排序演算法的穩定性 (stability) 在核心中具有安全意涵。CVE-2023-1829 涉及 `tcindex` 分類器的 use-after-free，其根因之一是物件生命週期管理依賴特定走訪順序。建立數學模型：若排序不穩定導致相同鍵值的元素重排，在 $n$ 個元素中有 $k$ 組相同鍵值 (每組 $g_i$ 個)，不穩定排序可能產生多少種不同的輸出排列？以 $\prod_{i=1}^{k} g_i!$ 量化，說明此不確定性如何在核心的 RCU callback 排序或 timer wheel 排程中引發非確定性行為
:::
---
## Problem I: Linux 核心的數學基礎
- [ ] Part 1: 數論與模運算
Linux `lib/mpi/` 實作大數模運算，用於 RSA/DSA 等公鑰加密。
```c
/* lib/mpi/mpi-pow.c — modular exponentiation */
/* square-and-multiply：平均 1.5k 次模乘法 (k = 指數 bit 長度)*/
```
* Square-and-multiply 對 $k$ bits 指數：每個 bit 需 1 次 square，期望 $k/2$ 個 '1' bits 各需 1 次 multiply；平均共 __ I01 __ K 次模乘法。
* `GOLDEN_RATIO_32 = 0x61C88647` 為奇數，與 $2^{32}$ 的 $\gcd$ = __ I02 __ (互質)，確保乘法雜湊覆蓋全部 $2^{32}$ 個輸出值 (若為偶數則只覆蓋一半，見 Problem E Part 2)
* Miller-Rabin 質數測試 (Linux RSA 金鑰生成使用)的安全參數 $t$ 決定偽質數 (composite 被誤判為 prime)的機率上界 $4^{-t}$；$t = 40$ 時上界 = $2^{-80}$
- [ ] Part 2: 圖論——路由與 Trie
Linux 核心的 IP 路由以 trie 結構 (`net/ipv4/fib_trie.c`) 實作，Dijkstra 演算法則用於 OSPF 等動態路由協定的 SPF 樹計算。
```c
/* net/ipv4/fib_trie.c */
/* Patricia trie：每次查詢從 root 走至 leaf，深度 = prefix 位元長度 */
```
* IPv4 routing trie 的最壞查詢複雜度 $O(\mathtt{I03})$ (以 IP 位址 bit 長度表達)；IPv6 為 $O(128)$。
* Dijkstra 以 binary heap 實作 (如核心的 `lib/rbtree.c` 用於優先佇列語意)，對 $V$ 個節點、$E$ 條邊的圖 (graph)，時間複雜度為 $O((V + E) \log V)$
* FIB hash table (`net/ipv4/fib_hash.c` 舊實作) 在負載因子 $\alpha$ 下每次查詢期望時間 $O(1 + \alpha)$；Patricia trie 最壞 $O(W)$ ($W$ = key bits)。二者在低負載時 __ I04 __ (hash table vs. trie) 效能較好，因為常數因子更小且無 bit-by-bit 走訪。
- [ ] Part 3: 資訊理論與壓縮
Linux `lib/` 包含 LZO、LZ4、DEFLATE (LZ77 + Huffman) 等壓縮演算法。Shannon entropy：$H(X) = -\sum_i p_i \log_2 p_i$ bits。
* 均勻分布的 256 個符號 ($p_i = 1/256$ 各自)，Shannon entropy $= \log_2 256 =$ __ I05 __ bits (byte 最大熵)。
* 符號機率：'e' = 0.5，'a' = 0.25，'o' = 0.25；$H = -(0.5 \log_2 0.5 + 0.25 \log_2 0.25 + 0.25 \log_2 0.25) =$ __ I06 __ bits
* 最佳 Huffman 碼對上述分布：'e' 分配 __ I07 __ bit，'a'/'o' 各 __ I08 __ bits；期望碼長 = __ I09 __ bits，與 Shannon entropy 相等，因為所有機率均為 dyadic probabilities (二進位分割機率，即 $p_i = 2^{-k_i}$，$k_i$ 為非負整數)
* DEFLATE 的無失真壓縮理論下界由 Shannon entropy 給出；對完全隨機資料 ($H = 8$ bits/byte)，壓縮後大小不可能小於原始大小
- [ ] Part 4: 攤銷分析——SLUB Allocator
Linux SLUB allocator (`mm/slub.c`) 的 per-CPU freelist 使 object 分配達到攤銷 $O(1)$：
```c
/* mm/slub.c */
/*
* fast path: per-CPU freelist 非空 → O(1) pop
* slow path: 從 partial slab 補充 freelist → amortized O(1)
*/
```
回答以下：
使用 potential function $\Phi$ = freelist 中 free object 數：
* Fast path 分配：actual cost = 1，$\Delta\Phi = -1$，amortized cost $=$ __ I10 __
* Slow path (一次補充 $k$ 個 object)：actual cost = $O(k)$，$\Delta\Phi = +k$，amortized cost $= O(k) + k$；但均攤至每個 object 仍為 $O(\mathtt{I11})$。
* per-CPU freelist 設計 (每 CPU 持有獨立 freelist) 使 fast path 免於 spinlock 競爭，這是攤銷 $O(1)$ 在多核環境成立的關鍵假設
:::success
* Square-and-multiply 演算法的時間複雜度依賴指數中 '1' bits 的數量。從旁路攻擊 (side-channel attack) 的角度，說明為何簡單的 square-and-multiply 實作容易遭受 timing attack。Linux 核心的 `lib/mpi/mpi-pow.c` 如何以 constant-time 技巧防禦此攻擊？在 git log 找出相關的安全性改進 commit
* IPv4 routing 從 FIB hash table (`fib_hash.c`) 遷移至 Patricia trie (`fib_trie.c`)。從 git log 找出此遷移的關鍵 commit，分析遷移動機 (最壞情況查詢時間、記憶體使用、prefix 匹配能力)。設計實驗，以 $10^5$ 條路由規則比較 hash table 和 trie 在不同 prefix 長度分布下的查詢延遲
* Shannon entropy 給出無失真壓縮的理論下界。Linux 核心的 `lib/` 提供 LZO、LZ4、DEFLATE、ZSTD 等壓縮演算法。設計實驗，以 Linux 核心原始程式碼 (`vmlinux` 或 `initramfs`) 為輸入，測量各壓縮演算法的壓縮率、壓縮/解壓速度，並與 Shannon entropy 的理論下界比較。說明為何 `zram` (記憶體壓縮) 預設選用 LZO/LZ4 而非 DEFLATE
* SLUB allocator 的 per-CPU freelist 使 fast path 免於 spinlock 競爭。從攤銷分析的 potential function 出發，嚴格證明 SLUB 的 `kmalloc`/`kfree` 攤銷成本為 $O(1)$。在高競爭環境 (如 networking stack 的大量 `alloc_skb`)，per-CPU freelist 可能耗盡。分析 SLUB 的 slow path (從 partial slab 補充) 如何影響攤銷分析的假設，並在 git log 找出相關的效能改進
* Dijkstra 演算法在 Linux 核心中不直接使用，但 OSPF 路由協定的 SPF 計算依賴此演算法。從使用者空間的路由軟體 (如 FRRouting 的 `ospfd/ospf_spf.c` 或 BIRD) 原始程式碼找出 Dijkstra 的實作，分析其使用的優先佇列資料結構 (binary heap、Fibonacci heap 或其他)，並說明為何 Linux 核心偏好 binary heap 而非理論上更快的 Fibonacci heap
:::
---
## Problem J: Bitwise 運算、定點數與 C 標準違反導致的 CVE/CWE
- [ ] Part 1: 符號擴充陷阱與 CVE-2013-2094
C99 §6.3.1.3 §2 規定：將較大無號整數型別轉換為較小有號整數型別時，若值無法表示，結果屬於 implementation-defined behavior；但在實務上，x86-64 和 Arm64 均以截斷後再以二補數解讀的方式進行，若符號位元為 1，即發生符號擴充 (sign extension)。[CVE-2013-2094](https://nvd.nist.gov/vuln/detail/cve-2013-2094) 即是此類型別截斷與符號擴充在核心效能事件子系統造成的本機提權漏洞 (CWE-194: Unexpected Sign Extension)。
核心原始的弱點模式 (適度改寫自 `kernel/events/core.c`，v3.8 之前版本)：
```c
/* kernel/events/core.c (CVE-2013-2094 漏洞模式，已於 v3.8.9 修補) */
struct perf_event_attr {
__u64 config; /* 64 位元無號：攻擊者完全可控 */
/* ... */
};
static atomic_t perf_swevent_enabled[PERF_COUNT_SW_MAX]; /* 陣列大小 = 9 */
static int perf_swevent_init(struct perf_event *event)
{
/* 弱點：u64 截斷為 int (32-bit signed)，高 32 bits 直接丟棄 */
int event_id = event->attr.config; /* (A) 隱式截斷 */
if (event_id >= PERF_COUNT_SW_MAX) /* (B) 只檢查上界，未檢查 < 0 */
return -ENOENT;
/* (C) 以負索引存取全域陣列，觸發越界寫入 */
atomic_inc(&perf_swevent_enabled[event_id]);
return 0;
}
```
* `event->attr.config` 的型別為 `__u64`，在 (A) 隱式截斷為 `int` 後，若攻擊者傳入 `0x00000000FFFFFFFF`，`event_id` 的十進位值為 __ J01 __，因為低 32 bits `0xFFFFFFFF` 以二補數解讀為有號 32 位元整數
* (B) 的邊界檢查 `event_id >= PERF_COUNT_SW_MAX`，當 `event_id = -1` 時，檢查結果為 __ J02 __ (true / false)；根據有號整數比較規則說明原因
* 在 \(C) 執行 `&perf_swevent_enabled[event_id]` 時，依 C99 §6.5.6 §8，指標算術以 `ptrdiff_t` 單位計算。`int event_id = -1` 在轉型為 `ptrdiff_t` 時發生符號擴充 (sign extension)，使偏移量變為 __ J03 __ (十六進位，64 位元)；陣列元素大小 `sizeof(atomic_t) = 4` bytes，因此實際存取位址比陣列起始位址低 __ J04 __ bytes
* 修補方式是在 (A) 之後加入 `if (event_id < 0) return -EINVAL;` 或將 `event_id` 的宣告型別改為 __ J05 __ (填標準 C 關鍵字，使 `0xFFFFFFFF` 被解讀為 `4294967295` 而非 `-1`)，使負數在邊界檢查中被正確攔截
* 此弱點對應 CWE-__ J06 __ (Unexpected Sign Extension)，CVSS v3 評分中的 Attack Vector 為 Local，因為攻擊者需要能呼叫 `perf_event_open(2)` 系統呼叫
- [ ] Part 2: TCP Cubic 定點數運算與溢位防護
Linux 核心 `net/ipv4/tcp_cubic.c` 實作 Cubic 壅塞控制演算法，以定點數 (fixed-point arithmetic) 計算 $W_{cubic}(t) = C \cdot (t - K)^3 + W_{max}$，避免核心中使用浮點運算：
```c
/* net/ipv4/tcp_cubic.c */
#define BICTCP_BETA_SCALE 1024 /* beta 的縮放因子，= 2^10 */
#define BICTCP_HZ 10 /* 時間單位：1/2^10 秒 */
/* 全域可調整參數 (sysctl) */
static int beta __read_mostly = 717; /* 乘法減少因子：717/1024 ≈ 0.70 */
/* cube_factor：預先計算以避免執行期除法 */
static u64 cube_factor __read_mostly;
void bictcp_init(void)
{
/* 1ull 確保以 u64 執行位移，避免 1 << 40 的未定義行為 */
cube_factor = 1ull << (10 + 3 * BICTCP_HZ); /* (A) = 1 << 40 */
do_div(cube_factor, bic_scale * 10);
}
static void bictcp_update(struct bictcp *ca, u32 cwnd, u32 acked)
{
u64 offs, t;
/* ... */
/* t：自上次壅塞以來的 BICTCP_HZ 單位時間 */
t = ...;
/* (B) 三次方計算，必須以 u64 避免 u32 溢位 */
offs = (u64)t * t * t;
/* 乘法減少壅塞視窗 */
u32 new_cwnd = max((cwnd * beta) / BICTCP_BETA_SCALE, 2U); /* \(C) */
}
```
* (A) 中 `1ull << (10 + 3 * BICTCP_HZ)` = `1ull << 40`；若寫成 `1 << 40` 且 `int` 為 32 位元，依 C99 §6.5.7 §3，位移量 ≥ 型別寬度，屬於 __ J07 __，GCC 在 `-O2` 下可能產生任意值。`ull` 字尾確保型別為 `unsigned long long` (至少 64 位元)
* (B) 中若 `t` 為 `u32`，未加強制轉型的 `t * t * t` 依 C99 §6.3.1.8 (Usual Arithmetic Conversions) 結果型別為 __ J08 __，當 `t` 稍大即發生無號整數繞回 (wrap-around)，使 `offs` 計算錯誤；加 `(u64)t` 後第一個乘法提升為 u64，後續乘法亦自動保持 u64
* \(C) 中 `cwnd * beta` 的中間值若 `cwnd` 接近 `u32` 最大值：`beta` 最大為 `BICTCP_BETA_SCALE = 1024`，在 32 位元算術不發生溢位的前提下，`cwnd` 的最大安全值為 __ J09 __ (十進位，取 $\lfloor (2^{32}-1) / 1024 \rfloor$)
* `BICTCP_BETA_SCALE = 1024 = 2^{10}`，因此 \(C) 中除以 `BICTCP_BETA_SCALE` 可替換為右移 __ J10 __ 位元，但核心程式保留除法以增加可讀性
* `beta = 717` 對應的實際乘法因子為 $717 / 1024 \approx$ __ J11 __ (保留四位有效數字)，代表發生壅塞後 cwnd 縮小至原來的此比例；TCP Cubic 論文建議 $\beta = 0.7$，$0.7 \times 1024 = 716.8$，四捨五入後即為 $717$
- [ ] Part 3: `__ffs`、`cpumask` 與 IRQ affinity 的位元操作
Linux `include/linux/cpumask.h` 與 `include/asm-generic/bitops/builtin-__ffs.h` 以 GCC 內建函式操作 CPU 遮罩，用於 IRQ affinity 設定和 CPU hotplug 路徑：
```c
/* include/asm-generic/bitops/builtin-__ffs.h */
static __always_inline unsigned long __ffs(unsigned long word)
{
return __builtin_ctzl(word); /* count trailing zeros：找到 LSB 位置 */
}
/* include/linux/cpumask.h */
static inline unsigned int cpumask_first(const struct cpumask *srcp)
{
return find_first_bit(cpumask_bits(srcp), nr_cpumask_bits);
}
/* kernel/irq/affinity.c */
static void irq_build_affinity_masks(unsigned int startvec, ...)
{
unsigned long mask = 0xB0; /* CPU 4、5、7 可用 */
/* 找到最低位的可用 CPU */
unsigned int cpu = __ffs(mask); /* (A) */
/* 清除 LSB，以便下次迭代找到下一個 CPU */
mask &= mask - 1; /* (B) */
}
```
* `0xB0` 的二進位為 `0b10110000`；`__builtin_ctzl(0xB0)` 計算 trailing zeros 個數，回傳 __ J12 __ (十進位)，對應 CPU __ J13 __ (十進位，即 IRQ 將分配至的 CPU 編號)
* (B) `mask &= mask - 1` 是清除 LSB 的慣用手法；`0xB0 - 1 = 0xAF = 0b10101111`，與 `0xB0` AND 後得 __ J14 __ (十六進位)，即清除 CPU 4 後剩餘 CPU 5、7
* 若要「僅保留 LSB (即從 `0xB0` 得到 `0x10`)」，應使用 C 語言運算式 `mask & __ J15 __` (填寫含 `mask` 的最短 C 運算式)。
* 在 Arm64 (AArch64) 架構下，GCC/Clang 展開 `__builtin_ctzl(word)` 時，通常先執行 `rbit` 指令反轉所有位元，再執行 __ J16 __ 指令 (填 Arm64 組合語言助憶子) 計算前導零，二者合稱 `__ffs` 的 Arm64 lowering sequence。
* 以 $n = 256$ 個 CPU 的系統為例 (64 位元平台，每個 `unsigned long` 容納 64 bits)，`cpumask_t` 共佔 __ J17 __ 個 `unsigned long`；`find_first_bit` 最壞情況需逐一走訪全部 word，每個 word 以 `__builtin_ctzl` 或比較是否為零判斷是否繼續。
:::success
* CVE-2013-2094 的根本成因是 `u64` 到 `int` 的隱式截斷。從 C99 §6.3.1.3 和 CWE-194 (Unexpected Sign Extension) 的角度，設計一個靜態分析規則，能自動偵測 Linux 核心中所有從無號 64-bit 型別截斷為有號 32-bit 型別的隱式轉換。在 git log 找出至少三個類似的截斷漏洞，分析其修補策略
* TCP Cubic 以定點數避免核心中的浮點運算。從 `net/ipv4/tcp_cubic.c` 的完整原始程式碼出發，追蹤 `bictcp_update` 中三次方計算的完整定點數路徑。建立數學模型，分析在 `cwnd` 接近 $2^{16}$ 時，定點數截斷誤差如何影響壅塞視窗的收斂行為。與 TCP BBR 的壅塞控制策略比較，說明為何 BBR 選擇不同的數值計算方式
* `__ffs` 在 Arm64 上展開為 `rbit` + `clz` 兩道指令。從 ISA 手冊查閱這兩道指令的延遲和吞吐量 (以 Cortex-A76 或 Cortex-X4 為例)。在 x86-64 上，GCC 展開 `__builtin_ctzl` 為 `bsf` 或 `tzcnt` 指令。比較二個架構的 `__ffs` 實作效能，並說明為何 `tzcnt` (BMI1 extension) 優於 `bsf` (後者在輸入為 0 時行為未定義)
* `cpumask` 操作是 Linux 核心中 IRQ affinity 和 CPU hotplug 的基礎。設計實驗，以 `sched_setaffinity(2)` 將行程繫結至不同 CPU 組合，使用 `perf stat` 測>量 context switch 和 cache miss 的變化。說明在 NUMA 架構下，IRQ affinity 設定如何影響網路封包處理的延遲 (提示：`irqbalance` 和 `/proc/irq/*/smp_affinity`)
* C99 §6.5.7 §3 規定位移量超過型別寬度時為 undefined behavior。在 Linux 核心的 git log 找出因位移量越界而導致 bug 的案例。`BIT(nr)` 使用 `1UL` 而非 `1`，但在 32-bit 平台上 `BIT(32)` 對 `unsigned long` (32-bit) 仍為 UB。分析 `BIT_ULL(nr)` 如何解決此問題，以及核心中 `BITS_PER_LONG` 檢查的必要性
* `find_first_bit` 在 $n$ 個 CPU 的系統中，`cpumask_t` 佔 $\lceil n/64 \rceil$ 個 word (64-bit 平台)。建立數學模型：若系統有 $n$ 個 CPU 且有 $k$ 個 CPU 在線 (均勻隨機分布)，`find_first_bit` 的期望掃描 word 數為何？推導封閉式 $E[\text{words}] = \lceil n/64 \rceil \cdot (1 - (1 - 64/n)^k)$ 是否成立，並>以 $n = 256, k = 8$ 代入驗證。在 NUMA 系統中，`cpumask_next_and` 的效能與 CPU topology 的關聯為何？從 git log 找出 CVE-2022-1012 (隨機化 port 選擇中的 CPU affinity 弱點) 等案例，分析 cpumask 操作的安全性意涵
:::
---
## Problem K: EWMA 定點數實作與 PELT 排程負載追蹤
- [ ] Part 1: 定點數 EWMA：整數位元移位逼近浮點衰減
EWMA 公式 $S_n = (1 - \alpha) S_{n-1} + \alpha x_n$，限制 $\alpha = 1/W$ ($W = 2^w$)，令 `internal = S × 2^p`，推導後得整數更新式：
$$
\text{internal}_\text{new} = ((\text{internal}_\text{old} \ll w) - \text{internal}_\text{old} + (x \ll p)) \gg w
$$
`lib/average.c` 的 `ewma_add()` (`avg->factor` = $p$，`avg->weight` = $w$)：
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((__K01__ << avg->weight) - avg->internal +
(val << avg->factor)) >> __K02__)
: (val << avg->factor);
return avg;
}
```
* `K01` = __ K01 __；`K02` = __ K02 __ (均填 C 語言運算式)。
* `avg->weight = 3` ($\alpha = 1/8$，$W = 8$) 時，`(internal << 3) - internal` 數學上等效於 `internal * __ K03 __` (填十進位整數，即 $2^w - 1$)。
* 省略 `avg->internal == 0` 特判時，代入公式得 $I_\text{new} = \text{val} \times 2^p / 2^w$，即第一筆 `internal` = `val << (avg->factor - __ K04 __)` (填 C 語言運算式)，第一筆資料被衰減因子折扣，造成暖機偏差
* 以 $p = 10$，$w = 3$ 代入：`ewma_add()` 中 `>> w` 的每步最大截斷誤差為 __ K05 __ (十進位小數，小數點後 5 位，由 $(2^w - 1)/2^p$ 計算)；`ewma_read()` 中 `>> p` 的讀回誤差最大嚴格小於 __ K06 __ (整數，輸入值單位)
- [ ] Part 2: `DECLARE_EWMA` 展開：編譯期常數取代執行期欄位讀取
`DECLARE_EWMA(rssi, 10, 8)` 展開後，核心更新邏輯等效於：
```c
static inline void ewma_rssi_add(struct ewma_rssi *e, unsigned long val)
{
unsigned long internal = READ_ONCE(e->internal);
unsigned long w = ilog2(__K07__); /* w = __K08__ */
WRITE_ONCE(e->internal,
internal
? (((internal << w) - internal + (val << __K09__)) >> w)
: (val << __K09__));
}
static inline unsigned long ewma_rssi_read(const struct ewma_rssi *e)
{
return e->internal >> __K10__;
}
```
* `K07` = __ K07 __ (`_weight_rcp` 的值，即衰減權重的倒數)；`K08` = __ K08 __ (`ilog2` 的運算結果)；`K09` = `K10` = __ K09 __ (`_precision` 的值)。
* 相較 `lib/average.c` 的 `struct ewma`，`DECLARE_EWMA` 將 `factor` 與 `weight` 改為編譯期常數，讓編譯器以固定移位量替代執行期欄位讀取；每次 `ewma_rssi_add()` 呼叫節省讀取 __ K11 __ (整數) 個結構體欄位的開銷
* `ath9k` Wi-Fi 驅動以此設定追蹤 RSSI，典型讀值範圍 $[0, 100]$ (無符號整數)。穩態下 `internal` 的最大值為 __ K12 __ (整數，即 `max_val << _precision`)
* 核心以 `BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp)` 強制 `_weight_rcp` 必須為 2 的冪，底層判斷式為 `n & (n - 1) == 0`。以 `_weight_rcp = 8` 代入：`8 & (8 - 1)` = `8 & 7` = __ K13 __ (填十六進位整數)，確認為 2 的冪，除以 $W = 8$ 可安全改寫為 `>> 3`
- [ ] Part 3: 精度與溢位工程分析
在 32 位元平台 (`unsigned long` = 32 bits)，以 EWMA 追蹤最大輸入值 $10^6$ 的感測器讀值：
* `internal` 穩態上限 $= 10^6 \times 2^p$；需滿足 $10^6 \times 2^p < 2^{32}$，`_precision` 最大可設為 __ K14 __ (整數，由 $\lfloor \log_2(2^{32}/10^6) \rfloor$ 取整)。
* 以 `_weight_rcp = 8` ($w = 3$)代入：`ewma_add()` 中間項 `internal << w` 使上限再乘以 $2^3$；此額外限制使 `_precision` 安全上限收緊至 __ K15 __ (整數，由 $10^6 \times 2^{p+3} < 2^{32}$ 推導)。
* 若改在 64 位元平台，輸入範圍 $[0, 10^6]$，要求每個 LSB 對應真實值不超過 $2^{-10}$ (即 `internal` 每單位代表約 $1/1024$)，`_precision` 最小值為 __ K16 __ (整數)。
- [ ] Part 4: PELT 週期碎片補償與定點衰減
Linux PELT (Per-Entity Load Tracking) 以 1024 微秒為一個排程週期，以下迴圈累計完整週期數 (仿 Kahan summation 的進位補償，確保不丟失碎片時間)：
```c
u32 periods_passed = 0;
u32 period_contrib = 0; /* 上輪未滿一個週期的餘量 */
for (int i = 0; i < N; ++i) {
u32 delta = deltas[i] + __K17__; /* 加入上輪餘量 */
periods_passed += delta / __K18__; /* 提取完整週期數 */
period_contrib = delta % __K19__; /* 保留本輪不足一週期的餘量 */
}
```
* `K17` = __ K17 __ (填 C 語言運算式)；`K18` = `K19` = __ K18 __ (填整數，一個週期的微秒數)。
* 此迴圈的不變式：每次迭代後，`1024 * periods_passed + period_contrib` 等於已處理的所有 `deltas[0..i]` 之總和 (恆等式成立與否以整數 __ K20 __ 表示，1 = 成立)。
* 若 `deltas[i]` 全為 1 微秒，且 $N = 2048$，迴圈結束後 `periods_passed = __ K21 __` (整數)。
* PELT 預設半衰期 $t_{1/2} = 32$ ms，$\tau = t_{1/2}/\ln 2 \approx 46.16$ ms，$\Delta t = 1$ ms 時 $k = e^{-\Delta t/\tau}$；每輪更新納入的即時使用率比例 $1 - k \approx$ __ K22 __% (保留一位小數)
* PELT 的 $k \approx 0.9785$ 不等於 2 的冪的倒數，無法直接以 `DECLARE_EWMA` 的整數位移逼近；核心改以 `runnable_avg_yN_inv[]` 查表近似 $k^n$，表中存放 $\lfloor 2^{32} \cdot k^n \rfloor$，乘積除以 $2^{32}$ 的運算以右移 __ K23 __ 位元 (填整數) 來取代除法
:::success
* EWMA 的暖機偏差 (warm-up bias) 來自第一筆資料未以完整權重納入。在 Linux 核心的 `DECLARE_EWMA` 實作中，`avg->internal == 0` 時直接設定 `val << factor` 以消除此偏差。從數學角度，推導在不使用此特判的情況下，前 $k$ 筆資料的 EWMA 值與真實平均值的偏差公式。在 Wi-Fi 驅動程式 (`ath9k`、`iwlwifi`) 的使用情境中，此暖機偏差對 RSSI 追蹤的實際影響為何？
* `DECLARE_EWMA` 強制 `_weight_rcp` 為 2 的冪，使除法可替換為右移。但 PELT 的衰減因子 $k \approx 0.9785$ 不是 2 的冪的倒數。從 `kernel/sched/pelt.c` 的原始程式碼出發，分析 `runnable_avg_yN_inv[]` 查表的完整計算路徑：如何預先計算 $\lfloor 2^{32} \cdot k^n \rfloor$、如何以 `mul_u64_u32_shr` 實現定點數乘法、以及查表與直接計算的精度差異。建立數學模型分析累積誤差
* PELT 以 1024 微秒為一個排程週期，使用進位補償 (類似 Kahan summation) 避免碎片時間丟失。從數值分析的角度，說明為何簡單的 `periods_passed += delta / 1024` 在累積大量短 delta 時會產生系統性截斷誤差。設計實驗：以 $10^6$ 個 `delta = 1` 微秒的輸入，比較有進位補償和無進位補償的累計週期數差異
* 在 32 位元平台上，EWMA 的 `internal` 值受限於 `unsigned long` 的 32-bit 範圍。教材推導出 `_precision` 的安全上限。設計一個完整的溢位分析框架：給定輸>入範圍 $[0, V_{max}]$、`_weight_rcp = W`、平台位寬 $B$，推導 `_precision` 的安全上限公式。以此框架驗證 Linux 核心中 `DECLARE_EWMA` 的所有使用情境 (搜尋核心原始程式碼) 是否皆滿足溢位安全條件
* PELT 的半衰期設定為 32 ms。從 CPU 排程的角度，分析此半衰期的選擇如何影響：(a) 短暫 burst 工作負載的負載追蹤靈敏度；(b) 穩定工作負載的負載估計穩定性。在 `kernel/sched/pelt.c` 的 git log 找出調整半衰期或衰減參數的 commit，說明其動機與效能影響。若要將半衰期從 32 ms 改為 16 ms，`runnable_avg_yN_inv[]` 表需要如何重新計算？
:::
參考題解：
:::spoiler
* A01: ==20==
* A02: ==8==
* A03: ==4==
* A04: ==`int (*)[5]`==
* A05: ==20==
* A06: ==4==
* A07: ==4==
* A08: ==16==
* A09: ==3==
* A10: ==undefined behavior==
* A11: ==`SSIZE_MAX`==
* A12: ==8==
* A13: ==lvalue==
* A14: ==strict aliasing==
* A15: ==character type== (`char`, `signed char`, or `unsigned char`)
* B01: ==`&(*pp)->next`==
* B02: ==undefined behavior==
* B03: ==`&h->first`==
* B04: ==`&h->first`==
* B05: ==`&tail->next`==
* B06: ==`&prev->next`==
* B07: ==4==
* C01: ==`head->prev`==
* C02: ==`&head`==
* C03: ==1==
* C04: ==`list_next_entry(pos,list)`==
* C05: ==`head`==
* C06: ==n==
* C07: ==`hlist`==
* C08: ==LSB==
* C09: ==1==
* D01: ==1024==
* D02: ==10==
* D03: ==leftmost==
* D04: ==0.8==
* D05: ==1.25==
* D06: ==1024==
* D07: ==64==
* D08: ==`shift`==
* D09: ==`0x0000FF00`==
* D10: ==`0x00F00000`==
* D11: ==`(preempt_count()&NMI_MASK)`==
* D12: ==512==
* D13: ==`0x00020000`==
* E01: ==8==
* E02: ==`&h->first`==
* E03: ==`&prev->next`==
* E04: ==$O(1)$==
* E05: ==20==
* E06: ==`0x61C88647`==
* E07: ==1==
* E08: ==26==
* E09: ==16==
* E10: ==0==
* E11: ==1.5==
* E12: ==0.5==
* E13: ==10==
* F01: ==128==
* F02: ==0==
* F03: ==0==
* F04: ==0%==
* F05: ==undefined behavior==
* F06: ==`0xF0`==
* F07: ==1==
* F08: ==true==
* F09: ==`INT_MAX`==
* F10: ==undefined behavior==
* F11: ==`0xFFFFFE00`==
* F12: ==-512==
* F13: ==true==
* F14: ==`typeof(a)`==
* G01: ==2==
* G02: ==6==
* G03: ==0.75==
* G04: ==9==
* G05: ==0.75==
* G06: ==0.184==
* G07: ==1.5==
* G08: ==1==
* H01: ==2==
* H02: ==10619==
* H03: ==`list_head`==
* H04: ==7==
* H05: ==17==
* H06: ==21==
* H07: ==16==
* H08: ==1==
* I01: ==$1.5$==
* I02: ==1==
* I03: ==32==
* I04: ==hash table==
* I05: ==8==
* I06: ==1.5==
* I07: ==1==
* I08: ==2==
* I09: ==1.5==
* I10: ==0==
* I11: ==1==
* J01: ==-1==
* J02: ==false==
* J03: ==`0xFFFFFFFFFFFFFFFF`==
* J04: ==4==
* J05: ==`unsigned int`==
* J06: ==194==
* J07: ==undefined behavior==
* J08: ==`u32`==
* J09: ==4194303==
* J10: ==10==
* J11: ==0.7002==
* J12: ==4==
* J13: ==4==
* J14: ==`0xA0`==
* J15: ==-mask==
* J16: ==`clz`==
* J17: ==4==
* K01: ==`avg->internal`==
* K02: ==`avg->weight`==
* K03: ==7==
* K04: ==`avg->weight`==
* K05: ==0.00684==
* K06: ==1==
* K07: ==8==
* K08: ==3==
* K09: ==10==
* K10: ==10==
* K11: ==2==
* K12: ==102400==
* K13: ==0==
* K14: ==12==
* K15: ==9==
* K16: ==10==
* K17: ==`period_contrib`==
* K18: ==1024==
* K19: ==1024==
* K20: ==1==
* K21: ==2==
* K22: ==2.1==
* K23: ==32==
:::
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet