net: ovs: use CRC32 accelerated flow hash if available
Subsystems (3)
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
@@ -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
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
Quoted 29 lines · Francesco Fusco
Currently OVS uses
jhash2()for calculating flow hashes in its internalflow_hash()function. The performance of theflow_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_64based 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 ofovs_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
Signed-off-by Francesco Fusco <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>Signed-off-by Thomas Graf <[email protected]>
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?
David Miller
maintainerFrom: 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".
Quoted 7 lines · David Miller
From: Jesse Gross <[email protected]>
Date: Tue, 10 Dec 2013 11:28:08 -0800Quoted 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.
Quoted 17 lines · Thomas Graf
Quoted 9 lines · David Miller
From: Jesse Gross <[email protected]>
Date: Tue, 10 Dec 2013 11:28:08 -0800Quoted 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_64centric 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.
David Miller
maintainerFrom: 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_64centric would want to live with.
The things you are listing as implicit overhead can be eliminated almost entirely using static branches.
Quoted 11 lines · David Miller
From: Jesse Gross <[email protected]>
Date: Tue, 10 Dec 2013 11:28:08 -0800Quoted 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
Quoted 13 lines · Tom Herbert
Quoted 11 lines · David Miller
From: Jesse Gross <[email protected]>
Date: Tue, 10 Dec 2013 11:28:08 -0800Quoted 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.)