Skip to contentSkip to conversation

unbreak element deletion in map with ranges

PATCH New Pablo Neira Ayuso 1 participant 5 messages Jul 4, 2024 netfilter

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

cover unbreak element deletion in map with ranges

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
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

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

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")
---
 src/evaluate.c | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)
src/evaluate.c +11 -1
index aa9293a87856..0a31c73e4276 100644
@@ -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:
Signature · 1 line
2.30.2
author maintainer
#2 lore raw

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

In reply to 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")
---
 src/segtree.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
src/segtree.c +3 -1
index 5e6f857f85b7..4df96467c3f5 100644
@@ -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);
Signature · 1 line
2.30.2
author maintainer
#3 lore raw

PATCH 3/4 intervals: fix element deletions with maps

In reply to 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")
---
 src/intervals.c | 31 ++++++++++++++++++-------------
 1 file changed, 18 insertions(+), 13 deletions(-)
src/intervals.c +18 -13
index 6c3f36fec02a..ff202be9375b 100644
@@ -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;
Signature · 1 line
2.30.2
author maintainer
#4 lore raw

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

In reply to Pablo Neira Ayuso

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

---
 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
tests/shell/testcases/maps/delete_element new file +28 -0
new file mode 100755
index 000000000000..75272f448dbf
@@ -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 }
tests/shell/testcases/maps/delete_element_catchall new file +35 -0
new file mode 100755
index 000000000000..a6a0fc6f3e04
@@ -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 }'
tests/shell/testcases/maps/dumps/delete_elem_catchall.nft new file +12 -0
new file mode 100644
index 000000000000..14054f4dc4d5
@@ -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
+	}
+}
tests/shell/testcases/maps/dumps/delete_element.nft new file +12 -0
new file mode 100644
index 000000000000..5275b4dc2a68
@@ -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
+	}
+}
Signature · 1 line
2.30.2