idr

[TOC]

lib/idr.c IDR/IDA机制(ID-to-Pointer/ID Allocator) 内核对象ID的分配与管理

历史与背景

这项技术是为了解决什么特定问题而诞生的？

lib/idr.c 中的IDR（ID Radix Tree）和IDA（ID Allocator）机制是为了解决一个在内核中普遍存在的问题：如何为一个内核对象动态地分配一个唯一的、通常是小整数的ID，并能通过这个ID快速地反向查找到该对象。

这解决了以下几个关键痛点：

• 需要稳定的“句柄”：内核中的许多对象（如设备、定时器）需要被用户空间或其他子系统通过一个简单的整数ID来引用，这个ID就像一个“句柄”。直接暴露内核指针既不安全（违反KASLR）也不稳定（对象可能被重新分配）。
• 稀疏ID的空间效率：如果要支持的ID范围很大（例如0到INT_MAX），但实际同时存在的对象数量却相对较少，使用一个简单的指针数组（void *pointers[INT_MAX]）将会造成巨大的内存浪费。IDR/IDA需要一种空间高效的方式来管理这种“稀疏”的ID分配。
• ID的循环使用：当一个对象被销毁后，它所占用的ID应该能被回收并重新分配给新的对象，以保持ID的紧凑性。
• 简化ID分配逻辑：在没有通用框架之前，需要此功能的各个子系统都必须自己实现一套ID分配和管理的逻辑，导致代码重复和潜在的错误。

它的发展经历了哪些重要的里程碑或版本迭代？

IDR/IDA的发展是一个功能提炼和分离的过程：

1. IDR的诞生：最初，内核引入了IDR（ID Radix Tree）。它将两个功能合二为一：分配一个新的、未被使用的整数ID，并将这个ID与一个指针关联起来。它的底层实现是基于基数树（Radix Tree），这使得它在处理稀疏ID时非常节省空间。
2. IDA的提炼：开发者们发现，在很多场景下，他们只需要分配一个唯一的整数ID，而不需要存储与之关联的指针。例如，仅仅需要一个唯一的标签号。为了满足这种更轻量级的需求，IDA（ID Allocator）被从IDR的逻辑中提炼出来。IDA只负责分配和回收ID，其内部实现使用基数树来跟踪哪些ID是空闲的，因此比IDR更简单、开销更小。
3. IDR基于IDA的重构：在现代内核中，IDR的实现通常被重构为在内部使用一个IDA来处理ID的分配和回收，然后再额外负责管理ID到指针的映射。这种分层使得代码更加清晰和模块化。

目前该技术的社区活跃度和主流应用情况如何？

IDR/IDA是内核中一个非常核心、稳定且被广泛使用的基础库。它不是一个试验性功能，而是许多关键子系统的基石。

• cdev (字符设备)：使用IDR机制来管理次设备号，并将它们映射到对应的字符设备结构。
• POSIX Timers：当用户空间创建一个POSIX定时器时，内核使用IDR来分配一个timer_t ID，并将其映射到内部的k_itimer结构。
• I/O子系统：一些I/O调度器和块设备驱动使用IDA来分配请求标签（request tags）。
• DRM/GPU驱动：用于管理图形内存对象或其他硬件资源的句柄。
• InfiniBand和网络驱动：用于管理各种资源的标识符。

核心原理与设计

它的核心工作原理是什么？

IDR/IDA的核心数据结构是基数树（Radix Tree），一种针对整数键进行优化的、空间效率极高的前缀树。

• IDA (ID Allocator) 的工作原理：

  1. IDA内部维护一个基数树，这个树的叶子节点并不存储指针，而是通过一种特殊的方式（位图）来表示一个范围内的ID是否被分配。
  2. 当调用 ida_alloc() 来请求一个新的ID时，IDA会从上一次分配的位置开始，在基数树中搜索一个未被使用的位（代表一个空闲的ID）。
  3. 找到后，它会在树中将该位标记为“已使用”，并返回对应的整数ID。这种从上一次位置开始搜索的策略，保证了分配出的ID总是倾向于小的、紧凑的数值。
  4. 当调用 ida_free() 时，IDA会在树中将对应ID的位标记为“未使用”。

