理解并使用Linux内核Hash表
理解并使用Linux内核Hash表
1. 引言
1.1 为什么学习Linux内核Hash表？
在Linux内核开发中，Hash表（哈希表）是一种非常高效的数据结构，它广泛应用于内核中各类数据的存储和查找。学习并理解Linux内核中的Hash表，不仅可以帮助开发者在内核模块中高效地处理数据，还能够提升对内核设计和性能优化的理解。在日常的内核编程中，哈希表常常用于实现资源管理、内存管理、文件系统、网络协议等多个方面。
1.2 Hash表在日常编程中的应用
在日常编程中，哈希表被用于存储键值对，并支持常数时间复杂度的查找、插入和删除操作。无论是开发数据库、缓存系统，还是在处理大数据集合时，哈希表都是必不可少的工具。尤其是在需要快速查找或处理大量数据时，哈希表能极大提高性能。
2. Hash表基础回顾
2.1 什么是Hash表？
哈希表是一种基于哈希函数将数据映射到固定大小的存储位置（桶）的数据结构。每个桶存储一个或多个数据项，哈希函数通过键值计算出数据项的存储位置。哈希表提供了高效的插入、查找和删除操作，时间复杂度接近O(1)，这使得它成为许多应用程序中理想的数据结构。
2.2 哈希函数的工作原理
哈希函数是哈希表的核心，它将键（key）转换为数组下标。理想的哈希函数应该具备以下特点：
- 均匀分布：不同的键值应均匀分布在哈希表的各个桶中，以避免冲突。
- 高效性：哈希函数计算简单，能够快速返回数组下标。
常见的哈希函数包括除法法、乘法法、位运算法等。
2.3 解决哈希冲突的方法
哈希冲突是指多个键值映射到同一个桶中。常见的冲突解决方法有：
- 链地址法：每个桶存储一个链表，所有映射到同一桶的键值对都存储在这个链表中。
- 开放地址法：如果桶已经被占用，则寻找下一个空桶来存储数据。
- 双重哈希法：使用另一个哈希函数来解决冲突。
Linux内核中的哈希表通常使用链地址法来解决冲突。
3. Linux内核中的Hash表
3.1 内核Hash表的独特需求
与用户空间应用中的哈希表不同，Linux内核的哈希表需要满足以下特殊需求：
- 高效性：内核代码往往需要处理大量数据，因此哈希表的性能至关重要。
- 内存管理：内核中的数据结构管理要求内存分配和释放更加严格和高效。
- 线程安全：内核操作往往需要支持并发执行，因此需要考虑并发访问时的数据一致性。
3.2 数据结构概览：链地址法和其他方法
Linux内核中的哈希表主要使用链地址法，它通过hlist_head和hlist_node结构实现。每个桶头是一个hlist_head结构，它包含一个指向链表的指针，所有映射到同一个桶的元素都通过hlist_node进行链接。
3.3 内核中常用的哈希算法介绍
Linux内核提供了一些常用的哈希算法，例如：
- Jenkins hash：一种非加密的哈希算法，具有较高的性能和较低的冲突概率。内核中常用的
hash_long函数就是基于 Jenkins 算法实现的。 - FNV-1a hash：一种简单的哈希算法，适用于大多数场景。
- MurmurHash：在内核中也有应用，通常用于非加密的场景。
这些哈希算法确保哈希表的数据分布尽可能均匀，从而减少哈希冲突，提高性能。
3.5 并发控制与同步机制
在内核中，哈希表经常用于多线程环境，因此需要确保并发访问时的同步。
- 自旋锁：在修改哈希表时，加锁确保只有一个线程能够访问表。
- 读写锁：对于读操作较多的情况，可以使用读锁，允许多个线程并发读取数据。
4. Hash表示例代码: 增删查遍历
通过这个示例，你可以理解如何在Linux内核中使用哈希表及其相关操作接口。
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/list.h>
// 定义哈希表的大小
#define HASH_TABLE_SIZE 16
// 哈希表节点结构
struct hash_node {
int key;
int value;
struct hlist_node hnode; // 链表节点
};
// 哈希表头
static struct hlist_head hash_table[HASH_TABLE_SIZE];
// 哈希函数：计算key的哈希值
static unsigned int hash_function(int key)
{
return key % HASH_TABLE_SIZE;
}
// 插入元素到哈希表
static void insert_into_hash_table(int key, int value)
{
unsigned int hash_index = hash_function(key);
struct hash_node *new_node;
new_node = kmalloc(sizeof(struct hash_node), GFP_KERNEL);
if (!new_node) {
pr_err("Memory allocation failed\n");
return;
}
new_node->key = key;
new_node->value = value;
// 将节点添加到对应哈希表桶的头部
hlist_add_head(&new_node->hnode, &hash_table[hash_index]);
pr_info("Inserted key: %d, value: %d into hash table\n", key, value);
}
// 从哈希表中删除元素
static void delete_from_hash_table(int key)
{
unsigned int hash_index = hash_function(key);
struct hash_node *node;
struct hlist_node *tmp;
// 遍历链表寻找对应的节点
hlist_for_each_entry_safe(node, tmp, &hash_table[hash_index], hnode) {
if (node->key == key) {
hlist_del(&node->hnode); // 删除节点
kfree(node); // 释放内存
pr_info("Deleted key: %d from hash table\n", key);
return;
}
}
pr_info("Key: %d not found in hash table\n", key);
}
// 查找哈希表中的元素
static struct hash_node *find_in_hash_table(int key)
{
unsigned int hash_index = hash_function(key);
struct hash_node *node;
// 遍历链表寻找对应的节点
hlist_for_each_entry(node, &hash_table[hash_index], hnode) {
if (node->key == key) {
return node;
}
}
return NULL; // 未找到
}
// 初始化哈希表
static int __init hash_table_init(void)
{
int i;
// 初始化哈希表
for (i = 0; i < HASH_TABLE_SIZE; i++) {
INIT_HLIST_HEAD(&hash_table[i]);
}
// 测试插入、查找和删除操作
insert_into_hash_table(10, 100);
insert_into_hash_table(20, 200);
insert_into_hash_table(30, 300);
struct hash_node *node = find_in_hash_table(20);
if (node) {
pr_info("Found key: %d, value: %d\n", node->key, node->value);
} else {
pr_info("Key: 20 not found\n");
}
delete_from_hash_table(10);
node = find_in_hash_table(10);
if (node) {
pr_info("Found key: %d, value: %d\n", node->key, node->value);
} else {
pr_info("Key: 10 not found\n");
}
return 0;
}
// 清理哈希表
static void __exit hash_table_exit(void)
{
int i;
struct hash_node *node;
struct hlist_node *tmp;
// 清理哈希表
for (i = 0; i < HASH_TABLE_SIZE; i++) {
hlist_for_each_entry_safe(node, tmp, &hash_table[i], hnode) {
hlist_del(&node->hnode);
kfree(node);
}
}
pr_info("Hash table module exited\n");
}
module_init(hash_table_init);
module_exit(hash_table_exit);
MODULE_LICENSE("GPL");
MODULE_AUTHOR("Your Name");
MODULE_DESCRIPTION("A simple Linux kernel module using hlist as a hash table");
解释
- 哈希函数：使用简单的取余方式
key % HASH_TABLE_SIZE来计算哈希值。 - 插入操作：
insert_into_hash_table函数创建一个新的哈希节点，并将其插入到计算得到的哈希表桶的头部。 - 删除操作：
delete_from_hash_table函数遍历链表并删除匹配的节点。如果找到该节点，调用hlist_del将其从链表中删除，并使用kfree释放内存。 - 查找操作：
find_in_hash_table函数遍历链表并查找匹配的节点。如果找到，返回该节点；否则返回NULL。 - 初始化和清理：模块加载时，初始化哈希表，并进行一些插入、查找和删除的测试。模块卸载时，释放所有分配的内存。
测试流程
- 插入了键值对 (10, 100)、(20, 200)、(30, 300) 到哈希表。
- 查找键为 20 的节点，并打印值。
- 删除键为 10 的节点，再次查找键为 10 的节点，验证删除是否成功。
注意事项
hlist_add_head用于将新节点添加到链表的头部。hlist_del删除节点时不会将节点初始化，因此，如果你需要将节点移除并初始化，应该使用hlist_del_init。- 通过
hlist_for_each_entry_safe实现遍历操作，确保在遍历过程中删除节点时不会造成崩溃。
5. 深入理解
在这一节中，我们将分析Linux内核中哈希表的源代码，特别是插入、删除和遍历操作的实现。Linux内核中的哈希表通常使用链表处理哈希冲突，这样可以高效地管理键值对。
5.1 哈希表插入操作的代码分析
// 将节点 n 添加到链表 h 的头部
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
// 获取链表 h 的第一个节点
struct hlist_node *first = h->first;
// 将节点 n 的 next 指针指向当前链表的第一个节点
n->next = first;
// 如果链表非空，则更新第一个节点的 pprev 指针，指向新插入的节点
if (first)
first->pprev = &n->next;
// 使用 WRITE_ONCE 来确保对 h->first 的更新在多线程环境中的正确性
WRITE_ONCE(h->first, n);
// 设置节点 n 的 pprev 指针为指向链表头部（h->first）
n->pprev = &h->first;
}
解释：
hlist_add_head：该函数将节点n插入到链表h的头部。struct hlist_node *first = h->first;：首先获取链表h的第一个节点。如果链表为空，h->first是NULL。n->next = first;：将新节点n的next指针指向当前的第一个节点。if (first) first->pprev = &n->next;：如果链表非空，则将当前第一个节点的pprev指针指向新节点n。这样，新节点n成为新的头节点。WRITE_ONCE(h->first, n);：将链表的头指针h->first更新为新节点n。WRITE_ONCE用于防止在并发环境下发生不一致的写入操作。n->pprev = &h->first;：将新节点n的pprev指针指向链表头指针的地址，以保持双向链表的正确性。
5.2 哈希表删除操作的代码分析
删除操作用于从哈希表中移除一个指定节点。内核提供了两种删除操作：一种是删除节点并不重新初始化，另一种则是删除后重新初始化节点。
// 内部删除节点函数，实际执行删除操作
static inline void __hlist_del(struct hlist_node *n)
{
// 获取节点的下一个节点
struct hlist_node *next = n->next;
// 获取节点的前驱节点的指针（指向当前节点的前一个节点）
struct hlist_node **pprev = n->pprev;
// 将当前节点从链表中删除：将前驱节点的next指针指向当前节点的next指针
WRITE_ONCE(*pprev, next);
// 如果当前节点后面还有节点，将后继节点的pprev指针指向前驱节点
if (next)
next->pprev = pprev;
}
// 删除节点并使其指向特定的“毒值”以防止后续误用
static inline void hlist_del(struct hlist_node *n)
{
// 调用 __hlist_del 函数实际删除节点
__hlist_del(n);
// 设置节点的 next 和 pprev 指针为“毒值”，以便调试时发现已删除节点的访问
n->next = LIST_POISON1;
n->pprev = LIST_POISON2;
}
// 删除节点并重新初始化它，以便重新使用
static inline void hlist_del_init(struct hlist_node *n)
{
// 如果节点未被删除（即未被移除链表）
if (!hlist_unhashed(n)) {
// 调用 __hlist_del 删除节点
__hlist_del(n);
// 重新初始化节点，以防它再次被误用
INIT_HLIST_NODE(n);
}
}
hlist_del：首先调用__hlist_del函数从链表中删除节点，然后将节点的next和pprev指针设置为特殊值LIST_POISON1和LIST_POISON2，以便在调试时检测。hlist_del_init：此函数在删除节点后会重新初始化节点，避免节点重复使用时引发问题。
5.3 哈希表遍历操作的代码分析
哈希表的遍历操作是操作哈希表时常见的任务，特别是在需要遍历哈希桶中的所有元素时。在 Linux 内核中，哈希表的遍历有几种常见的方式，包括基本的遍历、删除安全遍历以及通过结构体成员进行的遍历。
以下是 Linux 内核中用于哈希表遍历的宏定义：
// 遍历哈希表中的所有节点，从链表头开始
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos; pos = pos->next)
// 遍历哈希表中的所有节点，保证在遍历过程中删除节点的安全
#define hlist_for_each_safe(pos, n, head) \
for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
pos = n)
// 遍历哈希表中的每个元素，适用于结构体嵌套链表节点的遍历
#define hlist_for_each_entry(pos, head, member) \
for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
pos; \
pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
1. hlist_for_each
这是最基础的遍历方式，用于遍历哈希表中链表的所有节点。它从链表头部开始，依次访问每个节点，直到链表末尾。
pos = (head)->first：首先将pos设置为链表头部head->first，即哈希桶中的第一个节点。pos = pos->next：然后在每次迭代中，将pos移动到下一个节点，直到pos为NULL（即链表末尾）。
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos ; pos = pos->next)
2. hlist_for_each_safe
这个宏比 hlist_for_each 更为安全，特别适用于在遍历过程中可能会删除链表节点的情况。它通过使用临时变量 n 来保存当前节点的下一个节点，从而避免了在删除当前节点时链表结构的破坏。
pos = (head)->first：将pos设置为链表头部head->first，开始遍历。n = pos->next：在每次循环开始时，将n设置为当前节点的下一个节点，确保即使当前节点被删除，遍历过程依然能继续。pos = n：每次循环结束时，更新pos为n，继续遍历下一个节点。
#define hlist_for_each_safe(pos, n, head) \
for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
pos = n)
3. hlist_for_each_entry
这个宏用于遍历哈希表中每个元素，尤其是当链表节点是结构体中的一部分时。这种遍历方式需要特别注意，遍历过程中会从链表头部 head->first 开始，查找每个节点中的嵌套链表节点。它确保了可以直接访问结构体中的数据。
hlist_entry_safe：该宏是对节点指针的封装，它将hlist_node指针转换为指向结构体的指针，确保遍历过程不会由于空指针而出错。pos = hlist_entry_safe((head)->first, typeof(*(pos)), member)：将pos设置为链表中的第一个元素，hlist_entry_safe将链表节点指针转换为结构体指针。pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member)：然后遍历结构体中嵌套的链表节点，直到遍历完整个链表。
#define hlist_for_each_entry(pos, head, member) \
for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member); \
pos; \
pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
hlist_entry 和 hlist_entry_safe 解释
在 Linux 内核中，hlist_entry 和 hlist_entry_safe 是常用的宏，用于将哈希链表节点（hlist_node）指针转换为包含该节点的结构体指针。哈希链表节点通常是结构体中的一部分，使用这些宏可以便捷地访问和操作链表中的结构体。类似链表的list_entry
hlist_entry 宏用于将 hlist_node 指针（通常是链表节点）转换为包含它的结构体指针。它的定义如下：
#define hlist_entry(ptr, type, member) container_of(ptr, type, member)
ptr：传入的指向链表节点（hlist_node）的指针。type：目标结构体的类型，通常是链表中包含hlist_node的结构体类型。member：指向hlist_node的结构体成员名。
container_of 是一个常见的宏，用于从结构体的成员获取包含该成员的结构体指针。hlist_entry 通过 container_of 实现了这个功能。
示例：
假设有以下结构体定义，其中 hlist_node 是结构体 my_struct 的一部分：
struct my_struct {
int value;
struct hlist_node node; // 链表节点
};
如果我们有一个指向 hlist_node 类型的指针 pos，我们可以使用 hlist_entry 将其转换为指向 my_struct 类型的指针：
struct my_struct *entry = hlist_entry(pos, struct my_struct, node);
这段代码的作用是：通过链表节点 pos，获取到包含该节点的结构体 my_struct 的指针 entry。
hlist_entry_safe 宏是在 hlist_entry 的基础上加了一些安全检查，以防传入 NULL 指针。在某些情况下，传入的 ptr 可能是 NULL，此时使用 hlist_entry 会导致未定义的行为。hlist_entry_safe 通过增加 NULL 检查来避免这种情况。
小结：
hlist_for_each是最简单的遍历方式，适用于不需要删除节点的情况。hlist_for_each_safe是安全遍历方式，避免在遍历过程中修改链表时出错，常用于需要删除节点的场景。hlist_for_each_entry则适用于结构体中嵌套链表节点的遍历，通常在哈希表中每个元素本身是结构体时使用。
6. 结语
6.1 总结学到的知识点
通过本文的学习，你应该掌握了Linux内核中的哈希表的使用方法，包括哈希表的定义、操作、性能优化等方面。哈希表作为内核中的一种高效数据结构，在多个子系统中发挥着重要作用。
6.2 进一步学习资源推荐
- Linux内核源代码
- 《Linux Device Drivers》by Jonathan Corbet
- 《Linux内核设计与实现》by Robert Love
- 在线资源：Kernel Newbies, LWN.net
通过进一步的实践和学习，你可以更深入地理解Linux内核的工作原理，并提升自己的内核编程技能。
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
23
0- 0
已为社区贡献17条内容
所有评论(0)