vault

MGLRU Generations and Aging

14 min read

MGLRU Generations and Aging

In the Multi-Generational LRU (MGLRU), evictable pages in each lruvec (the per-memory-cgroup, per-NUMA-node reclaim unit) are partitioned into a small sliding window of generations ordered by access recency. The youngest generation’s sequence number is held in lrugen->max_seq, the oldest in lrugen->min_seq[], and both are monotonically increasing 64-bit counters; the window holds between MIN_NR_GENS (2) and MAX_NR_GENS (4) live generations (include/linux/mmzone.h, v6.12). Aging is the producer half of reclaim: it scans for recently-accessed pages, promotes the hot ones to the youngest generation, and increments max_seq to mint a new youngest generation — implicitly demoting everything that was not promoted one step toward the oldest generation, where eviction drains them. Each generation is further subdivided into tiers by access frequency, and a refault-feedback loop decides which tiers to protect. This note dissects that machinery; for orientation read Multi-Generational LRU first, and for the scanning details read MGLRU Page Table Walks.

Mental Model — A Numbered Sliding Window

flowchart LR
  subgraph LV["one lruvec — struct lru_gen_folio"]
    direction LR
    G3["gen = max_seq % 4<br/>YOUNGEST<br/>(just promoted / faulted)"]
    G2["gen<br/>(active)"]
    G1["gen<br/>(inactive)"]
    G0["gen = min_seq % 4<br/>OLDEST<br/>(eviction drains here)"]
    G3 --> G2 --> G1 --> G0
  end
  AGE["AGING:<br/>find young PTEs,<br/>promote to G3,<br/>then max_seq++"]
  EVI["EVICTION:<br/>reclaim from G0,<br/>then min_seq++<br/>when G0 empties"]
  AGE -->|"produces"| G3
  G0 -->|"consumes"| EVI

The generation window of a single lruvec. What it shows: at most MAX_NR_GENS = 4 generations are live at once. A page’s generation is an index gen in [0, 3] computed as seq % MAX_NR_GENS; the youngest generation is max_seq % 4 and the oldest is min_seq % 4. Aging promotes hot pages into the youngest generation and bumps max_seq (creating a new youngest slot and shifting the window right); eviction reclaims from the oldest generation and bumps min_seq when it empties (shifting the window’s tail right). The insight to take: because max_seq and min_seq only ever increase, demotion is free — a page that is never re-promoted simply finds itself in an older generation as max_seq advances around it, with no per-page list surgery. The classic LRU’s explicit active→inactive demotion is replaced by counter arithmetic.

The two-generation minimum (MIN_NR_GENS) exists for a precise reason that the source comments spell out: the aging “needs to check the accessed bit at least twice before handing this page over to the eviction. The first check takes care of the accessed bit set on the initial fault; the second check makes sure this page hasn’t been used since then. This process, AKA second chance, requires a minimum of two generations” (mmzone.h). The four-generation maximum gives “twice the number of categories of the active/inactive LRU when keeping track of accesses through page tables,” at the cost of order_base_2(MAX_NR_GENS+1) bits in folio->flags.

min_seq, max_seq, and the gen Counter

Three counters define the window per lruvec (design doc):

  • max_seq — “the youngest generation number … for both anon and file types as they are aged on an equal footing.” A single value: anonymous and file pages share the youngest generation.
  • min_seq[ANON_AND_FILE] — “the oldest generation numbers … stored … separately for anon and file types as clean file pages can be evicted regardless of swap constraints.” Two values, because file and anonymous reclaim proceed at different rates. “Normally anon and file min_seq are in sync. But if swapping is constrained, e.g., out of swap space, file min_seq is allowed to advance and leave anon min_seq behind” (mmzone.h).
  • The per-page gen counter — packed into folio->flags. “The gen counter in folio->flags stores gen+1 while a page is on one of lrugen->folios[]. Otherwise it stores 0.” So a stored value in [1, MAX_NR_GENS] means “on generation gen,” and 0 means “not on an MGLRU list.” Storing gen+1 rather than gen lets 0 be the unambiguous off-list sentinel.

