linux 内核 hlist 哈希表 详细介绍

作者

hlist 解析

hlist (Hashed List 或 Headless List) 是 Linux 内核中一种特殊的双向链表。它的设计初衷是为了在哈希表（Hash Table）场景下，以更节省内存的方式存储链表。

我们先来思考一个问题：为什么不直接用内核中最常见的标准双向循环链表 list_head 来构建哈希表呢？

一个典型的哈希表示意图如下：

  Hash Table Array
+---+
| 0 | --> Node1 -> Node2 -> NULL
+---+
| 1 | --> NULL (empty)
+---+
| 2 | --> Node3 -> NULL
+---+
  ...
| N | --> Node4 -> Node5 -> Node6 -> NULL
+---+

这个哈希表由一个数组构成，每个数组元素（称为“桶”或“bucket”）是一个链表的头。如果使用标准的 list_head，每个桶的头部结构如下：

struct list_head {
    struct list_head *next, *prev;
};

这意味着，即使一个桶是空的，它也需要占用两个指针（next 和 prev）的空间。在一个大型哈希表（例如，有成千上万个桶）中，大部分桶可能都是空的，这会造成巨大的内存浪费。

hlist 就是为了解决这个问题而生的。

1. hlist 如何实现的 (Implementation)

hlist 的精髓在于它重新设计了链表头和节点的结构，特别是对链表头进行了极致的优化。

数据结构定义

hlist 涉及两个核心结构，定义在 <linux/hlist.h> 中：

  1. struct hlist_head: 链表头结构。 struct hlist_head { struct hlist_node *first; };
    • 特点：它只有一个指向链表第一个节点的指针 first。相比 list_head，它节省了一半的内存空间。当桶为空时，first 指针为 NULL。
  2. struct hlist_node: 链表节点结构。
    c struct hlist_node { struct hlist_node *next; struct hlist_node **pprev; };
    • next: 和普通链表一样，指向下一个节点。
    • pprev: 这是 hlist 设计的灵魂所在。它是一个指向指针的指针（pointer to a pointer）。它的值不是前一个节点的地址，而是指向前一个节点中 next 指针的地址，或者是指向链表头 hlist_head 中 first 指针的地址。

图示理解 pprev

让我们通过一个直观的图示来理解 pprev 的精妙之处。

假设我们有一个 hlist_head 和三个链接的 hlist_node：

+---------------+      +----------------+      +----------------+      +----------------+
|  hlist_head   |      |   hlist_node A |      |   hlist_node B |      |   hlist_node C |
|---------------|      |----------------|      |----------------|      |----------------|
| *first  ------+----->| *next   -------+----->| *next   -------+----->| *next  (NULL)  |
+---------------+      | **pprev -------+-----| **pprev -------+-----| **pprev -------+
                       +----------------+      +----------------+      +----------------+

现在，我们来看 pprev 到底指向哪里：

详细解释：

  1. 节点 A (第一个节点):
    • A->next 指向节点 B。
    • A->pprev 指向 hlist_head 结构体中的 first 成员。即 A->pprev 的值是 &hlist_head.first。
  2. 节点 B (中间节点):
    • B->next 指向节点 C。
    • B->pprev 指向节点 A 结构体中的 next 成员。即 B->pprev 的值是 &A->next。
  3. 节点 C (末尾节点):
    • C->next 是 NULL。
    • C->pprev 指向节点 B 结构体中的 next 成员。即 C->pprev 的值是 &B->next。

为什么这样设计？——为了高效删除

这个 pprev 的设计使得删除任何一个节点都变得非常高效（O(1) 时间复杂度），且无需知道其前驱节点的完整结构体。

假设我们要删除节点 B：

  1. 我们只需要一个指向节点 B 的指针 node_b。
  2. 获取 B 的前一个指针：*(node_b->pprev)。这个表达式解引用后就是 A->next。
  3. 将其指向 B 的下一个节点：*(node_b->pprev) = node_b->next; 这就等价于 A->next = C;，从而将 B 从链表中摘除。
  4. 如果 B 后面还有节点 C，我们还需要更新 C 的 pprev：if (node_b->next) { node_b->next->pprev = node_b->pprev; } 这就等价于 C->pprev = &A->next;。

整个删除过程只依赖于待删除节点本身和其后继节点，非常简洁高效。

2. hlist 的使用场景 (Use Cases)

hlist 的核心应用场景就是哈希表。凡是内核中需要用到哈希表的地方，几乎都能看到 hlist 的身影。

主要优点：

  • 节省内存：对于哈希表的桶数组，使用 hlist_head 比 list_head 节省 50% 的内存。在 64 位系统上，每个空桶只占用 8 字节而不是 16 字节。当哈希表非常大时，这个优势极为明显。
  • 高效操作：添加（通常是头插法）和删除都是 O(1) 操作。

