From a27ce57b65959a3fb796ebb20958930624b0732e Mon Sep 17 00:00:00 2001 From: Alex Wang Date: Fri, 14 Mar 2014 11:47:30 -0700 Subject: [PATCH] datapath: compat: Downstream the reciprocal_div.{c,h}. 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 Reviewed-by: Thomas Graf Acked-by: Pravin B Shelar --- datapath/linux/Modules.mk | 1 + datapath/linux/compat/flex_array.c | 2 +- .../linux/compat/include/linux/flex_array.h | 3 +- .../compat/include/linux/reciprocal_div.h | 37 +++++++++++++++++++ datapath/linux/compat/reciprocal_div.c | 28 ++++++++++---- 5 files changed, 61 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 cedb8c92d..1e76305c6 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 1e6d9c18b..c39dd1b5f 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 1cc6648a5..443c4af3b 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 #else +#include #include #include @@ -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 000000000..2def5c6ca --- /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 + +/* + * 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 7ec752840..90ce7b1ca 100644 --- a/datapath/linux/compat/reciprocal_div.c +++ b/datapath/linux/compat/reciprocal_div.c @@ -1,13 +1,25 @@ +#include #include #include -#include -#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 -- 2.43.0