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 5CA7941DB8; Thu, 2 Mar 2023 21:39:50 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id E8B2E40E2D; Thu, 2 Mar 2023 21:39:49 +0100 (CET) Received: from linux.microsoft.com (linux.microsoft.com [13.77.154.182]) by mails.dpdk.org (Postfix) with ESMTP id 8827640E09 for ; Thu, 2 Mar 2023 21:39:48 +0100 (CET) Received: by linux.microsoft.com (Postfix, from userid 1086) id D0E5C20B9C3D; Thu, 2 Mar 2023 12:39:47 -0800 (PST) DKIM-Filter: OpenDKIM Filter v2.11.0 linux.microsoft.com D0E5C20B9C3D DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linux.microsoft.com; s=default; t=1677789587; bh=zZnGONCcYGB5qKuEY1vE7iYIUspE/XDqPF6crsRnTJI=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=kl2j2YhyOkCKuxvThjVaM4qYkfQLuKPzRjmZLt/GXK9BMEGC3WQnbc2OuQUE94yt2 RIXOzrxdDUfQ5qYwrUGyabsYvKKc9fXKIBm2DQT+vjWKYXtuibAyF/ldOop1Gmp5dm t8AfKzUwuweVsSEdvgwCqcA0hXauTZb01orfAjn0= Date: Thu, 2 Mar 2023 12:39:47 -0800 From: Tyler Retzlaff To: Mattias =?iso-8859-1?Q?R=F6nnblom?= Cc: "dev@dpdk.org" , Erik Gabriel Carrillo , David Marchand , Maria Lingemark , Stefan Sundkvist Subject: Re: [RFC 1/2] eal: add bitset type Message-ID: <20230302203947.GA10153@linuxonhyperv3.guj3yctzbm1etfxqx2vob5hsef.xx.internal.cloudapp.net> References: <20230228093916.87206-1-mattias.ronnblom@ericsson.com> <20230228093916.87206-2-mattias.ronnblom@ericsson.com> <20230228184650.GA10925@linuxonhyperv3.guj3yctzbm1etfxqx2vob5hsef.xx.internal.cloudapp.net> <9a341748-7daf-2d66-6d5c-4dc2be86dddb@ericsson.com> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <9a341748-7daf-2d66-6d5c-4dc2be86dddb@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 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 > >> 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 > > > > That include was a misdirected attempt to get the 'size_t' definition. I > will replaced it with . Thanks. > > >> + > >> +#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? > > > > 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; > >> + > >> +} > >> + >