Re:[PATCH 3/5] lib: Add KUnit tests for Union-Find implementation

[Xavier]

At 2024-10-06 05:49:36, "Kuan-Wei Chiu" <visitorckw@xxxxxxxxx> wrote:
>Introduce a KUnit test suite for the Union-Find data structure. The
>tests verify the functionality and correctness of the union and find
>operations, including edge cases such as handling duplicate unions.
>The addition of KUnit tests enhances the robustness of the Union-Find
>implementation by ensuring its correctness under various scenarios.
>
>Signed-off-by: Kuan-Wei Chiu <visitorckw@xxxxxxxxx>
>---
>Regarding the changes to the MAINTAINERS file, I'm also happy to help
>maintain/review patches related to union find. If I am qualified
>enough, may I send another patch to add myself later? :)

Of course, if you are interested.

>
> MAINTAINERS            |  1 +
> lib/Kconfig.debug      | 12 +++++++
> lib/Makefile           |  1 +
> lib/union_find_kunit.c | 74 ++++++++++++++++++++++++++++++++++++++++++
> 4 files changed, 88 insertions(+)
> create mode 100644 lib/union_find_kunit.c
>
>diff --git a/MAINTAINERS b/MAINTAINERS
>index 5153c995d429..3b10ac1cdf63 100644
>--- a/MAINTAINERS
>+++ b/MAINTAINERS
>@@ -23799,6 +23799,7 @@ F:	Documentation/core-api/union_find.rst
> F:	Documentation/translations/zh_CN/core-api/union_find.rst
> F:	include/linux/union_find.h
> F:	lib/union_find.c
>+F:	lib/union_find_kunit.c
> 
> UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER
> R:	Alim Akhtar <alim.akhtar@xxxxxxxxxxx>
>diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
>index 7315f643817a..376c86d34253 100644
>--- a/lib/Kconfig.debug
>+++ b/lib/Kconfig.debug
>@@ -2841,6 +2841,18 @@ config SIPHASH_KUNIT_TEST
> 	  This is intended to help people writing architecture-specific
> 	  optimized versions.  If unsure, say N.
> 
>+config UNION_FIND_KUNIT_TEST
>+	tristate "KUnit Test for Union find"
>+	depends on KUNIT
>+	default KUNIT_ALL_TESTS
>+	help
>+	  This option enables the KUnit tests for the Union-Find data structure.
>+	  These tests verify the functionality and correctness of the Union-Find
>+	  implementation, including union and find operations, as well as
>+	  edge cases such as handling of duplicate unions.
>+
>+	  If unsure, say N
>+
> config USERCOPY_KUNIT_TEST
> 	tristate "KUnit Test for user/kernel boundary protections"
> 	depends on KUNIT
>diff --git a/lib/Makefile b/lib/Makefile
>index 773adf88af41..03da92faf9b8 100644
>--- a/lib/Makefile
>+++ b/lib/Makefile
>@@ -388,6 +388,7 @@ CFLAGS_fortify_kunit.o += $(call cc-disable-warning, stringop-truncation)
> CFLAGS_fortify_kunit.o += $(DISABLE_STRUCTLEAK_PLUGIN)
> obj-$(CONFIG_FORTIFY_KUNIT_TEST) += fortify_kunit.o
> obj-$(CONFIG_SIPHASH_KUNIT_TEST) += siphash_kunit.o
>+obj-$(CONFIG_UNION_FIND_KUNIT_TEST) += union_find_kunit.o
> obj-$(CONFIG_USERCOPY_KUNIT_TEST) += usercopy_kunit.o
> 
> obj-$(CONFIG_GENERIC_LIB_DEVMEM_IS_ALLOWED) += devmem_is_allowed.o
>diff --git a/lib/union_find_kunit.c b/lib/union_find_kunit.c
>new file mode 100644
>index 000000000000..9bdf9e0e455e
>--- /dev/null
>+++ b/lib/union_find_kunit.c
>@@ -0,0 +1,74 @@
>+// SPDX-License-Identifier: GPL-2.0-only
>+
>+#include <kunit/test.h>
>+#include <linux/module.h>
>+#include <linux/union_find.h>
>+
>+static void test_union_and_find(struct kunit *test)
>+{
>+	struct uf_node node1, node2, node3;
>+	struct uf_node *root1, *root2, *root3;
>+	bool merged;
>+
>+	/* Initialize the nodes */
>+	uf_node_init(&node1);
>+	uf_node_init(&node2);
>+	uf_node_init(&node3);
>+
>+	/* Check the initial parent and rank */
>+	KUNIT_ASSERT_PTR_EQ(test, uf_find(&node1), &node1);
>+	KUNIT_ASSERT_PTR_EQ(test, uf_find(&node2), &node2);
>+	KUNIT_ASSERT_PTR_EQ(test, uf_find(&node3), &node3);
>+	KUNIT_ASSERT_EQ(test, node1.rank, 0);
>+	KUNIT_ASSERT_EQ(test, node2.rank, 0);
>+	KUNIT_ASSERT_EQ(test, node3.rank, 0);
>+
>+	/* Union node1 and node2 */
>+	merged = uf_union(&node1, &node2);
>+	KUNIT_ASSERT_TRUE(test, merged);
>+
>+	/* Assert that one of the nodes is now the parent of the other */
>+	root1 = uf_find(&node1);
>+	root2 = uf_find(&node2);
>+	KUNIT_ASSERT_PTR_EQ(test, root1, root2);
>+
>+	/* Check rank after the first union */
>+	if (root1 == &node1) {
>+		KUNIT_ASSERT_EQ(test, node1.rank, 1);
>+		KUNIT_ASSERT_EQ(test, node2.rank, 0);
>+	} else {
>+		KUNIT_ASSERT_EQ(test, node1.rank, 0);
>+		KUNIT_ASSERT_EQ(test, node2.rank, 1);
>+	}
>+
>+	/* Attempt to union node1 and node2 again and check for false return */
>+	merged = uf_union(&node1, &node2);
>+	KUNIT_ASSERT_FALSE(test, merged);
>+
>+	/* Union node3 with the result of the previous union (node1 and node2) */
>+	uf_union(&node1, &node3);
>+
>+	/* Assert that all nodes have the same root */
>+	root3 = uf_find(&node3);
>+	KUNIT_ASSERT_PTR_EQ(test, root1, root3);
>+
>+	/* Check rank after the second union */
>+	KUNIT_ASSERT_EQ(test, root1->rank, 1);
>+	KUNIT_ASSERT_EQ(test, node3.rank, 0);
>+}
>+
>+static struct kunit_case union_find_test_cases[] = {
>+	KUNIT_CASE(test_union_and_find),
>+	{}
>+};
>+
>+static struct kunit_suite union_find_test_suite = {
>+	.name = "union_find_test_suite",
>+	.test_cases = union_find_test_cases,
>+};
>+
>+kunit_test_suites(&union_find_test_suite);
>+
>+MODULE_AUTHOR("Kuan-Wei Chiu <visitorckw@xxxxxxxxx>");
>+MODULE_DESCRIPTION("Union-find KUnit test suite");
>+MODULE_LICENSE("GPL");
>-- 
>2.34.1