Re: [PATCH] acl: fix trie splitting

[Arthur Leung <arcyleung@gmail.com>]

[-- 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 --]