[PATCH nft 0/4] unbreak element deletion in map with ranges

[PATCH nft 0/4] unbreak element deletion in map with ranges

[Pablo Neira Ayuso]

Hi,

The following series fixes element deletion in maps with ranges
(ie. those with interval flag set on):

 # nft delete element ip filter mymap { 0-2400000 }
 BUG: invalid range expression type set element
 nft: src/expression.c:1472: range_expr_value_low: Assertion `0' failed.
 Aborted

Same BUG notice is reported when deleting catchall in maps with ranges,
this is related to the src/interval.c code that deals with element
deletions.

Patch #1 sets on expr->len for catchall elements since this is required
	 by map element deletion, which relies on mergesort.

Patch #2 sets on EXPR_F_KERNEL for catchall elements which is required
	 by map element deletion to identify matching elements already
	 in the kernel.

Patch #3 fixes set element deletion in maps with ranges. Use expr->left
         to fetch the key range but still expr->flags to fetch
	 EXPR_F_REMOVE and the expression itself when moving elements
	 to the purge list.

Patch #4 extends test coverage for this usecase.

Pablo Neira Ayuso (4):
  evaluate: set on expr->len for catchall set elements
  segtree: set on EXPR_F_KERNEL flag for catchall elements in the cache
  intervals: fix element deletions with maps
  tests: shell: cover set element deletion in maps

 src/evaluate.c                                | 12 ++++++-
 src/intervals.c                               | 31 +++++++++-------
 src/segtree.c                                 |  4 ++-
 tests/shell/testcases/maps/delete_element     | 28 +++++++++++++++
 .../testcases/maps/delete_element_catchall    | 35 +++++++++++++++++++
 .../maps/dumps/delete_elem_catchall.nft       | 12 +++++++
 .../testcases/maps/dumps/delete_element.nft   | 12 +++++++
 7 files changed, 119 insertions(+), 15 deletions(-)
 create mode 100755 tests/shell/testcases/maps/delete_element
 create mode 100755 tests/shell/testcases/maps/delete_element_catchall
 create mode 100644 tests/shell/testcases/maps/dumps/delete_elem_catchall.nft
 create mode 100644 tests/shell/testcases/maps/dumps/delete_element.nft

-- 
2.30.2

[PATCH nft 1/4] evaluate: set on expr->len for catchall set elements

[Pablo Neira Ayuso]

Catchall elements coming from the parser provide expr->len == 0.
However, the existing mergesort implementation requires expr->len to be
set up to the length of the set key to properly sort elements.

In particular, set element deletion leverages such list sorting to find
if elements exists in the set.

Fixes: 419d19688688 ("src: add set element catch-all support")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/evaluate.c | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

diff --git a/src/evaluate.c b/src/evaluate.c
index aa9293a87856..0a31c73e4276 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1877,6 +1877,16 @@ err_missing_flag:
 			  set_is_map(ctx->set->flags) ? "map" : "set", expr_name(key));
 }
 
+static int expr_evaluate_set_elem_catchall(struct eval_ctx *ctx, struct expr **expr)
+{
+	struct expr *elem = *expr;
+
+	if (ctx->set)
+		elem->len = ctx->set->key->len;
+
+	return 0;
+}
+
 static const struct expr *expr_set_elem(const struct expr *expr)
 {
 	if (expr->etype == EXPR_MAPPING)
@@ -2996,7 +3006,7 @@ static int expr_evaluate(struct eval_ctx *ctx, struct expr **expr)
 	case EXPR_XFRM:
 		return expr_evaluate_xfrm(ctx, expr);
 	case EXPR_SET_ELEM_CATCHALL:
-		return 0;
+		return expr_evaluate_set_elem_catchall(ctx, expr);
 	case EXPR_FLAGCMP:
 		return expr_evaluate_flagcmp(ctx, expr);
 	default:
-- 
2.30.2

[PATCH nft 2/4] segtree: set on EXPR_F_KERNEL flag for catchall elements in the cache

[Pablo Neira Ayuso]

Catchall set element deletion requires this flag to be set on,
otherwise it bogusly reports that such element does not exist
in the set.

Fixes: f1cc44edb218 ("src: add EXPR_F_KERNEL to identify expression in the kernel")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/segtree.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/src/segtree.c b/src/segtree.c
index 5e6f857f85b7..4df96467c3f5 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -629,8 +629,10 @@ void interval_map_decompose(struct expr *set)
 	expr_free(i);
 
 out:
-	if (catchall)
+	if (catchall) {
+		catchall->flags |= EXPR_F_KERNEL;
 		compound_expr_add(set, catchall);
+	}
 
 	free(ranges);
 	free(elements);
-- 
2.30.2

[PATCH nft 3/4] intervals: fix element deletions with maps

[Pablo Neira Ayuso]

Set element deletion in maps (including catchall elements) does not work.

 # nft delete element ip x m { \* }
 BUG: invalid range expression type catch-all set element
 nft: src/expression.c:1472: range_expr_value_low: Assertion `0' failed.
 Aborted