The generation index used to subscript the per-lruvec arrays is seq % MAX_NR_GENS. Because the sequence numbers are monotonic but the array has only four slots, the window wraps around the four slots like a ring buffer; the kernel uses the sequence numbers (not the wrapped indices) for all ordering comparisons, so wraparound of the index never confuses recency.

The lru_gen_folio Structure

All of a generation window’s state lives in one structure embedded in each lruvec. Here is the verbatim definition from v6.12 (mmzone.h):

struct lru_gen_folio {
	/* the aging increments the youngest generation number */
	unsigned long max_seq;
	/* the eviction increments the oldest generation numbers */
	unsigned long min_seq[ANON_AND_FILE];
	/* the birth time of each generation in jiffies */
	unsigned long timestamps[MAX_NR_GENS];
	/* the multi-gen LRU lists, lazily sorted on eviction */
	struct list_head folios[MAX_NR_GENS][ANON_AND_FILE][MAX_NR_ZONES];
	/* the multi-gen LRU sizes, eventually consistent */
	long nr_pages[MAX_NR_GENS][ANON_AND_FILE][MAX_NR_ZONES];
	/* the exponential moving average of refaulted */
	unsigned long avg_refaulted[ANON_AND_FILE][MAX_NR_TIERS];
	/* the exponential moving average of evicted+protected */
	unsigned long avg_total[ANON_AND_FILE][MAX_NR_TIERS];
	/* the first tier doesn't need protection, hence the minus one */
	unsigned long protected[NR_HIST_GENS][ANON_AND_FILE][MAX_NR_TIERS - 1];
	/* can be modified without holding the LRU lock */
	atomic_long_t evicted[NR_HIST_GENS][ANON_AND_FILE][MAX_NR_TIERS];
	atomic_long_t refaulted[NR_HIST_GENS][ANON_AND_FILE][MAX_NR_TIERS];
	/* whether the multi-gen LRU is enabled */
	bool enabled;
	/* the memcg generation this lru_gen_folio belongs to */
	u8 gen;
	/* the list segment this lru_gen_folio belongs to */
	u8 seg;
	/* per-node lru_gen_folio list for global reclaim */
	struct hlist_nulls_node list;
};

Walking the load-bearing fields:

  • max_seq, min_seq[] — the window counters described above.
  • timestamps[MAX_NR_GENS] — the birth time of each generation in jiffies. This is what min_ttl_ms working-set protection reads (see Multi-Generational LRU): if the oldest generation’s timestamp is younger than min_ttl_ms ago, the lruvec is protected from eviction.
  • folios[MAX_NR_GENS][ANON_AND_FILE][MAX_NR_ZONES] — the actual lists of pages, indexed by generation × type × zone. This three-dimensional indexing is why MGLRU can keep anon and file separate (for swappiness balancing) and zone-aware (so a high-order or zone-constrained allocation can reclaim from the right zone). The comment “lazily sorted on eviction” matters: pages are not eagerly re-sorted into the right generation when their gen counter changes; the eviction path sorts a page into its correct generation when it reaches it (see Eviction below).
  • nr_pages[...] — page counts per (gen, type, zone), “eventually consistent” and able to go “transiently negative when reset_batch_size() is pending” because aging batches its updates.
  • avg_refaulted, avg_total, protected, evicted, refaulted — the per-tier statistics that drive the PID feedback loop (next section). evicted and refaulted are atomic_long_t because, as the comment notes, they “can be modified without holding the LRU lock” — refaults are recorded on the fault path, which must not contend on the reclaim lock.
  • gen, seg, list — these belong to the memcg LRU (an LRU of memcgs for global reclaim), not the per-page generations; gen/seg place this lru_gen_folio in the old/young memcg generation and its head/tail/default segment. See the Memcg LRU note below.

The relevant macros, also verbatim (mmzone.h):

#define MIN_NR_GENS		2U
#define MAX_NR_GENS		4U
#define MAX_NR_TIERS		4U

Aging: Producing Young Generations

Aging is triggered when the window is about to run short — “it increments max_seq when max_seq-min_seq+1 approaches MIN_NR_GENS” (design doc). In other words, when only the bare minimum of generations remain, the producer must make a fresh one or eviction will have nothing cold to consume.

