Re: Extensible hashing and RCU

[Stephen Hemminger <shemminger@linux-foundation.org>]

On Thu, 22 Feb 2007 03:07:55 -0800 (PST)
David Miller <davem@davemloft.net> wrote:

> From: "Michael K. Edwards" <medwards.linux@gmail.com>
> Date: Thu, 22 Feb 2007 03:00:32 -0800
> 
> > Besides, RCUing a hash of any sort sounds like a nightmare, whereas
> > something like a splay tree is reputed to be very straightforward to
> > make "persistent" in the functional-programming sense.  I haven't
> > coded that one myself but surely it's in the current edition of Knuth.
> 
> Knuth tends to be thorough, yet archaic. :-)
> 
> > You are much better off obtaining all per-flow state with a
> > single data structure lookup.  It would be kind of nice if state for
> > other layers like IPSec and NAT could live there too.
> 
> This is the eventual idea.
> 
> > By the way, are these flows unidirectional or bidirectional?
> 
> The entries created by Robert's TRASH are unidirectional, they have to
> be because the path from remote to localhost is different than the
> path from localhost to remote :-)
> 
> But we don't need to do a socket demux on packet output, we just
> need a plain route (+ firewall, IPSEC, etc.) destination cache
> entry for that.
> -


There are a number of other lock-less algorithms rather than simple RCU
that might be worth exploring. A number of them rely on a working implementation
of compare-exchange; that can be a problem since some architectures don't have
a fast way of doing that.

-- 
Stephen Hemminger <shemminger@linux-foundation.org>