eal: introduce random generator with upper bound

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>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>

diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c
index 7717137..fe797eb 100644 (file)
--- 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 5928f22..ad0ac43 100644 (file)
--- 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, <rte_random.h> 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 66dfe8a..939e6aa 100644 (file)
--- 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 e53d96d..3d9b9b7 100644 (file)
--- 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 20c1a90..a53a29a 100644 (file)
--- 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;