Red-Black Tree (rbtree)

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

개요

Red-Black Tree(이하 rbtree)는 Linux 커널에서 널리 사용되는 자기 균형 이진 탐색 트리입니다. CFS 스케줄러의 태스크 정렬, hrtimer 타이머 큐, epoll 파일 디스크립터 관리 등에서 핵심적으로 활용됩니다. VMA(가상 메모리 영역)는 커널 6.1 이상에서 Maple Tree가 기본이며, rbtree 기반 설명은 주로 6.0 이하/역사적 맥락에 해당합니다.

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번의 회전만 필요합니다. 커널처럼 쓰기(삽입/삭제)가 빈번한 환경에서 이 차이는 유의미합니다.

내부 구조

rb_node 구조체

/* 개념 예시: include/linux/rbtree_types.h 핵심 구조체 */
/* 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 메모리 레이아웃

핵심 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)

전체 코드 예제

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

/* 실습 예제: 커널 모듈에서 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");

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);
}

증강 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 = 결과 수) 자세한 내용은 Interval Tree 문서를 참고하세요.

/* 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 (버전 조건 병기)

커널 6.1+에서는 VMA의 주 인덱스 자료구조가 Maple Tree입니다. 아래 rbtree/interval tree 패턴은 커널 6.0 이하 및 역사적 구현을 이해하기 위한 예시이며, 현재도 파일 매핑 reverse-map 계열 경로에서는 interval tree 개념이 사용됩니다.

/* 개념 예시: 6.0 이하 vm_area_struct의 rbtree/interval tree 패턴 */
/* 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)에서 사용 */

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();

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;
}

실제 커널 활용 사례

구조 다이어그램

rbtree 삽입 및 리밸런싱

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

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

자료구조 비교

rbtree 디버깅 루틴

rbtree 버그는 삽입/삭제 후 균형 불변식 위반으로 드러납니다. 문제를 재현할 때는 회전과 링크 변경 경로를 함께 추적하세요.

1. 삽입 경로 점검: 링크 설정 후 rb_insert_color() 호출 순서 확인
2. 삭제 경로 점검: rb_erase() 뒤 노드 수명주기 확인
3. 중복 키 정책 확인: 동일 키 처리 규칙(허용/거부) 명확화
4. 증강 필드 검증: interval/augmented tree라면 propagate 경로 확인

# 사용 지점 및 오용 패턴 확인
git grep -n "rb_insert_color\\|rb_erase\\|rb_link_node" -- "*.c"
git grep -n "container_of(.*rb_node" -- "*.c"

회전 알고리즘 심화 (Rotation Deep Dive)

rbtree의 균형 유지는 회전(rotation)과 색상 변경(recoloring) 두 가지 연산으로 이루어집니다. 회전은 트리의 구조를 변경하면서도 BST 속성(왼쪽 < 부모 < 오른쪽)을 유지하는 핵심 연산입니다.

좌회전 (Left Rotation)

좌회전은 노드 X를 기준으로, X의 오른쪽 자식 Y를 X의 부모 위치로 올리는 연산입니다. Y의 왼쪽 서브트리 β는 X의 오른쪽 자식이 됩니다.

우회전 (Right Rotation)

우회전은 좌회전의 대칭 연산입니다. 노드 Y를 기준으로, Y의 왼쪽 자식 X를 Y의 부모 위치로 올립니다.

__rb_rotate_set_parents() 커널 구현

커널의 회전 함수는 부모 포인터와 색상을 동시에 설정하는 최적화된 헬퍼를 사용합니다. __rb_rotate_set_parents()는 회전 시 old 노드의 부모/색상을 new 노드에 이전하고, old 노드의 부모를 new 노드로 설정합니다.

/* lib/rbtree.c — 회전 시 부모/색상 일괄 설정 */
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 노드에 old의 부모와 old의 원래 색상을 설정 */
    new->__rb_parent_color = old->__rb_parent_color;
    /* old 노드의 부모를 new로, 색상을 color로 설정 */
    rb_set_parent_color(old, new, color);
    /* 조부모(parent)의 자식 포인터를 old → new로 갱신 */
    __rb_change_child(old, new, parent, root);
}

삽입 리밸런싱 3가지 케이스 상세

새 노드 N을 삽입한 후 부모 P가 Red이면 "No Red-Red" 위반이 발생합니다. 삼촌(Uncle) U와 배치에 따라 아래 3가지 케이스로 처리합니다.

