[PATCH nftables 0/4] optimization updates

[PATCH nftables 0/4] optimization updates

[Pablo Neira Ayuso]

nft -o/--optimize crashes with verdict maps due to insufficient checks
on the expression type for verdict statements.

This patchset extends -o/--optimize to merge two rules with the same
verdict maps side by side.

This also prepares for allowing to merge raw expressions in
concatenation which is not possible yet due to the use of integer type.

Pablo Neira Ayuso (4):
  optimize: add __expr_cmp()
  optimize: merge verdict maps with same lookup key
  optimize: check for payload base and offset when searching for mergers
  optimize: do not merge raw payload expressions

 src/optimize.c                                | 210 +++++++++++++-----
 .../optimizations/dumps/merge_vmaps.nft       |  12 +
 .../shell/testcases/optimizations/merge_vmaps |  25 +++
 3 files changed, 189 insertions(+), 58 deletions(-)
 create mode 100644 tests/shell/testcases/optimizations/dumps/merge_vmaps.nft
 create mode 100755 tests/shell/testcases/optimizations/merge_vmaps

-- 
2.30.2

[PATCH nftables 1/4] optimize: add __expr_cmp()

[Pablo Neira Ayuso]

Add helper function to compare expression to allow for reuse.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/optimize.c | 98 ++++++++++++++++++++++++++------------------------
 1 file changed, 52 insertions(+), 46 deletions(-)

diff --git a/src/optimize.c b/src/optimize.c
index b5fb2c4179d0..c52966a86e2c 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -33,6 +33,57 @@ struct optimize_ctx {
 	uint32_t num_rules;
 };
 
+static bool __expr_cmp(const struct expr *expr_a, const struct expr *expr_b)
+{
+	if (expr_a->etype != expr_b->etype)
+		return false;
+
+	switch (expr_a->etype) {
+	case EXPR_PAYLOAD:
+		if (expr_a->payload.desc != expr_b->payload.desc)
+			return false;
+		if (expr_a->payload.tmpl != expr_b->payload.tmpl)
+			return false;
+		break;
+	case EXPR_EXTHDR:
+		if (expr_a->exthdr.desc != expr_b->exthdr.desc)
+			return false;
+		if (expr_a->exthdr.tmpl != expr_b->exthdr.tmpl)
+			return false;
+		break;
+	case EXPR_META:
+		if (expr_a->meta.key != expr_b->meta.key)
+			return false;
+		if (expr_a->meta.base != expr_b->meta.base)
+			return false;
+		break;
+	case EXPR_CT:
+		if (expr_a->ct.key != expr_b->ct.key)
+			return false;
+		if (expr_a->ct.base != expr_b->ct.base)
+			return false;
+		if (expr_a->ct.direction != expr_b->ct.direction)
+			return false;
+		if (expr_a->ct.nfproto != expr_b->ct.nfproto)
+			return false;
+		break;
+	case EXPR_RT:
+		if (expr_a->rt.key != expr_b->rt.key)
+			return false;
+		break;
+	case EXPR_SOCKET:
+		if (expr_a->socket.key != expr_b->socket.key)
+			return false;
+		if (expr_a->socket.level != expr_b->socket.level)
+			return false;
+		break;
+	default:
+		return false;
+	}
+
+	return true;
+}
+
 static bool __stmt_type_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)
 {
 	struct expr *expr_a, *expr_b;
@@ -45,52 +96,7 @@ static bool __stmt_type_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)
 		expr_a = stmt_a->expr;
 		expr_b = stmt_b->expr;
 
