Linux 内核常用数据结构

时间轴

时间轴

2026-05-24

init

2026-08-15

补充 hlist、xarray、plist 的完整模块示例，将 list_head、rbtree、radix_tree 的示例同步为 linux_driver_learning 82~87 系列的最新版本，并将其余数据结构（llist、rhashtable、maple_tree、interval_tree、klist、idr、ida、bitmap、scatterlist、atomic、kref、spinlock、mutex、completion、RCU、wait_queue、workqueue、timer、hrtimer、kobject、notifier、kfifo、percpu、circ_buf）的示例统一改写为同风格的可加载模块

本文介绍了Linux内核中常用的通用数据结构，按实际使用频率从高到低梳理了双向循环链表list_head、哈希链表hlist、红黑树rbtree、基数树radix_tree等核心结构，涵盖其数据结构定义、核心API及典型使用场景。文章基于Linux 6.x内核，并同步更新了各数据结构的可加载模块示例，便于开发者理解和应用。

---

概述

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

info

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

基础容器

list_head — 双向循环链表

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

success

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

头文件：<linux/list.h>

数据结构：

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)	合并两个链表

使用示例：

#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/module.h>
#include <linux/slab.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;

	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 0;
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("even629");
MODULE_DESCRIPTION("list test");

运行

~ # insmod list_test.ko
[   11.039661] list_test: loading out-of-tree module taints kernel.
[   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

完整可编译工程（含 Makefile 与 QEMU 运行环境）：linux_driver_learning/82_list。本系列每个数据结构都有对应的示例目录（82~87），后文不再逐个说明运行方法。

---

list_add和list_add_tail:

/**
 * 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函数

/**
 * 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可以替换一个链表节点

/**
 * 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>

数据结构：

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)

这样设计便于删除

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相关

/**
 * 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;
}

使用示例（哈希表演示，节选自 linux_driver_learning/83_hlist）：

// SPDX-License-Identifier: GPL-2.0
/* hlist_test.c -- hlist 最典型的应用场景：哈希表 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/list.h>
#include <linux/slab.h>

/* 哈希节点：模拟实际使用中嵌入 hlist_node 的数据结构 */
struct hlist_item {
	int key;			/* 键 */
	int value;			/* 值，模拟负载 */
	struct hlist_node node;		/* 嵌入的 hlist 节点 */
};

/* 辅助宏：通过 hlist_node 指针获取父结构体指针 */
#define item_entry(ptr)  hlist_entry(ptr, struct hlist_item, node)

#define HASH_TABLE_SIZE  8

static void demo_hash_table(void)
{
	struct hlist_head hashtable[HASH_TABLE_SIZE];
	struct hlist_item *items;
	/* 精心选择的 key，确保产生哈希冲突 */
	int keys[] = { 5, 13, 21, 8, 16, 24, 7, 15, 23, 6, 14, 22 };
	int n = ARRAY_SIZE(keys);
	int i;

	/* 初始化所有哈希桶 */
	for (i = 0; i < HASH_TABLE_SIZE; i++)
		INIT_HLIST_HEAD(&hashtable[i]);

	items = kcalloc(n, sizeof(*items), GFP_KERNEL);
	if (!items)
		return;

	/* 插入阶段：key 取模后放入对应桶，冲突时用头插法形成链 */
	for (i = 0; i < n; i++) {
		int hash = keys[i] % HASH_TABLE_SIZE;

		items[i].key = keys[i];
		items[i].value = keys[i] * 10;
		hlist_add_head(&items[i].node, &hashtable[hash]);
	}

	/* 打印桶布局：可以直观看到冲突链 */
	for (i = 0; i < HASH_TABLE_SIZE; i++) {
		struct hlist_node *pos;
		int count = 0;

		pr_info("  bucket[%d]: ", i);
		hlist_for_each(pos, &hashtable[i]) {
			if (count > 0)
				pr_cont(" -> ");
			pr_cont("%d", item_entry(pos)->key);
			count++;
		}
		pr_cont("%s  (chain len: %d)\n", count ? "" : "(empty)", count);
	}

	/* 查找阶段：先定位桶，再在冲突链上遍历比对 */
	{
		int key = 13;
		int hash = key % HASH_TABLE_SIZE;
		struct hlist_item *found = NULL;

		hlist_for_each_entry(found, &hashtable[hash], node) {
			if (found->key == key)
				break;
		}
		if (found && found->key == key)
			pr_info("  lookup key=%d: found! value=%d (bucket[%d])\n",
				key, found->value, hash);
	}

	/* 删除阶段：hlist_del 是 O(1) 操作，这就是 pprev 的威力 */
	{
		int key = 13;
		int hash = key % HASH_TABLE_SIZE;
		struct hlist_item *target = NULL;

		hlist_for_each_entry(target, &hashtable[hash], node) {
			if (target->key == key)
				break;
		}
		if (target && target->key == key)
			hlist_del_init(&target->node);
	}

	/*
	 * hlist_move_list 在 rehash 中的应用：
	 * 哈希表扩容/缩容时把整个桶的链表 O(1) 搬移到新桶
	 */
	{
		struct hlist_head new_bucket;
		struct hlist_node *pos;

		INIT_HLIST_HEAD(&new_bucket);
		hlist_move_list(&hashtable[5], &new_bucket);

		pr_info("  new_bucket: ");
		hlist_for_each(pos, &new_bucket)
			pr_cont("%d ", item_entry(pos)->key);
		pr_cont("\n");
	}

	kfree(items);
}

static int __init hlist_test_init(void)
{
	demo_hash_table();
	return 0;
}

static void __exit hlist_test_exit(void)
{
	pr_info("hlist_test module exit\n");
}

module_init(hlist_test_init);
module_exit(hlist_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("hlist hashtable demo module");

完整工程：linux_driver_learning/83_hlist

---

rbtree — 红黑树

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

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

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

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

数据结构：

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进行位操作。

#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和它管理的数据结构。

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

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

示例

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/rbtree.h>
#include <linux/slab.h>
#include <linux/random.h>

struct my_node {
	struct rb_node rb;
	unsigned long data;
};

static struct rb_root my_tree = RB_ROOT;

#define my_rb_entry(ptr) rb_entry((ptr), struct my_node, rb)

/*
 * 查找节点 - O(logn)
 */
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 = my_rb_entry(node);

		if (data < entry->data)
			node = node->rb_left;
		else if (data > entry->data)
			node = node->rb_right;
		else
			return entry;
	}
	return NULL;
}

/*
 * 插入节点
 */
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;

	while (*link) {
		struct my_node *entry = my_rb_entry(*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;
}

/*
 * 删除节点
 */
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;
	while ((node = rb_first_postorder(root))) {
		rb_erase(node, root);
		kfree(my_rb_entry(node));
	}
	*root = RB_ROOT;
}

static int __init rbtree_test_init(void)
{
	int i;
	unsigned long keys[] = { 1, 2, 3, 4, 5, 6, 7 };
	int count = ARRAY_SIZE(keys);

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

	/* 插入测试 */
	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("INSERT data=%lu OK\n", keys[i]);
		} else {
			pr_warn("INSERT data=%lu DUPLICATE\n", keys[i]);
			kfree(node);
		}
	}

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

		found = my_rb_search(&my_tree, 99);
		if (found)
			pr_info("SEARCH data=99 => %lu\n", found->data);
		else
			pr_warn("SEARCH data=99 => Not Found\n");
	}
	/* 中序遍历 */
	{
		struct rb_node *node;

		pr_info("IN-ORDER TRAVERSAL:\n");

		for (node = rb_first(&my_tree); node; node = rb_next(node)) {
			struct my_node *entry = my_rb_entry(node);
			pr_info("    data=%lu\n", entry->data);
		}
	}
	/* 后序遍历 */
	{
		struct rb_node *node;

		pr_info("POST-ORDER TRAVERSAL:\n");

		for (node = rb_last(&my_tree); node; node = rb_prev(node)) {
			struct my_node *entry = my_rb_entry(node);
			pr_info("    data=%lu\n", entry->data);
		}
	}

	/* 获取最小/最大节点 */
	{
		struct my_node *min = my_rb_entry(rb_first(&my_tree));
		struct my_node *max = my_rb_entry(rb_last(&my_tree));
		pr_info("    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("ERASE data=4\n");
			my_rb_erase(&my_tree, to_del);
		}
	}

	/* 再次中序遍历确认结果 */
	{
		struct rb_node *node;

		pr_info("AFTER ERASE 4:\n");

		for (node = rb_first(&my_tree); node; node = rb_next(node)) {
			struct my_node *entry = my_rb_entry(node);
			pr_info("    data=%lu\n", entry->data);
		}
	}

	return 0;
}

