Skip to content

skip empty PUD subtrees during aging with a PUD-level Bloom filter

Baoquan He linux-mm sashiko-reviews 2 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v3 Latest4 patches 4 repliesIn review
  2. v14 patches 0 repliesSuperseded

Changes in v3 from the cover letter

- Use (mm, PUD-aligned address) as the PUD filter key instead of the PUD page-table pointer. This removes the pud_offset(p4d_offset(pgd_offset())) page-table walk that the v2 lru_gen_look_around() hunk had to do to obtain the key with withc Barry is very worried about adding cost to a hot paths. This is suggested by Kairui.

- Store both levels in one array, filters[BLOOM_FILTER_LEVELS] [NR_BLOOM_FILTERS], instead of separate pmd_filters/pud_filters (Kairui's idea).

- Count skipped subtrees (MM_PUD_EMPTY_SKIPPED, debugfs column "S" of TYFALWEES, and a tracepoint field) so the avoided cost is measurable.

Patches in v3 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/4mm/mglru: add MM_WALK_EMPTY stats and tracepointinclude/linux/mmzone.h mm/trace_vmscan.h mm/vmscan.c+60 -42 replies
2/4mm/mglru: add PUD-level Bloom filter state and generic helpersinclude/linux/mmzone.h mm/vmscan.c+49 -191 reply
3/4mm/mglru: skip cold PUD subtrees during agingmm/vmscan.c+38 -71 reply
4/4mm/mglru: count PUD subtrees skipped by the PUD-level filterinclude/linux/mmzone.h mm/trace_vmscan.h mm/vmscan.c+15 -90 replies

Reviews trailers per patch

2 of 4 patches have a Reviewed-by or Acked-by.

PatchBarry SongKairui Song
1/4R-b
2/4R-b
3/4
4/4

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v3 thread

Cover letter [PATCH v3 0/4] skip empty PUD subtrees during aging with a PUD-level Bloom filter

Problem
=======

MGLRU's aging walks every PUD of every mm in the mm_list. For a PUD whose 512 PMDs all fail the existing PMD-level Bloom filter, the walker still descends into the PUD and iterates all 512 PMD entries. When an mm has no pages on a given node this is structural waste: lru_gen_use_mm() sets mm->lru_gen.bitmap to -1 (all nodes) on every context switch, so the aging walker of *every* node -- kswapd, direct reclaim, proactive aging -- walks the same mm.

On a 2-node KVM guest with the workload pinned to node 0, node 1's aging walks of those mms scan 1,363 leaf entries per walk while finding no folio that belongs to node 1's lruvec, and 94% of those walks are entirely empty.

Approach
========

Add a PUD-level Bloom filter, one level above the existing PMD filter. The walker now:

1. Tests the PUD filter before descending into a PUD subtree.
2. If the PUD had nothing young for this lruvec last generation, skips the whole 1 GiB region -- avoiding 512 PMD lookups.
3. walk_pmd_range() reports whether it found anything young; walk_pud_range() records that in the double-buffered PUD filter.
4. The rmap feedback path (lru_gen_look_around()) marks hot PUDs, so regions whose hotness is only observed by eviction are re-examined promptly.
5. force_scan walks bypass the PUD test, so manual aging and newly added mms always rescan and re-populate the filter.

The filter key is (mm, PUD-aligned address), as suggested by Kairui. It is a stable identity of the range on both sides of the interface which the aging walk computes from args->mm and addr, lru_gen_look_around() from vma->vm_mm and pvmw->address. So the rmap feedback path needs no page-table walk at all.

The double-buffered filter flips each generation and force_scan bypasses it, so a missed re-mark costs at most one generation, and reclaim is still safe for a wrongly skipped subtree because folio_referenced() consults the PTE young bits, not the filter.

Change log
==========

v2 -> v3:

- Use (mm, PUD-aligned address) as the PUD filter key instead of the PUD page-table pointer. This removes the pud_offset(p4d_offset(pgd_offset())) page-table walk that the v2 lru_gen_look_around() hunk had to do to obtain the key with withc Barry is very worried about adding cost to a hot paths. This is suggested by Kairui.

- Store both levels in one array, filters[BLOOM_FILTER_LEVELS] [NR_BLOOM_FILTERS], instead of separate pmd_filters/pud_filters (Kairui's idea).

- Count skipped subtrees (MM_PUD_EMPTY_SKIPPED, debugfs column "S" of TYFALWEES, and a tracepoint field) so the avoided cost is measurable.

Test
====

8 GiB KVM guest, 4 vCPU, two 4 GiB NUMA nodes, 7.4.0-rc1 with the series. "base" below is the same kernel with the filter disabled (patch 1 only):
same .config, same workload, medians of 3 runs.

1) Cross-node empty walks. 16 workers x 128 MiB pinned to node 0 (numactl --membind=0), so node 1 owns none of these pages. 100 aging passes, per pass, both nodes aged:

base filter change
node 1 leaf entries scanned 1,213 99 -92%
walks with leaves 17 1 -94%
PUDs skipped 0 52
node 0 leaf entries scanned 12,308 11,793 -4.2%
leaf entries assoc. 9,175 8,902 -3.0%
worker RSS delta 0% 0%

forced pass, node 1 leaf/walk
before the filtered passes 1,363.0 1,361.4
after them 1,363.0 1,341.3

A forced pass bypasses the filter, so it costs the same on both kernels and the same before and after 100 filtered passes: the filter is a cache, not a state. Node 0 keeps its associated leaves (-3.0% is run-to-run noise), so the coarser filter does not starve the node that owns them.

2) Correctness, 11 checks, all pass: a cold PUD is skipped; touching it does not revive it; force_scan re-marks it and the next pass walks it again; a munmap + mmap at the same address shows no stale suppression; a 1 GiB range migrated from node 0 to node 1 is re-scanned by node 1 after one forced pass; no premature reclaim in any of them; dmesg clean.

3) Reclaim pressure. Four 512 MiB workers in a memory.max=2G/swap.max=1G memcg, i.e. exactly at the limit, so reclaim is always active; each touches one 256 MiB half and flips it every second, so a half is cold for a few aging generations and then hot again. Aging runs on both nodes every 0.5 s, for 600 s; medians of 3 runs each:

     oom_kill 0 vs 0
     hot half resident, min   261,902 vs 261,887  (of 262,144 pages)
     pgscan_anon               84.5M  vs  110.6M  1.31x
     pgsteal_anon              4.47M  vs   3.55M  0.79x
     pswpout                   4.45M  vs   3.54M  0.80x
     workingset_refault_anon   4.47M  vs   3.55M  0.79x
     node 1 walks with leaves  4,568  vs      4  -99.9%

No OOM, no residency loss, fewer evictions and refaults. The extra scanning is expected: pgscan_anon counts folios examined by the LRU scanner on both nodes, not page-table walks, and the baseline's own spread on these counters is 1.5x (pgscan_anon 73.1-112.4M between its three runs), so both directions are inside the noise. PUD subtrees skipped on node 0 are 0.002-0.015% of its associated leaves.

4) Low memory. Two checks for the phone case. First, when a 1 GiB PUD covers most of a process, can the filter still save anything? Second, if it cannot help, does it cost anything?

a) Aging cost on a single node. CPU time per pass, taken from the utime+stime of the task that writes to debugfs:

shape base filter change
32 GiB VA, 0.2% touched 2400 us 1750 us -27%
(32 PUDs per mm)
3 GiB VA, 2% touched 7650 us 7650 us 0%
(3 PUDs per mm)
64 MiB, fully touched 8250 us 7950 us 0%

The leaves scanned, the leaves associated and the number of walks with leaves are the same in all three rows. If a mm has only a few 1 GiB subtrees, the filter has nothing to save and it spends nothing. If a mm has more, it saves about 10.5 us of CPU per skipped subtree per pass, which is the cost of 512 PMD-level Bloom tests.

b) The pressure test of (3), repeated on a single-node 3.9 GiB guest. mem=6G cuts the 2x4 GiB memory layout so that one node has 3.9 GiB and the other has none. 2 runs each:

oom_kill 0 vs 0
hot half resident, min 262,121 vs 262,051 (of 262,144 pages)
pgscan_anon 99.6M vs 97.3M 0.98x
pgsteal_anon 3.50M vs 3.54M 1.01x
pswpout 3.49M vs 3.53M 1.01x
workingset_refault_anon 3.50M vs 3.54M 1.01x

Residency is the same, and there is no OOM. The patched kernel evicts and refaults 1% more, and scans 2% less. We think this is noise, for two reasons. Between two runs of the baseline kernel the same numbers move by 16%. And in the 2-node test of (3) the same ratio is 0.79x -- lower, not higher -- so the direction is not stable across tests.

Even if the 1% is real, it is what the design expects. A subtree is skipped only when it had no young page for this lruvec in the last generation. The pages in such a subtree are already cold, so it is normal that they are reclaimed first. On the only node the filter skips 16-18 subtrees per pass, which is 0.013% of its associated leaves.

Baoquan He (4):
mm/mglru: add MM_WALK_EMPTY stats and tracepoint mm/mglru: add PUD-level Bloom filter state and generic helpers mm/mglru: skip cold PUD subtrees during aging mm/mglru: count PUD subtrees skipped by the PUD-level filter

 include/linux/mmzone.h |  15 ++++-
 mm/trace_vmscan.h      |  30 +++++++++
 mm/vmscan.c            | 134 +++++++++++++++++++++++++++++++++--------
 3 files changed, 151 insertions(+), 28 deletions(-)
Signature · 1 line
2.52.0