[dpdk-dev] [RFC] eal: make rte_rand() MT safe

[dpdk-dev] [RFC] eal: make rte_rand() MT safe

[Mattias Rönnblom]

The rte_rand() documentation left it unspecified if the rte_rand() was
multi-thread safe or not, and the implementation (based on lrand48())
was not.

This commit makes rte_rand() safe to use from any lcore thread by
using lrand48_r() and per-lcore random state structs. Besides the
obvious improvement in terms of correctness (for concurrent users),
this also much improves rte_rand() performance, since the threads no
longer shares state. For the single-threaded case, this patch causes
~10% rte_rand() performance degradation.

rte_srand() is left multi-thread unsafe, and external synchronization
is required to serialize rte_sand() calls from different lcore
threads, and a rte_srand() call with rte_rand() calls made by other
lcore threads.

The assumption is that the random number generators will be seeded
once, during startup.

Bugzilla ID: 114

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         | 65 ++++++++++++++++++++++
 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, 80 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..9d519d03b
--- /dev/null
+++ b/lib/librte_eal/common/rte_random.c
@@ -0,0 +1,65 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2010-2014 Intel Corporation
+ * 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_data
+{
+	struct drand48_data data;
+} __rte_cache_aligned;
+
+static struct rte_rand_data rand_data[RTE_MAX_LCORE];
+
+void
+rte_srand(uint64_t seedval)
+{
+	unsigned i;
+
+	/* give the different lcores a different seed, to avoid a
+	   situation where they generate the same sequence */
+	for (i = 0; i < RTE_MAX_LCORE; i++)
+		srand48_r((long)seedval + i, &rand_data[i].data);
+}
+
+static inline uint32_t
+__rte_rand48(struct drand48_data *data)
+{
+	long res;
+
+	lrand48_r(data, &res);
+
+	return (uint32_t)res;
+}
+
+uint64_t
+rte_rand(void)
+{
+	unsigned lcore_id;
+	struct drand48_data *data;
+	uint64_t val;
+
+	lcore_id = rte_lcore_id();
+
+	if (unlikely(lcore_id == LCORE_ID_ANY))
+		lcore_id = rte_get_master_lcore();
+
+	data = &rand_data[lcore_id].data;
+
+	val = __rte_rand48(data);
+	val <<= 32;
+	val += __rte_rand48(data);
+
+	return val;
+}
+
+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

Re: [dpdk-dev] [RFC] eal: make rte_rand() MT safe

[Mattias Rönnblom]

On 2019-04-05 15:45, Mattias Rönnblom wrote:
> The rte_rand() documentation left it unspecified if the rte_rand() was
> multi-thread safe or not, and the implementation (based on lrand48())
> was not.
> 
> This commit makes rte_rand() safe to use from any lcore thread by
> using lrand48_r() and per-lcore random state structs. Besides the
> obvious improvement in terms of correctness (for concurrent users),
> this also much improves rte_rand() performance, since the threads no
> longer shares state. For the single-threaded case, this patch causes
> ~10% rte_rand() performance degradation.
> 

It's a little unclear to me, if lrand48_r() exists in FreeBSD or not. 
Could someone confirm?

Another question I have is in which section of the version.map file the 
new symbols should go. Experimental, or 19.05?

The source interface is backward compatible, but the functions are no 
longer inline functions in the header file, and thus needs to go 
somewhere to be properly exported.

Re: [dpdk-dev] [RFC] eal: make rte_rand() MT safe

[Bruce Richardson]

On Fri, Apr 05, 2019 at 03:51:39PM +0200, Mattias Rönnblom wrote:
> On 2019-04-05 15:45, Mattias Rönnblom wrote:
> > The rte_rand() documentation left it unspecified if the rte_rand() was
> > multi-thread safe or not, and the implementation (based on lrand48())
> > was not.
> > 
> > This commit makes rte_rand() safe to use from any lcore thread by
> > using lrand48_r() and per-lcore random state structs. Besides the
> > obvious improvement in terms of correctness (for concurrent users),
> > this also much improves rte_rand() performance, since the threads no
> > longer shares state. For the single-threaded case, this patch causes
> > ~10% rte_rand() performance degradation.
> > 
> 
> It's a little unclear to me, if lrand48_r() exists in FreeBSD or not. Could
> someone confirm?
>
Nothing shows up for me in the man pages for such a function on FreeBSD 12,
so I suspect they aren't available.
 
> Another question I have is in which section of the version.map file the new
> symbols should go. Experimental, or 19.05?
> 
I think it should be 19.05. Since the APIs have been around as inline
functions for some time now, I don't see the point of having them be
experimental for a time.

> The source interface is backward compatible, but the functions are no longer
> inline functions in the header file, and thus needs to go somewhere to be
> properly exported.

Regards,
/Bruce

Re: [dpdk-dev] [RFC] eal: make rte_rand() MT safe

[Mattias Rönnblom]

On 2019-04-05 16:28, Bruce Richardson wrote:
> On Fri, Apr 05, 2019 at 03:51:39PM +0200, Mattias Rönnblom wrote:
>> On 2019-04-05 15:45, Mattias Rönnblom wrote:
>>> The rte_rand() documentation left it unspecified if the rte_rand() was
>>> multi-thread safe or not, and the implementation (based on lrand48())
>>> was not.
>>>
>>> This commit makes rte_rand() safe to use from any lcore thread by
>>> using lrand48_r() and per-lcore random state structs. Besides the
>>> obvious improvement in terms of correctness (for concurrent users),
>>> this also much improves rte_rand() performance, since the threads no
>>> longer shares state. For the single-threaded case, this patch causes
>>> ~10% rte_rand() performance degradation.
>>>
>>
>> It's a little unclear to me, if lrand48_r() exists in FreeBSD or not. Could
>> someone confirm?
>>
> Nothing shows up for me in the man pages for such a function on FreeBSD 12,
> so I suspect they aren't available.
>   

Could arc4random(3) be a good replacement on FreeBSD? It "can be called 
in almost all coding environments, including pthreads(3)" according to 
the man page, so assume it's MT safe.

Re: [dpdk-dev] [RFC] eal: make rte_rand() MT safe

[Stephen Hemminger]

On Fri, 5 Apr 2019 15:45:42 +0200
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:

> The rte_rand() documentation left it unspecified if the rte_rand() was
> multi-thread safe or not, and the implementation (based on lrand48())
> was not.
> 
> This commit makes rte_rand() safe to use from any lcore thread by
> using lrand48_r() and per-lcore random state structs. Besides the
> obvious improvement in terms of correctness (for concurrent users),
> this also much improves rte_rand() performance, since the threads no
> longer shares state. For the single-threaded case, this patch causes
> ~10% rte_rand() performance degradation.
> 
> rte_srand() is left multi-thread unsafe, and external synchronization
> is required to serialize rte_sand() calls from different lcore
> threads, and a rte_srand() call with rte_rand() calls made by other
> lcore threads.
> 
> The assumption is that the random number generators will be seeded
> once, during startup.
> 
> Bugzilla ID: 114
> 
> 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         | 65 ++++++++++++++++++++++
>  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, 80 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..9d519d03b
> --- /dev/null
> +++ b/lib/librte_eal/common/rte_random.c
> @@ -0,0 +1,65 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2010-2014 Intel Corporation
> + * 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_data
> +{
> +	struct drand48_data data;
> +} __rte_cache_aligned;
> +
> +static struct rte_rand_data rand_data[RTE_MAX_LCORE];
> +
> +void
> +rte_srand(uint64_t seedval)
> +{
> +	unsigned i;
> +
> +	/* give the different lcores a different seed, to avoid a
> +	   situation where they generate the same sequence */
> +	for (i = 0; i < RTE_MAX_LCORE; i++)
> +		srand48_r((long)seedval + i, &rand_data[i].data);
> +}
> +
> +static inline uint32_t
> +__rte_rand48(struct drand48_data *data)
> +{
> +	long res;
> +
> +	lrand48_r(data, &res);
> +
> +	return (uint32_t)res;
> +}
> +
> +uint64_t
> +rte_rand(void)
> +{
> +	unsigned lcore_id;
> +	struct drand48_data *data;
> +	uint64_t val;
> +
> +	lcore_id = rte_lcore_id();
> +
> +	if (unlikely(lcore_id == LCORE_ID_ANY))
> +		lcore_id = rte_get_master_lcore();
> +
> +	data = &rand_data[lcore_id].data;
> +
> +	val = __rte_rand48(data);
> +	val <<= 32;
> +	val += __rte_rand48(data);
> +
> +	return val;
> +}
> +
> +RTE_INIT(rte_rand_init)
> +{
> +	rte_srand(rte_get_timer_cycles());
> +}

rand48 is a terrible PRNG, why not use something better?

Similar discussion in Linux kernel pointed at:
http://www.pcg-random.org/posts/some-prng-implementations.html

Mail thread here:
https://www.spinics.net/lists/netdev/msg560231.html

Re: [dpdk-dev] [RFC] eal: make rte_rand() MT safe

[Mattias Rönnblom]

On 2019-04-05 18:57, Stephen Hemminger wrote:
> 
> rand48 is a terrible PRNG, why not use something better?
> 
> Similar discussion in Linux kernel pointed at:
> http://www.pcg-random.org/posts/some-prng-implementations.html
> 
> Mail thread here:
> https://www.spinics.net/lists/netdev/msg560231.html
> 

DPDK was already using lrand48(), I primarily wanted to address 
lrand48()'s lack of MT safety, nothing else.

That said, maybe the easiest way to maintain the current API, provide MT 
safety and have something portable is for DPDK to carry its own random 
number generator, instead of relying on libc.

Maybe an ARC4 port from BSD? But instead of pulling entropy from the 
kernel, let the user give the seed, like the current DPDK APIs permit.

You could deprecate rte_srand(), but I would vote against such a move, 
because its sometimes useful to able to have something that is "random", 
yet reproducible.

Re: [dpdk-dev] [RFC] eal: make rte_rand() MT safe

[Stephen Hemminger]

On Fri, 5 Apr 2019 20:04:28 +0200
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:

> On 2019-04-05 18:57, Stephen Hemminger wrote:
> > 
> > rand48 is a terrible PRNG, why not use something better?
> > 
> > Similar discussion in Linux kernel pointed at:
> > http://www.pcg-random.org/posts/some-prng-implementations.html
> > 
> > Mail thread here:
> > https://www.spinics.net/lists/netdev/msg560231.html
> >   
> 
> DPDK was already using lrand48(), I primarily wanted to address 
> lrand48()'s lack of MT safety, nothing else.
> 
> That said, maybe the easiest way to maintain the current API, provide MT 
> safety and have something portable is for DPDK to carry its own random 
> number generator, instead of relying on libc.
> 
> Maybe an ARC4 port from BSD? But instead of pulling entropy from the 
> kernel, let the user give the seed, like the current DPDK APIs permit.
> 
> You could deprecate rte_srand(), but I would vote against such a move, 
> because its sometimes useful to able to have something that is "random", 
> yet reproducible.

Read the discussion link about ARC4. http://www.pcg-random.org/

	As a general-purpose PRNG, it is rather slow, and it is also slow by
	the standards of modern cryptographic PRNGs and is also considered too
	weak to use for cryptographic purposes. It is, however, of historical
	interest and can be useful in testing to see how sensitive a algorithms
	are to PRNG speed.

Using ARC4 replaces a one legacy one with another.

Re: [dpdk-dev] [RFC] eal: make rte_rand() MT safe

[Mattias Rönnblom]

On 2019-04-05 22:50, Stephen Hemminger wrote:
> 
> Read the discussion link about ARC4. http://www.pcg-random.org/
> 
> 	As a general-purpose PRNG, it is rather slow, and it is also slow by
> 	the standards of modern cryptographic PRNGs and is also considered too
> 	weak to use for cryptographic purposes. It is, however, of historical
> 	interest and can be useful in testing to see how sensitive a algorithms
> 	are to PRNG speed.
> 
> Using ARC4 replaces a one legacy one with another.
> 

Yes, I agree.

After looking at the code, I learned that - seemingly - most 
arc4random() implementations aren't using ARC4, but ChaCha.

Would it be unfortunate from a export control point of view to include 
cipher-based random generators in DPDK?

[dpdk-dev] [RFC 1/3] Replace lrand48-based rte_rand with LFSR generator

[Mattias Rönnblom]

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

[dpdk-dev] [RFC 2/3] Add 32-bit version of rte_rand

[Mattias Rönnblom]

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/include/rte_random.h | 15 +++++++++++----
 lib/librte_eal/common/rte_random.c         | 10 ++++++++++
 lib/librte_eal/rte_eal_version.map         |  1 +
 3 files changed, 22 insertions(+), 4 deletions(-)

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index bca85a672..a96fc7f96 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -35,11 +35,18 @@ void
 rte_srand(uint64_t seedval);
 
 /**
- * Get a pseudo-random value.
+ * Generates a 32-bit pseudo-random number.
  *
- * This function generates pseudo-random numbers using the linear
- * 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<<32)-1.
+ */
+uint32_t
+rte_rand32(void);
+
+/**
+ * Generates a 64-bit pseudo-random number.
  *
  * If called from lcore threads, this function is thread-safe.
  *
diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index b8fb7006e..c6dac2fc7 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -83,6 +83,16 @@ struct rte_rand_state *__rte_rand_get_state(void)
 	return &rand_states[lcore_id];
 }
 
+uint32_t __rte_experimental
+rte_rand32(void)
+{
+	struct rte_rand_state *state;
+
+	state = __rte_rand_get_state();
+
+	return __rte_rand32(state);
+}
+
 uint64_t __rte_experimental
 rte_rand(void)
 {
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index 0d60668fa..027a22fe5 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -366,6 +366,7 @@ EXPERIMENTAL {
 	rte_mp_request_async;
 	rte_mp_sendmsg;
 	rte_option_register;
+	rte_rand32;
 	rte_rand;
 	rte_realloc_socket;
 	rte_service_lcore_attr_get;
-- 
2.17.1

[dpdk-dev] [RFC 3/3] Introduce random generator functions with upper bound

[Mattias Rönnblom]

Add two functions rte_rand32_max() and rte_rand_max(), which generate
uniformly distributed pseudo-random number less than a user-specified
upper bound.

The commonly used pattern rte_rand() % SOME_VALUE, in addition to
being slow, also creates biased results if SOME_VALUE is not a power
of 2. This bias is very small for small SOME_VALUE, but increases
linearly with larger SOME_VALUE.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/include/rte_random.h | 32 +++++++++++++++++
 lib/librte_eal/common/rte_random.c         | 40 ++++++++++++++++++++++
 lib/librte_eal/rte_eal_version.map         |  2 ++
 3 files changed, 74 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index a96fc7f96..b560b0a0d 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -45,6 +45,22 @@ rte_srand(uint64_t seedval);
 uint32_t
 rte_rand32(void);
 
+/**
+ * Generates an 32-bit pseudo-random number less than upper_bound.
+ *
+ * This function returns an uniformly distributed (unbiased) random
+ * number lower than a user-specified maximum value.
+ *
+ * If called from lcore threads, this function is thread-safe.
+ *
+ * @param upper_bound
+ *   The upper bound of the generated number.
+ * @return
+ *   A pseudo-random value between 0 and (upper_bound-1).
+ */
+uint32_t
+rte_rand32_max(uint32_t upper_bound);
+
 /**
  * Generates a 64-bit pseudo-random number.
  *
@@ -56,6 +72,22 @@ rte_rand32(void);
 uint64_t
 rte_rand(void);
 
+/**
+ * Generates an 64-bit pseudo-random number less than upper_bound.
+ *
+ * This function returns an uniformly distributed (unbiased) random
+ * number lower than a user-specified maximum value.
+ *
+ * If called from lcore threads, this function is thread-safe.
+ *
+ * @param upper_bound
+ *   The upper bound of the generated number.
+ * @return
+ *   A pseudo-random value between 0 and (upper_bound-1).
+ */
+uint64_t
+rte_rand_max(uint64_t upper_bound);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index c6dac2fc7..67d07d3ff 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -93,6 +93,26 @@ rte_rand32(void)
 	return __rte_rand32(state);
 }
 