static void __exit rbtree_test_exit(void)
{
	my_rb_destroy(&my_tree);
	pr_info("%s is called\n", __func__);
}

module_init(rbtree_test_init);
module_exit(rbtree_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("rbtree test");

完整工程：linux_driver_learning/84_rbtree

---

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>

#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替代了它

示例

#include <linux/kernel.h>
#include <linux/module.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;
}

/* 核心操作函数封装 */
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);
}

/* 使用tag批量标记和检索 */
static void demo_tag_operations(void)
{
	struct my_data *d;
	void **slot;
	struct radix_tree_iter iter;

	pr_info("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);

	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);
                        continue;
                }
                if (d)
                        pr_info("TAGGED idex=%lu name=%s\n", iter.index, d->name);
	}
}

/* ========== 模块入口 ========== */
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("test for radix_tree_test");

完整工程：linux_driver_learning/85_radix_tree

---

xarray — 可扩展数组

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

头文件：<linux/xarray.h>

数据结构：

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)	查找范围内的条目

使用示例：

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);
}

完整模块示例（节选自 linux_driver_learning/86_xarray，完整版还包含xa_cmpxchg比较交换和xa_for_each_start起点遍历的演示）：

// SPDX-License-Identifier: GPL-2.0
/* xarray_test.c -- XArray 完整 API 演示 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/xarray.h>
#include <linux/slab.h>

struct xa_node_data {
	int key;
	int value;
};

static int g_passed;
static int g_failed;

#define test_assert(cond, msg)  do {					\
	if (cond) {							\
		g_passed++;						\
		pr_info("  [PASS] %s\n", msg);				\
	} else {							\
		g_failed++;						\
		pr_err("  [FAIL] %s\n", msg);				\
	}								\
} while (0)

/* ========== 基础操作：load/store/erase ========== */
static void demo_basic_ops(void)
{
	struct xarray xa;
	struct xa_node_data *data, *old;

	xa_init(&xa);
	test_assert(xa_empty(&xa), "xa_init creates empty array");

	data = kmalloc(sizeof(*data), GFP_KERNEL);
	data->key = 42;
	data->value = 420;

	/* xa_store：返回旧 entry（首次存储返回 NULL） */
	old = xa_store(&xa, 42, data, GFP_KERNEL);
	test_assert(old == NULL, "xa_store at empty index returns NULL");

	old = xa_load(&xa, 42);
	test_assert(old == data, "xa_load returns stored entry");

	/* 空槽返回 NULL */
	old = xa_load(&xa, 100);
	test_assert(old == NULL, "xa_load empty slot returns NULL");

	/* 稀疏索引：可以直接存储到大索引 */
	data = kmalloc(sizeof(*data), GFP_KERNEL);
	data->key = 1000;
	data->value = 10000;
	xa_store(&xa, 1000, data, GFP_KERNEL);

	old = xa_load(&xa, 1000);
	test_assert(old && old->value == 10000, "sparse index (1000) works");

	/* xa_erase：返回被删除的 entry */
	old = xa_erase(&xa, 42);
	test_assert(old && old->key == 42, "xa_erase returns erased entry");
	kfree(old);

	xa_erase(&xa, 1000);
	xa_destroy(&xa);
	test_assert(xa_empty(&xa), "xa_destroy leaves array empty");
}

/* ========== Value 存储：小整数直接存，无需分配内存 ========== */
static void demo_store_value(void)
{
	struct xarray xa;
	void *entry;
	unsigned long val;

	xa_init(&xa);

	/*
	 * xa_mk_value / xa_to_value / xa_is_value
	 * 原理：利用指针的最低位作为 tag（value entry 的 bit0 = 1）
	 */
	entry = xa_mk_value(12345);
	xa_store(&xa, 0, entry, GFP_KERNEL);

	entry = xa_load(&xa, 0);
	test_assert(xa_is_value(entry), "loaded entry is a value");
	val = xa_to_value(entry);
	test_assert(val == 12345, "value round-trip correct");

	xa_destroy(&xa);
}

/* ========== Mark 机制：标记 entry 状态，支持按 mark 遍历 ========== */
static void demo_mark_and_tag(void)
{
	struct xarray xa;
	struct xa_node_data *data, *d2, *d3, *found;
	unsigned long index;

	xa_init(&xa);

	/*
	 * 3 个 mark（XA_MARK_0/1/2），典型应用：
	 * page cache 用 mark 表示 dirty 状态
	 */
	data = kmalloc(sizeof(*data), GFP_KERNEL);
	data->key = 1; data->value = 100;
	xa_store(&xa, 10, data, GFP_KERNEL);

	d2 = kmalloc(sizeof(*d2), GFP_KERNEL);
	d2->key = 2; d2->value = 200;
	xa_store(&xa, 20, d2, GFP_KERNEL);

	d3 = kmalloc(sizeof(*d3), GFP_KERNEL);
	d3->key = 3; d3->value = 300;
	xa_store(&xa, 30, d3, GFP_KERNEL);

	/* 设置/查询/清除 mark */
	xa_set_mark(&xa, 10, XA_MARK_0);
	xa_set_mark(&xa, 30, XA_MARK_0);

	test_assert(xa_get_mark(&xa, 10, XA_MARK_0), "XA_MARK_0 set on index 10");
	test_assert(!xa_get_mark(&xa, 20, XA_MARK_0), "XA_MARK_0 not set on index 20");

	xa_clear_mark(&xa, 10, XA_MARK_0);
	test_assert(!xa_get_mark(&xa, 10, XA_MARK_0), "XA_MARK_0 cleared from index 10");

	/* 按 mark 遍历：只迭代设置了指定 mark 的 entry */
	xa_for_each_marked(&xa, index, found, XA_MARK_0)
		pr_info("    index=%lu, key=%d, value=%d\n",
			index, found->key, found->value);

	kfree(data);
	kfree(d2);
	kfree(d3);
	xa_destroy(&xa);
}

/* ========== xa_alloc 自动分配空闲 ID（inode 号、fd 分配） ========== */
static void demo_alloc(void)
{
	struct xarray xa;
	struct xa_node_data *data;
	u32 id;
	int ret, i;

	xa_init_flags(&xa, XA_FLAGS_ALLOC);

	for (i = 0; i < 5; i++) {
		data = kmalloc(sizeof(*data), GFP_KERNEL);
		data->key = i;
		data->value = i * 100;

		ret = xa_alloc(&xa, &id, data, XA_LIMIT(0, 100), GFP_KERNEL);
		test_assert(ret == 0, "xa_alloc succeeds");
		pr_info("  allocated id=%u for key=%d\n", id, i);
	}

	/* 删除中间一个，再分配应该复用 */
	data = xa_erase(&xa, 2);
	kfree(data);

	data = kmalloc(sizeof(*data), GFP_KERNEL);
	data->key = 99;
	data->value = 9900;
	xa_alloc(&xa, &id, data, XA_LIMIT(0, 100), GFP_KERNEL);
	test_assert(id == 2, "xa_alloc reuses freed id");

	for (i = 0; i <= 4; i++) {
		data = xa_load(&xa, i);
		if (data)
			xa_erase(&xa, i);
		kfree(data);
	}
	xa_destroy(&xa);
}

