revisit overlap/automerge codebase
Pablo Neira Ayuso
maintainerv4 cover revisit overlap/automerge codebase
Hi,
This is another iteration of the set element automerge codebase rework, posted last time in March 1st.
This series comes with a oneliner fix for Patch 2/7 "src: replace interval segment tree overlap and automerge" that sets on i->elem_flags instead of elem->elem_flags (this was breaking open intervals).
Now tests/monitor are passing fine in this batch.
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 also allows to use automerge with set element deletions.
This is passing tests/shell, tests/py and tests/monitor.
Pablo Neira Ayuso (7):
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
evaluate: allow for zero length ranges
intervals: support to partial deletion with automerge
include/Makefile.am | 2 +- include/expression.h | 7 +- include/intervals.h | 12 + include/mnl.h | 3 +- include/rbtree.h | 98 --- include/rule.h | 2 + src/Makefile.am | 2 +- src/cache.c | 6 + src/evaluate.c | 75 +- src/intervals.c | 740 ++++++++++++++++++ src/libnftables.c | 4 +- src/mergesort.c | 1 + src/mnl.c | 6 +- src/netlink.c | 1 + src/rbtree.c | 388 --------- src/rule.c | 25 +- src/segtree.c | 660 +--------------- .../shell/testcases/sets/0069interval_merge_0 | 28 + .../sets/dumps/0069interval_merge_0.nft | 9 + 19 files changed, 895 insertions(+), 1174 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 create mode 100755 tests/shell/testcases/sets/0069interval_merge_0 create mode 100644 tests/shell/testcases/sets/dumps/0069interval_merge_0.nft
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v4 1/7 src: add EXPR_F_KERNEL to identify expression in the kernel
This 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
@@ -192,6 +192,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 ,
@@ -200,6 +201,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
@@ -1286,6 +1286,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 v4 2/7 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 | 70 ++++- src/intervals.c | 392 ++++++++++++++++++++++++++ src/mergesort.c | 1 + src/rule.c | 13 +- src/segtree.c | 650 ------------------------------------------- 10 files changed, 477 insertions(+), 666 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
@@ -486,10 +486,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 +67 -3
139 lines not on this page · raw message
src/intervals.c new file +392 -0
392 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>
@@ -1495,9 +1496,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);
@@ -1522,9 +1521,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 ; }
@@ -1601,9 +1598,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 -650
662 lines not on this page · raw message
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v4 3/7 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 -------------------------------------------- 4 files changed, 488 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
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v4 4/7 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
@@ -1728,9 +1728,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;
@@ -1748,7 +1748,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
@@ -1601,7 +1601,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 v4 5/7 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 a list of elements to be purged to cmd and set objects. These elements representing outdated intervals are deleted before adding the updated ranges.
This routine splices the list of userspace and kernel elements, then it mergesorts to identify overlapping and contiguous ranges. This splice operation is undone so the set userspace cache remains consistent.
Incrementally update the elements in the cache, this allows to remove dd44081d91ce ("segtree: Fix add and delete of element in same batch").
--- include/intervals.h | 3 +- src/cache.c | 6 + src/evaluate.c | 8 +- src/intervals.c | 144 ++++++++++++++---- src/rule.c | 10 -- .../shell/testcases/sets/0069interval_merge_0 | 28 ++++ .../sets/dumps/0069interval_merge_0.nft | 9 ++ 7 files changed, 168 insertions(+), 40 deletions(-) create mode 100755 tests/shell/testcases/sets/0069interval_merge_0 create mode 100644 tests/shell/testcases/sets/dumps/0069interval_merge_0.nft
include/intervals.h +2 -1
@@ -2,7 +2,8 @@#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_automerge (struct list_head *msgs,struct cmd *cmd,struct set *set, +struct expr *init,unsigned int debug_mask);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);
src/cache.c +6 -0
@@ -19,6 +19,8 @@static unsigned int evaluate_cache_add (struct cmd *cmd,unsigned int flags) { +struct set *set; +switch (cmd->obj) {case CMD_OBJ_TABLE :if (!cmd->table)
@@ -29,6 +31,10 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)NFT_CACHE_SET |NFT_CACHE_OBJECT |NFT_CACHE_FLOWTABLE ; +list_for_each_entry (set, &cmd->table->sets, list) { +if (set->automerge) + flags |=NFT_CACHE_SETELEM_MAYBE ; + }break ;case CMD_OBJ_CHAIN :case CMD_OBJ_SET :
src/evaluate.c +5 -3
@@ -1466,10 +1466,12 @@ static int interval_set_eval(struct eval_ctx *ctx, struct set *set,switch (ctx->cmd->op) {case CMD_CREATE :case CMD_ADD : -if (set->automerge) - ret =set_automerge (ctx->msgs, set, init); -else +if (set->automerge) { + ret =set_automerge (ctx->msgs, ctx->cmd, set, init, + ctx->nft->debug_mask); + }else { ret =set_overlap (ctx->msgs, set, init); + }break ;case CMD_DELETE :set_to_range (init);
src/intervals.c +118 -26
211 lines not on this page · raw message
src/rule.c +0 -10
@@ -1476,16 +1476,6 @@ static int __do_add_elements(struct netlink_ctx *ctx, struct set *set,if (mnl_nft_setelem_add (ctx, set, expr, flags) <0 )return -1 ; -if (!set_is_anonymous (set->flags) && - set->init !=NULL && set->init != expr && - set->flags &NFT_SET_INTERVAL && - set->desc.field_count <=1 ) { -interval_map_decompose (expr); -list_splice_tail_init (&expr->expressions, &set->init->expressions); - set->init->size += expr->size; - expr->size =0 ; - } -return 0 ; }
tests/shell/testcases/sets/0069interval_merge_0 new file +28 -0
@@ -0,0 +1,28 @@ +#!/bin/bash + +set -e + +RULESET="table ip x { + set y { + type ipv4_addr + flags interval + auto-merge + elements = { 1.2.3.0, 1.2.3.255, 1.2.3.0/24, 3.3.3.3, 4.4.4.4, 4.4.4.4-4.4.4.8, 3.3.3.4, 3.3.3.5 } + } +}" + +$NFT -f - <<< $RULESET + +RULESET="table ip x { + set y { + type ipv4_addr + flags interval + auto-merge + elements = { 1.2.4.0, 3.3.3.6, 4.4.4.0/24 } + } +}" + +$NFT -f - <<< $RULESET + +$NFT add element ip x y { 1.2.3.0-1.2.4.255, 3.3.3.5, 4.4.4.1 } +$NFT add element ip x y { 1.2.3.0-1.2.4.255, 3.3.3.5, 4.4.5.0 }
tests/shell/testcases/sets/dumps/0069interval_merge_0.nft new file +9 -0
@@ -0,0 +1,9 @@ +table ip x { + set y { + type ipv4_addr + flags interval + auto-merge + elements = { 1.2.3.0-1.2.4.255, 3.3.3.3-3.3.3.6, + 4.4.4.0-4.4.5.0 } + } +}
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v4 6/7 evaluate: allow for zero length ranges
In reply to Pablo Neira AyusoAllow for ranges such as, eg. 30-30.
This is required by the new intervals.c code, which normalize constant, prefix set elements to all ranges.
--- src/evaluate.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
src/evaluate.c +1 -1
@@ -1017,7 +1017,7 @@ static int expr_evaluate_range(struct eval_ctx *ctx, struct expr **expr) left = range->left; right = range->right; -if (mpz_cmp (left->value, right->value) >=0 ) +if (mpz_cmp (left->value, right->value) >0 )return expr_error (ctx->msgs, range,"Range has zero or negative size" );datatype_set (range, left->dtype);
Signature · 1 line
2.30.2
Pablo Neira Ayuso
maintainerPATCH v4 7/7 intervals: support to partial deletion with automerge
In reply to Pablo Neira AyusoSplice the existing set element cache with the elements to be deleted and merge sort it. The elements to be deleted are identified by the EXPR_F_REMOVE flag.
The set elements to be deleted is automerged in first place if the automerge flag is set on.
There are four possible deletion scenarios:
- Exact match, eg. delete [a-b] and there is a [a-b] range in the kernel set.
- Adjust left side of range, eg. delete [a-b] from range [a-x] where x > b.
- Adjust right side of range, eg. delete [a-b] from range [x-b] where x < a.
- Split range, eg. delete [a-b] from range [x-y] where x < a and b < y.
Update nft_evaluate() to use the safe list variant since new commands are dynamically registered to the list to update ranges.
This patch also restores the set element existence check for Linux kernels <= 5.7.
--- include/expression.h | 1 + include/intervals.h | 2 + src/evaluate.c | 3 +- src/intervals.c | 256 +++++++++++++++++++++++++++++++++++++++++++ src/libnftables.c | 4 +- 5 files changed, 263 insertions(+), 3 deletions(-)
include/expression.h +1 -0
@@ -202,6 +202,7 @@ enum expr_flags {EXPR_F_BOOLEAN =0x10 ,EXPR_F_INTERVAL =0x20 ,EXPR_F_KERNEL =0x40 , + EXPR_F_REMOVE = 0x80, };#include <payload.h>
include/intervals.h +2 -0
@@ -4,6 +4,8 @@void set_to_range (struct expr *init);int set_automerge (struct list_head *msgs,struct cmd *cmd,struct set *set,struct expr *init,unsigned int debug_mask); +int set_delete (struct list_head *msgs,struct cmd *cmd,struct set *set, +struct expr *init,unsigned int debug_mask);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);
src/evaluate.c +2 -1
@@ -1474,7 +1474,8 @@ static int interval_set_eval(struct eval_ctx *ctx, struct set *set, }break ;case CMD_DELETE : -set_to_range (init); + ret =set_delete (ctx->msgs, ctx->cmd, set, init, + ctx->nft->debug_mask);break ;case CMD_GET :break ;
src/intervals.c +256 -0
262 lines not on this page · raw message
src/libnftables.c +2 -2
@@ -500,8 +500,8 @@ static int nft_evaluate(struct nft_ctx *nft, struct list_head *msgs, struct list_head *cmds) {struct nft_cache_filter *filter; +struct cmd *cmd, *next;unsigned int flags; -struct cmd *cmd; filter =nft_cache_filter_init (); flags =nft_cache_evaluate (nft, cmds, filter);
@@ -512,7 +512,7 @@ static int nft_evaluate(struct nft_ctx *nft, struct list_head *msgs,nft_cache_filter_fini (filter); -list_for_each_entry (cmd, cmds, list) { +list_for_each_entry_safe (cmd, next, cmds, list) {struct eval_ctx ectx = { .nft = nft, .msgs = msgs,
Signature · 1 line
2.30.2
Phil Sutter
reviewerRe: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
Hi Pablo,
On Tue, Apr 12, 2022 at 04:47:11PM +0200, Pablo Neira Ayuso wrote:
[...]
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 262
Quoted 13 lines
src/intervals.c +5
-0@@ -255,6 +255,262 @@ int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,return 0 ; } +static void remove_elem (struct expr *prev,struct set *set,struct expr *purge) +{ +struct expr *clone; + +if (!(prev->flags &EXPR_F_REMOVE )) {
Does prev->flags ever contain EXPR_F_REMOVE? (See below.)
Quoted 4 lines
src/intervals.c +4
-0+if (prev->flags &EXPR_F_KERNEL ) { + clone =expr_clone (prev); +list_move_tail (&clone->list, &purge->expressions); + }else {
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 276
Quoted 10 lines
src/intervals.c +10
-0+list_del (&prev->list); +expr_free (prev); + } + } +} + +static void __adjust_elem_left (struct set *set,struct expr *prev,struct expr *i, +struct expr *init) +{ + prev->flags &=EXPR_F_KERNEL ;
This looks odd. You're intentionally stripping all flags other than EXPR_F_KERNEL (if set)?
IIUC, you're just dropping EXPR_F_REMOVE if set. If so, explicit 'prev->flags &= ~EXPR_F_REMOVE' is more clear, no?
Maybe it's also irrelevant after all WRT above question.
Quoted 5 lines
src/intervals.c +5
-0+expr_free (prev->key->left); + prev->key->left =expr_get (i->key->right); +mpz_add_ui (prev->key->left->value, prev->key->left->value,1 ); +list_move (&prev->list, &init->expressions); +}
[...]
Quoted 24 lines
src/intervals.c +24
-0+static int setelem_delete (struct list_head *msgs,struct set *set, +struct expr *init,struct expr *purge, +struct expr *elems,unsigned int debug_mask) +{ +struct expr *i, *next, *prev =NULL ; +struct range range, prev_range; +int err =0 ; +mpz_t rop; + +mpz_init (prev_range.low); +mpz_init (prev_range.high); +mpz_init (range.low); +mpz_init (range.high); +mpz_init (rop); + +list_for_each_entry_safe (i, next, &elems->expressions, list) { +if (i->key->etype ==EXPR_SET_ELEM_CATCHALL ) +continue ; + +range_expr_value_low (range.low, i); +range_expr_value_high (range.high, i); + +if (!prev && i->flags &EXPR_F_REMOVE ) { +expr_error (msgs, i,"element does not exist" );
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 416
Quoted 10 lines
src/intervals.c +10
-0+ err =-1 ; + goto err; + } + +if (!(i->flags &EXPR_F_REMOVE )) { + prev = i; +mpz_set (prev_range.low, range.low); +mpz_set (prev_range.high, range.high); +continue ; + }
The loop assigns to 'prev' only if EXPR_F_REMOVE is not set.
Quoted 6 lines
src/intervals.c +6
-0+ +if (mpz_cmp (prev_range.low, range.low) ==0 && +mpz_cmp (prev_range.high, range.high) ==0 ) { +if (!(prev->flags &EXPR_F_REMOVE ) && + i->flags &EXPR_F_REMOVE ) { +list_move_tail (&prev->list, &purge->expressions);
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 432
Quoted 10 lines
src/intervals.c +10
-0+list_del (&i->list); +expr_free (i); + } + }else if (set->automerge && +setelem_adjust (set, init, purge, &prev_range, &range, prev, i) <0 ) { +expr_error (msgs, i,"element does not exist" ); + err =-1 ; + goto err; + } + prev =NULL ;
The code above may set EXPR_F_REMOVE in 'prev', but AFAICT 'prev' is not revisited within and cleared before next iteration.
Cheers, Phil
Pablo Neira Ayuso
maintainerRe: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
Quoted 12 lines · Phil Sutter
Hi Pablo,
On Tue, Apr 12, 2022 at 04:47:11PM +0200, Pablo Neira Ayuso wrote:
[...]Quoted 8 lines
src/intervals.c +0
-0@@ -255,6 +255,262 @@ int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,return 0 ; }
Quoted 7 lines
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 262
Quoted 5 lines
src/intervals.c +5
-0+static void remove_elem (struct expr *prev,struct set *set,struct expr *purge) +{ +struct expr *clone; + +if (!(prev->flags &EXPR_F_REMOVE )) {Does
prev->flagsever containEXPR_F_REMOVE? (See below.)
EXPR_F_REMOVE flag is used to specify that this element represents a deletion.
The existing list of elements in the kernel is mixed with the list of elements to be deleted, this list is merge-sorted, then we look for EXPR_F_REMOVE elements that are asking for removal of elements in the kernel.
The flag allows me to track objects, whether they are in the kernel (EXPR_F_KERNEL), they are new (no flag) or they represent an element that need to be removed from the kernel (EXPR_F_REMOVE).
Quoted 12 lines
Quoted 12 lines
src/intervals.c +12
-0+if (prev->flags &EXPR_F_KERNEL ) { + clone =expr_clone (prev); +list_move_tail (&clone->list, &purge->expressions); + }else { +list_del (&prev->list); +expr_free (prev); + } + } +} + +static void __adjust_elem_left (struct set *set,struct expr *prev,struct expr *i, +struct expr *init)
Quoted 8 lines
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 276
Quoted 2 lines
src/intervals.c +2
-0+{ + prev->flags &=EXPR_F_KERNEL ;This looks odd. You're intentionally stripping all flags other than
EXPR_F_KERNEL(if set)?
IIUC, you're just droppingEXPR_F_REMOVEif set. If so, explicit 'prev->flags&= ~EXPR_F_REMOVE' is more clear, no?
Maybe it's also irrelevant after all WRT above question.
Yes, this should be prev->flags &= ~EXPR_F_KERNEL, I'll fix it.
This element is moved to the list of elements to be added. This flag is irrelevant though at this stage, but in case you look at the list of elements to be added, you should not see EXPR_F_KERNEL there.
Quoted 34 lines
Quoted 5 lines
src/intervals.c +5
-0+expr_free (prev->key->left); + prev->key->left =expr_get (i->key->right); +mpz_add_ui (prev->key->left->value, prev->key->left->value,1 ); +list_move (&prev->list, &init->expressions); +}[...]
Quoted 28 lines
src/intervals.c +28
-0+static int setelem_delete (struct list_head *msgs,struct set *set, +struct expr *init,struct expr *purge, +struct expr *elems,unsigned int debug_mask) +{ +struct expr *i, *next, *prev =NULL ; +struct range range, prev_range; +int err =0 ; +mpz_t rop; + +mpz_init (prev_range.low); +mpz_init (prev_range.high); +mpz_init (range.low); +mpz_init (range.high); +mpz_init (rop); + +list_for_each_entry_safe (i, next, &elems->expressions, list) { +if (i->key->etype ==EXPR_SET_ELEM_CATCHALL ) +continue ; + +range_expr_value_low (range.low, i); +range_expr_value_high (range.high, i); + +if (!prev && i->flags &EXPR_F_REMOVE ) { +expr_error (msgs, i,"element does not exist" ); + err =-1 ; + goto err; + } +
Quoted 8 lines
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 416
Quoted 6 lines
src/intervals.c +6
-0+if (!(i->flags &EXPR_F_REMOVE )) { + prev = i; +mpz_set (prev_range.low, range.low); +mpz_set (prev_range.high, range.high); +continue ; + }The loop assigns to 'prev' only if
EXPR_F_REMOVEis not set.
Yes, this annotates is a element candidate to be removed.
The list of elements is merged-sorted, coming the element with EXPR_F_REMOVE before the element that needs to be removed.
Quoted 10 lines
Quoted 10 lines
src/intervals.c +10
-0+if (mpz_cmp (prev_range.low, range.low) ==0 && +mpz_cmp (prev_range.high, range.high) ==0 ) { +if (!(prev->flags &EXPR_F_REMOVE ) && + i->flags &EXPR_F_REMOVE ) { +list_move_tail (&prev->list, &purge->expressions); +list_del (&i->list); +expr_free (i); + } + }else if (set->automerge && +setelem_adjust (set, init, purge, &prev_range, &range, prev, i) <0 ) {
Quoted 8 lines
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 432
Quoted 5 lines
src/intervals.c +5
-0+expr_error (msgs, i,"element does not exist" ); + err =-1 ; + goto err; + } + prev =NULL ;The code above may set
EXPR_F_REMOVEin 'prev', but AFAICT 'prev' is not revisited within and cleared before next iteration.
Yes, it is intentional. First this annotates the element to be delete, next iteration should find a similar element with either EXPR_F_KERNEL (if already in the kernel) or no flag if it was freshly added in this batch.
Phil Sutter
reviewerRe: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
Quoted 1 line · Pablo Neira Ayuso
On Wed, Apr 13, 2022 at 02:54:34PM +0200, Phil Sutter wrote:
[...]
Quoted 11 lines
Quoted 10 lines
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 276
Quoted 4 lines
src/intervals.c +4
-0+static void __adjust_elem_left (struct set *set,struct expr *prev,struct expr *i, +struct expr *init) +{ + prev->flags &=EXPR_F_KERNEL ;This looks odd. You're intentionally stripping all flags other than
EXPR_F_KERNEL(if set)?
IIUC, you're just droppingEXPR_F_REMOVEif set. If so, explicit 'prev->flags&= ~EXPR_F_REMOVE' is more clear, no?
Maybe it's also irrelevant after all WRT above question.
Quoted 1 line
Yes, this should be
prev->flags&= ~EXPR_F_KERNEL, I'll fix it.
Ah, OK!
Quoted 3 lines
This element is moved to the list of elements to be added. This flag is irrelevant though at this stage, but in case you look at the list of elements to be added, you should not see
EXPR_F_KERNELthere.
I guess none of the flags are relevant at this point anymore since your code cleared them all and apparently passed testing? Or none of the relevant ones were set, which is my suspicion with EXPR_F_REMOVE.
[...]
Quoted 22 lines
Quoted 13 lines
Quoted 13 lines
src/intervals.c +13
-0+list_for_each_entry_safe (i, next, &elems->expressions, list) { +if (i->key->etype ==EXPR_SET_ELEM_CATCHALL ) +continue ; + +range_expr_value_low (range.low, i); +range_expr_value_high (range.high, i); + +if (!prev && i->flags &EXPR_F_REMOVE ) { +expr_error (msgs, i,"element does not exist" ); + err =-1 ; + goto err; + } +Quoted 8 lines
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 416
Quoted 6 lines
src/intervals.c +6
-0+if (!(i->flags &EXPR_F_REMOVE )) { + prev = i; +mpz_set (prev_range.low, range.low); +mpz_set (prev_range.high, range.high); +continue ; + }The loop assigns to 'prev' only if
EXPR_F_REMOVEis not set.
Quoted 4 lines
Yes, this annotates is a element candidate to be removed.
The list of elements is merged-sorted, coming the element with
EXPR_F_REMOVEbefore the element that needs to be removed.
The one with EXPR_F_REMOVE comes *after* the one to be removed, right?
My question again: Is it possible for 'prev' to have EXPR_F_REMOVE set? Maybe I miss something, but to me it looks like not although the code expects it.
Cheers, Phil
Pablo Neira Ayuso
maintainerRe: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
Quoted 49 lines · Phil Sutter
Quoted 1 line · Pablo Neira Ayuso
On Wed, Apr 13, 2022 at 02:54:34PM +0200, Phil Sutter wrote:
[...]
Quoted 11 lines
Quoted 10 lines
src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 276
Quoted 4 lines
src/intervals.c +4
-0+static void __adjust_elem_left (struct set *set,struct expr *prev,struct expr *i, +struct expr *init) +{ + prev->flags &=EXPR_F_KERNEL ;This looks odd. You're intentionally stripping all flags other than
EXPR_F_KERNEL(if set)?
IIUC, you're just droppingEXPR_F_REMOVEif set. If so, explicit 'prev->flags&= ~EXPR_F_REMOVE' is more clear, no?
Maybe it's also irrelevant after all WRT above question.Quoted 1 line
Yes, this should be
prev->flags&= ~EXPR_F_KERNEL, I'll fix it.Ah, OK!
Quoted 3 lines
This element is moved to the list of elements to be added. This flag is irrelevant though at this stage, but in case you look at the list of elements to be added, you should not see
EXPR_F_KERNELthere.I guess none of the flags are relevant at this point anymore since your code cleared them all and apparently passed testing? Or none of the relevant ones were set, which is my suspicion with
EXPR_F_REMOVE.[...]
Quoted 22 lines
Quoted 21 lines
Quoted 9 lines
src/intervals.c +9
-0+list_for_each_entry_safe (i, next, &elems->expressions, list) { +if (i->key->etype ==EXPR_SET_ELEM_CATCHALL ) +continue ; + +range_expr_value_low (range.low, i); +range_expr_value_high (range.high, i); + +if (!prev && i->flags &EXPR_F_REMOVE ) { +expr_error (msgs, i,"element does not exist" );src/intervals.c int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set, · line 416
Quoted 10 lines
src/intervals.c +10
-0+ err =-1 ; + goto err; + } + +if (!(i->flags &EXPR_F_REMOVE )) { + prev = i; +mpz_set (prev_range.low, range.low); +mpz_set (prev_range.high, range.high); +continue ; + }The loop assigns to 'prev' only if
EXPR_F_REMOVEis not set.
Quoted 6 lines
Quoted 4 lines
Yes, this annotates is a element candidate to be removed.
The list of elements is merged-sorted, coming the element with
EXPR_F_REMOVEbefore the element that needs to be removed.The one with
EXPR_F_REMOVEcomes *after* the one to be removed, right?
Right, the other way around actually.
Quoted 3 lines
My question again: Is it possible for 'prev' to have
EXPR_F_REMOVEset? Maybe I miss something, but to me it looks like not although the code expects it.
prev never has EXPR_F_REMOVE, so it points to an existing element.
Phil Sutter
reviewerRe: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
On Wed, Apr 13, 2022 at 04:27:07PM +0200, Pablo Neira Ayuso wrote:
[...]
Quoted 9 lines
Quoted 1 line
The one with
EXPR_F_REMOVEcomes *after* the one to be removed, right?Right, the other way around actually.
Quoted 3 lines
My question again: Is it possible for 'prev' to have
EXPR_F_REMOVEset? Maybe I miss something, but to me it looks like not although the code expects it.prev never has
EXPR_F_REMOVE, so it points to an existing element.
So below change should be fine?
src/intervals.c +10 -16
@@ -265,14 +265,12 @@ static void remove_elem(struct expr *prev, struct set *set, struct expr *purge) {struct expr *clone; -if (!(prev->flags &EXPR_F_REMOVE )) { -if (prev->flags &EXPR_F_KERNEL ) { - clone =expr_clone (prev); -list_move_tail (&clone->list, &purge->expressions); - }else { -list_del (&prev->list); -expr_free (prev); - } +if (prev->flags &EXPR_F_KERNEL ) { + clone =expr_clone (prev); +list_move_tail (&clone->list, &purge->expressions); + }else { +list_del (&prev->list); +expr_free (prev); } }
@@ -360,18 +358,15 @@ static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge, {if (mpz_cmp (prev_range->low, range->low) ==0 &&mpz_cmp (prev_range->high, range->high) >0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) +if (i->flags &EXPR_F_REMOVE )adjust_elem_left (set, prev, i, add, purge); }else if (mpz_cmp (prev_range->low, range->low) <0 &&mpz_cmp (prev_range->high, range->high) ==0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) +if (i->flags &EXPR_F_REMOVE )adjust_elem_right (set, prev, i, add, purge); }else if (mpz_cmp (prev_range->low, range->low) <0 &&mpz_cmp (prev_range->high, range->high) >0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) +if (i->flags &EXPR_F_REMOVE )split_range (set, prev, i, add, purge); }else {return -1 ;
@@ -417,8 +412,7 @@ static int setelem_delete(struct list_head *msgs, struct set *set,if (mpz_cmp (prev_range.low, range.low) ==0 &&mpz_cmp (prev_range.high, range.high) ==0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) { +if (i->flags &EXPR_F_REMOVE ) {list_move_tail (&prev->list, &purge->expressions);list_del (&i->list);expr_free (i);
Pablo Neira Ayuso
maintainerRe: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
Quoted 6 lines · Phil Sutter
On Wed, Apr 13, 2022 at 04:27:07PM +0200, Pablo Neira Ayuso wrote:
[...]Quoted 4 lines
Quoted 1 line
The one with
EXPR_F_REMOVEcomes *after* the one to be removed, right?Right, the other way around actually.
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
My question again: Is it possible for 'prev' to have
EXPR_F_REMOVEset? Maybe I miss something, but to me it looks like not although the code expects it.prev never has
EXPR_F_REMOVE, so it points to an existing element.So below change should be fine?
Yes, setelem_adjust() always checks for if (!(prev->flags & EXPR_F_REMOVE))
Your patch looks correct to me.
Quoted 57 lines
src/intervals.c +10
-16@@ -265,14 +265,12 @@ static void remove_elem(struct expr *prev, struct set *set, struct expr *purge) {struct expr *clone; -if (!(prev->flags &EXPR_F_REMOVE )) { -if (prev->flags &EXPR_F_KERNEL ) { - clone =expr_clone (prev); -list_move_tail (&clone->list, &purge->expressions); - }else { -list_del (&prev->list); -expr_free (prev); - } +if (prev->flags &EXPR_F_KERNEL ) { + clone =expr_clone (prev); +list_move_tail (&clone->list, &purge->expressions); + }else { +list_del (&prev->list); +expr_free (prev); } }@@ -360,18 +358,15 @@ static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge, {if (mpz_cmp (prev_range->low, range->low) ==0 &&mpz_cmp (prev_range->high, range->high) >0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) +if (i->flags &EXPR_F_REMOVE )adjust_elem_left (set, prev, i, add, purge); }else if (mpz_cmp (prev_range->low, range->low) <0 &&mpz_cmp (prev_range->high, range->high) ==0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) +if (i->flags &EXPR_F_REMOVE )adjust_elem_right (set, prev, i, add, purge); }else if (mpz_cmp (prev_range->low, range->low) <0 &&mpz_cmp (prev_range->high, range->high) >0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) +if (i->flags &EXPR_F_REMOVE )split_range (set, prev, i, add, purge); }else {return -1 ;@@ -417,8 +412,7 @@ static int setelem_delete(struct list_head *msgs, struct set *set,if (mpz_cmp (prev_range.low, range.low) ==0 &&mpz_cmp (prev_range.high, range.high) ==0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) { +if (i->flags &EXPR_F_REMOVE ) {list_move_tail (&prev->list, &purge->expressions);list_del (&i->list);expr_free (i);
Pablo Neira Ayuso
maintainerRe: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
In reply to Phil SutterQuoted 6 lines · Phil Sutter
On Wed, Apr 13, 2022 at 04:27:07PM +0200, Pablo Neira Ayuso wrote:
[...]Quoted 4 lines
Quoted 1 line
The one with
EXPR_F_REMOVEcomes *after* the one to be removed, right?Right, the other way around actually.
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
My question again: Is it possible for 'prev' to have
EXPR_F_REMOVEset? Maybe I miss something, but to me it looks like not although the code expects it.prev never has
EXPR_F_REMOVE, so it points to an existing element.So below change should be fine?
Wait.
Quoted 4 lines
src/intervals.c +0
-0
[...]
src/intervals.c static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge, · line 361
Quoted 7 lines
src/intervals.c +1
-2@@ -360,18 +358,15 @@ static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge, {if (mpz_cmp (prev_range->low, range->low) ==0 &&mpz_cmp (prev_range->high, range->high) >0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) +if (i->flags &EXPR_F_REMOVE )
This chunk is not correct.
User might ask to delete an element which does not exist.
Then, you might find two consecutive EXPR_F_REMOVE.
Only the initial chunk in this patch is fine.
Pablo Neira Ayuso
maintainerRe: [PATCH nft,v4 7/7] intervals: support to partial deletion with automerge
Quoted 32 lines · Pablo Neira Ayuso
Quoted 6 lines · Phil Sutter
On Wed, Apr 13, 2022 at 04:27:07PM +0200, Pablo Neira Ayuso wrote:
[...]Quoted 4 lines
Quoted 1 line
The one with
EXPR_F_REMOVEcomes *after* the one to be removed, right?Right, the other way around actually.
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
My question again: Is it possible for 'prev' to have
EXPR_F_REMOVEset? Maybe I miss something, but to me it looks like not although the code expects it.prev never has
EXPR_F_REMOVE, so it points to an existing element.So below change should be fine?
Wait.
Quoted 4 lines
src/intervals.c +0
-0[...]
src/intervals.c static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge, · line 361
Quoted 7 lines
src/intervals.c +1
-2@@ -360,18 +358,15 @@ static int setelem_adjust(struct set *set, struct expr *add, struct expr *purge, {if (mpz_cmp (prev_range->low, range->low) ==0 &&mpz_cmp (prev_range->high, range->high) >0 ) { -if (!(prev->flags &EXPR_F_REMOVE ) && - i->flags &EXPR_F_REMOVE ) +if (i->flags &EXPR_F_REMOVE )This chunk is not correct.
Quoted 5 lines
User might ask to delete an element which does not exist.
Then, you might find two consecutive
EXPR_F_REMOVE.Only the initial chunk in this patch is fine.
Wait, you mean prev is always !EXPR_F_REMOVE, then this should be fine.