Multi-Gen LRU

개요와 설계 목표

Multi-gen LRU는 page reclaim을 최적화하고 memory pressure 아래의 성능을 개선하는 대체 LRU 구현입니다. Page reclaim은 kernel의 caching policy와 memory overcommit 능력을 결정하며 `kswapd` CPU 사용량과 RAM 효율에 직접 영향을 줍니다.

설계 목표는 다음과 같습니다.

• 접근 최신성을 잘 표현할 것
• Spatial locality를 활용할 것
• 명백한 선택에는 fast path를 사용할 것
• 단순하고 self-correcting한 heuristic을 사용할 것

접근 최신성의 표현은 모든 LRU 구현의 중심입니다. Multi-gen LRU에서 각 generation은 접근 최신성이 비슷한 page group을 나타냅니다. Generation은 시간 기반의 공통 기준틀을 만들기 때문에 한 computer의 서로 다른 memcg, 또는 job scheduling을 위한 data center의 서로 다른 computer 사이에서도 더 나은 선택을 돕습니다.

Spatial locality를 이용하면 accessed bit를 수집하는 효율이 좋아집니다. Rmap walk는 page 하나를 대상으로 하며 young PTE를 발견해도 주변을 활용하지 않습니다. Page-table walk는 address space의 모든 young PTE를 훑을 수 있지만 address space가 너무 sparse하면 이득이 없습니다. 핵심은 두 방법을 모두 최적화하고 조합하는 것입니다.

Fast path는 code complexity와 runtime overhead를 줄입니다. Unmapped page는 TLB flush가 필요 없고 clean page는 writeback이 필요 없습니다. 다만 접근 최신성 같은 다른 조건이 비슷할 때만 이런 사실이 유용합니다. Generation이라는 공통 기준이 있으면 추가 요인이 두드러집니다. 그러나 명백해 보이는 선택이 좋은 선택이 아닐 수도 있으므로 self-correction이 필요합니다.

단순한 self-correcting heuristic의 장점은 분명합니다. Generation이라는 공통 기준틀 덕분에 같은 generation의 page를 추가 요인으로 분류하고, feedback loop가 category별 refault 비율을 통계적으로 비교해 어느 category가 더 나은 선택인지 추론할 수 있습니다.

.. SPDX-License-Identifier: GPL-2.0

=============
Multi-Gen LRU
=============
The multi-gen LRU is an alternative LRU implementation that optimizes
page reclaim and improves performance under memory pressure. Page
reclaim decides the kernel's caching policy and ability to overcommit
memory. It directly impacts the kswapd CPU usage and RAM efficiency.

Design overview
===============
Objectives
----------
The design objectives are:

* Good representation of access recency
* Try to profit from spatial locality
* Fast paths to make obvious choices
* Simple self-correcting heuristics

The representation of access recency is at the core of all LRU
implementations. In the multi-gen LRU, each generation represents a
group of pages with similar access recency. Generations establish a
(time-based) common frame of reference and therefore help make better
choices, e.g., between different memcgs on a computer or different
computers in a data center (for job scheduling).

Exploiting spatial locality improves efficiency when gathering the
accessed bit. A rmap walk targets a single page and does not try to
profit from discovering a young PTE. A page table walk can sweep all
the young PTEs in an address space, but the address space can be too
sparse to make a profit. The key is to optimize both methods and use
them in combination.

Fast paths reduce code complexity and runtime overhead. Unmapped pages
do not require TLB flushes; clean pages do not require writeback.
These facts are only helpful when other conditions, e.g., access
recency, are similar. With generations as a common frame of reference,
additional factors stand out. But obvious choices might not be good
choices; thus self-correction is necessary.

The benefits of simple self-correcting heuristics are self-evident.
Again, with generations as a common frame of reference, this becomes
attainable. Specifically, pages in the same generation can be
categorized based on additional factors, and a feedback loop can
statistically compare the refault percentages across those categories
and infer which of them are better choices.

접근 channel과 pattern에 대한 가정

Hot page 보호와 cold page 선택은 page-access channel과 pattern을 바탕으로 합니다. Access channel은 두 가지입니다.

