[PATCH 0/3] nftables: fix segtree interval conflict reporting

[PATCH 0/3] nftables: fix segtree interval conflict reporting

[Patrick McHardy]

The following patches fix segtree interval conflict reporting. Currently
on a conflict a debug message is printed and the error is ignored. These
patches change this to output a proper error and abort.

Additionally the cases where an conflict is detected is fixed to ignore
cases when the data associated with two intervals is equal.


Patrick McHardy (3):
      expr: make expr_binary_error() usable outside of evaluation
      expr: add comparison function for singleton expressions
      set: abort on interval conflicts

 include/expression.h | 12 ++++++++----
 src/ct.c             |  6 ++++++
 src/expression.c     | 36 ++++++++++++++++++++++++++++++++++--
 src/exthdr.c         |  7 +++++++
 src/meta.c           |  6 ++++++
 src/payload.c        | 17 +++++++++++++----
 src/rule.c           |  5 +++--
 src/segtree.c        | 21 +++++++++++++++------
 8 files changed, 92 insertions(+), 18 deletions(-)

[PATCH 1/3] expr: make expr_binary_error() usable outside of evaluation

[Patrick McHardy]

Turn the eval_ctx argument into a list_head to queue the error to.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/expression.h | 6 +++---
 src/expression.c     | 4 ++--
 src/payload.c        | 8 ++++----
 3 files changed, 9 insertions(+), 9 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index ac6a4f4..354e679 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -268,12 +268,12 @@ extern void expr_set_type(struct expr *expr, const struct datatype *dtype,
 			  enum byteorder byteorder);
 
 struct eval_ctx;