-		if (expr_a->left->etype != expr_b->left->etype)
-			return false;
-
-		switch (expr_a->left->etype) {
-		case EXPR_PAYLOAD:
-			if (expr_a->left->payload.desc != expr_b->left->payload.desc)
-				return false;
-			if (expr_a->left->payload.tmpl != expr_b->left->payload.tmpl)
-				return false;
-			break;
-		case EXPR_EXTHDR:
-			if (expr_a->left->exthdr.desc != expr_b->left->exthdr.desc)
-				return false;
-			if (expr_a->left->exthdr.tmpl != expr_b->left->exthdr.tmpl)
-				return false;
-			break;
-		case EXPR_META:
-			if (expr_a->left->meta.key != expr_b->left->meta.key)
-				return false;
-			if (expr_a->left->meta.base != expr_b->left->meta.base)
-				return false;
-			break;
-		case EXPR_CT:
-			if (expr_a->left->ct.key != expr_b->left->ct.key)
-				return false;
-			if (expr_a->left->ct.base != expr_b->left->ct.base)
-				return false;
-			if (expr_a->left->ct.direction != expr_b->left->ct.direction)
-				return false;
-			if (expr_a->left->ct.nfproto != expr_b->left->ct.nfproto)
-				return false;
-			break;
-		case EXPR_RT:
-			if (expr_a->left->rt.key != expr_b->left->rt.key)
-				return false;
-			break;
-		case EXPR_SOCKET:
-			if (expr_a->left->socket.key != expr_b->left->socket.key)
-				return false;
-			if (expr_a->left->socket.level != expr_b->left->socket.level)
-				return false;
-			break;
-		default:
-			return false;
-		}
-		break;
+		return __expr_cmp(expr_a->left, expr_b->left);
 	case STMT_COUNTER:
 	case STMT_NOTRACK:
 		break;
-- 
2.30.2

[PATCH nftables 2/4] optimize: merge verdict maps with same lookup key

[Pablo Neira Ayuso]

Merge two consecutive verdict maps with the same lookup key.

For instance, merge the following:

 table inet x {
        chain filter_in_tcp {
                tcp dport vmap {
                           80 : accept,
                           81 : accept,
                          443 : accept,
                          931 : accept,
                         5001 : accept,
                         5201 : accept,
                }
                tcp dport vmap {
                         6800-6999  : accept,
                        33434-33499 : accept,
                }
        }
 }

into:

 table inet x {
        chain filter_in_tcp {
                tcp dport vmap {
                           80 : accept,
                           81 : accept,
                          443 : accept,
                          931 : accept,
                         5001 : accept,
                         5201 : accept,
                         6800-6999  : accept,
                        33434-33499 : accept,
                }
	}
 }

This patch updates statement comparison routine to inspect the verdict
expression type to detect possible merger.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/optimize.c                                | 105 ++++++++++++++++--
 .../optimizations/dumps/merge_vmaps.nft       |  12 ++
 .../shell/testcases/optimizations/merge_vmaps |  25 +++++
 3 files changed, 130 insertions(+), 12 deletions(-)
 create mode 100644 tests/shell/testcases/optimizations/dumps/merge_vmaps.nft
 create mode 100755 tests/shell/testcases/optimizations/merge_vmaps

diff --git a/src/optimize.c b/src/optimize.c
index c52966a86e2c..9a93e3b8d296 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -101,6 +101,15 @@ static bool __stmt_type_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)
 	case STMT_NOTRACK:
 		break;
 	case STMT_VERDICT:
+		expr_a = stmt_a->expr;
+		expr_b = stmt_b->expr;
+
+		if (expr_a->etype != expr_b->etype)
+			return false;
+
+		if (expr_a->etype == EXPR_MAP &&
+		    expr_b->etype == EXPR_MAP)
+			return __expr_cmp(expr_a->map, expr_b->map);
 		break;
 	case STMT_LIMIT:
 		if (stmt_a->limit.rate != stmt_b->limit.rate ||
@@ -139,14 +148,8 @@ static bool __stmt_type_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)
 	return true;
 }
 
