一.结构体
1.idr结构体
[cpp]
struct idr {
struct idr_layer __rcu *top; //idr_layer顶层,32叉树的根
struct idr_layer *id_free; //指向idr_layer的空闲链表
int layers; //idr_layer的层数量
int id_free_cnt; //idr_layer空闲链表中剩余的idr_layer个数
spinlock_t lock;
};
2.idr_layer结构体
[cpp
struct idr_layer {
unsigned long bitmap; //标记位图,标记使用情况
struct idr_layer __rcu *ary[1<<IDR_BITS]; //子idr_layer数组ary[32]
int count; //ary数组使用情况
int layer; //层号
struct rcu_head rcu_head;
};
在32位系统中IDR_BITS的取值为5
[cpp]
#if BITS_PER_LONG == 32
# define IDR_BITS 5
# define IDR_FULL 0xfffffffful
# define TOP_LEVEL_FULL (IDR_FULL >> 30)
#elif BITS_PER_LONG == 64
# define IDR_BITS 6
# define IDR_FULL 0xfffffffffffffffful
# define TOP_LEVEL_FULL (IDR_FULL >> 62)
#else
# error "BITS_PER_LONG is not 32 or 64"
#endif
二.idr的初始化
[cpp]
#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)
定义一个idr结构体并赋值
三.分配id
1.idr_pre_get
[cpp]
int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
{
while (idp->id_free_cnt < IDR_FREE_MAX) { //IDR_FREE_MAX=14
struct idr_layer *new; //定义新的idr_layer结构体指针
new = kmem_cache_zalloc(idr_layer_cache, gfp_mask); //分配*new内存空间
if (new == NULL)
return (0);
move_to_free_list(idp, new); //-->move_to_free_list
}
return 1;
}
EXPORT_SYMBOL(idr_pre_get);
move_to_free_list
[cpp]
static void move_to_free_list(struct idr *idp, struct idr_layer *p)
{
unsigned long flags;
spin_lock_irqsave(&idp->lock, flags);
__move_to_free_list(idp, p); //-->__move_to_free_list
spin_unlock_irqrestore(&idp->lock, flags);
}
__move_to_free_list
[cpp]
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++;
}
第一次循环结果
接着循环
再接着
一直这样下去直到循环结束(14次)
2.idr_get_new和idr_get_new_above
idr_get_new
[cpp]
int idr_get_new(struct idr *idp, void *ptr, int *id)
{
int rv;
rv = idr_get_new_above_int(idp, ptr, 0);
if (rv < 0)
return _idr_rc_to_errno(rv);
*id = rv;
return 0;
}
EXPORT_SYMBOL(idr_get_new);
idr_get_new_above
[cpp]
int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
{
int rv;
rv = idr_get_new_above_int(idp, ptr, starting_id);
if (rv < 0)
return _idr_rc_to_errno(rv);
*id = rv;
return 0;
}
EXPORT_SYMBOL(idr_get_new_above);
两个函数都会调用idr_get_new_above_int函数,差别在于starting_id不同
下面分情况讨论,先以id为0走个过场
idr的top简称为根top,free简称为根free均为idr_layer指针类型,分别指向使用中和空闲idr_layer链表头
[cpp]
static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
{
struct idr_layer *pa[MAX_LEVEL]; //MAX_LEVEL=7
int id;
id = idr_get_empty_slot(idp, starting_id, pa); //-->idr_get_empty_slot
if (id >= 0) {
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],(struct idr_layer *)ptr
//pa[0]->ary[0]=ptr 也就是idr_layer14->ary[0]=ptr
pa[0]->count++; //idr_layer14->count++
idr_mark_full(pa, id); //设置其位图-->走完0过场的效果见图c
}
return id;
}
idr_get_empty_slot
[cpp]
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; //按常规出牌吧,假设这个为0
build_up:
p = idp->top; //根top指向的idr_layer NULL
layers = idp->layers; //获取layers层数量(0)
if (unlikely(!p)) { //第一次运行idp->top=NULL,所以if条件为真,执行if分支的结果参考 图A
if (!(p = get_from_free_list(idp))) //>>>1-->get_from_free_list 从根free中获取一个idr_layer14
return -1;
