net_random_N, reciprocal_divide helper updates
Subsystems (8)
cover net_random_N, reciprocal_divide helper updates
Introduce a net_random_N() helper instead of reimplementing it over and over, plus use reciprocal_divide() helper instead of reimplementing it as well.
Daniel Borkmann (2):
net: introduce generic net_random_N helper
net: use reciprocal_divide instead of reimplementing it
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/core/dev.c | 2 +- net/core/flow_dissector.c | 5 ++--- net/ipv4/inet_hashtables.c | 2 +- net/ipv4/netfilter/ipt_CLUSTERIP.c | 2 +- net/ipv4/udp.c | 6 +++--- net/ipv6/inet6_hashtables.c | 2 +- net/ipv6/udp.c | 4 ++-- net/netfilter/nf_conntrack_core.c | 2 +- net/netfilter/nf_conntrack_expect.c | 2 +- net/netfilter/nf_nat_core.c | 4 ++-- net/netfilter/xt_HMARK.c | 2 +- net/netfilter/xt_NFQUEUE.c | 4 ++-- net/netfilter/xt_cluster.c | 2 +- net/netfilter/xt_hashlimit.c | 2 +- net/packet/af_packet.c | 2 +- net/sched/sch_choke.c | 8 +------- net/sched/sch_fq_codel.c | 2 +- 22 files changed, 34 insertions(+), 39 deletions(-)
Signature · 1 line
1.7.11.7
PATCH 1/2 net: introduce generic net_random_N helper
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.
--- 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(-)
drivers/net/team/team_mode_random.c +1 -6
@@ -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;
include/linux/net.h +7 -0
@@ -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,
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 net_random_N (p->max_P_reciprocal); } static inline int red_mark_probability(const struct red_parms *p,
net/802/garp.c +1 -1
@@ -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); }
net/802/mrp.c +1 -1
@@ -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); }
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 net_random_N (num); } 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 + net_random_N(choke_len(q))) & q->tab_mask; skb = q->tab[*pidx]; if (skb) return skb;
Signature · 1 line
1.7.11.7
Re: [PATCH net-next 1/2] net: introduce generic net_random_N helper
Quoted 4 lines · Daniel Borkmann
We have implemented the same function over and over, so introduce a generic helper
net_random_N()that unifies these implementations. It internally usednet_random()which eventually resolves toprandom_u32(). Explicit include ofreciprocal_div.his 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.
Re: [PATCH net-next 1/2] net: introduce generic net_random_N helper
Quoted 11 lines · Joe Perches
Quoted 4 lines · Daniel Borkmann
We have implemented the same function over and over, so introduce a generic helper
net_random_N()that unifies these implementations. It internally usednet_random()which eventually resolves toprandom_u32(). Explicit include ofreciprocal_div.his not necessary.Perhaps adding a generic helper to
random.hlikeu32 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.
Re: [PATCH net-next 1/2] net: introduce generic net_random_N helper
Quoted 13 lines · Daniel Borkmann
Quoted 11 lines · Joe Perches
Quoted 4 lines · Daniel Borkmann
We have implemented the same function over and over, so introduce a generic helper
net_random_N()that unifies these implementations. It internally usednet_random()which eventually resolves toprandom_u32(). Explicit include ofreciprocal_div.his not necessary.Perhaps adding a generic helper to
random.hlikeu32 prandom_u32_between(u32 low, u32 high); or u32 prandom_u32_range(u32 bound1, u32 bound2)would be better.
Quoted 3 lines
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);
Re: [PATCH net-next 1/2] net: introduce generic net_random_N helper
Quoted 18 lines · Joe Perches
Quoted 13 lines · Daniel Borkmann
Quoted 11 lines · Joe Perches
Quoted 4 lines · Daniel Borkmann
We have implemented the same function over and over, so introduce a generic helper
net_random_N()that unifies these implementations. It internally usednet_random()which eventually resolves toprandom_u32(). Explicit include ofreciprocal_div.his not necessary.Perhaps adding a generic helper to
random.hlikeu32 prandom_u32_between(u32 low, u32 high); or u32 prandom_u32_range(u32 bound1, u32 bound2)would be better.
Quoted 3 lines
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.
Quoted 7 lines
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_Ndoes.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().
Quoted 4 lines
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.
Quoted 34 lines
$ 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);
Re: [PATCH net-next 1/2] net: introduce generic net_random_N helper
Quoted 8 lines · Daniel Borkmann
Quoted 2 lines · Joe Perches
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 ofprandom_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
Quoted 6 lines
Quoted 4 lines
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.
Re: [PATCH net-next 1/2] net: introduce generic net_random_N helper
In reply to Daniel BorkmannQuoted 7 lines · Daniel Borkmann
We have implemented the same function over and over, so introduce a generic helper
net_random_N()that unifies these implementations. It internally usednet_random()which eventually resolves toprandom_u32(). Explicit include ofreciprocal_div.his not necessary.Signed-off-by Daniel Borkmann <[email protected]>---
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.
PATCH 2/2 net: use reciprocal_divide instead of reimplementing it
In reply to Daniel BorkmannReplace these places with reciprocal_divide() inline function instead of reimplementing it each time, thus it will become easier to read. We do not need to explicitly include its header as it's pulled in from linux/net.h anyway.
--- net/core/dev.c | 2 +- net/core/flow_dissector.c | 5 ++--- net/ipv4/inet_hashtables.c | 2 +- net/ipv4/netfilter/ipt_CLUSTERIP.c | 2 +- net/ipv4/udp.c | 6 +++--- net/ipv6/inet6_hashtables.c | 2 +- net/ipv6/udp.c | 4 ++-- net/netfilter/nf_conntrack_core.c | 2 +- net/netfilter/nf_conntrack_expect.c | 2 +- net/netfilter/nf_nat_core.c | 4 ++-- net/netfilter/xt_HMARK.c | 2 +- net/netfilter/xt_NFQUEUE.c | 4 ++-- net/netfilter/xt_cluster.c | 2 +- net/netfilter/xt_hashlimit.c | 2 +- net/sched/sch_fq_codel.c | 2 +- 15 files changed, 21 insertions(+), 22 deletions(-)
net/core/dev.c +1 -1
@@ -3040,7 +3040,7 @@ static int get_rps_cpu(struct net_device *dev, struct sk_buff *skb, }if (map) { - tcpu = map->cpus[((u64 ) skb->rxhash * map->len) >>32 ]; + tcpu = map->cpus[reciprocal_divide (skb->rxhash, map->len)];if (cpu_online (tcpu)) { cpu = tcpu;
net/core/flow_dissector.c +2 -3
@@ -233,7 +233,7 @@ u16 __skb_tx_hash(const struct net_device *dev, const struct sk_buff *skb, hash = (__force u16 ) skb->protocol; hash =jhash_1word (hash, hashrnd); -return (u16) (((u64 ) hash * qcount) >>32 ) + qoffset; +return (u16 )reciprocal_divide (hash, qcount) + qoffset; }EXPORT_SYMBOL (__skb_tx_hash);
@@ -324,8 +324,7 @@ static inline int get_xps_queue(struct net_device *dev, struct sk_buff *skb) hash = (__force u16 ) skb->protocol ^ skb->rxhash; hash =jhash_1word (hash, hashrnd); - queue_index = map->queues[ - ((u64 )hash * map->len) >>32 ]; + queue_index = map->queues[reciprocal_divide (hash, map->len)]; }if (unlikely (queue_index >= dev->real_num_tx_queues)) queue_index =-1 ;
net/ipv4/inet_hashtables.c +1 -1
@@ -204,7 +204,7 @@ begin: } }else if (score == hiscore && reuseport) { matches++; -if (((u64 )phash * matches) >>32 ==0 ) +if (reciprocal_divide (phash, matches) ==0 ) result = sk; phash =next_pseudo_random32 (phash); }
net/ipv4/netfilter/ipt_CLUSTERIP.c +1 -1
@@ -273,7 +273,7 @@ clusterip_hashfn(const struct sk_buff *skb, }/* node numbers are 1..n, not 0..n */ -return (((u64 )hashval * config->num_total_nodes) >>32 ) +1 ; +return reciprocal_divide (hashval, config->num_total_nodes) +1 ; } static inline int
net/ipv4/udp.c +3 -3
@@ -223,7 +223,7 @@ int udp_lib_get_port(struct sock *sk, unsigned short snum, remaining = (high - low) +1 ; rand =net_random (); - first = (((u64 )rand * remaining) >>32 ) + low; + first =reciprocal_divide (rand, remaining) + low;/* * force rand to be an odd multiple of UDP_HTABLE_SIZE */
@@ -435,7 +435,7 @@ begin: } }else if (score == badness && reuseport) { matches++; -if (((u64 )hash * matches) >>32 ==0 ) +if (reciprocal_divide (hash, matches) ==0 ) result = sk; hash =next_pseudo_random32 (hash); }
@@ -516,7 +516,7 @@ begin: } }else if (score == badness && reuseport) { matches++; -if (((u64 )hash * matches) >>32 ==0 ) +if (reciprocal_divide (hash, matches) ==0 ) result = sk; hash =next_pseudo_random32 (hash); }
net/ipv6/inet6_hashtables.c +1 -1
@@ -187,7 +187,7 @@ begin: } }else if (score == hiscore && reuseport) { matches++; -if (((u64 )phash * matches) >>32 ==0 ) +if (reciprocal_divide (phash, matches) ==0 ) result = sk; phash =next_pseudo_random32 (phash); }
net/ipv6/udp.c +2 -2
@@ -226,7 +226,7 @@ begin: goto exact_match; }else if (score == badness && reuseport) { matches++; -if (((u64 )hash * matches) >>32 ==0 ) +if (reciprocal_divide (hash, matches) ==0 ) result = sk; hash =next_pseudo_random32 (hash); }
@@ -306,7 +306,7 @@ begin: } }else if (score == badness && reuseport) { matches++; -if (((u64 )hash * matches) >>32 ==0 ) +if (reciprocal_divide (hash, matches) ==0 ) result = sk; hash =next_pseudo_random32 (hash); }
net/netfilter/nf_conntrack_core.c +1 -1
@@ -97,7 +97,7 @@ static u32 hash_conntrack_raw(const struct nf_conntrack_tuple *tuple, u16 zone)static u32 __hash_bucket (u32 hash,unsigned int size) { -return ((u64 )hash * size) >>32 ; +return reciprocal_divide (hash, size); }static u32 hash_bucket (u32 hash,const struct net *net)
net/netfilter/nf_conntrack_expect.c +1 -1
@@ -83,7 +83,7 @@ static unsigned int nf_ct_expect_dst_hash(const struct nf_conntrack_tuple *tuple hash =jhash2 (tuple->dst.u3.all,ARRAY_SIZE (tuple->dst.u3.all), (((tuple->dst.protonum ^ tuple->src.l3num) <<16 ) | (__force __u16 )tuple->dst.u.all) ^ nf_conntrack_hash_rnd); -return ((u64 )hash * nf_ct_expect_hsize) >>32 ; +return reciprocal_divide (hash, nf_ct_expect_hsize); } struct nf_conntrack_expect *
net/netfilter/nf_nat_core.c +2 -2
@@ -126,7 +126,7 @@ hash_by_src(const struct net *net, u16 zone,/* Original src, to ensure we map it consistently if poss. */ hash =jhash2 ((u32 *)&tuple->src,sizeof (tuple->src) /sizeof (u32), tuple->dst.protonum ^ zone ^ nf_conntrack_hash_rnd); -return ((u64 )hash * net->ct.nat_htable_size) >>32 ; +return reciprocal_divide (hash, net->ct.nat_htable_size); }/* Is this tuple already taken? (not by us) */
@@ -274,7 +274,7 @@ find_best_ips_proto(u16 zone, struct nf_conntrack_tuple *tuple, } var_ipp->all[i] = (__force __u32 ) -htonl (minip + (((u64 )j * dist) >>32 )); +htonl (minip +reciprocal_divide (j, dist));if (var_ipp->all[i] != range->max_addr.all[i]) full_range = true;
net/netfilter/xt_HMARK.c +1 -1
@@ -126,7 +126,7 @@ hmark_hash(struct hmark_tuple *t, const struct xt_hmark_info *info) hash =jhash_3words (src, dst, t->uports.v32, info->hashrnd); hash = hash ^ (t->proto & info->proto_mask); -return (((u64 )hash * info->hmodulus) >>32 ) + info->hoffset; +return reciprocal_divide (hash, info->hmodulus) + info->hoffset; } static void
net/netfilter/xt_NFQUEUE.c +2 -2
@@ -83,10 +83,10 @@ nfqueue_hash(const struct sk_buff *skb, const struct xt_action_param *par)u32 queue = info->queuenum;if (par->family ==NFPROTO_IPV4 ) - queue += ((u64 )hash_v4 (skb) * info->queues_total) >>32 ; + queue +=reciprocal_divide (hash_v4 (skb), info->queues_total);#if IS_ENABLED (CONFIG_IP6_NF_IPTABLES ) else if (par->family == NFPROTO_IPV6) - queue += ((u64) hash_v6(skb) * info->queues_total) >> 32; + queue += reciprocal_divide(hash_v6(skb), info->queues_total);#endif return queue;
net/netfilter/xt_cluster.c +1 -1
@@ -55,7 +55,7 @@ xt_cluster_hash(const struct nf_conn *ct,WARN_ON (1 );break ; } -return (((u64 )hash * info->total_nodes) >>32 ); +return reciprocal_divide (hash, info->total_nodes); } static inline bool
net/netfilter/xt_hashlimit.c +1 -1
@@ -135,7 +135,7 @@ hash_dst(const struct xt_hashlimit_htable *ht, const struct dsthash_dst *dst)* give results between [0 and cfg.size-1] and same hash distribution, * but using a multiply, less expensive than a divide */ -return ((u64 )hash * ht->cfg.size) >>32 ; +return reciprocal_divide (hash, ht->cfg.size); } static struct dsthash_ent *
net/sched/sch_fq_codel.c +1 -1
@@ -77,7 +77,7 @@ static unsigned int fq_codel_hash(const struct fq_codel_sched_data *q, hash =jhash_3words ((__force u32 )keys.dst, (__force u32 )keys.src ^ keys.ip_proto, (__force u32 )keys.ports, q->perturbation); -return ((u64 )hash * q->flows_cnt) >>32 ; +return reciprocal_divide (hash, q->flows_cnt); } static unsigned int fq_codel_classify(struct sk_buff *skb, struct Qdisc *sch,
Signature · 1 line
1.7.11.7
Re: [PATCH net-next 2/2] net: use reciprocal_divide instead of reimplementing it
Quoted 4 lines · Daniel Borkmann
Replace these places with
reciprocal_divide()inline function instead of reimplementing it each time, thus it will become easier to read. We do not need to explicitly include its header as it's pulled in fromlinux/net.hanyway.
Sure, (((u64) hash * qcount) >> 32) happens to be reciprocal_divide(hash, qcount) but the result depends on hash being well distributed in [0 .. ~0U] space.
So 'reciprocal' and 'divide' do not accurately describe this exact operation.
I suggest making the thing more descriptive.
(And discussed on lkml btw)
Re: [PATCH net-next 2/2] net: use reciprocal_divide instead of reimplementing it
Quoted 10 lines · Eric Dumazet
Quoted 4 lines · Daniel Borkmann
Replace these places with
reciprocal_divide()inline function instead of reimplementing it each time, thus it will become easier to read. We do not need to explicitly include its header as it's pulled in fromlinux/net.hanyway.Sure, (((u64) hash * qcount) >> 32) happens to be
reciprocal_divide(hash, qcount)but the result depends on hash being well distributed in [0 .. ~0U] space.
Quoted 6 lines
So 'reciprocal' and 'divide' do not accurately describe this exact operation.
I suggest making the thing more descriptive.
(And discussed on lkml btw)
Sure, we can do that. Then lets drop these two for now.