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
