[PATCH nft 1/4] optimize: incorrect comparison for reject statement

[PATCH nft 1/4] optimize: incorrect comparison for reject statement

[Pablo Neira Ayuso]

Logic is reverse, this should returns false if the compared reject
expressions are not the same.

Fixes: 38d48fe57fff ("optimize: fix reject statement")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/optimize.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/optimize.c b/src/optimize.c
index 05d8084b2a47..bb849267d8d9 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -235,7 +235,7 @@ static bool __stmt_type_eq(const struct stmt *stmt_a, const struct stmt *stmt_b,
 		if (!stmt_a->reject.expr)
 			return true;
 
-		if (__expr_cmp(stmt_a->reject.expr, stmt_b->reject.expr))
+		if (!__expr_cmp(stmt_a->reject.expr, stmt_b->reject.expr))
 			return false;
 		break;
 	case STMT_NAT:
-- 
2.30.2

[PATCH nft 2/4] optimize: compact bitmask matching in set/map

[Pablo Neira Ayuso]

Check if right hand side of relational is a bitmask, ie.

     relational
       /   \
    ...     or
           /  \
       value   or
              /  \
         value    value

then, if left hand side is a binop expression, compare left and right
hand sides (not only left hand of this binop expression) to check for
redundant matches in consecutive rules, ie.

        relational
          /   \
       and     ...
      /   \
 payload  value

before this patch, only payload in the binop expression was compared.

This allows to compact several rules matching tcp flags in a set/map, eg.

 # nft -c -o -f ruleset.nft
 Merging:
 ruleset.nft:7:17-76:                 tcp flags & (fin | syn | rst | ack | urg) == fin | ack | urg
 ruleset.nft:8:17-70:                 tcp flags & (fin | syn | rst | ack | urg) == fin | ack
 ruleset.nft:9:17-64:                 tcp flags & (fin | syn | rst | ack | urg) == fin
 ruleset.nft:10:17-70:                 tcp flags & (fin | syn | rst | ack | urg) == syn | ack
 ruleset.nft:11:17-64:                 tcp flags & (fin | syn | rst | ack | urg) == syn
 ruleset.nft:12:17-70:                 tcp flags & (fin | syn | rst | ack | urg) == rst | ack
 ruleset.nft:13:17-64:                 tcp flags & (fin | syn | rst | ack | urg) == rst
 ruleset.nft:14:17-70:                 tcp flags & (fin | syn | rst | ack | urg) == ack | urg
 ruleset.nft:15:17-64:                 tcp flags & (fin | syn | rst | ack | urg) == ack
 into:
        tcp flags & (fin | syn | rst | ack | urg) == { fin | ack | urg, fin | ack, fin, syn | ack, syn, rst | ack, rst, ack | urg, ack }
 Merging:
 ruleset.nft:17:17-61:                 tcp flags & (ack | urg) == ack jump ack_chain
 ruleset.bft:18:17-61:                 tcp flags & (ack | urg) == urg jump urg_chain
 into:
        tcp flags & (ack | urg) vmap { ack : jump ack_chain, urg : jump urg_chain }

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/optimize.c                                | 35 ++++++++++++++++++-
 tests/shell/testcases/optimizations/bitmask   | 26 ++++++++++++++
 .../testcases/optimizations/dumps/bitmask.nft | 14 ++++++++
 3 files changed, 74 insertions(+), 1 deletion(-)
 create mode 100755 tests/shell/testcases/optimizations/bitmask
 create mode 100644 tests/shell/testcases/optimizations/dumps/bitmask.nft

diff --git a/src/optimize.c b/src/optimize.c
index bb849267d8d9..44010f2bb377 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -127,7 +127,17 @@ static bool __expr_cmp(const struct expr *expr_a, const struct expr *expr_b)
 			return false;
 		break;
 	case EXPR_BINOP:
-		return __expr_cmp(expr_a->left, expr_b->left);
+		if (!__expr_cmp(expr_a->left, expr_b->left))
+			return false;
+
+		return __expr_cmp(expr_a->right, expr_b->right);
+	case EXPR_SYMBOL:
+		if (expr_a->symtype != expr_b->symtype)
+			return false;
+		if (expr_a->symtype != SYMBOL_VALUE)
+			return false;
+
+		return !strcmp(expr_a->identifier, expr_b->identifier);
 	default:
 		return false;
 	}
