內(nèi)核ida和idr機制分析（盤符分配機制）

ida和idr的機制在我個人看來，是內(nèi)核管理整數(shù)資源的一種方法。在內(nèi)核中，許多地方都用到了該結(jié)構(gòu)（例如class的id，disk的id），更直觀的說，硬盤的sda到sdz的自動排序也是依靠該機制。使用該結(jié)構(gòu)的好處是可以管理大量的整數(shù)資源并且檢索的時候非常高效。但是，使用該機制的另一個弊端就是：同一個槽位的硬盤進行拔插的時候，如果之前申請的整數(shù)資源沒有來得及釋放，那么可能會產(chǎn)生盤符漂移現(xiàn)象。這給上層軟件對盤符的管理帶來了困難。在本篇博文中，對具體如何解決盤符漂移不做說明。

在根據(jù)代碼說明之前，我想先介紹一下該機制對整型數(shù)的靈活應(yīng)用。int數(shù)值一般來說，為4個字節(jié)。那么將一個int數(shù)分為4部分的結(jié)果就是每部分8bit。在idr的機制中，采用樹來管理資源，int數(shù)值的一個字節(jié)，被抽象成了樹中的一層。即：對某個int值從又向左數(shù)，分別是第一層、第二層、第三層、第四層。第一層必須要有，第一層一般是樹葉層。該idr樹的生長方式也是從樹葉開始，隨著不斷的生長，最開始，樹根就是樹葉，到最后，樹根處于第四層，樹葉還是第一層。特別注意說明的是，idr還有一個第0層的概念。在第0層上，可以比喻成樹葉上水珠。
之前的文字描述可能比較抽象，而且也可能不太準(zhǔn)確。下面用一個圖來表示這種關(guān)系。

假設(shè)我們現(xiàn)在有個a=0x0001，那么a在圖中對應(yīng)第一層中的１。如果有個b=0x0011，那么就必須從第二層的１上生長出一個和第一層一樣的結(jié)構(gòu)，再在這上面找到１.如圖所示：

當(dāng)然，如果該樹管理的最大資源，還沒有涉及到第三層，即最大的數(shù)第三個字節(jié)都是0，那么其實是沒有必要維護第三層的。
此外，該圖只是形象的說明了idr的思想，但與實際的代碼并不完全一樣，具體細節(jié)還需要接下來慢慢結(jié)合代碼分析。在分析代碼之前，再介紹一下常用運算符抑或。請觀察下面的運算式：((m >> 8) & (0xF) ^ (m >> 8) ^ (0x5)) << 8 該運算的作用是將m的第二個字節(jié)置為5，第三個第四個字節(jié)不變，第一個字節(jié)清零。

下面開始結(jié)合代碼分析，先分別給出ida和idr的結(jié)構(gòu)說明：

168 struct ida { 169 struct idr idr; 170 struct ida_bitmap *free_bitmap; 171 };163 struct ida_bitmap { 164 long nr_busy; 165 unsigned long bitmap[IDA_BITMAP_LONGS]; 166 };

idr代表著上面介紹的那一棵樹，因此可見，ida只是對這棵樹的封裝，在idr樹的基礎(chǔ)上，統(tǒng)一了管理辦法。

42 struct idr { 43 struct idr_layer __rcu *hint; /* the last layer allocated from */44 struct idr_layer __rcu *top;45 int layers; /* only valid w/o concurrent changes */46 int cur; /* current pos for cyclic allocation */47 spinlock_t lock;48 int id_free_cnt;49 struct idr_layer *id_free;50 };30 struct idr_layer {31 int prefix; /* the ID prefix of this idr_layer */32 int layer; /* distance from leaf */33 struct idr_layer __rcu *ary[1<<IDR_BITS];34 int count; /* When zero, we can release it */35 union {36 /* A zero bit means "space here" */37 DECLARE_BITMAP(bitmap, IDR_SIZE);38 struct rcu_head rcu_head;39 };40 };

