Skip to contentSkip to conversation

intervals: Do not sort cached set elements over and over again

PATCH In review Phil Sutter 2 participants 4 messages Jun 15, 2022 – Jun 16, 2022 netfilter

lore
Share & tools
lore

Phil Sutter

author reviewer
#0 lore raw

PATCH 1/1 intervals: Do not sort cached set elements over and over again

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")
---
 include/expression.h |  1 +
 src/intervals.c      | 10 ++++++----
 src/mergesort.c      |  2 +-
 3 files changed, 8 insertions(+), 5 deletions(-)
include/expression.h +1 -0
index 2c3818e89b791..0f7ffb3a0a623 100644
@@ -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);
 
src/intervals.c +6 -4
index bc414d6c87976..a18967ee21061 100644
@@ -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) {
src/mergesort.c +1 -1
index 8e6aac5fb24ed..dca71422dd947 100644
@@ -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;
Signature · 1 line
2.34.1
#1 lore raw
Quoted 8 lines · Phil Sutter

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/[email protected]/

Thanks.

Quoted 66 lines
Fixes 3da9643fb9ff9 ("intervals: add support to automerge with kernel elements")
---
 include/expression.h |  1 +
 src/intervals.c      | 10 ++++++----
 src/mergesort.c      |  2 +-
 3 files changed, 8 insertions(+), 5 deletions(-)
include/expression.h +1 -0
index 2c3818e89b791..0f7ffb3a0a623 100644
@@ -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);
 
src/intervals.c +6 -4
index bc414d6c87976..a18967ee21061 100644
@@ -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) {
src/mergesort.c +1 -1
index 8e6aac5fb24ed..dca71422dd947 100644
@@ -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;
Signature · 1 line
2.34.1
author reviewer
#2 lore raw
Quoted 7 lines · Pablo Neira Ayuso
Quoted 6 lines · Phil Sutter

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.

Quoted 7 lines
Quoted 2 lines

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

#3 lore raw
Quoted 16 lines · Phil Sutter
Quoted 7 lines · Pablo Neira Ayuso
Quoted 6 lines · Phil Sutter

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.

Quoted 7 lines
Quoted 2 lines

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?

Quoted 7 lines

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 [...]
Quoted 2 lines

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.