diff mbox

[v4,04/38] lib: Add a simple prime number generator

Message ID 20161222083641.2691-5-chris@chris-wilson.co.uk (mailing list archive)
State New, archived
Headers show

Commit Message

Chris Wilson Dec. 22, 2016, 8:36 a.m. UTC
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.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
Cc: Lukas Wunner <lukas@wunner.de>
---
 include/linux/prime_numbers.h                |  37 ++++
 lib/Kconfig                                  |   7 +
 lib/Makefile                                 |   2 +
 lib/prime_numbers.c                          | 304 +++++++++++++++++++++++++++
 tools/testing/selftests/lib/prime_numbers.sh |  15 ++
 5 files changed, 365 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

Comments

Joonas Lahtinen Dec. 22, 2016, 9:52 a.m. UTC | #1
On to, 2016-12-22 at 08:36 +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.
> 
> Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> Cc: Lukas Wunner <lukas@wunner.de>

<SNIP>

> +static bool expand_to_next_prime(unsigned long x)
> +{
> +	const struct primes *p;
> +	struct primes *new;
> +	unsigned long sz, y;
> +
> +	/* Betrand's Theorem states:

"From Bertrand's postulate:"

> +	 * 	For all n > 1, there exists a prime p: n < p <= 2*n.

"n < p < 2*n"

> +	 */
> +	sz = 2 * x + 1;

And I'd also drop the + 1, not that it matters much.

Reviewed-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>

Regards, Joonas
Chris Wilson Dec. 22, 2016, 10 a.m. UTC | #2
On Thu, Dec 22, 2016 at 11:52:45AM +0200, Joonas Lahtinen wrote:
> On to, 2016-12-22 at 08:36 +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.
> > 
> > Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> > Cc: Lukas Wunner <lukas@wunner.de>
> 
> <SNIP>
> 
> > +static bool expand_to_next_prime(unsigned long x)
> > +{
> > +	const struct primes *p;
> > +	struct primes *new;
> > +	unsigned long sz, y;
> > +
> > +	/* Betrand's Theorem states:
> 
> "From Bertrand's postulate:"

It has been proven, so it should be referred to as a theorem! :)
Anyway, Wolfram calls it Betrand's postulate, Bertrand-Chebyshev theorem
or Chebyshev's theorem, so pretty ambigious. I've updated the quote to
include the full statement (as well as the simplified version for us)
and a couple of links to wikipedia and Wolfram for easy reference.
-Chris
diff mbox

Patch

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..1e4dcbf99619
--- /dev/null
+++ b/lib/prime_numbers.c
@@ -0,0 +1,304 @@ 
+#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 Theorem states:
+	 * 	For all n > 1, there exists a prime p: n < p <= 2*n.
+	 */
+	sz = 2 * x + 1;
+	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;
+}
+
+/**
+ * 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)
+{
+	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);
+}
+
+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