[RFC v3] eal: add bitset type

[RFC v3] eal: add bitset type

[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

Re: [RFC v3] eal: add bitset type

[Stephen Hemminger]

On Wed, 31 Jan 2024 14:13:01 +0100
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:

> Introduce a set of functions and macros that operate on sets of bits,
> kept in arrays of 64-bit elements.
> 
> RTE bitset is designed for bitsets which are larger than what fits in
> a single machine word (i.e., 64 bits). For very large bitsets, the
> <rte_bitmap.h> API may be a more appropriate choice.
> 
> 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();
Cast to char unneeded, and you don't want signed character here.
Use uint8_t

Re: [RFC v3] eal: add bitset type

[Stephen Hemminger]

On Wed, 31 Jan 2024 14:13:01 +0100
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:

> +/**
> + * @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.
> + *
> + */

FYI - the linux kernel has a similar but more complete set of operations.
It might be more efficient to use unsigned long rather than requiring
the elements to be uint64_t. Thinking of the few 32 bit platforms.

Also, what if any thread safety guarantees? or atomic.

From kernel bitmap.h

/**
 * DOC: bitmap overview
 *
 * The available bitmap operations and their rough meaning in the
 * case that the bitmap is a single unsigned long are thus:
 *
 * The generated code is more efficient when nbits is known at
 * compile-time and at most BITS_PER_LONG.
 *
 * ::
 *
 *  bitmap_zero(dst, nbits)                     *dst = 0UL
 *  bitmap_fill(dst, nbits)                     *dst = ~0UL
 *  bitmap_copy(dst, src, nbits)                *dst = *src
 *  bitmap_and(dst, src1, src2, nbits)          *dst = *src1 & *src2
 *  bitmap_or(dst, src1, src2, nbits)           *dst = *src1 | *src2
 *  bitmap_xor(dst, src1, src2, nbits)          *dst = *src1 ^ *src2
 *  bitmap_andnot(dst, src1, src2, nbits)       *dst = *src1 & ~(*src2)
 *  bitmap_complement(dst, src, nbits)          *dst = ~(*src)
 *  bitmap_equal(src1, src2, nbits)             Are *src1 and *src2 equal?
 *  bitmap_intersects(src1, src2, nbits)        Do *src1 and *src2 overlap?
 *  bitmap_subset(src1, src2, nbits)            Is *src1 a subset of *src2?
 *  bitmap_empty(src, nbits)                    Are all bits zero in *src?
 *  bitmap_full(src, nbits)                     Are all bits set in *src?
 *  bitmap_weight(src, nbits)                   Hamming Weight: number set bits
 *  bitmap_weight_and(src1, src2, nbits)        Hamming Weight of and'ed bitmap
 *  bitmap_set(dst, pos, nbits)                 Set specified bit area
 *  bitmap_clear(dst, pos, nbits)               Clear specified bit area
 *  bitmap_find_next_zero_area(buf, len, pos, n, mask)  Find bit free area
 *  bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off)  as above
 *  bitmap_shift_right(dst, src, n, nbits)      *dst = *src >> n
 *  bitmap_shift_left(dst, src, n, nbits)       *dst = *src << n
 *  bitmap_cut(dst, src, first, n, nbits)       Cut n bits from first, copy rest
 *  bitmap_replace(dst, old, new, mask, nbits)  *dst = (*old & ~(*mask)) | (*new & *mask)
 *  bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)
 *  bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)
 *  bitmap_onto(dst, orig, relmap, nbits)       *dst = orig relative to relmap
 *  bitmap_fold(dst, orig, sz, nbits)           dst bits = orig bits mod sz
 *  bitmap_parse(buf, buflen, dst, nbits)       Parse bitmap dst from kernel buf
 *  bitmap_parse_user(ubuf, ulen, dst, nbits)   Parse bitmap dst from user buf
 *  bitmap_parselist(buf, dst, nbits)           Parse bitmap dst from kernel buf
 *  bitmap_parselist_user(buf, dst, nbits)      Parse bitmap dst from user buf
 *  bitmap_find_free_region(bitmap, bits, order)  Find and allocate bit region
 *  bitmap_release_region(bitmap, pos, order)   Free specified bit region
 *  bitmap_allocate_region(bitmap, pos, order)  Allocate specified bit region
 *  bitmap_from_arr32(dst, buf, nbits)          Copy nbits from u32[] buf to dst
 *  bitmap_from_arr64(dst, buf, nbits)          Copy nbits from u64[] buf to dst
 *  bitmap_to_arr32(buf, src, nbits)            Copy nbits from buf to u32[] dst
 *  bitmap_to_arr64(buf, src, nbits)            Copy nbits from buf to u64[] dst
 *  bitmap_get_value8(map, start)               Get 8bit value from map at start
 *  bitmap_set_value8(map, value, start)        Set 8bit value to map at start
 *
 * Note, bitmap_zero() and bitmap_fill() operate over the region of
 * unsigned longs, that is, bits behind bitmap till the unsigned long
 * boundary will be zeroed or filled as well. Consider to use
 * bitmap_clear() or bitmap_set() to make explicit zeroing or filling
 * respectively.
 */

Re: [RFC v3] eal: add bitset type

[Mattias Rönnblom]

On 2024-01-31 17:02, Stephen Hemminger wrote:
> On Wed, 31 Jan 2024 14:13:01 +0100
> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> 
>> Introduce a set of functions and macros that operate on sets of bits,
>> kept in arrays of 64-bit elements.
>>
>> RTE bitset is designed for bitsets which are larger than what fits in
>> a single machine word (i.e., 64 bits). For very large bitsets, the
>> <rte_bitmap.h> API may be a more appropriate choice.
>>
>> 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();
> Cast to char unneeded, and you don't want signed character here.
> Use uint8_t

Going through a char pointer is useful in that it never aliases some 
other type. I'll change it to unsigned char.

Thanks.

Re: [RFC v3] eal: add bitset type

[Mattias Rönnblom]

On 2024-01-31 17:06, Stephen Hemminger wrote:
> On Wed, 31 Jan 2024 14:13:01 +0100
> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> 
>> +/**
>> + * @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.
>> + *
>> + */
> 
> FYI - the linux kernel has a similar but more complete set of operations.
> It might be more efficient to use unsigned long rather than requiring
> the elements to be uint64_t. Thinking of the few 32 bit platforms.
> 

Keeping it 64-bit avoids a popcount-related #ifdef. DPDK doesn't have an 
equivalent to __builtin_popcountl().

How much do we need to care about 32-bit ISA performance?

I'll go through the below API and some other APIs to see if there's 
something obvious missing.

When I originally wrote this code there were a few potential features 
where I wasn't sure to what extent they were useful. One example was the 
shift operation. Any input is appreciated.

> Also, what if any thread safety guarantees? or atomic.
> 

Currently, it's all MT unsafe.

An atomic set and get/test would make sense, and maybe other operations 
would as well.

Bringing in atomicity into the design makes it much less obvious:

Would the atomic operations imply some memory ordering, or be "relaxed". 
I would lean toward relaxed, but then shouldn't bit-level atomics be 
consistent with the core DPDK atomics API? With that in mind, memory 
ordering should be user-configurable.

If the code needs to be pure C11 atomics-wise, the words that makes up 
the bitset must be _Atomic uint64_t. Then you need to be careful or end 
up with "lock"-prefixed instructions if you manipulate the bitset words. 
Just a pure words[N] = 0; gives you a mov+mfence on x86, for example, 
plus all the fun memory_order_seq_cst in terms of preventing 
compiler-level optimizations. So you definitely can't have the bitset 
always using _Atomic uint64_t, since would risk non-shared use cases. 
You could have a variant I guess. Just duplicate the whole thing, or 
something with macros.

With GCC C11 builtins, you can both have the atomic cake and eat it, in 
that you both access the data non-atomically/normally, and in an atomic 
manner.

>  From kernel bitmap.h
> 
> /**
>   * DOC: bitmap overview
>   *
>   * The available bitmap operations and their rough meaning in the
>   * case that the bitmap is a single unsigned long are thus:
>   *
>   * The generated code is more efficient when nbits is known at
>   * compile-time and at most BITS_PER_LONG.
>   *
>   * ::
>   *
>   *  bitmap_zero(dst, nbits)                     *dst = 0UL
>   *  bitmap_fill(dst, nbits)                     *dst = ~0UL
>   *  bitmap_copy(dst, src, nbits)                *dst = *src
>   *  bitmap_and(dst, src1, src2, nbits)          *dst = *src1 & *src2
>   *  bitmap_or(dst, src1, src2, nbits)           *dst = *src1 | *src2
>   *  bitmap_xor(dst, src1, src2, nbits)          *dst = *src1 ^ *src2
>   *  bitmap_andnot(dst, src1, src2, nbits)       *dst = *src1 & ~(*src2)
>   *  bitmap_complement(dst, src, nbits)          *dst = ~(*src)
>   *  bitmap_equal(src1, src2, nbits)             Are *src1 and *src2 equal?
>   *  bitmap_intersects(src1, src2, nbits)        Do *src1 and *src2 overlap?
>   *  bitmap_subset(src1, src2, nbits)            Is *src1 a subset of *src2?
>   *  bitmap_empty(src, nbits)                    Are all bits zero in *src?
>   *  bitmap_full(src, nbits)                     Are all bits set in *src?
>   *  bitmap_weight(src, nbits)                   Hamming Weight: number set bits
>   *  bitmap_weight_and(src1, src2, nbits)        Hamming Weight of and'ed bitmap
>   *  bitmap_set(dst, pos, nbits)                 Set specified bit area
>   *  bitmap_clear(dst, pos, nbits)               Clear specified bit area
>   *  bitmap_find_next_zero_area(buf, len, pos, n, mask)  Find bit free area
>   *  bitmap_find_next_zero_area_off(buf, len, pos, n, mask, mask_off)  as above
>   *  bitmap_shift_right(dst, src, n, nbits)      *dst = *src >> n
>   *  bitmap_shift_left(dst, src, n, nbits)       *dst = *src << n
>   *  bitmap_cut(dst, src, first, n, nbits)       Cut n bits from first, copy rest
>   *  bitmap_replace(dst, old, new, mask, nbits)  *dst = (*old & ~(*mask)) | (*new & *mask)
>   *  bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)
>   *  bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)
>   *  bitmap_onto(dst, orig, relmap, nbits)       *dst = orig relative to relmap
>   *  bitmap_fold(dst, orig, sz, nbits)           dst bits = orig bits mod sz
>   *  bitmap_parse(buf, buflen, dst, nbits)       Parse bitmap dst from kernel buf
>   *  bitmap_parse_user(ubuf, ulen, dst, nbits)   Parse bitmap dst from user buf
>   *  bitmap_parselist(buf, dst, nbits)           Parse bitmap dst from kernel buf
>   *  bitmap_parselist_user(buf, dst, nbits)      Parse bitmap dst from user buf
>   *  bitmap_find_free_region(bitmap, bits, order)  Find and allocate bit region
>   *  bitmap_release_region(bitmap, pos, order)   Free specified bit region
>   *  bitmap_allocate_region(bitmap, pos, order)  Allocate specified bit region
>   *  bitmap_from_arr32(dst, buf, nbits)          Copy nbits from u32[] buf to dst
>   *  bitmap_from_arr64(dst, buf, nbits)          Copy nbits from u64[] buf to dst
>   *  bitmap_to_arr32(buf, src, nbits)            Copy nbits from buf to u32[] dst
>   *  bitmap_to_arr64(buf, src, nbits)            Copy nbits from buf to u64[] dst
>   *  bitmap_get_value8(map, start)               Get 8bit value from map at start
>   *  bitmap_set_value8(map, value, start)        Set 8bit value to map at start
>   *
>   * Note, bitmap_zero() and bitmap_fill() operate over the region of
>   * unsigned longs, that is, bits behind bitmap till the unsigned long
>   * boundary will be zeroed or filled as well. Consider to use
>   * bitmap_clear() or bitmap_set() to make explicit zeroing or filling
>   * respectively.
>   */
> 

RE: [RFC v3] eal: add bitset type

[Morten Brørup]

> From: Mattias Rönnblom [mailto:hofors@lysator.liu.se]
> Sent: Wednesday, 31 January 2024 19.46
> 
> On 2024-01-31 17:06, Stephen Hemminger wrote:
> > On Wed, 31 Jan 2024 14:13:01 +0100
> > Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:

[...]

> > FYI - the linux kernel has a similar but more complete set of
> operations.
> > It might be more efficient to use unsigned long rather than requiring
> > the elements to be uint64_t. Thinking of the few 32 bit platforms.
> >
> 
> Keeping it 64-bit avoids a popcount-related #ifdef. DPDK doesn't have
> an
> equivalent to __builtin_popcountl().
> 
> How much do we need to care about 32-bit ISA performance?

At the 2023 DPDK Summit I talked to someone at a very well known network equipment vendor using 32 bit CPUs in some of their products; some sort of CPE, IIRC. 32 bit CPUs are still out there, and 32-bit CPU support has not been deprecated in DPDK.

For the bitset parameter to functions, you could either use "unsigned long*" (as suggested by Stephen), or "void*" (followed by type casting inside the functions).

If only using this library for the command line argument parser and similar, performance is irrelevant. If we foresee using it in the fast path, e.g. with the htimer library, we shouldn't tie its API tightly to 64 bit.

> 
> I'll go through the below API and some other APIs to see if there's
> something obvious missing.
> 
> When I originally wrote this code there were a few potential features
> where I wasn't sure to what extent they were useful. One example was
> the
> shift operation. Any input is appreciated.

Start off with what you already have. If we need more operations, they can always be added later.

> 
> > Also, what if any thread safety guarantees? or atomic.
> >
> 
> Currently, it's all MT unsafe.
> 
> An atomic set and get/test would make sense, and maybe other operations
> would as well.
> 
> Bringing in atomicity into the design makes it much less obvious:
> 
> Would the atomic operations imply some memory ordering, or be
> "relaxed".
> I would lean toward relaxed, but then shouldn't bit-level atomics be
> consistent with the core DPDK atomics API? With that in mind, memory
> ordering should be user-configurable.
> 
> If the code needs to be pure C11 atomics-wise, the words that makes up
> the bitset must be _Atomic uint64_t. Then you need to be careful or end
> up with "lock"-prefixed instructions if you manipulate the bitset
> words.
> Just a pure words[N] = 0; gives you a mov+mfence on x86, for example,
> plus all the fun memory_order_seq_cst in terms of preventing
> compiler-level optimizations. So you definitely can't have the bitset
> always using _Atomic uint64_t, since would risk non-shared use cases.
> You could have a variant I guess. Just duplicate the whole thing, or
> something with macros.

It seems like MT unsafe suffices for the near term use cases.

We can add an atomic variant of the library later, if the need should arise.

> 
> With GCC C11 builtins, you can both have the atomic cake and eat it, in
> that you both access the data non-atomically/normally, and in an atomic
> manner.

Yep. And we care quite a lot about performance, so we are likely to keep using those until the compilers offer similar performance for C11 standard atomics.

Re: [RFC v3] eal: add bitset type

[Mattias Rönnblom]

On 2024-02-01 09:04, Morten Brørup wrote:
>> From: Mattias Rönnblom [mailto:hofors@lysator.liu.se]
>> Sent: Wednesday, 31 January 2024 19.46
>>
>> On 2024-01-31 17:06, Stephen Hemminger wrote:
>>> On Wed, 31 Jan 2024 14:13:01 +0100
>>> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> 
> [...]
> 
>>> FYI - the linux kernel has a similar but more complete set of
>> operations.
>>> It might be more efficient to use unsigned long rather than requiring
>>> the elements to be uint64_t. Thinking of the few 32 bit platforms.
>>>
>>
>> Keeping it 64-bit avoids a popcount-related #ifdef. DPDK doesn't have
>> an
>> equivalent to __builtin_popcountl().
>>
>> How much do we need to care about 32-bit ISA performance?
> 
> At the 2023 DPDK Summit I talked to someone at a very well known network equipment vendor using 32 bit CPUs in some of their products; some sort of CPE, IIRC. 32 bit CPUs are still out there, and 32-bit CPU support has not been deprecated in DPDK.
> 
> For the bitset parameter to functions, you could either use "unsigned long*" (as suggested by Stephen), or "void*" (followed by type casting inside the functions).
> 
> If only using this library for the command line argument parser and similar, performance is irrelevant. If we foresee using it in the fast path, e.g. with the htimer library, we shouldn't tie its API tightly to 64 bit.
> 

I'm not even sure performance will be that much worse. Sure, two 
popcount instead of one. What is probably worse is older ISAs (32- or 
64-bit, e.g. original x64_64) that lack machine instructions for 
counting set bits of *any* word size.

That said, the only real concern I have about going "unsigned long" -> 
"uint64_t" is that I might feel I need to go fix <rte_bitops.h> first.

>>
>> I'll go through the below API and some other APIs to see if there's
>> something obvious missing.
>>
>> When I originally wrote this code there were a few potential features
>> where I wasn't sure to what extent they were useful. One example was
>> the
>> shift operation. Any input is appreciated.
> 
> Start off with what you already have. If we need more operations, they can always be added later.
> 
>>
>>> Also, what if any thread safety guarantees? or atomic.
>>>
>>
>> Currently, it's all MT unsafe.
>>
>> An atomic set and get/test would make sense, and maybe other operations
>> would as well.
>>
>> Bringing in atomicity into the design makes it much less obvious:
>>
>> Would the atomic operations imply some memory ordering, or be
>> "relaxed".
>> I would lean toward relaxed, but then shouldn't bit-level atomics be
>> consistent with the core DPDK atomics API? With that in mind, memory
>> ordering should be user-configurable.
>>
>> If the code needs to be pure C11 atomics-wise, the words that makes up
>> the bitset must be _Atomic uint64_t. Then you need to be careful or end
>> up with "lock"-prefixed instructions if you manipulate the bitset
>> words.
>> Just a pure words[N] = 0; gives you a mov+mfence on x86, for example,
>> plus all the fun memory_order_seq_cst in terms of preventing
>> compiler-level optimizations. So you definitely can't have the bitset
>> always using _Atomic uint64_t, since would risk non-shared use cases.
>> You could have a variant I guess. Just duplicate the whole thing, or
>> something with macros.
> 
> It seems like MT unsafe suffices for the near term use cases.
> 
> We can add an atomic variant of the library later, if the need should arise.
> 

Agreed. The only concern I have here is that you end up wanting to 
change the original design, to better be able to fit atomic bit operations.

>>
>> With GCC C11 builtins, you can both have the atomic cake and eat it, in
>> that you both access the data non-atomically/normally, and in an atomic
>> manner.
> 
> Yep. And we care quite a lot about performance, so we are likely to keep using those until the compilers offer similar performance for C11 standard atomics.
> 

RE: [RFC v3] eal: add bitset type

[Morten Brørup]

> From: Mattias Rönnblom [mailto:hofors@lysator.liu.se]
> Sent: Friday, 2 February 2024 11.19
> 
> On 2024-02-01 09:04, Morten Brørup wrote:
> >> From: Mattias Rönnblom [mailto:hofors@lysator.liu.se]
> >> Sent: Wednesday, 31 January 2024 19.46
> >>
> >> On 2024-01-31 17:06, Stephen Hemminger wrote:
> >>> On Wed, 31 Jan 2024 14:13:01 +0100
> >>> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> >
> > [...]
> >
> >>> FYI - the linux kernel has a similar but more complete set of
> >> operations.
> >>> It might be more efficient to use unsigned long rather than
> requiring
> >>> the elements to be uint64_t. Thinking of the few 32 bit platforms.
> >>>
> >>
> >> Keeping it 64-bit avoids a popcount-related #ifdef. DPDK doesn't
> have
> >> an
> >> equivalent to __builtin_popcountl().
> >>
> >> How much do we need to care about 32-bit ISA performance?
> >
> > At the 2023 DPDK Summit I talked to someone at a very well known
> network equipment vendor using 32 bit CPUs in some of their products;
> some sort of CPE, IIRC. 32 bit CPUs are still out there, and 32-bit CPU
> support has not been deprecated in DPDK.
> >
> > For the bitset parameter to functions, you could either use "unsigned
> long*" (as suggested by Stephen), or "void*" (followed by type casting
> inside the functions).
> >
> > If only using this library for the command line argument parser and
> similar, performance is irrelevant. If we foresee using it in the fast
> path, e.g. with the htimer library, we shouldn't tie its API tightly to
> 64 bit.
> >
> 
> I'm not even sure performance will be that much worse. Sure, two
> popcount instead of one. What is probably worse is older ISAs (32- or
> 64-bit, e.g. original x64_64) that lack machine instructions for
> counting set bits of *any* word size.