/* lib/rbtree.c — __rb_insert() 핵심 루프 (간략화) */
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;

    while (true) {
        /* 부모가 없으면 node가 root → Black으로 설정 */
        if (unlikely(!parent)) {
            rb_set_parent_color(node, NULL, RB_BLACK);
            break;
        }
        /* 부모가 Black이면 위반 없음 → 종료 */
        if (rb_is_black(parent))
            break;

        gparent = rb_red_parent(parent);
        tmp = gparent->rb_right;  /* 삼촌 후보 */

        if (parent != tmp) {  /* parent == gparent→rb_left */
            if (tmp && rb_is_red(tmp)) {
                /* Case 1: 삼촌이 Red → Recolor */
                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);
                continue;
            }
            tmp = parent->rb_right;
            if (node == tmp) {
                /* Case 2: 삼각형 → 부모 좌회전 */
                tmp = node->rb_left;
                WRITE_ONCE(parent->rb_right, tmp);
                WRITE_ONCE(node->rb_left, parent);
                if (tmp)
                    rb_set_parent_color(tmp, parent, RB_BLACK);
                rb_set_parent_color(parent, node, RB_RED);
                augment_rotate(parent, node);
                parent = node;
                tmp = node->rb_right;
            }
            /* Case 3: 직선 → 조부모 우회전 */
            WRITE_ONCE(gparent->rb_left, tmp);
            WRITE_ONCE(parent->rb_right, gparent);
            if (tmp)
                rb_set_parent_color(tmp, gparent, RB_BLACK);
            __rb_rotate_set_parents(gparent, parent, root, RB_RED);
            augment_rotate(gparent, parent);
            break;
        }
        /* else: 대칭 케이스 (parent == gparent→rb_right) — 동일 로직 좌우 반전 */
    }
}

삭제 알고리즘 심화 (Delete Deep Dive)

rbtree 삭제는 삽입보다 복잡합니다. 삭제된 노드가 Black이면 Black-Height 불변식이 깨져 double-black 문제가 발생하며, 이를 해결하기 위해 4가지 케이스의 fixup이 필요합니다.

삭제 전체 흐름

1. BST 삭제: 자식이 0~1개면 직접 제거, 자식 2개면 in-order 후계자(successor)로 교체 후 후계자를 제거합니다.
2. 색상 판단: 실제 제거된 노드가 Red이면 불변식 위반 없이 종료. Black이면 fixup 진행.
3. Fixup: double-black 노드에서 시작하여 4가지 케이스를 처리합니다.

__rb_erase_augmented() 핵심 흐름

__rb_erase_augmented()는 삭제할 노드의 자식 수에 따라 처리를 분기합니다. 증강 rbtree의 경우 삭제/교체 시 콜백을 호출하여 서브트리 정보를 갱신합니다.

/* include/linux/rbtree_augmented.h — 삭제 핵심 (간략화) */
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;

    if (!tmp) {
        /* Case A: 왼쪽 자식 없음 → 오른쪽 자식(또는 NULL)으로 교체 */
        parent = rb_parent(node);
        __rb_change_child(node, child, parent, root);
        if (child) {
            child->__rb_parent_color = node->__rb_parent_color;
            rebalance = NULL;
        } else {
            rebalance = rb_is_black(node) ? parent : NULL;
        }
    } else if (!child) {
        /* Case B: 오른쪽 자식 없음 → 왼쪽 자식으로 교체 */
        parent = rb_parent(node);
        tmp->__rb_parent_color = node->__rb_parent_color;
        __rb_change_child(node, tmp, parent, root);
        rebalance = NULL;
    } else {
        /* Case C: 자식 2개 → in-order 후계자(successor)를 찾아 교체 */
        struct rb_node *successor = child, *child2;

        tmp = child->rb_left;
        if (!tmp) {
            /* 후계자가 바로 오른쪽 자식인 경우 */
            parent = successor;
            child2 = successor->rb_right;
            augment->copy(node, successor);
        } else {
            /* 후계자가 오른쪽 서브트리의 최좌 노드 */
            do {
                parent = successor;
                successor = tmp;
                tmp = tmp->rb_left;
            } while (tmp);
            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);
        }
        /* successor를 node 위치에 배치 */
        /* ... 부모/자식 포인터 재연결 ... */
        rebalance = rb_is_black(successor) ? parent : NULL;
    }
    return rebalance;  /* NULL이면 fixup 불필요, 아니면 fixup 시작점 */
}

