Lines Matching +full:page +full:- +full:based

1 .. SPDX-License-Identifier: GPL-2.0
4 Multi-Gen LRU
6 The multi-gen LRU is an alternative LRU implementation that optimizes
7 page reclaim and improves performance under memory pressure. Page
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
30 accessed bit. A rmap walk targets a single page and does not try to
31 profit from discovering a young PTE. A page table walk can sweep all
41 choices; thus self-correction is necessary.
43 The benefits of simple self-correcting heuristics are self-evident.
46 categorized based on additional factors, and a feedback loop can
51 -----------
52 The protection of hot pages and the selection of cold pages are based
53 on page access channels and patterns. There are two access channels:
55 * Accesses through page tables
65    applications usually do not prepare themselves for major page
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
95 within ``[1, MAX_NR_GENS]`` while a page is on one of
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
119 ``max_seq``. The aging uses page table walks and rmap walks to find
120 young PTEs. For the former, it iterates ``lruvec_memcg()->mm_list``
126 page mapped by this PTE to ``(max_seq%MAX_NR_GENS)+1``.
129 --------
131 increments ``min_seq`` when ``lrugen->folios[]`` indexed by
135 a lower refault percentage. The first tier contains single-use
137 page according to its gen counter if the aging has found this page
138 accessed through page tables and updated its gen counter. It also
139 moves a page to the next generation, i.e., ``min_seq+1``, if this page
141 loop has detected outlying refaults from the tier this page is in. To
146 ----------------------
154 This time-based approach has the following advantages:
161 ------------------
166 A page table walker iterates ``lruvec_memcg()->mm_list`` and calls
168 PTEs. When multiple page table walkers iterate the same list, each of
172 Page table walkers ignore any misplaced pages, e.g., if an
174 ignored when the current memcg is under reclaim. Similarly, page table
178 context switches so that page table walkers can skip processes that
182 ---------------------
183 Searching the rmap for PTEs mapping each page on an LRU list (to test
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
260 * Page table walks via ``mm_struct`` list
264 The aging and the eviction form a producer-consumer model;
266 generations. Within the aging, rmap walks drive page table walks by
267 inserting hot densely populated page tables to the Bloom filters.