XArray 자료구조

Linux 커널의 XArray는 radix tree를 대체하는 현대적 자료구조입니다. 단순한 API, 내장 잠금(Lock), 값 엔트리 지원, RCU 기반 lock-free 읽기를 제공하며, 페이지 캐시(Page Cache)와 IDR/IDA의 핵심 기반입니다.

개요

XArray는 커널 4.20/5.0에서 도입된 자료구조로, 기존의 radix_tree를 대체합니다. Oracle의 Matthew Wilcox가 설계하고 구현했으며, unsigned long 인덱스를 키로 사용하여 포인터 또는 정수 값을 저장하는 자동 크기 조절 배열입니다.

XArray가 radix tree를 대체하게 된 주요 이유:

• 단순한 API — xa_store(), xa_load(), xa_erase() 등 직관적인 인터페이스. radix tree의 복잡한 preload/slot API를 제거
• 내장 잠금 — xa_lock spinlock이 구조체에 포함되어 별도 잠금 관리 불필요
• 값 엔트리 (Value Entry) — 포인터뿐 아니라 정수 값도 노드 할당 없이 직접 저장 가능
• 타입 안전성 — void * 대신 명확한 엔트리 타입 구분 (xa_is_value(), xa_is_err())
• RCU 기반 읽기 — 읽기 경로는 lock-free로 동작하여 높은 동시성 제공
• IDR/IDA 통합 — ID 할당 기능을 내장하여 struct idr, struct ida의 백엔드로 사용

내부 구조

XArray는 내부적으로 radix tree(기수 트리(Radix Tree))를 사용합니다. 각 노드는 64개의 슬롯을 가지며(6비트 청크), 인덱스의 비트를 상위부터 6비트씩 소비하여 트리를 탐색합니다.

struct xarray

/* 개념 예시: include/linux/xarray.h 핵심 구조 */
/* include/linux/xarray.h */
struct xarray {
    spinlock_t  xa_lock;    /* 쓰기 연산 보호용 spinlock */
    gfp_t       xa_flags;   /* 할당 플래그 + XArray 옵션 */
    void __rcu  *xa_head;   /* 루트 노드 또는 단일 엔트리 */
};

xa_head는 트리의 루트를 가리킵니다. 엔트리가 하나뿐이고 인덱스가 0이면 노드 할당 없이 xa_head에 직접 저장됩니다 (단축 경로). 엔트리가 늘어나면 xa_node를 할당하여 트리를 확장합니다.

struct xa_node

/* lib/xarray.c 내부 구조체 */
struct xa_node {
    unsigned char  shift;      /* 이 노드가 담당하는 비트 위치 (0, 6, 12, ...) */
    unsigned char  offset;     /* 부모 노드에서의 슬롯 인덱스 (0~63) */
    unsigned char  count;      /* 사용 중인 슬롯 수 (NULL이 아닌 것) */
    unsigned char  nr_values;  /* 값 엔트리(xa_mk_value) 개수 */
    struct xa_node __rcu *parent;  /* 부모 노드 (루트면 NULL) */
    struct xarray  *array;     /* 소속된 XArray */
    union {
        struct list_head private_list;  /* 해제 대기 리스트 */
        struct rcu_head  rcu_head;      /* RCU 콜백 해제용 */
    };
    void __rcu *slots[XA_CHUNK_SIZE];  /* 64개 슬롯 (자식 노드 또는 엔트리) */
    union {
        unsigned long tags[XA_MAX_MARKS][XA_MARK_LONGS];  /* 마크 비트맵 */
        unsigned long marks[XA_MAX_MARKS][XA_MARK_LONGS];
    };
};

XA_CHUNK_SIZE는 1 << XA_CHUNK_SHIFT로, 기본값은 64(6비트)입니다. 따라서 각 노드는 64개의 자식 슬롯을 가집니다. shift 필드가 0이면 리프 노드이고, 슬롯에 실제 엔트리(포인터/값)가 저장됩니다. shift가 6이면 슬롯에 리프 노드 포인터가 저장됩니다.

트리 레이아웃과 확장/축소

64비트 시스템에서 unsigned long 인덱스를 6비트씩 나누면 최대 11레벨 트리가 필요합니다(64 / 6 = 10.67). 실제로 대부분의 경우 2~3레벨이면 충분합니다:

트리 확장: 새 인덱스가 현재 트리의 커버 범위를 초과하면, 새 루트 노드를 할당하고 기존 루트를 자식으로 연결하여 높이를 1 늘립니다. 축소: 루트 노드의 자식이 하나만 남으면, 그 자식을 새 루트로 승격하여 높이를 줄입니다.

기본 API

초기화

XArray를 사용하기 전에 초기화가 필요합니다. 정적 선언과 동적 초기화 두 가지 방법이 있습니다:

/* 정적 선언 */
DEFINE_XARRAY(my_xa);                /* 기본 XArray */
DEFINE_XARRAY_FLAGS(my_xa, XA_FLAGS_LOCK_IRQ);  /* 플래그 지정 */
DEFINE_XARRAY_ALLOC(my_xa);          /* ID 할당용 (XA_FLAGS_ALLOC) */

/* 동적 초기화 */
struct xarray xa;
xa_init(&xa);                         /* 기본 플래그 */
xa_init_flags(&xa, XA_FLAGS_ALLOC);  /* ID 할당용 */

사용 가능한 플래그:

저장, 로드, 삭제

#include <linux/xarray.h>

DEFINE_XARRAY(my_xa);
struct my_obj *obj, *old;

/* xa_store: 인덱스에 엔트리 저장. 이전 엔트리를 반환 */
obj = kmalloc(sizeof(*obj), GFP_KERNEL);
old = xa_store(&my_xa, 42, obj, GFP_KERNEL);
if (xa_is_err(old)) {
    pr_err("xa_store failed: %ld\\n", xa_err(old));
    kfree(obj);
    return xa_err(old);
}
/* old가 NULL이면 슬롯이 비어있었음, 아니면 이전 엔트리 */

/* xa_load: 인덱스에서 엔트리 로드 (RCU 보호, lock-free) */
rcu_read_lock();
obj = xa_load(&my_xa, 42);
if (obj)
    pr_info("found object at index 42\\n");
rcu_read_unlock();

/* xa_erase: 인덱스의 엔트리 삭제. 이전 엔트리를 반환 */
old = xa_erase(&my_xa, 42);
if (old)
    kfree(old);  /* 이전 엔트리 해제 (필요 시) */

CAS (Compare-And-Swap) 연산

/* xa_cmpxchg: 현재 값이 old_entry와 같을 때만 new_entry로 교체 */
struct my_obj *new_obj = kmalloc(sizeof(*new_obj), GFP_KERNEL);
struct my_obj *curr;

curr = xa_cmpxchg(&my_xa, 42, old_obj, new_obj, GFP_KERNEL);
if (curr == old_obj) {
    /* 교체 성공: curr(== old_obj)를 해제 */
    kfree(old_obj);
} else if (xa_is_err(curr)) {
    /* 에러 발생 (메모리 할당 실패 등) */
    kfree(new_obj);
} else {
    /* 현재 값이 old_obj가 아님 → 교체 실패 */
    kfree(new_obj);
}

해제와 비어있는지 확인

/* xa_empty: XArray가 비어있는지 확인 */
if (xa_empty(&my_xa))
    pr_info("xarray is empty\\n");

/* xa_destroy: 모든 내부 노드 해제 (엔트리 자체는 해제하지 않음!) */
xa_destroy(&my_xa);
/* 주의: 저장된 엔트리(포인터)의 메모리는 사용자가 직접 해제해야 함 */

ID 할당

XArray는 IDR(ID Radix tree)과 IDA(ID Allocator)를 대체하는 ID 할당 기능을 내장합니다. XA_FLAGS_ALLOC 플래그로 초기화한 XArray에서 xa_alloc()을 사용하면 사용 가능한 최소 인덱스를 자동으로 찾아 엔트리를 저장합니다.

xa_alloc / xa_alloc_cyclic

DEFINE_XARRAY_ALLOC(my_ids);
u32 new_id;
struct my_obj *obj;
int ret;

obj = kzalloc(sizeof(*obj), GFP_KERNEL);
if (!obj)
    return -ENOMEM;

/* xa_alloc: 범위 내에서 가장 작은 빈 ID를 할당 */
ret = xa_alloc(&my_ids, &new_id, obj, xa_limit_32b, GFP_KERNEL);
if (ret < 0) {
    kfree(obj);
    return ret;
}
pr_info("allocated ID: %u\\n", new_id);

/* xa_alloc_cyclic: 순환 방식으로 ID 할당 (재사용 최소화) */
static u32 next_id = 0;
ret = xa_alloc_cyclic(&my_ids, &new_id, obj, xa_limit_32b, &next_id, GFP_KERNEL);
/* ret == 1이면 wrap-around 발생, 0이면 정상, 음수면 에러 */

xa_limit 구조체

struct xa_limit {
    u32 min;   /* 최소 인덱스 (포함) */
    u32 max;   /* 최대 인덱스 (포함) */
};

/* 미리 정의된 범위 */
#define xa_limit_32b  XA_LIMIT(0, UINT_MAX)        /* 0 ~ 4G-1 */
#define xa_limit_31b  XA_LIMIT(0, INT_MAX)         /* 0 ~ 2G-1 (양수만) */

/* 커스텀 범위 */
struct xa_limit my_limit = XA_LIMIT(100, 999);  /* 100~999 범위 */
ret = xa_alloc(&my_ids, &new_id, obj, my_limit, GFP_KERNEL);

IDR에서 XArray로의 전환

/* === 기존 IDR 코드 === */
static DEFINE_IDR(my_idr);
static DEFINE_MUTEX(my_lock);
int id;

mutex_lock(&my_lock);
id = idr_alloc(&my_idr, obj, 0, 0, GFP_KERNEL);
mutex_unlock(&my_lock);

/* === XArray 대체 코드 === */
static DEFINE_XARRAY_ALLOC(my_xa);
u32 id;

/* xa_alloc이 내부적으로 xa_lock을 사용하므로 별도 mutex 불필요 */
ret = xa_alloc(&my_xa, &id, obj, xa_limit_32b, GFP_KERNEL);

/* 조회도 더 단순 */
obj = xa_load(&my_xa, id);  /* RCU 보호하에 lock-free */

순회

XArray는 다양한 순회 매크로(Macro)를 제공합니다. 모든 순회는 RCU 보호하에 동작하며, NULL 엔트리는 자동으로 건너뜁니다.

xa_for_each 계열

struct my_obj *obj;
unsigned long index;

/* 전체 순회: 모든 엔트리를 인덱스 순서대로 방문 */
xa_for_each(&my_xa, index, obj) {
    pr_info("index=%lu, obj=%p\\n", index, obj);
}

/* 지정 위치부터 순회 */
index = 100;
xa_for_each_start(&my_xa, index, obj, 100) {
    pr_info("index=%lu (from 100)\\n", index);
}

/* 범위 순회 */
xa_for_each_range(&my_xa, index, obj, 10, 50) {
    pr_info("index=%lu (10~50)\\n", index);
}

/* 마크된 항목만 순회 */
xa_for_each_marked(&my_xa, index, obj, XA_MARK_0) {
    pr_info("index=%lu (marked with MARK_0)\\n", index);
}

xa_find / xa_find_after

/* xa_find: indexp에서 시작하여 max까지 필터에 맞는 첫 엔트리 검색 */
unsigned long index = 0;
void *entry;

entry = xa_find(&my_xa, &index, ULONG_MAX, XA_PRESENT);
/* index가 찾은 엔트리의 인덱스로 갱신됨 */
if (entry)
    pr_info("first entry at index %lu\\n", index);

/* xa_find_after: index 다음 위치부터 검색 (index 자체는 제외) */
entry = xa_find_after(&my_xa, &index, ULONG_MAX, XA_PRESENT);
if (entry)
    pr_info("next entry at index %lu\\n", index);

