[PATCH nf] netfilter: nft_set_rbtree: revisit partial overlap detection

[PATCH nf] netfilter: nft_set_rbtree: revisit partial overlap detection

[Pablo Neira Ayuso]

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 ]
           <---------->

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.

Fixes: 7c84d41416d8 ("netfilter: nft_set_rbtree: Detect partial overlaps on insertion")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
This is coming after https://bugzilla.netfilter.org/show_bug.cgi?id=1449
I have removed the documentation in the code, although I could have updated it.
This patch description what kind of overlaps can be detected.

 net/netfilter/nft_set_rbtree.c | 86 ++++++++++++----------------------
 1 file changed, 29 insertions(+), 57 deletions(-)

diff --git a/net/netfilter/nft_set_rbtree.c b/net/netfilter/nft_set_rbtree.c
index b6aad3fc46c3..a70decea3e8c 100644
--- a/net/netfilter/nft_set_rbtree.c
+++ b/net/netfilter/nft_set_rbtree.c
@@ -225,39 +225,6 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set,
 	bool overlap = false;
 	int d;
 
-	/* Detect overlaps as we descend the tree. Set the flag in these cases:
-	 *
-	 * a1. _ _ __>|  ?_ _ __|  (insert end before existing end)
-	 * a2. _ _ ___|  ?_ _ _>|  (insert end after existing end)
-	 * a3. _ _ ___? >|_ _ __|  (insert start before existing end)
-	 *
-	 * and clear it later on, as we eventually reach the points indicated by
-	 * '?' above, in the cases described below. We'll always meet these
-	 * later, locally, due to tree ordering, and overlaps for the intervals
-	 * that are the closest together are always evaluated last.
-	 *
-	 * b1. _ _ __>|  !_ _ __|  (insert end before existing start)
-	 * b2. _ _ ___|  !_ _ _>|  (insert end after existing start)
-	 * b3. _ _ ___! >|_ _ __|  (insert start after existing end)
-	 *
-	 * Case a3. resolves to b3.:
-	 * - if the inserted start element is the leftmost, because the '0'
-	 *   element in the tree serves as end element
-	 * - otherwise, if an existing end is found. Note that end elements are
-	 *   always inserted after corresponding start elements.
-	 *
-	 * For a new, rightmost pair of elements, we'll hit cases b3. and b2.,
-	 * in that order.
-	 *
-	 * The flag is also cleared in two special cases:
-	 *
-	 * b4. |__ _ _!|<_ _ _   (insert start right before existing end)
-	 * b5. |__ _ >|!__ _ _   (insert end right after existing start)
-	 *
-	 * which always happen as last step and imply that no further
-	 * overlapping is possible.
-	 */
-
 	parent = NULL;
 	p = &priv->root.rb_node;
 	while (*p != NULL) {
@@ -269,44 +236,49 @@ static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set,
 		if (d < 0) {
 			p = &parent->rb_left;
 
-			if (nft_rbtree_interval_start(new)) {
-				if (nft_rbtree_interval_end(rbe) &&
-				    nft_set_elem_active(&rbe->ext, genmask) &&
-				    !nft_set_elem_expired(&rbe->ext))
-					overlap = false;
-			} else {
-				overlap = nft_rbtree_interval_end(rbe) &&
-					  nft_set_elem_active(&rbe->ext,
-							      genmask) &&
-					  !nft_set_elem_expired(&rbe->ext);
-			}
+			if (nft_set_is_anonymous(set) ||
+			    !nft_set_elem_active(&rbe->ext, genmask) ||
+			    nft_set_elem_expired(&rbe->ext))
+				continue;
+
+			if (nft_rbtree_interval_start(new) &&
+			    nft_rbtree_interval_start(rbe))
+				overlap = true;
+			else
+				overlap = false;
 		} else if (d > 0) {
 			p = &parent->rb_right;
 
-			if (nft_rbtree_interval_end(new)) {
-				overlap = nft_rbtree_interval_end(rbe) &&
-					  nft_set_elem_active(&rbe->ext,
-							      genmask) &&
-					  !nft_set_elem_expired(&rbe->ext);
-			} else if (nft_rbtree_interval_end(rbe) &&
-				   nft_set_elem_active(&rbe->ext, genmask) &&
-				   !nft_set_elem_expired(&rbe->ext)) {
+			if (nft_set_is_anonymous(set) ||
+			    !nft_set_elem_active(&rbe->ext, genmask) ||
+			    nft_set_elem_expired(&rbe->ext))
+				continue;
+
+			if (nft_rbtree_interval_end(new) &&
+			    nft_rbtree_interval_end(rbe))
 				overlap = true;
-			}
+			else
+				overlap = false;
 		} else {
 			if (nft_rbtree_interval_end(rbe) &&
 			    nft_rbtree_interval_start(new)) {
 				p = &parent->rb_left;
 
-				if (nft_set_elem_active(&rbe->ext, genmask) &&
-				    !nft_set_elem_expired(&rbe->ext))
+				if (!nft_set_elem_active(&rbe->ext, genmask) ||
+				    nft_set_elem_expired(&rbe->ext))
+					continue;
+
+				if (!nft_set_is_anonymous(set))
 					overlap = false;
 			} else if (nft_rbtree_interval_start(rbe) &&
 				   nft_rbtree_interval_end(new)) {
 				p = &parent->rb_right;
 
-				if (nft_set_elem_active(&rbe->ext, genmask) &&
-				    !nft_set_elem_expired(&rbe->ext))
+				if (!nft_set_elem_active(&rbe->ext, genmask) ||
+				    nft_set_elem_expired(&rbe->ext))
+					continue;
+
+				if (!nft_set_is_anonymous(set))
 					overlap = false;
 			} else if (nft_set_elem_active(&rbe->ext, genmask) &&
 				   !nft_set_elem_expired(&rbe->ext)) {
-- 
2.20.1

Re: [PATCH nf] netfilter: nft_set_rbtree: revisit partial overlap detection

[Stefano Brivio]

Hi, sorry for the delay.

On Fri, 14 Aug 2020 21:21:26 +0200
Pablo Neira Ayuso <pablo@netfilter.org> 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