Documentation/mm/multigen_lru.rst

1 .. SPDX-License-Identifier: GPL-2.0
4 Multi-Gen LRU
6 The multi-gen LRU is an alternative LRU implementation that optimizes
14 ----------
20 * Simple self-correcting heuristics
23 implementations. In the multi-gen LRU, each generation represents a
25 (time-based) common frame of reference and therefore help make better
41 choices; thus self-correction is necessary.
43 The benefits of simple self-correcting heuristics are self-evident.
51 -----------
58 The protection of the former channel is by design stronger because:
61    channel is higher due to the approximation of the accessed bit.
62 2. The cost of evicting the former channel is higher due to the TLB
64 3. The penalty of underprotecting the former channel is higher because
75 For the reasons listed above, the former channel is assumed to follow
77 present, and the latter channel is assumed to follow the latter
84 ``lrugen->max_seq`` for both anon and file types as they are aged on
86 ``lrugen->min_seq[]`` separately for anon and file types as clean file
91 bits in order to fit into the gen counter in ``folio->flags``. Each
92 truncated generation number is an index to ``lrugen->folios[]``. The
96 ``lrugen->folios[]``; otherwise it stores zero.
100 generations, tiers do not have dedicated ``lrugen->folios[]``. In
103 ``folio->flags`` and therefore has a negligible cost. A feedback loop
110 eviction. They form a closed-loop system, i.e., the page reclaim.
113 -----
115 increments ``max_seq`` when ``max_seq-min_seq+1`` approaches
120 young PTEs. For the former, it iterates ``lruvec_memcg()->mm_list``
129 --------
131 increments ``min_seq`` when ``lrugen->folios[]`` indexed by
135 a lower refault percentage. The first tier contains single-use
146 ----------------------
154 This time-based approach has the following advantages:
161 ------------------
166 A page table walker iterates ``lruvec_memcg()->mm_list`` and calls
182 ---------------------
196 -------------
212 --------------
213 A feedback loop modeled after the Proportional-Integral-Derivative
224 ---------
225 An memcg LRU is a per-node LRU of memcgs. It is also an LRU of LRUs,
228 global reclaim, which is critical to system-wide memory overcommit in
249 best-case complexity from O(n) to O(1) and does not affect the
250 worst-case complexity O(n). Therefore, on average, it has a sublinear
254 -------
255 The multi-gen LRU (of folios) can be disassembled into the following
264 The aging and the eviction form a producer-consumer model;