[PATCH nft 0/2] Fix listing of sets containing unclosed address prefix intervals

[PATCH nft 0/2] Fix listing of sets containing unclosed address prefix intervals

[Jeremy Sowden]

The code which decomposes unclosed intervals in sets doesn't check for
prefixes.  This means that a set containing such a prefix (e.g.,
ff00::/8 or 192.0.0.0/2) is incorrectly listed:

  # nft list table ip6 t
  table ip6 t {
    chain c {
      ip6 saddr ff00::/8 drop
      ip6 saddr fe80::/10 drop
      ip6 saddr { fe80::/10, ff00::-ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff } drop
    }
  }
  # nft list table ip t
  table ip t {
    chain c {
      ip saddr 192.0.0.0/2 drop
      ip saddr 10.0.0.0/8 drop
      ip saddr { 10.0.0.0/8, 192.0.0.0-255.255.255.255 } drop
    }
  }

This patch-set refactors `interval_map_decompose` to use the same code
to handle unclosed intervals that is used for closed ones.

Jeremy Sowden (2):
  segtree: refactor decomposition of closed intervals
  segtree: fix decomposition of unclosed intervals containing address
    prefixes

 src/segtree.c                                 | 90 +++++++++----------
 .../sets/0071unclosed_prefix_interval_0       | 23 +++++
 .../dumps/0071unclosed_prefix_interval_0.nft  | 19 ++++
 3 files changed, 85 insertions(+), 47 deletions(-)
 create mode 100755 tests/shell/testcases/sets/0071unclosed_prefix_interval_0
 create mode 100644 tests/shell/testcases/sets/dumps/0071unclosed_prefix_interval_0.nft

-- 
2.35.1

[PATCH nft 1/2] segtree: refactor decomposition of closed intervals

[Jeremy Sowden]

Move the code in `interval_map_decompose` which adds a new closed
interval to the set into a separate function.  In addition to the moving
of the code, there is one other change: `compound_expr_add` is called
once, after the main conditional, instead of being called in each
branch.

Signed-off-by: Jeremy Sowden <jeremy@azazel.net>
---
 src/segtree.c | 71 +++++++++++++++++++++++++++------------------------
 1 file changed, 38 insertions(+), 33 deletions(-)

diff --git a/src/segtree.c b/src/segtree.c
index c36497ce6253..d15c39f31f3a 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -493,12 +493,48 @@ static struct expr *interval_to_range(struct expr *low, struct expr *i, mpz_t ra
 	return __expr_to_set_elem(low, tmp);
 }
 
+static void
+add_interval(struct expr *set, struct expr *low, struct expr *i)
+{
+	struct expr *expr;
+	mpz_t range, p;
+
+	mpz_init(range);
+	mpz_init(p);
+
+	mpz_sub(range, expr_value(i)->value, expr_value(low)->value);
+	mpz_sub_ui(range, range, 1);
+
+	mpz_and(p, expr_value(low)->value, range);
+
+	if (!mpz_cmp_ui(range, 0)) {
+		if (expr_basetype(low)->type == TYPE_STRING)
+			mpz_switch_byteorder(expr_value(low)->value,
+					     expr_value(low)->len / BITS_PER_BYTE);
+		low->flags |= EXPR_F_KERNEL;
+		expr = expr_get(low);
+	} else if (range_is_prefix(range) && !mpz_cmp_ui(p, 0)) {
+
+		if (i->dtype->flags & DTYPE_F_PREFIX)
+			expr = interval_to_prefix(low, i, range);
+		else if (expr_basetype(i)->type == TYPE_STRING)
+			expr = interval_to_string(low, i, range);
+		else
+			expr = interval_to_range(low, i, range);
+	} else
+		expr = interval_to_range(low, i, range);
+
+	compound_expr_add(set, expr);
+
+	mpz_clear(range);
+	mpz_clear(p);
+}
+
 void interval_map_decompose(struct expr *set)
 {
 	struct expr *i, *next, *low = NULL, *end, *catchall = NULL, *key;
 	struct expr **elements, **ranges;
 	unsigned int n, m, size;
-	mpz_t range, p;
 	bool interval;
 
 	if (set->size == 0)
@@ -507,9 +543,6 @@ void interval_map_decompose(struct expr *set)
 	elements = xmalloc_array(set->size, sizeof(struct expr *));
 	ranges = xmalloc_array(set->size * 2, sizeof(struct expr *));
 
-	mpz_init(range);
-	mpz_init(p);
-
 	/* Sort elements */
 	n = 0;
 	list_for_each_entry_safe(i, next, &set->expressions, list) {
@@ -568,32 +601,7 @@ void interval_map_decompose(struct expr *set)
 			}
 		}
 
