From owner-freebsd-ipfw@FreeBSD.ORG  Sun Dec 25 19:37:12 2011
Return-Path: <owner-freebsd-ipfw@FreeBSD.ORG>
Delivered-To: freebsd-ipfw@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id B63411065675;
	Sun, 25 Dec 2011 19:37:12 +0000 (UTC)
	(envelope-from luigi@onelab2.iet.unipi.it)
Received: from onelab2.iet.unipi.it (onelab2.iet.unipi.it [131.114.59.238])
	by mx1.freebsd.org (Postfix) with ESMTP id 6A79E8FC1B;
	Sun, 25 Dec 2011 19:37:12 +0000 (UTC)
Received: by onelab2.iet.unipi.it (Postfix, from userid 275)
	id E3AFB7300B; Sun, 25 Dec 2011 20:37:55 +0100 (CET)
Date: Sun, 25 Dec 2011 20:37:55 +0100
From: Luigi Rizzo <rizzo@iet.unipi.it>
To: "Alexander V. Chernikov" <melifaro@freebsd.org>
Message-ID: <20111225193755.GB10707@onelab2.iet.unipi.it>
References: <1674097252.20111218125051@nitronet.pl>
	<4EEDD566.8020609@FreeBSD.org> <20111220163355.GA87584@DataIX.net>
	<4EF73A4A.3050902@FreeBSD.org>
	<1413850829.20111225184712@nitronet.pl>
	<AA3C6FCC-0817-4108-A107-3367A6F14757@lists.zabbadoz.net>
	<4EF7719A.8020902@FreeBSD.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <4EF7719A.8020902@FreeBSD.org>
User-Agent: Mutt/1.4.2.3i
Cc: Jason Hellenthal <jhell@dataix.net>, "Andrey V. Elsukov" <ae@freebsd.org>,
	freebsd-net@freebsd.org, freebsd-ipfw@freebsd.org,
	"Bjoern A. Zeeb" <bzeeb-lists@lists.zabbadoz.net>,
	Pawel Tyll <ptyll@nitronet.pl>
Subject: Re: IPFW eXtended tables [Was: Re: IPFW tables, dummynet and IPv6]
X-BeenThere: freebsd-ipfw@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: IPFW Technical Discussions <freebsd-ipfw.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-ipfw>,
	<mailto:freebsd-ipfw-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-ipfw>
List-Post: <mailto:freebsd-ipfw@freebsd.org>
List-Help: <mailto:freebsd-ipfw-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-ipfw>,
	<mailto:freebsd-ipfw-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sun, 25 Dec 2011 19:37:12 -0000

On Sun, Dec 25, 2011 at 10:55:22PM +0400, Alexander V. Chernikov wrote:
> Bjoern A. Zeeb wrote:
> > On 25. Dec 2011, at 17:47 , Pawel Tyll wrote:
> > 
> >> Hi Alexander,
> >>
> >>> Changes:
> >>> * Tables (actually, radix trees) are now created/freed on demand.
> >> Does  this  mean  IPFW_TABLES_MAX can now be safely set to arbitrarily
> >> high number that would allow flexible numbering of tables? Arbitrarily
> >> high  being 0xFFFFFFFF or some other nice large number that won't step
> >> on my ideas :)
> At the moment maximum number of tables remains the same however it is
> now possible to define IPFW_TABLES_MAX to 65k without much (memory)
> overhead. Since pointer to tables are stored in array, defining 2^32
> tables require 4G * (8+8+1) memory for pointers only.

perhaps you could reuse some of the infrastructure i have for
looking up rule numbers -- i keep them sorted into an array
(and if i am not mistaken there are generation numbers to validate
pointers) so lookups are O(log N) in the worst case, and direct
lookups are O(1) after the first attempt.

cheers
luigi