diff options
| author | T.J. Alumbaugh <talumbau@google.com> | 2023-01-18 03:18:23 +0300 |
|---|---|---|
| committer | Andrew Morton <akpm@linux-foundation.org> | 2023-02-03 09:33:27 +0300 |
| commit | ccbbbb85945d8f0255aa9dbc1b617017e2294f2c (patch) | |
| tree | 096de0c53f420d8439b528c2ca22244457c36962 /Documentation/mm | |
| parent | db19a43d9b3a8876552f00f656008206ef9a5efa (diff) | |
| download | linux-ccbbbb85945d8f0255aa9dbc1b617017e2294f2c.tar.xz | |
mm: multi-gen LRU: section for Bloom filters
Move Bloom filters code into a dedicated section. Improve the design doc
to explain Bloom filter usage and connection between aging and eviction in
their use.
Link: https://lkml.kernel.org/r/20230118001827.1040870-4-talumbau@google.com
Signed-off-by: T.J. Alumbaugh <talumbau@google.com>
Cc: Yu Zhao <yuzhao@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Diffstat (limited to 'Documentation/mm')
| -rw-r--r-- | Documentation/mm/multigen_lru.rst | 16 |
1 files changed, 16 insertions, 0 deletions
diff --git a/Documentation/mm/multigen_lru.rst b/Documentation/mm/multigen_lru.rst index bd988a142bc2..770b5d539856 100644 --- a/Documentation/mm/multigen_lru.rst +++ b/Documentation/mm/multigen_lru.rst @@ -170,6 +170,22 @@ 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. + Summary ------- The multi-gen LRU can be disassembled into the following parts: |