数据结构与算法回顾（十）：radix tree

// 基于位（bit）的Radix Tree
#define IDR_BITS 6
#define IDR_SIZE (1 << IDR_BITS)  // 64

struct idr_layer {
    DECLARE_BITMAP(bitmap, IDR_SIZE);  // 位图标记已用槽位
    struct idr_layer __rcu *slots[IDR_SIZE];  // 子节点或数据指针
    int count;  // 已用槽位计数
};

//https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/radix-tree.h#L112
struct radix_tree_root {
	gfp_t			gfp_mask;
	struct radix_tree_node	__rcu *rnode;
};

//https://elixir.bootlin.com/linux/v4.11.6/source/include/linux/radix-tree.h#L93
struct radix_tree_node {
	unsigned char	shift;		/* Bits remaining in each slot */
	unsigned char	offset;		/* Slot offset in parent */
	unsigned char	count;		/* Total entry count */
	unsigned char	exceptional;	/* Exceptional entry count */
	struct radix_tree_node *parent;		/* Used when ascending tree */
	struct radix_tree_root *root;		/* The tree we belong to */
	union {
		struct list_head private_list;	/* For tree user */
		struct rcu_head	rcu_head;	/* Used when freeing node */
	};
	//核心字段：RADIX_TREE_MAP_SIZE = 64
	//#define RADIX_TREE_MAX_TAGS 3
	void __rcu	*slots[RADIX_TREE_MAP_SIZE];
	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

struct address_space {
	struct inode		*host;		/* owner: inode, block_device */
	struct radix_tree_root	page_tree;	/* radix tree of all pages */
	spinlock_t		tree_lock;	/* and lock protecting it */
	......
}

union {
		struct list_head private_list;	/* For tree user */
		struct rcu_head	rcu_head;	/* Used when freeing node */
};

//内存重采样：
//当节点进入释放流程时，原来的 private_list.next 和 private_list.prev 所在的位置
//会被重新解释为 rcu_head.next 和 rcu_head.func
struct callback_head {
    struct callback_head *next;
    void (*func)(struct callback_head *head);
};
typedef struct callback_head rcu_head;

/*
 * Radix-tree tags, for tagging dirty and writeback pages within the pagecache
 * radix trees
 */
/*
    tags[0][0]的64bit用来标记page 的dirty状态，bit0-63的值分别对应slot0-63的状态
    tags[1][0]的64bit用来标记page 的WRITEBACK状态，bit0-63的值分别对应slot0-63的状态
    tags[2][0]的64bit用来标记page 的TOWRITE状态，bit0-63的值分别对应slot0-63的状态
*/
#define PAGECACHE_TAG_DIRTY	0
#define PAGECACHE_TAG_WRITEBACK	1
#define PAGECACHE_TAG_TOWRITE	2

static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
{
	root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
}

static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
{
	root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
}
static inline void root_tag_clear_all(struct radix_tree_root *root)
{
	root->gfp_mask &= __GFP_BITS_MASK;
}

static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
{
	return (__force int)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
}

#define RADIX_TREE_ENTRY_MASK		3UL
#define RADIX_TREE_INTERNAL_NODE	1UL

static inline bool radix_tree_is_internal_node(void *ptr)
{	
	//叶子节点的内存地址至少是按照4字节对齐，即bit0~1需要为0
	return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) ==
				RADIX_TREE_INTERNAL_NODE;
}

//entry_to_node：用来实现将ptr指针的bit0~1位掩掉，也就是将ptr转换为radix_tree_node结构
static inline struct radix_tree_node *entry_to_node(void *ptr)
{
	return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
}

