From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 855C841C40; Wed, 8 Feb 2023 14:16:50 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 6DB644014F; Wed, 8 Feb 2023 14:16:50 +0100 (CET) Received: from mail-lj1-f174.google.com (mail-lj1-f174.google.com [209.85.208.174]) by mails.dpdk.org (Postfix) with ESMTP id 4C696406A2 for ; Mon, 6 Feb 2023 04:00:45 +0100 (CET) Received: by mail-lj1-f174.google.com with SMTP id u27so10767222ljo.12 for ; Sun, 05 Feb 2023 19:00:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=XY5VpGlxkBnvxULn6uiMaozwqsteGlzkYk/bqBT+YIk=; b=Q3bl/Bizh3lBccQ6m9EzQhZa/6h20SNTSOcqid8EBQpLlYAL71L+h43qYXFiX2XeU+ IZlpBug3z9iLMX3T4W6gjtDHBxoYu65utygvzAIdx207A+MAQ71XawdNHu/wzBNgmZSE BlXymQFtx7MeURgw9856PgalaQC2v9BXygDVVjdfgPNKLFLkPUQ05MN7PndVVjR3L4QU jrz/zGo0R268EHI9rMVbzoBY4eQbcNaUpJi3kczSQAOO4/0GxIv1S6cNyJDu/rnoLofC auQxwVHOEjH+y2zEJ3IcShWH3xe4M39A0DItdWfdei8Q0NEVIR4Z3R7rY6YFXfsvuFmq Kg4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=XY5VpGlxkBnvxULn6uiMaozwqsteGlzkYk/bqBT+YIk=; b=VeMriUWvNADgMKhTW9oWYKBCqKQn2J9ds57gaze27jgeFgg2yrF5/Hpm33ZzlNoR3j zgb+I70Zjc8LE5B9iH2OhdtMEuV9/X6QmuFqROIIo2K44JcZNcIbAwY/UqDCcQXLtbZ2 SvkUKQTD+zACRMrRapIJLsoa5nUunB4kGbidrKDZUATGnmTS1yUCC9EXJYSIri75jctk jnkosUPrHpi9zHgF/BZrbj9YrBNekVZCfNmJjCHsaKRs8msUzhpKntMnD673qW9uzzv5 iHRtRm+076wXuA4YZbk4ApPYA7+lx9u2SfcRijn2OGyIgo42GERyIxWKbyzccmL4NY6t nkFA== X-Gm-Message-State: AO0yUKWsleqtPCt9yirXjISv3a2UPij760mUS+4HTLzT+cm6ATLQ3NEk 6zldPGmrXZZHCynrROebKqPjDYH0M73rvoWH4w0= X-Google-Smtp-Source: AK7set9PPDZ/s1AbqB2aVftKAaYqHHpq+wCski6lQhUDo8/X0CV12LuP0AZGr7z8yji70TUcfL+W6/tgwWjBGdVKEyg= X-Received: by 2002:a2e:8055:0:b0:290:84ba:3749 with SMTP id p21-20020a2e8055000000b0029084ba3749mr2452283ljg.21.1675652444663; Sun, 05 Feb 2023 19:00:44 -0800 (PST) MIME-Version: 1.0 References: <20230201193426.19243-1-arcyleung@gmail.com> In-Reply-To: From: Arthur Leung Date: Sun, 5 Feb 2023 22:00:35 -0500 Message-ID: Subject: Re: [PATCH] acl: fix trie splitting To: Konstantin Ananyev , dev@dpdk.org Cc: Pablo de Lara Content-Type: multipart/alternative; boundary="000000000000bb346a05f3ff3c43" X-Mailman-Approved-At: Wed, 08 Feb 2023 14:16:49 +0100 X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org --000000000000bb346a05f3ff3c43 Content-Type: text/plain; charset="UTF-8" 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 @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 > > --- > > 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 @@ > > # '/' > > # trace record format: > > # \ > > -# ... > > +# ... > > # > > # 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; > > } > > > > --000000000000bb346a05f3ff3c43 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Konstantin

Thanks for= the explanation and examples, I see I've misunderstood "node limi= t 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=20 created=20 in a trie as a result of merging".

Sorry= for the bother, the patch can be closed as non-issue then.

<= /div>
Best,

Arthur

