radix-tree(基数ツリー)

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

radix treeはradix_tree_rootをヘッドとし、各radix_tree_nodeのslot[]にradix_tree_nodeをリンクすることで、階層的にradix_tree_nodeを管理します。ファイルシステムのディレクトリとファイルみたいな物です。新規階層の追加はrootに追加します。従って全てのスロットは1段階層が深くなりますが、heightは下位からの階層でrootのhightをインクリメントするだけです。

slot[]にはradix_tree_nodeならradix_tree_nodeのみ、管理オブジェクトなら管理オブジェクトのみとなります。なお、linuxでは、pageに特化した形態での実装となっています。

RADIX_TREE_MAP_SHIFTは1ノード管理できるスロット数で、16また64、通常は16です。スロット数が大きいほど階層化は少なくて済みますが、その分階層毎に広範囲にわたってスロットを検索する必要があります。

tags[][]は、slotの空き状態をビットで管理します。RADIX_TREE_TAG_LONGSはRADIX_TREE_MAP_SIZE(slotサイズ)をBITS_PER_LONG(tags[][]がlongで、longのビットサイズ)で割ることで、slot数に応じてた配列サイズとなります。

RADIX_TREE_MAX_TAGは管理するオブジェクト(page)を属性に応じても管理できるようにするためです。

#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)

#define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))

#define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
                                         RADIX_TREE_MAP_SHIFT))

#define RADIX_TREE_MAX_TAGS 3

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];
};


#define RADIX_TREE_INIT(mask)   {                                      \
       .height = 0,                                                    \
       .gfp_mask = (mask),                                             \
       .rnode = NULL,                                                  \
}

radixモジュールがロードされると、radix_tree_init_maxindex()で階層毎の最大インデックスをheight_to_maxindex[i]に設定します。radix tree参照時、height_to_maxindex[]を参照することで、検索開始階層からスロットを検索します。

static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;

static __init void radix_tree_init_maxindex(void)
{
       unsigned int i;

       for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
               height_to_maxindex[i] = __maxindex(i);
}

static __init unsigned long __maxindex(unsigned int height)
{
       unsigned int width = height * RADIX_TREE_MAP_SHIFT;
       int shift = RADIX_TREE_INDEX_BITS - width;

       if (shift < 0)
               return ~0UL;
       if (shift >= BITS_PER_LONG)
               return 0UL;
       return ~0UL >> shift;
}

サンプル

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

MODULE_LICENSE("GPL");
MODULE_AUTHOR("y.kitamura");

struct radix_tree_root radix_tree = RADIX_TREE_INIT(GFP_ATOMIC|__GFP_NOWARN);

struct my_object {
   char data[100];
   int     index;
};
static  void    set_data(void);

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

   set_data();
   for (i = 0; i < 100; i++) {
       p = radix_tree_lookup(&radix_tree, i);
       printk("%s\n", p->data);
   }
   return 0;
}

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

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

static  void    set_data()
{
   int     i;
   struct my_object *myobj;

   for (i = 0; i < 100; i++) {
       myobj = kmalloc(sizeof(struct my_object), GFP_KERNEL);
       myobj->index = i;
       sprintf(myobj->data, "radix data:%d", i);
       radix_tree_insert(&radix_tree, myobj->index, myobj);
   }
}

module_init(mod_init);
module_exit(mod_exit);

[root@localhost lkm]# dmesg
[ 2508.232194] radix data:0
[ 2508.232204] radix data:1
[ 2508.232209] radix data:2
  :
[ 2508.232586] radix data:97
[ 2508.232590] radix data:98
[ 2508.232594] radix data:99