[PATCH 0/4] nftables: bitmask and prefix fixes

[PATCH 0/4] nftables: bitmask and prefix fixes

[Patrick McHardy]

These patches fix a problem with bitmask types outside of a flag comparison
noticed by Florian, as well as a couple of bugs in related areas:

- always use FLAGCMP op if RHS of a relational expression has basetype bitmask
- add parens in output of binops when necessary
- fix netlink prefix expression handling

Unless there are objections, I'll push them shortly.


Patrick McHardy (4):
      evaluate: use flagcmp for single RHS bitmask expression
      binop: take care of operator precedence when printing binop arguments
      netlink_delinarize: convert *all* bitmask values into individual bit values
      netlink: fix prefix expression handling

 include/expression.h      |   8 ++++
 src/evaluate.c            |   6 ++-
 src/expression.c          |  88 +++++++++++++++++++++++++++++++++++++--
 src/netlink.c             |  27 ------------
 src/netlink_delinearize.c | 104 ++++++++++++++++++++++++++--------------------
 src/netlink_linearize.c   |  11 ++++-
 6 files changed, 165 insertions(+), 79 deletions(-)

[PATCH 1/4] evaluate: use flagcmp for single RHS bitmask expression

[Patrick McHardy]

Always use flagcmp for RHS bitmask expressions, independant of whether
only one or an entire list of bitmask expression is specified.

This makes sure that f.i. "tcp flags ack" will match any combinations
of ACK instead of ACK and only ACK.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 src/evaluate.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/src/evaluate.c b/src/evaluate.c
index 8e51a63..f10d0d9 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -885,7 +885,11 @@ static int expr_evaluate_relational(struct eval_ctx *ctx, struct expr **expr)
 			rel->op = OP_FLAGCMP;
 			break;
 		default:
-			rel->op = OP_EQ;
+			if (right->dtype->basetype != NULL &&
+			    right->dtype->basetype->type == TYPE_BITMASK)
+				rel->op = OP_FLAGCMP;
+			else
+				rel->op = OP_EQ;
 			break;
 		}
 	}
-- 
1.8.5.3

[PATCH 2/4] binop: take care of operator precedence when printing binop arguments

[Patrick McHardy]

When the argument of a binop is a binop itself, we may need to add parens
if the precedence of the argument is lower then the binop.

Before:

tcp flags & syn | ack == syn | ack
tcp flags & syn | ack != syn | ack

After:

tcp flags & (syn | ack) == syn | ack
tcp flags & (syn | ack) != syn | ack

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/expression.h |  2 ++
 src/expression.c     | 30 ++++++++++++++++++++++++++++--
 2 files changed, 30 insertions(+), 2 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index 0633102..5128a5b 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -80,7 +80,9 @@ enum ops {
 	OP_FLAGCMP,
 	/* Set lookup */
 	OP_LOOKUP,
+	__OP_MAX
 };
+#define OP_MAX		(__OP_MAX - 1)
 
 extern const char *expr_op_symbols[];
 
diff --git a/src/expression.c b/src/expression.c
index c856622..6cc79b2 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -404,16 +404,42 @@ struct expr *unary_expr_alloc(const struct location *loc,
 	return expr;
 }
 
+static uint8_t expr_binop_precedence[OP_MAX + 1] = {
+	[OP_LSHIFT]	= 1,
+	[OP_RSHIFT]	= 1,
+	[OP_AND]	= 2,
+	[OP_XOR]	= 3,
+	[OP_OR]		= 4,
+};
+
+static void binop_arg_print(const struct expr *op, const struct expr *arg)
+{
+	bool prec = false;
+
+	if (arg->ops->type == EXPR_BINOP &&
+	    expr_binop_precedence[op->op] != 0 &&
+	    expr_binop_precedence[op->op] < expr_binop_precedence[arg->op])
+		prec = 1;
+
+	if (prec)
+		printf("(");
+	expr_print(arg);
+	if (prec)
+		printf(")");
+}
+
 static void binop_expr_print(const struct expr *expr)
 {
-	expr_print(expr->left);
+	binop_arg_print(expr, expr->left);
+
 	if (expr_op_symbols[expr->op] &&
 	    (expr->op != OP_EQ ||
 	     expr->left->ops->type == EXPR_BINOP))
 		printf(" %s ", expr_op_symbols[expr->op]);
 	else
 		printf(" ");
-	expr_print(expr->right);
+
+	binop_arg_print(expr, expr->right);
 }
 
 static void binop_expr_clone(struct expr *new, const struct expr *expr)
-- 
1.8.5.3

