Re: [PATCH v10] lib: Add a simple prime number generator

[Daniel Vetter <daniel@ffwll.ch>]

On Thu, Dec 22, 2016 at 02:45:14PM +0000, Chris Wilson wrote:
> Prime numbers are interesting for testing components that use multiplies
> and divides, such as testing DRM's struct drm_mm alignment computations.
> 
> v2: Move to lib/, add selftest
> v3: Fix initial constants (exclude 0/1 from being primes)
> v4: More RCU markup to keep 0day/sparse happy
> v5: Fix RCU unwind on module exit, add to kselftests
> v6: Tidy computation of bitmap size
> v7: for_each_prime_number_from()
> v8: Compose small-primes using BIT() for easier verification
> v9: Move rcu dance entirely into callers.
> v10: Improve quote for Betrand's Postulate (aka Chebyshev's theorem)
> 
> Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> Cc: Lukas Wunner <lukas@wunner.de>
> Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
> ---
>  include/linux/prime_numbers.h                |  37 ++++
>  lib/Kconfig                                  |   7 +
>  lib/Makefile                                 |   2 +
>  lib/prime_numbers.c                          | 314 +++++++++++++++++++++++++++
>  tools/testing/selftests/lib/prime_numbers.sh |  15 ++

You typed all that nice kernel-doc, but no stanza in any .rst to pull it
in. Can you pls fix that up in a follow-up, cc: linux-doc@vger?
-Daniel