/* ========== 真实场景模拟：页缓存索引 ========== */
static void demo_page_cache_simulation(void)
{
	struct xarray xa;
	struct xa_node_data *page;
	unsigned long index;
	int i, found_count = 0;
	unsigned long pages[] = { 0, 3, 7, 15, 100 };

	/*
	 * 模拟内核 page cache 的核心机制：
	 * - 文件的 page cache 用 XArray 索引（index = page offset）
	 * - 支持 sparse access（文件可以有 hole）
	 * - 用 mark 标记 dirty page（需要回写）
	 */
	xa_init(&xa);

	for (i = 0; i < ARRAY_SIZE(pages); i++) {
		page = kmalloc(sizeof(*page), GFP_KERNEL);
		page->key = pages[i];
		page->value = pages[i] * 4096; /* 模拟 page 物理地址 */
		xa_store(&xa, pages[i], page, GFP_KERNEL);

		/* 模拟 dirty page 标记 */
		if (i % 2 == 0)
			xa_set_mark(&xa, pages[i], XA_MARK_0);
	}

	/* 遍历所有 dirty page（需要回写的） */
	xa_for_each_marked(&xa, index, page, XA_MARK_0)
		found_count++;
	test_assert(found_count == 3, "3 dirty pages (index 0,7,100)");

	/* 模拟 truncate：删除 offset >= 7 的 page */
	for (i = 0; i < ARRAY_SIZE(pages); i++) {
		if (pages[i] >= 7) {
			page = xa_erase(&xa, pages[i]);
			kfree(page);
		}
	}

	/* 清理 */
	xa_for_each(&xa, index, page) {
		xa_erase(&xa, index);
		kfree(page);
	}
	xa_destroy(&xa);
}

static int __init xarray_test_init(void)
{
	demo_basic_ops();
	demo_store_value();
	demo_mark_and_tag();
	demo_alloc();
	demo_page_cache_simulation();

	pr_info("PASS: %d  FAIL: %d\n", g_passed, g_failed);
	return 0;
}

static void __exit xarray_test_exit(void)
{
	pr_info("xarray_test module exit\n");
}

module_init(xarray_test_init);
module_exit(xarray_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("xarray demo module");

完整工程：linux_driver_learning/86_xarray

---

plist — 优先级链表

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

头文件：<linux/plist.h>

数据结构：

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)	判断是否为空

使用示例（节选自 linux_driver_learning/87_plist）：

注意

内核的plist_add()/plist_del()/plist_requeue()没有 export 给模块使用，所以模块里无法直接调用它们。下面的示例用my_plist_前缀自行实现了简化版插入/删除，用来演示 plist 的两层结构和排序行为；头文件里的遍历/访问宏（plist_for_each_entry、plist_first()等）是可以直接用的。

// SPDX-License-Identifier: GPL-2.0
/* plist_test.c -- 理解 plist（优先级链表）的核心原理 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/plist.h>
#include <linux/slab.h>

/*
 * my_plist_add: 按优先级插入节点（简化版，内核未 export 原版）
 * 算法：遍历 node_list 找到第一个 prio 大于等于新节点的位置，插入其前面
 * 使用 >= 保证同优先级时新节点插在同级前面（LIFO，这是内核 plist 的行为）
 */
static void my_plist_add(struct plist_node *node, struct plist_head *head)
{
	struct list_head *pos;
	struct plist_node *iter;

	list_for_each(pos, &head->node_list) {
		iter = list_entry(pos, struct plist_node, node_list);
		if (iter->prio >= node->prio) {
			list_add_tail(&node->node_list, pos);
			return;
		}
	}
	/* 优先级最低，插到最后 */
	list_add_tail(&node->node_list, &head->node_list);
}

/* my_plist_del: O(1) 删除 */
static void my_plist_del(struct plist_node *node, struct plist_head *head)
{
	list_del_init(&node->node_list);
}

/* my_plist_requeue: 修改优先级后重新排序（先删再插） */
static void my_plist_requeue(struct plist_node *node, struct plist_head *head)
{
	if (!plist_node_empty(node))
		my_plist_del(node, head);
	my_plist_add(node, head);
}

/* 测试数据节点 */
struct plist_data {
	int id;
	int value;
	struct plist_node node;
};

/* ========== 基础操作：add/del/iterate ========== */
static void demo_basic_ops(void)
{
	PLIST_HEAD(head);
	struct plist_data *d1, *d2, *d3, *pos;

	d1 = kmalloc(sizeof(*d1), GFP_KERNEL);
	d1->id = 1; d1->value = 100;
	plist_node_init(&d1->node, 10);		/* 数值越小优先级越高 */

	d2 = kmalloc(sizeof(*d2), GFP_KERNEL);
	d2->id = 2; d2->value = 200;
	plist_node_init(&d2->node, 20);

	d3 = kmalloc(sizeof(*d3), GFP_KERNEL);
	d3->id = 3; d3->value = 300;
	plist_node_init(&d3->node, 30);

	/* 乱序插入，最终顺序只由优先级决定 */
	my_plist_add(&d2->node, &head);
	my_plist_add(&d1->node, &head);
	my_plist_add(&d3->node, &head);

	/* plist_first 返回最高优先级的节点 */
	pr_info("  first prio=%d, last prio=%d\n",
		plist_first(&head)->prio, plist_last(&head)->prio);

	/* 按优先级从高到低遍历 */
	plist_for_each_entry(pos, &head, node) {
		pr_info("    id=%d, prio=%d, value=%d\n",
			pos->id, pos->node.prio, pos->value);
	}

	my_plist_del(&d1->node, &head);
	my_plist_del(&d2->node, &head);
	my_plist_del(&d3->node, &head);
	kfree(d1); kfree(d2); kfree(d3);
}

/* ========== 动态修改优先级（requeue） ========== */
static void demo_requeue(void)
{
	PLIST_HEAD(head);
	struct plist_data d1, d2, d3;

	plist_node_init(&d1.node, 10);
	plist_node_init(&d2.node, 20);
	plist_node_init(&d3.node, 30);

	my_plist_add(&d1.node, &head);
	my_plist_add(&d2.node, &head);
	my_plist_add(&d3.node, &head);

	/* 初始顺序: d1(10) > d2(20) > d3(30) */

	/* 将 d1 从 prio 10 改为 prio 40（最低），重新排序 */
	d1.node.prio = 40;
	my_plist_requeue(&d1.node, &head);

	/* 新顺序: d2(20) > d3(30) > d1(40) */
	pr_info("  after requeue d1 10->40, first prio=%d, last prio=%d\n",
		plist_first(&head)->prio, plist_last(&head)->prio);

	my_plist_del(&d1.node, &head);
	my_plist_del(&d2.node, &head);
	my_plist_del(&d3.node, &head);
}

/* ========== 真实场景模拟：RT 调度器 pushable_tasks ========== */
static void demo_rt_sched_pushable(void)
{
	/*
	 * 模拟内核 RT 调度器的 pushable_tasks：
	 * - 每个 RT task 有一个 pushable_node，按优先级排序
	 * - 便于快速找到最高优先级的可推送任务（下一个该迁往其他 CPU 的任务）
	 */
	PLIST_HEAD(pushable_tasks);
	struct plist_data tasks[5];
	int prios[] = { 50, 30, 70, 10, 90 };
	int i;

	for (i = 0; i < 5; i++) {
		tasks[i].id = (i + 1) * 100;
		tasks[i].value = prios[i];
		plist_node_init(&tasks[i].node, prios[i]);
		my_plist_add(&tasks[i].node, &pushable_tasks);
	}

	/* 获取最高优先级的可推送任务 */
	pr_info("  Highest prio pushable task: id=%d, prio=%d\n",
		plist_first_entry(&pushable_tasks, struct plist_data, node)->id,
		plist_first(&pushable_tasks)->prio);

	/* 模拟某个任务动态提升优先级后重新排序 */
	tasks[2].node.prio = 5;
	my_plist_requeue(&tasks[2].node, &pushable_tasks);
	pr_info("  after requeue task300 70->5, first task id=%d\n",
		plist_first_entry(&pushable_tasks, struct plist_data, node)->id);

	for (i = 0; i < 5; i++)
		my_plist_del(&tasks[i].node, &pushable_tasks);
}

