* [PATCH] acl: fix trie splitting @ 2023-02-01 19:34 Arthur Leung 2023-02-05 16:46 ` Konstantin Ananyev 0 siblings, 1 reply; 3+ messages in thread From: Arthur Leung @ 2023-02-01 19:34 UTC (permalink / raw) To: dev; +Cc: Arthur Leung, Konstantin Ananyev, Pablo de Lara When using a large number of ACL rules, the trie is supposed to split when there are over 2048 nodes. However, node_count is negative, so node_count > context->cur_node_max never actually runs, so all the nodes created from the rules end up being in one trie. Original PR with sample files and test output can be found here: https://github.com/DPDK/dpdk/pull/50 Fixes: dc276b5780c2 ("acl: new library") Signed-off-by: Arthur Leung <arcyleung@gmail.com> --- app/test-acl/test-acl.sh | 2 +- lib/acl/acl_bld.c | 9 +++------ 2 files changed, 4 insertions(+), 7 deletions(-) diff --git a/app/test-acl/test-acl.sh b/app/test-acl/test-acl.sh index 30814f3fe2..59bfa121cf 100644 --- a/app/test-acl/test-acl.sh +++ b/app/test-acl/test-acl.sh @@ -17,7 +17,7 @@ # <proto>'/'<mask> # trace record format: # <src_ip_addr><space><dst_ip_addr><space> \ -# <src_port><space<dst_port><space><proto>...<rule_id> +# <src_port><space><dst_port><space><proto>...<rule_id> # # As an example: # /bin/bash app/test-acl/test-acl.sh build/app/dpdk-test-acl \ diff --git a/lib/acl/acl_bld.c b/lib/acl/acl_bld.c index 2816632803..6064a8103b 100644 --- a/lib/acl/acl_bld.c +++ b/lib/acl/acl_bld.c @@ -946,7 +946,7 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head, struct rte_acl_build_rule **last, uint32_t *count) { uint32_t n, m; - int field_index, node_count; + int field_index; struct rte_acl_node *trie; struct rte_acl_build_rule *prev, *rule; struct rte_acl_node *end, *merge, *root, *end_prev; @@ -1048,15 +1048,13 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head, } } - node_count = context->num_nodes; (*count)++; /* merge this rule into the trie */ if (acl_merge_trie(context, trie, root, 0, NULL)) return NULL; - node_count = context->num_nodes - node_count; - if (node_count > context->cur_node_max) { + if (context->num_nodes > (context->cur_node_max * context->num_tries)) { *last = prev; return trie; } @@ -1368,6 +1366,7 @@ acl_build_tries(struct acl_build_context *context, for (n = 0;; n = num_tries) { num_tries = n + 1; + context->num_tries = num_tries; last = build_one_trie(context, rule_sets, n, context->node_max); if (context->bld_tries[n].trie == NULL) { @@ -1411,8 +1410,6 @@ acl_build_tries(struct acl_build_context *context, } } - - context->num_tries = num_tries; return 0; } -- 2.25.1 ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] acl: fix trie splitting 2023-02-01 19:34 [PATCH] acl: fix trie splitting Arthur Leung @ 2023-02-05 16:46 ` Konstantin Ananyev 2023-02-06 3:00 ` Arthur Leung 0 siblings, 1 reply; 3+ messages in thread From: Konstantin Ananyev @ 2023-02-05 16:46 UTC (permalink / raw) To: Arthur Leung, dev; +Cc: Pablo de Lara It is not really clear to me what is the actual problem and what are you trying to fix here... > When using a large number of ACL rules, the trie is supposed to split when there are over 2048 nodes. What do you mean by 'there'? As I remember, it decided to split set of rules, when trie starts to grow too fast: if merging of last rule creates more then cur_node_max new nodes, then it splits. > However, node_count is negative, so node_count > context->cur_node_max never actually runs, so all the nodes created from the rules end up being in one trie. Hmm... sentence that node count is negative is too cryptic for me. Obviously there are plenty examples with rule-sets that causes more then one trie to be created. Simplest way to check that, just run acl autotest: echo 'acl_autotest' | ./x86_64-default-linuxapp-gcc-dbg/app/test/dpdk-test --lcores=15 --no-pci --no-huge --log-level=acl,debug ... You will see that there are bunch of cases with more then one trie. Another way - try with dts test-cases for acl. few of them will create multiple tries: git clone -v http://dpdk.org/git/tools/dts/ cd dts gzip -cd dep/test-acl-input.tar.gz | tar xfv - ./x86_64-default-linuxapp-gcc-dbg/app/dpdk-test-acl --lcores=15 --no-pci \ --no-huge --log-level=acl,debug -- \ --rulesf=/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_rule \ --tracef=/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_trace \ --verbose=0 ... dump_config: rulesf:/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_rule tracef:/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_trace rulenum:65536 tracenum:65536 tracestep:256 bldcat:3 runcat:1 maxsize:0 iter:1 verbose:0 alg:0(default) ipv6:0 ACL: Gen phase for ACL "TESTACL": runtime memory footprint on socket -1: single nodes/bytes used: 54437/435496 quad nodes/vectors/bytes used: 55775/189941/1519528 DFA nodes/group64/bytes used: 9516/28940/14819336 match nodes/bytes used: 9760/1249280 total: 18027888 bytes max limit: 18446744073709551615 bytes ACL: Build phase for ACL "TESTACL": node limit for tree split: 2048 nodes created: 129488 memory consumed: 184549530 ACL: trie 0: number of rules: 655, indexes: 4 ACL: trie 1: number of rules: 9129, indexes: 4 rte_acl_build(3) finished with 0 acl context <TESTACL>@0x103adfa80 socket_id=-1 alg=3 first_load_sz=4 max_rules=65536 rule_size=96 num_rules=9784 num_categories=3 num_tries=2 > > Original PR with sample files and test output can be found here: > https://github.com/DPDK/dpdk/pull/50 > > Fixes: dc276b5780c2 ("acl: new library") > Signed-off-by: Arthur Leung <arcyleung@gmail.com> > --- > app/test-acl/test-acl.sh | 2 +- > lib/acl/acl_bld.c | 9 +++------ > 2 files changed, 4 insertions(+), 7 deletions(-) > > diff --git a/app/test-acl/test-acl.sh b/app/test-acl/test-acl.sh > index 30814f3fe2..59bfa121cf 100644 > --- a/app/test-acl/test-acl.sh > +++ b/app/test-acl/test-acl.sh > @@ -17,7 +17,7 @@ > # <proto>'/'<mask> > # trace record format: > # <src_ip_addr><space><dst_ip_addr><space> \ > -# <src_port><space<dst_port><space><proto>...<rule_id> > +# <src_port><space><dst_port><space><proto>...<rule_id> > # > # As an example: > # /bin/bash app/test-acl/test-acl.sh build/app/dpdk-test-acl \ > diff --git a/lib/acl/acl_bld.c b/lib/acl/acl_bld.c > index 2816632803..6064a8103b 100644 > --- a/lib/acl/acl_bld.c > +++ b/lib/acl/acl_bld.c > @@ -946,7 +946,7 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head, > struct rte_acl_build_rule **last, uint32_t *count) > { > uint32_t n, m; > - int field_index, node_count; > + int field_index; > struct rte_acl_node *trie; > struct rte_acl_build_rule *prev, *rule; > struct rte_acl_node *end, *merge, *root, *end_prev; > @@ -1048,15 +1048,13 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head, > } > } > > - node_count = context->num_nodes; > (*count)++; > > /* merge this rule into the trie */ > if (acl_merge_trie(context, trie, root, 0, NULL)) > return NULL; > > - node_count = context->num_nodes - node_count; > - if (node_count > context->cur_node_max) { > + if (context->num_nodes > (context->cur_node_max * context->num_tries)) { > *last = prev; > return trie; > } > @@ -1368,6 +1366,7 @@ acl_build_tries(struct acl_build_context *context, > for (n = 0;; n = num_tries) { > > num_tries = n + 1; > + context->num_tries = num_tries; > > last = build_one_trie(context, rule_sets, n, context->node_max); > if (context->bld_tries[n].trie == NULL) { > @@ -1411,8 +1410,6 @@ acl_build_tries(struct acl_build_context *context, > } > > } > - > - context->num_tries = num_tries; > return 0; > } > ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] acl: fix trie splitting 2023-02-05 16:46 ` Konstantin Ananyev @ 2023-02-06 3:00 ` Arthur Leung 0 siblings, 0 replies; 3+ messages in thread From: Arthur Leung @ 2023-02-06 3:00 UTC (permalink / raw) To: Konstantin Ananyev, dev; +Cc: Pablo de Lara [-- Attachment #1: Type: text/plain, Size: 5733 bytes --] Hi Konstantin Thanks for the explanation and examples, I see I've misunderstood "node limit for tree split" to mean "the limit of the total number of nodes in a tree", rather than the intended logic of "the limit of new nodes that can be created in a trie as a result of merging". Sorry for the bother, the patch can be closed as non-issue then. Best, Arthur On Sun, Feb 5, 2023 at 11:47 AM Konstantin Ananyev < konstantin.v.ananyev@yandex.ru> wrote: > > It is not really clear to me what is the actual problem > and what are you trying to fix here... > > > > When using a large number of ACL rules, the trie is supposed to split > when there are over 2048 nodes. > > What do you mean by 'there'? > As I remember, it decided to split set of rules, when trie starts to > grow too fast: if merging of last rule creates more then cur_node_max > new nodes, then it splits. > > > However, node_count is negative, so node_count > context->cur_node_max > never actually runs, so all the nodes created from the rules end up being > in one trie. > > Hmm... sentence that node count is negative is too cryptic for me. > Obviously there are plenty examples with rule-sets that causes more then > one trie to be created. Simplest way to check that, just run acl autotest: > echo 'acl_autotest' | > ./x86_64-default-linuxapp-gcc-dbg/app/test/dpdk-test --lcores=15 > --no-pci --no-huge --log-level=acl,debug > ... > You will see that there are bunch of cases with more then one trie. > Another way - try with dts test-cases for acl. few of them will create > multiple tries: > git clone -v http://dpdk.org/git/tools/dts/ > cd dts > gzip -cd dep/test-acl-input.tar.gz | tar xfv - > ./x86_64-default-linuxapp-gcc-dbg/app/dpdk-test-acl --lcores=15 --no-pci \ > --no-huge --log-level=acl,debug -- \ > --rulesf=/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_rule \ > --tracef=/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_trace \ > --verbose=0 > ... > dump_config: > rulesf:/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_rule > tracef:/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_trace > rulenum:65536 > tracenum:65536 > tracestep:256 > bldcat:3 > runcat:1 > maxsize:0 > iter:1 > verbose:0 > alg:0(default) > ipv6:0 > ACL: Gen phase for ACL "TESTACL": > runtime memory footprint on socket -1: > single nodes/bytes used: 54437/435496 > quad nodes/vectors/bytes used: 55775/189941/1519528 > DFA nodes/group64/bytes used: 9516/28940/14819336 > match nodes/bytes used: 9760/1249280 > total: 18027888 bytes > max limit: 18446744073709551615 bytes > ACL: Build phase for ACL "TESTACL": > node limit for tree split: 2048 > nodes created: 129488 > memory consumed: 184549530 > ACL: trie 0: number of rules: 655, indexes: 4 > ACL: trie 1: number of rules: 9129, indexes: 4 > rte_acl_build(3) finished with 0 > acl context <TESTACL>@0x103adfa80 > socket_id=-1 > alg=3 > first_load_sz=4 > max_rules=65536 > rule_size=96 > num_rules=9784 > num_categories=3 > num_tries=2 > > > > > > Original PR with sample files and test output can be found here: > > https://github.com/DPDK/dpdk/pull/50 > > > > Fixes: dc276b5780c2 ("acl: new library") > > Signed-off-by: Arthur Leung <arcyleung@gmail.com> > > --- > > app/test-acl/test-acl.sh | 2 +- > > lib/acl/acl_bld.c | 9 +++------ > > 2 files changed, 4 insertions(+), 7 deletions(-) > > > > diff --git a/app/test-acl/test-acl.sh b/app/test-acl/test-acl.sh > > index 30814f3fe2..59bfa121cf 100644 > > --- a/app/test-acl/test-acl.sh > > +++ b/app/test-acl/test-acl.sh > > @@ -17,7 +17,7 @@ > > # <proto>'/'<mask> > > # trace record format: > > # <src_ip_addr><space><dst_ip_addr><space> \ > > -# <src_port><space<dst_port><space><proto>...<rule_id> > > +# <src_port><space><dst_port><space><proto>...<rule_id> > > # > > # As an example: > > # /bin/bash app/test-acl/test-acl.sh build/app/dpdk-test-acl \ > > diff --git a/lib/acl/acl_bld.c b/lib/acl/acl_bld.c > > index 2816632803..6064a8103b 100644 > > --- a/lib/acl/acl_bld.c > > +++ b/lib/acl/acl_bld.c > > @@ -946,7 +946,7 @@ build_trie(struct acl_build_context *context, struct > rte_acl_build_rule *head, > > struct rte_acl_build_rule **last, uint32_t *count) > > { > > uint32_t n, m; > > - int field_index, node_count; > > + int field_index; > > struct rte_acl_node *trie; > > struct rte_acl_build_rule *prev, *rule; > > struct rte_acl_node *end, *merge, *root, *end_prev; > > @@ -1048,15 +1048,13 @@ build_trie(struct acl_build_context *context, > struct rte_acl_build_rule *head, > > } > > } > > > > - node_count = context->num_nodes; > > (*count)++; > > > > /* merge this rule into the trie */ > > if (acl_merge_trie(context, trie, root, 0, NULL)) > > return NULL; > > > > - node_count = context->num_nodes - node_count; > > - if (node_count > context->cur_node_max) { > > + if (context->num_nodes > (context->cur_node_max * > context->num_tries)) { > > *last = prev; > > return trie; > > } > > @@ -1368,6 +1366,7 @@ acl_build_tries(struct acl_build_context *context, > > for (n = 0;; n = num_tries) { > > > > num_tries = n + 1; > > + context->num_tries = num_tries; > > > > last = build_one_trie(context, rule_sets, n, > context->node_max); > > if (context->bld_tries[n].trie == NULL) { > > @@ -1411,8 +1410,6 @@ acl_build_tries(struct acl_build_context *context, > > } > > > > } > > - > > - context->num_tries = num_tries; > > return 0; > > } > > > > [-- Attachment #2: Type: text/html, Size: 7552 bytes --] ^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-02-08 13:16 UTC | newest] Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2023-02-01 19:34 [PATCH] acl: fix trie splitting Arthur Leung 2023-02-05 16:46 ` Konstantin Ananyev 2023-02-06 3:00 ` Arthur Leung
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).