radix-tree(基数ツリー)

Rev.2を表示中。最新版はこちら。

radix-treeは基数ツリーというそうで、アドレス空間内のページを効率よく検索するためのツリーである。構造はext2/ext3のような間接ブロックの考え方で、その階層を動的に変化させるということだが、ノードの追加とかノードのtagメンバーの取り扱いなどよく考えられている。

#ifdef __KERNEL__
#define RADIX_TREE_MAP_SHIFT    (CONFIG_BASE_SMALL ? 4 : 6)
#else
#define RADIX_TREE_MAP_SHIFT    3       /* For more stressful testing */
#endif
#define RADIX_TREE_MAP_SIZE     (1UL << RADIX_TREE_MAP_SHIFT)

struct radix_tree_root {
       unsigned int            height;
       gfp_t                   gfp_mask;
       struct radix_tree_node  *rnode;
};

struct radix_tree_node {
       unsigned int    height;         /* Height from the bottom */
       unsigned int    count;
       struct rcu_head rcu_head;
       void            *slots[RADIX_TREE_MAP_SIZE];
       unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

radix-treeはrootをトップとするradix_tree_node構造体をノードとして階層構造を作成する。heightはそのノードの階層レベルを表し、最下位位階層を1として、上位階層に従って1づつ大きくなっていく。rootのheight値が一番大きい。*slotsは実データないし下位ノードが設定される。1ノードあたりのスロット数はRADIX_TREE_MAP_SIZEで通常は64となる。

ノードツリーはキーとなる32ビットインデックの下位から6ビットずつを割り当てる。（最上位は2ビット)従って最大階層は6階層となり、スロット数との関係は以下のようになる。ただし6階層ではインデックスは2ビットとなるため、すべてを使うわけでない。

階層スロット数
0 1 1
1 64 64
2 64*64 4096
3 64*64*64 262144
4 64*64*64*64　16252928
5 64*64*64*64*64 1073741823
6 64*64*64*64*64*64 66571993088

下記は上記の内容を検証するためのものである。rootを静的変数radix_treeとして定義し、radix_tree_insert関数でmy_objectを登録し、このときの階層値を確認するものである。インデックスが0のときrootの*rnodeに繋がれている。そしてインデックスが1から63までは階層1、64から4095は階層2となっていくことが確認できる。

#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/syscalls.h>
#include <linux/radix-tree.h>

MODULE_LICENSE("GPL");

struct radix_tree_root radix_tree = RADIX_TREE_INIT(GFP_ATOMIC|__GFP_NOWARN);
struct my_object {
    char data[10];
};
struct my_object *myobj;

static int mod_init(void)
{
   int error, i;
   struct my_object    *p;

   error = radix_tree_preload(__GFP_NOWARN);
   if (!error) {
       for (i = 0; i < 4097; i++) {
           myobj = kmalloc(sizeof(struct my_object), GFP_KERNEL);
           sprintf(myobj->data, "%d", i);
           error = radix_tree_insert(&radix_tree, i, myobj);
           printk("insert:%d:%s\n", radix_tree.height, myobj->data);
       }
       radix_tree_preload_end();
       if (!error) {
           for (i = 0; i < 4097; i++) {
               p = radix_tree_lookup(&radix_tree, i);
               printk("look:%s\n", p->data);
           }
       }
   }
   return error;
}

static void mod_exit(void)
{
   int i;
   struct my_object    *p;

   for (i = 0; i < 4097; i++) {
       p = radix_tree_lookup(&radix_tree, i);
       kfree(p);
   }
}

module_init(mod_init);
module_exit(mod_exit);

[root@localhost test]# dmesg
insert:0:0
insert:1:1
insert:1:2
 :
 :
insert:1:62
insert:1:63
insert:2:64
insert:2:65
 :
 :
insert:2:4094
insert:2:4095
insert:3:4096
look:0
look:1
 :
 :
look:4095
look:4096

radix_tree_insert関数は引数のインデックスでrootから対応するノードを辿ってスロットは見つけるわけだが、見つからなければradix_tree_extend関数で新規ノードを割り当てる。このノードはroot配下に割り付ける。そして以下のノードのheightを1インクリメントする。そしてradix_tree_insert関数へ戻ると、目的とするデータのインデックスに応じた必要とする階層ノードを作成しながら、そのツリー下に該当するノードを作成する。

radix_tree_node構造体にtagsメンバーは、汚れているページ検索の効率化を図っている。汚れているページを有しているツリーノードのtagsメンバーにその旨の情報を設定することで、そうでないノードは検索する必要がなくなる。

補足
radix_tree_preload関数はカーネルプリエンプションを禁止し、64GBまでの登録処理を保障するものらしい。