时间轴

2026-05-24

init

概述

Linux 内核中定义了大量的通用数据结构，这些结构贯穿于进程调度、内存管理、文件系统、设备驱动等各个子系统。本文按实际使用频率从高到低梳理这些数据结构，涵盖数据结构定义、核心 API 及典型使用场景。

本文基于 Linux 6.x 内核，部分 API 在不同版本间可能略有差异。

基础容器

list_head — 双向循环链表

使用频率：最高。 这是 Linux 内核中使用最广泛的数据结构，没有之一。几乎每个子系统都会用到它。

Linux 的链表实现将数据与链表节点分离，链表节点嵌入到结构体中，而非结构体包含链表指针。这种设计的精髓在于：一套链表操作适用于所有数据类型。

头文件： <linux/list.h>

数据结构：

1
2
3
struct list_head {
    struct list_head *next, *prev;
};

核心 API：

API 说明
LIST_HEAD(name) 静态定义并初始化一个链表头
INIT_LIST_HEAD(ptr) 动态初始化链表头
list_add(new, head) 在 head 之后插入
list_add_tail(new, head) 在 head 之前插入（尾部）
list_del(entry) 删除节点
list_del_init(entry) 删除并重新初始化节点
list_empty(head) 判断链表是否为空
list_entry(ptr, type, member) 从 list_head 指针获取包含它的结构体
list_for_each(pos, head) 遍历链表
list_for_each_entry(pos, head, member) 遍历链表并获取宿主结构体
list_for_each_entry_safe(pos, n, head, member) 安全遍历（可在遍历时删除）
list_move(list, head) 移动节点到新链表
list_splice(list, head) 合并两个链表

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/list.h>

#define CNT 10

struct my_data {
        int val;
        struct list_head list;
};

// 定义链表头
LIST_HEAD(my_list);

static int __init list_test_init(void)
{
        int i, ret = 0;
        struct my_data *entry, *tmp;

        pr_info("%s is called\n", __func__);

        for (i = 0; i < CNT; i++) {
                entry = kzalloc(sizeof(*entry), GFP_KERNEL);
                if (!entry) {
                        ret = -ENOMEM;
                        goto cleanup;
                }

                entry->val = i * 2;
                INIT_LIST_HEAD(&entry->list); // 初始化链表节点
                list_add_tail(&entry->list, &my_list); // 将链表添加到尾部
        }

        list_for_each_entry(entry, &my_list, list)
        {
                pr_info("val is %d\n", entry->val);
        }

        return ret;
cleanup:
        list_for_each_entry_safe(entry, tmp, &my_list, list)
        {
                list_del(&entry->list);
                kfree(entry);
        }
        return ret;
}

static void __exit list_test_exit(void)
{
        struct my_data *entry, *tmp;

        list_for_each_entry_safe(entry, tmp, &my_list, list)
        {
                pr_info("del %d\n", entry->val);
                list_del(&entry->list);
                kfree(entry);
        }
        pr_info("%s is called\n", __func__);
}

module_init(list_test_init);
module_exit(list_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("zhaohang");
MODULE_DESCRIPTION("A test sample for linux link list");

运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
~ # insmod list_test.ko
[   11.039661] list_test: loading out-of-tree module taints kernel.
[   11.050065] list_test_init is called
[   11.050235] val is 0
[   11.050289] val is 2
[   11.050325] val is 4
[   11.050390] val is 6
[   11.050429] val is 8
[   11.050466] val is 10
[   11.050734] val is 12
[   11.050808] val is 14
[   11.050885] val is 16
[   11.050936] val is 18
~ # rmmod list_test.ko
[   17.474727] del 0
[   17.474865] del 2
[   17.474913] del 4
[   17.474950] del 6
[   17.474981] del 8
[   17.475060] del 10
[   17.475103] del 12
[   17.475135] del 14
[   17.475169] del 16
[   17.475221] del 18
[   17.475263] list_test_exit is called

list_add 和 list_add_tail:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}


/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

list_add_tail是被插入到了head—>prev和head之间。但因为这是一个环，“head 的前面” 在逻辑上就等于 “链表的末尾”。

list_del 和 list_del_init 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}


/**
 * list_del_init - deletes entry from list and reinitialize it.
 * @entry: the element to delete from the list.
 */
static inline void list_del_init(struct list_head *entry)
{
	__list_del_entry(entry);
	INIT_LIST_HEAD(entry);
}

list_replace 可以替换一个链表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * list_replace - replace old entry by new one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * If @old was empty, it will be overwritten.
 */
static inline void list_replace(struct list_head *old,
				struct list_head *new)
{
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}

/**
 * list_replace_init - replace old entry by new one and initialize the old one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * If @old was empty, it will be overwritten.
 */
static inline void list_replace_init(struct list_head *old,
				     struct list_head *new)
{
	list_replace(old, new);
	INIT_LIST_HEAD(old);
}

hlist — 哈希链表

hlist 是专门为哈希表设计的双向链表变体。就是说在对需要存储的数据进行hash时，如果产生了冲突，就使用链表的方式将产生冲突的数据进行存储。通常情况下，哈希表中元素的使用顺序是：数据存储—>数据获取—>数据删除。与 list_head 的区别在于：头节点只用一个 struct hlist_head（单指针），节省哈希表数组的内存。

它的核心设计动机是为了解决标准双向循环链表 list_head 在作为哈希桶（Hash Bucket）使用时存在的内存浪费和语义不匹配问题。

特性 list_head (标准链表) hlist_head + hlist_node (哈希链表)
头节点结构 完整的双向指针 (next, prev) 仅一个单向指针 (first)
数据节点结构 双向指针 (next, prev) 双向指针 (next, pprev)
是否循环 是（头尾相连） 否（以 NULL 结尾）
空链表判断 head->next == head head->first == NULL
内存开销(头节点) 2个指针 (16字节/64位) 1个指针 (8字节/64位)

头文件： <linux/list.h>

数据结构：

1
2
3
4
5
6
7
struct hlist_head {
    struct hlist_node *first;  // 只有一个指针！
};

struct hlist_node {
    struct hlist_node *next, **pprev;  // pprev 指向前一个节点的 next 指针
};

pprev 的类型是 struct hlist_node **（指向指针的指针）。它存储的不是"前一个节点的地址"，而是 “前一个节点中 next 字段的内存地址”。

对于hlist链 head -> A -> B

  • 对于链表中间的节点 B：B->pprev == &(A->next)
  • 对于链表的节点 A：A->pprev == &(head->first)

这样设计便于删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
static inline void __hlist_del(struct hlist_node *n)
{
	struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;

	WRITE_ONCE(*pprev, next);
	if (next)
		WRITE_ONCE(next->pprev, pprev);
}

/**
 * hlist_del - Delete the specified hlist_node from its list
 * @n: Node to delete.
 *
 * Note that this function leaves the node in hashed state.  Use
 * hlist_del_init() or similar instead to unhash @n.
 */
static inline void hlist_del(struct hlist_node *n)
{
	__hlist_del(n);
	n->next = LIST_POISON1;
	n->pprev = LIST_POISON2;
}

/**
 * hlist_del_init - Delete the specified hlist_node from its list and initialize
 * @n: Node to delete.
 *
 * Note that this function leaves the node in unhashed state.
 */
static inline void hlist_del_init(struct hlist_node *n)
{
	if (!hlist_unhashed(n)) {
		__hlist_del(n);
		INIT_HLIST_NODE(n);
	}
}

add相关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * hlist_add_head - add a new entry at the beginning of the hlist
 * @n: new entry to be added
 * @h: hlist head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;
	WRITE_ONCE(n->next, first);
	if (first)
		WRITE_ONCE(first->pprev, &n->next);
	WRITE_ONCE(h->first, n);
	WRITE_ONCE(n->pprev, &h->first);
}

