파일의 앞부분과 아주 먼 offset만 읽었다면, 사이의 모든 page를 담을 배열까지 할당해야 할까요? 반대로 folio 하나가 여러 page를 묶는다면 그 pointer를 page 수만큼 별도로 관리해야 할까요? page cache의 address_space.i_pages가 사용하는 XArray는 이 두 문제를 함께 다루는 자료구조입니다.
XArray는 word-sized index를 pointer나 정수 value에 대응시킵니다. 인접 index를 효율적으로 순회하면서도 sparse index 때문에 거대한 연속 배열을 만들지 않고, multi-index entry와 mark를 이용해 한 객체의 범위와 탐색 목적을 함께 표현합니다. 아래의 구체적인 encoding과 macro 계산은 upstream Linux v6.18을 기준으로 설명합니다.
연속 배열처럼 보이지만 확장은 node를 연결합니다
동적 배열은 용량을 늘릴 때 기존 원소를 새 memory로 옮기는 비용이 있습니다. hash table은 임의 key의 검색에는 유용하지만 file offset 순서로 다음 entry를 찾는 일과는 목적이 다릅니다. linked list는 드문 원소만 보관할 수 있어도 index 검색과 인접 데이터의 cache locality가 불리합니다. XArray는 radix tree 계열의 구조로 이 요구를 절충합니다.
struct xarray 자체는 비교적 작습니다. xa_lock은 수정 시 필요한 spinlock이고, xa_flags와 xa_head는 내부 상태입니다. 일반 사용자가 field를 직접 해석해 API를 대신하기보다 xa_init()나 정적 초기화 macro를 사용해야 합니다. 빈 tree의 head는 NULL입니다. index 0의 entry 하나만 있는 작은 경우에는 node 없이 head가 그 entry를 직접 담을 수도 있습니다.
다음은 v6.18의 struct xarray와 XARRAY_INIT() 전체입니다. 이 글의 kernel 발췌는 각 파일에 source와 notice를 보존하고, license 및 upstream notice를 함께 제공합니다. 필요한 kernel type·macro·build 문맥에 의존하며, 발췌 파일끼리 합치면 독립 program이 된다는 뜻은 아닙니다. 책의 정확한 source commit을 확인한 복원본이나 compile·runtime 검증 결과도 아닙니다.
/* SPDX-License-Identifier: GPL-2.0+ */
/*
* eXtensible Arrays
* Copyright (c) 2017 Microsoft Corporation
* Author: Matthew Wilcox <willy@infradead.org>
*
* See Documentation/core-api/xarray.rst for how to use the XArray.
*/
/*
* Exact named definitions / explicit macro groups from Linux v6.18 include/linux/xarray.h.
* Source: https://github.com/torvalds/linux/blob/v6.18/include/linux/xarray.h
* Upstream lines: 300-311
* See LICENSES and UPSTREAM-NOTICES.md; kernel excerpt, not a translation unit.
* This tag is not asserted to be the book's exact revision.
*/
struct xarray {
spinlock_t xa_lock;
/* private: The rest of the data structure is not to be used directly. */
gfp_t xa_flags;
void __rcu * xa_head;
};
#define XARRAY_INIT(name, flags) { \
.xa_lock = __SPIN_LOCK_UNLOCKED(name.xa_lock), \
.xa_flags = flags, \
.xa_head = NULL, \
}
큰 index가 필요해지면 상위 node를 추가하고 기존 subtree를 그 아래로 연결합니다. 기존 entry를 모두 새 배열로 복사하는 과정이 아닙니다. 통상 XA_CHUNK_SHIFT가 6이면 node에 1 << 6, 즉 64개 slot이 있습니다. x86-64에서 pointer array만 세면 512 byte이지만 node 전체 크기가 512 byte라는 뜻은 아닙니다. 설정에 따라 chunk shift가 달라질 수 있으므로 이 숫자를 ABI로 다루어서도 안 됩니다.
leaf의 shift가 0이면 slot 하나가 index 하나를 나타냅니다. 상위 node의 shift가 6이면 slot 하나가 64개 index 범위를 나타내고, shift가 12이면 slot 하나가 4096개 index 범위를 나타냅니다. 높이가 한 단계 커질 때 해석할 index bit 묶음이 하나 늘어나는 구조입니다. shift를 64씩 더하는 계산이 아닙니다.
새 index 때문에 root가 커지더라도 사이의 모든 index에 객체나 leaf node를 할당하지는 않습니다. 아직 없는 entry는 검색에서 비어 있다고 해석됩니다. 높은 index의 삽입이 어떤 경로의 allocation을 요구하는지와, 그 아래 모든 index가 실제로 채워져 있는지는 다른 문제입니다.
확장의 경계는 구체적으로 계산할 수 있습니다. chunk shift 6인 tree에서 index 0의 단일 entry에 index 1을 더하면 shift 0 node가 필요합니다. index 0부터 63까지 담은 상태에서 64를 넣을 때에는 shift 6 root가 기존 leaf를 slot 0에 보존하고 새 leaf를 slot 1에 연결합니다. 0부터 4095까지 담은 tree에 4096을 넣으면 root shift는 12가 됩니다. 이전 shift 6 subtree는 그대로 slot 0에 남고, slot 1 아래에 shift 6 node와 shift 0 leaf를 준비합니다. 새 root와 새 branch의 node를 따로 세어야 하며, 모든 원소를 복사하거나 기존 용량이 단순히 두 배가 된다고 해석하면 안 됩니다. 확장과 allocation
fanout을 크게 하면 같은 index를 표현하는 깊이는 줄지만 node 하나의 memory 사용량은 늘어납니다. XA_CHUNK_SHIFT는 CONFIG_BASE_SMALL에 따라 4 또는 6이 될 수 있고 XA_MARK_LONGS는 한 chunk의 mark bitmap에 필요한 word 수를 올림해 계산합니다. node의 실제 크기와 한 allocator page에 들어가는 개수는 pointer 크기·설정·부가 field에 따라 달라집니다. slot array의 512 byte만으로 allocator 소비량을 판단할 수 없는 이유입니다.
XA_CHUNK_MASK는 XA_CHUNK_SIZE - 1이며 한 level에서 사용할 slot bit를 고릅니다. 전체 index의 높은 bit가 다음 level을 선택하는 것과, 이 mask로 현재 node의 slot을 고르는 일을 나누어 읽어야 합니다.
root의 범위와 원소 수는 다릅니다
여기서는 자료의 설명 오류를 하나 구별해야 합니다. The Linux Memory Manager의 Figure 9-4 caption은 XA_CHUNK_SIZE^2 + 1개 원소를 가진 array에 다시 하나를 더한다고 적혀 있습니다. 그러나 그림의 확장 전 상태는 가득 찬 64개 leaf, 즉 4096개 entry이며 확장 후 상태는 새 branch에 entry 하나가 추가된 4097개입니다. 이 caption과 그림의 원소 수가 맞지 않는 것은 저자의 설명 오류입니다. 어떤 쪽을 쓰려던 것인지까지 추정하지는 않겠습니다. 확인 가능한 것은 그림의 전후 상태와 위에서 계산한 index 경계입니다.
이 원리를 원소 두 개만 있는 다른 사례로 확인할 수 있습니다. chunk shift 6으로 index 17을 보관한 tree에 index 4096을 추가한다고 가정하겠습니다. 필요한 root shift는 12이지만 실제 원소 수는 2입니다. shift 6 root가 표현하는 최대 index는 4095라서 새 index를 담을 수 없기 때문입니다. 높은 root가 있다는 사실을 그 아래의 모든 slot이 차 있다는 뜻으로 읽어서는 안 됩니다.
shift가 s인 node에서 slot 하나가 대표하는 index 수는 2^s입니다. slot을 고르는 식은 (index >> s) & XA_CHUNK_MASK입니다. root shift 12의 slot 1은 [4096, 8192)를 담당하고, index 4096은 그 아래 shift 6 node의 slot 0과 shift 0 leaf의 slot 0으로 내려갑니다. root 전체는 64개 slot이므로 [0, 262144)를 표현할 수 있습니다. 이 capacity와 현재 entry 두 개라는 수량은 전혀 다른 값입니다. index 범위와 확장 구현
xas_expand()는 요청한 최대 index를 담을 수 있을 때까지 head 위에 node를 추가합니다. 이전 head를 새 node의 slot 0에 연결하고 기존 subtree의 parent를 갱신하며, mark 집계도 새 상위 level에 전달합니다. node allocation이 실패하면 -ENOMEM입니다. 빈 tree에서는 곧바로 모든 node를 만드는 대신 필요한 높이를 계산해 반환하는 분기도 있습니다. 반환되는 shift는 후속 descent가 사용할 높이이므로 새 root의 node->shift와 무조건 같은 값이라고 해석하면 안 됩니다. advanced 수정 경로의 xa_lock 보호와 allocation 재시도 계약도 그대로 적용됩니다.
아래는 같은 v6.18 source의 xas_expand() 전체 정의입니다. GPL-2.0+와 attribution을 보존했으며 kernel 내부 helper에 의존하는 발췌입니다. 독립 실행 program이나 책 코드의 복원은 아닙니다.
// SPDX-License-Identifier: GPL-2.0+
/*
* Complete xas_expand from Linux v6.18 lib/xarray.c.
* Copyright (c) 2017-2018 Microsoft Corporation
* Copyright (c) 2018-2020 Oracle
* Author: Matthew Wilcox <willy@infradead.org>
*/
static int xas_expand(struct xa_state *xas, void *head)
{
struct xarray *xa = xas->xa;
struct xa_node *node = NULL;
unsigned int shift = 0;
unsigned long max = xas_max(xas);
if (!head) {
if (max == 0)
return 0;
while ((max >> shift) >= XA_CHUNK_SIZE)
shift += XA_CHUNK_SHIFT;
return shift + XA_CHUNK_SHIFT;
} else if (xa_is_node(head)) {
node = xa_to_node(head);
shift = node->shift + XA_CHUNK_SHIFT;
}
xas->xa_node = NULL;
while (max > max_index(head)) {
xa_mark_t mark = 0;
XA_NODE_BUG_ON(node, shift > BITS_PER_LONG);
node = xas_alloc(xas, shift);
if (!node)
return -ENOMEM;
node->count = 1;
if (xa_is_value(head))
node->nr_values = 1;
RCU_INIT_POINTER(node->slots[0], head);
/* Propagate the aggregated mark info to the new child */
for (;;) {
if (xa_track_free(xa) && mark == XA_FREE_MARK) {
node_mark_all(node, XA_FREE_MARK);
if (!xa_marked(xa, XA_FREE_MARK)) {
node_clear_mark(node, 0, XA_FREE_MARK);
xa_mark_set(xa, XA_FREE_MARK);
}
} else if (xa_marked(xa, mark)) {
node_set_mark(node, 0, mark);
}
if (mark == XA_MARK_MAX)
break;
mark_inc(mark);
}
/*
* Now that the new node is fully initialised, we can add
* it to the tree
*/
if (xa_is_node(head)) {
xa_to_node(head)->offset = 0;
rcu_assign_pointer(xa_to_node(head)->parent, node);
}
head = xa_mk_node(node);
rcu_assign_pointer(xa->xa_head, head);
xas_update(xas, node);
shift += XA_CHUNK_SHIFT;
}
xas->xa_node = node;
return shift;
}
low bit는 pointer와 value를 구별합니다
XArray slot의 형식이 void *라고 해서 내용이 전부 dereference 가능한 pointer인 것은 아닙니다. 일반 pointer는 최소 4-byte alignment를 요구합니다. 보장된 low bit를 entry 종류에 사용할 수 있기 때문입니다. 임의 user pointer나 함수 pointer를 그대로 넣어도 된다는 뜻은 아닙니다.
정수는 0부터 LONG_MAX까지를 value entry로 표현할 수 있습니다. xa_mk_value()가 정수를 entry로 만들고, xa_is_value()가 형식을 확인하며, xa_to_value()가 정수를 복원합니다. 정수 0을 encode한 value는 빈 entry NULL과 다릅니다. 이 구별이 없으면 subsystem의 상태 값 0과 자료구조 안에 값이 없다는 상태를 구분할 수 없습니다.
BITS_PER_XA_VALUE는 BITS_PER_LONG - 1입니다. low bit가 1이면 value 계열이고, 일반 pointer의 low two bits는 00, internal entry는 10입니다. 그래서 value 생성은 한 bit 왼쪽 shift 뒤 1을 OR하고, 복원은 unsigned 값을 한 bit 오른쪽 shift합니다. xa_mk_value()의 음수 검사도 정수의 부호 있는 표현 범위를 벗어난 입력을 경고하기 위한 것입니다.
아래 파일에는 v6.18의 value·internal 변환 helper 여섯 개를 함수 단위로 전부 담았습니다. kernel header의 type과 macro를 사용하는 발췌이므로 standalone user program은 아닙니다. 원본 header의 GPL-2.0+와 attribution을 파일에 보존했습니다.
/* SPDX-License-Identifier: GPL-2.0+ */
/*
* Complete helper definitions from Linux v6.18 include/linux/xarray.h.
* Copyright (c) 2017 Microsoft Corporation
* Author: Matthew Wilcox <willy@infradead.org>
*/
static inline void *xa_mk_value(unsigned long v)
{
WARN_ON((long)v < 0);
return (void *)((v << 1) | 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;
}
static inline void *xa_mk_internal(unsigned long v)
{
return (void *)((v << 2) | 2);
}
static inline unsigned long xa_to_internal(const void *entry)
{
return (unsigned long)entry >> 2;
}
static inline bool xa_is_internal(const void *entry)
{
return ((unsigned long)entry & 3) == 2;
}
내부 구현에는 node pointer, sibling, retry와 reserved zero 같은 internal entry도 있습니다. xa_is_internal()과 변환 helper는 이 표현을 다루지만 normal API의 caller가 임의 internal entry를 만들어 저장하는 용도는 아닙니다. normal API가 내부 node를 사용자 객체처럼 돌려주도록 기대해서도 안 됩니다.
internal 값은 두 bit를 사용하므로 xa_mk_internal()은 두 bit 왼쪽 shift 뒤 2를 OR하고, xa_to_internal()은 unsigned 값을 두 bit 오른쪽으로 옮깁니다. sibling의 작은 값은 canonical entry가 있는 slot을 가리키며, 현재 사용되는 sibling 값은 0~62입니다. internal 값 256은 XA_RETRY_ENTRY, 257은 XA_ZERO_ENTRY입니다. 전자는 탐색을 다시 시작해야 하는 상태이고, 후자는 reserved slot을 normal API에서는 NULL로 보이게 하는 표현입니다. 이는 integer value 0과도 다릅니다. tagged pointer를 사용하려는 caller는 관련 전용 helper와 자신의 표현 계약을 따라야 하며 mark bitmap과 혼동해서는 안 됩니다.
에러도 pointer와 구분해야 합니다. XArray API의 encoded error는 xa_is_err()와 xa_err()로 판정합니다. kernel의 일반적인 ERR_PTR() 값을 마음대로 저장하는 것과는 다른 계약입니다. 일부 값은 value/internal encoding과 충돌하므로 XArray는 임의 IS_ERR() pointer를 저장 대상으로 지원하지 않습니다. 작은 음수 error code를 pointer에 싣는 관습만 보고 두 표현을 섞으면 안 됩니다. entry encoding과 API 정의
xa_err()가 xa_to_internal()을 그대로 쓰지 않는 이유는 sign extension입니다. error인 경우에는 long으로 해석한 값을 두 bit 오른쪽 shift해 음수 errno를 되찾고, error가 아니면 0을 반환합니다. 반대로 node는 internal 표시가 있으면서 값이 4096보다 큰 pointer를 xa_is_node()로 구별합니다. xa_mk_node()는 정렬된 node pointer에 2를 OR하고 xa_to_node()는 그 2를 제거합니다. 둘 다 임의 user pointer를 안전한 kernel node로 검증해 주는 함수는 아닙니다.
다음 파일에는 같은 v6.18 header의 error·node helper 다섯 개 전체가 있습니다. 각각의 입력 종류를 먼저 확인하고 적절한 복원 함수를 선택해야 합니다.
/* SPDX-License-Identifier: GPL-2.0+ */
/*
* Complete helper definitions from Linux v6.18 include/linux/xarray.h.
* Copyright (c) 2017 Microsoft Corporation
* Author: Matthew Wilcox <willy@infradead.org>
*/
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)
{
/* xa_to_internal() would not do sign extension. */
if (xa_is_err(entry))
return (long)entry >> 2;
return 0;
}
static inline void *xa_mk_node(const struct xa_node *node)
{
return (void *)((unsigned long)node | 2);
}
static inline struct xa_node *xa_to_node(const void *entry)
{
return (struct xa_node *)((unsigned long)entry - 2);
}
static inline bool xa_is_node(const void *entry)
{
return xa_is_internal(entry) && (unsigned long)entry > 4096;
}
node는 자식뿐 아니라 탐색 상태를 요약합니다
아래에는 chunk 크기를 정하는 #ifndef XA_CHUNK_SHIFT 분기와 mark 계산, struct xa_node 전체를 함께 남겼습니다. 이미 정의한 chunk shift를 존중하는 조건을 지우면 설정 가능 범위를 잘못 읽게 됩니다.
/* SPDX-License-Identifier: GPL-2.0+ */
/*
* eXtensible Arrays
* Copyright (c) 2017 Microsoft Corporation
* Author: Matthew Wilcox <willy@infradead.org>
*
* See Documentation/core-api/xarray.rst for how to use the XArray.
*/
/*
* Exact named definitions / explicit macro groups from Linux v6.18 include/linux/xarray.h.
* Source: https://github.com/torvalds/linux/blob/v6.18/include/linux/xarray.h
* Upstream lines: 1153-1159, 1168-1184
* See LICENSES and UPSTREAM-NOTICES.md; kernel excerpt, not a translation unit.
* This tag is not asserted to be the book's exact revision.
*/
#ifndef XA_CHUNK_SHIFT
#define XA_CHUNK_SHIFT (IS_ENABLED(CONFIG_BASE_SMALL) ? 4 : 6)
#endif
#define XA_CHUNK_SIZE (1UL << XA_CHUNK_SHIFT)
#define XA_CHUNK_MASK (XA_CHUNK_SIZE - 1)
#define XA_MAX_MARKS 3
#define XA_MARK_LONGS BITS_TO_LONGS(XA_CHUNK_SIZE)
struct xa_node {
unsigned char shift; /* Bits remaining in each slot */
unsigned char offset; /* Slot offset in parent */
unsigned char count; /* Total entry count */
unsigned char nr_values; /* Value entry count */
struct xa_node __rcu *parent; /* NULL at top of tree */
struct xarray *array; /* The array we belong to */
union {
struct list_head private_list; /* For tree user */
struct rcu_head rcu_head; /* Used when freeing node */
};
void __rcu *slots[XA_CHUNK_SIZE];
union {
unsigned long tags[XA_MAX_MARKS][XA_MARK_LONGS];
unsigned long marks[XA_MAX_MARKS][XA_MARK_LONGS];
};
};
struct xa_node의 shift는 slot이 담당하는 index 범위를, offset은 부모 node 안에서 자신의 위치를 나타냅니다. parent가 NULL이면 최상위 node이고 array는 소속 XArray를 가리킵니다. 이 정보 덕분에 순회가 leaf에만 머무르지 않고 상위로 돌아가 다음 subtree를 찾을 수 있습니다.
count는 non-NULL slot 수를 추적합니다. 이 수에 child node나 sibling 같은 내부 entry도 들어갈 수 있으므로 사용자 객체 수라고 읽어서는 안 됩니다. nr_values 역시 정수 value와 그 sibling 표현을 고려하는 내부 집계입니다. page cache의 folio 수나 mapping->nrpages와 서로 바꾸어 사용할 수 없습니다.
slots는 실제 entry array입니다. private_list와 rcu_head는 같은 저장 공간을 다른 수명 단계에 쓰는 union입니다. subtree에서 node를 떼어 냈다고 reader가 즉시 옛 node를 더 이상 보지 않는 것은 아니므로, RCU를 통한 회수 단계까지 고려해야 합니다.
mark bitmaps도 node마다 존재합니다. header에 tags와 marks가 union으로 보인다는 이유로, XArray mark와 page-cache tag를 서로 독립적이며 전파 방식이 다른 두 분류라고 생각하면 안 됩니다. 현재 XArray는 최대 세 mark를 지원하고 mark를 상위 node로 전파해 해당 종류가 없는 subtree를 건너뛸 수 있게 합니다. page cache의 DIRTY, WRITEBACK, TOWRITE tag는 이 기능을 사용합니다.
이 mark는 entry pointer의 low-bit tagging과도 다릅니다. 하나는 tree 검색을 돕는 bitmap이고 다른 하나는 entry 값의 형식을 구분하는 encoding입니다. folio의 dirty bit와도 항상 같은 순간에 바뀌는 단순 복사본은 아닙니다.
큰 entry는 sibling과 정렬로 표현합니다
한 folio가 여러 base page를 묶는다면 page index 어느 지점에서 찾아도 같은 folio를 얻어야 합니다. XArray는 하나의 multi-index entry로 이 범위를 나타낼 수 있습니다. order는 pointer 수가 아니라 2^order개 index를 대표한다는 뜻입니다.
예를 들어 shift 6 node에서 slot 여덟 개가 담당하는 범위는 64 * 8 = 512개 index입니다. canonical entry 하나와 sibling 일곱 개로 그 범위를 나타내더라도 folio pointer 여덟 개를 독립적으로 소유하는 것은 아닙니다. sibling은 같은 entry로 돌아갈 정보를 담습니다. lookup과 다음 index로 전진하는 순회가 이 범위를 알아야 중복 반환과 잘못된 참조 계산을 피할 수 있습니다.
단일 index를 수정하는 것처럼 보여도 multi-index entry 전체에 영향을 줄 수 있습니다. 범위 일부를 다른 entry로 대체해야 한다면 split과 저장 규칙을 따라야 합니다. page cache에서 large folio를 만났을 때 반환 slot 개수에 PAGE_SIZE를 곱해 byte 범위를 계산할 수 없는 이유도 같습니다.
XA_STATE_ORDER()는 세 계산을 한꺼번에 준비합니다. 먼저 index의 아래 order bit를 지워 범위 시작으로 정렬합니다. 그다음 order - order % XA_CHUNK_SHIFT로 저장할 shift를 고르고, (1U << (order % XA_CHUNK_SHIFT)) - 1로 canonical entry 뒤에 필요한 sibling 수를 구합니다. 이 sibling 수는 byte 수가 아닙니다. macro는 상태를 만들 뿐 folio나 XArray node를 즉시 할당하지는 않습니다.
예를 들어 chunk shift 6, index 600, order 9라면 범위 시작은 512, 저장 shift는 6, sibling 수는 7입니다. canonical slot 하나와 일곱 sibling이 각각 64 index를 대표해 [512, 1024)의 512 index를 표현합니다. 입력 index 600이 그 범위 안에 있다는 사실과 범위의 canonical 시작이 600이라는 주장은 다릅니다.
normal API도 실패와 수명을 대신 처리하지는 않습니다
xa_load(), xa_store(), xa_erase(), xa_find() 같은 normal API는 흔한 작업을 간단히 수행하도록 합니다. store와 erase가 내부에서 필요한 XArray lock을 처리하더라도 caller가 여러 번 호출한 전체 구간이 하나의 transaction이 되는 것은 아닙니다.
xa_store()는 이전 entry 또는 encoded error를 반환합니다. node allocation이 필요하면 GFP 조건에 맞게 memory를 얻어야 하고 실패할 수 있습니다. 새 entry를 저장했다는 사실이 그것이 가리키는 객체의 참조를 자동으로 얻었다는 뜻도 아닙니다. tree의 동기화와 객체 소유권은 별도의 계약입니다.
기존 multi-index entry 내부의 index에 일반 store를 하면 그 entry가 대표하는 범위 전체를 바꿀 수 있습니다. 일반 mark도 새 pointer를 대입했다고 무조건 초기화되는 것이 아니며, NULL로 삭제하는 경우의 정리와 구별해야 합니다. 한 index의 값만 바꿨다고 가정한 caller가 나머지 범위와 mark를 계속 옛 객체의 것으로 해석하면 오류가 생깁니다.
__xa_store()처럼 lock을 이미 보유한 caller를 위한 계열도 있습니다. 함수 이름의 밑줄만 보고 빠른 동의어로 선택하면 안 됩니다. API의 lock 요구와 allocation 허용 조건을 맞춰야 합니다. 원래 entry를 확인한 뒤 바꾸어야 하는 작업에는 그 경쟁을 처리하는 API 또는 적절한 critical section이 필요합니다.
v6.18 __xa_store()는 xa_is_advanced()에 해당하는 입력을 받으면 XA_ERROR(-EINVAL)로 거절합니다. xas_store() 뒤 allocation 재시도에 실패하면 최종 오류가 반환되므로 NULL과 -ENOMEM을 같은 결과로 취급해서도 안 됩니다. xa_store()는 그 바깥에서 lock을 얻고 놓는 wrapper입니다. GFP가 허용하면 내부 memory 준비 중 lock을 놓았다 다시 얻을 수 있으므로 caller의 다른 상태까지 그 사이 고정되는 것은 아닙니다.
free tracking을 켠 array에서는 NULL 저장도 reserved zero entry로 바꾸고, 저장한 slot의 XA_FREE_MARK를 내립니다. 반환할 때에는 내부 zero 표현을 다시 NULL로 바꿉니다. 이 경로를 생략한 예시만 보면 reserved slot과 비어 있는 slot의 구별을 놓치기 쉽습니다. 아래에는 lib/xarray.c의 두 함수 전체를 각각 보존했습니다.
// SPDX-License-Identifier: GPL-2.0+
/*
* Complete function definitions from Linux v6.18 lib/xarray.c.
* Copyright (c) 2017-2018 Microsoft Corporation
* Copyright (c) 2018-2020 Oracle
* Author: Matthew Wilcox <willy@infradead.org>
*/
void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
{
XA_STATE(xas, xa, index);
void *curr;
if (WARN_ON_ONCE(xa_is_advanced(entry)))
return XA_ERROR(-EINVAL);
if (xa_track_free(xa) && !entry)
entry = XA_ZERO_ENTRY;
do {
curr = xas_store(&xas, entry);
if (xa_track_free(xa))
xas_clear_mark(&xas, XA_FREE_MARK);
} while (__xas_nomem(&xas, gfp));
return xas_result(&xas, xa_zero_to_null(curr));
}
void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
{
void *curr;
xa_lock(xa);
curr = __xa_store(xa, index, entry, gfp);
xa_unlock(xa);
return curr;
}
xa_state는 검색 위치와 재시도를 이어 갑니다
다음 파일은 callback typedef, struct xa_state, 세 sentinel과 초기화 macro의 전체 선언을 담습니다. 서로 떨어진 선언을 모은 발췌이며 그 사이의 다른 API를 전부 옮긴 header는 아닙니다. XA_STATE_ORDER()의 정렬·shift·sibling 계산과 __XA_STATE()의 초기 field를 실제 정의에서 함께 확인하실 수 있습니다.
/* SPDX-License-Identifier: GPL-2.0+ */
/*
* eXtensible Arrays
* Copyright (c) 2017 Microsoft Corporation
* Author: Matthew Wilcox <willy@infradead.org>
*
* See Documentation/core-api/xarray.rst for how to use the XArray.
*/
/*
* Exact named definitions / explicit macro groups from Linux v6.18 include/linux/xarray.h.
* Source: https://github.com/torvalds/linux/blob/v6.18/include/linux/xarray.h
* Upstream lines: 1333-1333, 1354-1365, 1371-1386, 1396-1397, 1410-1414
* See LICENSES and UPSTREAM-NOTICES.md; kernel excerpt, not a translation unit.
* This tag is not asserted to be the book's exact revision.
*/
typedef void (*xa_update_node_t)(struct xa_node *node);
struct xa_state {
struct xarray *xa;
unsigned long xa_index;
unsigned char xa_shift;
unsigned char xa_sibs;
unsigned char xa_offset;
unsigned char xa_pad; /* Helps gcc generate better code */
struct xa_node *xa_node;
struct xa_node *xa_alloc;
xa_update_node_t xa_update;
struct list_lru *xa_lru;
};
#define XA_ERROR(errno) ((struct xa_node *)(((unsigned long)errno << 2) | 2UL))
#define XAS_BOUNDS ((struct xa_node *)1UL)
#define XAS_RESTART ((struct xa_node *)3UL)
#define __XA_STATE(array, index, shift, sibs) { \
.xa = array, \
.xa_index = index, \
.xa_shift = shift, \
.xa_sibs = sibs, \
.xa_offset = 0, \
.xa_pad = 0, \
.xa_node = XAS_RESTART, \
.xa_alloc = NULL, \
.xa_update = NULL, \
.xa_lru = NULL, \
}
#define XA_STATE(name, array, index) \
struct xa_state name = __XA_STATE(array, index, 0, 0)
#define XA_STATE_ORDER(name, array, index, order) \
struct xa_state name = __XA_STATE(array, \
(index >> order) << order, \
order - (order % XA_CHUNK_SHIFT), \
(1U << (order % XA_CHUNK_SHIFT)) - 1)
advanced API는 struct xa_state를 통해 한 작업의 상태를 이어 갑니다. xa는 대상 array, xa_index는 관심 index, xa_shift와 xa_sibs는 multi-index 범위, xa_offset과 xa_node는 현재 tree 위치입니다. xa_alloc은 미리 준비한 allocation을 연결하고 xa_update는 node의 집계가 변할 때의 callback을 지원합니다. padding과 LRU 관련 field는 index 자체의 일부가 아닙니다.
XA_STATE()는 단일 index용 기본 상태를 만들고 __XA_STATE()는 그 초기 field를 구성합니다. 처음의 xa_node는 실제 node pointer가 아니라 XAS_RESTART일 수 있습니다. XAS_BOUNDS는 현재 tree에서 범위를 벗어났음을 나타내고 XA_ERROR()는 오류 상태를 encode합니다. 따라서 xa_node != NULL이라는 검사 하나로 유효한 node라고 판단할 수 없습니다.
기본 초기화에서 xa_offset과 padding은 0, 준비한 allocation과 callback 및 LRU pointer는 NULL입니다. xa_node == NULL 자체도 항상 오류는 아닙니다. index 0의 단일 entry가 head에 직접 저장된 경우에는 가리킬 node가 없기 때문입니다. xa_update는 node의 count 또는 nr_values가 변할 때 집계 상태를 함께 갱신할 수 있게 합니다. 이런 field는 상태를 이해하기 위한 것이며 caller가 accessor를 건너뛰고 임의로 덮어쓰라는 공개 interface는 아닙니다.
수정하는 advanced caller는 xa_lock 계열로 필요한 구간을 보호합니다. spinlock을 잡은 채 잠들 수 있는 allocation을 수행할 수는 없습니다. xas_nomem()를 사용하는 패턴은 필요한 memory를 lock 밖에서 준비하고 다시 들어와 작업을 재시도합니다. 그 사이 다른 writer가 tree를 바꿀 수 있으므로 이전 cursor나 존재 여부 판단을 그대로 믿어서는 안 됩니다.
RCU 검색과 folio 참조는 서로 보완합니다
RCU는 Read-Copy-Update입니다. 기존 reader가 critical section을 벗어날 때까지 옛 객체의 회수를 미루는 방식이지, writer가 reader 없는 시간에만 변경하거나 모든 reader가 무조건 memory ordering을 걱정하지 않아도 되는 규칙은 아닙니다.
XArray를 RCU로 따라갈 수 있다는 것과 반환한 folio를 이후에도 사용할 수 있다는 것은 다릅니다. page cache의 lockless lookup은 entry를 읽고 nonzero refcount를 확보한 뒤 xas_reload()로 여전히 같은 entry인지 확인합니다. 어긋나면 참조를 놓고 다시 찾습니다. folio lock을 얻고 나서도 mapping을 재확인해야 truncation이 소속을 끊은 경우를 걸러낼 수 있습니다.
이렇게 보면 XArray는 단순히 검색이 빠른 tree가 아닙니다. index의 범위, entry 형식, 목적별 mark, 잠금과 재시도 상태를 함께 제공하지만 실제 folio의 수명은 page cache 사용자가 완성해야 하는 자료구조입니다. 이 경계를 지켜야 내부 entry를 객체로 잘못 해석하거나 tree의 안전성을 파일 내용의 불변성으로 오해하지 않습니다.
참고 자료
- Lorenzo Stoakes, The Linux Memory Manager, Early Access 2025, Chapter 9, §9.2~9.2.2.
- Linux v6.18: XArray documentation, xarray.h, xarray.c, filemap.c.