企业官网建设流程全解析

在内核里写业务逻辑，绕不开一个很朴素的问题：手头有一大堆动态对象，可能是设备实例、回调句柄、缓存项，怎么用最快的速度按编号找回来，又怎么保证多核并发下不炸。链表找一轮是O(n)，红黑树用起来琐碎，哈希要自己管冲突和扩容。我最早写驱动时都用最笨的数组加位图，直到后来认真读了xarray——Linux内核从4.17开始提供的一个通用数据结构/工具类，底层是一棵基数树，对外却是一套“整数索引到指针”的干净API，page cache、IDR这些核心子系统都从radix tree迁移到了它上面。

这篇东西面向的是想在内核模块、驱动或文件系统代码里优雅管理对象集合的开发者。如果你是刚接触内核编程，也能把它当一份xarray入门手册用，从API调用到并发细节到坑，一次讲透。

1. 从radix tree到xarray：内核为什么专门造一个“指针管理工具”

1.1 它其实是一个数学意义上的稀疏数组

先打个比方。你在用户态写程序，要按学号找人，最直接的想法是开一个足够大的数组，数组下标就是学号。问题是学号可能从1号到一亿号，但实际只有几百人，为几百人开一亿个槽位太浪费了——这就是稀疏数组的困境。

xarray解决的就是这个问题。它在语义上让你觉得“我按下标存了一堆指针”，底层却不会为空洞浪费内存。树上的每一层按固定宽度切分下标，64位系统上一个内部节点通常能分流64个分支，深度最多也就几层。你按下标找指针，就是在这些分支里走下去，找到叶子槽位。

更难得的是，它保留了稀疏数组的随机访问能力：xa_load按下标取值是O(log n)级别，而老的链表方案是O(n)，差距在十万级条目下非常明显。所以xarray在内核里的定位很明确——这就是一个通用的、专门管“一堆有索引的指针”的工具类，你不用再重复造轮子。

1.2 radix tree 的麻烦：API和内存管理都别扭

xarray的前身就是我们熟悉的radix tree。radix tree本身很好用，但它有几个很实际的问题，几乎所有写过相关代码的人都会碰到：

第一，API割裂严重。radix tree既支持radix_tree_insert、radix_tree_lookup这种面向指针的操作，又因为要兼容page cache的场景，弄出了一套需要手动维护slot指针的迭代器（radix_tree_for_each_slot）。新手很难一次写对，老手也经常要翻头文件确认参数含义。

第二，插入路径的内存预分配特别麻烦。在原子上下文往radix tree里插入条目时，你不能随便kmalloc，否则可能睡眠。老内核的解法是让你提前调用radix_tree_preload，把要用的节点预先塞进per-CPU缓存，然后关掉抢占进入临界区操作。这套东西写起来啰嗦，漏一次就是半夜日志里一句莫名其妙的“BUG: sleeping function called from invalid context”。

第三，节点内部结构的空间利用率不够好。radix tree的年代主要是为page cache优化的，tag标记用了几组bitmap但彼此独立，空节点回收也不够聪明。内核开发者们在4.17前后终于决定做一个新的替代品，同时把多年积累的经验吸收进去，这就是xarray。

1.3 内核里大规模换装的底气：page cache与IDR

判断一个内核工具类是否靠谱，最硬的指标不是文档写得多好，而是内核自己敢不敢大规模用。xarray 4.17落地后，最重头的迁移有两个：

一个是page cache。每个address_space对象里原来有个radix tree管理所有缓存页，现在改成了struct xarray i_pages。文件读写是最热的热路径，page cache换装xarray并且多年来没有出大问题，这本身就说明了性能。

另一个是IDR。老内核里用IDR管理设备号、inode编号这类“整数ID到对象指针”的映射，IDR自己又是一套独立实现。xarray出现后，IDR干脆退居二线，直接在xarray上做了一层薄封装，核心就是XA_FLAGS_ALLOC加xa_alloc。你现在去翻最新内核的lib/idr.c，能清楚地看到这层关系。

这两次换装给外部的教训很直接：如果你的模块里还在折腾自己的idr、自己的radix tree、自己的稀疏数组，完全可以考虑往xarray上迁移。内核自己都把最核心的子系统换掉了，你还犹豫什么。

