From: Konstantin Ananyev <konstantin.ananyev@intel.com>
To: dev@dpdk.org
Subject: [dpdk-dev] [PATCHv2 3/3] ACL: remove subtree_id calculations at build stage
Date: Wed, 3 Jun 2015 18:45:19 +0100 [thread overview]
Message-ID: <1433353519-20589-4-git-send-email-konstantin.ananyev@intel.com> (raw)
In-Reply-To: <1433353519-20589-1-git-send-email-konstantin.ananyev@intel.com>
v2:
- reorder code a bit to avoid gcc 5.1 warnings.
As now subtree_id is not used acl_merge_trie() any more,
there is no point to calculate and maintain that information.
Signed-off-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
---
lib/librte_acl/acl.h | 7 ---
lib/librte_acl/acl_bld.c | 121 +++++------------------------------------------
2 files changed, 13 insertions(+), 115 deletions(-)
diff --git a/lib/librte_acl/acl.h b/lib/librte_acl/acl.h
index 4dadab5..eb4930c 100644
--- a/lib/librte_acl/acl.h
+++ b/lib/librte_acl/acl.h
@@ -151,13 +151,6 @@ struct rte_acl_node {
/* free list link or pointer to duplicate node during merge */
struct rte_acl_node *prev;
/* points to node from which this node was duplicated */
-
- uint32_t subtree_id;
- uint32_t subtree_ref_count;
-
-};
-enum {
- RTE_ACL_SUBTREE_NODE = 0x80000000
};
/*
diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c
index 92a85df..3801843 100644
--- a/lib/librte_acl/acl_bld.c
+++ b/lib/librte_acl/acl_bld.c
@@ -117,7 +117,7 @@ struct acl_build_context {
static int acl_merge_trie(struct acl_build_context *context,
struct rte_acl_node *node_a, struct rte_acl_node *node_b,
- uint32_t level, uint32_t subtree_id, struct rte_acl_node **node_c);
+ uint32_t level, struct rte_acl_node **node_c);
static int acl_merge(struct acl_build_context *context,
struct rte_acl_node *node_a, struct rte_acl_node *node_b,
@@ -386,8 +386,8 @@ acl_gen_mask(struct rte_acl_bitset *bitset, uint32_t value, uint32_t mask)
* Determine if A and/or B are supersets of the intersection.
*/
static int
-acl_intersect_type(struct rte_acl_bitset *a_bits,
- struct rte_acl_bitset *b_bits,
+acl_intersect_type(const struct rte_acl_bitset *a_bits,
+ const struct rte_acl_bitset *b_bits,
struct rte_acl_bitset *intersect)
{
uint32_t n;
@@ -901,94 +901,6 @@ acl_resolve_leaf(struct acl_build_context *context,
}
/*
-* Within the existing trie structure, determine which nodes are
-* part of the subtree of the trie to be merged.
-*
-* For these purposes, a subtree is defined as the set of nodes that
-* are 1) not a superset of the intersection with the same level of
-* the merging tree, and 2) do not have any references from a node
-* outside of the subtree.
-*/
-static void
-mark_subtree(struct rte_acl_node *node,
- struct rte_acl_bitset *level_bits,
- uint32_t level,
- uint32_t id)
-{
- uint32_t n;
-
- /* mark this node as part of the subtree */
- node->subtree_id = id | RTE_ACL_SUBTREE_NODE;
-
- for (n = 0; n < node->num_ptrs; n++) {
-
- if (node->ptrs[n].ptr != NULL) {
-
- struct rte_acl_bitset intersect_bits;
- int intersect;
-
- /*
- * Item 1) :
- * check if this child pointer is not a superset of the
- * same level of the merging tree.
- */
- intersect = acl_intersect_type(&node->ptrs[n].values,
- &level_bits[level],
- &intersect_bits);
-
- if ((intersect & ACL_INTERSECT_A) == 0) {
-
- struct rte_acl_node *child = node->ptrs[n].ptr;
-
- /*
- * reset subtree reference if this is
- * the first visit by this subtree.
- */
- if (child->subtree_id != id) {
- child->subtree_id = id;
- child->subtree_ref_count = 0;
- }
-
- /*
- * Item 2) :
- * increment the subtree reference count and if
- * all references are from this subtree then
- * recurse to that child
- */
- child->subtree_ref_count++;
- if (child->subtree_ref_count ==
- child->ref_count)
- mark_subtree(child, level_bits,
- level + 1, id);
- }
- }
- }
-}
-
-/*
- * Build the set of bits that define the set of transitions
- * for each level of a trie.
- */
-static void
-build_subset_mask(struct rte_acl_node *node,
- struct rte_acl_bitset *level_bits,
- int level)
-{
- uint32_t n;
-
- /* Add this node's transitions to the set for this level */
- for (n = 0; n < RTE_ACL_BIT_SET_SIZE; n++)
- level_bits[level].bits[n] &= node->values.bits[n];
-
- /* For each child, add the transitions for the next level */
- for (n = 0; n < node->num_ptrs; n++)
- if (node->ptrs[n].ptr != NULL)
- build_subset_mask(node->ptrs[n].ptr, level_bits,
- level + 1);
-}
-
-
-/*
* Merge nodes A and B together,
* returns a node that is the path for the intersection
*
@@ -1014,7 +926,7 @@ build_subset_mask(struct rte_acl_node *node,
static int
acl_merge_trie(struct acl_build_context *context,
struct rte_acl_node *node_a, struct rte_acl_node *node_b,
- uint32_t level, uint32_t subtree_id, struct rte_acl_node **return_c)
+ uint32_t level, struct rte_acl_node **return_c)
{
uint32_t n, m, ptrs_c, ptrs_b;
uint32_t min_add_c, min_add_b;
@@ -1040,14 +952,12 @@ acl_merge_trie(struct acl_build_context *context,
}
/*
- * Create node C as a copy of node A if node A is not part of
- * a subtree of the merging tree (node B side). Otherwise,
- * just use node A.
+ * Create node C as a copy of node A, and do: C = merge(A,B);
+ * If node A can be used instead (A==C), then later we'll
+ * destroy C and return A.
*/
- if (level > 0) {
+ if (level > 0)
node_c = acl_dup_node(context, node_a);
- node_c->subtree_id = subtree_id | RTE_ACL_SUBTREE_NODE;
- }
/*
* If the two node transitions intersect then merge the transitions.
@@ -1094,7 +1004,7 @@ acl_merge_trie(struct acl_build_context *context,
if (acl_merge_trie(context,
node_c->ptrs[n].ptr,
node_b->ptrs[m].ptr,
- level + 1, subtree_id,
+ level + 1,
&child_node_c))
return 1;
@@ -1312,10 +1222,10 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
struct rte_acl_build_rule *prev, *rule;
struct rte_acl_node *end, *merge, *root, *end_prev;
const struct rte_acl_field *fld;
- struct rte_acl_bitset level_bits[RTE_ACL_MAX_LEVELS];
prev = head;
rule = head;
+ *last = prev;
trie = acl_alloc_node(context, 0);
@@ -1394,7 +1304,7 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
/* merge this field on to the end of the rule */
if (acl_merge_trie(context, end_prev, merge, 0,
- 0, NULL) != 0) {
+ NULL) != 0) {
return NULL;
}
}
@@ -1409,7 +1319,7 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
end->mrt = acl_build_alloc(context, 1,
sizeof(*end->mrt));
- for (m = 0; m < context->cfg.num_categories; m++) {
+ for (m = context->cfg.num_categories; 0 != m--; ) {
if (rule->f->data.category_mask & (1 << m)) {
end->mrt->results[m] = rule->f->data.userdata;
end->mrt->priority[m] = rule->f->data.priority;
@@ -1420,15 +1330,10 @@ build_trie(struct acl_build_context *context, struct rte_acl_build_rule *head,
}
node_count = context->num_nodes;
-
- memset(&level_bits[0], UINT8_MAX, sizeof(level_bits));
- build_subset_mask(root, &level_bits[0], 0);
- mark_subtree(trie, &level_bits[0], 0, end->match_flag);
(*count)++;
/* merge this rule into the trie */
- if (acl_merge_trie(context, trie, root, 0, end->match_flag,
- NULL))
+ if (acl_merge_trie(context, trie, root, 0, NULL))
return NULL;
node_count = context->num_nodes - node_count;
--
2.4.2
next prev parent reply other threads:[~2015-06-03 17:45 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-06-03 17:45 [dpdk-dev] [PATCHv2 0/3] ACL: Fix bug in acl_merge_trie() and add a new test-case for it to the UT Konstantin Ananyev
2015-06-03 17:45 ` [dpdk-dev] [PATCHv2 1/3] ACL: fix a problem in acl_merge_trie Konstantin Ananyev
2015-06-03 17:45 ` [dpdk-dev] [PATCHv2 2/3] ACL: add new test case for ranges build Konstantin Ananyev
2015-06-03 17:45 ` Konstantin Ananyev [this message]
2015-06-04 9:15 ` [dpdk-dev] [PATCHv2 0/3] ACL: Fix bug in acl_merge_trie() and add a new test-case for it to the UT Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1433353519-20589-4-git-send-email-konstantin.ananyev@intel.com \
--to=konstantin.ananyev@intel.com \
--cc=dev@dpdk.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).