• Page table을 통한 접근
• File descriptor를 통한 접근

설계상 page-table channel을 더 강하게 보호합니다.

• Accessed bit의 근사 때문에 page-table channel의 access pattern을 판별하는 불확실성이 더 큽니다.
• Page-table channel을 evict하면 TLB flush가 필요하고 dirty bit를 만날 가능성이 높아 비용이 더 큽니다.
• Application은 blocked I/O에 대비하듯 major page fault에 대비하지 않는 경우가 많아 page-table channel을 덜 보호했을 때의 penalty가 더 큽니다. 예를 들어 GUI application은 rendering thread가 막히지 않도록 전용 I/O thread를 흔히 사용합니다.

Access pattern도 두 가지입니다.

• Temporal locality를 보이는 접근
• Temporal locality를 보이지 않는 접근

앞의 이유로 page-table channel은 `VM_SEQ_READ`나 `VM_RAND_READ`가 없는 한 temporal locality pattern을 따른다고 가정합니다. File-descriptor channel은 특이한 refault가 관찰되지 않는 한 temporal locality가 없는 pattern을 따른다고 가정합니다.

Assumptions
-----------
The protection of hot pages and the selection of cold pages are based
on page access channels and patterns. There are two access channels:

* Accesses through page tables
* Accesses through file descriptors

The protection of the former channel is by design stronger because:

1. The uncertainty in determining the access patterns of the former
   channel is higher due to the approximation of the accessed bit.
2. The cost of evicting the former channel is higher due to the TLB
   flushes required and the likelihood of encountering the dirty bit.
3. The penalty of underprotecting the former channel is higher because
   applications usually do not prepare themselves for major page
   faults like they do for blocked I/O. E.g., GUI applications
   commonly use dedicated I/O threads to avoid blocking rendering
   threads.

There are also two access patterns:

* Accesses exhibiting temporal locality
* Accesses not exhibiting temporal locality

For the reasons listed above, the former channel is assumed to follow
the former pattern unless ``VM_SEQ_READ`` or ``VM_RAND_READ`` is
present, and the latter channel is assumed to follow the latter
pattern unless outlying refaults have been observed.

Generation, tier와 폐루프 workflow

각 `lruvec`에서 evict 가능한 page를 여러 generation으로 나눕니다. Anon과 file type은 동등하게 aging하므로 두 type의 youngest generation number를 `lrugen->max_seq` 하나에 저장합니다. Clean file page는 swap 제약과 관계없이 evict할 수 있으므로 oldest generation number는 anon과 file type별 `lrugen->min_seq[]`에 따로 저장합니다. 이 세 변수는 단조 증가합니다.

Generation number는 `folio->flags`의 gen counter에 들어가도록 `order_base_2(MAX_NR_GENS+1)` bit로 자릅니다. 잘린 generation number는 `lrugen->folios[]`의 index입니다. Sliding-window 기법으로 최소 `MIN_NR_GENS`, 최대 `MAX_NR_GENS` generation을 추적합니다. Page가 `lrugen->folios[]` 중 하나에 있으면 gen counter는 `[1, MAX_NR_GENS]` 범위 값을 저장하고, 그렇지 않으면 0을 저장합니다.

각 generation은 여러 tier로 나뉩니다. File descriptor를 통해 N번 접근한 page는 `order_base_2(N)` tier에 속합니다. Generation과 달리 tier에는 전용 `lrugen->folios[]`가 없습니다. Generation 사이 이동은 LRU lock이 필요하지만 tier 사이 이동은 `folio->flags`에 대한 atomic operation만 사용하므로 비용이 거의 없습니다. PID controller를 본뜬 feedback loop가 anon과 file type의 모든 tier에 걸친 refault를 관찰하고 어느 type의 어느 tier를 evict하거나 보호할지 결정합니다. 목표는 swappiness 수준에 비례해 anon과 file type의 refault 비율을 균형 있게 만드는 것입니다.

개념적으로 독립적인 procedure는 aging과 eviction 두 가지이며, 둘이 page reclaim이라는 closed-loop system을 이룹니다.

