Subject prefix should start with datapath for kernel patches. You can
use "compat" to specify extra context.
On Sat, Mar 15, 2014 at 5:13 PM, Alex Wang <al...@nicira.com> 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.
>
I got build error on Redhat 6 kernel:-
make all-recursive
make[1]: Entering directory `/home/pravin/ovs/openvswitch'
Making all in datapath
make[2]: Entering directory `/home/pravin/ovs/openvswitch/datapath'
Making all in linux
make[3]: Entering directory `/home/pravin/ovs/openvswitch/datapath/linux'
make -C /lib/modules/2.6.32-358.123.2.openstack.el6.x86_64/build/
M=/home/pravin/ovs/openvswitch/datapath/linux modules
make[4]: Entering directory
`/home/pravin/linux/linux-2.6.32-358.123.2.openstack.el6.x86_64'
CC [M] /home/pravin/ovs/openvswitch/datapath/linux/actions.o
In file included from /home/pravin/ovs/openvswitch/datapath/linux/../flow.h:33,
from
/home/pravin/ovs/openvswitch/datapath/linux/../datapath.h:30,
from /home/pravin/ovs/openvswitch/datapath/linux/actions.c:37:
/home/pravin/ovs/openvswitch/datapath/linux/compat/include/linux/flex_array.h:30:
error: field 'reciprocal_elems' has incomplete type
> Signed-off-by: Alex Wang <al...@nicira.com>
> ---
> datapath/linux/Modules.mk | 1 +
> datapath/linux/compat/flex_array.c | 2 +-
> datapath/linux/compat/include/linux/flex_array.h | 2 +-
> .../linux/compat/include/linux/reciprocal_div.h | 37
> ++++++++++++++++++++
> datapath/linux/compat/reciprocal_div.c | 30 +++++++++++-----
> 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..d70b86d 100644
> --- a/datapath/linux/compat/flex_array.c
> +++ b/datapath/linux/compat/flex_array.c
> @@ -94,7 +94,7 @@ 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;
> + struct reciprocal_value reciprocal_elems = 0;
> int max_size = 0;
>
Use {} to set zero to struct.
> 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..3ef5406 100644
> --- a/datapath/linux/compat/include/linux/flex_array.h
> +++ b/datapath/linux/compat/include/linux/flex_array.h
> @@ -27,7 +27,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..15d40db
> --- /dev/null
> +++ b/datapath/linux/compat/include/linux/reciprocal_div.h
> @@ -0,0 +1,37 @@
> +#ifndef _LINUX_RECIPROCAL_DIV_H
> +#define _LINUX_RECIPROCAL_DIV_H
> +
This constant should have WRAPPER as suffix so that we can include
reciprocal_div.h
if available.
> +#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.
> + */
> +
Include reciprocal_div.h if available.
> +#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_H */
> diff --git a/datapath/linux/compat/reciprocal_div.c
> b/datapath/linux/compat/reciprocal_div.c
> index 7ec7528..4641524 100644
> --- a/datapath/linux/compat/reciprocal_div.c
> +++ b/datapath/linux/compat/reciprocal_div.c
> @@ -1,13 +1,27 @@
> +#include <linux/kernel.h>
> #include <asm/div64.h>
> #include <linux/reciprocal_div.h>
> +#include <linux/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
> +EXPORT_SYMBOL(reciprocal_value);
Why are you exporting this symbol?
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
