Red-Black Tree (rbtree)

커널에서 가장 널리 사용되는 자기 균형 이진 탐색 트리. rb_node/rb_root 구조체, 삽입·삭제·순회 API, rb_root_cached, 증강 rbtree, RCU-safe rbtree, Latched rbtree, CFS·VMA·hrtimer 활용 사례를 다룹니다.

1. 개요

Red-Black Tree(이하 rbtree)는 Linux 커널에서 가장 광범위하게 사용되는 자기 균형 이진 탐색 트리입니다. CFS 스케줄러의 태스크 정렬, VMA(가상 메모리 영역) 관리, hrtimer 타이머 큐, epoll 파일 디스크립터 관리 등 커널의 핵심 서브시스템 전반에 걸쳐 활용됩니다.

Red-Black Tree 5가지 속성

rbtree는 다음 5가지 불변 조건(invariant)을 항상 만족하는 이진 탐색 트리입니다:

1. 모든 노드는 빨간색(Red) 또는 검은색(Black)이다.
2. 루트 노드는 항상 검은색이다.
3. 모든 리프(NIL) 노드는 검은색이다. (NIL은 실제 노드가 아닌 논리적 자식)
4. 빨간 노드의 두 자식은 반드시 검은색이다. (연속된 빨간 노드 불가 — "No Red-Red" 규칙)
5. 임의의 노드에서 모든 리프(NIL)까지의 경로에 포함된 검은 노드 수가 동일하다. (Black-Height 불변)

이 5가지 속성으로 인해 트리의 최장 경로가 최단 경로의 2배를 초과할 수 없으며, 검색·삽입·삭제 모두 O(log n)의 시간 복잡도를 보장합니다.

AVL 트리 대비 장점

커널이 AVL 대신 rbtree를 선택한 핵심 이유는 삽입/삭제 시 리밸런싱 비용입니다:

• AVL 트리: 균형 조건이 더 엄격하여 검색은 약간 빠르지만, 삽입/삭제 시 최대 O(log n)번의 회전이 필요합니다.
• Red-Black Tree: 삽입 시 최대 2번, 삭제 시 최대 3번의 회전만 필요합니다. 커널처럼 쓰기(삽입/삭제)가 빈번한 환경에서 이 차이는 유의미합니다.

2. 내부 구조

rb_node 구조체

/* include/linux/rbtree_types.h */
struct rb_node {
    unsigned long  __rb_parent_color;  /* 부모 포인터 + 색상 비트 */
    struct rb_node *rb_right;           /* 오른쪽 자식 */
    struct rb_node *rb_left;            /* 왼쪽 자식 */
} __attribute__((aligned(sizeof(long))));

/* rb_root: 트리의 루트 */
struct rb_root {
    struct rb_node *rb_node;  /* 루트 노드 포인터 */
};

/* 초기화 매크로 */
#define RB_ROOT  (struct rb_root) { NULL, }

/* 빈 트리 확인 */
#define RB_EMPTY_ROOT(root)  (READ_ONCE((root)->rb_node) == NULL)
#define RB_EMPTY_NODE(node)  \
    ((node)->__rb_parent_color == (unsigned long)(node))

__rb_parent_color 비트 트릭

__rb_parent_color 필드는 커널 rbtree의 핵심 최적화입니다. rb_node 구조체가 sizeof(long)으로 정렬(align)되므로, 부모 포인터의 하위 2비트는 항상 0입니다. 커널은 이 하위 비트 중 LSB(비트 0)를 노드의 색상 정보로 활용합니다:

• 비트 0 = 0: 빨간색 (Red)
• 비트 0 = 1: 검은색 (Black)
• 비트 1~63: 부모 노드의 포인터 (하위 비트 마스킹)

/* include/linux/rbtree_augmented.h — 내부 매크로 */
#define RB_RED    0
#define RB_BLACK  1

#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))
#define __rb_color(pc)     ((pc) & 1)
#define rb_parent(rb)      __rb_parent((rb)->__rb_parent_color)
#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
#define rb_is_red(rb)      (!__rb_color((rb)->__rb_parent_color))
#define rb_is_black(rb)    (__rb_color((rb)->__rb_parent_color))

