[PATCH 04/18] sched: fix data race in RED random number generation

[Stephen Hemminger <stephen@networkplumber.org>]

RED used a private LCG whose seed and cached value were globals shared
by all lcores without synchronisation. The QoS framework documents
running different ports on different threads, so this is a data race.
The values do not tear, but updates are lost and drop decisions become
correlated across queues.

Use rte_rand32() in the drop test instead. Its state is per lcore, so
nothing is shared and no cache is needed. PIE already does this with
rte_drand().

This removes rte_fast_rand(), rte_red_rand_seed and rte_red_rand_val,
which were only used by RED itself. Removing exported symbols breaks
ABI, so this cannot be backported.

There is no prior deprecation notice for these symbols. They were
never meant to be part of the API: rte_fast_rand() is the internal
generator of the dropper and the two variables are its state, all
exposed only because the drop test is inline in rte_red.h. Keeping
them for a release would mean keeping the data race, which is the
bug being fixed.

Fixes: de3cfa2c9823 ("sched: initial import")
Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
 doc/guides/rel_notes/release_26_11.rst | 12 +++++++++++-
 lib/sched/rte_red.c                    |  9 +--------
 lib/sched/rte_red.h                    | 26 ++------------------------
 3 files changed, 14 insertions(+), 33 deletions(-)

diff --git a/doc/guides/rel_notes/release_26_11.rst b/doc/guides/rel_notes/release_26_11.rst
index 1dc634d504..c1742b3c60 100644
--- a/doc/guides/rel_notes/release_26_11.rst
+++ b/doc/guides/rel_notes/release_26_11.rst
@@ -85,6 +85,12 @@ Removed Items
     ``rte_rib6_is_equal``
   * table: ``RTE_LPM_IPV6_ADDR_SIZE``
 
+* sched: Removed the private random number generator used by RED: the
+  inline function ``rte_fast_rand()`` in ``rte_red.h`` and its global
+  state ``rte_red_rand_seed`` and ``rte_red_rand_val``. Its state was
+  shared by all lcores without synchronisation. RED now uses
+  ``rte_rand32()``, which has per lcore state.
+
 
 API Changes
 -----------
@@ -101,7 +107,6 @@ API Changes
    Also, make sure to start the actual text at the margin.
    =======================================================
 
-
 ABI Changes
 -----------
 
@@ -117,6 +122,11 @@ ABI Changes
    Also, make sure to start the actual text at the margin.
    =======================================================
 
+* sched: Removed the exported variables ``rte_red_rand_seed`` and
+  ``rte_red_rand_val``. They held the state of the private random
+  number generator used by RED, which has been replaced by
+  ``rte_rand32()``.
+
 
 Known Issues
 ------------
diff --git a/lib/sched/rte_red.c b/lib/sched/rte_red.c
index d7534d0bee..6d20afa9dc 100644
--- a/lib/sched/rte_red.c
+++ b/lib/sched/rte_red.c
@@ -5,14 +5,9 @@
 #include <math.h>
 #include <eal_export.h>
 #include "rte_red.h"
-#include <rte_random.h>
 #include <rte_common.h>
 
-static int rte_red_init_done = 0;     /**< Flag to indicate that global initialisation is done */
-RTE_EXPORT_SYMBOL(rte_red_rand_val)
-uint32_t rte_red_rand_val = 0;        /**< Random value cache */
-RTE_EXPORT_SYMBOL(rte_red_rand_seed)
-uint32_t rte_red_rand_seed = 0;       /**< Seed for random number generation */
+static int rte_red_init_done;         /**< Flag to indicate that global initialisation is done */
 
 /**
  * table[i] = log2(1-Wq) * Scale * -1
@@ -116,8 +111,6 @@ rte_red_config_init(struct rte_red_config *red_cfg,
 	 *  Initialize the RED module if not already done
 	 */
 	if (!rte_red_init_done) {
-		rte_red_rand_seed = rte_rand();
-		rte_red_rand_val = rte_fast_rand();
 		__rte_red_init_tables();
 		rte_red_init_done = 1;
 	}
diff --git a/lib/sched/rte_red.h b/lib/sched/rte_red.h
index 3b90cc46a9..8c9d86f6f5 100644
--- a/lib/sched/rte_red.h
+++ b/lib/sched/rte_red.h
@@ -15,6 +15,7 @@
 #include <rte_debug.h>
 #include <rte_cycles.h>
 #include <rte_branch_prediction.h>
+#include <rte_random.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -34,8 +35,6 @@ extern "C" {
 /**
  * Externs
  */
-extern uint32_t rte_red_rand_val;
-extern uint32_t rte_red_rand_seed;
 extern uint16_t rte_red_log2_1_minus_Wq[RTE_RED_WQ_LOG2_NUM];
 extern uint16_t rte_red_pow2_frac_inv[16];
 
@@ -102,23 +101,6 @@ rte_red_config_init(struct rte_red_config *red_cfg,
 	const uint16_t max_th,
 	const uint16_t maxp_inv);
 
-/**
- * @brief Generate random number for RED
- *
- * Implementation based on:
- * http://software.intel.com/en-us/articles/fast-random-number-generator-on-the-intel-pentiumr-4-processor/
- *
- * 10 bit shift has been found through empirical tests (was 16).
- *
- * @return Random number between 0 and (2^22 - 1)
- */
-static inline uint32_t
-rte_fast_rand(void)
-{
-	rte_red_rand_seed = (214013 * rte_red_rand_seed) + 2531011;
-	return rte_red_rand_seed >> 10;
-}
-
 /**
  * @brief calculate factor to scale average queue size when queue
  *        becomes empty
@@ -293,12 +275,8 @@ __rte_red_drop(const struct rte_red_config *red_cfg, struct rte_red *red)
 
 	pa_den = red_cfg->pa_const - pa_num_count;
 
-	/* If drop, generate and save random number to be used next time */
-	if (unlikely((rte_red_rand_val % pa_den) < pa_num)) {
-		rte_red_rand_val = rte_fast_rand();
-
+	if (unlikely((rte_rand32() % pa_den) < pa_num))
 		return 1;
-	}
 
 	/* No drop */
 	return 0;
-- 
2.53.0