B-tree (lib/btree)

리눅스 커널의 범용 인메모리 B-tree 구현(lib/btree.c, lib/btree.h)을 심층 분석합니다. btree_head/btree_geo 구조체(Struct), 32/64/128비트 키 타입, 검색/삽입/삭제 알고리즘, visitor 패턴을 통한 순회, mempool 기반 메모리 관리(Memory Management), 그리고 Maple Tree/rbtree와의 비교까지 포괄합니다. B-tree 이론부터 커널 소스 수준의 구현 세부사항, btrfs의 온디스크 B-tree+와의 차이, 성능 특성, 디버깅(Debugging) 기법까지 다룹니다.

B-tree 개요

B-tree는 1970년 Rudolf Bayer와 Edward McCreight가 발명한 자기 균형 탐색 트리입니다. 하나의 노드에 여러 개의 키를 저장하여 트리 높이를 최소화하고, 디스크 I/O 최적화를 위해 설계되었습니다. 리눅스 커널의 lib/btree.c는 이 개념을 인메모리 환경에 적용한 구현으로, 노드 크기를 128바이트(L1 캐시라인 2개)로 고정하여 캐시 성능을 최적화합니다.

이진 트리와의 차이

커널 내 위치와 용도

lib/btree.c는 범용 키-값 저장소로 설계되었습니다. 주요 사용처는 다음과 같습니다:

• LogFS -- 원래 개발 동기. 로그 구조 파일시스템의 세그먼트 매핑(Mapping)에 사용 (LogFS는 이후 커널에서 제거되었지만 btree 라이브러리는 유지됨)
• HID -- drivers/hid/에서 report field 매핑에 활용
• 범용 인메모리 맵 -- 고정 크기 키로 빠른 검색이 필요한 서브시스템에서 사용 가능

소스 파일 구조

B-tree 이론

B-tree는 데이터베이스와 파일시스템의 근간이 되는 자료구조로, 1970년 Rudolf Bayer와 Edward McCreight가 Boeing Research Labs에서 발명했습니다. 이름의 "B"에 대해서는 "Balanced", "Bayer", "Boeing" 등 여러 해석이 있지만, 원저자는 공식적으로 밝히지 않았습니다.

B-tree의 핵심은 최소 차수(minimum degree) t로 정의되는 5가지 속성입니다. 커널의 lib/btree.c는 노드 크기 128바이트에서 키 길이에 따라 t가 자동 결정됩니다.

B-tree 5대 속성

높이 분석

n개의 키를 가진 B-tree의 높이 h는 다음 부등식을 만족합니다:

h ≤ logt((n + 1) / 2)

예시: t=32 (커널 geo32의 실제 값), n=1,000,000
h ≤ log32(500000.5) ≈ 3.79
--> 최대 높이 4, 즉 4번의 노드 접근으로 백만 개 키 검색 가능

B-tree 변형들

학술/산업 분야에서 B-tree의 다양한 변형이 존재합니다. 커널에서 사용되는 것들과의 관계를 정리합니다:

시간 복잡도 요약

노드 레이아웃

커널 B-tree의 노드는 128바이트(NODESIZE) 고정 크기의 unsigned long 배열입니다. 키, 값(포인터), 자식 포인터가 하나의 배열 안에 인터리빙되어 배치됩니다. 이 128바이트라는 크기는 대부분의 아키텍처에서 L1 캐시라인 2개에 해당하며, 노드 하나를 읽는 데 최대 2번의 캐시라인 로드만 필요합니다.

/* lib/btree.c */
#define NODESIZE     128    /* 바이트 단위 노드 크기 */
#define MAX_KEYLEN   4      /* unsigned long 단위 최대 키 길이 (128비트) */

/* 노드 = unsigned long 배열 (32비트: 32 슬롯, 64비트: 16 슬롯) */
static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
{
    unsigned long *node;
    node = mempool_alloc(head->mempool, gfp);
    if (likely(node))
        memset(node, 0, NODESIZE);
    return node;
}

btree_head 구조체

btree_head는 B-tree 인스턴스의 루트를 가리키는 핸들입니다. 모든 B-tree API는 이 구조체를 첫 번째 인자로 받습니다. 이 구조체는 매우 작아서(포인터 2개 + int 1개, 약 20바이트) 스택이나 다른 구조체에 임베딩하기에 적합합니다. rbtree의 rb_root(8바이트)보다는 크지만, Maple Tree의 maple_tree(16바이트)와 비슷한 수준입니다.

/* include/linux/btree.h */
struct btree_head {
    unsigned long *node;       /* 루트 노드 포인터 (NULL이면 빈 트리) */
    mempool_t     *mempool;    /* 노드 할당용 메모리 풀 */
    int            height;     /* 트리 높이 (0 = 리프만 존재) */
};

/* 초기화 패턴 */
struct btree_head my_tree;

/* 트리 초기화 -- mempool 생성 포함 */
ret = btree_init(&my_tree);
if (ret)
    return ret;  /* -ENOMEM */

/* ... 사용 ... */

/* 트리 해체 -- 모든 노드 해제 + mempool 파괴 */
btree_destroy(&my_tree);

btree_geo 구조체

btree_geo는 B-tree의 기하학적 파라미터를 정의합니다. 키 크기에 따라 노드당 몇 개의 키-값 쌍을 저장할 수 있는지가 결정됩니다.

/* include/linux/btree.h */
struct btree_geo {
    int keylen;     /* 키 길이 (unsigned long 단위) */
    int no_pairs;   /* 노드당 키-값 쌍의 최대 수 */
    int no_longs;   /* 키 영역이 차지하는 총 long 수 = keylen * no_pairs */
};

/* lib/btree.c -- geo 상수 정의 */
struct btree_geo btree_geo32 = {
    .keylen  = 1,
    .no_pairs = NODESIZE / sizeof(long) / 2,
    .no_longs = NODESIZE / sizeof(long) / 2,
};
EXPORT_SYMBOL_GPL(btree_geo32);

struct btree_geo btree_geo64 = {
    .keylen  = LONG_PER_U64,
    .no_pairs = NODESIZE / sizeof(long) / (LONG_PER_U64 + 1),
    .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (LONG_PER_U64 + 1)),
};
EXPORT_SYMBOL_GPL(btree_geo64);

키 타입 (geo32/geo64/geo128)

커널 B-tree는 3가지 키 크기를 지원합니다. 각 키 타입에 대해 편의 래퍼 함수가 btree-type.h 매크로로 생성됩니다. 키 타입 선택은 저장 효율과 트리 높이에 직접적인 영향을 미칩니다. 래퍼 함수는 키의 unsigned long 배열 변환을 캡슐화(Encapsulation)하여, 호출자가 원시 배열을 직접 다룰 필요가 없게 합니다.

btree_geo32 -- 32비트 키

