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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 20 Feb 2007 20:17:31 +0100
From:	Eric Dumazet <dada1@...mosbay.com>
To:	Evgeniy Polyakov <johnpol@....mipt.ru>
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 Tuesday 20 February 2007 20:06, Evgeniy Polyakov wrote:

> > I added to my 'simulator_plugged_on_real_server' the average cost
> > calculation, relative to number of cache line per lookup.
> >
> > ehash_size=2^20
> > xor hash :
> > 386290 sockets, Avg lookup cost=3.2604 cache lines/lookup
> > 393667 sockets, Avg lookup cost=3.30579 cache lines/lookup
> > 400777 sockets, Avg lookup cost=3.3493 cache lines/lookup
> > 404720 sockets, Avg lookup cost=3.36705 cache lines/lookup
> > 406671 sockets, Avg lookup cost=3.37677 cache lines/lookup
> > jenkin hash:
> > 386290 sockets, Avg lookup cost=2.36763 cache lines/lookup
> > 393667 sockets, Avg lookup cost=2.37533 cache lines/lookup
> > 400777 sockets, Avg lookup cost=2.38211 cache lines/lookup
> > 404720 sockets, Avg lookup cost=2.38582 cache lines/lookup
> > 406671 sockets, Avg lookup cost=2.38679 cache lines/lookup
> >
> > (you can see that when number of sockets increase, the xor hash becomes
> > worst)
> >
> > So the jenkin hash function CPU cost is balanced by the fact its
> > distribution is better. In the end you are faster.
>
> Very strange test - it shows that jenkins distribution for your setup is
> better than xor one, although for the true random data they are roughly
> the same, and jenkins one has more instructions.
>
> But _you_ have shown that with true random data of 2^16 ports jenkins
> distribution is _worse_ than xor without any gain to buy.

I shown your test was bogus. All your claims are just bogus.
I claim your 'true random data' is a joke. rand() in your program is a pure 
joke.

Given 48 bits of input, you *can* find a lot of addr/port to hit one 
particular cache line if XOR function is used. With jhash, without knowing 
the 32bits random secret, you *cant*.

Again, you dont take into account the chain length.

If all chains were of length <= 1, then yes, xor would be faster. In real 
life, we *know* chain length can be larger, especially in DOS situations.

-
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