Skip to contentSkip to conversation

intervals: do not empty cache for maps

PATCH New Pablo Neira Ayuso 2 participants 6 messages Jun 16, 2022 – Jun 23, 2022 netfilter

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

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

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")
---
 src/intervals.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)
src/intervals.c +6 -3
index 89f5c33d7a6e..e20341320da2 100644
@@ -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);
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

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

From: Phil Sutter <[email protected]>

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")

---
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(-)
include/expression.h +1 -0
index 2c3818e89b79..0f7ffb3a0a62 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 +22 -24

64 lines not on this page · raw message

src/mergesort.c +1 -1
index 8e6aac5fb24e..dca71422dd94 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.30.2
reviewer
#2 lore raw

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

Quoted 11 lines · Pablo Neira Ayuso

From: Phil Sutter <[email protected]>

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.

Quoted 8 lines

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")

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

author maintainer
#3 lore raw

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

Quoted 24 lines · Phil Sutter
Quoted 11 lines · Pablo Neira Ayuso

From: Phil Sutter <[email protected]>

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.

Quoted 8 lines

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")

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

Quoted 6 lines

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.

reviewer
#4 lore raw

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

Quoted 32 lines · Pablo Neira Ayuso
Quoted 24 lines · Phil Sutter
Quoted 11 lines · Pablo Neira Ayuso

From: Phil Sutter <[email protected]>

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.

Quoted 8 lines

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")

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

Quoted 6 lines

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.

Quoted 2 lines

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

author maintainer
#5 lore raw

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

Quoted 36 lines · Phil Sutter
Quoted 32 lines · Pablo Neira Ayuso
Quoted 24 lines · Phil Sutter
Quoted 11 lines · Pablo Neira Ayuso

From: Phil Sutter <[email protected]>

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.

Quoted 8 lines

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")

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

Quoted 6 lines

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.

Quoted 2 lines

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

Quoted 6 lines

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.