Radix Tree (레거시)

Linux 커널의 Radix Tree는 정수 키 기반 매핑(Mapping)을 제공하는 자료구조로, 4.20 커널 이전까지 페이지 캐시(Page Cache)의 핵심이었습니다. 현재는 XArray로 대체되었지만, 레거시 코드 이해와 역사적 맥락을 위해 학습이 필요합니다.

개요 (Overview)

Radix Tree는 다음과 같은 특징을 가집니다:

• 정수 키 매핑 — unsigned long 키를 포인터에 매핑합니다.
• 희소 배열 — 빈 공간이 많아도 메모리 효율적입니다.
• 태그 — 각 항목에 여러 비트 플래그를 붙일 수 있습니다.
• RCU 지원 — lockless read를 위한 RCU 버전이 있습니다.

구조 (Structure)

/* include/linux/radix-tree.h (레거시) */
struct radix_tree_root {
    gfp_t gfp_mask;
    struct radix_tree_node __rcu *rnode;
};

struct radix_tree_node {
    unsigned char shift;
    unsigned char offset;
    unsigned char count;
    unsigned char exceptional;
    struct radix_tree_node *parent;
    struct radix_tree_root *root;
    void __rcu *slots[RADIX_TREE_MAP_SIZE];
    unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

#define RADIX_TREE_MAP_SHIFT 6  /* 64개 슬롯 */
#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)

Radix Tree 내부 구조

Radix Tree는 64-way 트리로, 인덱스의 6비트씩을 사용하여 경로를 결정합니다:

레거시 API

기본 연산

/* 초기화 */
RADIX_TREE_INIT(my_tree, GFP_KERNEL);
void INIT_RADIX_TREE(struct radix_tree_root *root, gfp_t gfp_mask);

/* 삽입 */
int radix_tree_insert(struct radix_tree_root *root,
                        unsigned long index, void *item);

/* 검색 */
void *radix_tree_lookup(struct radix_tree_root *root,
                           unsigned long index);

/* 삭제 */
void *radix_tree_delete(struct radix_tree_root *root,
                           unsigned long index);

/* 사용 예 */
struct radix_tree_root page_tree;
INIT_RADIX_TREE(&page_tree, GFP_KERNEL);

struct page *page = alloc_page(GFP_KERNEL);
radix_tree_insert(&page_tree, 42, page);

struct page *found = radix_tree_lookup(&page_tree, 42);

radix_tree_delete(&page_tree, 42);

태그 연산

/* 태그 설정 */
void *radix_tree_tag_set(struct radix_tree_root *root,
                           unsigned long index, unsigned int tag);

/* 태그 제거 */
void *radix_tree_tag_clear(struct radix_tree_root *root,
                             unsigned long index, unsigned int tag);

/* 태그 확인 */
int radix_tree_tag_get(struct radix_tree_root *root,
                         unsigned long index, unsigned int tag);

/* 페이지 캐시 예: dirty 태그 */
#define PAGECACHE_TAG_DIRTY 0
#define PAGECACHE_TAG_WRITEBACK 1

radix_tree_tag_set(&mapping->i_pages, index, PAGECACHE_TAG_DIRTY);

태그 비트맵 구조

Radix Tree의 태그 시스템은 각 항목에 여러 플래그를 비트맵으로 관리합니다:

페이지 캐시에서의 사용

Radix Tree는 페이지 캐시의 핵심이었습니다:

/* include/linux/fs.h (4.20 이전) */
struct address_space {
    struct radix_tree_root i_pages;  /* 페이지 캐시 */
    /* ... */
};

/* mm/filemap.c */
struct page *find_get_page(struct address_space *mapping,
                           pgoff_t offset)
{
    struct page *page;

    rcu_read_lock();
    page = radix_tree_lookup(&mapping->i_pages, offset);
    if (page && !get_page_unless_zero(page))
        page = NULL;
    rcu_read_unlock();

    return page;
}

XArray로 전환

Linux 4.20부터 Radix Tree는 XArray로 대체되었습니다:

변환 예제

/* 기존 Radix Tree 코드 */
struct radix_tree_root my_tree;
INIT_RADIX_TREE(&my_tree, GFP_KERNEL);
radix_tree_insert(&my_tree, 42, ptr);
void *result = radix_tree_lookup(&my_tree, 42);
radix_tree_delete(&my_tree, 42);

/* XArray로 변환 */
struct xarray my_xarray;
xa_init(&my_xarray);
xa_store(&my_xarray, 42, ptr, GFP_KERNEL);
void *result = xa_load(&my_xarray, 42);
xa_erase(&my_xarray, 42);

XArray 마이그레이션 체크리스트

왜 대체되었나

XArray가 Radix Tree를 대체한 이유:

1. API 복잡성 — Radix Tree API는 배우기 어려웠습니다.
2. 메모리 오버헤드(Overhead) — 내부 노드 구조가 비효율적이었습니다.
3. 잠금 복잡성 — RCU 동기화가 복잡했습니다.
4. 확장성 — 대규모 데이터셋에서 성능 문제가 있었습니다.

Radix Tree vs XArray 메모리 레이아웃

Radix Tree와 XArray의 메모리 구조 차이를 비교합니다:

레거시 코드 이해

4.20 이전 커널 코드를 분석할 때 알아야 할 패턴:

/* 태그 기반 순회 (dirty page 찾기) */
struct page *page;
unsigned long index = 0;

while ((page = radix_tree_gang_lookup_tag(
            &mapping->i_pages, (void **)&page, index,
            1, PAGECACHE_TAG_DIRTY)) != NULL) {
    /* process dirty page */
    index = page->index + 1;
}

/* XArray 등가 코드 */
unsigned long index;
struct page *page;

xa_for_each_marked(&mapping->i_pages, index, page,
                   XA_MARK_DIRTY) {
    /* process dirty page */
}

성능 특성

Legacy Radix Tree 유지보수 노트

Radix Tree는 XArray로 대체되었지만 레거시 코드 유지보수에서는 여전히 만납니다. 신규 구현은 XArray를 우선하고, 기존 경로 수정 시에는 RCU/예외 엔트리 규칙을 깨지 않도록 주의해야 합니다.

1. 신규 코드 여부 판단: 신규면 XArray 사용, 레거시면 최소 수정 원칙
2. 예외 엔트리 처리: NULL/exceptional entry 구분 경로 확인
3. 동시성 규칙: reader의 RCU 보호 여부 확인
4. 마이그레이션 가능성: API 매핑표로 XArray 전환 계획 수립

# 레거시 사용 지점 검색
git grep -n "radix_tree_" -- "*.c" "*.h"

# XArray 전환 후보 탐색
git grep -n "radix_tree_lookup\\|radix_tree_insert\\|radix_tree_delete" -- "*.c"

Multi-order 엔트리

Radix Tree는 단일 인덱스에 하나의 엔트리를 저장하는 것이 기본이지만, 커널 4.6부터 multi-order entry 기능이 추가되어 하나의 엔트리가 연속된 여러 슬롯을 차지할 수 있게 되었습니다. 이는 THP(Transparent Huge Pages)를 페이지 캐시에서 효율적으로 관리하기 위해 도입되었습니다.

radix_tree_insert()에 order 매개변수 사용

Multi-order 삽입은 __radix_tree_insert() 내부에서 order 값에 따라 여러 슬롯에 동일한 엔트리(또는 sibling 엔트리)를 배치합니다.

/* lib/radix-tree.c - multi-order insert (커널 4.6~4.20) */
static int __radix_tree_insert(struct radix_tree_root *root,
                                unsigned long index,
                                unsigned order,
                                void *item)
{
    struct radix_tree_node *node;
    void __rcu **slot;
    int error;

    BUG_ON(radix_tree_is_internal_node(item));

    /* 삽입 위치 탐색: order에 맞게 정렬된 index 사용 */
    error = __radix_tree_create(root, index, order, &node, &slot);
    if (error)
        return error;

    /* order > 0이면 sibling 슬롯도 함께 설정 */
    error = insert_entries(node, slot, item, order, false);
    if (error < 0)
        return error;

    /* 필요시 태그 전파 */
    if (node) {
        unsigned offset = get_slot_offset(node, slot);
        BUG_ON(tag_get(node, 0, offset));
        BUG_ON(tag_get(node, 1, offset));
        BUG_ON(tag_get(node, 2, offset));
    }

    return 0;
}

THP(Transparent Huge Pages)와의 관계

페이지 캐시에서 THP를 지원하기 위해 multi-order 엔트리가 도입되었습니다. 2MB huge page(order=9)를 페이지 캐시에 저장할 때, 512개의 개별 슬롯 대신 하나의 multi-order 엔트리로 관리합니다.

/* sibling 엔트리 확인 방법 */
static inline bool is_sibling_entry(
    const struct radix_tree_node *parent,
    void *node)
{
    void __rcu **ptr = (void __rcu **)node;
    return (ptr >= parent->slots) &&
           (ptr < parent->slots + RADIX_TREE_MAP_SIZE);
}

/* multi-order lookup에서 head entry 찾기 */
static void *radix_tree_descend(
    const struct radix_tree_node *parent,
    struct radix_tree_node **nodep,
    unsigned long index)
{
    unsigned offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
    void __rcu **entry = rcu_dereference_raw(parent->slots[offset]);
    void *node = rcu_dereference_raw(*entry);

    /* sibling이면 head 슬롯으로 재귀 */
    if (is_sibling_entry(parent, node))
        node = rcu_dereference_raw(*((void __rcu **)node));

    *nodep = (struct radix_tree_node *)node;
    return entry;
}

태그 전파 메커니즘

Radix Tree의 태그(tag) 시스템은 페이지 캐시에서 dirty/writeback 페이지를 빠르게 찾기 위한 핵심 메커니즘입니다. 태그는 리프 노드에서 루트까지 비트맵 형태로 전파되어, 특정 태그가 설정된 엔트리만 효율적으로 순회할 수 있습니다.

radix_tree_tag_set() / tag_clear() 구현

/* lib/radix-tree.c - 태그 설정 및 전파 */
void *radix_tree_tag_set(struct radix_tree_root *root,
                         unsigned long index,
                         unsigned int tag)
{
    struct radix_tree_node *node, *parent;
    unsigned long maxindex;

    radix_tree_load_root(root, &node, &maxindex);
    BUG_ON(index > maxindex);

    /* 리프까지 내려가며 경로 추적 */
    while (radix_tree_is_internal_node(node)) {
        unsigned offset;
        node = entry_to_node(node);
        offset = radix_tree_descend(node, &node, index);

        /* 이미 태그가 설정되어 있으면 상위 전파 불필요 */
        if (!tag_get(node, tag, offset))
            tag_set(node, tag, offset);

        /* 부모 노드에도 전파 */
        if (all_tag_set(node, tag))
            break;  /* 이미 부모에 전파됨 */
    }

    /* 루트에도 태그 존재 표시 */
    if (!root_tag_get(root, tag))
        root_tag_set(root, tag);

    return node;
}

/* 태그 클리어 - 반대 방향 전파 */
void *radix_tree_tag_clear(struct radix_tree_root *root,
                           unsigned long index,
                           unsigned int tag)
{
    struct radix_tree_node *node, *parent;
    unsigned offset;

    /* 리프에서 태그 비트 클리어 */
    tag_clear(node, tag, offset);

    /* 부모로 올라가며: 모든 자식이 클리어면 부모도 클리어 */
    while (node) {
        if (any_tag_set(node, tag))
            break;  /* 아직 태그된 자식 존재 */

        parent = node->parent;
        offset = node->offset;
        tag_clear(parent, tag, offset);
        node = parent;
    }

    /* 루트 태그도 갱신 */
    if (!any_tag_set_from_root(root, tag))
        root_tag_clear(root, tag);

    return node;
}

태그 기반 반복과 dirty 페이지 기록

filemap_fdatawrite()는 dirty 태그가 설정된 페이지만 빠르게 순회하여 디스크에 기록합니다. 태그가 없는 서브트리는 완전히 건너뛸 수 있어, 수백만 개의 clean 페이지를 가진 대용량 파일에서도 dirty 페이지를 O(k × log₆₄ n) 시간에 찾을 수 있습니다 (k = dirty 페이지 수).

/* 태그 기반 순회 - radix_tree_gang_lookup_tag() */
unsigned int radix_tree_gang_lookup_tag(
    const struct radix_tree_root *root,
    void **results,
    unsigned long first_index,
    unsigned int max_items,
    unsigned int tag)
{
    struct radix_tree_iter iter;
    void __rcu **slot;
    unsigned int ret = 0;

    if (!root_tag_get(root, tag))
        return 0;  /* 트리 전체에 태그 없음 → 즉시 반환 */

    radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
        results[ret] = rcu_dereference_raw(*slot);
        if (!results[ret])
            continue;
        if (++ret == max_items)
            break;
    }
    return ret;
}