>  5 files changed, 375 insertions(+)
>  create mode 100644 include/linux/prime_numbers.h
>  create mode 100644 lib/prime_numbers.c
>  create mode 100755 tools/testing/selftests/lib/prime_numbers.sh
> 
> diff --git a/include/linux/prime_numbers.h b/include/linux/prime_numbers.h
> new file mode 100644
> index 000000000000..14ec4f567342
> --- /dev/null
> +++ b/include/linux/prime_numbers.h
> @@ -0,0 +1,37 @@
> +#ifndef __LINUX_PRIME_NUMBERS_H
> +#define __LINUX_PRIME_NUMBERS_H
> +
> +#include <linux/types.h>
> +
> +bool is_prime_number(unsigned long x);
> +unsigned long next_prime_number(unsigned long x);
> +
> +/**
> + * for_each_prime_number - iterate over each prime upto a value
> + * @prime: the current prime number in this iteration
> + * @max: the upper limit
> + *
> + * Starting from the first prime number 2 iterate over each prime number up to
> + * the @max value. On each iteration, @prime is set to the current prime number.
> + * @max should be less than ULONG_MAX to ensure termination. To begin with
> + * @prime set to 1 on the first iteration use for_each_prime_number_from()
> + * instead.
> + */
> +#define for_each_prime_number(prime, max) \
> +	for_each_prime_number_from((prime), 2, (max))
> +
> +/**
> + * for_each_prime_number_from - iterate over each prime upto a value
> + * @prime: the current prime number in this iteration
> + * @from: the initial value
> + * @max: the upper limit
> + *
> + * Starting from @from iterate over each successive prime number up to the
> + * @max value. On each iteration, @prime is set to the current prime number.
> + * @max should be less than ULONG_MAX, and @from less than @max, to ensure
> + * termination.
> + */
> +#define for_each_prime_number_from(prime, from, max) \
> +	for (prime = (from); prime <= (max); prime = next_prime_number(prime))
> +
> +#endif /* !__LINUX_PRIME_NUMBERS_H */
> diff --git a/lib/Kconfig b/lib/Kconfig
> index 260a80e313b9..1788a1f50d28 100644
> --- a/lib/Kconfig
> +++ b/lib/Kconfig
> @@ -550,4 +550,11 @@ config STACKDEPOT
>  config SBITMAP
>  	bool
>  
> +config PRIME_NUMBERS
> +	tristate "Prime number generator"
> +	default n
> +	help
> +	  Provides a helper module to generate prime numbers. Useful for writing
> +	  test code, especially when checking multiplication and divison.
> +
>  endmenu
> diff --git a/lib/Makefile b/lib/Makefile
> index 50144a3aeebd..c664143fd917 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -197,6 +197,8 @@ obj-$(CONFIG_ASN1) += asn1_decoder.o
>  
>  obj-$(CONFIG_FONT_SUPPORT) += fonts/
>  
> +obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o
> +
>  hostprogs-y	:= gen_crc32table
>  clean-files	:= crc32table.h
>  
> diff --git a/lib/prime_numbers.c b/lib/prime_numbers.c
> new file mode 100644
> index 000000000000..c9b3c29614aa
> --- /dev/null
> +++ b/lib/prime_numbers.c
> @@ -0,0 +1,314 @@
> +#define pr_fmt(fmt) "prime numbers: " fmt "\n"
> +
> +#include <linux/module.h>
> +#include <linux/mutex.h>
> +#include <linux/prime_numbers.h>
> +#include <linux/slab.h>
> +
> +#define bitmap_size(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long))
> +
> +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 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)
> +{
> +	unsigned long y = int_sqrt(x);
> +
> +	while (y > 1) {
> +		if ((x % y) == 0)
> +			break;
> +		y--;
> +	}
> +
> +	return y == 1;
> +}
> +
> +static unsigned long slow_next_prime_number(unsigned long x)
> +{
> +	while (x < ULONG_MAX && !slow_is_prime_number(++x))
> +		;
> +
> +	return x;
> +}
> +
> +static unsigned long clear_multiples(unsigned long x,
> +				     unsigned long *p,
> +				     unsigned long start,
> +				     unsigned long end)
> +{
> +	unsigned long m;
> +
> +	m = 2 * x;
> +	if (m < start)
> +		m = roundup(start, x);
> +
> +	while (m < end) {
> +		__clear_bit(m, p);
> +		m += x;
> +	}
> +
> +	return x;
> +}
> +
> +static bool expand_to_next_prime(unsigned long x)
> +{
> +	const struct primes *p;
> +	struct primes *new;
> +	unsigned long sz, y;
> +
> +	/* Betrand's Postulate (or Chebyshev's theorem) states that if n > 3,
> +	 * there is always at least one prime p between n and 2n - 2.
> +	 * Equivalently, if n > 1, then there is always at least one prime p
> +	 * such that n < p < 2n.
> +	 *
> +	 * http://mathworld.wolfram.com/BertrandsPostulate.html
> +	 * https://en.wikipedia.org/wiki/Bertrand's_postulate
> +	 */
> +	sz = 2 * x;
> +	if (sz < x)
> +		return false;
> +
> +	sz = round_up(sz, BITS_PER_LONG);
> +	new = kmalloc(sizeof(*new) + bitmap_size(sz), GFP_KERNEL);
> +	if (!new)
> +		return false;
> +
> +	mutex_lock(&lock);
> +	p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
> +	if (x < p->last) {
> +		kfree(new);
> +		goto unlock;
> +	}
> +
> +	/* Where memory permits, track the primes using the
> +	 * Sieve of Eratosthenes. The sieve is to remove all multiples of known
> +	 * primes from the set, what remains in the set is therefore prime.
> +	 */
> +	bitmap_fill(new->primes, sz);
> +	bitmap_copy(new->primes, p->primes, p->sz);
> +	for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1))
> +		new->last = clear_multiples(y, new->primes, p->sz, sz);
> +	new->sz = sz;
> +
> +	BUG_ON(new->last <= x);
> +
> +	rcu_assign_pointer(primes, new);
> +	if (p != &small_primes)
> +		kfree_rcu((struct primes *)p, rcu);
> +
> +unlock:
> +	mutex_unlock(&lock);
> +	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
> + *
> + * A prime number is an integer greater than 1 that is only divisible by
> + * itself and 1.  The set of prime numbers is computed using the Sieve of
> + * Eratoshenes (on finding a prime, all multiples of that prime are removed
> + * from the set) enabling a fast lookup of the next prime number larger than
> + * @x. If the sieve fails (memory limitation), the search falls back to using
> + * slow trial-divison, up to the value of ULONG_MAX (which is reported as the
> + * final prime as a sentinel).
> + *
> + * Returns: the next prime number larger than @x
> + */
> +unsigned long next_prime_number(unsigned long x)
> +{
> +	const struct primes *p;
> +
> +	rcu_read_lock();
> +	p = rcu_dereference(primes);
> +	while (x >= p->last) {
> +		rcu_read_unlock();
> +
> +		if (!expand_to_next_prime(x))
> +			return slow_next_prime_number(x);
> +
> +		rcu_read_lock();
> +		p = rcu_dereference(primes);
> +	}
> +	x = find_next_bit(p->primes, p->last, x + 1);
> +	rcu_read_unlock();
> +
> +	return x;
> +}
> +EXPORT_SYMBOL(next_prime_number);
> +
> +/**
> + * is_prime_number - test whether the given number is prime
> + * @x: the number to test
> + *
> + * A prime number is an integer greater than 1 that is only divisible by
> + * itself and 1. Internally a cache of prime numbers is kept (to speed up
> + * searching for sequential primes, see next_prime_number()), but if the number
> + * falls outside of that cache, its primality is tested using trial-divison.
> + *
> + * Returns: true if @x is prime, false for composite numbers.
> + */
> +bool is_prime_number(unsigned long x)
> +{
> +	const struct primes *p;
> +	bool result;
> +
> +	rcu_read_lock();
> +	p = rcu_dereference(primes);
> +	while (x >= p->sz) {
> +		rcu_read_unlock();
> +
> +		if (!expand_to_next_prime(x))
> +			return slow_is_prime_number(x);
> +
> +		rcu_read_lock();
> +		p = rcu_dereference(primes);
> +	}
> +	result = test_bit(x, p->primes);
> +	rcu_read_unlock();
> +
> +	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",
> +		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!",
> +			       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",
> +			       last, x, next_prime_number(last));
> +			goto err;
> +		}
> +		last = x;
> +	}
> +
> +	pr_info("selftest(%lu) passed, last prime was %lu", 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_LICENSE("GPL");
> diff --git a/tools/testing/selftests/lib/prime_numbers.sh b/tools/testing/selftests/lib/prime_numbers.sh
> new file mode 100755
> index 000000000000..da4cbcd766f5
> --- /dev/null
> +++ b/tools/testing/selftests/lib/prime_numbers.sh
> @@ -0,0 +1,15 @@
> +#!/bin/sh
> +# Checks fast/slow prime_number generation for inconsistencies
> +
> +if ! /sbin/modprobe -q -r prime_numbers; then
> +	echo "prime_numbers: [SKIP]"
> +	exit 77
> +fi
> +
> +if /sbin/modprobe -q prime_numbers selftest=65536; then
> +	/sbin/modprobe -q -r prime_numbers
> +	echo "prime_numbers: ok"
> +else
> +	echo "prime_numbers: [FAIL]"
> +	exit 1
> +fi
> -- 
> 2.11.0
> 
> _______________________________________________
> Intel-gfx mailing list
> Intel-gfx@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/intel-gfx

-- 
Daniel Vetter
Software Engineer, Intel Corporation
http://blog.ffwll.ch
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx