| Message ID | 1378204010-27050-2-git-send-email-dborkman@redhat.com |
|---|---|
| State | Changes Requested, archived |
| Delegated to: | David Miller |
| Headers | show |
On Tue, 2013-09-03 at 12:26 +0200, Daniel Borkmann wrote: > We have implemented the same function over and over, so introduce a > generic helper net_random_N() that unifies these implementations. > It internally used net_random() which eventually resolves to > prandom_u32(). Explicit include of reciprocal_div.h is not necessary. Perhaps adding a generic helper to random.h like u32 prandom_u32_between(u32 low, u32 high); or u32 prandom_u32_range(u32 bound1, u32 bound2) would be better. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 09/03/2013 01:00 PM, Joe Perches wrote: > On Tue, 2013-09-03 at 12:26 +0200, Daniel Borkmann wrote: >> We have implemented the same function over and over, so introduce a >> generic helper net_random_N() that unifies these implementations. >> It internally used net_random() which eventually resolves to >> prandom_u32(). Explicit include of reciprocal_div.h is not necessary. > > Perhaps adding a generic helper to random.h like > u32 prandom_u32_between(u32 low, u32 high); > or > u32 prandom_u32_range(u32 bound1, u32 bound2) > would be better. Sure, this could be done as a follow-up. Once, we've migrated users to the new API, follow-ups could go ahead to do the rest, and migration will be easy. Note that the lower bound is 0 here. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, 2013-09-03 at 13:40 +0200, Daniel Borkmann wrote: > On 09/03/2013 01:00 PM, Joe Perches wrote: > > On Tue, 2013-09-03 at 12:26 +0200, Daniel Borkmann wrote: > >> We have implemented the same function over and over, so introduce a > >> generic helper net_random_N() that unifies these implementations. > >> It internally used net_random() which eventually resolves to > >> prandom_u32(). Explicit include of reciprocal_div.h is not necessary. > > > > Perhaps adding a generic helper to random.h like > > u32 prandom_u32_between(u32 low, u32 high); > > or > > u32 prandom_u32_range(u32 bound1, u32 bound2) > > would be better. > > Sure, this could be done as a follow-up. Once, we've migrated users to > the new API, follow-ups could go ahead to do the rest, and migration > will be easy. Note that the lower bound is 0 here. Part of the reason I suggested this it to make the API more readable/intelligible. At first glance, I have no idea what net_random_N does. I think #define net_random() prandom_u32() should be removed eventually as well. If gcc doesn't already do this optimization, perhaps there are also some use of net_random() % non_const that could be optimized a bit using this API. $ git grep -E "(prandom_u32|net_random)\s*\(\s*\)\s*\%" net net/batman-adv/bat_iv_ogm.c: msecs += prandom_u32() % (2 * BATADV_JITTER); net/batman-adv/bat_iv_ogm.c: return jiffies + msecs_to_jiffies(prandom_u32() % (BATADV_JITTER / 2)); net/core/neighbour.c: return base ? (net_random() % base) + (base >> 1) : 0; net/core/neighbour.c: unsigned long sched_next = now + (net_random() % p->proxy_delay); net/core/pktgen.c: flow = prandom_u32() % pkt_dev->cflows; net/core/pktgen.c: t = prandom_u32() % net/core/pktgen.c: mc = prandom_u32() % pkt_dev->src_mac_count; net/core/pktgen.c: mc = prandom_u32() % pkt_dev->dst_mac_count; net/core/pktgen.c: pkt_dev->cur_udp_src = prandom_u32() % net/core/pktgen.c: pkt_dev->cur_udp_dst = prandom_u32() % net/core/pktgen.c: t = prandom_u32() % (imx - imn) + imn; net/core/pktgen.c: t = prandom_u32() % net/core/pktgen.c: t = prandom_u32() % net/core/stream.c: current_timeo = vm_wait = (net_random() % (HZ / 5)) + 2; net/ipv4/igmp.c: int tv = net_random() % max_delay; net/ipv4/igmp.c: int tv = net_random() % in_dev->mr_maxdelay; net/ipv4/igmp.c: int tv = net_random() % delay; net/ipv4/inet_connection_sock.c: smallest_rover = rover = net_random() % remaining + low; net/ipv6/addrconf.c: rand_num = net_random() % (idev->cnf.rtr_solicit_delay ? : 1); net/ipv6/mcast.c: unsigned long tv = net_random() % idev->mc_maxdelay; net/ipv6/mcast.c: unsigned long tv = net_random() % delay; net/ipv6/mcast.c: unsigned long tv = net_random() % delay; net/ipv6/mcast.c: delay = net_random() % resptime; net/ipv6/mcast.c: delay = net_random() % unsolicited_report_interval(ma->idev); net/netfilter/nf_conntrack_core.c: (prandom_u32() % net->ct.sysctl_events_retry_timeout); net/netfilter/nf_conntrack_core.c: (prandom_u32() % net->ct.sysctl_events_retry_timeout); net/sched/act_gact.c: if (!gact->tcfg_pval || net_random() % gact->tcfg_pval) net/sched/sch_netem.c: skb->data[net_random() % skb_headlen(skb)] ^= 1<<(net_random() % 8); net/sctp/socket.c: rover = net_random() % remaining + low; net/sunrpc/xprtsock.c: unsigned short rand = (unsigned short) net_random() % range; net/xfrm/xfrm_state.c: spi = low + net_random()%(high-low+1); -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 09/03/2013 02:15 PM, Joe Perches wrote: > On Tue, 2013-09-03 at 13:40 +0200, Daniel Borkmann wrote: >> On 09/03/2013 01:00 PM, Joe Perches wrote: >>> On Tue, 2013-09-03 at 12:26 +0200, Daniel Borkmann wrote: >>>> We have implemented the same function over and over, so introduce a >>>> generic helper net_random_N() that unifies these implementations. >>>> It internally used net_random() which eventually resolves to >>>> prandom_u32(). Explicit include of reciprocal_div.h is not necessary. >>> >>> Perhaps adding a generic helper to random.h like >>> u32 prandom_u32_between(u32 low, u32 high); >>> or >>> u32 prandom_u32_range(u32 bound1, u32 bound2) >>> would be better. >> >> Sure, this could be done as a follow-up. Once, we've migrated users to >> the new API, follow-ups could go ahead to do the rest, and migration >> will be easy. Note that the lower bound is 0 here. > > Part of the reason I suggested this it to make the > API more readable/intelligible. > > At first glance, I have no idea what net_random_N does. > > I think #define net_random() prandom_u32() > should be removed eventually as well. Why? Assume there could be different PRNGs in future that have different properties (e.g. speed vs. period, etc). Then, changing net_random() to something else is way easier and less error-prone than searching through the whole subtree of net and replacing every occurrence of prandom_u32(). > If gcc doesn't already do this optimization, > perhaps there are also some use of > net_random() % non_const > that could be optimized a bit using this API. I agree with you, needs to be evaluated on a case by case basis for future work. > $ git grep -E "(prandom_u32|net_random)\s*\(\s*\)\s*\%" net > net/batman-adv/bat_iv_ogm.c: msecs += prandom_u32() % (2 * BATADV_JITTER); > net/batman-adv/bat_iv_ogm.c: return jiffies + msecs_to_jiffies(prandom_u32() % (BATADV_JITTER / 2)); > net/core/neighbour.c: return base ? (net_random() % base) + (base >> 1) : 0; > net/core/neighbour.c: unsigned long sched_next = now + (net_random() % p->proxy_delay); > net/core/pktgen.c: flow = prandom_u32() % pkt_dev->cflows; > net/core/pktgen.c: t = prandom_u32() % > net/core/pktgen.c: mc = prandom_u32() % pkt_dev->src_mac_count; > net/core/pktgen.c: mc = prandom_u32() % pkt_dev->dst_mac_count; > net/core/pktgen.c: pkt_dev->cur_udp_src = prandom_u32() % > net/core/pktgen.c: pkt_dev->cur_udp_dst = prandom_u32() % > net/core/pktgen.c: t = prandom_u32() % (imx - imn) + imn; > net/core/pktgen.c: t = prandom_u32() % > net/core/pktgen.c: t = prandom_u32() % > net/core/stream.c: current_timeo = vm_wait = (net_random() % (HZ / 5)) + 2; > net/ipv4/igmp.c: int tv = net_random() % max_delay; > net/ipv4/igmp.c: int tv = net_random() % in_dev->mr_maxdelay; > net/ipv4/igmp.c: int tv = net_random() % delay; > net/ipv4/inet_connection_sock.c: smallest_rover = rover = net_random() % remaining + low; > net/ipv6/addrconf.c: rand_num = net_random() % (idev->cnf.rtr_solicit_delay ? : 1); > net/ipv6/mcast.c: unsigned long tv = net_random() % idev->mc_maxdelay; > net/ipv6/mcast.c: unsigned long tv = net_random() % delay; > net/ipv6/mcast.c: unsigned long tv = net_random() % delay; > net/ipv6/mcast.c: delay = net_random() % resptime; > net/ipv6/mcast.c: delay = net_random() % unsolicited_report_interval(ma->idev); > net/netfilter/nf_conntrack_core.c: (prandom_u32() % net->ct.sysctl_events_retry_timeout); > net/netfilter/nf_conntrack_core.c: (prandom_u32() % net->ct.sysctl_events_retry_timeout); > net/sched/act_gact.c: if (!gact->tcfg_pval || net_random() % gact->tcfg_pval) > net/sched/sch_netem.c: skb->data[net_random() % skb_headlen(skb)] ^= 1<<(net_random() % 8); > net/sctp/socket.c: rover = net_random() % remaining + low; > net/sunrpc/xprtsock.c: unsigned short rand = (unsigned short) net_random() % range; > net/xfrm/xfrm_state.c: spi = low + net_random()%(high-low+1); > > -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, 2013-09-03 at 14:26 +0200, Daniel Borkmann wrote: > On 09/03/2013 02:15 PM, Joe Perches wrote: > > I think #define net_random() prandom_u32() > > should be removed eventually as well. > > Why? Assume there could be different PRNGs in future that have different properties > (e.g. speed vs. period, etc). Then, changing net_random() to something else is way > easier and less error-prone than searching through the whole subtree of net and > replacing every occurrence of prandom_u32(). Maybe. There are already instances of prandom_u32 in the net tree. I don't find value in the indirection. Akinobu Mita once posted a s/net_random/prandom_u32/ patch: https://lkml.org/lkml/2012/12/23/140 > > If gcc doesn't already do this optimization, > > perhaps there are also some use of > > net_random() % non_const > > that could be optimized a bit using this API. > > I agree with you, needs to be evaluated on a case by case basis for future work. __builtin_constant_p is useful. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, 2013-09-03 at 12:26 +0200, Daniel Borkmann wrote: > We have implemented the same function over and over, so introduce a > generic helper net_random_N() that unifies these implementations. > It internally used net_random() which eventually resolves to > prandom_u32(). Explicit include of reciprocal_div.h is not necessary. > > Signed-off-by: Daniel Borkmann <dborkman@redhat.com> > --- It was private, so the name was whatever we chose at that time. If we want to make it generic, why still doing a net_something() ? Really this patch should be discussed on lkml and netdev and we should use a generic name. -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/drivers/net/team/team_mode_random.c b/drivers/net/team/team_mode_random.c index 7f032e2..b2294f8 100644 --- a/drivers/net/team/team_mode_random.c +++ b/drivers/net/team/team_mode_random.c @@ -16,17 +16,12 @@ #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 = net_random_N(team->en_port_count); port = team_get_port_by_index_rcu(team, port_index); if (unlikely(!port)) goto drop; diff --git a/include/linux/net.h b/include/linux/net.h index 4f27575..86ffce7 100644 --- a/include/linux/net.h +++ b/include/linux/net.h @@ -24,6 +24,7 @@ #include <linux/fcntl.h> /* For O_CLOEXEC and O_NONBLOCK */ #include <linux/kmemcheck.h> #include <linux/rcupdate.h> +#include <linux/reciprocal_div.h> #include <uapi/linux/net.h> struct poll_table_struct; @@ -243,6 +244,12 @@ do { \ #define net_random() prandom_u32() #define net_srandom(seed) prandom_seed((__force u32)(seed)) +/* deliver a random number between 0 and N - 1 */ +static inline u32 net_random_N(u32 N) +{ + return reciprocal_divide(net_random(), N); +} + extern int kernel_sendmsg(struct socket *sock, struct msghdr *msg, struct kvec *vec, size_t num, size_t len); extern int kernel_recvmsg(struct socket *sock, struct msghdr *msg, diff --git a/include/net/red.h b/include/net/red.h index ef46058..b17ed60 100644 --- a/include/net/red.h +++ b/include/net/red.h @@ -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 net_random_N(p->max_P_reciprocal); } static inline int red_mark_probability(const struct red_parms *p, diff --git a/net/802/garp.c b/net/802/garp.c index 5d9630a..c6fe7ca 100644 --- a/net/802/garp.c +++ b/net/802/garp.c @@ -397,7 +397,7 @@ 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 = net_random_N(msecs_to_jiffies(garp_join_time)); mod_timer(&app->join_timer, jiffies + delay); } diff --git a/net/802/mrp.c b/net/802/mrp.c index 1eb05d8..7338a7c 100644 --- a/net/802/mrp.c +++ b/net/802/mrp.c @@ -578,7 +578,7 @@ 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 = net_random_N(msecs_to_jiffies(mrp_join_time)); mod_timer(&app->join_timer, jiffies + delay); } diff --git a/net/packet/af_packet.c b/net/packet/af_packet.c index 2e8286b..7ac669e 100644 --- a/net/packet/af_packet.c +++ b/net/packet/af_packet.c @@ -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 net_random_N(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 ef53ab8..e19b20be 100644 --- a/net/sched/sch_choke.c +++ b/net/sched/sch_choke.c @@ -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 + net_random_N(choke_len(q))) & q->tab_mask; skb = q->tab[*pidx]; if (skb) return skb;
We have implemented the same function over and over, so introduce a generic helper net_random_N() that unifies these implementations. It internally used net_random() which eventually resolves to prandom_u32(). Explicit include of reciprocal_div.h is not necessary. Signed-off-by: Daniel Borkmann <dborkman@redhat.com> --- drivers/net/team/team_mode_random.c | 7 +------ include/linux/net.h | 7 +++++++ include/net/red.h | 2 +- net/802/garp.c | 2 +- net/802/mrp.c | 2 +- net/packet/af_packet.c | 2 +- net/sched/sch_choke.c | 8 +------- 7 files changed, 13 insertions(+), 17 deletions(-)