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 D0D5FA0534; Wed, 12 Feb 2020 14:48:00 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id CE3402BE9; Wed, 12 Feb 2020 14:47:55 +0100 (CET) Received: from mga05.intel.com (mga05.intel.com [192.55.52.43]) by dpdk.org (Postfix) with ESMTP id B9425137D; Wed, 12 Feb 2020 14:47:53 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga002.jf.intel.com ([10.7.209.21]) by fmsmga105.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 12 Feb 2020 05:47:53 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.70,433,1574150400"; d="scan'208";a="251914319" Received: from sivswdev08.ir.intel.com ([10.237.217.47]) by orsmga002.jf.intel.com with ESMTP; 12 Feb 2020 05:47:51 -0800 From: Konstantin Ananyev To: dev@dpdk.org Cc: Ido@cgstowernetworks.com, Konstantin Ananyev , stable@dpdk.org Date: Wed, 12 Feb 2020 13:47:44 +0000 Message-Id: <20200212134745.5723-2-konstantin.ananyev@intel.com> X-Mailer: git-send-email 2.18.0 In-Reply-To: <20200212134745.5723-1-konstantin.ananyev@intel.com> References: <20200212134745.5723-1-konstantin.ananyev@intel.com> Subject: [dpdk-dev] [PATCH 1/2] acl: fix 32-bit range field doesn't work properly X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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 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 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