--- # System prepended metadata title: 2026q1 Homework2 (stdc) --- # 2026q1 Homework2 (stdc) contributed by < Kally1206 > {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 思索〈[分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT)〉 * 設計實驗並在 GNU/Linux 比較文中二個演算法的 cache 行為。 * 如何在 Linux 上建立長度可控制的鏈結串列（例如 $10^4$、$10^6$、$10^8$）？ * 如何避免節點在記憶體中連續配置（例如使用 `malloc` + 隨機排列）？ * 如何使用 [perf stat](https://hackmd.io/@sysprog/linux-perf) 測量： `perf stat -e cache-references,cache-misses,cycles,instructions` * 思考 cache miss rate 是否隨 linked list 長度增加而擴大？ * 如何觀察 temporal locality？ * 如何使用 `perf record` + `perf report` 分析 memory access pattern？ * 是否可以利用 `perf c2c` 分析 cache line 使用？ * 在 Linux 核心程式碼中，有哪些 commit 明確提到 cache locality，並類似本文的方式提出改進？(提示: slab, rbtree, runqueue) * Linux 核心存在大量 linked list traversal，是否有對應的 commit 改進節點走訪的效率？請探討並提出自己的改進方案 (之後可貢獻回 Linux 核心) * 如何建立數學模型來預測 traversal latency？例如 $T = N \times (L_{mem} + L_{miss})$，其中 $L_{mem}$ = memory latency 和 $L_{miss}$ = cache miss penalty，當建立理想模型後，對照上述的 perf 結果並進行分析 ## 細讀〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉 * 教材以 `0.1 + 0.2 ≠ 0.3` 作為引言，說明電腦的數值表示問題，援引 IEEE 754 規格和你在電腦上的實驗，充分回答以下: * 為何十進位的 `0.1` 無法在二進位浮點數中精確表示？用 Graphviz 或類似的向量繪圖表示法，清晰展現數值表示的過程和限制。 A: 十進位的小數要能被二進位精確表示，其分母必須是 2 的冪次方。$0.1$ 轉換為二進位時：$0.1 \times 2 = 0.2 \dots 0$ $0.2 \times 2 = 0.4 \dots 0$ $0.4 \times 2 = 0.8 \dots 0$ $0.8 \times 2 = 1.6 \dots 1$ $0.6 \times 2 = 1.2 \dots 1$ $0.2 \times 2 = 0.4 \dots 0$ 形成無限循環小數，故必須在某個位數進行捨入，這就是誤差的來源。 * IEEE-754 單精度或雙精度為例，說明 sign, exponent, mantissa 在表示 `0.1` 時會發生什麼情況。 A: 以 64-bit Double 為例，將 $0.000110011...$ 寫成科學記號 $\Rightarrow 1.100110011... \times 2^{-4}$。轉為二進位為 01111111011。Mantissa 取小數點後的位數，並在第 52 位後根據捨入規則處理。最後存儲的值實際上比 $0.1$ 稍微大了一點點，精確值約為 $0.10000000000000000555...$。計算 0.1 + 0.2 時兩者的誤差會累積，導致結果 $0.30000000000000004$，而不等於精確的 $0.3$。 * 文中指出浮點數加法不具有結合律，從 Linux 核心的原始程式碼 (事實上使用定點數，但具備浮點數運算的特性) git log 找出對應的浮點數運算考量並充分討論 A: 在浮點數運算中由於每次加法都會進行一次捨入，運算順序會改變最終結果。Linux 核心原始碼中極少直接使用浮點數，主要原因有二：進入核心模式時，為了效率，核心不會自動保存 FPU 的暫存器。若要使用，必須手動呼叫 kernel_fpu_begin()，這會增加額外開銷;核心需要精確且可預測的結果，浮點數的捨入是不可接受的。Linux 核心常使用定點數來模擬浮點運算。例如在計算負載平衡或頻寬限制時。我們可以從 Git 歷史中找到關於數值精確度的討論。例如在 kernel/sched/loadavg.c 中，關於 Exponential Moving Average 的計算： ```c /* * Fixed-point arithmetic: * fraction bits = 11 * 1.0 = 2048 */ #define FSHIFT 11 /* nr of bits of precision */ #define FIXED_1 (1<> 1)$ 可避免 overflow A: 原因：若 $x$ 與 $y$ 皆為較大的正整數，x + y 會立即產生溢位，導致結果變為負數或錯誤數值。$(x \mathbin{\&} y) + ((x \oplus y) \gg 1)$。$x \mathbin{\&} y$ 是計算兩數共同擁有的「1」（即「進位部分」的一半），而 $(x \oplus y) \gg 1$ 是處理兩數中只有一方為「1」的位元（即「非進位部分」的一半）。兩者相加絕不會超過 $x$ 或 $y$ 的範圍，有效避免溢位。 * 在 Linux 核心中，為何這類 bit-level reasoning 對於效能與正確性非常重要？在 git log 找出對應的改進和修正 A: 在 lib/average.c 或處理定點數運算時，這種寫法能確保核心在處理高負載數據時不會因溢位導致排程錯誤。 * `x & (x - 1)` 可用來檢測什麼數值性質？給出數學推導，說明為何此技巧成立。Linux 核心中有哪些場景會利用 power-of-two (2 的冪，[不是「冪次」](https://hackmd.io/@sysprog/it-vocabulary)) 性質？為何 power-of-two 對於系統效能特別重要？ A: 這是一個極其高效的技巧，用於檢測 $x$ 是否為 2 的冪。若 $x = 2^k$，其二進位表示為一個 1 後面跟著 $k$ 個 0（如 $1000_2$）。則 $x - 1$ 的二進位表示為 $0$ 後面跟著 $k$ 個 1（如 $0111_2$），$(1000 \mathbin{\&} 0111) = 0$。若 $x$ 不是 2 的冪，則減 1 後最右邊的 1 之後的位元會翻轉，但更左邊的 1 依然存在，& 運算結果不為 0。Linux 的 Page 大小通常是 $4$ KB ($2^{12}$)，記憶體要求對齊。kfifo 實作中，緩衝區大小必須是 2 的冪，這樣可以用 index & (size - 1) 取代昂貴的取模運算 % size。CPU 執行位元運算只需 1 個週期，而整數除法/取模運算可能需要數十個週期。 * `((X) - 0x01010101) & ~(X) & 0x80808080` 技巧可用於 `strlen()` 的實作，回答： * 該巨集偵測的是什麼資料？為何該運算可一次檢測 4 個位元組？為何這比逐 byte 檢查更有效率？ A: 巨集 ((X) - 0x01010101) & ~(X) & 0x80808080 被稱為 Hacker's Delight 技巧。偵測一個 32 位元字組（Word）中是否存在 Null Byte (0x00)。 (X) - 0x01010101：如果某個 byte 是 0，減去 1 會導致該 byte 向高位借位，使該 byte 變為 0xFF。 & ~(X)：過濾掉原本就很大的數值（防止誤判）。 & 0x80808080：檢查每個 byte 的最高位（MSB）。若結果不為 0，代表該 Word 中至少有一個 byte 為 0。一次檢查 4 或 8 bytes（64-bit），減少了迴圈次數與分支預測（Branch Prediction）的負擔。 * 在 Linux 核心原始程式碼中找出類似 word-at-a-time 手法的案例，並充分進行效能分析 A:　參考 include/linux/wordpart.h 與 lib/string.c 中的 has_zero()。這類實作讓核心處理路徑名稱或字串拷貝時速度提升數倍。 * 教材提及若干真實案例，以 Boeing 787 的[軟體缺失案例](https://hackmd.io/@sysprog/software-failure)來說，為何 32 位元計數器在約 248 天會 overflow？參照 FAA (Federal Aviation Administration ) 和相關官方事故分析報告進行探討 A: 根據 FAA 的 AD 2015-09-07 指令，Boeing 787 的發電機控制單元若連續通電 248 天，會進入安全模式導致電力中斷。技術原因：GCU 使用一個 32-bit 有號整數來計時，單位是 10 毫秒 (cs)。$$2^{31} / (100 \text{次/秒} \times 60 \text{秒} \times 60 \text{分} \times 24 \text{小時}) \approx 248.5 \text{天}$$當計數器溢位至負值時，軟體邏輯判定發生異常，進而關閉系統。 * 在 Linux 核心的 git log 找出類似的 integer overflow 案例並探討 A: Linux 核心使用 jiffies 紀錄系統啟動後的 tick 數。在早期 32-bit 系統上，這很容易溢位。Git Log 修正：搜尋 git log --grep="jiffies overflow"，可以看到核心引入了 time_after() 與 time_before() 巨集。這些巨集利用 二補數運算下的減法特性，即便 jiffies 溢位，依然能正確判斷時間的前後順序。 * 在 C 語言規格書列舉相關整數範圍的規範和實作考量 A: 規格書規定 Signed Integer Overflow 是未定義行為，編譯器可能會因此進行激進的優化（如直接移除溢位檢查程式碼）。Unsigned Integer 則保證會發生 Wrap-around。這就是為什麼 Linux 核心在處理計數器時，強烈傾向使用 unsigned long。 ## 細讀〈[你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)〉 * 為何 Linux 核心程式碼通常會將用以描述硬體狀態 (例如 [x86 的 CR 系列暫存器](https://wiki.osdev.org/CPU_Registers_x86)) 的旗標 (flag) 型態定義為 unsigned 整數，而非 signed 整數？從 padding bits、trap representation 與 C 語言標準行為說明原因 A: 在描述 x86 的 CR0 或 CR4 暫存器時，旗標通常對映到特定的位元（如 Bit 31）。使用 signed 會引入以下麻煩，Padding Bits 與 Trap Representation 根據 C99/C11 規格，signed 整數的最高位是符號位。另外規格允許 signed 型態包含填充位元，這會導致位元分布不連續，無法直接對映硬體暫存器。最後在某些架構下，特定的位元組合對 signed 型態來說是非法的，存取時可能觸發硬體異常。C 語言保證 unsigned 遵循純粹的二進位標記法，沒有符號位，且絕不產生 Trap Representation。這確保了 1 << 31 在 32-bit unsigned int 中永遠是確定的數值。 * 若錯誤地使用 signed int 來儲存旗標並進行位移運算，可能出現哪些實作相依（implementation-defined）或未定義（undefined）行為？結合右移與負數的例子說明，搭配 C 語言規格書描述 A: 若錯誤地將旗標存於 signed int 並進行位移，若一個 signed 數值為負（最高位為 1），執行 >> 時，算術右移補 1（保留符號）。邏輯右移補 0。 如果你的旗標正好位在最高位，右移後的結果在不同編譯器（GCC vs MSVC）或不同架構上可能完全不同，導致判斷邏輯崩潰。根據 C 規格（ISO/IEC 9899），若 E1 << E2 中，E1 是有號正數但運算結果超過該型態能表示的最大值，或者 E1 本身就是負數，則結果是 Undefined Behavior (UB)。如果 int 是 32-bit，這會將 1 移入符號位。在規格中這是 UB，編譯器有權假設這件事永遠不會發生而將相關代碼優化掉。 * 在 Linux 核心中，若某個欄位同時承載 pointer 與 flags（例如最低幾個 bit 作為 flag），程式設計者通常會如何利用 bitwise 操作來拆解這些資訊？參照〈[Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)〉並在 Linux 核心原始程式碼找出更多案例。若程式碼在不同架構（例如 32-bit 與 64-bit）上編譯，這種技巧可能帶來哪些可攜性問題？請討論 alignment 與 pointer size 的影響 A: 在 Linux 核心中，為了節省空間，開發者常利用指標的 Alignment 特性。由於記憶體對齊，指標的最低位元通常是 0。例如在 64-bit 系統上，指標以 8-bytes 對齊，代表最低 3 位元（bit 0, 1, 2）永遠是 0。這些閒置位元可以用來存放旗標。Linux 紅黑樹在紅黑樹中，節點的父指標 __rb_parent_color 同時存儲了父節點位址與節點顏色（紅/黑）。 存入 Flag：node->parent = (unsigned long)ptr | color; 提取 Pointer：ptr = (struct rb_node *)(node->parent & ~3UL); 提取 Flag：color = node->parent & 1; struct page：在記憶體管理中，常利用指標最低位來標記該頁面是否屬於某種特定的 mapping。 Wait Queues：有時會利用位元來標記排隊狀態。 * 當 signed 與 unsigned 整數混合運算時，signed 數值會轉換為 unsigned，導致意外結果，例如比較運算結果顛倒。分析以下程式片段可能導致無窮迴圈: ```c int n = 10; for (int i = n - 1; i - sizeof(char) >= 0; i--) printf("%d\n", i); ``` 這種技巧雖然優雅，但潛藏風險，在 32-bit 架構下指標是 4 bytes，在 64-bit 是 8 bytes。必須使用 unsigned long 或 uintptr_t 進行轉型。在 Linux 核心中，unsigned long 被保證與指標大小一致。另外並非所有架構都強制對齊，若在一個不強制 8-byte 對齊的架構上運行，指標的最低三位可能不是 0，此時進行 | flag 操作會直接毀壞指標位址，導致 Kernel Panic。Linux 核心通常會搭配 __attribute__((aligned(8))) 或透過編譯檢查確保資料結構的對齊符合預期。若將 32-bit 的有號整數旗標與 64-bit 指標進行運算，可能觸發意外的符號擴展，導致高位元全被填成 1。這再次強調了為什麼所有位元運算都應強制使用 U (Unsigned) 字尾（例如 1UL << 31）。 * 以 C 語言規格，逐步說明此程式產生無窮迴圈的原因，特別是 sizeof 的型態與整數提升（integer promotion）的影響 A: ```c for (int i = 10; i - sizeof(char) >= 0; i--) { ... } ``` 根據規格，sizeof 運算子的結果型態是 size_t，這是一個 Unsigned Integer 型態（在 64-bit 系統上通常是 uint64_t）。整數提升與尋常算術轉換：當 int i 與 size_t 進行減法運算時，int 會被提升為 size_t（無號數）。若 i 為 0，執行 0 - 1 (假設 sizeof(char) 是 1) 時，結果不會是 -1，而是 size_t 的最大值（$2^{64}-1$）。條件判定：由於結果是巨大的正數，unsigned_result >= 0 永遠成立，導致無窮迴圈。 * 若這段程式出現在 Linux 核心的 memory allocator 或 buffer traversal 程式碼中，可能造成什麼類型的 bug？在 git log 找出類似案例並探討 A: Linux 核心中的潛在 Bug在 Memory Allocator（如 SLUB）或 Buffer 走訪中，這會導致 Buffer Overflow 或 Kernel Panic。Git Log 案例：搜尋 git log --grep="unsigned underflow"。在早期處理 copy_from_user 的長度檢查時，若長度（size_t）與位移（int）運算不慎，會導致安全檢查失效，讓攻擊者能讀取超出預期的記憶體。 * 教材展示影像處理程式中使用 bitwise 操作拆解 RGBA pixel，將此概念延伸到 Linux 系統軟體： * 若 framebuffer driver 使用 32-bit RGBA pixel 格式，請說明如何用 bitwise 操作快速取得 R、G、B、A 四個分量，並在 Linux 核心原始程式碼找出類似的案例 (提示: V4L2) A: Bitwise 拆解 RGBA，在 32-bit RGBA (8-8-8-8) 格式中： Red: (pixel >> 24) & 0xFF Green: (pixel >> 16) & 0xFF Blue: (pixel >> 8) & 0xFF Alpha: pixel & 0xFF * 為何程式常用位移與遮罩（mask）而非結構體欄位來解析 pixel？從 C 語言規格來探討 A:在　drivers/media/v4l2-core/v4l2-common.c 中，處理像素格式轉換（如 YUYV 轉 RGB）時，大量使用位移與遮罩。為何不用結構體 (Struct Fields)？C 語言規格中，struct 欄位的排列順序受大端/小端影響。使用位元操作能確保在邏輯上的一致性。規格書指出 struct 中的 bit-fields 如何跨越存儲單元邊界是由實作定義 的，這對追求跨平台驅動程式的 Linux 核心來說是不可接受的。 * 若要在 CPU cache 與記憶體頻寬受限的嵌入式系統中處理影像，位元操作與 lookup table 為何能顯著改善效能？ A:在嵌入式系統中，div 與 mul 運算極其昂貴。Lookup Table ：預先計算好色彩空間轉換，將複雜運算簡化為一次記憶體讀取。位元操作：利用並行性（如一次位移處理多個像素的分量），減少對記憶體頻寬的佔用。 * 推導為何 $abs(n) = ((n >> 31) ^ n) - (n >> 31)$ 能正確計算絕對值，回答: * 這種 branchless 技巧在 Linux 核心程式碼中特別重要？提供數學分析和產生的機械碼作為解說 A:數學推導假設 $n$ 是 32-bit 有號整數：若 $n \ge 0$：$n \gg 31$ 會得到 0x00000000 (0)。$(0 \oplus n) - 0 = n$。若 $n < 0$：$n \gg 31$ 會得到 0xFFFFFFFF (-1)。$(-1 \oplus n)$ 等於對 $n$ 取反（One's complement）。根據二補數定義，$-n = (\sim n) + 1$。這裡的運算為 $(\sim n) - (-1) = (\sim n) + 1$，剛好等於其絕對值。傳統寫法 (if (n < 0) return -n;) 會產生 cmp 與 jne。 ```c 　　cdq　; 將 eax 符號擴展到edx (即 n >> 31) 　　xor eax, edx ; (n >> 31) ^ n 　　sub eax, edx ; result - (n >> 31) ``` Branchless 寫法 產生的指令通常如下： * 在現代 CPU 的 branch predictor 與 pipeline 存在的情況下，branchless 寫法仍然有優勢嗎？請分析可能的情境。搭配 Linux 核心的 git log 來解說 A: 雖然現代 CPU 有強大的 Branch Predictor，但在以下情境 Branchless 仍具優勢：若 $n$ 正負分布隨機，預測器會頻繁失效，清空流水線代價極大。程式碼體積 ：減少跳躍指令能讓 I-Cache 效率更高。在處理時序計算法（如 kernel/time/）或網路封包權重時，為了確保每個封包處理的時間一致會優先選擇 Branchless 實作。 ## 分析〈[類神經網路的 ReLU 及其常數時間實作](https://hackmd.io/@sysprog/constant-time-relu)〉 * 教材提及利用 `union` 與位移運算實作 ReLU 的方法，其概念是利用浮點數與整數共用記憶體，藉由檢查 sign bit 判斷輸入是否為負數，並建立遮罩完成條件選擇，回答以下: * 該實作依賴 `int32_t` 的算術右移行為來複製 sign bit。請說明為何在大多數現代處理器上此方法可行，但在 C 語言標準層面仍存在未完全保證的行為。列舉 C 語言規格書內容和處理器指令的語意 (semantics) A: 算術右移的行為與規格 在 ReLU 的實作中，out.i >> 31 依賴算術右移來填充符號位元。大多數現代 CPU（如 x86 的 SAR 指令、ARM 的 ASR）在硬體層級都支援算術右移，根據 C99/C11 規格書（ISO/IEC 9899），對於有號整數的右移，若該值為負，其結果是 Implementation-defined。雖然 GCC 和 Clang 在所有常見平台上都定義為算術右移，但這在標準層面並非 100% 保證。 * 在 Linux 核心中，若要撰寫類似依賴位元語義的程式碼，通常會如何避免 implementation-defined behavior？請舉出 Linux 核心中常見的做法，例如使用特定型別、巨集或輔助用函式 A: 傾向於使用 unsigned 型態 進行位元運算，或使用 BIT() 巨集。若必須處理有號位移，開發者會傾向使用核心提供的封裝函式，並在編譯時透過 -fno-strict-aliasing 等 flag 確保行為符合預期。 * 倘若 ReLU 函式需要被納入 Linux 核心的數值處理路徑中，例如某種 AI 推論模組，請討論 Linux 核心開發者是否會接受 union 型別轉換的寫法，還是傾向其他方式。說明理由並提出替代實作 A: Linux 核心開發者通常不反對使用 union 進行 type punning，因為這比指標轉型更符合直覺且安全。C 規格明確允許透過 union 讀取非當前 active 的成員，這在 C 中是被允許的特性。如果是在核心的數值路徑中，可能會使用 builtin_memcpy（編譯器通常會優化掉實際拷貝，僅做型態重新解釋）或特定的位元運算巨集，以增加可讀性並避免潛在的 padding 影響。 * 藉由位元操作可達成 branchless 計算，即避免使用條件分支來判斷 `x < 0` 的情況，回答以下: * 在現代 CPU pipeline 中，branchless 實作可能比條件分支更快。說明造成此現象的原因，並討論 branch predictor 在其中的角色。設計實驗並用 perf 驗證 A: 現代 CPU 具有 Deep Pipeline。當發生 Branch Misprediction 時，CPU 必須清空已進入流水線的所有指令，代價可能高達 15–20 個週期。ReLU 的輸入通常具有高度隨機性（正負分布不均），這會導致分支預測器失效。Branchless 透過數據依賴取代控制依賴，讓流水線保持順暢。 perf stat -e branches,branch-misses,cycles,instructions ./relu_bench Branchless 版本雖然指令數可能略多，但 branch-misses 趨近於零，且 cycles 顯著下降。 * [Linux 核心中的 `min()` 和 `max()` 巨集](https://hackmd.io/@sysprog/linux-macro-minmax)如何實作，其考量是什麼？ A: Linux 中的 min() 與 max() 巨集Linux 的 min(x, y) 實作非常複雜，其核心考量是 Type Safety：型態檢查：使用 (void) (&_x == &_y); 確保 $x$ 與 $y$ 型態一致，避免 signed 與 unsigned 比較產生的錯誤。避免 Side Effects：使用區域變數儲存參數值，確保 min(i++, j) 這種呼叫不會導致 i 被遞增兩次。 * 考慮上述程式碼在具備 SIMD 的處理器使用，如 AVX 或 RISC-V Vector extension (RVV)，branchless 設計會可帶來什麼額外優勢？提供程式碼和相關分析 A:在向量化運算中，Branchless 是絕對必要的。AVX 或 RVV 無法對向量中的每個元素單獨執行 if 分支。使用向量比較指令產生遮罩（Mask），然後與原數據進行 AND。 ```c // 偽代碼：AVX2 ReLU __m256 x = _mm256_load_ps(data); __m256 zero = _mm256_setzero_ps(); __m256 result = _mm256_max_ps(x, zero); // 硬體層級的 branchless max ``` * ReLU 其一特性是產生稀疏輸出，也就是負值會被截斷為零，導致許多節點沒有貢獻。在 Linux 核心中，找出類似稀疏化帶來效能優勢的案例 (提示: git log) 並充分探討 A: ReLU 導致的稀疏性（許多 0）在 AI 中能節省運算。在 Linux 核心中，類似的思維出現在 Sparse Data Structures：Sparse Indexing in Virtual Memory：Linux 的四級/五級分頁表。IDR (ID Allocation)：利用基數樹（Radix Tree）處理稀疏的整數 ID 對映。搜尋 git log --grep="sparse"，你會發現關於 static_key 或 jump_label 的優化。這類技術在大多數時間保持非活化（0），僅在特定除錯或效能追蹤需求時才跳轉（1），大幅減少了冷路徑對熱路徑的干擾。 * 利用 union 共享記憶體，使 `float` 與 `int32_t` 可直接存取相同位元表示，該技巧本質是種 type punning。請解釋 strict aliasing rule 與此技巧之間的關係。 * 在 GCC 或 Clang 編譯 Linux 核心時，為何 Linux 核心程式碼仍能安全地使用某些 type punning 手法 A: ReLU 導致的稀疏性（許多 0）在 AI 中能節省運算。在 Linux 核心中，類似的思維出現在 Sparse Data Structures：Sparse Indexing in Virtual Memory：Linux 的四級/五級分頁表。IDR (ID Allocation)：利用基數樹處理稀疏的整數 ID 對映。搜尋 git log --grep="sparse" 會發現關於 static_key 或 jump_label 的優化。這類技術在大多數時間保持非活化（0），僅在特定除錯或效能追蹤需求時才跳轉（1），大幅減少了冷路徑對熱路徑的干擾。 Strict Aliasing Rule 該規則規定，編譯器可以假設不同型態的指標不會指向同一個記憶體位址。這允許編譯器進行激進的重排優化。如果你透過 int * 修改了一個 float 的值，編譯器可能因優化而忽略這次修改。Linux 核心在 Makefile 中強制加上 -fno-strict-aliasing。因為核心充滿了各種型態轉換，Strict Aliasing 會導致核心崩潰。 * 若在使用者空間程式中需要安全地取得浮點數的 sign bit，請提出至少二種做法，並比較其可攜性與效能 signbit() (math.h)，可攜性最高，C99 標準函式，編譯器通常會將其轉換為最優位元操作。 memcpy() 可攜性高，現代編譯器會優化掉拷貝動作，安全性最高（符合 Strict Aliasing）。 ## 分析〈[從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt)〉 * 在 Linux 核心中，由於浮點運算通常不可用，許多數值計算必須使用整數或固定點數實作，例如 `int_sqrt()` 或 digit-by-digit 類型的平方根演算法。回答以下: * 假設你要在 Linux 核心中實作 `isqrt()` 函式，用來計算 32 位元整數的平方根。分析以下在核心環境中的可行性與成本: 1) 二分逼近法; 2) 牛頓法; 3) digit-by-digit 方法 A: 在核心環境中實作 32 位元整數的平方根，三種方法的成本與可行性截然不同： 二分逼近法 (Binary Search)可行性高。僅需加法、位移與乘法。需要固定 16 次迭代（對於 32 位元整數的平方根，結果最多 16 位元）。最大的成本在於每次迴圈的 if-else 判斷。在沒有 Loop unrolling 的情況下，極易造成管線的分支預測失敗。 牛頓法 (Newton's Method)可行性中。數學公式為 $x_{k+1} = \frac{1}{2}(x_k + \frac{n}{x_k})$。 Digit-by-digit 方法可行性極高。Linux 核心的 lib/math/int_sqrt.c 正是採用類似此方法的變體。僅需加法、減法與位移。無需乘法與除法。由於迴圈的邏輯單純，甚至可以透過巨集將迴圈完全展開，消除所有迴圈控制的分支開銷。 * 在 Linux 核心環境中不能使用浮點數的情況下，牛頓法需要哪些改寫才能安全使用？詳盡探討固定點數或整數除法可能帶來的誤差來源，以及迭代停止條件該如何設計 A: 牛頓法最大的致命傷是除法運算 (n / x_k)。在多數架構中，整數除法是非常昂貴的指令。由於整數除法會產生截斷誤差（Truncation error），迭代可能不會收斂到單一數值，而是會在兩個相鄰整數間震盪。停止條件不能只寫 $x_{k+1} == x_k$，必須改為檢查 $x_{k+1} \ge x_k$ 或是判斷 $ans \times ans \le n < (ans+1) \times (ans+1)$。 * Linux 核心常要求演算法具備 [predictable execution time](https://en.wikipedia.org/wiki/Worst-case_execution_time)，比較二分逼近法和牛頓法在最壞情況執行時間 (WCET) 上的差異，並說明何者更適合即時 (real-time) 系統。 A: 在要求嚴格的即時系統中，最壞情況執行時間 (WCET) 是演算法選擇的鐵律。二分逼近法的 WCET 是嚴格有界的，對於 32-bit 輸入固定為 16 次運算。牛頓法的迭代次數取決於初始猜測值 $x_0$ 與輸入值 $n$ 的大小。雖然收斂極快，但分析其絕對的 WCET 難度較高。Digit-by-digit 是最適合即時系統的，因為它的運算路徑是固定的，沒有依賴於資料大小的迴圈，WCET 容易計算且穩定。 * 假設輸入值來自不可信來源 (例如網路封包解析)，設計安全版本的 `isqrt()`，並說明如何避免整數溢位、除以零，和無限迴圈 A: ```c u32 secure_isqrt(u32 n) { if (n == 0) return 0; u32 x = n; u32 y = (x + 1) / 2; u32 iterations = 0; while (y < x && iterations < 32) { x = y; if (unlikely(x == 0)) break; y = (x + n / x) / 2; iterations++; } return x; } ``` * 教材說明固定點定理以及 contraction mapping 條件，並指出若函數導數滿足 $|g'(x)| < 1$，則迭代序列會收斂到唯一固定點。將此概念延伸到系統程式設計的情境： * 在 Linux 核心中，許多子系統藉由 feedback control 調整系統狀態，如 CPU frequency scaling, TCP congestion control, memory reclaim 等，選擇其中一機制，說明其更新規則為何可視為固定點迭代過程。提供數學模型和對應程式碼分析 A: 固定點定理指出，若 $x_{k+1} = g(x_k)$，且在區間內 $|g'(x)| < 1$（Contraction Mapping），則系統會收斂至唯一固定點。Linux 核心案例：Load Average (EWMA 指數加權移動平均)Linux 計算系統負載時，使用了 EWMA 公式：$$L_t = L_{t-1} \times e^{-dt/W} + A_t \times (1 - e^{-dt/W})$$簡化為離散的固定點迭代模型：$x_{n+1} = \alpha x_n + (1-\alpha) u_n$。收斂性： 這裡的 $g(x) = \alpha x + C$。其導數 $g'(x) = \alpha$。因為設計上衰減係數 $0 < \alpha < 1$ 嚴格成立，這完美滿足了 $|g'(x)| < 1$ 的條件。只要系統真實負載 $u_n$ 保持穩定，計算出的 Load Average 必然會平滑地收斂至真實負載，而不會發散崩潰。 * 設計自動調整 CPU load balancing 參數的機制，請提出簡單的迭代更新公式，並分析其收斂條件 A: 若設計一個核心排程器的負載轉移量 $W$，可定義迭代更新：$$W_{new} = W_{old} - \beta (Load_{heavy} - Load_{light})$$若 $\beta$（學習率或步長）設定過大，會導致 $|g'(W)| > 1$，使得任務在兩顆 CPU 間瘋狂搬移（Ping-pong effect），系統發散。因此 $\beta$ 必須被嚴格限制在一個小於 1 的小數（在核心中通常透過位移 >> N 來實作小數乘法），確保收斂。 * 教材討論固定點迭代的收斂階數 (order of convergence)，並指出牛頓法具有二次收斂，而一般固定點迭代通常只有線性收斂。假設數值演算法每次迭代的成本為 (C)，而收斂速率可為線性收斂和二次收斂，在實際系統中何者可能更有效率，並考慮每次迭代的計算成本、分支預測，及 cache locality A: 牛頓法具備二次收斂，而 Digit-by-digit 是線性收斂 。但在實際系統中，線性收斂的 Digit-by-digit 通常更有效率。牛頓法次數少（可能只需 4-5 次），但每次包含一次硬體除法。在許多架構（如早期的 ARM 或輕量級 RISC-V）中，除法不是管線化的（Unpipelined），一次除法可能鎖死 ALU 達 30-40 個週期。Digit-by-digit：次數多（16 次），但每次只包含位移、加減與位元邏輯（AND/OR）。這些操作只需 1 個週期，且高度依賴 CPU 的整數管線，Cache Locality 極佳（無查表，無額外記憶體存取）。結論： $5 \times 40$ 週期 $\gg$ $16 \times 1$ 週期。高階收斂如果在單次迭代上付出了過高的 ALU 延遲代價，在底層系統中反而會被捨棄。 * 在 Linux 核心中，有些演算法會刻意避免 division，而改用 bit shift 或查表。說明： * 為何 division 在某些架構上特別昂貴，搭配 git log 來解讀 A: 硬體除法器通常基於 SRT 演算法（一種 Digit-by-digit 的微架構實現），本質上就是一個需要多個 Clock cycle 才能跑完的狀態機。 在核心原始碼中，若搜尋 git log --grep="avoid division"，常會看到除以常數的操作被替換為乘以倒數 (Multiplication by reciprocal)。 例如，x / 10 會被編譯器或工程師手動優化為 (x * 0xCCCCCCCD) >> 35。 * 這如何影響數值演算法設計 A: 我們傾向將所有的除法轉換為基於 2 的冪次位移，或是預先計算好的定點數乘法。 * 針對 digit-by-digit 的平方根計算方法，該方法只需加減與位移運算 。為何該方法特別適合 Linux 核心？若你要為 RISC-V 架構設計新的 `sqrt` 指令，digit-by-digit 方法與牛頓法何者更適合作為硬體微架構 (microarchitecture) 的基礎？請說明原因。 A: 若要在 RISC-V 實作硬體 sqrt 指令，Digit-by-digit (尤其是 SRT 演算法的變體) 是絕對的首選，而非牛頓法。牛頓法在硬體層次需要一個完整的硬體乘法器和一個完整的硬體除法器。這會消耗巨大的晶片面積與功耗。相反地，Digit-by-digit 的硬體電路只需要「移位暫存器 (Shift Registers)」與「加法/減法器」。它與硬體除法器的運作邏輯極度相似，因此 CPU 設計者通常會將整數除法器與平方根運算單元合併，共用同一套資料路徑，這在重視 PPA（效能、功耗、面積）的 RISC-V 核心設計中是最佳實踐。 * 教材展示某些固定點迭代可能會發散甚至產生 `nan` 的案例，回答: * 在系統程式設計中，數值演算法發散可能造成哪些實際問題，例如 scheduler decision 和 network congestion control，以 Linux 核心原始程式碼進行探討 A: 若網路壅塞控制演算法（如 TCP BBR 或 Cubic 的變體）在定點數運算中因為溢位或數學模型失去 Contraction 條件而發散，發送視窗（Congestion Window, cwnd）可能會暴增至最大值，導致網路瞬間癱瘓；或是縮減為 0 導致傳輸 Starvation 。 * 說明為何在 Linux 核心程式碼有時會加入保護式界限(clamping)，並舉例說明其與數值穩定性的關係 A: 在核心中，常看到類似 val = clamp(val, MIN, MAX) 的巨集。從數學數值穩定性的角度來看，很多非線性函數 $g(x)$ 只有在特定的定義域 $[a, b]$ 內才能滿足 $|g'(x)| < 1$。 超出這個範圍，斜率可能大於 1，導致迭代彈射出去。clamp() 的作用就是強制將數值拉回這個安全收斂域內，確保系統無論遭受何種極端的外部輸入，都不會因為數值演算法的崩潰而導致 Kernel Panic。 ## 探討〈[Linux 核心原始程式碼的整數除法](https://hackmd.io/@sysprog/linux-intdiv)〉 * 針對 `#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))`，回答以下: * 說明為何 `((n)+(d)-1)/d` 在 `n` 與 `d` 為正整數時可以實作上取整除法。請以歐幾里得除法表示式 `n = dq + r`，其中 `0 ≤ r < d`，以嚴謹的數學推導此巨集的正確性 A: 假設 $n$ 與 $d$ 皆為正整數。根據歐幾里得除法我們可以將被除數 $n$ 表示為：$$n = dq + r$$其中 $q$ 為商數，$r$ 為餘數，且滿足 $0 \le r < d$。將此代入巨集表達式 ((n) + (d) - 1) / (d) 中：$$\frac{n + d - 1}{d} = \frac{dq + r + d - 1}{d} = q + \frac{r + d - 1}{d}$$在 C 語言中，整數除法會無條件捨去小數部分。我們針對餘數 $r$ 分兩種情況討論： 情況一（可以整除，$r = 0$）：後面的項變成 $\frac{d - 1}{d}$。因為 $d \ge 1$，所以 $0 \le d - 1 < d$。在整數除法中，分子小於分母，結果為 0。最終結果為 $q$，符合上取整的預期。 情況二（無法整除，$1 \le r \le d - 1$）：將不等式各項加上 $d - 1$，得到：$$d \le r + d - 1 \le 2d - 2 < 2d$$此時分子 $r + d - 1$ 介於 $d$ 與 $2d$ 之間（包含 $d$，但不包含 $2d$）。在整數除法中，$\frac{r + d - 1}{d}$ 的結果必定為 1。最終結果為 $q + 1$，精準達成了向上取整（Ceiling）的效果。 * 若 `n` 或 `d` 可能為負數，該巨集可能出現錯誤結果。請設計可在 Linux 核心中安全使用、同時仍盡量避免分支的版本，並說明設計考量 A: 如果 $n$ 或 $d$ 為負數，標準的 + d - 1 邏輯會因為 C99 規格中「向零截斷（Truncate toward zero）」的特性而崩潰。當 $n$ 與 $d$ 異號時（例如 $n = -7, d = 3$），標準的 C 語言除法 -7 / 3 結果是 -2。有趣的是，從數學上來看，$\lceil -2.33 \rceil = -2$，這意味著當兩數異號時，C 語言的預設除法本身就具備向上取整的效果。針對核心環境，我們需要避免高成本的分支指令（Branching）。可以利用位元運算與條件運算子（常被編譯器最佳化為 cmov 條件搬移指令）來設計： ```c #define SIGNED_DIV_ROUND_UP(n, d) \ ({ \ typeof(n) __n = (n); \ typeof(d) __d = (d); \ (((__n) ^ (__d)) < 0) ? \ ((__n) / (__d)) : \ (((__n) + (__d) - ((__n) > 0 ? 1 : -1)) / (__d)); \ }) ``` 使用 typeof 建立區域變數，避免傳入像 i++ 的參數時產生副作用（Side effects）。(__n) ^ (__d) < 0 利用 XOR 運算快速檢查最高位（Sign bit）是否不同。若不同，直接利用 C 語言的向零截斷特性取得天花板值。若同號，則根據正負動態調整 offset，正數為 + d - 1，負數則需要補償為 + d - (-1) 來迫使其向遠離零的方向進位。 * Linux 核心原始程式碼提供 `do_div` 巨集，可在一次操作中取得 64 位元整數除法的商與餘數。回答以下： * 在某些架構 (例如部分 Arm 平台，缺乏 FPU) 上，編譯器可能將 64 位元除法轉換為呼叫 `__aeabi_uldivmod`。說明為何 Linux 核心會刻意避免依賴這類 libgcc 函式 A: Linux 核心是一個獨立環境（Freestanding Environment）。它不依賴使用者空間的標準 C 函式庫（libc），也極力避免隱式依賴編譯器自帶的函式庫（如 libgcc 的 __aeabi_uldivmod）。 如果編譯器偷偷將單純的 / 替換為一個複雜的軟體模擬除法函式，這會破壞系統的指令快取，並且讓該段程式碼的WCET變得極難預測。 核心開發者要求對硬體執行的每一個指令擁有絕對的掌控權。如果硬體不支援 64 位元除法，開發者寧願讓程式在 Linking stage 報錯，以便手動評估並選擇最適合該情境的演算法（例如轉為乘法或位移）。 * 假設你正在實作 Linux 核心中的時間子系統，需要頻繁將奈秒 (ns) 轉換為毫秒 (ms)，討論以下實作方式的優缺點： a) 使用一般 `/` 運算子; b) 使用 `do_div`; c) 將除法轉換為乘法與位移 A: 將奈秒除以 1,000,000 轉換為毫秒： a) 一般 / 運算子： 在 32-bit 架構上會直接觸發連結錯誤。在 64-bit 架構上雖然可行，但硬體除法器會消耗 40 到 100 個 CPU 週期，在頻繁呼叫的時間子系統中是巨大的效能毒藥。 b) do_div 巨集： 解決了跨平台相容性問題，在 32-bit 系統上使用核心手寫的最佳化組合語言或演算法。但本質上仍是除法，面對 1,000,000 這個常數除數，依然不夠快。 c) 乘法與位移（最佳解）： 由於 1,000,000 是已知常數，我們可以預先計算一個 Magic Number $M = \lceil \frac{2^k}{1000000} \rceil$。將轉換公式改為 ms = (ns * M) >> k。這只需要一次 64 位元整數乘法與一次位移，耗時僅需約 3-5 個 CPU 週期，效能差異達數十倍以上。 * Linux 核心 `vsprintf` 中的十進位轉換實作會避免直接使用除法，而改用乘法與查表方式來提升效能。回答以下: * 為何 `/proc` 與 `/sys` 的輸出效能會影響整體系統效能？以實際的測試來說明 A: /proc 與 /sys 虛擬檔案系統是使用者空間工具讀取核心狀態的唯一途徑。如果 vsprintf 將系統資料轉換為十進位字串的速度很慢，當監控工具以高頻率讀取 /proc/stat 或 /proc/net/dev 時，核心會耗費大量 CPU 時間在「印字串」上。這會導致監控系統本身成為系統負載的來源，甚至引發中斷延遲，拖慢真實的應用程式。 * 假設你需要在 Linux 核心中實作頻率統計 (histogram) 輸出函式，每秒可能被呼叫數十萬次，則直接使用 `sprintf` 可能帶來哪些效能問題？為何查表法能改善效能？ A: 標準的 sprintf 每次都需要在執行期解析格式字串，處理不定參數，並且在內部迴圈中反覆使用 num % 10 與 num / 10 來萃取每一個數字。核心的 decpair[100] 陣列預先存儲了 00 到 99 的 ASCII 字元組合。透過定點數乘法 q = (r * (u64)0x28f5c29) >> 32，核心直接除以 100，然後一次從表中查出兩個字元填入 Buffer。這完全消除了硬體除法，減少了一半的迭代次數，並且避免了格式字串解析的額外開銷。 * 某些特殊常數除數可以讓編譯器將除法完全轉換為單一乘法，例如： `⌊n / 274177⌋ = (n × 67280421310721) >> 64`，回答以下: * 為何這類除數被稱為「理想除數」？說明其數學背景 A: 某些特殊除數（例如 274177）被稱為理想除數，因為它們與 2 的冪次方有著完美的因數關係。以 274177 為例：$$274177 \times 67280421310721 = 2^{64} + 1$$當我們要計算 $\lfloor \frac{n}{274177} \rfloor$ 時，等價於計算 $n \times \frac{67280421310721}{2^{64} + 1}$。由於被除數 $n$ 的大小受到資料型態限制（例如 32-bit 無號整數），分母的 $+1$ 對最終截斷結果的影響微乎其微。因此，式子可簡化為 $(n \times 67280421310721) \gg 64$。最精妙的是，當我們對一個暫存器進行乘法，並取其高 64 位元（High 64-bits）時，硬體本身就完成了 $\gg 64$ 的動作。因此，位移指令被完全消除，只需一個乘法指令。 * 假設 Linux 核心 scheduler 需要頻繁計算某個比例值，如 `scaled = load / 274177`，分析使用上述技巧可能帶來的效益與風險 A: 排程器（Scheduler）在計算 vruntime 或 CPU load 時，處於系統最熱的路徑（Hot path）。將除法替換為單一乘法指令，能顯著降低排程延遲，提升系統吞吐量。但參數僵化。排程器的比例常數若寫死為 274177，將導致系統調校失去彈性。若日後需要將負載參數改為動態可調（例如透過 sysctl），這個最佳化就會失效，必須退回使用一般除法或動態計算 Magic Number 的成本。 * 若你是編譯器設計者，會如何在最佳化階段自動偵測並套用此類轉換？ A: 常數傳播（Constant Propagation） 在中間碼（IR）階段，確認除法指令的除數是否為編譯期已知的常數。 Granlund-Montgomery 演算法： 使用數學模型計算出該常數對應的 Magic Multiplier $M$ 與 Shift $S$。 理想特徵匹配： 檢查算出的 $S$ 是否剛好等於目標架構的暫存器寬度（例如 64）。 指令替換（Instruction Selection）： 若匹配，則將 DIV 指令替換為該架構特有的「取高位乘法」指令（例如 x86 的 MUL 取 RDX 暫存器，或 ARM64 的 UMULH），並省略後續的 SHR 位移指令。 ## 細讀〈[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)〉 * Linux 核心在雜湊表 bucket 中使用 hlist_head / hlist_node，而不是一般的 doubly-linked list。其節點結構如 `struct hlist_node { struct hlist_node *next, **pprev; }`，不難見到，`pprev` 不是指向前一個節點，而是指向「指向目前節點的指標」。該設計讓刪除節點時不需要知道 list head。回答下列問題： * 若改用典型雙向連結串列 (prev / next)，當刪除 bucket 中的首個節點時，為何必須額外傳入 list head？用 Graphviz 繪製指標關係圖說明原因 A: 在典型的 struct list_head 中，每個節點包含 prev 和 next。但 Hash Table 的 Bucket array 通常只儲存一個指向首節點的指標（Head）。若我們要刪除第一個節點，必須修改 Head 的指向。如果只傳入節點本身，我們無法往回找到 Head 指標所在的記憶體位址來進行更新。 **Graphviz 指標關係圖： * 說明 hlist 的設計如何消除上述特殊情況。解釋 `__hlist_del()` 的行為並探討其效益 A: hlist 透過將 pprev 宣告為指標的指標來消除特例： 首節點的 pprev 指向 Bucket Head 的 first 指標的位址 (&head->first)。 非首節點的 pprev 指向前一個節點的 next 指標的位址 (&prev->next)。 __hlist_del() 行為： 當執行 *pprev = next 時，無論刪除的是首節點還是中間節點，這行程式碼都能精準地將「指向當前節點的那個指標」改為「指向下一個節點」。這賦予了它在 $O(1)$ 時間內，僅靠節點自身就能完成刪除的能力。 * Linux 核心在 `hash_32()` 中使用乘法雜湊 `val * GOLDEN_RATIO_32 >> (32 - bits)`，其中 `GOLDEN_RATIO_32 = 0x61C88647` 是黃金比例相關常數。探討以下： * 解釋為什麼 Linux hash 函數會取「高位元」作為 bucket index，而不是低位元 A: hlist 透過將 pprev 宣告為指標的指標來消除特例：首節點的 pprev 指向 Bucket Head 的 first 指標的位址 (&head->first)。非首節點的 pprev 指向前一個節點的 next 指標的位址 (&prev->next)。__hlist_del() 行為： 當執行 *pprev = next 時，無論刪除的是首節點還是中間節點，這行程式碼都能精準地將「指向當前節點的那個指標」改為「指向下一個節點」。這賦予了它在 $O(1)$ 時間內，僅靠節點自身就能完成刪除的能力。 * 若 bucket 數量為 `2^p`，說明右移 `(32 - p)` 的數學意義 A: 當 Bucket 數量為 $2^p$ 時，我們需要一個介於 $0$ 到 $2^p - 1$ 的 Index，這剛好對應 $p$ 個位元。 乘法結果保存在 32 位元暫存器中，我們需要最頂端的 $p$ 個位元。將 32 位元數值向右移 $32 - p$ 位，剛好就能把最高位的 $p$ 個位元擠到最低位，作為陣列的 Index。 * 假設系統中 key 值具有模式 `K, K + d, K + 2d, K + 3d, ...`，例如連續的 file descriptor 或 PID。說明為何使用 golden ratio 乘法可以減少 clustering。 A: 當 Key 呈等差數列 $K, K+d, K+2d, \dots$ 時，乘以黃金比例常數等同於在一個圓（大小為 $2^{32}$）上，每次前進一個黃金分割的弧度。這在數學上保證了每次落點會切割現有最大的空白區間（Three-gap theorem），使得連續的 Key 會被極度均勻地打散到不同的 Bucket 中，完美打破等差數列帶來的 Clustering。 * 設計實驗程式（使用 C 或 Python 皆可)，比較以下對 hash 分布的影響: 0x61C88647, 0x80000000, 0x12345678, 0x54061094 等常數，說明實驗結果與文件中的觀察是否一致。要求： * key 範圍：0 ~ 10000 * bucket 數量：1024 * 繪製 bucket occupancy 分布圖 * 分析 collision 與 clustering 情形 * hlist 的其中一個設計目標是減少記憶體開銷，因為 bucket head 只需要一個指標，而不是雙向鏈結串列的二個指標。回答以下: * 假設 hash table 有 1,048,576 個 buckets，在 64 位元系統中，分別使用 `struct list_head` 和 `struct hlist_head`，需要多少記憶體？ A: 記憶體開銷計算 (64-bit 系統) list_head: 2 個指標 (16 bytes)。1,048,576 buckets $\times$ 16 bytes = 16 MB。 hlist_head: 1 個指標 (8 bytes)。1,048,576 buckets $\times$ 8 bytes = 8 MB。 節省了整整 8 MB 的連續核心記憶體。 * 若該 hash table 用於 networking subsystem（例如 connection tracking），bucket 數量非常大但每個 bucket 的元素數量通常很少，說明為何 hlist 是更合理的設計 A: 在 Connection Tracking 中，連線數量極大，Bucket 陣列非常龐大。由於多數 bucket 只有 0 或 1 個元素，節省一半的 Bucket Array 體積能讓更多 Bucket 留在 CPU 的 L2/L3 Cache 中，極大地提升了 Cache Hit Rate。 * hlist 無法在 O(1) 時間取得 tail，討論在什麼情況下 Linux 核心仍會選擇 `list_head` 而非 `hlist` A: 當需要 $O(1)$ 時間取得 Tail 時（例如 FIFO 佇列、LRU Cache 的淘汰機制），hlist 因為只有頭指標，必須遍歷 $O(n)$ 才能到尾端，此時必須使用雙向的 list_head。 * 舉出 Linux 核心中二個實際使用 hash table 的子系統（例如 dentry cache、routing table 或 TCP connection lookup），並分析其 bucket collision 的行為會如何影響系統效能 A: dcache (Dentry Cache)： 快速路徑解析檔名到 inode。碰撞過多會導致遍歷長鏈結串列，使得系統的檔案開啟（open()）操作延遲暴增。 TCP Connection Lookup： 收到封包時比對 4-tuple。若碰撞過多，網路吞吐量會因為 CPU 消耗在鏈結串列尋找上而崩潰（SoftIRQ 佔用 100%）。 * Linux 的雜湊表的設計實際結合三個層面的考量：1) 雜湊函數的統計性質; 2) 資料結構的記憶體布局; 3) CPU cache 與指標操作成本。回答以下： * 若 bucket collision 過多，查找時間將從期望的 $O(1)$ 退化為 $O(n)$，在 Linux 核心中，這種退化可能造成哪些實際系統效應？ A: 若查找從 $O(1)$ 退化為 $O(n)$，CPU 將在鎖（Lock）保護的區段內花費大量時間遍歷鏈結，導致鎖競爭（Lock Contention）加劇、中斷處理延遲（Latency spike），最終引發 Denial of Service (DoS)。 * 假設某個攻擊者可以控制輸入 key（例如 HTTP header 或網路封包欄位），並刻意製造大量 hash collision。說明這種攻擊如何影響系統效能，並舉出 Linux 或其他系統曾出現的類似案例 (提示: git log) A: 攻擊者若知道系統的 Hash 演算法（如單純的乘法或 CRC），可離線計算出數萬個具有相同 Hash 值的 Key（例如 HTTP POST 參數），將其一次發送。伺服器在插入這些 Key 時退化為 $O(n^2)$ 複雜度，瞬間耗盡 CPU。Git Log 案例： Linux 核心曾為了防禦此類攻擊，全面引入了 SipHash（一種具備密碼學強度的隨機化雜湊函數）來取代傳統的 Jenkins Hash 或乘法雜湊，特別是在網路堆疊中。 * 設計改進方案，使雜湊表在碰撞過多時仍能維持穩定性能，應適度考慮 bucket resize, alternate hashing, tree-based bucket, randomized hashing 等手法，並分析這些方法在 Linux 核心中的可行性 (後續可提交貢獻到 Linux 核心) A: Randomized Hashing (SipHash)： 可行且已採用。 每個 Hash Table 初始化時產生一組隨機 Secret，使得攻擊者無法預測 Hash 值。 Tree-based buckets： 部分可行。 Java HashMap 在碰撞超過 8 時會轉為 RB-Tree。但在 Linux 核心中，RB-Tree 節點較大且操作複雜。核心傾向於保持鏈結串列，但透過動態 Resize (Rehashing)（如 rhashtable API）來確保 Bucket 數量充足。 * 教材提到 Fibonacci hashing 與 Three-gap theorem 的數學背景。回答以下: * 為何 Linux 核心實作 hash 函數時，偏好使用整數運算與 bit shift，而非浮點運算？ A: Linux 核心執行緒預設不會保存/還原 FPU（浮點運算單元）暫存器。若要使用浮點數，必須呼叫 kernel_fpu_begin()，這會增加巨大的 Context Switch 負擔。整數運算則極快且具備絕對的確定性。 * 將數學式 $h(K) = \lfloor m (KA - \lfloor KA \rfloor) \rfloor$ 轉換為 Linux 核心實際程式碼形式並解釋每個步驟對應的位元操作 A: $KA$: val * GOLDEN_RATIO_32。$(KA - \lfloor KA \rfloor)$: 在 32-bit 整數乘法中，超過 $2^{32}$ 的進位會被硬體自動丟棄（溢位）。留在暫存器內的 32 位元，實際上就代表了純小數部分。$\lfloor m \times \dots \rfloor$: 乘以 $m = 2^p$ 相當於將小數點右移 $p$ 位。在純整數表示中，這等同於取該 32 位元小數的最頂端 $p$ 個位元，也就是 >> (32 - bits)。 * 若系統由 32 位元架構改為 64 位元架構，hash 函數應如何調整？ A: 改用 64 位元常數 GOLDEN_RATIO_64 (0x61C8864680B583EBull)，使用 64 位元乘法，並向右移 (64 - bits)。 * 把 `GOLDEN_RATIO_64` 放回環論語境，探討可逆性與雜湊不可逆性的差異 * 在環 $R=\mathbb{Z}/2^{64}\mathbb{Z}$ 中，判定 `GOLDEN_RATIO_64` 是否為 unit。必須給出判定條件與理由 (提示: 奇偶性與 $\gcd(C,2^{64})$) A: 在環 $R=\mathbb{Z}/2^{64}\mathbb{Z}$ 中，一個元素 $C$ 為 unit 的充要條件是 $\gcd(C, 2^{64}) = 1$。 由於 $2^{64}$ 的質因數只有 2，任何與其互質的數必須是奇數。 觀察 GOLDEN_RATIO_64 = 0x61C8864680B583EB。它的最後一個十六進位位數是 B (二進位 1011)，這是一個奇數。因此，它在 $R$ 中絕對可逆。 * 若它可逆，說明你如何以擴展歐幾里得演算法求出 $C^{-1}\bmod 2^{64}$，隨後解釋即使乘法在 $R$ 中可逆，為何 `hash_64(val,bits)` 依然不可逆。你必須指出右移取高位元等價於丟棄資訊、丟棄的位元數量與 preimage 的大小關係，並把這點連結到雜湊表只需要分布性，而不需要可逆性 A: 透過擴展歐幾里得演算法，我們尋找整數 $x, y$ 使得 $C \cdot x + 2^{64} \cdot y = 1$。 在模 $2^{64}$ 下，這等價於 $C \cdot x \equiv 1 \pmod{2^{64}}$。求出的 $x$ 即為 $C^{-1}$。在軟體實作上，常利用牛頓-拉弗森方法 (Newton-Raphson) 針對模反元素進行快速迭代計算。 ## 細讀〈[為什麼要深入學習 C 語言？] (https://hackmd.io/@sysprog/c-standards)〉 * 在 Linux 核心原始程式碼和 git log，找出，哪些「編譯器行為差異」會被視為 bug，而非「容忍實作差」的案例 A: 核心本身使用的是一種被稱為 "GNU C" 的方言，而非純粹的 ISO C。當編譯器的改版改變了某些基於 Undefined Behavior 的最佳化策略，且這項改變破壞了核心原有的假設時，Linus Torvalds 與核心社群通常會將其視為編譯器 Bug ，而非單純的實作差異。 從 git log 與核心郵件論壇中，最經典的案例包含: 激進的 Null 指標檢查消除: 早期核心程式碼中有時會先解參考指標，隨後才檢查該指標是否為 NULL。GCC 4.2+ 引入了激進的最佳化：既然指標已經被解參考，編譯器假設它不可能為 NULL ，於是直接把後面的 if (ptr == NULL) 檢查整行刪除。這是致命的 Bug，會導致本地權限升級漏洞。核心透過強制加上 -fno-delete-null-pointer-checks 來封殺此行為。 嚴格別名規則 (Strict Aliasing) 的破壞: C 語言規格允許編譯器假設「不同型態的指標不會指向同一個物件」。但核心的網路堆疊（如 sk_buff 解析）大量依賴指標轉型（Type Punning）來讀取封包標頭。若編譯器依據 Strict Aliasing 重新排序或優化掉記憶體存取，在核心眼中就是 Bug。因此核心永遠以 -fno-strict-aliasing 編譯。 有號整數溢位最佳化: 編譯器若假設有號整數溢位是 UB 而將迴圈條件（如 i + 1 > i 永遠為真）優化掉，會破壞核心的時間計算或計數器。核心依賴 -fno-strict-overflow 或 -fwrapv 來確保溢位行為是可預期的二補數回繞。 * object 與 pointer 的視角如何影響核心中的 API 契約？教材提及 object 是執行時期中「資料儲存區域」的語意單元，pointer 只是其存取表達 ，也點出 `void *` 與字元型別指標在表示法與對齊需求的一致性。回答以下： * Linux 核心的 `copy_from_user` 一類的函式中，若以「object 邊界」定義安全，應該如何表達契約？ A: 傳統上，copy_from_user(void *to, const void __user *from, unsigned long n) 的契約只看指標位址與長度 n。但若從Object 邊界出發，契約應嚴格定義為 契約表達： 目標記憶體區域（Destination Object）的真實容量 $S_{dest}$ 必須大於或等於傳入的長度 $n$。亦即 $n \le S_{dest}$。 核心實作： Linux 核心透過 CONFIG_HARDENED_USERCOPY 實踐了這個契約。它利用編譯器內建函式 __builtin_object_size(to, 0) 在編譯期或執行期動態探測指標 to 背後所代表的 Object 真實大小。如果使用者空間試圖傳入一個超大的 n，即使指標合法，只要超出 Object 邊界，核心就會觸發 Panic，從而阻絕 Buffer Overflow。 * 針對核心常見的巨集，如 `container_of`，從 object model 觀點分析它倚賴哪些假設、哪些假設其實屬於 compiler extension？ A: container_of(ptr, type, member) 是將內部成員的 Pointer 還原為整個物件的 Object 。 倚賴的假設（標準 C ）： 傳入的指標確實指向該 type 結構體中的 member。結構體的記憶體佈局是連續的，且 member 在結構體中的位元組偏移量（Byte offset）在編譯期是固定且可知的。 倚賴的假設（ Compiler Extension ）： 型別安全檢查 (typeof)： 核心實作中有一行 const typeof( ((type *)0)->member ) *__mptr = (ptr);。這依賴了 GNU C 的擴充 __typeof__。它的目的是宣告一個與 member 型別完全相同的區域指標，並將傳入的 ptr 賦值給它。如果傳入的 ptr 型別不對，編譯器會在此時發出警告，確保指標視角的正確性。 指標算術的擴充： 透過將指標轉型為 char *（字元型別指標與 void * 具有一致的對齊需求，且允許逐位元組移動），減去 offset 後，再轉型回 type *。 * 教材列出 C23 候選特徵例如 `typeof`, `call_once`, `char8_t`, `unreachable` 單參數 `_Static_assert` C++11 風格 attribute 二補數強制 binary literal `_BitInt` `#elifdef` 等，回答以下: * 從 GCC 手冊 (不能參照其他二手材料！) 挑出「核心早已有 GNU extension 對應物」的特徵，例如 `typeof` 對應 `__typeof__`, `unreachable` 對應 `__builtin_unreachable`, attribute 對應 `__attribute__` A: 待寫 * 探討 `_BitInt(N)` 是否能改善 Linux 核心在不同處理器架構中，位元精準資料結構與 ABI 表述 A: _BitInt(N) 允許開發者定義精確位元寬度的整數（例如 _BitInt(24) 代表精確的 24-bit 整數）。 Linux 核心處理硬體暫存器、網路封包標頭（如 24-bit 的網路欄位）時，傳統上依賴 C 語言的「位元欄位 (Bit-fields)」。然而，C 規格書明定 Bit-fields 的記憶體佈局（Endienness、Padding、跨越 Byte 邊界的行為）是 Implementation-defined 的。這導致核心為了跨架構相容性，通常會避免使用 Bit-fields，轉而使用 __u32 搭配手動的位移與遮罩操作。理論上，_BitInt(N) 能在語言層級提供精確的位元寬度，減少手動操作的繁瑣。但核心現實面的挑戰，核心對 ABI（Application Binary Interface）的要求極端嚴苛。_BitInt(N) 在不同處理器架構（x86, ARM64, RISC-V）上的 ABI 規範（例如：一個 _BitInt(24) 在記憶體中到底佔用 3 bytes 還是會被 padding 到 4 bytes？對齊要求是 1 byte 還是 4 bytes？）目前在各平台的 C ABI 規範中仍在發展或存在歧異。只要編譯器對 _BitInt(N) 的記憶體對齊（Alignment）與填充（Padding）行為在跨架構時有一絲一毫的不可預測性，核心網路堆疊與檔案系統的開發者就不可能信任它，依然會堅持使用 __u8 陣列或 __le32 搭配手動解析，以確保物件在記憶體中的 representation 絕對精準。 ## 探討〈[基於 C 語言標準研究與系統程式安全議題](https://hackmd.io/@sysprog/c-std-security)〉 * 文件提及 integer conversion rank 和 usual arithmetic conversions，在系統程式設計中，混合使用 `signed` 與 `unsigned` 型別是緩衝區溢位（buffer overflow）的常見根源。回答以下: * 參考 C11 標準 §6.3.1.8 (Usual arithmetic conversions)，當一個 `signed long` (64-bit) 與一個 `unsigned int` (32-bit) 進行二元運算（如比較大小或加法）時，標準規定具體會發生什麼轉型？這與 `signed int` 和 `unsigned int` 的情況有何不同？ A: 根據 C11 的 常規算術轉換規則 signed long (64-bit) vs unsigned int (32-bit)：因為 signed long 的轉換階級大於 unsigned int，且 64 位元的 signed long 可以完整表示 32 位元 unsigned int 的所有值（$0$ 到 $2^{32}-1$），編譯器會將 unsigned int 提升為 signed long。此時進行的是有號數運算。 signed int (32-bit) vs unsigned int (32-bit)：兩者 Rank 相同，且 32 位元有號數無法表示無號數的所有值。編譯器會將 signed int 強制轉型為 unsigned int。此時進行的是無號數運算。 * 在 Linux 核心的歷史漏洞中，常見於 `access_ok(type, addr, size)` 或類似的記憶體範圍檢查巨集。假設開發者寫出 `if (user_len < 0 || user_len > MAX_LEN)`，但 `MAX_LEN` 被定義為 `unsigned` 常數，而 `user_len` 是 `signed` A: 假設程式碼為 if (user_len > MAX_LEN)，其中 user_len 為 signed long (64-bit)，MAX_LEN 為 unsigned int (32-bit)：因為兩者都被轉換為 signed long，編譯器會產生算術比較的組合語言指令。如果攻擊者傳入負數（例如 -1），在有號比較下，-1 > MAX_LEN 為 False，成功繞過長度上限檢查。當這個 -1 被傳遞給 copy_from_user(dst, src, user_len) 時，該函數的 size 參數型別通常是 unsigned long。-1 會被符號擴展並轉為無號數，變成 0xFFFFFFFFFFFFFFFF。這會導致核心將海量的使用者空間資料拷貝到 Kernel Heap 中，引發毀滅性的溢位。 * 請編譯器（如 GCC）在產生組合語言時，會使用邏輯比較（`CMP` 指令後接 `JA/JB`）還是算術比較（`JG/JL`）？這如何導致負數的 `user_len` 繞過檢查並在後續 `copy_from_user` 中造成巨大的 kernel heap overflow？ A:　User-level (malloc / ptmalloc)： malloc(0xFFFFFFFF) 通常會嘗試使用 mmap 向作業系統請求記憶體，但會因為觸發行程的位址空間上限（RLIMIT_AS）或實體記憶體不足而直接失敗返回 NULL。若有妥善檢查 NULL，通常只會造成 Denial of Service (DoS)。 * 結合文件提到的 "wraparound"，當攻擊者控制 `size` 參數造成 integer underflow，這在核心層級（kernel space）的 `kmalloc(size)` 配置中，與使用者層級的 `malloc` 行為有何本質上的不同 (考量到 SLUB 配置器的行為)？ A: Kernel-level (kmalloc / SLUB)： kmalloc 遇到過大的 size 也會失敗返回 NULL。但在核心攻擊場景中，攻擊者通常會利用乘法溢位：如 kmalloc(count * sizeof(struct))。如果 count 夠大使得乘積發生 wraparound 變成極小值（例如 8），SLUB 配置器會成功配發一個 8 bytes 的極小 chunk。隨後 copy_from_user 卻使用原本極大的 count 進行寫入，這會直接摧毀 SLUB 的 Metadata（如 freepointer），讓攻擊者得以劫持核心的記憶體配置鏈，進而執行任意程式碼。 * C11 §6.2.4.2 關於物件生命週期的定義是，當物件生命週期結束，指標的值變為不確定 (indeterminate)，回答以下: * 在現代 C 語言編譯器模型（如 LLVM 的 [PNVI-ae-udi 模型](https://inria.hal.science/hal-02089907/file/n2363.pdf)）中，即使兩個指標 `p` (已釋放) 和 `q` (新配置) 的記憶體地址（數值）相同，它們在語意上是否相等？ A: 在現代 C 編譯器的 PNVI-ae-udi 模型中，指標不僅僅是一個數值，還帶有來源。 即使已釋放的指標 p 與新配置的指標 q 記憶體位址數值完全相同，它們的來源截然不同。在語意上，它們是不相等的。存取 p 依舊是 Undefined Behavior 。 * 討論 Alias Analysis（別名分析）如何利用 "Strict Aliasing Rule" 或 "Object Lifetime" 假設，認定對 `q` 的寫入不會影響 `p` 指向的內容，進而對程式碼進行激進的最佳化 (例如刪除看似多餘的 null check) A: 編譯器的別名分析會基於物件生命週期進行假設：因為 p 指向的物件生命週期已經結束，任何對新物件 q 的寫入操作，絕對不可能改變 p 所指向的內容，因為 p 已經無效。 這讓編譯器可以對記憶體存取進行重新排序或快取暫存器，忽略 p 與 q 可能在實體記憶體上重疊的事實。 * 考慮以下程式碼: ```c if (ptr) free(ptr); // Object lifetime ends here // ... 複雜邏輯 ... if (ptr) // 攻擊點 ptr->func_table->execute(); ``` 根據 C 標準，存取已釋放的 `ptr` 是 Undefined Behavior (UB)。編譯器是否有權力假設「UB 永遠不會發生」，進而直接移除第二個 `if (ptr)` 的檢查（Dead Code Elimination），導致該程式碼無條件執行？這對漏洞防護機制的實作有何啟示？ A: free(ptr) 雖然結束了物件生命週期，但並未改變 ptr 變數本身的數值。因此第二個 if (ptr) 永遠為 True。根據 C 標準，解參考已釋放的指標是 UB。編譯器「有權力」假設開發者絕對不會寫出觸發 UB 的程式碼，因此它可能直接認定這個程式路徑不可能發生，進而刪除整個第二段 if 區塊；或是反過來，因為確定 ptr 非空，直接拔掉 if 檢查並裸奔執行 UAF。依賴邏輯判斷來防護 UAF 是不可靠的。唯一的正解是貫徹防禦性編程，在 free(ptr) 後立即強制 ptr = NULL;，從根本上切斷編譯器對指標狀態的危險假設。 * 文件分析 Exim 郵件伺服器自訂的 `store_pool` 機制，及 `store_extend` 函數邏輯錯誤導致的 UAF。回答以下: * Exim 選擇實作自己的 Block/Pool 管理器，而非直接依賴 `glibc` 的 `malloc/free`。從 Heap Layout 的角度分析，Exim 的這種連續記憶體 (chunking) 策略，與 `glibc` 的 `ptmalloc`（使用 bins, chunks, boundary tags）相比，哪種結構在發生 overflow 時更容易被利用來進行 "House of Spirit" 或 "Unlink Exploit" 類的攻擊？ A: Exim 維護一個巨大的連續 Block，靠移動指標來切割空間，沒有中介的 Chunk Metadata。發生 Overflow 時，攻擊者只能覆蓋相鄰的應用程式資料。每個分配的記憶體前都有 Boundary Tags 。若發生 Overflow，攻擊者可以輕易覆寫這些 Metadata，偽造 Chunk 結構，觸發 "Unlink Exploit"（在 free 時利用雙向鏈結串列脫離寫入任意記憶體）或 "House of Spirit"。就破壞配置器內部結構而言，ptmalloc 遠比 Exim 的實作容易被利用；但 Exim 的 UAF 則為攻擊者提供了直接劫持應用程式邏輯（如覆寫函數指標）的途徑。 * Exim 的 `store_release` 只是移動指標，並未真正清除資料。這與 Linux 的 [RCU (Read-Copy-Update)](https://hackmd.io/@sysprog/linux-rcu) 機制中的 "Grace Period" 有何異同？ A: Exim store_release： 只是單純將分配指標倒退回上一個位置，資料原封不動保留。這是一種同步、立即生效的空間回收，但非常容易因為指標未同步清空而導致 UAF。RCU 採用的是延遲釋放。更新者會先拷貝一份資料，更新後替換指標，但舊的記憶體必須等到所有正在讀取它的執行緒都度過 Grace Period 後，確認無人引用，才會真正被 kfree。RCU 的本質就是為了解決並行環境下的 UAF 問題。 * 該漏洞的關鍵在於 `store_extend` 失敗後，程式邏輯誤以為舊區塊仍有效，但實際上指標已指向被釋放 (或即將被重用) 的區域。對照 Linux 核心的 `krealloc` 函式實作，當 `krealloc` 原地擴充（resize in place）失敗而必須移動記憶體時，如何處理舊指標？Linux 核心如何避免類似 Exim 這種「舊指標指向已釋放區域」的 race condition？ A: Exim 的漏洞在於 store_extend 失敗後，開發者繼續使用舊指標。在 Linux 核心中，當 krealloc(p, new_size, flags) 嘗試原地擴展失敗時，它會配置一塊新記憶體，拷貝資料，然後 kfree(p)。krealloc 會返回新的記憶體位址。核心社群嚴格要求開發者必須寫成 p = krealloc(p, size, flags);。同時，核心會利用靜態分析工具（如 Smatch、Coccinelle）加上編譯器屬性 __must_check，強制開發者接住回傳值，確保舊指標 p 立即被覆寫，徹底消滅「舊指標指向已釋放區域」的 UAF 風險。 * 文件 UAF 的緩解措施及 `stack-use-after-scope`。然而，開發者常嘗試手動清除敏感資料 (如密碼或 Key)，回答以下: * 依據 C11 §5.1.2.3 (Program execution) 的 "As-if" 規則，編譯器只需要保證「可觀察行為」（Observable Behavior）一致。若開發者在函式返回前處理 `memset(password, 0, len);`，隨後變數 `password` 脫離 Scope。解釋為何在較高的編譯器最佳化級別（`-O2` 或 `-O3`，編譯器會將這行 `memset` 視為無用程式碼並刪除？ A: 根據 C11 的 "As-if" 規則，編譯器可以對程式碼進行任何最佳化，只要不改變程式的可觀察行為（Observable Behavior，如 I/O 操作、volatile 存取）。 當開發者寫下 memset(password, 0, len); 後，變數 password 隨即脫離 Scope。對編譯器而言，這個變數已經死亡，對一個死亡物件的寫入不會對程式的後續輸出產生任何影響。因此在 -O2 最佳化下，這行 memset 會被視為 無效寫入 (Dead Store) 並被無情刪除。密碼就此殘留在 Stack 中，成為嚴重的資訊洩漏漏洞。 * 比較 C11 Annex K 引入的 `memset_s` 及 Linux 核心中的 `memzero_explicit`。這些函式在實作層面上使用哪些技巧 (例如 `volatile` 關鍵字或 memory barrier) 來強迫編譯器保留清除指令？這與文件中提到的「物件生命週期」概念有何衝突與妥協？ A: C11 memset_s： 標準庫特別規定，memset_s 對記憶體的寫入效果必須被視為「可觀察行為」，編譯器絕不可將其最佳化掉。 Linux Kernel memzero_explicit： 實作上通常會結合編譯器屏障或 volatile 強制轉型。例如使用 asm volatile("" : : "r"(ptr) : "memory");，這告訴編譯器這段內聯組合語言可能會讀寫全域記憶體，且 ptr 被使用了不能亂改寫它之前的記憶體寫入操作。這在理論上產生了矛盾：C 標準認為物件死亡後資料毫無意義，但安全實務認為物理記憶體中殘留的電子信號是致命的。這些特殊函數與 Barrier，就是開發者為了在 C 語言的抽象虛擬機語意與物理硬體安全性之間取得妥協。 ## 探討〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉 * C 語言規格指出 `void *` 可與任何物件指標互相轉換，並且其 representation 與 alignment requirement 與 `char *` 相同，但 ISO C 不允許直接對 `void *` 進行 pointer arithmetic。從 C 語言型別系統與記憶體模型的角度，說明以下： * 為何 C 語言需要 `void *` 這種「無型別指標」(提示: C 語言規格書)？這種設計如何支援泛型資料結構（例如 `malloc`、鏈結串列、資料容器函式庫）？ A: 在 C89 引入 void * 之前，C 語言通常使用 char * 來充當通用指標，這在語意上並不嚴謹。void * 是一種不帶有物件大小資訊的指標。它代表「這裡有一塊記憶體，但我不知道裡面裝什麼」。像 malloc(size_t size) 返回的就是一塊未定型態的記憶體，必須是 void * 才能被隱式或顯式地轉型為任何資料型態的指標（如 int *, struct node *）。對於 qsort() 或 Linked List 這種資料容器，底層只需搬移 void * 即可處理任何型態的資料，實現了 C 語言的泛型（Generics）機制。 * 為何 ISO C 不允許對 `void *` 進行 pointer arithmetic，這反映什麼設計考量？ A: 指標算術如 ptr + 1，其背後的真實位址運算是 address + 1 * sizeof(*ptr)。因為 void * 不知道所指物件的型態，編譯器無從得知 sizeof(void) 是多少（在 ISO C 中 sizeof(void) 是非法的）。因此，ISO C 嚴格禁止對 void * 進行加減運算，強迫開發者必須顯式轉型（例如轉為 char *，此時 sizeof(char) == 1）後才能進行位移，這避免了隱含的記憶體存取錯誤。GNU C Compiler (GCC) 作為擴充，允許對 void * 運算，並假設其 size 為 1，但這不符合標準 C 規格。 * 為何 `void *` 可安全轉換為 `int *` 再轉回，但 `void *` 與 `void **` 的轉換卻可能導致未定義行為 A: int * $\to$ void * $\to$ int * (安全)： C11 規格 §6.3.2.3 保證，任何物件指標轉換為 void * 後，再轉換回原本的型態，結果必須與原指標相等。 * Linux 核心程式碼中少用 `void *` arithmetic，而是轉型為 `char *` 或其他型別後再計算位址。說明考量因素並分析其與 strict aliasing rule 的關聯 A: void ** 是「指向 void * 的指標」。它不是無型別指標，它是一個有明確型態（指向指標的指標）的指標。如果把一個 int ** 強制轉型為 void * (合法)，再轉型為 void ** 並進行解參考，這違反了嚴格別名規則，因為你正在用 void * 的型態去讀寫一個實際上是 int * 的物件，這會導致編譯器產生未定義行為 。 * `malloc` 可能回傳有效指標，但實際的實體記憶體尚未配置，只有在程式首次存取該記憶體時才會真正配置 page。回答以下: * 說明虛擬記憶體 (virtual memory) 的基本概念，及為何使用者行程只能看到虛擬位址，硬體設計者的考量是什麼？ A: 每個行程都擁有獨立且連續的虛擬位址空間，這些虛擬位址透過 CPU 的 MMU映射到分散的實體記憶體。行程間無法互相讀寫記憶體，防止崩潰蔓延或惡意存取。程式設計師不需關心實體記憶體碎片問題，永遠看到連續的可用空間。 * 解釋 demand paging 的運作流程，包含 page fault 發生後 Linux 核心需要進行的主要步驟 A: 當呼叫 malloc 時，OS 只會分配虛擬記憶體位址，不會分配真實的實體分頁。 首次存取 (First Touch)： 程式嘗試讀寫該虛擬位址。 Page Fault (分頁錯誤)： MMU 發現該虛擬位址在分頁表 (Page Table) 中標記為無效（未映射），觸發 Exception 交控給 Linux 核心。 核心處理： Linux 核心的 Page Fault Handler 介入，檢查該虛擬位址是否合法。若合法，核心從 Free List 中找出一塊實體分頁。 映射與恢復： 核心更新分頁表，將虛擬位址映射到該實體分頁，然後讓 CPU 重新執行剛才觸發 Exception 的那道指令。 * 為何 `malloc()` 的回傳值無法直接對應到保證記憶體一定可用？在什麼情況下首次存取記憶體可能觸發 OOM？ A: OOM (Out of Memory)： 如果所有行程開始兌現它們的虛擬記憶體（大量觸發 Page Fault），導致實體記憶體與 Swap 空間耗盡，Linux 核心的 OOM Killer 就會被喚醒，強制殺死某些行程以釋放記憶體。這就是為什麼 malloc() 回傳非 NULL，卻在後續存取時導致程式崩潰的原因。在高效能運算 (HPC) 或大型資料庫系統中，Overcommit 可以極大化記憶體利用率；但在 Mission-Critical 系統中，這帶來了極大的不可預測性。 * Linux 的 memory overcommit policy 為何允許系統配置超過實體記憶體容量的虛擬記憶體？該設計在伺服器系統與高效能運算環境中有哪些優缺點？以 Linux 核心原始程式碼內附的文件和原始程式碼進行解讀 A: Overcommit Policy： Linux 預設允許配置超過系統實體記憶體總量的虛擬記憶體（因為很多程式 malloc 了一大塊記憶體卻只用一小部分）。 * CPU 存取資料通常以 word 或 cache line 為單位，若資料未對齊可能需要多次記憶體讀取或額外硬體操作，回答以下： * 為何 CPU 偏好對齊的記憶體存取？以 4-byte integer 為例，說明 aligned 與 unaligned access 的差異，搭配 Graphviz 繪製記憶體佈局圖 A: 記憶體控制器與 CPU Cache 通常以 Word (如 4 bytes 或 8 bytes) 或 Cache Line (如 64 bytes) 為單位抓取資料。如果一個 4-byte int 的位址是 0x00 (對齊)，CPU 只需要發出一次記憶體讀取請求。 **記憶體佈局圖 (Graphviz): * 若一個 4-byte integer 位於 address `0x01`，CPU 可能需要執行哪些額外操作才能完成存取？ A: 若 4-byte int 位於 0x01（跨越了 Word 邊界）： CPU 必須讀取 Word 1 (0x00-0x03)。 CPU 必須讀取 Word 2 (0x04-0x07)。 CPU 將 Word 1 去掉 byte 0，將 Word 2 取出 byte 4。 將兩部分拼接 (Shift and Mask) 成一個完整的 4-byte 暫存器數值。這不僅耗時，如果跨越了 Cache Line 甚至 Page 邊界，代價更為巨大。 * 為何 x86(-64) 架構通常允許 unaligned access，而某些 RISC 架構（如 ARM 或 RISC-V）可能需要額外指令甚至觸發例外？ A: x86 硬體內部實作了複雜的微指令 (Micro-ops) 來自動處理拼接，對開發者透明，但會造成效能下降。 ARM/RISC-V： 早期或精簡的 RISC 架構硬體不處理這件事，遇到 Unaligned Access 會直接丟出 Hardware Exception ，導致程式崩潰。 * Linux 核心提供 `get_unaligned()` 與 `put_unaligned()` 等工具函式，其設計目的為何？在跨平台核心程式碼中為何重要？ A: get_unaligned() 為核心處理網路封包時，標頭的位元組常常不對齊。這些巨集在 x86 上直接展開為指標讀取，而在 ARM 等平台則展開為逐 Byte 讀取並手動 Shift 組合，確保程式具備跨平台可攜性。 * 由於結構體與指標通常具有 alignment 保證，因此位址的最低幾個 bit 永遠為 0，可被用作額外資訊，例如在 [lock-free linked list](https://hackmd.io/@sysprog/concurrency) 中標記節點已被邏輯刪除。 * 為何 alignment 可保證某些位元永遠為 0？若系統保證 8-byte alignment，最低幾個 bit 可以安全使用？ A: 在 64-bit 系統中，指標通常以 8-byte 對齊。這意味著所有合法的指標數值，其二進位的最低 3 個 bit 永遠是 0（因為是 8 的倍數）。這 3 個 bit 可以安全地被拿來當作 Boolean Flag (即 Pointer Tagging)。 * 為何 lock-free linked list 常使用 logical deletion 而非立即刪除節點？ A: 在 Lock-free 鏈結串列中，多個執行緒同時在遍歷與刪除。如果執行緒 A 準備從節點 X 走到節點 Y，而執行緒 B 瞬間將節點 Y free 掉，執行緒 A 就會觸發 UAF (Use-After-Free) 崩潰。 * pointer tagging 如何協助實作這種邏輯刪除機制？ A: 不直接 free，利用 Pointer Tagging，將節點 Y 的 next 指標最低位設為 1。這表示這條路徑即將被刪除。其他執行緒看到這個標記，就知道不該往這裡走，或者協助完成刪除動作。 * Linux 核心中哪些資料結構或同步機制使用類似技術 (提示: RCU 或其他 lock-free container)？ A: RCU (Read-Copy Update)： RCU 的指標也大量依賴這類記憶體排序與標記機制。 rbtree ： 核心的紅黑樹實作中，父節點指標的最底端 bit 被用來儲存節點的顏色（紅或黑），極大地節省了記憶體空間。 * 說明 glibc `malloc` 設計的關鍵原理與其在多執行緒環境中的限制： * 為何 `malloc` 需要 arena 機制？它如何減少多執行緒競爭？ A: 早期 malloc 只有一個 Global Lock，多執行緒同時 malloc 會導致嚴重的鎖競爭。glibc 引入多個 Arena。每個執行緒分配一個 Arena，執行緒只在自己的 Arena 中鎖定並配置記憶體，大幅減少了執行緒間的碰撞。 * 為何 thread arena 通常使用 `mmap()` 而不是 `brk()` 取得記憶體？ A: Main Arena： 使用 brk() 推進 Heap 指標。這要求虛擬位址空間必須是連續的。 Thread Arena： 因為一個 Process 中無法有多個連續的 brk 區域，Thread Arena 改用 mmap() 在記憶體映射區中挖出獨立的區塊（通常 1MB 到數 MB）來進行管理。 * 為何 fastbin 在 `free()` 時不會立即合併 chunk，而 small bin 與 large bin 則會？ A: Fastbin 專門處理極小塊的記憶體（如小於 64 bytes）。這類記憶體被頻繁配置與釋放。如果不合併，下次遇到相同大小的請求，可以直接 $O(1)$ 彈出。如果每次 free 都去檢查相鄰 chunk 並合併，會消耗大量 CPU 週期，且很快又會被切開。只有在系統記憶體真的不夠，或分配 large chunk 時，才會觸發 malloc_consolidate() 進行大掃除。 * 為何在[高度並行](https://hackmd.io/@sysprog/concurrency)伺服器程式中，glibc malloc 可能成為效能瓶頸？這也是為何出現 jemalloc、tcmalloc 等 allocator 的原因 A: 儘管有 Arena，glibc ptmalloc 在極端多執行緒下（如 Nginx, Redis）仍有 False Sharing、鎖競爭與嚴重記憶體碎片的問題。因此出現了 jemalloc / tcmalloc 採用了 Thread-Caching 、更細緻的 Size Class 與更好的碎片管理演算法，專為多核高並行設計。 * 教材提及的記憶體配置器屬於使用者空間的實作，但 Linux 核心並不使用 glibc `malloc`，而有自己的記憶體配置器，如 slub 與 `kmalloc()`。 * 為何 Linux 核心不能直接使用 glibc `malloc`？ A: 核心是作業系統的底層，它自己就是記憶體的管理者。glibc 運行在 User Space，依賴核心的 System Call (如 mmap)。核心如果用 glibc，就會變成「雞生蛋、蛋生雞」的問題。 * `kmalloc()` 與 `vmalloc()` 在記憶體配置方式與位址連續性方面有何不同？ A: kmalloc()： 分配的記憶體在虛擬位址與實體位址上都是連續的。適用於 DMA (Direct Memory Access) 等需要實體連續記憶體的硬體驅動程式。速度極快，因為直接對應核心的線性映射區。 vmalloc()： 分配的記憶體在虛擬位址上連續，但實體位址可能不連續。適用於需要配置巨大陣列（如核心模組載入）但不需要 DMA 的場景。速度較慢，因為需要修改核心的分頁表 (Page Table)。 * slab / slub 為何對核心資料結構特別重要？ A: Object Cache： SLUB 為這些特定結構建立專屬的 Cache。釋放時不會交還給系統，而是保留初始化狀態，下次配置直接拿來用，消除了初始化的開銷，並且由於物件大小完全一致，徹底解決了外部碎片（External Fragmentation）問題。 * Linux 核心環境中，記憶體配置器的設計為何特別強調 deterministic behavior 與 cache locality？搭配 git log 來說明 Linux 核心的相關演化 A: 在系統核心中，WCET 必須可控。kmalloc 基於 SLUB，其配置路徑在 Fast-path 下是 Lock-free 且無分支的，保證了極致的效能。 此外，SLUB 的設計高度對齊硬體的 L1/L2 Cache Line，並支援 NUMA-aware（盡量在發出請求的 CPU 節點上分配實體記憶體），這對於降低 Memory Latency 至關重要。 ## 細讀〈[C 語言的 bit field](https://hackmd.io/@sysprog/c-bitfield)〉 * 考慮以下程式： ```c struct { signed int a : 1; } obj = { .a = 1 }; if (obj.a == 1) puts("one"); else puts("not one"); ``` 教材中指出，輸出結果會是 `"not one"`，因為 `1-bit signed` 在二補數系統中只能表示 `{0, -1}`。因此當 `1` 被存入時，bit pattern `1` 會被解讀為 `-1`。 回答： * 為何 `signed int : 1` 只能表示 `{0, -1}`？自 C 語言規格書找出對應的描述 A: 在 C 語言中，有號整數使用二補數來表示（C23 規格更是強制規定只能使用二補數）。對於一個寬度為 $N$ 的二補數有號整數，其表示範圍是 $-2^{N-1}$ 到 $2^{N-1} - 1$。當 $N = 1$ 時，這個唯一的 bit 也就是符號位元完全沒有空間存放數值大小。根據 C99/C11 規格，當該位元為 0 時，數值為 $0$。當該位元為 1 時，代表負數，其數值為 $-2^{1-1} = -1$。因此，將 1 存入時，這唯一的 bit 被設為 1，在取值時就會被強制作符號擴展（Sign extension），解讀為 -1。 * 若改為 `struct { unsigned int a : 1;};`，其語意會如何改變？ A: 若改為無號整數，表示範圍變為 $0$ 到 $2^N - 1$。當 $N = 1$ 時，範圍即為 {0, 1}。此時存入 1，讀取出來的結果就會如預期般是 1，條件判斷 obj.a == 1 便會成立。 * Linux 核心原始程式碼如何使用 C bit-field 來表示旗標？為何還有 set_bit(), clear_bit(), test_bit() 等操作？ A: Linux 核心在宣告狀態旗標時，極少使用 Bit-field（例如 unsigned int is_running : 1;），而是採用 unsigned long flags; 並搭配 set_bit()、clear_bit() 與 test_bit()。C 語言的位元欄位賦值（如 obj.a = 1）在底層會被編譯為「讀取-修改-寫入（Read-Modify-Write, RMW）」的指令序列。這在多核心環境下不是原子操作，會引發嚴重的 Race Condition。set_bit() 等函式是架構相依的，它們在底層會使用硬體級別的原子指令（例如 x86 的 LOCK BTS 指令），確保在多 CPU 並行修改同一個 unsigned long 變數的不同 bit 時，絕對安全。 * 說明在 Linux 核心中使用 bit-field 需要考慮到 1) ABI; 2) 編譯器差異; 3) 記憶體 layout 不可預測。並搭配 git log 舉例說明這些考量 A:　ABI 與位元順序（Byte/Bit Order）： C 規格書明確指出，Bit-field 在儲存單元內的分配順序是 Implementation-defined（由編譯器決定）。在大端序（Big-Endian）與小端序（Little-Endian）機器上，a 和 b 誰在高位、誰在低位完全相反。這使得它無法用於定義網路封包標頭（Network Headers）或跨平台的資料結構。 編譯器差異（Padding & Alignment）： 不同編譯器（甚至同編譯器的不同版本）對於跨越邊界的 Bit-field 如何填充（Padding）有不同的策略。 不可預測的 Memory Layout： 無法透過 sizeof 準確預估含有 Bit-field 結構的真實大小，也無法對 Bit-field 取位址（&obj.a 是非法的）。 Git Log 實例： 在核心網路堆疊或 USB 驅動中（例如搜尋 git log --grep="bitfield"），你可以看到大量的 Patch 將舊有的 struct { u8 a:4, b:4; } 替換為單純的 u8 val;，並引入 FIELD_GET() 與 FIELD_PREP() 巨集來進行安全的位元提取。 * 教材提到 zero-width bit-field: `int : 0;`，其作用是強制下個 bit-field 對齊到新的 storage unit，分析以下: ```c struct foo { int a : 3; int b : 2; int : 0; int c : 4; int d : 3; }; ``` 回答以下: * 在 C 語言標準中，`int : 0` 的語意是什麼？ A: C11 規格 §6.7.2.1 指出寬度為 0 的未命名位元欄位，指示先前的位元欄位所在的儲存單元（Storage Unit）不應再封裝後續的位元欄位。簡言之，它強迫 c 和 d 必須放在下一個獨立的分配單元中。 * 為何 `c` 與 `d` 可能落在不同的記憶體區域？ A: 在沒有 int : 0 時，a, b, c, d 加起來只有 12 bits，可以完美塞進一個 4-byte 的 int 裡。加入 int : 0 後，a, b 佔用第一個 4-byte，c, d 被強制推到第二個 4-byte 裡。此時 sizeof(struct foo) 變成了 8 bytes。 * 為何在不同編譯器（例如 gcc 和 clang）中結果可能不同？ A: 當教材中的程式碼執行 int i = 0xFFFF; struct foo *f = (struct foo *)&i; 時，指標 f 指向的記憶體實際上只有 4 bytes（即變數 i 的生命週期範圍）。 * 以 C 語言規格的觀點，解釋教材聲明的「`c` 和 `d` 可能指向不同記憶體區域，因此結果可能不穩定」的根本原因 A: 當讀取 f->c 與 f->d 時，程式實際上越界讀取了 i 之後未初始化的 Stack 記憶體，因此每次印出的數值都是不可預期的垃圾值。 * Linux 核心在結構對齊上幾乎不用 zero-width bit-field，而是使用 `__aligned()` 或 `__attribute__((aligned))`，回答以下： * 為何 Linux 核心避免使用 zero-width bit-field？ A: int : 0 太過隱晦，且下一個儲存單元到底是 4 bytes 還是 8 bytes 取決於編譯器。Linux 核心偏好使用明確的 __attribute__((aligned(x))) ，這能以絕對精確的 byte 數控制資料結構的記憶體佈局，不留模糊空間。 * 若在 Linux 核心中使用 bit-field 進行硬體暫存器映射，可能會出現什麼問題？以 memory-mapped IO (MMIO) 暫存器操作為例說明 A: 如果用 Bit-field 來映射硬體暫存器（Memory-Mapped IO），會引發災難。Read-Modify-Write (RMW) 副作用： 假設寫入 obj.c = 1。編譯器會產生指令：先讀取整個暫存器的狀態，修改 c 所在的位元，然後將整個值寫回暫存器。如果該暫存器中有某些硬體狀態位元是讀取後清除（Read-to-Clear）或寫入 1 清除（Write-1-to-Clear, W1C）」，這個 RMW 循環會意外地將其他與 c 無關的硬體中斷或狀態旗標清空，導致硬體行為失控。因此，核心讀寫硬體暫存器嚴格要求使用 readl() 與 writel()。 * 教材提及 Linux 核心的技巧 `#define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:(-!!(e)); }))`，從 C 語言規格的角度回答以下: * `!!(e)` 的作用是什麼？為何 `-!!(e)` 可能變成 `-1`？為何 `int : -1` 會導致編譯時期的錯誤？ A: !!(e): 兩次邏輯 NOT。將任何非零值（真）轉為 1，零值（假）轉為 0。 -!!(e): 加上負號。結果只會是 -1（真）或 0（假）。 * 為何 `int : 0` 是合法的？ A: 如果條件 e 為真，宣告變成 int : -1。C 規格嚴格要求 Bit-field 的寬度必須是非負整數常數，編譯器會在此時直接丟出編譯錯誤。如果為假，int : 0 是合法的（寬度為 0 的未命名欄位），而且這整個匿名的 struct 使用 sizeof 計算後會回傳 0，可合法放在任何需要常數的地方。 * 對應到 C11 以上的規格，有哪些替代方案？ A: C11 引入了 _Static_assert(expression, message);。它能在編譯時期優雅地檢查條件，並提供自訂的錯誤訊息，完全取代了這類利用 Bit-field 寬度來強迫編譯器報錯的方式。 * C11 規格指出，同一個結構體中的二個 bit-field 若位於同一記憶體位置，並行更新不安全。考慮 `struct flags { unsigned a : 1; unsigned b : 1; };`，假設 CPU~0~ 修改 `a` 且 CPU~1~ 修改 `b`，回答以下： * 為何這兩個操作可能發生 race condition？ A: 根據 C11 規格 §3.14，相鄰的 Bit-fields 共享同一個記憶體位置。 當 CPU~0~ 修改 a，CPU~1~ 修改 b 時，它們實際上是對同一個 Byte（或 Word）進行競爭。這構成了標準定義的資料競爭，屬於未定義行為。 * bit-field 修改通常需要什麼指令序列？以 C11 (含之後) 規格書內文來解讀 A: Load (LDR): 將包含 a 和 b 的整個 Word 載入 CPU 暫存器。 Modify (AND/ORR): 使用 Bit Mask 清除目標位元，再用 OR 寫入新值。 Store (STR): 將修改後的 Word 寫回記憶體。如果 CPU~0~ 和 CPU~1~ 同時 Load 了初始值，各自 Modify 後寫回，後寫回的 CPU 會直接覆蓋掉另一個 CPU 的修改（Lost Update），導致其中一個旗標的設定完全失效。 ## 練習題 > 逐一分析[第二週教材](https://wiki.csie.ncku.edu.tw/linux/schedule)列出的[題目-1](https://hackmd.io/@sysprog/linux2025-quiz2)、[題目-2](https://hackmd.io/@sysprog/linux2024-quiz2)、[題目-3](https://hackmd.io/@sysprog/linux2023-quiz2)、[題目-4](https://hackmd.io/@sysprog/linux2022-quiz2)，和[題目-5](https://hackmd.io/@sysprog/linux2021-quiz2)，確認理解題目且充分作答，並指出參考題解的錯誤和待改進之處 * `ldexpf` 的實作中，可用 `-!!(new_exp >> 8)` 產生全為 `1` 或全為 `0` 的 bitmask 來判斷 overflow，且不用條件分支，回答以下： * 說明 `!!x` 與 `-!!x` 在位元層級上的運作方式，為何可產生 `0x00000000` 或 `0xffffffff`？ * 說明為何 Linux 核心中使用 branchless bit operations，而非 `if` 條件判斷，以 git log 舉例探討 * 在 CPU pipeline 與 branch prediction 的角度，分析 branchless bitmask 技術可能帶來的效能優勢 * 利用 SWAR (SIMD Within A Register) 技巧可同時處理多個 byte，例如用於 `memchr` 的加速。回答以下： * SWAR 的原理是什麼？為何可在單一暫存器中同時處理多個位元組？ * 利用 SWAR 來加速 Linux 核心原始程式碼的字串處理函式 (之後可貢獻回 Linux 核心)，務必詳盡測試並確認效益 * CRC 計算本質上是 mod 2 polynomial division，並可用 XOR 取代加減運算。回答以下： * 為何 CRC 的多項式運算可以用 XOR 取代加減？ * 說明 CRC polynomial 的 bit representation 與 GF(2) 之間的數學關係 * LSB-first CRC 計算需使用 reversed polynomial。說明其原因 * Linux 核心中 CRC 的實作常見於 `lib/crc32.c` 和 `lib/crc-ccitt.c`，說明二者實作策略的差異 * 若要設計 bit-field friendly CRC pipeline，如何利用 `crc = (crc >> 1) ^ (-int(crc & 1) & POLY);` 技巧降低運算成本？ * Linux CPU 排程器的 PELT 使用 EWMA 並透過位元操作實作衰減計算，其設計目標是 `y^32 = 0.5`，回答以下： * Linux 核心如何避免使用浮點數？ * PELT 為何將 $y^n$ 轉換為 $(1/2)^{n/32}$ 的表示方式？ * Linux 透過 `mul_u64_u32_shr()` 完成定點數乘法，說明其設計原理並從 C 語言規格書觀點解說 * 說明 `val = mul_u64_u32_shr(val, runnable_avg_yN_inv[n], 32);` 的數學意義 * 為何 CPU 排程器的 EWMA 必須保持 deterministic fixed-point arithmetic？搭配 Linux 核心原始程式碼和數學模型來解說