[PATCH net-next 0/2] reciprocal_divide updates

[PATCH net-next 0/2] reciprocal_divide updates

[Daniel Borkmann]

Set is on top of Eric's BPF fix, that is:

   http://patchwork.ozlabs.org/patch/311163/

Daniel Borkmann (1):
  random32: add prandom_u32_lt_N and convert "misuses" of reciprocal_divide

Hannes Frederic Sowa (1):
  reciprocal_divide: correction/update of the algorithm

 drivers/net/bonding/bond_main.c     | 16 +++++++-------
 drivers/net/bonding/bond_netlink.c  |  4 ----
 drivers/net/bonding/bond_options.c  |  9 +++-----
 drivers/net/bonding/bond_sysfs.c    |  5 -----
 drivers/net/bonding/bonding.h       |  3 +++
 drivers/net/team/team_mode_random.c |  8 +------
 include/linux/flex_array.h          |  3 ++-
 include/linux/random.h              | 19 ++++++++++++++++-
 include/linux/reciprocal_div.h      | 42 ++++++++++++++++++++++---------------
 include/linux/slab_def.h            |  4 +++-
 include/net/codel.h                 |  4 +---
 include/net/red.h                   |  3 ++-
 lib/flex_array.c                    |  3 ++-
 lib/reciprocal_div.c                | 28 +++++++++++++++++++++----
 net/packet/af_packet.c              |  5 ++---
 net/sched/sch_choke.c               |  9 +-------
 net/sched/sch_netem.c               |  4 +++-
 17 files changed, 99 insertions(+), 70 deletions(-)

-- 
1.8.3.1

[PATCH net-next 1/2] random32: add prandom_u32_lt_N and convert "misuses" of reciprocal_divide

[Daniel Borkmann]

Many functions have open coded a function that return a random
number in range [0,N-1]. Also, only because we have a function
that is named reciprocal_divide(), it has not much to do with
the pupose where it is being used when a previous reciprocal_value()
has not been obtained.

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.

Other users can further be migrated to the new prandom_u32_lt_N()
function later on; for now, we need to make sure to migrate
"misuses" of reciprocal_divide() for the reciprocal_divide()
follow-up fixup.

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>
---
 drivers/net/team/team_mode_random.c |  8 +-------
 include/linux/random.h              | 19 ++++++++++++++++++-
 include/net/codel.h                 |  4 +---
 net/packet/af_packet.c              |  5 ++---
 net/sched/sch_choke.c               |  9 +--------
 5 files changed, 23 insertions(+), 22 deletions(-)

diff --git a/drivers/net/team/team_mode_random.c b/drivers/net/team/team_mode_random.c
index 7f032e2..f2d22a5 100644
--- a/drivers/net/team/team_mode_random.c
+++ b/drivers/net/team/team_mode_random.c
@@ -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_lt_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/random.h b/include/linux/random.h
index 4002b3d..cc3f006 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -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);
@@ -38,6 +37,24 @@ 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_lt_N - returns a random number in interval [0, N), the
+ *                    interval is right-open. This is useful when an
+ *                    requesting random index of an array containing
+ *                    N elements, for example.
+ *
+ * @N: higher interval endpoint
+ *
+ * Returns a pseduo-random number that is in interval [0, N). Note
+ * that the result depends on PRNG being well distributed in [0, ~0U]
+ * space. Here, we use maximally equidistributed combined Tausworthe
+ * generator, that is, prandom_u32().
+ */
+static inline u32 prandom_u32_lt_N(u32 N)
+{
+	return (u32)(((u64) prandom_u32() * N) >> 32);
+}
+
 /*
  * Handle minimum values for seeds
  */
diff --git a/include/net/codel.h b/include/net/codel.h
index 3b04ff5..7705a72 100644
--- a/include/net/codel.h
+++ b/include/net/codel.h
@@ -46,7 +46,6 @@
 #include <linux/skbuff.h>
 #include <net/pkt_sched.h>
 #include <net/inet_ecn.h>
