hash table 內(nèi)核中的哈西表結(jié)構(gòu)
常用 API
在 Linux 內(nèi)核中，Hash Table 和 RCU 是經(jīng)常一起使用的。Hash Table 主要用于快速查找元素，而 RCU 用于讀操作的并發(fā)保護(hù)，以便多個(gè)線程能夠同時(shí)訪問 Hash Table。以下是 Hash Table 與 RCU 相關(guān)的一些 API：
hlist_add_head_rcu() 和 hlist_add_tail_rcu()：在 Hash Table 中添加新節(jié)點(diǎn)，使用 RCU 確保并發(fā)讀訪問的正確性。
hlist_del_rcu()：從 Hash Table 中刪除一個(gè)節(jié)點(diǎn)，使用 RCU 確保并發(fā)讀訪問的正確性。
hlist_for_each_entry_rcu()：使用 RCU 遍歷 Hash Table，讀取節(jié)點(diǎn)數(shù)據(jù)時(shí)使用 rcu_dereference() 等 RCU API 以確保正確性。
rcu_assign_pointer()：用于使用 RCU 保護(hù)指針賦值操作。
synchronize_rcu()：等待所有已經(jīng)開始的 RCU 讀操作完成，以便對(duì) Hash Table 進(jìn)行修改。
使用 Hash Table 時(shí)，需要特別注意并發(fā)讀寫的正確性，以避免數(shù)據(jù)不一致等問題。使用 RCU 可以有效地提高 Hash Table 的并發(fā)讀取性能，并減少鎖競(jìng)爭(zhēng)。
demo
首先，定義一個(gè)哈希表結(jié)構(gòu)體 my_file_ht，包含了一個(gè)哈希數(shù)組和一個(gè)自旋鎖用于保護(hù)哈希表的并發(fā)操作。
#define HT_SIZE 1024
struct my_file_ht {
struct hlist_head head[HT_SIZE];
spinlock_t lock;
};
接著，定義一個(gè)緩存文件狀態(tài)的結(jié)構(gòu)體 my_file_ar，包含了文件描述符的 inode 號(hào)和狀態(tài)掩碼。
struct my_file_ar {
__le32 ino;
int mask;
struct hlist_node node;
};
接下來，提供哈希表的初始化函數(shù)，初始化哈希表的每個(gè)哈希槽都為空鏈表，并初始化哈希表的自旋鎖。
void my_file_ht_init(struct my_file_ht *ht)
{
int i;
for (i = 0; i < HT_SIZE; i++)
INIT_HLIST_HEAD(&ht->head[i]);
spin_lock_init(&ht->lock);
}
然后，提供一個(gè)添加節(jié)點(diǎn)的函數(shù)，使用哈希表的自旋鎖來保護(hù)節(jié)點(diǎn)的添加操作。
void my_file_ht_add(struct my_file_ht *ht, struct my_file_ar *ar)
{
unsigned int hash = my_file_ht_hashfn(ar->ino);
spin_lock_bh(&ht->lock);
hlist_add_head_rcu(&ar->node, &ht->head[hash]);
spin_unlock_bh(&ht->lock);
}
接下來，提供一個(gè)查找節(jié)點(diǎn)的函數(shù)，使用 RCU 機(jī)制來保護(hù)節(jié)點(diǎn)的讀操作。需要注意的是，這里使用了 hlist_for_each_entry_rcu 函數(shù)來遍歷鏈表。
struct my_file_ar *my_file_ht_lookup(struct my_file_ht *ht, __le32 ino)
{
unsigned int hash = my_file_ht_hashfn(ino);
struct my_file_ar *ar = NULL;
struct hlist_node *n;
rcu_read_lock();
hlist_for_each_entry_rcu(ar, n, &ht->head[hash], node) {
if (ar->ino == ino) {
rcu_read_unlock();
return ar;
}
}
rcu_read_unlock();
return NULL;
}
最后，提供一個(gè)刪除節(jié)點(diǎn)的函數(shù)，使用哈希表的自旋鎖來保護(hù)節(jié)點(diǎn)的刪除操作。
void my_file_ht_del(struct my_file_ht *ht, struct my_file_ar *ar)
{
unsigned int hash = my_file_ht_hashfn(ar->ino);
spin_lock_bh(&ht->lock);
hlist_del_rcu(&ar->node);
spin_unlock_bh(&ht->lock);
call_rcu(&ar->rcu, my_file_ht_rcu_free);
}
同時(shí)，我們還需要提供一個(gè)回調(diào)函數(shù) my_file_ht_rcu_free，用于釋放節(jié)點(diǎn)內(nèi)存空間：
static void my_file_ht_rcu_free(struct rcu_head *rcu)
{
struct my_file_ar *ar = container_of(rcu, struct my_file_ar, rcu);
kfree(ar);
}
在這個(gè)回調(diào)函數(shù)中，我們使用 container_of 宏將 RCU 頭轉(zhuǎn)換為節(jié)點(diǎn)指針，然后調(diào)用 kfree 函數(shù)釋放節(jié)點(diǎn)內(nèi)存空間。
這樣，就完成了一個(gè)基于哈希表和 RCU 的緩存文件描述符及其狀態(tài)的 demo。在多線程環(huán)境下，讀操作不需要加鎖，寫操作只需要用自旋鎖來保護(hù)并發(fā)修改，從而提高了讀寫操作的效率。
static inline unsigned int my_file_ht_hashfn(__le32 ino)
{
return le32_to_cpu(ino) % HT_SIZE;
}
這個(gè)哈希函數(shù)使用了 inode 的值對(duì)哈希表大小進(jìn)行求模，從而獲得在哈希表中的索引值。其中，le32_to_cpu 用于將 inode 的字節(jié)序從小端轉(zhuǎn)換為主機(jī)字節(jié)序，以便更好地進(jìn)行哈希計(jì)算。
請(qǐng)注意，這個(gè)哈希函數(shù)只是一個(gè)簡(jiǎn)單的示例，實(shí)際應(yīng)用中可能需要根據(jù)具體的場(chǎng)景來編寫更加復(fù)雜的哈希函數(shù)。