/**
 * hlist_add_before - add a new entry before the one specified
 * @n: new entry to be added
 * @next: hlist node to add it before, which must be non-NULL
 */
static inline void hlist_add_before(struct hlist_node *n,
				    struct hlist_node *next)
{
	WRITE_ONCE(n->pprev, next->pprev);
	WRITE_ONCE(n->next, next);
	WRITE_ONCE(next->pprev, &n->next);
	WRITE_ONCE(*(n->pprev), n);
}

/**
 * hlist_add_behing - add a new entry after the one specified
 * @n: new entry to be added
 * @prev: hlist node to add it after, which must be non-NULL
 */
static inline void hlist_add_behind(struct hlist_node *n,
				    struct hlist_node *prev)
{
	WRITE_ONCE(n->next, prev->next);
	WRITE_ONCE(prev->next, n);
	WRITE_ONCE(n->pprev, &prev->next);

	if (n->next)
		WRITE_ONCE(n->next->pprev, &n->next);
}

/**
 * hlist_add_fake - create a fake hlist consisting of a single headless node
 * @n: Node to make a fake list out of
 *
 * This makes @n appear to be its own predecessor on a headless hlist.
 * The point of this is to allow things like hlist_del() to work correctly
 * in cases where there is no list.
 */
static inline void hlist_add_fake(struct hlist_node *n)
{
	n->pprev = &n->next;
}

/**
 * hlist_fake: Is this node a fake hlist?
 * @h: Node to check for being a self-referential fake hlist.
 */
static inline bool hlist_fake(struct hlist_node *h)
{
	return h->pprev == &h->next;
}

rbtree — 红黑树

内核中使用最多的自平衡二叉搜索树，提供 O(log n) 的查找、插入和删除。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树的特性:

  • 每个节点或者是黑色，或者是红色。
  • 根节点是黑色。
  • 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL 或 NULL)的叶子节点！]
  • 如果一个节点是红色的，则它的子节点必须是黑色的。
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。此特性确保没有一条路径会比其他路径长出两倍，因而，红黑树是相对是接近平衡的二叉树。

对红黑树的所有操作都要保持红黑树的特性不变，红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。cfs_rq就是使用红黑树存储任务的。

头文件： <linux/rbtree.h> / <linux/rbtree_augmented.h>

数据结构：

1
2
3
4
5
6
7
8
9
10
struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root {
	struct rb_node *rb_node;
};

粗略一看，这里似乎没有定义颜色的域，但这就是这里红黑树实现的一个巧妙的地方。__rb_parent_color这个域其实同时包含了颜色信息以及父亲节点的指针，因为该域是一个long的类型，需要大小为sizeof(long)的对齐，那么在一般的32位机器上，其后两位的数值永远是0，于是可以拿其中的一位来表示颜色。

关键在于 内存对齐（Alignment）：

  • struct rb_node 被强制要求按 sizeof(long) 对齐。
  • 在 32 位系统上，sizeof(long) == 4，意味着任何合法的 rb_node 指针地址必然是 4 的倍数，即二进制最低 2 位 永远为 00。
  • 在 64 位系统上，sizeof(long) == 8，最低 3 位 永远为 000。

事实上，这里就是使用了最低位来表示颜色信息。以下关于父亲指针和颜色信息的操作其本质上都是对rb_parent_color的位进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

#define RB_ROOT	(struct rb_root) { NULL, }
#define	rb_entry(ptr, type, member) container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)

/* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
#define RB_EMPTY_NODE(node)  \
	((node)->__rb_parent_color == (unsigned long)(node))
#define RB_CLEAR_NODE(node)  \
	((node)->__rb_parent_color = (unsigned long)(node))

Linux的红黑树实现对速度进行了优化，因此比传统的实现少一个间接层（有更好的缓存局部性）。 每个struct rb_node结构体的实例嵌入在它管理的数据结构中，因此不需要靠指针来分离rb_node和它 管理的数据结构。

  • 用户应该编写他们自己的树搜索和插入函数，来调用已提供的红黑树函数， 而不是使用一个比较回调函数指针。

  • 加锁代码也留给红黑树的用户编写。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
// SPDX-License-Identifier: GPL-2.0
/*
 * rbtree_demo.c - Linux 5.10.x Red-Black Tree Module Demo
 * 演示: 插入、查找、删除、顺序遍历、逆序遍历、获取首尾节点
 */
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/rbtree.h>
#include <linux/slab.h>
#include <linux/random.h>

/* ========== 1. 定义包含 rb_node 的自定义结构体 ========== */
struct my_node {
        struct rb_node rb; /* 必须作为成员嵌入，通常放在开头或任意位置 */
        unsigned long data; /* 数据 */
};

/* 全局红黑树根节点 */
static struct rb_root my_tree = RB_ROOT;

/* ========== 2. 辅助宏：从 rb_node 反查宿主结构体 ========== */
#define rb_entry_my(ptr) rb_entry((ptr), struct my_node, rb)

/* ========== 3. 核心操作封装 ========== */

/**
 * 查找节点 - O(log n)
 */
static struct my_node *my_rb_search(struct rb_root *root, unsigned long data)
{
        struct rb_node *node = root->rb_node;

        while (node) {
                struct my_node *entry = rb_entry_my(node);

                if (data < entry->data) // 当前节点大于要找到的key，往左子树走
                        node = node->rb_left;
                else if (data > entry->data) // 当前节点小于要找到的key，往右走
                        node = node->rb_right;
                else
                        return entry; /* 找到 */
        }
        return NULL; /* 未找到 */
}

/**
 * 插入节点 - O(log n)
 * 返回: true=新插入, false=key已存在(未插入)
 *
 * 【关键】Linux 5.10.x 使用两步法:
 *   1) rb_link_node()  : 将节点链接到父节点下（不着色）
 *   2) rb_insert_color(): 修复红黑树性质（旋转+变色）
 */
static bool my_rb_insert(struct rb_root *root, struct my_node *new_node)
{
        struct rb_node **link = &root->rb_node; // 要找到的插入位置
        struct rb_node *parent = NULL;
        unsigned long data = new_node->data;

        /* 第一步：标准BST查找插入位置 */
        while (*link) {
                struct my_node *entry = rb_entry_my(*link);
                parent = *link;

                if (data < entry->data)
                        link = &(*link)->rb_left;
                else if (data > entry->data)
                        link = &(*link)->rb_right;
                else
                        return false; /* key 已存在，不重复插入 */
        }

        /* 第二步：链接并着色 */
        rb_link_node(&new_node->rb, parent, link);
        rb_insert_color(&new_node->rb, root);
        return true;
}

/**
 * 删除节点 - O(log n)
 */
static void my_rb_erase(struct rb_root *root, struct my_node *node)
{
        rb_erase(&node->rb, root);
        kfree(node);
}

/**
 * 销毁整棵树
 */
static void my_rb_destroy(struct rb_root *root)
{
        struct rb_node *node;
        /* postorder 方式安全释放，避免访问已释放的子节点 */
        while ((node = rb_first_postorder(root))) {
                rb_erase(node, root);
                kfree(rb_entry_my(node));
        }
        *root = RB_ROOT;
}

