[PATCH 0/2]: nftables: segtree fixes

[PATCH 0/2]: nftables: segtree fixes

[Patrick McHardy]

These patches fix a couple of broken cases and improve readability
in interval decomposition.

- mark datatypes where representations as prefixes is preferrable to ranges,
  like IP addresses, and use that to decide whether to use prefix or range
  expressions if both are possible

- fix a couple of bugs wrt. unclosed intervals

I'm working on some further improvements and cleanups, but these are the
minimum we should put in for the upcoming release to make the output
both understandable and correct.

Signed-off-by: Patrick McHardy <kaber@trash.net>

[PATCH 1/2] segtree: only use prefix expressions for ranges for selected datatypes

[Patrick McHardy]

It is uncommon to represent f.i. port number ranges as prefix expressions.

Introduce a datatype DTYPE_F_PREFIX flag to indicate that the preferred
representation of a range is a prefix and use it for segtree decomposition
to decide whether to use a range or prefix expression.

The ipaddr, ip6addr, mark and realm datatypes are changed to include the
DTYPE_F_PREFIX flag.

This fixes completely unreadable output in cases where the ranges are
representable as prefixes, f.i. in case of port number:

{ 0/6 => jump chain1, 0/5 => jump chain2, 0/4 => continue}

becomes:

{ 0-1023 => jump chain1, 1024-2047 => jump chain2, 2048-4095 => continue}

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/datatype.h | 7 +++++++
 src/datatype.c     | 3 +++
 src/meta.c         | 1 +
 src/segtree.c      | 4 +++-
 4 files changed, 14 insertions(+), 1 deletion(-)

