| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <26f4867c.3d5b.192671de81c.Coremail.xavier_qy@163.com>
Date: Mon, 7 Oct 2024 21:14:26 +0800 (CST)
From: Xavier <xavier_qy@....com>
To: "Kuan-Wei Chiu" <visitorckw@...il.com>
Cc: longman@...hat.com, lizefan.x@...edance.com, tj@...nel.org,
hannes@...xchg.org, mkoutny@...e.com, akpm@...ux-foundation.org,
jserv@...s.ncku.edu.tw, linux-kernel@...r.kernel.org,
cgroups@...r.kernel.org
Subject: Re:[PATCH 3/5] lib: Add KUnit tests for Union-Find implementation
At 2024-10-06 05:49:36, "Kuan-Wei Chiu" <visitorckw@...il.com> 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@...il.com>
>---
>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@...sung.com>
>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@...il.com>");
>+MODULE_DESCRIPTION("Union-find KUnit test suite");
>+MODULE_LICENSE("GPL");
>--
>2.34.1
Powered by blists - more mailing lists