Re: [ANNOUNCE] ipset 6.11 released

[Mr Dash Four <mr.dash.four@googlemail.com>]

> Doable, but needs time and would involve adding the logic to auto-merge 
> smaller subnets into larger ones and to make possible to delete subnets 
> from larger networks.
>   
Merging of ip ranges would be very difficult - I am having the same 
problem here as well. I use PostgreSQL as part of my setup and even 
though it has some nice capabilities to deal with "common" ip/range/net 
address operations, it is still very difficult, nigh-impossible to deal 
with ip range merges, simply because there are so many possible 
scenarios: any two ranges could be partially overlapping - like [ (] ), 
one range completely overlapping another - like [ () ], or two ranges 
"touching" one another - like [ ]( ) - that last one is very difficult 
to spot for merging and can't see it done very easily.

Just for testing ip range matches though, things could be a bit easier 
(pun intended).

If we assume that the whole ip address space (0.0.0.0-255.255.255.255, 
similar for ipv6 as well) occupies X number of bits (0...X-1), then each 
ip range (including a single ip address) could be represented by a 
starting bit number, length (in bits) and an end bit number (the latter 
is optional, but would ease ip range matching, if included). These 3 
components would have roughly the same memory footprint no matter what 
is the size of the actual ip range.

When adding such ip range in a set, I assume you just store their hash 
(to find them quickly when searching for exact set members). If you 
could add the above 3 elements, then matching ip ranges should be fairly 
easy: you take the starting bit from the ip range which needs to be 
tested and then isolate all those elements in the set which have their 
starting bit and ending bit in-between the starting bit of the testing 
range, i.e. test_start_bit between set_member_start_bit and 
set_member_end_bit, *or*, having their ending bit also between those 
ranges (i.e. test_end_bit between set_member_start_bit and 
srt_member_end_bit). You also need to discard duplicates, so that you 
don't test more than once.

Once you've isolated those potential matches, you can then construct a 
"partial" bitmap of these potential matches by using the 3 stored set 
member attributes - starting bit, length and end bit.

Then a simple bitwise "or" ("|") operation against each "partial" set 
member bitmap matched would suffice. By "partial" I mean applying the 
"or" only on the bit-range value we are interested in. This needs to be 
done recursively, whereby the result of the previous bitwise "or" 
operation should be applied to the partial bitmap of the next set 
member, so that you get partial matches accounted for.

If the end result after this leaves you with the exact bitmap of the ip 
range being tested, then there is a complete match. If you end up with 
something different, then there is either no or incomplete match. I hope 
I am making sense.

One very simple (and very crude) example to illustrate this: suppose the 
ip range we are interested in testing has a start bit value of 10 and 
its length is 16 (therefore the end bit = 25). Now, suppose we have 4 
set members with the following values stored in the set:

1. start-> 2, length-> 6
2. start-> 13, length-> 7
3. start-> 8, length-> 8
4. start-> 20, length-> 6

The "partial" bitmap of the ip range to be tested (stat bit = 10, end 
bit = 25) could be presented like this, after being "normalised" 
(position indicates bit number, starting from 0):

.........1111111111111111

Therefore, after initial scanning, we discard element 1 as it doesn't 
have its either start or end bit in the range we are interested in (10 - 
25) and that leaves us with the following set members:

.........0001111111000000
.......111111110000000000
.........0000000000111111

When we apply bitwise or ("|") on the range we are interested in (bits 
10-25) - recursively for each member left in the pot - we are left with 
a value of all 1's for the range of bits we are interested in (bits 
10-25), which is exactly the same as the ip range we are testing, so 
there is a complete match, otherwise there would either be no or 
incomplete match.

> I'm sure you are aware, this is a free time project.
>   
I am! I am also trying to help you with this as I would benefit from 
this bug being resolved.

> Sorry, for a while you have to use workarounds like you described.
>   
Pity that!