From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <dev-bounces@dpdk.org>
Received: from dpdk.org (dpdk.org [92.243.14.124])
by dpdk.space (Postfix) with ESMTP id C6757A00E6
for <public@inbox.dpdk.org>; Tue, 14 May 2019 11:21:36 +0200 (CEST)
Received: from [92.243.14.124] (localhost [127.0.0.1])
by dpdk.org (Postfix) with ESMTP id 8E96C5B2A;
Tue, 14 May 2019 11:21:34 +0200 (CEST)
Received: from sessmg22.ericsson.net (sessmg22.ericsson.net [193.180.251.58])
by dpdk.org (Postfix) with ESMTP id 9DB1A5A4A
for <dev@dpdk.org>; Tue, 14 May 2019 11:21:33 +0200 (CEST)
DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801;
c=relaxed/relaxed;
q=dns/txt; i=@ericsson.com; t=1557825693; x=1560417693;
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=d8IrLP7hWL5S+xfzhDw/zKwOPIKdITQcZEqq2N7axeU=;
b=OKy7gGNqpahmLT9bF7jTec2CocPjHyXq7S5Wnus+i0jDMz2oAYb/cF5IDKAzrwfa
tCP+MKT/6rnMZATf9u+c8U6B65qMnfN8VHfaLB/srj9KCIV1aUYGmQTOlWo6Io/A
tnS9z2eiy3nqaLoQoYSr3INsFta5MlDDrHwBdd5M7mE=;
X-AuditID: c1b4fb3a-709ff7000000189f-9b-5cda889d804c
Received: from ESESBMB503.ericsson.se (Unknown_Domain [153.88.183.116])
by sessmg22.ericsson.net (Symantec Mail Security) with SMTP id
65.2B.06303.D988ADC5; Tue, 14 May 2019 11:21:33 +0200 (CEST)
Received: from ESESBMB502.ericsson.se (153.88.183.169) by
ESESBMB503.ericsson.se (153.88.183.170) with Microsoft SMTP Server
(version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id
15.1.1713.5; Tue, 14 May 2019 11:21:32 +0200
Received: from selio1a020.lmera.ericsson.se (153.88.183.153) by
smtp.internal.ericsson.com (153.88.183.185) with Microsoft SMTP Server id
15.1.1713.5 via Frontend Transport; Tue, 14 May 2019 11:21:32 +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
x4E9LQN5027252; Tue, 14 May 2019 11:21:32 +0200 (CEST)
From: =?UTF-8?q?Mattias=20R=C3=B6nnblom?= <mattias.ronnblom@ericsson.com>
To: <dev@dpdk.org>
CC: <nhorman@tuxdriver.com>, <stephen@networkplumber.org>,
<david.marchand@redhat.com>, <bruce.richardson@intel.com>,
=?UTF-8?q?Mattias=20R=C3=B6nnblom?= <mattias.ronnblom@ericsson.com>
Date: Tue, 14 May 2019 11:20:41 +0200
Message-ID: <20190514092046.30808-2-mattias.ronnblom@ericsson.com>
X-Mailer: git-send-email 2.17.1
In-Reply-To: <20190514092046.30808-1-mattias.ronnblom@ericsson.com>
References: <20190508181014.7dde7580@xps13>
<20190514092046.30808-1-mattias.ronnblom@ericsson.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFnrJLMWRmVeSWpSXmKPExsUyM2J7ie7cjlsxBpd381rcWGVvsX1FF5vF
u0/bmSxuNZ9ks1h8R86B1ePXgqWsHov3vGTy6Dk5j8nj/b6rbB5Xvq9mDGCN4rJJSc3JLEst
0rdL4MpY93Y2e8F7j4rDC0QaGLfbdDFycEgImEgce2PcxcjFISRwlFGiefl8FgjnG6PErfUf
2CGci4wSrz4eYYVwLjNKTG/7A1TGycEm4Ckx+V03mC0iICSx9ONlsA5mgb1AHevmgSWEBfwl
lvz7wwqyj0VAVWLn2WqQMK+Ak8Tjq2dYQWwJAXmJ1RsOMIPYnALOEpOm3GIHsYUEUiT+9Dxi
gagXlDg58wmYzSygKdG6/Tc7hC0v0bx1NjNEvZbE/SVfmCcwCs1C0jILScssJC0LGJlXMYoW
pxYX56YbGemlFmUmFxfn5+nlpZZsYgRGwMEtv612MB587niIUYCDUYmHNzb9VowQa2JZcWXu
IUYJDmYlEd4oxRsxQrwpiZVVqUX58UWlOanFhxilOViUxHmjV++JERJITyxJzU5NLUgtgsky
cXBKNTBm1ulfOlg/TSRblGtp8O2MVd8zcnZO5A621YsqKmcU2KP/jMt8mlDGRSGZ7a7P8njj
JqXutXXY3qu0wvLTzo2Ptykfe94izPQ7+kv03kc3xR/8eujlUNmk8NU2Sfeu76bz26Y49VS7
S551mhMZyXNul/2kdeHiVz/9nMW5NVihVMZk7ektZxKUWIozEg21mIuKEwHXCbS+fAIAAA==
Subject: [dpdk-dev] [PATCH 1/6] 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 <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://mails.dpdk.org/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://mails.dpdk.org/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>
Message-ID: <20190514092041.IQpWHOAdALrLv1XKZimRju-nHlVZ2SWfTja3E2UOjqg@z>
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