summaryrefslogtreecommitdiff
path: root/Documentation/mm
diff options
context:
space:
mode:
authorT.J. Alumbaugh <talumbau@google.com>2023-01-18 03:18:23 +0300
committerAndrew Morton <akpm@linux-foundation.org>2023-02-03 09:33:27 +0300
commitccbbbb85945d8f0255aa9dbc1b617017e2294f2c (patch)
tree096de0c53f420d8439b528c2ca22244457c36962 /Documentation/mm
parentdb19a43d9b3a8876552f00f656008206ef9a5efa (diff)
downloadlinux-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.rst16
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: