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.
Scope, stated in both directions
Four notes in this vault describe the page cache, split by the question you are asking. The one this note is most often confused with is The Page Cache and address_space, and the boundary is sharp:
The Page Cache and address_space owns the VFS-side vtable seam. What each address_space_operations method must guarantee, which lock is held when it runs, how ext4 and XFS install their tables, how a buffered read()/write() dispatches into them, and what the methods used to be called before the folio conversion. If the noun at the centre of your question is a function pointer, go there.
This note owns the indexing structure. What an XArray slot can physically contain and how each kind is recognised from its bit pattern, how a multi-order folio occupies several slots, how the DIRTY/WRITEBACK/TOWRITE marks are stored and walked, what a shadow entry’s bits mean, how the RCU lookup defends itself against three concurrent races, and how to see the whole thing from userspace with mincore(2). If the noun at the centre of your question is an index, a slot, a mark or an entry, you are in the right place.
The Page Cache owns memory behaviour (how much RAM, dirty thresholds, reclaim, stalls) and Folios and the Page Cache owns the stored object (folio sizing, FGP_* flags).
Where this note touches struct address_space’s fields or the vtable at all, it does so only from the data-structure angle — which lock protects which field, and which methods mutate i_pages — and defers the contracts to the sibling rather than restating them.
This note pins every claim to Linux 6.12, read at the v6.12 tag via raw.githubusercontent.com. Where something changed after 6.12, the release that changed it is named, and version claims are established by fetching the same path at successive tags and recording HTTP 200 versus 404 rather than from release notes. Live measurements at the end of the note were taken on a 7.1.13 kernel and are labelled as such.
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).
Which lock protects which field
The structure is not protected by one lock; it is protected by five, and knowing which is which is the difference between a correct traversal and a data race. struct address_space is defined at include/linux/fs.h line 465 (v6.12) and the locks it embeds or implies are:
Field
Type
What it holds
Protected by
Read under RCU?
host
struct inode *
The owning inode (or block_device)
Immutable after init
n/a
i_pages
struct xarray
The page cache itself. Slots hold folios, shadows, DAX or swap entries
Its own embedded xa_lock, taken with IRQs disabled (xa_lock_irq) because writeback completion touches it from softirq
Yes — lookups take only rcu_read_lock()
invalidate_lock
struct rw_semaphore
— (it is a lock)
—
—
gfp_mask
gfp_t
Allocation flags for folios in this mapping
Set at inode init; read lock-free
Effectively yes
i_mmap_writable
atomic_t
Count of VM_SHARED, VM_MAYWRITE mappings
i_mmap_rwsem (per kerneldoc) plus atomics
—
nr_thps
atomic_t (only under CONFIG_READ_ONLY_THP_FOR_FS)
Count of huge pages in a non-shmem file
Atomics
—
i_mmap
struct rb_root_cached
Not the cache — the interval tree of VMAs that mmap() this file, used as the file-backed reverse map (rmap)
i_mmap_rwsem
No
nrpages
unsigned long
Number of page-sized units cached (a 64 KiB folio contributes 16, not 1)
The i_pages lock — incremented inside xas_lock_irq() in __filemap_add_folio and decremented inside page_cache_delete, so it can never drift from the tree
No
writeback_index
pgoff_t
Where the next background writeback pass resumes
The writeback path’s own serialization
No
a_ops
const struct address_space_operations *
The filesystem’s vtable
Immutable after init
Effectively yes
flags
unsigned long
AS_* error/policy bits and the folio-order range
Bit-atomic ops (set_bit/test_bit)
Yes
wb_err
errseq_t
Most recent writeback error, as a sequence cookie
errseq_t’s own cmpxchg protocol
Yes
i_private_lock
spinlock_t
— (it is a lock). Kerneldoc: “For use by the owner of the address_space.” fs/buffer.c uses the block device’s copy of it
—
—
i_private_list
struct list_head
Buffer-cache list of metadata buffers a filesystem must write before this inode’s data. Not protected by this structure’s own i_private_lock — see below
The backing block device’si_private_lock
No
i_mmap_rwsem
struct rw_semaphore
— (it is a lock) — guards i_mmap and i_mmap_writable
—
—
i_private_data
void *
Filesystem-private pointer
Filesystem’s own rules
—
Three observations that a field list alone would not give you.
nrpages counts pages, not entries. It is bumped by folio_nr_pages(folio), not by 1, so with large folios enabled nrpages and “number of occupied XArray slots” are different numbers. Code that treats nrpages as a folio count is wrong on any modern filesystem.
i_pages and i_mmap are a deliberate split by shape of question. Cached content is indexed by a dense integer (page offset) and lives in the XArray; mappings of that content are arbitrary [start, end) intervals and live in a red-black interval tree. Neither structure can do the other’s job efficiently. The same split recurs one level up: a process’s VMAs are intervals and live in a maple tree.
i_private_lock does not protect i_private_list. This is the single most counter-intuitive fact in the structure and it is stated outright in fs/buffer.c (v6.12, lines 467–483): “mapping→i_private_lock does not protect mapping→i_private_list! In fact, mapping→i_private_list will always be protected by the backing blockdev’s →i_private_lock.” The list holds metadata buffer-heads that must reach disk before this inode’s data (the ordering guarantee behind sync_mapping_buffers()), and since those buffers live in the block device’s address_space, that is the address_space whose lock owns them. The kerneldoc for all three i_private_* fields says only “For use by the owner of the address_space,” which is accurate and unhelpful; the real rule is in buffer.c.
Only one lock in this structure protects the cache, and readers do not take it. Everything below in this note is either “what a writer does under xa_lock_irq” or “what a reader does under rcu_read_lock() alone.”
The contracts of a_ops and the full matrix of which lock is held when each method is invoked belong to The Page Cache and address_space and are not restated here.
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) let a mapping declare a minimum and maximum folio order it will use. They landed in v6.12 exactly — AS_FOLIO_ORDER_MIN does not appear in include/linux/pagemap.h at v6.11 and appears six times at v6.12 (verified by fetching both tags) — and they are 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 — the subset that mutates i_pages
a_ops points at the filesystem’s per-mapping methods, defined at include/linux/fs.h line 397 (v6.12). What each method must guarantee, and which lock is held when it is called, is The Page Cache and address_space’s subject, not this note’s. What belongs here is narrower and more useful for reasoning about the data structure: which of these twenty methods actually touch the XArray, and what do they do to it? Most of them do not touch it at all — they operate on a folio the caller already found.
Method
Signature shape (v6.12)
Effect on i_pages
read_folio
int (*)(struct file *, struct folio *)
None. The folio is already in the XArray (inserted by __filemap_get_folio(… FGP_CREAT)) and locked; the method only fills its bytes and sets PG_uptodate.
readahead
void (*)(struct readahead_control *)
None directly — readahead_folio() hands the method folios that page_cache_ra_unbounded() already inserted. The insertions are what make mincore(2) light up ahead of demand, as measured below.
dirty_folio
bool (*)(struct address_space *, struct folio *)
Sets PAGECACHE_TAG_DIRTY (XA_MARK_0) on the folio’s slot, under xa_lock_irqsave. This is the only way the searchable dirty state is created.
writepages
int (*)(struct address_space *, struct writeback_control *)
Walks the DIRTY/TOWRITE marks (via writeback_iter() / filemap_get_folios_tag()) and, per folio written, clears DIRTY and sets then clears WRITEBACK.
writepage
int (*)(struct page *, struct writeback_control *)
Same mark transitions, one page at a time. Removed from the struct in v6.16 (present at v6.15, absent at v6.16 — verified by fetching include/linux/fs.h at both tags).
invalidate_folio
void (*)(struct folio *, size_t, size_t)
None — but it is called immediately before filemap_remove_folio(), which is what stores NULL or a shadow into the slot.
release_folio
bool (*)(struct folio *, gfp_t)
None. It votes on whether the folio may be removed; the removal is the caller’s xas_store().
free_folio
void (*)(struct folio *)
None — called after the slot has already been cleared, from filemap_free_folio().
Replaces the slot’s pointer with the destination folio, via folio_migrate_mapping(), which does the xas_store() under xa_lock_irq and copies the marks across.
direct_IO
ssize_t (*)(struct kiocb *, struct iov_iter *)
Bypasses the XArray entirely — that is the point of O_DIRECT. The generic path invalidates any overlapping cached range first so the two views cannot diverge.
swap_activate / swap_rw
swapfile support
Operate on the swap device’s own address_space, one of the swap caches, not on a file’s.
Two consequences worth carrying forward. First, the marks are the interface between the vtable and the XArray: dirty_folio sets a mark, writepages walks marks, and nothing else in the table participates in mark maintenance. Marking a folio dirty without setting the XArray mark is therefore a real bug class — writeback will never find it — and is exactly one of the failure modes catalogued in the sibling note.
Second, the method names are a fingerprint of the folio conversion: what used to be readpage, set_page_dirty and invalidatepage (all taking struct page *) are now read_folio, dirty_folio and invalidate_folio (all taking struct folio *). The legacy writepage was the last struct page * holdout in the table and is gone as of v6.16. Material written against readpage predates v5.19 and material written against ->writepage describes a method that no longer exists in mainline — see Folios and the Folio Conversion for the shape of that migration.
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. This is independently confirmed by existence-checking rather than by release notes: raw.githubusercontent.com/torvalds/linux/v4.19/lib/xarray.c returns HTTP 404 and the same path at v4.20 returns HTTP 200, which dates the file’s addition to that merge window exactly. So: radix tree until 4.19; XArray from 4.20 onward, which includes both 6.12 and 6.18 LTS.
Three API layers, and which one the page cache uses
The XArray exposes the same tree through three interfaces, and mixing them up is the commonest source of confusion when reading mm/filemap.c. The core-api documentation (v6.12) enumerates the locking obligations of each precisely:
Layer
Prefix
Locking obligation
Example
Used by the page cache?
Normal
xa_*
“You do not have to worry about locking.” Reads take rcu_read_lock() internally (xa_load, xa_for_each, xa_get_mark); writes take xa_lock internally (xa_store, xa_erase, xa_cmpxchg, xa_set_mark)
xa_load(&xa, index)
Rarely — the page cache almost always needs to do more than one thing under one lock
Normal, lock-held
__xa_*
“Assumes xa_lock held on entry.” Same operations, but the caller has already taken the lock so several can be composed atomically
__xa_set_mark(&mapping->i_pages, folio_index(folio), PAGECACHE_TAG_DIRTY) in __folio_mark_dirty()
Yes — for single-slot mark changes where a cursor would be overkill
Advanced
xas_* + XA_STATE
“No locking is done for you … you are required to use the xa_lock while modifying the array.” A stack-allocated struct xa_state cursor holds the position and any error, so operations compose without re-walking from the root
XA_STATE(xas, &mapping->i_pages, index) then xas_lock_irq, xas_set_order, xas_for_each_conflict, xas_store
Yes — this is the page cache’s native layer. Insertion, deletion, mark-copying and multi-index stores are all xas_*
The reason the page cache lives in the advanced layer is composition. Inserting a folio must, under one acquisition of xa_lock_irq: widen the cursor to the folio’s order, scan the whole target range for conflicts, capture any shadow it displaces, store the folio, and bump mapping->nrpages. With the normal API that is five tree walks and four lock round-trips, and nrpages could drift from the tree in between. With a cursor it is one walk and one critical section.
Two cursor facilities earn special mention because they replace mechanisms the radix tree handled badly.
xas_nomem() replaced radix_tree_preload(). The old API forced callers to pre-allocate nodes before taking their lock, guessing how many they would need, in a per-CPU cache. The XArray instead lets xas_store() try a GFP_NOWAIT allocation under the lock; if that fails, the store leaves -ENOMEM in the cursor, the caller drops the lock, calls xas_nomem(&xas, gfp) to allocate properly, and loops. That is the for (;;) { … if (!xas_nomem(&xas, gfp)) break; } shape in __filemap_add_folio().
xas_pause() makes long walks preemptible. A cursor holds raw pointers into tree nodes, so dropping the lock invalidates it. xas_pause() collapses the cursor back to a plain index so it can be safely resumed after cond_resched(). The docs state the rule: “If you need to drop whichever of those locks is protecting your state and tree, you must call xas_pause() so that future calls do not rely on the parts of the state which were left unprotected.” This is why tag_pages_for_writeback() can mark a 100 GiB file without holding xa_lock_irq — and interrupts disabled — for the whole operation.
One footnote with teeth: the advanced API is EXPORT_SYMBOL_GPL — “The advanced API is only available to modules with a GPL-compatible license.” A proprietary module can use xa_load() but cannot build a page-cache-like structure with cursors.
What an XArray slot can actually hold
This is the single most useful thing to know about the page cache as a data structure, and it is almost never written down in one place: a page-cache slot is a tagged union, and the tag is the bottom two bits of the word. The XArray requires every stored pointer to be at least 4-byte aligned — true for anything from kmalloc() or the page allocator — which frees bits 1:0 to discriminate. include/linux/xarray.h (v6.12) defines the whole encoding in a dozen lines:
packet-beta
title Bottom bits of an XArray slot decide what the word means (64-bit)
0: "t0"
1: "t1"
2-63: "payload -- pointer bits 63:2, or value v in bits 63:1, or internal v in bits 63:2"
The two-bit tag at the bottom of every XArray slot. What it shows:t0 = 1 means the slot is a value entry and the payload is the integer v in bits 63:1 (BITS_PER_XA_VALUE = 63). t1:t0 = 10 means the slot is an internal entry and v lives in bits 63:2. t1:t0 = 00 means the word is an ordinary, 4-byte-aligned pointer — which for the page cache means a struct folio *. t1:t0 = 01 and 11 are the “tagged pointer” encodings (xa_tag_pointer()), which the page cache does not use. The insight to take: the page cache never allocates a separate “what kind of thing is this” field. The discriminant is free, stolen from alignment, which is why a shadow entry costs a pointer’s worth of memory instead of a whole struct page.
Everything a page-cache slot can contain, and the exact test that recognises it:
What is in the slot
Recognised by
Payload
Who puts it there
Refcount taken on lookup?
Nothing
entry == NULL
—
Initial state, or xas_store(&xas, NULL) on truncate
n/a
A folio
!xa_is_value(e) && !xa_is_internal(e) — i.e. bits 1:0 are 00
struct folio *
__filemap_add_folio()
Yes — folio_try_get()
A shadow / workingset entry
xa_is_value(e)
Packed eviction cookie (see below)
page_cache_delete(mapping, folio, shadow) during reclaim
No — returned as an opaque value
A swap entry (shmem/tmpfs only)
xa_is_value(e) — same test as a shadow
swp_entry_t
shmem’s swap-out path
No
A DAX entry
xa_is_value(e) — also the same test
pfn << DAX_SHIFT plus four flag bits: DAX_LOCKED, DAX_PMD, DAX_ZERO_PAGE, DAX_EMPTY (fs/dax.c, v6.12)
the DAX fault path
No
A sibling entry (part of a multi-index folio)
xa_is_sibling(e) — internal, with v in 0…62
The offset of the canonical slot within this node
xas_store() on a cursor widened by xas_set_order()
Skipped by iterators
A retry entry
xa_is_retry(e) — e == XA_RETRY_ENTRY (internal 256)
—
The XArray itself, transiently, while a node is being reorganised
Triggers a retry
A zero entry
xa_is_zero(e) — internal 257
—
xa_reserve(). The normal API returns NULL for it; only the advanced xas_* API ever sees it
n/a
A node pointer
xa_is_node(e) — internal with value > 4096
struct xa_node *
The XArray, for interior tree links
Never returned to callers
An error
xa_is_err(e) — internal in the negative range
-errno
Returned by the API; never stored in a slot
n/a
The crucial, non-obvious point is in rows three, four and five: shadow entries, shmem swap entries and DAX entries are all value entries and cannot be told apart by xa_is_value() alone. What disambiguates them is which mapping you are looking at. A DAX entry only appears in a mapping on a DAX-mounted filesystem (IS_DAX(inode)); a swap entry only in a shmem_mapping(); a shadow anywhere else. This is why filemap_get_entry() returns the raw value and makes the caller decide, and why __filemap_get_folio() — the general-purpose wrapper — simply treats any value entry as a miss:
folio = filemap_get_entry(mapping, index); if (xa_is_value(folio)) folio = NULL;
Inside a shadow entry
A shadow is not a flag; it is a packed record, and reading its layout explains what workingset detection actually measures. mm/workingset.c (v6.12, lines 183–226) builds it:
packet-beta
title A page-cache shadow entry, assembled from the inside out
0: "1"
1: "WS"
2-11: "NUMA node id -- NODES_SHIFT = 10"
12-27: "memcg id -- MEM_CGROUP_ID_SHIFT = 16"
28-63: "eviction timestamp, bucketed by bucket_order (36 bits left over)"
The bit layout of a shadow entry as pack_shadow() builds it (field widths are CONFIG-dependent and the ones drawn are from this host’s Fedora kernel config: CONFIG_NODES_SHIFT=10 and MEM_CGROUP_ID_SHIFT = 16 (it is 0 when CONFIG_MEMCG is off), giving EVICTION_SHIFT = (64 − 63) + 1 + 10 + 16 = 28 and leaving 36 bits for the timestamp). What it shows: bit 0 is the xa_mk_value() tag that makes the whole word a value entry rather than a pointer; then, from the bottom up, one workingset flag, the NUMA node the folio was evicted from, the memory-cgroup that owned it, and finally an eviction timestamp filling all remaining bits. The insight to take: a shadow answers four questions at once — was this folio already a workingset member, where was it, whose was it, and how long ago did it go? — in the space of one pointer. unpack_shadow() peels the fields off in exactly the reverse order.
The timestamp is not a wall clock. It is a snapshot of the LRU’s eviction counter, right-shifted by bucket_order so that the fixed number of available bits covers the whole possible range of a machine’s memory at a coarser granularity. On a refault, the current counter minus the stored one gives the refault distance: how many other folios were evicted between this one leaving and coming back. If that distance is smaller than the size of the list that could have held it, the folio was evicted too early — the working set does not fit — and the folio is promoted on re-entry. That is the whole of workingset detection, and it is why a shadow can be thrown away cheaply (you lose accuracy, never correctness) and why /proc/vmstat’s workingset_refault_* counters are the metric to watch for thrashing.
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() (mm/filemap.c line 1881) wraps this and adds the create-on-miss path; filemap_get_folio(mapping, index) is simply __filemap_get_folio(mapping, index, 0, 0), a static inline in include/linux/pagemap.h line 767. Drawn as control flow, the whole lookup is this:
flowchart TB
START(["filemap_get_folio(mapping, index)<br/>= __filemap_get_folio(…, fgp=0, gfp=0)"])
START --> GE["filemap_get_entry(mapping, index)<br/>rcu_read_lock()"]
GE --> LOAD["xas_load(&xas)<br/>walk the tree to the slot"]
LOAD --> RETRY{"xas_retry(&xas, folio)?<br/>(hit XA_RETRY_ENTRY:<br/>a node is being reorganised)"}
RETRY -->|yes| LOAD
RETRY -->|no| KIND{"What is in the slot?"}
KIND -->|"NULL"| MISS
KIND -->|"xa_is_value(): shadow,<br/>shmem swap, or DAX"| VAL["returned as an opaque value<br/>with NO refcount"]
KIND -->|"a folio pointer"| GET{"folio_try_get(folio)<br/>succeeded?"}
GET -->|"no: refcount already 0,<br/>the folio is mid-free"| LOAD
GET -->|yes| RELOAD{"folio == xas_reload(&xas)?<br/>(did a writer swap the slot<br/>while we were unlocked?)"}
RELOAD -->|"no: folio_put() and retry"| LOAD
RELOAD -->|yes| HIT(["HIT -- return the folio<br/>with an elevated refcount"])
VAL --> COERCE["__filemap_get_folio:<br/>if (xa_is_value(folio)) folio = NULL"]
COERCE --> MISS
MISS{"FGP_CREAT set?"}
MISS -->|no| ENOENT(["return ERR_PTR(-ENOENT)"])
MISS -->|yes| ORDER["order = max(mapping_min_folio_order,<br/>FGF_GET_ORDER(fgp))<br/>clamped to mapping_max_folio_order<br/>and to __ffs(index) if misaligned"]
ORDER --> ALLOC["filemap_alloc_folio(gfp, order)<br/>then filemap_add_folio()"]
ALLOC -->|"-EEXIST: someone<br/>raced us to the slot"| GE
ALLOC -->|"-ENOMEM"| SHRINK["order-- and retry<br/>down to min_order"]
SHRINK --> ALLOC
ALLOC -->|success| NEWF(["return the new, locked folio"])
filemap_get_folio() and its FGP_CREAT sibling as one flowchart. What it shows: three distinct retry loops, each defending against a different race, plus a fourth loop that walks folio order downwards under memory pressure. The insight to take: the lockless read path is not “just look it up” — it is a small state machine, and every back-edge in the diagram exists because a writer holding xa_lock can change the slot at any instant. xas_retry covers the XArray’s own internal reorganisation, folio_try_get covers a folio whose last reference has already been dropped, and xas_reload covers a slot that was replaced entirely between the load and the reference. Remove any one of the three and the path is racy.
The order-reduction loop at the bottom is a 6.x addition and is why FGP_CREAT almost never fails outright: if an order-4 (64 KiB) folio cannot be allocated, the code retries at order 3, then 2, and so on down to mapping_min_folio_order(mapping) — the floor the filesystem declared through the AS_FOLIO_ORDER bits in flags. Only below that floor does it give up, because a filesystem with a block size larger than PAGE_SIZE genuinely cannot represent its data in smaller folios.
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.
Marks are not stored in the leaf slot; they are bitmaps in the interior nodes (unsigned long marks[XA_MAX_MARKS][XA_MARK_LONGS] in struct xa_node, include/linux/xarray.h v6.12), and a mark set on a leaf propagates up so that every ancestor node says “somewhere below me there is a marked entry.” That propagation is the whole point: xas_for_each_marked() can skip an entire subtree in one comparison, so writepages on a 100 GiB file with three dirty folios visits a handful of nodes rather than 26 million slots.
Mark
Alias
Meaning
Set by
Cleared by
XA_MARK_0
PAGECACHE_TAG_DIRTY
This folio holds data not yet on the backing store
__folio_mark_dirty() — __xa_set_mark(&mapping->i_pages, folio_index(folio), PAGECACHE_TAG_DIRTY) under xa_lock_irqsave (mm/page-writeback.c line 2798)
__folio_start_writeback() — xas_clear_mark(&xas, PAGECACHE_TAG_DIRTY), but only if (!folio_test_dirty(folio)), i.e. only if the caller already cleared the folio flag via folio_clear_dirty_for_io() (line 3152). Also cleared wholesale by xas_init_marks() when the folio is removed.
Read the DIRTY row’s “cleared by” column carefully, because it encodes a real invariant. DIRTY is not cleared when writeback starts; it is cleared only when the caller has already cleared PG_dirty on the folio itself. folio_clear_dirty_for_io() does that before calling __folio_start_writeback(), and if a concurrent writer re-dirties the folio in between, folio_test_dirty() is true again and the mark survives — so the folio stays visible to the next writeback pass. Getting this ordering wrong is how you lose a write.
Note also the IRQ asymmetry: DIRTY is set from process context under xa_lock_irqsave, while WRITEBACK is cleared from interrupt context when a bio completes. That is the reason i_pages is initialized with XA_FLAGS_LOCK_IRQ and every writer in this note takes xas_lock_irq / xa_lock_irqsave rather than a plain spinlock.
Finally, a mapping can opt out entirely: AS_NO_WRITEBACK_TAGS (bit 5 of flags) makes mapping_use_writeback_tags() false, and the whole tag-maintenance block above is skipped. Anonymous-memory swap mappings use this — there is no ->writepages walk to serve.
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.
Eviction: swapping a folio out of the slot and a shadow into it
Removal is the mirror image of insertion, and the one place where the tagged-union nature of a slot does real work. page_cache_delete() (v6.12, lines 137–156) is four lines of substance:
static void page_cache_delete(struct address_space *mapping, struct folio *folio, void *shadow){ XA_STATE(xas, &mapping->i_pages, folio->index); long nr = 1; mapping_set_update(&xas, mapping); xas_set_order(&xas, folio->index, folio_order(folio)); nr = folio_nr_pages(folio); VM_BUG_ON_FOLIO(!folio_test_locked(folio), folio); xas_store(&xas, shadow); /* shadow may be NULL */ xas_init_marks(&xas); folio->mapping = NULL; /* Leave page->index set: truncation lookup relies upon it */ mapping->nrpages -= nr;}
The shadow argument is the entire difference between the two reasons a folio leaves the cache. Truncation calls filemap_remove_folio(), which passes NULL: the file’s data at that offset is gone, so remembering anything about it would be wrong. Reclaim calls __filemap_remove_folio(folio, shadow) with a packed workingset cookie: the data still exists on disk, and the kernel wants to remember when it gave up on caching it. One function, one store, two very different meanings — discriminated by which value the caller supplies.
Note xas_init_marks(&xas) immediately after the store. A shadow entry is not dirty, not under writeback and not to-write; resetting all three marks in one call is both cheaper and safer than clearing them individually, and it is what prevents a stale DIRTY mark from making writepages trip over a value entry.
sequenceDiagram
autonumber
participant R as Reclaim (shrink_folio_list)
participant W as workingset_eviction()
participant X as i_pages XArray
participant F as Faulting reader, later
participant D as Backing store
Note over R,X: folio at index 42 is clean, cold, file-backed
R->>R: folio_lock(folio)
R->>W: workingset_eviction(folio, target_memcg)
W->>W: read lruvec eviction counter<br/>pack_shadow(memcgid, node, eviction, workingset)
W-->>R: void *shadow (a value entry)
R->>X: xa_lock_irq(&mapping->i_pages)
R->>X: xas_store(&xas, shadow) -- folio pointer REPLACED
R->>X: xas_init_marks(&xas) and nrpages -= folio_nr_pages()
R->>X: xa_unlock_irq
R->>R: folio_put() -- frame returns to the allocator
Note over X: slot 42 now holds one word of<br/>metadata instead of 4 KiB of data
F->>X: filemap_get_entry(mapping, 42)
X-->>F: a value entry, not a folio
F->>F: __filemap_get_folio() maps it to "miss",<br/>allocates a fresh folio
F->>W: workingset_refault(folio, shadow)
W->>W: unpack_shadow() then distance = now minus eviction
alt distance < available list size
W->>F: folio_set_active() -- evicted too early,<br/>promote it and bump workingset_restore
else distance too large
W->>F: leave inactive -- genuinely cold,<br/>bump workingset_refault only
end
F->>D: ->read_folio() / ->readahead() refills the bytes
F->>X: the slot's value entry is overwritten by the new folio pointer
The full life of a shadow entry, from eviction to refault decision. What it shows: reclaim does not merely delete the slot — it substitutes a one-word record in place of a 4 KiB folio, and that record is what lets a later miss be classified as thrashing rather than cold. The insight to take: the XArray’s value-entry encoding is not a convenience, it is the enabling mechanism for workingset detection. Without a way to store a non-pointer in a slot, the kernel would need a side table keyed by (inode, offset) to remember evictions — which is to say, a second page cache. Note that the shadow is consumed and then destroyed — the final step overwrites the slot with the new folio pointer, and nothing preserves the cookie. Shadows are lossy by design: losing one costs accuracy in the refault decision, never correctness.
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.
flowchart TB
ROOT["struct xarray (i_pages)<br/>xa_head"]
N0["struct xa_node<br/>shift = 6, 64 slots<br/>marks[3][1] bitmaps propagate<br/>DIRTY / WRITEBACK / TOWRITE upward"]
ROOT --> N0
N0 -->|"slot 0"| S0["folio A (order 0)<br/>covers index 0"]
N0 -->|"slot 1"| S1["NULL<br/>index 1 not cached"]
N0 -->|"slot 2"| S2["value entry<br/>shadow for index 2"]
N0 -->|"slot 3"| S3["NULL"]
N0 -->|"slot 4 -- CANONICAL"| S4["<b>folio B (order 2)</b><br/>the real struct folio *<br/>covers indices 4..7"]
N0 -->|"slot 5"| S5["sibling -> 4<br/>xa_is_sibling() true"]
N0 -->|"slot 6"| S6["sibling -> 4"]
N0 -->|"slot 7"| S7["sibling -> 4"]
N0 -->|"slot 8"| S8["struct xa_node *<br/>xa_is_node() -- deeper subtree<br/>for indices 512.."]
S5 -.->|"resolved by the<br/>iterator, never<br/>returned to callers"| S4
S6 -.-> S4
S7 -.-> S4
One interior XArray node holding a mixture of everything a page cache slot can be. What it shows: an order-0 folio in one slot, a hole, a shadow value entry, an order-2 (16 KiB) folio occupying four slots — one canonical pointer plus three sibling entries — and a child-node pointer. The insight to take: a large folio is stored once and referenced from its other indices, so a lookup at index 6 costs exactly the same as a lookup at index 4 (the sibling resolves in the same node, with no extra memory access), while a lookup at index 5 that returned the sibling word verbatim would be a catastrophic type confusion. This is why xas_load() resolves siblings internally and why advanced-API callers stepping with xas_next() must test xa_is_sibling() themselves. The docs quantify the saving: “tying 512 entries together will save over 4kB.”
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, and the page cache asks for the IRQ-safe variant at inode initialization time — fs/inode.c line 403, v6.12: xa_init_flags(&mapping->i_pages, XA_FLAGS_LOCK_IRQ | XA_FLAGS_ACCOUNT). XA_FLAGS_LOCK_IRQ is there because writeback-completion handlers clear PAGECACHE_TAG_WRITEBACK from interrupt context; XA_FLAGS_ACCOUNT charges the tree’s own interior nodes to the owning memory cgroup, so a process that pins a huge sparse page cache pays for the index as well as the data. 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.
Reading the XArray From Userspace with mincore(2)
Everything above is internal to the kernel, but the contents of one file’s i_pages are directly observable without any privilege at all, and the tool is mincore(2). This is worth doing once: it turns the structure from a diagram into something you can watch fill and empty.
The syscall’s own contract is modest — “determine whether pages are resident in memory … the least significant bit of each byte will be set if the corresponding page is currently resident in memory” (mincore(2)) — but for a file-backed mapping with no PTE installed, “resident” is resolved by going to the page cache. mm/mincore.c (v6.12, lines 52–70) is unambiguous:
That is a lookup in vma->vm_file->f_mapping->i_pages at the given index. So mincore() over a file mapping is, quite literally, a dump of which slots of that file’s XArray are occupied by an up-to-date folio. Every # in the bitmaps below is one non-empty slot.
Uncertain
These measurements were taken on kernel 7.1.13-200.fc44 (Fedora 44), nine releases past this note’s v6.12 pin, on btrfs over LUKS. The readahead numbers in particular are policy, not structure, and policy moves between releases and varies by filesystem and by the backing device’s read_ahead_kb (4096 on this device’s bdi). Treat the numbers as an illustration of what readahead does to the XArray, not as v6.12 constants. Reason: no v6.12 machine was available in this task. To resolve: repeat on 6.12 with the same filesystem. uncertain
Watching the slots fill
A 1 MiB file (256 pages) written, fsynced, then evicted with posix_fadvise(POSIX_FADV_DONTNEED) before being mapped:
A. after fadvise(DONTNEED) + mmap 0/256 resident ................................................................ ...B. after faulting every 16th page 256/256 resident ################################################################ ...C. after madvise(WILLNEED) (readahead) 256/256 resident ################################################################ ...D. re-evicted, re-mmapped 0/256 resident ................................................................ ...E. after a single pread() of 4 KiB @0 32/256 resident ################################................................ ...
Line A is an empty XArray: a struct address_space exists, i_pages is initialized, and every slot is NULL. Line B is the surprise if you expected demand paging to be literal — touching pages 0, 16, 32, … brought in all 256, because a file fault goes through filemap_fault(), which calls do_sync_mmap_readahead(), which populates a whole window of slots, not one. Line E is the cleanest number in the set: one 4 KiB pread() at offset 0 left 32 folios in the XArray, exactly 128 KiB. The kernel did not read what was asked for; it read what it guessed would be asked for next, and every guess is an __filemap_add_folio() into a slot.
Pushing on line E, one 4 KiB read at a time, sequentially, over a 16 MiB file shows the readahead window ramping:
Read #2 adds nothing — the data was already cached, and readahead had not yet reached its trigger page. Read #3 doubles the window. Read #4 jumps it to 160 pages. Then it plateaus, because the async readahead marker has been pushed far enough ahead that reads 5 and 6 are satisfied entirely from already-populated slots. This is Readahead’s ramp, rendered as the literal occupancy of an XArray’s index space. The policy — the window sizing, the marker placement, the ra_pages cap — belongs to that note; what belongs here is the mechanical fact that each of those 160 pages is one xas_store() into mapping->i_pages, and that each one is visible from userspace the instant it lands.
The two walls, named
Wall 1 — POSIX_FADV_DONTNEED cannot evict a folio that is currently mapped. Measured directly:
after faulting all pages (still mapped): 256/256fadvise DONTNEED *while mapped*: 256/256fadvise DONTNEED *after munmap*, then remap: 0/256
The reason is one comment in mm/truncate.c’s mapping_evict_folio():
/* The refcount will be elevated if any page in the folio is mapped */ if (folio_ref_count(folio) > folio_nr_pages(folio) + folio_has_private(folio) + 1) return 0;
Invalidation is advisory and refuses to act on a folio someone is using. Any benchmark that “drops the cache” with fadvise while the file is still mapped is measuring a warm cache. The resolving command for a genuine global drop is echo 3 | sudo tee /proc/sys/vm/drop_caches, which needs root — unavailable on this host, so the munmap-then-fadvise sequence above was used instead, which is per-file and sufficient here.
Wall 2 — on tmpfs the folios never leave. The same program run against a file on /tmp (which df -T reports as tmpfs) reports 256/256 resident at every single step, including immediately after fadvise(DONTNEED). That is not a failure of the measurement; it is the correct behaviour. On tmpfs the page cache is the storage — there is no backing file to re-read from, so a folio can only leave i_pages by being written to swap, and it is replaced by a swap value entry, not removed. This is the fourth row of the entry-taxonomy table made visible: the one filesystem where a page-cache slot routinely holds a swp_entry_t. mincore_page()’s own comment says so: “When tmpfs swaps out a page from a file, any process mapping that file will not get a swp_entry_t in its pte, but rather it is like any other file mapping … So swapped out tmpfs mappings are tested here.”
smaps — the same folios, counted by sharing and dirtiness
mincore() answers “is there a folio in this slot.” /proc/PID/smaps answers the complementary question: of the folios this process has mapped, how many are shared with someone else, and how many are dirty. The two views intersect exactly at the page cache. A program that maps the same 256 KiB file twice — once MAP_SHARED, once MAP_PRIVATE — reads every page of both, then writes half of each:
--- MAP_SHARED, read-only touches ---7fd5b6af1000-7fd5b6b31000 rw-s 00000000 00:24 10924516 /home/linman/.cache/u1demo/sh.binRss: 256 kBPss: 128 kBShared_Clean: 256 kBShared_Dirty: 0 kBPrivate_Clean: 0 kBPrivate_Dirty: 0 kB--- MAP_SHARED after a child process also maps and reads it ---Rss: 256 kBPss: 85 kBShared_Clean: 256 kB--- MAP_SHARED after writing 32 of 64 pages ---Shared_Clean: 128 kBShared_Dirty: 128 kBPrivate_Dirty: 0 kB--- MAP_PRIVATE after writing 32 of 64 pages (COW) ---Shared_Clean: 128 kBShared_Dirty: 0 kBPrivate_Dirty: 128 kB
Four things fall out of that, and each one is a statement about the XArray.
Shared_Clean: 256 kB on a mapping nobody else has opened. “Shared” in smaps means mapcount ≥ 2, not MAP_SHARED. Here the same process holds two mappings of the same file, so every page-cache folio is mapped twice and every page counts as shared in both VMAs. There are still only 64 folios in i_pages — the 256 kB is counted once per mapping.
Pss is the arithmetic of that sharing. Proportional set size divides each folio by its mapcount: 256 kB ÷ 2 = 128 kB with two mappings, and 256 ÷ 3 = 85 kB once a forked child adds a third. Pss is the only column that sums correctly across processes, which is why it, and not Rss, is the right number for “how much memory is this process actually costing.”
Shared_Dirty after writing through MAP_SHARED. The write dirtied the page-cache folio itself, which set PAGECACHE_TAG_DIRTY on its XArray slot. Those 128 kB are still in i_pages, still shared, and now discoverable by writepages. Nothing was copied.
Private_Dirty after writing through MAP_PRIVATE. This is the opposite: copy-on-write allocated 32 fresh anonymous pages and repointed this process’s PTEs at them. Those pages are not in the XArray at all — they have left the page cache and become anonymous memory backed by swap. The original folios are still in i_pages, still clean, and are still counted in the surviving Shared_Clean: 128 kB. The 128 kB moved columns because it moved data structures, from a file’s i_pages to an anon VMA’s rmap. That boundary — which pages belong to the page cache and which have escaped into anonymous memory — is exactly what Shared_* versus Private_Dirty is telling you, and it is the single most useful thing smaps reports about a file mapping. The PTE-level view of the same event is in Page Table Entries and Hardware Flags and Copy-on-Write and fork.
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.
“xa_is_value() tells me it is a shadow entry.” It tells you the slot is not a pointer. Shadows, shmem swap entries and DAX entries are all value entries and share the identical test; what disambiguates them is which mapping you are holding (shmem_mapping(), IS_DAX(), otherwise a shadow). Code that assumes “value entry ⇒ shadow” breaks on tmpfs and on DAX.
“nrpages is the number of entries in the XArray.” It is the number of page-sized units: __filemap_add_folio() adds folio_nr_pages(folio), so one 64 KiB folio contributes 16. With large folios, nrpages and the number of occupied slots are different numbers.
“mapping->i_private_lock protects mapping->i_private_list.” It does not, and fs/buffer.c says so in as many words: the list is protected by the backing block device’si_private_lock, because that is where the buffers on it live.
“POSIX_FADV_DONTNEED drops the file from the page cache.” Only if nobody has it mapped. mapping_evict_folio() refuses on an elevated refcount, and “the refcount will be elevated if any page in the folio is mapped.” Measured above: 256/256 pages survived a DONTNEED issued while the file was mapped, and 0/256 survived the same call after munmap.
“On tmpfs, evicting the cache frees the file’s memory.” On tmpfs the page cache is the storage. A tmpfs folio leaves i_pages only by going to swap, and it is replaced by a swap value entry rather than removed. mincore() reports 256/256 through every eviction attempt.
“Setting PAGECACHE_TAG_DIRTY is what folio_mark_dirty() does, and clearing PG_dirty clears it.” The mark is set by __folio_mark_dirty(), but it is cleared in __folio_start_writeback() and only if (!folio_test_dirty(folio)) — i.e. only if the caller already ran folio_clear_dirty_for_io(). A re-dirty that races in between keeps the mark, which is what stops writeback from losing the second write.
“Marks live in the slot.” They live in struct xa_node’s marks[XA_MAX_MARKS][XA_MARK_LONGS] bitmaps and propagate to every ancestor, which is the only reason xas_for_each_marked() can skip unmarked subtrees. A per-slot flag would make finding three dirty folios in a 100 GiB file a full scan.
“mincore() tells me whether the page is mapped into my address space.” For a file mapping it tells you whether an up-to-date folio exists in that file’s i_pages — mincore_page() calls filemap_get_incore_folio(). A page can be cache-resident with no PTE of yours pointing at it, and mincore() will still report it present.
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 and address_space — the near-title sibling, and the one to read alongside this note. It owns the VFS-side seam: what every address_space_operations method must guarantee, which lock is held when each runs, and how a filesystem installs its vtable. This note owns the indexing structure underneath. Neither re-derives the other.
The Page Cache — the memory-behaviour view: how much RAM, dirty thresholds, reclaim pressure, /proc/meminfo semantics.
Page Table Entries and Hardware Flags — the PTE that maps a cached folio, as opposed to the slot that caches it. The Shared_Clean / Private_Dirty measurements above have their bit-level explanation there.
Readahead — the policy that decides how many slots to fill ahead of demand; the mincore() ramp measured above is its output.
The Maple Tree and VMA Lookup — the interval-indexed counterpart structure, and the same rbtree-versus-XArray distinction one level up: i_mmap, the other tree in struct address_space, is the file-backed reverse map and is an interval structure for the same reason.
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.