The mechanism, step by step (design doc):

  1. Promote hot pages. Aging finds pages “accessed through page tables” and promotes them to the youngest generation. It locates young PTEs two ways — full page-table walks and rmap-driven look-around — both detailed in MGLRU Page Table Walks. For each young PTE found, “the aging clears the accessed bit and updates the gen counter of the page mapped by this PTE to (max_seq%MAX_NR_GENS)+1.” Clearing the accessed bit is the “second chance” reset: the next pass can now tell whether the page is touched again.
  2. Increment max_seq. After a full page-table-walk pass, “it increments max_seq,” creating a brand-new youngest generation slot.
  3. Implicit demotion. Incrementing max_seq is exactly what demotes the cold pages: “the demotion of cold pages happens consequently when it increments max_seq.” No page is moved to do this — the pages that were not re-promoted simply now sit one generation older relative to the advanced max_seq. This is the key efficiency over the classic LRU, which must physically move pages between active and inactive lists.

Because aging promotes only pages it positively observes as young, and demotes the rest for free by advancing the counter, the per-pass cost is proportional to the number of hot pages and the cost of the scan — not to the total resident set. That is the whole point: cheap, periodic, batched aging instead of expensive per-page reclaim-time rmap chases.

Eviction: Consuming Old Generations

Eviction is the consumer and lives in the reclaim path; the generation-bookkeeping parts relevant here are:

  • It “increments min_seq when lrugen->folios[] indexed by min_seq%MAX_NR_GENS becomes empty” — i.e. once the oldest generation is fully drained, the tail of the window slides forward (design doc).
  • It performs the lazy sort promised by the folios[] comment: “the eviction sorts a page according to its gen counter if the aging has found this page accessed through page tables and updated its gen counter.” So a page the aging promoted (by writing a younger gen into folio->flags) but did not physically move is moved to its correct generation only when eviction reaches it — deferring the list work to the moment it is needed.
  • It can give a frequently-used file page another reprieve: “It also moves a page to the next generation, i.e., min_seq+1, if this page was accessed multiple times through file descriptors and the feedback loop has detected outlying refaults from the tier this page is in.”

To choose which type to evict, eviction “first compares min_seq[] to select the older type. If both types are equally old, it selects the one whose first tier has a lower refault percentage. The first tier contains single-use unmapped clean pages, which are the best bet” (design doc) — clean file pages can be dropped with no I/O.

Tiers and Refault Feedback

Generations capture recency; tiers capture frequency, orthogonally, within a generation. The source comment is precise: “Each generation is divided into multiple tiers. A page accessed N times through file descriptors is in tier order_base_2(N)” (mmzone.h). So tier 0 is pages accessed 0–1 times, tier 1 is 2–3 times, tier 2 is 4–7 times, and so on, with MAX_NR_TIERS = 4 tiers.

The decisive property of tiers is that they are cheap to move between. “Unlike generations, tiers do not have dedicated lrugen->folios[]. In contrast to moving across generations, which requires the LRU lock, moving across tiers only involves atomic operations on folio->flags and therefore has a negligible cost in the buffered access path” (mmzone.h). A page records access-frequency promotions in its flag bits (PG_referenced, PG_workingset) without ever touching the contended reclaim lock — only generation moves need the lock.

Tiers feed a PID-controller refault loop. The kernel tracks, per tier per type, how many pages it evicted and how many of those refaulted (were faulted back in soon after — proof the eviction was premature). It keeps exponential moving averages (avg_refaulted, avg_total). In the eviction path, “comparisons of refaulted/(evicted+protected) from the first tier and the rest infer whether pages accessed multiple times through file descriptors are statistically hot and thus worth protecting” (mmzone.h). Tier 0 (single-use pages) is the baseline; if a higher tier refaults more than tier 0, its pages are statistically hot and get protected (moved to a younger generation rather than evicted). The protected[NR_HIST_GENS][ANON_AND_FILE][MAX_NR_TIERS - 1] array tracks exactly this — note the - 1: “the first tier doesn’t need protection, hence the minus one.” This is precisely the defense against the classic LRU’s failure mode of one-off I/O flooding out the working set: a burst of single-use reads stays in tier 0 and is evicted first, while genuinely re-read pages climb tiers and earn protection. LWN described this design as computing “per-tier refault rates and protecting higher-tier pages from reclaim if their refault rate exceeds tier 0’s rate” (LWN 856931).