Workflow overview
=================
Evictable pages are divided into multiple generations for each
``lruvec``. The youngest generation number is stored in
``lrugen->max_seq`` for both anon and file types as they are aged on
an equal footing. The oldest generation numbers are stored in
``lrugen->min_seq[]`` separately for anon and file types as clean file
pages can be evicted regardless of swap constraints. These three
variables are monotonically increasing.

Generation numbers are truncated into ``order_base_2(MAX_NR_GENS+1)``
bits in order to fit into the gen counter in ``folio->flags``. Each
truncated generation number is an index to ``lrugen->folios[]``. The
sliding window technique is used to track at least ``MIN_NR_GENS`` and
at most ``MAX_NR_GENS`` generations. The gen counter stores a value
within ``[1, MAX_NR_GENS]`` while a page is on one of
``lrugen->folios[]``; otherwise it stores zero.

Each generation is divided into multiple tiers. A page accessed ``N``
times through file descriptors is in tier ``order_base_2(N)``. Unlike
generations, tiers do not have dedicated ``lrugen->folios[]``. In
contrast to moving across generations, which requires the LRU lock,
moving across tiers only involves atomic operations on
``folio->flags`` and therefore has a negligible cost. A feedback loop
modeled after the PID controller monitors refaults over all the tiers
from anon and file types and decides which tiers from which types to
evict or protect. The desired effect is to balance refault percentages
between anon and file types proportional to the swappiness level.

There are two conceptually independent procedures: the aging and the
eviction. They form a closed-loop system, i.e., the page reclaim.

Aging

Aging은 young generation을 만듭니다. `lruvec`가 주어지면 `max_seq-min_seq+1`이 `MIN_NR_GENS`에 가까워질 때 `max_seq`를 증가시킵니다. Page table을 통해 접근된 hot page를 찾으면 youngest generation으로 승격합니다. `max_seq` 증가에 따라 cold page는 결과적으로 강등됩니다.

Aging은 page-table walk와 rmap walk로 young PTE를 찾습니다. Page-table walk는 `lruvec_memcg()->mm_list`를 순회하며 list의 각 `mm_struct`에 `walk_page_range()`를 호출해 PTE를 scan하고, iteration마다 `max_seq`를 증가시킵니다. Rmap walk는 eviction이 rmap에서 young PTE를 찾으면 주변 PTE를 scan하는 방식입니다. 두 경우 모두 young PTE를 찾으면 accessed bit를 지우고 그 PTE가 mapping하는 page의 gen counter를 `(max_seq%MAX_NR_GENS)+1`로 갱신합니다.

Aging
-----
The aging produces young generations. Given an ``lruvec``, it
increments ``max_seq`` when ``max_seq-min_seq+1`` approaches
``MIN_NR_GENS``. The aging promotes hot pages to the youngest
generation when it finds them accessed through page tables; the
demotion of cold pages happens consequently when it increments
``max_seq``. The aging uses page table walks and rmap walks to find
young PTEs. For the former, it iterates ``lruvec_memcg()->mm_list``
and calls ``walk_page_range()`` with each ``mm_struct`` on this list
to scan PTEs, and after each iteration, it increments ``max_seq``. For
the latter, when the eviction walks the rmap and finds a young PTE,
the aging scans the adjacent PTEs. For both, on finding a young PTE,
the aging clears the accessed bit and updates the gen counter of the
page mapped by this PTE to ``(max_seq%MAX_NR_GENS)+1``.

Eviction

Eviction은 old generation을 소비합니다. `lruvec`가 주어지면 `min_seq%MAX_NR_GENS`로 index한 `lrugen->folios[]`가 비었을 때 `min_seq`를 증가시킵니다. Evict할 type과 tier를 고르기 위해 먼저 `min_seq[]`를 비교해 더 오래된 type을 선택합니다. 두 type이 같은 나이면 첫 tier의 refault 비율이 더 낮은 type을 고릅니다. 첫 tier에는 한 번만 사용된 unmapped clean page가 들어 있어 가장 유력한 후보입니다.