[PATCH 3/4] netlink_delinarize: convert *all* bitmask values into individual bit values

[Patrick McHardy]

We're currently only converting bitmask types as direct argument to a
relational expression in the form of a flagcmp (expr & mask neq 0) back
into a list of bit values. This means expressions like:

tcp flags & (syn | ack) == syn | ack

won't be shown symbolically. Convert *all* bitmask values back to a sequence
of inclusive or expressions of the individual bits. In case of a flagcmp,
this sequence is further converted to a list (tcp flags syn,ack).

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/expression.h      |  6 +++++
 src/expression.c          | 58 +++++++++++++++++++++++++++++++++++++++++++++--
 src/netlink_delinearize.c | 54 +++++++++++++++++++++++++++++--------------
 3 files changed, 99 insertions(+), 19 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index 5128a5b..ac6a4f4 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -316,6 +316,12 @@ extern struct expr *constant_expr_join(const struct expr *e1,
 				       const struct expr *e2);
 extern struct expr *constant_expr_splice(struct expr *expr, unsigned int len);
 
+extern struct expr *flag_expr_alloc(const struct location *loc,
+				    const struct datatype *dtype,
+				    enum byteorder byteorder,
+				    unsigned int len, unsigned long n);
+extern struct expr *bitmask_expr_to_binops(struct expr *expr);
+
 extern struct expr *prefix_expr_alloc(const struct location *loc,
 				      struct expr *expr,
 				      unsigned int prefix_len);
diff --git a/src/expression.c b/src/expression.c
index 6cc79b2..adaf6e7 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -13,6 +13,7 @@
 #include <stdio.h>
 #include <stdint.h>
 #include <string.h>
+#include <limits.h>
 
 #include <expression.h>
 #include <datatype.h>
@@ -302,6 +303,59 @@ struct expr *constant_expr_splice(struct expr *expr, unsigned int len)
 	return slice;
 }
 
