--- tags: linux2026 --- # [2026q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 5 週測驗題 > [作答表單](https://forms.gle/xG7xPzfKLwJrA3dS7) :::warning :warning: 回答延伸問題時，務必優先以[課程教材](https://wiki.csie.ncku.edu.tw/linux/schedule)為主要出處，隨後參照 C 語言規格書、Linux 核心原始程式碼及其 git log 和 LKML (Linux Kernel Mailing-List)，和權威素材 (如 GCC 和 glibc 手冊，但絕對不是 CSDN 或者尋常的網路日誌/筆記) AI 工具是輔助性質，可用來撰寫測試程式碼和收集資訊，但主要的推測、查證、分析，和討論，都該由人類進行。 ::: 本測驗以 CS:APP (Computer Systems: A Programmer's Perspective) 第二章練習題為基礎，結合 Linux 核心原始程式碼，探討 bitwise operation、浮點數值系統及 C 語言規格中的未定義行為。每題 Part 1 保留原始 CS:APP 練習原文，Part 2 以 Part 1 的概念為基礎，搭配 Linux 核心中的實際應用設計延伸填空。填空答案接受代數上等價的 C 運算式 (例如 `(sx&y)+(sy&x)` 與 `(sy&x)+(sx&y)` 等價)。 注意須知： * 標示為 `Part 1` 是 CS:APP 書本作業題目，在本次測驗中，學員不需要作答 * 學員實際從每個題組的 Part 2 開始作答，但 Part 2 的內容依賴 Part 1，因此學員仍需要閱讀 CS:APP 描述 * 作答的程式碼片段不包含任何空白，以最精簡的形式書寫，不該包含 `?` 和 `;` 字元 * 關於 C 語言規格書的術語，全部小寫，至多一個半行空白字元 * 十六進位的數值一律用大寫表示，也就是 ABC 而非 abc；32 位元值以 8 位數字表示 (含前導零，例如 `00200000`) * 數值常數填空以十進位整數作答 (例如 `112` 而非 `127-15` 或 `0x70`)，除非題目另有指定 --- ## Problem A: 位元組替換與遮罩運算 > 延伸 CS:APP 2.60 - [ ] Part 1: replace_byte :::info 對應到 CS:APP 的 2.60 ::: - [ ] Part 2: Linux 核心的位元欄位操作 網路介面卡、GPU、USB 控制器等硬體裝置以 memory-mapped I/O (MMIO) 暴露控制暫存器。典型的硬體暫存器將 32 位元空間切分為多個欄位：以 PCI 組態空間的 Command Register (offset 0x04) 為例，bit 0 控制 I/O 存取、bit 1 控制記憶體存取、bit 2 為 bus master 啟用：驅動程式修改其中一個位元時，不能破壞其餘位元的狀態，因此必須執行 read-modify-write：先讀取整個暫存器、以遮罩清除目標欄位、填入新值、再寫回。這個「清除再填入」的操作，邏輯上等同 Part 1 的 `replace_byte`。 早期 Linux 核心驅動程式各自手寫位移與遮罩常數，散見 `(val >> 4) & 0xF` 之類的 magic number，不僅難以審閱，也容易因欄位邊界算錯而引入安全漏洞。對 MMIO 暫存器而言，寫入錯誤的位元欄位可能觸發 DMA 至非預期的記憶體位址，後果比一般的記憶體損壞更嚴重。Linux 核心自 v4.9 起在 [`include/linux/bitfield.h`](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 統一定義 `FIELD_PREP` 和 `FIELD_GET` 巨集，將此手法標準化： ```c /* include/linux/bitfield.h (節錄，經簡化) */ #define __bf_shf(x) (__builtin_ffsll(x) - 1) #define FIELD_PREP(_mask, _val) \ ((typeof(_mask))(((_val) << __bf_shf(_mask)) & (_mask))) #define FIELD_GET(_mask, _reg) \ ((typeof(_mask))(((_reg) & (_mask)) >> __bf_shf(_mask))) ``` `FIELD_PREP` 將值左移至遮罩位置再以 AND 裁切，`FIELD_GET` 以 AND 取出欄位再右移回最低位元。Part 1 的 `replace_byte` 等同於對 8-bit 欄位執行清除再填入。 從代數的角度，$w$ 位元字組在 XOR 運算下構成阿貝爾群 $(\mathbb{F}_2^w, \oplus)$，亦即有限體 $\text{GF}(2)$ 上的 $w$ 維向量空間，每個元素都是自身的加法反元素 ($a \oplus a = 0$)。AND 運算 `x & mask` 是此向量空間上的投影：保留 `mask` 為 1 的座標分量、清除為 0 的分量。`replace_byte` 的 `(x & ~mask) | (b << shift)` 正是對二個互補子空間 (遮罩位元與非遮罩位元) 分別取值後以 OR 合併：OR 在互補遮罩的前提下等效於向量加法。核心的 [`include/linux/bitops.h`](https://github.com/torvalds/linux/blob/master/include/linux/bitops.h) 提供的 `hweight_long()` (Hamming weight，即 popcount) 滿足次可加性 (subadditivity)：$\text{hweight}(a \oplus b) \leq \text{hweight}(a) + \text{hweight}(b)$，等號在 $a$ 與 $b$ 無共同置位位元時成立 (注意 `hweight` 不是群同態：取 $a = b$ 即得 $\text{hweight}(0) = 0 \neq 2 \cdot \text{hweight}(a)$)。 實務上，裝置驅動程式以 `FIELD_PREP(GENMASK(h, l), val)` 組合使用這二個巨集。[`include/uapi/linux/bits.h`](https://github.com/torvalds/linux/blob/master/include/uapi/linux/bits.h) 定義的 `GENMASK(h, l)` 以 `(((~_ULL(0)) << (l)) & (~_ULL(0) >> (__BITS_PER_LONG_LONG - 1 - (h))))` 搭配減法產生 bit $l$ 至 bit $h$ 連續為 1 的遮罩，Hamming weight 恰為 $h - l + 1$。此巨集以 `unsigned long` 運算避開 `1 << 32` 在 32 位元平台觸發的未定義行為 (見 Problem B)。`__bf_shf()` 內部呼叫 `__builtin_ffsll` 取得遮罩最低有效位元位置，在 x86 對映至 `bsf` 或 `tzcnt` 硬體指令：前者對零輸入的行為在 Intel SDM 標示為 undefined，核心以 `BUILD_BUG_ON_ZERO` 在編譯期確保遮罩不為零，使此 undefined 行為永遠不被觸發。以 Intel i225 網路控制器驅動程式 ([`drivers/net/ethernet/intel/igc/igc_defines.h`](https://github.com/torvalds/linux/blob/master/drivers/net/ethernet/intel/igc/igc_defines.h)) 為例，暫存器欄位以 `GENMASK` 定義遮罩、`FIELD_PREP` 填入值、`FIELD_GET` 讀出值，三者構成完整的欄位存取抽象，取代早期散布於各驅動程式的手動位移常數。 以下推廣為連續 $n$ 個位元組的替換；當 $n = 1$ 時，`replace_nbytes(x, i, 1, b)` 應與 Part 1 的 `replace_byte(x, i, b)` 結果相同。填空 __ A01 __ 與 __ A02 __ 的運算邏輯應直接對應 Part 1 `replace_byte` 中清除原位元與填入新值的步驟，推廣至任意寬度欄位： ```c /* Assume 32-bit unsigned, 0 <= i <= 3, 1 <= n <= 4-i */ unsigned replace_nbytes(unsigned x, int i, int n, unsigned y) { unsigned shift = i << 3; unsigned width = n << 3; unsigned mask = (n == 4) ? ~0u : ((1u << width) - 1); return (x&~(__A01__))|((y&__A02__)<<shift); } ``` `mask` 以 `(1u << width) - 1` 產生。當 $n = 4$ 時 $\text{width} = 32$，`1u << 32` 依 C99 6.5.7 §3 屬於 __ A03 __ ，故以 `~0u` 特例處理。 驗證：`replace_nbytes(0xAABBCCDD, 0, 3, 0x112233)` = `0x` __ A04 __。 自我檢查 (非填空)：`replace_nbytes(0x12345678, 1, 2, 0xABCD)` 中 `shift = 8`，`mask = 0xFFFF`；清除 `0x12345678 & ~(0xFFFF << 8) = 0x12000078`，填入 `(0xABCD & 0xFFFF) << 8 = 0x00ABCD00`，結果為 `0x12ABCD78`。當 $n = 1, i = 2, y = \text{0xAB}$ 時應與 Part 1 的 `replace_byte(x, 2, 0xAB)` 結果一致。 自我檢查 ($n = 4$ 特例)：`replace_nbytes(0x12345678, 0, 4, 0xAABBCCDD)` 中 `mask = ~0u` (因 `n == 4` 走特例路徑)，`shift = 0`；清除 `0x12345678 & ~(~0u) = 0`，填入 `0xAABBCCDD & ~0u = 0xAABBCCDD`，結果為 `0xAABBCCDD`，完整替換所有 4 個位元組。 延伸閱讀：手動位移與遮罩運算容易出錯，屬 [CWE-682](https://cwe.mitre.org/data/definitions/682.html) (Incorrect Calculation)。`__bf_shf()` 內部以 `__builtin_ffsll` 取得遮罩最低有效位元的位置，此 GCC 內建函式在 x86 對映至 `bsf` 或 `tzcnt` 硬體指令，開銷極低。Marvell libertas 無線驅動程式的 [CVE-2019-14896](https://nvd.nist.gov/vuln/detail/CVE-2019-14896) 即為一例：`lbs_ibss_join_existing()` 在解析 IBSS 加入回應封包時，未檢驗 rates IE 的長度欄位即以該值作為 `memcpy` 的複製大小，遠端攻擊者可傳入超長 IE 觸發堆積溢位。此漏洞的根因是手動解析封包欄位時缺乏邊界檢查，與 `replace_nbytes` 中 `n` 超出合理範圍的情境類似。核心中愈來愈多子系統改用 `FIELD_PREP`/`FIELD_GET` 取代零散的手動位移，以降低此類手動計算出錯的風險。 ### 延伸問題 * `FIELD_PREP`/`FIELD_GET` 以 `__builtin_ffsll` 計算遮罩最低有效位元位置，在 x86 對映至 `bsf`/`tzcnt` 指令。以此為出發點： * (a) `bsf` 對輸入為零的行為在 Intel SDM 中標示為 undefined，而 `tzcnt` (BMI1 擴充) 對零輸入回傳運算元位元寬度。閱讀 `include/linux/bitfield.h` 的 `__bf_shf()` 實作，說明核心如何以編譯期靜態檢查 (`BUILD_BUG_ON_ZERO`) 確保遮罩不為零，使 `bsf` 的 undefined 行為永遠不被觸發。從 C99 6.3.1.1 (integer promotion) 的角度，分析 `__builtin_ffsll(x) - 1` 在遮罩恰為 `1ULL << 63` 時的回傳值，以及此值作為位移量是否觸發 C99 6.5.7 §3 的未定義行為 * (b) [CVE-2019-14896](https://nvd.nist.gov/vuln/detail/CVE-2019-14896) 的 Marvell libertas 驅動程式在 `lbs_ibss_join_existing()` 中未檢驗 rates IE 長度即用於 `memcpy`，導致 heap overflow。閱讀 [`drivers/net/wireless/marvell/libertas/cfg.c`](https://github.com/torvalds/linux/blob/master/drivers/net/wireless/marvell/libertas/cfg.c) 的修補紀錄，說明原始程式碼在哪一步以使用者可控的長度值計算複製範圍而未設上限。此漏洞的根因是，手動解析欄位時缺乏邊界驗證，與 Part 2 中 `(1u << width) - 1` 在 `width = 32` 時溢位的問題屬同一類別：手工計算欄位參數容易遺漏邊界條件。設計一個以 `FIELD_PREP`/`FIELD_GET` 搭配 `min_t()` 限制長度的改寫方案，並從攻擊者的角度分析：若驅動程式的暫存器寫入巨集使用了錯誤的遮罩寬度 (偏移 1 位元)，寫入硬體 DMA 描述子的位址欄位如何造成相鄰堆積物件被覆寫 * \(c) `replace_nbytes` 中 `n == 4` 的特例處理 (`~0u`) 源自 `1u << 32` 在 32 位元平台的未定義行為。Linux 核心的 `GENMASK(h, l)` 以 `(~UL(0) >> (BITS_PER_LONG - 1 - h))` 迴避此問題。從環論 $\mathbb{Z}/2^w\mathbb{Z}$ 的角度，證明 `~UL(0) >> k` 在 $k \in [0, w-1]$ 範圍內產生的遮罩集合恰為所有「高 $k$ 位元為零、低 $w-k$ 位元為一」的元素，並說明為何 `GENMASK(31, 0)` 在 64 位元平台回傳 `0x00000000FFFFFFFF` 而非 `0xFFFFFFFFFFFFFFFF`，此行為在 PCI BAR 位址解碼等需區分 32/64 位元暫存器的情境下為何是正確的 --- ## Problem B: 位移寬度與未定義行為 > 延伸 CS:APP 2.67 - [ ] Part 1: int_size_is_32 :::info 對應到 CS:APP 的 2.67 ::: - [ ] Part 2: Linux 核心如何避免位移未定義行為 核心程式碼大量使用位元遮罩設定硬體暫存器、旗標欄位與權限位元。C 語言規格將位移量超出型別寬度、有號左移溢位等情況列為未定義行為 (undefined behavior)，編譯器遇到這類程式碼時，可依規格自由假定「此情況不會發生」，進而移除看似「不可能」的分支。 具體而言：GCC 在 `-O2` 下可能假定有號左移不溢位，將 `1 << n` 的結果視為恆正，略過後續的負值檢查。核心以 `-fno-strict-overflow` 降低部分風險，但此旗標僅涵蓋有號算術 (加法、減法、乘法) 與指標溢位的假設，對位移運算的未定義行為並無保護效果。在安全敏感的核心路徑 (如 capability 檢查、SELinux 權限判定) 中，若編譯器因位移 UB 而省略條件分支，攻擊者即可繞過存取控制。早期驅動程式中 `1 << N` 的寫法極為普遍，例如 `drivers/gpu/drm/` 下的 framebuffer 旗標設定、`drivers/net/` 下的中斷遮罩計算，當 $N = 31$ 時結果超出 `int` 可表示範圍。核心自 2017 年起以 Coccinelle semantic patch ([`scripts/coccinelle/misc/`](https://github.com/torvalds/linux/tree/master/scripts/coccinelle/misc)) 批次將此類程式碼改為 `BIT(N)`，涉及數百筆修補。 位移 UB 之外，核心在頂層 Makefile 還設定 `-fno-strict-aliasing`，停用 C99 6.5 §7 的 strict aliasing rule (type-based alias analysis, TBAA)。Strict aliasing 允許編譯器假定不同型別的指標不指向同一物件，據此省略看似「多餘」的記憶體載入。例如 `void process(int *ip, float *fp)` 中，編譯器可假定 `*ip` 與 `*fp` 不重疊，對 `*ip` 的寫入不會影響先前讀取的 `*fp` 值。核心程式碼大量以 `char *`、`void *` 和 union 存取同一記憶體區塊 (如 Problem D 的 `union ieee754sp` 以 `u32 bits` 和 bit-field 結構體共用同一 32 位元)，若啟用 strict aliasing，編譯器可能將透過不同型別指標的存取重排或消除，導致硬體暫存器寫入遺失或資料結構損壞。`-fno-strict-overflow` 與 `-fno-strict-aliasing` 合併使用，是核心對抗「編譯器利用 UB 進行激進最佳化」的兩道防線。Linux 核心以 [`include/vdso/bits.h`](https://github.com/torvalds/linux/blob/master/include/vdso/bits.h) 的 `BIT()` 和 `GENMASK()` 巨集避開 Part 1 揭示的有號位移未定義行為。關鍵差異：以 `unsigned long` 而非 `int` 執行位移，確保結果不會溢位有號型別的可表示範圍： ```c /* include/vdso/bits.h (節錄) */ #define BIT(nr) (UL(1) << (nr)) /* include/linux/bits.h (節錄，經簡化) */ #define GENMASK(h, l) \ (((~UL(0)) - (UL(1) << (l)) + 1) & \ (~UL(0) >> (BITS_PER_LONG - 1 - (h)))) ``` `BIT(31)` 以 `UL(1) << 31` 計算，因 `unsigned long` 至少 32 位元寬，$1 \times 2^{31}$ 仍可表示，不觸發未定義行為。反觀 Part 1 的 `1 << 31` 使用有號 `int`，結果超出可表示範圍。 從代數的角度，左移 $k$ 位元等效於在環 $\mathbb{Z}/2^w\mathbb{Z}$ 中乘以 $2^k$。當 $k < w$ 時，此乘法在環中有明確定義；但 C 語言的位移運算並非嚴格對映至環上的乘法：C99 6.5.7 §3 在 $k \geq w$ 時宣告未定義行為，等於宣告「超出環的階數的乘法不存在」。`unsigned long` 的位移在 $[0, w)$ 範圍內與 $\mathbb{Z}/2^w\mathbb{Z}$ 的乘法一致；有號 `int` 的位移則更危險：C99 6.5.7 §4 規定，即使移位量合法，只要結果超出有號型別的可表示範圍 (如 $2^{31}$ 超出 32 位元 `int` 的 $[-2^{31}, 2^{31}-1]$)，行為同樣未定義。`BIT()` 切換至 `unsigned long` 的做法，本質上是選擇一個足夠大的環，使得目標乘積 $2^k$ 落在環的可表示元素範圍內。 以下嘗試以 Part 1 的策略泛化至判斷 `int` 是否恰為 $w$ 位元 (假設 $16 \leq w \leq 64$，$w$ 為 8 的倍數)： ```c int int_size_is_w(int w) { int high = 1 << (w - 1); int wrapped = high << 1; return high&&!__B01__; } ``` 此函式的意圖：`high` 設定第 $(w - 1)$ 位元，`wrapped` 再左移一位。若 `int` 恰為 $w$ 位元，`wrapped` 在多數平台上歸零。填空 __ B01 __ 為在 `int` 恰為 $w$ 位元時應歸零的變數，請對照 Part 1 的 `bad_int_size_is_32` 邏輯推導。 此泛化版與 Part 1 的 `bad_int_size_is_32` 犯相同錯誤：`high` 和 `wrapped` 的計算本身存在二處未定義行為： * 當 $w$ 等於實際 `int` 寬度時 (例如 32 位元機器上呼叫 `int_size_is_w(32)`)，`1 << 31` 使 $1 \times 2^{31}$ 超出 `int` 可表示範圍。依 C99 6.5.7 §4：對非負有號整數左移，若結果無法以該型別表示，行為屬於 __ B02 __ 。 * 當 $w$ 超過實際 `int` 寬度時，`1 << (w - 1)` 的移位量 $\geq$ 型別寬度，觸發 C99 6.5.7 §3 的同類行為。 二處未定義行為使此函式不具可移植性，正如 Part 1 所揭示。Linux 核心的 `BIT()` 改用 `unsigned long`，避免有號左移溢位的未定義行為；但呼叫端仍須確保位移量在 `[0, BITS_PER_LONG)` 範圍內，否則同樣觸發 C99 6.5.7 §3 的未定義行為。 延伸閱讀：有號位移溢位屬 [CWE-758](https://cwe.mitre.org/data/definitions/758.html) (Reliance on Undefined Behavior)。UBSan (`CONFIG_UBSAN`) 在核心啟用後，會對每次位移操作插入執行期檢查，搭配 syzbot 模糊測試持續偵測此類缺陷。Coverity 的靜態掃描亦將有號位移列為高優先級告警。核心在 2009 年因 gcc-4.1.x 的 `-fwrapv` 實作有 bug (導致核心無法完成 init 啟動) 而改用 `-fno-strict-overflow`，二者對加法、減法、乘法的溢位假設效果相同。但無論是 `-fwrapv` 或 `-fno-strict-overflow`，都僅涵蓋算術運算子 (`+`、`-`、`*`) 的溢位語意，對位移運算的未定義行為 (C99 6.5.7 §3/§4) 不提供任何保護，而 `BIT()` 搭配 `unsigned long` 才是正解。 ### 延伸問題 * `BIT()` 以 `UL(1) << (nr)` 避免有號位移溢位，但呼叫端傳入的 `nr` 若超出 `[0, BITS_PER_LONG)` 仍觸發未定義行為。以此為出發點： * (a) GCC 在 `-O2` 下對有號左移溢位可利用 UB 進行激進最佳化。設計一段程式碼，其中 `1 << 31` 的結果被用於條件判斷 (如 `if ((1 << n) > 0)`)，以 GCC `-O0` 和 `-O2` 分別編譯為 x86-64 組合語言，比較產生的分支指令差異。從 C99 6.5.7 §4 的角度解釋：編譯器為何有權假定有號左移結果為正，進而將整個條件分支消除？以 [CWE-758](https://cwe.mitre.org/data/definitions/758.html) 的分類說明此類最佳化在核心安全檢查中的風險 * (b) 閱讀 [`include/linux/bits.h`](https://github.com/torvalds/linux/blob/master/include/linux/bits.h) 的 `GENMASK(h, l)` 巨集完整展開式。當 `h = l` 時 (單一位元遮罩)，`GENMASK` 應退化為 `BIT(h)`。手動展開驗證此等價性，並推導 `GENMASK(h, l)` 產生的遮罩以 popcount 表示恰有 $h - l + 1$ 個置位位元的數學證明 (提示：將遮罩的位元模式視為等比級數 $\sum_{i=l}^{h} 2^i$ 並套用求和公式)。核心在 [`tools/include/linux/bits.h`](https://github.com/torvalds/linux/blob/master/tools/include/linux/bits.h) 另有使用者空間版本，比較二者在型別寬度假設上的差異 * \(c) UBSan (`-fsanitize=undefined`) 的 shift sanitizer 會在執行期攔截位移量超出範圍或有號溢位。閱讀 [`scripts/Makefile.ubsan`](https://github.com/torvalds/linux/blob/master/scripts/Makefile.ubsan)，說明核心啟用 `CONFIG_UBSAN_SHIFT` 時的效能開銷估算方法 (提示：每次位移操作插入一組條件分支與 `__ubsan_handle_shift_out_of_bounds` 呼叫)。從 CPU branch predictor 的角度，分析此檢查在 hot path (如 scheduler 的 `update_curr()` 每次 context switch 皆呼叫) 的 pipeline stall 成本，並說明核心為何在生產環境通常僅啟用 `UBSAN_BOUNDS` 而非完整 `UBSAN` * 核心頂層 Makefile 同時設定 `-fno-strict-overflow` 與 `-fno-strict-aliasing`，前者處理算術溢位假設，後者處理型別別名假設。以此為出發點： * (a) 設計一段程式碼示範 strict aliasing 如何影響編譯結果：定義 `int x = 1;` 後以 `*(float *)&x = 2.0f;` 寫入，再讀取 `x`。以 GCC `-O2 -fstrict-aliasing` 編譯，說明編譯器為何有權假定 `float *` 的寫入不影響 `int x`，進而將後續的 `x` 讀取最佳化為常數 1。對照 C99 6.5 §7 列舉的合法存取型別 (物件的有效型別、相容型別、對應的有號/無號型別、`char` 型別)，說明 `float *` 存取 `int` 物件為何不在此清單中。以 `-fno-strict-aliasing` 重新編譯，比較產生的組合語言差異 * (b) Linux 核心的 [`tools/include/linux/compiler.h`](https://github.com/torvalds/linux/blob/master/tools/include/linux/compiler.h) 定義 `__may_alias` 屬性 (`__attribute__((__may_alias__))`)，而 [`include/linux/unaligned.h`](https://github.com/torvalds/linux/blob/master/include/linux/unaligned.h) 引入 [`include/linux/unaligned/packed_struct.h`](https://github.com/torvalds/linux/blob/master/include/linux/unaligned/packed_struct.h) 的 `__packed` 結構體實作 `get_unaligned()`。閱讀此實作路徑，說明 `__packed struct { u32 x; } *` 如何改變對齊要求使編譯器不假定自然對齊，從而在某些架構上產生非對齊安全的載入指令。注意 `__packed` 的主要效果是降低對齊約束，不一定產生 byte-by-byte 載入：在 x86 等支援非對齊存取的架構上，GCC 仍可能產生單一 `mov` 指令。對比 `memcpy` 方案在 GCC `-O2` 下的編譯結果，說明現代 GCC 是否能將小尺寸 `memcpy` 最佳化為單一載入指令 (提示：GCC 的 `__builtin_memcpy` 在已知長度 ≤ 8 時通常內聯展開)； * \(c) MMIO 暫存器的存取必須經由 `readl()`/`writel()` (定義於 [`include/asm-generic/io.h`](https://github.com/torvalds/linux/blob/master/include/asm-generic/io.h))，不能直接以 `*(volatile u32 *)addr` 存取。閱讀 `readl()` 的展開式，說明其中 `volatile` 如何防止編譯器消除或重排載入，以及 `__iomem` 標註 (搭配 Sparse 靜態檢查工具) 如何在編譯期偵測 MMIO 指標與一般指標的混用。從 strict aliasing 的角度分析：若省略 `volatile`，編譯器在 `-fstrict-aliasing` 下是否可能將同一 MMIO 位址的兩次 `readl()` 合併為一次載入？ --- ## Problem C: 無號高位乘積 > 延伸 CS:APP 2.75 - [ ] Part 1: unsigned_high_prod :::info 對應到 CS:APP 的 2.75 ::: - [ ] Part 2: Linux 核心的寬乘法實作 核心的排程器 CFS (Completely Fair Scheduler) 以奈秒級虛擬執行時間 `vruntime` 決定行程的執行順序。每次 timer tick 或行程讓出 CPU 時，[`kernel/sched/fair.c`](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c) 的 `update_curr()` 呼叫 `calc_delta_fair()` 計算 $\delta_{\text{vruntime}} = \delta_{\text{exec}} \times \frac{1024}{\text{weight}}$，其中 `weight` 由 nice 值對映 (nice 0 = 1024，nice -20 = 88761)。這個乘法涉及 64 位元運算元：`delta_exec` 為奈秒計，在 4 GHz 處理器上每秒累積 $10^9$，乘以權重比後輕易超過 $2^{32}$。 計時子系統 ([`kernel/time/`](https://github.com/torvalds/linux/tree/master/kernel/time)) 將 TSC 週期轉換為奈秒時同樣需要全寬乘積。在不支援 `__int128` 的 32 位元平台 (如 ARMv7 嵌入式 Linux) 上，[`include/linux/math64.h`](https://github.com/torvalds/linux/blob/master/include/linux/math64.h) 將乘積拆為四組 $32 \times 32 \to 64$ 部分積再累加，這是 base-$2^{32}$ 多項式展開 (長乘法)，屬於不同位元寬度間的分段累加技術。Part 1 Equation 2.18 處理的是另一個面向：同一位元寬度下有號與無號解釋的乘積差異修正。二者皆關注如何取得全寬乘積的高位，但採用的分解策略不同： ```c /* include/linux/math64.h (32-bit fallback, 節錄) */ static inline u64 mul_u64_u64_shr(u64 a, u64 b, unsigned int shift) { #if defined(CONFIG_ARCH_SUPPORTS_INT128) return (unsigned __int128)a * b >> shift; #else /* split a, b into high/low 32-bit halves and accumulate four partial products with carry propagation */ ... #endif } ``` Part 1 要求利用 `signed_high_prod` 實作 `unsigned_high_prod`。二者的差異可從環 $\mathbb{Z}/2^w\mathbb{Z}$ 的觀點理解：$w$ 位元無號整數與二補數有號整數在加法與低 $w$ 位元乘法上完全一致：它們是同個環元素的不同「代表元」選擇 (無號取 $[0, 2^w)$，有號取 $[-2^{w-1}, 2^{w-1})$)。然而，全寬 $2w$ 位元乘積不在 $\mathbb{Z}/2^w\mathbb{Z}$ 中運算，而是在 $\mathbb{Z}$ 上計算後拆為高、低各 $w$ 位元。低 $w$ 位元 ($= xy \bmod 2^w$) 與代表元的選擇無關，但高 $w$ 位元 ($= \lfloor xy / 2^w \rfloor$) 取決於乘數在 $\mathbb{Z}$ 中的實際值。令 $x_u = x_s + x_{w-1} \cdot 2^w$ (無號 = 有號 + 符號修正)，展開 $x_u \cdot y_u$ 並取高位，即得 Equation 2.18 的修正項 $x_{w-1} \cdot y + y_{w-1} \cdot x$。這個修正項的本質是：從 $\mathbb{Z}/2^w\mathbb{Z}$ 的環同態提升 (lift) 至 $\mathbb{Z}$ 時，有號與無號代表元在 $\mathbb{Z}$ 上相差 $2^w$ 的倍數，乘法後此差異反映在高位。 核心的 CFS 排程器在 `__calc_delta` 中以 `mul_u64_u32_shr` 計算 $\delta \times \text{inv\_weight} \gg 32$，其中 `inv_weight` 是 $\lfloor 2^{32} / \text{weight} \rfloor$ 的預計算值：這等效於在 $\mathbb{Z}/2^{32}\mathbb{Z}$ 中以乘以近似倒數取代除法，`>> 32` 取出高位即為商。此技巧的正確性同樣建立在環結構上：$a \cdot \lfloor 2^{32}/b \rfloor$ 的高 32 位元逼近 $\lfloor a/b \rfloor$，誤差至多 1。核心的 [`lib/math/gcd.c`](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c) 則實作 Euclidean 演算法求最大公因數：這是 $\mathbb{Z}$ 作為 Euclidean domain 的直接應用，CFS 用它簡化權重比。 從精確度的角度，`inv_weight = ⌊2^{32} / weight⌋` 的截斷絕對誤差不超過 1，因此倒數近似的相對誤差受限於 $\text{weight} / 2^{32}$。對 nice 0 (weight = 1024)，相對誤差 $< 1024 / 2^{32} \approx 2.4 \times 10^{-7}$；對 nice -20 (weight = 88761)，相對誤差 $< 88761 / 2^{32} \approx 2.1 \times 10^{-5}$。即使在最壞情況下，此誤差仍遠小於 timer tick 粒度 (1~4 ms)。CFS 選擇 32 位元倒數而非更窄的定點格式，正是因為排程公平性對 `vruntime` 的累積精度極為敏感：若二個 nice 0 的行程因倒數截斷導致 `vruntime` 每秒偏移 1 ns，經過數小時運行後偏移可達微秒級，足以造成可觀測的 CPU 分配不均。 在 32 位元平台上，`mul_u64_u32_shr` 無法使用 `__int128`，必須將 64 位元乘數 $a$ 拆為高低各 32 位元，以兩組部分積 $a_{\text{lo}} \cdot b$ 與 $a_{\text{hi}} \cdot b$ (各為 $32 \times 32 \to 64$) 累加取得全寬結果，這與 Part 1 的高位乘積修正處理的是同一個核心問題：如何在有限硬體寬度下取得全寬乘積的高位。差異在於 Part 1 修正有號/無號的解釋差異，而 `mul_u64_u32_shr` 修正位元寬度的分段累加。此 fallback 路徑的 carry propagation 邏輯若有誤，CFS 的 `vruntime` 計算在 32 位元 ARM 嵌入式裝置上會產生與 64 位元平台不同的排程行為，同一組 nice 值的行程在不同架構上獲得不等量的 CPU 時間，違反 CFS「完全公平」的設計目標。 學員須依據 Part 1 提示的 Equation 2.18 自行推導有號與無號乘積的修正關係。程式碼中 `sx` 與 `sy` 分別以算術右移擴充符號位元 (此處依賴 Part 1 Coding Rules 的假設：有號資料的右移以算術方式執行)。程式碼已提供 `sx&y` (即 $x_{w-1} \cdot y'$) 為第一個修正項，填空 __ C01 __ 為第二個修正項中與 `sy` 做 AND 的運算元： ```c /* Assume 32-bit unsigned */ unsigned unsigned_high_prod(unsigned x, unsigned y) { int sx = (int) x >> 31; int sy = (int) y >> 31; int signed_hi = signed_high_prod((int)x, (int)y); return (unsigned)signed_hi+(sx&y)+(sy&__C01__); } ``` 注意 `(int) x` 的轉型在 C99 下屬於 value conversion (C99 6.3.1.3 §3)：當 `x` 超出 `int` 可表示範圍時，結果為 implementation-defined。GCC 定義此轉型為模 $2^w$ 截斷再重新解釋為有號值 (即二補數重新詮釋)，核心程式碼依賴此 GCC 保證。此處的 `(int) x` 與 `(unsigned) signed_hi` 來回轉型不涉及指標別名，故不觸發 strict aliasing 問題。相較之下，`*(int *)&x` (其中 `x` 為 `unsigned`) 在 C99 6.5 §7 下反而是合法的：該條款明確允許透過「與有效型別對應的有號或無號型別」存取物件，`int` 恰為 `unsigned` 的對應有號型別。但若型別配對不在此清單中 (如 `*(float *)&x`)，即構成 strict aliasing violation。核心的 [`include/linux/math64.h`](https://github.com/torvalds/linux/blob/master/include/linux/math64.h) 中部分 32 位元 fallback 以 union 拆分 64 位元值的高低半字，涉及 `u32` 與 `u64` 之間的型別轉換，需要 `-fno-strict-aliasing` 或 union type punning 保障正確性。 驗證：$(2^{32} - 1)^2 = 2^{64} - 2^{33} + 1$，故 `unsigned_high_prod(0xFFFFFFFF, 0xFFFFFFFF)` 的結果為 `0x` __ C02 __。 延伸閱讀：整數乘法溢位屬 [CWE-190](https://cwe.mitre.org/data/definitions/190.html) (Integer Overflow or Wraparound)。[CVE-2021-22555](https://nvd.nist.gov/vuln/detail/CVE-2021-22555) 中 Netfilter `x_tables` 的 `xt_compat_target_from_user()` 在計算 compat 結構體大小時，使用者空間傳入的 `target_size` 與固定偏移相加後發生整數溢位，導致 `kmalloc` 配置過小的緩衝區，後續的 `memcpy` 造成 heap out-of-bounds write，攻擊者可藉此從非特權容器提權至 root。核心後續以 [`include/linux/overflow.h`](https://github.com/torvalds/linux/blob/master/include/linux/overflow.h) 提供 `size_mul()`、`size_add()`、`struct_size()` 等防禦巨集，在編譯期或執行期攔截溢位。 ### 延伸問題 * Part 1 的 Equation 2.18 修正項 `(sx&y)+(sy&x)` 將有號高位乘積轉為無號高位乘積，核心的 `mul_u64_u64_shr` 在 32 位元平台以四組部分積累加實作同一目的。以此為出發點： * (a) 閱讀 [`include/linux/math64.h`](https://github.com/torvalds/linux/blob/master/include/linux/math64.h) 中 `mul_u64_u32_shr` 的 32 位元 fallback 實作 (non-`CONFIG_ARCH_SUPPORTS_INT128` 路徑)，追蹤兩組部分積 $a_{\text{lo}} \cdot b$、$a_{\text{hi}} \cdot b$ 的 carry propagation 邏輯。證明此分段累加在數學上等價於 $a \cdot b = (a_{\text{hi}} \cdot 2^{32} + a_{\text{lo}}) \cdot b$，並分析中間累加步驟是否存在 64 位元溢位風險 (提示：$a_{\text{hi}} \cdot b$ 本身為 64 位元結果，加上 $a_{\text{lo}} \cdot b$ 的高 32 位元是否可能溢位？)。CFS 的 `__calc_delta` 以此函式計算 $\delta_{\text{exec}} \times \frac{\text{weight}}{\text{lw.weight}}$，說明此除法如何以乘以倒數的預計算值 (`lw.inv_weight`) 再右移實作，以及 `inv_weight` 的精度 (32 位元) 對 `vruntime` 公平性的量化影響 * (b) [CVE-2021-22555](https://nvd.nist.gov/vuln/detail/CVE-2021-22555) 的 Netfilter `x_tables` 以 `xt_compat_match_offset` 計算記憶體大小時發生整數溢位。閱讀 `include/linux/overflow.h` 的 `size_mul(a, b)` 巨集，說明其如何以 `__builtin_mul_overflow` 偵測溢位並回傳 `SIZE_MAX` 作為哨兵值。從攻擊者的角度，若 `size_mul` 回傳的 `SIZE_MAX` 被直接傳入 `kmalloc`，核心的 slab allocator 如何處理此極端值？閱讀 [`mm/slab_common.c`](https://github.com/torvalds/linux/blob/master/mm/slab_common.c) 的 `__kmalloc` 入口，說明 `KMALLOC_MAX_SIZE` 檢查是否足以防禦此攻擊路徑 * \(c) 從數論的角度，Part 1 的修正公式可表示為 $u_{\text{hi}} = s_{\text{hi}} + x_{w-1} \cdot y + y_{w-1} \cdot x$，其中 $x_{w-1}$、$y_{w-1}$ 為符號位元。推導此公式 (提示：將無號值改寫為「有號代表元 + 符號位元 $\times 2^w$」再展開乘積，只保留會落到高 $w$ 位元的項。注意算術右移產生的 `sx` 值如何充當條件遮罩) --- ## Problem D: 半精度浮點數轉換 > 延伸 CS:APP 2.87 - [ ] Part 1: Half-Precision 表格 :::info 對應到 CS:APP 的 2.87 ::: - [ ] Part 2: 核心浮點模擬與格式轉換 Linux 核心在一般執行路徑禁止使用浮點運算。原因在於：行程的浮點暫存器狀態 (x86 的 XMM/YMM、ARM 的 VFP/NEON) 在進入核心時不會自動儲存，若核心程式碼使用浮點指令而未以 `kernel_fpu_begin()`/`kernel_fpu_end()` 包裹 (x86) 或等效機制保護，會無聲地破壞使用者空間的浮點狀態。這項禁令迫使所有核心內的數值計算以整數或定點數實作：CFS 排程器以 `u64` 追蹤 `vruntime` (奈秒精度)、以 32 位元倒數近似權重除法 (見 Problem C Part 2)；計時子系統以 `mult`/`shift` 定點參數將 TSC 週期轉換為奈秒。程式設計者必須在選擇 `shift` 值時自行權衡精度與溢位風險，這正是 Part 1 填表時對 IEEE 754 exponent bias 和 fraction 寬度的手動推算在核心實務中的對應。 然而，某些嵌入式 MIPS 處理器 (如路由器、IoT 裝置的 SoC) 根本省略硬體 FPU，使用者空間程式執行浮點指令時 CPU 觸發「coprocessor unusable」例外，由核心的軟體模擬器接手，這是核心中少數必須處理浮點語意的情境。 Linux 核心的 MIPS FPU 軟體模擬器 ([`arch/mips/math-emu/`](https://github.com/torvalds/linux/tree/master/arch/mips/math-emu)) 以 C 結構體對映 IEEE 754 的 sign/exponent/fraction 欄位，在純整數運算下完成浮點計算。當使用者空間程式執行浮點指令時，CPU 觸發 trap，核心的例外處理路徑 ([`arch/mips/kernel/traps.c`](https://github.com/torvalds/linux/blob/master/arch/mips/kernel/traps.c) 的 `do_cpu()`) 解碼觸發指令並轉交模擬器，而模擬器必須產出與硬體 FPU 位元完全一致的結果，包含 NaN payload 傳播與 denormalized 數的漸進下溢 (gradual underflow)。其 double → single 轉換 ([`sp_fdp.c`](https://github.com/torvalds/linux/blob/master/arch/mips/math-emu/sp_fdp.c)) 經由 `ieee754sp_format` 施以 sticky-bit 截斷與 round-to-even，轉換流程類似本題 single → half 的邏輯。 近年 GPU 運算與機器學習推論大量使用 half-precision (fp16)。DRM/KMS 子系統定義了 `DRM_FORMAT_XRGB16161616F` 等 fp16 像素格式 ([`include/uapi/drm/drm_fourcc.h`](https://github.com/torvalds/linux/blob/master/include/uapi/drm/drm_fourcc.h))，GPU 驅動程式 (如 AMD 的 [`drivers/gpu/drm/amd/display/amdgpu_dm/amdgpu_dm_color.c`](https://github.com/torvalds/linux/blob/master/drivers/gpu/drm/amd/display/amdgpu_dm/amdgpu_dm_color.c)) 在 HDR 色彩管線中以整數運算操作 fp16 位元模式，將使用者空間傳入的 fp16 色彩值轉換為硬體暫存器格式。這些情境下，核心需要在禁止浮點指令的環境下以純整數位元操作處理 16 位元浮點格式： ```c /* arch/mips/math-emu/ieee754.h (節錄，經簡化； mainline 以 __BITFIELD_FIELD() 包裹並處理位元組序) */ union ieee754sp { struct { unsigned sign:1; unsigned bexp:8; unsigned mant:23; }; u32 bits; }; ``` 此 `union` 以 bit-field 結構體與 `u32` 共用同一 32 位元，是 type punning 的典型手法。C99 6.5 §7 列舉了合法的 effective type 存取規則 (即 strict aliasing rule)：透過與物件有效型別不相容的指標存取屬於未定義行為。對 union 而言，C99 附註 82 (非規範性) 指出透過 union 讀取非最後寫入的成員時，位元組以新型別重新詮釋 (可能產生 trap representation)。C 標準本身未明確定義此行為，但 GCC 明確保證 union type punning 產生預期結果。然而，若改以指標強制轉型 `*(u32 *)&sp_val` 存取同一記憶體，在啟用 strict aliasing 的編譯器下即觸發 UB：編譯器可能假定 `u32 *` 與 `struct { unsigned sign:1; ... } *` 不指向同一物件，將讀取結果快取於暫存器而忽略後續寫入。核心以 `-fno-strict-aliasing` 全域停用此假設 (見 Problem B Part 2 的說明)。Part 2 的 `float32_to_float16` 以 `unsigned` 表示位元模式，完全在整數域操作，不涉及浮點型別的指標別名問題；但若學員嘗試以 `*(float *)&f` 解碼位元模式進行驗證，需注意此寫法在標準 C 下違反 strict aliasing，應改用 `memcpy` 或 `union`。 Part 1 以手動填表熟悉 half-precision 的欄位配置。以下將此編碼規則轉為 C 程式，實作 32 位元 single precision ($\text{bias}_s = 127$, fraction 23 位元) → Part 1 定義的 16 位元 half precision 格式轉換。 偏移量轉換可一步完成：$\text{hexp} = \text{exp} - (\text{bias}_s - \text{bias}_h)$，填空 __ D01 __ 為此淨偏移量，須依 Part 1 的 half-precision 參數 ($k$ 與 bias) 計算。當 $\text{hexp} \leq 0$ 時結果落入 half-precision denormalized 區間，mantissa 須右移以對齊 denormalized 的固定指數；填空 __ D02 __ 為此基底常數 ($\text{bias}_h - 1$)，同樣須依 Part 1 的 bias 值導出。Normalized 路徑截斷 fraction 低位元以符合 Part 1 定義的 half-precision 寬度；填空 __ D03 __ 為截斷位元的 round-to-even 中點位移量，須依 Part 1 的 $n$ 值推算： ```c unsigned float32_to_float16(unsigned f) { unsigned sign = (f >> 31) & 1; unsigned exp = (f >> 23) & 0xFF; unsigned frac = f & 0x7FFFFF; unsigned hsign = sign << 15; /* 特殊值 */ if (exp == 0xFF) { if (frac == 0) return hsign | 0x7C00; /* infinity */ return hsign | 0x7E00; /* NaN */ } if (exp == 0) return hsign; /* single denorm 極小，映射為 0 */ int hexp = (int)exp - __D01__; /* net bias: single → half */ if (hexp >= 31) return hsign | 0x7C00; /* overflow → infinity */ if (hexp <= 0) { /* denormalized 路徑 */ unsigned mant = frac | 0x800000; int shift = __D02__ - hexp; if (shift > 24) return hsign; unsigned val = mant >> shift; unsigned lost = mant & ((1u << shift) - 1); unsigned half = 1u << (shift - 1); if (lost > half || (lost == half && (val & 1))) val++; return hsign | val; } /* normalized 截斷與捨入 */ unsigned hfrac = frac >> 13; unsigned lost = frac & 0x1FFF; unsigned half = 1u<<__D03__; if (lost > half || (lost == half && (hfrac & 1))) { hfrac++; if (hfrac == 0x400) { hfrac = 0; hexp++; if (hexp >= 31) return hsign | 0x7C00; } } return hsign | ((unsigned)hexp << 10) | hfrac; } ``` 自我檢查 (非填空)：`float32_to_float16(0x387FE000)` (`exp = 112`, `frac = 0x7FE000`) 落入 denormalized 路徑 (`hexp = 0`)，`mant = 0xFFE000`，`shift = 14`，`val = 0x3FF`。丟失位元 `lost = 0x2000` 恰等於中點 `half = 0x2000` 且 `val` 末位為 1，觸發 round-to-even 進位，`val = 0x400`。結果 `0x0400` 恰好越過 denormalized/normalized 邊界，成為 half-precision 最小 normalized 數 $1.0 \times 2^{-14}$。注意 `0x0400` 自然編碼為 `exp = 1, frac = 0`，無需額外的進位分支。 自我檢查 (特殊值)：`float32_to_float16(0x7F800000)` (`exp = 0xFF`, `frac = 0`) 命中 infinity 路徑，回傳 `0x7C00`。`float32_to_float16(0x7FC00000)` (`exp = 0xFF`, `frac != 0`) 命中 NaN 路徑，回傳 `0x7E00`。 延伸閱讀：數值截斷屬 [CWE-197](https://cwe.mitre.org/data/definitions/197.html) (Numeric Truncation Error)。[CVE-2021-33200](https://nvd.nist.gov/vuln/detail/CVE-2021-33200) 中 BPF verifier 的 `coerce_reg_to_size()` 在 ALU32 模式下將 64 位元暫存器值域截斷為 32 位元時，未同步更新有號值域 (`smin_value`/`smax_value`)，使 verifier 對後續的陣列索引運算做出過於寬鬆的安全判斷，攻擊者藉此構造越界存取的 BPF 程式。核心雖禁止在一般路徑使用浮點運算，但 MIPS FPU 軟體模擬器 ([`arch/mips/math-emu/`](https://github.com/torvalds/linux/tree/master/arch/mips/math-emu)) 與 BPF verifier 的數值截斷邏輯仍需嚴格處理精度損失。 ### 延伸問題 * MIPS FPU 軟體模擬器的 `sp_fdp.c` 執行 double → single 轉換時，以 sticky-bit 截斷搭配 round-to-even 處理精度損失，流程與 Part 2 的 `float32_to_float16` 在 denormalized 路徑的捨入邏輯直接對應。以此為出發點： * (a) 閱讀 `arch/mips/math-emu/sp_fdp.c` 的 `ieee754sp_fdp()` 函式，追蹤 double fraction (52 位元) 截斷至 single fraction (23 位元) 時的 sticky-bit 計算方式：被截除的低 29 位元中，最高位元為 guard bit、次高位元為 round bit、其餘以 OR 合併為 sticky bit。以 $G$、$R$、$S$ 表示這三個位元，自行推導 IEEE 754 round-to-even 的進位條件 (提示：先分類 discarded bits 為「小於、等於、大於」半 ulp 三種情況，再考慮「等於」時截斷後最低位元 $L$ 如何決定進位方向)，並驗證 Part 2 程式碼的 `lost > half || (lost == half && (val & 1))` 與此條件等價。說明 round-to-even 相較於 round-towards-zero (截斷) 在統計上消除系統性偏差的數學依據 (提示：比較兩種捨入方式的期望捨入誤差) * (b) BPF verifier 的 [CVE-2021-33200](https://nvd.nist.gov/vuln/detail/CVE-2021-33200) 在 64→32 位元截斷時遺失值域追蹤精度。閱讀 [`kernel/bpf/verifier.c`](https://github.com/torvalds/linux/blob/master/kernel/bpf/verifier.c) 中 `coerce_reg_to_size()` 的修補前後差異，說明原始程式碼如何在截斷後未更新 `reg->smin_value`/`reg->smax_value`，使攻擊者能構造一個 BPF 程式：verifier 認為暫存器值在安全範圍內，但實際執行時截斷後的值超出陣列邊界。從 abstract interpretation 的角度，說明值域追蹤 (interval analysis) 在位元寬度轉換時必須滿足的 soundness 條件 * \(c) 設計 C 程式以窮舉驗證 `float32_to_float16` 的正確性：對所有 $2^{32}$ 個 single-precision 位元模式，以純整數位元操作建構參考轉換器 (從 32 位元位元模式直接拆解 sign/exp/frac 欄位，以整數算術執行 guard/round/sticky bit 判斷與 round-to-even)，與 `float32_to_float16` 的輸出逐位元比較。注意：不應以主機的 `float`/`double` 算術作為 oracle，因 NaN payload 的傳播行為與 signaling NaN 的處理方式依主機實作而異，純整數參考器可避免此類平台相依問題。分析此驗證的計算量 ($2^{32}$ 次迭代) 在現代 x86-64 上的預期執行時間 (提示：每次迭代約 10 ns，總計約 43 秒)，並說明可利用 IEEE 754 的單調性 (同號正數中，若 $|a| \leq |b|$ 則 $\text{encode}(a) \leq \text{encode}(b)$) 將驗證範圍縮減至 denormalized 邊界附近與捨入進位臨界點 (如 `hexp` 從 0 跨至 1、`hfrac` 從 0x3FF 進位至 0x400 的 single-precision 輸入區間) * Part 2 的 `union ieee754sp` 以 `u32 bits` 與 bit-field 結構體共用同一 32 位元，屬 union type punning。C99 附註 82 (非規範性) 指出位元組以新型別重新詮釋，GCC 明確保證此行為產生預期結果。以此為出發點： * (a) 設計三種從 `float` 取出位元模式的方法：(i) `*(unsigned *)&f` (pointer cast)、(ii) `union { float f; unsigned u; } cvt; cvt.f = val; return cvt.u;` (union)、(iii) `unsigned u; memcpy(&u, &f, 4); return u;` (`memcpy`)。以 GCC `-O2 -fstrict-aliasing` 分別編譯，比較產生的組合語言。說明方法 (i) 在標準 C 下違反 C99 6.5 §7 (effective type rule) 而構成 UB，方法 (ii) 依賴 GCC 擴充，方法 (iii) 在任何符合標準的編譯器下皆合法。現代 GCC/Clang 在 `-O2` 下能將 4 位元組 `memcpy` 最佳化為單一 `movd` 指令，無額外開銷。閱讀 [`arch/mips/math-emu/sp_flong.c`](https://github.com/torvalds/linux/blob/master/arch/mips/math-emu/sp_flong.c) 與 [`sp_tlong.c`](https://github.com/torvalds/linux/blob/master/arch/mips/math-emu/sp_tlong.c) 中 `ieee754sp_flong()` / `ieee754sp_tlong()` 的實作，說明核心採用哪種方式，以及 `-fno-strict-aliasing` 如何使三種方法在核心語境下行為一致 * (b) GCC 的 `-ftree-dominator-opts` 在啟用 strict aliasing 時，可能對透過不同型別指標的連續存取進行 load forwarding 最佳化。設計一個 MMIO 驅動程式片段，其中 `writel(val, reg)` 後接 `status = readl(reg)` 讀回同一暫存器以確認寫入完成。說明若編譯器假定 `u32 *` (writel 內部) 與 `volatile u32 *` (readl 的回傳語意) 不重疊，是否可能省略 `readl` 的實際記憶體載入。閱讀 [`include/asm-generic/io.h`](https://github.com/torvalds/linux/blob/master/include/asm-generic/io.h) 的 `readl()` 展開式，說明 `__raw_readl()` 中的 `volatile` 與記憶體屏障 (`__io_br()` / `__io_ar()`) 如何共同防止此最佳化 --- ## Problem E: 位元級浮點除法 > 延伸 CS:APP 2.95 - [ ] Part 1: float_half :::info 對應到 CS:APP 的 2.95 ::: - [ ] Part 2: 核心浮點模擬與 float_quarter Problem D 提及的 MIPS FPU 軟體模擬器 ([`arch/mips/math-emu/`](https://github.com/torvalds/linux/tree/master/arch/mips/math-emu)) 在 double → single 轉換時，需處理指數縮減後落入 denormalized 區間的捨入問題，直接對應於這與 Part 1 `float_half` 的 denormalized 路徑邏輯。核心的 `ieee754sp_format` 函式在重新包裝浮點欄位時，以 sticky-bit 截斷搭配 round-to-even 處理精度損失，流程等同本題將 Part 1 `float_half` 延伸至 `float_quarter` 時所面臨的 normalized/denormalized 邊界與捨入挑戰。 從代數的角度，IEEE 754 的可表示數構成 $\mathbb{R}$ 的一個離散子集 (格子，lattice)。Normalized 區間的可表示數以等比數列分布 (相鄰數的比值固定)，denormalized 區間則以等差數列分布 (相鄰數的差固定為 $2^{1-\text{bias}-n}$，即最小正 denormalized 數)。`float_half` 的操作「將 $f$ 對映至最接近 $f/2$ 的可表示數」，等效於在此格子中尋找最近鄰 (nearest-point problem)。Round-to-even 的 tie-breaking 規則保證此對映在統計上無偏：可表示數構成 $\mathbb{Z}$ 的一個子群 (以 ulp 為單位)，tie 恰好落在二個格點的中點，round-to-even 使一半 tie 向上、一半向下，累積偏差為零。denormalized 區間的難點在於格子的間距從等比切換至等差，使得 `exp > 1` 路徑的簡單「指數減 1」不再適用，必須顯式右移 mantissa 並重新執行最近鄰搜尋。 核心中另一類「除以 $2^n$」的情境以定點數實作。EWMA ([`include/linux/average.h`](https://github.com/torvalds/linux/blob/master/include/linux/average.h)) 以 `>> weight_rcp` 實作除法。cfg80211 無線子系統以 EWMA 平滑接收訊號強度 (RSSI)，平滑後的數值直接影響漫遊 (roaming) 決策：若截斷右移引入系統性偏差，無線用戶端可能在訊號已明顯衰減後仍黏著於原存取點，延遲切換至更佳的基地台。TCP 堆疊的 SRTT (smoothed round-trip time) 以 `srtt_us >> 3` 計算 (等效於 $\alpha = 1/8$ 的 EWMA)，壅塞控制演算法依據 SRTT 調整傳送窗口，捨入偏差會導致 RTT 估算偏低，進而使傳送端在壅塞時反應遲緩。CFS 排程器的 `__calc_delta` 以 `mul_u64_u32_shr` 搭配 `WMULT_SHIFT` (= 32) 截斷定點乘積：`vruntime` 差異在奈秒級，截斷偏差 < 1 ns 遠小於排程延遲，故可容忍。定點數的可表示值構成 $\mathbb{Z}$ 的一個子群 (以 $2^{-\text{precision}}$ 為生成元)，間距均勻，右移就是在此均勻格子上的整數除法，不存在格子間距改變的問題。這正是 Part 1 `float_half` 與本題 `float_quarter` 的難點所在：IEEE 754 的格子間距在 normalized 與 denormalized 邊界處突變，而核心的定點數除法無此困擾。 Part 1 要求以 bit-level 操作實作 `float_half` ($0.5 \times f$)，`float_half` 在 `exp > 1` 時直接將指數減 1，僅 $\text{exp} \leq 1$ 需處理 denormalized 區間。以下延伸至 `float_quarter` ($0.25 \times f$)，除以 4 等效於指數減 2，使得 $\text{exp} \in \{0, 1, 2\}$ 三種情況皆落入 denormalized 路徑。沿用 Part 1 的 `float_bits` 型別定義。 請延續 Part 1 實作 `float_half` 時處理 denormalized 區間的推導邏輯。在 $\text{exp} \in \{0, 1, 2\}$ 的三種情況中，僅一種的位移量與其他不同；填空 __ E01 __ 為該特殊 `exp` 值。若 round-to-even 進位使 `mant` 達到 $2^{23}$，結果恰為最小 normalized 數；填空 __ E02 __ 為最小 normalized 數的指數欄位值： ```c float_bits float_quarter(float_bits f) { unsigned sign = f & 0x80000000u; unsigned exp = (f >> 23) & 0xFF; unsigned frac = f & 0x7FFFFF; if (exp == 0xFF) return f; /* NaN / infinity 不變 */ if (exp > 2) return sign | ((exp - 2) << 23) | frac; unsigned mant = frac; if (exp != 0) mant |= 1u << 23; /* 還原 hidden bit */ int shift = (exp==__E01__) ? 1 : 2; unsigned lost = mant & ((1u << shift) - 1); unsigned half = 1u << (shift - 1); mant >>= shift; if (lost > half || (lost == half && (mant & 1))) mant++; if (mant == (1u << 23)) return sign|(__E02__<<23); /* 進位回到最小 normalized */ return sign | mant; } ``` 驗證：`float_quarter(0x00800000)` 的輸入為最小正 normalized 數 ($1.0 \times 2^{-126}$，`exp = 1`，`frac = 0`)。除以 4 後值為 $2^{-128}$，以 denormalized 編碼表示。結果的位元表示為 `0x` __ E03 __。 自我檢查 (round-to-even 進位)：`float_quarter(0x017FFFFF)` (`exp = 2`, `frac = 0x7FFFFF`) 進入 denormalized 路徑。`mant = 0xFFFFFF`，`shift = 1`，右移後 `mant = 0x7FFFFF`。丟失位元 `lost = 1` 恰等於 `half = 1` 且 `mant` 末位為 1，觸發 round-to-even 進位，`mant = 0x800000 = 2^{23}`，命中 E02 分支，回傳 `0x00800000` (最小正 normalized 數 $1.0 \times 2^{-126}$)。 自我檢查 (負數符號保留)：`float_quarter(0x80800000)` (`sign = 0x80000000`, `exp = 1`, `frac = 0`) 為最小負 normalized 數 $-1.0 \times 2^{-126}$。`mant = 0x800000`，`shift = 2`，右移後 `mant = 0x200000`，無進位。回傳 `0x80000000 | 0x200000 = 0x80200000`，即 $-2^{-128}$ 的 denormalized 編碼，符號位元正確保留。 延伸閱讀：右移捨入偏差屬 [CWE-682](https://cwe.mitre.org/data/definitions/682.html) (Incorrect Calculation)。[`include/linux/average.h`](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 的 `DECLARE_EWMA` 於 v4.9 由 Johannes Berg 重新設計，改以無號定點數搭配明確精度參數 (`precision` 控制小數位元數、`weight_rcp` 控制衰減速率)，消除舊版有號右移的系統性捨入偏差。舊版 `ewma_add()` 對有號中間值右移時，負值向負無限大方向截斷，正值向零截斷，長期累積造成均值偏低。新版改用無號運算，截斷方向一致。TCP 堆疊的 SRTT (smoothed round-trip time) 計算 ([`net/ipv4/tcp_input.c`](https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_input.c)) 亦多次修正類似的定點捨入問題。 ### 延伸問題 * `float_quarter` 的 denormalized 路徑需處理 `exp ∈ {0, 1, 2}` 三種情況，其中 `exp == 2` 的位移量 (`shift = 1`) 與其餘二者 (`shift = 2`) 不同。此不對稱性源自 hidden bit 的有無。以此為出發點： * (a) 推廣至 `float_eighth` ($0.125 \times f$，除以 8，指數減 3)，denormalized 路徑涵蓋 `exp ∈ {0, 1, 2, 3}`。列出每個 `exp` 值對應的 `shift` 量，並嘗試歸納一般化公式 (提示：分別考慮 `exp == 0` (無 hidden bit) 與 `exp >= 1` (有 hidden bit) 兩類，觀察 hidden bit 的存在如何影響有效位元寬度與所需位移量的關係。特別注意 `exp == 0` 與 `exp == 1` 的 `shift` 值為何相同：思考二者的有效位元寬度與指數偏移如何互相補償)。推導 round-to-even 進位使 `mant` 達到 $2^{23}$ 的臨界輸入條件 (以 `exp` 和 `frac` 的最低位元表示)，說明此進位在統計上的發生機率 (假設 `frac` 均勻分布) * (b) 核心的 EWMA (`include/linux/average.h`) 以 `>> weight_rcp` 實作定點數除以 $2^n$，無需處理 denormalized 邊界。閱讀 `DECLARE_EWMA(name, _precision, _weight_rcp)` 的展開式，追蹤 `ewma_##name##_read()` 如何以 `>> precision` 還原實際值。以 TCP SRTT (`net/ipv4/tcp_input.c` 的 `tcp_rtt_estimator`) 為例：SRTT 以 `srtt_us >> 3` 取得平滑值 (等效於 $\alpha = 1/8$ 的 EWMA)。設計一段分析程式，模擬 RTT 序列 $[100, 100, \ldots, 200, 200, \ldots]$ (先穩定於 100 ms 再跳變至 200 ms) 經 EWMA 平滑後的收斂曲線，計算達到新穩態 95% 所需的樣本數 $n_{95} = \lceil \log(0.05) / \log(1 - \alpha) \rceil$，並與 IEEE 754 float_half 的精度損失做類比：EWMA 的截斷右移等效於 Part 1 denormalized 路徑的精度衰減，二者皆在低值區域累積系統性捨入偏差 * \(c) `float_quarter` 以 `(lost == half && (mant & 1))` 實作 round-to-even 的 tie-breaking。從機率論的角度，假設浮點數均勻分布於 $[1, 2)$，計算除以 4 後恰好命中 tie (即 `lost == half`) 的機率。對 `exp == 1` 的情況 (`shift = 2`)，分析 `mant` 的低位元模式中哪些會觸發 tie，計算 tie 的發生機率，並說明 round-to-even 如何確保 tie 事件中進位與截斷各佔一半，使累積捨入誤差的期望值精確為零。對比 Linux 核心 [`lib/math/div64.c`](https://github.com/torvalds/linux/blob/master/lib/math/div64.c) 的 `div_u64_rem` 在整數除法中不提供 round-to-even 語意，以及 [`kernel/sched/fair.c`](https://github.com/torvalds/linux/blob/master/kernel/sched/fair.c) 的 `__calc_delta` 以 `mul_u64_u32_shr` 搭配 `WMULT_SHIFT` (= 32) 截斷定點乘積：說明在排程器的精度需求下，截斷偏差為何可容忍 (提示：`vruntime` 差異在奈秒級，截斷偏差 < 1 ns 遠小於排程延遲)。注意 `SCHED_FIXEDPOINT_SHIFT` (= 10) 與 `WMULT_SHIFT` (= 32) 是排程器中二個不同的定點參數：前者用於負載追蹤 (load tracking) 的權重比縮放，後者用於 `__calc_delta` 的倒數乘法。二者的共通點是以右移取代除法，但精度等級不同。`SCHED_FIXEDPOINT_SHIFT = 10` 恰與 Part 1 half-precision 的 fraction 寬度 ($n = 10$) 相同，提供 $2^{-10} \approx 10^{-3}$ 的相對精度；`WMULT_SHIFT = 32` 則對應 single-precision 的有效位元數量級。閱讀 [`kernel/time/clocksource.c`](https://github.com/torvalds/linux/blob/master/kernel/time/clocksource.c) 的 `clocks_calc_mult_shift()`，說明此函式如何在給定的 `from` (Hz)、`to` (Hz) 與 `maxsec` (最大不溢位秒數) 約束下，選擇最大的 `shift` 值以最大化定點精度。此決策與 IEEE 754 格式設計有粗略的類比：定點的 `shift` 越大，小數精度越高但可表示的最大整數值越小 (溢位越快)；IEEE 754 的 fraction 位元越多，有效數字越精確但 exponent 位元越少、動態範圍越窄。二者都是在固定位元預算下的精度/範圍權衡，但機制不同：定點以線性刻度分配精度，IEEE 754 以對數刻度 (exponent) 搭配線性刻度 (fraction) 分配 --- ## 參考題解 :::spoiler * A01: ==`mask<<shift`== * A02: ==`mask`== * A03: ==`undefined behavior`== * A04: ==AA112233== * B01: ==`wrapped`== * B02: ==`undefined behavior`== * C01: ==`x`== * C02: ==FFFFFFFE== * D01: ==112== * D02: ==14== * D03: ==12== * E01: ==2== * E02: ==1== * E03: ==00200000== :::