Date: Thu, 22 Apr 2004 03:54:24 -0700 From: Luigi Rizzo <luigi@FreeBSD.org> To: Darren Reed <darrenr@hub.freebsd.org> Cc: cvs-src@FreeBSD.org Subject: Re: cvs commit: src/sys/net radix.c Message-ID: <20040422035424.A4881@xorpc.icir.org> In-Reply-To: <20040422092120.GC27025@hub.freebsd.org>; from darrenr@hub.freebsd.org on Thu, Apr 22, 2004 at 02:21:20AM -0700 References: <200404211527.i3LFRabS088245@repoman.freebsd.org> <6.0.1.1.1.20040422005919.03afaaa0@imap.sfu.ca> <20040422002143.GC60368@hub.freebsd.org> <200404220259.45651.max@love2party.net> <20040422051953.GA27025@hub.freebsd.org> <20040422005258.A84320@xorpc.icir.org> <20040422092120.GC27025@hub.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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 gradually. > 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) ? cheers luigi
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040422035424.A4881>