-		mpz_sub(range, expr_value(i)->value, expr_value(low)->value);
-		mpz_sub_ui(range, range, 1);
-
-		mpz_and(p, expr_value(low)->value, range);
-
-		if (!mpz_cmp_ui(range, 0)) {
-			if (expr_basetype(low)->type == TYPE_STRING)
-				mpz_switch_byteorder(expr_value(low)->value, expr_value(low)->len / BITS_PER_BYTE);
-			low->flags |= EXPR_F_KERNEL;
-			compound_expr_add(set, expr_get(low));
-		} else if (range_is_prefix(range) && !mpz_cmp_ui(p, 0)) {
-			struct expr *expr;
-
-			if (i->dtype->flags & DTYPE_F_PREFIX)
-				expr = interval_to_prefix(low, i, range);
-			else if (expr_basetype(i)->type == TYPE_STRING)
-				expr = interval_to_string(low, i, range);
-			else
-				expr = interval_to_range(low, i, range);
-
-			compound_expr_add(set, expr);
-		} else {
-			struct expr *expr = interval_to_range(low, i, range);
-
-			compound_expr_add(set, expr);
-		}
+		add_interval(set, low, i);
 
 		if (i->flags & EXPR_F_INTERVAL_END) {
 			expr_free(low);
@@ -633,9 +641,6 @@ out:
 	if (catchall)
 		compound_expr_add(set, catchall);
 
-	mpz_clear(range);
-	mpz_clear(p);
-
 	xfree(ranges);
 	xfree(elements);
 }
-- 
2.35.1

[PATCH nft 2/2] segtree: fix decomposition of unclosed intervals containing address prefixes

[Jeremy Sowden]

The code which decomposes unclosed intervals doesn't check for prefixes.  This
leads to incorrect output for sets which contain these.  For example,

  # nft -f - <<END
  table ip t {
    chain c {
      ip saddr 192.0.0.0/2 drop
      ip saddr 10.0.0.0/8 drop
      ip saddr { 192.0.0.0/2, 10.0.0.0/8 } drop
    }
  }
  table ip6 t {
    chain c {
      ip6 saddr ff00::/8 drop
      ip6 saddr fe80::/10 drop
      ip6 saddr { ff00::/8, fe80::/10 } drop
    }
  }
  END
  # nft list table ip6 t
  table ip6 t {
    chain c {
      ip6 saddr ff00::/8 drop
      ip6 saddr fe80::/10 drop
      ip6 saddr { fe80::/10, ff00::-ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff } drop
    }
  }
  # nft list table ip t
  table ip t {
    chain c {
      ip saddr 192.0.0.0/2 drop
      ip saddr 10.0.0.0/8 drop
      ip saddr { 10.0.0.0/8, 192.0.0.0-255.255.255.255 } drop
    }
  }

Instead of treating the final unclosed interval as a special case, reuse the
code which correctly handles closed intervals.

Add a shell test-case.

Link: https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=1018156
Fixes: 86b965bdab8d ("segtree: fix decomposition of unclosed intervals")
Signed-off-by: Jeremy Sowden <jeremy@azazel.net>

tests: shell: add case to test unclosed prefix intervals