+uint32_t __rte_experimental
+rte_rand32_max(uint32_t upper_bound)
+{
+	uint32_t mask = ~((uint32_t)0);
+	uint8_t zeros;
+	uint32_t res;
+
+	if (upper_bound < 2)
+		return 0;
+
+	zeros = __builtin_clz(upper_bound);
+	mask >>= zeros;
+
+	do {
+		res = rte_rand32() & mask;
+	} while (unlikely(res >= upper_bound));
+
+	return res;
+}
+
 uint64_t __rte_experimental
 rte_rand(void)
 {
@@ -108,6 +128,26 @@ rte_rand(void)
 	return low | (high << 32);
 }
 
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound)
+{
+	uint64_t mask = ~((uint64_t)0);
+	uint8_t zeros;
+	uint64_t res;
+
+	if (upper_bound < 2)
+		return 0;
+
+	zeros = __builtin_clzll(upper_bound);
+	mask >>= zeros;
+
+	do {
+		res = rte_rand() & mask;
+	} while (unlikely(res >= upper_bound));
+
+	return res;
+}
+
 RTE_INIT(rte_rand_init)
 {
 	rte_srand(rte_get_timer_cycles());
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index 027a22fe5..abdacb217 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -367,7 +367,9 @@ EXPERIMENTAL {
 	rte_mp_sendmsg;
 	rte_option_register;
 	rte_rand32;
+	rte_rand32_max;
 	rte_rand;
+	rte_rand_max;
 	rte_realloc_socket;
 	rte_service_lcore_attr_get;
 	rte_service_lcore_attr_reset_all;
-- 
2.17.1

Re: [dpdk-dev] [RFC 1/3] Replace lrand48-based rte_rand with LFSR generator

[Mattias Rönnblom]

On 2019-04-08 14:30, Mattias Rönnblom wrote:

> +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)

How do I best avoid around having this function marked as experimental?

If I removed the attribute, the compilation will fail (because of 
check-symbol-change.sh rules).

[dpdk-dev] [RFC v2 0/2] Pseudo-number generation improvements

[Mattias Rönnblom]

Make rte_rand() multi-thread safe, go faster and produce
better-quality pseudo-random numbers.

v2:
* Removed 32-bit version of rte_rand() and rte_rand_max().
* Switched from a four-sequence LFSR (producing a 32-bit number)
  to a five-sequence LFSR (producing a 64-bit number).
* Added a note on generator not being cryptographically secure.

Mattias Rönnblom (2):
  eal: replace libc-based random number generation with LFSR
  eal: introduce random generator function with upper bound

 lib/librte_eal/common/include/rte_random.h |  45 +++---
 lib/librte_eal/common/meson.build          |   1 +
 lib/librte_eal/common/rte_random.c         | 157 +++++++++++++++++++++
 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         |   3 +
 8 files changed, 190 insertions(+), 22 deletions(-)
 create mode 100644 lib/librte_eal/common/rte_random.c

-- 
2.17.1

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

[Mattias Rönnblom]

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)
+{
+	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;
 };
-- 
2.17.1

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

[Neil Horman]

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;
>  };

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

[Stephen Hemminger]

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.

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

[Mattias Rönnblom]

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.

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

[Mattias Rönnblom]

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?

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

[Neil Horman]

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

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

[Mattias Rönnblom]

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.

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

[Neil Horman]

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.
> 

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

[Stephen Hemminger]

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.

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

[Mattias Rönnblom]

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.

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

[Mattias Rönnblom]

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.

[dpdk-dev] [RFC v3 0/2] Pseudo-random number generation improvements

[Mattias Rönnblom]

Make rte_rand() multi-thread safe, go faster and produce
better-quality pseudo-random numbers.

Thanks to Stephen Hemminger, Keith Wiles and Neil Horman for valuable
feedback.

v3:
* Since rte_rand() and rte_srand() have been a part of the API since long,
  the experimental attribute was removed and the symbols were moved out
  of the experimental section of the version.map file.
* rte_rand_max() performance improvements:
  * Avoid repeated rte_lcore_id() calls.
  * Handle a power-of-2 upper bound as a special case.
* Added a Bugzilla reference to the rte_rand() MT safety bug.

v2:
* Removed 32-bit version of rte_rand() and rte_rand_max().
* Switched from a four-sequence LFSR (producing a 32-bit number)
  to a five-sequence LFSR (producing a 64-bit number).
* Added a note on generator not being cryptographically secure.

Mattias Rönnblom (2):
  eal: replace libc-based random number generation with LFSR
  eal: introduce random generator function with upper bound

 lib/librte_eal/common/include/rte_random.h |  45 +++---
 lib/librte_eal/common/meson.build          |   1 +
 lib/librte_eal/common/rte_random.c         | 176 +++++++++++++++++++++
 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         |   3 +
 8 files changed, 209 insertions(+), 22 deletions(-)
 create mode 100644 lib/librte_eal/common/rte_random.c

-- 
2.17.1

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

[Mattias Rönnblom]

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

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

[Stephen Hemminger]

On Wed, 24 Apr 2019 14:33:19 +0200
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:

> 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());

The current model of seeding with TSC will have problems at scale.
If a whole rack of machines reboots at the same time because of power cycle,
it would not be surprising if several had the same TSC value.

A better solution would be to use the get_random() system call to get
seed, the kernel can get entropy from more sources.

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

[Mattias Rönnblom]

On 2019-05-08 22:12, Stephen Hemminger wrote:
> On Wed, 24 Apr 2019 14:33:19 +0200
> Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> 
>> 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());
> 
> The current model of seeding with TSC will have problems at scale.
> If a whole rack of machines reboots at the same time because of power cycle,
> it would not be surprising if several had the same TSC value.
> 
> A better solution would be to use the get_random() system call to get
> seed, the kernel can get entropy from more sources.
> 

Sounds reasonable.

What version of FreeBSD is DPDK supposed to support? getrandom(2) (and 
its cousin getentropy(3)) seem not be available until FreeBSD 12.

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

[Stephen Hemminger]

On Wed, 8 May 2019 22:30:00 +0200
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:

> On 2019-05-08 22:12, Stephen Hemminger wrote:
> > On Wed, 24 Apr 2019 14:33:19 +0200
> > Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> >   
> >> 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());  
> > 
> > The current model of seeding with TSC will have problems at scale.
> > If a whole rack of machines reboots at the same time because of power cycle,
> > it would not be surprising if several had the same TSC value.
> > 
> > A better solution would be to use the get_random() system call to get
> > seed, the kernel can get entropy from more sources.
> >   
> 
> Sounds reasonable.
> 
> What version of FreeBSD is DPDK supposed to support? getrandom(2) (and 
> its cousin getentropy(3)) seem not be available until FreeBSD 12.

Linux has had it since 3.17 but you often need a syscall wrapper.
Or just read /dev/urandom.

[dpdk-dev] [PATCH 0/6] Pseudo-random number generation improvements

[Mattias Rönnblom]

Make DPDK pseudo-random number generation multi-thread safe, go faster
and produce better-quality pseudo-random numbers.

Thanks to Stephen Hemminger, Keith Wiles and Neil Horman for valuable
feedback.

PATCH v1:
* Added performance tests
* Added __experimental to rte_rand_max() declaration
* Introduced a PRNG section in the MAINTAINERS file
* Added missing <rte_memory.h> include
* Use getentropy() instead of rdtsc for seeding the internal LCG

RFC v3:
* Since rte_rand() and rte_srand() have been a part of the API since long,
  the experimental attribute was removed and the symbols were moved out
  of the experimental section of the version.map file.
* rte_rand_max() performance improvements:
  * Avoid repeated rte_lcore_id() calls.
  * Handle a power-of-2 upper bound as a special case.
* Added a Bugzilla reference to the rte_rand() MT safety bug.

RFC v2:
* Removed 32-bit version of rte_rand() and rte_rand_max().
* Switched from a four-sequence LFSR (producing a 32-bit number)
  to a five-sequence LFSR (producing a 64-bit number).
* Added a note on generator not being cryptographically secure.

Mattias Rönnblom (6):
  eal: replace libc-based random number generation with LFSR
  eal: add pseudo-random number generation performance test
  eal: improve entropy for initial PRNG seed
  eal: introduce random generator function with upper bound
  eal: add bounded PRNG performance tests
  eal: add pseudo-random number generation to MAINTAINERS

 MAINTAINERS                                |   6 +
 app/test/Makefile                          |   1 +
 app/test/test_rand_perf.c                  |  92 ++++++++++
 lib/librte_eal/common/include/rte_random.h |  47 ++++--
 lib/librte_eal/common/meson.build          |   1 +
 lib/librte_eal/common/rte_random.c         | 188 +++++++++++++++++++++
 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         |   9 +
 11 files changed, 328 insertions(+), 22 deletions(-)
 create mode 100644 app/test/test_rand_perf.c
 create mode 100644 lib/librte_eal/common/rte_random.c

-- 
2.17.1

[dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR

[Mattias Rönnblom]

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

This generator is faster and produces better-quality random numbers
than the linear congruential generator (LCG) of lib's lrand48(). The
implementation, as opposed to lrand48(), is multi-thread safe in
regards to concurrent rte_rand() calls from different lcore threads.
A LCG is still used, but only to seed the five per-lcore LFSR
sequences.

In addition, this patch also addresses the issue of the legacy
implementation only producing 62 bits of pseudo randomness, while the
API requires all 64 bits to be random.

This pseudo-random number generator is not cryptographically secure -
just like lrand48().

Bugzilla ID: 114
Bugzilla ID: 276

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         | 139 +++++++++++++++++++++
 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         |   8 ++
 8 files changed, 161 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..4d3cf5226
--- /dev/null
+++ b/lib/librte_eal/common/rte_random.c
@@ -0,0 +1,139 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <stdlib.h>
+
+#include <rte_branch_prediction.h>
+#include <rte_cycles.h>
+#include <rte_eal.h>
+#include <rte_lcore.h>
+#include <rte_memory.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..e615d7cb9 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -287,6 +287,14 @@ DPDK_19.05 {
 
 } DPDK_18.11;
 
