[dpdk-stable] patch 'acl: fix 32-bit match for range field' has been queued to LTS release 18.11.7

[Kevin Traynor]

Hi,

FYI, your patch has been queued to LTS release 18.11.7

Note it hasn't been pushed to http://dpdk.org/browse/dpdk-stable yet.
It will be pushed if I get no objections before 02/25/20. So please
shout if anyone has objections.

Also note that after the patch there's a diff of the upstream commit vs the
patch applied to the branch. This will indicate if there was any rebasing
needed to apply to the stable branch. If there were code changes for rebasing
(ie: not only metadata diffs), please double check that the rebase was
correctly done.

Queued patches are on a temporary branch at:
https://github.com/kevintraynor/dpdk-stable-queue

This queued commit can be viewed at:
https://github.com/kevintraynor/dpdk-stable-queue/commit/2527d59084537b2915aa6f80c45df404688fbba6

Thanks.

Kevin.

---
>From 2527d59084537b2915aa6f80c45df404688fbba6 Mon Sep 17 00:00:00 2001
From: Konstantin Ananyev <konstantin.ananyev at intel.com>
Date: Wed, 12 Feb 2020 13:47:44 +0000
Subject: [PATCH] acl: fix 32-bit match for range field

[ upstream commit dbed2c9ef8d3e0c99d026c5bd401c9e2c3d0bdcd ]

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

Bugzilla ID: 307
Fixes: dc276b5780c2 ("acl: new library")

Reported-by: Ido Goshen <ido at cgstowernetworks.com>
Signed-off-by: Konstantin Ananyev <konstantin.ananyev at 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 b06bbe9207..d1f920b09c 100644
--- a/lib/librte_acl/acl_bld.c
+++ b/lib/librte_acl/acl_bld.c
@@ -779,7 +779,6 @@ 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;
@@ -789,8 +788,69 @@ acl_gen_range(struct acl_build_context *context,
 	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);
 }
 
@@ -800,50 +860,54 @@ acl_gen_range_trie(struct acl_build_context *context,
 	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;
 
-	*pend = acl_alloc_node(context, level+size);
+	lo = min;
+	hi = max;
+
+	*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 possible */
+	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 branch 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.21.1

---
  Diff of the applied patch vs upstream commit (please double-check if non-empty:
---
--- -	2020-02-19 15:43:49.810782365 +0000
+++ 0001-acl-fix-32-bit-match-for-range-field.patch	2020-02-19 15:43:49.713142357 +0000
@@ -1 +1 @@
-From dbed2c9ef8d3e0c99d026c5bd401c9e2c3d0bdcd Mon Sep 17 00:00:00 2001
+From 2527d59084537b2915aa6f80c45df404688fbba6 Mon Sep 17 00:00:00 2001
@@ -5,0 +6,2 @@
+[ upstream commit dbed2c9ef8d3e0c99d026c5bd401c9e2c3d0bdcd ]
+
@@ -13 +14,0 @@
-Cc: stable at dpdk.org