idr机制(32叉树)(三)
ZE, n); //>>>1 find_next_bit 位图中偏移量为n处查找'1'
if (m == IDR_SIZE) { //位图满了
l++;
oid = id;
id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
if (id >= 1 << (idp->layers * IDR_BITS)) {
*starting_id = id;
return IDR_NEED_TO_GROW;
}
p = pa[l];
BUG_ON(!p);
sh = IDR_BITS * (l + 1);
if (oid >> sh == id >> sh)
continue;
else
goto restart;
}
if (m != n) { //期望的n值被占用,但可找到可用的m值
sh = IDR_BITS*l;
id = ((id >> sh) ^ n ^ m) << sh; //>>>2 重新计算id值
}
if ((id >= MAX_ID_BIT) || (id < 0))
return IDR_NOMORE_SPACE;
if (l == 0) //l==0跳出while循环
break;
if (!p->ary[m]) {
new = get_from_free_list(idp);
if (!new)
return -1;
new->layer = l-1;
rcu_assign_pointer(p->ary[m], new);
p->count++;
}
pa[l--] = p;
p = p->ary[m];
}
pa[l] = p; //pa[0]=p 也就是idr_layer14
return id;
}
>>>find_next_bit
[cpp] view plaincopy
#define find_next_bit(p,sz,off) _find_next_bit_le(p,sz,off) //>>_find_next_bit_le
该宏的意思是在p指向的(大小为sz的)位图表中的第off个位置开始找寻可用(为"1")的格子,找到返回该位
_find_next_bit_le是汇编代码实现的定义在/arch/arm/lib/findbit.S
[cpp]
ENTRY(_find_next_bit_le)
teq r1, #0
beq 3b
ands ip, r2, #7
beq 1b @ If new byte, goto old routine
ARM( ldrb r3, [r0, r2, lsr #3] )
THUMB( lsr r3, r2, #3 )
THUMB( ldrb r3, [r0, r3] )
movs r3, r3, lsr ip @ shift off unused bits
bne .L_found
orr r2, r2, #7 @ if zero, then no bits here
add r2, r2, #1 @ align bit pointer
b 2b @ loop for next bit
ENDPROC(_find_next_bit_le)
.L_found找到合适的跳转
[cpp]
.L_found:
#if __LINUX_ARM_ARCH__ >= 5
rsb r0, r3, #0
and r3, r3, r0
clz r3, r3
rsb r3, r3, #31
add r0, r2, r3
#else
tst r3, #0x0f
addeq r2, r2, #4
movne r3, r3, lsl #4
tst r3, #0x30
addeq r2, r2, #2
movne r3, r3, lsl #2
tst r3, #0x40
addeq r2, r2, #1
mov r0, r2
#endif
cmp r1, r0 @ Clamp to maxbit
movlo r0, r1
mov pc, lr
>>>id值的计算的补充说明
首先前面n的取值n = (id >> (IDR_BITS*l)) & IDR_MASK;
IDR_MASK的定义#define IDR_MASK ((1 << IDR_BITS)-1)也就是说IDR_MASK=31等于2进制的1,1111b
所以&IDR_MASK只是框定n值落在0~31之间,掩码作用
那么不出意外的话n = (id >> (IDR_BITS*l))
接着
sh = IDR_BITS*l;
id = ((id >> sh) ^ n ^ m) << sh;
带入表达式中
id=((id >> IDR_BITS*l) ^ (id >> (IDR_BITS*l)) ^ m) << IDR_BITS*l;
异或的操作是相同为1,不同为0,结合起来化简得
id = ((1 ^ m) << sh=m<
图C
^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_
已经借用id0走了过场,下面分析下其他情况
[cpp]
static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
{
struct idr_layer *pa[MAX_LEVEL]; //定义父idr_layer数组
int id;
id = idr_get_empty_slot(idp, starting_id, pa); //获取id
if (id >= 0) {
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],(struct idr_layer *)ptr);
//pa[0]->ary[id]=ptr
pa[0]->count++; //idr_layer->count++
idr_mark_full(pa, id); //标记id位图
}
return id;
}
static int idr_get_empty_slot(struct idr *idp, int starting_id,struct idr_layer **pa)