Generic Radix Tree (lib/generic-radix-tree)

리눅스 커널의 Generic Radix Tree를 심층 분석합니다. include/linux/generic-radix-tree.h와 lib/generic-radix-tree.c에 구현된 페이지(Page) 크기 노드 기반의 확장 가능 배열(Expandable Array)로, 기존 Radix Tree/XArray와는 완전히 별개의 자료구조입니다. genradix_ptr/genradix_ptr_alloc 등 핵심 API, 트리 깊이 동적 증가 메커니즘, bcachefs와 io_uring에서의 실제 활용 사례, 성능 특성과 디버깅 기법까지 커널 소스 기반으로 분석합니다.

개요: 왜 Generic Radix Tree인가

커널에는 이미 Radix Tree(include/linux/radix-tree.h)와 XArray(include/linux/xarray.h)라는 강력한 기수 트리(Radix Tree) 구현이 있습니다. 그런데 왜 별도의 Generic Radix Tree가 필요할까요?

설계 목적: 단순한 확장 가능 배열

기존 Radix Tree와 XArray는 키(Key)→포인터(Pointer) 매핑에 최적화되어 있습니다. 페이지 캐시(Page Cache)에서 오프셋(Offset)→페이지(Page) 매핑, IDR에서 ID→객체 매핑 등이 대표적입니다. 이들은 태그(Tag) 관리, 동시성 제어(RCU, spinlock), 예외 엔트리(Exception Entry) 등 풍부한 기능을 제공하지만, "단순히 인덱스로 접근하는 동적 배열"에는 과도한 복잡성입니다.

Generic Radix Tree는 이 틈새를 채웁니다:

Kent Overstreet는 bcachefs 파일시스템 개발 과정에서 "인덱스로 임의 크기 구조체(Struct)에 접근하는 단순한 자료구조"가 필요했습니다. 기존 flex_array(이후 제거됨)나 자체 동적 배열 대신, 기수 트리 구조를 활용하되 모든 노드를 페이지 크기로 통일한 깔끔한 설계를 선택했습니다.

구조체 분석

Generic Radix Tree의 핵심 자료구조는 놀라울 정도로 간결합니다. 전체 구현이 헤더 파일과 소스 파일 합쳐서 약 300줄에 불과합니다.

struct __genradix (루트 구조체)

/* include/linux/generic-radix-tree.h */
struct __genradix {
    struct genradix_root *root;
};

루트 구조체는 단일 포인터 하나뿐입니다. 이 포인터의 하위 비트(Bit)에 트리의 깊이(Depth) 정보가 인코딩(Encoding)됩니다.

genradix_root 포인터 인코딩

/* include/linux/generic-radix-tree.h */
#define GENRADIX_DEPTH_MASK  ((unsigned long) 3)  /* 하위 2비트 */

static inline struct genradix_node *genradix_root_to_node(
    struct genradix_root *r)
{
    return (struct genradix_node *)
        ((unsigned long) r & ~GENRADIX_DEPTH_MASK);
}

static inline unsigned genradix_root_to_depth(
    struct genradix_root *r)
{
    return (unsigned long) r & GENRADIX_DEPTH_MASK;
}

struct genradix_node (노드 구조체)

/* lib/generic-radix-tree.c */
struct genradix_node {
    union {
        /* 리프 노드: 실제 데이터가 저장되는 바이트 배열 */
        u8    data[PAGE_SIZE];

        /* 내부 노드: 자식 노드 포인터 배열 */
        struct genradix_node *children[PAGE_SIZE / sizeof(struct genradix_node *)];
    };
};

페이지당 객체 수 계산

/* include/linux/generic-radix-tree.h */
#define GENRADIX_NODE_SHIFT   PAGE_SHIFT  /* 12 (4KB) */
#define GENRADIX_NODE_SIZE    PAGE_SIZE   /* 4096 */

/* 한 리프 노드(페이지)에 들어가는 객체 수 */
#define GENRADIX_OBJS_PER_PAGE(type) \
    (PAGE_SIZE / sizeof(type))

/* 예시 계산 */
/* sizeof(u64) = 8  → 4096/8  = 512개/페이지 */
/* sizeof(u32) = 4  → 4096/4  = 1024개/페이지 */
/* struct bkey_cached (128B) → 4096/128 = 32개/페이지 */

핵심 API

Generic Radix Tree의 API는 매우 간결합니다. 타입 안전 래퍼 매크로를 통해 사용하며, 내부적으로 __genradix_* 함수를 호출합니다.

GENRADIX() 매크로: 타입 안전 선언

/* include/linux/generic-radix-tree.h */
#define GENRADIX(_type)                   \
struct {                                    \
    struct __genradix tree;                \
}

/* 사용 예 */
GENRADIX(struct my_entry) my_array;

/* 위 매크로가 확장되면: */
struct {
    struct __genradix tree;
} my_array;

genradix_init() / genradix_free()

/* 초기화: root를 NULL로 설정 */
#define genradix_init(_radix)              \
    __genradix_init(&(_radix)->tree)

static inline void __genradix_init(
    struct __genradix *radix)
{
    radix->root = NULL;
}

/* 해제: 모든 노드를 재귀적으로 free */
#define genradix_free(_radix)              \
    __genradix_free(&(_radix)->tree)

void __genradix_free(struct __genradix *radix);

genradix_ptr(): 읽기 전용 접근

/* 인덱스로 객체 포인터 반환 (할당하지 않음) */
#define genradix_ptr(_radix, _idx)         \
    ((__typeof__((_radix))0) *)          \
    __genradix_ptr(&(_radix)->tree,       \
        _idx, sizeof(*(_radix)0))

/* 내부 구현 */
void *__genradix_ptr(struct __genradix *radix,
                     size_t offset)
{
    struct genradix_root *r = radix->root;
    struct genradix_node *n;
    unsigned level;

    if (!r)
        return NULL;

    n     = genradix_root_to_node(r);
    level = genradix_root_to_depth(r);

    while (level) {
        unsigned idx = (offset >> (level * GENRADIX_NODE_SHIFT))
                     & (GENRADIX_NODE_SIZE / sizeof(void *) - 1);
        n = n->children[idx];
        if (!n)
            return NULL;
        level--;
    }

    return &n->data[offset & (GENRADIX_NODE_SIZE - 1)];
}

genradix_ptr_alloc(): 할당 포함 접근

/* 인덱스로 객체 포인터 반환 (필요시 노드 할당) */
#define genradix_ptr_alloc(_radix, _idx, _gfp) \
    ((__typeof__((_radix))0) *)               \
    __genradix_ptr_alloc(&(_radix)->tree,      \
        _idx, sizeof(*(_radix)0), _gfp)

void *__genradix_ptr_alloc(
    struct __genradix *radix,
    size_t offset,
    gfp_t gfp)
{
    struct genradix_root *r, *new_root;
    struct genradix_node *node, *new_node;
    unsigned level;

    /* 기존 트리에서 찾기 시도 */
restart:
    r = radix->root;

    if (r) {
        node  = genradix_root_to_node(r);
        level = genradix_root_to_depth(r);

        /* 현재 깊이로 인덱스 표현 가능한지 확인 */
        if (offset < genradix_depth_size(level)) {
            /* 경로를 따라 내려가며 필요한 노드 할당 */
            while (level) {
                unsigned idx = ...;
                if (!node->children[idx]) {
                    new_node = genradix_alloc_node(gfp);
                    if (!new_node)
                        return NULL;
                    node->children[idx] = new_node;
                }
                node = node->children[idx];
                level--;
            }
            return &node->data[offset & ...];
        }
    }

    /* 깊이 증가 필요: 새 루트 노드 삽입 */
    new_node = genradix_alloc_node(gfp);
    if (!new_node)
        return NULL;

    new_node->children[0] = node;
    new_root = (struct genradix_root *)
        ((unsigned long) new_node | (level + 1));

    if (cmpxchg(&radix->root, r, new_root) != r) {
        free_page((unsigned long) new_node);
        goto restart;
    }

    goto restart;
}

genradix_iter_peek() / genradix_for_each()

/* 반복자 구조체 */
struct genradix_iter {
    size_t offset;
    size_t pos;
};

#define genradix_iter_init(_radix, _idx)   \
    ((struct genradix_iter) {               \
        .offset = (_idx) * sizeof(...),    \
        .pos    = _idx,                       \
    })

/* 현재 위치의 객체를 반환하고, 없으면 다음 유효 객체로 이동 */
#define genradix_iter_peek(_radix, _iter)  \
    (__typeof__((_radix))0) *)              \
    __genradix_iter_peek(&(_radix)->tree, _iter, sizeof(...))

/* 전체 순회 매크로 */
#define genradix_for_each(_radix, _iter, _p) \
    for (_iter = genradix_iter_init(_radix, 0); \
         (_p = genradix_iter_peek(_radix, &_iter)) != NULL; \
         genradix_iter_advance(&_iter, sizeof(...)))

API 요약표

내부 구현

Generic Radix Tree의 내부 구현은 간결하면서도 정교합니다. 핵심은 인덱스를 트리 경로로 변환하는 방식과, 트리 깊이를 동적으로 늘리는 메커니즘입니다.

인덱스 → 경로 변환

바이트 오프셋(Byte Offset)을 트리 경로로 변환하는 과정을 살펴봅니다. 객체 인덱스는 먼저 바이트 오프셋으로 변환됩니다: offset = index * obj_size.

/* 깊이별 커버 가능한 최대 바이트 오프셋 */
static inline size_t genradix_depth_size(unsigned depth)
{
    return 1UL << (GENRADIX_NODE_SHIFT +
                   depth * (GENRADIX_NODE_SHIFT - ilog2(sizeof(void *))));
}

/* 64비트 시스템 (ptr=8B, PAGE_SIZE=4KB):
 * depth 0: 1 << 12         = 4KB     (리프 1개)
 * depth 1: 1 << (12+9)     = 2MB     (리프 512개)
 * depth 2: 1 << (12+18)    = 1GB     (리프 262144개)
 * depth 3: 1 << (12+27)    = 512GB   (리프 ~134M개)
 */

트리 깊이 동적 증가

인덱스 범위가 현재 트리 깊이로 표현할 수 없을 때, 루트 위에 새 내부 노드를 삽입하여 깊이를 늘립니다.

/* 깊이 증가 핵심 로직 (lib/generic-radix-tree.c) */
do {
    new_node = genradix_alloc_node(gfp);
    if (!new_node)
        return NULL;

    /* 기존 트리를 새 노드의 첫 번째 자식에 연결 */
    new_node->children[0] = node;

    /* 새 루트 = 새 노드 주소 | (깊이+1) */
    new_root = (struct genradix_root *)
        ((unsigned long) new_node | (level + 1));

    /* 원자적 교체: 다른 스레드와의 경합 방지 */
    if (cmpxchg_release(&radix->root, r, new_root) == r) {
        /* 성공: 깊이 증가 완료 */
        node  = new_node;
        level = level + 1;
        r     = new_root;
    } else {
        /* 실패: 다른 스레드가 먼저 변경함 → 새 노드 해제 후 재시도 */
        free_page((unsigned long) new_node);
        goto restart;
    }
} while (offset >= genradix_depth_size(level));

노드 할당과 해제

/* lib/generic-radix-tree.c */
static inline struct genradix_node *genradix_alloc_node(gfp_t gfp)
{
    return (struct genradix_node *)
        __get_free_page(gfp | __GFP_ZERO);
}