idr代表圖中的那棵樹，idr_layer代表著圖上的每個圓球，而其中的ary數(shù)組代表著每個圓球下的箭頭，bitmap位圖用來記錄該位置下的子layer是否還有空位，如果沒有將置1.
獲取idr資源主要由兩個api來管理。ida_pre_get和ida_get_new_above。前者負(fù)責(zé)按照該樹可承載的最多l(xiāng)ayer數(shù)量申請layer資源，并存放到資源池中。后者可以指定從某個id開始，尋找下一個未被使用的id。

896 int ida_pre_get(struct ida *ida, gfp_t gfp_mask) 897 {898 /* allocate idr_layers */899 if (!__idr_pre_get(&ida->idr, gfp_mask))900 return 0;901 902 /* allocate free_bitmap */903 if (!ida->free_bitmap) {904 struct ida_bitmap *bitmap;905 906 bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask);907 if (!bitmap)908 return 0;909 910 free_bitmap(ida, bitmap);911 }912 913 return 1;914 }192 static int __idr_pre_get(struct idr *idp, gfp_t gfp_mask) 193 {194 while (idp->id_free_cnt < MAX_IDR_FREE) {195 struct idr_layer *new;196 new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);197 if (new == NULL)198 return (0);199 move_to_free_list(idp, new);200 }201 return 1;202 }160 static void move_to_free_list(struct idr *idp, struct idr_layer *p) 161 {162 unsigned long flags;163 164 /*165 * Depends on the return element being zeroed.166 */167 spin_lock_irqsave(&idp->lock, flags);168 __move_to_free_list(idp, p);169 spin_unlock_irqrestore(&idp->lock, flags);170 }153 static void __move_to_free_list(struct idr *idp, struct idr_layer *p) 154 {155 p->ary[0] = idp->id_free;156 idp->id_free = p;157 idp->id_free_cnt++;158 }868 static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap) 869 { 870 unsigned long flags;871 872 if (!ida->free_bitmap) {873 spin_lock_irqsave(&ida->idr.lock, flags);874 if (!ida->free_bitmap) {875 ida->free_bitmap = bitmap;876 bitmap = NULL;877 } 878 spin_unlock_irqrestore(&ida->idr.lock, flags);879 }880 881 kfree(bitmap);882 }

899行調(diào)用__idr_pre_get分配layer。在該函數(shù)內(nèi)，分配MAX_IDR_FREE個layer，之后使用move_to_free_list函數(shù)進行保存。153行可以看出，所有的未使用layer都通過idr里的id_free連接起來，layer之間通過ary[0]連接。這樣，創(chuàng)建的資源，在之后需要使用的時候，直接取就可以了，可以節(jié)省運行時間，提高性能。
ida內(nèi)還有個free_bitmap域，由于該域的操作涉及到競爭，因此，放到自旋鎖中處理。881行的free是因為，防止某個線程申請好了資源，但是有一個線程比他還快，已經(jīng)進入了874行。那么等之后他獲取到鎖后，直接不需要進入if分支，釋放之前申請的資源即可。

