一、Hash表简介
1. 哈希表(Hash table)又叫散列表，是根据(Key, Value) 键值对进行访问的数据结构。主要目的是提高查询效率，比如Hash表的order为5，也就是同时使用2^5个链表，理论上查询速度可以比链表快2^5倍，典型的
以空间换时间。
2. 主要实现在 include/linux/hashtable.h 中，基于hlist。
二、相关结构
/* include/linux/types.h */
struct hlist_head {
struct hlist_node *first;
};
struct hlist_node {
struct hlist_node *next, **pprev;
};
使用二级指针 **pprev 可以使在删除节点上的处理变的简单，无需关心是否是head节点。而单链表或双向链表使用 *prev 成员需要单独判断是否是head节点。
三、相关函数
1. 定义Hash表
/* Hash表的表头就是一个数组，数组中每一个原生都是一个链表 */
#define DECLARE_HASHTABLE(name, bits) \
struct hlist_head name[1 << (bits)]
/* 定义并初始化 */
#define DEFINE_HASHTABLE(name, bits) \
struct hlist_head name[1 << (bits)] = \
{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }
2. Hash表初始化
/* 初始化Hash表 */
#define hash_init(hashtable) __hash_init(hashtable, HASH_SIZE(hashtable))
static inline void __hash_init(struct hlist_head *ht, unsigned int sz)
{
unsigned int i;
for (i = 0; i < sz; i++)
INIT_HLIST_HEAD(&ht[i]);
}
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
3. Hash表添加元素
/**
* hash_add - add an object to a hashtable
* @hashtable: hashtable to add to
* @node: the &struct hlist_node of the object to be added
* @key: the key of the object to be added
*/
#define hash_add(hashtable, node, key) \
hlist_add_head(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
/**
* hash_add_rcu - add an object to a rcu enabled hashtable
* @hashtable: hashtable to add to
* @node: the &struct hlist_node of the object to be added
* @key: the key of the object to be added
*/
#define hash_add_rcu(hashtable, node, key) \
hlist_add_head_rcu(node, &hashtable[hash_min(key, HASH_BITS(hashtable))])
4. Hash表遍历
/**
* hash_for_each - iterate over a hashtable
* @name: hashtable to iterate
* @bkt: integer to use as bucket loop cursor
* @obj: the type * to use as a loop cursor for each entry
* @member: the name of the hlist_node within the struct
*/
#define hash_for_each(name, bkt, obj, member) \
for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
(bkt)++)\
hlist_for_each_entry(obj, &name[bkt], member)
/**
* hash_for_each_rcu - iterate over a rcu enabled hashtable
* @name: hashtable to iterate
* @bkt: integer to use as bucket loop cursor
* @obj: the type * to use as a loop cursor for each entry
* @member: the name of the hlist_node within the struct
*/
#define hash_for_each_rcu(name, bkt, obj, member) \
for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
(bkt)++)\
hlist_for_each_entry_rcu(obj, &name[bkt], member)
/**
* hash_for_each_safe - iterate over a hashtable safe against removal of
* hash entry
* @name: hashtable to iterate
* @bkt: integer to use as bucket loop cursor
* @tmp: a &struct hlist_node used for temporary storage
* @obj: the type * to use as a loop cursor for each entry
* @member: the name of the hlist_node within the struct
*/
#define hash_for_each_safe(name, bkt, tmp, obj, member) \
for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
(bkt)++)\
hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
/**
* hash_for_each_possible - iterate over all possible objects hashing to the
* same bucket
* @name: hashtable to iterate
* @obj: the type * to use as a loop cursor for each entry
* @member: the name of the hlist_node within the struct
* @key: the key of the objects to iterate over
*/
#define hash_for_each_possible(name, obj, member, key) \
hlist_for_each_entry(obj, &name[hash_min(key, HASH_BITS(name))], member)
/**
* hash_for_each_possible_rcu - iterate over all possible objects hashing to the
* same bucket in an rcu enabled hashtable
* @name: hashtable to iterate
* @obj: the type * to use as a loop cursor for each entry
* @member: the name of the hlist_node within the struct
* @key: the key of the objects to iterate over
*/
#define hash_for_each_possible_rcu(name, obj, member, key, cond...) \
hlist_for_each_entry_rcu(obj, &name[hash_min(key, HASH_BITS(name))],\
member, ## cond)
/**
* hash_for_each_possible_rcu_notrace - iterate over all possible objects hashing
* to the same bucket in an rcu enabled hashtable in a rcu enabled hashtable
* @name: hashtable to iterate
* @obj: the type * to use as a loop cursor for each entry
* @member: the name of the hlist_node within the struct
* @key: the key of the objects to iterate over
*
* This is the same as hash_for_each_possible_rcu() except that it does
* not do any RCU debugging or tracing.
*/
#define hash_for_each_possible_rcu_notrace(name, obj, member, key) \
hlist_for_each_entry_rcu_notrace(obj, \
&name[hash_min(key, HASH_BITS(name))], member)
/**
* hash_for_each_possible_safe - iterate over all possible objects hashing to the
* same bucket safe against removals
* @name: hashtable to iterate
* @obj: the type * to use as a loop cursor for each entry
* @tmp: a &struct hlist_node used for temporary storage
* @member: the name of the hlist_node within the struct
* @key: the key of the objects to iterate over
*/
#define hash_for_each_possible_safe(name, obj, tmp, member, key) \
hlist_for_each_entry_safe(obj, tmp,\
&name[hash_min(key, HASH_BITS(name))], member)
5. Hash表元素删除
/**
* hash_del - remove an object from a hashtable
* @node: &struct hlist_node of the object to remove
*/
static inline void hash_del(struct hlist_node *node)
{
hlist_del_init(node);
}
/**
* hash_del_rcu - remove an object from a rcu enabled hashtable
* @node: &struct hlist_node of the object to remove
*/
static inline void hash_del_rcu(struct hlist_node *node)
{
hlist_del_init_rcu(node);
}
注：更多API见 hashtable.h。
四、使用举例
1. 使用hash表缓存内核符号
#define pr_fmt(fmt) "Hash Table Debug: " fmt
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/errno.h>
#include <linux/init.h>
#include <linux/kallsyms.h>
#include <linux/hashtable.h>
#define HASH_TABLE_BIT 5
#define HASH_TABLE_LEN (1 << HASH_TABLE_BIT)
#define HASH_KEY_MASK ((1 << HASH_TABLE_BIT) - 1)
struct hash_node {
unsigned long addr;
char symbol[KSYM_SYMBOL_LEN];
struct hlist_node node;
};
struct hash_test_desc {
struct hlist_head htbl[HASH_TABLE_LEN];
};
static struct hash_test_desc *htd = NULL;
static const char *find_and_cache_symbol(unsigned long caller_addr)
{
struct hash_node *cur_node = NULL;
struct hash_node *new_node = NULL;
const char *cur_symbol = NULL;
unsigned int cur_key = 0;
if (!htd)
return "NULL";
cur_key = (unsigned int) caller_addr & HASH_KEY_MASK;
/* try to find symbols from history records */
hash_for_each_possible(htd->htbl, cur_node, node, cur_key) {
if (cur_node->addr == caller_addr) {
cur_symbol = cur_node->symbol;
break;
}
}
/* symbol not found, add new a record */
if (!cur_symbol) {
new_node = kzalloc(sizeof(struct hash_node), GFP_ATOMIC);
if (!new_node)
return "NULL-no_mem";
new_node->addr = caller_addr;
sprint_symbol(new_node->symbol, caller_addr);
cur_symbol = new_node->symbol;
hash_add(htd->htbl, &new_node->node, cur_key);
}
return cur_symbol;
}
static void remove_hash_table(struct hash_test_desc *ld)
{
int bkt = 0;
struct hash_node *cur = NULL;
struct hlist_node *tmp = NULL;
struct hlist_head *htbl = NULL;
if (!ld)
return;
hash_for_each_safe(ld->htbl, bkt, tmp, cur, node) {
hash_del(&cur->node);
kfree(cur);
}
}
static void hash_table_hook_func(void)
{
void *location;
if (!htd)
return;
location = __builtin_return_address(1);
pr_info("caller=%s\n", find_and_cache_symbol((unsigned long)location));
}
EXPORT_SYMBOL(hash_table_hook_func);
static int __init hash_table_debug_init(void)
{
struct hash_test_desc *ld = kzalloc(sizeof(struct hash_test_desc), GFP_KERNEL);
if (!ld) {
pr_info("kzalloc failed!\n");
return -ENOMEM;
}
htd = ld;
return 0;
}
static void __exit hash_table_debug_exit(void)
{
struct hash_test_desc *ld = htd;
htd = NULL;
remove_hash_table(ld);
kfree(ld);
}
module_init(hash_table_debug_init);
module_exit(hash_table_debug_exit);
MODULE_DESCRIPTION("Hash Table Debug");
MODULE_LICENSE("GPL v2");
参考：https://zhuanlan.zhihu.com/p/360217911
标签：node,hashtable,hash,name,hlist,each,Hash,内核 From： https://www.cnblogs.com/hellokitty2/p/16648235.html