Maple Tree Work 2023/11

[Matthew Wilcox]

On Wed, Nov 01, 2023 at 01:36:10PM -0400, Liam R. Howlett wrote:
>  - Search Marks
>  	To complete the features that xarray support, the maple tree
> 	needs to support search marks.  Marks will replace the gap
> 	tracking in a new node type complete with searching for a
> 	specific tag from the top-level to the leaves; just like the
> 	gaps that exist in the allocation nodes.  It will probably need
> 	two new node types (range and dense). Dense with 29 pointers,
> 	range64 with 15 pointers.

 - Pruning trees under memory pressure
	For the page cache, we support retaining workingset information in
	the tree after the folio has been swapped out ("shadow entries").
	The problem with this is that trees full of stale workingset
	information can occupy a large amount of memory.  For the radix
	tree, this was solved by putting nodes which contained only
	shadow entries on the 'shadow_nodes' list in mm/workingset.c.
	We might take a different approach for maple tree, such as
	putting entire trees that contain many shadow entries on an LRU
	list and pruning the entire tree of its shadow entries (or some
	high percentage of its shadow entries) under memory pressure.