本文主要目的是对 Linux kernel 中 rb-tree 有个初步印象,方便理解后面的文章
RB-TREE
// linux-5.4/lib/rb-tree.c
* red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
*
* 1) A node is either red or black
* 2) The root is black
* 3) All leaves (NULL) are black
* 4) Both children of every red node are black
* 5) Every simple path from root to leaves contains the same number
* of black nodes.
*
* 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
* consecutive red nodes in a path and every red node is therefore followed by
* a black. So if B is the number of black nodes on every simple path (as per
* 5), then the longest possible path due to 4 is 2B.
建议熟读并背诵
consecutive
CET6 TEM4
英 [kənˈsekjətɪv] 美 [kənˈsekjətɪv]
* adj. 连贯的;连续不断的
Data structures & Macros
// include/linux/rbtree_augmented.h
#define RB_RED 0
#define RB_BLACK 1
// linux-5.4/include/linux/rbtree.h
struct rb_root {
struct rb_node *rb_node;
};
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
#define RB_ROOT (struct rb_root) { NULL, }
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
建议手敲个十几遍,先记熟。
APIs
// include/linux/rbtree.h
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
struct rb_node ** rb_link)
extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);
Example
// include/linux/vmalloc.h
struct vmap_area {
unsigned long va_start;
unsigned long va_end;
unsigned long flags;
struct rb_node rb_node; /* address sorted rbtree */
// ...
};
struct vm_struct {
struct vm_struct *next;
void *addr;
unsigned long size;
unsigned long flags;
struct page **pages;
unsigned int nr_pages;
phys_addr_t phys_addr;
const void *caller;
};
// mm/vmalloc.c
static struct rb_root vmap_area_root = RB_ROOT;
static struct vmap_area *__find_vmap_area(unsigned long addr);
static void __insert_vmap_area(struct vmap_area *va);
static void __free_vmap_area(struct vmap_area *va);
// 搜索
static struct vmap_area *__find_vmap_area(unsigned long addr)
{
// 取 rb_root.rb_entry 地址
struct rb_node *n = vmap_area_root.rb_node;
// 遍历 rb_tree
while (n) {
struct vmap_area *va;
// 获取 rb_node 的container
va = rb_entry(n, struct vmap_area, rb_node);
// 比较目标值
if (addr < va->va_start)
n = n->rb_left;
else if (addr > va->va_start)
n = n->rb_right;
else
return va;
}
return NULL;
}
// 插入
static void __insert_vmap_area(struct vmap_area *va)
{
struct rb_node **p = &vmap_area_root.rb_node;
struct rb_node *parent = NULL;
struct rb_node *tmp;
// 遍历 rb_tree
while (*p) {
struct vmap_area *tmp_va;
parent = *p;
tmp_va = rb_entry(parent, struct vmap_area, rb_node);
// 比较,找到合适的插入位置
if (va->va_start < tmp_va->va_end)
p = &(*p)->rb_left;
else if (va->va_end > tmp_va->va_start)
p = &(*p)->rb_right;
else
BUG();
}
// 插入节点
rb_link_node(&va->rb_node, parent, p);
// 上色
rb_insert_color(&va->rb_node, &vmap_area_root);
//...
}
// 删除
static void __free_vmap_area(struct vmap_area *va){
// ...
rb_erase(&va->rb_node, &vmap_area_root);
// ...
}
// 创建节点
static struct vmap_area *alloc_vmap_area(unsigned long size,
unsigned long align,
unsigned long vstart, unsigned long vend,
int node, gfp_t gfp_mask)
{
struct vmap_area *va;
// ...
va = kmalloc_node(sizeof(struct vmap_area),
gfp_mask & GFP_RECLAIM_MASK, node);
// ...
va->va_start = addr;
va->va_end = addr + size;
va->flags = 0;
__insert_vmap_area(va);
// ...
}
网友评论