Aging이 page-table 접근을 발견해 gen counter를 갱신한 page는 eviction이 gen counter에 따라 다시 분류합니다. File descriptor를 통해 여러 번 접근했고 해당 tier에서 특이한 refault를 feedback loop가 감지한 page는 다음 generation, 즉 `min_seq+1`로 이동합니다. Feedback loop는 앞서 설명한 이유로 첫 tier를 baseline으로 사용합니다.

Eviction
--------
The eviction consumes old generations. Given an ``lruvec``, it
increments ``min_seq`` when ``lrugen->folios[]`` indexed by
``min_seq%MAX_NR_GENS`` becomes empty. To select a type and a tier to
evict from, it first compares ``min_seq[]`` to select the older type.
If both types are equally old, it selects the one whose first tier has
a lower refault percentage. The first tier contains single-use
unmapped clean pages, which are the best bet. The eviction sorts a
page according to its gen counter if the aging has found this page
accessed through page tables and updated its gen counter. It also
moves a page to the next generation, i.e., ``min_seq+1``, if this page
was accessed multiple times through file descriptors and the feedback
loop has detected outlying refaults from the tier this page is in. To
this end, the feedback loop uses the first tier as the baseline, for
the reason stated earlier.

Working-set 보호

각 generation은 생성 시점의 timestamp를 가집니다. `lru_gen_min_ttl`을 설정하면 `lruvec`의 oldest generation이 `lru_gen_min_ttl` millisecond 안에 생성됐을 때 eviction으로부터 보호합니다. 즉 최근 `lru_gen_min_ttl` millisecond의 working set이 evict되지 않게 합니다. 이 working set을 memory에 유지할 수 없으면 OOM killer를 실행합니다.

이 시간 기반 접근에는 다음 장점이 있습니다.

• Application과 memory size에 의존하지 않아 설정하기 쉽습니다.
• OOM killer에 직접 연결돼 있어 더 신뢰할 수 있습니다.

Working set protection
----------------------
Each generation is timestamped at birth. If ``lru_gen_min_ttl`` is
set, an ``lruvec`` is protected from the eviction when its oldest
generation was born within ``lru_gen_min_ttl`` milliseconds. In other
words, it prevents the working set of ``lru_gen_min_ttl`` milliseconds
from getting evicted. The OOM killer is triggered if this working set
cannot be kept in memory.

This time-based approach has the following advantages:

1. It is easier to configure because it is agnostic to applications
   and memory sizes.
2. It is more reliable because it is directly wired to the OOM killer.

Memcg별 mm_struct list

Memcg마다 `mm_struct` list를 유지하며 task가 새 memcg로 migration되면 `mm_struct`도 owner task를 따라갑니다.

Page-table walker는 `lruvec_memcg()->mm_list`를 순회하며 각 `mm_struct`에 `walk_page_range()`를 호출해 PTE를 scan합니다. 여러 page-table walker가 같은 list를 순회할 때 각각 고유한 `mm_struct`를 받으므로 병렬로 실행할 수 있습니다.

Page-table walker는 잘못 배치된 page를 무시합니다. 예를 들어 `mm_struct`가 migration된 뒤 이전 memcg에 남은 page는 현재 memcg를 reclaim할 때 무시합니다. 마찬가지로 reclaim 중인 node 외의 node에 속한 page도 무시합니다.

이 기반 구조는 context switch 사이의 `mm_struct` 사용도 추적하므로 page-table walker가 지난 iteration 이후 계속 sleep 중인 process를 건너뛸 수 있습니다.

``mm_struct`` list
------------------
An ``mm_struct`` list is maintained for each memcg, and an
``mm_struct`` follows its owner task to the new memcg when this task
is migrated.

A page table walker iterates ``lruvec_memcg()->mm_list`` and calls
``walk_page_range()`` with each ``mm_struct`` on this list to scan
PTEs. When multiple page table walkers iterate the same list, each of
them gets a unique ``mm_struct``, and therefore they can run in
parallel.

