[dpdk-dev] [RFC v2 1/2] eal: replace libc-based random number generation with LFSR

[Neil Horman]

On Fri, Apr 19, 2019 at 11:21:37PM +0200, Mattias Rönnblom wrote:
> This commit replaces rte_rand()'s use of lrand48() with a DPDK-native
> combined Linear Feedback Shift Register (LFSR) (also known as
> Tausworthe) pseudo-number generator, with five sequences.
> 
> This generator is faster and produces better quality random numbers
> than libc's lrand48() implementation. This implementation, as opposed
> to lrand48(), is multi-thread safe in regards to concurrent rte_rand()
> calls from different lcore threads. It is not cryptographically
> secure - just like lrand48().
> 
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom at ericsson.com>
> ---
>  lib/librte_eal/common/include/rte_random.h |  29 ++---
>  lib/librte_eal/common/meson.build          |   1 +
>  lib/librte_eal/common/rte_random.c         | 137 +++++++++++++++++++++
>  lib/librte_eal/freebsd/eal/Makefile        |   1 +
>  lib/librte_eal/freebsd/eal/eal.c           |   2 -
>  lib/librte_eal/linux/eal/Makefile          |   1 +
>  lib/librte_eal/linux/eal/eal.c             |   2 -
>  lib/librte_eal/rte_eal_version.map         |   2 +
>  8 files changed, 153 insertions(+), 22 deletions(-)
>  create mode 100644 lib/librte_eal/common/rte_random.c
> 
> diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
> index b2ca1c209..66dfe8ae7 100644
> --- a/lib/librte_eal/common/include/rte_random.h
> +++ b/lib/librte_eal/common/include/rte_random.h
> @@ -16,7 +16,6 @@ extern "C" {
>  #endif
>  
>  #include <stdint.h>
> -#include <stdlib.h>
>  
>  /**
>   * Seed the pseudo-random generator.
> @@ -25,34 +24,28 @@ extern "C" {
>   * value. It may need to be re-seeded by the user with a real random
>   * value.
>   *
> + * This function is not multi-thread safe in regards to other
> + * rte_srand() calls, nor is it in relation to concurrent rte_rand()
> + * calls.
> + *
>   * @param seedval
>   *   The value of the seed.
>   */
> -static inline void
> -rte_srand(uint64_t seedval)
> -{
> -	srand48((long)seedval);
> -}
> +void
> +rte_srand(uint64_t seedval);
>  
>  /**
>   * Get a pseudo-random value.
>   *
> - * This function generates pseudo-random numbers using the linear
> - * congruential algorithm and 48-bit integer arithmetic, called twice
> - * to generate a 64-bit value.
> + * The generator is not cryptographically secure.
> + *
> + * If called from lcore threads, this function is thread-safe.
>   *
>   * @return
>   *   A pseudo-random value between 0 and (1<<64)-1.
>   */
> -static inline uint64_t
> -rte_rand(void)
> -{
> -	uint64_t val;
> -	val = (uint64_t)lrand48();
> -	val <<= 32;
> -	val += (uint64_t)lrand48();
> -	return val;
> -}
> +uint64_t
> +rte_rand(void);
>  
>  #ifdef __cplusplus
>  }
> diff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build
> index 0670e4102..bafd23207 100644
> --- a/lib/librte_eal/common/meson.build
> +++ b/lib/librte_eal/common/meson.build
> @@ -35,6 +35,7 @@ common_sources = files(
>  	'rte_keepalive.c',
>  	'rte_malloc.c',
>  	'rte_option.c',
> +	'rte_random.c',
>  	'rte_reciprocal.c',
>  	'rte_service.c'
>  )
> diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> new file mode 100644
> index 000000000..288e7b8c5
> --- /dev/null
> +++ b/lib/librte_eal/common/rte_random.c
> @@ -0,0 +1,137 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2019 Ericsson AB
> + */
> +
> +#include <stdlib.h>
> +
> +#include <rte_cycles.h>
> +#include <rte_eal.h>
> +#include <rte_lcore.h>
> +#include <rte_random.h>
> +
> +struct rte_rand_state {
> +	uint64_t z1;
> +	uint64_t z2;
> +	uint64_t z3;
> +	uint64_t z4;
> +	uint64_t z5;
> +} __rte_cache_aligned;
> +
> +static struct rte_rand_state rand_states[RTE_MAX_LCORE];
> +
> +static uint32_t
> +__rte_rand_lcg32(uint32_t *seed)
> +{
> +	*seed = 1103515245U * *seed + 12345U;
> +
> +	return *seed;
> +}
> +
> +static uint64_t
> +__rte_rand_lcg64(uint32_t *seed)
> +{
> +	uint64_t low;
> +	uint64_t high;
> +
> +	/* A 64-bit LCG would have been much cleaner, but well-known
> +	 * good multiplier/increments seem hard to come by.
> +	 */
> +
> +	low = __rte_rand_lcg32(seed);
> +	high = __rte_rand_lcg32(seed);
> +
> +	return low | (high << 32);
> +}
> +
> +static uint64_t
> +__rte_rand_lfsr258_gen_seed(uint32_t *seed, uint64_t min_value)
> +{
> +	uint64_t res;
> +
> +	res = __rte_rand_lcg64(seed);
> +
> +	if (res < min_value)
> +		res += min_value;
> +
> +	return res;
> +}
> +
> +static void
> +__rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)
> +{
> +	uint32_t lcg_seed;
> +
> +	lcg_seed = (uint32_t)(seed ^ (seed >> 32));
> +
> +	state->z1 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 2UL);
> +	state->z2 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 512UL);
> +	state->z3 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 4096UL);
> +	state->z4 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 131072UL);
> +	state->z5 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 8388608UL);
> +}
> +
> +void __rte_experimental
> +rte_srand(uint64_t seed)
> +{
> +	unsigned int lcore_id;
> +
> +	/* add lcore_id to seed to avoid having the same sequence */
> +	for (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id++)
> +		__rte_srand_lfsr258(seed + lcore_id, &rand_states[lcore_id]);
> +}
> +
> +static __rte_always_inline uint64_t
> +__rte_rand_lfsr258_comp(uint64_t z, uint64_t a, uint64_t b, uint64_t c,
> +			uint64_t d)
> +{
> +	return ((z & c) << d) ^ (((z << a) ^ z) >> b);
> +}
> +
> +/* Based on L’Ecuyer, P.: Tables of maximally equidistributed combined
> + * LFSR generators.
> + */
> +
> +static __rte_always_inline uint64_t
> +__rte_rand_lfsr258(struct rte_rand_state *state)
> +{
> +	state->z1 = __rte_rand_lfsr258_comp(state->z1, 1UL, 53UL,
> +					    18446744073709551614UL, 10UL);
> +	state->z2 = __rte_rand_lfsr258_comp(state->z2, 24UL, 50UL,
> +					    18446744073709551104UL, 5UL);
> +	state->z3 = __rte_rand_lfsr258_comp(state->z3, 3UL, 23UL,
> +					    18446744073709547520UL, 29UL);
> +	state->z4 = __rte_rand_lfsr258_comp(state->z4, 5UL, 24UL,
> +					    18446744073709420544UL, 23UL);
> +	state->z5 = __rte_rand_lfsr258_comp(state->z5, 3UL, 33UL,
> +					    18446744073701163008UL, 8UL);
> +
> +	return state->z1 ^ state->z2 ^ state->z3 ^ state->z4 ^ state->z5;
> +}
> +
> +static __rte_always_inline
> +struct rte_rand_state *__rte_rand_get_state(void)
> +{
> +	unsigned int lcore_id;
> +
> +	lcore_id = rte_lcore_id();
> +
> +	if (unlikely(lcore_id == LCORE_ID_ANY))
> +		lcore_id = rte_get_master_lcore();
> +
> +	return &rand_states[lcore_id];
> +}
> +
> +uint64_t __rte_experimental
> +rte_rand(void)
Do you really want to mark this as experimental?  I know it will trigger the
symbol checker with a warning if you don't, but this function already existed
previously and was accepted as part of the ABI.  Given that the prototype hasn't
changed, I think you just need to accept it as a non-experimental function


> +{
> +	struct rte_rand_state *state;
> +
> +	state = __rte_rand_get_state();
> +
> +	return __rte_rand_lfsr258(state);
> +}
> +
> +RTE_INIT(rte_rand_init)
> +{
> +	rte_srand(rte_get_timer_cycles());
> +}
> diff --git a/lib/librte_eal/freebsd/eal/Makefile b/lib/librte_eal/freebsd/eal/Makefile
> index 19854ee2c..ca616c480 100644
> --- a/lib/librte_eal/freebsd/eal/Makefile
> +++ b/lib/librte_eal/freebsd/eal/Makefile
> @@ -69,6 +69,7 @@ SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += malloc_mp.c
>  SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_keepalive.c
>  SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_option.c
>  SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_service.c
> +SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_random.c
>  SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_reciprocal.c
>  
>  # from arch dir
> diff --git a/lib/librte_eal/freebsd/eal/eal.c b/lib/librte_eal/freebsd/eal/eal.c
> index c6ac9028f..5d43310b3 100644
> --- a/lib/librte_eal/freebsd/eal/eal.c
> +++ b/lib/librte_eal/freebsd/eal/eal.c
> @@ -727,8 +727,6 @@ rte_eal_init(int argc, char **argv)
>  #endif
>  	}
>  
> -	rte_srand(rte_rdtsc());
> -
>  	/* in secondary processes, memory init may allocate additional fbarrays
>  	 * not present in primary processes, so to avoid any potential issues,
>  	 * initialize memzones first.
> diff --git a/lib/librte_eal/linux/eal/Makefile b/lib/librte_eal/linux/eal/Makefile
> index 6e5261152..729795a10 100644
> --- a/lib/librte_eal/linux/eal/Makefile
> +++ b/lib/librte_eal/linux/eal/Makefile
> @@ -77,6 +77,7 @@ SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += malloc_mp.c
>  SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_keepalive.c
>  SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_option.c
>  SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_service.c
> +SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_random.c
>  SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_reciprocal.c
>  
>  # from arch dir
> diff --git a/lib/librte_eal/linux/eal/eal.c b/lib/librte_eal/linux/eal/eal.c
> index f7ae62d7b..c2bdf0a67 100644
> --- a/lib/librte_eal/linux/eal/eal.c
> +++ b/lib/librte_eal/linux/eal/eal.c
> @@ -1083,8 +1083,6 @@ rte_eal_init(int argc, char **argv)
>  #endif
>  	}
>  
> -	rte_srand(rte_rdtsc());
> -
>  	if (rte_eal_log_init(logid, internal_config.syslog_facility) < 0) {
>  		rte_eal_init_alert("Cannot init logging.");
>  		rte_errno = ENOMEM;
> diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
> index d6e375135..0d60668fa 100644
> --- a/lib/librte_eal/rte_eal_version.map
> +++ b/lib/librte_eal/rte_eal_version.map
> @@ -366,10 +366,12 @@ EXPERIMENTAL {
>  	rte_mp_request_async;
>  	rte_mp_sendmsg;
>  	rte_option_register;
> +	rte_rand;
>  	rte_realloc_socket;
>  	rte_service_lcore_attr_get;
>  	rte_service_lcore_attr_reset_all;
>  	rte_service_may_be_active;
>  	rte_socket_count;
>  	rte_socket_id_by_idx;
> +	rte_srand;
>  };