From patchwork Wed Apr 24 12:33:19 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Mattias_R=C3=B6nnblom?= X-Patchwork-Id: 53049 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 9DB7F1B398; Wed, 24 Apr 2019 14:33:33 +0200 (CEST) Received: from sessmg22.ericsson.net (sessmg22.ericsson.net [193.180.251.58]) by dpdk.org (Postfix) with ESMTP id 976931B2B0 for ; Wed, 24 Apr 2019 14:33:32 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801; c=relaxed/relaxed; q=dns/txt; i=@ericsson.com; t=1556109212; x=1558701212; 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=kcXxrzYEbiXBgJcQI+4gVDO/1Yt4+XxVicVNBFj+76E=; b=baCAWjCEZ9x/J4+odk9ahANEh10KTrVWg9GCNfVgoRTL0tu5MnnAs8ZfXIMa9JB0 8ukoL/A7iGWeHh+zwerhKUcrJv99pgPTnQ61dn2DFjGHz5sNpX3aBzkwPey/TzoZ VOZB3WoatQ0QZ/YH0+9/Q/uVduthXezvPvGIpIv8tOQ=; X-AuditID: c1b4fb3a-709ff7000000189f-0e-5cc0579c301f Received: from ESESSMB501.ericsson.se (Unknown_Domain [153.88.183.119]) by sessmg22.ericsson.net (Symantec Mail Security) with SMTP id 6A.30.06303.C9750CC5; Wed, 24 Apr 2019 14:33:32 +0200 (CEST) Received: from ESESSMB505.ericsson.se (153.88.183.166) by ESESSMB501.ericsson.se (153.88.183.162) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1713.5; Wed, 24 Apr 2019 14:33:31 +0200 Received: from selio1a020.lmera.ericsson.se (153.88.183.153) by smtp.internal.ericsson.com (153.88.183.193) with Microsoft SMTP Server id 15.1.1713.5 via Frontend Transport; Wed, 24 Apr 2019 14:33:31 +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 x3OCXNAd010622; Wed, 24 Apr 2019 14:33:31 +0200 (CEST) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: , , =?utf-8?q?Matti?= =?utf-8?q?as_R=C3=B6nnblom?= Date: Wed, 24 Apr 2019 14:33:19 +0200 Message-ID: <20190424123320.19610-2-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190424123320.19610-1-mattias.ronnblom@ericsson.com> References: <20190424123320.19610-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFrrGLMWRmVeSWpSXmKPExsUyM2J7ue6c8AMxBp1nRCzefdrOZHGr+SSb xeI7cg7MHr8WLGX16Dk5j8njyvfVjAHMUVw2Kak5mWWpRfp2CVwZzy+UFUx2q9jd9p2pgXGp VRcjJ4eEgInEtJZ2JhBbSOAoo8TLLxpdjFxA9jdGibbdH1khnIuMEkt6DzBBOJcZJbYfXswI 0sIm4Ckx+V03C4gtIiAksfTjZXYQm1mggVFi4VYOEFtYIEBiX+c2ZhCbRUBVYtKOh2A2r4CT xKVzB1ggzpCXWL3hAFicU8BZ4sDLBYwQJ1VIvPv7nR2iXlDi5MwnLBDzNSVat/+G2iUv0bx1 NjNEvZbE/SVfmCcwCs1C0jILScssJC0LGJlXMYoWpxYX56YbGemlFmUmFxfn5+nlpZZsYgSG 9sEtv612MB587niIUYCDUYmHN8z5QIwQa2JZcWXuIUYJDmYlEV6T7ftjhHhTEiurUovy44tK c1KLDzFKc7AoifNGr94TIySQnliSmp2aWpBaBJNl4uCUamA0UjG5kqs5Ida/okCmV+Jk0JQ9 Cx+EsIY2RC3x/lzYY/huZtmJDXxTmUKvxucwa3WcembWFBMqfvVw4bJDN6RqGvau63vX/md1 hsRMBZvmY83PF1v9fhW08F70rN3hfmWzJtgKrrrm88dMiyM26PzlCzfmC69bK/P1amCHCIN1 6dJrFnGOt+SVWIozEg21mIuKEwE71W7yaQIAAA== Subject: [dpdk-dev] [RFC v3 1/2] eal: replace libc-based random number generation with LFSR X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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 --- lib/librte_eal/common/include/rte_random.h | 29 ++--- lib/librte_eal/common/meson.build | 1 + lib/librte_eal/common/rte_random.c | 137 +++++++++++++++++++++ lib/librte_eal/freebsd/eal/Makefile | 1 + lib/librte_eal/freebsd/eal/eal.c | 2 - lib/librte_eal/linux/eal/Makefile | 1 + lib/librte_eal/linux/eal/eal.c | 2 - lib/librte_eal/rte_eal_version.map | 2 + 8 files changed, 153 insertions(+), 22 deletions(-) create mode 100644 lib/librte_eal/common/rte_random.c diff --git a/lib/librte_eal/common/include/rte_random.h b/lib/librte_eal/common/include/rte_random.h index b2ca1c209..66dfe8ae7 100644 --- a/lib/librte_eal/common/include/rte_random.h +++ b/lib/librte_eal/common/include/rte_random.h @@ -16,7 +16,6 @@ extern "C" { #endif #include -#include /** * Seed the pseudo-random generator. @@ -25,34 +24,28 @@ extern "C" { * value. It may need to be re-seeded by the user with a real random * value. * + * This function is not multi-thread safe in regards to other + * rte_srand() calls, nor is it in relation to concurrent rte_rand() + * calls. + * * @param seedval * The value of the seed. */ -static inline void -rte_srand(uint64_t seedval) -{ - srand48((long)seedval); -} +void +rte_srand(uint64_t seedval); /** * Get a pseudo-random value. * - * This function generates pseudo-random numbers using the linear - * congruential algorithm and 48-bit integer arithmetic, called twice - * to generate a 64-bit value. + * The generator is not cryptographically secure. + * + * If called from lcore threads, this function is thread-safe. * * @return * A pseudo-random value between 0 and (1<<64)-1. */ -static inline uint64_t -rte_rand(void) -{ - uint64_t val; - val = (uint64_t)lrand48(); - val <<= 32; - val += (uint64_t)lrand48(); - return val; -} +uint64_t +rte_rand(void); #ifdef __cplusplus } diff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build index 0670e4102..bafd23207 100644 --- a/lib/librte_eal/common/meson.build +++ b/lib/librte_eal/common/meson.build @@ -35,6 +35,7 @@ common_sources = files( 'rte_keepalive.c', 'rte_malloc.c', 'rte_option.c', + 'rte_random.c', 'rte_reciprocal.c', 'rte_service.c' ) diff --git a/lib/librte_eal/common/rte_random.c b/lib/librte_eal/common/rte_random.c new file mode 100644 index 000000000..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 + +#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 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; From patchwork Wed Apr 24 12:33:20 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Mattias_R=C3=B6nnblom?= X-Patchwork-Id: 53050 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id B1F361B4E3; Wed, 24 Apr 2019 14:33:39 +0200 (CEST) Received: from sesbmg22.ericsson.net (sesbmg22.ericsson.net [193.180.251.48]) by dpdk.org (Postfix) with ESMTP id 9A1B71B2B0 for ; Wed, 24 Apr 2019 14:33:37 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801; c=relaxed/relaxed; q=dns/txt; i=@ericsson.com; t=1556109217; x=1558701217; 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=mVt6qNT+KVb8TgSEPSLAqv4/01tiUkrrU+5bjs//QJ8=; b=E5IiUjgIiKHArPagpefqOUQH8pTNSy2csls1y06+363Y41Ccodn+39P51hcDCpJ3 9pi1fn/nPkwLHfSPi/YueiaESzASxmxNx0jBwHS+4gQ2qXlmR63/UL1TzReDRKrn F6hoalFTaBbZSLnrPt4QXuDKwGwt9D0b4AMmcZCIzE4=; X-AuditID: c1b4fb30-6ddff70000001814-07-5cc057a15456 Received: from ESESBMB501.ericsson.se (Unknown_Domain [153.88.183.114]) by sesbmg22.ericsson.net (Symantec Mail Security) with SMTP id 67.F3.06164.1A750CC5; Wed, 24 Apr 2019 14:33:37 +0200 (CEST) Received: from ESESBMB502.ericsson.se (153.88.183.169) by ESESBMB501.ericsson.se (153.88.183.168) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1713.5; Wed, 24 Apr 2019 14:33:36 +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; Wed, 24 Apr 2019 14:33:36 +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 x3OCXNAe010622; Wed, 24 Apr 2019 14:33:36 +0200 (CEST) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: , , =?utf-8?q?Matti?= =?utf-8?q?as_R=C3=B6nnblom?= Date: Wed, 24 Apr 2019 14:33:20 +0200 Message-ID: <20190424123320.19610-3-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190424123320.19610-1-mattias.ronnblom@ericsson.com> References: <20190424123320.19610-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFrrGLMWRmVeSWpSXmKPExsUyM2J7ke7C8AMxBot/8Vq8+7SdyeJW80k2 i8V35ByYPX4tWMrq0XNyHpPHle+rGQOYo7hsUlJzMstSi/TtErgy5px6y1awTbLi3YutjA2M baJdjJwcEgImElO7HrB2MXJxCAkcZZRYeOkmM4TzjVFi64J7zCBVQgIXGSU2fi+GSFxmlFh3 eRo7SIJNwFNi8rtuFhBbREBIYunHy2BxZoEGoFFbOUBsYQF/ieNNSxlBbBYBVYkPG88ArePg 4BVwkrh1WgXiCnmJ1RsOgO3iFHCWOPByASPE3gqJd3+/g43kFRCUODnzCQvEeE2J1u2/oVbJ SzRvnQ11p5bE/SVfmCcwCs1C0jILScssJC0LGJlXMYoWpxYn5aYbGemlFmUmFxfn5+nlpZZs YgSG9sEtvw12ML587niIUYCDUYmHV8v5QIwQa2JZcWXuIUYJDmYlEV6T7ftjhHhTEiurUovy 44tKc1KLDzFKc7AoifNGr94TIySQnliSmp2aWpBaBJNl4uCUamAMF0rXS2qW5RfJF9ojVHfP fJ5y1td54nmWDEt8Rdjsw76d4uieuva6SsCJa1fjzy7amGl+97jbQYXNZ1KeBU/wrfiSsHLX LfYpMnH/5okXidy+eU9w8vIkufjmEtf3d5k2LlTIXbWCaRuHzYbwL/2n/gdmZh1bLpQYZPP0 79LTaXM2bV5S5xenxFKckWioxVxUnAgAzvtOL2kCAAA= Subject: [dpdk-dev] [RFC v3 2/2] eal: introduce random generator function with upper bound 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" 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 --- 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;