+DPDK_19.08 {
+	global:
+
+	rte_rand;
+	rte_srand;
+
+} DPDK_19.05;
+
 EXPERIMENTAL {
 	global:
 
-- 
2.17.1

Re: [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR

[Mattias Rönnblom]

On 2019-05-14 11:20, Mattias Rönnblom wrote:
>
> Bugzilla ID: 114
> Bugzilla ID: 276
> 

I don't know which, if any, of these bugs you want to address in any 
stable releases.

If fixing bug 276 "rte_rand() bit 31 and 63 are always zero" is enough, 
then one could either split this patch set in two (w/ only the new 
rte_rand() going into stable), or develop a smaller fix based on lrand48().

Since the old implementation was an inline function, any fix will 
require a recompilation.

Re: [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR

[Neil Horman]

On Tue, May 14, 2019 at 11:20:41AM +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-random number generator.
> 
> This generator is faster and produces better-quality random numbers
> than the linear congruential generator (LCG) of lib's lrand48(). The
> implementation, as opposed to lrand48(), is multi-thread safe in
> regards to concurrent rte_rand() calls from different lcore threads.
> A LCG is still used, but only to seed the five per-lcore LFSR
> sequences.
> 
> In addition, this patch also addresses the issue of the legacy
> implementation only producing 62 bits of pseudo randomness, while the
> API requires all 64 bits to be random.
> 
> This pseudo-random number generator is not cryptographically secure -
> just like lrand48().
> 
> Bugzilla ID: 114
> Bugzilla ID: 276
> 
> 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         | 139 +++++++++++++++++++++
>  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         |   8 ++
>  8 files changed, 161 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..4d3cf5226
> --- /dev/null
> +++ b/lib/librte_eal/common/rte_random.c
> @@ -0,0 +1,139 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2019 Ericsson AB
> + */
> +
> +#include <stdlib.h>
> +
> +#include <rte_branch_prediction.h>
> +#include <rte_cycles.h>
> +#include <rte_eal.h>
> +#include <rte_lcore.h>
> +#include <rte_memory.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];
> +

It just occured to me that this variable embodies all the state of the rng.
Whats to stop an attacker from digging through ram to get this info and
predicting what the output will be?  I understand that this rng probably
shouldn't be considered secure for cryptographic use, but it is used in the
ipsec test example, so it could be mistaken for an rng that is.

Neil

> 

Re: [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR

[Mattias Rönnblom]

On 2019-05-14 16:16, Neil Horman wrote:
> On Tue, May 14, 2019 at 11:20:41AM +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-random number generator.
>>
>> This generator is faster and produces better-quality random numbers
>> than the linear congruential generator (LCG) of lib's lrand48(). The
>> implementation, as opposed to lrand48(), is multi-thread safe in
>> regards to concurrent rte_rand() calls from different lcore threads.
>> A LCG is still used, but only to seed the five per-lcore LFSR
>> sequences.
>>
>> In addition, this patch also addresses the issue of the legacy
>> implementation only producing 62 bits of pseudo randomness, while the
>> API requires all 64 bits to be random.
>>
>> This pseudo-random number generator is not cryptographically secure -
>> just like lrand48().
>>
>> Bugzilla ID: 114
>> Bugzilla ID: 276
>>
>> 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         | 139 +++++++++++++++++++++
>>   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         |   8 ++
>>   8 files changed, 161 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..4d3cf5226
>> --- /dev/null
>> +++ b/lib/librte_eal/common/rte_random.c
>> @@ -0,0 +1,139 @@
>> +/* SPDX-License-Identifier: BSD-3-Clause
>> + * Copyright(c) 2019 Ericsson AB
>> + */
>> +
>> +#include <stdlib.h>
>> +
>> +#include <rte_branch_prediction.h>
>> +#include <rte_cycles.h>
>> +#include <rte_eal.h>
>> +#include <rte_lcore.h>
>> +#include <rte_memory.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];
>> +
> 
> It just occured to me that this variable embodies all the state of the rng.
> Whats to stop an attacker from digging through ram to get this info and
> predicting what the output will be?  I understand that this rng probably
> shouldn't be considered secure for cryptographic use, but it is used in the
> ipsec test example, so it could be mistaken for an rng that is.
> 

rte_rand() was never safe for use in cryptography, and now it's spelled 
out in the API documentation.

If the IPsec example uses rte_rand() for anything security-related, it's 
a bug or at least should be accompanied by a comment, in my opinion.

That said, if you have an attacker who's already broken into your DPDK 
process' virtual memory, I'm not sure I understand why he would care 
much about the state of the PRNG. Wouldn't he just read your private 
keys, your messages in clear text or whatever other secrets you might 
have in memory?

Re: [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR

[Neil Horman]

On Tue, May 14, 2019 at 04:53:08PM +0200, Mattias Rönnblom wrote:
> On 2019-05-14 16:16, Neil Horman wrote:
> > On Tue, May 14, 2019 at 11:20:41AM +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-random number generator.
> > > 
> > > This generator is faster and produces better-quality random numbers
> > > than the linear congruential generator (LCG) of lib's lrand48(). The
> > > implementation, as opposed to lrand48(), is multi-thread safe in
> > > regards to concurrent rte_rand() calls from different lcore threads.
> > > A LCG is still used, but only to seed the five per-lcore LFSR
> > > sequences.
> > > 
> > > In addition, this patch also addresses the issue of the legacy
> > > implementation only producing 62 bits of pseudo randomness, while the
> > > API requires all 64 bits to be random.
> > > 
> > > This pseudo-random number generator is not cryptographically secure -
> > > just like lrand48().
> > > 
> > > Bugzilla ID: 114
> > > Bugzilla ID: 276
> > > 
> > > 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         | 139 +++++++++++++++++++++
> > >   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         |   8 ++
> > >   8 files changed, 161 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..4d3cf5226
> > > --- /dev/null
> > > +++ b/lib/librte_eal/common/rte_random.c
> > > @@ -0,0 +1,139 @@
> > > +/* SPDX-License-Identifier: BSD-3-Clause
> > > + * Copyright(c) 2019 Ericsson AB
> > > + */
> > > +
> > > +#include <stdlib.h>
> > > +
> > > +#include <rte_branch_prediction.h>
> > > +#include <rte_cycles.h>
> > > +#include <rte_eal.h>
> > > +#include <rte_lcore.h>
> > > +#include <rte_memory.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];
> > > +
> > 
> > It just occured to me that this variable embodies all the state of the rng.
> > Whats to stop an attacker from digging through ram to get this info and
> > predicting what the output will be?  I understand that this rng probably
> > shouldn't be considered secure for cryptographic use, but it is used in the
> > ipsec test example, so it could be mistaken for an rng that is.
> > 
> 
> rte_rand() was never safe for use in cryptography, and now it's spelled out
> in the API documentation.
> 
> If the IPsec example uses rte_rand() for anything security-related, it's a
> bug or at least should be accompanied by a comment, in my opinion.
> 
I would agree with that, but the fact remains that the examples use rte_rand in
a context that is explicitly in violation of what you are documenting, which
certainly seems confusing.

> That said, if you have an attacker who's already broken into your DPDK
> process' virtual memory, I'm not sure I understand why he would care much
> about the state of the PRNG. Wouldn't he just read your private keys, your
> messages in clear text or whatever other secrets you might have in memory?
> 
Because the term "Breaking in" is a misnomer here.  In unix system, IIRC, global
variables are shared accross processes.  Breaking in to get this information is
as simple as writing a program that links against the dpdk shared library, or
just dlopens it and looks up the requisite symbol address.  And while thats true
of any symbol, given the prior example which uses rte_rand for a cryptographic
purpose, it seems like this would be a particularly tempting target to exploit.

Either way, asserting that its fine to do this because any method that gives you
access to it gives you access to other information is really not a great
argument.  We should protect application data wherever we can, and the integrity
of the randomness of data seems like a case in point.

Neil

Re: [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR

[Bruce Richardson]

On Fri, May 17, 2019 at 03:27:25PM -0400, Neil Horman wrote:
> On Tue, May 14, 2019 at 04:53:08PM +0200, Mattias Rönnblom wrote:
> > On 2019-05-14 16:16, Neil Horman wrote:
> > > On Tue, May 14, 2019 at 11:20:41AM +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-random number generator.
> > > > 
> > > > This generator is faster and produces better-quality random numbers
> > > > than the linear congruential generator (LCG) of lib's lrand48(). The
> > > > implementation, as opposed to lrand48(), is multi-thread safe in
> > > > regards to concurrent rte_rand() calls from different lcore threads.
> > > > A LCG is still used, but only to seed the five per-lcore LFSR
> > > > sequences.
> > > > 
> > > > In addition, this patch also addresses the issue of the legacy
> > > > implementation only producing 62 bits of pseudo randomness, while the
> > > > API requires all 64 bits to be random.
> > > > 
> > > > This pseudo-random number generator is not cryptographically secure -
> > > > just like lrand48().
> > > > 
> > > > Bugzilla ID: 114
> > > > Bugzilla ID: 276
> > > > 
> > > > 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         | 139 +++++++++++++++++++++
> > > >   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         |   8 ++
> > > >   8 files changed, 161 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..4d3cf5226
> > > > --- /dev/null
> > > > +++ b/lib/librte_eal/common/rte_random.c
> > > > @@ -0,0 +1,139 @@
> > > > +/* SPDX-License-Identifier: BSD-3-Clause
> > > > + * Copyright(c) 2019 Ericsson AB
> > > > + */
> > > > +
> > > > +#include <stdlib.h>
> > > > +
> > > > +#include <rte_branch_prediction.h>
> > > > +#include <rte_cycles.h>
> > > > +#include <rte_eal.h>
> > > > +#include <rte_lcore.h>
> > > > +#include <rte_memory.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];
> > > > +
> > > 
> > > It just occured to me that this variable embodies all the state of the rng.
> > > Whats to stop an attacker from digging through ram to get this info and
> > > predicting what the output will be?  I understand that this rng probably
> > > shouldn't be considered secure for cryptographic use, but it is used in the
> > > ipsec test example, so it could be mistaken for an rng that is.
> > > 
> > 
> > rte_rand() was never safe for use in cryptography, and now it's spelled out
> > in the API documentation.
> > 
> > If the IPsec example uses rte_rand() for anything security-related, it's a
> > bug or at least should be accompanied by a comment, in my opinion.
> > 
> I would agree with that, but the fact remains that the examples use rte_rand in
> a context that is explicitly in violation of what you are documenting, which
> certainly seems confusing.
> 
> > That said, if you have an attacker who's already broken into your DPDK
> > process' virtual memory, I'm not sure I understand why he would care much
> > about the state of the PRNG. Wouldn't he just read your private keys, your
> > messages in clear text or whatever other secrets you might have in memory?
> > 
> Because the term "Breaking in" is a misnomer here.  In unix system, IIRC, global
> variables are shared accross processes.

That doesn't seem right to me. Data variables, even globals, inside
processes are isolated from other processes unless the data is explicitly
placed in shared memory. Otherwise, what would be the point of having
shared memory areas?

Even for shared libraries, the text segment would be a single copy in
memory, but each process using the library should have it's own data area.

/Bruce

Re: [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR

[Mattias Rönnblom]

On 2019-05-17 21:27, Neil Horman wrote:

>>>> diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
>>>> new file mode 100644
>>>> index 000000000..4d3cf5226
>>>> --- /dev/null
>>>> +++ b/lib/librte_eal/common/rte_random.c
>>>> @@ -0,0 +1,139 @@
>>>> +/* SPDX-License-Identifier: BSD-3-Clause
>>>> + * Copyright(c) 2019 Ericsson AB
>>>> + */
>>>> +
>>>> +#include <stdlib.h>
>>>> +
>>>> +#include <rte_branch_prediction.h>
>>>> +#include <rte_cycles.h>
>>>> +#include <rte_eal.h>
>>>> +#include <rte_lcore.h>
>>>> +#include <rte_memory.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];
>>>> +
>>>
>>> It just occured to me that this variable embodies all the state of the rng.
>>> Whats to stop an attacker from digging through ram to get this info and
>>> predicting what the output will be?  I understand that this rng probably
>>> shouldn't be considered secure for cryptographic use, but it is used in the
>>> ipsec test example, so it could be mistaken for an rng that is.
>>>
>>
>> rte_rand() was never safe for use in cryptography, and now it's spelled out
>> in the API documentation.
>>
>> If the IPsec example uses rte_rand() for anything security-related, it's a
>> bug or at least should be accompanied by a comment, in my opinion.
>>
> I would agree with that, but the fact remains that the examples use rte_rand in
> a context that is explicitly in violation of what you are documenting, which
> certainly seems confusing.
> 
>> That said, if you have an attacker who's already broken into your DPDK
>> process' virtual memory, I'm not sure I understand why he would care much
>> about the state of the PRNG. Wouldn't he just read your private keys, your
>> messages in clear text or whatever other secrets you might have in memory?
>>
> Because the term "Breaking in" is a misnomer here.  In unix system, IIRC, global
> variables are shared accross processes.

Mutable data, like the BSS section where the PRNG state goes, is not shared.

Does a srand48() call in one process reseed lrand48() PRNGs in all other 
processes in the system? No.

> Breaking in to get this information is
> as simple as writing a program that links against the dpdk shared library, or
> just dlopens it and looks up the requisite symbol address.

Two programs using the same shared object do share memory, but the 
portions shared are either read-only or copy-on-write (which means 
modified pages will be private to the process).

It's even the case that with address space layout randomization (ASLR), 
the address of the same symbol varies across different processes.

> And while thats true
> of any symbol, given the prior example which uses rte_rand for a cryptographic
> purpose, it seems like this would be a particularly tempting target to exploit.
> > Either way, asserting that its fine to do this because any method 
that gives you
> access to it gives you access to other information is really not a great
> argument.  We should protect application data wherever we can, and the integrity
> of the randomness of data seems like a case in point.

UNIX virtual memory and MMU memory protection is already protecting this 
data, and has been doing so for the last 30-40 years or so.

Re: [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR

[Neil Horman]

On Fri, May 17, 2019 at 11:10:25PM +0200, Mattias Rönnblom wrote:
> On 2019-05-17 21:27, Neil Horman wrote:
> 
> > > > > diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> > > > > new file mode 100644
> > > > > index 000000000..4d3cf5226
> > > > > --- /dev/null
> > > > > +++ b/lib/librte_eal/common/rte_random.c
> > > > > @@ -0,0 +1,139 @@
> > > > > +/* SPDX-License-Identifier: BSD-3-Clause
> > > > > + * Copyright(c) 2019 Ericsson AB
> > > > > + */
> > > > > +
> > > > > +#include <stdlib.h>
> > > > > +
> > > > > +#include <rte_branch_prediction.h>
> > > > > +#include <rte_cycles.h>
> > > > > +#include <rte_eal.h>
> > > > > +#include <rte_lcore.h>
> > > > > +#include <rte_memory.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];
> > > > > +
> > > > 
> > > > It just occured to me that this variable embodies all the state of the rng.
> > > > Whats to stop an attacker from digging through ram to get this info and
> > > > predicting what the output will be?  I understand that this rng probably
> > > > shouldn't be considered secure for cryptographic use, but it is used in the
> > > > ipsec test example, so it could be mistaken for an rng that is.
> > > > 
> > > 
> > > rte_rand() was never safe for use in cryptography, and now it's spelled out
> > > in the API documentation.
> > > 
> > > If the IPsec example uses rte_rand() for anything security-related, it's a
> > > bug or at least should be accompanied by a comment, in my opinion.
> > > 
> > I would agree with that, but the fact remains that the examples use rte_rand in
> > a context that is explicitly in violation of what you are documenting, which
> > certainly seems confusing.
> > 
> > > That said, if you have an attacker who's already broken into your DPDK
> > > process' virtual memory, I'm not sure I understand why he would care much
> > > about the state of the PRNG. Wouldn't he just read your private keys, your
> > > messages in clear text or whatever other secrets you might have in memory?
> > > 
> > Because the term "Breaking in" is a misnomer here.  In unix system, IIRC, global
> > variables are shared accross processes.
> 
> Mutable data, like the BSS section where the PRNG state goes, is not shared.
> 
Yes, you and bruce are right, It is shared, but marked copy on write, so
its safe from the common case of multiple programs loading the object.

Neil

> 

Re: [dpdk-dev] [PATCH 1/6] eal: replace libc-based random number generation with LFSR

[Stephen Hemminger]

On Tue, 14 May 2019 11:20:41 +0200
Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:

> +RTE_INIT(rte_rand_init)
> +{
> +	rte_srand(rte_get_timer_cycles());
> +}

Please make initialization OS specific and use get_random() on Linux.

[dpdk-dev] [PATCH 2/6] eal: add pseudo-random number generation performance test

[Mattias Rönnblom]

Add performance test for rte_rand().

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 app/test/Makefile         |  1 +
 app/test/test_rand_perf.c | 75 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 76 insertions(+)
 create mode 100644 app/test/test_rand_perf.c

diff --git a/app/test/Makefile b/app/test/Makefile
index 68d6b4fbc..be0f39227 100644
--- a/app/test/Makefile
+++ b/app/test/Makefile
@@ -73,6 +73,7 @@ SRCS-y += test_reciprocal_division.c
 SRCS-y += test_reciprocal_division_perf.c
 SRCS-y += test_fbarray.c
 SRCS-y += test_external_mem.c
+SRCS-y += test_rand_perf.c
 
 SRCS-y += test_ring.c
 SRCS-y += test_ring_perf.c
diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c
new file mode 100644
index 000000000..771713757
--- /dev/null
+++ b/app/test/test_rand_perf.c
@@ -0,0 +1,75 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <inttypes.h>
+#include <stdio.h>
+
+#include <rte_common.h>
+#include <rte_cycles.h>
+#include <rte_random.h>
+
+#include "test.h"
+
+static volatile uint64_t vsum;
+
+#define ITERATIONS (100000000)
+
+enum rand_type {
+	rand_type_64
+};
+
+static const char *
+rand_type_desc(enum rand_type rand_type)
+{
+	switch (rand_type) {
+	case rand_type_64:
+		return "Full 64-bit [rte_rand()]";
+	default:
+		return NULL;
+	}
+}
+
+static __rte_always_inline void
+test_rand_perf_type(enum rand_type rand_type)
+{
+	uint64_t start;
+	uint32_t i;
+	uint64_t end;
+	uint64_t sum = 0;
+	uint64_t op_latency;
+
+	start = rte_rdtsc();
+
+	for (i = 0; i < ITERATIONS; i++) {
+		switch (rand_type) {
+		case rand_type_64:
+			sum += rte_rand();
+			break;
+		}
+	}
+
+	end = rte_rdtsc();
+
+	/* to avoid an optimizing compiler removing the whole loop */
+	vsum = sum;
+
+	op_latency = (end - start) / ITERATIONS;
+
+	printf("%s: %"PRId64" TSC cycles/op\n", rand_type_desc(rand_type),
+	       op_latency);
+}
+
+static int
+test_rand_perf(void)
+{
+	rte_srand(42);
+
+	printf("Pseudo-random number generation latencies:\n");
+
+	test_rand_perf_type(rand_type_64);
+
+	return 0;
+}
+
+REGISTER_TEST_COMMAND(rand_perf_autotest, test_rand_perf);
-- 
2.17.1

[dpdk-dev] [PATCH 3/6] eal: improve entropy for initial PRNG seed

[Mattias Rönnblom]

Replace the use of rte_get_timer_cycles() with getentropy() for
seeding the pseudo-random number generator. getentropy() provides a
more truly random value.

Suggested-by: Stephen Hemminger <stephen@networkplumber.org>
Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/rte_random.c | 12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)

diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index 4d3cf5226..aafc2f7ad 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -3,6 +3,7 @@
  */
 
 #include <stdlib.h>
+#include <unistd.h>
 
 #include <rte_branch_prediction.h>
 #include <rte_cycles.h>
@@ -135,5 +136,14 @@ rte_rand(void)
 
 RTE_INIT(rte_rand_init)
 {
-	rte_srand(rte_get_timer_cycles());
+	uint64_t seed;
+	int rc;
+
+	rc = getentropy(&seed, sizeof(seed));
+
+	/* fall back to rdtsc in case of failure */
+	if (rc < 0)
+		seed = rte_get_timer_cycles();
+
+	rte_srand(seed);
 }
-- 
2.17.1

Re: [dpdk-dev] [PATCH 3/6] eal: improve entropy for initial PRNG seed

[Mattias Rönnblom]

On 2019-05-14 11:20, Mattias Rönnblom wrote:
> Replace the use of rte_get_timer_cycles() with getentropy() for
> seeding the pseudo-random number generator. getentropy() provides a
> more truly random value.
> 

getentropy() doens't exist in libc versions earler than 2.25, and it 
also (like Stephen mentioned) requires the getrandom() syscall not 
available until Linux 3.17.

If this is deemed too much of a limitation, I'll change to 
/dev/urandom-based seeding.

Re: [dpdk-dev] [PATCH 3/6] eal: improve entropy for initial PRNG seed

[Bruce Richardson]

On Tue, May 14, 2019 at 11:36:49AM +0200, Mattias Rönnblom wrote:
> On 2019-05-14 11:20, Mattias Rönnblom wrote:
> > Replace the use of rte_get_timer_cycles() with getentropy() for
> > seeding the pseudo-random number generator. getentropy() provides a
> > more truly random value.
> > 
> 
> getentropy() doens't exist in libc versions earler than 2.25, and it also
> (like Stephen mentioned) requires the getrandom() syscall not available
> until Linux 3.17.
> 
> If this is deemed too much of a limitation, I'll change to
> /dev/urandom-based seeding.

Since we are shifting over to meson builds more and more, I'd suggest just
using function detection there with a very basic fallback (e.g. your
time-based one) for cases where the function is not supported.

/Bruce

Re: [dpdk-dev] [PATCH 3/6] eal: improve entropy for initial PRNG seed

[Mattias Rönnblom]

On 2019-05-14 11:39, Bruce Richardson wrote:
> On Tue, May 14, 2019 at 11:36:49AM +0200, Mattias Rönnblom wrote:
>> On 2019-05-14 11:20, Mattias Rönnblom wrote:
>>> Replace the use of rte_get_timer_cycles() with getentropy() for
>>> seeding the pseudo-random number generator. getentropy() provides a
>>> more truly random value.
>>>
>>
>> getentropy() doens't exist in libc versions earler than 2.25, and it also
>> (like Stephen mentioned) requires the getrandom() syscall not available
>> until Linux 3.17.
>>
>> If this is deemed too much of a limitation, I'll change to
>> /dev/urandom-based seeding.
> 
> Since we are shifting over to meson builds more and more, I'd suggest just
> using function detection there with a very basic fallback (e.g. your
> time-based one) for cases where the function is not supported.
> 

OK, fixed. Thanks.

Would it be OK to always use the rdtsc fallback w/ make-based builds?

Re: [dpdk-dev] [PATCH 3/6] eal: improve entropy for initial PRNG seed

[Bruce Richardson]

On Tue, May 14, 2019 at 11:20:43AM +0200, Mattias Rönnblom wrote:
> Replace the use of rte_get_timer_cycles() with getentropy() for
> seeding the pseudo-random number generator. getentropy() provides a
> more truly random value.
> 
> Suggested-by: Stephen Hemminger <stephen@networkplumber.org>
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> ---
>  lib/librte_eal/common/rte_random.c | 12 +++++++++++-
>  1 file changed, 11 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> index 4d3cf5226..aafc2f7ad 100644
> --- a/lib/librte_eal/common/rte_random.c
> +++ b/lib/librte_eal/common/rte_random.c
> @@ -3,6 +3,7 @@
>   */
>  
>  #include <stdlib.h>
> +#include <unistd.h>
>  
>  #include <rte_branch_prediction.h>
>  #include <rte_cycles.h>
> @@ -135,5 +136,14 @@ rte_rand(void)
>  
>  RTE_INIT(rte_rand_init)
>  {
> -	rte_srand(rte_get_timer_cycles());
> +	uint64_t seed;
> +	int rc;
> +
> +	rc = getentropy(&seed, sizeof(seed));

This API was only introduced in FreeBSD in v12, so you may want to have a
define for enabling it, and (for meson) but in a check for
cc.has_function(get_entropy).

> +
> +	/* fall back to rdtsc in case of failure */
> +	if (rc < 0)
> +		seed = rte_get_timer_cycles();

Rather than fallback immediately to time, what about putting in a call to
HW random number generator support if available, e.g. rdseed instruction.

> +
> +	rte_srand(seed);
>  }
> -- 
> 2.17.1
> 

[dpdk-dev] [PATCH 4/6] eal: introduce random generator function with upper bound

[Mattias Rönnblom]

Add a function rte_rand_max() which generates an uniformly distributed
pseudo-random number less than a user-specified upper bound.

The commonly used pattern rte_rand() % SOME_VALUE creates biased
results (as in some values in the range are more frequently occurring
than others) if SOME_VALUE is not a power of 2.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/include/rte_random.h | 18 ++++++++++
 lib/librte_eal/common/rte_random.c         | 39 ++++++++++++++++++++++
 lib/librte_eal/rte_eal_version.map         |  1 +
 3 files changed, 58 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index 66dfe8ae7..939e6aaa9 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -17,6 +17,8 @@ extern "C" {
 
 #include <stdint.h>
 
+#include <rte_compat.h>
+
 /**
  * Seed the pseudo-random generator.
  *
@@ -47,6 +49,22 @@ rte_srand(uint64_t seedval);
 uint64_t
 rte_rand(void);
 
+/**
+ * Generates a pseudo-random number with an upper bound.
+ *
+ * This function returns an uniformly distributed (unbiased) random
+ * number less than a user-specified maximum value.
+ *
+ * If called from lcore threads, this function is thread-safe.
+ *
+ * @param upper_bound
+ *   The upper bound of the generated number.
+ * @return
+ *   A pseudo-random value between 0 and (upper_bound-1).
+ */
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index aafc2f7ad..0e8abbb1c 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -134,6 +134,45 @@ rte_rand(void)
 	return __rte_rand_lfsr258(state);
 }
 
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound)
+{
+	struct rte_rand_state *state;
+	uint8_t ones;
+	uint8_t leading_zeros;
+	uint64_t mask = ~((uint64_t)0);
+	uint64_t res;
+
+	if (unlikely(upper_bound < 2))
+		return 0;
+
+	state = __rte_rand_get_state();
+
+	ones = __builtin_popcountll(upper_bound);
+
+	/* Handle power-of-2 upper_bound as a special case, since it
+	 * has no bias issues.
+	 */
+	if (unlikely(ones == 1))
+		return __rte_rand_lfsr258(state) & (upper_bound - 1);
+
+	/* The approach to avoiding bias is to create a mask that
+	 * stretches beyond the request value range, and up to the
+	 * next power-of-2. In case the masked generated random value
+	 * is equal to or greater than the upper bound, just discard
+	 * the value and generate a new one.
+	 */
+
+	leading_zeros = __builtin_clzll(upper_bound);
+	mask >>= leading_zeros;
+
+	do {
+		res = __rte_rand_lfsr258(state) & mask;
+	} while (unlikely(res >= upper_bound));
+
+	return res;
+}
+
 RTE_INIT(rte_rand_init)
 {
 	uint64_t seed;
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index e615d7cb9..82483aed2 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -382,6 +382,7 @@ EXPERIMENTAL {
 	rte_mp_request_async;
 	rte_mp_sendmsg;
 	rte_option_register;
+	rte_rand_max;
 	rte_realloc_socket;
 	rte_service_lcore_attr_get;
 	rte_service_lcore_attr_reset_all;
-- 
2.17.1

[dpdk-dev] [PATCH 5/6] eal: add bounded PRNG performance tests

[Mattias Rönnblom]

Add best- and worst-case performance tests for rte_rand_max().

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 app/test/test_rand_perf.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c
index 771713757..fe797ebfa 100644
--- a/app/test/test_rand_perf.c
+++ b/app/test/test_rand_perf.c
@@ -15,8 +15,13 @@ static volatile uint64_t vsum;
 
 #define ITERATIONS (100000000)
 
+#define BEST_CASE_BOUND (1<<16)
+#define WORST_CASE_BOUND (BEST_CASE_BOUND + 1)
+
 enum rand_type {
-	rand_type_64
+	rand_type_64,
+	rand_type_bounded_best_case,
+	rand_type_bounded_worst_case
 };
 
 static const char *
@@ -25,6 +30,10 @@ rand_type_desc(enum rand_type rand_type)
 	switch (rand_type) {
 	case rand_type_64:
 		return "Full 64-bit [rte_rand()]";
+	case rand_type_bounded_best_case:
+		return "Bounded average best-case [rte_rand_max()]";
+	case rand_type_bounded_worst_case:
+		return "Bounded average worst-case [rte_rand_max()]";
 	default:
 		return NULL;
 	}
@@ -46,6 +55,12 @@ test_rand_perf_type(enum rand_type rand_type)
 		case rand_type_64:
 			sum += rte_rand();
 			break;
+		case rand_type_bounded_best_case:
+			sum += rte_rand_max(BEST_CASE_BOUND);
+			break;
+		case rand_type_bounded_worst_case:
+			sum += rte_rand_max(WORST_CASE_BOUND);
+			break;
 		}
 	}
 
@@ -68,6 +83,8 @@ test_rand_perf(void)
 	printf("Pseudo-random number generation latencies:\n");
 
 	test_rand_perf_type(rand_type_64);
+	test_rand_perf_type(rand_type_bounded_best_case);
+	test_rand_perf_type(rand_type_bounded_worst_case);
 
 	return 0;
 }
-- 
2.17.1

[dpdk-dev] [PATCH 6/6] eal: add pseudo-random number generation to MAINTAINERS

[Mattias Rönnblom]

Add a section on PRNG in MAINTAINERS.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 MAINTAINERS | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/MAINTAINERS b/MAINTAINERS
index 15d0829c5..d06f5da90 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -222,6 +222,12 @@ M: Joyce Kong <joyce.kong@arm.com>
 F: lib/librte_eal/common/include/generic/rte_ticketlock.h
 F: app/test/test_ticketlock.c
 
+Pseudo-random Number Generation
+M: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
+F: lib/librte_eal/common/include/rte_random.h
+F: lib/librte_eal/common/rte_random.c
+F: app/test/test_rand_perf.c
+
 ARM v7
 M: Jan Viktorin <viktorin@rehivetech.com>
 M: Gavin Hu <gavin.hu@arm.com>
-- 
2.17.1

[dpdk-dev] [PATCH v2 0/6] Pseudo-random number generation improvements

[Mattias Rönnblom]

Make DPDK pseudo-random number generation multi-thread safe, go faster
and produce better-quality pseudo-random numbers.

This patchset requires the yet-to-be-merged rdseed build detection
patch for rdseed support to be enabled.
http://patchwork.dpdk.org/patch/53404/

Thanks to Stephen Hemminger, Bruce Richardson, Keith Wiles and Neil
Horman for valuable feedback.

PATCH v2:
* Introduce the x86 rdseed machine instruction as a first fallback, in case
  getentropy() is unavailable
* Use meson to detect getentropy() and rdseed

PATCH v1:
* Added performance tests
* Added __experimental to rte_rand_max() declaration
* Introduced a PRNG section in the MAINTAINERS file
* Added missing <rte_memory.h> include
* Use getentropy() instead of rdtsc for seeding the internal LCG

RFC v3:
* Since rte_rand() and rte_srand() have been a part of the API since long,
  the experimental attribute was removed and the symbols were moved out
  of the experimental section of the version.map file.
* rte_rand_max() performance improvements:
  * Avoid repeated rte_lcore_id() calls.
  * Handle a power-of-2 upper bound as a special case.
* Added a Bugzilla reference to the rte_rand() MT safety bug.

RFC v2:
* Removed 32-bit version of rte_rand() and rte_rand_max().
* Switched from a four-sequence LFSR (producing a 32-bit number)
  to a five-sequence LFSR (producing a 64-bit number).
* Added a note on generator not being cryptographically secure.

Mattias Rönnblom (6):
  eal: replace libc-based random number generation with LFSR
  eal: add pseudo-random number generation performance test
  eal: improve entropy for initial PRNG seed
  eal: introduce random generator function with upper bound
  eal: add bounded PRNG performance tests
  eal: add PRNG to MAINTAINERS and release notes

 MAINTAINERS                                |   6 +
 app/test/Makefile                          |   1 +
 app/test/test_rand_perf.c                  |  92 +++++++++
 doc/guides/rel_notes/release_19_08.rst     |  13 ++
 lib/librte_eal/common/include/rte_random.h |  47 +++--
 lib/librte_eal/common/meson.build          |   1 +
 lib/librte_eal/common/rte_random.c         | 212 +++++++++++++++++++++
 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/meson.build                 |   3 +
 lib/librte_eal/rte_eal_version.map         |   9 +
 13 files changed, 368 insertions(+), 22 deletions(-)
 create mode 100644 app/test/test_rand_perf.c
 create mode 100644 lib/librte_eal/common/rte_random.c

-- 
2.17.1

[dpdk-dev] [PATCH v2 1/6] eal: replace libc-based random number generation with LFSR

[Mattias Rönnblom]

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

This generator is faster and produces better-quality random numbers
than the linear congruential generator (LCG) of lib's lrand48(). The
implementation, as opposed to lrand48(), is multi-thread safe in
regards to concurrent rte_rand() calls from different lcore threads.
A LCG is still used, but only to seed the five per-lcore LFSR
sequences.

In addition, this patch also addresses the issue of the legacy
implementation only producing 62 bits of pseudo randomness, while the
API requires all 64 bits to be random.

This pseudo-random number generator is not cryptographically secure -
just like lrand48().

Bugzilla ID: 114
Bugzilla ID: 276

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         | 139 +++++++++++++++++++++
 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         |   8 ++
 8 files changed, 161 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..4d3cf5226
--- /dev/null
+++ b/lib/librte_eal/common/rte_random.c
@@ -0,0 +1,139 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <stdlib.h>
+
+#include <rte_branch_prediction.h>
+#include <rte_cycles.h>
+#include <rte_eal.h>
+#include <rte_lcore.h>
+#include <rte_memory.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..e615d7cb9 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -287,6 +287,14 @@ DPDK_19.05 {
 
 } DPDK_18.11;
 
+DPDK_19.08 {
+	global:
+
+	rte_rand;
+	rte_srand;
+
+} DPDK_19.05;
+
 EXPERIMENTAL {
 	global:
 
-- 
2.17.1

[dpdk-dev] [PATCH v2 2/6] eal: add pseudo-random number generation performance test

[Mattias Rönnblom]

Add performance test for rte_rand().

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 app/test/Makefile         |  1 +
 app/test/test_rand_perf.c | 75 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 76 insertions(+)
 create mode 100644 app/test/test_rand_perf.c

diff --git a/app/test/Makefile b/app/test/Makefile
index 68d6b4fbc..be0f39227 100644
--- a/app/test/Makefile
+++ b/app/test/Makefile
@@ -73,6 +73,7 @@ SRCS-y += test_reciprocal_division.c
 SRCS-y += test_reciprocal_division_perf.c
 SRCS-y += test_fbarray.c
 SRCS-y += test_external_mem.c
+SRCS-y += test_rand_perf.c
 
 SRCS-y += test_ring.c
 SRCS-y += test_ring_perf.c
diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c
new file mode 100644
index 000000000..771713757
--- /dev/null
+++ b/app/test/test_rand_perf.c
@@ -0,0 +1,75 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <inttypes.h>
+#include <stdio.h>
+
+#include <rte_common.h>
+#include <rte_cycles.h>
+#include <rte_random.h>
+
+#include "test.h"
+
+static volatile uint64_t vsum;
+
+#define ITERATIONS (100000000)
+
+enum rand_type {
+	rand_type_64
+};
+
+static const char *
+rand_type_desc(enum rand_type rand_type)
+{
+	switch (rand_type) {
+	case rand_type_64:
+		return "Full 64-bit [rte_rand()]";
+	default:
+		return NULL;
+	}
+}
+
+static __rte_always_inline void
+test_rand_perf_type(enum rand_type rand_type)
+{
+	uint64_t start;
+	uint32_t i;
+	uint64_t end;
+	uint64_t sum = 0;
+	uint64_t op_latency;
+
+	start = rte_rdtsc();
+
+	for (i = 0; i < ITERATIONS; i++) {
+		switch (rand_type) {
+		case rand_type_64:
+			sum += rte_rand();
+			break;
+		}
+	}
+
+	end = rte_rdtsc();
+
+	/* to avoid an optimizing compiler removing the whole loop */
+	vsum = sum;
+
+	op_latency = (end - start) / ITERATIONS;
+
+	printf("%s: %"PRId64" TSC cycles/op\n", rand_type_desc(rand_type),
+	       op_latency);
+}
+
+static int
+test_rand_perf(void)
+{
+	rte_srand(42);
+
+	printf("Pseudo-random number generation latencies:\n");
+
+	test_rand_perf_type(rand_type_64);
+
+	return 0;
+}
+
+REGISTER_TEST_COMMAND(rand_perf_autotest, test_rand_perf);
-- 
2.17.1

[dpdk-dev] [PATCH v2 3/6] eal: improve entropy for initial PRNG seed

[Mattias Rönnblom]

Replace the use of rte_get_timer_cycles() with getentropy() for
seeding the pseudo-random number generator. getentropy() provides a
more truly random value.

getentropy() requires glibc 2.25 and Linux kernel 3.17. In case
getentropy() is not found at compile time, or the relevant syscall
fails in runtime, the rdseed machine instruction will be used as a
fallback.

rdseed is only available on x86 (Broadwell or later). In case it is
not present, rte_get_timer_cycles() will be used as a second fallback.

On non-Meson builds, getentropy() will not be used.

Suggested-by: Bruce Richardson <bruce.richardson@intel.com>
Suggested-by: Stephen Hemminger <stephen@networkplumber.org>
Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/rte_random.c | 36 +++++++++++++++++++++++++++++-
 lib/librte_eal/meson.build         |  3 +++
 2 files changed, 38 insertions(+), 1 deletion(-)

diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index 4d3cf5226..e53d96d18 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -2,7 +2,11 @@
  * Copyright(c) 2019 Ericsson AB
  */
 
+#ifdef RTE_MACHINE_CPUFLAG_RDSEED
+#include <x86intrin.h>
+#endif
 #include <stdlib.h>
+#include <unistd.h>
 
 #include <rte_branch_prediction.h>
 #include <rte_cycles.h>
@@ -133,7 +137,37 @@ rte_rand(void)
 	return __rte_rand_lfsr258(state);
 }
 
+static uint64_t
+__rte_random_initial_seed(void)
+{
+#ifdef RTE_LIBEAL_USE_GETENTROPY
+	int ge_rc;
+	uint64_t ge_seed;
+
+	ge_rc = getentropy(&ge_seed, sizeof(ge_seed));
+
+	if (ge_rc == 0)
+		return ge_seed;
+#endif
+#ifdef RTE_MACHINE_CPUFLAG_RDSEED
+	unsigned int rdseed_rc;
+	unsigned long long rdseed_seed;
+
+	/* first fallback: rdseed instruction, if available */
+	rdseed_rc = _rdseed64_step(&rdseed_seed);
+
+	if (rdseed_rc == 1)
+		return (uint64_t)rdseed_seed;
+#endif
+	/* second fallback: seed using rdtsc */
+	return rte_get_timer_cycles();
+}
+
 RTE_INIT(rte_rand_init)
 {
-	rte_srand(rte_get_timer_cycles());
+	uint64_t seed;
+
+	seed = __rte_random_initial_seed();
+
+	rte_srand(seed);
 }
diff --git a/lib/librte_eal/meson.build b/lib/librte_eal/meson.build
index fa36b20e0..ccd5b85b8 100644
--- a/lib/librte_eal/meson.build
+++ b/lib/librte_eal/meson.build
@@ -18,6 +18,9 @@ deps += 'kvargs'
 if dpdk_conf.has('RTE_USE_LIBBSD')
 	ext_deps += libbsd
 endif
+if cc.has_function('getentropy', prefix : '#include <unistd.h>')
+	cflags += '-DRTE_LIBEAL_USE_GETENTROPY'
+endif
 sources = common_sources + env_sources
 objs = common_objs + env_objs
 headers = common_headers + env_headers
-- 
2.17.1

[dpdk-dev] [PATCH v2 4/6] eal: introduce random generator function with upper bound

[Mattias Rönnblom]

Add a function rte_rand_max() which generates an uniformly distributed
pseudo-random number less than a user-specified upper bound.

The commonly used pattern rte_rand() % SOME_VALUE creates biased
results (as in some values in the range are more frequently occurring
than others) if SOME_VALUE is not a power of 2.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/include/rte_random.h | 18 ++++++++++
 lib/librte_eal/common/rte_random.c         | 39 ++++++++++++++++++++++
 lib/librte_eal/rte_eal_version.map         |  1 +
 3 files changed, 58 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index 66dfe8ae7..939e6aaa9 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -17,6 +17,8 @@ extern "C" {
 
 #include <stdint.h>
 
+#include <rte_compat.h>
+
 /**
  * Seed the pseudo-random generator.
  *
@@ -47,6 +49,22 @@ rte_srand(uint64_t seedval);
 uint64_t
 rte_rand(void);
 
+/**
+ * Generates a pseudo-random number with an upper bound.
+ *
+ * This function returns an uniformly distributed (unbiased) random
+ * number less than a user-specified maximum value.
+ *
+ * If called from lcore threads, this function is thread-safe.
+ *
+ * @param upper_bound
+ *   The upper bound of the generated number.
+ * @return
+ *   A pseudo-random value between 0 and (upper_bound-1).
+ */
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index e53d96d18..3d9b9b7d8 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -137,6 +137,45 @@ rte_rand(void)
 	return __rte_rand_lfsr258(state);
 }
 
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound)
+{
+	struct rte_rand_state *state;
+	uint8_t ones;
+	uint8_t leading_zeros;
+	uint64_t mask = ~((uint64_t)0);
+	uint64_t res;
+
+	if (unlikely(upper_bound < 2))
+		return 0;
+
+	state = __rte_rand_get_state();
+
+	ones = __builtin_popcountll(upper_bound);
+
+	/* Handle power-of-2 upper_bound as a special case, since it
+	 * has no bias issues.
+	 */
+	if (unlikely(ones == 1))
+		return __rte_rand_lfsr258(state) & (upper_bound - 1);
+
+	/* The approach to avoiding bias is to create a mask that
+	 * stretches beyond the request value range, and up to the
+	 * next power-of-2. In case the masked generated random value
+	 * is equal to or greater than the upper bound, just discard
+	 * the value and generate a new one.
+	 */
+
+	leading_zeros = __builtin_clzll(upper_bound);
+	mask >>= leading_zeros;
+
+	do {
+		res = __rte_rand_lfsr258(state) & mask;
+	} while (unlikely(res >= upper_bound));
+
+	return res;
+}
+
 static uint64_t
 __rte_random_initial_seed(void)
 {
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index e615d7cb9..82483aed2 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -382,6 +382,7 @@ EXPERIMENTAL {
 	rte_mp_request_async;
 	rte_mp_sendmsg;
 	rte_option_register;
+	rte_rand_max;
 	rte_realloc_socket;
 	rte_service_lcore_attr_get;
 	rte_service_lcore_attr_reset_all;
-- 
2.17.1

[dpdk-dev] [PATCH v2 5/6] eal: add bounded PRNG performance tests

[Mattias Rönnblom]

Add best- and worst-case performance tests for rte_rand_max().

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 app/test/test_rand_perf.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c
index 771713757..fe797ebfa 100644
--- a/app/test/test_rand_perf.c
+++ b/app/test/test_rand_perf.c
@@ -15,8 +15,13 @@ static volatile uint64_t vsum;
 
 #define ITERATIONS (100000000)
 
+#define BEST_CASE_BOUND (1<<16)
+#define WORST_CASE_BOUND (BEST_CASE_BOUND + 1)
+
 enum rand_type {
-	rand_type_64
+	rand_type_64,
+	rand_type_bounded_best_case,
+	rand_type_bounded_worst_case
 };
 
 static const char *
@@ -25,6 +30,10 @@ rand_type_desc(enum rand_type rand_type)
 	switch (rand_type) {
 	case rand_type_64:
 		return "Full 64-bit [rte_rand()]";
+	case rand_type_bounded_best_case:
+		return "Bounded average best-case [rte_rand_max()]";
+	case rand_type_bounded_worst_case:
+		return "Bounded average worst-case [rte_rand_max()]";
 	default:
 		return NULL;
 	}
@@ -46,6 +55,12 @@ test_rand_perf_type(enum rand_type rand_type)
 		case rand_type_64:
 			sum += rte_rand();
 			break;
+		case rand_type_bounded_best_case:
+			sum += rte_rand_max(BEST_CASE_BOUND);
+			break;
+		case rand_type_bounded_worst_case:
+			sum += rte_rand_max(WORST_CASE_BOUND);
+			break;
 		}
 	}
 
@@ -68,6 +83,8 @@ test_rand_perf(void)
 	printf("Pseudo-random number generation latencies:\n");
 
 	test_rand_perf_type(rand_type_64);
+	test_rand_perf_type(rand_type_bounded_best_case);
+	test_rand_perf_type(rand_type_bounded_worst_case);
 
 	return 0;
 }
-- 
2.17.1

[dpdk-dev] [PATCH v2 6/6] eal: add PRNG to MAINTAINERS and release notes

[Mattias Rönnblom]

Add a section on PRNG in MAINTAINERS, and information on the PRNG
improvements in the 19.08 release notes.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 MAINTAINERS                            |  6 ++++++
 doc/guides/rel_notes/release_19_08.rst | 13 +++++++++++++
 2 files changed, 19 insertions(+)

diff --git a/MAINTAINERS b/MAINTAINERS
index 15d0829c5..d06f5da90 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -222,6 +222,12 @@ M: Joyce Kong <joyce.kong@arm.com>
 F: lib/librte_eal/common/include/generic/rte_ticketlock.h
 F: app/test/test_ticketlock.c
 
+Pseudo-random Number Generation
+M: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
+F: lib/librte_eal/common/include/rte_random.h
+F: lib/librte_eal/common/rte_random.c
+F: app/test/test_rand_perf.c
+
 ARM v7
 M: Jan Viktorin <viktorin@rehivetech.com>
 M: Gavin Hu <gavin.hu@arm.com>
diff --git a/doc/guides/rel_notes/release_19_08.rst b/doc/guides/rel_notes/release_19_08.rst
index b9510f93a..62a9acf89 100644
--- a/doc/guides/rel_notes/release_19_08.rst
+++ b/doc/guides/rel_notes/release_19_08.rst
@@ -54,6 +54,19 @@ New Features
      Also, make sure to start the actual text at the margin.
      =========================================================
 
+* **Updated the EAL Pseudo-random Number Generator.**
+
+  The lrand48()-based rte_rand() function is replaced with a
+  DPDK-native combined Linear Feedback Shift Register (LFSR)
+  pseudo-random number generator (PRNG).
+
+  This new PRNG implementation is multi-thread safe, provides
+  higher-quality pseudo-random numbers (including full 64 bit
+  support) and improved performance.
+
+  In addition, <rte_random.h> is extended with a new function
+  rte_rand_max() which supplies unbiased, bounded pseudo-random
+  numbers.
 
 Removed Items
 -------------
-- 
2.17.1

Re: [dpdk-dev] [PATCH v2 0/6] Pseudo-random number generation improvements

[Bruce Richardson]

On Thu, May 16, 2019 at 07:55:04PM +0200, Mattias Rönnblom wrote:
> Make DPDK pseudo-random number generation multi-thread safe, go faster
> and produce better-quality pseudo-random numbers.
> 
> This patchset requires the yet-to-be-merged rdseed build detection
> patch for rdseed support to be enabled.
> http://patchwork.dpdk.org/patch/53404/
> 
> Thanks to Stephen Hemminger, Bruce Richardson, Keith Wiles and Neil
> Horman for valuable feedback.
> 
This looks a good improvement to have in DPDK.

Series-acked-by: Bruce Richardson <bruce.richardson@intel.com>

[dpdk-dev] [PATCH v3 0/6] Pseudo-random number generation improvements

[Mattias Rönnblom]

Fix bugs in DPDK pseudo-random number generation, make it multi-thread
safe, go faster and produce better-quality pseudo-random numbers.

Thanks to Stephen Hemminger, Bruce Richardson, Keith Wiles and Neil
Horman for valuable feedback.

PATCH v3:
* Rebase

PATCH v2:
* Introduce the x86 rdseed machine instruction as a first fallback, in case
  getentropy() is unavailable
* Use meson to detect getentropy() and rdseed

PATCH v1:
* Added performance tests
* Added __experimental to rte_rand_max() declaration
* Introduced a PRNG section in the MAINTAINERS file
* Added missing <rte_memory.h> include
* Use getentropy() instead of rdtsc for seeding the internal LCG

RFC v3:
* Since rte_rand() and rte_srand() have been a part of the API since long,
  the experimental attribute was removed and the symbols were moved out
  of the experimental section of the version.map file.
* rte_rand_max() performance improvements:
  * Avoid repeated rte_lcore_id() calls.
  * Handle a power-of-2 upper bound as a special case.
* Added a Bugzilla reference to the rte_rand() MT safety bug.

RFC v2:
* Removed 32-bit version of rte_rand() and rte_rand_max().
* Switched from a four-sequence LFSR (producing a 32-bit number)
  to a five-sequence LFSR (producing a 64-bit number).
* Added a note on generator not being cryptographically secure.

Mattias Rönnblom (6):
  eal: replace libc-based random number generation with LFSR
  eal: add pseudo-random number generation performance test
  eal: improve entropy for initial PRNG seed
  eal: introduce random generator function with upper bound
  eal: add bounded PRNG performance tests
  eal: add PRNG to MAINTAINERS and release notes

 MAINTAINERS                                |   6 +
 app/test/Makefile                          |   1 +
 app/test/test_rand_perf.c                  |  92 +++++++++
 doc/guides/rel_notes/release_19_08.rst     |  13 ++
 lib/librte_eal/common/include/rte_random.h |  47 +++--
 lib/librte_eal/common/meson.build          |   1 +
 lib/librte_eal/common/rte_random.c         | 212 +++++++++++++++++++++
 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/meson.build                 |   3 +
 lib/librte_eal/rte_eal_version.map         |   3 +
 13 files changed, 362 insertions(+), 22 deletions(-)
 create mode 100644 app/test/test_rand_perf.c
 create mode 100644 lib/librte_eal/common/rte_random.c

-- 
2.17.1

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

[Mattias Rönnblom]

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

This generator is faster and produces better-quality random numbers
than the linear congruential generator (LCG) of lib's lrand48(). The
implementation, as opposed to lrand48(), is multi-thread safe in
regards to concurrent rte_rand() calls from different lcore threads.
A LCG is still used, but only to seed the five per-lcore LFSR
sequences.

In addition, this patch also addresses the issue of the legacy
implementation only producing 62 bits of pseudo randomness, while the
API requires all 64 bits to be random.

This pseudo-random number generator is not cryptographically secure -
just like lrand48().

Bugzilla ID: 114
Bugzilla ID: 276

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 lib/librte_eal/common/include/rte_random.h |  29 ++---
 lib/librte_eal/common/meson.build          |   1 +
 lib/librte_eal/common/rte_random.c         | 139 +++++++++++++++++++++
 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, 155 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..4d3cf5226
--- /dev/null
+++ b/lib/librte_eal/common/rte_random.c
@@ -0,0 +1,139 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <stdlib.h>
+
+#include <rte_branch_prediction.h>
+#include <rte_cycles.h>
+#include <rte_eal.h>
+#include <rte_lcore.h>
+#include <rte_memory.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 824edf0ff..20c1a9018 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -292,6 +292,8 @@ DPDK_19.08 {
 
 	rte_lcore_index;
 	rte_lcore_to_socket_id;
+	rte_rand;
+	rte_srand;
 
 } DPDK_19.05;
 
-- 
2.17.1

[dpdk-dev] [PATCH v3 2/6] eal: add pseudo-random number generation performance test

[Mattias Rönnblom]

Add performance test for rte_rand().

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 app/test/Makefile         |  1 +
 app/test/test_rand_perf.c | 75 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 76 insertions(+)
 create mode 100644 app/test/test_rand_perf.c

diff --git a/app/test/Makefile b/app/test/Makefile
index 68d6b4fbc..be0f39227 100644
--- a/app/test/Makefile
+++ b/app/test/Makefile
@@ -73,6 +73,7 @@ SRCS-y += test_reciprocal_division.c
 SRCS-y += test_reciprocal_division_perf.c
 SRCS-y += test_fbarray.c
 SRCS-y += test_external_mem.c
+SRCS-y += test_rand_perf.c
 
 SRCS-y += test_ring.c
 SRCS-y += test_ring_perf.c
diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c
new file mode 100644
index 000000000..771713757
--- /dev/null
+++ b/app/test/test_rand_perf.c
@@ -0,0 +1,75 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <inttypes.h>
+#include <stdio.h>
+
+#include <rte_common.h>
+#include <rte_cycles.h>
+#include <rte_random.h>
+
+#include "test.h"
+
+static volatile uint64_t vsum;
+
+#define ITERATIONS (100000000)
+
+enum rand_type {
+	rand_type_64
+};
+
+static const char *
+rand_type_desc(enum rand_type rand_type)
+{
+	switch (rand_type) {
+	case rand_type_64:
+		return "Full 64-bit [rte_rand()]";
+	default:
+		return NULL;
+	}
+}
+
+static __rte_always_inline void
+test_rand_perf_type(enum rand_type rand_type)
+{
+	uint64_t start;
+	uint32_t i;
+	uint64_t end;
+	uint64_t sum = 0;
+	uint64_t op_latency;
+
+	start = rte_rdtsc();
+
+	for (i = 0; i < ITERATIONS; i++) {
+		switch (rand_type) {
+		case rand_type_64:
+			sum += rte_rand();
+			break;
+		}
+	}
+
+	end = rte_rdtsc();
+
+	/* to avoid an optimizing compiler removing the whole loop */
+	vsum = sum;
+
+	op_latency = (end - start) / ITERATIONS;
+
+	printf("%s: %"PRId64" TSC cycles/op\n", rand_type_desc(rand_type),
+	       op_latency);
+}
+
+static int
+test_rand_perf(void)
+{
+	rte_srand(42);
+
+	printf("Pseudo-random number generation latencies:\n");
+
+	test_rand_perf_type(rand_type_64);
+
+	return 0;
+}
+
+REGISTER_TEST_COMMAND(rand_perf_autotest, test_rand_perf);
-- 
2.17.1

Re: [dpdk-dev] [PATCH v3 2/6] eal: add pseudo-random number generation performance test

[Thomas Monjalon]

05/06/2019 12:43, Mattias Rönnblom:
> Add performance test for rte_rand().
> 
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> Acked-by: Bruce Richardson <bruce.richardson@intel.com>
> ---
>  app/test/Makefile         |  1 +
>  app/test/test_rand_perf.c | 75 +++++++++++++++++++++++++++++++++++++++
>  2 files changed, 76 insertions(+)

Why it is not added in meson.build?

Re: [dpdk-dev] [PATCH v3 2/6] eal: add pseudo-random number generation performance test

[Mattias Rönnblom]

On 2019-06-27 23:23, Thomas Monjalon wrote:
> 05/06/2019 12:43, Mattias Rönnblom:
>> Add performance test for rte_rand().
>>
>> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
>> Acked-by: Bruce Richardson <bruce.richardson@intel.com>
>> ---
>>   app/test/Makefile         |  1 +
>>   app/test/test_rand_perf.c | 75 +++++++++++++++++++++++++++++++++++++++
>>   2 files changed, 76 insertions(+)
> 
> Why it is not added in meson.build?
> 

Because the author both made the mistake of not adding it, and failed to 
test the meson build in this regard.

I'll send an updated patch set.

Thanks!

[dpdk-dev] [PATCH v3 3/6] eal: improve entropy for initial PRNG seed

[Mattias Rönnblom]

Replace the use of rte_get_timer_cycles() with getentropy() for
seeding the pseudo-random number generator. getentropy() provides a
more truly random value.

getentropy() requires glibc 2.25 and Linux kernel 3.17. In case
getentropy() is not found at compile time, or the relevant syscall
fails in runtime, the rdseed machine instruction will be used as a
fallback.

rdseed is only available on x86 (Broadwell or later). In case it is
not present, rte_get_timer_cycles() will be used as a second fallback.

On non-Meson builds, getentropy() will not be used.

Suggested-by: Bruce Richardson <bruce.richardson@intel.com>
Suggested-by: Stephen Hemminger <stephen@networkplumber.org>
Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 lib/librte_eal/common/rte_random.c | 36 +++++++++++++++++++++++++++++-
 lib/librte_eal/meson.build         |  3 +++
 2 files changed, 38 insertions(+), 1 deletion(-)

diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index 4d3cf5226..e53d96d18 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -2,7 +2,11 @@
  * Copyright(c) 2019 Ericsson AB
  */
 
+#ifdef RTE_MACHINE_CPUFLAG_RDSEED
+#include <x86intrin.h>
+#endif
 #include <stdlib.h>
+#include <unistd.h>
 
 #include <rte_branch_prediction.h>
 #include <rte_cycles.h>
@@ -133,7 +137,37 @@ rte_rand(void)
 	return __rte_rand_lfsr258(state);
 }
 