/* 수동 순회 패턴 (xa_find_after 반복) */
index = 0;
entry = xa_find(&my_xa, &index, ULONG_MAX, XA_PRESENT);
while (entry) {
    process_entry(index, entry);
    entry = xa_find_after(&my_xa, &index, ULONG_MAX, XA_PRESENT);
}

마크 (Mark/Tag)

XArray의 각 엔트리에는 3개의 마크 비트를 설정할 수 있습니다. 마크는 xa_node의 비트맵(Bitmap)에 저장되며, 마크된 엔트리만 효율적으로 순회할 수 있습니다.

/* 3개의 마크 */
XA_MARK_0   /* 범용 마크 0 */
XA_MARK_1   /* 범용 마크 1 */
XA_MARK_2   /* 범용 마크 2 */

/* 마크 설정 */
xa_set_mark(&my_xa, 42, XA_MARK_0);

/* 마크 해제 */
xa_clear_mark(&my_xa, 42, XA_MARK_0);

/* 마크 확인 */
if (xa_get_mark(&my_xa, 42, XA_MARK_0))
    pr_info("index 42 is marked\\n");

/* XArray 전체에서 특정 마크가 설정된 엔트리가 있는지 확인 */
if (xa_marked(&my_xa, XA_MARK_0))
    pr_info("at least one entry has MARK_0\\n");

실제 사용 사례: 페이지 캐시 태그

페이지 캐시에서 XArray 마크는 dirty/writeback 상태 추적에 사용됩니다:

/* include/linux/pagemap.h */
#define PAGECACHE_TAG_DIRTY      XA_MARK_0  /* dirty 페이지 */
#define PAGECACHE_TAG_WRITEBACK  XA_MARK_1  /* writeback 중인 페이지 */
#define PAGECACHE_TAG_TOWRITE    XA_MARK_2  /* writeback 예정 페이지 */

/* 페이지가 dirty로 설정될 때 */
xa_set_mark(&mapping->i_pages, page->index, PAGECACHE_TAG_DIRTY);

/* dirty 페이지만 효율적으로 순회 (fsync, writeback 등) */
xa_for_each_marked(&mapping->i_pages, index, folio, PAGECACHE_TAG_DIRTY) {
    /* 이 folio를 디스크에 기록 */
    write_folio(folio);
}

마크 전파 메커니즘

값 엔트리 (Value Entry)

XArray는 포인터뿐 아니라 정수 값을 직접 저장할 수 있습니다. 값 엔트리는 노드 할당 없이 슬롯에 인라인으로 저장되므로 매우 효율적입니다.

LSB 메커니즘

커널의 모든 동적 할당 포인터는 최소 4바이트(대부분 8바이트) 정렬이므로, 하위 비트가 항상 0입니다. XArray는 이를 활용하여 LSB(최하위 비트)가 1이면 값 엔트리, 0이면 포인터로 구분합니다:

/* 값 엔트리 생성: v를 왼쪽으로 1비트 시프트하고 LSB를 1로 설정 */
static inline void *xa_mk_value(unsigned long v)
{
    return (void *)((unsigned long)(v) << 1) | 1);
}

/* 값 엔트리에서 정수 추출: LSB를 제거하고 오른쪽으로 1비트 시프트 */
static inline unsigned long xa_to_value(const void *entry)
{
    return (unsigned long)(entry) >> 1;
}

/* 값 엔트리 여부 확인 */
static inline bool xa_is_value(const void *entry)
{
    return (unsigned long)(entry) & 1;
}

값 엔트리 사용 예제

DEFINE_XARRAY(counters);

/* 정수 값을 값 엔트리로 저장 (노드 할당 없음) */
xa_store(&counters, 0, xa_mk_value(100), GFP_KERNEL);
xa_store(&counters, 1, xa_mk_value(200), GFP_KERNEL);

/* 값 엔트리 로드 */
void *entry = xa_load(&counters, 0);
if (xa_is_value(entry)) {
    unsigned long val = xa_to_value(entry);
    pr_info("counter[0] = %lu\\n", val);  /* 출력: counter[0] = 100 */
}

/* 포인터와 값 엔트리가 혼재할 수 있음 */
xa_store(&counters, 2, some_pointer, GFP_KERNEL);  /* 포인터 */
xa_store(&counters, 3, xa_mk_value(42), GFP_KERNEL);  /* 정수 값 */

/* 순회 시 타입 구분 */
unsigned long index;
void *e;
xa_for_each(&counters, index, e) {
    if (xa_is_value(e))
        pr_info("[%lu] value: %lu\\n", index, xa_to_value(e));
    else
        pr_info("[%lu] pointer: %p\\n", index, e);
}

다중 인덱스 엔트리 (Multi-Index Entries)

하나의 엔트리가 여러 연속 인덱스에 걸쳐 저장될 수 있습니다. 이는 주로 THP(Transparent Huge Page)와 대형 폴리오(large folio)에서 사용됩니다. 예를 들어, 2MB 대형 폴리오는 512개의 4KB 페이지(Page) 인덱스를 차지합니다.

/* xa_store_order: 2^order 크기의 엔트리 저장 */
/* order=9 → 512개 인덱스(0~511)에 같은 엔트리가 매핑됨 */
void *old = xa_store_order(&xa, 0, 9, huge_folio, GFP_KERNEL);

/* 0~511 어떤 인덱스로 로드해도 같은 엔트리 반환 */
xa_load(&xa, 0);    /* == huge_folio */
xa_load(&xa, 255);  /* == huge_folio */
xa_load(&xa, 511);  /* == huge_folio */

/* 페이지 캐시에서의 실제 사용: 대형 폴리오 삽입 */
static int filemap_add_folio(struct address_space *mapping,
                             struct folio *folio, pgoff_t index,
                             gfp_t gfp)
{
    /* folio_order(folio)는 대형 폴리오의 order (예: 9 = 2MB) */
    xa_store_order(&mapping->i_pages, index,
                   folio_order(folio), folio, gfp);
    /* ... */
}

고급 API (xas_*)

고급 API는 xa_state 구조체를 사용하여 트리 내 현재 위치를 추적합니다. 기본 API(xa_store 등)가 매번 루트부터 탐색하는 반면, 고급 API는 커서(cursor) 방식으로 이전 위치부터 이어서 작업할 수 있어 배치 처리에 매우 효율적입니다.

xa_state 선언과 기본 사용

/* XA_STATE 매크로로 xa_state를 스택에 선언 */
XA_STATE(xas, &my_xa, start_index);

/* 고급 API로 로드 */
void *entry;
rcu_read_lock();
entry = xas_load(&xas);
if (entry)
    pr_info("found: %p\\n", entry);
rcu_read_unlock();

/* 고급 API로 저장 (xa_lock 보유 필요) */
xa_lock(&my_xa);
xas_store(&xas, new_entry);
xa_unlock(&my_xa);

고급 API 순회

XA_STATE(xas, &my_xa, 0);
void *entry;

/* xas_for_each: 효율적인 순회 (lock/RCU 보호 필요) */
rcu_read_lock();
xas_for_each(&xas, entry, ULONG_MAX) {
    if (xas_retry(&xas, entry))
        continue;  /* 동시 수정으로 인한 재시도 */

    /* entry 처리 */
    process_entry(xas_index(&xas), entry);
}
rcu_read_unlock();

/* 에러 확인 */
if (xas_error(&xas))
    pr_err("iteration error: %d\\n", xas_error(&xas));

고급 API 마크 조작

XA_STATE(xas, &my_xa, target_index);

/* 현재 위치의 마크 설정/해제 (xa_lock 보유 필요) */
xa_lock(&my_xa);
xas_load(&xas);           /* 위치로 이동 */
xas_set_mark(&xas, XA_MARK_0);    /* 마크 설정 */
xas_clear_mark(&xas, XA_MARK_1);  /* 마크 해제 */
xa_unlock(&my_xa);

고급 API의 장점

/* 메모리 사전 할당 패턴: 원자적 컨텍스트에서 저장 */
XA_STATE(xas, &my_xa, index);

/* 1단계: 프로세스 컨텍스트에서 노드 미리 할당 */
do {
    xas_lock(&xas);
    xas_store(&xas, entry);
    xas_unlock(&xas);
} while (xas_nomem(&xas, GFP_KERNEL));
/* xas_nomem: 메모리 부족 시 true 반환하고 GFP_KERNEL로 할당 후 재시도 */

잠금 모델

XArray는 읽기-쓰기 비대칭 잠금 모델을 사용합니다. 읽기는 RCU로 보호되어 lock-free이고, 쓰기만 spinlock이 필요합니다.

잠금 변형

/* 기본 spinlock */
xa_lock(&xa);
/* ... 쓰기 연산 ... */
xa_unlock(&xa);

/* IRQ 비활성화 (인터럽트 핸들러에서도 XArray 접근 시) */
xa_lock_irq(&xa);
/* ... */
xa_unlock_irq(&xa);

/* Bottom-half 비활성화 (softirq에서도 접근 시) */
xa_lock_bh(&xa);
/* ... */
xa_unlock_bh(&xa);

/* IRQ 플래그 저장 (중첩 인터럽트 처리용) */
unsigned long flags;
xa_lock_irqsave(&xa, flags);
/* ... */
xa_unlock_irqrestore(&xa, flags);

잠금 규칙 요약

외부 잠금 사용 패턴

/* 여러 연산을 원자적으로 수행할 때 __xa_ 접두사 함수 사용 */
xa_lock(&my_xa);

/* lock 보유 상태에서 여러 연산 수행 */
old = __xa_store(&my_xa, 10, entry_a, GFP_NOWAIT);
__xa_store(&my_xa, 20, entry_b, GFP_NOWAIT);
__xa_set_mark(&my_xa, 10, XA_MARK_0);
__xa_erase(&my_xa, 30);

xa_unlock(&my_xa);

/* 주의: __xa_store에서 GFP_KERNEL 등 슬립 가능한 플래그 사용 금지!
 * spinlock 보유 중이므로 GFP_NOWAIT 또는 GFP_ATOMIC 사용 */

에러 처리

XArray의 쓰기 연산은 에러를 ERR_PTR로 반환합니다. 이는 포인터와 에러 코드를 같은 반환값으로 구분하는 커널의 표준 패턴입니다.

/* xa_store 실패 시 ERR_PTR 반환 */
void *old = xa_store(&my_xa, index, entry, GFP_KERNEL);
if (xa_is_err(old)) {
    int err = xa_err(old);  /* -ENOMEM 등 */
    pr_err("xa_store failed: %d\\n", err);
    return err;
}

/* xa_err: 에러 포인터에서 에러 코드 추출 */
static inline int xa_err(void *entry)
{
    if (xa_is_err(entry))
        return (int)(((unsigned long)entry >> 2) | (~0UL << (62)));
    return 0;
}

/* 일반적인 에러 처리 패턴 */
struct my_obj *obj = kzalloc(sizeof(*obj), GFP_KERNEL);
if (!obj)
    return -ENOMEM;

old = xa_store(&my_xa, id, obj, GFP_KERNEL);
if (xa_is_err(old)) {
    kfree(obj);  /* 저장 실패 시 할당한 메모리 해제 */
    return xa_err(old);
}
/* 성공: old에 이전 엔트리가 있으면 필요에 따라 해제 */
if (old)
    kfree(old);

/* xa_alloc의 에러 처리 */
u32 id;
int ret;

ret = xa_alloc(&my_xa, &id, obj, xa_limit_32b, GFP_KERNEL);
switch (ret) {
case 0:
    /* 성공: id에 할당된 인덱스 */
    break;
case -ENOMEM:
    /* 메모리 할당 실패 */
    kfree(obj);
    break;
case -EBUSY:
    /* 범위 내 가용 ID 없음 */
    kfree(obj);
    break;
}

Radix Tree 마이그레이션

기존 radix tree API에서 XArray로 전환할 때의 대응 관계:

실제 커널 활용

페이지 캐시 (address_space->i_pages)

XArray의 가장 중요한 사용처는 페이지 캐시입니다. 커널 5.0에서 address_space->i_pages가 radix tree에서 XArray로 전환되었습니다:

/* include/linux/fs.h */
struct address_space {
    struct inode           *host;
    struct xarray           i_pages;    /* 페이지 캐시! (이전: page_tree) */
    atomic_t                i_mmap_writable;
    struct rb_root_cached   i_mmap;
    unsigned long           nrpages;
    /* ... */
};

/* 페이지 캐시에서 folio 검색 */
struct folio *filemap_get_folio(struct address_space *mapping, pgoff_t index)
{
    struct folio *folio;

    rcu_read_lock();
    folio = xa_load(&mapping->i_pages, index);
    /* RCU 보호하에 lock-free로 페이지 검색 */
    if (folio && !folio_try_get(folio))
        folio = NULL;
    rcu_read_unlock();

    return folio;
}

IDR 백엔드

struct idr은 내부적으로 XArray를 사용합니다:

/* include/linux/idr.h */
struct idr {
    struct xarray  idr_rt;       /* 내부 XArray */
    unsigned int   idr_base;     /* 시작 ID */
    unsigned int   idr_next;     /* 다음 할당 ID 힌트 */
};

/* idr_alloc은 내부적으로 xa_alloc 호출 */
int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
{
    u32 id;
    int ret;

    if (WARN_ON_ONCE(start < 0))
        return -EINVAL;

    ret = xa_alloc(&idr->idr_rt, &id, ptr,
                   XA_LIMIT(start, end > 0 ? end - 1 : INT_MAX), gfp);
    if (ret)
        return ret;
    return id;
}

IDA 백엔드

/* include/linux/idr.h */
struct ida {
    struct xarray  xa;  /* 내부 XArray (값 엔트리로 비트맵 관리) */
};

/* IDA는 값 엔트리를 비트맵으로 활용하여 순수 ID 할당에 최적화 */
DEFINE_IDA(my_ida);
int id = ida_alloc(&my_ida, GFP_KERNEL);  /* 내부: XArray 값 엔트리 사용 */
ida_free(&my_ida, id);

성능 특성

시간/공간 복잡도

공간 복잡도: 각 xa_node는 약 576바이트입니다 (64 슬롯 x 8바이트 + 메타데이터 + 마크 비트맵). 엔트리가 듬성듬성 분포하면 빈 슬롯이 많아져 공간 낭비가 발생할 수 있습니다. 단, 인덱스 0에 단일 엔트리만 있으면 xa_head에 직접 저장되어 노드 할당이 전혀 없습니다.

자료구조 비교

선택 기준

• XArray를 선택: 정수 키(인덱스), 범위 순회 필요, 마크/태그 필요, ID 할당 필요, RCU lock-free 읽기 필요
• Hashtable을 선택: 비정수 키, 정확한 키 매칭만 필요, 매우 큰 데이터셋에서 O(1) 검색이 중요
• Red-Black Tree를 선택: 비정수 키, 정렬된 순회 필요, 범위 쿼리 필요, 메모리 효율성 중요
• Linked List를 선택: 순서만 중요하고 인덱스 기반 검색 불필요, 단순한 FIFO/LIFO

실전 종합 예제

다음은 XArray를 활용한 커널 모듈의 완전한 예제입니다. ID 할당, 마크, 순회, 에러 처리를 모두 포함합니다:

/* 실습 예제: XArray 기반 세션 테이블 커널 모듈 */
#include <linux/module.h>
#include <linux/xarray.h>
#include <linux/slab.h>

struct my_session {
    u32 id;
    char name[32];
    bool active;
};

static DEFINE_XARRAY_ALLOC(sessions);

/* 새 세션 생성: ID 자동 할당 */
static struct my_session *session_create(const char *name)
{
    struct my_session *s;
    u32 id;
    int ret;

    s = kzalloc(sizeof(*s), GFP_KERNEL);
    if (!s)
        return ERR_PTR(-ENOMEM);

    strscpy(s->name, name, sizeof(s->name));
    s->active = true;

    /* ID 할당 (1~65535 범위) */
    ret = xa_alloc(&sessions, &id, s, XA_LIMIT(1, 65535), GFP_KERNEL);
    if (ret) {
        kfree(s);
        return ERR_PTR(ret);
    }
    s->id = id;

    /* active 세션에 마크 설정 */
    xa_set_mark(&sessions, id, XA_MARK_0);

    pr_info("session created: id=%u name=%s\\n", id, name);
    return s;
}

/* 세션 검색 */
static struct my_session *session_find(u32 id)
{
    return xa_load(&sessions, id);  /* RCU lock-free 읽기 */
}

/* 세션 비활성화 */
static void session_deactivate(u32 id)
{
    struct my_session *s = xa_load(&sessions, id);
    if (s) {
        s->active = false;
        xa_clear_mark(&sessions, id, XA_MARK_0);
    }
}

/* 세션 삭제 */
static void session_destroy(u32 id)
{
    struct my_session *s = xa_erase(&sessions, id);
    if (s) {
        pr_info("session destroyed: id=%u name=%s\\n", s->id, s->name);
        kfree_rcu(s, rcu);  /* RCU grace period 후 해제 */
    }
}

/* active 세션만 순회 */
static void session_list_active(void)
{
    struct my_session *s;
    unsigned long id;

    pr_info("--- active sessions ---\\n");
    xa_for_each_marked(&sessions, id, s, XA_MARK_0) {
        pr_info("  [%lu] %s\\n", id, s->name);
    }
}

/* 전체 세션 정리 */
static void session_cleanup_all(void)
{
    struct my_session *s;
    unsigned long id;

    xa_for_each(&sessions, id, s) {
        xa_erase(&sessions, id);
        kfree(s);
    }
    xa_destroy(&sessions);
}

static int __init my_init(void)
{
    struct my_session *s1, *s2, *s3;

    s1 = session_create("alpha");
    s2 = session_create("beta");
    s3 = session_create("gamma");
    if (IS_ERR(s1) || IS_ERR(s2) || IS_ERR(s3))
        return -ENOMEM;

    session_list_active();       /* alpha, beta, gamma */
    session_deactivate(s2->id); /* beta 비활성화 */
    session_list_active();       /* alpha, gamma */

    return 0;
}

static void __exit my_exit(void)
{
    session_cleanup_all();
}

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

XArray 운영 루틴

XArray는 현대 커널의 기본 인덱스 자료구조로 자리잡았습니다. 정상 동작의 핵심은 xa_lock 사용 규칙, RCU 읽기 모델, 엔트리 타입 구분을 일관되게 유지하는 것입니다.

# XArray 사용 경로 점검
git grep -n "xa_store\\|xa_load\\|xa_erase\\|xa_for_each" -- "*.c"
git grep -n "xa_lock\\|rcu_read_lock" -- "*.c"

XA_STATE 커서

xa_state 구조체는 XArray 트리 안에서의 현재 위치(커서)를 추적하는 핵심 메커니즘입니다. 기본 API가 매 호출마다 루트부터 탐색하는 반면, xa_state는 이전 탐색 결과를 기억하여 인접 인덱스 접근 시 불필요한 재탐색을 제거합니다.

XA_STATE 초기화와 내부 필드

/* include/linux/xarray.h */
struct xa_state {
    struct xarray  *xa;         /* 대상 XArray */
    unsigned long   xa_index;   /* 현재 인덱스 */
    unsigned char   xa_shift;   /* 현재 노드의 shift */
    unsigned char   xa_sibs;    /* 형제(sibling) 수 */
    unsigned char   xa_offset;  /* 노드 내 슬롯 오프셋 */
    unsigned char   xa_pad;     /* 패딩 */
    struct xa_node *xa_node;    /* 현재 위치의 노드 */
    struct xa_node *xa_alloc;   /* 사전 할당된 노드 */
    xa_update_node_t xa_update; /* 노드 변경 콜백 */
};

/* XA_STATE 매크로: 스택에 xa_state 선언 */
#define XA_STATE(name, array, index)              \
    struct xa_state name = __XA_STATE(array, index, 0, 0)

/* 특수 xa_node 값 */
#define XAS_RESTART  ((struct xa_node *)1)  /* 루트부터 재탐색 필요 */
#define XAS_ERROR(err)  ...                    /* 에러 상태 */
#define XAS_BOUNDS  ...                        /* 범위 초과 */

xas_load / xas_store 내부 동작

/* xas_load: 커서 위치에서 엔트리 로드 */
XA_STATE(xas, &my_xa, 135);

rcu_read_lock();
void *entry = xas_load(&xas);
/* 내부 동작:
 * 1. xa_node == XAS_RESTART이면 루트부터 탐색 시작
 * 2. index(135)를 6비트씩 분해: [상위][중간][하위=7]
 * 3. 루트 → 중간 노드 → 리프 노드로 내려감
 * 4. xa_node = 리프 노드, xa_offset = 7
 * 5. slots[7]의 엔트리 반환
 */

/* xas_next: 다음 인덱스로 이동 (같은 노드 내에서 O(1)) */
entry = xas_next(&xas);
/* xa_index=136, xa_offset=8, 같은 리프 노드에서 slots[8] 반환 */

/* xas_find: NULL이 아닌 다음 엔트리 찾기 */
entry = xas_find(&xas, ULONG_MAX);
/* 빈 슬롯을 건너뛰고 다음 유효 엔트리까지 이동 */
rcu_read_unlock();

/* xas_store: 커서 위치에 엔트리 저장 (xa_lock 필요) */
XA_STATE(xas2, &my_xa, 200);
xa_lock(&my_xa);
xas_store(&xas2, new_entry);
xa_unlock(&my_xa);

xas_retry / xas_pause: RCU 반복 안전성

/* RCU 보호 순회에서 동시 수정 처리 */
XA_STATE(xas, &my_xa, 0);
void *entry;

rcu_read_lock();
xas_for_each(&xas, entry, ULONG_MAX) {
    /* xas_retry: 동시 수정으로 인해 무효화된 엔트리 감지 */
    if (xas_retry(&xas, entry))
        continue;  /* 자동으로 해당 인덱스를 재로드 */

    /* 긴 처리 전에 RCU grace period 양보 */
    if (need_resched() || xas_nomem(&xas, GFP_KERNEL)) {
        xas_pause(&xas);      /* 현재 위치 저장 */
        rcu_read_unlock();
        cond_resched();
        rcu_read_lock();
        /* xas_pause 후 다음 반복에서 자동으로 위치 복원 */
    }
}
rcu_read_unlock();

/* xas_retry가 필요한 이유:
 * RCU 읽기 중 다른 CPU가 xa_store()로 노드를 교체하면,
 * 이전 노드의 슬롯이 "retry" 마커로 바뀜.
 * xas_retry()는 이를 감지하고 루트부터 재탐색을 트리거함 */

Multi-index 엔트리

Multi-index 엔트리는 하나의 엔트리가 2^order개의 연속 인덱스에 매핑(Mapping)되는 기능입니다. 커널의 THP(Transparent Huge Pages)와 대형 폴리오(large folio)에서 핵심적으로 사용되며, 단일 2MB 폴리오가 512개(2⁹)의 4KB 페이지 인덱스를 차지할 때 각 인덱스에서 동일한 폴리오를 반환합니다.

xa_store_range 구현

/* xa_store_range: 범위 내 모든 인덱스에 같은 엔트리 저장 */
void *xa_store_range(struct xarray *xa, unsigned long first,
                     unsigned long last, void *entry, gfp_t gfp)
{
    XA_STATE(xas, xa, first);
    void *curr;

    if (WARN_ON_ONCE(xa_is_internal(entry)))
        return XA_ERROR(-EINVAL);

    do {
        xas_lock(&xas);
        if (first == last) {
            /* 단일 인덱스: 일반 저장 */
            curr = xas_store(&xas, entry);
        } else {
            /* 범위: order 기반 multi-index 저장 */
            xas_set_range(&xas, first, last);
            curr = xas_store(&xas, entry);
        }
        xas_unlock(&xas);
    } while (xas_nomem(&xas, gfp));

    return curr;
}

/* 사용 예: 인덱스 0~511에 같은 대형 폴리오 매핑 */
xa_store_range(&mapping->i_pages, 0, 511, huge_folio, GFP_KERNEL);