-static bool stmt_verdict_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)
+static bool expr_verdict_eq(const struct expr *expr_a, const struct expr *expr_b)
 {
-	struct expr *expr_a, *expr_b;
-
-	assert (stmt_a->ops->type == STMT_VERDICT);
-
-	expr_a = stmt_a->expr;
-	expr_b = stmt_b->expr;
 	if (expr_a->verdict != expr_b->verdict)
 		return false;
 	if (expr_a->chain && expr_b->chain) {
@@ -162,6 +165,25 @@ static bool stmt_verdict_eq(const struct stmt *stmt_a, const struct stmt *stmt_b
 	return true;
 }
 
+static bool stmt_verdict_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)
+{
+	struct expr *expr_a, *expr_b;
+
+	assert (stmt_a->ops->type == STMT_VERDICT);
+
+	expr_a = stmt_a->expr;
+	expr_b = stmt_b->expr;
+	if (expr_a->etype == EXPR_VERDICT &&
+	    expr_b->etype == EXPR_VERDICT)
+		return expr_verdict_eq(expr_a, expr_b);
+
+	if (expr_a->etype == EXPR_MAP &&
+	    expr_b->etype == EXPR_MAP)
+		return __expr_cmp(expr_a->map, expr_b->map);
+
+	return false;
+}
+
 static bool stmt_type_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)
 {
 	if (!stmt_a && !stmt_b)
@@ -194,6 +216,10 @@ static int rule_collect_stmts(struct optimize_ctx *ctx, struct rule *rule)
 		if (stmt_type_find(ctx, stmt))
 			continue;
 
+		if (stmt->ops->type == STMT_VERDICT &&
+		    stmt->expr->etype == EXPR_MAP)
+			continue;
+
 		/* No refcounter available in statement objects, clone it to
 		 * to store in the array of selectors.
 		 */
@@ -273,16 +299,15 @@ struct merge {
 	uint32_t	num_stmts;
 };
 
-static void merge_stmts(const struct optimize_ctx *ctx,
-			uint32_t from, uint32_t to, const struct merge *merge)
+static void merge_expr_stmts(const struct optimize_ctx *ctx,
+			     uint32_t from, uint32_t to,
+			     const struct merge *merge,
+			     struct stmt *stmt_a)
 {
-	struct stmt *stmt_a = ctx->stmt_matrix[from][merge->stmt[0]];
 	struct expr *expr_a, *expr_b, *set, *elem;
 	struct stmt *stmt_b;
 	uint32_t i;
 
-	assert (stmt_a->ops->type == STMT_EXPRESSION);
-
 	set = set_expr_alloc(&internal_location, NULL);
 	set->set_flags |= NFT_SET_ANONYMOUS;
 
@@ -301,6 +326,62 @@ static void merge_stmts(const struct optimize_ctx *ctx,
 	stmt_a->expr->right = set;
 }
 
+static void merge_vmap(const struct optimize_ctx *ctx,
+		       struct stmt *stmt_a, const struct stmt *stmt_b)
+{
+	struct expr *mappings, *mapping, *expr;
+
+	mappings = stmt_b->expr->mappings;
+	list_for_each_entry(expr, &mappings->expressions, list) {
+		mapping = expr_clone(expr);
+		compound_expr_add(stmt_a->expr->mappings, mapping);
+	}
+}
+
+static void merge_verdict_stmts(const struct optimize_ctx *ctx,
+				uint32_t from, uint32_t to,
+				const struct merge *merge,
+				struct stmt *stmt_a)
+{
+	struct stmt *stmt_b;
+	uint32_t i;
+
+	for (i = from + 1; i <= to; i++) {
+		stmt_b = ctx->stmt_matrix[i][merge->stmt[0]];
+		switch (stmt_b->ops->type) {
+		case STMT_VERDICT:
+			switch (stmt_b->expr->etype) {
+			case EXPR_MAP:
+				merge_vmap(ctx, stmt_a, stmt_b);
+				break;
+			default:
+				assert(1);
+			}
+			break;
+		default:
+			assert(1);
+			break;
+		}
+	}
+}
+
+static void merge_stmts(const struct optimize_ctx *ctx,
+			uint32_t from, uint32_t to, const struct merge *merge)
+{
+	struct stmt *stmt_a = ctx->stmt_matrix[from][merge->stmt[0]];
+
+	switch (stmt_a->ops->type) {
+	case STMT_EXPRESSION:
+		merge_expr_stmts(ctx, from, to, merge, stmt_a);
+		break;
+	case STMT_VERDICT:
+		merge_verdict_stmts(ctx, from, to, merge, stmt_a);
+		break;
+	default:
+		assert(1);
+	}
+}
+
 static void merge_concat_stmts(const struct optimize_ctx *ctx,
 			       uint32_t from, uint32_t to,
 			       const struct merge *merge)
diff --git a/tests/shell/testcases/optimizations/dumps/merge_vmaps.nft b/tests/shell/testcases/optimizations/dumps/merge_vmaps.nft
new file mode 100644
index 000000000000..c1c9743b9f8c
--- /dev/null
+++ b/tests/shell/testcases/optimizations/dumps/merge_vmaps.nft
@@ -0,0 +1,12 @@
+table ip x {
+	chain filter_in_tcp {
+	}
+
+	chain filter_in_udp {
+	}
+
+	chain y {
+		tcp dport vmap { 80 : accept, 81 : accept, 443 : accept, 8000-8100 : accept, 24000-25000 : accept }
+		meta l4proto vmap { tcp : goto filter_in_tcp, udp : goto filter_in_udp }
+	}
+}
diff --git a/tests/shell/testcases/optimizations/merge_vmaps b/tests/shell/testcases/optimizations/merge_vmaps
new file mode 100755
index 000000000000..7b7a2723be4b
--- /dev/null
+++ b/tests/shell/testcases/optimizations/merge_vmaps
@@ -0,0 +1,25 @@
+#!/bin/bash
+
+set -e
+
+RULESET="table ip x {
+	chain filter_in_tcp {
+	}
+	chain filter_in_udp {
+	}
+	chain y {
+		tcp dport vmap {
+			80 : accept,
+			81 : accept,
+			443 : accept,
+		}
+		tcp dport vmap {
+			8000-8100 : accept,
+			24000-25000 : accept,
+		}
+		meta l4proto tcp goto filter_in_tcp
+		meta l4proto udp goto filter_in_udp
+	}
+}"
+
+$NFT -o -f - <<< $RULESET
-- 
2.30.2

[PATCH nftables 3/4] optimize: check for payload base and offset when searching for mergers

[Pablo Neira Ayuso]

Extend the existing checks to cover the payload base and offset.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/optimize.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/src/optimize.c b/src/optimize.c
index 9a93e3b8d296..5882f3bd005d 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -40,6 +40,10 @@ static bool __expr_cmp(const struct expr *expr_a, const struct expr *expr_b)
 
 	switch (expr_a->etype) {
 	case EXPR_PAYLOAD:
+		if (expr_a->payload.base != expr_b->payload.base)
+			return false;
+		if (expr_a->payload.offset != expr_b->payload.offset)
+			return false;
 		if (expr_a->payload.desc != expr_b->payload.desc)
 			return false;
 		if (expr_a->payload.tmpl != expr_b->payload.tmpl)
-- 
2.30.2

[PATCH nftables 4/4] optimize: do not merge raw payload expressions

[Pablo Neira Ayuso]

Merging raw expressions results in a valid concatenation which throws:

 Error: can not use variable sized data types (integer) in concat expressions

Disable merging raw expressions until this is supported by skipping raw
expressions.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/optimize.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/src/optimize.c b/src/optimize.c
index 5882f3bd005d..04523edb795b 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -40,6 +40,9 @@ static bool __expr_cmp(const struct expr *expr_a, const struct expr *expr_b)
 
 	switch (expr_a->etype) {
 	case EXPR_PAYLOAD:
+		/* disable until concatenation with integer works. */
+		if (expr_a->payload.is_raw || expr_b->payload.is_raw)
+			return false;
 		if (expr_a->payload.base != expr_b->payload.base)
 			return false;
 		if (expr_a->payload.offset != expr_b->payload.offset)
-- 
2.30.2