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 6B89745A68; Fri, 11 Oct 2024 11:35:11 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 5AA4B4064F; Fri, 11 Oct 2024 11:35:11 +0200 (CEST) Received: from mail.lysator.liu.se (mail.lysator.liu.se [130.236.254.3]) by mails.dpdk.org (Postfix) with ESMTP id EA45240659 for ; Fri, 11 Oct 2024 11:35:09 +0200 (CEST) Received: from mail.lysator.liu.se (localhost [127.0.0.1]) by mail.lysator.liu.se (Postfix) with ESMTP id 3F13731EF for ; Fri, 11 Oct 2024 11:35:09 +0200 (CEST) Received: by mail.lysator.liu.se (Postfix, from userid 1004) id 31F5F326A; Fri, 11 Oct 2024 11:35:09 +0200 (CEST) X-Spam-Checker-Version: SpamAssassin 4.0.0 (2022-12-13) on hermod.lysator.liu.se X-Spam-Level: X-Spam-Status: No, score=-1.2 required=5.0 tests=ALL_TRUSTED,AWL, T_SCC_BODY_TEXT_LINE autolearn=disabled version=4.0.0 X-Spam-Score: -1.2 Received: from [192.168.1.85] (h-62-63-215-114.A163.priv.bahnhof.se [62.63.215.114]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mail.lysator.liu.se (Postfix) with ESMTPSA id 3B8813265; Fri, 11 Oct 2024 11:35:04 +0200 (CEST) Message-ID: <5f599676-761a-4cc0-a870-ade63c7c0e92@lysator.liu.se> Date: Fri, 11 Oct 2024 11:35:03 +0200 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH v2 1/4] eal: add bitset type To: David Marchand , dev@dpdk.org Cc: mattias.ronnblom@ericsson.com, mb@smartsharesystems.com, stephen@networkplumber.org, harry.van.haaren@intel.com, roretzla@linux.microsoft.com, Thomas Monjalon References: <20240809201440.590464-1-mattias.ronnblom@ericsson.com> <20241010083022.3437380-1-david.marchand@redhat.com> <20241010083022.3437380-2-david.marchand@redhat.com> Content-Language: en-US From: =?UTF-8?Q?Mattias_R=C3=B6nnblom?= In-Reply-To: <20241010083022.3437380-2-david.marchand@redhat.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Virus-Scanned: ClamAV using ClamSMTP 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 2024-10-10 10:30, David Marchand wrote: > From: Mattias Rönnblom > > Introduce a set of functions and macros that operate on sets of bits, > kept in arrays of 64-bit words. > > RTE bitset is designed for bitsets which are larger than what fits in > a single machine word (i.e., 64 bits). Tiny detail: there is an extra newline here that shouldn't be there. > For very large bitsets, the API may be a more appropriate > choice. > > Signed-off-by: Mattias Rönnblom > Acked-by: Morten Brørup > Acked-by: Tyler Retzlaff > --- > MAINTAINERS | 6 + > app/test/meson.build | 1 + > app/test/test_bitset.c | 861 +++++++++++++++++++++ > doc/api/doxy-api-index.md | 1 + > doc/guides/rel_notes/release_24_11.rst | 9 + > lib/eal/common/meson.build | 1 + > lib/eal/common/rte_bitset.c | 30 + > lib/eal/include/meson.build | 1 + > lib/eal/include/rte_bitset.h | 998 +++++++++++++++++++++++++ > lib/eal/version.map | 3 + > 10 files changed, 1911 insertions(+) > create mode 100644 app/test/test_bitset.c > create mode 100644 lib/eal/common/rte_bitset.c > create mode 100644 lib/eal/include/rte_bitset.h > > diff --git a/MAINTAINERS b/MAINTAINERS > index 812463fe9f..00da3dac29 100644 > --- a/MAINTAINERS > +++ b/MAINTAINERS > @@ -255,6 +255,12 @@ M: Jack Bond-Preston > F: lib/eal/include/rte_bitops.h > F: app/test/test_bitops.c > > +Bitset > +M: Mattias Rönnblom > +F: lib/eal/include/rte_bitset.h > +F: lib/eal/common/rte_bitset.c > +F: app/test/test_bitset.c > + > Bitmap > M: Cristian Dumitrescu > F: lib/eal/include/rte_bitmap.h > diff --git a/app/test/meson.build b/app/test/meson.build > index e29258e6ec..fe248b786c 100644 > --- a/app/test/meson.build > +++ b/app/test/meson.build > @@ -33,6 +33,7 @@ source_file_deps = { > 'test_bitcount.c': [], > 'test_bitmap.c': [], > 'test_bitops.c': [], > + 'test_bitset.c': [], > 'test_bitratestats.c': ['metrics', 'bitratestats', 'ethdev'] + sample_packet_forward_deps, > 'test_bpf.c': ['bpf', 'net'], > 'test_byteorder.c': [], > diff --git a/app/test/test_bitset.c b/app/test/test_bitset.c > new file mode 100644 > index 0000000000..fd3e50f396 > --- /dev/null > +++ b/app/test/test_bitset.c > @@ -0,0 +1,861 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2023 Ericsson AB > + */ > + > +#include > +#include > + > +#include > +#include > + > +#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++) > + ((unsigned char *)buf)[i] = 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 void > +rand_unused_bits(uint64_t *bitset, size_t size) > +{ > + uint64_t bits = rte_rand() & ~__RTE_BITSET_USED_MASK(size); > + > + bitset[RTE_BITSET_NUM_WORDS(size) - 1] |= bits; > +} > + > +static void > +rand_bitset(uint64_t *bitset, size_t size) > +{ > + size_t i; > + > + rte_bitset_init(bitset, size); > + > + for (i = 0; i < size; i++) > + rte_bitset_assign(bitset, i, rand_bool()); > + > + rand_unused_bits(bitset, size); > +} > + > +typedef bool test_fun(const uint64_t *bitset, size_t bit_num); > +typedef void set_fun(uint64_t *bitset, size_t bit_num); > +typedef void clear_fun(uint64_t *bitset, size_t bit_num); > +typedef void assign_fun(uint64_t *bitset, size_t bit_num, bool value); > +typedef void flip_fun(uint64_t *bitset, size_t bit_num); > + > +static int > +test_set_clear_size(test_fun test_fun, set_fun set_fun, clear_fun clear_fun, size_t size) > +{ > + size_t i; > + bool reference[size]; > + uint64_t *bitset; > + > + rand_bool_ary(reference, size); > + > + bitset = alloc_bitset(size); > + > + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); > + > + rte_bitset_init(bitset, size); > + > + for (i = 0; i < size; i++) { > + if (reference[i]) > + set_fun(bitset, i); > + else > + clear_fun(bitset, i); > + } > + > + for (i = 0; i < size; i++) > + if (reference[i] != test_fun(bitset, i)) > + return TEST_FAILED; > + > + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, > + "Buffer over- or underrun detected"); > + > + return TEST_SUCCESS; > +} > + > +#define RAND_ITERATIONS (10000) > +#define RAND_SET_MAX_SIZE (1000) > + > +static int > +test_set_clear_fun(test_fun test_fun, set_fun set_fun, clear_fun clear_fun) > +{ > + size_t i; > + > + for (i = 0; i < RAND_ITERATIONS; i++) { > + size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1); > + > + if (test_set_clear_size(test_fun, set_fun, clear_fun, size) != TEST_SUCCESS) > + return TEST_FAILED; > + } > + > + return TEST_SUCCESS; > +} > + > +static int > +test_set_clear(void) > +{ > + return test_set_clear_fun(rte_bitset_test, rte_bitset_set, rte_bitset_clear); > +} > + > +static int > +test_flip_size(test_fun test_fun, assign_fun assign_fun, flip_fun flip_fun, size_t size) > +{ > + size_t i; > + uint64_t *bitset; > + > + bitset = alloc_bitset(size); > + > + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); > + > + rand_bitset(bitset, size); > + > + for (i = 0; i < size; i++) { > + RTE_BITSET_DECLARE(reference, size); > + > + rte_bitset_copy(reference, bitset, size); > + > + bool value = test_fun(bitset, i); > + > + flip_fun(bitset, i); > + > + TEST_ASSERT(test_fun(bitset, i) != value, "Bit %zd was not flipped", i); > + > + assign_fun(reference, i, !value); > + > + TEST_ASSERT(rte_bitset_equal(bitset, reference, size), > + "Not only the target bit %zd was flipped", i); > + > + > + } > + > + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, > + "Buffer over- or underrun detected"); > + > + return TEST_SUCCESS; > +} > + > +static int > +test_flip_fun(test_fun test_fun, assign_fun assign_fun, flip_fun flip_fun) > +{ > + size_t i; > + > + for (i = 0; i < RAND_ITERATIONS; i++) { > + size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1); > + > + if (test_flip_size(test_fun, assign_fun, flip_fun, size) != TEST_SUCCESS) > + return TEST_FAILED; > + } > + > + return TEST_SUCCESS; > +} > + > +static int > +test_flip(void) > +{ > + return test_flip_fun(rte_bitset_test, rte_bitset_assign, rte_bitset_flip); > +} > + > +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); > + > + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); > + > + 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; > + } > + > + } > + > + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, > + "Buffer over- or underrun detected"); > + > + 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); > + > + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); > + > + 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; > + } > + > + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, > + "Buffer over- or underrun detected"); > + > + 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); > + > + TEST_ASSERT(bitset != NULL, "Failed to allocate memory"); > + > + rte_bitset_init(bitset, size); > + > + rand_unused_bits(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; > + > + TEST_ASSERT_EQUAL(free_bitset(bitset, size), TEST_SUCCESS, > + "Buffer over- or underrun detected"); > + > + 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 = 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); > +} > + > +typedef void bitset_op(uint64_t *dst, const uint64_t *a, const uint64_t *b, size_t bit_num); > +typedef bool bool_op(bool a, bool b); > + > +static int > +test_logic_op(bitset_op bitset_op, bool_op bool_op) > +{ > + const size_t size = 1 + rte_rand_max(200); > + RTE_BITSET_DECLARE(bitset_a, size); > + RTE_BITSET_DECLARE(bitset_b, size); > + RTE_BITSET_DECLARE(bitset_d, size); > + > + bool ary_a[size]; > + bool ary_b[size]; > + bool ary_d[size]; > + > + rand_bool_ary(ary_a, size); > + rand_bool_ary(ary_b, size); > + > + size_t i; > + for (i = 0; i < size; i++) { > + rte_bitset_assign(bitset_a, i, ary_a[i]); > + rte_bitset_assign(bitset_b, i, ary_b[i]); > + ary_d[i] = bool_op(ary_a[i], ary_b[i]); > + } > + > + bitset_op(bitset_d, bitset_a, bitset_b, size); > + > + for (i = 0; i < size; i++) > + TEST_ASSERT_EQUAL(rte_bitset_test(bitset_d, i), ary_d[i], > + "Unexpected value of bit %zd", i); > + > + return TEST_SUCCESS; > +} > + > +static bool > +bool_or(bool a, bool b) > +{ > + return a || b; > +} > + > +static int > +test_or(void) > +{ > + return test_logic_op(rte_bitset_or, bool_or); > +} > + > +static bool > +bool_and(bool a, bool b) > +{ > + return a && b; > +} > + > +static int > +test_and(void) > +{ > + return test_logic_op(rte_bitset_and, bool_and); > +} > + > +static bool > +bool_xor(bool a, bool b) > +{ > + return a != b; > +} > + > +static int > +test_xor(void) > +{ > + return test_logic_op(rte_bitset_xor, bool_xor); > +} > + > +static int > +test_complement(void) > +{ > + int i; > + > + for (i = 0; i < RAND_ITERATIONS; i++) { > + const size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1); > + > + RTE_BITSET_DECLARE(src, size); > + > + rand_bitset(src, size); > + > + bool bit_idx = rte_rand_max(size); > + bool bit_value = rte_bitset_test(src, bit_idx); > + > + RTE_BITSET_DECLARE(dst, size); > + > + rte_bitset_complement(dst, src, size); > + > + TEST_ASSERT(bit_value != rte_bitset_test(dst, bit_idx), > + "Bit %d was not flipped", bit_idx); > + } > + > + return TEST_SUCCESS; > +} > + > +static int > +test_shift(bool right) > +{ > + int i; > + > + const char *direction = right ? "right" : "left"; > + > + for (i = 0; i < 10000; i++) { > + const int size = 1 + (int)rte_rand_max(500); > + const int shift_count = (int)rte_rand_max(1.5 * size); > + int src_idx; > + > + RTE_BITSET_DECLARE(src, size); > + RTE_BITSET_DECLARE(reference, size); > + > + rte_bitset_init(src, size); > + rte_bitset_init(reference, size); > + > + rand_unused_bits(src, size); > + rand_unused_bits(reference, size); > + > + for (src_idx = 0; src_idx < size; src_idx++) { > + bool value = rand_bool(); > + > + rte_bitset_assign(src, src_idx, value); > + > + int dst_idx = right ? src_idx - shift_count : src_idx + shift_count; > + > + if (dst_idx >= 0 && dst_idx < size) > + rte_bitset_assign(reference, dst_idx, value); > + } > + > + uint64_t *dst = alloc_bitset(size); > + > + if (right) > + rte_bitset_shift_right(dst, src, size, shift_count); > + else > + rte_bitset_shift_left(dst, src, size, shift_count); > + > + TEST_ASSERT(rte_bitset_equal(dst, reference, size), > + "Unexpected result from shifting bitset of size %d bits %d bits %s", > + size, shift_count, direction); > + > + TEST_ASSERT_EQUAL(free_bitset(dst, size), TEST_SUCCESS, > + "Shift %s operation overwrote buffer", direction); > + } > + > + return TEST_SUCCESS; > +} > + > +static int > +test_shift_right(void) > +{ > + return test_shift(true); > +} > + > +static int > +test_shift_left(void) > +{ > + return test_shift(false); > +} > + > +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)); > + > + 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 struct unit_test_suite bitset_tests = { > + .suite_name = "bitset test suite", > + .unit_test_cases = { > + TEST_CASE_ST(NULL, NULL, test_set_clear), > + TEST_CASE_ST(NULL, NULL, test_flip), > + TEST_CASE_ST(NULL, NULL, test_find), > + TEST_CASE_ST(NULL, NULL, test_foreach), > + TEST_CASE_ST(NULL, NULL, test_count), > + TEST_CASE_ST(NULL, NULL, test_define), > + TEST_CASE_ST(NULL, NULL, test_or), > + TEST_CASE_ST(NULL, NULL, test_and), > + TEST_CASE_ST(NULL, NULL, test_xor), > + TEST_CASE_ST(NULL, NULL, test_complement), > + TEST_CASE_ST(NULL, NULL, test_shift_right), > + TEST_CASE_ST(NULL, NULL, test_shift_left), > + TEST_CASE_ST(NULL, NULL, test_equal), > + TEST_CASE_ST(NULL, NULL, test_copy), > + TEST_CASE_ST(NULL, NULL, test_to_str), > + TEST_CASES_END() > + } > +}; > + > +static int > +test_bitset(void) > +{ > + return unit_test_suite_runner(&bitset_tests); > +} > + > +REGISTER_FAST_TEST(bitset_autotest, true, true, test_bitset); > diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md > index f9f0300126..abd44b1861 100644 > --- a/doc/api/doxy-api-index.md > +++ b/doc/api/doxy-api-index.md > @@ -174,6 +174,7 @@ The public API headers are grouped by topics: > [ring](@ref rte_ring.h), > [stack](@ref rte_stack.h), > [tailq](@ref rte_tailq.h), > + [bitset](@ref rte_bitset.h), > [bitmap](@ref rte_bitmap.h) > > - **packet framework**: > diff --git a/doc/guides/rel_notes/release_24_11.rst b/doc/guides/rel_notes/release_24_11.rst > index 2f78f2d125..f3fd8517ed 100644 > --- a/doc/guides/rel_notes/release_24_11.rst > +++ b/doc/guides/rel_notes/release_24_11.rst > @@ -70,6 +70,15 @@ New Features > The new public API elements are polymorphic, using the _Generic-based > macros (for C) and function overloading (in C++ translation units). > > +* **Added multi-word bitset API.** > + > + A new multi-word bitset API has been introduced in the EAL. > + The RTE bitset is optimized for scenarios where the bitset size exceeds the > + capacity of a single word (e.g., larger than 64 bits), but is not large > + enough to justify the overhead and complexity of the more scalable, > + yet slower, API. This addition provides an efficient and > + straightforward alternative for handling bitsets of intermediate sizes. > + > * **Extended service cores statistics.** > > Two new per-service counters are added to the service cores framework. > diff --git a/lib/eal/common/meson.build b/lib/eal/common/meson.build > index 22a626ba6f..c1bbf26654 100644 > --- a/lib/eal/common/meson.build > +++ b/lib/eal/common/meson.build > @@ -31,6 +31,7 @@ sources += files( > 'eal_common_uuid.c', > 'malloc_elem.c', > 'malloc_heap.c', > + 'rte_bitset.c', > 'rte_malloc.c', > 'rte_random.c', > 'rte_reciprocal.c', > diff --git a/lib/eal/common/rte_bitset.c b/lib/eal/common/rte_bitset.c > new file mode 100644 > index 0000000000..e25008519e > --- /dev/null > +++ b/lib/eal/common/rte_bitset.c > @@ -0,0 +1,30 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2023 Ericsson AB > + */ > + > +#include > +#include > +#include > +#include > + > +#include "rte_bitset.h" > + > +ssize_t > +rte_bitset_to_str(const uint64_t *bitset, size_t num_bits, char *buf, size_t capacity) > +{ > + size_t i; > + > + if (capacity < (num_bits + 1)) > + return -EINVAL; > + > + for (i = 0; i < num_bits; i++) { > + bool value; > + > + value = rte_bitset_test(bitset, num_bits - 1 - i); > + buf[i] = value ? '1' : '0'; > + } > + > + buf[num_bits] = '\0'; > + > + return num_bits + 1; > +} > diff --git a/lib/eal/include/meson.build b/lib/eal/include/meson.build > index e94b056d46..474097f211 100644 > --- a/lib/eal/include/meson.build > +++ b/lib/eal/include/meson.build > @@ -7,6 +7,7 @@ headers += files( > 'rte_alarm.h', > 'rte_bitmap.h', > 'rte_bitops.h', > + 'rte_bitset.h', > 'rte_branch_prediction.h', > 'rte_bus.h', > 'rte_class.h', > diff --git a/lib/eal/include/rte_bitset.h b/lib/eal/include/rte_bitset.h > new file mode 100644 > index 0000000000..b2d71aa7c6 > --- /dev/null > +++ b/lib/eal/include/rte_bitset.h > @@ -0,0 +1,998 @@ > +/* 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 > + > +#include > +#include > +#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)) > +#define __RTE_BITSET_USED_MASK(size) \ > + (UINT64_MAX >> __RTE_BITSET_UNUSED(size)) > + > +#define __RTE_BITSET_DELEGATE_N(fun, bitset, bit_num, ...) \ > + fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], __RTE_BITSET_BIT_OFFSET(bit_num), \ > + __VA_ARGS__) > + > +/* MSVC doesn't have ##__VA_ARGS__, so argument-less -> special case */ > +#define __RTE_BITSET_DELEGATE(fun, bitset, bit_num) \ > + fun(&(bitset)[__RTE_BITSET_WORD_IDX(bit_num)], __RTE_BITSET_BIT_OFFSET(bit_num)) > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Declare a bitset. > + * > + * Declare (e.g., as a struct field) or define (e.g., as a stack > + * variable) a bitset of the specified size. > + * > + * @param size > + * The number of bits the bitset must be able to represent. Must be > + * a compile-time constant. > + * @param name > + * The field or variable name of the resulting definition. > + */ > +#define RTE_BITSET_DECLARE(name, size) \ > + uint64_t name[RTE_BITSET_NUM_WORDS(size)] > + > +#define __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) \ > + ((len) - 1 - ((var) >= (start_bit) ? (var) - (start_bit) : (size) - (start_bit) + (var))) > + > +#define __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, flags) \ > + for ((var) = __rte_bitset_find(bitset, size, start_bit, len, flags); \ > + (var) != -1; \ > + (var) = __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len) > 0 ? \ > + __rte_bitset_find(bitset, size, ((var) + 1) % (size), \ > + __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len), flags) : -1) > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Iterate over all bits set. > + * > + * This macro iterates over all bits set (i.e., all ones) in the > + * bitset, in the forward direction (i.e., starting with the least > + * significant '1'). > + * > + * @param var > + * An iterator variable of type @c ssize_t. For each successive > + * iteration, this variable will hold the bit index of a set bit. > + * @param bitset > + * A 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 successive 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 successive 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. > + * > + * In case all words in the bitset array are already set to zero by > + * other means (e.g., at the time of memory allocation), this function > + * need not be called. > + * > + * @param bitset > + * A pointer to the array of bitset 64-bit words. > + * @param size > + * The size of the bitset (in bits). > + */ > +__rte_experimental > +static inline void > +rte_bitset_init(uint64_t *bitset, size_t size) > +{ > + memset(bitset, 0, RTE_BITSET_SIZE(size)); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Test if a bit is set. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param bit_num > + * Index of the bit to test. Index 0 is the least significant bit. > + * @return > + * Returns true if the bit is '1', and false if the bit is '0'. > + */ > +__rte_experimental > +static inline bool > +rte_bitset_test(const uint64_t *bitset, size_t bit_num) > +{ > + return __RTE_BITSET_DELEGATE(rte_bit_test, bitset, bit_num); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Set a bit in the bitset. > + * > + * Bits are numbered from 0 to (size - 1) (inclusive). > + * > + * The operation is not guaranteed to be atomic. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param bit_num > + * The index of the bit to be set. > + */ > +__rte_experimental > +static inline void > +rte_bitset_set(uint64_t *bitset, size_t bit_num) > +{ > + __RTE_BITSET_DELEGATE(rte_bit_set, bitset, bit_num); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Clear a bit in the bitset. > + * > + * Bits are numbered 0 to (size - 1) (inclusive). > + * > + * The operation is not guaranteed to be atomic. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param bit_num > + * The index of the bit to be cleared. > + */ > +__rte_experimental > +static inline void > +rte_bitset_clear(uint64_t *bitset, size_t bit_num) > +{ > + __RTE_BITSET_DELEGATE(rte_bit_clear, bitset, bit_num); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Set or clear a bit in the bitset. > + * > + * Bits are numbered 0 to (size - 1) (inclusive). > + * > + * The operation is not guaranteed to be atomic. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param bit_num > + * The index of the bit to be set or cleared. > + * @param bit_value > + * Control if the bit should be set or cleared. > + */ > +__rte_experimental > +static inline void > +rte_bitset_assign(uint64_t *bitset, size_t bit_num, bool bit_value) > +{ > + __RTE_BITSET_DELEGATE_N(rte_bit_assign, bitset, bit_num, bit_value); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Change the value of a bit in the bitset. > + * > + * Bits are numbered 0 to (size - 1) (inclusive). > + * > + * The operation is not guaranteed to be atomic. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param bit_num > + * The index of the bit to be flipped. > + */ > +__rte_experimental > +static inline void > +rte_bitset_flip(uint64_t *bitset, size_t bit_num) > +{ > + __RTE_BITSET_DELEGATE(rte_bit_flip, bitset, bit_num); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Set all bits in the bitset. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + */ > +__rte_experimental > +static inline void > +rte_bitset_set_all(uint64_t *bitset, size_t size) > +{ > + memset(bitset, 0xFF, RTE_BITSET_SIZE(size)); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Clear all bits in the bitset. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + */ > +__rte_experimental > +static inline void > +rte_bitset_clear_all(uint64_t *bitset, size_t size) > +{ > + rte_bitset_init(bitset, size); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Count all set bits (also known as the @e weight). > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + * @return > + * Returns the number of '1' bits in the bitset. > + */ > +__rte_experimental > +static inline size_t > +rte_bitset_count_set(const uint64_t *bitset, size_t size) > +{ > + size_t i; > + size_t total = 0; > + > + /* > + * Unused bits in a rte_bitset are always '0', and thus are > + * not included in this count. > + */ > + for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++) > + total += rte_popcount64(bitset[i]); > + > + total += rte_popcount64(bitset[i] & __RTE_BITSET_USED_MASK(size)); > + > + return total; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Count all cleared bits. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + * @return > + * Returns the number of '0' bits in the bitset. > + */ > +__rte_experimental > +static inline size_t > +rte_bitset_count_clear(const uint64_t *bitset, size_t size) > +{ > + return size - rte_bitset_count_set(bitset, size); > +} > + > +#define __RTE_BITSET_FIND_FLAG_FIND_CLEAR (1U << 0) > +#define __RTE_BITSET_FIND_FLAG_WRAP (1U << 1) > + > +__rte_experimental > +static inline ssize_t > +__rte_bitset_find_nowrap(const uint64_t *bitset, size_t __rte_unused size, size_t start_bit, > + size_t len, bool find_clear) > +{ > + size_t word_idx; > + size_t offset; > + size_t end_bit = start_bit + len; > + > + RTE_ASSERT(end_bit <= size); > + > + if (unlikely(len == 0)) > + return -1; > + > + word_idx = __RTE_BITSET_WORD_IDX(start_bit); > + offset = __RTE_BITSET_BIT_OFFSET(start_bit); > + > + while (word_idx <= __RTE_BITSET_WORD_IDX(end_bit - 1)) { > + uint64_t word; > + int word_ffs; > + > + word = bitset[word_idx]; > + if (find_clear) > + word = ~word; > + > + word >>= offset; > + > + word_ffs = __builtin_ffsll(word); > + > + if (word_ffs != 0) { > + ssize_t ffs = start_bit + word_ffs - 1; > + > + /* > + * Check if set bit were among the last, > + * unused bits, in the last word. > + */ > + if (unlikely(ffs >= (ssize_t)end_bit)) > + return -1; > + > + return ffs; > + } > + > + start_bit += (RTE_BITSET_WORD_BITS - offset); > + word_idx++; > + offset = 0; > + } > + > + return -1; > + > +} > + > +__rte_experimental > +static inline ssize_t > +__rte_bitset_find(const uint64_t *bitset, size_t size, size_t start_bit, size_t len, > + unsigned int flags) > +{ > + bool find_clear = flags & __RTE_BITSET_FIND_FLAG_FIND_CLEAR; > + bool may_wrap = flags & __RTE_BITSET_FIND_FLAG_WRAP; > + bool does_wrap = (start_bit + len) > size; > + ssize_t rc; > + > + RTE_ASSERT(len <= size); > + if (!may_wrap) > + RTE_ASSERT(!does_wrap); > + > + if (may_wrap && does_wrap) { > + size_t len0 = size - start_bit; > + size_t len1 = len - len0; > + > + rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len0, find_clear); > + if (rc < 0) > + rc = __rte_bitset_find_nowrap(bitset, size, 0, len1, find_clear); > + } else > + rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len, find_clear); > + > + return rc; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Find first bit set. > + * > + * Scans the bitset in the forward direction (i.e., starting at the > + * least significant bit), and returns the index of the first '1'. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + * @return > + * Returns the index of the least significant '1', or -1 if all > + * bits are '0'. > + */ > +__rte_experimental > +static inline ssize_t > +rte_bitset_find_first_set(const uint64_t *bitset, size_t size) > +{ > + return __rte_bitset_find(bitset, size, 0, size, 0); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Find first bit set at offset. > + * > + * Scans the bitset in the forward direction (i.e., starting at the > + * least significant bit), starting at an offset @c start_bit into the > + * bitset, and returns the index of the first '1' encountered. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + * @param start_bit > + * The index of the first bit to check. Must be less than @c size. > + * @param len > + * The number of bits to scan. @c start_bit + @c len must be less > + * than or equal to @c size. > + * @return > + * Returns the index of the least significant '1', or -1 if all > + * bits are '0'. > + */ > +__rte_experimental > +static inline ssize_t > +rte_bitset_find_set(const uint64_t *bitset, size_t size, size_t start_bit, size_t len) > +{ > + return __rte_bitset_find(bitset, size, start_bit, len, 0); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Find first bit set at offset, with wrap-around. > + * > + * Scans the bitset in the forward direction (i.e., starting at the > + * least significant bit), starting at an offset @c start_bit into the > + * bitset. If no '1' is encountered before the end of the bitset, the search > + * will continue at index 0. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + * @param start_bit > + * The index of the first bit to check. Must be less than @c size. > + * @param len > + * The number of bits to scan. @c start_bit + @c len must be less > + * than or equal to @c size. > + * @return > + * Returns the index of the least significant '1', or -1 if all > + * bits are '0'. > + */ > +__rte_experimental > +static inline ssize_t > +rte_bitset_find_set_wrap(const uint64_t *bitset, size_t size, size_t start_bit, size_t len) > +{ > + return __rte_bitset_find(bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_WRAP); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Find first cleared bit. > + * > + * Scans the bitset in the forward direction (i.e., starting at the > + * least significant bit), and returns the index of the first '0'. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + * @return > + * Returns the index of the least significant '0', or -1 if all > + * bits are '1'. > + */ > +__rte_experimental > +static inline ssize_t > +rte_bitset_find_first_clear(const uint64_t *bitset, size_t size) > +{ > + return __rte_bitset_find(bitset, size, 0, size, __RTE_BITSET_FIND_FLAG_FIND_CLEAR); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Find first cleared bit at offset. > + * > + * Scans the bitset in the forward direction (i.e., starting at the > + * least significant bit), starting at an offset @c start_bit into the > + * bitset, and returns the index of the first '0' encountered. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + * @param start_bit > + * The index of the first bit to check. Must be less than @c size. > + * @param len > + * The number of bits to scan. @c start_bit + @c len must be less > + * than or equal to @c size. > + * @return > + * Returns the index of the least significant '0', or -1 if all > + * bits are '1'. > + */ > +__rte_experimental > +static inline ssize_t > +rte_bitset_find_clear(const uint64_t *bitset, size_t size, size_t start_bit, size_t len) > +{ > + return __rte_bitset_find(bitset, size, start_bit, len, __RTE_BITSET_FIND_FLAG_FIND_CLEAR); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Find first cleared bit at offset, with wrap-around. > + * > + * Scans the bitset in the forward direction (i.e., starting at the > + * least significant bit), starting at an offset @c start_bit into the > + * bitset. If no '0' is encountered before the end of the bitset, the > + * search will continue at index 0. > + * > + * @param bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitset (in bits). > + * @param start_bit > + * The index of the first bit to check. Must be less than @c size. > + * @param len > + * The number of bits to scan. @c start_bit + @c len must be less > + * than or equal to @c size. > + * @return > + * Returns the index of the least significant '0', or -1 if all > + * bits are '1'. > + */ > +__rte_experimental > +static inline ssize_t > +rte_bitset_find_clear_wrap(const uint64_t *bitset, size_t size, size_t start_bit, size_t len) > +{ > + return __rte_bitset_find(bitset, size, start_bit, len, > + __RTE_BITSET_FIND_FLAG_FIND_CLEAR | __RTE_BITSET_FIND_FLAG_WRAP); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Copy bitset. > + * > + * Copy the bits of the @c src_bitset to the @c dst_bitset. > + * > + * The bitsets may not overlap and must be of equal size. > + * > + * @param dst_bitset > + * A pointer to the array of words making up the bitset. > + * @param src_bitset > + * A pointer to the array of words making up the bitset. > + * @param size > + * The size of the bitsets (in bits). > + */ > +__rte_experimental > +static inline void > +rte_bitset_copy(uint64_t *__rte_restrict dst_bitset, const uint64_t *__rte_restrict src_bitset, > + size_t size) > +{ > + rte_memcpy(dst_bitset, src_bitset, RTE_BITSET_SIZE(size)); > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Bitwise or two bitsets. > + * > + * Perform a bitwise OR operation on all bits in the two equal-size > + * bitsets @c src_bitset0 and @c src_bitset1, and store the results in > + * @c dst_bitset. > + * > + * @param dst_bitset > + * A pointer to the destination bitset. > + * @param src_bitset0 > + * A pointer to the first source bitset. > + * @param src_bitset1 > + * A pointer to the second source bitset. > + * @param size > + * The size of the bitsets (in bits). > + */ > +__rte_experimental > +static inline void > +rte_bitset_or(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1, > + size_t size) > +{ > + size_t i; > + > + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) > + dst_bitset[i] = src_bitset0[i] | src_bitset1[i]; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Bitwise and two bitsets. > + * > + * Perform a bitwise AND operation on all bits in the two equal-size > + * bitsets @c src_bitset0 and @c src_bitset1, and store the result in > + * @c dst_bitset. > + * > + * @param dst_bitset > + * A pointer to the destination bitset. > + * @param src_bitset0 > + * A pointer to the first source bitset. > + * @param src_bitset1 > + * A pointer to the second source bitset. > + * @param size > + * The size of the bitsets (in bits). > + */ > +__rte_experimental > +static inline void > +rte_bitset_and(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1, > + size_t size) > +{ > + size_t i; > + > + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) > + dst_bitset[i] = src_bitset0[i] & src_bitset1[i]; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Bitwise xor two bitsets. > + * > + * Perform a bitwise XOR operation on all bits in the two equal-size > + * bitsets @c src_bitset0 and @c src_bitset1, and store the result in > + * @c dst_bitset. > + * > + * @param dst_bitset > + * A pointer to the destination bitset. > + * @param src_bitset0 > + * A pointer to the first source bitset. > + * @param src_bitset1 > + * A pointer to the second source bitset. > + * @param size > + * The size of the bitsets (in bits). > + */ > +__rte_experimental > +static inline void > +rte_bitset_xor(uint64_t *dst_bitset, const uint64_t *src_bitset0, const uint64_t *src_bitset1, > + size_t size) > +{ > + size_t i; > + > + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) > + dst_bitset[i] = src_bitset0[i] ^ src_bitset1[i]; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Compute the bitwise complement of a bitset. > + * > + * Flip every bit in the @c src_bitset, and store the result in @c > + * dst_bitset. > + * > + * @param dst_bitset > + * A pointer to the destination bitset. > + * @param src_bitset > + * A pointer to the source bitset. > + * @param size > + * The size of the bitsets (in bits). > + */ > +__rte_experimental > +static inline void > +rte_bitset_complement(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size) > +{ > + size_t i; > + > + for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++) > + dst_bitset[i] = ~src_bitset[i]; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Shift bitset left. > + * > + * Perform a logical shift left of (multiply) @c src_bitset, and store > + * the result in @c dst_bitset. > + * > + * @param dst_bitset > + * A pointer to the destination bitset. > + * @param src_bitset > + * A pointer to the source bitset. > + * @param size > + * The size of the bitsets (in bits). > + * @param shift_bits > + * The number of bits to shift the bitset. > + */ > +__rte_experimental > +static inline void > +rte_bitset_shift_left(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size, > + size_t shift_bits) > +{ > + const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS; > + const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS; > + unsigned int dst_idx; > + > + for (dst_idx = 0; dst_idx < RTE_BITSET_NUM_WORDS(size); dst_idx++) { > + int src_high_idx = dst_idx - src_word_offset; > + uint64_t low_bits = 0; > + uint64_t high_bits = 0; > + > + if (src_high_idx >= 0) { > + int src_low_idx = src_high_idx - 1; > + > + high_bits = src_bitset[src_high_idx] << src_bit_offset; > + > + if (src_bit_offset > 0 && src_low_idx >= 0) > + low_bits = src_bitset[src_low_idx] >> > + (RTE_BITSET_WORD_BITS - src_bit_offset); > + } > + dst_bitset[dst_idx] = low_bits | high_bits; > + } > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Shift bitset right. > + * > + * Perform a logical shift right of (divide) @c src_bitset, and store > + * the result in @c dst_bitset. > + * > + * @param dst_bitset > + * A pointer to the destination bitset. > + * @param src_bitset > + * A pointer to the source bitset. > + * @param size > + * The size of the bitsets (in bits). > + * @param shift_bits > + * The number of bits to shift the bitset. > + */ > +__rte_experimental > +static inline void > +rte_bitset_shift_right(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size, > + size_t shift_bits) > +{ > + const int num_words = RTE_BITSET_NUM_WORDS(size); > + const uint64_t used_mask = __RTE_BITSET_USED_MASK(size); > + const int src_word_offset = shift_bits / RTE_BITSET_WORD_BITS; > + const int src_bit_offset = shift_bits % RTE_BITSET_WORD_BITS; > + int dst_idx; > + > + for (dst_idx = 0; dst_idx < num_words; dst_idx++) { > + int src_low_idx = src_word_offset + dst_idx; > + int src_high_idx = src_low_idx + 1; > + uint64_t src_low_word_bits = 0; > + uint64_t src_high_word_bits = 0; > + > + if (src_low_idx < num_words) { > + src_low_word_bits = src_bitset[src_low_idx]; > + > + if (src_low_idx == (num_words - 1)) > + src_low_word_bits &= used_mask; > + > + src_low_word_bits >>= src_bit_offset; > + > + if (src_bit_offset > 0 && src_high_idx < num_words) { > + src_high_word_bits = src_bitset[src_high_idx]; > + > + if (src_high_idx == (num_words - 1)) > + src_high_word_bits &= used_mask; > + > + src_high_word_bits <<= (RTE_BITSET_WORD_BITS - src_bit_offset); > + } > + } > + dst_bitset[dst_idx] = src_low_word_bits | src_high_word_bits; > + } > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Compare two bitsets. > + * > + * Compare two bitsets for equality. > + * > + * @param bitset_a > + * A pointer to the destination bitset. > + * @param bitset_b > + * A pointer to the source bitset. > + * @param size > + * The size of the bitsets (in bits). > + */ > +__rte_experimental > +static inline bool > +rte_bitset_equal(const uint64_t *bitset_a, const uint64_t *bitset_b, size_t size) > +{ > + size_t i; > + uint64_t last_a, last_b; > + > + for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++) > + if (bitset_a[i] != bitset_b[i]) > + return false; > + > + last_a = bitset_a[i] << __RTE_BITSET_UNUSED(size); > + last_b = bitset_b[i] << __RTE_BITSET_UNUSED(size); > + > + return last_a == last_b; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Converts a bitset to a string. > + * > + * This function prints a string representation of the bitstring to > + * the supplied buffer. > + * > + * Each bit is represented either by '0' or '1' in the output, with > + * the first (left-most) character in the output being the most > + * significant bit. The resulting string is NUL terminated. > + * > + * @param bitset > + * A pointer to the array of bitset 64-bit words. > + * @param size > + * The number of bits the bitset represent. > + * @param buf > + * A buffer to hold the output. > + * @param capacity > + * The size of the buffer. Must be @c size + 1 or larger. > + * @return > + * Returns the number of bytes written (i.e., @c size + 1), or -EINVAL > + * in case the buffer capacity was too small. > + */ > +__rte_experimental > +ssize_t > +rte_bitset_to_str(const uint64_t *bitset, size_t size, char *buf, size_t capacity); > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* _RTE_BITSET_H_ */ > diff --git a/lib/eal/version.map b/lib/eal/version.map > index e3ff412683..f493cd1ca7 100644 > --- a/lib/eal/version.map > +++ b/lib/eal/version.map > @@ -396,6 +396,9 @@ EXPERIMENTAL { > > # added in 24.03 > rte_vfio_get_device_info; # WINDOWS_NO_EXPORT > + > + # added in 24.11 > + rte_bitset_to_str; > }; > > INTERNAL {