THP 페이지 캐시 통합

/* 페이지 캐시에서 대형 폴리오 삽입 (mm/filemap.c 기반) */
static noinline int __filemap_add_folio(
    struct address_space *mapping,
    struct folio *folio,
    pgoff_t index, gfp_t gfp, void **shadowp)
{
    XA_STATE(xas, &mapping->i_pages, index);
    int huge = folio_test_hugetlb(folio);
    long nr = folio_nr_pages(folio);  /* order=9면 512 */

    xas_set_order(&xas, index, folio_order(folio));
    /* xas_set_order: multi-index 엔트리로 설정
     * 내부적으로 sibling 슬롯을 생성하여
     * index ~ index+nr-1 모두 같은 folio를 가리킴 */

    do {
        unsigned int order = xa_get_order(xas.xa, xas.xa_index);
        void *entry, *old = NULL;

        xas_lock_irq(&xas);
        xas_store(&xas, folio);
        if (xas_error(&xas))
            goto unlock;

        mapping->nrpages += nr;
unlock:
        xas_unlock_irq(&xas);
    } while (xas_nomem(&xas, gfp));

    return xas_error(&xas);
}

마크(Mark) 전파 메커니즘

XArray의 마크 시스템은 리프 노드에서 설정된 마크 비트가 루트까지 상향 전파되는 구조입니다. 이로 인해 xa_for_each_marked()는 마크되지 않은 서브트리 전체를 O(1)에 건너뛸 수 있어, 대규모 XArray에서도 마크된 엔트리만 효율적으로 순회합니다.

xa_set_mark / xa_clear_mark 내부 코드

/* lib/xarray.c: 마크 설정 내부 구현 (간략화) */
static void node_set_mark(struct xa_node *node,
                          unsigned int offset, xa_mark_t mark)
{
    /* 1. 현재 노드의 비트맵에 비트 설정 */
    __set_bit(offset, node->marks[(__force unsigned)mark]);
}

static void xas_set_mark(const struct xa_state *xas, xa_mark_t mark)
{
    struct xa_node *node = xas->xa_node;
    unsigned int offset = xas->xa_offset;

    /* 리프 노드부터 루트까지 상향 순회하며 마크 전파 */
    while (node) {
        if (node_get_mark(node, offset, mark))
            return;  /* 이미 설정됨 → 상위도 이미 설정된 상태 */
        node_set_mark(node, offset, mark);
        offset = node->offset;   /* 부모에서의 슬롯 위치 */
        node = xa_parent(node->array, node);  /* 부모로 이동 */
    }
}

/* 마크 해제는 역방향 전파: 비트 해제 후 전체 0이면 부모도 해제 */
static void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark)
{
    struct xa_node *node = xas->xa_node;
    unsigned int offset = xas->xa_offset;

    while (node) {
        node_clear_mark(node, offset, mark);
        /* 이 노드에 다른 마크된 슬롯이 남아있으면 전파 중단 */
        if (node_any_mark(node, mark))
            return;
        offset = node->offset;
        node = xa_parent(node->array, node);
    }
}

페이지 캐시 dirty/writeback 마크 활용

/* 페이지가 dirty로 마크되는 흐름 (fs/buffer.c 기반) */
void folio_mark_dirty(struct folio *folio)
{
    struct address_space *mapping = folio->mapping;

    xa_lock_irqsave(&mapping->i_pages, flags);
    /* PAGECACHE_TAG_DIRTY == XA_MARK_0 */
    __xa_set_mark(&mapping->i_pages, folio->index, PAGECACHE_TAG_DIRTY);
    xa_unlock_irqrestore(&mapping->i_pages, flags);
    /* 마크 전파: 리프→부모→루트까지 DIRTY 비트가 전파됨 */
}

/* writeback: dirty 마크된 폴리오만 효율적으로 수집 */
void writeback_dirty_folios(struct address_space *mapping)
{
    struct folio *folio;
    unsigned long index;

    /* O(dirty 페이지 수 × log₆₄ n)로 dirty 페이지만 순회 */
    xa_for_each_marked(&mapping->i_pages, index, folio,
                       PAGECACHE_TAG_DIRTY) {
        /* dirty → writeback 전환 */
        xa_clear_mark(&mapping->i_pages, index, PAGECACHE_TAG_DIRTY);
        xa_set_mark(&mapping->i_pages, index, PAGECACHE_TAG_WRITEBACK);

        submit_folio_for_writeback(folio);
    }
}

페이지 캐시 XArray 활용

address_space.i_pages는 커널에서 XArray를 가장 집중적으로 사용하는 곳입니다. 모든 파일의 페이지 캐시가 이 XArray를 통해 관리되며, 일반 페이지/폴리오뿐 아니라 shadow 엔트리(workingset 추적)와 DAX 엔트리(영구 메모리)도 저장됩니다.

filemap_get_folio / filemap_add_folio 코드 워크스루

/* mm/filemap.c: 페이지 캐시에서 folio 검색 (간략화) */
struct folio *__filemap_get_folio(struct address_space *mapping,
                                  pgoff_t index, fgf_t fgp_flags,
                                  gfp_t gfp)
{
    struct folio *folio;

repeat:
    folio = filemap_get_entry(mapping, index);
    if (xa_is_value(folio)) {
        /* Shadow 엔트리: workingset refault 추적에 사용 */
        if (fgp_flags & FGP_ENTRY)
            return folio;  /* 호출자가 shadow 처리 */
        folio = NULL;  /* shadow는 유효 folio가 아님 */
    }
    if (!folio)
        goto no_page;

    /* folio 참조 카운트 증가 (RCU 보호 하에) */
    if (!folio_try_get(folio))
        goto repeat;  /* 동시 해제 → 재시도 */

    /* folio가 여전히 이 mapping에 속하는지 확인 */
    if (unlikely(folio->mapping != mapping)) {
        folio_put(folio);
        goto repeat;
    }

    return folio;

no_page:
    if (fgp_flags & FGP_CREAT) {
        /* 페이지 없으면 새로 할당하여 캐시에 추가 */
        folio = filemap_alloc_folio(gfp, 0);
        if (!folio)
            return ERR_PTR(-ENOMEM);
        filemap_add_folio(mapping, folio, index, gfp);
    }
    return folio;
}

Shadow 엔트리와 Workingset 감지

/* mm/workingset.c: shadow 엔트리 관리 */

/* 페이지가 evict될 때 shadow 엔트리로 교체 */
void workingset_eviction(struct folio *folio,
                        struct mem_cgroup *target_memcg)
{
    unsigned long eviction;
    struct lruvec *lruvec;

    /* eviction 타임스탬프를 값 엔트리로 인코딩 */
    eviction = atomic_long_read(&lruvec->nonresident_age);
    eviction = pack_shadow(eviction, memcgid, pgdat, workingset);

    /* XArray에 shadow 엔트리 저장 (원래 folio 대신) */
    xa_store(&mapping->i_pages, folio->index,
             xa_mk_value(eviction), GFP_KERNEL);
    /* 이제 해당 인덱스에는 folio 대신 shadow가 저장됨 */
}

/* 페이지 재진입 시 refault 감지 */
bool workingset_test_recent(void *shadow, bool file,
                           bool *workingset)
{
    /* shadow 엔트리에서 eviction 타임스탬프 추출 */
    unsigned long eviction = xa_to_value(shadow);
    unpack_shadow(eviction, &memcgid, &pgdat, workingset);

    /* 현재 시간과 비교하여 refault 여부 판단 */
    refault_distance = (refault - eviction) & EVICTION_MASK;
    return refault_distance <= lruvec_page_state(lruvec, NR_INACTIVE);
    /* true면 working set에 속하므로 active list로 직접 승격 */
}

잠금 모델

XArray의 잠금 설계는 읽기-쓰기 비대칭의 극단적 최적화입니다. 읽기 경로(xa_load, xa_for_each)는 RCU로 완전히 lock-free이고, 쓰기 경로만 spinlock을 사용합니다. 이 설계는 읽기가 압도적으로 많은 페이지 캐시의 워크로드에 최적화되어 있습니다.

xas_lock_irq: 인터럽트(Interrupt) 컨텍스트 잠금

/* 인터럽트 핸들러에서도 XArray를 수정하는 경우 */
/* 페이지 캐시가 대표적 — writeback 완료 인터럽트에서 마크 해제 */

/* 프로세스 컨텍스트: xa_lock_irq 사용 (IRQ 비활성화) */
xa_lock_irq(&mapping->i_pages);
__xa_store(&mapping->i_pages, index, folio, 0);
xa_unlock_irq(&mapping->i_pages);

/* 인터럽트 컨텍스트: xa_lock_irqsave 사용 */
unsigned long flags;
xa_lock_irqsave(&mapping->i_pages, flags);
__xa_clear_mark(&mapping->i_pages, index, PAGECACHE_TAG_WRITEBACK);
xa_unlock_irqrestore(&mapping->i_pages, flags);

/* XA_FLAGS_LOCK_IRQ: XArray 초기화 시 IRQ 잠금 자동 사용 */
/* 기본 xa_store()도 내부적으로 xa_lock_irq()를 사용하게 됨 */
xa_init_flags(&xa, XA_FLAGS_LOCK_IRQ);

잠금 경쟁 패턴과 완화 전략

/* 배치 쓰기로 lock 경쟁 완화 패턴 */
XA_STATE(xas, &my_xa, start);

/* xa_lock을 한 번만 잡고 여러 엔트리를 일괄 처리 */
xa_lock(&my_xa);
for (i = 0; i < batch_size; i++) {
    xas_set(&xas, indices[i]);
    xas_store(&xas, entries[i]);
    if (xas_error(&xas))
        break;
}
xa_unlock(&my_xa);

/* 메모리 부족 시 재시도 */
if (xas_nomem(&xas, GFP_KERNEL))
    goto retry;

메모리 관리(Memory Management)와 노드 할당

XArray의 내부 노드(xa_node)는 동적으로 할당/해제됩니다. 노드 할당 실패 시의 graceful 처리, RCU 기반 지연(Latency) 해제, 그리고 메모리 오버헤드는 XArray 성능을 이해하는 핵심 요소입니다.

xas_nomem 재시도 패턴 상세

/* xas_nomem: 메모리 할당 실패 후 재시도하는 표준 패턴 */
XA_STATE(xas, &my_xa, index);

/* do-while 루프로 할당 실패 시 자동 재시도 */
do {
    xas_lock(&xas);        /* spinlock 획득 */
    xas_store(&xas, entry); /* 저장 시도 */
    xas_unlock(&xas);      /* spinlock 해제 */
} while (xas_nomem(&xas, GFP_KERNEL));
/* xas_nomem 동작:
 * 1. xas에 에러가 없으면 → false 반환 (루프 종료)
 * 2. xas에 -ENOMEM이면 →
 *    a. GFP_KERNEL로 xa_node 할당 (슬립 가능)
 *    b. xas->xa_alloc에 저장
 *    c. 에러 상태 클리어
 *    d. true 반환 (루프 재시도)
 * 3. 다른 에러면 → false 반환 (루프 종료, 에러 유지)
 */

/* 최종 에러 확인 */
if (xas_error(&xas))
    return xas_error(&xas);

/* 인터럽트 컨텍스트에서의 사전 할당 패턴 */
XA_STATE(xas, &my_xa, index);

/* 프로세스 컨텍스트에서 미리 노드 할당 */
if (xas_nomem(&xas, GFP_KERNEL)) {
    /* 노드가 xas.xa_alloc에 준비됨 */
}
/* 이후 인터럽트 컨텍스트에서 저장 */
xas_lock_irq(&xas);
xas_store(&xas, entry);  /* 사전 할당된 노드 사용 → 추가 할당 불필요 */
xas_unlock_irq(&xas);

에러 처리 패턴

XArray는 포인터 값 안에 에러 코드를 인코딩하는 커널 표준 패턴(ERR_PTR/IS_ERR)과 유사하지만 별도의 인코딩을 사용합니다. XArray 에러 엔트리는 하위 2비트가 10인 특수 내부 엔트리입니다.