+/*
+ * Allocate a constant expression with a single bit set at position n.
+ */
+struct expr *flag_expr_alloc(const struct location *loc,
+			     const struct datatype *dtype,
+			     enum byteorder byteorder,
+			     unsigned int len, unsigned long n)
+{
+	struct expr *expr;
+
+	assert(n < len);
+
+	expr = constant_expr_alloc(loc, dtype, byteorder, len, NULL);
+	mpz_set_ui(expr->value, 1);
+	mpz_lshift_ui(expr->value, n);
+
+	return expr;
+}
+
+/*
+ * Convert an expression of basetype TYPE_BITMASK into a series of inclusive
+ * OR binop expressions of the individual flag values.
+ */
+struct expr *bitmask_expr_to_binops(struct expr *expr)
+{
+	struct expr *binop, *flag;
+	unsigned long n;
+
+	assert(expr->ops->type == EXPR_VALUE);
+	assert(expr->dtype->basetype->type == TYPE_BITMASK);
+
+	n = mpz_popcount(expr->value);
+	if (n == 0 || n == 1)
+		return expr;
+
+	binop = NULL;
+	n = 0;
+	while ((n = mpz_scan1(expr->value, n)) != ULONG_MAX) {
+		flag = flag_expr_alloc(&expr->location, expr->dtype,
+				       expr->byteorder, expr->len, n);
+		if (binop != NULL)
+			binop = binop_expr_alloc(&expr->location,
+						 OP_OR, binop, flag);
+		else
+			binop = flag;
+
+		n++;
+	}
+
+	expr_free(expr);
+	return binop;
+}
+
 static void prefix_expr_print(const struct expr *expr)
 {
 	expr_print(expr->prefix);
@@ -467,8 +521,8 @@ struct expr *binop_expr_alloc(const struct location *loc, enum ops op,
 {
 	struct expr *expr;
 
-	expr = expr_alloc(loc, &binop_expr_ops, &invalid_type,
-			  BYTEORDER_INVALID, 0);
+	expr = expr_alloc(loc, &binop_expr_ops, left->dtype,
+			  left->byteorder, 0);
 	expr->left  = left;
 	expr->op    = op;
 	expr->right = right;
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 6668308..645bf63 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -692,28 +692,43 @@ next:
 	return k;
 }
 
+/* Convert a series of inclusive OR expressions into a list */
+static struct expr *binop_tree_to_list(struct expr *list, struct expr *expr)
+{
+	if (expr->ops->type == EXPR_BINOP && expr->op == OP_OR) {
+		if (list == NULL)
+			list = list_expr_alloc(&expr->location);
+		list = binop_tree_to_list(list, expr->left);
+		list = binop_tree_to_list(list, expr->right);
+	} else {
+		if (list == NULL)
+			return expr_get(expr);
+		compound_expr_add(list, expr_get(expr));
+	}
+
+	return list;
+}
+
 static void relational_binop_postprocess(struct expr *expr)
 {
-	struct expr *binop = expr->left, *value = expr->right, *i;
-	unsigned long n;
+	struct expr *binop = expr->left, *value = expr->right;
 
 	if (binop->op == OP_AND && expr->op == OP_NEQ &&
-	    expr->right->dtype->basetype->type == TYPE_BITMASK) {
+	    value->dtype->basetype->type == TYPE_BITMASK &&
+	    !mpz_cmp_ui(value->value, 0)) {
+		/* Flag comparison: data & flags != 0
+		 *
+		 * Split the flags into a list of flag values and convert the
+		 * op to OP_FLAGCMP.
+		 */
 		expr_free(expr->right);
-		expr->right = list_expr_alloc(&binop->left->location);
-		n = 0;
-		while ((n = mpz_scan1(binop->right->value, n)) != ULONG_MAX) {
-			i = constant_expr_alloc(&binop->right->location,
-						binop->left->dtype,
-						binop->right->byteorder,
-						binop->right->len, NULL);
-			mpz_set_ui(i->value, 1);
-			mpz_lshift_ui(i->value, n);
-			compound_expr_add(expr->right, i);
-			n++;
-		}
-		expr->left = binop->left;
-		expr->op = OP_FLAGCMP;
+		expr_free(value);
+
+		expr->left  = expr_get(binop->left);
+		expr->right = binop_tree_to_list(NULL, binop->right);
+		expr->op    = OP_FLAGCMP;
+
+		expr_free(binop);
 	} else if ((binop->left->dtype->type == TYPE_IPADDR ||
 		    binop->left->dtype->type == TYPE_IP6ADDR) &&
 		    binop->op == OP_AND) {
@@ -811,6 +826,11 @@ static void expr_postprocess(struct rule_pp_ctx *ctx,
 			mpz_clear(tmp);
 			expr->len = len;
 		}
+
+		if (expr->dtype->basetype != NULL &&
+		    expr->dtype->basetype->type == TYPE_BITMASK)
+			*exprp = bitmask_expr_to_binops(expr);
+
 		break;
 	case EXPR_RANGE:
 		expr_postprocess(ctx, stmt, &expr->left);
-- 
1.8.5.3

[PATCH 4/4] netlink: fix prefix expression handling

[Patrick McHardy]

The prefix expression handling is full of bugs:

- netlink_gen_data() is used to construct the prefix mask from the full
  prefix expression. This is both conceptually wrong, the prefix expression
  is *not* data, and buggy, it only assumes network masks and thus only
  handles big endian types.

- Prefix expression reconstruction doesn't check whether the mask is a
  valid prefix and reconstructs crap otherwise. It doesn't reconstruct
  prefixes for anything but network addresses. On top of that its
  needlessly complicated, using the mpz values directly its a simple
  matter of finding the sequence of 1's that extend up to the full width.

- Unnecessary cloning of expressions where a simple refcount increase would
  suffice.

Rewrite that code properly.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 src/netlink.c             | 27 ------------------------
 src/netlink_delinearize.c | 52 +++++++++++++++++++++--------------------------
 src/netlink_linearize.c   | 11 ++++++++--
 3 files changed, 32 insertions(+), 58 deletions(-)

diff --git a/src/netlink.c b/src/netlink.c
index 6e797dc..07af1cb 100644
--- a/src/netlink.c
+++ b/src/netlink.c
@@ -252,31 +252,6 @@ static void netlink_gen_verdict(const struct expr *expr,
 	}
 }
 
-static void netlink_gen_prefix(const struct expr *expr,
-			       struct nft_data_linearize *data)
-{
-	uint32_t idx;
-	int32_t i, cidr;
-	uint32_t mask;
-
-	assert(expr->ops->type == EXPR_PREFIX);
-
-	data->len = div_round_up(expr->prefix->len, BITS_PER_BYTE);
-	cidr = expr->prefix_len;
-
-	for (i = 0; (uint32_t)i / BITS_PER_BYTE < data->len; i += 32) {
-		if (cidr - i >= 32)
-			mask = 0xffffffff;
-		else if (cidr - i > 0)
-			mask = (1 << (cidr - i)) - 1;
-		else
-			mask = 0;
-
-		idx = i / 32;
-		data->value[idx] = mask;
-	}
-}
-
 void netlink_gen_data(const struct expr *expr, struct nft_data_linearize *data)
 {
 	switch (expr->ops->type) {
@@ -286,8 +261,6 @@ void netlink_gen_data(const struct expr *expr, struct nft_data_linearize *data)
 		return netlink_gen_concat_data(expr, data);
 	case EXPR_VERDICT:
 		return netlink_gen_verdict(expr, data);
-	case EXPR_PREFIX:
-		return netlink_gen_prefix(expr, data);
 	default:
 		BUG("invalid data expression type %s\n", expr->ops->name);
 	}
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 645bf63..0e75c8a 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -663,33 +663,27 @@ static void meta_match_postprocess(struct rule_pp_ctx *ctx,
 	}
 }
 
-static int expr_value2cidr(struct expr *expr)
+/* Convert a bitmask to a prefix length */
+static unsigned int expr_mask_to_prefix(struct expr *expr)
 {
-	int i, j, k = 0;
-	uint32_t data[4], bits;
-	uint32_t len = div_round_up(expr->len, BITS_PER_BYTE) / sizeof(uint32_t);
+	unsigned long n;
 
-	assert(expr->ops->type == EXPR_VALUE);
-
-	mpz_export_data(data, expr->value, expr->byteorder, len);
-
-	for (i = len - 1; i >= 0; i--) {
-		j = 32;
-		bits = UINT32_MAX >> 1;
-
-		if (data[i] == UINT32_MAX)
-			goto next;
+	n = mpz_scan1(expr->value, 0);
+	return mpz_scan0(expr->value, n + 1) - n;
+}
 
-		while (--j >= 0) {
-			if (data[i] == bits)
-				break;
+/* Return true if a bitmask can be expressed as a prefix length */
+static bool expr_mask_is_prefix(const struct expr *expr)
+{
+	unsigned long n1, n2;
 
-			bits >>=1;
-		}
-next:
-		k += j;
-	}
-	return k;
+	n1 = mpz_scan1(expr->value, 0);
+	if (n1 == ULONG_MAX)
+		return false;
+	n2 = mpz_scan0(expr->value, n1 + 1);
+	if (n2 < expr->len || n2 == ULONG_MAX)
+		return false;
+	return true;
 }
 
 /* Convert a series of inclusive OR expressions into a list */
@@ -729,13 +723,13 @@ static void relational_binop_postprocess(struct expr *expr)
 		expr->op    = OP_FLAGCMP;
 
 		expr_free(binop);
-	} else if ((binop->left->dtype->type == TYPE_IPADDR ||
-		    binop->left->dtype->type == TYPE_IP6ADDR) &&
-		    binop->op == OP_AND) {
-		expr->left = expr_clone(binop->left);
+	} else if (binop->left->dtype->flags & DTYPE_F_PREFIX &&
+		   binop->op == OP_AND &&
+		   expr_mask_is_prefix(binop->right)) {
+		expr->left = expr_get(binop->left);
 		expr->right = prefix_expr_alloc(&expr->location,
-						expr_clone(value),
-						expr_value2cidr(binop->right));
+						expr_get(value),
+						expr_mask_to_prefix(binop->right));
 		expr_free(value);
 		expr_free(binop);
 	}
diff --git a/src/netlink_linearize.c b/src/netlink_linearize.c
index e5fb536..9d59374 100644
--- a/src/netlink_linearize.c
+++ b/src/netlink_linearize.c
@@ -193,9 +193,14 @@ static void netlink_gen_cmp(struct netlink_linearize_ctx *ctx,
 	netlink_gen_expr(ctx, expr->left, sreg);
 
 	if (expr->right->ops->type == EXPR_PREFIX) {
-		right = expr->right->prefix;
+		mpz_t mask;
+
+		mpz_init(mask);
+		mpz_prefixmask(mask, expr->right->len, expr->right->prefix_len);
+		netlink_gen_raw_data(mask, expr->right->byteorder,
+				     expr->right->len / BITS_PER_BYTE, &nld);
+		mpz_clear(mask);
 
-		netlink_gen_data(expr->right, &nld);
 		zero.len = nld.len;
 
 		nle = alloc_nft_expr("bitwise");
@@ -205,6 +210,8 @@ static void netlink_gen_cmp(struct netlink_linearize_ctx *ctx,
 		nft_rule_expr_set(nle, NFT_EXPR_BITWISE_MASK, &nld.value, nld.len);
 		nft_rule_expr_set(nle, NFT_EXPR_BITWISE_XOR, &zero.value, zero.len);
 		nft_rule_add_expr(ctx->nlr, nle);
+
+		right = expr->right->prefix;
 	} else {
 		right = expr->right;
 	}
-- 
1.8.5.3