Re: [kvm-unit-tests PATCH v3 11/27] lib: Add random number generator

[Claudio Imbrenda <imbrenda@linux.ibm.com>]

On Tue, 22 Nov 2022 18:11:36 +0200
Maxim Levitsky <mlevitsk@redhat.com> wrote:

> Add a simple pseudo random number generator which can be used
> in the tests to add randomeness in a controlled manner.

ahh, yes I have wanted something like this in the library for quite some
time! thanks!

I have some comments regarding the interfaces (see below), and also a
request, if you could split the x86 part in a different patch, so we
can have a "pure" lib patch, and then you can have an x86-only patch
that uses the new interface

> 
> For x86 add a wrapper which initializes the PRNG with RDRAND,
> unless RANDOM_SEED env variable is set, in which case it is used
> instead.
> 
> Signed-off-by: Maxim Levitsky <mlevitsk@redhat.com>
> ---
>  Makefile              |  3 ++-
>  README.md             |  1 +
>  lib/prng.c            | 41 +++++++++++++++++++++++++++++++++++++++++
>  lib/prng.h            | 23 +++++++++++++++++++++++
>  lib/x86/random.c      | 33 +++++++++++++++++++++++++++++++++
>  lib/x86/random.h      | 17 +++++++++++++++++
>  scripts/arch-run.bash |  2 +-
>  x86/Makefile.common   |  1 +
>  8 files changed, 119 insertions(+), 2 deletions(-)
>  create mode 100644 lib/prng.c
>  create mode 100644 lib/prng.h
>  create mode 100644 lib/x86/random.c
>  create mode 100644 lib/x86/random.h
> 
> diff --git a/Makefile b/Makefile
> index 6ed5deac..384b5acf 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -29,7 +29,8 @@ cflatobjs := \
>  	lib/string.o \
>  	lib/abort.o \
>  	lib/report.o \
> -	lib/stack.o
> +	lib/stack.o \
> +	lib/prng.o
>  
>  # libfdt paths
>  LIBFDT_objdir = lib/libfdt
> diff --git a/README.md b/README.md
> index 6e82dc22..5a677a03 100644
> --- a/README.md
> +++ b/README.md
> @@ -91,6 +91,7 @@ the framework.  The list of reserved environment variables is below
>      QEMU_ACCEL                   either kvm, hvf or tcg
>      QEMU_VERSION_STRING          string of the form `qemu -h | head -1`
>      KERNEL_VERSION_STRING        string of the form `uname -r`
> +    TEST_SEED                    integer to force a fixed seed for the prng
>  
>  Additionally these self-explanatory variables are reserved
>  
> diff --git a/lib/prng.c b/lib/prng.c
> new file mode 100644
> index 00000000..d9342eb3
> --- /dev/null
> +++ b/lib/prng.c
> @@ -0,0 +1,41 @@
> +
> +/*
> + * Random number generator that is usable from guest code. This is the
> + * Park-Miller LCG using standard constants.
> + */
> +
> +#include "libcflat.h"
> +#include "prng.h"
> +
> +struct random_state new_random_state(uint32_t seed)
> +{
> +	struct random_state s = {.seed = seed};
> +	return s;
> +}
> +
> +uint32_t random_u32(struct random_state *state)
> +{
> +	state->seed = (uint64_t)state->seed * 48271 % ((uint32_t)(1 << 31) - 1);

why not:

state->seed = state->seed * 48271ULL % (BIT_ULL(31) - 1);

I think it's more readable

> +	return state->seed;
> +}
> +
> +
> +uint32_t random_range(struct random_state *state, uint32_t min, uint32_t max)
> +{
> +	uint32_t val = random_u32(state);
> +
> +	return val % (max - min + 1) + min;

what happens if max == UINT_MAX and min = 0 ?

maybe:

if (max - min == UINT_MAX)
	return val;

> +}
> +
> +/*
> + * Returns true randomly in 'percent_true' cases (e.g if percent_true = 70.0,
> + * it will return true in 70.0% of cases)
> + */
> +bool random_decision(struct random_state *state, float percent_true)

I'm not a fan of floats in the lib...

> +{
> +	if (percent_true == 0)
> +		return 0;
> +	if (percent_true == 100)
> +		return 1;
> +	return random_range(state, 1, 10000) < (uint32_t)(percent_true * 100);

...especially when you are only using 2 decimal places anyway

can you rewrite it to take an unsigned int? 
e.g. if percent_true = 7123, it will return true in 71.23% of the cases

then you can rewrite the last line like this:

return random_range(state, 1, 10000) < percent_true;

> +}
> diff --git a/lib/prng.h b/lib/prng.h
> new file mode 100644
> index 00000000..61d3a48b
> --- /dev/null
> +++ b/lib/prng.h
> @@ -0,0 +1,23 @@
> +
> +#ifndef SRC_LIB_PRNG_H_
> +#define SRC_LIB_PRNG_H_
> +
> +struct random_state {
> +	uint32_t seed;
> +};
> +
> +struct random_state new_random_state(uint32_t seed);
> +uint32_t random_u32(struct random_state *state);
> +
> +/*
> + * return a random number from min to max (included)
> + */
> +uint32_t random_range(struct random_state *state, uint32_t min, uint32_t max);
> +
> +/*
> + * Returns true randomly in 'percent_true' cases (e.g if percent_true = 70.0,
> + * it will return true in 70.0% of cases)
> + */
> +bool random_decision(struct random_state *state, float percent_true);
> +
> +#endif /* SRC_LIB_PRNG_H_ */


and then put the rest below in a new patch

> diff --git a/lib/x86/random.c b/lib/x86/random.c
> new file mode 100644
> index 00000000..fcdd5fe8
> --- /dev/null
> +++ b/lib/x86/random.c
> @@ -0,0 +1,33 @@
> +
> +#include "libcflat.h"
> +#include "processor.h"
> +#include "prng.h"
> +#include "smp.h"
> +#include "asm/spinlock.h"
> +#include "random.h"
> +
> +static u32 test_seed;
> +static bool initialized;
> +
> +void init_prng(void)
> +{
> +	char *test_seed_str = getenv("TEST_SEED");
> +
> +	if (test_seed_str && strlen(test_seed_str))
> +		test_seed = atol(test_seed_str);
> +	else
> +#ifdef __x86_64__
> +		test_seed =  (u32)rdrand();
> +#else
> +		test_seed = (u32)(rdtsc() << 4);
> +#endif
> +	initialized = true;
> +
> +	printf("Test seed: %u\n", (unsigned int)test_seed);
> +}
> +
> +struct random_state get_prng(void)
> +{
> +	assert(initialized);
> +	return new_random_state(test_seed + this_cpu_read_smp_id());
> +}
> diff --git a/lib/x86/random.h b/lib/x86/random.h
> new file mode 100644
> index 00000000..795b450b
> --- /dev/null
> +++ b/lib/x86/random.h
> @@ -0,0 +1,17 @@
> +/*
> + * prng.h
> + *
> + *  Created on: Nov 9, 2022
> + *      Author: mlevitsk
> + */
> +
> +#ifndef SRC_LIB_X86_RANDOM_H_
> +#define SRC_LIB_X86_RANDOM_H_
> +
> +#include "libcflat.h"
> +#include "prng.h"
> +
> +void init_prng(void);
> +struct random_state get_prng(void);
> +
> +#endif /* SRC_LIB_X86_RANDOM_H_ */
> diff --git a/scripts/arch-run.bash b/scripts/arch-run.bash
> index 51e4b97b..238d19f8 100644
> --- a/scripts/arch-run.bash
> +++ b/scripts/arch-run.bash
> @@ -298,7 +298,7 @@ env_params ()
>  	KERNEL_EXTRAVERSION=${KERNEL_EXTRAVERSION%%[!0-9]*}
>  	! [[ $KERNEL_SUBLEVEL =~ ^[0-9]+$ ]] && unset $KERNEL_SUBLEVEL
>  	! [[ $KERNEL_EXTRAVERSION =~ ^[0-9]+$ ]] && unset $KERNEL_EXTRAVERSION
> -	env_add_params KERNEL_VERSION_STRING KERNEL_VERSION KERNEL_PATCHLEVEL KERNEL_SUBLEVEL KERNEL_EXTRAVERSION
> +	env_add_params KERNEL_VERSION_STRING KERNEL_VERSION KERNEL_PATCHLEVEL KERNEL_SUBLEVEL KERNEL_EXTRAVERSION TEST_SEED
>  }
>  
>  env_file ()
> diff --git a/x86/Makefile.common b/x86/Makefile.common
> index 698a48ab..fa0a50e6 100644
> --- a/x86/Makefile.common
> +++ b/x86/Makefile.common
> @@ -23,6 +23,7 @@ cflatobjs += lib/x86/stack.o
>  cflatobjs += lib/x86/fault_test.o
>  cflatobjs += lib/x86/delay.o
>  cflatobjs += lib/x86/pmu.o
> +cflatobjs += lib/x86/random.o
>  ifeq ($(CONFIG_EFI),y)
>  cflatobjs += lib/x86/amd_sev.o
>  cflatobjs += lib/efi.o