diff --git a/include/datatype.h b/include/datatype.h
index 9f8b44a..9e609cf 100644
--- a/include/datatype.h
+++ b/include/datatype.h
@@ -85,8 +85,15 @@ enum byteorder {
 
 struct expr;
 
+/**
+ * enum datatype_flags
+ *
+ * @DTYPE_F_ALLOC:		datatype is dynamically allocated
+ * @DTYPE_F_PREFIX:		preferred representation for ranges is a prefix
+ */
 enum datatype_flags {
 	DTYPE_F_ALLOC		= (1 << 0),
+	DTYPE_F_PREFIX		= (1 << 1),
 };
 
 /**
diff --git a/src/datatype.c b/src/datatype.c
index e228f53..5e4aacd 100644
--- a/src/datatype.c
+++ b/src/datatype.c
@@ -398,6 +398,7 @@ const struct datatype ipaddr_type = {
 	.basetype	= &integer_type,
 	.print		= ipaddr_type_print,
 	.parse		= ipaddr_type_parse,
+	.flags		= DTYPE_F_PREFIX,
 };
 
 static void ip6addr_type_print(const struct expr *expr)
@@ -455,6 +456,7 @@ const struct datatype ip6addr_type = {
 	.basetype	= &integer_type,
 	.print		= ip6addr_type_print,
 	.parse		= ip6addr_type_parse,
+	.flags		= DTYPE_F_PREFIX,
 };
 
 static void inet_protocol_type_print(const struct expr *expr)
@@ -680,6 +682,7 @@ const struct datatype mark_type = {
 	.basefmt	= "0x%.8Zx",
 	.print		= mark_type_print,
 	.parse		= mark_type_parse,
+	.flags		= DTYPE_F_PREFIX,
 };
 
 static void time_type_print(const struct expr *expr)
diff --git a/src/meta.c b/src/meta.c
index 098728b..0a3df39 100644
--- a/src/meta.c
+++ b/src/meta.c
@@ -61,6 +61,7 @@ static const struct datatype realm_type = {
 	.basetype	= &integer_type,
 	.print		= realm_type_print,
 	.parse		= realm_type_parse,
+	.flags		= DTYPE_F_PREFIX,
 };
 
 static void tchandle_type_print(const struct expr *expr)
diff --git a/src/segtree.c b/src/segtree.c
index 5426e24..e3bca4c 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -552,7 +552,9 @@ void interval_map_decompose(struct expr *set)
 
 		if (!mpz_cmp_ui(range, 0))
 			compound_expr_add(set, low);
-		else if (!range_is_prefix(range) || mpz_cmp_ui(p, 0)) {
+		else if ((!range_is_prefix(range) ||
+			  !(i->dtype->flags & DTYPE_F_PREFIX)) ||
+			 mpz_cmp_ui(p, 0)) {
 			struct expr *tmp;
 
 			tmp = constant_expr_alloc(&low->location, low->dtype,
-- 
1.8.4.2

[PATCH 2/2] segtree: fix decomposition of unclosed intervals

[Patrick McHardy]

If intervals are directly adjacent or extend to the right end of the dimension,
they are not closed by a EXPR_F_INTERVAL_END entry. This leads to multiple
errors when decomposing the intervals:

- the last unclosed interval is not shown at all.

- if a range is unclosed and the set is a map, the starting point of the
  next interval is set to the data, not the key, leading to nonsensical
  output.

- if a prefix is unclosed, the interval is assumed to be a prefix as well
  and the same starting point is kept. This makes sense for cases like
  192.168.0.0/24, 192.168.0.0/16, but leads to hard to understand
  results if the next interval is not representable as a prefix.

Fix this by doing two things:

- add an EXPR_F_INTERVAL_END element for each unclosed interval during
  preprocessing.

- process the final unclosed interval extending to the right end of the
  dimension, if present.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 src/segtree.c | 39 ++++++++++++++++++++++++++++++---------
 1 file changed, 30 insertions(+), 9 deletions(-)

diff --git a/src/segtree.c b/src/segtree.c
index e3bca4c..1a21c6c 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -509,10 +509,11 @@ static struct expr *expr_value(struct expr *expr)
 
 void interval_map_decompose(struct expr *set)
 {
-	struct expr *ranges[set->size];
-	struct expr *i, *next, *low = NULL;
+	struct expr *ranges[set->size * 2];
+	struct expr *i, *next, *low = NULL, *end;
 	unsigned int n, size;
 	mpz_t range, p;
+	bool interval;
 
 	mpz_init(range);
 	mpz_init(p);
@@ -520,8 +521,20 @@ void interval_map_decompose(struct expr *set)
 	size = set->size;
 	n = 0;
 
+	interval = false;
 	list_for_each_entry_safe_reverse(i, next, &set->expressions, list) {
 		compound_expr_remove(set, i);
+
+		if (i->flags & EXPR_F_INTERVAL_END)
+			interval = false;
+		else if (interval) {
+			end = expr_clone(expr_value(i));
+			end->flags |= EXPR_F_INTERVAL_END;
+			ranges[n++] = end;
+			size++;
+		} else
+			interval = true;
+
 		ranges[n++] = i;
 	}
 
@@ -569,8 +582,6 @@ void interval_map_decompose(struct expr *set)
 				tmp = mapping_expr_alloc(&tmp->location, tmp, low->right);
 
 			compound_expr_add(set, tmp);
-
-			low = expr_get(tmp->right);
 		} else {
 			struct expr *prefix;
 			unsigned int prefix_len;
@@ -578,13 +589,9 @@ void interval_map_decompose(struct expr *set)
 			prefix_len = expr_value(i)->len - mpz_scan0(range, 0);
 			prefix = prefix_expr_alloc(&low->location, expr_value(low),
 						   prefix_len);
-
-			if (low->ops->type == EXPR_MAPPING) {
+			if (low->ops->type == EXPR_MAPPING)
 				prefix = mapping_expr_alloc(&low->location, prefix,
 							    low->right);
-				/* Update mapping of "low" to the current mapping */
-				low->right = expr_get(i->right);
-			}
 
 			compound_expr_add(set, prefix);
 		}
@@ -595,4 +602,18 @@ void interval_map_decompose(struct expr *set)
 		}
 		expr_free(i);
 	}
+
+	/* Unclosed interval */
+	if (low != NULL) {
+		i = constant_expr_alloc(&low->location, low->dtype,
+					low->byteorder, expr_value(low)->len,
+					NULL);
+		mpz_init_bitmask(i->value, i->len);
+
+		i = range_expr_alloc(&low->location, expr_value(low), i);
+		if (low->ops->type == EXPR_MAPPING)
+			i = mapping_expr_alloc(&i->location, i, low->right);
+
+		compound_expr_add(set, i);
+	}
 }
-- 
1.8.4.2