datapath: Backport reciprocal division.

The reciprocal division library did not exist until 2.6.20 and is
not currently exported in any version, so this backports it.

Signed-off-by: Jesse Gross <jesse@nicira.com>
Acked-by: Ben Pfaff <blp@nicira.com>

diff --git a/datapath/linux/.gitignore b/datapath/linux/.gitignore
index b99cbd3..d434175 100644 (file)
--- a/datapath/linux/.gitignore
+++ b/datapath/linux/.gitignore
@@ -24,6 +24,7 @@
 /modules.order
 /netdevice.c
 /random32.c
+/reciprocal_div.c
 /skbuff-openvswitch.c
 /table.c
 /time.c

diff --git a/datapath/linux/Modules.mk b/datapath/linux/Modules.mk
index 217f12d..a3fdc78 100644 (file)
--- a/datapath/linux/Modules.mk
+++ b/datapath/linux/Modules.mk
@@ -5,6 +5,7 @@ openvswitch_sources += \
        linux/compat/ip_output-openvswitch.c \
        linux/compat/kmemdup.c \
        linux/compat/netdevice.c \
+       linux/compat/reciprocal_div.c \
        linux/compat/skbuff-openvswitch.c \
        linux/compat/time.c
 openvswitch_headers += \
@@ -38,6 +39,7 @@ openvswitch_headers += \
        linux/compat/include/linux/netlink.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/skbuff.h \
        linux/compat/include/linux/slab.h \

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..f618bdd
--- /dev/null
+++ b/datapath/linux/compat/include/linux/reciprocal_div.h
@@ -0,0 +1,40 @@
+#ifndef __LINUX_RECIPROCAL_DIV_WRAPPER_H
+#define __LINUX_RECIPROCAL_DIV_WRAPPER_H
+
+#include <linux/version.h>
+
+#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,20)
+#include_next <linux/reciprocal_div.h>
+#else
+
+#include <linux/types.h>
+
+/*
+ * This file describes reciprocical division.
+ *
+ * This optimizes the (A/B) problem, when A and B are two u32
+ * and B is a known value (but not known at compile time)
+ *
+ * The math principle used is :
+ *   Let RECIPROCAL_VALUE(B) be (((1LL << 32) + (B - 1))/ B)
+ *   Then A / B = (u32)(((u64)(A) * (R)) >> 32)
+ *
+ * This replaces a divide by a multiply (and a shift), and
+ * is generally less expensive in CPU cycles.
+ */
+
+/*
+ * Computes the reciprocal value (R) for the value B of the divisor.
+ * Should not be called before each reciprocal_divide(),
+ * or else the performance is slower than a normal divide.
+ */
+extern u32 reciprocal_value(u32 B);
+
+
+static inline u32 reciprocal_divide(u32 A, u32 R)
+{
+       return (u32)(((u64)A * R) >> 32);
+}
+
+#endif /* Linux kernel < 2.6.20 */
+#endif /* __LINUX_RECIPROCAL_DIV_WRAPPER_H */

diff --git a/datapath/linux/compat/reciprocal_div.c b/datapath/linux/compat/reciprocal_div.c
new file mode 100644 (file)
index 0000000..6a3bd48
--- /dev/null
+++ b/datapath/linux/compat/reciprocal_div.c
@@ -0,0 +1,9 @@
+#include <asm/div64.h>
+#include <linux/reciprocal_div.h>
+
+u32 reciprocal_value(u32 k)
+{
+       u64 val = (1LL << 32) + (k - 1);
+       do_div(val, k);
+       return (u32)val;
+}