Skip to contentSkip to conversation

ovs: introduce arch-specific fast hashing improvements

PATCH In review Francesco Fusco 7 participants 12 messages Dec 12, 2013 – Dec 17, 2013 2 messages not in the archive

Subsystems (6)
lore
Share & tools
lore
#0 lore raw

v2 cover ovs: introduce arch-specific fast hashing improvements

From: Daniel Borkmann <[email protected]>

We are introducing a fast hash function (see patch1) that can be used in the context of OpenVSwitch to reduce the hashing footprint (patch2). For details, please see individual patches!

Thanks !

v1->v2:
- Make hash generic and place it under lib

Francesco Fusco (2):
lib: introduce arch optimized hash library
net: ovs: use CRC32 accelerated flow hash if available

 arch/x86/include/asm/hash.h  |  7 ++++
 arch/x86/lib/Makefile        |  2 +-
 arch/x86/lib/hash.c          | 88 ++++++++++++++++++++++++++++++++++++++++++++
 include/asm-generic/hash.h   |  9 +++++
 include/linux/hash.h         | 36 ++++++++++++++++++
 lib/Makefile                 |  2 +-
 lib/hash.c                   | 38 +++++++++++++++++++
 net/openvswitch/flow_table.c |  4 +-
 8 files changed, 182 insertions(+), 4 deletions(-)
 create mode 100644 arch/x86/include/asm/hash.h
 create mode 100644 arch/x86/lib/hash.c
 create mode 100644 include/asm-generic/hash.h
 create mode 100644 lib/hash.c
Signature · 1 line
1.8.3.1
#1 lore raw

PATCH v2 1/2 lib: introduce arch optimized hash library

We introduce a new hashing library that is meant to be used in the contexts where speed is more important than uniformity of the hashed values. The hash library leverages architecture specific implementation to achieve high performance and fall backs to jhash() for the generic case.

On Intel-based x86 architectures, the library can exploit the crc32l instruction, part of the Intel SSE4.2 instruction set, if the instruction is supported by the processor. This implementation is twice as fast as the jhash() implementation on an i7 processor.

Additional architectures, such as Arm64 provide instructions for accelerating the computation of CRC, so they could be added as well in follow-up work.

---
 arch/x86/include/asm/hash.h |  7 ++++
 arch/x86/lib/Makefile       |  2 +-
 arch/x86/lib/hash.c         | 88 +++++++++++++++++++++++++++++++++++++++++++++
 include/asm-generic/hash.h  |  9 +++++
 include/linux/hash.h        | 36 +++++++++++++++++++
 lib/Makefile                |  2 +-
 lib/hash.c                  | 38 ++++++++++++++++++++
 7 files changed, 180 insertions(+), 2 deletions(-)
 create mode 100644 arch/x86/include/asm/hash.h
 create mode 100644 arch/x86/lib/hash.c
 create mode 100644 include/asm-generic/hash.h
 create mode 100644 lib/hash.c
arch/x86/include/asm/hash.h new file +7 -0
new file mode 100644
index 0000000..e8c58f8
@@ -0,0 +1,7 @@
+#ifndef _ASM_X86_HASH_H
+#define _ASM_X86_HASH_H
+
+struct fast_hash_ops;
+extern void setup_arch_fast_hash(struct fast_hash_ops *ops);
+
+#endif /* _ASM_X86_HASH_H */
arch/x86/lib/Makefile +1 -1
index 992d63b..eabcb6e 100644
@@ -24,7 +24,7 @@ lib-$(CONFIG_SMP) += rwlock.o
 lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
 lib-$(CONFIG_INSTRUCTION_DECODER) += insn.o inat.o
 
-obj-y += msr.o msr-reg.o msr-reg-export.o
+obj-y += msr.o msr-reg.o msr-reg-export.o hash.o
 
 ifeq ($(CONFIG_X86_32),y)
         obj-y += atomic64_32.o
