[PATCHv2 0/3] ACL: Fix bug in acl_merge_trie() and add a new test-case for it to the UT

[PATCHv2 0/3] ACL: Fix bug in acl_merge_trie() and add a new test-case for it to the UT

[Konstantin Ananyev]

v2:
- reorder code a bit to avoid gcc 5.1 warnings.

Konstantin Ananyev (3):
  ACL: fix a problem in acl_merge_trie
  ACL: add new test case for ranges build
  ACL: remove subtree_id calculations at build stage

 app/test/test_acl.c      | 147 +++++++++++++++++++++++++++++++++++++++++++++--
 lib/librte_acl/acl.h     |   7 ---
 lib/librte_acl/acl_bld.c | 123 +++++----------------------------------
 3 files changed, 156 insertions(+), 121 deletions(-)

-- 
2.4.2

[PATCHv2 1/3] ACL: fix a problem in acl_merge_trie

[Konstantin Ananyev]

Reported by Zi Hu <huzilucky@gmail.com>:

"...
cat test_data/rule1
@192.168.0.0/24 192.168.0.0/24 400 : 500 0 : 52 6/0xff
@192.168.0.0/24 192.168.0.0/24 400 : 500 54 : 65280 6/0xff
@192.168.0.0/24 192.168.0.0/24 400 : 500 0 : 65535 6/0xff

cat test_data/trace1
0xc0a80005 0xc0a80009 450 53 0x06

I run the test by:
sudo ./testacl -n 2 -c 4 -- --rulesf=./test_data/rule1
 --tracef=./test_data/trace1

The result shows that the packet matches the second rule,  which is wrong.
The dest port of the pkt is 53, so it should match the third rule."

Indeed there is problem at ACL build stage.
Sometimes acl_merge_trie() is too aggressive in trying to conserve
space at build time.
So it takes a wrong assumptions and didn't duplicate a node,
even when it should.
The easiest and safest fix seems to always duplicate a left non-root/non-leaf
node first, and let the further code to destroy the node, if it is not needed.

Signed-off-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
---
 lib/librte_acl/acl_bld.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c
