Skip to contentSkip to conversation

netfilter: nft_set_rbtree: revisit partial overlap detection

PATCH In review Pablo Neira Ayuso 2 participants 2 messages Aug 14, 2020 – Aug 19, 2020

Subsystems (2)
lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

PATCH 1/1 netfilter: nft_set_rbtree: revisit partial overlap detection

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")

---
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(-)
net/netfilter/nft_set_rbtree.c +29 -57
index b6aad3fc46c3..a70decea3e8c 100644
@@ -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)) {
Signature · 1 line
2.20.1
#1 lore raw

Hi, sorry for the delay.

Quoted 14 lines · On Fri, 14 Aug 2020 21:21:26 +0200 Pablo Neira Ayuso <[email protected]>…

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.

Quoted 8 lines

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).

Quoted 7 lines

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.

Signature · 1 line
Stefano