Re: [ANNOUNCE] ipset 6.11 released
|[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]|
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-> 6The "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):
.........1111111111111111Therefore, 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 .........0000000000111111When 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 am! I am also trying to help you with this as I would benefit from this bug being resolved.I'm sure you are aware, this is a free time project.
Sorry, for a while you have to use workarounds like you described.
Pity that! -- To unsubscribe from this list: send the line "unsubscribe netfilter" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html