netdev - Re: Extensible hashing and RCU

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: <20070220180027.GC26961@2ka.mipt.ru>
Date:	Tue, 20 Feb 2007 21:00:30 +0300
From:	Evgeniy Polyakov <johnpol@....mipt.ru>
To:	Eric Dumazet <dada1@...mosbay.com>
Cc:	"Michael K. Edwards" <medwards.linux@...il.com>,
	David Miller <davem@...emloft.net>, akepner@....com,
	linux@...izon.com, netdev@...r.kernel.org, bcrl@...ck.org
Subject: Re: Extensible hashing and RCU

On Tue, Feb 20, 2007 at 06:53:59PM +0100, Eric Dumazet (dada1@...mosbay.com) wrote:
> > > I've attached source code and running script.
> > > $ ./run.sh
> >
> > Yep, of course.
> 
> Your test program is just bogus. artefacts come from your 'random' generator.
> 
> You just increment a counter, assuming the key you search is not in the table 
> yet.

No, that part is commented, but it does not matter.

> But obviously with only a variation of sport (16 bits), you have a maximum of 
> 65536 values. No need to feed 100*2^20 values are most of them are dups.
> 
> Now if you change your program to do a real lookups with the 2^16 possible 
> values of sport you'll see :

No need to change something - I showed that in some cases jenkins ends
up with a huge problem. If test will be changed, or solar will be turned
off, things will behave good, but as is they behave very bad.

> jhash function :
> 1 61578
> 2 1916
> 3 42
> 
> that is : 61578 chains of length 1
> 1916 chains of length 2
> 42 chains of length 3
> 
> (for reference, with HASH_FOLD, about same results :
> 1 61692
> 2 1856
> 3 44
> 
> Pretty good results... for the gain jhash gives us.
> 
> Of course, XOR hash gives a 'perfect' 65536 chains of length 1.

As you can see, jhash has problems in a really trivial case of 2^16,
which in local lan is a disaster. The only reason jenkins hash is good
for hashing purposes is that is it more complex than xor one, and thus
it is harder to find a collision law. That's all.
And it is two times slower.

-- 
	Evgeniy Polyakov
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html