static int __init plist_test_init(void)
{
	demo_basic_ops();
	demo_requeue();
	demo_rt_sched_pushable();
	return 0;
}

static void __exit plist_test_exit(void)
{
	pr_info("plist_test module exit\n");
}

module_init(plist_test_init);
module_exit(plist_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("plist demo module");

完整工程：linux_driver_learning/87_plist。plist 在内核中的实际用户是 RT 调度器的pushable_tasks（kernel/sched/rt.c）和 rt_mutex 的 PI 链，可以对照阅读。

---

llist — 无锁链表

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

头文件：<linux/llist.h>

数据结构：

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)	判断是否为空

典型模式：

// SPDX-License-Identifier: GPL-2.0
/* llist_test.c -- 无锁单链表：生产者无锁积压、消费者原子收割 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/llist.h>
#include <linux/slab.h>

struct llist_item {
	int val;
	struct llist_node node;
};

static LLIST_HEAD(my_llist);

static int __init llist_test_init(void)
{
	struct llist_item *items[5], *pos, *n;
	struct llist_node *list;
	int i;

	/* 生产者：头插法，无锁（中断上下文同样适用） */
	for (i = 0; i < 5; i++) {
		items[i] = kmalloc(sizeof(*items[i]), GFP_KERNEL);
		items[i]->val = i;
		llist_add(&items[i]->node, &my_llist);
	}

	/* 消费者：原子地摘下整个链表，再慢慢处理 */
	list = llist_del_all(&my_llist);

	/* 注意遍历顺序与插入顺序相反（头插法的特性） */
	llist_for_each_entry_safe(pos, n, list, node) {
		pr_info("  val=%d\n", pos->val);
		kfree(pos);
	}

	pr_info("  llist empty: %s\n", llist_empty(&my_llist) ? "yes" : "no");
	return 0;
}

static void __exit llist_test_exit(void)
{
	pr_info("llist_test module exit\n");
}

module_init(llist_test_init);
module_exit(llist_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("llist demo module");

---

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)	销毁

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* rhashtable_test.c -- 可自动扩缩容的 RCU 哈希表 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/rhashtable.h>
#include <linux/slab.h>

struct my_obj {
	int key;
	int value;
	struct rhash_head node;		/* 链入哈希桶 */
};

/* 描述 key/head 在宿主结构体中的位置 */
static const struct rhashtable_params my_params = {
	.key_offset		= offsetof(struct my_obj, key),
	.head_offset		= offsetof(struct my_obj, node),
	.key_len		= sizeof(int),
	.automatic_shrinking	= true,
};

static struct rhashtable my_ht;

/* 查找：读侧 RCU 无锁 */
static struct my_obj *my_lookup(int key)
{
	struct my_obj *obj;

	rcu_read_lock();
	obj = rhashtable_lookup(&my_ht, &key, my_params);
	rcu_read_unlock();
	return obj;
}

static void my_free(void *ptr, void *arg)
{
	kfree(ptr);
}

static int __init rhashtable_test_init(void)
{
	struct my_obj *obj, *found;
	int i;

	rhashtable_init(&my_ht, &my_params);

	for (i = 1; i <= 100; i++) {
		obj = kmalloc(sizeof(*obj), GFP_KERNEL);
		obj->key = i * 10;
		obj->value = i;
		rhashtable_insert_fast(&my_ht, &obj->node, my_params);
	}
	pr_info("  inserted 100 keys, nelems=%d\n", atomic_read(&my_ht.nelems));

	found = my_lookup(500);
	pr_info("  lookup 500 => value=%d\n", found ? found->value : -1);

	/* 删除并释放 */
	rhashtable_remove_fast(&my_ht, &found->node, my_params);
	kfree(found);

	found = my_lookup(500);
	pr_info("  lookup 500 after remove => %s\n", found ? "found" : "not found");

	return 0;
}

static void __exit rhashtable_test_exit(void)
{
	rhashtable_free_and_destroy(&my_ht, my_free, NULL);
	pr_info("rhashtable_test module exit\n");
}

module_init(rhashtable_test_init);
module_exit(rhashtable_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("rhashtable demo module");

内核中的典型应用：

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

---

maple_tree — 枫树（Maple Tree）

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

头文件：<linux/maple_tree.h>

数据结构：

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)	销毁

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* maple_tree_test.c -- 区间映射与遍历（VMA 管理同款结构） */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/maple_tree.h>

static struct maple_tree my_mt;

static int __init maple_test_init(void)
{
	MA_STATE(mas, &my_mt, 0, 0);
	unsigned long index = 35;
	void *entry;

	mt_init(&my_mt);

	/* 写入：mas_store 把 [index, last] 区间映射到 entry */
	mtree_lock(&my_mt);
	mas_set_range(&mas, 0, 9);
	mas_store(&mas, (void *)1UL);
	mas_set_range(&mas, 10, 19);
	mas_store(&mas, (void *)2UL);
	mas_set_range(&mas, 40, 49);
	mas_store(&mas, (void *)3UL);		/* 中间 20~39 留空洞 */
	mtree_unlock(&my_mt);

	/* mas_for_each 遍历所有非空区间 */
	mtree_lock(&my_mt);
	mas_for_each(&mas, entry, ULONG_MAX)
		pr_info("  [%lu - %lu] -> entry %lu\n",
			mas.index, mas.last, (unsigned long)entry);
	mtree_unlock(&my_mt);

	/* mt_find：从 index 开始找第一个非空条目并推进 index */
	entry = mt_find(&my_mt, &index, ULONG_MAX);
	pr_info("  mt_find from 35 => found at %lu, entry %lu\n",
		index, (unsigned long)entry);

	/* 删除包含 index 10 的区间 */
	mtree_lock(&my_mt);
	mas_set(&mas, 10);
	entry = mas_erase(&mas);
	mtree_unlock(&my_mt);
	pr_info("  erased entry %lu\n", (unsigned long)entry);

	return 0;
}

static void __exit maple_test_exit(void)
{
	mtree_destroy(&my_mt);
	pr_info("maple_test module exit\n");
}

module_init(maple_test_init);
module_exit(maple_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("maple tree demo module");

内核中的典型应用：

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

---

interval_tree — 区间树

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

头文件：<linux/interval_tree.h>

数据结构：

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)	查找下一个重叠区间

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* interval_tree_test.c -- 区间的插入与重叠查找 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/interval_tree.h>

static struct rb_root_cached my_tree = RB_ROOT_CACHED;
static struct interval_tree_node nodes[4];

static int __init interval_tree_test_init(void)
{
	unsigned long ranges[][2] = { {0, 9}, {10, 19}, {15, 24}, {40, 49} };
	struct interval_tree_node *node;
	int i;

	/* 插入：注意 10~19 与 15~24 部分重叠 */
	for (i = 0; i < 4; i++) {
		nodes[i].start = ranges[i][0];
		nodes[i].last = ranges[i][1];
		interval_tree_insert(&nodes[i], &my_tree);
	}

	/* 查找与 [16, 20] 重叠的所有区间：期望 10-19 和 15-24 */
	pr_info("  overlaps with [16, 20]:\n");
	for (node = interval_tree_iter_first(&my_tree, 16, 20); node;
	     node = interval_tree_iter_next(node, 16, 20))
		pr_info("    [%lu - %lu]\n", node->start, node->last);

	/* 删除一个区间后再次查找 */
	interval_tree_remove(&nodes[1], &my_tree);

	pr_info("  overlaps after removing [10, 19]:\n");
	for (node = interval_tree_iter_first(&my_tree, 16, 20); node;
	     node = interval_tree_iter_next(node, 16, 20))
		pr_info("    [%lu - %lu]\n", node->start, node->last);

	return 0;
}

static void __exit interval_tree_test_exit(void)
{
	pr_info("interval_tree_test module exit\n");
}

