Linuxのidrの構造 - akachochinの日記

Linux Kernel Development（以後「Linux本」)を読んでみて、いまいちイメージが湧かなかったのがidr。
idrはLinux本によれば「mapping a unique identification number (UID) to a pointer」となっている。
どうやらひとつのポインタに一つのIDを割り振って管理するものらしい。

けれど、仕組みが今ひとつ想像できない。そこでソースを読んでみて分かったことをまとめてみたい。

まず、idrを使うにあたり、idr構造体の変数を一つ用意する必要がある。これはちょうどファイルディスクリプタのような役割を果たす。
これをidr_init()で初期化する。
この関数は単にidr構造体を0クリアし、struct idr内のロックを初期化するだけである。

次にidr_pre_get()を呼び出す。これはLinux本によれば、「resize the backing tree」のために呼び出すそうだ。
backing tree?早速ソースを読む。

idr_pre_get()はstruct idr_layer型の変数を確保し、これをidr構造体内のfree listにつなげるだけである。
これを図で表したものが図1である。

図1

図1のとおり、idr構造体のid_freeにidr_layer構造体をつなげていく。このときnextポインタの役割を果たすのがidr_layer構造体のary[0]である。でも、これだけだとbacking treeの正体は良く分からない。

ここまでの2関数を呼び出せば、idr_get_new()コールで、第二引数のpointerに対応したIDを確保できる。
実装の概要をソースで追ってみる。
idr_get_new()が呼ばれると、idr_get_new_above_int() -> idr_get_empty_slot()という関数コールを行う。
実際のIDはidr_get_empty_slot()内で獲得する。
idr_get_empty_slot()では、最初にidr構造体のメンバtopを見に行く。
topに何も繋がっていない場合、idr構造体のid_freeからidr_layer構造体を確保する。そして、一番最初のデータ構造は図2のようになる。
※図2以降はid_freeに繋がっているidr_layer構造体は省略。

図2.

ここで、topからidr_layer構造体を辿った末尾がleaf、辿った途中がnodeである。
leafのaryはIDと対応付けするためのポインタ、nodeのaryはleafとなるidr_layer構造体もしくは子nodeとなるidr_layer構造体を指す。

もし、あるaryを図3のように全部使い切った場合(全部使いきったかどうかはidr_layer内のbitmapがすべて1かどうかで判別する。)、図4のように新たにidr_layerを割り当てる。
そうしてleafもしくはnodeを増やし、IDにひもづけるためのポインタを保存できるようにする。

図3

図4

基本的にidr_get_empty_slot()では、
(1)sub_alloc()でIDの割り付けをする。
(2)sub_alloc()内でIDの割付がこれ以上できない(idr_layer構造体が不足している)場合は、sub_alloc()はIDR_NEED_TO_GROWを返す。
この値が返ってきたら、idr_get_empty_slot()は先頭に戻り、再度idr_layer構造体の割り当て、チェインを作って空きスロットを作り再度sub_alloc()を呼び出す。
ということをしている。

なるほど、これがLinux本でいう「backing tree」か。途中が歯抜けになりやすいID割り当てにはうってつけのデータ構造である。
また勉強になった。