ruleset optimization infrastructure
Pablo Neira Ayuso
maintainercover ruleset optimization infrastructure
Hi,
This patchset adds a new -o/--optimize option to enable ruleset optimization.
The ruleset optimization first loads the ruleset in "dry run" mode to validate that the original ruleset is correct. Then, on a second pass it performs the ruleset optimization before adding the rules into the kernel.
This infrastructure collects the statements that are used in rules. Then, it builds a matrix of rules vs. statements. Then, it looks for common statements in consecutive rules that are candidate to be merged. Finally, it merges rules.
From libnftables perspective, there is a new API to enable this feature:
bool nft_ctx_get_optimize(struct nft_ctx *ctx); void nft_ctx_set_optimize(struct nft_ctx *ctx, bool optimize);
This patchset adds support for three optimizations:
1) Collapse rules matching on a single selector into a set, which transforms:
ip daddr 192.168.0.1 counter accept
ip daddr 192.168.0.2 counter accept
ip daddr 192.168.0.3 counter accept
into:
ip daddr { 192.168.0.1, 192.168.0.2, 192.168.0.3 } counter packets 0 bytes 0 accept
2) Collapse rules with the same selectors into a concatenation, which transforms:
meta iifname eth1 ip saddr 1.1.1.1 ip daddr 2.2.2.3 accept meta iifname eth1 ip saddr 1.1.1.2 ip daddr 2.2.2.5 accept meta iifname eth2 ip saddr 1.1.1.3 ip daddr 2.2.2.6 accept
into:
meta iifname . ip saddr . ip daddr { eth1 . 1.1.1.1 . 2.2.2.6, eth1 . 1.1.1.2 . 2.2.2.5 , eth1 . 1.1.1.3 . 2.2.2.6 } accept
3) Collapse rules with same selector but different verdic into verdict map, which transforms:
ct state invalid drop
ct state established,related accept
into:
ct state vmap { established : accept, related : accept, invalid : drop }
Comments welcome,
Thanks.
Pablo Neira Ayuso (3):
src: add ruleset optimization infrastructure
optimize: merge rules with same selectors into a concatenation
optimize: merge same selector with different verdict into verdict map
include/nftables.h | 4 + include/nftables/libnftables.h | 5 + src/Makefile.am | 1 + src/libnftables.c | 41 ++- src/libnftables.map | 5 + src/main.c | 9 +- src/optimize.c | 524 +++++++++++++++++++++++++++++++++ 7 files changed, 586 insertions(+), 3 deletions(-) create mode 100644 src/optimize.c
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 1/3 src: add ruleset optimization infrastructure
This patch adds a new -o/--optimize option to enable ruleset optimization. From libnftables perspective, there is a new API to enable this feature:
bool nft_ctx_get_optimize(struct nft_ctx *ctx); void nft_ctx_set_optimize(struct nft_ctx *ctx, bool optimize);
The ruleset optimization first loads the ruleset in "dry run" mode to validate that the original ruleset is correct. Then, on a second pass it performs the ruleset optimization before adding the rules into the kernel.
This infrastructure collects the statements that are used in rules, then it builds a matrix of rules vs. statements. Then, look for common statements in consecutive rules. Finally, merge rules.
This patch adds support for the first optimization: Collapse a linear list of rules matching on a single selector into a set, which transforms:
ip daddr 192.168.0.1 counter accept
ip daddr 192.168.0.2 counter accept
ip daddr 192.168.0.3 counter accept
into:
ip daddr { 192.168.0.1, 192.168.0.2, 192.168.0.3 } counter packets 0 bytes 0 accept
--- include/nftables.h | 4 + include/nftables/libnftables.h | 5 + src/Makefile.am | 1 + src/libnftables.c | 41 +++- src/libnftables.map | 5 + src/main.c | 9 +- src/optimize.c | 377 +++++++++++++++++++++++++++++++++ 7 files changed, 439 insertions(+), 3 deletions(-) create mode 100644 src/optimize.c
include/nftables.h +4 -0
@@ -121,6 +121,7 @@ struct nft_ctx {unsigned int debug_mask;struct output_ctx output;bool check; +bool optimize;struct nft_cache cache;uint32_t flags;struct parser_state *state;
@@ -222,6 +223,9 @@ int nft_print(struct output_ctx *octx, const char *fmt, ...)int nft_gmp_print (struct output_ctx *octx,const char *fmt, ...) __attribute__((format (printf,2 ,0 ))); +int nft_optimize (struct nft_ctx *nft,struct list_head *cmds, +struct list_head *msgs); +#define __NFT_OUTPUT_NOTSUPP UINT_MAX#endif /* NFTABLES_NFTABLES_H */
include/nftables/libnftables.h +5 -0
@@ -41,6 +41,9 @@ void nft_ctx_free(struct nft_ctx *ctx);bool nft_ctx_get_dry_run (struct nft_ctx *ctx);void nft_ctx_set_dry_run (struct nft_ctx *ctx,bool dry); +bool nft_ctx_get_optimize (struct nft_ctx *ctx); +void nft_ctx_set_optimize (struct nft_ctx *ctx,bool optimize); +enum {NFT_CTX_OUTPUT_REVERSEDNS = (1 <<0 ),NFT_CTX_OUTPUT_SERVICE = (1 <<1 ),
@@ -85,6 +88,8 @@ void nft_ctx_clear_vars(struct nft_ctx *ctx);int nft_run_cmd_from_buffer (struct nft_ctx *nft,const char *buf);int nft_run_cmd_from_filename (struct nft_ctx *nft,const char *filename); +int nft_optimize_from_filename (struct nft_ctx *nft,const char *filename); + #ifdef __cplusplus }/* extern "C" */ #endif
src/Makefile.am +1 -0
@@ -70,6 +70,7 @@ libnftables_la_SOURCES = \ mnl.c \ iface.c \ mergesort.c \ + optimize.c \ osf.c \ nfnl_osf.c \ tcpopt.c \
src/libnftables.c +39 -2
62 lines not on this page · raw message
src/libnftables.map +5 -0
@@ -28,3 +28,8 @@ LIBNFTABLES_2 { nft_ctx_add_var; nft_ctx_clear_vars; } LIBNFTABLES_1; + +LIBNFTABLES_3 { + nft_set_optimize; + nft_get_optimize; +} LIBNFTABLES_2;
src/main.c +8 -1
@@ -36,7 +36,8 @@ enum opt_indices {IDX_INTERACTIVE ,IDX_INCLUDEPATH ,IDX_CHECK , -#define IDX_RULESET_INPUT_END IDX_CHECK +IDX_OPTIMIZE , +#define IDX_RULESET_INPUT_END IDX_OPTIMIZE /* Ruleset list formatting */ IDX_HANDLE,#define IDX_RULESET_LIST_START IDX_HANDLE
@@ -80,6 +81,7 @@ enum opt_vals {OPT_NUMERIC_PROTO ='p' ,OPT_NUMERIC_TIME ='T' ,OPT_TERSE ='t' , +OPT_OPTIMIZE ='o' , OPT_INVALID = '?', };
@@ -136,6 +138,8 @@ static const struct nft_opt nft_options[] = { "Format output in JSON"), [IDX_DEBUG ] =NFT_OPT ("debug" ,OPT_DEBUG ,"<level [,level...]>" , "Specify debugging level (scanner, parser, eval, netlink, mnl, proto-ctx, segtree, all)"), + [IDX_OPTIMIZE ] =NFT_OPT ("optimize" ,OPT_OPTIMIZE ,NULL , + "Optimize ruleset"), };#define NR_NFT_OPTIONS (sizeof(nft_options) / sizeof(nft_options[0]))
@@ -484,6 +488,9 @@ int main(int argc, char * const *argv)case OPT_TERSE : output_flags |=NFT_CTX_OUTPUT_TERSE ;break ; +case OPT_OPTIMIZE : +nft_ctx_set_optimize (nft, true); +break ;case OPT_INVALID :exit (EXIT_FAILURE ); }
src/optimize.c new file +377 -0
377 lines not on this page · raw message
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 2/3 optimize: merge rules with same selectors into a concatenation
In reply to Pablo Neira AyusoThis patch extends the ruleset optimization infrastructure to collapse several rules with the same selectors into a concatenation.
Transform:
meta iifname eth1 ip saddr 1.1.1.1 ip daddr 2.2.2.3 accept meta iifname eth1 ip saddr 1.1.1.2 ip daddr 2.2.2.5 accept meta iifname eth2 ip saddr 1.1.1.3 ip daddr 2.2.2.6 accept
into:
meta iifname . ip saddr . ip daddr { eth1 . 1.1.1.1 . 2.2.2.6, eth1 . 1.1.1.2 . 2.2.2.5 , eth1 . 1.1.1.3 . 2.2.2.6 } accept
--- src/optimize.c | 43 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 42 insertions(+), 1 deletion(-)
src/optimize.c +42 -1
@@ -217,6 +217,47 @@ static void merge_stmts(const struct optimize_ctx *ctx, stmt_a->expr->right = set; } +static void merge_multi_stmts (const struct optimize_ctx *ctx, +uint32_t from,uint32_t to, +const struct merge *merge) +{ +struct expr *concat, *expr, *elem; +struct stmt *stmt, *stmt_a; +uint32_t i, k; + + stmt = ctx->stmt_matrix[from][merge->stmt[0 ]]; +/* build concatenation of selectors, eg. ifname . ip daddr . tcp dport */ + concat =concat_expr_alloc (&internal_location); + +for (k =0 ; k < merge->num_stmts; k++) { + stmt_a = ctx->stmt_matrix[from][merge->stmt[k]]; +compound_expr_add (concat,expr_get (stmt_a->expr->left)); + } +expr_free (stmt->expr->left); + stmt->expr->left = concat; + +/* build set data contenation, eg. { eth0 . 1.1.1.1 . 22 } */ + expr =set_expr_alloc (&internal_location,NULL ); + +for (i = from; i <= to; i++) { + concat =concat_expr_alloc (&internal_location); +for (k =0 ; k < merge->num_stmts; k++) { + stmt_a = ctx->stmt_matrix[i][merge->stmt[k]]; +compound_expr_add (concat,expr_get (stmt_a->expr->right)); + } + elem =set_elem_expr_alloc (&internal_location, concat); +compound_expr_add (expr, elem); + } +expr_free (stmt->expr->right); + stmt->expr->right = expr; + +for (k =1 ; k < merge->num_stmts; k++) { + stmt_a = ctx->stmt_matrix[from][merge->stmt[k]]; +list_del (&stmt_a->list); +stmt_free (stmt_a); + } +} +static void merge_rules (const struct optimize_ctx *ctx,uint32_t from,uint32_t to,const struct merge *merge)
@@ -224,7 +265,7 @@ static void merge_rules(const struct optimize_ctx *ctx,uint32_t x;if (merge->num_stmts >1 ) { -return ; +merge_multi_stmts (ctx, from, to, merge); }else {merge_stmts (ctx, from, to, merge); }
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 3/3 optimize: merge same selector with different verdict into verdict map
In reply to Pablo Neira AyusoTransform:
ct state invalid drop
ct state established,related accept
into:
ct state vmap { established : accept, related : accept, invalid : drop }
--- src/optimize.c | 142 ++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 124 insertions(+), 18 deletions(-)
src/optimize.c +124 -18
@@ -96,19 +96,6 @@ static bool __stmt_type_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)case STMT_COUNTER :break ;case 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) { -if (expr_a->chain->etype != expr_b->chain->etype) -return false; -if (expr_a->chain->etype ==EXPR_VALUE && -strcmp (expr_a->chain->identifier, expr_b->chain->identifier)) -return false; - }else if (expr_a->chain || expr_b->chain) { -return false; - }break ;default :break ;
@@ -117,6 +104,29 @@ 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) +{ +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) { +if (expr_a->chain->etype != expr_b->chain->etype) +return false; +if (expr_a->chain->etype ==EXPR_VALUE && +strcmp (expr_a->chain->identifier, expr_b->chain->identifier)) +return false; + }else if (expr_a->chain || expr_b->chain) { +return false; + } + +return true; +} +static bool stmt_type_eq (const struct stmt *stmt_a,const struct stmt *stmt_b) {if (!stmt_a && !stmt_b)
@@ -182,6 +192,20 @@ static void rule_build_stmt_matrix_stmts(struct optimize_ctx *ctx, ctx->rule[(*i)++] = rule; } +static int stmt_verdict_find (const struct optimize_ctx *ctx) +{ +uint32_t i; + +for (i =0 ; i < ctx->num_stmts; i++) { +if (ctx->stmt[i]->ops->type !=STMT_VERDICT ) +continue ; + +return i; + } + +return -1 ; +} +struct merge {/* interval of rules to be merged */ uint32_t rule_from;
@@ -197,7 +221,7 @@ static void merge_stmts(const struct optimize_ctx *ctx,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 x; +uint32_t i;assert (stmt_a->ops->type ==STMT_EXPRESSION );
@@ -206,8 +230,8 @@ static void merge_stmts(const struct optimize_ctx *ctx, elem =set_elem_expr_alloc (&internal_location,expr_get (expr_a));compound_expr_add (set, elem); -for (x = from +1 ; x <= to; x++) { - stmt_b = ctx->stmt_matrix[x][merge->stmt[0 ]]; +for (i = from +1 ; i <= to; i++) { + stmt_b = ctx->stmt_matrix[i][merge->stmt[0 ]]; expr_b = stmt_b->expr->right; elem =set_elem_expr_alloc (&internal_location,expr_get (expr_b));compound_expr_add (set, elem);
@@ -258,16 +282,98 @@ static void merge_multi_stmts(const struct optimize_ctx *ctx, } } +static void build_verdict_map (struct expr *expr,struct stmt *verdict,struct expr *set) +{ +struct expr *item, *elem, *mapping; + +if (expr->etype ==EXPR_LIST ) { +list_for_each_entry (item, &expr->expressions, list) { + elem =set_elem_expr_alloc (&internal_location,expr_get (item)); + mapping =mapping_expr_alloc (&internal_location, elem, +expr_get (verdict->expr)); +compound_expr_add (set, mapping); + } + }else { + elem =set_elem_expr_alloc (&internal_location,expr_get (expr)); + mapping =mapping_expr_alloc (&internal_location, elem, +expr_get (verdict->expr)); +compound_expr_add (set, mapping); + } +} + +static void merge_stmts_vmap (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 ]]; +struct stmt *stmt_b, *verdict_a, *verdict_b, *stmt; +struct expr *expr_a, *expr_b, *expr, *left, *set; +uint32_t i, k; + + k =stmt_verdict_find (ctx); +assert (k >=0 ); + + verdict_a = ctx->stmt_matrix[from][k]; + expr_a = stmt_a->expr->right; + set =set_expr_alloc (&internal_location,NULL ); + +build_verdict_map (expr_a, verdict_a, set); +for (i = from +1 ; i <= to; i++) { + stmt_b = ctx->stmt_matrix[i][merge->stmt[0 ]]; + expr_b = stmt_b->expr->right; + verdict_b = ctx->stmt_matrix[i][k]; + +build_verdict_map (expr_b, verdict_b, set); + } + + left =expr_get (stmt_a->expr->left); + expr =map_expr_alloc (&internal_location, left, set); + stmt =verdict_stmt_alloc (&internal_location, expr); + +list_add (&stmt->list, &stmt_a->list); +list_del (&stmt_a->list); +stmt_free (stmt_a); +list_del (&verdict_a->list); +stmt_free (verdict_a); +} + +static bool stmt_verdict_cmp (const struct optimize_ctx *ctx, +uint32_t from,uint32_t to) +{ +struct stmt *stmt_a, *stmt_b; +uint32_t k, i; + + k =stmt_verdict_find (ctx); +if (k <0 ) +return true; + +for (i = from; i +1 <= to; i++) { + stmt_a = ctx->stmt_matrix[i][k]; + stmt_b = ctx->stmt_matrix[i +1 ][k]; +if (!stmt_verdict_eq (stmt_a, stmt_b)) +return false; + } + +return true; +} +static void merge_rules (const struct optimize_ctx *ctx,uint32_t from,uint32_t to,const struct merge *merge) { +bool same_verdict;uint32_t x; + same_verdict =stmt_verdict_cmp (ctx, from, to); +if (merge->num_stmts >1 ) { -merge_multi_stmts (ctx, from, to, merge); +if (same_verdict) +merge_multi_stmts (ctx, from, to, merge); }else { -merge_stmts (ctx, from, to, merge); +if (same_verdict) +merge_stmts (ctx, from, to, merge); +else +merge_stmts_vmap (ctx, from, to, merge); }for (x = from +1 ; x <= to; x++) {list_del (&ctx->rule[x]->list);
Signature · 1 line
2.30.2
Quoted 5 lines · Pablo Neira Ayuso
Hi,
This patchset adds a new -o/--optimize option to enable ruleset optimization.
Thanks for working on this. From what I see in the community, this feature will be of high value to some folks: users often struggle with doing this kind of optimizations by hand.
Quoted 5 lines
The ruleset optimization first loads the ruleset in "dry run" mode to validate that the original ruleset is correct. Then, on a second pass it performs the ruleset optimization before adding the rules into the kernel.
Could you please describe how to work with this if all I want is to check how an optimized version of my ruleset would look like, but not load it into the kernel?
The use case would be: I just need a diff between my ruleset.nft file and whatever the optimized version would be, without performing any actual change.
Of course this can be added later on if not supported in this patch.
Quoted 4 lines
This infrastructure collects the statements that are used in rules. Then, it builds a matrix of rules vs. statements. Then, it looks for common statements in consecutive rules that are candidate to be merged. Finally, it merges rules.
clever!
Is this infra extensible enough to support scanning non-adjacent rules in the future?
ie, being able to transform:
* ip daddr 1.1.1.1 counter accept
* tcp dport 80 accept
* ip daddr 2.2.2.2 counter accept
into:
* ip daddr { 1.1.1., 2.2.2.2 } counter accept
* tcp dport 80 accept
Pablo Neira Ayuso
maintainerHi Arturo,
Quoted 17 lines · Arturo Borrero Gonzalez
Quoted 5 lines · Pablo Neira Ayuso
Hi,
This patchset adds a new -o/--optimize option to enable ruleset optimization.
Thanks for working on this. From what I see in the community, this feature will be of high value to some folks: users often struggle with doing this kind of optimizations by hand.
Quoted 5 lines
The ruleset optimization first loads the ruleset in "dry run" mode to validate that the original ruleset is correct. Then, on a second pass it performs the ruleset optimization before adding the rules into the kernel.
Quoted 7 lines
Could you please describe how to work with this if all I want is to check how an optimized version of my ruleset would look like, but not load it into the kernel?
The use case would be: I just need a diff between my ruleset.nft file and whatever the optimized version would be, without performing any actual change.
This is feasible. I could probably add a flags field instead of simple boolean to the API so it is possible to specify an option such as:
# nft -o offline -f ruleset.nft
which would print the ruleset listing without loading it.
Quoted 11 lines
Of course this can be added later on if not supported in this patch.
Quoted 4 lines
This infrastructure collects the statements that are used in rules. Then, it builds a matrix of rules vs. statements. Then, it looks for common statements in consecutive rules that are candidate to be merged. Finally, it merges rules.
clever!
Is this infra extensible enough to support scanning non-adjacent rules in the future?
This requires another step to group rules with the same statements whenever possible, such routine would need to make sure that the rule verdict is the same and that no stateful statements (eg. limit) is used.
Quoted 10 lines
ie, being able to transform:
* ip daddr 1.1.1.1 counter accept
* tcp dport 80 accept
* ip daddr 2.2.2.2 counter acceptinto:
* ip daddr { 1.1.1.1, 2.2.2.2 } counter accept
* tcp dport 80 accept
or even this:
* ip daddr . tcp dport { 1.1.1.1 . 0-65535, 2.2.2.2 . 0-65535, 0.0.0.0/0 . 80 } counter accept
but this requires a Linux kernel >= 5.6.
There are a few more transformations that come to my mind, such as packing several snat/dnat rules into a map.
I'll be posting v2 of this patchset with many fixes and tests soon.