【页高速缓存】radix tree 源码解析

项目要在内核做和页高速缓存相类似缓存机制，在写内核代码之前必须先搞清楚页高速缓存源码是什么情况。 之前有一篇博客分析过了页高速缓存的基础，但是远远没有达到动手写代码的基础。这几天端午节假期集中精力，搞懂整个框架 与 在内核中的应用。

其他类别的博客也不会停止更新。

谨以此祭奠逝去的时间。

前言

基于内核版本 4.4.4

• Linux 基数树（radix tree）是将指针与long整数键值相关联的机制，它存储有效率，并且可快速查询，用于指针与整数值的映射（如：IDR机制）、内存管理等。
• IDR（ID Radix）机制是将对象的身份鉴别号整数值ID与对象指针建立关联表，完成从ID与指针之间的相互转换。IDR机制使用radix树状结构作为由id进行索引获取指针的稀疏数组，通过使用位图可以快速分配新的ID，IDR机制避免了使用固定尺寸的数组存放指针。IDR机制的API函数在lib/idr.c中实现，这里不加分析。

基于页高速缓存基础这篇博客我们已经知道：

• 页高速缓存的核心数据结构是 address_space.
• 每个inode表示的文件里面都有一个i_mapping字段。真正的对象就在 i_data字段。

struct address_space *i_mapping; struct address_space i_data; 

• 每个页描述符都包括把页链接到页高速缓存的两个字段mapping和index。

