linux機制之IDR
一．前言
在linux中有idr，關於idr的用處並不是清楚。查看網上所述知所谓IDR，其实就是和身份证的含义差不多，我们知道，每个人有一个身份证，身份证只是一串数字，从数字，我们就能知道这个人的信息。同样道理，idr的要完成的任务是给要管理的对象分配一个数字，可以通过这个数字找到要管理的对象。類似于為內核任何對象創建一個普通的id，通過該id可以很快的索引到該對象。在該文中將詳細講述linux中idr的具體實現。
二．idr數據結構
在linux中關於idr有兩個很重要的數據結構1. struct idr 2. struct idr_layer，下面具體來看這兩個數據結構
struct idr_layer {
unsigned long bitmap; --標示id在ary中的位置
struct idr_layer *ary[1< --用於保存對象的地址
int count; --當該值為0時，釋放他
int layer; --距離葉子的距離
struct rcu_head rcu_head; --這個不管
};
struct idr {
struct idr_layer *top; --標示使用的idr_layer
struct idr_layer *id_free; --連接沒有使用的idr_layer
int layers; --拒絕幷發
int id_free_cnt; --空閒的idr_layer計數
spinlock_t lock;
};
三．定義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)
通過宏定義定義一個名為name的idr實體。
四．具體使用idr
在開始idr具體使用之前，需要說明幾個宏的意思
在32位機下IDR_BITS為5
#define IDR_SIZE (1 << IDR_BITS) =32即0x20
#define IDR_MASK ((1 << IDR_BITS)-1) =31即0x1F
#define MAX_ID_SHIFT (sizeof(int)*8 - 1) =31
#define MAX_ID_BIT (1U << MAX_ID_SHIFT) =0x100000000
#define MAX_ID_MASK (MAX_ID_BIT - 1) =0xFFFFFFFF
#define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS =7
#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL =14
上面的宏定義中比較難以理解的是MAX_LEVEL爲什麽是7，其實很好理解，由於我們是32位機，其可以使用的id號時0xFFFFFFFF，而我們idr_layer一層最多為0x1F，故最少需要7level才能將一個id號瓜分完成。也許空口在這兒說，可能一層霧水。下面根據具體的示例就好理解很多。
4.1 idr_pre_get
int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
{
while (idp->id_free_cnt < IDR_FREE_MAX) {
struct idr_layer *new;
new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
if (new == NULL)
return (0);
move_to_free_list(idp, new);
}
return 1;
}
上面的重點是move_to_free_list。
move_to_free_list-> __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++;
}
上面的函數很好理解，下圖會很好的闡述上面函數的意思
當idr_pre_get結束時id_free_count=14.其實該函數的本質是開闢idr_layer內存。
4.2 idr_get_new
分配一個新的idr entry，返回值存儲在id中。
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;
}
下面就是按圖索驥，一步一步去分析idr的內幕。
static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
{
struct idr_layer *pa[MAX_LEVEL];
int id;
id = idr_get_empty_slot(idp, starting_id, pa);--獲得一個空位
if (id >= 0) {
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
pa[0]->count++;
idr_mark_full(pa, id);
}
return id;
}
也許單看這些函數會很枯燥，我們來假設一情況，結合具體的內容會好理解很多。在某一驅動中，調用idr_pre_get后第一次調用下面函數。以starting_id為0。
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; --p=NULL
layers = idp->layers; -- layers = 0
if (unlikely(!p)) {
if (!(p = get_from_free_list(idp))) –從上面的id_free上卸下一個idr_layer,第一次使用。
return -1;
p->layer = 0;
layers = 1;
}
//當id為0時，直接跳過下面的while
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); --idp->top = p;
idp->layers = layers; --idp->layers = 1
v = sub_alloc(idp, &id, pa); --這個是個關鍵
if (v == IDR_NEED_TO_GROW)
goto build_up;
return(v);
}
從free_list上獲得一個未使用的idr_layer
static struct idr_layer *get_from_free_list(struct idr *idp)
{
struct idr_layer *p;
if ((p = idp->id_free)) {
idp->id_free = p->ary[0];
idp->id_free_cnt--;
p->ary[0] = NULL;
}
return(p);
}
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; --id = 0；
restart:
p = idp->top; --p應該為第一個可用的idr_layer
l = idp->layers; --l = 1;
pa[l--] = NULL;
while (1) {
n = (id >> (IDR_BITS*l)) & IDR_MASK; --n = 0
bm = ~p->bitmap; --bm = 0xFFFFFFFF
m = find_next_bit(&bm, IDR_SIZE, n); --查找第一個bit為1的位，這裡m = 1
if (m == IDR_SIZE) {
l++;
oid = id;
id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
if (!(p = pa[l])) {
*starting_id = id;
return IDR_NEED_TO_GROW;
}
sh = IDR_BITS * (l + 1);
if (oid >> sh == id >> sh)
continue;
else
goto restart;
}
if (m != n) {
sh = IDR_BITS*l;
id = ((id >> sh) ^ n ^ m) << sh;
}
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] = idr_layer1
return id;
}
在idr_get_new_above_int函數中
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
pa[0]->count++;
idr_mark_full(pa, id);
即*idr_lay1->ary[0] = (struct idr_layer *)ptr , idr_lay1->count = 1;同時將bitmap中對應id的bit位設置為1.
上面主要是針對第一次調用idr_get_new情況的分析。
一．前言
在linux中有idr，關於idr的用處並不是清楚。查看網上所述知所谓IDR，其实就是和身份证的含义差不多，我们知道，每个人有一个身份证，身份证只是一串数字，从数字，我们就能知道这个人的信息。同样道理，idr的要完成的任务是给要管理的对象分配一个数字，可以通过这个数字找到要管理的对象。類似于為內核任何對象創建一個普通的id，通過該id可以很快的索引到該對象。在該文中將詳細講述linux中idr的具體實現。
二．idr數據結構
在linux中關於idr有兩個很重要的數據結構1. struct idr 2. struct idr_layer，下面具體來看這兩個數據結構
struct idr_layer {
unsigned long bitmap; --標示id在ary中的位置
struct idr_layer *ary[1< --用於保存對象的地址
int count; --當該值為0時，釋放他
int layer; --距離葉子的距離
struct rcu_head rcu_head; --這個不管
};
struct idr {
struct idr_layer *top; --標示使用的idr_layer
struct idr_layer *id_free; --連接沒有使用的idr_layer
int layers; --拒絕幷發
int id_free_cnt; --空閒的idr_layer計數
spinlock_t lock;
};
三．定義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)
通過宏定義定義一個名為name的idr實體。
四．具體使用idr
在開始idr具體使用之前，需要說明幾個宏的意思
在32位機下IDR_BITS為5
#define IDR_SIZE (1 << IDR_BITS) =32即0x20
#define IDR_MASK ((1 << IDR_BITS)-1) =31即0x1F
#define MAX_ID_SHIFT (sizeof(int)*8 - 1) =31
#define MAX_ID_BIT (1U << MAX_ID_SHIFT) =0x100000000
#define MAX_ID_MASK (MAX_ID_BIT - 1) =0xFFFFFFFF
#define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS =7
#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL =14
上面的宏定義中比較難以理解的是MAX_LEVEL爲什麽是7，其實很好理解，由於我們是32位機，其可以使用的id號時0xFFFFFFFF，而我們idr_layer一層最多為0x1F，故最少需要7level才能將一個id號瓜分完成。也許空口在這兒說，可能一層霧水。下面根據具體的示例就好理解很多。
4.1 idr_pre_get
int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
{
while (idp->id_free_cnt < IDR_FREE_MAX) {
struct idr_layer *new;
new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
if (new == NULL)
return (0);
move_to_free_list(idp, new);
}
return 1;
}
上面的重點是move_to_free_list。
move_to_free_list-> __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++;
}
上面的函數很好理解，下圖會很好的闡述上面函數的意思
當idr_pre_get結束時id_free_count=14.其實該函數的本質是開闢idr_layer內存。
4.2 idr_get_new
分配一個新的idr entry，返回值存儲在id中。
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;
}
下面就是按圖索驥，一步一步去分析idr的內幕。
static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
{
struct idr_layer *pa[MAX_LEVEL];
int id;
id = idr_get_empty_slot(idp, starting_id, pa);--獲得一個空位
if (id >= 0) {
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
pa[0]->count++;
idr_mark_full(pa, id);
}
return id;
}
也許單看這些函數會很枯燥，我們來假設一情況，結合具體的內容會好理解很多。在某一驅動中，調用idr_pre_get后第一次調用下面函數。以starting_id為0。
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; --p=NULL
layers = idp->layers; -- layers = 0
if (unlikely(!p)) {
if (!(p = get_from_free_list(idp))) –從上面的id_free上卸下一個idr_layer,第一次使用。
return -1;
p->layer = 0;
layers = 1;
}
//當id為0時，直接跳過下面的while
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); --idp->top = p;
idp->layers = layers; --idp->layers = 1
v = sub_alloc(idp, &id, pa); --這個是個關鍵
if (v == IDR_NEED_TO_GROW)
goto build_up;
return(v);
}
從free_list上獲得一個未使用的idr_layer
static struct idr_layer *get_from_free_list(struct idr *idp)
{
struct idr_layer *p;
if ((p = idp->id_free)) {
idp->id_free = p->ary[0];
idp->id_free_cnt--;
p->ary[0] = NULL;
}
return(p);
}
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; --id = 0；
restart:
p = idp->top; --p應該為第一個可用的idr_layer
l = idp->layers; --l = 1;
pa[l--] = NULL;
while (1) {
n = (id >> (IDR_BITS*l)) & IDR_MASK; --n = 0
bm = ~p->bitmap; --bm = 0xFFFFFFFF
m = find_next_bit(&bm, IDR_SIZE, n); --查找第一個bit為1的位，這裡m = 1
if (m == IDR_SIZE) {
l++;
oid = id;
id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
if (!(p = pa[l])) {
*starting_id = id;
return IDR_NEED_TO_GROW;
}
sh = IDR_BITS * (l + 1);
if (oid >> sh == id >> sh)
continue;
else
goto restart;
}
if (m != n) {
sh = IDR_BITS*l;
id = ((id >> sh) ^ n ^ m) << sh;
}
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] = idr_layer1
return id;
}
在idr_get_new_above_int函數中
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
pa[0]->count++;
idr_mark_full(pa, id);
即*idr_lay1->ary[0] = (struct idr_layer *)ptr , idr_lay1->count = 1;同時將bitmap中對應id的bit位設置為1.
上面主要是針對第一次調用idr_get_new情況的分析。
