XArray 자료구조

Linux 커널의 XArray는 radix tree를 대체하는 현대적 자료구조입니다. 단순한 API, 내장 잠금, 값 엔트리 지원, RCU 기반 lock-free 읽기를 제공하며, 페이지 캐시와 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(기수 트리)를 사용합니다. 각 노드는 64개의 슬롯을 가지며(6비트 청크), 인덱스의 비트를 상위부터 6비트씩 소비하여 트리를 탐색합니다.

struct xarray

/* 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는 다양한 순회 매크로를 제공합니다. 모든 순회는 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의 비트맵에 저장되며, 마크된 엔트리만 효율적으로 순회할 수 있습니다.

/* 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 페이지 인덱스를 차지합니다.

/* 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 할당, 마크, 순회, 에러 처리를 모두 포함합니다:

#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");