• IDR (ID Radix Tree) 的工作原理：

  1. IDR将ID的分配和指针的存储结合起来。它的基数树的叶子节点直接存储用户提供的指针。
  2. 当调用 idr_alloc() 时，它（现在通常）会先通过内部的IDA逻辑找到一个空闲的ID。
  3. 然后，它会在基数树中为这个ID创建一个路径，并将用户提供的指针存放在对应的叶子节点上。
  4. 当调用 idr_find() 时，它会以要查找的ID作为“路径”，在基数树中进行遍历。如果路径存在且叶子节点不为空，就返回存储的指针。这是一个非常快速的操作，其时间复杂度与ID的位数成正比，与已分配ID的总数无关。
  5. 当调用 idr_remove() 时，它会先找到对应的叶子节点，将其清空，然后通过内部的IDA逻辑回收这个ID。

它的主要优势体现在哪些方面？

• 空间效率：对于稀疏的ID分布，基数树的内存占用远小于简单的数组。
• 性能高效：查找、插入和删除操作的时间复杂度为O(log N)，更准确地说是O(k)，其中k是ID的位数。这与已分配ID的总数无关，具有很好的可扩展性。
• ID分配策略：能自动找到并分配当前未被使用的最小ID，有助于保持ID的紧凑性。
• 线程安全：IDR/IDA的所有操作都由内部的自旋锁保护，是线程安全的。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

• 锁竞争：IDR/IDA使用一个单一的自旋锁来保护其内部数据结构。如果在性能要求极高的场景下，有大量的CPU核心同时、高频率地进行ID的分配和释放，这个锁可能会成为一个性能瓶颈。
• 复杂性：相比于简单的数组或位图，基数树的实现更复杂，有一定的理解和维护成本。
• ID范围限制：ID的最大值受到基数树深度的限制，通常是30位或31位，即最大ID不能超过INT_MAX。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？请举例说明。

当需要在内核中实现一个句柄（Handle）系统时，IDR是首选解决方案。即，你需要：

1. 生成一个唯一的整数ID。
2. 将这个ID关联到一个内核对象指针。
3. 在未来的某个时刻，能通过这个ID快速找回这个指针。

• 例一：USB设备驱动
  一个复杂的USB设备可能有多个逻辑单元（例如，一个U盘+读卡器设备）。驱动程序需要为每个逻辑单元分配一个唯一的ID，以便上层协议栈可以通过这个ID来寻址。驱动可以使用IDR，将生成的ID（如0, 1, 2…）映射到代表每个逻辑单元的内部数据结构指针。
• 例二：cdev实现
  内核的cdev子系统需要管理系统中所有的字符设备。当一个驱动调用cdev_add()注册一个字符设备时，cdev子系统需要将设备号dev_t和一个struct cdev对象关联起来。IDR是实现这个映射的理想工具。

如果只需要分配唯一ID而不需要存储指针，那么更轻量级的IDA是首选。

• 例三：I/O请求标签
  一个NVMe驱动需要为每个发往硬件的命令分配一个唯一的标签号（Tag），以便在命令完成时能识别是哪个命令。驱动可以使用IDA来快速获取一个未被使用的Tag号。当命令完成后，再用IDA释放这个Tag号。

是否有不推荐使用该技术的场景？为什么？

• 键不是整数或范围很大：IDR/IDA的键是整数。如果你需要用字符串或其他复杂结构作为键来查找对象，应该使用哈希表。
• ID是连续且密集的：如果你需要分配的ID总是从0开始，连续递增，且最大值不大（例如0-255），那么使用一个简单的指针数组 (void *my_pointers[256]) 会比IDR更简单、更快。
• 只需要一个简单的位图：如果你只是想从一个小的、固定的范围内分配ID（例如，管理32个可用的资源槽），使用内核的位图（bitmap）API会比IDA更直接、开-销更小。

对比分析

请将其 与 其他相似技术 进行详细对比。

