p = rcu_dereference_raw(idp->top); //获取根top
if (!p)
return NULL;
n = (p->layer+1) * IDR_BITS; //计算最外层的n值
id &= MAX_ID_MASK;
if (id >= (1 << n))
return NULL;
BUG_ON(n == 0);
while (n > 0 && p) { //循环一层层查找
n -= IDR_BITS;
BUG_ON(n != p->layer*IDR_BITS);
p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); //一次获取an ... a0
}
return((void *)p);
}
EXPORT_SYMBOL(idr_find);
前面讲过32进制的id值算法
当构建完idr机制之后
id=top->ary[an]->ary[a(n-1)]->....->ary[a0]来获得
借助图片分析下(idr_layer13的位图标记有错)
五idr操作
1. idr_remove idr_remove_all 移除
[cpp] www.2cto.com
void idr_remove(struct idr *idp, int id)
{
struct idr_layer *p;
struct idr_layer *to_free;
id &= MAX_ID_MASK;
sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
idp->top->ary[0]) {
to_free = idp->top;
p = idp->top->ary[0];
rcu_assign_pointer(idp->top, p);
--idp->layers;
to_free->bitmap = to_free->count = 0;
free_layer(to_free);
}
while (idp->id_free_cnt >= IDR_FREE_MAX) {
p = get_from_free_list(idp);
kmem_cache_free(idr_layer_cache, p);
}
return;
}
EXPORT_SYMBOL(idr_remove);
移除全部
[cpp]
void idr_remove_all(struct idr *idp)
{
int n, id, max;
int bt_mask;
struct idr_layer *p;
struct idr_layer *pa[MAX_LEVEL];
struct idr_layer **paa = &pa[0];
n = idp->layers * IDR_BITS;
p = idp->top;
rcu_assign_pointer(idp->top, NULL);
max = 1 << n;
id = 0;
while (id < max) {
while (n >
IDR_BITS && p) {
n -= IDR_BITS;
*paa++ = p;
p = p->ary[(id >> n) & IDR_MASK];
}
bt_mask = id;
id += 1 << n;
/* Get the highest bit that the above add changed from 0->1. */
while (n < fls(id ^ bt_mask)) {
if (p)
free_layer(p);
n += IDR_BITS;
p = *--paa;
}
}
idp->layers = 0;
}
EXPORT_SYMBOL(idr_remove_all);
2.idr_replace 替换
[cpp]
void *idr_replace(struct idr *idp, void *ptr, int id)
{
int n;
struct idr_layer *p, *old_p;
p = idp->top;
if (!p)
return ERR_PTR(-EINVAL);
n = (p->layer+1) * IDR_BITS;
id &= MAX_ID_MASK;
if (id >= (1 << n))
return ERR_PTR(-EINVAL);
n -= IDR_BITS;
while ((n > 0) && p) {
p = p->ary[(id >> n) & IDR_MASK];
n -= IDR_BITS;
}
n = id & IDR_MASK;
if (unlikely(p == NULL || !test_bit(n, &p->bitmap)))
return ERR_PTR(-ENOENT);
old_p = p->ary[n];
rcu_assign_pointer(p->ary[n], ptr);
return old_p;
}
EXPORT_SYMBOL(idr_replace);
六.idr空闲链表的销毁
idr_destroy
[cpp]
void idr_destroy(struct idr *idp)
{
while (idp->id_free_cnt) {
struct idr_layer *p = get_from_free_list(idp);
kmem_cache_free(idr_layer_cache, p);
}
}
EXPORT_SYMBOL(idr_destroy);
七.用法
1.api函数
[cpp]
void *idr_find(struct idr *idp, int id); //查找id对应的指针
int idr_pre_get(struct idr *idp, gfp_t gfp_mask); //分配idr_layer空闲链表
int idr_get_new(struct idr *idp, void *ptr, int *id); /