module_init(interval_tree_test_init);
module_exit(interval_tree_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("interval tree demo module");

内核中的典型应用：

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

---

klist — 内核对象链表

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

头文件：<linux/klist.h>

数据结构：

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)	清理迭代器

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* klist_test.c -- 带引用计数保护的内核对象链表 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/klist.h>
#include <linux/slab.h>

struct my_kitem {
	int id;
	struct klist_node n;
};

/* get/put 回调为 NULL：节点由我们手动管理 */
static struct klist my_klist = KLIST_INIT(my_klist, NULL, NULL);

static int __init klist_test_init(void)
{
	struct my_kitem *items[3];
	struct klist_iter iter;
	struct klist_node *kn;
	int i;

	for (i = 0; i < 3; i++) {
		items[i] = kmalloc(sizeof(*items[i]), GFP_KERNEL);
		items[i]->id = i;
		klist_add_tail(&items[i]->n, &my_klist);
	}

	/* 迭代器遍历：klist_next 会对返回的节点自动 get，
	 * 防止遍历过程中节点被其他 CPU 释放 */
	klist_iter_init(&my_klist, &iter);
	while ((kn = klist_next(&iter)) != NULL) {
		struct my_kitem *item = container_of(kn, struct my_kitem, n);
		pr_info("  id=%d\n", item->id);
	}
	klist_iter_exit(&iter);

	/* 删除中间节点 */
	klist_del(&items[1]->n);
	kfree(items[1]);

	klist_iter_init(&my_klist, &iter);
	while ((kn = klist_next(&iter)) != NULL)
		pr_info("  after del: id=%d\n",
			container_of(kn, struct my_kitem, n)->id);
	klist_iter_exit(&iter);

	klist_del(&items[0]->n);
	kfree(items[0]);
	klist_del(&items[2]->n);
	kfree(items[2]);

	return 0;
}

static void __exit klist_test_exit(void)
{
	pr_info("klist_test module exit\n");
}

module_init(klist_test_init);
module_exit(klist_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("klist demo module");

内核中的典型应用：

• 设备驱动模型中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)	初始化

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* idr_test.c -- 整数 ID 到指针的映射 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/idr.h>

static DEFINE_IDR(my_idr);

static int my_idr_cb(int id, void *ptr, void *data)
{
	pr_info("  id=%d -> obj%lu\n", id, (unsigned long)ptr);
	return 0;	/* 返回非 0 终止遍历 */
}

static int __init idr_test_init(void)
{
	void *p;
	int id, i;

	/* 分配 ID 并关联指针：范围 [1, 100) */
	for (i = 1; i <= 3; i++) {
		id = idr_alloc(&my_idr, (void *)(unsigned long)i, 1, 100, GFP_KERNEL);
		pr_info("  allocated id=%d -> obj%d\n", id, i);
	}

	/* 再分配一个 ID：idr 不去重指针，同一指针可关联多个 ID */
	id = idr_alloc(&my_idr, (void *)4UL, 1, 100, GFP_KERNEL);
	pr_info("  allocated id=%d -> obj4\n", id);

	p = idr_find(&my_idr, 2);
	pr_info("  idr_find(2) => obj%lu\n", (unsigned long)p);

	/* 遍历所有条目 */
	idr_for_each(&my_idr, my_idr_cb, NULL);

	/* 删除后 ID 可被复用 */
	idr_remove(&my_idr, 2);
	p = idr_find(&my_idr, 2);
	pr_info("  idr_find(2) after remove => %s\n", p ? "found" : "NULL");

	id = idr_alloc(&my_idr, (void *)5UL, 1, 100, GFP_KERNEL);
	pr_info("  next alloc reuses lowest free id=%d\n", id);

	return 0;
}

static void __exit idr_test_exit(void)
{
	idr_destroy(&my_idr);
	pr_info("idr_test module exit\n");
}

module_init(idr_test_init);
module_exit(idr_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("idr demo module");

内核中的典型应用：

• 进程 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)	销毁

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* ida_test.c -- 只分配唯一整数 ID（不关联指针） */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/idr.h>

static DEFINE_IDA(my_ida);

static int __init ida_test_init(void)
{
	int ids[5];
	int id, i;

	for (i = 0; i < 5; i++) {
		ids[i] = ida_alloc(&my_ida, GFP_KERNEL);
		pr_info("  allocated id=%d\n", ids[i]);
	}

	/* 释放中间的 id=2，形成空洞 */
	ida_free(&my_ida, ids[2]);
	pr_info("  freed id=%d\n", ids[2]);

	/* 下一次分配复用最小空洞 */
	id = ida_alloc(&my_ida, GFP_KERNEL);
	pr_info("  next id=%d (reuses hole)\n", id);
	ida_free(&my_ida, id);

	/* 范围分配：在 [100, 200) 内 */
	id = ida_alloc_range(&my_ida, 100, 200, GFP_KERNEL);
	pr_info("  range alloc id=%d\n", id);

	return 0;
}

static void __exit ida_test_exit(void)
{
	ida_destroy(&my_ida);
	pr_info("ida_test module exit\n");
}

