一、概述

Linux radix树最广泛的用途是用于内存管理，结构address_space通过radix树跟踪绑定到地址映射上的核心页，该radix树允许内存管理代码快速查找标识为dirty或writeback的页。Linux radix树的API函数在lib/radix-tree.c中实现。

Linux基数树（radix tree）是将指针与long整数键值相关联的机制，它存储有效率，并且可快速查询，用于指针与整数值的映射（如：IDR机制）、内存管理等。

上图显示了一个有3级结点的radix树，每个数据条目（item）可用3个6位的键值（key）进行索引，键值从左到右分别代表第1~3层结点位置。没有孩子的结点在图中不出现。因此，radix树为稀疏树提供了有效的存储，代替固定尺寸数组提供了键值到指针的快速查找。
以index=0x5BFB68为例，化为二进制，每6位为一组：10110(22,第一层编号) 111111(63第二次编号) 101101(45第三层编号) 101000(40第四层编号)

二、基本数据结构

struct radix_tree_root {
unsigned int height;
gfp_t gfp_mask;
struct radix_tree_node *rnode;/*间接指针指向结点而非数据条目，通过设置root->rnode的低位表示是否是间指针*/
};

struct radix_tree_node {
unsigned int height; /* 从叶子向上计算的树高度 */
unsigned int count; /*非叶子结点含有一个count域，表示出现在该结点的孩子的数量*/
struct rcu_head rcu_head;
void *slots[RADIX_TREE_MAP_SIZE]; //64个指针，每层64个子节点
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
//2X2数组，每个成员都为32位，
在结点结构radix_tree_node中，tags域是一个二维数组，每个slot用2位标识，这是一个典型的用空间换时间的应用。tags域用于记录该结点下面的子结点有没有相应的标志位。
//结点标签数组=每个slot需要的最大标签位数*slot数所需的long类型变量数
/*tag[0]64位，2个long类型，每一位代表一个slot，表示其PG_dirty
tag[0]64位，2个long类型，每一位代表一个slot，表示其PG_Writeback
如果当前节点的tags[0]值为1，那么它的子树节点就存在PAGE_CACHE_DIRTY节点，否则这个子树分枝就不存在着这样的节点，就不必再查找这个子树了。比如在查找PG_dirty的页面时，就不需要遍历整个树，而可以跳过那些tags[0]为0值的子树，这样就提高了查找效率*/
};

三、全局定义

#define RADIX_TREE_MAP_SHIFT 6
/*值为6时，表示每个结点有2^6＝64个slot，值为4时，表示有2^4=16个slot*/
#define RADIX_TREE_MAP_SIZE (1UL </*表示1个叶子结点可映射的页数，如：1<<6=64，表示可映射64个slot映射64页*/
#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) //111111
#define RADIX_TREE_TAG_LONGS \
((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) /BITS_PER_LONG) //(64+32-1)/32=2
#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsignedlong)) //32
#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
RADIX_TREE_MAP_SHIFT)) //(32+6-1)/6=6
#define RADIX_TREE_MAX_TAGS 2
/*定义slot数占用的long类型长度个数，每个slot用位图1位进行标记，如：64个slot时，值为2*/

static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1]
// 全局数组，在32位机器上，这个数组大小是7，表示每一层的最大有多少个slot
height=0:maxindex=0， 第一层只有一个radix_tree_node
height=1:maxindex=2^6-1, 第二层最多63个
height=2:maxindex=2^12-1,
height=3:maxindex=2^18-1,
height=4:maxindex=2^24-1, 若每个slot为4k，则表示支持64G
height=5:maxindex=2^30-1,
height=6:maxindex=2^32-1, 16T

四、初始化函数

初始化一个名字是name的树根。mask是gfp相关的掩码，在内存管理的时候用到。
#define RADIX_TREE(name, mask)
struct radix_tree_root my_tree;
INIT_RADIX_TREE(my_tree, gfp_mask);
248 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, SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
1253 radix_tree_node_ctor);
1254 radix_tree_init_maxindex();//初始化全局数组height_to_maxindex
1255 hotcpu_notifier(radix_tree_callback, 0);
1256 }

五、插入条目