Signed-off-by: Jeremy Sowden <jeremy@azazel.net>
---
 src/segtree.c                                 | 21 +++++------------
 .../sets/0071unclosed_prefix_interval_0       | 23 +++++++++++++++++++
 .../dumps/0071unclosed_prefix_interval_0.nft  | 19 +++++++++++++++
 3 files changed, 48 insertions(+), 15 deletions(-)
 create mode 100755 tests/shell/testcases/sets/0071unclosed_prefix_interval_0
 create mode 100644 tests/shell/testcases/sets/dumps/0071unclosed_prefix_interval_0.nft

diff --git a/src/segtree.c b/src/segtree.c
index d15c39f31f3a..ad3821376dae 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -158,6 +158,8 @@ static struct expr *expr_value(struct expr *expr)
 		return expr->left->key;
 	case EXPR_SET_ELEM:
 		return expr->key;
+	case EXPR_VALUE:
+		return expr;
 	default:
 		BUG("invalid expression type %s\n", expr_name(expr));
 	}
@@ -503,7 +505,8 @@ add_interval(struct expr *set, struct expr *low, struct expr *i)
 	mpz_init(p);
 
 	mpz_sub(range, expr_value(i)->value, expr_value(low)->value);
-	mpz_sub_ui(range, range, 1);
+	if (i->etype != EXPR_VALUE)
+		mpz_sub_ui(range, range, 1);
 
 	mpz_and(p, expr_value(low)->value, range);
 
@@ -619,24 +622,12 @@ void interval_map_decompose(struct expr *set)
 
 	if (!mpz_cmp(i->value, expr_value(low)->value)) {
 		expr_free(i);
-		i = low;
+		compound_expr_add(set, low);
 	} else {
-		i = range_expr_alloc(&low->location,
-				     expr_clone(expr_value(low)), i);
-		i = set_elem_expr_alloc(&low->location, i);
-		if (low->etype == EXPR_MAPPING) {
-			i = mapping_expr_alloc(&i->location, i,
-					       expr_clone(low->right));
-			interval_expr_copy(i->left, low->left);
-		} else {
-			interval_expr_copy(i, low);
-		}
-		i->flags |= EXPR_F_KERNEL;
-
+		add_interval(set, low, i);
 		expr_free(low);
 	}
 
-	compound_expr_add(set, i);
 out:
 	if (catchall)
 		compound_expr_add(set, catchall);
diff --git a/tests/shell/testcases/sets/0071unclosed_prefix_interval_0 b/tests/shell/testcases/sets/0071unclosed_prefix_interval_0
new file mode 100755
index 000000000000..79e3ca7da743
--- /dev/null
+++ b/tests/shell/testcases/sets/0071unclosed_prefix_interval_0
@@ -0,0 +1,23 @@
+#!/bin/bash
+
+set -e
+
+RULESET="
+table inet t {
+	set s1 {
+		type ipv4_addr
+		flags interval
+		elements = { 192.0.0.0/2, 10.0.0.0/8 }
+	}
+	set s2 {
+		type ipv6_addr
+		flags interval
+		elements = { ff00::/8, fe80::/10 }
+	}
+	chain c {
+		ip saddr @s1 accept
+		ip6 daddr @s2 accept
+	}
+}"
+
+$NFT -f - <<< "$RULESET"
diff --git a/tests/shell/testcases/sets/dumps/0071unclosed_prefix_interval_0.nft b/tests/shell/testcases/sets/dumps/0071unclosed_prefix_interval_0.nft
new file mode 100644
index 000000000000..4eed94c2c884
--- /dev/null
+++ b/tests/shell/testcases/sets/dumps/0071unclosed_prefix_interval_0.nft
@@ -0,0 +1,19 @@
+table inet t {
+	set s1 {
+		type ipv4_addr
+		flags interval
+		elements = { 10.0.0.0/8, 192.0.0.0/2 }
+	}
+
+	set s2 {
+		type ipv6_addr
+		flags interval
+		elements = { fe80::/10,
+			     ff00::/8 }
+	}
+
+	chain c {
+		ip saddr @s1 accept
+		ip6 daddr @s2 accept
+	}
+}
-- 
2.35.1

Re: [PATCH nft 0/2] Fix listing of sets containing unclosed address prefix intervals

