[1/6] eal: add bitset type

Message ID 20240809201440.590464-1-mattias.ronnblom@ericsson.com (mailing list archive)
State Superseded
Delegated to: David Marchand
Headers
Series [1/6] eal: add bitset type |

Checks

Context Check Description
ci/checkpatch success coding style OK
ci/loongarch-compilation warning apply patch failure
ci/iol-testing warning apply patch failure

Commit Message

Mattias Rönnblom Aug. 9, 2024, 8:14 p.m. UTC
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
<rte_bitmap.h> API may be a more appropriate choice.

Depends-on: series-32740 ("Improve EAL bit operations API")

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>

--

PATCH:
 * Update MAINTAINERS.
 * Update release notes.

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 <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>.
---
 MAINTAINERS                            |    6 +
 doc/api/doxy-api-index.md              |    1 +
 doc/guides/rel_notes/release_24_11.rst |   10 +
 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                    |    3 +
 8 files changed, 1112 insertions(+)
 create mode 100644 lib/eal/common/rte_bitset.c
 create mode 100644 lib/eal/include/rte_bitset.h
  

Comments

Mattias Rönnblom Aug. 20, 2024, 5:09 p.m. UTC | #1
On 2024-08-09 22:14, Mattias Rönnblom wrote:
> 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
> <rte_bitmap.h> API may be a more appropriate choice.
> 

Anyone else that might have time to have a look at this patch set?

I find these kind of bitsets incredibly useful, so I really want to get 
it into DPDK.

<snip>
  
Morten Brørup Sept. 2, 2024, 1:55 p.m. UTC | #2
> From: Mattias Rönnblom [mailto:mattias.ronnblom@ericsson.com]
> Sent: Friday, 9 August 2024 22.15
> 
> Introduce a set of functions and macros that operate on sets of bits,
> kept in arrays of 64-bit words.

This could be 32-bit words on 32 bit architectures. Just an idea.

> 
> 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.

RTE bitset uses size_t to index the bits.
This means that it supports very large bitsets.

If it is not supposed to support more than 2^32 bits, it could use uint32_t for indexing.
I don't know if it make any practical difference.

> 
> Depends-on: series-32740 ("Improve EAL bit operations API")
> 
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> 
> --

With or without considering the above ideas, this library is a good addition to DPDK.

For the series,
Acked-by: Morten Brørup <mb@smartsharesystems.com>
  
Mattias Rönnblom Sept. 2, 2024, 2:46 p.m. UTC | #3
On 2024-09-02 15:55, Morten Brørup wrote:
>> From: Mattias Rönnblom [mailto:mattias.ronnblom@ericsson.com]
>> Sent: Friday, 9 August 2024 22.15
>>
>> Introduce a set of functions and macros that operate on sets of bits,
>> kept in arrays of 64-bit words.
> 
> This could be 32-bit words on 32 bit architectures. Just an idea.
> 

The use of "unsigned long" instead of "uint64_t" as the type has been 
discussed before on the list.

I prefer uint64_t because it's less to type and the performance benefits 
of using "unsigned long" on 32-bit ISAs likely are small. That said, I 
have no strong opinion on the subject.

>>
>> 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.
> 
> RTE bitset uses size_t to index the bits.
> This means that it supports very large bitsets.
> 

Yes, it does, although I can't say I see a use case for enormous 
bitsets. But, who knows.

I used size_t in an attempt to slightly improve readability.

Performance wise, it does not matter, at least in the tests I did. I 
don't know if it ever could, considering these functions will pretty 
much always be inlined.

> If it is not supposed to support more than 2^32 bits, it could use uint32_t for indexing.
> I don't know if it make any practical difference.
> 
>>
>> Depends-on: series-32740 ("Improve EAL bit operations API")
>>
>> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
>>
>> --
> 
> With or without considering the above ideas, this library is a good addition to DPDK.
> 
> For the series,
> Acked-by: Morten Brørup <mb@smartsharesystems.com>
>
  
Mattias Rönnblom Sept. 2, 2024, 2:49 p.m. UTC | #4
On 2024-09-02 15:55, Morten Brørup wrote:

>> --> 
> With or without considering the above ideas, this library is a good addition to DPDK.
>  > For the series,
> Acked-by: Morten Brørup <mb@smartsharesystems.com>
> 

Thomas and David, what else need I do to get this merged?

I have the same question for the bitops patch set.

Thanks.
  
Tyler Retzlaff Sept. 12, 2024, 4:51 a.m. UTC | #5
On Fri, Aug 09, 2024 at 10:14:35PM +0200, Mattias R??nnblom wrote:
> 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
> <rte_bitmap.h> API may be a more appropriate choice.
> 
> Depends-on: series-32740 ("Improve EAL bit operations API")
> 
> Signed-off-by: Mattias R??nnblom <mattias.ronnblom@ericsson.com>
> 
> --

Acked-by: Tyler Retzlaff <roretzla@linux.microsoft.com>
  

Patch

diff --git a/MAINTAINERS b/MAINTAINERS
index c5a703b5c0..00ad6fd318 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -260,6 +260,12 @@  M: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
 F: lib/eal/include/rte_bitmap.h
 F: app/test/test_bitmap.c
 
+Bitset
+M: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
+F: lib/eal/include/rte_bitset.h
+F: lib/eal/include/rte_bitset.c
+F: app/test/test_bitset.c
+
 MCSlock
 M: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
 F: lib/eal/include/rte_mcslock.h
diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md
index f9f0300126..abd44b1861 100644
--- a/doc/api/doxy-api-index.md
+++ b/doc/api/doxy-api-index.md
@@ -174,6 +174,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/doc/guides/rel_notes/release_24_11.rst b/doc/guides/rel_notes/release_24_11.rst
index 3111b1e4c0..89716defac 100644
--- a/doc/guides/rel_notes/release_24_11.rst
+++ b/doc/guides/rel_notes/release_24_11.rst
@@ -73,6 +73,16 @@  New Features
   based macros (for C) and function overloading (in C++ translation
   units).
 
+* **Added multi-word bitset API.**
+
+  A new multi-word bitset API has been introduced in the EAL. The RTE
+  bitset is optimized for scenarios where the bitset size exceeds the
+  capacity of a single word (e.g., larger than 64 bits), but is not
+  large enough to justify the overhead and complexity of the more
+  scalable, yet slower, <rte_bitmap.h> API. This addition provides an
+  efficient and straightforward alternative for handling bitsets of
+  intermediate sizes.
+
 Removed Items
 -------------
 
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..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 <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))
+#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 <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.
+ *
+ * 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 e3ff412683..f493cd1ca7 100644
--- a/lib/eal/version.map
+++ b/lib/eal/version.map
@@ -396,6 +396,9 @@  EXPERIMENTAL {
 
 	# added in 24.03
 	rte_vfio_get_device_info; # WINDOWS_NO_EXPORT
+
+	# added in 24.11
+	rte_bitset_to_str;
 };
 
 INTERNAL {