subject:"\[Intel\-gfx\] \[PATCH v2 08\/40\] drm\: Add a simple prime number generator"

Re: [Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

2016-12-16 Thread Chris Wilson

On Fri, Dec 16, 2016 at 11:08:10AM +0100, Lukas Wunner wrote:
> On Fri, Dec 16, 2016 at 09:43:54AM +, Chris Wilson wrote:
> > On Fri, Dec 16, 2016 at 10:31:17AM +0100, Lukas Wunner wrote:
> > > On Fri, Dec 16, 2016 at 07:46:46AM +, Chris Wilson wrote:
> > > > 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 
> > > > ---
> > > >  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
> > > 
> > > Hm, why not put this in lib/ ?  Don't see anything DRM-specific here
> > > at first glance and this might be useful to others.  Or others might
> > > come up with improvements and they'll be more likely to discover it
> > > outside of DRM.
> > 
> > Because that is a 3+ month cycle before I can then apply the testcases,
> > and without the testscases do you want the bugfixes?
> 
> Do patches for lib/ have to go through a different tree?
> Don't think so, I've seen e.g. changes to lib/ucs2_string.c
> go through the EFI tree.  It seems to me lib/ is sort of
> free for all.

Hmm, I was expecting to shepherd them through say Andrew Morton.
lib/random32.c is maintained by David Miller, so definitely would like
to present a simple set of pre-reviewed patches.

But it looks like we could create lib/prime_numbers.c without too much
consternation.
-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

Re: [Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

2016-12-16 Thread Lukas Wunner

On Fri, Dec 16, 2016 at 09:43:54AM +, Chris Wilson wrote:
> On Fri, Dec 16, 2016 at 10:31:17AM +0100, Lukas Wunner wrote:
> > On Fri, Dec 16, 2016 at 07:46:46AM +, Chris Wilson wrote:
> > > 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 
> > > ---
> > >  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
> > 
> > Hm, why not put this in lib/ ?  Don't see anything DRM-specific here
> > at first glance and this might be useful to others.  Or others might
> > come up with improvements and they'll be more likely to discover it
> > outside of DRM.
> 
> Because that is a 3+ month cycle before I can then apply the testcases,
> and without the testscases do you want the bugfixes?

Do patches for lib/ have to go through a different tree?
Don't think so, I've seen e.g. changes to lib/ucs2_string.c
go through the EFI tree.  It seems to me lib/ is sort of
free for all.


> If I put in in drm/lib then lift it, I can use it immediately and drop
> the local copy once merged.

That is also workable of course.  Anyway, it was just a suggestion.

Thanks,

Lukas
___
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx

Re: [Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

2016-12-16 Thread Chris Wilson

On Fri, Dec 16, 2016 at 10:31:17AM +0100, Lukas Wunner wrote:
> On Fri, Dec 16, 2016 at 07:46:46AM +, Chris Wilson wrote:
> > 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 
> > ---
> >  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
> 
> Hm, why not put this in lib/ ?  Don't see anything DRM-specific here
> at first glance and this might be useful to others.  Or others might
> come up with improvements and they'll be more likely to discover it
> outside of DRM.

Because that is a 3+ month cycle before I can then apply the testcases,
and without the testscases do you want the bugfixes?

If I put in in drm/lib then lift it, I can use it immediately and drop
the local copy once merged.
-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

Re: [Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

2016-12-16 Thread Lukas Wunner

On Fri, Dec 16, 2016 at 07:46:46AM +, Chris Wilson wrote:
> 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 
> ---
>  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

Hm, why not put this in lib/ ?  Don't see anything DRM-specific here
at first glance and this might be useful to others.  Or others might
come up with improvements and they'll be more likely to discover it
outside of DRM.

Same for the random permutations patch.

Thanks,

Lukas

> 
> 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 ..839563d9b787
> --- /dev/null
> +++ b/drivers/gpu/drm/lib/drm_prime_numbers.c
> @@ -0,0 +1,175 @@
> +#include 
> +#include 
> +#include 
> +
> +#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();
> + p = rcu_dereference_protected(primes, lockdep_is_held());
> + 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();
> + 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) {
> +

[Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

2016-12-15 Thread 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 
---
 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 ..839563d9b787
--- /dev/null
+++ b/drivers/gpu/drm/lib/drm_prime_numbers.c
@@ -0,0 +1,175 @@
+#include 
+#include 
+#include 
+
+#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();
+   p = rcu_dereference_protected(primes, lockdep_is_held());
+   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();
+   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:
+

Re: [Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

Re: [Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

Re: [Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

Re: [Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

[Intel-gfx] [PATCH v2 08/40] drm: Add a simple prime number generator

5 matches

Site Navigation

Mail list logo

Footer information