From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 1E7B7455AD for ; Mon, 15 Jul 2024 17:28:38 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 18C7440A75; Mon, 15 Jul 2024 17:28:38 +0200 (CEST) Received: from mail-lj1-f174.google.com (mail-lj1-f174.google.com [209.85.208.174]) by mails.dpdk.org (Postfix) with ESMTP id 83CB640B9B for ; Mon, 15 Jul 2024 17:28:36 +0200 (CEST) Received: by mail-lj1-f174.google.com with SMTP id 38308e7fff4ca-2eede876fbfso26185301fa.1 for ; Mon, 15 Jul 2024 08:28:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721057316; x=1721662116; darn=dpdk.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=mZIvdfNlIAzE4q635QSOsWbl1IErFCmUaLpi+UecKas=; b=esRRoeGR22oZG7HcRQuIeZijVxf/fMLrN8e6jNKUCLPU/sEAsNKPL5+Zz49kSfK1Qd jlDmy09Wj5plzpriV71i0maLyzwi3AJ7Bj+szmP1vDwcx4CbXO/Jp2Zu4BcKhVWttqGY b+B/5I2+LhHgfUX2yWzYuox5eiid/zvmkMi+qfH5F9m61KLoz5InW2TIeOquBUsWawfC A6wUEhCQUtIHym2Kb7htQy7VSBQr5hcnJjxLi33LgyuGyQEe0yVBuCk1fuKHFoEyMU87 vvVocVmRQ5nt7M2dFMMD0ogjx5F7ramsNaZ3vIRQL8PuZ+HgZ40RwOmxBIYwZpthU1nK IB0Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721057316; x=1721662116; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=mZIvdfNlIAzE4q635QSOsWbl1IErFCmUaLpi+UecKas=; b=EayhEQ59Mde80r+7xTdJMR1d/5Nd3cJrnsceOTGgBkyIcJw94Q7TvlQxb2JgSin4uB AV1oRHqB6JSSXTe2bg/Wb7md0NUaktOqvpjoOwdSQh9xomnvPmItZ6AIxr3hyuOxxaCP JhIzbGbA9yIYlKux63cNCj9w2znAwrWvGjbzfJS1Q/+Qyl7WXGyROuJtWx3BD7zYoyPM 1qqq3gNbikR2VwG1MJbDM4OpaLBLxAxfrYHwKDb7q3Q2PKFnH4lA7yNOZLIX8p5cFRAG 9B4/Ku7Id2kpoUMK8q+tPBzKnPSgpEgeI99aEL3+0BaR7c2oe4yt0JZrSDdjRvbpxZc0 sh+g== X-Forwarded-Encrypted: i=1; AJvYcCUIuY84zPEOVswdxe+SOiOD/70s6PKKV1S82eTsDcRtpiUrCyupvbLNHE4ktWaoCFaIgtVJ+nsHTvNMdQNuzCo= X-Gm-Message-State: AOJu0Yz3DKTC01+UIMBegod0O3bkJaqVthC3XbkxZuYznPVwx3rj9X7X zfJ0RX7vN29zXkeeqVIzDtLvqt8CJaRomf28738qJPQ/1eU/E/1g X-Google-Smtp-Source: AGHT+IE5kTu4s+lp4cmGflqSdpLl20jJ2Hgw5xppeJryL26LBTUKlNt6RcmO8IvtEc9rx7/kRAObQA== X-Received: by 2002:a2e:3c16:0:b0:2ee:4c2e:3d35 with SMTP id 38308e7fff4ca-2eef2d9157emr1399821fa.23.1721057315858; Mon, 15 Jul 2024 08:28:35 -0700 (PDT) Received: from localhost ([137.220.120.171]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-3680dab3bd8sm6722104f8f.13.2024.07.15.08.28.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 15 Jul 2024 08:28:35 -0700 (PDT) From: luca.boccassi@gmail.com To: Anatoly Burakov Cc: Vipin Padmam Ramesh , dpdk stable Subject: patch 'fbarray: fix lookahead ignore mask handling' has been queued to stable release 22.11.6 Date: Mon, 15 Jul 2024 16:26:07 +0100 Message-Id: <20240715152704.2229503-29-luca.boccassi@gmail.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240715152704.2229503-1-luca.boccassi@gmail.com> References: <20240624235907.885628-81-luca.boccassi@gmail.com> <20240715152704.2229503-1-luca.boccassi@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-BeenThere: stable@dpdk.org X-Mailman-Version: 2.1.29 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 Hi, FYI, your patch has been queued to stable release 22.11.6 Note it hasn't been pushed to http://dpdk.org/browse/dpdk-stable yet. It will be pushed if I get no objections before 07/17/24. 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/bluca/dpdk-stable This queued commit can be viewed at: https://github.com/bluca/dpdk-stable/commit/2050d2ea0146e2ffd93742eb9105e039e5f6eb1e Thanks. Luca Boccassi --- >From 2050d2ea0146e2ffd93742eb9105e039e5f6eb1e Mon Sep 17 00:00:00 2001 From: Anatoly Burakov Date: Mon, 8 Jul 2024 17:07:34 +0100 Subject: [PATCH] fbarray: fix lookahead ignore mask handling [ upstream commit a344719c181aac28cb2ada0d2ddbfee8ad737a1a ] 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") Signed-off-by: Vipin Padmam Ramesh 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 f448d4f196..38a62cd456 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 374103dc15..1909615187 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; -- 2.39.2 --- Diff of the applied patch vs upstream commit (please double-check if non-empty: --- --- - 2024-07-15 16:19:36.189873104 +0100 +++ 0029-fbarray-fix-lookahead-ignore-mask-handling.patch 2024-07-15 16:19:34.524205524 +0100 @@ -1 +1 @@ -From a344719c181aac28cb2ada0d2ddbfee8ad737a1a Mon Sep 17 00:00:00 2001 +From 2050d2ea0146e2ffd93742eb9105e039e5f6eb1e Mon Sep 17 00:00:00 2001 @@ -5,0 +6,2 @@ +[ upstream commit a344719c181aac28cb2ada0d2ddbfee8ad737a1a ] + @@ -19 +20,0 @@ -Cc: stable@dpdk.org @@ -29 +30 @@ -index 147d6e2a07..4b17ef6be3 100644 +index f448d4f196..38a62cd456 100644 @@ -75 +76 @@ -index b4f0b0b0c3..195f8394be 100644 +index 374103dc15..1909615187 100644