arch/x86/lib/hash.c new file +88 -0

88 lines not on this page · raw message

include/asm-generic/hash.h new file +9 -0
new file mode 100644
index 0000000..05cb342
@@ -0,0 +1,9 @@
+#ifndef __ASM_GENERIC_HASH_H
+#define __ASM_GENERIC_HASH_H
+
+struct arch_hash_ops;
+static inline void setup_arch_fast_hash(struct arch_hash_ops *ops)
+{
+}
+
+#endif /* __ASM_GENERIC_HASH_H */
include/linux/hash.h +36 -0
index f09a0ae..bd1754c 100644
@@ -15,6 +15,7 @@
  */
 
 #include <asm/types.h>
+#include <asm/hash.h>
 #include <linux/compiler.h>
 
 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
@@ -78,4 +79,39 @@ static inline u32 hash32_ptr(const void *ptr)
 #endif
 	return (u32)val;
 }
+
+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 /* _LINUX_HASH_H */
lib/Makefile +1 -1
index a459c31..d0f79c5 100644
@@ -26,7 +26,7 @@ obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
 	 bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
 	 gcd.o lcm.o list_sort.o uuid.o flex_array.o iovec.o clz_ctz.o \
 	 bsearch.o find_last_bit.o find_next_bit.o llist.o memweight.o kfifo.o \
-	 percpu-refcount.o percpu_ida.o
+	 percpu-refcount.o percpu_ida.o hash.o
 obj-y += string_helpers.o
 obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o
 obj-y += kstrtox.o
lib/hash.c new file +38 -0
new file mode 100644
index 0000000..b89f06a
@@ -0,0 +1,38 @@
+/* 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 <[email protected]>
+ * Copyright 2013 Daniel Borkmann <[email protected]>
+ * Copyright 2013 Thomas Graf <[email protected]>
+ * Licensed under the GNU General Public License, version 2.0 (GPLv2)
+ */
+
+#include <linux/jhash.h>
+#include <linux/hash.h>
+
+static struct fast_hash_ops arch_hash_ops __read_mostly = {
+	.hash  = jhash,
+	.hash2 = jhash2,
+};
+
+u32 arch_fast_hash(const void *data, u32 len, u32 seed)
+{
+	return arch_hash_ops.hash(data, len, seed);
+}
+EXPORT_SYMBOL_GPL(arch_fast_hash);
+
+u32 arch_fast_hash2(const u32 *data, u32 len, u32 seed)
+{
+	return arch_hash_ops.hash2(data, len, seed);
+}
+EXPORT_SYMBOL_GPL(arch_fast_hash2);
+
+static int __init hashlib_init(void)
+{
+	setup_arch_fast_hash(&arch_hash_ops);
+	return 0;
+}
+early_initcall(hashlib_init);
Signature · 1 line
1.8.3.1
#2 lore raw

Re: [PATCH net-next v2 1/2] lib: introduce arch optimized hash library

Quoted 65 lines · Francesco Fusco

We introduce a new hashing library that is meant to be used in the contexts where speed is more important than uniformity of the hashed values. The hash library leverages architecture specific implementation to achieve high performance and fall backs to jhash() for the generic case.

On Intel-based x86 architectures, the library can exploit the crc32l instruction, part of the Intel SSE4.2 instruction set, if the instruction is supported by the processor. This implementation is twice as fast as the jhash() implementation on an i7 processor.

Additional architectures, such as Arm64 provide instructions for accelerating the computation of CRC, so they could be added as well in follow-up work.

---
  arch/x86/include/asm/hash.h |  7 ++++
  arch/x86/lib/Makefile       |  2 +-
  arch/x86/lib/hash.c         | 88 +++++++++++++++++++++++++++++++++++++++++++++
  include/asm-generic/hash.h  |  9 +++++
  include/linux/hash.h        | 36 +++++++++++++++++++
  lib/Makefile                |  2 +-
  lib/hash.c                  | 38 ++++++++++++++++++++
  7 files changed, 180 insertions(+), 2 deletions(-)

