From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id D0852A046B for ; Fri, 28 Jun 2019 11:01:31 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 4F9141B99A; Fri, 28 Jun 2019 11:01:31 +0200 (CEST) Received: from sesbmg22.ericsson.net (sesbmg22.ericsson.net [193.180.251.48]) by dpdk.org (Postfix) with ESMTP id 263C24C6C for ; Fri, 28 Jun 2019 11:01:30 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801; c=relaxed/relaxed; q=dns/txt; i=@ericsson.com; t=1561712489; x=1564304489; h=From:Sender:Reply-To:Subject:Date:Message-ID:To:CC:MIME-Version:Content-Type: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date:Resent-From: Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:In-Reply-To:References:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=+jqqRp1ZocOB69gs+FBWdnMQ0sOqM8XEJhNaVIhZLx8=; b=Ejacjh37rpj3+kF61u24QiMguA4EGCxD3NL4Xz+2HfFJB0HfK/V9BxjTT3GlpnXN 74DH/xmT0M3Z5aq0Rl+RDsUvSGSLDmcOVUQu4q8Vp1PWCzlDkPXXi18wYqilLIoR 4w1D/hzY0iqXLxWwV234fW7BVSrKjT2OVf6Va75lLgw=; X-AuditID: c1b4fb30-6ddff70000001814-7f-5d15d7697883 Received: from ESESSMB504.ericsson.se (Unknown_Domain [153.88.183.122]) by sesbmg22.ericsson.net (Symantec Mail Security) with SMTP id CD.97.06164.967D51D5; Fri, 28 Jun 2019 11:01:29 +0200 (CEST) Received: from ESESBMB503.ericsson.se (153.88.183.170) by ESESSMB504.ericsson.se (153.88.183.122) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1713.5; Fri, 28 Jun 2019 11:01:29 +0200 Received: from selio1a020.lmera.ericsson.se (153.88.183.153) by smtp.internal.ericsson.com (153.88.183.186) with Microsoft SMTP Server id 15.1.1713.5 via Frontend Transport; Fri, 28 Jun 2019 11:01:29 +0200 Received: from breslau.lmera.ericsson.se (breslau.lmera.ericsson.se [150.132.109.241]) by selio1a020.lmera.ericsson.se (8.15.1+Sun/8.15.1) with ESMTP id x5S91SYV019342; Fri, 28 Jun 2019 11:01:29 +0200 (CEST) From: =?UTF-8?q?Mattias=20R=C3=B6nnblom?= To: CC: , , , , , =?UTF-8?q?Mattias=20R=C3=B6nnblom?= Date: Fri, 28 Jun 2019 11:01:20 +0200 Message-ID: <20190628090124.16849-2-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190628090124.16849-1-mattias.ronnblom@ericsson.com> References: <20190605104400.24484-1-mattias.ronnblom@ericsson.com> <20190628090124.16849-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFvrKLMWRmVeSWpSXmKPExsUyM2J7lW7mddFYg+5eHYsbq+wttq/oYrN4 92k7k8Wt5pNsFovvyFl8enCCxYHN49eCpawei/e8ZPI4dnMau0fPyXlMHu/3XWXzuPJ9NWMA WxSXTUpqTmZZapG+XQJXxq5ld5kL5oZUrJ73kaWB8Z9rFyMnh4SAicTOrsVMXYxcHEICRxkl 9kxZzw7hfGOUeHTwJFTmIqPE0U3TGEFahAQuM0oc354LYrMJeEpMftfNAmKLCAhJLP14Gayb WeAao8TXSy+YQRLCAkESR5+dBCtiEVCVWPxkPhOIzSvgJPG2aQsrxB3yEqs3HACr5xRwluha 28sOsaxa4ueJh2wQ9YISJ2c+AZvDLKAp0br9NzuELS/RvHU2M0S9lsT9JV+YJzAKzULSMgtJ yywkLQsYmVcxihanFiflphsZ6aUWZSYXF+fn6eWllmxiBEbGwS2/DXYwvnzueIhRgINRiYd3 wR7RWCHWxLLiytxDjBIczEoivJLnRGKFeFMSK6tSi/Lji0pzUosPMUpzsCiJ8673/hcjJJCe WJKanZpakFoEk2Xi4JRqYAyoS0q3eLA/xHana5mHs8z+yScTrwjqXFt/3u2J17vLmXcqp4g5 ycTHKCWLmygFzPHNdteRvetzRHJyzOlzLhekimMFk7/3/PVclPy96W+258PZAQUc209c+mF+ hDOD76hD8/sAjY6s1x+ceLl3uzLY54SEXPj7nV3ou62Kht02Scel+sXuSizFGYmGWsxFxYkA eEfTnIgCAAA= Subject: [dpdk-dev] [PATCH v4 1/5] eal: replace libc-based random number generation with LFSR X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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 Acked-by: Bruce Richardson --- 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 F: lib/librte_eal/common/include/generic/rte_ticketlock.h F: app/test/test_ticketlock.c +Pseudo-random Number Generation +M: Mattias Rönnblom +F: lib/librte_eal/common/include/rte_random.h +F: lib/librte_eal/common/rte_random.c + ARM v7 M: Jan Viktorin M: Gavin Hu 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 -#include /** * Seed the pseudo-random generator. @@ -25,34 +24,28 @@ extern "C" { * value. It may need to be re-seeded by the user with a real random * value. * + * This function is not multi-thread safe in regards to other + * rte_srand() calls, nor is it in relation to concurrent rte_rand() + * calls. + * * @param seedval * The value of the seed. */ -static inline void -rte_srand(uint64_t seedval) -{ - srand48((long)seedval); -} +void +rte_srand(uint64_t seedval); /** * Get a pseudo-random value. * - * This function generates pseudo-random numbers using the linear - * congruential algorithm and 48-bit integer arithmetic, called twice - * to generate a 64-bit value. + * The generator is not cryptographically secure. + * + * If called from lcore threads, this function is thread-safe. * * @return * A pseudo-random value between 0 and (1<<64)-1. */ -static inline uint64_t -rte_rand(void) -{ - uint64_t val; - val = (uint64_t)lrand48(); - val <<= 32; - val += (uint64_t)lrand48(); - return val; -} +uint64_t +rte_rand(void); #ifdef __cplusplus } diff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build index 0670e4102..bafd23207 100644 --- a/lib/librte_eal/common/meson.build +++ b/lib/librte_eal/common/meson.build @@ -35,6 +35,7 @@ common_sources = files( 'rte_keepalive.c', 'rte_malloc.c', 'rte_option.c', + 'rte_random.c', 'rte_reciprocal.c', 'rte_service.c' ) diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c new file mode 100644 index 000000000..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 + +#include +#include +#include +#include +#include +#include + +struct rte_rand_state { + uint64_t z1; + uint64_t z2; + uint64_t z3; + uint64_t z4; + uint64_t z5; +} __rte_cache_aligned; + +static struct rte_rand_state rand_states[RTE_MAX_LCORE]; + +static uint32_t +__rte_rand_lcg32(uint32_t *seed) +{ + *seed = 1103515245U * *seed + 12345U; + + return *seed; +} + +static uint64_t +__rte_rand_lcg64(uint32_t *seed) +{ + uint64_t low; + uint64_t high; + + /* A 64-bit LCG would have been much cleaner, but 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