linux内核IDR机制详解（一）

逃离我推掉我的手 2022-04-04 08:46 630阅读 0赞

这几天在看Linux内核的IPC命名空间时候看到关于IDR的一些管理性质的东西，刚开始看有些迷茫，深入看下去豁然开朗的感觉，把一些心得输出共勉。  
我们来看一下什么是IDR？IDR的做作用是什么呢？  
先来看下IDR的作用：IDR主要实现ID与数据结构的绑定。刚开始看的时候感觉到有点懵，什么叫“ID与数据结构的绑定”？举一个例子大家就会明白了：在IPC通信的时候先要动态获取一个key值或者使用现有的key值进行通信，那么系统怎么知道这个key值是否使用了呢？这个就需要IDR来进行判断了。以上就是IDR的一些浅显的概念，IDR本质上就是通过对于ID一些有效的管理进而管理和这些ID有关的数据结构----不限于IPC通信的key值。  
IDR怎么对于数据ID管理呢？传统上我们对于未使用的ID进行管理的时候可以使用位图进行管理，也可以使用数组进行管理，也可以使用链表进行ID管理，三个个各有优缺点：

1.  使用位图进行管理的时候优点是使用空间少，但是对于位图对应的数据结构支持不太友好。
2.  使用数组进行管理的时候寻址快速，但是只能管理比较少量的ID数目。
3.  使用链表进行管理的时候虽然可以支持大量的数据ID，但是通过链表的指针寻址比较慢。  
    所以引入了以上三者的优点进行IDR管理。

## IDR管理的核心 ##

IDR把每一个ID分级数据进行管理，每一级维护着ID的5位数据，这样就可以把IDR分为7级进行管理（5\*7=35，维护的数据大于32位），如下所示：  
31 30 | 29 28 27 26 25 | 24 23 22 21 20 | 19 18 17 16 15 | 14 13 12 11 10 | 9 8 7 6 5 | 4 3 2 1 0  
其中第一级维护着30-31位的数据，可以根据30-31位的数据找到下一级IDR的指针；第二级维护着25-29位数据，根据第二级数组下标索引可以寻址到第三级；…以此类推，可以寻址到第七级；寻找到第七级IDR；  
例如数据ID为0B 10 11111 10011 00111 11001 100001 00001，寻址如下：

1. 第一级寻址 ary1[0b10]得到第二级地址ary2[]
     2. ary3 = ary2[0b11111]
     3. ary4 = ary3[ob10011]
     4. ary5 = ary4[0b00111]
     5. ary6 = ary5[0b11001]
     6. ary7 = ary6[0b100001]
     7. ary8 = ary7[0b00001]

气质ary8即为要寻址到的ID对应的IDR指针。  
如下图：

![IDR结构][IDR]  
上图中每一个分级中的IDR数组中的值不为空代表相应位有效的ID位，但是使用数组下标标示有效的ID位还是有点慢----需要通过数组下标以及数组内容判断有效的ID位，所以对于每一个IDR引入了有效的ID位图来表示，每一个位图为32位刚好给出了相应的有效的ID位。方便查找。  
上图中只是使用了IDR的32个数组表示，并没有给出IDR的位图以及层数标志，下面给出相应的数据结构：  
IDR 数据结构：

struct idr_layer { 
    	//位图，ary数组结构哪个有效
            unsigned long            bitmap; /* A zero bit means "space here" */
            //IDR数组
            struct idr_layer __rcu  *ary[1<<IDR_BITS];
            标示
            int                      count;  /* When zero, we can release it */
            //层数，代表所在的ID位
            int                      layer;  /* distance from leaf */
            struct rcu_head          rcu_head;
    };
    
    struct idr { 
    	//IDR层数头，实际上就是32叉树
            struct idr_layer __rcu *top;
    	//尚未使用的IDR
            struct idr_layer *id_free;
            //层数
            int               layers; /* only valid without concurrent changes */
            //id_free未用的个数；
            int               id_free_cnt;
            spinlock_t        lock;
    };

下面讨论一下IDR的初始化以及增删改查ID问题：

1.  IDR的初始化
2.  IDR的增加
3.  IDR的查找

### IDR的初始化： ###

IDR的初始化相对来说比较简单，使用IDR\_INIT可以初始化一个IDR，原型如下：

#define IDR_INIT(name) \ { \ .top = NULL, \ .id_free = NULL, \ .layers = 0, \ .id_free_cnt = 0, \ .lock = __SPIN_LOCK_UNLOCKED(name.lock), \ }

可以看到IDR只是把各个数据值为零，原子锁初始化下。

### IDR的增加： ###

IDR增加比较复杂，在C中编程大部分情况可以分为如下两点讨论：

1.idr.top为NULL的情况；
     2.idr.top不为NULL的情况；
     以上考虑问题也是可以的，但是没有考虑到如下问题：
     每一个idr_layer结构体有一个layer标示,我们每每增加一层，就要遍历整个idr的32叉树。无形中增加了系统负担。

idr设计者在考虑问题时候恰恰相反，没增加一个idr\_layer层，就把要增加的idr\_layer->ary\[0\]指向旧的idr\_layer树的根，把要增加idr\_layer->layer赋予旧的根部的idr\_layer->layer + 1值，这样就不会考虑到idr->top为NULL的情况了。ps:只需要判断在增加第一个idr\_layer时候判断一下，并且把idr\_layer->layer值赋为0.

### IDR的查找： ###

在查找IDR时侯会先查找IDR根节点，然后根据ID位所在的层的值遍历IDR树，如果查找到某一段树为NULL，则会返回NULL。  
以下是IDR查找的过程：

void *idr_find(struct idr *idp, int id)                         
    {       
            int n;
            struct idr_layer *p;                                    
            //获取根IDR
            p = rcu_dereference_raw(idp->top);
            if (!p)
                    return NULL;
            /**
    		根据IDR的层数获取要遍历的个数；
    	**/
            n = (p->layer+1) * IDR_BITS;
    
            /* 去除我们不需要查找的位数. */
            id &= MAX_ID_MASK;
    	/***如果ID值大于n, 1<<n为根据层数换算过来的ID的最大值**/
            if (id >= (1 << n))
                    return NULL;
            BUG_ON(n == 0);
    	/***
    		遍历顺序：28---->0,每次减少5位，可以遍历完全IDR的32叉树
    	***/
            while (n > 0 && p) {
                    n -= IDR_BITS;
                    BUG_ON(n != p->layer*IDR_BITS);
                    p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
            }
            return((void *)p);
    }

参考文献：  
[https://blog.csdn.net/bingqingsuimeng/article/details/8258783][https_blog.csdn.net_bingqingsuimeng_article_details_8258783]  
[https://www.cnblogs.com/zero-jh/p/5184836.html][https_www.cnblogs.com_zero-jh_p_5184836.html]

[IDR]: /images/20220404/f079a011659848f1acdf5d61fd8d2147.png
[https_blog.csdn.net_bingqingsuimeng_article_details_8258783]: https://blog.csdn.net/bingqingsuimeng/article/details/8258783
[https_www.cnblogs.com_zero-jh_p_5184836.html]: https://www.cnblogs.com/zero-jh/p/5184836.html