[dpdk-dev] [RFC v3 1/2] eal: replace libc-based random number generation with LFSR

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

This commit replaces rte_rand()'s use of lrand48() with a DPDK-native
combined Linear Feedback Shift Register (LFSR) (also known as
Tausworthe) pseudo-number generator, with five sequences.

This generator is faster and produces better quality random numbers
than libc's lrand48() implementation. This implementation, as opposed
to lrand48(), is multi-thread safe in regards to concurrent rte_rand()
calls from different lcore threads. It is not cryptographically
secure - just like lrand48().

Bugzilla ID: 114

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/include/rte_random.h |  29 ++---
 lib/librte_eal/common/meson.build          |   1 +
 lib/librte_eal/common/rte_random.c         | 137 +++++++++++++++++++++
 lib/librte_eal/freebsd/eal/Makefile        |   1 +
 lib/librte_eal/freebsd/eal/eal.c           |   2 -
 lib/librte_eal/linux/eal/Makefile          |   1 +
 lib/librte_eal/linux/eal/eal.c             |   2 -
 lib/librte_eal/rte_eal_version.map         |   2 +
 8 files changed, 153 insertions(+), 22 deletions(-)
 create mode 100644 lib/librte_eal/common/rte_random.c

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index b2ca1c209..66dfe8ae7 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -16,7 +16,6 @@ extern "C" {
 #endif
 
 #include <stdint.h>
-#include <stdlib.h>
 
 /**
  * Seed the pseudo-random generator.
@@ -25,34 +24,28 @@ extern "C" {
  * value. It may need to be re-seeded by the user with a real random
  * value.
  *
+ * This function is not multi-thread safe in regards to other
+ * rte_srand() calls, nor is it in relation to concurrent rte_rand()
+ * calls.
+ *
  * @param seedval
  *   The value of the seed.
  */
-static inline void
-rte_srand(uint64_t seedval)
-{
-	srand48((long)seedval);
-}
+void
+rte_srand(uint64_t seedval);
 
 /**
  * Get a pseudo-random value.
  *
- * This function generates pseudo-random numbers using the linear
- * congruential algorithm and 48-bit integer arithmetic, called twice
- * to generate a 64-bit value.
+ * The generator is not cryptographically secure.
+ *
+ * If called from lcore threads, this function is thread-safe.
  *
  * @return
  *   A pseudo-random value between 0 and (1<<64)-1.
  */
-static inline uint64_t
-rte_rand(void)
-{
-	uint64_t val;
-	val = (uint64_t)lrand48();
-	val <<= 32;
-	val += (uint64_t)lrand48();
-	return val;
-}
+uint64_t
+rte_rand(void);
 
 #ifdef __cplusplus
 }
diff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build
index 0670e4102..bafd23207 100644
--- a/lib/librte_eal/common/meson.build
+++ b/lib/librte_eal/common/meson.build
@@ -35,6 +35,7 @@ common_sources = files(
 	'rte_keepalive.c',
 	'rte_malloc.c',
 	'rte_option.c',
+	'rte_random.c',
 	'rte_reciprocal.c',
 	'rte_service.c'
 )
diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
new file mode 100644
index 000000000..85dfd0cde
--- /dev/null
+++ b/lib/librte_eal/common/rte_random.c
@@ -0,0 +1,137 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <stdlib.h>
+
+#include <rte_cycles.h>
+#include <rte_eal.h>
+#include <rte_lcore.h>
+#include <rte_random.h>
+
+struct rte_rand_state {
+	uint64_t z1;
+	uint64_t z2;
+	uint64_t z3;
+	uint64_t z4;
+	uint64_t z5;
+} __rte_cache_aligned;
+
+static struct rte_rand_state rand_states[RTE_MAX_LCORE];
+
+static uint32_t
+__rte_rand_lcg32(uint32_t *seed)
+{
+	*seed = 1103515245U * *seed + 12345U;
+
+	return *seed;
+}
+
+static uint64_t
+__rte_rand_lcg64(uint32_t *seed)
+{
+	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.
+	 */
+
+	low = __rte_rand_lcg32(seed);
+	high = __rte_rand_lcg32(seed);
+
+	return low | (high << 32);
+}
+
+static uint64_t
+__rte_rand_lfsr258_gen_seed(uint32_t *seed, uint64_t min_value)
+{
+	uint64_t res;
+
+	res = __rte_rand_lcg64(seed);
+
+	if (res < min_value)
+		res += min_value;
+
+	return res;
+}
+
+static void
+__rte_srand_lfsr258(uint64_t seed, struct rte_rand_state *state)
+{
+	uint32_t lcg_seed;
+
+	lcg_seed = (uint32_t)(seed ^ (seed >> 32));
+
+	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);
+}
+
+void
+rte_srand(uint64_t seed)
+{
+	unsigned int lcore_id;
+
+	/* add lcore_id to seed to avoid having the same sequence */
+	for (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id++)
+		__rte_srand_lfsr258(seed + lcore_id, &rand_states[lcore_id]);
+}
+
+static __rte_always_inline uint64_t
+__rte_rand_lfsr258_comp(uint64_t z, uint64_t a, uint64_t b, uint64_t c,
+			uint64_t d)
+{
+	return ((z & c) << d) ^ (((z << a) ^ z) >> b);
+}
+
+/* Based on L’Ecuyer, P.: Tables of maximally equidistributed combined
+ * LFSR generators.
+ */
+
+static __rte_always_inline uint64_t
+__rte_rand_lfsr258(struct rte_rand_state *state)
+{
+	state->z1 = __rte_rand_lfsr258_comp(state->z1, 1UL, 53UL,
+					    18446744073709551614UL, 10UL);
+	state->z2 = __rte_rand_lfsr258_comp(state->z2, 24UL, 50UL,
+					    18446744073709551104UL, 5UL);
+	state->z3 = __rte_rand_lfsr258_comp(state->z3, 3UL, 23UL,
+					    18446744073709547520UL, 29UL);
+	state->z4 = __rte_rand_lfsr258_comp(state->z4, 5UL, 24UL,
+					    18446744073709420544UL, 23UL);
+	state->z5 = __rte_rand_lfsr258_comp(state->z5, 3UL, 33UL,
+					    18446744073701163008UL, 8UL);
+
+	return state->z1 ^ state->z2 ^ state->z3 ^ state->z4 ^ state->z5;
+}
+
+static __rte_always_inline
+struct rte_rand_state *__rte_rand_get_state(void)
+{
+	unsigned int lcore_id;
+
+	lcore_id = rte_lcore_id();
+
+	if (unlikely(lcore_id == LCORE_ID_ANY))
+		lcore_id = rte_get_master_lcore();
+
+	return &rand_states[lcore_id];
+}
+
+uint64_t
+rte_rand(void)
+{
+	struct rte_rand_state *state;
+
+	state = __rte_rand_get_state();
+
+	return __rte_rand_lfsr258(state);
+}
+
+RTE_INIT(rte_rand_init)
+{
+	rte_srand(rte_get_timer_cycles());
+}
diff --git a/lib/librte_eal/freebsd/eal/Makefile b/lib/librte_eal/freebsd/eal/Makefile
index 19854ee2c..ca616c480 100644
--- a/lib/librte_eal/freebsd/eal/Makefile
+++ b/lib/librte_eal/freebsd/eal/Makefile
@@ -69,6 +69,7 @@ SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += malloc_mp.c
 SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_keepalive.c
 SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_option.c
 SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_service.c
+SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_random.c
 SRCS-$(CONFIG_RTE_EXEC_ENV_FREEBSD) += rte_reciprocal.c
 
 # from arch dir
diff --git a/lib/librte_eal/freebsd/eal/eal.c b/lib/librte_eal/freebsd/eal/eal.c
index c6ac9028f..5d43310b3 100644
--- a/lib/librte_eal/freebsd/eal/eal.c
+++ b/lib/librte_eal/freebsd/eal/eal.c
@@ -727,8 +727,6 @@ rte_eal_init(int argc, char **argv)
 #endif
 	}
 
-	rte_srand(rte_rdtsc());
-
 	/* in secondary processes, memory init may allocate additional fbarrays
 	 * not present in primary processes, so to avoid any potential issues,
 	 * initialize memzones first.
diff --git a/lib/librte_eal/linux/eal/Makefile b/lib/librte_eal/linux/eal/Makefile
index 6e5261152..729795a10 100644
--- a/lib/librte_eal/linux/eal/Makefile
+++ b/lib/librte_eal/linux/eal/Makefile
@@ -77,6 +77,7 @@ SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += malloc_mp.c
 SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_keepalive.c
 SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_option.c
 SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_service.c
+SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_random.c
 SRCS-$(CONFIG_RTE_EXEC_ENV_LINUX) += rte_reciprocal.c
 
 # from arch dir
diff --git a/lib/librte_eal/linux/eal/eal.c b/lib/librte_eal/linux/eal/eal.c
index 161399619..d6bf0e89e 100644
--- a/lib/librte_eal/linux/eal/eal.c
+++ b/lib/librte_eal/linux/eal/eal.c
@@ -1083,8 +1083,6 @@ rte_eal_init(int argc, char **argv)
 #endif
 	}
 
-	rte_srand(rte_rdtsc());
-
 	if (rte_eal_log_init(logid, internal_config.syslog_facility) < 0) {
 		rte_eal_init_alert("Cannot init logging.");
 		rte_errno = ENOMEM;
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index 245493461..381351749 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -282,8 +282,10 @@ DPDK_19.05 {
 	rte_devargs_remove;
 	rte_devargs_type_count;
 	rte_eal_cleanup;
+	rte_rand;
 	rte_socket_count;
 	rte_socket_id_by_idx;
+	rte_srand;
 
 } DPDK_18.11;
 
-- 
2.17.1