//https://elixir.bootlin.com/linux/v4.11.6/source/lib/radix-tree.c#L599
/*
root：标识radix tree的root
nodep：输出参数，用来返回radix tree的第一个节点的地址
maxindex：输出参数，用来返回radix tree的当前能容纳的最大的node值


返回值：
-	如果radix tree目前是空树（形态1）或者只有一个index为0的叶子结点，此时返回0
-	其他形态，返回值等于第一个节点的shift值+6
*/
static unsigned radix_tree_load_root(const struct radix_tree_root *root,
		struct radix_tree_node **nodep, unsigned long *maxindex)
{
	//先取得`struct radix_tree_root`的`rnode`指针。因为一棵radix tree有且仅有一个`struct radix_tree_root`结构，而`rnode`指向radix tree 的第一个节点，通过它才能遍历整棵radix tree
	struct radix_tree_node *node = rcu_dereference_raw(root->rnode);

	*nodep = node;
	
	//rnode可以等于NULL， 此时表示一棵空树
	//rnode也可以直接指向一个叶子节点； rnode大多数情况是指向一个内部节点
	//rnode非NULL时，使用地址最后两个bit来判断
	if (likely(radix_tree_is_internal_node(node))) {
		node = entry_to_node(node);
		*maxindex = node_maxindex(node);
		return node->shift + RADIX_TREE_MAP_SHIFT;
	}

	*maxindex = 0;
	return 0;
}

void __init radix_tree_init(void)
{
	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
			sizeof(struct radix_tree_node), 0,
			SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
			radix_tree_node_ctor);
	......
}

/*
 * Per-cpu pool of preloaded nodes
 */
struct radix_tree_preload {
	unsigned nr;
	/* nodes->private_data points to next preallocated node */
	struct radix_tree_node *nodes;
};
static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };

//https://elixir.bootlin.com/linux/v4.11.6/source/lib/radix-tree.c#L466
static int __radix_tree_preload(gfp_t gfp_mask, unsigned nr)
{
	struct radix_tree_preload *rtp;
	struct radix_tree_node *node;
	int ret = -ENOMEM;

	gfp_mask &= ~__GFP_ACCOUNT;

	// 因为要访问percpu变量，这里需要禁止抢占，也就是防止，访问percpu变量过程中，执行线程迁移到其他cpu上运行
	preempt_disable();
	rtp = this_cpu_ptr(&radix_tree_preloads);
	while (rtp->nr < nr) {
		// 分配内存过程中，可能出现阻塞，所以在调用内存分配函数之前，使能抢占 
		preempt_enable();
		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
		if (node == NULL)
			goto out;
		//分配内存完成，需要重新禁止抢占，重新获取percpu变量，也需要重新判断percpu内存池的内存对象是否充足
		preempt_disable();
		rtp = this_cpu_ptr(&radix_tree_preloads);
		if (rtp->nr < nr) {
			node->parent = rtp->nodes;
			rtp->nodes = node;
			rtp->nr++;
		} else {
			kmem_cache_free(radix_tree_node_cachep, node);
		}
	}
	//函数返回时，抢占仍然处于禁止状态
	// 后续流程在radix_tree_preload_end函数中调用preempt_enable使能抢占
	ret = 0;
out:
	return ret;
}

static struct radix_tree_node *
radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent,
			struct radix_tree_root *root,
			unsigned int shift, unsigned int offset,
			unsigned int count, unsigned int exceptional)
{
	struct radix_tree_node *ret = NULL;

	/*
	 * Preload code isn't irq safe and it doesn't make sense to use
	 * preloading during an interrupt anyway as all the allocations have
	 * to be atomic. So just do normal allocation when in interrupt.
	 */

	//优先从percpu的内存池分配内存
	if (!gfpflags_allow_blocking(gfp_mask) && !in_interrupt()) {
		struct radix_tree_preload *rtp;

		/*
		 * Even if the caller has preloaded, try to allocate from the
		 * cache first for the new node to get accounted to the memory
		 * cgroup.
		 */
		ret = kmem_cache_alloc(radix_tree_node_cachep,
				       gfp_mask | __GFP_NOWARN);
		if (ret)
			goto out;

		/*
		 * Provided the caller has preloaded here, we will always
		 * succeed in getting a node here (and never reach
		 * kmem_cache_alloc)
		 */
		rtp = this_cpu_ptr(&radix_tree_preloads);
		if (rtp->nr) {
			ret = rtp->nodes;
			rtp->nodes = ret->parent;
			rtp->nr--;
		}
		/*
		 * Update the allocation stack trace as this is more useful
		 * for debugging.
		 */
		kmemleak_update_trace(ret);
		goto out;
	}

	//percpu的内存池不能满足要求时，才直接从radix_tree_node_cachep这个slab申请内存
	ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
out:
	BUG_ON(radix_tree_is_internal_node(ret));
	if (ret) {
		ret->shift = shift;
		ret->offset = offset;
		ret->count = count;
		ret->exceptional = exceptional;
		ret->parent = parent;
		ret->root = root;
	}
	return ret;
}

