[PATCH nftables,v2 0/7] ruleset optimization infrastructure

[PATCH nftables,v2 0/7] ruleset optimization infrastructure

[Pablo Neira Ayuso]

Hi,

This patchset adds a new -o/--optimize option to enable ruleset
optimization. Two type of optimizations are supported in this batch:

* Use a set to compact several rules with the same selector using a set,
  for example:

      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

* Use a verdict map to compact rules with same selectors but different
  verdicts, for example:

      ip saddr 1.1.1.1 ip daddr 2.2.2.2 accept
      ip saddr 2.2.2.2 ip daddr 3.3.3.3 drop

   into:

      ip saddr . ip daddr vmap { 1.1.1.1 . 2.2.2.2 : accept, 2.2.2.2 . 3.3.3.3 : drop }

Updates since last patch series:

- display information on the rule merges that are proposed, this can be
  combined with -c to inspect the proposed ruleset updates.

  # nft -c -o -f ruleset.nft

  This allows sysadmins to review the proposed optimization without actually
  loading the ruleset, in case they prefer to manually edit their rulesets
  to apply the proposed optimizations (requested by Arturo).

- tests/py and tests/shell run fine after this new iteration.

- fix error reporting with /dev/stdin, which is a prerequisite for this
  series.

- fixes.

Pablo Neira Ayuso (7):
  erec: expose print_location() and line_location()
  src: error reporting with -f and read from stdin
  src: remove '$' in symbol_expr_print
  src: add ruleset optimization infrastructure
  optimize: merge rules with same selectors into a concatenation
  optimize: merge same selector with different verdict into verdict map
  optimize: merge several selectors with different verdict into verdict map

 doc/nft.txt                                   |   5 +
 include/erec.h                                |   5 +
 include/nftables.h                            |   5 +
 include/nftables/libnftables.h                |   7 +
 include/rule.h                                |   1 -
 src/Makefile.am                               |   1 +
 src/erec.c                                    |  87 ++-
 src/expression.c                              |  33 +-
 src/libnftables.c                             | 109 ++-
 src/libnftables.map                           |   5 +
 src/main.c                                    |   9 +-
 src/optimize.c                                | 698 ++++++++++++++++++
 src/scanner.l                                 |   2 +-
 .../optimizations/dumps/merge_stmts.nft       |   5 +
 .../dumps/merge_stmts_concat.nft              |   5 +
 .../dumps/merge_stmts_concat_vmap.nft         |   5 +
 .../optimizations/dumps/merge_stmts_vmap.nft  |   5 +
 .../shell/testcases/optimizations/merge_stmts |  13 +
 .../optimizations/merge_stmts_concat          |  13 +
 .../optimizations/merge_stmts_concat_vmap     |  13 +
 .../testcases/optimizations/merge_stmts_vmap  |  12 +
 21 files changed, 992 insertions(+), 46 deletions(-)
 create mode 100644 src/optimize.c
 create mode 100644 tests/shell/testcases/optimizations/dumps/merge_stmts.nft
 create mode 100644 tests/shell/testcases/optimizations/dumps/merge_stmts_concat.nft
 create mode 100644 tests/shell/testcases/optimizations/dumps/merge_stmts_concat_vmap.nft
 create mode 100644 tests/shell/testcases/optimizations/dumps/merge_stmts_vmap.nft
 create mode 100755 tests/shell/testcases/optimizations/merge_stmts
 create mode 100755 tests/shell/testcases/optimizations/merge_stmts_concat
 create mode 100755 tests/shell/testcases/optimizations/merge_stmts_concat_vmap
 create mode 100755 tests/shell/testcases/optimizations/merge_stmts_vmap

[PATCH nftables,v2 1/7] erec: expose print_location() and line_location()

[Pablo Neira Ayuso]

Add a few helper functions to reuse code in the new rule optimization
infrastructure.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/erec.h |  5 ++++
 include/rule.h |  1 -
 src/erec.c     | 81 +++++++++++++++++++++++++++++++-------------------
 3 files changed, 56 insertions(+), 31 deletions(-)

