linux-kernel - Re: [PATCH v9 06/14] mm: multi-gen LRU: minimal implementation

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: <CAOUHufYmUPZY0gCC+wYk6Vr1L8KEx+tJeEAhjpBfUnLJsAHq5A@mail.gmail.com>
Date:   Mon, 21 Mar 2022 18:30:06 -0600
From:   Yu Zhao <yuzhao@...gle.com>
To:     Barry Song <21cnbao@...il.com>
Cc:     Andrew Morton <akpm@...ux-foundation.org>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Andi Kleen <ak@...ux.intel.com>,
        Aneesh Kumar <aneesh.kumar@...ux.ibm.com>,
        Catalin Marinas <catalin.marinas@....com>,
        Dave Hansen <dave.hansen@...ux.intel.com>,
        Hillf Danton <hdanton@...a.com>, Jens Axboe <axboe@...nel.dk>,
        Jesse Barnes <jsbarnes@...gle.com>,
        Johannes Weiner <hannes@...xchg.org>,
        Jonathan Corbet <corbet@....net>,
        Matthew Wilcox <willy@...radead.org>,
        Mel Gorman <mgorman@...e.de>,
        Michael Larabel <Michael@...haellarabel.com>,
        Michal Hocko <mhocko@...nel.org>,
        Mike Rapoport <rppt@...nel.org>,
        Rik van Riel <riel@...riel.com>,
        Vlastimil Babka <vbabka@...e.cz>,
        Will Deacon <will@...nel.org>,
        Ying Huang <ying.huang@...el.com>,
        LAK <linux-arm-kernel@...ts.infradead.org>,
        Linux Doc Mailing List <linux-doc@...r.kernel.org>,
        LKML <linux-kernel@...r.kernel.org>,
        Linux-MM <linux-mm@...ck.org>,
        Kernel Page Reclaim v2 <page-reclaim@...gle.com>,
        x86 <x86@...nel.org>, Brian Geffon <bgeffon@...gle.com>,
        Jan Alexander Steffens <heftig@...hlinux.org>,
        Oleksandr Natalenko <oleksandr@...alenko.name>,
        Steven Barrett <steven@...uorix.net>,
        Suleiman Souhlal <suleiman@...gle.com>,
        Daniel Byrne <djbyrne@....edu>,
        Donald Carr <d@...os-reins.com>,
        Holger Hoffstätte <holger@...lied-asynchrony.com>,
        Konstantin Kharlamov <Hi-Angel@...dex.ru>,
        Shuang Zhai <szhai2@...rochester.edu>,
        Sofia Trinh <sofia.trinh@....works>,
        Vaibhav Jain <vaibhav@...ux.ibm.com>
Subject: Re: [PATCH v9 06/14] mm: multi-gen LRU: minimal implementation

On Sat, Mar 19, 2022 at 5:15 AM Barry Song <21cnbao@...il.com> wrote:
>
> > +                            unsigned long *min_seq, bool can_swap, bool *need_aging)
> > +{
> > +       int gen, type, zone;
> > +       long old = 0;
> > +       long young = 0;
> > +       long total = 0;
> > +       struct lru_gen_struct *lrugen = &lruvec->lrugen;
> > +
> > +       for (type = !can_swap; type < ANON_AND_FILE; type++) {
> > +               unsigned long seq;
> > +
> > +               for (seq = min_seq[type]; seq <= max_seq; seq++) {
> > +                       long size = 0;
> > +
> > +                       gen = lru_gen_from_seq(seq);
> > +
> > +                       for (zone = 0; zone < MAX_NR_ZONES; zone++)
> > +                               size += READ_ONCE(lrugen->nr_pages[gen][type][zone]);
> > +
> > +                       total += size;
> > +                       if (seq == max_seq)
> > +                               young += size;
> > +                       if (seq + MIN_NR_GENS == max_seq)
> > +                               old += size;
> > +               }
> > +       }
> > +
> > +       /* try to spread pages out across MIN_NR_GENS+1 generations */
> > +       if (min_seq[LRU_GEN_FILE] + MIN_NR_GENS > max_seq)
> > +               *need_aging = true;
> > +       else if (min_seq[LRU_GEN_FILE] + MIN_NR_GENS < max_seq)
> > +               *need_aging = false;
> > +       else if (young * MIN_NR_GENS > total)
> > +               *need_aging = true;
>
> Could we have some doc here?

Will do.

> Given MIN_NR_GENS=2 and MAX_NR_GENS=4,
> it seems you mean if we have three generations and the youngest pages are more
> than 1/2 of the total pages, we need aging?

Yes.

> > +       else if (old * (MIN_NR_GENS + 2) < total)
> > +               *need_aging = true;
>
> it seems you mean if the oldest pages are less than 1/4 of the total pages,
> we need aging?

Yes.

> Can we have comments to explain why here?
>
> your commit message only says " The aging produces young generations.
> Given an lruvec, it increments max_seq when max_seq-min_seq+1
> approaches MIN_NR_GENS." it can't explain what the code is doing
> here.

Fair enough. Approaching MIN_NR_GENS=2 means getting close to it. From
the consumer's POV, if it *reaches* 2, the eviction will have to
stall, because the two youngest generations are not yet fully aged,
i.e., the second chance policy similar to the active/inactive lru.
>From the producer's POV, the aging tries to be lazy to reduce the
overhead. So ideally, we want 3 generations, which gives a reasonable
range [2, 4], hence the first two if's.

In addition, we want pages to spread out evenly over these 3
generations, meaning an average 1/3 of total pages for each
generation, which gives another reasonable range [1/2, 1/4]. Since the
eviction reduces the number of old pages, we only need to check
against the lower bound, i.e., 1/4. On the other hand, page (re)faults
increase the number of young pages, so in this case, we need to check
against the upper bound.

I'll include these details in the next spin.