Linux的idr機制(32叉樹)
一.結構體
1.idr結構體
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結構體
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
#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的初始化
#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
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
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
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
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
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鏈表頭
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
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;
p->layer = 0; //指定idr_layer14的層號為0
layers = 1; //layers層數量設為1
}
//layers<6 && id>=2^(layers*5) 看需不需要增加層數 見圖B
while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
layers++;
if (!p->count) {
p->layer++;
continue;
}
if (!(new = get_from_free_list(idp))) {
spin_lock_irqsave(&idp->lock, flags);
for (new = p; p && p != idp->top; new = p) {
p = p->ary[0];
new->ary[0] = NULL;
new->bitmap = new->count = 0;
__move_to_free_list(idp, new);
}
spin_unlock_irqrestore(&idp->lock, flags);
return -1;
}
new->ary[0] = p;
new->count = 1;
new->layer = layers-1;
if (p->bitmap == IDR_FULL)
__set_bit(0, &new->bitmap);
p = new;
}
rcu_assign_pointer(idp->top, p); //根top指向idr_layer14
idp->layers = layers; //設置更新idr->layers層數量
//----------------------------------------------分割線----------------------------------------------
//以上部分主要處理layer相關,以下部分主要處理id相關
v = sub_alloc(idp, &id, pa); //>>>2-->sub_alloc
if (v == IDR_NEED_TO_GROW) //IDR_NEED_TO_GROW=-2需要擴大
goto build_up;
return(v);
}
圖A：
圖B
>>>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
^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_
已經借用id0走了過場,下面分析下其他情況
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)
{
struct idr_layer *p, *new;
int layers, v, id;
unsigned long flags;
id = starting_id;
build_up:
p = idp->top; //獲取根top
layers = idp->layers; //獲取層數量 layers=1
if (unlikely(!p)) { //FALSE
if (!(p = get_from_free_list(idp)))
return -1;
p->layer = 0;
layers = 1;
}
while ((layers < 6) && (id >= (1 << (layers*5)))) { //參考圖B,如果id值超過或等於對應層所能容納的最大數,則進入循環
layers++; //增加層數量
if (!p->count) { //0~31沒使用,直接使用32就屬於這種情況
p->layer++; //由於32需要添加1層的,所以之前的層的層號需要+1
continue; //層數量也需要加1
}
if (!(new = get_from_free_list(idp))) { //空閒鏈表中獲取新的idr_layer
spin_lock_irqsave(&idp->lock, flags); //分配失敗,--空閒idr_layer鏈表缺貨
for (new = p; p && p != idp->top; new = p) { //p指針還原
p = p->ary[0];
new->ary[0] = NULL;
new->bitmap = new->count = 0;
__move_to_free_list(idp, new); //分配更多空閒鏈表
}
spin_unlock_irqrestore(&idp->lock, flags);
return -1;
}
new->ary[0] = p; //新的idr_layer->ary[0]指向舊的idr_layer
new->count = 1; //新的idr_layer計數加1
new->layer = layers-1; //設置新的idr_layer的層號
if (p->bitmap == IDR_FULL) //若舊的(葉子)idr_layer的id全用過了
__set_bit(0, &new->bitmap); //那麼標記下新(父)idr_layer位圖的第0位
p = new; //根top指向新的idr_layer
}
rcu_assign_pointer(idp->top, p); //設置根top
idp->layers = layers; //更新層數量
v = sub_alloc(idp, &id, pa); //獲取id
if (v == IDR_NEED_TO_GROW) //該層id號全用完了,必須擴大idr_layer層數量
goto build_up;
return(v);
}
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; //pa[1]=NULL,l=0
while (1) {
n = (id >> (5*l)) & IDR_MASK; //n做處理 屬於[0,31]
bm = ~p->bitmap; //位圖取反
m = find_next_bit(&bm, IDR_SIZE, n); //查找n開始能用的位
if (m == IDR_SIZE) { //id表滿了
l++; 層數+1
oid = id;
id = (id | ((1 << (5 * l)) - 1)) + 1; //id或上掩碼再+1
if (id >= 1 << (idp->layers * 5)) { //需要添加層
*starting_id = id;
return IDR_NEED_TO_GROW;
}
p = pa[l];
BUG_ON(!p);
sh = 5 * (l + 1);
if (oid >> sh == id >> sh)
continue;
else
goto restart;
}
if (m != n) { //期望id給用但有可用id
sh = 5*l;
id = ((id >> sh) ^ n ^ m) << sh; //id設置為可用id
}
if ((id >= MAX_ID_BIT) || (id < 0))
return IDR_NOMORE_SPACE;
if (l == 0) //一層層循環計算直到到達葉子處l才為0
break;
if (!p->ary[m]) { //葉子m為空
new = get_from_free_list(idp); //從空閒鏈表拿一個idr_layer
if (!new)
return -1;
new->layer = l-1; //設置新鏈表層數
rcu_assign_pointer(p->ary[m], new); //葉子m指向新鏈表
p->count++; //使用計數加1
}
pa[l--] = p; //pa[大]=節點
p = p->ary[m]; //p=節點->葉子m
}
pa[l] = p; //pa[小]=葉子
return id;
}
來個效果圖id=4吧
id=32情況(idr_layer13的位圖1標記錯了)
1024情況
四.查找id
1.idr_find
void *idr_find(struct idr *idp, int id)
{
int n;
struct idr_layer *p;
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 移除
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);
移除全部
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 替換
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
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函數
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); //獲取id,捆綁指針ptr int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id); //起始數值獲取id,捆綁指針ptr int idr_for_each(struct idr *idp,int (*fn)(int id, void *p, void *data), void *data); void *idr_get_next(struct idr *idp, int *nextid); void *idr_replace(struct idr *idp, void *ptr, int id); //替換id捆綁的指針 void idr_remove(struct idr *idp, int id); //移除id void idr_remove_all(struct idr *idp); //移除所有id void idr_destroy(struct idr *idp); //銷毀idr_layer空閒鏈表 void idr_init(struct idr *idp); //初始化idr
2.大致用法
1.idr_init聲明設置idr
2.idr_pre_get分配空閒idr_layer鏈表
3.id_get_new/idr_get_new_above分配id並將id與指針ptr捆綁
4.利用idr_find根據id獲取指針ptr
5.idr_remove/idr_remove_all移除分配的id
6.idr_destroy銷毀空閒idr_layer鏈表
7.idr_replace替換id