create mode 100644 arch/x86/include/asm/hash.h
create mode 100644 arch/x86/lib/hash.c
create mode 100644 include/asm-generic/hash.h
create mode 100644 lib/hash.c

arch/x86/include/asm/hash.h new file +7 -0
new file mode 100644
index 0000000..e8c58f8
@@ -0,0 +1,7 @@
+#ifndef _ASM_X86_HASH_H
+#define _ASM_X86_HASH_H
+
+struct fast_hash_ops;
+extern void setup_arch_fast_hash(struct fast_hash_ops *ops);
+
+#endif /* _ASM_X86_HASH_H */
arch/x86/lib/Makefile +1 -1
index 992d63b..eabcb6e 100644
@@ -24,7 +24,7 @@ lib-$(CONFIG_SMP) += rwlock.o
  lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
  lib-$(CONFIG_INSTRUCTION_DECODER) += insn.o inat.o
 
-obj-y += msr.o msr-reg.o msr-reg-export.o
+obj-y += msr.o msr-reg.o msr-reg-export.o hash.o
 
  ifeq ($(CONFIG_X86_32),y)
          obj-y += atomic64_32.o
arch/x86/lib/hash.c new file +0 -0
new file mode 100644
index 0000000..3056702

arch/x86/lib/hash.c line 5

Quoted 5 lines
arch/x86/lib/hash.c new file +5 -0
@@ -0,0 +1,88 @@
+/*
+ * Some portions derived from code covered by the following notice:
+ *
+ * Copyright (c) 2010-2013 Intel Corporation. All rights reserved.
+ * All rights reserved.

Is it possible to trace that this comes from the DPDK? At least in the commit log, like it was done in the v1.

Quoted 27 lines
arch/x86/lib/hash.c new file +27 -0
+ *
+ * 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.
+ */

arch/x86/lib/hash.c line 42

Quoted 10 lines
arch/x86/lib/hash.c new file +10 -0
+
+#include <linux/hash.h>
+
+#include <asm/processor.h>
+#include <asm/cpufeature.h>
+#include <asm/hash.h>
+
+static inline u32 crc32_u32(u32 crc, u32 val)
+{
+	asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));

I'm not an expert, but is it not possible to use intrisics functions, like it is done in the original code?

Regards,
Nicolas

#3 lore raw

Re: [PATCH net-next v2 1/2] lib: introduce arch optimized hash library

On 12/12/2013 06:54 PM, Nicolas Dichtel wrote:
...

Quoted 2 lines

Is it possible to trace that this comes from the DPDK? At least in the commit log, like it was done in the v1.

Hm, that got lost; but we can put that back into the commit log. In any case, we properly included the header comment, of course.

Quoted 5 lines

arch/x86/lib/hash.c line 42

Quoted 3 lines
arch/x86/lib/hash.c new file +3 -0
+static inline u32 crc32_u32(u32 crc, u32 val)
+{
+    asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));

I'm not an expert, but is it not possible to use intrisics functions, like it is done in the original code?

Intrinsics are not used/available in the kernel, so we used asm as everywhere else.

#4 lore raw

PATCH v2 2/2 net: ovs: use CRC32 accelerated flow hash if available

In reply to Francesco Fusco

Currently OVS uses jhash2() for calculating flow hashes in its internal flow_hash() function. The performance of the flow_hash() function is critical, as the input data can be hundreds of bytes long.

OVS is largely deployed in x86_64 based datacenters. Therefore, we argue that the performance critical fast path of OVS should exploit underlying CPU features in order to reduce the per packet processing costs. We replace jhash2 with the hash implementation provided by the kernel hash lib, which exploits the crc32l instruction to achieve high performance

