[PATCH nft 0/8] rework dependency removal

[PATCH nft 0/8] rework dependency removal

[Florian Westphal]

This series resolves a few shortcomings with the current dependency
removal.

Problem is that the current approach sometimes can remove dependencies
that are required, i.e. where the removal does change the rule.

Examples:
inet t .. meta nfproto ipv6 tcp dport 22 or
inet t .. ip protocol tcp tcp dport 22
are reduced to 'tcp dport 22'.
ip6 nexthdr icmpv6 icmpv6 type echo-request
becomes 'ipv6 type echo-request' (which is not exactly the same,
the implicit dependency nft adds is 'meta l4proto', which skips
most extension headers).

I already pushed a couple of test cases to increase coverage.

These patches aim to fix those by making dependency removal more
strict.

The additional checks are only done in families other than ip and ipv6,
as those are already restricted to a particular l3 protocol.


 include/payload.h         |   14 +-
 include/utils.h           |    1 
 src/netlink.c             |   11 --
 src/netlink_delinearize.c |   27 +----
 src/payload.c             |  224 +++++++++++++++++++++++++++++++++++++++++-----
 tests/py/bridge/icmpX.t   |    4 
 tests/py/inet/icmpX.t     |    4 
 tests/py/inet/ip_tcp.t    |    4 
 8 files changed, 224 insertions(+), 65 deletions(-)

[PATCH nft 1/8] tests: adjust output to silence warnings

[Florian Westphal]

silence following (correct but harmless) warnings:
bridge/icmpX.t: WARNING: line: 6: 'src/nft add rule --debug=netlink bridge test-bridge input icmp type echo-request': 'icmp type echo-request' mismatches 'ether type ip icmp type echo-request'
bridge/icmpX.t: WARNING: line: 8: 'src/nft add rule --debug=netlink bridge test-bridge input icmpv6 type echo-request': 'icmpv6 type echo-request' mismatches 'ether type ip6 icmpv6 type echo-request'
inet/icmpX.t: WARNING: line: 6: 'src/nft add rule --debug=netlink inet test-inet input icmp type echo-request': 'icmp type echo-request' mismatches 'meta nfproto ipv4 icmp type echo-request'
inet/icmpX.t: WARNING: line: 8: 'src/nft add rule --debug=netlink inet test-inet input icmpv6 type echo-request': 'icmpv6 type echo-request' mismatches 'meta nfproto ipv6 icmpv6 type echo-request'

in all of these cases, we *could* remove the dependency, it can
be correctly re-built using icmp/icmpv6.

However, at this time, nft dependency removal does not have the needed
information to do this correctly.  In order to remove the ll dependency
(ether type, meta nfproto) we would need to know if the layer 4 protocol
is icmp (implies ipv4) or icmpv6 (implies ipv6).

Access to the next expression (meta l4proto) is NOT enough, for example:
ether type ip meta l4proto tcp

does not imply ip, we would need access to the rhs (the layer 4
protocol number) to know if the layer 2 check is (was) implied by another
statement later on.

To do that we would need two passes over a rule, or we would need to
track dependencies per-base.

So for now just accept that we don't handle it.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 tests/py/bridge/icmpX.t | 4 ++--
 tests/py/inet/icmpX.t   | 4 ++--
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/tests/py/bridge/icmpX.t b/tests/py/bridge/icmpX.t
index 4d7b9b0637aa..58e366c00712 100644
--- a/tests/py/bridge/icmpX.t
+++ b/tests/py/bridge/icmpX.t
@@ -3,6 +3,6 @@
 *bridge;test-bridge;input
 
 ip protocol icmp icmp type echo-request;ok;icmp type echo-request
-icmp type echo-request;ok
+icmp type echo-request;ok;ether type ip icmp type echo-request
 ip6 nexthdr icmpv6 icmpv6 type echo-request;ok;ip6 nexthdr 58 icmpv6 type echo-request
-icmpv6 type echo-request;ok
+icmpv6 type echo-request;ok;ether type ip6 icmpv6 type echo-request
diff --git a/tests/py/inet/icmpX.t b/tests/py/inet/icmpX.t
index 43ac0909195f..91f7b9e1c472 100644
--- a/tests/py/inet/icmpX.t
+++ b/tests/py/inet/icmpX.t
@@ -3,8 +3,8 @@
 *inet;test-inet;input
 
 ip protocol icmp icmp type echo-request;ok;icmp type echo-request
-icmp type echo-request;ok
+icmp type echo-request;ok;meta nfproto ipv4 icmp type echo-request
 ip6 nexthdr icmpv6 icmpv6 type echo-request;ok;ip6 nexthdr 58 icmpv6 type echo-request
-icmpv6 type echo-request;ok
+icmpv6 type echo-request;ok;meta nfproto ipv6 icmpv6 type echo-request
 # must not remove 'ip protocol' dependency, this explicitly matches icmpv6-in-ipv4.
 ip protocol ipv6-icmp meta l4proto ipv6-icmp icmpv6 type 1;ok;ip protocol 58 meta l4proto 58 icmpv6 type destination-unreachable
-- 
2.13.6

Re: [PATCH nft 1/8] tests: adjust output to silence warnings

[Pablo Neira Ayuso]

Hi Florian,

On Fri, Oct 27, 2017 at 01:06:04AM +0200, Florian Westphal wrote:
> silence following (correct but harmless) warnings:
> bridge/icmpX.t: WARNING: line: 6: 'src/nft add rule --debug=netlink bridge test-bridge input icmp type echo-request': 'icmp type echo-request' mismatches 'ether type ip icmp type echo-request'
> bridge/icmpX.t: WARNING: line: 8: 'src/nft add rule --debug=netlink bridge test-bridge input icmpv6 type echo-request': 'icmpv6 type echo-request' mismatches 'ether type ip6 icmpv6 type echo-request'
> inet/icmpX.t: WARNING: line: 6: 'src/nft add rule --debug=netlink inet test-inet input icmp type echo-request': 'icmp type echo-request' mismatches 'meta nfproto ipv4 icmp type echo-request'
> inet/icmpX.t: WARNING: line: 8: 'src/nft add rule --debug=netlink inet test-inet input icmpv6 type echo-request': 'icmpv6 type echo-request' mismatches 'meta nfproto ipv6 icmpv6 type echo-request'

