Skip to contentSkip to conversation

optimization updates

PATCH New Pablo Neira Ayuso 1 participant 5 messages Jan 26, 2022 netfilter

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

cover optimization updates

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
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

PATCH 1/4 optimize: add __expr_cmp()

Add helper function to compare expression to allow for reuse.

---
 src/optimize.c | 98 ++++++++++++++++++++++++++------------------------
 1 file changed, 52 insertions(+), 46 deletions(-)
src/optimize.c +52 -46
index b5fb2c4179d0..c52966a86e2c 100644
@@ -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;
Signature · 1 line
2.30.2
author maintainer
#2 lore raw

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

In reply to 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.

---
 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
src/optimize.c +93 -12
index c52966a86e2c..9a93e3b8d296 100644
@@ -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)
tests/shell/testcases/optimizations/dumps/merge_vmaps.nft new file +12 -0
new file mode 100644
index 000000000000..c1c9743b9f8c
@@ -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 }
+	}
+}
tests/shell/testcases/optimizations/merge_vmaps new file +25 -0
new file mode 100755
index 000000000000..7b7a2723be4b
@@ -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
Signature · 1 line
2.30.2
author maintainer
#3 lore raw

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

In reply to Pablo Neira Ayuso

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

---
 src/optimize.c | 4 ++++
 1 file changed, 4 insertions(+)
src/optimize.c +4 -0
index 9a93e3b8d296..5882f3bd005d 100644
@@ -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)
Signature · 1 line
2.30.2
author maintainer
#4 lore raw

PATCH 4/4 optimize: do not merge raw payload expressions

In reply to 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.

---
 src/optimize.c | 3 +++
 1 file changed, 3 insertions(+)
src/optimize.c +3 -0
index 5882f3bd005d..04523edb795b 100644
@@ -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)
Signature · 1 line
2.30.2