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 -----------
52 The protection of hot pages and the selection of cold pages are based
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
87 pages can be evicted regardless of swap constraints. These three
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
116 ``MIN_NR_GENS``. The aging promotes hot pages to the youngest
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 ---------------------
191 promotes hot pages. If the scan was done cacheline efficiently, it
196 -------------
202 PMD has a sufficient number of hot pages, its address is placed in the
208 which may yield hot pages anyway. Parameters of the filter itself can
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;
267 inserting hot densely populated page tables to the Bloom filters.