1.4 选型参考：xarray vs 链表 vs rbtree vs 哈希表

我做选型的时候习惯把选项摆在一张表里对比，不迷信某一个结构：

xarray的另一个隐藏优势是它允许在树节点上打标记（mark），做“带状态过滤的遍历”特别方便。后面我会专门讲mark的用法。总之，当你的key本身就是整数、而且订阅顺序就是下标顺序时，xarray基本是最舒服的选择。

2. 入门xarray：一套会自己加锁的业务API

2.1 初始化与flags选择

xarray的使用门槛低到让人怀疑自己用错了库。定义一把“数组”只有两种常见姿势。

如果你需要一个静态定义的表，直接：

static DEFINE_XARRAY(my_table);

如果你需要在模块入口函数里动态初始化，或者要指定flag，这样写：

static struct xarray my_table; static int __init my_init(void) { /* 0表示不附带任何特殊能力 */ xa_init(&my_table); /* 或者：初始化并开启ID自动分配能力 */ xa_init_flags(&my_table, XA_FLAGS_ALLOC); }

这里最常用的flag就是XA_FLAGS_ALLOC，开了它之后你才能用xa_alloc自动分配一个不重复的ID，而不是自己手工维护“下一个ID是多少”。这对对象注册表场景是刚需。

另外两个flag值得知道：XA_FLAGS_LOCK_IRQ和XA_FLAGS_LOCK_BH。它们影响的是xarray内部锁的变体，在中断上下文或bottom half上下文使用xarray时建议开启对应的flag，让内部锁切换到irqsave版本，避免中断打断自旋锁持有者导致死锁。

2.2 增删查：xa_store / xa_load / xa_erase

三个最核心的API长这样：

int xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp); void *xa_load(struct xarray *xa, unsigned long index); void *xa_erase(struct xarray *xa, unsigned long index);

简单到不需要解释。但我建议你记住几个容易忽略的点：

• xa_store返回0表示成功，返回负数是由GFP_KERNEL分配节点失败或参数非法导致的错误。如果你写入的entry本身是ERR_PTR类的错误指针，返回的也可能是这类特殊指针，判断时用xa_is_err而不是简单的IS_ERR，语义更清晰。
• xa_load在槽位为空时返回NULL，但是要注意：NULL和“我存了一个NULL”是一样的，因为xarray不允许用NULL作为有效entry。想存“空”就什么都不存。
• xa_erase等价于执行一次xa_store(xa, index, NULL, GFP_KERNEL)，返回值是被删掉的旧entry。如果返回NULL，说明这个下标本来就没有东西，这时候做对象释放要格外小心，别把NULL当真指针free了。

我自己写代码时一个习惯是，错误路径和空路径单独打日志，尤其是xa_erase返回NULL的情况，多半意味着你的ID管理逻辑有漏洞。

2.3 NULL、内部entry与value entry

这一节是入门者最容易踩的雷。xarray的槽位不只是能存普通指针，它内部还约定了两种特殊内容：

第一种叫内部entry。内核在实现xarray时需要一些占位符，比如XA_ZERO_ENTRY、XA_RETRY_ENTRY。这些值和普通指针长得很像，但低位有特殊编码。判断一个返回值到底是普通业务指针还是内部占位符，用xa_is_internal来查。普通开发者绝大多数情况不会直接碰到内部entry，但在遍历大表时如果看到某个entry长得不对劲，先怀疑这里。

第二种是value entry。有时候你想在槽位里直接存一个小整数，比如一个状态码，不想为了它单独创建一个结构体再记一次kzalloc/kfree。这时可以用：

xa_store(&table, index, xa_mk_value(12345), GFP_KERNEL); unsigned long val = xa_to_value(xa_load(&table, index));

判断是不是value entry用xa_is_value。这是xarray一个很聪明的设计：直接把整数值编码进指针空间，省掉一次堆分配。代价是存入的整数不能太大，受指针可用位数限制（64位上非常宽裕）。

2.4 遍历与查找：xa_for_each家族

遍历一个xarray全表，最常用的宏是：

unsigned long index; struct my_obj *obj; xa_for_each(&my_table, index, obj) { pr_info("index %lu -> %s\n", index, obj->name); }

