From 5f4ed3f058493552658e914815f58e784755a1b3 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Mattias=20R=C3=B6nnblom?= Date: Fri, 28 Jun 2019 11:01:23 +0200 Subject: [PATCH] eal: introduce random generator with upper bound MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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 creates biased results (as in some values in the range are more frequently occurring than others) if SOME_VALUE is not a power of 2. Signed-off-by: Mattias Rönnblom Acked-by: Bruce Richardson --- app/test/test_rand_perf.c | 19 ++++++++++- doc/guides/rel_notes/release_19_08.rst | 4 +++ lib/librte_eal/common/include/rte_random.h | 18 ++++++++++ lib/librte_eal/common/rte_random.c | 39 ++++++++++++++++++++++ lib/librte_eal/rte_eal_version.map | 1 + 5 files changed, 80 insertions(+), 1 deletion(-) diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c index 7717137578..fe797ebfa1 100644 --- a/app/test/test_rand_perf.c +++ b/app/test/test_rand_perf.c @@ -15,8 +15,13 @@ static volatile uint64_t vsum; #define ITERATIONS (100000000) +#define BEST_CASE_BOUND (1<<16) +#define WORST_CASE_BOUND (BEST_CASE_BOUND + 1) + enum rand_type { - rand_type_64 + rand_type_64, + rand_type_bounded_best_case, + rand_type_bounded_worst_case }; static const char * @@ -25,6 +30,10 @@ rand_type_desc(enum rand_type rand_type) switch (rand_type) { case rand_type_64: return "Full 64-bit [rte_rand()]"; + case rand_type_bounded_best_case: + return "Bounded average best-case [rte_rand_max()]"; + case rand_type_bounded_worst_case: + return "Bounded average worst-case [rte_rand_max()]"; default: return NULL; } @@ -46,6 +55,12 @@ test_rand_perf_type(enum rand_type rand_type) case rand_type_64: sum += rte_rand(); break; + case rand_type_bounded_best_case: + sum += rte_rand_max(BEST_CASE_BOUND); + break; + case rand_type_bounded_worst_case: + sum += rte_rand_max(WORST_CASE_BOUND); + break; } } @@ -68,6 +83,8 @@ test_rand_perf(void) printf("Pseudo-random number generation latencies:\n"); test_rand_perf_type(rand_type_64); + test_rand_perf_type(rand_type_bounded_best_case); + test_rand_perf_type(rand_type_bounded_worst_case); return 0; } diff --git a/doc/guides/rel_notes/release_19_08.rst b/doc/guides/rel_notes/release_19_08.rst index 5928f225b9..ad0ac4333f 100644 --- a/doc/guides/rel_notes/release_19_08.rst +++ b/doc/guides/rel_notes/release_19_08.rst @@ -64,6 +64,10 @@ New Features higher-quality pseudo-random numbers (including full 64 bit support) and improved performance. + In addition, is extended with a new function + rte_rand_max() which supplies unbiased, bounded pseudo-random + numbers. + * **Updated the bnxt PMD.** Updated the bnxt PMD. The major enhancements include: diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h index 66dfe8ae75..939e6aaa91 100644 --- a/lib/librte_eal/common/include/rte_random.h +++ b/lib/librte_eal/common/include/rte_random.h @@ -17,6 +17,8 @@ extern "C" { #include +#include + /** * Seed the pseudo-random generator. * @@ -47,6 +49,22 @@ rte_srand(uint64_t seedval); uint64_t rte_rand(void); +/** + * Generates a pseudo-random number with an upper bound. + * + * This function returns an uniformly distributed (unbiased) random + * number less 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_experimental +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 e53d96d180..3d9b9b7d83 100644 --- a/lib/librte_eal/common/rte_random.c +++ b/lib/librte_eal/common/rte_random.c @@ -137,6 +137,45 @@ rte_rand(void) return __rte_rand_lfsr258(state); } +uint64_t __rte_experimental +rte_rand_max(uint64_t upper_bound) +{ + struct rte_rand_state *state; + uint8_t ones; + uint8_t leading_zeros; + uint64_t mask = ~((uint64_t)0); + uint64_t res; + + if (unlikely(upper_bound < 2)) + return 0; + + state = __rte_rand_get_state(); + + ones = __builtin_popcountll(upper_bound); + + /* Handle power-of-2 upper_bound as a special case, since it + * has no bias issues. + */ + if (unlikely(ones == 1)) + return __rte_rand_lfsr258(state) & (upper_bound - 1); + + /* The approach to avoiding bias is to create a mask that + * stretches beyond the request value range, and up to the + * next power-of-2. In case the masked generated random value + * is equal to or greater than the upper bound, just discard + * the value and generate a new one. + */ + + leading_zeros = __builtin_clzll(upper_bound); + mask >>= leading_zeros; + + do { + res = __rte_rand_lfsr258(state) & mask; + } while (unlikely(res >= upper_bound)); + + return res; +} + static uint64_t __rte_random_initial_seed(void) { diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map index 20c1a90180..a53a29a35d 100644 --- a/lib/librte_eal/rte_eal_version.map +++ b/lib/librte_eal/rte_eal_version.map @@ -384,6 +384,7 @@ EXPERIMENTAL { rte_mp_request_async; rte_mp_sendmsg; rte_option_register; + rte_rand_max; rte_realloc_socket; rte_service_lcore_attr_get; rte_service_lcore_attr_reset_all; -- 2.20.1