named sets with intervals
Pablo Neira Ayuso
maintainercover 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
Pablo Neira Ayuso
maintainerPATCH 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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 2/7 segtree: clone full expression from interval_map_decompose()
In reply to Pablo Neira AyusoInstead 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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 3/7 segtree: handle adjacent interval nodes from expr_value_cmp()
In reply to Pablo Neira AyusoNamed 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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 4/7 segtree: explicit initialization via set_to_intervals()
In reply to Pablo Neira AyusoAllow 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
@@ -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
@@ -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
@@ -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/7 rule: support for incremental set interval element updates
In reply to Pablo Neira AyusoIntroduce __do_add_setelems() and do_delete_setelems() to support incremental set interval element updates.
Quoted 1 line
From
do_add_set(), usenetlink_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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 6/7 segtree: special handling for the first non-matching segment
In reply to Pablo Neira AyusoAdd 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
@@ -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
@@ -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
Pablo Neira Ayuso
maintainerPATCH 7/7 evaluate: bail out on prefix or range to non-interval set
In reply to Pablo Neira AyusoIf 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.
AbortedAfter 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
@@ -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