+static uint64_t
+__rte_random_initial_seed(void)
+{
+#ifdef RTE_LIBEAL_USE_GETENTROPY
+	int ge_rc;
+	uint64_t ge_seed;
+
+	ge_rc = getentropy(&ge_seed, sizeof(ge_seed));
+
+	if (ge_rc == 0)
+		return ge_seed;
+#endif
+#ifdef RTE_MACHINE_CPUFLAG_RDSEED
+	unsigned int rdseed_rc;
+	unsigned long long rdseed_seed;
+
+	/* first fallback: rdseed instruction, if available */
+	rdseed_rc = _rdseed64_step(&rdseed_seed);
+
+	if (rdseed_rc == 1)
+		return (uint64_t)rdseed_seed;
+#endif
+	/* second fallback: seed using rdtsc */
+	return rte_get_timer_cycles();
+}
+
 RTE_INIT(rte_rand_init)
 {
-	rte_srand(rte_get_timer_cycles());
+	uint64_t seed;
+
+	seed = __rte_random_initial_seed();
+
+	rte_srand(seed);
 }
diff --git a/lib/librte_eal/meson.build b/lib/librte_eal/meson.build
index fa36b20e0..ccd5b85b8 100644
--- a/lib/librte_eal/meson.build
+++ b/lib/librte_eal/meson.build
@@ -18,6 +18,9 @@ deps += 'kvargs'
 if dpdk_conf.has('RTE_USE_LIBBSD')
 	ext_deps += libbsd
 endif
