Radix Tree总结

Date:2019-6-19
主要转载自:
https://www.cnblogs.com/mingziday/p/3969269.html
https://blog.csdn.net/qq_22613757/article/details/91049293
https://blog.csdn.net/joker0910/article/details/8250085

由于原博比较混乱，这里单独整理一下排版：

一、概述

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 <<RADIX_TREE_MAP_SHIFT) //1000000,2^6=64
/*表示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

四、初始化函数

与初始化radix tree有关的函数有三个，尚不清楚他们之间的相互关系以及该调用谁

//初始化一个名字是name的树根。mask是gfp相关的掩码，在内存管理的时候用到。
#define RADIX_TREE(name, mask) 
	struct radix_tree_root name = RADIX_TREE_INIT(mask)
#define RADIX_TREE_INIT(mask)	{
	.height = 0,
	.gfp_mask = (mask),
	.rnode = NULL,
}

#define INIT_RADIX_TREE(root, mask)
do {
	(root)->height = 0;
	(root)->gfp_mask = (mask);
	(root)->rnode = NULL;	
} while (0)

void __init radix_tree_init(void)
{
radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
		sizeof(struct radix_tree_node), 0,
		SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
		radix_tree_node_ctor);
radix_tree_init_maxindex();
hotcpu_notifier(radix_tree_callback, 0);
}

五、基础操作函数

1.插入函数

int radix_tree_insert(struct radix_tree_root *root, unsigned long, void *item);

函数radix_tree_insert插入条目item到树root中，如果插入条目中内存分配错误，将返回错误-ENOMEM。该函数不能覆盖写正存在的条目。如果索引键值index已存在于树中，返回错误-EEXIST。插入操作成功返回0。

对于插入条目操作失败将引起严重问题的场合，下面的一对函数可避免插入操作失败：

int radix_tree_preload(gfp_t gfp_mask);
void radix_tree_preload_end(void);

函数radix_tree_preload尝试用给定的gfp_mask分配足够的内存，保证下一个插入操作不会失败。在调用插入操作函数之前调用此函数，分配的结构将存放在每CPU变量中。函数radix_tree_preload操作成功后，将关闭内核抢占。因此，在插入操作完成之后，用户应调用函数radix_tree_preload_end打开内核抢占。

2.删除函数

void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)

函数radix_tree_delete删除与索引键值index相关的条目，如果删除条目在树中，返回该条目的指针，否则返回NULL。

3.查询函数

/*在树中查找指定键值的条目，查找成功，返回该条目的指针，否则，返回NULL*/
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index);
/*返回指向slot的指针，该slot含有指向查找到条目的指针*/
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index);
/*多键值查找，max_items为需要查找的item个数，results表示查询结果。查询时键值索引从first_index开始*/
radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items);

4.标签操作

 /*将键值index对应的条目设置标签tag，返回值为设置标签的条目*/
void *radix_tree_tag_set(struct radix_tree_root *root, unsigned long index, unsigned int tag);
/*从键值index对应的条目清除标签tag，返回值为清除标签的条目*/
void *radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index, unsigned int tag);
/*检查键值index对应的条目tag是否设置。tag参数为0或者1，表示Dirty位或者WB位
如果键值不存在，返回0，如果键值存在，但标签未设置，返回-1；如果键值存在，且标签已设置，返回1*/
int radix_tree_tag_get(struct radix_tree_root *root, unsigned long index, unsigned int tag);
/*从first_index起查询树root中标签值为tag的条目，在results中返回*/
unsigned int radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag);
/*如果树root中有任何条目使用tag标签，返回键值*/
int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);