[PATCH nft 1/2] intervals: do not empty cache for maps

[PATCH nft 1/2] intervals: do not empty cache for maps

[Pablo Neira Ayuso]

Translate set element to range and sort in maps for the NFT_SET_MAP
case, which does not support for automerge yet.

Fixes: 81e36530fcac ("src: replace interval segment tree overlap and automerge")
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/intervals.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/src/intervals.c b/src/intervals.c
index 89f5c33d7a6e..e20341320da2 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -216,6 +216,12 @@ int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,
 	struct cmd *purge_cmd;
 	struct handle h = {};
 
+	if (set->flags & NFT_SET_MAP) {
+		set_to_range(init);
+		list_expr_sort(&init->expressions);
+		return 0;
+	}
+
 	if (existing_set) {
 		if (existing_set->init) {
 			list_splice_init(&existing_set->init->expressions,
@@ -229,9 +235,6 @@ int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,
 	set_to_range(init);
 	list_expr_sort(&init->expressions);
 
-	if (set->flags & NFT_SET_MAP)
-		return 0;
-
 	ctx.purge = set_expr_alloc(&internal_location, set);
 
 	setelem_automerge(&ctx);
-- 
2.30.2

[PATCH nft 2/2,v2] intervals: Do not sort cached set elements over and over again

[Pablo Neira Ayuso]

From: Phil Sutter <phil@nwl.cc>

When adding element(s) to a non-empty set, code merged the two lists and
sorted the result. With many individual 'add element' commands this
causes substantial overhead. Make use of the fact that
existing_set->init is sorted already, sort only the list of new elements
and use list_splice_sorted() to merge the two sorted lists.

Add set_sort_splice() and use it for set element overlap detection and
automerge.

A test case adding ~25k elements in individual commands completes in
about 1/4th of the time with this patch applied.

Joint work with Pablo.

Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
Signed-off-by: Phil Sutter <phil@nwl.cc>
Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
v2: add set_sort_splice() and reuse it for the automerge case.

 include/expression.h |  1 +
 src/intervals.c      | 46 +++++++++++++++++++++-----------------------
 src/mergesort.c      |  2 +-
 3 files changed, 24 insertions(+), 25 deletions(-)

diff --git a/include/expression.h b/include/expression.h
index 2c3818e89b79..0f7ffb3a0a62 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -480,6 +480,7 @@ extern struct expr *compound_expr_alloc(const struct location *loc,
 extern void compound_expr_add(struct expr *compound, struct expr *expr);
 extern void compound_expr_remove(struct expr *compound, struct expr *expr);
 extern void list_expr_sort(struct list_head *head);
+extern void list_splice_sorted(struct list_head *list, struct list_head *head);
 
 extern struct expr *concat_expr_alloc(const struct location *loc);
 
diff --git a/src/intervals.c b/src/intervals.c
index e20341320da2..dcc06d18d594 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -118,6 +118,26 @@ static bool merge_ranges(struct set_automerge_ctx *ctx,
 	return false;
 }
 
+static void set_sort_splice(struct expr *init, struct set *set)
+{
+	struct set *existing_set = set->existing_set;
+
+	set_to_range(init);
+	list_expr_sort(&init->expressions);
+
+	if (!existing_set)
+		return;
+
+	if (existing_set->init) {
+		set_to_range(existing_set->init);
+		list_splice_sorted(&existing_set->init->expressions,
+				   &init->expressions);
+		init_list_head(&existing_set->init->expressions);
+	} else {
+		existing_set->init = set_expr_alloc(&internal_location, set);
+	}
+}
+
 static void setelem_automerge(struct set_automerge_ctx *ctx)
 {
 	struct expr *i, *next, *prev = NULL;
@@ -222,18 +242,7 @@ int set_automerge(struct list_head *msgs, struct cmd *cmd, struct set *set,
 		return 0;
 	}
 
-	if (existing_set) {
-		if (existing_set->init) {
-			list_splice_init(&existing_set->init->expressions,
-					 &init->expressions);
-		} else {
-			existing_set->init = set_expr_alloc(&internal_location,
-							    set);
-		}
-	}
-
-	set_to_range(init);
-	list_expr_sort(&init->expressions);
+	set_sort_splice(init, set);
 
 	ctx.purge = set_expr_alloc(&internal_location, set);
 
@@ -591,18 +600,7 @@ int set_overlap(struct list_head *msgs, struct set *set, struct expr *init)
 	struct expr *i, *n, *clone;
 	int err;
 
-	if (existing_set) {
-		if (existing_set->init) {
-			list_splice_init(&existing_set->init->expressions,
-					 &init->expressions);
-		} else {
-			existing_set->init = set_expr_alloc(&internal_location,
-							    set);
-		}
-	}
-
-	set_to_range(init);
-	list_expr_sort(&init->expressions);
+	set_sort_splice(init, set);
 
 	err = setelem_overlap(msgs, set, init);
 
diff --git a/src/mergesort.c b/src/mergesort.c
index 8e6aac5fb24e..dca71422dd94 100644
--- a/src/mergesort.c
+++ b/src/mergesort.c
@@ -70,7 +70,7 @@ static int expr_msort_cmp(const struct expr *e1, const struct expr *e2)
 	return ret;
 }
 
-static void list_splice_sorted(struct list_head *list, struct list_head *head)
+void list_splice_sorted(struct list_head *list, struct list_head *head)
 {
 	struct list_head *h = head->next;
 	struct list_head *l = list->next;
-- 
2.30.2

Re: [PATCH nft 2/2,v2] intervals: Do not sort cached set elements over and over again

[Phil Sutter]

On Thu, Jun 16, 2022 at 11:04:46AM +0200, Pablo Neira Ayuso wrote:
> From: Phil Sutter <phil@nwl.cc>
> 
> When adding element(s) to a non-empty set, code merged the two lists and
> sorted the result. With many individual 'add element' commands this
> causes substantial overhead. Make use of the fact that
> existing_set->init is sorted already, sort only the list of new elements
> and use list_splice_sorted() to merge the two sorted lists.
> 
> Add set_sort_splice() and use it for set element overlap detection and
> automerge.
> 
> A test case adding ~25k elements in individual commands completes in
> about 1/4th of the time with this patch applied.
> 
> Joint work with Pablo.
> 
> Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
> Signed-off-by: Phil Sutter <phil@nwl.cc>
> Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

Thanks for picking it up, I missed the automerge code being very
similar.

I worked on a patch to move the whole set adjustment to a separate step
after evaluating commands, but it's a bit larger effort as it requires
to combine overlap detection, auto merge and element deletion. With
simple appending new elements in eval phase and reacting upon
EXPR_F_KERNEL and EXPR_F_REMOVE flags, I guess it's possible to update
the whole set in one go.

Cheers, Phil

Re: [PATCH nft 2/2,v2] intervals: Do not sort cached set elements over and over again

[Pablo Neira Ayuso]

On Thu, Jun 23, 2022 at 06:05:20PM +0200, Phil Sutter wrote:
> On Thu, Jun 16, 2022 at 11:04:46AM +0200, Pablo Neira Ayuso wrote:
> > From: Phil Sutter <phil@nwl.cc>
> > 
> > When adding element(s) to a non-empty set, code merged the two lists and
> > sorted the result. With many individual 'add element' commands this
> > causes substantial overhead. Make use of the fact that
> > existing_set->init is sorted already, sort only the list of new elements
> > and use list_splice_sorted() to merge the two sorted lists.
> > 
> > Add set_sort_splice() and use it for set element overlap detection and
> > automerge.
> > 
> > A test case adding ~25k elements in individual commands completes in
> > about 1/4th of the time with this patch applied.
> > 
> > Joint work with Pablo.
> > 
> > Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
> > Signed-off-by: Phil Sutter <phil@nwl.cc>
> > Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> 
> Thanks for picking it up, I missed the automerge code being very
> similar.
> 
> I worked on a patch to move the whole set adjustment to a separate step
> after evaluating commands, but it's a bit larger effort as it requires
> to combine overlap detection, auto merge and element deletion. With
> simple appending new elements in eval phase and reacting upon
> EXPR_F_KERNEL and EXPR_F_REMOVE flags, I guess it's possible to update
> the whole set in one go.

You mean, appending if they come in order as in your test ruleset? Not
sure what you are suggesting.

Re: [PATCH nft 2/2,v2] intervals: Do not sort cached set elements over and over again

[Phil Sutter]

On Thu, Jun 23, 2022 at 06:17:16PM +0200, Pablo Neira Ayuso wrote:
> On Thu, Jun 23, 2022 at 06:05:20PM +0200, Phil Sutter wrote:
> > On Thu, Jun 16, 2022 at 11:04:46AM +0200, Pablo Neira Ayuso wrote:
> > > From: Phil Sutter <phil@nwl.cc>
> > > 
> > > When adding element(s) to a non-empty set, code merged the two lists and
> > > sorted the result. With many individual 'add element' commands this
> > > causes substantial overhead. Make use of the fact that
> > > existing_set->init is sorted already, sort only the list of new elements
> > > and use list_splice_sorted() to merge the two sorted lists.
> > > 
> > > Add set_sort_splice() and use it for set element overlap detection and
> > > automerge.
> > > 
> > > A test case adding ~25k elements in individual commands completes in
> > > about 1/4th of the time with this patch applied.
> > > 
> > > Joint work with Pablo.
> > > 
> > > Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
> > > Signed-off-by: Phil Sutter <phil@nwl.cc>
> > > Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> > 
> > Thanks for picking it up, I missed the automerge code being very
> > similar.
> > 
> > I worked on a patch to move the whole set adjustment to a separate step
> > after evaluating commands, but it's a bit larger effort as it requires
> > to combine overlap detection, auto merge and element deletion. With
> > simple appending new elements in eval phase and reacting upon
> > EXPR_F_KERNEL and EXPR_F_REMOVE flags, I guess it's possible to update
> > the whole set in one go.
> 
> You mean, appending if they come in order as in your test ruleset? Not
> sure what you are suggesting.

It was merely loud thinking - combining repeated 'add element' commands
is fine with me for avoiding the problem. I have an alternative in mind
where added elements are appended to the set without EXPR_F_KERNEL and
removed ones also with EXPR_F_REMOVE. So after nft_evaluate() one could
do all the overlap detection / auto merging / element removing once for
each changed set.

Cheers, Phil

Re: [PATCH nft 2/2,v2] intervals: Do not sort cached set elements over and over again

[Pablo Neira Ayuso]

On Thu, Jun 23, 2022 at 06:25:35PM +0200, Phil Sutter wrote:
> On Thu, Jun 23, 2022 at 06:17:16PM +0200, Pablo Neira Ayuso wrote:
> > On Thu, Jun 23, 2022 at 06:05:20PM +0200, Phil Sutter wrote:
> > > On Thu, Jun 16, 2022 at 11:04:46AM +0200, Pablo Neira Ayuso wrote:
> > > > From: Phil Sutter <phil@nwl.cc>
> > > > 
> > > > When adding element(s) to a non-empty set, code merged the two lists and
> > > > sorted the result. With many individual 'add element' commands this
> > > > causes substantial overhead. Make use of the fact that
> > > > existing_set->init is sorted already, sort only the list of new elements
> > > > and use list_splice_sorted() to merge the two sorted lists.
> > > > 
> > > > Add set_sort_splice() and use it for set element overlap detection and
> > > > automerge.
> > > > 
> > > > A test case adding ~25k elements in individual commands completes in
> > > > about 1/4th of the time with this patch applied.
> > > > 
> > > > Joint work with Pablo.
> > > > 
> > > > Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
> > > > Signed-off-by: Phil Sutter <phil@nwl.cc>
> > > > Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
> > > 
> > > Thanks for picking it up, I missed the automerge code being very
> > > similar.
> > > 
> > > I worked on a patch to move the whole set adjustment to a separate step
> > > after evaluating commands, but it's a bit larger effort as it requires
> > > to combine overlap detection, auto merge and element deletion. With
> > > simple appending new elements in eval phase and reacting upon
> > > EXPR_F_KERNEL and EXPR_F_REMOVE flags, I guess it's possible to update
> > > the whole set in one go.
> > 
> > You mean, appending if they come in order as in your test ruleset? Not
> > sure what you are suggesting.
> 
> It was merely loud thinking - combining repeated 'add element' commands
> is fine with me for avoiding the problem. I have an alternative in mind
> where added elements are appended to the set without EXPR_F_KERNEL and
> removed ones also with EXPR_F_REMOVE. So after nft_evaluate() one could
> do all the overlap detection / auto merging / element removing once for
> each changed set.

I have pushed out this coalesce approach to tackle this regression.
Feel free to revisit this approach.