Our patch greatly reduces the hash footprint from ~200 cycles of jhash2() to around ~90 cycles in case of ovs_flow_hash_crc() (measured with rdtsc over maximum length flow keys on an i7 Intel CPU).

Additionally, we wrote a microbenchmark to stress the flow table performance. The benchmark inserts random flows into the flow hash and then performs lookups. Our hash deployed on a CRC32 capable CPU reduces the lookup for 1000 flows, 100 masks from ~10,100us to ~6,700us, for example.

Thus, simply use the newly introduced arch_fast_hash2() as a drop-in replacement.

---
 net/openvswitch/flow_table.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
net/openvswitch/flow_table.c +2 -2
index e425427..0e720c3 100644
@@ -25,7 +25,7 @@
 #include <linux/if_vlan.h>
 #include <net/llc_pdu.h>
 #include <linux/kernel.h>
-#include <linux/jhash.h>
+#include <linux/hash.h>
 #include <linux/jiffies.h>
 #include <linux/llc.h>
 #include <linux/module.h>
@@ -362,7 +362,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 jhash2(hash_key, hash_u32s, 0);
+	return arch_fast_hash2(hash_key, hash_u32s, 0);
 }
 
 static int flow_key_start(const struct sw_flow_key *key)
Signature · 1 line
1.8.3.1
Acked-by on v2 2/2
#5 lore raw

Re: [PATCH net-next v2 2/2] net: ovs: use CRC32 accelerated flow hash if available

Quoted 23 lines · Francesco Fusco

Currently OVS uses jhash2() for calculating flow hashes in its internal flow_hash() function. The performance of the flow_hash() function is critical, as the input data can be hundreds of bytes long.

OVS is largely deployed in x86_64 based datacenters. Therefore, we argue that the performance critical fast path of OVS should exploit underlying CPU features in order to reduce the per packet processing costs. We replace jhash2 with the hash implementation provided by the kernel hash lib, which exploits the crc32l instruction to achieve high performance

Our patch greatly reduces the hash footprint from ~200 cycles of jhash2() to around ~90 cycles in case of ovs_flow_hash_crc() (measured with rdtsc over maximum length flow keys on an i7 Intel CPU).

Additionally, we wrote a microbenchmark to stress the flow table performance. The benchmark inserts random flows into the flow hash and then performs lookups. Our hash deployed on a CRC32 capable CPU reduces the lookup for 1000 flows, 100 masks from ~10,100us to ~6,700us, for example.

Quoted 6 lines

Thus, simply use the newly introduced arch_fast_hash2() as a drop-in replacement.

Out of curiosity, did you try using crc32q? OVS data structures are already aligned to 8 bytes. It would also be interesting to know if a parallelized implementation is worthwhile, although my guess is that the OVS flow key is not quite long enough.

#6 lore raw

Re: [PATCH net-next v2 2/2] net: ovs: use CRC32 accelerated flow hash if available

Quoted 4 lines · Jesse Gross

Out of curiosity, did you try using crc32q? OVS data structures are already aligned to 8 bytes. It would also be interesting to know if a parallelized implementation is worthwhile, although my guess is that the OVS flow key is not quite long enough.

We did not try with crc32q yet because we had the very same concerns.
In the general case, when the length of the key is not a multiple of 8 bytes, we will have to use the crc32q to process multiple 64 bit numbers, then process the the rest with a crc32l. My guess is that the performance benefit won't be that high.

But we will try that out and if the outcome will be positive, we will submit a follow up patch.

Best,
Francesco

#7 lore raw

Re: [PATCH net-next v2 2/2] net: ovs: use CRC32 accelerated flow hash if available

Quoted 8 lines · Francesco Fusco
Quoted 5 lines · Jesse Gross

Out of curiosity, did you try using crc32q? OVS data structures are already aligned to 8 bytes. It would also be interesting to know if a parallelized implementation is worthwhile, although my guess is that the OVS flow key is not quite long enough.

