From patchwork Sun May 5 07:33:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Mattias_R=C3=B6nnblom?= X-Patchwork-Id: 139864 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 40C7943FAC; Sun, 5 May 2024 09:43:59 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 1B6A340647; Sun, 5 May 2024 09:43:42 +0200 (CEST) Received: from EUR02-AM0-obe.outbound.protection.outlook.com (mail-am0eur02on2058.outbound.protection.outlook.com [40.107.247.58]) by mails.dpdk.org (Postfix) with ESMTP id 669AC402DE for ; Sun, 5 May 2024 09:43:37 +0200 (CEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=CHV2nx0q8BD6nhpVv6sTu9Ua5Kpprn2oqvG+afk1vt8CyZPzsGT2zDPC9IrrLvqRDOnt/rOsu2Cu9gC1WrPyIu+7R14Jlo+38sgfGZa7CcPGTyGNuQMj+I7/vIUMSLAqbVVsk+3R70GD4V9GnGkJ7JoVkXHkkbIy4RcTHDdAhWvuIfnuYmquVWWqiRuanO26Lfr5Fyu8l3BvDEY0Z5/W6ZF9azK1wfn48PYLyrlkVpJJ3nlJ3hw9FcGgt6v2fMvxVFl4HXOs9RbxMw9gjlFuTtb5w4r9e9QS4I6aKGBB98sunoZJFPAOFjJMNiXklGoktsa6UtXTxZMKK6aNLymDPQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=25zFeH5qAZJpWPxBUYFWpgHUkxk41okgz7mGFvGIbL8=; b=D89qWK2n0MqFDHXfuTSZhbQQzkACWckd03uUuiZUtXXeVNZc+weXbySx1ibBQkNk2pA6yImycLLe2BVNPRThIuhXn5DRdqMuBuNYcKxp0uA848NWwIVMalaHfqHAkQnwqJG6ADK8CG0eLEuQibhnCYCzLVz/4HGUjBjNsWgeXXT/7FZkTIlA7unOWkQt+v8wdsh/oVT80pmm2G9BA/qYrSCmNEsVvl9BtpJE2Ykeu4A27Y/cQmOKb51P3wI4DyKxCw9X7+MddVT7kaNu+TZ1YJ5KZvaK2JjB24JEBQ8stY4dfVnYVG95wKa7AZ30Kt8xgcMJzkpbeJiLU1OKhmYPNQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 192.176.1.74) smtp.rcpttodomain=dpdk.org smtp.mailfrom=ericsson.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=ericsson.com; dkim=none (message not signed); arc=none (0) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ericsson.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=25zFeH5qAZJpWPxBUYFWpgHUkxk41okgz7mGFvGIbL8=; b=L4gitdVprvdajJp1A4DqSRo9o7TMoPM4Zk8+xmSenhyVZmDCY6tYu988sC//wtgGZWVDQhCDAjoQmJ9opmHu8yMELTrEzruLWSJNjT24k8+DlS22kOr4eLkqAoCVZOGVY1l3SkbcGzOgd+Iw/PX0DxNdWE595iIYE2pt4yptWDqSrOIWXnD3pJZblpuG7bj2lyBZUR2gD8CvBOW03TyxQfnBsKDwUsEI6mMadp7zPyG0JnSqOl9MooaJsB5XoMQJE6AEXIEArMteZs2LnrzigLDwJJIjjXYObjwBdMuXH76tTdY+aR4+SJmnDp3N3FB6/ni6rWecNrfgHwCDIjbF5Q== Received: from AM5PR0101CA0024.eurprd01.prod.exchangelabs.com (2603:10a6:206:16::37) by AS8PR07MB7384.eurprd07.prod.outlook.com (2603:10a6:20b:289::24) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.39; Sun, 5 May 2024 07:43:34 +0000 Received: from AM3PEPF00009B9C.eurprd04.prod.outlook.com (2603:10a6:206:16:cafe::fe) by AM5PR0101CA0024.outlook.office365.com (2603:10a6:206:16::37) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.40 via Frontend Transport; Sun, 5 May 2024 07:43:34 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 192.176.1.74) smtp.mailfrom=ericsson.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=ericsson.com; Received-SPF: Pass (protection.outlook.com: domain of ericsson.com designates 192.176.1.74 as permitted sender) receiver=protection.outlook.com; client-ip=192.176.1.74; helo=oa.msg.ericsson.com; pr=C Received: from oa.msg.ericsson.com (192.176.1.74) by AM3PEPF00009B9C.mail.protection.outlook.com (10.167.16.21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.18 via Frontend Transport; Sun, 5 May 2024 07:43:34 +0000 Received: from seliicinfr00049.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.66) with Microsoft SMTP Server id 15.2.1544.9; Sun, 5 May 2024 09:43:32 +0200 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00049.seli.gic.ericsson.se (Postfix) with ESMTP id 079CC38007A; Sun, 5 May 2024 09:43:32 +0200 (CEST) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: , =?utf-8?q?Morten_Br=C3=B8rup?= , Tyler Retzlaff , Stephen Hemminger , Harry van Haaren , =?utf-8?q?Mattias_R=C3=B6nnb?= =?utf-8?q?lom?= Subject: [RFC v5 1/6] eal: add bitset type Date: Sun, 5 May 2024 09:33:08 +0200 Message-ID: <20240505073313.118515-1-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> References: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: AM3PEPF00009B9C:EE_|AS8PR07MB7384:EE_ X-MS-Office365-Filtering-Correlation-Id: f16aadfc-658f-4bf8-d32f-08dc6cd71169 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; ARA:13230031|1800799015|376005|36860700004|82310400017; X-Microsoft-Antispam-Message-Info: =?utf-8?q?IFT6MyWC32wiCK0y6psvc6hdUzXVOWF?= =?utf-8?q?q/OrItqlIAxKAfcLdx14xl4F14ithWy8XO/aVyCbHe0OlQV3ja0N82oHPI0ylJXO1?= =?utf-8?q?BadKeZxUHJ/LxzRmVvkzRiMT2C7QGm1HaB0AGjSdgGWWmj1s8JxkXKye+KUPZjtVe?= =?utf-8?q?Y+cyvHX9OPmACR93JrwZl57lki3Ng9W8RrylNqZorXjKh6mfbywomJ6K+ieLguSvV?= =?utf-8?q?ljxDZP7rwMV9nH0uQ3rPKM+UKpCRTb9MdacZOKFLb7Kyr5JWJoQtyQzKQBh5gAUZq?= =?utf-8?q?NwDba/B8lpLXr0ns8X9TXrhE3QL17beq9rgytP/z+kSEeE/4lbkEe9ql0ts3b6e6I?= =?utf-8?q?oVoUW4fARsxUyRH0bQYjj9LnOFv35ro7dUf+WtpXDvHyYjXGs2mMQ7+WfESxe+Wz6?= =?utf-8?q?+uz2kN5GRSqQBTEcT9+wfBsuZkJaiTxo3vUKYv/GhvcqwdE6VXiS3Jjehr130Vwl7?= =?utf-8?q?5tCyPCDvXSzzXeme0FwakbGKKEGUFjkqjTM58WDVdg6fY1QJbP6QQ1tnQ981gJfgz?= =?utf-8?q?WZZKhbaS7IkEGhBrCOmrV+B6YZl1is7DqHZoO1f98HeR5amAk77dvja0+eq6Y7N4e?= =?utf-8?q?OvJePuZiXdDoYdDUI5Y3t7LTL/AvZFghwK6wATXlvHC+HhXB31rISXjDuvHuPCegr?= =?utf-8?q?mODezP+XTxmc6nDxNpecCfdtTMFnLANR8PNYMp4NnwwkZ4ZjDbUvKF0bjUt8y3YFB?= =?utf-8?q?gNeicTcO/4Q3oiyxt2Vk4Tzckd8tUiIyc3MqbIePAQxc9rFIIOTfWUlSTJLFxcH9u?= =?utf-8?q?eSPb+7WMBpPhfoX4LYS+4AQ18KNlxpBQIfsefKs1cnetr5fMtYufp/grV2czAp1EC?= =?utf-8?q?Saz4XR4SGTGr2ACB7KPiF8krgL5HOdk8dqMHU8633gY+pOjgz3LBCbxPbWdYSkbmJ?= =?utf-8?q?cHHWr0vUD0gCCr1dlvLj3b7pLTXMkGjokjAQfpyKzcwNNintQgSi/T5l0CEjH7tp2?= =?utf-8?q?nQq3ZB4xJCNQ0H5Gtx+75UtXCHe2D9zv07Yki3nmpTS/tks6/5txnq8WtpaoN7Hly?= =?utf-8?q?Pqt2RBTxr1oRTpPfxHoL6JiJ/s0UAPh+Okq7hEu00Ro/WkE29CoATTE8Jna81x1sI?= =?utf-8?q?4EmwIt65kKsuXYlMLKvsOsXmI87DoMSMy6GZrp0FOK/aWVXt7/vYuNFLTk3iG+cNN?= =?utf-8?q?+7sjDg9Q1Za0lb1U3ng1UMPXVTCQw2XmfKxT65s+1GOcH0mw2ew0XyTZ5KVXtJpgU?= =?utf-8?q?+oNxCg1BniFHYhRTxmv5p2fCCNb7dTE3wvvkTdGjcu3SfAddb3Bq4oYwNjSTqqAY6?= =?utf-8?q?qvpX9Y0zEqEa/sfxay7UwTkNrZ0vid3PkBS0nK/0ZkfE39U0QtB7iTsE=3D?= X-Forefront-Antispam-Report: CIP:192.176.1.74; CTRY:SE; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:oa.msg.ericsson.com; PTR:office365.se.ericsson.net; CAT:NONE; SFS:(13230031)(1800799015)(376005)(36860700004)(82310400017); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 May 2024 07:43:34.5059 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: f16aadfc-658f-4bf8-d32f-08dc6cd71169 X-MS-Exchange-CrossTenant-Id: 92e84ceb-fbfd-47ab-be52-080c6b87953f X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=92e84ceb-fbfd-47ab-be52-080c6b87953f; Ip=[192.176.1.74]; Helo=[oa.msg.ericsson.com] X-MS-Exchange-CrossTenant-AuthSource: AM3PEPF00009B9C.eurprd04.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8PR07MB7384 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 Introduce a set of functions and macros that operate on sets of bits, kept in arrays of 64-bit words. RTE bitset is designed for bitsets which are larger than what fits in a single machine word (i.e., 64 bits). For very large bitsets, the API may be a more appropriate choice. Depends-on: series-31863 ("Improve EAL bit operations API") RFC v5: * Delegate bit test/set/clear/assign/flip to RTE bitops. * Note in the documentation that set/clear/assign/flip are not atomic. RFC v4: * Add function rte_bitset_flip() to change the value of a bit. * Add function rte_bitset_complement(), flipping the value of all bits. * Add function rte_bitset_assign(), setting the value of a bit based on a 'bool' parameter. * Add functions to perform logical shift the bitset left or right. * Add explicit destination bitset to logic operation type functions (e.g., rte_bitset_and()), to increase flexibility. * Split implementation and test suite into distinct commits. RFC v3: * Split the bitset from the htimer patchset, where it was originally hosted. * Rebase to current DPDK main. * Add note that rte_bitset_init() need not be called if bitset words have already been zeroed. * Use REGISTER_FAST_TEST instead of REGISTER_TEST_COMMAND. * Use rte_popcount64() instead of compiler builtin. RFC v2: * Replaced with include, to properly get size_t typedef. * Add to get __rte_experimental in . Signed-off-by: Mattias Rönnblom --- doc/api/doxy-api-index.md | 1 + lib/eal/common/meson.build | 1 + lib/eal/common/rte_bitset.c | 29 + lib/eal/include/meson.build | 1 + lib/eal/include/rte_bitset.h | 1061 ++++++++++++++++++++++++++++++++++ lib/eal/version.map | 2 + 6 files changed, 1095 insertions(+) create mode 100644 lib/eal/common/rte_bitset.c create mode 100644 lib/eal/include/rte_bitset.h diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md index 8c1eb8fafa..1ce04a8edf 100644 --- a/doc/api/doxy-api-index.md +++ b/doc/api/doxy-api-index.md @@ -173,6 +173,7 @@ The public API headers are grouped by topics: [ring](@ref rte_ring.h), [stack](@ref rte_stack.h), [tailq](@ref rte_tailq.h), + [bitset](@ref rte_bitset.h), [bitmap](@ref rte_bitmap.h) - **packet framework**: diff --git a/lib/eal/common/meson.build b/lib/eal/common/meson.build index 22a626ba6f..c1bbf26654 100644 --- a/lib/eal/common/meson.build +++ b/lib/eal/common/meson.build @@ -31,6 +31,7 @@ sources += files( 'eal_common_uuid.c', 'malloc_elem.c', 'malloc_heap.c', + 'rte_bitset.c', 'rte_malloc.c', 'rte_random.c', 'rte_reciprocal.c', diff --git a/lib/eal/common/rte_bitset.c b/lib/eal/common/rte_bitset.c new file mode 100644 index 0000000000..35e55a64db --- /dev/null +++ b/lib/eal/common/rte_bitset.c @@ -0,0 +1,29 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2023 Ericsson AB + */ + +#include + +#include "rte_bitset.h" + +ssize_t +rte_bitset_to_str(const uint64_t *bitset, size_t num_bits, char *buf, + size_t capacity) +{ + size_t i; + + if (capacity < (num_bits + 1)) + return -EINVAL; + + for (i = 0; i < num_bits; i++) { + bool value; + + value = rte_bitset_test(bitset, num_bits - 1 - i); + + buf[i] = value ? '1' : '0'; + } + + buf[num_bits] = '\0'; + + return num_bits + 1; +} diff --git a/lib/eal/include/meson.build b/lib/eal/include/meson.build index e94b056d46..4b5f120a66 100644 --- a/lib/eal/include/meson.build +++ b/lib/eal/include/meson.build @@ -5,6 +5,7 @@ includes += include_directories('.') headers += files( 'rte_alarm.h', + 'rte_bitset.h', 'rte_bitmap.h', 'rte_bitops.h', 'rte_branch_prediction.h', diff --git a/lib/eal/include/rte_bitset.h b/lib/eal/include/rte_bitset.h new file mode 100644 index 0000000000..49a07c77b8 --- /dev/null +++ b/lib/eal/include/rte_bitset.h @@ -0,0 +1,1061 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2023 Ericsson AB + */ + +#ifndef _RTE_BITSET_H_ +#define _RTE_BITSET_H_ + +/** + * @file + * RTE Bitset + * + * This file provides functions and macros for querying and + * manipulating sets of bits kept in arrays of @c uint64_t-sized + * elements. + * + * The bits in a bitset are numbered from 0 to @c size - 1, with the + * lowest index being the least significant bit. + * + * The bitset array must be properly aligned. + * + * For optimal performance, the @c size parameter, required by + * many of the API's functions, should be a compile-time constant. + * + * For large bitsets, the rte_bitmap.h API may be more appropriate. + * + * @warning + * All functions modifying a bitset may overwrite any unused bits of + * the last word. Such unused bits are ignored by all functions reading + * bits. + * + */ + +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * The size (in bytes) of each element in the array used to represent + * a bitset. + */ +#define RTE_BITSET_WORD_SIZE (sizeof(uint64_t)) + +/** + * The size (in bits) of each element in the array used to represent + * a bitset. + */ +#define RTE_BITSET_WORD_BITS (RTE_BITSET_WORD_SIZE * CHAR_BIT) + +/** + * Computes the number of words required to store @c size bits. + */ +#define RTE_BITSET_NUM_WORDS(size) \ + ((size + RTE_BITSET_WORD_BITS - 1) / RTE_BITSET_WORD_BITS) + +/** + * Computes the amount of memory (in bytes) required to fit a bitset + * holding @c size bits. + */ +#define RTE_BITSET_SIZE(size) \ + ((size_t)(RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_SIZE)) + +#define __RTE_BITSET_WORD_IDX(bit_num) ((bit_num) / RTE_BITSET_WORD_BITS) +#define __RTE_BITSET_BIT_OFFSET(bit_num) ((bit_num) % RTE_BITSET_WORD_BITS) +#define __RTE_BITSET_UNUSED(size) \ + ((RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_BITS) \ + - (size)) +#define __RTE_BITSET_USED_MASK(size) \ + (UINT64_MAX >> __RTE_BITSET_UNUSED(size)) + +#define __RTE_BITSET_DELEGATE_N(fun, bitset, bit_num, ...) \ + fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], \ + __RTE_BITSET_BIT_OFFSET(bit_num), __VA_ARGS__) + +/* MSVC doesn't have ##__VA_ARGS__, so argument-less -> special case */ +#define __RTE_BITSET_DELEGATE(fun, bitset, bit_num) \ + fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], \ + __RTE_BITSET_BIT_OFFSET(bit_num)) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Declare a bitset. + * + * Declare (e.g., as a struct field) or define (e.g., as a stack + * variable) a bitset of the specified size. + * + * @param size + * The number of bits the bitset must be able to represent. Must be + * a compile-time constant. + * @param name + * The field or variable name of the resulting definition. + */ +#define RTE_BITSET_DECLARE(name, size) \ + uint64_t name[RTE_BITSET_NUM_WORDS(size)] + +#define __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) \ + ((len) - 1 - ((var) >= (start_bit) ? (var) - (start_bit) : \ + (size) - (start_bit) + (var))) + +#define __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, flags) \ + for ((var) = __rte_bitset_find(bitset, size, start_bit, len, \ + flags); \ + (var) != -1; \ + (var) = __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, \ + len) > 0 ? \ + __rte_bitset_find(bitset, size, \ + ((var) + 1) % (size), \ + __RTE_BITSET_FOREACH_LEFT(var, \ + size, \ + start_bit, \ + len), \ + flags) : -1) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Iterate over all bits set. + * + * This macro iterates over all bits set (i.e., all ones) in the + * bitset, in the forward direction (i.e., starting with the least + * significant '1'). + * + * @param var + * An iterator variable of type @c ssize_t. For each successive + * iteration, this variable will hold the bit index of a set bit. + * @param bitset + * A const uint64_t * pointer to the bitset array. + * @param size + * The size of the bitset (in bits). + */ + +#define RTE_BITSET_FOREACH_SET(var, bitset, size) \ + __RTE_BITSET_FOREACH(var, bitset, size, 0, size, 0) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Iterate over all bits cleared. + * + * This macro iterates over all bits cleared in the bitset, in the + * forward direction (i.e., starting with the lowest-indexed set bit). + * + * @param var + * An iterator variable of type @c ssize_t. For each successive iteration, + * this variable will hold the bit index of a cleared bit. + * @param bitset + * A const uint64_t * pointer to the bitset array. + * @param size + * The size of the bitset (in bits). + */ + +#define RTE_BITSET_FOREACH_CLEAR(var, bitset, size) \ + __RTE_BITSET_FOREACH(var, bitset, size, 0, size, \ + __RTE_BITSET_FIND_FLAG_FIND_CLEAR) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Iterate over all bits set within a range. + * + * This macro iterates over all bits set (i.e., all ones) in the + * specified range, in the forward direction (i.e., starting with the + * least significant '1'). + * + * @param var + * An iterator variable of type @c ssize_t. For each successive iteration, + * this variable will hold the bit index of a set bit. + * @param bitset + * A const uint64_t * pointer to the bitset array. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The length (in bits) of the range. @c start_bit + @c len must be less + * than or equal to @c size. + */ + +#define RTE_BITSET_FOREACH_SET_RANGE(var, bitset, size, start_bit, \ + len) \ + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, 0) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Iterate over all cleared bits within a range. + * + * This macro iterates over all bits cleared (i.e., all zeroes) in the + * specified range, in the forward direction (i.e., starting with the + * least significant '0'). + * + * @param var + * An iterator variable of type @c ssize_t. For each successive iteration, + * this variable will hold the bit index of a set bit. + * @param bitset + * A const uint64_t * pointer to the bitset array. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The length (in bits) of the range. @c start_bit + @c len must be less + * than or equal to @c size. + */ + +#define RTE_BITSET_FOREACH_CLEAR_RANGE(var, bitset, size, start_bit, \ + len) \ + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ + __RTE_BITSET_FIND_FLAG_FIND_CLEAR) + +#define RTE_BITSET_FOREACH_SET_WRAP(var, bitset, size, start_bit, \ + len) \ + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ + __RTE_BITSET_FIND_FLAG_WRAP) + +#define RTE_BITSET_FOREACH_CLEAR_WRAP(var, bitset, size, start_bit, \ + len) \ + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ + __RTE_BITSET_FIND_FLAG_WRAP | \ + __RTE_BITSET_FIND_FLAG_FIND_CLEAR) + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Initializes a bitset. + * + * All bits are cleared. + * + * In case all words in the bitset array are already set to zero by + * other means (e.g., at the time of memory allocation), this function + * need not be called. + * + * @param bitset + * A pointer to the array of bitset 64-bit words. + * @param size + * The size of the bitset (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_init(uint64_t *bitset, size_t size) +{ + memset(bitset, 0, RTE_BITSET_SIZE(size)); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Test if a bit is set. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * Index of the bit to test. Index 0 is the least significant bit. + * @return + * Returns true if the bit is '1', and false if the bit is '0'. + */ + +__rte_experimental +static inline bool +rte_bitset_test(const uint64_t *bitset, size_t bit_num) +{ + return __RTE_BITSET_DELEGATE(rte_bit_test, bitset, bit_num); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Set a bit in the bitset. + * + * Bits are numbered from 0 to (size - 1) (inclusive). + * + * The operation is not guaranteed to be atomic. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be set. + */ + +__rte_experimental +static inline void +rte_bitset_set(uint64_t *bitset, size_t bit_num) +{ + __RTE_BITSET_DELEGATE(rte_bit_set, bitset, bit_num); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Clear a bit in the bitset. + * + * Bits are numbered 0 to (size - 1) (inclusive). + * + * The operation is not guaranteed to be atomic. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be cleared. + */ + +__rte_experimental +static inline void +rte_bitset_clear(uint64_t *bitset, size_t bit_num) +{ + __RTE_BITSET_DELEGATE(rte_bit_clear, bitset, bit_num); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Set or clear a bit in the bitset. + * + * Bits are numbered 0 to (size - 1) (inclusive). + * + * The operation is not guaranteed to be atomic. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be set or cleared. + * @param bit_value + * Control if the bit should be set or cleared. + */ + +__rte_experimental +static inline void +rte_bitset_assign(uint64_t *bitset, size_t bit_num, bool bit_value) +{ + __RTE_BITSET_DELEGATE_N(rte_bit_assign, bitset, bit_num, bit_value); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Change the value of a bit in the bitset. + * + * Bits are numbered 0 to (size - 1) (inclusive). + * + * The operation is not guaranteed to be atomic. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param bit_num + * The index of the bit to be flipped. + */ + +__rte_experimental +static inline void +rte_bitset_flip(uint64_t *bitset, size_t bit_num) +{ + __RTE_BITSET_DELEGATE(rte_bit_flip, bitset, bit_num); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Set all bits in the bitset. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_set_all(uint64_t *bitset, size_t size) +{ + memset(bitset, 0xFF, RTE_BITSET_SIZE(size)); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Clear all bits in the bitset. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_clear_all(uint64_t *bitset, size_t size) +{ + rte_bitset_init(bitset, size); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Count all set bits (also known as the @e weight). + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @return + * Returns the number of '1' bits in the bitset. + */ + +__rte_experimental +static inline size_t +rte_bitset_count_set(const uint64_t *bitset, size_t size) +{ + size_t i; + size_t total = 0; + + /* + * Unused bits in a rte_bitset are always '0', and thus are + * not included in this count. + */ + for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++) + total += rte_popcount64(bitset[i]); + + total += rte_popcount64(bitset[i] & __RTE_BITSET_USED_MASK(size)); + + return total; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Count all cleared bits. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @return + * Returns the number of '0' bits in the bitset. + */ + +__rte_experimental +static inline size_t +rte_bitset_count_clear(const uint64_t *bitset, size_t size) +{ + return size - rte_bitset_count_set(bitset, size); +} + +#define __RTE_BITSET_FIND_FLAG_FIND_CLEAR (1U << 0) +#define __RTE_BITSET_FIND_FLAG_WRAP (1U << 1) + +__rte_experimental +static inline ssize_t +__rte_bitset_find_nowrap(const uint64_t *bitset, size_t __rte_unused size, + size_t start_bit, size_t len, bool find_clear) +{ + size_t word_idx; + size_t offset; + size_t end_bit = start_bit + len; + + RTE_ASSERT(end_bit <= size); + + if (unlikely(len == 0)) + return -1; + + word_idx = __RTE_BITSET_WORD_IDX(start_bit); + offset = __RTE_BITSET_BIT_OFFSET(start_bit); + + while (word_idx <= __RTE_BITSET_WORD_IDX(end_bit - 1)) { + uint64_t word; + int word_ffs; + + word = bitset[word_idx]; + if (find_clear) + word = ~word; + + word >>= offset; + + word_ffs = __builtin_ffsll(word); + + if (word_ffs != 0) { + ssize_t ffs = start_bit + word_ffs - 1; + + /* + * Check if set bit were among the last, + * unused bits, in the last word. + */ + if (unlikely(ffs >= (ssize_t)end_bit)) + return -1; + + return ffs; + } + + start_bit += (RTE_BITSET_WORD_BITS - offset); + word_idx++; + offset = 0; + } + + return -1; + +} + +__rte_experimental +static inline ssize_t +__rte_bitset_find(const uint64_t *bitset, size_t size, size_t start_bit, + size_t len, unsigned int flags) +{ + bool find_clear = flags & __RTE_BITSET_FIND_FLAG_FIND_CLEAR; + bool may_wrap = flags & __RTE_BITSET_FIND_FLAG_WRAP; + bool does_wrap = (start_bit + len) > size; + ssize_t rc; + + RTE_ASSERT(len <= size); + if (!may_wrap) + RTE_ASSERT(!does_wrap); + + if (may_wrap && does_wrap) { + size_t len0 = size - start_bit; + size_t len1 = len - len0; + + rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len0, + find_clear); + if (rc < 0) + rc = __rte_bitset_find_nowrap(bitset, size, + 0, len1, find_clear); + } else + rc = __rte_bitset_find_nowrap(bitset, size, start_bit, + len, find_clear); + + return rc; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first bit set. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), and returns the index of the first '1'. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @return + * Returns the index of the least significant '1', or -1 if all + * bits are '0'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_first_set(const uint64_t *bitset, size_t size) +{ + return __rte_bitset_find(bitset, size, 0, size, 0); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first bit set at offset. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), starting at an offset @c start_bit into the + * bitset, and returns the index of the first '1' encountered. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The number of bits to scan. @c start_bit + @c len must be less + * than or equal to @c size. + * @return + * Returns the index of the least significant '1', or -1 if all + * bits are '0'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_set(const uint64_t *bitset, size_t size, + size_t start_bit, size_t len) +{ + return __rte_bitset_find(bitset, size, start_bit, len, 0); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first bit set at offset, with wrap-around. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), starting at an offset @c start_bit into the + * bitset. If no '1' is encountered before the end of the bitset, the search + * will continue at index 0. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The number of bits to scan. @c start_bit + @c len must be less + * than or equal to @c size. + * @return + * Returns the index of the least significant '1', or -1 if all + * bits are '0'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_set_wrap(const uint64_t *bitset, size_t size, + size_t start_bit, size_t len) +{ + return __rte_bitset_find(bitset, size, start_bit, len, + __RTE_BITSET_FIND_FLAG_WRAP); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first cleared bit. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), and returns the index of the first '0'. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @return + * Returns the index of the least significant '0', or -1 if all + * bits are '1'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_first_clear(const uint64_t *bitset, size_t size) +{ + return __rte_bitset_find(bitset, size, 0, size, + __RTE_BITSET_FIND_FLAG_FIND_CLEAR); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first cleared bit at offset. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), starting at an offset @c start_bit into the + * bitset, and returns the index of the first '0' encountered. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The number of bits to scan. @c start_bit + @c len must be less + * than or equal to @c size. + * @return + * Returns the index of the least significant '0', or -1 if all + * bits are '1'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_clear(const uint64_t *bitset, size_t size, + size_t start_bit, size_t len) +{ + return __rte_bitset_find(bitset, size, start_bit, len, + __RTE_BITSET_FIND_FLAG_FIND_CLEAR); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Find first cleared bit at offset, with wrap-around. + * + * Scans the bitset in the forward direction (i.e., starting at the + * least significant bit), starting at an offset @c start_bit into the + * bitset. If no '0' is encountered before the end of the bitset, the + * search will continue at index 0. + * + * @param bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitset (in bits). + * @param start_bit + * The index of the first bit to check. Must be less than @c size. + * @param len + * The number of bits to scan. @c start_bit + @c len must be less + * than or equal to @c size. + * @return + * Returns the index of the least significant '0', or -1 if all + * bits are '1'. + */ + +__rte_experimental +static inline ssize_t +rte_bitset_find_clear_wrap(const uint64_t *bitset, size_t size, + size_t start_bit, size_t len) +{ + return __rte_bitset_find(bitset, size, start_bit, len, + __RTE_BITSET_FIND_FLAG_FIND_CLEAR | + __RTE_BITSET_FIND_FLAG_WRAP); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Copy bitset. + * + * Copy the bits of the @c src_bitset to the @c dst_bitset. + * + * The bitsets may not overlap and must be of equal size. + * + * @param dst_bitset + * A pointer to the array of words making up the bitset. + * @param src_bitset + * A pointer to the array of words making up the bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_copy(uint64_t *__rte_restrict dst_bitset, + const uint64_t *__rte_restrict src_bitset, + size_t size) +{ + rte_memcpy(dst_bitset, src_bitset, RTE_BITSET_SIZE(size)); +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Bitwise or two bitsets. + * + * Perform a bitwise OR operation on all bits in the two equal-size + * bitsets @c src_bitset0 and @c src_bitset1, and store the results in + * @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset0 + * A pointer to the first source bitset. + * @param src_bitset1 + * A pointer to the second source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_or(uint64_t *dst_bitset, const uint64_t *src_bitset0, + const uint64_t *src_bitset1, size_t size) +{ + size_t i; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) + dst_bitset[i] = src_bitset0[i] | src_bitset1[i]; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Bitwise and two bitsets. + * + * Perform a bitwise AND operation on all bits in the two equal-size + * bitsets @c src_bitset0 and @c src_bitset1, and store the result in + * @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset0 + * A pointer to the first source bitset. + * @param src_bitset1 + * A pointer to the second source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_and(uint64_t *dst_bitset, const uint64_t *src_bitset0, + const uint64_t *src_bitset1, size_t size) +{ + size_t i; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) + dst_bitset[i] = src_bitset0[i] & src_bitset1[i]; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Bitwise xor two bitsets. + * + * Perform a bitwise XOR operation on all bits in the two equal-size + * bitsets @c src_bitset0 and @c src_bitset1, and store the result in + * @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset0 + * A pointer to the first source bitset. + * @param src_bitset1 + * A pointer to the second source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_xor(uint64_t *dst_bitset, const uint64_t *src_bitset0, + const uint64_t *src_bitset1, size_t size) +{ + size_t i; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) + dst_bitset[i] = src_bitset0[i] ^ src_bitset1[i]; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Compute the bitwise complement of a bitset. + * + * Flip every bit in the @c src_bitset, and store the result in @c + * dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset + * A pointer to the source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline void +rte_bitset_complement(uint64_t *dst_bitset, const uint64_t *src_bitset, + size_t size) +{ + size_t i; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) + dst_bitset[i] = ~src_bitset[i]; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Shift bitset left. + * + * Perform a logical shift left of (multiply) @c src_bitset, and store + * the result in @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset + * A pointer to the source bitset. + * @param size + * The size of the bitsets (in bits). + * @param shift_bits + * The number of bits to shift the bitset. + */ + +__rte_experimental +static inline void +rte_bitset_shift_left(uint64_t *dst_bitset, const uint64_t *src_bitset, + size_t size, size_t shift_bits) +{ + const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS; + const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS; + unsigned int dst_idx; + + for (dst_idx = 0; dst_idx < RTE_BITSET_NUM_WORDS(size); dst_idx++) { + int src_high_idx = dst_idx - src_word_offset; + uint64_t low_bits = 0; + uint64_t high_bits = 0; + + if (src_high_idx >= 0) { + int src_low_idx = src_high_idx - 1; + + high_bits = src_bitset[src_high_idx] << src_bit_offset; + + if (src_bit_offset > 0 && src_low_idx >= 0) + low_bits = src_bitset[src_low_idx] >> + (RTE_BITSET_WORD_BITS - src_bit_offset); + } + dst_bitset[dst_idx] = low_bits | high_bits; + } +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Shift bitset right. + * + * Perform a logical shift right of (divide) @c src_bitset, and store + * the result in @c dst_bitset. + * + * @param dst_bitset + * A pointer to the destination bitset. + * @param src_bitset + * A pointer to the source bitset. + * @param size + * The size of the bitsets (in bits). + * @param shift_bits + * The number of bits to shift the bitset. + */ + +__rte_experimental +static inline void +rte_bitset_shift_right(uint64_t *dst_bitset, const uint64_t *src_bitset, + size_t size, size_t shift_bits) +{ + const int num_words = RTE_BITSET_NUM_WORDS(size); + const uint64_t used_mask = __RTE_BITSET_USED_MASK(size); + const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS; + const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS; + int dst_idx; + + for (dst_idx = 0; dst_idx < num_words; dst_idx++) { + int src_low_idx = src_word_offset + dst_idx; + int src_high_idx = src_low_idx + 1; + uint64_t src_low_word_bits = 0; + uint64_t src_high_word_bits = 0; + + if (src_low_idx < num_words) { + src_low_word_bits = src_bitset[src_low_idx]; + + if (src_low_idx == (num_words - 1)) + src_low_word_bits &= used_mask; + + src_low_word_bits >>= src_bit_offset; + + if (src_bit_offset > 0 && src_high_idx < num_words) { + src_high_word_bits = src_bitset[src_high_idx]; + + if (src_high_idx == (num_words - 1)) + src_high_word_bits &= used_mask; + + src_high_word_bits <<= + (RTE_BITSET_WORD_BITS - src_bit_offset); + } + } + dst_bitset[dst_idx] = src_low_word_bits | src_high_word_bits; + } +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Compare two bitsets. + * + * Compare two bitsets for equality. + * + * @param bitset_a + * A pointer to the destination bitset. + * @param bitset_b + * A pointer to the source bitset. + * @param size + * The size of the bitsets (in bits). + */ + +__rte_experimental +static inline bool +rte_bitset_equal(const uint64_t *bitset_a, const uint64_t *bitset_b, + size_t size) +{ + size_t i; + uint64_t last_a, last_b; + + for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++) + if (bitset_a[i] != bitset_b[i]) + return false; + + last_a = bitset_a[i] << __RTE_BITSET_UNUSED(size); + last_b = bitset_b[i] << __RTE_BITSET_UNUSED(size); + + return last_a == last_b; +} + +/** + * @warning + * @b EXPERIMENTAL: this API may change without prior notice. + * + * Converts a bitset to a string. + * + * This function prints a string representation of the bitstring to + * the supplied buffer. + * + * Each bit is represented either by '0' or '1' in the output, with + * the first (left-most) character in the output being the most + * significant bit. The resulting string is NUL terminated. + * + * @param bitset + * A pointer to the array of bitset 64-bit words. + * @param size + * The number of bits the bitset represent. + * @param buf + * A buffer to hold the output. + * @param capacity + * The size of the buffer. Must be @c size + 1 or larger. + * @return + * Returns the number of bytes written (i.e., @c size + 1), or -EINVAL + * in case the buffer capacity was too small. + */ + +__rte_experimental +ssize_t +rte_bitset_to_str(const uint64_t *bitset, size_t size, char *buf, + size_t capacity); + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_BITSET_H_ */ diff --git a/lib/eal/version.map b/lib/eal/version.map index 3df50c3fbb..254d3fd4b2 100644 --- a/lib/eal/version.map +++ b/lib/eal/version.map @@ -396,6 +396,8 @@ EXPERIMENTAL { # added in 24.03 rte_vfio_get_device_info; # WINDOWS_NO_EXPORT + + rte_bitset_to_str; }; INTERNAL { From patchwork Sun May 5 07:33:12 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Mattias_R=C3=B6nnblom?= X-Patchwork-Id: 139866 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 2BD9843FAC; Sun, 5 May 2024 09:44:13 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 371824067E; Sun, 5 May 2024 09:43:45 +0200 (CEST) Received: from EUR05-DB8-obe.outbound.protection.outlook.com (mail-db8eur05on2064.outbound.protection.outlook.com [40.107.20.64]) by mails.dpdk.org (Postfix) with ESMTP id CC132402E1 for ; Sun, 5 May 2024 09:43:37 +0200 (CEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=SRpqcUrcdlASfEUy6XWrTjsaplVX2VGImWIKVsyhcDO1OvFDTdSv+Wki5/POb7GawBhlThvWbnKBQ8t0OB9OwB/9DHmDfPsDi0YJ/hW9D91L0WXrGryqR9Bl+30xQH3TifbiCbMF+/f6TmJklfP7enWEks4YMyVLiv9EWYj/RCx1D65cqMtb8nYzMTEvscd13QICUfdhcxlDbG5zoVXDq9AB9YSUdA/EqH9cJ8yfnH+qrF4/7A25tnmw5iOrhsyXx/waHq0vIOWNE9tolPHValNSvptxzKuy5/h7Z04SaXPI3l6VvbjB2heSG8yHm8IstyG/R27+bDYcrDeZQ2OOJw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=Mx2k72mHtMfvaE5BD+qrppgugwcEHxL9T3OLZibFkgE=; b=EI0LpDyEybiPrmEhYAUj2Wrms2ABOIC6CgCpTV+v+8bjd7OeffnjbwCM+ZZjCzhB/ovdBXXgyh9bbJX6hLB0LMgmG33Ewy8EnBLIn/gw4dz2XWNBeWU27iKEeWdUECTyvbZeF/RsUMrCq3tZwjG13AJxWu7sP3M9oj95O4S6ZVwux2GE4YRtd7b/DPaT5nOIIj9t02vbdoJzb2mSn86A0kiCSgBOFuN+xlej3EwDI6GLQ3vVSOmBKF+VqcIiJAKd/2yvtRl9w7eRjomF+6m/DI/aYDHpU1wu+eMZVz0WynwyAeTmv1rPdQiyzzwvk2SnL6nkLMBsZP57f5ngvnuyIA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 192.176.1.74) smtp.rcpttodomain=dpdk.org smtp.mailfrom=ericsson.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=ericsson.com; dkim=none (message not signed); arc=none (0) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ericsson.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=Mx2k72mHtMfvaE5BD+qrppgugwcEHxL9T3OLZibFkgE=; b=qaU7zNhxSRBSAOdXKQ1KrJst9E3O4mPwlQptaj4fsbvnM3AwUzvXJZu0CrCiAlyW9gqIWCszmVvn+2hi7jssQ1Njr9zvzsZb7hOwVQnUu6TC0dgirkWC/ONv95UuXmu4Kk3L7FmtoOKUwfx+C4Z1q/XXbgzUDASBllIG4zmw2JwOyNyL0WV9q+EP632krfSZ+CfW0kzWwaK0Zw7fJAi8e1EMtwOjJIGczjVKy6yjgetLNN88e9OACAoGRykZI7gjpUiRCi25zudycGx9JNN0bKt75ud0xh+nZ/VVrvAmB+ziy84ht0Lu1nRMF310uJiMjHXDZgvZJxkOnBxByXeNFg== Received: from DUZPR01CA0337.eurprd01.prod.exchangelabs.com (2603:10a6:10:4b8::10) by AM9PR07MB7812.eurprd07.prod.outlook.com (2603:10a6:20b:2fe::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.39; Sun, 5 May 2024 07:43:35 +0000 Received: from DB1PEPF000509E7.eurprd03.prod.outlook.com (2603:10a6:10:4b8:cafe::af) by DUZPR01CA0337.outlook.office365.com (2603:10a6:10:4b8::10) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.39 via Frontend Transport; Sun, 5 May 2024 07:43:35 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 192.176.1.74) smtp.mailfrom=ericsson.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=ericsson.com; Received-SPF: Pass (protection.outlook.com: domain of ericsson.com designates 192.176.1.74 as permitted sender) receiver=protection.outlook.com; client-ip=192.176.1.74; helo=oa.msg.ericsson.com; pr=C Received: from oa.msg.ericsson.com (192.176.1.74) by DB1PEPF000509E7.mail.protection.outlook.com (10.167.242.57) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7519.19 via Frontend Transport; Sun, 5 May 2024 07:43:35 +0000 Received: from seliicinfr00049.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.69) with Microsoft SMTP Server id 15.2.1544.9; Sun, 5 May 2024 09:43:34 +0200 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00049.seli.gic.ericsson.se (Postfix) with ESMTP id 884D038007A; Sun, 5 May 2024 09:43:34 +0200 (CEST) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: , =?utf-8?q?Morten_Br=C3=B8rup?= , Tyler Retzlaff , Stephen Hemminger , Harry van Haaren , =?utf-8?q?Mattias_R=C3=B6nnb?= =?utf-8?q?lom?= Subject: [RFC v5 5/6] service: use multi-word bitset to represent service flags Date: Sun, 5 May 2024 09:33:12 +0200 Message-ID: <20240505073313.118515-5-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240505073313.118515-1-mattias.ronnblom@ericsson.com> References: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> <20240505073313.118515-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: DB1PEPF000509E7:EE_|AM9PR07MB7812:EE_ X-MS-Office365-Filtering-Correlation-Id: 3c325b78-45fd-41cb-61d5-08dc6cd711cd X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; ARA:13230031|1800799015|376005|36860700004|82310400017; X-Microsoft-Antispam-Message-Info: =?utf-8?q?+6yyeeD/uH+2sYN8Y1/TP4RiNPzkpn1?= =?utf-8?q?5SFpM0XeHkjmKXsGgt52uS7/y/EUWbGEwyPwhcQaHEQKoAVcfr6kb3nEjP8lEWQdQ?= =?utf-8?q?h6EHT1tWFvCs1QRkk8WmKfp0CtD9dWCXAmiXdqdH17GSGjzFniiIQgPgJ5Cqz3ucS?= =?utf-8?q?uaf5w5JcjX4g9Jqj0B5XICwAZGlY2KBlKfa527mHgzCCOjzcz01IMQ9tCNcF+v1ux?= =?utf-8?q?y2IDPjaHVUl/XEi6MlvevgPDknuT2IIxALAbQVkUgw7hbUIO/YcdwcCP9bSOF1rNO?= =?utf-8?q?K+Cv9U6C8qzmU1EqcDKSQjrJoRXe9hD3Rt9+lD0rm9LYYT6E4a5Y4W6tZSqGum3lT?= =?utf-8?q?iGB0fe8Pa2/NxrgAdacKGQ19T3LYD+Dz7lp6MR9B5L7Toh1YPzVTsiCNbont637/L?= =?utf-8?q?DMcr1T19EOd8RkWIi8X7vMHGXU5IGxrx/jt7Oe+d551omEPu93pQEMBjQ2t+u16MS?= =?utf-8?q?ZeKim3y4xEt9nt21zs/RUlDWXJ/D1/5Clk/bpdrXgEvRKWH3rwBVH+vH2JwLPTso0?= =?utf-8?q?ZKH6q4rHDIsBErC/0nLvwnCZjJBd5Kic4bsbuNVVmeiV3aSuPf1DwjGrxxyjIJMKt?= =?utf-8?q?4kT6A4Cf5rj64tTjqICbv05BY4c5wdQ6ulrE7egdRrIUpO2YSx5Xv05o+HCGUZCYG?= =?utf-8?q?sdqM55dPzDjha+knoBtWYsF9ClkUJeG6uB/ashi4HMn9VS4Z3GqbhkxN3l9M6bQ6p?= =?utf-8?q?LGkzgvXPrZa/J7EugmvwQSKvvNNaLAjh13UfLpU2WKAB4thK1XSghM7VFAyAti/+I?= =?utf-8?q?CnyMBvEzBH2AuDysXSno+Qg+7rhU2DggVIpHxzCU0jJQOyK0jOEnbQIbrBeWUVqwT?= =?utf-8?q?cFTIMST+A4Fcefrhkonv5piPwO/7Vf2HSCgn/CSIBXSwR8+WSoWYzW/lts9r8c+Pb?= =?utf-8?q?eD7IumMiPw59SJ8c0jGExr9C7CQHw+Su6nrnQiVEQOD28RCZZTC9sAPEDvq76785b?= =?utf-8?q?bgkoIL7tiZn//JKxscEB0OMCWFMXb+bv1qn7qYjD8OtgubX60dcygzkas0lFlamVO?= =?utf-8?q?lqvg2Iwzw7oqFvi1b+Y1FR+G309fSazMrXtcPhOZv7ki5vBCm/jCNs9AMBBccGHDK?= =?utf-8?q?zoYQHt4oWmdf466n8d4GHdqT0GEebNSC9jmk0iR8zytvBX7c3MEu9Fv6hwb7Xf10Y?= =?utf-8?q?51k60SeGMaK1RajEJrZ6H2YEulsehzEzH+bwV/22KDUwYB2f/LxPLyhygrp4dz9Do?= =?utf-8?q?Jde57SKHk5jM2UG1LoY3vde1koiSxD+7FC68jvezvKHd6v5JbPF6OhBq1PR4kyqx8?= =?utf-8?q?tDu6pD7bWwFkVcdg5Yrz1qqqa2akNc5jfKFr8rFTKbA9t2gKqjZpxeybf3KspRJfh?= =?utf-8?q?+13k0VZkpXAN?= X-Forefront-Antispam-Report: CIP:192.176.1.74; CTRY:SE; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:oa.msg.ericsson.com; PTR:office365.se.ericsson.net; CAT:NONE; SFS:(13230031)(1800799015)(376005)(36860700004)(82310400017); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 May 2024 07:43:35.1427 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 3c325b78-45fd-41cb-61d5-08dc6cd711cd X-MS-Exchange-CrossTenant-Id: 92e84ceb-fbfd-47ab-be52-080c6b87953f X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=92e84ceb-fbfd-47ab-be52-080c6b87953f; Ip=[192.176.1.74]; Helo=[oa.msg.ericsson.com] X-MS-Exchange-CrossTenant-AuthSource: DB1PEPF000509E7.eurprd03.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM9PR07MB7812 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 Use a multi-word bitset to track which services are mapped to which lcores, allowing the RTE_SERVICE_NUM_MAX compile-time constant to be > 64. Replace array-of-bytes service-currently-active flags with a more compact multi-word bitset-based representation, reducing memory footprint somewhat. Signed-off-by: Mattias Rönnblom --- lib/eal/common/rte_service.c | 70 ++++++++++++++---------------------- 1 file changed, 27 insertions(+), 43 deletions(-) diff --git a/lib/eal/common/rte_service.c b/lib/eal/common/rte_service.c index 56379930b6..ec0f47e141 100644 --- a/lib/eal/common/rte_service.c +++ b/lib/eal/common/rte_service.c @@ -11,6 +11,7 @@ #include #include +#include #include #include #include @@ -63,11 +64,11 @@ struct service_stats { /* the internal values of a service core */ struct __rte_cache_aligned core_state { /* map of services IDs are run on this core */ - uint64_t service_mask; + RTE_BITSET_DECLARE(mapped_services, RTE_SERVICE_NUM_MAX); RTE_ATOMIC(uint8_t) runstate; /* running or stopped */ RTE_ATOMIC(uint8_t) thread_active; /* indicates when thread is in service_run() */ uint8_t is_service_core; /* set if core is currently a service core */ - uint8_t service_active_on_lcore[RTE_SERVICE_NUM_MAX]; + RTE_BITSET_DECLARE(service_active_on_lcore, RTE_SERVICE_NUM_MAX); RTE_ATOMIC(uint64_t) loops; RTE_ATOMIC(uint64_t) cycles; struct service_stats service_stats[RTE_SERVICE_NUM_MAX]; @@ -81,11 +82,6 @@ static uint32_t rte_service_library_initialized; int32_t rte_service_init(void) { - /* Hard limit due to the use of an uint64_t-based bitmask (and the - * clzl intrinsic). - */ - RTE_BUILD_BUG_ON(RTE_SERVICE_NUM_MAX > 64); - if (rte_service_library_initialized) { EAL_LOG(NOTICE, "service library init() called, init flag %d", @@ -296,7 +292,7 @@ rte_service_component_unregister(uint32_t id) /* clear the run-bit in all cores */ for (i = 0; i < RTE_MAX_LCORE; i++) - lcore_states[i].service_mask &= ~(UINT64_C(1) << id); + rte_bitset_clear(lcore_states[i].mapped_services, id); memset(&rte_services[id], 0, sizeof(struct rte_service_spec_impl)); @@ -410,7 +406,7 @@ service_runner_do_callback(struct rte_service_spec_impl *s, /* Expects the service 's' is valid. */ static int32_t -service_run(uint32_t i, struct core_state *cs, uint64_t service_mask, +service_run(uint32_t i, struct core_state *cs, const uint64_t *mapped_services, struct rte_service_spec_impl *s, uint32_t serialize_mt_unsafe) { if (!s) @@ -424,12 +420,12 @@ service_run(uint32_t i, struct core_state *cs, uint64_t service_mask, RUNSTATE_RUNNING || rte_atomic_load_explicit(&s->app_runstate, rte_memory_order_acquire) != RUNSTATE_RUNNING || - !(service_mask & (UINT64_C(1) << i))) { - cs->service_active_on_lcore[i] = 0; + !rte_bitset_test(mapped_services, i)) { + rte_bitset_clear(cs->service_active_on_lcore, i); return -ENOEXEC; } - cs->service_active_on_lcore[i] = 1; + rte_bitset_set(cs->service_active_on_lcore, i); if ((service_mt_safe(s) == 0) && (serialize_mt_unsafe == 1)) { if (!rte_spinlock_trylock(&s->execute_lock)) @@ -454,7 +450,7 @@ rte_service_may_be_active(uint32_t id) return -EINVAL; for (i = 0; i < lcore_count; i++) { - if (lcore_states[ids[i]].service_active_on_lcore[id]) + if (rte_bitset_test(lcore_states[ids[i]].service_active_on_lcore, id)) return 1; } @@ -474,7 +470,9 @@ rte_service_run_iter_on_app_lcore(uint32_t id, uint32_t serialize_mt_unsafe) */ rte_atomic_fetch_add_explicit(&s->num_mapped_cores, 1, rte_memory_order_relaxed); - int ret = service_run(id, cs, UINT64_MAX, s, serialize_mt_unsafe); + RTE_BITSET_DECLARE(all_services, RTE_SERVICE_NUM_MAX); + rte_bitset_set_all(all_services, RTE_SERVICE_NUM_MAX); + int ret = service_run(id, cs, all_services, s, serialize_mt_unsafe); rte_atomic_fetch_sub_explicit(&s->num_mapped_cores, 1, rte_memory_order_relaxed); @@ -485,7 +483,6 @@ static int32_t service_runner_func(void *arg) { RTE_SET_USED(arg); - uint8_t i; const int lcore = rte_lcore_id(); struct core_state *cs = &lcore_states[lcore]; @@ -497,20 +494,11 @@ service_runner_func(void *arg) */ while (rte_atomic_load_explicit(&cs->runstate, rte_memory_order_acquire) == RUNSTATE_RUNNING) { + ssize_t id; - const uint64_t service_mask = cs->service_mask; - uint8_t start_id; - uint8_t end_id; - - if (service_mask == 0) - continue; - - start_id = rte_ctz64(service_mask); - end_id = 64 - rte_clz64(service_mask); - - for (i = start_id; i < end_id; i++) { + RTE_BITSET_FOREACH_SET(id, cs->mapped_services, RTE_SERVICE_NUM_MAX) { /* return value ignored as no change to code flow */ - service_run(i, cs, service_mask, service_get(i), 1); + service_run(id, cs, cs->mapped_services, service_get(id), 1); } rte_atomic_store_explicit(&cs->loops, cs->loops + 1, rte_memory_order_relaxed); @@ -519,8 +507,7 @@ service_runner_func(void *arg) /* Switch off this core for all services, to ensure that future * calls to may_be_active() know this core is switched off. */ - for (i = 0; i < RTE_SERVICE_NUM_MAX; i++) - cs->service_active_on_lcore[i] = 0; + rte_bitset_clear_all(cs->service_active_on_lcore, RTE_SERVICE_NUM_MAX); /* Use SEQ CST memory ordering to avoid any re-ordering around * this store, ensuring that once this store is visible, the service @@ -586,7 +573,7 @@ rte_service_lcore_count_services(uint32_t lcore) if (!cs->is_service_core) return -ENOTSUP; - return rte_popcount64(cs->service_mask); + return rte_bitset_count_set(cs->mapped_services, RTE_SERVICE_NUM_MAX); } int32_t @@ -639,25 +626,23 @@ service_update(uint32_t sid, uint32_t lcore, uint32_t *set, uint32_t *enabled) !lcore_states[lcore].is_service_core) return -EINVAL; - uint64_t sid_mask = UINT64_C(1) << sid; if (set) { - uint64_t lcore_mapped = lcore_states[lcore].service_mask & - sid_mask; + uint64_t lcore_mapped = rte_bitset_test(lcore_states[lcore].mapped_services, sid); if (*set && !lcore_mapped) { - lcore_states[lcore].service_mask |= sid_mask; + rte_bitset_set(lcore_states[lcore].mapped_services, sid); rte_atomic_fetch_add_explicit(&rte_services[sid].num_mapped_cores, 1, rte_memory_order_relaxed); } if (!*set && lcore_mapped) { - lcore_states[lcore].service_mask &= ~(sid_mask); + rte_bitset_clear(lcore_states[lcore].mapped_services, sid); rte_atomic_fetch_sub_explicit(&rte_services[sid].num_mapped_cores, 1, rte_memory_order_relaxed); } } if (enabled) - *enabled = !!(lcore_states[lcore].service_mask & (sid_mask)); + *enabled = rte_bitset_test(lcore_states[lcore].mapped_services, sid); return 0; } @@ -699,11 +684,11 @@ set_lcore_state(uint32_t lcore, int32_t state) int32_t rte_service_lcore_reset_all(void) { - /* loop over cores, reset all to mask 0 */ + /* loop over cores, reset all mapped services */ uint32_t i; for (i = 0; i < RTE_MAX_LCORE; i++) { if (lcore_states[i].is_service_core) { - lcore_states[i].service_mask = 0; + rte_bitset_clear_all(lcore_states[i].mapped_services, RTE_SERVICE_NUM_MAX); set_lcore_state(i, ROLE_RTE); /* runstate act as guard variable Use * store-release memory order here to synchronize @@ -731,7 +716,7 @@ rte_service_lcore_add(uint32_t lcore) set_lcore_state(lcore, ROLE_SERVICE); /* ensure that after adding a core the mask and state are defaults */ - lcore_states[lcore].service_mask = 0; + rte_bitset_clear_all(lcore_states[lcore].mapped_services, RTE_SERVICE_NUM_MAX); /* Use store-release memory order here to synchronize with * load-acquire in runstate read functions. */ @@ -814,12 +799,11 @@ rte_service_lcore_stop(uint32_t lcore) uint32_t i; struct core_state *cs = &lcore_states[lcore]; - uint64_t service_mask = cs->service_mask; for (i = 0; i < RTE_SERVICE_NUM_MAX; i++) { - int32_t enabled = service_mask & (UINT64_C(1) << i); - int32_t service_running = rte_service_runstate_get(i); - int32_t only_core = (1 == + bool enabled = rte_bitset_test(cs->mapped_services, i); + bool service_running = rte_service_runstate_get(i); + bool only_core = (1 == rte_atomic_load_explicit(&rte_services[i].num_mapped_cores, rte_memory_order_relaxed)); From patchwork Sun May 5 07:33:13 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Mattias_R=C3=B6nnblom?= X-Patchwork-Id: 139865 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 5B38143FAC; Sun, 5 May 2024 09:44:07 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id E186F4064C; Sun, 5 May 2024 09:43:43 +0200 (CEST) Received: from EUR05-VI1-obe.outbound.protection.outlook.com (mail-vi1eur05on2053.outbound.protection.outlook.com [40.107.21.53]) by mails.dpdk.org (Postfix) with ESMTP id B981C4025D for ; Sun, 5 May 2024 09:43:37 +0200 (CEST) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=g8YJRG2mxjp3hmazc7Qp+B4O0XRZZqFAKMFKKioZJF0JR8zRO7xnvil2CcCbFrTyCkLITEHZ6H8xeBGTAw2PwvMu4DidfXuK4ZsOOCUU4tEdbArrMQ+rNk4Mp06BRnsGr99QwB2DAp3F/dQDxID1IGYHWVYzFR5USSIU7N1rCXB0tU7U3hkqKaLsLS8/szKna7ZqaDAJwmiSRo9UM5fW+e/F5Fyo9/8REfDr79ONmvjCAG2NUqNZey6jG+W+QNmq08wXZSKSPl1vpoTPW92DfxSnIrXXFRDk4KdRPlz1OmY8762x4ovnPLTKNrayoHu79ER/BMLKkEzDOa9ljq20Kw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; 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=yg9JyEy7mLkxh3uPP7MtbRx4iQ/spseeByLLkTdz4d0=; b=aYcqtmE9e/qiglTYihtXS6SUJTzeFKhuQK1sGN7MX+nPRNCUvDIGc4ZdIBxujyf+u2tgqWmb4HpJFK/QdV1i8HM1zNQp97ucTKrKq4pYeS+YwUEAmZ8wbv6ZnOp4ReUHNf6UNakb+qiPzUq17SPU5CILBMRUFHdluKkAw32lH0X0eZ7/Nxf5Iu7bBJbYyg/vb9oautzXjrHtSuFqCzE/wBg7kFmJwn+OYuKRIdPF7pU7byG66hleFA18M/rX9IZ20ypMiludaggpUZcHIFmrBUaFJ3cd0MnrvxrCiDnSviXHYLOIJ3LdN/W5X7v9X0b2inSYJQ9CeTGR8ISMmqztHg== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 192.176.1.74) smtp.rcpttodomain=dpdk.org smtp.mailfrom=ericsson.com; dmarc=pass (p=reject sp=reject pct=100) action=none header.from=ericsson.com; dkim=none (message not signed); arc=none (0) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ericsson.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=yg9JyEy7mLkxh3uPP7MtbRx4iQ/spseeByLLkTdz4d0=; b=qrD13SVzZMIwZcAl2zesOO9xH0dCecWjuCZeb8vQVfChNMQ3O2wbW48xfl6XVPDkLr7OcdU+YMIHHwjfLkuPwiGTbwabb2yzvWvv2xUFdwMPcC14P2Oqkw01P0t08WJuQnYSdj/uAV5zGRbfaxoqkyVlhJ9fX8adGvRzzKjAKiNRZfZtOJV5WppG7wZtRGnIOaTvxUX+0UCCen8OknIe4nD9ByJC3o2eJw/GEuGumPFxUYMQDImmDEv7LY3ATIFIdyohKIsA5HcpOGvUB6xWYsEGgpzKosDvzokvee7C7u25GS+Nes9Z9mU9Rf436r3iQmUKaGw2HQlLF+Riu8nvZg== Received: from DUZPR01CA0332.eurprd01.prod.exchangelabs.com (2603:10a6:10:4b8::18) by AS8PR07MB7765.eurprd07.prod.outlook.com (2603:10a6:20b:396::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.39; Sun, 5 May 2024 07:43:36 +0000 Received: from DB1PEPF000509E7.eurprd03.prod.outlook.com (2603:10a6:10:4b8:cafe::fb) by DUZPR01CA0332.outlook.office365.com (2603:10a6:10:4b8::18) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7544.39 via Frontend Transport; Sun, 5 May 2024 07:43:36 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 192.176.1.74) smtp.mailfrom=ericsson.com; dkim=none (message not signed) header.d=none;dmarc=pass action=none header.from=ericsson.com; Received-SPF: Pass (protection.outlook.com: domain of ericsson.com designates 192.176.1.74 as permitted sender) receiver=protection.outlook.com; client-ip=192.176.1.74; helo=oa.msg.ericsson.com; pr=C Received: from oa.msg.ericsson.com (192.176.1.74) by DB1PEPF000509E7.mail.protection.outlook.com (10.167.242.57) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7519.19 via Frontend Transport; Sun, 5 May 2024 07:43:36 +0000 Received: from seliicinfr00049.seli.gic.ericsson.se (153.88.142.248) by smtp-central.internal.ericsson.com (100.87.178.69) with Microsoft SMTP Server id 15.2.1544.9; Sun, 5 May 2024 09:43:35 +0200 Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100]) by seliicinfr00049.seli.gic.ericsson.se (Postfix) with ESMTP id 258FA38007A; Sun, 5 May 2024 09:43:35 +0200 (CEST) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: , =?utf-8?q?Morten_Br=C3=B8rup?= , Tyler Retzlaff , Stephen Hemminger , Harry van Haaren , =?utf-8?q?Mattias_R=C3=B6nnb?= =?utf-8?q?lom?= Subject: [RFC v5 6/6] event/dsw: optimize serving port logic Date: Sun, 5 May 2024 09:33:13 +0200 Message-ID: <20240505073313.118515-6-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240505073313.118515-1-mattias.ronnblom@ericsson.com> References: <20240216102348.480407-1-mattias.ronnblom@ericsson.com> <20240505073313.118515-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-EOPAttributedMessage: 0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: DB1PEPF000509E7:EE_|AS8PR07MB7765:EE_ X-MS-Office365-Filtering-Correlation-Id: b95395f7-336b-4b66-6d5e-08dc6cd7127b X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; ARA:13230031|82310400017|36860700004|1800799015|376005; X-Microsoft-Antispam-Message-Info: =?utf-8?q?nP0pd3993kRA3aj9Cm/3SA/IAXmHsdf?= =?utf-8?q?gmOj2PC6hzz0xjTzGs9fmsEaAnonv5Hq8I4Ic7rI2WYdV219QcW2PQuLAAmfisWG/?= =?utf-8?q?YCZ1P+8+h4gyessw95u8fkMLsGX7A0RfT7VwJqn/Bz+LNDhvBtDUZwdyHzhlMbY6J?= =?utf-8?q?45IYYX8o7P+F/BQ76PG/iHAdGiSMHcP8B8zP9pxpuCWdLyBHUApEDdDEYnXxn22UH?= =?utf-8?q?SqDUh/VlYTg98rqR3lOD89sJABinBwBvdRBpzkU9gcgmMJAv4fuQCnZqh0DcOKIPj?= =?utf-8?q?aYBNkP4rdglAp2Pp0Q4mzpF5PABHJNGmhbAYo3WhLgWIyLohYjKRtDJhZOQYn2+ML?= =?utf-8?q?nuPixSx/9XB2I2nleN2kdENk75blBXIvLaKUisHEAkG2mYPsupyNh7z2uRKiIPue2?= =?utf-8?q?OZHCnJZB41Myb+mlGPzWLjhL6UPzTPEGpk36COzFNStjxLpk0bHoUO2nn81mnVBJZ?= =?utf-8?q?VYZqVg6aCawkQuapd/7GViq+ppqirYUGu7Vw8hGEVDT/1xa2dfsKvXOwm+YenBwOq?= =?utf-8?q?ZYbqL90ScvPg7Tf30xH8KfbefenfLrkrtJStNhne3e/3/7sR2fD8fkDhW2eh6NdVo?= =?utf-8?q?Sjt5kVBOUxgBfA9Z83Qm/g6D8oNeUW98DxO2rRytxqzNRpfyphNIJHPFQJ44ji/sF?= =?utf-8?q?eVfXVBto1whyjJuYgu5Gw45SzlKd7NuaGxp6YlwE5y1kVRR9bbpvJH2FVxtQSKNPD?= =?utf-8?q?xoGnpjtGVcuZAsfHwCbLDzs86jbBr/lof3PZqneuEYIibDCxpzKqRnlIo/2/nUDc6?= =?utf-8?q?cCOMHFxoCSWNbQDO/r+GGqPAakXrBthSbYL3BswnWbDw7Q8tGKHq4dNGFjYH665SM?= =?utf-8?q?rv2yAsuiVyymTfLOXS4VcwdQBSEpoz1KFNdWCNTTpXjjqsRdZHSN9YD9vw6ZHha2/?= =?utf-8?q?vjyz3kQxpAsmC9lesYyOFvJkcykTvgSbCQbkOZwLUHhB9rvI0zUFoC/7WsvKntZ4C?= =?utf-8?q?MPpSqr+yHhNaBHRb/aPq3txUdg9XgJJ6XguzgVH95yH2RI3tvkexoWYn+kizWkc8E?= =?utf-8?q?DZjXTmSBzV8AHXi2O8kwXmSMBwmrE0VHeZvo5ZjKb5KOVyo/T4X7gbS6cEzfbUwYT?= =?utf-8?q?F4haDr7jyGBw8/6L7xvwQLOrX/FzcdhvHI6QiMjaA149QksNrMhCWfEhZ/weWeKPE?= =?utf-8?q?NkL4vEFsLmpuvkcW1WH5YpH32M+uJujCO4f24zewP4surh/e8PKjb5r+32Eemjvf2?= =?utf-8?q?sCR4V9/k2UXRzZrz90iv0+69rpUS1UoJZRwtVJJgSgoecpT3iEa8Jx8OPYtJ3w6fS?= =?utf-8?q?k+Jux0UtzeAO2Xt8UpA7UhYTL4/W1caKL1zE2zLqPdQpJzg4JJvsgvi5FXW3BJ01z?= =?utf-8?q?MitynCiuYzmj?= X-Forefront-Antispam-Report: CIP:192.176.1.74; CTRY:SE; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:oa.msg.ericsson.com; PTR:office365.se.ericsson.net; CAT:NONE; SFS:(13230031)(82310400017)(36860700004)(1800799015)(376005); DIR:OUT; SFP:1101; X-OriginatorOrg: ericsson.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 May 2024 07:43:36.2833 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: b95395f7-336b-4b66-6d5e-08dc6cd7127b X-MS-Exchange-CrossTenant-Id: 92e84ceb-fbfd-47ab-be52-080c6b87953f X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=92e84ceb-fbfd-47ab-be52-080c6b87953f; Ip=[192.176.1.74]; Helo=[oa.msg.ericsson.com] X-MS-Exchange-CrossTenant-AuthSource: DB1PEPF000509E7.eurprd03.prod.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: AS8PR07MB7765 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 To reduce flow migration overhead, replace the array-based representation of which set of ports are bound to a particular queue by a multi-word bitset. Signed-off-by: Mattias Rönnblom --- drivers/event/dsw/dsw_evdev.c | 19 +++++++------------ drivers/event/dsw/dsw_evdev.h | 3 ++- drivers/event/dsw/dsw_event.c | 7 ++++--- 3 files changed, 13 insertions(+), 16 deletions(-) diff --git a/drivers/event/dsw/dsw_evdev.c b/drivers/event/dsw/dsw_evdev.c index ab0420b549..f3ca99e935 100644 --- a/drivers/event/dsw/dsw_evdev.c +++ b/drivers/event/dsw/dsw_evdev.c @@ -118,6 +118,7 @@ dsw_queue_setup(struct rte_eventdev *dev, uint8_t queue_id, queue->schedule_type = conf->schedule_type; } + rte_bitset_init(queue->serving_ports, DSW_MAX_PORTS); queue->num_serving_ports = 0; return 0; @@ -144,20 +145,16 @@ dsw_queue_release(struct rte_eventdev *dev __rte_unused, static void queue_add_port(struct dsw_queue *queue, uint16_t port_id) { - uint64_t port_mask = UINT64_C(1) << port_id; - - queue->serving_ports |= port_mask; + rte_bitset_set(queue->serving_ports, port_id); queue->num_serving_ports++; } static bool queue_remove_port(struct dsw_queue *queue, uint16_t port_id) { - uint64_t port_mask = UINT64_C(1) << port_id; - - if (queue->serving_ports & port_mask) { + if (rte_bitset_test(queue->serving_ports, port_id)) { queue->num_serving_ports--; - queue->serving_ports ^= port_mask; + rte_bitset_clear(queue->serving_ports, port_id); return true; } @@ -257,14 +254,12 @@ initial_flow_to_port_assignment(struct dsw_evdev *dsw) struct dsw_queue *queue = &dsw->queues[queue_id]; uint16_t flow_hash; for (flow_hash = 0; flow_hash < DSW_MAX_FLOWS; flow_hash++) { - uint8_t skip = - rte_rand_max(queue->num_serving_ports); + uint8_t skip = rte_rand_max(queue->num_serving_ports); uint8_t port_id; for (port_id = 0;; port_id++) { - uint64_t port_mask = UINT64_C(1) << port_id; - - if (queue->serving_ports & port_mask) { + if (rte_bitset_test(queue->serving_ports, + port_id)) { if (skip == 0) break; skip--; diff --git a/drivers/event/dsw/dsw_evdev.h b/drivers/event/dsw/dsw_evdev.h index 3a5989f148..0c40c45e46 100644 --- a/drivers/event/dsw/dsw_evdev.h +++ b/drivers/event/dsw/dsw_evdev.h @@ -7,6 +7,7 @@ #include +#include #include #include @@ -234,7 +235,7 @@ struct __rte_cache_aligned dsw_port { struct dsw_queue { uint8_t schedule_type; - uint64_t serving_ports; + RTE_BITSET_DECLARE(serving_ports, DSW_MAX_PORTS); uint16_t num_serving_ports; alignas(RTE_CACHE_LINE_SIZE) uint8_t flow_to_port_map[DSW_MAX_FLOWS]; diff --git a/drivers/event/dsw/dsw_event.c b/drivers/event/dsw/dsw_event.c index 23488d9030..b855f9ecf1 100644 --- a/drivers/event/dsw/dsw_event.c +++ b/drivers/event/dsw/dsw_event.c @@ -447,9 +447,8 @@ static bool dsw_is_serving_port(struct dsw_evdev *dsw, uint8_t port_id, uint8_t queue_id) { struct dsw_queue *queue = &dsw->queues[queue_id]; - uint64_t port_mask = UINT64_C(1) << port_id; - return queue->serving_ports & port_mask; + return rte_bitset_test(queue->serving_ports, port_id); } static bool @@ -571,7 +570,9 @@ dsw_schedule(struct dsw_evdev *dsw, uint8_t queue_id, uint16_t flow_hash) /* A single-link queue, or atomic/ordered/parallel but * with just a single serving port. */ - port_id = rte_bsf64(queue->serving_ports); + port_id = (uint8_t)rte_bitset_find_first_set( + queue->serving_ports, DSW_MAX_PORTS + ); DSW_LOG_DP(DEBUG, "Event with queue_id %d flow_hash %d is scheduled " "to port %d.\n", queue_id, flow_hash, port_id);