Call interval_expr_key() to fetch expr->left in the mapping but use the
expression that represents the mapping because it provides access to the
EXPR_F_REMOVE flags.

Moreover, assume maximum value for catchall expression by means of the
expr->len to reuse the existing code to check if the element to be
deleted really exists.

Fixes: 3e8d934e4f72 ("intervals: support to partial deletion with automerge")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/intervals.c | 31 ++++++++++++++++++-------------
 1 file changed, 18 insertions(+), 13 deletions(-)

diff --git a/src/intervals.c b/src/intervals.c
index 6c3f36fec02a..ff202be9375b 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -383,7 +383,7 @@ static int setelem_delete(struct list_head *msgs, struct set *set,
 			  struct expr *purge, struct expr *elems,
 			  unsigned int debug_mask)
 {
-	struct expr *i, *next, *prev = NULL;
+	struct expr *i, *next, *elem, *prev = NULL;
 	struct range range, prev_range;
 	int err = 0;
 	mpz_t rop;
@@ -394,21 +394,26 @@ static int setelem_delete(struct list_head *msgs, struct set *set,
 	mpz_init(range.high);
 	mpz_init(rop);
 
-	list_for_each_entry_safe(i, next, &elems->expressions, list) {
-		if (i->key->etype == EXPR_SET_ELEM_CATCHALL)
-			continue;
+	list_for_each_entry_safe(elem, next, &elems->expressions, list) {
+		i = interval_expr_key(elem);
 
-		range_expr_value_low(range.low, i);
-		range_expr_value_high(range.high, i);
+		if (i->key->etype == EXPR_SET_ELEM_CATCHALL) {
+			/* Assume max value to simplify handling. */
+			mpz_bitmask(range.low, i->len);
+			mpz_bitmask(range.high, i->len);
+		} else {
+			range_expr_value_low(range.low, i);
+			range_expr_value_high(range.high, i);
+		}
 
-		if (!prev && i->flags & EXPR_F_REMOVE) {
+		if (!prev && elem->flags & EXPR_F_REMOVE) {
 			expr_error(msgs, i, "element does not exist");
 			err = -1;
 			goto err;
 		}
 
-		if (!(i->flags & EXPR_F_REMOVE)) {
-			prev = i;
+		if (!(elem->flags & EXPR_F_REMOVE)) {
+			prev = elem;
 			mpz_set(prev_range.low, range.low);
 			mpz_set(prev_range.high, range.high);
 			continue;
@@ -416,12 +421,12 @@ static int setelem_delete(struct list_head *msgs, struct set *set,
 
 		if (mpz_cmp(prev_range.low, range.low) == 0 &&
 		    mpz_cmp(prev_range.high, range.high) == 0) {
-			if (i->flags & EXPR_F_REMOVE) {
+			if (elem->flags & EXPR_F_REMOVE) {
 				if (prev->flags & EXPR_F_KERNEL)
 					list_move_tail(&prev->list, &purge->expressions);
 
-				list_del(&i->list);
-				expr_free(i);
+				list_del(&elem->list);
+				expr_free(elem);
 			}
 		} else if (set->automerge) {
 			if (setelem_adjust(set, purge, &prev_range, &range, prev, i) < 0) {
@@ -429,7 +434,7 @@ static int setelem_delete(struct list_head *msgs, struct set *set,
 				err = -1;
 				goto err;
 			}
-		} else if (i->flags & EXPR_F_REMOVE) {
+		} else if (elem->flags & EXPR_F_REMOVE) {
 			expr_error(msgs, i, "element does not exist");
 			err = -1;
 			goto err;
-- 
2.30.2

[PATCH nft 4/4] tests: shell: cover set element deletion in maps

[Pablo Neira Ayuso]

Extend existing coverage to deal with set element deletion, including
catchall elements too.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 tests/shell/testcases/maps/delete_element     | 28 +++++++++++++++
 .../testcases/maps/delete_element_catchall    | 35 +++++++++++++++++++
 .../maps/dumps/delete_elem_catchall.nft       | 12 +++++++
 .../testcases/maps/dumps/delete_element.nft   | 12 +++++++
 4 files changed, 87 insertions(+)
 create mode 100755 tests/shell/testcases/maps/delete_element
 create mode 100755 tests/shell/testcases/maps/delete_element_catchall
 create mode 100644 tests/shell/testcases/maps/dumps/delete_elem_catchall.nft
 create mode 100644 tests/shell/testcases/maps/dumps/delete_element.nft

diff --git a/tests/shell/testcases/maps/delete_element b/tests/shell/testcases/maps/delete_element
new file mode 100755
index 000000000000..75272f448dbf
--- /dev/null
+++ b/tests/shell/testcases/maps/delete_element
@@ -0,0 +1,28 @@
+#!/bin/bash
+
+set -e
+
+RULESET="flush ruleset
+
+table ip x {
+        map m {
+                typeof ct bytes : meta priority
+                flags interval
+                elements = {
+                        0-2048000 : 1:0001,
+                        2048001-4000000 : 1:0002,
+                }
+        }
+
+        chain y {
+                type filter hook output priority 0; policy accept;
+
+                meta priority set ct bytes map @m
+        }
+}"
+
+$NFT -f - <<< $RULESET
+
+$NFT delete element ip x m { 0-2048000 }
+$NFT add element ip x m { 0-2048000 : 1:0002 }
+$NFT delete element ip x m { 0-2048000 : 1:0002 }
diff --git a/tests/shell/testcases/maps/delete_element_catchall b/tests/shell/testcases/maps/delete_element_catchall
new file mode 100755
index 000000000000..a6a0fc6f3e04
--- /dev/null
+++ b/tests/shell/testcases/maps/delete_element_catchall
@@ -0,0 +1,35 @@
+#!/bin/bash
+
+# NFT_TEST_REQUIRES(NFT_TEST_HAVE_catchall_element)
+
+set -e
+
+RULESET="flush ruleset
+
+table ip x {
+        map m {
+                typeof ct bytes : meta priority
+                flags interval
+                elements = {
+                        0-2048000 : 1:0001,
+                        * : 1:0002,
+                }
+        }
+
+        chain y {
+                type filter hook output priority 0; policy accept;
+
+                meta priority set ct bytes map @m
+        }
+}"
+
+$NFT -f - <<< $RULESET
+
+$NFT delete element ip x m { 0-2048000 }
+$NFT add element ip x m { 0-2048000 : 1:0002 }
+$NFT delete element ip x m { 0-2048000 : 1:0002 }
+
+$NFT 'delete element ip x m { * }'
+$NFT 'add element ip x m { * : 1:0003 }'
+$NFT 'delete element ip x m { * : 1:0003 }'
+$NFT 'add element ip x m { * : 1:0003 }'
diff --git a/tests/shell/testcases/maps/dumps/delete_elem_catchall.nft b/tests/shell/testcases/maps/dumps/delete_elem_catchall.nft
new file mode 100644
index 000000000000..14054f4dc4d5
--- /dev/null
+++ b/tests/shell/testcases/maps/dumps/delete_elem_catchall.nft
@@ -0,0 +1,12 @@
+table ip x {
+	map m {
+		typeof ct bytes : meta priority
+		flags interval
+		elements = { * : 1:3 }
+	}
+
+	chain y {
+		type filter hook output priority filter; policy accept;
+		meta priority set ct bytes map @m
+	}
+}
diff --git a/tests/shell/testcases/maps/dumps/delete_element.nft b/tests/shell/testcases/maps/dumps/delete_element.nft
new file mode 100644
index 000000000000..5275b4dc2a68
--- /dev/null
+++ b/tests/shell/testcases/maps/dumps/delete_element.nft
@@ -0,0 +1,12 @@
+table ip x {
+	map m {
+		typeof ct bytes : meta priority
+		flags interval
+		elements = { 2048001-4000000 : 1:2 }
+	}
+
+	chain y {
+		type filter hook output priority filter; policy accept;
+		meta priority set ct bytes map @m
+	}
+}
-- 
2.30.2