/* filemap_fdatawrite에서의 사용 예 */
int filemap_fdatawrite_range(struct address_space *mapping,
                            loff_t start, loff_t end)
{
    struct writeback_control wbc = {
        .sync_mode = WB_SYNC_ALL,
        .nr_to_write = LONG_MAX,
        .range_start = start,
        .range_end = end,
    };
    /* DIRTY 태그 기반으로 dirty 페이지만 순회하여 기록 */
    return do_writepages(mapping, &wbc);
}

내부 노드 구조 분석

Radix Tree의 성능과 메모리 특성을 이해하려면 radix_tree_node의 내부 구조를 정확히 알아야 합니다. 각 노드는 64개의 슬롯(RADIX_TREE_MAP_SIZE)과 3개의 태그 비트맵을 가지며, 포인터를 통해 부모-자식 관계를 형성합니다.

트리 성장 과정

Radix Tree는 필요에 따라 동적으로 높이가 증가합니다. 기존 키 범위를 초과하는 인덱스가 삽입되면, 새로운 루트 노드를 생성하고 기존 트리를 자식으로 연결합니다.

/* lib/radix-tree.c - 트리 높이 확장 */
static int radix_tree_extend(struct radix_tree_root *root,
                              struct radix_tree_node *child,
                              unsigned long index)
{
    unsigned int maxshift;

    /* 필요한 높이 계산 */
    maxshift = fls_long(index) - 1;

    while (maxshift > child->shift) {
        struct radix_tree_node *node;

        /* 새 내부 노드 할당 */
        node = radix_tree_node_alloc(root, child, 0,
                                      child->shift + RADIX_TREE_MAP_SHIFT,
                                      0, 1);

        /* 기존 자식을 slot[0]에 연결 */
        rcu_assign_pointer(node->slots[0],
                           node_to_entry(child));

        /* 자식의 태그를 새 노드에 전파 */
        if (root_tag_get(root, 0))
            tag_set(node, 0, 0);
        if (root_tag_get(root, 1))
            tag_set(node, 1, 0);

        child = node;
    }

    /* 새 루트 설정 */
    rcu_assign_pointer(root->rnode, node_to_entry(child));
    return 0;
}

/* 인덱스에서 오프셋 계산 */
static inline unsigned int radix_tree_descend_offset(
    unsigned long index, unsigned int shift)
{
    /* 6비트씩 추출: (index >> shift) & 0x3F */
    return (index >> shift) & RADIX_TREE_MAP_MASK;
}

예외(Exceptional) 엔트리

Radix Tree 슬롯에는 일반 데이터 포인터 외에 예외 엔트리가 저장될 수 있습니다. 페이지 캐시에서는 shadow entry(eviction 정보)를 저장하는 데 사용됩니다.

/* include/linux/radix-tree.h - 엔트리 타입 판별 */

/* 내부 노드: 최하위 비트 = 1, bit 1 = 0 */
#define RADIX_TREE_INTERNAL_NODE  1UL

static inline bool radix_tree_is_internal_node(void *ptr)
{
    return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK)
            == RADIX_TREE_INTERNAL_NODE;
}

/* 예외 엔트리: bit 0 = 0, bit 1 = 1 */
#define RADIX_TREE_EXCEPTIONAL_ENTRY  2

static inline bool radix_tree_exceptional_entry(void *entry)
{
    return (unsigned long)entry & RADIX_TREE_EXCEPTIONAL_ENTRY;
}

/* 페이지 캐시에서 shadow entry 저장 */
static void *pack_shadow(int memcgid, pg_data_t *pgdat,
                         unsigned long eviction, bool workingset)
{
    /* eviction 정보를 예외 엔트리로 인코딩 */
    eviction <<= MEM_CGROUP_ID_SHIFT;
    eviction |= memcgid;
    eviction = (eviction << NODES_SHIFT) | page_to_nid(pgdat);
    eviction = (eviction << 1) | workingset;
    return (void *)(eviction << RADIX_TREE_EXCEPTIONAL_SHIFT
                   | RADIX_TREE_EXCEPTIONAL_ENTRY);
}

XArray 전환 비교 분석

XArray는 커널 4.20에서 Radix Tree를 대체하기 위해 Matthew Wilcox가 설계한 자료구조입니다. 내부적으로는 유사한 트라이 구조를 사용하지만, API 설계, 잠금 모델, 다중 인덱스 처리에서 근본적인 개선이 이루어졌습니다.

API 매핑표

XArray vs Radix Tree 내부 구조

xa_state (XAS) 커서 기반 API

XArray의 가장 큰 혁신 중 하나는 xa_state(XAS) 커서입니다. Radix Tree에서는 매 연산마다 루트부터 탐색해야 했지만, XAS는 트리 내 위치를 기억하여 연속 연산의 효율성을 크게 높입니다.

/* XAS 커서 기반 순회 예제 */
void process_pages_xarray(struct address_space *mapping)
{
    XA_STATE(xas, &mapping->i_pages, 0);
    struct page *page;

    /* XAS가 현재 위치를 기억 → 루트부터 재탐색 불필요 */
    rcu_read_lock();
    xas_for_each(&xas, page, ULONG_MAX) {
        if (xas_retry(&xas, page))
            continue;
        /* page 처리 */
    }
    rcu_read_unlock();
}

/* Radix Tree 대비 이점 */
/* Radix Tree: 매번 radix_tree_lookup() → O(h) 탐색 */
/* XArray XAS: 이전 위치에서 이동 → 평균 O(1) 이동 */

/* XAS 기반 조건부 저장 (cmpxchg 패턴) */
void conditional_store(struct xarray *xa,
                       unsigned long index,
                       void *old, void *new)
{
    XA_STATE(xas, xa, index);
    void *entry;

    xa_lock(xa);
    entry = xas_load(&xas);
    if (entry == old)
        xas_store(&xas, new);  /* 위치 재탐색 불필요 */
    xa_unlock(xa);
}

페이지 캐시 히스토리

리눅스 페이지 캐시의 자료구조는 커널 발전과 함께 세 번의 대규모 전환을 거쳤습니다. 이 변천사를 이해하면 현재 XArray 기반 구조가 왜 존재하는지 맥락을 잡을 수 있습니다.

address_space.i_pages 필드 변천

/* 커널 2.6: struct address_space */
struct address_space {
    struct radix_tree_root  page_tree;   /* radix tree of pages */
    spinlock_t             tree_lock;   /* 외부 잠금 필요 */
    /* ... */
};

/* 커널 4.17: 이름 변경 (타입은 동일) */
struct address_space {
    struct radix_tree_root  i_pages;     /* page_tree → i_pages */
    spinlock_t             i_pages_lock;
    /* ... */
};

/* 커널 4.20+: XArray 타입으로 전환 */
struct address_space {
    struct xarray           i_pages;     /* xarray (내장 lock) */
    /* tree_lock/i_pages_lock 제거 → xa_lock 내장 */
    /* ... */
};

Folio 도입의 영향

커널 5.16부터 folio 개념이 도입되면서, 페이지 캐시 API가 한 번 더 진화했습니다. Folio는 compound page의 head page를 타입 안전하게 다루는 추상화로, multi-order 엔트리 처리를 단순화합니다.

/* 페이지 캐시 lookup 진화 비교 */

/* 방법 1: 레거시 radix tree (커널 2.6~4.16) */
struct page *find_get_page(struct address_space *mapping,
                          pgoff_t offset)
{
    struct page *page;
    rcu_read_lock();
    page = radix_tree_lookup(&mapping->page_tree, offset);
    if (page && !page_cache_get_speculative(page))
        page = NULL;
    rcu_read_unlock();
    return page;
}

/* 방법 2: XArray 전환 후 (커널 4.20~5.15) */
struct page *pagecache_get_page(struct address_space *mapping,
                                pgoff_t index,
                                int fgp_flags, gfp_t gfp)
{
    struct page *page;
    page = xa_load(&mapping->i_pages, index);
    /* ... 플래그 기반 처리 ... */
    return page;
}

/* 방법 3: Folio 시대 (커널 5.16+) */
struct folio *filemap_get_folio(struct address_space *mapping,
                                pgoff_t index)
{
    XA_STATE(xas, &mapping->i_pages, index);
    struct folio *folio;

    rcu_read_lock();
    folio = xas_load(&xas);
    if (xas_retry(&xas, folio))
        goto retry;
    if (!folio || xa_is_value(folio))
        folio = NULL;
    else if (!folio_try_get_rcu(folio))
        goto retry;
    rcu_read_unlock();
    return folio;
}

IDR과 Radix Tree 관계

IDR(ID Radix)은 정수 ID를 포인터에 매핑하는 자료구조로, 커널 2.6에서 도입되었습니다. 초기에는 자체 IDR 레이어 구조를 사용했으나, 이후 Radix Tree 위에 구축되었고, 최종적으로 XArray 백엔드로 전환되었습니다.

/* IDR의 Radix Tree 시대 구현 (커널 4.11~4.19) */
struct idr {
    struct radix_tree_root  idr_rt;
    int                    idr_base;
    int                    idr_next;
};

int idr_alloc(struct idr *idr, void *ptr,
              int start, int end, gfp_t gfp)
{
    /* 내부적으로 radix_tree_insert() 사용 */
    return idr_alloc_cmn(idr, ptr, NULL, start, end, gfp, false);
}

void *idr_find(const struct idr *idr, unsigned long id)
{
    /* 내부적으로 radix_tree_lookup() 사용 */
    return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
}

/* XArray 시대 전환 후 (커널 4.20+) */
struct idr {
    struct xarray  idr_rt;
    unsigned int  idr_base;
    unsigned int  idr_next;
};

int idr_alloc(struct idr *idr, void *ptr,
              int start, int end, gfp_t gfp)
{
    u32 id;
    int ret;

    /* xa_alloc()으로 ID 할당 */
    ret = xa_alloc(&idr->idr_rt, &id, ptr,
                   XA_LIMIT(start, end - 1), gfp);
    return ret ? ret : id;
}

/* IDR 사용 예: 파일 디스크립터 할당 */
int alloc_fd(unsigned start, unsigned flags)
{
    struct fdtable *fdt = files_fdtable(current->files);
    int fd;

    /* IDR로 빈 fd 번호 할당 */
    fd = idr_alloc(&current->files->fd_idr, NULL,
                   start, fdt->max_fds, GFP_KERNEL);
    return fd;
}

RCU 안전성 분석

Radix Tree는 읽기 경로에서 RCU(Read-Copy-Update)를 사용하여 잠금 없이 동시 접근을 허용합니다. 쓰기는 외부 잠금(spinlock 등)으로 보호하고, 읽기는 RCU 보호 아래서 lockless로 수행됩니다. 이 모델은 페이지 캐시처럼 읽기가 압도적으로 많은 경우에 탁월한 성능을 제공합니다.

/* RCU-safe lookup 경로 분석 */
void *radix_tree_lookup(const struct radix_tree_root *root,
                        unsigned long index)
{
    struct radix_tree_node *node, *parent;
    unsigned long maxindex;
    void __rcu **slot;

    /* RCU 보호 아래에서 호출되어야 함 */
    node = rcu_dereference_raw(root->rnode);
    if (!radix_tree_is_internal_node(node)) {
        if (index > 0)
            return NULL;
        return node;  /* 단일 엔트리 */
    }

    /* 트리 하강: 각 레벨에서 RCU로 포인터 읽기 */
    do {
        parent = entry_to_node(node);
        unsigned offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;

        /* rcu_dereference로 슬롯 읽기 — 원자적 */
        node = rcu_dereference_raw(parent->slots[offset]);
        if (!node)
            return NULL;
    } while (radix_tree_is_internal_node(node));

    return node;
}

/* 노드 해제 시 RCU 콜백 사용 */
static void radix_tree_node_free(struct radix_tree_node *node)
{
    /* 즉시 해제하면 안 됨 — 읽기 중인 CPU가 있을 수 있음 */
    call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
}

static void radix_tree_node_rcu_free(struct rcu_head *head)
{
    struct radix_tree_node *node =
        container_of(head, struct radix_tree_node, rcu_head);
    /* Grace period 이후: 모든 reader 완료 → 안전하게 해제 */
    kmem_cache_free(radix_tree_node_cachep, node);
}

XArray RCU 모델과의 비교

ftrace/perf 디버깅(Debugging) 실습

Radix Tree(또는 XArray로 전환된) 페이지 캐시 연산을 추적하는 것은 I/O 성능 분석에서 핵심입니다. ftrace, perf, bpftrace를 활용하여 실시간(Real-time)으로 페이지 캐시 hit/miss를 분석할 수 있습니다.