diff --git a/include/erec.h b/include/erec.h
index 79a162902304..c17f5def5302 100644
--- a/include/erec.h
+++ b/include/erec.h
@@ -76,4 +76,9 @@ extern int __fmtstring(4, 5) __stmt_binary_error(struct eval_ctx *ctx,
 #define stmt_binary_error(ctx, s1, s2, fmt, args...) \
 	__stmt_binary_error(ctx, &(s1)->location, &(s2)->location, fmt, ## args)
 
+void print_location(FILE *f, const struct input_descriptor *indesc,
+		    const struct location *loc);
+const char *line_location(const struct input_descriptor *indesc,
+			  const struct location *loc, char *buf, size_t bufsiz);
+
 #endif /* NFTABLES_EREC_H */
diff --git a/include/rule.h b/include/rule.h
index be31695636df..150576641b39 100644
--- a/include/rule.h
+++ b/include/rule.h
@@ -311,7 +311,6 @@ void rule_stmt_append(struct rule *rule, struct stmt *stmt);
 void rule_stmt_insert_at(struct rule *rule, struct stmt *nstmt,
 			 struct stmt *stmt);
 
-
 /**
  * struct set - nftables set
  *
diff --git a/src/erec.c b/src/erec.c
index 5c3351a51246..7c9165c290d8 100644
--- a/src/erec.c
+++ b/src/erec.c
@@ -81,11 +81,57 @@ struct error_record *erec_create(enum error_record_types type,
 	return erec;
 }
 
+void print_location(FILE *f, const struct input_descriptor *indesc,
+		    const struct location *loc)
+{
+	const struct input_descriptor *tmp;
+	const struct location *iloc;
+
+	if (indesc->location.indesc != NULL) {
+		const char *prefix = "In file included from";
+		iloc = &indesc->location;
+		for (tmp = iloc->indesc;
+		     tmp != NULL && tmp->type != INDESC_INTERNAL;
+		     tmp = iloc->indesc) {
+			fprintf(f, "%s %s:%u:%u-%u:\n", prefix,
+				tmp->name,
+				iloc->first_line, iloc->first_column,
+				iloc->last_column);
+			prefix = "                 from";
+			iloc = &tmp->location;
+		}
+	}
+	if (indesc->name != NULL)
+		fprintf(f, "%s:%u:%u-%u: ", indesc->name,
+			loc->first_line, loc->first_column,
+			loc->last_column);
+}
+
+const char *line_location(const struct input_descriptor *indesc,
+			  const struct location *loc, char *buf, size_t bufsiz)
+{
+	const char *line;
+	FILE *f;
+
+	f = fopen(indesc->name, "r");
+	if (!f)
+		return NULL;
+
+	if (!fseek(f, loc->line_offset, SEEK_SET) &&
+	    fread(buf, 1, bufsiz - 1, f) > 0) {
+		*strchrnul(buf, '\n') = '\0';
+		line = buf;
+	}
+	fclose(f);
+
+	return line;
+}
+
 void erec_print(struct output_ctx *octx, const struct error_record *erec,
 		unsigned int debug_mask)
 {
-	const struct location *loc = erec->locations, *iloc;
-	const struct input_descriptor *indesc = loc->indesc, *tmp;
+	const struct location *loc = erec->locations;
+	const struct input_descriptor *indesc = loc->indesc;
 	const char *line = NULL;
 	char buf[1024] = {};
 	char *pbuf = NULL;
@@ -100,16 +146,7 @@ void erec_print(struct output_ctx *octx, const struct error_record *erec,
 		*strchrnul(line, '\n') = '\0';
 		break;
 	case INDESC_FILE:
-		f = fopen(indesc->name, "r");
-		if (!f)
-			break;
-
-		if (!fseek(f, loc->line_offset, SEEK_SET) &&
-		    fread(buf, 1, sizeof(buf) - 1, f) > 0) {
-			*strchrnul(buf, '\n') = '\0';
-			line = buf;
-		}
-		fclose(f);
+		line = line_location(indesc, loc, buf, sizeof(buf));
 		break;
 	case INDESC_INTERNAL:
 	case INDESC_NETLINK:
@@ -132,24 +169,8 @@ void erec_print(struct output_ctx *octx, const struct error_record *erec,
 		return;
 	}
 
-	if (indesc->location.indesc != NULL) {
-		const char *prefix = "In file included from";
-		iloc = &indesc->location;
-		for (tmp = iloc->indesc;
-		     tmp != NULL && tmp->type != INDESC_INTERNAL;
-		     tmp = iloc->indesc) {
-			fprintf(f, "%s %s:%u:%u-%u:\n", prefix,
-				tmp->name,
-				iloc->first_line, iloc->first_column,
-				iloc->last_column);
-			prefix = "                 from";
-			iloc = &tmp->location;
-		}
-	}
-	if (indesc->name != NULL)
-		fprintf(f, "%s:%u:%u-%u: ", indesc->name,
-			loc->first_line, loc->first_column,
-			loc->last_column);
+	print_location(f, indesc, loc);
+
 	if (error_record_names[erec->type])
 		fprintf(f, "%s: ", error_record_names[erec->type]);
 	fprintf(f, "%s\n", erec->msg);
-- 
2.30.2

[PATCH nftables,v2 2/7] src: error reporting with -f and read from stdin

[Pablo Neira Ayuso]

Reading from stdin requires to store the ruleset in a buffer so error
reporting works accordingly, eg.

 # cat ruleset.nft | nft -f -
 /dev/stdin:3:13-13: Error: unknown identifier 'x'
                 ip saddr $x
                           ^

The error reporting infrastructure performs a fseek() on the file
descriptor which does not work in this case since the data from the
descriptor has been already consumed.

This patch adds a new stdin input descriptor to perform this special
handling which consists on re-routing this request through the buffer
functions.

Fixes: 935f82e7dd49 ("Support 'nft -f -' to read from stdin")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/nftables.h |  2 ++
 src/erec.c         |  8 +++++++-
 src/libnftables.c  | 48 ++++++++++++++++++++++++++++++++++++++++++----
 src/scanner.l      |  2 +-
 4 files changed, 54 insertions(+), 6 deletions(-)

diff --git a/include/nftables.h b/include/nftables.h
index 7b6339053b54..d6d9b9cc7206 100644
--- a/include/nftables.h
+++ b/include/nftables.h
@@ -128,6 +128,7 @@ struct nft_ctx {
 	struct scope		*top_scope;
 	void			*json_root;
 	json_t			*json_echo;
+	const char		*stdin_buf;
 };
 
 enum nftables_exit_codes {
@@ -175,6 +176,7 @@ enum input_descriptor_types {
 	INDESC_FILE,
 	INDESC_CLI,
 	INDESC_NETLINK,
+	INDESC_STDIN,
 };
 
 /**
diff --git a/src/erec.c b/src/erec.c
index 7c9165c290d8..32fb079fa8b4 100644
--- a/src/erec.c
+++ b/src/erec.c
@@ -101,10 +101,11 @@ void print_location(FILE *f, const struct input_descriptor *indesc,
 			iloc = &tmp->location;
 		}
 	}
-	if (indesc->name != NULL)
+	if (indesc->type != INDESC_BUFFER && indesc->name) {
 		fprintf(f, "%s:%u:%u-%u: ", indesc->name,
 			loc->first_line, loc->first_column,
 			loc->last_column);
+	}
 }
 
 const char *line_location(const struct input_descriptor *indesc,
@@ -145,6 +146,11 @@ void erec_print(struct output_ctx *octx, const struct error_record *erec,
 		line = indesc->data;
 		*strchrnul(line, '\n') = '\0';
 		break;
+	case INDESC_STDIN:
+		line = indesc->data;
+		line += loc->line_offset;
+		*strchrnul(line, '\n') = '\0';
+		break;
 	case INDESC_FILE:
 		line = line_location(indesc, loc, buf, sizeof(buf));
 		break;
diff --git a/src/libnftables.c b/src/libnftables.c
index 7b9d7efaeaae..e76f32eff7ca 100644
--- a/src/libnftables.c
+++ b/src/libnftables.c
@@ -424,13 +424,14 @@ 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 list_head *msgs, struct list_head *cmds,
+				  const struct input_descriptor *indesc)
 {
 	int ret;
 
 	parser_init(nft, nft->state, msgs, cmds, nft->top_scope);
 	nft->scanner = scanner_init(nft->state);
-	scanner_push_buffer(nft->scanner, &indesc_cmdline, buf);
+	scanner_push_buffer(nft->scanner, indesc, buf);
 
 	ret = nft_parse(nft, nft->scanner, nft->state);
 	if (ret != 0 || nft->state->nerrs > 0)
@@ -439,11 +440,42 @@ static int nft_parse_bison_buffer(struct nft_ctx *nft, const char *buf,
 	return 0;
 }
 
+static char *stdin_to_buffer(void)
+{
+	unsigned int bufsiz = 16384, consumed = 0;
+	int numbytes;
+	char *buf;
+
+	buf = xmalloc(bufsiz);
+
+	numbytes = read(STDIN_FILENO, buf, bufsiz);
+	while (numbytes > 0) {
+		consumed += numbytes;
+		if (consumed == bufsiz) {
+			bufsiz *= 2;
+			buf = realloc(buf, bufsiz);
+		}
+		numbytes = read(STDIN_FILENO, buf + consumed, bufsiz - consumed);
+	}
+	buf[consumed] = '\0';
+
+	return buf;
+}
+
+static const struct input_descriptor indesc_stdin = {
+	.type	= INDESC_STDIN,
+	.name	= "/dev/stdin",
+};
+
 static int nft_parse_bison_filename(struct nft_ctx *nft, const char *filename,
 				    struct list_head *msgs, struct list_head *cmds)
 {
 	int ret;
 
+	if (nft->stdin_buf)
+		return nft_parse_bison_buffer(nft, nft->stdin_buf, msgs, cmds,
+					      &indesc_stdin);
+
 	parser_init(nft, nft->state, msgs, cmds, nft->top_scope);
 	nft->scanner = scanner_init(nft->state);
 	if (scanner_read_file(nft, filename, &internal_location) < 0)
@@ -510,7 +542,8 @@ int nft_run_cmd_from_buffer(struct nft_ctx *nft, const char *buf)
 	if (nft_output_json(&nft->output))
 		rc = nft_parse_json_buffer(nft, nlbuf, &msgs, &cmds);
 	if (rc == -EINVAL)
-		rc = nft_parse_bison_buffer(nft, nlbuf, &msgs, &cmds);
+		rc = nft_parse_bison_buffer(nft, nlbuf, &msgs, &cmds,
+					    &indesc_cmdline);
 
 	parser_rc = rc;
 
@@ -578,7 +611,7 @@ retry:
 	}
 	snprintf(buf + offset, bufsize - offset, "\n");
 
-	rc = nft_parse_bison_buffer(ctx, buf, msgs, &cmds);
+	rc = nft_parse_bison_buffer(ctx, buf, msgs, &cmds, &indesc_cmdline);
 
 	assert(list_empty(&cmds));
 	/* Stash the buffer that contains the variable definitions and zap the
@@ -608,6 +641,10 @@ int nft_run_cmd_from_filename(struct nft_ctx *nft, const char *filename)
 	if (!strcmp(filename, "-"))
 		filename = "/dev/stdin";
 
+	if (!strcmp(filename, "/dev/stdin") &&
+	    !nft_output_json(&nft->output))
+		nft->stdin_buf = stdin_to_buffer();
+
 	rc = -EINVAL;
 	if (nft_output_json(&nft->output))
 		rc = nft_parse_json_filename(nft, filename, &msgs, &cmds);
@@ -656,5 +693,8 @@ err:
 		json_print_echo(nft);
 	if (rc)
 		nft_cache_release(&nft->cache);
+
+	xfree(nft->stdin_buf);
+
 	return rc;
 }
diff --git a/src/scanner.l b/src/scanner.l
index f28bf3153f0b..7dcc45c2fd50 100644
--- a/src/scanner.l
+++ b/src/scanner.l
@@ -1032,7 +1032,7 @@ void scanner_push_buffer(void *scanner, const struct input_descriptor *indesc,
 	new_indesc = xzalloc(sizeof(struct input_descriptor));
 	memcpy(new_indesc, indesc, sizeof(*new_indesc));
 	new_indesc->data = buffer;
-	new_indesc->name = NULL;
+	new_indesc->name = xstrdup(indesc->name);
 	scanner_push_indesc(state, new_indesc);
 
 	b = yy_scan_string(buffer, scanner);
-- 
2.30.2

[PATCH nftables,v2 3/7] src: remove '$' in symbol_expr_print

[Pablo Neira Ayuso]

This is used in --debug=eval mode to annotate symbols that have not yet
been evaluated, remove it.

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

diff --git a/src/expression.c b/src/expression.c
index f1cca8845376..34e0880be470 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -300,8 +300,7 @@ struct expr *verdict_expr_alloc(const struct location *loc,
 
 static void symbol_expr_print(const struct expr *expr, struct output_ctx *octx)
 {
-	nft_print(octx, "%s%s", expr->scope != NULL ? "$" : "",
-		  expr->identifier);
+	nft_print(octx, "%s", expr->identifier);
 }
 
 static void symbol_expr_clone(struct expr *new, const struct expr *expr)
-- 
2.30.2

[PATCH nftables,v2 4/7] src: add ruleset optimization infrastructure

[Pablo Neira Ayuso]

This patch adds a new -o/--optimize option to enable ruleset
optimization.

You can combine this option with the dry run mode (--check) to review
the proposed ruleset updates without actually loading the ruleset, e.g.

 # nft -c -o -f ruleset.test
 Merging:
 ruleset.nft:16:3-37:           ip daddr 192.168.0.1 counter accept
 ruleset.nft:17:3-37:           ip daddr 192.168.0.2 counter accept
 ruleset.nft:18:3-37:           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

This infrastructure collects the common statements that are used in
rules, then it builds a matrix of rules vs. statements. Then, it looks
for common statements in consecutive rules which allows to merge rules.

This ruleset optimization always performs an implicit dry run to
validate that the original ruleset is correct. Then, on a second pass,
it performs the ruleset optimization and add the rules into the kernel
(unless --check has been specified by the user).

From libnftables perspective, there is a new API to enable
this feature:

  uint32_t nft_ctx_get_optimize(struct nft_ctx *ctx);
  void nft_ctx_set_optimize(struct nft_ctx *ctx, uint32_t flags);

This patch adds support for the first optimization: Collapse a linear
list of rules matching on a single selector into a set as exposed in the
example above.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 doc/nft.txt                                   |   5 +
 include/nftables.h                            |   3 +
 include/nftables/libnftables.h                |   7 +
 src/Makefile.am                               |   1 +
 src/libnftables.c                             |  71 ++-
 src/libnftables.map                           |   5 +
 src/main.c                                    |   9 +-
 src/optimize.c                                | 473 ++++++++++++++++++
 .../optimizations/dumps/merge_stmts.nft       |   5 +
 .../shell/testcases/optimizations/merge_stmts |  13 +
 10 files changed, 581 insertions(+), 11 deletions(-)
 create mode 100644 src/optimize.c
 create mode 100644 tests/shell/testcases/optimizations/dumps/merge_stmts.nft
 create mode 100755 tests/shell/testcases/optimizations/merge_stmts

diff --git a/doc/nft.txt b/doc/nft.txt
index e4ed98241018..7240deaa8100 100644
--- a/doc/nft.txt
+++ b/doc/nft.txt
@@ -62,6 +62,11 @@ understanding of their meaning. You can get information about options by running
 *--check*::
 	Check commands validity without actually applying the changes.
 
+*-o*::
+*--optimize*::
+	Optimize your ruleset. You can combine this option with '-c' to inspect
+        the proposed optimizations.
+
 .Ruleset list output formatting that modify the output of the list ruleset command:
 
 *-a*::
diff --git a/include/nftables.h b/include/nftables.h
index d6d9b9cc7206..d49eb579dc04 100644
--- a/include/nftables.h
+++ b/include/nftables.h
@@ -123,6 +123,7 @@ struct nft_ctx {
 	bool			check;
 	struct nft_cache	cache;
 	uint32_t		flags;
+	uint32_t		optimize_flags;
 	struct parser_state	*state;
 	void			*scanner;
 	struct scope		*top_scope;
@@ -224,6 +225,8 @@ 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);
+
 #define __NFT_OUTPUT_NOTSUPP	UINT_MAX
 
 #endif /* NFTABLES_NFTABLES_H */
diff --git a/include/nftables/libnftables.h b/include/nftables/libnftables.h
index 957b5fbee243..85e08c9bc98b 100644
--- a/include/nftables/libnftables.h
+++ b/include/nftables/libnftables.h
@@ -41,6 +41,13 @@ 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);
 
+enum nft_optimize_flags {
+	NFT_OPTIMIZE_ENABLED		= 0x1,
+};
+
+uint32_t nft_ctx_get_optimize(struct nft_ctx *ctx);
+void nft_ctx_set_optimize(struct nft_ctx *ctx, uint32_t flags);
+
 enum {
 	NFT_CTX_OUTPUT_REVERSEDNS	= (1 << 0),
 	NFT_CTX_OUTPUT_SERVICE		= (1 << 1),
diff --git a/src/Makefile.am b/src/Makefile.am
index 01c12c81bce7..c4556de5bd8b 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -70,6 +70,7 @@ libnftables_la_SOURCES =			\
 		mnl.c				\
 		iface.c				\
 		mergesort.c			\
+		optimize.c			\
 		osf.c				\
 		nfnl_osf.c			\
 		tcpopt.c			\
diff --git a/src/libnftables.c b/src/libnftables.c
index e76f32eff7ca..bd71ae9e704f 100644
--- a/src/libnftables.c
+++ b/src/libnftables.c
@@ -395,6 +395,18 @@ void nft_ctx_set_dry_run(struct nft_ctx *ctx, bool dry)
 	ctx->check = dry;
 }
 
+EXPORT_SYMBOL(nft_ctx_get_optimize);
+uint32_t nft_ctx_get_optimize(struct nft_ctx *ctx)
+{
+	return ctx->optimize_flags;
+}
+
+EXPORT_SYMBOL(nft_ctx_set_optimize);
+void nft_ctx_set_optimize(struct nft_ctx *ctx, uint32_t flags)
+{
+	ctx->optimize_flags = flags;
+}
+
 EXPORT_SYMBOL(nft_ctx_output_get_flags);
 unsigned int nft_ctx_output_get_flags(struct nft_ctx *ctx)
 {
@@ -626,8 +638,7 @@ retry:
 	return rc;
 }
 
-EXPORT_SYMBOL(nft_run_cmd_from_filename);
-int nft_run_cmd_from_filename(struct nft_ctx *nft, const char *filename)
+static int __nft_run_cmd_from_filename(struct nft_ctx *nft, const char *filename)
 {
 	struct cmd *cmd, *next;
 	int rc, parser_rc;
@@ -638,13 +649,6 @@ int nft_run_cmd_from_filename(struct nft_ctx *nft, const char *filename)
 	if (rc < 0)
 		goto err;
 
-	if (!strcmp(filename, "-"))
-		filename = "/dev/stdin";
-
-	if (!strcmp(filename, "/dev/stdin") &&
-	    !nft_output_json(&nft->output))
-		nft->stdin_buf = stdin_to_buffer();
-
 	rc = -EINVAL;
 	if (nft_output_json(&nft->output))
 		rc = nft_parse_json_filename(nft, filename, &msgs, &cmds);
@@ -653,6 +657,9 @@ int nft_run_cmd_from_filename(struct nft_ctx *nft, const char *filename)
 
 	parser_rc = rc;
 
+	if (nft->optimize_flags)
+		nft_optimize(nft, &cmds);
+
 	rc = nft_evaluate(nft, &msgs, &cmds);
 	if (rc < 0)
 		goto err;
@@ -694,7 +701,51 @@ err:
 	if (rc)
 		nft_cache_release(&nft->cache);
 
+	return rc;
+}
+
+static int nft_run_optimized_file(struct nft_ctx *nft, const char *filename)
+{
+	uint32_t optimize_flags;
+	bool check;
+	int ret;
+
+	check = nft->check;
+	nft->check = true;
+	optimize_flags = nft->optimize_flags;
+	nft->optimize_flags = 0;
+
+	/* First check the original ruleset loads fine as is. */
+	ret = __nft_run_cmd_from_filename(nft, filename);
+	if (ret < 0)
+		return ret;
+
+	nft->check = check;
+	nft->optimize_flags = optimize_flags;
+
+	return __nft_run_cmd_from_filename(nft, filename);
+}
+
+EXPORT_SYMBOL(nft_run_cmd_from_filename);
+int nft_run_cmd_from_filename(struct nft_ctx *nft, const char *filename)
+{
+	int ret;
+
+	if (!strcmp(filename, "-"))
+		filename = "/dev/stdin";
+
+	if (!strcmp(filename, "/dev/stdin") &&
+	    !nft_output_json(&nft->output))
+		nft->stdin_buf = stdin_to_buffer();
+
+	if (nft->optimize_flags) {
+		ret = nft_run_optimized_file(nft, filename);
+		xfree(nft->stdin_buf);
+		return ret;
+	}
+
+	ret = __nft_run_cmd_from_filename(nft, filename);
 	xfree(nft->stdin_buf);
 
-	return rc;
+	return ret;
 }
diff --git a/src/libnftables.map b/src/libnftables.map
index d3a795ce8567..a511dd789154 100644
--- a/src/libnftables.map
+++ b/src/libnftables.map
@@ -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;
diff --git a/src/main.c b/src/main.c
index 5847fc4ad514..9bd25db82343 100644
--- a/src/main.c
+++ b/src/main.c
@@ -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, 0x1);
+			break;
 		case OPT_INVALID:
 			exit(EXIT_FAILURE);
 		}
