linux-kernel - Re: [LSF/MM/BPF TOPIC] Physical LRU scanning feasibility

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: <964997a9-3604-49e7-aedf-f9d2fbec22a9@lucifer.local>
Date: Thu, 9 Jan 2025 12:38:11 +0000
From: Lorenzo Stoakes <lorenzo.stoakes@...cle.com>
To: Yosry Ahmed <yosryahmed@...gle.com>
Cc: lsf-pc@...ts.linux-foundation.org, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org, Matthew Wilcox <willy@...radead.org>,
        Axel Rasmussen <axelrasmussen@...gle.com>,
        Guru Anbalagane <gurua@...gle.com>, Wei Xu <weixugc@...gle.com>,
        Yuanchu Xie <yuanchu@...gle.com>
Subject: Re: [LSF/MM/BPF TOPIC] Physical LRU scanning feasibility

On Wed, Jan 08, 2025 at 02:33:01PM -0800, Yosry Ahmed wrote:
> On Wed, Jan 8, 2025 at 1:46 PM Lorenzo Stoakes
> <lorenzo.stoakes@...cle.com> wrote:
> >
> > Hi all,
> >
> > Not too long ago I took some time to investigate the possibility of
> > scanning physical memory directly by traversing the memory map directly
> > rather than the LRU linked list.
> >
> > This was inspired by a post from Matthew [0] wherein he demonstrated just
> > how significant the difference is between traversing arrays of contiguous
> > data on a modern system vs. the almost worst-case scenario of traversing a
> > linked-list.
> >
> > I tested how this might look by implementing code which simply traverses
> > and filters the memory map for LRU pages, simplifying as much as possible.
> >
> > However no matter which machine (ranging from 16 GB - 192 GB) or whether
> > virtualised or real hardware, I found unfortunately disappointing results -
> > the act of having to scan such a large range of memory resulted in
> > performance significantly less than a typical LRU scan at low memory
> > utilisation and performance at best matching LRU scanning at high memory
> > utilisation (simulating higher memory pressure).
> >
> > There are a number of factors at play here, and perhaps the shrinkage of
> > struct page (allowing for denser placement in cache lines), or an improved
> > algorithm might lead to more promising results.
> >
> > Having discussed this with Matthew, he suggested I put forward a proposal
> > to discuss this area in order that we can learn from this should it appear
> > this approach is unworkable or perhaps determine whether there might be
> > something to this that we might still salvage.
> >
> > I intend to do some more research and generate some more specific numbers
> > (feel free to give feedback here) before LSF so we can have something more
> > specific to talk about.
> >
> > I always envisioned this approach being somehow integrated with MGLRU and I
> > wonder if some hybrid means of integrating this approach with the MGLRU one
> > might make sense, which could also be another area of discussion.
>
> When I read this proposal the first thing that came to mind was memcg
> reclaim. While it seems to me that it is already inefficient to scan
> all physical memory looking for a possible reclaim candidate, it seems
> even more inefficient to try to find a possible reclaim candidate
> within the needed memcg. We'll also probably do a lot of repeated
> scanning as we iterate memcgs. The per-memcg per-node LRUs save us
> from this.

Indeed the memcg and cgroup side of this is a big bug bear of this
approach, I was initially investigating from the global reclaim pespective,
but one would _absolutely_ have to have a good answer as to how to proceed
in this instances.

I suspect any workable version of this approach will involve some kind of
hybrid approach.

If we consider the issues arising from the current use of linked lists they
are:

1. LRU lock contention (probably by far the prime concern)
2. The horrible cache performance of linked list traversal.

So perhaps use of an appropriate data structure might improve things (maple
tree seems a candidate, though whether appropriate I am not sure), though
in considering this one has also to be very very concerned about potential
'ironic' memory overhead in using such a data structure, ironic because
reclaim is our last gasp attempt to free memory, so needing to allocate it
becomes problematic under memory pressure...

I wonder whether one might consider some sort of physical stratification of
memory based on memcg, but that seems likely unworkable especially in light
of zone constraints.

>
> Do you have an idea about handling memcg reclaim efficiently?

So in short, no :>) but 100% acked that this is a fundamental issue here.

I will do some more research on this though in preparation for further
discussion.