32비트 키는 unsigned long 1개로 표현됩니다(64비트 시스템에서도 상위 비트는 0). 단순 정수 키가 필요한 경우에 사용합니다. 64비트 시스템에서 geo32를 사용하면 상위 32비트가 0으로 채워지므로 키 공간의 절반을 낭비하지만, 노드당 쌍 수는 geo64와 동일합니다(둘 다 keylen=1).

/* include/linux/btree-type.h 매크로 확장 예시 */
static inline void *btree_lookup32(struct btree_head32 *head, u32 key)
{
    unsigned long _key = key;
    return btree_lookup(&head->h, &btree_geo32, &_key);
}

static inline int btree_insert32(struct btree_head32 *head,
                                   u32 key, void *val, gfp_t gfp)
{
    unsigned long _key = key;
    return btree_insert(&head->h, &btree_geo32, &_key, val, gfp);
}

btree_geo64 -- 64비트 키

64비트 키는 u64를 사용합니다. 32비트 시스템에서는 unsigned long 2개(LONG_PER_U64=2)로 분할되고, 64비트 시스템에서는 1개(LONG_PER_U64=1)로 표현됩니다. 64비트 시스템에서는 geo32와 geo64가 동일한 노드 레이아웃을 가집니다 (둘 다 keylen=1).

/* 64비트 키 사용 예시 */
struct btree_head tree;
u64 key = 0xDEADBEEF12345678ULL;
void *val = my_data;

btree_insert64(&tree, key, val, GFP_KERNEL);
val = btree_lookup64(&tree, key);  /* --> my_data */

btree_geo128 -- 128비트 키

128비트 키는 unsigned long 2개(64비트 시스템) 또는 4개(32비트 시스템)로 구성됩니다. 복합 키(예: inode 번호 + offset)에 유용합니다. 128비트 키는 별도의 헤더 파일(btree-128.h)에 정의되어 있으며, 두 개의 u64를 인자로 받는 편의 함수를 제공합니다.

/* include/linux/btree-128.h */
static inline void *btree_lookup128(struct btree_head128 *head,
                                     u64 k1, u64 k2)
{
    unsigned long key[2] = { k1, k2 };  /* 64비트 시스템 */
    return btree_lookup(&head->h, &btree_geo128, key);
}

검색 알고리즘

B-tree 검색은 루트에서 시작하여 각 노드에서 키를 비교하며 적절한 자식으로 내려갑니다. 커널 구현은 노드 내에서 선형 검색을 사용합니다. 노드당 최대 8개 키(geo32 기준)이므로 이진 검색 대비 추가 비교 횟수는 미미하고, 분기 예측(Branch Prediction) 실패 비용을 피할 수 있습니다.

/* lib/btree.c -- btree_lookup */
void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
                   unsigned long *key)
{
    int i, height = head->height;
    unsigned long *node = head->node;

    if (height == 0)
        return NULL;

    for ( ; height > 1; height--) {
        for (i = 0; i < geo->no_pairs; i++)
            if (keycmp(geo, node, i, key) <= 0)
                break;
        if (i == geo->no_pairs)
            return NULL;
        node = bval(geo, node, i);   /* 자식 노드로 이동 */
        if (!node)
            return NULL;
    }

    /* 리프 레벨: 정확한 키 매칭 */
    if (!node)
        return NULL;
    for (i = 0; i < geo->no_pairs; i++)
        if (keycmp(geo, node, i, key) == 0)
            return bval(geo, node, i);
    return NULL;
}

keycmp / longcmp 함수

키 비교는 unsigned long 배열을 첫 번째 원소부터 순차적으로 비교합니다. 이는 big-endian 스타일 비교로, 128비트 키에서 첫 번째 u64가 major key 역할을 합니다. 비교 함수의 반환값은 표준 strcmp 규칙을 따릅니다: 음수(l1 < l2), 0(같음), 양수(l1 > l2).

/* lib/btree.c */
static int keycmp(struct btree_geo *geo,
                  unsigned long *node, int pos,
                  unsigned long *key)
{
    return longcmp(bkey(geo, node, pos), key, geo->keylen);
}

static int longcmp(const unsigned long *l1,
                   const unsigned long *l2, size_t n)
{
    int i;
    for (i = 0; i < n; i++) {
        if (l1[i] < l2[i])
            return -1;
        if (l1[i] > l2[i])
            return 1;
    }
    return 0;
}

삽입 알고리즘

B-tree 삽입은 항상 리프 노드에서 이루어집니다. 리프가 가득 찬 경우(no_pairs개 키) 노드 분할(split)이 발생하며, 분할은 부모로 전파될 수 있습니다. 루트까지 전파되면 트리 높이가 1 증가합니다. 삽입 알고리즘은 top-down 방식으로, 루트에서 시작하여 적절한 리프까지 내려가면서 필요한 분할을 수행합니다.

/* lib/btree.c -- btree_insert (핵심 흐름) */
int btree_insert(struct btree_head *head, struct btree_geo *geo,
                 unsigned long *key, void *val, gfp_t gfp)
{
    /* 빈 트리이면 루트 노드 생성 */
    if (!head->node) {
        head->node = btree_node_alloc(head, gfp);
        if (!head->node)
            return -ENOMEM;
        head->height = 1;
    }

    /* 재귀적 삽입 -- 분할이 필요하면 반환값으로 전파 */
    return btree_insert_level(head, geo, key, val,
                             1, gfp);  /* level=1: 리프 */
}

노드 분할 메커니즘

분할 시 가득 찬 노드의 상위 절반 키를 새 노드로 이동하고, 중간 키를 부모로 올립니다(promote). 이 과정은 O(no_pairs) 시간이 소요되며, 주로 memcpy에 해당하는 setkey/setval 반복으로 구성됩니다:

/* lib/btree.c -- btree_splitnode (간략화) */
static unsigned long *btree_splitnode(struct btree_head *head,
    struct btree_geo *geo, unsigned long *node, gfp_t gfp)
{
    unsigned long *new;
    int fill = geo->no_pairs;

    new = btree_node_alloc(head, gfp);
    if (!new)
        return ERR_PTR(-ENOMEM);

    /* 상위 절반을 새 노드로 복사 */
    for (i = 0; i < fill / 2; i++) {
        setkey(geo, new, i, bkey(geo, node, i));
        setval(geo, new, i, bval(geo, node, i));
        clearpair(geo, node, i);
    }

    return new;
}

btree_insert_level 세부 흐름

실제 삽입은 재귀적 btree_insert_level()에서 처리됩니다. 각 레벨에서 적절한 자식을 찾아 내려가고, 리프에서 삽입 후 분할이 필요하면 상위로 전파합니다:

