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 DB2C4A0096
for <public@inbox.dpdk.org>; Wed, 5 Jun 2019 12:45:28 +0200 (CEST)
Received: from [92.243.14.124] (localhost [127.0.0.1])
by dpdk.org (Postfix) with ESMTP id 5BB721BB22;
Wed, 5 Jun 2019 12:44:43 +0200 (CEST)
Received: from sessmg23.ericsson.net (sessmg23.ericsson.net [193.180.251.45])
by dpdk.org (Postfix) with ESMTP id 8C2E91BA8F
for <dev@dpdk.org>; Wed, 5 Jun 2019 12:44: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=1559731476; x=1562323476;
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=uZiIz4oSZOfhKYpEU373SIY5pIImkCt1mT2IwfQZKBU=;
b=Z+GcW31ZnCtL82R0sntUHSeVouDh2XM5s5zCu2u/jWKlp95nR8PhYRXOk9i4TfaZ
GGPdrT9JIouhcpUmyOa9Y9Xat0Hk5hAlZQMSZDnrsF5JdSBv9YfT8x52BQqNoOTs
QkUzGVKodKwhtpYf/rp/QCzi/aW3AhW7cJiWNbBg49c=;
X-AuditID: c1b4fb2d-195ff70000001a6d-41-5cf79d1480d1
Received: from ESESBMB501.ericsson.se (Unknown_Domain [153.88.183.114])
by sessmg23.ericsson.net (Symantec Mail Security) with SMTP id
70.58.06765.41D97FC5; Wed, 5 Jun 2019 12:44:36 +0200 (CEST)
Received: from ESESBMB504.ericsson.se (153.88.183.171) 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, 5 Jun 2019 12:44:26 +0200
Received: from selio1a020.lmera.ericsson.se (153.88.183.153) by
smtp.internal.ericsson.com (153.88.183.187) with Microsoft SMTP Server id
15.1.1713.5 via Frontend Transport; Wed, 5 Jun 2019 12:44:26 +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
x55AiQRE025408; Wed, 5 Jun 2019 12:44:27 +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: Wed, 5 Jun 2019 12:43:58 +0200
Message-ID: <20190605104400.24484-5-mattias.ronnblom@ericsson.com>
X-Mailer: git-send-email 2.17.1
In-Reply-To: <20190605104400.24484-1-mattias.ronnblom@ericsson.com>
References: <20190516203529.GA642@bricha3-MOBL.ger.corp.intel.com>
<20190605104400.24484-1-mattias.ronnblom@ericsson.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFnrDLMWRmVeSWpSXmKPExsUyM2J7ka7I3O8xBouPsVncWGVvsX1FF5vF
u0/bmSxuNZ9ks1h8R86B1ePXgqWsHov3vGTy6Dk5j8nj/b6rbB5Xvq9mDGCN4rJJSc3JLEst
0rdL4Mr48mUac0GTdMX8S1dYGxiXiXUxcnJICJhIdL6bx9TFyMUhJHCUUeL+70VsEM5XRolH
kzZCZS4wSqze3s0M4VxilFj6fgobSD+bgKfE5HfdLCC2iICQxNKPl9lBipgF9jJKvFo3Dywh
LBAosfHOdLAGFgEVibXL2thBbF4BJ4n9hw+zQBwiL7F6wwFmEJtTwFni8fT9TCC2kEC1xIS3
zUwQ9YISJ2c+AatnFtCUaN3+mx3Clpdo3jqbGaJeS+L+ki/MExiFZiFpmYWkZRaSlgWMzKsY
RYtTi4tz042M9VKLMpOLi/Pz9PJSSzYxAuPg4JbfujsYV792PMQowMGoxMMr3/s9Rog1say4
MvcQowQHs5IIb+LtLzFCvCmJlVWpRfnxRaU5qcWHGKU5WJTEeaNX74kREkhPLEnNTk0tSC2C
yTJxcEo1MC7YtsvcPPa0vaR0rUGTf4Ln+0WvVhw9/mpb87ON/haiV/UiohIKGZfwGPF1z7/s
UzY3Y0Pd432cxxkvnTq+QnEnb8uqt2d9H9r0LXpk1r5/tp9KO+Phummv9ka/9q+YbpZ47lGo
42OXs6+1uUxaUqLzBLw3Zsa4P2Fb8eZPPC/bjU/NSxm3MiqxFGckGmoxFxUnAgB9zlkKfwIA
AA==
Subject: [dpdk-dev] [PATCH v3 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 <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>
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 <mattias.ronnblom@ericsson.com>
Acked-by: Bruce Richardson <bruce.richardson@intel.com>
---
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 <stdint.h>
+#include <rte_compat.h>
+
/**
* 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 e53d96d18..3d9b9b7d8 100644
--- a/lib/librte_eal/common/rte_random.c
+++ b/lib/librte_eal/common/rte_random.c
@@ -137,6 +137,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;
+}
+
static uint64_t
__rte_random_initial_seed(void)
{
diff --git a/lib/librte_eal/rte_eal_version.map b/lib/librte_eal/rte_eal_version.map
index 20c1a9018..a53a29a35 100644
--- a/lib/librte_eal/rte_eal_version.map
+++ b/lib/librte_eal/rte_eal_version.map
@@ -384,6 +384,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