这篇文章主要讲述如何给要管理的对象分配一个小数字作为id。
首先看知道obj的ID，如果查找obj
，即指向obj的指针。也就是说先看我们想要达到的效果，在来分析如何实现给对象分配ID。
根据ID ,来查找obj。函数idr_find实现查找功能
假如下图中C
的ary[2]指向一个管理的obj。我们来看下如何通过数字66来查找到obj。
我们以top为根的树其实是一个32叉树。如果只有一层，那么top本身指向叶子层，那么最多理32个obj，即ary数组的每个元素，指向一个obj。
但是假如说我们管理的对象超过了32个，我们就不能用一层来管理这个需要有两层结构。就像我们的示意图。
其实idr有一种比较简单的理解方式，就是它是一种32进制的数，满32，向前进一位。
我们还是从示意图讲起。我们寻找66指向的obj。首先判断66是否超过了当前层数所能管理最多obj。
当前我们是两层结构，top指向32叉树的根，top下面管理32个叶子层的idr_layer。上面一讲提到了，叶子层idr_layer的ary数组元素是用来指向目标obj的。那么两层总共可以管理32*32=1024个obj。同样道理三层可以最多管理32*32*32=32K
个obj。
要想找到obj的指针，必须根据ID，一路寻找的叶子层。66/32
= 2,所以从top--->top->ary[2],
我们就找到了叶子节点C。66|IDR_MASK
= 2，所以C的ary[2]指向管理的obj。
用前面的32进制方法理解就是66
= 2*32+2，所以，top->ary[2]->ary[2]指向obj。
同样我们可以求ID是27对应的obj
27=0*32+27，所以top->ary[0]->ary[27]指向obj。
小结
：通过上面的描述，我们也看到了，我们就是要建立一个32叉树，来管理obj。通过ID，可以一层层定位到叶子层，叶子层的指针指向的就是我们要管理的obj。 需要指出的是32叉树，不一定每个分支都分配好了idr_layer，用到了再分配，防止浪费，比如示意图中，并没有用到32~63，我们看到top->ary[1]为NULL。如有需要分配34了，那没办法，会在分配过程中分配个idr_layer,top->ary[1]指向分配的idr_layer。
void *idr_find(struct idr *idp, int id)
{
int n;
struct idr_layer *p;
n = idp->layers * IDR_BITS;
p = idp->top;
/* Mask off upper bits we don't use for the search. */
id &= MAX_ID_MASK;
if (id >= (1 << n))
return NULL;
while (n > 0 && p) {
n -= IDR_BITS;
p = p->ary[(id >> n) & IDR_MASK];
}
return((void *)p);
}
下面分析如果给一个obj分配个ID。
提供两个函数给obj分配ＩＤ
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)
参数说明：idp---不说了，管理结构idr的指针，对应示意图中最左面的那个结构。
ptr---指向要管理的结构的指针，我们的任务就是给它分配个小数字，作为他的身份证。成功之后，
我们可以拿着这个ID，直接找到ptr。
id----输出参数，将分配的数字存入id。
这两个函数其中idr_get_new比较乖，比较好说话，随便给他分配一个没人用的id就可以，他他不挑不捡。第二个函数idr_get_new_above有点难说话，要求挺多，他有个参数starting_id，要求分配不小于starting_id的一个数字作为id。
两个函数都是调用了idr_get_new_above_int，区别是idr_get_new将starting_id填成了0.表示随便给分配个大于0的没被别人用的id就行。
-EAGAIN的意思上面一讲提到过，这个是预备役全体阵亡的遗言，没有空闲的idr_layer用来分配了，所以失败了，如果用户非常需要给ptr分配个id，那么请先分配点预备役，即调用idr_pre_get。
-ENOSPC的含义是你小子要的id太大了，超过了MAX_ID_BIT，即2^31，idr说，我是管理小数字的结构，拜托不要那这么大的数字骚扰我。
if ((id >= MAX_ID_BIT) || (id < 0))
return -3; // sub_alloc函数中的语句
int idr_get_new(struct idr *idp, void *ptr, int *id)
{
int rv;
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) {
if (rv == -1)
return -EAGAIN;
else /* Will be -3 */
return -ENOSPC;
}
*id = rv;
return 0;
}
---------------------------------------------------------------------------------------
酝酿了半天，可以聊聊idr_get_new_above_int这个了。
idr_get_empty_slot函数是分配个大于starting_id的数字作为ptr的ID。如果分配成功，id>=0,将叶子节点id对应的ary数组的元素赋值为
ptr。同时将叶子层的count++，表示又分配出去一个。将叶子层的位图bitmap对应槽位置1的工作是idr_mark_full完成。如果叶子层全满了，则通知叶子层的父亲对应槽位置1，依次传递。
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.
*/
pa[0]->ary[id & IDR_MASK] = (struct idr_layer *)ptr;
pa[0]->count++;
idr_mark_full(pa, id);
}
return id;
}
OK，到了idr_get_empty_slot。这个函数是干重活的函数。需要仔细研读代码。这个函数不举例子很难描述清楚，举例子又显得特别琐碎，很头疼。建议读者从0开始分配一直分配到32需要分层，就可以理解代码的含义。
先讲初始化：
#define IDR_INIT(name) \
{ \
.top = NULL, \
.id_free = NULL, \
.layers = 0, \
.id_free_cnt = 0, \
.lock = __SPIN_LOCK_UNLOCKED(name.lock), \
}
top等于NULL
表示我的32叉树还没建立起来，id_free
=NULL，id_free_cnt=0表示不好意思，我的预备役也为空，没法为您分配idr_layer。这是最初的状态，32叉树连个根都没有，整个idr处于一穷二白的状态。
p = idp->top;
layers = idp->layers;
if (unlikely(!p)) {
if (!(p = alloc_layer(idp)))
return -1;
layers = 1;
}
idr_get_empty_slot这个部分，表示如果ｉｄｒ的３２叉树连个根都没有，我需要分配一个idr_layer来当根。如果alloc_layer失败，表示预备役空了，惨了，只能返回失败，告诉调用者，预备役没了，请填充预备役。一般是可以分配的。
这个循环体的含义是，用户这个搞得这个starting_id太大了，或者低的id分配出去了，只能给用户分配个大的id。如果这个id大于了当前层数所能管理的最高ID，我们需要加一层了。
以上面的示意图为例，我们当前有两层结构，最多能管理32*32=1K个，我们能分配的最大id就是1023，如果用户要求我们分配大于等于1500的id，那么我们目前的两层结构是无法满足需要的，所以我们需要加一层。首先将layer++，表示我们的32叉树升级了，多了一层，从预备役分配出一个idr_layer，让新分配的new当根。p指针指向根。
如果分配的id不够大，不需要分层，那么这个while就不执行了，直接跳到sub_alloc函数。
while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
layers++;
if (!p->count)//这个地方是应对特殊情况，比如0~31都没有分配，第一层还没有，用户
//上来要分配32或46这样明显是两层才能完成的结构
continue;
if (!(new = alloc_layer(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;
__free_layer(idp, new);
}
spin_unlock_irqrestore(&idp->lock, flags);
return -1;
}
new->ary[0] = p;
new->count = 1;
if (p->bitmap == IDR_FULL)
__set_bit(0, &new->bitmap);
p = new;
}
idp->top = p;
idp->layers = layers;
v = sub_alloc(idp, &id, pa);
if (v == -2)
goto build_up;
------------------------------------------------------------------------------------------
sub_alloc函数。
还是以示意图为例讲述