ftrace로 페이지 캐시 추적

# 1. ftrace 설정: 페이지 캐시 관련 함수 추적
cd /sys/kernel/debug/tracing

# filemap 관련 함수 필터
echo 'filemap_get_folio' > set_ftrace_filter
echo 'filemap_add_folio' >> set_ftrace_filter
echo 'filemap_remove_folio' >> set_ftrace_filter

# function_graph 트레이서 사용 (호출 깊이 포함)
echo function_graph > current_tracer
echo 1 > tracing_on

# 테스트 워크로드 실행
cat /path/to/testfile > /dev/null

# 결과 확인
echo 0 > tracing_on
cat trace | head -50

# 출력 예시:
#  0)               |  filemap_get_folio() {
#  0)   0.234 us    |    xas_load();
#  0)   0.891 us    |  }

perf probe로 동적 추적점(Tracepoint) 생성

# 2. perf probe: radix tree / XArray 연산 추적

# XArray lookup 함수에 프로브 설정
perf probe --add 'xa_load xa=%di index=%si'

# 페이지 캐시 miss 추적 (add_to_page_cache_lru)
perf probe --add 'filemap_add_folio mapping=%di index=%si'

# 프로브 기반 레코딩
perf record -e probe:xa_load -e probe:filemap_add_folio -a -- sleep 10

# 결과 분석
perf report --sort=symbol

# 프로브 정리
perf probe --del '*'

bpftrace 스크립트: 페이지 캐시 히트/미스 비율

/* page_cache_ratio.bt — bpftrace 스크립트 */
/* 사용법: bpftrace page_cache_ratio.bt */

kprobe:filemap_get_folio
{
    @lookup_total = count();
    @lookup_by_comm[comm] = count();
}

kretprobe:filemap_get_folio
/retval == 0/
{
    /* NULL 반환 = cache miss */
    @miss_total = count();
    @miss_by_comm[comm] = count();
}

kprobe:filemap_add_folio
{
    /* 새 folio 추가 = cache miss에 따른 할당 */
    @add_total = count();
}

interval:s:5
{
    printf("--- Page Cache Stats (5s interval) ---\n");
    printf("Total lookups: %d\n", @lookup_total);
    printf("Total misses : %d\n", @miss_total);
    printf("Total adds   : %d\n", @add_total);

    if (@lookup_total > 0) {
        printf("Hit ratio    : %d%%\n",
               100 - (@miss_total * 100 / @lookup_total));
    }

    printf("\nLookups by process:\n");
    print(@lookup_by_comm);
    printf("\nMisses by process:\n");
    print(@miss_by_comm);

    clear(@lookup_total);
    clear(@miss_total);
    clear(@add_total);
    clear(@lookup_by_comm);
    clear(@miss_by_comm);
}

레거시 radix_tree 함수 추적 (4.20 이전 커널)

# 구 커널에서 radix_tree 함수 직접 추적

# 사용 가능한 radix tree 함수 확인
cat /sys/kernel/debug/tracing/available_filter_functions | \
    grep radix_tree

# radix_tree_lookup 빈도 측정
perf stat -e 'probe:radix_tree_lookup' -a -- sleep 10

# ftrace로 radix_tree_insert 호출 스택 추적
echo radix_tree_insert > /sys/kernel/debug/tracing/set_ftrace_filter
echo function > /sys/kernel/debug/tracing/current_tracer
echo 1 > /sys/kernel/debug/tracing/options/func_stack_trace
echo 1 > /sys/kernel/debug/tracing/tracing_on
# ... 워크로드 실행 ...
echo 0 > /sys/kernel/debug/tracing/tracing_on
cat /sys/kernel/debug/tracing/trace

메모리 오버헤드 분석

Radix Tree의 메모리 효율성은 키 분포에 크게 의존합니다. 조밀한(dense) 키 분포에서는 효율적이지만, 희소한(sparse) 키 분포에서는 내부 노드의 빈 슬롯으로 인한 낭비가 발생합니다.

radix_tree_preload() 메커니즘

Radix Tree 삽입 시 노드 할당이 필요할 수 있는데, 원자적(Atomic) 컨텍스트에서는 메모리 할당이 실패할 수 있습니다. radix_tree_preload()는 이를 해결하기 위해 미리 노드를 할당해 per-CPU 캐시에 저장합니다.

/* lib/radix-tree.c - preload 메커니즘 */
DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = {
    .lock = INIT_LOCAL_LOCK(lock),
};

struct radix_tree_preload {
    struct local_lock lock;
    unsigned nr;
    struct radix_tree_node *nodes;
};

/* preload: 미리 노드를 할당하여 per-CPU에 저장 */
int radix_tree_preload(gfp_t gfp_mask)
{
    /* 최대 RADIX_TREE_PRELOAD_SIZE개 미리 할당 */
    return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
}

static int __radix_tree_preload(gfp_t gfp, unsigned nr)
{
    struct radix_tree_preload *rtp;
    struct radix_tree_node *node;
    int ret = -ENOMEM;

    /* preempt 비활성화하여 per-CPU 데이터 보호 */
    preempt_disable();
    rtp = this_cpu_ptr(&radix_tree_preloads);

    while (rtp->nr < nr) {
        preempt_enable();
        /* 프리엠션 가능 구간에서 할당 */
        node = kmem_cache_alloc(radix_tree_node_cachep,
                                gfp_mask);
        if (!node)
            goto out;
        preempt_disable();
        rtp = this_cpu_ptr(&radix_tree_preloads);

        /* per-CPU 리스트에 추가 */
        node->parent = rtp->nodes;
        rtp->nodes = node;
        rtp->nr++;
    }
    ret = 0;
out:
    return ret;
}

/* 사용 패턴 */
int add_to_page_cache(struct page *page,
                      struct address_space *mapping,
                      pgoff_t offset, gfp_t gfp)
{
    int error;

    /* 1단계: 슬리핑 가능 컨텍스트에서 미리 할당 */
    error = radix_tree_preload(gfp & GFP_RECLAIM_MASK);
    if (error)
        return error;

    /* 2단계: 잠금 획득 (원자적 컨텍스트 진입) */
    spin_lock_irq(&mapping->tree_lock);

    /* 3단계: 삽입 — preload된 노드 사용 */
    error = radix_tree_insert(&mapping->page_tree,
                              offset, page);

    spin_unlock_irq(&mapping->tree_lock);

    /* 4단계: preload 해제 */
    radix_tree_preload_end();
    return error;
}

/* XArray에서는 preload 불필요 */
/* xa_store()가 내부적으로 GFP_NOWAIT + 재시도 로직 처리 */

실전 레거시 코드 분석

현재 커널에서도 일부 서브시스템은 여전히 레거시 radix tree 패턴을 사용하고 있습니다. 이러한 코드를 읽고 이해하며, 필요시 XArray로 전환하는 방법을 알아봅니다.

레거시 패턴 인식 가이드

/* 패턴 1: 기본 CRUD — 가장 흔한 레거시 패턴 */
struct my_cache {
    struct radix_tree_root  tree;
    spinlock_t             lock;
};

/* 초기화 */
INIT_RADIX_TREE(&cache->tree, GFP_ATOMIC);
spin_lock_init(&cache->lock);

/* 삽입 */
radix_tree_preload(GFP_KERNEL);          /* 미리 할당 */
spin_lock(&cache->lock);
radix_tree_insert(&cache->tree, id, ptr);
spin_unlock(&cache->lock);
radix_tree_preload_end();                 /* preload 해제 */

/* 검색 (RCU) */
rcu_read_lock();
ptr = radix_tree_lookup(&cache->tree, id);
rcu_read_unlock();

/* ─── XArray 전환 후 ─── */
struct my_cache {
    struct xarray  xa;    /* spinlock 내장 */
};

/* 초기화 */
xa_init(&cache->xa);

/* 삽입 — preload 불필요, lock 자동 */
xa_store(&cache->xa, id, ptr, GFP_KERNEL);

/* 검색 — RCU 자동 */
ptr = xa_load(&cache->xa, id);

레거시 코드에서 흔한 실수 패턴

/* 패턴 2: 태그 기반 순회 → XArray mark 전환 */

/* 레거시: dirty 엔트리 순회 */
unsigned long index = 0;
unsigned int found;
void *results[16];

rcu_read_lock();
while ((found = radix_tree_gang_lookup_tag(
            &tree, results, index, 16,
            MY_TAG_DIRTY))) {
    for (unsigned int i = 0; i < found; i++) {
        /* 결과 처리 */
        process(results[i]);
    }
    index = get_index(results[found - 1]) + 1;
}
rcu_read_unlock();

/* XArray 전환 후: 훨씬 간결 */
unsigned long index;
void *entry;

xa_for_each_marked(&xa, index, entry, XA_MARK_0) {
    process(entry);
}

/* 패턴 3: 조건부 삭제 → XArray cmpxchg */

/* 레거시: lock + lookup + delete */
spin_lock(&lock);
entry = radix_tree_lookup(&tree, index);
if (entry && should_remove(entry)) {
    radix_tree_delete(&tree, index);
    kfree_rcu(entry, rcu);
}
spin_unlock(&lock);

/* XArray: xa_cmpxchg로 원자적 조건부 교체 */
old = xa_cmpxchg(&xa, index, expected, NULL, GFP_KERNEL);
if (old == expected)
    kfree_rcu(old, rcu);

레거시 코드 검색 및 분석

# 커널 소스에서 레거시 radix tree 사용 지점 찾기

# 1. radix_tree_root 선언 검색
git grep -n 'struct radix_tree_root' -- '*.c' '*.h' | \
    grep -v 'include/linux/radix-tree.h' | \
    grep -v 'lib/radix-tree.c'

# 2. INIT_RADIX_TREE 사용처 (아직 XArray 미전환)
git grep -n 'INIT_RADIX_TREE' -- '*.c'

# 3. preload 패턴 (XArray에서는 불필요)
git grep -n 'radix_tree_preload' -- '*.c'

# 4. 전환 대상 우선순위 판단
# — 사용 빈도, 잠금 복잡도, exceptional entry 유무 확인
git grep -c 'radix_tree_' -- '*.c' | sort -t: -k2 -rn | head -20

# 5. XArray 전환 커밋 패턴 참고
git log --oneline --all --grep='radix.tree.*xarray' | head -10
git log --oneline --all --grep='Convert.*radix.*xarray' | head -10

XArray 마이그레이션 실전 가이드

Radix Tree에서 XArray로 전환할 때는 단순한 함수명 교체가 아니라, 잠금 모델과 메모리 할당 전략의 근본적인 변화를 이해해야 합니다. 이 섹션에서는 실제 커널 코드 전환에 필요한 패턴별 변환 방법을 상세히 다룹니다.

radix_tree_insert → xa_store 변환

가장 기본적인 삽입 연산의 변환입니다. Radix Tree에서는 preload와 외부 잠금이 필수였지만, XArray에서는 단일 호출로 처리됩니다.

/* ─── Before: Radix Tree 삽입 패턴 ─── */
struct radix_tree_root my_tree;
spinlock_t my_lock;

INIT_RADIX_TREE(&my_tree, GFP_ATOMIC);
spin_lock_init(&my_lock);

int my_insert(unsigned long index, void *ptr)
{
    int err;

    /* 1단계: 메모리 사전 할당 (슬립 가능 컨텍스트) */
    err = radix_tree_preload(GFP_KERNEL);
    if (err)
        return err;

    /* 2단계: 잠금 획득 (preempt 이미 disabled) */
    spin_lock(&my_lock);

    /* 3단계: 삽입 */
    err = radix_tree_insert(&my_tree, index, ptr);

    /* 4단계: 잠금 해제 */
    spin_unlock(&my_lock);

    /* 5단계: preload 해제 (preempt re-enable) */
    radix_tree_preload_end();

    return err;
}

/* ─── After: XArray 삽입 패턴 ─── */
DEFINE_XARRAY(my_xa);

int my_insert(unsigned long index, void *ptr)
{
    void *old;

    /* 단일 호출: 잠금 + 할당 + 삽입 모두 처리 */
    old = xa_store(&my_xa, index, ptr, GFP_KERNEL);
    if (xa_is_err(old))
        return xa_err(old);

    /* old에 이전 엔트리가 반환됨 (덮어쓰기 감지 가능) */
    if (old)
        pr_warn("index %lu already had entry %p\n", index, old);

    return 0;
}

radix_tree_lookup → xa_load 변환

/* ─── Before: Radix Tree 검색 (RCU 보호 필수) ─── */
void *my_lookup_old(unsigned long index)
{
    void *ptr;

    rcu_read_lock();
    ptr = radix_tree_lookup(&my_tree, index);
    /* ptr은 RCU 보호 구간에서만 유효 */
    if (ptr)
        my_get_ref(ptr);  /* 참조 카운트 증가 필수 */
    rcu_read_unlock();

    return ptr;
}