+if cc.has_function('getentropy', prefix : '#include <unistd.h>')
+	cflags += '-DRTE_LIBEAL_USE_GETENTROPY'
+endif
 sources = common_sources + env_sources
 objs = common_objs + env_objs
 headers = common_headers + env_headers
-- 
2.17.1

[dpdk-dev] [PATCH v3 4/6] eal: introduce random generator function with upper bound

[Mattias Rönnblom]

Add a function rte_rand_max() which generates an uniformly distributed
pseudo-random number less than a user-specified upper bound.

The commonly used pattern rte_rand() % SOME_VALUE creates biased
results (as in some values in the range are more frequently occurring
than others) if SOME_VALUE is not a power of 2.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 lib/librte_eal/common/include/rte_random.h | 18 ++++++++++
 lib/librte_eal/common/rte_random.c         | 39 ++++++++++++++++++++++
 lib/librte_eal/rte_eal_version.map         |  1 +
 3 files changed, 58 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index 66dfe8ae7..939e6aaa9 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -17,6 +17,8 @@ extern "C" {
 
 #include <stdint.h>
 
+#include <rte_compat.h>
+
 /**
  * Seed the pseudo-random generator.
  *
@@ -47,6 +49,22 @@ rte_srand(uint64_t seedval);
 uint64_t
 rte_rand(void);
 
+/**
+ * Generates a pseudo-random number with an upper bound.
+ *
+ * This function returns an uniformly distributed (unbiased) random
+ * number less than a user-specified maximum value.
+ *
+ * If called from lcore threads, this function is thread-safe.
+ *
+ * @param upper_bound
+ *   The upper bound of the generated number.
+ * @return
+ *   A pseudo-random value between 0 and (upper_bound-1).
+ */
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index e53d96d18..3d9b9b7d8 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -137,6 +137,45 @@ rte_rand(void)
 	return __rte_rand_lfsr258(state);
 }
 
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound)
+{
+	struct rte_rand_state *state;
+	uint8_t ones;
+	uint8_t leading_zeros;
+	uint64_t mask = ~((uint64_t)0);
+	uint64_t res;
+
+	if (unlikely(upper_bound < 2))
+		return 0;
+
+	state = __rte_rand_get_state();
+
+	ones = __builtin_popcountll(upper_bound);
+
+	/* Handle power-of-2 upper_bound as a special case, since it
+	 * has no bias issues.
+	 */
+	if (unlikely(ones == 1))
+		return __rte_rand_lfsr258(state) & (upper_bound - 1);
+
+	/* The approach to avoiding bias is to create a mask that
+	 * stretches beyond the request value range, and up to the
+	 * next power-of-2. In case the masked generated random value
+	 * is equal to or greater than the upper bound, just discard
+	 * the value and generate a new one.
+	 */
+
+	leading_zeros = __builtin_clzll(upper_bound);
+	mask >>= leading_zeros;
+
+	do {
+		res = __rte_rand_lfsr258(state) & mask;
+	} while (unlikely(res >= upper_bound));
+
+	return res;
+}
+
 static uint64_t
 __rte_random_initial_seed(void)
 {
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index 20c1a9018..a53a29a35 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -384,6 +384,7 @@ EXPERIMENTAL {
 	rte_mp_request_async;
 	rte_mp_sendmsg;
 	rte_option_register;
+	rte_rand_max;
 	rte_realloc_socket;
 	rte_service_lcore_attr_get;
 	rte_service_lcore_attr_reset_all;
-- 
2.17.1

[dpdk-dev] [PATCH v3 5/6] eal: add bounded PRNG performance tests

[Mattias Rönnblom]

Add best- and worst-case performance tests for rte_rand_max().

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 app/test/test_rand_perf.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c
index 771713757..fe797ebfa 100644
--- a/app/test/test_rand_perf.c
+++ b/app/test/test_rand_perf.c
@@ -15,8 +15,13 @@ static volatile uint64_t vsum;
 
 #define ITERATIONS (100000000)
 
+#define BEST_CASE_BOUND (1<<16)
+#define WORST_CASE_BOUND (BEST_CASE_BOUND + 1)
+
 enum rand_type {
-	rand_type_64
+	rand_type_64,
+	rand_type_bounded_best_case,
+	rand_type_bounded_worst_case
 };
 
 static const char *
@@ -25,6 +30,10 @@ rand_type_desc(enum rand_type rand_type)
 	switch (rand_type) {
 	case rand_type_64:
 		return "Full 64-bit [rte_rand()]";
+	case rand_type_bounded_best_case:
+		return "Bounded average best-case [rte_rand_max()]";
+	case rand_type_bounded_worst_case:
+		return "Bounded average worst-case [rte_rand_max()]";
 	default:
 		return NULL;
 	}
@@ -46,6 +55,12 @@ test_rand_perf_type(enum rand_type rand_type)
 		case rand_type_64:
 			sum += rte_rand();
 			break;
+		case rand_type_bounded_best_case:
+			sum += rte_rand_max(BEST_CASE_BOUND);
+			break;
+		case rand_type_bounded_worst_case:
+			sum += rte_rand_max(WORST_CASE_BOUND);
+			break;
 		}
 	}
 
