Lines Matching +full:first +full:- +full:generation

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.
45 attainable. Specifically, pages in the same generation can be
51 -----------
83 ``lruvec``. The youngest generation number is stored in
84 ``lrugen->max_seq`` for both anon and file types as they are aged on
85 an equal footing. The oldest generation numbers are stored in
86 ``lrugen->min_seq[]`` separately for anon and file types as clean file
90 Generation numbers are truncated into ``order_base_2(MAX_NR_GENS+1)``
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.
98 Each generation is divided into multiple tiers. A page accessed ``N``
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
117 generation when it finds them accessed through page tables; the
120 young PTEs. For the former, it iterates ``lruvec_memcg()->mm_list``
129 --------
131 increments ``min_seq`` when ``lrugen->folios[]`` indexed by
133 evict from, it first compares ``min_seq[]`` to select the older type.
134 If both types are equally old, it selects the one whose first tier has
135 a lower refault percentage. The first tier contains single-use
139 moves a page to the next generation, i.e., ``min_seq+1``, if this page
142 this end, the feedback loop uses the first tier as the baseline, for
146 ----------------------
147 Each generation is timestamped at birth. If ``lru_gen_min_ttl`` is
149 generation was born within ``lru_gen_min_ttl`` milliseconds. In other
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
216 same generation.
221 generation to avoid being permanently locked in a suboptimal state.
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
244    the old generation) and improves parallelism;
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;