From owner-freebsd-ipfw@FreeBSD.ORG Tue May 18 00:07:11 2004 Return-Path: Delivered-To: freebsd-ipfw@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id BD58416A4CE for ; Tue, 18 May 2004 00:07:11 -0700 (PDT) Received: from xorpc.icir.org (xorpc.icir.org [192.150.187.68]) by mx1.FreeBSD.org (Postfix) with ESMTP id C770543D1D for ; Tue, 18 May 2004 00:07:10 -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 i4I777gd096534; Tue, 18 May 2004 00:07:07 -0700 (PDT) (envelope-from rizzo@xorpc.icir.org) Received: (from rizzo@localhost) by xorpc.icir.org (8.12.9p1/8.12.3/Submit) id i4I7775c096533; Tue, 18 May 2004 00:07:07 -0700 (PDT) (envelope-from rizzo) Date: Tue, 18 May 2004 00:07:06 -0700 From: Luigi Rizzo To: Max Laier Message-ID: <20040518000706.A96220@xorpc.icir.org> References: <40A8C12D.5040906@email.dp.ua> <20040517151050.B63591@xorpc.icir.org> <200405180525.36273.max@love2party.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <200405180525.36273.max@love2party.net>; from max@love2party.net on Tue, May 18, 2004 at 05:25:33AM +0200 cc: freebsd-ipfw@freebsd.org Subject: Re: ipfw prefix-list support request X-BeenThere: freebsd-ipfw@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: IPFW Technical Discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 18 May 2004 07:07:11 -0000 On Tue, May 18, 2004 at 05:25:33AM +0200, Max Laier wrote: ... > I'll try to describe a bit how it is handled in pf, to give you some more > hints in case you are going to look at the code ... good, thanks. > pf uses the existing radix-tree implementation for the tables. This provides > lookups in O(32) for IPv4 and O(128) for IPv6 which means it's a constant > time lookup. Unfortunately, the radix code has some locking requirements that > add overhead but it's sure worth looking at. well, good luck :) it's not just the locking requirements, it's the space used for each entry and the very complicated API to use it that scares me -- basically requiring a lot of extra work to format arguments. If anything, a good output from this kind of project would be a reimplementation of a forwarding table... > > + remember that ipfw(2) accepts one line at a time -- so there will be > > times when the configuration is inconsistent e.g. you might have rules > > pointing to a non-existing list. Make sure the handling of these cases > > is not terribly expensive. > > I have no clue how to address this, but I find it a rather gross way of > dealing with a ruleSET ... well this was for backward compatibility. The way ipfw2/dummynet handle this is the same way in whihc one should handle pluggable hardware -- invalidate pointers on departures, flag arrivals so that the code can (lazily) try to update an invalid reference after an arrival. A generation-id of some kind would make the mechanism very simple. cheers luigi