Simplified 16 bit Toeplitz hash algorithm
Subsystems (2)
cover Simplified 16 bit Toeplitz hash algorithm
This patch series is meant to be a proof of concept for simplifying the cost of Toeplitz hashing by reducing the complexity of the key to a 16 bit repeating value. The resultant advantages are that the hash computation performance is significantly increased, and that the resultant hash is the same for flows in either direction.
The idea for this occurred to me while working on the ATR hashing algorithms and improving their performance. ATR implements a 32 bit repeating key which results in us being able to XOR everything down to a 32 bit value. By using a 16 bit key we are able to cut down the 12 to 36 byte input value to only 2 bytes via XOR operations. This reduces the resultant hash to 16 bits, however since queue selection only requires 7 bits for RSS that still leaves us with a large enough resultant key.
I'm currently not planning to do any more work on this in the near future as I have several other projects in which I am currently engaged. However I just wanted to put this code out there in case anyone had a use for it.
Thanks,
Alex
---
Alexander Duyck (3):
igb: example of how to update igb to make use of in-kernel Toeplitz hashing
ixgbe: example of how to update ixgbe to make use of in-kernel Toeplitz hash
net: add simplified 16 bit Toeplitz hash function for transmit side hashing
drivers/net/igb/igb_main.c | 22 ++++------ drivers/net/ixgbe/ixgbe_main.c | 47 ++++++++++++--------- include/linux/netdevice.h | 2 + include/linux/toeplitz.h | 89 ++++++++++++++++++++++++++++++++++++++++ net/core/dev.c | 68 +++++++++++++++++++++++++++++++ 5 files changed, 195 insertions(+), 33 deletions(-) create mode 100644 include/linux/toeplitz.h
RFC PATCH 1/3 net: add simplified 16 bit Toeplitz hash function for transmit side hashing
This change provides transmit side scaling functionality by providing a hash function that uses the 16 bit key to determine the queue number that should be used for transmit.
The advantages of the 16 bit key are two fold. First it allows for a much simpler computation as the number of outcomes are reduced to 64K, and generation of the hash can be done using only 64bytes of data with 4 lookups in said data. The second advantage is that both TX and RX sides will generate the same hash while using the same function. This is due the fact that both source and destination will see the same key even though the destination port is offset 16 bits from the source. The downside of this is that the resultant hash is only 16 bits wide itself. It can be expanded to 32 bits, but the 2nd 16 bits will be identical to the first.
---
include/linux/netdevice.h | 2 + include/linux/toeplitz.h | 89 +++++++++++++++++++++++++++++++++++++++++++++ net/core/dev.c | 68 ++++++++++++++++++++++++++++++++++ 3 files changed, 159 insertions(+), 0 deletions(-) create mode 100644 include/linux/toeplitz.h
include/linux/netdevice.h +2 -0
@@ -2370,6 +2370,8 @@ static inline u32 dev_ethtool_get_flags(struct net_device *dev)return dev->ethtool_ops->get_flags (dev); } +extern u16 toeplitz_select_queue (struct net_device *dev,struct sk_buff *skb); +/* Logging, debugging and troubleshooting/diagnostic helpers. */ /* netdev_printk helpers, similar to dev_printk */
include/linux/toeplitz.h new file +89 -0
89 lines not on this page · raw message
net/core/dev.c +68 -0
80 lines not on this page · raw message
RFC PATCH 2/3 ixgbe: example of how to update ixgbe to make use of in-kernel Toeplitz hash
In reply to Alexander DuyckThis change allows ixgbe to make use of the in-kernel Toeplitz hashing so that RX and TX hash queues can be matched up.
---
drivers/net/ixgbe/ixgbe_main.c | 47 ++++++++++++++++++++++------------------ 1 files changed, 26 insertions(+), 21 deletions(-)
drivers/net/ixgbe/ixgbe_main.c +26 -21
@@ -42,6 +42,7 @@#include <linux/ethtool.h> #include <linux/if_vlan.h> #include <scsi/fc/fc_fcoe.h> +#include <linux/toeplitz.h> #include "ixgbe.h" #include "ixgbe_common.h"
@@ -2847,27 +2848,31 @@ static void ixgbe_configure_srrctl(struct ixgbe_adapter *adapter,static void ixgbe_setup_mrqc (struct ixgbe_adapter *adapter) {struct ixgbe_hw *hw = &adapter->hw; -static const u32 seed[10 ] = {0xE291D73D ,0x1805EC6C ,0x2A94B30D , -0xA54F2BEC ,0xEA49AF7C ,0xE214AD3D ,0xB855AABE , -0x6A3E67EA ,0x14364D17 ,0x3BED200D }; -u32 mrqc =0 , reta =0 ; +u32 mrqc =0 ;u32 rxcsum; -int i, j; +int i, j, indices;int mask;/* Fill out hash function seeds */ -for (i =0 ; i <10 ; i++) -IXGBE_WRITE_REG (hw,IXGBE_RSSRK (i), seed[i]); +for (i =0 ; i <10 ; i++) { +u32 toeplitz_key = (u32 )toeplitz_get_key_byte ((4 * i)); + toeplitz_key |= (u32 )toeplitz_get_key_byte ((4 * i) +1 ) <<8 ; + toeplitz_key |= (u32 )toeplitz_get_key_byte ((4 * i) +2 ) <<16 ; + toeplitz_key |= (u32 )toeplitz_get_key_byte ((4 * i) +3 ) <<24 ; +IXGBE_WRITE_REG (hw,IXGBE_RSSRK (i), toeplitz_key); + }/* Fill out redirection table */ -for (i =0 , j =0 ; i <128 ; i++, j++) { -if (j == adapter->ring_feature[RING_F_RSS ].indices) - j =0 ; + indices = adapter->ring_feature[RING_F_RSS ].indices; +for (i =0 ; i <32 ; i++) { +u32 reta =0 ;/* reta = 4-byte sliding window of * 0x00..(indices-1)(indices-1)00..etc. */ - reta = (reta <<8 ) | (j *0x11 ); -if ((i &3 ) ==3 ) -IXGBE_WRITE_REG (hw,IXGBE_RETA (i >>2 ), reta); +for (j =0 ; j <4 ; j++) { +u32 entry = (indices * ((i *4 ) + j)) >>7 ; + reta |= entry << (8 * j); + } +IXGBE_WRITE_REG (hw,IXGBE_RETA (i), reta); }/* Disable indicating checksum in descriptor, enables RSS hash */
@@ -6643,14 +6648,8 @@ static u16 ixgbe_select_queue(struct net_device *dev, struct sk_buff *skb) #endif } } -#endif - -if (adapter->flags &IXGBE_FLAG_FDIR_HASH_CAPABLE ) { -while (unlikely (txq >= dev->real_num_tx_queues)) - txq -= dev->real_num_tx_queues; -return txq; - } +#endif if (adapter->flags &IXGBE_FLAG_DCB_ENABLED ) {if (skb->priority ==TC_PRIO_CONTROL ) txq = adapter->ring_feature[RING_F_DCB ].indices-1 ;
@@ -6660,7 +6659,13 @@ static u16 ixgbe_select_queue(struct net_device *dev, struct sk_buff *skb)return txq; } -return skb_tx_hash (dev, skb); +if (adapter->flags &IXGBE_FLAG_FDIR_HASH_CAPABLE ) { +while (unlikely (txq >= dev->real_num_tx_queues)) + txq -= dev->real_num_tx_queues; +return txq; + } + +return toeplitz_select_queue (dev, skb); } netdev_tx_t ixgbe_xmit_frame_ring(struct sk_buff *skb,
RFC PATCH 3/3 igb: example of how to update igb to make use of in-kernel Toeplitz hashing
In reply to Alexander DuyckThis change allows igb to make use of the in-kernel Toeplitz hashing so that RX and TX hash queues can be matched up.
---
drivers/net/igb/igb_main.c | 22 ++++++++++------------ 1 files changed, 10 insertions(+), 12 deletions(-)
drivers/net/igb/igb_main.c +10 -12
@@ -45,6 +45,7 @@#include <linux/interrupt.h> #include <linux/if_ether.h> #include <linux/aer.h> +#include <linux/toeplitz.h> #ifdef CONFIG_IGB_DCA #include <linux/dca.h> #endif
@@ -1691,6 +1692,7 @@ static const struct net_device_ops igb_netdev_ops = { .ndo_open = igb_open, .ndo_stop = igb_close, .ndo_start_xmit = igb_xmit_frame_adv, + .ndo_select_queue = toeplitz_select_queue, .ndo_get_stats64 = igb_get_stats64, .ndo_set_rx_mode = igb_set_rx_mode, .ndo_set_multicast_list = igb_set_rx_mode,
@@ -2660,19 +2662,14 @@ static void igb_setup_mrqc(struct igb_adapter *adapter)u32 dword;u8 bytes[4 ]; } reta; -static const u8 rsshash[40 ] = { -0x6d ,0x5a ,0x56 ,0xda ,0x25 ,0x5b ,0x0e ,0xc2 ,0x41 ,0x67 , -0x25 ,0x3d ,0x43 ,0xa3 ,0x8f ,0xb0 ,0xd0 ,0xca ,0x2b ,0xcb , -0xae ,0x7b ,0x30 ,0xb4 ,0x77 ,0xcb ,0x2d ,0xa3 ,0x80 ,0x30 , -0xf2 ,0x0c ,0x6a ,0x42 ,0xb7 ,0x3b ,0xbe ,0xac ,0x01 ,0xfa };/* Fill out hash function seeds */ for (j =0 ; j <10 ; j++) { -u32 rsskey = rsshash[(j *4 )]; - rsskey |= rsshash[(j *4 ) +1 ] <<8 ; - rsskey |= rsshash[(j *4 ) +2 ] <<16 ; - rsskey |= rsshash[(j *4 ) +3 ] <<24 ; -array_wr32 (E1000_RSSRK (0 ), j, rsskey); +u32 toeplitz_key = (u32 )toeplitz_get_key_byte ((4 * j)); + toeplitz_key |= (u32 )toeplitz_get_key_byte ((4 * j) +1 ) <<8 ; + toeplitz_key |= (u32 )toeplitz_get_key_byte ((4 * j) +2 ) <<16 ; + toeplitz_key |= (u32 )toeplitz_get_key_byte ((4 * j) +3 ) <<24 ; +array_wr32 (E1000_RSSRK (0 ), j, toeplitz_key); } num_rx_queues = adapter->rss_queues;
@@ -2700,8 +2697,9 @@ static void igb_setup_mrqc(struct igb_adapter *adapter) shift =6 ; } -for (j =0 ; j < (32 *4 ); j++) { - reta.bytes[j &3 ] = (j % num_rx_queues) << shift; +for (j =0 ; j <128 ; j++) { +u32 entry = ((j * num_rx_queues) &0xFF80 ) >>7 ; + reta.bytes[j &3 ] = entry << shift;if (shift2) reta.bytes[j &3 ] |= num_rx_queues << shift2;if ((j &3 ) ==3 )
David Miller
maintainerRe: [RFC PATCH 3/3] igb: example of how to update igb to make use of in-kernel Toeplitz hashing
From: Alexander Duyck <[email protected]>
Date: Fri, 17 Dec 2010 17:00:48 -0800
drivers/net/igb/igb_main.c static const struct net_device_ops igb_netdev_ops = { · line 1698
Quoted 8 lines
drivers/net/igb/igb_main.c +1
-0@@ -1691,6 +1692,7 @@ static const struct net_device_ops igb_netdev_ops = { .ndo_open = igb_open, .ndo_stop = igb_close, .ndo_start_xmit = igb_xmit_frame_adv, + .ndo_select_queue = toeplitz_select_queue, .ndo_get_stats64 = igb_get_stats64, .ndo_set_rx_mode = igb_set_rx_mode, .ndo_set_multicast_list = igb_set_rx_mode,
Adding a NETIF_F_TX_TOEPLITZ flag that skb_tx_hash() keys off of would be a lot simpler.
We want less overriding of ->ndo_select_queue(), not more, and this case is definitely gratuitous.
Re: [RFC PATCH 3/3] igb: example of how to update igb to make use of in-kernel Toeplitz hashing
Quoted 14 lines · David Miller
From: Alexander Duyck <[email protected]>
Date: Fri, 17 Dec 2010 17:00:48 -0800drivers/net/igb/igb_main.c static const struct net_device_ops igb_netdev_ops = { · line 1698
Quoted 8 lines
drivers/net/igb/igb_main.c +1
-0@@ -1691,6 +1692,7 @@ static const struct net_device_ops igb_netdev_ops = { .ndo_open = igb_open, .ndo_stop = igb_close, .ndo_start_xmit = igb_xmit_frame_adv, + .ndo_select_queue = toeplitz_select_queue, .ndo_get_stats64 = igb_get_stats64, .ndo_set_rx_mode = igb_set_rx_mode, .ndo_set_multicast_list = igb_set_rx_mode,Adding a
NETIF_F_TX_TOEPLITZflag thatskb_tx_hash()keys off of would be a lot simpler
Thats probably true. I hadn't put much thought into it at the time.
Quoted 2 lines
We want less overriding of ->ndo_select_queue(), not more, and this case is definitely gratuitous.
I kind of figured that was the approach was flawed. As I said in the cover page, this is a somewhat hastily thrown together set of patches to demonstrate a proof of concept. To me this appeared to be the quickest way to come up with the means to alter the queue selection. The main piece I am interested in is any input on the first patch that added the Toeplitz hash functionality. Specifically would a 16 bit key/hash work for queue selection or would there be cases where we need a 32 bit key/hash result?
Thanks,
Alex
David Miller
maintainerRe: [RFC PATCH 3/3] igb: example of how to update igb to make use of in-kernel Toeplitz hashing
From: Alexander Duyck <[email protected]>
Date: Fri, 17 Dec 2010 22:53:24 -0800
Quoted 2 lines
Specifically would a 16 bit key/hash work for queue selection or would there be cases where we need a 32 bit key/hash result?
Currently for TX 16-bit ought to be enough.
I'm not sure why this would be needed. What is the a advantage in making the TX and RX queues match?
Quoted 44 lines · Alexander Duyck
This patch series is meant to be a proof of concept for simplifying the cost of Toeplitz hashing by reducing the complexity of the key to a 16 bit repeating value. The resultant advantages are that the hash computation performance is significantly increased, and that the resultant hash is the same for flows in either direction.
The idea for this occurred to me while working on the ATR hashing algorithms and improving their performance. ATR implements a 32 bit repeating key which results in us being able to XOR everything down to a 32 bit value. By using a 16 bit key we are able to cut down the 12 to 36 byte input value to only 2 bytes via XOR operations. This reduces the resultant hash to 16 bits, however since queue selection only requires 7 bits for RSS that still leaves us with a large enough resultant key.
I'm currently not planning to do any more work on this in the near future as I have several other projects in which I am currently engaged. However I just wanted to put this code out there in case anyone had a use for it.
Thanks,
Alex
---
Alexander Duyck (3):
igb: example of how to update igb to make use of in-kernel Toeplitz hashing
ixgbe: example of how to update ixgbe to make use of in-kernel Toeplitz hash
net: add simplified 16 bit Toeplitz hash function for transmit side hashingdrivers/net/igb/igb_main.c | 22 ++++------
drivers/net/ixgbe/ixgbe_main.c| 47 ++++++++++++---------include/linux/netdevice.h| 2 +
include/linux/toeplitz.h | 89 ++++++++++++++++++++++++++++++++++++++++net/core/dev.c| 68 +++++++++++++++++++++++++++++++5 files changed, 195 insertions(+), 33 deletions(-)create mode 100644
include/linux/toeplitz.h--
--
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 3 lines · Tom Herbert
I'm not sure why this would be needed. What is the a advantage in making the TX and RX queues match?
If the application is affinitized and you are working with RX/TX pairs as we have in ixgbe then you can be certain that your buffers are staying in the same NUMA node or CPU as the application. Having them on different NUMA nodes can hurt performance for either TX or RX.
The other advantage was that I didn't have to bother with trying to reorder the source and destination values when computing an RX hash or a TX hash. I can just call the same function and regardless of direction I would get the same hash. That way I could be guaranteed in a routing test that if I was using the RX hash to determine the TX queue that the queue number shouldn't change.
I believe the same thing is being accomplished in RPS/TPS via a test for the values and swapping them if source is greater than destination.
Thanks,
Alex
David Miller
maintainerFrom: Tom Herbert <[email protected]>
Date: Mon, 3 Jan 2011 10:47:20 -0800
Quoted 2 lines
I'm not sure why this would be needed. What is the a advantage in making the TX and RX queues match?
That's how their hardware based RFS essentially works.
Instead of watching for "I/O system calls" like we do in software, the chip watches for which TX queue a flow ends up on and matches things up on the receive side with the same numbered RX queue to match.
Quoted 11 lines · David Miller
From: Tom Herbert <[email protected]>
Date: Mon, 3 Jan 2011 10:47:20 -0800Quoted 2 lines
I'm not sure why this would be needed. What is the a advantage in making the TX and RX queues match?
That's how their hardware based RFS essentially works.
Instead of watching for "I/O system calls" like we do in software, the chip watches for which TX queue a flow ends up on and matches things up on the receive side with the same numbered RX queue to match.
ixgbe also implements IRQ affinity setting (or rather hinting) and TX queue selection by CPU, the inverse of IRQ affinity setting. Together with the hardware/firmware Flow Director feature, this should indeed result in hardware RFS. (However, irqbalanced does not yet follow the affinity hints AFAIK, so this requires some manual intervention. Maybe the OOT driver is different?)
The proposed change to make TX queue selection hash-based seems to be a step backwards.
Ben.
Signature · 3 lines
Ben Hutchings, Senior Software Engineer, Solarflare Communications Not speaking for my employer; that's the marketing department's job. They asked us to note that Solarflare product names are trademarked.
Quoted 20 lines · Ben Hutchings
Quoted 11 lines · David Miller
From: Tom Herbert<[email protected]>
Date: Mon, 3 Jan 2011 10:47:20 -0800Quoted 2 lines
I'm not sure why this would be needed. What is the a advantage in making the TX and RX queues match?
That's how their hardware based RFS essentially works.
Instead of watching for "I/O system calls" like we do in software, the chip watches for which TX queue a flow ends up on and matches things up on the receive side with the same numbered RX queue to match.
ixgbe also implements IRQ affinity setting (or rather hinting) and TX queue selection by CPU, the inverse of IRQ affinity setting. Together with the hardware/firmware Flow Director feature, this should indeed result in hardware RFS. (However, irqbalanced does not yet follow the affinity hints AFAIK, so this requires some manual intervention. Maybe the OOT driver is different?)
Quoted 5 lines
The proposed change to make TX queue selection hash-based seems to be a step backwards.
Ben.
Actually this code would only be applied in the case where Flow Director didn't apply such as non-TCP frames. It would essentially guarantee that we end up with TX/RX on the same CPU for all cases instead of just when Flow Director matches a given flow.
The general idea is to at least keep the traffic local to one TX/RX queue pair so that if we cannot match the queue pair to the application, perhaps the application can be affinitized to match up with the queue pair. Otherwise we end up with traffic getting routed to one TX queue on one CPU, and the RX being routed to another queue on perhaps a different CPU and it becomes quite difficult to match up the queues and the applications.
Since the approach is based on Toeplitz it can be applied to all hardware capable of generating a Toeplitz based hash and as a result it would likely also work in a much more vendor neutral kind of way than Flow Director currently does.
Thanks,
Alex
David Miller
maintainerFrom: Alexander Duyck <[email protected]>
Date: Mon, 03 Jan 2011 11:52:00 -0800
Quoted 4 lines
Since the approach is based on Toeplitz it can be applied to all hardware capable of generating a Toeplitz based hash and as a result it would likely also work in a much more vendor neutral kind of way than Flow Director currently does.
Immediately this excludes NIU, for one, since it does not use Topelitz.
Quoted 24 lines · Alexander Duyck
Quoted 23 lines · Ben Hutchings
Quoted 11 lines · David Miller
From: Tom Herbert<[email protected]>
Date: Mon, 3 Jan 2011 10:47:20 -0800Quoted 2 lines
I'm not sure why this would be needed. What is the a advantage in making the TX and RX queues match?
That's how their hardware based RFS essentially works.
Instead of watching for "I/O system calls" like we do in software, the chip watches for which TX queue a flow ends up on and matches things up on the receive side with the same numbered RX queue to match.
ixgbe also implements IRQ affinity setting (or rather hinting) and TX queue selection by CPU, the inverse of IRQ affinity setting. Together with the hardware/firmware Flow Director feature, this should indeed result in hardware RFS. (However, irqbalanced does not yet follow the affinity hints AFAIK, so this requires some manual intervention. Maybe the OOT driver is different?)
The proposed change to make TX queue selection hash-based seems to be a step backwards.
Quoted 7 lines
Quoted 2 lines
Ben.
Actually this code would only be applied in the case where Flow Director didn't apply such as non-TCP frames. It would essentially guarantee that we end up with TX/RX on the same CPU for all cases instead of just when Flow Director matches a given flow.
The code you posted doesn't seem to implement that, though.
Quoted 7 lines
The general idea is to at least keep the traffic local to one TX/RX queue pair so that if we cannot match the queue pair to the application, perhaps the application can be affinitized to match up with the queue pair. Otherwise we end up with traffic getting routed to one TX queue on one CPU, and the RX being routed to another queue on perhaps a different CPU and it becomes quite difficult to match up the queues and the applications.
Right. That certainly seems like a Good Thing, though I believe it can be implemented generically by recording the RX queue number on the socket:
http://article.gmane.org/gmane.linux.network/158477
Quoted 4 lines
Since the approach is based on Toeplitz it can be applied to all hardware capable of generating a Toeplitz based hash and as a result it would likely also work in a much more vendor neutral kind of way than Flow Director currently does.
Which I appreciate, but I'm not convinced that weakening Toeplitz is a good way to do it.
I understand that Robert Watson (FreeBSD hacker) has been doing some research on the security and performance implications of flow hashing algorithms, though I haven't seen any results of that yet.
Ben.
Signature · 3 lines
Ben Hutchings, Senior Software Engineer, Solarflare Communications Not speaking for my employer; that's the marketing department's job. They asked us to note that Solarflare product names are trademarked.
Quoted 28 lines · Ben Hutchings
Quoted 27 lines · Alexander Duyck
Quoted 25 lines · Ben Hutchings
Quoted 11 lines · David Miller
From: Tom Herbert<[email protected]>
Date: Mon, 3 Jan 2011 10:47:20 -0800Quoted 2 lines
I'm not sure why this would be needed. What is the a advantage in making the TX and RX queues match?
That's how their hardware based RFS essentially works.
Instead of watching for "I/O system calls" like we do in software, the chip watches for which TX queue a flow ends up on and matches things up on the receive side with the same numbered RX queue to match.
ixgbe also implements IRQ affinity setting (or rather hinting) and TX queue selection by CPU, the inverse of IRQ affinity setting. Together with the hardware/firmware Flow Director feature, this should indeed result in hardware RFS. (However, irqbalanced does not yet follow the affinity hints AFAIK, so this requires some manual intervention. Maybe the OOT driver is different?)
The proposed change to make TX queue selection hash-based seems to be a step backwards.
Ben.
Quoted 6 lines
Quoted 4 lines
Actually this code would only be applied in the case where Flow Director didn't apply such as non-TCP frames. It would essentially guarantee that we end up with TX/RX on the same CPU for all cases instead of just when Flow Director matches a given flow.
The code you posted doesn't seem to implement that, though.
Actually it does, it only takes effect in the case that flow director isn't enabled. I just implemented it as a ndo_select_queue and then in the case of the igb example I applied it directly, and in the case of the ixgbe example I just added it to the end of the ndo_select_queue function that it already had.
Quoted 9 lines
Quoted 8 lines
The general idea is to at least keep the traffic local to one TX/RX queue pair so that if we cannot match the queue pair to the application, perhaps the application can be affinitized to match up with the queue pair. Otherwise we end up with traffic getting routed to one TX queue on one CPU, and the RX being routed to another queue on perhaps a different CPU and it becomes quite difficult to match up the queues and the applications.
Quoted 5 lines
Right. That certainly seems like a Good Thing, though I believe it can be implemented generically by recording the RX queue number on the socket:
That was one of the reasons why I put this chunk of code out there as an RFC as I didn't see anywhere where it really fit in. I wasn't sure if anyone had a use for it or not, but I didn't see much point in keeping it to myself and so I submitted as an RFC to see if anyone had any interest.
Quoted 5 lines
Quoted 4 lines
Since the approach is based on Toeplitz it can be applied to all hardware capable of generating a Toeplitz based hash and as a result it would likely also work in a much more vendor neutral kind of way than Flow Director currently does.
Quoted 9 lines
Which I appreciate, but I'm not convinced that weakening Toeplitz is a good way to do it.
I understand that Robert Watson (FreeBSD hacker) has been doing some research on the security and performance implications of flow hashing algorithms, though I haven't seen any results of that yet.
Ben.
I wasn't really sure about it either, but from what I can tell Toeplitz is pretty weak in the first place, especially if using a static key, but really hard to do efficiently in software with a full 40 byte key.
The advantages of the 16 bit key were that I could do the hash computation with little CPU overhead and then I also was able to generate the symmetric hash result so I didn't have to mess with source and destination field ordering to generate the TX hash. Since most of the hardware I am familiar with doesn't support more than 128 queues anyway the 16 bit hash input and result generated via this approach should be more than enough to handle the queue selection and distribution needs of the hardware which was my only real concern.
Thanks for the input,
Alex
Quoted 8 lines
Quoted 7 lines
The general idea is to at least keep the traffic local to one TX/RX queue pair so that if we cannot match the queue pair to the application, perhaps the application can be affinitized to match up with the queue pair. Otherwise we end up with traffic getting routed to one TX queue on one CPU, and the RX being routed to another queue on perhaps a different CPU and it becomes quite difficult to match up the queues and the applications.
Quoted 6 lines
Right. That certainly seems like a Good Thing, though I believe it can be implemented generically by recording the RX queue number on the socket:
I still don't see the value in doing this RX/TX queue pairing (unless you're considering the possibility of explicitly binding sockets to queue pairs). XPS should be sufficient mechanism to get affinity on sending side. Also, don't know how the queue paring model will be maintained when using priority queues on transmit-- transmit is likely to be asymmetric to receive side. The ability to seamlessly decouple transmit queues and receive queues seems like a nice property.
Quoted 5 lines
Quoted 4 lines
Since the approach is based on Toeplitz it can be applied to all hardware capable of generating a Toeplitz based hash and as a result it would likely also work in a much more vendor neutral kind of way than Flow Director currently does.
The device hash should already be available in sk_rxhash, so maybe that could be used for this purpose. I think it is a good property to keeping treat the device hashes as opaque values, any reasonable 32-bit 4-tuple hash should work equally well in the stack.
Quoted 12 lines · Tom Herbert
Quoted 12 lines
Quoted 7 lines
The general idea is to at least keep the traffic local to one TX/RX queue pair so that if we cannot match the queue pair to the application, perhaps the application can be affinitized to match up with the queue pair. Otherwise we end up with traffic getting routed to one TX queue on one CPU, and the RX being routed to another queue on perhaps a different CPU and it becomes quite difficult to match up the queues and the applications.
Right. That certainly seems like a Good Thing, though I believe it can be implemented generically by recording the RX queue number on the socket:
Quoted 5 lines
Quoted 2 lines
I still don't see the value in doing this RX/TX queue pairing (unless you're considering the possibility of explicitly binding sockets to queue pairs).
Sure, the real value is in getting TX completions to line up with TX initiation and queue pairing is not a reliable way to do that.
Quoted 2 lines
XPS should be sufficient mechanism to get affinity on sending side.
[...]
At least if it's configured properly... or if this is automated using my irq_cpu_rmap.
Ben.
Signature · 3 lines
Ben Hutchings, Senior Software Engineer, Solarflare Communications Not speaking for my employer; that's the marketing department's job. They asked us to note that Solarflare product names are trademarked.