diff mbox

[06/34] drm: Add a simple linear congruent generator PRNG

Message ID 20161212115350.780-7-chris@chris-wilson.co.uk (mailing list archive)
State New, archived
Headers show

Commit Message

Chris Wilson Dec. 12, 2016, 11:53 a.m. UTC 
For testing, we want a reproducible PRNG, a plain linear congruent
generator is suitable for our very limited selftests.

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
---
 drivers/gpu/drm/Kconfig        |  5 +++++
 drivers/gpu/drm/Makefile       |  1 +
 drivers/gpu/drm/lib/drm_rand.c | 51 ++++++++++++++++++++++++++++++++++++++++++
 drivers/gpu/drm/lib/drm_rand.h |  9 ++++++++
 4 files changed, 66 insertions(+)
 create mode 100644 drivers/gpu/drm/lib/drm_rand.c
 create mode 100644 drivers/gpu/drm/lib/drm_rand.h

Comments

Joonas Lahtinen Dec. 13, 2016, 10:44 a.m. UTC | #1 
On ma, 2016-12-12 at 11:53 +0000, Chris Wilson wrote:
> For testing, we want a reproducible PRNG, a plain linear congruent
> generator is suitable for our very limited selftests.
> 
> Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

<SNIP>

> +++ b/drivers/gpu/drm/lib/drm_rand.c
> @@ -0,0 +1,51 @@
> +#include <linux/kernel.h>
> +#include <linux/slab.h>
> +#include <linux/types.h>
> +
> +#include "drm_rand.h"
> +
> +u32 drm_lcg_random(u32 *state)
> +{
> +	u32 s = *state;
> +
> +#define rol(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
> +	s = (s ^ rol(s, 5) ^ rol(s, 24)) + 0x37798849;
> +#undef rol
> +
> +	*state = s;
> +	return s;
> +}

Do state your source for checking purposes. Code is bound to be copied
and there's no reason to have it good.

> +EXPORT_SYMBOL(drm_lcg_random);
> +
> +int *drm_random_reorder(int *order, int count, u32 *state)
> +{
> +	int n;
> +
> +	for (n = count-1; n > 1; n--) {
> +		int r = drm_lcg_random(state) % (n + 1);
> +		if (r != n) {
> +			int tmp = order[n];
> +			order[n] = order[r];
> +			order[r] = tmp;
> +		}
> +	}
> +
> +	return order;
> +}

If you have two items... So definitely add big disclaimers of not being
random, or use some more proven algorithm :)

Regards, Joonas
David Herrmann Dec. 13, 2016, 3:16 p.m. UTC | #2 
Hey Chris

On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson <chris@chris-wilson.co.uk> wrote:
> For testing, we want a reproducible PRNG, a plain linear congruent
> generator is suitable for our very limited selftests.
>
> Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> ---
>  drivers/gpu/drm/Kconfig        |  5 +++++
>  drivers/gpu/drm/Makefile       |  1 +
>  drivers/gpu/drm/lib/drm_rand.c | 51 ++++++++++++++++++++++++++++++++++++++++++
>  drivers/gpu/drm/lib/drm_rand.h |  9 ++++++++
>  4 files changed, 66 insertions(+)
>  create mode 100644 drivers/gpu/drm/lib/drm_rand.c
>  create mode 100644 drivers/gpu/drm/lib/drm_rand.h
>
> diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig
> index fd341ab69c46..04d1d0a32c5c 100644
> --- a/drivers/gpu/drm/Kconfig
> +++ b/drivers/gpu/drm/Kconfig
> @@ -48,10 +48,15 @@ config DRM_DEBUG_MM
>
>           If in doubt, say "N".
>
> +config DRM_LIB_RAND
> +       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
>         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 c8aed3688b20..363eb1a23151 100644
> --- a/drivers/gpu/drm/Makefile
> +++ b/drivers/gpu/drm/Makefile
> @@ -18,6 +18,7 @@ drm-y       :=        drm_auth.o drm_bufs.o drm_cache.o \
>                 drm_plane.o drm_color_mgmt.o drm_print.o \
>                 drm_dumb_buffers.o drm_mode_config.o
>
> +drm-$(CONFIG_DRM_LIB_RAND) += lib/drm_rand.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_rand.c b/drivers/gpu/drm/lib/drm_rand.c
> new file mode 100644
> index 000000000000..f203c47bb525
> --- /dev/null
> +++ b/drivers/gpu/drm/lib/drm_rand.c
> @@ -0,0 +1,51 @@
> +#include <linux/kernel.h>
> +#include <linux/slab.h>
> +#include <linux/types.h>
> +
> +#include "drm_rand.h"
> +
> +u32 drm_lcg_random(u32 *state)
> +{
> +       u32 s = *state;
> +
> +#define rol(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
> +       s = (s ^ rol(s, 5) ^ rol(s, 24)) + 0x37798849;
> +#undef rol

#include <linux/bitops.h>

static inline __u32 rol32(__u32 word, unsigned int shift);

Allows you to get rid of "rol()" and the temporary "u32 s;".

> +
> +       *state = s;
> +       return s;
> +}
> +EXPORT_SYMBOL(drm_lcg_random);
> +
> +int *drm_random_reorder(int *order, int count, u32 *state)
> +{
> +       int n;
> +
> +       for (n = count-1; n > 1; n--) {
> +               int r = drm_lcg_random(state) % (n + 1);
> +               if (r != n) {

Why not drop that condition? No harm in doing the self-swap, is there?
Makes the code shorter.

> +                       int tmp = order[n];
> +                       order[n] = order[r];
> +                       order[r] = tmp;

swap() in <linux/kernel.h>

> +               }
> +       }

Is there a specific reason to do it that way? How about:

for (i = 0; i < count; ++i)
        swap(order[i], order[drm_lcg_random(state) % count]);

Much simpler and I cannot see why it wouldn't work.

> +
> +       return order;

You sure that return value serves any purpose? Is that convenience so
you can use the function in a combined statement?

> +}
> +EXPORT_SYMBOL(drm_random_reorder);
> +
> +int *drm_random_order(int count, u32 *state)
> +{
> +       int *order;
> +       int n;
> +
> +       order = kmalloc_array(count, sizeof(*order), GFP_TEMPORARY);
> +       if (!order)
> +               return order;
> +
> +       for (n = 0; n < count; n++)
> +               order[n] = n;
> +
> +       return drm_random_reorder(order, count, state);

Why "signed int"? We very often use "size_t" to count things. By
making the order signed you just keep running into "comparing signed
vs unsigned" warnings, don't you?

> +}
> +EXPORT_SYMBOL(drm_random_order);
> diff --git a/drivers/gpu/drm/lib/drm_rand.h b/drivers/gpu/drm/lib/drm_rand.h
> new file mode 100644
> index 000000000000..a3f22d115aac
> --- /dev/null
> +++ b/drivers/gpu/drm/lib/drm_rand.h
> @@ -0,0 +1,9 @@
> +#ifndef __DRM_RAND_H__
> +#define __DRM_RAND_H
> +
> +u32 drm_lcg_random(u32 *state);
> +
> +int *drm_random_reorder(int *order, int count, u32 *state);
> +int *drm_random_order(int count, u32 *state);
> +
> +#endif /* __DRM_RAND_H__ */

"random.h". Why the abbreviation?

Looks good to me. Only nitpicks, so feel free to ignore.

Thanks
David

> --
> 2.11.0
>
> _______________________________________________
> dri-devel mailing list
> dri-devel@lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/dri-devel
David Herrmann Dec. 13, 2016, 3:18 p.m. UTC | #3 
On Tue, Dec 13, 2016 at 4:16 PM, David Herrmann <dh.herrmann@gmail.com> wrote:
> On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson <chris@chris-wilson.co.uk> wrote:
> for (i = 0; i < count; ++i)
>         swap(order[i], order[drm_lcg_random(state) % count]);
>
> Much simpler and I cannot see why it wouldn't work.