[Jeremy Sowden]

[-- Attachment #1: Type: text/plain, Size: 2283 bytes --]

On 2022-09-18, at 18:22:10 +0100, Jeremy Sowden wrote:
> The code which decomposes unclosed intervals in sets doesn't check for
> prefixes.  This means that a set containing such a prefix (e.g.,
> ff00::/8 or 192.0.0.0/2) is incorrectly listed:

The original Debian bug-report only covers the IPv6 case:

>   # nft list table ip6 t
>   table ip6 t {
>     chain c {
>       ip6 saddr ff00::/8 drop
>       ip6 saddr fe80::/10 drop
>       ip6 saddr { fe80::/10, ff00::-ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff } drop
>     }
>   }

To the reporter that range looked like a garbled address with a negative
hex number embedded in it, and when I read the report it looked like
that to me too.  Inevitably, it was only after I sent this patch-set
that I finally parsed it correctly as the range ff00:: to
ffff:ffff:...:ffff:ffff, largely because of the IPv4 case:

>   # nft list table ip t
>   table ip t {
>     chain c {
>       ip saddr 192.0.0.0/2 drop
>       ip saddr 10.0.0.0/8 drop
>       ip saddr { 10.0.0.0/8, 192.0.0.0-255.255.255.255 } drop
>     }
>   }

which, to me at least, is easier to read.

The reason that I bring this up is that I should probably have phrased
the commit messages differently and avoided the use of "correct" and
"incorrect" if I hadn't misparsed the IPv6 range, like the original
reporter, since the ranges currently output are unexpected (and arguably
confusing), rather than wrong.  I'm happy to reword the commits if you
would like.

J.

> This patch-set refactors `interval_map_decompose` to use the same code
> to handle unclosed intervals that is used for closed ones.
> 
> Jeremy Sowden (2):
>   segtree: refactor decomposition of closed intervals
>   segtree: fix decomposition of unclosed intervals containing address
>     prefixes
> 
>  src/segtree.c                                 | 90 +++++++++----------
>  .../sets/0071unclosed_prefix_interval_0       | 23 +++++
>  .../dumps/0071unclosed_prefix_interval_0.nft  | 19 ++++
>  3 files changed, 85 insertions(+), 47 deletions(-)
>  create mode 100755 tests/shell/testcases/sets/0071unclosed_prefix_interval_0
>  create mode 100644 tests/shell/testcases/sets/dumps/0071unclosed_prefix_interval_0.nft
> 
> -- 
> 2.35.1
> 
> 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH nft 2/2] segtree: fix decomposition of unclosed intervals containing address prefixes

[Florian Westphal]

Jeremy Sowden <jeremy@azazel.net> wrote:
> @@ -619,24 +622,12 @@ void interval_map_decompose(struct expr *set)
>  
>  	if (!mpz_cmp(i->value, expr_value(low)->value)) {
>  		expr_free(i);
> -		i = low;
> +		compound_expr_add(set, low);
>  	} else {
> -		i = range_expr_alloc(&low->location,
> -				     expr_clone(expr_value(low)), i);
> -		i = set_elem_expr_alloc(&low->location, i);
> -		if (low->etype == EXPR_MAPPING) {
> -			i = mapping_expr_alloc(&i->location, i,
> -					       expr_clone(low->right));
> -			interval_expr_copy(i->left, low->left);
> -		} else {
> -			interval_expr_copy(i, low);
> -		}
> -		i->flags |= EXPR_F_KERNEL;
> -
> +		add_interval(set, low, i);
>  		expr_free(low);
>  	}
>  
> -	compound_expr_add(set, i);

This results in a memory leak:

__interceptor_malloc libsanitizer/asan/asan_malloc_linux.cpp:145
xmalloc src/utils.c:36
xzalloc src/utils.c:75
expr_alloc src/expression.c:46
constant_expr_alloc src/expression.c:420
interval_map_decompose src/segtree.c:619

Before, 'i' was assigned to the compund expr, but thats no longer the
case.

