[dpdk-dev] [PATCH 0/2] acl: fix 32-bit range field doesn't work properly

[dpdk-dev] [PATCH 0/2] acl: fix 32-bit range field doesn't work properly

[Konstantin Ananyev]

Fix problem with ACL library for 32-bit range fields,
and extend UT to cover such cases in future.

Konstantin Ananyev (2):
  acl: fix 32-bit range field doesn't work properly
  test/acl: add 32-bit range test-case

 app/test/test_acl.c      | 164 +++++++++++++++++++++++++++++++++------
 app/test/test_acl.h      |  43 ++++++++++
 lib/librte_acl/acl_bld.c | 148 +++++++++++++++++++++++++----------
 3 files changed, 290 insertions(+), 65 deletions(-)

-- 
2.17.1

[dpdk-dev] [PATCH 1/2] acl: fix 32-bit range field doesn't work properly

[Konstantin Ananyev]

ACL build phase for range fields that are bigger then
16 bits might generate wrong trie.
For more details please refer to:
https://bugs.dpdk.org/show_bug.cgi?id=307

Fixes: dc276b5780c2 ("acl: new library")
Cc: stable@dpdk.org

Reported-by: Ido Goshen <Ido@cgstowernetworks.com>
Signed-off-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
---
 lib/librte_acl/acl_bld.c | 148 ++++++++++++++++++++++++++++-----------
 1 file changed, 106 insertions(+), 42 deletions(-)

diff --git a/lib/librte_acl/acl_bld.c b/lib/librte_acl/acl_bld.c
index b06bbe920..0ae143e4e 100644
--- a/lib/librte_acl/acl_bld.c
+++ b/lib/librte_acl/acl_bld.c
@@ -778,9 +778,8 @@ acl_build_reset(struct rte_acl_ctx *ctx)
 }
 
 static void
