[PATCH v2 3/5] random: use all 64 bits of the seed

[Stephen Hemminger <stephen@networkplumber.org>]

The generator state is five 64 bit words, expanded from the seed by a
32 bit linear congruential generator. The two halves of the seed were
folded together first, so only 32 bits of it had any effect, and the
low order bits of such a generator are weak, leaving the five words
with correlated low bits.

Expand the seed with SplitMix64 instead, so every bit of the seed
affects every word of the state. It is described in "Fast Splittable
Pseudorandom Number Generators" by Steele, Lea and Flood,
https://doi.org/10.1145/2714064.2660195 and is what the authors of
the xoshiro and xoroshiro generators recommend for seeding.

The per-lcore seeds were formed by adding the lcore id to the seed,
leaving neighbouring lcores with nearly identical state. Pass that
sum through SplitMix64 as well.

Fixes: 3f002f069612 ("eal: replace libc-based random generation with LFSR")

Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
 doc/guides/rel_notes/release_26_11.rst |  4 ++
 lib/eal/common/rte_random.c            | 74 +++++++++++++-------------
 2 files changed, 40 insertions(+), 38 deletions(-)

diff --git a/doc/guides/rel_notes/release_26_11.rst b/doc/guides/rel_notes/release_26_11.rst
index 9bef8b4774..2d12eb7949 100644
--- a/doc/guides/rel_notes/release_26_11.rst
+++ b/doc/guides/rel_notes/release_26_11.rst
@@ -161,6 +161,10 @@ New Features
 * **Updated random number generation.**
 
   * The initial seed is now always taken from ``getentropy()``.
+  * Improved the expansion of the seed into the generator state. All
+    64 bits of the value passed to ``rte_srand()`` now affect the state,
+    so a given seed produces a different sequence than in previous
+    releases.
 
 
 Removed Items
diff --git a/lib/eal/common/rte_random.c b/lib/eal/common/rte_random.c
index b036c50349..3c5b36aa2c 100644
--- a/lib/eal/common/rte_random.c
+++ b/lib/eal/common/rte_random.c
@@ -35,55 +35,45 @@ static RTE_LCORE_VAR_HANDLE(struct rte_rand_state, rand_state);
 /* instance to be shared by all unregistered non-EAL threads */
 static struct rte_rand_state unregistered_rand_state;
 
-static uint32_t
-__rte_rand_lcg32(uint32_t *seed)
-{
-	*seed = 1103515245U * *seed + 12345U;
-
-	return *seed;
-}
-
+/* SplitMix64, used to expand the seed into the generator state.
+ * It has a full 64 bit period and good avalanche, so all the bits
+ * of the seed affect every word of the resulting state.
+ *
+ * See "Fast Splittable Pseudorandom Number Generators" by Steele,
+ * Lea and Flood, https://doi.org/10.1145/2714064.2660195
+ */
 static uint64_t
-__rte_rand_lcg64(uint32_t *seed)
+__rte_rand_splitmix64(uint64_t *state)
 {
-	uint64_t low;
-	uint64_t high;
-
-	/* A 64-bit LCG would have been much cleaner, but good
-	 * multiplier/increments for such seem hard to come by.
-	 */
+	uint64_t z;
 
-	low = __rte_rand_lcg32(seed);
-	high = __rte_rand_lcg32(seed);
+	z = (*state += 0x9E3779B97F4A7C15ULL);
+	z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
+	z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
 
-	return low | (high << 32);
+	return z ^ (z >> 31);
 }
 
 static uint64_t
-__rte_rand_lfsr258_gen_seed(uint32_t *seed, uint64_t min_value)
+__rte_rand_lfsr258_gen_seed(uint64_t *state, uint64_t min_value)
 {
-	uint64_t res;
-
-	res = __rte_rand_lcg64(seed);
-
-	if (res < min_value)
-		res += min_value;
-
-	return res;
+	/* LFSR258 degenerates unless each word exceeds its threshold.
+	 * All thresholds are powers of two, so a bitwise or is enough
+	 * and keeps the remaining bits untouched.
+	 */
+	return __rte_rand_splitmix64(state) | min_value;
 }
 
 static void
 __rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)
 {
-	uint32_t lcg_seed;
-
-	lcg_seed = (uint32_t)(seed ^ (seed >> 32));
+	uint64_t mix_state = seed;
 
-	state->z1 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 2UL);
-	state->z2 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 512UL);
-	state->z3 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 4096UL);
-	state->z4 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 131072UL);
-	state->z5 = __rte_rand_lfsr258_gen_seed(&lcg_seed, 8388608UL);
+	state->z1 = __rte_rand_lfsr258_gen_seed(&mix_state, 2UL);
+	state->z2 = __rte_rand_lfsr258_gen_seed(&mix_state, 512UL);
+	state->z3 = __rte_rand_lfsr258_gen_seed(&mix_state, 4096UL);
+	state->z4 = __rte_rand_lfsr258_gen_seed(&mix_state, 131072UL);
+	state->z5 = __rte_rand_lfsr258_gen_seed(&mix_state, 8388608UL);
 }
 
 RTE_EXPORT_SYMBOL(rte_srand)
@@ -91,16 +81,24 @@ void
 rte_srand(uint64_t seed)
 {
 	unsigned int lcore_id;
+	uint64_t mix_state;
 
-	/* add lcore_id to seed to avoid having the same sequence */
+	/* Mix in the lcore id so that each lcore gets an unrelated
+	 * sequence. Adding it to the seed would leave neighbouring
+	 * lcores with nearly identical generator state.
+	 */
 	for (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id++) {
 		struct rte_rand_state *lcore_state =
 			RTE_LCORE_VAR_LCORE(lcore_id, rand_state);
 
-		__rte_srand_lfsr258(seed + lcore_id, lcore_state);
+		mix_state = seed + lcore_id;
+		__rte_srand_lfsr258(__rte_rand_splitmix64(&mix_state),
+				    lcore_state);
 	}
 
-	__rte_srand_lfsr258(seed + lcore_id, &unregistered_rand_state);
+	mix_state = seed + lcore_id;
+	__rte_srand_lfsr258(__rte_rand_splitmix64(&mix_state),
+			    &unregistered_rand_state);
 }
 
 static __rte_always_inline uint64_t
-- 
2.53.0