증강 rbtree 심화 (rb_augment Deep Dive)

증강 rbtree는 각 노드에 서브트리 요약 정보(예: 서브트리 내 최댓값, 총 합 등)를 캐싱하고, 트리 회전이나 노드 교체 시 이 정보를 자동으로 갱신합니다. 커널은 세 가지 콜백(propagate, copy, rotate)을 통해 이를 처리합니다.

콜백 체인: propagate → copy → rotate

RB_DECLARE_CALLBACKS 매크로

커널은 RB_DECLARE_CALLBACKS와 RB_DECLARE_CALLBACKS_MAX 매크로로 증강 콜백 보일러플레이트를 자동 생성합니다.

/* include/linux/rbtree_augmented.h */

/*
 * RB_DECLARE_CALLBACKS — propagate/copy/rotate 콜백 자동 생성
 *
 * rbstruct:  rb_node를 포함하는 구조체 타입
 * rbfield:   rb_node 필드 이름
 * rbtype:    증강 데이터의 타입
 * rbaugmented: 증강 데이터 필드 이름
 * rbcompute: 증강 데이터 재계산 함수
 */
#define RB_DECLARE_CALLBACKS(rbstatic, rbname,               \
                             rbstruct, rbfield,              \
                             rbtype, rbaugmented, rbcompute) \
static inline void                                          \
rbname##_propagate(struct rb_node *rb, struct rb_node *stop) \
{                                                            \
    while (rb != stop) {                                     \
        rbstruct *node = rb_entry(rb, rbstruct, rbfield);     \
        rbtype augmented = rbcompute(node);                  \
        if (node->rbaugmented == augmented)                   \
            break;  /* 변경 없으면 조기 종료 */             \
        node->rbaugmented = augmented;                       \
        rb = rb_parent(&node->rbfield);                     \
    }                                                        \
}                                                            \
/* ... copy, rotate 콜백도 유사하게 생성 ... */

/*
 * RB_DECLARE_CALLBACKS_MAX — max 계산 전용 변형
 * 서브트리의 최댓값을 자동으로 계산 (Interval Tree 패턴)
 */
#define RB_DECLARE_CALLBACKS_MAX(rbstatic, rbname,           \
                                 rbstruct, rbfield,          \
                                 rbtype, rbaugmented,        \
                                 rbcompute)                  \
/* 내부적으로 left/right 자식의 max와 self 값 중 최대를 선택 */

augment_rotate 동작 예시

/* Interval Tree의 rotate 콜백 — 간략화 */
static inline void
interval_tree_augment_rotate(struct rb_node *old, struct rb_node *new)
{
    struct interval_tree_node *old_it, *new_it;

    old_it = rb_entry(old, struct interval_tree_node, rb);
    new_it = rb_entry(new, struct interval_tree_node, rb);

    /* new는 old의 서브트리를 그대로 물려받으므로
     * new→__subtree_last = old→__subtree_last (이전 값 유지) */
    new_it->__subtree_last = old_it->__subtree_last;

    /* old는 서브트리가 변경되었으므로 재계산 */
    old_it->__subtree_last = interval_tree_compute_max(old_it);
}

메모리 레이아웃과 색상 인코딩

rb_node는 64비트 시스템에서 정확히 24바이트를 차지합니다. 색상 정보를 별도 필드 없이 부모 포인터의 LSB에 인코딩하여 메모리를 절약하는 것이 핵심입니다.

CFS 스케줄러 rbtree 분석

CFS(Completely Fair Scheduler)는 rb_root_cached를 사용하여 실행 가능한 태스크를 vruntime(가상 실행 시간) 순서로 관리합니다. vruntime이 가장 작은(가장 적게 실행된) 태스크를 O(1)에 선택합니다.

__enqueue_entity() 분석

/* kernel/sched/fair.c — CFS rbtree 삽입 */
static void __enqueue_entity(struct cfs_rq *cfs_rq,
                             struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    struct rb_node *parent = NULL;
    bool leftmost = true;

    while (*link) {
        struct sched_entity *entry;
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);

        /*
         * vruntime 비교: entity_before()
         * se->vruntime < entry->vruntime이면 왼쪽으로
         */
        if (entity_before(se, entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = false;  /* 오른쪽으로 이동 → 최좌 아님 */
        }
    }

    rb_link_node(&se->run_node, parent, link);
    rb_insert_color_cached(&se->run_node,
                            &cfs_rq->tasks_timeline, leftmost);
}

