無料Wikiサービス | デモページ
検索

アクセス数
最近のコメント
kprobe - ななし
ksetの実装 - スーパーコピー
カーネルスレッドとは - ノース
カーネルスレッドとは - nbyst
asmlinkageってなに? - ノース
asmlinkageってなに? - よろしく
はじめ - ノース
はじめ - ノース
はじめ - 楽打連動ユーザー
はじめ - 楽打連動ユーザー
Adsense
広告情報が設定されていません。

radix-tree(基数ツリー)


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

補足

myobj->index = i;はradix treeそのものと無関係です。myobjからradix treeのslot[]検索時に使われるもので、pageがキャッシュ実装としてのカーネルでは、pageが登録されているかどうかチェックすっるために必要です。従ってradix treeの階層はunsigned int height(階層)で、1 << (32 - 1) - 1までOKですが、pageキャッシュでは最大6となるのは、unsigned int page->index(slot数)故と言うことです。

最終更新 2014/06/12 19:02:39 - north
(2010/05/26 19:16:37 作成)