Page table walkers ignore any misplaced pages, e.g., if an
``mm_struct`` was migrated, pages left in the previous memcg will be
ignored when the current memcg is under reclaim. Similarly, page table
walkers will ignore pages from nodes other than the one under reclaim.

This infrastructure also tracks the usage of ``mm_struct`` between
context switches so that page table walkers can skip processes that
have been sleeping since the last iteration.

Rmap/PT walk feedback과 Bloom filter

LRU list의 각 page를 mapping하는 PTE를 rmap에서 찾아 accessed bit를 검사하고 지우는 작업은 비용이 클 수 있습니다. 서로 다른 VMA의 page는 physical-address 공간에서 서로 가까워도 rmap의 virtual-address 공간에서는 cache-friendly하지 않기 때문입니다. Mapping된 page를 주로 쓰는 workload에서는 rmap 검색이 reclaim path에서 가장 큰 CPU 비용이 될 수 있습니다.

`lru_gen_look_around()`은 spatial locality를 이용해 rmap 진입 횟수를 줄입니다. Young PTE 주변의 PTE를 scan하고 hot page를 승격합니다. Scan이 cacheline 효율적으로 이뤄졌다면 PTE table을 가리키는 PMD entry를 Bloom filter에 추가합니다. 이로써 eviction과 aging 사이에 feedback loop가 생깁니다.

Bloom filter는 set membership을 검사하는 공간·memory 효율적인 자료 구조입니다. Element가 set에 없거나 있을 가능성이 있는지를 검사합니다.

Eviction path의 `lru_gen_look_around()`에서 PMD가 충분한 수의 hot page를 가지면 그 주소를 filter에 넣습니다. Aging path에서 set membership이 확인되면 해당 PTE 범위에서 young page를 scan합니다.

Bloom filter의 set membership은 확률적입니다. False positive이면 PTE 범위를 한 번 더 scan하는 비용이 들지만 그 scan에서 hot page를 찾을 수도 있습니다. Filter parameter로 false-positive rate의 상한을 조절할 수 있습니다.

Rmap/PT walk feedback
---------------------
Searching the rmap for PTEs mapping each page on an LRU list (to test
and clear the accessed bit) can be expensive because pages from
different VMAs (PA space) are not cache friendly to the rmap (VA
space). For workloads mostly using mapped pages, searching the rmap
can incur the highest CPU cost in the reclaim path.

``lru_gen_look_around()`` exploits spatial locality to reduce the
trips into the rmap. It scans the adjacent PTEs of a young PTE and
promotes hot pages. If the scan was done cacheline efficiently, it
adds the PMD entry pointing to the PTE table to the Bloom filter. This
forms a feedback loop between the eviction and the aging.

Bloom filters
-------------
Bloom filters are a space and memory efficient data structure for set
membership test, i.e., test if an element is not in the set or may be
in the set.

In the eviction path, specifically, in ``lru_gen_look_around()``, if a
PMD has a sufficient number of hot pages, its address is placed in the
filter. In the aging path, set membership means that the PTE range
will be scanned for young pages.

Note that Bloom filters are probabilistic on set membership. If a test
is false positive, the cost is an additional scan of a range of PTEs,
which may yield hot pages anyway. Parameters of the filter itself can
control the false positive rate in the limit.

PID controller

Proportional-Integral-Derivative, 즉 PID controller를 본뜬 feedback loop가 anon과 file type의 refault를 관찰하고 같은 generation에서 두 type을 모두 선택할 수 있을 때 어느 type을 evict할지 결정합니다.

Memory pressure에 따라 CPU의 page scan 속도가 달라질 수 있으므로 PID controller는 wall clock이 아니라 generation을 time domain으로 사용합니다. Suboptimal state에 영구적으로 갇히지 않도록 새 generation마다 moving average를 계산합니다.

PID controller
--------------
A feedback loop modeled after the Proportional-Integral-Derivative
(PID) controller monitors refaults over anon and file types and
decides which type to evict when both types are available from the
same generation.

The PID controller uses generations rather than the wall clock as the
time domain because a CPU can scan pages at different rates under
varying memory pressure. It calculates a moving average for each new
generation to avoid being permanently locked in a suboptimal state.

