Hi, sorry for the delay. On Fri, 14 Aug 2020 21:21:26 +0200 Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx> wrote: > Assuming d = memcmp(node, new) when comparing existing nodes and a new > node, when descending the tree to find the spot to insert the node, the > overlaps that can be detected are: > > 1) If d < 0 and the new node represents an opening interval and there > is an existing opening interval node in the tree, then there is a > possible overlap. > > 2) If d > 0 and the new node represents an end of interval and there is an > existing end of interval node, then there is a possible overlap. > > When descending the tree, the overlap flag can be reset if the > conditions above do not evaluate true anymore. > > Note that it is not possible to detect some form of overlaps from the > kernel: Assuming the interval [x, y] exists, then this code cannot > detect when the interval [ a, b ] when [ a, b ] fully wraps [ x, y ], ie. > > [ a, b ] > <----------------> > [ x, y ] > <----------> Actually, also this kind of overlap is detected (and already covered by testcases). Here, we would notice already while inserting 'x' that it sits between non-matching existing start, x, and existing end, y. This can't be detected with just local considerations, and it's the reason why the 'overlap' flag is updated as we descend the tree. Now, the issue mentioned below: https://bugzilla.netfilter.org/show_bug.cgi?id=1449 comes from a wrong assumption I took, namely, the fact that as end elements are always inserted after start elements, they also need to be found in the tree as descendants of start elements. This isn't true with tree rebalancing operations resulting in rotations, and in the case reported we have some delete operations triggering that. I fixed this case in a new series I'm posting, together with additional tests that cause different types of rotations, and one fix for a false negative case instead, that I found while playing around with nft (skipping different types of overlap checks while keeping others in place). > Moreover, skip checks for anonymous sets where it is not possible to > catch overlaps since anonymous sets might not have an explicit end of > interval. e.g. 192.168.0.0/24 and 192.168.1.0/24 results in three tree > nodes, one open interval for 192.168.0.0, another open interval for > 192.168.1.0 and the end of interval 192.168.2.0. In this case, there is > no end of interval for 192.168.1.0 since userspace optimizes the > structure to skip this redundant node. Now, I couldn't find a way to insert anonymous sets that would trigger (partial) overlap detection. This is because those overlaps are already handled (by merging) by nft, and if I insert multiple anonymous sets with overlapping intervals, they are, well... different sets, so anything goes. Let me know if I'm missing something here. -- Stefano
