From patchwork Fri Aug 12 13:30:53 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tim Gardner X-Patchwork-Id: 658640 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from huckleberry.canonical.com (huckleberry.canonical.com [91.189.94.19]) by ozlabs.org (Postfix) with ESMTP id 3s9m4T3mV4z9sXy; Fri, 12 Aug 2016 23:31:21 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=canonical-com.20150623.gappssmtp.com header.i=@canonical-com.20150623.gappssmtp.com header.b=FGy7Sh27; dkim-atps=neutral Received: from localhost ([127.0.0.1] helo=huckleberry.canonical.com) by huckleberry.canonical.com with esmtp (Exim 4.76) (envelope-from ) id 1bYCYR-0003dO-3P; Fri, 12 Aug 2016 13:31:19 +0000 Received: from mail-pf0-f175.google.com ([209.85.192.175]) by huckleberry.canonical.com with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.76) (envelope-from ) id 1bYCYF-0003Vj-Ow for kernel-team@lists.ubuntu.com; Fri, 12 Aug 2016 13:31:08 +0000 Received: by mail-pf0-f175.google.com with SMTP id p64so9295701pfb.1 for ; Fri, 12 Aug 2016 06:31:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=canonical-com.20150623.gappssmtp.com; s=20150623; h=from:to:subject:date:message-id:in-reply-to:references; bh=dAFXiTv25Eu6Ps0pQOtehLxQlpcEdhxyH3yrFken/8s=; b=FGy7Sh27xBwn6JoxaIil5HH4jZM+ww5EzXFX5i7ycxAX3Ib/lDTnNP+Ik8GW8iyQJN hpSaLGvh7Z++O1avQyDzN2YLoBTlpo2ane4EysWGCmGGbTUQyLKHnZVO7DeW+yYpBieH Y6nAUuPgimsfQUoWZV2TIsExc+1kN8RZklgGPdm8O0LX9EcTIXv1cRFiyPfUxUBoKayI XwNUjoMfXbT9WUUQ4SZdZdXb3t1CLS921aOEnfGviE1fHJqE1m5Eu1hZGGhpvRUYkWuX TO+wo0uSDQJt5xefvy8irWFddRmrYCjtyAkaxpAEpRDieHJxleXxJkv0N0rPaEUrAOA9 Yiig== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=dAFXiTv25Eu6Ps0pQOtehLxQlpcEdhxyH3yrFken/8s=; b=OGljC/8/UlsRKNOI1Y5zIOxoNpADfTvS7fs+tA21jm1+eDGH65FDszStPFyHVpI6DC 4nXTJH6bxP3rQ+yU/p3QFFe9kTQiBXfeRJ+imYoZOPSOlmG95ybvEuBrUq+OVXZmkleF oiQ+Rj/6JuI5r3g1sWI2kCBzfQC4K1dBX5T+QIW3ZbiwX1IxLi6U3cnhFg65muh55UZh OfV/jZZEc54UlF5c8DG5kvnpXWWjP/GUvU3GJ+Iwe6051/gWRUfrEH5zv113ODWf/qUw Xgi8dGnn0sEMKHpcmjg+LfxtOwQtDhsnh5OzUQBdxVgjKiyHboMaa7I1BxMAXlNvv6up v+hA== X-Gm-Message-State: AEkoouuOWSGiGEbE1IVhSE8FHuR412bIe10qKDewP19BjuTD8M9gTkDiPIaENCiOSHWjvFUO X-Received: by 10.98.92.65 with SMTP id q62mr27284633pfb.70.1471008666125; Fri, 12 Aug 2016 06:31:06 -0700 (PDT) Received: from localhost.localdomain (host-174-45-44-32.hln-mt.client.bresnan.net. [174.45.44.32]) by smtp.gmail.com with ESMTPSA id q26sm13270847pfj.53.2016.08.12.06.31.05 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 12 Aug 2016 06:31:05 -0700 (PDT) From: Tim Gardner To: kernel-team@lists.ubuntu.com Subject: [PATCH 3/4] random32: add prandom_u32_max and convert open coded users Date: Fri, 12 Aug 2016 07:30:53 -0600 Message-Id: <1471008654-28755-4-git-send-email-tim.gardner@canonical.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1471008654-28755-1-git-send-email-tim.gardner@canonical.com> References: <56dc5289-a906-8574-8401-60291e63d2cc@canonical.com> <1471008654-28755-1-git-send-email-tim.gardner@canonical.com> X-BeenThere: kernel-team@lists.ubuntu.com X-Mailman-Version: 2.1.14 Precedence: list List-Id: Kernel team discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: kernel-team-bounces@lists.ubuntu.com Sender: kernel-team-bounces@lists.ubuntu.com From: Daniel Borkmann Many functions have open coded a function that returns a random number in range [0,N-1]. Under the assumption that we have a PRNG such as taus113 with being well distributed in [0, ~0U] space, we can implement such a function as uword t = (n*m')>>32, where m' is a random number obtained from PRNG, n the right open interval border and t our resulting random number, with n,m',t in u32 universe. Lets go with Joe and simply call it prandom_u32_max(), although technically we have an right open interval endpoint, but that we have documented. Other users can further be migrated to the new prandom_u32_max() function later on; for now, we need to make sure to migrate reciprocal_divide() users for the reciprocal_divide() follow-up fixup since their function signatures are going to change. Joint work with Hannes Frederic Sowa. Cc: Jakub Zawadzki Cc: Eric Dumazet Cc: linux-kernel@vger.kernel.org Signed-off-by: Hannes Frederic Sowa Signed-off-by: Daniel Borkmann Signed-off-by: David S. Miller (cherry picked from commit f337db64af059c9a94278a8b0ab97d87259ff62f) Signed-off-by: Tim Gardner --- drivers/net/team/team_mode_random.c | 8 +------- include/linux/random.h | 18 +++++++++++++++++- net/packet/af_packet.c | 2 +- net/sched/sch_choke.c | 9 +-------- 4 files changed, 20 insertions(+), 17 deletions(-) diff --git a/drivers/net/team/team_mode_random.c b/drivers/net/team/team_mode_random.c index 7f032e2..cd2f692 100644 --- a/drivers/net/team/team_mode_random.c +++ b/drivers/net/team/team_mode_random.c @@ -13,20 +13,14 @@ #include #include #include -#include #include -static u32 random_N(unsigned int N) -{ - return reciprocal_divide(prandom_u32(), N); -} - static bool rnd_transmit(struct team *team, struct sk_buff *skb) { struct team_port *port; int port_index; - port_index = random_N(team->en_port_count); + port_index = prandom_u32_max(team->en_port_count); port = team_get_port_by_index_rcu(team, port_index); if (unlikely(!port)) goto drop; diff --git a/include/linux/random.h b/include/linux/random.h index 4002b3d..1cfce0e 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -8,7 +8,6 @@ #include - extern void add_device_randomness(const void *, unsigned int); extern void add_input_randomness(unsigned int type, unsigned int code, unsigned int value); @@ -38,6 +37,23 @@ struct rnd_state { u32 prandom_u32_state(struct rnd_state *state); void prandom_bytes_state(struct rnd_state *state, void *buf, int nbytes); +/** + * prandom_u32_max - returns a pseudo-random number in interval [0, ep_ro) + * @ep_ro: right open interval endpoint + * + * Returns a pseudo-random number that is in interval [0, ep_ro). Note + * that the result depends on PRNG being well distributed in [0, ~0U] + * u32 space. Here we use maximally equidistributed combined Tausworthe + * generator, that is, prandom_u32(). This is useful when requesting a + * random index of an array containing ep_ro elements, for example. + * + * Returns: pseudo-random number in interval [0, ep_ro) + */ +static inline u32 prandom_u32_max(u32 ep_ro) +{ + return (u32)(((u64) prandom_u32() * ep_ro) >> 32); +} + /* * Handle minimum values for seeds */ diff --git a/net/packet/af_packet.c b/net/packet/af_packet.c index e3070e6..b2b2d81 100644 --- a/net/packet/af_packet.c +++ b/net/packet/af_packet.c @@ -1177,7 +1177,7 @@ static unsigned int fanout_demux_rnd(struct packet_fanout *f, struct sk_buff *skb, unsigned int num) { - return reciprocal_divide(prandom_u32(), num); + return prandom_u32_max(num); } static unsigned int fanout_demux_rollover(struct packet_fanout *f, diff --git a/net/sched/sch_choke.c b/net/sched/sch_choke.c index ddd73cb..2aee028 100644 --- a/net/sched/sch_choke.c +++ b/net/sched/sch_choke.c @@ -14,7 +14,6 @@ #include #include #include -#include #include #include #include @@ -77,12 +76,6 @@ struct choke_sched_data { struct sk_buff **tab; }; -/* deliver a random number between 0 and N - 1 */ -static u32 random_N(unsigned int N) -{ - return reciprocal_divide(prandom_u32(), N); -} - /* number of elements in queue including holes */ static unsigned int choke_len(const struct choke_sched_data *q) { @@ -233,7 +226,7 @@ static struct sk_buff *choke_peek_random(const struct choke_sched_data *q, int retrys = 3; do { - *pidx = (q->head + random_N(choke_len(q))) & q->tab_mask; + *pidx = (q->head + prandom_u32_max(choke_len(q))) & q->tab_mask; skb = q->tab[*pidx]; if (skb) return skb;