From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from sessmg23.ericsson.net (sessmg23.ericsson.net [193.180.251.45]) by dpdk.org (Postfix) with ESMTP id A3F5A568A for ; Tue, 14 May 2019 11:21:55 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801; c=relaxed/relaxed; q=dns/txt; i=@ericsson.com; t=1557825715; x=1560417715; 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=fo/08qnoTaUwhTj/JNiFfFYvkUN9tqEjm/Qgb6LsjZU=; b=PMPRbGj4DlvcPix0rsZj8jTZ78mhQvAFybTnf3Nfw9z7DMiJUB4l9qPK8bOFW+G5 M8hZUihcsf7WvdIzfAnOKFXY3227WZWB3i+7/Bodnzv8DfGs55j3sWn/Qrt3STCV pVzh6grrAbABYIs6GGw7k+JwMYTEjsHg30rgCcMCGWs=; X-AuditID: c1b4fb2d-17dff70000001a6d-94-5cda88b37bea Received: from ESESSMB502.ericsson.se (Unknown_Domain [153.88.183.120]) by sessmg23.ericsson.net (Symantec Mail Security) with SMTP id AC.A2.06765.3B88ADC5; Tue, 14 May 2019 11:21:55 +0200 (CEST) Received: from ESESSMB502.ericsson.se (153.88.183.163) by ESESSMB502.ericsson.se (153.88.183.163) 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:54 +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; Tue, 14 May 2019 11:21:54 +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 x4E9LQN8027252; Tue, 14 May 2019 11:21:54 +0200 (CEST) From: =?UTF-8?q?Mattias=20R=C3=B6nnblom?= To: CC: , , , , =?UTF-8?q?Mattias=20R=C3=B6nnblom?= Date: Tue, 14 May 2019 11:20:44 +0200 Message-ID: <20190514092046.30808-5-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+NgFnrNLMWRmVeSWpSXmKPExsUyM2J7he7mjlsxBpfvClrcWGVvsX1FF5vF u0/bmSxuNZ9ks1h8R86B1ePXgqWsHov3vGTy6Dk5j8nj/b6rbB5Xvq9mDGCN4rJJSc3JLEst 0rdL4Mp497iTqeCgVMWFGQ9ZGhhfinYxcnJICJhIHJv1grmLkYtDSOAoo0T/759sIAkhgW+M Et8/5EIkLgLZm2+wQDiXGSXm3OgBq2IT8JSY/K6bBcQWERCSWPrxMjtIEbPAXkaJV+vmgSWE Bfwk/p0/CGazCKhK3P64jRnE5hVwkjjY3MEGcYe8xOoNB8DinALOEpOm3GKHOCNF4k/PIxaI ekGJkzOfgNnMApoSrdt/s0PY8hLNW2czQ9RrSdxf8oV5AqPQLCQts5C0zELSsoCReRWjaHFq cXFuupGxXmpRZnJxcX6eXl5qySZGYBQc3PJbdwfj6teOhxgFOBiVeHjfpd+KEWJNLCuuzD3E KMHBrCTCG6V4I0aINyWxsiq1KD++qDQntfgQozQHi5I4b/TqPTFCAumJJanZqakFqUUwWSYO TqkGxkz++YeN6vNXcXNfVnqwyVXl6bP57Cqv7z2eXzxvwyWXhQ80593o5uv24fshsPpdjnBO zmap7H+FZstYapc/t4r6tOlmqzX3hD+XG8N41h8K5DMviHMWPrViWf+u4rsX6t9abd1QzHne 2CYj+7LSjZ6Ll+Pme88Q8r4kFCVQ8FP96Q+rWanp75RYijMSDbWYi4oTAXdclK1+AgAA Subject: [dpdk-dev] [PATCH 4/6] 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: , X-List-Received-Date: Tue, 14 May 2019 09:21:55 -0000 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 | 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 +#include + /** * 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 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by dpdk.space (Postfix) with ESMTP id CA915A00E6 for ; Tue, 14 May 2019 11:22:04 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 33A695F22; Tue, 14 May 2019 11:21:56 +0200 (CEST) Received: from sessmg23.ericsson.net (sessmg23.ericsson.net [193.180.251.45]) by dpdk.org (Postfix) with ESMTP id A3F5A568A for ; Tue, 14 May 2019 11:21:55 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; d=ericsson.com; s=mailgw201801; c=relaxed/relaxed; q=dns/txt; i=@ericsson.com; t=1557825715; x=1560417715; 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=fo/08qnoTaUwhTj/JNiFfFYvkUN9tqEjm/Qgb6LsjZU=; b=PMPRbGj4DlvcPix0rsZj8jTZ78mhQvAFybTnf3Nfw9z7DMiJUB4l9qPK8bOFW+G5 M8hZUihcsf7WvdIzfAnOKFXY3227WZWB3i+7/Bodnzv8DfGs55j3sWn/Qrt3STCV pVzh6grrAbABYIs6GGw7k+JwMYTEjsHg30rgCcMCGWs=; X-AuditID: c1b4fb2d-17dff70000001a6d-94-5cda88b37bea Received: from ESESSMB502.ericsson.se (Unknown_Domain [153.88.183.120]) by sessmg23.ericsson.net (Symantec Mail Security) with SMTP id AC.A2.06765.3B88ADC5; Tue, 14 May 2019 11:21:55 +0200 (CEST) Received: from ESESSMB502.ericsson.se (153.88.183.163) by ESESSMB502.ericsson.se (153.88.183.163) 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:54 +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; Tue, 14 May 2019 11:21:54 +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 x4E9LQN8027252; Tue, 14 May 2019 11:21:54 +0200 (CEST) From: =?UTF-8?q?Mattias=20R=C3=B6nnblom?= To: CC: , , , , =?UTF-8?q?Mattias=20R=C3=B6nnblom?= Date: Tue, 14 May 2019 11:20:44 +0200 Message-ID: <20190514092046.30808-5-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+NgFnrNLMWRmVeSWpSXmKPExsUyM2J7he7mjlsxBpfvClrcWGVvsX1FF5vF u0/bmSxuNZ9ks1h8R86B1ePXgqWsHov3vGTy6Dk5j8nj/b6rbB5Xvq9mDGCN4rJJSc3JLEst 0rdL4Mp497iTqeCgVMWFGQ9ZGhhfinYxcnJICJhIHJv1grmLkYtDSOAoo0T/759sIAkhgW+M Et8/5EIkLgLZm2+wQDiXGSXm3OgBq2IT8JSY/K6bBcQWERCSWPrxMjtIEbPAXkaJV+vmgSWE Bfwk/p0/CGazCKhK3P64jRnE5hVwkjjY3MEGcYe8xOoNB8DinALOEpOm3GKHOCNF4k/PIxaI ekGJkzOfgNnMApoSrdt/s0PY8hLNW2czQ9RrSdxf8oV5AqPQLCQts5C0zELSsoCReRWjaHFq cXFuupGxXmpRZnJxcX6eXl5qySZGYBQc3PJbdwfj6teOhxgFOBiVeHjfpd+KEWJNLCuuzD3E KMHBrCTCG6V4I0aINyWxsiq1KD++qDQntfgQozQHi5I4b/TqPTFCAumJJanZqakFqUUwWSYO TqkGxkz++YeN6vNXcXNfVnqwyVXl6bP57Cqv7z2eXzxvwyWXhQ80593o5uv24fshsPpdjnBO zmap7H+FZstYapc/t4r6tOlmqzX3hD+XG8N41h8K5DMviHMWPrViWf+u4rsX6t9abd1QzHne 2CYj+7LSjZ6Ll+Pme88Q8r4kFCVQ8FP96Q+rWanp75RYijMSDbWYi4oTAXdclK1+AgAA Subject: [dpdk-dev] [PATCH 4/6] 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" Message-ID: <20190514092044.gA-Fn8L6JFwJEVlWJvyAbouaJRzKea48_f0hO2g1vCc@z> 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 | 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 +#include + /** * 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