segtree: Check ranges when deleting elements
Phil Sutter
reviewerPATCH 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
@@ -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
@@ -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
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
Signed-off-by Phil Sutter <[email protected]>
Phil Sutter
reviewerHi,
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