From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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=20R=C3=B6nnblom?= To: CC: =?UTF-8?q?Mattias=20R=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 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit 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: , X-List-Received-Date: Mon, 08 Apr 2019 12:30:50 -0000 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; -- 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 169CDA0096 for ; Mon, 8 Apr 2019 14:30:54 +0200 (CEST) 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=20R=C3=B6nnblom?= To: CC: =?UTF-8?q?Mattias=20R=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 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8bit 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" Message-ID: <20190408123029.xVZ_INXtEL8KwSMgn94151V7tc77WliPkOj0ce2b9n4@z> 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; -- 2.17.1