---
# System prepended metadata

title: 2026q1 Homework2 (stdc)

---

# 2026q1 Homework2 (stdc)


{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
> 課程助教註記: 4 月 14 日


## 思索〈[分析「快慢指標」](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 或類似的向量繪圖表示法，清晰展現數值表示的過程和限制
    * IEEE-754 單精度或雙精度為例，說明 sign, exponent, mantissa 在表示 `0.1` 時會發生什麼情況。
    * 文中指出浮點數加法不具有結合律，從 Linux 核心的原始程式碼 (事實上使用定點數，但具備浮點數運算的特性) git log 找出對應的浮點數運算考量並充分討論

十進位小數在轉換為二進位時，需透過不斷乘以 $2$ 並提取整數部分來求得小數位元。由於 $0.1$ 的質因數僅包含 $2$ 與 $5$，在基底為 $2$ 的系統中無法被徹底消除，不可避免地會產生無限循環。

**轉換狀態圖 (Graphviz)**
如下圖所示，從 $0.1$ 開始的乘法運算，在到達 $1.2$ 取出整數 $1$ 後，小數部分再次回到 $0.2$，形成了無法終止的循環迴圈。


```graphviz


digraph decimal_to_binary {
    rankdir=LR;
    node [shape=record, fontname="Helvetica"];
    edge [fontname="Helvetica", fontsize=10];
    
    Start [label="{0.1 | initial}"];
    S1 [label="{0.2 | bit: 0}"];
    S2 [label="{0.4 | bit: 0}"];
    S3 [label="{0.8 | bit: 0}"];
    S4 [label="{1.6 | bit: 1}"];
    S5 [label="{1.2 | bit: 1}"];
    
    Start -> S1 [label=" *2"];
    S1 -> S2 [label=" *2"];
    S2 -> S3 [label=" *2"];
    S3 -> S4 [label=" *2"];
    S4 -> S5 [label=" -1, *2"];
    S5 -> S2 [label=" -1, *2\n(Loop)", color=red, style=dashed];
}
```

#### IEEE-754 單精度的儲存行為

在 32 位元的單精度浮點數 (Single-precision floating-point format) 中，實體記憶體的有限性強制截斷了前述的無限循環小數。$0.1$結構與儲存行為如下：

* **符號 (Sign, 1 bit):** 數值為正，故記為 $0$。
* **指數 (Exponent, 8 bits):** $0.1$ 在二進位的正規化表示為 $1.100110011... \times 2^{-4}$。將指數 $-4$ 加上偏移量 (Bias) $127$ 後得到 $123$，對應二進位序列為 `01111011`。
* **尾數 (Mantissa, 23 bits):** 去除隱含的整數 $1.$ 後，剩餘的小數部分受限於 23 bits 的記憶體空間，硬體必須採用就近捨入 (Round-to-Nearest) 原則進行截斷。最終尾數儲存為 `10011001100110011001101`（最後一位因進位機制，由 $0$ 進位為 $1$）。

此截斷與進位機制導致系統實際儲存的數值略大於精確的 $0.1$，此即 $0.1 + 0.2 \neq 0.3$ 精度流失現象的底層物理成因。

#### 實體記憶體佈局驗證實驗
為驗證上述理論，以下透過 C 語言的 `union` 共用體機制，直接讀取並剖析單精度浮點數 $0.1f$ 的底層位元狀態：

```c
#include <stdio.h>
#include <stdint.h>

/* 定義 union 來共用記憶體 */
typedef union {
    float f;
    uint32_t u;
} FloatBits;

void print_ieee754_bits(float value) {
    FloatBits fb;
    fb.f = value; // 寫入浮點數

    // 透過位元遮罩與右移，提取各個區塊
    uint32_t sign = (fb.u >> 31) & 0x1;
    uint32_t exponent = (fb.u >> 23) & 0xFF;
    uint32_t mantissa = fb.u & 0x7FFFFF;

    printf("輸入數值: %.17f\n", value);
    printf("記憶體 Hex: 0x%08X\n\n", fb.u);
    printf("[Sign]     (1 bit) : %u\n", sign);

    printf("[Exponent] (8 bits): ");
    for (int i = 7; i >= 0; i--) {
        printf("%u", (exponent >> i) & 1);
    }
    printf(" (實際十進位值: %d, 扣除偏移值 127 後為: %d)\n", exponent, exponent - 127);

    printf("[Mantissa] (23 bits): ");
    for (int i = 22; i >= 0; i--) {
        printf("%u", (mantissa >> i) & 1);
    }
    printf("\n");
}

int main() {
    print_ieee754_bits(0.1f);
    return 0;
}
```
**實驗輸出結果：**

```
輸入數值: 0.10000000149011612
記憶體 Hex: 0x3DCCCCCD

[Sign]     (1 bit) : 0
[Exponent] (8 bits): 01111011 (實際十進位值: 123, 扣除偏移值 127 後為: -4)
[Mantissa] (23 bits): 10011001100110011001101
```
實驗結果與理論推導吻合，展示截斷誤差 (Truncation Error) 如何反映在實體記憶體中。

####  浮點數結合律的失效
在純數學領域中，實數加法構成阿貝爾群 (Abelian group)，必然滿足結合律。然而在 IEEE 754 浮點數運算中，$(a + b) + c \neq a + (b + c)$ 經常成立。
其根源在於：當極大數值與極小數值相加時，硬體為了對齊指數 (Exponent Alignment)，較小數值的有效尾數會被移出界線而永久丟棄，造成無法復原的精度流失。改變運算的先後順序，會直接改變對齊的基準點，進而改變捨去誤差 (Rounding Error) 發生的時間點與規模。

####  Linux 核心的架構考量與定點數 (Fixed-point) 實作
查閱 Linux 核心代碼庫（如核心調度器 [kernel/sched/fair.c](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c) 或時間子系統 `ktime_t` 相關實作），可以發現開發者極力避免在核心層級 (Kernel Space) 使用浮點數型別。此設計基於兩大核心考量：

1.  **硬體上下文切換成本 (Context Switch Overhead)：** 浮點運算單元 (FPU) 包含龐大且複雜的暫存器狀態。若核心使用浮點數，每次中斷或排程切換皆需保存與恢復 FPU 狀態，將引發難以承受的效能瓶頸。
2.  **絕對決定性 (Determinism) 的數學需求：** 若在核心中使用浮點數累加執行時間或計算負載權重，前述的非結合律會導致微小的捨去誤差隨時間不斷發散，破壞排程公平性。因此，Linux 採用 64 位元無號整數 (`u64`) 配合極大的縮放因子 (Scaling Factor) 來實作定點數運算。此種整數域的運算能確保調度權重（如 `NICE_0_LOAD`）的累加嚴格維持數學上的結合律，保障跨微處理器架構行為的一致性。




* 針對 balanced ternary 和 radix economy
    * 電腦科學家 Donald E. Knuth 在《The Art of Computer Programming》第 2 卷說 "Perhaps the prettiest number system of all is the balanced ternary notation"，其背景考量是什麼？Knuth 是否有對應的著作進一步探討？
    * 為何 balanced ternary 中求負數只需「符號反轉」？與二補數 (two's complement) 表示法相比，分析計算成本、硬體實作，和數值對稱性。建立數學模型並討論
    * 說明為什麼低位元量化 (例如 ternary / 1-bit LLM) 在 AI 硬體中具有潛在優勢。參照提及的論文，描述其關鍵考量 $\to$ 歡迎協作 [BitMamba.c](https://github.com/jserv/bitmamba.c)

#### 平衡三進位 (Balanced Ternary) 的理論優勢與底數經濟學

Knuth 的學術評價背景與底數經濟學 (Radix Economy)
Donald E. Knuth 在其鉅作《The Art of Computer Programming, Volume 2: Seminumerical Algorithms》第 4.1 節「Positional Number Systems」中，給予平衡三進位高度評價："Perhaps the prettiest number system of all is the balanced ternary notation"。

其背景考量建立在「底數經濟學 (Radix Economy)」的數學評估模型上。底數經濟學用於衡量不同進位制在表達同一數值時的硬體儲存效率，其公式為 $E(b) \propto b/\ln(b)$。透過微積分求導可知，該函數在自然底數 $e \approx 2.718$ 時達到極小值（即最優效率）。由於實體數位邏輯必須採用整數基數，距離 $e$ 最近的整數 $3$ 其效率嚴格優於基數 $2$。

平衡三進位的數學對稱性
Knuth 進一步指出，平衡三進位（使用 $-1, 0, +1$ 作為基本單位）在數學運算上具備極簡的美感。它無需如二進位般特意挪用最高位元作為獨立的符號位元 (Sign bit)。此外，在該系統中進行就近捨入 (Round-to-Nearest) 時，無須實作複雜的進位判斷，只需直接截去小數部位 (Truncation) 即可完成，大幅簡化了數值運算的邏輯閘設計。



* 算術運算可完全以數位邏輯實作，分析 $x + y = (x \oplus y) + ((x \& y) << 1)$ 並回答：
    * 參閱數位邏輯教科書 (善用圖書館資源)，在硬體加法器中 `x ^ y` 和 `x & y` 各代表什麼訊號？並摘錄書中對應的描述，探討其應用場景



在硬體半加器 (Half-Adder) 的數位邏輯電路中，`x ^ y`（互斥或，XOR）代表的是「總和訊號 (Sum)」，而 `x & y`（及閘，AND）代表的則是「進位訊號 (Carry)」。

在權威數位邏輯教科書（如 M. Morris Mano 的《Digital Design》）的運算單元章節中，對加法器的基本定義為：XOR 閘負責計算兩個位元相加後該位數的結果，而 AND 閘則判定是否需要向高位數進位。將進位訊號左移一位 (`<< 1`) 並與總和訊號相加，即可構成完整的加法運算。

應用場景方面，此邏輯是算術邏輯單元 (ALU) 中建構漣波進位加法器 (Ripple-Carry Adder) 與前瞻進位加法器 (Carry-Lookahead Adder) 的基礎。

程式實驗設計（C 語言實作無加號加法器）：
```C
#include <stdio.h>
#include <stdint.h>

uint32_t bitwise_add(uint32_t x, uint32_t y) {
    while (y != 0) {
        uint32_t sum = x ^ y;           // 計算無進位的總和訊號
        uint32_t carry = (x & y) << 1;  // 計算進位訊號並左移
        x = sum;
        y = carry;
    }
    return x;
}

int main() {
    printf("105 + 42 = %u\n", bitwise_add(105, 42)); // 輸出 147
    return 0;
}
```












* 為何 `(x+y)/2` 可能造成 overflow？又為何 $(x \& y) + ((x \oplus y) >> 1)$ 可避免 overflow


`(x+y)/2` 發生整數溢位 (Integer Overflow) 的原因在於，當 `x` 與 `y` 的數值皆接近該資料型態的極限值（如 32 位元無號整數的 UINT_MAX）時，`x + y` 的中間產物會超越暫存器能表示的最大範圍，導致高位元遺失（發生 Wrap-around），此時再除以 2 將得到完全錯誤的極小值。

`(x&y)+((x⊕y)>>1)` 能避免整數溢位，其數學邏輯在於將加法拆解：
1. `x & y` 擷取出兩數皆為 1 的位元（即共同擁有的數值），這些位元在相加除以二後，數值與自身相同。
2. `x ⊕ y` 擷取出兩數相異的位元。
3. `(x ⊕ y) >> 1` 直接將這些相異位元的總和訊號除以 2。
兩者相加即等於平均值，且過程中沒有任何步驟會產生大於 `max(x, y)` 的中間數值，從硬體層面徹底消除了溢位的風險。

程式實驗設計（極端數值平均測試）：
```C
#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t x = 0xFFFFFFFF; // UINT_MAX
    uint32_t y = 0xFFFFFFFD; // UINT_MAX - 2
    
    uint32_t avg_naive = (x + y) / 2;
    uint32_t avg_safe  = (x & y) + ((x ^ y) >> 1);
    
    printf("Naive: %u\nSafe: %u\n", avg_naive, avg_safe);
    // 輸出結果：
    // Naive: 2147483646 (因 x+y 溢位導致結果錯誤)
    // Safe: 4294967294 (正確算出平均值)
    return 0;
}
```







* 在 Linux 核心中，為何這類 bit-level reasoning 對於效能與正確性非常重要？在 git log 找出對應的改進和修正
* `x & (x - 1)` 可用來檢測什麼數值性質？給出數學推導，說明為何此技巧成立。Linux 核心中有哪些場景會利用 power-of-two (2 的冪，[不是「冪次」](https://hackmd.io/@sysprog/it-vocabulary)) 性質？為何 power-of-two 對於系統效能特別重要？


`x & (x - 1)` 用於檢測一個無號整數是否為「二的冪 (Power-of-two)」或是 0。

數學推導：
若 $x$ 為二的冪（即 $x = 2^k$），其二進位表示式中將有且僅有一個位元為 1（例如：$16_{10} = 00010000_2$）。
計算 $x - 1$ 時，必然會向該唯一的 1 借位，導致該位元變成 0，而其右方所有較低的位元皆翻轉為 1（例如：$15_{10} = 00001111_2$）。
此時執行位元及閘運算 `x & (x - 1)`，因所有位元皆完全互補，結果必然為 0。

在 Linux 核心中，記憶體管理的夥伴系統 (Buddy System) 高度依賴此性質，所有的記憶體區塊大小皆被嚴格限制為二的冪。此外，核心的對齊巨集（如 `ALIGN` 與 `IS_ALIGNED`）也大量運用此性質。

二的冪對效能的關鍵影響在於：它能將極度耗時的除法，替換為只需 1 個 CPU 週期的位元及閘運算 (`&`)。例如，計算 `val % size` 時，只要 `size` 是二的冪，就能以等價的 `val & (size - 1)` 取代，大幅提昇系統吞吐量。





* `((X) - 0x01010101) & ~(X) & 0x80808080` 技巧可用於 `strlen()` 的實作，回答：
    * 該巨集偵測的是什麼資料？為何該運算可一次檢測 4 個位元組？為何這比逐 byte 檢查更有效率？

該巨集偵測的目標資料為「零位元組 (Null Byte, 0x00)」，通常用於判斷 C 語言字串的結尾。

運算能一次檢測 4 個位元組 (32 bits) 的原理為 SWAR (SIMD Within A Register，暫存器內的單指令多資料流) 技術：
1. `(X - 0x01010101)`：對 32 位元整數內的 4 個位元組同時減 1。若其中存在值為 `0x00` 的位元組，減 1 後會產生下溢位 (Underflow)，使其最高位元（即 `0x80` 的位置）被設置為 1。
2. `~(X)`：確保該位元組原本的最高位元不是 1（排除原本就大於等於 128 的 ASCII 或 UTF-8 字元）。
3. `& 0x80808080`：將雜訊遮罩，只保留 4 個位元組各自的最高位元。若最終結果不為 0，則表示這 4 個位元組中至少包含一個 Null Byte。

比逐 Byte 檢查更有效率的原因在於「逐字組 (Word-at-a-time)」操作：現代 CPU 從記憶體載入資料時，原生字組長度即為 32 或 64 位元。逐位元組檢查需要執行 4 次載入指令、4 次條件跳躍指令；而使用 SWAR 僅需 1 次載入指令與極少量的位元算術運算，徹底釋放了 CPU 暫存器寬度的硬體潛能，並大幅降低了分支預測 (Branch Prediction) 失敗的機率。


* 在 Linux 核心原始程式碼中找出類似 word-at-a-time 手法的案例，並充分進行效能分析
* 教材提及若干真實案例，以 Boeing 787 的[軟體缺失案例](https://hackmd.io/@sysprog/software-failure)來說，為何 32 位元計數器在約 248 天會 overflow？參照 FAA (Federal Aviation Administration ) 和相關官方事故分析報告進行探討
    * 在 Linux 核心的 git log 找出類似的 integer overflow 案例並探討
    * 在 C 語言規格書列舉相關整數範圍的規範和實作考量

## 細讀〈[你所不知道的 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 語言標準行為說明原因


* 若錯誤地使用 signed int 來儲存旗標並進行位移運算，可能出現哪些實作相依（implementation-defined）或未定義（undefined）行為？結合右移與負數的例子說明，搭配 C 語言規格書描述

在 C99 與 C11 的標準中，位元位移運算子（Shift operators）潛藏著兩種極需注意的硬體與編譯器陷阱：實作相依行為（Implementation-defined Behavior）與未定義行為（Undefined Behavior, UB）。

首先是「實作相依行為」。當我們對負數進行右移（`>>`）時，C 語言標準並未強制規定電腦應該在高位補 0（即邏輯位移，Logical shift）還是補 1（即算術位移，Arithmetic shift）。這意味著具體的行為交由編譯器開發者決定。多數主流編譯器（例如 GCC）在實作上會選擇採用算術位移以保留數值的負號；然而，這樣的設計如果在處理位元遮罩（Bitmask）時不加注意，補進來的高位元 1 很容易破壞遮罩的完整性，導致非預期的運算結果。

其次則是更為致命的「未定義行為」。在左移運算（`<<`）中，標準對「無號數（Unsigned）」和「有號數（Signed）」的容錯度截然不同。當我們對一個正整數（有號型態）進行左移時，如果移動後的數值過大，導致該資料型態的記憶體空間無法容納（例如左移後覆蓋到了最高位的「符號位元，Sign bit」），標準並未規定電腦該如何處理，這便觸發了 UB。由於現代編譯器在進行高度最佳化時，會建立在「程式設計師寫出的程式碼絕對不會觸發 UB」的假設上，因此編譯器可能會將引發 UB 狀態下的相關邊界檢查或防呆邏輯視為無用程式碼（Dead Code）並直接捨棄，最終導致系統執行時發生無法預期的崩潰。

關於左移運算引發 UB 的原文與詳細定義，明確記載於 C11 規格書的第 6.5.7 節第 4 條：
"The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 × 2^E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined."
[參考出處](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf)

這段原文清楚劃分了安全與危險的邊界：無號數的左移發生溢位時會自動取同餘（Modulo），超出高位的部份會被安全捨棄；但有號正整數的左移結果必須能完整放進該資料型態的範圍內，一旦擠壓到符號位元，即屬未定義行為。在撰寫 C 語言底層與系統程式時，這兩種位移行為都是需要嚴格防範的重點。


為了更具體地說明這兩種陷阱，我們可以透過以下 C 語言程式碼來進行實驗驗證：
```C
#include <stdio.h>

int main() {
    int val = 1;
    // 實驗：觸發 C99/C11 的未定義行為 (左移覆蓋符號位元)
    // 註：在 C23 之後此行為被定義為合法的二補數環繞，但在舊版標準與舊編譯器中為 UB。
    int ub_shift = val << 31;

    // 實驗：負數右移的實作相依
    int neg_val = -16; // 0xFFFFFFF0
    int right_shift = neg_val >> 2;

    printf("Left shift (UB in C11): %d (0x%X)\n", ub_shift, ub_shift);
    printf("Right shift (Imp-def): %d (0x%X)\n", right_shift, right_shift);
    // 輸出為 -4 (0xFFFFFFFC)，證明高位補 1 (算術位移)
    return 0;
}

}
```
從上述程式碼的執行結果可以觀察到兩個現象：首先，在多數現代編譯器（如 GCC）的實作下，`right_shift` 的輸出通常為 `-4 (0xFFFFFFFC)`。這證實了編譯器在處理負數右移時採用了「算術位移」，自動在高位補上 1 以維持負數特性；其次，`val << 31` 刻意將正整數 1 推入符號位元，雖然在未開啟激進最佳化的環境下，它可能會印出 `-2147483648 (0x80000000)`，但這在 C99/C11 標準下確確實實是未定義行為（UB）。特別值得注意的是，雖然最新的 C23 標準已經順應硬體發展，將此行為重新定義為合法的二補數環繞（Two's complement wrap-around），但在維護龐大的舊有系統或使用較舊的編譯器標準時，這樣的寫法仍可能成為最佳化階段的未爆彈。因此，在撰寫 C 語言底層與系統程式時，面對位移操作需極度謹慎。


















* 在 Linux 核心中，若某個欄位同時承載 pointer 與 flags（例如最低幾個 bit 作為 flag），程式設計者通常會如何利用 bitwise 操作來拆解這些資訊？參照〈[Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)〉並在 Linux 核心原始程式碼找出更多案例。若程式碼在不同架構（例如 32-bit 與 64-bit）上編譯，這種技巧可能帶來哪些可攜性問題？請討論 alignment 與 pointer size 的影響
* 當 signed 與 unsigned 整數混合運算時，signed 數值會轉換為 unsigned，導致意外結果，例如比較運算結果顛倒。分析以下程式片段可能導致無窮迴圈:
    ```c
    int n = 10;
    for (int i = n - 1; i - sizeof(char) >= 0; i--)
        printf("%d\n", i);
    ```
    * 以 C 語言規格，逐步說明此程式產生無窮迴圈的原因，特別是 sizeof 的型態與整數提升（integer promotion）的影響
    * 若這段程式出現在 Linux 核心的 memory allocator 或 buffer traversal 程式碼中，可能造成什麼類型的 bug？在 git log 找出類似案例並探討 


分析程式碼：
```c
    int n = 10;
    for (int i = n - 1; i - sizeof(char) >= 0; i--)
        printf("%d\n", i);
```
此程式會陷入無窮迴圈。依據 C 語言標準，`sizeof` 運算子回傳的型態為 `size_t`（無號整數）。當有號變數 `i` 與無號的 `sizeof(char)` 進行運算時，會觸發「整數提升（Integer Promotion）」，`i` 會被隱式轉換為無號整數。當 `i` 遞減至 0 時，`0 - 1` 會發生無號數下溢位（Underflow），環繞成該型態的最大正值（如 `0xFFFFFFFF`），永遠大於等於 0。

實驗設計：
```C
#include <stdio.h>

int main() {
    int i = 0;
    // 觀察型態提升後的運算結果
    if (i - sizeof(char) >= 0) {
        printf("0 - 1 is functionally >= 0 due to unsigned promotion.\n");
        // 強制轉型回 unsigned long long 印出真實數值
        printf("Underflow value: %llu\n", (unsigned long long)(i - sizeof(char)));
    }
    return 0;
}
```
分析：若此邏輯存在於 Linux 核心的記憶體分配器（Memory Allocator）陣列走訪中，這類漏洞（Bug）會導致記憶體越界讀寫（Out-of-Bounds Access），進而引發 Kernel Panic 或形成可利用的資訊安全漏洞。





* 教材展示影像處理程式中使用 bitwise 操作拆解 RGBA pixel，將此概念延伸到 Linux 系統軟體：
    * 若 framebuffer driver 使用 32-bit RGBA pixel 格式，請說明如何用 bitwise 操作快速取得 R、G、B、A 四個分量，並在 Linux 核心原始程式碼找出類似的案例 (提示: V4L2)
    * 為何程式常用位移與遮罩（mask）而非結構體欄位來解析 pixel？從 C 語言規格來探討
    * 若要在 CPU cache 與記憶體頻寬受限的嵌入式系統中處理影像，位元操作與 lookup table 為何能顯著改善效能？
* 推導為何 $abs(n) = ((n >> 31) ^ n) - (n >> 31)$ 能正確計算絕對值，回答:
    * 這種 branchless 技巧在 Linux 核心程式碼中特別重要？提供數學分析和產生的機械碼作為解說


為了探究效能差異，我們將傳統的 `if-else` 絕對值寫法與 Branchless 寫法透過 GCC 編譯器（x86-64 架構，-O2 最佳化）編譯，並對照其產生的機械碼指令。

1. 傳統條件分支寫法 (Branching)
C 語言原碼：
```C
int abs_branch(int n) {
    if (n < 0) return -n;
    return n;
}
```

對應的 x86-64 組合語言：
```
abs_branch:
    mov     eax, edi      ; 將參數 n 放入暫存器 eax
    test    eax, eax      ; 測試 eax 的數值 (與 0 比較)
    jns     .L2           ; 若非負數 (Jump if Not Sign)，則跳躍至 .L2
    neg     eax           ; 若為負數，執行二補數反轉 (取相反數)
.L2:
    ret                   ; 回傳結果
```
2. 無分支位元運算寫法 (Branchless)
```C
int abs_branchless(int n) {
    int mask = n >> 31;
    return (n ^ mask) - mask;
}
```
對應的 x86-64 組合語言：
```
abs_branchless:
    mov     eax, edi      ; 將參數 n 放入 eax
    mov     edx, edi      ; 複製 n 到 edx
    sar     edx, 31       ; 算術右移 31 位，產生全 0 或全 1 的遮罩 (mask)
    xor     eax, edx      ; 執行 n ^ mask
    sub     eax, edx      ; 執行減去 mask
    ret                   ; 回傳結果
```
3. 效能優勢底層剖析：管線化 (Pipelining) 與分支預測 (Branch Prediction)

表面上，傳統寫法在非負數時只需執行 2 個指令，似乎比無分支寫法的 4 個指令更有效率。然而，現代 CPU 的執行效能並非單純計算指令數量，而是受制於「超純量管線化架構 (Superscalar Pipeline)」。

在傳統寫法中，`jns` 是一個條件跳躍指令。CPU 為了維持管線滿載，必須依賴「分支預測器 (Branch Predictor)」在 `test` 指令得出結果前，就先「猜測」要不要跳躍，並預先載入後續指令。
- 若預測成功：執行速度較快。
- 若預測失敗：CPU 必須將已經進入管線的錯誤指令全部作廢（Pipeline Flush），重新從正確的位址載入指令。這個懲罰（Penalty）在現代微架構中高達接近十個或更多個時脈週期（Clock Cycles）。

在作業系統核心（如加密演算法、封包處理、排程計算）中，處理的數值往往具備高度隨機性，導致分支預測器的準確率大幅下降（接近 50%）。此時，傳統寫法會頻繁觸發 Pipeline Flush，導致效能雪崩。

相反地，Branchless 寫法（`sar`, `xor`, `sub`）沒有任何條件跳躍指令。CPU 可以完美地將這些算術指令排入管線，無論輸入數值為何，執行時間完全固定（Constant Time），徹底免疫了分支預測失敗的懲罰。這就是在底層系統程式設計中，位元運算往往比邏輯判斷更受青睞的根本原因。




* 在現代 CPU 的 branch predictor 與 pipeline 存在的情況下，branchless 寫法仍然有優勢嗎？請分析可能的情境。搭配 Linux 核心的 git log 來解說

## 分析〈[類神經網路的 ReLU 及其常數時間實作](https://hackmd.io/@sysprog/constant-time-relu)〉
* 教材提及利用 `union` 與位移運算實作 ReLU 的方法，其概念是利用浮點數與整數共用記憶體，藉由檢查 sign bit 判斷輸入是否為負數，並建立遮罩完成條件選擇，回答以下:
    * 該實作依賴 `int32_t` 的算術右移行為來複製 sign bit。請說明為何在大多數現代處理器上此方法可行，但在 C 語言標準層面仍存在未完全保證的行為。列舉 C 語言規格書內容和處理器指令的語意 (semantics)
    * 在 Linux 核心中，若要撰寫類似依賴位元語義的程式碼，通常會如何避免 implementation-defined behavior？請舉出 Linux 核心中常見的做法，例如使用特定型別、巨集或輔助用函式
    * 倘若 ReLU 函式需要被納入 Linux 核心的數值處理路徑中，例如某種 AI 推論模組，請討論 Linux 核心開發者是否會接受 union 型別轉換的寫法，還是傾向其他方式。說明理由並提出替代實作
* 藉由位元操作可達成 branchless 計算，即避免使用條件分支來判斷 `x < 0` 的情況，回答以下:
    * 在現代 CPU pipeline 中，branchless 實作可能比條件分支更快。說明造成此現象的原因，並討論 branch predictor 在其中的角色。設計實驗並用 perf 驗證
    * [Linux 核心中的 `min()` 和 `max()` 巨集](https://hackmd.io/@sysprog/linux-macro-minmax)如何實作，其考量是什麼？
    * 考慮上述程式碼在具備 SIMD 的處理器使用，如 AVX 或 RISC-V Vector extension (RVV)，branchless 設計會可帶來什麼額外優勢？提供程式碼和相關分析
* ReLU 其一特性是產生稀疏輸出，也就是負值會被截斷為零，導致許多節點沒有貢獻。在 Linux 核心中，找出類似稀疏化帶來效能優勢的案例 (提示: git log) 並充分探討
* 利用 union 共享記憶體，使 `float` 與 `int32_t` 可直接存取相同位元表示，該技巧本質是種 type punning。請解釋 strict aliasing rule 與此技巧之間的關係。
    * 在 GCC 或 Clang 編譯 Linux 核心時，為何 Linux 核心程式碼仍能安全地使用某些 type punning 手法
    * 若在使用者空間程式中需要安全地取得浮點數的 sign bit，請提出至少二種做法，並比較其可攜性與效能

## 分析〈[從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt)〉
* 在 Linux 核心中，由於浮點運算通常不可用，許多數值計算必須使用整數或固定點數實作，例如 `int_sqrt()` 或 digit-by-digit 類型的平方根演算法。回答以下:
    * 假設你要在 Linux 核心中實作 `isqrt()` 函式，用來計算 32 位元整數的平方根。分析以下在核心環境中的可行性與成本: 1) 二分逼近法; 2) 牛頓法; 3) digit-by-digit 方法
    * 在 Linux 核心環境中不能使用浮點數的情況下，牛頓法需要哪些改寫才能安全使用？詳盡探討固定點數或整數除法可能帶來的誤差來源，以及迭代停止條件該如何設計
* Linux 核心常要求演算法具備 [predictable execution time](https://en.wikipedia.org/wiki/Worst-case_execution_time)，比較二分逼近法和牛頓法在最壞情況執行時間 (WCET) 上的差異，並說明何者更適合即時 (real-time) 系統。
* 假設輸入值來自不可信來源 (例如網路封包解析)，設計安全版本的 `isqrt()`，並說明如何避免整數溢位、除以零，和無限迴圈
* 教材說明固定點定理以及 contraction mapping 條件，並指出若函數導數滿足 $|g'(x)| < 1$，則迭代序列會收斂到唯一固定點。將此概念延伸到系統程式設計的情境：
    * 在 Linux 核心中，許多子系統藉由 feedback control 調整系統狀態，如 CPU frequency scaling, TCP congestion control, memory reclaim 等，選擇其中一機制，說明其更新規則為何可視為固定點迭代過程。提供數學模型和對應程式碼分析
    * 設計自動調整 CPU load balancing 參數的機制，請提出簡單的迭代更新公式，並分析其收斂條件
* 教材討論固定點迭代的收斂階數 (order of convergence)，並指出牛頓法具有二次收斂，而一般固定點迭代通常只有線性收斂。假設數值演算法每次迭代的成本為 (C)，而收斂速率可為線性收斂和二次收斂，在實際系統中何者可能更有效率，並考慮每次迭代的計算成本、分支預測，及 cache locality
* 在 Linux 核心中，有些演算法會刻意避免 division，而改用 bit shift 或查表。說明：
   * 為何 division 在某些架構上特別昂貴，搭配 git log 來解讀
   * 這如何影響數值演算法設計
* 針對 digit-by-digit 的平方根計算方法，該方法只需加減與位移運算 。為何該方法特別適合 Linux 核心？若你要為 RISC-V 架構設計新的 `sqrt` 指令，digit-by-digit 方法與牛頓法何者更適合作為硬體微架構 (microarchitecture) 的基礎？請說明原因。
* 教材展示某些固定點迭代可能會發散甚至產生 `nan` 的案例，回答:
    * 在系統程式設計中，數值演算法發散可能造成哪些實際問題，例如 scheduler decision 和 network congestion control，以 Linux 核心原始程式碼進行探討
    * 說明為何在 Linux 核心程式碼有時會加入保護式界限(clamping)，並舉例說明其與數值穩定性的關係

## 探討〈[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`，以嚴謹的數學推導此巨集的正確性
    * 若 `n` 或 `d` 可能為負數，該巨集可能出現錯誤結果。請設計可在 Linux 核心中安全使用、同時仍盡量避免分支的版本，並說明設計考量
* Linux 核心原始程式碼提供 `do_div` 巨集，可在一次操作中取得 64 位元整數除法的商與餘數。回答以下：
    * 在某些架構 (例如部分 Arm 平台，缺乏 FPU) 上，編譯器可能將 64 位元除法轉換為呼叫 `__aeabi_uldivmod`。說明為何 Linux 核心會刻意避免依賴這類 libgcc 函式
    * 假設你正在實作 Linux 核心中的時間子系統，需要頻繁將奈秒 (ns) 轉換為毫秒 (ms)，討論以下實作方式的優缺點： a) 使用一般 `/` 運算子; b) 使用 `do_div`; c) 將除法轉換為乘法與位移
* Linux 核心 `vsprintf` 中的十進位轉換實作會避免直接使用除法，而改用乘法與查表方式來提升效能。回答以下:
    * 為何 `/proc` 與 `/sys` 的輸出效能會影響整體系統效能？以實際的測試來說明
    * 假設你需要在 Linux 核心中實作頻率統計 (histogram) 輸出函式，每秒可能被呼叫數十萬次，則直接使用 `sprintf` 可能帶來哪些效能問題？為何查表法能改善效能？
* 某些特殊常數除數可以讓編譯器將除法完全轉換為單一乘法，例如： `⌊n / 274177⌋ = (n × 67280421310721) >> 64`，回答以下:
    * 為何這類除數被稱為「理想除數」？說明其數學背景
    * 假設 Linux 核心 scheduler 需要頻繁計算某個比例值，如 `scaled = load / 274177`，分析使用上述技巧可能帶來的效益與風險
    * 若你是編譯器設計者，會如何在最佳化階段自動偵測並套用此類轉換？

## 細讀〈[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 繪製指標關係圖說明原因
    * 說明 hlist 的設計如何消除上述特殊情況。解釋 `__hlist_del()` 的行為並探討其效益
* Linux 核心在 `hash_32()` 中使用乘法雜湊 `val * GOLDEN_RATIO_32 >> (32 - bits)`，其中 `GOLDEN_RATIO_32 = 0x61C88647` 是黃金比例相關常數。探討以下：
    * 解釋為什麼 Linux hash 函數會取「高位元」作為 bucket index，而不是低位元
    * 若 bucket 數量為 `2^p`，說明右移 `(32 - p)` 的數學意義
    * 假設系統中 key 值具有模式 `K, K + d, K + 2d, K + 3d, ...`，例如連續的 file descriptor 或 PID。說明為何使用 golden ratio 乘法可以減少 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`，需要多少記憶體？
    * 若該 hash table 用於 networking subsystem（例如 connection tracking），bucket 數量非常大但每個 bucket 的元素數量通常很少，說明為何 hlist 是更合理的設計
    * hlist 無法在 O(1) 時間取得 tail，討論在什麼情況下 Linux 核心仍會選擇 `list_head` 而非 `hlist`
    * 舉出 Linux 核心中二個實際使用 hash table 的子系統（例如 dentry cache、routing table 或 TCP connection lookup），並分析其 bucket collision 的行為會如何影響系統效能
* Linux 的雜湊表的設計實際結合三個層面的考量：1) 雜湊函數的統計性質; 2) 資料結構的記憶體布局; 3) CPU cache 與指標操作成本。回答以下：
    * 若 bucket collision 過多，查找時間將從期望的 $O(1)$ 退化為 $O(n)$，在 Linux 核心中，這種退化可能造成哪些實際系統效應？
    * 假設某個攻擊者可以控制輸入 key（例如 HTTP header 或網路封包欄位），並刻意製造大量 hash collision。說明這種攻擊如何影響系統效能，並舉出 Linux 或其他系統曾出現的類似案例 (提示: git log)
    * 設計改進方案，使雜湊表在碰撞過多時仍能維持穩定性能，應適度考慮 bucket resize, alternate hashing, tree-based bucket, randomized hashing 等手法，並分析這些方法在 Linux 核心中的可行性 (後續可提交貢獻到 Linux 核心)
* 教材提到 Fibonacci hashing 與 Three-gap theorem 的數學背景。回答以下:
    * 為何 Linux 核心實作 hash 函數時，偏好使用整數運算與 bit shift，而非浮點運算？
    * 將數學式 $h(K) = \lfloor m (KA - \lfloor KA \rfloor) \rfloor$ 轉換為 Linux 核心實際程式碼形式並解釋每個步驟對應的位元操作
    * 若系統由 32 位元架構改為 64 位元架構，hash 函數應如何調整？
* 把 `GOLDEN_RATIO_64` 放回環論語境，探討可逆性與雜湊不可逆性的差異
    * 在環 $R=\mathbb{Z}/2^{64}\mathbb{Z}$ 中，判定 `GOLDEN_RATIO_64` 是否為 unit。必須給出判定條件與理由 (提示: 奇偶性與 $\gcd(C,2^{64})$)
    * 若它可逆，說明你如何以擴展歐幾里得演算法求出 $C^{-1}\bmod 2^{64}$，隨後解釋即使乘法在 $R$ 中可逆，為何 `hash_64(val,bits)` 依然不可逆。你必須指出右移取高位元等價於丟棄資訊、丟棄的位元數量與 preimage 的大小關係，並把這點連結到雜湊表只需要分布性，而不需要可逆性

## 細讀〈[為什麼要深入學習 C 語言？](https://hackmd.io/@sysprog/c-standards)〉
* 在 Linux 核心原始程式碼和 git log，找出，哪些「編譯器行為差異」會被視為 bug，而非「容忍實作差」的案例
* object 與 pointer 的視角如何影響核心中的 API 契約？教材提及 object 是執行時期中「資料儲存區域」的語意單元，pointer 只是其存取表達 ，也點出 `void *` 與字元型別指標在表示法與對齊需求的一致性。回答以下：
    * Linux 核心的 `copy_from_user` 一類的函式中，若以「object 邊界」定義安全，應該如何表達契約？
    * 針對核心常見的巨集，如 `container_of`，從 object model 觀點分析它倚賴哪些假設、哪些假設其實屬於 compiler extension？
* 教材列出 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__`
    * 探討 `_BitInt(N)` 是否能改善 Linux 核心在不同處理器架構中，位元精準資料結構與 ABI 表述

## 探討〈[基於 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` 的情況有何不同？
    * 在 Linux 核心的歷史漏洞中，常見於 `access_ok(type, addr, size)` 或類似的記憶體範圍檢查巨集。假設開發者寫出 `if (user_len < 0 || user_len > MAX_LEN)`，但 `MAX_LEN` 被定義為 `unsigned` 常數，而 `user_len` 是 `signed`
    * 請編譯器（如 GCC）在產生組合語言時，會使用邏輯比較（`CMP` 指令後接 `JA/JB`）還是算術比較（`JG/JL`）？這如何導致負數的 `user_len` 繞過檢查並在後續 `copy_from_user` 中造成巨大的 kernel heap overflow？
    * 結合文件提到的 "wraparound"，當攻擊者控制 `size` 參數造成 integer underflow，這在核心層級（kernel space）的 `kmalloc(size)` 配置中，與使用者層級的 `malloc` 行為有何本質上的不同 (考量到 SLUB 配置器的行為)？
* C11 §6.2.4.2 關於物件生命週期的定義是，當物件生命週期結束，指標的值變為不確定 (indeterminate)，回答以下:
    * 在現代 C 語言編譯器模型（如 LLVM 的 [PNVI-ae-udi 模型](https://inria.hal.science/hal-02089907/file/n2363.pdf)）中，即使兩個指標 `p` (已釋放) 和 `q` (新配置) 的記憶體地址（數值）相同，它們在語意上是否相等？
    * 討論 Alias Analysis（別名分析）如何利用 "Strict Aliasing Rule" 或 "Object Lifetime" 假設，認定對 `q` 的寫入不會影響 `p` 指向的內容，進而對程式碼進行激進的最佳化 (例如刪除看似多餘的 null check)
    * 考慮以下程式碼:
    ```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），導致該程式碼無條件執行？這對漏洞防護機制的實作有何啟示？
* 文件分析 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" 類的攻擊？
    * Exim 的 `store_release` 只是移動指標，並未真正清除資料。這與 Linux 的 [RCU (Read-Copy-Update)](https://hackmd.io/@sysprog/linux-rcu) 機制中的 "Grace Period" 有何異同？
    * 該漏洞的關鍵在於 `store_extend` 失敗後，程式邏輯誤以為舊區塊仍有效，但實際上指標已指向被釋放 (或即將被重用) 的區域。對照 Linux 核心的 `krealloc` 函式實作，當 `krealloc` 原地擴充（resize in place）失敗而必須移動記憶體時，如何處理舊指標？Linux 核心如何避免類似 Exim 這種「舊指標指向已釋放區域」的 race condition？
* 文件 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` 視為無用程式碼並刪除？
    * 比較 C11 Annex K 引入的 `memset_s` 及 Linux 核心中的 `memzero_explicit`。這些函式在實作層面上使用哪些技巧 (例如 `volatile` 關鍵字或 memory barrier) 來強迫編譯器保留清除指令？這與文件中提到的「物件生命週期」概念有何衝突與妥協？

## 探討〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉
* C 語言規格指出 `void *` 可與任何物件指標互相轉換，並且其 representation 與 alignment requirement 與 `char *` 相同，但 ISO C 不允許直接對 `void *` 進行 pointer arithmetic。從 C 語言型別系統與記憶體模型的角度，說明以下：
    * 為何 C 語言需要 `void *` 這種「無型別指標」(提示: C 語言規格書)？這種設計如何支援泛型資料結構（例如 `malloc`、鏈結串列、資料容器函式庫）？
    * 為何 ISO C 不允許對 `void *` 進行 pointer arithmetic，這反映什麼設計考量？
    * 為何 `void *` 可安全轉換為 `int *` 再轉回，但 `void *` 與 `void **` 的轉換卻可能導致未定義行為？
* Linux 核心程式碼中少用 `void *` arithmetic，而是轉型為 `char *` 或其他型別後再計算位址。說明考量因素並分析其與 strict aliasing rule 的關聯
* `malloc` 可能回傳有效指標，但實際的實體記憶體尚未配置，只有在程式首次存取該記憶體時才會真正配置 page。回答以下:
    * 說明虛擬記憶體 (virtual memory) 的基本概念，及為何使用者行程只能看到虛擬位址，硬體設計者的考量是什麼？
    * 解釋 demand paging 的運作流程，包含 page fault 發生後 Linux 核心需要進行的主要步驟
    * 為何 `malloc()` 的回傳值無法直接對應到保證記憶體一定可用？在什麼情況下首次存取記憶體可能觸發 OOM？
    * Linux 的 memory overcommit policy 為何允許系統配置超過實體記憶體容量的虛擬記憶體？該設計在伺服器系統與高效能運算環境中有哪些優缺點？以 Linux 核心原始程式碼內附的文件和原始程式碼進行解讀
* CPU 存取資料通常以 word 或 cache line 為單位，若資料未對齊可能需要多次記憶體讀取或額外硬體操作，回答以下：
    * 為何 CPU 偏好對齊的記憶體存取？以 4-byte integer 為例，說明 aligned 與 unaligned access 的差異，搭配 Graphviz 繪製記憶體佈局圖
    * 若一個 4-byte integer 位於 address `0x01`，CPU 可能需要執行哪些額外操作才能完成存取？
    * 為何 x86(-64) 架構通常允許 unaligned access，而某些 RISC 架構（如 ARM 或 RISC-V）可能需要額外指令甚至觸發例外？
    * Linux 核心提供 `get_unaligned()` 與 `put_unaligned()` 等工具函式，其設計目的為何？在跨平台核心程式碼中為何重要？
* 由於結構體與指標通常具有 alignment 保證，因此位址的最低幾個 bit 永遠為 0，可被用作額外資訊，例如在 [lock-free linked list](https://hackmd.io/@sysprog/concurrency) 中標記節點已被邏輯刪除。
    * 為何 alignment 可保證某些位元永遠為 0？若系統保證 8-byte alignment，最低幾個 bit 可以安全使用？
    * 為何 lock-free linked list 常使用 logical deletion 而非立即刪除節點？
    * pointer tagging 如何協助實作這種邏輯刪除機制？
    * Linux 核心中哪些資料結構或同步機制使用類似技術 (提示: RCU 或其他 lock-free container)？
* 說明 glibc `malloc` 設計的關鍵原理與其在多執行緒環境中的限制：
    * 為何 `malloc` 需要 arena 機制？它如何減少多執行緒競爭？
    * 為何 thread arena 通常使用 `mmap()` 而不是 `brk()` 取得記憶體？
    * 為何 fastbin 在 `free()` 時不會立即合併 chunk，而 small bin 與 large bin 則會？
    * 為何在[高度並行](https://hackmd.io/@sysprog/concurrency)伺服器程式中，glibc malloc 可能成為效能瓶頸？這也是為何出現 jemalloc、tcmalloc 等 allocator 的原因
* 教材提及的記憶體配置器屬於使用者空間的實作，但 Linux 核心並不使用 glibc `malloc`，而有自己的記憶體配置器，如 slub 與 `kmalloc()`。
    * 為何 Linux 核心不能直接使用 glibc `malloc`？
    * `kmalloc()` 與 `vmalloc()` 在記憶體配置方式與位址連續性方面有何不同？
    * slab / slub 為何對核心資料結構特別重要？
    * Linux 核心環境中，記憶體配置器的設計為何特別強調 deterministic behavior 與 cache locality？搭配 git log 來說明 Linux 核心的相關演化

## 細讀〈[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 語言規格書找出對應的描述
    * 若改為 `struct { unsigned int a : 1;};`，其語意會如何改變？
    * Linux 核心原始程式碼如何使用 C bit-field 來表示旗標？為何還有 set_bit(), clear_bit(), test_bit() 等操作？
* 說明在 Linux 核心中使用 bit-field 需要考慮到 1) ABI; 2) 編譯器差異; 3) 記憶體 layout 不可預測。並搭配 git log 舉例說明這些考量
* 教材提到 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` 的語意是什麼？
    * 為何 `c` 與 `d` 可能落在不同的記憶體區域？
    * 為何在不同編譯器（例如 gcc 和 clang）中結果可能不同？
    * 以 C 語言規格的觀點，解釋教材聲明的「`c` 和 `d` 可能指向不同記憶體區域，因此結果可能不穩定」的根本原因
* Linux 核心在結構對齊上幾乎不用 zero-width bit-field，而是使用 `__aligned()` 或 `__attribute__((aligned))`，回答以下：
    * 為何 Linux 核心避免使用 zero-width bit-field？
    * 若在 Linux 核心中使用 bit-field 進行硬體暫存器映射，可能會出現什麼問題？以 memory-mapped IO (MMIO) 暫存器操作為例說明

* 教材提及 Linux 核心的技巧 `#define BUILD_BUG_ON_ZERO(e) (sizeof(struct { int:(-!!(e)); }))`，從 C 語言規格的角度回答以下:
    * `!!(e)` 的作用是什麼？為何 `-!!(e)` 可能變成 `-1`？為何 `int : -1` 會導致編譯時期的錯誤？
    * 為何 `int : 0` 是合法的？
    * 對應到 C11 以上的規格，有哪些替代方案？
* C11 規格指出，同一個結構體中的二個 bit-field 若位於同一記憶體位置，並行更新不安全。考慮 `struct flags { unsigned a : 1; unsigned b : 1; };`，假設 CPU~0~ 修改 `a` 且 CPU~1~ 修改 `b`，回答以下：
    * 為何這兩個操作可能發生 race condition？
    * bit-field 修改通常需要什麼指令序列？以 C11 (含之後) 規格書內文來解讀