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 C782DA0553 for ; Mon, 17 Feb 2020 18:45:52 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 89EF91DA12; Mon, 17 Feb 2020 18:45:52 +0100 (CET) Received: from mail-wr1-f42.google.com (mail-wr1-f42.google.com [209.85.221.42]) by dpdk.org (Postfix) with ESMTP id 7576C1DA12 for ; Mon, 17 Feb 2020 18:45:51 +0100 (CET) Received: by mail-wr1-f42.google.com with SMTP id w15so20794432wru.4 for ; Mon, 17 Feb 2020 09:45:51 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=nHZtWPPN0LhhwBi5WhYpAq7SpGtWTSu76ZntnF0aFGw=; b=ASfnHr6jsDkI4bIexIlbZR4MrvmDys6nNT2D0j4eF3QHUhwk2F4XZRDyZp/MP/zqL+ Zi/lThzMuzf0FlO5MF/6ZmzRffwOSi1FpaCwh1RVr7Fl+I4RNqMohuxPTI4YOvjaXN4k vtmMQsLk+dilzrRUSD18+C0pWbC9MGOsm4pb3TSf66B27FcVff/xDIHWl0XGEkqueDNW 28DQiT7RS0IzEdAq3eDz223HCByBM+nDB8uuiMx2/vXPfmuF2Uf6t2FaroeytggJbAww QA5cls6EJX0zzpkEjTUx8/8CHQ6ImUmkfSLdsR/Be5LuvftOObFI/YgKu58V1KoVwHBS 8/bw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=nHZtWPPN0LhhwBi5WhYpAq7SpGtWTSu76ZntnF0aFGw=; b=QjzM/eAvY26Sob63I+YXrZ/5Ug4Wp+G6JgwZbGvH6jCkbCsy9E/oTrTmZ4bjZijIbh vrWMtc3saoTrMgCRiZ9+53mSrQFFrirIMzPtZC8SLHQkVLEv9wVkOfJVkEK5On3wW6u/ uoJZ9X3svJ4jtdRKr1AjBP83ds0jjFcxY9PjK189zGycOoTaBh5LjUxwv+2hmY9g2JBm Q4MdKU3Cm1olckWDpqRgMTJbG8Yb1X+7D//JGIA1xz8IIqCMAV3NUDYFa0j4bA9EhXiq NBp4xr3H/RT+Agnmcs8uHnYCRQull6goPxZPNri4EdRzKLhrFvTaECFEs4NL7nPH9lLx f5Sw== X-Gm-Message-State: APjAAAVyvVlFkuOmmKOCIqSh2TFBO9kc+kkgKQ/6O1/fpY01UEI37xIc We03d8mxFO7Hfdl9HdDuu8Y= X-Google-Smtp-Source: APXvYqyD2nn0730QguGM1NNaAAcA7LQV3WM1wH2Wbl8an+3b4SClEbUqtz/Jtryf10zxR2M47uKK3g== X-Received: by 2002:a5d:5452:: with SMTP id w18mr22259243wrv.333.1581961551039; Mon, 17 Feb 2020 09:45:51 -0800 (PST) Received: from localhost (userh634.uk.uudial.com. [194.69.103.7]) by smtp.gmail.com with ESMTPSA id z6sm2021908wrw.36.2020.02.17.09.45.50 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 17 Feb 2020 09:45:50 -0800 (PST) From: luca.boccassi@gmail.com To: Konstantin Ananyev Cc: Ido Goshen , dpdk stable Date: Mon, 17 Feb 2020 17:44:53 +0000 Message-Id: <20200217174546.25334-1-luca.boccassi@gmail.com> X-Mailer: git-send-email 2.20.1 In-Reply-To: <20200211112216.3929-190-luca.boccassi@gmail.com> References: <20200211112216.3929-190-luca.boccassi@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [dpdk-stable] patch 'acl: fix 32-bit match for range field' has been queued to stable release 19.11.1 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 stable release 19.11.1 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/19/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. Thanks. Luca Boccassi --- >From e0cdc3a98194320ad576a0b6516158ab3275ebdd 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=307 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 @@ -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; - *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.20.1 --- Diff of the applied patch vs upstream commit (please double-check if non-empty: --- --- - 2020-02-17 17:00:15.406309624 +0000 +++ 0001-acl-fix-32-bit-match-for-range-field.patch 2020-02-17 17:00:15.259949775 +0000 @@ -1,8 +1,10 @@ -From dbed2c9ef8d3e0c99d026c5bd401c9e2c3d0bdcd Mon Sep 17 00:00:00 2001 +From e0cdc3a98194320ad576a0b6516158ab3275ebdd 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: @@ -10,7 +12,6 @@ Bugzilla ID: 307 Fixes: dc276b5780c2 ("acl: new library") -Cc: stable@dpdk.org Reported-by: Ido Goshen Signed-off-by: Konstantin Ananyev