[PATCH nft 0/7] named sets with intervals

[PATCH nft 0/7] named sets with intervals

[Pablo Neira Ayuso]

This patchset updates the set interval support to work with named sets,
that requires the following kernel patches that I have already submitted:

http://patchwork.ozlabs.org/patch/609733/
http://patchwork.ozlabs.org/patch/609734/
http://patchwork.ozlabs.org/patch/609735/
http://patchwork.ozlabs.org/patch/609736/

Several comments on this:

1) nft supports automerging of adjacent intervals when they are added in
   the same command, eg.

	nft add element filter myset { 192.168.0.0/24, 192.168.1.0/24 }

   this results in one single interval 192.168.0.0/23.

   However, if you add them in two command invocations:

	nft add element filter myset { 192.168.0.0/24 }
	nft add element filter myset { 192.168.0.1/24 }

   You get two intervals, ie. 192.168.0.0/24 and 192.168.1.0/24. Automerging
   for this case should be possible from userspace, by removing the previous
   interval and adding the new one. This code is not yet available though.

2) There is currently no check in userspace for interval shadowing, eg.

	nft add element filter myset { 192.168.0.0/24 }
	nft add element filter myset { 192.168.0.0/16 }

    In this case, the largest segment is prioritized over the smaller one.
    The code to detect this shadowing from userspace is missing.

3) The first non-matching end interval (ie. all-zero) is specific of the
   rbtree implementation, I don't need this in my bitmap set
   representation. This is already part of the API though, so my plan is to
   add this node to the rbtree set from the kernel and ignore whenever we
   receive it from userspace, so we can deprecate having to send this from
   userspace at some point.

4) Support for named interval map is also missing. This requires a very
   small oneliner fix for the parser. Interval shadowing is particularly
   problematic in this scenario, for this reason, the oneliner fix should
   come with the shadowing detection code too. Meanwhile we don't have
   proper support for named interval maps.

Pablo Neira Ayuso (7):
  segtree: perform stricter expression type validation from expr_value()
  segtree: clone full expression from interval_map_decompose()
  segtree: handle adjacent interval nodes from expr_value_cmp()
  segtree: explicit initialization via set_to_intervals()
  rule: support for incremental set interval element updates
  segtree: special handling for the first non-matching segment
  evaluate: bail out on prefix or range to non-interval set

 include/expression.h |  3 ++-
 src/evaluate.c       | 15 +++++++++++
 src/rule.c           | 52 +++++++++++++++++++++++++++++-------
 src/segtree.c        | 75 +++++++++++++++++++++++++++++++++++++++++-----------
 4 files changed, 118 insertions(+), 27 deletions(-)

-- 
2.1.4

[PATCH nft 1/7] segtree: perform stricter expression type validation from expr_value()

[Pablo Neira Ayuso]

This helper function returns a expression value type that represents the
set element key. This functions currently expects two kind of
expressions: set elements and mappings.

Bail out otherwise, if we see anything else, we have to fix our code.

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

diff --git a/src/segtree.c b/src/segtree.c
index 060951c..5b69ffb 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -473,10 +473,14 @@ extern void interval_map_decompose(struct expr *set);
 
 static struct expr *expr_value(struct expr *expr)
 {
-	if (expr->ops->type == EXPR_MAPPING)
+	switch (expr->ops->type) {
+	case EXPR_MAPPING:
 		return expr->left->key;
-	else
+	case EXPR_SET_ELEM:
 		return expr->key;
+	default:
+		BUG("invalid expression type %s\n", expr->ops->name);
+	}
 }
 
 static int expr_value_cmp(const void *p1, const void *p2)
-- 
2.1.4

[PATCH nft 2/7] segtree: clone full expression from interval_map_decompose()

[Pablo Neira Ayuso]

Instead of cloning just its value, expr_value() expects a set element or
mapping.

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

diff --git a/src/segtree.c b/src/segtree.c
index 5b69ffb..75f02b9 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -520,7 +520,7 @@ void interval_map_decompose(struct expr *set)
 		if (i->flags & EXPR_F_INTERVAL_END)
 			interval = false;
 		else if (interval) {
-			end = expr_clone(expr_value(i));
+			end = expr_clone(i);
 			end->flags |= EXPR_F_INTERVAL_END;
 			ranges[n++] = end;
 		} else
-- 
2.1.4

[PATCH nft 3/7] segtree: handle adjacent interval nodes from expr_value_cmp()

[Pablo Neira Ayuso]

