[PATCH 1/5 nf,kernel] netfilter: nft_rbtree: allow adjacent intervals with dynamic updates

[PATCH 1/5 nf,kernel] netfilter: nft_rbtree: allow adjacent intervals with dynamic updates

[Pablo Neira Ayuso]

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'.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
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(-)

diff --git a/net/netfilter/nft_rbtree.c b/net/netfilter/nft_rbtree.c
index 1c30f41..063603d 100644
--- a/net/netfilter/nft_rbtree.c
+++ b/net/netfilter/nft_rbtree.c
@@ -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);
-- 
2.1.4

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

[Pablo Neira Ayuso]

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").

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

diff --git a/src/rule.c b/src/rule.c
index 18ff592..1295228 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -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;
-- 
2.1.4

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

[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.

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 060951c..86c37b4 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -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)
-- 
2.1.4

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

[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).

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 eacbb2d..55af734 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -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);
diff --git a/src/rule.c b/src/rule.c
index 1295228..8549c2b 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -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;
diff --git a/src/segtree.c b/src/segtree.c
index 86c37b4..5b1cd29 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 5/5, nft] rule: allow dynamic updates for intervals in set declarations

[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.

Closes: https://bugzilla.netfilter.org/show_bug.cgi?id=994
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/rule.c    | 13 ++++++++++++-
 src/segtree.c |  9 ++++++---
 2 files changed, 18 insertions(+), 4 deletions(-)

diff --git a/src/rule.c b/src/rule.c
index 8549c2b..a32b697 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -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;
 }
 
diff --git a/src/segtree.c b/src/segtree.c
index 5b1cd29..c05eead 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -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()) {
-- 
2.1.4