이 기법으로 별도의 색상 필드 없이 노드 1개당 메모리를 8바이트(64비트) 절약합니다. 수만~수십만 노드가 존재하는 커널 자료구조에서 이 절약은 매우 유의미합니다.

rb_node 메모리 레이아웃

3. 핵심 API

rb_entry() / container_of()

커널의 rbtree는 비침투적(intrusive) 설계입니다. rb_node를 사용자 구조체에 임베딩하고, rb_entry()(container_of()의 래퍼)로 부모 구조체를 역참조합니다.

/* rb_entry는 container_of의 별칭 */
#define rb_entry(ptr, type, member) \
    container_of(ptr, type, member)

/* 사용 예 */
struct my_data {
    int               key;
    int               value;
    struct rb_node    node;  /* rbtree 노드 임베딩 */
};

/* rb_node 포인터에서 my_data 포인터로 변환 */
struct rb_node *n = ...;
struct my_data *data = rb_entry(n, struct my_data, node);

삽입: rb_link_node() + rb_insert_color()

rbtree 삽입은 2단계로 이루어집니다:

/* 1단계: rb_link_node() — 노드를 트리에 연결 (아직 리밸런싱 안됨) */
void rb_link_node(struct rb_node *node,
                   struct rb_node *parent,
                   struct rb_node **rb_link);

/* 2단계: rb_insert_color() — 색상 조정 + 회전으로 5가지 속성 복원 */
void rb_insert_color(struct rb_node *node,
                      struct rb_root *root);

삭제: rb_erase()

/* 노드를 트리에서 제거하고 리밸런싱 수행 */
void rb_erase(struct rb_node *node, struct rb_root *root);

/* 노드 교체 (위치를 그대로 유지하며 노드만 교체) */
void rb_replace_node(struct rb_node *victim,
                      struct rb_node *new_node,
                      struct rb_root *root);

순회 함수

/* 최솟값 / 최댓값 (in-order 순서) */
struct rb_node *rb_first(const struct rb_root *root);  /* 최좌 노드 */
struct rb_node *rb_last(const struct rb_root *root);   /* 최우 노드 */

/* 전후 순회 */
struct rb_node *rb_next(const struct rb_node *node);  /* in-order 후계자 */
struct rb_node *rb_prev(const struct rb_node *node);  /* in-order 전임자 */

/* post-order 순회 (삭제 시 안전한 순회) */
struct rb_node *rb_first_postorder(const struct rb_root *root);
struct rb_node *rb_next_postorder(const struct rb_node *node);

/* 안전한 순회 매크로 (순회 중 삭제 가능) */
#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
    for (pos = rb_entry_safe(rb_first_postorder(root), \
                             typeof(*pos), field); \
         pos && ({ n = rb_entry_safe( \
              rb_next_postorder(&pos->field), \
              typeof(*pos), field); 1; }); \
         pos = n)

4. 전체 코드 예제

커널 모듈 형태의 완전한 rbtree 사용 예제입니다. 삽입, 검색, 순회, 삭제, 안전한 삭제 순회를 모두 포함합니다.

#include <linux/module.h>
#include <linux/rbtree.h>
#include <linux/slab.h>

struct my_node {
    int               key;
    int               value;
    struct rb_node    rb;
};

static struct rb_root my_tree = RB_ROOT;

/* ---- 삽입 ---- */
static int my_insert(struct rb_root *root, struct my_node *new_node)
{
    struct rb_node **link = &root->rb_node;
    struct rb_node *parent = NULL;
    int key = new_node->key;

    /* BST 탐색: 삽입 위치 찾기 */
    while (*link) {
        struct my_node *entry = rb_entry(*link, struct my_node, rb);

        parent = *link;
        if (key < entry->key)
            link = &(*link)->rb_left;
        else if (key > entry->key)
            link = &(*link)->rb_right;
        else
            return -EEXIST;  /* 중복 키 */
    }

    /* 1단계: 노드 연결 */
    rb_link_node(&new_node->rb, parent, link);
    /* 2단계: 리밸런싱 */
    rb_insert_color(&new_node->rb, root);
    return 0;
}

