prandom_u32_range, prandom_u32_max helpers
Subsystems (6)
v2 cover prandom_u32_range, prandom_u32_max helpers
v1->v2:
- migrated api to random.h, ccing lkml
- dropped second patch for now
Daniel Borkmann (2):
random: add prandom_u32_range and prandom_u32_max helpers
net: migrate direct users to prandom_u32_max
drivers/net/team/team_mode_random.c | 8 +------- include/linux/random.h | 31 ++++++++++++++++++++++++++++++- include/net/red.h | 2 +- net/802/garp.c | 3 ++- net/802/mrp.c | 3 ++- net/packet/af_packet.c | 2 +- net/sched/sch_choke.c | 8 +------- 7 files changed, 38 insertions(+), 19 deletions(-)
Signature · 1 line
1.7.11.7
PATCH v2 1/2 random: add prandom_u32_range and prandom_u32_max helpers
We have implemented the same function over and over, so introduce generic helpers that unify these implementations in order to migrate such code to use them. Make the API similarly to randomize_range() for consistency. prandom_u32_range() generates numbers in [start, end] interval and prandom_u32_max() generates numbers in [0, end] interval.
--- include/linux/random.h | 31 ++++++++++++++++++++++++++++++- 1 file changed, 30 insertions(+), 1 deletion(-)
include/linux/random.h +30 -1
@@ -8,7 +8,6 @@#include <uapi/linux/random.h> -extern void add_device_randomness (const void *,unsigned int );extern void add_input_randomness (unsigned int type,unsigned int code,unsigned int value);
@@ -32,6 +31,36 @@ void prandom_seed(u32 seed);u32 prandom_u32_state (struct rnd_state *);void prandom_bytes_state (struct rnd_state *state,void *buf,int nbytes); +/** +* prandom_u32_range - return a random number in interval [start, end] +* @start: lower interval endpoint +* @end: higher interval endpoint +* +* Returns a number that is in the given interval: +* +* [...... <range> .....] +* start end +* +* Callers need to make sure that start <= end. Note that the result +* depends on PRNG being well distributed in [0, ~0U] space. Here we +* use maximally equidistributed combined Tausworthe generator. +*/ +static inline u32 prandom_u32_range (u32 start,u32 end) +{ +return (u32)(((u64 )prandom_u32 () * (end +1 - start)) >>32 ) + start; +} + +/** +* prandom_u32_max - return a random number in interval [0, max] +* @max: higher interval endpoint +* +* Returns a number that is in interval [0, end]. +*/ +static inline u32 prandom_u32_max (u32 end) +{ +return prandom_u32_range (0 , end); +} +/* * Handle minimum values for seeds */
Signature · 1 line
1.7.11.7
Re: [PATCH net-next v2 1/2] random: add prandom_u32_range and prandom_u32_max helpers
Quoted 5 lines · Daniel Borkmann
We have implemented the same function over and over, so introduce generic helpers that unify these implementations in order to migrate such code to use them. Make the API similarly to
randomize_range()for consistency.prandom_u32_range()generates numbers in [start, end] interval andprandom_u32_max()generates numbers in [0, end] interval.
I think these helpers can in many cases cause poorer compiler generated object code.
Quoted 8 lines
include/linux/random.h +8
-0+/** +* prandom_u32_range - return a random number in interval [start, end] +* @start: lower interval endpoint +* @end: higher interval endpoint +* +* Returns a number that is in the given interval: +* +* [...... <range> .....]
include/linux/random.h void prandom_seed(u32 seed); · line 51
Quoted 10 lines
include/linux/random.h +10
-0+* start end +* +* Callers need to make sure that start <= end. Note that the result +* depends on PRNG being well distributed in [0, ~0U] space. Here we +* use maximally equidistributed combined Tausworthe generator. +*/ +static inline u32 prandom_u32_range (u32 start,u32 end) +{ +return (u32)(((u64 )prandom_u32 () * (end +1 - start)) >>32 ) + start; +}
This is effectively:
return (prandom_u32() % (end - start)) + start;
and if start and end are constant, gcc can optimize the division by constant to a 32 bit multiply/shift/add.
I think if you add __builtin_constant_p tests for start and end and expand the code a little you can still get the optimizations done.
PATCH v2 2/2 net: migrate direct users to prandom_u32_max
In reply to Daniel BorkmannUsers that directly use or reimplement what we have in prandom_u32_max() can be migrated for now to use it directly, so that we can reduce code size and avoid reimplementations. That's obvious, follow-up patches could inspect modulo use cases for possible migration as well.
--- drivers/net/team/team_mode_random.c | 8 +------- include/net/red.h | 2 +- net/802/garp.c | 3 ++- net/802/mrp.c | 3 ++- net/packet/af_packet.c | 2 +- net/sched/sch_choke.c | 8 +------- 6 files changed, 8 insertions(+), 18 deletions(-)
drivers/net/team/team_mode_random.c +1 -7
@@ -13,20 +13,14 @@#include <linux/module.h> #include <linux/init.h> #include <linux/skbuff.h> -#include <linux/reciprocal_div.h> #include <linux/if_team.h> -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 -1 ); port =team_get_port_by_index_rcu (team, port_index);if (unlikely (!port)) goto drop;
include/net/red.h +1 -1
@@ -303,7 +303,7 @@ static inline unsigned long red_calc_qavg(const struct red_parms *p,static inline u32 red_random (const struct red_parms *p) { -return reciprocal_divide (net_random (), p->max_P_reciprocal); +return prandom_u32_max (p->max_P_reciprocal -1 ); } static inline int red_mark_probability(const struct red_parms *p,
net/802/garp.c +2 -1
@@ -397,7 +397,8 @@ static void garp_join_timer_arm(struct garp_applicant *app) {unsigned long delay; - delay = (u64 )msecs_to_jiffies (garp_join_time) *net_random () >>32 ; + delay =prandom_u32_max (msecs_to_jiffies (garp_join_time) -1 ); +mod_timer (&app->join_timer, jiffies + delay); }
net/802/mrp.c +2 -1
@@ -578,7 +578,8 @@ static void mrp_join_timer_arm(struct mrp_applicant *app) {unsigned long delay; - delay = (u64 )msecs_to_jiffies (mrp_join_time) *net_random () >>32 ; + delay =prandom_u32_max (msecs_to_jiffies (mrp_join_time) -1 ); +mod_timer (&app->join_timer, jiffies + delay); }
net/packet/af_packet.c +1 -1
@@ -1162,7 +1162,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 -1 ); } static unsigned int fanout_demux_rollover(struct packet_fanout *f,
net/sched/sch_choke.c +1 -7
@@ -77,12 +77,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 +227,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) - 1)) & q->tab_mask; skb = q->tab[*pidx]; if (skb) return skb;
Signature · 1 line
1.7.11.7
Re: [PATCH net-next v2 2/2] net: migrate direct users to prandom_u32_max
Quoted 28 lines · Daniel Borkmann
Users that directly use or reimplement what we have in
prandom_u32_max()can be migrated for now to use it directly, so that we can reduce code size and avoid reimplementations. That's obvious, follow-up patches could inspect modulo use cases for possible migration as well.Signed-off-by Daniel Borkmann <[email protected]>--- drivers/net/team/team_mode_random.c | 8 +------- include/net/red.h | 2 +- net/802/garp.c | 3 ++- net/802/mrp.c | 3 ++- net/packet/af_packet.c | 2 +- net/sched/sch_choke.c | 8 +------- 6 files changed, 8 insertions(+), 18 deletions(-)drivers/net/team/team_mode_random.c +0
-3@@ -13,20 +13,14 @@#include <linux/module.h> #include <linux/init.h> #include <linux/skbuff.h> -#include <linux/reciprocal_div.h> #include <linux/if_team.h> -static u32 random_N (unsigned int N ) -{
drivers/net/team/team_mode_random.c line 23
Quoted 10 lines
drivers/net/team/team_mode_random.c +1
-4-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 -1 );
Note the random_N(0) gave 0, while prandom_u32_max(0 - 1) can return any number in [0 ... ~0U]
Re: [PATCH net-next v2 2/2] net: migrate direct users to prandom_u32_max
Quoted 37 lines · Eric Dumazet
Quoted 36 lines · Daniel Borkmann
Users that directly use or reimplement what we have in
prandom_u32_max()can be migrated for now to use it directly, so that we can reduce code size and avoid reimplementations. That's obvious, follow-up patches could inspect modulo use cases for possible migration as well.Signed-off-by Daniel Borkmann <[email protected]>--- drivers/net/team/team_mode_random.c | 8 +------- include/net/red.h | 2 +- net/802/garp.c | 3 ++- net/802/mrp.c | 3 ++- net/packet/af_packet.c | 2 +- net/sched/sch_choke.c | 8 +------- 6 files changed, 8 insertions(+), 18 deletions(-)drivers/net/team/team_mode_random.c +0
-6@@ -13,20 +13,14 @@#include <linux/module.h> #include <linux/init.h> #include <linux/skbuff.h> -#include <linux/reciprocal_div.h> #include <linux/if_team.h> -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;
Quoted 6 lines
drivers/net/team/team_mode_random.c line 23
Quoted 2 lines
drivers/net/team/team_mode_random.c +1
-1- port_index =random_N (team->en_port_count); + port_index =prandom_u32_max (team->en_port_count -1 );Note the
random_N(0)gave 0, whileprandom_u32_max(0 - 1)can return any number in [0 ... ~0U]
Very true, that was stupid. Thanks for catching!