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: <f2b55d220702211315h1266d25el4a0f46c4fb65e12a@mail.gmail.com>
Date:	Wed, 21 Feb 2007 13:15:51 -0800
From:	"Michael K. Edwards" <medwards.linux@...il.com>
To:	"Evgeniy Polyakov" <johnpol@....mipt.ru>
Cc:	"Eric Dumazet" <dada1@...mosbay.com>,
	"David Miller" <davem@...emloft.net>, akepner@....com,
	linux@...izon.com, netdev@...r.kernel.org, bcrl@...ck.org
Subject: Re: Extensible hashing and RCU

Look, Evgeniy.  Eric and I may be morons but davem is not.  He's
telling you, again and again, that DoS attacks do happen, that to
survive them you need for the distribution of tuples within hash
buckets to vary unpredictably from system to system and boot to boot,
and that XOR hash does not accomplish this.  He has told you that the
Jenkins hash works, for reasons discussed exhaustively in the link I
gave you, which you can follow to statistical analysis that is beyond
your expertise or mine.  He has told you that your performance
analysis is fundamentally flawed.  Do you think you might need to drop
back five and punt?

As for the distribution issues:  who cares?  You fundamentally can't
do any better, for random input drawn from a tuple space much larger
than the number of hash buckets, than a Poisson distribution.  And
that's enough to kill a naive hash table design, because chaining is
going to cost you another cache miss for every link, and you couldn't
afford the first cache miss in the first place.  If you absolutely
insist on a hash table (on the theory that you can't keep the hot
connections warm in cache anyway, which isn't necessarily true if you
use a splay tree), it had better be a 2-left hash with a compact
overflow pool for the rare case of second collision.

I recommend Michael Mitzenmacher's paper to you, or rather to
whoever's reading along with the intention of improving the kernel
without reinventing the square wheel.

Cheers,
- Michael
-
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