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: <947c153e-72ff-421f-8042-c636c196b831@lucifer.local>
Date: Sat, 22 Feb 2025 19:12:04 +0000
From: Lorenzo Stoakes <lorenzo.stoakes@...cle.com>
To: lsf-pc@...ts.linux-foundation.org
Cc: 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

Hi all,

Apologies I feel I've bitten off more than I can chew especially given
current workload. I'd like to focus on my anon_vma topic, so I'm going to
have to drop this one on physical LRU scanning.

If anybody else would like to lead feel free, but I think this one is
rather too dependent on my providing my analysis (which unfortunately I
don't have time for any longer) so I don't think this is really feasible :(

I may try to pick this up in 2026, and perhaps by then it won't be a
post-mortem of a failed attempt but rather a discussion of a succesful one
:) let's see.

Best, Lorenzo

On Wed, Jan 08, 2025 at 09:46:31PM +0000, Lorenzo Stoakes 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.
>
> Thanks!
>
> [0]:https://lore.kernel.org/linux-mm/ZTc7SHQ4RbPkD3eZ@casper.infradead.org/