From: "Mattias Rönnblom" <mattias.ronnblom@ericsson.com>
To: <dev@dpdk.org>
Cc: "Mattias Rönnblom" <mattias.ronnblom@ericsson.com>
Subject: [dpdk-dev] [RFC 1/3] Replace lrand48-based rte_rand with LFSR generator
Date: Mon, 8 Apr 2019 14:30:27 +0200 [thread overview]
Message-ID: <20190408123029.6701-1-mattias.ronnblom@ericsson.com> (raw)
In-Reply-To: <20190405135030.09c5291a@shemminger-XPS-13-9360>
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 four 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.
Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
lib/librte_eal/common/include/rte_random.h | 25 ++---
lib/librte_eal/common/meson.build | 1 +
lib/librte_eal/common/rte_random.c | 104 +++++++++++++++++++++
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, 119 insertions(+), 19 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..bca85a672 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,14 +24,15 @@ 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.
@@ -41,18 +41,13 @@ rte_srand(uint64_t seedval)
* congruential algorithm and 48-bit integer arithmetic, called twice
* to generate a 64-bit value.
*
+ * 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..b8fb7006e
--- /dev/null
+++ b/lib/librte_eal/common/rte_random.c
@@ -0,0 +1,104 @@
+/* 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 {
+ uint32_t z1;
+ uint32_t z2;
+ uint32_t z3;
+ uint32_t z4;
+} __rte_cache_aligned;
+
+static struct rte_rand_state rand_states[RTE_MAX_LCORE];
+
+static inline uint32_t
+__rte_rand_lcg32(uint32_t *seed)
+{
+ *seed = 1103515245U * *seed + 12345;
+ return *seed;
+}
+
+static uint32_t
+__rte_rand_lfsr113_gen_seed(uint32_t *seed, uint32_t min_value)
+{
+ uint32_t res = __rte_rand_lcg32(seed);
+
+ return res < min_value ? res + min_value : res;
+}
+
+static void
+__rte_srand_lfsr113(uint32_t seed, struct rte_rand_state *state)
+{
+ uint32_t lcg32_seed = seed;
+ state->z1 = __rte_rand_lfsr113_gen_seed(&lcg32_seed, 2U);
+ state->z2 = __rte_rand_lfsr113_gen_seed(&lcg32_seed, 8U);
+ state->z3 = __rte_rand_lfsr113_gen_seed(&lcg32_seed, 16U);
+ state->z4 = __rte_rand_lfsr113_gen_seed(&lcg32_seed, 128U);
+}
+
+void __rte_experimental
+rte_srand(uint64_t seedval)
+{
+ 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_lfsr113(seedval + lcore_id, &rand_states[lcore_id]);
+}
+
+static __rte_always_inline uint32_t
+__rte_rand_lfsr113(uint32_t s, uint32_t a, uint32_t b, uint32_t c, uint32_t d)
+{
+ return ((s & c) << d) ^ (((s << a) ^ s) >> b);
+}
+
+static __rte_always_inline uint32_t
+__rte_rand32(struct rte_rand_state *state)
+{
+ state->z1 = __rte_rand_lfsr113(state->z1, 6U, 13U, 4294967294U, 18U);
+ state->z2 = __rte_rand_lfsr113(state->z2, 2U, 27U, 4294967288U, 2U);
+ state->z3 = __rte_rand_lfsr113(state->z3, 13U, 21U, 4294967280U, 7U);
+ state->z4 = __rte_rand_lfsr113(state->z4, 3U, 12U, 4294967168U, 13U);
+
+ return state->z1 ^ state->z2 ^ state->z3 ^ state->z4;
+}
+
+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_experimental
+rte_rand(void)
+{
+ struct rte_rand_state *state;
+ uint64_t low;
+ uint64_t high;
+
+ state = __rte_rand_get_state();
+
+ low = __rte_rand32(state);
+ high = __rte_rand32(state);
+
+ return low | (high << 32);
+}
+
+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 f7ae62d7b..c2bdf0a67 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 d6e375135..0d60668fa 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -366,10 +366,12 @@ EXPERIMENTAL {
rte_mp_request_async;
rte_mp_sendmsg;
rte_option_register;
+ rte_rand;
rte_realloc_socket;
rte_service_lcore_attr_get;
rte_service_lcore_attr_reset_all;
rte_service_may_be_active;
rte_socket_count;
rte_socket_id_by_idx;
+ rte_srand;
};
--
2.17.1
next prev parent reply other threads:[~2019-04-08 12:30 UTC|newest]
Thread overview: 137+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-04-05 13:45 [dpdk-dev] [RFC] eal: make rte_rand() MT safe Mattias Rönnblom
2019-04-05 13:45 ` Mattias Rönnblom
2019-04-05 13:51 ` Mattias Rönnblom
2019-04-05 13:51 ` Mattias Rönnblom
2019-04-05 14:28 ` Bruce Richardson
2019-04-05 14:28 ` Bruce Richardson
2019-04-05 14:56 ` Mattias Rönnblom
2019-04-05 14:56 ` Mattias Rönnblom
2019-04-05 16:57 ` Stephen Hemminger
2019-04-05 16:57 ` Stephen Hemminger
2019-04-05 18:04 ` Mattias Rönnblom
2019-04-05 18:04 ` Mattias Rönnblom
2019-04-05 20:50 ` Stephen Hemminger
2019-04-05 20:50 ` Stephen Hemminger
2019-04-06 5:52 ` Mattias Rönnblom
2019-04-06 5:52 ` Mattias Rönnblom
2019-04-08 12:30 ` Mattias Rönnblom [this message]
2019-04-08 12:30 ` [dpdk-dev] [RFC 1/3] Replace lrand48-based rte_rand with LFSR generator Mattias Rönnblom
2019-04-08 12:30 ` [dpdk-dev] [RFC 2/3] Add 32-bit version of rte_rand Mattias Rönnblom
2019-04-08 12:30 ` Mattias Rönnblom
2019-04-08 12:30 ` [dpdk-dev] [RFC 3/3] Introduce random generator functions with upper bound Mattias Rönnblom
2019-04-08 12:30 ` Mattias Rönnblom
2019-04-08 12:47 ` [dpdk-dev] [RFC 1/3] Replace lrand48-based rte_rand with LFSR generator Mattias Rönnblom
2019-04-08 12:47 ` Mattias Rönnblom
2019-04-19 21:21 ` [dpdk-dev] [RFC v2 0/2] Pseudo-number generation improvements Mattias Rönnblom
2019-04-19 21:21 ` Mattias Rönnblom
2019-04-19 21:21 ` [dpdk-dev] [RFC v2 1/2] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-04-19 21:21 ` Mattias Rönnblom
2019-04-22 11:34 ` Neil Horman
2019-04-22 11:34 ` Neil Horman
2019-04-22 14:49 ` Stephen Hemminger
2019-04-22 14:49 ` Stephen Hemminger
2019-04-22 15:52 ` Mattias Rönnblom
2019-04-22 15:52 ` Mattias Rönnblom
2019-04-22 17:44 ` Mattias Rönnblom
2019-04-22 17:44 ` Mattias Rönnblom
2019-04-23 11:33 ` Neil Horman
2019-04-23 11:33 ` Neil Horman
2019-04-23 17:13 ` Mattias Rönnblom
2019-04-23 17:13 ` Mattias Rönnblom
2019-04-24 11:37 ` Neil Horman
2019-04-24 11:37 ` Neil Horman
2019-04-23 15:31 ` Stephen Hemminger
2019-04-23 15:31 ` Stephen Hemminger
2019-04-23 17:17 ` Mattias Rönnblom
2019-04-23 17:17 ` Mattias Rönnblom
2019-04-24 7:52 ` Mattias Rönnblom
2019-04-24 7:52 ` Mattias Rönnblom
2019-04-24 12:33 ` [dpdk-dev] [RFC v3 0/2] Pseudo-random number generation improvements Mattias Rönnblom
2019-04-24 12:33 ` Mattias Rönnblom
2019-04-24 12:33 ` [dpdk-dev] [RFC v3 1/2] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-04-24 12:33 ` Mattias Rönnblom
2019-05-08 20:12 ` Stephen Hemminger
2019-05-08 20:12 ` Stephen Hemminger
2019-05-08 20:30 ` Mattias Rönnblom
2019-05-08 20:30 ` Mattias Rönnblom
2019-05-09 1:10 ` Stephen Hemminger
2019-05-09 1:10 ` Stephen Hemminger
2019-05-14 9:20 ` [dpdk-dev] [PATCH 0/6] Pseudo-random number generation improvements Mattias Rönnblom
2019-05-14 9:20 ` Mattias Rönnblom
2019-05-14 9:20 ` [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-05-14 9:20 ` Mattias Rönnblom
2019-05-14 9:32 ` Mattias Rönnblom
2019-05-14 9:32 ` Mattias Rönnblom
2019-05-14 14:16 ` Neil Horman
2019-05-14 14:16 ` Neil Horman
2019-05-14 14:53 ` Mattias Rönnblom
2019-05-14 14:53 ` Mattias Rönnblom
2019-05-17 19:27 ` Neil Horman
2019-05-17 20:57 ` Bruce Richardson
2019-05-17 21:10 ` Mattias Rönnblom
2019-05-19 18:32 ` Neil Horman
2019-05-14 15:27 ` Stephen Hemminger
2019-05-14 15:27 ` Stephen Hemminger
2019-05-14 9:20 ` [dpdk-dev] [PATCH 2/6] eal: add pseudo-random number generation performance test Mattias Rönnblom
2019-05-14 9:20 ` Mattias Rönnblom
2019-05-14 9:20 ` [dpdk-dev] [PATCH 3/6] eal: improve entropy for initial PRNG seed Mattias Rönnblom
2019-05-14 9:20 ` Mattias Rönnblom
2019-05-14 9:36 ` Mattias Rönnblom
2019-05-14 9:36 ` Mattias Rönnblom
2019-05-14 9:39 ` Bruce Richardson
2019-05-14 9:39 ` Bruce Richardson
2019-05-14 11:58 ` Mattias Rönnblom
2019-05-14 11:58 ` Mattias Rönnblom
2019-05-14 9:37 ` Bruce Richardson
2019-05-14 9:37 ` Bruce Richardson
2019-05-14 9:20 ` [dpdk-dev] [PATCH 4/6] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-05-14 9:20 ` Mattias Rönnblom
2019-05-14 9:20 ` [dpdk-dev] [PATCH 5/6] eal: add bounded PRNG performance tests Mattias Rönnblom
2019-05-14 9:20 ` Mattias Rönnblom
2019-05-14 9:20 ` [dpdk-dev] [PATCH 6/6] eal: add pseudo-random number generation to MAINTAINERS Mattias Rönnblom
2019-05-14 9:20 ` Mattias Rönnblom
2019-05-16 17:55 ` [dpdk-dev] [PATCH v2 0/6] Pseudo-random number generation improvements Mattias Rönnblom
2019-05-16 17:55 ` [dpdk-dev] [PATCH v2 1/6] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-05-16 17:55 ` [dpdk-dev] [PATCH v2 2/6] eal: add pseudo-random number generation performance test Mattias Rönnblom
2019-05-16 17:55 ` [dpdk-dev] [PATCH v2 3/6] eal: improve entropy for initial PRNG seed Mattias Rönnblom
2019-05-16 17:55 ` [dpdk-dev] [PATCH v2 4/6] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-05-16 17:55 ` [dpdk-dev] [PATCH v2 5/6] eal: add bounded PRNG performance tests Mattias Rönnblom
2019-05-16 17:55 ` [dpdk-dev] [PATCH v2 6/6] eal: add PRNG to MAINTAINERS and release notes Mattias Rönnblom
2019-05-16 20:35 ` [dpdk-dev] [PATCH v2 0/6] Pseudo-random number generation improvements Bruce Richardson
2019-06-05 10:43 ` [dpdk-dev] [PATCH v3 " Mattias Rönnblom
2019-06-05 10:43 ` [dpdk-dev] [PATCH v3 1/6] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-06-05 10:43 ` [dpdk-dev] [PATCH v3 2/6] eal: add pseudo-random number generation performance test Mattias Rönnblom
2019-06-27 21:23 ` Thomas Monjalon
2019-06-28 8:20 ` Mattias Rönnblom
2019-06-05 10:43 ` [dpdk-dev] [PATCH v3 3/6] eal: improve entropy for initial PRNG seed Mattias Rönnblom
2019-06-05 10:43 ` [dpdk-dev] [PATCH v3 4/6] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-06-05 10:43 ` [dpdk-dev] [PATCH v3 5/6] eal: add bounded PRNG performance tests Mattias Rönnblom
2019-06-05 10:44 ` [dpdk-dev] [PATCH v3 6/6] eal: add PRNG to MAINTAINERS and release notes Mattias Rönnblom
2019-06-27 21:27 ` Thomas Monjalon
2019-06-28 8:17 ` Mattias Rönnblom
2019-06-15 12:23 ` [dpdk-dev] [PATCH v3 0/6] Pseudo-random number generation improvements Mattias Rönnblom
2019-06-28 9:01 ` [dpdk-dev] [PATCH v4 0/5] " Mattias Rönnblom
2019-06-28 9:01 ` [dpdk-dev] [PATCH v4 1/5] eal: replace libc-based random number generation with LFSR Mattias Rönnblom
2019-06-28 9:01 ` [dpdk-dev] [PATCH v4 2/5] eal: add pseudo-random number generation performance test Mattias Rönnblom
2019-06-28 9:01 ` [dpdk-dev] [PATCH v4 3/5] eal: improve entropy for initial PRNG seed Mattias Rönnblom
2019-06-28 19:01 ` Ferruh Yigit
2019-06-28 20:58 ` Mattias Rönnblom
2019-06-28 21:08 ` [dpdk-dev] [PATCH] eal: use 32-bit RDSEED to allow 32-bit x86 usage Mattias Rönnblom
2019-06-29 12:54 ` Thomas Monjalon
2019-06-28 9:01 ` [dpdk-dev] [PATCH v4 4/5] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-06-28 9:01 ` [dpdk-dev] [PATCH v4 5/5] eal: add bounded PRNG performance tests Mattias Rönnblom
2019-06-28 13:24 ` [dpdk-dev] [PATCH v4 0/5] Pseudo-random number generation improvements Thomas Monjalon
2019-04-24 12:33 ` [dpdk-dev] [RFC v3 2/2] eal: introduce random generator function with upper bound Mattias Rönnblom
2019-04-24 12:33 ` Mattias Rönnblom
2019-04-19 21:21 ` [dpdk-dev] [RFC v2 " Mattias Rönnblom
2019-04-19 21:21 ` Mattias Rönnblom
2019-04-20 21:08 ` Wiles, Keith
2019-04-20 21:08 ` Wiles, Keith
2019-04-21 19:05 ` Mattias Rönnblom
2019-04-21 19:05 ` Mattias Rönnblom
2019-04-22 4:33 ` Wiles, Keith
2019-04-22 4:33 ` Wiles, Keith
2019-04-22 7:07 ` Mattias Rönnblom
2019-04-22 7:07 ` Mattias Rönnblom
2019-04-22 13:19 ` Wiles, Keith
2019-04-22 13:19 ` Wiles, Keith
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190408123029.6701-1-mattias.ronnblom@ericsson.com \
--to=mattias.ronnblom@ericsson.com \
--cc=dev@dpdk.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).