| radix tree中文名“基树”。主要用在内存页管理上,这个链接是Linux Weekly News上对radix tree的描述: http://lwn.net/Articles/175432/
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;
|
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。关机的时候??
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);
|
|