Skip to contentSkip to conversation

net: ovs: use CRC32 accelerated flow hash if available

PATCH In review Francesco Fusco 6 participants 9 messages Dec 10, 2013

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

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

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.

One possible direction to achieve higher performance consists of replacing jhash2() with an architecture specific hash function pretty much like the Intel folks have proposed in DPDK. DPDK provides a very fast hash function that leverages the 32bit crc32l instruction part of the Intel SSE4.2 instruction set.

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 adapted and integrated Intel's hashing function from DPDK in order to be used with OVS internally. 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.

---
 net/openvswitch/flow_table.c | 12 ++++++--
 net/openvswitch/flow_table.h | 66 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 75 insertions(+), 3 deletions(-)
net/openvswitch/flow_table.c +9 -3
index e425427..262d7ca 100644
@@ -43,13 +43,16 @@
 #include <net/ip.h>
 #include <net/ipv6.h>
 #include <net/ndisc.h>
-
+#ifdef CONFIG_X86
+#include <asm/cpufeature.h>
+#endif
 #include "datapath.h"
 
 #define TBL_MIN_BUCKETS		1024
 #define REHASH_INTERVAL		(10 * 60 * HZ)
 
 static struct kmem_cache *flow_cache;
+static u32 (*__flow_hash)(const u32 *data, u32 len, u32 seed) = jhash2;
 
 static u16 range_n_bytes(const struct sw_flow_key_range *range)
 {
@@ -362,7 +365,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 __flow_hash(hash_key, hash_u32s, 0);
 }
 
 static int flow_key_start(const struct sw_flow_key *key)
@@ -581,7 +584,10 @@ int ovs_flow_init(void)
 					0, NULL);
 	if (flow_cache == NULL)
 		return -ENOMEM;
-
+#ifdef CONFIG_X86_64
+	if (cpu_has_xmm4_2)
+		__flow_hash = ovs_flow_hash_crc;
+#endif
 	return 0;
 }
 
net/openvswitch/flow_table.h +66 -0

76 lines not on this page · raw message

Signature · 1 line
1.8.3.1
#1 lore raw
Quoted 1 line

From: Francesco Fusco

...

Quoted 6 lines

One possible direction to achieve higher performance consists of replacing jhash2() with an architecture specific hash function pretty much like the Intel folks have proposed in DPDK. DPDK provides a very fast hash function that leverages the 32bit crc32l instruction part of the Intel SSE4.2 instruction set.

...

IIRC the cpu can execute multiple crc32l instructions in parallel. If you use a software lookup table to crc (say) 256 zero bytes it should be possible to crc chunks of a large buffer in parallel.

Quoted 1 line

+#ifdef CONFIG_X86_64

Why not also i386?