#define RADIX_TREE_ENTRY_MASK		3UL
#define RADIX_TREE_INTERNAL_NODE	1UL

static inline bool radix_tree_is_internal_node(void *ptr)
{
	return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) ==
				RADIX_TREE_INTERNAL_NODE;
}

static inline struct radix_tree_node *entry_to_node(void *ptr)
{
	return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
}

static inline struct radix_tree_node *entry_to_node(void *ptr)
{
	return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
}

/*
    parent：输入参数，标识radix tree的一个中间节点，要查找index对应的ptr item，需要经由此节点
    nodep：输出参数，要查找index对应的ptr item，需要经由parent节点的下一级节点
    index：输入参数，待查找节点的index
*/
//https://elixir.bootlin.com/linux/v4.11.6/source/lib/radix-tree.c#L125
static unsigned int radix_tree_descend(const struct radix_tree_node *parent,
			struct radix_tree_node **nodep, unsigned long index)
{
	//计算index在当前层级的6bit 索引， 也就是在parent节点中的slot编号
	unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;

	//parent->slots[offset]：指向下一级中间节点或者叶子节点
	void __rcu **entry = rcu_dereference_raw(parent->slots[offset]);

	......

	*nodep = (void *)entry;
	return offset;
}

/*
    root：输入参数，标识radix tree的root
    index：输入参数，待查找节点的index
    nodep：输出参数，用来返回index对应的ptr item的parent节点
    slotp：输出参数，用来返回index对应的ptr item关联的slot的地址
*/
void *__radix_tree_lookup(const struct radix_tree_root *root,
			  unsigned long index, struct radix_tree_node **nodep,
			  void __rcu ***slotp)
{
	struct radix_tree_node *node, *parent;
	unsigned long maxindex;
	void __rcu **slot;

 restart:
	parent = NULL;
	slot = (void __rcu **)&root->rnode;
	// 找到radix树的根
	radix_tree_load_root(root, &node, &maxindex);
	if (index > maxindex)
		return NULL;

	/*
		退出的条件：
		1.	到达叶子节点
		2.	node==NULL
	*/
	while (radix_tree_is_internal_node(node)) {
		unsigned offset;

		if (node == RADIX_TREE_RETRY)
			goto restart;
		parent = entry_to_node(node);
		offset = radix_tree_descend(parent, &node, index);
		slot = parent->slots + offset;
	}

	if (nodep)
		*nodep = parent;
	if (slotp)
		*slotp = slot;
	return node;
}

/*
    root：输入参数，标识radix tree的root
    index：输入参数，待查找节点的index
    order：是在CONFIG_RADIX_TREE_MULTIORDER使能时才使用的参数，正常情况下order = 0
    item：与index关联的指针，需要插入到radix tree的合适位置
*/
//https://elixir.bootlin.com/linux/v4.11.6/source/lib/radix-tree.c#L985
int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
			unsigned order, void *item)
{
	struct radix_tree_node *node;
	void __rcu **slot;
	int error;

	......
	// __radix_tree_create函数调用完成之后
	// node指向了待插入指针item的父节点，slot是item插入位置的slot的地址
	// 调用rcu_assign_pointer(*slot, item)操作相当于*slot = item
	error = __radix_tree_create(root, index, order, &node, &slot);
	if (error)
		return error;

	error = insert_entries(node, slot, item, order, false);
	if (error < 0)
		return error;

	if (node) {
		unsigned offset = get_slot_offset(node, slot);
		BUG_ON(tag_get(node, 0, offset));
		BUG_ON(tag_get(node, 1, offset));
		BUG_ON(tag_get(node, 2, offset));
	} else {
		BUG_ON(root_tags_get(root));
	}

	return 0;
}

