Chinaunix首页 | 论坛 | 博客
  • 博客访问: 443513
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 594
  • 用 户 组: 普通用户
  • 注册时间: 2013-12-17 16:24
个人简介

我是一只小小鸟

文章分类

全部博文(184)

文章存档

2016年(1)

2015年(55)

2014年(127)

2013年(1)

分类: LINUX

2014-05-21 21:14:43

原文地址:内核radix tree初探 作者:lizhijie86su

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


阅读(695) | 评论(0) | 转发(0) |
0

上一篇:pdflush进程详解

下一篇:理解哈希表

给主人留下些什么吧!~~