/* ─── After: XArray 검색 (RCU 자동 처리) ─── */
void *my_lookup_new(unsigned long index)
{
    void *ptr;

    /* xa_load()는 내부적으로 rcu_read_lock/unlock 수행 */
    ptr = xa_load(&my_xa, index);
    /* 주의: 반환 후 RCU 보호 종료 — 즉시 참조 카운트 증가 필요 */
    if (ptr)
        my_get_ref(ptr);

    return ptr;
}

/* 장기간 사용 시: 직접 RCU 관리 + xas API */
void my_lookup_extended(unsigned long index)
{
    XA_STATE(xas, &my_xa, index);
    void *entry;

    rcu_read_lock();
    entry = xas_load(&xas);
    if (entry) {
        /* RCU 구간 내에서 여러 작업 수행 가능 */
        process_entry(entry);
    }
    rcu_read_unlock();
}

radix_tree_delete → xa_erase 변환

/* ─── Before: Radix Tree 삭제 ─── */
void *my_delete_old(unsigned long index)
{
    void *ptr;

    spin_lock(&my_lock);
    ptr = radix_tree_delete(&my_tree, index);
    spin_unlock(&my_lock);

    if (ptr)
        kfree_rcu(ptr, rcu);  /* RCU grace period 후 해제 */

    return ptr;
}

/* ─── After: XArray 삭제 ─── */
void *my_delete_new(unsigned long index)
{
    void *ptr;

    /* xa_erase()는 내부적으로 xa_lock 사용 */
    ptr = xa_erase(&my_xa, index);

    if (ptr)
        kfree_rcu(ptr, rcu);  /* 여전히 RCU 해제 필요 */

    return ptr;
}

/* 조건부 삭제: xa_cmpxchg 활용 */
void *my_delete_if(unsigned long index, void *expected)
{
    void *old;

    /* expected와 일치할 때만 삭제 (원자적) */
    old = xa_cmpxchg(&my_xa, index, expected, NULL, GFP_KERNEL);
    if (old == expected) {
        kfree_rcu(old, rcu);
        return old;
    }
    return NULL;  /* 불일치: 삭제하지 않음 */
}

radix_tree_for_each_slot → xa_for_each 변환

/* ─── Before: Radix Tree 순회 ─── */
void iterate_old(struct radix_tree_root *root)
{
    struct radix_tree_iter iter;
    void __rcu **slot;

    rcu_read_lock();
    radix_tree_for_each_slot(slot, root, &iter, 0) {
        void *entry = radix_tree_deref_slot(slot);
        if (!entry)
            continue;
        if (radix_tree_deref_retry(entry)) {
            slot = radix_tree_iter_retry(&iter);
            continue;
        }
        if (radix_tree_exceptional_entry(entry))
            continue;  /* shadow/exceptional 건너뛰기 */

        process(entry);
    }
    rcu_read_unlock();
}

/* ─── After: XArray 순회 ─── */
void iterate_new(struct xarray *xa)
{
    unsigned long index;
    void *entry;

    /* xa_for_each는 내부적으로 RCU 보호, retry, internal 필터링 수행 */
    xa_for_each(xa, index, entry) {
        process(entry);
    }
}

태그 → 마크 변환: radix_tree_tag_set/clear → xa_set_mark/xa_clear_mark

/* ─── Before: Radix Tree 태그 조작 ─── */
/* 태그는 정수 (PAGECACHE_TAG_DIRTY = 0, PAGECACHE_TAG_WRITEBACK = 1 등) */
spin_lock_irq(&mapping->tree_lock);
radix_tree_tag_set(&mapping->i_pages, index, PAGECACHE_TAG_DIRTY);
spin_unlock_irq(&mapping->tree_lock);

/* 태그 확인 (RCU 보호 필요) */
rcu_read_lock();
int tagged = radix_tree_tag_get(&mapping->i_pages, index,
                                  PAGECACHE_TAG_DIRTY);
rcu_read_unlock();

/* 태그 기반 순회 */
radix_tree_gang_lookup_tag(&tree, results, start, nr,
                           PAGECACHE_TAG_DIRTY);

/* ─── After: XArray 마크 조작 ─── */
/* 마크는 열거형 (XA_MARK_0, XA_MARK_1, XA_MARK_2) */
xa_set_mark(&mapping->i_pages, index, PAGECACHE_TAG_DIRTY);
/* xa_set_mark()가 내부적으로 xa_lock 획득 */

/* 마크 확인 */
bool marked = xa_get_mark(&mapping->i_pages, index,
                          PAGECACHE_TAG_DIRTY);

/* 마크 기반 순회 — 훨씬 간결 */
unsigned long idx;
void *entry;
xa_for_each_marked(&xa, idx, entry, PAGECACHE_TAG_DIRTY) {
    process_dirty_page(entry);
}

변환 전후 비교표: GFP 플래그 처리

잠금 모델 변화: 외부 잠금 → xa_lock

/*
 * Radix Tree: 외부 잠금을 직접 관리해야 합니다.
 * 읽기 경로: rcu_read_lock()
 * 쓰기 경로: spin_lock(&external_lock)
 *
 * XArray: 내장 xa_lock을 사용하거나 API가 자동 관리합니다.
 * 읽기 경로: xa_load() → 내부 rcu_read_lock/unlock
 * 쓰기 경로: xa_store() → 내부 xa_lock/unlock
 */

/* ─── Radix Tree: 외부 잠금 패턴 ─── */
struct my_subsystem {
    struct radix_tree_root  cache;
    spinlock_t             cache_lock;   /* 별도의 잠금 */
};

/* 쓰기 경로 */
spin_lock(&subsys->cache_lock);
radix_tree_insert(&subsys->cache, key, val);
radix_tree_tag_set(&subsys->cache, key, MY_TAG);
spin_unlock(&subsys->cache_lock);

/* ─── XArray: xa_lock 패턴 ─── */
struct my_subsystem {
    struct xarray  cache;   /* spinlock 내장 */
    /* cache_lock 제거 — xa_lock이 대체 */
};

/* 단순 쓰기: API가 자동으로 xa_lock 처리 */
xa_store(&subsys->cache, key, val, GFP_KERNEL);
xa_set_mark(&subsys->cache, key, XA_MARK_0);

/* 복합 쓰기: 명시적 xa_lock으로 원자적 묶음 연산 */
xa_lock(&subsys->cache);
__xa_store(&subsys->cache, key, val, GFP_NOWAIT);
__xa_set_mark(&subsys->cache, key, XA_MARK_0);
xa_unlock(&subsys->cache);

/* IRQ 컨텍스트: xa_lock_irqsave 사용 */
unsigned long flags;
xa_lock_irqsave(&subsys->cache, flags);
__xa_store(&subsys->cache, key, val, GFP_NOWAIT);
xa_unlock_irqrestore(&subsys->cache, flags);

마이그레이션 사례 연구

실제 커널에서 진행된 Radix Tree → XArray 마이그레이션의 대표적 사례를 분석합니다. 각 사례는 서로 다른 복잡도와 특수 상황을 보여주며, 자신의 코드 전환 시 참고할 수 있는 실전 교훈을 담고 있습니다.

사례 1: 페이지 캐시(address_space) 마이그레이션

페이지 캐시(Page Cache)는 Radix Tree의 가장 대표적이고 복잡한 사용처였습니다. address_space 구조체의 page_tree 필드가 i_pages로 이름이 바뀌면서 xarray 타입으로 전환되었습니다.

/*
 * 전환 전: address_space (v4.19 이전)
 * 파일: include/linux/fs.h
 */
struct address_space {
    struct inode            *host;
    struct radix_tree_root  page_tree;     /* 페이지 캐시 트리 */
    spinlock_t             tree_lock;     /* 외부 잠금 */
    unsigned long          nrpages;
    /* ... */
};

/*
 * 전환 후: address_space (v5.2+)
 * 파일: include/linux/fs.h
 */
struct address_space {
    struct inode     *host;
    struct xarray    i_pages;       /* xarray (spinlock 내장) */
    /* tree_lock 제거됨 — xa_lock(&mapping->i_pages) 사용 */
    unsigned long   nrpages;
    /* ... */
};

/*
 * 전환 전: add_to_page_cache_lru() 내부 (간략화)
 */
static int __add_to_page_cache_locked(
    struct page *page,
    struct address_space *mapping,
    pgoff_t offset, gfp_t gfp_mask)
{
    int error;

    get_page(page);
    page->mapping = mapping;
    page->index = offset;

    /* preload → lock → insert → unlock → preload_end */
    error = radix_tree_maybe_preload(gfp_mask & GFP_RECLAIM_MASK);
    if (error)
        goto err;

    xa_lock_irq(&mapping->i_pages);
    error = __radix_tree_insert(&mapping->i_pages, offset, 0, page);
    if (!error) {
        mapping->nrpages++;
        __inc_lruvec_page_state(page, NR_FILE_PAGES);
    }
    xa_unlock_irq(&mapping->i_pages);
    radix_tree_preload_end();
err:
    return error;
}

/*
 * 전환 후: filemap_add_folio() (v5.15+)
 */
int filemap_add_folio(
    struct address_space *mapping,
    struct folio *folio,
    pgoff_t index, gfp_t gfp)
{
    void *shadow = NULL;
    int ret;

    __folio_set_locked(folio);
    ret = __filemap_add_folio(mapping, folio, index, gfp, &shadow);
    if (unlikely(ret)) {
        __folio_clear_locked(folio);
        mem_cgroup_uncharge(folio);
    } else {
        /*
         * __filemap_add_folio 내부:
         * xas_store(&xas, folio) — preload 불필요
         * xa_lock_irq 사용 — 외부 tree_lock 불필요
         */
        if (shadow)
            workingset_refault(folio, shadow);
    }
    return ret;
}

사례 2: IDR → XArray 전환

IDR(ID Radix tree)은 Radix Tree 위에 구축된 정수 ID 할당기였습니다. XArray 도입 후 IDR의 내부 구현이 XArray 기반으로 교체되었으며, IDR API는 호환성 래퍼로 남아 있습니다.

/*
 * 전환 전: IDR 내부 구조 (v4.19 이전)
 */
struct idr {
    struct radix_tree_root  idr_rt;    /* Radix Tree 백엔드 */
    unsigned int           idr_base;
    unsigned int           idr_next;
};

/*
 * 전환 후: IDR 내부 구조 (v4.20+)
 */
struct idr {
    struct xarray      idr_rt;    /* XArray 백엔드 */
    unsigned int       idr_base;
    unsigned int       idr_next;
};

/* IDR API는 변경 없이 동작 — 내부만 XArray로 교체 */
int id = idr_alloc(&my_idr, ptr, 0, 0, GFP_KERNEL);
void *p = idr_find(&my_idr, id);
idr_remove(&my_idr, id);

/* 새 코드에서 직접 XArray를 사용하는 것이 더 효율적입니다 */
DEFINE_XARRAY_ALLOC(my_xa);  /* 자동 ID 할당 지원 */
u32 id;

/* xa_alloc — IDR을 거치지 않고 직접 ID 할당 */
xa_alloc(&my_xa, &id, ptr, xa_limit_32b, GFP_KERNEL);
void *p = xa_load(&my_xa, id);
xa_erase(&my_xa, id);

마이그레이션 시 흔한 실수와 해결 방법

Coccinelle 스크립트 활용

대규모 코드베이스에서의 기계적 변환에는 Coccinelle(코시넬) 시맨틱 패치를 활용할 수 있습니다. 아래는 기본 삽입 패턴을 자동 변환하는 스크립트 예시입니다.

// Coccinelle 시맨틱 패치: radix_tree_insert → xa_store 변환
// 파일: scripts/coccinelle/api/radix_to_xarray.cocci

@@
expression root, index, ptr, gfp;
identifier lock;
@@

// 패턴 1: preload + lock + insert + unlock + preload_end
- radix_tree_preload(gfp);
- spin_lock(&lock);
- radix_tree_insert(root, index, ptr);
- spin_unlock(&lock);
- radix_tree_preload_end();
+ xa_store(root, index, ptr, gfp);

@@
expression root, index;
@@

// 패턴 2: radix_tree_lookup → xa_load
- radix_tree_lookup(root, index)
+ xa_load(root, index)

@@
expression root, index;
@@

// 패턴 3: radix_tree_delete → xa_erase
- radix_tree_delete(root, index)
+ xa_erase(root, index)

@@
expression root, index, tag;
@@

// 패턴 4: 태그 → 마크
- radix_tree_tag_set(root, index, tag)
+ xa_set_mark(root, index, tag)

@@
expression root, index, tag;
@@