/* lib/btree.c -- btree_insert_level (간략화) */
static int btree_insert_level(struct btree_head *head,
    struct btree_geo *geo, unsigned long *key,
    void *val, int level, gfp_t gfp)
{
    unsigned long *node = head->node;
    int i, pos, fill, err;

    /* 노드가 가득 찼는지 확인 */
    fill = getfill(geo, node, 0);
    if (fill == geo->no_pairs) {
        /* 분할 필요 → 새 루트 생성 */
        err = btree_grow(head, geo, gfp);
        if (err)
            return err;
    }

    /* 적절한 위치에 키-값 쌍 삽입 */
    /* 기존 키들을 shift하여 정렬 위치 확보 */
    for (i = fill; i > pos; i--) {
        setkey(geo, node, i, bkey(geo, node, i - 1));
        setval(geo, node, i, bval(geo, node, i - 1));
    }
    setkey(geo, node, pos, key);
    setval(geo, node, pos, val);
    return 0;
}

btree_grow -- 트리 높이 증가

루트 노드가 가득 차면 btree_grow()가 호출되어 새 루트를 생성합니다:

/* lib/btree.c -- btree_grow */
static int btree_grow(struct btree_head *head,
                      struct btree_geo *geo, gfp_t gfp)
{
    unsigned long *node;

    node = btree_node_alloc(head, gfp);
    if (!node)
        return -ENOMEM;

    /* 기존 루트의 첫 번째 키를 새 루트에 복사 */
    setkey(geo, node, 0, bkey(geo, head->node, 0));
    /* 기존 루트를 새 루트의 자식으로 설정 */
    setval(geo, node, 0, head->node);

    head->node = node;
    head->height++;
    return 0;
}

삭제 알고리즘

B-tree 삭제는 리프에서의 키 제거, 필요 시 형제 노드와의 재분배(redistribute) 또는 병합(merge)으로 구성됩니다. 커널 구현에서는 삭제 후 노드의 키가 0개가 되면 노드를 해제합니다. 삭제는 삽입과 달리 메모리 할당이 필요하지 않으므로, 항상 성공합니다(키가 존재하면).

/* lib/btree.c -- btree_remove (핵심 흐름 간략화) */
void *btree_remove(struct btree_head *head,
                   struct btree_geo *geo,
                   unsigned long *key)
{
    /* 1. 리프까지 내려가며 키 위치 탐색 */
    /* 2. 키-값 쌍 제거 (배열 shift) */
    /* 3. 노드가 비면(fill==0) 부모에서 자식 포인터 제거 */
    /* 4. 루트가 비고 자식이 1개면 높이 감소 (shrink) */
    return btree_remove_level(head, geo, key, 1);
}

병합과 수축

노드가 비어지면 형제와 병합하거나, 부모에서 해당 자식 포인터를 제거합니다. 루트에 키가 없고 자식이 하나만 남으면 그 자식이 새 루트가 되어 트리 높이가 1 감소합니다.

btree_shrink -- 트리 높이 감소

삭제 후 루트에 키가 없고 자식이 하나만 남으면, 그 자식이 새 루트가 됩니다:

/* lib/btree.c -- btree_shrink (간략화) */
static void btree_shrink(struct btree_head *head,
                         struct btree_geo *geo)
{
    unsigned long *node = head->node;
    unsigned long *child;
    int fill = getfill(geo, node, 0);

    if (fill != 1)
        return;  /* 2개 이상이면 수축 불필요 */

    child = bval(geo, node, 0);
    head->node = child;
    head->height--;

    mempool_free(node, head->mempool);  /* 기존 루트 해제 */
}

btree_remove_level 세부 흐름

삭제의 핵심인 btree_remove_level()은 다음 단계로 동작합니다:

/* 삭제 핵심 흐름 (의사 코드) */
static void *btree_remove_level(head, geo, key, level)
{
    /* 1. 키 위치 탐색 */
    for (i = 0; i < geo->no_pairs; i++)
        if (keycmp(geo, node, i, key) == 0)
            break;

    /* 2. 값 보존 (반환용) */
    val = bval(geo, node, i);

    /* 3. 배열 shift로 gap 제거 */
    for (j = i; j < fill - 1; j++) {
        setkey(geo, node, j, bkey(geo, node, j + 1));
        setval(geo, node, j, bval(geo, node, j + 1));
    }
    clearpair(geo, node, fill - 1);

    /* 4. 필요 시 수축 */
    if (getfill(geo, head->node, 0) == 1)
        btree_shrink(head, geo);

    return val;
}

update 연산

btree_update()는 이미 존재하는 키의 값(포인터)을 교체합니다. 새로운 노드 할당이 필요하지 않으므로 항상 성공하며(키가 존재하면), GFP 플래그가 필요 없습니다. 이전 값은 반환되지 않으므로, 이전 값의 해제가 필요하면 호출 전에 btree_lookup()으로 먼저 조회해야 합니다.

/* lib/btree.c */
int btree_update(struct btree_head *head, struct btree_geo *geo,
                 unsigned long *key, void *val)
{
    /* 트리를 순회하며 키를 찾고, bval 슬롯만 교체 */
    unsigned long *node = head->node;
    int i, height = head->height;

    for ( ; height > 1; height--) {
        for (i = 0; i < geo->no_pairs; i++)
            if (keycmp(geo, node, i, key) <= 0)
                break;
        node = bval(geo, node, i);
    }

    for (i = 0; i < geo->no_pairs; i++)
        if (keycmp(geo, node, i, key) == 0) {
            setval(geo, node, i, val);
            return 0;
        }
    return -ENOENT;  /* 키가 존재하지 않음 */
}

Upsert 패턴 (Insert or Update)

키가 존재하면 업데이트, 없으면 삽입하는 "upsert" 패턴입니다:

/* upsert: 있으면 update, 없으면 insert */
static int btree_upsert32(struct btree_head32 *head,
                           u32 key, void *val, gfp_t gfp)
{
    int ret;

    /* 먼저 update 시도 (메모리 할당 불필요) */
    ret = btree_update32(head, key, val);
    if (ret == -ENOENT)
        /* 키 없음 → insert */
        ret = btree_insert32(head, key, val, gfp);
    return ret;
}

/* remove + insert 방식 (이전 값 보존 필요 시) */
static int btree_replace32(struct btree_head32 *head,
                            u32 key, void *new_val,
                            void **old_val, gfp_t gfp)
{
    *old_val = btree_remove32(head, key);
    return btree_insert32(head, key, new_val, gfp);
}

완전한 사용 예시

커널 모듈(Kernel Module)에서 B-tree를 사용하는 전체 흐름입니다:

#include <linux/btree.h>
#include <linux/slab.h>

struct my_data {
    u32 id;
    char name[32];
};

static struct btree_head32 my_tree;

static int __init my_init(void)
{
    struct my_data *d;
    int ret;

    /* 1. 트리 초기화 */
    ret = btree_init32(&my_tree);
    if (ret)
        return ret;

    /* 2. 데이터 삽입 */
    d = kmalloc(sizeof(*d), GFP_KERNEL);
    if (!d) { ret = -ENOMEM; goto err; }
    d->id = 42;
    strscpy(d->name, "test", sizeof(d->name));

    ret = btree_insert32(&my_tree, 42, d, GFP_KERNEL);
    if (ret) { kfree(d); goto err; }

    /* 3. 검색 */
    d = btree_lookup32(&my_tree, 42);
    if (d)
        pr_info("found: %s\n", d->name);

    return 0;

err:
    btree_destroy32(&my_tree);
    return ret;
}