/* ========== 4. 模块初始化：批量插入 + 验证 ========== */
static int __init rbtree_demo_init(void)
{
        int i;
        unsigned long keys[] = { 1, 2, 3, 4, 5, 6, 7 };
        int count = ARRAY_SIZE(keys);

        pr_info("rbtree_demo: === Module Loaded ===\n");

        /* --- 插入测试 --- */
        for (i = 0; i < count; i++) {
                struct my_node *node = kzalloc(sizeof(*node), GFP_KERNEL);
                if (!node)
                        return -ENOMEM;

                node->data = keys[i];

                if (my_rb_insert(&my_tree, node))
                        pr_info("rbtree_demo: INSERT data=%lu OK\n", keys[i]);
                else {
                        pr_warn("rbtree_demo: INSERT data=%lu DUPLICATE\n", keys[i]);
                        kfree(node);
                }
        }

        /* --- 查找测试 --- */
        {
                struct my_node *found = my_rb_search(&my_tree, 4);
                if (found)
                        pr_info("rbtree_demo: SEARCH data=4 => %lu\n", found->data);
                else
                        pr_warn("rbtree_demo: SEARCH data=4 => Not Found\n");
                

                found = my_rb_search(&my_tree, 666);
                if (found)
                        pr_info("rbtree_demo: SEARCH data=99 => %lu\n", found->data);
                else
                        pr_warn("rbtree_demo: SEARCH data=99 => Not Found\n");
        }

        /* --- 正序遍历 (in-order) --- */
        pr_info("rbtree_demo: IN-ORDER TRAVERSAL:\n");
        {
                struct rb_node *node;
                for (node = rb_first(&my_tree); node; node = rb_next(node)) {
                        struct my_node *entry = rb_entry_my(node);
                        pr_info("       data=%lu\n", entry->data);
                }
        }

        /* --- 逆序遍历 --- */
        pr_info("rbtree_demo: REVERSE TRAVERSAL:\n");
        {
                struct rb_node *node;
                for (node = rb_last(&my_tree); node; node = rb_prev(node)) {
                        struct my_node *entry = rb_entry_my(node);
                        pr_info("       data=%lu\n", entry->data);
                }
        }

        /* --- 获取最小/最大节点 --- */
        {
                struct my_node *min = rb_entry_my(rb_first(&my_tree));
                struct my_node *max = rb_entry_my(rb_last(&my_tree));
                pr_info("rbtree_demo: MIN=%lu MAX=%lu\n", min->data, max->data);
        }

        /* --- 删除测试 --- */
        {
                struct my_node *to_del = my_rb_search(&my_tree, 4);
                if (to_del) {
                        pr_info("rbtree_demo: ERASE data=4\n");
                        my_rb_erase(&my_tree, to_del);
                }
        }

        /* 再次正序遍历确认删除结果 */
        pr_info("rbtree_demo: AFTER ERASE 30:\n");
        {
                struct rb_node *node;
                for (node = rb_first(&my_tree); node; node = rb_next(node)) {
                        struct my_node *entry = rb_entry_my(node);
                        pr_info("data=%lu\n", entry->data);
                }
        }

        return 0;
}

/* ========== 5. 模块卸载：清理所有资源 ========== */
static void __exit rbtree_demo_exit(void)
{
        my_rb_destroy(&my_tree);
        pr_info("rbtree_demo: === Module Unloaded ===\n");
}

