[dpdk-dev] [RFC 3/3] Introduce random generator functions with upper bound

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

Add two functions rte_rand32_max() and rte_rand_max(), which generate
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@ericsson.com>
---
 lib/librte_eal/common/include/rte_random.h | 32 +++++++++++++++++
 lib/librte_eal/common/rte_random.c         | 40 ++++++++++++++++++++++
 lib/librte_eal/rte_eal_version.map         |  2 ++
 3 files changed, 74 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index a96fc7f96..b560b0a0d 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -45,6 +45,22 @@ rte_srand(uint64_t seedval);
 uint32_t
 rte_rand32(void);
 
+/**
+ * Generates an 32-bit 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).
+ */
+uint32_t
+rte_rand32_max(uint32_t upper_bound);
+
 /**
  * Generates a 64-bit pseudo-random number.
  *
@@ -56,6 +72,22 @@ rte_rand32(void);
 uint64_t
 rte_rand(void);
 
+/**
+ * Generates an 64-bit 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 c6dac2fc7..67d07d3ff 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -93,6 +93,26 @@ rte_rand32(void)
 	return __rte_rand32(state);
 }
 
+uint32_t __rte_experimental
+rte_rand32_max(uint32_t upper_bound)
+{
+	uint32_t mask = ~((uint32_t)0);
+	uint8_t zeros;
+	uint32_t res;
+
+	if (upper_bound < 2)
+		return 0;
+
+	zeros = __builtin_clz(upper_bound);
+	mask >>= zeros;
+
+	do {
+		res = rte_rand32() & mask;
+	} while (unlikely(res >= upper_bound));
+
+	return res;
+}
+
 uint64_t __rte_experimental
 rte_rand(void)
 {
@@ -108,6 +128,26 @@ rte_rand(void)
 	return low | (high << 32);
 }
 
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound)
+{
+	uint64_t mask = ~((uint64_t)0);
+	uint8_t zeros;
+	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));
+
+	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 027a22fe5..abdacb217 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -367,7 +367,9 @@ EXPERIMENTAL {
 	rte_mp_sendmsg;
 	rte_option_register;
 	rte_rand32;
+	rte_rand32_max;
 	rte_rand;
+	rte_rand_max;
 	rte_realloc_socket;
 	rte_service_lcore_attr_get;
 	rte_service_lcore_attr_reset_all;
-- 
2.17.1