# 2025q1 Homework2 (quiz1+2)
contributed by <`Andrushika`>
## Week 1 Q1
本題要實作 `list_insert_before` 這個函式：
如果只看函式說明，參數的用法還是有些難懂。所以往前找到了 `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` 的家
把 `*before` 從他家趕出來，讓新節點 `*item` 住進去
將`*item` 的下一位指向 `*before`
## 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)
Sign in with Wallet
Connect another wallet