Does this look good to you?  If so, I will sqash this before applying:

diff --git a/src/segtree.c b/src/segtree.c
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -621,13 +621,14 @@ void interval_map_decompose(struct expr *set)
 	mpz_bitmask(i->value, i->len);
 
 	if (!mpz_cmp(i->value, expr_value(low)->value)) {
-		expr_free(i);
 		compound_expr_add(set, low);
 	} else {
 		add_interval(set, low, i);
 		expr_free(low);
 	}
 
+	expr_free(i);
+
 out:
 	if (catchall)
 		compound_expr_add(set, catchall);

Re: [PATCH nft 2/2] segtree: fix decomposition of unclosed intervals containing address prefixes

[Jeremy Sowden]

[-- Attachment #1: Type: text/plain, Size: 1861 bytes --]

On 2022-09-21, at 13:48:27 +0200, Florian Westphal wrote:
> Jeremy Sowden <jeremy@azazel.net> wrote:
> > @@ -619,24 +622,12 @@ void interval_map_decompose(struct expr *set)
> >
> >  	if (!mpz_cmp(i->value, expr_value(low)->value)) {
> >  		expr_free(i);
> > -		i = low;
> > +		compound_expr_add(set, low);
> >  	} else {
> > -		i = range_expr_alloc(&low->location,
> > -				     expr_clone(expr_value(low)), i);
> > -		i = set_elem_expr_alloc(&low->location, i);
> > -		if (low->etype == EXPR_MAPPING) {
> > -			i = mapping_expr_alloc(&i->location, i,
> > -					       expr_clone(low->right));
> > -			interval_expr_copy(i->left, low->left);
> > -		} else {
> > -			interval_expr_copy(i, low);
> > -		}
> > -		i->flags |= EXPR_F_KERNEL;
> > -
> > +		add_interval(set, low, i);
> >  		expr_free(low);
> >  	}
> >
> > -	compound_expr_add(set, i);
>
> This results in a memory leak:
>
> __interceptor_malloc libsanitizer/asan/asan_malloc_linux.cpp:145
> xmalloc src/utils.c:36
> xzalloc src/utils.c:75
> expr_alloc src/expression.c:46
> constant_expr_alloc src/expression.c:420
> interval_map_decompose src/segtree.c:619

I did try running the new shell test under valgrind: lots of noise, not
a lot of signal. :)

> Before, 'i' was assigned to the compund expr, but thats no longer the
> case.

> Does this look good to you?

Yes, LTGM.

> If so, I will sqash this before applying:
>
> diff --git a/src/segtree.c b/src/segtree.c
> --- a/src/segtree.c
> +++ b/src/segtree.c
> @@ -621,13 +621,14 @@ void interval_map_decompose(struct expr *set)
>  	mpz_bitmask(i->value, i->len);
>
>  	if (!mpz_cmp(i->value, expr_value(low)->value)) {
> -		expr_free(i);
>  		compound_expr_add(set, low);
>  	} else {
>  		add_interval(set, low, i);
>  		expr_free(low);
>  	}
>
> +	expr_free(i);
> +
>  out:
>  	if (catchall)
>  		compound_expr_add(set, catchall);
>

Thanks,

J.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH nft 2/2] segtree: fix decomposition of unclosed intervals containing address prefixes

[Florian Westphal]

Jeremy Sowden <jeremy@azazel.net> wrote:
> > __interceptor_malloc libsanitizer/asan/asan_malloc_linux.cpp:145
> > xmalloc src/utils.c:36
> > xzalloc src/utils.c:75
> > expr_alloc src/expression.c:46
> > constant_expr_alloc src/expression.c:420
> > interval_map_decompose src/segtree.c:619
> 
> I did try running the new shell test under valgrind: lots of noise, not
> a lot of signal. :)

Yes.  You can use -fsanitize=leak as alternative, that has a much better
signal/noise ratio.

> > Before, 'i' was assigned to the compund expr, but thats no longer the
> > case.
> 
> > Does this look good to you?
> 
> Yes, LTGM.

Applied, thanks!