Linux kernel rb-tree (1)

本文主要目的是对 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);
// ...
}