netfilter: nft_rbtree: allow adjacent intervals with dynamic updates
Subsystems (2)
Pablo Neira Ayuso
maintainerPATCH 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 )
^^^^^^^
aNew element [ 1.2.4.0, 1.2.5.0 )
^^^^^^^^
bWhen 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 )
^^^^^^^
aNew element [ 1.2.2.0, 1.2.3.0 )
^^^^^^^^
bwill 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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 3/5 segtree: when checks when qsorting from interval_map_decompose()
In reply to Pablo Neira AyusoIf 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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 4/5 segtree: pass element expression as parameter to set_to_intervals()
In reply to Pablo Neira AyusoUse 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
@@ -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
@@ -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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 5/5 rule: allow dynamic updates for intervals in set declarations
In reply to Pablo Neira AyusoFor 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
@@ -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
@@ -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