内核radix tree初探

radix tree中文名“基树”。主要用在内存页管理上，这个链接是Linux Weekly News上对radix tree的描述：

• radix-tree.c中的一些定义：

  37 #define RADIX_TREE_MAP_SHIFT 6
  41
  42 #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)    //1000000,2^6=64

  43 #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)    //111111

  44
  45 #define RADIX_TREE_TAG_LONGS \
  46 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)    //(64+32-1)/32=2

  47
  48 struct radix_tree_node {
  49 unsigned int height; /* Height from the bottom */
  50 unsigned int count;
  51 struct rcu_head rcu_head;
  52 void *slots[RADIX_TREE_MAP_SIZE];
  53 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
  54 };
...
  61 #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))    //32

  62 #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
  63 RADIX_TREE_MAP_SHIFT))                //(32+6-1)/6=6

  64
  65 /*
  66 * The height_to_maxindex array needs to be one deeper than the maximum
  67 * path as height 0 holds only 1 entry.
  68 */
  69 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
  70
  71 /*
  72 * Radix tree node cache.
  73 */
  74 static struct kmem_cache *radix_tree_node_cachep;

• radix-tree.h中的定义

58 #define RADIX_TREE_MAX_TAGS 2
 59
 60 /* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
 61 struct radix_tree_root {
 62 unsigned int height;
 63 gfp_t gfp_mask;
 64 struct radix_tree_node *rnode;
 65 };

• 在start_kernel的时候调用初始化函数（初始化一些全局变量）：

1248 void __init radix_tree_init(void)
1249 {
1250 radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
1251 sizeof(struct radix_tree_node), 0,
1252 SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1253 radix_tree_node_ctor);
1254 radix_tree_init_maxindex();
1255 hotcpu_notifier(radix_tree_callback, 0);
1256 }


1)首先在cache上申请一个radix_tree_node的内存，radix_tree_node_cachep是全局，定义在 lib/radix-tree.c
2)radix_tree_init_maxindex初始化height_to_maxindex[]数组 （每个height中的最大index），在32位机器上，这个数组大小是7，初始化后数组中的元素是：
height=0:maxindex=0， 第一层只有一个radix_tree_node
height=1:maxindex=2^6-1,111111，第二层最多63个
height=2:maxindex=2^12-1,111111-111111，
height=3:maxindex=2^18-1,111111-111111-111111，
height=4:maxindex=2^24-1,111111-111111-111111-111111，
height=5:maxindex=2^30-1,111111-111111-111111-111111-111111，
height=6:maxindex=2^32-1,111111-111111-111111-111111-111111-11
3) 最后注册了一个回调函数radix_tree_callback，还不知道具体什么时候会调用这个函数，作用是用来释放cache上的 radix_tree_node_cachep。关机的时候？？

• radix-tree APIs，分如下几类：

1.初始化函数和宏：
初始化一个名字是name的树根。mask是gfp相关的掩码（get free page），在内存管理的时候用到。

#define RADIX_TREE(name, mask)

2.基础操作：

165 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
166 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
167 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
168 void *radix_tree_delete(struct radix_tree_root *, unsigned long);

3.gang基础操作：

169 unsigned int
170 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
171 unsigned long first_index, unsigned int max_items);
172 unsigned int
173 radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
174 unsigned long first_index, unsigned int max_items);
175 unsigned long radix_tree_next_hole(struct radix_tree_root *root,
176 unsigned long index, unsigned long max_scan);
177 unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
178 unsigned long index, unsigned long max_scan);

4.tag操作：
关于tag，这是linux内核radix tree的一个特性，用来在内存管理中标识page的dirty或writeback。

181 void *radix_tree_tag_set(struct radix_tree_root *root,
182 unsigned long index, unsigned int tag);
183 void *radix_tree_tag_clear(struct radix_tree_root *root,
184 unsigned long index, unsigned int tag);
185 int radix_tree_tag_get(struct radix_tree_root *root,
186 unsigned long index, unsigned int tag);

187 unsigned int
188 radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
189 unsigned long first_index, unsigned int max_items,
190 unsigned int tag);
191 unsigned int
192 radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
193 unsigned long first_index, unsigned int max_items,
194 unsigned int tag);
195 int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);