/*
    root：输入参数，标识radix tree的root
    index：输入参数，待查找节点的index
    order， 这是在CONFIG_RADIX_TREE_MULTIORDER使能时才使用的参数，正常情况下order = 0
    shift：与当前radixtree第一个节点的shift值相关联，这个值决定了树的高度。如果radix tree为空树（形态1）或者radix tree只有一个index为0的叶子节点(形态2)，则shift = 0；其他的情况，shift = 第一个内部节点的shift值+ 6
*/
//https://elixir.bootlin.com/linux/v4.11.6/source/lib/radix-tree.c#L794
int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
			unsigned order, struct radix_tree_node **nodep,
			void __rcu ***slotp)
{	
	struct radix_tree_node *node = NULL, *child;
	void __rcu **slot = (void __rcu **)&root->rnode;
	unsigned long maxindex;
	unsigned int shift, offset = 0;
	unsigned long max = index | ((1UL << order) - 1);
	gfp_t gfp = root_gfp_mask(root);
	//首先把 slot 指针指向了根节点的 rnode，把整个 root 当作一个虚拟槽位
    //radix_tree_load_root 返回当前树的 shift（高度）以及它能覆盖的最大索引 maxindex
	shift = radix_tree_load_root(root, &child, &maxindex);

	/* Make sure the tree is high enough.  */
	if (order > 0 && max == ((1UL << order) - 1))
		max++;

	/* 1. 如果要查找的index值比当前node所能覆盖的最大index值还要大，这时需要实现radix 
           tree高度的生长（radix_tree_extend函数实现）
       2. radix_tree_extend 函数返回时，期望radix tree 已经有足够的高度能够容纳
           输入参数index。但是有一种例外，就是当root->rnode为NULL时，树的高度还不能够
           容纳输入参数index */
	if (max > maxindex) {
		//radix_tree_extend：见下分析
		int error = radix_tree_extend(root, gfp, max, shift);
		if (error < 0)
			return error;

		// 成功情况下，shift被更新为扩展后的根节点的shift值
		shift = error;
		// set child（默认为新根）
		child = rcu_dereference_raw(root->rnode);
	}

	// 上面仅仅是扩展了radix树，这里还要对radix树（从新的根到插入的index中的途径）进行一些处理
	while (shift > order) {
		shift -= RADIX_TREE_MAP_SHIFT;
		 /* 如果当前节点为NULL，表示到达与index对应的item路径上中间节点缺失，
                   这时需要把中间节点补上 */
		if (child == NULL) {
			//如果路径上某个中间节点是空的（NULL），说明这是第一次访问该分支
			//这里的child表示slots中的某个槽
			child = radix_tree_node_alloc(gfp, node, root, shift,
							offset, 0, 0);
			if (!child)
				return -ENOMEM;
			
			//关键动作：分配一个新节点，并利用 rcu_assign_pointer 挂载到父节点的 slot 中
			rcu_assign_pointer(*slot, node_to_entry(child));
			if (node)
				node->count++;
		} else if (!radix_tree_is_internal_node(child))	/* 到达叶子节点，完成退出 */
			break;

		/* Go a level down */
		//下降一级，调用radix_tree_descend找到下一级内部节点
		node = entry_to_node(child);
		offset = radix_tree_descend(node, &child, index);

		slot = &node->slots[offset];
	}

	// 函数返回时，要填写item所在的父内部节点，以及与item对应slot的地址
	if (nodep)
		*nodep = node;
	if (slotp)
		*slotp = slot;
	return 0;
}

static inline unsigned long shift_maxindex(unsigned int shift){
	return (RADIX_TREE_MAP_SIZE << shift) - 1;
}