__dequeue_entity() 분석

/* kernel/sched/fair.c — CFS rbtree 삭제 */
static void __dequeue_entity(struct cfs_rq *cfs_rq,
                              struct sched_entity *se)
{
    rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}

/* pick_next_entity — O(1) 태스크 선택 */
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);
}

hrtimer rbtree 분석

고해상도 타이머(hrtimer)는 rb_root_cached를 사용하여 타이머를 만료 시간(ktime) 순서로 관리합니다. rb_first_cached()로 다음에 만료될 타이머를 O(1)에 조회합니다.

enqueue_hrtimer() 분석

/* kernel/time/hrtimer.c — 타이머 등록 */
static void enqueue_hrtimer(struct hrtimer *timer,
                            struct hrtimer_clock_base *base,
                            enum hrtimer_mode mode)
{
    /* timerqueue_add()는 내부적으로 rb_root_cached에 삽입 */
    timerqueue_add(&base->active, &timer->node);
    /* ... reprogram 등 ... */
}

/* kernel/time/timer_list.c — timerqueue 삽입 핵심 */
bool timerqueue_add(struct timerqueue_head *head,
                    struct timerqueue_node *node)
{
    struct rb_node **p = &head->rb_root.rb_root.rb_node;
    struct rb_node *parent = NULL;
    struct timerqueue_node *ptr;
    bool leftmost = true;

    while (*p) {
        parent = *p;
        ptr = rb_entry(parent, struct timerqueue_node, node);

        /* ktime 비교: expires 기준 */
        if (node->expires < ptr->expires) {
            p = &(*p)->rb_left;
        } else {
            p = &(*p)->rb_right;
            leftmost = false;
        }
    }

    rb_link_node(&node->node, parent, p);
    rb_insert_color_cached(&node->node, &head->rb_root, leftmost);

    return leftmost;  /* 새 타이머가 최솟값이면 true → HW reprogramming 필요 */
}

epoll rbtree 분석

epoll은 모니터링할 파일 디스크립터(fd)를 rb_root_cached로 관리합니다. fd 기반으로 정렬하여 O(log n) 삽입/삭제/검색을 제공합니다.

ep_insert() 코드 분석

/* fs/eventpoll.c — epoll_ctl(EPOLL_CTL_ADD) 핵심 */
static int ep_insert(struct eventpoll *ep,
                     const struct epoll_event *event,
                     struct file *tfile, int fd,
                     int full_check)
{
    struct epitem *epi;

    /* epitem 할당 */
    epi = kmem_cache_zalloc(epi_cache, GFP_KERNEL);
    if (unlikely(!epi))
        return -ENOMEM;

    /* 키 설정: file 포인터 + fd */
    epi->ffd.file = tfile;
    epi->ffd.fd = fd;
    epi->event = *event;
    epi->ep = ep;

    /* rbtree에 삽입 */
    ep_rbtree_insert(ep, epi);
    /* ... poll callback 등록, wakeup 설정 등 ... */
    return 0;
}

/* rbtree 삽입 — (file, fd) 쌍으로 비교 */
static void ep_rbtree_insert(struct eventpoll *ep,
                             struct epitem *epi)
{
    struct rb_node **p = &ep->rbr.rb_root.rb_node;
    struct rb_node *parent = NULL;
    struct epitem *epic;
    bool leftmost = true;

    while (*p) {
        parent = *p;
        epic = rb_entry(parent, struct epitem, rbn);

        /* ep_cmp_ffd(): file 포인터 비교, 같으면 fd 비교 */
        if (ep_cmp_ffd(&epi->ffd, &epic->ffd) > 0) {
            p = &(*p)->rb_right;
            leftmost = false;
        } else {
            p = &(*p)->rb_left;
        }
    }

    rb_link_node(&epi->rbn, parent, p);
    rb_insert_color_cached(&epi->rbn, &ep->rbr, leftmost);
}

ftrace/perf 실습

rbtree 연산을 실시간으로 추적하여 성능 병목과 동작을 분석할 수 있습니다.

ftrace로 rbtree 연산 추적

