应用IDR机制时要包含头文件
struct idr {
struct idr_layer *top; //IDR顶层
struct idr_layer *id_free; //预留的可用idr layer指针
int layers; /* only valid without concurrent changes */ //IDR树的层数
int id_free_cnt; //预留的可用idr layer数目
spinlock_t lock; //锁保护
};
而idr layer的结构体如下
struct idr_layer {
unsigned long bitmap; /* A zero bit means "space here" */ //节点的位图，0表示slot槽空闲可用
struct idr_layer *ary[1<
int layer; /* distance from leaf */ //与叶子节点的距离，以0开始
struct rcu_head rcu_head;//rcu锁
};
首先创建一个IDR对象需要定义一个struct idr，并将指针传给函数void idr_init(struct idr *idp);一般采用快捷方式DEFINE_IDR(name)来创建，定义如下
#define IDR_INIT(name) \
{ \
.top = NULL, \
.id_free = NULL, \
.layers = 0, \
.id_free_cnt = 0, \
.lock = __SPIN_LOCK_UNLOCKED(name.lock), \
}
#define DEFINE_IDR(name) struct idr name = IDR_INIT(name)
要获得一个ID号要分两个步骤，首先分配内存，其次是获得ID号；因此，先调用函数
int idr_pre_get(struct idr *idp, gfp_t gfp_mask);
注意该函数会导致睡眠，因此不应该用锁保护，函数实现如下
int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
{
//通过kmem_cache_zalloc函数申请足够的内存空间，IDR_FREE_MAX定义为2倍的MAX_LEVEL，即14；所以一共预申请了14个idr_layer内存空间
while (idp->id_free_cnt < IDR_FREE_MAX) {
struct idr_layer *new;
new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
if (new == NULL)
return (0);
//该函数将预申请的idr_layer内存放入可用链表中，具体分析如下
move_to_free_list(idp, new);
}
return 1;
}
static void move_to_free_list(struct idr *idp, struct idr_layer *p)
{
unsigned long flags;
/*
* Depends on the return element being zeroed.
*/
spin_lock_irqsave(&idp->lock, flags);
__move_to_free_list(idp, p); //真正调用的函数
spin_unlock_irqrestore(&idp->lock, flags);
}
static void __move_to_free_list(struct idr *idp, struct idr_layer *p)
{
p->ary[0] = idp->id_free;
idp->id_free = p;
idp->id_free_cnt++;
}
在初始化创建IDR对象时，top设为NULL，id_free设为NULL，id_free_cnt设为0，在将第一个idr_layer移入链表时， 该idr_layer第一个slot槽（ary[0]）指向id_free（NULL），而id_free指向新加入的 idr_layer，id_free_cnt加1，如下图所示
第二个idr_layer移入链表时，该idr_layer第一个slot槽（ary[0]）指向第一个idr_layer，而id_free指向第二个 idr_layer，id_free_cnt自加到2；一次移入第三个，第四个，…，直到第十四个idr_layer为止，最终id_free指向最后一 个idr_layer，id_free_cnt为14，如下图所示
调用函数idr_pre_get成功后，将返回1，若申请不到内存则返回0；接下来，可通过下面的任一函数来获得ID号：
int idr_get_new(struct idr *idp, void *ptr, int *id)；
int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)；
这两个函数的区别在于idr_get_new函数是从0开始申请ID号，而idr_get_new_above是从starting_id开始申请ID号，这里我们将只分析第一个函数：
int idr_get_new(struct idr *idp, void *ptr, int *id)
{
int rv;
//具体调用idr_get_new_above_int函数，我们发现idr_get_new和idr_get_new_above函数的区别在于传入的第三个参数是0还是starting_id
rv = idr_get_new_above_int(idp, ptr, 0);
/*
* This is a cheap hack until the IDR code can be fixed to
* return proper error values.
*/
if (rv < 0)
return _idr_rc_to_errno(rv);
*id = rv;
return 0;
}
static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
{
struct idr_layer *pa[MAX_LEVEL];
int id;
id = idr_get_empty_slot(idp, starting_id, pa);
if (id >= 0) {
/*
* Successfully found an empty slot. Install the user
* pointer and mark the slot full.
*/
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],
(struct idr_layer *)ptr);
pa[0]->count++;
idr_mark_full(pa, id);
}
return id;
}
该函数先后调用了idr_get_empty_slot，rcu_assign_pointer和idr_mark_full这三个函数，先来分析idr_get_empty_slot函数：
static int idr_get_empty_slot(struct idr *idp, int starting_id,
struct idr_layer **pa)
{
struct idr_layer *p, *new;
int layers, v, id;
unsigned long flags;
id = starting_id; //starting_id为0
build_up:
//我们以初始化idr后的第一次申请ID号为例
p = idp->top; //初始化时idp->top设为NULL
layers = idp->layers; //初始化时idp->layers设为0
if (unlikely(!p)) {
//该函数是从idr_pre_get申请的空闲idr_layer内存中获得一块赋给p，
具体实现函数如下分析
if (!(p = get_from_free_list(idp)))
return -1;
p->layer = 0;
layers = 1;
}
/*
* Add a new layer to the top of the tree if the requested
* id is larger than the currently allocated space.
*/
while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
layers++;
if (!p->count) {
/* special case: if the tree is currently empty,
* then we grow the tree by moving the top node
* upwards.
*/
p->layer++;
continue;
}
if (!(new = get_from_free_list(idp))) {
/*
* The allocation failed. If we built part of
* the structure tear it down.
*/
spin_lock_irqsave(&idp->lock, flags);
for (new = p; p && p != idp->top; new = p) {
p = p->ary[0];
new->ary[0] = NULL;
new->bitmap = new->count = 0;
__move_to_free_list(idp, new);
}
spin_unlock_irqrestore(&idp->lock, flags);
return -1;
}
new->ary[0] = p;
new->count = 1;
new->layer = layers-1;
if (p->bitmap == IDR_FULL)
__set_bit(0, &new->bitmap);
p = new;
}
//将p，即通过get_from_free_list函数获得的内存赋给top层
rcu_assign_pointer(idp->top, p);
idp->layers = layers; //此时只有根节点，layers为1
//该函数真正实现ID号的获得
v = sub_alloc(idp, &id, pa);
if (v == IDR_NEED_TO_GROW)
goto build_up;
return(v);
}
static struct idr_layer *get_from_free_list(struct idr *idp)
{
struct idr_layer *p;
unsigned long flags;
spin_lock_irqsave(&idp->lock, flags);
//idp->id_free非零，说明有预留的idr_layer内存可用
if ((p = idp->id_free)) {
//此时将最后申请的可用idr_layer内存从链表中移除，将id_free指向前一个预留内存，如下如图所示（蓝线标出）
idp->id_free = p->ary[0];//p->ary[0]指向前一个预留内存
idp->id_free_cnt--; //数目减一
p->ary[0] = NULL; //slot0槽设为空
}
spin_unlock_irqrestore(&idp->lock, flags);
return(p);
}
函数idr_get_new_above_int中的rcu_assign_pointer实现了指针与ID号的绑定，并将指针保存在ary的slot槽中；
函数idr_get_new_above_int中的idr_mark_full根据ID号来置位bitmap，代码如下
static void idr_mark_full(struct idr_layer **pa, int id)
{
struct idr_layer *p = pa[0];
int l = 0;
//根据id设置bitmap相应位
__set_bit(id & IDR_MASK, &p->bitmap);
/*
* If this layer is full mark the bit in the layer above to
* show that this part of the radix tree is full. This may
* complete the layer above and require walking up the radix
* tree.
*/
while (p->bitmap == IDR_FULL) {
if (!(p = pa[++l]))
break;
id = id >> IDR_BITS;
__set_bit((id & IDR_MASK), &p->bitmap);
}
}
总的实现如下图的红色部分表示。
若已知ID号，而要得到相应的指针，则可调用函数：
void *idr_find(struct idr *idp, int id);
若删除ID号并释放指针，可调用函数：
void idr_remove(struct idr *idp, int id);
若要销毁idr树，则可调用函数：
void idr_destroy(struct idr *idp);
通过上述这些函数接口，我们能够产生ID号用做设备的次设备号，节点号等，在内核的rtc子系统的设备注册中，就用到了idr机制，代码如下（/drivers/rtc/class.c）：
//初始化一个rtc的idr对象
static DEFINE_IDR(rtc_idr);
struct rtc_device *rtc_device_register(const char *name, struct device *dev,
const struct rtc_class_ops *ops,
struct module *owner)
{
struct rtc_device *rtc;
int id, err;
//为rtc_idr预留内存空间
if (idr_pre_get(&rtc_idr, GFP_KERNEL) == 0) {
err = -ENOMEM;
goto exit;
}
mutex_lock(&idr_lock);
err = idr_get_new(&rtc_idr, NULL, &id); //获得ID号
mutex_unlock(&idr_lock);
if (err < 0)
goto exit;
id = id & MAX_ID_MASK; //ID号范围是0～0x7fffffff，而rtc的设备数目RTC_DEV_MAX定义为16
rtc = kzalloc(sizeof(struct rtc_device), GFP_KERNEL);
if (rtc == NULL) {
err = -ENOMEM;
goto exit_idr;
}
rtc->id = id;//将获得的ID号作为rtc的次设备号
rtc->ops = ops;
rtc->owner = owner;
rtc->max_user_freq = 64;
rtc->dev.parent = dev;
rtc->dev.class = rtc_class;
rtc->dev.release = rtc_device_release;
mutex_init(&rtc->ops_lock);
spin_lock_init(&rtc->irq_lock);
spin_lock_init(&rtc->irq_task_lock);
init_waitqueue_head(&rtc->irq_queue);
strlcpy(rtc->name, name, RTC_DEVICE_NAME_SIZE);
dev_set_name(&rtc->dev, "rtc%d", id);
rtc_dev_prepare(rtc);
err = device_register(&rtc->dev);
if (err)
goto exit_kfree;
rtc_dev_add_device(rtc);
rtc_sysfs_add_device(rtc);
rtc_proc_add_device(rtc);
dev_info(dev, "rtc core: registered %s as %s\n",
rtc->name, dev_name(&rtc->dev));
return rtc;
exit_kfree:
kfree(rtc);
exit_idr:
mutex_lock(&idr_lock);
idr_remove(&rtc_idr, id);
mutex_unlock(&idr_lock);
exit:
dev_err(dev, "rtc core: unable to register %s, err = %d\n",
name, err);
return ERR_PTR(err);
}