這幾天在看Linux內核的IPC命名空間時候看到關於IDR的一些管理性質的東西，剛開始看有些迷茫，深入看下去豁然開朗的感覺，把一些心得輸出共勉。 我們來看一下什麼是IDR？IDR的作用是什麼呢？ 先來看下IDR的作用：IDR主要實現ID與數據結構的綁定。剛開始看的時候感覺到有點懵，什麼叫“ID與數據 ...
這幾天在看Linux內核的IPC命名空間時候看到關於IDR的一些管理性質的東西，剛開始看有些迷茫，深入看下去豁然開朗的感覺，把一些心得輸出共勉。
我們來看一下什麼是IDR？IDR的作用是什麼呢？
先來看下IDR的作用：IDR主要實現ID與數據結構的綁定。剛開始看的時候感覺到有點懵，什麼叫“ID與數據結構的綁定”？舉一個例子大家就會明白了：在IPC通信的時候先要動態獲取一個key值或者使用現有的key值進行通信，那麼系統怎麼知道這個key值是否使用了呢？這個就需要IDR來進行判斷了。以上就是IDR的一些淺顯的概念，IDR本質上就是通過對於ID一些有效的管理進而管理和這些ID有關的數據結構----不限於IPC通信的key值。
IDR怎麼對於數據ID管理呢？傳統上我們對於未使用的ID進行管理的時候可以使用點陣圖進行管理，也可以使用數組進行管理，也可以使用鏈表進行ID管理，三個個各有優缺點：
- 使用點陣圖進行管理的時候優點是使用空間少，但是對於點陣圖對應的數據結構支持不太友好。
- 使用數組進行管理的時候定址快速，但是只能管理比較少量的ID數目。
- 使用鏈表進行管理的時候雖然可以支持大量的數據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例如數據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數組中的值不為空代表相應位有效的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問題：
- IDR的初始化
- IDR的增加
- 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);
}