/* ---- 검색 ---- */
static struct my_node *my_search(struct rb_root *root, int key)
{
    struct rb_node *n = root->rb_node;

    while (n) {
        struct my_node *entry = rb_entry(n, struct my_node, rb);

        if (key < entry->key)
            n = n->rb_left;
        else if (key > entry->key)
            n = n->rb_right;
        else
            return entry;  /* 찾음 */
    }
    return NULL;
}

/* ---- 삭제 ---- */
static void my_erase(struct rb_root *root, struct my_node *node)
{
    rb_erase(&node->rb, root);
    kfree(node);
}

/* ---- in-order 순회 ---- */
static void my_traverse(struct rb_root *root)
{
    struct rb_node *n;

    for (n = rb_first(root); n; n = rb_next(n)) {
        struct my_node *entry = rb_entry(n, struct my_node, rb);
        pr_info("key=%d value=%d\n", entry->key, entry->value);
    }
}

/* ---- 전체 트리 삭제 (post-order safe) ---- */
static void my_destroy_tree(struct rb_root *root)
{
    struct my_node *pos, *n;

    rbtree_postorder_for_each_entry_safe(pos, n, root, rb) {
        kfree(pos);
    }
    root->rb_node = NULL;
}

/* ---- 모듈 init ---- */
static int __init rbtree_demo_init(void)
{
    int keys[] = { 50, 30, 70, 20, 40, 60, 80 };
    int i;

    for (i = 0; i < ARRAY_SIZE(keys); i++) {
        struct my_node *node = kmalloc(sizeof(*node), GFP_KERNEL);
        if (!node)
            return -ENOMEM;
        node->key = keys[i];
        node->value = keys[i] * 10;
        my_insert(&my_tree, node);
    }

    pr_info("=== In-order traversal ===\n");
    my_traverse(&my_tree);

    /* 검색 테스트 */
    struct my_node *found = my_search(&my_tree, 40);
    if (found)
        pr_info("Found: key=%d value=%d\n", found->key, found->value);

    /* 삭제 테스트 */
    found = my_search(&my_tree, 30);
    if (found)
        my_erase(&my_tree, found);

    pr_info("=== After delete 30 ===\n");
    my_traverse(&my_tree);

    return 0;
}

/* ---- 모듈 exit ---- */
static void __exit rbtree_demo_exit(void)
{
    my_destroy_tree(&my_tree);
    pr_info("rbtree demo unloaded\n");
}

module_init(rbtree_demo_init);
module_exit(rbtree_demo_exit);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Red-Black Tree demo module");

5. rb_root_cached

rb_root_cached는 rbtree의 최좌(최솟값) 노드를 캐싱하여 O(1) 접근을 제공하는 확장 구조체입니다.

/* include/linux/rbtree_types.h */
struct rb_root_cached {
    struct rb_root  rb_root;       /* 기본 rbtree root */
    struct rb_node *rb_leftmost;   /* 최좌(최솟값) 노드 캐시 */
};

#define RB_ROOT_CACHED  (struct rb_root_cached) { {NULL}, NULL }

/* O(1) 최솟값 접근 */
struct rb_node *rb_first_cached(const struct rb_root_cached *root);

/* cached 전용 삽입 — leftmost 자동 갱신 */
void rb_insert_color_cached(struct rb_node *node,
                            struct rb_root_cached *root,
                            bool leftmost);

/* cached 전용 삭제 — leftmost 자동 갱신 */
void rb_erase_cached(struct rb_node *node,
                      struct rb_root_cached *root);

사용 패턴

static struct rb_root_cached my_cached_tree = RB_ROOT_CACHED;