static void __exit my_exit(void)
{
    /* grim_visitor로 모든 데이터 해제 + 노드 해제 */
    btree_grim_visitor32(&my_tree, free_entry);
    btree_destroy32(&my_tree);
}

visitor 패턴

B-tree 순회에는 두 가지 visitor가 있습니다. btree_visitor는 읽기 전용(Read-Only) 순회, btree_grim_visitor는 순회와 동시에 모든 노드를 해제하는 파괴적 순회입니다. visitor 패턴은 GoF 디자인 패턴의 Visitor 패턴과 유사하며, 트리 구조의 순회 로직과 처리 로직을 분리합니다.

/* include/linux/btree.h */
typedef void (*visitor_t)(void *elem, unsigned long opaque,
                          unsigned long *key, size_t index,
                          void *__func);

/* 읽기 전용 순회 -- 트리 구조 유지 */
size_t btree_visitor(struct btree_head *head,
                     struct btree_geo *geo,
                     unsigned long opaque,
                     visitor_t func);

/* 파괴적 순회 -- 방문 후 모든 노드 해제 */
size_t btree_grim_visitor(struct btree_head *head,
                          struct btree_geo *geo,
                          unsigned long opaque,
                          visitor_t func);

visitor 사용 예시

/* 모든 항목 출력 */
static void print_entry(void *elem, unsigned long opaque,
                       unsigned long *key, size_t index,
                       void *__func)
{
    pr_info("[%zu] key=%lu val=%p\n", index, key[0], elem);
}

/* 순회 호출 */
size_t count = btree_visitor(&my_tree, &btree_geo32, 0, print_entry);
pr_info("total: %zu entries\n", count);

grim_visitor를 이용한 트리 해체

/* 모든 값 객체를 kfree한 후 트리 파괴 */
static void free_entry(void *elem, unsigned long opaque,
                      unsigned long *key, size_t index,
                      void *__func)
{
    kfree(elem);  /* 값 객체 해제 */
}

/* grim_visitor는 콜백 후 노드도 해제 */
btree_grim_visitor(&my_tree, &btree_geo32, 0, free_entry);
/* 이 시점에서 트리는 완전히 비어 있음 (head->node = NULL) */

메모리 풀 통합

커널 B-tree는 노드 할당에 mempool을 사용합니다. mempool은 최소 개수의 객체를 미리 예약하여, GFP_ATOMIC 컨텍스트에서도 할당 실패를 방지합니다. 이는 인터럽트(Interrupt) 핸들러(Handler)나 spinlock 보호 구간에서도 B-tree 삽입을 안전하게 수행할 수 있게 합니다.

btree_alloc / btree_free 콜백

mempool의 할당/해제 백엔드로 사용되는 함수입니다:

/* lib/btree.c */
static void *btree_alloc(gfp_t gfp_mask, void *pool_data)
{
    return kmalloc(NODESIZE, gfp_mask);
}

static void btree_free(void *element, void *pool_data)
{
    kfree(element);
}

/* lib/btree.c -- 초기화 */
int btree_init(struct btree_head *head)
{
    head->node = NULL;
    head->height = 0;
    head->mempool = mempool_create(0,
        btree_alloc, btree_free, NULL);
    if (!head->mempool)
        return -ENOMEM;
    return 0;
}

/* lib/btree.c -- 해체 */
void btree_destroy(struct btree_head *head)
{
    mempool_free(head->node, head->mempool);
    mempool_destroy(head->mempool);
    head->mempool = NULL;
}

API 레퍼런스

lib/btree.c가 내보내는 전체 API 목록입니다. 모든 함수는 EXPORT_SYMBOL_GPL로 모듈에서 사용 가능합니다.

타입별 래퍼

include/linux/btree-type.h의 BTREE_TYPE_SUFFIX 매크로는 위 API 각각에 대해 32/64 접미사 래퍼를 생성합니다:

/* btree-type.h 매크로 사용법 */
BTREE_TYPE_SUFFIX              /* 32, 64 */
btree_lookup32(head, key)      /* -> btree_lookup(&head->h, &btree_geo32, &key) */
btree_insert32(head, key, val, gfp)
btree_update32(head, key, val)
btree_remove32(head, key)
btree_last32(head, key)
btree_get_prev32(head, key)

btree_merge -- 두 트리 병합

btree_merge()는 victim 트리의 모든 키-값 쌍을 target 트리로 이동합니다:

/* lib/btree.c */
int btree_merge(struct btree_head *target,
                struct btree_head *victim,
                struct btree_geo *geo, gfp_t gfp)
{
    unsigned long key[MAX_KEYLEN];
    void *val;
    int err;

    /* victim에서 하나씩 꺼내서 target에 삽입 */
    while ((val = btree_last(victim, geo, key))) {
        err = btree_insert(target, geo, key, val, gfp);
        if (err)
            return err;
        btree_remove(victim, geo, key);
    }
    return 0;
}

에러 코드 요약

btree_last / btree_get_prev

이 두 함수는 범위 스캔과 역순 순회의 핵심입니다. 커널 B-tree에는 정순(forward) 이터레이터가 없으므로, 역순 순회가 키 순서 기반 범위 검색의 유일한 방법입니다. btree_last()는 최대 키를 O(height) 시간에 반환하고, btree_get_prev()는 주어진 키 이하의 최대 키를 O(height) 시간에 반환합니다.

btree_last -- 최대 키 조회

/* lib/btree.c */
void *btree_last(struct btree_head *head,
                 struct btree_geo *geo,
                 unsigned long *key)
{
    int height = head->height;
    unsigned long *node = head->node;

    if (height == 0)
        return NULL;

    /* 각 레벨에서 가장 마지막(최대) 키 쪽으로 이동 */
    for ( ; height > 1; height--)
        node = bval(geo, node, 0);  /* 첫 번째 = 가장 큰 키 */

    longcpy(key, bkey(geo, node, 0), geo->keylen);
    return bval(geo, node, 0);
}

btree_get_prev -- 이전 키 조회 (범위 스캔)

btree_get_prev()는 주어진 키보다 작거나 같은 가장 큰 키를 찾습니다. 이를 반복 호출하면 역순 범위 스캔이 가능합니다:

/* 역순 범위 스캔 패턴 */
unsigned long key;
void *val;

/* 최대 키부터 시작 */
val = btree_last(&tree, &btree_geo32, &key);
while (val) {
    process(key, val);
    /* 현재 키보다 작은 다음 키 찾기 */
    val = btree_get_prev(&tree, &btree_geo32, &key);
}

범위 쿼리 패턴

특정 범위 [lo, hi] 내의 모든 키를 찾으려면 btree_get_prev()를 반복 호출하면서 범위를 체크합니다:

/* 범위 [lo, hi] 내 모든 항목 처리 */
static void btree_range_query(struct btree_head *head,
                               unsigned long lo,
                               unsigned long hi)
{
    unsigned long key = hi;
    void *val;

    /* hi 이하의 최대 키부터 시작 */
    val = btree_get_prev(head, &btree_geo32, &key);
    while (val && key >= lo) {
        process(key, val);
        if (key == 0)
            break;  /* 언더플로 방지 */
        key--;  /* 현재 키보다 작은 키 탐색 */
        val = btree_get_prev(head, &btree_geo32, &key);
    }
}

/* 주의: 이 패턴은 O(range * log n)으로,
 * 범위가 넓으면 btree_visitor()가 더 효율적 */

내부 헬퍼 함수

lib/btree.c의 핵심 내부 함수들입니다. 이 함수들은 static으로 외부에 노출되지 않지만, 알고리즘 이해에 필수적입니다:

/* lib/btree.c -- getfill: 채워진 슬롯 수 계산 */
static int getfill(struct btree_geo *geo,
                   unsigned long *node, int start)
{
    int i;
    for (i = start; i < geo->no_pairs; i++)
        if (!bval(geo, node, i))
            break;
    return i;
}

/* lib/btree.c -- keyzero: 빈 키 판별 */
static int keyzero(struct btree_geo *geo,
                   unsigned long *key)
{
    int i;
    for (i = 0; i < geo->keylen; i++)
        if (key[i])
            return 0;
    return 1;
}

Maple Tree 비교

Maple Tree(Linux 6.1+)는 B-tree에서 영감을 받은 범위 기반 자료구조로, rbtree를 대체하여 VMA(Virtual Memory Area) 관리에 사용됩니다. Liam Howlett(Oracle)이 개발했으며, Matthew Wilcox의 xarray와 B-tree의 아이디어를 결합한 것입니다. lib/btree.c의 범용 B-tree와는 설계 목적과 구현이 크게 다릅니다.

rbtree 비교

Red-Black Tree(rbtree)는 커널에서 가장 널리 사용되는 탐색 트리입니다. CFS 스케줄러(Scheduler), VMA 관리(Linux 6.0 이전), ext4 extent tree 등 수백 곳에서 사용됩니다. B-tree와의 차이를 이해하면 적절한 자료구조를 선택할 수 있습니다.

lib/btree.c 선택 시점

• 고정 크기 키(32/64/128비트)로 포인트 검색이 주요 연산인 경우
• mempool을 통한 할당 실패 방지가 중요한 경우
• btree_merge()로 두 트리를 합쳐야 하는 경우
• 구현의 단순함이 우선인 경우 (~600줄 vs rbtree ~800줄)

rbtree 선택 시점

• 가변 크기 키 또는 사용자 정의 비교 함수가 필요한 경우
• RCU 기반 동시 접근이 필요한 경우 (rbtree는 RCU-safe 변형 존재)
• augmented tree가 필요한 경우 (예: interval tree)
• 순서 순회(rb_next/rb_prev)가 빈번한 경우
• 기존 커널 코드와의 일관성이 중요한 경우 (rbtree가 표준)

실전 비교: 어떤 자료구조를 선택할 것인가

btrfs B-tree 참고

btrfs 파일시스템도 "B-tree"를 사용하지만, lib/btree.c와는 완전히 별개의 구현입니다. btrfs의 B-tree+는 온디스크(on-disk) 자료구조로, COW(Copy-on-Write) 시맨틱과 결합됩니다. 사실 "btrfs"라는 이름 자체가 "B-tree File System"의 약자입니다.

btrfs 키 형식

btrfs의 키는 3-튜플 구조로, lib/btree.c의 단순 정수 키보다 훨씬 복잡합니다:

/* fs/btrfs/ctree.h */
struct btrfs_key {
    __le64 objectid;   /* 8바이트: 객체 ID (inode 번호 등) */
    __u8   type;       /* 1바이트: 아이템 유형 (INODE_ITEM 등) */
    __le64 offset;     /* 8바이트: 유형별 오프셋 (블록 번호 등) */
} __attribute__((__packed__));  /* 총 17바이트 */

btrfs COW 시맨틱

btrfs는 노드를 직접 수정하지 않고, 수정된 복사본을 생성(Copy-on-Write)합니다. 이는 원자적(Atomic) 트랜잭션(Transaction)과 스냅샷 지원의 핵심이지만, lib/btree.c에는 없는 기능입니다. COW의 비용은 수정이 루트까지 전파되어야 하므로 경로(path) 전체에 대한 복사가 필요하다는 점입니다:

lib/btree.c: node[slot] = new_value  (직접 수정, O(1))
btrfs:       new_node = copy(node)   (복사 후 수정, O(node_size))
             parent->child = new_node
             --> 수정이 루트까지 전파 (path COW)

성능 분석

커널 B-tree의 실제 성능은 키 타입, 트리 크기, 접근 패턴에 따라 달라집니다. 이 섹션에서는 이론적 복잡도부터 캐시 성능, 메모리 오버헤드, 확장성까지 종합적으로 분석합니다.

이론적 복잡도

캐시 성능 분석

B-tree 노드 접근 패턴:
  - 노드 크기 128바이트 = L1 캐시라인 2개 (64바이트 x 2)
  - 한 번의 노드 접근으로 최대 8개 키 비교 (geo32)
  - 캐시 미스: O(height) = O(log_t n) 회

rbtree 노드 접근 패턴:
  - 노드 크기 ~40바이트 = 캐시라인 1개
  - 한 번의 노드 접근으로 1개 키 비교
  - 캐시 미스: O(log_2 n) 회 (각각 다른 캐시라인)

예시 n=10,000:
  B-tree (geo32): height ≤ 4 --> 최대 4회 캐시 미스
  rbtree: 깊이 ≤ 27 (2 * log_2(10001)) --> 최대 27회 캐시 미스

메모리 오버헤드 분석

자료구조의 메모리 효율은 키-값 쌍당 소비하는 바이트 수로 비교할 수 있습니다:

삽입 분할 비용 분석

분할(split)은 B-tree 삽입의 주요 비용입니다. 분할 발생 확률과 비용을 분석합니다:

무작위 삽입 시 분할 확률은 1/no_pairs에 근사합니다. geo32에서 100번 삽입하면 평균 12~13회 분할이 발생하며, 루트 분할(트리 높이 증가)은 매우 드뭅니다.

삭제 비용 분석

커널 B-tree의 삭제는 교과서 B-tree보다 단순하지만, 트리가 희소해질 수 있습니다:

교과서 B-tree 삭제: merge/rotate 비용 O(t) + 전파 O(log_t n)
커널 B-tree 삭제:   배열 shift O(no_pairs) + shrink O(1)

절충점:
- 교과서: 노드 utilization >= 50% 보장 → 메모리 효율적
- 커널:   노드 utilization 보장 없음 → 구현 단순, 약간 희소

확장성 (Scalability)

트리 크기별 예상 높이와 노드 접근 횟수입니다 (geo32, 64비트 시스템 기준):