- radix_tree_tag_clear(root, index, tag)
+ xa_clear_mark(root, index, tag)

# Coccinelle 스크립트 실행 방법

# 1. 단일 파일에 대한 변환 미리보기 (패치 미적용)
spatch --sp-file scripts/coccinelle/api/radix_to_xarray.cocci \
    --dir drivers/my_driver/ --dry-run

# 2. 변환 적용
spatch --sp-file scripts/coccinelle/api/radix_to_xarray.cocci \
    --in-place --dir drivers/my_driver/

# 3. 커널 내장 coccinelle 활용
make coccicheck COCCI=scripts/coccinelle/api/radix_to_xarray.cocci \
    MODE=patch M=drivers/my_driver/

# 주의: Coccinelle은 기계적 변환만 수행합니다
# 잠금 모델 변경, GFP 플래그 조정, exceptional entry 처리는
# 반드시 수동 검토가 필요합니다

Radix Tree 레거시 코드 유지보수

XArray로의 전환이 진행 중이지만, 커널의 일부 서브시스템과 외부 모듈에서는 여전히 레거시 Radix Tree API를 사용하고 있습니다. 이러한 코드를 읽고 유지보수하기 위해 알아야 할 핵심 패턴들을 정리합니다.

아직 Radix Tree를 사용하는 코드 영역 (2024+ 기준)

radix_tree_preload / radix_tree_preload_end 패턴

preload 패턴은 Radix Tree 코드에서 가장 특징적인 관용구입니다. 원자적 컨텍스트(spinlock 보호 구간)에서 메모리 할당을 회피하기 위해, 미리 프로세스 컨텍스트에서 노드를 할당해 per-CPU 풀에 저장해 둡니다.

/*
 * preload 패턴의 내부 동작 원리
 * 파일: lib/radix-tree.c (간략화)
 */

/* per-CPU preload 구조체 */
struct radix_tree_preload {
    unsigned  nr;                          /* 할당된 노드 수 */
    struct radix_tree_node *nodes;          /* 단일 연결 리스트 */
};
DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads);

/*
 * radix_tree_preload() — 프로세스 컨텍스트에서 호출
 * 1) GFP_KERNEL으로 노드 사전 할당
 * 2) preempt_disable()  ← 주의: per-CPU 데이터 보호
 * 3) 반환값 0이면 성공, 음수면 할당 실패
 */
int radix_tree_preload(gfp_t gfp_mask)
{
    /* 최대 RADIX_TREE_MAX_PATH만큼 노드 사전 할당 */
    return __radix_tree_preload(gfp_mask, RADIX_TREE_MAX_PATH);
}

/*
 * insert 시 preload 풀에서 노드를 가져와 사용
 * → 원자적 컨텍스트에서도 메모리 할당 실패 없음
 */
static struct radix_tree_node *
radix_tree_node_alloc(gfp_t gfp, struct radix_tree_node *parent,
                      struct radix_tree_root *root,
                      unsigned int shift, unsigned int offset,
                      unsigned int count, unsigned int nr_values)
{
    struct radix_tree_node *ret = NULL;

    /* 먼저 일반 할당 시도 */
    ret = kmem_cache_alloc(radix_tree_node_cachep,
                           gfp | __GFP_NOWARN);
    if (ret)
        goto out;

    /* 실패 시 per-CPU preload 풀에서 가져옴 */
    ret = this_cpu_ptr(&radix_tree_preloads)->nodes;
    if (ret) {
        this_cpu_ptr(&radix_tree_preloads)->nodes = ret->parent;
        this_cpu_dec(radix_tree_preloads.nr);
    }
out:
    return ret;
}

/*
 * radix_tree_preload_end() — preempt_enable()만 수행
 * 미사용 노드는 per-CPU 풀에 남아 다음 insert에 재사용
 */
static inline void radix_tree_preload_end(void)
{
    preempt_enable();
}

exceptional entry와 shadow entry 처리

Radix Tree에서 "exceptional entry"는 최하위 비트가 1로 설정된 특수 값으로, 일반 포인터가 아닌 메타데이터를 인코딩합니다. 페이지 캐시에서는 shadow entry(작업 세트 감지), DAX entry(직접 매핑), swap entry 등에 사용되었습니다.

/*
 * exceptional entry 인코딩 (v4.19 이전)
 * 최하위 2비트로 엔트리 유형을 구분합니다
 */

/* 비트 레이아웃:
 * bit 0 = 1: exceptional entry (일반 포인터는 정렬되어 bit 0 = 0)
 * bit 1 = 0: shadow entry (workingset 감지)
 * bit 1 = 1: DAX entry 또는 기타 특수 값
 */

/* exceptional entry 검사 (레거시 API) */
static inline bool radix_tree_exceptional_entry(void *entry)
{
    return (unsigned long)entry & RADIX_TREE_EXCEPTIONAL_ENTRY;
}

/* shadow entry 생성 (workingset.c) */
static void *pack_shadow(int memcgid,
                          pg_data_t *pgdat,
                          unsigned long eviction,
                          bool workingset)
{
    unsigned long entry = eviction;
    entry = (entry << NODES_SHIFT) | pgdat_idx(pgdat);
    entry = (entry << MEM_CGROUP_ID_SHIFT) | memcgid;
    entry = (entry << 1) | workingset;
    entry = (entry << RADIX_TREE_EXCEPTIONAL_SHIFT) |
             RADIX_TREE_EXCEPTIONAL_ENTRY;
    return (void *)entry;
}

/* ─── XArray 전환 후 (v4.20+) ─── */

/* xa_is_value() — exceptional entry를 대체 */
static inline bool xa_is_value(const void *entry)
{
    return (unsigned long)entry & 1;
}

/* xa_to_value() / xa_mk_value() — 값 인코딩/디코딩 */
static inline unsigned long xa_to_value(const void *entry)
{
    return (unsigned long)entry >> 1;
}

static inline void *xa_mk_value(unsigned long v)
{
    return (void *)((unsigned long)v << 1 | 1);
}

/* 페이지 캐시 순회 시 exceptional/value 처리 비교 */

/* Before: Radix Tree */
radix_tree_for_each_slot(slot, &mapping->page_tree, &iter, start) {
    void *entry = radix_tree_deref_slot(slot);
    if (radix_tree_exceptional_entry(entry))
        continue;  /* shadow entry 건너뛰기 */
    struct page *page = entry;
    /* page 처리 */
}

/* After: XArray */
xa_for_each(&mapping->i_pages, index, entry) {
    /* xa_for_each는 내부적으로 internal entry를 필터링 */
    /* value entry(shadow 등)는 통과하므로 직접 검사 */
    if (xa_is_value(entry))
        continue;  /* shadow entry 건너뛰기 */
    struct folio *folio = entry;
    /* folio 처리 */
}

Generic Radix Tree와의 비교

커널에는 "Radix Tree"라는 이름을 공유하지만 완전히 별개의 구현인 Generic Radix Tree(lib/generic-radix-tree.c)가 있습니다. 두 구현은 목적, 설계, API가 전혀 다르므로 혼동하지 않도록 주의해야 합니다.

Generic Radix Tree API

/*
 * Generic Radix Tree — 단순 확장 배열
 * 파일: include/linux/generic-radix-tree.h, lib/generic-radix-tree.c
 *
 * 목적: 크기가 동적으로 변하는 고정 크기 객체 배열
 * 특징: 연속 메모리가 아닌 페이지 단위 할당 → vmalloc 대비 할당 실패율 낮음
 */

/* 타입 안전 래퍼 선언 */
GENRADIX(struct my_object) my_array;

/* 초기화 */
genradix_init(&my_array);

/* 인덱스로 접근 (없으면 NULL, 있으면 포인터 반환) */
struct my_object *obj = genradix_ptr(&my_array, index);

/* 인덱스로 접근 + 필요시 페이지 할당 */
obj = genradix_ptr_alloc(&my_array, index, GFP_KERNEL);
if (!obj)
    return -ENOMEM;

obj->field1 = value1;
obj->field2 = value2;

/* 순회 */
genradix_for_each(&my_array, iter, obj) {
    process(obj);
}

/* 해제 */
genradix_free(&my_array);

API 비교표

/*
 * 사용 시나리오 비교:
 * "정수 키로 포인터를 찾아야 합니다" → Radix Tree / XArray
 * "인덱스로 구조체 배열을 확장 가능하게 유지" → Generic Radix Tree
 */

/* 예시 1: 프로세스 ID → task_struct 매핑 — XArray 적합 */
DEFINE_XARRAY(pid_map);
xa_store(&pid_map, pid, task, GFP_KERNEL);
struct task_struct *t = xa_load(&pid_map, pid);

/* 예시 2: 동적 크기 CPU별 통계 배열 — Generic Radix Tree 적합 */
GENRADIX(struct cpu_stats) per_cpu_data;
genradix_init(&per_cpu_data);

struct cpu_stats *stats = genradix_ptr_alloc(
    &per_cpu_data, cpu_id, GFP_KERNEL);
stats->packets_rx++;

/* 예시 3: bcachefs에서의 실제 사용 */
/* bcachefs는 Generic Radix Tree를 키-값 테이블, */
/* 저널 엔트리 배열 등에 광범위하게 사용합니다 */
GENRADIX(struct journal_entry) journal_entries;
struct journal_entry *je = genradix_ptr_alloc(
    &journal_entries, seq_nr, GFP_KERNEL);

Radix Tree 노드 구조 시각화

struct radix_tree_node는 커널의 Radix Tree를 구성하는 핵심 빌딩 블록입니다. 각 노드는 RADIX_TREE_MAP_SIZE(64)개의 슬롯 배열과 3종류의 태그 비트맵 배열을 포함하며, 64비트 시스템에서 약 576바이트를 차지합니다. 이 섹션에서는 실제 메모리 레이아웃과 각 필드의 배치를 상세히 시각화합니다.

radix_tree_node 구조체 정의

/* include/linux/radix-tree.h — radix_tree_node 구조체 */
#define RADIX_TREE_MAP_SHIFT    6
#define RADIX_TREE_MAP_SIZE    (1UL << RADIX_TREE_MAP_SHIFT)  /* 64 */
#define RADIX_TREE_MAP_MASK    (RADIX_TREE_MAP_SIZE - 1)     /* 0x3F */
#define RADIX_TREE_TAG_LONGS   \
    ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)  /* 1 (64-bit) */
#define RADIX_TREE_MAX_TAGS    3

struct radix_tree_node {
    unsigned char   shift;          /* 이 노드가 담당하는 비트 시프트량 */
    unsigned char   offset;         /* 부모 노드의 slots[] 내 위치 */
    unsigned char   count;          /* NULL이 아닌 슬롯의 개수 */
    unsigned char   exceptional;    /* 예외(shadow) 엔트리 개수 */
    struct radix_tree_node *parent; /* 부모 노드 (RCU 안전 접근) */
    struct radix_tree_root *root;   /* 루트 구조체 포인터 */

    union {
        struct list_head private_list; /* SLAB reclaim 용 리스트 */
        struct rcu_head  rcu_head;     /* RCU 해제용 콜백 */
    };

    /* 태그 비트맵: 각 슬롯의 상태를 비트로 관리 */
    unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];

    /* 슬롯 배열: 자식 노드 또는 데이터 포인터 */
    void __rcu      *slots[RADIX_TREE_MAP_SIZE];
};

노드 할당과 SLAB 캐시

/* lib/radix-tree.c — 노드 메모리 관리 */
static struct kmem_cache *radix_tree_node_cachep;

/* 커널 초기화 시 SLAB 캐시 생성 */
void __init radix_tree_init(void)
{
    /* SLAB_PANIC: 실패 시 커널 패닉 */
    /* SLAB_RECLAIM_ACCOUNT: 메모리 압박 시 회수 가능 */
    radix_tree_node_cachep = kmem_cache_create(
        "radix_tree_node",
        sizeof(struct radix_tree_node), 0,
        SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
        NULL);

    /* percpu prealloc 풀 초기화 */
    radix_tree_init_maxnodes();
}

/* 노드 할당 — GFP 플래그에 따른 분기 */
static struct radix_tree_node *
radix_tree_node_alloc(struct radix_tree_root *root,
                      struct radix_tree_node *parent,
                      gfp_t gfp, unsigned int shift,
                      unsigned int offset, unsigned int count,
                      unsigned int exceptional)
{
    struct radix_tree_node *ret;

    /* 먼저 percpu prealloc 풀에서 시도 */
    ret = kmem_cache_alloc(radix_tree_node_cachep, gfp | __GFP_ACCOUNT);
    if (!ret)
        return NULL;

    ret->shift = shift;
    ret->offset = offset;
    ret->count = count;
    ret->exceptional = exceptional;
    ret->parent = parent;
    ret->root = root;

    /* 태그 비트맵과 슬롯을 모두 0으로 초기화 */
    memset(ret->tags, 0, sizeof(ret->tags));
    memset(ret->slots, 0, sizeof(ret->slots));

    return ret;
}

