[ovs-dev] [PATCH 6/8] datapath: replace remaining users of arch_fast_hash with jhash

Thomas Graf tgraf at noironetworks.com
Wed Jan 7 02:10:34 UTC 2015


This patch effectively reverts commit 500f80872645 ("net: ovs: use CRC32
accelerated flow hash if available"), and other remaining arch_fast_hash()
users such as from nfsd via commit 6282cd565553 ("NFSD: Don't hand out
delegations for 30 seconds after recalling them.") where it has been used
as a hash function for bloom filtering.

While we think that these users are actually not much of concern, it has
been requested to remove the arch_fast_hash() library bits that arose
from [1] entirely as per recent discussion [2]. The main argument is that
using it as a hash may introduce bias due to its linearity (see avalanche
criterion) and thus makes it less clear (though we tried to document that)
when this security/performance trade-off is actually acceptable for a
general purpose library function.

Lets therefore avoid any further confusion on this matter and remove it to
prevent any future accidental misuse of it. For the time being, this is
going to make hashing of flow keys a bit more expensive in the ovs case,
but future work could reevaluate a different hashing discipline.

  [1] https://patchwork.ozlabs.org/patch/299369/
  [2] https://patchwork.ozlabs.org/patch/418756/

Upstream: 8754589 ("net: replace remaining users of arch_fast_hash with jhash")
Signed-off-by: Thomas Graf <tgraf at noironetworks.com>
---
 acinclude.m4                               |  1 -
 datapath/flow_table.c                      |  4 +-
 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 | 44 --------------
 7 files changed, 2 insertions(+), 215 deletions(-)
 delete mode 100644 datapath/linux/compat/hash-x86.c
 delete mode 100644 datapath/linux/compat/hash.c
 delete mode 100644 datapath/linux/compat/include/asm/hash.h
 delete mode 100644 datapath/linux/compat/include/linux/hash.h

diff --git a/acinclude.m4 b/acinclude.m4
index 2579754..10ede83 100644
--- a/acinclude.m4
+++ b/acinclude.m4
@@ -284,7 +284,6 @@ AC_DEFUN([OVS_CHECK_LINUX_COMPAT], [
 
   OVS_GREP_IFELSE([$KSRC/include/linux/err.h], [ERR_CAST])
   OVS_GREP_IFELSE([$KSRC/include/linux/err.h], [IS_ERR_OR_NULL])
-  OVS_GREP_IFELSE([$KSRC/include/linux/hash.h], [fast_hash_ops])
 
   OVS_GREP_IFELSE([$KSRC/include/linux/etherdevice.h], [eth_hw_addr_random])
   OVS_GREP_IFELSE([$KSRC/include/linux/etherdevice.h], [ether_addr_copy])
diff --git a/datapath/flow_table.c b/datapath/flow_table.c
index ad410fd..2f8f3fb 100644
--- a/datapath/flow_table.c
+++ b/datapath/flow_table.c
@@ -25,7 +25,7 @@
 #include <linux/if_vlan.h>
 #include <net/llc_pdu.h>
 #include <linux/kernel.h>
-#include <linux/hash.h>
+#include <linux/jhash.h>
 #include <linux/jiffies.h>
 #include <linux/llc.h>
 #include <linux/module.h>
@@ -448,7 +448,7 @@ static u32 flow_hash(const struct sw_flow_key *key, int key_start,
 	/* Make sure number of hash bytes are multiple of u32. */
 	BUILD_BUG_ON(sizeof(long) % sizeof(u32));
 
-	return arch_fast_hash2(hash_key, hash_u32s, 0);
+	return jhash2(hash_key, hash_u32s, 0);
 }
 
 static int flow_key_start(const struct sw_flow_key *key)
diff --git a/datapath/linux/Modules.mk b/datapath/linux/Modules.mk
index 4b38fd5..a463331 100644
--- a/datapath/linux/Modules.mk
+++ b/datapath/linux/Modules.mk
@@ -6,8 +6,6 @@ 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 \
@@ -17,7 +15,6 @@ openvswitch_sources += \
 	linux/compat/utils.c
 openvswitch_headers += \
 	linux/compat/gso.h \
-	linux/compat/include/asm/hash.h \
 	linux/compat/include/linux/percpu.h \
 	linux/compat/include/linux/bug.h \
 	linux/compat/include/linux/compiler.h \
@@ -26,7 +23,6 @@ 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
deleted file mode 100644
index ca259b9..0000000
--- a/datapath/linux/compat/hash-x86.c
+++ /dev/null
@@ -1,95 +0,0 @@
-/*
- * 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 <linux/version.h>
-#if LINUX_VERSION_CODE < KERNEL_VERSION(3,14,0)
-
-#ifdef CONFIG_X86
-
-#include <linux/hash.h>
-
-#include <asm/processor.h>
-#include <asm/cpufeature.h>
-
-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
deleted file mode 100644
index 5e0d324..0000000
--- a/datapath/linux/compat/hash.c
+++ /dev/null
@@ -1,51 +0,0 @@
-/* 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 <ffusco at redhat.com>
- * Copyright 2013 Daniel Borkmann <dborkman at redhat.com>
- * Copyright 2013 Thomas Graf <tgraf at redhat.com>
- * Licensed under the GNU General Public License, version 2.0 (GPLv2)
- */
-
-#include <linux/version.h>
-#if LINUX_VERSION_CODE < KERNEL_VERSION(3,14,0)
-
-#include <linux/cache.h>
-#include <linux/compiler.h>
-#include <linux/jhash.h>
-#include <linux/hash.h>
-#include <linux/kernel.h>
-
-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
deleted file mode 100644
index 2ed5a9b..0000000
--- a/datapath/linux/compat/include/asm/hash.h
+++ /dev/null
@@ -1,18 +0,0 @@
-#ifndef _ASM_HASH_WRAPPER_H
-#define _ASM_HASH_WRAPPER_H
-
-#include <linux/version.h>
-#if LINUX_VERSION_CODE >= KERNEL_VERSION(3,14,0)
-#include_next <asm/hash.h>
-#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
deleted file mode 100644
index 1d70dcb..0000000
--- a/datapath/linux/compat/include/linux/hash.h
+++ /dev/null
@@ -1,44 +0,0 @@
-#ifndef _LINUX_HASH_WRAPPER_H
-#define _LINUX_HASH_WRAPPER_H
-
-#include_next <linux/hash.h>
-#include <asm/hash.h>
-
-#ifndef HAVE_FAST_HASH_OPS
-
-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 /* !HASH_FAST_HASH_OPS */
-
-#endif /* _LINUX_HASH_WRAPPER_H */
-- 
1.9.3




More information about the dev mailing list