[PATCH] mm/mglru: Stop try_to_inc_min_seq() if the oldest generation LRU lists are not empty

[PATCH] mm/mglru: Stop try_to_inc_min_seq() if the oldest generation LRU lists are not empty

[Hao Jia]

From: Hao Jia <jiahao1@lixiang.com>

In try_to_inc_min_seq(), if the oldest generation of LRU lists
(anonymous and file) are not empty. Then we should return directly
to avoid unnecessary subsequent overhead.

Corollary: If the lrugen->folios[gen][type][zone] lists of both
anonymous and file are not empty, try_to_inc_min_seq() will fail.

Proof: Taking LRU_GEN_ANON as an example, consider the following two cases:

Case 1: min_seq[LRU_GEN_ANON] <= seq (seq is lrugen->max_seq - MIN_NR_GENS)

Since min_seq[LRU_GEN_ANON] has not increased,
so min_seq[LRU_GEN_ANON] is still equal to lrugen->min_seq[LRU_GEN_ANON].
Therefore, in the following judgment:
min_seq[LRU_GEN_ANON] <= lrugen->min_seq[LRU_GEN_ANON] is always true.
So, we will not increase the seq of the oldest generation of anonymous,
and try_to_inc_min_seq() will return false.

case 2: min_seq[LRU_GEN_ANON] > seq (seq is lrugen->max_seq - MIN_NR_GENS)

If min_seq[LRU_GEN_ANON] > seq, that is, lrugen->min_seq[LRU_GEN_ANON] > seq
Then min_seq[LRU_GEN_ANON] is assigned seq.
Therefore, in the following judgment:
min_seq[LRU_GEN_ANON] (seq) <= lrugen->min_seq[LRU_GEN_ANON] is always true.
So, we will not update the oldest generation seq of anonymous,
and try_to_inc_min_seq() will return false.

It is similar for LRU_GEN_FILE. Therefore, in try_to_inc_min_seq(),
if the oldest generation LRU lists (anonymous and file) are not empty,
in other words, min_seq[type] has not increased.
we can directly return false to avoid unnecessary checking overhead later.

Signed-off-by: Hao Jia <jiahao1@lixiang.com>
---
 mm/vmscan.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/mm/vmscan.c b/mm/vmscan.c
index f8dfd2864bbf..3ba63d87563f 100644
--- a/mm/vmscan.c
+++ b/mm/vmscan.c
@@ -3928,6 +3928,7 @@ static bool try_to_inc_min_seq(struct lruvec *lruvec, int swappiness)
 	int gen, type, zone;
 	bool success = false;
 	struct lru_gen_folio *lrugen = &lruvec->lrugen;
+	int seq_inc_flags[ANON_AND_FILE] = {0};
 	DEFINE_MIN_SEQ(lruvec);
 
 	VM_WARN_ON_ONCE(!seq_is_valid(lruvec));
@@ -3943,11 +3944,20 @@ static bool try_to_inc_min_seq(struct lruvec *lruvec, int swappiness)
 			}
 
 			min_seq[type]++;
+			seq_inc_flags[type] = 1;
 		}
 next:
 		;
 	}
 
+	/*
+	 * If the oldest generation of LRU lists (anonymous and file)
+	 * are not empty, we can directly return false to avoid unnecessary
+	 * checking overhead later.
+	 */
+	if (!seq_inc_flags[LRU_GEN_ANON] && !seq_inc_flags[LRU_GEN_FILE])
+		return success;
+
 	/* see the comment on lru_gen_folio */
 	if (swappiness && swappiness <= MAX_SWAPPINESS) {
 		unsigned long seq = lrugen->max_seq - MIN_NR_GENS;
-- 
2.34.1

Re: [PATCH] mm/mglru: Stop try_to_inc_min_seq() if the oldest generation LRU lists are not empty

[Yuanchu Xie]

On Mon, Jun 30, 2025 at 1:06 AM Hao Jia <jiahao.kernel@gmail.com> wrote:
>
> From: Hao Jia <jiahao1@lixiang.com>
>
> In try_to_inc_min_seq(), if the oldest generation of LRU lists
> (anonymous and file) are not empty. Then we should return directly
> to avoid unnecessary subsequent overhead.
>
> Corollary: If the lrugen->folios[gen][type][zone] lists of both
> anonymous and file are not empty, try_to_inc_min_seq() will fail.
>
> Proof: Taking LRU_GEN_ANON as an example, consider the following two cases:
>
> Case 1: min_seq[LRU_GEN_ANON] <= seq (seq is lrugen->max_seq - MIN_NR_GENS)
>
> Since min_seq[LRU_GEN_ANON] has not increased,
> so min_seq[LRU_GEN_ANON] is still equal to lrugen->min_seq[LRU_GEN_ANON].
> Therefore, in the following judgment:
> min_seq[LRU_GEN_ANON] <= lrugen->min_seq[LRU_GEN_ANON] is always true.
> So, we will not increase the seq of the oldest generation of anonymous,
> and try_to_inc_min_seq() will return false.
>
> case 2: min_seq[LRU_GEN_ANON] > seq (seq is lrugen->max_seq - MIN_NR_GENS)
>
> If min_seq[LRU_GEN_ANON] > seq, that is, lrugen->min_seq[LRU_GEN_ANON] > seq
This part doesn't make sense to me.
The code is as follows:

    /* find the oldest populated generation */
    for_each_evictable_type(type, swappiness) {
        while (min_seq[type] + MIN_NR_GENS <= lrugen->max_seq) {
            gen = lru_gen_from_seq(min_seq[type]);

            for (zone = 0; zone < MAX_NR_ZONES; zone++) {
                if (!list_empty(&lrugen->folios[gen][type][zone]))
                    goto next;
            }

            min_seq[type]++;
        }

Here, it could be that , min_seq[type] > lrugen->max_seq - MIN_NR_GENS
(what you refer to as seq)
However, this is a result of incrementing a copy of
lrugen->min_seq[type] as this piece of code finds the oldest populated
generation.

next:
        ;
    }

> Then min_seq[LRU_GEN_ANON] is assigned seq.
This is not necessarily true, because swappiness can be 0, and the
assignments happen to prevent one LRU type from going more than 1 gen
past the other.
so if `min_seq[LRU_GEN_ANON] > seq && min_seq[LRU_GEN_FILE] == seq` is
true, then min_seq[LRU_GEN_ANON] is not assigned seq.


> Therefore, in the following judgment:
> min_seq[LRU_GEN_ANON] (seq) <= lrugen->min_seq[LRU_GEN_ANON] is always true.
> So, we will not update the oldest generation seq of anonymous,
> and try_to_inc_min_seq() will return false.
>
> It is similar for LRU_GEN_FILE. Therefore, in try_to_inc_min_seq(),
> if the oldest generation LRU lists (anonymous and file) are not empty,
> in other words, min_seq[type] has not increased.
> we can directly return false to avoid unnecessary checking overhead later.
Yeah I don't think this proof holds. If you think it does please
elaborate more and make your assumptions more clear.

>
> Signed-off-by: Hao Jia <jiahao1@lixiang.com>
> ---
>  mm/vmscan.c | 10 ++++++++++
>  1 file changed, 10 insertions(+)
>
> diff --git a/mm/vmscan.c b/mm/vmscan.c
> index f8dfd2864bbf..3ba63d87563f 100644
> --- a/mm/vmscan.c
> +++ b/mm/vmscan.c
> @@ -3928,6 +3928,7 @@ static bool try_to_inc_min_seq(struct lruvec *lruvec, int swappiness)
>         int gen, type, zone;
>         bool success = false;
>         struct lru_gen_folio *lrugen = &lruvec->lrugen;
> +       int seq_inc_flags[ANON_AND_FILE] = {0};
>         DEFINE_MIN_SEQ(lruvec);
>
>         VM_WARN_ON_ONCE(!seq_is_valid(lruvec));
> @@ -3943,11 +3944,20 @@ static bool try_to_inc_min_seq(struct lruvec *lruvec, int swappiness)
>                         }
>
>                         min_seq[type]++;
> +                       seq_inc_flags[type] = 1;
>                 }
>  next:
>                 ;
>         }
>
> +       /*
> +        * If the oldest generation of LRU lists (anonymous and file)
> +        * are not empty, we can directly return false to avoid unnecessary
> +        * checking overhead later.
> +        */
> +       if (!seq_inc_flags[LRU_GEN_ANON] && !seq_inc_flags[LRU_GEN_FILE])
> +               return success;
> +
>         /* see the comment on lru_gen_folio */
>         if (swappiness && swappiness <= MAX_SWAPPINESS) {
>                 unsigned long seq = lrugen->max_seq - MIN_NR_GENS;
> --
> 2.34.1
>
>
I don't understand what problem this patch tries to solve.

Yuanchu

Re: [PATCH] mm/mglru: Stop try_to_inc_min_seq() if the oldest generation LRU lists are not empty

[Hao Jia]

On 2025/7/2 08:31, Yuanchu Xie wrote:

Sorry, I got my email wrong. I'll reply again to make sure the kernel 
mail lists can receive it.

> On Mon, Jun 30, 2025 at 1:06 AM Hao Jia <jiahao.kernel@gmail.com> wrote:
>>
>> From: Hao Jia <jiahao1@lixiang.com>
>>
>> In try_to_inc_min_seq(), if the oldest generation of LRU lists
>> (anonymous and file) are not empty. Then we should return directly
>> to avoid unnecessary subsequent overhead.
>>
>> Corollary: If the lrugen->folios[gen][type][zone] lists of both
>> anonymous and file are not empty, try_to_inc_min_seq() will fail.
>>
>> Proof: Taking LRU_GEN_ANON as an example, consider the following two cases:
>>
>> Case 1: min_seq[LRU_GEN_ANON] <= seq (seq is lrugen->max_seq - MIN_NR_GENS)
>>
>> Since min_seq[LRU_GEN_ANON] has not increased,
>> so min_seq[LRU_GEN_ANON] is still equal to lrugen->min_seq[LRU_GEN_ANON].
>> Therefore, in the following judgment:
>> min_seq[LRU_GEN_ANON] <= lrugen->min_seq[LRU_GEN_ANON] is always true.
>> So, we will not increase the seq of the oldest generation of anonymous,
>> and try_to_inc_min_seq() will return false.
>>
>> case 2: min_seq[LRU_GEN_ANON] > seq (seq is lrugen->max_seq - MIN_NR_GENS)
>>
>> If min_seq[LRU_GEN_ANON] > seq, that is, lrugen->min_seq[LRU_GEN_ANON] > seq
> This part doesn't make sense to me.
> The code is as follows:
> 
>      /* find the oldest populated generation */
>      for_each_evictable_type(type, swappiness) {
>          while (min_seq[type] + MIN_NR_GENS <= lrugen->max_seq) {
>              gen = lru_gen_from_seq(min_seq[type]);
> 
>              for (zone = 0; zone < MAX_NR_ZONES; zone++) {
>                  if (!list_empty(&lrugen->folios[gen][type][zone]))
>                      goto next;
>              }
> 
>              min_seq[type]++;
>          }
> 
> Here, it could be that , min_seq[type] > lrugen->max_seq - MIN_NR_GENS
> (what you refer to as seq)
> However, this is a result of incrementing a copy of
> lrugen->min_seq[type] as this piece of code finds the oldest populated
> generation.
> 

Hi, Yuanchu

Sorry for the confusion.

I am assuming that if the oldest generation LRU lists (anonymous and
file) are not empty, in other words, *min_seq[type]* has not increased.

The above part has been executed, and it is known that min_seq[type] has
not increased（that is, min_seq[type]=lrugen->min_seq[type] at this
time）, so the rest of the reasoning.

Maybe you mean that under the above premise min_seq[type] is impossible
to be greater than seq (seq is lrugen->max_seq - MIN_NR_GENS)?
If so, case2 does not need to be discussed and reasoned.

In either case, my patch will work well.

Thanks,
Hao

> next:
>          ;
>      }
> 
>> Then min_seq[LRU_GEN_ANON] is assigned seq.
> This is not necessarily true, because swappiness can be 0, and the
> assignments happen to prevent one LRU type from going more than 1 gen
> past the other.
> so if `min_seq[LRU_GEN_ANON] > seq && min_seq[LRU_GEN_FILE] == seq` is
> true, then min_seq[LRU_GEN_ANON] is not assigned seq.
> 

Yes, if min_seq[LRU_GEN_ANON] is not assigned seq, then the situation is
the same as case 1. min_seq[LRU_GEN_ANON] is equal to
lrugen->min_seq[LRU_GEN_ANON].
in the following judgment:
min_seq[LRU_GEN_ANON] <= lrugen->min_seq[LRU_GEN_ANON] is always true.


Case 2 wants to discuss another situation, that is, when
min_seq[LRU_GEN_ANON] is assigned to seq. The following judgment is
whether min_seq[LRU_GEN_ANON] <= lrugen->min_seq[LRU_GEN_ANON] is always
true.


> 
>> Therefore, in the following judgment:
>> min_seq[LRU_GEN_ANON] (seq) <= lrugen->min_seq[LRU_GEN_ANON] is always true.
>> So, we will not update the oldest generation seq of anonymous,
>> and try_to_inc_min_seq() will return false.
>>
>> It is similar for LRU_GEN_FILE. Therefore, in try_to_inc_min_seq(),
>> if the oldest generation LRU lists (anonymous and file) are not empty,
>> in other words, min_seq[type] has not increased.
>> we can directly return false to avoid unnecessary checking overhead later.
> Yeah I don't think this proof holds. If you think it does please
> elaborate more and make your assumptions more clear.
> 
>>
>> Signed-off-by: Hao Jia <jiahao1@lixiang.com>
>> ---
>>   mm/vmscan.c | 10 ++++++++++
>>   1 file changed, 10 insertions(+)
>>
>> diff --git a/mm/vmscan.c b/mm/vmscan.c
>> index f8dfd2864bbf..3ba63d87563f 100644
>> --- a/mm/vmscan.c
>> +++ b/mm/vmscan.c
>> @@ -3928,6 +3928,7 @@ static bool try_to_inc_min_seq(struct lruvec *lruvec, int swappiness)
>>          int gen, type, zone;
>>          bool success = false;
>>          struct lru_gen_folio *lrugen = &lruvec->lrugen;
>> +       int seq_inc_flags[ANON_AND_FILE] = {0};
>>          DEFINE_MIN_SEQ(lruvec);
>>
>>          VM_WARN_ON_ONCE(!seq_is_valid(lruvec));
>> @@ -3943,11 +3944,20 @@ static bool try_to_inc_min_seq(struct lruvec *lruvec, int swappiness)
>>                          }
>>
>>                          min_seq[type]++;
>> +                       seq_inc_flags[type] = 1;
>>                  }
>>   next:
>>                  ;
>>          }
>>
>> +       /*
>> +        * If the oldest generation of LRU lists (anonymous and file)
>> +        * are not empty, we can directly return false to avoid unnecessary
>> +        * checking overhead later.
>> +        */
>> +       if (!seq_inc_flags[LRU_GEN_ANON] && !seq_inc_flags[LRU_GEN_FILE])
>> +               return success;
>> +
>>          /* see the comment on lru_gen_folio */
>>          if (swappiness && swappiness <= MAX_SWAPPINESS) {
>>                  unsigned long seq = lrugen->max_seq - MIN_NR_GENS;
>> --
>> 2.34.1
>>
>>
> I don't understand what problem this patch tries to solve.
> 
> Yuanchu

My pathch is that if we already know that min_seq[type] (including
anonymous and file) has not increased, we can directly let
try_to_inc_min_seq() return failure to reduce unnecessary checking
overhead later. After my above reasoning, this does not change the
original behavior of try_to_inc_min_seq().

I added some code to count the number of try_to_inc_min_seq() calls and
the number of times the situation mentioned in my patch is hit.

Run the test in tools/testing/selftests/cgroup/test_memcontrol on my
machine.

hit_cnt: 1215 total_cnt: 1702
The hit rate is about 71%

Thanks,
Hao

Re: [PATCH] mm/mglru: Stop try_to_inc_min_seq() if the oldest generation LRU lists are not empty

[Hao Jia]

On 2025/7/2 08:31, Yuanchu Xie wrote:
> On Mon, Jun 30, 2025 at 1:06 AM Hao Jia <jiahao.kernel@gmail.com> wrote:
>>
>> From: Hao Jia <jiahao1@lixiang.com>
>>
>> In try_to_inc_min_seq(), if the oldest generation of LRU lists
>> (anonymous and file) are not empty. Then we should return directly
>> to avoid unnecessary subsequent overhead.
>>
>> Corollary: If the lrugen->folios[gen][type][zone] lists of both
>> anonymous and file are not empty, try_to_inc_min_seq() will fail.
>>
>> Proof: Taking LRU_GEN_ANON as an example, consider the following two cases:
>>
>> Case 1: min_seq[LRU_GEN_ANON] <= seq (seq is lrugen->max_seq - MIN_NR_GENS)
>>
>> Since min_seq[LRU_GEN_ANON] has not increased,
>> so min_seq[LRU_GEN_ANON] is still equal to lrugen->min_seq[LRU_GEN_ANON].
>> Therefore, in the following judgment:
>> min_seq[LRU_GEN_ANON] <= lrugen->min_seq[LRU_GEN_ANON] is always true.
>> So, we will not increase the seq of the oldest generation of anonymous,
>> and try_to_inc_min_seq() will return false.
>>
>> case 2: min_seq[LRU_GEN_ANON] > seq (seq is lrugen->max_seq - MIN_NR_GENS)
>>
>> If min_seq[LRU_GEN_ANON] > seq, that is, lrugen->min_seq[LRU_GEN_ANON] > seq
> This part doesn't make sense to me.
> The code is as follows:
> 
>      /* find the oldest populated generation */
>      for_each_evictable_type(type, swappiness) {
>          while (min_seq[type] + MIN_NR_GENS <= lrugen->max_seq) {
>              gen = lru_gen_from_seq(min_seq[type]);
> 
>              for (zone = 0; zone < MAX_NR_ZONES; zone++) {
>                  if (!list_empty(&lrugen->folios[gen][type][zone]))
>                      goto next;
>              }
> 
>              min_seq[type]++;
>          }
> 
> Here, it could be that , min_seq[type] > lrugen->max_seq - MIN_NR_GENS
> (what you refer to as seq)
> However, this is a result of incrementing a copy of
> lrugen->min_seq[type] as this piece of code finds the oldest populated
> generation.
> 
> next:
>          ;
>      }
> 
>> Then min_seq[LRU_GEN_ANON] is assigned seq.
> This is not necessarily true, because swappiness can be 0, and the
> assignments happen to prevent one LRU type from going more than 1 gen
> past the other.
> so if `min_seq[LRU_GEN_ANON] > seq && min_seq[LRU_GEN_FILE] == seq` is
> true, then min_seq[LRU_GEN_ANON] is not assigned seq.
> 
> 
>> Therefore, in the following judgment:
>> min_seq[LRU_GEN_ANON] (seq) <= lrugen->min_seq[LRU_GEN_ANON] is always true.
>> So, we will not update the oldest generation seq of anonymous,
>> and try_to_inc_min_seq() will return false.
>>
>> It is similar for LRU_GEN_FILE. Therefore, in try_to_inc_min_seq(),
>> if the oldest generation LRU lists (anonymous and file) are not empty,
>> in other words, min_seq[type] has not increased.
>> we can directly return false to avoid unnecessary checking overhead later.
> Yeah I don't think this proof holds. If you think it does please
> elaborate more and make your assumptions more clear.
> 

Perhaps another way to explain it is clearer.

It is known that min_seq[type] has not increased, that is, min_seq[type] 
is equal to lrugen->min_seq[type], then the following:

case 1: min_seq[type] has not been reassigned and changed before 
judgment min_seq[type] <= lrugen->min_seq[type].

Then the subsequent min_seq[type] <= lrugen->min_seq[type] judgment will 
always be true.


case 2: min_seq[type] is reassigned to seq, before judgment 
min_seq[type] <= lrugen->min_seq[type].

Then at least the condition of min_seq[type] > seq must be met before 
min_seq[type] will be reassigned to seq.
That is to say, before the reassignment, lrugen->min_seq[type] > seq is 
met, and then min_seq[type] = seq.

Then the following min_seq[type]（seq） <= lrugen->min_seq[type] judgment 
is always true.


Thanks,
Hao

Re: [PATCH] mm/mglru: Stop try_to_inc_min_seq() if the oldest generation LRU lists are not empty

[Yuanchu Xie]

On Tue, Jul 1, 2025 at 10:45 PM Hao Jia <jiahao.kernel@gmail.com> wrote:
>
> Perhaps another way to explain it is clearer.
>
> It is known that min_seq[type] has not increased, that is, min_seq[type]
> is equal to lrugen->min_seq[type], then the following:
>
> case 1: min_seq[type] has not been reassigned and changed before
> judgment min_seq[type] <= lrugen->min_seq[type].
>
> Then the subsequent min_seq[type] <= lrugen->min_seq[type] judgment will
> always be true.
>
>
> case 2: min_seq[type] is reassigned to seq, before judgment
> min_seq[type] <= lrugen->min_seq[type].
>
> Then at least the condition of min_seq[type] > seq must be met before
> min_seq[type] will be reassigned to seq.
> That is to say, before the reassignment, lrugen->min_seq[type] > seq is
> met, and then min_seq[type] = seq.
>
> Then the following min_seq[type]（seq） <= lrugen->min_seq[type] judgment
> is always true.

This sounds good to me. Can you change the code to use one bool to
detect any increments in `min_seq[type]`? You don't need `int
seq_inc_flags[ANON_AND_FILE] = {0};`

Also update the commit message with what you have here. IMO much more clear.

Thanks,
Yuanchu

Re: [PATCH] mm/mglru: Stop try_to_inc_min_seq() if the oldest generation LRU lists are not empty

[Hao Jia]

On 2025/7/3 03:22, Yuanchu Xie wrote:
> On Tue, Jul 1, 2025 at 10:45 PM Hao Jia <jiahao.kernel@gmail.com> wrote:
>>
>> Perhaps another way to explain it is clearer.
>>
>> It is known that min_seq[type] has not increased, that is, min_seq[type]
>> is equal to lrugen->min_seq[type], then the following:
>>
>> case 1: min_seq[type] has not been reassigned and changed before
>> judgment min_seq[type] <= lrugen->min_seq[type].
>>
>> Then the subsequent min_seq[type] <= lrugen->min_seq[type] judgment will
>> always be true.
>>
>>
>> case 2: min_seq[type] is reassigned to seq, before judgment
>> min_seq[type] <= lrugen->min_seq[type].
>>
>> Then at least the condition of min_seq[type] > seq must be met before
>> min_seq[type] will be reassigned to seq.
>> That is to say, before the reassignment, lrugen->min_seq[type] > seq is
>> met, and then min_seq[type] = seq.
>>
>> Then the following min_seq[type]（seq） <= lrugen->min_seq[type] judgment
>> is always true.
> 
> This sounds good to me. Can you change the code to use one bool to
> detect any increments in `min_seq[type]`? You don't need `int
> seq_inc_flags[ANON_AND_FILE] = {0};`
> 
> Also update the commit message with what you have here. IMO much more clear.
> 

Thanks for your review, I have done it in patch v2.

Link to v2:
https://lore.kernel.org/all/20250703023946.65315-1-jiahao.kernel@gmail.com/

Thanks,
Hao