--- # System prepended metadata title: 2026q1 Homework2 (stdc) --- # 2026q1 Homework2 (stdc) contributed by < illdoCc > {%hackmd NrmQUGbRQWemgwPfhzXj6g %} > 課程助教註記: 4 月 14 日 ## 探討〈[Linux 核心原始程式碼的整數除法](https://hackmd.io/@sysprog/linux-intdiv)〉 - [ ] 針對 `#define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))`，回答以下: * 說明為何 `((n)+(d)-1)/d` 在 `n` 與 `d` 為正整數時可以實作上取整除法。請以歐幾里得除法表示式 `n = dq + r`，其中 `0 ≤ r < d`，以嚴謹的數學推導此巨集的正確性 A: 令 `n = dq + r, 0 ≤ r < d`，可以將 `((n)+(d)-1)/d` 改寫為 `((qd+r)+(d)-1)/d`，在整數除法中，此式可改寫為`q+(r+d-1)/d` 接下來要證明的有兩種情況: 1. `r = 0`，在這種情況下，由於 `q` 可以被 `d` 整除，不希望讓 `DIV_ROUND_UP` 錯誤的增加 1。回到原式， `q+(r+d-1)/d` 可改寫為`q+(d-1)/d`，在整數除法中，`(d-1)/d` 會等於 0，並不會讓該巨集錯誤的增加 1。 2. `0 < r < d`，這種情況下無法整除，因此需要將其向上取整。由於 `0 < r < d`，因此 `d-1 < r+d-1 < 2d-1`。此時無論令 `r+d-1=d` 或是 `r+d-1=2d-2`，整數除法除以 `d` 後都會等於 1，也因此得以向上取整。 * 若 `n` 或 `d` 可能為負數，該巨集可能出現錯誤結果。請設計可在 Linux 核心中安全使用、同時仍盡量避免分支的版本，並說明設計考量 A: 考慮以下四種情況 1. $\cfrac{n+d-1}{d}, \text{where}~n>0, d>0$ 2. $\cfrac{n-d+1}{d}, \text{where}~n<0, d>0$ 3. $\cfrac{n-d-1}{d}, \text{where}~n>0, d<0$ 4. $\cfrac{n+d+1}{d}, \text{where}~n<0, d<0$ 這四種情況，分母的 $d$ 以及分子的 $n$ 都不須因為正負而變號。 在 $n>0$ 的情況，分子都是 $-1$；在 $n<0$ 的情況，分子都是 $+1$，因此可以推導出 `~(n>>31)|1` 這段程式。 在 $n、d$ 同號的情況下，分子皆為 $+d$；在異號的情況下，分子皆為 $-d$，因此可以推導出 `((n>>31)|1)*((d>>31)|1)*d` 這段程式。 結合上述，可以得出以下程式: ```c #define DIV_ROUND_UP(n, d) (((n)+(((n>>31)|1)*((d>>31)|1)*d) + (n>>31)|1) / (d)) ``` 不過上述程式可讀性較差，鑑於 linux kernel 採用的是 GNU C 編譯，因此可以使用 GNU extension 來重新改寫: ```c #define DIV_ROUND_UP(n, d) \ ({ \ __typeof__(n) _n = (n); \ __typeof__(d) _d = (d); \ __typeof__(n) _sn = (_n >> 31) | 1; \ __typeof__(d) _sd = (_d >> 31) | 1; \ (_n + _sn * _sd * _d + _sn) / _d; \ }) ``` - [ ] Linux 核心原始程式碼提供 `do_div` 巨集，可在一次操作中取得 64 位元整數除法的商與餘數。回答以下： * 在某些架構 (例如部分 Arm 平台，缺乏 FPU) 上，編譯器可能將 64 位元除法轉換為呼叫 `__aeabi_uldivmod`。說明為何 Linux 核心會刻意避免依賴這類 libgcc 函式 A: 翻閱 [[PATCH] sched: Explicit division calls on 64-bit integers](https://lists.infradead.org/pipermail/linux-arm-kernel/2012-November/133312.html) 當中提到以下: > Certain gcc tool chains convert the division on a 64-bit dividend into a __aeabi_uldivmod call which does unnecessary 64-bit by 64-bit divides although the divisor is 32-bit.This 64 by 64 bit division is not implemented in the kernel for reasons of efficiency,which results in undefined reference errors during link time.Hence perform the division on 64-bit dividends using do_div() function. 因此可以得知之所以不用這類 libgcc 函式，是因為即使除數是 32-bit，`__aeabi_uldivmod` 依舊會將其轉為 64-bit，導致效能下降。 * 假設你正在實作 Linux 核心中的時間子系統，需要頻繁將奈秒 (ns) 轉換為毫秒 (ms)，討論以下實作方式的優缺點： a) 使用一般 `/` 運算子; b) 使用 `do_div`; c) 將除法轉換為乘法與位移 A: a) 使用一般 `/` 運算子的好處就是實作簡易，不需額外複雜的技巧。而缺點則是在硬體架構下，除法所消耗的資源是龐大的，甚至某些硬體架構沒有除法器，需要利用軟體層來實作除法。 b) 使用 `do_div` 的好處是由於將奈秒轉換為毫秒，只需要除以 $10^{6}$，而 $10^{-6} < 2^{32} - 1$，因此不會被擴展為 64-bit 導致效能下降。缺點也如上，除法所消耗的資源是龐大的。 c) 將除法轉換為乘法與位移的好處是避開耗時的除法操作，硬體在實作乘法及位移是相對快速的。缺點則是寫法複雜，要找到對應的 magic number 並驗證該近似值是否會造成誤差。 - [ ] Linux 核心 `vsprintf` 中的十進位轉換實作會避免直接使用除法，而改用乘法與查表方式來提升效能。回答以下: * 為何 `/proc` 與 `/sys` 的輸出效能會影響整體系統效能？以實際的測試來說明 A: 參考["運用 Perf 分析程式效能並改善"](https://hackmd.io/p6CKCtaZQBe3GJyiLEjbJg?view#%E6%B8%AC%E9%87%8F%E7%9F%A9%E9%99%A3%E7%9B%B8%E4%B9%98%E7%A8%8B%E5%BC%8F%E6%95%88%E8%83%BD)這篇教材，以下先單純測量基礎矩陣運算所運行的時間作為比較基準，觀察參數當中額外加上 `cs`(context switch)、`cache-misses`: `sudo perf stat -e cycles,instructions,cs,cache-misses taskset -c 0 ./matrix-v1` 為了避免 kernel 將任務分散在多核 CPU 運行導致測量結果相差無幾，我指定他運行在 core 0，以下是運行結果： ``` Performance counter stats for 'taskset -c 0 ./matrix-v1': 10,470,974,909 task-clock # 0.998 CPUs utilized 46,525,043,795 cycles # 4.443 GHz 37,793,447,608 instructions # 0.81 insn per cycle 2,293 cs # 218.986 /sec 6,057,678 cache-misses 10.490842610 seconds time elapsed 10.302676000 seconds user 0.164770000 seconds sys ``` 這段程式從開始執行到結束總共花了 10.49 秒，其中有 2293 個 context switch、6057678 個 cache-misses。 接下來在背景運行 `taskset -c 0 bash -c "while true; do cat /proc/stat > /dev/null; done"`，同樣指定在 core 0，再次觀察矩陣乘法所耗費的時間： ``` Performance counter stats for 'taskset -c 0 ./matrix-v1': 10,649,420,800 task-clock # 0.379 CPUs utilized 47,727,715,461 cycles # 4.482 GHz 38,082,314,609 instructions # 0.80 insn per cycle 6,346 cs # 595.901 /sec 36,619,372 cache-misses 28.129436311 seconds time elapsed 10.610067000 seconds user 0.047844000 seconds sys ``` 這次從程式開始執行到結束總共花費了 28.13 秒，同時 context switch 的次數增加為 6346、cache-misses 增至 36619372，多了六倍，效能明顯下降。 接下來運行一個純粹消耗 CPU 且運行在 user space 的程式 `taskset -c 0 bash -c 'while true; do x=$((1+1)); done'`，比對其效能是否一樣造成如此巨大的下降: ``` Performance counter stats for 'taskset -c 0 ./matrix-v1': 10,231,780,369 task-clock # 0.499 CPUs utilized 45,986,675,686 cycles # 4.494 GHz 37,794,985,592 instructions # 0.82 insn per cycle 5,066 cs # 495.124 /sec 6,568,105 cache-misses 20.491855917 seconds time elapsed 10.209988000 seconds user 0.020934000 seconds sys ``` 觀察到 cache-misses 並沒有增加如此多。 * 假設你需要在 Linux 核心中實作頻率統計 (histogram) 輸出函式，每秒可能被呼叫數十萬次，則直接使用 `sprintf` 可能帶來哪些效能問題？為何查表法能改善效能？ A: TODO: 找 sprintf src code 以及實際分析回答 - [ ] 某些特殊常數除數可以讓編譯器將除法完全轉換為單一乘法，例如： `⌊n / 274177⌋ = (n × 67280421310721) >> 64`，回答以下: * 為何這類除數被稱為「理想除數」？說明其數學背景 A: 因為 $274177*67280421310721=2^{64}+1$，又因為 C 語言的整數除法特性，因此 `(n x 67280421310721) / (2^64 + 1)` 等同於 `(n x 67280421310721) >> 64`。而因為是完全乘法(得到 128 位元的值)，因此在某些編譯器中，`>> 64` 等同於直接將低位的 64 位元捨棄，連 shift 都不需要做，大幅節省時間。 * 假設 Linux 核心 scheduler 需要頻繁計算某個比例值，如 `scaled = load / 274177`，分析使用上述技巧可能帶來的效益與風險 A: 這種技巧的效益是能將除法轉換為乘法及 right shift，某些編譯器甚至不需要做 shift。能夠節省除法所帶來的巨大開銷，並且在某些沒有除法器的硬體也不須因此透過軟體層來實作，造成效率下降。風險則是每次都是完全乘法，硬體需要將高位的 64-bit 也保留下來，造成成本增加。 TODO: 拿參考書乘法器來解釋 * 若你是編譯器設計者，會如何在最佳化階段自動偵測並套用此類轉換？ A: 我會在看到除數是 274177 時，直接將 `n` 乘上 67280421310721，並只取高位的 64 位元數值。若除數是 67280421310721，則將 `n` 乘上 274177，一樣只取高位的 64 位元數值。 ## 細讀〈[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)〉 - [ ] Linux 核心在雜湊表 bucket 中使用 hlist_head / hlist_node，而不是一般的 doubly-linked list。其節點結構如 `struct hlist_node { struct hlist_node *next, **pprev; }`，不難見到，`pprev` 不是指向前一個節點，而是指向「指向目前節點的指標」。該設計讓刪除節點時不需要知道 list head。回答下列問題： * 若改用典型雙向連結串列 (prev / next)，當刪除 bucket 中的首個節點時，為何必須額外傳入 list head？用 Graphviz 繪製指標關係圖說明原因 A: 在典型雙向鍊結串列中，由於首個節點的 `prev` 指向 `NULL`，因此若要刪除某個節點，需要額外判斷該節點是否為首個節點，如果是的話，要將 `first` 指向首個節點時，無法直接使用 `prev->next = next` 的操作，因此須額外傳入 list head。 ![output](https://hackmd.io/_uploads/H1LcinicWe.jpg) * 說明 hlist 的設計如何消除上述特殊情況。解釋 `__hlist_del()` 的行為並探討其效益 A: 查看以下程式碼: ```c void hlist_delete_node(struct hlist_node *n) { struct hlist_node *next = n->next; // Step 1 struct hlist_node **pprev = n->pprev; // Step 2 // Since there is always a pointer which points to node n, // no special case is needed to deal with. *pprev = next; // Step 3 if (next) next->pprev = pprev; // Step 4 } ``` 透過指標的指標指向前一個節點的 `next` 指標，即使是首個節點，也會指向 `head` 當中的 `next` 指標，而不是像典型鍊結串列那樣指向 `NULL`，因此不需考量例外情況。 - [ ] Linux 核心在 `hash_32()` 中使用乘法雜湊 `val * GOLDEN_RATIO_32 >> (32 - bits)`，其中 `GOLDEN_RATIO_32 = 0x61C88647` 是黃金比例相關常數。探討以下： * 解釋為什麼 Linux hash 函數會取「高位元」作為 bucket index，而不是低位元 A: 原因之一是因為 $h(K) = K \times 2^w \times A >> (w - p)$ 等價於 $h(K) = \lfloor m \times (KA - \lfloor KA \rfloor) \rfloor$，因此取前 $(w-p)$ 個位元。 第二個原因是在 `linux/hash.h` 中 `hash_32` 的註解中有提到高位元可以有更多的隨機性: ```c static inline u32 hash_32(u32 val, unsigned int bits) { /* High bits are more random, so use them. */ return __hash_32(val) >> (32 - bits); } ``` 考量乘法的概念，高位元由於乘法的乘積以及進位的影響，受到更多位元的交互作用，拿來做 hash 分布較均勻。而低位元受到的影響較少，做出來的 hash 分布較不均勻。 * 若 bucket 數量為 `2^p`，說明右移 `(32 - p)` 的數學意義 A: Multiplication Method 的雜湊函數為 $h(K) = \lfloor m \times (KA - \lfloor KA \rfloor) \rfloor$，其中 $m=2^p$。公式的意義為取得 $KA$ 的小數部分，並左移 $p$ 個位元後再取其整數下界。 上述公式可替換為 $h(K) = K \times 2^w \times A >> (w - p)$，其中 $w$ 為 word size，兩者等價而後者(bit shifting)效率較好。此時由於將 $KA$ 乘上 $2^w$，意義等同於將小數部分的位元全部左移到整數部分的位元，因此後續還須右移 $(w-p)$ 個位元，才會等同於原始公式的「左移 $p$ 個位元」。 * 假設系統中 key 值具有模式 `K, K + d, K + 2d, K + 3d, ...`，例如連續的 file descriptor 或 PID。說明為何使用 golden ratio 乘法可以減少 clustering。 A: [Hashing and Hash Tables 課程講義](https://www.cs.hunter.cuny.edu/~sweiss/course_materials/csci335/lecture_notes/chapter05.pdf)中有到: >This property of the golden ratio is actually a special case of a more general theorem proved in 1957 by Vera Turán Sós, which states that for any irrational number $θ$, when the points $\{\theta\}$, $\{2\theta\}$, $\{3\theta\}$, . . . $\{n\theta\}$are placed into the line segment $[0, 1]$, the $n+1$ line segments between them are of at most three different lengths and the next point $\{(n + 1)\theta\}$ will fall into one of the largest intervals! 要看懂這段敘述，需要先理解 three gap theorem，參考維基百科對於 [three gap theorem](https://en.wikipedia.org/wiki/Three-gap_theorem) 的敘述: >In mathematics, the three-gap theorem, three-distance theorem, or Steinhaus conjecture states that if one places n points on a circle, at angles of $\theta$, $2\theta$, $3\theta$, ... from the starting point, then there will be at most three distinct distances between pairs of points in adjacent positions around the circle. When there are three distances, the largest of the three always equals the sum of the other two. 把某個無理數 $\theta$ 不斷加上去，取其小數部分並將其落在 [0, 1] 間的線段，任意相鄰兩點的間距距離最多只有三種。表面上看起來這些點是複雜的散開，實際上局部結構是規律的。再參考前段敘述，golden ratio 是 three gap theorem 的特例，對於每個點所切割的線段，依然保持 golden ratio。並且由於 golden ratio 很難被某個 $\cfrac{p}{q}$ 近似，因此對於有規律的 key 值，使用 golden ratio 能有效減少 clustering，避免堆積在某個 bucket。 - [ ] 設計實驗程式（使用 C 或 Python 皆可)，比較以下對 hash 分布的影響: 0x61C88647, 0x80000000, 0x12345678, 0x54061094 等常數，說明實驗結果與文件中的觀察是否一致。要求： * key 範圍：0 ~ 10000 * bucket 數量：1024 * 繪製 bucket occupancy 分布圖 * 分析 collision 與 clustering 情形 A: 以下分別為 0x61C88647(golden ratio), 0x80000000, 0x12345678, 0x54061094 所繪製的分佈圖，完整程式放在 [github](https://github.com/illdoCc/hash_collision_analysis) 中 ![image](https://hackmd.io/_uploads/HkHDvr_cZl.png) ![image](https://hackmd.io/_uploads/HJRMdruqbx.png) ![image](https://hackmd.io/_uploads/BJB_uHOq-l.png) ![image](https://hackmd.io/_uploads/r1Ahdrdq-l.png) 在使用 golden ratio 時，整體的分佈最均勻，每個 bucket 都大約有 10 筆資料，而 0x80000000 則是指出現 0 和 512 兩個 key value，因此都會發生碰撞，導致資料都會聚集在這兩個 key 當中。使用 0x12345678 及 0x54061094 得到的資料也都有不同程度的碰撞，無法像 golden ratio 如此均勻。 - [ ] hlist 的其中一個設計目標是減少記憶體開銷，因為 bucket head 只需要一個指標，而不是雙向鏈結串列的二個指標。回答以下: * 假設 hash table 有 1,048,576 個 buckets，在 64 位元系統中，分別使用 `struct list_head` 和 `struct hlist_head`，需要多少記憶體？ A: 在 `include/linux/types.h` 中對於兩者的宣告如下: ```c struct list_head { struct list_head *next, *prev; }; struct hlist_head { struct hlist_node *first; }; ``` 在 64 位元系統中，指標的大小為 8 bytes，因此 `list_head` 本身需要占用 16 個 bytes，而 `hlist_head` 占用 8 個 bytes，因此使用 `struct list_head` 需要 $1048576 \times 16=16777216$ bytes 的記憶體。使用 `struct hlist_head` 需要 $1048576 \times 8=8388608$ bytes 的記憶體。 實際運行以下程式，輸出為 `16777216 8388608`: ```c struct list_head { struct list_head *next, *prev; }; struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; }; int main(){ struct list_head l; struct hlist_head h; printf("%zu %zu", sizeof(l) * 1048576, sizeof(h)*1048576); return 0; } ``` * 若該 hash table 用於 networking subsystem（例如 connection tracking），bucket 數量非常大但每個 bucket 的元素數量通常很少，說明為何 hlist 是更合理的設計 A: 在上題可以得知，使用 `hlist` 可以節省一半的記憶體開銷，在 bucket 數量非常大的情況下，節省出來的記憶體是很可觀的。第二點是因為每個 bucket 的元素數量很少，即使使用 `hlist` 這個無法在 O(1) 時間取得 tail 的結構，效能上影響也不大。 * hlist 無法在 O(1) 時間取得 tail，討論在什麼情況下 Linux 核心仍會選擇 `list_head` 而非 `hlist` A: 使用 `hlist` 的好處是可以讓 code smell 變更好，並且相較於 `list_head`，可以讓 bucket 所佔用的記憶體節省一半，但缺點是取得 tail 節點需要花費 O(n) 的時間，這在需要插入節點至尾端的操作(例如 queue)會受到效能影響。 * 舉出 Linux 核心中二個實際使用 hash table 的子系統（例如 dentry cache、routing table 或 TCP connection lookup），並分析其 bucket collision 的行為會如何影響系統效能 A: Linux 核心當中，檔案系統使用到 hash table 來高效尋找檔案位址，`Documentation/filesystems/path-lookup.txt` 當中指出，查找某個檔案時會依照該檔案的父目錄以及檔名去做 hash，找到對應的 bucket 後，走訪該鍊結串列並找到指定的檔案位址，如此就能避免直接去硬碟找，造成效能的下降： >In order to lookup a dcache (parent, name) tuple, we take a hash on the tuple and use that to select a bucket in the dcache-hash table. The list of entries in that bucket is then walked, and we do a full comparison of each entry against our (parent, name) tuple. 以下為 `fs/dcache.c` 當中的程式片段，在取得該檔案的 `hlist_bl_head` 之後，會依序走訪其中的節點並逐一比對 ```c static noinline struct dentry *__d_lookup_rcu_op_compare( const struct dentry *parent, const struct qstr *name, unsigned *seqp) { u64 hashlen = name->hash_len; struct hlist_bl_head *b = d_hash(hashlen); struct hlist_bl_node *node; struct dentry *dentry; hlist_bl_for_each_entry_rcu(dentry, node, b, d_hash) { int tlen; const char *tname; unsigned seq; seqretry: seq = raw_seqcount_begin(&dentry->d_seq); if (dentry->d_parent != parent) continue; if (d_unhashed(dentry)) continue; if (dentry->d_name.hash != hashlen_hash(hashlen)) continue; tlen = dentry->d_name.len; tname = dentry->d_name.name; /* we want a consistent (name,len) pair */ if (read_seqcount_retry(&dentry->d_seq, seq)) { cpu_relax(); goto seqretry; } if (parent->d_op->d_compare(dentry, tlen, tname, name) != 0) continue; *seqp = seq; return dentry; } return NULL; } ``` 此時如果有過多的 bucket collision，在逐一比對階段就會因此消耗大量時間，並且如果單一 bucket 當中有過多的 dentry，無法完整放進 cache 當中也會導致 cache miss。 // TODO: 實際分析 cache miss - [ ] Linux 的雜湊表的設計實際結合三個層面的考量：1) 雜湊函數的統計性質; 2) 資料結構的記憶體布局; 3) CPU cache 與指標操作成本。回答以下： * 若 bucket collision 過多，查找時間將從期望的 $O(1)$ 退化為 $O(n)$，在 Linux 核心中，這種退化可能造成哪些實際系統效應？ A: bucket collision 除了會導致查找時間下降外，若該 bucket 當中的節點過多，無法完整放進 cache 當中也會導致 cahce miss。 * 假設某個攻擊者可以控制輸入 key（例如 HTTP header 或網路封包欄位），並刻意製造大量 hash collision。說明這種攻擊如何影響系統效能，並舉出 Linux 或其他系統曾出現的類似案例 (提示: git log) A: 利用 git log 查找到其中一個 commit 當中提到作者修改了 hash 的方法，改為 jhash，避免 collision: >commit 4a0ec2aa0704c8271fde33a0f7bb92d09c066c17 Author: Eric Dumazet Date: Tue Oct 8 12:01:01 2024 +0000 ipv6: switch inet6_addr_hash() to less predictable hash > >In commit 3f27fb23219e ("ipv6: addrconf: add per netns perturbation in inet6_addr_hash()"), I added net_hash_mix() in inet6_addr_hash() to get better hash dispersion, at a time all netns were sharing the hash table. > >Since then, commit 21a216a8fc63 ("ipv6/addrconf: allocate a per netns hash table") made the hash table per netns. > >We could remove the net_hash_mix() from inet6_addr_hash(), but there is still an issue with ipv6_addr_hash(). > >It is highly predictable and a malicious user can easily create thousands of IPv6 addresses all stored in the same hash bucket. > >Switch to __ipv6_addr_jhash(). We could use a dedicated secret, or reuse net_hash_mix() as I did in this patch. 從上述 commit message 順藤摸瓜，可以看到實際程式片段： ```c hlist_for_each_entry_rcu(ifp, &net->ipv6.inet6_addr_lst[hash], addr_lst) { ndev = ifp->idev->dev; if (l3mdev_master_dev_rcu(ndev) != l3mdev) continue; /* Decouple optimistic from tentative for evaluation here. * Ban optimistic addresses explicitly, when required. */ ifp_flags = (ifp->flags&IFA_F_OPTIMISTIC) ? (ifp->flags&~IFA_F_TENTATIVE) : ifp->flags; if (ipv6_addr_equal(&ifp->addr, addr) && !(ifp_flags&banned_flags) && (!dev || ndev == dev || !(ifp->scope&(IFA_LINK|IFA_HOST) || strict))) { rcu_read_unlock(); return ndev; } } ``` 因此如果 collision 過多，在迴圈當中會搜尋過久影響效能。 * 設計改進方案，使雜湊表在碰撞過多時仍能維持穩定性能，應適度考慮 bucket resize, alternate hashing, tree-based bucket, randomized hashing 等手法，並分析這些方法在 Linux 核心中的可行性 (後續可提交貢獻到 Linux 核心) A: 若要使雜湊表在碰撞過多時依舊維持穩定性能，必須使其能夠將聚集在同一個 bucket 的資料分散到不同 bucket 當中。 使用 git log 查看一些關於 hash collision 的 commit： 在 e28c5bc45640bc851e8f7f0b8d5431fdaa420c8e 這個 commit 當中，作者使用 bucket resize，將 3 bits hash table 擴展為 12 bits，如此可避免每個 bucket 當中儲存太多數值。不過這種將 bucket 擴大的作法在記憶體空間珍貴的系統(例如 embedded system)不適合。 在 4a0ec2aa0704c8271fde33a0f7bb92d09c066c17 當中作者則是將 `ipv6_addr_hash` 改為更具有安全性的 `__ipv6_addr_jhash`，`ipv6_addr_hash` 透過 xor 及 right shift 達成，hash 結果容易預測，容易被濫用造成 hash collision，而 `__ipv6_addr_jhash` 則是利用了 Jenkins hash 的方式加入一個隨機值避免此問題。 // TODO: 想自己的方法 - [ ] 教材提到 Fibonacci hashing 與 Three-gap theorem 的數學背景。回答以下: * 為何 Linux 核心實作 hash 函數時，偏好使用整數運算與 bit shift，而非浮點運算？ A: 在某些嵌入式系統中，並不具備浮點運算單元(FPU)，若要進行浮點運算，就需要以軟體來模擬，導致效能下降。而所有硬體都具備 ALU，可以進行整數運算與 bit shift，因此實作 hash 函數時以整數運算及 bit shifting 會比浮點運算好。 * 將數學式 $h(K) = \lfloor m (KA - \lfloor KA \rfloor) \rfloor$ 轉換為 Linux 核心實際程式碼形式並解釋每個步驟對應的位元操作 A: 在 Linux 核心中，會將上述數學式改為整數運算與 bit shift: $h(K)=K\times 2^w\times A>>(w-p)$，其中 $w$ 為 word size，$2^p=m$。$KA\times 2^w$ 之後，會將小數的位元左移到整數的位元，再右移 $(w-p)$ 個位元將低位移除，效果等同於原始數學式。以下為 Linux 針對 32 位元雜湊函數的原始程式碼: ```c #define GOLDEN_RATIO_32 0x61C88647 #ifndef HAVE_ARCH__HASH_32 #define __hash_32 __hash_32_generic #endif static inline u32 __hash_32_generic(u32 val) { return val * GOLDEN_RATIO_32; } static inline u32 hash_32(u32 val, unsigned int bits) { /* High bits are more random, so use them. */ return __hash_32(val) >> (32 - bits); } ``` 這裡選擇的 $A$ 為 $1-\varphi^{-1}$，$\varphi$ 代表 golden ratio。而 `GOLDEN_RATIO_32` 即為 $A\times 2^{32}$，因此在 `__hash_32_generic` 當中所回傳的數值即為 $K\times 2^{32}\times A$，`hash_32` 當中的 bits 為 $p$，因此將該函式攤開即等同於 $K\times 2^{32}\times A>>(32-p)$。 * 若系統由 32 位元架構改為 64 位元架構，hash 函數應如何調整？ A: 32 位元程式中的 `GOLDEN_RATIO_32` 為 $A\times 2^{32}$，word size 為 32。因此 64 位元只需將 `GOLDEN_RATIO_64` 改為 $A\times 2^{64}$，並且將 `hash_32` 當中的 `(32-bits)` 改為 `(64-bits)` 即可。 - [ ] 把 `GOLDEN_RATIO_64` 放回環論語境，探討可逆性與雜湊不可逆性的差異 * 在環 $R=\mathbb{Z}/2^{64}\mathbb{Z}$ 中，判定 `GOLDEN_RATIO_64` 是否為 unit。必須給出判定條件與理由 (提示: 奇偶性與 $\gcd(C,2^{64})$) A: * 若它可逆，說明你如何以擴展歐幾里得演算法求出 $C^{-1}\bmod 2^{64}$，隨後解釋即使乘法在 $R$ 中可逆，為何 `hash_64(val,bits)` 依然不可逆。你必須指出右移取高位元等價於丟棄資訊、丟棄的位元數量與 preimage 的大小關係，並把這點連結到雜湊表只需要分布性，而不需要可逆性 ## 探討〈[基於 C 語言標準研究與系統程式安全議題](https://hackmd.io/@sysprog/c-std-security)〉 - [ ] 文件提及 integer conversion rank 和 usual arithmetic conversions，在系統程式設計中，混合使用 `signed` 與 `unsigned` 型別是緩衝區溢位（buffer overflow）的常見根源。回答以下: * 參考 C11 標準 §6.3.1.8 (Usual arithmetic conversions)，當一個 `signed long` (64-bit) 與一個 `unsigned int` (32-bit) 進行二元運算（如比較大小或加法）時，標準規定具體會發生什麼轉型？這與 `signed int` 和 `unsigned int` 的情況有何不同？ A: C11 標準 §6.3.1.8 當中提到以下轉換規則: >Otherwise, the integer promotions are performed on both operands. Then the following rules are applied to the promoted operands: If both operands have the same type, then no further conversion is needed. Otherwise, if both operands have signed integer types or both have unsigned integer types, the operand with the type of lesser integer conversion rank is converted to the type of the operand with greater rank. Otherwise, if the operand that has unsigned integer type has rank greater or equal to the rank of the type of the other operand, then the operand with signed integer type is converted to the type of the operand with unsigned integer type. **Otherwise, if the type of the operand with signed integer type can represent all of the values of the type of the operand with unsigned integer type, then the operand with unsigned integer type is converted to the type of the operand with signed integer type.** Otherwise, both operands are converted to the unsigned integer type corresponding to the type of the operand with signed integer type. 在第四點 (粗體處) 當中有提到，如果該 signed integer type 的數值範圍可以容納該 unsigned integer type 的數值範圍，那這個 unsigned integer type 會被轉變為 signed integer type。 `signed long` (64-bit) 的數值範圍為 $-2^{63}$ ~ $2^{63}-1$，而 `unsigned int` (32-bit) 則是 $0$ ~ $2^{32}-1$，由於 `signed long` 的數值範圍可以完整涵蓋 `unsigned int`，因此 `unsigned int` 會被轉變為 `signed long`。 實際運行以下程式並以 gdb 印出型別，和上述相符： ```c long a = 100; unsigned int b = 100; a = a + b; ``` ``` (gdb) ptype a+b type = long ``` `signed int` 與 `unsigned int` 的轉換規則則是參考第三點，如果該 unsigned integer type 的 rank 大於或等於 signed integer type 的 rank，則會將 signed integer type 轉變為 unsigned integer type。 C11 §6.3.1.1 當中有提到 unsigned integer type 的 rank 與對應的 signed integer type 的 rank 相等，因此運算時會將 `signed int` 轉變為 `unsigned int`: >The rank of any unsigned integer type shall equal the rank of the corresponding signed integer type, if any. 運行以下程式並用 gdb 印出型別，和上述相符： ```c signed int a = 100; unsigned int b = 100; a = a + b; ``` ``` (gdb) ptype a+b type = 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` (新配置) 的記憶體地址（數值）相同，它們在語意上是否相等？ A: 不相等。首先，C99 6.2.4 當中提到指標是指向一個「物件」，而非單純指向地址: >The value of a pointer becomes indeterminate when **the object it points to** reaches the end of its lifetime. 再參考該段全文，可以知道當一個物件的 lifetime 結束後，此時再去存取會是 UB: >The lifetime of an object is the portion of program execution during which storage is guaranteed to be reserved for it. An object exists, has a constant address,25) and retains its last-stored value throughout its lifetime.26) If an object is referred to outside of its lifetime, the behavior is undefined. The value of a pointer becomes indeterminate when **the object it points to** reaches the end of its lifetime. 被釋放的指標所指向的物件的 lifetime 已經結束，而新配置的指標所指向的是一個新的物件，即使該物件所佔據的記憶體地址和被釋放的物件的記憶體地址相同，語意上也早已不相等。 * 討論 Alias Analysis（別名分析）如何利用 "Strict Aliasing Rule" 或 "Object Lifetime" 假設，認定對 `q` 的寫入不會影響 `p` 指向的內容，進而對程式碼進行激進的最佳化 (例如刪除看似多餘的 null check) A: // TODO: 借編譯器教科書講解 * 考慮以下程式碼: ```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) 來強迫編譯器保留清除指令？這與文件中提到的「物件生命週期」概念有何衝突與妥協？