[RFC,v2,1/2] eal: replace libc-based random number generation with LFSR
Checks
Commit Message
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 <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
Comments
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 <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..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 <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 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;
> };
On Mon, 22 Apr 2019 07:34:20 -0400
Neil Horman <nhorman@tuxdriver.com> wrote:
> > +
> > +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
Agree with Neil. Don't mark existing functions as experimental.
On 2019-04-22 13:34, Neil Horman wrote:
>> +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
>
I'll remove the experimental tag and move it into the 19_05 section
(without suggesting it should go into 19.05). That maneuver seems not to
trigger any build warnings/errors.
It's been a part of the API since forever, but it was never a part of
the ABI.
On 2019-04-22 17:52, Mattias Rönnblom wrote:
> On 2019-04-22 13:34, Neil Horman wrote:
>
>>> +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
>>
>
> I'll remove the experimental tag and move it into the 19_05 section
> (without suggesting it should go into 19.05). That maneuver seems not to
> trigger any build warnings/errors.
>
OK, so that wasn't true. It does trigger a build error, courtesy of
buildtools/check-experimental-syms.sh.
I can't see any obvious way around it. Ideas, anyone?
On Mon, Apr 22, 2019 at 07:44:39PM +0200, Mattias Rönnblom wrote:
> On 2019-04-22 17:52, Mattias Rönnblom wrote:
> > On 2019-04-22 13:34, Neil Horman wrote:
> >
> > > > +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
> > >
> >
> > I'll remove the experimental tag and move it into the 19_05 section
> > (without suggesting it should go into 19.05). That maneuver seems not to
> > trigger any build warnings/errors.
> >
>
> OK, so that wasn't true. It does trigger a build error, courtesy of
> buildtools/check-experimental-syms.sh.
>
> I can't see any obvious way around it. Ideas, anyone?
>
No, we would have to waive it. But its pretty clear that This function has been
around forever, so I think it would be worse to demote it to an experimental
symbol. The only thing you're doing here is moving it from an inline function
(which is arguably part of the ABI, even if it never appeared as a symbol in the
ELF file), to a fully fleged symbol with a new implementation.
Neil
On Mon, 22 Apr 2019 19:44:39 +0200
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> On 2019-04-22 17:52, Mattias Rönnblom wrote:
> > On 2019-04-22 13:34, Neil Horman wrote:
> >
> >>> +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
> >>
> >
> > I'll remove the experimental tag and move it into the 19_05 section
> > (without suggesting it should go into 19.05). That maneuver seems not to
> > trigger any build warnings/errors.
> >
>
> OK, so that wasn't true. It does trigger a build error, courtesy of
> buildtools/check-experimental-syms.sh.
>
> I can't see any obvious way around it. Ideas, anyone?
Ignore the error, the build tool is not smart enough for this kind of change.
On 2019-04-23 13:33, Neil Horman wrote:
> On Mon, Apr 22, 2019 at 07:44:39PM +0200, Mattias Rönnblom wrote:
>> On 2019-04-22 17:52, Mattias Rönnblom wrote:
>>> On 2019-04-22 13:34, Neil Horman wrote:
>>>
>>>>> +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
>>>>
>>>
>>> I'll remove the experimental tag and move it into the 19_05 section
>>> (without suggesting it should go into 19.05). That maneuver seems not to
>>> trigger any build warnings/errors.
>>>
>>
>> OK, so that wasn't true. It does trigger a build error, courtesy of
>> buildtools/check-experimental-syms.sh.
>>
>> I can't see any obvious way around it. Ideas, anyone?
>>
> No, we would have to waive it.
I don't understand. What do you mean?
> But its pretty clear that This function has been
> around forever, so I think it would be worse to demote it to an experimental
> symbol. The only thing you're doing here is moving it from an inline function
> (which is arguably part of the ABI, even if it never appeared as a symbol in the
> ELF file), to a fully fleged symbol with a new implementation.
>
I agree it shouldn't be marked experimental. The reason for doing so was
to avoid triggering a build error.
On 2019-04-23 17:31, Stephen Hemminger wrote:
> On Mon, 22 Apr 2019 19:44:39 +0200
> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
>
>> On 2019-04-22 17:52, Mattias Rönnblom wrote:
>>> On 2019-04-22 13:34, Neil Horman wrote:
>>>
>>>>> +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
>>>>
>>>
>>> I'll remove the experimental tag and move it into the 19_05 section
>>> (without suggesting it should go into 19.05). That maneuver seems not to
>>> trigger any build warnings/errors.
>>>
>>
>> OK, so that wasn't true. It does trigger a build error, courtesy of
>> buildtools/check-experimental-syms.sh.
>>
>> I can't see any obvious way around it. Ideas, anyone?
>
> Ignore the error, the build tool is not smart enough for this kind of change.
>
It stops the build.
On 2019-04-23 19:17, Mattias Rönnblom wrote:
> On 2019-04-23 17:31, Stephen Hemminger wrote:
>> On Mon, 22 Apr 2019 19:44:39 +0200
>> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
>>
>>> On 2019-04-22 17:52, Mattias Rönnblom wrote:
>>>> On 2019-04-22 13:34, Neil Horman wrote:
>>>>>> +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
>>>>
>>>> I'll remove the experimental tag and move it into the 19_05 section
>>>> (without suggesting it should go into 19.05). That maneuver seems
>>>> not to
>>>> trigger any build warnings/errors.
>>>
>>> OK, so that wasn't true. It does trigger a build error, courtesy of
>>> buildtools/check-experimental-syms.sh.
>>>
>>> I can't see any obvious way around it. Ideas, anyone?
>>
>> Ignore the error, the build tool is not smart enough for this kind of
>> change.
>>
>
> It stops the build.
OK, so what was the way of a successful build was not the
check-experimental-syms.sh script, but my incompetence. I had listed
rte_rand in both the 19_05 section, and the EXPERIMENTAL section.
On Tue, Apr 23, 2019 at 07:13:24PM +0200, Mattias Rönnblom wrote:
> On 2019-04-23 13:33, Neil Horman wrote:
> > On Mon, Apr 22, 2019 at 07:44:39PM +0200, Mattias Rönnblom wrote:
> > > On 2019-04-22 17:52, Mattias Rönnblom wrote:
> > > > On 2019-04-22 13:34, Neil Horman wrote:
> > > >
> > > > > > +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
> > > > >
> > > >
> > > > I'll remove the experimental tag and move it into the 19_05 section
> > > > (without suggesting it should go into 19.05). That maneuver seems not to
> > > > trigger any build warnings/errors.
> > > >
> > >
> > > OK, so that wasn't true. It does trigger a build error, courtesy of
> > > buildtools/check-experimental-syms.sh.
> > >
> > > I can't see any obvious way around it. Ideas, anyone?
> > >
> > No, we would have to waive it.
>
> I don't understand. What do you mean?
>
I mean we have to work around the error, understanding that its not really
experimental. My first suggestion would be to make a commit with the symbol as
experimental, than add a new commit moving it into the proper section of the
version map
> > But its pretty clear that This function has been
> > around forever, so I think it would be worse to demote it to an experimental
> > symbol. The only thing you're doing here is moving it from an inline function
> > (which is arguably part of the ABI, even if it never appeared as a symbol in the
> > ELF file), to a fully fleged symbol with a new implementation.
> >
>
> I agree it shouldn't be marked experimental. The reason for doing so was to
> avoid triggering a build error.
>
@@ -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
}
@@ -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'
)
new file mode 100644
@@ -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 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)
+{
+ 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());
+}
@@ -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
@@ -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.
@@ -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
@@ -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;
@@ -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;
};