diff --git a/src/optimize.c b/src/optimize.c
new file mode 100644
index 000000000000..5ccdbbdd491f
--- /dev/null
+++ b/src/optimize.c
@@ -0,0 +1,473 @@
+/*
+ * Copyright (c) 2021 Pablo Neira Ayuso <pablo@netfilter.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 (or any
+ * later) as published by the Free Software Foundation.
+ */
+
+#define _GNU_SOURCE
+#include <string.h>
+#include <errno.h>
+#include <inttypes.h>
+#include <nftables.h>
+#include <parser.h>
+#include <expression.h>
+#include <statement.h>
+#include <utils.h>
+#include <erec.h>
+
+#define MAX_STMTS	32
+
+struct optimize_ctx {
+	struct stmt *stmt[MAX_STMTS];
+	uint32_t num_stmts;
+
+	struct stmt ***stmt_matrix;
+	struct rule **rule;
+	uint32_t num_rules;
+};
+
+static bool __stmt_type_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)
+{
+	struct expr *expr_a, *expr_b;
+
+	if (stmt_a->ops->type != stmt_b->ops->type)
+		return false;
+
+	switch (stmt_a->ops->type) {
+	case STMT_EXPRESSION:
+		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;
+	case STMT_COUNTER:
+	case STMT_NOTRACK:
+		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;
+	case STMT_LIMIT:
+		if (stmt_a->limit.rate != stmt_b->limit.rate ||
+		    stmt_a->limit.unit != stmt_b->limit.unit ||
+		    stmt_a->limit.burst != stmt_b->limit.burst ||
+		    stmt_a->limit.type != stmt_b->limit.type ||
+		    stmt_a->limit.flags != stmt_b->limit.flags)
+			return false;
+		break;
+	case STMT_LOG:
+		if (stmt_a->log.snaplen != stmt_b->log.snaplen ||
+		    stmt_a->log.group != stmt_b->log.group ||
+		    stmt_a->log.qthreshold != stmt_b->log.qthreshold ||
+		    stmt_a->log.level != stmt_b->log.level ||
+		    stmt_a->log.logflags != stmt_b->log.logflags ||
+		    stmt_a->log.flags != stmt_b->log.flags ||
+		    stmt_a->log.prefix->etype != EXPR_VALUE ||
+		    stmt_b->log.prefix->etype != EXPR_VALUE ||
+		    mpz_cmp(stmt_a->log.prefix->value, stmt_b->log.prefix->value))
+			return false;
+		break;
+	case STMT_REJECT:
+		if (stmt_a->reject.expr || stmt_b->reject.expr)
+			return false;
+
+		if (stmt_a->reject.family != stmt_b->reject.family ||
+		    stmt_a->reject.type != stmt_b->reject.type ||
+		    stmt_a->reject.icmp_code != stmt_b->reject.icmp_code)
+			return false;
+		break;
+	default:
+		/* ... Merging anything else is yet unsupported. */
+		return false;
+	}
+
+	return true;
+}
+
+static bool stmt_type_eq(const struct stmt *stmt_a, const struct stmt *stmt_b)
+{
+	if (!stmt_a && !stmt_b)
+		return true;
+	else if (!stmt_a)
+		return false;
+	else if (!stmt_b)
+		return false;
+
+	return __stmt_type_eq(stmt_a, stmt_b);
+}
+
+static bool stmt_type_find(struct optimize_ctx *ctx, const struct stmt *stmt)
+{
+	uint32_t i;
+
+	for (i = 0; i < ctx->num_stmts; i++) {
+		if (__stmt_type_eq(stmt, ctx->stmt[i]))
+			return true;
+	}
+
+	return false;
+}
+
+static int rule_collect_stmts(struct optimize_ctx *ctx, struct rule *rule)
+{
+	struct stmt *stmt, *clone;
+
+	list_for_each_entry(stmt, &rule->stmts, list) {
+		if (stmt_type_find(ctx, stmt))
+			continue;
+
+		/* No refcounter available in statement objects, clone it to
+		 * to store in the array of selectors.
+		 */
+		clone = stmt_alloc(&internal_location, stmt->ops);
+		switch (stmt->ops->type) {
+		case STMT_EXPRESSION:
+		case STMT_VERDICT:
+			clone->expr = expr_get(stmt->expr);
+			break;
+		case STMT_COUNTER:
+		case STMT_NOTRACK:
+			break;
+		case STMT_LIMIT:
+			memcpy(&clone->limit, &stmt->limit, sizeof(clone->limit));
+			break;
+		case STMT_LOG:
+			memcpy(&clone->log, &stmt->log, sizeof(clone->log));
+			clone->log.prefix = expr_get(stmt->log.prefix);
+			break;
+		default:
+			break;
+		}
+
+		ctx->stmt[ctx->num_stmts++] = clone;
+		if (ctx->num_stmts >= MAX_STMTS)
+			return -1;
+	}
+
+	return 0;
+}
+
+static int cmd_stmt_find_in_stmt_matrix(struct optimize_ctx *ctx, struct stmt *stmt)
+{
+	uint32_t i;
+
+	for (i = 0; i < ctx->num_stmts; i++) {
+		if (__stmt_type_eq(stmt, ctx->stmt[i]))
+			return i;
+	}
+	/* should not ever happen. */
+	return 0;
+}
+
+static void rule_build_stmt_matrix_stmts(struct optimize_ctx *ctx,
+					 struct rule *rule, uint32_t *i)
+{
+	struct stmt *stmt;
+	int k;
+
+	list_for_each_entry(stmt, &rule->stmts, list) {
+		k = cmd_stmt_find_in_stmt_matrix(ctx, stmt);
+		ctx->stmt_matrix[*i][k] = stmt;
+	}
+	ctx->rule[(*i)++] = rule;
+}
+
+struct merge {
+	/* interval of rules to be merged */
+	uint32_t	rule_from;
+	uint32_t	num_rules;
+	/* statements to be merged (index relative to statement matrix) */
+	uint32_t	stmt[MAX_STMTS];
+	uint32_t	num_stmts;
+};
+
+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]];
+	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;
+
+	expr_a = stmt_a->expr->right;
+	elem = set_elem_expr_alloc(&internal_location, expr_get(expr_a));
+	compound_expr_add(set, elem);
+
+	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);
+	}
+
+	expr_free(stmt_a->expr->right);
+	stmt_a->expr->right = set;
+}
+
+static void rule_optimize_print(struct output_ctx *octx,
+				const struct rule *rule)
+{
+	const struct location *loc = &rule->location;
+	const struct input_descriptor *indesc = loc->indesc;
+	const char *line;
+	char buf[1024];
+
+	switch (indesc->type) {
+	case INDESC_BUFFER:
+	case INDESC_CLI:
+		line = indesc->data;
+		*strchrnul(line, '\n') = '\0';
+		break;
+	case INDESC_STDIN:
+		line = indesc->data;
+		line += loc->line_offset;
+		*strchrnul(line, '\n') = '\0';
+		break;
+	case INDESC_FILE:
+		line = line_location(indesc, loc, buf, sizeof(buf));
+		break;
+	case INDESC_INTERNAL:
+	case INDESC_NETLINK:
+		break;
+	default:
+		BUG("invalid input descriptor type %u\n", indesc->type);
+	}
+
+	print_location(octx->error_fp, indesc, loc);
+	fprintf(octx->error_fp, "%s\n", line);
+}
+
+static void merge_rules(const struct optimize_ctx *ctx,
+			uint32_t from, uint32_t to,
+			const struct merge *merge,
+			struct output_ctx *octx)
+{
+	uint32_t i;
+
+	if (merge->num_stmts > 1) {
+		return;
+	} else {
+		merge_stmts(ctx, from, to, merge);
+	}
+
+	fprintf(octx->error_fp, "Merging:\n");
+	rule_optimize_print(octx, ctx->rule[from]);
+
+	for (i = from + 1; i <= to; i++) {
+		rule_optimize_print(octx, ctx->rule[i]);
+		list_del(&ctx->rule[i]->list);
+		rule_free(ctx->rule[i]);
+	}
+
+	fprintf(octx->error_fp, "into:\n\t");
+	rule_print(ctx->rule[from], octx);
+	fprintf(octx->error_fp, "\n");
+}
+
+static bool rules_eq(const struct optimize_ctx *ctx, int i, int j)
+{
+	uint32_t k;
+
+	for (k = 0; k < ctx->num_stmts; k++) {
+		if (!stmt_type_eq(ctx->stmt_matrix[i][k], ctx->stmt_matrix[j][k]))
+			return false;
+	}
+
+	return true;
+}
+
+static int chain_optimize(struct nft_ctx *nft, struct list_head *rules)
+{
+	struct optimize_ctx *ctx;
+	uint32_t num_merges = 0;
+	struct merge *merge;
+	uint32_t i, j, m, k;
+	struct rule *rule;
+	int ret;
+
+	ctx = xzalloc(sizeof(*ctx));
+
+	/* Step 1: collect statements in rules */
+	list_for_each_entry(rule, rules, list) {
+		ret = rule_collect_stmts(ctx, rule);
+		if (ret < 0)
+			goto err;
+
+		ctx->num_rules++;
+	}
+
+	ctx->rule = xzalloc(sizeof(ctx->rule) * ctx->num_rules);
+	ctx->stmt_matrix = xzalloc(sizeof(struct stmt *) * ctx->num_rules);
+	for (i = 0; i < ctx->num_rules; i++)
+		ctx->stmt_matrix[i] = xzalloc(sizeof(struct stmt *) * MAX_STMTS);
+
+	merge = xzalloc(sizeof(*merge) * ctx->num_rules);
+
+	/* Step 2: Build matrix of statements */
+	i = 0;
+	list_for_each_entry(rule, rules, list)
+		rule_build_stmt_matrix_stmts(ctx, rule, &i);
+
+	/* Step 3: Look for common selectors for possible rule mergers */
+	for (i = 0; i < ctx->num_rules; i++) {
+		for (j = i + 1; j < ctx->num_rules; j++) {
+			if (!rules_eq(ctx, i, j)) {
+				if (merge[num_merges].num_rules > 0)
+					num_merges++;
+
+				i = j - 1;
+				break;
+			}
+			if (merge[num_merges].num_rules > 0) {
+				merge[num_merges].num_rules++;
+			} else {
+				merge[num_merges].rule_from = i;
+				merge[num_merges].num_rules = 2;
+			}
+		}
+		if (j == ctx->num_rules && merge[num_merges].num_rules > 0) {
+			num_merges++;
+			break;
+		}
+	}
+
+	/* Step 4: Infer how to merge the candidate rules */
+	for (k = 0; k < num_merges; k++) {
+		i = merge[k].rule_from;
+
+		for (m = 0; m < ctx->num_stmts; m++) {
+			if (!ctx->stmt_matrix[i][m])
+				continue;
+			switch (ctx->stmt_matrix[i][m]->ops->type) {
+			case STMT_EXPRESSION:
+				merge[k].stmt[merge[k].num_stmts++] = m;
+				break;
+			default:
+				break;
+			}
+		}
+
+		j = merge[k].num_rules - 1;
+		merge_rules(ctx, i, i + j, &merge[k], &nft->output);
+	}
+	ret = 0;
+	for (i = 0; i < ctx->num_rules; i++)
+		xfree(ctx->stmt_matrix[i]);
+
+	xfree(ctx->stmt_matrix);
+	xfree(merge);
+err:
+	for (i = 0; i < ctx->num_stmts; i++)
+		stmt_free(ctx->stmt[i]);
+
+	xfree(ctx->rule);
+	xfree(ctx);
+
+	return ret;
+}
+
+static int cmd_optimize(struct nft_ctx *nft, struct cmd *cmd)
+{
+	struct table *table;
+	struct chain *chain;
+	int ret = 0;
+
+	switch (cmd->obj) {
+	case CMD_OBJ_TABLE:
+		table = cmd->table;
+		if (!table)
+			break;
+
+		list_for_each_entry(chain, &table->chains, list) {
+			if (chain->flags & CHAIN_F_HW_OFFLOAD)
+				continue;
+
+			chain_optimize(nft, &chain->rules);
+		}
+		break;
+	default:
+		break;
+	}
+
+	return ret;
+}
+
+int nft_optimize(struct nft_ctx *nft, struct list_head *cmds)
+{
+	struct cmd *cmd;
+	int ret;
+
+	list_for_each_entry(cmd, cmds, list) {
+		switch (cmd->op) {
+		case CMD_ADD:
+			ret = cmd_optimize(nft, cmd);
+			break;
+		default:
+			break;
+		}
+	}
+
+	return ret;
+}
diff --git a/tests/shell/testcases/optimizations/dumps/merge_stmts.nft b/tests/shell/testcases/optimizations/dumps/merge_stmts.nft
new file mode 100644
index 000000000000..b56ea3ed4115
--- /dev/null
+++ b/tests/shell/testcases/optimizations/dumps/merge_stmts.nft
@@ -0,0 +1,5 @@
+table ip x {
+	chain y {
+		ip daddr { 192.168.0.1, 192.168.0.2, 192.168.0.3 } counter packets 0 bytes 0 accept
+	}
+}
diff --git a/tests/shell/testcases/optimizations/merge_stmts b/tests/shell/testcases/optimizations/merge_stmts
new file mode 100755
index 000000000000..0c35636efaa9
--- /dev/null
+++ b/tests/shell/testcases/optimizations/merge_stmts
@@ -0,0 +1,13 @@
+#!/bin/bash
+
+set -e
+
+RULESET="table ip x {
+	chain y {
+		ip daddr 192.168.0.1 counter accept
+		ip daddr 192.168.0.2 counter accept
+		ip daddr 192.168.0.3 counter accept
+	}
+}"
+
+$NFT -o -f - <<< $RULESET
-- 
2.30.2