Named sets may contain adjacent interval nodes, when equal in key, look
at the flags. Those with EXPR_F_INTERVAL_END should come in first place.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/segtree.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/src/segtree.c b/src/segtree.c
index 75f02b9..d8f98fa 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -487,8 +487,15 @@ static int expr_value_cmp(const void *p1, const void *p2)
 {
 	struct expr *e1 = *(void * const *)p1;
 	struct expr *e2 = *(void * const *)p2;
+	int ret;
 
-	return mpz_cmp(expr_value(e1)->value, expr_value(e2)->value);
+	ret = mpz_cmp(expr_value(e1)->value, expr_value(e2)->value);
+	if (ret == 0 && (e1->flags & EXPR_F_INTERVAL_END))
+		return -1;
+	else
+		return 1;
+
+	return ret;
 }
 
 void interval_map_decompose(struct expr *set)
-- 
2.1.4

[PATCH nft 4/7] segtree: explicit initialization via set_to_intervals()

[Pablo Neira Ayuso]

Allow explicit compound expression to initialize the set intervals.
Incremental updates to interval sets require this.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/expression.h |  3 ++-
 src/rule.c           |  2 +-
 src/segtree.c        | 15 ++++++++-------
 3 files changed, 11 insertions(+), 9 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index 72b6f69..62a1e51 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -364,7 +364,8 @@ 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 int set_to_intervals(struct list_head *msgs, struct set *set);
+extern int set_to_intervals(struct list_head *msgs, struct set *set,
+			    struct expr *init);
 
 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 b7f4a07..43a606b 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -878,7 +878,7 @@ static int do_add_set(struct netlink_ctx *ctx, const struct handle *h,
 		return -1;
 	if (set->init != NULL) {
 		if (set->flags & SET_F_INTERVAL &&
-		    set_to_intervals(ctx->msgs, set) < 0)
+		    set_to_intervals(ctx->msgs, set, set->init) < 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 d8f98fa..c0a8c28 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -64,11 +64,12 @@ struct elementary_interval {
 	struct expr			*expr;
 };
 
-static void seg_tree_init(struct seg_tree *tree, const struct set *set)
+static void seg_tree_init(struct seg_tree *tree, const struct set *set,
+			  struct expr *init)
 {
 	struct expr *first;
 
-	first = list_entry(set->init->expressions.next, struct expr, list);
+	first = list_entry(init->expressions.next, struct expr, list);
 	tree->root	= RB_ROOT;
 	tree->keytype	= set->keytype;
 	tree->keylen	= set->keylen;
@@ -431,14 +432,14 @@ static void set_insert_interval(struct expr *set, struct seg_tree *tree,
 	compound_expr_add(set, expr);
 }
 
-int set_to_intervals(struct list_head *errs, struct set *set)
+int set_to_intervals(struct list_head *errs, struct set *set, struct expr *init)
 {
 	struct elementary_interval *ei, *next;
 	struct seg_tree tree;
 	LIST_HEAD(list);
 
-	seg_tree_init(&tree, set);
-	if (set_to_segtree(errs, set->init, &tree) < 0)
+	seg_tree_init(&tree, set, init);
+	if (set_to_segtree(errs, init, &tree) < 0)
 		return -1;
 	segtree_linearize(&list, &tree);
 
@@ -448,12 +449,12 @@ int set_to_intervals(struct list_head *errs, struct set *set)
 				     2 * tree.keylen / BITS_PER_BYTE, ei->left,
 				     2 * tree.keylen / BITS_PER_BYTE, ei->right);
 		}
-		set_insert_interval(set->init, &tree, ei);
+		set_insert_interval(init, &tree, ei);
 		ei_destroy(ei);
 	}
 
 	if (segtree_debug()) {
-		expr_print(set->init);
+		expr_print(init);
 		pr_gmp_debug("\n");
 	}
 	return 0;
-- 
2.1.4

[PATCH nft 5/7] rule: support for incremental set interval element updates

[Pablo Neira Ayuso]

Introduce __do_add_setelems() and do_delete_setelems() to support
incremental set interval element updates.

>From do_add_set(), use netlink_add_setelems() not to try to re-add the
same elements again

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/rule.c | 52 ++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 42 insertions(+), 10 deletions(-)

diff --git a/src/rule.c b/src/rule.c
index 43a606b..e2f15ee 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -863,26 +863,39 @@ static int do_add_chain(struct netlink_ctx *ctx, const struct handle *h,
 	return 0;
 }
 
-static int do_add_setelems(struct netlink_ctx *ctx, const struct handle *h,
-			   const struct expr *expr)
+static int __do_add_setelems(struct netlink_ctx *ctx, const struct handle *h,
+			     struct set *set, struct expr *expr)
 {
+	if (set->flags & SET_F_INTERVAL &&
+	    set_to_intervals(ctx->msgs, set, expr) < 0)
+		return -1;
+
 	if (netlink_add_setelems(ctx, h, expr) < 0)
 		return -1;
+
 	return 0;
 }
 
+static int do_add_setelems(struct netlink_ctx *ctx, const struct handle *h,
+			   struct expr *init)
+{
+	struct table *table;
+	struct set *set;
+
+	table = table_lookup(h);
+	set = set_lookup(table, h->set);
+
+	return __do_add_setelems(ctx, h, set, init);
+}
+
 static int do_add_set(struct netlink_ctx *ctx, const struct handle *h,
 		      struct set *set)
 {
 	if (netlink_add_set(ctx, h, set) < 0)
 		return -1;
-	if (set->init != NULL) {
-		if (set->flags & SET_F_INTERVAL &&
-		    set_to_intervals(ctx->msgs, set, set->init) < 0)
-			return -1;
-		if (do_add_setelems(ctx, &set->handle, set->init) < 0)
-			return -1;
-	}
+	if (set->init != NULL)
+		return __do_add_setelems(ctx, &set->handle, set, set->init);
+
 	return 0;
 }
 
@@ -961,6 +974,25 @@ static int do_command_insert(struct netlink_ctx *ctx, struct cmd *cmd)
 	return 0;
 }
 