Hm, I'm not hitting this here, probably there's a bug in test
infrastructure.

> in all of these cases, we *could* remove the dependency, it can
> be correctly re-built using icmp/icmpv6.
> 
> However, at this time, nft dependency removal does not have the needed
> information to do this correctly.  In order to remove the ll dependency
> (ether type, meta nfproto) we would need to know if the layer 4 protocol
> is icmp (implies ipv4) or icmpv6 (implies ipv6).
> 
> Access to the next expression (meta l4proto) is NOT enough, for example:
> ether type ip meta l4proto tcp
> 
> does not imply ip, we would need access to the rhs (the layer 4
> protocol number) to know if the layer 2 check is (was) implied by another
> statement later on.
> 
> To do that we would need two passes over a rule, or we would need to
> track dependencies per-base.
> 
> So for now just accept that we don't handle it.
> 
> Signed-off-by: Florian Westphal <fw@strlen.de>
> ---
>  tests/py/bridge/icmpX.t | 4 ++--
>  tests/py/inet/icmpX.t   | 4 ++--
>  2 files changed, 4 insertions(+), 4 deletions(-)
> 
> diff --git a/tests/py/bridge/icmpX.t b/tests/py/bridge/icmpX.t
> index 4d7b9b0637aa..58e366c00712 100644
> --- a/tests/py/bridge/icmpX.t
> +++ b/tests/py/bridge/icmpX.t
> @@ -3,6 +3,6 @@
>  *bridge;test-bridge;input
>  
>  ip protocol icmp icmp type echo-request;ok;icmp type echo-request
> -icmp type echo-request;ok
> +icmp type echo-request;ok;ether type ip icmp type echo-request
>  ip6 nexthdr icmpv6 icmpv6 type echo-request;ok;ip6 nexthdr 58 icmpv6 type echo-request
> -icmpv6 type echo-request;ok
> +icmpv6 type echo-request;ok;ether type ip6 icmpv6 type echo-request
> diff --git a/tests/py/inet/icmpX.t b/tests/py/inet/icmpX.t
> index 43ac0909195f..91f7b9e1c472 100644
> --- a/tests/py/inet/icmpX.t
> +++ b/tests/py/inet/icmpX.t
> @@ -3,8 +3,8 @@
>  *inet;test-inet;input
>  
>  ip protocol icmp icmp type echo-request;ok;icmp type echo-request
> -icmp type echo-request;ok
> +icmp type echo-request;ok;meta nfproto ipv4 icmp type echo-request

I read a couple of times your description above and I must be
overlooking anything.

To me, "icmp type echo-request" in bridge/inet/netdev should result in
two implicit dependencies, so this ends up looking like this:

1) check for IPv4, then...
2) check for ICMP in iph->protocol, then...
3) check for ICMP type.

This would be the default reasonable behaviour.

Then, we have to deal with specific corner cases, where we should
cancel dependencies.

Am I missing anything?

Re: [PATCH nft 1/8] tests: adjust output to silence warnings

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> Hi Florian,
> 
> On Fri, Oct 27, 2017 at 01:06:04AM +0200, Florian Westphal wrote:
> > silence following (correct but harmless) warnings:
> > bridge/icmpX.t: WARNING: line: 6: 'src/nft add rule --debug=netlink bridge test-bridge input icmp type echo-request': 'icmp type echo-request' mismatches 'ether type ip icmp type echo-request'
> > bridge/icmpX.t: WARNING: line: 8: 'src/nft add rule --debug=netlink bridge test-bridge input icmpv6 type echo-request': 'icmpv6 type echo-request' mismatches 'ether type ip6 icmpv6 type echo-request'
> > inet/icmpX.t: WARNING: line: 6: 'src/nft add rule --debug=netlink inet test-inet input icmp type echo-request': 'icmp type echo-request' mismatches 'meta nfproto ipv4 icmp type echo-request'
> > inet/icmpX.t: WARNING: line: 8: 'src/nft add rule --debug=netlink inet test-inet input icmpv6 type echo-request': 'icmpv6 type echo-request' mismatches 'meta nfproto ipv6 icmpv6 type echo-request'
> 
> Hm, I'm not hitting this here, probably there's a bug in test
> infrastructure.

The test case is new, most likely git pull will help.

Re: [PATCH nft 1/8] tests: adjust output to silence warnings

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > index 43ac0909195f..91f7b9e1c472 100644
> > --- a/tests/py/inet/icmpX.t
> > +++ b/tests/py/inet/icmpX.t
> > @@ -3,8 +3,8 @@
> >  *inet;test-inet;input
> >  
> >  ip protocol icmp icmp type echo-request;ok;icmp type echo-request
> > -icmp type echo-request;ok
> > +icmp type echo-request;ok;meta nfproto ipv4 icmp type echo-request
> 
> I read a couple of times your description above and I must be
> overlooking anything.
> 
> To me, "icmp type echo-request" in bridge/inet/netdev should result in
> two implicit dependencies, so this ends up looking like this:
> 
> 1) check for IPv4, then...
> 2) check for ICMP in iph->protocol, then...
> 3) check for ICMP type.
> 
> This would be the default reasonable behaviour.
> 
> Then, we have to deal with specific corner cases, where we should
> cancel dependencies.
> 
> Am I missing anything?

Sorry, I overlooked this on my first reply.

Your assesment is correct, that is indeed the default reasonable
behaviour, but, when removing, we have limited information on
the rule at the moment.

So this is really:

1) check for IPv4, then...
2) check for some l4 protocol

