From patchwork Mon Jul 8 16:07:32 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anatoly Burakov X-Patchwork-Id: 142219 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 7F7D745556; Mon, 8 Jul 2024 18:07:46 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id C41CF4275A; Mon, 8 Jul 2024 18:07:43 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.13]) by mails.dpdk.org (Postfix) with ESMTP id DE12740265; Mon, 8 Jul 2024 18:07:40 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1720454861; x=1751990861; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=kw3njbAWkTPQYFMcXwbYh/eSmEl1Lz6GLmYa9xT//mc=; b=A/ob4PcM8wC0R35De+0AlgZYKc3NWv3vaKSrTMYw7tTEhmPbjbeFWEEH v0aRFLYuftfdCjXk3o3i727lovEFeq61zmDYP98ZfCkeXii8ilgTxQuy/ v0WQ/4ZmWbb59p8QfcCuJ5qqbNC5jiK+aVXX7zDYKJHdPzY+nWIrzaExD pQRYbmJpqdrcVbqwOx/pLKzDDOGPtiYDfq6lP6sFzs1bM0m3bIGNgKkt/ CMCglrHFcKzntRpUR6kHDX5Yo3VcaNUkqoWG6VVyyKYfKr7e19Hec9zGO m3EZ1Q7i9flHpUAcNS6o9hOFqTPYwHNoK2U6IB9+FdkTSEUaumv+vbs6r w==; X-CSE-ConnectionGUID: 07Y4RM+6RZyKbydcgnHRyA== X-CSE-MsgGUID: OR/vC9h5SEG4P8r6YXBQsA== X-IronPort-AV: E=McAfee;i="6700,10204,11127"; a="28827520" X-IronPort-AV: E=Sophos;i="6.09,192,1716274800"; d="scan'208";a="28827520" Received: from fmviesa005.fm.intel.com ([10.60.135.145]) by orvoesa105.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 Jul 2024 09:07:40 -0700 X-CSE-ConnectionGUID: GObcjcjLRf+h5JytvUMCWw== X-CSE-MsgGUID: bjS4vLgYQKO0AVM795SCxw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.09,192,1716274800"; d="scan'208";a="51965477" Received: from silpixa00401119.ir.intel.com ([10.55.129.167]) by fmviesa005.fm.intel.com with ESMTP; 08 Jul 2024 09:07:39 -0700 From: Anatoly Burakov To: dev@dpdk.org, Tyler Retzlaff Cc: stable@dpdk.org Subject: [PATCH v1 1/4] fbarray: fix incorrect lookahead behavior Date: Mon, 8 Jul 2024 17:07:32 +0100 Message-ID: <62d5744a70ba1cde7d1dcf5311fdbc24d317b695.1720454625.git.anatoly.burakov@intel.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: References: MIME-Version: 1.0 X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Currently, whenever last bit of current index mask is set (meaning, there is potentially a run starting at the end of the mask), lookahead loop is entered. In that loop, if the first bit of lookahead mask is not set, the lookahead is stopped, and the current lookahead mask index is assigned to current index mask. However, because at that point we are inside a for-loop that increments current index mask after each iteration, this results in erroneous mask index increment. Fixlookahead to avoid erroneous increment, and add corresponding unit test. Fixes: c44d09811b40 ("eal: add shared indexed file-backed array") Cc: stable@dpdk.org Signed-off-by: Vipin P R Signed-off-by: Anatoly Burakov --- app/test/test_fbarray.c | 23 +++++++++++++++++++++++ lib/eal/common/eal_common_fbarray.c | 3 ++- 2 files changed, 25 insertions(+), 1 deletion(-) diff --git a/app/test/test_fbarray.c b/app/test/test_fbarray.c index 26a51e2a3e..bf89b99e5b 100644 --- a/app/test/test_fbarray.c +++ b/app/test/test_fbarray.c @@ -103,6 +103,14 @@ static int empty_msk_test_setup(void) return 0; } +static int lookahead_test_setup(void) +{ + /* set index 64 as used */ + param.start = 64; + param.end = 64; + return init_array(); +} + static int test_invalid(void) { struct rte_fbarray dummy; @@ -709,6 +717,20 @@ static int test_empty(void) return TEST_SUCCESS; } +static int test_lookahead(void) +{ + int ret; + + /* run regular test first */ + ret = test_find(); + if (ret != TEST_SUCCESS) + return ret; + + /* test if we can find free chunk while not starting with 0 */ + TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_free(¶m.arr, 1, param.start), + param.start + 1, "Free chunk index is wrong\n"); + return TEST_SUCCESS; +} static struct unit_test_suite fbarray_test_suite = { .suite_name = "fbarray autotest", @@ -723,6 +745,7 @@ static struct unit_test_suite fbarray_test_suite = { TEST_CASE_ST(last_msk_test_setup, reset_array, test_find), TEST_CASE_ST(full_msk_test_setup, reset_array, test_find), TEST_CASE_ST(empty_msk_test_setup, reset_array, test_empty), + TEST_CASE_ST(lookahead_test_setup, reset_array, test_lookahead), TEST_CASES_END() } }; diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c index 0fe5bcfe06..2680b34823 100644 --- a/lib/eal/common/eal_common_fbarray.c +++ b/lib/eal/common/eal_common_fbarray.c @@ -236,7 +236,8 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, * as well, so skip that on next iteration. */ ignore_msk = ~((1ULL << need) - 1); - msk_idx = lookahead_idx; + /* outer loop will increment msk_idx so add 1 */ + msk_idx = lookahead_idx - 1; break; } From patchwork Mon Jul 8 16:07:33 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anatoly Burakov X-Patchwork-Id: 142220 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 39B80455C2; Mon, 8 Jul 2024 18:07:54 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 4E2A042794; Mon, 8 Jul 2024 18:07:45 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.13]) by mails.dpdk.org (Postfix) with ESMTP id A61564029E; Mon, 8 Jul 2024 18:07:41 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1720454862; x=1751990862; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=5hS4KqDK+7kIBoPImh/vCX5QRQbVDsMty5aH7UTcNpQ=; b=AY06IZIo0ed3et1a8N+tNjvICFlXP2vtDXQGqBN2/Z75x/8warA7QEOP buB/7UZSBN3ESuHmBlDamgFqnKEDDVoISy4L/sqyk+p7PpjJEhkpLT6Cu KKwZU8UrNVrOPvpnZautwtn7fjL7SyeU3a4WhGTC/IdUDSyHpCJkk8QJx ZarGvZxbDDesLz+WsdpsvGkVKaZp43HjW2XvrdbLcpCW+uXA4Up0PoRop MBgA/oHHpczawNZ+EjVE3bsWpI9pDJmP7o1qc9m6gd8ocFG8We+bbU3Af K+k/x0e+x4rwPr/9H5arn7l+84YjN7BoutqJemjLxFLkl3/Dxd09Xee3x w==; X-CSE-ConnectionGUID: AVuabdnvSyidsut75x4EgQ== X-CSE-MsgGUID: APbKA6gPQKanpp8Qlhw1EQ== X-IronPort-AV: E=McAfee;i="6700,10204,11127"; a="28827524" X-IronPort-AV: E=Sophos;i="6.09,192,1716274800"; d="scan'208";a="28827524" Received: from fmviesa005.fm.intel.com ([10.60.135.145]) by orvoesa105.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 Jul 2024 09:07:41 -0700 X-CSE-ConnectionGUID: ecuRvVpUTiyCnetKwlb74g== X-CSE-MsgGUID: T2dI1ItgSb62Q6NPio71PQ== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.09,192,1716274800"; d="scan'208";a="51965481" Received: from silpixa00401119.ir.intel.com ([10.55.129.167]) by fmviesa005.fm.intel.com with ESMTP; 08 Jul 2024 09:07:40 -0700 From: Anatoly Burakov To: dev@dpdk.org, Tyler Retzlaff Cc: stable@dpdk.org Subject: [PATCH v1 2/4] fbarray: fix incorrect lookbehind behavior Date: Mon, 8 Jul 2024 17:07:33 +0100 Message-ID: X-Mailer: git-send-email 2.43.0 In-Reply-To: References: MIME-Version: 1.0 X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Currently, whenever first bit of current index mask is set (meaning, there is potentially a run starting at the start of the mask), lookbehind loop is entered. In that loop, if the last bit of lookbehind mask is not set, the lookbehind is stopped, and the current lookbehind mask index is assigned to current index mask. However, because at that point we are inside a while-loop that decrements current index mask after each iteration, this results in erroneous mask index decrement. Fix lookbehind to avoid erroneous decrement, and add corresponding unit test. Fixes: e1ca5dc86226 ("fbarray: add reverse finding of chunk") Cc: stable@dpdk.org Signed-off-by: Vipin P R Signed-off-by: Anatoly Burakov --- app/test/test_fbarray.c | 24 ++++++++++++++++++++++++ lib/eal/common/eal_common_fbarray.c | 3 ++- 2 files changed, 26 insertions(+), 1 deletion(-) diff --git a/app/test/test_fbarray.c b/app/test/test_fbarray.c index bf89b99e5b..147d6e2a07 100644 --- a/app/test/test_fbarray.c +++ b/app/test/test_fbarray.c @@ -111,6 +111,14 @@ static int lookahead_test_setup(void) return init_array(); } +static int lookbehind_test_setup(void) +{ + /* set index 63 as used */ + param.start = 63; + param.end = 63; + return init_array(); +} + static int test_invalid(void) { struct rte_fbarray dummy; @@ -732,6 +740,21 @@ static int test_lookahead(void) return TEST_SUCCESS; } +static int test_lookbehind(void) +{ + int ret, free_len = 2; + + /* run regular test first */ + ret = test_find(); + if (ret != TEST_SUCCESS) + return ret; + + /* test if we can find free chunk while crossing mask boundary */ + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_free(¶m.arr, param.start + 1, free_len), + param.start - free_len, "Free chunk index is wrong\n"); + return TEST_SUCCESS; +} + static struct unit_test_suite fbarray_test_suite = { .suite_name = "fbarray autotest", .setup = autotest_setup, @@ -746,6 +769,7 @@ static struct unit_test_suite fbarray_test_suite = { TEST_CASE_ST(full_msk_test_setup, reset_array, test_find), TEST_CASE_ST(empty_msk_test_setup, reset_array, test_empty), TEST_CASE_ST(lookahead_test_setup, reset_array, test_lookahead), + TEST_CASE_ST(lookbehind_test_setup, reset_array, test_lookbehind), TEST_CASES_END() } }; diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c index 2680b34823..b4f0b0b0c3 100644 --- a/lib/eal/common/eal_common_fbarray.c +++ b/lib/eal/common/eal_common_fbarray.c @@ -512,7 +512,8 @@ find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, * as well, so skip that on next iteration. */ ignore_msk = UINT64_MAX << need; - msk_idx = lookbehind_idx; + /* outer loop will decrement msk_idx so add 1 */ + msk_idx = lookbehind_idx + 1; break; } From patchwork Mon Jul 8 16:07:34 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anatoly Burakov X-Patchwork-Id: 142221 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id AC856455C2; Mon, 8 Jul 2024 18:08:00 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id A1D9842799; Mon, 8 Jul 2024 18:07:46 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.13]) by mails.dpdk.org (Postfix) with ESMTP id 5C98542708; Mon, 8 Jul 2024 18:07:43 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1720454863; x=1751990863; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=hluY7du+AkcVuR4aLtnNJCbYBlpXpZJwizBii6V2/q0=; b=f//he3EmnpzHCuVxRvXtQ9ZK6BJBh7Nr+1e6fR2Ywx2mg3gdPz1jOmjD LX25JDi6RkykFkbqC1rmpPyeLLpN6gvXsYbBltPjTV8WxPQPlpQc1+YvD 1WNBMhatFbXU2x5K/jTb6JmlC0QQ1D+p2tGcMierYQpgpdeeBBENfP3Eh kFs+xqarbOKQcWYOeBsXvL0e+6XAnqPJ/Zt62X+l7ZRlze+uVJjnwcJZV NToeJEGE499hrQ+xw/kJQwDdbWG8dIaYgntPxLDy91Sy6nwhQD6nNmNiU qJz/cHd2IBGWXjAr3R8eEZTblSGCLCFi7qDbNUXabcxnX82e6liQf4qL5 A==; X-CSE-ConnectionGUID: UKBqy/50TfaXdu4MOFZ9Ew== X-CSE-MsgGUID: cf2lGJQvQy69xpLwNrzIvA== X-IronPort-AV: E=McAfee;i="6700,10204,11127"; a="28827527" X-IronPort-AV: E=Sophos;i="6.09,192,1716274800"; d="scan'208";a="28827527" Received: from fmviesa005.fm.intel.com ([10.60.135.145]) by orvoesa105.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 Jul 2024 09:07:42 -0700 X-CSE-ConnectionGUID: +K7emqNCSq6IHDSW7zPYWg== X-CSE-MsgGUID: bhcWtIZ0Qf+vAqOhnNJdnA== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.09,192,1716274800"; d="scan'208";a="51965492" Received: from silpixa00401119.ir.intel.com ([10.55.129.167]) by fmviesa005.fm.intel.com with ESMTP; 08 Jul 2024 09:07:42 -0700 From: Anatoly Burakov To: dev@dpdk.org, Tyler Retzlaff Cc: stable@dpdk.org Subject: [PATCH v1 3/4] fbarray: fix lookahead ignore mask handling Date: Mon, 8 Jul 2024 17:07:34 +0100 Message-ID: X-Mailer: git-send-email 2.43.0 In-Reply-To: References: MIME-Version: 1.0 X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org When lookahead mask does not have its first bit set, we can infer that we've lost our run. However, currently, we set ignore mask to ignore `need` number of bits, which is incorrect because while there is no *current* run within those bits, we might still be able to start a new run within those ignored bits later. This issue is fixed by counting how many shifts it took to lose the run, and this is the number of bits we should ignore (+1 to skip one we stopped on). Also, add unit tests to reproduce the problem. Fixes: c44d09811b40 ("eal: add shared indexed file-backed array") Cc: stable@dpdk.org Signed-off-by: Vipin P R Signed-off-by: Anatoly Burakov --- app/test/test_fbarray.c | 28 ++++++++++++++++++++++++++++ lib/eal/common/eal_common_fbarray.c | 13 ++++++++++--- 2 files changed, 38 insertions(+), 3 deletions(-) diff --git a/app/test/test_fbarray.c b/app/test/test_fbarray.c index 147d6e2a07..4b17ef6be3 100644 --- a/app/test/test_fbarray.c +++ b/app/test/test_fbarray.c @@ -755,6 +755,32 @@ static int test_lookbehind(void) return TEST_SUCCESS; } +static int test_lookahead_mask(void) +{ + /* + * There is a certain type of lookahead behavior we want to test here, + * namely masking of bits that were scanned with lookahead but that we + * know do not match our criteria. This is achieved in following steps: + * + * 0. Look for a big enough chunk of free space (say, 62 elements) + * 1. Trigger lookahead by breaking a run somewhere inside mask 0 + * (indices 0-63) + * 2. Fail lookahead by breaking the run somewhere inside mask 1 + * (indices 64-127) + * 3. Ensure that we can still find free space in mask 1 afterwards + */ + + /* break run on first mask */ + rte_fbarray_set_used(¶m.arr, 61); + /* break run on second mask */ + rte_fbarray_set_used(¶m.arr, 70); + + /* we expect to find free space at 71 */ + TEST_ASSERT_EQUAL(rte_fbarray_find_next_n_free(¶m.arr, 0, 62), + 71, "Free chunk index is wrong\n"); + return TEST_SUCCESS; +} + static struct unit_test_suite fbarray_test_suite = { .suite_name = "fbarray autotest", .setup = autotest_setup, @@ -770,6 +796,8 @@ static struct unit_test_suite fbarray_test_suite = { TEST_CASE_ST(empty_msk_test_setup, reset_array, test_empty), TEST_CASE_ST(lookahead_test_setup, reset_array, test_lookahead), TEST_CASE_ST(lookbehind_test_setup, reset_array, test_lookbehind), + /* setup for these tests is more complex so do it in test func */ + TEST_CASE_ST(NULL, reset_array, test_lookahead_mask), TEST_CASES_END() } }; diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c index b4f0b0b0c3..195f8394be 100644 --- a/lib/eal/common/eal_common_fbarray.c +++ b/lib/eal/common/eal_common_fbarray.c @@ -216,6 +216,8 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, for (lookahead_idx = msk_idx + 1; lookahead_idx < msk->n_masks; lookahead_idx++) { unsigned int s_idx, need; + uint64_t first_bit = 1; + lookahead_msk = msk->data[lookahead_idx]; /* if we're looking for free space, invert the mask */ @@ -225,17 +227,22 @@ find_next_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, /* figure out how many consecutive bits we need here */ need = RTE_MIN(left, MASK_ALIGN); - for (s_idx = 0; s_idx < need - 1; s_idx++) + /* count number of shifts we performed */ + for (s_idx = 0; s_idx < need - 1; s_idx++) { lookahead_msk &= lookahead_msk >> 1ULL; + /* did we lose the run yet? */ + if ((lookahead_msk & first_bit) == 0) + break; + } /* if first bit is not set, we've lost the run */ - if ((lookahead_msk & 1) == 0) { + if ((lookahead_msk & first_bit) == 0) { /* * we've scanned this far, so we know there are * no runs in the space we've lookahead-scanned * as well, so skip that on next iteration. */ - ignore_msk = ~((1ULL << need) - 1); + ignore_msk = ~((1ULL << (s_idx + 1)) - 1); /* outer loop will increment msk_idx so add 1 */ msk_idx = lookahead_idx - 1; break; From patchwork Mon Jul 8 16:07:35 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Anatoly Burakov X-Patchwork-Id: 142222 X-Patchwork-Delegate: david.marchand@redhat.com Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id C7466455C2; Mon, 8 Jul 2024 18:08:06 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id D39E54279D; Mon, 8 Jul 2024 18:07:47 +0200 (CEST) Received: from mgamail.intel.com (mgamail.intel.com [198.175.65.13]) by mails.dpdk.org (Postfix) with ESMTP id 282A940265; Mon, 8 Jul 2024 18:07:44 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=intel.com; i=@intel.com; q=dns/txt; s=Intel; t=1720454864; x=1751990864; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=S8aDKkJ8Tg2q+fmE3Nd4P/v5hjDk9Os6VYoiB6R3d/0=; b=dZOFT661mv+Jsy1siG6xHF9L6L5wn6Obay6diZMA6qolNuJzxch4j2ZV ddEwDAXHBUo+jdvv9UIGK+3rMFo6JId094hJpA8uIYgLhxFrZ1noaXxPB d12lf1ZXcjUP5FG5tgc5lpjDPmb7vuNTHdnBP2hDacQQQOmUk4zQ/n50B CqnXoV9uBi9sG9NigUH2ucNWbVekmXoIZrvdDQsn2DEW5QDZmTrHPhDg1 s9N9zNmzhb4WFvzEISiryKWs13yU0cXeH5ItNC6Xid5/qXeWHN89dJCUy 9x0dEFJmd8WCtoNECb0Df39bZBu1z788KKBLbo4WsGbMMG+a01C2vKwUH Q==; X-CSE-ConnectionGUID: e0GTETTZQcSzmxctrinDqw== X-CSE-MsgGUID: uaZpk89YRTqO7Wya/8fH/w== X-IronPort-AV: E=McAfee;i="6700,10204,11127"; a="28827532" X-IronPort-AV: E=Sophos;i="6.09,192,1716274800"; d="scan'208";a="28827532" Received: from fmviesa005.fm.intel.com ([10.60.135.145]) by orvoesa105.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 08 Jul 2024 09:07:43 -0700 X-CSE-ConnectionGUID: uGBVzpoYTwSFuYtbYalIpA== X-CSE-MsgGUID: pHLsUoitQqufxc0mwL4YHw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="6.09,192,1716274800"; d="scan'208";a="51965493" Received: from silpixa00401119.ir.intel.com ([10.55.129.167]) by fmviesa005.fm.intel.com with ESMTP; 08 Jul 2024 09:07:43 -0700 From: Anatoly Burakov To: dev@dpdk.org, Tyler Retzlaff Cc: stable@dpdk.org Subject: [PATCH v1 4/4] fbarray: fix lookbehind ignore mask handling Date: Mon, 8 Jul 2024 17:07:35 +0100 Message-ID: <0dab28b7989826db35da275ba18c3a5c7473f46f.1720454625.git.anatoly.burakov@intel.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: References: MIME-Version: 1.0 X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org When lookahead mask does not have its last bit set, we can infer that we've lost our run. However, currently, we set ignore mask to ignore first `need` bits, which is incorrect for two reasons: first, using `need` bits as ignore bit count means we might miss opportunities to start a new run within those bits, and more improtantly when doing lookbehind, we start looking from the top, so we should be ignoring *last* N bits, not *first* N bits of the mask. This issue is fixed by counting how many shifts it took to lose the run, and this is the number of bits we should ignore from the top (+1 to skip one we stopped on). Also, add unit tests to reproduce the problem. Fixes: e1ca5dc86226 ("fbarray: add reverse finding of chunk") Cc: stable@dpdk.org Signed-off-by: Vipin P R Signed-off-by: Anatoly Burakov --- app/test/test_fbarray.c | 27 +++++++++++++++++++++++++++ lib/eal/common/eal_common_fbarray.c | 9 +++++++-- 2 files changed, 34 insertions(+), 2 deletions(-) diff --git a/app/test/test_fbarray.c b/app/test/test_fbarray.c index 4b17ef6be3..13c6691e50 100644 --- a/app/test/test_fbarray.c +++ b/app/test/test_fbarray.c @@ -781,6 +781,32 @@ static int test_lookahead_mask(void) return TEST_SUCCESS; } +static int test_lookbehind_mask(void) +{ + /* + * There is a certain type of lookbehind behavior we want to test here, + * namely masking of bits that were scanned with lookbehind but that we + * know do not match our criteria. This is achieved in two steps: + * + * 0. Look for a big enough chunk of free space (say, 62 elements) + * 1. Trigger lookbehind by breaking a run somewhere inside mask 2 + * (indices 128-191) + * 2. Fail lookbehind by breaking the run somewhere inside mask 1 + * (indices 64-127) + * 3. Ensure that we can still find free space in mask 1 afterwards + */ + + /* break run on mask 2 */ + rte_fbarray_set_used(¶m.arr, 130); + /* break run on mask 1 */ + rte_fbarray_set_used(¶m.arr, 70); + + /* start from 190, we expect to find free space at 8 */ + TEST_ASSERT_EQUAL(rte_fbarray_find_prev_n_free(¶m.arr, 190, 62), + 8, "Free chunk index is wrong\n"); + return TEST_SUCCESS; +} + static struct unit_test_suite fbarray_test_suite = { .suite_name = "fbarray autotest", .setup = autotest_setup, @@ -798,6 +824,7 @@ static struct unit_test_suite fbarray_test_suite = { TEST_CASE_ST(lookbehind_test_setup, reset_array, test_lookbehind), /* setup for these tests is more complex so do it in test func */ TEST_CASE_ST(NULL, reset_array, test_lookahead_mask), + TEST_CASE_ST(NULL, reset_array, test_lookbehind_mask), TEST_CASES_END() } }; diff --git a/lib/eal/common/eal_common_fbarray.c b/lib/eal/common/eal_common_fbarray.c index 195f8394be..63d8b731f5 100644 --- a/lib/eal/common/eal_common_fbarray.c +++ b/lib/eal/common/eal_common_fbarray.c @@ -508,8 +508,13 @@ find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, /* figure out how many consecutive bits we need here */ need = RTE_MIN(left, MASK_ALIGN); - for (s_idx = 0; s_idx < need - 1; s_idx++) + /* count number of shifts we performed */ + for (s_idx = 0; s_idx < need - 1; s_idx++) { lookbehind_msk &= lookbehind_msk << 1ULL; + /* did we lose the run yet? */ + if ((lookbehind_msk & last_bit) == 0) + break; + } /* if last bit is not set, we've lost the run */ if ((lookbehind_msk & last_bit) == 0) { @@ -518,7 +523,7 @@ find_prev_n(const struct rte_fbarray *arr, unsigned int start, unsigned int n, * no runs in the space we've lookbehind-scanned * as well, so skip that on next iteration. */ - ignore_msk = UINT64_MAX << need; + ignore_msk = ~(UINT64_MAX << (MASK_ALIGN - s_idx - 1)); /* outer loop will decrement msk_idx so add 1 */ msk_idx = lookbehind_idx + 1; break;