디버깅

B-tree 관련 버그는 대부분 잘못된 API 사용, 메모리 누수, 동시성 문제에서 발생합니다. 이 섹션에서는 일반적인 오류 패턴과 체계적인 진단 절차를 다룹니다.

일반적 오류 패턴

트리 무결성(Integrity) 검증

/* 디버그용: 트리 내용 덤프 */
static void btree_dump_entry(void *elem, unsigned long opaque,
                             unsigned long *key, size_t index,
                             void *__func)
{
    pr_debug("btree[%zu]: key=%lx val=%px\n",
             index, key[0], elem);

    /* 값 포인터 유효성 검사 */
    WARN_ON(!virt_addr_valid(elem));
}

/* 전체 트리 덤프 */
size_t n = btree_visitor(&my_tree, &btree_geo32, 0,
                        btree_dump_entry);
pr_debug("btree: %zu entries, height=%d\n",
         n, my_tree.height);

ftrace를 이용한 B-tree 추적

# btree 관련 함수 추적 활성화
echo 'btree_*' > /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
# 출력 예시:
# my_module-1234  [002]  123.456789: btree_lookup <- my_lookup_func
# my_module-1234  [002]  123.456790: btree_insert <- my_insert_func

# 함수 그래프 트레이서로 호출 깊이 확인
echo function_graph > /sys/kernel/debug/tracing/current_tracer
# btree_insert -> btree_insert_level -> btree_grow -> btree_node_alloc 경로 확인

kmemleak으로 B-tree 메모리 누수 추적

# kmemleak 활성화 (CONFIG_DEBUG_KMEMLEAK=y)
echo scan > /sys/kernel/debug/kmemleak
cat /sys/kernel/debug/kmemleak

# 누수된 B-tree 노드 예시 출력:
# unreferenced object 0xffff888012345000 (size 128):
#   comm "my_module", pid 1234
#   backtrace:
#     btree_node_alloc+0x1c/0x40
#     btree_insert_level+0xab/0x200
#     btree_insert+0x56/0x80
#     my_insert_func+0x30/0x60

디버깅 관련 커널 설정

동시성 보호 패턴

커널 B-tree는 내부적으로 동시성 보호를 제공하지 않습니다. 호출자가 외부 락으로 보호해야 합니다:

/* 패턴 1: spinlock 보호 (짧은 연산) */
static DEFINE_SPINLOCK(tree_lock);

void my_insert(u32 key, void *val)
{
    spin_lock(&tree_lock);
    btree_insert32(&my_tree, key, val, GFP_ATOMIC);
    spin_unlock(&tree_lock);
}

/* 패턴 2: mutex 보호 (GFP_KERNEL 사용 가능) */
static DEFINE_MUTEX(tree_mutex);

void my_insert_sleepable(u32 key, void *val)
{
    mutex_lock(&tree_mutex);
    btree_insert32(&my_tree, key, val, GFP_KERNEL);
    mutex_unlock(&tree_mutex);
}

lockdep 어노테이션 패턴

B-tree를 보호하는 락에 대해 lockdep 어노테이션을 추가하면 잠금(Lock) 순서 위반을 자동 탐지할 수 있습니다:

/* lockdep을 위한 올바른 패턴 */
static DEFINE_MUTEX(tree_A_mutex);
static DEFINE_MUTEX(tree_B_mutex);

/* 항상 A -> B 순서로 잠금 (역순 금지) */
void transfer(u32 key)
{
    void *val;

    mutex_lock(&tree_A_mutex);     /* 항상 A 먼저 */
    mutex_lock(&tree_B_mutex);     /* 그 다음 B */

    val = btree_remove32(&tree_A, key);
    if (val)
        btree_insert32(&tree_B, key, val, GFP_KERNEL);

    mutex_unlock(&tree_B_mutex);
    mutex_unlock(&tree_A_mutex);
}

/* lockdep이 A->B 의존성을 기록하고,
 * B->A 순서 시 경고를 출력함 */

흔한 실수 코드 vs 올바른 코드

/* [잘못된 코드] 키 값 0 사용 */
btree_insert32(&tree, 0, my_data, GFP_KERNEL);
/* --> 키 0은 빈 슬롯으로 인식되어 검색 불가! */

/* [올바른 코드] 키 값 0 회피 */
btree_insert32(&tree, key + 1, my_data, GFP_KERNEL);
/* 또는 0이 아닌 매핑 함수 사용 */

/* [잘못된 코드] insert 반환값 무시 */
btree_insert32(&tree, key, val, GFP_KERNEL);
/* --> -ENOMEM 시 데이터 손실 가능 */

/* [올바른 코드] 반환값 확인 */
ret = btree_insert32(&tree, key, val, GFP_KERNEL);
if (ret) {
    pr_err("btree insert failed: %d\n", ret);
    kfree(val);
    return ret;
}

/* [잘못된 코드] destroy 없이 해제 */
btree_grim_visitor32(&tree, free_cb);
/* --> mempool이 해제되지 않아 메모리 누수! */

/* [올바른 코드] grim_visitor + destroy */
btree_grim_visitor32(&tree, free_cb);
btree_destroy32(&tree);  /* mempool 해제 */

안전한 정리 패턴

/* 모듈 제거 시 안전한 정리 순서 */
static void my_exit(void)
{
    /* 1. 새로운 삽입 차단 (플래그 또는 락) */
    spin_lock(&my_lock);
    shutting_down = true;
    spin_unlock(&my_lock);

    /* 2. 모든 값 객체 해제 + 노드 해제 */
    btree_grim_visitor(&my_tree, &btree_geo32, 0, free_entry);

    /* 3. mempool 파괴 (잔여 예약 객체 해제) */
    btree_destroy(&my_tree);
}

커널 설정 옵션

lib/btree.c는 CONFIG_BTREE 옵션으로 제어됩니다:

# lib/Kconfig
config BTREE
    bool
    help
      B-tree library, useful for indexing/searching in kernel space.
      This is selected by drivers/modules that need it.

CONFIG_BTREE는 직접 선택하지 않고, btree를 사용하는 드라이버/모듈이 select BTREE로 간접 활성화합니다. 대부분의 배포판 커널에서는 기본적으로 포함됩니다.

모듈에서 B-tree 사용 체크리스트

B-트리 변형: B+트리, B*트리

커널의 lib/btree.c는 표준 B-tree이지만, 파일시스템에서는 B+트리와 B*트리 변형이 더 널리 사용됩니다. 각 변형의 구조적 차이와 커널에서의 활용을 비교합니다.

lib/btree.c 구현 특성

커널의 인메모리 B-tree는 디스크 B-tree와 여러 면에서 다릅니다:

• 고정 노드 크기: 128바이트 (L1 캐시 라인 2개 = 가장 일반적인 캐시 라인 크기의 배수)로 고정. NODESIZE = L1_CACHE_BYTES <= 128 ? L1_CACHE_BYTES : 128
• 키 0 예약: 키 값 0은 빈 슬롯을 표시하는 센티넬(Sentinel)로 사용. 사용자 키에 0을 사용하면 검색이 실패합니다.
• 비침투적 설계: 값은 void * 포인터로 저장하여, rbtree와 달리 사용자 구조체에 노드를 임베딩하지 않습니다.
• 반복자 없음: rb_next()/rb_prev() 같은 반복자가 없고, btree_visitor() 콜백 패턴만 지원합니다.

Btrfs B+트리 구조

/* Btrfs B+트리 온디스크 구조 (fs/btrfs/ctree.h) */
struct btrfs_header {
    u8  csum[32];        /* 노드 체크섬 */
    u8  fsid[16];        /* 파일시스템 UUID */
    __le64 bytenr;         /* 디스크 오프셋 */
    __le64 flags;
    __le64 generation;     /* COW 트랜잭션 세대 */
    __le64 owner;          /* 소유 트리 ID */
    __le32 nritems;        /* 아이템 수 */
    u8  level;             /* 0 = 리프 */
};

/* 내부 노드: 키 + 자식 블록 포인터 */
struct btrfs_key_ptr {
    struct btrfs_disk_key key;
    __le64 blockptr;       /* 자식 노드 디스크 주소 */
    __le64 generation;     /* 자식 세대 (무결성 검증) */
};

/* 리프 노드: 키 + 아이템 데이터 (인라인) */
struct btrfs_item {
    struct btrfs_disk_key key;
    __le32 offset;         /* 리프 내 데이터 오프셋 */
    __le32 size;           /* 데이터 크기 */
};

XFS B+트리 활용

XFS는 여러 용도에 각각 독립적인 B+트리를 사용합니다:

ext4 Extent 트리

ext4의 extent 트리는 완전한 B+트리는 아니지만, B-tree 변형의 트리 구조를 사용합니다:

/* ext4 extent 트리 구조 (fs/ext4/ext4_extents.h) */
struct ext4_extent_header {
    __le16 eh_magic;       /* 0xF30A */
    __le16 eh_entries;     /* 유효 엔트리 수 */
    __le16 eh_max;         /* 최대 엔트리 수 */
    __le16 eh_depth;       /* 0 = 리프 */
    __le32 eh_generation;
};

/* 리프: 논리 블록 → 물리 블록 매핑 */
struct ext4_extent {
    __le32 ee_block;       /* 논리 블록 시작 */
    __le16 ee_len;         /* extent 길이 */
    __le16 ee_start_hi;    /* 물리 블록 상위 16비트 */
    __le32 ee_start_lo;    /* 물리 블록 하위 32비트 */
};

/* 내부 노드: 인덱스 엔트리 */
struct ext4_extent_idx {
    __le32 ei_block;       /* 논리 블록 범위 시작 */
    __le32 ei_leaf_lo;     /* 자식 블록 하위 32비트 */
    __le16 ei_leaf_hi;     /* 자식 블록 상위 16비트 */
    __le16 ei_unused;
};

커널 btree API 사용 가이드

이 섹션은 lib/btree.c의 타입별 래퍼 API를 중심으로, 실전 모듈 개발에 필요한 패턴을 정리합니다. 모든 타입별 래퍼는 btree-type.h의 매크로로 생성되며, 내부적으로 동일한 범용 함수를 호출합니다.

초기화와 해체

/* 초기화: mempool 생성 + 빈 트리 설정 */
struct btree_head32 my_tree;
int ret;

ret = btree_init32(&my_tree);
if (ret) {
    pr_err("btree init failed: %d\n", ret);
    return ret;
}

/* 해체: 모든 노드 + mempool 해제 */
/* 주의: 값 객체는 btree_destroy가 해제하지 않음! */
btree_grim_visitor32(&my_tree, my_free_callback);
btree_destroy32(&my_tree);

CRUD 연산

/* Insert: 키가 이미 존재하면 -EEXIST가 아니라 값이 교체됨 */
ret = btree_insert32(&my_tree, key, value, GFP_KERNEL);
if (ret == -ENOMEM) {
    pr_err("OOM during btree insert\n");
}

/* Lookup: 키가 없으면 NULL 반환 */
void *val = btree_lookup32(&my_tree, key);
if (!val)
    pr_debug("key %u not found\n", key);

/* Remove: 키가 없으면 NULL 반환, 있으면 제거하고 값 반환 */
void *removed = btree_remove32(&my_tree, key);
if (removed)
    kfree(removed);   /* 값 객체 해제는 호출자 책임 */

/* Update (lib/btree에는 별도 update가 없으므로 remove+insert) */
old_val = btree_remove32(&my_tree, key);
kfree(old_val);
btree_insert32(&my_tree, key, new_val, GFP_KERNEL);

/* Last: 가장 큰 키와 값 조회 */
void *last_val = btree_last32(&my_tree, &last_key);

/* Get Prev: 주어진 키보다 작은 가장 큰 키 조회 */
void *prev_val = btree_get_prev32(&my_tree, &prev_key);

GFP 플래그 선택 가이드

파일시스템별 B-tree/B+트리 활용 비교

성능 분석

lib/btree.c의 성능 특성을 이론적 분석과 실측 관점에서 상세히 다룹니다.

연산별 복잡도 상세

여기서 k는 노드당 키 수, h는 트리 높이입니다. geo32의 경우 k=14이므로 log14(1,000,000) ≈ 5.2, 즉 백만 개 항목도 6회 이내의 노드 접근으로 검색됩니다.

캐시(Cache) 효율 분석

# B-tree 연산의 캐시 미스 측정
perf stat -e L1-dcache-load-misses,L1-dcache-loads,\
LLC-load-misses,LLC-loads \
-a -- modprobe my_btree_test_module

# B-tree vs rbtree 비교 분석:
# B-tree: 128B 노드 = 2개 캐시 라인, 14개 키 검색 가능
#   → 1 노드 접근 = 2 캐시 미스로 14개 키 비교
# rbtree: 24B 노드, 2개 자식만
#   → 1 노드 접근 = 1 캐시 미스로 1개 키 비교
#
# 결론: 동일 키 수에서 B-tree가 캐시 미스 횟수 ~3배 적음
# 단, rbtree는 침투적이라 노드 할당 오버헤드 없음

대용량 벤치마크 (geo32 기준)

실전 커널 모듈 예제

B-tree API를 사용하는 완전한 커널 모듈 예제입니다. 초기화, CRUD 연산, 순회, 해체를 모두 포함합니다.

/*
 * btree_demo.c -- lib/btree API 데모 모듈
 *
 * 빌드: make -C /lib/modules/$(uname -r)/build M=$(pwd) modules
 * 로드: insmod btree_demo.ko
 * 제거: rmmod btree_demo
 * 로그: dmesg | grep btree_demo
 */

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

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("B-tree API demo");

struct my_data {
    u32 id;
    char name[32];
};

static struct btree_head32 my_tree;
static DEFINE_MUTEX(tree_mutex);

/* visitor 콜백: 항목 출력 */
static int print_entry(void *elem, unsigned long opaque,
                       unsigned long *key, size_t index,
                       void *__func)
{
    struct my_data *d = elem;
    pr_info("btree_demo: [%zu] key=%lu id=%u name=%s\n",
            index, key[0], d->id, d->name);
    return 0;
}

/* grim_visitor 콜백: 값 객체 해제 */
static int free_entry(void *elem, unsigned long opaque,
                      unsigned long *key, size_t index,
                      void *__func)
{
    kfree(elem);
    return 0;
}

static int __init btree_demo_init(void)
{
    struct my_data *d;
    void *found;
    int ret, i;
    size_t count;

    /* 1. 트리 초기화 */
    ret = btree_init32(&my_tree);
    if (ret)
        return ret;

    /* 2. 100개 항목 삽입 (키 1~100, 0은 사용 금지!) */
    mutex_lock(&tree_mutex);
    for (i = 1; i <= 100; i++) {
        d = kzalloc(sizeof(*d), GFP_KERNEL);
        if (!d) { ret = -ENOMEM; goto err_unlock; }
        d->id = i;
        snprintf(d->name, sizeof(d->name), "item-%03d", i);

        ret = btree_insert32(&my_tree, i, d, GFP_KERNEL);
        if (ret) {
            kfree(d);
            goto err_unlock;
        }
    }
    mutex_unlock(&tree_mutex);

    /* 3. 검색 */
    found = btree_lookup32(&my_tree, 42);
    if (found)
        pr_info("btree_demo: found key=42 → %s\n",
                ((struct my_data *)found)->name);

    /* 4. 삭제 */
    mutex_lock(&tree_mutex);
    found = btree_remove32(&my_tree, 50);
    mutex_unlock(&tree_mutex);
    if (found) {
        pr_info("btree_demo: removed key=50 → %s\n",
                ((struct my_data *)found)->name);
        kfree(found);
    }

    /* 5. 전체 순회 */
    count = btree_visitor32(&my_tree, 0, print_entry);
    pr_info("btree_demo: %zu entries total\n", count);

    return 0;

err_unlock:
    mutex_unlock(&tree_mutex);
    btree_grim_visitor32(&my_tree, free_entry);
    btree_destroy32(&my_tree);
    return ret;
}

static void __exit btree_demo_exit(void)
{
    mutex_lock(&tree_mutex);
    btree_grim_visitor32(&my_tree, free_entry);
    btree_destroy32(&my_tree);
    mutex_unlock(&tree_mutex);
    pr_info("btree_demo: cleaned up\n");
}

module_init(btree_demo_init);
module_exit(btree_demo_exit);

# Makefile
obj-m += btree_demo.o

all:
	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

clean:
	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

메모리 할당 전략

lib/btree.c는 노드 할당에 mempool을 사용합니다. 모든 노드가 동일한 128바이트 크기이므로, slab 캐시(kmalloc-128)에서 빠르게 할당/해제됩니다.

노드 크기 결정 로직

/* lib/btree.c의 노드 크기 결정 */
#define NODESIZE   max_t(int, L1_CACHE_BYTES, 128)
/* L1 캐시 라인이 128B 이하면 128B 사용 (대부분의 아키텍처)
 * L1 캐시 라인이 128B 초과면 캐시 라인 크기 사용 (POWER9 등)
 */

/* 노드 내부 레이아웃 (geo32, NODESIZE=128) */
/*
 * keys[]:   unsigned long × 14개 = 112B (64비트) 또는 56B (32비트)
 * vals[]:   void * × 14개 (키와 인터리브)
 * child[]:  void * × 15개 (내부 노드만)
 *
 * 실제 슬롯 수 계산:
 *   no_pairs = NODESIZE / (keysize + sizeof(void *))
 *   no_longs = keysize / sizeof(unsigned long)
 */

mempool 동작 상세

키 타입별 슬롯 수 상세

관련 문서

• Red-Black Tree (rbtree) -- 커널의 주요 탐색 트리, B-tree와의 비교 기준
• Maple Tree 자료구조 -- B-tree 영감의 범위 기반 트리, VMA 관리
• Interval Tree -- augmented rbtree 기반 구간 검색
• SLAB/SLUB 할당자 -- B-tree 노드의 kmalloc 백엔드
• 메모리 관리 개요 -- mempool, GFP 플래그 컨텍스트
• lockdep -- B-tree 보호 락의 의존성 검증
• 동기화 기법 -- B-tree 접근 보호에 사용되는 락 프리미티브
• XArray -- 정수 키 기반 대안 자료구조, 페이지 캐시(Page Cache) 관리

참고 자료

• include/linux/btree.h — Bootlin Elixir — 커널 B-tree API 헤더 파일입니다. btree_head, btree_geo 구조체와 모든 공개 함수 선언을 포함합니다.
• lib/btree.c — Bootlin Elixir — 커널 B-tree 구현 소스 코드입니다. 삽입, 삭제, 탐색, visitor 패턴 등 전체 알고리즘을 확인할 수 있습니다.
• include/linux/btree-128.h — Bootlin Elixir — 128비트 키 전용 인라인 래퍼 함수들을 정의합니다.
• include/linux/btree-type.h — Bootlin Elixir — 타입 안전 B-tree 매크로 템플릿입니다. 사용자 정의 키/값 타입의 B-tree를 생성할 때 사용합니다.
• Jonathan Corbet, "An in-kernel B-tree library" — LWN.net (2008) — Joern Engel이 LogFS를 위해 제안한 커널 내 B-tree 라이브러리의 설계 배경과 API를 소개하는 기사입니다.
• "LogFS — a new log-structured file system" — LWN.net (2008) — B-tree 라이브러리의 원래 사용처인 LogFS 파일 시스템의 설계와 구현을 설명합니다.
• lib/btree.c 커밋 히스토리 — git.kernel.org — Joern Engel의 최초 커밋부터 현재까지의 변경 이력을 추적할 수 있습니다.
• B-tree API 문서 — kernel.org — 커널 공식 문서에서 제공하는 B-tree API 레퍼런스입니다.
• B-tree — Wikipedia — B-tree 자료구조의 정의, 연산 복잡도, 변형(B+ tree, B* tree) 등을 포괄적으로 설명합니다.
• Cormen, T. H. et al. "Introduction to Algorithms" (CLRS) — Chapter 18: B-Trees에서 B-tree 삽입, 삭제, 분할 알고리즘의 이론적 기초를 다루는 표준 교재입니다.
• Bayer, R. & McCreight, E. "Organization and Maintenance of Large Ordered Indexes" (1970) — B-tree를 최초로 제안한 원논문입니다. 대용량 정렬 인덱스의 효율적 관리 방법을 정립했습니다.
• Comer, D. "The Ubiquitous B-Tree" — ACM Computing Surveys (1979) — B-tree의 다양한 변형과 응용을 종합적으로 정리한 서베이 논문입니다.