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"

관련 문서

• XArray — Radix Tree의 후속
• 페이지 캐시 — 페이지 캐시 구현
• IDR/IDA — Radix Tree 기반 ID 할당
• RCU — lockless read