@@ -68,6 +83,8 @@ test_rand_perf(void)
 	printf("Pseudo-random number generation latencies:\n");
 
 	test_rand_perf_type(rand_type_64);
+	test_rand_perf_type(rand_type_bounded_best_case);
+	test_rand_perf_type(rand_type_bounded_worst_case);
 
 	return 0;
 }
-- 
2.17.1

[dpdk-dev] [PATCH v3 6/6] eal: add PRNG to MAINTAINERS and release notes

[Mattias Rönnblom]

Add a section on PRNG in MAINTAINERS, and information on the PRNG
improvements in the 19.08 release notes.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 MAINTAINERS                            |  6 ++++++
 doc/guides/rel_notes/release_19_08.rst | 13 +++++++++++++
 2 files changed, 19 insertions(+)

diff --git a/MAINTAINERS b/MAINTAINERS
index d0bf259b8..fad4a7bc0 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -222,6 +222,12 @@ M: Joyce Kong <joyce.kong@arm.com>
 F: lib/librte_eal/common/include/generic/rte_ticketlock.h
 F: app/test/test_ticketlock.c
 
+Pseudo-random Number Generation
+M: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
+F: lib/librte_eal/common/include/rte_random.h
+F: lib/librte_eal/common/rte_random.c
+F: app/test/test_rand_perf.c
+
 ARM v7
 M: Jan Viktorin <viktorin@rehivetech.com>
 M: Gavin Hu <gavin.hu@arm.com>
diff --git a/doc/guides/rel_notes/release_19_08.rst b/doc/guides/rel_notes/release_19_08.rst
index c199270c5..b6195dd14 100644
--- a/doc/guides/rel_notes/release_19_08.rst
+++ b/doc/guides/rel_notes/release_19_08.rst
@@ -54,6 +54,19 @@ New Features
      Also, make sure to start the actual text at the margin.
      =========================================================
 
+* **Updated the EAL Pseudo-random Number Generator.**
+
+  The lrand48()-based rte_rand() function is replaced with a
+  DPDK-native combined Linear Feedback Shift Register (LFSR)
+  pseudo-random number generator (PRNG).
+
+  This new PRNG implementation is multi-thread safe, provides
+  higher-quality pseudo-random numbers (including full 64 bit
+  support) and improved performance.
+
+  In addition, <rte_random.h> is extended with a new function
+  rte_rand_max() which supplies unbiased, bounded pseudo-random
+  numbers.
 
 Removed Items
 -------------
-- 
2.17.1

Re: [dpdk-dev] [PATCH v3 6/6] eal: add PRNG to MAINTAINERS and release notes

[Thomas Monjalon]

05/06/2019 12:44, Mattias Rönnblom:
> Add a section on PRNG in MAINTAINERS, and information on the PRNG
> improvements in the 19.08 release notes.
> 
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> Acked-by: Bruce Richardson <bruce.richardson@intel.com>
> ---
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> +Pseudo-random Number Generation
> +M: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> +F: lib/librte_eal/common/include/rte_random.h
> +F: lib/librte_eal/common/rte_random.c
> +F: app/test/test_rand_perf.c

Please, this file may be updated while adding the files
in previous patches.
Same progressive update can be done for the release notes.

> --- a/doc/guides/rel_notes/release_19_08.rst
> +++ b/doc/guides/rel_notes/release_19_08.rst
> +* **Updated the EAL Pseudo-random Number Generator.**
> +
> +  The lrand48()-based rte_rand() function is replaced with a
> +  DPDK-native combined Linear Feedback Shift Register (LFSR)
> +  pseudo-random number generator (PRNG).
> +
> +  This new PRNG implementation is multi-thread safe, provides
> +  higher-quality pseudo-random numbers (including full 64 bit
> +  support) and improved performance.
> +
> +  In addition, <rte_random.h> is extended with a new function
> +  rte_rand_max() which supplies unbiased, bounded pseudo-random
> +  numbers.

Re: [dpdk-dev] [PATCH v3 6/6] eal: add PRNG to MAINTAINERS and release notes

[Mattias Rönnblom]

On 2019-06-27 23:27, Thomas Monjalon wrote:
> 05/06/2019 12:44, Mattias Rönnblom:
>> Add a section on PRNG in MAINTAINERS, and information on the PRNG
>> improvements in the 19.08 release notes.
>>
>> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
>> Acked-by: Bruce Richardson <bruce.richardson@intel.com>
>> ---
>> --- a/MAINTAINERS
>> +++ b/MAINTAINERS
>> +Pseudo-random Number Generation
>> +M: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
>> +F: lib/librte_eal/common/include/rte_random.h
>> +F: lib/librte_eal/common/rte_random.c
>> +F: app/test/test_rand_perf.c
> 
> Please, this file may be updated while adding the files
> in previous patches.
> Same progressive update can be done for the release notes.
> 

OK, will do.

Re: [dpdk-dev] [PATCH v3 0/6] Pseudo-random number generation improvements

[Mattias Rönnblom]

On 2019-06-05 12:43, Mattias Rönnblom wrote:
> Fix bugs in DPDK pseudo-random number generation, make it multi-thread
> safe, go faster and produce better-quality pseudo-random numbers.
> 

Does anyone else have any comments or opinions on this patchset?

[dpdk-dev] [PATCH v4 0/5] Pseudo-random number generation improvements

[Mattias Rönnblom]

Fix bugs in DPDK pseudo-random number generation, make it multi-thread
safe, go faster and produce better-quality pseudo-random numbers.

Thanks to Stephen Hemminger, Bruce Richardson, Keith Wiles and Neil
Horman for valuable feedback.

PATCH v4:
* Fold the MAINTAINERS update and release notes commit into the other
  commits.
* Add rte_rand() performance test to the meson build.

PATCH v3:
* Rebase

PATCH v2:
* Introduce the x86 rdseed machine instruction as a first fallback, in case
  getentropy() is unavailable
* Use meson to detect getentropy() and rdseed

PATCH v1:
* Added performance tests
* Added __experimental to rte_rand_max() declaration
* Introduced a PRNG section in the MAINTAINERS file
* Added missing <rte_memory.h> include
* Use getentropy() instead of rdtsc for seeding the internal LCG

RFC v3:
* Since rte_rand() and rte_srand() have been a part of the API since long,
  the experimental attribute was removed and the symbols were moved out
  of the experimental section of the version.map file.
* rte_rand_max() performance improvements:
  * Avoid repeated rte_lcore_id() calls.
  * Handle a power-of-2 upper bound as a special case.
* Added a Bugzilla reference to the rte_rand() MT safety bug.

RFC v2:
* Removed 32-bit version of rte_rand() and rte_rand_max().
* Switched from a four-sequence LFSR (producing a 32-bit number)
  to a five-sequence LFSR (producing a 64-bit number).
* Added a note on generator not being cryptographically secure.

Mattias Rönnblom (5):
  eal: replace libc-based random number generation with LFSR
  eal: add pseudo-random number generation performance test
  eal: improve entropy for initial PRNG seed
  eal: introduce random generator function with upper bound
  eal: add bounded PRNG performance tests

 MAINTAINERS                                |   6 +
 app/test/Makefile                          |   1 +
 app/test/meson.build                       |   2 +
 app/test/test_rand_perf.c                  |  92 +++++++++
 doc/guides/rel_notes/release_19_08.rst     |  14 +-
 lib/librte_eal/common/include/rte_random.h |  47 +++--
 lib/librte_eal/common/meson.build          |   1 +
 lib/librte_eal/common/rte_random.c         | 212 +++++++++++++++++++++
 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/meson.build                 |   3 +
 lib/librte_eal/rte_eal_version.map         |   3 +
 14 files changed, 364 insertions(+), 23 deletions(-)
 create mode 100644 app/test/test_rand_perf.c
 create mode 100644 lib/librte_eal/common/rte_random.c

-- 
2.17.1

[dpdk-dev] [PATCH v4 1/5] eal: replace libc-based random number generation with LFSR

[Mattias Rönnblom]

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

This generator is faster and produces better-quality random numbers
than the linear congruential generator (LCG) of lib's lrand48(). The
implementation, as opposed to lrand48(), is multi-thread safe in
regards to concurrent rte_rand() calls from different lcore threads.
A LCG is still used, but only to seed the five per-lcore LFSR
sequences.

In addition, this patch also addresses the issue of the legacy
implementation only producing 62 bits of pseudo randomness, while the
API requires all 64 bits to be random.

This pseudo-random number generator is not cryptographically secure -
just like lrand48().

Bugzilla ID: 114
Bugzilla ID: 276

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 MAINTAINERS                                |   5 +
 doc/guides/rel_notes/release_19_08.rst     |   9 ++
 lib/librte_eal/common/include/rte_random.h |  29 ++---
 lib/librte_eal/common/meson.build          |   1 +
 lib/librte_eal/common/rte_random.c         | 139 +++++++++++++++++++++
 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 +
 10 files changed, 169 insertions(+), 22 deletions(-)
 create mode 100644 lib/librte_eal/common/rte_random.c

diff --git a/MAINTAINERS b/MAINTAINERS
index 0c3b48920..75775129d 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -227,6 +227,11 @@ M: Joyce Kong <joyce.kong@arm.com>
 F: lib/librte_eal/common/include/generic/rte_ticketlock.h
 F: app/test/test_ticketlock.c
 
+Pseudo-random Number Generation
+M: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
+F: lib/librte_eal/common/include/rte_random.h
+F: lib/librte_eal/common/rte_random.c
+
 ARM v7
 M: Jan Viktorin <viktorin@rehivetech.com>
 M: Gavin Hu <gavin.hu@arm.com>
diff --git a/doc/guides/rel_notes/release_19_08.rst b/doc/guides/rel_notes/release_19_08.rst
index 3da266705..7080d1f47 100644
--- a/doc/guides/rel_notes/release_19_08.rst
+++ b/doc/guides/rel_notes/release_19_08.rst
@@ -99,6 +99,15 @@ New Features
   Updated ``librte_telemetry`` to fetch the global metrics from the
   ``librte_metrics`` library.
 
+* **Updated the EAL Pseudo-random Number Generator.**
+
+  The lrand48()-based rte_rand() function is replaced with a
+  DPDK-native combined Linear Feedback Shift Register (LFSR)
+  pseudo-random number generator (PRNG).
+
+  This new PRNG implementation is multi-thread safe, provides
+  higher-quality pseudo-random numbers (including full 64 bit
+  support) and improved performance.
 
 Removed Items
 -------------
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..4d3cf5226
--- /dev/null
+++ b/lib/librte_eal/common/rte_random.c
@@ -0,0 +1,139 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <stdlib.h>
+
+#include <rte_branch_prediction.h>
+#include <rte_cycles.h>
+#include <rte_eal.h>
+#include <rte_lcore.h>
+#include <rte_memory.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 97633a55a..3ccc5503c 100644
--- a/lib/librte_eal/freebsd/eal/eal.c
+++ b/lib/librte_eal/freebsd/eal/eal.c
@@ -758,8 +758,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 d96ed3a7c..5f2083c4b 100644
--- a/lib/librte_eal/linux/eal/eal.c
+++ b/lib/librte_eal/linux/eal/eal.c
@@ -1122,8 +1122,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 824edf0ff..20c1a9018 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -292,6 +292,8 @@ DPDK_19.08 {
 
 	rte_lcore_index;
 	rte_lcore_to_socket_id;
+	rte_rand;
+	rte_srand;
 
 } DPDK_19.05;
 
-- 
2.17.1

[dpdk-dev] [PATCH v4 2/5] eal: add pseudo-random number generation performance test

[Mattias Rönnblom]

Add performance test for rte_rand().

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 MAINTAINERS               |  1 +
 app/test/Makefile         |  1 +
 app/test/meson.build      |  2 ++
 app/test/test_rand_perf.c | 75 +++++++++++++++++++++++++++++++++++++++
 4 files changed, 79 insertions(+)
 create mode 100644 app/test/test_rand_perf.c

diff --git a/MAINTAINERS b/MAINTAINERS
index 75775129d..bbec1982c 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -231,6 +231,7 @@ Pseudo-random Number Generation
 M: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
 F: lib/librte_eal/common/include/rte_random.h
 F: lib/librte_eal/common/rte_random.c
+F: app/test/test_rand_perf.c
 
 ARM v7
 M: Jan Viktorin <viktorin@rehivetech.com>
diff --git a/app/test/Makefile b/app/test/Makefile
index 68d6b4fbc..be0f39227 100644
--- a/app/test/Makefile
+++ b/app/test/Makefile
@@ -73,6 +73,7 @@ SRCS-y += test_reciprocal_division.c
 SRCS-y += test_reciprocal_division_perf.c
 SRCS-y += test_fbarray.c
 SRCS-y += test_external_mem.c
+SRCS-y += test_rand_perf.c
 
 SRCS-y += test_ring.c
 SRCS-y += test_ring_perf.c