Quoted 5 lines
net/openvswitch/flow_table.h +5 -0
+static inline u32 ovs_flow_hash_crc_4b(u32 crc, u32 val)
+{
+	asm ("crc32l %[val], %[crc]\n"
+		: [crc] "+r" (crc)
+		: [val] "rm" (val));

net/openvswitch/flow_table.h bool ovs_flow_cmp_unmasked_key(const struct sw_flow *flow, · line 128

Quoted 10 lines
net/openvswitch/flow_table.h +10 -0
+	return crc;
+}
+
+static inline u32 ovs_flow_hash_crc(const u32 *data, u32 len, u32 seed)
+{
+	const u32 *p32 = (const u32 *) data;
+	u32 i, tmp = 0;
+
+	for (i = 0; i < len; i++)
+		seed = ovs_flow_hash_crc_4b(*p32++, seed);

Doesn't that have the arguments if the wrong order ? Maybe it doesn't affect the result, but the asm pattern works better the other way around.

net/openvswitch/flow_table.h bool ovs_flow_cmp_unmasked_key(const struct sw_flow *flow, · line 130

Quoted 1 line
net/openvswitch/flow_table.h +1 -0
+	switch (3 - ((len * 4) & 0x03)) {

This looked like an obscure way to calculate the remainder, then I noticed the 'len *4' which means it is always 3 (no residual).

Quoted 6 lines
net/openvswitch/flow_table.h +6 -0
+	case 0:
+		tmp |= *((const u8 *) p32 + 2) << 16;
+		/* Fallthrough */
+	case 1:
+		tmp |= *((const u8 *) p32 + 1) << 8;
+		/* Fallthrough */

net/openvswitch/flow_table.h bool ovs_flow_cmp_unmasked_key(const struct sw_flow *flow, · line 146

Quoted 10 lines
net/openvswitch/flow_table.h +10 -0
+	case 2:
+		tmp |= *((const u8 *) p32);
+		seed = ovs_flow_hash_crc_4b(tmp, seed);
+	default:
+		break;
+	}
+
+	return seed;
+}
+#endif

David

#2 lore raw
In reply to Francesco Fusco
Quoted 29 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.

One possible direction to achieve higher performance consists of replacing jhash2() with an architecture specific hash function pretty much like the Intel folks have proposed in DPDK. DPDK provides a very fast hash function that leverages the 32bit crc32l instruction part of the Intel SSE4.2 instruction set.

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 adapted and integrated Intel's hashing function from DPDK in order to be used with OVS internally. 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 3 lines

I think this is definitely a good optimization to do given that so much of the work that OVS does is hashing. However, isn't there a library where there would be a more appropriate place to put this?

maintainer
#3 lore raw

From: Jesse Gross <[email protected]>
Date: Tue, 10 Dec 2013 11:28:08 -0800

Quoted 3 lines

I think this is definitely a good optimization to do given that so much of the work that OVS does is hashing. However, isn't there a library where there would be a more appropriate place to put this?

I also honestly don't see why we want to special case OVS at all here. This faster hashing would be useful for socket demux and other locations in the kernel.

When I see changes like this my only reaction is "sad face".

#4 lore raw
Quoted 7 lines · David Miller

From: Jesse Gross <[email protected]>
Date: Tue, 10 Dec 2013 11:28:08 -0800

Quoted 3 lines

I think this is definitely a good optimization to do given that so much of the work that OVS does is hashing. However, isn't there a library where there would be a more appropriate place to put this?

Quoted 5 lines

I also honestly don't see why we want to special case OVS at all here. This faster hashing would be useful for socket demux and other locations in the kernel.

When I see changes like this my only reaction is "sad face".

We discussed this heavily and decided to go with the minimal approach first to collect some feedback. We were not sure whether the runtime check, function pointer and hardware dependencies are something other subsystems that are less x86_64 centric would want to live with.

That said, we are _very_ willing to do the work and move it to lib/ to make it available to other consumers but one should be aware that crc32 based hashes are not as generally usable as jhash.

#5 lore raw
Quoted 17 lines · Thomas Graf
Quoted 9 lines · David Miller

From: Jesse Gross <[email protected]>
Date: Tue, 10 Dec 2013 11:28:08 -0800

Quoted 3 lines

I think this is definitely a good optimization to do given that so much of the work that OVS does is hashing. However, isn't there a library where there would be a more appropriate place to put this?

Quoted 5 lines

I also honestly don't see why we want to special case OVS at all here. This faster hashing would be useful for socket demux and other locations in the kernel.

When I see changes like this my only reaction is "sad face".

Quoted 8 lines

We discussed this heavily and decided to go with the minimal approach first to collect some feedback. We were not sure whether the runtime check, function pointer and hardware dependencies are something other subsystems that are less x86_64 centric would want to live with.

That said, we are _very_ willing to do the work and move it to lib/ to make it available to other consumers but one should be aware that crc32 based hashes are not as generally usable as jhash.

Most hash users probably don't care what the actual hash function is, as long as it is consistent. Couldn't you have a function that uses CRC32 if it is available (or whatever is appropriate on a given architecture) and jhash otherwise? Most users would then be able to call this function without knowing or caring about the various quirks.

We could also potentially use the static key stuff to get the right hash function as well.

maintainer
#6 lore raw
In reply to Thomas Graf

From: Thomas Graf <[email protected]>
Date: Tue, 10 Dec 2013 21:47:48 +0100

Quoted 3 lines

We were not sure whether the runtime check, function pointer and hardware dependencies are something other subsystems that are less x86_64 centric would want to live with.

The things you are listing as implicit overhead can be eliminated almost entirely using static branches.

#7 lore raw
In reply to David Miller
Quoted 11 lines · David Miller

From: Jesse Gross <[email protected]>
Date: Tue, 10 Dec 2013 11:28:08 -0800

Quoted 3 lines

I think this is definitely a good optimization to do given that so much of the work that OVS does is hashing. However, isn't there a library where there would be a more appropriate place to put this?

I also honestly don't see why we want to special case OVS at all here. This faster hashing would be useful for socket demux and other locations in the kernel.

Also, we already do a lot of work to compute flow hashes for packets in both TX and RX. Can these be leveraged? For instance, if OVS is computing a 5-tuple hash on an RX packet it's probably redundant to skb->rxhash.

Quoted 5 lines

When I see changes like this my only reaction is "sad face". --
To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#8 lore raw
Quoted 13 lines · Tom Herbert
Quoted 11 lines · David Miller

From: Jesse Gross <[email protected]>
Date: Tue, 10 Dec 2013 11:28:08 -0800

Quoted 3 lines

I think this is definitely a good optimization to do given that so much of the work that OVS does is hashing. However, isn't there a library where there would be a more appropriate place to put this?

I also honestly don't see why we want to special case OVS at all here. This faster hashing would be useful for socket demux and other locations in the kernel.

Quoted 4 lines

Also, we already do a lot of work to compute flow hashes for packets in both TX and RX. Can these be leveraged? For instance, if OVS is computing a 5-tuple hash on an RX packet it's probably redundant to skb->rxhash.

That's true if we care about exactly the 5-tuple. However, the set of fields that are included in the OVS flow lookup is dynamically generated down to a bit mask so I don't know if it's worth special casing. (In fact, I don't think that current OVS userspace will ever actually emit exactly a 5-tuple.)