linux中idr基本原理介绍

idr是一个管理结构，它管理了多个idr_layer结构变量，这些idr_layer结构变量组成了一个id——地址的映射空间。理论上它能够保存的id从0——0xffffffff，它兼顾了数组产寻速度快和链表占用空间小的优点。

idr的管理思路比较简单，单单从代码上看比较枯燥，源代码分析的博文也非常多，因此这里不再分析一些代码细节，更多从原理上进行说明，看完原理之后，再看代码自然简单很多了。

每个 idr_layer表示一个叶节点或者一个中间节点或者一个根节点。

struct idr_layer {

unsigned long bitmap; /*位图，对叶节点来说，bit[i]为1表明其中的ary[i]已经分配了，对其他节点来说bit[i]为1表明ary[i]及其更下层都已经分配完了*/

struct idr_layer __rcu *ary[1<

int count; /* 计数器，记录 ary[]有效的个数*/

int layer; /* 距离叶节点的距离 */

struct rcu_head rcu_head;

};

idr管理一个由 idr_layer组成的树。

struct idr {

struct idr_layer __rcu top; /* 指向树的根节点 */

struct idr_layer *id_free; /* 指向空闲idr_layer结构变量链表表头 */

int layers; /* 树的高度 */

int id_free_cnt; /* 指向空闲idr_layer结构变量个数 */

spinlock_t lock;

};

下面举出几个例子来说明idr的管理形式。首先假定idr只管理了一个id，id=15，那么树的形式是这样的：

如果下一个我需要增加一个id=0x123456进制的项，是什么情况呢，首先将其转换为二进制数，然后5位1组，变成32进制数 0b1 0010 0011 0100 0101 0110

= 0b1 00100 01101 00010 10110

后面就容易理解了。