Linux 内核 IDR/IDA 标识符分配机制完全指南从 ID 到指针的映射与高效位图分配【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linux本文以内核文档 Documentation/core-api/idr.rst 为主线结合 include/linux/idr.h 与 lib/idr.c 的源码实现系统讲解 Linux 内核中统一 ID 分配的两套设施IDRID Radix treeID 到指针映射与IDAID Allocator纯 ID 分配器。读完本文你将掌握二者的适用场景、全部核心 API 的参数与返回值语义、同步与预加载的正确姿势并通过内核测试用例与真实驱动用法获得可直接落地的实战能力。一、为什么内核需要统一的 ID 分配设施内核中给某样东西分配一个标识符ID是极其常见的需求文件描述符、进程号、网络协议中的报文标识、SCSI tag、设备实例号本质上都是用一个小整数去唯一标识一个对象。如果每个子系统都各自实现一套分配逻辑不仅容易出错还会造成功能重复。IDR 与 IDA 正是内核为此提供的通用解决方案IDR提供 ID 到指针void *的映射能力即给定 ID 查对象、给定对象分 ID的双向服务IDA只做 ID 分配/释放不保存任何指针因此每个 ID 只需占用 1 个 bit内存效率远高于 IDR。两者底层分别构建在 radix tree 与 XArray 之上。需要特别注意的是IDR 接口已被标记为废弃deprecated官方建议新代码改用 XArray见 Documentation/core-api/xarray.rst但 IDR 在内核中仍有大量存量使用者理解其语义对于阅读和维护这些代码依然必要。二、IDR 核心数据结构与初始化从源码看struct idr只包含三个字段include/linux/idr.h#L20-L24struct idr { struct radix_tree_root idr_rt; /* 底层 radix tree 根 */ unsigned int idr_base; /* 分配起始基数 */ unsigned int idr_next; /* 循环分配器的游标 */ };其中idr_base使得 IDR 可以从指定基数值开始分配内部 radix tree 索引统一按id - idr_base折算idr_next则是idr_alloc_cyclic()的循环游标可通过idr_get_cursor()/idr_set_cursor()读写include/linux/idr.h#L67-L83。初始化 IDR 有两条路径对应静态与动态分配两种场景/* 静态定义一个即可直接使用无需额外初始化 */ DEFINE_IDR(my_idr); /* 动态运行时初始化 */ struct idr my_idr; idr_init(my_idr); /* 变体指定分配基数ID 将从 base 开始分配 */ idr_init_base(my_idr, 100);实现细节上DEFINE_IDR(name)展开为struct idr name IDR_INIT(name)include/linux/idr.h#L57idr_init()内部调用idr_init_base(idr, 0)include/linux/idr.h#L166-L169。IDR 初始化时会在 radix tree 根上打上IDR_RT_MARKER标志并用 tag 0IDR_FREE跟踪该节点之下是否还有空闲槽位这是分配算法高效性的关键include/linux/idr.h#L26-L34。三、IDR 核心操作分配、查找、释放、替换3.1 分配idr_alloc()int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp);在[start, end)区间start 闭、end 开内分配一个空闲 ID 并关联指针ptr返回新 ID失败时返回负的错误码-ENOMEM内存不足或-ENOSPC区间内没有空闲 ID。参数语义有两个容易踩坑的点lib/idr.c#L81-L95end 0时按INT_MAX 1处理即上界默认为整个 int 正区间start 0会触发WARN_ON_ONCE并返回-EINVAL。3.2 大 ID 分配idr_alloc_u32()部分使用者需要分配大于INT_MAX的 ID。idr_alloc_u32()专为此设计目前上限为UINT_MAXint idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid, unsigned long max, gfp_t gfp);与idr_alloc()不同它的max是闭区间上界新 ID 会写回*nextid且该写入发生在指针插入 radix tree之前因此即使nextid指向被关联对象内部的字段并发查找也不会看到未初始化的 IDlib/idr.c#L11-L58。3.3 循环分配idr_alloc_cyclic()int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp);从上次分配位置之后继续搜索避免长期复用同一个低 ID若搜索到end仍无空闲则回绕到start重试lib/idr.c#L119-L137。分配成功后会把idr-idr_next id 1作为下次搜索起点。文档特别提醒IDR 处理大 ID 时效率会下降使用循环分配会带来少量额外开销适合ID 会频繁分配与释放、需要摊平热点的场景。3.4 查找idr_find()void *idr_find(const struct idr *idr, unsigned long id);返回与id关联的指针。注意NULL有两种含义ID 未分配或该 ID 关联的本来就是NULL指针——这正是先用NULL占位技巧的基础。idr_find()支持在rcu_read_lock()区间内无锁调用见下文同步章节。3.5 释放idr_remove()void *idr_remove(struct idr *idr, unsigned long id);从 IDR 中摘除该 ID并返回原先关联的指针若该 ID 本就不存在则返回NULL。实现上是带基数折算的radix_tree_delete_item()lib/idr.c#L154-L158。3.6 替换idr_replace() 与先占位后初始化模式void *idr_replace(struct idr *idr, void *ptr, unsigned long id);用新指针替换id关联的旧指针并返回旧值。失败时返回ERR_PTR(-ENOENT)ID 不存在或ERR_PTR(-EINVAL)ptr不合法。这是内核文档中重点推荐的一种惯用法——保留式分配用idr_alloc(idr, NULL, ...)分配一个 ID先不关联有效对象用该 ID 完成对象的初始化最后idr_replace(idr, obj, id)把初始化好的对象挂到 IDR 上。这样做的好处是在对象完全就绪之前其它路径通过idr_find()只能拿到NULL不会触碰到半初始化状态。内核测试 tools/testing/radix-tree/idr-test.c#L96-L148idr_null_test专门覆盖了 NULL 占位、替换、释放后idr_is_empty()状态等边界情况。四、遍历 IDR 的三种方式文档给出三种遍历手段适用场景各异/* 1. 回调式对每个 (id, ptr) 调用 fnfn 返回非 0 立即终止 */ int idr_for_each(const struct idr *idr, int (*fn)(int id, void *p, void *data), void *data); /* 2. 迭代器式for 循环内逐个取出 entry 与 id */ #define idr_for_each_entry(idr, entry, id) \ for (id 0; ((entry) idr_get_next(idr, (id))) ! NULL; id 1U) /* 3. 从中途继续迭代 */ #define idr_for_each_entry_continue(idr, entry, id) /* 4. 手动迭代拿到 *nextid 的下一个已填充项并更新 *nextid */ void *idr_get_next(struct idr *idr, int *nextid);实现上idr_for_each()基于radix_tree_for_each_slot展开遍历并会跳过内部节点lib/idr.c#L197-L217idr_for_each_entry等宏则直接封装了idr_get_next()include/linux/idr.h#L204-L250。回调式的好处是可以借助回调的返回值提前终止遍历例如遍历释放所有对象迭代器式则更贴近普通 C 循环的书写习惯循环正常结束后entry为NULL正好可以当未找到用。文档还提示若要在遍历过程中释放对象直接用迭代器逐个idr_remove()kfree()即可idr_destroy()并不会帮你释放被关联的对象。五、生命周期管理与状态查询void idr_destroy(struct idr *idr); /* 释放 IDR 内部占用的内存 */ bool idr_is_empty(const struct idr *idr); /* 是否还有已分配的 ID */idr_destroy()只释放 IDR 自身的 radix tree 节点内存不会释放那些被关联的对象如需一并清理必须先用第三节的遍历手段逐个释放文档明确强调。idr_is_empty()的语义是是否还有已分配的 IDinclude/linux/idr.h#L177-L181。注意一个细节占用着 ID 但关联NULL指针时idr_is_empty()返回false——这一点在idr_null_test中被反复断言是理解占位即占用语义的重要线索。六、同步模型RCU 无锁读 idr_preload 预加载6.1 RCU 无锁查找IDR 的查找路径可以在rcu_read_lock()区间内完全无锁执行文档在idr sync一节说明include/linux/idr.h#L85-L100。但调用者仍须自行管理对象本身的同步与生命周期对象自身带锁或天然适合无锁访问对象通过 RCU 释放或从 IDR 删除后等待一个synchronize_rcu()宽限期再释放。测试 tools/testing/radix-tree/idr-test.c#L302-L358idr_throbberidr_find_test用一个后台线程反复 alloc/remove、主线程在 RCU 读锁内持续idr_get_next()的方式验证了这种并发模型下查找的可靠性。6.2 持锁分配与 idr_preload()一个常见困局分配新 ID 时可能需要持锁但持锁期间又必须使用不允许睡眠/阻塞的 GFP 标志否则可能死锁而严格标志又可能导致分配内存失败。解决之道是预加载preloadidr_preload(GFP_KERNEL); /* 持锁前预先分配好 radix tree 节点 */ spin_lock(lock); id idr_alloc(idr, obj, 0, 0, GFP_NOWAIT); /* 持锁期间用不阻塞标志 */ spin_unlock(lock); idr_preload_end(); /* 与 idr_preload() 成对出现 */idr_preload()内部通过__radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE)预分配足够整棵树路径使用的节点并关闭抢占idr_preload_end()负责重新开启并归还预加载锁lib/radix-tree.c#L1466-L1473。测试idr_nowait_testtools/testing/radix-tree/idr-test.c#L150-L166展示了idr_preload()GFP_NOWAIT的组合用法。此外IDR 还提供了与 XArray 等价的锁宏族idr_lock()/idr_unlock()/idr_lock_bh()/idr_lock_irq()/idr_lock_irqsave()include/linux/idr.h#L102-L111。七、IDA只分配不映射的内存友好型分配器7.1 定位与初始化当业务只需要一个不重复的整数、不需要拿 ID 换指针时例如给设备实例编号IDA 是更优选择每个 ID 只需 1 bit 存储空间效率远高于 IDR。文档中的IDA descriptionlib/idr.c#L310-L330给出完整定义DEFINE_IDA(my_ida); /* 静态定义开箱即用 */ /* 或嵌入结构体后运行时初始化 */ struct ida my_ida; ida_init(my_ida);底层上struct ida只含一个 XArrayinclude/linux/idr.h#L263-L265位图以 128 字节为一个 chunkIDA_CHUNK_SIZE每个 chunk 可承载IDA_BITMAP_BITS个 ID。IDA 的分配上限目前为[0, INT_MAX]。7.2 分配与释放int ida_alloc(struct ida *ida, gfp_t gfp); /* [0, INT_MAX] */ int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp); /* [min, INT_MAX] */ int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp); /* [0, max] */ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, gfp_t gfp); void ida_free(struct ida *ida, unsigned int id); /* 释放一个 ID */ void ida_destroy(struct ida *ida); /* 整体销毁无需逐 ID 释放 */三个便捷包装最终都汇聚到ida_alloc_range()include/linux/idr.h#L291-L330。返回值约定成功返回分配的 ID失败返回-ENOMEM或-ENOSPC。ida_free()对未分配的 ID 会调用WARN报警lib/idr.c#L548-L596因此释放的 ID 必须是之前分配成功的。与 IDR 最大的差异在于并发模型IDA 在内部自行加锁文档明确可以在不加任何外部同步的情况下安全调用任意 IDA 函数。这大幅简化了使用者的心智负担。7.3 状态查询bool ida_is_empty(struct ida *ida); /* 是否还有已分配 ID */ bool ida_exists(struct ida *ida, unsigned int id); /* 指定 ID 是否已分配 */ int ida_find_first(struct ida *ida); /* 最低的已用 ID */ int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max);其中ida_find_first_range()在持锁状态下用xa_find(..., XA_PRESENT)定位最低已用位lib/idr.c#L493-L546供ida_exists()/ida_find_first()等内联包装复用。7.4 内部实现的两级优化源码中的Developers noteslib/idr.c#L332-L365揭示了 IDA 的存储策略值得展开位图分片XArray 每个槽位存一个 128 字节位图为避免把索引直接映射到多阶 XArray 节点造成的头节点内存膨胀实现上将索引先除以每叶位图位数再查树值条目优化当一个 chunk 内只有少数低位被占用时不分配 128 字节位图而是把位图直接以 XArray 值条目value entry的形式内联存储仅在位图增长后才升级为完整位图。这一设计在ida_check_conv_user测试tools/testing/radix-tree/idr-test.c#L476-L495中被专门验证XA_FREE_MARK仅在位图全部位被置位后才清除用于快速定位仍有空闲的 chunk。八、真实内核使用案例IDR/IDA 遍布内核各处这里举两个可读性强的例子驱动平台的自动设备号drivers/base/platform.c 顶部static DEFINE_IDA(platform_devid_ida)第 40 行在platform_device_register路径用ida_alloc(platform_devid_ida, GFP_KERNEL)分配自动 ID注销时ida_free()归还第 798、841 行等。这正是只要编号、无需映射的典型 IDA 场景。进程/线程号kernel/pid.c 使用 IDR 维护 PID 到struct pid的映射是ID 到指针映射最经典的 IDR 用户kernel/bpf/btf.c、kernel/cgroup/cgroup.c、kernel/workqueue.c 等也大量使用 IDR 管理各自的 ID。读者可通过grep -r DEFINE_IDR\|DEFINE_IDA kernel drivers fs net在内核源码树中快速找到更多实战样本。九、测试与验证体系IDR/IDA 的测试集中在用户态测试程序 tools/testing/radix-tree/idr-test.c内核通过make -C tools/testing/radix-tree可独立构建运行覆盖了本文涉及的全部 API 与边界测试函数验证点idr_alloc_test循环分配的回绕语义、ID 复用idr_alloc2_test带基数base的区间限制与-ENOSPCidr_null_testNULL 占位、idr_is_empty()语义、idr_replace()返回旧值idr_nowait_testidr_preload()GFP_NOWAIT组合idr_get_next_test按序迭代与基数折算idr_u32_test大于INT_MAX的 u32 ID0x7fffffff、0x80000000、0xffffffffidr_find_testRCU 无锁读与并发 alloc/remove 的可靠性ida_check_conv_user值条目 ↔ 完整位图的升级转换ida_check_random/ida_thread_tests随机分配释放、20 线程并发压力ida_alloc_free_test1 万次分配/释放循环与ida_is_empty()这些测试同时是理解 API 语义尤其是错误码与边界条件的最佳补充教材。十、选型建议与迁移方向总结 IDR 与 IDA 的选型决策需要ID ↔ 指针双向映射、且愿意自行管理同步 → 使用 IDR或直接迁移 XArray只需分配不重复的整数、希望内部自带锁 → 使用 IDA新代码IDR 接口已废弃官方建议改用 XArray 的分配能力参见 Documentation/core-api/xarray.rst 中的xa_alloc()/xa_store()等接口IDA 则没有类似废弃声明仍可放心使用。无论选择哪套设施牢记本文梳理的三条铁律即可写出健壮的 ID 管理代码分配/释放/替换需自行加锁IDA 除外、查找可在 RCU 读锁内无锁执行、持锁分配务必配合idr_preload()使用不阻塞 GFP 标志。【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linux创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Linux 内核 IDR/IDA 标识符分配机制完全指南：从 ID 到指针的映射与高效位图分配
Linux 内核 IDR/IDA 标识符分配机制完全指南从 ID 到指针的映射与高效位图分配【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linux本文以内核文档 Documentation/core-api/idr.rst 为主线结合 include/linux/idr.h 与 lib/idr.c 的源码实现系统讲解 Linux 内核中统一 ID 分配的两套设施IDRID Radix treeID 到指针映射与IDAID Allocator纯 ID 分配器。读完本文你将掌握二者的适用场景、全部核心 API 的参数与返回值语义、同步与预加载的正确姿势并通过内核测试用例与真实驱动用法获得可直接落地的实战能力。一、为什么内核需要统一的 ID 分配设施内核中给某样东西分配一个标识符ID是极其常见的需求文件描述符、进程号、网络协议中的报文标识、SCSI tag、设备实例号本质上都是用一个小整数去唯一标识一个对象。如果每个子系统都各自实现一套分配逻辑不仅容易出错还会造成功能重复。IDR 与 IDA 正是内核为此提供的通用解决方案IDR提供 ID 到指针void *的映射能力即给定 ID 查对象、给定对象分 ID的双向服务IDA只做 ID 分配/释放不保存任何指针因此每个 ID 只需占用 1 个 bit内存效率远高于 IDR。两者底层分别构建在 radix tree 与 XArray 之上。需要特别注意的是IDR 接口已被标记为废弃deprecated官方建议新代码改用 XArray见 Documentation/core-api/xarray.rst但 IDR 在内核中仍有大量存量使用者理解其语义对于阅读和维护这些代码依然必要。二、IDR 核心数据结构与初始化从源码看struct idr只包含三个字段include/linux/idr.h#L20-L24struct idr { struct radix_tree_root idr_rt; /* 底层 radix tree 根 */ unsigned int idr_base; /* 分配起始基数 */ unsigned int idr_next; /* 循环分配器的游标 */ };其中idr_base使得 IDR 可以从指定基数值开始分配内部 radix tree 索引统一按id - idr_base折算idr_next则是idr_alloc_cyclic()的循环游标可通过idr_get_cursor()/idr_set_cursor()读写include/linux/idr.h#L67-L83。初始化 IDR 有两条路径对应静态与动态分配两种场景/* 静态定义一个即可直接使用无需额外初始化 */ DEFINE_IDR(my_idr); /* 动态运行时初始化 */ struct idr my_idr; idr_init(my_idr); /* 变体指定分配基数ID 将从 base 开始分配 */ idr_init_base(my_idr, 100);实现细节上DEFINE_IDR(name)展开为struct idr name IDR_INIT(name)include/linux/idr.h#L57idr_init()内部调用idr_init_base(idr, 0)include/linux/idr.h#L166-L169。IDR 初始化时会在 radix tree 根上打上IDR_RT_MARKER标志并用 tag 0IDR_FREE跟踪该节点之下是否还有空闲槽位这是分配算法高效性的关键include/linux/idr.h#L26-L34。三、IDR 核心操作分配、查找、释放、替换3.1 分配idr_alloc()int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp);在[start, end)区间start 闭、end 开内分配一个空闲 ID 并关联指针ptr返回新 ID失败时返回负的错误码-ENOMEM内存不足或-ENOSPC区间内没有空闲 ID。参数语义有两个容易踩坑的点lib/idr.c#L81-L95end 0时按INT_MAX 1处理即上界默认为整个 int 正区间start 0会触发WARN_ON_ONCE并返回-EINVAL。3.2 大 ID 分配idr_alloc_u32()部分使用者需要分配大于INT_MAX的 ID。idr_alloc_u32()专为此设计目前上限为UINT_MAXint idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid, unsigned long max, gfp_t gfp);与idr_alloc()不同它的max是闭区间上界新 ID 会写回*nextid且该写入发生在指针插入 radix tree之前因此即使nextid指向被关联对象内部的字段并发查找也不会看到未初始化的 IDlib/idr.c#L11-L58。3.3 循环分配idr_alloc_cyclic()int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp);从上次分配位置之后继续搜索避免长期复用同一个低 ID若搜索到end仍无空闲则回绕到start重试lib/idr.c#L119-L137。分配成功后会把idr-idr_next id 1作为下次搜索起点。文档特别提醒IDR 处理大 ID 时效率会下降使用循环分配会带来少量额外开销适合ID 会频繁分配与释放、需要摊平热点的场景。3.4 查找idr_find()void *idr_find(const struct idr *idr, unsigned long id);返回与id关联的指针。注意NULL有两种含义ID 未分配或该 ID 关联的本来就是NULL指针——这正是先用NULL占位技巧的基础。idr_find()支持在rcu_read_lock()区间内无锁调用见下文同步章节。3.5 释放idr_remove()void *idr_remove(struct idr *idr, unsigned long id);从 IDR 中摘除该 ID并返回原先关联的指针若该 ID 本就不存在则返回NULL。实现上是带基数折算的radix_tree_delete_item()lib/idr.c#L154-L158。3.6 替换idr_replace() 与先占位后初始化模式void *idr_replace(struct idr *idr, void *ptr, unsigned long id);用新指针替换id关联的旧指针并返回旧值。失败时返回ERR_PTR(-ENOENT)ID 不存在或ERR_PTR(-EINVAL)ptr不合法。这是内核文档中重点推荐的一种惯用法——保留式分配用idr_alloc(idr, NULL, ...)分配一个 ID先不关联有效对象用该 ID 完成对象的初始化最后idr_replace(idr, obj, id)把初始化好的对象挂到 IDR 上。这样做的好处是在对象完全就绪之前其它路径通过idr_find()只能拿到NULL不会触碰到半初始化状态。内核测试 tools/testing/radix-tree/idr-test.c#L96-L148idr_null_test专门覆盖了 NULL 占位、替换、释放后idr_is_empty()状态等边界情况。四、遍历 IDR 的三种方式文档给出三种遍历手段适用场景各异/* 1. 回调式对每个 (id, ptr) 调用 fnfn 返回非 0 立即终止 */ int idr_for_each(const struct idr *idr, int (*fn)(int id, void *p, void *data), void *data); /* 2. 迭代器式for 循环内逐个取出 entry 与 id */ #define idr_for_each_entry(idr, entry, id) \ for (id 0; ((entry) idr_get_next(idr, (id))) ! NULL; id 1U) /* 3. 从中途继续迭代 */ #define idr_for_each_entry_continue(idr, entry, id) /* 4. 手动迭代拿到 *nextid 的下一个已填充项并更新 *nextid */ void *idr_get_next(struct idr *idr, int *nextid);实现上idr_for_each()基于radix_tree_for_each_slot展开遍历并会跳过内部节点lib/idr.c#L197-L217idr_for_each_entry等宏则直接封装了idr_get_next()include/linux/idr.h#L204-L250。回调式的好处是可以借助回调的返回值提前终止遍历例如遍历释放所有对象迭代器式则更贴近普通 C 循环的书写习惯循环正常结束后entry为NULL正好可以当未找到用。文档还提示若要在遍历过程中释放对象直接用迭代器逐个idr_remove()kfree()即可idr_destroy()并不会帮你释放被关联的对象。五、生命周期管理与状态查询void idr_destroy(struct idr *idr); /* 释放 IDR 内部占用的内存 */ bool idr_is_empty(const struct idr *idr); /* 是否还有已分配的 ID */idr_destroy()只释放 IDR 自身的 radix tree 节点内存不会释放那些被关联的对象如需一并清理必须先用第三节的遍历手段逐个释放文档明确强调。idr_is_empty()的语义是是否还有已分配的 IDinclude/linux/idr.h#L177-L181。注意一个细节占用着 ID 但关联NULL指针时idr_is_empty()返回false——这一点在idr_null_test中被反复断言是理解占位即占用语义的重要线索。六、同步模型RCU 无锁读 idr_preload 预加载6.1 RCU 无锁查找IDR 的查找路径可以在rcu_read_lock()区间内完全无锁执行文档在idr sync一节说明include/linux/idr.h#L85-L100。但调用者仍须自行管理对象本身的同步与生命周期对象自身带锁或天然适合无锁访问对象通过 RCU 释放或从 IDR 删除后等待一个synchronize_rcu()宽限期再释放。测试 tools/testing/radix-tree/idr-test.c#L302-L358idr_throbberidr_find_test用一个后台线程反复 alloc/remove、主线程在 RCU 读锁内持续idr_get_next()的方式验证了这种并发模型下查找的可靠性。6.2 持锁分配与 idr_preload()一个常见困局分配新 ID 时可能需要持锁但持锁期间又必须使用不允许睡眠/阻塞的 GFP 标志否则可能死锁而严格标志又可能导致分配内存失败。解决之道是预加载preloadidr_preload(GFP_KERNEL); /* 持锁前预先分配好 radix tree 节点 */ spin_lock(lock); id idr_alloc(idr, obj, 0, 0, GFP_NOWAIT); /* 持锁期间用不阻塞标志 */ spin_unlock(lock); idr_preload_end(); /* 与 idr_preload() 成对出现 */idr_preload()内部通过__radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE)预分配足够整棵树路径使用的节点并关闭抢占idr_preload_end()负责重新开启并归还预加载锁lib/radix-tree.c#L1466-L1473。测试idr_nowait_testtools/testing/radix-tree/idr-test.c#L150-L166展示了idr_preload()GFP_NOWAIT的组合用法。此外IDR 还提供了与 XArray 等价的锁宏族idr_lock()/idr_unlock()/idr_lock_bh()/idr_lock_irq()/idr_lock_irqsave()include/linux/idr.h#L102-L111。七、IDA只分配不映射的内存友好型分配器7.1 定位与初始化当业务只需要一个不重复的整数、不需要拿 ID 换指针时例如给设备实例编号IDA 是更优选择每个 ID 只需 1 bit 存储空间效率远高于 IDR。文档中的IDA descriptionlib/idr.c#L310-L330给出完整定义DEFINE_IDA(my_ida); /* 静态定义开箱即用 */ /* 或嵌入结构体后运行时初始化 */ struct ida my_ida; ida_init(my_ida);底层上struct ida只含一个 XArrayinclude/linux/idr.h#L263-L265位图以 128 字节为一个 chunkIDA_CHUNK_SIZE每个 chunk 可承载IDA_BITMAP_BITS个 ID。IDA 的分配上限目前为[0, INT_MAX]。7.2 分配与释放int ida_alloc(struct ida *ida, gfp_t gfp); /* [0, INT_MAX] */ int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp); /* [min, INT_MAX] */ int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp); /* [0, max] */ int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, gfp_t gfp); void ida_free(struct ida *ida, unsigned int id); /* 释放一个 ID */ void ida_destroy(struct ida *ida); /* 整体销毁无需逐 ID 释放 */三个便捷包装最终都汇聚到ida_alloc_range()include/linux/idr.h#L291-L330。返回值约定成功返回分配的 ID失败返回-ENOMEM或-ENOSPC。ida_free()对未分配的 ID 会调用WARN报警lib/idr.c#L548-L596因此释放的 ID 必须是之前分配成功的。与 IDR 最大的差异在于并发模型IDA 在内部自行加锁文档明确可以在不加任何外部同步的情况下安全调用任意 IDA 函数。这大幅简化了使用者的心智负担。7.3 状态查询bool ida_is_empty(struct ida *ida); /* 是否还有已分配 ID */ bool ida_exists(struct ida *ida, unsigned int id); /* 指定 ID 是否已分配 */ int ida_find_first(struct ida *ida); /* 最低的已用 ID */ int ida_find_first_range(struct ida *ida, unsigned int min, unsigned int max);其中ida_find_first_range()在持锁状态下用xa_find(..., XA_PRESENT)定位最低已用位lib/idr.c#L493-L546供ida_exists()/ida_find_first()等内联包装复用。7.4 内部实现的两级优化源码中的Developers noteslib/idr.c#L332-L365揭示了 IDA 的存储策略值得展开位图分片XArray 每个槽位存一个 128 字节位图为避免把索引直接映射到多阶 XArray 节点造成的头节点内存膨胀实现上将索引先除以每叶位图位数再查树值条目优化当一个 chunk 内只有少数低位被占用时不分配 128 字节位图而是把位图直接以 XArray 值条目value entry的形式内联存储仅在位图增长后才升级为完整位图。这一设计在ida_check_conv_user测试tools/testing/radix-tree/idr-test.c#L476-L495中被专门验证XA_FREE_MARK仅在位图全部位被置位后才清除用于快速定位仍有空闲的 chunk。八、真实内核使用案例IDR/IDA 遍布内核各处这里举两个可读性强的例子驱动平台的自动设备号drivers/base/platform.c 顶部static DEFINE_IDA(platform_devid_ida)第 40 行在platform_device_register路径用ida_alloc(platform_devid_ida, GFP_KERNEL)分配自动 ID注销时ida_free()归还第 798、841 行等。这正是只要编号、无需映射的典型 IDA 场景。进程/线程号kernel/pid.c 使用 IDR 维护 PID 到struct pid的映射是ID 到指针映射最经典的 IDR 用户kernel/bpf/btf.c、kernel/cgroup/cgroup.c、kernel/workqueue.c 等也大量使用 IDR 管理各自的 ID。读者可通过grep -r DEFINE_IDR\|DEFINE_IDA kernel drivers fs net在内核源码树中快速找到更多实战样本。九、测试与验证体系IDR/IDA 的测试集中在用户态测试程序 tools/testing/radix-tree/idr-test.c内核通过make -C tools/testing/radix-tree可独立构建运行覆盖了本文涉及的全部 API 与边界测试函数验证点idr_alloc_test循环分配的回绕语义、ID 复用idr_alloc2_test带基数base的区间限制与-ENOSPCidr_null_testNULL 占位、idr_is_empty()语义、idr_replace()返回旧值idr_nowait_testidr_preload()GFP_NOWAIT组合idr_get_next_test按序迭代与基数折算idr_u32_test大于INT_MAX的 u32 ID0x7fffffff、0x80000000、0xffffffffidr_find_testRCU 无锁读与并发 alloc/remove 的可靠性ida_check_conv_user值条目 ↔ 完整位图的升级转换ida_check_random/ida_thread_tests随机分配释放、20 线程并发压力ida_alloc_free_test1 万次分配/释放循环与ida_is_empty()这些测试同时是理解 API 语义尤其是错误码与边界条件的最佳补充教材。十、选型建议与迁移方向总结 IDR 与 IDA 的选型决策需要ID ↔ 指针双向映射、且愿意自行管理同步 → 使用 IDR或直接迁移 XArray只需分配不重复的整数、希望内部自带锁 → 使用 IDA新代码IDR 接口已废弃官方建议改用 XArray 的分配能力参见 Documentation/core-api/xarray.rst 中的xa_alloc()/xa_store()等接口IDA 则没有类似废弃声明仍可放心使用。无论选择哪套设施牢记本文梳理的三条铁律即可写出健壮的 ID 管理代码分配/释放/替换需自行加锁IDA 除外、查找可在 RCU 读锁内无锁执行、持锁分配务必配合idr_preload()使用不阻塞 GFP 标志。【免费下载链接】linuxLinux kernel source tree项目地址: https://gitcode.com/GitHub_Trending/li/linux创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考