I'm sorry about being unclear. I didn't mean to suggest supporting *any* word size; I was thinking about one word size, either 32 or 64 bit, automatically selected at build time depending on CPU architecture.

> 
> That said, the only real concern I have about going "unsigned long" ->
> "uint64_t" is that I might feel I need to go fix <rte_bitops.h> first.

I see.
Otherwise you'll end up with a bunch of #if RTE_ARCH_32 rte_bit_<op>32() #else rte_bit_<op>64() #endif in the implementation.
Perhaps a string concatenation macro could replace that with something like rte_bit_<op>##RTE_ARCH_BITS(), or RTE_POSTFIX_ARCH_BITS(rte_bit_<op>, (params)). Just thinking out aloud.

> 
> >>
> >> I'll go through the below API and some other APIs to see if there's
> >> something obvious missing.
> >>
> >> When I originally wrote this code there were a few potential
> features
> >> where I wasn't sure to what extent they were useful. One example was
> >> the
> >> shift operation. Any input is appreciated.
> >
> > Start off with what you already have. If we need more operations,
> they can always be added later.
> >
> >>
> >>> Also, what if any thread safety guarantees? or atomic.
> >>>
> >>
> >> Currently, it's all MT unsafe.
> >>
> >> An atomic set and get/test would make sense, and maybe other
> operations
> >> would as well.
> >>
> >> Bringing in atomicity into the design makes it much less obvious:
> >>
> >> Would the atomic operations imply some memory ordering, or be
> >> "relaxed".
> >> I would lean toward relaxed, but then shouldn't bit-level atomics be
> >> consistent with the core DPDK atomics API? With that in mind, memory
> >> ordering should be user-configurable.
> >>
> >> If the code needs to be pure C11 atomics-wise, the words that makes
> up
> >> the bitset must be _Atomic uint64_t. Then you need to be careful or
> end
> >> up with "lock"-prefixed instructions if you manipulate the bitset
> >> words.
> >> Just a pure words[N] = 0; gives you a mov+mfence on x86, for
> example,
> >> plus all the fun memory_order_seq_cst in terms of preventing
> >> compiler-level optimizations. So you definitely can't have the
> bitset
> >> always using _Atomic uint64_t, since would risk non-shared use
> cases.
> >> You could have a variant I guess. Just duplicate the whole thing, or
> >> something with macros.
> >
> > It seems like MT unsafe suffices for the near term use cases.
> >
> > We can add an atomic variant of the library later, if the need should
> arise.
> >
> 
> Agreed. The only concern I have here is that you end up wanting to
> change the original design, to better be able to fit atomic bit
> operations.