-extern int expr_binary_error(struct eval_ctx *ctx,
+extern int expr_binary_error(struct list_head *msgs,
 			     const struct expr *e1, const struct expr *e2,
 			     const char *fmt, ...) __gmp_fmtstring(4, 5);
 
-#define expr_error(ctx, expr, fmt, args...) \
-	expr_binary_error(ctx, expr, NULL, fmt, ## args)
+#define expr_error(msgs, expr, fmt, args...) \
+	expr_binary_error(msgs, expr, NULL, fmt, ## args)
 
 static inline bool expr_is_constant(const struct expr *expr)
 {
diff --git a/src/expression.c b/src/expression.c
index adaf6e7..cdc2b7b 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -127,7 +127,7 @@ const struct datatype *expr_basetype(const struct expr *expr)
 	return type;
 }
 
-int __fmtstring(4, 5) expr_binary_error(struct eval_ctx *ctx,
+int __fmtstring(4, 5) expr_binary_error(struct list_head *msgs,
 					const struct expr *e1, const struct expr *e2,
 					const char *fmt, ...)
 {
@@ -139,7 +139,7 @@ int __fmtstring(4, 5) expr_binary_error(struct eval_ctx *ctx,
 	if (e2 != NULL)
 		erec_add_location(erec, &e2->location);
 	va_end(ap);
-	erec_queue(erec, ctx->msgs);
+	erec_queue(erec, msgs);
 	return -1;
 }
 
diff --git a/src/payload.c b/src/payload.c
index a312e07..9f2db6d 100644
--- a/src/payload.c
+++ b/src/payload.c
@@ -154,12 +154,12 @@ int payload_gen_dependency(struct eval_ctx *ctx, const struct expr *expr,
 
 	if (expr->payload.base < h->base) {
 		if (expr->payload.base < h->base - 1)
-			return expr_error(ctx, expr,
+			return expr_error(ctx->msgs, expr,
 					  "payload base is invalid for this "
 					  "family");
 
 		if (proto_dev_type(expr->payload.desc, &type) < 0)
-			return expr_error(ctx, expr,
+			return expr_error(ctx->msgs, expr,
 					  "protocol specification is invalid "
 					  "for this family");
 
@@ -181,14 +181,14 @@ int payload_gen_dependency(struct eval_ctx *ctx, const struct expr *expr,
 		desc = &proto_inet_service;
 
 	if (desc == NULL)
-		return expr_error(ctx, expr,
+		return expr_error(ctx->msgs, expr,
 				  "ambiguous payload specification: "
 				  "no %s protocol specified",
 				  proto_base_names[expr->payload.base - 1]);
 
 	protocol = proto_find_num(desc, expr->payload.desc);
 	if (protocol < 0)
-		return expr_error(ctx, expr,
+		return expr_error(ctx->msgs, expr,
 				  "conflicting protocols specified: %s vs. %s",
 				  desc->name, expr->payload.desc->name);
 
-- 
1.8.5.3

[PATCH 2/3] expr: add comparison function for singleton expressions

[Patrick McHardy]

Singed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/expression.h |  4 ++++
 src/ct.c             |  6 ++++++
 src/expression.c     | 32 ++++++++++++++++++++++++++++++++
 src/exthdr.c         |  7 +++++++
 src/meta.c           |  6 ++++++
 src/payload.c        |  9 +++++++++
 6 files changed, 64 insertions(+)

diff --git a/include/expression.h b/include/expression.h
index 354e679..d974131 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -120,6 +120,7 @@ static inline void expr_set_context(struct expr_ctx *ctx,
  * @destroy:	destructor, must release inner expressions
  * @set_type:	function to promote type and byteorder of inner types
  * @print:	function to print the expression
+ * @cmp:	function to compare two expressions of the same types
  * @pctx_update:update protocol context
  */
 struct proto_ctx;
@@ -132,6 +133,8 @@ struct expr_ops {
 					    const struct datatype *dtype,
 					    enum byteorder byteorder);
 	void			(*print)(const struct expr *expr);
+	bool			(*cmp)(const struct expr *e1,
+				       const struct expr *e2);
 	void			(*pctx_update)(struct proto_ctx *ctx,
 					       const struct expr *expr);
 };
@@ -261,6 +264,7 @@ extern struct expr *expr_clone(const struct expr *expr);
 extern struct expr *expr_get(struct expr *expr);
 extern void expr_free(struct expr *expr);
 extern void expr_print(const struct expr *expr);
+extern bool expr_cmp(const struct expr *e1, const struct expr *e2);
 extern void expr_describe(const struct expr *expr);
 
 extern const struct datatype *expr_basetype(const struct expr *expr);
diff --git a/src/ct.c b/src/ct.c
index 32f22a5..a27621e 100644
--- a/src/ct.c
+++ b/src/ct.c
@@ -204,6 +204,11 @@ static void ct_expr_print(const struct expr *expr)
 	printf("ct %s", ct_templates[expr->ct.key].token);
 }
 
+static bool ct_expr_cmp(const struct expr *e1, const struct expr *e2)
+{
+	return e1->ct.key == e2->ct.key;
+}
+
 static void ct_expr_clone(struct expr *new, const struct expr *expr)
 {
 	new->ct.key = expr->ct.key;
@@ -233,6 +238,7 @@ static const struct expr_ops ct_expr_ops = {
 	.type		= EXPR_CT,
 	.name		= "ct",
 	.print		= ct_expr_print,
+	.cmp		= ct_expr_cmp,
 	.clone		= ct_expr_clone,
 	.pctx_update	= ct_expr_pctx_update,
 };
diff --git a/src/expression.c b/src/expression.c
index cdc2b7b..1313925 100644
--- a/src/expression.c
+++ b/src/expression.c
@@ -74,6 +74,17 @@ void expr_print(const struct expr *expr)
 	expr->ops->print(expr);
 }
 
+bool expr_cmp(const struct expr *e1, const struct expr *e2)
+{
+	assert(e1->flags & EXPR_F_SINGLETON);
+	assert(e2->flags & EXPR_F_SINGLETON);
+
+	if (e1->ops->type != e2->ops->type)
+		return false;
+
+	return e1->ops->cmp(e1, e2);
+}
+
 void expr_describe(const struct expr *expr)
 {
 	const struct datatype *dtype = expr->dtype;
@@ -148,6 +159,19 @@ static void verdict_expr_print(const struct expr *expr)
 	datatype_print(expr);
 }
 
+static bool verdict_expr_cmp(const struct expr *e1, const struct expr *e2)
+{
+	if (e1->verdict != e2->verdict)
+		return false;
+
+	if ((e1->verdict == NFT_JUMP ||
+	     e1->verdict == NFT_GOTO) &&
+	    strcmp(e1->chain, e2->chain))
+		return false;
+
+	return true;
+}
+
 static void verdict_expr_clone(struct expr *new, const struct expr *expr)
 {
 	new->verdict = expr->verdict;
@@ -164,6 +188,7 @@ static const struct expr_ops verdict_expr_ops = {
 	.type		= EXPR_VERDICT,
 	.name		= "verdict",
 	.print		= verdict_expr_print,
+	.cmp		= verdict_expr_cmp,
 	.clone		= verdict_expr_clone,
 	.destroy	= verdict_expr_destroy,
 };
@@ -226,6 +251,12 @@ static void constant_expr_print(const struct expr *expr)
 	datatype_print(expr);
 }
 
+static bool constant_expr_cmp(const struct expr *e1, const struct expr *e2)
+{
+	return expr_basetype(e1) == expr_basetype(e2) &&
+	       !mpz_cmp(e1->value, e2->value);
+}
+
 static void constant_expr_clone(struct expr *new, const struct expr *expr)
 {
 	mpz_init_set(new->value, expr->value);
@@ -240,6 +271,7 @@ static const struct expr_ops constant_expr_ops = {
 	.type		= EXPR_VALUE,
 	.name		= "value",
 	.print		= constant_expr_print,
+	.cmp		= constant_expr_cmp,
 	.clone		= constant_expr_clone,
 	.destroy	= constant_expr_destroy,
 };
diff --git a/src/exthdr.c b/src/exthdr.c
index 458f9d6..a619ecc 100644
--- a/src/exthdr.c
+++ b/src/exthdr.c
@@ -27,6 +27,12 @@ static void exthdr_expr_print(const struct expr *expr)
 	printf("%s %s", expr->exthdr.desc->name, expr->exthdr.tmpl->token);
 }
 
+static bool exthdr_expr_cmp(const struct expr *e1, const struct expr *e2)
+{
+	return e1->exthdr.desc == e2->exthdr.desc &&
+	       e1->exthdr.tmpl == e2->exthdr.tmpl;
+}
+
 static void exthdr_expr_clone(struct expr *new, const struct expr *expr)
 {
 	new->exthdr.desc = expr->exthdr.desc;
@@ -37,6 +43,7 @@ static const struct expr_ops exthdr_expr_ops = {
 	.type		= EXPR_EXTHDR,
 	.name		= "exthdr",
 	.print		= exthdr_expr_print,
+	.cmp		= exthdr_expr_cmp,
 	.clone		= exthdr_expr_clone,
 };
 
diff --git a/src/meta.c b/src/meta.c
index af5c3f9..ebc0c54 100644
--- a/src/meta.c
+++ b/src/meta.c
@@ -350,6 +350,11 @@ static void meta_expr_print(const struct expr *expr)
 	}
 }
 
+static bool meta_expr_cmp(const struct expr *e1, const struct expr *e2)
+{
+	return e1->meta.key == e2->meta.key;
+}
+
 static void meta_expr_clone(struct expr *new, const struct expr *expr)
 {
 	new->meta.key = expr->meta.key;
@@ -407,6 +412,7 @@ static const struct expr_ops meta_expr_ops = {
 	.type		= EXPR_META,
 	.name		= "meta",
 	.print		= meta_expr_print,
+	.cmp		= meta_expr_cmp,
 	.clone		= meta_expr_clone,
 	.pctx_update	= meta_expr_pctx_update,
 };
diff --git a/src/payload.c b/src/payload.c
index 9f2db6d..427080c 100644
--- a/src/payload.c
+++ b/src/payload.c
@@ -40,6 +40,14 @@ static void payload_expr_print(const struct expr *expr)
 		       expr->payload.offset, expr->len);
 }
 
+static bool payload_expr_cmp(const struct expr *e1, const struct expr *e2)
+{
+	return e1->payload.desc   == e2->payload.desc &&
+	       e1->payload.tmpl   == e2->payload.tmpl &&
+	       e1->payload.base   == e2->payload.base &&
+	       e1->payload.offset == e2->payload.offset;
+}
+
 static void payload_expr_clone(struct expr *new, const struct expr *expr)
 {
 	new->payload.desc   = expr->payload.desc;
@@ -76,6 +84,7 @@ static const struct expr_ops payload_expr_ops = {
 	.type		= EXPR_PAYLOAD,
 	.name		= "payload",
 	.print		= payload_expr_print,
+	.cmp		= payload_expr_cmp,
 	.clone		= payload_expr_clone,
 	.pctx_update	= payload_expr_pctx_update,
 };
-- 
1.8.5.3

[PATCH 3/3] set: abort on interval conflicts

[Patrick McHardy]

We currently print a debug message (with debugging) and continue. Output
a proper error message and abort.

While at it, make sure we only report a conflict if there actually is one.
This is not the case similar actions, IOW in case of sets, never, in case
of maps, only if the mapping differs.

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 include/expression.h |  2 +-
 src/rule.c           |  5 +++--
 src/segtree.c        | 21 +++++++++++++++------
 3 files changed, 19 insertions(+), 9 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index d974131..edb6dc5 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -341,7 +341,7 @@ extern struct expr *concat_expr_alloc(const struct location *loc);
 extern struct expr *list_expr_alloc(const struct location *loc);
 
 extern struct expr *set_expr_alloc(const struct location *loc);
-extern void set_to_intervals(struct set *set);
+extern int set_to_intervals(struct list_head *msgs, struct set *set);
 
 extern struct expr *mapping_expr_alloc(const struct location *loc,
 				       struct expr *from, struct expr *to);
diff --git a/src/rule.c b/src/rule.c
index 0e04282..b719040 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -498,8 +498,9 @@ static int do_add_set(struct netlink_ctx *ctx, const struct handle *h,
 	if (netlink_add_set(ctx, h, set) < 0)
 		return -1;
 	if (set->init != NULL) {
-		if (set->flags & SET_F_INTERVAL)
-			set_to_intervals(set);
+		if (set->flags & SET_F_INTERVAL &&
+		    set_to_intervals(ctx->msgs, set) < 0)
+			return -1;
 		if (do_add_setelems(ctx, &set->handle, set->init) < 0)
 			return -1;
 	}
diff --git a/src/segtree.c b/src/segtree.c
index 1a21c6c..c169f8d 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -329,13 +329,15 @@ static bool interval_conflict(const struct elementary_interval *e1,
 {
 	if (mpz_cmp(e1->left, e2->left) <= 0 &&
 	    mpz_cmp(e1->right, e2->left) >= 0 &&
-	    mpz_cmp(e1->size, e2->size) == 0)
+	    mpz_cmp(e1->size, e2->size) == 0 &&
+	    !expr_cmp(e1->expr->right, e2->expr->right))
 		return true;
 	else
 		return false;
 }
 
-static void set_to_segtree(struct expr *set, struct seg_tree *tree)
+static int set_to_segtree(struct list_head *msgs, struct expr *set,
+			  struct seg_tree *tree)
 {
 	struct elementary_interval *intervals[set->size];
 	struct elementary_interval *ei;
@@ -365,14 +367,19 @@ static void set_to_segtree(struct expr *set, struct seg_tree *tree)
 	 * Insert elements into tree
 	 */
 	for (n = 0; n < set->size; n++) {
-		if (n < set->size - 1 &&
+		if (set->set_flags & SET_F_MAP &&
+		    n < set->size - 1 &&
 		    interval_conflict(intervals[n], intervals[n+1]))
-			pr_debug("conflict\n");
+			return expr_binary_error(msgs,
+					intervals[n]->expr,
+					intervals[n+1]->expr,
+					"conflicting intervals specified");
 		ei_insert(tree, intervals[n]);
 	}
 
 	mpz_clear(high);
 	mpz_clear(low);
+	return 0;
 }
 
 static void segtree_linearize(struct list_head *list, struct seg_tree *tree)
@@ -461,14 +468,15 @@ static void set_insert_interval(struct expr *set, struct seg_tree *tree,
 	compound_expr_add(set, expr);
 }
 
-void set_to_intervals(struct set *set)
+int set_to_intervals(struct list_head *errs, struct set *set)
 {
 	struct elementary_interval *ei, *next;
 	struct seg_tree tree;
 	LIST_HEAD(list);
 
 	seg_tree_init(&tree, set);
-	set_to_segtree(set->init, &tree);
+	if (set_to_segtree(errs, set->init, &tree) < 0)
+		return -1;
 	segtree_linearize(&list, &tree);
 
 	list_for_each_entry_safe(ei, next, &list, list) {
@@ -485,6 +493,7 @@ void set_to_intervals(struct set *set)
 		expr_print(set->init);
 		pr_debug("\n");
 	}
+	return 0;
 }
 
 static bool range_is_prefix(const mpz_t range)
-- 
1.8.5.3