[PATCH 06/34] drm: Add a simple linear congruent generator PRNG
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 This doesn't seem very DRM-specific, is there a reason why we can't use the ansi_cprng already present in the kernel ? -- Regards, Laurent Pinchart
[PATCH 06/34] drm: Add a simple linear congruent generator PRNG
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 > > 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 -- Chris Wilson, Intel Open Source Technology Centre
[PATCH 06/34] drm: Add a simple linear congruent generator PRNG
Hey Chris On Tue, Dec 13, 2016 at 4:40 PM, Chris Wilson 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 >> wrote: >> > On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson > > 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
[PATCH 06/34] drm: Add a simple linear congruent generator PRNG
On Tue, Dec 13, 2016 at 4:16 PM, David Herrmann wrote: > On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson > 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:
[PATCH 06/34] drm: Add a simple linear congruent generator PRNG
Hey Chris
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
> ---
> 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 ..f203c47bb525
> --- /dev/null
> +++ b/drivers/gpu/drm/lib/drm_rand.c
> @@ -0,0 +1,51 @@
> +#include
> +#include
> +#include
> +
> +#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
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
> + }
> + }
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 ..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 at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/dri-devel
[PATCH 06/34] drm: Add a simple linear congruent generator PRNG
On Tue, Dec 13, 2016 at 04:18:35PM +0100, David Herrmann wrote: > On Tue, Dec 13, 2016 at 4:16 PM, David Herrmann > wrote: > > On Mon, Dec 12, 2016 at 12:53 PM, Chris Wilson > 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 -- Chris Wilson, Intel Open Source Technology Centre
[PATCH 06/34] drm: Add a simple linear congruent generator PRNG
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
> 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
> > ---
> > 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 ..f203c47bb525
> > --- /dev/null
> > +++ b/drivers/gpu/drm/lib/drm_rand.c
> > @@ -0,0 +1,51 @@
> > +#include
> > +#include
> > +#include
> > +
> > +#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
>
> 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
>
> > + }
> > + }
>
> 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 ..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
[PATCH 06/34] drm: Add a simple linear congruent generator PRNG
On ma, 2016-12-12 at 11:53 +, 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
> +++ b/drivers/gpu/drm/lib/drm_rand.c
> @@ -0,0 +1,51 @@
> +#include
> +#include
> +#include
> +
> +#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
--
Joonas Lahtinen
Open Source Technology Center
Intel Corporation
[PATCH 06/34] drm: Add a simple linear congruent generator PRNG
For testing, we want a reproducible PRNG, a plain linear congruent
generator is suitable for our very limited selftests.
Signed-off-by: Chris Wilson
---
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 ..f203c47bb525
--- /dev/null
+++ b/drivers/gpu/drm/lib/drm_rand.c
@@ -0,0 +1,51 @@
+#include
+#include
+#include
+
+#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 ..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__ */
--
2.11.0