diff --git a/app/test/meson.build b/app/test/meson.build
index 4de856f93..a47e001bf 100644
--- a/app/test/meson.build
+++ b/app/test/meson.build
@@ -89,6 +89,7 @@ test_sources = files('commands.c',
 	'test_power_acpi_cpufreq.c',
 	'test_power_kvm_vm.c',
 	'test_prefetch.c',
+	'test_rand_perf.c',
 	'test_rcu_qsbr.c',
 	'test_rcu_qsbr_perf.c',
 	'test_reciprocal_division.c',
@@ -254,6 +255,7 @@ perf_test_names = [
         'pmd_perf_autotest',
         'stack_perf_autotest',
         'stack_nb_perf_autotest',
+        'rand_perf_autotest'
 ]
 
 # All test cases in driver_test_names list are non-parallel
diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c
new file mode 100644
index 000000000..771713757
--- /dev/null
+++ b/app/test/test_rand_perf.c
@@ -0,0 +1,75 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Ericsson AB
+ */
+
+#include <inttypes.h>
+#include <stdio.h>
+
+#include <rte_common.h>
+#include <rte_cycles.h>
+#include <rte_random.h>
+
+#include "test.h"
+
+static volatile uint64_t vsum;
+
+#define ITERATIONS (100000000)
+
+enum rand_type {
+	rand_type_64
+};
+
+static const char *
+rand_type_desc(enum rand_type rand_type)
+{
+	switch (rand_type) {
+	case rand_type_64:
+		return "Full 64-bit [rte_rand()]";
+	default:
+		return NULL;
+	}
+}
+
+static __rte_always_inline void
+test_rand_perf_type(enum rand_type rand_type)
+{
+	uint64_t start;
+	uint32_t i;
+	uint64_t end;
+	uint64_t sum = 0;
+	uint64_t op_latency;
+
+	start = rte_rdtsc();
+
+	for (i = 0; i < ITERATIONS; i++) {
+		switch (rand_type) {
+		case rand_type_64:
+			sum += rte_rand();
+			break;
+		}
+	}
+
+	end = rte_rdtsc();
+
+	/* to avoid an optimizing compiler removing the whole loop */
+	vsum = sum;
+
+	op_latency = (end - start) / ITERATIONS;
+
+	printf("%s: %"PRId64" TSC cycles/op\n", rand_type_desc(rand_type),
+	       op_latency);
+}
+
+static int
+test_rand_perf(void)
+{
+	rte_srand(42);
+
+	printf("Pseudo-random number generation latencies:\n");
+
+	test_rand_perf_type(rand_type_64);
+
+	return 0;
+}
+
+REGISTER_TEST_COMMAND(rand_perf_autotest, test_rand_perf);
-- 
2.17.1

[dpdk-dev] [PATCH v4 3/5] eal: improve entropy for initial PRNG seed

[Mattias Rönnblom]

Replace the use of rte_get_timer_cycles() with getentropy() for
seeding the pseudo-random number generator. getentropy() provides a
more truly random value.

getentropy() requires glibc 2.25 and Linux kernel 3.17. In case
getentropy() is not found at compile time, or the relevant syscall
fails in runtime, the rdseed machine instruction will be used as a
fallback.

rdseed is only available on x86 (Broadwell or later). In case it is
not present, rte_get_timer_cycles() will be used as a second fallback.

On non-Meson builds, getentropy() will not be used.

Suggested-by: Bruce Richardson <bruce.richardson@intel.com>
Suggested-by: Stephen Hemminger <stephen@networkplumber.org>
Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 lib/librte_eal/common/rte_random.c | 36 +++++++++++++++++++++++++++++-
 lib/librte_eal/meson.build         |  3 +++
 2 files changed, 38 insertions(+), 1 deletion(-)

diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index 4d3cf5226..e53d96d18 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -2,7 +2,11 @@
  * Copyright(c) 2019 Ericsson AB
  */
 
+#ifdef RTE_MACHINE_CPUFLAG_RDSEED
+#include <x86intrin.h>
+#endif
 #include <stdlib.h>
+#include <unistd.h>
 
 #include <rte_branch_prediction.h>
 #include <rte_cycles.h>
@@ -133,7 +137,37 @@ rte_rand(void)
 	return __rte_rand_lfsr258(state);
 }
 
+static uint64_t
+__rte_random_initial_seed(void)
+{
+#ifdef RTE_LIBEAL_USE_GETENTROPY
+	int ge_rc;
+	uint64_t ge_seed;
+
+	ge_rc = getentropy(&ge_seed, sizeof(ge_seed));
+
+	if (ge_rc == 0)
+		return ge_seed;
+#endif
+#ifdef RTE_MACHINE_CPUFLAG_RDSEED
+	unsigned int rdseed_rc;
+	unsigned long long rdseed_seed;
+
+	/* first fallback: rdseed instruction, if available */
+	rdseed_rc = _rdseed64_step(&rdseed_seed);
+
+	if (rdseed_rc == 1)
+		return (uint64_t)rdseed_seed;
+#endif
+	/* second fallback: seed using rdtsc */
+	return rte_get_timer_cycles();
+}
+
 RTE_INIT(rte_rand_init)
 {
-	rte_srand(rte_get_timer_cycles());
+	uint64_t seed;
+
+	seed = __rte_random_initial_seed();
+
+	rte_srand(seed);
 }
diff --git a/lib/librte_eal/meson.build b/lib/librte_eal/meson.build
index fa36b20e0..ccd5b85b8 100644
--- a/lib/librte_eal/meson.build
+++ b/lib/librte_eal/meson.build
@@ -18,6 +18,9 @@ deps += 'kvargs'
 if dpdk_conf.has('RTE_USE_LIBBSD')
 	ext_deps += libbsd
 endif
+if cc.has_function('getentropy', prefix : '#include <unistd.h>')
+	cflags += '-DRTE_LIBEAL_USE_GETENTROPY'
+endif
 sources = common_sources + env_sources
 objs = common_objs + env_objs
 headers = common_headers + env_headers
-- 
2.17.1

Re: [dpdk-dev] [PATCH v4 3/5] eal: improve entropy for initial PRNG seed

[Ferruh Yigit]

On 6/28/2019 10:01 AM, Mattias Rönnblom wrote:
> Replace the use of rte_get_timer_cycles() with getentropy() for
> seeding the pseudo-random number generator. getentropy() provides a
> more truly random value.
> 
> getentropy() requires glibc 2.25 and Linux kernel 3.17. In case
> getentropy() is not found at compile time, or the relevant syscall
> fails in runtime, the rdseed machine instruction will be used as a
> fallback.
> 
> rdseed is only available on x86 (Broadwell or later). In case it is
> not present, rte_get_timer_cycles() will be used as a second fallback.
> 
> On non-Meson builds, getentropy() will not be used.
> 
> Suggested-by: Bruce Richardson <bruce.richardson@intel.com>
> Suggested-by: Stephen Hemminger <stephen@networkplumber.org>
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> Acked-by: Bruce Richardson <bruce.richardson@intel.com>

<...>

> +#ifdef RTE_MACHINE_CPUFLAG_RDSEED
> +	unsigned int rdseed_rc;
> +	unsigned long long rdseed_seed;
> +
> +	/* first fallback: rdseed instruction, if available */
> +	rdseed_rc = _rdseed64_step(&rdseed_seed);

This is causing build error for 32-bit [1] and ICC [2], can you please check?

[1]
.../dpdk/lib/librte_eal/common/rte_random.c: In function
‘__rte_random_initial_seed’:
.../dpdk/lib/librte_eal/common/rte_random.c:196:14: error: implicit declaration
of function ‘_rdseed64_step’; did you mean ‘_rdseed32_step’?
[-Werror=implicit-function-declaration]
  196 |  rdseed_rc = _rdseed64_step(&rdseed_seed);
      |              ^~~~~~~~~~~~~~
      |              _rdseed32_step
.../dpdk/lib/librte_eal/common/rte_random.c:196:14: error: nested extern
declaration of ‘_rdseed64_step’ [-Werror=nested-externs]



[2]
Building x86_64-native-linuxapp-icc ...
.../dpdk/lib/librte_eal/common/rte_random.c(196): error #167: argument of type
"unsigned long long *" is incompatible with parameter of type "unsigned long *"
        rdseed_rc = _rdseed64_step(&rdseed_seed);
                                   ^

Re: [dpdk-dev] [PATCH v4 3/5] eal: improve entropy for initial PRNG seed

[Mattias Rönnblom]

On 2019-06-28 21:01, Ferruh Yigit wrote:
> On 6/28/2019 10:01 AM, Mattias Rönnblom wrote:
>> Replace the use of rte_get_timer_cycles() with getentropy() for
>> seeding the pseudo-random number generator. getentropy() provides a
>> more truly random value.
>>
>> getentropy() requires glibc 2.25 and Linux kernel 3.17. In case
>> getentropy() is not found at compile time, or the relevant syscall
>> fails in runtime, the rdseed machine instruction will be used as a
>> fallback.
>>
>> rdseed is only available on x86 (Broadwell or later). In case it is
>> not present, rte_get_timer_cycles() will be used as a second fallback.
>>
>> On non-Meson builds, getentropy() will not be used.
>>
>> Suggested-by: Bruce Richardson <bruce.richardson@intel.com>
>> Suggested-by: Stephen Hemminger <stephen@networkplumber.org>
>> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
>> Acked-by: Bruce Richardson <bruce.richardson@intel.com>
> 
> <...>
> 
>> +#ifdef RTE_MACHINE_CPUFLAG_RDSEED
>> +	unsigned int rdseed_rc;
>> +	unsigned long long rdseed_seed;
>> +
>> +	/* first fallback: rdseed instruction, if available */
>> +	rdseed_rc = _rdseed64_step(&rdseed_seed);
> 
> This is causing build error for 32-bit [1] and ICC [2], can you please check?
> 
> [1]
> .../dpdk/lib/librte_eal/common/rte_random.c: In function
> ‘__rte_random_initial_seed’:
> .../dpdk/lib/librte_eal/common/rte_random.c:196:14: error: implicit declaration
> of function ‘_rdseed64_step’; did you mean ‘_rdseed32_step’?
> [-Werror=implicit-function-declaration]
>    196 |  rdseed_rc = _rdseed64_step(&rdseed_seed);
>        |              ^~~~~~~~~~~~~~
>        |              _rdseed32_step
> .../dpdk/lib/librte_eal/common/rte_random.c:196:14: error: nested extern
> declaration of ‘_rdseed64_step’ [-Werror=nested-externs]
> 
> 

My suggestion would be to just replace _rdseed64_step() with two 
_rdseed32_step() calls on both 32-bit and 64-bit x86. I'll submit a patch.

> 
> [2]
> Building x86_64-native-linuxapp-icc ...
> .../dpdk/lib/librte_eal/common/rte_random.c(196): error #167: argument of type
> "unsigned long long *" is incompatible with parameter of type "unsigned long *"
>          rdseed_rc = _rdseed64_step(&rdseed_seed);
>                                     ^

I'll fix this as well.

Thanks.

[dpdk-dev] [PATCH] eal: use 32-bit RDSEED to allow 32-bit x86 usage

[Mattias Rönnblom]

When seeding the pseudo-random number generator, replace the 64-bit
RDSEED with two 32-bit RDSEED instructions to allow building and
running on 32-bit x86.

Fixes: faf8fd252785 ("eal: improve entropy for initial PRNG seed")

Reported-by: Ferruh Yigit <ferruh.yigit@intel.com>
Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/rte_random.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index 3d9b9b7d8..f51708b30 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -189,14 +189,13 @@ __rte_random_initial_seed(void)
 		return ge_seed;
 #endif
 #ifdef RTE_MACHINE_CPUFLAG_RDSEED
-	unsigned int rdseed_rc;
-	unsigned long long rdseed_seed;
+	unsigned int rdseed_low;
+	unsigned int rdseed_high;
 
 	/* first fallback: rdseed instruction, if available */
-	rdseed_rc = _rdseed64_step(&rdseed_seed);
-
-	if (rdseed_rc == 1)
-		return (uint64_t)rdseed_seed;
+	if (_rdseed32_step(&rdseed_low) == 1 &&
+	    _rdseed32_step(&rdseed_high) == 1)
+		return (uint64_t)rdseed_low | ((uint64_t)rdseed_high << 32);
 #endif
 	/* second fallback: seed using rdtsc */
 	return rte_get_timer_cycles();
-- 
2.17.1

Re: [dpdk-dev] [PATCH] eal: use 32-bit RDSEED to allow 32-bit x86 usage

[Thomas Monjalon]

28/06/2019 23:08, Mattias Rönnblom:
> When seeding the pseudo-random number generator, replace the 64-bit
> RDSEED with two 32-bit RDSEED instructions to allow building and
> running on 32-bit x86.
> 
> Fixes: faf8fd252785 ("eal: improve entropy for initial PRNG seed")
> 
> Reported-by: Ferruh Yigit <ferruh.yigit@intel.com>
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>

Applied, thanks

[dpdk-dev] [PATCH v4 4/5] eal: introduce random generator function with upper bound

[Mattias Rönnblom]

Add a function rte_rand_max() which generates an uniformly distributed
pseudo-random number less than a user-specified upper bound.

The commonly used pattern rte_rand() % SOME_VALUE creates biased
results (as in some values in the range are more frequently occurring
than others) if SOME_VALUE is not a power of 2.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 doc/guides/rel_notes/release_19_08.rst     |  5 ++-
 lib/librte_eal/common/include/rte_random.h | 18 ++++++++++
 lib/librte_eal/common/rte_random.c         | 39 ++++++++++++++++++++++
 lib/librte_eal/rte_eal_version.map         |  1 +
 4 files changed, 62 insertions(+), 1 deletion(-)

diff --git a/doc/guides/rel_notes/release_19_08.rst b/doc/guides/rel_notes/release_19_08.rst
index 7080d1f47..f1c83d603 100644
--- a/doc/guides/rel_notes/release_19_08.rst
+++ b/doc/guides/rel_notes/release_19_08.rst
@@ -109,6 +109,10 @@ New Features
   higher-quality pseudo-random numbers (including full 64 bit
   support) and improved performance.
 
+  In addition, <rte_random.h> is extended with a new function
+  rte_rand_max() which supplies unbiased, bounded pseudo-random
+  numbers.
+
 Removed Items
 -------------
 
@@ -125,7 +129,6 @@ Removed Items
 
 * build: armv8 crypto extension is disabled.
 
-
 API Changes
 -----------
 
diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index 66dfe8ae7..939e6aaa9 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -17,6 +17,8 @@ extern "C" {
 
 #include <stdint.h>
 
+#include <rte_compat.h>
+
 /**
  * Seed the pseudo-random generator.
  *
@@ -47,6 +49,22 @@ rte_srand(uint64_t seedval);
 uint64_t
 rte_rand(void);
 
+/**
+ * Generates a pseudo-random number with an upper bound.
+ *
+ * This function returns an uniformly distributed (unbiased) random
+ * number less than a user-specified maximum value.
+ *
+ * If called from lcore threads, this function is thread-safe.
+ *
+ * @param upper_bound
+ *   The upper bound of the generated number.
+ * @return
+ *   A pseudo-random value between 0 and (upper_bound-1).
+ */
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index e53d96d18..3d9b9b7d8 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -137,6 +137,45 @@ rte_rand(void)
 	return __rte_rand_lfsr258(state);
 }
 
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound)
+{
+	struct rte_rand_state *state;
+	uint8_t ones;
+	uint8_t leading_zeros;
+	uint64_t mask = ~((uint64_t)0);
+	uint64_t res;
+
+	if (unlikely(upper_bound < 2))
+		return 0;
+
+	state = __rte_rand_get_state();
+
+	ones = __builtin_popcountll(upper_bound);
+
+	/* Handle power-of-2 upper_bound as a special case, since it
+	 * has no bias issues.
+	 */
+	if (unlikely(ones == 1))
+		return __rte_rand_lfsr258(state) & (upper_bound - 1);
+
+	/* The approach to avoiding bias is to create a mask that
+	 * stretches beyond the request value range, and up to the
+	 * next power-of-2. In case the masked generated random value
+	 * is equal to or greater than the upper bound, just discard
+	 * the value and generate a new one.
+	 */
+
+	leading_zeros = __builtin_clzll(upper_bound);
+	mask >>= leading_zeros;
+
+	do {
+		res = __rte_rand_lfsr258(state) & mask;
+	} while (unlikely(res >= upper_bound));
+
+	return res;
+}
+
 static uint64_t
 __rte_random_initial_seed(void)
 {
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index 20c1a9018..a53a29a35 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -384,6 +384,7 @@ EXPERIMENTAL {
 	rte_mp_request_async;
 	rte_mp_sendmsg;
 	rte_option_register;
+	rte_rand_max;
 	rte_realloc_socket;
 	rte_service_lcore_attr_get;
 	rte_service_lcore_attr_reset_all;
-- 
2.17.1

[dpdk-dev] [PATCH v4 5/5] eal: add bounded PRNG performance tests

[Mattias Rönnblom]

Add best- and worst-case performance tests for rte_rand_max().

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
 app/test/test_rand_perf.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/app/test/test_rand_perf.c b/app/test/test_rand_perf.c
index 771713757..fe797ebfa 100644
--- a/app/test/test_rand_perf.c
+++ b/app/test/test_rand_perf.c
@@ -15,8 +15,13 @@ static volatile uint64_t vsum;
 
 #define ITERATIONS (100000000)
 
+#define BEST_CASE_BOUND (1<<16)
+#define WORST_CASE_BOUND (BEST_CASE_BOUND + 1)
+
 enum rand_type {
-	rand_type_64
+	rand_type_64,
+	rand_type_bounded_best_case,
+	rand_type_bounded_worst_case
 };
 
 static const char *
@@ -25,6 +30,10 @@ rand_type_desc(enum rand_type rand_type)
 	switch (rand_type) {
 	case rand_type_64:
 		return "Full 64-bit [rte_rand()]";
+	case rand_type_bounded_best_case:
+		return "Bounded average best-case [rte_rand_max()]";
+	case rand_type_bounded_worst_case:
+		return "Bounded average worst-case [rte_rand_max()]";
 	default:
 		return NULL;
 	}
@@ -46,6 +55,12 @@ test_rand_perf_type(enum rand_type rand_type)
 		case rand_type_64:
 			sum += rte_rand();
 			break;
+		case rand_type_bounded_best_case:
+			sum += rte_rand_max(BEST_CASE_BOUND);
+			break;
+		case rand_type_bounded_worst_case:
+			sum += rte_rand_max(WORST_CASE_BOUND);
+			break;
 		}
 	}
 
@@ -68,6 +83,8 @@ test_rand_perf(void)
 	printf("Pseudo-random number generation latencies:\n");
 
 	test_rand_perf_type(rand_type_64);
+	test_rand_perf_type(rand_type_bounded_best_case);
+	test_rand_perf_type(rand_type_bounded_worst_case);
 
 	return 0;
 }
-- 
2.17.1

Re: [dpdk-dev] [PATCH v4 0/5] Pseudo-random number generation improvements

[Thomas Monjalon]

28/06/2019 11:01, Mattias Rönnblom:
> Mattias Rönnblom (5):
>   eal: replace libc-based random number generation with LFSR
>   eal: add pseudo-random number generation performance test
>   eal: improve entropy for initial PRNG seed
>   eal: introduce random generator function with upper bound
>   eal: add bounded PRNG performance tests

