On Mon, Mar 17, 2014 at 3:34 PM, Alex Wang <[email protected]> wrote:
> The reciprocal division code used in datapath is flawed. The bug
> has been fixed in the linux kernel repo in commit 809fa972fd(
> reciprocal_divide: update/correction of the algorithm).
>
> This commit downstreams the reciprocal_div.{c,h} from the linux
> kernel repo.
>
> Signed-off-by: Alex Wang <[email protected]>
> ---
> PATCH -> V2:
> - include <linux/reciprocal_div.h> in the flex_array.h.
> - use {0} to initialize struct variable to all 0.
> - add WRAPPER in the prefix of header 'ifndef' macro.
> - remove the EXPORT_SYMBOL in reciprocal_div.c.
> ---
> datapath/linux/Modules.mk | 1 +
> datapath/linux/compat/flex_array.c | 2 +-
> datapath/linux/compat/include/linux/flex_array.h | 3 +-
> .../linux/compat/include/linux/reciprocal_div.h | 37
> ++++++++++++++++++++
> datapath/linux/compat/reciprocal_div.c | 29 ++++++++++-----
> 5 files changed, 62 insertions(+), 10 deletions(-)
> create mode 100644 datapath/linux/compat/include/linux/reciprocal_div.h
>
> diff --git a/datapath/linux/Modules.mk b/datapath/linux/Modules.mk
> index cedb8c9..1e76305 100644
> --- a/datapath/linux/Modules.mk
> +++ b/datapath/linux/Modules.mk
> @@ -49,6 +49,7 @@ openvswitch_headers += \
> linux/compat/include/linux/poison.h \
> linux/compat/include/linux/rculist.h \
> linux/compat/include/linux/rcupdate.h \
> + linux/compat/include/linux/reciprocal_div.h \
> linux/compat/include/linux/rtnetlink.h \
> linux/compat/include/linux/sctp.h \
> linux/compat/include/linux/skbuff.h \
> diff --git a/datapath/linux/compat/flex_array.c
> b/datapath/linux/compat/flex_array.c
> index 1e6d9c1..c39dd1b 100644
> --- a/datapath/linux/compat/flex_array.c
> +++ b/datapath/linux/compat/flex_array.c
> @@ -93,8 +93,8 @@ struct flex_array *flex_array_alloc(int element_size,
> unsigned int total,
> gfp_t flags)
> {
> struct flex_array *ret;
> + struct reciprocal_value reciprocal_elems = {0};
> int elems_per_part = 0;
> - int reciprocal_elems = 0;
> int max_size = 0;
>
> if (element_size) {
> diff --git a/datapath/linux/compat/include/linux/flex_array.h
> b/datapath/linux/compat/include/linux/flex_array.h
> index 1cc6648..443c4af 100644
> --- a/datapath/linux/compat/include/linux/flex_array.h
> +++ b/datapath/linux/compat/include/linux/flex_array.h
> @@ -6,6 +6,7 @@
> #include_next <linux/flex_array.h>
> #else
>
> +#include <linux/reciprocal_div.h>
> #include <linux/types.h>
> #include <asm/page.h>
>
> @@ -27,7 +28,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/datapath/linux/compat/include/linux/reciprocal_div.h
> b/datapath/linux/compat/include/linux/reciprocal_div.h
> new file mode 100644
> index 0000000..2def5c6
> --- /dev/null
> +++ b/datapath/linux/compat/include/linux/reciprocal_div.h
> @@ -0,0 +1,37 @@
> +#ifndef _LINUX_RECIPROCAL_DIV_WRAPPER_H
> +#define _LINUX_RECIPROCAL_DIV_WRAPPER_H 1
> +
> +#include <linux/types.h>
> +
> +/*
> + * This algorithm is based on the paper "Division by Invariant
> + * Integers Using Multiplication" by Torbjörn Granlund and Peter
> + * L. Montgomery.
> + *
> + * The assembler implementation from Agner Fog, which this code is
> + * based on, can be found here:
> + * http://www.agner.org/optimize/asmlib.zip
> + *
> + * This optimization for A/B is helpful if the divisor B is mostly
> + * runtime invariant. 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.
> + */
> +
> +#define reciprocal_value rpl_reciprocal_value
> +struct reciprocal_value {
> + u32 m;
> + u8 sh1, sh2;
> +};
> +
> +struct reciprocal_value reciprocal_value(u32 d);
> +
> +#define reciprocal_divide rpl_reciprocal_divide
> +static inline u32 reciprocal_divide(u32 a, struct reciprocal_value R)
> +{
> + u32 t = (u32)(((u64)a * R.m) >> 32);
> + return (t + ((a - t) >> R.sh1)) >> R.sh2;
> +}
> +
> +#endif /* _LINUX_RECIPROCAL_DIV_WRAPPER_H */
> diff --git a/datapath/linux/compat/reciprocal_div.c
> b/datapath/linux/compat/reciprocal_div.c
> index 7ec7528..8027214 100644
> --- a/datapath/linux/compat/reciprocal_div.c
> +++ b/datapath/linux/compat/reciprocal_div.c
> @@ -1,13 +1,26 @@
> +#include <linux/kernel.h>
> #include <asm/div64.h>
> #include <linux/reciprocal_div.h>
> +#include <linux/export.h>
>
Do we still need to include kernel.h and export.h?
> -#include <linux/version.h>
> -#if LINUX_VERSION_CODE < KERNEL_VERSION(3,3,0)
> -/* definition is required since reciprocal_value() is not exported */
> -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;
> +
> + 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;
> }
> -#endif
> --
> 1.7.9.5
>
Otherwise looks good.
Acked-by: Pravin B Shelar <[email protected]>
> _______________________________________________
> dev mailing list
> [email protected]
> http://openvswitch.org/mailman/listinfo/dev
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
