Linux中有着大量的红黑树的应用：

因此为了更好地了解内核，有必要对Linux内核中红黑树的实现进行分析，本次分析的内核源码版本为5.15.155。

内核源码中与红黑树定义有关的文件包括：/include/linux/rbtree.h、/include/linux/rbtree_augmented.h、/inclue/linux/rbtree_types.h、/lib/rbtree.c。本文将对这四个文件中的关键代码进行探索。

数据结构

  • rb_node是内核红黑树中最基础的数据结构, 用于表示红黑树节点。

    该结构包含四个信息：父节点指针、颜色、左子节点指针、右子节点指针，但是结构体中只有三个变量。由于指针通常是对齐的（例如，4字节或8字节对齐），最低有效位可以安全地用作存储其他信息而不影响指针的正确性，因此rbtree结构体将颜色信息嵌入到__rb_parent_color成员变量的最低有效位中，因此该变量中包含了父节点指针和颜色信息。

    1
    2
    3
    4
    5
    6
    struct rb_node {
        unsigned long  __rb_parent_color;
        struct rb_node *rb_right;
        struct rb_node *rb_left;
    } __attribute__((aligned(sizeof(long))));	//指定 rb_node 结构体的起始地址将按 `long` 类型的大小对齐。
    /* The alignment might seem pointless, but allegedly CRIS needs it */

    该结构体中没有key域，这是linux数据结构的一大特色，就是结构不包括数据，而是由数据和基本结构被包括在同一个struct中。如果我们需要创建一个结构体，并用红黑树进行组织，可以向如下代码这样组织：

    1
    2
    3
    4
    5
    struct mytype {
      struct rb_node node;
      char *keystring;
    };
    //linux的rbtree的功能是由多种接口组成,相比于我们c++的面向对象实现的红黑树或者其他数据结构，我们实现一个链表类都是将所有的功能完全的在一个类中实现，而对于linux(不过linux大部分源码都是c实现的，所以没有面向对象的思想)，则是写成很多的接口。至于写成接口的好处就是：当linux实现完链表的结构后，后面实现栈和队列的时候，可以不用赋值链表的源码或者在实现栈和队列时引用链表类，这里可以直接使用链表的接口。就可以大大缩减代码量和内存空间。

  • rb_root变量存储了根节点指针，用于表示一颗红黑树。

    1
    2
    3
    struct rb_root {
        struct rb_node *rb_node;
    };

  • struct rb_root_cached 是一个用来表示红黑树（Red-Black Tree）的结构体，并且它增加了一个缓存（rb_leftmost）来存储树中最左边的节点。

    通常，找到红黑树中的最小节点需要从根节点开始，调用rb_frist()沿着左子树一路遍历到最左边的叶子节点。而有了 rb_leftmost 指针后，可以直接通过这个指针访问最小节点，避免了每次查找时的遍历操作。

    1
    2
    3
    4
    struct rb_root_cached {
        struct rb_root rb_root;
        struct rb_node *rb_leftmost; //指向红黑树中最左边（也就是最小）的节点
    };

  • dummy_callbacks是一个包含占位符回调函数的结构体，这些回调函数目前都是空实现（什么都不做）。这些占位符通常在需要红黑树的增强功能（augmented red-black tree）的场景中被实际的逻辑所替换，例如更新某些附加信息。当前的空实现可以视为一个默认的、不需要任何额外操作的基础实现。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
    static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
    static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}

    static const struct rb_augment_callbacks dummy_callbacks = {
        .propagate = dummy_propagate,
        .copy = dummy_copy,
        .rotate = dummy_rotate
    };

辅助函数

辅助函数一般为宏定义，用于便捷地获取与设置红黑树节点的值。

  • rb_parent用于获取输入节点的父节点地址。由于父节点指针和颜色信息都存储在同一个字段中,所以需要通过位操作来分离出父节点指针。(r)->__rb_parent_color & ~3 可以将最后两个位（存储颜色信息）清零,得到的就是父节点指针的值。

    1
    #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

  • rb_color用于获取节点的颜色

    1
    2
    #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
    #define __rb_color(pc)     ((pc) & 1)

  • rb_is_red用于判断节点是否为红色, rb_is_black同理

    1
    2
    3
    #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
    #define __rb_is_red(pc)    (!__rb_color(pc))
    #define __rb_color(pc)     ((pc) & 1)

  • rb_red_parent从 __rb_parent_color 字段中提取当前节点的父节点指针,并检查父节点是否为红色。

    1
    2
    3
    4
    static inline struct rb_node *rb_red_parent(struct rb_node *red)
    {
    	return (struct rb_node *)red->__rb_parent_color;
    }

  • RB_EMPTY_ROOT用于判断节点是否为空

    1
    #define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)

    READ_ONCE 是一个内核级别的宏,它主要用于确保在多线程/多核环境下安全地读取一个变量的值。
    在多线程/多核环境下,一个变量可能会被多个线程/CPU同时访问和修改。如果不采取特殊措施,编译器可能会对变量的访问进行优化,导致读取到不正确的值。
    READ_ONCE 宏能够禁止编译器对变量的访问进行优化,确保每次读取都是从内存中直接获取变量的最新值,而不是使用寄存器中缓存的旧值。

  • rb_set_parent用于设置parent节点, rb_set_parent_color用于设置parent节点与当前节点的颜色.

    1
    2
    3
    4
    static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
    {
        rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
    }
    1
    2
    3
    4
    5
    static inline void rb_set_parent_color(struct rb_node *rb,
                           struct rb_node *p, int color)
    {
        rb->__rb_parent_color = (unsigned long)p | color;
    }

  • rb_link_node用于将新节点插入树中，把parent设为node的父结点，并且让rb_link指向node。

  • static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
                struct rb_node **rb_link)
{
    node->__rb_parent_color = (unsigned long)parent;
    node->rb_left = node->rb_right = NULL;

