[PATCH v7 05/12] mm: multigenerational LRU: minimal implementation

[Johannes Weiner]

Hi Yu,

Thanks for restructuring this from the last version. It's easier to
learn the new model when you start out with the bare bones, then let
optimizations and self-contained features follow later.

On Tue, Feb 08, 2022 at 01:18:55AM -0700, Yu Zhao wrote:
> To avoid confusions, the terms "promotion" and "demotion" will be
> applied to the multigenerational LRU, as a new convention; the terms
> "activation" and "deactivation" will be applied to the active/inactive
> LRU, as usual.
> 
> The aging produces young generations. Given an lruvec, it increments
> max_seq when max_seq-min_seq+1 approaches MIN_NR_GENS. The aging
> promotes hot pages to the youngest generation when it finds them
> accessed through page tables; the demotion of cold pages happens
> consequently when it increments max_seq. Since the aging is only
> interested in hot pages, its complexity is O(nr_hot_pages). Promotion
> in the aging path doesn't require any LRU list operations, only the
> updates of the gen counter and lrugen->nr_pages[]; demotion, unless
> as the result of the increment of max_seq, requires LRU list
> operations, e.g., lru_deactivate_fn().

I'm having trouble with this changelog. It opens with a footnote and
summarizes certain aspects of the implementation whose importance to
the reader aren't entirely clear at this time.

It would be better to start with a high-level overview of the problem
and how this algorithm solves it. How the reclaim algorithm needs to
find the page that is most suitable for eviction and to signal when
it's time to give up and OOM. Then explain how grouping pages into
multiple generations accomplishes that - in particular compared to the
current two use-once/use-many lists.

Explain the problem of MMU vs syscall references, and how tiering
addresses this.

Explain the significance of refaults and how the algorithm responds to
them. Not in terms of which running averages are updated, but in terms
of user-visible behavior ("will start swapping (more)" etc.)

Express *intent*, how it's supposed to behave wrt workloads and memory
pressure. The code itself will explain the how, its complexity etc.

Most reviewers will understand the fundamental challenges of page
reclaim. The difficulty is matching individual aspects of the problem
space to your individual components and design choices you have made.

Let us in on that thinking, please ;)

> @@ -892,6 +892,50 @@ config ANON_VMA_NAME
>  	  area from being merged with adjacent virtual memory areas due to the
>  	  difference in their name.
>  
> +# multigenerational LRU {
> +config LRU_GEN
> +	bool "Multigenerational LRU"
> +	depends on MMU
> +	# the following options can use up the spare bits in page flags
> +	depends on !MAXSMP && (64BIT || !SPARSEMEM || SPARSEMEM_VMEMMAP)
> +	help
> +	  A high performance LRU implementation for memory overcommit. See
> +	  Documentation/admin-guide/mm/multigen_lru.rst and
> +	  Documentation/vm/multigen_lru.rst for details.

These files don't exist at this time, please introduce them before or
when referencing them. If they document things introduced later in the
patchset, please start with a minimal version of the file and update
it as you extend the algorithm and add optimizations etc.

It's really important to only reference previous patches, not later
ones. This allows reviewers to read the patches linearly.  Having to
search for missing pieces in patches you haven't looked at yet is bad.

> +config NR_LRU_GENS
> +	int "Max number of generations"
> +	depends on LRU_GEN
> +	range 4 31
> +	default 4
> +	help
> +	  Do not increase this value unless you plan to use working set
> +	  estimation and proactive reclaim to optimize job scheduling in data
> +	  centers.
> +
> +	  This option uses order_base_2(N+1) bits in page flags.
> +
> +config TIERS_PER_GEN
> +	int "Number of tiers per generation"
> +	depends on LRU_GEN
> +	range 2 4
> +	default 4
> +	help
> +	  Do not decrease this value unless you run out of spare bits in page
> +	  flags, i.e., you see the "Not enough bits in page flags" build error.
> +
> +	  This option uses N-2 bits in page flags.

Linus had pointed out that we shouldn't ask these questions of the
user. How do you pick numbers here? I'm familiar with workingset
estimation and proactive reclaim usecases but I wouldn't know.

Even if we removed the config option and hardcoded the number, this is
a question for kernel developers: What does "4" mean? How would
behavior differ if it were 3 or 5 instead? Presumably there is some
sort of behavior gradient. "As you increase the number of
generations/tiers, the user-visible behavior of the kernel will..."
This should really be documented.

I'd also reiterate Mel's point: Distribution kernels need to support
the full spectrum of applications and production environments. Unless
using non-defaults it's an extremely niche usecase (like compiling out
BUG() calls) compile-time options are not the right choice. If we do
need a tunable, it could make more sense to have a compile time upper
limit (to determine page flag space) combined with a runtime knob?

Thanks!