>>>get_from_free_list 从idr空闲idr_layer链表中获取第一个idr_layer
static struct idr_layer *get_from_free_list(struct idr *idp) { struct idr_layer *p; //定义一个idr_layer指针 unsigned long flags; spin_lock_irqsave(&idp->lock, flags); if ((p = idp->id_free)) { //根free获取一个空闲idr_layer idp->id_free = p->ary[0]; //idr空闲链表指针指向第二个idr_layer idp->id_free_cnt--; //idr的空闲idr_layer个数减1(14-1) p->ary[0] = NULL; //断开第一个idr_layer和第二个idr_layer的联系 } spin_unlock_irqrestore(&idp->lock, flags); return(p); }这里先穿插一下32进制的计算,上面图B中2^0,2^5,2^10,2^15,2^20,2^25可以(32=2^5)理解成32^0,32^1,32^2,32^3,32^3,32^4,32^5
那么用32进制表达一个十进制数id可以套用一下公式
a的值属于[0,31]
an的值如何获得id/(32^n)即可,等同于id/(2^5^n)等同于id/((1<<5)^n)
an-1的值如何获得id>>(5*(n-1))即可
>>>sub_alloc
static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa) { int n, m, sh; struct idr_layer *p, *new; int l, id, oid; unsigned long bm; id = *starting_id; restart: p = idp->top; //根top l = idp->layers; //l=1 pa[l--] = NULL; //p[1]=NULL;l=0 while (1) { n = (id >> (IDR_BITS*l)) & IDR_MASK; //计算对应的n值,属于[0,31] bm = ~p->bitmap; //取反位图 m = find_next_bit(&bm, IDR_SIZE, 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
#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
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找到合适的跳转
.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<<sh
图C
