close

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情況的分析。

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 成功运行 的頭像
    成功运行

    成功运行的部落格

    成功运行 發表在 痞客邦 留言(0) 人氣()