index a406737..92a85df 100644
--- a/lib/librte_acl/acl_bld.c
+++ b/lib/librte_acl/acl_bld.c
@@ -1044,9 +1044,7 @@ acl_merge_trie(struct acl_build_context *context,
 	 * a subtree of the merging tree (node B side). Otherwise,
 	 * just use node A.
 	 */
-	if (level > 0 &&
-			node_a->subtree_id !=
-			(subtree_id | RTE_ACL_SUBTREE_NODE)) {
+	if (level > 0) {
 		node_c = acl_dup_node(context, node_a);
 		node_c->subtree_id = subtree_id | RTE_ACL_SUBTREE_NODE;
 	}
-- 
2.4.2

[PATCHv2 2/3] ACL: add new test case for ranges build

[Konstantin Ananyev]

Signed-off-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
---
 app/test/test_acl.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 143 insertions(+), 4 deletions(-)

diff --git a/app/test/test_acl.c b/app/test/test_acl.c
index 7119ad3..6a032f9 100644
--- a/app/test/test_acl.c
+++ b/app/test/test_acl.c
@@ -191,7 +191,8 @@ err:
 }
 
 static int
-test_classify_buid(struct rte_acl_ctx *acx)
+test_classify_buid(struct rte_acl_ctx *acx,
+	const struct rte_acl_ipv4vlan_rule *rules, uint32_t num)
 {
 	int ret;
 	const uint32_t layout[RTE_ACL_IPV4VLAN_NUM] = {
@@ -203,8 +204,7 @@ test_classify_buid(struct rte_acl_ctx *acx)
 	};
 
 	/* add rules to the context */
-	ret = rte_acl_ipv4vlan_add_rules(acx, acl_test_rules,
-			RTE_DIM(acl_test_rules));
+	ret = rte_acl_ipv4vlan_add_rules(acx, rules, num);
 	if (ret != 0) {
 		printf("Line %i: Adding rules to ACL context failed!\n",
 			__LINE__);
@@ -246,7 +246,8 @@ test_classify(void)
 		else
 			rte_acl_reset_rules(acx);
 
-		ret = test_classify_buid(acx);
+		ret = test_classify_buid(acx, acl_test_rules,
+			RTE_DIM(acl_test_rules));
 		if (ret != 0) {
 			printf("Line %i, iter: %d: "
 				"Adding rules to ACL context failed!\n",
@@ -275,6 +276,142 @@ test_classify(void)
 	return ret;
 }
 
+static int
+test_build_ports_range(void)
+{
+	static const struct rte_acl_ipv4vlan_rule test_rules[] = {
+		{
+			/* match all packets. */
+			.data = {
+				.userdata = 1,
+				.category_mask = ACL_ALLOW_MASK,
+				.priority = 101,
+			},
+			.src_port_low = 0,
+			.src_port_high = UINT16_MAX,
+			.dst_port_low = 0,
+			.dst_port_high = UINT16_MAX,
+		},
+		{
+			/* match all packets with dst ports [54-65280]. */
+			.data = {
+				.userdata = 2,
+				.category_mask = ACL_ALLOW_MASK,
+				.priority = 102,
+			},
+			.src_port_low = 0,
+			.src_port_high = UINT16_MAX,
+			.dst_port_low = 54,
+			.dst_port_high = 65280,
+		},
+		{
+			/* match all packets with dst ports [0-52]. */
+			.data = {
+				.userdata = 3,
+				.category_mask = ACL_ALLOW_MASK,
+				.priority = 103,
+			},
+			.src_port_low = 0,
+			.src_port_high = UINT16_MAX,
+			.dst_port_low = 0,
+			.dst_port_high = 52,
+		},
+		{
+			/* match all packets with dst ports [53]. */
+			.data = {
+				.userdata = 4,
+				.category_mask = ACL_ALLOW_MASK,
+				.priority = 99,
+			},
+			.src_port_low = 0,
+			.src_port_high = UINT16_MAX,
+			.dst_port_low = 53,
+			.dst_port_high = 53,
+		},
+		{
+			/* match all packets with dst ports [65279-65535]. */
+			.data = {
+				.userdata = 5,
+				.category_mask = ACL_ALLOW_MASK,
+				.priority = 98,
+			},
+			.src_port_low = 0,
+			.src_port_high = UINT16_MAX,
+			.dst_port_low = 65279,
+			.dst_port_high = UINT16_MAX,
+		},
+	};
+
+	static struct ipv4_7tuple test_data[] = {
+		{
+			.proto = 6,
+			.ip_src = IPv4(10, 1, 1, 1),
+			.ip_dst = IPv4(192, 168, 0, 33),
+			.port_dst = 53,
+			.allow = 1,
+		},
+		{
+			.proto = 6,
+			.ip_src = IPv4(127, 84, 33, 1),
+			.ip_dst = IPv4(1, 2, 3, 4),
+			.port_dst = 65281,
+			.allow = 1,
+		},
+	};
+
+	struct rte_acl_ctx *acx;
+	int32_t ret, i, j;
+	uint32_t results[RTE_DIM(test_data)];
+	const uint8_t *data[RTE_DIM(test_data)];
+
+	acx = rte_acl_create(&acl_param);
+	if (acx == NULL) {
+		printf("Line %i: Error creating ACL context!\n", __LINE__);
+		return -1;
+	}
+
+	/* swap all bytes in the data to network order */
+	bswap_test_data(test_data, RTE_DIM(test_data), 1);
+
+	/* store pointers to test data */
+	for (i = 0; i != RTE_DIM(test_data); i++)
+		data[i] = (uint8_t *)&test_data[i];
+
+	for (i = 0; i != RTE_DIM(test_rules); i++) {
+		rte_acl_reset(acx);
+		ret = test_classify_buid(acx, test_rules, i + 1);
+		if (ret != 0) {
+			printf("Line %i, iter: %d: "
+				"Adding rules to ACL context failed!\n",
+				__LINE__, i);
+			break;
+		}
+		ret = rte_acl_classify(acx, data, results,
+			RTE_DIM(data), 1);
+		if (ret != 0) {
+			printf("Line %i, iter: %d: classify failed!\n",
+				__LINE__, i);
+			break;
+		}
+
+		/* check results */
+		for (j = 0; j != RTE_DIM(results); j++) {
+			if (results[j] != test_data[j].allow) {
+				printf("Line %i: Error in allow results at %i "
+					"(expected %"PRIu32" got %"PRIu32")!\n",
+					__LINE__, j, test_data[j].allow,
+					results[j]);
+				ret = -EINVAL;
+			}
+		}
+	}
+
+	bswap_test_data(test_data, RTE_DIM(test_data), 0);
+
+	rte_acl_free(acx);
+	return ret;
+}
+
 /*
  * Test wrong layout behavior
  * This test supplies the ACL context with invalid layout, which results in
@@ -930,6 +1067,8 @@ test_acl(void)
 		return -1;
 	if (test_classify() < 0)
 		return -1;
+	if (test_build_ports_range() < 0)
+		return -1;
 
 	return 0;
 }
-- 
2.4.2

[PATCHv2 3/3] ACL: remove subtree_id calculations at build stage

[Konstantin Ananyev]

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

Re: [PATCHv2 0/3] ACL: Fix bug in acl_merge_trie() and add a new test-case for it to the UT

[Thomas Monjalon]

2015-06-03 18:45, Konstantin Ananyev:
> v2:
> - reorder code a bit to avoid gcc 5.1 warnings.
> 
> Konstantin Ananyev (3):
>   ACL: fix a problem in acl_merge_trie
>   ACL: add new test case for ranges build
>   ACL: remove subtree_id calculations at build stage

Applied, thanks