典型内核实例：

  1. Dentry Cache (dcache): 内核使用一个名为 d_hash 的哈希表来快速查找目录项（dentry）。每个 dentry 结构体中都包含一个 struct hlist_node d_u.d_alias 成员，用于挂载到这个哈希表中。这是 hlist 最经典的应用。
  2. Inode Cache: 类似地，内核也有一个哈希表来缓存活跃的 inode，加速文件系统的访问。
  3. PID 哈希表: 内核通过 PID（进程标识符）来快速定位 task_struct。它维护了几个基于 PID 的哈希表，这些表的实现也依赖于 hlist。
  4. 网络子系统: 在连接跟踪（conntrack）、邻居表（ARP cache）等许多网络数据结构中，都广泛使用 hlist 来构建哈希表以实现快速查找。

3. hlist 的操作接口 (API)

内核提供了一套完整的宏和内联函数来操作 hlist，都位于 <linux/hlist.h>。这些接口与 list_head 的接口非常相似。

初始化

  • HLIST_HEAD_INIT: 静态初始化一个 hlist_head。{ .first = NULL }
  • HLIST_HEAD(name): 定义并静态初始化一个名为 name 的 hlist_head。
  • INIT_HLIST_HEAD(ptr): 动态初始化一个 hlist_head。将 ptr->first 设为 NULL。
  • INIT_HLIST_NODE(ptr): 初始化一个 hlist_node。通常节点在被添加到链表前或从链表删除后，会用此函数进行初始化，便于调试和检查。

添加节点

  • hlist_add_head(n, h): 将节点 n 添加到头 h 指向的链表的头部。这是哈希表中最常用的插入方法（LIFO）。
  • hlist_add_before(n, next): 将节点 n 添加到 next 节点的前面。
  • hlist_add_after(n, prev): 将节点 n 添加到 prev 节点的后面。

删除节点

  • hlist_del(n): 从链表中删除节点 n。删除后，节点 n 的内容不会被清空，需要手动处理。
  • hlist_del_init(n): 从链表中删除节点 n，并立即调用 INIT_HLIST_NODE(n) 对其进行初始化。这是一个更安全的版本。

检查与遍历

  • hlist_empty(h): 检查头 h 指向的链表是否为空。
  • 遍历宏：
    • hlist_for_each(pos, h): 遍历链表，pos 是 struct hlist_node * 类型的游标。
    • hlist_for_each_safe(pos, n, h): 安全版本的遍历。在遍历过程中如果需要删除当前节点 pos，必须使用此宏。n 是一个临时 hlist_node 指针，用于保存下一个节点，防止删除 pos 后链表断裂。
    • hlist_for_each_entry(pos, h, member): 这是最常用的遍历宏。它不是遍历节点本身，而是遍历包含该节点的父结构体。
      • pos: 用户定义的、指向父结构体的指针。
      • h: hlist_head 指针。
      • member: hlist_node 在父结构体中的成员名。
    • hlist_for_each_entry_safe(pos, n, h, member): hlist_for_each_entry 的安全版本。

示例代码

假设我们有一个自定义结构体，并用 hlist 将它们组织成一个哈希表。

#include <linux/hlist.h>
#include <linux/stddef.h> // for container_of

// 自定义数据结构
struct my_object {
    int id;
    struct hlist_node hash_node; // 内嵌的 hlist 节点
};

// 假设我们有一个哈希表
#define HASH_TABLE_SIZE 16
static HLIST_HEAD(my_hash_table[HASH_TABLE_SIZE]);

// 计算哈希值的简单函数
static inline int my_hash_func(int id) {
    return id % HASH_TABLE_SIZE;
}

void add_to_my_table(struct my_object *obj) {
    int bucket = my_hash_func(obj->id);
    hlist_add_head(&obj->hash_node, &my_hash_table[bucket]);
}

struct my_object *find_in_my_table(int id) {
    int bucket = my_hash_func(id);
    struct my_object *obj;

    // 使用 hlist_for_each_entry 遍历特定桶
    hlist_for_each_entry(obj, &my_hash_table[bucket], hash_node) {
        if (obj->id == id) {
            return obj; // 找到了
        }
    }
    return NULL; // 未找到
}

4. hlist vs list_head 对比总结

特性 (Feature)hlist (hlist_head / hlist_node)list_head
头部结构struct { struct hlist_node *first; } (单指针)struct { struct list_head *next, *prev; } (双指针)
节点结构struct { struct hlist_node *next, **pprev; }struct { struct list_head *next, *prev; }
头部内存开销小 (一个指针大小)较大 (两个指针大小)
擅长场景哈希表通用的双向循环链表，如任务队列、设备列表等
链表类型单向（头 -> 尾），但可高效删除（伪双向）双向循环链表
从尾部添加不支持直接从尾部添加（需要遍历整个链表）O(1) 操作，因为有 prev 指针指向尾部
删除操作O(1)，依赖 pprev 指针O(1)，依赖 prev 和 next 指针

总结

hlist 是 Linux 内核中一个为了特定场景（哈希表）而精心优化的数据结构。它通过巧妙地使用指向指针的指针 pprev，在显著减少链表头内存占用的同时，保留了 O(1) 时间复杂度的节点插入（头部）和删除能力

本文版权归原作者zhaofujian所有，采用 CC BY-NC-ND 4.0 协议进行许可，转载请注明出处。

发表评论