acl: fix trie splitting
PATCH 1/1 acl: fix trie splitting
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
--- app/test-acl/test-acl.sh | 2 +- lib/acl/acl_bld.c | 9 +++------ 2 files changed, 4 insertions(+), 7 deletions(-)
app/test-acl/test-acl.sh +1 -1
@@ -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 \
lib/acl/acl_bld.c +3 -6
@@ -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 ; }
Signature · 1 line
2.25.1
It is not really clear to me what is the actual problem and what are you trying to fix here...
Quoted 1 line
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.
Quoted 1 line
However,
node_countis negative, sonode_count>context->cur_node_maxnever 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: 4rte_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
Quoted 71 lines
Original PR with sample files and test output can be found here:
https://github.com/DPDK/dpdk/pull/50Fixes dc276b5780c2 ("acl: new library")Signed-off-by Arthur Leung <[email protected]>--- app/test-acl/test-acl.sh | 2 +- lib/acl/acl_bld.c | 9 +++------ 2 files changed, 4 insertions(+), 7 deletions(-)app/test-acl/test-acl.sh +1
-1@@ -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 \lib/acl/acl_bld.c +3
-6@@ -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 ; }
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
Quoted 152 lines · Konstantin Ananyev
It is not really clear to me what is the actual problem and what are you trying to fix here...
Quoted 1 line
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 thencur_node_maxnew nodes, then it splits.Quoted 1 line
However,
node_countis negative, sonode_count>context->cur_node_maxnever 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: 4rte_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=2lib/acl/acl_bld.c build_trie(struct acl_build_context *context, struct
Quoted 29 lines
Original PR with sample files and test output can be found here:
https://github.com/DPDK/dpdk/pull/50Fixes dc276b5780c2 ("acl: new library")Signed-off-by Arthur Leung <[email protected]>--- app/test-acl/test-acl.sh | 2 +- lib/acl/acl_bld.c | 9 +++------ 2 files changed, 4 insertions(+), 7 deletions(-)app/test-acl/test-acl.sh +1
-1@@ -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 \lib/acl/acl_bld.c +0
-0@@ -946,7 +946,7 @@ build_trie(struct acl_build_context *context, struct
rte_acl_build_rule*head,lib/acl/acl_bld.c build_trie(struct acl_build_context *context,
Quoted 9 lines
lib/acl/acl_bld.c +1
-1struct 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,lib/acl/acl_bld.c build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
Quoted 13 lines
lib/acl/acl_bld.c +1
-3} } - 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)) {lib/acl/acl_bld.c acl_build_tries(struct acl_build_context *context, · line 1371
Quoted 10 lines
lib/acl/acl_bld.c +1
-0*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);Quoted 10 lines
lib/acl/acl_bld.c +0
-2if (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 ; }