@@ -135,6 +145,25 @@ static bool __expr_cmp(const struct expr *expr_a, const struct expr *expr_b)
 	return true;
 }
 
+static bool is_bitmask(const struct expr *expr)
+{
+	switch (expr->etype) {
+	case EXPR_BINOP:
+		if (expr->op == OP_OR &&
+		    !is_bitmask(expr->left))
+			return false;
+
+		return is_bitmask(expr->right);
+	case EXPR_VALUE:
+	case EXPR_SYMBOL:
+		return true;
+	default:
+		break;
+	}
+
+	return false;
+}
+
 static bool stmt_expr_supported(const struct expr *expr)
 {
 	switch (expr->right->etype) {
@@ -146,6 +175,10 @@ static bool stmt_expr_supported(const struct expr *expr)
 	case EXPR_LIST:
 	case EXPR_VALUE:
 		return true;
+	case EXPR_BINOP:
+		if (is_bitmask(expr->right))
+			return true;
+		break;
 	default:
 		break;
 	}
diff --git a/tests/shell/testcases/optimizations/bitmask b/tests/shell/testcases/optimizations/bitmask
new file mode 100755
index 000000000000..064d95604061
--- /dev/null
+++ b/tests/shell/testcases/optimizations/bitmask
@@ -0,0 +1,26 @@
+#!/bin/bash
+
+set -e
+
+RULESET='table inet t {
+	chain ack_chain {}
+	chain urg_chain {}
+
+        chain c {
+                tcp flags & (syn | rst | ack | urg) == ack | urg
+                tcp flags & (fin | syn | rst | ack | urg) == fin | ack | urg
+                tcp flags & (fin | syn | rst | ack | urg) == fin | ack
+                tcp flags & (fin | syn | rst | ack | urg) == fin
+                tcp flags & (fin | syn | rst | ack | urg) == syn | ack
+                tcp flags & (fin | syn | rst | ack | urg) == syn
+                tcp flags & (fin | syn | rst | ack | urg) == rst | ack
+                tcp flags & (fin | syn | rst | ack | urg) == rst
+                tcp flags & (fin | syn | rst | ack | urg) == ack | urg
+                tcp flags & (fin | syn | rst | ack | urg) == ack
+                tcp flags & (rst | ack | urg) == rst | ack
+                tcp flags & (ack | urg) == ack jump ack_chain
+                tcp flags & (ack | urg) == urg jump urg_chain
+        }
+}'
+
+$NFT -o -f - <<< $RULESET
diff --git a/tests/shell/testcases/optimizations/dumps/bitmask.nft b/tests/shell/testcases/optimizations/dumps/bitmask.nft
new file mode 100644
index 000000000000..758b32a374e2
--- /dev/null
+++ b/tests/shell/testcases/optimizations/dumps/bitmask.nft
@@ -0,0 +1,14 @@
+table inet t {
+	chain ack_chain {
+	}
+
+	chain urg_chain {
+	}
+
+	chain c {
+		tcp flags & (syn | rst | ack | urg) == ack | urg
+		tcp flags & (fin | syn | rst | ack | urg) == { fin | ack | urg, fin | ack, fin, syn | ack, syn, rst | ack, rst, ack | urg, ack }
+		tcp flags & (rst | ack | urg) == rst | ack
+		tcp flags & (ack | urg) vmap { ack : jump ack_chain, urg : jump urg_chain }
+	}
+}
-- 
2.30.2

[PATCH nft 3/4] src: transform flag match expression to binop expression from parser

[Pablo Neira Ayuso]