static void insert_cached(struct my_node *new_node)
{
    struct rb_node **link = &my_cached_tree.rb_root.rb_node;
    struct rb_node *parent = NULL;
    bool leftmost = true;  /* 새 노드가 최좌인지 추적 */

    while (*link) {
        struct my_node *entry = rb_entry(*link, struct my_node, rb);
        parent = *link;
        if (new_node->key < entry->key) {
            link = &(*link)->rb_left;
        } else {
            link = &(*link)->rb_right;
            leftmost = false;  /* 오른쪽으로 이동했으므로 최좌 아님 */
        }
    }
    rb_link_node(&new_node->rb, parent, link);
    rb_insert_color_cached(&new_node->rb, &my_cached_tree, leftmost);
}

CFS 스케줄러의 활용

CFS(Completely Fair Scheduler)는 rb_root_cached를 사용하여 태스크를 vruntime(가상 실행 시간) 기준으로 정렬합니다. rb_first_cached()로 vruntime이 가장 작은(가장 적게 실행된) 태스크를 O(1)에 선택합니다.

/* kernel/sched/sched.h */
struct cfs_rq {
    struct load_weight    load;
    unsigned int          nr_running;
    u64                   min_vruntime;
    struct rb_root_cached tasks_timeline;  /* vruntime 기준 rbtree */
    /* ... */
};

/* kernel/sched/fair.c — 다음 실행할 태스크 선택 */
static struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;
    return rb_entry(left, struct sched_entity, run_node);
}

6. 증강 rbtree (Augmented RB Tree)

증강(Augmented) rbtree는 각 노드에 서브트리 정보를 캐싱하여 트리 회전 시 이를 갱신하는 메커니즘입니다. 대표적인 활용이 Interval Tree입니다.

rb_augment_callbacks

/* include/linux/rbtree_augmented.h */
struct rb_augment_callbacks {
    /* 노드에서 루트까지 서브트리 정보 전파 */
    void (*propagate)(struct rb_node *node, struct rb_node *stop);
    /* 노드 간 서브트리 정보 복사 */
    void (*copy)(struct rb_node *old, struct rb_node *new_node);
    /* 회전 후 서브트리 정보 갱신 */
    void (*rotate)(struct rb_node *old, struct rb_node *new_node);
};

/* 증강 삽입: 리밸런싱 시 콜백 호출 */
void rb_insert_augmented(struct rb_node *node,
                         struct rb_root *root,
                         const struct rb_augment_callbacks *augment);

/* 증강 삭제: 리밸런싱 시 콜백 호출 */
void rb_erase_augmented(struct rb_node *node,
                        struct rb_root *root,
                        const struct rb_augment_callbacks *augment);

Interval Tree

Interval Tree는 증강 rbtree의 가장 대표적인 활용입니다. 각 노드가 구간 [start, last]을 나타내며, 서브트리의 최대 끝점(subtree_last)을 증강 정보로 유지합니다. 이를 통해 겹치는 구간을 O(k log n)에 검색합니다. (k = 결과 수)

/* include/linux/interval_tree_generic.h */
/* INTERVAL_TREE_DEFINE 매크로로 타입별 interval tree 생성 */

/* include/linux/interval_tree.h — 기본 interval_tree_node */
struct interval_tree_node {
    struct rb_node  rb;
    unsigned long   start;          /* 구간 시작 */
    unsigned long   last;           /* 구간 끝 */
    unsigned long   __subtree_last; /* 서브트리 최대 끝점 (증강) */
};

/* API */
void interval_tree_insert(struct interval_tree_node *node,
                          struct rb_root_cached *root);
void interval_tree_remove(struct interval_tree_node *node,
                          struct rb_root_cached *root);
/* [start, last] 구간과 겹치는 첫 번째 노드 검색 */
struct interval_tree_node *
interval_tree_iter_first(struct rb_root_cached *root,
                         unsigned long start, unsigned long last);
/* 다음 겹치는 노드 */
struct interval_tree_node *
interval_tree_iter_next(struct interval_tree_node *node,
                        unsigned long start, unsigned long last);

VMA Interval Tree

커널의 vm_area_struct(VMA)는 Interval Tree를 사용하여 가상 주소 범위를 관리합니다. 특정 주소가 어느 VMA에 속하는지 빠르게 검색할 수 있습니다.

