迷彩 潜伏 隐蔽 伪装
分类: LINUX
2013-06-08 10:20:37
原文地址: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
后面就容易理解了。