linux内核IDR机制详解（二）

以你之姓@ 2022-04-04 10:50 846阅读 0赞

上一篇博文讨论了IDR机制的数据表示以及IDR如何寻找到一个ID，本文主要记录下IDR机制的实际应用。  
主要涉及如下：

1. 增加一个IDR；
     2. 查找一个ID对应的IDR；

IDR增加函数主要是增加一个ID到IDR中，主要函数如下：

int idr_get_new(struct idr *idp, void *ptr, int *id);
    int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);

本质上idr\_get\_new和idr\_get\_new\_above差不多，唯一不同的是后者有一个从哪个ID开始获取未使用的ID号而已。  
两者函数原型如下：

int idr_get_new(struct idr *idp, void *ptr, int *id)
    {                
            int rv; 
                    
            rv = idr_get_new_above_int(idp, ptr, 0);
            /* * This is a cheap hack until the IDR code can be fixed to * return proper error values. */
            if (rv < 0)
                    return _idr_rc_to_errno(rv);
            *id = rv;
            return 0;
    }
    
    int idr_get_new(struct idr *idp, void *ptr, int *id)
    {                
            int rv; 
                    
            rv = idr_get_new_above_int(idp, ptr, 0);
            /* * This is a cheap hack until the IDR code can be fixed to * return proper error values. */
            if (rv < 0)
                    return _idr_rc_to_errno(rv);
            *id = rv;
            return 0;
    }
    
    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) { 
                    /* * Successfully found an empty slot. Install the user * pointer and mark the slot full. */
                    rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],
                                    (struct idr_layer *)ptr);
                    pa[0]->count++;
                    idr_mark_full(pa, id);
            }
    
            return id;
    }

本质上调用的都是idr\_get\_empty\_slot，idr\_get\_empty\_slot函数是分配个大于starting\_id的数字作为ptr的ID。如果分配成功，id>=0,将叶子节点id对应的ary数组的元素赋值为 ptr。同时将叶子层的count++，表示又分配出去一个。将叶子层的位图bitmap对应槽位置1的工作是idr\_mark\_full完成。如果叶子层全满了，则通知叶子层的父亲对应槽位置1，依次传递。  
idr\_get\_empty\_slot这个部分，表示如果ｉｄｒ的３２叉树连个根都没有，我需要分配一个idr\_layer来当根。如果alloc\_layer失败，表示预备役空了，惨了，只能返回失败，告诉调用者，预备役没了，请填充预备役。一般是可以分配的。

这个循环体的含义是，用户这个搞得这个starting_id太大了，或者低的id分配出去了，只能给用户分配个大的id。如果这个id大于了当前层数所能管理的最高ID，我们需要加一层了。
    
    以上面的示意图为例，我们当前有两层结构，最多能管理32*32=1K个，我们能分配的最大id就是1023，如果用户要求我们分配大于等于1500的id，那么我们目前的两层结构是无法满足需要的，所以我们需要加一层。首先将layer++，表示我们的32叉树升级了，多了一层，从预备役分配出一个idr_layer，让新分配的new当根。p指针指向根。
    
    如果分配的id不够大，不需要分层，那么这个while就不执行了，直接跳到sub_alloc函数。函数原型如下：

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;
            layers = idp->layers;
            if (unlikely(!p)) { 
                    if (!(p = get_from_free_list(idp)))
                            return -1;
                    p->layer = 0;
                    layers = 1;
            }
            /* * Add a new layer to the top of the tree if the requested * id is larger than the currently allocated space. */     
            while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) { 
                    layers++;
                    if (!p->count) { 
                            /* special case: if the tree is currently empty, * then we grow the tree by moving the top node * upwards. */
                            p->layer++;
                            continue;
                    }       
                    if (!(new = get_from_free_list(idp))) { 
                            /* * The allocation failed. If we built part of * the structure tear it down. */ 
                            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->layers = layers;
            v = sub_alloc(idp, &id, pa);
            if (v == IDR_NEED_TO_GROW)
                    goto build_up;
            return (v);
     }

sub\_alloc函数。

还是以示意图为例讲述。我们是两层的结构，p是32叉树的根节点top
    
       如果用户要分配大于等于66的id，66=2*32+2，首先找到了我们要找的66是位于top->ary[2],我们需要确认 根的ary[2]这个分支是否还能分配。如果p->ary[2]对应的idr_layer 所有的槽位都分配出去了，客满，新的顾客无法入住，我们就不必白费劲去ary[2]这个分支去分配了。判断的办法就是m = find_next_bit(&bm, IDR_SIZE, n);这个函数很可爱，就是说我要找大于2 的所有分支，寻找第一个没有客满的分支。通过top层或者中间层bitmap的含义，如果某个分支全部客满，则在对应bitmap位置1 ，表示，不要去这个分支找了，找也白找。
    
      然后一层层往下找，知道找到叶子层，在叶子层查找大于等于2的id。
    
      各种情况我就不分析了，大家可以自己尝试分配一下
    
     1  从0开始，分配，累加到33，差不多就可以理解idr_get_new这种情况的分配流程
    
     2 不按常理出牌，乱分配，假如我第一个就要分配 大于37的，第二次就要分配大于1500的，之类的

### 总结： ###

IDR分配未使用ID过程中主要是先根据idr->layers判断是否增加根节点，如果需要增加根节点，则在sub\_alloc函数之前增加根idr\_layer根节点。然后再增加叶子节点，把各个叶子节点增加到直到能够表示一个ID为止。并且sub\_alloc中叶子节点函数传入了一个pa，就是要返回从叶子节点开始直到根节点的地址索引。  
查找IDR就不用赘述了，已经在上一篇博客里面介绍过。