-#include <linux/reciprocal_div.h>
 
 /* Controlling Queue Delay (CoDel) algorithm
  * =========================================
@@ -211,10 +210,9 @@ static codel_time_t codel_control_law(codel_time_t t,
 				      codel_time_t interval,
 				      u32 rec_inv_sqrt)
 {
-	return t + reciprocal_divide(interval, rec_inv_sqrt << REC_INV_SQRT_SHIFT);
+	return t + (u32)(((u64) interval * (rec_inv_sqrt << REC_INV_SQRT_SHIFT)) >> 32);
 }
 
-
 static bool codel_should_drop(const struct sk_buff *skb,
 			      struct Qdisc *sch,
 			      struct codel_vars *vars,
diff --git a/net/packet/af_packet.c b/net/packet/af_packet.c
index 279467b..f976474 100644
--- a/net/packet/af_packet.c
+++ b/net/packet/af_packet.c
@@ -88,7 +88,6 @@
 #include <linux/virtio_net.h>
 #include <linux/errqueue.h>
 #include <linux/net_tstamp.h>
-#include <linux/reciprocal_div.h>
 #ifdef CONFIG_INET
 #include <net/inet_common.h>
 #endif
@@ -1220,7 +1219,7 @@ static unsigned int fanout_demux_hash(struct packet_fanout *f,
 				      struct sk_buff *skb,
 				      unsigned int num)
 {
-	return reciprocal_divide(skb->rxhash, num);
+	return (u32)(((u64) skb->rxhash * num) >> 32);
 }
 
 static unsigned int fanout_demux_lb(struct packet_fanout *f,
@@ -1247,7 +1246,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_lt_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 ddd73cb..556b6f6 100644
--- a/net/sched/sch_choke.c
+++ b/net/sched/sch_choke.c
@@ -14,7 +14,6 @@
 #include <linux/types.h>
 #include <linux/kernel.h>
 #include <linux/skbuff.h>
-#include <linux/reciprocal_div.h>
 #include <linux/vmalloc.h>
 #include <net/pkt_sched.h>
 #include <net/inet_ecn.h>
@@ -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_lt_N(choke_len(q))) & q->tab_mask;
 		skb = q->tab[*pidx];
 		if (skb)
 			return skb;
-- 
1.8.3.1

[PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

[Daniel Borkmann]

From: Hannes Frederic Sowa <hannes@stressinduktion.org>

Jakub Zawadzki noticed that some divisions by reciprocal_divide()
were not correct [1][2], which he could also show with BPF code
after divisions are transformed into reciprocal_value() for runtime
invariant which can be passed to reciprocal_divide() later on;
reverse in BPF dump ended up with a different, off-by-one K.

Also, reciprocal_value() and reciprocal_divide() always return 0
for divisions by 1. This is a bit worrisome as those functions
also get used in mm/slab.c and lib/flex_array.c, apparently for
index calculation to access array slots. Bonding already seems to
check for the 1-divisor case and handles that correctly. We don't
know about other problems, besides possibly flex array, yet.

In order to fix that, we propose an extension from the original
implementation from commit 6a2d7a955d8d resp. [3][4], by using
the algorithm proposed in "Division by Invariant Integers Using
Multiplication" [5], Torbjörn Granlund and Peter L. Montgomery,
that is, pseudocode for q = n/d where q,n,d is in u32 universe:

1) Initialization:

  int l = ceil(log_2 d)
  uword m' = floor((1<<32)*((1<<l)-d)/d)+1
  int sh_1 = min(l,1)
  int sh_2 = max(l-1,0)

2) For q = n/d, all uword:

  uword t = (n*m')>>32
  q = (t+((n-t)>>sh_1))>>sh_2

The assembler implementation from Agner Fog [6] also helped a lot
while implementing. We have tested the implementation on x86_64,
ppc64, i686, s390x; on x86_64/haswell we're still half the latency
compared to normal divide.

Joint work with Daniel Borkmann.

  [1] http://www.wireshark.org/~darkjames/reciprocal-buggy.c
  [2] http://www.wireshark.org/~darkjames/set-and-dump-filter-k-bug.c
  [3] https://gmplib.org/~tege/division-paper.pdf
  [4] http://homepage.cs.uiowa.edu/~jones/bcd/divide.html
  [5] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.2556
  [6] http://www.agner.org/optimize/asmlib.zip

Fixes: 6a2d7a955d8d ("SLAB: use a multiply instead of a divide in obj_to_index()")
Fixes: 704f15ddb5fc2a ("flex_array: avoid divisions when accessing elements")
Reported-by: Jakub Zawadzki <darkjames-ws@darkjames.pl>
Cc: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Austin S Hemmelgarn <ahferroin7@gmail.com>
Cc: linux-kernel@vger.kernel.org
Cc: Jesse Gross <jesse@nicira.com>
Cc: Jamal Hadi Salim <jhs@mojatatu.com>
Cc: Stephen Hemminger <stephen@networkplumber.org>
Cc: Matt Mackall <mpm@selenic.com>
Cc: Pekka Enberg <penberg@kernel.org>
Cc: Christoph Lameter <cl@linux-foundation.org>
Cc: Andy Gospodarek <andy@greyhouse.net>
Cc: Veaceslav Falico <vfalico@redhat.com>
Cc: Jay Vosburgh <fubar@us.ibm.com>
Cc: Jakub Zawadzki <darkjames-ws@darkjames.pl>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
---
 drivers/net/bonding/bond_main.c    | 16 ++++++++-------
 drivers/net/bonding/bond_netlink.c |  4 ----
 drivers/net/bonding/bond_options.c |  9 +++-----
 drivers/net/bonding/bond_sysfs.c   |  5 -----
 drivers/net/bonding/bonding.h      |  3 +++
 include/linux/flex_array.h         |  3 ++-
 include/linux/reciprocal_div.h     | 42 +++++++++++++++++++++++---------------
 include/linux/slab_def.h           |  4 +++-
 include/net/red.h                  |  3 ++-
 lib/flex_array.c                   |  3 ++-
 lib/reciprocal_div.c               | 28 +++++++++++++++++++++----
 net/sched/sch_netem.c              |  4 +++-
 12 files changed, 76 insertions(+), 48 deletions(-)

diff --git a/drivers/net/bonding/bond_main.c b/drivers/net/bonding/bond_main.c
index f2fe6cb..8cf03eb 100644
--- a/drivers/net/bonding/bond_main.c
+++ b/drivers/net/bonding/bond_main.c
@@ -79,7 +79,6 @@
 #include <net/pkt_sched.h>
 #include <linux/rculist.h>
 #include <net/flow_keys.h>
-#include <linux/reciprocal_div.h>
 #include "bonding.h"
 #include "bond_3ad.h"
 #include "bond_alb.h"
@@ -3551,8 +3550,9 @@ static void bond_xmit_slave_id(struct bonding *bond, struct sk_buff *skb, int sl
  */
 static u32 bond_rr_gen_slave_id(struct bonding *bond)
 {
-	int packets_per_slave = bond->params.packets_per_slave;
 	u32 slave_id;
+	struct reciprocal_value reciprocal_packets_per_slave;
+	int packets_per_slave = bond->params.packets_per_slave;
 
 	switch (packets_per_slave) {
 	case 0:
@@ -3562,8 +3562,10 @@ static u32 bond_rr_gen_slave_id(struct bonding *bond)
 		slave_id = bond->rr_tx_counter;
 		break;
 	default:
+		reciprocal_packets_per_slave =
+			bond->params.reciprocal_packets_per_slave;
 		slave_id = reciprocal_divide(bond->rr_tx_counter,
-					     packets_per_slave);
+					     reciprocal_packets_per_slave);
 		break;
 	}
 	bond->rr_tx_counter++;
