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 ECBF7457A1 for ; Mon, 12 Aug 2024 14:54:36 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id E64E540668; Mon, 12 Aug 2024 14:54:36 +0200 (CEST) Received: from NAM10-DM6-obe.outbound.protection.outlook.com (mail-dm6nam10on2070.outbound.protection.outlook.com [40.107.93.70]) by mails.dpdk.org (Postfix) with ESMTP id AE78940668 for ; Mon, 12 Aug 2024 14:54:35 +0200 (CEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector10001; d=microsoft.com; cv=none; b=rBWZAHeM1swZiJrQgWpZ2RXh0xhTsTuNSHJGWDr+ZWH/a/1EtiAglZiQV+jqtp1bHJo1TcFy5j4MgPJcuuckVErFGfpvpxvHtB67bNfqDEpQTR+C5jO4wW6CgwuJQk6kQFCPnyOOg2qSu8/KbGLZhrYEgxULLhUPv4uK2QIShHTX5dw0oEOEB4W9ghbkas466/TKvF1Co25InrnhsGj/AjI/+HGdergcAxAbvpd+Kuv0SC9C+uPZiKtNuer+1CJuotKApbWCfzWcoLaK8nfaFQkRCMJ1lCXP9XlNuCkc2LRRH3UO1IIjsGE8GwA+p/ZIunwHWlazq43I0NwharF1fw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector10001; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=Vcytr20d5WCZk20F6k62vAmpxhW5LQDj4NiAy1cu4DM=; b=n8x42u0Iw5x5bwCvGPHAIm9+94F4uWC84BUvQ0UffXdiXMjPlYrJr4SPYR5UygS35h2lfBwd/+3UEGYZfh9x19ak35OCQKu+PfkNY0dNx1z9xJdGJh7HHBrdJLgXyvAHrB77CwiyA/xOfFY96djxks5wXJLUPuOnw8SkLAv556jlyHrpDadbwbdIp+LCt347Rd+5mz48mLK+hSzJqERV64Pqu9y1BlRd+qpUfqczvdGLl2tTG/9MbZGvkUEOGSnYsdtN8Bf0inqX8y6FXEQbq1hjb+XETBo3WwyvhBm49MvoV3+S4MTD1r9tAJ5+Hvk0QBWP0JcCdQdM/HtKqSBYDA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 216.228.117.161) smtp.rcpttodomain=intel.com smtp.mailfrom=nvidia.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=nvidia.com; dkim=none (message not signed); arc=none (0) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=Nvidia.com; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Vcytr20d5WCZk20F6k62vAmpxhW5LQDj4NiAy1cu4DM=; b=FI9HCTwUjdMsCLdzzJTTpNjFGf7OM/6Wo7PgOktxuwAHGfISHGZOLFDmXn7vK8wK8zu03hvugntuVBMuVV5G4Yg0hdrDRlfjHuUy2BTbvUoKViQfT89pjxX5bhh/3DWoN1SLanRxZqVBLAfk0B8K32UlzqfbMAySG1+YLjIUujs1by3hqqU1mpecDLQjCnoKKMjByN0x5mhK2J0aMukDpN/ZeFdBFU5aJWozvpaPRWaImUGh4NqUPwMy2U2+oGiCBpIEjAWeS+T2V5v900eYh+KE9N5vWFQZDW9RREvy28WLcMYRANQgsvEHkFSRmgt8WZfS4/pJOMizYm9Ibm1A0w== Received: from SN7P220CA0028.NAMP220.PROD.OUTLOOK.COM (2603:10b6:806:123::33) by PH7PR12MB8426.namprd12.prod.outlook.com (2603:10b6:510:241::20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7849.22; Mon, 12 Aug 2024 12:54:33 +0000 Received: from SA2PEPF00003F67.namprd04.prod.outlook.com (2603:10b6:806:123:cafe::73) by SN7P220CA0028.outlook.office365.com (2603:10b6:806:123::33) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7849.19 via Frontend Transport; Mon, 12 Aug 2024 12:54:32 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 216.228.117.161) smtp.mailfrom=nvidia.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=nvidia.com; Received-SPF: Pass (protection.outlook.com: domain of nvidia.com designates 216.228.117.161 as permitted sender) receiver=protection.outlook.com; client-ip=216.228.117.161; helo=mail.nvidia.com; pr=C Received: from mail.nvidia.com (216.228.117.161) by SA2PEPF00003F67.mail.protection.outlook.com (10.167.248.42) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7849.8 via Frontend Transport; Mon, 12 Aug 2024 12:54:32 +0000 Received: from rnnvmail201.nvidia.com (10.129.68.8) by mail.nvidia.com (10.129.200.67) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1544.4; Mon, 12 Aug 2024 05:54:20 -0700 Received: from nvidia.com (10.126.230.35) by rnnvmail201.nvidia.com (10.129.68.8) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.2.1544.4; Mon, 12 Aug 2024 05:54:18 -0700 From: Xueming Li To: Anatoly Burakov CC: , Vipin Padmam Ramesh , "dpdk stable" Subject: patch 'fbarray: fix lookbehind ignore mask handling' has been queued to stable release 23.11.2 Date: Mon, 12 Aug 2024 20:48:34 +0800 Message-ID: <20240812125035.389667-38-xuemingl@nvidia.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240812125035.389667-1-xuemingl@nvidia.com> References: <20240712110153.309690-23-xuemingl@nvidia.com> <20240812125035.389667-1-xuemingl@nvidia.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain X-Originating-IP: [10.126.230.35] X-ClientProxiedBy: rnnvmail201.nvidia.com (10.129.68.8) To rnnvmail201.nvidia.com (10.129.68.8) X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SA2PEPF00003F67:EE_|PH7PR12MB8426:EE_ X-MS-Office365-Filtering-Correlation-Id: 67cfe6bb-f5b0-4447-be7c-08dcbacde98c X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; ARA:13230040|36860700013|1800799024|82310400026|376014; X-Microsoft-Antispam-Message-Info: =?us-ascii?Q?4INl3XBlXlOaDtu+iIKH+g1jgYSf+owz1WaPSpiM7dgMrocVNqTFD9w5nxVx?= =?us-ascii?Q?evwm6+hla6lnSm0IEY2xwuNx1WxpGKvBGJ0FcZr72A0RObnmVojAY747oRy5?= =?us-ascii?Q?Hmx+MZTiaTHjTGmH0Sc/huq6vxM9pxekzloeL1LplVn2+HbIkIEg5gf4CEAB?= =?us-ascii?Q?8CX728dE84uvDU+wehi4csXKmla+oMdBZny3ALqjEyDiT+z64ezQQkIM28qm?= =?us-ascii?Q?01vh1JI1EGM6Jjag9rILwnNUPxkrBGPkrx8qCRNo0dIGA+Wy/jGyDU6tbaEb?= =?us-ascii?Q?BJNtQwLEqIaxi184vtvvytxzWtDIYz+TI6JrxzuPnCbURtJNKGww6TsjXvvT?= =?us-ascii?Q?GphXJP4edljRsxepTHz71A1pcQNzj3gMvoeV/Rd6yLNC6tyW1qIP6aq6d49P?= =?us-ascii?Q?HeHq2cKfw49hPsJLMMExkmXYRaXRud+06DCNNXi+8frIXMbCUzQ6gsnljyTe?= =?us-ascii?Q?Fk+/LxATOhVDTk9JWasopMR34InSjrzgzOqVFIYtptjBBR6Xl5pjrmE86bCy?= =?us-ascii?Q?RqAWrN07XV65oNhD88mEzLk8ON9mzMhZ7cnPaAcfnbukhSvrH/FFwh8B96tE?= =?us-ascii?Q?fvPpGSyJLOsAhtONZA6pE4ijedPLzgE3QALU5RFu+9Tf57AZfBU8CdccN0Qb?= =?us-ascii?Q?gHrG8BnVpp2K8CqVAzcXbypOBUg/wRWHv0OV7gIUtt2KqPwybXhfNujSn/29?= =?us-ascii?Q?VXtx52Bf9tmfabHHSr8AAYrNFHOXgQMucyFYTi6gmKfmzbcJp7KHBv6zt3G3?= =?us-ascii?Q?B2qVhdErLGCu9p7FTI8HL2E1wLbvw8XXmqWDLn0BGETnL/U7CkjWGHCEdeFn?= =?us-ascii?Q?M0qhf+gyEFl0mBXyYK75i5IzyNOYW/NtNXtk2oAhfpgcqgxIvcoAFuPb5lPn?= =?us-ascii?Q?QxTx1bAbIxbYLaEuBFxK4s70JuH2uTm7lt4wQepLl6d5B0ACA633q8EbmxEd?= =?us-ascii?Q?DoNTw3qopF9APiewyTPvG4xyKJfryeZ15IKw35K5ZemA09CgITCToQv6N9Kf?= =?us-ascii?Q?ChBfnUuD+AMFr+n4QjVopT2NQLgmPiYy050gTAoe5ykpCbS9zW7dMnVVEeZ0?= =?us-ascii?Q?omKmCFwkoJ/DK4TykMH68hSKTZ5VcOZn3zrUTYeILLVsFxKAe9KPMzoGprLD?= =?us-ascii?Q?lgVv0/FtuxR5T9PFGzFCrRNi+YQyMSl1AkZKqVgp0jGQ1N9iQRbbZWMHMnMu?= =?us-ascii?Q?oDy709pkD6K9hQUyQvdQAKv8b0DCCo+MSJb6tftA/jswpO7pKUBK2wSn5OjV?= =?us-ascii?Q?F7s3vHeDoL25Zk/QE2NN7jGG26RHdwVJpVadCyUQPYXLF5ejMa0NNKQf7NKZ?= =?us-ascii?Q?kf7PWg0k4XwbJ0z0pyrbAIBaIuak7aLYDYKsv0Pucsb2BP7/xcIbEamJ1+h9?= =?us-ascii?Q?CQ2M8+B/kDmfm2hiKD+UWi+jRHuYYsn113xZiNpohQahX6+OKLth8A1nr9vp?= =?us-ascii?Q?yaN4hE09RW196lhYJscuZ5R4+Al2DLkS?= X-Forefront-Antispam-Report: CIP:216.228.117.161; CTRY:US; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:mail.nvidia.com; PTR:dc6edge2.nvidia.com; CAT:NONE; SFS:(13230040)(36860700013)(1800799024)(82310400026)(376014); DIR:OUT; SFP:1101; X-OriginatorOrg: Nvidia.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 12 Aug 2024 12:54:32.7894 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 67cfe6bb-f5b0-4447-be7c-08dcbacde98c X-MS-Exchange-CrossTenant-Id: 43083d15-7273-40c1-b7db-39efd9ccc17a X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=43083d15-7273-40c1-b7db-39efd9ccc17a; Ip=[216.228.117.161]; Helo=[mail.nvidia.com] X-MS-Exchange-CrossTenant-AuthSource: SA2PEPF00003F67.namprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH7PR12MB8426 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 23.11.2 Note it hasn't been pushed to http://dpdk.org/browse/dpdk-stable yet. It will be pushed if I get no objections before 08/14/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://git.dpdk.org/dpdk-stable/log/?h=23.11-staging This queued commit can be viewed at: https://git.dpdk.org/dpdk-stable/commit/?h=23.11-staging&id=997166395e73d419c33172abc09d8eb279bee09b Thanks. Xueming Li --- >From 997166395e73d419c33172abc09d8eb279bee09b Mon Sep 17 00:00:00 2001 From: Anatoly Burakov Date: Mon, 8 Jul 2024 17:07:35 +0100 Subject: [PATCH] fbarray: fix lookbehind ignore mask handling Cc: Xueming Li [ upstream commit 0c6e2781578f37d0497c225acf68ce5ffe31bd8e ] 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 importantly 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") Signed-off-by: Vipin Padmam Ramesh 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 13dc68207f..fb8d32ce31 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; -- 2.34.1 --- Diff of the applied patch vs upstream commit (please double-check if non-empty: --- --- - 2024-08-12 20:44:03.733235102 +0800 +++ 0037-fbarray-fix-lookbehind-ignore-mask-handling.patch 2024-08-12 20:44:02.015069279 +0800 @@ -1 +1 @@ -From 0c6e2781578f37d0497c225acf68ce5ffe31bd8e Mon Sep 17 00:00:00 2001 +From 997166395e73d419c33172abc09d8eb279bee09b Mon Sep 17 00:00:00 2001 @@ -4,0 +5,3 @@ +Cc: Xueming Li + +[ upstream commit 0c6e2781578f37d0497c225acf68ce5ffe31bd8e ] @@ -21 +23,0 @@ -Cc: stable@dpdk.org @@ -76 +78 @@ -index 195f8394be..63d8b731f5 100644 +index 13dc68207f..fb8d32ce31 100644