IPFW eXtended tables [Was: Re: IPFW tables, dummynet and IPv6]

[Luigi Rizzo]

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