Memcg LRU

Memcg LRU는 node별 memcg LRU입니다. 각 node와 memcg 조합에 folio LRU가 있으므로 `mem_cgroup_lruvec()`에서 볼 수 있듯 LRU들의 LRU이기도 합니다. 목표는 data center의 system-wide memory overcommit에 중요한 global reclaim 확장성을 높이는 것입니다. Memcg LRU는 global reclaim에만 적용됩니다.

Memcg LRU의 기본 구조는 folio의 active/inactive LRU에 빗대어 이해할 수 있습니다.

• Young과 old generation이 있으며 각각 active와 inactive에 대응합니다.
• `max_seq` 증가는 promotion을 일으키며 activation에 대응합니다.
• 다른 event도 비슷한 operation을 일으킵니다. 예를 들어 memcg offlining은 demotion을 일으키며 deactivation에 대응합니다.

Global reclaim 관점에서는 두 가지 특징이 있습니다.

• Sharding은 각 thread가 old generation의 임의 memcg에서 시작하게 해 parallelism을 높입니다.
• Eventual fairness는 direct reclaim이 원할 때 중단할 수 있게 해 일정 시간 범위의 fairness를 해치지 않으면서 latency를 줄입니다.

Global reclaim 중 memcg를 순회할 때 best-case complexity를 O(n)에서 O(1)로 개선하고 worst-case O(n)은 바꾸지 않습니다. 따라서 평균적으로 sublinear complexity를 가집니다.

Memcg LRU
---------
An memcg LRU is a per-node LRU of memcgs. It is also an LRU of LRUs,
since each node and memcg combination has an LRU of folios (see
``mem_cgroup_lruvec()``). Its goal is to improve the scalability of
global reclaim, which is critical to system-wide memory overcommit in
data centers. Note that memcg LRU only applies to global reclaim.

The basic structure of an memcg LRU can be understood by an analogy to
the active/inactive LRU (of folios):

1. It has the young and the old (generations), i.e., the counterparts
   to the active and the inactive;
2. The increment of ``max_seq`` triggers promotion, i.e., the
   counterpart to activation;
3. Other events trigger similar operations, e.g., offlining an memcg
   triggers demotion, i.e., the counterpart to deactivation.

In terms of global reclaim, it has two distinct features:

1. Sharding, which allows each thread to start at a random memcg (in
   the old generation) and improves parallelism;
2. Eventual fairness, which allows direct reclaim to bail out at will
   and reduces latency without affecting fairness over some time.

In terms of traversing memcgs during global reclaim, it improves the
best-case complexity from O(n) to O(1) and does not affect the
worst-case complexity O(n). Therefore, on average, it has a sublinear
complexity.

구성 요소와 상호작용 요약

Folio용 multi-gen LRU는 다음 부분으로 나눌 수 있습니다.

• Generation
• Rmap walk
• `mm_struct` list를 통한 page-table walk
• Rmap/PT-walk feedback용 Bloom filter
• Refault feedback용 PID controller

Aging과 eviction은 producer-consumer model을 이룹니다. 구체적으로 eviction이 generation sliding window를 통해 aging을 구동합니다. Aging 안에서는 rmap walk가 hot page가 조밀하게 들어 있는 page table을 Bloom filter에 넣어 page-table walk를 구동합니다. Eviction 안에서는 PID controller가 refault를 feedback으로 사용해 evict할 type과 보호할 tier를 선택합니다.

Summary
-------
The multi-gen LRU (of folios) can be disassembled into the following
parts:

* Generations
* Rmap walks
* Page table walks via ``mm_struct`` list
* Bloom filters for rmap/PT walk feedback
* PID controller for refault feedback

The aging and the eviction form a producer-consumer model;
specifically, the latter drives the former by the sliding window over
generations. Within the aging, rmap walks drive page table walks by
inserting hot densely populated page tables to the Bloom filters.
Within the eviction, the PID controller uses refaults as the feedback
to select types to evict and tiers to protect.