Skip to contentSkip to conversation

netfilter: nft_rbtree: allow adjacent intervals with dynamic updates

PATCH New Pablo Neira Ayuso 1 participant 5 messages Jan 19, 2016

Subsystems (2)
lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

PATCH 1/5 netfilter: nft_rbtree: allow adjacent intervals with dynamic updates

This patch fixes dynamic element updates for intervals, since this is always returning a bogus EEXIST when comparing the high and low ends of adjacent intervals.

Moreover, when two intervals are adjacent, we have to check flags to know where to insert the new nodes in the tree.

Assuming the following scenario:

Existing element [ 1.2.3.0, 1.2.4.0 )

                                   ^^^^^^^
                                      a

New element [ 1.2.4.0, 1.2.5.0 )

                         ^^^^^^^^
                             b

When comparing 'a' and 'b', 'a' got its end-of-interval flag set, therefore they are different elements. This patch places 'b' on the left branch so the lookup finds 'b' before 'a' so the existing lookup function finds this in first place in case of exact matching (ie. for the 1.2.4.0 case).

The opposite scenario, ie:

Existing element [ 1.2.3.0, 1.2.4.0 )

                          ^^^^^^^
                             a

New element [ 1.2.2.0, 1.2.3.0 )

                                   ^^^^^^^^
                                      b

will place 'b' on the right branch, so it is placed after 'a'.

---
This approach is not very efficient since we can merge adjacent segments. In case of maps, we would need to check if the data part can actually be merged too. Anyway, we still have a central spinlock to protect the rb-tree, we should probably explore an alternative implementation.

This is attempt to resolve the existing issue in a minimalistic fashion, we have to revisit this.

 net/netfilter/nft_rbtree.c | 22 ++++++++++++++++------
 1 file changed, 16 insertions(+), 6 deletions(-)
net/netfilter/nft_rbtree.c +16 -6
index 1c30f41..063603d 100644
@@ -29,6 +29,11 @@ struct nft_rbtree_elem {
 	struct nft_set_ext	ext;
 };
 
+static bool nft_rbtree_interval_end(const struct nft_rbtree_elem *rbe)
+{
+	return nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) &&
+	       (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END);
+}
 
 static bool nft_rbtree_lookup(const struct nft_set *set, const u32 *key,
 			      const struct nft_set_ext **ext)
@@ -56,9 +61,7 @@ found:
 				parent = parent->rb_left;
 				continue;
 			}
-			if (nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) &&
-			    *nft_set_ext_flags(&rbe->ext) &
-			    NFT_SET_ELEM_INTERVAL_END)
+			if (nft_rbtree_interval_end(rbe))
 				goto out;
 			spin_unlock_bh(&nft_rbtree_lock);
 
@@ -98,9 +101,16 @@ static int __nft_rbtree_insert(const struct nft_set *set,
 		else if (d > 0)
 			p = &parent->rb_right;
 		else {
-			if (nft_set_elem_active(&rbe->ext, genmask))
-				return -EEXIST;
-			p = &parent->rb_left;
+			if (nft_set_elem_active(&rbe->ext, genmask)) {
+				if (!nft_rbtree_interval_end(rbe) &&
+				    nft_rbtree_interval_end(new))
+					p = &parent->rb_right;
+				else if (nft_rbtree_interval_end(rbe) &&
+					 !nft_rbtree_interval_end(new))
+					p = &parent->rb_left;
+				else
+					return -EEXIST;
+			}
 		}
 	}
 	rb_link_node(&new->node, parent, p);
Signature · 1 line
2.1.4
author maintainer
#1 lore raw

PATCH 2/5 rule: use netlink_add_setelems() when creating literal sets

Thus, do_add_setelems() is only used for set declarations. This change is required by the follow up patch entitled ("rule: fix use of intervals in set declarations").

---
 src/rule.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
src/rule.c +1 -1
index 18ff592..1295228 100644
@@ -876,7 +876,7 @@ static int do_add_set(struct netlink_ctx *ctx, const struct handle *h,
 		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)
+		if (netlink_add_setelems(ctx, &set->handle, set->init) < 0)
 			return -1;
 	}
 	return 0;
Signature · 1 line
2.1.4
author maintainer
#2 lore raw

PATCH 3/5 segtree: when checks when qsorting from interval_map_decompose()

In reply to Pablo Neira Ayuso

If we have two elements with the same key, check the interval flag so we make sure that the one with the end flag set (ie. closing interval) comes before the one that starts it.

This is required to decompose adjacent ranges the right way when listing sets from userspace.

---
 src/segtree.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)
src/segtree.c +8 -1
index 060951c..86c37b4 100644
@@ -483,8 +483,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
#3 lore raw

PATCH 4/5 segtree: pass element expression as parameter to set_to_intervals()

In reply to Pablo Neira Ayuso

Use the existing set element definition to build the segment tree, so we skip the elements that we already have defined in the kernel (that we have in the set->init expression list).

---
 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 eacbb2d..55af734 100644
@@ -363,7 +363,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 1295228..8549c2b 100644
@@ -874,7 +874,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 (netlink_add_setelems(ctx, &set->handle, set->init) < 0)
 			return -1;
src/segtree.c +8 -7
index 86c37b4..5b1cd29 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
#4 lore raw

PATCH 5/5 rule: allow dynamic updates for intervals in set declarations

In reply to Pablo Neira Ayuso

For example:

 # nft add table test
 # nft add set test myset { type ipv4_addr\; flags interval\; }
 # nft add element test myset { 1.2.3.0/24 }
 ... later on ...
 # nft add element test myset { 1.2.4.0/24 }

Then the listing shows:

 set myset2 {
         type ipv4_addr
         flags interval
         elements = { 1.2.3.0/24, 1.2.4.0/24}

}

If the set contains at least one element, this skips the non-matching segment 0.0.0.0, otherwise the kernel returns -EEXIST when updating the extsing set definition with (more) new elements.

---
 src/rule.c    | 13 ++++++++++++-
 src/segtree.c |  9 ++++++---
 2 files changed, 18 insertions(+), 4 deletions(-)
src/rule.c +12 -1
index 8549c2b..a32b697 100644
@@ -860,10 +860,21 @@ static int do_add_chain(struct netlink_ctx *ctx, const struct handle *h,
 }
 
 static int do_add_setelems(struct netlink_ctx *ctx, const struct handle *h,
-			   const struct expr *expr)
+			   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_add_setelems(ctx, h, expr) < 0)
 		return -1;
+
 	return 0;
 }
 
src/segtree.c +6 -3
index 5b1cd29..c05eead 100644
@@ -345,7 +345,8 @@ 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 void segtree_linearize(struct list_head *list, struct seg_tree *tree,
+			      bool needs_first_segment)
 {
 	struct rb_node *node, *next;
 	struct elementary_interval *ei, *nei, *prev = NULL;
@@ -366,7 +367,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);
@@ -441,7 +442,9 @@ 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, &tree,
+			  (set->flags & SET_F_ANONYMOUS) ?
+				true : set->init && set->init->size == 0);
 
 	list_for_each_entry_safe(ei, next, &list, list) {
 		if (segtree_debug()) {
Signature · 1 line
2.1.4