xa_err / xa_is_err 인코딩 상세

/* include/linux/xarray.h: 에러 인코딩 */

/* 내부 엔트리 생성: 값을 2비트 왼쪽 시프트하고 하위 비트를 10으로 설정 */
static inline void *xa_mk_internal(unsigned long v)
{
    return (void *)((v << 2) | 2);
}

/* 에러 여부 확인: 내부 엔트리 + 상위 비트에 음수 errno가 인코딩 */
static inline bool xa_is_err(const void *entry)
{
    return unlikely(xa_is_internal(entry) &&
                    entry >= xa_mk_internal(-MAX_ERRNO));
}

/* 에러 코드 추출 */
static inline int xa_err(void *entry)
{
    if (xa_is_err(entry))
        return (long)entry >> 2;  /* 부호 확장 포함 */
    return 0;
}

/* 예시: -ENOMEM (-12) 인코딩 과정 */
/*   xa_mk_internal(-12) = (-12 << 2) | 2
 *   = 0xFFFFFFFFFFFFFFD0 | 2
 *   = 0xFFFFFFFFFFFFFFD2
 *   xa_err(0xFFFFFFFFFFFFFFD2) = (long)0xFFFFFFFFFFFFFFD2 >> 2
 *   = 0xFFFFFFFFFFFFFFF4 = -12
 */

xas_error / xas_set_err 활용

/* xa_state의 에러 관리 */
XA_STATE(xas, &my_xa, 0);

/* xas에 에러 설정: 이후 모든 xas_* 연산이 no-op으로 됨 */
xas_set_err(&xas, -EINVAL);

/* 에러 상태에서는 store가 아무 동작도 하지 않음 (안전) */
xas_store(&xas, entry);  /* no-op */

/* 에러 확인 */
int err = xas_error(&xas);  /* -EINVAL */

/* 일반적인 에러 복구 패턴 */
XA_STATE(xas, &xa, index);
void *old;

do {
    xas_lock(&xas);
    old = xas_load(&xas);
    if (old && !valid_entry(old)) {
        xas_set_err(&xas, -EEXIST);
        xas_unlock(&xas);
        break;
    }
    xas_store(&xas, new_entry);
    xas_unlock(&xas);
} while (xas_nomem(&xas, GFP_KERNEL));

if (xas_error(&xas)) {
    pr_err("XArray operation failed: %d\\n", xas_error(&xas));
    return xas_error(&xas);
}

ftrace/perf 디버깅(Debugging) 실습

XArray 관련 성능 문제나 동작 확인 시 커널의 ftrace, bpftrace, perf 도구를 활용할 수 있습니다. 페이지 캐시가 XArray를 사용하므로, 파일 I/O 성능 분석에서도 이 도구들이 유용합니다.

ftrace로 XArray 함수 추적

# XArray 관련 커널 함수 목록 확인
cat /sys/kernel/debug/tracing/available_filter_functions | grep "^xa_\|^xas_"

# function_graph tracer로 xa_store 호출 경로 추적
echo function_graph > /sys/kernel/debug/tracing/current_tracer
echo xa_store > /sys/kernel/debug/tracing/set_graph_function
echo 1 > /sys/kernel/debug/tracing/tracing_on

# 테스트 I/O 수행 후 결과 확인
dd if=/dev/zero of=/tmp/test bs=4k count=100
cat /sys/kernel/debug/tracing/trace

# 출력 예시:
#  0)               |  xa_store() {
#  0)   0.150 us    |    xas_store();
#  0)   0.080 us    |    xas_init_marks();
#  0)   1.200 us    |  }

# 추적 중단
echo 0 > /sys/kernel/debug/tracing/tracing_on
echo nop > /sys/kernel/debug/tracing/current_tracer

bpftrace로 페이지 캐시 XArray 모니터링

# 페이지 캐시 xa_load(조회) 빈도를 프로세스별로 집계
bpftrace -e '
kprobe:xa_load {
    @load_count[comm] = count();
}
interval:s:5 {
    print(@load_count);
    clear(@load_count);
}'

# xa_store(삽입) 시 인덱스 분포 히스토그램
bpftrace -e '
kprobe:xa_store {
    @index_hist = hist(arg1);   /* arg1 = index */
}
interval:s:10 {
    print(@index_hist);
    clear(@index_hist);
}'

# 페이지 캐시 miss (xa_load 반환값이 NULL) 추적
bpftrace -e '
kretprobe:xa_load /retval == 0/ {
    @cache_miss[comm] = count();
}'

perf probe로 XArray 지연 시간 측정

# perf probe 설정: xa_store 진입/반환 지점
perf probe --add 'xa_store_entry=xa_store'
perf probe --add 'xa_store_ret=xa_store%return'

# 10초간 xa_store 이벤트 기록
perf record -e probe:xa_store_entry -e probe:xa_store_ret -a -- sleep 10

# 결과 분석
perf script | head -20

# perf stat으로 XArray 함수 호출 빈도 측정
perf stat -e 'probe:xa_store_entry' -a -- sleep 5

# 정리
perf probe --del 'xa_store_entry'
perf probe --del 'xa_store_ret'

# 캐시 미스 분석 (XArray 노드 접근 패턴)
perf stat -e cache-misses,cache-references,L1-dcache-load-misses \
    -a -- dd if=/tmp/largefile of=/dev/null bs=4k count=10000

성능 분석

XArray의 성능은 인덱스 분포, 워크로드 패턴, 동시성 수준에 따라 크게 달라집니다. 이 섹션에서는 XArray와 다른 커널 자료구조의 성능을 정량적으로 비교하고, 캐시 동작과 NUMA 영향을 분석합니다.

자료구조 성능 비교표

캐시 동작과 NUMA 고려사항

XArray 캐시 효율 분석:

• xa_node 구조체 크기: ~576 bytes, L1 캐시 라인: 64 bytes → xa_node 하나가 9개 캐시 라인을 차지합니다
• slots[] 배열: 64 × 8B = 512 bytes = 8 캐시 라인 → 연속 인덱스 8개를 하나의 캐시 라인에서 접근할 수 있습니다

밀집 인덱스 (0, 1, 2, ..., N):

• 리프 노드의 연속 슬롯 접근 → L1 캐시 히트율이 높습니다
• prefetch 효과로 순차 순회가 매우 빠릅니다

희소 인덱스 (0, 1000000, 2000000, ...):

• 각 인덱스가 다른 리프 노드에 분산됩니다
• 빈 중간 노드의 메모리가 낭비됩니다
• 캐시 미스가 증가합니다

NUMA 환경에서의 XArray 최적화:

XArray의 xa_node가 한 NUMA 노드에 할당되면, 다른 NUMA 노드에서 접근 시 원격 메모리 접근 지연이 발생합니다. 페이지 캐시의 해결책은 다음과 같습니다:

• address_space가 inode에 내장 → inode가 할당된 NUMA 노드에 위치합니다
• xa_node도 같은 NUMA 노드에 할당하려면 __GFP_THISNODE를 사용합니다
• 읽기 경로(xa_load)는 RCU로 lock-free이므로 NUMA 영향이 최소화됩니다

높은 동시성 환경에서는 per-NUMA XArray 분할을 고려하거나, per-CPU 배치 처리로 원격 접근 빈도를 감소시킬 수 있습니다.

대규모 인덱스 범위 확장성

고급 활용 패턴

이 섹션에서는 XArray의 고급 연산인 원자적 비교-교환(xa_cmpxchg), 순환 ID 할당(xa_alloc_cyclic), 예약(xa_reserve), 배치 처리 패턴을 다룹니다.

xa_cmpxchg: 원자적 비교-교환

/* xa_cmpxchg: 현재 값이 old와 같을 때만 new로 교체 */
struct my_obj *old_obj, *new_obj, *curr;

new_obj = kzalloc(sizeof(*new_obj), GFP_KERNEL);
if (!new_obj)
    return -ENOMEM;

/* 인덱스 42의 현재 값이 old_obj일 때만 new_obj로 교체 */
curr = xa_cmpxchg(&my_xa, 42, old_obj, new_obj, GFP_KERNEL);

if (curr == old_obj) {
    /* 성공: 이전 값(old_obj)을 RCU grace period 후 해제 */
    if (old_obj)
        kfree_rcu(old_obj, rcu);
} else if (xa_is_err(curr)) {
    /* 메모리 할당 실패 등 에러 */
    kfree(new_obj);
    return xa_err(curr);
} else {
    /* 경쟁 조건: 다른 CPU가 먼저 값을 변경함 */
    kfree(new_obj);
    /* curr에 현재 실제 값이 들어있음 → 재시도 결정 */
}

/* 활용: NULL→엔트리 삽입 (삽입 전용, 이미 있으면 실패) */
curr = xa_cmpxchg(&my_xa, index, NULL, new_entry, GFP_KERNEL);
if (curr != NULL) {
    /* 이미 엔트리가 존재함 → 삽입 실패 */
    kfree(new_entry);
}

/* 활용: 엔트리→NULL 조건부 삭제 */
curr = xa_cmpxchg(&my_xa, index, expected, NULL, GFP_KERNEL);
if (curr == expected) {
    /* 삭제 성공 */
    kfree_rcu(expected, rcu);
}

xa_alloc_cyclic: 순환 ID 할당

/* 순환 ID 할당: 이전에 할당된 ID를 가능한 재사용하지 않음 */
static DEFINE_XARRAY_ALLOC(fd_table);
static u32 next_fd = 0;  /* 다음 할당 시작점 */

int alloc_fd(struct file *file)
{
    u32 fd;
    int ret;

    ret = xa_alloc_cyclic(&fd_table, &fd, file,
                         XA_LIMIT(3, 1023),  /* fd 범위: 3~1023 */
                         &next_fd,            /* 순환 카운터 */
                         GFP_KERNEL);

    switch (ret) {
    case 0:
        /* 정상 할당: fd에 새 파일 디스크립터 */
        return fd;
    case 1:
        /* wrap-around 발생: max 도달 후 min부터 재검색 */
        pr_debug("fd allocation wrapped around\\n");
        return fd;  /* 여전히 유효한 fd */
    case -EBUSY:
        /* 범위 내 가용 ID 없음 */
        return -EMFILE;
    default:
        return ret;  /* -ENOMEM 등 */
    }
}

/* next_fd는 xa_alloc_cyclic이 자동으로 갱신함:
 * 할당 성공 시 next_fd = fd + 1
 * wrap 시 next_fd = min (범위 시작부터 재검색) */

xa_reserve: 2단계 초기화 패턴

/* xa_reserve: 인덱스를 미리 예약 (XA_ZERO_ENTRY로 채움) */
/* 용도: ID 할당 후 초기화 완료 전에 다른 할당이 같은 ID를 받지 않도록 */

u32 id;
int ret;

/* 1단계: 인덱스 예약 */
ret = xa_reserve(&my_xa, id, GFP_KERNEL);
if (ret)
    return ret;
/* 이제 인덱스 id에는 XA_ZERO_ENTRY가 저장됨
 * xa_load()는 NULL 반환 (외부에서는 비어있는 것처럼 보임)
 * xa_alloc()는 이 인덱스를 건너뜀 (이미 사용 중) */

/* 2단계: 실제 초기화 (시간이 오래 걸릴 수 있음) */
struct my_obj *obj = kzalloc(sizeof(*obj), GFP_KERNEL);
if (!obj) {
    xa_release(&my_xa, id);  /* 예약 해제 */
    return -ENOMEM;
}
initialize_obj(obj);

/* 3단계: 실제 값으로 교체 */
void *old = xa_store(&my_xa, id, obj, GFP_KERNEL);
/* old == XA_ZERO_ENTRY (내부 값, 사용자가 해제할 필요 없음) */

/* xa_release: 예약 취소 (XA_ZERO_ENTRY를 NULL로 교체) */
xa_release(&my_xa, id);
/* 이제 인덱스 id는 비어있는 상태로 복원됨 */

배치 처리 종합 예제

