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

[Baoquan He <baoquan.he@linux.dev>]

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(-)

-- 
2.52.0