Mailing List Archive: iptables: Devel

[RFC] ipset: New set type iptreemap

Index | Next | Previous | View Threaded

sven.wegener at stealer

Aug 20, 2007, 1:36 PM

Post #1 of 2 (676 views)
Permalink

[RFC] ipset: New set type iptreemap

Hi all,

based on the feedback from Jan Engelhardt I've converted the fullipmap [1]
set type I announced last week to manage the bitmaps with a tree
structure, instead of a large flat single array. The code is based on
iptree and the name of the new type is iptreemap.

Worst case memory usage has increased slightly over fullipmap, but the
average memory usage should be lower. It also supports adding and deleting
of ranges, so it can be used to match against lists of ranges and
networks. Be aware that the set type doesn't store the range itself, but
it expands the range so that the set contains all addresses within that
range. With a pure network set type like nethash the following is not
possible:

ipset -A foo 172.16.0.0/12
ipset -D foo 172.17.0.0/16

But iptreemap will handle it as expected and after the delete operation
the set will only contain the ranges:

172.16.0.0-172.16.255.255
172.18.0.0-172.31.255.255

(The userspace part uses : as the range separator to not interfere with -
in hostnames)

For ranges that start and end at octet boundaries iptreemap will not use
any memory for the bitmaps as it manages this by reusing global allocated
bitmaps. A garbage collector checks whether a bitmap or a complete subtree
can be replaced by these global bitmaps.

I'm responding with two patches, one for the kernel part and one for the
userspace part. I think the looping code for the add and delete operation
for ranges could need some cleanup. The CHECK[1-3] macro is for checking
whether a complete subtree can be added or deleted. And the GETVALUE[1-3]
is for getting the start and end values for octets when we're inside of a
range.

Sven

[1] https://lists.netfilter.org/pipermail/netfilter-devel/2007-August/029066.html

kadlec at blackhole

Aug 21, 2007, 4:29 AM

Post #2 of 2 (603 views)
Permalink

Re: [RFC] ipset: New set type iptreemap [In reply to]

Hi,

On Mon, 20 Aug 2007, Sven Wegener wrote:

> based on the feedback from Jan Engelhardt I've converted the fullipmap [1]
> set type I announced last week to manage the bitmaps with a tree
> structure, instead of a large flat single array. The code is based on
> iptree and the name of the new type is iptreemap.

I'm back from my long tenting holiday :-) and revisiting your pacthes.
It seems there'll be need a new ipset release...

Best regards,
Jozsef
-
E-mail : kadlec [at] blackhole, kadlec [at] sunserv
PGP key : http://www.kfki.hu/~kadlec/pgp_public_key.txt
Address : KFKI Research Institute for Particle and Nuclear Physics
H-1525 Budapest 114, POB. 49, Hungary

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact Gossamer Threads