Transform flagcmp expression to a relational with binop on the left hand
side, ie.

         relational
          /      \
       binop    value
       /   \
 payload  mask

Add list_expr_to_binop() to make this transformation.

Goal is two-fold:

- Allow -o/--optimize to pick up on this representation.
- Remove the flagcmp expression in a follow up patch.

This prepare for the removal of the flagcmp expression added by:

  c3d57114f119 ("parser_bison: add shortcut syntax for matching flags without binary operations")

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/expression.h |  1 +
 src/expression.c     | 23 +++++++++++++++++++++++
 src/parser_bison.y   | 22 ++++++++++++++++++----
 3 files changed, 42 insertions(+), 4 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index 8472748621ef..818d7a7dc74b 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -519,6 +519,7 @@ extern void list_splice_sorted(struct list_head *list, struct list_head *head);
 extern struct expr *concat_expr_alloc(const struct location *loc);
 
 extern struct expr *list_expr_alloc(const struct location *loc);
+struct expr *list_expr_to_binop(struct expr *expr);
 
 extern struct expr *set_expr_alloc(const struct location *loc,
 				   const struct set *set);
diff --git a/src/expression.c b/src/expression.c
index 156a66eb37f0..2a30d5af92a4 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -1263,6 +1263,29 @@ struct expr *list_expr_alloc(const struct location *loc)
 	return compound_expr_alloc(loc, EXPR_LIST);
 }
 
