diff mbox series

[nft] segtree: Check ranges when deleting elements

Message ID 20191112191007.9752-1-phil@nwl.cc
State Accepted
Delegated to: Pablo Neira
Headers show
Series [nft] segtree: Check ranges when deleting elements | expand

Commit Message

Phil Sutter Nov. 12, 2019, 7:10 p.m. UTC 
Make sure any intervals to delete actually exist, otherwise reject the
command. Without this, it is possible to mess up rbtree contents:

| # nft list ruleset
| table ip t {
| 	set s {
| 		type ipv4_addr
| 		flags interval
| 		auto-merge
| 		elements = { 192.168.1.0-192.168.1.254, 192.168.1.255 }
| 	}
| }
| # nft delete element t s '{ 192.168.1.0/24 }'
| # nft list ruleset
| table ip t {
| 	set s {
| 		type ipv4_addr
| 		flags interval
| 		auto-merge
| 		elements = { 192.168.1.255-255.255.255.255 }
| 	}
| }

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 src/segtree.c                                 | 41 ++++++++++++++-----
 .../testcases/sets/0039delete_interval_0      | 17 ++++++++
 2 files changed, 47 insertions(+), 11 deletions(-)
 create mode 100755 tests/shell/testcases/sets/0039delete_interval_0

Comments

Pablo Neira Ayuso Nov. 13, 2019, 11:11 p.m. UTC | #1 
On Tue, Nov 12, 2019 at 08:10:07PM +0100, Phil Sutter wrote:
> Make sure any intervals to delete actually exist, otherwise reject the
> command. Without this, it is possible to mess up rbtree contents:
> 
> | # nft list ruleset
> | table ip t {
> | 	set s {
> | 		type ipv4_addr
> | 		flags interval
> | 		auto-merge
> | 		elements = { 192.168.1.0-192.168.1.254, 192.168.1.255 }
> | 	}
> | }
> | # nft delete element t s '{ 192.168.1.0/24 }'
> | # nft list ruleset
> | table ip t {
> | 	set s {
> | 		type ipv4_addr
> | 		flags interval
> | 		auto-merge
> | 		elements = { 192.168.1.255-255.255.255.255 }
> | 	}
> | }
> 
> Signed-off-by: Phil Sutter <phil@nwl.cc>

Acked-by: Pablo Neira Ayuso <pablo@netfilter.org>
Phil Sutter Nov. 16, 2019, 7:43 p.m. UTC | #2 
Hi,

On Tue, Nov 12, 2019 at 08:10:07PM +0100, Phil Sutter wrote:
> Make sure any intervals to delete actually exist, otherwise reject the
> command. Without this, it is possible to mess up rbtree contents:
> 
> | # nft list ruleset
> | table ip t {
> | 	set s {
> | 		type ipv4_addr
> | 		flags interval
> | 		auto-merge
> | 		elements = { 192.168.1.0-192.168.1.254, 192.168.1.255 }
> | 	}
> | }
> | # nft delete element t s '{ 192.168.1.0/24 }'
> | # nft list ruleset
> | table ip t {
> | 	set s {
> | 		type ipv4_addr
> | 		flags interval
> | 		auto-merge
> | 		elements = { 192.168.1.255-255.255.255.255 }
> | 	}
> | }

Sadly, this breaks tests/monitor/testcases/set-simple.t. The reason is
that 'add element' command does not add the new element to set in cache
and my change requires for 'delete element' command to find the range in
cache. Above test case basically does:

| # nft 'add element ip t s { 10-20 }; delete element ip t s { 10-20 }'

This is not really a common use-case, but still worth fixing IMO.

Sorry, Phil
diff mbox series

Patch

diff --git a/src/segtree.c b/src/segtree.c
index 5d6ecd4fcab1f..10c82eed5378f 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -334,6 +334,13 @@  static unsigned int expr_to_intervals(const struct expr *set,
 	return n;
 }
 
+static bool intervals_match(const struct elementary_interval *e1,
+			    const struct elementary_interval *e2)
+{
+	return mpz_cmp(e1->left, e2->left) == 0 &&
+	       mpz_cmp(e1->right, e2->right) == 0;
+}
+
 /* This function checks for overlaps in two ways:
  *
  * 1) A new interval end intersects an existing interval.
@@ -343,8 +350,7 @@  static unsigned int expr_to_intervals(const struct expr *set,
 static bool interval_overlap(const struct elementary_interval *e1,
 			     const struct elementary_interval *e2)
 {
-	if (mpz_cmp(e1->left, e2->left) == 0 &&
-	    mpz_cmp(e1->right, e2->right) == 0)
+	if (intervals_match(e1, e2))
 		return false;
 
 	return (mpz_cmp(e1->left, e2->left) >= 0 &&
@@ -356,7 +362,7 @@  static bool interval_overlap(const struct elementary_interval *e1,
 }
 
 static int set_overlap(struct list_head *msgs, const struct set *set,
-		       struct expr *init, unsigned int keylen)
+		       struct expr *init, unsigned int keylen, bool add)
 {
 	struct elementary_interval *new_intervals[init->size];
 	struct elementary_interval *intervals[set->init->size];
@@ -367,15 +373,28 @@  static int set_overlap(struct list_head *msgs, const struct set *set,
 	m = expr_to_intervals(set->init, keylen, intervals);
 
 	for (i = 0; i < n; i++) {
-		for (j = 0; j < m; j++) {
-			if (!interval_overlap(new_intervals[i], intervals[j]))
-				continue;
+		bool found = false;
 
+		for (j = 0; j < m; j++) {
+			if (add && interval_overlap(new_intervals[i],
+						    intervals[j])) {
+				expr_error(msgs, new_intervals[i]->expr,
+					   "interval overlaps with an existing one");
+				errno = EEXIST;
+				ret = -1;
+				goto out;
+			} else if (!add && intervals_match(new_intervals[i],
+							   intervals[j])) {
+				found = true;
+				break;
+			}
+		}
+		if (!add && !found) {
 			expr_error(msgs, new_intervals[i]->expr,
-				   "interval overlaps with an existing one");
-			errno = EEXIST;
+				   "interval not found in set");
+			errno = ENOENT;
 			ret = -1;
-			goto out;
+			break;
 		}
 	}
 out:
@@ -399,8 +418,8 @@  static int set_to_segtree(struct list_head *msgs, struct set *set,
 	/* We are updating an existing set with new elements, check if the new
 	 * interval overlaps with any of the existing ones.
 	 */
-	if (add && set->init && set->init != init) {
-		err = set_overlap(msgs, set, init, tree->keylen);
+	if (set->init && set->init != init) {
+		err = set_overlap(msgs, set, init, tree->keylen, add);
 		if (err < 0)
 			return err;
 	}
diff --git a/tests/shell/testcases/sets/0039delete_interval_0 b/tests/shell/testcases/sets/0039delete_interval_0
new file mode 100755
index 0000000000000..19df16ec0e588
--- /dev/null
+++ b/tests/shell/testcases/sets/0039delete_interval_0
@@ -0,0 +1,17 @@ 
+#!/bin/bash
+
+# Make sure nft allows to delete existing ranges only
+
+RULESET="
+table t {
+	set s {
+		type ipv4_addr
+		flags interval
+		elements = { 192.168.1.0-192.168.1.254, 192.168.1.255 }
+	}
+}"
+
+$NFT -f - <<< "$RULESET" || { echo "E: Can't load basic ruleset" 1>&2; exit 1; }
+
+$NFT delete element t s '{ 192.168.1.0/24 }' 2>/dev/null || exit 0
+echo "E: Deletion of non-existing range allowed" 1>&2