Applied, thanks
Note: I merged the tests with the related API changes.

[dpdk-dev] [RFC v3 2/2] eal: introduce random generator function with upper bound

[Mattias Rönnblom]

Add a function rte_rand_max() which generates an uniformly distributed
pseudo-random number less than a user-specified upper bound.

The commonly used pattern rte_rand() % SOME_VALUE creates biased
results (as in some values in the range are more frequently occurring
than others) if SOME_VALUE is not a power of 2.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/include/rte_random.h | 16 +++++++++
 lib/librte_eal/common/rte_random.c         | 39 ++++++++++++++++++++++
 lib/librte_eal/rte_eal_version.map         |  1 +
 3 files changed, 56 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index 66dfe8ae7..cd29f3249 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -47,6 +47,22 @@ rte_srand(uint64_t seedval);
 uint64_t
 rte_rand(void);
 
+/**
+ * Generates a pseudo-random number with an upper bound.
+ *
+ * This function returns an uniformly distributed (unbiased) random
+ * number less than a user-specified maximum value.
+ *
+ * If called from lcore threads, this function is thread-safe.
+ *
+ * @param upper_bound
+ *   The upper bound of the generated number.
+ * @return
+ *   A pseudo-random value between 0 and (upper_bound-1).
+ */
+uint64_t
+rte_rand_max(uint64_t upper_bound);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index 85dfd0cde..03a186337 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -131,6 +131,45 @@ rte_rand(void)
 	return __rte_rand_lfsr258(state);
 }
 
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound)
+{
+	struct rte_rand_state *state;
+	uint8_t ones;
+	uint8_t leading_zeros;
+	uint64_t mask = ~((uint64_t)0);
+	uint64_t res;
+
+	if (unlikely(upper_bound < 2))
+		return 0;
+
+	state = __rte_rand_get_state();
+
+	ones = __builtin_popcountll(upper_bound);
+
+	/* Handle power-of-2 upper_bound as a special case, since it
+	 * has no bias issues.
+	 */
+	if (unlikely(ones == 1))
+		return __rte_rand_lfsr258(state) & (upper_bound - 1);
+
+	/* The approach to avoiding bias is to create a mask that
+	 * stretches beyond the request value range, and up to the
+	 * next power-of-2. In case the masked generated random value
+	 * is equal to or greater than the upper bound, just discard
+	 * the value and generate a new one.
+	 */
+
+	leading_zeros = __builtin_clzll(upper_bound);
+	mask >>= leading_zeros;
+
+	do {
+		res = __rte_rand_lfsr258(state) & mask;
+	} while (unlikely(res >= upper_bound));
+
+	return res;
+}
+
 RTE_INIT(rte_rand_init)
 {
 	rte_srand(rte_get_timer_cycles());
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index 381351749..1d3a54021 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -376,6 +376,7 @@ EXPERIMENTAL {
 	rte_mp_request_async;
 	rte_mp_sendmsg;
 	rte_option_register;
+	rte_rand_max;
 	rte_realloc_socket;
 	rte_service_lcore_attr_get;
 	rte_service_lcore_attr_reset_all;
-- 
2.17.1

[dpdk-dev] [RFC v2 2/2] eal: introduce random generator function with upper bound

[Mattias Rönnblom]

Add a function rte_rand_max() which generates an uniformly distributed
pseudo-random number less than a user-specified upper bound.

The commonly used pattern rte_rand() % SOME_VALUE, in addition to
being slow, also creates biased results if SOME_VALUE is not a power
of 2. This bias is very small for small SOME_VALUE, but increases
linearly with larger SOME_VALUE.

Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
---
 lib/librte_eal/common/include/rte_random.h | 16 ++++++++++++++++
 lib/librte_eal/common/rte_random.c         | 20 ++++++++++++++++++++
 lib/librte_eal/rte_eal_version.map         |  1 +
 3 files changed, 37 insertions(+)

diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
index 66dfe8ae7..053912168 100644
--- a/lib/librte_eal/common/include/rte_random.h
+++ b/lib/librte_eal/common/include/rte_random.h
@@ -47,6 +47,22 @@ rte_srand(uint64_t seedval);
 uint64_t
 rte_rand(void);
 
+/**
+ * Generates a pseudo-random number less than upper_bound.
+ *
+ * This function returns an uniformly distributed (unbiased) random
+ * number lower than a user-specified maximum value.
+ *
+ * If called from lcore threads, this function is thread-safe.
+ *
+ * @param upper_bound
+ *   The upper bound of the generated number.
+ * @return
+ *   A pseudo-random value between 0 and (upper_bound-1).
+ */
+uint64_t
+rte_rand_max(uint64_t upper_bound);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
index 288e7b8c5..bf9240470 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -131,6 +131,26 @@ rte_rand(void)
 	return __rte_rand_lfsr258(state);
 }
 
+uint64_t __rte_experimental
+rte_rand_max(uint64_t upper_bound)
+{
+	uint8_t zeros;
+	uint64_t mask = ~((uint64_t)0);
+	uint64_t res;
+
+	if (upper_bound < 2)
+		return 0;
+
+	zeros = __builtin_clzll(upper_bound);
+	mask >>= zeros;
+
+	do {
+		res = rte_rand() & mask;
+	} while (unlikely(res >= upper_bound));
+
+	return res;
+}
+
 RTE_INIT(rte_rand_init)
 {
 	rte_srand(rte_get_timer_cycles());
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index 0d60668fa..8f5b8c6a6 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -367,6 +367,7 @@ EXPERIMENTAL {
 	rte_mp_sendmsg;
 	rte_option_register;
 	rte_rand;
+	rte_rand_max;
 	rte_realloc_socket;
 	rte_service_lcore_attr_get;
 	rte_service_lcore_attr_reset_all;
-- 
2.17.1

Re: [dpdk-dev] [RFC v2 2/2] eal: introduce random generator function with upper bound

[Wiles, Keith]

> On Apr 19, 2019, at 5:21 PM, Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> 
> Add a function rte_rand_max() which generates an uniformly distributed
> pseudo-random number less than a user-specified upper bound.
> 
> The commonly used pattern rte_rand() % SOME_VALUE, in addition to
> being slow, also creates biased results if SOME_VALUE is not a power
> of 2. This bias is very small for small SOME_VALUE, but increases
> linearly with larger SOME_VALUE.
> 
> Signed-off-by: Mattias Rönnblom <mattias.ronnblom@ericsson.com>
> ---
> lib/librte_eal/common/include/rte_random.h | 16 ++++++++++++++++
> lib/librte_eal/common/rte_random.c         | 20 ++++++++++++++++++++
> lib/librte_eal/rte_eal_version.map         |  1 +
> 3 files changed, 37 insertions(+)
> 
> diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h
> index 66dfe8ae7..053912168 100644
> --- a/lib/librte_eal/common/include/rte_random.h
> +++ b/lib/librte_eal/common/include/rte_random.h
> @@ -47,6 +47,22 @@ rte_srand(uint64_t seedval);
> uint64_t
> rte_rand(void);
> 
> +/**
> + * Generates a pseudo-random number less than upper_bound.
> + *
> + * This function returns an uniformly distributed (unbiased) random
> + * number lower than a user-specified maximum value.
> + *
> + * If called from lcore threads, this function is thread-safe.
> + *
> + * @param upper_bound
> + *   The upper bound of the generated number.
> + * @return
> + *   A pseudo-random value between 0 and (upper_bound-1).
> + */
> +uint64_t
> +rte_rand_max(uint64_t upper_bound);
> +
> #ifdef __cplusplus
> }
> #endif
> diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c
> index 288e7b8c5..bf9240470 100644
> --- a/lib/librte_eal/common/rte_random.c
> +++ b/lib/librte_eal/common/rte_random.c
> @@ -131,6 +131,26 @@ rte_rand(void)
> 	return __rte_rand_lfsr258(state);
> }
> 
> +uint64_t __rte_experimental
> +rte_rand_max(uint64_t upper_bound)
> +{
> +	uint8_t zeros;
> +	uint64_t mask = ~((uint64_t)0);
> +	uint64_t res;
> +
> +	if (upper_bound < 2)
> +		return 0;
> +
> +	zeros = __builtin_clzll(upper_bound);
> +	mask >>= zeros;
> +
> +	do {
> +		res = rte_rand() & mask;
> +	} while (unlikely(res >= upper_bound));

My concern here is the numbers of times this loop could be executed as the upper bound could be just over a power of 2 and it is a large number meaning the number of values above upper max and the power of 2 could be huge. Am I looking this loop correctly. If my thought process is correct it could take a long time to get a value less tha n upper max, correct?

If every thing aligns in a bad way it could be a large number of loops and cause all kinds of problems. What could be done here or is this a non-issue?
> +
> +	return res;
> +}
> +
> RTE_INIT(rte_rand_init)
> {
> 	rte_srand(rte_get_timer_cycles());
> diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
> index 0d60668fa..8f5b8c6a6 100644
> --- a/lib/librte_eal/rte_eal_version.map
> +++ b/lib/librte_eal/rte_eal_version.map
> @@ -367,6 +367,7 @@ EXPERIMENTAL {
> 	rte_mp_sendmsg;
> 	rte_option_register;
> 	rte_rand;
> +	rte_rand_max;
> 	rte_realloc_socket;
> 	rte_service_lcore_attr_get;
> 	rte_service_lcore_attr_reset_all;
> -- 
> 2.17.1
> 

Regards,
Keith

Re: [dpdk-dev] [RFC v2 2/2] eal: introduce random generator function with upper bound

[Mattias Rönnblom]

On 2019-04-20 23:08, Wiles, Keith wrote:

>> +uint64_t __rte_experimental
>> +rte_rand_max(uint64_t upper_bound)
>> +{
>> +	uint8_t zeros;
>> +	uint64_t mask = ~((uint64_t)0);
>> +	uint64_t res;
>> +
>> +	if (upper_bound < 2)
>> +		return 0;
>> +
>> +	zeros = __builtin_clzll(upper_bound);
>> +	mask >>= zeros;
>> +
>> +	do {
>> +		res = rte_rand() & mask;
>> +	} while (unlikely(res >= upper_bound));
> 
> My concern here is the numbers of times this loop could be executed as the upper bound could be just over a power of 2 and it is a large number meaning the number of values above upper max and the power of 2 could be huge. Am I looking this loop correctly. If my thought process is correct it could take a long time to get a value less tha n upper max, correct?
> 

If the number of values over the limit is huge, so is the value range 
below it.

> If every thing aligns in a bad way it could be a large number of loops and cause all kinds of problems. What could be done here or is this a non-issue?

Formally, the execution has no upper bound, but in practice I think this 
is a non-issue.

The cycle cost of an iteration of the loop (including the rte_rand() 
call) is ~10 cc. With the worst-case upper_limit, the probability of 
having to redo the rte_rand() call is ~0.5, for every iteration. This is 
with a pseudo-random number generator featuring an uniform distribution.

Let's assume we care about determinism, and we have a system which 
suffers a catastrophic failure if the rte_rand_max() latency is more 
than 10k clock cycles. The system performs 10M rte_rand_max() calls per 
second.

The probability of this system running for a year without any 
rte_rand_max()-related crashes is:
0.999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999970568598526

So crashes due to excessive rte_rand_max() latency may occur, but this 
risk is dwarfed by that of the system being hit by an asteroid.

(Btw, I doubt even the people in our sales force have seen that many 
nines before.)

 From a performance point of view, the high-loop-count cases are rare 
enough not to pose a serious threat. For example, being forced to redo 
rte_rand() more than five times is only a ~3% risk.

Re: [dpdk-dev] [RFC v2 2/2] eal: introduce random generator function with upper bound

[Wiles, Keith]

Sent from my iPhone

> On Apr 21, 2019, at 2:05 PM, Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> 
> On 2019-04-20 23:08, Wiles, Keith wrote:
> 
>>> +uint64_t __rte_experimental
>>> +rte_rand_max(uint64_t upper_bound)
>>> +{
>>> +    uint8_t zeros;
>>> +    uint64_t mask = ~((uint64_t)0);
>>> +    uint64_t res;
>>> +
>>> +    if (upper_bound < 2)
>>> +        return 0;
>>> +
>>> +    zeros = __builtin_clzll(upper_bound);
>>> +    mask >>= zeros;
>>> +
>>> +    do {
>>> +        res = rte_rand() & mask;
>>> +    } while (unlikely(res >= upper_bound));
>> My concern here is the numbers of times this loop could be executed as the upper bound could be just over a power of 2 and it is a large number meaning the number of values above upper max and the power of 2 could be huge. Am I looking this loop correctly. If my thought process is correct it could take a long time to get a value less tha n upper max, correct?
> 
> If the number of values over the limit is huge, so is the value range below it.
> 
>> If every thing aligns in a bad way it could be a large number of loops and cause all kinds of problems. What could be done here or is this a non-issue?
> 
> Formally, the execution has no upper bound, but in practice I think this is a non-issue.
> 
> The cycle cost of an iteration of the loop (including the rte_rand() call) is ~10 cc. With the worst-case upper_limit, the probability of having to redo the rte_rand() call is ~0.5, for every iteration. This is with a pseudo-random number generator featuring an uniform distribution.
> 
> Let's assume we care about determinism, and we have a system which suffers a catastrophic failure if the rte_rand_max() latency is more than 10k clock cycles. The system performs 10M rte_rand_max() calls per second.
> 
> The probability of this system running for a year without any rte_rand_max()-related crashes is:
> 0.999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999970568598526
> 
> So crashes due to excessive rte_rand_max() latency may occur, but this risk is dwarfed by that of the system being hit by an asteroid.
> 
> (Btw, I doubt even the people in our sales force have seen that many nines before.)
> 
> From a performance point of view, the high-loop-count cases are rare enough not to pose a serious threat. For example, being forced to redo rte_rand() more than five times is only a ~3% risk.

Even a few loops can have an effect on performance when we are talking about micro-seconds plus it leads to indeterminate results. The numbers you reported here are interesting, but I would be happier if you added a limit to the loop. If you state the likely hood of doing 5 loops is only 3% then adding a loop limit would be reasonable, right?

Re: [dpdk-dev] [RFC v2 2/2] eal: introduce random generator function with upper bound

[Mattias Rönnblom]

On 2019-04-22 06:33, Wiles, Keith wrote:

>>  From a performance point of view, the high-loop-count cases are rare enough not to pose a serious threat. For example, being forced to redo rte_rand() more than five times is only a ~3% risk.
> 
> Even a few loops can have an effect on performance when we are talking about micro-seconds plus it leads to indeterminate results. The numbers you reported here are interesting, but I would be happier if you added a limit to the loop. If you state the likely hood of doing 5 loops is only 3% then adding a loop limit would be reasonable, right?
> 

Probability is already effectively putting a limit to the loop. The risk 
of being stuck for >1us is p=~6e-73. The variations in execution times 
will in most cases be less than a LLC miss.

A loop variable will not have any effect on performance, pollute the 
code, and hurt uniformity.

Here's what rte_rand_max() performance looks like on my Skylake.

Average rte_rand_max() latency with worst-case upper_bound:
rte_rand_max() w/o loop limit: 47 cc
rte_rand_max() w/ max 8 retries: 49 cc
rte_rand_max() w/ max 4 retries: 47 cc
rte_rand_max() w/ max 2 retries: 40 cc

So you need to be very aggressive in limiting the loop count for that 
loop variable to pay off. Otherwise, you will just be at a loss, doing 
all that bookkeeping which very rarely turns out to be useful.

Re: [dpdk-dev] [RFC v2 2/2] eal: introduce random generator function with upper bound

[Wiles, Keith]

> On Apr 22, 2019, at 2:07 AM, Mattias Rönnblom <mattias.ronnblom@ericsson.com> wrote:
> 
> On 2019-04-22 06:33, Wiles, Keith wrote:
> 
>>> From a performance point of view, the high-loop-count cases are rare enough not to pose a serious threat. For example, being forced to redo rte_rand() more than five times is only a ~3% risk.
>> Even a few loops can have an effect on performance when we are talking about micro-seconds plus it leads to indeterminate results. The numbers you reported here are interesting, but I would be happier if you added a limit to the loop. If you state the likely hood of doing 5 loops is only 3% then adding a loop limit would be reasonable, right?
> 
> Probability is already effectively putting a limit to the loop. The risk of being stuck for >1us is p=~6e-73. The variations in execution times will in most cases be less than a LLC miss.
> 
> A loop variable will not have any effect on performance, pollute the code, and hurt uniformity.
> 
> Here's what rte_rand_max() performance looks like on my Skylake.
> 
> Average rte_rand_max() latency with worst-case upper_bound:
> rte_rand_max() w/o loop limit: 47 cc
> rte_rand_max() w/ max 8 retries: 49 cc
> rte_rand_max() w/ max 4 retries: 47 cc
> rte_rand_max() w/ max 2 retries: 40 cc
> 
> So you need to be very aggressive in limiting the loop count for that loop variable to pay off. Otherwise, you will just be at a loss, doing all that bookkeeping which very rarely turns out to be useful.

The adding of a loop counter is not a performance problem (as you stated only a few cycles are added) and it does not hurt the readability of the code. As for hurting uniformity I do not see that being a problem, as most loops have a visible way to terminate the loop instead of relying on a random number generator to give a valid value in a few loops. It is only reasonable IMO to limit the loop.

But I will let it go and let you add this code to DPDK if someone else wants to ACK it.

Regards,
Keith