^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_^_
已经借用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情况
