---
tags: linux kernel, linux2022
---
# [rhashtable](https://elixir.bootlin.com/linux/latest/source/include/linux/rhashtable.h) 研究
contributed by < [linjohnss](https://github.com/linjohnss) >
> [GitHub: rcuhashbash](https://github.com/linjohnss/rcuhashbash)
## 目標
Linux 核心提供一套 Resizable, Scalable, Concurrent Hash Table，名為 `rhashtable` (見 [include/linux/rhashtable.h](https://elixir.bootlin.com/linux/latest/source/include/linux/rhashtable.h) 及 [lib/rhashtable.c](https://elixir.bootlin.com/linux/latest/source/lib/rhashtable.c))，描述於論文〈[Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming](https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf)〉。摘譯 LWN 文章，並佐以原論文，描述 rhashtable 何以落實高效的並行雜湊表，搭配撰寫 Linux 核心模組作為試驗
## [Relativistic hash tables, part 1: Algorithms](https://lwn.net/Articles/612021/)
### hash table 在 Linux 的應用場景
在 Linux 的 file system 中，利用 hash table 儲存 mount 的 root dentry ，因此 `lookup_mount` 可以利用 `hash_get` 取得 mount 的 root dentry
```c
/*
* find the first mount at @dentry on vfsmount @mnt.
* call under rcu_read_lock()
*/
struct mount *__lookup_mnt(struct vfsmount *mnt, struct dentry *dentry)
{
struct hlist_head *head = m_hash(mnt, dentry);
struct mount *p;
hlist_for_each_entry_rcu(p, head, mnt_hash)
if (&p->mnt_parent->mnt == mnt && p->mnt_mountpoint == dentry)
return p;
return NULL;
}
```
#### data compress
Linux 核心支援多種資料壓縮的方法，而 hash table 在其中扮演重要的角色。hash table 儲存 encode 過後的片段資料，在進行資料壓縮過程中，可以用快速的找出重複的資料
在 `linux/lib/842/842_compress.c` 中，利用 hash table 找尋是否有重複的 `index`
```c
#define find_index(p, b, n) ({ \
struct sw842_hlist_node##b *_n; \
p->index##b[n] = INDEX_NOT_FOUND; \
hash_for_each_possible(p->htable##b, _n, node, p->data##b[n]) { \
if (p->data##b[n] == _n->data) { \
p->index##b[n] = _n->index; \
break; \
} \
} \
p->index##b[n] >= 0; \
})
```
### rhashtable 解決的問題
hash table 雖然相較於 linked list 能更快速的搜索目標，但需要避免碰撞發生造成效能損失。為了應付此問題，除了改進 hash function，對於 hash table 的大小估計同樣重要，太小的會成性能損失；太大會造成空間的浪費。為 hash table 選擇正確的大小並不容易，在 Linux 核心中有許多 hash table 其大小是在系統初始化時進行簡單的估計。然而，儘管猜測是完美的，工作負載也會隨時間而變化。此時，一個 resizable 的 hash table 即可解決此問題。
但是若要同時達到 concurrent 與 resizable，不對 hash table 進行 blocking 是很難達成的。在 2010 年，Josh Triplett、Paul McKenney 和 Jonathan Walpole 在 USENIX ATC 發表一篇名為〈[Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming](https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf)〉 的論文，描述了該問題解決方案。
### rhashtable 在 Linux 核心的應用場景
在 Linux 核心的網路模組中，RDS 使用 rhashtable 儲存 ip 地址與 port
`linux/net/rds/bind.c`
```c
static inline void __rds_create_bind_key(u8 *key, const struct in6_addr *addr,
__be16 port, __u32 scope_id)
{
memcpy(key, addr, sizeof(*addr));
key += sizeof(*addr);
memcpy(key, &port, sizeof(port));
key += sizeof(port);
memcpy(key, &scope_id, sizeof(scope_id));
}
```
### 論文〈Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming〉
Relativistic hash table 與普通 hash table 類似，同樣都是由包含 link list 的 bucket 組成。
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">Bucket</TD></TR>
<TR><TD PORT="c">Bucket</TD></TR>
<TR><TD PORT="d">...</TD></TR>
</TABLE>>];
{
subgraph cluster_treenode{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=green];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=green];
ge[shape=none, label="..."];
gr->g1->g2->g3->ge;
br[label="", style=filled,fillcolor=blue];
b1[label="", style=filled,fillcolor=blue];
b2[label="", style=filled,fillcolor=blue];
b3[label="", style=filled,fillcolor=blue];
be[shape=none, label="..."];
br->b1->b2->b3->be;
}
}
table->a:a
a:c:e->br;
a:b:e->gr;
}
```
#### Table shrinking
若發現目前的 hash table 的空間太大，希望能縮小 hash table
1. Initial state:
將初始狀態分為 odd 與 even 兩種 bucket，odd 為奇數 reader 可以存取，even 為偶數 reader 可以存取。
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">Bucket</TD></TR>
<TR><TD PORT="c">Bucket</TD></TR>
<TR><TD PORT="d">...</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=green];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=green];
ge[shape=none, label="..."];
gr->g1->g2->g3->ge;
br[label="", style=filled,fillcolor=blue];
b1[label="", style=filled,fillcolor=blue];
b2[label="", style=filled,fillcolor=blue];
b3[label="", style=filled,fillcolor=blue];
be[shape=none, label="..."];
br->b1->b2->b3->be;
}
}
table->a:a
a:c:e->br;
a:b:e->gr;
}
```
2. Initialize new buckets:
分配一個新的 shrinking hash table，連接到對應的舊 node(指向具有匹配 index 的第一項)，並將其儲存在 writer 的 local memory 中，其它 reader 無法存取
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
// new_table [shape=none, label="new table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
<TR><TD PORT="d">...</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=green];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=green];
ge[shape=none, label="..."];
gr->g1->g2->g3->ge;
br[label="", style=filled,fillcolor=blue];
b1[label="", style=filled,fillcolor=blue];
b2[label="", style=filled,fillcolor=blue];
b3[label="", style=filled,fillcolor=blue];
be[shape=none, label="..."];
br->b1->b2->b3->be;
}
}
table->a:a;
// new_table->b:a;
b:b:e->gr:n;
a:c:e->br;
a:b:e->gr;
}
```
3. Link old chains:
將奇數 bucket 的 tail 接到偶數 bucket，因此在 reader 存取奇數 bucket 時，也會存取到偶數的部份。查找的結果仍然會是正確的，但這會導致需要走訪更長的時間
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
// new_table [shape=none, label="new table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
<TR><TD PORT="d">...</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=green];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=green];
// ge[shape=none, label="..."];
gr->g1->g2->g3;
br[label="", style=filled,fillcolor=blue];
b1[label="", style=filled,fillcolor=blue];
b2[label="", style=filled,fillcolor=blue];
b3[label="", style=filled,fillcolor=blue];
be[shape=none, label="..."];
br->b1->b2->b3->be;
}
subgraph node_same{
rank="same";
edge[style="invisible",dir="none"];
gr->br;
}
}
table->a:a;
b:b:e->gr:n;
a:c:e->br;
a:b:e->gr;
g3->br:s
}
```
:::warning
此演算法放寬每個 bucket 內的 link list 必須為同一個 index 的限制，使 link list 可以臨時包含不同 index 的 node，確保在 resizing 時不會找不到 node，並且可以避免複製 link list，論文稱其為 "hash chains imprecise"
:::
4. Publish new buckets:
將 table 指標指向新的 hash table，此時後續的 reader 將會從新的 table 進行操作
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
<TR><TD PORT="d">...</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=green];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=green];
gr->g1->g2->g3;
br[label="", style=filled,fillcolor=blue];
b1[label="", style=filled,fillcolor=blue];
b2[label="", style=filled,fillcolor=blue];
b3[label="", style=filled,fillcolor=blue];
be[shape=none, label="..."];
br->b1->b2->b3->be;
}
}
table->b:a;
b:b:e->gr;
a:c:e->br;
a:b:e->gr;
g3->br;
}
```
5. Wait for readers:
此時，仍可能有 reader 正在走訪舊的 bucket，所以必須等待一個 [RCU](https://hackmd.io/@sysprog/linux-rcu?type=view) 的寬限期過去
若新的 hash table 有兩個以上的 bucket，則需像 expansion 一樣 unzip
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
<TR><TD PORT="d">...</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=green];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=green];
gr->g1->g2->g3;
br[label="", style=filled,fillcolor=blue];
b1[label="", style=filled,fillcolor=blue];
b2[label="", style=filled,fillcolor=blue];
b3[label="", style=filled,fillcolor=blue];
be[shape=none, label="..."];
br->b1->b2->b3->be;
}
}
table->b:a;
b:b:e->gr;
a:c:e->br[style=dashed];
a:b:e->gr[style=dashed];
g3->br;
}
```
6. Reclaim:
釋放舊的 hash table，完成 hash table shrinking
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=green];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=green];
gr->g1->g2->g3;
br[label="", style=filled,fillcolor=blue];
b1[label="", style=filled,fillcolor=blue];
b2[label="", style=filled,fillcolor=blue];
b3[label="", style=filled,fillcolor=blue];
be[shape=none, label="..."];
br->b1->b2->b3->be;
}
}
table->b:a;
b:b:e->gr;
g3->br;
}
```
:::warning
為簡單起見，rhashtable 透過整數因子限制 resizing 改變桶的數量。例如，將 bucket 的數量加倍或減半。這保證了兩個約束：
1. 當收縮 table 時，新 table 的每個 bucket 將包含多個來自舊 table 的bucket
2. 當擴張 table 時，新 table 的每個 bucket 將包含最多一個來自舊 table 的 bucket
:::
#### Table expansion
隨著 hash table 中的 node 數量增加，每個 bucket 的平均深度會增加，造成查找效率降低，因此需要擴張大小
1. Initial state:
假設初始狀態為只有一個 bucket 的 hash table
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=blue];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=blue];
ge[shape=none, label="..."];
gr->g1->g2->g3->ge;
}
}
table->b:a;
b:b:e->gr;
}
```
2. Initialize new buckets:
分配一個新的包含兩個 bucket 的 expansion hash table，連接到對應的舊 node(指向具有匹配 index 的第一項)，並將其儲存在 writer 的 local memory 中，其它 reader 無法存取
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=blue];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=blue];
ge[shape=none, label="..."];
gr->g1->g2->g3->ge;
}
}
table->b:a;
b:b:e->gr;
a:c:e->g1:s[style=dashed];
a:b:e->gr[style=dashed];
}
```
3. Publish new buckets:
將 table 指標指向新的 hash table，此時後續的 reader 將會從新的 table 進行操作，舊有的 hash table 可能有 reader 正在存取，還不可以釋放
:::warning
注意，此時新的兩個 bucket 只有連接的第一個 node 為正確的，但由於舊的 link list 仍將 node 接在一起，所以此時新的 hash table 查找成果仍為正確，只是需要花費較多走訪時間
:::
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=blue];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=blue];
ge[shape=none, label="..."];
gr->g1->g2->g3->ge;
}
}
table->a:a;
b:b:e->gr;
a:c:e->g1:s[color=red];
a:b:e->gr[color=red];
}
```
4. Wait for readers:
需要等待一個 RCU 寬限期過去，才能開始舊的 hash table 進行 unzip
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=blue];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=blue];
ge[shape=none, label="..."];
gr->g1->g2->g3->ge;
}
}
table->a:a;
b:b:e->gr:n[style=dashed];
a:c:e->g1:s[color=red];
a:b:e->gr[color=red];
}
```
5. Unzip one step:
進行 unzip 的過程使利用存取舊的 hash table 來工作，其演算法如下：
1.) 確定 link list 中的第一個 node 屬於新 hash table 的哪個 bucket
2.) 持續走訪 link list，直到遇到不屬於同一個 bucket 的 node
3.) 此時，舊的 bucket 將會指向該 node，成果如下：
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
{
rank = same
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
}
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=blue];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=blue];
ge[shape=none, label="..."];
gr->g1->g2->g3->ge;
// gr:n->g2:n[color=red]
}
}
table->a:a;
b:b:e->g1:n[style=dashed];
a:c:e->g1:s[color=red];
a:b:e->gr[color=red];
}
```
   4.) 更改前一項中的 next 指標，指向下一個匹配的 node：
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
{
rank = same
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
}
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=blue];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=blue];
ge[shape=none, label="..."];
gr->g1[style="invisible",dir="none"];
g1->g2->g3->ge;
gr:n->g2:n[color=red]
}
}
table->a:a;
b:b:e->g1:n[style=dashed];
a:c:e->g1:s[color=red];
a:b:e->gr[color=red];
}
```
:::warning
在另一個 RCU 寬限期過去之前，不能對此 list 進行任何更改，否則在 list 中的 reader 可能最終會出現在錯誤的位置。
> 假設尋找綠色 node 的 reader 可能正在查看從列表中修補出來的藍色 node，但是，由於該 node 的 next 指標保持不變，因此 reader 不會 derailed。而尋找藍色 node 的 reader 從一開始就不會看到更改的 node，因此它們也是安全的。
該演算法通過更改不尋找將 "unzip" 的 node 的 reader 的可見指標來工作。只要每個 RCU 寬限期只更改列表中的一個指標，這個屬性就成立，並且當 reader 通過它時，list 可以安全地 unzip。
:::
6. Wait for readers:
修改完成後，在一次等待一個 RCU 寬限期
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
{
rank = same
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
}
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=blue];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=blue];
ge[shape=none, label="..."];
gr->g1[style="invisible",dir="none"];
g1->g2->g3->ge;
gr:n->g2:n[color=red]
}
}
table->a:a;
b:b:e->g1:n[style=dashed];
a:c:e->g1:s[color=red];
a:b:e->gr[color=red];
}
```
7. Unzip again:
重複步驟 5，此時舊 hash table 的 bucket 指向 even node
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
{
rank = same
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVNE</TD></TR>
</TABLE>>];
b[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ALL</TD></TR>
</TABLE>>];
}
{
subgraph link_list{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=blue];
g2[label="", style=filled,fillcolor=green];
g3[label="", style=filled,fillcolor=blue];
ge[shape=none, label="..."];
gr->g1[style="invisible",dir="none"];
g1->g2[style="invisible",dir="none"];
g2->g3->ge;
gr:n->g2:n[color=red]
g1:s->g3:s[color=red]
}
}
table->a:a;
b:b:e->g2:n[style=dashed];
a:c:e->g1:s[color=red];
a:b:e->gr[color=red];
}
```
8. Final state:
重複等待 reader 與 unzip，直到處理到每個 bucket 的尾端。此時每個 node 僅出現在其相段應的 bucket 中，即可釋放舊的 hash table，完成 hash table expansion
```graphviz
digraph g{
rankdir=LR;
node [shape=record,width=01,height=.1];
table [shape=none, label="table"]
a[shape=plaintext,label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR><TD PORT="a" BGCOLOR="gray">Hash Table</TD></TR>
<TR><TD PORT="b">ODD</TD></TR>
<TR><TD PORT="c">EVEN</TD></TR>
</TABLE>>];
{
subgraph cluster_treenode{
penwidth=0;
node[shape=oval,width=.5,height=.3];
gr[label="", style=filled,fillcolor=green];
g1[label="", style=filled,fillcolor=green];
ge[shape=none, label="..."];
gr->g1->ge;
br[label="", style=filled,fillcolor=blue];
b1[label="", style=filled,fillcolor=blue];
be[shape=none, label="..."];
br->b1->be;
}
}
table->a:a
a:c:e->br;
a:b:e->gr;
}
```
:::info
如果 hash table 很長，則此過程可能需要相當長的時間。但是調整大小操作應該比較少，而 reader 存取 table 的頻率很高。所以，對於一個存取量足夠大的 table，額外的努力最終是值得的，在經常有 reader 存取的路徑中將得到了很多倍的回報。
:::
#### Handling Insertion and Removal
現階段我們可以利用以 RCU 為基礎的 hash table 使插入、刪除與查找並行執行。而引入額外的 resizing 操作，也同樣需要做到與其他操作同步。
原先若要進行 resize 操作，需阻止 table 的更新直到 resize 完成。但是，我們可以處理在 resizing 產生的中間狀態，從而提前運行並行更新 table，這可以避免 concurrent 時的過度延遲。
> In the simplest case, concurrent updates can continue to block until the resize completes;however, concurrent updates can potentially run earlier if they carefully handle the intermediate states produced by the resizer. For a sufficiently large hash table, this may prove necessary to avoid excessive delays on concurrent updates.
關於在 resizing 同時插入與刪除主要可以分為兩種情形：
1. Table shrinking
收縮演算法可以選擇在完成初始化後立即為 updaters 發布已初始化的 table，從而允許在進行 cross-linking 的同時進行並行更新（*Table shrinking step 3*）。收縮演算法也會在它完成與該 bucket 的 cross-linking 後立即刪除該 bucket 的每個鎖，從而允許對該 bucket 的並行插入和刪除。
2. Table expansion
在擴展演算法中，需要比收縮演算法更小心處理，對 zipped link list 進行單個 unzip 操作時，必須獲取該 bucket 的鎖。在執行插入時，只須在沒有被 lock 的 bucket 開頭插入，就不會影響 resizing。但在執行刪除時，可能會發生在 list 中的任何節點，包括標記下一個 unzip 目標的指標位置（舊 table 的 bucket pointer，論文稱 "aux pointer"），所以需要檢查與 aux pointer 的衝突，如果發生衝突，刪除節點後需要更新 aux pointer。鑑於與查找和插入相比，刪除的頻率相對較低，調整大小的頻率甚至更低，因此在刪除演算法中要求這種額外的檢查是可以接受的。
:::info
論文中有更多的實做細節，包含針對記憶體分配的 "Resizing in Place" 與優化 hash 分配的 "Keeping Buckets Sorted" 本節就暫不描述
:::
#### [rcuhashbash-resize](https://git.kernel.org/pub/scm/linux/kernel/git/josh/rcuhashbash.git)
rcuhashbash-resize 為論文創建一個為了可調整大小的 hash table 的測試工具和基準測試框架。首先創建一個具有指定 bucket 數量的 hash table，並向其中添加包含從 0 到指定上限的整數值的元素。然後它啟動 reader 執行緒和調整大小執行緒，這些執行緒記錄 thread-local 統計資料，以避免需要額外的同步。當測試完成時，rcuhashbash-resize 停止所有執行緒，匯總它們記錄的統計數據，並通過 kernel message buffer 顯示結果。
## [Relativistic hash tables, part 2: Implementation](https://lwn.net/Articles/612100/)
rhashtable 的實現在 Linux 核心 3.17 版開始加入，這使得 hashtable 可以調整大小，並同時允需 reader 與 writer 同時存取。此篇將描述在 3.17 版中所看到的 "rhashtable" 的 kernel API。
rhashtable 最初是為了在網路子系統中使用而被創建的，但當時的開發者 Thomas Graf 明白 rhashtable 將會獲得更廣泛的使用。因此，他們設計一系列的前置參數，來擴張 rhashtable 的 API 的使用可能，只要完成設置，後續對 table 的操作就會相對簡單了。
### rhashtable structure
首先，我們可以看到 `rhashtable` 的結構包含 `rhashtable_params`，因此需要先定義參數結構
```c
/**
* struct rhashtable - Hash table handle
* @tbl: Bucket table
* @nelems: Number of elements in table
* @shift: Current size (1 << shift)
* @p: Configuration parameters
*/
struct rhashtable {
struct bucket_table __rcu *tbl;
size_t nelems;
size_t shift;
struct rhashtable_params p;
};
```
以下為 `rhashtable_params` 的定義：
- `nelem_hint` 是對錶中將存儲多少元素的猜測（它用於計算初始的 table 大小）。
- `key_len` 和 `key_offset` 描述了 key 的字節大小和它在結構中的 offset（應該用 offsetof() 獲得）。
- `head_offset` 是 hashed object 中 rhash_head 結構的 offset。
- `hash_rnd` 是 hash function 中使用的隨機種子；如果為零，則 rhashtable 將生成一個隨機種子。
- `max_shift` 是用於設置 table 的最大大小；它的值是 table 大小以 2 為底的對數。
- `hashfn` 是執行的 hash function；通常它可以設置為 `arch_fast_hash()`，在`<linux/hash.h>` 中有定義。
- `obj_hashfn` 是 hash 整個 hash object 的函式。如果已提供 `key_len` 和 `key_offset`，則不需要 `obj_hashfn`。如果計算 hash 需要比查看 object 更為複雜，則可以提供這個函式來完成這項工作（並且 `key_len` 應該設置為零）。
- `grow_decision` 和 `shrink_decision` 提供自動調整 table 大小的函式。如果這些函式返回真值，則表的大小將適當的加倍或減半。另外，`rhashtable` 提供了兩個可用的函式：
`rht_grow_above_75()` 和 `rht_shrink_below_30()`。這些函式會力求保持 table 30% 到 75% 的滿度。
- `mutex_is_held` 如果當前持有 protecting mutex，則返回 true。用於除錯和追蹤，確保在呼叫修改 table 的函式時保持鎖定。
```c
/**
* struct rhashtable_params - Hash table construction parameters
* @nelem_hint: Hint on number of elements, should be 75% of desired size
* @key_len: Length of key
* @key_offset: Offset of key in struct to be hashed
* @head_offset: Offset of rhash_head in struct to be hashed
* @hash_rnd: Seed to use while hashing
* @max_shift: Maximum number of shifts while expanding
* @hashfn: Function to hash key
* @obj_hashfn: Function to hash object
* @grow_decision: If defined, may return true if table should expand
* @shrink_decision: If defined, may return true if table should shrink
* @mutex_is_held: Must return true if protecting mutex is held
*/
struct rhashtable_params {
size_t nelem_hint;
size_t key_len;
size_t key_offset;
size_t head_offset;
u32 hash_rnd;
size_t max_shift;
rht_hashfn_t hashfn;
rht_obj_hashfn_t obj_hashfn;
bool (*grow_decision)(const struct rhashtable *ht,
size_t new_size);
bool (*shrink_decision)(const struct rhashtable *ht,
size_t new_size);
int (*mutex_is_held)(void);
};
```
後續就可以使用 `rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)` 來分配一個 `rhashtable`，另外也有，`rhashtable_destroy(const struct rhashtable *ht)` 來釋放 rhashtable
### rhashtable operations
#### Insertion and Removal
concurrent inserts 與 removes 必須進行 blocking，直到收縮演算法完成發布新 hash table 並等待 reader 結束存取舊 table
```c
void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node, gfp_t);
bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node, gfp_t);
void rhashtable_remove_pprev(struct rhashtable *ht, struct rhash_head *obj,
struct rhash_head __rcu **pprev, gfp_t flags);
```
#### Expand and Shrink
```c
int rhashtable_expand(struct rhashtable *ht, gfp_t gfp_flags);
int rhashtable_shrink(struct rhashtable *ht, gfp_t gfp_flags);
```
#### Lookup
```c
void *rhashtable_lookup(const struct rhashtable *ht, const void *key);
void *rhashtable_lookup_compare(const struct rhashtable *ht, u32 hash,
bool (*compare)(void *, void *), void *arg);
```
:::warning
文章提到，後需提交的 patch 將會把調整大小的操作移到單獨的執行序中，所以將不再需要在上述函式中分配記憶體空間。因此，`gfp_flags` 參數將被刪除。而我們也可以看到在 [6eba82](https://github.com/torvalds/linux/commit/6eba82248ef47fd478f940a418429e3ec95cb3db) 已刪除此參數
:::
#### [Per bucket locks & deferred expansion/shrinking](https://github.com/torvalds/linux/commit/97defe1ecf868b8127f8e62395499d6a06e4c4b1)
原先沒有像論文描述的對每個 bucket 用 lock 保護 ，加入對每個 bucket 的 spinlock，可以增加並行效率。並且將 expansion 與 shrinking 加到允許從 atomic context 插入和刪除的 warker queue，達到延遲 resizing 使插入和刪除可能與它並行發生，僅在 bucket unzip 或被 link 才短暫暫停
```diff
struct bucket_table {
size_t size;
+ unsigned int locks_mask;
+ spinlock_t *locks;
struct rhash_head __rcu *buckets[];
};
```
## 撰寫 Linux 核心模組作為試驗
我在 Linux 核心發現從 v4 開始有一個用於測試 `rhashtable` 的 module [test_rhashtable.c](https://elixir.bootlin.com/linux/v5.13/source/lib/test_rhashtable.c)
我嘗試將 rhashtable.c 複製下來，並將其掛載到核心
### 實驗環境
首先，確認 Linux 核心版本為 5.13
```shell
$ uname -r
5.13.0-51-generic
```
### 建構核心模組
從 test_rhashtable.c 的程式碼來看，他是使用 `__init` and `__exit` macros 去實做。因此我參考 [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux2021-summer/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Flinux-kernel-module#%E7%A8%8B%E5%BC%8F%E7%A2%BC%E6%BA%96%E5%82%99) 中掛載 hello 的方式
`Makefile`
```shell
obj-m := test_rhashtable.o
clean:
rm -rf *.o *.ko *.mod.* *.symvers *.order *.mod.cmd *.mod
```
### 編譯核心模組
```shell
$ make -C /lib/modules/`uname -r`/build M=`pwd` modules
```
### 掛載核心模組
產生 test_rhashtable.ko 之後，可將其掛載:
```shell
$ sudo insmod test_rhashtable.ko
```
dmesg 命令可顯示核心訊息
```c
[54613.602222] Running rhashtable test nelem=8, max_size=0, shrinking=0
[54613.602227] Test 00:
[54613.602278] Adding 50000 keys
[54613.628007] Info: encountered resize
[54613.629866] Traversal complete: counted=57342, nelems=50000, entries=50000, table-jumps=1
[54613.629869] Test failed: Total count mismatch ^^^
[54613.634864] Traversal complete: counted=50000, nelems=50000, entries=50000, table-jumps=0
[54613.634867] Deleting 50000 keys
[54613.642286] Duration of test: 40009203 ns
[54613.642293] Test 01:
[54613.642341] Adding 50000 keys
[54613.652447] Info: encountered resize
[54613.653142] Traversal complete: counted=50000, nelems=50000, entries=50000, table-jumps=1
[54613.661613] Info: encountered resize
[54613.663122] Traversal complete: counted=59447, nelems=50000, entries=50000, table-jumps=1
[54613.663125] Test failed: Total count mismatch ^^^
[54613.663126] Deleting 50000 keys
[54613.669292] Duration of test: 26952688 ns
[54613.669302] Test 02:
[54613.669342] Adding 50000 keys
[54613.680276] Traversal complete: counted=50000, nelems=50000, entries=50000, table-jumps=0
[54613.685170] Traversal complete: counted=50000, nelems=50000, entries=50000, table-jumps=0
[54613.685172] Deleting 50000 keys
[54613.692572] Duration of test: 23231530 ns
[54613.692580] Test 03:
[54613.692631] Adding 50000 keys
[54613.703299] Info: encountered resize
[54613.703959] Traversal complete: counted=50000, nelems=50000, entries=50000, table-jumps=1
[54613.711343] Info: encountered resize
[54613.712014] Traversal complete: counted=50000, nelems=50000, entries=50000, table-jumps=1
[54613.712017] Deleting 50000 keys
[54613.720477] Duration of test: 27847456 ns
[54613.722645] test if its possible to exceed max_size 8192: no, ok
[54613.722698] Average test time: 29510219
[54613.722699] test inserting duplicates
[54613.722707]
---- ht: ----
bucket[1] -> [[ val 21 (tid=1) ]] -> [[ val 1 (tid=0) ]]
-------------
[54613.722713]
---- ht: ----
bucket[1] -> [[ val 21 (tid=1) ]] -> [[ val 1 (tid=2), val 1 (tid=0) ]]
-------------
[54613.722717]
---- ht: ----
bucket[1] -> [[ val 21 (tid=1) ]] -> [[ val 1 (tid=0) ]]
-------------
[54613.722720]
---- ht: ----
bucket[1] -> [[ val 21 (tid=1) ]] -> [[ val 1 (tid=2), val 1 (tid=0) ]]
-------------
[54613.722722] Testing concurrent rhashtable access from 10 threads
[54614.010355] test 3125 add/delete pairs into rhlist
[54614.039495] test 3125 random rhlist add/delete operations
[54614.061349] Started 10 threads, 0 failed, rhltable test returns 0
```
### 程式碼運作原理
`test_rhashtable.c` 的目的是測量操作的時間與正確性，主要分為三個部份：
1. 插入、走訪與刪除測試以及 table 的最大大小測試
2. 測試插入會 map 到同一個 bucket 的不同值
3. 在多線程同時存取 table
而 resizing 的部份會在 `rhashtable_init` 時利用 `rht_deferred_worker` 使 table 在測試時自動調整大小，其作法是用 `rht_grow_above_75()` 與 `rht_shrink_below_30()` 判斷要擴張還是縮小
```c
static void rht_deferred_worker(struct work_struct *work)
{
struct rhashtable *ht;
struct bucket_table *tbl;
int err = 0;
ht = container_of(work, struct rhashtable, run_work);
mutex_lock(&ht->mutex);
tbl = rht_dereference(ht->tbl, ht);
tbl = rhashtable_last_table(ht, tbl);
if (rht_grow_above_75(ht, tbl))
err = rhashtable_rehash_alloc(ht, tbl, tbl->size * 2);
else if (ht->p.automatic_shrinking && rht_shrink_below_30(ht, tbl))
err = rhashtable_shrink(ht);
else if (tbl->nest)
err = rhashtable_rehash_alloc(ht, tbl, tbl->size);
if (!err || err == -EEXIST) {
int nerr;
nerr = rhashtable_rehash_table(ht);
err = err ?: nerr;
}
mutex_unlock(&ht->mutex);
if (err)
schedule_work(&ht->run_work);
}
```
### v5.13 與 v3.17 比較
> `rhashtable.h` 自 v3.17 到 v5.13，已從 200 多行增加至 1200 多行程式碼，有眾多的 API 擴增與改進，以下針對幾項 `test_rhashtable.c` 有使用到的進行說明。
#### rhashtable-types.h
由於 `rhashtable.h` 自 2014 年實現在 Linux 核心以後被大量使用，因此微小的更改可能需要大量的重新編譯。所以 [0eb71a](https://github.com/torvalds/linux/commit/0eb71a9da5796851fa87ddc1a534066c0fe54055) 將 [`rhashtable-types.h`](https://elixir.bootlin.com/linux/v5.13/source/include/linux/rhashtable-types.h) 拆分出來，內容只包含主要的型態宣告，後續只須引入 `rhashtable-types.h` 即可，進而減少大型的重新編譯。
#### rhashtable_params
v5.13 的 rhashtable 參數相較 v3.17 的更加簡單易用，多了可以自動對 table 進行收縮的參數 `automatic_shrinking`
```c
/**
* struct rhashtable_params - Hash table construction parameters
* @nelem_hint: Hint on number of elements, should be 75% of desired size
* @key_len: Length of key
* @key_offset: Offset of key in struct to be hashed
* @head_offset: Offset of rhash_head in struct to be hashed
* @max_size: Maximum size while expanding
* @min_size: Minimum size while shrinking
* @automatic_shrinking: Enable automatic shrinking of tables
* @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
* @obj_hashfn: Function to hash object
* @obj_cmpfn: Function to compare key with object
*/
struct rhashtable_params {
u16 nelem_hint;
u16 key_len;
u16 key_offset;
u16 head_offset;
unsigned int max_size;
u16 min_size;
bool automatic_shrinking;
rht_hashfn_t hashfn;
rht_obj_hashfn_t obj_hashfn;
rht_obj_cmpfn_t obj_cmpfn;
};
```
#### rhashtable_lookup_fast
原先的 Lookup，需要有 RCU 確保並行的正確性，但是若有其他機制保證目標的存在，則可以使用 `rhashtable_lookup_fast` 加快運行時間
```c
/**
* rhashtable_lookup_fast - search hash table, without RCU read lock
* @ht: hash table
* @key: the pointer to the key
* @params: hash table parameters
*
* Computes the hash value for the key and traverses the bucket chain looking
* for a entry with an identical key. The first matching entry is returned.
*
* Only use this function when you have other mechanisms guaranteeing
* that the object won't go away after the RCU read lock is released.
*
* Returns the first entry on which the compare function returned true.
*/
static inline void *rhashtable_lookup_fast(
struct rhashtable *ht, const void *key,
const struct rhashtable_params params)
{
void *obj;
rcu_read_lock();
obj = rhashtable_lookup(ht, key, params);
rcu_read_unlock();
return obj;
}
```
## 執行論文提供的 [rcuhashbash-resize](https://git.kernel.org/pub/scm/linux/kernel/git/josh/rcuhashbash.git)
### 下載程式碼
```shell
git clone git://git.kernel.org/pub/scm/linux/kernel/git/josh/rcuhashbash.git
```
### 編譯核心模組
程式碼提供 `rcuhashbash.c` 與 `rcuhashbash-resize.c`，這裡主要先測試 `rcuhashbash-resize.c`
```shell
make modules
```
編譯後會出現很錯誤，接下來就是一個一個 debug
1. 出現 cpu_clock 錯誤
```c
error: implicit declaration of function ‘cpu_clock’ [-Werror=implicit-function-declaration]
```
從 linux kernel 程式碼中找到 `cpu_clock()` 是定義在 `linux/sched/clock.h`，因此引入該函式庫
```c
#include <linux/sched/clock.h>
```
2. hlist_for_each_entry_rcu、hlist_for_each_entry
程式碼中的 hlist_for_each_entry_rcu 用法怪怪的，原先 [v2.6.37](https://elixir.bootlin.com/linux/v2.6.37/source/include/linux/rculist.h#L449) 的定義為 `hlist_for_each_entry_rcu(tpos, pos, head, member)`，而根據 [v5.13](https://elixir.bootlin.com/linux/v5.13/source/include/linux/rculist.h#L705) 的 `rculist.h` 已改為 `hlist_for_each_entry_srcu(pos, head, member, cond)`，故將程式碼根據新的定義進行修改
```diff
- hlist_for_each_entry_rcu(entry, node, &t->buckets[value & t->mask], node)
+ hlist_for_each_entry_rcu(entry, &t->buckets[value & t->mask], node)
- hlist_for_each_entry(entry, node, &table->buckets[i & table->mask], node)
+ hlist_for_each_entry(entry, &table->buckets[i & table->mask], node)
```
### 掛載核心模組
產生 rcuhashbash.ko 之後，可將其掛載:
```shell
$ sudo insmod rcuhashbash.ko
```
dmesg 命令可顯示核心訊息
```c
[ 六 27 03:52] rcuhashbash starting threads
[ +6.727131] rcuhashbash summary: test=rcu readers=8 resize=true
rcuhashbash summary: entries=65536 shift1=13 (8192 buckets) shift2=14 (16384 buckets)
rcuhashbash summary: reads: 582710953 primary hits, 0 slowpath primary hits, 0 secondary hits, 0 misses
rcuhashbash summary: resizes: 13
rcuhashbash summary: PASS
[ +0.000016] rcuhashbash done
```
編譯成功後執行，若將 resize 開啟仍出現問題
```c
[ 六 27 02:00] rcuhashbash starting threads
[ +0.006406] BUG: kernel NULL pointer dereference, address: 0000000000000008
[ +0.000017] #PF: supervisor write access in kernel mode
[ +0.000008] #PF: error_code(0x0002) - not-present page
```
發現是 resize 在 grow 時誤用了 `node`，應該改為 `entry->node`，就沒問題了
```diff=184
- temp_table->buckets[i].first = node;
- node->pprev = &temp_table->buckets[i].first;
+ temp_table->buckets[i].first = &entry->node;
+ entry->node.pprev = &temp_table->buckets[i].first;
```
```diff=208
- old_table->buckets[i].first = node;
- if (!node)
+ old_table->buckets[i].first = &entry->node;
+ if (!&entry->node)
```
```diff=215
- entry_prev->node.next = node;
- if (node)
- node->pprev = &entry_prev->node.next;
+ entry_prev->node.next = &entry->node;
+ if (&entry->node)
+ entry->node.pprev = &entry_prev->node.next;
```
### 量測時間
利用 `ktime_get_ns()` 紀錄分配 `kthread_run()` 與 `kthread_stop()` 的時間，計算 `end - start` 即為執行時間，並將其寫入 `rcuhashbash_print_stats` 作輸出
```diff
[ 六 27 04:04] rcuhashbash starting threads
[ +6.052081] rcuhashbash summary: test=rcu readers=8 resize=true
rcuhashbash summary: entries=65536 shift1=13 (8192 buckets) shift2=14 (16384 buckets)
rcuhashbash summary: reads: 552065527 primary hits, 0 slowpath primary hits, 0 secondary hits, 0 misses
rcuhashbash summary: resizes: 17
rcuhashbash summary: PASS
+ rcuhashbash summary: totak time: 6005639149 ns
[ +0.000027] rcuhashbash done
```
### 程式碼運作原理
論文提供的測試平台主要是想測試 rhashtable 在發生 resizing 時，多個 reader read hit 的次數，用於比較 scalability。
Module 的參數包含：
- `test`：測試的演算法（rcu, ddds, rwlock）
- `readers`：reader 線程的數量
- `resize`：是否開啟 resizing
- `shift1`：原始 table 大小
- `shift2`：調整的 table 大小
- `entries`：table 內條目的數量
```c
module_param(test, charp, 0444);
MODULE_PARM_DESC(test, "Hash table implementation");
module_param(readers, int, 0444);
MODULE_PARM_DESC(readers, "Number of reader threads (default: number of online CPUs)");
module_param(resize, bool, 0444);
MODULE_PARM_DESC(resize, "Whether to run a resize thread (default: true)");
module_param(shift1, byte, 0444);
MODULE_PARM_DESC(shift1, "Initial number of hash buckets, log 2");
module_param(shift2, byte, 0444);
MODULE_PARM_DESC(shift2, "Number of hash buckets after resize, log 2");
module_param(entries, ulong, 0444);
MODULE_PARM_DESC(entries, "Number of hash table entries");
```
`rcuhashbash_table` 的結構包含用於計算 index 的 `mask` 與由 `hlist_head` 組成的 `buckets` 陣列。而 `stats` 結構為每個 reader 執行緒需要紀錄的統計變數
```c
struct rcuhashbash_table {
unsigned long mask;
struct hlist_head buckets[];
};
struct stats {
u64 read_hits; /* Primary table hits */
u64 read_hits_fallback; /* Fallback (secondary table) hits */
u64 read_hits_slowpath; /* Slowpath primary table hits (if applicable) */
u64 read_misses;
u64 resizes;
};
```
接著，程式會根據設定的參數先建立好 hashtable，並利用 `hlist_add_head` 插入 `entries` 個條目，然後分配 reader thread 與 resize thread 分別執行 `rcuhashbash_read_thread` 與 `rcuhashbash_resize_thread`
```c
static int __init rcuhashbash_init(void)
{
int ret;
unsigned long i;
for (i = 0; i < ARRAY_SIZE(all_ops); i++)
if (strcmp(test, all_ops[i].test) == 0) {
ops = &all_ops[i];
}
if (!ops) {
printk(KERN_ALERT "rcuhashbash: No implementation with test=%s\n",
test);
return -EINVAL;
}
if (readers < 0)
readers = num_online_cpus();
if (!ops->read) {
printk(KERN_ALERT "rcuhashbash: Internal error: read function NULL\n");
return -EINVAL;
}
if (!ops->resize) {
printk(KERN_ALERT "rcuhashbash: Internal error: resize function NULL\n");
return -EINVAL;
}
entry_cache = KMEM_CACHE(rcuhashbash_entry, 0);
if (!entry_cache)
goto enomem;
table = kzalloc(sizeof(*table) + (1UL << shift1) * sizeof(table->buckets[0]), GFP_KERNEL);
if (!table)
goto enomem;
table->mask = (1UL << shift1) - 1;
for (i = 0; i < entries; i++) {
struct rcuhashbash_entry *entry;
entry = kmem_cache_zalloc(entry_cache, GFP_KERNEL);
if(!entry)
goto enomem;
entry->value = i;
hlist_add_head(&entry->node, &table->buckets[i & table->mask]);
}
thread_stats = kcalloc(readers + resize, sizeof(thread_stats[0]), GFP_KERNEL);
if (!thread_stats)
goto enomem;
tasks = kcalloc(readers + resize, sizeof(tasks[0]), GFP_KERNEL);
if (!tasks)
goto enomem;
printk(KERN_ALERT "rcuhashbash starting threads\n");
for (i = 0; i < readers + resize; i++) {
struct task_struct *task;
if (i < readers)
task = kthread_run(rcuhashbash_read_thread,
&thread_stats[i],
"rcuhashbash_read");
else
task = kthread_run(rcuhashbash_resize_thread,
&thread_stats[i],
"rcuhashbash_resize");
if (IS_ERR(task)) {
ret = PTR_ERR(task);
goto error;
}
tasks[i] = task;
}
return 0;
enomem:
ret = -ENOMEM;
error:
rcuhashbash_exit();
return ret;
}
```
當 module exit 時，會停止所有執行緒，統計每個 reader thread 的 `stats`，並釋放 `table` 與 `thread_stats`
```c
static void __exit rcuhashbash_exit(void)
{
unsigned long i;
int ret;
printk(KERN_ALERT "exit\n");
if (tasks) {
for (i = 0; i < readers + resize; i++)
if (tasks[i]) {
ret = kthread_stop(tasks[i]);
if(ret)
printk(KERN_ALERT "rcuhashbash task returned error %d\n", ret);
}
kfree(tasks);
}
/* Wait for all RCU callbacks to complete. */
rcu_barrier();
if (table2) {
printk(KERN_ALERT "rcuhashbash FAIL: secondary table still exists during cleanup.\n");
kfree(table2);
}
if (table) {
for (i = 0; i <= table->mask; i++) {
struct hlist_head *head = &table->buckets[i];
while (!hlist_empty(head)) {
struct rcuhashbash_entry *entry;
entry = hlist_entry(head->first, struct rcuhashbash_entry, node);
head->first = entry->node.next;
kmem_cache_free(entry_cache, entry);
}
}
kfree(table);
}
if (entry_cache)
kmem_cache_destroy(entry_cache);
rcuhashbash_print_stats();
kfree(thread_stats);
printk(KERN_ALERT "rcuhashbash done\n");
}
```
## 論文 Banchmark 比較
### 實驗環境
```c
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
Stepping: 10
CPU MHz: 1800.000
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
### 實驗參數
分別調整三中不同演算法（rcu, ddds, rwlock）與 `reader` 的數量，比較每秒 lookup hit 的次數，而 resizer 在過程中會不斷調整 table 的大小，從 2^13^ 擴張到 2^14^ 再收縮回去（2 倍）
```c
static char *test = "rcu"; /* Hash table implementation to benchmark */
static int readers = 1;
static bool resize = true;
static u8 shift1 = 13;
static u8 shift2 = 14;
static unsigned long entries = 65536;
```
### 實驗結果
針對三中不同演算法，依序執行 1,2,4, 8, 16 個 readers
利用 shell script 固定每次測試時間為 30 秒
- RP 為論文的演算法
- DDDS 為另一個基於 RCU hashtable 的調整大小演算法，該演算法通過檢查多個 hashtable 達成 reaizing 時的查找
- rwlock 為利用 read, write lock 來達成查找
#### 固定 table 大小
固定大小在 2^14^， 比較不同演算法的查找次數
#### 開啟 resize
resize thread 會不斷在 2^13^ 到 2^14^ 之間調整 table 大小，比較在 resizing 時不同演算法的查找次數
#### 不同大小的 RP
比較固定大小在 2^13^ 與 2^14^ 還有 resize 時，使用 RP 演算法的查找次數
:::warning
論文所使用的實驗環境為 24 個 hardware-supported threads，所以它選擇使用 1, 2, 4, 8, 16 作為測試的 reader 數量，使運行的線程都比支持的硬體還少。
> Our test system had two Intel “Westmere” Xeon DP
processors at 2.4GHz, each of which had 6 hardware
cores of two logical threads each, for a total of 24
hardware-supported threads.
另外，論文觀察到 16 個 readers 與線性增長的預期偏差，可能是由於超過了 12 個處理器核的限制，而論文測試 16 readers 的性能似乎比 8 readers 的性能高出大約 50%，這與充分利用 12 個 cores 的預期線性增長一致
而本研究的實驗環境為 8 核 16 個硬體執行緒，但在 8 個 readers 就產生偏差，16 個 readers 發生瓶頸，可能原因是我在測試時仍有其他 process 在運作
:::
## 結論
本研究從最初的論文出發，說明 rhashtable 的動機、原理，再來介紹 Thomas Graf 在 Linux 核心的首次實作，以及至今 `rhashtable.h` 的演化，最後撰寫 Linux 核心模組作為試驗，得出以下結論：
- 比較論文與 Linux 核心測試的差異：
- 論文者要是希望驗證演算法在 resizing 時對查找影響
- Linux 核心將 resizing 自動化，主要測試插入、刪除與查找所花費的時間
- 論文的演算法比較：
- rhashtable 在測試中都提供了線性可擴展的查找性能。
- 在固定大小時，論文演算法與 DDDS 差不多，這兩種實現都大大地使 rwlock 相形見絀
- 在 resizing 時，論文演算法明顯優於 DDDS，但沒有如論文所述的幅度高達 56%
- 比較不同大小的 RP，可知論文的調整大小演算法幾乎不會增加並行查找的開銷
Sign in with Wallet
Connect another wallet