MAINTAINERS | 1 +
lib/Kconfig.debug | 13 ++
lib/tests/Makefile | 1 +
lib/tests/sbitmap_kunit.c | 300 ++++++++++++++++++++++++++++++++++++++
4 files changed, 315 insertions(+)
create mode 100644 lib/tests/sbitmap_kunit.c
diff --git a/MAINTAINERS b/MAINTAINERS
index f53047aa8d3c..c8510e6f1817 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4726,6 +4726,7 @@ F: include/uapi/linux/blk*
F: include/uapi/linux/ioprio.h
F: kernel/trace/blktrace.c
F: lib/sbitmap.c
+F: lib/tests/sbitmap_kunit.c
BLOCK LAYER DEVICE DRIVER API [RUST]
M: Andreas Hindborg <[email protected]>
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 6b24a2c89b84..f5fe7f5a0a4d 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2456,6 +2456,19 @@ config PRINTF_KUNIT_TEST
If unsure, say N.
+config SBITMAP_KUNIT_TEST
+ tristate "KUnit test for sbitmap" if !KUNIT_ALL_TESTS
+ depends on KUNIT
+ depends on SBITMAP
+ default KUNIT_ALL_TESTS
+ help
+ Enable to turn on sbitmap tests, running at boot or module load time.
+
+ For more information on KUnit and unit tests in general, please refer
+ to the KUnit documentation in Documentation/dev-tools/kunit/.
+
+ If unsure, say N.
+
config SCANF_KUNIT_TEST
tristate "KUnit test scanf() family of functions at runtime" if
!KUNIT_ALL_TESTS
depends on KUNIT
diff --git a/lib/tests/Makefile b/lib/tests/Makefile
index 3cac3b63a752..1f49555f94c3 100644
--- a/lib/tests/Makefile
+++ b/lib/tests/Makefile
@@ -44,6 +44,7 @@ obj-$(CONFIG_OVERFLOW_KUNIT_TEST) += overflow_kunit.o
obj-$(CONFIG_PRANDOM_KUNIT_TEST) += random32_kunit.o
obj-$(CONFIG_PRINTF_KUNIT_TEST) += printf_kunit.o
obj-$(CONFIG_RANDSTRUCT_KUNIT_TEST) += randstruct_kunit.o
+obj-$(CONFIG_SBITMAP_KUNIT_TEST) += sbitmap_kunit.o
obj-$(CONFIG_SCANF_KUNIT_TEST) += scanf_kunit.o
obj-$(CONFIG_SEQ_BUF_KUNIT_TEST) += seq_buf_kunit.o
obj-$(CONFIG_SIPHASH_KUNIT_TEST) += siphash_kunit.o
diff --git a/lib/tests/sbitmap_kunit.c b/lib/tests/sbitmap_kunit.c
new file mode 100644
index 000000000000..4f3a588d15df
--- /dev/null
+++ b/lib/tests/sbitmap_kunit.c
@@ -0,0 +1,300 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * KUnit tests for the scalable bitmap (sbitmap) implementation.
+ *
+ * sbitmap is the tag allocator used by blk-mq and the I/O schedulers built on
+ * top of it, but it has no tests. These tests pin down the observable
+ * behaviour of the plain, synchronous parts of the API.
+ *
+ * Copyright (C) 2026 Wang Yibo <[email protected]>
+ */
+
+#include <linux/bitmap.h>
+#include <linux/gfp.h>
+#include <linux/sbitmap.h>
+
+#include <kunit/test.h>
+
+/*
+ * Big enough to span several words for any plausible BITS_PER_LONG, and not a
+ * power of two so that the last word is partially used.
+ */
+#define SBITMAP_TEST_DEPTH (3 * BITS_PER_LONG + 5)
+
+static void sbitmap_test_init(struct kunit *test)
+{
+ const unsigned int depth = 97;
+ struct sbitmap sb;
+ int ret;
+
+ ret = sbitmap_init_node(&sb, depth, -1, GFP_KERNEL, NUMA_NO_NODE,
+ false, true);
+ KUNIT_ASSERT_EQ(test, ret, 0);
+ KUNIT_EXPECT_EQ(test, sb.depth, depth);
+ KUNIT_EXPECT_EQ(test, sb.shift,
+ (unsigned int)sbitmap_calculate_shift(depth));
+ KUNIT_EXPECT_EQ(test, sb.map_nr, DIV_ROUND_UP(depth, 1U << sb.shift));
+ KUNIT_EXPECT_FALSE(test, sb.round_robin);
+ KUNIT_EXPECT_NOT_NULL(test, sb.alloc_hint);
+ KUNIT_EXPECT_FALSE(test, sbitmap_any_bit_set(&sb));
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb), 0U);
+ sbitmap_free(&sb);
+
+ /* An explicitly requested shift is honoured. */
+ ret = sbitmap_init_node(&sb, depth, 3, GFP_KERNEL, NUMA_NO_NODE,
+ false, true);
+ KUNIT_ASSERT_EQ(test, ret, 0);
+ KUNIT_EXPECT_EQ(test, sb.shift, 3U);
+ KUNIT_EXPECT_EQ(test, sb.map_nr, DIV_ROUND_UP(depth, 1U << 3));
+ sbitmap_free(&sb);
+
+ /* BITS_PER_LONG bits per word is the largest representable
granularity. */
+ ret = sbitmap_init_node(&sb, depth, ilog2(BITS_PER_LONG), GFP_KERNEL,
+ NUMA_NO_NODE, false, true);
+ KUNIT_ASSERT_EQ(test, ret, 0);
+ KUNIT_EXPECT_EQ(test, sb.shift, (unsigned int)ilog2(BITS_PER_LONG));
+ KUNIT_EXPECT_EQ(test, sb.map_nr, DIV_ROUND_UP(depth, BITS_PER_LONG));
+ sbitmap_free(&sb);
+
+ /* Anything above that cannot be represented and must be rejected. */
+ ret = sbitmap_init_node(&sb, depth, ilog2(BITS_PER_LONG) + 1,
+ GFP_KERNEL, NUMA_NO_NODE, false, true);
+ KUNIT_EXPECT_EQ(test, ret, -EINVAL);
+}
+
+static void sbitmap_test_calculate_shift(struct kunit *test)
+{
+ /* Maps too small to spread over several words keep the default. */
+ KUNIT_EXPECT_EQ(test, sbitmap_calculate_shift(0), ilog2(BITS_PER_LONG));
+ KUNIT_EXPECT_EQ(test, sbitmap_calculate_shift(1), ilog2(BITS_PER_LONG));
+ KUNIT_EXPECT_EQ(test, sbitmap_calculate_shift(3), ilog2(BITS_PER_LONG));
+
+ /* Four bits map to one bit per word. */
+ KUNIT_EXPECT_EQ(test, sbitmap_calculate_shift(4), 0);
+
+ /* The shift grows back as the depth increases. */
+ KUNIT_EXPECT_EQ(test, sbitmap_calculate_shift(4 * BITS_PER_LONG - 1),
+ ilog2(BITS_PER_LONG) - 1);
+ KUNIT_EXPECT_EQ(test, sbitmap_calculate_shift(4 * BITS_PER_LONG),
+ ilog2(BITS_PER_LONG));
+}
+
+static void sbitmap_test_get_exhaust(struct kunit *test)
+{
+ DECLARE_BITMAP(seen, SBITMAP_TEST_DEPTH) = { 0 };
+ struct sbitmap sb;
+ unsigned int i;
+ int bit;
+
+ KUNIT_ASSERT_EQ(test, sbitmap_init_node(&sb, SBITMAP_TEST_DEPTH, -1,
+ GFP_KERNEL, NUMA_NO_NODE,
+ false, true), 0);
+
+ /* Every bit is handed out exactly once, then the map is empty. */
+ for (i = 0; i < SBITMAP_TEST_DEPTH; i++) {
+ bit = sbitmap_get(&sb);
+ KUNIT_ASSERT_GE(test, bit, 0);
+ KUNIT_ASSERT_LT(test, bit, (int)SBITMAP_TEST_DEPTH);
+ KUNIT_ASSERT_FALSE(test, test_bit(bit, seen));
+ __set_bit(bit, seen);
+ }
+
+ KUNIT_EXPECT_TRUE(test, sbitmap_any_bit_set(&sb));
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb),
+ (unsigned int)SBITMAP_TEST_DEPTH);
+ KUNIT_EXPECT_EQ(test, sbitmap_get(&sb), -1);
+
+ sbitmap_free(&sb);
+}
+
+static void sbitmap_test_put_reuse(struct kunit *test)
+{
+ struct sbitmap sb;
+ unsigned int i;
+ int bit;
+
+ KUNIT_ASSERT_EQ(test, sbitmap_init_node(&sb, BITS_PER_LONG, -1,
+ GFP_KERNEL, NUMA_NO_NODE,
+ true, true), 0);
+
+ for (i = 0; i < BITS_PER_LONG; i++)
+ KUNIT_ASSERT_GE(test, sbitmap_get(&sb), 0);
+
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb), (unsigned int)BITS_PER_LONG);
+ KUNIT_EXPECT_EQ(test, sbitmap_get(&sb), -1);
+
+ /*
+ * Freeing a single bit must make exactly that bit available again, no
+ * matter which bit it was.
+ */
+ for (i = 0; i < BITS_PER_LONG; i++) {
+ sbitmap_put(&sb, i);
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb),
+ (unsigned int)BITS_PER_LONG - 1);
+ bit = sbitmap_get(&sb);
+ KUNIT_EXPECT_EQ(test, bit, (int)i);
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb),
+ (unsigned int)BITS_PER_LONG);
+ KUNIT_EXPECT_EQ(test, sbitmap_get(&sb), -1);
+ }
+
+ sbitmap_free(&sb);
+}
+
+static void sbitmap_test_round_robin(struct kunit *test)
+{
+ struct sbitmap sb;
+ unsigned int i;
+ int bit, prev = -1;
+
+ KUNIT_ASSERT_EQ(test, sbitmap_init_node(&sb, SBITMAP_TEST_DEPTH, -1,
+ GFP_KERNEL, NUMA_NO_NODE,
+ true, true), 0);
+
+ /*
+ * round_robin must hand out strictly increasing bit numbers while the
+ * map fills up from empty.
+ */
+ for (i = 0; i < SBITMAP_TEST_DEPTH; i++) {
+ bit = sbitmap_get(&sb);
+ KUNIT_ASSERT_GE(test, bit, 0);
+ KUNIT_ASSERT_LT(test, bit, (int)SBITMAP_TEST_DEPTH);
+ if (prev != -1)
+ KUNIT_ASSERT_GT(test, bit, prev);
+ prev = bit;
+ }
+
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb),
+ (unsigned int)SBITMAP_TEST_DEPTH);
+ KUNIT_EXPECT_EQ(test, sbitmap_get(&sb), -1);
+
+ sbitmap_free(&sb);
+}
+
+static void sbitmap_test_resize(struct kunit *test)
+{
+ const unsigned int depth = 4 * BITS_PER_LONG;
+ struct sbitmap sb;
+ unsigned int i;
+
+ KUNIT_ASSERT_EQ(test, sbitmap_init_node(&sb, depth, -1, GFP_KERNEL,
+ NUMA_NO_NODE, true, true), 0);
+
+ for (i = 0; i < depth; i++)
+ KUNIT_ASSERT_GE(test, sbitmap_get(&sb), 0);
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb), depth);
+
+ /* Shrinking hides the bits past the new depth. */
+ sbitmap_resize(&sb, depth / 2);
+ KUNIT_EXPECT_EQ(test, sb.depth, depth / 2);
+ KUNIT_EXPECT_EQ(test, sb.map_nr,
+ DIV_ROUND_UP(depth / 2, 1U << sb.shift));
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb), depth / 2);
+ KUNIT_EXPECT_EQ(test, sbitmap_get(&sb), -1);
+
+ /* Growing makes them visible again; they are still allocated. */
+ sbitmap_resize(&sb, depth);
+ KUNIT_EXPECT_EQ(test, sb.depth, depth);
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb), depth);
+ KUNIT_EXPECT_EQ(test, sbitmap_get(&sb), -1);
+
+ sbitmap_free(&sb);
+}
+
+static void sbitmap_test_set_clear_bit(struct kunit *test)
+{
+ static const unsigned int bits[] = {
+ 0, 1, BITS_PER_LONG - 1, BITS_PER_LONG,
+ 2 * BITS_PER_LONG + 3, SBITMAP_TEST_DEPTH - 1
+ };
+ struct sbitmap sb;
+ unsigned int i;
+
+ KUNIT_ASSERT_EQ(test, sbitmap_init_node(&sb, SBITMAP_TEST_DEPTH, -1,
+ GFP_KERNEL, NUMA_NO_NODE,
+ false, true), 0);
+
+ KUNIT_EXPECT_FALSE(test, sbitmap_any_bit_set(&sb));
+
+ for (i = 0; i < ARRAY_SIZE(bits); i++) {
+ sbitmap_set_bit(&sb, bits[i]);
+ KUNIT_EXPECT_TRUE(test, sbitmap_test_bit(&sb, bits[i]));
+ }
+ KUNIT_EXPECT_TRUE(test, sbitmap_any_bit_set(&sb));
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb), (unsigned
int)ARRAY_SIZE(bits));
+
+ for (i = 0; i < ARRAY_SIZE(bits); i++) {
+ sbitmap_clear_bit(&sb, bits[i]);
+ KUNIT_EXPECT_FALSE(test, sbitmap_test_bit(&sb, bits[i]));
+ }
+ KUNIT_EXPECT_FALSE(test, sbitmap_any_bit_set(&sb));
+ KUNIT_EXPECT_EQ(test, sbitmap_weight(&sb), 0U);
+
+ sbitmap_free(&sb);
+}
+
+struct sbitmap_iter_ctx {
+ struct kunit *test;
+ DECLARE_BITMAP(visited, SBITMAP_TEST_DEPTH);
+ unsigned int nr_visited;
+};
+
+static bool sbitmap_iter_collect(struct sbitmap *sb, unsigned int bitnr,
+ void *data)
+{
+ struct sbitmap_iter_ctx *ctx = data;
+
+ KUNIT_ASSERT_LT(ctx->test, bitnr, SBITMAP_TEST_DEPTH);
+ __set_bit(bitnr, ctx->visited);
+ ctx->nr_visited++;
+
+ return true;
+}
+
+static void sbitmap_test_iterate_set(struct kunit *test)
+{
+ static const unsigned int bits[] = {
+ 0, 5, BITS_PER_LONG - 1, BITS_PER_LONG, 130,
+ SBITMAP_TEST_DEPTH - 1
+ };
+ struct sbitmap_iter_ctx ctx = { .test = test };
+ struct sbitmap sb;
+ unsigned int i;
+
+ KUNIT_ASSERT_EQ(test, sbitmap_init_node(&sb, SBITMAP_TEST_DEPTH, -1,
+ GFP_KERNEL, NUMA_NO_NODE,
+ false, true), 0);
+
+ for (i = 0; i < ARRAY_SIZE(bits); i++)
+ sbitmap_set_bit(&sb, bits[i]);
+
+ sbitmap_for_each_set(&sb, sbitmap_iter_collect, &ctx);
+
+ KUNIT_EXPECT_EQ(test, ctx.nr_visited, (unsigned int)ARRAY_SIZE(bits));