+static int do_delete_setelems(struct netlink_ctx *ctx, const struct handle *h,
+			      struct expr *expr)
+{
+	struct table *table;
+	struct set *set;
+
+	table = table_lookup(h);
+	set = set_lookup(table, h->set);
+
+	if (set->flags & SET_F_INTERVAL &&
+	    set_to_intervals(ctx->msgs, set, expr) < 0)
+		return -1;
+
+	if (netlink_delete_setelems(ctx, h, expr) < 0)
+		return -1;
+
+	return 0;
+}
+
 static int do_command_delete(struct netlink_ctx *ctx, struct cmd *cmd)
 {
 	switch (cmd->obj) {
@@ -974,7 +1006,7 @@ static int do_command_delete(struct netlink_ctx *ctx, struct cmd *cmd)
 	case CMD_OBJ_SET:
 		return netlink_delete_set(ctx, &cmd->handle, &cmd->location);
 	case CMD_OBJ_SETELEM:
-		return netlink_delete_setelems(ctx, &cmd->handle, cmd->expr);
+		return do_delete_setelems(ctx, &cmd->handle, cmd->expr);
 	default:
 		BUG("invalid command object type %u\n", cmd->obj);
 	}
-- 
2.1.4

[PATCH nft 6/7] segtree: special handling for the first non-matching segment

[Pablo Neira Ayuso]

Add the first non-matching segment if the set is empty or if we are
deleting the element.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 include/expression.h |  2 +-
 src/rule.c           |  4 ++--
 src/segtree.c        | 43 +++++++++++++++++++++++++++++++++++++------
 3 files changed, 40 insertions(+), 9 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index 62a1e51..d44e804 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -365,7 +365,7 @@ extern struct expr *list_expr_alloc(const struct location *loc);
 
 extern struct expr *set_expr_alloc(const struct location *loc);
 extern int set_to_intervals(struct list_head *msgs, struct set *set,
-			    struct expr *init);
+			    struct expr *init, bool add);
 
 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 e2f15ee..049104d 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -867,7 +867,7 @@ static int __do_add_setelems(struct netlink_ctx *ctx, const struct handle *h,
 			     struct set *set, struct expr *expr)
 {
 	if (set->flags & SET_F_INTERVAL &&
-	    set_to_intervals(ctx->msgs, set, expr) < 0)
+	    set_to_intervals(ctx->msgs, set, expr, true) < 0)
 		return -1;
 
 	if (netlink_add_setelems(ctx, h, expr) < 0)
@@ -984,7 +984,7 @@ static int do_delete_setelems(struct netlink_ctx *ctx, const struct handle *h,
 	set = set_lookup(table, h->set);
 
 	if (set->flags & SET_F_INTERVAL &&
-	    set_to_intervals(ctx->msgs, set, expr) < 0)
+	    set_to_intervals(ctx->msgs, set, expr, false) < 0)
 		return -1;
 
 	if (netlink_delete_setelems(ctx, h, expr) < 0)
diff --git a/src/segtree.c b/src/segtree.c
index c0a8c28..617fabc 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -345,10 +345,37 @@ static int set_to_segtree(struct list_head *msgs, struct expr *set,
 	return 0;
 }
 