特性	IDR/IDA	哈希表 (Hash Table)	位图 (Bitmap)	简单数组 (Simple Array)
核心功能	分配并（对于IDR）映射稀疏的整数ID。	映射一个已存在的键到一个值。	分配来自一个固定、密集范围的ID。	映射一个密集的整数索引到一个值。
键/ID的来源	由机制本身生成。	由调用者提供。	由机制本身生成（返回第一个空闲位的索引）。	由调用者提供（作为数组索引）。
空间效率	高（对稀疏ID友好）。	中等。	低（对稀疏ID非常浪费）。	极低（对稀疏ID完全不可行）。
查找性能	O(k) (k为ID位数)。	平均 O(1)。	O(n) (查找一个空闲位)。	O(1)。
分配性能	O(k) (k为ID位数)。	不适用（不分配ID）。	O(n) (查找一个空-闲位)。	不适用（不分配ID）。
典型用途	内核句柄系统（cdev, POSIX timers），唯一标签生成。	快速查找（dcache, PID表）。	管理固定数量的资源槽。	管理固定、小范围、密集的对象（如中断向量表）。
关键区别	“请给我一个空闲的ID，并帮我记住它指向谁”	“帮我记住这个键对应这个值”	“请告诉我这个范围里哪个位置是空的”	“请把这个值存在第N个位置”

include/linux/idr.h

DEFINE_IDR

/*
 * IDR API 不向用户公开基数树的标记功能。使用标记 0 来跟踪节点下方是否有自由空间。
 */
#define IDR_FREE	0

/* 设置IDR标志和IDR_FREE标签 */
#define IDR_RT_MARKER	(ROOT_IS_IDR | (__force gfp_t)			\
					(1 << (ROOT_TAG_SHIFT + IDR_FREE)))

#define IDR_INIT_BASE(name, base) {					\
	.idr_rt = RADIX_TREE_INIT(name, IDR_RT_MARKER),			\
	.idr_base = (base),						\
	.idr_next = 0,							\
}

/**
 * IDR_INIT() - Initialise an IDR.
 * @name: Name of IDR.
 *
 * 一个刚刚初始化的 IDR 中不包含任何 ID。
 */
#define IDR_INIT(name)	IDR_INIT_BASE(name, 0)

/* * DEFINE_IDR() - 定义一个静态分配的 IDR。
 * @name: IDR 的名称。
 * 使用此宏定义的 IDR 可直接使用，无需额外的初始化。 
 * 它不包含任何 ID。 
*/
#define DEFINE_IDR(name)	struct idr name = IDR_INIT(name)

idr_for_each_entry 遍历给定类型的IDR元素.

/**
 * idr_for_each_entry() - 遍历给定类型的IDR元素.
 * @idr: IDR handle.
 * @entry: The type * to use as cursor
 * @id: Entry ID.
 *
 *@entry 和 @id 在循环之前不需要初始化，在正常结束后 @entry 的值会被设置为 NULL。这对于表示“未找到”的值非常方便。
 */
#define idr_for_each_entry(idr, entry, id)			\
	for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; id += 1U)

idr_init_base 初始化 IDR

/**
 * idr_init_base（） - 初始化 IDR。
 * @idr：IDR 句柄。
 * @base：IDR 的基值。
 *
 * idr_init（） 的此变体将创建一个 IDR，该 IDR 将从 se 开始分配 ID。
 */
static inline void idr_init_base(struct idr *idr, int base)
{
	INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
	idr->idr_base = base;
	idr->idr_next = 0;
}

idr_init - 初始化 IDR

/**
 * idr_init（） - 初始化 IDR。
 * @idr：IDR 句柄。
 *
 * 初始化动态分配的 IDR。 要初始化静态分配的 IDR，请使用 DEFINE_IDR（）。
 */
static inline void idr_init(struct idr *idr)
{
	idr_init_base(idr, 0);
}

lib/idr.c

idr_get_next_ul 查找下一个已填充的条目（即非空条目）

/**
 * idr_get_next_ul() - 查找下一个已填充的条目（即非空条目）。
 * @idr: IDR handle.
 * @nextid: Pointer to an ID.
 *
 * 返回树中下一个ID大于或等于@nextid指向的值的已填充条目。退出时，@nextid将更新为找到的值的ID。要在循环中使用，nextid指向的值必须由用户递增。
 */
