[LSF/MM/BPF TOPIC] Page cache tracking with the Maple Tree

[LSF/MM/BPF TOPIC] Page cache tracking with the Maple Tree

[Liam R. Howlett]

Hi,

The page cache currently uses a radix tree to store folios.  There are several
well-known deficiencies to this approach:
 - Inefficient representation of large folios
 - Inefficient representation of sparsely accessed files
 - Poor cache locality
 - Supports 3 search marks

The Maple Tree solves these problems more efficiently than the XArray.  In this
session, I'd like to discuss what needs to happen to change from using the
XArray to the Maple Tree for the page cache.

The Maple Tree needs some enhancements:
 - New node type to efficiently support entries of length of 1
 - New node type to support marks
 - Searching and iterating over marks
 - Support for purging shadow entries from the page cache

The motivation, beyond potential performance gains and memory footprint,
is to support more features natively in the data structure.

Thanks,
Liam

Re: [LSF/MM/BPF TOPIC] Page cache tracking with the Maple Tree

[Matthew Wilcox]

On Tue, Feb 24, 2026 at 12:10:26PM -0500, Liam R. Howlett wrote:
> The Maple Tree needs some enhancements:
>  - Support for purging shadow entries from the page cache

Liam and I hd some preliminary discussions yesterday around this
and we'd like some feedback if anyone has time before LSFMM.

For those who aren't aware, when a folio falls off the end of the
LRU list, we store a shadow entry in the page cache in its place
so that if we access that page again, we know where to put its folio in
the LRU list.

But this creates a problem (documented in mm/workingset.c) where
we can fill up memory with shadow entries.  Currently, we embed a
list_head in xa_node and add nodes which contain only shadow entries
to a list which can be walked by a shrinker when we're low on memory.
Ideally we wouldn't do that with the maple tree.  There are a few
options.

The first question we have is whether it's best to keep nodes around to
wait for a shrinker to kick in.  Was any experimentation done to
see whether eagerly freeing a node that contains only shadow entries
has a bad effect on performance?

The second idea we talked about is that the maple tree is much more
flexible than the radix tree.  Having even a single folio in a node pins
the entire node, so it's "free" to keep the shadow entries in that node
around.  But with the maple tree, we can be much more granular and
delete shadow entries in arbitrary positions.  So we could (for example)
keep track of inodes which contain shadow entries and purge shadow
entries when they reach, say, 10% of the number of pages.  Or 1000
entries, or some other threshold.

The third idea is that instead of having an injected list_head that we
keep a tree pointing to inodes (or even just maple tree nodes which
contain a lot of shadow entries).  That's not how list_lru works today,
so a certain amount of development work would need to be done.

Liam, anything I missed?