From patchwork Mon Apr 8 12:30:27 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: 52420 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 92CAA2C54; Mon, 8 Apr 2019 14:30:47 +0200 (CEST) Received: from sessmg22.ericsson.net (sessmg22.ericsson.net [193.180.251.58]) by dpdk.org (Postfix) with ESMTP id F26DD2C24 for ; Mon, 8 Apr 2019 14:30:46 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801; c=relaxed/relaxed; q=dns/txt; i=@ericsson.com; t=1554726646; x=1557318646; 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=ujLrsN6Wq+geN6v+VL00LAfWCUF73KMZFs4yGVEvHqM=; b=SepuksCkalmJ56m3anqOVeBm7jpRqlg/2IuLQMpjbFCVQIKs6ZeHOQKDyRss7yCW hbfxTKF/N2TMHc1aCDqzDLi4EsME8Du9689gUTAntuPN5oJBFOtcgYolLUCvKW1q SADqXZVWQ8cD1soJk3WB2JvvSag1D38HHvSgOWBFcfk=; X-AuditID: c1b4fb3a-ccb299e000005461-b4-5cab3ef6993d Received: from ESESSMB501.ericsson.se (Unknown_Domain [153.88.183.119]) by sessmg22.ericsson.net (Symantec Mail Security) with SMTP id 70.D7.21601.6FE3BAC5; Mon, 8 Apr 2019 14:30:46 +0200 (CEST) Received: from ESESSMB502.ericsson.se (153.88.183.163) 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; Mon, 8 Apr 2019 14:30:45 +0200 Received: from selio1a020.lmera.ericsson.se (153.88.183.153) by smtp.internal.ericsson.com (153.88.183.190) with Microsoft SMTP Server id 15.1.1713.5 via Frontend Transport; Mon, 8 Apr 2019 14:30:45 +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 x38CUjiE011282; Mon, 8 Apr 2019 14:30:45 +0200 (CEST) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: =?utf-8?q?Mattias_R=C3=B6nnblom?= Date: Mon, 8 Apr 2019 14:30:27 +0200 Message-ID: <20190408123029.6701-1-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190405135030.09c5291a@shemminger-XPS-13-9360> References: <20190405135030.09c5291a@shemminger-XPS-13-9360> MIME-Version: 1.0 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrMLMWRmVeSWpSXmKPExsUyM2J7ue43u9UxBse2aFq8+7SdyYHR49eC pawBjFFcNimpOZllqUX6dglcGbNP3mQqWOZQ8W6nRAPjZ9MuRk4OCQETiVX9PWxdjFwcQgJH GSXmbt7DCOF8ZZR48WIRC4RzgVHiYMduqLJLjBKLZl1hBelnE/CUmPyumwXEFhEQklj68TI7 iM0s4C7x/tFypi5GDg5hAVeJf0vNQMIsAioSV7cfYwaxeQUcJWY37GGDOENeYvWGA2BxTgFb if7GnWBjhARsJDbMf8kKUS8ocXLmExaI8ZoSrdt/Q62Sl2jeOpsZol5L4v6SL8wTGIVmIWmZ haRlFpKWBYzMqxhFi1OLi3PTjYz0Uosyk4uL8/P08lJLNjECg/bglt9WOxgPPnc8xCjAwajE w6tnvDpGiDWxrLgy9xCjBAezkgjvzqmrYoR4UxIrq1KL8uOLSnNSiw8xSnOwKInz/hESjBES SE8sSc1OTS1ILYLJMnFwSjUwhrt7ZT5+/tHr6rLZ8R88vCYudJE+MS/p8xt/1VXPK/5sLnl7 ZHYqU/rhT3GsZ3fxlc+7/uvgTm2/F0p9W98n5r3UzLY8+2Li5cSf07Tl0juvVxyZnOmcNye/ pOPFuxWTb3y3TJD0UFWK7v1qJPnx1o3m9wpPduVlVfXwOz8+cuXZRIfSWw+vlyixFGckGmox FxUnAgBQEfshVgIAAA== Subject: [dpdk-dev] [RFC 1/3] Replace lrand48-based rte_rand with LFSR generator 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 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 --- 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 -#include /** * 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 + +#include +#include +#include +#include + +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; }; From patchwork Mon Apr 8 12:30:28 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: 52422 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 B92A25424; Mon, 8 Apr 2019 14:31:32 +0200 (CEST) Received: from sesbmg23.ericsson.net (sesbmg23.ericsson.net [193.180.251.37]) by dpdk.org (Postfix) with ESMTP id 919BE2C54 for ; Mon, 8 Apr 2019 14:31:31 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801; c=relaxed/relaxed; q=dns/txt; i=@ericsson.com; t=1554726691; x=1557318691; 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=3sFXeMrF3salHKItoY3zpReR9fRWB0UTFSJaZHyUXpI=; b=CqbS9UXYrbhp9Y9ni6QmkG3U4szFvfZis8h4Cs2eg3sI5dMBIPUjWXbuNWk3lqya LpfyXh9UNu9ijE62WHTf7pLy74suIQW9qii+rMuF0LFwrIZ8w+ojd5JxGkqEEYsi OJCUZg4nfoyc8JPpZAICxyz492/4hsVt+Nr+o0+kNrQ=; X-AuditID: c1b4fb25-91c349e000001b0f-25-5cab3f23a5ae Received: from ESESBMB502.ericsson.se (Unknown_Domain [153.88.183.115]) by sesbmg23.ericsson.net (Symantec Mail Security) with SMTP id 76.FA.06927.32F3BAC5; Mon, 8 Apr 2019 14:31:31 +0200 (CEST) Received: from ESESBMB502.ericsson.se (153.88.183.169) by ESESBMB502.ericsson.se (153.88.183.169) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1713.5; Mon, 8 Apr 2019 14:30:47 +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; Mon, 8 Apr 2019 14:30:46 +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 x38CUjiF011282; Mon, 8 Apr 2019 14:30:47 +0200 (CEST) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: =?utf-8?q?Mattias_R=C3=B6nnblom?= Date: Mon, 8 Apr 2019 14:30:28 +0200 Message-ID: <20190408123029.6701-2-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190408123029.6701-1-mattias.ronnblom@ericsson.com> References: <20190405135030.09c5291a@shemminger-XPS-13-9360> <20190408123029.6701-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrMLMWRmVeSWpSXmKPExsUyM2J7sa6y/eoYg1en+C3efdrO5MDo8WvB UtYAxigum5TUnMyy1CJ9uwSujOuX9rEV7BSo+Na5maWB8Q1vFyMHh4SAicSFmTxdjFwcQgJH GSUmbjzKBOF8ZZS4fWEGK4RzgVFi0qwWZgjnEqPE/F/z2bsYOTnYBDwlJr/rZgGxRQSEJJZ+ vAwWZxZwl3j/aDkTiC0sYCgxdfM9VhCbRUBFYvn0XSwgq3kFHCV+tOWBhCUE5CVWbzjADGJz CjhJNJ6+CGYLCZRITJ+yAGwkr4CgxMmZT1ggxmtKtG7/DbVKXqJ562yoei2J+0u+ME9gFJqF pGUWkpZZSFoWMDKvYhQtTi1Oyk03MtZLLcpMLi7Oz9PLSy3ZxAgM2oNbfqvuYLz8xvEQowAH oxIP7xmj1TFCrIllxZW5hxglOJiVRHh3Tl0VI8SbklhZlVqUH19UmpNafIhRmoNFSZz3j5Bg jJBAemJJanZqakFqEUyWiYNTqoGRRcp5y2qna6w2B9zy17FN75/P9CniReByiyPqZh6Z2yvM 81REE26ruk9STrq24GWHM/Nz4S9/A3bPDMvN7xSxSq+ed9+yp+oS/7kgbsGeQoY1d74zBrsX F2w5e0O1Oc89zzLphts907jL3boTzpTZn2SPCrnwofrDthc3ZBL9czdfmlnb81OJpTgj0VCL uag4EQDN6DyyVgIAAA== Subject: [dpdk-dev] [RFC 2/3] Add 32-bit version of rte_rand 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" Signed-off-by: Mattias Rönnblom --- 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; From patchwork Mon Apr 8 12:30:29 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: 52421 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 86EC94CBD; Mon, 8 Apr 2019 14:30:52 +0200 (CEST) Received: from sesbmg22.ericsson.net (sesbmg22.ericsson.net [193.180.251.48]) by dpdk.org (Postfix) with ESMTP id 386144CBD for ; Mon, 8 Apr 2019 14:30:50 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801; c=relaxed/relaxed; q=dns/txt; i=@ericsson.com; t=1554726649; x=1557318649; 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=mxN9Wgagh43zWAre7y1tHdw5srutos6+IFnchZnKldA=; b=do8u1vOc6nKO8a9PT5rHZPtXG5FOwDfs7ot4RftoQYZ7tT5BYyDkzUgvHcNPBEs5 dbq6a4umX756SBWqymwZOQNb6ZLBFEamxFh9OUJmTnpOrhxRcrkT7WkGPi4UWmEf wZxjlcAyEP9y5reO/uXEnYQu9WtC5oXJvnv5zl6Uxt4=; X-AuditID: c1b4fb30-0bbc49e000004449-6a-5cab3ef95701 Received: from ESESSMB501.ericsson.se (Unknown_Domain [153.88.183.119]) by sesbmg22.ericsson.net (Symantec Mail Security) with SMTP id 6E.5F.17481.9FE3BAC5; Mon, 8 Apr 2019 14:30:49 +0200 (CEST) Received: from ESESBMB505.ericsson.se (153.88.183.172) 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; Mon, 8 Apr 2019 14:30:48 +0200 Received: from selio1a020.lmera.ericsson.se (153.88.183.153) by smtp.internal.ericsson.com (153.88.183.188) with Microsoft SMTP Server id 15.1.1713.5 via Frontend Transport; Mon, 8 Apr 2019 14:30:48 +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 x38CUjiG011282; Mon, 8 Apr 2019 14:30:48 +0200 (CEST) From: =?utf-8?q?Mattias_R=C3=B6nnblom?= To: CC: =?utf-8?q?Mattias_R=C3=B6nnblom?= Date: Mon, 8 Apr 2019 14:30:29 +0200 Message-ID: <20190408123029.6701-3-mattias.ronnblom@ericsson.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190408123029.6701-1-mattias.ronnblom@ericsson.com> References: <20190405135030.09c5291a@shemminger-XPS-13-9360> <20190408123029.6701-1-mattias.ronnblom@ericsson.com> MIME-Version: 1.0 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrCLMWRmVeSWpSXmKPExsUyM2J7ue5Pu9UxBu/Wali8+7SdyYHR49eC pawBjFFcNimpOZllqUX6dglcGX03DjAXnJStaNq7hamBcbFEFyMHh4SAicS0iTVdjFwcQgJH GSWWrpvKBuF8ZZTY1PIdyrnAKPHh+lIWCOcSo8S0ax8Yuxg5OdgEPCUmv+tmAbFFBIQkln68 zA5iMwu4S7x/tJwJxBYW8JB40jwDLM4ioCKx7MtGsDivgKPExQ/v2UBsCQF5idUbDjCD2JwC ThKNpy+C2UICJRLTpyxgh6gXlDg58wkLxHxNidbtv6F2yUs0b50NVa8lcX/JF+YJjEKzkLTM QtIyC0nLAkbmVYyixanFSbnpRkZ6qUWZycXF+Xl6eaklmxiBYXtwy2+DHYwvnzseYhTgYFTi 4S0wWh0jxJpYVlyZe4hRgoNZSYR359RVMUK8KYmVValF+fFFpTmpxYcYpTlYlMR5/wgJxggJ pCeWpGanphakFsFkmTg4pRoYxT/8WnbA5U/wkYbFqTtLBH1vM4f4FIic8W5aofWtje3UzN6o RJFfnQ3H6tazCdVd2FydcOklyxL3iekdOpuC7238GGaQvu5jXZ7hlfA3K0/I77Pmrefbvf7/ lXOG/h1G4T6tCxK6LvTatnF8ehYQXWPUz+cmoPYrwOxTYpCHlkMPv2To4nVKLMUZiYZazEXF iQDZ6gsYVwIAAA== Subject: [dpdk-dev] [RFC 3/3] Introduce random generator functions 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 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 --- 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;