/* include/linux/mm_types.h */
struct vm_area_struct {
    unsigned long  vm_start;     /* 시작 가상 주소 */
    unsigned long  vm_end;       /* 끝 가상 주소 */
    struct {
        struct rb_node  rb;
        unsigned long   rb_subtree_last;
    } shared;                      /* interval tree (address_space) */
    /* ... */
};

/* mm/interval_tree.c — VMA interval tree 검색 */
/* 파일의 특정 페이지 오프셋 범위를 매핑한 모든 VMA를 찾음 */
/* → reverse mapping (rmap)에서 사용 */

7. RCU-safe rbtree

읽기가 빈번하고 쓰기가 드문 패턴에서, RCU 보호 하에 rbtree를 lock-free로 읽기할 수 있습니다.

rb_link_node_rcu()

/* include/linux/rbtree.h */
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로 새 노드 발행 */
    rcu_assign_pointer(*rb_link, node);
}

/* 사용 패턴: 쓰기 측 (잠금 보유) */
spin_lock(&tree_lock);
rb_link_node_rcu(&new->rb, parent, link);
rb_insert_color(&new->rb, &my_root);
spin_unlock(&tree_lock);

/* 읽기 측 (RCU 보호) */
rcu_read_lock();
struct rb_node *n = rcu_dereference(my_root.rb_node);
while (n) {
    struct my_node *entry = rb_entry(n, struct my_node, rb);
    if (key < entry->key)
        n = rcu_dereference(n->rb_left);
    else if (key > entry->key)
        n = rcu_dereference(n->rb_right);
    else
        break;
}
rcu_read_unlock();

8. Latched rbtree

Latched rbtree는 이중 rbtree를 유지하여 완전한 lock-free 읽기를 달성합니다. 쓰기 시 두 트리를 순차적으로 갱신하고, 읽기 측은 seqcount_latch를 이용해 일관된 트리를 선택합니다.

/* include/linux/rbtree_latch.h */
struct latch_tree_node {
    struct rb_node node[2];  /* 이중 rbtree 노드 */
};

struct latch_tree_root {
    seqcount_latch_t  seq;
    struct rb_root     tree[2];  /* 이중 rbtree */
};

/* 콜백 구조체: 비교/검색 함수 정의 */
struct latch_tree_ops {
    bool (*less)(struct latch_tree_node *a,
                 struct latch_tree_node *b);
    int  (*comp)(void *key,
                 struct latch_tree_node *b);
};

/* API */
void latch_tree_insert(struct latch_tree_node *node,
                       struct latch_tree_root *root,
                       const struct latch_tree_ops *ops);

void latch_tree_erase(struct latch_tree_node *node,
                      struct latch_tree_root *root,
                      const struct latch_tree_ops *ops);

/* lock-free 검색 */
struct latch_tree_node *
latch_tree_find(void *key,
                struct latch_tree_root *root,
                const struct latch_tree_ops *ops);

모듈 주소 검색 사례

커널 모듈의 코어/init 주소 범위를 관리하는 module_tree는 latched rbtree를 사용합니다. 모듈 로드/언로드(쓰기)는 드물고, 스택 트레이스 등에서의 주소-모듈 매핑(읽기)은 매우 빈번하기 때문입니다.

/* kernel/module/tree_lookup.c */
static struct latch_tree_root mod_tree __cacheline_aligned;

/* 모듈 주소 검색 — NMI/인터럽트 컨텍스트에서도 안전 */
struct module *__module_address(unsigned long addr)
{
    struct latch_tree_node *ltn;
    ltn = latch_tree_find((void *)addr, &mod_tree, &mod_tree_ops);
    if (!ltn)
        return NULL;
    return container_of(ltn, struct mod_tree_node, node)->mod;
}

9. 실제 커널 활용 사례

10. 구조 다이어그램

rbtree 삽입 및 리밸런싱

아래 다이어그램은 rbtree에 노드를 삽입한 후, Red-Red 위반을 해결하기 위한 리밸런싱 과정을 보여줍니다.

리밸런싱은 크게 세 가지 경우로 나뉩니다:

11. 자료구조 비교