Two bugfixes around prefixes in sets
Phil Sutter
reviewercover Two bugfixes around prefixes in sets
Patch 1 fixes a pretty obvious typo, leading to prefixes not showing their expiry time.
The remaining patches deal with wrong behaviour of 'get element' command when looking up prefixes. This could have been simple, 'get element' would return the prefix address but prefix length was missing.
While digging through the code, I eventually found out that get_set_interval_find() and get_set_interval_end() didn't respect prefix elements but cared about range elements only.
I am still not entirely sure how the code really works and why everything is needed, but the test case added in patch 4 and some debug output showed that things could be simplified quite a bit. Since this also streamlined adding prefix support, I went ahead with it.
Phil Sutter (4):
segtree: Fix missing expires value in prefixes
segtree: Use expr_clone in get_set_interval_*()
segtree: Merge get_set_interval_find() and get_set_interval_end()
segtree: Fix get element command with prefixes
src/segtree.c | 70 +++++--------------- tests/shell/testcases/sets/0034get_element_0 | 51 +++++++++----- 2 files changed, 51 insertions(+), 70 deletions(-)
Signature · 1 line
2.25.1
Phil Sutter
reviewerPATCH 1/4 segtree: Fix missing expires value in prefixes
This probable copy'n'paste bug prevented 'expiration' field from being populated when turning a range into a prefix in interval_map_decompose(). Consequently, interval sets with timeout did print expiry value for ranges (such as 10.0.0.1-10.0.0.5) but not prefixes (10.0.0.0/8, for instance).
--- src/segtree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
src/segtree.c +1 -1
@@ -1099,7 +1099,7 @@ void interval_map_decompose(struct expr *set) prefix->comment =xstrdup (low->comment);if (low->timeout) prefix->timeout = low->timeout; -if (low->left->expiration) +if (low->expiration) prefix->expiration = low->expiration; }
Signature · 1 line
2.25.1
Phil Sutter
reviewerPATCH 2/4 segtree: Use expr_clone in get_set_interval_*()
In reply to Phil SutterBoth functions perform interval set lookups with either start and end or only start values as input. Interestingly, in practice they either see values which are not contained or which match an existing range exactly.
Make use of the above and just return a clone of the matching entry instead of creating a new one based on input data.
--- src/segtree.c | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-)
src/segtree.c +2 -6
@@ -708,9 +708,7 @@ static struct expr *get_set_interval_find(const struct table *table,range_expr_value_high (high, i);if (mpz_cmp (left->key->value, low) >=0 &&mpz_cmp (right->key->value, high) <=0 ) { - range =range_expr_alloc (&internal_location, -expr_clone (left->key), -expr_clone (right->key)); + range =expr_clone (i->key); goto out; }break ;
@@ -742,9 +740,7 @@ static struct expr *get_set_interval_end(const struct table *table,case EXPR_RANGE :range_expr_value_low (low, i);if (mpz_cmp (low, left->key->value) ==0 ) { - range =range_expr_alloc (&internal_location, -expr_clone (left->key), -expr_clone (i->key->right)); + range =expr_clone (i->key); goto out; }break ;
Signature · 1 line
2.25.1
Phil Sutter
reviewerPATCH 3/4 segtree: Merge get_set_interval_find() and get_set_interval_end()
In reply to Phil SutterBoth functions were very similar already. Under the assumption that they will always either see a range (or start of) that matches exactly or not at all, reduce complexity and make get_set_interval_find() accept NULL (left or) right values. This way it becomes a full replacement for get_set_interval_end().
--- src/segtree.c | 63 +++++++++++++-------------------------------------- 1 file changed, 16 insertions(+), 47 deletions(-)
src/segtree.c +16 -47
@@ -694,63 +694,31 @@ static struct expr *get_set_interval_find(const struct table *table, {struct expr *range =NULL ;struct set *set; -mpz_t low, high;struct expr *i; +mpz_t val; set =set_lookup (table, set_name); -mpz_init2 (low, set->key->len); -mpz_init2 (high, set->key->len); +mpz_init2 (val, set->key->len);list_for_each_entry (i, &set->init->expressions, list) {switch (i->key->etype) {case EXPR_RANGE : -range_expr_value_low (low, i); -range_expr_value_high (high, i); -if (mpz_cmp (left->key->value, low) >=0 && -mpz_cmp (right->key->value, high) <=0 ) { - range =expr_clone (i->key); - goto out; - } -break ; -default : -break ; - } - } -out: -mpz_clear (low); -mpz_clear (high); - -return range; -} - -static struct expr *get_set_interval_end (const struct table *table, -const char *set_name, -struct expr *left) -{ -struct expr *i, *range =NULL ; -struct set *set; -mpz_t low, high; +range_expr_value_low (val, i); +if (left &&mpz_cmp (left->key->value, val)) +break ; - set =set_lookup (table, set_name); -mpz_init2 (low, set->key->len); -mpz_init2 (high, set->key->len); +range_expr_value_high (val, i); +if (right &&mpz_cmp (right->key->value, val)) +break ; -list_for_each_entry (i, &set->init->expressions, list) { -switch (i->key->etype) { -case EXPR_RANGE : -range_expr_value_low (low, i); -if (mpz_cmp (low, left->key->value) ==0 ) { - range =expr_clone (i->key); - goto out; - } -break ; + range =expr_clone (i->key); + goto out;default :break ; } } out: -mpz_clear (low); -mpz_clear (high); +mpz_clear (val);return range; }
@@ -780,9 +748,9 @@ int get_set_decompose(struct table *table, struct set *set) left =NULL ; }else {if (left) { - range =get_set_interval_end (table, - set->handle.set.name, - left); + range =get_set_interval_find (table, + set->handle.set.name, + left,NULL );if (range)compound_expr_add (new_init, range);else
@@ -793,7 +761,8 @@ int get_set_decompose(struct table *table, struct set *set) } }if (left) { - range =get_set_interval_end (table, set->handle.set.name, left); + range =get_set_interval_find (table, set->handle.set.name, + left,NULL );if (range)compound_expr_add (new_init, range);else
Signature · 1 line
2.25.1
Pablo Neira Ayuso
maintainerRe: [nft PATCH 3/4] segtree: Merge get_set_interval_find() and get_set_interval_end()
Quoted 5 lines · Phil Sutter
Both functions were very similar already. Under the assumption that they will always either see a range (or start of) that matches exactly or not at all, reduce complexity and make
get_set_interval_find()accept NULL (left or) right values. This way it becomes a full replacement forget_set_interval_end().
I have to go back to the commit log of this patch, IIRC my intention here was to allow users to ask for a single element, then return the range that contains it.
Pablo Neira Ayuso
maintainerRe: [nft PATCH 3/4] segtree: Merge get_set_interval_find() and get_set_interval_end()
Quoted 10 lines · Pablo Neira Ayuso
Quoted 5 lines · Phil Sutter
Both functions were very similar already. Under the assumption that they will always either see a range (or start of) that matches exactly or not at all, reduce complexity and make
get_set_interval_find()accept NULL (left or) right values. This way it becomes a full replacement forget_set_interval_end().I have to go back to the commit log of this patch, IIRC my intention here was to allow users to ask for a single element, then return the range that contains it.
# nft add table x
# nft add set x y { type ipv4_addr\; flags interval\; }
# nft add element x y { 1.1.1.1-2.2.2.2 }
# nft get element x y { 1.1.1.2 }
table ip x {
set y {
type ipv4_addr
flags interval
elements = { 1.1.1.1-2.2.2.2 }
}
}Otherwise it might not be so useful for users.
If the number of elements is huge, then this 'get' command is not so useful, right?
BTW, are get commands to the pipapo set working like this too?
Thanks.
Phil Sutter
reviewerRe: [nft PATCH 3/4] segtree: Merge get_set_interval_find() and get_set_interval_end()
Hi Pablo,
Quoted 11 lines · Pablo Neira Ayuso
Quoted 10 lines · Pablo Neira Ayuso
Quoted 5 lines · Phil Sutter
Both functions were very similar already. Under the assumption that they will always either see a range (or start of) that matches exactly or not at all, reduce complexity and make
get_set_interval_find()accept NULL (left or) right values. This way it becomes a full replacement forget_set_interval_end().I have to go back to the commit log of this patch, IIRC my intention here was to allow users to ask for a single element, then return the range that contains it.
[...]
Quoted 1 line
BTW, are get commands to the pipapo set working like this too?
Yes, indeed they do. I added some lines to cover concatenated ranges in sets/0034get_element_0 shell test, will push it out along with this series.
Thanks, Phil
Phil Sutter
reviewerRe: [nft PATCH 3/4] segtree: Merge get_set_interval_find() and get_set_interval_end()
In reply to Pablo Neira AyusoQuoted 10 lines · Pablo Neira Ayuso
Quoted 5 lines · Phil Sutter
Both functions were very similar already. Under the assumption that they will always either see a range (or start of) that matches exactly or not at all, reduce complexity and make
get_set_interval_find()accept NULL (left or) right values. This way it becomes a full replacement forget_set_interval_end().I have to go back to the commit log of this patch, IIRC my intention here was to allow users to ask for a single element, then return the range that contains it.
That was my suspicion as well, but while testing I found out that no matter what I passed to 'get element', I couldn't provoke a situation in which get_set_interval_find() would have left and right elements which didn't match exactly (or not at all).
There must be some preparation happening before the call to get_set_decompose() which normalizes things. And still, If I disable the call to get_set_decompose() entirely, tests start failing.
Cheers, Phil
Pablo Neira Ayuso
maintainerRe: [nft PATCH 3/4] segtree: Merge get_set_interval_find() and get_set_interval_end()
Quoted 12 lines · Phil Sutter
Quoted 10 lines · Pablo Neira Ayuso
Quoted 5 lines · Phil Sutter
Both functions were very similar already. Under the assumption that they will always either see a range (or start of) that matches exactly or not at all, reduce complexity and make
get_set_interval_find()accept NULL (left or) right values. This way it becomes a full replacement forget_set_interval_end().I have to go back to the commit log of this patch, IIRC my intention here was to allow users to ask for a single element, then return the range that contains it.
Quoted 8 lines
That was my suspicion as well, but while testing I found out that no matter what I passed to 'get element', I couldn't provoke a situation in which
get_set_interval_find()would have left and right elements which didn't match exactly (or not at all).There must be some preparation happening before the call to
get_set_decompose()which normalizes things. And still, If I disable the call toget_set_decompose()entirely, tests start failing.
Hm, so the approximate or exact matching is broken? Or you mean they fail because you didn't expect the approximate matching?
Phil Sutter
reviewerRe: [nft PATCH 3/4] segtree: Merge get_set_interval_find() and get_set_interval_end()
Quoted 18 lines · Pablo Neira Ayuso
Quoted 17 lines · Phil Sutter
Quoted 10 lines · Pablo Neira Ayuso
Quoted 5 lines · Phil Sutter
Both functions were very similar already. Under the assumption that they will always either see a range (or start of) that matches exactly or not at all, reduce complexity and make
get_set_interval_find()accept NULL (left or) right values. This way it becomes a full replacement forget_set_interval_end().I have to go back to the commit log of this patch, IIRC my intention here was to allow users to ask for a single element, then return the range that contains it.
That was my suspicion as well, but while testing I found out that no matter what I passed to 'get element', I couldn't provoke a situation in which
get_set_interval_find()would have left and right elements which didn't match exactly (or not at all).
Quoted 6 lines
Quoted 3 lines
There must be some preparation happening before the call to
get_set_decompose()which normalizes things. And still, If I disable the call toget_set_decompose()entirely, tests start failing.Hm, so the approximate or exact matching is broken? Or you mean they fail because you didn't expect the approximate matching?
It's the opposite: Things are working fine even after my simplifications. get_set_interval_find() expected left/right values which sit within a range, e.g. left/right of 22/23 and a set with element 20-30. But to my surprise, this doesn't happen. With these example values, left/right are 20/30, i.e. match the range in the set.
That's why I extended tests/shell/testcases/sets/0034get_element_0. Please have a look if there's a use-case I missed.
Cheers, Phil
Pablo Neira Ayuso
maintainerRe: [nft PATCH 3/4] segtree: Merge get_set_interval_find() and get_set_interval_end()
Quoted 26 lines · Phil Sutter
Quoted 18 lines · Pablo Neira Ayuso
Quoted 17 lines · Phil Sutter
Quoted 10 lines · Pablo Neira Ayuso
Quoted 5 lines · Phil Sutter
Both functions were very similar already. Under the assumption that they will always either see a range (or start of) that matches exactly or not at all, reduce complexity and make
get_set_interval_find()accept NULL (left or) right values. This way it becomes a full replacement forget_set_interval_end().I have to go back to the commit log of this patch, IIRC my intention here was to allow users to ask for a single element, then return the range that contains it.
That was my suspicion as well, but while testing I found out that no matter what I passed to 'get element', I couldn't provoke a situation in which
get_set_interval_find()would have left and right elements which didn't match exactly (or not at all).Quoted 6 lines
Quoted 3 lines
There must be some preparation happening before the call to
get_set_decompose()which normalizes things. And still, If I disable the call toget_set_decompose()entirely, tests start failing.Hm, so the approximate or exact matching is broken? Or you mean they fail because you didn't expect the approximate matching?
Quoted 8 lines
It's the opposite: Things are working fine even after my simplifications.
get_set_interval_find()expected left/right values which sit within a range, e.g. left/right of 22/23 and a set with element 20-30. But to my surprise, this doesn't happen. With these example values, left/right are 20/30, i.e. match the range in the set.That's why I extended tests/shell/testcases/sets/0034get_element_0. Please have a look if there's a use-case I missed.
This looks good indeed. Please, push this out.
Thanks for explaining.
Phil Sutter
reviewerPATCH 4/4 segtree: Fix get element command with prefixes
In reply to Phil SutterCode wasn't aware of prefix elements in interval sets. With previous changes in place, they merely need to be accepted in get_set_interval_find() - value comparison and expression duplication is identical to ranges.
Extend sets/0034get_element_0 test to cover prefixes as well.
--- src/segtree.c | 1 + tests/shell/testcases/sets/0034get_element_0 | 51 +++++++++++++------- 2 files changed, 34 insertions(+), 18 deletions(-)
src/segtree.c +1 -0
@@ -702,6 +702,7 @@ static struct expr *get_set_interval_find(const struct table *table,list_for_each_entry (i, &set->init->expressions, list) {switch (i->key->etype) { +case EXPR_PREFIX :case EXPR_RANGE :range_expr_value_low (val, i);if (left &&mpz_cmp (left->key->value, val))
tests/shell/testcases/sets/0034get_element_0 +33 -18
76 lines not on this page · raw message
Signature · 1 line
2.25.1