Every cacheable, mappable kernel object — almost always a file inode, sometimes a block device — owns a struct address_space, and the heart of that structure is i_pages, an XArray that maps a page-aligned file offset (pgoff_t, in units of pages from the start of the file) to the in-memory folio caching that offset’s data. The XArray is “an abstract data type which behaves like a very large array of pointers” (kernel core-api docs) and is, in the documentation’s own words, the data structure whose “most important user … is the page cache.” It replaced the older radix tree in the 4.20 merge window (commits dated 2018-10-21, lib/xarray.c history). This note is the data-structure companion to The Page Cache: that note explains the cache as a subsystem; this one dissects the address_space container, the XArray indexing it, the per-entry DIRTY / WRITEBACK / TOWRITE marks, multi-index folio entries, and the lockless RCU lookup that makes a read() hit fast.
Mental Model — One Tree Per File, Indexed by Page Offset
Think of the page cache not as one global structure but as one XArray per file, hanging off that file’s inode. When you open() a file, the kernel finds (or creates) its struct inode; inside that inode lives i_data, a struct address_space, and inside that lives i_pages, the XArray. The XArray’s index is the page offset within the file — file byte offset divided by PAGE_SIZE (4096 on x86-64) — and the value stored at each index is a pointer to the struct folio holding that page’s contents. A miss (no folio at that index) means the data is not cached and must be read from the backing store; a hit returns the folio directly.
flowchart TB
inode["struct inode<br/>(one per open file)"]
as["struct address_space (i_data)<br/>host, a_ops, flags, nrpages…"]
xa["i_pages: struct xarray<br/>index = pgoff_t (file offset / PAGE_SIZE)"]
f0["folio @ index 0"]
f1["folio @ index 1<br/>(order-2: covers 4 indices)"]
shadow["value entry @ index 7<br/>(shadow / workingset)"]
inode --> as --> xa
xa -->|"slot 0"| f0
xa -->|"slots 4-7 (multi-index)"| f1
xa -->|"slot 12"| shadow
The page-cache indexing structure for a single file. What it shows: the inode points at one address_space, whose i_pages XArray maps page offsets to folios; a large folio (here order-2, four 4 KiB pages) occupies a contiguous power-of-two range of indices as a single multi-index entry, and an evicted page can leave behind a tiny “value” entry (a shadow) instead of a pointer. The insight to take: lookups, insertions, dirty-tracking, and reclaim all operate on this one XArray; everything the page cache does mechanically is an XArray operation under the i_pages lock or RCU.
struct address_space — The Per-Inode Cache Container
The definition, verbatim from the Linux 6.12 LTS tree (include/linux/fs.h, v6.12), with the kernel’s own kerneldoc comment:
/** * struct address_space - Contents of a cacheable, mappable object. * @host: Owner, either the inode or the block_device. * @i_pages: Cached pages. * @invalidate_lock: Guards coherency between page cache contents and * file offset->disk block mappings in the filesystem during invalidates. * @gfp_mask: Memory allocation flags to use for allocating pages. * @i_mmap_writable: Number of VM_SHARED, VM_MAYWRITE mappings. * @i_mmap: Tree of private and shared mappings. * @i_mmap_rwsem: Protects @i_mmap and @i_mmap_writable. * @nrpages: Number of page entries, protected by the i_pages lock. * @writeback_index: Writeback starts here. * @a_ops: Methods. * @flags: Error bits and flags (AS_*). * @wb_err: The most recent error which has occurred. */struct address_space { struct inode *host; struct xarray i_pages; struct rw_semaphore invalidate_lock; gfp_t gfp_mask; atomic_t i_mmap_writable; /* ... CONFIG_READ_ONLY_THP_FOR_FS: atomic_t nr_thps; ... */ struct rb_root_cached i_mmap; unsigned long nrpages; pgoff_t writeback_index; const struct address_space_operations *a_ops; unsigned long flags; errseq_t wb_err; spinlock_t i_private_lock; struct list_head i_private_list; struct rw_semaphore i_mmap_rwsem; void * i_private_data;} __attribute__((aligned(sizeof(long)))) __randomize_layout;
Walking the load-bearing fields:
host — back-pointer to the owning object, almost always the struct inode (for a block device’s buffer cache it is the block_device). This is how, given a cached folio, the kernel walks back to “which file?”
i_pages — the field this note is about: a struct xarray (the page cache proper). Indexed by pgoff_t. Its embedded spinlock is the famous i_pages lock (xa_lock(&mapping->i_pages)).
invalidate_lock — a read-write semaphore (added in 5.x) that serializes truncation/hole-punch against faults and reads, closing a long-standing race where a fault could re-populate a page that truncate was concurrently removing. It guards coherence between the cache and the file→disk-block mapping.
gfp_mask — the GFP flags used when allocating folios for this mapping (e.g. a filesystem on a highmem-only zone might restrict allocations here).
i_mmap — a separate rb_root_cached (a red-black tree, not the XArray) holding the VMAs that mmap() this file. This is the reverse map used to find every process mapping a given page (for try_to_unmap, dirty-tracking of mmapped writes, etc.). Note the deliberate split: cached content lives in the XArray; mappings of that content live in the rbtree.
nrpages — count of page entries currently in i_pages, protected by the i_pages lock. This is what feeds /proc/meminfo’s per-file contribution to Cached.
writeback_index — where the next WB_SYNC_NONE (background) writeback pass over this mapping should resume, so writeback round-robins across the file instead of always restarting at offset 0.
a_ops — pointer to the address_space_operations vtable (below): the filesystem’s hooks for reading, writing back, dirtying, and invalidating folios.
flags — the AS_* bits (error and policy flags); see below.
wb_err — an errseq_t cookie that records the most recent writeback error so a later fsync() can report a writeback failure that happened asynchronously, even across multiple file descriptors. __filemap_set_wb_err() writes it (mm/filemap.c, v6.12).
enum mapping_flags { AS_EIO = 0, /* IO error on async write */ AS_ENOSPC = 1, /* ENOSPC on async write */ AS_MM_ALL_LOCKS = 2, /* under mm_take_all_locks() */ AS_UNEVICTABLE = 3, /* e.g., ramdisk, SHM_LOCK */ AS_EXITING = 4, /* final truncate in progress */ AS_NO_WRITEBACK_TAGS = 5, AS_RELEASE_ALWAYS = 6, /* Call ->release_folio(), even if no private data */ AS_STABLE_WRITES = 7, /* must wait for writeback before modifying contents */ AS_INACCESSIBLE = 8, /* Do not attempt direct R/W access to the mapping */ /* Bits 16-25 are used for FOLIO_ORDER */ AS_FOLIO_ORDER_BITS = 5, AS_FOLIO_ORDER_MIN = 16, AS_FOLIO_ORDER_MAX = AS_FOLIO_ORDER_MIN + AS_FOLIO_ORDER_BITS,};
Two things worth flagging. First, AS_UNEVICTABLE marks a whole mapping as never-reclaimable (tmpfs under SHM_LOCK, ramdisks) — its folios go on the unevictable LRU. Second, the AS_FOLIO_ORDER bits (16–25) are a 6.x addition that lets a mapping declare a minimum and maximum folio order it will use — the mechanism behind per-filesystem large-folio support and block sizes larger than PAGE_SIZE. This is why __filemap_add_folio checks folio_order(folio) >= mapping_min_folio_order(mapping).
The address_space_operations vtable
a_ops points at the filesystem’s per-mapping methods. Abbreviated from v6.12 fs.h — these are the hooks the page cache calls to talk to the filesystem:
The naming is itself a fingerprint of the folio conversion: methods that used to take struct page * (readpage, set_page_dirty, invalidatepage) are now read_folio, dirty_folio, invalidate_folio and take struct folio *. The legacy writepage still takes a struct page * and is being phased out in favour of writepages. The page cache itself is filesystem-agnostic; all filesystem-specific behaviour funnels through this vtable.
The XArray — What It Is and Why It Replaced the Radix Tree
The XArray (the “x” is the historical “eXpandable/radix” lineage) is, per the core-api documentation, an abstract array of pointers indexed by an unsigned long. It is “efficient when the indices used are densely clustered” — exactly the access pattern of a file read, which touches consecutive page offsets — and it “takes advantage of RCU to perform lookups without locking.” Internally it is still a radix tree (a wide-fanout trie: each node has 64 slots on 64-bit, so 6 index bits per level), but the interface was redesigned.
The history matters and is dated to a primary source. Matthew Wilcox proposed the XArray at linux.conf.au 2018 (LWN, Jan 2018). His complaint was that the radix-tree API was bad: it required callers to do their own locking, exposed a fragile “preload” mechanism for pre-allocating memory before taking locks, and used confusing “exception entry” terminology. The XArray keeps the radix-tree data structure largely unchanged but reframes it as an array, handles its own locking (an internal spinlock plus RCU), and removes preload. The page cache — the single biggest radix-tree user — was the motivating conversion. While the LWN piece records Wilcox planning inclusion for the 4.16 merge window, the actual landing slipped. The series of “page cache: Convert … to XArray” commits (mm/filemap.c git log) are dated 2018-10-21, and Linus Torvalds’ “Merge branch ‘xarray’” commit is dated 2018-10-28 — squarely in the 4.20 merge window (4.20-rc1 followed in early November 2018). lib/xarray.c itself was introduced in the same window. Linux 4.20 shipped in December 2018. So: radix tree until 4.19; XArray from 4.20 onward, which includes both 6.12 and 6.18 LTS.
Value entries vs pointer entries — and shadow entries
A subtlety the page cache leans on: the XArray distinguishes pointer entries (a real struct folio *, which must be at least 4-byte aligned — true for anything from kmalloc/alloc_page) from value entries (a small integer 0…LONG_MAX packed into the slot, created with xa_mk_value() and tested with xa_is_value()). The page cache uses value entries for two things (filemap_get_entry comment, v6.12):
Shadow / workingset entries. When a clean file folio is evicted by reclaim, the cache can leave a tiny value entry in its slot recording eviction recency (a “shadow”). On a later miss, the workingset code reads this shadow to decide whether the page was recently evicted (refault → it deserves protection) or long ago (genuine cold miss). This is how Linux distinguishes thrashing from a cold working set without keeping the folio around.
Swap entries for shmem/tmpfs. A tmpfs file’s “page cache” can hold a swap entry value when the page has been swapped out.
Because both share the slot, a lookup must always test xa_is_value() before treating a returned entry as a folio pointer.
Adding a folio to the cache is the canonical use of the XArray advanced API — the xas_* cursor functions that require the caller to hold xa_lock. From mm/filemap.c, v6.12 (abridged):
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); /* declare cursor at index */ ... xas_set_order(&xas, index, folio_order(folio)); /* multi-index: span 2^order slots */ folio->mapping = mapping; folio->index = xas.xa_index; for (;;) { xas_lock_irq(&xas); /* take i_pages lock, disable IRQs */ xas_for_each_conflict(&xas, entry) { /* anything already in this range? */ old = entry; if (!xa_is_value(entry)) { /* a real folio is in the way */ xas_set_err(&xas, -EEXIST); goto unlock; } ... /* a value entry = old shadow; capture it */ } ... xas_store(&xas, folio); /* THE store */ if (xas_error(&xas)) goto unlock; mapping->nrpages += nr; /* account, under the lock */ __lruvec_stat_mod_folio(folio, NR_FILE_PAGES, nr);unlock: xas_unlock_irq(&xas); if (!xas_nomem(&xas, gfp)) /* retry once if store needed memory */ break; } ...}
Reading this line by line teaches the whole pattern. XA_STATE(xas, &mapping->i_pages, index) declares an on-stack cursor (struct xa_state) positioned at index — the macro the core-api docs call “an opaque data structure which you declare on the stack.” xas_set_order widens the cursor to cover a power-of-two range of slots when inserting a large folio (multi-index, below). xas_lock_irq takes the embedded i_pages spinlock with interrupts disabled — necessary because writeback completion runs in softirq/IRQ context and also touches i_pages. xas_for_each_conflict walks every entry overlapping the target range to detect an -EEXIST collision (a real folio already there) versus a reclaimable value entry (an old shadow, which is captured into *shadowp). xas_store performs the actual insertion. Crucially, mapping->nrpages is bumped inside the lock, keeping the counter exactly consistent with the tree. Finally, xas_nomem(&xas, gfp) implements the lockless-allocation retry the docs describe: the store attempts allocation while holding the lock (likely to fail under pressure), and on ENOMEM the code drops the lock, lets xas_nomem allocate more aggressively, and retries — replacing the old radix-tree “preload” dance.
Lookup: filemap_get_entry (RCU, lockless)
The fast path — what a cache-hitting read() runs — takes no lock at all:
void *filemap_get_entry(struct address_space *mapping, pgoff_t index){ XA_STATE(xas, &mapping->i_pages, index); struct folio *folio; rcu_read_lock();repeat: xas_reset(&xas); folio = xas_load(&xas); /* walk the tree to the slot */ if (xas_retry(&xas, folio)) /* hit a transient "retry" internal entry? */ goto repeat; if (!folio || xa_is_value(folio)) /* miss, or a shadow/swap value entry */ goto out; if (!folio_try_get(folio)) /* raise refcount; fails if being freed */ goto repeat; if (unlikely(folio != xas_reload(&xas))) { /* did it change under us? */ folio_put(folio); goto repeat; }out: rcu_read_unlock(); return folio;}
This is the textbook RCU-protected lookup. Under rcu_read_lock() the tree cannot be freed out from under us, but an entry can be swapped concurrently by a writer holding xa_lock. The code defends against three races: xas_retry handles the transient “retry” internal entry the XArray plants while a node is being modified; folio_try_get fails if the folio’s refcount already hit zero (it is mid-eviction); and xas_reload re-reads the slot to confirm the folio we grabbed is still the one at this index, retrying if a concurrent store replaced it. The result distinguishes three outcomes a caller must handle: a real folio (with a raised refcount), NULL (genuine miss), or a value entry (shadow/swap — returned as-is, no refcount). The higher-level __filemap_get_folio wraps this, treats a value entry as a miss, and optionally locks or creates the folio (FGP_LOCK, FGP_CREAT).
Marks: the DIRTY / WRITEBACK / TOWRITE tags
Each XArray entry carries three independent mark bits — XA_MARK_0, XA_MARK_1, XA_MARK_2 (core-api docs). The mark bits are stored compactly in the tree’s interior nodes so that a search for “the next marked entry” can skip whole subtrees with no marked descendants — that is the entire point of marks, and why writeback can find dirty folios without scanning every slot.
PAGECACHE_TAG_DIRTY (mark 0) — the folio holds data not yet written to backing store. Set when the folio is dirtied. From __folio_mark_dirty (mm/page-writeback.c, v6.12):
PAGECACHE_TAG_WRITEBACK (mark 1) — the folio is currently being written to disk. Set in __folio_start_writeback (xas_set_mark(&xas, PAGECACHE_TAG_WRITEBACK)), and cleared, along with DIRTY and TOWRITE, when writeback completes.
PAGECACHE_TAG_TOWRITE (mark 2) — a snapshot of “dirty right now, at the start of this writeback pass.” This exists to defeat writeback livelock: a process steadily re-dirtying pages could keep a sync running forever. tag_pages_for_writeback (v6.12) walks the DIRTY-marked entries once and copies the mark to TOWRITE; the writeback loop then writes only TOWRITE-marked folios, so pages dirtied after the pass began are not chased:
The xas_pause() / cond_resched() every XA_CHECK_SCHED entries is the documented manners for not hogging the CPU (and not holding the lock) while marking a huge file.
mapping_tagged(mapping, PAGECACHE_TAG_*) answers “does this mapping have any folio with this mark?” cheaply — used to decide whether a mapping needs to be on the writeback list at all. The policy of when dirtying and flushing happen lives in the sibling notes Dirty Pages and Writeback and Dirty Page Balancing and Throttling; here the point is purely that dirty/writeback state is XArray marks, queried and walked with the xas_* mark API.
Multi-index entries — how large folios sit in the XArray
A 4 KiB page occupies one slot. A large folio (e.g. an order-9, 2 MiB THP, or a smaller order-2 large folio) occupies a range of slots tied together as one multi-index entry. The core-api docs state the rule precisely: “operations on one index affect all indices … the current implementation only allows tying ranges which are aligned powers of two together; eg indices 64–127 may be tied together, but 2–6 may not be.” This aligns exactly with folio order: an order-n folio at index i (where i is 2^n-aligned) occupies indices i … i + 2^n − 1.
Internally, one slot holds the canonical entry (the real folio pointer) and the others hold sibling entries (xa_is_sibling()), each encoding which slot has the canonical value. The advanced caller sees them when stepping with xas_next/xas_prev and must skip them; iterators like xas_for_each return each multi-index entry exactly once, at its first index. A multi-index entry is created with XA_STATE_ORDER() or xas_set_order() followed by xas_store() — precisely what __filemap_add_folio does via xas_set_order(&xas, index, folio_order(folio)). Storing NULL into any index dissolves the tie; a multi-index entry can be split into smaller ranges with xas_split_alloc() (allocate, lock-free) then xas_split() (under the lock) — the mechanism behind splitting a large folio during partial truncation or reclaim. The memory win is real: “tying 512 entries together will save over 4kB” per the docs.
Locking summary
The i_pages lock (xa_lock) is the XArray’s embedded spinlock; the page cache initializes i_pages to take it with IRQs disabled (XA_FLAGS_LOCK_IRQ) because writeback-completion handlers touch the tree from interrupt context. Writers (insert, erase, mark) hold xa_lock_irq. Readers (lookup) use only rcu_read_lock() and the retry/reload dance shown above. The advanced xas_* API does no locking for you — the caller is responsible. The address_space carries additional higher-level locks for distinct concerns: invalidate_lock (truncate vs fault/read coherence) and i_mmap_rwsem (the i_mmap rbtree of VMAs), which sit abovei_pages in the lock-ordering hierarchy documented at the top of mm/filemap.c.
Common Misunderstandings
“i_pages is still a radix tree.” It is a radix tree internally, but the type and API are struct xarray / xa_* / xas_* as of 4.20; code or articles using radix_tree_* against the page cache are pre-4.20. Both 6.12 and 6.18 LTS use the XArray.
“A page-cache lookup takes the i_pages lock.” The hot lookup path is fully lockless (RCU); only writers take xa_lock. Assuming the lock is held on read is a correctness error.
“DIRTY and WRITEBACK are folio flags.” The folio also has PG_dirty/PG_writeback flags, but the searchable, per-mapping dirty/writeback state — the thing writeback actually iterates — is the XArray mark, not the folio flag. The two are kept in sync; conflating them obscures why writeback can find dirty folios cheaply.
“Multi-index entries can cover arbitrary ranges.” No — only aligned powers of two, matching folio order. An order-3 folio cannot start at index 5.
“A value entry returned by a lookup is a folio.” A value entry (xa_is_value()) is a shadow or swap entry, not a pointer; dereferencing it as a folio is a bug. Lookups must test for it.
Alternatives and When a Different Structure Is Used
The page cache could conceivably use a hash table (O(1) lookup) but the XArray is chosen because file access is range-clustered and ordered — readahead, writeback, and truncate all operate on contiguous offset ranges, which a hash cannot iterate cache-efficiently, and the XArray can (“go to the next or previous entry in a cache-efficient manner,” per the docs). Where the kernel needs an ordered interval structure instead of an offset-indexed array — for example the set of VMAs mapping a file, which are arbitrary [start,end) ranges — it uses a different structure entirely: i_mmap is an rb_root_cached (red-black tree), and the per-process VMA set uses the maple tree. The distinction is instructive: XArray for dense integer-indexed arrays (page offsets); rbtree/maple tree for sparse interval sets (address ranges). For the IDR-style “allocate a small integer ID” use case, the XArray’s allocating mode (XA_FLAGS_ALLOC) has subsumed the old idr API.
Production Notes
The XArray’s design directly shaped two of the most consequential 6.x page-cache features. Large folios rely on multi-index entries: a filesystem like XFS can read a file in 64 KiB or larger units, storing one large folio per multi-index range, cutting per-page overhead and TLB pressure — the AS_FOLIO_ORDER_MIN/MAX bits in flags declare the allowed orders. Shadow/workingset detection relies on value entries: by leaving a recency cookie where an evicted folio was, the kernel measures refault distance and protects a thrashing working set — visible in /proc/vmstat’s workingset_* counters. Operationally, the i_pages lock can become a contention point on a single hot file hammered by many CPUs (e.g. a shared mmap’d database file); the RCU-lockless read path mitigates this for the common cache-hit read, but heavy concurrent dirtying of one file serializes on xa_lock_irq. Tracing mm_filemap_add_to_page_cache / mm_filemap_delete_from_page_cache tracepoints (emitted by the functions above) is the standard way to watch cache churn for a specific inode.
See Also
The Page Cache — the subsystem this structure implements; read it for the buffered-I/O path, eviction, and /proc/meminfo semantics. This note is its data-structure half.
Folios and the Folio Conversion — what a struct folio is; the XArray stores folio pointers, and the *_folio method names trace the conversion.