-static void segtree_linearize(struct list_head *list, struct seg_tree *tree)
+static bool segtree_needs_first_segment(const struct set *set,
+					const struct expr *init, bool add)
 {
-	struct rb_node *node, *next;
+	if (add) {
+		/* If we're adding the first element to the set, we have to
+		 * include the first segment too. In case of anonymous sets,
+		 * we always have to add the first non-matching segment.
+		 */
+		if ((set->flags & SET_F_ANONYMOUS) ||
+		    (set->init && set->init->size == 0))
+			return true;
+	} else {
+		/* If the set is empty after the removal, we have to
+		 * remove the first non-matching segment too.
+		 */
+		if (set->init && set->init->size - init->size == 0)
+			return true;
+	}
+	/* This is an update for a set that already contains elements, so don't
+	 * add the first non-matching elements otherwise we hit EEXIST.
+	 */
+	return false;
+}
+
+static void segtree_linearize(struct list_head *list, const struct set *set,
+			      const struct expr *init, struct seg_tree *tree,
+			      bool add)
+{
+	bool needs_first_segment = segtree_needs_first_segment(set, init, add);
 	struct elementary_interval *ei, *nei, *prev = NULL;
+	struct rb_node *node, *next;
 	mpz_t p, q;
 
 	mpz_init2(p, tree->keylen);
@@ -366,7 +393,7 @@ static void segtree_linearize(struct list_head *list, struct seg_tree *tree)
 			 * If the first segment doesn't begin at zero, insert a
 			 * non-matching segment to cover [0, first_left).
 			 */
-			if (mpz_cmp_ui(ei->left, 0)) {
+			if (needs_first_segment && mpz_cmp_ui(ei->left, 0)) {
 				mpz_set_ui(p, 0);
 				mpz_sub_ui(q, ei->left, 1);
 				nei = ei_alloc(p, q, NULL, EI_F_INTERVAL_END);
@@ -383,7 +410,10 @@ static void segtree_linearize(struct list_head *list, struct seg_tree *tree)
 				mpz_sub_ui(q, ei->left, 1);
 				nei = ei_alloc(p, q, NULL, EI_F_INTERVAL_END);
 				list_add_tail(&nei->list, list);
-			} else if (ei->expr->ops->type != EXPR_MAPPING) {
+			} else if (add && ei->expr->ops->type != EXPR_MAPPING) {
+				/* Merge contiguous segments only in case of
+				 * new additions.
+				 */
 				mpz_set(prev->right, ei->right);
 				ei_remove(tree, ei);
 				ei_destroy(ei);
@@ -432,7 +462,8 @@ static void set_insert_interval(struct expr *set, struct seg_tree *tree,
 	compound_expr_add(set, expr);
 }
 
-int set_to_intervals(struct list_head *errs, struct set *set, struct expr *init)
+int set_to_intervals(struct list_head *errs, struct set *set,
+		     struct expr *init, bool add)
 {
 	struct elementary_interval *ei, *next;
 	struct seg_tree tree;
@@ -441,7 +472,7 @@ int set_to_intervals(struct list_head *errs, struct set *set, struct expr *init)
 	seg_tree_init(&tree, set, init);
 	if (set_to_segtree(errs, init, &tree) < 0)
 		return -1;
-	segtree_linearize(&list, &tree);
+	segtree_linearize(&list, set, init, &tree, add);
 
 	list_for_each_entry_safe(ei, next, &list, list) {
 		if (segtree_debug()) {
-- 
2.1.4

[PATCH nft 7/7] evaluate: bail out on prefix or range to non-interval set

[Pablo Neira Ayuso]

If you declare a set with no interval flag, you get this bug message:

 # nft add element filter myset { 192.168.1.100/24 }
 BUG: invalid data expression type prefix
 nft: netlink.c:323: netlink_gen_data: Assertion `0' failed.
 Aborted

After this patch, we provide a clue to the user:

 # nft add element filter myset { 192.168.1.100/24 }
 <cmdline>:1:23-38: Error: Set member cannot be prefix, missing interval flag on declaration
 add element filter myset { 192.168.1.100/24 }
                            ^^^^^^^^^^^^^^^^

 # nft add element filter myset { 192.168.1.100-192.168.1.200 }
 <cmdline>:1:23-49: Error: Set member cannot be range, missing interval flag on declaration
 add element filter myset { 192.168.1.100-192.168.1.200 }
                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/evaluate.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/src/evaluate.c b/src/evaluate.c
index 346e34f..be4dac7 100644
--- a/src/evaluate.c
+++ b/src/evaluate.c
@@ -957,6 +957,21 @@ static int expr_evaluate_set_elem(struct eval_ctx *ctx, struct expr **expr)
 	if (expr_evaluate(ctx, &elem->key) < 0)
 		return -1;
 
+	if (ctx->set && !(ctx->set->flags & SET_F_INTERVAL)) {
+		switch (elem->key->ops->type) {
+		case EXPR_PREFIX:
+			return expr_error(ctx->msgs, elem,
+					  "Set member cannot be prefix, "
+					  "missing interval flag on declaration");
+		case EXPR_RANGE:
+			return expr_error(ctx->msgs, elem,
+					  "Set member cannot be range, "
+					  "missing interval flag on declaration");
+		default:
+			break;
+		}
+	}
+
 	elem->dtype = elem->key->dtype;
 	elem->len   = elem->key->len;
 	elem->flags = elem->key->flags;
-- 
2.1.4