patches for DPDK stable branches
 help / color / mirror / Atom feed
* [dpdk-stable] patch 'acl: fix 32-bit match for range field' has been queued to LTS release 18.11.7
@ 2020-02-19 15:55 Kevin Traynor
  2020-02-19 15:55 ` [dpdk-stable] patch 'examples/ethtool: fix unchecked return value' " Kevin Traynor
                   ` (20 more replies)
  0 siblings, 21 replies; 22+ messages in thread
From: Kevin Traynor @ 2020-02-19 15:55 UTC (permalink / raw)
  To: Konstantin Ananyev; +Cc: Ido Goshen, dpdk stable

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@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@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 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@dpdk.org


^ permalink raw reply	[flat|nested] 22+ messages in thread
end of thread, other threads:[~2020-02-19 15:58 UTC | newest]

Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-02-19 15:55 [dpdk-stable] patch 'acl: fix 32-bit match for range field' has been queued to LTS release 18.11.7 Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'examples/ethtool: fix unchecked return value' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'kni: fix build with Linux 5.6' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'fix Mellanox copyright and SPDX tag' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'kni: fix not contiguous FIFO' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'examples/l3fwd-power: fix a typo' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'examples/l3fwd-power: fix interrupt disable' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'lib: fix unnecessary double negation' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'crypto/ccp: fix queue alignment' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'test/compress: replace test vector' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'drivers/crypto: fix session-less mode' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'net/bnxt: fix buffer allocation reattempt' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'net/netvsc: initialize link state' " Kevin Traynor
2020-02-19 15:55 ` [dpdk-stable] patch 'net/ixgbe: remove dead code' " Kevin Traynor
2020-02-19 15:56 ` [dpdk-stable] patch 'net/mlx5: fix VLAN match for DV mode' " Kevin Traynor
2020-02-19 15:56 ` [dpdk-stable] patch 'vhost: check message header size read' " Kevin Traynor
2020-02-19 15:56 ` [dpdk-stable] patch 'vhost: protect log address translation in IOTLB update' " Kevin Traynor
2020-02-19 15:56 ` [dpdk-stable] patch 'app/testpmd: fix hot-unplug detaching' " Kevin Traynor
2020-02-19 15:56 ` [dpdk-stable] patch 'net/i40e: fix unchecked Tx cleanup error' " Kevin Traynor
2020-02-19 15:56 ` [dpdk-stable] patch 'app/eventdev: fix pipeline test with meson build' " Kevin Traynor
2020-02-19 15:56 ` [dpdk-stable] patch 'usertools: fix syntax warning in python 3.8' " Kevin Traynor
2020-02-19 15:56 ` [dpdk-stable] patch 'usertools: fix telemetry client with python 3' " Kevin Traynor

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).