intervals: do not empty cache for maps
Pablo Neira Ayuso
maintainerPATCH 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.
--- src/intervals.c | 9 ++++++--- 1 file changed, 6 insertions(+), 3 deletions(-)
src/intervals.c +6 -3
@@ -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
Pablo Neira Ayuso
maintainerPATCH 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.
---
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
@@ -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
@@ -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
Phil Sutter
reviewerRe: [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->initis sorted already, sort only the list of new elements and uselist_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")Signed-off-by Phil Sutter <[email protected]>Signed-off-by Pablo Neira Ayuso <[email protected]>
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
Pablo Neira Ayuso
maintainerRe: [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->initis sorted already, sort only the list of new elements and uselist_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")Signed-off-by Phil Sutter <[email protected]>Signed-off-by Pablo Neira Ayuso <[email protected]>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_KERNELandEXPR_F_REMOVEflags, 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.
Phil Sutter
reviewerRe: [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->initis sorted already, sort only the list of new elements and uselist_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")Signed-off-by Phil Sutter <[email protected]>Signed-off-by Pablo Neira Ayuso <[email protected]>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_KERNELandEXPR_F_REMOVEflags, 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
Pablo Neira Ayuso
maintainerRe: [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->initis sorted already, sort only the list of new elements and uselist_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")Signed-off-by Phil Sutter <[email protected]>Signed-off-by Pablo Neira Ayuso <[email protected]>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_KERNELandEXPR_F_REMOVEflags, 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_KERNELand removed ones also withEXPR_F_REMOVE. So afternft_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.