linux-kernel - Re: [PATCH v9 07/14] mm: multi-gen LRU: exploit locality in rmap

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] [day] [month] [year] [list]

Message-ID: <CAOUHufbU=Uov54da8u9AqEuP0Y-1T2Khgd5Br-AhTfP=jbM1mA@mail.gmail.com>
Date:   Thu, 7 Apr 2022 17:51:50 -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 07/14] mm: multi-gen LRU: exploit locality in rmap

On Wed, Apr 6, 2022 at 9:46 PM Barry Song <21cnbao@...il.com> wrote:
>
> On Thu, Apr 7, 2022 at 3:04 PM Yu Zhao <yuzhao@...gle.com> wrote:
> >
> > On Wed, Apr 6, 2022 at 8:29 PM Barry Song <21cnbao@...il.com> wrote:
> > >
> > > On Wed, Mar 9, 2022 at 3:48 PM Yu Zhao <yuzhao@...gle.com> wrote:
> > > >
> > > > Searching the rmap for PTEs mapping each page on an LRU list (to test
> > > > and clear the accessed bit) can be expensive because pages from
> > > > different VMAs (PA space) are not cache friendly to the rmap (VA
> > > > space). For workloads mostly using mapped pages, the rmap has a high
> > > > CPU cost in the reclaim path.
> > > >
> > > > This patch exploits spatial locality to reduce the trips into the
> > > > rmap. When shrink_page_list() walks the rmap and finds a young PTE, a
> > > > new function lru_gen_look_around() scans at most BITS_PER_LONG-1
> > > > adjacent PTEs. On finding another young PTE, it clears the accessed
> > > > bit and updates the gen counter of the page mapped by this PTE to
> > > > (max_seq%MAX_NR_GENS)+1.
> > >
> > > Hi Yu,
> > > It seems an interesting feature to save the cost of rmap. but will it lead to
> > > possible judging of cold pages as hot pages?
> > > In case a page is mapped by 20 processes,  and it has been accessed
> > > by 5 of them, when we look around one of the 5 processes, the page
> > > will be young and this pte is cleared. but we still have 4 ptes which are not
> > > cleared. then we don't access the page for a long time, but the 4 uncleared
> > > PTEs will still make the page "hot" since they are not cleared, we will find
> > > the page is hot either due to look-arounding the 4 processes or rmapping
> > > the page later?
> >
> > Why are the remaining 4 accessed PTEs skipped? The rmap should check
> > all the 20 PTEs.
>
> for example page A is the neighbour of page B in process 1, when we do rmap
> for B, we look-around and clear A's pte in process 1. but A's ptes are
> still set in
> process 2,3,4,5.

It makes no difference because it's too insignificant. The goal is not
to give several million pages unique timestamps and sort them; it's to
partition pages on the orders one tenth to a few seconds and quickly
find some reasonable candidates. Temporal locality gets weaker
exponentially over time. Even on small systems, the difference is not
measurable if several thousand pages used in the last few seconds are
chosen over another several thousand pages used in the last minute.