The PID controller deliberately uses generations as its time domain, not the wall clock, “because a CPU can scan pages at different rates under varying memory pressure[, and] it calculates a moving average for each new generation to avoid being permanently locked in a suboptimal state” (design doc). The net effect is to “balance refault percentages between anon and file types proportional to the swappiness level” — MGLRU’s principled replacement for the blunt swappiness arbitration of the classic scanner (see Swappiness and Reclaim Balance).

The Memcg LRU (Generations of Cgroups)

A second, easily-confused use of the word “generation” appears in lru_gen_folio.gen/seg and in struct lru_gen_memcg: the memcg LRU, “a per-node LRU of memcgs … also an LRU of LRUs” (design doc). For global reclaim, the kernel needs to pick which control group to reclaim from; the memcg LRU orders memcgs into just two generations (old and young) per node, sharded across MEMCG_NR_BINS (8) bins for parallelism. By analogy to the page LRU: young/old memcgs are the counterparts to active/inactive, and incrementing a memcg’s max_seq is the counterpart to activation. The payoff is scalability: traversing memcgs during global reclaim improves “the best-case complexity from O(n) to O(1)” while keeping worst-case O(n), “therefore, on average, … a sublinear complexity.” The relevant macros are MEMCG_NR_GENS = 3 (three slots, only two valid generations — the third prevents a stale lockless read from wrapping a value of seq-1 into “young”) and MEMCG_NR_BINS = 8 (mmzone.h). This applies only to global reclaim; targeted memcg reclaim still uses mem_cgroup_iter().

Uncertain

Verify the exact promotion/demotion trigger events for the memcg LRU (the MEMCG_LRU_HEAD/TAIL/OLD/YOUNG operations and the seven events that trigger them) against the running 6.12/6.18 source if a reader needs that level of detail — they are documented in the mmzone.h comment block but were not independently traced through mm/vmscan.c during this write-up. Reason: cited from the header comment only. To resolve: read shrink_many() / shrink_node_memcgs() in mm/vmscan.c at the v6.12 tag. uncertain

Inspecting Generations at Runtime

The debugfs interface exposes the live generation state and lets you drive aging/eviction by hand (admin guide). /sys/kernel/debug/lru_gen accepts:

+ memcg_id node_id max_gen_nr [can_swap [force_scan]]   # run the aging up to a target youngest gen
- memcg_id node_id min_gen_nr [swappiness [nr_to_reclaim]]  # run the eviction down to a target oldest gen

Writing a + line forces the aging to produce generations (working-set estimation); writing a - line forces eviction to drain generations (proactive reclaim). Reading the file shows, per memcg and node, the current min_seq/max_seq and the per-generation page counts and birth times. /sys/kernel/debug/lru_gen_full adds the historical per-tier evicted/refaulted statistics when CONFIG_LRU_GEN_STATS=y. This is the canonical way to watch the aging move pages between generations and to verify the refault feedback in action.

Failure Modes and Subtleties

Transiently negative nr_pages. Because aging batches its accounting and applies it in reset_batch_size(), the per-generation nr_pages counters are only “eventually consistent” and can read negative momentarily. Code (and humans) reading them must not assume non-negativity at every instant.

Window starvation under no aging. If nothing triggers aging (e.g. an architecture without a hardware young bit and a workload that defeats rmap look-around), the window can fail to produce fresh young generations, degrading MGLRU’s recency resolution. This is why CONFIG_LRU_GEN_WALKS_MMU and the accessed-bit batching switches (0x0002/0x0004 in Multi-Generational LRU) matter for the page-table-walk path.

Tier inflation is bounded. Because a page’s tier is order_base_2(N), frequency growth is logarithmic — a page read a million times is tier ~20 in principle but the array caps at MAX_NR_TIERS = 4, so the highest tier is a catch-all. The feedback loop only needs to distinguish “single-use” (tier 0) from “re-used” (tiers 1+), so four tiers suffice.

Confusing the two “generations.” The single biggest reading hazard: page generations (MAX_NR_GENS = 4, recency of pages within an lruvec) versus memcg generations (MEMCG_NR_GENS = 3, recency of whole cgroups for global reclaim). They are separate mechanisms that share a name.

See Also

Graph View