[RFC 1/2] eal: add bitset type

[Mattias Rönnblom]

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 at 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;
>> +
>> +}
>> +