linux-kernel - RE: [PATCH 0/1] Rosebush, a new hash table

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: <4a1416fcb3c547eb9612ce07da6a77ed@AcuMS.aculab.com>
Date: Sat, 24 Feb 2024 22:10:27 +0000
From: David Laight <David.Laight@...LAB.COM>
To: 'Herbert Xu' <herbert@...dor.apana.org.au>, "Matthew Wilcox (Oracle)"
	<willy@...radead.org>
CC: "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>, Thomas Graf
	<tgraf@...g.ch>, "netdev@...r.kernel.org" <netdev@...r.kernel.org>,
	"linux-fsdevel@...r.kernel.org" <linux-fsdevel@...r.kernel.org>,
	"maple-tree@...ts.infradead.org" <maple-tree@...ts.infradead.org>,
	"rcu@...r.kernel.org" <rcu@...r.kernel.org>
Subject: RE: [PATCH 0/1] Rosebush, a new hash table

From: Herbert Xu
> Sent: 24 February 2024 00:21
> 
> On Thu, Feb 22, 2024 at 08:37:23PM +0000, Matthew Wilcox (Oracle) wrote:
> >
> > Where I expect rosebush to shine is on dependent cache misses.
> > I've assumed an average chain length of 10 for rhashtable in the above
> > memory calculations.  That means on average a lookup would take five cache
> > misses that can't be speculated.  Rosebush does a linear walk of 4-byte
> 
> Normally an rhashtable gets resized when it reaches 75% capacity
> so the average chain length should always be one.

The average length of non-empty hash chains is more interesting.
You don't usually search for items in empty chains.
The only way you'll get all the chains of length one is if you've
carefully picked the data so that it hashed that way.

I remember playing around with the elf symbol table for a browser
and all its shared libraries.
While the hash function is pretty trivial, it really didn't matter
whether you divided 2^n, 2^n-1 or 'the prime below 2^n' some hash
chains were always long.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)