void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)
{
	struct radix_tree_iter iter;
	void __rcu **slot;
	void *entry = NULL;
	unsigned long base = idr->idr_base;
	unsigned long id = *nextid;

	id = (id < base) ? 0 : id - base;
	radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, id) {
		entry = rcu_dereference_raw(*slot); /*  获取当前槽位的值 */
		if (!entry)
			continue;
		if (!xa_is_internal(entry))         /* 检查值是否为内部节点 */
			break;
		if (slot != &idr->idr_rt.xa_head && !xa_is_retry(entry))
			break;
		slot = radix_tree_iter_retry(&iter);
	}
	if (!slot)
		return NULL;

	*nextid = iter.index + base;
	return entry;
}
EXPORT_SYMBOL(idr_get_next_ul);

idr_get_next 查找下一个填充的条目

/**
 * idr_get_next() - 查找下一个填充的条目。
 * @idr: IDR handle.
 * @nextid: Pointer to an ID.
 *
 * 返回树中下一个ID大于或等于@nextid指向的值的已填充条目。
 * 退出时，@nextid将更新为找到的值的ID。要在循环中使用，nextid指向的值必须由用户递增。
 */
void *idr_get_next(struct idr *idr, int *nextid)
{
	unsigned long id = *nextid;
	void *entry = idr_get_next_ul(idr, &id);

	if (WARN_ON_ONCE(id > INT_MAX))
		return NULL;
	*nextid = id;
	return entry;
}
EXPORT_SYMBOL(idr_get_next);

replace_slot 替换槽位

static void replace_slot(void __rcu **slot, void *item,
		struct radix_tree_node *node, int count, int values)
{
	if (node && (count || values)) {
		node->count += count;
		node->nr_values += values;
	}

	rcu_assign_pointer(*slot, item);
}

radix_tree_replace_slot 替换插槽中的项目

/** * __radix_tree_replace - 替换槽中的项目 
 * @root: radix 树的根 
 * @node: 指向树节点的指针 
 * @slot: 指向 @node 中槽的指针 
 * @item: 要存储在槽中的新项目。 * 
 * 用于 __radix_tree_lookup()。调用者必须在槽查找和替换期间持有树写锁定。 */
void __radix_tree_replace(struct radix_tree_root *root,
			  struct radix_tree_node *node,
			  void __rcu **slot, void *item)
{
	void *old = rcu_dereference_raw(*slot);
	/* 计算新条目和旧条目是否为“值条目”（value entry）的差异：
	xa_is_value(item) 和 xa_is_value(old) 检查条目是否为值。
	values 的值为 1 表示新条目是值条目，旧条目不是；-1 表示相反 */
	int values = !!xa_is_value(item) - !!xa_is_value(old);
	/* 调用 calculate_count 计算节点计数的变化量 */
	int count = calculate_count(root, node, slot, item, old);

	/*
	 * This function supports replacing value entries and
	 * deleting entries, but that needs accounting against the
	 * node unless the slot is root->xa_head.
	 */
	WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->xa_head) &&
			(count || values));
	replace_slot(slot, item, node, count, values);

	if (!node)
		return;

	delete_node(root, node);
}

/**
 * radix_tree_replace_slot - 替换插槽中的项目 
 * @root: 树根 
 * @slot: 指向插槽的指针 
 * @item: 要存储在插槽中的新项目。 * 
 * 用于 radix_tree_lookup_slot() 和 radix_tree_gang_lookup_tag_slot()。 
 * 调用者必须在插槽查找和替换之间持有树的写锁。 * 
 * 注意：这不能用于在非条目（空插槽）、常规条目和数值条目之间切换，因为这需要在 Radix 树节点内部进行记账。
 * 当从一种类型的条目切换或删除时，使用 __radix_tree_lookup() 和 __radix_tree_replace() 或 radix_tree_iter_replace()。
 */
void radix_tree_replace_slot(struct radix_tree_root *root,
			     void __rcu **slot, void *item)
{
	__radix_tree_replace(root, NULL, slot, item);
}
EXPORT_SYMBOL(radix_tree_replace_slot);

idr_alloc 分配一个ID

