IPv6-ify and rewrite ip_range_to_subnet_array() [resubmit of #1709 (was #974)]

Function cannot handle IPv6 ranges, and is horribly inefficient, because it uses splitting+function call recursion for each "half". Even if extended for IPv6, it is probably far too inefficient for IPv6 on low power hardware. As written it's simply unable to handle an IPv6 environment or IPv6 ranges. As a result, if used in an IPv6 context, it would fail.

It has other problematic issues: 

Validates both IPv4 and IPv6 as valid args, but then tries to process any IPv6 subnet bitwise as x32 LONG without further checking, potentially causing very incorrect return values.

Doesn't detect if the start/end IPs are of same type (eg when validating user input related to an IP range), so a range such as "1.1.1.1-fe00::" is not detected as invalid.

I've rewritten this function, but have had to effectively produce a better algorithm not just a code rewrite. The updated algorithm is extremely fast and gives identical results as far as I can tell from extensive testing. It also handles IPv6 much faster than the old code handled IPv4, and appears very robust. The algorithm is explained below.

Changes:

1) IPv4/IPv6 works correctly.

2) detects mismatched start-end IP types

3) the algorithm written seems very robust (tested on 1 million random IPv4/IPv6 ranges and a number of edge cases, gives same results as existing code)

4) execution time is linear or better to number of bits, rather than exponential (due to lack of split+recurse). So it runs in about 4 - 6% of the time as the existing code for IPv4 (1ms vs. 20ms). On 128-bit IPv6 this would be a much greater saving.

5) it uses simple string pattern matching of low bit(s) to test needed subnets, so it's very efficient. (ip2long, or BCMATH, etc, don't actually add much if anything)

6) 3 functions never used anywhere else are removed (find_smallest_cidr(), ip_before() and ip_after()). Checked using Github search, can't find any other place using these, so removed and left a comment.

RESUBMITTED FROM PR #1709 (WAS #974) TO ALLOW MERGING - NO CODE CHANGE.
ALGORITHM DETAILS BELOW
CHANGES SINCE PR #1709: 
(1) PHP bug related to "long numeric string compare" has been fixed for over a year now, since October 2014, which means all the === and strcmp() can revert to normal == and <.  See https://bugs.php.net/bug.php?id=54547
(2) haven't removed redundant function "find_smallest_cidr_v4()" which can be done separately



ALGORITHM:

Documented on pfsense dev list 19-20 May 2013. PD'd by Stilez - please use as you like!

A quick consideration of what subnets have to be present to span the endpoints of a range, shows that this can be done much faster, can be made to handle IPv6 (which present code never will!), and avoid function call recursion.

SUMMARY:

Algorithm looks at patterns of 0's and 1's in the least significant bit (or bits). These are all that needs checking, to identify the (guaranteed) correct, minimal and optimal subnet array.

As a result, string/binary, with pattern matching built-in, is very efficient. It uses just 2 pattern-matching rules to chop off subnets at both ends, until nothing's left.

(a) If any range has low bit 1 (in startip) or 0 (in endip), these endpoints are _always_ optimally represented by their own 'single IP' CIDR; the remaining range then shrinks by one IP up or down. Only one edge case needs checking: if the range contained exactly 2 adjacent IPs then these CIDRs will now exactly span it, and we're done.

(b) Otherwise, if any range has low bits 0 (in ip1) _and_ 1 (in ip2), these low bits can *always* be ignored for subnet spanning. So provided we remember the bits we've place-shifted, we can _always_ right-shift and chop off those bits, and loop to span the remaining (place shifted) range as above, until after a few loops, the remaining (place shifted) range has become just one IP (ip1==ip2).

0 files changed, 0 insertions, 0 deletions