All of lore.kernel.org
 help / color / mirror / Atom feed
* [RFC v3] eal: add bitset type
@ 2024-01-31 13:13 Mattias Rönnblom
  2024-01-31 16:02 ` Stephen Hemminger
                   ` (2 more replies)
  0 siblings, 3 replies; 115+ messages in thread
From: Mattias Rönnblom @ 2024-01-31 13:13 UTC (permalink / raw)
  To: dev; +Cc: hofors, Morten Brørup, Tyler Retzlaff, Mattias Rönnblom

Introduce a set of functions and macros that operate on sets of bits,
kept in arrays of 64-bit elements.

RTE bitset is designed for bitsets which are larger than what fits in
a single machine word (i.e., 64 bits). For very large bitsets, the
<rte_bitmap.h> API may be a more appropriate choice.

RFC v3:
 * Split the bitset from the htimer patchset, where it was originally
   hosted.
 * Rebase to current DPDK main.
 * Add note that rte_bitset_init() need not be called if bitset words
   have already been zeroed.
 * Use REGISTER_FAST_TEST instead of REGISTER_TEST_COMMAND.
 * Use rte_popcount64() instead of compiler builtin.

RFC v2:
 * Replaced <sys/types.h> with <stddef.h> include, to properly get
   size_t typedef.
 * Add <rte_compat.h> to get __rte_experimental in <rte_bitset.h>.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 app/test/meson.build         |   1 +
 app/test/test_bitset.c       | 645 +++++++++++++++++++++++++
 lib/eal/common/meson.build   |   1 +
 lib/eal/common/rte_bitset.c  |  29 ++
 lib/eal/include/meson.build  |   1 +
 lib/eal/include/rte_bitset.h | 884 +++++++++++++++++++++++++++++++++++
 lib/eal/version.map          |   3 +
 7 files changed, 1564 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/app/test/meson.build b/app/test/meson.build