/* 대량 엔트리를 효율적으로 삽입하는 패턴 */
static int bulk_insert(struct xarray *xa, unsigned long start,
                       unsigned long count, void **entries)
{
    XA_STATE(xas, xa, start);
    unsigned long i;

    do {
        xas_lock(&xas);
        for (i = 0; i < count; i++) {
            xas_set(&xas, start + i);
            xas_store(&xas, entries[i]);
            if (xas_error(&xas))
                break;
        }
        xas_unlock(&xas);
    } while (xas_nomem(&xas, GFP_KERNEL));

    return xas_error(&xas);
}

/* 순회하면서 조건부 일괄 수정 */
static void bulk_update_marked(struct xarray *xa,
                              xa_mark_t mark,
                              void *new_entry)
{
    XA_STATE(xas, xa, 0);
    void *entry;

    xa_lock(xa);
    xas_for_each_marked(&xas, entry, ULONG_MAX, mark) {
        /* 마크된 엔트리를 새 값으로 교체 */
        xas_store(&xas, new_entry);
        /* 마크 해제 */
        xas_clear_mark(&xas, mark);
    }
    xa_unlock(xa);
}

커널 소스 분석: xa_store() 내부 구현

xa_store()는 XArray의 가장 핵심적인 쓰기 연산입니다. 외부에서는 단순한 인덱스-값 저장처럼 보이지만, 내부적으로는 트리 확장, 노드 할당, RCU 안전 포인터 교체, 빈 노드 축소까지 처리합니다. 실제 커널 소스(lib/xarray.c)의 핵심 경로를 단계별로 분석합니다.

/* lib/xarray.c — xa_store() 진입점 */
void *xa_store(struct xarray *xa, unsigned long index,
               void *entry, gfp_t gfp)
{
    void *curr;

    /* xa_state를 스택에 선언하고 인덱스로 초기화 */
    XA_STATE(xas, xa, index);

    /* 내부 엔트리(retry, sibling 등)의 직접 저장을 방지 */
    if (WARN_ON_ONCE(xa_is_advanced(entry)))
        return XA_ERROR(-EINVAL);

    /* 값 엔트리가 아닌 NULL을 저장하면 xa_erase와 동일하게 동작 */
    if (xa_track_free(xa) && !entry)
        entry = XA_ZERO_ENTRY;

    /* xas_nomem 루프: 메모리 할당 실패 시 재시도 */
    do {
        xas_lock(&xas);           /* xa->xa_lock 획득 */
        curr = xas_store(&xas, entry);  /* 핵심 저장 로직 */
        xas_unlock(&xas);         /* xa->xa_lock 해제 */
    } while (xas_nomem(&xas, gfp));
    /* xas_nomem: 메모리 부족 시 GFP 플래그로 할당하고 true 반환 → 재시도
     * 성공 또는 복구 불가 에러 시 false 반환 → 루프 종료 */

    return curr;  /* 이전 엔트리 반환 (에러 시 ERR_PTR) */
}

xas_store() 핵심 경로

xas_store()는 xa_state 커서를 사용하여 실제 트리 조작을 수행합니다. 이 함수는 xa_lock을 이미 보유한 상태에서 호출되며, 트리 확장과 노드 분할을 포함합니다.

/* lib/xarray.c — xas_store() 핵심 로직 (간략화) */
void *xas_store(struct xa_state *xas, void *entry)
{
    struct xa_node *node;
    void __rcu **slot = &xas->xa->xa_head;
    unsigned int offset, max;
    int count = 0;
    int values = 0;
    void *first, *next;
    bool value = xa_is_value(entry);

    /* 1단계: 트리 확장 — 인덱스가 현재 트리 범위를 초과하면 루트를 확장 */
    if (xas_top(xas->xa_node)) {
        /* xas_expand: 새 루트 노드를 할당하고 기존 루트를 자식으로 연결
         * xa_head의 shift를 올려 더 큰 인덱스 범위를 커버 */
        if (xas_expand(xas, entry))
            return XA_ERROR(-ENOMEM);
    }

    /* 2단계: 트리 탐색 — 인덱스 비트를 6비트씩 소비하며 내려감 */
    /* xas_descend: 현재 노드에서 인덱스의 해당 6비트 청크로
     * 슬롯 오프셋을 계산하고 자식 노드로 이동 */
    while ((node = xas_descend(xas, node))) {
        /* 중간 노드가 없으면 xas_create: 새 xa_node 할당 */
        if (!node)
            node = xas_create(xas, true);
    }

    /* 3단계: 리프 노드에 도달 — 실제 엔트리 교체 */
    slot = &node->slots[xas->xa_offset];
    first = xa_entry_locked(xas->xa, node, xas->xa_offset);

    /* RCU 안전 포인터 교체 */
    rcu_assign_pointer(*slot, entry);

    /* 4단계: 카운터 갱신 */
    if (first) {
        if (xa_is_value(first))
            values--;
    } else {
        count++;  /* 빈 슬롯에 저장 → count 증가 */
    }
    if (value)
        values++;
    node->count += count;
    node->nr_values += values;

    /* 5단계: 트리 축소 — 루트 노드에 자식이 하나만 남으면 높이 줄이기 */
    if (!entry)
        xas_free_nodes(xas, xa_top_pointer(xas));

    return first;  /* 이전 엔트리 반환 */
}

커널 소스 분석: xa_load() 내부 구현

xa_load()는 RCU 보호하에 lock-free로 동작하는 읽기 연산입니다. spinlock 없이 트리를 탐색하므로 높은 동시성을 제공하지만, 동시에 발생하는 쓰기 연산으로 인한 retry 엔트리를 처리해야 합니다.

/* lib/xarray.c — xa_load() */
void *xa_load(struct xarray *xa, unsigned long index)
{
    XA_STATE(xas, xa, index);
    void *entry;

    rcu_read_lock();
    do {
        entry = xas_load(&xas);
        /* xas_retry: 동시 수정으로 retry 엔트리가 감지되면
         * xa_state를 RESTART로 리셋하고 루트부터 재탐색 */
    } while (xas_retry(&xas, entry));
    rcu_read_unlock();

    return entry;
}

xas_load() 트리 탐색 로직

/* lib/xarray.c — xas_load() 내부 (간략화) */
void *xas_load(struct xa_state *xas)
{
    void *entry = xas_start(xas);
    /* xas_start: xa_node가 XAS_RESTART이면 xa_head를 entry로 설정 */

    while (xa_is_node(entry)) {
        struct xa_node *node = xa_to_node(entry);

        /* 인덱스가 이 노드의 커버 범위를 벗어나면 NULL 반환 */
        if (xas->xa_shift > node->shift)
            break;

        /* 6비트 오프셋 계산: (index >> node->shift) & XA_CHUNK_MASK */
        entry = xas_descend(xas, node);
        /* xas_descend 내부:
         *   unsigned int offset = xas_get_offset(xas);
         *   xas->xa_node = node;
         *   xas->xa_offset = offset;
         *   return rcu_dereference(node->slots[offset]);
         */

        /* sibling 엔트리 처리: multi-index 엔트리에서
         * sibling 슬롯이면 canonical 슬롯으로 리다이렉트 */
        if (xa_is_sibling(entry)) {
            unsigned long offset = xa_to_sibling(entry);
            entry = rcu_dereference(node->slots[offset]);
        }
    }

    return entry;
}

커널 소스 분석: xa_erase() 내부 구현

xa_erase()는 인덱스의 엔트리를 NULL로 교체하고, 비어진 노드를 자동으로 축소합니다. 내부적으로 xa_store(xa, index, NULL, 0)과 유사하지만, 트리 축소 로직이 핵심입니다.

/* lib/xarray.c — xa_erase() */
void *xa_erase(struct xarray *xa, unsigned long index)
{
    return xa_store(xa, index, NULL, 0);
    /* GFP가 0인 이유: 삭제는 새 노드 할당이 불필요
     * NULL 저장 시 xas_store 내부에서 트리 축소 수행 */
}

/* 트리 축소 핵심: xas_delete_node() (간략화) */
static void xas_delete_node(struct xa_state *xas)
{
    struct xa_node *node = xas->xa_node;

    while (node) {
        /* 현재 노드의 모든 슬롯이 비었는지 확인 */
        if (node->count)
            break;  /* 아직 엔트리가 남아있음 → 축소 중단 */

        /* 부모 노드에서 이 노드를 가리키는 슬롯을 NULL로 설정 */
        struct xa_node *parent = xa_parent_locked(xas->xa, node);
        if (parent) {
            parent->slots[node->offset] = NULL;
            parent->count--;
        }

        /* RCU grace period 후 노드 메모리 해제 */
        xa_node_free(node);
        /* xa_node_free 내부: call_rcu(&node->rcu_head, radix_tree_node_rcu_free)
         * 기존 RCU reader가 이 노드를 참조 중일 수 있으므로 즉시 해제 불가 */

        /* 부모 노드도 비었는지 재귀적으로 확인 */
        node = parent;
    }

    /* 루트 노드까지 축소되면 xa_head를 직접 갱신 */
    if (!node)
        xas->xa->xa_head = NULL;
}

커널 소스 분석: xa_alloc() ID 할당 메커니즘

xa_alloc()은 지정 범위 내에서 비어있는 최소 인덱스를 찾아 엔트리를 저장합니다. IDR을 대체하는 핵심 메커니즘으로, 내부적으로 XA_FREE_MARK라는 특수 마크를 활용하여 빈 슬롯을 효율적으로 검색합니다.

/* lib/xarray.c — xa_alloc() */
int xa_alloc(struct xarray *xa, u32 *id,
             void *entry, struct xa_limit limit, gfp_t gfp)
{
    XA_STATE(xas, xa, 0);
    int err;

    /* WARN: XA_FLAGS_ALLOC 없이 xa_alloc 호출은 버그 */
    WARN_ON_ONCE(!xa_track_free(xa));

    do {
        xas_lock(&xas);
        /* xas_find_marked: XA_FREE_MARK가 설정된 슬롯 검색
         * XA_FREE_MARK는 빈(NULL) 슬롯에 자동으로 설정되는 내부 마크
         * 마크 전파 덕분에 비어있지 않은 서브트리를 빠르게 건너뜀 */
        err = __xa_alloc(&xas, id, entry, limit);
        xas_unlock(&xas);
    } while (xas_nomem(&xas, gfp));

    return err;
}

/* __xa_alloc 핵심 로직 (간략화) */
static int __xa_alloc(struct xa_state *xas, u32 *id,
                      void *entry, struct xa_limit limit)
{
    /* 검색 범위 설정 */
    xas->xa_index = limit.min;

    /* XA_FREE_MARK가 설정된 첫 번째 슬롯 찾기
     * 이 마크는 NULL 엔트리에 자동 설정되므로
     * 빈 인덱스를 O(log₆₄ n)에 검색 가능 */
    xas_find_marked(xas, limit.max, XA_FREE_MARK);

    if (xas_error(xas))
        return xas_error(xas);

    /* 범위 내 빈 슬롯 없음 */
    if (xas->xa_index > limit.max)
        return -EBUSY;

    /* 찾은 빈 인덱스에 엔트리 저장 */
    *id = xas->xa_index;
    xas_store(xas, entry);
    /* xas_store 내부에서 XA_FREE_MARK 자동 해제:
     * 빈 슬롯이 엔트리로 채워졌으므로 마크 제거
     * 노드의 모든 슬롯이 채워지면 부모의 마크도 해제 (전파) */

    return 0;
}

커널 소스 분석: XArray 잠금 모델 상세

XArray의 잠금은 단순한 spinlock이 아니라, xa_lock과 RCU의 비대칭 조합으로 구현됩니다. 쓰기 측은 spinlock으로 상호 배제(Mutual Exclusion)하고, 읽기 측은 RCU read-side critical section에서 lock-free로 동작합니다. 이 섹션에서는 잠금이 실제로 어떻게 획득/해제되는지, 그리고 RCU 안전성이 어떻게 보장되는지 커널 소스 수준에서 분석합니다.

