[PATCH nft] optimize: invalidate merge in case of duplicated key in set/map

[Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx>]

-o/--optimize results in EEXIST error when merging two rules that lead
to ambiguous set/map, for instance:

 table ip x {
        chain v4icmp {}
        chain v4icmpc {}

        chain y {
                ip protocol icmp jump v4icmp
                ip protocol icmp goto v4icmpc
        }
 }

which is not possible because duplicated keys are not possible in
set/map. This is how it shows when running a test:

 Merging:
 testcases/sets/dumps/sets_with_ifnames.nft:56:3-30:            ip protocol icmp jump v4icmp
 testcases/sets/dumps/sets_with_ifnames.nft:57:3-31:            ip protocol icmp goto v4icmpc
 into:
       ip protocol vmap { icmp : jump v4icmp, icmp : goto v4icmpc }
 internal:0:0-0: Error: Could not process rule: File exists

Add a new step to compare rules that are candidate to be merged to
detect colissions in set/map keys in order to skip them in the next
final merging step.

Fixes: fb298877ece2 ("src: add ruleset optimization infrastructure")
Signed-off-by: Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx>
---
 src/optimize.c | 40 +++++++++++++++++++++++++++++++++++++++-
 1 file changed, 39 insertions(+), 1 deletion(-)

diff --git a/src/optimize.c b/src/optimize.c
index 139bc2d73c3c..5b7b0ab62fbc 100644
--- a/src/optimize.c
+++ b/src/optimize.c
@@ -138,6 +138,8 @@ static bool __expr_cmp(const struct expr *expr_a, const struct expr *expr_b)
 			return false;
 
 		return !strcmp(expr_a->identifier, expr_b->identifier);
+	case EXPR_VALUE:
+		return !mpz_cmp(expr_a->value, expr_b->value);
 	default:
 		return false;
 	}
@@ -548,6 +550,8 @@ struct merge {
 	/* statements to be merged (index relative to statement matrix) */
 	uint32_t	stmt[MAX_STMTS];
 	uint32_t	num_stmts;
+	/* merge has been invalidated */
+	bool		skip;
 };
 
 static void merge_expr_stmts(const struct optimize_ctx *ctx,
@@ -1379,8 +1383,42 @@ static int chain_optimize(struct nft_ctx *nft, struct list_head *rules)
 		}
 	}
 
-	/* Step 4: Infer how to merge the candidate rules */
+	/* Step 4: Invalidate merge in case of duplicated keys in set/map. */
+	for (k = 0; k < num_merges; k++) {
+		uint32_t r1, r2;
+
+		i = merge[k].rule_from;
+
+		for (r1 = i; r1 < i + merge[k].num_rules; r1++) {
+			for (r2 = r1 + 1; r2 < i + merge[k].num_rules; r2++) {
+				bool match_same_value = true, match_seen = false;
+
+				for (m = 0; m < ctx->num_stmts; m++) {
+					if (!ctx->stmt_matrix[r1][m])
+						continue;
+
+					switch (ctx->stmt_matrix[r1][m]->type) {
+					case STMT_EXPRESSION:
+						match_seen = true;
+						if (!__expr_cmp(ctx->stmt_matrix[r1][m]->expr->right,
+							        ctx->stmt_matrix[r2][m]->expr->right))
+							match_same_value = false;
+						break;
+					default:
+						break;
+					}
+				}
+				if (match_seen && match_same_value)
+					merge[k].skip = true;
+			}
+		}
+	}
+
+	/* Step 5: Infer how to merge the candidate rules */
 	for (k = 0; k < num_merges; k++) {
+		if (merge[k].skip)
+			continue;
+
 		i = merge[k].rule_from;
 
 		for (m = 0; m < ctx->num_stmts; m++) {
-- 
2.30.2