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 <alexw@nicira.com>
Reviewed-by: Thomas Graf <tgraf@redhat.com>
Acked-by: Pravin B Shelar <pshelar@nicira.com>

diff --git a/datapath/linux/Modules.mk b/datapath/linux/Modules.mk
index cedb8c9..1e76305 100644 (file)
--- 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 (file)
--- 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 (file)
--- 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 (file)
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..90ce7b1 100644 (file)
--- a/datapath/linux/compat/reciprocal_div.c
+++ b/datapath/linux/compat/reciprocal_div.c
@@ -1,13 +1,25 @@
+#include <linux/kernel.h>
 #include <asm/div64.h>
 #include <linux/reciprocal_div.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