注意，这个宏只会遍历“实际有值的槽位”，空洞会被自动跳过。它以升序遍历下标，内部调用的xa_find/xa_find_after会自己处理RCU读锁，所以在读多写少的场景下直接用很安全。

如果你只关心某些打了标记的条目，用xa_for_each_marked：

xa_for_each_marked(&my_table, index, obj, XA_MARK_0) { /* 只有打了 XA_MARK_0 标记的条目会被遍历到 */ }

除了全表遍历，还有两个查询函数值得记住：

• xa_find(xa, &index, max, filter)：从index开始找下一个符合条件的entry，并把index更新为实际找到的下标。
• xa_find_after(xa, &index, max, filter)：和上面类似，但是从index之后开始找。

这两个函数是实现“分批拉取”“续传遍历”的利器。filter参数传XA_PRESENT就是找任意存在的条目，传XA_MARK_0就是找带标记的条目。

2.5 给条目打标签：xarray的marks

xarray还在每个条目上预留了3个标记位：XA_MARK_0、XA_MARK_1、XA_MARK_2。这个设计非常有价值，很多场景你会需要一个“状态”挂在对象上，又不想改对象结构体。

举一个具体例子，你在驱动里缓存了一批网络会话，想把“需要写回”的会话挑出来统一刷盘。传统做法是在对象结构体里加一个bool：dirty，遍历时逐个判断。xarray的做法更优雅：

xa_set_mark(&table, session_id, XA_MARK_0); // 标记为脏 xa_clear_mark(&table, session_id, XA_MARK_0); // 清除脏标记 bool is_dirty = xa_get_mark(&table, session_id, XA_MARK_0);

配合xa_for_each_marked，你只需要“精确地刷那些脏的”，不用把全表翻一遍。而且这三个标记是xarray数据结构自带的，连额外的内存都不用你管。

3. 实战：把xarray封装成驱动里的对象注册工具类

3.1 面向的业务场景与设计目标

我最早想用xarray替换一段“自己用数组+位图维护ID”的代码，场景很典型：一个内核模块要管理多种后端处理器，每个处理器注册时分配一个唯一ID，上层通过ID快速找到处理器，还能遍历所有已注册项。旧实现需要维护：空闲位图、ID到对象的数组、并发锁。三个东西联动，代码一多就容易漏锁。

用xarray做同样的事，核心设计目标变成一句话：只维护一个xarray，其余映射逻辑全交给它。自动分配ID用xa_alloc，按ID找对象用xa_load，注销用xa_erase，遍历用xa_for_each，内存生命周期的并发保护交给RCU加kfree_rcu。

这个方案还有一个额外好处：ID不会因为模块反复注册注销而碎片化。xarray的xa_alloc会从低到高复用空闲ID，老数组加位图的方法虽然也能做，但代码一多就容易在边界条件上翻车。

3.2 完整模块代码：xtool

下面是一个可以直接编译加载的内核模块，功能就是“对象注册表”。你可以把它当成一个最小可用的xarray工具类模板，后续往里面填自己的业务字段就行。

