On Sat, 8 Feb 2025 at 06:33, Tamir Duberstein <tamird@xxxxxxxxx> wrote:
>
> Extract a private header and convert the prime_numbers self-test to a
> KUnit test. I considered parameterizing the test using
> `KUNIT_CASE_PARAM` but didn't see how it was possible since the test
> logic is entangled with the test parameter generation logic.
>
> Signed-off-by: Tamir Duberstein <tamird@xxxxxxxxx>
> ---
I'm not totally sold on moving everything into the
prime_numbers_private.h file, as we could end up with duplicate copies
of the small primes list and associated variables.
Would it not make more sense to keep as many of these private as
possible, and only export slow_is_prime_number() -- perhaps
conditionally if the test is enabled --, and use that from the test.
The lists of primes (both the small primes list and the rcu-controlled
larger cache) seem to me to still be implementation details, and the
test itself should share the existing ones.
(And, if we wanted the test to keep its own independent versions of
these, we'd still be in trouble, as the prime number library and the
test might access separate versions of the lists, if they're static to
separate files/modules.)
The only tricky bit would be handling dump_primes(): that could be
done either by exporting (perhaps conditionally / in a namespace) the
prime lists, and having dump_primes() be a part of the test, or
exporting dump_primes() -- which would be simpler, but make it harder
to use the kunit log functions.
Thoughts?
Cheers,
-- David
> lib/Kconfig.debug | 14 +++
> lib/math/prime_numbers.c | 151 +--------------------------
> lib/math/prime_numbers_private.h | 64 ++++++++++++
> lib/math/tests/Makefile | 1 +
> lib/math/tests/prime_numbers_kunit.c | 92 ++++++++++++++++
> tools/testing/selftests/lib/config | 1 -
> tools/testing/selftests/lib/prime_numbers.sh | 4 -
> 7 files changed, 173 insertions(+), 154 deletions(-)
>
> diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
> index 1af972a92d06..616beaca4a2b 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -3197,6 +3197,20 @@ config INT_SQRT_KUNIT_TEST
>
> If unsure, say N
>
> +config PRIME_NUMBERS_KUNIT_TEST
> + tristate "Prime number generator test" if !KUNIT_ALL_TESTS
> + depends on KUNIT
> + select PRIME_NUMBERS
> + default KUNIT_ALL_TESTS
> + help
> + This option enables the KUnit test suite for the {is,next}_prime_number
> + functions.
> +
> + Enabling this option will include tests that compare the prime number
> + generator functions against a brute force implementation.
> +
> + If unsure, say N
> +
> endif # RUNTIME_TESTING_MENU
>
> config ARCH_USE_MEMTEST
> diff --git a/lib/math/prime_numbers.c b/lib/math/prime_numbers.c
> index 9a17ee9af93a..0842b0826672 100644
> --- a/lib/math/prime_numbers.c
> +++ b/lib/math/prime_numbers.c
> @@ -1,70 +1,11 @@
> // SPDX-License-Identifier: GPL-2.0-only
> -#define pr_fmt(fmt) "prime numbers: " fmt
>
> -#include <linux/module.h>
> -#include <linux/mutex.h>
> #include <linux/prime_numbers.h>
> #include <linux/slab.h>
>
> -struct primes {
> - struct rcu_head rcu;
> - unsigned long last, sz;
> - unsigned long primes[];
> -};
> +#include "prime_numbers_private.h"
>
> -#if BITS_PER_LONG == 64
> -static const struct primes small_primes = {
> - .last = 61,
> - .sz = 64,
> - .primes = {
> - BIT(2) |
> - BIT(3) |
> - BIT(5) |
> - BIT(7) |
> - BIT(11) |
> - BIT(13) |
> - BIT(17) |
> - BIT(19) |
> - BIT(23) |
> - BIT(29) |
> - BIT(31) |
> - BIT(37) |
> - BIT(41) |
> - BIT(43) |
> - BIT(47) |
> - BIT(53) |
> - BIT(59) |
> - BIT(61)
> - }
> -};
> -#elif BITS_PER_LONG == 32
> -static const struct primes small_primes = {
> - .last = 31,
> - .sz = 32,
> - .primes = {
> - BIT(2) |
> - BIT(3) |
> - BIT(5) |
> - BIT(7) |
> - BIT(11) |
> - BIT(13) |
> - BIT(17) |
> - BIT(19) |
> - BIT(23) |
> - BIT(29) |
> - BIT(31)
> - }
> -};
> -#else
> -#error "unhandled BITS_PER_LONG"
> -#endif
> -
> -static DEFINE_MUTEX(lock);
> -static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes);
> -
> -static unsigned long selftest_max;
> -
> -static bool slow_is_prime_number(unsigned long x)
> +bool slow_is_prime_number(unsigned long x)
> {
> unsigned long y = int_sqrt(x);
>
> @@ -156,19 +97,6 @@ static bool expand_to_next_prime(unsigned long x)
> return true;
> }
>
> -static void free_primes(void)
> -{
> - const struct primes *p;
> -
> - mutex_lock(&lock);
> - p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
> - if (p != &small_primes) {
> - rcu_assign_pointer(primes, &small_primes);
> - kfree_rcu((struct primes *)p, rcu);
> - }
> - mutex_unlock(&lock);
> -}
> -
> /**
> * next_prime_number - return the next prime number
> * @x: the starting point for searching to test
> @@ -238,78 +166,3 @@ bool is_prime_number(unsigned long x)
> return result;
> }
> EXPORT_SYMBOL(is_prime_number);
> -
> -static void dump_primes(void)
> -{
> - const struct primes *p;
> - char *buf;
> -
> - buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
> -
> - rcu_read_lock();
> - p = rcu_dereference(primes);
> -
> - if (buf)
> - bitmap_print_to_pagebuf(true, buf, p->primes, p->sz);
> - pr_info("primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s\n",
> - p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf);
> -
> - rcu_read_unlock();
> -
> - kfree(buf);
> -}
> -
> -static int selftest(unsigned long max)
> -{
> - unsigned long x, last;
> -
> - if (!max)
> - return 0;
> -
> - for (last = 0, x = 2; x < max; x++) {
> - bool slow = slow_is_prime_number(x);
> - bool fast = is_prime_number(x);
> -
> - if (slow != fast) {
> - pr_err("inconsistent result for is-prime(%lu): slow=%s, fast=%s!\n",
> - x, slow ? "yes" : "no", fast ? "yes" : "no");
> - goto err;
> - }
> -
> - if (!slow)
> - continue;
> -
> - if (next_prime_number(last) != x) {
> - pr_err("incorrect result for next-prime(%lu): expected %lu, got %lu\n",
> - last, x, next_prime_number(last));
> - goto err;
> - }
> - last = x;
> - }
> -
> - pr_info("%s(%lu) passed, last prime was %lu\n", __func__, x, last);
> - return 0;
> -
> -err:
> - dump_primes();
> - return -EINVAL;
> -}
> -
> -static int __init primes_init(void)
> -{
> - return selftest(selftest_max);
> -}
> -
> -static void __exit primes_exit(void)
> -{
> - free_primes();
I'd argue that we should keep this here: the primes should be freed
when the prime number library exits, not the test.
> -}
> -
> -module_init(primes_init);
> -module_exit(primes_exit);
> -
> -module_param_named(selftest, selftest_max, ulong, 0400);
> -
> -MODULE_AUTHOR("Intel Corporation");
> -MODULE_DESCRIPTION("Prime number library");
> -MODULE_LICENSE("GPL");
> diff --git a/lib/math/prime_numbers_private.h b/lib/math/prime_numbers_private.h
> new file mode 100644
> index 000000000000..d0da5584aee8
> --- /dev/null
> +++ b/lib/math/prime_numbers_private.h
> @@ -0,0 +1,64 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +
> +#include <linux/bits.h>
> +#include <linux/mutex.h>
> +#include <linux/rcupdate.h>
> +#include <linux/types.h>
> +
> +struct primes {
> + struct rcu_head rcu;
> + unsigned long last, sz;
> + unsigned long primes[];
> +};
> +
> +#if BITS_PER_LONG == 64
> +static const struct primes small_primes = {
> + .last = 61,
> + .sz = 64,
> + .primes = {
> + BIT(2) |
> + BIT(3) |
> + BIT(5) |
> + BIT(7) |
> + BIT(11) |
> + BIT(13) |
> + BIT(17) |
> + BIT(19) |
> + BIT(23) |
> + BIT(29) |
> + BIT(31) |
> + BIT(37) |
> + BIT(41) |
> + BIT(43) |
> + BIT(47) |
> + BIT(53) |
> + BIT(59) |
> + BIT(61)
> + }
> +};
> +#elif BITS_PER_LONG == 32
> +static const struct primes small_primes = {
> + .last = 31,
> + .sz = 32,
> + .primes = {
> + BIT(2) |
> + BIT(3) |
> + BIT(5) |
> + BIT(7) |
> + BIT(11) |
> + BIT(13) |
> + BIT(17) |
> + BIT(19) |
> + BIT(23) |
> + BIT(29) |
> + BIT(31)
> + }
> +};
> +#else
> +#error "unhandled BITS_PER_LONG"
> +#endif
> +
> +static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes);
> +static DEFINE_MUTEX(lock);
> +
> +bool slow_is_prime_number(unsigned long x);
> diff --git a/lib/math/tests/Makefile b/lib/math/tests/Makefile
> index e1a79f093b2d..da21a592c75a 100644
> --- a/lib/math/tests/Makefile
> +++ b/lib/math/tests/Makefile
> @@ -2,3 +2,4 @@
>
> obj-$(CONFIG_INT_POW_TEST) += int_pow_kunit.o
> obj-$(CONFIG_INT_SQRT_KUNIT_TEST) += int_sqrt_kunit.o
> +obj-$(CONFIG_PRIME_NUMBERS_KUNIT_TEST) += prime_numbers_kunit.o
> diff --git a/lib/math/tests/prime_numbers_kunit.c b/lib/math/tests/prime_numbers_kunit.c
> new file mode 100644
> index 000000000000..8b0884887f20
> --- /dev/null
> +++ b/lib/math/tests/prime_numbers_kunit.c
> @@ -0,0 +1,92 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +
> +#include <kunit/test.h>
> +#include <linux/module.h>
> +#include <linux/prime_numbers.h>
> +#include <linux/slab.h>
> +
> +#include "../prime_numbers_private.h"
> +
> +static void free_primes(struct kunit_suite *suite)
> +{
> + const struct primes *p;
> +
> + mutex_lock(&lock);
> + p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
> + if (p != &small_primes) {
> + rcu_assign_pointer(primes, &small_primes);
> + kfree_rcu((struct primes *)p, rcu);
> + }
> + mutex_unlock(&lock);
> +}
> +
> +static void dump_primes(struct kunit *test)
> +{
> + const struct primes *p;
> + char *buf;
> +
> + buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
> +
> + rcu_read_lock();
> + p = rcu_dereference(primes);
> +
> + if (buf)
> + bitmap_print_to_pagebuf(true, buf, p->primes, p->sz);
> + kunit_info(test, "primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s\n",
> + p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf);
> +
> + rcu_read_unlock();
> +
> + kfree(buf);
> +}
> +
> +static void prime_numbers_test(struct kunit *test)
> +{
> + const unsigned long max = 65536;
> + unsigned long x, last;
> +
> + for (last = 0, x = 2; x < max; x++) {
> + bool slow = slow_is_prime_number(x);
> + bool fast = is_prime_number(x);
> +
> + if (slow != fast) {
> + KUNIT_FAIL(test,
> + "inconsistent result for is-prime(%lu): slow=%s, fast=%s!\n",
> + x, slow ? "yes" : "no", fast ? "yes" : "no");
> + goto err;
> + }
> +
> + if (!slow)
> + continue;
> +
> + if (next_prime_number(last) != x) {
> + KUNIT_FAIL(test,
> + "incorrect result for next-prime(%lu): expected %lu, got %lu\n",
> + last, x, next_prime_number(last));
> + goto err;
> + }
> + last = x;
> + }
> +
> + kunit_info(test, "%s(%lu) passed, last prime was %lu\n", __func__, x, last);
> +
> +err:
> + dump_primes(test);
> +}
> +
> +static struct kunit_case prime_numbers_cases[] = {
> + KUNIT_CASE(prime_numbers_test),
> + {},
> +};
> +
> +static struct kunit_suite prime_numbers_suite = {
> + .name = "math-prime_numbers",
> + .suite_exit = free_primes,
Should we be freeing the primes when the test exits? I suspect we
should leave them in case any other part of the kernel needs them.
(This, of course, potentially makes the test more brittle if run
multiple times (or on a system with already initialised primes), but
seems right to me.
> + .test_cases = prime_numbers_cases,
> +};
> +
> +kunit_test_suite(prime_numbers_suite);
> +
> +MODULE_AUTHOR("Intel Corporation");
> +MODULE_DESCRIPTION("Prime number library");
> +MODULE_LICENSE("GPL");
> diff --git a/tools/testing/selftests/lib/config b/tools/testing/selftests/lib/config
> index dc15aba8d0a3..306a3d4dca98 100644
> --- a/tools/testing/selftests/lib/config
> +++ b/tools/testing/selftests/lib/config
> @@ -1,5 +1,4 @@
> CONFIG_TEST_PRINTF=m
> CONFIG_TEST_SCANF=m
> CONFIG_TEST_BITMAP=m
> -CONFIG_PRIME_NUMBERS=m
> CONFIG_TEST_BITOPS=m
> diff --git a/tools/testing/selftests/lib/prime_numbers.sh b/tools/testing/selftests/lib/prime_numbers.sh
> deleted file mode 100755
> index 370b79a9cb2e..000000000000
> --- a/tools/testing/selftests/lib/prime_numbers.sh
> +++ /dev/null
> @@ -1,4 +0,0 @@
> -#!/bin/sh
> -# SPDX-License-Identifier: GPL-2.0
> -# Checks fast/slow prime_number generation for inconsistencies
> -$(dirname $0)/../kselftest/module.sh "prime numbers" prime_numbers selftest=65536
>
> --
> 2.48.1
>
Attachment:
smime.p7s
Description: S/MIME Cryptographic Signature
