---
# System prepended metadata

title: 2025q1 Homework2 (quiz1+2)

---

# 2025q1 Homework2 (quiz1+2)
contributed by <`Andrushika`>

## Week 1 Q1
本題要實作 `list_insert_before` 這個函式：
![image](https://hackmd.io/_uploads/rJ8iAnpokl.png)

如果只看函式說明，參數的用法還是有些難懂。所以往前找到了 `list_t` 和 `list_item_t` 的定義：
```c
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;
```

由此可知，`list_t` 代表著整個鏈結串列，其中每個節點的結構為 `list_item`。

接下來，在不看題目給定的程式碼的狀況下，思考應該如何實作；可以歸納為以下步驟：
1. 用迴圈迭代，維護兩個 `list_item*` (`*prev`, `*curr`)，代表著目前和上一個節點
2. 持續迭代更新兩個 pointer，直到 `curr == before`
3. 插入 `*item` 到 `*prev` 和 `*curr` 之間

```c
void list_insert_before(list_t *l, list_item_t *before, list_item_t *item) {
    if (!l || !item) return;

    // 如果要插入的位置就是 head (或原本就是 empty)
    // 那 item 會變成新的 head
    if (before == l->head) {
        item->next = l->head;
        l->head = item;
        return;
    }

    list_item_t *prev = NULL;
    list_item_t *curr = l->head;

    // 迭代直到找到 curr == before 或走到串列末端
    while (curr && curr != before) {
        prev = curr;
        curr = curr->next;
    }

    // 連結新節點
    if (curr == before) {
        item->next = curr;
        if (prev) {
            prev->next = item;
        }
    }
}
```

但這樣的實作方式不太優雅，需要考慮太多 edge cases（要從 `head` 插入等等）

改用 pointer of pointer 來簡化過程，用一個比較生動的描述幫助理解：
1. 找到指向 `*before` 的指標 （找到 `*before` 他家，即 `**before`）
2. 把 `*before` 從他家趕出來，讓新節點 `*item` 住進去
（如此一來，原本指向 `*before` 的，會變成指向 `*item`）
3. `*item` 的下一位指向 `*before`

依題意可實作成下方程式碼：
```c
void list_insert_before(list_t *l, list_item_t *before, list_item_t *item) {
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    (*p)->next = before;
}
```

將步驟視覺化：
（假設 `before->value = 4`, `item->value = 3`）

先移動到 pointer of pointer，找到 `*before` 的家
![image](https://hackmd.io/_uploads/HyuIl0aiyg.png)
![image](https://hackmd.io/_uploads/S1ZDxRTokl.png)

把 `*before` 從他家趕出來，讓新節點 `*item` 住進去
![image](https://hackmd.io/_uploads/rJfQF0pskg.png)

將`*item` 的下一位指向 `*before`
![image](https://hackmd.io/_uploads/ry2QFA6skx.png)


## Week 1 Q2
先看節點的結構：
```c
typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;
```

可以觀察到 `*l`, `*r` 這樣指向下一個節點的指標，可以合理推測是使用 Binary tree 進行 free block 的管理。
本題要完成的是 `remove_free_tree` 這個函式，看起來和 Binary Search Tree 的 remove 操作相同，該函式的流程如下：
1. 先用 `find_free_tree(root, target)` 找到欲刪除節點的位置
2. 根據 `target` 擁有不同數量的 child，有不同的策略
    * `target` 同時有 `l`, `r` child
        * 找到 `target` 的 `pred`，稍等要用它來取代 `target` 本身
        * 如果 `pred` 是 `target` 的 `l` child，可以直接用 `pred` 替換 `target`
        * 如果不是，代表要先從其他 subtree 中移除 `pred`；先遞迴呼叫 remove 後，才把它用來替換 `target`
    * `target` 只有一個子節點，直接用子節點替換 `target`
    * `target` 是 leaf node，直接刪除 target
3. 清理 target 節點，防止 dangling pointer
         
在做題目的時候，一直卡在 predecessor node 這個名詞；原來他指的是 left subtree 中最大的節點。

了解名詞後，要填出空缺處的 code 就很簡單了：
```c
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred)->r)
    pred_ptr = &(*pred)->r;
```

## Week 1 Q3
本題目標為實作 quick sort，不使用傳統遞迴的方式，而是改用兩個 linked list pointer `left`, `right` 來儲存陣列中元素和 pivot 比較大小後的結果；比較小的會被儲存在 `left`，比較大的儲存在 `right`。

針對程式碼中空缺的地方進行填補：
### rebuild_list_link
下方的程式在進行 circular doubly linked list 的重建，可以看出迴圈的最後是在連接 linked list 的 head 和 tail；因要進行雙向的連結，故補上該程式碼。
``` c
static void rebuild_list_link(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *prev;
    prev = head;
    node = head->next;
    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    head->prev = prev; // GGGG
}

```

### quick_sort 
參照題意，每次會從 `begin[]` 選定 pivot（每個 `begin[i]` 都是一個 linked list 的 `head`）
讓所有元素和 `pivot` 比大小，並依結果放進 `left` or `right`；分組完畢後再將 `left` 和 `right` 放進 `begin[]` 中。

原先的實作方式中還會使用 `end` 去紀錄子陣列結束點；但在 linux kernel list API 中，可以直接呼叫 `list_end()`，就無需再用額外的記憶體空間紀錄 `end`。
分組完畢的結果可以參考以下：
```graphviz
digraph g6 {
    node[shape=plaintext];
    // 定義節點，使用 label 避免方括號問題
    "begin_0" [label="begin[0]", fontcolor="brown"];
    "begin_1" [label="begin[1]", fontcolor="brown"];
    "begin_2" [label="begin[2]", fontcolor="brown"];
    "left" [fontcolor="purple"];
    "right" [fontcolor="purple"];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    l1 [label="NULL", fontcolor="black"];
    l2 [label="NULL", fontcolor="black"];
    l3 [label="NULL", fontcolor="black"];

    node[shape=box];
    n0 [label="0"];
    n1 [label="1"];
    n2 [label="2"];
    n3 [label="3"];
    n4 [label="4"];

    // 設定相同層級
    { rank="same"; }

    // 定義指向關係
    "begin_0" -> n1;
    "begin_1" -> n3; 
    "begin_2" -> n4;
    pivot -> n3 -> l1;
    left -> n1 -> n0 -> n2 -> l3;
    right -> n4 -> l2;
    L -> n3;
    R -> n4;
}
```
之後會繼續對左、右子鏈結串列持續 quick sort。當 `L == R`，也就是 list 中只剩下一個節點時，會直接將其將到 result 中。

這樣的實作方式，需要確保 `left`, `right` 在分割完畢後，放進 `begin[]` 時的順序需為 inorder。根據這個線索，可以完成程式碼空缺部分：

```c
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    struct list_head *begin[max_level];
    struct list_head *result = NULL, *left = NULL, *right = NULL;
    begin[0] = list->next;
    list->prev->next = NULL;
    while (i >= 0) {
        struct list_head *L = begin[i], *R = list_tail(begin[i]);
        if (L != R) {
            struct list_head *pivot = L;
            value = pivot->value; // HHHH
            struct list_head *p = pivot->next;
            pivot->next = NULL; /* break the list */

            while (p) {
                struct list_head *n = p;
                p = p->next;
                int n_value = n->value; // IIII
                if (n_value > value) {
                    n->next = right;
                    right = n;
                } else {
                    n->next = left;
                    left = n;
                }
            }

            // 此處須以 inorder 插入
            begin[i] = left;
            begin[i + 1] = pivot; // JJJJ
            begin[i + 2] = right; // KKKK
            left = right = NULL;
            i += 2;
        } else {
            if (L) {
                L->next = result;
                result = L;
            }
            i--;
        }
    }
    list->next = result;
    rebuild_list_link(list);
}
```

## Week 2 Q1
本題和 `Week 1 Q3` 相似，都和 quick sort 高度相關；但實作手法不同，本題更全面使用 linux kernel list API。

在開始完成題目需求前，先探討一下前面的亂數生成、洗牌函式。
### get_num 
一開始看不太懂，為何一個沒有傳入參數的函式，可以用來產生每次都不相同的隨機數？
原來是這三行的定義發揮了作用：
```c
static uint16_t s1 = UINT16_C(2);
static uint16_t s2 = UINT16_C(1);
static uint16_t s3 = UINT16_C(1);
```
此處使用 `static`，讓 `s1`, `s2`, `s3` 即使在函式結束後，占用的記憶體不會被釋放掉；進而導致每次呼叫 `get_num()` 會有不一樣的結果。

`static` 的特性可以參考 C99 規格書：
> An object whose identifier is declared with external or internal linkage, or with the storage-class specifier static has static storage duration. **Its lifetime is the entire execution of the program** and its stored value is initialized only once, prior to program startup. (C99 6.2.4.3)

#### 隨機數產生的小細節？
`get_num()` 實際上是使用了 [Linear congruential generator (LCG)](https://en.wikipedia.org/wiki/Linear_congruential_generator) 來產生隨機亂數：
$$X_{n+1}=(aX_n+c)\space mod\space m$$
但是單個變數所產生的亂數，在經過 $m$ 週期後就會重複。
題目的設計使用了三個變數計算 LCG 後 XOR，使重複的週期延長，為三個 $m$ 的最小公倍數。當三個 $m$ 互質時，可以達到最長的周期。
舉例來說，題目裡設計的三個 $m$ 分別為 `30269`, `30307`, `30323`，其週期為： $$30269 \times 30307 \times 30323 = 2.8 \times 10^{13}$$

### random_shuffle_array
先看程式碼：
```c
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0; i < len; i++) {
        /* WARNING biased shuffling */
        uint16_t j = get_unsigned16() % (i + 1);
        operations[i] = operations[j];
        operations[j] = i;
    }
}
```
這個算法存在兩個問題：
1. 在選擇隨機數時，每次隨機數出現的機率不同。由於每次都是對 `i+1` mod，那麼對於其他 `n` (`i+1 <= n < len`) 就沒有被選到的機會。
這樣會造成某些排列組合出現的機率比較高，亂度不足。
2. 在完成隨機 index 選擇後，swap 的操作有些奇怪。除非能保證輸入的陣列滿足 `operations[i] == i` 的條件，否則 shuffle 函式的結果會有錯誤。這不只是亂度不足的問題，可能會意外改變了陣列內的元素。若不能保證 input，使用 swap 才正確。

### list_quicksort
此處為本題填空主要作答的地方，考驗點應該是 linux kernel list API 的熟悉程度，且前面已經解釋過 quick sort 的思路，故不再詳細解釋。
附上程式碼：
```c
{
    struct list_head list_less, list_greater;
    struct listitem *pivot;
    struct listitem *item = NULL, *is = NULL;

    if (list_empty(head) || list_is_singular(head))
        return;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    // AAAA
    pivot = list_first_entry(head, struct listitem, list);
    // BBBB
    list_del(&pivot->list);

    list_for_each_entry_safe (item, is, head, list) {
        if (cmpint(&item->i, &pivot->i) < 0)
            list_move_tail(&item->list, &list_less);
        else
            // CCCC
            list_move_tail(&item->list, &list_greater); 
    }

    list_quicksort(&list_less);
    list_quicksort(&list_greater);
    
    //DDDD 加入單顆節點到 linked list 中
    list_add(&pivot->list, head); 
    
    //EEEE 加入整串 left 到 head
    list_splice(&list_less, head);
    
    //FFFF 加入整串 right 到 tail
    list_splice_tail(&list_greater, head);
}
```

#### 為何使用 `list_move` 取代 `list_move_tail` 時無法滿足 stable sort？
根據 kernel.org 於 Linux Kernel API List Management Functions 的說明，`list_move` 的作用如下：
```c
void list_move(struct list_head * list, struct list_head * head)
```
> delete from one list and add as another’s **head**

因為 `list_for_each_entry_safe` 是逐一走訪，比較後方的節點也會比較晚走訪到。如果使用 `list_move`，當兩個節點值相同時，會將**後方節點插入在前方節點之前**，也就破壞了 stable sort 的規則。


## Week 2 Q2
`clz2()` 包含了兩個參數，其定義如下：
```c
unsigned clz2(uint32_t x, int c)
```

其中 `x` 代表目前要計算 count leading zero 的目標數，`c` 代表目前已經累積計算第幾輪。因為每次會把 `x` 拆成一半 （upper 和 lower） 以進行後續運算，每次遞迴呼叫時，`x` 的 bits 長度減半 （$\log_2x \rightarrow\frac{\log_2x}{2}$），所以這個函式可以在 $O(\log(\log_2x))$ 的時間複雜度下完成計算。
>註：對於任意 `x`，其在二進位制下的 bits 數可表示為 $\log_2x$

### 模擬運算過程
假設要對 `0x00000001` count leading zero，運行的過程應該長怎樣呢？

#### 第一輪
`x = 0x00000001`, `c = 0`
| Upper | Lower |
| -------- | -------- |
| 0000 0000 0000 0000 | 0000 0000 0000 0001 |

此時 `upper` 為 `0`，確定至少有 16 個 leading zero。
因此呼叫 `return 16 + clz2(lower, c+1)`，除了加上答案外，繼續遞迴計算剩下的 bits 結果。（目前累積 16 個 `0`）

#### 第二輪
`x = 0x0001`, `c = 1`
| Upper | Lower |
| -------- | -------- |
| 0000 0000 | 0000 0001 |

此時 `upper` 為 `0`，確定至少有 8 個 leading zero。
因此呼叫 `return 8 + clz2(lower, c+1)`，除了加上答案外，繼續遞迴計算剩下的 bits 結果。（目前累積 24 個 `0`）

#### 第三輪
`x = 0x01`, `c = 2`
| Upper | Lower |
| -------- | -------- |
| 0000 | 0001 |

此時 `upper` 為 `0`，確定至少有 4 個 leading zero。
因此呼叫 `return 4 + clz2(lower, c+1)`，除了加上答案外，繼續遞迴計算剩下的 bits 結果。（目前累積 28 個 `0`）

#### 第四輪
`x = 0x1`, `c = 3`
| Upper | Lower |
| -------- | -------- |
| 00 | 01 |

做到這邊時，已經不用繼續遞迴呼叫，可以直接從 `magic[]` 來獲取結果。
判斷依據是 `magic[]` 的 size 為 4，且程式中只有一行會用到 `magic[]`：
```c
return upper ? magic[upper] : KKKK + magic[lower];
```
由此可知，當 `upper` 和 `lower` 小於 `4` 時，可以直接進行查表；且此時 `c = 3`，因此可以借助這些線索，還原 `clz2()` 程式碼如下：

```c
static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == 3)
        return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}
```

### 整數開根號實作
> 參閱老師撰寫的 [從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt) Digit-by-digit Method 部分，但該章節最後好像沒有寫完整，因此我參照 [維基百科](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_(base_2)) 將剩餘證明過程補齊。

對於二進位制，可以先假設我們要計算平方根的數如下：
$$N^2 = (a_n + a_{n-1} +\cdots+a_1+a_0 )^2$$ 
> 注意！此處的 $a_n$ 為最高位係數！所以從最高位到最低位，$n$ 是倒序的

以上假設數的二進位表示法共有 $n$ 位，其中每一個 $a_m$ 皆為 $2^m$ 或 $0$。
透過 digit-by-digit 的方法，由高位開始找到低位，依序判斷「放不放得下」。為了計算方便，定義一個符號：

$$P_m = a_n + a_{n-1} +\cdots+a_{m+1}+a_m $$

由於會逐位進行測試「是否塞得下」，$P_m$ 將代表著「目前確定的部份和」。隨著每次測試，$P_m$ 都會更新一次，直到 $P_0 = N$。

逐位檢查的過程，事實上就是在檢查以下條件是否成立：
$$\begin{aligned} &P_m^2 \le N^2 \\
\Rightarrow \space&(P_{m+1}+2^m)^2 \le N^2 \end{aligned}$$


但因為每次檢查條件都要計算平方的話，成本很高；可以再額外定義兩個符號，幫助後續的加速與簡化。

$$X_m = N^2 - P_m^2$$ 主要的想法是，每次計算完「是否塞得下某數」之後，就把該數從總數中減去。這裡的 $X_m$ 代表餘數，亦會隨著逐位更新而變動：當第 $m$ 位決定後，距離最終目標還剩多少？當 $P_m^2$ 足夠逼近 $N^2$ 時，$X_m$ 就會很小。這樣一來，就不用每次都計算 $N^2 - P_m^2$，只需要每一位 $a_m$ 決定完，更新 $X_m$ 即可。


再定義 $X_m$ 的更新方式：
$$X_m = X_{m+1} - Y_m$$ $$\begin{aligned}Y_m &= P_{m}^2 - P_{m+1}^2 \\
&= (P_{m+1} + a_m)^2 - P_{m+1}^2 \\ &= P_{m+1}^2 + 2 \cdot P_{m+1} \cdot a_m + a_m^2- P_{m+1}^2 \\&=2P_{m+1}a_m+a_m^2 \end{aligned}$$

此處所定義的 $Y_m$ 代表 $X_m$ 所需更新的幅度。所有 $Y_i$ 的和正好會等於最終部分解 $P^2$。
這樣還不夠，為了完全免去在程式實作中的乘法操作，還需要定義兩個符號來巧妙的避開他們。
$$c_m = P_{m+1}2^{m+1}$$ $$d_m = 2^{2m}$$

這樣一來，若 $Y_m$ 中的 $a_m$ 為 $2^m$ （該位「放得下」），則定義為
$$Y_m = c_m +d_m$$ 否則為 $0$。 

經過這番巧妙的定義，$c_m$ 和 $d_m$ 的更新方式，變成了可以透過位移和加法操作完成的形式：
$$c_{m-1} = P_m2^m = (P_{m+1}+a_m)2^m=P_{m+1}2^m + a_m2^m=
\left\{
\begin{array}{l@{\quad}l}
\displaystyle c_m/2+d_m & \text{if } a_m=2^m\\[4pt]
\displaystyle c_m/2     & \text{if } a_m=0
\end{array}
\right.
$$ $$d_{m-1}=\frac{d_m}{4}$$

其中 $c_{-1}=P_02^0=P_0=N$，即為所求之開根號計算結果。

最後來看程式碼：
```c
uint64_t sqrti(uint64_t x)
{
    // m is d_n in the proof above
    // y is c_n
    uint64_t m, y = 0;
    if (x <= 1)
        return x;

    int total_bits = 64;

    /* clz64(x) returns the count of leading zeros in x.
     * (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
     * Rounding that index down to an even number ensures our starting m is a
     * power of 4.
     */
    int shift = (total_bits - 1 - clz64(x)) & ~1;
    m = 1ULL << shift;

    while (m) {
        // b is Y_m = c_m + d_m
        uint64_t b = y + m;
        y >>= 1;       // c_m = c_m/2 (do it early, use later)
        if (x >= b) {  // if X_(m+1) ≥ Y_m then a_m = 2^m
            x -= b;    // X_m = X_(m+1) - Y_m
            y += m;    // c_(m-1) = c_m/2 + d_m (for the case a_m = 2^m)
        }
        m >>= 2;
    }
    return y; // c_(-1) = sqrt(x)
}
```

### 擴充為 $\lceil \sqrt{x}) \rceil$ 函式
事實上，向上取整可以視作下方兩個條件：
* `x` 有小數部分，答案為整數部分 `+1`
* `x` 沒有小數部分，答案維持不變

在上方小節的證明中，提及了 $X_m$ 為餘數。若 $X$ 在做完開根號後為 0（整除），則代表傳入函式的數值是完全平方數，不需要做額外操作；反之，對 $c_{-1}$ `+1`（在先前程式中為變數 `y`）即為所求。

在先前的程式碼中加上兩行即可：

```c
uint64_t sqrti(uint64_t x)
{
    //... ignore()
    
    if(x > 0)
        y++;
        
    return y; // c_(-1) = ceil(sqrt(x))
}
```

## Week 2 Q3
### Hash Table 的結構
```c
struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};
```
其中 `hlist_node` 為何需要將 `pprev` 定義為 pointer of pointer 呢？他代表的又是什麼？
先觀察 `map_add()` （已經還原程式空缺處）：
```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;  /* CCCC: 把原先第一個節點的 pprev 指向 n->next */
    h->first = n;
    n->pprev = &h->first;         /* DDDD: 新節點 n 的 pprev 指向鏈表頭 */
}
```

這個 add 操作，會把新的 node 插入到該 hash bucket 的第一個位置。
其中 `first->pprev = &n->next;`，會將後方節點的 `pprev` 指向「上個節點指向自己的指標」（換句話說，他其實在指著自己的家？）
若當前節點是 hash bucket 中的第一個節點，指向自己的會是 `hlist_head*`；而若不是第一個節點，指向自己的則會是 `hlist_node*`。選擇不和普通的 doubly linked list 一樣維護一個 `*prev`，而是改用 `**pprev` 的話，就不需要創建一個「用不到、但和 `hlist_node` 一樣肥的 dummy head」，可以節省更多空間。

這樣做的好處是，當想要對特定節點進行刪除時，就不需要對當前節點的狀態進行額外判斷（是否是第一個節點等等），如果想要刪除，可以簡化成以下（假設要刪除的節點為 curr）：
```c
if (n->pprev) {
    *n->pprev = n->next;
}
if (n->next) {
    n->next->pprev = n->pprev;
}
```

（參考 [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)）

### two sum 使用 hash table 的實作
由於 hash table 在沒有 collision 的狀況下，可以達到 query 和 insert 操作時間複雜度 O(1) 的優異表現；可以利用其特性來完成 two sum 函式。
#### 步驟 - 走訪所有陣列中數值
* 若該數的 key 不存在於 hash table，代表尚未出現匹配的數字
    * 將 `target - num` 加入 hash table 中，供後續數值匹配
* 若該數 key 存在於 hash table，則 `return table[num]`

### Linux 核心中使用 hash table 的應用
#### fs/inode.c
在檔案系統中的 inode，是協助在 data block 檢索資料時使用的索引節點。
可以看到在 `inode.c` 中定義了這個：
```c
static struct hlist_head *inode_hashtable __ro_after_init;
```
其中 `__ro_after_init` 為 初始化後改為 read-only 之意。
可以看到，在 `ilookup` 中，該 hash table 被用來快速尋找 inode 位置：
```c
struct inode *ilookup(struct super_block *sb, unsigned long ino)
{
        //此行可以快速得到對應的 hash bucket
	struct hlist_head *head = inode_hashtable + hash(sb, ino);
	struct inode *inode;
again:
	inode = find_inode_fast(sb, head, ino, false);

	if (inode) {
		if (IS_ERR(inode))
			return NULL;
		wait_on_inode(inode);
		if (unlikely(inode_unhashed(inode))) {
			iput(inode);
			goto again;
		}
	}
	return inode;
}
```

可以看到是以 ino (inode number) 進行 hash 計算，其中 `head` 為 inode 所在的 bucket，因為可能存在多個 inode 在 bucket 中，所以還需要呼叫 `find_inode_fast()` 尋找正確的對應 inode。
程式碼的下半部則是針對修改檔案系統時的 lock 處理；一次只能有一個 writer，必須等待該 inode idle 的時候才可以對其進行修改。

#### net/phonet/socket.c
在 socket 套件中也能看見 hash table 的身影。不過本套件似乎有些冷門，根據 [The Linux Kernel](https://docs.kernel.org/networking/phonet.html) 官網描述，Phonet 這個封包協議是由 Nokia 的手機及相關設備在使用：
> Phonet is a packet protocol used by Nokia cellular modems for both IPC and RPC. With the Linux Phonet socket family, Linux host processes can receive and send messages from/to the modem, or any other external device attached to the modem.

在 socket.c 中，裡面定義了一個包含 hash table 的結構：
```c
static struct  {
	struct hlist_head hlist[PN_HASHSIZE]; //hash table
	struct mutex lock;
} pnsocks;
```

還有使用到 hash table 的函式：
```c
static struct hlist_head *pn_hash_list(u16 obj)
{
	return pnsocks.hlist + (obj & PN_HASHMASK);
}

struct sock *pn_find_sock_by_sa(struct net *net, const struct sockaddr_pn *spn)
{
	struct sock *sknode;
	struct sock *rval = NULL;
	u16 obj = pn_sockaddr_get_object(spn);
	u8 res = spn->spn_resource;
	struct hlist_head *hlist = pn_hash_list(obj);

	rcu_read_lock();
	sk_for_each_rcu(sknode, hlist) {
		struct pn_sock *pn = pn_sk(sknode);
		BUG_ON(!pn->sobject); /* unbound socket */

		if (!net_eq(sock_net(sknode), net))
			continue;
		if (pn_port(obj)) {
			/* Look up socket by port */
			if (pn_port(pn->sobject) != pn_port(obj))
				continue;
		} else {
			/* If port is zero, look up by resource */
			if (pn->resource != res)
				continue;
		}
		if (pn_addr(pn->sobject) &&
		    pn_addr(pn->sobject) != pn_addr(obj))
			continue;

		rval = sknode;
		sock_hold(sknode);
		break;
	}
	rcu_read_unlock();

	return rval;
}
```
本函式將用來尋找特定的 socket，會傳入一個 `obj` 來計算 hash。同樣的，因 hash table 存在 collision 問題，需要在找到 bucket 後逐一走訪，確認該節點是 target 時才回傳。
> 走訪時使用到了 RCU 機制，簡單來說是同時允許一個 writer、多個 reader 存取檔案的機制，需要再深入學習 [Linux 核心設計: RCU 同步機制](https://hackmd.io/@sysprog/linux-rcu#%E8%A8%82%E9%96%B1%E2%80%94%E7%99%BC%E5%B8%83%E6%A9%9F%E5%88%B6)