Hint: swap() does multiple evaluations. So this needs to be:
Chris Wilson Dec. 13, 2016, 3:26 p.m. UTC | #4 
On Tue, Dec 13, 2016 at 04:16:41PM +0100, David Herrmann wrote:
> Hey Chris
> 
> On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson <chris@chris-wilson.co.uk> wrote:
> > For testing, we want a reproducible PRNG, a plain linear congruent
> > generator is suitable for our very limited selftests.
> >
> > Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> > ---
> >  drivers/gpu/drm/Kconfig        |  5 +++++
> >  drivers/gpu/drm/Makefile       |  1 +
> >  drivers/gpu/drm/lib/drm_rand.c | 51 ++++++++++++++++++++++++++++++++++++++++++
> >  drivers/gpu/drm/lib/drm_rand.h |  9 ++++++++
> >  4 files changed, 66 insertions(+)
> >  create mode 100644 drivers/gpu/drm/lib/drm_rand.c
> >  create mode 100644 drivers/gpu/drm/lib/drm_rand.h
> >
> > diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig
> > index fd341ab69c46..04d1d0a32c5c 100644
> > --- a/drivers/gpu/drm/Kconfig
> > +++ b/drivers/gpu/drm/Kconfig
> > @@ -48,10 +48,15 @@ config DRM_DEBUG_MM
> >
> >           If in doubt, say "N".
> >
> > +config DRM_LIB_RAND
> > +       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
> >         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 c8aed3688b20..363eb1a23151 100644
> > --- a/drivers/gpu/drm/Makefile
> > +++ b/drivers/gpu/drm/Makefile
> > @@ -18,6 +18,7 @@ drm-y       :=        drm_auth.o drm_bufs.o drm_cache.o \
> >                 drm_plane.o drm_color_mgmt.o drm_print.o \
> >                 drm_dumb_buffers.o drm_mode_config.o
> >
> > +drm-$(CONFIG_DRM_LIB_RAND) += lib/drm_rand.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_rand.c b/drivers/gpu/drm/lib/drm_rand.c
> > new file mode 100644
> > index 000000000000..f203c47bb525
> > --- /dev/null
> > +++ b/drivers/gpu/drm/lib/drm_rand.c
> > @@ -0,0 +1,51 @@
> > +#include <linux/kernel.h>
> > +#include <linux/slab.h>
> > +#include <linux/types.h>
> > +
> > +#include "drm_rand.h"
> > +
> > +u32 drm_lcg_random(u32 *state)
> > +{
> > +       u32 s = *state;
> > +
> > +#define rol(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
> > +       s = (s ^ rol(s, 5) ^ rol(s, 24)) + 0x37798849;
> > +#undef rol
> 
> #include <linux/bitops.h>
> 
> static inline __u32 rol32(__u32 word, unsigned int shift);
> 
> Allows you to get rid of "rol()" and the temporary "u32 s;".

Ta.

> 
> > +
> > +       *state = s;
> > +       return s;
> > +}
> > +EXPORT_SYMBOL(drm_lcg_random);
> > +
> > +int *drm_random_reorder(int *order, int count, u32 *state)
> > +{
> > +       int n;
> > +
> > +       for (n = count-1; n > 1; n--) {
> > +               int r = drm_lcg_random(state) % (n + 1);
> > +               if (r != n) {
> 
> Why not drop that condition? No harm in doing the self-swap, is there?
> Makes the code shorter.

It makes more sense when it was calling a function to handle the swap.

> 
> > +                       int tmp = order[n];
> > +                       order[n] = order[r];
> > +                       order[r] = tmp;
> 
> swap() in <linux/kernel.h>
> 
> > +               }
> > +       }
> 
> Is there a specific reason to do it that way? How about:
> 
> for (i = 0; i < count; ++i)
>         swap(order[i], order[drm_lcg_random(state) % count]);
> 
> Much simpler and I cannot see why it wouldn't work.

Ta.
> 
> > +
> > +       return order;
> 
> You sure that return value serves any purpose? Is that convenience so
> you can use the function in a combined statement?
> 

Just convenience from splitting the function up.

> > +}
> > +EXPORT_SYMBOL(drm_random_reorder);
> > +
> > +int *drm_random_order(int count, u32 *state)
> > +{
> > +       int *order;
> > +       int n;
> > +
> > +       order = kmalloc_array(count, sizeof(*order), GFP_TEMPORARY);
> > +       if (!order)
> > +               return order;
> > +
> > +       for (n = 0; n < count; n++)
> > +               order[n] = n;
> > +
> > +       return drm_random_reorder(order, count, state);
> 
> Why "signed int"? We very often use "size_t" to count things. By
> making the order signed you just keep running into "comparing signed
> vs unsigned" warnings, don't you?

Because I only needed ints. :-p

> 
> > +}
> > +EXPORT_SYMBOL(drm_random_order);
> > diff --git a/drivers/gpu/drm/lib/drm_rand.h b/drivers/gpu/drm/lib/drm_rand.h
> > new file mode 100644
> > index 000000000000..a3f22d115aac
> > --- /dev/null
> > +++ b/drivers/gpu/drm/lib/drm_rand.h
> > @@ -0,0 +1,9 @@
> > +#ifndef __DRM_RAND_H__
> > +#define __DRM_RAND_H
> > +
> > +u32 drm_lcg_random(u32 *state);
> > +
> > +int *drm_random_reorder(int *order, int count, u32 *state);
> > +int *drm_random_order(int count, u32 *state);
> > +
> > +#endif /* __DRM_RAND_H__ */
> 
> "random.h". Why the abbreviation?

