unbreak element deletion in map with ranges
Pablo Neira Ayuso
maintainercover 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.
AbortedSame 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
Pablo Neira Ayuso
maintainerPATCH 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.
--- src/evaluate.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-)
src/evaluate.c +11 -1
@@ -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
Pablo Neira Ayuso
maintainerPATCH 2/4 segtree: set on EXPR_F_KERNEL flag for catchall elements in the cache
In reply to Pablo Neira AyusoCatchall set element deletion requires this flag to be set on, otherwise it bogusly reports that such element does not exist in the set.
--- src/segtree.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
src/segtree.c +3 -1
@@ -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
Pablo Neira Ayuso
maintainerPATCH 3/4 intervals: fix element deletions with maps
In reply to Pablo Neira AyusoSet 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.
AbortedCall 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.
--- src/intervals.c | 31 ++++++++++++++++++------------- 1 file changed, 18 insertions(+), 13 deletions(-)
src/intervals.c +18 -13
@@ -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
Pablo Neira Ayuso
maintainerPATCH 4/4 tests: shell: cover set element deletion in maps
In reply to Pablo Neira AyusoExtend 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
@@ -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
@@ -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
@@ -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
@@ -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