From 01308c2bb5d7970c59ea3a61554ce58736dcc2a9 Mon Sep 17 00:00:00 2001 From: Jesse Gross Date: Fri, 15 Jul 2011 09:59:05 -0700 Subject: [PATCH] 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 Acked-by: Ben Pfaff --- datapath/linux/.gitignore | 1 + datapath/linux/Modules.mk | 2 + .../compat/include/linux/reciprocal_div.h | 40 +++++++++++++++++++ datapath/linux/compat/reciprocal_div.c | 9 +++++ 4 files changed, 52 insertions(+) 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 b99cbd34..d4341759 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 217f12d4..a3fdc782 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 00000000..f618bddc --- /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 + +#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,20) +#include_next +#else + +#include + +/* + * 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 00000000..6a3bd48f --- /dev/null +++ b/datapath/linux/compat/reciprocal_div.c @@ -0,0 +1,9 @@ +#include +#include + +u32 reciprocal_value(u32 k) +{ + u64 val = (1LL << 32) + (k - 1); + do_div(val, k); + return (u32)val; +} -- 2.30.2