static void genradix_free_recurse(
    struct genradix_node *n, unsigned level)
{
    if (level) {
        unsigned i;
        for (i = 0; i < GENRADIX_NODE_SIZE / sizeof(void *); i++)
            if (n->children[i])
                genradix_free_recurse(n->children[i], level - 1);
    }
    free_page((unsigned long) n);
}

void __genradix_free(struct __genradix *radix)
{
    struct genradix_root *r = radix->root;

    if (r) {
        genradix_free_recurse(
            genradix_root_to_node(r),
            genradix_root_to_depth(r));
        radix->root = NULL;
    }
}

bcachefs 활용

Generic Radix Tree의 가장 중요한 사용처는 bcachefs 파일시스템입니다. Kent Overstreet가 bcachefs 개발을 위해 이 자료구조를 직접 작성했습니다.

키 캐시(Key Cache) 관리

/* fs/bcachefs/btree_key_cache_types.h */
struct bch_fs {
    /* ... */
    GENRADIX(struct btree_key_cache_freelist_entry)
        key_cache_freelist;
    /* ... */
};

bcachefs는 B-트리(B-Tree) 키 캐시의 프리리스트(Freelist)를 Generic Radix Tree로 관리합니다. 캐시 엔트리 수가 동적으로 변하므로 확장 가능 배열이 적합합니다.

스트라이프(Stripe) 관리

/* fs/bcachefs/ec_types.h */
struct ec_stripe_head;

struct bch_fs {
    /* 스트라이프 데이터를 인덱스로 관리 */
    GENRADIX(struct stripe) stripes;
    /* ... */
};

/* 스트라이프 접근 예 */
struct stripe *s = genradix_ptr(&c->stripes, idx);
if (s && s->alive) {
    /* 스트라이프 데이터 사용 */
}

오픈 버킷(Open Bucket) 추적

/* fs/bcachefs/alloc_types.h */
struct bch_fs {
    GENRADIX(struct bucket_gens) bucket_gens;
    /* 버킷 세대(Generation) 번호를 인덱스로 추적 */
};

/* 버킷 세대 조회 */
static inline u8 *bucket_gen(
    struct bch_dev *ca, size_t b)
{
    return genradix_ptr(&ca->bucket_gens, b);
}

기타 커널 활용

io_uring 활용

io_uring은 고성능 비동기 I/O 프레임워크(Framework)로, 요청(Request) 슬롯 관리에 Generic Radix Tree를 사용합니다.

/* io_uring/io_uring.c */
struct io_ring_ctx {
    /* ... */
    GENRADIX(struct io_rsrc_node *) rsrc_nodes;
    /* 리소스 노드를 인덱스로 관리 */
};

/* 리소스 노드 접근 */
struct io_rsrc_node **node_p;
node_p = genradix_ptr(&ctx->rsrc_nodes, index);
if (node_p && *node_p) {
    /* 리소스 노드 사용 */
}

기타 서브시스템

Generic Radix Tree의 사용처는 아직 많지 않습니다. 대부분의 커널 서브시스템은 기존 XArray나 Red-Black Tree, 해시 테이블(Hash Table) 등을 사용합니다. Generic Radix Tree는 "단순한 확장 가능 배열"이 필요한 특정 니치(Niche)에 적합합니다.

Radix Tree / XArray 비교

커널의 세 가지 기수 트리(Radix Tree) 계열 자료구조를 비교합니다.

언제 Generic Radix Tree를 선택하는가

• Generic Radix Tree 적합: 정수 인덱스 기반 배열, 임의 크기 객체 저장, 개별 삭제 불필요, 단순한 API 선호, 페이지 단위 할당 선호
• XArray 적합: 키→포인터 매핑, 태그/마크 필요, RCU 보호 필요, 개별 삭제 필요, 범용 사전(Dictionary) 용도
• 일반 배열/flex_array 적합: 크기가 고정이거나 작은 경우, 연속 메모리 필요

1. Q1: 키가 정수(인덱스)입니까?
   • 아니오 → 해시 테이블 또는 Red-Black Tree
   • 예 → Q2로 진행
2. Q2: 저장하는 값이 포인터입니까?
   • 예 → XArray (가장 범용적)
   • 아니오 (임의 크기 구조체) → Q3로 진행
3. Q3: 개별 삭제가 필요합니까?
   • 예 → XArray (포인터로 감싸서)
   • 아니오 → Q4로 진행
4. Q4: RCU 보호 읽기가 필요합니까?
   • 예 → XArray
   • 아니오 → Q5로 진행
5. Q5: 요소 수가 100개 이상입니까?
   • 아니오 → kmalloc 배열
   • 예 → Generic Radix Tree

성능 특성

메모리 오버헤드

요소 수가 적을 때는 페이지 단위 할당의 낭비가 크지만, 수백 개 이상이면 오버헤드가 급격히 감소합니다. bcachefs에서처럼 수천~수만 개의 요소를 관리할 때 효율적입니다.

접근 시간 분석

일반적으로 O(log₅₁₂(N))이며 이는 실질적으로 O(1)에 해당합니다. depth 3 이상은 거의 발생하지 않습니다.

캐시 효율

Generic Radix Tree의 리프 노드는 4KB 페이지이므로, 순차 순회 시 하드웨어 프리페처(Prefetcher)가 효과적으로 동작합니다. 64B 객체 기준으로 한 리프 내 64개 객체가 연속 메모리에 위치합니다.

디버깅

구조 시각화

디버거(Debugger)에서 Generic Radix Tree의 상태를 확인하는 방법입니다.

/* crash/drgn 등의 디버거에서 구조 확인 */

/* 1. root 포인터에서 노드 주소와 깊이 추출 */
unsigned long root_val = (unsigned long)radix->root;
unsigned depth = root_val & 3;
struct genradix_node *node =
    (struct genradix_node *)(root_val & ~3UL);

pr_info("genradix: root=%px depth=%u node=%px\n",
        radix->root, depth, node);

/* 2. 내부 노드의 자식 포인터 덤프 */
if (depth > 0) {
    unsigned i;
    for (i = 0; i < PAGE_SIZE / sizeof(void *); i++) {
        if (node->children[i])
            pr_info("  children[%u] = %px\n",
                    i, node->children[i]);
    }
}

/* 3. 리프 노드의 데이터 덤프 */
if (depth == 0) {
    print_hex_dump(KERN_INFO, "genradix data: ",
        DUMP_PREFIX_OFFSET, 16, 1,
        node->data, 256, true);
}

일반적인 문제

디버깅 팁

/* 트리 통계 출력 헬퍼 */
static void genradix_dump_stats(
    struct __genradix *radix, size_t obj_size)
{
    struct genradix_root *r = radix->root;
    unsigned depth;
    size_t max_objs, objs_per_page;

    if (!r) {
        pr_info("genradix: empty (root=NULL)\n");
        return;
    }

    depth = genradix_root_to_depth(r);
    objs_per_page = PAGE_SIZE / obj_size;
    max_objs = genradix_depth_size(depth) / obj_size;

    pr_info("genradix: depth=%u obj_size=%zu "
            "objs_per_page=%zu max_objs=%zu\n",
            depth, obj_size, objs_per_page, max_objs);
}

소스 코드 워크스루

genradix_ptr_alloc()의 전체 실행 흐름을 추적합니다. 빈 트리에 인덱스 1000번째 요소(obj_size=64B)를 처음 삽입하는 시나리오입니다.

시나리오: 빈 트리에 인덱스 1000 쓰기

/* 사용자 코드 */
GENRADIX(struct my_obj) tree;  /* sizeof(my_obj) = 64 */
genradix_init(&tree);               /* root = NULL */

struct my_obj *p = genradix_ptr_alloc(
    &tree, 1000, GFP_KERNEL);
/* p는 이제 인덱스 1000의 my_obj를 가리킴 */

해제 경로 추적

genradix_free(&tree) 호출 시 내부 동작은 다음과 같습니다:

1. root 포인터에서 depth=1, node 주소를 추출합니다
2. genradix_free_recurse(root_node, 1)을 호출합니다
3. level=1이므로 children[]을 순회합니다:
   • children[0] != NULL → genradix_free_recurse(children[0], 0) → level=0이므로 free_page(children[0])
   • children[1..14] == NULL → 건너뜁니다
   • children[15] != NULL → genradix_free_recurse(children[15], 0) → free_page(children[15])
4. free_page(root_node)로 내부 노드 자체를 해제합니다
5. radix->root = NULL로 리셋합니다

총 free_page 호출: 3회 (할당과 동일)

사용 예제

커널 모듈에서 Generic Radix Tree를 사용하는 완전한 예제입니다.

#include <linux/module.h>
#include <linux/generic-radix-tree.h>

struct my_entry {
    u32 id;
    u32 flags;
    u64 timestamp;
    char name[48];
};  /* sizeof = 64 바이트 → PAGE_SIZE/64 = 64개/페이지 */

static GENRADIX(struct my_entry) entries;

static int __init my_init(void)
{
    struct my_entry *e;
    struct genradix_iter iter;
    int i;

    genradix_init(&entries);

    /* 100개 엔트리 추가 */
    for (i = 0; i < 100; i++) {
        e = genradix_ptr_alloc(&entries, i, GFP_KERNEL);
        if (!e) {
            pr_err("alloc failed at %d\n", i);
            goto err;
        }
        e->id = i;
        e->flags = 0;
        e->timestamp = ktime_get_ns();
        snprintf(e->name, sizeof(e->name),
                 "entry-%d", i);
    }

    /* 특정 엔트리 조회 */
    e = genradix_ptr(&entries, 42);
    if (e)
        pr_info("entry 42: id=%u name=%s\n",
                e->id, e->name);

    /* 전체 순회 */
    genradix_for_each(&entries, iter, e) {
        pr_info("[%zu] id=%u ts=%llu\n",
                iter.pos, e->id, e->timestamp);
    }

    return 0;
err:
    genradix_free(&entries);
    return -ENOMEM;
}

static void __exit my_exit(void)
{
    genradix_free(&entries);
}

module_init(my_init);
module_exit(my_exit);
MODULE_LICENSE("GPL");

설계 세부사항

왜 PAGE_SIZE 노드인가

Generic Radix Tree가 슬랩(Slab) 할당 대신 페이지 할당을 사용하는 데는 명확한 이유가 있습니다.

/* 페이지 할당의 핵심 이점: 포인터 하위 비트 활용 */

/* __get_free_page()는 항상 PAGE_SIZE(4096) 정렬 반환
 * → 하위 12비트가 항상 0
 * → 하위 2비트를 깊이(depth) 저장에 활용 가능
 * → 별도의 깊이 필드 불필요 → struct __genradix가 포인터 1개로 충분 */

struct __genradix {
    struct genradix_root *root;
    /* 이것이 전부! 8바이트로 전체 트리를 관리 */
};

/* 만약 kmalloc을 사용했다면: */
struct __genradix_hypothetical {
    void *root;
    unsigned depth;        /* 별도 필드 필요 */
    size_t node_size;      /* 노드 크기도 저장 필요 */
};

동시성 모델

Generic Radix Tree는 내부적으로 최소한의 원자적 연산만 사용하며, 전체 동시성 제어는 호출자에게 위임합니다.

/* 내부 원자적 연산: 깊이 증가 시만 cmpxchg 사용 */
if (cmpxchg_release(&radix->root, old_root, new_root) != old_root) {
    /* 다른 스레드가 먼저 깊이를 늘림 → 새 노드 해제 후 재시도 */
    free_page((unsigned long) new_node);
    goto restart;
}

