rule: collapse set element commands

Robots might generate a long list of singleton element commands such as:

  add element t s { 1.0.1.0/24 }
  ...
  add element t s { 1.0.2.0/23 }

collapse them into one single command before the evaluation step, ie.

  add element t s { 1.0.1.0/24, ..., 1.0.2.0/23 }

this speeds up overlap detection and set element automerge operations in
this worst case scenario.

Since 3da9643fb9ff9 ("intervals: add support to automerge with kernel
elements"), the new interval tracking relies on mergesort. The pattern
above triggers the set sorting for each element.

This patch adds a list to cmd objects that store collapsed commands.
Moreover, expressions also contain a reference to the original command,
to uncollapse the commands after the evaluation step.

These commands are uncollapsed after the evaluation step to ensure error
reporting works as expected (command and netlink message are mapped
1:1).

For the record:

- nftables versions <= 1.0.2 did not perform any kind of overlap
  check for the described scenario above (because set cache only contained
  elements in the kernel in this case). This is a problem for kernels < 5.7
  which rely on userspace to detect overlaps.

- the overlap detection could be skipped for kernels >= 5.7.

- The extended netlink error reporting available for set elements
  since 5.19-rc might allow to remove the uncollapse step, in this case,
  error reporting does not rely on the netlink sequence to refer to the
  command triggering the problem.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

1 files changed, 75 insertions, 0 deletions

diff --git a/src/rule.c b/src/rule.c
index 7f61bdc1..0526a148 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -1279,6 +1279,8 @@ struct cmd *cmd_alloc(enum cmd_ops op, enum cmd_obj obj,
 	cmd->handle   = *h;
 	cmd->location = *loc;
 	cmd->data     = data;
+	init_list_head(&cmd->collapse_list);
+
 	return cmd;
 }
 
@@ -1379,6 +1381,79 @@ void nft_cmd_expand(struct cmd *cmd)
 	}
 }
 
+bool nft_cmd_collapse(struct list_head *cmds)
+{
+	struct cmd *cmd, *next, *elems = NULL;
+	struct expr *expr, *enext;
+	bool collapse = false;
+
+	list_for_each_entry_safe(cmd, next, cmds, list) {
+		if (cmd->op != CMD_ADD &&
+		    cmd->op != CMD_CREATE) {
+			elems = NULL;
+			continue;
+		}
+
+		if (cmd->obj != CMD_OBJ_ELEMENTS) {
+			elems = NULL;
+			continue;
+		}
+
+		if (!elems) {
+			elems = cmd;
+			continue;
+		}
+
+		if (cmd->op != elems->op) {
+			elems = cmd;
+			continue;
+		}
+
+		if (strcmp(elems->handle.table.name, cmd->handle.table.name) ||
+		    strcmp(elems->handle.set.name, cmd->handle.set.name)) {
+			elems = cmd;
+			continue;
+		}
+
+		collapse = true;
+		list_for_each_entry_safe(expr, enext, &cmd->expr->expressions, list) {
+			expr->cmd = cmd;
+			list_move_tail(&expr->list, &elems->expr->expressions);
+		}
+		elems->expr->size += cmd->expr->size;
+		list_move_tail(&cmd->list, &elems->collapse_list);
+	}
+
+	return collapse;
+}
+
+void nft_cmd_uncollapse(struct list_head *cmds)
+{
+	struct cmd *cmd, *cmd_next, *collapse_cmd, *collapse_cmd_next;
+	struct expr *expr, *next;
+
+	list_for_each_entry_safe(cmd, cmd_next, cmds, list) {
+		if (list_empty(&cmd->collapse_list))
+			continue;
+
+		assert(cmd->obj == CMD_OBJ_ELEMENTS);
+
+		list_for_each_entry_safe(expr, next, &cmd->expr->expressions, list) {
+			if (!expr->cmd)
+				continue;
+
+			list_move_tail(&expr->list, &expr->cmd->expr->expressions);
+			cmd->expr->size--;
+			expr->cmd = NULL;
+		}
+
+		list_for_each_entry_safe(collapse_cmd, collapse_cmd_next, &cmd->collapse_list, list) {
+			collapse_cmd->elem.set = set_get(cmd->elem.set);
+			list_add(&collapse_cmd->list, &cmd->list);
+		}
+	}
+}
+
 struct markup *markup_alloc(uint32_t format)
 {
 	struct markup *markup;