Radix Tree (레거시)

Linux 커널의 Radix Tree는 정수 키 기반 매핑을 제공하는 자료구조로, 4.20 커널 이전까지 페이지 캐시의 핵심이었습니다. 현재는 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. 메모리 오버헤드 — 내부 노드 구조가 비효율적이었습니다.
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 디버깅 실습

Radix Tree(또는 XArray로 전환된) 페이지 캐시 연산을 추적하는 것은 I/O 성능 분석에서 핵심입니다. ftrace, perf, bpftrace를 활용하여 실시간으로 페이지 캐시 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로 동적 추적점 생성

# 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 삽입 시 노드 할당이 필요할 수 있는데, 원자적 컨텍스트에서는 메모리 할당이 실패할 수 있습니다. 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의 후속
• 페이지 캐시 — 페이지 캐시 구현
• IDR/IDA — Radix Tree 기반 ID 할당
• RCU — lockless read