... from a dependency removal perspective.
and 2) doesn't provide enough information to decide if the dependency
is needed or not.

Re: [PATCH nft 1/8] tests: adjust output to silence warnings

[Pablo Neira Ayuso]

On Fri, Oct 27, 2017 at 02:52:02PM +0200, Florian Westphal wrote:
> Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> > > index 43ac0909195f..91f7b9e1c472 100644
> > > --- a/tests/py/inet/icmpX.t
> > > +++ b/tests/py/inet/icmpX.t
> > > @@ -3,8 +3,8 @@
> > >  *inet;test-inet;input
> > >  
> > >  ip protocol icmp icmp type echo-request;ok;icmp type echo-request
> > > -icmp type echo-request;ok
> > > +icmp type echo-request;ok;meta nfproto ipv4 icmp type echo-request
> > 
> > I read a couple of times your description above and I must be
> > overlooking anything.
> > 
> > To me, "icmp type echo-request" in bridge/inet/netdev should result in
> > two implicit dependencies, so this ends up looking like this:
> > 
> > 1) check for IPv4, then...
> > 2) check for ICMP in iph->protocol, then...
> > 3) check for ICMP type.
> > 
> > This would be the default reasonable behaviour.
> > 
> > Then, we have to deal with specific corner cases, where we should
> > cancel dependencies.
> > 
> > Am I missing anything?
> 
> Sorry, I overlooked this on my first reply.
> 
> Your assesment is correct, that is indeed the default reasonable
> behaviour, but, when removing, we have limited information on
> the rule at the moment.
>
> So this is really:
> 
> 1) check for IPv4, then...
> 2) check for some l4 protocol
> 
> ... from a dependency removal perspective.
> and 2) doesn't provide enough information to decide if the dependency
> is needed or not.

We probably need to make an initial pass of the entire rule, populate
context, then kill these dependencies once we have a global view on
what is being expressed there. Make sense to you?

Re: [PATCH nft 1/8] tests: adjust output to silence warnings

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> On Fri, Oct 27, 2017 at 02:52:02PM +0200, Florian Westphal wrote:
> We probably need to make an initial pass of the entire rule, populate
> context, then kill these dependencies once we have a global view on
> what is being expressed there. Make sense to you?

Yes, unfortunately I won't have time to work on that anytime soon.

[PATCH nft 2/8] src: remove exthdr_dependency_kill

[Florian Westphal]

Extend payload_dependency_kill to obtain the base from the
ct/meta/payload expression and convert the only caller.

This also introduces new WARN() define.
An earlier version used BUG() here, however, because this is used
during delinearization it seems better to not crash on a user
and just continue instead.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/payload.h         |  2 --
 include/utils.h           |  1 +
 src/netlink_delinearize.c |  2 +-
 src/payload.c             | 51 +++++++++++++++++++++++++++++++++--------------
 4 files changed, 38 insertions(+), 18 deletions(-)

diff --git a/include/payload.h b/include/payload.h
index 8e357aef461e..22443adc3358 100644
--- a/include/payload.h
+++ b/include/payload.h
@@ -44,8 +44,6 @@ extern void __payload_dependency_kill(struct payload_dep_ctx *ctx,
 				      enum proto_bases base);
 extern void payload_dependency_kill(struct payload_dep_ctx *ctx,
 				    struct expr *expr);