/* 호출자 책임: 동시 접근 보호 */
struct my_data {
    struct mutex lock;
    GENRADIX(struct my_entry) entries;
};

/* 쓰기 경로 */
mutex_lock(&data->lock);
e = genradix_ptr_alloc(&data->entries, idx, GFP_KERNEL);
if (e)
    e->value = new_value;
mutex_unlock(&data->lock);

/* 읽기 경로: 쓰기와 동시에 읽으면 안 됨 (RCU 미지원) */
mutex_lock(&data->lock);
e = genradix_ptr(&data->entries, idx);
if (e)
    process(e);
mutex_unlock(&data->lock);

메모리 0 초기화의 중요성

/* 노드 할당 시 __GFP_ZERO 필수 */
static inline struct genradix_node *genradix_alloc_node(gfp_t gfp)
{
    return (struct genradix_node *)
        __get_free_page(gfp | __GFP_ZERO);
}

/* __GFP_ZERO가 보장하는 것:
 *
 * 내부 노드:
 *   children[0..511] = NULL
 *   → genradix_ptr()가 미할당 경로에서 안전하게 NULL 반환
 *   → genradix_free_recurse()가 NULL 자식을 건너뜀
 *
 * 리프 노드:
 *   data[0..4095] = 0
 *   → 새로 할당된 객체가 자동으로 0 초기화
 *   → 호출자가 memset() 불필요
 *   → genradix_ptr_alloc() 후 즉시 사용 가능 (0값이 안전한 경우)
 */

객체 크기 제약

/* 객체 크기 제약사항 */

/* 1. obj_size는 PAGE_SIZE 이하여야 함 */
BUILD_BUG_ON(sizeof(type) > PAGE_SIZE);

/* 2. PAGE_SIZE가 obj_size의 배수일 때 가장 효율적 */
/* PAGE_SIZE=4096, obj_size=64:  4096/64  = 64개 (낭비 0) */
/* PAGE_SIZE=4096, obj_size=100: 4096/100 = 40개 (낭비 96B) */
/* PAGE_SIZE=4096, obj_size=3000: 4096/3000 = 1개 (낭비 1096B) */

/* 3. 2의 거듭제곱 크기를 권장 */
/* 정렬이 자연스럽고, 나눗셈이 시프트로 최적화됨 */
struct good_entry {   /* 64B - 완벽 */
    u64 fields[8];
};

struct ok_entry {     /* 128B - 양호 */
    u64 fields[16];
};

struct wasteful_entry { /* 3000B - 비효율적 */
    char data[3000];
    /* 페이지당 1개만 저장, 1096B 낭비 */
};

반복자(Iterator) 내부 구현

Generic Radix Tree의 반복자는 희소(Sparse) 배열에서 효율적으로 동작하도록 설계되어 있습니다.

__genradix_iter_peek() 상세

/* lib/generic-radix-tree.c */
void *__genradix_iter_peek(
    struct genradix_iter *iter,
    struct __genradix *radix,
    size_t objs_per_page)
{
    struct genradix_root *r;
    struct genradix_node *n;
    unsigned level, i;

restart:
    r = radix->root;
    if (!r)
        return NULL;

    n     = genradix_root_to_node(r);
    level = genradix_root_to_depth(r);

    /* 현재 오프셋이 트리 범위를 초과하면 종료 */
    if (iter->offset >= genradix_depth_size(level))
        return NULL;

    /* 트리를 내려가며 리프 탐색 */
    while (level) {
        i = (iter->offset >> (level * GENRADIX_NODE_SHIFT))
            & (GENRADIX_ARY - 1);

        if (!n->children[i]) {
            /* NULL 서브트리 → 다음 서브트리로 건너뛰기 */
            iter->offset = round_up(iter->offset + 1,
                1UL << (level * GENRADIX_NODE_SHIFT));
            iter->pos = iter->offset / objs_per_page;
            goto restart;
        }

        n = n->children[i];
        level--;
    }

    return &n->data[iter->offset & (PAGE_SIZE - 1)];
}

순회 성능: 희소 vs 밀집

고급 사용 패턴

Lookup-or-Create 패턴

/* 일반적인 패턴: 먼저 읽기, 없으면 생성 */
struct my_entry *get_or_create_entry(
    GENRADIX(struct my_entry) *tree,
    size_t idx)
{
    struct my_entry *e;

    /* 빠른 경로: 이미 할당된 경우 */
    e = genradix_ptr(tree, idx);
    if (e && e->initialized)
        return e;

    /* 느린 경로: 할당 필요 */
    e = genradix_ptr_alloc(tree, idx, GFP_KERNEL);
    if (!e)
        return ERR_PTR(-ENOMEM);

    if (!e->initialized) {
        e->id = idx;
        e->initialized = true;
    }
    return e;
}

배치 초기화 패턴

/* 대량 요소 사전 할당 */
static int preallocate_entries(
    GENRADIX(struct my_entry) *tree,
    size_t count)
{
    size_t i;

    for (i = 0; i < count; i++) {
        struct my_entry *e;

        e = genradix_ptr_alloc(tree, i, GFP_KERNEL);
        if (!e)
            return -ENOMEM;

        /* 0 초기화는 __GFP_ZERO가 보장하므로
         * 기본값이 0인 필드는 별도 초기화 불필요 */
        e->id = i;
    }
    return 0;
}

다양한 타입 활용

/* 포인터 배열로 사용 */
GENRADIX(struct task_struct *) task_table;

/* 단순 정수 배열로 사용 */
GENRADIX(u64) counter_array;
/* PAGE_SIZE/8 = 512개/페이지 */

/* 비트맵으로 사용 */
GENRADIX(unsigned long) bitmap;
/* 각 unsigned long에 64비트 → 페이지당 512*64 = 32,768비트 */

/* 큰 구조체 */
struct big_entry {
    char data[1024];
};
GENRADIX(struct big_entry) big_table;
/* PAGE_SIZE/1024 = 4개/페이지 */

개별 삭제 불가: 대안

/* Generic Radix Tree는 개별 요소 삭제를 지원하지 않음!
 * genradix_free()로 전체 해제만 가능 */

/* 대안 1: 유효성 플래그 사용 */
struct my_entry {
    bool valid;     /* false면 "삭제됨"으로 취급 */
    u32 data;
};

/* "삭제" = valid 플래그를 false로 */
e = genradix_ptr(&tree, idx);
if (e)
    e->valid = false;

/* 대안 2: 세대 번호(generation) 사용 */
struct versioned_entry {
    u32 generation;  /* 전역 세대와 불일치하면 무효 */
    u32 data;
};

/* 대안 3: 0 값을 "비어있음"으로 간주 */
/* __GFP_ZERO 덕분에 미사용 슬롯은 자연스럽게 0 */
e = genradix_ptr(&tree, idx);
if (e && e->id != 0) {
    /* 유효한 엔트리 */
}

제한사항과 대안

알려진 제한사항

사용하지 말아야 할 경우

• 키→값 사전: 문자열이나 복합 키로 검색이 필요하면 해시 테이블(Hash Table) 또는 Red-Black Tree를 사용합니다
• 빈번한 삭제: 요소를 자주 추가/삭제하면 XArray가 적합합니다
• RCU 보호 읽기: 잠금 없는(Lock-Free) 읽기가 필요하면 XArray를 사용합니다
• 소수 요소 (<64): 배열이 작으면 단순 kmalloc 배열이 더 효율적입니다
• 정렬 순회: 키 순서대로 순회가 필요하면 Red-Black Tree를 사용합니다

깊이별 용량 분석

Generic Radix Tree의 용량은 객체 크기와 트리 깊이에 따라 결정됩니다. 아키텍처(Architecture)별 포인터 크기에 따라 팬 아웃이 달라집니다.

64비트 시스템 (포인터 8바이트)

32비트 시스템 (포인터 4바이트)

/* 팬 아웃 계산 */
#define GENRADIX_ARY  (PAGE_SIZE / sizeof(void *))

/* 64비트: 4096 / 8  = 512 */
/* 32비트: 4096 / 4  = 1024 */

/* 깊이별 최대 바이트 오프셋 */
/* depth_size(d) = PAGE_SIZE * GENRADIX_ARY^d */
/*
 * 64비트:
 *   d=0: 4096 * 1    = 4KB
 *   d=1: 4096 * 512  = 2MB
 *   d=2: 4096 * 512^2 = 1GB
 *   d=3: 4096 * 512^3 = 512GB
 *
 * 32비트:
 *   d=0: 4096 * 1     = 4KB
 *   d=1: 4096 * 1024  = 4MB
 *   d=2: 4096 * 1024^2 = 4GB (전체 주소 공간)
 */

구현 역사

Generic Radix Tree는 Kent Overstreet의 bcachefs 프로젝트에서 탄생했습니다. bcachefs는 10년 이상의 개발 끝에 v6.7에서 mainline Linux에 머지되었으며, 이와 함께 Generic Radix Tree의 중요성도 높아졌습니다. 코드 자체는 매우 안정적이며, 초기 도입 이후 큰 API 변경 없이 유지되고 있습니다.

flex_array와의 관계

Generic Radix Tree 도입 이전에는 lib/flex_array.c가 유사한 역할을 했습니다. flex_array는 가변 크기의 배열을 페이지 단위로 관리했지만, 다음과 같은 문제가 있었습니다:

flex_array가 제거된 후, 그 역할의 상당 부분을 Generic Radix Tree가 대체하고 있습니다. flex_array가 고정 최대 크기를 요구한 반면, Generic Radix Tree는 필요에 따라 트리 깊이를 늘려 사실상 무제한 확장이 가능합니다.

향후 방향

Generic Radix Tree의 현재 구현은 매우 안정적이며, 대규모 변경보다는 점진적 개선이 예상됩니다:

• 개별 요소 삭제: 빈 리프 노드 자동 해제와 트리 축소 기능이 추가될 가능성이 있습니다
• RCU 읽기 지원: 읽기 경로의 잠금 없는(Lock-Free) 접근이 추가되면 더 많은 서브시스템에서 채택될 수 있습니다
• bcachefs 안정화: bcachefs가 성숙함에 따라 Generic Radix Tree의 사용 패턴도 최적화될 것입니다
• 문서화 개선: 커널 문서(Documentation/)에 공식 가이드가 추가될 가능성이 있습니다

genradix_delete(radix, idx) — 개별 요소 삭제

현재 미지원입니다. 특정 인덱스의 원소만 제거하는 기능입니다.

genradix_count(radix) — 사용 중인 요소 수 카운트

현재 미지원입니다. 트리에 저장된 유효 원소의 수를 반환하는 기능입니다.

genradix_ptr_rcu(radix, idx) — RCU 보호 읽기

현재 미지원입니다. 잠금 없이 RCU 보호 하에 원소를 읽는 기능입니다.

현재는 이 기능들이 필요하면 XArray 사용을 권장합니다.

Generic Radix Tree 메모리 레이아웃 심층

Generic Radix Tree의 핵심은 모든 노드가 정확히 PAGE_SIZE(4096바이트)라는 점입니다. 이 절에서는 깊이별 노드 배치, 인덱스에서 경로로의 변환 과정, 실제 메모리 사용량을 수식과 함께 상세히 분석합니다.

팬아웃(Fanout) 계산

