Better "hash_packet6"

[Luigi Rizzo]

On Wed, Dec 06, 2006 at 11:38:47AM +0000, David Malone wrote:
> On Wed, Dec 06, 2006 at 01:29:31AM -0800, Luigi Rizzo wrote:
> > the top forwarding performance of a soekris is around 30-35kpps if
> > i remember well - this translates in around 30us/packet all included.
> 
> Is that the peak with ipfw2, IPv6 packets and dynamic rules turned on?

maybe just ipfw2-ipv4 on and a single accept rule.
that's to give an estimate of all the remaining packet processing
costs that you were mentioning (interrupts etc.)

> I've read the description of the Hsieh hash now and I'm pretty sure
> it should be possible to produce lots of collisions fairly easily

i am not saying that this is the only option, the page lists other
hashes.

> > (here we probably overflow some cache so the simple algorithm
> > suffers a lot by increasing the number of different packets)
> 
> I guess by default, this will always be a cache miss, because
> the packet will just have been DMAed into memory? (Or, we will

i think all of this is irrelevant if we go for a complex hash
with many operations. Caching gives/saves is a constant overhead, which for a
very simple hash maybe doubles the time (from 0.8 to 2us/pkt)
but it is negligible on the 11us and 27us consumed by the
hsieh and universal hashes.

> recently have paid for the cache miss.)
> 
> > Surely we need to experiment a bit more, but the cost
> > is significant especially on low end boxes.
> 
> I think we really need to test the code in-place and look at the
> increase in CPU usage at different packet rates? That way the
> relative overhead and cache conditions will be closet to realistic.
> Do you have any suitable setup for this?

no, and i think we should not bother on the cache effects as
they are negligible here _and_ almost completely out of our control.

If i may make a modest proposal, lets make the hashing algorithm
a compile (or run) time option so people worried about collisions
will be able to use the expensive function, and others can select
a simpler one e.g. some simpler hash that xor's the addresses
instead of sorting them.

> (The other option, is to replace the use of hash tables for dynamic
> rules with some other data structure that has better worst-case
> behaviour.)

with the 36 bytes strings we have to work on, i doubt we can find
something that is not a memory killer yet runs in decent times!

	cheers
	luigi