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.anan...@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 <arcyle...@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; > > } > > > >