내부 노드는 자식 포인터 배열을 저장합니다. 64비트 시스템에서 포인터 크기는 8바이트이므로, 하나의 내부 노드가 가질 수 있는 자식 수(팬아웃)는 다음과 같습니다.

/* 팬아웃 계산 — include/linux/generic-radix-tree.h */

/* 내부 노드의 자식 포인터 수 */
#define GENRADIX_NODE_SHIFT   (PAGE_SHIFT)          /* 12 (4KB 페이지) */
#define GENRADIX_NODE_SIZE    (1UL << GENRADIX_NODE_SHIFT)  /* 4096 */

/* 포인터 크기 = sizeof(void *) = 8 (64-bit) */
/* 팬아웃 = PAGE_SIZE / sizeof(void *) = 4096 / 8 = 512 */
#define GENRADIX_ARY          (GENRADIX_NODE_SIZE / sizeof(void *))  /* 512 */

/* 리프 노드의 슬롯 수는 원소 크기에 따라 달라짐 */
/* objs_per_leaf = PAGE_SIZE / obj_size */
/*   obj_size =   8B → 512개 */
/*   obj_size =  64B →  64개 */
/*   obj_size = 256B →  16개 */
/*   obj_size = 512B →   8개 */

struct genradix_node {
    union {
        /* 리프 노드: 원시 데이터 바이트 */
        u8  data[GENRADIX_NODE_SIZE];

        /* 내부 노드: 자식 포인터 배열 (최대 512개) */
        struct genradix_node *children[GENRADIX_ARY];
    };
};

깊이별 노드 배치

다음 다이어그램은 깊이 0부터 3까지의 트리 구조와 각 깊이에서 지원하는 최대 원소 수를 보여줍니다. 원소 크기가 64바이트인 경우를 기준으로 합니다.

인덱스 → 경로 변환

인덱스에서 트리 경로를 도출하는 과정은 바이트 오프셋 변환과 비트 분해로 이루어집니다. 다음은 원소 크기 64바이트에서 인덱스 1000을 조회하는 과정입니다.

/* 인덱스 → 경로 변환 과정 (obj_size = 64, depth = 1) */

/* 1단계: 바이트 오프셋 계산 */
size_t byte_offset = index * obj_size;
/* byte_offset = 1000 * 64 = 64000 = 0xFA00 */

/* 2단계: 필요한 깊이 결정 */
/* depth_size(d) = PAGE_SIZE << (PAGE_SHIFT * d) */
/* depth_size(0) = 4096 = 0x1000         → 64000 > 4096 (부족) */
/* depth_size(1) = 4096 << 12 = 16777216 → 64000 < 16MB  (충분) */
/* → 깊이 1이면 충분합니다 */

/* 3단계: 비트 분해로 경로 결정 */
/* PAGE_SHIFT = 12, 각 레벨은 PAGE_SHIFT(12) 비트씩 소비 */
/*
 * byte_offset = 0xFA00 = 0b 1111 1010 0000 0000
 *                              ↑↑↑↑          ↑↑↑↑
 *                         비트[20:12]     비트[11:0]
 *                         Level 1 idx    리프 내 오프셋
 */

/* Level 1 인덱스: (0xFA00 >> 12) & 0x1FF = 0xF = 15 */
unsigned level1_idx = (byte_offset >> PAGE_SHIFT) & (GENRADIX_ARY - 1);
/* level1_idx = 15 → root->children[15]로 이동 */

/* 리프 내 오프셋: 0xFA00 & 0xFFF = 0xA00 = 2560 */
unsigned leaf_offset = byte_offset & (PAGE_SIZE - 1);
/* leaf_offset = 2560 → &leaf->data[2560] 반환 */

/* 검증: 2560 / 64 = 40 → 리프 내 40번째 슬롯 */
/* 전체: children[15]의 40번째 = 15*64 + 40 = 1000번째 원소 ✓ */

실제 메모리 사용량 계산

원소 크기와 저장 개수에 따른 실제 메모리 사용량을 계산합니다. 내부 노드의 오버헤드를 포함한 정확한 값입니다.

메모리 사용량 계산 공식:

• objs_per_leaf = PAGE_SIZE / obj_size
• 필요한 리프 수 = ceil(N / objs_per_leaf)
• 내부 노드 수 = ceil(리프 수 / 512) (깊이 1) + ceil(위 결과 / 512) (깊이 2, 필요 시) + ...
• 총 메모리 = (리프 수 + 내부 노드 수) × PAGE_SIZE

메모리 효율이 높은 이유:

1. 노드가 정확히 PAGE_SIZE이므로 내부 단편화가 없습니다
2. Slab 할당자 메타데이터 오버헤드가 없습니다
3. 희소 배열(Sparse Array)일 때 미사용 영역에 메모리를 할당하지 않습니다

genradix_ptr_alloc 전체 경로 워크스루

__genradix_ptr_alloc은 Generic Radix Tree에서 가장 복잡한 함수입니다. 인덱스에 해당하는 슬롯의 포인터를 반환하되, 경로에 노드가 없으면 할당하고, 트리 깊이가 부족하면 루트 위에 새 노드를 삽입합니다. 이 절에서는 전체 실행 경로를 단계별로 추적합니다.

함수 전체 구조

/* lib/generic-radix-tree.c — __genradix_ptr_alloc 핵심 경로 */

void *__genradix_ptr_alloc(struct __genradix *radix,
                            size_t offset,
                            gfp_t gfp_mask)
{
    struct genradix_root *r, *new_root;
    struct genradix_node *node, *new_node;
    unsigned level;

    /* 1. 현재 루트와 깊이 읽기 */
    r = READ_ONCE(radix->root);
    /* root 포인터의 하위 비트에 깊이가 인코딩되어 있습니다 */

    /* 2. 트리가 비었거나 깊이가 부족하면 확장 */
    while (!r || offset >= genradix_depth_size(genradix_root_to_depth(r))) {
        new_node = (struct genradix_node *)
            __get_free_page(gfp_mask | __GFP_ZERO);
        if (!new_node)
            return NULL;

        if (!r) {
            /* 빈 트리: 새 노드를 depth=0 루트로 설정 */
            new_root = genradix_depth_to_root(0, new_node);
        } else {
            /* 깊이 확장: 새 노드를 루트로, 기존 루트를 자식[0]으로 */
            new_node->children[0] = genradix_root_to_node(r);
            new_root = genradix_depth_to_root(
                genradix_root_to_depth(r) + 1, new_node);
        }

        /* 3. cmpxchg로 원자적 루트 교체 시도 */
        if (cmpxchg(&radix->root, r, new_root) != r) {
            /* 다른 스레드가 먼저 교체 → 할당 해제 후 재시도 */
            free_page((unsigned long)new_node);
            r = READ_ONCE(radix->root);
            continue;
        }
        r = new_root;
    }

    /* 4. 루트에서 리프까지 경로 탐색 */
    node = genradix_root_to_node(r);
    level = genradix_root_to_depth(r);

    while (level--) {
        unsigned idx = (offset >> (PAGE_SHIFT * (level + 1)))
                       & (GENRADIX_ARY - 1);
        struct genradix_node **child = &node->children[idx];

        if (!*child) {
            /* 중간 노드 또는 리프 할당 */
            new_node = (struct genradix_node *)
                __get_free_page(gfp_mask | __GFP_ZERO);
            if (!new_node)
                return NULL;
            *child = new_node;
        }
        node = *child;
    }

    /* 5. 리프 노드 내 바이트 오프셋 위치 반환 */
    return &node->data[offset & (PAGE_SIZE - 1)];
}

깊이 확장 과정

트리 깊이가 부족할 때의 확장 과정을 3단계로 보여줍니다. 기존 트리의 데이터를 이동하지 않고, 루트 위에 새 노드를 추가하는 것이 핵심입니다.

cmpxchg 동시성 상세

스레드 A와 B가 동시에 깊이 확장을 시도하는 시나리오:

초기 상태: root = (leaf_node | depth=0)

이 패턴의 장점:

1. spinlock/mutex 없이 동작하므로 읽기 경로에 오버헤드가 없습니다
2. 경쟁 실패 시 비용은 한 페이지 할당+해제뿐이며, 이는 드문 경우에만 발생합니다
3. ABA 문제가 없습니다. 깊이는 단조 증가하므로 같은 값으로 돌아오지 않습니다

genradix_iter와 순회 내부

Generic Radix Tree의 반복자(Iterator)는 트리의 모든 유효한 원소를 순서대로 방문합니다. 이 절에서는 struct genradix_iter의 내부 구조, genradix_iter_peek의 노드 탐색 알고리즘, genradix_for_each 매크로의 확장 결과를 분석합니다.

struct genradix_iter 분석

/* include/linux/generic-radix-tree.h — 반복자 구조체 */

struct genradix_iter {
    size_t           offset;    /* 현재 바이트 오프셋 */
    size_t           pos;       /* 현재 논리 인덱스 (offset / obj_size) */
};

/* 초기화 매크로 */
#define genradix_iter_init(_radix, _idx)    \
    ((struct genradix_iter) {                \
        .offset = (_idx) * (_radix)->_type_size, \
        .pos    = (_idx),                        \
    })

/* 핵심 이해: offset과 pos의 관계 */
/* offset = pos * obj_size */
/* offset은 트리 내부 탐색에, pos는 사용자 콜백에 사용됩니다 */

/* 예: obj_size=64, pos=100 → offset=6400 */
/*     offset으로 트리 경로를 계산하고, */
/*     pos를 사용자에게 현재 인덱스로 전달합니다 */

genradix_iter_peek 내부 동작

/* lib/generic-radix-tree.c — __genradix_iter_peek 핵심 로직 */

void *__genradix_iter_peek(struct genradix_iter *iter,
                            struct __genradix *radix,
                            size_t objs_per_leaf)
{
    struct genradix_root *r;
    struct genradix_node *node;
    unsigned level, i;

restart:
    r = READ_ONCE(radix->root);
    if (!r)
        return NULL;

    /* 현재 오프셋이 트리 범위를 넘으면 종료 */
    if (iter->offset >= genradix_depth_size(genradix_root_to_depth(r)))
        return NULL;

    node = genradix_root_to_node(r);
    level = genradix_root_to_depth(r);

    while (level) {
        i = (iter->offset >> (PAGE_SHIFT * level)) & (GENRADIX_ARY - 1);

        if (!node->children[i]) {
            /* NULL 서브트리 발견: 다음 유효한 서브트리로 건너뛰기 */
            size_t skip_size = 1UL << (PAGE_SHIFT * level);
            iter->offset = (iter->offset | (skip_size - 1)) + 1;
            iter->pos    = iter->offset / (PAGE_SIZE / objs_per_leaf);
            goto restart;
        }

        node = node->children[i];
        level--;
    }

    /* 리프 도달: 데이터 포인터 반환 */
    return &node->data[iter->offset & (PAGE_SIZE - 1)];
}

genradix_for_each 매크로 확장

/* include/linux/generic-radix-tree.h — genradix_for_each 매크로 */

#define genradix_for_each(_radix, _iter, _p)                    \
    for (_iter = genradix_iter_init(_radix, 0);                  \
         (_p = genradix_iter_peek(&_iter, _radix)) != NULL;     \
         genradix_iter_advance(&_iter, _radix))

