[dpdk-dev] [PATCH 4/6] eal: introduce random generator function with upper bound

["Mattias Rönnblom" <mattias.ronnblom@ericsson.com>]

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 <mattias.ronnblom@ericsson.com>
---
 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 +
 3 files changed, 58 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index 66dfe8ae7..939e6aaa9 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 <stdint.h>
 
+#include <rte_compat.h>
+
 /**
  * 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 aafc2f7ad..0e8abbb1c 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -134,6 +134,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;
+}
+
 RTE_INIT(rte_rand_init)
 {
 	uint64_t seed;
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index e615d7cb9..82483aed2 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -382,6 +382,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.17.1