-extern void exthdr_dependency_kill(struct payload_dep_ctx *ctx,
-				   struct expr *expr);
 
 extern bool payload_can_merge(const struct expr *e1, const struct expr *e2);
 extern struct expr *payload_expr_join(const struct expr *e1,
diff --git a/include/utils.h b/include/utils.h
index 369195240e24..1eaf1ed9b1d7 100644
--- a/include/utils.h
+++ b/include/utils.h
@@ -28,6 +28,7 @@
 #define __noreturn		__attribute__((__noreturn__))
 
 #define BUG(fmt, arg...)	({ fprintf(stderr, "BUG: " fmt, ##arg); assert(0); })
+#define WARN(fmt, arg...)	({ fprintf(stderr, "WARN: " fmt, ##arg); })
 
 #define BUILD_BUG_ON(condition)	((void)sizeof(char[1 - 2*!!(condition)]))
 #define BUILD_BUG_ON_ZERO(e)	(sizeof(char[1 - 2 * !!(e)]) - 1)
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 44328879ebb8..1a5724843218 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -1834,7 +1834,7 @@ static void expr_postprocess(struct rule_pp_ctx *ctx, struct expr **exprp)
 		expr_postprocess(ctx, &expr->key);
 		break;
 	case EXPR_EXTHDR:
-		exthdr_dependency_kill(&ctx->pdctx, expr);
+		payload_dependency_kill(&ctx->pdctx, expr);
 		break;
 	case EXPR_SET_REF:
 	case EXPR_META:
diff --git a/src/payload.c b/src/payload.c
index aa8a95ad59f1..7d5596670cb4 100644
--- a/src/payload.c
+++ b/src/payload.c
@@ -433,6 +433,41 @@ void payload_dependency_store(struct payload_dep_ctx *ctx,
 	ctx->pdep  = stmt;
 }
 
+static enum proto_bases exthdr_to_base(const struct expr *expr)
+{
+	switch (expr->exthdr.op) {
+	case NFT_EXTHDR_OP_TCPOPT:
+		return PROTO_BASE_TRANSPORT_HDR;
+		break;
+	case NFT_EXTHDR_OP_IPV6:
+		return PROTO_BASE_NETWORK_HDR;
+	default:
+		WARN("Unhandled exthdr operation %d",
+				expr->exthdr.op);
+		break;
+	}
+
+	return PROTO_BASE_INVALID;
+}
+
+static enum proto_bases expr_to_base(const struct expr *expr)
+{
+	switch (expr->ops->type) {
+	case EXPR_PAYLOAD:
+		return expr->payload.base;
+	case EXPR_META:
+		return expr->meta.base;
+	case EXPR_CT:
+		return expr->ct.base;
+	case EXPR_EXTHDR:
+		return exthdr_to_base(expr);
+	default:
+		WARN("Cannot use payload_dependency_kill with expression type %d", expr->ops->type);
+	}
+
+	return PROTO_BASE_INVALID;
+}
+
 /**
  * __payload_dependency_kill - kill a redundant payload depedency
  *
@@ -460,21 +495,7 @@ void __payload_dependency_kill(struct payload_dep_ctx *ctx,
 
 void payload_dependency_kill(struct payload_dep_ctx *ctx, struct expr *expr)
 {
-	__payload_dependency_kill(ctx, expr->payload.base);
-}
-
-void exthdr_dependency_kill(struct payload_dep_ctx *ctx, struct expr *expr)
-{
-	switch (expr->exthdr.op) {
-	case NFT_EXTHDR_OP_TCPOPT:
-		__payload_dependency_kill(ctx, PROTO_BASE_TRANSPORT_HDR);
-		break;
-	case NFT_EXTHDR_OP_IPV6:
-		__payload_dependency_kill(ctx, PROTO_BASE_NETWORK_HDR);
-		break;
-	default:
-		break;
-	}
+	__payload_dependency_kill(ctx, expr_to_base(expr));
 }
 
 /**
-- 
2.13.6

[PATCH nft 3/8] src: add and use payload_dependency_update helper

[Florian Westphal]

We have two places that kill previous dependency (if posssible)
and then store current statement as new dependency (if eligible).

Add a helper for this and use it both from netlink (trace monitor)
and netlink_delinarize.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/payload.h         |  6 +++++-
 src/netlink.c             | 11 +----------
 src/netlink_delinearize.c | 15 +--------------
 src/payload.c             | 25 ++++++++++++++++++++++++-
 4 files changed, 31 insertions(+), 26 deletions(-)

diff --git a/include/payload.h b/include/payload.h
index 22443adc3358..76662a7a8a91 100644
--- a/include/payload.h
+++ b/include/payload.h
@@ -43,7 +43,11 @@ extern void payload_dependency_store(struct payload_dep_ctx *ctx,
 extern void __payload_dependency_kill(struct payload_dep_ctx *ctx,
 				      enum proto_bases base);
 extern void payload_dependency_kill(struct payload_dep_ctx *ctx,
-				    struct expr *expr);
+				    const struct expr *expr);
+extern void payload_dependency_update(struct payload_dep_ctx *pdctx,
+				      struct proto_ctx *ctx,
+				      struct stmt *stmt,
+				      enum proto_bases base);
 
 extern bool payload_can_merge(const struct expr *e1, const struct expr *e2);
 extern struct expr *payload_expr_join(const struct expr *e1,
diff --git a/src/netlink.c b/src/netlink.c
index 845eeeffd738..0f1dc31dc73a 100644
--- a/src/netlink.c
+++ b/src/netlink.c
@@ -2753,16 +2753,7 @@ next:
 		n++;
 
 		stacked = payload_is_stacked(desc, rel);
-
-		if (lhs->flags & EXPR_F_PROTOCOL &&
-		    pctx->pbase == PROTO_BASE_INVALID) {
-			payload_dependency_store(pctx, stmt, base - stacked);
-		} else {
-			payload_dependency_kill(pctx, lhs);
-			if (lhs->flags & EXPR_F_PROTOCOL)
-				payload_dependency_store(pctx, stmt, base - stacked);
-		}
-
+		payload_dependency_update(pctx, ctx, stmt, base - stacked);
 		goto next;
 	}
 }
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 1a5724843218..543b3a379b15 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -1339,20 +1339,7 @@ static void payload_match_expand(struct rule_pp_ctx *ctx,
 		assert(base == left->payload.base);
 
 		stacked = payload_is_stacked(ctx->pctx.protocol[base].desc, nexpr);
-
-		/* Remember the first payload protocol expression to
-		 * kill it later on if made redundant by a higher layer
-		 * payload expression.
-		 */
-		if (ctx->pdctx.pbase == PROTO_BASE_INVALID &&
-		    expr->op == OP_EQ &&
-		    left->flags & EXPR_F_PROTOCOL) {
-			payload_dependency_store(&ctx->pdctx, nstmt, base - stacked);
-		} else {
-			payload_dependency_kill(&ctx->pdctx, nexpr->left);
-			if (expr->op == OP_EQ && left->flags & EXPR_F_PROTOCOL)
-				payload_dependency_store(&ctx->pdctx, nstmt, base - stacked);
-		}
+		payload_dependency_update(&ctx->pdctx, &ctx->pctx, nstmt, base - stacked);
 	}
 	list_del(&ctx->stmt->list);
 	stmt_free(ctx->stmt);
diff --git a/src/payload.c b/src/payload.c
index 7d5596670cb4..f1b0def7cd28 100644
--- a/src/payload.c
+++ b/src/payload.c
@@ -493,7 +493,30 @@ void __payload_dependency_kill(struct payload_dep_ctx *ctx,
 	}
 }
 
-void payload_dependency_kill(struct payload_dep_ctx *ctx, struct expr *expr)
+void payload_dependency_update(struct payload_dep_ctx *pdctx,
+			       struct proto_ctx *ctx,
+			       struct stmt *stmt,
+			       enum proto_bases base)
+{
+	const struct expr *expr = stmt->expr;
+	const struct expr *left;
+
+	assert(stmt->ops->type == STMT_EXPRESSION);
+	assert(expr->ops->type == EXPR_RELATIONAL);
+
+	left = expr->left;
+	if (pdctx->pbase == PROTO_BASE_INVALID &&
+	    expr->op == OP_EQ &&
+	    left->flags & EXPR_F_PROTOCOL) {
+		payload_dependency_store(pdctx, stmt, base);
+	} else {
+		payload_dependency_kill(pdctx, left);
+		if (expr->op == OP_EQ && left->flags & EXPR_F_PROTOCOL)
+			payload_dependency_store(pdctx, stmt, base);
+	}
+}
+
+void payload_dependency_kill(struct payload_dep_ctx *ctx, const struct expr *expr)
 {
 	__payload_dependency_kill(ctx, expr_to_base(expr));
 }
