[PATCH nft 1/2] evaluate: rename recursion counter to recursion.binop

[PATCH nft 1/2] evaluate: rename recursion counter to recursion.binop

[Florian Westphal]

The existing recursion counter is only used by the binop expression
to detect if we've completely followed all the binops.

We can only chain up to NFT_MAX_EXPR_RECURSION binops, but
the evaluation step can perform constant-folding, so we must
first recurse until we found the rightmost (last) binop in the
chain.

Then we can check the post-eval chain to see if it is something
that can be serialized later or not.

Thus we can't reuse the existing ctx->recursion counter for
other expressions; entering the initial expr_evaluate_binop with
ctx->recursion > 0 would break things.

Therefore rename this to an embedded structure.
This allows us to add a new recursion counter to the new embedded
structure in a followup patch.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/rule.h |  8 ++++++--
 src/evaluate.c | 10 +++++-----
 2 files changed, 11 insertions(+), 7 deletions(-)

diff --git a/include/rule.h b/include/rule.h
index 85a0d9c0b524..e7e80a41506c 100644
--- a/include/rule.h
+++ b/include/rule.h
@@ -756,6 +756,10 @@ extern void cmd_free(struct cmd *cmd);
 #include <payload.h>
 #include <expression.h>
 
+struct eval_recursion {
+	uint16_t binop;
+};
+
 /**
  * struct eval_ctx - evaluation context
  *
@@ -767,7 +771,7 @@ extern void cmd_free(struct cmd *cmd);
  * @set:	current set
  * @stmt:	current statement
  * @stmt_len:	current statement template length
- * @recursion:  expr evaluation recursion counter
+ * @recursion:  expr evaluation recursion counters
  * @cache:	cache context
  * @debug_mask: debugging bitmask
  * @ectx:	expression context
@@ -783,7 +787,7 @@ struct eval_ctx {
 	struct set		*set;
 	struct stmt		*stmt;
 	uint32_t		stmt_len;
-	uint32_t		recursion;
+	struct eval_recursion	recursion;
 	struct expr_ctx		ectx;
 	struct proto_ctx	_pctx[2];
 	const struct proto_desc	*inner_desc;
diff --git a/src/evaluate.c b/src/evaluate.c
index f73edc916406..d099be137cb3 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1518,11 +1518,11 @@ static int expr_evaluate_binop(struct eval_ctx *ctx, struct expr **expr)
 	unsigned int max_shift_len = ctx->ectx.len;
 	int ret = -1;
 
-	if (ctx->recursion >= USHRT_MAX)
+	if (ctx->recursion.binop >= USHRT_MAX)
 		return expr_binary_error(ctx->msgs, op, NULL,
 					 "Binary operation limit %u reached ",
-					 ctx->recursion);
-	ctx->recursion++;
+					 ctx->recursion.binop);
+	ctx->recursion.binop++;
 
 	if (expr_evaluate(ctx, &op->left) < 0)
 		return -1;
@@ -1607,7 +1607,7 @@ static int expr_evaluate_binop(struct eval_ctx *ctx, struct expr **expr)
 	}
 
 
-	if (ctx->recursion == 0)
+	if (ctx->recursion.binop == 0)
 		BUG("recursion counter underflow");
 
 	/* can't check earlier: evaluate functions might do constant-merging + expr_free.
@@ -1615,7 +1615,7 @@ static int expr_evaluate_binop(struct eval_ctx *ctx, struct expr **expr)
 	 * So once we've evaluate everything check for remaining length of the
 	 * binop chain.
 	 */