-acl_gen_range(struct acl_build_context *context,
-	const uint8_t *hi, const uint8_t *lo, int size, int level,
-	struct rte_acl_node *root, struct rte_acl_node *end)
+acl_gen_full_range(struct acl_build_context *context, struct rte_acl_node *root,
+	struct rte_acl_node *end, int size, int level)
 {
 	struct rte_acl_node *node, *prev;
 	uint32_t n;
@@ -788,10 +787,71 @@ acl_gen_range(struct acl_build_context *context,
 	prev = root;
 	for (n = size - 1; n > 0; n--) {
 		node = acl_alloc_node(context, level++);
-		acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
+		acl_add_ptr_range(context, prev, node, 0, UINT8_MAX);
 		prev = node;
 	}
-	acl_add_ptr_range(context, prev, end, lo[0], hi[0]);
+	acl_add_ptr_range(context, prev, end, 0, UINT8_MAX);
+}
+
+static void
+acl_gen_range_mdl(struct acl_build_context *context, struct rte_acl_node *root,
+	struct rte_acl_node *end, uint8_t lo, uint8_t hi, int size, int level)
+{
+	struct rte_acl_node *node;
+
+	node = acl_alloc_node(context, level++);
+	acl_add_ptr_range(context, root, node, lo, hi);
+	acl_gen_full_range(context, node, end, size - 1, level);
+}
+
+static void
+acl_gen_range_low(struct acl_build_context *context, struct rte_acl_node *root,
+	struct rte_acl_node *end, const uint8_t *lo, int size, int level)
+{
+	struct rte_acl_node *node;
+	uint32_t n;
+
+	n = size - 1;
+	if (n == 0) {
+		acl_add_ptr_range(context, root, end, lo[0], UINT8_MAX);
+		return;
+	}
+
+	node = acl_alloc_node(context, level++);
+	acl_add_ptr_range(context, root, node, lo[n], lo[n]);
+
+	/* generate lower-bound sub-trie */
+	acl_gen_range_low(context, node, end, lo, n, level);
+
+	/* generate middle sub-trie */
+	if (n > 1 && lo[n - 1] != UINT8_MAX)
+		acl_gen_range_mdl(context, node, end, lo[n - 1] + 1, UINT8_MAX,
+			n, level);
+}
+
+static void
+acl_gen_range_high(struct acl_build_context *context, struct rte_acl_node *root,
+	struct rte_acl_node *end, const uint8_t *hi, int size, int level)
+{
+	struct rte_acl_node *node;
+	uint32_t n;
+
+	n = size - 1;
+	if (n == 0) {
+		acl_add_ptr_range(context, root, end, 0, hi[0]);
+		return;
+	}
+
+	node = acl_alloc_node(context, level++);
+	acl_add_ptr_range(context, root, node, hi[n], hi[n]);
+
+	/* generate upper-bound sub-trie */
+	acl_gen_range_high(context, node, end, hi, n, level);
+
+	/* generate middle sub-trie */
+	if (n > 1 && hi[n - 1] != 0)
+		acl_gen_range_mdl(context, node, end, 0, hi[n - 1] - 1,
+			n, level);
 }
 
 static struct rte_acl_node *
@@ -799,52 +859,56 @@ acl_gen_range_trie(struct acl_build_context *context,
 	const void *min, const void *max,
 	int size, int level, struct rte_acl_node **pend)
 {
-	int32_t n;
-	struct rte_acl_node *root;
-	const uint8_t *lo = min;
-	const uint8_t *hi = max;
+	int32_t k, n;
+	uint8_t hi_ff, lo_00;
+	struct rte_acl_node *node, *prev, *root;
+	const uint8_t *lo;
+	const uint8_t *hi;
+
+	lo = min;
+	hi = max;
 
-	*pend = acl_alloc_node(context, level+size);
+	*pend = acl_alloc_node(context, level + size);
 	root = acl_alloc_node(context, level++);
+	prev = root;
 
-	if (lo[size - 1] == hi[size - 1]) {
-		acl_gen_range(context, hi, lo, size, level, root, *pend);
-	} else {
-		uint8_t limit_lo[64];
-		uint8_t limit_hi[64];
-		uint8_t hi_ff = UINT8_MAX;
-		uint8_t lo_00 = 0;
+	/* build common sub-trie till possilbe */
+	for (n = size - 1; n > 0 && lo[n] == hi[n]; n--) {
+		node = acl_alloc_node(context, level++);
+		acl_add_ptr_range(context, prev, node, lo[n], hi[n]);
+		prev = node;
+	}
 
-		memset(limit_lo, 0, RTE_DIM(limit_lo));
-		memset(limit_hi, UINT8_MAX, RTE_DIM(limit_hi));
+	/* no branchs needed, just one sub-trie */
+	if (n == 0) {
+		acl_add_ptr_range(context, prev, *pend, lo[0], hi[0]);
+		return root;
+	}
 
-		for (n = size - 2; n >= 0; n--) {
-			hi_ff = (uint8_t)(hi_ff & hi[n]);
-			lo_00 = (uint8_t)(lo_00 | lo[n]);
-		}
+	/* gather information about divirgent paths */
+	lo_00 = 0;
+	hi_ff = UINT8_MAX;
+	for (k = n - 1; k >= 0; k--) {
+		hi_ff &= hi[k];
+		lo_00 |= lo[k];
+	}
 
-		if (hi_ff != UINT8_MAX) {
-			limit_lo[size - 1] = hi[size - 1];
-			acl_gen_range(context, hi, limit_lo, size, level,
-				root, *pend);
-		}
+	/* generate left (lower-bound) sub-trie */
+	if (lo_00 != 0)
+		acl_gen_range_low(context, prev, *pend, lo, n + 1, level);
 
-		if (lo_00 != 0) {
-			limit_hi[size - 1] = lo[size - 1];
-			acl_gen_range(context, limit_hi, lo, size, level,
-				root, *pend);
-		}
+	/* generate right (upper-bound) sub-trie */
+	if (hi_ff != UINT8_MAX)
+		acl_gen_range_high(context, prev, *pend, hi, n + 1, level);
 
-		if (hi[size - 1] - lo[size - 1] > 1 ||
-				lo_00 == 0 ||
-				hi_ff == UINT8_MAX) {
-			limit_lo[size-1] = (uint8_t)(lo[size-1] + (lo_00 != 0));
-			limit_hi[size-1] = (uint8_t)(hi[size-1] -
-				(hi_ff != UINT8_MAX));
-			acl_gen_range(context, limit_hi, limit_lo, size,
-				level, root, *pend);
-		}
+	/* generate sub-trie in the middle */
+	if (lo[n] + 1 != hi[n] || lo_00 == 0 || hi_ff == UINT8_MAX) {
+		lo_00 = lo[n] + (lo_00 != 0);
+		hi_ff = hi[n] - (hi_ff != UINT8_MAX);
+		acl_gen_range_mdl(context, prev, *pend, lo_00, hi_ff,
+			n + 1, level);
 	}
+
 	return root;
 }
 
-- 
2.17.1

[dpdk-dev] [PATCH 2/2] test/acl: add 32-bit range test-case

[Konstantin Ananyev]

Add new test-case to improve test coverage for 32-bit range fields.

Suggested-by: Ido Goshen <Ido@cgstowernetworks.com>
Signed-off-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
---
 app/test/test_acl.c | 164 +++++++++++++++++++++++++++++++++++++-------
 app/test/test_acl.h |  43 ++++++++++++
 2 files changed, 184 insertions(+), 23 deletions(-)

diff --git a/app/test/test_acl.c b/app/test/test_acl.c
index 9cd9e37db..501de35da 100644
--- a/app/test/test_acl.c
+++ b/app/test/test_acl.c
@@ -269,25 +269,25 @@ rte_acl_ipv4vlan_build(struct rte_acl_ctx *ctx,
  * Test scalar and SSE ACL lookup.
  */
 static int
-test_classify_run(struct rte_acl_ctx *acx)
+test_classify_run(struct rte_acl_ctx *acx, struct ipv4_7tuple test_data[],
+	size_t dim)
 {
 	int ret, i;
 	uint32_t result, count;
-	uint32_t results[RTE_DIM(acl_test_data) * RTE_ACL_MAX_CATEGORIES];
-	const uint8_t *data[RTE_DIM(acl_test_data)];
-
+	uint32_t results[dim * RTE_ACL_MAX_CATEGORIES];
+	const uint8_t *data[dim];
 	/* swap all bytes in the data to network order */
-	bswap_test_data(acl_test_data, RTE_DIM(acl_test_data), 1);
+	bswap_test_data(test_data, dim, 1);
 
 	/* store pointers to test data */
-	for (i = 0; i < (int) RTE_DIM(acl_test_data); i++)
-		data[i] = (uint8_t *)&acl_test_data[i];
+	for (i = 0; i < (int) dim; i++)
+		data[i] = (uint8_t *)&test_data[i];
 
 	/**
 	 * these will run quite a few times, it's necessary to test code paths
 	 * from num=0 to num>8
 	 */
-	for (count = 0; count <= RTE_DIM(acl_test_data); count++) {
+	for (count = 0; count <= dim; count++) {
 		ret = rte_acl_classify(acx, data, results,
 				count, RTE_ACL_MAX_CATEGORIES);
 		if (ret != 0) {
@@ -299,10 +299,10 @@ test_classify_run(struct rte_acl_ctx *acx)
 		for (i = 0; i < (int) count; i++) {
 			result =
 				results[i * RTE_ACL_MAX_CATEGORIES + ACL_ALLOW];
-			if (result != acl_test_data[i].allow) {
+			if (result != test_data[i].allow) {
 				printf("Line %i: Error in allow results at %i "
 					"(expected %"PRIu32" got %"PRIu32")!\n",
-					__LINE__, i, acl_test_data[i].allow,
+					__LINE__, i, test_data[i].allow,
 					result);
 				ret = -EINVAL;
 				goto err;
@@ -312,10 +312,10 @@ test_classify_run(struct rte_acl_ctx *acx)
 		/* check if we deny everything we should deny */
 		for (i = 0; i < (int) count; i++) {
 			result = results[i * RTE_ACL_MAX_CATEGORIES + ACL_DENY];
-			if (result != acl_test_data[i].deny) {
+			if (result != test_data[i].deny) {
 				printf("Line %i: Error in deny results at %i "
 					"(expected %"PRIu32" got %"PRIu32")!\n",
-					__LINE__, i, acl_test_data[i].deny,
+					__LINE__, i, test_data[i].deny,
 					result);
 				ret = -EINVAL;
 				goto err;
@@ -325,7 +325,7 @@ test_classify_run(struct rte_acl_ctx *acx)
 
 	/* make a quick check for scalar */
 	ret = rte_acl_classify_alg(acx, data, results,
-			RTE_DIM(acl_test_data), RTE_ACL_MAX_CATEGORIES,
+			dim, RTE_ACL_MAX_CATEGORIES,
 			RTE_ACL_CLASSIFY_SCALAR);
 	if (ret != 0) {
 		printf("Line %i: scalar classify failed!\n", __LINE__);
@@ -333,12 +333,12 @@ test_classify_run(struct rte_acl_ctx *acx)
 	}
 
 	/* check if we allow everything we should allow */
-	for (i = 0; i < (int) RTE_DIM(acl_test_data); i++) {
+	for (i = 0; i < (int) dim; i++) {
 		result = results[i * RTE_ACL_MAX_CATEGORIES + ACL_ALLOW];
-		if (result != acl_test_data[i].allow) {
+		if (result != test_data[i].allow) {
 			printf("Line %i: Error in allow results at %i "
 					"(expected %"PRIu32" got %"PRIu32")!\n",
-					__LINE__, i, acl_test_data[i].allow,
+					__LINE__, i, test_data[i].allow,
 					result);
 			ret = -EINVAL;
 			goto err;
@@ -346,12 +346,12 @@ test_classify_run(struct rte_acl_ctx *acx)
 	}
 
 	/* check if we deny everything we should deny */
-	for (i = 0; i < (int) RTE_DIM(acl_test_data); i++) {
+	for (i = 0; i < (int) dim; i++) {
 		result = results[i * RTE_ACL_MAX_CATEGORIES + ACL_DENY];
-		if (result != acl_test_data[i].deny) {
+		if (result != test_data[i].deny) {
 			printf("Line %i: Error in deny results at %i "
 					"(expected %"PRIu32" got %"PRIu32")!\n",
-					__LINE__, i, acl_test_data[i].deny,
+					__LINE__, i, test_data[i].deny,
 					result);
 			ret = -EINVAL;
 			goto err;
@@ -362,7 +362,7 @@ test_classify_run(struct rte_acl_ctx *acx)
 
 err:
 	/* swap data back to cpu order so that next time tests don't fail */
-	bswap_test_data(acl_test_data, RTE_DIM(acl_test_data), 0);
+	bswap_test_data(test_data, dim, 0);
 	return ret;
 }
 
@@ -425,7 +425,8 @@ test_classify(void)
 			break;
 		}
 
-		ret = test_classify_run(acx);
+		ret = test_classify_run(acx, acl_test_data,
+			RTE_DIM(acl_test_data));
 		if (ret != 0) {
 			printf("Line %i, iter: %d: %s failed!\n",
 				__LINE__, i, __func__);
@@ -434,7 +435,8 @@ test_classify(void)
 
 		/* reset rules and make sure that classify still works ok. */
 		rte_acl_reset_rules(acx);
-		ret = test_classify_run(acx);
+		ret = test_classify_run(acx, acl_test_data,
+			RTE_DIM(acl_test_data));
 		if (ret != 0) {
 			printf("Line %i, iter: %d: %s failed!\n",
 				__LINE__, i, __func__);
@@ -925,7 +927,8 @@ test_convert_rules(const char *desc,
 			break;
 		}
 
-		rc = test_classify_run(acx);
+		rc = test_classify_run(acx, acl_test_data,
+			RTE_DIM(acl_test_data));
 		if (rc != 0)
 			printf("%s failed at line %i, max_size=%zu\n",
 				__func__, __LINE__, mem_sizes[i]);
@@ -1597,6 +1600,119 @@ test_misc(void)
 	return 0;
 }
 
+static uint32_t
+get_u32_range_max(void)
+{
+	uint32_t i, max;
+
+	max = 0;
+	for (i = 0; i != RTE_DIM(acl_u32_range_test_rules); i++)
+		max = RTE_MAX(max, acl_u32_range_test_rules[i].src_mask_len);
+	return max;
+}
+
+static uint32_t
+get_u32_range_min(void)
+{
+	uint32_t i, min;
+
+	min = UINT32_MAX;
+	for (i = 0; i != RTE_DIM(acl_u32_range_test_rules); i++)
+		min = RTE_MIN(min, acl_u32_range_test_rules[i].src_addr);
+	return min;
+}
+
+static const struct rte_acl_ipv4vlan_rule *
+find_u32_range_rule(uint32_t val)
+{
+	uint32_t i;
+
+	for (i = 0; i != RTE_DIM(acl_u32_range_test_rules); i++) {
+		if (val >= acl_u32_range_test_rules[i].src_addr &&
+				val <= acl_u32_range_test_rules[i].src_mask_len)
+			return acl_u32_range_test_rules + i;
+	}
+	return NULL;
+}
+
+static void
+fill_u32_range_data(struct ipv4_7tuple tdata[], uint32_t start, uint32_t num)
+{
+	uint32_t i;
+	const struct rte_acl_ipv4vlan_rule *r;
+
+	for (i = 0; i != num; i++) {
+		tdata[i].ip_src = start + i;
+		r = find_u32_range_rule(start + i);
+		if (r != NULL)
+			tdata[i].allow = r->data.userdata;
+	}
+}
+
+static int
+test_u32_range(void)
+{
+	int32_t rc;
+	uint32_t i, k, max, min;
+	struct rte_acl_ctx *acx;
+	struct acl_ipv4vlan_rule r;
+	struct ipv4_7tuple test_data[64];
+
+	acx = rte_acl_create(&acl_param);
+	if (acx == NULL) {
+		printf("%s#%i: Error creating ACL context!\n",
+			__func__, __LINE__);
+		return -1;
+	}
+
+	for (i = 0; i != RTE_DIM(acl_u32_range_test_rules); i++) {
+		convert_rule(&acl_u32_range_test_rules[i], &r);
+		rc = rte_acl_add_rules(acx, (struct rte_acl_rule *)&r, 1);
+		if (rc != 0) {
+			printf("%s#%i: Adding rule to ACL context "
+				"failed with error code: %d\n",
+				__func__, __LINE__, rc);
+			rte_acl_free(acx);
+			return rc;
+		}
+	}
+
+	rc = build_convert_rules(acx, convert_config_2, 0);
+	if (rc != 0) {
+		printf("%s#%i Error @ build_convert_rules!\n",
+			__func__, __LINE__);
+		rte_acl_free(acx);
+		return rc;
+	}
+
+	max = get_u32_range_max();
+	min = get_u32_range_min();
+
+	max = RTE_MAX(max, max + 1);
+	min = RTE_MIN(min, min - 1);
+
+	printf("%s#%d starting range test from %u to %u\n",
+		__func__, __LINE__, min, max);
+
+	for (i = min; i <= max; i += k) {
+
+		k = RTE_MIN(max - i + 1, RTE_DIM(test_data));
+
+		memset(test_data, 0, sizeof(test_data));
+		fill_u32_range_data(test_data, i, k);
+
+		rc = test_classify_run(acx, test_data, k);
+		if (rc != 0) {
+			printf("%s#%d failed at [%u, %u) interval\n",
+				__func__, __LINE__, i, i + k);
+			break;
+		}
+	}
+
+	rte_acl_free(acx);
+	return rc;
+}
+
 static int
 test_acl(void)
 {
@@ -1616,6 +1732,8 @@ test_acl(void)
 		return -1;
 	if (test_convert() < 0)
 		return -1;
+	if (test_u32_range() < 0)
+		return -1;
 
 	return 0;
 }
diff --git a/app/test/test_acl.h b/app/test/test_acl.h
index 4f6e659c7..4cdead0b7 100644
--- a/app/test/test_acl.h
+++ b/app/test/test_acl.h
@@ -666,4 +666,47 @@ struct ipv4_7tuple acl_test_data[] = {
 		}, /* should not match */
 };
 
+/*
+ * ruleset for ACL 32 bit range (by src addr) unit test
+ * keep them ordered by priority in descending order.
+ */
+struct rte_acl_ipv4vlan_rule acl_u32_range_test_rules[] = {
+		{
+			.data = {
+				.userdata = 500,
+				.category_mask = ACL_ALLOW_MASK,
+				.priority = 500
+			},
+			.src_addr = RTE_IPV4(0, 0, 0, 1),
+			.src_mask_len = RTE_IPV4(0, 0, 2, 58),
+		},
+		{
+			.data = {
+				.userdata = 400,
+				.category_mask = ACL_ALLOW_MASK,
+				.priority = 400
+			},
+			.src_addr = RTE_IPV4(0, 4, 3, 2),
+			.src_mask_len = RTE_IPV4(0, 4, 7, 255),
+		},
+		{
+			.data = {
+				.userdata = 300,
+				.category_mask = ACL_ALLOW_MASK,
+				.priority = 300
+			},
+			.src_addr = RTE_IPV4(0, 1, 12, 14),
+			.src_mask_len = RTE_IPV4(0, 3, 11, 13),
+		},
+		{
+			.data = {
+				.userdata = 200,
+				.category_mask = ACL_ALLOW_MASK,
+				.priority = 200
+			},
+			.src_addr = RTE_IPV4(0, 0, 1, 40),
+			.src_mask_len = RTE_IPV4(0, 4, 5, 6),
+		},
+};
+
 #endif /* TEST_ACL_H_ */
-- 
2.17.1

Re: [dpdk-dev] [PATCH 0/2] acl: fix 32-bit range field doesn't work properly

[David Marchand]

On Wed, Feb 12, 2020 at 2:48 PM Konstantin Ananyev
<konstantin.ananyev@intel.com> wrote:
>
> Fix problem with ACL library for 32-bit range fields,
> and extend UT to cover such cases in future.
>
> Konstantin Ananyev (2):
>   acl: fix 32-bit range field doesn't work properly
>   test/acl: add 32-bit range test-case
>
>  app/test/test_acl.c      | 164 +++++++++++++++++++++++++++++++++------
>  app/test/test_acl.h      |  43 ++++++++++
>  lib/librte_acl/acl_bld.c | 148 +++++++++++++++++++++++++----------
>  3 files changed, 290 insertions(+), 65 deletions(-)
>

Series applied, thanks.



--
David Marchand