optimization updates
Pablo Neira Ayuso
maintainerPATCH 1/4 optimize: add __expr_cmp()
In reply to Pablo Neira AyusoAdd 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
@@ -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
Pablo Neira Ayuso
maintainercover 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
Pablo Neira Ayuso
maintainerPATCH 3/4 optimize: check for payload base and offset when searching for mergers
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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 2/4 optimize: merge verdict maps with same lookup key
In reply to Pablo Neira AyusoMerge 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
@@ -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_breturn 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
@@ -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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 4/4 optimize: do not merge raw payload expressions
In reply to Pablo Neira AyusoMerging 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
@@ -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