[nft PATCH 0/4] Two bugfixes around prefixes in sets

[nft PATCH 0/4] Two bugfixes around prefixes in sets

[Phil Sutter]

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(-)

-- 
2.25.1

[nft PATCH 1/4] segtree: Fix missing expires value in prefixes

[Phil Sutter]

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")
Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 src/segtree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/segtree.c b/src/segtree.c
index a9d6ecc89d7c1..002ee41a16db0 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -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;
 			}
 
-- 
2.25.1

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

[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.

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 src/segtree.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/src/segtree.c b/src/segtree.c
index 002ee41a16db0..f81a66e185990 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -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;
-- 
2.25.1

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

[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().

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 src/segtree.c | 63 +++++++++++++--------------------------------------
 1 file changed, 16 insertions(+), 47 deletions(-)

diff --git a/src/segtree.c b/src/segtree.c
index f81a66e185990..6aa6f97a4ebfe 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -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
-- 
2.25.1

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

[Pablo Neira Ayuso]

On Thu, Apr 30, 2020 at 05:14:07PM +0200, Phil Sutter wrote:
> 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.

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

[Pablo Neira Ayuso]

On Thu, Apr 30, 2020 at 05:37:29PM +0200, Pablo Neira Ayuso wrote:
> On Thu, Apr 30, 2020 at 05:14:07PM +0200, Phil Sutter wrote:
> > 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.

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

[Phil Sutter]

Hi Pablo,

On Thu, Apr 30, 2020 at 05:41:13PM +0200, Pablo Neira Ayuso wrote:
> On Thu, Apr 30, 2020 at 05:37:29PM +0200, Pablo Neira Ayuso wrote:
> > On Thu, Apr 30, 2020 at 05:14:07PM +0200, Phil Sutter wrote:
> > > 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.

[...]

> 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

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

[Phil Sutter]

On Thu, Apr 30, 2020 at 05:37:29PM +0200, Pablo Neira Ayuso wrote:
> On Thu, Apr 30, 2020 at 05:14:07PM +0200, Phil Sutter wrote:
> > 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

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

[Pablo Neira Ayuso]

On Thu, Apr 30, 2020 at 05:48:42PM +0200, Phil Sutter wrote:
> On Thu, Apr 30, 2020 at 05:37:29PM +0200, Pablo Neira Ayuso wrote:
> > On Thu, Apr 30, 2020 at 05:14:07PM +0200, Phil Sutter wrote:
> > > 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.

Hm, so the approximate or exact matching is broken? Or you mean they
fail because you didn't expect the approximate matching?

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

[Phil Sutter]

On Thu, Apr 30, 2020 at 05:52:18PM +0200, Pablo Neira Ayuso wrote:
> On Thu, Apr 30, 2020 at 05:48:42PM +0200, Phil Sutter wrote:
> > On Thu, Apr 30, 2020 at 05:37:29PM +0200, Pablo Neira Ayuso wrote:
> > > On Thu, Apr 30, 2020 at 05:14:07PM +0200, Phil Sutter wrote:
> > > > 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.
> 
> 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

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

[Pablo Neira Ayuso]

On Thu, Apr 30, 2020 at 06:01:20PM +0200, Phil Sutter wrote:
> On Thu, Apr 30, 2020 at 05:52:18PM +0200, Pablo Neira Ayuso wrote:
> > On Thu, Apr 30, 2020 at 05:48:42PM +0200, Phil Sutter wrote:
> > > On Thu, Apr 30, 2020 at 05:37:29PM +0200, Pablo Neira Ayuso wrote:
> > > > On Thu, Apr 30, 2020 at 05:14:07PM +0200, Phil Sutter wrote:
> > > > > 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.
> > 
> > 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.

This looks good indeed. Please, push this out.

Thanks for explaining.

[nft PATCH 4/4] segtree: Fix get element command with prefixes

[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.

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 src/segtree.c                                |  1 +
 tests/shell/testcases/sets/0034get_element_0 | 51 +++++++++++++-------
 2 files changed, 34 insertions(+), 18 deletions(-)

diff --git a/src/segtree.c b/src/segtree.c
index 6aa6f97a4ebfe..2b5831f2d64b2 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -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))
diff --git a/tests/shell/testcases/sets/0034get_element_0 b/tests/shell/testcases/sets/0034get_element_0
index e23dbda09b45c..f174bc37273ca 100755
--- a/tests/shell/testcases/sets/0034get_element_0
+++ b/tests/shell/testcases/sets/0034get_element_0
@@ -2,43 +2,58 @@
 
 RC=0
 
-check() { # (elems, expected)
-	out=$($NFT get element ip t s "{ $1 }")
+check() { # (set, elems, expected)
+	out=$($NFT get element ip t $1 "{ $2 }")
 	out=$(grep "elements =" <<< "$out")
 	out="${out#* \{ }"
 	out="${out% \}}"
-	[[ "$out" == "$2" ]] && return
-	echo "ERROR: asked for '$1', expecting '$2' but got '$out'"
+	[[ "$out" == "$3" ]] && return
+	echo "ERROR: asked for '$2' in set $1, expecting '$3' but got '$out'"
 	((RC++))
 }
 
 RULESET="add table ip t
 add set ip t s { type inet_service; flags interval; }
 add element ip t s { 10, 20-30, 40, 50-60 }
+add set ip t ips { type ipv4_addr; flags interval; }
+add element ip t ips { 10.0.0.1, 10.0.0.5-10.0.0.8 }
+add element ip t ips { 10.0.0.128/25, 10.0.1.0/24, 10.0.2.3-10.0.2.12 }
 "
 
 $NFT -f - <<< "$RULESET"
 
 # simple cases, (non-)existing values and ranges
-check 10 10
-check 11 ""
-check 20-30 20-30
-check 15-18 ""
+check s 10 10
+check s 11 ""
+check s 20-30 20-30
+check s 15-18 ""
 
 # multiple single elements, ranges smaller than present
-check "10, 40" "10, 40"
-check "22-24, 26-28" "20-30, 20-30"
-check 21-29 20-30
+check s "10, 40" "10, 40"
+check s "22-24, 26-28" "20-30, 20-30"
+check s 21-29 20-30
 
 # mixed single elements and ranges
-check "10, 20" "10, 20-30"
-check "10, 22" "10, 20-30"
-check "10, 22-24" "10, 20-30"
+check s "10, 20" "10, 20-30"
+check s "10, 22" "10, 20-30"
+check s "10, 22-24" "10, 20-30"
 
 # non-existing ranges matching elements
-check 10-40 ""
-check 10-20 ""
-check 10-25 ""
-check 25-55 ""
+check s 10-40 ""
+check s 10-20 ""
+check s 10-25 ""
+check s 25-55 ""
+
+# playing with IPs, ranges and prefixes
+check ips 10.0.0.1 10.0.0.1
+check ips 10.0.0.2 ""
+check ips 10.0.1.0/24 10.0.1.0/24
+check ips 10.0.1.2/31 10.0.1.0/24
+check ips 10.0.1.0 10.0.1.0/24
+check ips 10.0.1.3 10.0.1.0/24
+check ips 10.0.1.255 10.0.1.0/24
+check ips 10.0.2.3-10.0.2.12 10.0.2.3-10.0.2.12
+check ips 10.0.2.10 10.0.2.3-10.0.2.12
+check ips 10.0.2.12 10.0.2.3-10.0.2.12
 
 exit $RC
-- 
2.25.1