-- 
2.13.6

[PATCH nft 4/8] src: pass proto_ctx to payload_dependency_kill

[Florian Westphal]

Preparation patch only, we pass proto_ctx but don't
do anything with it yet to reduce noise of follup patch.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 include/payload.h         |  6 ++++--
 src/netlink_delinearize.c | 12 ++++++------
 src/payload.c             | 32 ++++++++++++++++++--------------
 3 files changed, 28 insertions(+), 22 deletions(-)

diff --git a/include/payload.h b/include/payload.h
index 76662a7a8a91..baf284e9c307 100644
--- a/include/payload.h
+++ b/include/payload.h
@@ -40,9 +40,11 @@ void payload_dependency_reset(struct payload_dep_ctx *ctx);
 extern void payload_dependency_store(struct payload_dep_ctx *ctx,
 				     struct stmt *stmt,
 				     enum proto_bases base);
-extern void __payload_dependency_kill(struct payload_dep_ctx *ctx,
+extern void __payload_dependency_kill(struct payload_dep_ctx *pdctx,
+				      const struct proto_ctx *pctx,
 				      enum proto_bases base);
-extern void payload_dependency_kill(struct payload_dep_ctx *ctx,
+extern void payload_dependency_kill(struct payload_dep_ctx *pdctx,
+				    const struct proto_ctx *pctx,
 				    const struct expr *expr);
 extern void payload_dependency_update(struct payload_dep_ctx *pdctx,
 				      struct proto_ctx *ctx,
diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 543b3a379b15..57d780b316d0 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -1367,7 +1367,7 @@ static void payload_match_postprocess(struct rule_pp_ctx *ctx,
 		payload_expr_complete(payload, &ctx->pctx);
 		expr_set_type(expr->right, payload->dtype,
 			      payload->byteorder);
-		payload_dependency_kill(&ctx->pdctx, payload);
+		payload_dependency_kill(&ctx->pdctx, &ctx->pctx, payload);
 		break;
 	}
 }
@@ -1390,7 +1390,7 @@ static void ct_meta_common_postprocess(struct rule_pp_ctx *ctx,
 		    left->flags & EXPR_F_PROTOCOL) {
 			payload_dependency_store(&ctx->pdctx, ctx->stmt, base);
 		} else if (ctx->pdctx.pbase < PROTO_BASE_TRANSPORT_HDR) {
-			__payload_dependency_kill(&ctx->pdctx, base);
+			__payload_dependency_kill(&ctx->pdctx, &ctx->pctx, base);
 			if (left->flags & EXPR_F_PROTOCOL)
 				payload_dependency_store(&ctx->pdctx, ctx->stmt, base);
 		}
@@ -1798,7 +1798,7 @@ static void expr_postprocess(struct rule_pp_ctx *ctx, struct expr **exprp)
 		break;
 	case EXPR_PAYLOAD:
 		payload_expr_complete(expr, &ctx->pctx);
-		payload_dependency_kill(&ctx->pdctx, expr);
+		payload_dependency_kill(&ctx->pdctx, &ctx->pctx, expr);
 		break;
 	case EXPR_VALUE:
 		// FIXME
@@ -1821,7 +1821,7 @@ static void expr_postprocess(struct rule_pp_ctx *ctx, struct expr **exprp)
 		expr_postprocess(ctx, &expr->key);
 		break;
 	case EXPR_EXTHDR:
-		payload_dependency_kill(&ctx->pdctx, expr);
+		payload_dependency_kill(&ctx->pdctx, &ctx->pctx, expr);
 		break;
 	case EXPR_SET_REF:
 	case EXPR_META:
@@ -1853,14 +1853,14 @@ static void stmt_reject_postprocess(struct rule_pp_ctx *rctx)
 		stmt->reject.family = rctx->pctx.family;
 		stmt->reject.expr->dtype = &icmp_code_type;
 		if (stmt->reject.type == NFT_REJECT_TCP_RST)
-			__payload_dependency_kill(&rctx->pdctx,
+			__payload_dependency_kill(&rctx->pdctx, &rctx->pctx,
 						  PROTO_BASE_TRANSPORT_HDR);
 		break;
 	case NFPROTO_IPV6:
 		stmt->reject.family = rctx->pctx.family;
 		stmt->reject.expr->dtype = &icmpv6_code_type;
 		if (stmt->reject.type == NFT_REJECT_TCP_RST)
-			__payload_dependency_kill(&rctx->pdctx,
+			__payload_dependency_kill(&rctx->pdctx, &rctx->pctx,
 						  PROTO_BASE_TRANSPORT_HDR);
 		break;
 	case NFPROTO_INET:
diff --git a/src/payload.c b/src/payload.c
index f1b0def7cd28..12d359fd1738 100644
--- a/src/payload.c
+++ b/src/payload.c
@@ -471,25 +471,27 @@ static enum proto_bases expr_to_base(const struct expr *expr)
 /**
  * __payload_dependency_kill - kill a redundant payload depedency
  *
- * @ctx: payload dependency context
+ * @pdctx: payload dependency context
+ * @pctx: protocol context
  * @expr: higher layer payload expression
  *
  * Kill a redundant payload expression if a higher layer payload expression
  * implies its existance.
  */
-void __payload_dependency_kill(struct payload_dep_ctx *ctx,
+void __payload_dependency_kill(struct payload_dep_ctx *pdctx,
+			       const struct proto_ctx *pctx,
 			       enum proto_bases base)
 {
-	if (ctx->pbase != PROTO_BASE_INVALID &&
-	    ctx->pbase == base &&
-	    ctx->pdep != NULL) {
-		list_del(&ctx->pdep->list);
-		stmt_free(ctx->pdep);
+	if (pdctx->pbase != PROTO_BASE_INVALID &&
+	    pdctx->pbase == base &&
+	    pdctx->pdep != NULL) {
+		list_del(&pdctx->pdep->list);
+		stmt_free(pdctx->pdep);
 
-		ctx->pbase = PROTO_BASE_INVALID;
-		if (ctx->pdep == ctx->prev)
-			ctx->prev = NULL;
-		ctx->pdep  = NULL;
+		pdctx->pbase = PROTO_BASE_INVALID;
+		if (pdctx->pdep == pdctx->prev)
+			pdctx->prev = NULL;
+		pdctx->pdep  = NULL;
 	}
 }
 
@@ -510,15 +512,17 @@ void payload_dependency_update(struct payload_dep_ctx *pdctx,
 	    left->flags & EXPR_F_PROTOCOL) {
 		payload_dependency_store(pdctx, stmt, base);
 	} else {
-		payload_dependency_kill(pdctx, left);
+		payload_dependency_kill(pdctx, ctx, left);
 		if (expr->op == OP_EQ && left->flags & EXPR_F_PROTOCOL)
 			payload_dependency_store(pdctx, stmt, base);
 	}
 }
 
-void payload_dependency_kill(struct payload_dep_ctx *ctx, const struct expr *expr)
+void payload_dependency_kill(struct payload_dep_ctx *pdctx,
+			     const struct proto_ctx *ctx,
+			     const struct expr *expr)
 {
-	__payload_dependency_kill(ctx, expr_to_base(expr));
+	__payload_dependency_kill(pdctx, ctx, expr_to_base(expr));
 }
 
 /**
-- 
2.13.6

[PATCH nft 5/8] payload: add basic infrastructure to keep some dependencies

[Florian Westphal]

all the errors highlighted by the new test cases are because our current
dependency removal scheme is too trigger-happy.

Add infrastructure to do extra checks to see if the dependency can really
be removed.

This change has no effect because the new pdep_is_redundant() function
always returns true.

The next patch changes the default to false (keep dependency).

The split is to clarify infrastructure vs. conditions that need to be met
for a dependency to be okay.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 src/payload.c | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 59 insertions(+), 1 deletion(-)

diff --git a/src/payload.c b/src/payload.c
index 12d359fd1738..9cb8c6144d70 100644
--- a/src/payload.c
+++ b/src/payload.c
@@ -468,6 +468,63 @@ static enum proto_bases expr_to_base(const struct expr *expr)
 	return PROTO_BASE_INVALID;
 }
 
+static bool get_relop_base(const struct stmt *stmt,
+			   enum proto_bases *base)
+{
+	const struct expr *lhs, *rel;
+
+	if (stmt->ops->type != STMT_EXPRESSION)
+		return false;
+
+	rel = stmt->expr;
+	if (rel->ops->type != EXPR_RELATIONAL)
+		return false;
+
+	lhs = rel->left;
+	if ((lhs->flags & EXPR_F_PROTOCOL) == 0)
+		return false;
+
+	*base = expr_to_base(lhs);
+	return *base != PROTO_BASE_INVALID;
+}
+
+/*
+ * For INET/BRIDGE/NETDEV families extra care needs to be taken before
+ * removing a dependency, it might restrict the l3 protocol.  Examples:
+ *
+ * ip protocol tcp tcp dport 22
+ *
+ * In bridge/inet/netdev case, this rule only matches tcp/ipv4 so the
+ * l3 dependency cannot be removed.
+ *
+ * ip protocol ipv6-icmp meta l4proto ipv6-icmp icmpv6 type 1
+ *
+ * This only matches ipv6-icmp in ipv4, so 'ip protocol' must not be
+ * removed either.
+ */
+static bool pdep_is_redundant(struct payload_dep_ctx *pdctx,
+			      const struct proto_ctx *pctx,
+			      enum proto_bases base)
+{
+	const struct proto_desc *proto, *proto_upper;
+	const struct stmt *stmt = pdctx->pdep;
+	unsigned int family = pctx->family;
+	enum proto_bases depbase;
+
+	if (family == NFPROTO_IPV4 || family == NFPROTO_IPV6)
+		return true;
+
+	if (!get_relop_base(stmt, &depbase))
+		return true;
+
+	proto = pctx->protocol[depbase].desc;
+	proto_upper = pctx->protocol[base].desc;
+	if (proto == proto_upper)
+		return true;
+
+	return true;
+}
+
 /**
  * __payload_dependency_kill - kill a redundant payload depedency
  *
@@ -484,7 +541,8 @@ void __payload_dependency_kill(struct payload_dep_ctx *pdctx,
 {
 	if (pdctx->pbase != PROTO_BASE_INVALID &&
 	    pdctx->pbase == base &&
-	    pdctx->pdep != NULL) {
+	    pdctx->pdep != NULL &&
+	    pdep_is_redundant(pdctx, pctx, base)) {
 		list_del(&pdctx->pdep->list);
 		stmt_free(pdctx->pdep);
 
-- 
2.13.6

[PATCH nft 6/8] payload: keep dependencies that enforce a specific l3 protocol

[Florian Westphal]

This change makes dependency removal consider both the type
of the dependency and base of the dependency (linklayer, network).

For icmp, we allow removal as it implies ipv4 even if dependency
'ip protocol' rather than 'meta l4proto', for ipv4 these are the
same.

For ipv6, we do not do this, as 'ip6 nexthdr' does not skip extension
headers.

Because the default is changed to 'keep dependency', this will result
in a ton of test case warnings, we fix them up by allowing more
dependency removals in followup patches.

Most warnings occur in inet table as we no longer remove 'meta nfproto',
even if it is redundant.  Example:

inet test-inet input ip6 saddr 1234:1234:1234:1234:1234:1234:1234:1234'
will be shown as
meta nfproto ipv6 ip6 saddr 1...

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 src/payload.c | 45 ++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 42 insertions(+), 3 deletions(-)

diff --git a/src/payload.c b/src/payload.c
index 9cb8c6144d70..184a611704ea 100644
--- a/src/payload.c
+++ b/src/payload.c
@@ -469,7 +469,8 @@ static enum proto_bases expr_to_base(const struct expr *expr)
 }
 
 static bool get_relop_base(const struct stmt *stmt,
-			   enum proto_bases *base)
+			   enum proto_bases *base,
+			   unsigned int *type)
 {
 	const struct expr *lhs, *rel;
 
@@ -485,6 +486,7 @@ static bool get_relop_base(const struct stmt *stmt,
 		return false;
 
 	*base = expr_to_base(lhs);
+	*type = lhs->ops->type;
 	return *base != PROTO_BASE_INVALID;
 }
 
@@ -510,11 +512,12 @@ static bool pdep_is_redundant(struct payload_dep_ctx *pdctx,
 	const struct stmt *stmt = pdctx->pdep;
 	unsigned int family = pctx->family;
 	enum proto_bases depbase;
+	unsigned int type;
 
 	if (family == NFPROTO_IPV4 || family == NFPROTO_IPV6)
 		return true;
 
-	if (!get_relop_base(stmt, &depbase))
+	if (!get_relop_base(stmt, &depbase, &type))
 		return true;
 
 	proto = pctx->protocol[depbase].desc;
@@ -522,7 +525,43 @@ static bool pdep_is_redundant(struct payload_dep_ctx *pdctx,
 	if (proto == proto_upper)
 		return true;
 
-	return true;
+	switch (depbase) {
+	case PROTO_BASE_NETWORK_HDR:
+		/* if pdep is meta its redundant ('meta l4proto'). */
+		if (type == EXPR_META)
+			return true;
+
+		/* exceptions: icmp implies ipv4 */
+		if (proto_upper == &proto_icmp && proto == &proto_ip)
+			return true;
+		/* no exception for &proto_icmp6: 'ip protocol' that is
+		 * handled above is NOT the same as ip6 nexthdr, due to
+		 * extension headers in ipv6.
+		 */
+		break;
+	case PROTO_BASE_LL_HDR:
+		/*
+		 * It would be nice to also remove
+		 * 'meta nfproto' in cases like
+		 * meta nfproto ipv6 icmpv6 type ..., but we can't.
+		 * problem is that we do not know the upper (l4 protocol)
+		 * as, we only have access to the next expression.
+		 *
+		 * In this case, that would be EXPR_META (meta l4proto),
+		 * but we need to know the rhs to learn the protocol.
+		 *
+		 * Just removing blindly here
+		 * (if (e->ops->type == EXPR_META) return true), would
+		 * break cases like
+		 * meta nfproto ipv6 tcp dport ..., as tcp doesn't imply
+		 * ipv4 or ipv6, unlike icmp/icmpv6.
+		 */
+		break;
+	default:
+		return true;
+	}
+
+	return false;
 }
 
 /**
-- 
2.13.6

[PATCH nft 7/8] payload: consider expression type during dependency removal

[Florian Westphal]

permit removal of linklayer dependencies if the current
expression type permits this.

This gets rid of most of the warnings added by the previous
commit.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 src/netlink_delinearize.c |  2 +-
 src/payload.c             | 37 ++++++++++++++++++++++++++++++++++---
 2 files changed, 35 insertions(+), 4 deletions(-)

diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c
index 57d780b316d0..efb80fdc3da4 100644
--- a/src/netlink_delinearize.c
+++ b/src/netlink_delinearize.c
@@ -1390,7 +1390,7 @@ static void ct_meta_common_postprocess(struct rule_pp_ctx *ctx,
 		    left->flags & EXPR_F_PROTOCOL) {
 			payload_dependency_store(&ctx->pdctx, ctx->stmt, base);
 		} else if (ctx->pdctx.pbase < PROTO_BASE_TRANSPORT_HDR) {
-			__payload_dependency_kill(&ctx->pdctx, &ctx->pctx, base);
+			payload_dependency_kill(&ctx->pdctx, &ctx->pctx, left);
 			if (left->flags & EXPR_F_PROTOCOL)
 				payload_dependency_store(&ctx->pdctx, ctx->stmt, base);
 		}
diff --git a/src/payload.c b/src/payload.c
index 184a611704ea..69985af99c9a 100644
--- a/src/payload.c
+++ b/src/payload.c
@@ -506,6 +506,7 @@ static bool get_relop_base(const struct stmt *stmt,
  */
 static bool pdep_is_redundant(struct payload_dep_ctx *pdctx,
 			      const struct proto_ctx *pctx,
+			      const struct expr *e,
 			      enum proto_bases base)
 {
 	const struct proto_desc *proto, *proto_upper;
@@ -541,6 +542,28 @@ static bool pdep_is_redundant(struct payload_dep_ctx *pdctx,
 		break;
 	case PROTO_BASE_LL_HDR:
 		/*
+		 * If we have an expression, then check if it implies an l3
+		 * protocol.
+		 * If we don't have one, then we keep the protocol dependency.
+		 */
+		if (!e)
+			return false;
+
+		if ((e->flags & EXPR_F_PROTOCOL) == 0)
+			return true;
+
+		switch (e->ops->type) {
+		case EXPR_PAYLOAD:
+			return true;
+		case EXPR_CT:
+			if (type == EXPR_CT) /* ct s/daddr */
+				return true;
+			break;
+		default:
+			break;
+		}
+
+		/*
 		 * It would be nice to also remove
 		 * 'meta nfproto' in cases like
 		 * meta nfproto ipv6 icmpv6 type ..., but we can't.
@@ -574,14 +597,15 @@ static bool pdep_is_redundant(struct payload_dep_ctx *pdctx,
  * Kill a redundant payload expression if a higher layer payload expression
  * implies its existance.
  */
-void __payload_dependency_kill(struct payload_dep_ctx *pdctx,
+static void do_payload_dependency_kill(struct payload_dep_ctx *pdctx,
 			       const struct proto_ctx *pctx,
+			       const struct expr *e,
 			       enum proto_bases base)
 {
 	if (pdctx->pbase != PROTO_BASE_INVALID &&
 	    pdctx->pbase == base &&
 	    pdctx->pdep != NULL &&
-	    pdep_is_redundant(pdctx, pctx, base)) {
+	    pdep_is_redundant(pdctx, pctx, e, base)) {
 		list_del(&pdctx->pdep->list);
 		stmt_free(pdctx->pdep);
 
@@ -592,6 +616,13 @@ void __payload_dependency_kill(struct payload_dep_ctx *pdctx,
 	}
 }
 
+void __payload_dependency_kill(struct payload_dep_ctx *pdctx,
+			       const struct proto_ctx *pctx,
+			       enum proto_bases base)
+{
+	do_payload_dependency_kill(pdctx, pctx, NULL, base);
+}
+
 void payload_dependency_update(struct payload_dep_ctx *pdctx,
 			       struct proto_ctx *ctx,
 			       struct stmt *stmt,
@@ -619,7 +650,7 @@ void payload_dependency_kill(struct payload_dep_ctx *pdctx,
 			     const struct proto_ctx *ctx,
 			     const struct expr *expr)
 {
-	__payload_dependency_kill(pdctx, ctx, expr_to_base(expr));
+	do_payload_dependency_kill(pdctx, ctx, expr, expr_to_base(expr));
 }
 
 /**
-- 
2.13.6

[PATCH nft 8/8] tests: silence test case

[Florian Westphal]

removes this harmless warning:
'ip saddr 1.2.3.4 tcp dport 22' mismatches 'ip protocol 6 ip saddr 1.2.3.4 tcp dport 22'

alternative fix is to track the number of payload expressions seen
in the current dependency base so we know that we had another expression
(ip saddr in this case) besides the 'ip protocol' statement.

But because nft doesn't add such a dependency on its own (it would
have added 'meta l4proto tcp' without the ip protocol 6 statement)
it seems simpler to just let nft print the rule as-is instead of
adding more code.

Signed-off-by: Florian Westphal <fw@strlen.de>
---
 tests/py/inet/ip_tcp.t | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/tests/py/inet/ip_tcp.t b/tests/py/inet/ip_tcp.t
index f2a28ebdd531..4eebe3865d76 100644
--- a/tests/py/inet/ip_tcp.t
+++ b/tests/py/inet/ip_tcp.t
@@ -8,8 +8,8 @@
 # must not remove ip dependency -- ONLY ipv4 packets should be matched
 ip protocol tcp tcp dport 22;ok;ip protocol 6 tcp dport 22
 
-# can remove it here, ip protocol is implied via saddr.
-ip protocol tcp ip saddr 1.2.3.4 tcp dport 22;ok;ip saddr 1.2.3.4 tcp dport 22
+# could be remove here, ip protocol is implied via saddr.
+ip protocol tcp ip saddr 1.2.3.4 tcp dport 22;ok;ip protocol 6 ip saddr 1.2.3.4 tcp dport 22
 
 # but not here.
 ip protocol tcp counter ip saddr 1.2.3.4 tcp dport 22;ok;ip protocol 6 counter ip saddr 1.2.3.4 tcp dport 22
-- 
2.13.6

Re: [PATCH nft 0/8] rework dependency removal

[Pablo Neira Ayuso]

On Fri, Oct 27, 2017 at 01:06:03AM +0200, Florian Westphal wrote:
> This series resolves a few shortcomings with the current dependency
> removal.
> 
> Problem is that the current approach sometimes can remove dependencies
> that are required, i.e. where the removal does change the rule.
> 
> Examples:
> inet t .. meta nfproto ipv6 tcp dport 22 or
> inet t .. ip protocol tcp tcp dport 22
> are reduced to 'tcp dport 22'.

OK, this is wrong, indeed.

> ip6 nexthdr icmpv6 icmpv6 type echo-request
> becomes 'ipv6 type echo-request' (which is not exactly the same,
> the implicit dependency nft adds is 'meta l4proto', which skips
> most extension headers).

This dependency removal is wrong too indeed and I agree it needs to be
fixed.

What I don't still is why patch 1/8 is expanding icmp type
echo-request to show explicit "ether type ip icmp type echo-request"
when listing the ruleset.

I mean:

-icmp type echo-request;ok
+icmp type echo-request;ok;ether type ip icmp type echo-request

Re: [PATCH nft 0/8] rework dependency removal

[Florian Westphal]

Pablo Neira Ayuso <pablo@netfilter.org> wrote:
> What I don't still is why patch 1/8 is expanding icmp type
> echo-request to show explicit "ether type ip icmp type echo-request"
> when listing the ruleset.
> 
> I mean:
> 
> -icmp type echo-request;ok
> +icmp type echo-request;ok;ether type ip icmp type echo-request

Correct, this is redundant, the 'ether type ip' could be removed
here.

But it would need more work to achive this, f.e. by
tracking not the last but all seen dependencies per-base and doing
the removal only after seeing all consecutive expression statements.

At the moment, when 'remove ether type ip' decision is made, we only
know that the next expression is 'meta l4proto'.

But that is not enough to know if the dependency is implicit or not.
Another soltution would be to pass the relational expression, and
then extract rhs too. That would allow to see the 'icmp' in
'meta l4proto icmp' (and then remove the dep because icmp implies ipv4).

However, as icmp is the only case where we can do the removal I think
its currently not super urgent to make these changes.

Does that explanation help?

I would re-word the commit message accordingly.