From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <dev-bounces@dpdk.org>
Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124])
by inbox.dpdk.org (Postfix) with ESMTP id 7542E43A1E;
Wed, 31 Jan 2024 14:21:13 +0100 (CET)
Received: from mails.dpdk.org (localhost [127.0.0.1])
by mails.dpdk.org (Postfix) with ESMTP id 5982F402D0;
Wed, 31 Jan 2024 14:21:13 +0100 (CET)
Received: from EUR03-AM7-obe.outbound.protection.outlook.com
(mail-am7eur03on2087.outbound.protection.outlook.com [40.107.105.87])
by mails.dpdk.org (Postfix) with ESMTP id 21388402A1
for <dev@dpdk.org>; Wed, 31 Jan 2024 14:21:11 +0100 (CET)
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none;
b=UFDVX1fhMj2b6vcSFAVh3/97cRzTtyvI2DXYfnKYODjL2ssSve4JqjSWwEtEtc2vO0PW+JxEHwQU59EsEMlNlSm2p56IgGpmMPoEMYPvNXT8xAjQ58DaZzEJYkQYjF0zhPgdbocRj7R2EmXcTVhRj/rH+exteTntCtmzuIkccCqa2LdDk2YeaUyLgzjMAUmqMCOO/JoCNTX04dAJCOWXSgDLdTGLNSgG/ji7RzDSy6cmWLQK/eR3BfEnxx+ZPXqcCuajH4WwOWIZzpdMsgpxCieEQ4m1h+u6HP9ltrvUQn/h7jVW3gfHEyrnE9RYsER2sh/NlYMjLRaQkvKebvkCIg==
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=/+SS1YcQ4iThvA9ZYijAXCAxQiyikTcxKzfkAQ0ryjw=;
b=Ff2FDmtgJMJglGOHQBNts0i78k3tvJkjsVw6pkm3Jt88SAO0qZ7ub5yEdX5zD+xLOZS5Ir1CeDunZc23qBJ6CfWp/dnfeo1uNlcG0NyZ1VRjm/MEE/NSnvQSOFTWImpKyrI4VIjJaEhsyFUGJbemgnpqERbuW4B5ms45TxpUmtgJcHjX6MRyxdjgsqnyDEgOcyuQp5K8X5hMlmaLlnbK+qb/dSOiJT5xgh8wWArtjOFH/4r0rdArcRATbdQYIO7xLLdUnsHJjwFvH8L1H3lPhT6+uXi7V0+9M9zmSTqn14XAHYxCJZujqmEZ6z9XglsbVTBN5QY9rRlBeMeDcw8ouA==
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=/+SS1YcQ4iThvA9ZYijAXCAxQiyikTcxKzfkAQ0ryjw=;
b=VwXnBc9eYLrylrVkDT9IOcQDmU1Ezqq3uI8UaHKOuQcxa9/vxfSe0ctUdW2jUJKlHIEYTriocek9kVWqQZZJ0Vat7skqHOIC4GVhKjp8lqQ99Z8eSWnJc9g0FsnZvj8m1y2V3OBg0cmjugHPw8TZ2M7DtQ5Nwcxhqtd7at2856+8La8ge82Rj3pA3fy6dJjlvedQldDBPOZ+JEEnnUrBZdXHrAsCG/3znHSfSRq+W6KARomNW/luFKtUtW4INI0W+EsesgLhKBEA6gwv4vWO802DuWcxWgujnNkZPMKqSPn/9YIYd4QTK/RkRUIm8v6CMlMH1UEJ0G+klgC0loyURw==
Received: from DB9PR06CA0002.eurprd06.prod.outlook.com (2603:10a6:10:1db::7)
by AM7PR07MB6964.eurprd07.prod.outlook.com (2603:10a6:20b:1be::5) with
Microsoft SMTP Server (version=TLS1_2,
cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7228.34; Wed, 31 Jan
2024 13:21:07 +0000
Received: from DB3PEPF0000885F.eurprd02.prod.outlook.com
(2603:10a6:10:1db:cafe::7f) by DB9PR06CA0002.outlook.office365.com
(2603:10a6:10:1db::7) with Microsoft SMTP Server (version=TLS1_2,
cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7249.23 via Frontend
Transport; Wed, 31 Jan 2024 13:21:07 +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
DB3PEPF0000885F.mail.protection.outlook.com (10.167.242.10) with Microsoft
SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id
15.20.7249.19 via Frontend Transport; Wed, 31 Jan 2024 13:21:07 +0000
Received: from seliicinfr00050.seli.gic.ericsson.se (153.88.142.248) by
smtp-central.internal.ericsson.com (100.87.178.61) with Microsoft SMTP Server
id 15.2.1258.12; Wed, 31 Jan 2024 14:21:06 +0100
Received: from breslau.. (seliicwb00002.seli.gic.ericsson.se [10.156.25.100])
by seliicinfr00050.seli.gic.ericsson.se (Postfix) with ESMTP id
1F9A21C006A; Wed, 31 Jan 2024 14:21:06 +0100 (CET)
From: =?UTF-8?q?Mattias=20R=C3=B6nnblom?= <mattias.ronnblom@ericsson.com>
To: <dev@dpdk.org>
CC: <hofors@lysator.liu.se>, =?UTF-8?q?Morten=20Br=C3=B8rup?=
<mb@smartsharesystems.com>, Tyler Retzlaff <roretzla@linux.microsoft.com>,
=?UTF-8?q?Mattias=20R=C3=B6nnblom?= <mattias.ronnblom@ericsson.com>
Subject: [RFC v3] eal: add bitset type
Date: Wed, 31 Jan 2024 14:13:01 +0100
Message-ID: <20240131131301.418361-1-mattias.ronnblom@ericsson.com>
X-Mailer: git-send-email 2.34.1
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
X-EOPAttributedMessage: 0
X-MS-PublicTrafficType: Email
X-MS-TrafficTypeDiagnostic: DB3PEPF0000885F:EE_|AM7PR07MB6964:EE_
X-MS-Office365-Filtering-Correlation-Id: 11ac6891-da73-411e-29da-08dc225f7bba
X-MS-Exchange-SenderADCheck: 1
X-MS-Exchange-AntiSpam-Relay: 0
X-Microsoft-Antispam: BCL:0;
X-Microsoft-Antispam-Message-Info: S4DtcKntX3f/jApusEcu7vVYIzojlpCWKRLnNDVyMVCET+7CYKVgb/jwIcjZMX45TrRMQ4Yo5teUsHhmPZVtzpzInpvtwvWo/LPmE9rEjNisp1fMAWiDOcVLLr2TAu5U56++GypkV4xHc2OVJfJFoV3TIrgKLaNoIvBW6sLVoMAALEoGFEuS02eijyat0fewNU+1LnfsrjdgSCTIlvtRXOGfQNbNPcmCAiLMscNXZbLf5GoJX7Gw1xB0M/oKZFWLeFA39DFN0mzaX6TtLjL74J3nCpq/r/4Urjjn0IGFGJwpwmOL6WhDG/xSrMVRxhy7w4BEKdzpwQlTQhoRUt6CEr/RpyFJlIVYMZlxSwVWj95ruS1r3E7wLP7EsUyPuOe1yJ05wQ+kCAML0x5ln40J/iJvaxpxFXihs7cEdzaHk4Jz8R1RV+VW045x+SPfwzw+HT1oKMn85BzDck+amnX+bSHjEIRDHmXwJjWMoeqsIdi6O/EYQtj0FH0I3kc7E1NBizOK05Edk+JMVTCjT68OGIIqLN8RMJ3/6OwFYyAZcNxdfbHizWdIbGMiqZhj7sES7BNU/GSPtBjRGgDvyJrLQFZnvOnlWzfeqZ0chYTSMIFI4pMd6T/7wOv/zUL54goFLbKc8Lbo5+c8vueSuYdS2evLzxTrdt2XG2pSBwAxfdiYPY2o2ABgoX87Qpaa9BK9QJ4okz3olMW7EEiTy/DtWHNu/lZjrMFVPY5mzGgIl4CixTJr2qYRkTlBfVZZjuPj1PSquX5B2rIeBqJLJq9zlZ1ls/iDpE4rRR2W7sQ3R038I+WgwqJLNTTRVwf2sJV/
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)(4636009)(396003)(346002)(136003)(39860400002)(376002)(230173577357003)(230273577357003)(230922051799003)(64100799003)(82310400011)(186009)(451199024)(1800799012)(36840700001)(40470700004)(46966006)(40480700001)(40460700003)(41300700001)(83380400001)(86362001)(82960400001)(36756003)(82740400003)(7636003)(356005)(36860700001)(66574015)(47076005)(2616005)(107886003)(1076003)(6266002)(336012)(26005)(2906002)(30864003)(478600001)(70206006)(6916009)(70586007)(316002)(54906003)(8676002)(4326008)(8936002)(5660300002)(6666004)(21314003)(579004);
DIR:OUT; SFP:1101;
X-OriginatorOrg: ericsson.com
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 31 Jan 2024 13:21:07.2022 (UTC)
X-MS-Exchange-CrossTenant-Network-Message-Id: 11ac6891-da73-411e-29da-08dc225f7bba
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: DB3PEPF0000885F.eurprd02.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Anonymous
X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM7PR07MB6964
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://mails.dpdk.org/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://mails.dpdk.org/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=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 elements.
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
<rte_bitmap.h> API may be a more appropriate choice.
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 <sys/types.h> with <stddef.h> include, to properly get
size_t typedef.
* Add <rte_compat.h> to get __rte_experimental in <rte_bitset.h>.
Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
app/test/meson.build | 1 +
app/test/test_bitset.c | 645 +++++++++++++++++++++++++
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 | 884 +++++++++++++++++++++++++++++++++++
lib/eal/version.map | 3 +
7 files changed, 1564 insertions(+)
create mode 100644 app/test/test_bitset.c
create mode 100644 lib/eal/common/rte_bitset.c
create mode 100644 lib/eal/include/rte_bitset.h
diff --git a/app/test/meson.build b/app/test/meson.build
index dcc93f4a43..e218be11d8 100644
--- a/app/test/meson.build
+++ b/app/test/meson.build
@@ -32,6 +32,7 @@ source_file_deps = {
'test_bitcount.c': [],
'test_bitmap.c': [],
'test_bitops.c': [],
+ 'test_bitset.c': [],
'test_bitratestats.c': ['metrics', 'bitratestats', 'ethdev'] + sample_packet_forward_deps,
'test_bpf.c': ['bpf', 'net'],
'test_byteorder.c': [],
diff --git a/app/test/test_bitset.c b/app/test/test_bitset.c
new file mode 100644
index 0000000000..688349b03b
--- /dev/null
+++ b/app/test/test_bitset.c
@@ -0,0 +1,645 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2023 Ericsson AB
+ */
+
+#include <stdlib.h>
+#include <inttypes.h>
+
+#include <rte_random.h>
+
+#include <rte_bitset.h>
+
+#include "test.h"
+
+#define MAGIC UINT64_C(0xdeadbeefdeadbeef)
+
+static void
+rand_buf(void *buf, size_t n)
+{
+ size_t i;
+
+ for (i = 0; i < n; i++)
+ ((char *)buf)[i] = (char)rte_rand();
+}
+
+static uint64_t *
+alloc_bitset(size_t size)
+{
+ uint64_t *p;
+
+ p = malloc(RTE_BITSET_SIZE(size) + 2 * sizeof(uint64_t));
+
+ if (p == NULL)
+ rte_panic("Unable to allocate memory\n");
+
+ rand_buf(&p[0], RTE_BITSET_SIZE(size));
+
+ p[0] = MAGIC;
+ p[RTE_BITSET_NUM_WORDS(size) + 1] = MAGIC;
+
+ return p + 1;
+}
+
+
+static int
+free_bitset(uint64_t *bitset, size_t size)
+{
+ uint64_t *p;
+
+ p = bitset - 1;
+
+ if (p[0] != MAGIC)
+ return TEST_FAILED;
+
+ if (p[RTE_BITSET_NUM_WORDS(size) + 1] != MAGIC)
+ return TEST_FAILED;
+
+ free(p);
+
+ return TEST_SUCCESS;
+}
+
+static bool
+rand_bool(void)
+{
+ return rte_rand_max(2);
+}
+
+static void
+rand_bool_ary(bool *ary, size_t len)
+{
+ size_t i;
+
+ for (i = 0; i < len; i++)
+ ary[i] = rand_bool();
+}
+
+static int
+test_test_set_size(size_t size)
+{
+ size_t i;
+ bool reference[size];
+ uint64_t *bitset;
+
+ rand_bool_ary(reference, size);
+
+ bitset = alloc_bitset(size);
+
+ if (bitset == NULL)
+ return TEST_FAILED;
+
+ rte_bitset_init(bitset, size);
+
+ for (i = 0; i < size; i++) {
+ if (reference[i])
+ rte_bitset_set(bitset, i);
+ else
+ rte_bitset_clear(bitset, i);
+ }
+
+ for (i = 0; i < size; i++)
+ if (reference[i] != rte_bitset_test(bitset, i))
+ return TEST_FAILED;
+
+ if (free_bitset(bitset, size) != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ return TEST_SUCCESS;
+}
+
+#define RAND_ITERATIONS (10000)
+#define RAND_SET_MAX_SIZE (1000)
+
+static int
+test_test_set(void)
+{
+ size_t i;
+
+ for (i = 0; i < RAND_ITERATIONS; i++) {
+ size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
+
+ if (test_test_set_size(size) != TEST_SUCCESS)
+ return TEST_FAILED;
+ }
+
+ return TEST_SUCCESS;
+}
+
+static ssize_t
+find(const bool *ary, size_t num_bools, size_t start, size_t len, bool set)
+{
+ size_t i;
+
+ for (i = 0; i < len; i++) {
+ ssize_t idx = (start + i) % num_bools;
+
+ if (ary[idx] == set)
+ return idx;
+ }
+
+ return -1;
+}
+
+static ssize_t
+find_set(const bool *ary, size_t num_bools, size_t start, size_t len)
+{
+ return find(ary, num_bools, start, len, true);
+}
+
+static ssize_t
+find_clear(const bool *ary, size_t num_bools, size_t start, size_t len)
+{
+ return find(ary, num_bools, start, len, false);
+}
+
+#define FFS_ITERATIONS (100)
+
+static int
+test_find_size(size_t size, bool set)
+{
+ uint64_t *bitset;
+ bool reference[size];
+ size_t i;
+
+ bitset = alloc_bitset(size);
+
+ if (bitset == NULL)
+ return TEST_FAILED;
+
+ rte_bitset_init(bitset, size);
+
+ for (i = 0; i < size; i++) {
+ bool bit = rand_bool();
+ reference[i] = bit;
+
+ if (bit)
+ rte_bitset_set(bitset, i);
+ else /* redundant, still useful for testing */
+ rte_bitset_clear(bitset, i);
+ }
+
+ for (i = 0; i < FFS_ITERATIONS; i++) {
+ size_t start_bit = rte_rand_max(size);
+ size_t len = rte_rand_max(size + 1);
+ bool full_range = len == size && start_bit == 0;
+ bool wraps = start_bit + len > size;
+ ssize_t rc;
+
+ if (set) {
+ if (full_range && rand_bool())
+ rc = rte_bitset_find_first_set(bitset,
+ size);
+ else if (wraps || rand_bool()) {
+ rc = rte_bitset_find_set_wrap(bitset, size,
+ start_bit, len);
+
+ } else
+ rc = rte_bitset_find_set(bitset, size,
+ start_bit, len);
+
+ if (rc != find_set(reference, size, start_bit,
+ len))
+ return TEST_FAILED;
+ } else {
+ if (full_range && rand_bool())
+ rc = rte_bitset_find_first_clear(bitset,
+ size);
+ else if (wraps || rand_bool())
+ rc = rte_bitset_find_clear_wrap(bitset,
+ size,
+ start_bit, len);
+ else
+ rc = rte_bitset_find_clear(bitset, size,
+ start_bit, len);
+
+ if (rc != find_clear(reference, size, start_bit,
+ len))
+ return TEST_FAILED;
+ }
+
+ }
+
+ if (free_bitset(bitset, size) != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ return TEST_SUCCESS;
+}
+
+static int
+test_find_set_size(size_t size)
+{
+ return test_find_size(size, true);
+}
+
+static int
+test_find_clear_size(size_t size)
+{
+ return test_find_size(size, false);
+}
+
+static int
+test_find(void)
+{
+ size_t i;
+
+ for (i = 0; i < RAND_ITERATIONS; i++) {
+ size_t size = 2 + rte_rand_max(RAND_SET_MAX_SIZE - 2);
+
+ if (test_find_set_size(size) != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_find_clear_size(size) != TEST_SUCCESS)
+ return TEST_FAILED;
+ }
+
+ return TEST_SUCCESS;
+}
+
+static int
+record_match(ssize_t match_idx, size_t size, int *calls)
+{
+ if (match_idx < 0 || (size_t)match_idx >= size)
+ return TEST_FAILED;
+
+ calls[match_idx]++;
+
+ return TEST_SUCCESS;
+}
+
+static int
+test_foreach_size(ssize_t size, bool may_wrap, bool set)
+{
+ bool reference[size];
+ int calls[size];
+ uint64_t *bitset;
+ ssize_t i;
+ ssize_t start_bit;
+ ssize_t len;
+ bool full_range;
+ size_t total_calls = 0;
+
+ rand_bool_ary(reference, size);
+
+ bitset = alloc_bitset(size);
+
+ if (bitset == NULL)
+ return TEST_FAILED;
+
+ memset(calls, 0, sizeof(calls));
+
+ start_bit = rte_rand_max(size);
+ len = may_wrap ? rte_rand_max(size + 1) :
+ rte_rand_max(size - start_bit + 1);
+
+ rte_bitset_init(bitset, size);
+
+ /* random data in the unused bits should not matter */
+ rand_buf(bitset, RTE_BITSET_SIZE(size));
+
+ for (i = start_bit; i < start_bit + len; i++) {
+ size_t idx = i % size;
+
+ if (reference[idx])
+ rte_bitset_set(bitset, idx);
+ else
+ rte_bitset_clear(bitset, idx);
+
+ if (rte_bitset_test(bitset, idx) != reference[idx])
+ return TEST_FAILED;
+ }
+
+ full_range = (len == size && start_bit == 0);
+
+ /* XXX: verify iteration order as well */
+ if (set) {
+ if (full_range && rand_bool()) {
+ RTE_BITSET_FOREACH_SET(i, bitset, size) {
+ if (record_match(i, size, calls) !=
+ TEST_SUCCESS)
+ return TEST_FAILED;
+ }
+ } else if (may_wrap) {
+ RTE_BITSET_FOREACH_SET_WRAP(i, bitset, size,
+ start_bit, len) {
+ if (record_match(i, size, calls) !=
+ TEST_SUCCESS) {
+ printf("failed\n");
+ return TEST_FAILED;
+ }
+ }
+ } else {
+ RTE_BITSET_FOREACH_SET_RANGE(i, bitset, size,
+ start_bit, len) {
+ if (record_match(i, size, calls) !=
+ TEST_SUCCESS)
+ return TEST_FAILED;
+ }
+ }
+ } else {
+ if (full_range && rand_bool()) {
+ RTE_BITSET_FOREACH_CLEAR(i, bitset, size)
+ if (record_match(i, size, calls) !=
+ TEST_SUCCESS)
+ return TEST_FAILED;
+ } else if (may_wrap) {
+ RTE_BITSET_FOREACH_CLEAR_WRAP(i, bitset, size,
+ start_bit, len) {
+ if (record_match(i, size, calls) !=
+ TEST_SUCCESS)
+ return TEST_FAILED;
+ }
+ } else {
+ RTE_BITSET_FOREACH_CLEAR_RANGE(i, bitset, size,
+ start_bit, len)
+ if (record_match(i, size, calls) !=
+ TEST_SUCCESS)
+ return TEST_FAILED;
+ }
+ }
+
+ for (i = 0; i < len; i++) {
+ size_t idx = (start_bit + i) % size;
+
+ if (reference[idx] == set && calls[idx] != 1) {
+ printf("bit %zd shouldn't have been found %d "
+ "times\n", idx, calls[idx]);
+ return TEST_FAILED;
+ }
+
+ if (reference[idx] != set && calls[idx] != 0) {
+ puts("bar");
+ return TEST_FAILED;
+ }
+
+ total_calls += calls[idx];
+ }
+
+ if (full_range) {
+ size_t count;
+
+ count = set ? rte_bitset_count_set(bitset, size) :
+ rte_bitset_count_clear(bitset, size);
+
+ if (count != total_calls)
+ return TEST_FAILED;
+ }
+
+ if (free_bitset(bitset, size) != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ return TEST_SUCCESS;
+}
+
+static int
+test_foreach(void)
+{
+ size_t i;
+
+ for (i = 0; i < RAND_ITERATIONS; i++) {
+ size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
+
+ if (test_foreach_size(size, false, true) != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_foreach_size(size, false, false) != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_foreach_size(size, true, true) != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_foreach_size(size, true, false) != TEST_SUCCESS)
+ return TEST_FAILED;
+ }
+
+ return TEST_SUCCESS;
+}
+
+static int
+test_count_size(size_t size)
+{
+ uint64_t *bitset;
+
+ bitset = alloc_bitset(size);
+
+ if (bitset == NULL)
+ return TEST_FAILED;
+
+ rte_bitset_init(bitset, size);
+
+ if (rte_bitset_count_set(bitset, size) != 0)
+ return TEST_FAILED;
+
+ if (rte_bitset_count_clear(bitset, size) != size)
+ return TEST_FAILED;
+
+ rte_bitset_set_all(bitset, size);
+
+ if (rte_bitset_count_set(bitset, size) != size)
+ return TEST_FAILED;
+
+ if (rte_bitset_count_clear(bitset, size) != 0)
+ return TEST_FAILED;
+
+ rte_bitset_clear_all(bitset, size);
+
+ if (rte_bitset_count_set(bitset, size) != 0)
+ return TEST_FAILED;
+
+ if (rte_bitset_count_clear(bitset, size) != size)
+ return TEST_FAILED;
+
+ rte_bitset_set(bitset, rte_rand_max(size));
+
+ if (rte_bitset_count_set(bitset, size) != 1)
+ return TEST_FAILED;
+
+ if (rte_bitset_count_clear(bitset, size) != (size - 1))
+ return TEST_FAILED;
+
+ rte_bitset_clear_all(bitset, size);
+ if (rte_bitset_count_set(bitset, size) != 0)
+ return TEST_FAILED;
+ if (rte_bitset_count_clear(bitset, size) != size)
+ return TEST_FAILED;
+
+ rte_bitset_set_all(bitset, size);
+ if (rte_bitset_count_set(bitset, size) != size)
+ return TEST_FAILED;
+ if (rte_bitset_count_clear(bitset, size) != 0)
+ return TEST_FAILED;
+
+ if (free_bitset(bitset, size) != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ return TEST_SUCCESS;
+}
+
+static int
+test_count(void)
+{
+ size_t i;
+
+ if (test_count_size(128) != TEST_SUCCESS)
+ return TEST_FAILED;
+ if (test_count_size(1) != TEST_SUCCESS)
+ return TEST_FAILED;
+ if (test_count_size(63) != TEST_SUCCESS)
+ return TEST_FAILED;
+ if (test_count_size(64) != TEST_SUCCESS)
+ return TEST_FAILED;
+ if (test_count_size(65) != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ for (i = 0; i < RAND_ITERATIONS; i++) {
+ size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
+
+ if (test_count_size(size) != TEST_SUCCESS)
+ return TEST_FAILED;
+ }
+
+ return TEST_SUCCESS;
+}
+
+#define GEN_DECLARE(size) \
+ { \
+ RTE_BITSET_DECLARE(bitset, size); \
+ size_t idx; \
+ \
+ idx = rte_rand_max(size); \
+ rte_bitset_init(bitset, size); \
+ \
+ rte_bitset_set(bitset, idx); \
+ if (!rte_bitset_test(bitset, idx)) \
+ return TEST_FAILED; \
+ if (rte_bitset_count_set(bitset, size) != 1) \
+ return TEST_FAILED; \
+ return TEST_SUCCESS; \
+ }
+
+static int
+test_define(void)
+{
+ GEN_DECLARE(1);
+ GEN_DECLARE(64);
+ GEN_DECLARE(65);
+ GEN_DECLARE(4097);
+}
+
+static int
+test_equal(void)
+{
+ const size_t size = 100;
+ RTE_BITSET_DECLARE(bitset_a, size);
+ RTE_BITSET_DECLARE(bitset_b, size);
+
+ rand_buf(bitset_a, RTE_BITSET_SIZE(size));
+ rand_buf(bitset_b, RTE_BITSET_SIZE(size));
+
+ rte_bitset_init(bitset_a, size);
+ rte_bitset_init(bitset_b, size);
+
+ rte_bitset_set(bitset_a, 9);
+ rte_bitset_set(bitset_b, 9);
+ rte_bitset_set(bitset_a, 90);
+ rte_bitset_set(bitset_b, 90);
+
+ if (!rte_bitset_equal(bitset_a, bitset_b, size))
+ return TEST_FAILED;
+
+ /* set unused bit, which should be ignored */
+ rte_bitset_set(&bitset_a[1], 60);
+
+ if (!rte_bitset_equal(bitset_a, bitset_b, size))
+ return TEST_FAILED;
+
+ return TEST_SUCCESS;
+}
+
+static int
+test_copy(void)
+{
+ const size_t size = 100;
+ RTE_BITSET_DECLARE(bitset_a, size);
+ RTE_BITSET_DECLARE(bitset_b, size);
+
+ rand_buf(bitset_a, RTE_BITSET_SIZE(size));
+ rand_buf(bitset_b, RTE_BITSET_SIZE(size));
+
+ if (rte_bitset_equal(bitset_a, bitset_b, size))
+ return TEST_FAILED;
+
+ rte_bitset_copy(bitset_a, bitset_b, size);
+
+ if (!rte_bitset_equal(bitset_a, bitset_b, size))
+ return TEST_FAILED;
+
+ return TEST_SUCCESS;
+}
+
+static int
+test_to_str(void)
+{
+ char buf[1024];
+ RTE_BITSET_DECLARE(bitset, 128);
+
+ rte_bitset_init(bitset, 128);
+ rte_bitset_set(bitset, 1);
+
+ if (rte_bitset_to_str(bitset, 2, buf, 3) != 3)
+ return TEST_FAILED;
+ if (strcmp(buf, "10") != 0)
+ return TEST_FAILED;
+
+ rte_bitset_set(bitset, 0);
+
+ if (rte_bitset_to_str(bitset, 1, buf, sizeof(buf)) != 2)
+ return TEST_FAILED;
+ if (strcmp(buf, "1") != 0)
+ return TEST_FAILED;
+
+ rte_bitset_init(bitset, 99);
+ rte_bitset_set(bitset, 98);
+
+ if (rte_bitset_to_str(bitset, 99, buf, sizeof(buf)) != 100)
+ return TEST_FAILED;
+
+ if (buf[0] != '1' || strchr(&buf[1], '1') != NULL)
+ return TEST_FAILED;
+
+ if (rte_bitset_to_str(bitset, 128, buf, 64) != -EINVAL)
+ return TEST_FAILED;
+
+ return TEST_SUCCESS;
+}
+
+static int
+test_bitset(void)
+{
+ if (test_test_set() != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_find() != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_foreach() != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_count() != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_define() != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_equal() != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_copy() != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ if (test_to_str() != TEST_SUCCESS)
+ return TEST_FAILED;
+
+ return TEST_SUCCESS;
+}
+
+REGISTER_FAST_TEST(bitset_autotest, true, true, test_bitset);
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 <errno.h>
+
+#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..24c6ec3703
--- /dev/null
+++ b/lib/eal/include/rte_bitset.h
@@ -0,0 +1,884 @@
+/* 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 <limits.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include <rte_bitops.h>
+#include <rte_branch_prediction.h>
+#include <rte_common.h>
+#include <rte_compat.h>
+#include <rte_debug.h>
+#include <rte_memcpy.h>
+
+#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))
+
+/**
+ * @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)]
+
+/* XXX: should one include flags here and use to avoid a comparison? */
+/* XXX: would this be better off as a function? */
+
+#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 <tt>const uint64_t *</tt> 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 <tt>const uint64_t *</tt> 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 <tt>const uint64_t *</tt> 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 <tt>const uint64_t *</tt> 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.
+ *
+ * Set a bit in the bitset.
+ *
+ * Bits are numbered from 0 to (size - 1) (inclusive).
+ *
+ * @param bitset
+ * A pointer to the array 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)
+{
+ size_t word;
+ size_t offset;
+ uint64_t mask;
+
+ word = __RTE_BITSET_WORD_IDX(bit_num);
+ offset = __RTE_BITSET_BIT_OFFSET(bit_num);
+ mask = UINT64_C(1) << offset;
+
+ bitset[word] |= mask;
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Clear a bit in the bitset.
+ *
+ * Bits are numbered 0 to (size - 1) (inclusive).
+ *
+ * @param bitset
+ * A pointer to the array 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)
+{
+ size_t word;
+ size_t offset;
+ uint64_t mask;
+
+ word = __RTE_BITSET_WORD_IDX(bit_num);
+ offset = __RTE_BITSET_BIT_OFFSET(bit_num);
+ mask = ~(UINT64_C(1) << offset);
+
+ bitset[word] &= mask;
+}
+
+/**
+ * @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.
+ *
+ * @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;
+ uint64_t unused_mask;
+
+ /*
+ * 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]);
+
+ unused_mask = UINT64_MAX >> __RTE_BITSET_UNUSED(size);
+ total += rte_popcount64(bitset[i] & unused_mask);
+
+ 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);
+}
+
+/**
+ * @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)
+{
+ size_t word;
+ size_t offset;
+
+ word = __RTE_BITSET_WORD_IDX(bit_num);
+ offset = __RTE_BITSET_BIT_OFFSET(bit_num);
+
+ return (bitset[word] >> offset) & 1;
+}
+
+#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 dst_bitset and @c src_bitset, and store the results 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_or(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.
+ *
+ * Bitwise and two bitsets.
+ *
+ * Perform a bitwise AND operation on all bits in the two equal-size
+ * bitsets @c dst_bitset and @c src_bitset, and store the results 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_and(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.
+ *
+ * Bitwise xor two bitsets.
+ *
+ * Perform a bitwise XOR operation on all bits in the two equal-size
+ * bitsets @c dst_bitset and @c src_bitset, and store the results 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_xor(uint64_t *__rte_restrict dst_bitset,
+ const uint64_t *__rte_restrict 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.
+ *
+ * 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. 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 5e0cd47c82..639ccfe4b0 100644
--- a/lib/eal/version.map
+++ b/lib/eal/version.map
@@ -393,6 +393,9 @@ EXPERIMENTAL {
# added in 23.07
rte_memzone_max_get;
rte_memzone_max_set;
+
+ # added in 24.03
+ rte_bitset_to_str;
};
INTERNAL {
--
2.34.1