From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 39C4FA0555 for ; Wed, 19 Feb 2020 16:56:39 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id E9DB91B951; Wed, 19 Feb 2020 16:56:38 +0100 (CET) Received: from us-smtp-delivery-1.mimecast.com (us-smtp-1.mimecast.com [205.139.110.61]) by dpdk.org (Postfix) with ESMTP id 392AE1B951 for ; Wed, 19 Feb 2020 16:56:38 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1582127797; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=8Fn2PsdJmRyw7F1+JKZJp1I4bxpB+r/7VCtoISkLYkY=; b=KMPeaXFHYO4c5/p2PzhaG0qnKTZyU+3CjZX+/Bg4KU/+uPl8HfVwCdx27alDH3oUUuR0gI TvWBsbY9AiUnnoPeTJTwWHs4ZBWLdpXqEXfkauTmS5mH7f8lmoPPR7FXWcpNQMxiIsPla5 qoT6XqLPK13oTZ1oQQTxsPJz+VjE2yg= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-270-LwfMq3BSOaWgR45lPZxQ9w-1; Wed, 19 Feb 2020 10:56:29 -0500 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 87D66800D48; Wed, 19 Feb 2020 15:56:28 +0000 (UTC) Received: from rh.redhat.com (unknown [10.33.36.109]) by smtp.corp.redhat.com (Postfix) with ESMTP id DBA5E8AC45; Wed, 19 Feb 2020 15:56:24 +0000 (UTC) From: Kevin Traynor To: Konstantin Ananyev Cc: Ido Goshen , dpdk stable Date: Wed, 19 Feb 2020 15:55:46 +0000 Message-Id: <20200219155607.20495-1-ktraynor@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-MC-Unique: LwfMq3BSOaWgR45lPZxQ9w-1 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable Subject: [dpdk-stable] patch 'acl: fix 32-bit match for range field' has been queued to LTS release 18.11.7 X-BeenThere: stable@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches for DPDK stable branches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: stable-bounces@dpdk.org Sender: "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 rebasi= ng (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/2527d59084537b2915= aa6f80c45df404688fbba6 Thanks. Kevin. --- >From 2527d59084537b2915aa6f80c45df404688fbba6 Mon Sep 17 00:00:00 2001 From: Konstantin Ananyev 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=3D307 Bugzilla ID: 307 Fixes: dc276b5780c2 ("acl: new library") Reported-by: Ido Goshen Signed-off-by: Konstantin Ananyev --- 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) =20 static void -acl_gen_range(struct acl_build_context *context, -=09const uint8_t *hi, const uint8_t *lo, int size, int level, -=09struct rte_acl_node *root, struct rte_acl_node *end) +acl_gen_full_range(struct acl_build_context *context, struct rte_acl_node = *root, +=09struct rte_acl_node *end, int size, int level) { =09struct rte_acl_node *node, *prev; @@ -789,8 +788,69 @@ acl_gen_range(struct acl_build_context *context, =09for (n =3D size - 1; n > 0; n--) { =09=09node =3D acl_alloc_node(context, level++); -=09=09acl_add_ptr_range(context, prev, node, lo[n], hi[n]); +=09=09acl_add_ptr_range(context, prev, node, 0, UINT8_MAX); =09=09prev =3D node; =09} -=09acl_add_ptr_range(context, prev, end, lo[0], hi[0]); +=09acl_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, +=09struct rte_acl_node *end, uint8_t lo, uint8_t hi, int size, int level) +{ +=09struct rte_acl_node *node; + +=09node =3D acl_alloc_node(context, level++); +=09acl_add_ptr_range(context, root, node, lo, hi); +=09acl_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, +=09struct rte_acl_node *end, const uint8_t *lo, int size, int level) +{ +=09struct rte_acl_node *node; +=09uint32_t n; + +=09n =3D size - 1; +=09if (n =3D=3D 0) { +=09=09acl_add_ptr_range(context, root, end, lo[0], UINT8_MAX); +=09=09return; +=09} + +=09node =3D acl_alloc_node(context, level++); +=09acl_add_ptr_range(context, root, node, lo[n], lo[n]); + +=09/* generate lower-bound sub-trie */ +=09acl_gen_range_low(context, node, end, lo, n, level); + +=09/* generate middle sub-trie */ +=09if (n > 1 && lo[n - 1] !=3D UINT8_MAX) +=09=09acl_gen_range_mdl(context, node, end, lo[n - 1] + 1, UINT8_MAX, +=09=09=09n, level); +} + +static void +acl_gen_range_high(struct acl_build_context *context, struct rte_acl_node = *root, +=09struct rte_acl_node *end, const uint8_t *hi, int size, int level) +{ +=09struct rte_acl_node *node; +=09uint32_t n; + +=09n =3D size - 1; +=09if (n =3D=3D 0) { +=09=09acl_add_ptr_range(context, root, end, 0, hi[0]); +=09=09return; +=09} + +=09node =3D acl_alloc_node(context, level++); +=09acl_add_ptr_range(context, root, node, hi[n], hi[n]); + +=09/* generate upper-bound sub-trie */ +=09acl_gen_range_high(context, node, end, hi, n, level); + +=09/* generate middle sub-trie */ +=09if (n > 1 && hi[n - 1] !=3D 0) +=09=09acl_gen_range_mdl(context, node, end, 0, hi[n - 1] - 1, +=09=09=09n, level); } =20 @@ -800,50 +860,54 @@ acl_gen_range_trie(struct acl_build_context *context, =09int size, int level, struct rte_acl_node **pend) { -=09int32_t n; -=09struct rte_acl_node *root; -=09const uint8_t *lo =3D min; -=09const uint8_t *hi =3D max; +=09int32_t k, n; +=09uint8_t hi_ff, lo_00; +=09struct rte_acl_node *node, *prev, *root; +=09const uint8_t *lo; +=09const uint8_t *hi; =20 -=09*pend =3D acl_alloc_node(context, level+size); +=09lo =3D min; +=09hi =3D max; + +=09*pend =3D acl_alloc_node(context, level + size); =09root =3D acl_alloc_node(context, level++); +=09prev =3D root; =20 -=09if (lo[size - 1] =3D=3D hi[size - 1]) { -=09=09acl_gen_range(context, hi, lo, size, level, root, *pend); -=09} else { -=09=09uint8_t limit_lo[64]; -=09=09uint8_t limit_hi[64]; -=09=09uint8_t hi_ff =3D UINT8_MAX; -=09=09uint8_t lo_00 =3D 0; +=09/* build common sub-trie till possible */ +=09for (n =3D size - 1; n > 0 && lo[n] =3D=3D hi[n]; n--) { +=09=09node =3D acl_alloc_node(context, level++); +=09=09acl_add_ptr_range(context, prev, node, lo[n], hi[n]); +=09=09prev =3D node; +=09} =20 -=09=09memset(limit_lo, 0, RTE_DIM(limit_lo)); -=09=09memset(limit_hi, UINT8_MAX, RTE_DIM(limit_hi)); +=09/* no branch needed, just one sub-trie */ +=09if (n =3D=3D 0) { +=09=09acl_add_ptr_range(context, prev, *pend, lo[0], hi[0]); +=09=09return root; +=09} =20 -=09=09for (n =3D size - 2; n >=3D 0; n--) { -=09=09=09hi_ff =3D (uint8_t)(hi_ff & hi[n]); -=09=09=09lo_00 =3D (uint8_t)(lo_00 | lo[n]); -=09=09} +=09/* gather information about divirgent paths */ +=09lo_00 =3D 0; +=09hi_ff =3D UINT8_MAX; +=09for (k =3D n - 1; k >=3D 0; k--) { +=09=09hi_ff &=3D hi[k]; +=09=09lo_00 |=3D lo[k]; +=09} =20 -=09=09if (hi_ff !=3D UINT8_MAX) { -=09=09=09limit_lo[size - 1] =3D hi[size - 1]; -=09=09=09acl_gen_range(context, hi, limit_lo, size, level, -=09=09=09=09root, *pend); -=09=09} +=09/* generate left (lower-bound) sub-trie */ +=09if (lo_00 !=3D 0) +=09=09acl_gen_range_low(context, prev, *pend, lo, n + 1, level); =20 -=09=09if (lo_00 !=3D 0) { -=09=09=09limit_hi[size - 1] =3D lo[size - 1]; -=09=09=09acl_gen_range(context, limit_hi, lo, size, level, -=09=09=09=09root, *pend); -=09=09} +=09/* generate right (upper-bound) sub-trie */ +=09if (hi_ff !=3D UINT8_MAX) +=09=09acl_gen_range_high(context, prev, *pend, hi, n + 1, level); =20 -=09=09if (hi[size - 1] - lo[size - 1] > 1 || -=09=09=09=09lo_00 =3D=3D 0 || -=09=09=09=09hi_ff =3D=3D UINT8_MAX) { -=09=09=09limit_lo[size-1] =3D (uint8_t)(lo[size-1] + (lo_00 !=3D 0)); -=09=09=09limit_hi[size-1] =3D (uint8_t)(hi[size-1] - -=09=09=09=09(hi_ff !=3D UINT8_MAX)); -=09=09=09acl_gen_range(context, limit_hi, limit_lo, size, -=09=09=09=09level, root, *pend); -=09=09} +=09/* generate sub-trie in the middle */ +=09if (lo[n] + 1 !=3D hi[n] || lo_00 =3D=3D 0 || hi_ff =3D=3D UINT8_MAX) { +=09=09lo_00 =3D lo[n] + (lo_00 !=3D 0); +=09=09hi_ff =3D hi[n] - (hi_ff !=3D UINT8_MAX); +=09=09acl_gen_range_mdl(context, prev, *pend, lo_00, hi_ff, +=09=09=09n + 1, level); =09} + =09return root; } --=20 2.21.1 --- Diff of the applied patch vs upstream commit (please double-check if non-= empty: --- --- -=092020-02-19 15:43:49.810782365 +0000 +++ 0001-acl-fix-32-bit-match-for-range-field.patch=092020-02-19 15:43:49.7= 13142357 +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