+/* list is assumed to have two items at least, otherwise extend this! */
+struct expr *list_expr_to_binop(struct expr *expr)
+{
+	struct expr *first, *last, *i;
+
+	first = list_first_entry(&expr->expressions, struct expr, list);
+	i = first;
+
+	list_for_each_entry_continue(i, &expr->expressions, list) {
+		if (first) {
+			last = binop_expr_alloc(&expr->location, OP_OR, first, i);
+			first = NULL;
+		} else {
+			last = binop_expr_alloc(&expr->location, OP_OR, i, last);
+		}
+	}
+	/* zap list expressions, they have been moved to binop expression. */
+	init_list_head(&expr->expressions);
+	expr_free(expr);
+
+	return last;
+}
+
 static const char *calculate_delim(const struct expr *expr, int *count,
 				   struct output_ctx *octx)
 {
diff --git a/src/parser_bison.y b/src/parser_bison.y
index 5760ba479fc9..4b2b51d4275c 100644
--- a/src/parser_bison.y
+++ b/src/parser_bison.y
@@ -4917,19 +4917,33 @@ relational_expr		:	expr	/* implicit */	rhs_expr
 			}
 			|	expr	/* implicit */	basic_rhs_expr	SLASH	list_rhs_expr
 			{
-				$$ = flagcmp_expr_alloc(&@$, OP_EQ, $1, $4, $2);
+				struct expr *mask = list_expr_to_binop($4);
+				struct expr *binop = binop_expr_alloc(&@$, OP_AND, $1, mask);
+
+				$$ = relational_expr_alloc(&@$, OP_IMPLICIT, binop, $2);
 			}
 			|	expr	/* implicit */	list_rhs_expr	SLASH	list_rhs_expr
 			{
-				$$ = flagcmp_expr_alloc(&@$, OP_EQ, $1, $4, $2);
+				struct expr *value = list_expr_to_binop($2);
+				struct expr *mask = list_expr_to_binop($4);
+				struct expr *binop = binop_expr_alloc(&@$, OP_AND, $1, mask);
+
+				$$ = relational_expr_alloc(&@$, OP_IMPLICIT, binop, value);
 			}
 			|	expr	relational_op	basic_rhs_expr	SLASH	list_rhs_expr
 			{
-				$$ = flagcmp_expr_alloc(&@$, $2, $1, $5, $3);
+				struct expr *mask = list_expr_to_binop($5);
+				struct expr *binop = binop_expr_alloc(&@$, OP_AND, $1, mask);
+
+				$$ = relational_expr_alloc(&@$, $2, binop, $3);
 			}
 			|	expr	relational_op	list_rhs_expr	SLASH	list_rhs_expr
 			{
-				$$ = flagcmp_expr_alloc(&@$, $2, $1, $5, $3);
+				struct expr *value = list_expr_to_binop($3);
+				struct expr *mask = list_expr_to_binop($5);
+				struct expr *binop = binop_expr_alloc(&@$, OP_AND, $1, mask);
+
+				$$ = relational_expr_alloc(&@$, $2, binop, value);
 			}
 			|	expr	relational_op	rhs_expr
 			{
-- 
2.30.2

[PATCH nft 4/4] src: remove flagcmp expression

[Pablo Neira Ayuso]

This expression is not used anymore, since:

 ("src: transform flag match expression to binop expression from parser")

remove it.

This completes the revert of c3d57114f119 ("parser_bison: add shortcut
syntax for matching flags without binary operations"), except the parser
chunk for backwards compatibility.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/expression.h | 14 +----------
 include/json.h       |  2 --
 src/evaluate.c       | 21 -----------------
 src/expression.c     | 56 --------------------------------------------
 src/json.c           | 14 -----------
 5 files changed, 1 insertion(+), 106 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index 818d7a7dc74b..8399fae88d78 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -47,7 +47,6 @@
  * @EXPR_FIB		forward information base expression
  * @EXPR_XFRM		XFRM (ipsec) expression
  * @EXPR_SET_ELEM_CATCHALL catchall element expression
- * @EXPR_FLAGCMP	flagcmp expression
  * @EXPR_RANGE_VALUE	constant range expression
  * @EXPR_RANGE_SYMBOL	unparse symbol range expression
  */
@@ -81,11 +80,10 @@ enum expr_types {
 	EXPR_FIB,
 	EXPR_XFRM,
 	EXPR_SET_ELEM_CATCHALL,
-	EXPR_FLAGCMP,
 	EXPR_RANGE_VALUE,
 	EXPR_RANGE_SYMBOL,
 
-	EXPR_MAX = EXPR_FLAGCMP
+	EXPR_MAX = EXPR_SET_ELEM_CATCHALL
 };
 
 enum ops {
@@ -402,12 +400,6 @@ struct expr {
 			uint8_t			ttl;
 			uint32_t		flags;
 		} osf;
-		struct {
-			/* EXPR_FLAGCMP */
-			struct expr		*expr;
-			struct expr		*mask;
-			struct expr		*value;
-		} flagcmp;
 	};
 };
 
@@ -544,10 +536,6 @@ extern struct expr *set_elem_expr_alloc(const struct location *loc,
 
 struct expr *set_elem_catchall_expr_alloc(const struct location *loc);
 
-struct expr *flagcmp_expr_alloc(const struct location *loc, enum ops op,
-				struct expr *expr, struct expr *mask,
-				struct expr *value);
-
 extern void range_expr_value_low(mpz_t rop, const struct expr *expr);
 extern void range_expr_value_high(mpz_t rop, const struct expr *expr);
 void range_expr_swap_values(struct expr *range);
diff --git a/include/json.h b/include/json.h
index 0670b8714519..b61eeafe8d7e 100644
--- a/include/json.h
+++ b/include/json.h
@@ -29,7 +29,6 @@ struct list_head;
 
 json_t *binop_expr_json(const struct expr *expr, struct output_ctx *octx);
 json_t *relational_expr_json(const struct expr *expr, struct output_ctx *octx);
-json_t *flagcmp_expr_json(const struct expr *expr, struct output_ctx *octx);
 json_t *range_expr_json(const struct expr *expr, struct output_ctx *octx);
 json_t *meta_expr_json(const struct expr *expr, struct output_ctx *octx);
 json_t *payload_expr_json(const struct expr *expr, struct output_ctx *octx);
@@ -137,7 +136,6 @@ static inline json_t *name##_json(arg1_t arg1, arg2_t arg2) { return NULL; }
 	JSON_PRINT_STUB(name##_stmt, const struct stmt *, struct output_ctx *)
 
 EXPR_PRINT_STUB(binop_expr)
-EXPR_PRINT_STUB(flagcmp_expr)
 EXPR_PRINT_STUB(relational_expr)
 EXPR_PRINT_STUB(range_expr)
 EXPR_PRINT_STUB(meta_expr)
diff --git a/src/evaluate.c b/src/evaluate.c
index a27961193da5..8a61dcc4a4e9 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -2977,25 +2977,6 @@ static int expr_evaluate_xfrm(struct eval_ctx *ctx, struct expr **exprp)
 	return expr_evaluate_primary(ctx, exprp);
 }
 
-static int expr_evaluate_flagcmp(struct eval_ctx *ctx, struct expr **exprp)
-{
-	struct expr *expr = *exprp, *binop, *rel;
-
-	if (expr->op != OP_EQ &&
-	    expr->op != OP_NEQ)
-		return expr_error(ctx->msgs, expr, "either == or != is allowed");
-
-	binop = binop_expr_alloc(&expr->location, OP_AND,
-				 expr_get(expr->flagcmp.expr),
-				 expr_get(expr->flagcmp.mask));
-	rel = relational_expr_alloc(&expr->location, expr->op, binop,
-				    expr_get(expr->flagcmp.value));
-	expr_free(expr);
-	*exprp = rel;
-
-	return expr_evaluate(ctx, exprp);
-}
-
 static int verdict_validate_chainlen(struct eval_ctx *ctx,
 				     struct expr *chain)
 {
@@ -3095,8 +3076,6 @@ static int expr_evaluate(struct eval_ctx *ctx, struct expr **expr)
 		return expr_evaluate_xfrm(ctx, expr);
 	case EXPR_SET_ELEM_CATCHALL:
 		return expr_evaluate_set_elem_catchall(ctx, expr);
-	case EXPR_FLAGCMP:
-		return expr_evaluate_flagcmp(ctx, expr);
 	case EXPR_RANGE_SYMBOL:
 		return expr_evaluate_symbol_range(ctx, expr);
 	default:
diff --git a/src/expression.c b/src/expression.c
index 2a30d5af92a4..fdf9fb97daac 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -1680,61 +1680,6 @@ struct expr *set_elem_catchall_expr_alloc(const struct location *loc)
 	return expr;
 }
 
-static void flagcmp_expr_print(const struct expr *expr, struct output_ctx *octx)
-{
-	expr_print(expr->flagcmp.expr, octx);
-
-	if (expr->op == OP_NEQ)
-		nft_print(octx, " != ");
-	else
-		nft_print(octx, " ");
-
-	expr_print(expr->flagcmp.value, octx);
-	nft_print(octx, " / ");
-	expr_print(expr->flagcmp.mask, octx);
-}
-
-static void flagcmp_expr_clone(struct expr *new, const struct expr *expr)
-{
-	new->flagcmp.expr = expr_clone(expr->flagcmp.expr);
-	new->flagcmp.mask = expr_clone(expr->flagcmp.mask);
-	new->flagcmp.value = expr_clone(expr->flagcmp.value);
-}
-
-static void flagcmp_expr_destroy(struct expr *expr)
-{
-	expr_free(expr->flagcmp.expr);
-	expr_free(expr->flagcmp.mask);
-	expr_free(expr->flagcmp.value);
-}
-
-static const struct expr_ops flagcmp_expr_ops = {
-	.type		= EXPR_FLAGCMP,
-	.name		= "flags comparison",
-	.print		= flagcmp_expr_print,
-	.json		= flagcmp_expr_json,
-	.clone		= flagcmp_expr_clone,
-	.destroy	= flagcmp_expr_destroy,
-};
-
-struct expr *flagcmp_expr_alloc(const struct location *loc, enum ops op,
-				struct expr *match, struct expr *mask,
-				struct expr *value)
-{
-	struct expr *expr;
-
-	expr = expr_alloc(loc, EXPR_FLAGCMP, match->dtype, match->byteorder,
-			  match->len);
-	expr->op = op;
-	expr->flagcmp.expr = match;
-	expr->flagcmp.mask = mask;
-	/* json output needs this operation for compatibility */
-	expr->flagcmp.mask->op = OP_OR;
-	expr->flagcmp.value = value;
-
-	return expr;
-}
-
 void range_expr_value_low(mpz_t rop, const struct expr *expr)
 {
 	switch (expr->etype) {
@@ -1814,7 +1759,6 @@ static const struct expr_ops *__expr_ops_by_type(enum expr_types etype)
 	case EXPR_FIB: return &fib_expr_ops;
 	case EXPR_XFRM: return &xfrm_expr_ops;
 	case EXPR_SET_ELEM_CATCHALL: return &set_elem_catchall_expr_ops;
-	case EXPR_FLAGCMP: return &flagcmp_expr_ops;
 	case EXPR_RANGE_VALUE: return &constant_range_expr_ops;
 	case EXPR_RANGE_SYMBOL: return &symbol_range_expr_ops;
 	}
diff --git a/src/json.c b/src/json.c
index 96413d70895a..d15e7017b892 100644
--- a/src/json.c
+++ b/src/json.c
@@ -547,20 +547,6 @@ static json_t *table_print_json(const struct table *table)
 	return json_pack("{s:o}", "table", root);
 }
 
-json_t *flagcmp_expr_json(const struct expr *expr, struct output_ctx *octx)
-{
-	json_t *left;
-
-	left = json_pack("{s:[o, o]}", expr_op_symbols[OP_AND],
-			 expr_print_json(expr->flagcmp.expr, octx),
-			 expr_print_json(expr->flagcmp.mask, octx));
-
-	return json_pack("{s:{s:s, s:o, s:o}}", "match",
-			 "op", expr_op_symbols[expr->op] ? : "in",
-			 "left", left,
-			 "right", expr_print_json(expr->flagcmp.value, octx));
-}
-
 static json_t *
 __binop_expr_json(int op, const struct expr *expr, struct output_ctx *octx)
 {
-- 
2.30.2

Re: [PATCH nft 4/4] src: remove flagcmp expression

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
>  	EXPR_SET_ELEM_CATCHALL,
> -	EXPR_FLAGCMP,
>  	EXPR_RANGE_VALUE,
>  	EXPR_RANGE_SYMBOL,
>  
> -	EXPR_MAX = EXPR_FLAGCMP
> +	EXPR_MAX = EXPR_SET_ELEM_CATCHALL
>  };

This is strange, why is EXPR_MAX not set to last expression?

Perhaps this should be changed to __EXPR_MAX
#define EXPR_MAX (__EXPR_MAX-1)

like we do elsewhere so this doesn't have to be
updated all the time?

Re: [PATCH nft 4/4] src: remove flagcmp expression

[Pablo Neira Ayuso]

On Wed, Mar 26, 2025 at 09:33:25PM +0100, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> >  	EXPR_SET_ELEM_CATCHALL,
> > -	EXPR_FLAGCMP,
> >  	EXPR_RANGE_VALUE,
> >  	EXPR_RANGE_SYMBOL,
> >  
> > -	EXPR_MAX = EXPR_FLAGCMP
> > +	EXPR_MAX = EXPR_SET_ELEM_CATCHALL
> >  };
> 
> This is strange, why is EXPR_MAX not set to last expression?
> 
> Perhaps this should be changed to __EXPR_MAX
> #define EXPR_MAX (__EXPR_MAX-1)
> 
> like we do elsewhere so this doesn't have to be
> updated all the time?

That's a good idea, I will send a v2 of this:

https://patchwork.ozlabs.org/project/netfilter-devel/patch/20250326210511.188767-1-pablo@netfilter.org/