[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]

[-- Attachment #1: Type: text/plain, Size: 7323 bytes --]

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.
> 

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

声明：这封邮件只允许文件接收者阅读，有很高的机密性要求。禁止其他人使用、打开、复制或转发里面的任何内容。如果本邮件错误地发给了你，请联系邮件发出者并删除这个文件。机密及法律的特权并不因为误发邮件而放弃或丧失。任何提出的观点或意见只属于作者的个人见解，并不一定代表本公司。
Disclaimer: This email is intended to be read only by the designated recipient of the document and has high confidentiality requirements. Anyone else is prohibited from using, opening, copying or forwarding any of the contents inside. If this email was sent to you by mistake, please contact the sender of the email and delete this file immediately. Confidentiality and legal privileges are not waived or lost by misdirected emails. Any views or opinions expressed in the email are those of the author and do not necessarily represent those of the Company.


[-- Attachment #2: Type: text/html, Size: 9090 bytes --]

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