cvs commit: src/sys/net radix.c

Luigi Rizzo luigi at
Thu Apr 22 03:54:27 PDT 2004

On Thu, Apr 22, 2004 at 02:21:20AM -0700, Darren Reed wrote:
> Without looking, my experience with using the radix code is that if
> RNF_ROOT is set then you don't have an "struct somethingelse" (that
> flag is only set on structures allocated inside radix.c) so maybe it
> should be (unless it is ruled out by the code paths):
> #define RNTORT(p) ((struct rtentry *)((p->rn_flags & RNF_ROOT)?NULL:p))

could be. only one place to touch, now :)

> or create an mtod() equivalent:
> #define rntod(p,t)  ((t)(((p)->rn_flags & RNF_ROOT)?NULL:(p)))

not this one though, it would allow random casts which are inconsistent
with the way these structures are defined.

> > Additionally, we need to make progress. The entire routing structure
> > is incredibly expensive time and spacewise -- e.g each entry in the
> > routing table consumes 80 bytes + the metrics + the 2 sockaddr,
> > which 5-10 times the space you need for an optimised implementation
> Have you throught through this any more or are these just random

yes I have, and andre has even more. but we need to get there

> Are you concerned that a radix tree (rather than some other data
> structure) is being used or that its use is not efficient ?
> I suppose another pertinent question here might be if I put 4GB
> of RAM in a PC, can freebsd's kernel use 3.5GB of it, internally,
> or is it restricted to some fraction of that ?

There is memory and memory. If you keep the footprint small, you
have a hope to hit a nearby cache which can be 20-50 times faster
(in latency) than main memory. Which makes the radix-tree vs. 4-level tree
vs other data structure issue almost irrelevant.

BTW thanks for the Cisco datapoint (320bytes per entry).
Though, does it refer to the FIB (the info kept in the kernel for
forwarding purposes) or the RIB (the copy managed by the routing
daemon) ?


More information about the cvs-src mailing list