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

/* 실습 예제: 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개의 연속 인덱스에 매핑되는 기능입니다. 커널의 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: 인터럽트 컨텍스트 잠금

/* 인터럽트 핸들러에서도 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;

메모리 관리와 노드 할당

XArray의 내부 노드(xa_node)는 동적으로 할당/해제됩니다. 노드 할당 실패 시의 graceful 처리, RCU 기반 지연 해제, 그리고 메모리 오버헤드는 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 디버깅 실습

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);
}

관련 문서

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

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