/* 확장 결과 (obj_size = 64 기준): */
/*
 * for (_iter = (struct genradix_iter){ .offset = 0, .pos = 0 };
 *      (_p = __genradix_iter_peek(&_iter, &radix->tree, 64)) != NULL;
 *      _iter.offset += 64, _iter.pos++) {
 *     // _p는 현재 원소를 가리키는 포인터
 *     // _iter.pos는 현재 논리 인덱스
 * }
 */

/* genradix_for_each_from — 특정 인덱스부터 시작 */
#define genradix_for_each_from(_radix, _iter, _idx, _p)          \
    for (_iter = genradix_iter_init(_radix, _idx);               \
         (_p = genradix_iter_peek(&_iter, _radix)) != NULL;     \
         genradix_iter_advance(&_iter, _radix))

/* 사용 예: 인덱스 500부터 순회 */
struct my_obj *obj;
struct genradix_iter iter;

genradix_for_each_from(&my_radix, iter, 500, obj) {
    pr_info("index %zu: value = %d\n", iter.pos, obj->value);
    if (iter.pos >= 1000)
        break;  /* 범위 제한 순회 */
}

bcachefs에서의 실전 활용 상세

Generic Radix Tree는 Kent Overstreet가 bcachefs 파일시스템을 위해 만든 자료구조입니다. 이 절에서는 bcachefs에서 genradix가 구체적으로 어떤 구조체에, 어떤 목적으로 사용되는지, 그리고 왜 XArray 대신 genradix를 선택했는지를 분석합니다.

스트라이프(Stripe) 관리

/* fs/bcachefs/ec_types.h, fs/bcachefs/ec.h — 스트라이프 관리 */

/* bcachefs의 Erasure Coding (EC) 스트라이프 정보 */
struct stripe {
    size_t      heap_idx;       /* 힙에서의 위치 */
    u16         nr_blocks;      /* 스트라이프 내 블록 수 */
    u16         nr_redundant;   /* 패리티 블록 수 */
    u16         blocks_nonempty;/* 비어있지 않은 블록 수 */
    unsigned    alive:1;        /* 활성 여부 */
    unsigned    on_heap:1;      /* 힙에 존재 여부 */
};

/* bch_fs 구조체 내에서의 선언 (fs/bcachefs/bcachefs.h) */
struct bch_fs {
    /* ... 다른 필드들 ... */

    struct {
        /* 스트라이프 인덱스로 스트라이프 정보 조회 */
        GENRADIX(struct stripe)  stripes;

        /* 스트라이프 힙: GC 대상 선정에 사용 */
        HEAP(struct stripe_heap_entry) heap;

        size_t                     nr_stripes;
    } ec_stripes;

    /* ... */
};

/* GENRADIX(struct stripe)는 다음과 같이 확장됩니다: */
/*
 * struct {
 *     struct __genradix tree;
 * }
 *
 * sizeof(struct stripe)가 작으므로 (보통 16~24B)
 * 한 리프에 170~256개 스트라이프 정보를 저장할 수 있습니다.
 */

/* 스트라이프 접근 패턴 */
static inline struct stripe *genradix_ptr(
    &c->ec_stripes.stripes, stripe_idx)
{
    /* 스트라이프 번호로 즉시 접근: O(깊이) = O(1~3) */
}

/* 스트라이프 순회: 모든 활성 스트라이프 확인 */
struct stripe *s;
struct genradix_iter iter;

genradix_for_each(&c->ec_stripes.stripes, iter, s) {
    if (s->alive && s->blocks_nonempty < s->nr_blocks)
        /* GC 후보: 부분적으로 비어있는 스트라이프 */
        bch2_stripe_queue_gc(c, iter.pos);
}

스냅샷(Snapshot) 관리

/* fs/bcachefs/snapshot.h — 스냅샷 테이블 */

struct snapshot_t {
    u32     parent;         /* 부모 스냅샷 ID */
    u32     children[2];    /* 자식 스냅샷 (최대 2개: 바이너리 트리) */
    u32     depth;          /* 스냅샷 트리 깊이 */
    u32     skip[3];        /* 스킵 리스트 포인터 */
    u32     equiv;          /* 동등 스냅샷 (live 아닌 경우) */
    bool    live;           /* 활성 스냅샷 여부 */
};

/* bch_fs 내 스냅샷 테이블 선언 */
struct bch_fs {
    struct {
        GENRADIX(struct snapshot_t)  table;
        /* 스냅샷 ID로 인덱싱: table[snapshot_id] */
    } snapshots;
};

/* 왜 XArray가 아닌 genradix인가? */
/*
 * 1. 단순성: genradix는 ~200줄, XArray는 ~4000줄
 *    → 버그 표면적이 적고 검증이 쉽습니다
 * 2. 객체 직접 저장: XArray는 포인터만 저장, genradix는 임의 크기 객체 저장
 *    → kmalloc 없이 genradix 노드 안에 직접 저장됩니다
 * 3. GFP_KERNEL 전용: genradix는 슬립 가능 컨텍스트에서만 사용
 *    → IRQ/atomic 안전이 불필요하므로 락 설계가 단순합니다
 * 4. 안정적 포인터: 한번 할당된 슬롯의 주소가 변하지 않습니다
 *    → XArray는 내부 재조정으로 포인터가 무효화될 수 있습니다
 * 5. 일관된 성능: 트리 리밸런싱이 없어 최악 시간이 예측 가능합니다
 */

io_uring에서의 genradix 활용

io_uring 서브시스템에서도 genradix를 사용하여 고정 파일(Fixed File)과 고정 버퍼(Fixed Buffer) 테이블을 관리합니다. 등록된 파일 디스크립터와 버퍼를 인덱스로 빠르게 조회하는 데 활용됩니다.

/* io_uring에서의 genradix 활용 패턴 */

/* io_uring 컨텍스트 (io_uring/io_uring.h) */
struct io_ring_ctx {
    /* ... */

    /* 고정 파일 테이블: 등록된 fd를 인덱스로 조회 */
    struct io_rsrc_data     *file_data;
    /* file_data 내부에서 genradix 사용: */
    /* GENRADIX(struct io_rsrc_node *) 형태 */

    /* 고정 버퍼 테이블 */
    struct io_rsrc_data     *buf_data;

    unsigned                nr_user_files;
    unsigned                nr_user_bufs;
    /* ... */
};

/* 등록된 파일을 genradix로 조회하는 패턴 */
static struct file *io_file_from_index(
    struct io_ring_ctx *ctx, int fd)
{
    struct io_rsrc_node **node_ptr;

    /* genradix_ptr로 인덱스 기반 조회 */
    node_ptr = genradix_ptr(&ctx->file_data->nodes, fd);
    if (!node_ptr || !*node_ptr)
        return NULL;

    return (*node_ptr)->file;
}

/* io_uring에서 genradix를 선택한 이유: */
/*
 * 1. 등록 시(IORING_REGISTER_FILES) GFP_KERNEL 허용
 *    → genradix_ptr_alloc의 제약과 일치
 * 2. 조회 시(submission path)는 읽기만 필요
 *    → genradix_ptr이 락프리이므로 고성능 경로에 적합
 * 3. fd 번호가 0부터 순차적 → 희소 배열이 아니므로 메모리 효율적
 * 4. 파일 수 변경 시 genradix_free 후 새로 구축
 *    → 부분 수정보다 전체 교체가 더 안전
 */

genradix 사용 판단 기준

genradix가 적합한 경우:

1. 정수 인덱스로 접근하는 동적 배열이 필요할 때
2. 임의 크기 구조체를 직접 저장해야 할 때 (포인터가 아님)
3. 프로세스 컨텍스트에서만 할당/해제할 때
4. 한번 저장한 원소의 주소가 변하지 않아야 할 때
5. RCU 보호가 필요 없을 때
6. 단순한 구현을 선호할 때 (디버깅, 감사 용이성)

genradix가 부적합한 경우 (대안 포함):

실제 커널 사용 통계 (v6.8 기준, 대략적):

• genradix 사용처: ~30개 파일 (주로 bcachefs, io_uring)
• XArray 사용처: ~500개 이상 파일 (범용)
• 기존 radix-tree: ~100개 파일 (레거시, 점진적 XArray 전환 중)

에러 처리와 메모리 해제

Generic Radix Tree의 에러 처리는 할당 실패(OOM)와 메모리 해제에 집중됩니다. genradix_free는 트리의 모든 노드를 깊이 우선(DFS) 방식으로 해제하며, 할당 실패 시에는 부분 트리가 남는 것이 아니라 이전 상태가 유지됩니다.

genradix_free 구현

/* lib/generic-radix-tree.c — __genradix_free 구현 */

static void genradix_free_recurse(struct genradix_node *node,
                                   unsigned level)
{
    if (level) {
        /* 내부 노드: 자식부터 재귀적으로 해제 */
        unsigned i;
        for (i = 0; i < GENRADIX_ARY; i++)
            if (node->children[i])
                genradix_free_recurse(node->children[i], level - 1);
    }
    /* 자식 해제 후 자신을 해제 (post-order) */
    free_page((unsigned long)node);
}

void __genradix_free(struct __genradix *radix)
{
    struct genradix_root *r = radix->root;

    if (r) {
        genradix_free_recurse(genradix_root_to_node(r),
                              genradix_root_to_depth(r));
        radix->root = NULL;
    }
}

/* 호출 예 */
GENRADIX(struct my_obj) my_radix;

/* 사용 후 해제 */
genradix_free(&my_radix);
/* → __genradix_free(&my_radix.tree) 호출 */
/* → root부터 DFS로 모든 노드의 페이지를 free_page()로 반환 */
/* → radix->root = NULL로 초기화 */

해제 비용 분석

/* genradix_free 비용 분석 — 실제 시나리오별 */

/*
 * 시나리오 1: 소규모 배열 (1,000개 64B 객체, depth=1)
 *   리프 노드: ceil(1000/64) = 16개
 *   내부 노드: 1개 (루트)
 *   총 free_page 호출: 17회
 *   예상 시간: ~17µs (free_page 평균 ~1µs)
 *
 * 시나리오 2: 대규모 배열 (1,000,000개 64B 객체, depth=2)
 *   리프 노드: ceil(1000000/64) = 15,625개
 *   L1 내부 노드: ceil(15625/512) = 31개
 *   L2 루트: 1개
 *   총 free_page 호출: 15,657회
 *   예상 시간: ~15.7ms
 *
 * 시나리오 3: 희소 배열 (인덱스 0, 999,999만 사용, depth=2)
 *   리프 노드: 2개 (인덱스 0이 있는 리프, 999,999가 있는 리프)
 *   L1 내부 노드: 2개 (각 리프의 부모)
 *   L2 루트: 1개
 *   총 free_page 호출: 5회
 *   예상 시간: ~5µs
 */

/* 해제 시 주의사항 */
/*
 * 1. genradix_free는 슬립할 수 있음 (free_page → buddy allocator)
 *    → 원자적 컨텍스트(spinlock, IRQ)에서 호출 금지
 *
 * 2. 해제 중 동시 접근 방지 필요
 *    → 호출자가 외부 동기화 보장해야 함
 *    → 모듈에서는 /proc 제거 후 호출하는 패턴 사용
 *
 * 3. 부분 해제 API 없음
 *    → 특정 인덱스만 해제하는 것은 불가능
 *    → 슬롯 값을 0으로 memset하는 것으로 대체
 *    → 메모리는 genradix_free까지 반환되지 않음
 */

/* 부분 무효화 패턴 */
struct my_obj *obj = genradix_ptr(&radix, idx);
if (obj) {
    memset(obj, 0, sizeof(*obj));
    /* 슬롯은 0으로 초기화되지만 리프 페이지는 유지됨 */
    /* genradix_for_each에서 id==0 체크로 건너뛸 수 있음 */
}

할당 실패 시 동작

/* 할당 실패 시나리오 분석 */

/*
 * genradix_ptr_alloc에서 __get_free_page가 실패하는 경우:
 *
 * 시나리오 1: 루트 확장 중 실패
 * - 새 내부 노드 할당 실패 → NULL 반환
 * - 기존 트리는 변경되지 않음 (cmpxchg 전이므로)
 * - 안전: 트리가 이전 상태 그대로 유지됩니다
 *
 * 시나리오 2: 경로 탐색 중 중간 노드 할당 실패
 * - children[idx] = NULL 상태에서 새 노드 할당 실패
 * - NULL 반환
 * - 주의: 루트 확장은 이미 완료되었을 수 있음
 *   → 깊이는 늘었지만 리프는 없는 상태 (빈 서브트리)
 *   → genradix_ptr은 NULL을 반환하므로 안전
 *   → genradix_free는 NULL 자식을 건너뛰므로 안전
 *
 * 시나리오 3: OOM Killer 상황
 * - GFP_KERNEL은 직접 회수(reclaim)를 시도
 * - 그래도 실패하면 NULL 반환
 * - 호출자가 에러 처리 필요:
 */

struct my_obj *obj = genradix_ptr_alloc(&radix, idx, GFP_KERNEL);
if (!obj) {
    /* 할당 실패 처리 */
    pr_err("genradix: 인덱스 %zu 할당 실패\n", idx);

    /* 선택 1: 에러 반환 */
    return -ENOMEM;

    /* 선택 2: 재시도 (메모리가 확보될 때까지) */
    /* schedule_timeout_uninterruptible(HZ); */
    /* goto retry; */
}

/* GFP_NOWAIT 사용 시: 슬립 없이 즉시 실패 가능 */
obj = genradix_ptr_alloc(&radix, idx, GFP_NOWAIT);
/* → 메모리 압박 시 높은 확률로 NULL 반환 */

/* genradix_init을 사용한 명시적 초기화 */
/* (보통은 0으로 초기화된 구조체에 포함되어 불필요) */
genradix_init(&my_radix);
/* → radix->root = NULL 설정 */

커널 모듈 실전 예제

다음은 Generic Radix Tree를 사용하는 완전한 커널 모듈 예제입니다. 초기화, 원소 추가, 순회, /proc 인터페이스를 통한 데이터 조회, 그리고 정리(Cleanup)까지 전체 흐름을 포함합니다.

/* genradix_demo.c — Generic Radix Tree 커널 모듈 예제 */

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <linux/generic-radix-tree.h>

#define DEMO_MAX_ENTRIES  1024

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Generic Radix Tree 데모 모듈");

/* 저장할 구조체 정의 */
struct demo_entry {
    u32  id;              /* 항목 ID */
    u32  value;           /* 데이터 값 */
    u64  timestamp;       /* 생성 시각 (jiffies) */
    char name[16];        /* 항목 이름 */
};
/* sizeof(struct demo_entry) = 32 */
/* objs_per_leaf = 4096 / 32 = 128 */

/* genradix 선언: 타입 안전 래퍼 */
static GENRADIX(struct demo_entry) demo_radix;
static size_t demo_count;

/* /proc/genradix_demo 표시 콜백 */
static int demo_show(struct seq_file *m, void *v)
{
    struct demo_entry *entry;
    struct genradix_iter iter;

    seq_printf(m, "%-6s %-8s %-16s %s\n",
               "Index", "ID", "Name", "Value");
    seq_puts(m, "--------------------------------------\n");

    /* genradix_for_each: 모든 유효 원소 순회 */
    genradix_for_each(&demo_radix, iter, entry) {
        if (entry->id == 0)
            continue;  /* 미초기화 슬롯 건너뛰기 */

        seq_printf(m, "%-6zu %-8u %-16s %u\n",
                   iter.pos, entry->id,
                   entry->name, entry->value);
    }

    seq_printf(m, "\n총 %zu개 항목\n", demo_count);
    return 0;
}

static int demo_open(struct inode *inode, struct file *file)
{
    return single_open(file, demo_show, NULL);
}

static const struct proc_ops demo_proc_ops = {
    .proc_open    = demo_open,
    .proc_read    = seq_read,
    .proc_lseek   = seq_lseek,
    .proc_release = single_release,
};

/* 모듈 초기화 */
static int __init demo_init(void)
{
    struct demo_entry *entry;
    size_t i;

    /* genradix 초기화 (0으로 선언했으므로 사실 불필요) */
    genradix_init(&demo_radix);

    /* 샘플 데이터 삽입 */
    for (i = 0; i < DEMO_MAX_ENTRIES; i++) {
        /* 희소 패턴: 짝수 인덱스만 사용 */
        size_t idx = i * 2;

        entry = genradix_ptr_alloc(&demo_radix, idx, GFP_KERNEL);
        if (!entry) {
            pr_err("genradix_demo: 인덱스 %zu 할당 실패\n", idx);
            goto err_free;
        }

        entry->id        = i + 1;
        entry->value     = i * 100;
        entry->timestamp = jiffies;
        snprintf(entry->name, sizeof(entry->name),
                 "item-%04zu", i);
    }
    demo_count = DEMO_MAX_ENTRIES;

    /* /proc 인터페이스 생성 */
    if (!proc_create("genradix_demo", 0444, NULL, &demo_proc_ops)) {
        pr_err("genradix_demo: /proc 생성 실패\n");
        goto err_free;
    }

    pr_info("genradix_demo: %zu개 항목 로드 완료\n", demo_count);
    return 0;

err_free:
    genradix_free(&demo_radix);
    return -ENOMEM;
}

/* 모듈 정리 */
static void __exit demo_exit(void)
{
    remove_proc_entry("genradix_demo", NULL);
    genradix_free(&demo_radix);
    pr_info("genradix_demo: 모듈 언로드 완료\n");
}

module_init(demo_init);
module_exit(demo_exit);

빌드 및 실행

# Makefile — 커널 모듈 빌드

obj-m += genradix_demo.o

KDIR ?= /lib/modules/$(shell uname -r)/build

all:
	make -C $(KDIR) M=$(PWD) modules

clean:
	make -C $(KDIR) M=$(PWD) clean

# 빌드 및 로드
$ make
$ sudo insmod genradix_demo.ko
$ dmesg | tail -1
[  123.456] genradix_demo: 1024개 항목 로드 완료

# 데이터 조회
$ cat /proc/genradix_demo
Index  ID       Name             Value
--------------------------------------
0      1        item-0000        0
2      2        item-0001        100
4      3        item-0002        200
...
2046   1024     item-1023        102300

총 1024개 항목

# 메모리 사용량 확인
# 1024개 × 32B = 32KB 데이터
# 리프: ceil(2048/128) = 16개 × 4KB = 64KB (인덱스 0~2046 범위)
# 내부: 1개 × 4KB = 4KB
# 총: 68KB (데이터 32KB + 오버헤드 36KB)
# 희소 배열이므로 연속 배열(2047×32=64KB)보다 약간 큰 정도

# 모듈 언로드
$ sudo rmmod genradix_demo
$ dmesg | tail -1
[  456.789] genradix_demo: 모듈 언로드 완료

고급 패턴: genradix_ptr을 통한 읽기 전용 접근

/* 읽기 전용 접근 — genradix_ptr vs genradix_ptr_alloc 선택 기준 */

/* genradix_ptr: 읽기 전용, 할당하지 않음 */
struct demo_entry *entry = genradix_ptr(&demo_radix, idx);
if (!entry) {
    /* 해당 인덱스의 리프가 아직 할당되지 않음 */
    /* → 원소가 존재하지 않는다는 의미 */
    pr_info("인덱스 %zu: 존재하지 않음\n", idx);
    return -ENOENT;
}

/* entry가 NULL이 아니면 리프 내 해당 슬롯의 포인터 */
/* 단, 해당 슬롯에 의미있는 데이터가 있는지는 별도 확인 필요 */
if (entry->id == 0) {
    /* 리프는 할당되었지만 이 슬롯은 미사용 */
    /* (__get_free_page | __GFP_ZERO로 0 초기화됨) */
    return -ENOENT;
}

/* 읽기 전용 접근은 동시성에 안전합니다: */
/* - genradix_ptr은 락프리 */
/* - 이미 할당된 리프의 주소는 변하지 않음 */
/* - 단, 다른 스레드가 값을 쓰고 있으면 torn read 가능 */
/*   (크기가 워드보다 크면 별도 락 필요) */

pr_info("인덱스 %zu: id=%u, value=%u, name=%s\n",
        idx, entry->id, entry->value, entry->name);

커널 내장 테스트(KUnit) 분석

커널 소스에는 Generic Radix Tree의 정확성을 검증하는 KUnit 테스트가 포함되어 있습니다. lib/test_generic-radix-tree.c의 주요 테스트 케이스를 분석합니다.

/* lib/test_generic-radix-tree.c — KUnit 테스트 분석 */

/* 테스트 1: 기본 할당과 조회 */
static void test_basic(struct kunit *test)
{
    GENRADIX(u64) radix;
    u64 *ptr;
    int i;

    genradix_init(&radix);

    /* 연속 삽입 */
    for (i = 0; i < 1000; i++) {
        ptr = genradix_ptr_alloc(&radix, i, GFP_KERNEL);
        KUNIT_ASSERT_NOT_NULL(test, ptr);
        *ptr = i * 100;
    }

    /* 조회 검증 */
    for (i = 0; i < 1000; i++) {
        ptr = genradix_ptr(&radix, i);
        KUNIT_ASSERT_NOT_NULL(test, ptr);
        KUNIT_EXPECT_EQ(test, *ptr, (u64)(i * 100));
    }

    /* 범위 밖 조회: NULL 반환 확인 */
    ptr = genradix_ptr(&radix, 100000);
    KUNIT_EXPECT_NULL(test, ptr);

    genradix_free(&radix);
}

/* 테스트 2: 깊이 확장 검증 */
static void test_depth_expansion(struct kunit *test)
{
    GENRADIX(u8) radix;
    u8 *ptr;

    genradix_init(&radix);

    /* depth 0: 인덱스 0~4095 */
    ptr = genradix_ptr_alloc(&radix, 0, GFP_KERNEL);
    KUNIT_ASSERT_NOT_NULL(test, ptr);

    /* depth 0→1 확장 트리거: 인덱스 4096 */
    ptr = genradix_ptr_alloc(&radix, 4096, GFP_KERNEL);
    KUNIT_ASSERT_NOT_NULL(test, ptr);
    *ptr = 42;

    /* 기존 인덱스 0의 데이터가 보존되는지 확인 */
    ptr = genradix_ptr(&radix, 0);
    KUNIT_ASSERT_NOT_NULL(test, ptr);

    /* 확장 후 인덱스 4096 데이터 확인 */
    ptr = genradix_ptr(&radix, 4096);
    KUNIT_ASSERT_NOT_NULL(test, ptr);
    KUNIT_EXPECT_EQ(test, *ptr, (u8)42);

    genradix_free(&radix);
}

/* 테스트 3: 순회 검증 */
static void test_iteration(struct kunit *test)
{
    GENRADIX(u32) radix;
    struct genradix_iter iter;
    u32 *ptr;
    size_t count = 0;

    genradix_init(&radix);

    /* 희소 삽입: 인덱스 0, 100, 200 */
    ptr = genradix_ptr_alloc(&radix, 0, GFP_KERNEL);
    *ptr = 10;
    ptr = genradix_ptr_alloc(&radix, 100, GFP_KERNEL);
    *ptr = 20;
    ptr = genradix_ptr_alloc(&radix, 200, GFP_KERNEL);
    *ptr = 30;

    /* genradix_for_each는 리프가 있는 모든 슬롯을 방문 */
    /* 주의: NULL 리프는 건너뛰지만, 리프 내 0 값 슬롯은 방문함 */
    genradix_for_each(&radix, iter, ptr) {
        if (*ptr != 0)
            count++;
    }
    /* count == 3 (값이 있는 슬롯만 카운트) */
    KUNIT_EXPECT_EQ(test, count, (size_t)3);

    genradix_free(&radix);
}

/* KUnit 테스트 실행 방법: */
/* ./tools/testing/kunit/kunit.py run --kunitconfig=lib/Kconfig */
/* 또는 menuconfig에서 CONFIG_GENERIC_RADIX_TREE_TEST=y 설정 후 부팅 */

주소 계산 심층 분석

genradix_ptr()와 genradix_ptr_alloc()가 인덱스에서 실제 메모리 주소를 도출하는 과정을 커널 소스 레벨에서 분석합니다. 핵심은 바이트 오프셋의 비트 필드를 트리 레벨별 슬롯 인덱스로 분해하는 것입니다.

genradix_ptr() 주소 계산 전체 경로

/* lib/generic-radix-tree.c — __genradix_ptr 주소 계산 */

/* 호출자: genradix_ptr(&radix, idx) 매크로가
 *   __genradix_ptr(&radix->tree, idx * sizeof(type))를 호출합니다
 *   → 인덱스가 바이트 오프셋으로 변환되어 전달됩니다 */

void *__genradix_ptr(struct __genradix *radix,
                      size_t offset)
{
    struct genradix_root *r = READ_ONCE(radix->root);
    struct genradix_node *n;
    unsigned level;

    if (!r)
        return NULL;

    n     = genradix_root_to_node(r);
    /* n = (genradix_node *)((unsigned long)r & ~3UL)
     * 하위 2비트를 마스킹하여 노드 주소를 추출합니다 */

    level = genradix_root_to_depth(r);
    /* level = (unsigned long)r & 3
     * 하위 2비트가 트리 깊이(0~3)를 나타냅니다 */

    /* 현재 깊이로 offset을 수용할 수 있는지 확인 */
    if (offset >= genradix_depth_size(level))
        return NULL;
    /* depth_size(d) = 1UL << (PAGE_SHIFT + d * ilog2(GENRADIX_ARY))
     * 64비트: depth_size(0)=4KB, (1)=2MB, (2)=1GB, (3)=512GB */

    /* 루트에서 리프까지 경로 추적 */
    while (level) {
        /* 현재 레벨에서의 슬롯 인덱스를 비트 시프트+마스크로 추출 */
        unsigned idx = (offset >> (level * PAGE_SHIFT))
                     & (GENRADIX_ARY - 1);
        /* PAGE_SHIFT=12, GENRADIX_ARY=512 (64비트)
         * level=2: (offset >> 24) & 511 → L2 슬롯
         * level=1: (offset >> 12) & 511 → L1 슬롯 */

        n = n->children[idx];
        if (!n)
            return NULL;
        /* NULL 자식 = 해당 범위에 데이터 없음 */

        level--;
    }

    /* 리프 노드 도달: 바이트 오프셋의 하위 12비트가 data[] 인덱스 */
    return &n->data[offset & (PAGE_SIZE - 1)];
    /* offset & 0xFFF → 리프 페이지 내 0~4095 바이트 위치 */
}

genradix_ptr_alloc() 할당 경로 분석

genradix_ptr_alloc()는 genradix_ptr()와 동일한 주소 계산을 수행하되, 경로상에 NULL 노드가 있으면 새 페이지를 할당합니다. 두 함수의 차이를 비교합니다.

/* genradix_ptr vs genradix_ptr_alloc 경로 비교 */

/* ┌─────────────────┬────────────────────┬────────────────────────┐
 * │ 조건             │ genradix_ptr       │ genradix_ptr_alloc     │
 * ├─────────────────┼────────────────────┼────────────────────────┤
 * │ root == NULL    │ return NULL        │ 새 리프 할당 (depth=0) │
 * │ depth 부족      │ return NULL        │ 루트 위에 노드 삽입    │
 * │ children[i]==NULL│ return NULL       │ 새 노드 할당           │
 * │ 리프 도달       │ &data[off]         │ &data[off] (동일)      │
 * └─────────────────┴────────────────────┴────────────────────────┘ */

/* genradix_ptr_alloc의 할당 단계 상세 */

/* 단계 A: 빈 트리이거나 깊이 부족 시 트리 확장 */
while (!r || offset >= genradix_depth_size(
                          genradix_root_to_depth(r))) {
    /* 새 페이지 할당: __get_free_page(gfp | __GFP_ZERO) */
    new_node = genradix_alloc_node(gfp);

    if (!r) {
        /* 빈 트리: new_node가 depth=0 리프로 설정 */
        new_root = (void *)((unsigned long)new_node | 0);
    } else {
        /* 깊이 확장: 기존 루트를 new_node->children[0]에 연결 */
        new_node->children[0] = genradix_root_to_node(r);
        new_root = (void *)((unsigned long)new_node |
                           (genradix_root_to_depth(r) + 1));
    }

    /* cmpxchg: 원자적 루트 교체 */
    if (cmpxchg(&radix->root, r, new_root) == r)
        r = new_root;  /* 성공 → 계속 */
    else {
        free_page((unsigned long)new_node);  /* 실패 → 해제 */
        r = READ_ONCE(radix->root);        /* 최신 루트 재읽기 */
    }
}

/* 단계 B: 리프까지 경로 탐색 + 누락 노드 할당 */
node = genradix_root_to_node(r);
level = genradix_root_to_depth(r);

while (level--) {
    unsigned idx = (offset >> (PAGE_SHIFT * (level + 1)))
                   & (GENRADIX_ARY - 1);

    if (!node->children[idx]) {
        /* NULL 자식 → 새 페이지 할당 */
        new_node = genradix_alloc_node(gfp);
        if (!new_node)
            return NULL;  /* OOM: 부분 경로는 그대로 유지 */
        node->children[idx] = new_node;
    }
    node = node->children[idx];
}

/* 단계 C: 리프 도달 → genradix_ptr과 동일한 반환 */
return &node->data[offset & (PAGE_SIZE - 1)];

다중 깊이 주소 계산 예시

깊이 2 트리에서 인덱스 100,000(obj_size=64B)에 접근하는 전체 주소 계산 과정입니다.

/* 다중 깊이 주소 계산 예시: depth=2, obj_size=64, index=100000 */

/* 1. 바이트 오프셋 */
size_t offset = 100000 * 64;  /* = 6,400,000 = 0x61A800 */

/* 2. 깊이 확인 */
/* depth_size(1) = 2MB  = 2,097,152  → 6.4M > 2M (부족) */
/* depth_size(2) = 1GB  = 1,073,741,824 → 6.4M < 1G (충분) */
/* → depth=2 필요 */

/* 3. 비트 분해 (3단계 경로) */
/*
 * offset = 0x61A800
 * = 0b 0000 0000 0110 0001 1010 1000 0000 0000
 *              ↑↑↑↑↑↑↑↑↑    ↑↑↑↑↑↑↑↑↑    ↑↑↑↑↑↑↑↑↑↑↑↑
 *              bit[23:12]   bit[11:0]은    리프 내 오프셋
 *              불필요(L2)   추후 계산      (이 경우 0x800)
 */

/* L2 (루트 → 중간 노드): */
unsigned l2_idx = (0x61A800 >> 24) & 0x1FF;
/* = 0x0 & 0x1FF = 0 → children[0] */

/* L1 (중간 노드 → 리프): */
unsigned l1_idx = (0x61A800 >> 12) & 0x1FF;
/* = 0x61A & 0x1FF = 0x1A = 26 → children[26] */

/* 리프 내 오프셋: */
unsigned leaf_off = 0x61A800 & 0xFFF;
/* = 0x800 = 2048 → data[2048] */
/* 슬롯 번호 = 2048 / 64 = 32 */

/* 경로: root->children[0]->children[26]->data[2048] */
/* 포인터 역참조: 3회 (depth + 1) */
/* 검증: children[0]의 자식 26 × 리프당 64개 + 슬롯 32 */
/* = 0*32768 + 26*64 + 32 = 1696번째? → 아닙니다! */
/* 정확한 계산: L2*512*64 + L1*64 + slot = 0*32768 + 26*64 + 32 */
/* ... 이것은 리프 기준 인덱스입니다. 원래 인덱스: */
/* 전체: L2*(512*64) + L1*64 + slot = 0 + 1664 + 32 = 1696 */
/* 하지만 원래 인덱스는 100000? 차이: offset 기반이기 때문 */
/* 실제: L2 커버 = 2MB/64 = 32768개, L1 커버 = 4KB/64 = 64개 */
/* index = l2 * 32768 + l1 * 64 + slot */
/* = 0 * 32768 + ... (이 계산이 아니라 byte_offset 기반!) */
/* genradix는 인덱스가 아닌 byte_offset으로 경로를 결정합니다 */
/* 따라서 경로는 바이트 오프셋 6,400,000의 비트 분해로 결정됩니다 */

고정 크기 원소 저장: XArray/Radix Tree 비교

커널의 세 가지 기수 트리 구현이 "고정 크기 원소를 인덱스로 관리"하는 시나리오에서 어떻게 다른지 비교합니다. Generic Radix Tree가 이 용도에 최적화된 이유를 코드 레벨에서 분석합니다.

XArray로 고정 크기 원소 저장 시 문제

/* XArray로 64바이트 구조체를 저장하는 경우 */

struct my_obj {
    u64 fields[8];  /* 64바이트 */
};

/* XArray 방식: 별도 kmalloc + 포인터 저장 */
struct xarray xa;
xa_init(&xa);

struct my_obj *obj = kmalloc(sizeof(*obj), GFP_KERNEL);
xa_store(&xa, 42, obj, GFP_KERNEL);
/* 문제점:
 * 1. kmalloc 오버헤드: 슬랩 메타데이터 + 정렬 패딩
 * 2. 이중 간접 참조: xa_load()가 void* 반환 → 역참조 필요
 * 3. 메모리 산재: 각 obj가 독립 할당 → 캐시 효율 저하
 * 4. 개별 kfree 필요: 해제 시 N번의 kfree 호출
 */

/* 총 메모리 (1000개 저장 시): */
/*   XArray 노드: ~16 * 576B = ~9KB */
/*   kmalloc 객체: 1000 * (64 + 슬랩 오버헤드) ≈ 80~96KB */
/*   합계: ~89~105KB */

/* Generic Radix Tree 방식: 직접 저장 */
GENRADIX(struct my_obj) radix;
genradix_init(&radix);

struct my_obj *obj2 = genradix_ptr_alloc(&radix, 42, GFP_KERNEL);
/* 장점:
 * 1. 별도 kmalloc 없음: 객체가 리프 페이지 내에 직접 저장
 * 2. 단일 간접 참조: 반환 포인터가 곧 객체 포인터
 * 3. 메모리 연속: 같은 리프 내 객체들이 연속 배치 → 캐시 친화
 * 4. 일괄 해제: genradix_free() 한 번으로 전체 정리
 */

