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: <2a6001442b354c2fb5b881c2a9d75895@AcuMS.aculab.com>
Date: Sun, 25 Feb 2024 14:47:45 +0000
From: David Laight <David.Laight@...LAB.COM>
To: 'Kent Overstreet' <kent.overstreet@...ux.dev>
CC: 'Herbert Xu' <herbert@...dor.apana.org.au>, "Matthew Wilcox (Oracle)"
	<willy@...radead.org>, "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: Kent Overstreet
> Sent: 25 February 2024 03:19
.
> when I implemented cuckoo (which is more obviously sensitive to a weak
> hash function), I had to go with siphash, even jhash wasn't giving me
> great reslts. and looking at the code it's not hard to see why, it's all
> adds, and the rotates are byte aligned... you want mixed adds and xors
> and the rotates to be more prime-ish.
> 
> right idea, just old...
> 
> what would be ideal is something more like siphash, but with fewer
> rounds, so same number of instructions as jhash. xxhash might fit the
> bill, I haven't looked at the code yet...

There is likely to be a point where scanning a list of values
for the right hash value is faster than executing a hash function
that is good enough to separate them to separate buckets.

You don't want to scan a linked list because they have horrid
cache footprints.
The locking is equally horrid - especially for remove.
Arrays of pointers ar ethe way forward :-)

	David

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