From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by dpdk.space (Postfix) with ESMTP id 2914CA05D3 for ; Mon, 22 Apr 2019 13:35:13 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 2AD7F1B46D; Mon, 22 Apr 2019 13:35:12 +0200 (CEST) Received: from smtp.tuxdriver.com (charlotte.tuxdriver.com [70.61.120.58]) by dpdk.org (Postfix) with ESMTP id 9A6D21B217 for ; Mon, 22 Apr 2019 13:35:10 +0200 (CEST) Received: from cpe-2606-a000-111b-405a-0-0-0-188a.dyn6.twc.com ([2606:a000:111b:405a::188a] helo=localhost) by smtp.tuxdriver.com with esmtpsa (TLSv1:AES256-SHA:256) (Exim 4.63) (envelope-from ) id 1hIXDq-0004jJ-Hb; Mon, 22 Apr 2019 07:35:06 -0400 Date: Mon, 22 Apr 2019 07:34:20 -0400 From: Neil Horman To: Mattias =?iso-8859-1?Q?R=F6nnblom?= Cc: dev@dpdk.org, stephen@networkplumber.org Message-ID: <20190422113420.GA22056@hmswarspite.think-freely.org> References: <20190419212138.17422-2-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20190419212138.17422-2-mattias.ronnblom@ericsson.com> User-Agent: Mutt/1.11.3 (2019-02-01) X-Spam-Score: -2.9 (--) X-Spam-Status: No Subject: Re: [dpdk-dev] [RFC v2 1/2] eal: replace libc-based random number generation with LFSR X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Message-ID: <20190422113420.vGE8SdN46jxaCs_dFc67jHYhx-Upg1abeQzwu5tTYBs@z> On Fri, Apr 19, 2019 at 11:21:37PM +0200, Mattias Rönnblom wrote: > 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(). > > Signed-off-by: Mattias Rönnblom > --- > 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 > -#include > > /** > * 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..288e7b8c5 > --- /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 > + > +#include > +#include > +#include > +#include > + > +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 well-known > + * good multiplier/increments 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_experimental > +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_experimental > +rte_rand(void) Do you really want to mark this as experimental? I know it will trigger the symbol checker with a warning if you don't, but this function already existed previously and was accepted as part of the ABI. Given that the prototype hasn't changed, I think you just need to accept it as a non-experimental function > +{ > + 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 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; > };