Re: refactoring ip_output() and the L2 _output()

[David Young <dyoung%pobox.com@localhost>]

On Sat, Feb 09, 2013 at 07:24:32PM -0800, Dennis Ferguson wrote:
> Speaking of which, that radix tree implementation in the kernel is very
> old and crufty.  It was a very early implementation of a variable length
> mask search (when routes were classed route lookups were done in a hash
> table), the code was always opaque and had minor bugs that seemed impossible
> to find, it isn't very fast and operates in a way which unnecessarily
> penalizes longer addresses (i.e. IPv6), and we've learned just a whole lot
> more about data structures for longest match lookups since then.  If
> noncontiguous masks are no longer interesting then maybe it is time to
> replace that?

Yes, it is time to replace that.  We have one candidate to replace the
existing data structure in the form of src/common/lib/libc/gen/ptree.c.
I'm not sure if anyone's using it for a forwarding/routing table, yet.

Speaking of radix trees, it seems that in an SMP networking stack the PCB
tables could be replaced by a couple of them.  The tree for unconnected
sockets would use keys

        [protocol (tcp|udp|...), local port (1..65535)]

for sockets binding the same port and INADDR_ANY, and use keys

        [protocol (tcp|udp|...), local port (1..65535)], local address]

for sockets bound to a particular local address.

For connected sockets, and TCP sessions being established, or what have
you, there would be the flow table that you have described previously,
using the key you mention

        [local address, remote address, protocol (tcp|udp|...),
         first 4 bytes of L4 header]

or some permutation thereof.

The kernel will try for matches in the flow-table entry, first; failing
to find a match there, it would try the unconnected table.

I suppose that the two tables could be made one if the fields in the
key were suitably ordered,

        [protocol, local port, local address, remote port, remote address]

Just a thought, anyway.

Dave

-- 
David Young
dyoung%pobox.com@localhost    Urbana, IL    (217) 721-9981