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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <f50f8ddd-2ce8-47dc-657e-7b0edf80a508@gmail.com>
Date: Wed, 2 Jul 2025 13:44:54 +0800
From: Hao Jia <jiahao.kernel@...il.com>
To: Yuanchu Xie <yuanchu@...gle.com>
Cc: akpm@...ux-foundation.org, hannes@...xchg.org, yuzhao@...gle.com,
 kinseyho@...gle.com, david@...hat.com, mhocko@...nel.org,
 zhengqi.arch@...edance.com, shakeel.butt@...ux.dev,
 lorenzo.stoakes@...cle.com, linux-mm@...ck.org,
 linux-kernel@...r.kernel.org, Hao Jia <jiahao1@...iang.com>
Subject: Re: [PATCH] mm/mglru: Stop try_to_inc_min_seq() if the oldest
 generation LRU lists are not empty



On 2025/7/2 08:31, Yuanchu Xie wrote:
> On Mon, Jun 30, 2025 at 1:06 AM Hao Jia <jiahao.kernel@...il.com> wrote:
>>
>> From: Hao Jia <jiahao1@...iang.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