index dcc93f4a43..e218be11d8 100644
--- a/app/test/meson.build
+++ b/app/test/meson.build
@@ -32,6 +32,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..688349b03b
--- /dev/null
+++ b/app/test/test_bitset.c
@@ -0,0 +1,645 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2023 Ericsson AB
+ */
+
+#include <stdlib.h>
+#include <inttypes.h>
+
+#include <rte_random.h>
+
+#include <rte_bitset.h>
+
+#include "test.h"
+
+#define MAGIC UINT64_C(0xdeadbeefdeadbeef)
+
+static void
+rand_buf(void *buf, size_t n)
+{
+	size_t i;
+
+	for (i = 0; i < n; i++)
+		((char *)buf)[i] = (char)rte_rand();
+}
+
+static uint64_t *
+alloc_bitset(size_t size)
+{
+	uint64_t *p;
+
+	p = malloc(RTE_BITSET_SIZE(size) + 2 * sizeof(uint64_t));
+
+	if (p == NULL)
+		rte_panic("Unable to allocate memory\n");
+
+	rand_buf(&p[0], RTE_BITSET_SIZE(size));
+
+	p[0] = MAGIC;
+	p[RTE_BITSET_NUM_WORDS(size) + 1] = MAGIC;
+
+	return p + 1;
+}
+
+
+static int
+free_bitset(uint64_t *bitset, size_t size)
+{
+	uint64_t *p;
+
+	p = bitset - 1;
+
+	if (p[0] != MAGIC)
+		return TEST_FAILED;
+
+	if (p[RTE_BITSET_NUM_WORDS(size) + 1] != MAGIC)
+		return TEST_FAILED;
+
+	free(p);
+
+	return TEST_SUCCESS;
+}
+
+static bool
+rand_bool(void)
+{
+	return rte_rand_max(2);
+}
+
+static void
+rand_bool_ary(bool *ary, size_t len)
+{
+	size_t i;
+
+	for (i = 0; i < len; i++)
+		ary[i] = rand_bool();
+}
+
+static int
+test_test_set_size(size_t size)
+{
+	size_t i;
+	bool reference[size];
+	uint64_t *bitset;
+
+	rand_bool_ary(reference, size);
+
+	bitset = alloc_bitset(size);
+
+	if (bitset == NULL)
+		return TEST_FAILED;
+
+	rte_bitset_init(bitset, size);
+
+	for (i = 0; i < size; i++) {
+		if (reference[i])
+			rte_bitset_set(bitset, i);
+		else
+			rte_bitset_clear(bitset, i);
+	}
+
+	for (i = 0; i < size; i++)
+		if (reference[i] != rte_bitset_test(bitset, i))
+			return TEST_FAILED;
+
+	if (free_bitset(bitset, size) != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+#define RAND_ITERATIONS (10000)
+#define RAND_SET_MAX_SIZE (1000)
+
+static int
+test_test_set(void)
+{
+	size_t i;
+
+	for (i = 0; i < RAND_ITERATIONS; i++) {
+		size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
+
+		if (test_test_set_size(size) != TEST_SUCCESS)
+			return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+static ssize_t
+find(const bool *ary, size_t num_bools, size_t start, size_t len, bool set)
+{
+	size_t i;
+
+	for (i = 0; i < len; i++) {
+		ssize_t idx = (start + i) % num_bools;
+
+		if (ary[idx] == set)
+			return idx;
+	}
+
+	return -1;
+}
+
+static ssize_t
+find_set(const bool *ary, size_t num_bools, size_t start, size_t len)
+{
+	return find(ary, num_bools, start, len, true);
+}
+
+static ssize_t
+find_clear(const bool *ary, size_t num_bools, size_t start, size_t len)
+{
+	return find(ary, num_bools, start, len, false);
+}
+
+#define FFS_ITERATIONS (100)
+
+static int
+test_find_size(size_t size, bool set)
+{
+	uint64_t *bitset;
+	bool reference[size];
+	size_t i;
+
+	bitset = alloc_bitset(size);
+
+	if (bitset == NULL)
+		return TEST_FAILED;
+
+	rte_bitset_init(bitset, size);
+
+	for (i = 0; i < size; i++) {
+		bool bit = rand_bool();
+		reference[i] = bit;
+
+		if (bit)
+			rte_bitset_set(bitset, i);
+		else /* redundant, still useful for testing */
+			rte_bitset_clear(bitset, i);
+	}
+
+	for (i = 0; i < FFS_ITERATIONS; i++) {
+		size_t start_bit = rte_rand_max(size);
+		size_t len = rte_rand_max(size + 1);
+		bool full_range = len == size && start_bit == 0;
+		bool wraps = start_bit + len > size;
+		ssize_t rc;
+
+		if (set) {
+			if (full_range && rand_bool())
+				rc = rte_bitset_find_first_set(bitset,
+							       size);
+			else if (wraps || rand_bool()) {
+				rc = rte_bitset_find_set_wrap(bitset, size,
+							      start_bit, len);
+
+			} else
+				rc = rte_bitset_find_set(bitset, size,
+							 start_bit, len);
+
+			if (rc != find_set(reference, size, start_bit,
+					   len))
+				return TEST_FAILED;
+		} else {
+			if (full_range && rand_bool())
+				rc = rte_bitset_find_first_clear(bitset,
+								 size);
+			else if (wraps || rand_bool())
+				rc = rte_bitset_find_clear_wrap(bitset,
+								size,
+								start_bit, len);
+			else
+				rc = rte_bitset_find_clear(bitset, size,
+							   start_bit, len);
+
+			if (rc != find_clear(reference, size, start_bit,
+					     len))
+				return TEST_FAILED;
+		}
+
+	}
+
+	if (free_bitset(bitset, size) != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_find_set_size(size_t size)
+{
+	return test_find_size(size, true);
+}
+
+static int
+test_find_clear_size(size_t size)
+{
+	return test_find_size(size, false);
+}
+
+static int
+test_find(void)
+{
+	size_t i;
+
+	for (i = 0; i < RAND_ITERATIONS; i++) {
+		size_t size = 2 + rte_rand_max(RAND_SET_MAX_SIZE - 2);
+
+		if (test_find_set_size(size) != TEST_SUCCESS)
+			return TEST_FAILED;
+
+		if (test_find_clear_size(size) != TEST_SUCCESS)
+			return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
+record_match(ssize_t match_idx, size_t size, int *calls)
+{
+	if (match_idx < 0 || (size_t)match_idx >= size)
+		return TEST_FAILED;
+
+	calls[match_idx]++;
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_foreach_size(ssize_t size, bool may_wrap, bool set)
+{
+	bool reference[size];
+	int calls[size];
+	uint64_t *bitset;
+	ssize_t i;
+	ssize_t start_bit;
+	ssize_t len;
+	bool full_range;
+	size_t total_calls = 0;
+
+	rand_bool_ary(reference, size);
+
+	bitset = alloc_bitset(size);
+
+	if (bitset == NULL)
+		return TEST_FAILED;
+
+	memset(calls, 0, sizeof(calls));
+
+	start_bit = rte_rand_max(size);
+	len = may_wrap ? rte_rand_max(size + 1) :
+		rte_rand_max(size - start_bit + 1);
+
+	rte_bitset_init(bitset, size);
+
+	/* random data in the unused bits should not matter */
+	rand_buf(bitset, RTE_BITSET_SIZE(size));
+
+	for (i = start_bit; i < start_bit + len; i++) {
+		size_t idx = i % size;
+
+		if (reference[idx])
+			rte_bitset_set(bitset, idx);
+		else
+			rte_bitset_clear(bitset, idx);
+
+		if (rte_bitset_test(bitset, idx) != reference[idx])
+			return TEST_FAILED;
+	}
+
+	full_range = (len == size && start_bit == 0);
+
+	/* XXX: verify iteration order as well */
+	if (set) {
+		if (full_range && rand_bool()) {
+			RTE_BITSET_FOREACH_SET(i, bitset, size) {
+				if (record_match(i, size, calls) !=
+				    TEST_SUCCESS)
+					return TEST_FAILED;
+			}
+		} else if (may_wrap) {
+			RTE_BITSET_FOREACH_SET_WRAP(i, bitset, size,
+						    start_bit, len) {
+				if (record_match(i, size, calls) !=
+				    TEST_SUCCESS) {
+					printf("failed\n");
+					return TEST_FAILED;
+				}
+			}
+		} else {
+			RTE_BITSET_FOREACH_SET_RANGE(i, bitset, size,
+						     start_bit, len) {
+				if (record_match(i, size, calls) !=
+				    TEST_SUCCESS)
+					return TEST_FAILED;
+			}
+		}
+	} else {
+		if (full_range && rand_bool()) {
+			RTE_BITSET_FOREACH_CLEAR(i, bitset, size)
+				if (record_match(i, size, calls) !=
+				    TEST_SUCCESS)
+					return TEST_FAILED;
+		} else if (may_wrap) {
+			RTE_BITSET_FOREACH_CLEAR_WRAP(i, bitset, size,
+						      start_bit, len) {
+				if (record_match(i, size, calls) !=
+				    TEST_SUCCESS)
+					return TEST_FAILED;
+			}
+		} else {
+			RTE_BITSET_FOREACH_CLEAR_RANGE(i, bitset, size,
+						       start_bit, len)
+				if (record_match(i, size, calls) !=
+				    TEST_SUCCESS)
+					return TEST_FAILED;
+		}
+	}
+
+	for (i = 0; i < len; i++) {
+		size_t idx = (start_bit + i) % size;
+
+		if (reference[idx] == set && calls[idx] != 1) {
+			printf("bit %zd shouldn't have been found %d "
+			       "times\n", idx, calls[idx]);
+			return TEST_FAILED;
+		}
+
+		if (reference[idx] != set && calls[idx] != 0) {
+			puts("bar");
+			return TEST_FAILED;
+		}
+
+		total_calls += calls[idx];
+	}
+
+	if (full_range) {
+		size_t count;
+
+		count = set ? rte_bitset_count_set(bitset, size) :
+			rte_bitset_count_clear(bitset, size);
+
+		if (count != total_calls)
+			return TEST_FAILED;
+	}
+
+	if (free_bitset(bitset, size) != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_foreach(void)
+{
+	size_t i;
+
+	for (i = 0; i < RAND_ITERATIONS; i++) {
+		size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
+
+		if (test_foreach_size(size, false, true) != TEST_SUCCESS)
+			return TEST_FAILED;
+
+		if (test_foreach_size(size, false, false) != TEST_SUCCESS)
+			return TEST_FAILED;
+
+		if (test_foreach_size(size, true, true) != TEST_SUCCESS)
+			return TEST_FAILED;
+
+		if (test_foreach_size(size, true, false) != TEST_SUCCESS)
+			return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_count_size(size_t size)
+{
+	uint64_t *bitset;
+
+	bitset = alloc_bitset(size);
+
+	if (bitset == NULL)
+		return TEST_FAILED;
+
+	rte_bitset_init(bitset, size);
+
+	if (rte_bitset_count_set(bitset, size) != 0)
+		return TEST_FAILED;
+
+	if (rte_bitset_count_clear(bitset, size) != size)
+		return TEST_FAILED;
+
+	rte_bitset_set_all(bitset, size);
+
+	if (rte_bitset_count_set(bitset, size) != size)
+		return TEST_FAILED;
+
+	if (rte_bitset_count_clear(bitset, size) != 0)
+		return TEST_FAILED;
+
+	rte_bitset_clear_all(bitset, size);
+
+	if (rte_bitset_count_set(bitset, size) != 0)
+		return TEST_FAILED;
+
+	if (rte_bitset_count_clear(bitset, size) != size)
+		return TEST_FAILED;
+
+	rte_bitset_set(bitset, rte_rand_max(size));
+
+	if (rte_bitset_count_set(bitset, size) != 1)
+		return TEST_FAILED;
+
+	if (rte_bitset_count_clear(bitset, size) != (size - 1))
+		return TEST_FAILED;
+
+	rte_bitset_clear_all(bitset, size);
+	if (rte_bitset_count_set(bitset, size) != 0)
+		return TEST_FAILED;
+	if (rte_bitset_count_clear(bitset, size) != size)
+		return TEST_FAILED;
+
+	rte_bitset_set_all(bitset, size);
+	if (rte_bitset_count_set(bitset, size) != size)
+		return TEST_FAILED;
+	if (rte_bitset_count_clear(bitset, size) != 0)
+		return TEST_FAILED;
+
+	if (free_bitset(bitset, size) != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_count(void)
+{
+	size_t i;
+
+	if (test_count_size(128) != TEST_SUCCESS)
+		return TEST_FAILED;
+	if (test_count_size(1) != TEST_SUCCESS)
+		return TEST_FAILED;
+	if (test_count_size(63) != TEST_SUCCESS)
+		return TEST_FAILED;
+	if (test_count_size(64) != TEST_SUCCESS)
+		return TEST_FAILED;
+	if (test_count_size(65) != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	for (i = 0; i < RAND_ITERATIONS; i++) {
+		size_t size = 1 + rte_rand_max(RAND_SET_MAX_SIZE - 1);
+
+		if (test_count_size(size) != TEST_SUCCESS)
+			return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+#define GEN_DECLARE(size)						\
+	{								\
+		RTE_BITSET_DECLARE(bitset, size);			\
+		size_t idx;						\
+									\
+		idx = rte_rand_max(size);				\
+		rte_bitset_init(bitset, size);				\
+									\
+		rte_bitset_set(bitset, idx);				\
+		if (!rte_bitset_test(bitset, idx))			\
+			return TEST_FAILED;				\
+		if (rte_bitset_count_set(bitset, size) != 1)		\
+			return TEST_FAILED;				\
+		return TEST_SUCCESS;					\
+	}
+
+static int
+test_define(void)
+{
+	GEN_DECLARE(1);
+	GEN_DECLARE(64);
+	GEN_DECLARE(65);
+	GEN_DECLARE(4097);
+}
+
+static int
+test_equal(void)
+{
+	const size_t size = 100;
+	RTE_BITSET_DECLARE(bitset_a, size);
+	RTE_BITSET_DECLARE(bitset_b, size);
+
+	rand_buf(bitset_a, RTE_BITSET_SIZE(size));
+	rand_buf(bitset_b, RTE_BITSET_SIZE(size));
+
+	rte_bitset_init(bitset_a, size);
+	rte_bitset_init(bitset_b, size);
+
+	rte_bitset_set(bitset_a, 9);
+	rte_bitset_set(bitset_b, 9);
+	rte_bitset_set(bitset_a, 90);
+	rte_bitset_set(bitset_b, 90);
+
+	if (!rte_bitset_equal(bitset_a, bitset_b, size))
+		return TEST_FAILED;
+
+	/* set unused bit, which should be ignored */
+	rte_bitset_set(&bitset_a[1], 60);
+
+	if (!rte_bitset_equal(bitset_a, bitset_b, size))
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_copy(void)
+{
+	const size_t size = 100;
+	RTE_BITSET_DECLARE(bitset_a, size);
+	RTE_BITSET_DECLARE(bitset_b, size);
+
+	rand_buf(bitset_a, RTE_BITSET_SIZE(size));
+	rand_buf(bitset_b, RTE_BITSET_SIZE(size));
+
+	if (rte_bitset_equal(bitset_a, bitset_b, size))
+		return TEST_FAILED;
+
+	rte_bitset_copy(bitset_a, bitset_b, size);
+
+	if (!rte_bitset_equal(bitset_a, bitset_b, size))
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_to_str(void)
+{
+	char buf[1024];
+	RTE_BITSET_DECLARE(bitset, 128);
+
+	rte_bitset_init(bitset, 128);
+	rte_bitset_set(bitset, 1);
+
+	if (rte_bitset_to_str(bitset, 2, buf, 3) != 3)
+		return TEST_FAILED;
+	if (strcmp(buf, "10") != 0)
+		return TEST_FAILED;
+
+	rte_bitset_set(bitset, 0);
+
+	if (rte_bitset_to_str(bitset, 1, buf, sizeof(buf)) != 2)
+		return TEST_FAILED;
+	if (strcmp(buf, "1") != 0)
+		return TEST_FAILED;
+
+	rte_bitset_init(bitset, 99);
+	rte_bitset_set(bitset, 98);
+
+	if (rte_bitset_to_str(bitset, 99, buf, sizeof(buf)) != 100)
+		return TEST_FAILED;
+
+	if (buf[0] != '1' || strchr(&buf[1], '1') != NULL)
+		return TEST_FAILED;
+
+	if (rte_bitset_to_str(bitset, 128, buf, 64) != -EINVAL)
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_bitset(void)
+{
+	if (test_test_set() != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	if (test_find() != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	if (test_foreach() != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	if (test_count() != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	if (test_define() != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	if (test_equal() != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	if (test_copy() != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	if (test_to_str() != TEST_SUCCESS)
+		return TEST_FAILED;
+
+	return TEST_SUCCESS;
+}
+
+REGISTER_FAST_TEST(bitset_autotest, true, true, test_bitset);
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..35e55a64db
--- /dev/null
+++ b/lib/eal/common/rte_bitset.c
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2023 Ericsson AB
+ */
+
+#include <errno.h>
+
+#include "rte_bitset.h"
+
+ssize_t
+rte_bitset_to_str(const uint64_t *bitset, size_t num_bits, char *buf,
+		  size_t capacity)
+{
+	size_t i;
+
+	if (capacity < (num_bits + 1))
+		return -EINVAL;
+
+	for (i = 0; i < num_bits; i++) {
+		bool value;
+
+		value = rte_bitset_test(bitset, num_bits - 1 - i);
+
+		buf[i] = value ? '1' : '0';
+	}
+
+	buf[num_bits] = '\0';
+
+	return num_bits + 1;
+}
diff --git a/lib/eal/include/meson.build b/lib/eal/include/meson.build
index e94b056d46..4b5f120a66 100644
--- a/lib/eal/include/meson.build
+++ b/lib/eal/include/meson.build
@@ -5,6 +5,7 @@ includes += include_directories('.')
 
 headers += files(
         'rte_alarm.h',
+        'rte_bitset.h',
         'rte_bitmap.h',
         'rte_bitops.h',
         'rte_branch_prediction.h',
diff --git a/lib/eal/include/rte_bitset.h b/lib/eal/include/rte_bitset.h
new file mode 100644
index 0000000000..24c6ec3703
--- /dev/null
+++ b/lib/eal/include/rte_bitset.h
@@ -0,0 +1,884 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2023 Ericsson AB
+ */
+
+#ifndef _RTE_BITSET_H_
+#define _RTE_BITSET_H_
+
+/**
+ * @file
+ * RTE Bitset
+ *
+ * This file provides functions and macros for querying and
+ * manipulating sets of bits kept in arrays of @c uint64_t-sized
+ * elements.
+ *
+ * The bits in a bitset are numbered from 0 to @c size - 1, with the
+ * lowest index being the least significant bit.
+ *
+ * The bitset array must be properly aligned.
+ *
+ * For optimal performance, the @c size parameter, required by
+ * many of the API's functions, should be a compile-time constant.
+ *
+ * For large bitsets, the rte_bitmap.h API may be more appropriate.
+ *
+ * @warning
+ * All functions modifying a bitset may overwrite any unused bits of
+ * the last word. Such unused bits are ignored by all functions reading
+ * bits.
+ *
+ */
+
+#include <limits.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include <rte_bitops.h>
+#include <rte_branch_prediction.h>
+#include <rte_common.h>
+#include <rte_compat.h>
+#include <rte_debug.h>
+#include <rte_memcpy.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * The size (in bytes) of each element in the array used to represent
+ * a bitset.
+ */
+#define RTE_BITSET_WORD_SIZE (sizeof(uint64_t))
+
+/**
+ * The size (in bits) of each element in the array used to represent
+ * a bitset.
+ */
+#define RTE_BITSET_WORD_BITS (RTE_BITSET_WORD_SIZE * CHAR_BIT)
+
+/**
+ * Computes the number of words required to store @c size bits.
+ */
+#define RTE_BITSET_NUM_WORDS(size)			       \
+	((size + RTE_BITSET_WORD_BITS - 1) / RTE_BITSET_WORD_BITS)
+
+/**
+ * Computes the amount of memory (in bytes) required to fit a bitset
+ * holding @c size bits.
+ */
+#define RTE_BITSET_SIZE(size)					\
+	((size_t)(RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_SIZE))
+
+#define __RTE_BITSET_WORD_IDX(bit_num) ((bit_num) / RTE_BITSET_WORD_BITS)
+#define __RTE_BITSET_BIT_OFFSET(bit_num) ((bit_num) % RTE_BITSET_WORD_BITS)
+#define __RTE_BITSET_UNUSED(size)				\
+	((RTE_BITSET_NUM_WORDS(size) * RTE_BITSET_WORD_BITS) \
+	 - (size))
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Declare a bitset.
+ *
+ * Declare (e.g., as a struct field) or define (e.g., as a stack
+ * variable) a bitset of the specified size.
+ *
+ * @param size
+ *   The number of bits the bitset must be able to represent. Must be
+ *   a compile-time constant.
+ * @param name
+ *   The field or variable name of the resulting definition.
+ */
+#define RTE_BITSET_DECLARE(name, size)		\
+	uint64_t name[RTE_BITSET_NUM_WORDS(size)]
+
+/* XXX: should one include flags here and use to avoid a comparison? */
+/* XXX: would this be better off as a function? */
+
+#define __RTE_BITSET_FOREACH_LEFT(var, size, start_bit, len)		\
+	((len) - 1 - ((var) >= (start_bit) ? (var) - (start_bit) :	\
+		  (size) - (start_bit) + (var)))
+
+#define __RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, flags)	\
+	for ((var) = __rte_bitset_find(bitset, size, start_bit, len,	\
+				       flags);				\
+	     (var) != -1;						\
+	     (var) = __RTE_BITSET_FOREACH_LEFT(var, size, start_bit,	\
+					       len) > 0	?		\
+		     __rte_bitset_find(bitset, size,			\
+				       ((var) + 1) % (size),		\
+				       __RTE_BITSET_FOREACH_LEFT(var,	\
+								 size,	\
+								 start_bit, \
+								 len),	\
+				       flags) : -1)
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Iterate over all bits set.
+ *
+ * This macro iterates over all bits set (i.e., all ones) in the
+ * bitset, in the forward direction (i.e., starting with the least
+ * significant '1').
+ *
+ * @param var
+ *   An iterator variable of type @c ssize_t. For each successive
+ *   iteration, this variable will hold the bit index of a set bit.
+ * @param bitset
+ *   A <tt>const uint64_t *</tt> pointer to the bitset array.
+ * @param size
+ *   The size of the bitset (in bits).
+ */
+
+#define RTE_BITSET_FOREACH_SET(var, bitset, size)			\
+	__RTE_BITSET_FOREACH(var, bitset, size, 0, size, 0)
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Iterate over all bits cleared.
+ *
+ * This macro iterates over all bits cleared in the bitset, in the
+ * forward direction (i.e., starting with the lowest-indexed set bit).
+ *
+ * @param var
+ *   An iterator variable of type @c ssize_t. For each successive iteration,
+ *   this variable will hold the bit index of a cleared bit.
+ * @param bitset
+ *   A <tt>const uint64_t *</tt> pointer to the bitset array.
+ * @param size
+ *   The size of the bitset (in bits).
+ */
+
+#define RTE_BITSET_FOREACH_CLEAR(var, bitset, size)			\
+	__RTE_BITSET_FOREACH(var, bitset, size, 0, size,		\
+			     __RTE_BITSET_FIND_FLAG_FIND_CLEAR)
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Iterate over all bits set within a range.
+ *
+ * This macro iterates over all bits set (i.e., all ones) in the
+ * specified range, in the forward direction (i.e., starting with the
+ * least significant '1').
+ *
+ * @param var
+ *   An iterator variable of type @c ssize_t. For each successive iteration,
+ *   this variable will hold the bit index of a set bit.
+ * @param bitset
+ *   A <tt>const uint64_t *</tt> pointer to the bitset array.
+ * @param size
+ *   The size of the bitset (in bits).
+ * @param start_bit
+ *   The index of the first bit to check. Must be less than @c size.
+ * @param len
+ *   The length (in bits) of the range. @c start_bit + @c len must be less
+ *   than or equal to @c size.
+ */
+
+#define RTE_BITSET_FOREACH_SET_RANGE(var, bitset, size, start_bit,     \
+				     len)			       \
+	__RTE_BITSET_FOREACH(var, bitset, size, start_bit, len, 0)
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Iterate over all cleared bits within a range.
+ *
+ * This macro iterates over all bits cleared (i.e., all zeroes) in the
+ * specified range, in the forward direction (i.e., starting with the
+ * least significant '0').
+ *
+ * @param var
+ *   An iterator variable of type @c ssize_t. For each successive iteration,
+ *   this variable will hold the bit index of a set bit.
+ * @param bitset
+ *   A <tt>const uint64_t *</tt> pointer to the bitset array.
+ * @param size
+ *   The size of the bitset (in bits).
+ * @param start_bit
+ *   The index of the first bit to check. Must be less than @c size.
+ * @param len
+ *   The length (in bits) of the range. @c start_bit + @c len must be less
+ *   than or equal to @c size.
+ */
+
+#define RTE_BITSET_FOREACH_CLEAR_RANGE(var, bitset, size, start_bit,	\
+				       len)				\
+	__RTE_BITSET_FOREACH(var, bitset, size, start_bit, len,		\
+			     __RTE_BITSET_FIND_FLAG_FIND_CLEAR)
+
+#define RTE_BITSET_FOREACH_SET_WRAP(var, bitset, size, start_bit,      \
+				    len)			       \
+	__RTE_BITSET_FOREACH(var, bitset, size, start_bit, len,	       \
+			     __RTE_BITSET_FIND_FLAG_WRAP)
+
+#define RTE_BITSET_FOREACH_CLEAR_WRAP(var, bitset, size, start_bit,	\
+				       len)				\
+	__RTE_BITSET_FOREACH(var, bitset, size, start_bit, len,		\
+			     __RTE_BITSET_FIND_FLAG_WRAP |		\
+			     __RTE_BITSET_FIND_FLAG_FIND_CLEAR)
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Initializes a bitset.
+ *
+ * All bits are cleared.
+ *
+ * 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.
+ *
+ * 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 += rte_popcount64(bitset[i]);
+
+	unused_mask = UINT64_MAX >> __RTE_BITSET_UNUSED(size);
+	total += rte_popcount64(bitset[i] & unused_mask);
+
+	return total;
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Count all cleared bits.
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param size
+ *   The size of the bitset (in bits).
+ * @return
+ *   Returns the number of '0' bits in the bitset.
+ */
+
+__rte_experimental
+static inline size_t
+rte_bitset_count_clear(const uint64_t *bitset, size_t size)
+{
+	return size - rte_bitset_count_set(bitset, size);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Test if a bit is set.
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param bit_num
+ *   Index of the bit to test. Index 0 is the least significant bit.
+ * @return
+ *   Returns true if the bit is '1', and false if the bit is '0'.
+ */
+
+__rte_experimental
+static inline bool
+rte_bitset_test(const uint64_t *bitset, size_t bit_num)
+{
+	size_t word;
+	size_t offset;
+
+	word = __RTE_BITSET_WORD_IDX(bit_num);
+	offset = __RTE_BITSET_BIT_OFFSET(bit_num);
+
+	return (bitset[word] >> offset) & 1;
+}
+
+#define __RTE_BITSET_FIND_FLAG_FIND_CLEAR (1U << 0)
+#define __RTE_BITSET_FIND_FLAG_WRAP (1U << 1)
+
+__rte_experimental
+static inline ssize_t
+__rte_bitset_find_nowrap(const uint64_t *bitset, size_t __rte_unused size,
+			 size_t start_bit, size_t len, bool find_clear)
+{
+	size_t word_idx;
+	size_t offset;
+	size_t end_bit = start_bit + len;
+
+	RTE_ASSERT(end_bit <= size);
+
+	if (unlikely(len == 0))
+		return -1;
+
+	word_idx = __RTE_BITSET_WORD_IDX(start_bit);
+	offset = __RTE_BITSET_BIT_OFFSET(start_bit);
+
+	while (word_idx <= __RTE_BITSET_WORD_IDX(end_bit - 1)) {
+		uint64_t word;
+		int word_ffs;
+
+		word = bitset[word_idx];
+		if (find_clear)
+			word = ~word;
+
+		word >>= offset;
+
+		word_ffs = __builtin_ffsll(word);
+
+		if (word_ffs != 0) {
+			ssize_t ffs = start_bit + word_ffs - 1;
+
+			/*
+			 * Check if set bit were among the last,
+			 * unused bits, in the last word.
+			 */
+			if (unlikely(ffs >= (ssize_t)end_bit))
+				return -1;
+
+			return ffs;
+		}
+
+		start_bit += (RTE_BITSET_WORD_BITS - offset);
+		word_idx++;
+		offset = 0;
+	}
+
+	return -1;
+
+}
+
+__rte_experimental
+static inline ssize_t
+__rte_bitset_find(const uint64_t *bitset, size_t size, size_t start_bit,
+		  size_t len, unsigned int flags)
+{
+	bool find_clear = flags & __RTE_BITSET_FIND_FLAG_FIND_CLEAR;
+	bool may_wrap = flags & __RTE_BITSET_FIND_FLAG_WRAP;
+	bool does_wrap = (start_bit + len) > size;
+	ssize_t rc;
+
+	RTE_ASSERT(len <= size);
+	if (!may_wrap)
+		RTE_ASSERT(!does_wrap);
+
+	if (may_wrap && does_wrap) {
+		size_t len0 = size - start_bit;
+		size_t len1 = len - len0;
+
+		rc = __rte_bitset_find_nowrap(bitset, size, start_bit, len0,
+					      find_clear);
+		if (rc < 0)
+			rc =  __rte_bitset_find_nowrap(bitset, size,
+						       0, len1, find_clear);
+	} else
+		rc = __rte_bitset_find_nowrap(bitset, size, start_bit,
+					      len, find_clear);
+
+	return rc;
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Find first bit set.
+ *
+ * Scans the bitset in the forward direction (i.e., starting at the
+ * least significant bit), and returns the index of the first '1'.
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param size
+ *   The size of the bitset (in bits).
+ * @return
+ *   Returns the index of the least significant '1', or -1 if all
+ *   bits are '0'.
+ */
+
+__rte_experimental
+static inline ssize_t
+rte_bitset_find_first_set(const uint64_t *bitset, size_t size)
+{
+	return __rte_bitset_find(bitset, size, 0, size, 0);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Find first bit set at offset.
+ *
+ * Scans the bitset in the forward direction (i.e., starting at the
+ * least significant bit), starting at an offset @c start_bit into the
+ * bitset, and returns the index of the first '1' encountered.
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param size
+ *   The size of the bitset (in bits).
+ * @param start_bit
+ *   The index of the first bit to check. Must be less than @c size.
+ * @param len
+ *   The number of bits to scan. @c start_bit + @c len must be less
+ *   than or equal to @c size.
+ * @return
+ *   Returns the index of the least significant '1', or -1 if all
+ *   bits are '0'.
+ */
+
+__rte_experimental
+static inline ssize_t
+rte_bitset_find_set(const uint64_t *bitset, size_t size,
+		    size_t start_bit, size_t len)
+{
+	return __rte_bitset_find(bitset, size, start_bit, len, 0);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Find first bit set at offset, with wrap-around.
+ *
+ * Scans the bitset in the forward direction (i.e., starting at the
+ * least significant bit), starting at an offset @c start_bit into the
+ * bitset. If no '1' is encountered before the end of the bitset, the search
+ * will continue at index 0.
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param size
+ *   The size of the bitset (in bits).
+ * @param start_bit
+ *   The index of the first bit to check. Must be less than @c size.
+ * @param len
+ *   The number of bits to scan. @c start_bit + @c len must be less
+ *   than or equal to @c size.
+ * @return
+ *   Returns the index of the least significant '1', or -1 if all
+ *   bits are '0'.
+ */
+
+__rte_experimental
+static inline ssize_t
+rte_bitset_find_set_wrap(const uint64_t *bitset, size_t size,
+			 size_t start_bit, size_t len)
+{
+	return __rte_bitset_find(bitset, size, start_bit, len,
+				 __RTE_BITSET_FIND_FLAG_WRAP);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Find first cleared bit.
+ *
+ * Scans the bitset in the forward direction (i.e., starting at the
+ * least significant bit), and returns the index of the first '0'.
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param size
+ *   The size of the bitset (in bits).
+ * @return
+ *   Returns the index of the least significant '0', or -1 if all
+ *   bits are '1'.
+ */
+
+__rte_experimental
+static inline ssize_t
+rte_bitset_find_first_clear(const uint64_t *bitset, size_t size)
+{
+	return __rte_bitset_find(bitset, size, 0, size,
+				 __RTE_BITSET_FIND_FLAG_FIND_CLEAR);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Find first cleared bit at offset.
+ *
+ * Scans the bitset in the forward direction (i.e., starting at the
+ * least significant bit), starting at an offset @c start_bit into the
+ * bitset, and returns the index of the first '0' encountered.
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param size
+ *   The size of the bitset (in bits).
+ * @param start_bit
+ *   The index of the first bit to check. Must be less than @c size.
+ * @param len
+ *   The number of bits to scan. @c start_bit + @c len must be less
+ *   than or equal to @c size.
+ * @return
+ *   Returns the index of the least significant '0', or -1 if all
+ *   bits are '1'.
+ */
+
+__rte_experimental
+static inline ssize_t
+rte_bitset_find_clear(const uint64_t *bitset, size_t size,
+			   size_t start_bit, size_t len)
+{
+	return __rte_bitset_find(bitset, size, start_bit, len,
+				 __RTE_BITSET_FIND_FLAG_FIND_CLEAR);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Find first cleared bit at offset, with wrap-around.
+ *
+ * Scans the bitset in the forward direction (i.e., starting at the
+ * least significant bit), starting at an offset @c start_bit into the
+ * bitset. If no '0' is encountered before the end of the bitset, the
+ * search will continue at index 0.
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param size
+ *   The size of the bitset (in bits).
+ * @param start_bit
+ *   The index of the first bit to check. Must be less than @c size.
+ * @param len
+ *   The number of bits to scan. @c start_bit + @c len must be less
+ *   than or equal to @c size.
+ * @return
+ *   Returns the index of the least significant '0', or -1 if all
+ *   bits are '1'.
+ */
+
+__rte_experimental
+static inline ssize_t
+rte_bitset_find_clear_wrap(const uint64_t *bitset, size_t size,
+			   size_t start_bit, size_t len)
+{
+	return __rte_bitset_find(bitset, size, start_bit, len,
+				 __RTE_BITSET_FIND_FLAG_FIND_CLEAR |
+				 __RTE_BITSET_FIND_FLAG_WRAP);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Copy bitset.
+ *
+ * Copy the bits of the @c src_bitset to the @c dst_bitset.
+ *
+ * The bitsets may not overlap and must be of equal size.
+ *
+ * @param dst_bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param src_bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param size
+ *   The size of the bitsets (in bits).
+ */
+
+__rte_experimental
+static inline void
+rte_bitset_copy(uint64_t *__rte_restrict dst_bitset,
+		const uint64_t *__rte_restrict src_bitset,
+		size_t size)
+{
+	rte_memcpy(dst_bitset, src_bitset, RTE_BITSET_SIZE(size));
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitwise or two bitsets.
+ *
+ * Perform a bitwise OR operation on all bits in the two equal-size
+ * bitsets @c dst_bitset and @c src_bitset, and store the results in
+ * @c dst_bitset.
+ *
+ * @param dst_bitset
+ *   A pointer to the destination bitset.
+ * @param src_bitset
+ *   A pointer to the source bitset.
+ * @param size
+ *   The size of the bitsets (in bits).
+ */
+
+__rte_experimental
+static inline void
+rte_bitset_or(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size)
+{
+	size_t i;
+
+	for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
+		dst_bitset[i] |= src_bitset[i];
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitwise and two bitsets.
+ *
+ * Perform a bitwise AND operation on all bits in the two equal-size
+ * bitsets @c dst_bitset and @c src_bitset, and store the results in
+ * @c dst_bitset.
+ *
+ * @param dst_bitset
+ *   A pointer to the destination bitset.
+ * @param src_bitset
+ *   A pointer to the source bitset.
+ * @param size
+ *   The size of the bitsets (in bits).
+ */
+
+__rte_experimental
+static inline void
+rte_bitset_and(uint64_t *dst_bitset, const uint64_t *src_bitset, size_t size)
+{
+	size_t i;
+
+	for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
+		dst_bitset[i] &= src_bitset[i];
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Bitwise xor two bitsets.
+ *
+ * Perform a bitwise XOR operation on all bits in the two equal-size
+ * bitsets @c dst_bitset and @c src_bitset, and store the results in
+ * @c dst_bitset.
+ *
+ * @param dst_bitset
+ *   A pointer to the destination bitset.
+ * @param src_bitset
+ *   A pointer to the source bitset.
+ * @param size
+ *   The size of the bitsets (in bits).
+ */
+
+__rte_experimental
+static inline void
+rte_bitset_xor(uint64_t *__rte_restrict dst_bitset,
+	       const uint64_t *__rte_restrict src_bitset, size_t size)
+{
+	size_t i;
+
+	for (i = 0; i < RTE_BITSET_NUM_WORDS(size); i++)
+		dst_bitset[i] ^= src_bitset[i];
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Compare two bitsets.
+ *
+ * Compare two bitsets for equality.
+ *
+ * @param bitset_a
+ *   A pointer to the destination bitset.
+ * @param bitset_b
+ *   A pointer to the source bitset.
+ * @param size
+ *   The size of the bitsets (in bits).
+ */
+
+__rte_experimental
+static inline bool
+rte_bitset_equal(const uint64_t *bitset_a, const uint64_t *bitset_b,
+		 size_t size)
+{
+	size_t i;
+	uint64_t last_a, last_b;
+
+	for (i = 0; i < RTE_BITSET_NUM_WORDS(size) - 1; i++)
+		if (bitset_a[i] != bitset_b[i])
+			return false;
+
+	last_a = bitset_a[i] << __RTE_BITSET_UNUSED(size);
+	last_b = bitset_b[i] << __RTE_BITSET_UNUSED(size);
+
+	return last_a == last_b;
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Converts a bitset to a string.
+ *
+ * This function prints a string representation of the bitstring to
+ * the supplied buffer.
+ *
+ * Each bit is represented either by '0' or '1' in the output. The
+ * resulting string is NUL terminated.
+ *
+ * @param bitset
+ *   A pointer to the array of bitset 64-bit words.
+ * @param size
+ *   The number of bits the bitset represent.
+ * @param buf
+ *   A buffer to hold the output.
+ * @param capacity
+ *   The size of the buffer. Must be @c size + 1 or larger.
+ * @return
+ *   Returns the number of bytes written (i.e., @c size + 1), or -EINVAL
+ *   in case the buffer capacity was too small.
+ */
+
+__rte_experimental
+ssize_t
+rte_bitset_to_str(const uint64_t *bitset, size_t size, char *buf,
+		  size_t capacity);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_BITSET_H_ */
diff --git a/lib/eal/version.map b/lib/eal/version.map
index 5e0cd47c82..639ccfe4b0 100644
--- a/lib/eal/version.map
+++ b/lib/eal/version.map
@@ -393,6 +393,9 @@ EXPERIMENTAL {
 	# added in 23.07
 	rte_memzone_max_get;
 	rte_memzone_max_set;
+
+	# added in 24.03
+	rte_bitset_to_str;
 };
 
 INTERNAL {
-- 
2.34.1


^ permalink raw reply related	[flat|nested] 115+ messages in thread

end of thread, other threads:[~2024-12-05  0:40 UTC | newest]

Thread overview: 115+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-01-31 13:13 [RFC v3] eal: add bitset type Mattias Rönnblom
2024-01-31 16:02 ` Stephen Hemminger
2024-01-31 16:28   ` Mattias Rönnblom
2024-01-31 16:06 ` Stephen Hemminger
2024-01-31 18:45   ` Mattias Rönnblom
2024-02-01  8:04     ` Morten Brørup
2024-02-02 10:19       ` Mattias Rönnblom
2024-02-02 12:42         ` Morten Brørup
2024-02-16 10:23 ` [RFC v4 1/4] " Mattias Rönnblom
2024-02-16 10:23   ` [RFC v4 2/4] eal: add bitset test suite Mattias Rönnblom
2024-02-16 10:23   ` [RFC v4 3/4] service: use multi-word bitset to represent service flags Mattias Rönnblom
2024-02-16 10:23   ` [RFC v4 4/4] event/dsw: optimize serving port logic Mattias Rönnblom
2024-05-05  7:33   ` [RFC v5 1/6] eal: add bitset type Mattias Rönnblom
2024-05-05  7:33     ` [RFC v5 2/6] eal: add bitset test suite Mattias Rönnblom
2024-05-05  7:33     ` [RFC v5 3/6] eal: add atomic bitset functions Mattias Rönnblom
2024-05-05  7:33     ` [RFC v5 4/6] eal: add unit tests for atomic bitset operations Mattias Rönnblom
2024-05-05  7:33     ` [RFC v5 5/6] service: use multi-word bitset to represent service flags Mattias Rönnblom
2024-05-05  7:33     ` [RFC v5 6/6] event/dsw: optimize serving port logic Mattias Rönnblom
2024-08-09 20:14     ` [PATCH 1/6] eal: add bitset type Mattias Rönnblom
2024-08-09 20:14       ` [PATCH 2/6] eal: add bitset test suite Mattias Rönnblom
2024-09-12  4:51         ` Tyler Retzlaff
2024-08-09 20:14       ` [PATCH 3/6] eal: add atomic bitset functions Mattias Rönnblom
2024-09-12  4:51         ` Tyler Retzlaff
2024-08-09 20:14       ` [PATCH 4/6] eal: add unit tests for atomic bitset operations Mattias Rönnblom
2024-09-12  4:52         ` Tyler Retzlaff
2024-10-09 20:29           ` Morten Brørup
2024-12-05  0:40             ` Tyler Retzlaff
2024-08-09 20:14       ` [PATCH 5/6] service: use multi-word bitset to represent service flags Mattias Rönnblom
2024-09-12  4:52         ` Tyler Retzlaff
2024-08-09 20:14       ` [PATCH 6/6] event/dsw: add support for larger port count Mattias Rönnblom
2024-09-12  4:53         ` Tyler Retzlaff
2024-08-20 17:09       ` [PATCH 1/6] eal: add bitset type Mattias Rönnblom
2024-09-02 13:55       ` Morten Brørup
2024-09-02 14:46         ` Mattias Rönnblom
2024-09-02 14:49         ` Mattias Rönnblom
2024-09-12  4:51       ` Tyler Retzlaff
2024-09-17  9:36       ` [PATCH v7 0/6] Improve EAL bit operations API Mattias Rönnblom
2024-09-17  9:36         ` [PATCH v7 1/6] dpdk: do not force C linkage on include file dependencies Mattias Rönnblom
2024-09-17 10:48           ` [PATCH v8 0/6] Improve EAL bit operations API Mattias Rönnblom
2024-09-17 10:48             ` [PATCH v8 1/6] dpdk: do not force C linkage on include file dependencies Mattias Rönnblom
2024-09-18  9:04               ` [PATCH v9 0/6] Improve EAL bit operations API Mattias Rönnblom
2024-09-18  9:04                 ` [PATCH v9 1/6] dpdk: do not force C linkage on include file dependencies Mattias Rönnblom
2024-09-19 19:31                   ` [PATCH v10 0/7] Improve EAL bit operations API Mattias Rönnblom
2024-09-19 19:31                     ` [PATCH v10 1/7] buildtools/chkincs: relax C linkage requirement Mattias Rönnblom
2024-09-20  6:24                       ` [PATCH v11 0/7] Improve EAL bit operations API Mattias Rönnblom
2024-09-20  6:24                         ` [PATCH v11 1/7] buildtools/chkincs: relax C linkage requirement Mattias Rönnblom
2024-09-20 10:47                           ` [PATCH v12 0/7] Improve EAL bit operations API Mattias Rönnblom
2024-09-20 10:47                             ` [PATCH v12 1/7] buildtools/chkincs: relax C linkage requirement Mattias Rönnblom
2024-10-03 16:47                               ` Robin Jarry
2024-10-04  7:31                                 ` Mattias Rönnblom
2024-10-04  8:05                                   ` Robin Jarry
2024-10-04  8:40                                     ` Mattias Rönnblom
2024-10-04 11:51                                       ` Robin Jarry
2024-10-04 12:19                                         ` Thomas Monjalon
2024-10-06  8:55                                         ` Mattias Rönnblom
2024-10-06  9:47                                           ` Mattias Rönnblom
2024-10-06 12:25                                             ` Robin Jarry
2024-10-06 13:09                                               ` Robin Jarry
2024-10-06 14:17                                               ` Mattias Rönnblom
2024-10-06 15:58                                                 ` Robin Jarry
2024-10-10 10:24                                                   ` Mattias Rönnblom
2024-10-10 10:39                                                     ` Bruce Richardson
2024-09-20 10:47                             ` [PATCH v12 2/7] dpdk: use C linkage only where appropriate Mattias Rönnblom
2024-09-20 10:47                             ` [PATCH v12 3/7] eal: extend bit manipulation functionality Mattias Rönnblom
2024-09-20 10:47                             ` [PATCH v12 4/7] eal: add unit tests for bit operations Mattias Rönnblom
2024-09-20 10:47                             ` [PATCH v12 5/7] eal: add atomic " Mattias Rönnblom
2024-09-20 10:47                             ` [PATCH v12 6/7] eal: add unit tests for atomic bit access functions Mattias Rönnblom
2024-10-10 10:45                               ` David Marchand
2024-10-10 11:55                                 ` Mattias Rönnblom
2024-10-10 12:14                                   ` David Marchand
2024-10-10 12:35                                     ` Mattias Rönnblom
2024-10-10 13:07                                       ` Thomas Monjalon
2024-10-11  8:35                                   ` David Marchand
2024-10-11 15:06                                 ` Morten Brørup
2024-10-11 15:11                                   ` David Marchand
2024-10-11 15:15                                     ` Morten Brørup
2024-10-11 15:18                                       ` David Marchand
2024-09-20 10:47                             ` [PATCH v12 7/7] eal: extend bitops to handle volatile pointers Mattias Rönnblom
2024-10-09 20:18                             ` [PATCH v12 0/7] Improve EAL bit operations API David Marchand
2024-09-20  6:24                         ` [PATCH v11 2/7] dpdk: use C linkage only where appropriate Mattias Rönnblom
2024-09-20  6:24                         ` [PATCH v11 3/7] eal: extend bit manipulation functionality Mattias Rönnblom
2024-09-20  6:24                         ` [PATCH v11 4/7] eal: add unit tests for bit operations Mattias Rönnblom
2024-09-20  6:24                         ` [PATCH v11 5/7] eal: add atomic " Mattias Rönnblom
2024-09-20  6:24                         ` [PATCH v11 6/7] eal: add unit tests for atomic bit access functions Mattias Rönnblom
2024-09-20  6:24                         ` [PATCH v11 7/7] eal: extend bitops to handle volatile pointers Mattias Rönnblom
2024-09-19 19:31                     ` [PATCH v10 2/7] dpdk: use C linkage only where appropriate Mattias Rönnblom
2024-09-19 19:31                     ` [PATCH v10 3/7] eal: extend bit manipulation functionality Mattias Rönnblom
2024-09-19 19:31                     ` [PATCH v10 4/7] eal: add unit tests for bit operations Mattias Rönnblom
2024-09-19 19:31                     ` [PATCH v10 5/7] eal: add atomic " Mattias Rönnblom
2024-09-19 19:31                     ` [PATCH v10 6/7] eal: add unit tests for atomic bit access functions Mattias Rönnblom
2024-09-19 19:31                     ` [PATCH v10 7/7] eal: extend bitops to handle volatile pointers Mattias Rönnblom
2024-09-18  9:04                 ` [PATCH v9 2/6] eal: extend bit manipulation functionality Mattias Rönnblom
2024-09-18  9:04                 ` [PATCH v9 3/6] eal: add unit tests for bit operations Mattias Rönnblom
2024-09-18  9:04                 ` [PATCH v9 4/6] eal: add atomic " Mattias Rönnblom
2024-09-18  9:04                 ` [PATCH v9 5/6] eal: add unit tests for atomic bit access functions Mattias Rönnblom
2024-09-18  9:04                 ` [PATCH v9 6/6] eal: extend bitops to handle volatile pointers Mattias Rönnblom
2024-09-17 10:48             ` [PATCH v8 2/6] eal: extend bit manipulation functionality Mattias Rönnblom
2024-09-17 10:48             ` [PATCH v8 3/6] eal: add unit tests for bit operations Mattias Rönnblom
2024-09-17 10:48             ` [PATCH v8 4/6] eal: add atomic " Mattias Rönnblom
2024-09-17 10:48             ` [PATCH v8 5/6] eal: add unit tests for atomic bit access functions Mattias Rönnblom
2024-09-17 10:48             ` [PATCH v8 6/6] eal: extend bitops to handle volatile pointers Mattias Rönnblom
2024-09-17  9:36         ` [PATCH v7 2/6] eal: extend bit manipulation functionality Mattias Rönnblom
2024-09-17  9:36         ` [PATCH v7 3/6] eal: add unit tests for bit operations Mattias Rönnblom
2024-09-17  9:36         ` [PATCH v7 4/6] eal: add atomic " Mattias Rönnblom
2024-09-17  9:36         ` [PATCH v7 5/6] eal: add unit tests for atomic bit access functions Mattias Rönnblom
2024-09-17  9:36         ` [PATCH v7 6/6] eal: extend bitops to handle volatile pointers Mattias Rönnblom
2024-10-10  8:30       ` [PATCH v2 0/4] Add bitset type David Marchand
2024-10-10  8:30         ` [PATCH v2 1/4] eal: add " David Marchand
2024-10-11  9:35           ` Mattias Rönnblom
2024-10-16 11:30           ` David Marchand
2024-10-16 13:37             ` Mattias Rönnblom
2024-10-10  8:30         ` [PATCH v2 2/4] bitset: add atomic functions David Marchand
2024-10-10  8:30         ` [PATCH v2 3/4] service: use multi-word bitset to represent service flags David Marchand
2024-10-10  8:30         ` [PATCH v2 4/4] event/dsw: add support for larger port count David Marchand
2024-10-14 15:08         ` [PATCH v2 0/4] Add bitset type David Marchand

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.