* [nft PATCH 1/4] segtree: Drop needless insertion in ei_insert()
2020-01-23 14:30 [nft PATCH 0/4] Covscan-induced review of ei_insert() Phil Sutter
@ 2020-01-23 14:30 ` Phil Sutter
2020-01-28 11:22 ` Pablo Neira Ayuso
2020-01-23 14:30 ` [nft PATCH 2/4] segtree: Drop dead code " Phil Sutter
` (2 subsequent siblings)
3 siblings, 1 reply; 12+ messages in thread
From: Phil Sutter @ 2020-01-23 14:30 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel, Florian Westphal
Code checks whether for two new ranges one fully includes the other. If
so, it would add the contained one only for segtree_linearize() to later
omit the redundant items.
Instead just drop the contained item (which will always come last
because caller orders the new elements in beforehand).
Signed-off-by: Phil Sutter <phil@nwl.cc>
---
src/segtree.c | 25 ++-----------------------
1 file changed, 2 insertions(+), 23 deletions(-)
diff --git a/src/segtree.c b/src/segtree.c
index e8e32412f3a41..aa1f1c38d789c 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -191,9 +191,6 @@ static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
struct elementary_interval *new, bool merge)
{
struct elementary_interval *lei, *rei;
- mpz_t p;
-
- mpz_init2(p, tree->keylen);
/*
* Lookup the intervals containing the left and right endpoints.
@@ -207,25 +204,9 @@ static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
if (lei != NULL && rei != NULL && lei == rei) {
if (!merge)
goto err;
- /*
- * The new interval is entirely contained in the same interval,
- * split it into two parts:
- *
- * [lei_left, new_left) and (new_right, rei_right]
- */
- if (segtree_debug(tree->debug_mask))
- pr_gmp_debug("split [%Zx %Zx]\n", lei->left, lei->right);
- ei_remove(tree, lei);
-
- mpz_sub_ui(p, new->left, 1);
- if (mpz_cmp(lei->left, p) <= 0)
- __ei_insert(tree, ei_alloc(lei->left, p, lei->expr, 0));
-
- mpz_add_ui(p, new->right, 1);
- if (mpz_cmp(p, rei->right) < 0)
- __ei_insert(tree, ei_alloc(p, rei->right, lei->expr, 0));
- ei_destroy(lei);
+ ei_destroy(new);
+ return 0;
} else {
if (lei != NULL) {
if (!merge)
@@ -271,8 +252,6 @@ static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
__ei_insert(tree, new);
- mpz_clear(p);
-
return 0;
err:
errno = EEXIST;
--
2.24.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [nft PATCH 1/4] segtree: Drop needless insertion in ei_insert()
2020-01-23 14:30 ` [nft PATCH 1/4] segtree: Drop needless insertion in ei_insert() Phil Sutter
@ 2020-01-28 11:22 ` Pablo Neira Ayuso
0 siblings, 0 replies; 12+ messages in thread
From: Pablo Neira Ayuso @ 2020-01-28 11:22 UTC (permalink / raw)
To: Phil Sutter; +Cc: netfilter-devel, Florian Westphal
On Thu, Jan 23, 2020 at 03:30:46PM +0100, Phil Sutter wrote:
> Code checks whether for two new ranges one fully includes the other. If
> so, it would add the contained one only for segtree_linearize() to later
> omit the redundant items.
>
> Instead just drop the contained item (which will always come last
> because caller orders the new elements in beforehand).
>
> Signed-off-by: Phil Sutter <phil@nwl.cc>
I would probably append this to the patch description.
* The auto-merge feature for sets merges what it has just been split
by this code thereafter, so it turns this code into no-op.
* The auto-merge feature is not available for maps at this stage.
This code allows to split intervals that have a different rhs mapping.
This could be used in that case, but I find this feature confusing
userwise.
Acked-by: Pablo Neira Ayuso <pablo@netfilter.org>
^ permalink raw reply [flat|nested] 12+ messages in thread
* [nft PATCH 2/4] segtree: Drop dead code in ei_insert()
2020-01-23 14:30 [nft PATCH 0/4] Covscan-induced review of ei_insert() Phil Sutter
2020-01-23 14:30 ` [nft PATCH 1/4] segtree: Drop needless insertion in ei_insert() Phil Sutter
@ 2020-01-23 14:30 ` Phil Sutter
2020-01-28 11:24 ` Pablo Neira Ayuso
2020-01-23 14:30 ` [nft PATCH 3/4] segtree: Simplify overlap case " Phil Sutter
2020-01-23 14:30 ` [nft PATCH 4/4] segtree: Refactor ei_insert() Phil Sutter
3 siblings, 1 reply; 12+ messages in thread
From: Phil Sutter @ 2020-01-23 14:30 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel, Florian Westphal
Caller sorts new items to be added, therefore when checking for overlaps
the current range can only overlap on lower end. Drop the check for
upper end overlap.
Signed-off-by: Phil Sutter <phil@nwl.cc>
---
src/segtree.c | 20 --------------------
1 file changed, 20 deletions(-)
diff --git a/src/segtree.c b/src/segtree.c
index aa1f1c38d789c..47e326533ac39 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -228,26 +228,6 @@ static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
ei_destroy(lei);
}
}
- if (rei != NULL) {
- if (!merge)
- goto err;
- /*
- * Right endpoint is within rei, adjust it so we have:
- *
- * [new_left, new_right](new_right, rei_right]
- */
- if (segtree_debug(tree->debug_mask)) {
- pr_gmp_debug("adjust right [%Zx %Zx]\n",
- rei->left, rei->right);
- }
-
- mpz_add_ui(rei->left, new->right, 1);
- mpz_sub(rei->size, rei->right, rei->left);
- if (mpz_sgn(rei->size) < 0) {
- ei_remove(tree, rei);
- ei_destroy(rei);
- }
- }
}
__ei_insert(tree, new);
--
2.24.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [nft PATCH 2/4] segtree: Drop dead code in ei_insert()
2020-01-23 14:30 ` [nft PATCH 2/4] segtree: Drop dead code " Phil Sutter
@ 2020-01-28 11:24 ` Pablo Neira Ayuso
0 siblings, 0 replies; 12+ messages in thread
From: Pablo Neira Ayuso @ 2020-01-28 11:24 UTC (permalink / raw)
To: Phil Sutter; +Cc: netfilter-devel, Florian Westphal
On Thu, Jan 23, 2020 at 03:30:47PM +0100, Phil Sutter wrote:
> Caller sorts new items to be added, therefore when checking for overlaps
> the current range can only overlap on lower end. Drop the check for
> upper end overlap.
>
> Signed-off-by: Phil Sutter <phil@nwl.cc>
Acked-by: Pablo Neira Ayuso <pablo@netfilter.org>
The iteration over the sorted array guarantees there cannot be an
interval.
^ permalink raw reply [flat|nested] 12+ messages in thread
* [nft PATCH 3/4] segtree: Simplify overlap case in ei_insert()
2020-01-23 14:30 [nft PATCH 0/4] Covscan-induced review of ei_insert() Phil Sutter
2020-01-23 14:30 ` [nft PATCH 1/4] segtree: Drop needless insertion in ei_insert() Phil Sutter
2020-01-23 14:30 ` [nft PATCH 2/4] segtree: Drop dead code " Phil Sutter
@ 2020-01-23 14:30 ` Phil Sutter
2020-01-28 11:29 ` Pablo Neira Ayuso
2020-01-23 14:30 ` [nft PATCH 4/4] segtree: Refactor ei_insert() Phil Sutter
3 siblings, 1 reply; 12+ messages in thread
From: Phil Sutter @ 2020-01-23 14:30 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel, Florian Westphal
Since upper boundary overlaps can't happen, lower boundary overlaps may
simply be resolved by adjusting the existing range's upper boundary to
that of the new one instead of adding elements which are later dropped
again.
Signed-off-by: Phil Sutter <phil@nwl.cc>
---
src/segtree.c | 11 ++++-------
1 file changed, 4 insertions(+), 7 deletions(-)
diff --git a/src/segtree.c b/src/segtree.c
index 47e326533ac39..3c0989e76093a 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -214,19 +214,16 @@ static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
/*
* Left endpoint is within lei, adjust it so we have:
*
- * [lei_left, new_left)[new_left, new_right]
+ * [lei_left, new_right]
*/
if (segtree_debug(tree->debug_mask)) {
pr_gmp_debug("adjust left [%Zx %Zx]\n",
lei->left, lei->right);
}
- mpz_sub_ui(lei->right, new->left, 1);
- mpz_sub(lei->size, lei->right, lei->left);
- if (mpz_sgn(lei->size) < 0) {
- ei_remove(tree, lei);
- ei_destroy(lei);
- }
+ mpz_set(lei->right, new->right);
+ ei_destroy(new);
+ return 0;
}
}
--
2.24.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [nft PATCH 3/4] segtree: Simplify overlap case in ei_insert()
2020-01-23 14:30 ` [nft PATCH 3/4] segtree: Simplify overlap case " Phil Sutter
@ 2020-01-28 11:29 ` Pablo Neira Ayuso
0 siblings, 0 replies; 12+ messages in thread
From: Pablo Neira Ayuso @ 2020-01-28 11:29 UTC (permalink / raw)
To: Phil Sutter; +Cc: netfilter-devel, Florian Westphal
On Thu, Jan 23, 2020 at 03:30:48PM +0100, Phil Sutter wrote:
> Since upper boundary overlaps can't happen, lower boundary overlaps may
> simply be resolved by adjusting the existing range's upper boundary to
> that of the new one instead of adding elements which are later dropped
> again.
I would append to this description that this only happens if
auto-merge is set on.
> Signed-off-by: Phil Sutter <phil@nwl.cc>
Acked-by: Pablo Neira Ayuso <pablo@netfilter.org>
^ permalink raw reply [flat|nested] 12+ messages in thread
* [nft PATCH 4/4] segtree: Refactor ei_insert()
2020-01-23 14:30 [nft PATCH 0/4] Covscan-induced review of ei_insert() Phil Sutter
` (2 preceding siblings ...)
2020-01-23 14:30 ` [nft PATCH 3/4] segtree: Simplify overlap case " Phil Sutter
@ 2020-01-23 14:30 ` Phil Sutter
2020-01-28 12:23 ` Pablo Neira Ayuso
3 siblings, 1 reply; 12+ messages in thread
From: Phil Sutter @ 2020-01-23 14:30 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel, Florian Westphal
With all simplifications in place, reorder the code to streamline it
further. Apart from making the second call to ei_lookup() conditional,
debug output is slightly enhanced.
Signed-off-by: Phil Sutter <phil@nwl.cc>
---
src/segtree.c | 63 +++++++++++++++++++++++----------------------------
1 file changed, 28 insertions(+), 35 deletions(-)
diff --git a/src/segtree.c b/src/segtree.c
index 3c0989e76093a..edec9f4ebf174 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -192,48 +192,41 @@ static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
{
struct elementary_interval *lei, *rei;
- /*
- * Lookup the intervals containing the left and right endpoints.
- */
lei = ei_lookup(tree, new->left);
- rei = ei_lookup(tree, new->right);
-
- if (segtree_debug(tree->debug_mask))
- pr_gmp_debug("insert: [%Zx %Zx]\n", new->left, new->right);
-
- if (lei != NULL && rei != NULL && lei == rei) {
- if (!merge)
- goto err;
-
- ei_destroy(new);
+ if (lei == NULL) {
+ /* no overlaps, just add the new interval */
+ if (segtree_debug(tree->debug_mask))
+ pr_gmp_debug("insert: [%Zx %Zx]\n",
+ new->left, new->right);
+ __ei_insert(tree, new);
return 0;
- } else {
- if (lei != NULL) {
- if (!merge)
- goto err;
- /*
- * Left endpoint is within lei, adjust it so we have:
- *
- * [lei_left, new_right]
- */
- if (segtree_debug(tree->debug_mask)) {
- pr_gmp_debug("adjust left [%Zx %Zx]\n",
- lei->left, lei->right);
- }
+ }
- mpz_set(lei->right, new->right);
- ei_destroy(new);
- return 0;
- }
+ if (!merge) {
+ errno = EEXIST;
+ return expr_binary_error(msgs, lei->expr, new->expr,
+ "conflicting intervals specified");
}
- __ei_insert(tree, new);
+ /* caller sorted intervals, so rei is either equal to lei or NULL */
+ rei = ei_lookup(tree, new->right);
+ if (rei != lei) {
+ /*
+ * Left endpoint is within lei, adjust it so we have:
+ *
+ * [lei_left, new_right]
+ */
+ if (segtree_debug(tree->debug_mask))
+ pr_gmp_debug("adjust right: [%Zx %Zx]\n",
+ lei->left, lei->right);
+ mpz_set(lei->right, new->right);
+ } else if (segtree_debug(tree->debug_mask)) {
+ pr_gmp_debug("skip new: [%Zx %Zx] for old: [%Zx %Zx]\n",
+ new->left, new->right, lei->left, lei->right);
+ }
+ ei_destroy(new);
return 0;
-err:
- errno = EEXIST;
- return expr_binary_error(msgs, lei->expr, new->expr,
- "conflicting intervals specified");
}
/*
--
2.24.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [nft PATCH 4/4] segtree: Refactor ei_insert()
2020-01-23 14:30 ` [nft PATCH 4/4] segtree: Refactor ei_insert() Phil Sutter
@ 2020-01-28 12:23 ` Pablo Neira Ayuso
2020-01-28 14:14 ` Phil Sutter
0 siblings, 1 reply; 12+ messages in thread
From: Pablo Neira Ayuso @ 2020-01-28 12:23 UTC (permalink / raw)
To: Phil Sutter; +Cc: netfilter-devel, Florian Westphal
On Thu, Jan 23, 2020 at 03:30:49PM +0100, Phil Sutter wrote:
> With all simplifications in place, reorder the code to streamline it
> further. Apart from making the second call to ei_lookup() conditional,
> debug output is slightly enhanced.
>
> Signed-off-by: Phil Sutter <phil@nwl.cc>
> ---
> src/segtree.c | 63 +++++++++++++++++++++++----------------------------
> 1 file changed, 28 insertions(+), 35 deletions(-)
>
> diff --git a/src/segtree.c b/src/segtree.c
> index 3c0989e76093a..edec9f4ebf174 100644
> --- a/src/segtree.c
> +++ b/src/segtree.c
> @@ -192,48 +192,41 @@ static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
> {
> struct elementary_interval *lei, *rei;
>
> - /*
> - * Lookup the intervals containing the left and right endpoints.
> - */
> lei = ei_lookup(tree, new->left);
> - rei = ei_lookup(tree, new->right);
> -
> - if (segtree_debug(tree->debug_mask))
> - pr_gmp_debug("insert: [%Zx %Zx]\n", new->left, new->right);
> -
> - if (lei != NULL && rei != NULL && lei == rei) {
> - if (!merge)
> - goto err;
> -
> - ei_destroy(new);
> + if (lei == NULL) {
> + /* no overlaps, just add the new interval */
> + if (segtree_debug(tree->debug_mask))
> + pr_gmp_debug("insert: [%Zx %Zx]\n",
> + new->left, new->right);
> + __ei_insert(tree, new);
> return 0;
> - } else {
> - if (lei != NULL) {
> - if (!merge)
> - goto err;
> - /*
> - * Left endpoint is within lei, adjust it so we have:
> - *
> - * [lei_left, new_right]
> - */
> - if (segtree_debug(tree->debug_mask)) {
> - pr_gmp_debug("adjust left [%Zx %Zx]\n",
> - lei->left, lei->right);
> - }
> + }
>
> - mpz_set(lei->right, new->right);
> - ei_destroy(new);
> - return 0;
> - }
> + if (!merge) {
> + errno = EEXIST;
> + return expr_binary_error(msgs, lei->expr, new->expr,
> + "conflicting intervals specified");
> }
Not your fault, but I think this check is actually useless given that
the overlap check happens before (unless you consider to consolidate
the insertion and the overlap checks in ei_insert).
> - __ei_insert(tree, new);
> + /* caller sorted intervals, so rei is either equal to lei or NULL */
> + rei = ei_lookup(tree, new->right);
> + if (rei != lei) {
Isn't this always true? I mean rei != lei always stands true?
> + /*
> + * Left endpoint is within lei, adjust it so we have:
> + *
> + * [lei_left, new_right]
> + */
> + if (segtree_debug(tree->debug_mask))
> + pr_gmp_debug("adjust right: [%Zx %Zx]\n",
> + lei->left, lei->right);
> + mpz_set(lei->right, new->right);
> + } else if (segtree_debug(tree->debug_mask)) {
> + pr_gmp_debug("skip new: [%Zx %Zx] for old: [%Zx %Zx]\n",
> + new->left, new->right, lei->left, lei->right);
> + }
>
> + ei_destroy(new);
> return 0;
> -err:
> - errno = EEXIST;
> - return expr_binary_error(msgs, lei->expr, new->expr,
> - "conflicting intervals specified");
> }
>
> /*
> --
> 2.24.1
>
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [nft PATCH 4/4] segtree: Refactor ei_insert()
2020-01-28 12:23 ` Pablo Neira Ayuso
@ 2020-01-28 14:14 ` Phil Sutter
2020-01-28 15:42 ` Pablo Neira Ayuso
0 siblings, 1 reply; 12+ messages in thread
From: Phil Sutter @ 2020-01-28 14:14 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel, Florian Westphal
Hi Pablo,
On Tue, Jan 28, 2020 at 01:23:12PM +0100, Pablo Neira Ayuso wrote:
> On Thu, Jan 23, 2020 at 03:30:49PM +0100, Phil Sutter wrote:
[...]
> > + if (!merge) {
> > + errno = EEXIST;
> > + return expr_binary_error(msgs, lei->expr, new->expr,
> > + "conflicting intervals specified");
> > }
>
> Not your fault, but I think this check is actually useless given that
> the overlap check happens before (unless you consider to consolidate
> the insertion and the overlap checks in ei_insert).
That's interesting, indeed. What's more interesting is how
interval_cmp() works: I assumed it would just sort by start element when
in fact interval size is the prominent aspect. In practice, this means
my changes work only as long as all intervals are of equal or decreasing
size. Does it make sense to uphold this ordering scheme?
> > - __ei_insert(tree, new);
> > + /* caller sorted intervals, so rei is either equal to lei or NULL */
> > + rei = ei_lookup(tree, new->right);
> > + if (rei != lei) {
>
> Isn't this always true? I mean rei != lei always stands true?
Not if the second interval is entirely contained within the first one,
something like { 10-20, 12-14 }.
Cheers, Phil
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [nft PATCH 4/4] segtree: Refactor ei_insert()
2020-01-28 14:14 ` Phil Sutter
@ 2020-01-28 15:42 ` Pablo Neira Ayuso
2020-01-28 15:55 ` Phil Sutter
0 siblings, 1 reply; 12+ messages in thread
From: Pablo Neira Ayuso @ 2020-01-28 15:42 UTC (permalink / raw)
To: Phil Sutter, netfilter-devel, Florian Westphal
On Tue, Jan 28, 2020 at 03:14:16PM +0100, Phil Sutter wrote:
> Hi Pablo,
>
> On Tue, Jan 28, 2020 at 01:23:12PM +0100, Pablo Neira Ayuso wrote:
> > On Thu, Jan 23, 2020 at 03:30:49PM +0100, Phil Sutter wrote:
> [...]
> > > + if (!merge) {
> > > + errno = EEXIST;
> > > + return expr_binary_error(msgs, lei->expr, new->expr,
> > > + "conflicting intervals specified");
> > > }
> >
> > Not your fault, but I think this check is actually useless given that
> > the overlap check happens before (unless you consider to consolidate
> > the insertion and the overlap checks in ei_insert).
>
> That's interesting, indeed. What's more interesting is how
> interval_cmp() works: I assumed it would just sort by start element when
> in fact interval size is the prominent aspect.
I overlook that this is ordered by the size.
> In practice, this means my changes work only as long as all
> intervals are of equal or decreasing size. Does it make sense to
> uphold this ordering scheme?
I think if you change the ordering scheme to use the left side
(instead of the size) your new logic will work fine. It will also make
it probably easier to check for overlaps in the end.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [nft PATCH 4/4] segtree: Refactor ei_insert()
2020-01-28 15:42 ` Pablo Neira Ayuso
@ 2020-01-28 15:55 ` Phil Sutter
0 siblings, 0 replies; 12+ messages in thread
From: Phil Sutter @ 2020-01-28 15:55 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel, Florian Westphal
On Tue, Jan 28, 2020 at 04:42:17PM +0100, Pablo Neira Ayuso wrote:
> On Tue, Jan 28, 2020 at 03:14:16PM +0100, Phil Sutter wrote:
> > Hi Pablo,
> >
> > On Tue, Jan 28, 2020 at 01:23:12PM +0100, Pablo Neira Ayuso wrote:
> > > On Thu, Jan 23, 2020 at 03:30:49PM +0100, Phil Sutter wrote:
> > [...]
> > > > + if (!merge) {
> > > > + errno = EEXIST;
> > > > + return expr_binary_error(msgs, lei->expr, new->expr,
> > > > + "conflicting intervals specified");
> > > > }
> > >
> > > Not your fault, but I think this check is actually useless given that
> > > the overlap check happens before (unless you consider to consolidate
> > > the insertion and the overlap checks in ei_insert).
> >
> > That's interesting, indeed. What's more interesting is how
> > interval_cmp() works: I assumed it would just sort by start element when
> > in fact interval size is the prominent aspect.
>
> I overlook that this is ordered by the size.
Me too. %)
> > In practice, this means my changes work only as long as all
> > intervals are of equal or decreasing size. Does it make sense to
> > uphold this ordering scheme?
>
> I think if you change the ordering scheme to use the left side
> (instead of the size) your new logic will work fine. It will also make
> it probably easier to check for overlaps in the end.
I wondered if this sorting may be used (or even necessary) for prefixes
or something. If it's not mandatory, I think sorting differently would
indeed help. Anyway, it means back to drawing board for me and self-NACK
this series.
Thanks, Phil
^ permalink raw reply [flat|nested] 12+ messages in thread