rhashtable 研究

contributed by < linjohnss >

GitHub: rcuhashbash

目標

Linux 核心提供一套 Resizable, Scalable, Concurrent Hash Table，名為 rhashtable (見 include/linux/rhashtable.h 及 lib/rhashtable.c)，描述於論文〈Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming〉。摘譯 LWN 文章，並佐以原論文，描述 rhashtable 何以落實高效的並行雜湊表，搭配撰寫 Linux 核心模組作為試驗

Relativistic hash tables, part 1: Algorithms

hash table 在 Linux 的應用場景

在 Linux 的 file system 中，利用 hash table 儲存 mount 的 root dentry ，因此 lookup_mount 可以利用 hash_get 取得 mount 的 root dentry

/*
 * 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

#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〉的論文，描述了該問題解決方案。

rhashtable 在 Linux 核心的應用場景

在 Linux 核心的網路模組中，RDS 使用 rhashtable 儲存 ip 地址與 port
linux/net/rds/bind.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 組成。

Table shrinking

若發現目前的 hash table 的空間太大，希望能縮小 hash table

Initial state:
將初始狀態分為 odd 與 even 兩種 bucket，odd 為奇數 reader 可以存取，even 為偶數 reader 可以存取。

Initialize new buckets:
分配一個新的 shrinking hash table，連接到對應的舊 node(指向具有匹配 index 的第一項)，並將其儲存在 writer 的 local memory 中，其它 reader 無法存取

Link old chains:
將奇數 bucket 的 tail 接到偶數 bucket，因此在 reader 存取奇數 bucket 時，也會存取到偶數的部份。查找的結果仍然會是正確的，但這會導致需要走訪更長的時間

此演算法放寬每個 bucket 內的 link list 必須為同一個 index 的限制，使 link list 可以臨時包含不同 index 的 node，確保在 resizing 時不會找不到 node，並且可以避免複製 link list，論文稱其為 "hash chains imprecise"

Publish new buckets:
將 table 指標指向新的 hash table，此時後續的 reader 將會從新的 table 進行操作

Wait for readers:
此時，仍可能有 reader 正在走訪舊的 bucket，所以必須等待一個 RCU 的寬限期過去
若新的 hash table 有兩個以上的 bucket，則需像 expansion 一樣 unzip

Reclaim:
釋放舊的 hash table，完成 hash table shrinking

為簡單起見，rhashtable 透過整數因子限制 resizing 改變桶的數量。例如，將 bucket 的數量加倍或減半。這保證了兩個約束：

當收縮 table 時，新 table 的每個 bucket 將包含多個來自舊 table 的bucket
當擴張 table 時，新 table 的每個 bucket 將包含最多一個來自舊 table 的 bucket

Table expansion

隨著 hash table 中的 node 數量增加，每個 bucket 的平均深度會增加，造成查找效率降低，因此需要擴張大小

Initial state:
假設初始狀態為只有一個 bucket 的 hash table

Initialize new buckets:
分配一個新的包含兩個 bucket 的 expansion hash table，連接到對應的舊 node(指向具有匹配 index 的第一項)，並將其儲存在 writer 的 local memory 中，其它 reader 無法存取

Publish new buckets:
將 table 指標指向新的 hash table，此時後續的 reader 將會從新的 table 進行操作，舊有的 hash table 可能有 reader 正在存取，還不可以釋放

注意，此時新的兩個 bucket 只有連接的第一個 node 為正確的，但由於舊的 link list 仍將 node 接在一起，所以此時新的 hash table 查找成果仍為正確，只是需要花費較多走訪時間

Wait for readers:
需要等待一個 RCU 寬限期過去，才能開始舊的 hash table 進行 unzip

Unzip one step:
進行 unzip 的過程使利用存取舊的 hash table 來工作，其演算法如下：
1.) 確定 link list 中的第一個 node 屬於新 hash table 的哪個 bucket
2.) 持續走訪 link list，直到遇到不屬於同一個 bucket 的 node
3.) 此時，舊的 bucket 將會指向該 node，成果如下：

4.) 更改前一項中的 next 指標，指向下一個匹配的 node：

在另一個 RCU 寬限期過去之前，不能對此 list 進行任何更改，否則在 list 中的 reader 可能最終會出現在錯誤的位置。

假設尋找綠色 node 的 reader 可能正在查看從列表中修補出來的藍色 node，但是，由於該 node 的 next 指標保持不變，因此 reader 不會 derailed。而尋找藍色 node 的 reader 從一開始就不會看到更改的 node，因此它們也是安全的。

該演算法通過更改不尋找將 "unzip" 的 node 的 reader 的可見指標來工作。只要每個 RCU 寬限期只更改列表中的一個指標，這個屬性就成立，並且當 reader 通過它時，list 可以安全地 unzip。

Wait for readers:
修改完成後，在一次等待一個 RCU 寬限期

Unzip again:
重複步驟 5，此時舊 hash table 的 bucket 指向 even node

Final state:
重複等待 reader 與 unzip，直到處理到每個 bucket 的尾端。此時每個 node 僅出現在其相段應的 bucket 中，即可釋放舊的 hash table，完成 hash table expansion

如果 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 同時插入與刪除主要可以分為兩種情形：

Table shrinking
收縮演算法可以選擇在完成初始化後立即為 updaters 發布已初始化的 table，從而允許在進行 cross-linking 的同時進行並行更新（Table shrinking step 3）。收縮演算法也會在它完成與該 bucket 的 cross-linking 後立即刪除該 bucket 的每個鎖，從而允許對該 bucket 的並行插入和刪除。
Table expansion
在擴展演算法中，需要比收縮演算法更小心處理，對 zipped link list 進行單個 unzip 操作時，必須獲取該 bucket 的鎖。在執行插入時，只須在沒有被 lock 的 bucket 開頭插入，就不會影響 resizing。但在執行刪除時，可能會發生在 list 中的任何節點，包括標記下一個 unzip 目標的指標位置（舊 table 的 bucket pointer，論文稱 "aux pointer"），所以需要檢查與 aux pointer 的衝突，如果發生衝突，刪除節點後需要更新 aux pointer。鑑於與查找和插入相比，刪除的頻率相對較低，調整大小的頻率甚至更低，因此在刪除演算法中要求這種額外的檢查是可以接受的。

論文中有更多的實做細節，包含針對記憶體分配的 "Resizing in Place" 與優化 hash 分配的 "Keeping Buckets Sorted" 本節就暫不描述

rcuhashbash-resize

rcuhashbash-resize 為論文創建一個為了可調整大小的 hash table 的測試工具和基準測試框架。首先創建一個具有指定 bucket 數量的 hash table，並向其中添加包含從 0 到指定上限的整數值的元素。然後它啟動 reader 執行緒和調整大小執行緒，這些執行緒記錄 thread-local 統計資料，以避免需要額外的同步。當測試完成時，rcuhashbash-resize 停止所有執行緒，匯總它們記錄的統計數據，並通過 kernel message buffer 顯示結果。

Relativistic hash tables, part 2: Implementation

rhashtable 的實現在 Linux 核心 3.17 版開始加入，這使得 hashtable 可以調整大小，並同時允需 reader 與 writer 同時存取。此篇將描述在 3.17 版中所看到的 "rhashtable" 的 kernel API。

rhashtable 最初是為了在網路子系統中使用而被創建的，但當時的開發者 Thomas Graf 明白 rhashtable 將會獲得更廣泛的使用。因此，他們設計一系列的前置參數，來擴張 rhashtable 的 API 的使用可能，只要完成設置，後續對 table 的操作就會相對簡單了。

rhashtable structure

首先，我們可以看到 rhashtable 的結構包含 rhashtable_params，因此需要先定義參數結構

/**
 * 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 的函式時保持鎖定。

/**
 * 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

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

int rhashtable_expand(struct rhashtable *ht, gfp_t gfp_flags);
int rhashtable_shrink(struct rhashtable *ht, gfp_t gfp_flags);

Lookup

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);

文章提到，後需提交的 patch 將會把調整大小的操作移到單獨的執行序中，所以將不再需要在上述函式中分配記憶體空間。因此，gfp_flags 參數將被刪除。而我們也可以看到在 6eba82 已刪除此參數

Per bucket locks & deferred expansion/shrinking

原先沒有像論文描述的對每個 bucket 用 lock 保護，加入對每個 bucket 的 spinlock，可以增加並行效率。並且將 expansion 與 shrinking 加到允許從 atomic context 插入和刪除的 warker queue，達到延遲 resizing 使插入和刪除可能與它並行發生，僅在 bucket unzip 或被 link 才短暫暫停

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
我嘗試將 rhashtable.c 複製下來，並將其掛載到核心

實驗環境

首先，確認 Linux 核心版本為 5.13

$ uname -r
5.13.0-51-generic

建構核心模組

從 test_rhashtable.c 的程式碼來看，他是使用 __init and __exit macros 去實做。因此我參考 Linux 核心模組運作原理中掛載 hello 的方式
Makefile

obj-m := test_rhashtable.o
clean:
	rm -rf *.o *.ko *.mod.* *.symvers *.order *.mod.cmd *.mod

編譯核心模組

$ make -C /lib/modules/`uname -r`/build M=`pwd` modules

掛載核心模組

產生 test_rhashtable.ko 之後，可將其掛載:

$ sudo insmod test_rhashtable.ko

dmesg 命令可顯示核心訊息

[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 的目的是測量操作的時間與正確性，主要分為三個部份：

插入、走訪與刪除測試以及 table 的最大大小測試
測試插入會 map 到同一個 bucket 的不同值
在多線程同時存取 table

而 resizing 的部份會在 rhashtable_init 時利用 rht_deferred_worker 使 table 在測試時自動調整大小，其作法是用 rht_grow_above_75() 與 rht_shrink_below_30() 判斷要擴張還是縮小

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 將 rhashtable-types.h 拆分出來，內容只包含主要的型態宣告，後續只須引入 rhashtable-types.h 即可，進而減少大型的重新編譯。

rhashtable_params

v5.13 的 rhashtable 參數相較 v3.17 的更加簡單易用，多了可以自動對 table 進行收縮的參數 automatic_shrinking

/**
 * 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 加快運行時間

/**
 * 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

下載程式碼

git clone git://git.kernel.org/pub/scm/linux/kernel/git/josh/rcuhashbash.git

編譯核心模組

程式碼提供 rcuhashbash.c 與 rcuhashbash-resize.c，這裡主要先測試 rcuhashbash-resize.c

make modules

編譯後會出現很錯誤，接下來就是一個一個 debug

出現 cpu_clock 錯誤

error: implicit declaration of function ‘cpu_clock’ [-Werror=implicit-function-declaration]

從 linux kernel 程式碼中找到 cpu_clock() 是定義在 linux/sched/clock.h，因此引入該函式庫

#include <linux/sched/clock.h>

hlist_for_each_entry_rcu、hlist_for_each_entry
程式碼中的 hlist_for_each_entry_rcu 用法怪怪的，原先 v2.6.37 的定義為 hlist_for_each_entry_rcu(tpos, pos, head, member)，而根據 v5.13 的 rculist.h 已改為 hlist_for_each_entry_srcu(pos, head, member, cond)，故將程式碼根據新的定義進行修改

- 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 之後，可將其掛載:

$ sudo insmod rcuhashbash.ko

dmesg 命令可顯示核心訊息

[ 六 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 開啟仍出現問題

[ 六 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，就沒問題了




- 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;




- old_table->buckets[i].first = node;
- if (!node)
+ old_table->buckets[i].first = &entry->node;
+ if (!&entry->node)






- 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 作輸出

[ 六 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 內條目的數量

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 執行緒需要紀錄的統計變數

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

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

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 比較

實驗環境

$ 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¹³ 擴張到 2¹⁴ 再收縮回去（2 倍）

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¹⁴，比較不同演算法的查找次數

開啟 resize

resize thread 會不斷在 2¹³ 到 2¹⁴ 之間調整 table 大小，比較在 resizing 時不同演算法的查找次數

不同大小的 RP

比較固定大小在 2¹³ 與 2¹⁴ 還有 resize 時，使用 RP 演算法的查找次數

論文所使用的實驗環境為 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，可知論文的調整大小演算法幾乎不會增加並行查找的開銷

rhashtable 研究

目標

Relativistic hash tables, part 1: Algorithms

hash table 在 Linux 的應用場景

data compress

rhashtable 解決的問題

rhashtable 在 Linux 核心的應用場景

論文〈Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming〉

Table shrinking

Table expansion

Handling Insertion and Removal

rcuhashbash-resize

Relativistic hash tables, part 2: Implementation

rhashtable structure

rhashtable operations

Insertion and Removal

Expand and Shrink

Lookup

Per bucket locks & deferred expansion/shrinking

撰寫 Linux 核心模組作為試驗

實驗環境

建構核心模組

編譯核心模組

掛載核心模組

程式碼運作原理

v5.13 與 v3.17 比較

rhashtable-types.h

rhashtable_params

rhashtable_lookup_fast

執行論文提供的 rcuhashbash-resize

下載程式碼

編譯核心模組

掛載核心模組

量測時間

程式碼運作原理

論文 Banchmark 比較

實驗環境

實驗參數

實驗結果

固定 table 大小

開啟 resize

不同大小的 RP

結論

Read more

2022q1 Homework5 (quiz6)

2022q1 Homework5 (quiz5)

2022q1 Homework3 (fibdrv)

2022q1 Homework4 (quiz4)