From owner-cvs-src@FreeBSD.ORG Thu Apr 22 03:54:27 2004 Return-Path: Delivered-To: cvs-src@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 5B80F16A4D0; Thu, 22 Apr 2004 03:54:27 -0700 (PDT) Received: from xorpc.icir.org (xorpc.icir.org [192.150.187.68]) by mx1.FreeBSD.org (Postfix) with ESMTP id 0CBBA43D54; Thu, 22 Apr 2004 03:54:27 -0700 (PDT) (envelope-from rizzo@icir.org) Received: from xorpc.icir.org (localhost [127.0.0.1]) by xorpc.icir.org (8.12.9p1/8.12.8) with ESMTP id i3MAsPgd005953; Thu, 22 Apr 2004 03:54:25 -0700 (PDT) (envelope-from rizzo@xorpc.icir.org) Received: (from rizzo@localhost) by xorpc.icir.org (8.12.9p1/8.12.3/Submit) id i3MAsP64005952; Thu, 22 Apr 2004 03:54:25 -0700 (PDT) (envelope-from rizzo) Date: Thu, 22 Apr 2004 03:54:24 -0700 From: Luigi Rizzo To: Darren Reed Message-ID: <20040422035424.A4881@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> <20040422092120.GC27025@hub.freebsd.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <20040422092120.GC27025@hub.freebsd.org>; from darrenr@hub.freebsd.org on Thu, Apr 22, 2004 at 02:21:20AM -0700 cc: Max Laier cc: src-committers@FreeBSD.org cc: cvs-all@FreeBSD.org cc: cvs-src@FreeBSD.org Subject: Re: cvs commit: src/sys/net radix.c X-BeenThere: cvs-src@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: CVS commit messages for the src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 22 Apr 2004 10:54:27 -0000 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