In a perfect world, the design should have a roadmap leading towards atomic bit operations.
In a fast moving world, we could mark the lib experimental (and mean it!) - it is still an improvement over copy-pasting something similar all over the code.

If a potential roadmap towards atomic operations is not obvious after thinking a few moments about it, we have a clear conscience to simply deem the library unsafe for multithreading and proceed with it "as is".

[RFC v4 1/4] eal: add bitset type

[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). For very large bitsets, the
<rte_bitmap.h> API may be a more appropriate choice.

RFC v4:
 * Add function rte_bitset_flip() to change the value of a bit.
 * Add function rte_bitset_complement(), flipping the value of all bits.
 * Add function rte_bitset_assign(), setting the value of a bit based
   on a 'bool' parameter.
 * Add functions to perform logical shift the bitset left or right.
 * Add explicit destination bitset to logic operation type functions
   (e.g., rte_bitset_and()), to increase flexibility.
 * Split implementation and test suite into distinct commits.

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>
---
 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 | 1080 ++++++++++++++++++++++++++++++++++
 lib/eal/version.map          |    3 +
 5 files changed, 1114 insertions(+)
 create mode 100644 lib/eal/common/rte_bitset.c
 create mode 100644 lib/eal/include/rte_bitset.h

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..35631a2a12
--- /dev/null
+++ b/lib/eal/include/rte_bitset.h
@@ -0,0 +1,1080 @@
+/* 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))
+#define __RTE_BITSET_USED_MASK(size)			\
+	(UINT64_MAX >> __RTE_BITSET_UNUSED(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 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)
+{
+	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 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)
+{
+	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 or clear a bit in the bitset.
+ *
+ * Bits are numbered 0 to (size - 1) (inclusive).
+ *
+ * @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)
+{
+	if (bit_value)
+		rte_bitset_set(bitset, bit_num);
+	else
+		rte_bitset_clear(bitset, bit_num);
+}
+
+/**
+ * @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).
+ *
+ * @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)
+{
+	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 (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);
+}
+
+/**
+ * @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 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 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

[RFC v4 2/4] eal: add bitset test suite

[Mattias Rönnblom]

Add test suite to exercise <rte_bitset.h>.

RFC v4:
 * Fix signed char issue in test cases. (Stephen Hemminger)
 * Add test cases for logic operations.
 * Use the unit test suite runner helper.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 app/test/meson.build   |   1 +
 app/test/test_bitset.c | 870 +++++++++++++++++++++++++++++++++++++++++
 2 files changed, 871 insertions(+)
 create mode 100644 app/test/test_bitset.c

diff --git a/app/test/meson.build b/app/test/meson.build
index b4382cf4ad..d5a7f771ae 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..84c8a117ee
--- /dev/null
+++ b/app/test/test_bitset.c
@@ -0,0 +1,870 @@
+/* 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++)
+		((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);
+}
+
+static int
+test_set_clear_size(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])
+			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;
+
+	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(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_set_clear_size(size) != TEST_SUCCESS)
+			return TEST_FAILED;
+	}
+
+	return TEST_SUCCESS;
+}
+
+static int
+test_flip_size(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 = rte_bitset_test(bitset, i);
+
+		rte_bitset_flip(bitset, i);
+
+		TEST_ASSERT(rte_bitset_test(bitset, i) != value,
+			    "Bit %zd was not flipped", i);
+
+		rte_bitset_assign(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(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_flip_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);
+
+	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;						\
+									\
+		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_logic_op(void (*bitset_op)(uint64_t *, const uint64_t *,
+					   const uint64_t *, size_t),
+			 bool (*bool_op)(bool, bool))
+{
+	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);
-- 
2.34.1

[RFC v4 3/4] service: use multi-word bitset to represent service flags

[Mattias Rönnblom]

Use a multi-word bitset to track which services are mapped to which
lcores, allowing the RTE_SERVICE_NUM_MAX compile-time constant to be >
64.

Replace array-of-bytes service-currently-active flags with a more
compact multi-word bitset-based representation, reducing memory
footprint somewhat.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/eal/common/rte_service.c | 70 ++++++++++++++----------------------
 1 file changed, 27 insertions(+), 43 deletions(-)

diff --git a/lib/eal/common/rte_service.c b/lib/eal/common/rte_service.c
index d959c91459..ac96ecaca8 100644
--- a/lib/eal/common/rte_service.c
+++ b/lib/eal/common/rte_service.c
@@ -11,6 +11,7 @@
 
 #include <eal_trace_internal.h>
 #include <rte_lcore.h>
+#include <rte_bitset.h>
 #include <rte_branch_prediction.h>
 #include <rte_common.h>
 #include <rte_cycles.h>
@@ -63,11 +64,11 @@ struct service_stats {
 /* the internal values of a service core */
 struct core_state {
 	/* map of services IDs are run on this core */
-	uint64_t service_mask;
+	RTE_BITSET_DECLARE(mapped_services, RTE_SERVICE_NUM_MAX);
 	RTE_ATOMIC(uint8_t) runstate; /* running or stopped */
 	RTE_ATOMIC(uint8_t) thread_active; /* indicates when thread is in service_run() */
 	uint8_t is_service_core; /* set if core is currently a service core */
-	uint8_t service_active_on_lcore[RTE_SERVICE_NUM_MAX];
+	RTE_BITSET_DECLARE(service_active_on_lcore, RTE_SERVICE_NUM_MAX);
 	RTE_ATOMIC(uint64_t) loops;
 	RTE_ATOMIC(uint64_t) cycles;
 	struct service_stats service_stats[RTE_SERVICE_NUM_MAX];
@@ -81,11 +82,6 @@ static uint32_t rte_service_library_initialized;
 int32_t
 rte_service_init(void)
 {
-	/* Hard limit due to the use of an uint64_t-based bitmask (and the
-	 * clzl intrinsic).
-	 */
-	RTE_BUILD_BUG_ON(RTE_SERVICE_NUM_MAX > 64);
-
 	if (rte_service_library_initialized) {
 		EAL_LOG(NOTICE,
 			"service library init() called, init flag %d",
@@ -296,7 +292,7 @@ rte_service_component_unregister(uint32_t id)
 
 	/* clear the run-bit in all cores */
 	for (i = 0; i < RTE_MAX_LCORE; i++)
-		lcore_states[i].service_mask &= ~(UINT64_C(1) << id);
+		rte_bitset_clear(lcore_states[i].mapped_services, id);
 
 	memset(&rte_services[id], 0, sizeof(struct rte_service_spec_impl));
 
@@ -410,7 +406,7 @@ service_runner_do_callback(struct rte_service_spec_impl *s,
 
 /* Expects the service 's' is valid. */
 static int32_t
-service_run(uint32_t i, struct core_state *cs, uint64_t service_mask,
+service_run(uint32_t i, struct core_state *cs, const uint64_t *mapped_services,
 	    struct rte_service_spec_impl *s, uint32_t serialize_mt_unsafe)
 {
 	if (!s)
@@ -424,12 +420,12 @@ service_run(uint32_t i, struct core_state *cs, uint64_t service_mask,
 			RUNSTATE_RUNNING ||
 	    rte_atomic_load_explicit(&s->app_runstate, rte_memory_order_acquire) !=
 			RUNSTATE_RUNNING ||
-	    !(service_mask & (UINT64_C(1) << i))) {
-		cs->service_active_on_lcore[i] = 0;
+	    !rte_bitset_test(mapped_services, i)) {
+		rte_bitset_clear(cs->service_active_on_lcore, i);
 		return -ENOEXEC;
 	}
 
-	cs->service_active_on_lcore[i] = 1;
+	rte_bitset_set(cs->service_active_on_lcore, i);
 
 	if ((service_mt_safe(s) == 0) && (serialize_mt_unsafe == 1)) {
 		if (!rte_spinlock_trylock(&s->execute_lock))
@@ -454,7 +450,7 @@ rte_service_may_be_active(uint32_t id)
 		return -EINVAL;
 
 	for (i = 0; i < lcore_count; i++) {
-		if (lcore_states[ids[i]].service_active_on_lcore[id])
+		if (rte_bitset_test(lcore_states[ids[i]].service_active_on_lcore, id))
 			return 1;
 	}
 
@@ -474,7 +470,9 @@ rte_service_run_iter_on_app_lcore(uint32_t id, uint32_t serialize_mt_unsafe)
 	 */
 	rte_atomic_fetch_add_explicit(&s->num_mapped_cores, 1, rte_memory_order_relaxed);
 
-	int ret = service_run(id, cs, UINT64_MAX, s, serialize_mt_unsafe);
+	RTE_BITSET_DECLARE(all_services, RTE_SERVICE_NUM_MAX);
+	rte_bitset_set_all(all_services, RTE_SERVICE_NUM_MAX);
+	int ret = service_run(id, cs, all_services, s, serialize_mt_unsafe);
 
 	rte_atomic_fetch_sub_explicit(&s->num_mapped_cores, 1, rte_memory_order_relaxed);
 
@@ -485,7 +483,6 @@ static int32_t
 service_runner_func(void *arg)
 {
 	RTE_SET_USED(arg);
-	uint8_t i;
 	const int lcore = rte_lcore_id();
 	struct core_state *cs = &lcore_states[lcore];
 
@@ -497,20 +494,11 @@ service_runner_func(void *arg)
 	 */
 	while (rte_atomic_load_explicit(&cs->runstate, rte_memory_order_acquire) ==
 			RUNSTATE_RUNNING) {
+		ssize_t id;
 
-		const uint64_t service_mask = cs->service_mask;
-		uint8_t start_id;
-		uint8_t end_id;
-
-		if (service_mask == 0)
-			continue;
-
-		start_id = rte_ctz64(service_mask);
-		end_id = 64 - rte_clz64(service_mask);
-
-		for (i = start_id; i < end_id; i++) {
+		RTE_BITSET_FOREACH_SET(id, cs->mapped_services, RTE_SERVICE_NUM_MAX) {
 			/* return value ignored as no change to code flow */
-			service_run(i, cs, service_mask, service_get(i), 1);
+			service_run(id, cs, cs->mapped_services, service_get(id), 1);
 		}
 
 		rte_atomic_store_explicit(&cs->loops, cs->loops + 1, rte_memory_order_relaxed);
@@ -519,8 +507,7 @@ service_runner_func(void *arg)
 	/* Switch off this core for all services, to ensure that future
 	 * calls to may_be_active() know this core is switched off.
 	 */
-	for (i = 0; i < RTE_SERVICE_NUM_MAX; i++)
-		cs->service_active_on_lcore[i] = 0;
+	rte_bitset_clear_all(cs->service_active_on_lcore, RTE_SERVICE_NUM_MAX);
 
 	/* Use SEQ CST memory ordering to avoid any re-ordering around
 	 * this store, ensuring that once this store is visible, the service
@@ -586,7 +573,7 @@ rte_service_lcore_count_services(uint32_t lcore)
 	if (!cs->is_service_core)
 		return -ENOTSUP;
 
-	return rte_popcount64(cs->service_mask);
+	return rte_bitset_count_set(cs->mapped_services, RTE_SERVICE_NUM_MAX);
 }
 
 int32_t
@@ -639,25 +626,23 @@ service_update(uint32_t sid, uint32_t lcore, uint32_t *set, uint32_t *enabled)
 			!lcore_states[lcore].is_service_core)
 		return -EINVAL;
 
-	uint64_t sid_mask = UINT64_C(1) << sid;
 	if (set) {
-		uint64_t lcore_mapped = lcore_states[lcore].service_mask &
-			sid_mask;
+		uint64_t lcore_mapped = rte_bitset_test(lcore_states[lcore].mapped_services, sid);
 
 		if (*set && !lcore_mapped) {
-			lcore_states[lcore].service_mask |= sid_mask;
+			rte_bitset_set(lcore_states[lcore].mapped_services, sid);
 			rte_atomic_fetch_add_explicit(&rte_services[sid].num_mapped_cores,
 				1, rte_memory_order_relaxed);
 		}
 		if (!*set && lcore_mapped) {
-			lcore_states[lcore].service_mask &= ~(sid_mask);
+			rte_bitset_clear(lcore_states[lcore].mapped_services, sid);
 			rte_atomic_fetch_sub_explicit(&rte_services[sid].num_mapped_cores,
 				1, rte_memory_order_relaxed);
 		}
 	}
 
 	if (enabled)
-		*enabled = !!(lcore_states[lcore].service_mask & (sid_mask));
+		*enabled = rte_bitset_test(lcore_states[lcore].mapped_services, sid);
 
 	return 0;
 }
@@ -699,11 +684,11 @@ set_lcore_state(uint32_t lcore, int32_t state)
 int32_t
 rte_service_lcore_reset_all(void)
 {
-	/* loop over cores, reset all to mask 0 */
+	/* loop over cores, reset all mapped services */
 	uint32_t i;
 	for (i = 0; i < RTE_MAX_LCORE; i++) {
 		if (lcore_states[i].is_service_core) {
-			lcore_states[i].service_mask = 0;
+			rte_bitset_clear_all(lcore_states[i].mapped_services, RTE_SERVICE_NUM_MAX);
 			set_lcore_state(i, ROLE_RTE);
 			/* runstate act as guard variable Use
 			 * store-release memory order here to synchronize
@@ -731,7 +716,7 @@ rte_service_lcore_add(uint32_t lcore)
 	set_lcore_state(lcore, ROLE_SERVICE);
 
 	/* ensure that after adding a core the mask and state are defaults */
-	lcore_states[lcore].service_mask = 0;
+	rte_bitset_clear_all(lcore_states[lcore].mapped_services, RTE_SERVICE_NUM_MAX);
 	/* Use store-release memory order here to synchronize with
 	 * load-acquire in runstate read functions.
 	 */
@@ -814,12 +799,11 @@ rte_service_lcore_stop(uint32_t lcore)
 
 	uint32_t i;
 	struct core_state *cs = &lcore_states[lcore];
-	uint64_t service_mask = cs->service_mask;
 
 	for (i = 0; i < RTE_SERVICE_NUM_MAX; i++) {
-		int32_t enabled = service_mask & (UINT64_C(1) << i);
-		int32_t service_running = rte_service_runstate_get(i);
-		int32_t only_core = (1 ==
+		bool enabled = rte_bitset_test(cs->mapped_services, i);
+		bool service_running = rte_service_runstate_get(i);
+		bool only_core = (1 ==
 			rte_atomic_load_explicit(&rte_services[i].num_mapped_cores,
 				rte_memory_order_relaxed));
 
-- 
2.34.1

[RFC v4 4/4] event/dsw: optimize serving port logic

[Mattias Rönnblom]

To reduce flow migration overhead, replace the array-based
representation of which set of ports are bound to a particular queue
by a multi-word bitset.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 drivers/event/dsw/dsw_evdev.c | 34 +++++++++++++++++++---------------
 drivers/event/dsw/dsw_evdev.h |  3 ++-
 drivers/event/dsw/dsw_event.c | 11 ++++-------
 3 files changed, 25 insertions(+), 23 deletions(-)

diff --git a/drivers/event/dsw/dsw_evdev.c b/drivers/event/dsw/dsw_evdev.c
index 1209e73a9d..a0781e4141 100644
--- a/drivers/event/dsw/dsw_evdev.c
+++ b/drivers/event/dsw/dsw_evdev.c
@@ -118,6 +118,7 @@ dsw_queue_setup(struct rte_eventdev *dev, uint8_t queue_id,
 		queue->schedule_type = conf->schedule_type;
 	}
 
+	rte_bitset_init(queue->serving_ports, DSW_MAX_PORTS);
 	queue->num_serving_ports = 0;
 
 	return 0;
@@ -144,24 +145,19 @@ dsw_queue_release(struct rte_eventdev *dev __rte_unused,
 static void
 queue_add_port(struct dsw_queue *queue, uint16_t port_id)
 {
-	queue->serving_ports[queue->num_serving_ports] = port_id;
+	rte_bitset_set(queue->serving_ports, port_id);
 	queue->num_serving_ports++;
 }
 
 static bool
 queue_remove_port(struct dsw_queue *queue, uint16_t port_id)
 {
-	uint16_t i;
+	if (rte_bitset_test(queue->serving_ports, port_id)) {
+		queue->num_serving_ports--;
+		rte_bitset_clear(queue->serving_ports, port_id);
+		return true;
+	}
 
-	for (i = 0; i < queue->num_serving_ports; i++)
-		if (queue->serving_ports[i] == port_id) {
-			uint16_t last_idx = queue->num_serving_ports - 1;
-			if (i != last_idx)
-				queue->serving_ports[i] =
-					queue->serving_ports[last_idx];
-			queue->num_serving_ports--;
-			return true;
-		}
 	return false;
 }
 
@@ -256,10 +252,18 @@ initial_flow_to_port_assignment(struct dsw_evdev *dsw)
 		struct dsw_queue *queue = &dsw->queues[queue_id];
 		uint16_t flow_hash;
 		for (flow_hash = 0; flow_hash < DSW_MAX_FLOWS; flow_hash++) {
-			uint8_t port_idx =
-				rte_rand() % queue->num_serving_ports;
-			uint8_t port_id =
-				queue->serving_ports[port_idx];
+			uint8_t skip = rte_rand_max(queue->num_serving_ports);
+			uint8_t port_id;
+
+			for (port_id = 0;; port_id++) {
+				if (rte_bitset_test(queue->serving_ports,
+						    port_id)) {
+					if (skip == 0)
+						break;
+					skip--;
+				}
+			}
+
 			dsw->queues[queue_id].flow_to_port_map[flow_hash] =
 				port_id;
 		}
diff --git a/drivers/event/dsw/dsw_evdev.h b/drivers/event/dsw/dsw_evdev.h
index 6416a8a898..503a63cbb2 100644
--- a/drivers/event/dsw/dsw_evdev.h
+++ b/drivers/event/dsw/dsw_evdev.h
@@ -7,6 +7,7 @@
 
 #include <eventdev_pmd.h>
 
+#include <rte_bitset.h>
 #include <rte_event_ring.h>
 #include <rte_eventdev.h>
 
@@ -234,7 +235,7 @@ struct dsw_port {
 
 struct dsw_queue {
 	uint8_t schedule_type;
-	uint8_t serving_ports[DSW_MAX_PORTS];
+	RTE_BITSET_DECLARE(serving_ports, DSW_MAX_PORTS);
 	uint16_t num_serving_ports;
 
 	uint8_t flow_to_port_map[DSW_MAX_FLOWS] __rte_cache_aligned;
diff --git a/drivers/event/dsw/dsw_event.c b/drivers/event/dsw/dsw_event.c
index 93bbeead2e..b855f9ecf1 100644
--- a/drivers/event/dsw/dsw_event.c
+++ b/drivers/event/dsw/dsw_event.c
@@ -447,13 +447,8 @@ static bool
 dsw_is_serving_port(struct dsw_evdev *dsw, uint8_t port_id, uint8_t queue_id)
 {
 	struct dsw_queue *queue = &dsw->queues[queue_id];
-	uint16_t i;
-
-	for (i = 0; i < queue->num_serving_ports; i++)
-		if (queue->serving_ports[i] == port_id)
-			return true;
 
-	return false;
+	return rte_bitset_test(queue->serving_ports, port_id);
 }
 
 static bool
@@ -575,7 +570,9 @@ dsw_schedule(struct dsw_evdev *dsw, uint8_t queue_id, uint16_t flow_hash)
 		/* A single-link queue, or atomic/ordered/parallel but
 		 * with just a single serving port.
 		 */
-		port_id = queue->serving_ports[0];
+		port_id = (uint8_t)rte_bitset_find_first_set(
+			queue->serving_ports, DSW_MAX_PORTS
+		);
 
 	DSW_LOG_DP(DEBUG, "Event with queue_id %d flow_hash %d is scheduled "
 		   "to port %d.\n", queue_id, flow_hash, port_id);
-- 
2.34.1

[RFC v5 1/6] eal: add bitset type

[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). For very large bitsets, the
<rte_bitmap.h> API may be a more appropriate choice.

Depends-on: series-31863 ("Improve EAL bit operations API")

RFC v5:
 * Delegate bit test/set/clear/assign/flip to RTE bitops.
 * Note in the documentation that set/clear/assign/flip are not
   atomic.

RFC v4:
 * Add function rte_bitset_flip() to change the value of a bit.
 * Add function rte_bitset_complement(), flipping the value of all bits.
 * Add function rte_bitset_assign(), setting the value of a bit based
   on a 'bool' parameter.
 * Add functions to perform logical shift the bitset left or right.
 * Add explicit destination bitset to logic operation type functions
   (e.g., rte_bitset_and()), to increase flexibility.
 * Split implementation and test suite into distinct commits.

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>
---
 doc/api/doxy-api-index.md    |    1 +
 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 | 1061 ++++++++++++++++++++++++++++++++++
 lib/eal/version.map          |    2 +
 6 files changed, 1095 insertions(+)
 create mode 100644 lib/eal/common/rte_bitset.c
 create mode 100644 lib/eal/include/rte_bitset.h

diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md
index 8c1eb8fafa..1ce04a8edf 100644
--- a/doc/api/doxy-api-index.md
+++ b/doc/api/doxy-api-index.md
@@ -173,6 +173,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/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..49a07c77b8
--- /dev/null
+++ b/lib/eal/include/rte_bitset.h
@@ -0,0 +1,1061 @@
+/* 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))
+#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 <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.
+ *
+ * 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 3df50c3fbb..254d3fd4b2 100644
--- a/lib/eal/version.map
+++ b/lib/eal/version.map
@@ -396,6 +396,8 @@ EXPERIMENTAL {
 
 	# added in 24.03
 	rte_vfio_get_device_info; # WINDOWS_NO_EXPORT
+
+	rte_bitset_to_str;
 };
 
 INTERNAL {
-- 
2.34.1

[RFC v5 2/6] eal: add bitset test suite

[Mattias Rönnblom]

Add test suite to exercise <rte_bitset.h>.

RFC v5:
 * Parameterize tests to allow reuse across both atomic and non-atomic
   functions.

RFC v4:
 * Fix signed char issue in test cases. (Stephen Hemminger)
 * Add test cases for logic operations.
 * Use the unit test suite runner helper.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 app/test/meson.build   |   1 +
 app/test/test_bitset.c | 894 +++++++++++++++++++++++++++++++++++++++++
 2 files changed, 895 insertions(+)
 create mode 100644 app/test/test_bitset.c

diff --git a/app/test/meson.build b/app/test/meson.build
index 7d909039ae..633af5ce05 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..b3496df1c0
--- /dev/null
+++ b/app/test/test_bitset.c
@@ -0,0 +1,894 @@
+/* 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++)
+		((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;						\
+									\
+		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_logic_op(void (*bitset_op)(uint64_t *, const uint64_t *,
+					   const uint64_t *, size_t),
+			 bool (*bool_op)(bool, bool))
+{
+	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);
-- 
2.34.1

[RFC v5 3/6] eal: add atomic bitset functions

[Mattias Rönnblom]

Extend the bitset API with atomic versions of the most basic bitset
operations.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/eal/include/rte_bitset.h | 155 +++++++++++++++++++++++++++++++++++
 1 file changed, 155 insertions(+)

diff --git a/lib/eal/include/rte_bitset.h b/lib/eal/include/rte_bitset.h
index 49a07c77b8..c0441b0e22 100644
--- a/lib/eal/include/rte_bitset.h
+++ b/lib/eal/include/rte_bitset.h
@@ -376,6 +376,161 @@ 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.
+ *
+ * Atomically test if a bit is set.
+ *
+ * Atomically test if a bit in a bitset is set with the specified
+ * memory ordering.
+ *
+ * @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.
+ * @param memory_order
+ *   The memory order to use.
+ * @return
+ *   Returns true if the bit is '1', and false if the bit is '0'.
+ */
+
+__rte_experimental
+static inline bool
+rte_bitset_atomic_test(const uint64_t *bitset, size_t bit_num,
+		       int memory_order)
+{
+	return __RTE_BITSET_DELEGATE_N(rte_bit_atomic_test, bitset, bit_num,
+				       memory_order);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Atomically set a bit in the bitset.
+ *
+ * Set a bit in a bitset as an atomic operation, with the specified
+ * memory ordering.
+ *
+ * rte_bitset_atomic_set() is multi-thread safe, provided all threads
+ * acting in parallel on the same bitset does so through
+ * @c rte_bitset_atomic_*() functions.
+ *
+ * Bits are numbered from 0 to (size - 1) (inclusive).
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param bit_num
+ *   The index of the bit to be set.
+ * @param memory_order
+ *   The memory order to use.
+ */
+
+__rte_experimental
+static inline void
+rte_bitset_atomic_set(uint64_t *bitset, size_t bit_num, int memory_order)
+{
+	__RTE_BITSET_DELEGATE_N(rte_bit_atomic_set, bitset, bit_num,
+				memory_order);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Atomically clear a bit in the bitset.
+ *
+ * Clear a bit in a bitset as an atomic operation, with the specified
+ * memory ordering.
+ *
+ * rte_bitset_atomic_clear() is multi-thread safe, provided all
+ * threads acting in parallel on the same bitset does so through @c
+ * rte_bitset_atomic_*() functions.
+ *
+ * Bits are numbered from 0 to (size - 1) (inclusive).
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param bit_num
+ *   The index of the bit to be cleared.
+ * @param memory_order
+ *   The memory order to use.
+ */
+
+__rte_experimental
+static inline void
+rte_bitset_atomic_clear(uint64_t *bitset, size_t bit_num, int memory_order)
+{
+	__RTE_BITSET_DELEGATE_N(rte_bit_atomic_clear, bitset, bit_num,
+				memory_order);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Atomically set or clear a bit in the bitset.
+ *
+ * Assign a value to a bit in a bitset as an atomic operation, with
+ * the specified memory ordering.
+ *
+ * rte_bitset_atomic_assign() is multi-thread safe, provided all
+ * threads acting in parallel on the same bitset does so through
+ * @c rte_bitset_atomic_*() functions.
+ *
+ * Bits are numbered from 0 to (size - 1) (inclusive).
+ *
+ * @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.
+ * @param memory_order
+ *   The memory order to use.
+ */
+
+__rte_experimental
+static inline void
+rte_bitset_atomic_assign(uint64_t *bitset, size_t bit_num, bool bit_value,
+			 int memory_order)
+{
+	__RTE_BITSET_DELEGATE_N(rte_bit_atomic_assign, bitset, bit_num,
+				bit_value, memory_order);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice.
+ *
+ * Atomically change the value of a bit in the bitset.
+ *
+ * Flip a bit in a bitset as an atomic operation, with the specified
+ * memory ordering.
+ *
+ * rte_bitset_atomic_flip() is multi-thread safe, provided all threads
+ * acting in parallel on the same bitset does so through
+ * @c rte_bitset_atomic_*() functions.
+ *
+ * Bits are numbered from 0 to (size - 1) (inclusive).
+ *
+ * @param bitset
+ *   A pointer to the array of words making up the bitset.
+ * @param bit_num
+ *   The index of the bit to be flipped.
+ * @param memory_order
+ *   The memory order to use.
+ */
+
+__rte_experimental
+static inline void
+rte_bitset_atomic_flip(uint64_t *bitset, size_t bit_num, int memory_order)
+{
+	__RTE_BITSET_DELEGATE_N(rte_bit_atomic_flip, bitset, bit_num,
+				memory_order);
+}
+
 /**
  * @warning
  * @b EXPERIMENTAL: this API may change without prior notice.
-- 
2.34.1

[RFC v5 4/6] eal: add unit tests for atomic bitset operations

[Mattias Rönnblom]

Extend bitset tests to cover the basic operation of the
rte_bitset_atomic_*() family of functions.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 app/test/test_bitset.c | 48 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)

diff --git a/app/test/test_bitset.c b/app/test/test_bitset.c
index b3496df1c0..32224a1eee 100644
--- a/app/test/test_bitset.c
+++ b/app/test/test_bitset.c
@@ -222,6 +222,52 @@ test_flip(void)
 			     rte_bitset_flip);
 }
 
+static bool
+bitset_atomic_test(const uint64_t *bitset, size_t bit_num)
+{
+	return rte_bitset_atomic_test(bitset, bit_num,
+				      rte_memory_order_relaxed);
+}
+
+static void
+bitset_atomic_set(uint64_t *bitset, size_t bit_num)
+{
+	rte_bitset_atomic_set(bitset, bit_num, rte_memory_order_relaxed);
+}
+
+static void
+bitset_atomic_clear(uint64_t *bitset, size_t bit_num)
+{
+	rte_bitset_atomic_clear(bitset, bit_num, rte_memory_order_relaxed);
+}
+
+static void
+bitset_atomic_flip(uint64_t *bitset, size_t bit_num)
+{
+	rte_bitset_atomic_flip(bitset, bit_num, rte_memory_order_relaxed);
+}
+
+static void
+bitset_atomic_assign(uint64_t *bitset, size_t bit_num, bool bit_value)
+{
+	rte_bitset_atomic_assign(bitset, bit_num, bit_value,
+				 rte_memory_order_relaxed);
+}
+
+static int
+test_atomic_set_clear(void)
+{
+	return test_set_clear_fun(bitset_atomic_test, bitset_atomic_set,
+				  bitset_atomic_clear);
+}
+
+static int
+test_atomic_flip(void)
+{
+	return test_flip_fun(bitset_atomic_test, bitset_atomic_assign,
+			     bitset_atomic_flip);
+}
+
 static ssize_t
 find(const bool *ary, size_t num_bools, size_t start, size_t len, bool set)
 {
@@ -868,6 +914,8 @@ static struct unit_test_suite bitset_tests  = {
 	.unit_test_cases = {
 		TEST_CASE_ST(NULL, NULL, test_set_clear),
 		TEST_CASE_ST(NULL, NULL, test_flip),
+		TEST_CASE_ST(NULL, NULL, test_atomic_set_clear),
+		TEST_CASE_ST(NULL, NULL, test_atomic_flip),
 		TEST_CASE_ST(NULL, NULL, test_find),
 		TEST_CASE_ST(NULL, NULL, test_foreach),
 		TEST_CASE_ST(NULL, NULL, test_count),
-- 
2.34.1

[RFC v5 5/6] service: use multi-word bitset to represent service flags

[Mattias Rönnblom]

Use a multi-word bitset to track which services are mapped to which
lcores, allowing the RTE_SERVICE_NUM_MAX compile-time constant to be >
64.

Replace array-of-bytes service-currently-active flags with a more
compact multi-word bitset-based representation, reducing memory
footprint somewhat.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/eal/common/rte_service.c | 70 ++++++++++++++----------------------
 1 file changed, 27 insertions(+), 43 deletions(-)

diff --git a/lib/eal/common/rte_service.c b/lib/eal/common/rte_service.c
index 56379930b6..ec0f47e141 100644
--- a/lib/eal/common/rte_service.c
+++ b/lib/eal/common/rte_service.c
@@ -11,6 +11,7 @@
 
 #include <eal_trace_internal.h>
 #include <rte_lcore.h>
+#include <rte_bitset.h>
 #include <rte_branch_prediction.h>
 #include <rte_common.h>
 #include <rte_cycles.h>
@@ -63,11 +64,11 @@ struct service_stats {
 /* the internal values of a service core */
 struct __rte_cache_aligned core_state {
 	/* map of services IDs are run on this core */
-	uint64_t service_mask;
+	RTE_BITSET_DECLARE(mapped_services, RTE_SERVICE_NUM_MAX);
 	RTE_ATOMIC(uint8_t) runstate; /* running or stopped */
 	RTE_ATOMIC(uint8_t) thread_active; /* indicates when thread is in service_run() */
 	uint8_t is_service_core; /* set if core is currently a service core */
-	uint8_t service_active_on_lcore[RTE_SERVICE_NUM_MAX];
+	RTE_BITSET_DECLARE(service_active_on_lcore, RTE_SERVICE_NUM_MAX);
 	RTE_ATOMIC(uint64_t) loops;
 	RTE_ATOMIC(uint64_t) cycles;
 	struct service_stats service_stats[RTE_SERVICE_NUM_MAX];
@@ -81,11 +82,6 @@ static uint32_t rte_service_library_initialized;
 int32_t
 rte_service_init(void)
 {
-	/* Hard limit due to the use of an uint64_t-based bitmask (and the
-	 * clzl intrinsic).
-	 */
-	RTE_BUILD_BUG_ON(RTE_SERVICE_NUM_MAX > 64);
-
 	if (rte_service_library_initialized) {
 		EAL_LOG(NOTICE,
 			"service library init() called, init flag %d",
@@ -296,7 +292,7 @@ rte_service_component_unregister(uint32_t id)
 
 	/* clear the run-bit in all cores */
 	for (i = 0; i < RTE_MAX_LCORE; i++)
-		lcore_states[i].service_mask &= ~(UINT64_C(1) << id);
+		rte_bitset_clear(lcore_states[i].mapped_services, id);
 
 	memset(&rte_services[id], 0, sizeof(struct rte_service_spec_impl));
 
@@ -410,7 +406,7 @@ service_runner_do_callback(struct rte_service_spec_impl *s,
 
 /* Expects the service 's' is valid. */
 static int32_t
-service_run(uint32_t i, struct core_state *cs, uint64_t service_mask,
+service_run(uint32_t i, struct core_state *cs, const uint64_t *mapped_services,
 	    struct rte_service_spec_impl *s, uint32_t serialize_mt_unsafe)
 {
 	if (!s)
@@ -424,12 +420,12 @@ service_run(uint32_t i, struct core_state *cs, uint64_t service_mask,
 			RUNSTATE_RUNNING ||
 	    rte_atomic_load_explicit(&s->app_runstate, rte_memory_order_acquire) !=
 			RUNSTATE_RUNNING ||
-	    !(service_mask & (UINT64_C(1) << i))) {
-		cs->service_active_on_lcore[i] = 0;
+	    !rte_bitset_test(mapped_services, i)) {
+		rte_bitset_clear(cs->service_active_on_lcore, i);
 		return -ENOEXEC;
 	}
 
-	cs->service_active_on_lcore[i] = 1;
+	rte_bitset_set(cs->service_active_on_lcore, i);
 
 	if ((service_mt_safe(s) == 0) && (serialize_mt_unsafe == 1)) {
 		if (!rte_spinlock_trylock(&s->execute_lock))
@@ -454,7 +450,7 @@ rte_service_may_be_active(uint32_t id)
 		return -EINVAL;
 
 	for (i = 0; i < lcore_count; i++) {
-		if (lcore_states[ids[i]].service_active_on_lcore[id])
+		if (rte_bitset_test(lcore_states[ids[i]].service_active_on_lcore, id))
 			return 1;
 	}
 
@@ -474,7 +470,9 @@ rte_service_run_iter_on_app_lcore(uint32_t id, uint32_t serialize_mt_unsafe)
 	 */
 	rte_atomic_fetch_add_explicit(&s->num_mapped_cores, 1, rte_memory_order_relaxed);
 
-	int ret = service_run(id, cs, UINT64_MAX, s, serialize_mt_unsafe);
+	RTE_BITSET_DECLARE(all_services, RTE_SERVICE_NUM_MAX);
+	rte_bitset_set_all(all_services, RTE_SERVICE_NUM_MAX);
+	int ret = service_run(id, cs, all_services, s, serialize_mt_unsafe);
 
 	rte_atomic_fetch_sub_explicit(&s->num_mapped_cores, 1, rte_memory_order_relaxed);
 
@@ -485,7 +483,6 @@ static int32_t
 service_runner_func(void *arg)
 {
 	RTE_SET_USED(arg);
-	uint8_t i;
 	const int lcore = rte_lcore_id();
 	struct core_state *cs = &lcore_states[lcore];
 
@@ -497,20 +494,11 @@ service_runner_func(void *arg)
 	 */
 	while (rte_atomic_load_explicit(&cs->runstate, rte_memory_order_acquire) ==
 			RUNSTATE_RUNNING) {
+		ssize_t id;
 
-		const uint64_t service_mask = cs->service_mask;
-		uint8_t start_id;
-		uint8_t end_id;
-
-		if (service_mask == 0)
-			continue;
-
-		start_id = rte_ctz64(service_mask);
-		end_id = 64 - rte_clz64(service_mask);
-
-		for (i = start_id; i < end_id; i++) {
+		RTE_BITSET_FOREACH_SET(id, cs->mapped_services, RTE_SERVICE_NUM_MAX) {
 			/* return value ignored as no change to code flow */
-			service_run(i, cs, service_mask, service_get(i), 1);
+			service_run(id, cs, cs->mapped_services, service_get(id), 1);
 		}
 
 		rte_atomic_store_explicit(&cs->loops, cs->loops + 1, rte_memory_order_relaxed);
@@ -519,8 +507,7 @@ service_runner_func(void *arg)
 	/* Switch off this core for all services, to ensure that future
 	 * calls to may_be_active() know this core is switched off.
 	 */
-	for (i = 0; i < RTE_SERVICE_NUM_MAX; i++)
-		cs->service_active_on_lcore[i] = 0;
+	rte_bitset_clear_all(cs->service_active_on_lcore, RTE_SERVICE_NUM_MAX);
 
 	/* Use SEQ CST memory ordering to avoid any re-ordering around
 	 * this store, ensuring that once this store is visible, the service
@@ -586,7 +573,7 @@ rte_service_lcore_count_services(uint32_t lcore)
 	if (!cs->is_service_core)
 		return -ENOTSUP;
 
-	return rte_popcount64(cs->service_mask);
+	return rte_bitset_count_set(cs->mapped_services, RTE_SERVICE_NUM_MAX);
 }
 
 int32_t
@@ -639,25 +626,23 @@ service_update(uint32_t sid, uint32_t lcore, uint32_t *set, uint32_t *enabled)
 			!lcore_states[lcore].is_service_core)
 		return -EINVAL;
 
-	uint64_t sid_mask = UINT64_C(1) << sid;
 	if (set) {
-		uint64_t lcore_mapped = lcore_states[lcore].service_mask &
-			sid_mask;
+		uint64_t lcore_mapped = rte_bitset_test(lcore_states[lcore].mapped_services, sid);
 
 		if (*set && !lcore_mapped) {
-			lcore_states[lcore].service_mask |= sid_mask;
+			rte_bitset_set(lcore_states[lcore].mapped_services, sid);
 			rte_atomic_fetch_add_explicit(&rte_services[sid].num_mapped_cores,
 				1, rte_memory_order_relaxed);
 		}
 		if (!*set && lcore_mapped) {
-			lcore_states[lcore].service_mask &= ~(sid_mask);
+			rte_bitset_clear(lcore_states[lcore].mapped_services, sid);
 			rte_atomic_fetch_sub_explicit(&rte_services[sid].num_mapped_cores,
 				1, rte_memory_order_relaxed);
 		}
 	}
 
 	if (enabled)
-		*enabled = !!(lcore_states[lcore].service_mask & (sid_mask));
+		*enabled = rte_bitset_test(lcore_states[lcore].mapped_services, sid);
 
 	return 0;
 }
@@ -699,11 +684,11 @@ set_lcore_state(uint32_t lcore, int32_t state)
 int32_t
 rte_service_lcore_reset_all(void)
 {
-	/* loop over cores, reset all to mask 0 */
+	/* loop over cores, reset all mapped services */
 	uint32_t i;
 	for (i = 0; i < RTE_MAX_LCORE; i++) {
 		if (lcore_states[i].is_service_core) {
-			lcore_states[i].service_mask = 0;
+			rte_bitset_clear_all(lcore_states[i].mapped_services, RTE_SERVICE_NUM_MAX);
 			set_lcore_state(i, ROLE_RTE);
 			/* runstate act as guard variable Use
 			 * store-release memory order here to synchronize
@@ -731,7 +716,7 @@ rte_service_lcore_add(uint32_t lcore)
 	set_lcore_state(lcore, ROLE_SERVICE);
 
 	/* ensure that after adding a core the mask and state are defaults */
-	lcore_states[lcore].service_mask = 0;
+	rte_bitset_clear_all(lcore_states[lcore].mapped_services, RTE_SERVICE_NUM_MAX);
 	/* Use store-release memory order here to synchronize with
 	 * load-acquire in runstate read functions.
 	 */
@@ -814,12 +799,11 @@ rte_service_lcore_stop(uint32_t lcore)
 
 	uint32_t i;
 	struct core_state *cs = &lcore_states[lcore];
-	uint64_t service_mask = cs->service_mask;
 
 	for (i = 0; i < RTE_SERVICE_NUM_MAX; i++) {
-		int32_t enabled = service_mask & (UINT64_C(1) << i);
-		int32_t service_running = rte_service_runstate_get(i);
-		int32_t only_core = (1 ==
+		bool enabled = rte_bitset_test(cs->mapped_services, i);
+		bool service_running = rte_service_runstate_get(i);
+		bool only_core = (1 ==
 			rte_atomic_load_explicit(&rte_services[i].num_mapped_cores,
 				rte_memory_order_relaxed));
 
-- 
2.34.1

[RFC v5 6/6] event/dsw: optimize serving port logic

[Mattias Rönnblom]

To reduce flow migration overhead, replace the array-based
representation of which set of ports are bound to a particular queue
by a multi-word bitset.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 drivers/event/dsw/dsw_evdev.c | 19 +++++++------------
 drivers/event/dsw/dsw_evdev.h |  3 ++-
 drivers/event/dsw/dsw_event.c |  7 ++++---
 3 files changed, 13 insertions(+), 16 deletions(-)

diff --git a/drivers/event/dsw/dsw_evdev.c b/drivers/event/dsw/dsw_evdev.c
index ab0420b549..f3ca99e935 100644
--- a/drivers/event/dsw/dsw_evdev.c
+++ b/drivers/event/dsw/dsw_evdev.c
@@ -118,6 +118,7 @@ dsw_queue_setup(struct rte_eventdev *dev, uint8_t queue_id,
 		queue->schedule_type = conf->schedule_type;
 	}
 
+	rte_bitset_init(queue->serving_ports, DSW_MAX_PORTS);
 	queue->num_serving_ports = 0;
 
 	return 0;
@@ -144,20 +145,16 @@ dsw_queue_release(struct rte_eventdev *dev __rte_unused,
 static void
 queue_add_port(struct dsw_queue *queue, uint16_t port_id)
 {
-	uint64_t port_mask = UINT64_C(1) << port_id;
-
-	queue->serving_ports |=	port_mask;
+	rte_bitset_set(queue->serving_ports, port_id);
 	queue->num_serving_ports++;
 }
 
 static bool
 queue_remove_port(struct dsw_queue *queue, uint16_t port_id)
 {
-	uint64_t port_mask = UINT64_C(1) << port_id;
-
-	if (queue->serving_ports & port_mask) {
+	if (rte_bitset_test(queue->serving_ports, port_id)) {
 		queue->num_serving_ports--;
-		queue->serving_ports ^= port_mask;
+		rte_bitset_clear(queue->serving_ports, port_id);
 		return true;
 	}
 
@@ -257,14 +254,12 @@ initial_flow_to_port_assignment(struct dsw_evdev *dsw)
 		struct dsw_queue *queue = &dsw->queues[queue_id];
 		uint16_t flow_hash;
 		for (flow_hash = 0; flow_hash < DSW_MAX_FLOWS; flow_hash++) {
-			uint8_t skip =
-				rte_rand_max(queue->num_serving_ports);
+			uint8_t skip = rte_rand_max(queue->num_serving_ports);
 			uint8_t port_id;
 
 			for (port_id = 0;; port_id++) {
-				uint64_t port_mask = UINT64_C(1) << port_id;
-
-				if (queue->serving_ports & port_mask) {
+				if (rte_bitset_test(queue->serving_ports,
+						    port_id)) {
 					if (skip == 0)
 						break;
 					skip--;
diff --git a/drivers/event/dsw/dsw_evdev.h b/drivers/event/dsw/dsw_evdev.h
index 3a5989f148..0c40c45e46 100644
--- a/drivers/event/dsw/dsw_evdev.h
+++ b/drivers/event/dsw/dsw_evdev.h
@@ -7,6 +7,7 @@
 
 #include <eventdev_pmd.h>
 
+#include <rte_bitset.h>
 #include <rte_event_ring.h>
 #include <rte_eventdev.h>
 
@@ -234,7 +235,7 @@ struct __rte_cache_aligned dsw_port {
 
 struct dsw_queue {
 	uint8_t schedule_type;
-	uint64_t serving_ports;
+	RTE_BITSET_DECLARE(serving_ports, DSW_MAX_PORTS);
 	uint16_t num_serving_ports;
 
 	alignas(RTE_CACHE_LINE_SIZE) uint8_t flow_to_port_map[DSW_MAX_FLOWS];
diff --git a/drivers/event/dsw/dsw_event.c b/drivers/event/dsw/dsw_event.c
index 23488d9030..b855f9ecf1 100644
--- a/drivers/event/dsw/dsw_event.c
+++ b/drivers/event/dsw/dsw_event.c
@@ -447,9 +447,8 @@ static bool
 dsw_is_serving_port(struct dsw_evdev *dsw, uint8_t port_id, uint8_t queue_id)
 {
 	struct dsw_queue *queue = &dsw->queues[queue_id];
-	uint64_t port_mask = UINT64_C(1) << port_id;
 
-	return queue->serving_ports & port_mask;
+	return rte_bitset_test(queue->serving_ports, port_id);
 }
 
 static bool
@@ -571,7 +570,9 @@ dsw_schedule(struct dsw_evdev *dsw, uint8_t queue_id, uint16_t flow_hash)
 		/* A single-link queue, or atomic/ordered/parallel but
 		 * with just a single serving port.
 		 */
-		port_id = rte_bsf64(queue->serving_ports);
+		port_id = (uint8_t)rte_bitset_find_first_set(
+			queue->serving_ports, DSW_MAX_PORTS
+		);
 
 	DSW_LOG_DP(DEBUG, "Event with queue_id %d flow_hash %d is scheduled "
 		   "to port %d.\n", queue_id, flow_hash, port_id);
-- 
2.34.1