-	if (--ctx->recursion == 0) {
+	if (--ctx->recursion.binop == 0) {
 		unsigned int to_linearize = 0;
 
 		op = *expr;
-- 
2.49.0

[PATCH nft 2/2] evaluate: restrict allowed subtypes of concatenations

[Florian Westphal]

We need to restrict this, included bogon asserts with:
BUG: unknown expression type prefix
nft: src/netlink_linearize.c:940: netlink_gen_expr: Assertion `0' failed.

Prefix expressions are only allowed if the concatenation is used within
a set element, not when specifying the lookup key.

For the former, anything that represents a value is allowed.
For the latter, only what will generate data (fill a register) is
permitted.

Add a new list recursion counter for this. If its 0 then we're building
the lookup key, if its the latter the concatenation is the RHS part
of a relational expression and prefix, ranges and so on are allowed.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/rule.h                                |  1 +
 src/evaluate.c                                | 42 ++++++++++++++++++-
 .../unknown_expression_type_prefix_assert     |  9 ++++
 3 files changed, 51 insertions(+), 1 deletion(-)
 create mode 100644 tests/shell/testcases/bogons/nft-f/unknown_expression_type_prefix_assert

diff --git a/include/rule.h b/include/rule.h
index e7e80a41506c..655d6abaf5fa 100644
--- a/include/rule.h
+++ b/include/rule.h
@@ -758,6 +758,7 @@ extern void cmd_free(struct cmd *cmd);
 
 struct eval_recursion {
 	uint16_t binop;
+	uint16_t list;
 };
 
 /**
diff --git a/src/evaluate.c b/src/evaluate.c
index d099be137cb3..0c8af09492d1 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -1638,10 +1638,12 @@ static int list_member_evaluate(struct eval_ctx *ctx, struct expr **expr)
 	struct expr *next = list_entry((*expr)->list.next, struct expr, list);
 	int err;
 
+	ctx->recursion.list++;
 	assert(*expr != next);
 	list_del(&(*expr)->list);
 	err = expr_evaluate(ctx, expr);
 	list_add_tail(&(*expr)->list, &next->list);
+	ctx->recursion.list--;
 	return err;
 }
 
@@ -1704,10 +1706,48 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr)
 		if (list_member_evaluate(ctx, &i) < 0)
 			return -1;
 
-		if (i->etype == EXPR_SET)
+		switch (i->etype) {
+		case EXPR_VALUE:
+		case EXPR_UNARY:
+		case EXPR_BINOP:
+		case EXPR_RELATIONAL:
+		case EXPR_CONCAT:
+		case EXPR_MAP:
+		case EXPR_PAYLOAD:
+		case EXPR_EXTHDR:
+		case EXPR_META:
+		case EXPR_RT:
+		case EXPR_CT:
+		case EXPR_SET_ELEM:
+		case EXPR_NUMGEN:
+		case EXPR_HASH:
+		case EXPR_FIB:
+		case EXPR_SOCKET:
+		case EXPR_OSF:
+		case EXPR_XFRM:
+			break;
+		case EXPR_RANGE:
+		case EXPR_PREFIX:
+			/* allowed on RHS (e.g. th dport . mark { 1-65535 . 42 }
+			 *                                       ~~~~~~~~ allowed
+			 * but not on LHS (e.g  1-4 . mark { ...}
+			 *                      ~~~ illegal
+			 *
+			 * recursion.list > 0 means that the concatenation is
+			 * part of another expression, such as EXPR_MAPPING or
+			 * EXPR_SET_ELEM (is used as RHS).
+			 */
+			if (ctx->recursion.list > 0)
+				break;
+
+			return expr_error(ctx->msgs, i,
+					  "cannot use %s in concatenation",
+					  expr_name(i));
+		default:
 			return expr_error(ctx->msgs, i,
 					  "cannot use %s in concatenation",
 					  expr_name(i));
+		}
 
 		if (!i->dtype)
 			return expr_error(ctx->msgs, i,
diff --git a/tests/shell/testcases/bogons/nft-f/unknown_expression_type_prefix_assert b/tests/shell/testcases/bogons/nft-f/unknown_expression_type_prefix_assert
new file mode 100644
index 000000000000..d7f8526092a5
--- /dev/null
+++ b/tests/shell/testcases/bogons/nft-f/unknown_expression_type_prefix_assert
@@ -0,0 +1,9 @@
+table t {
+	set sc {
+		type inet_service . ifname
+	}
+
+	chain c {
+		tcp dport . bla* @sc accept
+	}
+}
-- 
2.49.0

Re: [PATCH nft 2/2] evaluate: restrict allowed subtypes of concatenations

[Pablo Neira Ayuso]

Hi Florian,

On Wed, Apr 02, 2025 at 04:50:40PM +0200, Florian Westphal wrote:
> We need to restrict this, included bogon asserts with:
> BUG: unknown expression type prefix
> nft: src/netlink_linearize.c:940: netlink_gen_expr: Assertion `0' failed.
> 
> Prefix expressions are only allowed if the concatenation is used within
> a set element, not when specifying the lookup key.
> 
> For the former, anything that represents a value is allowed.
> For the latter, only what will generate data (fill a register) is
> permitted.
> 
> Add a new list recursion counter for this. If its 0 then we're building
> the lookup key, if its the latter the concatenation is the RHS part
> of a relational expression and prefix, ranges and so on are allowed.
[...]
> diff --git a/src/evaluate.c b/src/evaluate.c
> index d099be137cb3..0c8af09492d1 100644
> --- a/src/evaluate.c
> +++ b/src/evaluate.c
[...]
> @@ -1704,10 +1706,48 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr)
>  		if (list_member_evaluate(ctx, &i) < 0)
>  			return -1;
>  
> -		if (i->etype == EXPR_SET)
> +		switch (i->etype) {
> +		case EXPR_VALUE:
> +		case EXPR_UNARY:
> +		case EXPR_BINOP:
> +		case EXPR_RELATIONAL:
> +		case EXPR_CONCAT:
> +		case EXPR_MAP:
> +		case EXPR_PAYLOAD:
> +		case EXPR_EXTHDR:
> +		case EXPR_META:
> +		case EXPR_RT:
> +		case EXPR_CT:
> +		case EXPR_SET_ELEM:
> +		case EXPR_NUMGEN:
> +		case EXPR_HASH:
> +		case EXPR_FIB:
> +		case EXPR_SOCKET:
> +		case EXPR_OSF:
> +		case EXPR_XFRM:

I am expecting more new selector expressions here that would need to
be added and I think it is less likely to see new constant expressions
in the future, so maybe reverse this logic ...

		if (i->etype == EXPR_RANGE ||
                    i->etype == EXPR_PREFIX) {
			/* allowed on RHS (e.g. th dport . mark { 1-65535 . 42 }
			 *                                       ~~~~~~~~ allowed
			 * but not on LHS (e.g  1-4 . mark { ...}
			 *                      ~~~ illegal
                        ...

... and let anything else be accepted?

> +			break;
> +		case EXPR_RANGE:
> +		case EXPR_PREFIX:
> +			/* allowed on RHS (e.g. th dport . mark { 1-65535 . 42 }
> +			 *                                       ~~~~~~~~ allowed
> +			 * but not on LHS (e.g  1-4 . mark { ...}
> +			 *                      ~~~ illegal
> +			 *
> +			 * recursion.list > 0 means that the concatenation is
> +			 * part of another expression, such as EXPR_MAPPING or
> +			 * EXPR_SET_ELEM (is used as RHS).
> +			 */
> +			if (ctx->recursion.list > 0)
> +				break;

So recursion.list is used to provide context to identify this is rhs,
correct? Is your intention is to use this recursion.list to control to
deeper recursions in a follow up patch?

Not related, but if goal is to provide context then I also need more
explicit context hints for bitfield payload and bitwise expressions
where the evaluation needs to be different depending on where the
expression is located (not the same if the expression is either used
as selector or as lhs/rhs of assignment).

I don't know yet how such new context enum to modify evaluation
behaviour will look, so we can just use recursion.list by now, I don't
want to block this fix.

> +
> +			return expr_error(ctx->msgs, i,
> +					  "cannot use %s in concatenation",
> +					  expr_name(i));
> +		default:
>  			return expr_error(ctx->msgs, i,
>  					  "cannot use %s in concatenation",
>  					  expr_name(i));
> +		}
>  
>  		if (!i->dtype)
>  			return expr_error(ctx->msgs, i,
> diff --git a/tests/shell/testcases/bogons/nft-f/unknown_expression_type_prefix_assert b/tests/shell/testcases/bogons/nft-f/unknown_expression_type_prefix_assert
> new file mode 100644
> index 000000000000..d7f8526092a5
> --- /dev/null
> +++ b/tests/shell/testcases/bogons/nft-f/unknown_expression_type_prefix_assert
> @@ -0,0 +1,9 @@
> +table t {
> +	set sc {
> +		type inet_service . ifname
> +	}
> +
> +	chain c {
> +		tcp dport . bla* @sc accept
> +	}
> +}
> -- 
> 2.49.0
> 
> 

Re: [PATCH nft 2/2] evaluate: restrict allowed subtypes of concatenations

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > diff --git a/src/evaluate.c b/src/evaluate.c
> > index d099be137cb3..0c8af09492d1 100644
> > --- a/src/evaluate.c
> > +++ b/src/evaluate.c
> [...]
> > @@ -1704,10 +1706,48 @@ static int expr_evaluate_concat(struct eval_ctx *ctx, struct expr **expr)
> >  		if (list_member_evaluate(ctx, &i) < 0)
> >  			return -1;
> >  
> > -		if (i->etype == EXPR_SET)
> > +		switch (i->etype) {
> > +		case EXPR_VALUE:
> > +		case EXPR_UNARY:
> > +		case EXPR_BINOP:
> > +		case EXPR_RELATIONAL:
> > +		case EXPR_CONCAT:
> > +		case EXPR_MAP:
> > +		case EXPR_PAYLOAD:
> > +		case EXPR_EXTHDR:
> > +		case EXPR_META:
> > +		case EXPR_RT:
> > +		case EXPR_CT:
> > +		case EXPR_SET_ELEM:
> > +		case EXPR_NUMGEN:
> > +		case EXPR_HASH:
> > +		case EXPR_FIB:
> > +		case EXPR_SOCKET:
> > +		case EXPR_OSF:
> > +		case EXPR_XFRM:
> 
> I am expecting more new selector expressions here that would need to
> be added and I think it is less likely to see new constant expressions
> in the future, so maybe reverse this logic ...
> 
> 		if (i->etype == EXPR_RANGE ||
>                     i->etype == EXPR_PREFIX) {
> 			/* allowed on RHS (e.g. th dport . mark { 1-65535 . 42 }
> 			 *                                       ~~~~~~~~ allowed
> 			 * but not on LHS (e.g  1-4 . mark { ...}
> 			 *                      ~~~ illegal
>                         ...
> 
> ... and let anything else be accepted?

I prefer "accept whats safe and reject rest" but I can invert
if you want.

> > +			 * EXPR_SET_ELEM (is used as RHS).
> > +			 */
> > +			if (ctx->recursion.list > 0)
> > +				break;
> 
> So recursion.list is used to provide context to identify this is rhs,
> correct?

Yes.

> Is your intention is to use this recursion.list to control to
> deeper recursions in a follow up patch?

No, what did you have in mind?

I could see adding new members to ctx->recursion to control other
possible recursions in addition to what we have now.

But I don't see other uses for .list at this time.

> Not related, but if goal is to provide context then I also need more
> explicit context hints for bitfield payload and bitwise expressions
> where the evaluation needs to be different depending on where the
> expression is located (not the same if the expression is either used
> as selector or as lhs/rhs of assignment).
> 
> I don't know yet how such new context enum to modify evaluation
> behaviour will look, so we can just use recursion.list by now, I don't
> want to block this fix.

OK.  Yes, it would also work if there was some different "where am I"
indicator, e.g. if (ctx->expr_side == CTX_EXPR_LHS) or whatever.

This fix isn't urgent, we can keep it back and come back to this
if you prefer to first work on the ctx hint extensions.

Re: [PATCH nft 2/2] evaluate: restrict allowed subtypes of concatenations

[Pablo Neira Ayuso]

On Fri, Apr 11, 2025 at 07:52:01AM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
[...]
> > Not related, but if goal is to provide context then I also need more
> > explicit context hints for bitfield payload and bitwise expressions
> > where the evaluation needs to be different depending on where the
> > expression is located (not the same if the expression is either used
> > as selector or as lhs/rhs of assignment).
> > 
> > I don't know yet how such new context enum to modify evaluation
> > behaviour will look, so we can just use recursion.list by now, I don't
> > want to block this fix.
>
> OK.  Yes, it would also work if there was some different "where am I"
> indicator, e.g. if (ctx->expr_side == CTX_EXPR_LHS) or whatever.

Exactly, something like this.

> This fix isn't urgent, we can keep it back and come back to this
> if you prefer to first work on the ctx hint extensions.

I am in the need for such a context for payload/meta statements.

        meta mark set ip dscp map ...
                      ^^^^^^^

in this case, ip dscp needs to be evaluated as a key for lookups,
shift can probably be removed for implicit maps.

While in this case:

        meta mark set ip dscp
                      ^^^^^^^

in this case, ip dscp needs the shift.

Then, there is:

        ip dscp set meta mark
        ^^^^^^^

(note: this is not yet supported)

where ip dscp needs to expand to 16-bit because of the kernel
checksum routine requirements.

They are all payload expressions, but evaluation needs to be slightly
different depending on how the expression is used.

This context should help disentangle evaluation, evaluation is making
assumption based on subtle hints, I think there is a need for more
explicit hints.

We can revisit in a few weeks, otherwise take this.

Re: [PATCH nft 2/2] evaluate: restrict allowed subtypes of concatenations

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> I am in the need for such a context for payload/meta statements.
> 
>         meta mark set ip dscp map ...
>                       ^^^^^^^
> 
> in this case, ip dscp needs to be evaluated as a key for lookups,
> shift can probably be removed for implicit maps.
> 
> While in this case:
> 
>         meta mark set ip dscp
>                       ^^^^^^^
> 
> in this case, ip dscp needs the shift.
> 
> Then, there is:
> 
>         ip dscp set meta mark
>         ^^^^^^^
> 
> (note: this is not yet supported)
> 
> where ip dscp needs to expand to 16-bit because of the kernel
> checksum routine requirements.
> 
> They are all payload expressions, but evaluation needs to be slightly
> different depending on how the expression is used.
> 
> This context should help disentangle evaluation, evaluation is making
> assumption based on subtle hints, I think there is a need for more
> explicit hints.

Agreed.

> We can revisit in a few weeks, otherwise take this.

OK, lets keep this back for now; technically I don't need
to know the recursion depth, I need to know the placement
(lhs / lookup key resp. rhs / element key) to figure out what
restrictions apply.