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

[Lukas Wunner <lukas@wunner.de>]

On Fri, Dec 16, 2016 at 07:46:46AM +0000, 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 <chris@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

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 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
> 
> _______________________________________________
> dri-devel mailing list
> dri-devel@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/dri-devel
_______________________________________________
Intel-gfx mailing list
Intel-gfx@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/intel-gfx