/* 총 메모리 (1000개 저장 시): */
/*   리프 16개: 16 * 4KB = 64KB */
/*   내부 노드 1개: 4KB */
/*   합계: 68KB (XArray 대비 ~30% 절약) */

시나리오별 상세 비교

안정적 포인터(Stable Pointer) 보장

/* Generic Radix Tree의 중요한 특성: 포인터 안정성 */

/* genradix_ptr_alloc()이 반환한 포인터는 genradix_free()까지 유효합니다 */
struct my_obj *p1 = genradix_ptr_alloc(&radix, 10, GFP_KERNEL);
struct my_obj *p2 = genradix_ptr_alloc(&radix, 999999, GFP_KERNEL);
/* p1은 여전히 유효합니다!
 * 깊이 확장(0→1→2)이 발생해도 기존 리프 노드는 이동하지 않습니다.
 * 새 루트가 기존 트리를 children[0]에 연결할 뿐입니다. */

p1->fields[0] = 42;  /* 안전: p1이 가리키는 리프 페이지는 그대로 */

/* 반면 일부 자료구조는 이 보장을 제공하지 않습니다: */
/* - realloc 기반 배열: 확장 시 전체 복사 → 기존 포인터 무효 */
/* - 일부 해시 테이블: 리해시(Rehash) 시 포인터 무효 가능 */
/* - XArray: 내부 구조 변경 시 값(포인터) 자체는 보존되지만
 *           XArray에 직접 객체를 저장하는 것이 아니므로 해당 없음 */

/* bcachefs가 genradix를 선택한 핵심 이유 중 하나: */
/* 스트라이프 포인터를 여러 곳에서 캐시해도 안전합니다 */
struct stripe *s = genradix_ptr(&c->ec_stripes.stripes, idx);
/* 이후 다른 스트라이프가 추가되어 트리가 확장되어도 s는 유효 */

트리 성장 시각화

Generic Radix Tree가 원소 추가에 따라 어떻게 성장하는지 단계별로 시각화합니다. obj_size=64B (리프당 64개) 기준입니다.

실전 패턴: 밀집 정수 인덱스 배열

Generic Radix Tree를 밀집(Dense) 정수 인덱스 배열로 활용하는 실전 패턴을 분석합니다. 이 패턴은 bcachefs의 버킷 세대(Bucket Generation) 관리와 io_uring의 리소스 테이블에서 실제로 사용됩니다.

밀집 카운터 배열

/* 패턴: CPU별 통계 카운터를 genradix로 관리 */

struct per_cpu_stat {
    u64 rx_packets;
    u64 tx_packets;
    u64 rx_bytes;
    u64 tx_bytes;
};  /* sizeof = 32B → objs_per_leaf = 128 */

static GENRADIX(struct per_cpu_stat) cpu_stats;

/* 초기화: 모든 CPU에 대해 사전 할당 */
static int stats_init(void)
{
    unsigned int cpu;

    genradix_init(&cpu_stats);

    /* nr_cpu_ids 만큼 사전 할당하여 런타임 할당 실패 방지 */
    for (cpu = 0; cpu < nr_cpu_ids; cpu++) {
        struct per_cpu_stat *s;

        s = genradix_ptr_alloc(&cpu_stats, cpu, GFP_KERNEL);
        if (!s)
            goto err;
        /* __GFP_ZERO로 자동 0 초기화 완료 */
    }
    return 0;

err:
    genradix_free(&cpu_stats);
    return -ENOMEM;
}

/* 런타임 업데이트 (소프트IRQ 컨텍스트에서 호출 가능) */
static void stats_update(unsigned int cpu,
                          u64 rx_pkts, u64 tx_pkts)
{
    struct per_cpu_stat *s;

    /* 사전 할당했으므로 genradix_ptr()로 충분 (할당 불필요) */
    s = genradix_ptr(&cpu_stats, cpu);
    if (likely(s)) {
        s->rx_packets += rx_pkts;
        s->tx_packets += tx_pkts;
    }
}

/* 통계 수집: 모든 CPU의 합산 */
static void stats_aggregate(struct per_cpu_stat *total)
{
    struct per_cpu_stat *s;
    struct genradix_iter iter;

    memset(total, 0, sizeof(*total));

    /* genradix_for_each: 할당된 리프만 순회 */
    genradix_for_each(&cpu_stats, iter, s) {
        total->rx_packets += s->rx_packets;
        total->tx_packets += s->tx_packets;
        total->rx_bytes   += s->rx_bytes;
        total->tx_bytes   += s->tx_bytes;
    }
}

bcachefs 버킷 세대 관리 패턴

/* fs/bcachefs/buckets.h — 버킷 세대 번호 관리 */

/* bcachefs는 디바이스를 버킷(Bucket) 단위로 나누어 관리합니다.
 * 각 버킷에는 세대(Generation) 번호가 있어 재사용 시 증가합니다.
 * 이를 통해 오래된 포인터를 감지합니다. */

struct bch_dev {
    /* 버킷 번호 → 세대 번호 매핑 */
    GENRADIX(u8) bucket_gens;
    /* sizeof(u8)=1 → objs_per_leaf = 4096
     * 한 리프에 4096개 버킷의 세대 번호를 저장합니다 */
};

/* 버킷 세대 조회 */
static inline u8 *bucket_gen(
    struct bch_dev *ca, size_t b)
{
    return genradix_ptr(&ca->bucket_gens, b);
}

/* 사용 패턴: 버킷 할당 시 세대 증가 */
u8 *gen = bucket_gen(ca, bucket_idx);
if (gen)
    (*gen)++;
/* 세대 값이 255(u8 최대)를 넘으면 0으로 래핑됩니다.
 * bcachefs는 이를 고려하여 세대 비교 시 래핑을 처리합니다. */

/* 메모리 효율 분석: 1TB SSD, 버킷 크기 512KB인 경우 */
/*   버킷 수 = 1TB / 512KB = 2,097,152 (2M) */
/*   obj_size = 1 (u8) → objs_per_leaf = 4096 */
/*   리프 수 = 2M / 4096 = 512 */
/*   내부 노드 = 1 (depth=1, 512 슬롯 정확히 채움) */
/*   총 메모리 = 513 × 4KB = 2,052KB ≈ 2MB */
/*   비교: 단순 배열 = 2M × 1B = 2MB (동일!) */
/*   → 밀집 배열에서 genradix 오버헤드는 내부 노드 1개(4KB)뿐 */

io_uring 리소스 테이블 패턴

/* io_uring의 리소스 관리에서 genradix 활용 */

/* io_uring은 등록된 파일/버퍼를 고정 테이블로 관리합니다.
 * 사용자가 io_uring_register()로 파일 디스크립터를 등록하면,
 * 이후 SQE에서 인덱스로 직접 참조할 수 있습니다. */

struct io_ring_ctx {
    /* 등록된 파일 테이블 */
    GENRADIX(struct io_rsrc_node *) rsrc_data;
    /* sizeof(ptr)=8 → objs_per_leaf = 512 */
};

/* 파일 등록 시: */
struct io_rsrc_node **slot;
slot = genradix_ptr_alloc(&ctx->rsrc_data, idx, GFP_KERNEL);
if (!slot)
    return -ENOMEM;
*slot = node;  /* 포인터를 리프의 해당 슬롯에 저장 */

/* SQE 처리 시 (hot path): */
struct io_rsrc_node **slot;
slot = genradix_ptr(&ctx->rsrc_data, sqe->fd);
if (slot && *slot) {
    /* 등록된 파일 사용: 커널 fd 테이블 접근 생략 */
    io_req_set_rsrc_node(req, *slot);
}

/* 왜 genradix인가? */
/* 1. 사용자가 등록할 수 있는 파일 수가 가변적 (최대 수만 개) */
/* 2. 인덱스 기반 O(1) 접근이 SQE 처리 핫 패스에서 필수 */
/* 3. 등록/해제 빈도가 낮고, 조회 빈도가 매우 높음 */
/* 4. 전체 해제 시 genradix_free 한 번으로 정리 */

안전한 래퍼 함수 패턴

/* 프로덕션 코드에서 권장하는 genradix 래퍼 패턴 */

struct my_subsys {
    struct mutex             lock;
    GENRADIX(struct my_obj)  objects;
    size_t                   nr_objects;
    size_t                   max_objects;
};

/* 안전한 추가: 잠금 + 범위 검사 + 할당 에러 처리 */
static struct my_obj *subsys_add_object(
    struct my_subsys *ss, size_t idx)
{
    struct my_obj *obj;

    if (idx >= ss->max_objects)
        return ERR_PTR(-ERANGE);

    mutex_lock(&ss->lock);

    obj = genradix_ptr_alloc(&ss->objects, idx, GFP_KERNEL);
    if (!obj) {
        mutex_unlock(&ss->lock);
        return ERR_PTR(-ENOMEM);
    }

    /* 중복 추가 방지 */
    if (obj->initialized) {
        mutex_unlock(&ss->lock);
        return ERR_PTR(-EEXIST);
    }

    obj->initialized = true;
    obj->id = idx;
    ss->nr_objects++;

    mutex_unlock(&ss->lock);
    return obj;
}

/* 안전한 조회: 잠금 + 유효성 검사 */
static struct my_obj *subsys_get_object(
    struct my_subsys *ss, size_t idx)
{
    struct my_obj *obj;

    mutex_lock(&ss->lock);

    obj = genradix_ptr(&ss->objects, idx);
    if (!obj || !obj->initialized)
        obj = NULL;

    mutex_unlock(&ss->lock);
    return obj;
}

/* 정리: 전체 해제 */
static void subsys_cleanup(struct my_subsys *ss)
{
    mutex_lock(&ss->lock);
    genradix_free(&ss->objects);
    ss->nr_objects = 0;
    mutex_unlock(&ss->lock);
}

참고 자료

커널 소스

• include/linux/generic-radix-tree.h -- API 선언과 타입 안전 매크로, GENRADIX() 매크로 정의
• lib/generic-radix-tree.c -- 핵심 구현 (~200줄): __genradix_ptr, __genradix_ptr_alloc, __genradix_free, __genradix_iter_peek
• fs/bcachefs/ -- 주요 사용처 (Kent Overstreet의 Copy-on-Write 파일시스템)
• io_uring/ -- 비동기 I/O 프레임워크의 리소스 관리에 사용
• lib/test_generic-radix-tree.c -- 커널 내장 단위 테스트 (kunit)

커널 문서

• Generic Radix Trees - Core API -- 커널 공식 문서의 API 레퍼런스

외부 자료

• LWN: The generic radix tree -- 도입 배경과 설계 논의
• 초기 커밋: generic radix trees -- v5.0 머지 커밋
• bcachefs 공식 사이트 -- Kent Overstreet의 파일시스템 프로젝트

관련 문서

• Radix Tree (레거시) -- 기존 Radix Tree 구현과 역사
• XArray -- 현재 커널 표준 기수 트리 구현
• 메모리 관리 개요 -- 페이지 할당과 물리 메모리 구조
• Slab Allocator (SLUB) -- kmalloc 기반 할당과의 비교
• 페이지 할당자 (Buddy Allocator) -- __get_free_page의 내부 구현
• Red-Black Tree -- 커널의 또 다른 트리 자료구조