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]
Date:	Thu, 22 Feb 2007 01:06:38 -0800 (PST)
From:	David Miller <davem@...emloft.net>
To:	medwards.linux@...il.com
Cc:	johnpol@....mipt.ru, dada1@...mosbay.com, akepner@....com,
	linux@...izon.com, netdev@...r.kernel.org, bcrl@...ck.org
Subject: Re: Extensible hashing and RCU

From: "Michael K. Edwards" <medwards.linux@...il.com>
Date: Wed, 21 Feb 2007 13:15:51 -0800

> it had better be a 2-left hash with a compact
> overflow pool for the rare case of second collision.

Just like Evgeniy, you should do your research too :-))))

The gain for multiple-hash schemes, such as 2-left, exists only if you
can parallelize the N lookups in hardware.  This is an assumption
built into all the papers you will read on this subject, including the
one you reference by Mitzenmacher.

If you read any paper on IP route lookup algorithms, prefix
your reading of that paper with something that reads like:

	And by the way we are targeting implementations in
	hardware that can parallelize and pipeline memory
	accesses to fast SRAM.  Do not consider this algorithm
	seriously for running on general purpose processors
	in software.

Probably a few read's of Network Algorithmics would help your
understanding in this area as well.

Tries and similar structures do help in the case of our routing
because we're going from a potential 32-hashtable probe down
to a relatively small number of probes into a trie.  That's what
Robert's LC-Trie and upcoming TRASH work do.

But it won't help the same when going from hashes to a trie,
as would be the case for TCP.

If we can get the sockets into the TRASH entries, as Eric will
experiment with, we'll be able to eliminate the TCP hash lookup
in the fast path entirely.  It is the only reasonable suggestion
I've seen made in this area to date.
-
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

Powered by blists - more mailing lists