Re: [Intel-gfx] [PATCH v3 04/38] lib: Add a simple prime number generator

[Chris Wilson]

On Fri, Dec 16, 2016 at 07:25:16PM +, Chris Wilson wrote:
> +static void __exit primes_exit(void)
> +{
> + const struct primes *p;
> +
> + mutex_lock();
> + p = rcu_dereference_protected(primes, lockdep_is_held());
> + if (p != _primes) {
> + kfree_rcu((struct primes *)p, rcu);
> + rcu_assign_pointer(p, _primes);

Too much sparse appleasing, too little thinking. It's only the module
shutdown path, but we might as well be correct: s/p/primes here.
-Chris
> 

-- 
Chris Wilson, Intel Open Source Technology Centre
___
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx

[Intel-gfx] [PATCH v3 04/38] lib: Add a simple prime number generator

[Chris Wilson]

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

Signed-off-by: Chris Wilson 
Cc: Lukas Wunner 
---
 include/linux/prime_numbers.h |  13 +++
 lib/Kconfig   |   7 ++
 lib/Makefile  |   2 +
 lib/prime_numbers.c   | 238 ++
 4 files changed, 260 insertions(+)
 create mode 100644 include/linux/prime_numbers.h
 create mode 100644 lib/prime_numbers.c

diff --git a/include/linux/prime_numbers.h b/include/linux/prime_numbers.h
new file mode 100644
index ..877f6acbd0b6
--- /dev/null
+++ b/include/linux/prime_numbers.h
@@ -0,0 +1,13 @@
+#ifndef __LINUX_PRIME_NUMBERS_H
+#define __LINUX_PRIME_NUMBERS_H
+
+#include 
+
+bool is_prime_number(unsigned long x);
+unsigned long next_prime_number(unsigned long x);
+
+/* A useful white-lie here is that 1 is prime. */
+#define for_each_prime_number(prime, max) \
+   for (prime = 1; 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 ..ec2959520653
--- /dev/null
+++ b/lib/prime_numbers.c
@@ -0,0 +1,238 @@
+#define pr_fmt(fmt) "prime numbers: " fmt "\n"
+
+#include 
+#include 
+#include 
+#include 
+
+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 = { 0x28208a20a08a28acUL }
+};
+#elif BITS_PER_LONG == 32
+static const struct primes small_primes = {
+   .last = 31,
+   .sz = 32,
+   .primes = { 0xa08a28acUL }
+};
+#else
+#error "unhandled BITS_PER_LONG"
+#endif
+
+static DEFINE_MUTEX(lock);
+static const struct primes __rcu *primes = RCU_INITIALIZER(_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)
+{
+   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 = roundup(start, x);
+
+   while (m < end) {
+   __clear_bit(m, p);
+   m += x;
+   }
+
+   return x;
+}
+
+static const struct primes *expand_to_next(unsigned long x)
+{
+   const struct primes *p;
+   struct primes *new;
+   unsigned long sz, y;
+
+   rcu_read_unlock();
+
+   /* 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 NULL;
+
+   sz = round_up(sz, BITS_PER_LONG);
+   new = kmalloc(sizeof(*new) + sz / sizeof(long), GFP_KERNEL);
+   if (!new)
+   return NULL;
+
+   mutex_lock();
+   p = rcu_dereference_protected(primes, lockdep_is_held());
+   if (x < p->last) {
+   kfree(new);
+   goto relock;
+   }
+
+   /* Where memory permits, track the primes using the
+* Sieve of Eratosthenes.
+*/
+   memcpy(new->primes, p->primes, p->sz / BITS_PER_LONG * sizeof(long));
+   memset(new->primes + p->sz / BITS_PER_LONG,
+  0xff, (sz - p->sz) / BITS_PER_LONG * sizeof(long));
+   for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1))
+   new->last = mark_multiples(y, new->primes, p->sz, sz);
+