[dpdk-dev] [RFC v2 2/2] eal: introduce random generator function with upper bound

[Wiles, Keith]

> On Apr 19, 2019, at 5:21 PM, Mattias Rönnblom <mattias.ronnblom at ericsson.com> wrote:
> 
> Add a function rte_rand_max() which generates an uniformly distributed
> pseudo-random number less than a user-specified upper bound.
> 
> The commonly used pattern rte_rand() % SOME_VALUE, in addition to
> being slow, also creates biased results if SOME_VALUE is not a power
> of 2. This bias is very small for small SOME_VALUE, but increases
> linearly with larger SOME_VALUE.
> 
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom at ericsson.com>
> ---
> lib/librte_eal/common/include/rte_random.h | 16 ++++++++++++++++
> lib/librte_eal/common/rte_random.c         | 20 ++++++++++++++++++++
> lib/librte_eal/rte_eal_version.map         |  1 +
> 3 files changed, 37 insertions(+)
> 
> diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
> index 66dfe8ae7..053912168 100644
> --- a/lib/librte_eal/common/include/rte_random.h
> +++ b/lib/librte_eal/common/include/rte_random.h
> @@ -47,6 +47,22 @@ rte_srand(uint64_t seedval);
> uint64_t
> rte_rand(void);
> 
> +/**
> + * Generates a pseudo-random number less than upper_bound.
> + *
> + * This function returns an uniformly distributed (unbiased) random
> + * number lower than a user-specified maximum value.
> + *
> + * If called from lcore threads, this function is thread-safe.
> + *
> + * @param upper_bound
> + *   The upper bound of the generated number.
> + * @return
> + *   A pseudo-random value between 0 and (upper_bound-1).
> + */
> +uint64_t
> +rte_rand_max(uint64_t upper_bound);
> +
> #ifdef __cplusplus
> }
> #endif
> diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> index 288e7b8c5..bf9240470 100644
> --- a/lib/librte_eal/common/rte_random.c
> +++ b/lib/librte_eal/common/rte_random.c
> @@ -131,6 +131,26 @@ rte_rand(void)
> 	return __rte_rand_lfsr258(state);
> }
> 
> +uint64_t __rte_experimental
> +rte_rand_max(uint64_t upper_bound)
> +{
> +	uint8_t zeros;
> +	uint64_t mask = ~((uint64_t)0);
> +	uint64_t res;
> +
> +	if (upper_bound < 2)
> +		return 0;
> +
> +	zeros = __builtin_clzll(upper_bound);
> +	mask >>= zeros;
> +
> +	do {
> +		res = rte_rand() & mask;
> +	} while (unlikely(res >= upper_bound));

My concern here is the numbers of times this loop could be executed as the upper bound could be just over a power of 2 and it is a large number meaning the number of values above upper max and the power of 2 could be huge. Am I looking this loop correctly. If my thought process is correct it could take a long time to get a value less tha n upper max, correct?

If every thing aligns in a bad way it could be a large number of loops and cause all kinds of problems. What could be done here or is this a non-issue?
> +
> +	return res;
> +}
> +
> RTE_INIT(rte_rand_init)
> {
> 	rte_srand(rte_get_timer_cycles());
> diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
> index 0d60668fa..8f5b8c6a6 100644
> --- a/lib/librte_eal/rte_eal_version.map
> +++ b/lib/librte_eal/rte_eal_version.map
> @@ -367,6 +367,7 @@ EXPERIMENTAL {
> 	rte_mp_sendmsg;
> 	rte_option_register;
> 	rte_rand;
> +	rte_rand_max;
> 	rte_realloc_socket;
> 	rte_service_lcore_attr_get;
> 	rte_service_lcore_attr_reset_all;
> -- 
> 2.17.1
> 

Regards,
Keith