Skip to contentSkip to conversation

named sets with intervals

PATCH New Pablo Neira Ayuso 1 participant 8 messages Apr 18, 2016 netfilter

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

cover named sets with intervals

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(-)
Signature · 1 line
2.1.4
author maintainer
#1 lore raw

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

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.

---
 src/segtree.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)
src/segtree.c +6 -2
index 060951c..5b69ffb 100644
@@ -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)
Signature · 1 line
2.1.4
author maintainer
#2 lore raw

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

In reply to Pablo Neira Ayuso

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

---
 src/segtree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
src/segtree.c +1 -1
index 5b69ffb..75f02b9 100644
@@ -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
Signature · 1 line
2.1.4
author maintainer
#3 lore raw

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

In reply to 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.

---
 src/segtree.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)
src/segtree.c +8 -1
index 75f02b9..d8f98fa 100644
@@ -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)
Signature · 1 line
2.1.4
author maintainer
#4 lore raw

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

In reply to Pablo Neira Ayuso

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

---
 include/expression.h |  3 ++-
 src/rule.c           |  2 +-
 src/segtree.c        | 15 ++++++++-------
 3 files changed, 11 insertions(+), 9 deletions(-)
include/expression.h +2 -1
index 72b6f69..62a1e51 100644
@@ -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);
src/rule.c +1 -1
index b7f4a07..43a606b 100644
@@ -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;
src/segtree.c +8 -7
index d8f98fa..c0a8c28 100644
@@ -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;
Signature · 1 line
2.1.4
author maintainer
#5 lore raw

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

In reply to Pablo Neira Ayuso

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

Quoted 1 line

From do_add_set(), use netlink_add_setelems() not to try to re-add the

same elements again

---
 src/rule.c | 52 ++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 42 insertions(+), 10 deletions(-)
src/rule.c +42 -10
index 43a606b..e2f15ee 100644
@@ -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);
 	}
Signature · 1 line
2.1.4
author maintainer
#6 lore raw

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

In reply to Pablo Neira Ayuso

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

---
 include/expression.h |  2 +-
 src/rule.c           |  4 ++--
 src/segtree.c        | 43 +++++++++++++++++++++++++++++++++++++------
 3 files changed, 40 insertions(+), 9 deletions(-)
include/expression.h +1 -1
index 62a1e51..d44e804 100644
@@ -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);
src/rule.c +2 -2
index e2f15ee..049104d 100644
@@ -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)
src/segtree.c +37 -6

75 lines not on this page · raw message

Signature · 1 line
2.1.4
author maintainer
#7 lore raw

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

In reply to 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 }
                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^
---
 src/evaluate.c | 15 +++++++++++++++
 1 file changed, 15 insertions(+)
src/evaluate.c +15 -0
index 346e34f..be4dac7 100644
@@ -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;
Signature · 1 line
2.1.4