On Sun, Feb 5, 202= 3 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_no= de_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:<= br> echo 'acl_autotest' |
./x86_64-default-linuxapp-gcc-dbg/app/test/dpdk-test --lcores=3D15
--no-pci --no-huge --log-level=3Dacl,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=3D15 --no-pci = \
--no-huge --log-level=3Dacl,debug -- \
--rulesf=3D/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_rule \
--tracef=3D/home/kananyev/devel/dts/test-acl-input/acl2v4_10k_trace \
--verbose=3D0
...
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
=C2=A0 =C2=A0socket_id=3D-1
=C2=A0 =C2=A0alg=3D3
=C2=A0 =C2=A0first_load_sz=3D4
=C2=A0 =C2=A0max_rules=3D65536
=C2=A0 =C2=A0rule_size=3D96
=C2=A0 =C2=A0num_rules=3D9784
=C2=A0 =C2=A0num_categories=3D3
=C2=A0 =C2=A0num_tries=3D2


>
> 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>
> ---
>=C2=A0 =C2=A0app/test-acl/test-acl.sh | 2 +-
>=C2=A0 =C2=A0lib/acl/acl_bld.c=C2=A0 =C2=A0 =C2=A0 =C2=A0 | 9 +++------=
>=C2=A0 =C2=A02 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 @@
>=C2=A0 =C2=A0# <proto>'/'<mask>
>=C2=A0 =C2=A0# trace record format:
>=C2=A0 =C2=A0# <src_ip_addr><space><dst_ip_addr><s= pace> \
> -# <src_port><space<dst_port><space><proto>= ...<rule_id>
> +# <src_port><space><dst_port><space><proto= >...<rule_id>
>=C2=A0 =C2=A0#
>=C2=A0 =C2=A0# As an example:
>=C2=A0 =C2=A0# /bin/bash app/test-acl/test-acl.sh build/app/dpdk-test-a= cl \
> 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, stru= ct rte_acl_build_rule *head,
>=C2=A0 =C2=A0 =C2=A0 =C2=A0struct rte_acl_build_rule **last, uint32_t *= count)
>=C2=A0 =C2=A0{
>=C2=A0 =C2=A0 =C2=A0 =C2=A0uint32_t n, m;
> -=C2=A0 =C2=A0 =C2=A0int field_index, node_count;
> +=C2=A0 =C2=A0 =C2=A0int field_index;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0struct rte_acl_node *trie;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0struct rte_acl_build_rule *prev, *rule;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0struct rte_acl_node *end, *merge, *root, *en= d_prev;
> @@ -1048,15 +1048,13 @@ build_trie(struct acl_build_context *context, = struct rte_acl_build_rule *head,
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0}
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
>=C2=A0 =C2=A0
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0node_count =3D contex= t->num_nodes;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(*count)++;
>=C2=A0 =C2=A0
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0/* merge this ru= le into the trie */
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (acl_merge_tr= ie(context, trie, root, 0, NULL))
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0return NULL;
>=C2=A0 =C2=A0
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0node_count =3D contex= t->num_nodes - node_count;
> -=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (node_count > c= ontext->cur_node_max) {
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (context->num_n= odes > (context->cur_node_max * context->num_tries)) {
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0*last =3D prev;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0return trie;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
> @@ -1368,6 +1366,7 @@ acl_build_tries(struct acl_build_context *contex= t,
>=C2=A0 =C2=A0 =C2=A0 =C2=A0for (n =3D 0;; n =3D num_tries) {
>=C2=A0 =C2=A0
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0num_tries =3D n = + 1;
> +=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0context->num_tries= =3D num_tries;
>=C2=A0 =C2=A0
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0last =3D build_o= ne_trie(context, rule_sets, n, context->node_max);
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if (context->= bld_tries[n].trie =3D=3D NULL) {
> @@ -1411,8 +1410,6 @@ acl_build_tries(struct acl_build_context *contex= t,
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0}
>=C2=A0 =C2=A0
>=C2=A0 =C2=A0 =C2=A0 =C2=A0}
> -
> -=C2=A0 =C2=A0 =C2=A0context->num_tries =3D num_tries;
>=C2=A0 =C2=A0 =C2=A0 =C2=A0return 0;
>=C2=A0 =C2=A0}
>=C2=A0 =C2=A0

--000000000000bb346a05f3ff3c43--