Before the drm_ prefix I had to avoid a clash and I have a history with
calling this rand.h for no good reason.

> Looks good to me. Only nitpicks, so feel free to ignore.

(Apart from size_t because I still have the burn marks from DRM using
size_t where I need u64 on 32bit kernels. However, that looks correct
for this application. ;)
-Chris
Chris Wilson Dec. 13, 2016, 3:40 p.m. UTC | #5 
On Tue, Dec 13, 2016 at 04:18:35PM +0100, David Herrmann wrote:
> On Tue, Dec 13, 2016 at 4:16 PM, David Herrmann <dh.herrmann@gmail.com> wrote:
> > On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson <chris@chris-wilson.co.uk> wrote:
> > for (i = 0; i < count; ++i)
> >         swap(order[i], order[drm_lcg_random(state) % count]);
> >
> > Much simpler and I cannot see why it wouldn't work.
> 
> Hint: swap() does multiple evaluations. So this needs to be:

Hmm, and on switching to size_t count may be larger than u32...
-Chris
David Herrmann Dec. 13, 2016, 4:21 p.m. UTC | #6 
Hey Chris

On Tue, Dec 13, 2016 at 4:40 PM, Chris Wilson <chris@chris-wilson.co.uk> wrote:
> On Tue, Dec 13, 2016 at 04:18:35PM +0100, David Herrmann wrote:
>> On Tue, Dec 13, 2016 at 4:16 PM, David Herrmann <dh.herrmann@gmail.com> wrote:
>> > On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson <chris@chris-wilson.co.uk> wrote:
>> > for (i = 0; i < count; ++i)
>> >         swap(order[i], order[drm_lcg_random(state) % count]);
>> >
>> > Much simpler and I cannot see why it wouldn't work.
>>
>> Hint: swap() does multiple evaluations. So this needs to be:
>
> Hmm, and on switching to size_t count may be larger than u32...

I didn't mean to suggest 'size_t'. All I cared about was 'unsigned'.
So feel free to use 'u32', 'unsigned int', 'size_t', etc.

Thanks
David
Laurent Pinchart Dec. 13, 2016, 7:39 p.m. UTC | #7 
Hello,

On Tuesday 13 Dec 2016 16:16:41 David Herrmann wrote:
> On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson wrote:
> > For testing, we want a reproducible PRNG, a plain linear congruent
> > generator is suitable for our very limited selftests.
> > 
> > Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>

This doesn't seem very DRM-specific, is there a reason why we can't use the 
ansi_cprng already present in the kernel ?
Chris Wilson Dec. 13, 2016, 8:50 p.m. UTC | #8 
On Tue, Dec 13, 2016 at 09:39:06PM +0200, Laurent Pinchart wrote:
> Hello,
> 
> On Tuesday 13 Dec 2016 16:16:41 David Herrmann wrote:
> > On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson wrote:
> > > For testing, we want a reproducible PRNG, a plain linear congruent
> > > generator is suitable for our very limited selftests.
> > > 
> > > Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
> 
> This doesn't seem very DRM-specific, is there a reason why we can't use the 
> ansi_cprng already present in the kernel ?

That would be a nightmare to drag in a crypto dependency, for what
should be a 5 cycle function. However, I will replace the Hars-Petruska
lcg for prandom (from lib/random32.c). That meets the requirement of
being a seeded PRNG.
-Chris
diff mbox

Patch

diff --git a/drivers/gpu/drm/Kconfig b/drivers/gpu/drm/Kconfig
index fd341ab69c46..04d1d0a32c5c 100644
--- a/drivers/gpu/drm/Kconfig
+++ b/drivers/gpu/drm/Kconfig
@@ -48,10 +48,15 @@  config DRM_DEBUG_MM
 
 	  If in doubt, say "N".
 
+config DRM_LIB_RAND
+	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
 	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 c8aed3688b20..363eb1a23151 100644
--- a/drivers/gpu/drm/Makefile
+++ b/drivers/gpu/drm/Makefile
@@ -18,6 +18,7 @@  drm-y       :=	drm_auth.o drm_bufs.o drm_cache.o \
 		drm_plane.o drm_color_mgmt.o drm_print.o \
 		drm_dumb_buffers.o drm_mode_config.o
 
+drm-$(CONFIG_DRM_LIB_RAND) += lib/drm_rand.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_rand.c b/drivers/gpu/drm/lib/drm_rand.c
new file mode 100644
index 000000000000..f203c47bb525
--- /dev/null
+++ b/drivers/gpu/drm/lib/drm_rand.c
@@ -0,0 +1,51 @@ 
+#include <linux/kernel.h>
+#include <linux/slab.h>
+#include <linux/types.h>
+
+#include "drm_rand.h"
+
+u32 drm_lcg_random(u32 *state)
+{
+	u32 s = *state;
+
+#define rol(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
+	s = (s ^ rol(s, 5) ^ rol(s, 24)) + 0x37798849;
+#undef rol
+
+	*state = s;
+	return s;
+}
+EXPORT_SYMBOL(drm_lcg_random);
+
+int *drm_random_reorder(int *order, int count, u32 *state)
+{
+	int n;
+
+	for (n = count-1; n > 1; n--) {
+		int r = drm_lcg_random(state) % (n + 1);
+		if (r != n) {
+			int tmp = order[n];
+			order[n] = order[r];
+			order[r] = tmp;
+		}
+	}
+
+	return order;
+}
+EXPORT_SYMBOL(drm_random_reorder);
+
+int *drm_random_order(int count, u32 *state)
+{
+	int *order;
+	int n;
+
+	order = kmalloc_array(count, sizeof(*order), GFP_TEMPORARY);
+	if (!order)
+		return order;
+
+	for (n = 0; n < count; n++)
+		order[n] = n;
+
+	return drm_random_reorder(order, count, state);
+}
+EXPORT_SYMBOL(drm_random_order);
diff --git a/drivers/gpu/drm/lib/drm_rand.h b/drivers/gpu/drm/lib/drm_rand.h
new file mode 100644
index 000000000000..a3f22d115aac
--- /dev/null
+++ b/drivers/gpu/drm/lib/drm_rand.h
@@ -0,0 +1,9 @@ 
+#ifndef __DRM_RAND_H__
+#define __DRM_RAND_H
+
+u32 drm_lcg_random(u32 *state);
+
+int *drm_random_reorder(int *order, int count, u32 *state);
+int *drm_random_order(int count, u32 *state);
+
+#endif /* __DRM_RAND_H__ */