태그 전파 메커니즘 시각화

Radix Tree의 태그 전파(Tag Propagation)는 리프에서 루트로 진행되는 상향식 메커니즘입니다. PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_WRITEBACK, PAGECACHE_TAG_TOWRITE 세 가지 태그가 존재하며, 리프 노드에서 태그가 설정되면 해당 정보가 조상 노드까지 비트맵으로 전파됩니다. 이를 통해 특정 태그가 설정된 항목이 서브트리에 존재하는지를 O(1)에 판별할 수 있습니다.

tag_clear() 역전파 구현

/* lib/radix-tree.c — tag_clear의 역방향 전파 상세 */
/* 핵심: 모든 자식의 태그가 0이 되어야만 부모 비트도 클리어 */

static inline int any_tag_set(
    const struct radix_tree_node *node,
    unsigned int tag)
{
    unsigned idx;
    /* RADIX_TREE_TAG_LONGS개의 unsigned long을 검사 */
    for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
        if (node->tags[tag][idx])
            return 1;  /* 아직 태그된 자식 존재 */
    }
    return 0;  /* 모든 자식이 클리어됨 */
}

/* tag_clear 전파 예시 흐름 */
/*
 * radix_tree_tag_clear(root, 65, DIRTY):
 *   1. L0 노드 A의 tags[DIRTY] bit 1 클리어
 *   2. any_tag_set(L0_node_A, DIRTY) 검사
 *      → bit 4(index 68)가 아직 1이므로 true
 *      → 부모 전파 중단! L1 노드 A의 비트는 그대로 유지
 *
 * 만약 index 68도 클리어한 후:
 *   1. L0 노드 A의 tags[DIRTY] bit 4 클리어
 *   2. any_tag_set(L0_node_A, DIRTY) = false
 *      → L1 노드 A의 tags[DIRTY] bit 1 클리어
 *   3. any_tag_set(L1_node_A, DIRTY) 검사
 *      → bit 4(index 68 방향)도 0이면 = false
 *      → 루트의 tags[DIRTY] bit 0 클리어
 *   4. root_tag_clear(root, DIRTY) if 전체 트리에 dirty 없음
 */

gang_lookup_tag의 태그 기반 스킵

/* lib/radix-tree.c — 태그 기반 빠른 순회 */
unsigned int radix_tree_gang_lookup_tag(
    const struct radix_tree_root *root,
    void **results, unsigned long first_index,
    unsigned int max_items, unsigned int tag)
{
    struct radix_tree_iter iter;
    void **slot;
    unsigned int ret = 0;

    /* 먼저 루트 태그 검사 — O(1)에 전체 트리 확인 */
    if (!root_tag_get(root, tag))
        return 0;  /* 트리 전체에 해당 태그 없음 */

    /* 이터레이터를 사용한 순회 */
    radix_tree_for_each_tagged(slot, root, &iter,
                               first_index, tag) {
        results[ret] = rcu_dereference_raw(*slot);
        if (!results[ret])
            continue;
        if (++ret == max_items)
            break;
    }
    /* 태그 비트가 0인 서브트리는 자동으로 건너뜀 */
    /* → 전체 N개 중 태그된 M개만 방문 (M << N 가능) */
    return ret;
}

Radix Tree Lookup 경로 워크스루

radix_tree_lookup()은 unsigned long 인덱스를 받아 해당 인덱스에 저장된 포인터를 반환하는 핵심 검색 함수입니다. 인덱스의 비트를 RADIX_TREE_MAP_SHIFT(6비트)씩 상위부터 분해하여 트리를 레벨별로 하강합니다. 각 레벨에서 6비트 오프셋을 계산하여 해당 슬롯으로 이동하며, 리프에 도달하면 데이터 포인터를 반환합니다.

radix_tree_lookup() 구현 분석

/* lib/radix-tree.c — __radix_tree_lookup (핵심 경로) */
void *__radix_tree_lookup(
    const struct radix_tree_root *root,
    unsigned long index,
    struct radix_tree_node **nodep,
    void __rcu ***slotp)
{
    struct radix_tree_node *node, *parent;
    unsigned long maxindex;
    void __rcu **slot;

restart:
    parent = NULL;
    slot = (void __rcu **)&root->rnode;

    /* 루트에서 시작: rnode가 첫 번째 노드 */
    radix_tree_load_root(root, &node, &maxindex);
    if (index > maxindex)
        return NULL;  /* 트리 범위 초과 */

    while (radix_tree_is_internal_node(node)) {
        unsigned offset;

        parent = entry_to_node(node);
        /* shift 값으로 현재 레벨의 오프셋 계산 */
        offset = radix_tree_descend(parent, &node, index);
        /* offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK */
        slot = &parent->slots[offset];
    }

    /* 도달한 엔트리가 데이터 포인터인지 확인 */
    if (nodep)
        *nodep = parent;
    if (slotp)
        *slotp = slot;

    return node;  /* 데이터 포인터 또는 NULL */
}

/* 공개 API: RCU 보호 버전 */
void *radix_tree_lookup(
    const struct radix_tree_root *root,
    unsigned long index)
{
    return __radix_tree_lookup(root, index, NULL, NULL);
}

radix_tree_descend() — 레벨 하강 핵심

/* lib/radix-tree.c — 한 레벨 하강 */
static inline unsigned radix_tree_descend(
    const struct radix_tree_node *parent,
    struct radix_tree_node **nodep,
    unsigned long index)
{
    unsigned offset =
        (index >> parent->shift) & RADIX_TREE_MAP_MASK;
    /* parent->shift: 이 노드가 담당하는 비트 위치 */
    /* RADIX_TREE_MAP_MASK: 0x3F (하위 6비트 마스크) */

    void __rcu **entry = rcu_dereference_raw(
        parent->slots[offset]);
    /* RCU read-side에서도 안전하게 포인터 읽기 */

    *nodep = (void *)entry;
    return offset;
}

/* 트리 높이별 최대 인덱스 */
/*
 * height=1 (shift=0):  max = 2^6 - 1  = 63
 * height=2 (shift=6):  max = 2^12 - 1 = 4,095
 * height=3 (shift=12): max = 2^18 - 1 = 262,143
 * height=4 (shift=18): max = 2^24 - 1 = 16,777,215
 * ...
 * height=11 (shift=60): max = 2^64 - 1 (unsigned long 전체)
 */

페이지 캐시에서의 Radix Tree 역사

Radix Tree는 Linux 커널의 페이지 캐시에서 가장 핵심적인 자료구조로 사용되어 왔습니다. address_space 구조체의 page_tree 필드가 Radix Tree 루트를 가리켰으며, 파일 오프셋(페이지 인덱스)으로 페이지를 빠르게 찾는 데 사용되었습니다. Linux 4.20에서 Matthew Wilcox의 XArray 패치가 머지되면서, page_tree는 i_pages(XArray)로 교체되었습니다. 이 전환 과정에서 shadow entry를 통한 워킹셋 추적 메커니즘은 그대로 유지되었습니다.

Radix Tree 시대의 페이지 캐시 lookup

/* mm/filemap.c — Radix Tree 시대의 find_get_page (간소화) */
struct page *find_get_page(
    struct address_space *mapping,
    pgoff_t offset)
{
    void **pagep;
    struct page *page;

    rcu_read_lock();
repeat:
    page = NULL;
    pagep = radix_tree_lookup_slot(
        &mapping->page_tree, offset);
    /* page_tree: Radix Tree 루트 */

    if (pagep) {
        page = radix_tree_deref_slot(pagep);
        if (unlikely(!page))
            goto out;

        /* exceptional entry 검사 (shadow entry) */
        if (radix_tree_exception(page)) {
            if (radix_tree_deref_retry(page))
                goto repeat;  /* concurrent update */
            goto out;  /* shadow entry */
        }

        /* page 참조 카운트 증가 (get) */
        if (!page_cache_get_speculative(page))
            goto repeat;

        /* 매핑이 바뀌었는지 재확인 */
        if (unlikely(page != *pagep)) {
            put_page(page);
            goto repeat;
        }
    }
out:
    rcu_read_unlock();
    return page;
}

/* XArray 시대의 동일 함수: filemap_get_folio() */
/*
 * struct folio *filemap_get_folio(
 *     struct address_space *mapping, pgoff_t index)
 * {
 *     return xa_load(&mapping->i_pages, index);
 *     // xa_load가 RCU/retry/value entry 필터링을 내부 처리
 * }
 */

workingset_refault() — shadow entry 활용

/* mm/workingset.c — 워킹셋 크기 추적 핵심 */

/* shadow entry 인코딩 */
static void *pack_shadow(
    int memcgid, pg_data_t *pgdat,
    unsigned long eviction, bool workingset)
{
    eviction >>= bucket_order;
    eviction &= EVICTION_MASK;
    eviction = (eviction << WORKINGSET_SHIFT) | workingset;
    eviction = (eviction << NODES_SHIFT) | pgdat_to_nid(pgdat);
    eviction = (eviction << MEM_CGROUP_ID_SHIFT) | memcgid;

    /* Radix Tree: RADIX_TREE_EXCEPTIONAL_ENTRY로 마킹 */
    /* XArray: xa_mk_value()로 value entry 생성 */
    return xa_mk_value(eviction);
}

/* refault 시 워킹셋 판단 */
void workingset_refault(struct folio *folio,
                        void *shadow)
{
    int memcgid;
    unsigned long refault_distance;
    unsigned long active_file;
    bool workingset;
    long nr;

    unpack_shadow(shadow, &memcgid, &pgdat,
                  &eviction, &workingset);

    /* refault distance = 현재 age - eviction 시점 age */
    refault_distance = atomic_long_read(
        &lruvec->nonresident_age) - eviction;

    /* inactive list보다 작으면 → 활발하게 사용 중 */
    nr = folio_nr_pages(folio);
    active_file = lruvec_page_state(
        lruvec, NR_ACTIVE_FILE);

    if (refault_distance <= active_file) {
        /* active list로 직접 승격! */
        folio_set_active(folio);
        workingset_age_nonresident(lruvec, nr);
    }
}

Radix Tree vs XArray 성능 벤치마크

Radix Tree에서 XArray로의 전환이 단순히 API 정리만이 아니라 실질적인 성능 개선을 가져왔는지를 확인하기 위해, 동일 워크로드에서의 lookup/insert/delete 성능, 메모리 사용량, API 복잡도를 비교합니다. XArray는 내부적으로 동일한 radix tree 노드 구조를 사용하지만, 락 통합, 마크(mark) 비트 최적화, 불필요한 간접 호출 제거 등을 통해 전반적인 성능이 향상되었습니다.

Radix Tree vs XArray 마이크로벤치마크 커널 모듈

/* 벤치마크 예시: Radix Tree vs XArray 성능 측정 모듈 */
#include <linux/module.h>
#include <linux/radix-tree.h>
#include <linux/xarray.h>
#include <linux/ktime.h>

#define NUM_ENTRIES  100000
#define NUM_ITERS   10

static void bench_radix_lookup(void)
{
    RADIX_TREE(tree, GFP_KERNEL);
    ktime_t start, end;
    unsigned long i;
    s64 total_ns = 0;

    /* 준비: 엔트리 삽입 */
    for (i = 0; i < NUM_ENTRIES; i++) {
        radix_tree_preload(GFP_KERNEL);
        radix_tree_insert(&tree, i,
            (void *)((unsigned long)i | 0x1000));
        radix_tree_preload_end();
    }

    /* 측정: lookup 반복 */
    for (int iter = 0; iter < NUM_ITERS; iter++) {
        start = ktime_get();
        for (i = 0; i < NUM_ENTRIES; i++) {
            void *val = radix_tree_lookup(&tree, i);
            WARN_ON_ONCE(!val);
        }
        end = ktime_get();
        total_ns += ktime_to_ns(ktime_sub(end, start));
    }
    pr_info("radix_tree lookup: %lld ns/op\n",
            total_ns / (NUM_ENTRIES * NUM_ITERS));
}

static void bench_xarray_lookup(void)
{
    DEFINE_XARRAY(xa);
    ktime_t start, end;
    unsigned long i;
    s64 total_ns = 0;

    /* 준비: 엔트리 저장 — preload 불필요! */
    for (i = 0; i < NUM_ENTRIES; i++) {
        xa_store(&xa, i,
            xa_mk_value(i), GFP_KERNEL);
    }

    /* 측정: lookup 반복 */
    for (int iter = 0; iter < NUM_ITERS; iter++) {
        start = ktime_get();
        for (i = 0; i < NUM_ENTRIES; i++) {
            void *val = xa_load(&xa, i);
            WARN_ON_ONCE(!val);
        }
        end = ktime_get();
        total_ns += ktime_to_ns(ktime_sub(end, start));
    }
    pr_info("xarray lookup: %lld ns/op\n",
            total_ns / (NUM_ENTRIES * NUM_ITERS));

    /* 정리 */
    xa_destroy(&xa);
}

