Skip to contentSkip to conversation

segtree: Check ranges when deleting elements

PATCH In review Phil Sutter 2 participants 3 messages Nov 12, 2019 – Nov 16, 2019 netfilter

lore
Share & tools
lore

Phil Sutter

author reviewer
#0 lore raw

PATCH 1/1 segtree: Check ranges when deleting elements

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 }
| 	}
| }
---
 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
src/segtree.c +30 -11
index 5d6ecd4fcab1f..10c82eed5378f 100644
@@ -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;
 	}
tests/shell/testcases/sets/0039delete_interval_0 new file +17 -0
new file mode 100755
index 0000000000000..19df16ec0e588
@@ -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
Signature · 1 line
2.24.0
maintainer Acked-by on v1 1/1
#1 lore raw
Quoted 23 lines · Phil Sutter

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 }
| 	}
| }
Quoted 1 line
author reviewer
#2 lore raw
In reply to Phil Sutter

Hi,

Quoted 14 lines · Phil Sutter

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
Quoted 8 lines
| 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