Quoted 5 lines

We did not try with crc32q yet because we had the very same concerns. In the general case, when the length of the key is not a multiple of 8 bytes, we will have to use the crc32q to process multiple 64 bit numbers, then process the the rest with a crc32l. My guess is that the performance benefit won't be that high.

On 64-bit platforms, OVS already enforces alignment and multiples of 8 bytes for flow keys. If we introduced a hash primitive that does 8 bytes at a time instead of 4, there should be nothing extra to process (although I don't know how big the upside would be).

A message that is not in the archive (sent off-list or not yet received): CAEP_g=-JBT_XVvwSa4xOwVoTysoL0Z8zJc-ERSHJc96+qrA99Q-JsoAwUIsXosN+BqQ9rBEUg@public.gmane.org

#9 lore raw

Re: [PATCH net-next v2 2/2] net: ovs: use CRC32 accelerated flow hash if available

Quoted 1 line

From: Jesse Gross

...

Quoted 4 lines

Out of curiosity, did you try using crc32q? OVS data structures are already aligned to 8 bytes. It would also be interesting to know if a parallelized implementation is worthwhile, although my guess is that the OVS flow key is not quite long enough.

My thoughts exactly.
Given this is a hash it could crc alternate words into separate accumulators and the combine the values at the end. That way you are still doing sequential accesses to the data. (The crc instruction might be better than an xor for the combine.) If the cpu has 3 execution units that can do crc, use them all.

It might be that the hash function is now an insignificant cost. Looking at how much hashing the data twice (discarding the first result - assign to global volatile data) slows things down can help determine this.

David

#10 lore raw

Re: [PATCH net-next v2 2/2] net: ovs: use CRC32 accelerated flow hash if available

Quoted 11 lines · David Laight

My thoughts exactly.
Given this is a hash it could crc alternate words into separate accumulators and the combine the values at the end. That way you are still doing sequential accesses to the data. (The crc instruction might be better than an xor for the combine.) If the cpu has 3 execution units that can do crc, use them all.

It might be that the hash function is now an insignificant cost. Looking at how much hashing the data twice (discarding the first result - assign to global volatile data) slows things down can help determine this.

On i7 CPUs the crc32/crc64 instructions have a throughput
of 1 cycle and a latency of 3 cycles [1], which means that 1) with this code we pay 3 clocks per crc32 instruction, and 2) we could compute three CRCs in parallel, each processing 1/3 of the data during the same clock. This could in theory provide 3x the performance.

For short keys (~100 bytes and less) there is chance that the 3x theoretical speedup will be destroyed by the additional code required to compute boundaries, xor the results, etc. But as I already mentioned, this is something to try.

[1] http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-paper.pdf

maintainer
#11 lore raw
In reply to Francesco Fusco

From: Francesco Fusco <[email protected]>
Date: Thu, 12 Dec 2013 16:09:04 +0100

Quoted 3 lines

We are introducing a fast hash function (see patch1) that can be used in the context of OpenVSwitch to reduce the hashing footprint (patch2). For details, please see individual patches!

No objections from my side, I'll let the x86 folks get a chance to review this. I can add this optimization on sparc64 chips that have the crc instructions too.

I think we'll need to add implementations hash_3words, hash_2words, and hash_1word when we try to take advantage of this in the networking more generally.

A message that is not in the archive (sent off-list or not yet received): 1386860946-1621-1-git-send-email-ffusco-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org

#13 lore raw

From: Francesco Fusco <[email protected]>
Date: Thu, 12 Dec 2013 16:09:04 +0100

Quoted 10 lines

From: Daniel Borkmann <[email protected]>

We are introducing a fast hash function (see patch1) that can be used in the context of OpenVSwitch to reduce the hashing footprint (patch2). For details, please see individual patches!

Thanks !

v1->v2:
- Make hash generic and place it under lib

Series applied, thanks.