    *rb_link = node;
}

    1
    2
    3
    4
    5

    * `rb_entry`用于返回包含红黑树节点的结构体。由于红黑树节点中并不包含key，因此需要`rb_entry`来返回包含key和rb_node的结构体。`container_of` 宏是 Linux 内核中常用的一个宏，用于从结构体中的一个成员指针推导出包含该成员的结构体指针。

      ```c
      #define	rb_entry(ptr, type, member) container_of(ptr, type, member)

红黑树操作

遍历

红黑树的遍历方式与其他二叉树的遍历方式大致相同。Linux内核中对于红黑树的遍历实现了两种顺序：后序遍历与中序遍历。

  • 后序遍历

    • rb_first_postorder返回后序遍历中的第一个节点

      1
      2
      3
      4
      5
      6
      7
      8
      struct rb_node *rb_first_postorder(const struct rb_root *root)
      {
          if (!root->rb_node)
              return NULL;

          return rb_left_deepest_node(root->rb_node);
      }
      EXPORT_SYMBOL(rb_first_postorder);

      • rb_next_postorder返回后序遍历中输入节点的下一个节点

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        struct rb_node *rb_next_postorder(const struct rb_node *node)
        {
            const struct rb_node *parent;
            if (!node)
                return NULL;
            parent = rb_parent(node);

            /* If we're sitting on node, we've already seen our children */
            if (parent && node == parent->rb_left && parent->rb_right) {
                /* If we are the parent's left node, go to the parent's right
                 * node then all the way down to the left */
                return rb_left_deepest_node(parent->rb_right);
            } else
                /* Otherwise we are the parent's right node, and the parent
                 * should be next */
                return (struct rb_node *)parent;
        }
        EXPORT_SYMBOL(rb_next_postorder);

      • rb_left_deepest_node返回最深且位于最左端的节点, 即后序遍历中的第一个节点

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
        {
            for (;;) {
                if (node->rb_left)
                    node = node->rb_left;
                else if (node->rb_right)
                    node = node->rb_right;
                else
                    return (struct rb_node *)node;
            }
        }

  • 中序遍历

    • rb_last返回中序遍历中的最后一个节点

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      struct rb_node *rb_last(const struct rb_root *root)
          {
          struct rb_node	*n;

          n = root->rb_node;
          if (!n)
              return NULL;
          while (n->rb_right)
              n = n->rb_right;
          return n;
      }
      EXPORT_SYMBOL(rb_last);

    • rb_first返回中序遍历中的第一个节点

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      struct rb_node *rb_first(const struct rb_root *root)
      {
          struct rb_node	*n;

          n = root->rb_node;
          if (!n)
              return NULL;
          while (n->rb_left)
              n = n->rb_left;
          return n;
      }
      EXPORT_SYMBOL(rb_first);

    • rb_next返回指定节点中序遍历中的下一个节点, 即后继节点

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      struct rb_node *rb_next(const struct rb_node *node)
      {
          struct rb_node *parent;

          if (RB_EMPTY_NODE(node))
              return NULL;

          /*
           * If we have a right-hand child, go down and then left as far
           * as we can.
           */
          if (node->rb_right) {
              node = node->rb_right;
              while (node->rb_left)
                  node = node->rb_left;
              return (struct rb_node *)node;
          }

          /*
           * No right-hand children. Everything down and left is smaller than us,
           * so any 'next' node must be in the general direction of our parent.
           * Go up the tree; any time the ancestor is a right-hand child of its
           * parent, keep going up. First time it's a left-hand child of its
           * parent, said parent is our 'next' node.
           */
          while ((parent = rb_parent(node)) && node == parent->rb_right)
              node = parent;

          return parent;
      }
      EXPORT_SYMBOL(rb_next);

    • rb_prev返回指定节点中序遍历中的上一个节点, 即前驱节点

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      struct rb_node *rb_prev(const struct rb_node *node)
      {
          struct rb_node *parent;

          if (RB_EMPTY_NODE(node))
              return NULL;

          /*
           * If we have a left-hand child, go down and then right as far
           * as we can.
           */
          if (node->rb_left) {
              node = node->rb_left;
              while (node->rb_right)
                  node = node->rb_right;
              return (struct rb_node *)node;
          }

          /*
           * No left-hand children. Go up till we find an ancestor which
           * is a right-hand child of its parent.
           */
          while ((parent = rb_parent(node)) && node == parent->rb_left)
              node = parent;

          return parent;
      }
      EXPORT_SYMBOL(rb_prev);

查找

内核中遍历的具体实现方式有两种：

第一种是使用内核内部实现的查找函数, 由于内核红黑树的节点结构体中并不包含key，因此在实现查找操作时需要自定义cmp函数。内核中的查找函数如下：

  • rb_next_match用于判断下一个节点是否包含指定key, 若包含key则返回该节点指针, 否则返回空NULL

    1
    2
    3
    4
    5
    6
    7
    8
    9
    static __always_inline struct rb_node *
    rb_next_match(const void *key, struct rb_node *node,
              int (*cmp)(const void *key, const struct rb_node *))
    {
        node = rb_next(node);
        if (node && cmp(key, node))
            node = NULL;
        return node;
    }

  • rb_find_first返回红黑树中第一个包含指定key的节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    /**
     * rb_find_first() - find the first @key in @tree
     * @key: key to match
     * @tree: tree to search
     * @cmp: operator defining node order
     *
     * Returns the leftmost node matching @key, or NULL.
     */
    static __always_inline struct rb_node *
    rb_find_first(const void *key, const struct rb_root *tree,
              int (*cmp)(const void *key, const struct rb_node *))
    {
        struct rb_node *node = tree->rb_node;
        struct rb_node *match = NULL;

        while (node) {
            int c = cmp(key, node);

            if (c <= 0) {
                if (!c)
                    match = node;
                node = node->rb_left;
            } else if (c > 0) {
                node = node->rb_right;
            }
        }

        return match;
    }

  • rb_for_each通过rb_find_first与rb_next_match来遍历所有包含指定key的节点

    1
    2
    3
    #define rb_for_each(node, key, tree, cmp) \
        for ((node) = rb_find_first((key), (tree), (cmp)); \
             (node); (node) = rb_next_match((key), (node), (cmp)))

如/kernel/sched/core.c所示，其定义了rb_sched_core_cmp比较函数并作为函数指针传入了rb_find_first中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
 * Find left-most (aka, highest priority) task matching @cookie.
 */
static struct task_struct *sched_core_find(struct rq *rq, unsigned long cookie)
{
	struct rb_node *node;

	node = rb_find_first((void *)cookie, &rq->core_tree, rb_sched_core_cmp);
	/*
	 * The idle task always matches any cookie!
	 */
	if (!node)
		return idle_sched_class.pick_task(rq);

	return __node_2_sc(node);
}

static inline int rb_sched_core_cmp(const void *key, const struct rb_node *node)
{
	const struct task_struct *p = __node_2_sc(node);
	unsigned long cookie = (unsigned long)key;

	if (cookie < p->core_cookie)
		return -1;

	if (cookie > p->core_cookie)
		return 1;

	return 0;
}

#define __node_2_sc(node) rb_entry((node), struct task_struct, core_node)

第二种为不调用上述遍历函数，自己通过while循环实现遍历，如/mm/vmalloc.c所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static struct vmap_area *__find_vmap_area(unsigned long addr)
{
	struct rb_node *n = vmap_area_root.rb_node;

	while (n) {
		struct vmap_area *va;

		va = rb_entry(n, struct vmap_area, rb_node);
		if (addr < va->va_start)
			n = n->rb_left;
		else if (addr >= va->va_end)
			n = n->rb_right;
		else
			return va;
	}

	return NULL;
}

替换

  • rb_replace_node 是一个同步操作,它会直接修改红黑树的结构,并确保整个过程是原子性的。适用于单线程或者独占访问红黑树的情况,因为它可以快速完成节点替换。由于是同步操作,在高并发场景下可能会导致性能瓶颈。

    源码如下所示，victim为被替换的节点，new为需要替换的节点。首先找出victim的父节点，然后将victim节点的内容（颜色，父、儿子节点指针）复制到new中，将victim子节点的父节点指针指向new节点，最后调用__rb_change_child函数将parent的子节点指针指向的old替换为new。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void rb_replace_node(struct rb_node *victim, struct rb_node *new,
                 struct rb_root *root)
    {
        struct rb_node *parent = rb_parent(victim);

        /* Copy the pointers/colour from the victim to the replacement */
        *new = *victim;

        /* Set the surrounding nodes to point to the replacement */
        if (victim->rb_left)
            rb_set_parent(victim->rb_left, new);
        if (victim->rb_right)
            rb_set_parent(victim->rb_right, new);
        __rb_change_child(victim, new, parent, root);
    }
    EXPORT_SYMBOL(rb_replace_node);

    为了解决高并发场景下的性能瓶颈，linux内核提供了另一个替换函数：rb_replace_node_rcu。rb_replace_node_rcu 则是一种基于 RCU（Read-Copy-Update）机制的替换操作,它可以在不阻塞读取操作的情况下替换节点。

  • rb_replace_node_cached是rb_replace_node的cached版本，其主要的功能是维护rb_root_cached结构体中的leftmost节点。其首先判断被替换的节点是否为leftmost节点，若是，则更新rb_root_cached结构体中的rb_leftmost变量，最后调用rb_replace_node，进行替换。

    1
    2
    3
    4
    5
    6
    7
    8
    static inline void rb_replace_node_cached(struct rb_node *victim,
                          struct rb_node *new,
                          struct rb_root_cached *root)
    {
        if (root->rb_leftmost == victim)
            root->rb_leftmost = new;
        rb_replace_node(victim, new, &root->rb_root);
    }

旋转

红黑树中的旋转操作流程如下所示，代码中以兄弟节点为轴，向左旋转：

  1. 以兄弟节点为轴；

  2. 调用两次WRITE_ONCE将父节点的右子节点替换为兄弟节点的左子节点，将兄弟节点的左子节点替换为父节点；

  3. 调用rb_set_parent_color将兄弟节点的左子节点的parent指针指向父节点，并染为黑色；

  4. 调用__rb_rotate_set_parents将兄弟节点的parent指针指向祖父节点并染成与父节点相同的颜色，将父节点的parent指针指向兄弟节点并染成红色，将祖父节点的子节点指针指向兄弟节点。

1
2
3
4
5
6
7
8
9
10
11
12
/*
*     P               S
*    / \             / \
*   N   s    -->    p   Sr
*      / \         / \
*     Sl  Sr      N   Sl
*/
tmp1 = sibling->rb_left;
WRITE_ONCE(parent->rb_right, tmp1);
WRITE_ONCE(sibling->rb_left, parent);
rb_set_parent_color(tmp1, parent, RB_BLACK);
__rb_rotate_set_parents(parent, sibling, root, RB_RED);

__rb_rotate_set_parents函数首先找到old节点的父节点parent，将old节点的父指针与颜色信息复制到new节点中，调用rb_set_parent_color将old节点的父指针指向new节点、颜色设置为color，最后调用__rb_change_child将parent的子节点指针指向的old替换为new。

1
2
3
4
5
6
7
8
9
static inline void
__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
			struct rb_root *root, int color)
{
	struct rb_node *parent = rb_parent(old);
	new->__rb_parent_color = old->__rb_parent_color;
	rb_set_parent_color(old, new, color);
	__rb_change_child(old, new, parent, root);
}

插入

  • rb_add是在红黑树中插入节点的接口。首先调用while循环找到要插入的位置，调用rb_link_node将node节点插入红黑树中, 最后调用rb_insert_color对红黑树进行平衡。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    static __always_inline void
    rb_add(struct rb_node *node, struct rb_root *tree,
           bool (*less)(struct rb_node *, const struct rb_node *))
    {
        struct rb_node **link = &tree->rb_node;
        struct rb_node *parent = NULL;

        while (*link) {
            parent = *link;
            if (less(node, parent))
                link = &parent->rb_left;
            else
                link = &parent->rb_right;
        }

        rb_link_node(node, parent, link);
        rb_insert_color(node, tree);
    }

    rb_insert_color用于向插入节点添加颜色，其作为外部访问的接口, 调用内部的__rb_inset函数.

    1
    2
    3
    4
    5
    void rb_insert_color(struct rb_node *node, struct rb_root *root)
    {
        __rb_insert(node, root, dummy_rotate);
    }
    EXPORT_SYMBOL(rb_insert_color);

  • rb_add_cached是rb_add的cached版本。首先调用while循环找到要插入的位置, 并判断插入节点是否为leftmost节点，调用rb_link_node将node节点插入红黑树中, 最后调用rb_insert_color_cached对红黑树进行平衡。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    static __always_inline struct rb_node *
    rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
              bool (*less)(struct rb_node *, const struct rb_node *))
    {
        struct rb_node **link = &tree->rb_root.rb_node;
        struct rb_node *parent = NULL;
        bool leftmost = true;

        while (*link) {
            parent = *link;
            if (less(node, parent)) {
                link = &parent->rb_left;
            } else {
                link = &parent->rb_right;
                leftmost = false;
            }
        }

        rb_link_node(node, parent, link);
        rb_insert_color_cached(node, tree, leftmost);

        return leftmost ? node : NULL;
    }

    rb_insert_color_cached是rb_insert_color的cached版本，其主要的功能是维护rb_root_cached结构体中的leftmost节点。其首先判断插入的节点是否为leftmost节点，若是，则更新rb_root_cached结构体中的rb_leftmost变量，最后调用rb_insert_color，进行插入。

    1
    2
    3
    4
    5
    6
    7
    8
    static inline void rb_insert_color_cached(struct rb_node *node,
                          struct rb_root_cached *root,
                          bool leftmost)
    {
        if (leftmost)
            root->rb_leftmost = node;
        rb_insert_color(node, &root->rb_root);
    }

__rb_insert是插入操作的主要函数，它的处理逻辑如下：

  • 若父节点为空, 则表明插入节点为根节点, 无需其他操作;

  • 若父节点为黑色, 则无需其他操作直接插入;

  • 若父节点为红色：

    • 父节点为祖父节点的左子节点
      • 插入节点为父节点的左子节点
        • 叔节点为红色，父叔变黑，祖父变红
        • 叔节点为黑色，将子节点与父、祖父节点处于同意方向，父节点向叔节点方向进行旋转
      • 插入节点为父节点的右子节点
        • 叔节点为红色
        • 叔节点为黑色
    • 父节点为祖父节点的右子节点
      • 插入节点为父节点的右子节点
        • 叔节点为红色
        • 叔节点为黑色
      • 插入节点为父节点的左子节点
        • 叔节点为红色
        • 叔节点为黑色
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;	//声明三个节点变量-parent,gparent,tmp

	while (true) {
		//情况1：插入节点为根节点
		if (unlikely(!parent)) {
			
			rb_set_parent_color(node, NULL, RB_BLACK);
			break;
		}

		//情况2：插入节点的父节点为黑色
		if(rb_is_black(parent))
			break;
		
        //情况3：插入节点的父节点为红色
		gparent = rb_red_parent(parent);

		tmp = gparent->rb_right;	//此时tmp为叔节点
		if (parent != tmp) {	//父节点为祖父节点的左子节点
			if (tmp && rb_is_red(tmp)) {	
				/*
				 * Case 1 - 叔节点为红色
				 *
				 *       G            g
				 *      / \          / \
				 *     p   u  -->   P   U
				 *    /            /
				 *   n            n
				 *
				 * However, since g's parent might be red, and
				 * 4) does not allow this, we need to recurse
				 * at g.
				 */
				rb_set_parent_color(tmp, gparent, RB_BLACK);	//叔节点变为黑色
				rb_set_parent_color(parent, gparent, RB_BLACK);	//父节点变为黑色
				node = gparent;
				parent = rb_parent(node);
				rb_set_parent_color(node, parent, RB_RED);		//祖父节点变为红色
                //此时祖父节点为红色，其父节点可能也为红色，需要将node指向祖父节点继续循环处理
				continue;
			}
            
			tmp = parent->rb_right;		//此时，tmp指向父节点的右子节点
			if (node == tmp) {			//判断插入节点是否为父节点的右子节点
				/*
				 * Case 2 - 叔节点为黑色，插入节点为父节点的右子节点
				 *
				 *      G             G
				 *     / \           / \
				 *    p   U  -->    n   U
				 *     \           /
				 *      n         p
				 *
				 * 此时变成Case 3，进入Case 3的处理流程
				 */
				tmp = node->rb_left;	//此时，tmp指向子节点的左子节点
                //进行左旋操作
				WRITE_ONCE(parent->rb_right, tmp);
				WRITE_ONCE(node->rb_left, parent);
				if (tmp)	//如果子节点的左子节点存在，则将其parent指针指向父节点，并变成黑色
					rb_set_parent_color(tmp, parent, RB_BLACK);		
				rb_set_parent_color(parent, node, RB_RED);		//将父节点parent指针指向node，将parent染为红色
				augment_rotate(parent, node);		//调用rotate回调函数，增强型红黑树中才会使用
				parent = node;			//parent节点变为node
				tmp = node->rb_right;	//将tmp恢复为父节点的右子节点
			}

			/*
			 * Case 3 - 叔节点为黑色，插入节点为父节点的左子节点
			 *
			 *        G           P
			 *       / \         / \
			 *      p   U  -->  n   g
			 *     /                 \
			 *    n                   U
			 */
           //进行右旋操作
			WRITE_ONCE(gparent->rb_left, tmp);
			WRITE_ONCE(parent->rb_right, gparent);
			if (tmp)	//如果父节点的右子节点存在，则将其父节点指针指向gparent，并变成黑色
				rb_set_parent_color(tmp, gparent, RB_BLACK);
            //将父节点的parent指针指向祖父节点的父节点，并染成祖父节点的颜色；将祖父节点的parent指针指向父节点，并染成红色
			__rb_rotate_set_parents(gparent, parent, root, RB_RED);	
			augment_rotate(gparent, parent);		//调用rotate回调函数
			break;
		} else {
			//父节点为祖父节点的右子节点的情况，与上述步骤类似，不重复描述
	}
}

删除

  • rb_erase调用__rb_erase_augmented将指定节点删除，并返回红黑树是否需要重新平衡。如果需要，则调用____rb_erase_color。在这里调用了增强版红黑树的接口__rb_erase_augmented，但由于传入的回调函数指针为dummy_rotate，因此体现不出增强性质。

    1
    2
    3
    4
    5
    6
    7
    8
    void rb_erase(struct rb_node *node, struct rb_root *root)
    {
        struct rb_node *rebalance;
        rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
        if (rebalance)
            ____rb_erase_color(rebalance, root, dummy_rotate);
    }
    EXPORT_SYMBOL(rb_erase);

  • rb_erase_cached为rb_erase的cached版本，其主要的功能是维护rb_root_cached结构体中的leftmost节点。其首先判断需要删除的节点是否为当前红黑树的leftmost节点，如果是，则调用rb_next()将leftmost节点更新为其后继节点，再调用rb_erase进行删除。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    static inline struct rb_node *
    rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
    {
        struct rb_node *leftmost = NULL;

        if (root->rb_leftmost == node)
            leftmost = root->rb_leftmost = rb_next(node);

        rb_erase(node, &root->rb_root);
    }

__rb_erase_color调用__rb_erase_color函数。

1
2
3
4
5
6
7
/* Non-inline version for rb_erase_augmented() use */
void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	____rb_erase_color(parent, root, augment_rotate);
}
EXPORT_SYMBOL(__rb_erase_color);

__rb_erase_color是对删除后的节点进行染色的主要函数。其染色逻辑如下：

  • 兄弟节点为红：以父节点为轴，向左方向旋转，再进行染色；
  • 兄弟节点为黑：
    • 兄弟节点的右子节点为黑：
      • 兄弟节点的左子节为黑：兄弟节点变红。若父节点为红，父节点变黑，完成染色；若父节点为黑，上移至祖父节点继续染色；
      • 兄弟节点的左子节为红：以兄弟节点为轴，向右旋转，变为兄弟节点的右子节点为红的情况；
    • 兄弟节点的右子节点为红：兄弟节点变为父节点的颜色，父节点变黑，右子节点变黑，以父节点为轴，向左旋转。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;

	while (true) {
		/*
		 * Loop invariants:
		 * - node is black (or NULL on first iteration)
		 * - node is not the root (parent is not NULL)
		 * - All leaf paths going through parent and node have a
		 *   black node count that is 1 lower than other leaf paths.
		 */
		sibling = parent->rb_right;
		if (node != sibling) {	/* node为parent的左子节点 */
			if (rb_is_red(sibling)) {
				/*
				 * Case 1 - 兄弟节点为红色，进行左旋
				 * 小写字母代表红色，大写字母代表黑色
				 *
				 *     P               S
				 *    / \             / \
				 *   N   s    -->    p   Sr
				 *      / \         / \
				 *     Sl  Sr      N   Sl
				 */
				tmp1 = sibling->rb_left;
				WRITE_ONCE(parent->rb_right, tmp1);
				WRITE_ONCE(sibling->rb_left, parent);
				rb_set_parent_color(tmp1, parent, RB_BLACK);
				__rb_rotate_set_parents(parent, sibling, root,
							RB_RED);	//旋转后兄弟节点变为parent的颜色，parent变为红色，
				augment_rotate(parent, sibling);
				sibling = tmp1;		//旋转后变更兄弟节点，继续判断
			}
            //兄弟节点为黑
			tmp1 = sibling->rb_right;
			if (!tmp1 || rb_is_black(tmp1)) {	//兄弟节点的右子节点为黑
				tmp2 = sibling->rb_left;
				if (!tmp2 || rb_is_black(tmp2)) {	//兄弟节点的左子节点为黑
					/*
					 * Case 2 - 兄弟节点为黑，子节点均为黑
					 * 进行颜色翻转
					 * (p)表示p可以为任意颜色
					 *
					 *    (p)           (p)
					 *    / \           / \
					 *   N   S    -->  N   s
					 *      / \           / \
					 *     Sl  Sr        Sl  Sr
					 *
					 */
					rb_set_parent_color(sibling, parent, RB_RED); //将兄弟节点变为红色
					if (rb_is_red(parent))	//父节点为红，则将父节点变为黑色
						rb_set_black(parent);
					else {					//父节点为黑
						node = parent;
						parent = rb_parent(node);	//将父节点切换为祖父节点，继续进行判断
						if (parent)
							continue;
					}
					break;
				}
				/*
				 * Case 3 - 兄弟节点为黑，左子节点为红，右子节点为黑
				 * 以兄弟节点为轴右旋
				 *
				 *   (p)           (p)
				 *   / \           / \
				 *  N   S    -->  N   sl
				 *     / \             \
				 *    sl  Sr            S
				 *                       \
				 *                        Sr
				 */
				tmp1 = tmp2->rb_right;
				WRITE_ONCE(sibling->rb_left, tmp1);
				WRITE_ONCE(tmp2->rb_right, sibling);
				WRITE_ONCE(parent->rb_right, tmp2);
				if (tmp1)
					rb_set_parent_color(tmp1, sibling,
							    RB_BLACK);
				augment_rotate(sibling, tmp2);
				tmp1 = sibling;
				sibling = tmp2;
			}
			/*
			 * Case 4 - 兄弟节点为黑，右子节点为红，左子节点为任意颜色
			 *	以父节点为轴左旋 + 颜色翻转
			 *
			 *      (p)             (s)
			 *      / \             / \
			 *     N   S     -->   P   Sr
			 *        / \         / \
			 *      (sl) sr      N  (sl)
			 */
			tmp2 = sibling->rb_left;
			WRITE_ONCE(parent->rb_right, tmp2);
			WRITE_ONCE(sibling->rb_left, parent);
			rb_set_parent_color(tmp1, sibling, RB_BLACK);
			if (tmp2)
				rb_set_parent(tmp2, parent);
			__rb_rotate_set_parents(parent, sibling, root,
						RB_BLACK);
			augment_rotate(parent, sibling);
			break;
		} else {
			//父节点为祖父节点的右子节点的情况，与上述步骤类似，不重复描述
	}
}

红黑树增强版

内核中的红黑树实现了增强的接口，称之为Augmented rbtrees。增强版红黑树在每个节点中存储了一些附加的数据，其中节点N的附加数据为以节点N为根节点的子树中所有节点内容的函数。想要使用增强版红黑树，在插入和删除结点时必须调用增强型接口并提供增强型回调函数。

  • 插入节点时，用户必须更新通往被插入节点的路径上的增强信息，然后像往常一样调用rb_link_node()。增强版插入接口是rb_augment_inserted()而不是平时的rb_insert_color()。如果 rb_augment_inserted()再平衡了红黑树，它将回调至一个用户提供的函数来更新受影响的子树上的增强信息。

  • 删除节点时，用户必须调用rb_erase_augmented()而不是rb_erase()。 rb_erase_augmented()回调一个用户提供的函数来更新受影响的子树上的增强信息。

在上述情况下，回调都是通过rb_augment_callbacks结构体提供的。增强版红黑树必须定义3个回调：

  • 一个传播回调propagate，它更新一个给定结点和它的祖先们的增强数据，直到一个给定的停止点 （如果是NULL，将更新一路更新到树根）。
  • 一个复制回调copy，它将一颗给定子树的增强数据复制到一个新指定的子树树根。
  • 一个树旋转回调rotate，它将一颗给定的子树的增强值复制到新指定的子树树根上，并重新计算 先前的子树树根的增强值。
1
2
3
4
5
struct rb_augment_callbacks {
    void (*propagate)(struct rb_node *node, struct rb_node *stop);
    void (*copy)(struct rb_node *old, struct rb_node *new);
    void (*rotate)(struct rb_node *old, struct rb_node *new);
};

插入

  • rb_insert_augmented调用__rb_insert_augmented

    1
    2
    3
    4
    5
    6
    static inline void
    rb_insert_augmented(struct rb_node *node, struct rb_root *root,
                const struct rb_augment_callbacks *augment)
    {
        __rb_insert_augmented(node, root, augment->rotate);
    }

  • rb_insert_augmented_cached将插入节点替换为了rb_root_cached结构体中的rb_leftmost节点，即中序遍历中最小的点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    static inline void
    rb_insert_augmented_cached(struct rb_node *node,
                   struct rb_root_cached *root, bool newleft,
                   const struct rb_augment_callbacks *augment)
    {
        if (newleft)
            root->rb_leftmost = node;
        rb_insert_augmented(node, &root->rb_root, augment);
    }

__rb_insert_augmented调用了普通红黑树的插入操作__rb_insert，与普通红黑树插入操作不同的是，增强版插入用augment_rotate替代dummy_rotate作为回调函数。

1
2
3
4
5
void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
	__rb_insert(node, root, augment_rotate);
}

删除

  • rb_erase_augmented首先调用__rb_erase_augmented函数删除节点，并返回是否需要重新平衡。若需要重新平衡，则调用__rb_erase_color函数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    static __always_inline void
    rb_erase_augmented(struct rb_node *node, struct rb_root *root,
               const struct rb_augment_callbacks *augment)
    {
        struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
        if (rebalance)
            __rb_erase_color(rebalance, root, augment->rotate);
    }

  • rb_erase_augmented_cached是rb_erase_augmented的cached版本，使用rb_root_cached结构体来获取红黑树中key值最小的节点。

    1
    2
    3
    4
    5
    6
    7
    8
    static __always_inline void
    rb_erase_augmented_cached(struct rb_node *node, struct rb_root_cached *root,
                  const struct rb_augment_callbacks *augment)
    {
        if (root->rb_leftmost == node)
            root->rb_leftmost = rb_next(node);
        rb_erase_augmented(node, &root->rb_root, augment);
    }

__rb_erase_augmented实现了指定节点的删除，其删除逻辑如下：

  • 若删除的节点没有子节点，直接删除，需要根据删除节点的颜色判断是否需要重新平衡红黑树；
  • 若删除的节点只有一个子节点（其本身一定为黑，子节点一定为红），则直接用其子节点替代它本身，不需要重新平衡红黑树；
  • 若删除的节点有两个子节点，则找出中序遍历顺序中它的后继节点并代替它本身，具体流程如下：
    • 若其右子节点没有左子节点，则直接用右子节点代替需要删除的节点；
    • 若其右子节点有左子节点，则调用while循环找出右子树中的leftmost节点，用leftmost节点替换需要删除的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
static __always_inline struct rb_node *
__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
		     const struct rb_augment_callbacks *augment)
{
	struct rb_node *child = node->rb_right;	//删除节点的右子节点
	struct rb_node *tmp = node->rb_left;	//删除节点的左子节点
	struct rb_node *parent, *rebalance;		//parent为删除节点的父节点，rebalance为需要进行染色操作的节点
	unsigned long pc;	//parent_color

	if (!tmp) {
		/*
		 * node只有一个右子节点或没有子节点
		 *
		 * 如果只有一个子节点，那子节点一定是红色的，他本身一定是黑色的
		 */
		pc = node->__rb_parent_color;
		parent = __rb_parent(pc);
		__rb_change_child(node, child, parent, root);
		if (child) {
            //存在右子节点，直接用右子节点替换其本身，不需要重新平衡
			child->__rb_parent_color = pc;
			rebalance = NULL;
		} else
            //没有子节点的情况。若删除节点为黑色，需要重新平衡；若为红色，不需要重新平衡
			rebalance = __rb_is_black(pc) ? parent : NULL;
		tmp = parent;
	} else if (!child) {
		/* node只有一个左子节点 */
		tmp->__rb_parent_color = pc = node->__rb_parent_color;
		parent = __rb_parent(pc);
		__rb_change_child(node, tmp, parent, root);
		rebalance = NULL;	
		tmp = parent;
	} else {
        /* node有两个子节点， */
		struct rb_node *successor = child, *child2;

		tmp = child->rb_left;
		if (!tmp) {
			/*
			 * node的后继节点为它的右子节点
			 *
			 *    (n)          (s)
			 *    / \          / \
			 *  (x) (s)  ->  (x) (c)
			 *        \
			 *        (c)
			 */
			parent = successor;
			child2 = successor->rb_right;

			augment->copy(node, successor);
		} else {
			/*
			 * node的后继节点为右子树的leftmost节点
			 *
			 *    (n)          (s)
			 *    / \          / \
			 *  (x) (y)  ->  (x) (y)
			 *      /            /
			 *    (p)          (p)
			 *    /            /
			 *  (s)          (c)
			 *    \
			 *    (c)
			 */
			do {
				parent = successor;
				successor = tmp;
				tmp = tmp->rb_left;
			} while (tmp);	//找到右子树的leftmost节点
            
            //由于leftmost节点没有左子节点，因此直接用leftmost节点的右子节点替换它本身。
			child2 = successor->rb_right;
			WRITE_ONCE(parent->rb_left, child2);
			WRITE_ONCE(successor->rb_right, child);
			rb_set_parent(child, successor);

			augment->copy(node, successor);
			augment->propagate(parent, successor);
		}
		//用leftmost节点替换node节点
		tmp = node->rb_left;
		WRITE_ONCE(successor->rb_left, tmp);
		rb_set_parent(tmp, successor);

		pc = node->__rb_parent_color;
		tmp = __rb_parent(pc);
		__rb_change_child(node, successor, tmp, root);

		if (child2) {
            //leftmost的右子节点存在，此时右子节点一定为红色，将右子节点染为黑色，不需要重新平衡红黑树
			rb_set_parent_color(child2, parent, RB_BLACK);
			rebalance = NULL;
		} else {
            //leftmost的右子节点不存在，如果leftmost节点为黑色，需要重新平衡红黑树，如果为红色，则不需要。
			rebalance = rb_is_black(successor) ? parent : NULL;
		}
		successor->__rb_parent_color = pc;
		tmp = successor;
	}

    //结束删除操作，调用propagate，函数返回。
	augment->propagate(tmp, NULL);
	return rebalance;
}

使用案例

一种增强型红黑树的使用案例为区间树（线段树），定义在/include/linux/interval_tree.h中。

区间树在内核中的使用场景有以下几个：

经典的红黑树只有一个键，它不能直接用来存储像[lo:hi]这样的区间范围，也不能快速查找与新的[lo:hi]重叠的部分，或者查找是否有与新的[lo:hi]完全匹配的部分。

然而，内核通过增强型红黑树，以一种结构化的方式来存储这种区间范围，使得高效的查找和精确匹配成为可能。

其他

WRITE_ONCE

WRITE_ONCE 是一个用于确保对变量进行一次性写操作的宏，是对volatile和内存屏障的封装。WRITE_ONCE 的用处是对变量赋值，它的目的是避免编译器优化对变量的写操作，从而确保写操作的有序性、原子性和可见性，特别是在多线程环境中。

编译器在优化代码的时候，会对一些操作进行重排序，或者删掉一些它认为无用的操作。这些优化在单线程的环境下不存在问题，但是对于操作系统而言，时刻都存在着并行的计算，这样的乱序处理很可能会造成问题。为了保证代码之间不乱序，我们可以使用READ_ONCE()和WRITE_ONCE()宏，告知编译器涉及到的操作之间不能乱序。

WRITE_ONCE的宏定义位于/tools/include/linux/compiler.h，其运行流程如下：

  1. ({ ... }): 这是一个GNU扩展的语法块（statement expression），允许在块的最后返回一个值。这个语法在标准C中并不支持，但在GCC等编译器中是可以使用的。它是用于代替do { ... } while (0)表达式的。

  2. union { typeof(x) __val; char __c[1]; } __u = { .__val = (val) };定义联合__u, 通过这种联合，可以在不改变底层数据的情况下，将 __val 解释成一个字符数组 __c。虽然数组长度为1，但它实际目的是指向联合的内存区域的起始位置，从而可以访问整个变量的字节。

  3. __write_once_size将 __u.__c（也就是 __val 按字节形式）写入到 x 的地址，并且写入的大小是 x 的大小。

  4. 最后，返回联合体中的 __val 成员的值，这样宏的返回值就是赋值后的 val。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define WRITE_ONCE(x, val)				\
({							\
	union { typeof(x) __val; char __c[1]; } __u =	\
		{ .__val = (val) }; 			\
	__write_once_size(&(x), __u.__c, sizeof(x));	\
	__u.__val;					\
})

static __always_inline void __write_once_size(volatile void *p, void *res, int size)
{
	switch (size) {
	case 1: *(volatile  __u8_alias_t *) p = *(__u8_alias_t  *) res; break;
	case 2: *(volatile __u16_alias_t *) p = *(__u16_alias_t *) res; break;
	case 4: *(volatile __u32_alias_t *) p = *(__u32_alias_t *) res; break;
	case 8: *(volatile __u64_alias_t *) p = *(__u64_alias_t *) res; break;
	default:
		barrier();	//内存屏障函数 barrier()，防止编译器对内存操作进行重排序。
		__builtin_memcpy((void *)p, (const void *)res, size);	//进行内存复制，将 res 指向的内容复制到 p 指向的地址
		barrier();	//再次调用内存屏障函数 barrier()，确保 memcpy 的操作不会被重排序。
	}
}

RCU

上文替换操作中的rb_replace_node()函数是一个同步操作,它会直接修改红黑树的结构,并确保整个过程是原子性的。适用于单线程或者独占访问红黑树的情况,因为它可以快速完成节点替换。由于是同步操作,在高并发场景下可能会导致性能瓶颈。

rb_replace_node_rcu 则是一种基于 RCU（Read-Copy-Update）机制的替换操作,它可以在不阻塞读取操作的情况下替换节点。适用于多线程并发访问红黑树的情况,它可以在不影响读取操作的情况下替换节点。由于引入了 RCU 机制,在高并发场景下性能会更好,但也增加了一定的复杂度。

RCU方法首先在新的位置插入新的节点,然后再将旧节点从树中删除。这样可以确保在删除旧节点之前,所有的读取操作都可以访问到正确的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
			 struct rb_root *root)
{
	struct rb_node *parent = rb_parent(victim);

	/* Copy the pointers/colour from the victim to the replacement */
	*new = *victim;

	/* Set the surrounding nodes to point to the replacement */
	if (victim->rb_left)
		rb_set_parent(victim->rb_left, new);
	if (victim->rb_right)
		rb_set_parent(victim->rb_right, new);

	/* Set the parent's pointer to the new node last after an RCU barrier
	 * so that the pointers onwards are seen to be set correctly when doing
	 * an RCU walk over the tree.
	 */
	__rb_change_child_rcu(victim, new, parent, root);
}
EXPORT_SYMBOL(rb_replace_node_rcu);

rb_replace_node()和rb_replace_node_rcu()的差异在于__rb_change_child()和__rb_change_child_rcu(), 而__rb_change_child()与__rb_change_child_rcu()的差异在于WRITE_ONCE和rcu_assign_pointer。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static inline void
__rb_change_child(struct rb_node *old, struct rb_node *new,
		  struct rb_node *parent, struct rb_root *root)
{
	if (parent) {
		if (parent->rb_left == old)
			WRITE_ONCE(parent->rb_left, new);
		else
			WRITE_ONCE(parent->rb_right, new);
	} else
		WRITE_ONCE(root->rb_node, new);
}

static inline void
__rb_change_child_rcu(struct rb_node *old, struct rb_node *new,
		      struct rb_node *parent, struct rb_root *root)
{
	if (parent) {
		if (parent->rb_left == old)
			rcu_assign_pointer(parent->rb_left, new);
		else
			rcu_assign_pointer(parent->rb_right, new);
	} else
		rcu_assign_pointer(root->rb_node, new);
}

rcu_assign_pointer的定义位于/include/linux/rcupdate.h，用于将v复制到p指向的内存地址。

  1. do { ... } while (0): 使用 do … while (0) 结构包裹宏定义，以确保宏在使用时的语法一致性和安全性。
  2. rcu_check_sparse(p, __rcu);: 调用 rcu_check_sparse 函数（或宏），检查 p 是否是一个合法的 RCU 指针。这一步通常用于静态代码分析或编译期检查，以确保类型安全。
  3. WRITE_ONCE((p), (typeof(p))(_r_a_p__v));: 如果 v 是一个编译时常量且等于 NULL，则使用 WRITE_ONCE 宏将 _r_a_p__v 的值写入 p，确保写操作的原子性和可见性。
  4. smp_store_release(&p, RCU_INITIALIZER((typeof(p))_r_a_p__v));: 使用 smp_store_release 函数（或内建函数）执行带有内存屏障的存储操作，将 RCU_INITIALIZER((typeof(p))_r_a_p__v) 的值写入 p。
    • RCU_INITIALIZER((typeof(p))_r_a_p__v): 是一个宏或函数，用于初始化 RCU 指针，确保指针的正确性。
    • smp_store_release(&p, ...): 确保存储操作在多处理器环境中是有序的，防止编译器和 CPU 重排序。
1
2
3
4
5
6
7
8
9
10
#define rcu_assign_pointer(p, v)					      \
do {									      \
	uintptr_t _r_a_p__v = (uintptr_t)(v);				      \
	rcu_check_sparse(p, __rcu);					      \
									      \
	if (__builtin_constant_p(v) && (_r_a_p__v) == (uintptr_t)NULL)	      \
		WRITE_ONCE((p), (typeof(p))(_r_a_p__v));		      \
	else								      \
		smp_store_release(&p, RCU_INITIALIZER((typeof(p))_r_a_p__v)); \
} while (0)

除rb_replace_node()外，rb_link_node函数也有RCU版本，rb_link_node直接对rb_link赋值node，而rb_link_node_rcu调用rcu_assign_pointer对rb_link进行赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
				struct rb_node **rb_link)
{
	node->__rb_parent_color = (unsigned long)parent;
	node->rb_left = node->rb_right = NULL;

	*rb_link = node;
}

static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,
				    struct rb_node **rb_link)
{
	node->__rb_parent_color = (unsigned long)parent;
	node->rb_left = node->rb_right = NULL;

	rcu_assign_pointer(*rb_link, node);
}

EXPORT_SYMBOL

EXPORT_SYMBOL()是宏定义，用于将内核符号导出到内核符号表中。EXPORT_SYMBOL() 定义的函数或者符号对全部内核代码公开，不用修改内核代码就可以在其它内核模块中直接调用，即使用 EXPORT_SYMBOL 可以将一个函数以符号的方式导出给其他模块使用。

其定义位于/inclue/linux/export.h中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define EXPORT_SYMBOL(sym)		_EXPORT_SYMBOL(sym, "")

#define _EXPORT_SYMBOL(sym, sec)	__EXPORT_SYMBOL(sym, sec, "")

#define ___EXPORT_SYMBOL(sym, sec, ns)						\
	extern typeof(sym) sym;							\
	extern const char __kstrtab_##sym[];					\
	extern const char __kstrtabns_##sym[];					\
	__CRC_SYMBOL(sym, sec);							\
	asm("	.section \"__ksymtab_strings\",\"aMS\",%progbits,1	\n"	\
	    "__kstrtab_" #sym ":					\n"	\
	    "	.asciz 	\"" #sym "\"					\n"	\
	    "__kstrtabns_" #sym ":					\n"	\
	    "	.asciz 	\"" ns "\"					\n"	\
	    "	.previous						\n");	\
	__KSYMTAB_ENTRY(sym, sec)


#define __KSYMTAB_ENTRY(sym, sec)					\
	static const struct kernel_symbol __ksymtab_##sym		\
	__attribute__((section("___ksymtab" sec "+" #sym), used))	\
	__aligned(sizeof(void *))					\
	= { (unsigned long)&sym, __kstrtab_##sym, __kstrtabns_##sym }

struct kernel_symbol {
	unsigned long value;
	const char *name;
	const char *namespace;
};

参考资料

Linux rbtree document

Linux rbtree document（中文）

红黑树(二)——linux 内核的设计实现

红黑树在内核的应用——timer定时器

do{…}while(0)的意义和用法

WRITE_ONCE与volatile

Why kernel code should use READ_ONCE and WRITE_ONCE for shared memory accesses

OI-wiki线段树