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 <ch...@chris-wilson.co.uk>
---
drivers/gpu/drm/Kconfig | 4 +
drivers/gpu/drm/Makefile | 1 +
drivers/gpu/drm/lib/drm_prime_numbers.c | 175 ++++++++++++++++++++++++++++++++
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 2e6ae95459e4..93895898d596 100644
--- a/drivers/gpu/drm/Kconfig
+++ b/drivers/gpu/drm/Kconfig
@@ -53,6 +53,7 @@ config DRM_DEBUG_MM_SELFTEST
depends on DRM
depends on DEBUG_KERNEL
select DRM_LIB_RANDOM
+ select DRM_LIB_PRIMES
default n
help
This option provides a kernel module that can be used to test
@@ -340,3 +341,6 @@ config DRM_LIB_RANDOM
bool
default n
+config DRM_LIB_PRIMES
+ bool
+ default n
diff --git a/drivers/gpu/drm/Makefile b/drivers/gpu/drm/Makefile
index 0fa16275fdae..bbd390fa8914 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_RANDOM) += lib/drm_random.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..839563d9b787
--- /dev/null
+++ b/drivers/gpu/drm/lib/drm_prime_numbers.c
@@ -0,0 +1,175 @@
+#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)
+{
+ if (primes)
+ kfree_rcu(primes, rcu);
+}
+
+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
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx
