270 lines · plain
1.. SPDX-License-Identifier: GPL-2.02 3=============4Multi-Gen LRU5=============6The multi-gen LRU is an alternative LRU implementation that optimizes7page reclaim and improves performance under memory pressure. Page8reclaim decides the kernel's caching policy and ability to overcommit9memory. It directly impacts the kswapd CPU usage and RAM efficiency.10 11Design overview12===============13Objectives14----------15The design objectives are:16 17* Good representation of access recency18* Try to profit from spatial locality19* Fast paths to make obvious choices20* Simple self-correcting heuristics21 22The representation of access recency is at the core of all LRU23implementations. In the multi-gen LRU, each generation represents a24group of pages with similar access recency. Generations establish a25(time-based) common frame of reference and therefore help make better26choices, e.g., between different memcgs on a computer or different27computers in a data center (for job scheduling).28 29Exploiting spatial locality improves efficiency when gathering the30accessed bit. A rmap walk targets a single page and does not try to31profit from discovering a young PTE. A page table walk can sweep all32the young PTEs in an address space, but the address space can be too33sparse to make a profit. The key is to optimize both methods and use34them in combination.35 36Fast paths reduce code complexity and runtime overhead. Unmapped pages37do not require TLB flushes; clean pages do not require writeback.38These facts are only helpful when other conditions, e.g., access39recency, are similar. With generations as a common frame of reference,40additional factors stand out. But obvious choices might not be good41choices; thus self-correction is necessary.42 43The benefits of simple self-correcting heuristics are self-evident.44Again, with generations as a common frame of reference, this becomes45attainable. Specifically, pages in the same generation can be46categorized based on additional factors, and a feedback loop can47statistically compare the refault percentages across those categories48and infer which of them are better choices.49 50Assumptions51-----------52The protection of hot pages and the selection of cold pages are based53on page access channels and patterns. There are two access channels:54 55* Accesses through page tables56* Accesses through file descriptors57 58The protection of the former channel is by design stronger because:59 601. The uncertainty in determining the access patterns of the former61 channel is higher due to the approximation of the accessed bit.622. The cost of evicting the former channel is higher due to the TLB63 flushes required and the likelihood of encountering the dirty bit.643. The penalty of underprotecting the former channel is higher because65 applications usually do not prepare themselves for major page66 faults like they do for blocked I/O. E.g., GUI applications67 commonly use dedicated I/O threads to avoid blocking rendering68 threads.69 70There are also two access patterns:71 72* Accesses exhibiting temporal locality73* Accesses not exhibiting temporal locality74 75For the reasons listed above, the former channel is assumed to follow76the former pattern unless ``VM_SEQ_READ`` or ``VM_RAND_READ`` is77present, and the latter channel is assumed to follow the latter78pattern unless outlying refaults have been observed.79 80Workflow overview81=================82Evictable pages are divided into multiple generations for each83``lruvec``. The youngest generation number is stored in84``lrugen->max_seq`` for both anon and file types as they are aged on85an equal footing. The oldest generation numbers are stored in86``lrugen->min_seq[]`` separately for anon and file types as clean file87pages can be evicted regardless of swap constraints. These three88variables are monotonically increasing.89 90Generation numbers are truncated into ``order_base_2(MAX_NR_GENS+1)``91bits in order to fit into the gen counter in ``folio->flags``. Each92truncated generation number is an index to ``lrugen->folios[]``. The93sliding window technique is used to track at least ``MIN_NR_GENS`` and94at most ``MAX_NR_GENS`` generations. The gen counter stores a value95within ``[1, MAX_NR_GENS]`` while a page is on one of96``lrugen->folios[]``; otherwise it stores zero.97 98Each generation is divided into multiple tiers. A page accessed ``N``99times through file descriptors is in tier ``order_base_2(N)``. Unlike100generations, tiers do not have dedicated ``lrugen->folios[]``. In101contrast to moving across generations, which requires the LRU lock,102moving across tiers only involves atomic operations on103``folio->flags`` and therefore has a negligible cost. A feedback loop104modeled after the PID controller monitors refaults over all the tiers105from anon and file types and decides which tiers from which types to106evict or protect. The desired effect is to balance refault percentages107between anon and file types proportional to the swappiness level.108 109There are two conceptually independent procedures: the aging and the110eviction. They form a closed-loop system, i.e., the page reclaim.111 112Aging113-----114The aging produces young generations. Given an ``lruvec``, it115increments ``max_seq`` when ``max_seq-min_seq+1`` approaches116``MIN_NR_GENS``. The aging promotes hot pages to the youngest117generation when it finds them accessed through page tables; the118demotion of cold pages happens consequently when it increments119``max_seq``. The aging uses page table walks and rmap walks to find120young PTEs. For the former, it iterates ``lruvec_memcg()->mm_list``121and calls ``walk_page_range()`` with each ``mm_struct`` on this list122to scan PTEs, and after each iteration, it increments ``max_seq``. For123the latter, when the eviction walks the rmap and finds a young PTE,124the aging scans the adjacent PTEs. For both, on finding a young PTE,125the aging clears the accessed bit and updates the gen counter of the126page mapped by this PTE to ``(max_seq%MAX_NR_GENS)+1``.127 128Eviction129--------130The eviction consumes old generations. Given an ``lruvec``, it131increments ``min_seq`` when ``lrugen->folios[]`` indexed by132``min_seq%MAX_NR_GENS`` becomes empty. To select a type and a tier to133evict from, it first compares ``min_seq[]`` to select the older type.134If both types are equally old, it selects the one whose first tier has135a lower refault percentage. The first tier contains single-use136unmapped clean pages, which are the best bet. The eviction sorts a137page according to its gen counter if the aging has found this page138accessed through page tables and updated its gen counter. It also139moves a page to the next generation, i.e., ``min_seq+1``, if this page140was accessed multiple times through file descriptors and the feedback141loop has detected outlying refaults from the tier this page is in. To142this end, the feedback loop uses the first tier as the baseline, for143the reason stated earlier.144 145Working set protection146----------------------147Each generation is timestamped at birth. If ``lru_gen_min_ttl`` is148set, an ``lruvec`` is protected from the eviction when its oldest149generation was born within ``lru_gen_min_ttl`` milliseconds. In other150words, it prevents the working set of ``lru_gen_min_ttl`` milliseconds151from getting evicted. The OOM killer is triggered if this working set152cannot be kept in memory.153 154This time-based approach has the following advantages:155 1561. It is easier to configure because it is agnostic to applications157 and memory sizes.1582. It is more reliable because it is directly wired to the OOM killer.159 160``mm_struct`` list161------------------162An ``mm_struct`` list is maintained for each memcg, and an163``mm_struct`` follows its owner task to the new memcg when this task164is migrated.165 166A page table walker iterates ``lruvec_memcg()->mm_list`` and calls167``walk_page_range()`` with each ``mm_struct`` on this list to scan168PTEs. When multiple page table walkers iterate the same list, each of169them gets a unique ``mm_struct``, and therefore they can run in170parallel.171 172Page table walkers ignore any misplaced pages, e.g., if an173``mm_struct`` was migrated, pages left in the previous memcg will be174ignored when the current memcg is under reclaim. Similarly, page table175walkers will ignore pages from nodes other than the one under reclaim.176 177This infrastructure also tracks the usage of ``mm_struct`` between178context switches so that page table walkers can skip processes that179have been sleeping since the last iteration.180 181Rmap/PT walk feedback182---------------------183Searching the rmap for PTEs mapping each page on an LRU list (to test184and clear the accessed bit) can be expensive because pages from185different VMAs (PA space) are not cache friendly to the rmap (VA186space). For workloads mostly using mapped pages, searching the rmap187can incur the highest CPU cost in the reclaim path.188 189``lru_gen_look_around()`` exploits spatial locality to reduce the190trips into the rmap. It scans the adjacent PTEs of a young PTE and191promotes hot pages. If the scan was done cacheline efficiently, it192adds the PMD entry pointing to the PTE table to the Bloom filter. This193forms a feedback loop between the eviction and the aging.194 195Bloom filters196-------------197Bloom filters are a space and memory efficient data structure for set198membership test, i.e., test if an element is not in the set or may be199in the set.200 201In the eviction path, specifically, in ``lru_gen_look_around()``, if a202PMD has a sufficient number of hot pages, its address is placed in the203filter. In the aging path, set membership means that the PTE range204will be scanned for young pages.205 206Note that Bloom filters are probabilistic on set membership. If a test207is false positive, the cost is an additional scan of a range of PTEs,208which may yield hot pages anyway. Parameters of the filter itself can209control the false positive rate in the limit.210 211PID controller212--------------213A feedback loop modeled after the Proportional-Integral-Derivative214(PID) controller monitors refaults over anon and file types and215decides which type to evict when both types are available from the216same generation.217 218The PID controller uses generations rather than the wall clock as the219time domain because a CPU can scan pages at different rates under220varying memory pressure. It calculates a moving average for each new221generation to avoid being permanently locked in a suboptimal state.222 223Memcg LRU224---------225An memcg LRU is a per-node LRU of memcgs. It is also an LRU of LRUs,226since each node and memcg combination has an LRU of folios (see227``mem_cgroup_lruvec()``). Its goal is to improve the scalability of228global reclaim, which is critical to system-wide memory overcommit in229data centers. Note that memcg LRU only applies to global reclaim.230 231The basic structure of an memcg LRU can be understood by an analogy to232the active/inactive LRU (of folios):233 2341. It has the young and the old (generations), i.e., the counterparts235 to the active and the inactive;2362. The increment of ``max_seq`` triggers promotion, i.e., the237 counterpart to activation;2383. Other events trigger similar operations, e.g., offlining an memcg239 triggers demotion, i.e., the counterpart to deactivation.240 241In terms of global reclaim, it has two distinct features:242 2431. Sharding, which allows each thread to start at a random memcg (in244 the old generation) and improves parallelism;2452. Eventual fairness, which allows direct reclaim to bail out at will246 and reduces latency without affecting fairness over some time.247 248In terms of traversing memcgs during global reclaim, it improves the249best-case complexity from O(n) to O(1) and does not affect the250worst-case complexity O(n). Therefore, on average, it has a sublinear251complexity.252 253Summary254-------255The multi-gen LRU (of folios) can be disassembled into the following256parts:257 258* Generations259* Rmap walks260* Page table walks via ``mm_struct`` list261* Bloom filters for rmap/PT walk feedback262* PID controller for refault feedback263 264The aging and the eviction form a producer-consumer model;265specifically, the latter drives the former by the sliding window over266generations. Within the aging, rmap walks drive page table walks by267inserting hot densely populated page tables to the Bloom filters.268Within the eviction, the PID controller uses refaults as the feedback269to select types to evict and tiers to protect.270