/**
 * idr_alloc_u32() - 分配一个 ID。 
 * @idr: IDR 句柄。 * @ptr: 与新 ID 关联的指针。 
 * @nextid: ID 的指针。 
 * @max: 要分配的最大 ID（包含）。 
 * @gfp: 内存分配标志。 * 
 * 在 @nextid 和 @max 指定的范围内分配一个未使用的 ID。请注意，@max 是包含的，而 idr_alloc() 的 @end 参数是排除的。新的 ID 在将指针插入 IDR 之前分配给 @nextid，因此如果 @nextid 指向 @ptr 指向的对象，那么并发查找将不会找到未初始化的 ID。 * 
 * 调用者应该提供自己的锁，以确保 IDR 不能进行两个并发修改。对 IDR 的只读访问可以在 RCU 读锁下进行，或者可以排除同时写入者。 * 
 * 返回：如果分配了 ID 则返回 0，如果内存分配失败则返回 -ENOMEM，或者如果没有找到空闲 ID 则返回 -ENOSPC。如果发生错误，@nextid 不变。
 */
int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
			unsigned long max, gfp_t gfp)
{
	struct radix_tree_iter iter;
	void __rcu **slot;
	unsigned int base = idr->idr_base;
	unsigned int id = *nextid;
   /* 检查 IDR 的根节点标志 ROOT_IS_IDR 是否已设置 */
	if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR)))
		idr->idr_rt.xa_flags |= IDR_RT_MARKER;

	id = (id < base) ? 0 : id - base;
	radix_tree_iter_init(&iter, id);
	slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);  /* 查找 Radix Tree 中的空闲槽位 */
	if (IS_ERR(slot))
		return PTR_ERR(slot);

	*nextid = iter.index + base;
	/* 将槽位的内容替换为用户提供的指针 ptr.
   清除槽位的 IDR_FREE 标记，表示该槽位已被占用*/
	radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
	radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);

	return 0;
}
EXPORT_SYMBOL_GPL(idr_alloc_u32);

/**
 * idr_alloc() - 分配一个 ID。 
 * @idr: IDR 句柄。 
 * @ptr: 要与新 ID 关联的指针。 
 * @start: 最小 ID（包含）。 
 * @end: 最大 ID（不包含）。 
 * @gfp: 内存分配标志。 * 
 * 在 @start 和 @end 指定的范围内分配一个未使用的 ID。如果 @end 小于等于 0，则将其视为比 %INT_MAX 大 1。这允许调用者在 N 在整数范围内时使用 @start N 作为 @end。 * 
 * 调用者应提供自己的锁定，以确保无法对 IDR 进行两个并发修改。对 IDR 的只读访问可以在 RCU 读锁下进行，或者可以排除同时写入者。 * 
 * 返回：新分配的 ID，如果内存分配失败则返回 -ENOMEM，如果找不到空闲 ID 则返回 -ENOSPC。
 */
int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
{
	u32 id = start;
	int ret;

	if (WARN_ON_ONCE(start < 0))
		return -EINVAL;

	ret = idr_alloc_u32(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp);
	if (ret)
		return ret;

	return id;
}
EXPORT_SYMBOL_GPL(idr_alloc);

idr_find 查找ID

/**
 * idr_find() - Return pointer for given ID.
 * @idr: IDR handle.
 * @id: Pointer ID.
 *
 * 查找与此ID相关联的指针。%NULL指针可能表示@id未分配或该%NULL指针与此ID关联。 *  
 * 在rcu_read_lock()下可以调用此函数，前提是叶指针的生命周期得到正确管理。 *  
 * 返回：与此ID相关联的指针。
 */
void *idr_find(const struct idr *idr, unsigned long id)
{
	return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
}
EXPORT_SYMBOL_GPL(idr_find);

idr_remove 删除ID

/**
 * idr_remove() - Remove an ID from the IDR.
 * @idr: IDR handle.
 * @id: Pointer ID.
 *
 * 从 IDR 中移除此 ID。如果该 ID 之前不在 IDR 中，则此函数返回 %NULL。 *  
 * 由于此函数修改了 IDR，因此调用者应该提供自己的锁，以确保无法对同一 IDR 进行并发修改。 *  
 * 返回：以前与此 ID 关联的指针。
 */
void *idr_remove(struct idr *idr, unsigned long id)
{
	return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
}
EXPORT_SYMBOL_GPL(idr_remove);

