* [dpdk-dev] [PATCH 1/2] acl: fix 32-bit range field doesn't work properly
2020-02-12 13:47 [dpdk-dev] [PATCH 0/2] acl: fix 32-bit range field doesn't work properly Konstantin Ananyev
@ 2020-02-12 13:47 ` Konstantin Ananyev
2020-02-12 13:47 ` [dpdk-dev] [PATCH 2/2] test/acl: add 32-bit range test-case Konstantin Ananyev
2020-02-13 13:57 ` [dpdk-dev] [PATCH 0/2] acl: fix 32-bit range field doesn't work properly David Marchand
2 siblings, 0 replies; 4+ messages in thread
From: Konstantin Ananyev @ 2020-02-12 13:47 UTC (permalink / raw)
To: dev; +Cc: Ido, Konstantin Ananyev, stable
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
^ permalink raw reply [flat|nested] 4+ messages in thread* [dpdk-dev] [PATCH 2/2] test/acl: add 32-bit range test-case
2020-02-12 13:47 [dpdk-dev] [PATCH 0/2] acl: fix 32-bit range field doesn't work properly Konstantin Ananyev
2020-02-12 13:47 ` [dpdk-dev] [PATCH 1/2] " Konstantin Ananyev
@ 2020-02-12 13:47 ` Konstantin Ananyev
2020-02-13 13:57 ` [dpdk-dev] [PATCH 0/2] acl: fix 32-bit range field doesn't work properly David Marchand
2 siblings, 0 replies; 4+ messages in thread
From: Konstantin Ananyev @ 2020-02-12 13:47 UTC (permalink / raw)
To: dev; +Cc: Ido, 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
^ permalink raw reply [flat|nested] 4+ messages in thread