//https://elixir.bootlin.com/linux/v4.11.6/source/lib/radix-tree.c#L619
/*
    root：输入参数，标识radix tree的root
    index：输入参数，待查找节点的index。在radix tree中要有足够的高度能够容纳该index
    shift：与当前radixtree第一个节点的shift值相关联，这个值决定了树的高度。如果radix tree为空树（形态1）或者radix tree只有一个index为0的叶子节点(形态2)，则shift = 0；其他的情况，shift = 第一个内部节点的shift值+ 6
*/
static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
				unsigned long index, unsigned int shift){
	void *entry;
	unsigned int maxshift;
	int tag;

	/* 
	1、step1：计算目标高度
	下面while循环用来计算，radix tree 需要生长到的高度
	只要给定的 index 超过了当前 maxshift 能表示的最大值（例如 64 叉树，高度每增加 1，覆盖范围扩大 64 倍），就不断增加 maxshift
	*/
	maxshift = shift;
	while (index > shift_maxindex(maxshift))
		maxshift += RADIX_TREE_MAP_SHIFT;

	//2、空树，直接跳出返回计算出的 maxshift，后续调用者（如 create 函数）会发现根是空的，直接从最高层向下分配节点
	entry = rcu_dereference_raw(root->rnode);
	if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))
		goto out;	/* 对于空树，跳过下面的树纵向生长的过程 */
	
	// 以下是树纵向生长的过程，root->rnode已经存在
	do {
		 /* 分配一个node, 该新分配的node将关联到root->rnode，
		  也就是说这个新分配的node将成为根节点，原先的根节点反而成为新分
          配节点的子节点 */

		//注意参数parent：传入的是 NULL（因为它将成为新的顶层）
		//count 设为 1（参数中的倒数第二个 1），因为这个新节点目前只有一个子节点——即原来的旧根
		struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL,
							root, shift, 0, 1, 0);
		if (!node)
			return -ENOMEM;
		
		//标签（Tags）的向上迁移
		/*
		这是基数树保持查找效率的关键。如果旧的根节点里有某个标签（比如 DIRTY），那么新的根节点也必须在对应的槽位（这里是 slots[0]）打上这个标签
	    -	如果是 IDR：默认设置 IDR_FREE 标签
		-	如果是 Page Cache：遍历所有可能的标签（如 Dirty, Writeback），如果旧根有，新根的 slots[0] 也要有
		*/
		if (is_idr(root)) {
			all_tag_set(node, IDR_FREE);
			if (!root_tag_get(root, IDR_FREE)) {
				tag_clear(node, IDR_FREE, 0);
				root_tag_set(root, IDR_FREE);
			}
		} else {
			/* Propagate the aggregated tag info to the new child */
			for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
				if (root_tag_get(root, tag))
					tag_set(node, tag, 0);
			}
		}

		BUG_ON(shift > BITS_PER_LONG);
		if (radix_tree_is_internal_node(entry)) {
			//entry（旧的root）的父亲节点变为node（新申请的节点）
			entry_to_node(entry)->parent = node;
		} else if (radix_tree_exceptional_entry(entry)) {
			//异常条目：如果旧的根直接就是一个 exceptional entry（比如影子条目），新节点的 exceptional 计数要更新
			/* Moving an exceptional root->rnode to a node */
			node->exceptional = 1;
		}
		/*
		 * entry was already in the radix tree, so we do not need
		 * rcu_assign_pointer here
		 */
		node->slots[0] = (void __rcu *)entry;	// 旧根变成新根的第一个孩子（原先的根节点关联到新分配节点的slot[0]上 ）
		entry = node_to_entry(node);			// 把新节点包装成 entry
		rcu_assign_pointer(root->rnode, entry);	// 更新全局根指针
		shift += RADIX_TREE_MAP_SHIFT;
	} while (shift <= maxshift);
out:

	 /* 这里最后返回的时候，maxshift还要在加6，因为__radix_tree_create
          函数在while循环的判断条件是，当order=0，且shift=0， 循环就结束了 */
	return maxshift + RADIX_TREE_MAP_SHIFT;
}

......
node->slots[0] = (void __rcu *)entry;
entry = node_to_entry(node);
rcu_assign_pointer(root->rnode, entry);	
......

