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: <20070222.010638.27784211.davem@davemloft.net>
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