#include <linux/init.h> #include <linux/kernel.h> #include <linux/module.h> #include <linux/slab.h> #include <linux/string.h> #include <linux/xarray.h> #define XTOOL_NAME "xtool" #define XTOOL_OBJNAME 64 struct xtool_object { struct rcu_head rcu; /* 配合 kfree_rcu 使用，必须放在结构体里 */ u32 id; unsigned long flags; char name[XTOOL_OBJNAME]; }; static struct xarray xtool_objects; static int xtool_create(const char *name, unsigned long flags, u32 *out_id) { struct xtool_object *obj; u32 id; int ret; obj = kzalloc(sizeof(*obj), GFP_KERNEL); if (!obj) return -ENOMEM; strscpy(obj->name, name, sizeof(obj->name)); obj->flags = flags; /* xa_alloc 会自动分配一个不冲突的ID，范围为0~U32_MAX */ ret = xa_alloc(&xtool_objects, &id, obj, xa_limit_32b, GFP_KERNEL); if (ret) { kfree(obj); return ret; } obj->id = id; if (out_id) *out_id = id; pr_info("%s: created object #%u (%s)\n", XTOOL_NAME, id, name); return 0; } static struct xtool_object *xtool_find(u32 id) { return xa_load(&xtool_objects, id); } static int xtool_remove(u32 id) { struct xtool_object *obj; obj = xa_erase(&xtool_objects, id); if (!obj) return -ENOENT; /* 其他CPU可能正通过RCU读侧访问这个对象，必须等宽限期结束再释放 */ kfree_rcu(obj, rcu); pr_info("%s: removed object #%u\n", XTOOL_NAME, id); return 0; } static void xtool_dump(void) { unsigned long index; struct xtool_object *obj; pr_info("%s: dump table\n", XTOOL_NAME); xa_for_each(&xtool_objects, index, obj) pr_info(" [%lu] id=%u name=%s flags=0x%lx\n", index, obj->id, obj->name, obj->flags); } static int __init xtool_init(void) { u32 id1 = 0, id2 = 0, id3 = 0; xa_init_flags(&xtool_objects, XA_FLAGS_ALLOC); if (xtool_create("handler-netlink", 0x01, &id1)) return -ENOMEM; if (xtool_create("handler-ioctl", 0x02, &id2)) return -ENOMEM; if (xtool_create("handler-notify", 0x04, &id3)) return -ENOMEM; xtool_dump(); if (xtool_find(id1)) pr_info("%s: find object #%u ok\n", XTOOL_NAME, id1); if (xtool_remove(id1) == 0) pr_info("%s: removed %u, dump again\n", XTOOL_NAME, id1); xtool_dump(); pr_info("%s: loaded\n", XTOOL_NAME); return 0; } static void __exit xtool_exit(void) { unsigned long index; struct xtool_object *obj; xa_for_each(&xtool_objects, index, obj) { obj = xa_erase(&xtool_objects, index); if (obj) kfree_rcu(obj, rcu); } /* xa_destroy 只重置xarray本身，业务对象已经在上面释放完了 */ xa_destroy(&xtool_objects); pr_info("%s: unloaded\n", XTOOL_NAME); } module_init(xtool_init); module_exit(xtool_exit); MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("xarray based object registry demo");

几点说明：

• xa_alloc的ID参数类型是u32 *，我用局部变量id接收，再存进对象结构体。不要在xa_alloc里直接传&obj->id之外的野指针。
• xa_limit_32b表示ID范围是 0 到 U32_MAX，如果你希望ID从1开始，可以用XA_LIMIT(1, U32_MAX)。这个上限要按业务定，别懒。
• strscpy比strcpy/sprintf安全，拷贝不会越界。内核里写字符串拷贝尽量用它。

3.3 编译、加载与日志验证

在模块源码同级目录放一个Makefile：

obj-m += xtool.o KDIR := /lib/modules/$(shell uname -r)/build PWD := $(shell pwd) all: $(MAKE) -C $(KDIR) M=$(PWD) modules clean: $(MAKE) -C $(KDIR) M=$(PWD) clean

然后执行：

make sudo insmod xtool.ko sudo dmesg | tail -n 30

如果内核版本是4.17以上、又装了对应headers，这段代码能直接编译通过。加载后dmesg里应该能看到创建、查找、删除和两次dump的输出。最后卸载：

sudo rmmod xtool sudo dmesg | tail -n 5

重点看一下卸载日志里的顺序：先遍历删除所有对象，再xa_destroy清空xarray本身。如果反过来先xa_destroy再遍历，你手里就只剩一个空表了，业务对象全部泄漏。

3.4 向“工具类”演进：抽取成通用接口的思路

上面的代码还只是单个模块里的私有实现。如果多个模块都要用这套注册表，我会把它再抽一层，做成真正的“工具类”：

• 结构体xtool_table内部持有struct xarray xa，外部不直接碰xarray。
• 提供xtool_table_init、xtool_obj_add、xtool_obj_get、xtool_obj_del、xtool_for_each这几个接口。
• 对象的释放回调作为参数传入，xtool_obj_del在拿到旧entry后调用回调完成内存释放。
• 内部统一用kfree_rcu走RCU宽限期，上层完全不用关心并发释放的细节。

这个封装思路是所有“工