From 3c851001cbd55b080eaaa1c89ae033d8129cac28 Mon Sep 17 00:00:00 2001 From: Jesse Gross Date: Mon, 16 Dec 2013 00:44:05 -0800 Subject: [PATCH] datapath: Backport for architecture hash library. The architecture-specific hash library automatically selects either jhash or CRC32 if it is available on the current processor. Signed-off-by: Jesse Gross --- datapath/linux/Modules.mk | 4 + datapath/linux/compat/hash-x86.c | 95 ++++++++++++++++++++++ datapath/linux/compat/hash.c | 51 ++++++++++++ datapath/linux/compat/include/asm/hash.h | 18 ++++ datapath/linux/compat/include/linux/hash.h | 45 ++++++++++ 5 files changed, 213 insertions(+) create mode 100644 datapath/linux/compat/hash-x86.c create mode 100644 datapath/linux/compat/hash.c create mode 100644 datapath/linux/compat/include/asm/hash.h create mode 100644 datapath/linux/compat/include/linux/hash.h diff --git a/datapath/linux/Modules.mk b/datapath/linux/Modules.mk index fee132e6e..2f4a9c223 100644 --- a/datapath/linux/Modules.mk +++ b/datapath/linux/Modules.mk @@ -6,6 +6,8 @@ openvswitch_sources += \ linux/compat/gre.c \ linux/compat/gso.c \ linux/compat/genetlink-openvswitch.c \ + linux/compat/hash.c \ + linux/compat/hash-x86.c \ linux/compat/ip_tunnels_core.c \ linux/compat/netdevice.c \ linux/compat/net_namespace.c \ @@ -15,6 +17,7 @@ openvswitch_sources += \ linux/compat/utils.c openvswitch_headers += \ linux/compat/gso.h \ + linux/compat/include/asm/hash.h \ linux/compat/include/asm/percpu.h \ linux/compat/include/linux/compiler.h \ linux/compat/include/linux/compiler-gcc.h \ @@ -22,6 +25,7 @@ openvswitch_headers += \ linux/compat/include/linux/err.h \ linux/compat/include/linux/etherdevice.h \ linux/compat/include/linux/flex_array.h \ + linux/compat/include/linux/hash.h \ linux/compat/include/linux/icmp.h \ linux/compat/include/linux/icmpv6.h \ linux/compat/include/linux/if.h \ diff --git a/datapath/linux/compat/hash-x86.c b/datapath/linux/compat/hash-x86.c new file mode 100644 index 000000000..ca259b910 --- /dev/null +++ b/datapath/linux/compat/hash-x86.c @@ -0,0 +1,95 @@ +/* + * Some portions derived from code covered by the following notice: + * + * Copyright (c) 2010-2013 Intel Corporation. All rights reserved. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Intel Corporation nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#if LINUX_VERSION_CODE < KERNEL_VERSION(3,14,0) + +#ifdef CONFIG_X86 + +#include + +#include +#include + +static inline u32 crc32_u32(u32 crc, u32 val) +{ + asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val)); + return crc; +} + +static u32 intel_crc4_2_hash(const void *data, u32 len, u32 seed) +{ + const u32 *p32 = (const u32 *) data; + u32 i, tmp = 0; + + for (i = 0; i < len / 4; i++) + seed = crc32_u32(*p32++, seed); + + switch (3 - (len & 0x03)) { + case 0: + tmp |= *((const u8 *) p32 + 2) << 16; + /* fallthrough */ + case 1: + tmp |= *((const u8 *) p32 + 1) << 8; + /* fallthrough */ + case 2: + tmp |= *((const u8 *) p32); + seed = crc32_u32(tmp, seed); + default: + break; + } + + return seed; +} + +static u32 intel_crc4_2_hash2(const u32 *data, u32 len, u32 seed) +{ + const u32 *p32 = (const u32 *) data; + u32 i; + + for (i = 0; i < len; i++) + seed = crc32_u32(*p32++, seed); + + return seed; +} + +void setup_arch_fast_hash(struct fast_hash_ops *ops) +{ + if (cpu_has_xmm4_2) { + ops->hash = intel_crc4_2_hash; + ops->hash2 = intel_crc4_2_hash2; + } +} + +#endif /* CONFIG_X86 */ +#endif /* < 3.14 */ diff --git a/datapath/linux/compat/hash.c b/datapath/linux/compat/hash.c new file mode 100644 index 000000000..5e0d32425 --- /dev/null +++ b/datapath/linux/compat/hash.c @@ -0,0 +1,51 @@ +/* General purpose hashing library + * + * That's a start of a kernel hashing library, which can be extended + * with further algorithms in future. arch_fast_hash{2,}() will + * eventually resolve to an architecture optimized implementation. + * + * Copyright 2013 Francesco Fusco + * Copyright 2013 Daniel Borkmann + * Copyright 2013 Thomas Graf + * Licensed under the GNU General Public License, version 2.0 (GPLv2) + */ + +#include +#if LINUX_VERSION_CODE < KERNEL_VERSION(3,14,0) + +#include +#include +#include +#include +#include + +static struct fast_hash_ops arch_hash_ops __read_mostly = { + .hash = jhash, + .hash2 = jhash2, +}; + +static bool arch_inited __read_mostly; +static void init_arch(void) +{ + if (likely(arch_inited)) + return; + + setup_arch_fast_hash(&arch_hash_ops); + arch_inited = true; +} + +u32 arch_fast_hash(const void *data, u32 len, u32 seed) +{ + init_arch(); + + return arch_hash_ops.hash(data, len, seed); +} + +u32 arch_fast_hash2(const u32 *data, u32 len, u32 seed) +{ + init_arch(); + + return arch_hash_ops.hash2(data, len, seed); +} + +#endif /* < 3.14 */ diff --git a/datapath/linux/compat/include/asm/hash.h b/datapath/linux/compat/include/asm/hash.h new file mode 100644 index 000000000..2ed5a9b50 --- /dev/null +++ b/datapath/linux/compat/include/asm/hash.h @@ -0,0 +1,18 @@ +#ifndef _ASM_HASH_WRAPPER_H +#define _ASM_HASH_WRAPPER_H + +#include +#if LINUX_VERSION_CODE >= KERNEL_VERSION(3,14,0) +#include_next +#else + +struct fast_hash_ops; +#ifdef CONFIG_X86 +extern void setup_arch_fast_hash(struct fast_hash_ops *ops); +#else +static inline void setup_arch_fast_hash(struct fast_hash_ops *ops) { } +#endif + +#endif /* < 3.14 */ + +#endif /* _ASM_HASH_WRAPPER_H */ diff --git a/datapath/linux/compat/include/linux/hash.h b/datapath/linux/compat/include/linux/hash.h new file mode 100644 index 000000000..ac8531b3a --- /dev/null +++ b/datapath/linux/compat/include/linux/hash.h @@ -0,0 +1,45 @@ +#ifndef _LINUX_HASH_WRAPPER_H +#define _LINUX_HASH_WRAPPER_H + +#include_next + +#include +#if LINUX_VERSION_CODE < KERNEL_VERSION(3,14,0) +#include + +struct fast_hash_ops { + u32 (*hash)(const void *data, u32 len, u32 seed); + u32 (*hash2)(const u32 *data, u32 len, u32 seed); +}; + +/** + * arch_fast_hash - Caclulates a hash over a given buffer that can have + * arbitrary size. This function will eventually use an + * architecture-optimized hashing implementation if + * available, and trades off distribution for speed. + * + * @data: buffer to hash + * @len: length of buffer in bytes + * @seed: start seed + * + * Returns 32bit hash. + */ +extern u32 arch_fast_hash(const void *data, u32 len, u32 seed); + +/** + * arch_fast_hash2 - Caclulates a hash over a given buffer that has a + * size that is of a multiple of 32bit words. This + * function will eventually use an architecture- + * optimized hashing implementation if available, + * and trades off distribution for speed. + * + * @data: buffer to hash (must be 32bit padded) + * @len: number of 32bit words + * @seed: start seed + * + * Returns 32bit hash. + */ +extern u32 arch_fast_hash2(const u32 *data, u32 len, u32 seed); +#endif /* < 3.14 */ + +#endif /* _LINUX_HASH_WRAPPER_H */ -- 2.43.0