@@ -4297,10 +4299,10 @@ static int bond_check_params(struct bond_params *params)
 	params->resend_igmp = resend_igmp;
 	params->min_links = min_links;
 	params->lp_interval = lp_interval;
-	if (packets_per_slave > 1)
-		params->packets_per_slave = reciprocal_value(packets_per_slave);
-	else
-		params->packets_per_slave = packets_per_slave;
+	params->packets_per_slave = packets_per_slave;
+	params->reciprocal_packets_per_slave =
+		reciprocal_value(packets_per_slave);
+
 	if (primary) {
 		strncpy(params->primary, primary, IFNAMSIZ);
 		params->primary[IFNAMSIZ - 1] = 0;
diff --git a/drivers/net/bonding/bond_netlink.c b/drivers/net/bonding/bond_netlink.c
index 555c783..9b13791 100644
--- a/drivers/net/bonding/bond_netlink.c
+++ b/drivers/net/bonding/bond_netlink.c
@@ -19,7 +19,6 @@
 #include <linux/if_ether.h>
 #include <net/netlink.h>
 #include <net/rtnetlink.h>
-#include <linux/reciprocal_div.h>
 #include "bonding.h"
 
 static const struct nla_policy bond_policy[IFLA_BOND_MAX + 1] = {
@@ -416,9 +415,6 @@ static int bond_fill_info(struct sk_buff *skb,
 		goto nla_put_failure;
 
 	packets_per_slave = bond->params.packets_per_slave;
-	if (packets_per_slave > 1)
-		packets_per_slave = reciprocal_value(packets_per_slave);
-
 	if (nla_put_u32(skb, IFLA_BOND_PACKETS_PER_SLAVE,
 			packets_per_slave))
 		goto nla_put_failure;
diff --git a/drivers/net/bonding/bond_options.c b/drivers/net/bonding/bond_options.c
index 945a666..bacfd53 100644
--- a/drivers/net/bonding/bond_options.c
+++ b/drivers/net/bonding/bond_options.c
@@ -16,7 +16,6 @@
 #include <linux/netdevice.h>
 #include <linux/rwlock.h>
 #include <linux/rcupdate.h>
-#include <linux/reciprocal_div.h>
 #include "bonding.h"
 
 int bond_option_mode_set(struct bonding *bond, int mode)
@@ -671,11 +670,9 @@ int bond_option_packets_per_slave_set(struct bonding *bond,
 		pr_warn("%s: Warning: packets_per_slave has effect only in balance-rr mode\n",
 			bond->dev->name);
 
-	if (packets_per_slave > 1)
-		bond->params.packets_per_slave =
-			reciprocal_value(packets_per_slave);
-	else
-		bond->params.packets_per_slave = packets_per_slave;
+	bond->params.packets_per_slave = packets_per_slave;
+	bond->params.reciprocal_packets_per_slave =
+		reciprocal_value(packets_per_slave);
 
 	return 0;
 }
diff --git a/drivers/net/bonding/bond_sysfs.c b/drivers/net/bonding/bond_sysfs.c
index 011f163..c083e9a 100644
--- a/drivers/net/bonding/bond_sysfs.c
+++ b/drivers/net/bonding/bond_sysfs.c
@@ -39,7 +39,6 @@
 #include <net/net_namespace.h>
 #include <net/netns/generic.h>
 #include <linux/nsproxy.h>
-#include <linux/reciprocal_div.h>
 
 #include "bonding.h"
 
@@ -1374,10 +1373,6 @@ static ssize_t bonding_show_packets_per_slave(struct device *d,
 {
 	struct bonding *bond = to_bond(d);
 	unsigned int packets_per_slave = bond->params.packets_per_slave;
-
-	if (packets_per_slave > 1)
-		packets_per_slave = reciprocal_value(packets_per_slave);
-
 	return sprintf(buf, "%u\n", packets_per_slave);
 }
 
diff --git a/drivers/net/bonding/bonding.h b/drivers/net/bonding/bonding.h
index 955dc48..502dda8 100644
--- a/drivers/net/bonding/bonding.h
+++ b/drivers/net/bonding/bonding.h
@@ -23,6 +23,8 @@
 #include <linux/netpoll.h>
 #include <linux/inetdevice.h>
 #include <linux/etherdevice.h>
+#include <linux/reciprocal_div.h>
+
 #include "bond_3ad.h"
 #include "bond_alb.h"
 
@@ -171,6 +173,7 @@ struct bond_params {
 	int resend_igmp;
 	int lp_interval;
 	int packets_per_slave;
+	struct reciprocal_value reciprocal_packets_per_slave;
 };
 
 struct bond_parm_tbl {
diff --git a/include/linux/flex_array.h b/include/linux/flex_array.h
index 6843cf1..b6efb0c 100644
--- a/include/linux/flex_array.h
+++ b/include/linux/flex_array.h
@@ -2,6 +2,7 @@
 #define _FLEX_ARRAY_H
 
 #include <linux/types.h>
+#include <linux/reciprocal_div.h>
 #include <asm/page.h>
 
 #define FLEX_ARRAY_PART_SIZE PAGE_SIZE
@@ -22,7 +23,7 @@ struct flex_array {
 			int element_size;
 			int total_nr_elements;
 			int elems_per_part;
-			u32 reciprocal_elems;
+			struct reciprocal_value reciprocal_elems;
 			struct flex_array_part *parts[];
 		};
 		/*
diff --git a/include/linux/reciprocal_div.h b/include/linux/reciprocal_div.h
index f9c90b3..be66c3a 100644
--- a/include/linux/reciprocal_div.h
+++ b/include/linux/reciprocal_div.h
@@ -4,29 +4,37 @@
 #include <linux/types.h>
 
 /*
- * This file describes reciprocical division.
+ * This algorithm is based on the paper "Division by Invariant
+ * Integers Using Multiplication" by Torbjörn Granlund and Peter
+ * L. Montgomery.
  *
- * This optimizes the (A/B) problem, when A and B are two u32
- * and B is a known value (but not known at compile time)
+ * The assembler implementation from Agner Fog, which this code is
+ * based on, can be found here:
+ * http://www.agner.org/optimize/asmlib.zip
  *
- * The math principle used is :
- *   Let RECIPROCAL_VALUE(B) be (((1LL << 32) + (B - 1))/ B)
- *   Then A / B = (u32)(((u64)(A) * (R)) >> 32)
+ * This optimization for A/B is helpful if the divisor B is mostly
+ * constant. The reciprocal of B is calculated in the slow-path with
+ * reciprocal_value(). The fast-path can then just use a much faster
+ * multiplication operation with a variable dividend A to calculate
+ * the division A/B.
  *
- * This replaces a divide by a multiply (and a shift), and
- * is generally less expensive in CPU cycles.
+ * RECIPROCAL_VALUE_TO_ZERO can be used to express an element, which
+ * used as the argument to reciprocal_divide always yields zero.
  */
 
-/*
- * Computes the reciprocal value (R) for the value B of the divisor.
- * Should not be called before each reciprocal_divide(),
- * or else the performance is slower than a normal divide.
- */
-extern u32 reciprocal_value(u32 B);
+struct reciprocal_value {
+	u32 m;
+	u8 sh1, sh2;
+};
 
+#define RECIPROCAL_VALUE_RESULT_TO_ZERO ((struct reciprocal_value){.sh1 = 32})
 
-static inline u32 reciprocal_divide(u32 A, u32 R)
+struct reciprocal_value reciprocal_value(u32 d);
+
+static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R)
 {
-	return (u32)(((u64)A * R) >> 32);
+	u32 t = (u32)(((u64)a * R.m) >> 32);
+	return (t + ((a - t) >> R.sh1)) >> R.sh2;
 }
-#endif
+
+#endif /* _LINUX_RECIPROCAL_DIV_H */
diff --git a/include/linux/slab_def.h b/include/linux/slab_def.h
index 09bfffb..96e8aba 100644
--- a/include/linux/slab_def.h
+++ b/include/linux/slab_def.h
@@ -1,6 +1,8 @@
 #ifndef _LINUX_SLAB_DEF_H
 #define	_LINUX_SLAB_DEF_H
 
+#include <linux/reciprocal_div.h>
+
 /*
  * Definitions unique to the original Linux SLAB allocator.
  */
@@ -12,7 +14,7 @@ struct kmem_cache {
 	unsigned int shared;
 
 	unsigned int size;
-	u32 reciprocal_buffer_size;
+	struct reciprocal_value reciprocal_buffer_size;
 /* 2) touched by every alloc & free from the backend */
 
 	unsigned int flags;		/* constant flags */
diff --git a/include/net/red.h b/include/net/red.h
index 168bb2f..76e0b5f 100644
--- a/include/net/red.h
+++ b/include/net/red.h
@@ -130,7 +130,8 @@ struct red_parms {
 	u32		qth_max;	/* Max avg length threshold: Wlog scaled */
 	u32		Scell_max;
 	u32		max_P;		/* probability, [0 .. 1.0] 32 scaled */
-	u32		max_P_reciprocal; /* reciprocal_value(max_P / qth_delta) */
+	/* reciprocal_value(max_P / qth_delta) */
+	struct reciprocal_value	max_P_reciprocal;
 	u32		qth_delta;	/* max_th - min_th */
 	u32		target_min;	/* min_th + 0.4*(max_th - min_th) */
 	u32		target_max;	/* min_th + 0.6*(max_th - min_th) */
diff --git a/lib/flex_array.c b/lib/flex_array.c
index 6948a66..704efa1 100644
--- a/lib/flex_array.c
+++ b/lib/flex_array.c
@@ -90,8 +90,9 @@ struct flex_array *flex_array_alloc(int element_size, unsigned int total,
 {
 	struct flex_array *ret;
 	int elems_per_part = 0;
-	int reciprocal_elems = 0;
 	int max_size = 0;
+	struct reciprocal_value reciprocal_elems =
+		RECIPROCAL_VALUE_RESULT_TO_ZERO;
 
 	if (element_size) {
 		elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
diff --git a/lib/reciprocal_div.c b/lib/reciprocal_div.c
index 75510e9..f49742d 100644
--- a/lib/reciprocal_div.c
+++ b/lib/reciprocal_div.c
@@ -1,11 +1,31 @@
+#include <linux/kernel.h>
+#include <linux/bug.h>
 #include <asm/div64.h>
 #include <linux/reciprocal_div.h>
 #include <linux/export.h>
 
-u32 reciprocal_value(u32 k)
+/*
+ * For a description of the algorithm please have a look at
+ * include/linux/reciprocal_div.h
+ */
+
+struct reciprocal_value reciprocal_value(u32 d)
 {
-	u64 val = (1LL << 32) + (k - 1);
-	do_div(val, k);
-	return (u32)val;
+	struct reciprocal_value R;
+	u64 m;
+	int l;
+
+	BUILD_BUG_ON(reciprocal_divide(0U, RECIPROCAL_VALUE_RESULT_TO_ZERO));
+	BUILD_BUG_ON(reciprocal_divide(1U, RECIPROCAL_VALUE_RESULT_TO_ZERO));
+	BUILD_BUG_ON(reciprocal_divide(~(0U), RECIPROCAL_VALUE_RESULT_TO_ZERO));
+
+	l = fls(d - 1);
+	m = ((1ULL << 32) * ((1ULL << l) - d));
+	do_div(m, d);
+	++m;
+	R.m = (u32)m;
+	R.sh1 = min(l, 1);
+	R.sh2 = max(l-1, 0);
+	return R;
 }
 EXPORT_SYMBOL(reciprocal_value);
diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 3019c10..3bf6495 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -91,7 +91,7 @@ struct netem_sched_data {
 	u64 rate;
 	s32 packet_overhead;
 	u32 cell_size;
-	u32 cell_size_reciprocal;
+	struct reciprocal_value cell_size_reciprocal;
 	s32 cell_overhead;
 
 	struct crndstate {
@@ -718,6 +718,8 @@ static void get_rate(struct Qdisc *sch, const struct nlattr *attr)
 	q->cell_size = r->cell_size;
 	if (q->cell_size)
 		q->cell_size_reciprocal = reciprocal_value(q->cell_size);
+	else
+		q->cell_size_reciprocal = RECIPROCAL_VALUE_RESULT_TO_ZERO;
 	q->cell_overhead = r->cell_overhead;
 }
 
-- 
1.8.3.1

Re: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

[Ben Hutchings]

On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote:
[...]
> --- a/include/linux/reciprocal_div.h
> +++ b/include/linux/reciprocal_div.h
[...]
> + * RECIPROCAL_VALUE_TO_ZERO can be used to express an element, which
> + * used as the argument to reciprocal_divide always yields zero.
>   */
[...]
> +#define RECIPROCAL_VALUE_RESULT_TO_ZERO ((struct reciprocal_value){.sh1 = 32})
[...]
> +static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R)
>  {
> -	return (u32)(((u64)A * R) >> 32);
> +	u32 t = (u32)(((u64)a * R.m) >> 32);
> +	return (t + ((a - t) >> R.sh1)) >> R.sh2;
[...]

(a - t) has type u32.
So (a - t) >> 32 has undefined behaviour.

Ben.

-- 
Ben Hutchings, Staff Engineer, Solarflare
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

Re: [PATCH net-next 1/2] random32: add prandom_u32_lt_N and convert "misuses" of reciprocal_divide

[Joe Perches]

On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote:
> Many functions have open coded a function that return a random
> number in range [0,N-1]. Also, only because we have a function
> that is named reciprocal_divide(), it has not much to do with
> the pupose where it is being used when a previous reciprocal_value()
> has not been obtained.

prandom_u32_lt_N?

I do not like the camelcase name and thought the
prandom_u32_max was better.

How about using

u32 prandom_u32_max(u32 max)
{
	return (u32)(((u64)prandom_u32() * max) >> 32);
}

u32 prandom_u32_range(u32 a, u32 b)
{
	if (b < a)
		swap(a, b);

	return a + (u32)(((u64)prandom_u32() * (b - a)) >> 32);
}

Re: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

[Hannes Frederic Sowa]

On Thu, Jan 16, 2014 at 12:17:50AM +0000, Ben Hutchings wrote:
> On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote:
> [...]
> > --- a/include/linux/reciprocal_div.h
> > +++ b/include/linux/reciprocal_div.h
> [...]
> > + * RECIPROCAL_VALUE_TO_ZERO can be used to express an element, which
> > + * used as the argument to reciprocal_divide always yields zero.
> >   */
> [...]
> > +#define RECIPROCAL_VALUE_RESULT_TO_ZERO ((struct reciprocal_value){.sh1 = 32})
> [...]
> > +static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R)
> >  {
> > -	return (u32)(((u64)A * R) >> 32);
> > +	u32 t = (u32)(((u64)a * R.m) >> 32);
> > +	return (t + ((a - t) >> R.sh1)) >> R.sh2;
> [...]
> 
> (a - t) has type u32.
> So (a - t) >> 32 has undefined behaviour.

Good catch, totally overlooked that.

Thanks,

  Hannes

Re: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

[Eric Dumazet]

On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote:

> Also, reciprocal_value() and reciprocal_divide() always return 0
> for divisions by 1. This is a bit worrisome as those functions
> also get used in mm/slab.c and lib/flex_array.c, apparently for
> index calculation to access array slots. 

Hi Daniel

This off-by-one limitation is a known one,
and mm/slab.c does not have an issue with it because :

- Minimal object size is not 1 byte, but 8 (or maybe 4)
- We always divide a multiple of the divisor,
  so there is no off-by-one effect.

Little attached prog does a brute force check if needed.

So far, the only relevant issue was about BPF, and a better
documentation of reciprocal_divide() use cases.

(I let Jesse comment on the flex_array case)

I am unsure we want to 'fix' things, we tried hard in the past to avoid
divides, so the ones we use are usually because the divisor is not
constant, so the reciprocal doesn't help.

(BPF is fixed in David tree)

Thanks !

#include <stdio.h>

typedef unsigned int u32;
typedef unsigned long long u64;

static u32 reciprocal_value(u32 k)
{
	u64 val = (1LL << 32) + (k - 1);
	val /= k;
	return (u32)val;
}

static inline u32 reciprocal_divide(u32 A, u32 R)
{
	return (u32)(((u64)A * R) >> 32);
}

#define LIMIT 1000*1000*1000

int main()
{
	u32 divisor, dividend, reciprocal, next;
	int res = 0;

	for (divisor = 2; divisor < LIMIT; divisor++) {
		reciprocal = reciprocal_value(divisor);
		for (dividend = 0; ; dividend = next) {
			if (reciprocal_divide(dividend, reciprocal) != (dividend / divisor)) {
				printf("Arg: %u/%u was not properly computed (%u/%u)\n",
					dividend, divisor,
					reciprocal_divide(dividend, reciprocal),
					dividend / divisor);
				res = 1;
				break;
			}
			next = dividend + divisor;
			if (next < dividend)
				break;
		}
	}
	return res;
}

Re: [PATCH net-next 1/2] random32: add prandom_u32_lt_N and convert "misuses" of reciprocal_divide

[Eric Dumazet]

On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote:

> @@ -1220,7 +1219,7 @@ static unsigned int fanout_demux_hash(struct packet_fanout *f,
>  				      struct sk_buff *skb,
>  				      unsigned int num)
>  {
> -	return reciprocal_divide(skb->rxhash, num);
> +	return (u32)(((u64) skb->rxhash * num) >> 32);
>  }
>  

This is unfortunate.

(This reverts one of your patch : f55d112e529386 )

Please add a helper to explain what's going on here, and on many other
spots we do this computation (as in get_rps_cpu()).
Few people really understand this.

Or keep reciprocal_divide() as is, and introduce a new set of functions
for people really wanting the precise divides.

Re: [PATCH net-next 1/2] random32: add prandom_u32_lt_N and convert "misuses" of reciprocal_divide

[Daniel Borkmann]

On 01/16/2014 01:29 AM, Joe Perches wrote:
> On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote:
>> Many functions have open coded a function that return a random
>> number in range [0,N-1]. Also, only because we have a function
>> that is named reciprocal_divide(), it has not much to do with
>> the pupose where it is being used when a previous reciprocal_value()
>> has not been obtained.
>
> prandom_u32_lt_N?
>
> I do not like the camelcase name and thought the
> prandom_u32_max was better.

Hm, you wanted to have the name intuitive, right ... so
u32 prandom_u32_lt_N(u32 N) suggests "less then N". If you
are saying "_max" here, then you should keep in mind that
the maximum result you get from here is "max-1", not "max".
But whatever, it's just a name.

> How about using
>
> u32 prandom_u32_max(u32 max)
> {
> 	return (u32)(((u64)prandom_u32() * max) >> 32);
> }
>
> u32 prandom_u32_range(u32 a, u32 b)
> {
> 	if (b < a)
> 		swap(a, b);
>
> 	return a + (u32)(((u64)prandom_u32() * (b - a)) >> 32);
> }

I didn't introduce the last one as it wasn't used in the patch.

RE: [PATCH net-next 1/2] random32: add prandom_u32_lt_N and convert "misuses" of reciprocal_divide

[David Laight]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="utf-8", Size: 1168 bytes --]

From: Eric Dumazet
> On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote:
> 
> > @@ -1220,7 +1219,7 @@ static unsigned int fanout_demux_hash(struct packet_fanout *f,
> >  				      struct sk_buff *skb,
> >  				      unsigned int num)
> >  {
> > -	return reciprocal_divide(skb->rxhash, num);
> > +	return (u32)(((u64) skb->rxhash * num) >> 32);
> >  }
> >
> 
> This is unfortunate.
> 
> (This reverts one of your patch : f55d112e529386 )
> 
> Please add a helper to explain what's going on here, and on many other
> spots we do this computation (as in get_rps_cpu()).
> Few people really understand this.
> 
> Or keep reciprocal_divide() as is, and introduce a new set of functions
> for people really wanting the precise divides.

Maybe rename the current reciprocal_divide() as well?

In the above code it isn't immediately obvious that the result of
a division is as useful as that of a modulus!
OTOH the high 32 bits of a 32x32 multiply are (slightly) more obviously
in the required range.

	David

ÿôèº{.nÇ+‰·Ÿ®‰­†+%ŠËÿ±éݶ\x17¥Šwÿº{.nÇ+‰·¥Š{±þG«éÿŠ{ayº\x1dʇڙë,j\a­¢f£¢·hšïêÿ‘êçz_è®\x03(­éšŽŠÝ¢j"ú\x1a¶^[m§ÿÿ¾\a«þG«éÿ¢¸?™¨è­Ú&£ø§~á¶iO•æ¬z·švØ^\x14\x04\x1a¶^[m§ÿÿÃ\fÿ¶ìÿ¢¸?–I¥

Re: [PATCH net-next 1/2] random32: add prandom_u32_lt_N and convert "misuses" of reciprocal_divide

[Daniel Borkmann]

On 01/16/2014 04:14 AM, Eric Dumazet wrote:
> On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote:
>
>> @@ -1220,7 +1219,7 @@ static unsigned int fanout_demux_hash(struct packet_fanout *f,
>>   				      struct sk_buff *skb,
>>   				      unsigned int num)
>>   {
>> -	return reciprocal_divide(skb->rxhash, num);
>> +	return (u32)(((u64) skb->rxhash * num) >> 32);
>>   }
>>
>
> This is unfortunate.

Hm, I agree, it would be better to have a function here. It was mostly
for the purpose of the 2nd patch to migrate users since the structure
was introduced, and thus they become incompatible.

> (This reverts one of your patch : f55d112e529386 )
>
> Please add a helper to explain what's going on here, and on many other
> spots we do this computation (as in get_rps_cpu()).
> Few people really understand this.

Indeed, that's why we also thought that we should fix some spots in
the second patch, also with the thought in mind, when upcoming users
have to use a structure to enforce this call combination.

Anyway, we'll wait for some more feedback anyway regarding the 2nd patch
and then respin.

> Or keep reciprocal_divide() as is, and introduce a new set of functions
> for people really wanting the precise divides.

That might also be a possible option, we could consider. Thanks!

>
>
>

Re: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

[Hannes Frederic Sowa]

Hi Eric!

On Wed, Jan 15, 2014 at 07:07:26PM -0800, Eric Dumazet wrote:
> On Thu, 2014-01-16 at 00:23 +0100, Daniel Borkmann wrote:
> 
> > Also, reciprocal_value() and reciprocal_divide() always return 0
> > for divisions by 1. This is a bit worrisome as those functions
> > also get used in mm/slab.c and lib/flex_array.c, apparently for
> > index calculation to access array slots. 
> 
> Hi Daniel
> 
> This off-by-one limitation is a known one,
> and mm/slab.c does not have an issue with it because :
> 
> - Minimal object size is not 1 byte, but 8 (or maybe 4)
> - We always divide a multiple of the divisor,
>   so there is no off-by-one effect.
> 
> Little attached prog does a brute force check if needed.
> 
> So far, the only relevant issue was about BPF, and a better
> documentation of reciprocal_divide() use cases.
> 
> (I let Jesse comment on the flex_array case)
> 
> I am unsure we want to 'fix' things, we tried hard in the past to avoid
> divides, so the ones we use are usually because the divisor is not
> constant, so the reciprocal doesn't help.
> 
> (BPF is fixed in David tree)
> 
> Thanks !

You are right, we rewrite that part. The text is still from the first commit
message where we did no full impact analysis. ;)

Thanks,

  Hannes

Re: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

[Christoph Lameter]

On Thu, 16 Jan 2014, Daniel Borkmann wrote:

> - * or else the performance is slower than a normal divide.
> - */
> -extern u32 reciprocal_value(u32 B);
> +struct reciprocal_value {
> +	u32 m;
> +	u8 sh1, sh2;
> +};
>
> +#define RECIPROCAL_VALUE_RESULT_TO_ZERO ((struct reciprocal_value){.sh1 = 32})
>
> -static inline u32 reciprocal_divide(u32 A, u32 R)
> +struct reciprocal_value reciprocal_value(u32 d);

A function that returns a struct? That works? Which gcc versions support
it?

Re: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

[Hannes Frederic Sowa]

On Thu, Jan 16, 2014 at 10:37:37AM -0600, Christoph Lameter wrote:
> On Thu, 16 Jan 2014, Daniel Borkmann wrote:
> 
> > - * or else the performance is slower than a normal divide.
> > - */
> > -extern u32 reciprocal_value(u32 B);
> > +struct reciprocal_value {
> > +	u32 m;
> > +	u8 sh1, sh2;
> > +};
> >
> > +#define RECIPROCAL_VALUE_RESULT_TO_ZERO ((struct reciprocal_value){.sh1 = 32})
> >
> > -static inline u32 reciprocal_divide(u32 A, u32 R)
> > +struct reciprocal_value reciprocal_value(u32 d);
> 
> A function that returns a struct? That works? Which gcc versions support
> it?

Sure, that works and I actually like it. This is supported by the c standard,
but please don't ask me since which one. ;)

Greetings,

  Hannes

Re: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

[Ben Hutchings]

On Thu, 2014-01-16 at 10:37 -0600, Christoph Lameter wrote:
> On Thu, 16 Jan 2014, Daniel Borkmann wrote:
> 
> > - * or else the performance is slower than a normal divide.
> > - */
> > -extern u32 reciprocal_value(u32 B);
> > +struct reciprocal_value {
> > +	u32 m;
> > +	u8 sh1, sh2;
> > +};
> >
> > +#define RECIPROCAL_VALUE_RESULT_TO_ZERO ((struct reciprocal_value){.sh1 = 32})
> >
> > -static inline u32 reciprocal_divide(u32 A, u32 R)
> > +struct reciprocal_value reciprocal_value(u32 d);
> 
> A function that returns a struct? That works? Which gcc versions support
> it?

At least since gcc 1.29, given:

Thu Sep 22 15:57:41 1988  Richard Stallman  (rms at sugar-bombs.ai.mit.edu)
[...]
	* stmt.c (expand_function_start): Set current_function_needs_context
	and current_function_returns_struct.

Hope that's not a problem...

Ben.

-- 
Ben Hutchings, Staff Engineer, Solarflare
Not speaking for my employer; that's the marketing department's job.
They asked us to note that Solarflare product names are trademarked.

RE: [PATCH net-next 2/2] reciprocal_divide: correction/update of the algorithm

[David Laight]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="utf-8", Size: 1349 bytes --]

From: Hannes Frederic Sowa
> On Thu, Jan 16, 2014 at 10:37:37AM -0600, Christoph Lameter wrote:
> > On Thu, 16 Jan 2014, Daniel Borkmann wrote:
> >
> > > - * or else the performance is slower than a normal divide.
> > > - */
> > > -extern u32 reciprocal_value(u32 B);
> > > +struct reciprocal_value {
> > > +	u32 m;
> > > +	u8 sh1, sh2;
> > > +};
> > >
> > > +#define RECIPROCAL_VALUE_RESULT_TO_ZERO ((struct reciprocal_value){.sh1 = 32})
> > >
> > > -static inline u32 reciprocal_divide(u32 A, u32 R)
> > > +struct reciprocal_value reciprocal_value(u32 d);
> >
> > A function that returns a struct? That works? Which gcc versions support
> > it?
> 
> Sure, that works and I actually like it. This is supported by the c standard,
> but please don't ask me since which one. ;)

I think it has always been supported.
Originally by adding an extra hidden argument that points to an on-stack
structure.
More recent ABI tend to allow 'small' structures be returned in registers.
(Typically ones that would fit in the register(s) used for an integral result).

This doesn't mean that it is a good idea!

OTOH if the function is 'static inline' (and inlined) it probably doesn't matter.

	David

ÿôèº{.nÇ+‰·Ÿ®‰­†+%ŠËÿ±éݶ\x17¥Šwÿº{.nÇ+‰·¥Š{±þG«éÿŠ{ayº\x1dʇڙë,j\a­¢f£¢·hšïêÿ‘êçz_è®\x03(­éšŽŠÝ¢j"ú\x1a¶^[m§ÿÿ¾\a«þG«éÿ¢¸?™¨è­Ú&£ø§~á¶iO•æ¬z·švØ^\x14\x04\x1a¶^[m§ÿÿÃ\fÿ¶ìÿ¢¸?–I¥