[RFC] ipset: New set type iptreemap

[Sven Wegener <sven.wegener@stealer.net>]

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