module_init(rbtree_demo_init);
module_exit(rbtree_demo_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("Linux 5.10.x rbtree operations demo");

radix_tree — 基数树

xarray 的前身，用于整数 ID 到指针的映射。虽然 xarray 已逐步取代它，但内核中仍存在大量使用基数树的代码。

如果是新项目，请直接使用 <linux/xarray.h> 中的 XArray API。XArray 修复了 radix_tree 的诸多设计缺陷（如 preload 复杂性、索引偏移问题），且 API 更简洁。radix_tree 在 5.10.x 中仅是 XArray 上的兼容层。

头文件： <linux/radix-tree.h>

1
2
3
4
5
6
7
8
9
10
#define radix_tree_root		xarray
#define radix_tree_node		xa_node

struct radix_tree_preload {
	local_lock_t lock;
	unsigned nr;
	/* nodes->parent points to next preallocated node */
	struct radix_tree_node *nodes;
};
DECLARE_PER_CPU(struct radix_tree_preload, radix_tree_preloads);

可见linux-5.10.x中已经用xarray替代了它

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
// SPDX-License-Identifier: GPL-2.0
/*
 * radix_tree_demo.c - Linux 5.10.x Radix Tree Module Demo (Fixed)
 * 演示: 初始化、预加载、插入、查找、删除、标签(tag)操作、安全销毁
 */
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/radix-tree.h>
#include <linux/slab.h>
#include <linux/spinlock.h>
#include <linux/rcupdate.h>

/* 自定义存储的数据结构 */
struct my_data {
    unsigned long id;
    char name[32];
};

/* 全局 radix tree 及保护锁 */
static RADIX_TREE(my_rtree, GFP_ATOMIC);
static DEFINE_SPINLOCK(my_rtree_lock);

/* ========== 辅助函数 ========== */
static struct my_data *create_data(unsigned long id, const char *name)
{
    struct my_data *d = kmalloc(sizeof(*d), GFP_KERNEL);
    if (d) {
        d->id = id;
        strscpy(d->name, name, sizeof(d->name));
    }
    return d;
}

/* ========== 核心操作封装 ========== */

/**
 * 安全插入节点
 * 【关键】必须先 preload 再在锁内插入，避免持锁时触发睡眠分配导致死锁或 OOM
 */
static int safe_insert(unsigned long index, struct my_data *data)
{
    int ret;

    /* 预分配节点内存（允许睡眠） */
    ret = radix_tree_preload(GFP_KERNEL);
    if (ret)
        return ret;

    spin_lock(&my_rtree_lock);
    ret = radix_tree_insert(&my_rtree, index, data);
    spin_unlock(&my_rtree_lock);

    radix_tree_preload_end();
    return ret;
}

/**
 * 查找节点 - RCU 读侧安全
 */
static struct my_data *safe_lookup(unsigned long index)
{
    struct my_data *data;

    rcu_read_lock();
    data = radix_tree_lookup(&my_rtree, index);
    rcu_read_unlock();

    return data;
}

/**
 * 删除并释放节点
 */
static void safe_delete(unsigned long index)
{
    struct my_data *data;

    spin_lock(&my_rtree_lock);
    data = radix_tree_delete(&my_rtree, index);
    spin_unlock(&my_rtree_lock);

    kfree(data); /* delete 返回被移除的指针，由调用者负责释放 */
}

/**
 * 使用 Tag 批量标记和检索
 * 已修正：使用 struct radix_tree_iter 作为迭代器
 */
static void demo_tag_operations(void)
{
    struct my_data *d;
    void **slot;
    struct radix_tree_iter iter; /* 正确的迭代器类型 */

    pr_info("rtree_demo: === TAG Operations ===\n");

    /* 给 index=100 打上 tag 0 */
    spin_lock(&my_rtree_lock);
    radix_tree_tag_set(&my_rtree, 100, 0);
    spin_unlock(&my_rtree_lock);

    /* 通过 tag 批量检索 */
    rcu_read_lock();
    radix_tree_for_each_tagged(slot, &my_rtree, &iter, 0, 0) {
        d = radix_tree_deref_slot(slot);
        if (unlikely(radix_tree_deref_retry(d))) {
            slot = radix_tree_iter_retry(&iter); /* retry 传入 iter */
            continue;
        }
        if (d)
            pr_info("rtree_demo: TAGGED index=%lu name=%s\n",
                    iter.index, d->name); /* 从 iter.index 获取索引 */
    }
    rcu_read_unlock();
}

/* ========== 模块入口 ========== */
static int __init radix_tree_demo_init(void)
{
    struct my_data *d;
    int ret;

    pr_info("rtree_demo: === Module Loaded ===\n");

    /* RADIX_TREE() 宏已静态初始化，无需手动 INIT_RADIX_TREE */

    /* --- 插入测试 --- */
    d = create_data(42, "hello");
    ret = safe_insert(42, d);
    pr_info("rtree_demo: INSERT index=42 ret=%d\n", ret);

    d = create_data(100, "world");
    ret = safe_insert(100, d);
    pr_info("rtree_demo: INSERT index=100 ret=%d\n", ret);

    /* 测试重复插入 */
    d = create_data(42, "duplicate");
    ret = safe_insert(42, d);
    pr_info("rtree_demo: INSERT DUP index=42 ret=%d (expect -EEXIST)\n", ret);
    kfree(d); /* 重复插入失败，手动释放 */

    /* --- 查找测试 --- */
    d = safe_lookup(42);
    pr_info("rtree_demo: LOOKUP 42 => %s\n", d ? d->name : "NULL");

    d = safe_lookup(999);
    pr_info("rtree_demo: LOOKUP 999 => %s\n", d ? d->name : "NULL");

    /* --- Tag 测试 --- */
    demo_tag_operations();

    /* --- 删除测试 --- */
    safe_delete(42);
    d = safe_lookup(42);
    pr_info("rtree_demo: AFTER DELETE 42 => %s\n", d ? d->name : "NULL");

    return 0;
}

/* ========== 模块卸载：安全遍历并释放所有剩余节点 ========== */
static void __exit radix_tree_demo_exit(void)
{
    struct my_data *d;
    void **slot;
    struct radix_tree_iter iter; /* 正确的迭代器类型 */

    rcu_read_lock();
    radix_tree_for_each_slot(slot, &my_rtree, &iter, 0) {
        d = radix_tree_deref_slot(slot);
        if (unlikely(radix_tree_deref_retry(d))) {
            slot = radix_tree_iter_retry(&iter); /* retry 传入 iter */
            continue;
        }
        if (d) {
            /* 必须在锁内删除，且使用 iter.index */
            spin_lock(&my_rtree_lock);
            radix_tree_delete(&my_rtree, iter.index);
            spin_unlock(&my_rtree_lock);
            kfree(d);
        }
    }
    rcu_read_unlock();

    pr_info("rtree_demo: === Module Unloaded ===\n");
}

module_init(radix_tree_demo_init);
module_exit(radix_tree_demo_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("Linux 5.10.x radix_tree operations demo (fixed iterator)");

xarray — 可扩展数组

xarray 是 Linux 4.20 引入的新一代基数树（radix tree）替代品，提供从整数（unsigned long）到指针的映射，API 更简洁，性能更好。

头文件： <linux/xarray.h>

数据结构：

1
2
3
4
5
struct xarray {
    spinlock_t  xa_lock;
    gfp_t       xa_flags;
    void __rcu *xa_head;
};

核心 API：

API 说明
DEFINE_XARRAY(name) 静态定义 xarray
xa_init(xa) 动态初始化
xa_store(xa, index, entry, gfp) 存储条目
xa_load(xa, index) 读取条目
xa_erase(xa, index) 删除条目
xa_insert(xa, index, entry, gfp) 插入（key 不能已存在）
xa_for_each(xa, index, entry) 遍历所有条目
xa_find(xa, indexp, max, filter) 查找范围内的条目

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
DEFINE_XARRAY(my_xa);

// 存储
xa_store(&my_xa, 0, ptr1, GFP_KERNEL);
xa_store(&my_xa, 42, ptr2, GFP_KERNEL);

// 读取
void *p = xa_load(&my_xa, 42);

// 遍历
unsigned long index;
void *entry;
xa_for_each(&my_xa, index, entry) {
    pr_info("index=%lu, entry=%p\n", index, entry);
}

plist — 优先级链表

plist 在 list_head 基础上增加了优先级，表头始终指向优先级最高的节点（小的 prio 值代表高优先级），常用于需要"总是先处理最高优先级"的场景。

头文件： <linux/plist.h>

数据结构：

1
2
3
4
5
6
7
8
9
struct plist_node {
    int             prio;
    struct list_head    prio_list;  // 链接到同优先级的节点
    struct list_head    node_list;  // 总体链表
};

struct plist_head {
    struct list_head node_list;  // 所有节点按优先级排序
};

核心 API：

API 说明
plist_head_init(head) 初始化
plist_node_init(node, prio) 初始化节点
plist_add(node, head) 按优先级插入
plist_del(node, head) 删除节点
plist_first(head) 获取优先级最高的节点
plist_head_empty(head) 判断是否为空

llist — 无锁链表

llist（lock-less list）是一种无锁的单链表，基于 CAS 操作实现，在特定场景（如中断与进程共享数据）下比 spinlock + list_head 性能更好。

头文件： <linux/llist.h>

数据结构：

1
2
3
4
5
6
7
struct llist_head {
    struct llist_node *first;
};

struct llist_node {
    struct llist_node *next;
};

核心 API：

API 说明
llist_add(new, head) 头部插入（无锁）
llist_del_all(head) 原子地摘下整个链表
llist_del_first(head) 删除第一个节点
llist_empty(head) 判断是否为空

典型模式：

1
2
3
4
5
6
7
8
9
10
11
// 生产者（可在中断上下文）
struct llist_node *node = kmalloc(sizeof(*node), GFP_ATOMIC);
llist_add(node, &my_llist);

// 消费者（进程上下文）
struct llist_node *list = llist_del_all(&my_llist);  // 原子地取走整个链表
struct llist_node *entry, *tmp;
llist_for_each_entry_safe(entry, tmp, list) {
    process(entry);
    kfree(entry);
}

rhashtable — 可调整大小的哈希表

rhashtable 是一个可自动扩展和收缩的哈希表实现，支持 RCU 查找，适用于需要动态增长的哈希场景。

头文件： <linux/rhashtable.h>

核心 API：

API 说明
rhashtable_init(ht, params) 初始化
rhashtable_insert_slow(ht, key, obj) 插入
rhashtable_lookup(ht, key, params) 查找
rhashtable_remove(ht, obj, params) 删除
rhashtable_free_and_destroy(ht, fn, data) 销毁

内核中的典型应用：

  • 网络命名空间的连接跟踪表
  • XFRM 安全策略数据库
  • BPF map 的哈希类型实现

maple_tree — 枫树（Maple Tree）

Linux 6.1 引入的新型数据结构，用于替代 VMA 管理中的红黑树+链表组合。maple_tree 是一种 B 树变体，支持范围操作（range operations），对 VMA 的查找、遍历和间隙搜索非常高效。

头文件： <linux/maple_tree.h>

数据结构：

1
2
3
4
5
struct maple_tree {
    spinlock_t      ma_lock;
    unsigned int    ma_flags;
    void __rcu     *ma_root;  // RCU 保护
};

核心 API：

API 说明
mt_init(mt) 初始化
mtree_lock(mt) 获取写锁
mtree_unlock(mt) 释放写锁
mas_store(mas, entry) 存储条目
mas_find(mas, max) 查找
mas_erase(mas) 删除
MTREE_INIT(mt, flags) 静态初始化
mtree_destroy(mt) 销毁

内核中的典型应用：

  • VMA 管理：Linux 6.1+ 用 maple_tree 替代红黑树 + 双向链表管理 vm_area_struct
  • 用户空间程序（用户态 RCU 库 URCU 也实现了 maple tree）

interval_tree — 区间树

区间树是增强型红黑树，用于管理区间（[start, last]），支持快速查找与给定区间重叠的所有区间。基于 rbtree_augmented 实现。

头文件： <linux/interval_tree.h>

数据结构：

1
2
3
4
5
6
struct interval_tree_node {
    struct rb_node rb;
    unsigned long start;     // 区间起始
    unsigned long last;      // 区间结束
    unsigned long __subtree_last;  // 子树中最大的 last（增强信息）
};

核心 API：

API 说明
interval_tree_insert(node, root) 插入
interval_tree_remove(node, root) 删除
interval_tree_iter_first(root, start, last) 查找第一个重叠区间
interval_tree_iter_next(node, start, last) 查找下一个重叠区间

内核中的典型应用：

  • VMA 区间查找（查找与某个地址范围重叠的虚拟内存区域）
  • DRM GPU 驱动的 GEM 缓冲区管理

klist — 内核对象链表

klist 是对 list_head 的包装，与 kobject 体系配合使用，提供 get/put 引用计数保护：遍历链表时自动获取节点对象的引用，防止遍历过程中节点被释放。

头文件： <linux/klist.h>

数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
struct klist_node {
    void            *n_klist;   // 不再使用的字段
    struct list_head    n_node;
    struct kref     n_ref;      // 引用计数
};

struct klist {
    spinlock_t      k_lock;
    struct list_head    k_list;
    void            (*get)(struct klist_node *);
    void            (*put)(struct klist_node *);
};

核心 API：

API 说明
klist_add_head(n, k) 添加到头部
klist_add_tail(n, k) 添加到尾部
klist_del(n) 删除
klist_iter_init(k, i) 初始化迭代器
klist_next(i) 获取下一个节点（自动 get/put）
klist_iter_exit(i) 清理迭代器

内核中的典型应用：

  • 设备驱动模型中 bus_type 的设备列表
  • 设备驱动模型中 driver 的设备列表

ID、位图与 DMA

idr — ID 分配器

idr 提供整数 ID 到指针的映射，自动分配一个唯一的整数 ID 并关联到指针。适合"需要一个整数句柄"的场景。

头文件： <linux/idr.h>

核心 API（现代接口）：

API 说明
idr_alloc(idr, ptr, start, end, gfp) 分配 ID 并关联指针
idr_find(idr, id) 通过 ID 查找指针
idr_remove(idr, id) 删除 ID 映射
idr_for_each(idr, fn, data) 遍历所有条目
idr_destroy(idr) 销毁 idr
idr_init(idr) 初始化

使用示例：

1
2
3
4
5
6
7
8
9
10
11
DEFINE_IDR(my_idr);

// 分配
int id;
id = idr_alloc(&my_idr, ptr, 1, 0, GFP_KERNEL);  // 从1开始分配

// 查找
void *p = idr_find(&my_idr, id);

// 释放
idr_remove(&my_idr, id);

内核中的典型应用：

  • 进程 PID 管理
  • 设备 minor 号分配
  • GPU DRM 驱动的句柄管理（GEM buffer handle）

ida — IDA 分配器

ida 是 idr 的简化版，只分配整数 ID 而不关联指针（当只需要唯一整数 ID 时使用，内存开销更小）。

头文件： <linux/idr.h>

核心 API：

API 说明
ida_alloc(ida, gfp) 分配一个 ID
ida_free(ida, id) 释放 ID
ida_alloc_range(ida, min, max, gfp) 在范围内分配 ID
ida_init(ida) 初始化
ida_destroy(ida) 销毁

bitmap / cpumask — 位图

内核用 unsigned long 数组实现位图，提供高效的位操作集合。cpumask 是位图的特殊形式，专门描述 CPU 集合。

头文件： <linux/bitmap.h> / <linux/cpumask.h>

核心 API（bitmap）：

API 说明
bitmap_zero(dst, nbits) 全部清零
bitmap_set(dst, pos, nbits) 设置位
bitmap_clear(dst, pos, nbits) 清除位
bitmap_find_next_zero_area(buf, len, start, n, mask) 查找连续 0 区域
bitmap_and(dst, src1, src2, nbits) 按位与
bitmap_or(dst, src1, src2, nbits) 按位或

核心 API（cpumask）：

API 说明
cpumask_set_cpu(cpu, mask) 将 CPU 加入掩码
cpumask_clear_cpu(cpu, mask) 从掩码移除 CPU
cpumask_test_cpu(cpu, mask) 测试 CPU 是否在掩码中
for_each_cpu(cpu, mask) 遍历掩码中的 CPU
cpumask_of(cpu) 获取单个 CPU 的掩码
cpu_possible_mask 系统中所有可能的 CPU
cpu_online_mask 当前在线的 CPU
cpu_present_mask 当前存在的 CPU

内核中的典型应用：

  • IRQ 亲和性设置（指定中断由哪些 CPU 处理）
  • 进程的 cpus_allowed（设置进程能运行在哪些 CPU 上）
  • 内存节点的 DMA 掩码

scatterlist — 散布表

scatterlist 用于描述不连续的内存区域，在 DMA（直接内存访问）场景中极为常用：将分散的物理内存片段链接成一个整体，供 DMA 引擎一次性处理。

头文件： <linux/scatterlist.h>

数据结构：

1
2
3
4
5
6
7
struct scatterlist {
    unsigned long   page_link;   // 编码了 page + offset + chain 信息
    unsigned int    offset;      // 页内偏移
    unsigned int    length;      // 数据长度
    dma_addr_t      dma_address; // DMA 地址
    unsigned int    dma_length;
};

核心 API：

API 说明
sg_init_one(sg, buf, len) 初始化单条目 sg
sg_init_table(sg, nents) 初始化 sg 表
sg_set_buf(sg, buf, len) 设置条目
sg_set_page(sg, page, len, offset) 设置页条目
sg_next(sg) 获取下一个条目
sg_nents(sg) 计算条目数
dma_map_sg(dev, sg, nents, dir) 为 DMA 映射 sg 表
dma_unmap_sg(dev, sg, nents, dir) 解除 DMA 映射

使用示例：

1
2
3
4
5
6
7
8
struct scatterlist sg[2];
sg_init_table(sg, 2);
sg_set_buf(&sg[0], buf1, len1);
sg_set_buf(&sg[1], buf2, len2);

int nents = dma_map_sg(dev, sg, 2, DMA_TO_DEVICE);
// ... 发起 DMA 传输 ...
dma_unmap_sg(dev, sg, 2, DMA_TO_DEVICE);

内核中的典型应用：

  • 块设备 I/O（bio 中的 scatter-gather 链表）
  • 网络驱动（分散-聚集 Tx/Rx）
  • 任何涉及 DMA 的数据传输
  • 加密/解密子系统的数据缓冲区

并发与同步

atomic_t — 原子变量

内核中用于简单计数、标志位的原子操作，是锁-free 编程的基础。在 32 位平台上 atomic_t 是 32 位，64 位平台上还有 atomic64_t。

头文件： <linux/atomic.h>

数据结构：

1
2
3
typedef struct {
    int counter;
} atomic_t;

核心 API：

API 说明
atomic_read(v) 读取值
atomic_set(v, i) 设置值
atomic_inc(v) 自增
atomic_dec(v) 自减
atomic_add(i, v) 加
atomic_sub(i, v) 减
atomic_inc_return(v) 自增并返回新值
atomic_dec_and_test(v) 自减并测试是否为 0
atomic_cmpxchg(v, old, new) CAS 操作
atomic_xchg(v, new) 交换并返回旧值

内核中的典型应用：

  • 引用计数（驱动程序的打开计数）
  • 统计计数器（网络包计数、中断计数）
  • 简单的锁-free 标志

kref / refcount_t — 引用计数

kref

封装 refcount_t，提供对象的引用计数管理，配合 release 回调在计数归零时自动释放资源。

头文件： <linux/kref.h>

1
2
3
4
5
6
7
struct kref {
    refcount_t refcount;
};

void kref_init(struct kref *kref);
void kref_get(struct kref *kref);           // 增加引用
int kref_put(struct kref *kref, void (*release)(struct kref *kref));  // 减少引用，为0时调用release

refcount_t

refcount_t 是 atomic_t 的加强版，提供溢出保护——到达最大值后不再增加，避免引用计数溢出导致的 use-after-free 漏洞。

头文件： <linux/refcount.h>

1
2
3
typedef struct refcount_struct {
    atomic_t refs;
} refcount_t;

典型使用模式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct my_object {
    struct kref kref;
    // ... other data
};

void release_callback(struct kref *kref)
{
    struct my_object *obj = container_of(kref, struct my_object, kref);
    kfree(obj);
}

// 获取引用
struct my_object *get_object(struct my_object *obj)
{
    if (obj)
        kref_get(&obj->kref);
    return obj;
}

// 释放引用
void put_object(struct my_object *obj)
{
    if (obj)
        kref_put(&obj->kref, release_callback);
}

内核中的典型应用：

  • struct kobject 的引用计数
  • struct device 的生命周期管理
  • 文件描述符（struct file）
  • 几乎所有需要管理生命周期的内核对象

spinlock_t — 自旋锁

Linux 内核最基本的忙等锁，用于 SMP 系统中的短临界区保护。持有者在一个 CPU 上自旋等待时，其他 CPU 上的执行者也在自旋等待。

头文件： <linux/spinlock.h>

数据结构（简化）：

1
2
3
4
5
6
typedef struct spinlock {
    union {
        struct raw_spinlock rlock;
        // ...
    };
} spinlock_t;

核心 API：

API 说明
spin_lock_init(lock) 动态初始化
DEFINE_SPINLOCK(lock) 静态定义 + 初始化
spin_lock(lock) 获取锁（禁用内核抢占）
spin_unlock(lock) 释放锁
spin_lock_irq(lock) 获取锁并禁用本地中断
spin_unlock_irq(lock) 释放锁并启用本地中断
spin_lock_irqsave(lock, flags) 获取锁，保存中断状态
spin_unlock_irqrestore(lock, flags) 释放锁，恢复中断状态
spin_lock_bh(lock) 获取锁并禁用 bottom half
spin_trylock(lock) 尝试获取锁（非阻塞）
spin_is_locked(lock) 检查锁状态

持有自旋锁期间绝不能睡眠（不能调用 kmalloc(GFP_KERNEL)、copy_from_user 等可能阻塞的操作）。这是内核中最常见的 bug 来源之一。

选择指南：

场景 API
进程上下文之间 spin_lock / spin_unlock
进程与中断之间 spin_lock_irqsave / spin_unlock_irqrestore
不同中断之间 spin_lock_irqsave / spin_unlock_irqrestore
进程与 bottom half 之间 spin_lock_bh / spin_unlock_bh

mutex — 互斥锁

与自旋锁不同，mutex 在无法获取锁时会让出 CPU 进入睡眠，适用于可能休眠的临界区。

头文件： <linux/mutex.h>

数据结构：

1
2
3
4
5
6
struct mutex {
    atomic_long_t       owner;
    raw_spinlock_t      wait_lock;
    struct list_head    wait_list;  // 等待者队列
    // ...
};

核心 API：

API 说明
mutex_init(lock) 动态初始化
DEFINE_MUTEX(lock) 静态定义
mutex_lock(lock) 获取锁（可能睡眠）
mutex_unlock(lock) 释放锁
mutex_lock_interruptible(lock) 可被信号中断的获取
mutex_trylock(lock) 尝试获取（非阻塞）
mutex_is_locked(lock) 检查状态

mutex 上锁者必须负责解锁（不允许在不同上下文中 lock/unlock）。内核会对此进行严格检查。

spinlock 与 mutex 的选择：

spinlock mutex
无法获取时 自旋等待 睡眠让出 CPU
临界区 短（纳秒级） 可较长（毫秒级）
能否睡眠 绝对不能 可以
中断上下文 可用 不可用
系统开销 低 较高（涉及调度）

completion — 完成量

completion 是内核中实现一个线程等待另一个线程完成某项任务的同步机制，比信号量更轻量、语义更清晰。

头文件： <linux/completion.h>

数据结构：

1
2
3
4
struct completion {
    unsigned int done;
    struct swait_queue_head wait;
};

核心 API：

API 说明
DECLARE_COMPLETION(comp) 静态定义
init_completion(comp) 动态初始化
wait_for_completion(comp) 等待完成（不可中断）
wait_for_completion_interruptible(comp) 等待完成（可被信号中断）
wait_for_completion_timeout(comp, timeout) 带超时的等待
complete(comp) 唤醒一个等待者
complete_all(comp) 唤醒所有等待者
try_wait_for_completion(comp) 非阻塞尝试

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 线程 A：等待
DECLARE_COMPLETION(done);

int thread_a(void *data)
{
    wait_for_completion(&done);
    pr_info("任务完成\n");
    return 0;
}

// 线程 B：完成后通知
int thread_b(void *data)
{
    do_something();
    complete(&done);
    return 0;
}

内核中的典型应用：

  • 内核线程创建/销毁等待
  • 设备初始化完成通知
  • 异步 I/O 完成通知
  • 模块卸载等待

RCU (rcu_head) — 读-复制-更新

RCU（Read-Copy-Update）是 Linux 内核中重要的无锁同步机制，适用于读多写少的场景。读者完全无锁，写者先复制再更新，等待所有读者完成后回收旧数据。

头文件： <linux/rcupdate.h> / <linux/srcu.h>

数据结构：

1
2
3
4
struct rcu_head {
    struct callback_head *next;
    void (*func)(struct callback_head *head);
};

核心 API：

API 说明
rcu_read_lock() 读者进入临界区
rcu_read_unlock() 读者离开临界区
call_rcu(head, func) 注册回收回调
synchronize_rcu() 等待所有读者完成（阻塞）
rcu_assign_pointer(p, v) 写者更新指针
rcu_dereference(p) 读者解引用指针
kfree_rcu(ptr, rcu_field) RCU 安全释放内存

典型模式：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 读者 —— 完全无锁
rcu_read_lock();
struct my_data *p = rcu_dereference(global_ptr);
if (p)
    do_something(p);
rcu_read_unlock();

// 写者 —— 复制 + 更新
struct my_data *old = global_ptr;
struct my_data *new = kmemdup(old, sizeof(*old), GFP_KERNEL);
update_data(new);
rcu_assign_pointer(global_ptr, new);
call_rcu(&old->rcu, my_free_callback);

内核中的典型应用：

  • 网络路由表查找
  • 文件系统 dentry 缓存
  • radix_tree / xarray 的无锁查找
  • fdtable（文件描述符表）的扩展

等待与调度

wait_queue — 等待队列

等待队列是一种更通用的等待机制：进程将自己加入等待队列后进入睡眠，当条件满足时被唤醒。

头文件： <linux/wait.h>

数据结构：

1
2
3
4
5
6
7
8
9
10
11
struct wait_queue_head {
    spinlock_t          lock;
    struct list_head    head;     // 等待条目链表
};

struct wait_queue_entry {
    unsigned int        flags;
    void               *private;  // 通常指向 task_struct
    wait_queue_func_t   func;     // 唤醒回调（通常是 autoremove_wake_function）
    struct list_head    entry;
};

核心 API：

API 说明
DECLARE_WAIT_QUEUE_HEAD(wq) 静态定义
init_waitqueue_head(wq) 动态初始化
wait_event(wq, condition) 等待直到条件为真
wait_event_interruptible(wq, condition) 可被信号中断的等待
wait_event_timeout(wq, condition, timeout) 带超时的等待
wake_up(wq) 唤醒所有等待者
wake_up_interruptible(wq) 唤醒 TASK_INTERRUPTIBLE 的等待者
wake_up_nr(wq, nr) 唤醒 nr 个等待者

使用示例：

1
2
3
4
5
6
7
8
9
DECLARE_WAIT_QUEUE_HEAD(wq);
int data_ready = 0;

// 等待侧
wait_event_interruptible(wq, data_ready != 0);

// 唤醒侧
data_ready = 1;
wake_up_interruptible(&wq);

内核中的典型应用：

  • 进程状态切换（TASK_INTERRUPTIBLE / TASK_UNINTERRUPTIBLE）
  • 设备驱动的阻塞 I/O（read/write 等待数据）
  • Pipe、Socket 的读写等待

work_struct / workqueue — 工作队列

工作队列将任务推迟到进程上下文中执行，是中断底半部（bottom half）处理的常用方式之一。

头文件： <linux/workqueue.h>

数据结构：

1
2
3
4
5
6
7
8
struct work_struct {
    atomic_long_t data;
    struct list_head entry;
    work_func_t func;  // 工作函数
};

// 工作函数签名：
typedef void (*work_func_t)(struct work_struct *work);

核心 API：

API 说明
DECLARE_WORK(work, func) 静态定义
INIT_WORK(work, func) 动态初始化
schedule_work(work) 调度到系统工作队列
schedule_delayed_work(dwork, delay) 延迟调度
queue_work(wq, work) 调度到指定工作队列
cancel_work_sync(work) 取消并等待完成
flush_work(work) 等待工作完成
alloc_ordered_workqueue(name, flags) 创建有序工作队列

使用示例：

1
2
3
4
5
6
7
8
9
10
static void my_work_handler(struct work_struct *work)
{
    pr_info("工作在进程上下文执行\n");
    // 这里可以睡眠！
}

DECLARE_WORK(my_work, my_work_handler);

// 触发（例如在中断处理中）
schedule_work(&my_work);

内核中的典型应用：

  • 中断底半部处理
  • 设备驱动的延迟初始化
  • 网络栈的包处理
  • GPU 驱动的 command submission

timer_list — 内核定时器

用于在指定时间后执行回调函数（软中断上下文），精度为 jiffies 级别（通常 1ms~10ms）。需要更高精度应使用 hrtimer。

头文件： <linux/timer.h>

数据结构：

1
2
3
4
5
6
7
struct timer_list {
    struct hlist_node   entry;
    unsigned long       expires;  // 到期时间（jiffies）
    void                (*function)(struct timer_list *);
    u32                 flags;
    // ...
};

核心 API：

API 说明
timer_setup(timer, callback, flags) 初始化定时器
mod_timer(timer, expires) 修改到期时间
add_timer(timer) 添加定时器
del_timer(timer) 删除定时器
del_timer_sync(timer) 同步删除（等待 handler 完成）
timer_pending(timer) 检查是否已提交

使用示例：

1
2
3
4
5
6
7
8
9
10
static void my_timer_callback(struct timer_list *t)
{
    pr_info("定时器到期\n");
    // 周期定时器：重新设置
    mod_timer(t, jiffies + msecs_to_jiffies(500));
}

struct timer_list my_timer;
timer_setup(&my_timer, my_timer_callback, 0);
mod_timer(&my_timer, jiffies + msecs_to_jiffies(500));

内核中的典型应用：

  • TCP 重传定时器、keepalive 定时器
  • 看门狗定时器
  • 设备驱动的轮询（polling）
  • LED 闪烁控制

hrtimer — 高精度定时器

hrtimer 提供纳秒级精度的定时器，底层基于红黑树管理。是现代 Linux 定时器子系统的基础。

头文件： <linux/hrtimer.h>

数据结构：

1
2
3
4
5
6
struct hrtimer {
    struct timerqueue_node      node;   // 红黑树节点
    ktime_t                     _softexpires;
    enum hrtimer_restart        (*function)(struct hrtimer *);
    // ...
};

核心 API：

API 说明
hrtimer_init(timer, clock_id, mode) 初始化
hrtimer_start(timer, time, mode) 启动定时器
hrtimer_cancel(timer) 取消定时器
hrtimer_forward_now(timer, interval) 从当前时间向前推进

使用示例：

1
2
3
4
5
6
7
8
9
10
11
static enum hrtimer_restart my_hrtimer_cb(struct hrtimer *timer)
{
    pr_info("高精度定时器到期\n");
    hrtimer_forward_now(timer, ns_to_ktime(1000000));  // 1ms
    return HRTIMER_RESTART;
}

struct hrtimer hr_timer;
hrtimer_init(&hr_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
hr_timer.function = my_hrtimer_cb;
hrtimer_start(&hr_timer, ns_to_ktime(1000000), HRTIMER_MODE_REL);

内核中的典型应用：

  • 进程调度器的周期 tick
  • POSIX 定时器
  • 高精度 sleep（usleep_range）
  • 网络包的精确延迟控制

设备模型与通知

kobject / kset — 内核对象模型

kobject 是 Linux 设备驱动模型的基石，为所有内核对象提供统一的引用计数、sysfs 表示和热插拔事件支持。

头文件： <linux/kobject.h>

数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct kobject {
    const char      *name;
    struct list_head    entry;       // 链入 kset 的链表
    struct kobject      *parent;     // 父对象
    struct kset         *kset;       // 所属 kset
    struct kobj_type    *ktype;      // 类型描述符（包含 sysfs 操作）
    struct kernfs_node  *sd;        // sysfs 目录节点
    struct kref         kref;        // 引用计数
    unsigned int state_initialized:1;
    // ...
};

struct kset {
    struct list_head list;           // 属于这个 kset 的所有 kobject
    spinlock_t list_lock;
    struct kobject kobj;             // 自身也是一个 kobject
    const struct kset_uevent_ops *uevent_ops;
};

核心 API：

API 说明
kobject_init(obj, ktype) 初始化 kobject
kobject_add(obj, parent, fmt, ...) 添加到 sysfs
kobject_init_and_add(obj, ktype, parent, fmt, ...) 初始化 + 添加
kobject_put(obj) 减少引用计数
kobject_get(obj) 增加引用计数
kobject_uevent(obj, action) 发送 uevent 到用户空间
kset_register(kset) 注册 kset
kobject_create_and_add(name, parent) 快速创建 kobject

内核中的典型应用：

  • /sys 文件系统的每个目录和文件
  • struct device、struct driver、struct bus_type 等设备模型的基类
  • uevent 热插拔事件（如 U 盘插入通知 udev）

notifier_block — 通知链

通知链（Notifier Chain）是内核中发布-订阅模式的实现：某个子系统发布事件，其他感兴趣的模块注册回调来接收通知。

头文件： <linux/notifier.h>

数据结构：

1
2
3
4
5
struct notifier_block {
    notifier_fn_t notifier_call;    // 回调函数
    struct notifier_block __rcu *next;  // 链表下一个
    int priority;                   // 优先级
};

核心 API：

API 说明
blocking_notifier_chain_register(head, nb) 注册通知块
blocking_notifier_chain_unregister(head, nb) 注销
blocking_notifier_call_chain(head, val, v) 发起通知
raw_notifier_chain_register(head, nb) 注册（原子上下文安全）
atomic_notifier_chain_register(head, nb) 注册（原子上下文）

通知链类型：

类型 回调上下文 是否可阻塞
atomic_notifier_chain 原子上下文（中断/spinlock） 否
blocking_notifier_chain 进程上下文 是
raw_notifier_chain 任意上下文（调用者负责） 取决于调用者
SRCU_notifier_chain 进程上下文（SRCU 保护） 是

内核中的典型应用：

  • 内核恐慌（panic）通知
  • CPU 热插拔事件
  • 网络设备事件（netdev 注册/注销）
  • 系统重启/挂起通知
  • 内存不足（OOM）通知

内存管理与缓存

kfifo — 内核 FIFO 队列

kfifo 是一个无锁的环形缓冲区（circular buffer），提供 producer/consumer 单读者/单写者的无锁通信（多读者/多写者需外部同步）。

头文件： <linux/kfifo.h>

核心 API：

API 说明
DECLARE_KFIFO(fifo, type, size) 静态定义
kfifo_alloc(fifo, size, gfp) 动态分配
kfifo_put(fifo, val) 入队一个元素
kfifo_get(fifo, val) 出队一个元素
kfifo_in(fifo, buf, n) 入队多个字节
kfifo_out(fifo, buf, n) 出队多个字节
kfifo_is_empty(fifo) 是否为空
kfifo_is_full(fifo) 是否已满
kfifo_len(fifo) 已使用的元素数
kfifo_reset(fifo) 清空队列
kfifo_free(fifo) 释放内存

使用示例：

1
2
3
4
5
6
7
8
9
10
DECLARE_KFIFO(fifo, int, 32);

// 入队
int val = 42;
kfifo_put(&fifo, val);

// 出队
int out;
if (kfifo_get(&fifo, &out))
    pr_info("got: %d\n", out);

内核中的典型应用：

  • 串口驱动的收发缓冲区
  • 音频驱动的 PCM 缓冲区
  • 内核日志缓冲区（printk ring buffer）

percpu — Per-CPU 变量

Per-CPU 变量为每个 CPU 分配独立的内存副本，CPU 访问自己的副本无需加锁，且缓存利用率极高（变量在 CPU 本地缓存中）。

头文件： <linux/percpu.h>

核心 API：

API 说明
DEFINE_PER_CPU(type, name) 静态定义
alloc_percpu(type) 动态分配
per_cpu(var, cpu) 访问指定 CPU 的副本
get_cpu_var(var) 获取本 CPU 副本（禁用抢占）
put_cpu_var(var) 配合 get_cpu_var，恢复抢占
this_cpu_ptr(ptr) 获取本 CPU 副本的指针
per_cpu_ptr(ptr, cpu) 获取指定 CPU 副本的指针
for_each_possible_cpu(cpu) 遍历所有 CPU

使用示例：

1
2
3
4
5
6
7
8
9
static DEFINE_PER_CPU(int, my_counter);

// 递增本 CPU 的计数器 —— 无需加锁
int cpu = get_cpu();
per_cpu(my_counter, cpu)++;
put_cpu();

// 更简洁的方式（性能更好）
this_cpu_inc(my_counter);

内核中的典型应用：

  • 统计计数器（网络包计数、中断计数）
  • 内存分配器的 per-CPU 缓存（slab/slub）
  • RCU 的 per-CPU 状态
  • 调度器的 per-CPU 运行队列

circ_buf — 环形缓冲区宏

一组简单的宏，用于将普通字符数组作为环形缓冲区使用。常用于实现轻量级的 producer/consumer 队列。

头文件： <linux/circ_buf.h>

数据结构：

1
2
3
4
5
struct circ_buf {
    char *buf;
    int head;   // 生产者写入位置
    int tail;   // 消费者读取位置
};

核心宏：

宏 说明
CIRC_SPACE(head, tail, size) 可用空间
CIRC_CNT(head, tail, size) 已使用字节数
CIRC_SPACE_TO_END(head, tail, size) 到缓冲区末尾的连续空间

内核中的典型应用：

  • TTY 驱动的行规范（line discipline）缓冲区
  • 简单串口驱动

flex_array — 柔性数组

flex_array 允许创建跨多个页面的数组，但每个元素大小固定。相比一次 kmalloc 大块内存，flex_array 对小内存碎片的容忍度更好（因为每个元素分布在不同页面上）。

从 Linux 5.10 开始，flex_array 已被标记为 deprecated，推荐使用普通 kmalloc_array 或 kvmalloc_array 代替。

头文件： <linux/flex_array.h>（已删除）

替代方案： kvmalloc_array(n, size, GFP_KERNEL) 会自动选择 kmalloc 或 vmalloc。

page — 物理页描述符

struct page 是 Linux 内存管理中最重要的数据结构，每个物理内存页都有一个对应的 page 结构体。

头文件： <linux/mm_types.h>

数据结构（大幅简化）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct page {
    unsigned long flags;         // 页标志（PG_locked, PG_dirty 等）
    union {
        struct {
            struct list_head lru;    // LRU 链表
            struct address_space *mapping;  // 所属文件映射
            pgoff_t index;           // 页内偏移
            unsigned long private;
        };
        // ... SLUB/slab 相关字段
    };
    refcount_t _refcount;        // 引用计数
    // ...
};

核心 API（部分）：

API 说明
alloc_pages(gfp_mask, order) 分配 2^order 个页面
__free_pages(page, order) 释放页面
get_page(page) 增加引用计数
put_page(page) 减少引用计数
page_to_pfn(page) 获取页帧号
pfn_to_page(pfn) 页帧号转 page
kmap(page) 映射到内核地址空间
kunmap(page) 解除映射

内核中的典型应用：

  • Page Cache
  • SLUB/SLAB 分配器的底层基础
  • 用户空间页表映射（缺页异常处理）

mm_struct / vm_area_struct — 进程地址空间

mm_struct — 内存描述符

描述一个进程的完整虚拟地址空间，每个进程有唯一的 mm_struct（线程间可共享）。

头文件： <linux/mm_types.h>

1
2
3
4
5
6
7
8
9
10
11
12
struct mm_struct {
    struct maple_tree   mm_mt;          // VMA 的 maple tree（6.1+）
    struct vm_area_struct *mmap;        // VMA 链表头
    unsigned long task_size;            // 地址空间大小
    pgd_t *pgd;                         // 页全局目录
    atomic_t mm_users;                  // 使用者计数
    atomic_t mm_count;                  // 引用计数
    unsigned long total_vm;             // 总页面数
    spinlock_t page_table_lock;
    struct list_head mmlist;            // 全局 mm_struct 链表
    // ...
};

vm_area_struct — 虚拟内存区域

描述一段连续的虚拟地址区间，每个区间有相同的保护属性和映射类型。

1
2
3
4
5
6
7
8
9
10
11
12
struct vm_area_struct {
    unsigned long vm_start;             // 起始地址
    unsigned long vm_end;               // 结束地址（不包含）
    struct vm_area_struct *vm_next;     // 链表下一个
    pgprot_t vm_page_prot;              // 页面保护
    unsigned long vm_flags;             // VM_READ, VM_WRITE, VM_EXEC 等
    struct rb_node vm_rb;               // 红黑树节点（旧版）
    struct mm_struct *vm_mm;            // 所属 mm_struct
    const struct vm_operations_struct *vm_ops;  // 操作函数表
    struct file *vm_file;               // 映射的文件
    // ...
};

内核中的典型应用：

  • 缺页异常处理器
  • mmap() / munmap() 系统调用
  • /proc/<pid>/maps 的信息来源

网络

sk_buff — Socket 缓冲区

sk_buff（通常简称为 skb）是 Linux 网络子系统的核心数据结构，表示一个网络数据包。它贯穿于整个网络栈：从网卡驱动接收到应用层发送，都以 sk_buff 为载体。

头文件： <linux/skbuff.h>

数据结构（简化）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct sk_buff {
    union {
        struct {
            struct sk_buff      *next;   // 双向链表
            struct sk_buff      *prev;
        };
        struct list_head    list;
    };
    struct sock     *sk;
    ktime_t         tstamp;
    struct net_device   *dev;
    char            cb[48] __aligned(8);  // 各层私有数据
    unsigned int    len,           // 数据总长度
                    data_len;      // 非线性的数据长度
    __u16           mac_len,
                    hdr_len;
    // ... 后面还有 head, data, tail, end 等指针
    sk_buff_data_t      tail;
    sk_buff_data_t      end;
    unsigned char       *head, *data;
    unsigned int        truesize;
    refcount_t          users;
};

sk_buff 使用四指针模型管理数据空间：

1
2
3
4
5
6
head  data        tail  end
 |     |           |     |
 v     v           v     v
+-----+-----------+-----+
|headroom|  data   |tailroom|
+-----+-----------+-----+

核心 API：

API 说明
alloc_skb(size, gfp) 分配 skb
skb_put(skb, len) 在尾部添加数据
skb_push(skb, len) 在头部添加数据（添加协议头）
skb_pull(skb, len) 从头部移除数据（剥离协议头）
skb_clone(skb, gfp) 克隆 skb（共享数据）
skb_copy(skb, gfp) 深拷贝（复制数据）
kfree_skb(skb) 释放 skb
skb_queue_head(list, skb) 入队到头部
skb_dequeue(list) 出队

内核中的典型应用：

  • 整个网络栈的包载体
  • TUN/TAP 虚拟网卡
  • Netfilter / iptables 的包过滤

参考文献

[1]
linux list详解
[2]
Linux：内核hash表——hlist
[3]
Linux中的红黑树（rbtree）
[4]
Linux：radix实现简析