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 <[email protected]> --- 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 f25e497729..9d1238d6f3 100644 --- a/doc/guides/rel_notes/release_26_11.rst +++ b/doc/guides/rel_notes/release_26_11.rst @@ -65,6 +65,10 @@ New Features values which must not be predictable, such as keys, hash seeds and MAC addresses, where the pseudo-random ``rte_rand()`` is not suitable. + * 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 4b777f69f4..db4e19b414 100644 --- a/lib/eal/common/rte_random.c +++ b/lib/eal/common/rte_random.c @@ -39,55 +39,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) @@ -95,16 +85,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