932 int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)933 {934 struct idr_layer *pa[MAX_IDR_LEVEL + 1];935 struct ida_bitmap *bitmap;936 unsigned long flags;937 int idr_id = starting_id / IDA_BITMAP_BITS;938 int offset = starting_id % IDA_BITMAP_BITS;939 int t, id;940 941 restart:942 /* get vacant slot */943 t = idr_get_empty_slot(&ida->idr, idr_id, pa, 0, &ida->idr);944 if (t < 0)945 return t == -ENOMEM ? -EAGAIN : t;946 947 if (t * IDA_BITMAP_BITS >= MAX_IDR_BIT)948 return -ENOSPC;949 950 if (t != idr_id)951 offset = 0;952 idr_id = t;953 954 /* if bitmap isn't there, create a new one */955 bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK];956 if (!bitmap) {957 spin_lock_irqsave(&ida->idr.lock, flags);958 bitmap = ida->free_bitmap;959 ida->free_bitmap = NULL;960 spin_unlock_irqrestore(&ida->idr.lock, flags);961 962 if (!bitmap)963 return -EAGAIN;964 965 memset(bitmap, 0, sizeof(struct ida_bitmap));966 rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK],967 (void *)bitmap);968 pa[0]->count++;969 }970 971 /* lookup for empty slot */972 t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset);973 if (t == IDA_BITMAP_BITS) { 974 /* no empty slot after offset, continue to the next chunk */975 idr_id++;976 offset = 0;977 goto restart;978 }979 980 id = idr_id * IDA_BITMAP_BITS + t;981 if (id >= MAX_IDR_BIT)982 return -ENOSPC;983 984 __set_bit(t, bitmap->bitmap);985 if (++bitmap->nr_busy == IDA_BITMAP_BITS)986 idr_mark_full(pa, idr_id);987 988 *p_id = id;989 990 /* Each leaf node can handle nearly a thousand slots and the991 * whole idea of ida is to have small memory foot print.992 * Throw away extra resources one by one after each successful993 * allocation.994 */995 if (ida->idr.id_free_cnt || ida->free_bitmap) {996 struct idr_layer *p = get_from_free_list(&ida->idr);997 if (p)998 kmem_cache_free(idr_layer_cache, p);999 } 1000 1001 return 0; 1002 }289 static int idr_get_empty_slot(struct idr *idp, int starting_id, 290 struct idr_layer **pa, gfp_t gfp_mask,291 struct idr *layer_idr)292 {293 struct idr_layer *p, *new;294 int layers, v, id;295 unsigned long flags;296 297 id = starting_id;298 build_up:299 p = idp->top;300 layers = idp->layers;301 if (unlikely(!p)) {302 if (!(p = idr_layer_alloc(gfp_mask, layer_idr)))303 return -ENOMEM;304 p->layer = 0;305 layers = 1;306 }307 /*308 * Add a new layer to the top of the tree if the requested309 * id is larger than the currently allocated space.310 */311 while (id > idr_max(layers)) {312 layers++; 313 if (!p->count) {314 /* special case: if the tree is currently empty,315 * then we grow the tree by moving the top node316 * upwards.317 */318 p->layer++;319 WARN_ON_ONCE(p->prefix);320 continue;321 }322 if (!(new = idr_layer_alloc(gfp_mask, layer_idr))) {323 /*324 * The allocation failed. If we built part of325 * the structure tear it down.326 */327 spin_lock_irqsave(&idp->lock, flags);328 for (new = p; p && p != idp->top; new = p) {329 p = p->ary[0];330 new->ary[0] = NULL;331 new->count = 0;332 bitmap_clear(new->bitmap, 0, IDR_SIZE);333 __move_to_free_list(idp, new);334 }335 spin_unlock_irqrestore(&idp->lock, flags);336 return -ENOMEM;337 }338 new->ary[0] = p;339 new->count = 1;340 new->layer = layers-1;341 new->prefix = id & idr_layer_prefix_mask(new->layer);342 if (bitmap_full(p->bitmap, IDR_SIZE))343 __set_bit(0, new->bitmap);344 p = new;345 }346 rcu_assign_pointer(idp->top, p);347 idp->layers = layers;348 v = sub_alloc(idp, &id, pa, gfp_mask, layer_idr); 349 if (v == -EAGAIN)350 goto build_up;351 return(v);352 }220 static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa,221 gfp_t gfp_mask, struct idr *layer_idr)222 {223 int n, m, sh;224 struct idr_layer *p, *new;225 int l, id, oid;226 227 id = *starting_id;228 restart:229 p = idp->top;230 l = idp->layers;231 pa[l--] = NULL;232 while (1) {233 /*234 * We run around this while until we reach the leaf node...235 */236 n = (id >> (IDR_BITS*l)) & IDR_MASK;237 m = find_next_zero_bit(p->bitmap, IDR_SIZE, n);238 if (m == IDR_SIZE) {239 /* no space available go back to previous layer. */240 l++;241 oid = id;242 id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;243 244 /* if already at the top layer, we need to grow */245 if (id > idr_max(idp->layers)) {246 *starting_id = id;247 return -EAGAIN;248 }249 p = pa[l];250 BUG_ON(!p);251 252 /* If we need to go up one layer, continue the253 * loop; otherwise, restart from the top.254 */255 sh = IDR_BITS * (l + 1);256 if (oid >> sh == id >> sh)257 continue;258 else259 goto restart;260 } 261 if (m != n) {262 sh = IDR_BITS*l;263 id = ((id >> sh) ^ n ^ m) << sh;264 }265 if ((id >= MAX_IDR_BIT) || (id < 0))266 return -ENOSPC;267 if (l == 0)268 break;269 /*270 * Create the layer below if it is missing.271 */272 if (!p->ary[m]) {273 new = idr_layer_alloc(gfp_mask, layer_idr);274 if (!new)275 return -ENOMEM;276 new->layer = l-1;277 new->prefix = id & idr_layer_prefix_mask(new->layer);278 rcu_assign_pointer(p->ary[m], new);279 p->count++;280 }281 pa[l--] = p;282 p = p->ary[m];283 }284 285 pa[l] = p;286 return id;287 }

