# 2025q1 Homework5 (assessment)
contributed by < `fcu-D0812998` >
## 從前 6 週的測驗題選出 3 題改進
### [W2Q3](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-3)
#### 解釋上述程式碼運作原理
將 LeetCode 題目「Two Sum」以 Linux 核心風格實作 hash table ， Two Sum 題意是給一個整數陣列 nums 和一個整數 target，找出陣列中「兩個數字加總為 target」的索引。
```c
nums = [2, 11, 7, 15], target = 9
// 2 + 7 = 9 → 回傳 [0, 2] 或 [2, 0]
```
資料結構定義
* map_t（整個 hash table）
```c
typedef struct {
int bits; // 決定雜湊表大小 (大小 = 2^bits)
struct hlist_head *ht; // hash bucket 陣列，每個 bucket 是一個 hlist
} map_t;
```
* hash_key（表內元素）
```c
struct hash_key {
int key; // 被存入的 key（這邊是 nums[i]）
void *data; // 存 index 的 pointer（malloc int*）
struct hlist_node node; // hlist 結點
};
```
hash 函數
* 使用 [Fibonacci Hashing](https://en.wikipedia.org/wiki/Hash_function#Fibonacci_hashing)
```c
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits) {
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
為甚麼 Fibonacci Hashing 是黃金比例 ?
根據 [GOLDEN_RATIO](https://hackmd.io/rpIi8FeqQ9eBJ-UTFgb--A?view#GOLDEN_RATIO) ，這是個無理數，表示小數部分無限不循環，因為無理數無法與整數形成「整數倍關係」或「週期」，所以乘上它之後的結果會分布得非常均勻、不重複、不循環。
查詢操作
* 呼叫 find_key() 以 key 為引數尋找對應的 hlist
* 若找到，回傳該 key 對應的 data（這邊是 int*，代表之前出現過的 index）
```c
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn->data;
}
```
插入操作
* 若該 key 不存在（find_key == NULL）
* 分配 hash_key 結構，填入 key / data
* 以頭插法加入對應 bucket
```c
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return;
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, map->bits)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
if (first)
first->pprev = &n->next;
h->first = n;
n->pprev = &h->first;
}
```
* 重點是 pprev 是指向「指向自己的指標」，這樣刪除時就不需知道 head 也能刪除任意節點。
two sum
```c
for (int i = 0; i < numsSize; i++) {
int *p = map_get(map, target - nums[i]);
if (p) {
ret[0] = i, ret[1] = *p;
*returnSize = 2;
break;
}
p = malloc(sizeof(int));
*p = i;
map_add(map, nums[i], p);
}
```
* 每次查看 target - nums[i] 是否出現過
* 若出現，取出先前索引 *p 並組成 [i, *p]
* 若尚未出現，記錄 nums[i] 並存 index i
#### 改進
利用巨集 `list.h` 減少程式碼行數
* 插入
```diff
struct hlist_head *h = &map->ht[hash(key, map->bits)];
+hlist_add_head(&kn->node, h);
-struct hlist_node *n = &kn->node, *first = h->first;
-n->next = first;
-if (first)
- first->pprev = &n->next;
-h->first = n;
-n->pprev = &h->first;
```
* 走訪
```diff
+struct hash_key *kn;
+hlist_for_each_entry(kn, head, node)
+ if (kn->key == key)
+ return kn;
-for (struct hlist_node *p = head->first; p; p = p->next) {
- struct hash_key *kn = container_of(p, struct hash_key, node);
- if (kn->key == key)
- return kn;
-}
```
* 刪除
```diff
+hlist_del_init(&kn->node);
-struct hlist_node *next = n->next, **pprev = n->pprev;
-*pprev = next;
-if (next)
- next->pprev = pprev;
-n->next = NULL;
-n->pprev = NULL;
```
#### 探討 Linux 核心中使用 hash table 的應用案例
##### [Dentry Cache](https://github.com/torvalds/linux/blob/master/fs/dcache.c)
當我再找 Linux 核心中使用 hash table 的應用案例時，發現了 dentry cache ，dentry cache是 Linux VFS 層用來加速路徑查找的資料結構，舉例來說，每次存取一個檔案如 `/a/b/c.txt` ，都需要從根目錄層層找下去。為了避免每次都從磁碟查找，Linux 會將這些「路徑中每一層的目錄對應關係」緩存在記憶體中，以 struct dentry 結構儲存，並使用一個 hash table 快速存取。
盡力解釋一下 dentry hash table 的運作原理 :
* hash table 初始化，根據你想設置多少 buckets ( `dhash_entries` )， 13 是預設 log2 上限，假設若沒給 `dhash_entries` ，kernel 會估個 2¹³ = 8192 為預設大小，再來每個 dentry （代表一個檔案或目錄的名字）都會根據它的名字 hash 成一個 unsigned int 的 32-bit 值，但我們不可能用一個 4G (2³²) 大小的陣列來存 dentry，我們通常只會配置例如 8192 個 bucket ，你只想選擇 8192 個 bucket，那就需要把這個 hash 值的前面 13 bits 抽出來當成 index ，假設你想要 13 bits index，那你要把 32 - 13 = 19 個 bits 去掉（右移 19 bits）。
```c
static void __init dcache_init_early(void)
{
...
dentry_hashtable =
alloc_large_system_hash("Dentry cache",
sizeof(struct hlist_bl_head),
dhash_entries,
13,
HASH_EARLY | HASH_ZERO,
&d_hash_shift,
NULL,
0,
0);
d_hash_shift = 32 - d_hash_shift;
...
}
```
:::info
雖然 dentry cache 已經用 [Jenkins Hash](https://en.wikipedia.org/wiki/Jenkins_hash_function) 去避免碰撞發生，且更均勻的分佈，那為甚麼不使用 Fibonacci Hashing 這種黃金比例 hash 讓他分布更均勻?
:::
##### [rhashtable](https://github.com/torvalds/linux/blob/master/lib/rhashtable.c)
rhashtable 是 Linux 核心提供的一種可動態擴充、支援併發、安全與高效的通用雜湊表實作。它是針對 kernel 多執行緒、 RCU 協同存取場景設計的，是否能將 rhashtable 實作在 dentry cache 中?
##### [Re: FYI: path walking optimizations pending for 6.11](https://lkml.indiana.edu/2406.2/07225.html?utm_source=chatgpt.com)
這封原始郵件是 Linus 對某些人試圖用 rhashtable 來替換 dcache 中雜湊機制感到懷疑。他指出以下幾點
* 現有的 dcache hash 非常快，因為採用簡單的 array + linked list 架構，且大多數 bucket 裡面只有一個 entry，因此 lookup 幾乎是 O(1)。
* rhashtable 的開銷大於收益，雖然支援彈性成長、可調整大小等功能，但這些在 dentry case 中未必必要。多一層 indirection 和記憶體對齊導致 cache miss 風險增加。
但裡面 Kent Overstreet 有做回應， Kent 是 Linux 開發社群中以 Bcache 與內核優化知名的開發者。他的立場是:
* rhashtable 存取時需要兩次 dependent loads ，導致 pipeline stall。
* 假設 CPU 支援，能讓讀取 bucket 和 linked node 一次完成，減少 load latency。
這樣只需一次 load 即可拿到兩次 load 的值，節省延遲與 cache miss 機會，這邊想到的第一個想法就是利用 packing 的方法去做是否可以達成。
## 紀錄閱讀[〈因為自動飲料機而延畢的那一年〉](https://hackmd.io/@jserv/HkyCt0hqb?type=view)的啟發
在經過六週的 Linux 課程後，以前的我可能會覺得寫程式不就是幾句判斷式寫一寫就好的東西，但實際上，頂級業界真正需要的是能夠持續優化程式碼的人，而我又為甚麼一定要做到頂級 ? 搭配這篇文章老師說的一段話
>你最大的問題在太害怕失敗了，既然都已經決定要延畢做飲料機了，那就要好好做，才不會辜負當初自己的期望。
正如老師說的，既然都要修這堂課了，那就該好好做，而在審視我前六週的我時我深深體悟到除了剛上這堂課時有專心過一段幾周的時間，後面感覺都是為了應付，而不是認真的去好好做，在此後觀摩其他學員的成果，讓我深刻感受到自己還有很多的不足，像是為甚麼這位學員能想到這個方法?而我不能。而文章中老師的這段話又剛好能符合我現在的狀況
>你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。
既然事情要完蛋了，我就應該去學會處理失敗，當作經驗去做吸收，而不是為了怕避免失敗去應付這些事情。
## 簡述你想投入的專案
1. 因實驗室主要也是研究資訊安全方面的，所以想探討 linux 是否有資訊安全方面的問題。
預防 [ROP 攻擊](https://ithelp.ithome.com.tw/m/articles/10356195)，甚麼是 ROP 攻擊，執行流程為 :
* 找到有 Buffer overflow 風險的漏洞，例如 `gets(buffer)` 假設 buffer 的大小為 40 個字元
* 攻擊者就輸入以下資料
```
"A" * 40 → 填滿 buffer（前40 bytes）
0x401010 → gadget: pop rdi; ret
0x404080 → "/bin/sh" 地址，會放進 rdi
0x400520 → system() 函數位置
```
* 這樣的話就會超過 40 個字元的大小限制，記憶體就會順著往上寫，蓋掉 saved EBP 跟 return address ，根據上面的資料會先執行 `gadget: pop rdi; ret` ，這邊就會將攻擊者要得地址放到 rdi 然後 ret 到另一個他想跳的地址。
* [ASLR](https://zh.wikipedia.org/zh-tw/%E4%BD%8D%E5%9D%80%E7%A9%BA%E9%96%93%E9%85%8D%E7%BD%AE%E9%9A%A8%E6%A9%9F%E8%BC%89%E5%85%A5) 是一個每次當你執行一個程式檔案時，作業系統會為它建立一個新的 process ，這個 process 會有自己的記憶體空間，但如果發生格式化字串漏洞或者是 [heap overflow](https://en.wikipedia.org/wiki/Heap_overflow) 攻擊者就可以反推出其他 gadget 或函式的位置。我的想法是但若能在程式執行期間，定期重新排列每個函式的記憶體位置，同時確保不影響其正確執行邏輯，便能有效阻斷 ROP 攻擊的條件。因為就算攻擊者成功洩漏某個 gadget 的位置，該位址也會在極短時間內失效，迫使攻擊者無法構造穩定的攻擊鏈。這種方式可視為將傳統靜態的 ASLR 進化為一種動態、自我變異的執行時位址防禦機制。
2. 完成作業三
Sign in with Wallet
Connect another wallet