[PATCH 07/34] drm: Add a simple prime number generator

[Chris Wilson]

Prime numbers are interesting for testing components that use multiplies
and divides, such as testing struct drm_mm alignment computations.

Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
---
 drivers/gpu/drm/Kconfig                 |   5 +
 drivers/gpu/drm/Makefile                |   1 +
 drivers/gpu/drm/lib/drm_prime_numbers.c | 174 ++++++++++++++++++++++++++++++++
 drivers/gpu/drm/lib/drm_prime_numbers.h |  10 ++
 4 files changed, 190 insertions(+)
 create mode 100644 drivers/gpu/drm/lib/drm_prime_numbers.c
 create mode 100644 drivers/gpu/drm/lib/drm_prime_numbers.h

diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig
index 04d1d0a32c5c..09f076896844 100644
--- a/drivers/gpu/drm/Kconfig
+++ b/drivers/gpu/drm/Kconfig
@@ -52,11 +52,16 @@ config DRM_LIB_RAND
 	bool
 	default n
 
+config DRM_LIB_PRIMES
+	bool
+	default n
+
 config DRM_DEBUG_MM_SELFTEST
 	tristate "kselftests for DRM range manager (struct drm_mm)"
 	depends on DRM
 	depends on DEBUG_KERNEL
 	select DRM_LIB_RAND
+	select DRM_LIB_PRIMES
 	default n
 	help
 	  This option provides a kernel module that can be used to test
diff --git a/drivers/gpu/drm/Makefile b/drivers/gpu/drm/Makefile
index 363eb1a23151..24fe5d47960a 100644
--- a/drivers/gpu/drm/Makefile
+++ b/drivers/gpu/drm/Makefile
@@ -19,6 +19,7 @@ drm-y       :=	drm_auth.o drm_bufs.o drm_cache.o \
 		drm_dumb_buffers.o drm_mode_config.o
 
 drm-$(CONFIG_DRM_LIB_RAND) += lib/drm_rand.o
+obj-$(CONFIG_DRM_LIB_PRIMES) += lib/drm_prime_numbers.o
 obj-$(CONFIG_DRM_DEBUG_MM_SELFTEST) += selftests/test-drm_mm.o
 
 drm-$(CONFIG_COMPAT) += drm_ioc32.o
diff --git a/drivers/gpu/drm/lib/drm_prime_numbers.c b/drivers/gpu/drm/lib/drm_prime_numbers.c
new file mode 100644
index 000000000000..c6cc0c32ce22
--- /dev/null
+++ b/drivers/gpu/drm/lib/drm_prime_numbers.c
@@ -0,0 +1,174 @@
+#include <linux/module.h>
+#include <linux/mutex.h>
+#include <linux/slab.h>
+
+#include "drm_prime_numbers.h"
+
+static DEFINE_MUTEX(lock);
+
+static struct primes {
+	struct rcu_head rcu;
+	unsigned long last, sz;
+	unsigned long primes[];
+} __rcu *primes;
+
+static bool slow_is_prime_number(unsigned long x)
+{
+	unsigned long y = int_sqrt(x) + 1;
+
+	while (y > 1) {
+		if ((x % y) == 0)
+			break;
+		y--;
+	}
+
+	return y == 1;
+}
+
+static unsigned long slow_next_prime_number(unsigned long x)
+{
+	for (;;) {
+		if (slow_is_prime_number(++x))
+			return x;
+	}
+}
+
+static unsigned long mark_multiples(unsigned long x,
+				    unsigned long *p,
+				    unsigned long start,
+				    unsigned long end)
+{
+	unsigned long m;
+
+	m = 2 * x;
+	if (m < start)
+		m = (start / x + 1) * x;
+
+	while (m < end) {
+		__clear_bit(m, p);
+		m += x;
+	}
+
+	return x;
+}
+
+static struct primes *expand(unsigned long x)
+{
+	unsigned long sz, y, prev;
+	struct primes *p, *new;
+
+	sz = x * x;
+	if (sz < x)
+		return NULL;
+
+	mutex_lock(&lock);
+	p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
+	if (p && x < p->last)
+		goto unlock;
+
+	sz = round_up(sz, BITS_PER_LONG);
+	new = kmalloc(sizeof(*new) + sz / sizeof(long), GFP_KERNEL);
+	if (!new) {
+		p = NULL;
+		goto unlock;
+	}
+
+	/* Where memory permits, track the primes using the
+	 * Sieve of Eratosthenes.
+	 */
+	if (p) {
+		prev = p->sz;
+		memcpy(new->primes, p->primes, prev / BITS_PER_LONG);
+	} else {
+		prev = 0;
+	}
+	memset(new->primes + prev / BITS_PER_LONG,
+	       0xff, (sz - prev) / sizeof(long));
+	for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1))
+		new->last = mark_multiples(y, new->primes, prev, sz);
+	new->sz = sz;
+
+	rcu_assign_pointer(primes, new);
+	if (p)
+		kfree_rcu(p, rcu);
+	p = new;
+
+unlock:
+	mutex_unlock(&lock);
+	return p;
+}
+
+unsigned long drm_next_prime_number(unsigned long x)
+{
+	struct primes *p;
+
+	if (x < 2)
+		return 2;
+
+	rcu_read_lock();
+	p = rcu_dereference(primes);
+	if (!p || x >= p->last) {
+		rcu_read_unlock();
+
+		p = expand(x);
+		if (!p)
+			return slow_next_prime_number(x);
+
+		rcu_read_lock();
+	}
+
+	x = find_next_bit(p->primes, p->last, x + 1);
+	rcu_read_unlock();
+
+	return x;
+}
+EXPORT_SYMBOL(drm_next_prime_number);
+
+bool drm_is_prime_number(unsigned long x)
+{
+	struct primes *p;
+	bool result;
+
+	switch (x) {
+	case 0:
+		return false;
+	case 1:
+	case 2:
+	case 3:
+		return true;
+	}
+
+	rcu_read_lock();
+	p = rcu_dereference(primes);
+	if (!p || x >= p->last) {
+		rcu_read_unlock();
+
+		p = expand(x);
+		if (!p)
+			return slow_is_prime_number(x);
+
+		rcu_read_lock();
+	}
+
+	result = test_bit(x, p->primes);
+	rcu_read_unlock();
+
+	return result;
+}
+EXPORT_SYMBOL(drm_is_prime_number);
+
+static int __init drm_primes_init(void)
+{
+	return 0;
+}
+
+static void __exit drm_primes_exit(void)
+{
+	kfree(primes);
+}
+
+module_init(drm_primes_init);
+module_exit(drm_primes_exit);
+
+MODULE_AUTHOR("Intel Corporation");
+MODULE_LICENSE("GPL");
diff --git a/drivers/gpu/drm/lib/drm_prime_numbers.h b/drivers/gpu/drm/lib/drm_prime_numbers.h
new file mode 100644
index 000000000000..7bc58cf9a86c
--- /dev/null
+++ b/drivers/gpu/drm/lib/drm_prime_numbers.h
@@ -0,0 +1,10 @@
+#ifndef __DRM_PRIMES_H__
+#define __DRM_PRIMES_H__
+
+bool drm_is_prime_number(unsigned long x);
+unsigned long drm_next_prime_number(unsigned long x);
+
+#define drm_for_each_prime(prime, max) \
+	for (prime = 1;	prime < (max); prime = drm_next_prime_number(prime))
+
+#endif /* __DRM_PRIMES_H__ */
-- 
2.11.0