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

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

[Baoquan He]

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

[PATCH v3 1/4] mm/mglru: add MM_WALK_EMPTY stats and tracepoint

[Baoquan He]

From: Baoquan He <hebaoquan@kylinos.cn>

Add per-walk counters to measure empty aging walks which traverse
an mm's page tables but find no folio for the current lruvec (node+memcg).
These are common on multi-NUMA node systems because lru_gen_use_mm() marks
an mm for all nodes at every context switch.

New counters (accumulated in mm_state->stats[]):

  MM_LEAF_ASSOCIATED   - leaf entries whose folio is in this lruvec
  MM_WALK_TOTAL        - page-table walks completed
  MM_WALK_EMPTY        - walks that found no folio in this lruvec
  MM_LEAF_EMPTY_WALKS  - leaf entries scanned during empty walks

A new tracepoint, mm_vmscan_lru_gen_walk(), fires after each walk, and the
debugfs lru_gen output ("TYFALWEE") exposes the new counters.

Reviewed-by: Barry Song <baohua@kernel.org>
Signed-off-by: Baoquan He <hebaoquan@kylinos.cn>
Signed-off-by: Baoquan He <baoquan.he@linux.dev>
---
 include/linux/mmzone.h |  4 ++++
 mm/trace_vmscan.h      | 28 ++++++++++++++++++++++++++++
 mm/vmscan.c            | 32 ++++++++++++++++++++++++++++----
 3 files changed, 60 insertions(+), 4 deletions(-)

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index c161d563ce8f..a49efd9b74ed 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -579,6 +579,10 @@ enum {
 	MM_LEAF_YOUNG,		/* young leaf entries */
 	MM_NONLEAF_FOUND,	/* non-leaf entries found in Bloom filters */
 	MM_NONLEAF_ADDED,	/* non-leaf entries added to Bloom filters */
+	MM_LEAF_ASSOCIATED,	/* leaf entries whose folio is in this lruvec (node+memcg) */
+	MM_WALK_TOTAL,		/* page-table walks completed */
+	MM_WALK_EMPTY,		/* walks that found no folio in this lruvec */
+	MM_LEAF_EMPTY_WALKS,	/* leaf entries scanned during empty walks */
 	NR_MM_STATS
 };
 
diff --git a/mm/trace_vmscan.h b/mm/trace_vmscan.h
index 565c56428364..4884fc7a35b9 100644
--- a/mm/trace_vmscan.h
+++ b/mm/trace_vmscan.h
@@ -763,6 +763,34 @@ TRACE_EVENT(mm_vmscan_kswapd_clear_hopeless,
 		__entry->nid,
 		__print_symbolic(__entry->reason, kswapd_clear_hopeless_reason_ops))
 );
+TRACE_EVENT(mm_vmscan_lru_gen_walk,
+
+	TP_PROTO(int nid, unsigned long seq, int leaf_total,
+		 int leaf_associated, bool empty),
+
+	TP_ARGS(nid, seq, leaf_total, leaf_associated, empty),
+
+	TP_STRUCT__entry(
+		__field(int, nid)
+		__field(unsigned long, seq)
+		__field(int, leaf_total)
+		__field(int, leaf_associated)
+		__field(bool, empty)
+	),
+
+	TP_fast_assign(
+		__entry->nid = nid;
+		__entry->seq = seq;
+		__entry->leaf_total = leaf_total;
+		__entry->leaf_associated = leaf_associated;
+		__entry->empty = empty;
+	),
+
+	TP_printk("nid=%d seq=%lu leaf_total=%d leaf_associated=%d empty=%d",
+		__entry->nid, __entry->seq, __entry->leaf_total,
+		__entry->leaf_associated, __entry->empty)
+);
+
 #endif /* _TRACE_VMSCAN_H */
 
 /* This part must be outside protection */
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 96201eae0ceb..98037a562ab6 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -3590,6 +3590,8 @@ static bool walk_pte_range(pmd_t *pmd, unsigned long start, unsigned long end,
 		if (!folio)
 			continue;
 
+		walk->mm_stats[MM_LEAF_ASSOCIATED]++;
+
 		if (folio_test_large(folio)) {
 			const unsigned int max_nr = (end - addr) >> PAGE_SHIFT;
 
@@ -3688,6 +3690,8 @@ static void walk_pmd_range_locked(pud_t *pud, unsigned long addr, struct vm_area
 		if (!folio)
 			goto next;
 
+		walk->mm_stats[MM_LEAF_ASSOCIATED]++;
+
 		if (!pmdp_test_and_clear_young_notify(vma, addr, pmd + i))
 			goto next;
 
@@ -4151,8 +4155,28 @@ static bool try_to_inc_max_seq(struct lruvec *lruvec, unsigned long seq,
 
 	do {
 		success = iterate_mm_list(walk, &mm);
-		if (mm)
+		if (mm) {
+			bool empty = false;
+
 			walk_mm(mm, walk);
+			/*
+			 * A walk that traversed page tables but found no folio
+			 * belonging to this lruvec (node+memcg) is pure waste.
+			 */
+			if (walk->mm_stats[MM_LEAF_TOTAL]) {
+				walk->mm_stats[MM_WALK_TOTAL]++;
+				if (walk->mm_stats[MM_LEAF_ASSOCIATED] == 0) {
+					walk->mm_stats[MM_WALK_EMPTY]++;
+					walk->mm_stats[MM_LEAF_EMPTY_WALKS] +=
+						walk->mm_stats[MM_LEAF_TOTAL];
+					empty = true;
+				}
+			}
+			trace_mm_vmscan_lru_gen_walk(
+					lruvec_pgdat(lruvec)->node_id, walk->seq,
+					walk->mm_stats[MM_LEAF_TOTAL],
+					walk->mm_stats[MM_LEAF_ASSOCIATED], empty);
+		}
 	} while (mm);
 done:
 	if (success) {
@@ -5638,14 +5662,14 @@ static void lru_gen_seq_show_full(struct seq_file *m, struct lruvec *lruvec,
 
 	seq_puts(m, "                      ");
 	for (i = 0; i < NR_MM_STATS; i++) {
-		const char *s = "xxxx";
+		const char *s = "xxxxxxxx";
 		unsigned long n = 0;
 
 		if (seq == max_seq && NR_HIST_GENS == 1) {
-			s = "TYFA";
+			s = "TYFALWEE";
 			n = READ_ONCE(mm_state->stats[hist][i]);
 		} else if (seq != max_seq && NR_HIST_GENS > 1) {
-			s = "tyfa";
+			s = "tyfalwee";
 			n = READ_ONCE(mm_state->stats[hist][i]);
 		}
 
-- 
2.52.0

Re: [PATCH v3 1/4] mm/mglru: add MM_WALK_EMPTY stats and tracepoint

[Baoquan He]

On 11/13/26 at 04:49pm, Baoquan He wrote:
> From: Baoquan He <hebaoquan@kylinos.cn>
> 
> Add per-walk counters to measure empty aging walks which traverse
> an mm's page tables but find no folio for the current lruvec (node+memcg).
> These are common on multi-NUMA node systems because lru_gen_use_mm() marks
> an mm for all nodes at every context switch.
> 
> New counters (accumulated in mm_state->stats[]):
> 
>   MM_LEAF_ASSOCIATED   - leaf entries whose folio is in this lruvec
>   MM_WALK_TOTAL        - page-table walks completed
>   MM_WALK_EMPTY        - walks that found no folio in this lruvec
>   MM_LEAF_EMPTY_WALKS  - leaf entries scanned during empty walks
> 
> A new tracepoint, mm_vmscan_lru_gen_walk(), fires after each walk, and the
> debugfs lru_gen output ("TYFALWEE") exposes the new counters.
> 
> Reviewed-by: Barry Song <baohua@kernel.org>
> Signed-off-by: Baoquan He <hebaoquan@kylinos.cn>

> Signed-off-by: Baoquan He <baoquan.he@linux.dev>
~~~
Git format-patch automatically added my linux.dev mail address, I should
have noticed this and remove it.

> ---
>  include/linux/mmzone.h |  4 ++++
>  mm/trace_vmscan.h      | 28 ++++++++++++++++++++++++++++
>  mm/vmscan.c            | 32 ++++++++++++++++++++++++++++----
>  3 files changed, 60 insertions(+), 4 deletions(-)
> 
> diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
> index c161d563ce8f..a49efd9b74ed 100644
> --- a/include/linux/mmzone.h
> +++ b/include/linux/mmzone.h
> @@ -579,6 +579,10 @@ enum {
>  	MM_LEAF_YOUNG,		/* young leaf entries */
>  	MM_NONLEAF_FOUND,	/* non-leaf entries found in Bloom filters */
>  	MM_NONLEAF_ADDED,	/* non-leaf entries added to Bloom filters */
> +	MM_LEAF_ASSOCIATED,	/* leaf entries whose folio is in this lruvec (node+memcg) */
> +	MM_WALK_TOTAL,		/* page-table walks completed */
> +	MM_WALK_EMPTY,		/* walks that found no folio in this lruvec */
> +	MM_LEAF_EMPTY_WALKS,	/* leaf entries scanned during empty walks */
>  	NR_MM_STATS
>  };
>  
> diff --git a/mm/trace_vmscan.h b/mm/trace_vmscan.h
> index 565c56428364..4884fc7a35b9 100644
> --- a/mm/trace_vmscan.h
> +++ b/mm/trace_vmscan.h
> @@ -763,6 +763,34 @@ TRACE_EVENT(mm_vmscan_kswapd_clear_hopeless,
>  		__entry->nid,
>  		__print_symbolic(__entry->reason, kswapd_clear_hopeless_reason_ops))
>  );
> +TRACE_EVENT(mm_vmscan_lru_gen_walk,
> +
> +	TP_PROTO(int nid, unsigned long seq, int leaf_total,
> +		 int leaf_associated, bool empty),
> +
> +	TP_ARGS(nid, seq, leaf_total, leaf_associated, empty),
> +
> +	TP_STRUCT__entry(
> +		__field(int, nid)
> +		__field(unsigned long, seq)
> +		__field(int, leaf_total)
> +		__field(int, leaf_associated)
> +		__field(bool, empty)
> +	),
> +
> +	TP_fast_assign(
> +		__entry->nid = nid;
> +		__entry->seq = seq;
> +		__entry->leaf_total = leaf_total;
> +		__entry->leaf_associated = leaf_associated;
> +		__entry->empty = empty;
> +	),
> +
> +	TP_printk("nid=%d seq=%lu leaf_total=%d leaf_associated=%d empty=%d",
> +		__entry->nid, __entry->seq, __entry->leaf_total,
> +		__entry->leaf_associated, __entry->empty)
> +);
> +
>  #endif /* _TRACE_VMSCAN_H */
>  
>  /* This part must be outside protection */
> diff --git a/mm/vmscan.c b/mm/vmscan.c
> index 96201eae0ceb..98037a562ab6 100644
> --- a/mm/vmscan.c
> +++ b/mm/vmscan.c
> @@ -3590,6 +3590,8 @@ static bool walk_pte_range(pmd_t *pmd, unsigned long start, unsigned long end,
>  		if (!folio)
>  			continue;
>  
> +		walk->mm_stats[MM_LEAF_ASSOCIATED]++;
> +
>  		if (folio_test_large(folio)) {
>  			const unsigned int max_nr = (end - addr) >> PAGE_SHIFT;
>  
> @@ -3688,6 +3690,8 @@ static void walk_pmd_range_locked(pud_t *pud, unsigned long addr, struct vm_area
>  		if (!folio)
>  			goto next;
>  
> +		walk->mm_stats[MM_LEAF_ASSOCIATED]++;
> +
>  		if (!pmdp_test_and_clear_young_notify(vma, addr, pmd + i))
>  			goto next;
>  
> @@ -4151,8 +4155,28 @@ static bool try_to_inc_max_seq(struct lruvec *lruvec, unsigned long seq,
>  
>  	do {
>  		success = iterate_mm_list(walk, &mm);
> -		if (mm)
> +		if (mm) {
> +			bool empty = false;
> +
>  			walk_mm(mm, walk);
> +			/*
> +			 * A walk that traversed page tables but found no folio
> +			 * belonging to this lruvec (node+memcg) is pure waste.
> +			 */
> +			if (walk->mm_stats[MM_LEAF_TOTAL]) {
> +				walk->mm_stats[MM_WALK_TOTAL]++;
> +				if (walk->mm_stats[MM_LEAF_ASSOCIATED] == 0) {
> +					walk->mm_stats[MM_WALK_EMPTY]++;
> +					walk->mm_stats[MM_LEAF_EMPTY_WALKS] +=
> +						walk->mm_stats[MM_LEAF_TOTAL];
> +					empty = true;
> +				}
> +			}
> +			trace_mm_vmscan_lru_gen_walk(
> +					lruvec_pgdat(lruvec)->node_id, walk->seq,
> +					walk->mm_stats[MM_LEAF_TOTAL],
> +					walk->mm_stats[MM_LEAF_ASSOCIATED], empty);
> +		}
>  	} while (mm);
>  done:
>  	if (success) {
> @@ -5638,14 +5662,14 @@ static void lru_gen_seq_show_full(struct seq_file *m, struct lruvec *lruvec,
>  
>  	seq_puts(m, "                      ");
>  	for (i = 0; i < NR_MM_STATS; i++) {
> -		const char *s = "xxxx";
> +		const char *s = "xxxxxxxx";
>  		unsigned long n = 0;
>  
>  		if (seq == max_seq && NR_HIST_GENS == 1) {
> -			s = "TYFA";
> +			s = "TYFALWEE";
>  			n = READ_ONCE(mm_state->stats[hist][i]);
>  		} else if (seq != max_seq && NR_HIST_GENS > 1) {
> -			s = "tyfa";
> +			s = "tyfalwee";
>  			n = READ_ONCE(mm_state->stats[hist][i]);
>  		}
>  
> -- 
> 2.52.0
> 

[PATCH v3 2/4] mm/mglru: add PUD-level Bloom filter state and generic helpers

[Baoquan He]

From: Baoquan He <hebaoquan@kylinos.cn>

Generalize the Bloom filter state and helpers so that another filter
level can reuse the same hash, double-buffering and reset logic.

Replace the PMD-level filter array with a two-dimensional filters array
indexed by level, and add BLOOM_FILTER_PUD and BLOOM_FILTER_PMD. The
PUD-level filters operate at PUD granularity and generalize the
suppression one level up: when all PMDs under a PUD fail the PMD-level
filter, the whole PMD iteration can be skipped. Cross-node empty walks
are the most visible case: a foreign mm's PUDs have no young entries for
this lruvec, so the entire PMD iteration is pure waste.

The existing PMD-level code now goes through the generic
test/update/reset_bloom_filter() helpers.

No behavior change yet; the PUD-level filters are populated and used by
the next patch.

Signed-off-by: Baoquan He <hebaoquan@kylinos.cn>
Signed-off-by: Baoquan He <baoquan.he@linux.dev>
---
 include/linux/mmzone.h | 10 ++++++--
 mm/vmscan.c            | 58 +++++++++++++++++++++++++++++-------------
 2 files changed, 49 insertions(+), 19 deletions(-)

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index a49efd9b74ed..1f086ef3a00e 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -589,6 +589,12 @@ enum {
 /* double-buffering Bloom filters */
 #define NR_BLOOM_FILTERS	2
 
+enum bloom_filter_level {
+	BLOOM_FILTER_PUD,
+	BLOOM_FILTER_PMD,
+	BLOOM_FILTER_LEVELS,
+};
+
 struct lru_gen_mm_state {
 	/* synced with max_seq after each iteration */
 	unsigned long seq;
@@ -596,8 +602,8 @@ struct lru_gen_mm_state {
 	struct list_head *head;
 	/* where the last iteration ended before */
 	struct list_head *tail;
-	/* Bloom filters flip after each iteration */
-	unsigned long *filters[NR_BLOOM_FILTERS];
+	/* Bloom filters flip after each iteration, indexed by level */
+	unsigned long *filters[BLOOM_FILTER_LEVELS][NR_BLOOM_FILTERS];
 	/* the mm stats for debugging */
 	unsigned long stats[NR_HIST_GENS][NR_MM_STATS];
 };
diff --git a/mm/vmscan.c b/mm/vmscan.c
index 98037a562ab6..9dbb3f477d7d 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -2798,6 +2798,10 @@ static bool __maybe_unused seq_is_valid(struct lruvec *lruvec)
  * walk_pmd_range(); the eviction also report them when walking the rmap
  * in lru_gen_look_around().
  *
+ * A second, coarser pair of filters sits one level up. The filters are
+ * indexed by level: BLOOM_FILTER_PMD for the PMD-level filters above, and
+ * BLOOM_FILTER_PUD for the PUD-level pair.
+ *
  * For future optimizations:
  * 1. It's not necessary to keep both filters all the time. The spare one can be
  *    freed after the RCU grace period and reallocated if needed again.
@@ -2823,14 +2827,13 @@ static void get_item_key(void *item, int *key)
 	key[1] = hash >> BLOOM_FILTER_SHIFT;
 }
 
-static bool test_bloom_filter(struct lru_gen_mm_state *mm_state, unsigned long seq,
-			      void *item)
+static bool __test_bloom_filter(unsigned long **filters, unsigned long seq, void *item)
 {
 	int key[2];
 	unsigned long *filter;
 	int gen = filter_gen_from_seq(seq);
 
-	filter = READ_ONCE(mm_state->filters[gen]);
+	filter = READ_ONCE(filters[gen]);
 	if (!filter)
 		return true;
 
@@ -2839,14 +2842,13 @@ static bool test_bloom_filter(struct lru_gen_mm_state *mm_state, unsigned long s
 	return test_bit(key[0], filter) && test_bit(key[1], filter);
 }
 
-static void update_bloom_filter(struct lru_gen_mm_state *mm_state, unsigned long seq,
-				void *item)
+static void __update_bloom_filter(unsigned long **filters, unsigned long seq, void *item)
 {
 	int key[2];
 	unsigned long *filter;
 	int gen = filter_gen_from_seq(seq);
 
-	filter = READ_ONCE(mm_state->filters[gen]);
+	filter = READ_ONCE(filters[gen]);
 	if (!filter)
 		return;
 
@@ -2858,12 +2860,12 @@ static void update_bloom_filter(struct lru_gen_mm_state *mm_state, unsigned long
 		set_bit(key[1], filter);
 }
 
-static void reset_bloom_filter(struct lru_gen_mm_state *mm_state, unsigned long seq)
+static void __reset_bloom_filter(unsigned long **filters, unsigned long seq)
 {
 	unsigned long *filter;
 	int gen = filter_gen_from_seq(seq);
 
-	filter = mm_state->filters[gen];
+	filter = filters[gen];
 	if (filter) {
 		bitmap_clear(filter, 0, BIT(BLOOM_FILTER_SHIFT));
 		return;
@@ -2871,7 +2873,25 @@ static void reset_bloom_filter(struct lru_gen_mm_state *mm_state, unsigned long
 
 	filter = bitmap_zalloc(BIT(BLOOM_FILTER_SHIFT),
 			       __GFP_HIGH | __GFP_NOMEMALLOC | __GFP_NOWARN);
-	WRITE_ONCE(mm_state->filters[gen], filter);
+	WRITE_ONCE(filters[gen], filter);
+}
+
+static bool test_bloom_filter(struct lru_gen_mm_state *mm_state, int level,
+			      unsigned long seq, void *item)
+{
+	return __test_bloom_filter(mm_state->filters[level], seq, item);
+}
+
+static void update_bloom_filter(struct lru_gen_mm_state *mm_state, int level,
+				unsigned long seq, void *item)
+{
+	__update_bloom_filter(mm_state->filters[level], seq, item);
+}
+
+static void reset_bloom_filter(struct lru_gen_mm_state *mm_state, int level,
+			       unsigned long seq)
+{
+	__reset_bloom_filter(mm_state->filters[level], seq);
 }
 
 /******************************************************************************
@@ -3114,7 +3134,7 @@ static bool iterate_mm_list(struct lru_gen_mm_walk *walk, struct mm_struct **ite
 	spin_unlock(&mm_list->lock);
 
 	if (mm && first)
-		reset_bloom_filter(mm_state, walk->seq + 1);
+		reset_bloom_filter(mm_state, BLOOM_FILTER_PMD, walk->seq + 1);
 
 	if (*iter)
 		mmdrop(*iter);
@@ -3771,7 +3791,8 @@ static void walk_pmd_range(pud_t *pud, unsigned long start, unsigned long end,
 			walk_pmd_range_locked(pud, addr, vma, args, bitmap, &first);
 		}
 
-		if (!walk->force_scan && !test_bloom_filter(mm_state, walk->seq, pmd + i))
+		if (!walk->force_scan &&
+		    !test_bloom_filter(mm_state, BLOOM_FILTER_PMD, walk->seq, pmd + i))
 			continue;
 
 		walk->mm_stats[MM_NONLEAF_FOUND]++;
@@ -3782,7 +3803,7 @@ static void walk_pmd_range(pud_t *pud, unsigned long start, unsigned long end,
 		walk->mm_stats[MM_NONLEAF_ADDED]++;
 
 		/* carry over to the next generation */
-		update_bloom_filter(mm_state, walk->seq + 1, pmd + i);
+		update_bloom_filter(mm_state, BLOOM_FILTER_PMD, walk->seq + 1, pmd + i);
 	}
 
 	walk_pmd_range_locked(pud, -1, vma, args, bitmap, &first);
@@ -4417,8 +4438,8 @@ bool lru_gen_look_around(struct page_vma_mapped_walk *pvmw, unsigned int nr)
 
 	/* feedback from rmap walkers to page table walkers */
 	if (mm_state && suitable_to_scan(i, young))
-		update_bloom_filter(mm_state, READ_ONCE(lruvec->lrugen.max_seq),
-				    pvmw->pmd);
+		update_bloom_filter(mm_state, BLOOM_FILTER_PMD,
+				    READ_ONCE(lruvec->lrugen.max_seq), pvmw->pmd);
 
 	mem_cgroup_put(memcg);
 
@@ -5981,6 +6002,7 @@ void lru_gen_init_memcg(struct mem_cgroup *memcg)
 void lru_gen_exit_memcg(struct mem_cgroup *memcg)
 {
 	int i;
+	int level;
 	int nid;
 	struct lru_gen_mm_list *mm_list = get_mm_list(memcg);
 
@@ -5998,9 +6020,11 @@ void lru_gen_exit_memcg(struct mem_cgroup *memcg)
 		if (!mm_state)
 			continue;
 
-		for (i = 0; i < NR_BLOOM_FILTERS; i++) {
-			bitmap_free(mm_state->filters[i]);
-			mm_state->filters[i] = NULL;
+		for (level = 0; level < BLOOM_FILTER_LEVELS; level++) {
+			for (i = 0; i < NR_BLOOM_FILTERS; i++) {
+				bitmap_free(mm_state->filters[level][i]);
+				mm_state->filters[level][i] = NULL;
+			}
 		}
 	}
 }
-- 
2.52.0

[PATCH v3 3/4] mm/mglru: skip cold PUD subtrees during aging

[Baoquan He]

From: Baoquan He <hebaoquan@kylinos.cn>

The aging walks into every PUD and runs the PMD-level Bloom filter on
each PMD. Add a coarser PUD-level filter one level up:

 - walk_pmd_range() reports whether the subtree held anything young for
   this lruvec. That is the same condition which already carries a PMD
   over into the next generation: a young PMD entry, a huge page owned by
   this lruvec, or PTEs with enough young ones to pass suitable_to_scan().
 - walk_pud_range() records that in the PUD filter, and
 - on subsequent generations, skips the whole PUD subtree when the filter
   says it had nothing young last generation.

Use (mm, PUD-aligned address) as the filter key rather than the PUD page
table pointer. It is a stable identity for the range being walked, is
available without walking the page tables in lru_gen_look_around(), and
does not depend on the lifetime of a page table page.

The double-buffered filter flips with each new iteration, so newly hot or
migrated-in pages are re-checked promptly rather than suppressed
indefinitely. force_scan walks bypass the PUD test, so manual aging and
newly added mms always rescan and re-populate the filter.

To keep hot regions marked, also report the covering PUD from the rmap
feedback path (lru_gen_look_around()), so regions whose hotness is only
observed by eviction will be re-scanned.

Suggested-by: Kairui Song <ryncsn@gmail.com>
Signed-off-by: Baoquan He <hebaoquan@kylinos.cn>
Signed-off-by: Baoquan He <baoquan.he@linux.dev>
---
 mm/vmscan.c | 45 ++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 38 insertions(+), 7 deletions(-)

diff --git a/mm/vmscan.c b/mm/vmscan.c
index 9dbb3f477d7d..d12934f2fbb3 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -3133,8 +3133,10 @@ static bool iterate_mm_list(struct lru_gen_mm_walk *walk, struct mm_struct **ite
 
 	spin_unlock(&mm_list->lock);
 
-	if (mm && first)
+	if (mm && first) {
 		reset_bloom_filter(mm_state, BLOOM_FILTER_PMD, walk->seq + 1);
+		reset_bloom_filter(mm_state, BLOOM_FILTER_PUD, walk->seq + 1);
+	}
 
 	if (*iter)
 		mmdrop(*iter);
@@ -3738,10 +3740,11 @@ static void walk_pmd_range_locked(pud_t *pud, unsigned long addr, struct vm_area
 	*first = -1;
 }
 
-static void walk_pmd_range(pud_t *pud, unsigned long start, unsigned long end,
+static bool walk_pmd_range(pud_t *pud, unsigned long start, unsigned long end,
 			   struct mm_walk *args)
 {
 	int i;
+	bool young = false;
 	pmd_t *pmd;
 	unsigned long next;
 	unsigned long addr;
@@ -3778,8 +3781,10 @@ static void walk_pmd_range(pud_t *pud, unsigned long start, unsigned long end,
 
 			walk->mm_stats[MM_LEAF_TOTAL]++;
 
-			if (pfn != -1)
+			if (pfn != -1) {
 				walk_pmd_range_locked(pud, addr, vma, args, bitmap, &first);
+				young = true;
+			}
 			continue;
 		}
 
@@ -3789,6 +3794,7 @@ static void walk_pmd_range(pud_t *pud, unsigned long start, unsigned long end,
 				continue;
 
 			walk_pmd_range_locked(pud, addr, vma, args, bitmap, &first);
+			young = true;
 		}
 
 		if (!walk->force_scan &&
@@ -3801,6 +3807,7 @@ static void walk_pmd_range(pud_t *pud, unsigned long start, unsigned long end,
 			continue;
 
 		walk->mm_stats[MM_NONLEAF_ADDED]++;
+		young = true;
 
 		/* carry over to the next generation */
 		update_bloom_filter(mm_state, BLOOM_FILTER_PMD, walk->seq + 1, pmd + i);
@@ -3810,6 +3817,8 @@ static void walk_pmd_range(pud_t *pud, unsigned long start, unsigned long end,
 
 	if (i < PTRS_PER_PMD && get_next_vma(PUD_MASK, PMD_SIZE, args, &start, &end))
 		goto restart;
+
+	return young;
 }
 
 static int walk_pud_range(p4d_t *p4d, unsigned long start, unsigned long end,
@@ -3820,6 +3829,7 @@ static int walk_pud_range(p4d_t *p4d, unsigned long start, unsigned long end,
 	unsigned long addr;
 	unsigned long next;
 	struct lru_gen_mm_walk *walk = args->private;
+	struct lru_gen_mm_state *mm_state = get_mm_state(walk->lruvec);
 
 	VM_WARN_ON_ONCE(p4d_leaf(*p4d));
 
@@ -3827,13 +3837,29 @@ static int walk_pud_range(p4d_t *p4d, unsigned long start, unsigned long end,
 restart:
 	for (i = pud_index(start), addr = start; addr != end; i++, addr = next) {
 		pud_t val = pudp_get(pud + i);
+		void *pud_key;
 
 		next = pud_addr_end(addr, end);
 
 		if (!pud_present(val) || WARN_ON_ONCE(pud_leaf(val)))
 			continue;
 
-		walk_pmd_range(pud + i, addr, next, args);
+		/*
+		 * Use (mm, PUD-aligned address) as the filter key instead of
+		 * the page table pointer. It is stable across the aging walk
+		 * and the rmap feedback path, and avoids walking the page
+		 * tables in lru_gen_look_around().
+		 */
+		pud_key = (void *)((unsigned long)args->mm ^ (addr & PUD_MASK));
+
+		/* Skip a subtree that had nothing young for this lruvec last gen */
+		if (!walk->force_scan &&
+		    !test_bloom_filter(mm_state, BLOOM_FILTER_PUD, walk->seq, pud_key))
+			continue;
+
+		if (walk_pmd_range(pud + i, addr, next, args))
+			update_bloom_filter(mm_state, BLOOM_FILTER_PUD, walk->seq + 1,
+					    pud_key);
 
 		if (need_resched() || walk->batched >= MAX_LRU_BATCH) {
 			end = (addr | ~PUD_MASK) + 1;
@@ -4437,9 +4463,14 @@ bool lru_gen_look_around(struct page_vma_mapped_walk *pvmw, unsigned int nr)
 	lazy_mmu_mode_disable();
 
 	/* feedback from rmap walkers to page table walkers */
-	if (mm_state && suitable_to_scan(i, young))
-		update_bloom_filter(mm_state, BLOOM_FILTER_PMD,
-				    READ_ONCE(lruvec->lrugen.max_seq), pvmw->pmd);
+	if (mm_state && suitable_to_scan(i, young)) {
+		unsigned long max_seq = READ_ONCE(lruvec->lrugen.max_seq);
+		void *pud_key = (void *)((unsigned long)vma->vm_mm ^
+					 (pvmw->address & PUD_MASK));
+
+		update_bloom_filter(mm_state, BLOOM_FILTER_PMD, max_seq, pvmw->pmd);
+		update_bloom_filter(mm_state, BLOOM_FILTER_PUD, max_seq, pud_key);
+	}
 
 	mem_cgroup_put(memcg);
 
-- 
2.52.0

[PATCH v3 4/4] mm/mglru: count PUD subtrees skipped by the PUD-level filter

[Baoquan He]

From: Baoquan He <hebaoquan@kylinos.cn>

Add MM_PUD_EMPTY_SKIPPED, incremented in walk_pud_range() whenever a PUD
subtree is skipped by the filter. Like other counters accumulated
per walk, shown in debugfs lru_gen output (the "S" column of TYFALWEES)
and via the mm_vmscan_lru_gen_walk tracepoint, so the avoided cost
by the filter can be measured directly.

Signed-off-by: Baoquan He <hebaoquan@kylinos.cn>
Signed-off-by: Baoquan He <baoquan.he@linux.dev>
---
 include/linux/mmzone.h |  1 +
 mm/trace_vmscan.h      | 10 ++++++----
 mm/vmscan.c            | 13 ++++++++-----
 3 files changed, 15 insertions(+), 9 deletions(-)

diff --git a/include/linux/mmzone.h b/include/linux/mmzone.h
index 1f086ef3a00e..857ff92d5e58 100644
--- a/include/linux/mmzone.h
+++ b/include/linux/mmzone.h
@@ -583,6 +583,7 @@ enum {
 	MM_WALK_TOTAL,		/* page-table walks completed */
 	MM_WALK_EMPTY,		/* walks that found no folio in this lruvec */
 	MM_LEAF_EMPTY_WALKS,	/* leaf entries scanned during empty walks */
+	MM_PUD_EMPTY_SKIPPED,	/* PUD subtrees skipped by the PUD-level filter */
 	NR_MM_STATS
 };
 
diff --git a/mm/trace_vmscan.h b/mm/trace_vmscan.h
index 4884fc7a35b9..8b31057d66da 100644
--- a/mm/trace_vmscan.h
+++ b/mm/trace_vmscan.h
@@ -766,9 +766,9 @@ TRACE_EVENT(mm_vmscan_kswapd_clear_hopeless,
 TRACE_EVENT(mm_vmscan_lru_gen_walk,
 
 	TP_PROTO(int nid, unsigned long seq, int leaf_total,
-		 int leaf_associated, bool empty),
+		 int leaf_associated, bool empty, int pud_skipped),
 
-	TP_ARGS(nid, seq, leaf_total, leaf_associated, empty),
+	TP_ARGS(nid, seq, leaf_total, leaf_associated, empty, pud_skipped),
 
 	TP_STRUCT__entry(
 		__field(int, nid)
@@ -776,6 +776,7 @@ TRACE_EVENT(mm_vmscan_lru_gen_walk,
 		__field(int, leaf_total)
 		__field(int, leaf_associated)
 		__field(bool, empty)
+		__field(int, pud_skipped)
 	),
 
 	TP_fast_assign(
@@ -784,11 +785,12 @@ TRACE_EVENT(mm_vmscan_lru_gen_walk,
 		__entry->leaf_total = leaf_total;
 		__entry->leaf_associated = leaf_associated;
 		__entry->empty = empty;
+		__entry->pud_skipped = pud_skipped;
 	),
 
-	TP_printk("nid=%d seq=%lu leaf_total=%d leaf_associated=%d empty=%d",
+	TP_printk("nid=%d seq=%lu leaf_total=%d leaf_associated=%d empty=%d pud_skipped=%d",
 		__entry->nid, __entry->seq, __entry->leaf_total,
-		__entry->leaf_associated, __entry->empty)
+		__entry->leaf_associated, __entry->empty, __entry->pud_skipped)
 );
 
 #endif /* _TRACE_VMSCAN_H */
diff --git a/mm/vmscan.c b/mm/vmscan.c
index d12934f2fbb3..88de6bd4f7ca 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -3854,8 +3854,10 @@ static int walk_pud_range(p4d_t *p4d, unsigned long start, unsigned long end,
 
 		/* Skip a subtree that had nothing young for this lruvec last gen */
 		if (!walk->force_scan &&
-		    !test_bloom_filter(mm_state, BLOOM_FILTER_PUD, walk->seq, pud_key))
+		    !test_bloom_filter(mm_state, BLOOM_FILTER_PUD, walk->seq, pud_key)) {
+			walk->mm_stats[MM_PUD_EMPTY_SKIPPED]++;
 			continue;
+		}
 
 		if (walk_pmd_range(pud + i, addr, next, args))
 			update_bloom_filter(mm_state, BLOOM_FILTER_PUD, walk->seq + 1,
@@ -4222,7 +4224,8 @@ static bool try_to_inc_max_seq(struct lruvec *lruvec, unsigned long seq,
 			trace_mm_vmscan_lru_gen_walk(
 					lruvec_pgdat(lruvec)->node_id, walk->seq,
 					walk->mm_stats[MM_LEAF_TOTAL],
-					walk->mm_stats[MM_LEAF_ASSOCIATED], empty);
+					walk->mm_stats[MM_LEAF_ASSOCIATED], empty,
+					walk->mm_stats[MM_PUD_EMPTY_SKIPPED]);
 		}
 	} while (mm);
 done:
@@ -5714,14 +5717,14 @@ static void lru_gen_seq_show_full(struct seq_file *m, struct lruvec *lruvec,
 
 	seq_puts(m, "                      ");
 	for (i = 0; i < NR_MM_STATS; i++) {
-		const char *s = "xxxxxxxx";
+		const char *s = "xxxxxxxxx";
 		unsigned long n = 0;
 
 		if (seq == max_seq && NR_HIST_GENS == 1) {
-			s = "TYFALWEE";
+			s = "TYFALWEES";
 			n = READ_ONCE(mm_state->stats[hist][i]);
 		} else if (seq != max_seq && NR_HIST_GENS > 1) {
-			s = "tyfalwee";
+			s = "tyfalwees";
 			n = READ_ONCE(mm_state->stats[hist][i]);
 		}
 
-- 
2.52.0