-
基数（
radix
）树
-
嵌入式系统书撰写
2010-07-23
基数（
radix
）树
Linux
基数树（
radix tr
ee
）是将指针与
long
整数键值相
关联的机制，它存储
有效率，并且可快速查询，用于指针与整数值的映射（如：
IDR
机制）、内存管
理等。
< br>
IDR
（
ID Radix<
/p>
）机制是将对象的身份鉴别号整数值
ID
与对象指针建立关联表，
完成从
ID
与
指针之间的相互转换。
IDR
机制使用
radix
树状结构作为由
id
进行<
/p>
索引获取指针的稀疏数组，
通过使用位图可以快速分配新的
ID
，
IDR
机制避
免了
使用固定尺寸的数组存放指针。
IDR
机制的
API
函数在
lib/id
r.c
中实现，这里
不加分析。
Linux radix
树最广泛的用途是用于内存管理，结构
address_space
通过
ra
dix
树跟踪绑定到地址映射上的核心页，
该
< br>radix
树允许内存管理代码快速查找标识
为
dirty
或
writeback
的页。
Linux radix
树的
API
函数在
lib/radix-
tree.c
中实现。
（
1
）
radix
树概述
ra
dix
树是通用的字典类型数据结构，
radix
树又称为
PAT
位树（
Pa
tricia
Trie
or crit bit tree
）。
Linux
内核使用了数据类型<
/p>
unsigned long
的固定长度输
入的版本。每级代表了输入空间固定位数。
radix t
ree
是一种多叉搜索树，树的叶子结点是实际的数据条目。每个结点有
一个固定的、
2^n
指针指向子结点（每个指针称为槽
slot
），并有一个指针指向
父结点
。
Linux
内核利用
radix
树在文件内偏移快速定位文件缓存页，图
4
是一个
radix
树样例，该
radix
树的分叉为
4(22)
，树高为
4
，树的每个叶子结点用来快速定
位
8
位文件内偏移，
可以定位
4x4x4x4=256
页，
如：
图中虚线对应的两个叶子结
点的路径组成值
0x
和
0x
，指向文件内相
应偏移所对应的缓存页。
图
4
一个四叉
radix
树
Linux
radix
树每个结点有
64
个
slot
，与数据类型
long
的位数相同，图
1
显示
了一个有
3
< br>级结点的
radix
树，
每个数
据条目
（
item
）
< br>可用
3
个
6
位的键值
（
key
）
进行索引，
键值从左到右分别代表第
1~3
层结点位置。
没有孩子的结点在图中不
出现。因
此，
radix
树为稀疏树提供了有效的存储，代替固定尺寸数
组提供了键
值到指针的快速查找。
图
1
一个
3
级结点的
radix
树及其键值表示
（
2
）
radix
树
slot
数
Linux
内核根用户配置将树的<
/p>
slot
数定义为
4
或
6
，即每个结点有
16
或
64
个
slot
，如图
2
所示，当树高为
< br>1
时，
64
个
< br>slot
对应
64
个页，当树高
为
2
时，
对应
64*64
个页。
图
2
高为
1
和
2
、
slot
数为
64
的
radix
树
Linux
内核
radix
树的
slot
数定义如
下（在
lib/radix-
tree.c
中）：
#ifdef __KERNEL__
/*
< br>值为
6
时，
表示每个结点有
2^6
＝
64
个<
/p>
slot
，
值为
4
时，
表示有
2^4=16
个
slot*/
#define
RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL
? 4
: 6)
#else
#define RADIX_TREE_MAP_SHIFT 3 /*
用于更有强度的测试
*/
#endif
/*
表示
1
个叶子结点可映射的页数，如：
1<<6=64<
/p>
，表示可映射
64
个
slot
映射
64
页
*/
#define RADIX_TREE_MAP_SIZE
(1UL << RADIX_TREE_MAP_SHIFT)
#define
RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
/*
定义
slot
数占用的
long
类型长度个数，
每个
slot
用位图
1
位进
行标记，
如：
64
个
< br>slot
时，值为
2*/
#define RADIX_TREE_TAG_LONGS
((RADIX_TREE_MAP_SIZE + BITS_PER_LONG -
1) / BITS_PER_LONG)
（
3
）结点结构
树的根结点结构
radix_tree_root
< br>列出如下（在
include/linux/radix-
tree.h
中）：
#define
RADIX_TREE_MAX_TAGS 2 /*
每个
sl
ot
需要的最大标签位数
*/
/*
根结点的标签存放在
gfp_mask
中，通过
__GFP_BITS_SHIFT
移位得到
*/
struct radix_tree_root {
unsigned int height; /*
从叶子向上计算的树高度
*/
gfp_t
gfp_mask;
/*
间接指针指向结点而非数据条目，通过设置
root->rnode
的低位表示
是否是间指针<
/p>
*/
struct radix_tree_node *rnode;
#ifdef CONFIG_RADIX_TREE_CONCURRENT
struct radix_tree_context *context;
struct
task_struct *owner;
#endif
};
结构
radix_tree_context
列出如下：
struct radix_tree_context {
struct
radix_tree_root *root;
#ifdef
CONFIG_RADIX_TREE_CONCURRENT
spinlock_t
*locked;
#endif
}
树的结点结构
radix_tree
_node
列出如下（在
lib/radix-
tree.c
中）：
struct
radix_tree_node {
unsigned int height; /*
从叶子向上计算的树高度
*/
unsigned int
count; /*
非叶子结点含有一个
count
域，表示出现在该
结点的孩子的数量
*/
struct rcu_head rcu_head;
void
*slots[RADIX_TREE_MAP_SIZE]; /*
结点的
slot
指针
*/
/*
结点标签数组
=
每个
slot
需要的最大
标签位数
*slot
数所需的
long
类
型变量数
*/
unsigned long
tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
Linux
内核
radix
树高度是可变的，它依赖于存储的索引
键值。
radix
树查询必
须知道树高
度，
以便知道结点的
slot
是指向叶
子结点的指针还是结点的其他层。
Linux
在结点结构中有成
员
height
存入树高度信息。
Linux
radix
树的独特特征
是标签扩展。图
2
显示了有
2
个标签，分别表示打开
和关闭。这些标签是结点结构的成员
tags
，该标签用一个位图实现，在加锁的
情况下
设置和清除。
每个标签基本上是一个在
radix
树顶层上的位图序号。
标签
与群查询一起用来在给定
的范围内查找给定标签集的页。
标签在每结点位图中维护，<
/p>
在每个给定的级别上，
可以判定下一个级别是否至少
有一个标签集。
图
2
带有
2
位图标签指示的
8
< br>位
radix
树
在结点结构
radix_tree_
node
中，
tags
域是一个二维数
组，每个
slot
用
2
位标
识，这是一个典型的用空间换时间的应用。
tag
s
域用于记录该结点下面的子结
点有没有相应的标志位。
目前
RADIX_TREE_MAX_TAGS
为
2
，
表示只记录两个标志，
其中
tags[0]
为
PAGE_CACHE_DIRTY
，
tags[1]
为
PAGE_CACHE_WRITEBACK
。如果当
前节点的
tags[0]
值
为
1
，
那么它的子树节点就存在
PAGE_CACHE_DIRTY
节点，
否
则这个子树分枝就不存在着这样的节点，
就不必再查找这个子树
了。
比如在查找
PG_dirty
的页
面时，
就不需要遍历整个树，
而可以跳过那些
< br>tags[0]
为
0
值的子
树，这样就提高了查找效率。
“加标签查
询”是返回有指定标签集
radix
树条目的查询，
可以查询设置了标签
的条目。
加标签查询可以并行
执行，
但它们需要通过设置或清除标签从操作上互
斥。
(4)
并行操作的优化
Linux
radix
树并行操作包
括并行查询和并行修改，其中，并行修改在标准内核
中未完没有实现，需要通过打补丁获
得该功能。并行操作说明如下：
?
RCU
并发查询
通过使用
RCU
，
RCU Radix
树可以进行完全并发的查询操作。<
/p>
RCU
从根本上要求
原子操作地移动指针
从数据结构的一个版本到新的版本，
保持旧版本直到系统经
过静
止状态。
在静止状态点，
旧版本数据结构已没有用户，
因此可以被安全释放。
RCU
radix
树的修改操作之间还需要串行化，但是查询不再需要与修改操作串
行
化。
?
并发修改
RCU
可使
RCU
< br>radix
树查询完全并行化，但修改操作成了“瓶颈”。这可通过将
全树的锁破碎成较小的锁进行改善，
再明显的方法是对结点进行加锁而非对
整个
树加锁。
radix
树修改操作可分为单向和双向操作。
单向操作仅执行从根节点和叶子结点<
/p>
的单方向指针移动，它包括插入、更新和设置标签操作。双向操作较复杂，它需
要在指针移到叶子后又回移，它包括删除和清除标签操作。
梯级加锁（
Ladder
Locking
）和锁耦合（
Lock-Coupling
）技术常用于数据库方
面，允许单向遍历结点加锁的树（双向可能产
生死锁）。如果所有的修改者从树
顶到树底进行修改，并且修改的结点持有锁，那么，向
下遍历时对孩子加锁，在
孩子被锁住时再释放该结点锁。
在这种
情况下并发操作是可能的，
因为只要根结
点解锁，
另一个操作就可以自上向下进行。
如果两操作的路径没有相同操作结点，
后一个操作可能在前一个操作完成之前完成。
最坏的情况是流水线操
作，
但这还
是比串行化操作好很多。
双向操作包括删除和清除标签操作，分别说明如下：
1
）清除标签
在
radix
树中清除一个标签包括向下遍历树、
查找定位条目和清除条目标签的操
作。
只要孩子结点没有打标签的条目，
就可以向上遍历
结点清除标签。
结束条件
是：
如果遍历
遇到一个结点，
在清除一个标签后，
它还有一个或多个条目带有
标
签集，
就可以结束向上遍历。
为了与
向下遍历期间有同样的结束点，
将终止条件
改为：
向上遍历将在有比清除标签数更多标签的结点处结束。
这样，
不论何时遇
到这样的结点，将作为上遍历树的结束点。
2
）删除元素
删除元素在删除无用结点时还需要删除该条目的所有标签。<
/p>
它的终止条件需要满
足这两个方面。
向上
回退遍历树时需要满足下面的条件：
当遇到一个非空结点且
没有
无用的标签时应终止向上回退遍历树。
在向下遍历树时鉴别此
点的条件是：
当遇到有超过
2
个孩子的
结点、
并且每个标
签来说结点有多于一个标签条目被清除时，<
/p>
结束向上遍历。
该条件用来鉴别向上
回退
遍历的终止点。
（
5
）
radix
树
API
说明
?
声明和初始化
radix
树
声明和初始化<
/p>
radix
树的方法列出如下：
#include
/*
gfp_mask
表示如何执行内存分配，如果操作（如：插入）以原子性上下文中
执行，其值为
GFP_ATOMIC*/
RADIX_TREE(name,
gfp_mask); /*
声明和初始化名为
name
的树
*/
struct
radix_tree_root my_tree;
INIT_RADIX_TREE(my_tree, gfp_mask);
?
插入条目
插入条目的函数定义列出如下：
int
radix_tree_insert(struct
radix_tree_root
*root,
unsigned
long
index,
void *item)
函数
radix_tree_ins
ert
插入条目
item
到树
root
中，
如果插入条目中内存分配
错误，将返回错误
-ENOMEM
。该函数不能
覆盖写正存在的条目。如果索引键值
index
已存在于树中，
返回错误
-EEXIST
。插入操作成功是，返回
0
。
对于插入条目操作失
败将引起严重问题的场合，
下面的一对函数可避免插入操作
失败
：
int
radix_tree_preload(gfp_t gfp_mask);
void radix_tree_preload_end(void);
函数
radix_tree_pre
load
尝试用给定的
gfp_mask
分配足够的内存，
保证下一个
插入操作不会失败。
在调用插入操作函数之前调用此函数，
分配的结构将存放在
每
CPU
变量中。
函数
radix_tree_preload
操作成功后，
将完毕内核抢占。
因此，
在插入操作完成之后，
用户应调用函数
radix_tree_preload_end
打开内核抢占。
?
删除条目
删除条目的函数定义列出如下：
void *radix_tree_delete(struct
radix_tree_root *root, unsigned long
index)
函数
radix_tree_delete
删除与索引键值
index
相关的条目，
如果删除条目在树
< br>中，返回该条目的指针，否则返回
NULL
。
?
查询操作
用于查询操作的函数定义列出如下：
/*
在树中查找指定键值的条目，
查找成功，
返回该条目的指针，
否则，
返回
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
条
目在
results
中。
查询时键值索
引从
first_index
开始
*/
radix_tree_gang_lookup(struct
radix_tree_root *root, void **results,
unsigned long first_index, unsigned int
max_items);
?
标签操作
与标签操作相关的函数说明列出如下：
/*
将键值
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
，如果键值不存在，返回
0
，如果
键值存在，但标签未设置，返回
-1
；如果键值存在，且标签已设置，返回
1*/
int radix_tree_tag_get(struct
radix_tree_root *root, unsigned long
index, unsigned int tag);
/*
从
first_index
起查询树<
/p>
root
中标签值为
tag
的条目，在
results
中返回
< br>*/
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);
（
6
）并行
操作使用
radix
树
API
的方法
?
查询获取
slot
操作
< br>查询操作支持
RCU
无阻塞并行读操作，因此，需要遵循
RCU
的用法加
RCU
读锁，
还需要将
rcu_dereference()
用于获得的
slot
，在写（或更新）
操作时，需要给
新的
slot
使用
rcu_assign_pointer()
。查询操作的使用方法
列出如下：
struct page **slot,
*page;
rcu_read_lock();
slot
= radix_tree_lookup_slot(&mapping->page_tree,
index);
page = rcu_dereference(*slot);
rcu_read_unlock();
?
查询修改
slot
操作
< br>Linux
内核的
radix
树
需要打补丁才支持并发修改。
查询仅有一个全局状态：
RCU<
/p>
静止状态，并发修改需要跟踪持有什么锁。锁状态对于操作来说必须是外部的，
因此，我们需要实例化一个本地上下文跟踪这些锁。查询修改
slot
的方法列出
如下：
struct page **slot;
DEFINE_R
ADIX_TREE_CONTEXT(ctx,&mapping->page_tree);
radix_tree_lock(&ctx);
/*
锁住了根结点
*/
/*
代替
&mapping->page_tree
作为根，可以传递上下文
slot =
radix_tree_lookup_slot(, index);
rcu_assign_pointer(*slot, new_page);
radix_tree_unlock(&ctx);
<
/p>
radix
树
API
函数
radix_tree_lookup_slot
含有
锁从树顶向下移动机制，锁移
动的代码部分列出如下：
void **radix_tree_lookup_slot(struct
radix_tree *root, unsigned long
index)
{
...
RADIX_TREE_CONTEXT(context, root); /*
提供
上下文和实际的
root
指
针
*
、
...
do
{
...
/*
从树顶向下移动锁
*/
radix_ladder_lock(context, node);
...
}
while (height > 0);
...
}
（
7
）
radix
树
API
的实现
树的操作通常包括查找
、
插入、
删除和树调整，
下面分别说明
radix
树这些操作
-
-
-
-
-
-
-
-
-
上一篇：中药的拉丁名整理大全
下一篇：中药拉丁名大全