split parse and evaluation phase to simplify cache logic
Pablo Neira Ayuso
maintainercover split parse and evaluation phase to simplify cache logic
Hi,
There are a myriad of cache_update() calls all over the evaluation phase that are required because the parser invokes the evaluation per command.
This complicates the cache logic, since nft may have to invalid a partial cache to upgrade to a full cache from one command to another. This forces nft to go back re-evaluate the existing batch that is being processed, this overly complicates things because the number of scenarios that trigger cache updates explode. This will get even more complicated once we do proper cache generation and ERESTART support is added - which is still missing.
This patchset aims to simplify cache logic by performing one single cache_update() before the evaluation phase, the idea is to iterate over the existing commands that come from the parser to do a cache_evaluate() call that calculates what cache nft needs to dump from the kernel (either partial or full, actually we have more degress of completeness, not just these two only). Then, with the proper cache in place, the evaluation happens.
This patchset revisits the existing design to address this problem:
1) Dynamically allocate input_descriptor object, this allows error reporting from the evaluation phase to access file location that was only available from the parser phase.
2) Evaluate the ruleset once the parser is complete. So we have two independent phases.
3) The mixture of parsing + evaluation was introduced to display all errors, either from the parsing or the evaluation phases.
4) Make a single cache_update() call based on the new cache_evaluate() function that calculates the kernel dump that needs to be done before entering the evaluation phase.
Thanks.
Pablo Neira Ayuso (4):
src: dynamic input_descriptor allocation
src: perform evaluation after parsing
src: Display parser and evaluate errors in one shot
src: single cache_update() call to build cache before evaluation
include/nftables.h | 1 + include/parser.h | 4 +- include/rule.h | 1 + src/Makefile.am | 1 + src/cache.c | 123 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/erec.c | 35 +-------------- src/evaluate.c | 76 +-------------------------------- src/libnftables.c | 57 +++++++++++++++++++------ src/mnl.c | 8 +--- src/parser_bison.y | 28 ++---------- src/parser_json.c | 9 ---- src/rule.c | 18 +------- src/scanner.l | 63 ++++++++++++++++++--------- 13 files changed, 222 insertions(+), 202 deletions(-) create mode 100644 src/cache.c
Signature · 1 line
2.11.0
Pablo Neira Ayuso
maintainerPATCH 1/4 src: dynamic input_descriptor allocation
This patch introduces the input descriptor list, that stores the existing input descriptor objects. These objects are now dynamically allocated and release from scanner_destroy() path.
Follow up patches that decouple the parsing and the evaluation phases require this for error reporting as described by b14572f72aac ("erec:
Fix input descriptors for included files"), this patch partially reverts such partial.
--- include/nftables.h | 1 + include/parser.h | 3 ++- src/erec.c | 35 +----------------------------- src/parser_bison.y | 1 + src/scanner.l | 63 ++++++++++++++++++++++++++++++++++++------------------ 5 files changed, 47 insertions(+), 56 deletions(-)
include/nftables.h +1 -0
@@ -165,6 +165,7 @@ enum input_descriptor_types {* @line_offset: offset of the current line to the beginning */ struct input_descriptor { +struct list_head list;struct location location;enum input_descriptor_types type;const char *name;
include/parser.h +2 -1
@@ -15,8 +15,9 @@struct parser_state {struct input_descriptor *indesc; -struct input_descriptor indescs[MAX_INCLUDE_DEPTH ]; +struct input_descriptor *indescs[MAX_INCLUDE_DEPTH ];unsigned int indesc_idx; +struct list_head indesc_list;struct list_head *msgs;unsigned int nerrs;
src/erec.c +1 -34
@@ -34,50 +34,17 @@ static const char * const error_record_names[] = { [EREC_ERROR] = "Error" }; -static void input_descriptor_destroy (const struct input_descriptor *indesc) -{ -if (indesc->location.indesc && - indesc->location.indesc->type !=INDESC_INTERNAL ) { -input_descriptor_destroy (indesc->location.indesc); - } -if (indesc->name) -xfree (indesc->name); -xfree (indesc); -} - -static struct input_descriptor *input_descriptor_dup (const struct input_descriptor *indesc) -{ -struct input_descriptor *dup_indesc; - - dup_indesc =xmalloc (sizeof (struct input_descriptor )); - *dup_indesc = *indesc; - -if (indesc->location.indesc && - indesc->location.indesc->type !=INDESC_INTERNAL ) - dup_indesc->location.indesc =input_descriptor_dup (indesc->location.indesc); - -if (indesc->name) - dup_indesc->name =xstrdup (indesc->name); - -return dup_indesc; -} -void erec_add_location (struct error_record *erec,const struct location *loc) {assert (erec->num_locations <EREC_LOCATIONS_MAX ); erec->locations[erec->num_locations] = *loc; - erec->locations[erec->num_locations].indesc =input_descriptor_dup (loc->indesc); + erec->locations[erec->num_locations].indesc = loc->indesc; erec->num_locations++; }void erec_destroy (struct error_record *erec) { -unsigned int i; -xfree (erec->msg); -for (i =0 ; i < erec->num_locations; i++) { -input_descriptor_destroy (erec->locations[i].indesc); - }xfree (erec); }
src/parser_bison.y +1 -0
@@ -50,6 +50,7 @@ void parser_init(struct nft_ctx *nft, struct parser_state *state, state->scopes[0] = scope_init(&state->top_scope, NULL); state->ectx.nft = nft; state->ectx.msgs = msgs; + init_list_head(&state->indesc_list); } static void yyerror(struct location *loc, struct nft_ctx *nft, void *scanner,
src/scanner.l +42 -21
123 lines not on this page · raw message
Signature · 1 line
2.11.0
Pablo Neira Ayuso
maintainerPATCH 2/4 src: perform evaluation after parsing
In reply to Pablo Neira AyusoSince 61236968b7a1 ("parser: evaluate commands immediately after parsing"), evaluation is invoked from the parsing phase in order to improve error reporting.
However, this approach is problematic from the cache perspective since we don't know if a full or partial netlink dump from the kernel is needed. If the number of objects in the kernel is significant, the netlink dump operation to build the cache may significantly slow down commands.
This patch moves the evaluation phase after the parsing phase as a preparation update to allow for a better strategy to build the cache.
--- include/parser.h | 1 - src/libnftables.c | 30 +++++++++++++++++++++++++----- src/parser_bison.y | 27 ++------------------------- 3 files changed, 27 insertions(+), 31 deletions(-)
include/parser.h +0 -1
@@ -27,7 +27,6 @@ struct parser_state {unsigned int scope;struct list_head *cmds; -struct eval_ctx ectx; };struct mnl_socket ;
src/libnftables.c +25 -5
@@ -348,7 +348,6 @@ static const struct input_descriptor indesc_cmdline = {static int nft_parse_bison_buffer (struct nft_ctx *nft,const char *buf,struct list_head *msgs,struct list_head *cmds) { -struct cmd *cmd;int ret;parser_init (nft, nft->state, msgs, cmds);
@@ -359,16 +358,12 @@ static int nft_parse_bison_buffer(struct nft_ctx *nft, const char *buf,if (ret !=0 || nft->state->nerrs >0 )return -1 ; -list_for_each_entry (cmd, cmds, list) -nft_cmd_expand (cmd); -return 0 ; }static int nft_parse_bison_filename (struct nft_ctx *nft,const char *filename,struct list_head *msgs,struct list_head *cmds) { -struct cmd *cmd;int ret;parser_init (nft, nft->state, msgs, cmds);
@@ -380,6 +375,23 @@ static int nft_parse_bison_filename(struct nft_ctx *nft, const char *filename,if (ret !=0 || nft->state->nerrs >0 )return -1 ; +return 0 ; +} + +static int nft_evaluate (struct nft_ctx *nft,struct list_head *msgs, +struct list_head *cmds) +{ +struct cmd *cmd; + +list_for_each_entry (cmd, cmds, list) { +struct eval_ctx ectx = { + .nft = nft, + .msgs = msgs, + }; +if (cmd_evaluate (&ectx, cmd) <0 ) +return -1 ; + } +list_for_each_entry (cmd, cmds, list)nft_cmd_expand (cmd);
@@ -404,6 +416,10 @@ int nft_run_cmd_from_buffer(struct nft_ctx *nft, const char *buf)if (rc) goto err; + rc =nft_evaluate (nft, &msgs, &cmds); +if (rc <0 ) + goto err; +if (nft_netlink (nft, &cmds, &msgs, nft->nf_sock) !=0 ) rc =-1 ; err:
@@ -448,6 +464,10 @@ int nft_run_cmd_from_filename(struct nft_ctx *nft, const char *filename)if (rc) goto err; + rc =nft_evaluate (nft, &msgs, &cmds); +if (rc <0 ) + goto err; +if (nft_netlink (nft, &cmds, &msgs, nft->nf_sock) !=0 ) rc =-1 ; err:
src/parser_bison.y +2 -25
@@ -48,8 +48,6 @@ void parser_init(struct nft_ctx *nft, struct parser_state *state, state->msgs = msgs; state->cmds = cmds; state->scopes[0] = scope_init(&state->top_scope, NULL); - state->ectx.nft = nft; - state->ectx.msgs = msgs; init_list_head(&state->indesc_list); }
@@ -792,17 +790,8 @@ input : /* empty */ | input line { if ($2 != NULL) { - LIST_HEAD(list); - $2->location = @2; - - list_add_tail(&$2->list, &list); - if (cmd_evaluate(&state->ectx, $2) < 0) { - cmd_free($2); - if (++state->nerrs == nft->parser_max_errors) - YYABORT; - } else - list_splice_tail(&list, state->cmds); + list_add_tail(&$2->list, state->cmds); } } ;
@@ -878,22 +867,10 @@ line : common_block { $$ = NULL; } * work. */ if ($1 != NULL) { - LIST_HEAD(list); - $1->location = @1; - - list_add_tail(&$1->list, &list); - if (cmd_evaluate(&state->ectx, $1) < 0) { - cmd_free($1); - if (++state->nerrs == nft->parser_max_errors) - YYABORT; - } else - list_splice_tail(&list, state->cmds); + list_add_tail(&$1->list, state->cmds); } - if (state->nerrs) - YYABORT; $$ = NULL; - YYACCEPT; } ;
Signature · 1 line
2.11.0
Pablo Neira Ayuso
maintainerPATCH 3/4 src: Display parser and evaluate errors in one shot
In reply to Pablo Neira AyusoThis patch restores 61236968b7a1 ("parser: evaluate commands immediately after parsing") following a different approach.
In this patch, the evaluation phase is done if the parsing phase fails, hence the user gets parsing and evaluation errors in one shot, which is the purpose of 61236968b7a1.
Note that evaluation errors are now shown after parser errors, the example available in 61236968b7a1 displays with this patch the following error:
# nft -f /tmp/bad.nft
/tmp/bad.nft:3:32-32: Error: syntax error, unexpected newline
add rule filter input tcp dport
^
/tmp/bad.nft:5:37-41: Error: syntax error, unexpected dport, expecting end of file or newline or semicolon
add rule filter input tcp dport tcp dport
^^^^^
/tmp/bad.nft:4:33-35: Error: datatype mismatch, expected internet network service, expression has type Internet protocol
add rule filter input tcp dport tcp
~~~~~~~~~ ^^^So evaluation pointing to line 4 happens after line error reporting generated by the parser that points to line 3, while 61236968b7a1 was showing errors per line in order. As a future work, we can sort the error reporting list to restore exactly the same behaviour.
--- src/libnftables.c | 22 ++++++++++++++++------ src/parser_json.c | 9 --------- 2 files changed, 16 insertions(+), 15 deletions(-)
src/libnftables.c +16 -6
@@ -400,11 +400,11 @@ static int nft_evaluate(struct nft_ctx *nft, struct list_head *msgs,int nft_run_cmd_from_buffer (struct nft_ctx *nft,const char *buf) { +int rc = -EINVAL , parser_rc;struct cmd *cmd, *next;LIST_HEAD (msgs);LIST_HEAD (cmds);char *nlbuf; -int rc = -EINVAL ; nlbuf =xzalloc (strlen (buf) +2 );sprintf (nlbuf,"%s\n" , buf);
@@ -413,13 +413,18 @@ int nft_run_cmd_from_buffer(struct nft_ctx *nft, const char *buf) rc =nft_parse_json_buffer (nft, nlbuf, &msgs, &cmds);if (rc == -EINVAL ) rc =nft_parse_bison_buffer (nft, nlbuf, &msgs, &cmds); -if (rc) - goto err; + + parser_rc = rc; rc =nft_evaluate (nft, &msgs, &cmds);if (rc <0 ) goto err; +if (parser_rc) { + rc = parser_rc; + goto err; + } +if (nft_netlink (nft, &cmds, &msgs, nft->nf_sock) !=0 ) rc =-1 ; err:
@@ -445,9 +450,9 @@ err:int nft_run_cmd_from_filename (struct nft_ctx *nft,const char *filename) {struct cmd *cmd, *next; +int rc, parser_rc;LIST_HEAD (msgs);LIST_HEAD (cmds); -int rc; rc =cache_update (nft,CMD_INVALID , &msgs);if (rc <0 )
@@ -461,13 +466,18 @@ int nft_run_cmd_from_filename(struct nft_ctx *nft, const char *filename) rc =nft_parse_json_filename (nft, filename, &msgs, &cmds);if (rc == -EINVAL ) rc =nft_parse_bison_filename (nft, filename, &msgs, &cmds); -if (rc) - goto err; + + parser_rc = rc; rc =nft_evaluate (nft, &msgs, &cmds);if (rc <0 ) goto err; +if (parser_rc) { + rc = parser_rc; + goto err; + } +if (nft_netlink (nft, &cmds, &msgs, nft->nf_sock) !=0 ) rc =-1 ; err:
src/parser_json.c +0 -9
@@ -3390,10 +3390,6 @@ static json_t *seqnum_to_json(const uint32_t seqnum)static int __json_parse (struct json_ctx *ctx) { -struct eval_ctx ectx = { - .nft = ctx->nft, - .msgs = ctx->msgs, - };json_t *tmp, *value;size_t index;
@@ -3435,11 +3431,6 @@ static int __json_parse(struct json_ctx *ctx)list_add_tail (&cmd->list, &list); -if (cmd_evaluate (&ectx, cmd) <0 ) { -cmd_free (cmd); -json_error (ctx,"Evaluating command at index %zd failed." , index); -return -1 ; - }list_splice_tail (&list, ctx->cmds);if (nft_output_echo (&ctx->nft->output))
Signature · 1 line
2.11.0
Pablo Neira Ayuso
maintainerPATCH 4/4 src: single cache_update() call to build cache before evaluation
In reply to Pablo Neira AyusoThis patch allows us to make one single cache_update() call. Thus, there is not need to rebuild an incomplete cache from the middle of the batch processing.
Note that nft_run_cmd_from_filename() does not need a full netlink dump to build the cache anymore, this should speed nft -f with incremental updates and very large rulesets.
cache_evaluate() calculates the netlink dump to populate the cache that this batch needs.
--- include/rule.h | 1 + src/Makefile.am | 1 + src/cache.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/evaluate.c | 76 +-------------------------------- src/libnftables.c | 9 ++-- src/mnl.c | 8 +--- src/rule.c | 18 +------- 7 files changed, 134 insertions(+), 102 deletions(-) create mode 100644 src/cache.c
include/rule.h +1 -0
@@ -631,6 +631,7 @@ extern struct error_record *rule_postprocess(struct rule *rule);struct netlink_ctx ;extern int do_command (struct netlink_ctx *ctx,struct cmd *cmd); +extern int cache_evaluate (struct nft_ctx *nft,struct list_head *cmds);extern int cache_update (struct nft_ctx *ctx,enum cmd_ops cmd,struct list_head *msgs); extern void cache_flush(struct nft_ctx *ctx, enum cmd_ops cmd,
src/Makefile.am +1 -0
@@ -31,6 +31,7 @@ lib_LTLIBRARIES = libnftables.la libnftables_la_SOURCES = \ rule.c \ statement.c \ + cache.c \ datatype.c \ expression.c \ evaluate.c \
src/cache.c new file +123 -0
123 lines not on this page · raw message
src/evaluate.c +1 -75
185 lines not on this page · raw message
src/libnftables.c +5 -4
@@ -381,8 +381,13 @@ static int nft_parse_bison_filename(struct nft_ctx *nft, const char *filename,static int nft_evaluate (struct nft_ctx *nft,struct list_head *msgs,struct list_head *cmds) { +unsigned int completeness;struct cmd *cmd; + completeness =cache_evaluate (nft, cmds); +if (cache_update (nft, completeness, msgs) <0 ) +return -1 ; +list_for_each_entry (cmd, cmds, list) {struct eval_ctx ectx = { .nft = nft,
@@ -454,10 +459,6 @@ int nft_run_cmd_from_filename(struct nft_ctx *nft, const char *filename)LIST_HEAD (msgs);LIST_HEAD (cmds); - rc =cache_update (nft,CMD_INVALID , &msgs); -if (rc <0 ) -return -1 ; -if (!strcmp (filename,"-" )) filename ="/dev/stdin" ;
src/mnl.c +1 -7
@@ -394,15 +394,9 @@ int mnl_nft_rule_replace(struct netlink_ctx *ctx, const struct cmd *cmd)unsigned int flags =0 ;struct nftnl_rule *nlr;struct nlmsghdr *nlh; -int err; - -if (nft_output_echo (&ctx->nft->output)) { - err =cache_update (ctx->nft,CMD_INVALID , ctx->msgs); -if (err <0 ) -return err; +if (nft_output_echo (&ctx->nft->output)) flags |=NLM_F_ECHO ; - } nlr =nftnl_rule_alloc ();if (!nlr)
src/rule.c +2 -16
@@ -1501,15 +1501,8 @@ static int do_command_add(struct netlink_ctx *ctx, struct cmd *cmd, bool excl) {uint32_t flags = excl ?NLM_F_EXCL :0 ; -if (nft_output_echo (&ctx->nft->output)) { -int ret; - - ret =cache_update (ctx->nft, cmd->obj, ctx->msgs); -if (ret <0 ) -return ret; - +if (nft_output_echo (&ctx->nft->output)) flags |=NLM_F_ECHO ; - }switch (cmd->obj) {case CMD_OBJ_TABLE :
@@ -1552,15 +1545,8 @@ static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd) {uint32_t flags =0 ; -if (nft_output_echo (&ctx->nft->output)) { -int ret; - - ret =cache_update (ctx->nft, cmd->obj, ctx->msgs); -if (ret <0 ) -return ret; - +if (nft_output_echo (&ctx->nft->output)) flags |=NLM_F_ECHO ; - }switch (cmd->obj) {case CMD_OBJ_RULE :
Signature · 1 line
2.11.0
Phil Sutter
reviewerRe: [PATCH nft 4/4] src: single cache_update() call to build cache before evaluation
Hi,
On Wed, Jun 05, 2019 at 06:46:52PM +0200, Pablo Neira Ayuso wrote:
[...]
Quoted 25 lines
src/cache.c new file +19
-0@@ -0,0 +1,123 @@ +/* +* Copyright (c) 2019 Pablo Neira Ayuso <[email protected]> +* +* This program is free software; you can redistribute it and/or modify +* it under the terms of the GNU General Public License version 2 as +* published by the Free Software Foundation. +*/ + +#include <expression.h> +#include <statement.h> +#include <rule.h> +#include <erec.h> +#include <utils.h> + +static void evaluate_cache_add (struct cmd *cmd,unsigned int *completeness) +{ +switch (cmd->obj) { +case CMD_OBJ_SETELEM : +case CMD_OBJ_SET :
src/cache.c line 29
Quoted 10 lines
src/cache.c new file +10
-0+case CMD_OBJ_CHAIN : +case CMD_OBJ_FLOWTABLE : +if (*completeness < cmd->op) + *completeness = cmd->op; +break ; +case CMD_OBJ_RULE : +/* XXX index is set to zero unless this handle_merge() call is +* invoked, this handle_merge() call is done from the +* evaluation, which is too late. +*/
Using the right handle was somehow tricky. IIRC, getting it right was part of the work on v5 of my series. Maybe you were working around a bug in my code?
Quoted 7 lines
src/cache.c new file +7
-0+handle_merge (&cmd->rule->handle, &cmd->handle); + +if (cmd->rule->handle.index.id && + *completeness <CMD_LIST ) + *completeness =CMD_LIST ; +break ; +default :
src/cache.c line 46
Quoted 10 lines
src/cache.c new file +10
-0+break ; + } +} + +static void evaluate_cache_del (struct cmd *cmd,unsigned int *completeness) +{ +switch (cmd->obj) { +case CMD_OBJ_SETELEM : +if (*completeness < cmd->op) + *completeness = cmd->op;
This manual max() thing seems to be a common pattern. Maybe make these functions return cmd->op (or the desired completeness) and handle the max() check in caller?
[...]
src/cache.c line 91
Quoted 13 lines
src/cache.c new file +13
-0+int cache_evaluate (struct nft_ctx *nft,struct list_head *cmds) +{ +unsigned int completeness =CMD_INVALID ; +struct cmd *cmd; + +list_for_each_entry (cmd, cmds, list) { +switch (cmd->op) { +case CMD_ADD : +case CMD_INSERT : +case CMD_REPLACE : +if (nft_output_echo (&nft->output) && + completeness < cmd->op) +return cmd->op;
Is 'return' correct here? That would abort cmd list processing.
Quoted 11 lines
src/cache.c new file +11
-0+ +/* Fall through */ +case CMD_CREATE : +evaluate_cache_add (cmd, &completeness); +break ; +case CMD_DELETE : +evaluate_cache_del (cmd, &completeness); +break ; +case CMD_GET : +case CMD_LIST : +case CMD_RESET :
src/cache.c line 112
Quoted 10 lines
src/cache.c new file +10
-0+case CMD_EXPORT : +case CMD_MONITOR : +if (completeness < cmd->op) + completeness = cmd->op; +break ; +case CMD_FLUSH : +evaluate_cache_flush (cmd, &completeness); +break ; +case CMD_RENAME : +evaluate_cache_rename (cmd, &completeness);
As suggested above, I would do (also in the other cases):
tmp = evaluate_cache_rename(cmd);
src/cache.c line 119
Quoted 7 lines
src/cache.c new file +7
-0+break ; +case CMD_DESCRIBE : +case CMD_IMPORT : +break ; +default : +break ; + }
And here:
completeness = max(tmp, completeness);
src/cache.c line 123
Quoted 4 lines
src/cache.c new file +4
-0+ } + +return completeness; +}
Cheers, Phil
Pablo Neira Ayuso
maintainerPhil,
I have pushed out this to master so you can rebase your patchset to revisit index logic on top of what is in git HEAD.
If there's any fallout from this, just let me know, I'll be swift about addressing it.
Thanks!