# rb_insert_color / rb_erase 함수 추적
echo 'rb_insert_color' > /sys/kernel/debug/tracing/set_ftrace_filter
echo 'rb_erase' >> /sys/kernel/debug/tracing/set_ftrace_filter
echo function > /sys/kernel/debug/tracing/current_tracer
echo 1 > /sys/kernel/debug/tracing/tracing_on

# 워크로드 실행 후 결과 확인
cat /sys/kernel/debug/tracing/trace

# 출력 예시:
#  -0   [001] d.h.  1234.567890: rb_insert_color <-enqueue_hrtimer
#  nginx-1234 [003] ....  1234.567891: rb_insert_color <-ep_insert
#  nginx-1234 [003] ....  1234.567895: rb_erase        <-ep_remove

# 호출 스택 포함 추적 (function_graph)
echo function_graph > /sys/kernel/debug/tracing/current_tracer
echo 'rb_insert_color' > /sys/kernel/debug/tracing/set_graph_function

# 정리
echo 0 > /sys/kernel/debug/tracing/tracing_on
echo nop > /sys/kernel/debug/tracing/current_tracer

perf probe로 CFS enqueue/dequeue 추적

# CFS enqueue/dequeue 동적 프로브 등록
perf probe --add '__enqueue_entity cfs_rq se'
perf probe --add '__dequeue_entity cfs_rq se'

# 10초간 이벤트 기록
perf record -e 'probe:__enqueue_entity' \
            -e 'probe:__dequeue_entity' \
            -a -- sleep 10

# 결과 분석
perf report

# perf stat으로 캐시 미스 측정
perf stat -e cache-misses,cache-references,instructions \
          -p $(pgrep -f workload) -- sleep 5

# 프로브 정리
perf probe --del 'probe:__enqueue_entity'
perf probe --del 'probe:__dequeue_entity'

bpftrace 원라이너

# rbtree 회전 횟수를 호출자별로 카운트
bpftrace -e 'kprobe:rb_insert_color { @insert[kstack(2)] = count(); }'

# rb_erase 호출 빈도 (프로세스별)
bpftrace -e 'kprobe:rb_erase { @erase[comm] = count(); }'

# CFS enqueue 시 vruntime 분포 히스토그램
bpftrace -e 'kprobe:__enqueue_entity {
    $se = (struct sched_entity *)arg1;
    @vruntime = hist($se->vruntime);
}'

# hrtimer 등록 빈도 (clock base별)
bpftrace -e 'kprobe:enqueue_hrtimer {
    @hrtimer[kstack(3)] = count();
}'

성능 특성과 튜닝

rbtree는 범용적으로 우수하지만, 워크로드에 따라 다른 자료구조가 더 적합할 수 있습니다. 아래 비교표와 분석을 통해 적절한 선택을 할 수 있습니다.

rbtree vs Maple Tree vs XArray 비교

캐시 미스 분석

# rbtree 연산의 캐시 미스 측정
perf stat -e L1-dcache-load-misses,L1-dcache-loads,\
LLC-load-misses,LLC-loads \
-p $(pgrep -f target_workload) -- sleep 10

# 출력 예시:
#  1,234,567  L1-dcache-load-misses  #  3.45% of all L1-dcache loads
#    567,890  LLC-load-misses        # 12.34% of all LLC loads
#
# rbtree 워크로드에서 LLC miss가 높으면:
# - 노드가 메모리에 분산되어 캐시 지역성이 낮음
# - Maple Tree나 B-tree 변형이 더 적합할 수 있음

rb_root vs rb_root_cached 선택 기준

rbtree vs 대안 자료구조 실전 선택

커널에서 자료구조를 선택할 때는 워크로드 특성, RCU 요구사항, 키 유형 등을 종합적으로 고려해야 합니다.

VMA 마이그레이션 상세

커널 6.1에서 VMA가 rbtree에서 Maple Tree로 마이그레이션된 핵심 이유는 다음과 같습니다:

관련 문서

Red-Black Tree와 관련된 다른 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

• Linked List — 리스트 자료구조
• Interval Tree — 증강 rbtree 활용
• 프로세스 스케줄러 — CFS의 rbtree 사용
• 메모리 관리 (심화) — VMA 관리(6.1+ Maple Tree, 6.0 이하 rbtree 계열)
• VFS — dentry/inode lookup 자료구조 연계