Date: Thu, 22 Apr 2004 02:21:20 -0700 From: Darren Reed <darrenr@hub.freebsd.org> To: Luigi Rizzo <luigi@FreeBSD.org> Cc: cvs-src@FreeBSD.org Subject: Re: cvs commit: src/sys/net radix.c Message-ID: <20040422092120.GC27025@hub.freebsd.org> In-Reply-To: <20040422005258.A84320@xorpc.icir.org> 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>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, Apr 22, 2004 at 12:52:58AM -0700, Luigi Rizzo wrote: > i knew this would be a bit controversial :) Glad I met your expectations :) > > really the hard part of this code to grasp, it's the structures > > and how they interact and interconnect. Look in that book, see > > where all the arrows go in the diagrams. Perhaps I should say > > that part is unchanged and i do not have any intention of changing it, > nor interfaces. BTW the hard parts of the code in radix.c (rn_addmask(), > rn_addroute(), rn_delete() and so on) are _not_ documented in Stevens' > book so there is little if any motivation to preserve the lexical format > of the code. I'll take your word for it :) > + * 'struct rtentry' starts with two 'struct radix_node''s, the first > + * one representing leaf nodes in the routing tree, which is > + * what the code in radix.c passes us as a 'struct radix_node'. > + * > + * But because there are a lot of assumptions in this conversion, > + * do not cast explicitly, but always use the macro below. > + */ > +#define RNTORT(p) ((struct rtentry *)(p)) 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)) or create an mtod() equivalent: #define rntod(p,t) ((t)(((p)->rn_flags & RNF_ROOT)?NULL:(p))) > 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 > of the routing tree for ipv4. Maybe it was ok when you had 1000 > entries in the table, not anymore when you have large BGP tables > to push in the kernel. > We need to be able to provide specialised (and efficient) versions > of the code for selected address families -- this likely will > cause a change in the APIs, with a compatibility layer to > let old code still work. Have you throught through this any more or are these just random thoughts as you work your way through this code ? 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 ? Darren
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040422092120.GC27025>