On Tue, Feb 28, 2023 at 10:39:15AM +0100, Mattias Rönnblom wrote:
> 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.
>
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> ---
...
> diff --git a/lib/eal/include/rte_bitset.h b/lib/eal/include/rte_bitset.h
> new file mode 100644
> index 0000000000..e333e527e5
> --- /dev/null
> +++ b/lib/eal/include/rte_bitset.h
> @@ -0,0 +1,878 @@
> +/* 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 <stdint.h>
> +#include <sys/types.h>
windows has no sys/types.h if there is a shim being picked up somewhere
portable code shouldn't depend on sys/types.h
> +
> +#include <rte_branch_prediction.h>
> +#include <rte_common.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 sucessive 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 sucessive 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 sucessive 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.
> + *
> + * @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 += __builtin_popcountll(bitset[i]);
> +
> + unused_mask = UINT64_MAX >> __RTE_BITSET_UNUSED(size);
> + total += __builtin_popcountll(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)
^^ seems like the intent here is for this to be internal (not part of
public api) i wonder do we have to mark it __rte_experimental?
or better can we prevent visibility / consumption outside of the
inline functions in this header?
> +{
> + 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;
> +
> +}
> +
On 2023-02-28 19:46, Tyler Retzlaff wrote:
> On Tue, Feb 28, 2023 at 10:39:15AM +0100, Mattias Rönnblom wrote:
>> 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.
>>
>> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
>> ---
>
> ...
>
>> diff --git a/lib/eal/include/rte_bitset.h b/lib/eal/include/rte_bitset.h
>> new file mode 100644
>> index 0000000000..e333e527e5
>> --- /dev/null
>> +++ b/lib/eal/include/rte_bitset.h
>> @@ -0,0 +1,878 @@
>> +/* 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 <stdint.h>
>> +#include <sys/types.h>
>
> windows has no sys/types.h if there is a shim being picked up somewhere
> portable code shouldn't depend on sys/types.h
>
That include was a misdirected attempt to get the 'size_t' definition. I
will replaced it with <stddef.h>. Thanks.
>> +
>> +#include <rte_branch_prediction.h>
>> +#include <rte_common.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 sucessive 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 sucessive 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 sucessive 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.
>> + *
>> + * @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 += __builtin_popcountll(bitset[i]);
>> +
>> + unused_mask = UINT64_MAX >> __RTE_BITSET_UNUSED(size);
>> + total += __builtin_popcountll(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)
>
> ^^ seems like the intent here is for this to be internal (not part of
> public api) i wonder do we have to mark it __rte_experimental?
>
> or better can we prevent visibility / consumption outside of the
> inline functions in this header?
>
It is supposed to be internal (although you can question the DPDK habit
of using the reserved __ namespace for such symbols).
I don't know of any way to prevent its use. I'm not sure it's needed.
Those who don't heed the "___" prefix warning, are on their own.
>> +{
>> + 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;
>> +
>> +}
>> +
On Thu, Mar 02, 2023 at 06:31:40AM +0000, Mattias Rönnblom wrote:
> On 2023-02-28 19:46, Tyler Retzlaff wrote:
> > On Tue, Feb 28, 2023 at 10:39:15AM +0100, Mattias Rönnblom wrote:
> >> 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.
> >>
> >> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> >> ---
> >
> > ...
> >
> >> diff --git a/lib/eal/include/rte_bitset.h b/lib/eal/include/rte_bitset.h
> >> new file mode 100644
> >> index 0000000000..e333e527e5
> >> --- /dev/null
> >> +++ b/lib/eal/include/rte_bitset.h
> >> @@ -0,0 +1,878 @@
> >> +/* 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 <stdint.h>
> >> +#include <sys/types.h>
> >
> > windows has no sys/types.h if there is a shim being picked up somewhere
> > portable code shouldn't depend on sys/types.h
> >
>
> That include was a misdirected attempt to get the 'size_t' definition. I
> will replaced it with <stddef.h>. Thanks.
>
> >> +
> >> +#include <rte_branch_prediction.h>
> >> +#include <rte_common.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 sucessive 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 sucessive 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 sucessive 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.
> >> + *
> >> + * @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 += __builtin_popcountll(bitset[i]);
> >> +
> >> + unused_mask = UINT64_MAX >> __RTE_BITSET_UNUSED(size);
> >> + total += __builtin_popcountll(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)
> >
> > ^^ seems like the intent here is for this to be internal (not part of
> > public api) i wonder do we have to mark it __rte_experimental?
> >
> > or better can we prevent visibility / consumption outside of the
> > inline functions in this header?
> >
>
> It is supposed to be internal (although you can question the DPDK habit
> of using the reserved __ namespace for such symbols).
yes, i've made occasional comments on this. rightly or wrongly it seems
settled.
>
> I don't know of any way to prevent its use. I'm not sure it's needed.
> Those who don't heed the "___" prefix warning, are on their own.
fair enough, i was thinking we could tuck it inside some preprocessor
block and expand it within the scope of the header where used and then
undef.
but if consumers aren't smart enough to avoid __foo they probably
wouldn't hesitate to define FOO to get internal_foo anyway.
>
> >> +{
> >> + 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;
> >> +
> >> +}
> >> +
>
@@ -13,8 +13,9 @@ test_sources = files(
'test_alarm.c',
'test_atomic.c',
'test_barrier.c',
- 'test_bitops.c',
'test_bitmap.c',
+ 'test_bitset.c',
+ 'test_bitops.c',
'test_bpf.c',
'test_byteorder.c',
'test_cksum.c',
@@ -164,6 +165,7 @@ fast_tests = [
['bpf_autotest', true, true],
['bpf_convert_autotest', true, true],
['bitops_autotest', true, true],
+ ['bitset_autotest', true, true],
['byteorder_autotest', true, true],
['cksum_autotest', true, true],
['cmdline_autotest', true, true],
new file mode 100644
@@ -0,0 +1,646 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2023 Ericsson AB
+ */
+
+#include <stdio.h>
+#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_TEST_COMMAND(bitset_autotest, test_bitset);
@@ -32,6 +32,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',
new file mode 100644
@@ -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;
+}
@@ -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',
new file mode 100644
@@ -0,0 +1,878 @@
+/* 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 <stdint.h>
+#include <sys/types.h>
+
+#include <rte_branch_prediction.h>
+#include <rte_common.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 sucessive 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 sucessive 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 sucessive 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.
+ *
+ * @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 += __builtin_popcountll(bitset[i]);
+
+ unused_mask = UINT64_MAX >> __RTE_BITSET_UNUSED(size);
+ total += __builtin_popcountll(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_ */
@@ -430,6 +430,9 @@ EXPERIMENTAL {
rte_thread_create_control;
rte_thread_set_name;
__rte_eal_trace_generic_blob;
+
+ # added in X.Y
+ rte_bitset_to_str;
};
INTERNAL {