[ovs-dev] [PATCH 1/3] datapath: Backport reciprocal division.
Jesse Gross
jesse at nicira.com
Thu Jul 28 21:46:06 UTC 2011
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 at nicira.com>
---
datapath/linux/.gitignore | 1 +
datapath/linux/Modules.mk | 2 +
.../linux/compat/include/linux/reciprocal_div.h | 40 ++++++++++++++++++++
datapath/linux/compat/reciprocal_div.c | 9 ++++
4 files changed, 52 insertions(+), 0 deletions(-)
create mode 100644 datapath/linux/compat/include/linux/reciprocal_div.h
create mode 100644 datapath/linux/compat/reciprocal_div.c
diff --git a/datapath/linux/.gitignore b/datapath/linux/.gitignore
index b99cbd3..d434175 100644
--- 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
--- 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
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
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;
+}
--
1.7.4.1
More information about the dev
mailing list