module_init(ida_test_init);
module_exit(ida_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("ida demo module");

---

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

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* bitmap_test.c -- 位图操作与 cpumask 遍历 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/bitmap.h>
#include <linux/cpumask.h>
#include <linux/smp.h>

static int __init bitmap_test_init(void)
{
	DECLARE_BITMAP(my_bitmap, 64);
	cpumask_var_t cpu_mask;
	int bit, cpu;

	/* bitmap：置位 3~6，再逐位检查 */
	bitmap_zero(my_bitmap, 64);
	bitmap_set(my_bitmap, 3, 4);

	for_each_set_bit(bit, my_bitmap, 64)
		pr_info("  bit %d set\n", bit);

	/* 查找连续 4 个空闲位：期望 7 */
	bit = bitmap_find_next_zero_area(my_bitmap, 64, 0, 4, 0);
	pr_info("  next free area of 4 bits at %d\n", bit);

	/* cpumask：从在线 CPU 掩码中移除 CPU0 后遍历 */
	if (!alloc_cpumask_var(&cpu_mask, GFP_KERNEL))
		return -ENOMEM;

	cpumask_copy(cpu_mask, cpu_online_mask);
	cpumask_clear_cpu(0, cpu_mask);

	for_each_cpu(cpu, cpu_mask)
		pr_info("  cpu %d online (except cpu0)\n", cpu);

	free_cpumask_var(cpu_mask);
	return 0;
}

static void __exit bitmap_test_exit(void)
{
	pr_info("bitmap_test module exit\n");
}

module_init(bitmap_test_init);
module_exit(bitmap_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("bitmap/cpumask demo module");

内核中的典型应用：

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

---

scatterlist — 散布表

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

头文件：<linux/scatterlist.h>

数据结构：

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 映射

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* scatterlist_test.c -- 不连续内存段的描述与遍历 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/scatterlist.h>
#include <linux/mm.h>

static int __init sg_test_init(void)
{
	struct scatterlist sg[3];
	struct scatterlist *s;
	struct page *page;
	char buf[32];
	int i;

	/* 初始化表（末尾打上结束标记） */
	sg_init_table(sg, 3);

	/* 条目 0：描述一段 kmalloc/vmalloc 出来的虚拟连续缓冲 */
	sg_set_buf(&sg[0], buf, sizeof(buf));

	/* 条目 1：直接描述一个物理页 */
	page = alloc_page(GFP_KERNEL);
	if (!page)
		return -ENOMEM;
	sg_set_page(&sg[1], page, PAGE_SIZE, 0);

	/* 条目 2：留空，形成"已初始化但未使用"的槽位 */

	for_each_sg(sg, s, 3, i)
		pr_info("  sg[%d]: length=%u offset=%u\n",
			i, s->length, s->offset);

	__free_page(page);

	/*
	 * 真实 DMA 场景下，发起传输前还要做映射：
	 *   nents = dma_map_sg(dev, sg, 3, DMA_TO_DEVICE);
	 * 完成后：dma_unmap_sg(dev, sg, 3, DMA_TO_DEVICE);
	 * 映射会为每个条目填好 dma_address，供 DMA 引擎使用
	 */
	return 0;
}

static void __exit sg_test_exit(void)
{
	pr_info("sg_test module exit\n");
}

module_init(sg_test_init);
module_exit(sg_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("scatterlist demo module");

内核中的典型应用：

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

并发与同步

atomic_t — 原子变量

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

头文件：<linux/atomic.h>

数据结构：

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)	交换并返回旧值

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* atomic_test.c -- 原子变量：计数、dec_and_test 与 CAS */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/atomic.h>

static atomic_t counter = ATOMIC_INIT(0);

static int __init atomic_test_init(void)
{
	int old;

	atomic_inc(&counter);
	atomic_add(10, &counter);
	pr_info("  read=%d\n", atomic_read(&counter));

	/* dec_and_test：自减并测试是否到 0
	 * 典型用法：引用计数归零时触发清理 */
	atomic_set(&counter, 2);
	while (!atomic_dec_and_test(&counter))
		pr_info("  not zero yet: %d\n", atomic_read(&counter));
	pr_info("  reached zero\n");

	/* cmpxchg：CAS 原子更新（无锁编程的基础） */
	old = atomic_read(&counter);		/* 0 */
	if (atomic_cmpxchg(&counter, old, 42) == old)
		pr_info("  cas ok, now=%d\n", atomic_read(&counter));

	/* xchg：原子交换 */
	old = atomic_xchg(&counter, 100);
	pr_info("  xchg: old=%d, now=%d\n", old, atomic_read(&counter));

	return 0;
}

static void __exit atomic_test_exit(void)
{
	pr_info("atomic_test module exit\n");
}

module_init(atomic_test_init);
module_exit(atomic_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("atomic_t demo module");

内核中的典型应用：

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

---

kref / refcount_t — 引用计数

kref

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

头文件：<linux/kref.h>

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>

typedef struct refcount_struct {
    atomic_t refs;
} refcount_t;

典型使用模式：

// SPDX-License-Identifier: GPL-2.0
/* kref_test.c -- 引用计数：计数归零自动释放 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/kref.h>
#include <linux/slab.h>

struct my_object {
	struct kref kref;
	int data;
};

/* release 回调：最后一个引用被释放时调用 */
static void my_object_release(struct kref *kref)
{
	struct my_object *obj = container_of(kref, struct my_object, kref);

	pr_info("  release: refcount hit 0, freeing object\n");
	kfree(obj);
}

static struct my_object *my_object_get(struct my_object *obj)
{
	kref_get(&obj->kref);	/* 引用 +1，永不失败 */
	return obj;
}

static void my_object_put(struct my_object *obj)
{
	kref_put(&obj->kref, my_object_release);	/* 引用 -1，到 0 时释放 */
}

static int __init kref_test_init(void)
{
	struct my_object *obj, *alias;

	obj = kzalloc(sizeof(*obj), GFP_KERNEL);
	if (!obj)
		return -ENOMEM;
	obj->data = 42;
	kref_init(&obj->kref);			/* 引用 = 1 */
	pr_info("  created, refcount=%u\n", refcount_read(&obj->kref.refcount));

	alias = my_object_get(obj);		/* 引用 = 2 */
	pr_info("  after get, refcount=%u\n", refcount_read(&obj->kref.refcount));

	my_object_put(alias);			/* 引用 = 1，对象仍存活 */
	pr_info("  after put, refcount=%u\n", refcount_read(&obj->kref.refcount));

	my_object_put(obj);			/* 引用 = 0，触发 release 释放 */
	pr_info("  object freed\n");

	return 0;
}

static void __exit kref_test_exit(void)
{
	pr_info("kref_test module exit\n");
}

module_init(kref_test_init);
module_exit(kref_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("kref demo module");

内核中的典型应用：

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

---

spinlock_t — 自旋锁

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

头文件：<linux/spinlock.h>

数据结构（简化）：

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)	检查锁状态

warning

持有自旋锁期间绝不能睡眠（不能调用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

使用示例（两个内核线程对比「不加锁竞态 vs 加锁正确」）：

// SPDX-License-Identifier: GPL-2.0
/* spinlock_test.c -- 用竞态实验对比有无自旋锁的结果 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/spinlock.h>
#include <linux/kthread.h>
#include <linux/completion.h>
#include <linux/delay.h>

#define LOOPS 100000

static DEFINE_SPINLOCK(my_lock);
static int counter;
static DECLARE_COMPLETION(worker_done);

static int worker_fn(void *arg)
{
	bool use_lock = (bool)(unsigned long)arg;
	int i;

	for (i = 0; i < LOOPS; i++) {
		if (use_lock) {
			spin_lock(&my_lock);
			counter++;	/* 临界区：只能做短小的非睡眠操作 */
			spin_unlock(&my_lock);
		} else {
			counter++;	/* 非原子读-改-写，存在竞态 */
		}
	}
	complete(&worker_done);
	return 0;
}

static void run_pair(bool use_lock, const char *label)
{
	counter = 0;
	reinit_completion(&worker_done);

	kthread_run(worker_fn, (void *)(unsigned long)use_lock, "spin_worker_a");
	kthread_run(worker_fn, (void *)(unsigned long)use_lock, "spin_worker_b");

	wait_for_completion(&worker_done);
	wait_for_completion(&worker_done);

	pr_info("  %s: counter=%d (expect %d)\n", label, counter, LOOPS * 2);
}

static int __init spinlock_test_init(void)
{
	run_pair(false, "without lock");
	run_pair(true,  "with lock   ");
	return 0;
}

static void __exit spinlock_test_exit(void)
{
	pr_info("spinlock_test module exit\n");
}

module_init(spinlock_test_init);
module_exit(spinlock_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("spinlock demo module");

---

mutex — 互斥锁

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

头文件：<linux/mutex.h>

数据结构：

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)	检查状态

warning

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

spinlock 与 mutex 的选择：

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

使用示例（临界区内允许睡眠，这是 mutex 与 spinlock 的本质区别）：

// SPDX-License-Identifier: GPL-2.0
/* mutex_test.c -- 互斥锁保护可睡眠的临界区 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/mutex.h>
#include <linux/kthread.h>
#include <linux/completion.h>
#include <linux/delay.h>

static DEFINE_MUTEX(my_mutex);
static int shared_counter;
static DECLARE_COMPLETION(worker_done);

static int worker_fn(void *arg)
{
	int i;

	for (i = 0; i < 5; i++) {
		mutex_lock(&my_mutex);

		/* 临界区内可以睡眠（spinlock 绝对不允许） */
		shared_counter++;
		msleep(10);	/* 模拟耗时的可睡眠操作 */

		mutex_unlock(&my_mutex);
	}
	complete(&worker_done);
	return 0;
}

static int __init mutex_test_init(void)
{
	kthread_run(worker_fn, NULL, "mutex_worker_a");
	kthread_run(worker_fn, NULL, "mutex_worker_b");

	wait_for_completion(&worker_done);
	wait_for_completion(&worker_done);

	pr_info("  final counter=%d (expect 10)\n", shared_counter);
	return 0;
}

static void __exit mutex_test_exit(void)
{
	pr_info("mutex_test module exit\n");
}

module_init(mutex_test_init);
module_exit(mutex_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("mutex demo module");

---

completion — 完成量

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

头文件：<linux/completion.h>

数据结构：

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)	非阻塞尝试

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* completion_test.c -- 一个线程等待另一个线程完成任务 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/completion.h>
#include <linux/kthread.h>
#include <linux/delay.h>

static DECLARE_COMPLETION(work_done);

static int worker_fn(void *arg)
{
	msleep(100);	/* 模拟耗时任务 */

	pr_info("  worker: task done\n");
	complete(&work_done);		/* 单次事件用 complete */
	/* 如果有多个等待者，用 complete_all() */
	return 0;
}