//https://elixir.bootlin.com/linux/v4.11.6/source/lib/radix-tree.c#L961
static inline int insert_entries(struct radix_tree_node *node,
		void __rcu **slot, void *item, unsigned order, bool replace)
{
	if (*slot)
		return -EEXIST;

	// 将item填写到待插入位置
	// rcu_assign_pointer(*slot, item)操作相当于*slot = item
	rcu_assign_pointer(*slot, item);
	if (node) {
		// node为item所关联的父节点， item插入后node的子节点个数递增
		node->count++;
		if (radix_tree_exceptional_entry(item))
			node->exceptional++;
	}
	return 1;
}

struct idr {
	struct radix_tree_root	idr_rt;
	unsigned int		idr_base;
	unsigned int		idr_next;
};

#define radix_tree_root		xarray
#define radix_tree_node		xa_node

//https://elixir.bootlin.com/linux/v6.18/source/include/linux/xarray.h#L300
struct xarray {
	spinlock_t	xa_lock;
/* private: The rest of the data structure is not to be used directly. */
	gfp_t		xa_flags;
	void __rcu *	xa_head;
};

//https://elixir.bootlin.com/linux/v6.18/source/include/linux/xarray.h#L1168
struct xa_node {
	unsigned char	shift;		/* Bits remaining in each slot */
	unsigned char	offset;		/* Slot offset in parent */
	unsigned char	count;		/* Total entry count */
	unsigned char	nr_values;	/* Value entry count */
	struct xa_node __rcu *parent;	/* NULL at top of tree */
	struct xarray	*array;		/* The array we belong to */
	union {
		struct list_head private_list;	/* For tree user */
		struct rcu_head	rcu_head;	/* Used when freeing node */
	};
	void __rcu	*slots[XA_CHUNK_SIZE];  //核心，指针字段，有点像字符串radix的edges
    //默认XA_CHUNK_SIZE为64
	union {
        //#define XA_MAX_MARKS		3
        //#define XA_MARK_LONGS		BITS_TO_LONGS(XA_CHUNK_SIZE)
		unsigned long	tags[XA_MAX_MARKS][XA_MARK_LONGS];
		unsigned long	marks[XA_MAX_MARKS][XA_MARK_LONGS];
	};
};

//https://elixir.bootlin.com/linux/v6.18/source/kernel/pid.c#L163
struct pid *alloc_pid(struct pid_namespace *ns, pid_t *set_tid,size_t set_tid_size)
{
    ......

    // 进程可能归属多个命名空间，在每一个命令空间中都需要分配进程号
    // 实际调用 idr_alloc 来申请整数类型的进程号 
    tmp = ns;
    pid->level = ns->level;
    for (i = ns->level; i >= 0; i--) {
        ......
        nr = idr_alloc(&tmp->idr, NULL, tid,
                tid + 1, GFP_ATOMIC);
        ......
        pid->numbers[i].nr = nr;
        pid->numbers[i].ns = tmp;
        tmp = tmp->parent;
    }
    ......
}

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

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;

    ......

	id = (id < base) ? 0 : id - base;
	radix_tree_iter_init(&iter, id);

    //核心操作：遍历radix tree的若干节点，并根据每个节点的 tag、slot 等字段找出还未被占用的整数 ID
	slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
	if (IS_ERR(slot))
		return PTR_ERR(slot);

	*nextid = iter.index + base;
	/* there is a memory barrier inside radix_tree_iter_replace() */
	radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
	radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);

	return 0;
}

void __rcu **idr_get_free(struct radix_tree_root *root, ...)
{
    ......
    shift = radix_tree_load_root(root, &child, &maxindex);
    while (shift) {
        shift -= RADIX_TREE_MAP_SHIFT; //RADIX_TREE_MAP_SHIFT为6
        ......

        // 遍历 tag 状态 bitmap，寻找下一个可用的下标
        offset = radix_tree_find_next_bit(node, IDR_FREE,
            offset + 1);
        start = next_index(start, node, offset);
    }
    ......
}