Skip to contentSkip to conversation

Two bugfixes around prefixes in sets

PATCH In review Phil Sutter 2 participants 12 messages Apr 30, 2020 – May 4, 2020 netfilter

lore
Share & tools
lore

Phil Sutter

author reviewer
#0 lore raw

cover 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
author reviewer
#1 lore raw

PATCH 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).

Fixes bb0e6d8a2851b ("segtree: incorrect handling of comments and timeouts with mapping")
---
 src/segtree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
src/segtree.c +1 -1
index a9d6ecc89d7c1..002ee41a16db0 100644
@@ -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
author reviewer
#2 lore raw

PATCH 2/4 segtree: Use expr_clone in get_set_interval_*()

In reply to Phil Sutter

Both 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
index 002ee41a16db0..f81a66e185990 100644
@@ -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
author reviewer
#3 lore raw

PATCH 3/4 segtree: Merge get_set_interval_find() and get_set_interval_end()

In reply to 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 for get_set_interval_end().

---
 src/segtree.c | 63 +++++++++++++--------------------------------------
 1 file changed, 16 insertions(+), 47 deletions(-)
src/segtree.c +16 -47
index f81a66e185990..6aa6f97a4ebfe 100644
@@ -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
#4 lore raw

Re: [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 for get_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.

#5 lore raw

Re: [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 for get_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.

author reviewer
#6 lore raw

Re: [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 for get_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

author reviewer
#7 lore raw

Re: [nft PATCH 3/4] segtree: Merge get_set_interval_find() and get_set_interval_end()

In reply to 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 for get_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

#8 lore raw

Re: [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 for get_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 to get_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?

author reviewer
#9 lore raw

Re: [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 for get_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 to get_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

#10 lore raw

Re: [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 for get_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 to get_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.

author reviewer
#11 lore raw

PATCH 4/4 segtree: Fix get element command with prefixes

In reply to Phil Sutter

Code 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
index 6aa6f97a4ebfe..2b5831f2d64b2 100644
@@ -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