diff options
author | Daniel Borkmann <dborkman@redhat.com> | 2014-01-21 20:29:39 -0500 |
---|---|---|
committer | David S. Miller <davem@davemloft.net> | 2014-01-22 02:17:20 -0500 |
commit | f337db64af059c9a94278a8b0ab97d87259ff62f (patch) | |
tree | ef7db2258d5929760f2a22b74779d374916634bd /net/sched | |
parent | 6cd28f044b47aeeba91807d97d6f3ea5a048e88d (diff) |
random32: add prandom_u32_max and convert open coded users
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 <darkjames-ws@darkjames.pl>
Cc: Eric Dumazet <eric.dumazet@gmail.com>
Cc: linux-kernel@vger.kernel.org
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/sched')
-rw-r--r-- | net/sched/sch_choke.c | 9 |
1 files changed, 1 insertions, 8 deletions
diff --git a/net/sched/sch_choke.c b/net/sched/sch_choke.c index ddd73cb2d7ba..2aee02802c27 100644 --- a/net/sched/sch_choke.c +++ b/net/sched/sch_choke.c | |||
@@ -14,7 +14,6 @@ | |||
14 | #include <linux/types.h> | 14 | #include <linux/types.h> |
15 | #include <linux/kernel.h> | 15 | #include <linux/kernel.h> |
16 | #include <linux/skbuff.h> | 16 | #include <linux/skbuff.h> |
17 | #include <linux/reciprocal_div.h> | ||
18 | #include <linux/vmalloc.h> | 17 | #include <linux/vmalloc.h> |
19 | #include <net/pkt_sched.h> | 18 | #include <net/pkt_sched.h> |
20 | #include <net/inet_ecn.h> | 19 | #include <net/inet_ecn.h> |
@@ -77,12 +76,6 @@ struct choke_sched_data { | |||
77 | struct sk_buff **tab; | 76 | struct sk_buff **tab; |
78 | }; | 77 | }; |
79 | 78 | ||
80 | /* deliver a random number between 0 and N - 1 */ | ||
81 | static u32 random_N(unsigned int N) | ||
82 | { | ||
83 | return reciprocal_divide(prandom_u32(), N); | ||
84 | } | ||
85 | |||
86 | /* number of elements in queue including holes */ | 79 | /* number of elements in queue including holes */ |
87 | static unsigned int choke_len(const struct choke_sched_data *q) | 80 | static unsigned int choke_len(const struct choke_sched_data *q) |
88 | { | 81 | { |
@@ -233,7 +226,7 @@ static struct sk_buff *choke_peek_random(const struct choke_sched_data *q, | |||
233 | int retrys = 3; | 226 | int retrys = 3; |
234 | 227 | ||
235 | do { | 228 | do { |
236 | *pidx = (q->head + random_N(choke_len(q))) & q->tab_mask; | 229 | *pidx = (q->head + prandom_u32_max(choke_len(q))) & q->tab_mask; |
237 | skb = q->tab[*pidx]; | 230 | skb = q->tab[*pidx]; |
238 | if (skb) | 231 | if (skb) |
239 | return skb; | 232 | return skb; |