From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 8D68C41D9F; Tue, 28 Feb 2023 19:46:53 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 317B840EE6; Tue, 28 Feb 2023 19:46:53 +0100 (CET) Received: from linux.microsoft.com (linux.microsoft.com [13.77.154.182]) by mails.dpdk.org (Postfix) with ESMTP id D8B8D4021F for ; Tue, 28 Feb 2023 19:46:51 +0100 (CET) Received: by linux.microsoft.com (Postfix, from userid 1086) id EA87120B9C3D; Tue, 28 Feb 2023 10:46:50 -0800 (PST) DKIM-Filter: OpenDKIM Filter v2.11.0 linux.microsoft.com EA87120B9C3D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.microsoft.com; s=default; t=1677610010; bh=Hz6pVC5ad89syOcry2wMOfI42C0VaA7i8D+cwB8RTdc=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=nOwuW8MauA1V7/Nu8QozX5cTVkiun8OlgbjE6XlAnZdhK7PkEIqQindviIWkxO/cp S/B5kBiB+Ehm0yjj47iiVxSfjyRI9Lf6HwEnClmX/9JuOEbXD7Y7MpSYPn1jTMjUB3 hImRWZvOTdfe/hQJUtwfxwoaelAaQnUmnhxfHLgI= Date: Tue, 28 Feb 2023 10:46:50 -0800 From: Tyler Retzlaff To: Mattias =?iso-8859-1?Q?R=F6nnblom?= Cc: dev@dpdk.org, Erik Gabriel Carrillo , David Marchand , maria.lingemark@ericsson.com, Stefan Sundkvist Subject: Re: [RFC 1/2] eal: add bitset type Message-ID: <20230228184650.GA10925@linuxonhyperv3.guj3yctzbm1etfxqx2vob5hsef.xx.internal.cloudapp.net> References: <20230228093916.87206-1-mattias.ronnblom@ericsson.com> <20230228093916.87206-2-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20230228093916.87206-2-mattias.ronnblom@ericsson.com> User-Agent: Mutt/1.5.21 (2010-09-15) X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org 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 > API may be a more appropriate choice. > > Signed-off-by: Mattias Rönnblom > --- ... > 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 > +#include > +#include > +#include 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 > +#include > +#include > +#include > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +/** > + * The size (in bytes) of each element in the array used to represent > + * a bitset. > + */ > +#define RTE_BITSET_WORD_SIZE (sizeof(uint64_t)) > + > +/** > + * The size (in bits) of each element in the array used to represent > + * a bitset. > + */ > +#define RTE_BITSET_WORD_BITS (RTE_BITSET_WORD_SIZE * CHAR_BIT) > + > +/** > + * Computes the number of words required to store @c size bits. > + */ > +#define RTE_BITSET_NUM_WORDS(size) \ > + ((size + RTE_BITSET_WORD_BITS - 1) / RTE_BITSET_WORD_BITS) > + > +/** > + * Computes the amount of memory (in bytes) required to fit a bitset > + * holding @c size bits. > + */ > +#define RTE_BITSET_SIZE(size) \ > + ((size_t)(RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_SIZE)) > + > +#define __RTE_BITSET_WORD_IDX(bit_num) ((bit_num) / RTE_BITSET_WORD_BITS) > +#define __RTE_BITSET_BIT_OFFSET(bit_num) ((bit_num) % RTE_BITSET_WORD_BITS) > +#define __RTE_BITSET_UNUSED(size) \ > + ((RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_BITS) \ > + - (size)) > + > +/** > + * @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 const uint64_t * pointer to the bitset array. > + * @param size > + * The size of the bitset (in bits). > + */ > + > +#define RTE_BITSET_FOREACH_SET(var, bitset, size) \ > + __RTE_BITSET_FOREACH(var, bitset, size, 0, size, 0) > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Iterate over all bits cleared. > + * > + * This macro iterates over all bits cleared in the bitset, in the > + * forward direction (i.e., starting with the lowest-indexed set bit). > + * > + * @param var > + * An iterator variable of type @c ssize_t. For each successive iteration, > + * this variable will hold the bit index of a cleared bit. > + * @param bitset > + * A const uint64_t * pointer to the bitset array. > + * @param size > + * The size of the bitset (in bits). > + */ > + > +#define RTE_BITSET_FOREACH_CLEAR(var, bitset, size) \ > + __RTE_BITSET_FOREACH(var, bitset, size, 0, size, \ > + __RTE_BITSET_FIND_FLAG_FIND_CLEAR) > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Iterate over all bits set within a range. > + * > + * This macro iterates over all bits set (i.e., all ones) in the > + * specified range, in the forward direction (i.e., starting with the > + * least significant '1'). > + * > + * @param var > + * An iterator variable of type @c ssize_t. For each sucessive iteration, > + * this variable will hold the bit index of a set bit. > + * @param bitset > + * A const uint64_t * pointer to the bitset array. > + * @param size > + * The size of the bitset (in bits). > + * @param start_bit > + * The index of the first bit to check. Must be less than @c size. > + * @param len > + * The length (in bits) of the range. @c start_bit + @c len must be less > + * than or equal to @c size. > + */ > + > +#define RTE_BITSET_FOREACH_SET_RANGE(var, bitset, size, start_bit, \ > + len) \ > + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, 0) > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Iterate over all cleared bits within a range. > + * > + * This macro iterates over all bits cleared (i.e., all zeroes) in the > + * specified range, in the forward direction (i.e., starting with the > + * least significant '0'). > + * > + * @param var > + * An iterator variable of type @c ssize_t. For each sucessive iteration, > + * this variable will hold the bit index of a set bit. > + * @param bitset > + * A const uint64_t * pointer to the bitset array. > + * @param size > + * The size of the bitset (in bits). > + * @param start_bit > + * The index of the first bit to check. Must be less than @c size. > + * @param len > + * The length (in bits) of the range. @c start_bit + @c len must be less > + * than or equal to @c size. > + */ > + > +#define RTE_BITSET_FOREACH_CLEAR_RANGE(var, bitset, size, start_bit, \ > + len) \ > + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ > + __RTE_BITSET_FIND_FLAG_FIND_CLEAR) > + > +#define RTE_BITSET_FOREACH_SET_WRAP(var, bitset, size, start_bit, \ > + len) \ > + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ > + __RTE_BITSET_FIND_FLAG_WRAP) > + > +#define RTE_BITSET_FOREACH_CLEAR_WRAP(var, bitset, size, start_bit, \ > + len) \ > + __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, \ > + __RTE_BITSET_FIND_FLAG_WRAP | \ > + __RTE_BITSET_FIND_FLAG_FIND_CLEAR) > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Initializes a bitset. > + * > + * All bits are cleared. > + * > + * @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; > + > +} > +