* [nft PATCH] intervals: Do not sort cached set elements over and over again
@ 2022-06-15 17:33 Phil Sutter
2022-06-15 19:36 ` Pablo Neira Ayuso
0 siblings, 1 reply; 4+ messages in thread
From: Phil Sutter @ 2022-06-15 17:33 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel
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.
A test case adding ~25k elements in individual commands completes in
about 1/4th of the time with this patch applied.
Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
Signed-off-by: Phil Sutter <phil@nwl.cc>
---
include/expression.h | 1 +
src/intervals.c | 10 ++++++----
src/mergesort.c | 2 +-
3 files changed, 8 insertions(+), 5 deletions(-)
diff --git a/include/expression.h b/include/expression.h
index 2c3818e89b791..0f7ffb3a0a623 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 bc414d6c87976..a18967ee21061 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -589,19 +589,21 @@ int set_overlap(struct list_head *msgs, struct set *set, struct expr *init)
struct expr *i, *n, *clone;
int err;
+ set_to_range(init);
+ list_expr_sort(&init->expressions);
+
if (existing_set) {
if (existing_set->init) {
- list_splice_init(&existing_set->init->expressions,
+ 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);
}
}
- set_to_range(init);
- list_expr_sort(&init->expressions);
-
err = setelem_overlap(msgs, set, init);
list_for_each_entry_safe(i, n, &init->expressions, list) {
diff --git a/src/mergesort.c b/src/mergesort.c
index 8e6aac5fb24ed..dca71422dd947 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.34.1
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [nft PATCH] intervals: Do not sort cached set elements over and over again
2022-06-15 17:33 [nft PATCH] intervals: Do not sort cached set elements over and over again Phil Sutter
@ 2022-06-15 19:36 ` Pablo Neira Ayuso
2022-06-16 10:27 ` Phil Sutter
0 siblings, 1 reply; 4+ messages in thread
From: Pablo Neira Ayuso @ 2022-06-15 19:36 UTC (permalink / raw)
To: Phil Sutter; +Cc: netfilter-devel
On Wed, Jun 15, 2022 at 07:33:29PM +0200, Phil Sutter wrote:
> 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.
>
> A test case adding ~25k elements in individual commands completes in
> about 1/4th of the time with this patch applied.
Good.
Do you still like the idea of coalescing set element commands whenever
possible?
https://patchwork.ozlabs.org/project/netfilter-devel/patch/20220613160536.127441-1-pablo@netfilter.org/
Thanks.
> Fixes: 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
> Signed-off-by: Phil Sutter <phil@nwl.cc>
> ---
> include/expression.h | 1 +
> src/intervals.c | 10 ++++++----
> src/mergesort.c | 2 +-
> 3 files changed, 8 insertions(+), 5 deletions(-)
>
> diff --git a/include/expression.h b/include/expression.h
> index 2c3818e89b791..0f7ffb3a0a623 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 bc414d6c87976..a18967ee21061 100644
> --- a/src/intervals.c
> +++ b/src/intervals.c
> @@ -589,19 +589,21 @@ int set_overlap(struct list_head *msgs, struct set *set, struct expr *init)
> struct expr *i, *n, *clone;
> int err;
>
> + set_to_range(init);
> + list_expr_sort(&init->expressions);
> +
> if (existing_set) {
> if (existing_set->init) {
> - list_splice_init(&existing_set->init->expressions,
> + 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);
> }
> }
>
> - set_to_range(init);
> - list_expr_sort(&init->expressions);
> -
> err = setelem_overlap(msgs, set, init);
>
> list_for_each_entry_safe(i, n, &init->expressions, list) {
> diff --git a/src/mergesort.c b/src/mergesort.c
> index 8e6aac5fb24ed..dca71422dd947 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.34.1
>
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [nft PATCH] intervals: Do not sort cached set elements over and over again
2022-06-15 19:36 ` Pablo Neira Ayuso
@ 2022-06-16 10:27 ` Phil Sutter
2022-06-16 11:15 ` Pablo Neira Ayuso
0 siblings, 1 reply; 4+ messages in thread
From: Phil Sutter @ 2022-06-16 10:27 UTC (permalink / raw)
To: Pablo Neira Ayuso; +Cc: netfilter-devel
On Wed, Jun 15, 2022 at 09:36:11PM +0200, Pablo Neira Ayuso wrote:
> On Wed, Jun 15, 2022 at 07:33:29PM +0200, Phil Sutter wrote:
> > 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.
> >
> > A test case adding ~25k elements in individual commands completes in
> > about 1/4th of the time with this patch applied.
>
> Good.
>
> Do you still like the idea of coalescing set element commands whenever
> possible?
Does it mess with error reporting? If not, I don't see a downside of
doing it.
With regards to the problem at hand, it seems like a feature to escape
the actual problem. Please keep in mind that my patch's improvement from
~4min down to ~1min is pretty lousy given that v1.0.1 completed the same
task in 0.3s.
IMHO the whole overlap detection/auto merging should happen as commit
preparation and not per command.
Cheers, Phil
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [nft PATCH] intervals: Do not sort cached set elements over and over again
2022-06-16 10:27 ` Phil Sutter
@ 2022-06-16 11:15 ` Pablo Neira Ayuso
0 siblings, 0 replies; 4+ messages in thread
From: Pablo Neira Ayuso @ 2022-06-16 11:15 UTC (permalink / raw)
To: Phil Sutter, netfilter-devel
On Thu, Jun 16, 2022 at 12:27:31PM +0200, Phil Sutter wrote:
> On Wed, Jun 15, 2022 at 09:36:11PM +0200, Pablo Neira Ayuso wrote:
> > On Wed, Jun 15, 2022 at 07:33:29PM +0200, Phil Sutter wrote:
> > > 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.
> > >
> > > A test case adding ~25k elements in individual commands completes in
> > > about 1/4th of the time with this patch applied.
> >
> > Good.
> >
> > Do you still like the idea of coalescing set element commands whenever
> > possible?
>
> Does it mess with error reporting? If not, I don't see a downside of
> doing it.
>
> With regards to the problem at hand, it seems like a feature to escape
> the actual problem. Please keep in mind that my patch's improvement from
> ~4min down to ~1min is pretty lousy given that v1.0.1 completed the same
> task in 0.3s.
I running this comparison between 1.0.1:
# nft -v
nftables v1.0.1 (Fearless Fosdick #3)
# nft -f dump_sep.nft
real 0m3,867s
user 0m3,651s
sys 0m0,219s
and current 1.0.4 plus pending patches in patchwork:
# nft -v
nftables v1.0.4 (Lester Gooch #3)
# nft -f dump_sep.nft
real 0m3,867s
user 0m3,677s
sys 0m0,190s
For the record, this dump_sep.nft (that you sent me) looks like this:
# cat dump_sep.nft
add table t
add set t s { type ipv4_addr; flags interval; }
add element t s { 1.0.1.0/24 }
add element t s { 1.0.2.0/23 }
[...] more single command to add element [...]
> IMHO the whole overlap detection/auto merging should happen as commit
> preparation and not per command.
Then, this needs to coalesce the commands that update a single set at
a later stage, in such commit preparation phase.
This code also has to deal with deletions coming in the same batch,
which might be happening per command, by a robot generated batch.
Userspace overlap detection is only required by kernels <= 5.7, so
this check could be removed.
For automerging, I don't think I can escape tracking each command to
update the userspace set cache and adjust the existing ranges
accordingly.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2022-06-16 11:15 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-06-15 17:33 [nft PATCH] intervals: Do not sort cached set elements over and over again Phil Sutter
2022-06-15 19:36 ` Pablo Neira Ayuso
2022-06-16 10:27 ` Phil Sutter
2022-06-16 11:15 ` Pablo Neira Ayuso
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.