由于代碼較長。為了方便敘述，假設(shè)當(dāng)前idr樹中沒有被使用的id。現(xiàn)在調(diào)用ida_get_new_above從0開始找下一個可用的id。由于我們給出了假設(shè)，因此可以預(yù)期到得到的結(jié)果是0.我們帶著這樣的假設(shè)去分析代碼。
943行進入idr_get_empty_slot。301行由于是第一次申請id，因此將進入該分支，分配一個top，即根節(jié)點。此時，304行看出根節(jié)點層數(shù)為第0層。305行l(wèi)ayers表示總層數(shù)，為1層。由于是從0開始分配，因此311行循環(huán)不進入，直接跳過。346行通過rcu方式配置了top域。348行開始真正分配。
該函數(shù)工作開始，保存了幾個量，如227~230所示。考慮到我們從0開始，則id=0，p為剛剛分配的根節(jié)點，l=1。232行的循環(huán)是為了使l>1時，能不斷遍歷到第0層。237行得到m=0.if分支顯然不會進入，跳過。由于231行l(wèi)--，所以267行的時候，跳出循環(huán)。285行保存了根節(jié)點，之后返回0.
回到943行，t取到0.pa[0]內(nèi)保存的一定是葉子節(jié)點的地址。我們這里因為只有1層，根節(jié)點就是葉子節(jié)點。955行顯然取到一個NULL，那么將ida中的free_bitmap轉(zhuǎn)交給它，并在966行轉(zhuǎn)交給根節(jié)點的ary[0]。972行檢測當(dāng)前層數(shù)是否還有剩余空位，這里需要說明的是，一般情況下，一個節(jié)點（layer）管理8*128個id，這種管理就是直接通過數(shù)組進行管理的。這個數(shù)組就是ida申請的數(shù)組，在該函數(shù)內(nèi)通過強轉(zhuǎn)保存到了ary[0]內(nèi)。那么此時，肯定返回0. 980行id=0.984行配置相應(yīng)位為1. 985~986行判斷該節(jié)點是否已滿,如果之后沒有空閑了，將設(shè)置為該位置已滿。這是通過根節(jié)點下的bitmap去設(shè)置的。988行將id值賦給p_id，之后返回。
在這里，將對之前的假設(shè)做出一個糾正。我們開始假設(shè)是從0開始尋找，是假設(shè)ida_get_new_above里的參數(shù)staring_id是從哪個數(shù)開始查找的意思。實際上，通過走讀分析，我們可以看到，該starting_id其實代表某個layer。

通過這樣的分析，相信對于整個流程已經(jīng)有了簡單的認(rèn)知。代碼其他部分主要涉及到stating_id指定的layer不存在，分配新的layer。或者starting_id超過了當(dāng)前層數(shù)所能提供的最大id，則idr必須開始生長的過程。對于這些部分，相信經(jīng)過前面的分析，這些都已經(jīng)變的很簡單，本文不再詳細說明。留給讀者自行分析。

轉(zhuǎn)載于:https://www.cnblogs.com/wyk930511/p/7327778.html

總結(jié)

以上是生活随笔為你收集整理的ida和idr机制分析（盘符分配机制）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。