struct page { /* First double word block */ unsigned long flags; /* Atomic flags, some possibly * updated asynchronously */ union { struct address_space *mapping; /* If low bit clear, points to * inode address_space, or NULL. * If page mapped as anonymous * memory, low bit is set, and * it points to anon_vma object: * see PAGE_MAPPING_ANON below. */ void *s_mem; /* slab first object */ }; /* Second double word */ struct { union { pgoff_t index; /* Our offset within mapping. */ void *freelist; /* sl[aou]b first free object */ }; .... .... ... }; 

• address_space对象字段中， host 指向其所有者的索引对象 inode。 但真正的数据保存在 page_tree 里面。

struct address_space { struct inode *host; /* owner: inode, block_device 指向拥有该对象的索引节点的指针*/ struct radix_tree_root page_tree; /* radix tree of all pages 表示拥有者页的基数radix tree 的根*/ spinlock_t tree_lock; /* and lock protecting it 保护基树的自旋锁 */ atomic_t i_mmap_writable;/* count VM_SHARED mappings 地址空间中共享内存映射的个数*/ struct rb_root i_mmap; /* tree of private and shared mappings radix优先搜索树的根 */ struct rw_semaphore i_mmap_rwsem; /* protect tree, count, list */ /* Protected by tree_lock together with the radix tree */ unsigned long nrpages; /* number of total pages */ unsigned long nrshadows; /* number of shadow entries */ pgoff_t writeback_index;/* writeback starts here */ const struct address_space_operations *a_ops; /* methods */ unsigned long flags; /* error bits/gfp mask */ spinlock_t private_lock; /* for use by the address_space */ struct list_head private_list; /* ditto */ void *private_data; /* ditto */ } 

现在就把重点放在 radix_tree_root这个数据结构：

Radix Tree

linux 内存管理通过radix树管理映射到地址空间上的核心页，该树允许内存管理代码快速查找标识为dirty或writeback的页。Linux radix树的API函数在 lib/radix_tree.c中。

主要数据结构：

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

struct radix_tree_node { unsigned int height; /* Height from the bottom */ unsigned int count; /*非叶子结点含有一个count域，表示出现在该结点的孩子的数量*/ struct rcu_head rcu_head; void __rcu *slots[RADIX_TREE_MAP_SIZE];64个指针，每层64个子节点 /* 结点标签数组=每个slot需要的最大标签位数*slot数所需的long类型变量数: 3 * 64位 */ unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; //管理页的状态标志数组 }; 

全局定义

#define RADIX_TREE_MAX_TAGS 3 /*每个slot需要的最大标签位数*/ #ifdef __KERNEL__ #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) /*值为6时，表示每个结点有2^6＝64个slot，值为4时，表示有2^4=16个slot*/ #else #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ #endif #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) /*表示1个叶子结点可映射的页数，如：1<<6=64，表示可映射64个slot映射64页*/ #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1) // #define RADIX_TREE_TAG_LONGS \ ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG) //(64+32-1)/32=2 /*定义slot数占用的long类型长度个数，每个slot用位图1位进行标记，如：64个slot时，值为2*/ #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long)) //32 #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT)) //(32+6-1)/6=6 /* Height component in node->path */ #define RADIX_TREE_HEIGHT_SHIFT (RADIX_TREE_MAX_PATH + 1) #define RADIX_TREE_HEIGHT_MASK ((1UL << RADIX_TREE_HEIGHT_SHIFT) - 1) /* Internally used bits of node->count */ #define RADIX_TREE_COUNT_SHIFT (RADIX_TREE_MAP_SHIFT + 1) #define RADIX_TREE_COUNT_MASK ((1UL << RADIX_TREE_COUNT_SHIFT) - 1) 

插入函数

int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item) { struct radix_tree_node *node; void slot; int error; BUG_ON(radix_tree_is_indirect_ptr(item)); error = __radix_tree_create(root, index, &node, &slot); //创建一个slot if (error) return error; if (*slot != NULL) return -EEXIST; rcu_assign_pointer(*slot, item); //将item的值赋值给slot if (node) { node->count++; BUG_ON(tag_get(node, 0, index & RADIX_TREE_MAP_MASK)); BUG_ON(tag_get(node, 1, index & RADIX_TREE_MAP_MASK)); } else { BUG_ON(root_tag_get(root, 0)); BUG_ON(root_tag_get(root, 1)); } return 0; } EXPORT_SYMBOL(radix_tree_insert); 

其中最重要的是__radix_tree_create 函数：

int __radix_tree_create(struct radix_tree_root *root, unsigned long index, struct radix_tree_node nodep, void *slotp) { struct radix_tree_node *node = NULL, *slot; unsigned int height, shift, offset; int error; /* Make sure the tree is high enough. */ if (index > radix_tree_maxindex(root->height)) { //发现需要插入的index大于目前树的叶子个数 error = radix_tree_extend(root, index); //扩展树 if (error) return error; } slot = indirect_to_ptr(root->rnode); height = root->height; shift = (height-1) * RADIX_TREE_MAP_SHIFT; offset = 0; /* uninitialised var warning */ while (height > 0) { if (slot == NULL) { /* Have to add a child node. */ if (!(slot = radix_tree_node_alloc(root))) return -ENOMEM; slot->path = height; slot->parent = node; if (node) { rcu_assign_pointer(node->slots[offset], slot); node->count++; slot->path |= offset << RADIX_TREE_HEIGHT_SHIFT; } else rcu_assign_pointer(root->rnode, ptr_to_indirect(slot)); } /* Go a level down */ offset = (index >> shift) & RADIX_TREE_MAP_MASK; node = slot; slot = node->slots[offset]; shift -= RADIX_TREE_MAP_SHIFT; height--; } if (nodep) *nodep = node; if (slotp) *slotp = node ? node->slots + offset : (void )&root->rnode; return 0; } 

查找函数

void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index) { return __radix_tree_lookup(root, index, NULL, NULL); } void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, struct radix_tree_node nodep, void *slotp) { struct radix_tree_node *node, *parent; unsigned int height, shift; void slot; node = rcu_dereference_raw(root->rnode); if (node == NULL) return NULL; if (!radix_tree_is_indirect_ptr(node)) { if (index > 0) return NULL; if (nodep) *nodep = NULL; if (slotp) *slotp = (void )&root->rnode; return node; } node = indirect_to_ptr(node); height = node->path & RADIX_TREE_HEIGHT_MASK; if (index > radix_tree_maxindex(height)) return NULL; shift = (height-1) * RADIX_TREE_MAP_SHIFT; do { parent = node; slot = node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK); node = rcu_dereference_raw(*slot); if (node == NULL) return NULL; shift -= RADIX_TREE_MAP_SHIFT; height--; } while (height > 0); if (nodep) *nodep = parent; if (slotp) *slotp = slot; return node; } 

按照index >> shift 左移来查找，找不到返回空，如果找到返回存储地址。

下面这篇文档非常重要，原来已经有大佬指点江山！！！
参考： https://blog.csdn.net/joker0910/article/details/

下面的内容来自上面的文档

摘自文档

(4) 并行操作的优化

Linux radix树并行操作包括并行查询和并行修改，其中，并行修改在标准内核中未完没有实现，需要通过打补丁获得该功能。并行操作说明如下：

RCU并发查询 

并发修改 

双向操作包括删除和清除标签操作，分别说明如下：

1）清除标签

在radix树中清除一个标签包括向下遍历树、查找定位条目和清除条目标签的操作。只要孩子结点没有打标签的条目，就可以向上遍历结点清除标签。结束条件是：如果遍历遇到一个结点，在清除一个标签后，它还有一个或多个条目带有标签集，就可以结束向上遍历。为了与向下遍历期间有同样的结束点，将终止条件改为：向上遍历将在有比清除标签数更多标签的结点处结束。这样，不论何时遇到这样的结点，将作为上遍历树的结束点。

2）删除元素

（5）radix树API说明

声明和初始化radix树 

声明和初始化radix树的方法列出如下：

#include
/* gfp_mask表示如何执行内存分配，如果操作（如：插入）以原子性上下文中执行，其值为GFP_ATOMIC*/
RADIX_TREE(name, gfp_mask); /* 声明和初始化名为name的树*/

插入条目 

插入条目的函数定义列出如下：

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

函数radix_tree_preload尝试用给定的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相关的条目，如果删除条目在树中，返回该条目的指针，否则返回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起查询树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);

（6）并行操作使用radix树API的方法

查询获取slot操作 

查询操作支持RCU无阻塞并行读操作，因此，需要遵循RCU的用法加RCU读锁，还需要将rcu_dereference()用于获得的slot，在写（或更新）操作时，需要给新的slot使用rcu_assign_pointer()。查询操作的使用方法列出如下：

查询修改slot操作 

Linux内核的radix树需要打补丁才支持并发修改。查询仅有一个全局状态：RCU静止状态，并发修改需要跟踪持有什么锁。锁状态对于操作来说必须是外部的，因此，我们需要实例化一个本地上下文跟踪这些锁。查询修改slot的方法列出如下：

struct page *slot;
DEFINE_RADIX_TREE_CONTEXT(ctx,&mapping->page_tree);
radix_tree_lock(&ctx); /锁住了根结点/
/

ctx.tree代替&mapping->page_tree作为根，可以传递上下文
slot = radix_tree_lookup_slot(tx.tree, index);
rcu_assign_pointer(*slot, new_page);
radix_tree_unlock(&ctx);

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树这些操作的实现。

未完，待续！