# 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 (含之後) 規格書內文來解讀
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet