linux-kernel - Re: FYI: path walking optimizations pending for 6.11

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]

Date: Fri, 21 Jun 2024 21:04:42 +0100
From: Matthew Wilcox <willy@...radead.org>
To: Linus Torvalds <torvalds@...ux-foundation.org>
Cc: Christian Brauner <brauner@...nel.org>,
	Al Viro <viro@...iv.linux.org.uk>,
	linux-fsdevel <linux-fsdevel@...r.kernel.org>,
	the arch/x86 maintainers <x86@...nel.org>,
	Linux ARM <linux-arm-kernel@...ts.infradead.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	kernel test robot <lkp@...el.com>
Subject: Re: FYI: path walking optimizations pending for 6.11

On Wed, Jun 19, 2024 at 03:08:47PM -0700, Linus Torvalds wrote:
> On Wed, 19 Jun 2024 at 13:45, Matthew Wilcox <willy@...radead.org> wrote:
> >
> > Funnily, I'm working on rosebush v2 today.  It's in no shape to send out
> > (it's failing ~all of its selftests) but *should* greatly improve the
> > cache friendliness of the hash table.  And it's being written with the
> > dcache as its first customer.
> 
> I'm interested to see if you can come up with something decent, but
> I'm not hugely optimistic.

Well, I've now come up with something _working_.  There are still things
to be fixed, but it might be interesting for a performance comparison.
So I've pushed it out to
http://git.infradead.org/?p=users/willy/pagecache.git;a=shortlog;h=refs/heads/rosebush
where I hope 01.org will pick up on it and run some performance tests.

> From what I saw, you planned on comparing with rhashtable hash chains of 10.

That was the comparison I made (and it turns out I misunderstood
rhashtable entirely; the length is where it does an emergency resize,
and usually its size is such that the average hash length is <1)

What I was reacting to in your email was this:

: And on my arm64 machine, it turns out that the best optimization for the
: load I tested would be to make that hash table smaller to actually be a
: bit denser in the cache, But that's such a load-dependent optimization
: that I'm not doing this.

And that's exactly what rosebush does; it starts out incredibly small
(512 bytes) and then resizes as the buckets overflow.  So if you suspect
that a denser hashtable would give you better performance, then maybe
it'll help.

Or maybe not; it's not like I've done thorough testing.