static int __init completion_test_init(void)
{
	struct task_struct *tsk;

	tsk = kthread_run(worker_fn, NULL, "comp_worker");
	if (IS_ERR(tsk))
		return PTR_ERR(tsk);

	pr_info("  main: waiting for worker...\n");
	wait_for_completion(&work_done);	/* 阻塞直到 complete */
	pr_info("  main: worker finished, continue\n");

	return 0;
}

static void __exit completion_test_exit(void)
{
	pr_info("completion_test module exit\n");
}

module_init(completion_test_init);
module_exit(completion_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("completion demo module");

内核中的典型应用：

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

---

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

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

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

数据结构：

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 安全释放内存

典型模式：

// SPDX-License-Identifier: GPL-2.0
/* rcu_test.c -- 读者无锁、写者复制更新、延迟释放 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/rcupdate.h>
#include <linux/slab.h>

struct rcu_item {
	int version;
	struct rcu_head rcu;
};

static struct rcu_item __rcu *global_item;

/* 读者：完全无锁，只标记临界区范围 */
static int rcu_lookup(int *version)
{
	struct rcu_item *item;

	rcu_read_lock();
	item = rcu_dereference(global_item);	/* 与发布侧配对的读取 */
	if (item)
		*version = item->version;
	rcu_read_unlock();
	return item ? 0 : -1;
}

static int __init rcu_test_init(void)
{
	struct rcu_item *item, *old;
	int v = -1;

	/* 发布 v1 */
	item = kzalloc(sizeof(*item), GFP_KERNEL);
	item->version = 1;
	rcu_assign_pointer(global_item, item);	/* 保证先初始化后发布 */

	rcu_lookup(&v);
	pr_info("  after publish: version=%d
", v);

	/* 更新到 v2：分配新副本 -> 原子替换 -> 延迟释放旧副本 */
	item = kzalloc(sizeof(*item), GFP_KERNEL);
	item->version = 2;
	old = rcu_access_pointer(global_item);
	rcu_assign_pointer(global_item, item);
	kfree_rcu(old, rcu);	/* 宽限期结束后才真正释放旧对象 */

	rcu_lookup(&v);
	pr_info("  after update: version=%d
", v);

	return 0;
}

static void __exit rcu_test_exit(void)
{
	/* synchronize_rcu 等待所有读者退出后再释放 */
	synchronize_rcu();
	kfree_rcu(rcu_dereference_raw(global_item), rcu);
	pr_info("rcu_test module exit
");
}

module_init(rcu_test_init);
module_exit(rcu_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("rcu demo module");

内核中的典型应用：

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

---

---

等待与调度

wait_queue — 等待队列

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

头文件：<linux/wait.h>

数据结构：

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 个等待者

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* waitqueue_test.c -- 内核线程阻塞等待，被事件唤醒 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/wait.h>
#include <linux/kthread.h>
#include <linux/completion.h>
#include <linux/delay.h>

static DECLARE_WAIT_QUEUE_HEAD(my_wq);
static int data_ready;
static DECLARE_COMPLETION(waiter_done);

static int waiter_fn(void *arg)
{
	pr_info("  waiter: going to sleep\n");

	/* 阻塞直到 data_ready != 0（被唤醒后自动重新检查条件） */
	wait_event_interruptible(my_wq, data_ready != 0);

	pr_info("  waiter: woken up, data_ready=%d\n", data_ready);
	complete(&waiter_done);
	return 0;
}

static int __init waitqueue_test_init(void)
{
	kthread_run(waiter_fn, NULL, "wq_waiter");

	msleep(100);	/* 等线程睡下 */

	/* 唤醒侧：先改条件，再唤醒 */
	data_ready = 1;
	wake_up_interruptible(&my_wq);

	wait_for_completion(&waiter_done);
	return 0;
}

static void __exit waitqueue_test_exit(void)
{
	pr_info("waitqueue_test module exit\n");
}

module_init(waitqueue_test_init);
module_exit(waitqueue_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("wait queue demo module");

内核中的典型应用：

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

---

work_struct / workqueue — 工作队列

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

头文件：<linux/workqueue.h>

数据结构：

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)	创建有序工作队列

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* workqueue_test.c -- 普通工作 + 延迟工作 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/workqueue.h>

static void my_work_handler(struct work_struct *work)
{
	pr_info("  work running in process context (can sleep)\n");
}

static void my_delayed_handler(struct work_struct *work)
{
	pr_info("  delayed work fired after 200ms\n");
}

static DECLARE_WORK(my_work, my_work_handler);
static DECLARE_DELAYED_WORK(my_dwork, my_delayed_handler);

static int __init workqueue_test_init(void)
{
	/* 调度到系统工作队列（也可用 queue_work 提交到自定义队列） */
	schedule_work(&my_work);

	/* 200ms 后执行 */
	schedule_delayed_work(&my_dwork, msecs_to_jiffies(200));

	/* 等两个工作都执行完（验证输出顺序） */
	flush_work(&my_work);
	flush_delayed_work(&my_dwork);

	return 0;
}

static void __exit workqueue_test_exit(void)
{
	cancel_work_sync(&my_work);
	cancel_delayed_work_sync(&my_dwork);
	pr_info("workqueue_test module exit\n");
}

module_init(workqueue_test_init);
module_exit(workqueue_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("workqueue demo module");

内核中的典型应用：

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

---

timer_list — 内核定时器

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

头文件：<linux/timer.h>

数据结构：

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)	检查是否已提交

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* timer_test.c -- jiffies 级周期定时器（tick 3 次后自动停止） */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/timer.h>
#include <linux/jiffies.h>
#include <linux/delay.h>

static struct timer_list my_timer;
static int n;

/* 回调运行在软中断上下文：不能睡眠 */
static void my_timer_cb(struct timer_list *t)
{
	n++;

	if (n < 3) {
		pr_info("  tick %d\n", n);
		/* 周期定时器：重新武装自己 */
		mod_timer(t, jiffies + msecs_to_jiffies(100));
	} else {
		pr_info("  tick %d, stopping\n", n);
	}
}

static int __init timer_test_init(void)
{
	timer_setup(&my_timer, my_timer_cb, 0);
	mod_timer(&my_timer, jiffies + msecs_to_jiffies(100));

	msleep(500);	/* 等定时器跑完 */
	return 0;
}

static void __exit timer_test_exit(void)
{
	del_timer_sync(&my_timer);
	pr_info("timer_test module exit\n");
}

module_init(timer_test_init);
module_exit(timer_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("timer_list demo module");

内核中的典型应用：

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

---

hrtimer — 高精度定时器

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

头文件：<linux/hrtimer.h>

数据结构：

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)	从当前时间向前推进

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* hrtimer_test.c -- 纳秒级周期高精度定时器 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/hrtimer.h>
#include <linux/ktime.h>
#include <linux/delay.h>

static struct hrtimer my_hrtimer;
static ktime_t period;
static int n;

static enum hrtimer_restart my_hrtimer_cb(struct hrtimer *timer)
{
	if (++n < 3) {
		pr_info("  hrtimer tick %d\n", n);
		hrtimer_forward_now(timer, period);
		return HRTIMER_RESTART;
	}
	pr_info("  hrtimer tick %d, stopping\n", n);
	return HRTIMER_NORESTART;
}

static int __init hrtimer_test_init(void)
{
	period = ns_to_ktime(1000000);	/* 1ms */

	hrtimer_init(&my_hrtimer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
	my_hrtimer.function = my_hrtimer_cb;
	hrtimer_start(&my_hrtimer, period, HRTIMER_MODE_REL);

	msleep(10);	/* 等定时器跑完 */
	return 0;
}

static void __exit hrtimer_test_exit(void)
{
	hrtimer_cancel(&my_hrtimer);
	pr_info("hrtimer_test module exit\n");
}

module_init(hrtimer_test_init);
module_exit(hrtimer_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("hrtimer demo module");

内核中的典型应用：

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

---

---

设备模型与通知

kobject / kset — 内核对象模型

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

头文件：<linux/kobject.h>

数据结构：

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

使用示例（加载后cat /sys/kernel/my_kobj/hello）：

// SPDX-License-Identifier: GPL-2.0
/* kobject_test.c -- 在 /sys/kernel 下创建目录和属性文件 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/kobject.h>
#include <linux/sysfs.h>

static struct kobject *my_kobj;

static ssize_t hello_show(struct kobject *kobj,
			  struct kobj_attribute *attr, char *buf)
{
	return sprintf(buf, "hello from my_kobj\n");
}

/* __ATTR_RO(name)：只读属性，自动绑定 <name>_show 回调 */
static struct kobj_attribute hello_attr = __ATTR_RO(hello);

static int __init kobject_test_init(void)
{
	int ret;

	/* 创建 /sys/kernel/my_kobj/（kernel_kobj 是 /sys/kernel） */
	my_kobj = kobject_create_and_add("my_kobj", kernel_kobj);
	if (!my_kobj)
		return -ENOMEM;

	ret = sysfs_create_file(my_kobj, &hello_attr.attr);
	if (ret) {
		kobject_put(my_kobj);
		return ret;
	}

	pr_info("  see /sys/kernel/my_kobj/hello\n");
	return 0;
}

static void __exit kobject_test_exit(void)
{
	/* kobject_put 引用归零时自动从 sysfs 移除目录 */
	kobject_put(my_kobj);
	pr_info("kobject_test module exit\n");
}

module_init(kobject_test_init);
module_exit(kobject_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("kobject demo module");

内核中的典型应用：

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

---

notifier_block — 通知链

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

头文件：<linux/notifier.h>

数据结构：

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 保护）	是

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* notifier_test.c -- 自建通知链：发布-订阅 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/notifier.h>

#define MY_EVENT_FOO	0x0001
#define MY_EVENT_BAR	0x0002

/* 自建的阻塞通知链头 */
static BLOCKING_NOTIFIER_HEAD(my_chain);

/* 订阅者回调 */
static int my_notifier_fn(struct notifier_block *nb,
			  unsigned long event, void *data)
{
	pr_info("  event 0x%04lx received, data=%s\n", event, (char *)data);
	return NOTIFY_OK;	/* NOTIFY_DONE / NOTIFY_OK / NOTIFY_BAD */
}

static struct notifier_block my_nb = {
	.notifier_call	= my_notifier_fn,
};

static int __init notifier_test_init(void)
{
	/* 订阅 */
	blocking_notifier_chain_register(&my_chain, &my_nb);

	/* 发布两个事件给链上所有订阅者 */
	blocking_notifier_call_chain(&my_chain, MY_EVENT_FOO, "hello");
	blocking_notifier_call_chain(&my_chain, MY_EVENT_BAR, "world");

	return 0;
}

static void __exit notifier_test_exit(void)
{
	blocking_notifier_chain_unregister(&my_chain, &my_nb);
	pr_info("notifier_test module exit\n");
}

module_init(notifier_test_init);
module_exit(notifier_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("notifier chain demo module");

内核中的典型应用：

• 内核恐慌（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)	释放内存

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* kfifo_test.c -- 无锁环形 FIFO（单读单写场景） */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/kfifo.h>

/* 大小必须是 2 的幂 */
static DECLARE_KFIFO(my_fifo, int, 16);

static int __init kfifo_test_init(void)
{
	int val, out, i;

	INIT_KFIFO(my_fifo);

	/* 单元素入队 */
	for (i = 0; i < 8; i++) {
		val = i * 3;
		if (!kfifo_put(&my_fifo, val))
			pr_info("  fifo full, put %d failed\n", val);
	}
	pr_info("  len=%d\n", kfifo_len(&my_fifo));

	/* 出队：顺序与入队一致 */
	while (kfifo_get(&my_fifo, &out))
		pr_info("  got %d\n", out);

	pr_info("  empty=%s full=%s\n",
		kfifo_is_empty(&my_fifo) ? "yes" : "no",
		kfifo_is_full(&my_fifo) ? "yes" : "no");

	/* 批量入队/出队（kfifo_in/kfifo_out 按字节操作） */
	{
		int in_buf[4] = { 1, 2, 3, 4 };
		int out_buf[4];
		unsigned int n;

		n = kfifo_in(&my_fifo, in_buf, sizeof(in_buf));
		n = kfifo_out(&my_fifo, out_buf, n);
		for (i = 0; i < (int)(n / sizeof(int)); i++)
			pr_info("  bulk got %d\n", out_buf[i]);
	}

	return 0;
}

static void __exit kfifo_test_exit(void)
{
	pr_info("kfifo_test module exit\n");
}

module_init(kfifo_test_init);
module_exit(kfifo_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("kfifo demo module");

内核中的典型应用：

• 串口驱动的收发缓冲区
• 音频驱动的 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

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* percpu_test.c -- 静态与动态 per-CPU 变量 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/percpu.h>
#include <linux/smp.h>

static DEFINE_PER_CPU(int, my_counter);
static int __percpu *dynamic_counter;

static int __init percpu_test_init(void)
{
	int cpu, sum = 0;

	/* 静态定义的 per-CPU 变量：本 CPU 原子递增，无需加锁 */
	this_cpu_inc(my_counter);
	this_cpu_add(my_counter, 10);

	/* 汇总所有 CPU 的副本 */
	for_each_possible_cpu(cpu)
		sum += per_cpu(my_counter, cpu);
	pr_info("  static percpu sum=%d
", sum);

	/* 动态分配 */
	dynamic_counter = alloc_percpu(int);
	if (!dynamic_counter)
		return -ENOMEM;

	for_each_possible_cpu(cpu)
		per_cpu(*dynamic_counter, cpu) = cpu * 100;

	cpu = get_cpu();	/* 禁止抢占，防止执行过程中被迁移 */
	pr_info("  running on cpu%d, local value=%d
",
		cpu, per_cpu(*dynamic_counter, cpu));
	put_cpu();

	return 0;
}

static void __exit percpu_test_exit(void)
{
	free_percpu(dynamic_counter);
	pr_info("percpu_test module exit
");
}

module_init(percpu_test_init);
module_exit(percpu_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("percpu demo module");

内核中的典型应用：

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

---

circ_buf — 环形缓冲区宏

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

头文件：<linux/circ_buf.h>

数据结构：

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)	到缓冲区末尾的连续空间

使用示例：

// SPDX-License-Identifier: GPL-2.0
/* circ_buf_test.c -- 用宏实现轻量环形缓冲区 */

#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/circ_buf.h>

#define BUF_SIZE	64		/* 必须是 2 的幂 */

static char buf[BUF_SIZE];
static int head, tail;

static int __init circ_buf_test_init(void)
{
	char msg[] = "hello";
	int i;

	pr_info("  initial: space=%d cnt=%d\n",
		CIRC_SPACE(head, tail, BUF_SIZE),
		CIRC_CNT(head, tail, BUF_SIZE));

	/* 生产者：写入前先检查空间（宏保证索引回绕安全） */
	for (i = 0; i < (int)sizeof(msg); i++) {
		if (!CIRC_SPACE(head, tail, BUF_SIZE)) {
			pr_info("  buffer full\n");
			break;
		}
		buf[head] = msg[i];
		head = (head + 1) & (BUF_SIZE - 1);
	}

	/* 消费者 */
	while (CIRC_CNT(head, tail, BUF_SIZE)) {
		pr_info("  got '%c'\n", buf[tail]);
		tail = (tail + 1) & (BUF_SIZE - 1);
	}

	return 0;
}

static void __exit circ_buf_test_exit(void)
{
	pr_info("circ_buf_test module exit\n");
}

module_init(circ_buf_test_init);
module_exit(circ_buf_test_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("even629");
MODULE_DESCRIPTION("circ_buf demo module");

内核中的典型应用：

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

---

flex_array — 柔性数组

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

warning

从 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>

数据结构（大幅简化）：

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>

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 — 虚拟内存区域

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

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>

数据结构（简化）：

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使用四指针模型管理数据空间：

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实现简析