c - 如何使用内核哈希表 API?
问题描述
我正在尝试理解和使用内核哈希表,我已经阅读了这个和这个链接,但我一个都不理解。我的第一个问题是:为什么我们的结构必须有struct h_list
它的内部?如果我们要通过我们的结构访问我们的struct h_list
结构不应该在内部struct h_list
而不是相反?阅读教程后,我尝试编写以下代码:
DECLARE_HASHTABLE(nodes_hash, 3)
hash_init(nodes_hash);
struct h_node{
int data;
char name[MAX_NAME_SIZE]; /*The key is the name of lua state*/
struct hlist_node node;
};
struct h_node a = {
.data = 3,
.name = "foo",
.node = 0
};
struct h_node b = {
.data = 7,
.name = "bar",
.node = 0
};
hash_add(nodes_hash,&a.node, "foo");
hash_add(nodes_hash,&b.node, "bar");
但这甚至无法编译。我做错了什么?我需要密钥与struct h_node
. 所以我希望我的哈希表是这样的:
PS:在我的哈希表中它永远不会发生冲突(我会处理它永远不会发生)所以键可以是struct h_node
解决方案
为什么我们的结构必须有
struct h_list
它的内部?如果我们要通过我们的结构访问我们的struct h_list
结构不应该在内部struct h_list
而不是相反?
那是因为哈希表是如何在 Linux 内核中实现的。哈希表只是一个固定大小的数组struct hlist_head
。每一个都代表一个桶,并且是链表的头部。哈希表只包含一堆 的链表struct hlist_node
,没有别的。它并没有真正“存储”整个用户定义的结构,它只是保存一个指向struct hlist_node
每个元素的字段的指针。
当您将元素添加到哈希表时,将选择一个存储桶,并将指向struct hlist_node
您的结构字段的指针插入到存储桶列表中。当您稍后检索元素时(例如通过hash_for_each()
),container_of()
宏用于获取您的真实结构,知道它的类型和struct hlist_node
用户定义结构中类型的结构成员的名称。
这可以在源代码之后看到。例如,因为hash_for_each()
我们有:
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)
-
for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ pos; \ pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
-
({ typeof(ptr) ____ptr = (ptr); \ ____ptr ? hlist_entry(____ptr, type, member) : NULL; \ })
最后
hlist_entry()
用于container_of()
获取真正的结构:#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
我需要密钥与
struct h_node
.
这在本地是不可能的。Linux 内核哈希表 API 仅处理整数键。如果您查看 中的实现linux/hashtable.h
,您会看到使用的哈希函数是hash_32()
和hash_64()
,它们都采用无符号整数值(分别为u32
和u64
)。
Linux 内核哈希表 API 非常有限,它绝对不会实现您在其他编程语言中使用的那种哈希表。它不能使用字符串作为键,并且它具有固定的大小。
如果要使用字符串,则必须对这些字符串进行散列以生成无符号整数。为此,您可以使用xxhash()
或编写自己的函数。该xxhash()
功能相对较新,似乎尚未在内核代码中使用,因此我认为您的内核很可能是在没有它的情况下配置的,而您没有它可用。
无论如何,请注意如果哈希函数将不同的字符串转换为相同的键,或者如果hash_add()
最终选择哈希表数组中的相同索引来插入元素,那么这两个元素将被放置在同一个哈希表桶中。因此,在检索任何元素时(例如使用hash_for_each_possible()
),您需要考虑到这一点并正确检查其name
.
工作示例
这是一个完整的工作示例,用于演示内核哈希表的基本用法,在内核 v4.9 上进行了测试,但也应该在最新的 v5.7 上工作。请注意,在此示例中,为了简单起见,我将变量分配到模块_init
函数的堆栈中。这意味着除了从该函数内部之外,我无法hash_for_each_possible()
从代码中的其他任何地方执行操作。如果您想要一个能够保存稍后由不同函数访问的元素的全局哈希表,则需要使用kmalloc()
.
// SPDX-License-Identifier: GPL-3.0
#include <linux/hashtable.h> // hashtable API
#include <linux/module.h> // module_{init,exit}, MODULE_*
#include <linux/string.h> // strcpy, strcmp
#include <linux/types.h> // u32 etc.
#define MAX 32
struct h_node {
int data;
char name[MAX];
struct hlist_node node;
};
DECLARE_HASHTABLE(tbl, 3);
// Just to demonstrate the behavior when two keys are equal.
static u32 myhash(const char *s) {
u32 key = 0;
char c;
while ((c = *s++))
key += c;
return key;
}
static int __init myhashtable_init(void)
{
struct h_node a, b, *cur;
u32 key_a, key_b;
unsigned bkt;
pr_info("myhashtable: module loaded\n");
a.data = 3;
strcpy(a.name, "foo");
b.data = 7;
strcpy(b.name, "oof");
/* Calculate key for each element.
* Since the above hash function only sums the characters, we will
* end up having two identical keys here.
*/
key_a = myhash(a.name);
key_b = myhash(b.name);
pr_info("myhashtable: key_a = %u, key_b = %u\n", key_a, key_b);
// Initialize the hashtable.
hash_init(tbl);
// Insert the elements.
hash_add(tbl, &a.node, key_a);
hash_add(tbl, &b.node, key_b);
// List all elements in the table.
hash_for_each(tbl, bkt, cur, node) {
pr_info("myhashtable: element: data = %d, name = %s\n",
cur->data, cur->name);
}
// Get the element with name = "foo".
hash_for_each_possible(tbl, cur, node, key_a) {
pr_info("myhashtable: match for key %u: data = %d, name = %s\n",
key_a, cur->data, cur->name);
// Check the name.
if (!strcmp(cur->name, "foo")) {
pr_info("myhashtable: element named \"foo\" found!\n");
break;
}
}
// Remove elements.
hash_del(&a.node);
hash_del(&b.node);
return 0;
}
static void __exit myhashtable_exit(void)
{
// Do nothing (needed to be able to unload the module).
pr_info("myhashtable: module unloaded\n");
}
module_init(myhashtable_init);
module_exit(myhashtable_exit);
MODULE_VERSION("0.1");
MODULE_DESCRIPTION("Silly kernel hashtable API example module.");
MODULE_AUTHOR("Marco Bonelli");
MODULE_LICENSE("GPL");
dmesg
我机器上的输出:
[ 3174.567029] myhashtable: key_a = 324, key_b = 324
[ 3174.567030] myhashtable: element: data = 7, name = oof
[ 3174.567031] myhashtable: element: data = 3, name = foo
[ 3174.567032] myhashtable: match for key 324: data = 7, name = oof
[ 3174.567033] myhashtable: match for key 324: data = 3, name = foo
[ 3174.567033] myhashtable: element named "foo" found!
推荐阅读
- python - 用于相交列列表的一致 ColumnTransformer
- java - 错误 java.lang.OutOfMemoryError:Java 堆空间
- angular - Angular5csv Jasmine 单元测试
- javascript - Javascript在剪贴板变量中包含双引号
- rust - 为什么 `get` 对 std::vec::Vec 和 &std::vec::Vec 都有效?
- javascript - Highcharts 忽略跳过的日期
- java - 如何使用 Java 中的函数列表来比较两个对象的字段并求和结果
- mysql - SQL HELP:如何将两个不同的行加在一起作为一个值?
- javascript - Express 没有正确遵循 server.js 规范
- node.js - async.series() 中的 Promise.resolve