커널 소스 분석: radix_tree_insert() 경로

radix_tree_insert()는 트리에 새 엔트리를 삽입하는 핵심 함수입니다. 내부적으로 __radix_tree_create()를 호출하여 삽입 위치를 준비하고, 슬롯에 포인터를 기록합니다. 이 과정에서 트리 높이가 부족하면 radix_tree_extend()로 자동 확장됩니다.

/* lib/radix-tree.c — radix_tree_insert() 핵심 구현 분석 */

/**
 * radix_tree_insert - 인덱스에 항목 삽입
 * @root: radix tree 루트
 * @index: 삽입할 인덱스
 * @item: 저장할 포인터 (반드시 정렬된 포인터여야 함)
 *
 * 이미 해당 인덱스에 항목이 있으면 -EEXIST를 반환합니다.
 * 트리 높이가 부족하면 자동으로 확장합니다.
 */
int radix_tree_insert(struct radix_tree_root *root,
                        unsigned long index, void *item)
{
    struct radix_tree_node *node;
    void __rcu **slot;
    int error;

    /* 내부 노드 포인터를 데이터로 삽입하면 안 됨 */
    BUG_ON(radix_tree_is_internal_node(item));

    /* 1단계: 삽입 경로 생성
     * - 트리 높이 부족 시 extend()
     * - 중간 노드 부재 시 할당
     * - 최종 slot 위치와 부모 node 반환 */
    error = __radix_tree_create(root, index, 0, &node, &slot);
    if (error)
        return error;

    /* 2단계: 이미 엔트리가 있는지 확인 */
    if (*slot != NULL)
        return -EEXIST;

    /* 3단계: 원자적 포인터 교체
     * rcu_assign_pointer()는 메모리 배리어를 포함하여
     * RCU reader가 일관된 데이터를 읽도록 보장합니다 */
    rcu_assign_pointer(*slot, item);

    /* 4단계: 노드 메타데이터 갱신 */
    if (node) {
        node->count++;
        if (radix_tree_exceptional_entry(item))
            node->exceptional++;
    }

    return 0;
}

/* __radix_tree_create() — 삽입 경로를 준비하는 내부 함수 */
static int __radix_tree_create(
    struct radix_tree_root *root,
    unsigned long index,
    unsigned order,
    struct radix_tree_node **nodep,
    void __rcu ***slotp)
{
    struct radix_tree_node *node = NULL, *child;
    void __rcu **slot = (void __rcu **)&root->rnode;
    unsigned long maxindex;
    unsigned int shift, offset = 0;
    unsigned long max = index | ((1UL << order) - 1);

    /* 현재 트리의 최대 인덱스 확인 */
    shift = radix_tree_load_root(root, &child, &maxindex);

    /* 인덱스가 현재 범위를 초과하면 트리 확장 */
    while (max > maxindex) {
        int error = radix_tree_extend(root, child, max);
        if (error < 0)
            return error;
        shift = error;  /* extend()는 새 shift 값 반환 */
        child = rcu_dereference_raw(root->rnode);
        maxindex = shift_maxindex(shift);
    }

    /* 트리 하강: shift를 6비트씩 줄이며 노드 탐색 */
    while (shift > order) {
        shift -= RADIX_TREE_MAP_SHIFT;  /* 6비트 감소 */

        if (child == NULL) {
            /* 빈 슬롯: 새 내부 노드 할당 (preload 풀 사용) */
            child = radix_tree_node_alloc(root, node,
                                          shift, offset, 0, 0);
            if (!child)
                return -ENOMEM;
            rcu_assign_pointer(*slot,
                               node_to_entry(child));
            if (node)
                node->count++;
        } else if (!radix_tree_is_internal_node(child))
            break;

        /* 다음 레벨로 이동 */
        node = entry_to_node(child);
        offset = radix_tree_descend(node, &child, index);
        slot = &node->slots[offset];
    }

    *nodep = node;
    *slotp = slot;
    return 0;
}

커널 소스 분석: radix_tree_lookup() 경로 추적

radix_tree_lookup()은 주어진 인덱스에 대응하는 포인터를 찾아 반환합니다. RCU 보호 아래에서 잠금 없이 동작하며, 인덱스의 6비트씩을 추출하여 트리를 한 레벨씩 하강합니다.

/* lib/radix-tree.c — radix_tree_lookup() 상세 분석
 *
 * 핵심: rcu_dereference_raw()로 각 슬롯을 읽어 트리를 하강합니다.
 * 내부 노드인지 데이터 포인터인지를 최하위 비트로 구별합니다.
 */

void *radix_tree_lookup(
    const struct radix_tree_root *root,
    unsigned long index)
{
    return __radix_tree_lookup(root, index, NULL, NULL);
}

/* 실제 lookup 구현 — 노드와 슬롯 위치도 반환 가능 */
void *__radix_tree_lookup(
    const struct radix_tree_root *root,
    unsigned long index,
    struct radix_tree_node **nodep,
    void __rcu ***slotp)
{
    struct radix_tree_node *node, *parent;
    unsigned long maxindex;
    void *entry;

restart:
    /* 루트에서 시작: rnode를 RCU-safe하게 읽기 */
    entry = rcu_dereference_raw(root->rnode);
    if (!radix_tree_is_internal_node(entry)) {
        /* 트리 높이가 0: rnode가 직접 데이터 */
        if (index > 0)
            return NULL;
        if (nodep)
            *nodep = NULL;
        if (slotp)
            *slotp = (void __rcu **)&root->rnode;
        return entry;
    }

    /* 트리 하강 루프 */
    do {
        parent = entry_to_node(entry);
        /* 인덱스가 현재 트리 범위를 초과하면 NULL */
        if (index > shift_maxindex(parent->shift))
            return NULL;

        /* 오프셋 계산: 인덱스의 해당 6비트 추출
         * offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK
         * RADIX_TREE_MAP_MASK = 0x3F (63) */
        unsigned offset =
            (index >> parent->shift) & RADIX_TREE_MAP_MASK;

        /* RCU-safe 슬롯 읽기 */
        entry = rcu_dereference_raw(parent->slots[offset]);
        if (!entry)
            return NULL;

        /* sibling 엔트리 처리 (multi-order) */
        if (is_sibling_entry(parent, entry)) {
            entry = rcu_dereference_raw(
                *((void __rcu **)entry));
        }
    } while (radix_tree_is_internal_node(entry));
    /* 내부 노드가 아니면 데이터 포인터 → 루프 종료 */

    if (nodep)
        *nodep = parent;
    if (slotp)
        *slotp = &parent->slots[offset];

    return entry;
}

커널 소스 분석: radix_tree_node 슬롯 레이아웃

radix_tree_node의 64개 슬롯은 인덱스의 6비트 청크(chunk)에 대응합니다. 각 슬롯은 자식 노드(내부 노드)를 가리키거나 최종 데이터 포인터를 담습니다. 슬롯 내용물의 타입은 포인터의 하위 비트로 구별됩니다.

/* include/linux/radix-tree.h — 슬롯 접근 매크로와 엔트리 타입 */

/* 슬롯 수 결정 */
#define RADIX_TREE_MAP_SHIFT  6
#define RADIX_TREE_MAP_SIZE   (1UL << RADIX_TREE_MAP_SHIFT)  /* 64 */
#define RADIX_TREE_MAP_MASK   (RADIX_TREE_MAP_SIZE - 1)    /* 0x3F */

/* 태그 관련 상수 */
#define RADIX_TREE_MAX_TAGS   3
#define RADIX_TREE_TAG_LONGS  \
    ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
/* 64비트 시스템: (64 + 63) / 64 = 1
 * 32비트 시스템: (64 + 31) / 32 = 2 */

/* 노드 크기 분석 (64비트 시스템):
 *   shift:       1 byte
 *   offset:      1 byte
 *   count:       1 byte
 *   exceptional: 1 byte
 *   padding:     4 bytes (정렬)
 *   parent:      8 bytes (포인터)
 *   root:        8 bytes (포인터)
 *   union/list:  16 bytes
 *   slots[64]:   64 × 8 = 512 bytes  ← 노드의 89%
 *   tags[3][1]:  3 × 8 = 24 bytes
 *   ─────────────────────────────
 *   총 약 576 bytes
 */

/* 오프셋 계산 함수 — 인덱스에서 슬롯 위치 추출 */
static inline unsigned int get_slot_offset(
    const struct radix_tree_node *node,
    void __rcu **slot)
{
    /* slot 주소에서 배열 시작 주소를 빼서 인덱스 계산 */
    return slot - node->slots;
}

/* 최대 트리 높이: 64비트 키 / 6비트 per 레벨 = 최대 11레벨
 * 실제로는 페이지 캐시에서 2~3레벨이 일반적:
 *   - height=1 (shift=0): 인덱스 0~63
 *   - height=2 (shift=6): 인덱스 0~4095 (16KB~16MB 파일)
 *   - height=3 (shift=12): 인덱스 0~262143 (~1GB 파일)
 */

커널 소스 분석: 태그 연산과 부모 전파

radix_tree_tag_set()과 radix_tree_tag_get()은 페이지 캐시의 핵심 연산입니다. 태그를 설정하면 리프 노드에서 루트 방향으로 비트맵이 전파되고, 태그를 해제하면 모든 자식이 해제된 경우에만 부모도 해제됩니다.

/* lib/radix-tree.c — tag_get() 구현 분석
 *
 * tag_get은 특정 인덱스에 태그가 설정되어 있는지 확인합니다.
 * 루트의 태그 비트부터 확인하여 빈 서브트리를 빠르게 걸러냅니다.
 */

int radix_tree_tag_get(
    const struct radix_tree_root *root,
    unsigned long index,
    unsigned int tag)
{
    struct radix_tree_node *node, *parent;
    unsigned long maxindex;

    /* 1단계: 루트 레벨에서 태그 존재 여부 빠른 확인
     * 루트에 해당 태그가 없으면 트리 전체에 없음 → 즉시 반환 */
    if (!root_tag_get(root, tag))
        return 0;

    node = rcu_dereference_raw(root->rnode);
    if (!radix_tree_is_internal_node(node))
        return (node != NULL);

    /* 2단계: 트리 하강하며 각 레벨의 태그 비트 확인 */
    do {
        node = entry_to_node(node);
        unsigned offset =
            (index >> node->shift) & RADIX_TREE_MAP_MASK;

        /* 이 레벨에서 해당 슬롯의 태그 비트 확인 */
        if (!tag_get(node, tag, offset))
            return 0;  /* 태그 없음 → 하위도 볼 필요 없음 */

        /* 다음 레벨로 이동 */
        node = rcu_dereference_raw(node->slots[offset]);
    } while (radix_tree_is_internal_node(node));

    /* 리프까지 도달: 태그가 설정된 상태 */
    return 1;
}

/* tag_get/tag_set 비트 연산 — 매우 간단한 비트맵 조작 */
static inline int tag_get(
    const struct radix_tree_node *node,
    unsigned int tag, int offset)
{
    /* tags[tag]는 unsigned long 배열
     * offset / BITS_PER_LONG → 배열 인덱스
     * offset % BITS_PER_LONG → 비트 위치 */
    return test_bit(offset, node->tags[tag]);
}

static inline void tag_set(
    struct radix_tree_node *node,
    unsigned int tag, int offset)
{
    __set_bit(offset, node->tags[tag]);
}

static inline void tag_clear(
    struct radix_tree_node *node,
    unsigned int tag, int offset)
{
    __clear_bit(offset, node->tags[tag]);
}

/* 노드 내 특정 태그의 모든 비트가 0인지 확인
 * tag_clear 전파 시 사용: 자식 모두 해제되면 부모도 해제 */
static inline int any_tag_set(
    const struct radix_tree_node *node,
    unsigned int tag)
{
    unsigned int idx;
    for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
        if (node->tags[tag][idx])
            return 1;  /* 비트가 하나라도 있으면 true */
    }
    return 0;
}

커널 소스 분석: Radix Tree가 레거시인 이유

현재 커널에서 radix-tree.h는 XArray 위에 구축된 호환 래퍼(wrapper)입니다. radix_tree_root는 실제로 xarray의 별칭이며, radix_tree_lookup()은 내부적으로 xa_load()를 호출합니다. 이 구조를 이해하면 왜 Radix Tree API가 더 이상 직접 사용되지 않는지 명확해집니다.

