Почему в нашей структуре должен быть struct h_list? Если мы хотим получить доступ к нашей структуре через struct h_list, наша структура не должна быть в пределах struct h_list, а не наоборот?
Это потому, что в * реализованы таблицы sh в Linux ядро. Хеш-таблица - это просто массив фиксированного размера struct hlist_head. Каждый из них представляет собой bucked и является заголовком связанного списка. Хеш-таблица содержит только несколько связанных списков 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)
hlist_for_each_entry() делает:
for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\
pos; \
pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
hlist_entry_safe() делает:
({ 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.
Это невозможно изначально. API хеш-таблицы ядра Linux работает только с целочисленными ключами. Если вы посмотрите на реализацию в linux/hashtable.h, вы увидите, что используются функции ha sh: hash_32() и hash_64(), и они оба принимают целочисленные значения без знака (u32 и u64 соответственно).
API-интерфейс хеш-таблицы ядра Linux очень ограничен, и он определенно не реализует тот же тип hashtable, к которому вы привыкли в других языках программирования. Он не может использовать строки в качестве ключей и имеет фиксированный размер.
Если вы хотите использовать строки, вам придется иметь sh эти строки для генерации целого числа без знака. Для этого вы можете использовать xxhash() или написать собственную функцию. Функция xxhash() является относительно новой и, похоже, еще не используется в коде ядра, поэтому я думаю, что ваше ядро, скорее всего, было настроено без нее, и у вас ее нет.
В любом случае, имейте в виду, что если функция ha sh преобразует различные строки в ту же самую клавишу , или если hash_add() заканчивает выбор того же индекса в массиве хеш-таблиц для вставки элементов, то два элемента будут помещены в одну и ту же корзину Поэтому при извлечении любого элемента (используя, например, hash_for_each_possible()) вам необходимо , чтобы принять это во внимание и правильно проверить его name.
Вот полный рабочий пример. Обратите внимание, что в этом примере я размещаю переменные в стеке функции модуля _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);
// Insert elements.
hash_init(tbl);
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!