/* include/linux/xarray.h — xa_lock 변형 매크로 */
#define xa_lock(xa)              spin_lock(&(xa)->xa_lock)
#define xa_unlock(xa)            spin_unlock(&(xa)->xa_lock)
#define xa_lock_bh(xa)           spin_lock_bh(&(xa)->xa_lock)
#define xa_unlock_bh(xa)         spin_unlock_bh(&(xa)->xa_lock)
#define xa_lock_irq(xa)          spin_lock_irq(&(xa)->xa_lock)
#define xa_unlock_irq(xa)        spin_unlock_irq(&(xa)->xa_lock)
#define xa_lock_irqsave(xa, f)   spin_lock_irqsave(&(xa)->xa_lock, f)
#define xa_unlock_irqrestore(xa, f)  spin_unlock_irqrestore(&(xa)->xa_lock, f)

/* xa_store 내부의 잠금 흐름 */
void *xa_store(struct xarray *xa, unsigned long index,
               void *entry, gfp_t gfp)
{
    XA_STATE(xas, xa, index);
    void *curr;

    do {
        xas_lock(&xas);
        /* xas_lock 내부:
         * if (xa->xa_flags & XA_FLAGS_LOCK_IRQ)
         *     spin_lock_irq(&xa->xa_lock);
         * else if (xa->xa_flags & XA_FLAGS_LOCK_BH)
         *     spin_lock_bh(&xa->xa_lock);
         * else
         *     spin_lock(&xa->xa_lock);
         */

        curr = xas_store(&xas, entry);
        /* spinlock 보유 중이므로:
         * - 다른 CPU의 xa_store/xa_erase가 대기
         * - RCU reader는 병렬 실행 중 (lock-free)
         * - rcu_assign_pointer()로 포인터 교체 → 원자적 */

        xas_unlock(&xas);
    } while (xas_nomem(&xas, gfp));
    /* xas_nomem: spinlock 밖에서 GFP_KERNEL으로 메모리 할당
     * → 슬립 가능. spinlock 보유 중에는 슬립 불가하므로
     * lock 해제 후 할당하고 다시 lock 획득하여 재시도 */

    return curr;
}

RCU 읽기/쓰기 안전성 보장

/* 읽기 측: RCU read-side critical section */
rcu_read_lock();
void *entry = xa_load(&xa, index);
/* xa_load 내부:
 * 1. rcu_dereference(xa->xa_head) — 읽기 배리어 포함
 * 2. 노드를 타고 내려가며 rcu_dereference(node->slots[offset])
 * 3. retry 엔트리 감지 시 루트부터 재탐색
 *
 * 이 시점에 다른 CPU가 xa_store()로 슬롯을 교체할 수 있지만:
 * - rcu_assign_pointer()의 쓰기 배리어가 새 데이터의 가시성 보장
 * - 교체된 슬롯에는 retry 마커가 남아 xas_retry()가 감지
 * - 이전 노드는 call_rcu()로 grace period 후에만 해제
 */

/* entry가 가리키는 객체를 안전하게 사용 */
if (entry && !xa_is_value(entry))
    use_object(entry);
rcu_read_unlock();

/* 쓰기 측: xa_lock + RCU 포인터 교체 */
xa_lock(&xa);
/* 핵심: 포인터 교체 시 rcu_assign_pointer() 사용 */
rcu_assign_pointer(node->slots[offset], new_entry);
/* rcu_assign_pointer 내부:
 * smp_store_release(&p, v);
 * → new_entry의 모든 초기화가 포인터 교체 전에 가시적
 * → RCU reader가 새 포인터를 읽으면 완전히 초기화된 데이터를 봄 */

/* 이전 노드는 즉시 해제하지 않음 */
call_rcu(&old_node->rcu_head, xa_node_free_cb);
/* grace period 후 해제: 모든 RCU reader가 이전 노드 참조를 마친 후 */
xa_unlock(&xa);

커널 소스 분석: 값 엔트리 vs 포인터 엔트리

XArray의 슬롯에 저장되는 엔트리는 하위 비트 패턴으로 타입을 구분합니다. 이 비트 인코딩은 커널 포인터의 정렬 특성을 활용하며, 추가 메타데이터 없이 타입을 구분할 수 있어 매우 효율적입니다.

/* include/linux/xarray.h — 엔트리 타입 비트 인코딩 */

/* 비트[0]: 값 엔트리 표시
 * 정렬된 커널 포인터는 비트[0]=0이므로 구분 가능 */
static inline void *xa_mk_value(unsigned long v)
{
    WARN_ON((long)v < 0);
    return (void *)((v << 1) | 1);
    /* v=100 → 저장값: 0x...C9 (비트[0]=1) */
}

static inline unsigned long xa_to_value(const void *entry)
{
    return (unsigned long)entry >> 1;
}

static inline bool xa_is_value(const void *entry)
{
    return (unsigned long)entry & 1;
}

/* 비트[0:1] = 10: 내부 엔트리 (XArray 내부에서만 사용)
 * retry, sibling, zero, node 포인터 등 */
static inline bool xa_is_internal(const void *entry)
{
    return ((unsigned long)entry & 3) == 2;
}

/* 에러 엔트리: 비트[0:1] = 10 이고 특정 범위의 내부 엔트리 */
static inline bool xa_is_err(const void *entry)
{
    return unlikely(xa_is_internal(entry) &&
                    entry >= xa_mk_internal(-MAX_ERRNO));
}

/* 엔트리 타입 비트 패턴 요약:
 *   비트[0] = 0, 비트[1] = 0 → 포인터 엔트리 (정렬된 커널 주소)
 *   비트[0] = 1             → 값 엔트리 (정수 << 1 | 1)
 *   비트[0:1] = 10          → 내부 엔트리 (retry, node, zero, error)
 *   NULL (0x0)              → 빈 슬롯
 */

엔트리 타입별 실제 사용 사례

/* 1. 포인터 엔트리: 페이지 캐시에서 folio 포인터 저장 */
struct folio *folio = folio_alloc(GFP_HIGHUSER, 0);
xa_store(&mapping->i_pages, index, folio, GFP_NOFS);
/* folio 주소는 최소 PAGE_SIZE(4096) 정렬 → 하위 12비트 = 0
 * 따라서 xa_is_value() == false, xa_is_internal() == false */

/* 2. 값 엔트리: shmem의 swap 엔트리 저장 */
/* mm/shmem.c — 페이지가 swap-out되면 swap 정보를 값 엔트리로 저장 */
swp_entry_t swap = { .val = swp_val };
xa_store(&mapping->i_pages, index,
         swp_to_radix_entry(swap), GFP_NOWAIT);
/* swp_to_radix_entry: swap 값을 xa_mk_value()로 변환
 * 페이지 캐시에서 xa_load()로 읽을 때:
 *   if (xa_is_value(entry)) → swap 엔트리로 처리
 *   else → folio 포인터로 처리 */

/* 3. 혼재 처리: 순회 시 타입에 따라 분기 */
unsigned long index;
void *entry;
xa_for_each(&mapping->i_pages, index, entry) {
    if (xa_is_value(entry)) {
        /* swap 엔트리: 디스크에서 페이지를 읽어와야 함 */
        handle_swap_entry(index, entry);
    } else {
        /* folio 포인터: 메모리에 캐시된 페이지 */
        struct folio *folio = entry;
        handle_cached_folio(index, folio);
    }
}

커널 소스 분석: Multi-index 엔트리 상세

Multi-index 엔트리는 xa_store_order()를 통해 생성됩니다. 내부적으로 canonical 슬롯에 실제 포인터를, 나머지 sibling 슬롯에 canonical 오프셋을 인코딩한 내부 엔트리를 저장합니다.

/* include/linux/xarray.h — sibling 엔트리 인코딩 */
static inline void *xa_mk_sibling(unsigned int offset)
{
    return xa_mk_internal(offset);
    /* 내부 엔트리: (offset << 2) | 2
     * 비트[0:1] = 10 → 내부 엔트리로 식별
     * 상위 비트: canonical 슬롯의 offset */
}

static inline bool xa_is_sibling(const void *entry)
{
    return IS_ENABLED(CONFIG_XARRAY_MULTI) &&
           xa_is_internal(entry) &&
           entry < xa_mk_sibling(XA_CHUNK_SIZE - 1);
}

/* xas_store에서 multi-index 엔트리 저장 시 */
/* order=2 (4개 슬롯), 시작 인덱스=8일 때:
 *   slots[8] = folio;              ← canonical (실제 포인터)
 *   slots[9] = xa_mk_sibling(8);   ← sibling (canonical 위치 참조)
 *   slots[10] = xa_mk_sibling(8);  ← sibling
 *   slots[11] = xa_mk_sibling(8);  ← sibling
 */

/* xa_load에서 sibling을 만나면 canonical로 리다이렉트 */
/* lib/xarray.c — xas_descend() 내부 */
if (xa_is_sibling(entry)) {
    unsigned int offset = xa_to_sibling(entry);
    entry = rcu_dereference(node->slots[offset]);
    /* sibling이 가리키는 canonical 슬롯에서 실제 엔트리 로드 */
}

xas_set_order()와 정렬 규칙

/* lib/xarray.c — xas_set_order() (간략화) */
void xas_set_order(struct xa_state *xas,
                   unsigned long index, unsigned int order)
{
    /* 정렬 규칙: 인덱스는 2^order의 배수여야 함 */
    xas->xa_index = index >> order << order;
    /* 예: order=9, index=512 → xa_index=512 (OK)
     *     order=9, index=513 → xa_index=512 (자동 정렬) */

    /* sibling 수 계산 */
    if (order > xas->xa_shift)
        xas->xa_sibs = (1U << (order - xas->xa_shift)) - 1;
    /* order=2, shift=0 → sibs=3 (canonical 1개 + sibling 3개 = 4 슬롯) */

    /* order가 노드의 shift보다 크면 상위 레벨에서 처리
     * 예: order=9 > shift=6 → 이 노드 전체가 하나의 multi-index 엔트리
     * 상위 노드의 여러 슬롯이 sibling이 됨 */
}

/* 페이지 캐시에서의 실제 사용 (mm/filemap.c) */
static int __filemap_add_folio(
    struct address_space *mapping,
    struct folio *folio,
    pgoff_t index, gfp_t gfp, void **shadowp)
{
    XA_STATE_ORDER(xas, &mapping->i_pages, index,
                   folio_order(folio));
    /* XA_STATE_ORDER: XA_STATE + xas_set_order 결합
     * folio_order(folio) = compound_order(folio)
     * 예: 2MB 대형 폴리오 → order=9 → 512개 슬롯 */

    do {
        xas_lock_irq(&xas);
        /* xas_store: canonical 슬롯에 folio 저장,
         * 나머지 511개 슬롯에 sibling 엔트리 저장 */
        xas_store(&xas, folio);
        xas_unlock_irq(&xas);
    } while (xas_nomem(&xas, gfp));

    return xas_error(&xas);
}

구현 예제: 페이지 캐시 xa_store/xa_load 패턴

페이지 캐시는 XArray의 가장 중요한 사용처입니다. 파일 데이터를 메모리에 캐시할 때, 파일 오프셋(pgoff_t)을 인덱스로 사용하여 folio를 저장하고 조회합니다. 이 섹션에서는 페이지 캐시에서 XArray를 사용하는 실제 패턴을 코드 수준에서 분석합니다.

/* 구현 예제: 페이지 캐시 folio 삽입 (mm/filemap.c 기반) */
static int page_cache_insert_folio(
    struct address_space *mapping,
    struct folio *folio, pgoff_t index)
{
    XA_STATE(xas, &mapping->i_pages, index);
    void *old;
    int error;

    /* 대형 폴리오: order 기반 multi-index 저장 */
    if (folio_test_large(folio))
        xas_set_order(&xas, index, folio_order(folio));

    folio_ref_add(folio, folio_nr_pages(folio));

