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

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(-)

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.

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

--
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 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;
}


--
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

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

--
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 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?


--
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 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

--
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 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.