/* include/linux/radix-tree.h — 현재 커널의 래퍼 구조
 *
 * Linux 4.20 이후, radix_tree_root는 xarray의 타입 별칭입니다.
 * 모든 radix tree 함수는 내부적으로 XArray API를 호출합니다.
 */

/* radix_tree_root = xarray (타입 별칭) */
#define radix_tree_root    xarray

/* radix_tree_node = xa_node (타입 별칭) */
#define radix_tree_node    xa_node

/* 초기화 매크로도 XArray로 위임 */
#define RADIX_TREE_INIT(name, mask)   XARRAY_INIT(name, mask)
#define INIT_RADIX_TREE(root, mask)   xa_init_flags(root, mask)

/* lookup은 xa_load()로 직접 매핑 */
static inline void *radix_tree_lookup(
    const struct radix_tree_root *root,
    unsigned long index)
{
    return xa_load((struct xarray *)root, index);
}

/* insert는 xa_store() + 에러 변환 */
static inline int radix_tree_insert(
    struct radix_tree_root *root,
    unsigned long index, void *entry)
{
    void *old = xa_store(root, index, entry, root->xa_flags);
    if (xa_is_err(old))
        return xa_err(old);
    if (old)
        return -EEXIST;  /* Radix Tree는 덮어쓰기 거부 */
    return 0;
}

/* delete도 xa_erase()로 위임 */
static inline void *radix_tree_delete(
    struct radix_tree_root *root,
    unsigned long index)
{
    return xa_erase(root, index);
}

/* 태그 연산도 XArray mark로 위임 */
static inline void *radix_tree_tag_set(
    struct radix_tree_root *root,
    unsigned long index, unsigned int tag)
{
    xa_set_mark(root, index, tag);
    return xa_load(root, index);
}

구현 예제: 페이지 캐시 레거시 lookup 패턴

4.20 이전 커널에서 find_get_page()가 Radix Tree를 사용하여 페이지 캐시에서 페이지를 찾는 전체 과정을 분석합니다. 이 패턴은 preload, 외부 잠금, RCU 보호, speculative reference 등 Radix Tree 사용의 모든 복잡성을 보여줍니다.

/* mm/filemap.c — 페이지 캐시 레거시 lookup 전체 경로
 * (Linux 4.19 기준, 4.20에서 XArray로 전환)
 *
 * 호출 체인:
 *   sys_read() → vfs_read() → generic_file_read_iter()
 *   → filemap_get_pages() → find_get_page()
 *   → radix_tree_lookup()
 */

/* 1단계: find_get_page — 페이지 캐시에서 페이지 검색 */
struct page *find_get_page(
    struct address_space *mapping,
    pgoff_t offset)
{
    struct page *page;

    /* RCU 읽기 구간 시작 — 잠금 없이 동시 접근 허용 */
    rcu_read_lock();

repeat:
    /* Radix Tree에서 페이지 포인터 검색 */
    page = radix_tree_lookup(&mapping->page_tree, offset);

    /* NULL이면 캐시 미스 */
    if (!page)
        goto out;

    /* 예외 엔트리(shadow entry) 필터링 */
    if (radix_tree_exception(page)) {
        if (radix_tree_deref_retry(page))
            goto repeat;  /* 동시 수정 → 재시도 */
        page = NULL;
        goto out;
    }

    /* Speculative reference: 참조 카운트를 원자적으로 증가
     * 페이지가 해제 중이면 실패 → 재시도 */
    if (!page_cache_get_speculative(page))
        goto repeat;

    /* 참조 획득 후 재검증: 동시에 삭제되었을 수 있음 */
    if (unlikely(page != radix_tree_lookup(
            &mapping->page_tree, offset))) {
        put_page(page);
        goto repeat;
    }

out:
    rcu_read_unlock();
    return page;
}

/* 2단계: 페이지 캐시에 새 페이지 추가 (레거시 패턴) */
static int __add_to_page_cache_locked(
    struct page *page,
    struct address_space *mapping,
    pgoff_t offset, gfp_t gfp_mask,
    void **shadowp)
{
    int error;

    get_page(page);
    page->mapping = mapping;
    page->index = offset;

    /* preload: 원자적 컨텍스트 진입 전 노드 미리 할당 */
    error = radix_tree_maybe_preload(
        gfp_mask & GFP_RECLAIM_MASK);
    if (error) {
        page->mapping = NULL;
        put_page(page);
        return error;
    }

    /* 외부 잠금 획득 — 쓰기 경로 보호 */
    spin_lock_irq(&mapping->tree_lock);

    /* shadow entry가 있으면 교체 */
    void *old = radix_tree_lookup(
        &mapping->page_tree, offset);
    if (old) {
        if (radix_tree_exceptional_entry(old)) {
            if (shadowp)
                *shadowp = old;
            /* shadow → page 교체 */
            radix_tree_replace_slot(
                &mapping->page_tree, slot, page);
            mapping->nrexceptional--;
        } else {
            error = -EEXIST;
            goto unlock;
        }
    } else {
        /* 빈 슬롯에 새 페이지 삽입 */
        error = radix_tree_insert(
            &mapping->page_tree, offset, page);
        if (error)
            goto unlock;
    }

    mapping->nrpages++;

unlock:
    spin_unlock_irq(&mapping->tree_lock);
    radix_tree_preload_end();

    if (error) {
        page->mapping = NULL;
        put_page(page);
    }
    return error;
}

구현 예제: Radix Tree → XArray 전체 마이그레이션

실제 커널 드라이버의 Radix Tree 코드를 XArray로 전환하는 완전한 예제입니다. 초기화, CRUD 연산, 태그 기반 순회, 정리(cleanup)까지 모든 패턴을 포함합니다.

/* ═══════════════════════════════════════════════
 * BEFORE: Radix Tree 기반 오브젝트 캐시 (레거시)
 * ═══════════════════════════════════════════════ */
#include <linux/radix-tree.h>

#define MY_TAG_ACTIVE  0
#define MY_TAG_DIRTY   1

struct my_object {
    unsigned long id;
    void *data;
    struct rcu_head rcu;
};

struct my_cache_legacy {
    struct radix_tree_root  tree;
    spinlock_t             lock;  /* 외부 잠금 필수 */
    atomic_t               count;
};

/* 초기화 */
static void cache_init_legacy(struct my_cache_legacy *c)
{
    INIT_RADIX_TREE(&c->tree, GFP_ATOMIC);
    spin_lock_init(&c->lock);
    atomic_set(&c->count, 0);
}

/* 삽입: preload → lock → insert → unlock → preload_end */
static int cache_add_legacy(
    struct my_cache_legacy *c,
    struct my_object *obj)
{
    int err;

    err = radix_tree_preload(GFP_KERNEL);
    if (err)
        return err;

    spin_lock(&c->lock);
    err = radix_tree_insert(&c->tree, obj->id, obj);
    if (!err) {
        radix_tree_tag_set(&c->tree, obj->id,
                           MY_TAG_ACTIVE);
        atomic_inc(&c->count);
    }
    spin_unlock(&c->lock);
    radix_tree_preload_end();

    return err;
}

/* 검색: RCU 보호 필수 */
static struct my_object *cache_find_legacy(
    struct my_cache_legacy *c,
    unsigned long id)
{
    struct my_object *obj;

    rcu_read_lock();
    obj = radix_tree_lookup(&c->tree, id);
    rcu_read_unlock();

    return obj;
}

/* 삭제: lock → delete → unlock → RCU 해제 */
static struct my_object *cache_remove_legacy(
    struct my_cache_legacy *c,
    unsigned long id)
{
    struct my_object *obj;

    spin_lock(&c->lock);
    obj = radix_tree_delete(&c->tree, id);
    if (obj)
        atomic_dec(&c->count);
    spin_unlock(&c->lock);

    return obj;  /* 호출자가 kfree_rcu() 호출 */
}

/* dirty 오브젝트 순회: 복잡한 gang_lookup 패턴 */
static void cache_flush_dirty_legacy(
    struct my_cache_legacy *c)
{
    struct my_object *results[16];
    unsigned long index = 0;
    unsigned int found;

    rcu_read_lock();
    while ((found = radix_tree_gang_lookup_tag(
            &c->tree, (void **)results, index,
            16, MY_TAG_DIRTY))) {
        for (unsigned int i = 0; i < found; i++) {
            flush_object(results[i]);
            index = results[i]->id + 1;
        }
    }
    rcu_read_unlock();
}

/* ═══════════════════════════════════════════════
 * AFTER: XArray 기반 오브젝트 캐시 (현대적)
 * ═══════════════════════════════════════════════ */
#include <linux/xarray.h>

#define MY_MARK_ACTIVE  XA_MARK_0
#define MY_MARK_DIRTY   XA_MARK_1

struct my_cache_modern {
    struct xarray  xa;      /* spinlock 내장 */
    atomic_t      count;
    /* lock 필드 제거됨 */
};

/* 초기화: 한 줄로 완료 */
static void cache_init_modern(struct my_cache_modern *c)
{
    xa_init(&c->xa);
    atomic_set(&c->count, 0);
}

/* 삽입: 단일 호출 — preload, 외부 잠금 모두 불필요 */
static int cache_add_modern(
    struct my_cache_modern *c,
    struct my_object *obj)
{
    void *old;

    old = xa_store(&c->xa, obj->id, obj, GFP_KERNEL);
    if (xa_is_err(old))
        return xa_err(old);
    if (old)
        return -EEXIST;  /* 덮어쓰기 방지 */

    xa_set_mark(&c->xa, obj->id, MY_MARK_ACTIVE);
    atomic_inc(&c->count);
    return 0;
}

/* 검색: RCU 자동 — 단일 호출 */
static struct my_object *cache_find_modern(
    struct my_cache_modern *c,
    unsigned long id)
{
    return xa_load(&c->xa, id);
}

/* 삭제: 내장 잠금 사용 */
static struct my_object *cache_remove_modern(
    struct my_cache_modern *c,
    unsigned long id)
{
    struct my_object *obj;

    obj = xa_erase(&c->xa, id);
    if (obj)
        atomic_dec(&c->count);

    return obj;
}

/* dirty 오브젝트 순회: 매크로로 간결하게 */
static void cache_flush_dirty_modern(
    struct my_cache_modern *c)
{
    struct my_object *obj;
    unsigned long id;

    xa_for_each_marked(&c->xa, id, obj,
                       MY_MARK_DIRTY) {
        flush_object(obj);
    }
}

/* 정리: xa_destroy로 한 번에 모든 노드 해제 */
static void cache_destroy_modern(
    struct my_cache_modern *c)
{
    struct my_object *obj;
    unsigned long id;

    xa_for_each(&c->xa, id, obj) {
        xa_erase(&c->xa, id);
        kfree_rcu(obj, rcu);
    }
    xa_destroy(&c->xa);
}

참고 자료

• include/linux/radix-tree.h — Radix Tree 헤더 파일로, 주요 구조체와 API 선언을 확인할 수 있습니다 (Bootlin Elixir)
• lib/radix-tree.c — Radix Tree 핵심 구현 소스로, 삽입·검색·삭제·태그 전파 로직이 포함되어 있습니다 (Bootlin Elixir)
• include/linux/xarray.h — Radix Tree를 대체하는 XArray 헤더 파일입니다 (Bootlin Elixir)
• Trees I: Radix trees (LWN, 2006) — Jonathan Corbet이 작성한 커널 Radix Tree 자료 구조 소개 기사입니다
• A memory-efficient radix tree (LWN, 2016) — Radix Tree의 메모리 효율 개선 작업에 대한 기술 분석 기사입니다
• The XArray data structure (LWN, 2018) — Matthew Wilcox가 제안한 XArray의 설계 목표와 Radix Tree 대체 배경을 다룹니다
• The XArray API (LWN, 2018) — XArray의 구체적인 API 설계와 Radix Tree 대비 개선점을 설명합니다
• Converting filesystems to the XArray (LWN, 2020) — 파일 시스템 코드의 Radix Tree → XArray 마이그레이션 실제 사례를 다룹니다
• XArray — The Linux Kernel documentation — 커널 공식 문서의 XArray 사용 가이드로, Radix Tree 마이그레이션 방법을 포함합니다
• Radix tree — Wikipedia — Radix Tree(Patricia Trie) 자료 구조의 이론적 배경과 알고리즘 설명입니다
• The page cache (LWN, 2011) — Radix Tree의 가장 대표적인 사용처인 페이지 캐시(Page Cache)의 구현 원리를 설명합니다

관련 문서

• XArray — Radix Tree의 후속
• 페이지 캐시 — 페이지 캐시 구현
• IDR/IDA — Radix Tree 기반 ID 할당
• RCU — lockless read
• LC-Trie (FIB Trie) — IP 라우팅(Routing) 트라이, 경로·레벨 압축