diff options
Diffstat (limited to 'lib/math')
-rw-r--r-- | lib/math/Makefile | 5 | ||||
-rw-r--r-- | lib/math/prime_numbers.c | 91 | ||||
-rw-r--r-- | lib/math/prime_numbers_private.h | 16 | ||||
-rw-r--r-- | lib/math/tests/Makefile | 8 | ||||
-rw-r--r-- | lib/math/tests/gcd_kunit.c | 56 | ||||
-rw-r--r-- | lib/math/tests/int_log_kunit.c | 74 | ||||
-rw-r--r-- | lib/math/tests/prime_numbers_kunit.c | 59 | ||||
-rw-r--r-- | lib/math/tests/rational_kunit.c (renamed from lib/math/rational-test.c) | 0 |
8 files changed, 232 insertions, 77 deletions
diff --git a/lib/math/Makefile b/lib/math/Makefile index 853f023ae537..d1caba23baa0 100644 --- a/lib/math/Makefile +++ b/lib/math/Makefile @@ -5,8 +5,7 @@ obj-$(CONFIG_CORDIC) += cordic.o obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o obj-$(CONFIG_RATIONAL) += rational.o -obj-$(CONFIG_INT_POW_TEST) += tests/int_pow_kunit.o obj-$(CONFIG_TEST_DIV64) += test_div64.o obj-$(CONFIG_TEST_MULDIV64) += test_mul_u64_u64_div_u64.o -obj-$(CONFIG_RATIONAL_KUNIT_TEST) += rational-test.o -obj-$(CONFIG_INT_SQRT_KUNIT_TEST) += tests/int_sqrt_kunit.o
\ No newline at end of file + +obj-y += tests/ diff --git a/lib/math/prime_numbers.c b/lib/math/prime_numbers.c index 9a17ee9af93a..95a6f7960db9 100644 --- a/lib/math/prime_numbers.c +++ b/lib/math/prime_numbers.c @@ -1,16 +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 = { @@ -62,9 +57,25 @@ static const struct primes small_primes = { static DEFINE_MUTEX(lock); static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes); -static unsigned long selftest_max; +#if IS_ENABLED(CONFIG_PRIME_NUMBERS_KUNIT_TEST) +/* + * Calls the callback under RCU lock. The callback must not retain + * the primes pointer. + */ +void with_primes(void *ctx, primes_fn fn) +{ + rcu_read_lock(); + fn(ctx, rcu_dereference(primes)); + rcu_read_unlock(); +} +EXPORT_SYMBOL(with_primes); + +EXPORT_SYMBOL(slow_is_prime_number); -static bool slow_is_prime_number(unsigned long x) +#else +static +#endif +bool slow_is_prime_number(unsigned long x) { unsigned long y = int_sqrt(x); @@ -239,77 +250,13 @@ bool is_prime_number(unsigned long x) } 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(); } -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..f3ebf5386e6b --- /dev/null +++ b/lib/math/prime_numbers_private.h @@ -0,0 +1,16 @@ +/* SPDX-License-Identifier: GPL-2.0 */ + +#include <linux/types.h> + +struct primes { + struct rcu_head rcu; + unsigned long last, sz; + unsigned long primes[]; +}; + +#if IS_ENABLED(CONFIG_PRIME_NUMBERS_KUNIT_TEST) +typedef void (*primes_fn)(void *, const struct primes *); + +void with_primes(void *ctx, primes_fn fn); +bool slow_is_prime_number(unsigned long x); +#endif diff --git a/lib/math/tests/Makefile b/lib/math/tests/Makefile index e1a79f093b2d..13dc96e48408 100644 --- a/lib/math/tests/Makefile +++ b/lib/math/tests/Makefile @@ -1,4 +1,8 @@ # SPDX-License-Identifier: GPL-2.0-only -obj-$(CONFIG_INT_POW_TEST) += int_pow_kunit.o -obj-$(CONFIG_INT_SQRT_KUNIT_TEST) += int_sqrt_kunit.o +obj-$(CONFIG_GCD_KUNIT_TEST) += gcd_kunit.o +obj-$(CONFIG_INT_LOG_KUNIT_TEST) += int_log_kunit.o +obj-$(CONFIG_INT_POW_KUNIT_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 +obj-$(CONFIG_RATIONAL_KUNIT_TEST) += rational_kunit.o diff --git a/lib/math/tests/gcd_kunit.c b/lib/math/tests/gcd_kunit.c new file mode 100644 index 000000000000..ede1883583b1 --- /dev/null +++ b/lib/math/tests/gcd_kunit.c @@ -0,0 +1,56 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include <kunit/test.h> +#include <linux/gcd.h> +#include <linux/limits.h> + +struct test_case_params { + unsigned long val1; + unsigned long val2; + unsigned long expected_result; + const char *name; +}; + +static const struct test_case_params params[] = { + { 48, 18, 6, "GCD of 48 and 18" }, + { 18, 48, 6, "GCD of 18 and 48" }, + { 56, 98, 14, "GCD of 56 and 98" }, + { 17, 13, 1, "Coprime numbers" }, + { 101, 103, 1, "Coprime numbers" }, + { 270, 192, 6, "GCD of 270 and 192" }, + { 0, 5, 5, "GCD with zero" }, + { 7, 0, 7, "GCD with zero reversed" }, + { 36, 36, 36, "GCD of identical numbers" }, + { ULONG_MAX, 1, 1, "GCD of max ulong and 1" }, + { ULONG_MAX, ULONG_MAX, ULONG_MAX, "GCD of max ulong values" }, +}; + +static void get_desc(const struct test_case_params *tc, char *desc) +{ + strscpy(desc, tc->name, KUNIT_PARAM_DESC_SIZE); +} + +KUNIT_ARRAY_PARAM(gcd, params, get_desc); + +static void gcd_test(struct kunit *test) +{ + const struct test_case_params *tc = (const struct test_case_params *)test->param_value; + + KUNIT_EXPECT_EQ(test, tc->expected_result, gcd(tc->val1, tc->val2)); +} + +static struct kunit_case math_gcd_test_cases[] = { + KUNIT_CASE_PARAM(gcd_test, gcd_gen_params), + {} +}; + +static struct kunit_suite gcd_test_suite = { + .name = "math-gcd", + .test_cases = math_gcd_test_cases, +}; + +kunit_test_suite(gcd_test_suite); + +MODULE_LICENSE("GPL"); +MODULE_DESCRIPTION("math.gcd KUnit test suite"); +MODULE_AUTHOR("Yu-Chun Lin <eleanor15x@gmail.com>"); diff --git a/lib/math/tests/int_log_kunit.c b/lib/math/tests/int_log_kunit.c new file mode 100644 index 000000000000..14e854146cb4 --- /dev/null +++ b/lib/math/tests/int_log_kunit.c @@ -0,0 +1,74 @@ +// SPDX-License-Identifier: GPL-2.0-only +#include <kunit/test.h> +#include <linux/int_log.h> + +struct test_case_params { + u32 value; + unsigned int expected_result; + const char *name; +}; + + +/* The expected result takes into account the log error */ +static const struct test_case_params intlog2_params[] = { + {0, 0, "Log base 2 of 0"}, + {1, 0, "Log base 2 of 1"}, + {2, 16777216, "Log base 2 of 2"}, + {3, 26591232, "Log base 2 of 3"}, + {4, 33554432, "Log base 2 of 4"}, + {8, 50331648, "Log base 2 of 8"}, + {16, 67108864, "Log base 2 of 16"}, + {32, 83886080, "Log base 2 of 32"}, + {U32_MAX, 536870911, "Log base 2 of MAX"}, +}; + +static const struct test_case_params intlog10_params[] = { + {0, 0, "Log base 10 of 0"}, + {1, 0, "Log base 10 of 1"}, + {6, 13055203, "Log base 10 of 6"}, + {10, 16777225, "Log base 10 of 10"}, + {100, 33554450, "Log base 10 of 100"}, + {1000, 50331675, "Log base 10 of 1000"}, + {10000, 67108862, "Log base 10 of 10000"}, + {U32_MAX, 161614247, "Log base 10 of MAX"} +}; + +static void get_desc(const struct test_case_params *tc, char *desc) +{ + strscpy(desc, tc->name, KUNIT_PARAM_DESC_SIZE); +} + + +KUNIT_ARRAY_PARAM(intlog2, intlog2_params, get_desc); + +static void intlog2_test(struct kunit *test) +{ + const struct test_case_params *tc = (const struct test_case_params *)test->param_value; + + KUNIT_EXPECT_EQ(test, tc->expected_result, intlog2(tc->value)); +} + +KUNIT_ARRAY_PARAM(intlog10, intlog10_params, get_desc); + +static void intlog10_test(struct kunit *test) +{ + const struct test_case_params *tc = (const struct test_case_params *)test->param_value; + + KUNIT_EXPECT_EQ(test, tc->expected_result, intlog10(tc->value)); +} + +static struct kunit_case math_int_log_test_cases[] = { + KUNIT_CASE_PARAM(intlog2_test, intlog2_gen_params), + KUNIT_CASE_PARAM(intlog10_test, intlog10_gen_params), + {} +}; + +static struct kunit_suite int_log_test_suite = { + .name = "math-int_log", + .test_cases = math_int_log_test_cases, +}; + +kunit_test_suites(&int_log_test_suite); + +MODULE_DESCRIPTION("math.int_log KUnit test suite"); +MODULE_LICENSE("GPL"); diff --git a/lib/math/tests/prime_numbers_kunit.c b/lib/math/tests/prime_numbers_kunit.c new file mode 100644 index 000000000000..2f1643208c66 --- /dev/null +++ b/lib/math/tests/prime_numbers_kunit.c @@ -0,0 +1,59 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include <kunit/test.h> +#include <linux/module.h> +#include <linux/prime_numbers.h> + +#include "../prime_numbers_private.h" + +static void dump_primes(void *ctx, const struct primes *p) +{ + static char buf[PAGE_SIZE]; + struct kunit_suite *suite = ctx; + + bitmap_print_to_pagebuf(true, buf, p->primes, p->sz); + kunit_info(suite, "primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s", + p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf); +} + +static void prime_numbers_test(struct kunit *test) +{ + const unsigned long max = 65536; + unsigned long x, last, next; + + for (last = 0, x = 2; x < max; x++) { + const bool slow = slow_is_prime_number(x); + const bool fast = is_prime_number(x); + + KUNIT_ASSERT_EQ_MSG(test, slow, fast, "is-prime(%lu)", x); + + if (!slow) + continue; + + next = next_prime_number(last); + KUNIT_ASSERT_EQ_MSG(test, next, x, "next-prime(%lu)", last); + last = next; + } +} + +static void kunit_suite_exit(struct kunit_suite *suite) +{ + with_primes(suite, dump_primes); +} + +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 = kunit_suite_exit, + .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/lib/math/rational-test.c b/lib/math/tests/rational_kunit.c index 47486a95f088..47486a95f088 100644 --- a/lib/math/rational-test.c +++ b/lib/math/tests/rational_kunit.c |