revisit overlap/automerge codebase
Pablo Neira Ayuso
maintainercover revisit overlap/automerge codebase
Hi,
This patchset removes the segment tree interval overlap/automerge codebase. This is replaced with mergesort of the set elements + check for overlaps by linearly iterating the set elements.
This is passing tests/shell and tests/py.
Pablo Neira Ayuso (5):
src: add EXPR_F_KERNEL to identify expression in the kernel
src: replace interval segment tree overlap and automerge
src: remove rbtree datastructure
mnl: update mnl_nft_setelem_del() to allow for more reuse
intervals: add support to automerge with kernel elements
include/Makefile.am | 2 +- include/expression.h | 7 +- include/intervals.h | 9 + include/mnl.h | 3 +- include/rbtree.h | 98 ------- include/rule.h | 3 + src/Makefile.am | 2 +- src/cache.c | 3 +- src/evaluate.c | 50 +++- src/intervals.c | 413 +++++++++++++++++++++++++++ src/mergesort.c | 1 + src/mnl.c | 6 +- src/netlink.c | 1 + src/rbtree.c | 388 ------------------------- src/rule.c | 25 +- src/segtree.c | 660 +------------------------------------------ 16 files changed, 510 insertions(+), 1161 deletions(-) create mode 100644 include/intervals.h delete mode 100644 include/rbtree.h create mode 100644 src/intervals.c delete mode 100644 src/rbtree.c
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 1/1 intervals: add support to automerge with kernel elements
Extend the interval codebase to support for merging elements in the kernel with userspace element updates.
Add EXPR_F_REMOVE flag to specify that a range needs to be removed due to update (e.g. the range has been extended).
Add a list of elements to be purged to set objects. These elements representing outdated intervals are deleted before adding the updated ranged.
This routine splices the list of userspace and kernel elements, then it mergesorts to identify overlapping and contiguous ranges.
--- include/expression.h | 1 + include/rule.h | 1 + src/cache.c | 3 +- src/intervals.c | 77 ++++++++++++++++++++++++++++++++++---------- src/rule.c | 10 ++++++ 5 files changed, 74 insertions(+), 18 deletions(-)
include/expression.h +1 -0
@@ -200,6 +200,7 @@ enum expr_flags {EXPR_F_BOOLEAN =0x10 ,EXPR_F_INTERVAL =0x20 ,EXPR_F_KERNEL =0x40 , + EXPR_F_REMOVE = 0x80, };#include <payload.h>
include/rule.h +1 -0
@@ -348,6 +348,7 @@ struct set {uint32_t objtype;struct set *existing_set;struct expr *init; +struct expr *purge;struct expr *rg_cache;uint32_t policy;struct list_head stmt_list;
src/cache.c +2 -1
@@ -28,7 +28,8 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)NFT_CACHE_CHAIN |NFT_CACHE_SET |NFT_CACHE_OBJECT | -NFT_CACHE_FLOWTABLE ; +NFT_CACHE_FLOWTABLE | +NFT_CACHE_SETELEM_MAYBE ;break ;case CMD_OBJ_CHAIN :case CMD_OBJ_SET :
src/intervals.c +60 -17
128 lines not on this page · raw message
src/rule.c +10 -0
@@ -192,6 +192,8 @@ void set_free(struct set *set)return ;if (set->init !=NULL )expr_free (set->init); +if (set->purge) +expr_free (set->purge);if (set->comment)xfree (set->comment);handle_free (&set->handle);
@@ -1470,6 +1472,14 @@ static int __do_add_elements(struct netlink_ctx *ctx, struct set *set, struct expr *expr, uint32_t flags) { expr->set_flags |= set->flags; + +if (set->purge) { +if (set_to_intervals (set, set->purge, false) <0 ) +return -1 ; +if (mnl_nft_setelem_del (ctx, &set->handle, set->purge) <0 ) +return -1 ; + } +if (mnl_nft_setelem_add (ctx, set, expr, flags) <0 )return -1 ;
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 1/5 src: add EXPR_F_KERNEL to identify expression in the kernel
In reply to Pablo Neira AyusoThis allows to identify the set elements that reside in the kernel.
--- include/expression.h | 2 ++ src/netlink.c | 1 + src/segtree.c | 10 ++++++++-- 3 files changed, 11 insertions(+), 2 deletions(-)
include/expression.h +2 -0
@@ -190,6 +190,7 @@ const struct expr_ops *expr_ops_by_type(enum expr_types etype);* @EXPR_F_INTERVAL_END: set member ends an open interval * @EXPR_F_BOOLEAN: expression is boolean (set by relational expr on LHS) * @EXPR_F_INTERVAL: expression describes a interval +* @EXPR_F_KERNEL: expression resides in the kernel */ enum expr_flags {EXPR_F_CONSTANT =0x1 ,
@@ -198,6 +199,7 @@ enum expr_flags {EXPR_F_INTERVAL_END =0x8 ,EXPR_F_BOOLEAN =0x10 ,EXPR_F_INTERVAL =0x20 , + EXPR_F_KERNEL = 0x40, };#include <payload.h>
src/netlink.c +1 -0
@@ -1273,6 +1273,7 @@ key_end: } expr =set_elem_expr_alloc (&netlink_location, key); + expr->flags |=EXPR_F_KERNEL ;if (nftnl_set_elem_is_set (nlse,NFTNL_SET_ELEM_TIMEOUT )) expr->timeout =nftnl_set_elem_get_u64 (nlse,NFTNL_SET_ELEM_TIMEOUT );
src/segtree.c +8 -2
@@ -1060,9 +1060,10 @@ void interval_map_decompose(struct expr *set)mpz_and (p,expr_value (low)->value, range); -if (!mpz_cmp_ui (range,0 )) +if (!mpz_cmp_ui (range,0 )) { + low->flags |=EXPR_F_KERNEL ;compound_expr_add (set,expr_get (low)); -else if ((!range_is_prefix (range) || + }else if ((!range_is_prefix (range) || !(i->dtype->flags &DTYPE_F_PREFIX )) ||mpz_cmp_ui (p,0 )) {struct expr *tmp;
@@ -1087,6 +1088,7 @@ void interval_map_decompose(struct expr *set) }else {interval_expr_copy (tmp, low); } + tmp->flags |=EXPR_F_KERNEL ;compound_expr_add (set, tmp); }else {
@@ -1109,6 +1111,7 @@ void interval_map_decompose(struct expr *set) }else {interval_expr_copy (prefix, low); } + prefix->flags |=EXPR_F_KERNEL ;compound_expr_add (set, prefix); }
@@ -1134,6 +1137,7 @@ void interval_map_decompose(struct expr *set) i =range_expr_alloc (&low->location,expr_clone (expr_value (low)), i); i =set_elem_expr_alloc (&low->location, i); +if (low->etype ==EXPR_MAPPING ) { i =mapping_expr_alloc (&i->location, i,expr_clone (low->right));
@@ -1141,6 +1145,8 @@ void interval_map_decompose(struct expr *set) }else {interval_expr_copy (i, low); } + i->flags |=EXPR_F_KERNEL ; +expr_free (low); }
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 2/5 src: replace interval segment tree overlap and automerge
In reply to Pablo Neira AyusoThis is a rewrite of the segtree interval codebase.
This patch now splits the original set_to_interval() function in three routines:
- add set_automerge() to merge overlapping and contiguous ranges. The elements, expressed either as single value, prefix and ranges are all first normalized to ranges. This elements expressed as ranges are mergesorted. Then, there is a linear list inspection to check for merge candidates. This code only merges elements in the same batch, ie. it does not merge elements in the kernela and the userspace batch.
- add set_overlap() to check for overlapping set elements. Linux kernel >= 5.7 already checks for overlaps, older kernels still needs this code. This code checks for two conflict types:
1) between elements in this batch.
2) between elements in this batch and kernelspace.
The elements in the kernel are temporarily merged into the list of elements in the batch to check for this overlaps. The EXPR_F_KERNEL flag allows us to restore the set cache after the overlap check has been performed.
- set_to_interval() now only transforms set elements, expressed as range e.g. [a,b], to individual set elements using the EXPR_F_INTERVAL_END flag notation to represent e.g. [a,b+1), where b+1 has the EXPR_F_INTERVAL_END flag set on.
More relevant updates:
- The overlap and automerge routines are now performed in the evaluation phase.
- The userspace set object representation now stores a reference to the existing kernel set object (in case there is already a set with this same name in the kernel). This is required by the new overlap and automerge approach.
--- include/Makefile.am | 1 + include/expression.h | 4 - include/intervals.h | 9 + include/rule.h | 2 + src/Makefile.am | 1 + src/evaluate.c | 50 +++- src/intervals.c | 370 ++++++++++++++++++++++++ src/mergesort.c | 1 + src/rule.c | 13 +- src/segtree.c | 649 ------------------------------------------- 10 files changed, 436 insertions(+), 664 deletions(-) create mode 100644 include/intervals.h create mode 100644 src/intervals.c
include/Makefile.am +1 -0
@@ -8,6 +8,7 @@ noinst_HEADERS = cli.h \ expression.h \ fib.h \ hash.h \ + intervals.h \ ipopt.h \ json.h \ mini-gmp.h \
include/expression.h +0 -4
@@ -484,10 +484,6 @@ extern struct expr *list_expr_alloc(const struct location *loc);extern struct expr *set_expr_alloc (const struct location *loc,const struct set *set); -extern int set_to_intervals (struct list_head *msgs,struct set *set, -struct expr *init,bool add, -unsigned int debug_mask,bool merge, -struct output_ctx *octx);extern void concat_range_aggregate (struct expr *set);extern void interval_map_decompose (struct expr *set);
include/intervals.h new file +9 -0
@@ -0,0 +1,9 @@ +#ifndef NFTABLES_INTERVALS_H +#define NFTABLES_INTERVALS_H + +void set_to_range (struct expr *init); +int set_automerge (struct list_head *msgs,struct set *set,struct expr *init); +int set_overlap (struct list_head *msgs,struct set *set,struct expr *init); +int set_to_intervals (const struct set *set,struct expr *init,bool add); + +#endif
include/rule.h +2 -0
@@ -324,6 +324,7 @@ void rule_stmt_insert_at(struct rule *rule, struct stmt *nstmt,* @key: key expression (data type, length)) * @data: mapping data expression * @objtype: mapping object type +* @existing_set: reference to existing set in the kernel * @init: initializer * @rg_cache: cached range element (left) * @policy: set mechanism policy
@@ -345,6 +346,7 @@ struct set {struct expr *key;struct expr *data;uint32_t objtype; +struct set *existing_set;struct expr *init;struct expr *rg_cache;uint32_t policy;
src/Makefile.am +1 -0
@@ -48,6 +48,7 @@ libnftables_la_SOURCES = \ exthdr.c \ fib.c \ hash.c \ + intervals.c \ ipopt.c \ meta.c \ rt.c \
src/evaluate.c +48 -2
94 lines not on this page · raw message
src/intervals.c new file +370 -0
370 lines not on this page · raw message
src/mergesort.c +1 -0
@@ -36,6 +36,7 @@ static void expr_msort_value(const struct expr *expr, mpz_t value)break ;case EXPR_BINOP :case EXPR_MAPPING : +case EXPR_RANGE :expr_msort_value (expr->left, value);break ;case EXPR_VALUE :
src/rule.c +4 -9
@@ -26,6 +26,7 @@#include <json.h> #include <cache.h> #include <owner.h> +#include <intervals.h> #include <libnftnl/common.h> #include <libnftnl/ruleset.h>
@@ -1492,9 +1493,7 @@ static int do_add_elements(struct netlink_ctx *ctx, struct cmd *cmd,struct set *set = cmd->elem.set;if (set_is_non_concat_range (set) && -set_to_intervals (ctx->msgs, set, init, true, - ctx->nft->debug_mask, set->automerge, - &ctx->nft->output) <0 ) +set_to_intervals (set, init, true) <0 )return -1 ;return __do_add_elements (ctx, set, init, flags);
@@ -1519,9 +1518,7 @@ static int do_add_set(struct netlink_ctx *ctx, struct cmd *cmd,* comes too late which might result in spurious ENFILE errors. */ if (set_is_non_concat_range (set) && -set_to_intervals (ctx->msgs, set, set->init, true, - ctx->nft->debug_mask, set->automerge, - &ctx->nft->output) <0 ) +set_to_intervals (set, set->init, true) <0 )return -1 ; }
@@ -1598,9 +1595,7 @@ static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd)struct set *set = cmd->elem.set;if (set_is_non_concat_range (set) && -set_to_intervals (ctx->msgs, set, expr, false, - ctx->nft->debug_mask, set->automerge, - &ctx->nft->output) <0 ) +set_to_intervals (set, expr, false) <0 )return -1 ;if (mnl_nft_setelem_del (ctx, cmd) <0 )
src/segtree.c +0 -649
661 lines not on this page · raw message
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 3/5 src: remove rbtree datastructure
In reply to Pablo Neira AyusoNot used by anyone anymore, remove it.
--- include/Makefile.am | 1 - include/rbtree.h | 98 ----------- src/Makefile.am | 1 - src/rbtree.c | 388 -------------------------------------------- src/segtree.c | 1 - 5 files changed, 489 deletions(-) delete mode 100644 include/rbtree.h delete mode 100644 src/rbtree.c
include/Makefile.am +0 -1
@@ -17,7 +17,6 @@ noinst_HEADERS = cli.h \ mnl.h \ nftables.h \ payload.h \ - rbtree.h \ tcpopt.h \ statement.h \ ct.h \
include/rbtree.h deleted +0 -98
98 lines not on this page · raw message
src/Makefile.am +0 -1
@@ -62,7 +62,6 @@ libnftables_la_SOURCES = \ monitor.c \ owner.c \ segtree.c \ - rbtree.c \ gmputil.c \ utils.c \ erec.c \
src/rbtree.c deleted +0 -388
388 lines not on this page · raw message
src/segtree.c +0 -1
@@ -19,7 +19,6 @@#include <expression.h> #include <gmputil.h> #include <utils.h> -#include <rbtree.h> static void interval_expr_copy (struct expr *dst,struct expr *src) {
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 4/5 mnl: update mnl_nft_setelem_del() to allow for more reuse
In reply to Pablo Neira AyusoPass handle and element list as parameters to allow for code reuse.
--- include/mnl.h | 3 ++- src/mnl.c | 6 +++--- src/rule.c | 2 +- 3 files changed, 6 insertions(+), 5 deletions(-)
include/mnl.h +2 -1
@@ -62,7 +62,8 @@ struct nftnl_set_list *mnl_nft_set_dump(struct netlink_ctx *ctx, int family,int mnl_nft_setelem_add (struct netlink_ctx *ctx,const struct set *set,const struct expr *expr,unsigned int flags); -int mnl_nft_setelem_del (struct netlink_ctx *ctx,const struct cmd *cmd); +int mnl_nft_setelem_del (struct netlink_ctx *ctx,const struct handle *h, +const struct expr *init);int mnl_nft_setelem_flush (struct netlink_ctx *ctx,const struct cmd *cmd);int mnl_nft_setelem_get (struct netlink_ctx *ctx,struct nftnl_set *nls); struct nftnl_set *mnl_nft_setelem_get_one(struct netlink_ctx *ctx,
src/mnl.c +3 -3
@@ -1730,9 +1730,9 @@ int mnl_nft_setelem_flush(struct netlink_ctx *ctx, const struct cmd *cmd)return 0 ; } -int mnl_nft_setelem_del (struct netlink_ctx *ctx,const struct cmd *cmd) +int mnl_nft_setelem_del (struct netlink_ctx *ctx,const struct handle *h, +const struct expr *init) { -const struct handle *h = &cmd->handle;struct nftnl_set *nls;int err;
@@ -1750,7 +1750,7 @@ int mnl_nft_setelem_del(struct netlink_ctx *ctx, const struct cmd *cmd)netlink_dump_set (nls, ctx); err =mnl_nft_setelem_batch (nls, ctx->batch,NFT_MSG_DELSETELEM ,0 , - ctx->seqnum, cmd->expr, ctx); + ctx->seqnum, init, ctx);nftnl_set_free (nls);return err;
src/rule.c +1 -1
@@ -1598,7 +1598,7 @@ static int do_delete_setelems(struct netlink_ctx *ctx, struct cmd *cmd) set_to_intervals(set, expr, false) < 0)return -1 ; -if (mnl_nft_setelem_del (ctx, cmd) <0 ) +if (mnl_nft_setelem_del (ctx, &cmd->handle, cmd->elem.expr) <0 )return -1 ;return 0 ;
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH 5/5 intervals: add support to automerge with kernel elements
In reply to Pablo Neira AyusoExtend the interval codebase to support for merging elements in the kernel with userspace element updates.
Add EXPR_F_REMOVE flag to specify that a range needs to be removed due to update (e.g. the range has been extended).
Add a list of elements to be purged to set objects. These elements representing outdated intervals are deleted before adding the updated ranged.
This routine splices the list of userspace and kernel elements, then it mergesorts to identify overlapping and contiguous ranges.
--- include/expression.h | 1 + include/rule.h | 1 + src/cache.c | 3 +- src/intervals.c | 77 ++++++++++++++++++++++++++++++++++---------- src/rule.c | 10 ++++++ 5 files changed, 74 insertions(+), 18 deletions(-)
include/expression.h +1 -0
@@ -200,6 +200,7 @@ enum expr_flags {EXPR_F_BOOLEAN =0x10 ,EXPR_F_INTERVAL =0x20 ,EXPR_F_KERNEL =0x40 , + EXPR_F_REMOVE = 0x80, };#include <payload.h>
include/rule.h +1 -0
@@ -348,6 +348,7 @@ struct set {uint32_t objtype;struct set *existing_set;struct expr *init; +struct expr *purge;struct expr *rg_cache;uint32_t policy;struct list_head stmt_list;
src/cache.c +2 -1
@@ -28,7 +28,8 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)NFT_CACHE_CHAIN |NFT_CACHE_SET |NFT_CACHE_OBJECT | -NFT_CACHE_FLOWTABLE ; +NFT_CACHE_FLOWTABLE | +NFT_CACHE_SETELEM_MAYBE ;break ;case CMD_OBJ_CHAIN :case CMD_OBJ_SET :
src/intervals.c +60 -17
128 lines not on this page · raw message
src/rule.c +10 -0
@@ -192,6 +192,8 @@ void set_free(struct set *set)return ;if (set->init !=NULL )expr_free (set->init); +if (set->purge) +expr_free (set->purge);if (set->comment)xfree (set->comment);handle_free (&set->handle);
@@ -1470,6 +1472,14 @@ static int __do_add_elements(struct netlink_ctx *ctx, struct set *set, struct expr *expr, uint32_t flags) { expr->set_flags |= set->flags; + +if (set->purge) { +if (set_to_intervals (set, set->purge, false) <0 ) +return -1 ; +if (mnl_nft_setelem_del (ctx, &set->handle, set->purge) <0 ) +return -1 ; + } +if (mnl_nft_setelem_add (ctx, set, expr, flags) <0 )return -1 ;
Signature · 1 line
2.30.2