    do {
        xas_lock_irq(&xas);
        /* 인덱스가 이미 사용 중인지 확인 */
        old = xas_load(&xas);
        if (old) {
            if (xa_is_value(old)) {
                /* shadow(swap) 엔트리 → 교체 가능 */
                mapping_set_update(&xas, mapping);
            } else {
                /* 이미 다른 folio가 있음 → 실패 */
                xas_set_err(&xas, -EEXIST);
                goto unlock;
            }
        }

        /* folio를 페이지 캐시에 저장 */
        xas_store(&xas, folio);
        if (xas_error(&xas))
            goto unlock;

        mapping->nrpages += folio_nr_pages(folio);
unlock:
        xas_unlock_irq(&xas);
    } while (xas_nomem(&xas, mapping_gfp_mask(mapping)));

    if (xas_error(&xas)) {
        folio_ref_sub(folio, folio_nr_pages(folio));
        return xas_error(&xas);
    }
    return 0;
}

/* 구현 예제: 페이지 캐시 folio 조회 (mm/filemap.c 기반) */
struct folio *__filemap_get_folio(
    struct address_space *mapping, pgoff_t index,
    fgf_t fgp_flags, gfp_t gfp)
{
    struct folio *folio;

repeat:
    /* 1단계: RCU lock-free 조회 */
    folio = mapping_get_entry(mapping, index);
    /* mapping_get_entry 내부:
     *   rcu_read_lock();
     *   folio = xa_load(&mapping->i_pages, index);
     *   if (folio && !xa_is_value(folio))
     *       folio_try_get(folio);  // 참조 카운트 증가
     *   rcu_read_unlock();
     */

    if (IS_ERR(folio))
        return folio;

    if (!folio) {
        if (!(fgp_flags & FGP_CREAT))
            return ERR_PTR(-ENOENT);

        /* 2단계: folio 없으면 새로 할당하여 삽입 */
        folio = filemap_alloc_folio(gfp, 0);
        if (!folio)
            return ERR_PTR(-ENOMEM);

        int err = filemap_add_folio(mapping, folio, index, gfp);
        if (err) {
            folio_put(folio);
            if (err == -EEXIST)
                goto repeat;  /* 경쟁 조건: 다른 CPU가 먼저 삽입 → 재시도 */
            return ERR_PTR(err);
        }
    }
    return folio;
}

구현 예제: IDR을 XArray로 대체하는 패턴

기존 IDR 기반 드라이버를 XArray로 전환하는 실무 패턴입니다. XArray는 내장 잠금과 ID 할당을 제공하므로 코드가 크게 단순화됩니다.

/* === 기존 IDR 기반 드라이버 코드 === */
struct my_device {
    int  id;
    char name[64];
    /* ... 디바이스 필드 ... */
};

static DEFINE_IDR(dev_idr);
static DEFINE_MUTEX(dev_lock);  /* IDR은 잠금 미내장 → 별도 mutex 필요 */

static int old_device_register(struct my_device *dev)
{
    int id;
    mutex_lock(&dev_lock);
    id = idr_alloc(&dev_idr, dev, 0, 0, GFP_KERNEL);
    mutex_unlock(&dev_lock);
    if (id < 0)
        return id;
    dev->id = id;
    return 0;
}

static struct my_device *old_device_find(int id)
{
    struct my_device *dev;
    mutex_lock(&dev_lock);  /* 읽기에도 mutex 필요 */
    dev = idr_find(&dev_idr, id);
    mutex_unlock(&dev_lock);
    return dev;
}

static void old_device_unregister(int id)
{
    struct my_device *dev;
    mutex_lock(&dev_lock);
    dev = idr_remove(&dev_idr, id);
    mutex_unlock(&dev_lock);
    if (dev)
        kfree(dev);
}

/* === XArray로 전환한 코드 === */
static DEFINE_XARRAY_ALLOC(dev_xa);
/* mutex 제거: XArray는 xa_lock을 내장하고 있음 */

static int new_device_register(struct my_device *dev)
{
    u32 id;
    int ret;

    /* xa_alloc: 내부적으로 xa_lock을 잡고 ID 할당 + 저장 */
    ret = xa_alloc(&dev_xa, &id, dev,
                   XA_LIMIT(0, INT_MAX), GFP_KERNEL);
    if (ret)
        return ret;
    dev->id = id;
    return 0;
}

static struct my_device *new_device_find(int id)
{
    /* xa_load: RCU lock-free 읽기, mutex 불필요! */
    return xa_load(&dev_xa, id);
}

static void new_device_unregister(int id)
{
    struct my_device *dev;

    /* xa_erase: 내부적으로 xa_lock을 잡고 삭제 */
    dev = xa_erase(&dev_xa, id);
    if (dev)
        kfree_rcu(dev, rcu);
    /* kfree_rcu: RCU reader가 아직 참조 중일 수 있으므로
     * grace period 후 해제 */
}

/* 디바이스 순회: lock 없이 RCU로 순회 */
static void new_device_list_all(void)
{
    struct my_device *dev;
    unsigned long id;

    xa_for_each(&dev_xa, id, dev) {
        pr_info("device[%lu]: %s\\n", id, dev->name);
    }
}

/* 정리 */
static void new_device_cleanup(void)
{
    struct my_device *dev;
    unsigned long id;

    xa_for_each(&dev_xa, id, dev) {
        xa_erase(&dev_xa, id);
        kfree(dev);
    }
    xa_destroy(&dev_xa);
}

구현 예제: 배치 순회와 xas_for_each

대규모 XArray를 효율적으로 순회하면서 동시에 수정하는 패턴입니다. xas_for_each를 사용하면 커서가 트리 위치를 기억하므로, 순회 중 수정이 가능하고 RCU grace period 양보도 자연스럽게 처리됩니다.

/* 구현 예제 1: 마크 기반 배치 처리 — dirty 페이지 writeback */
static long writeback_dirty_folios(
    struct address_space *mapping,
    struct writeback_control *wbc)
{
    XA_STATE(xas, &mapping->i_pages, wbc->range_start);
    struct folio *folio;
    long nr_written = 0;

    rcu_read_lock();
    /* PAGECACHE_TAG_DIRTY(XA_MARK_0)가 설정된 엔트리만 순회
     * 마크 전파 덕분에 dirty가 아닌 서브트리는 O(1)에 건너뜀 */
    xas_for_each_marked(&xas, folio, wbc->range_end,
                        PAGECACHE_TAG_DIRTY) {
        /* retry 엔트리 처리 (동시 수정 감지) */
        if (xas_retry(&xas, folio))
            continue;

        /* 값 엔트리(swap)는 건너뜀 */
        if (xa_is_value(folio))
            continue;

        /* folio 참조 획득 */
        if (!folio_try_get(folio))
            continue;

        /* RCU 양보: 긴 순회에서 grace period 허용 */
        if (++nr_written % 16 == 0) {
            xas_pause(&xas);
            rcu_read_unlock();
            cond_resched();
            rcu_read_lock();
        }

        /* folio를 디스크에 기록 */
        rcu_read_unlock();
        folio_lock(folio);
        write_folio_to_disk(folio);

        /* writeback 마크 설정, dirty 마크 해제 */
        xa_lock_irq(&mapping->i_pages);
        __xa_set_mark(&mapping->i_pages,
                      folio_index(folio), PAGECACHE_TAG_WRITEBACK);
        __xa_clear_mark(&mapping->i_pages,
                        folio_index(folio), PAGECACHE_TAG_DIRTY);
        xa_unlock_irq(&mapping->i_pages);

        folio_unlock(folio);
        folio_put(folio);
        rcu_read_lock();

        if (--wbc->nr_to_write <= 0)
            break;
    }
    rcu_read_unlock();

    return nr_written;
}

/* 구현 예제 2: xa_lock 보유 상태에서 배치 수정 */
static void batch_update_entries(
    struct xarray *xa,
    unsigned long start, unsigned long end,
    void *(*transform)(void *old))
{
    XA_STATE(xas, xa, start);
    void *entry;

    /* xa_lock을 한 번만 잡고 범위 내 모든 엔트리를 수정 */
    xa_lock(xa);
    xas_for_each(&xas, entry, end) {
        void *new_entry = transform(entry);
        if (new_entry != entry) {
            xas_store(&xas, new_entry);
            if (xas_error(&xas))
                break;
        }
    }
    xa_unlock(xa);

    /* 메모리 부족 시 재시도 */
    if (xas_nomem(&xas, GFP_KERNEL)) {
        /* xas_nomem이 true를 반환하면 메모리를 확보했으므로
         * 실패한 위치부터 다시 시도 */
        xa_lock(xa);
        xas_store(&xas, transform(xas_load(&xas)));
        xa_unlock(xa);
    }
}

페이지 캐시 일괄 삭제(Truncate) 패턴

/* 구현 예제 3: truncate — 범위 내 모든 folio를 페이지 캐시에서 제거 */
static void truncate_inode_pages_range(
    struct address_space *mapping,
    loff_t lstart, loff_t lend)
{
    pgoff_t start = lstart >> PAGE_SHIFT;
    pgoff_t end = (lend >> PAGE_SHIFT) + 1;
    struct folio *folio;
    XA_STATE(xas, &mapping->i_pages, start);

    /* 1단계: 범위 내 folio를 lock-free로 검색하여 잠금 */
    rcu_read_lock();
    xas_for_each(&xas, folio, end - 1) {
        if (xas_retry(&xas, folio))
            continue;
        if (xa_is_value(folio))
            continue;  /* swap 엔트리는 별도 처리 */

        if (!folio_try_get(folio))
            continue;

        rcu_read_unlock();
        folio_lock(folio);

        /* 2단계: xa_lock 보유 상태에서 페이지 캐시에서 제거 */
        xa_lock_irq(&mapping->i_pages);
        __xa_erase(&mapping->i_pages, folio_index(folio));
        mapping->nrpages -= folio_nr_pages(folio);
        xa_unlock_irq(&mapping->i_pages);

        folio_unlock(folio);
        folio_put(folio);  /* 페이지 캐시 참조 해제 */
        folio_put(folio);  /* get 참조 해제 */

        rcu_read_lock();
    }
    rcu_read_unlock();
}

Linux 6.12 ~ 6.19 XArray 동향

XArray는 folio/page cache의 핵심 인덱스 자료구조로서 대형 folio 분할의 lock 보유 시간 단축(xas_try_split()), IRQ-safe variant 규약 명세화, multi-index entry 버그 수정, Rust 바인딩 도입 등이 2024~2026년에 꾸준히 진행되며 Radix Tree 대체 역할을 완전히 마무리했습니다.

커널 7.0은 2026년 4월 12일에 공개되었습니다. XArray API는 7.0에서도 같은 인터페이스를 유지합니다.

관련 문서

XArray와 관련된 다른 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

• Linked List — 다른 자료구조와 비교
• Hash Table — 해시 테이블(Hash Table)과 비교
• Page Cache — XArray를 사용하는 페이지 캐시
• RCU — RCU 보호 XArray

참고자료

• include/linux/xarray.h — XArray 헤더 파일로, 공개 API와 매크로 정의를 포함합니다 (Bootlin Elixir 크로스 레퍼런스)
• lib/xarray.c — XArray 핵심 구현 소스 코드입니다 (Bootlin Elixir 크로스 레퍼런스)
• lib/test_xarray.c — XArray 단위 테스트 코드로, 다양한 API 사용 예시를 확인할 수 있습니다
• XArray — The Linux Kernel documentation — 커널 공식 문서의 XArray API 가이드입니다
• The XArray data structure (LWN.net) — Matthew Wilcox가 XArray의 설계 동기와 기본 API를 소개하는 LWN 기사입니다
• The XArray API (LWN.net) — XArray API의 세부 사항과 radix tree 대체 계획을 다루는 후속 기사입니다
• An updated XArray API (LWN.net) — XArray API 업데이트 사항과 커뮤니티 피드백을 정리한 기사입니다
• The XArray lands in 4.20 (LWN.net) — XArray가 Linux 4.20에 병합된 과정과 향후 마이그레이션 계획을 다룹니다
• XArray: One Data Structure to Rule Them All — Matthew Wilcox (Linux Plumbers Conference 2018) — XArray의 설계 철학과 성능 비교를 발표한 컨퍼런스 영상입니다
• XArray — Oracle Linux Blog — XArray의 내부 구조와 radix tree와의 차이점을 설명하는 블로그 글입니다