This is not a very sophisticated test suite yet, but it helped find
a few bugs and provides a framework for adding more tests as more
bugs are found.
Signed-off-by: Matthew Wilcox (Oracle) <willy@xxxxxxxxxxxxx>
---
lib/Kconfig.debug | 3 +
lib/Makefile | 1 +
lib/test_rosebush.c | 140 ++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 144 insertions(+)
create mode 100644 lib/test_rosebush.c
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 59b6765d86b8..f3cfd79d8dbd 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2447,6 +2447,9 @@ config TEST_RHASHTABLE
If unsure, say N.
+config TEST_ROSEBUSH
+ tristate "Test the Rosebush data structure"
+
config TEST_IDA
tristate "Perform selftest on IDA functions"
diff --git a/lib/Makefile b/lib/Makefile
index 723e6c90b58d..de4edefc2c11 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -76,6 +76,7 @@ obj-$(CONFIG_TEST_LIST_SORT) += test_list_sort.o
obj-$(CONFIG_TEST_MIN_HEAP) += test_min_heap.o
obj-$(CONFIG_TEST_LKM) += test_module.o
obj-$(CONFIG_TEST_VMALLOC) += test_vmalloc.o
+obj-$(CONFIG_TEST_ROSEBUSH) += test_rosebush.o
obj-$(CONFIG_TEST_RHASHTABLE) += test_rhashtable.o
obj-$(CONFIG_TEST_SORT) += test_sort.o
obj-$(CONFIG_TEST_USER_COPY) += test_user_copy.o
diff --git a/lib/test_rosebush.c b/lib/test_rosebush.c
new file mode 100644
index 000000000000..59c342e7a5b3
--- /dev/null
+++ b/lib/test_rosebush.c
@@ -0,0 +1,140 @@
+#include <linux/rosebush.h>
+#include <kunit/test.h>
+
+static void iter_rbh(struct kunit *test, struct rbh *rbh, u32 hash, void *p)
+{
+ RBH_ITER(iter, rbh, hash);
+ void *q;
+
+ rcu_read_lock();
+ q = rbh_next(&iter);
+ KUNIT_EXPECT_PTR_EQ_MSG(test, p, q,
+ "rbh_next hash:%u returned %px, expected %px", hash, q, p);
+ q = rbh_next(&iter);
+ KUNIT_EXPECT_PTR_EQ_MSG(test, NULL, q,
+ "rbh_next hash:%u returned %px, expected NULL", hash, q);
+ rcu_read_unlock();
+}
+
+static void check_empty_rbh(struct kunit *test, struct rbh *rbh)
+{
+ iter_rbh(test, rbh, 0, NULL);
+ iter_rbh(test, rbh, 1, NULL);
+ iter_rbh(test, rbh, 17, NULL);
+ iter_rbh(test, rbh, 42, NULL);
+}
+
+static void test_insert(struct kunit *test, struct rbh *rbh, u32 hash)
+{
+ void *p = (void *)((hash << 1) | 1UL);
+ int err;
+
+ err = rbh_insert(rbh, hash, p);
+ KUNIT_EXPECT_EQ(test, err, 0);
+
+ iter_rbh(test, rbh, hash, p);
+}
+
+static void test_reserve(struct kunit *test, struct rbh *rbh, u32 hash)
+{
+ int err;
+
+ err = rbh_reserve(rbh, hash);
+ KUNIT_EXPECT_EQ(test, err, 0);
+
+ iter_rbh(test, rbh, hash, NULL);
+}
+
+static void test_use(struct kunit *test, struct rbh *rbh, u32 hash)
+{
+ void *p = (void *)((hash << 1) | 1UL);
+ int err;
+
+ err = rbh_use(rbh, hash, p);
+ KUNIT_EXPECT_EQ(test, err, 0);
+
+ iter_rbh(test, rbh, hash, p);
+}
+
+static void test_remove(struct kunit *test, struct rbh *rbh, u32 hash)
+{
+ void *p = (void *)((hash << 1) | 1UL);
+ int err;
+
+ err = rbh_remove(rbh, hash, p);
+ KUNIT_EXPECT_EQ(test, err, 0);
+
+ iter_rbh(test, rbh, hash, NULL);
+}
+
+static DEFINE_ROSEBUSH(rosebush);
+
+/*
+ * Conduct a number of tests on a rosebush that has never been used.
+ * They should all return NULL or an errno. We're looking for crashes
+ * here.
+ */
+static void empty(struct kunit *test)
+{
+ int err;
+
+ check_empty_rbh(test, &rosebush);
+ err = rbh_remove(&rosebush, 0, test);
+ KUNIT_EXPECT_EQ(test, err, -ENOENT);
+ err = rbh_use(&rosebush, 0, test);
+ KUNIT_EXPECT_EQ(test, err, -ENOENT);
+ KUNIT_EXPECT_EQ(test, rosebush.rbh_table, 0);
+}
+
+static void first(struct kunit *test)
+{
+ int err;
+
+ test_insert(test, &rosebush, 5);
+ check_empty_rbh(test, &rosebush);
+ test_remove(test, &rosebush, 5);
+ check_empty_rbh(test, &rosebush);
+
+ err = rbh_remove(&rosebush, 5, NULL);
+ KUNIT_EXPECT_EQ(test, err, -ENOENT);
+ test_reserve(test, &rosebush, 5);
+ err = rbh_remove(&rosebush, 5, test);
+ KUNIT_EXPECT_EQ(test, err, -ENOENT);
+ err = rbh_remove(&rosebush, 5, NULL);
+ KUNIT_EXPECT_EQ(test, err, 0);
+ err = rbh_remove(&rosebush, 5, NULL);
+ KUNIT_EXPECT_EQ(test, err, -ENOENT);
+
+ test_reserve(test, &rosebush, 5);
+ test_use(test, &rosebush, 5);
+ err = rbh_remove(&rosebush, 5, NULL);
+ KUNIT_EXPECT_EQ(test, err, -ENOENT);
+ test_remove(test, &rosebush, 5);
+}
+
+static void grow(struct kunit *test)
+{
+ int i;
+
+ for (i = 3; i < 3333; i += 2)
+ test_insert(test, &rosebush, i);
+
+ rbh_destroy(&rosebush);
+}
+
+static struct kunit_case rosebush_cases[] __refdata = {
+ KUNIT_CASE(empty),
+ KUNIT_CASE(first),
+ KUNIT_CASE(grow),
+ {}
+};
+
+static struct kunit_suite rosebush_suite = {
+ .name = "rosebush",
+ .test_cases = rosebush_cases,
+};
+
+kunit_test_suite(rosebush_suite);
+
+MODULE_AUTHOR("Matthew Wilcox (Oracle) <willy@xxxxxxxxxxxxx>");
+MODULE_LICENSE("GPL");
--
2.43.0