ida_free 释放ID

/**
 * ida_free() - Release an allocated ID.
 * @ida: IDA handle.
 * @id: Previously allocated ID.
 *
 * 上下文：任何上下文。在不锁定代码的情况下安全地调用此函数。
 */
void ida_free(struct ida *ida, unsigned int id)
{
	/* 使用 XA_STATE 宏初始化一个 xas 状态对象，指向 ida->xa（XArray 数据结构） */
	XA_STATE(xas, &ida->xa, id / IDA_BITMAP_BITS);
	/* 计算出 ID 在位图中的位置 
	id / IDA_BITMAP_BITS 确定 ID 所在的位图块。
	id % IDA_BITMAP_BITS 确定 ID 在块中的具体位置*/
	unsigned bit = id % IDA_BITMAP_BITS;
	struct ida_bitmap *bitmap;
	unsigned long flags;

	if ((int)id < 0)
		return;

	xas_lock_irqsave(&xas, flags);
	/* 加载 ID 对应的位图块 */
	bitmap = xas_load(&xas);
	/* 处理值型存储 */
	if (xa_is_value(bitmap)) {
		unsigned long v = xa_to_value(bitmap);
		if (bit >= BITS_PER_XA_VALUE)
			goto err;
		if (!(v & (1UL << bit)))
			goto err;
		/* 清除对应的位（v &= ~(1UL << bit)），并检查是否还有其他位被设置。如果没有，则跳转到 delete 标签删除整个块 */
		v &= ~(1UL << bit);
		if (!v)
			goto delete;
		xas_store(&xas, xa_mk_value(v));
	} else {/* 处理位图存储 如果 bitmap 是一个位图指针*/
		if (!bitmap || !test_bit(bit, bitmap->bitmap))
			goto err;
		/* 清除对应的位（__clear_bit），并标记该块为空闲（xas_set_mark */
		__clear_bit(bit, bitmap->bitmap);
		xas_set_mark(&xas, XA_FREE_MARK);
		/* 如果位图为空（通过 bitmap_empty 检查），释放位图内存并跳转到 delete 标签删除整个块 */
		if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {
			kfree(bitmap);
delete:
			xas_store(&xas, NULL);
		}
	}
	xas_unlock_irqrestore(&xas, flags);
	return;
 err:
	xas_unlock_irqrestore(&xas, flags);
	WARN(1, "ida_free called for id=%d which is not allocated.\n", id);
}
EXPORT_SYMBOL(ida_free);

idr_alloc_cyclic 在指定范围内循环分配唯一的 ID

/**
 * idr_alloc_cyclic（） - 循环分配 ID。
 * @idr：IDR 句柄。
 * @ptr：要与新 ID 关联的指针。
 * @start：最小 ID（含）。
 * @end：最大 ID（不含）。
 * @gfp：内存分配标志。
 *
 * 在 @start 和 @end 指定的范围内分配未使用的 ID。 如果 @end 为 <= 0，则将其视为大于 %INT_MAX 的 1。 这允许调用方使用 @start N 作为@end只要 N 在整数范围内即可。对未使用 ID 的搜索将从分配的最后一个 ID 开始，如果在到达 ID 之前未找到可用 ID，则将回绕到 @start @end。
 *
 * 调用方应提供自己的锁定，以确保无法同时对 IDR 进行两次修改。 对 IDR 的只读访问可以在 RCU 读锁定下完成，也可以排除同时写入器。
 *
 * 返回：新分配的 ID，如果内存分配失败，则返回 -ENOMEM，如果找不到可用 ID，则返回 -ENOSPC。
 */
int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
{
	u32 id = idr->idr_next;
	int err, max = end > 0 ? end - 1 : INT_MAX;

	if ((int)id < start)
		id = start;

	err = idr_alloc_u32(idr, ptr, &id, max, gfp);
	if ((err == -ENOSPC) && (id > start)) {
		id = start;
		err = idr_alloc_u32(idr, ptr, &id, max, gfp);
	}
	if (err)
		return err;

	idr->idr_next = id + 1;
	return id;
}
EXPORT_SYMBOL(idr_alloc_cyclic);