[PATCH nftables,v2 5/7] optimize: merge rules with same selectors into a concatenation

[Pablo Neira Ayuso]

This 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

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/optimize.c                                | 44 ++++++++++++++++++-
 .../dumps/merge_stmts_concat.nft              |  5 +++
 .../optimizations/merge_stmts_concat          | 13 ++++++
 3 files changed, 61 insertions(+), 1 deletion(-)
 create mode 100644 tests/shell/testcases/optimizations/dumps/merge_stmts_concat.nft
 create mode 100755 tests/shell/testcases/optimizations/merge_stmts_concat

diff --git a/src/optimize.c b/src/optimize.c
index 5ccdbbdd491f..aaf29c88af75 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -266,6 +266,48 @@ static void merge_stmts(const struct optimize_ctx *ctx,
 	stmt_a->expr->right = set;
 }
 
+static void merge_concat_stmts(const struct optimize_ctx *ctx,
+			       uint32_t from, uint32_t to,
+			       const struct merge *merge)
+{
+	struct expr *concat, *elem, *set;
+	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 } */
+	set = set_expr_alloc(&internal_location, NULL);
+	set->set_flags |= NFT_SET_ANONYMOUS;
+
+	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(set, elem);
+	}
+	expr_free(stmt->expr->right);
+	stmt->expr->right = set;
+
+	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 rule_optimize_print(struct output_ctx *octx,
 				const struct rule *rule)
 {
@@ -307,7 +349,7 @@ static void merge_rules(const struct optimize_ctx *ctx,
 	uint32_t i;
 
 	if (merge->num_stmts > 1) {
-		return;
+		merge_concat_stmts(ctx, from, to, merge);
 	} else {
 		merge_stmts(ctx, from, to, merge);
 	}
diff --git a/tests/shell/testcases/optimizations/dumps/merge_stmts_concat.nft b/tests/shell/testcases/optimizations/dumps/merge_stmts_concat.nft
new file mode 100644
index 000000000000..6dbfff2e15fc
--- /dev/null
+++ b/tests/shell/testcases/optimizations/dumps/merge_stmts_concat.nft
@@ -0,0 +1,5 @@
+table ip x {
+	chain y {
+		iifname . ip saddr . ip daddr { "eth1" . 1.1.1.1 . 2.2.2.3, "eth1" . 1.1.1.2 . 2.2.2.4, "eth2" . 1.1.1.3 . 2.2.2.5 } accept
+	}
+}
diff --git a/tests/shell/testcases/optimizations/merge_stmts_concat b/tests/shell/testcases/optimizations/merge_stmts_concat
new file mode 100755
index 000000000000..941e9a5aa822
--- /dev/null
+++ b/tests/shell/testcases/optimizations/merge_stmts_concat
@@ -0,0 +1,13 @@
+#!/bin/bash
+
+set -e
+
+RULESET="table ip x {
+	chain y {
+		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.4 accept
+		meta iifname eth2 ip saddr 1.1.1.3 ip daddr 2.2.2.5 accept
+	}
+}"
+
+$NFT -o -f - <<< $RULESET
-- 
2.30.2

[PATCH nftables,v2 6/7] optimize: merge same selector with different verdict into verdict map

[Pablo Neira Ayuso]

Transform:

  ct state invalid drop
  ct state established,related accept

into:

  ct state vmap { established : accept, related : accept, invalid : drop }

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

diff --git a/src/optimize.c b/src/optimize.c
index aaf29c88af75..1ca5e25e4337 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -90,19 +90,6 @@ 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->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;
 	case STMT_LIMIT:
 		if (stmt_a->limit.rate != stmt_b->limit.rate ||
@@ -141,6 +128,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)
@@ -229,6 +239,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;
@@ -308,6 +332,105 @@ static void merge_concat_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 remove_counter(const struct optimize_ctx *ctx, uint32_t from)
+{
+	struct stmt *stmt;
+	uint32_t i;
+
+	/* remove counter statement */
+	for (i = 0; i < ctx->num_stmts; i++) {
+		stmt = ctx->stmt_matrix[from][i];
+		if (!stmt)
+			continue;
+
+		if (stmt->ops->type == STMT_COUNTER) {
+			list_del(&stmt->list);
+			stmt_free(stmt);
+		}
+	}
+}
+
+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;
+	int k;
+
+	k = stmt_verdict_find(ctx);
+	assert(k >= 0);
+
+	verdict_a = ctx->stmt_matrix[from][k];
+	set = set_expr_alloc(&internal_location, NULL);
+	set->set_flags |= NFT_SET_ANONYMOUS;
+
+	expr_a = stmt_a->expr->right;
+	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);
+
+	remove_counter(ctx, from);
+	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 i;
+	int k;
+
+	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_a && !stmt_b)
+			return true;
+		if (stmt_verdict_eq(stmt_a, stmt_b))
+			return true;
+	}
+
+	return false;
+}
+
 static void rule_optimize_print(struct output_ctx *octx,
 				const struct rule *rule)
 {
@@ -346,12 +469,21 @@ static void merge_rules(const struct optimize_ctx *ctx,
 			const struct merge *merge,
 			struct output_ctx *octx)
 {
+	bool same_verdict;
 	uint32_t i;
 
+	same_verdict = stmt_verdict_cmp(ctx, from, to);
+
 	if (merge->num_stmts > 1) {
-		merge_concat_stmts(ctx, from, to, merge);
+		if (same_verdict)
+			merge_concat_stmts(ctx, from, to, merge);
+		else
+			return;
 	} else {
-		merge_stmts(ctx, from, to, merge);
+		if (same_verdict)
+			merge_stmts(ctx, from, to, merge);
+		else
+			merge_stmts_vmap(ctx, from, to, merge);
 	}
 
 	fprintf(octx->error_fp, "Merging:\n");
diff --git a/tests/shell/testcases/optimizations/dumps/merge_stmts_vmap.nft b/tests/shell/testcases/optimizations/dumps/merge_stmts_vmap.nft
new file mode 100644
index 000000000000..9fa19afcb783
--- /dev/null
+++ b/tests/shell/testcases/optimizations/dumps/merge_stmts_vmap.nft
@@ -0,0 +1,5 @@
+table ip x {
+	chain y {
+		ct state vmap { invalid : drop, established : accept, related : accept }
+	}
+}
diff --git a/tests/shell/testcases/optimizations/merge_stmts_vmap b/tests/shell/testcases/optimizations/merge_stmts_vmap
new file mode 100755
index 000000000000..f838fcfed70b
--- /dev/null
+++ b/tests/shell/testcases/optimizations/merge_stmts_vmap
@@ -0,0 +1,12 @@
+#!/bin/bash
+
+set -e
+
+RULESET="table ip x {
+	chain y {
+		ct state invalid drop
+		ct state established,related accept
+	}
+}"
+
+$NFT -o -f - <<< $RULESET
-- 
2.30.2

[PATCH nftables,v2 7/7] optimize: merge several selectors with different verdict into verdict map

[Pablo Neira Ayuso]

Transform:

  ip saddr 1.1.1.1 ip daddr 2.2.2.2 accept
  ip saddr 2.2.2.2 ip daddr 3.3.3.3 drop

into:

  ip saddr . ip daddr vmap { 1.1.1.1 . 2.2.2.2 : accept, 2.2.2.2 . 3.3.3.3 : drop }

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/expression.c                              | 30 +++++++++-
 src/optimize.c                                | 57 ++++++++++++++++++-
 .../dumps/merge_stmts_concat_vmap.nft         |  5 ++
 .../optimizations/merge_stmts_concat_vmap     | 13 +++++
 4 files changed, 102 insertions(+), 3 deletions(-)
 create mode 100644 tests/shell/testcases/optimizations/dumps/merge_stmts_concat_vmap.nft
 create mode 100755 tests/shell/testcases/optimizations/merge_stmts_concat_vmap

diff --git a/src/expression.c b/src/expression.c
index 34e0880be470..ea999f2e546c 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -1185,14 +1185,40 @@ struct expr *mapping_expr_alloc(const struct location *loc,
 	return expr;
 }
 
+static bool __set_expr_is_vmap(const struct expr *mappings)
+{
+	const struct expr *mapping;
+
+	if (list_empty(&mappings->expressions))
+		return false;
+
+	mapping = list_first_entry(&mappings->expressions, struct expr, list);
+	if (mapping->etype == EXPR_MAPPING &&
+	    mapping->right->etype == EXPR_VERDICT)
+		return true;
+
+	return false;
+}
+
+static bool set_expr_is_vmap(const struct expr *expr)
+{
+
+	if (expr->mappings->etype == EXPR_SET)
+		return __set_expr_is_vmap(expr->mappings);
+
+	return false;
+}
+
 static void map_expr_print(const struct expr *expr, struct output_ctx *octx)
 {
 	expr_print(expr->map, octx);
-	if (expr->mappings->etype == EXPR_SET_REF &&
-	    expr->mappings->set->data->dtype->type == TYPE_VERDICT)
+	if ((expr->mappings->etype == EXPR_SET_REF &&
+	     expr->mappings->set->data->dtype->type == TYPE_VERDICT) ||
+	    set_expr_is_vmap(expr))
 		nft_print(octx, " vmap ");
 	else
 		nft_print(octx, " map ");
+
 	expr_print(expr->mappings, octx);
 }
 
diff --git a/src/optimize.c b/src/optimize.c
index 1ca5e25e4337..b16fb5ec1b05 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -408,6 +408,61 @@ static void merge_stmts_vmap(const struct optimize_ctx *ctx,
 	stmt_free(verdict_a);
 }
 
+static void merge_concat_stmts_vmap(const struct optimize_ctx *ctx,
+				    uint32_t from, uint32_t to,
+				    const struct merge *merge)
+{
+	struct stmt *orig_stmt = ctx->stmt_matrix[from][merge->stmt[0]];
+	struct expr *concat_a, *concat_b, *expr, *set;
+	struct stmt *stmt, *stmt_a, *stmt_b, *verdict;
+	uint32_t i, j;
+	int k;
+
+	k = stmt_verdict_find(ctx);
+	assert(k >= 0);
+
+	/* build concatenation of selectors, eg. ifname . ip daddr . tcp dport */
+	concat_a = concat_expr_alloc(&internal_location);
+	for (i = 0; i < merge->num_stmts; i++) {
+		stmt_a = ctx->stmt_matrix[from][merge->stmt[i]];
+		compound_expr_add(concat_a, expr_get(stmt_a->expr->left));
+	}
+
+	/* build set data contenation, eg. { eth0 . 1.1.1.1 . 22 : accept } */
+	set = set_expr_alloc(&internal_location, NULL);
+	set->set_flags |= NFT_SET_ANONYMOUS;
+
+	for (i = from; i <= to; i++) {
+		concat_b = concat_expr_alloc(&internal_location);
+		for (j = 0; j < merge->num_stmts; j++) {
+			stmt_b = ctx->stmt_matrix[i][merge->stmt[j]];
+			expr = stmt_b->expr->right;
+			compound_expr_add(concat_b, expr_get(expr));
+		}
+		verdict = ctx->stmt_matrix[i][k];
+		build_verdict_map(concat_b, verdict, set);
+		expr_free(concat_b);
+	}
+
+	expr = map_expr_alloc(&internal_location, concat_a, set);
+	stmt = verdict_stmt_alloc(&internal_location, expr);
+
+	remove_counter(ctx, from);
+	list_add(&stmt->list, &orig_stmt->list);
+	list_del(&orig_stmt->list);
+	stmt_free(orig_stmt);
+
+	for (i = 1; i < merge->num_stmts; i++) {
+		stmt_a = ctx->stmt_matrix[from][merge->stmt[i]];
+		list_del(&stmt_a->list);
+		stmt_free(stmt_a);
+	}
+
+	verdict = ctx->stmt_matrix[from][k];
+	list_del(&verdict->list);
+	stmt_free(verdict);
+}
+
 static bool stmt_verdict_cmp(const struct optimize_ctx *ctx,
 			     uint32_t from, uint32_t to)
 {
@@ -478,7 +533,7 @@ static void merge_rules(const struct optimize_ctx *ctx,
 		if (same_verdict)
 			merge_concat_stmts(ctx, from, to, merge);
 		else
-			return;
+			merge_concat_stmts_vmap(ctx, from, to, merge);
 	} else {
 		if (same_verdict)
 			merge_stmts(ctx, from, to, merge);
diff --git a/tests/shell/testcases/optimizations/dumps/merge_stmts_concat_vmap.nft b/tests/shell/testcases/optimizations/dumps/merge_stmts_concat_vmap.nft
new file mode 100644
index 000000000000..c0f9ce0ccb6c
--- /dev/null
+++ b/tests/shell/testcases/optimizations/dumps/merge_stmts_concat_vmap.nft
@@ -0,0 +1,5 @@
+table ip x {
+	chain y {
+		ip saddr . ip daddr vmap { 1.1.1.1 . 2.2.2.2 : accept, 2.2.2.2 . 3.3.3.3 : drop, 4.4.4.4 . 5.5.5.5 : accept }
+	}
+}
diff --git a/tests/shell/testcases/optimizations/merge_stmts_concat_vmap b/tests/shell/testcases/optimizations/merge_stmts_concat_vmap
new file mode 100755
index 000000000000..f1ab0288ab0d
--- /dev/null
+++ b/tests/shell/testcases/optimizations/merge_stmts_concat_vmap
@@ -0,0 +1,13 @@
+#!/bin/bash
+
+set -e
+
+RULESET="table ip x {
+	chain y {
+		ip saddr 1.1.1.1 ip daddr 2.2.2.2 accept
+		ip saddr 2.2.2.2 ip daddr 3.3.3.3 drop
+		ip saddr 4.4.4.4 ip daddr 5.5.5.5 accept
+	}
+}"
+
+$NFT -o -f - <<< $RULESET
-- 
2.30.2

Re: [PATCH nftables,v2 0/7] ruleset optimization infrastructure

[Pablo Neira Ayuso]

On Sun, Jan 02, 2022 at 11:14:45PM +0100, Pablo Neira Ayuso wrote:
[...]
> Updates since last patch series:
> 
> - display information on the rule merges that are proposed, this can be
>   combined with -c to inspect the proposed ruleset updates.
> 
>   # nft -c -o -f ruleset.nft

For the record, an example output of -c -o

nft -o -c -f ruleset.nft
Merging:
ruleset.nft:3:3-46:            ip daddr 192.168.1.0/24 ct state new counter
ruleset.nft:4:3-46:            ip daddr 192.168.2.0/24 ct state new counter
ruleset.nft:5:3-46:            ip daddr 192.168.3.0/24 ct state new counter
ruleset.nft:6:3-46:            ip daddr 192.168.4.0/24 ct state new counter
into:
        ip daddr . ct state { 192.168.1.0/24 . new, 192.168.2.0/24 . new, 192.168.3.0/24 . new, 192.168.4.0/24 . new } counter packets 0 bytes 0
Merging:
ruleset.nft:7:3-23:            ct state invalid drop
ruleset.nft:8:3-37:            ct state established,related accept
into:
        ct state vmap { invalid : drop, established : accept, related : accept }
Merging:
ruleset.nft:9:3-60:            meta iifname eth1 ip saddr 1.1.1.2 ip daddr 2.2.2.3 accept
ruleset.nft:10:3-60:           meta iifname eth1 ip saddr 2.2.2.2 ip daddr 2.2.2.5 accept
ruleset.nft:11:3-60:           meta iifname eth2 ip saddr 1.1.1.3 ip daddr 2.2.2.6 accept
into:
        ip daddr . iifname . ip saddr { 2.2.2.3 . eth1 . 1.1.1.2, 2.2.2.5 . eth1 . 2.2.2.2, 2.2.2.6 . eth2 . 1.1.1.3 } accept
Merging:
ruleset.nft:12:3-97:           ip saddr 10.69.0.0/24 ct state new counter packets 0 bytes 0 log prefix "unexpected traffic" level debug
ruleset.nft:13:3-97:           ip saddr 10.69.1.0/24 ct state new counter packets 0 bytes 0 log prefix "unexpected traffic" level debug
into:
        ct state . ip saddr { new . 10.69.0.0/24, new . 10.69.1.0/24 } counter packets 0 bytes 0 log prefix "unexpected traffic" level debug
Merging:
ruleset.nft:16:3-37:           ip daddr 192.168.0.1 counter accept
ruleset.nft:17:3-37:           ip daddr 192.168.0.2 counter accept
ruleset.nft:18:3-37:           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

Re: [PATCH nftables,v2 0/7] ruleset optimization infrastructure

[Nicolas Dichtel]

Le 02/01/2022 à 23:14, Pablo Neira Ayuso a écrit :
> Hi,
> 
> This patchset adds a new -o/--optimize option to enable ruleset
> optimization. Two type of optimizations are supported in this batch:
> 
> * Use a set to compact several rules with the same selector using a set,
>   for example:
> 
>       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
nit: it would probably be better with this result ;-)
meta iifname . ip saddr . ip daddr { eth1 . 1.1.1.1 . 2.2.2.3, eth1 . 1.1.1.2 .
2.2.2.5 , eth2 . 1.1.1.3 . 2.2.2.6 } accept


Regards,
Nicolas

Re: [PATCH nftables,v2 0/7] ruleset optimization infrastructure

[Pablo Neira Ayuso]

On Sun, Jan 02, 2022 at 11:14:45PM +0100, Pablo Neira Ayuso wrote:
> Hi,
> 
> This patchset adds a new -o/--optimize option to enable ruleset
> optimization.

For the record, I have pushed out these.