[RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[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 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

[Alexander Duyck]

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.

Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>
---

 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

diff --git a/include/linux/netdevice.h b/include/linux/netdevice.h
index cc916c5..01b5989 100644
--- a/include/linux/netdevice.h
+++ b/include/linux/netdevice.h
@@ -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 */
diff --git a/include/linux/toeplitz.h b/include/linux/toeplitz.h
new file mode 100644
index 0000000..2360cf4
--- /dev/null
+++ b/include/linux/toeplitz.h
@@ -0,0 +1,89 @@
+/*
+ * Copyright (c) 2010, Intel Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU General Public License,
+ * version 2, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place - Suite 330, Boston, MA 02111-1307 USA.
+ *
+ * Author: Alexander Duyck <alexander.h.duyck@intel.com>
+ */
+
+#ifndef _LINUX_TOEPLITZ_H
+#define _LINUX_TOEPLITZ_H
+
+/*
+ * The code below implements a simplified version of toeplitz hashing.  To
+ * simplify it I have reduced the key size from 40 bytes to a repeating
+ * pattern of 2 bytes.  Doing this does two things.  First it reduces the
+ * computation complexity significantly since I can XOR together all of the
+ * input into a single 16 bit value when computing the hash.  Secondly it
+ * allows both directions of a flow to generate the same hash since now we
+ * are looking at the XORed result of the source against the destination as
+ * input.
+ */
+#define TOEPLITZ_KEY_0 0xE3
+#define TOEPLITZ_KEY_1 0xAF
+
+static inline u8 toeplitz_get_key_byte(int byte_number)
+{
+	if (byte_number & 0x1)
+		return TOEPLITZ_KEY_1;
+	else
+		return TOEPLITZ_KEY_0;
+}
+
+#define TOEPLITZ_KEY (((u64)(TOEPLITZ_KEY_1) << 32) | \
+		      ((u64)(TOEPLITZ_KEY_0) << 24) | \
+		      ((u64)(TOEPLITZ_KEY_1) << 16) | \
+		      ((u64)(TOEPLITZ_KEY_0) <<  8) | \
+		      ((u64)(TOEPLITZ_KEY_1)))
+
+#define TOEPLITZ_PRECOMPUTED_VALUE(_input) ( \
+	((((~_input >>  0) & 0x1) - 1) & ((TOEPLITZ_KEY >> 1) & 0xFFFFFFFF)) ^ \
+	((((~_input >>  1) & 0x1) - 1) & ((TOEPLITZ_KEY >> 2) & 0xFFFFFFFF)) ^ \
+	((((~_input >>  2) & 0x1) - 1) & ((TOEPLITZ_KEY >> 3) & 0xFFFFFFFF)) ^ \
+	((((~_input >>  3) & 0x1) - 1) & ((TOEPLITZ_KEY >> 4) & 0xFFFFFFFF)))
+
+static const u32 toeplitz_input_values[16] = {
+	TOEPLITZ_PRECOMPUTED_VALUE(0x0),
+	TOEPLITZ_PRECOMPUTED_VALUE(0x1),
+	TOEPLITZ_PRECOMPUTED_VALUE(0x2),
+	TOEPLITZ_PRECOMPUTED_VALUE(0x3),
+	TOEPLITZ_PRECOMPUTED_VALUE(0x4),
+	TOEPLITZ_PRECOMPUTED_VALUE(0x5),
+	TOEPLITZ_PRECOMPUTED_VALUE(0x6),
+	TOEPLITZ_PRECOMPUTED_VALUE(0x7),
+	TOEPLITZ_PRECOMPUTED_VALUE(0x8),
+	TOEPLITZ_PRECOMPUTED_VALUE(0x9),
+	TOEPLITZ_PRECOMPUTED_VALUE(0xA),
+	TOEPLITZ_PRECOMPUTED_VALUE(0xB),
+	TOEPLITZ_PRECOMPUTED_VALUE(0xC),
+	TOEPLITZ_PRECOMPUTED_VALUE(0xD),
+	TOEPLITZ_PRECOMPUTED_VALUE(0xE),
+	TOEPLITZ_PRECOMPUTED_VALUE(0xF)
+};
+
+static inline u16 toeplitz_compute_hash(u32 input)
+{
+	u16 result = 0;
+
+	input ^= input >> 16;
+
+	result ^= toeplitz_input_values[(input & 0x000F)];
+	result ^= toeplitz_input_values[(input & 0x00F0) >>  4] >>  4;
+	result ^= toeplitz_input_values[(input & 0x0F00) >>  8] >>  8;
+	result ^= toeplitz_input_values[(input & 0xF000) >> 12] >> 12;
+
+	return result;
+}
+
+#endif /* _LINUX_TOEPLITZ_H */
diff --git a/net/core/dev.c b/net/core/dev.c
index 92d414a..8b4e4d3 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -132,6 +132,7 @@
 #include <trace/events/skb.h>
 #include <linux/pci.h>
 #include <linux/inetdevice.h>
+#include <linux/toeplitz.h>
 
 #include "net-sysfs.h"
 
@@ -2170,6 +2171,73 @@ u16 __skb_tx_hash(const struct net_device *dev, const struct sk_buff *skb,
 }
 EXPORT_SYMBOL(__skb_tx_hash);
 
+static inline u16 toeplitz_hash_skb(const struct net_device *dev,
+				    const struct sk_buff *skb)
+{
+	union {
+		unsigned char *network;
+		struct iphdr *ipv4;
+		struct ipv6hdr *ipv6;
+	} hdr;
+	__be32 input;
+	u16 hash;
+	__be16 protocol = vlan_get_protocol(skb);
+
+	/* snag network header to get L4 type and address */
+	hdr.network = skb_network_header(skb);
+
+	/* Currently only IPv4/IPv6 with TCP is supported */
+	switch (protocol) {
+	case __constant_htons(ETH_P_IP):
+		input = hdr.ipv4->saddr ^ hdr.ipv4->daddr;
+		if (hdr.ipv4->protocol == IPPROTO_TCP)
+			input ^= *(__be32 *)tcp_hdr(skb);
+		break;
+	case __constant_htons(ETH_P_IPV6):
+		input = hdr.ipv6->saddr.s6_addr32[0] ^
+			hdr.ipv6->saddr.s6_addr32[1] ^
+			hdr.ipv6->saddr.s6_addr32[2] ^
+			hdr.ipv6->saddr.s6_addr32[3] ^
+			hdr.ipv6->daddr.s6_addr32[0] ^
+			hdr.ipv6->daddr.s6_addr32[1] ^
+			hdr.ipv6->daddr.s6_addr32[2] ^
+			hdr.ipv6->daddr.s6_addr32[3];
+		if (hdr.ipv6->nexthdr == IPPROTO_TCP)
+			input ^= *(__be32 *)tcp_hdr(skb);
+		break;
+	default:
+		return 0;
+	}
+
+	hash = toeplitz_compute_hash(ntohl(input)) & 0x7F;
+
+	return (dev->real_num_tx_queues * hash) >> 7;
+}
+
+u16 toeplitz_select_queue(struct net_device *dev, struct sk_buff *skb)
+{
+	struct sock *sk = skb->sk;
+	int queue_index = sk_tx_queue_get(sk);
+
+	if (queue_index >= 0 && queue_index < dev->real_num_tx_queues)
+		return queue_index;
+
+	queue_index = 0;
+
+	if (dev->real_num_tx_queues > 1)
+		queue_index = toeplitz_hash_skb(dev, skb);
+
+	if (sk) {
+		struct dst_entry *dst =
+			rcu_dereference_check(sk->sk_dst_cache, 1);
+		if (dst && skb_dst(skb) == dst)
+			sk_tx_queue_set(sk, queue_index);
+	}
+
+	return queue_index;
+}
+EXPORT_SYMBOL(toeplitz_select_queue);
+
 static inline u16 dev_cap_txqueue(struct net_device *dev, u16 queue_index)
 {
 	if (unlikely(queue_index >= dev->real_num_tx_queues)) {

[RFC PATCH 2/3] ixgbe: example of how to update ixgbe to make use of in-kernel Toeplitz hash

[Alexander Duyck]

This change allows ixgbe to make use of the in-kernel Toeplitz hashing so
that RX and TX hash queues can be matched up.

Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>
---

 drivers/net/ixgbe/ixgbe_main.c |   47 ++++++++++++++++++++++------------------
 1 files changed, 26 insertions(+), 21 deletions(-)

diff --git a/drivers/net/ixgbe/ixgbe_main.c b/drivers/net/ixgbe/ixgbe_main.c
index a060610..0d0fcde 100644
--- a/drivers/net/ixgbe/ixgbe_main.c
+++ b/drivers/net/ixgbe/ixgbe_main.c
@@ -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

[Alexander Duyck]

This change allows igb to make use of the in-kernel Toeplitz hashing so
that RX and TX hash queues can be matched up.

Signed-off-by: Alexander Duyck <alexander.h.duyck@intel.com>
---

 drivers/net/igb/igb_main.c |   22 ++++++++++------------
 1 files changed, 10 insertions(+), 12 deletions(-)

diff --git a/drivers/net/igb/igb_main.c b/drivers/net/igb/igb_main.c
index 72a2fad..9e6a437 100644
--- a/drivers/net/igb/igb_main.c
+++ b/drivers/net/igb/igb_main.c
@@ -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)

Re: [RFC PATCH 3/3] igb: example of how to update igb to make use of in-kernel Toeplitz hashing

[David Miller]

From: Alexander Duyck <alexander.h.duyck@intel.com>
Date: Fri, 17 Dec 2010 17:00:48 -0800

> @@ -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

[Alexander Duyck]

On Fri, Dec 17, 2010 at 9:09 PM, David Miller <davem@davemloft.net> wrote:
> From: Alexander Duyck <alexander.h.duyck@intel.com>
> Date: Fri, 17 Dec 2010 17:00:48 -0800
>
>> @@ -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

Thats probably true.  I hadn't put much thought into it at the time.

> 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

Re: [RFC PATCH 3/3] igb: example of how to update igb to make use of in-kernel Toeplitz hashing

[David Miller]

From: Alexander Duyck <alexander.duyck@gmail.com>
Date: Fri, 17 Dec 2010 22:53:24 -0800

> 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.

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[Tom Herbert]

I'm not sure why this would be needed.  What is the a advantage in
making the TX and RX queues match?

On Fri, Dec 17, 2010 at 5:00 PM, Alexander Duyck
<alexander.h.duyck@intel.com> wrote:
> 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
>
> --
> --
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[Alexander Duyck]

On 1/3/2011 10:47 AM, Tom Herbert wrote:
> 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

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[David Miller]

From: Tom Herbert <therbert@google.com>
Date: Mon, 3 Jan 2011 10:47:20 -0800

> 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.

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[Ben Hutchings]

On Mon, 2011-01-03 at 11:02 -0800, David Miller wrote:
> From: Tom Herbert <therbert@google.com>
> Date: Mon, 3 Jan 2011 10:47:20 -0800
> 
> > 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.

-- 
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.

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[Alexander Duyck]

On 1/3/2011 11:30 AM, Ben Hutchings wrote:
> On Mon, 2011-01-03 at 11:02 -0800, David Miller wrote:
>> From: Tom Herbert<therbert@google.com>
>> Date: Mon, 3 Jan 2011 10:47:20 -0800
>>
>>> 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.
>

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

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[David Miller]

From: Alexander Duyck <alexander.h.duyck@intel.com>
Date: Mon, 03 Jan 2011 11:52:00 -0800

> 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.

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[Ben Hutchings]

On Mon, 2011-01-03 at 11:52 -0800, Alexander Duyck wrote:
> On 1/3/2011 11:30 AM, Ben Hutchings wrote:
> > On Mon, 2011-01-03 at 11:02 -0800, David Miller wrote:
> >> From: Tom Herbert<therbert@google.com>
> >> Date: Mon, 3 Jan 2011 10:47:20 -0800
> >>
> >>> 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.
> >
> 
> 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.

> 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

> 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.

-- 
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.

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[Alexander Duyck]

On 1/3/2011 12:15 PM, Ben Hutchings wrote:
> On Mon, 2011-01-03 at 11:52 -0800, Alexander Duyck wrote:
>> On 1/3/2011 11:30 AM, Ben Hutchings wrote:
>>> On Mon, 2011-01-03 at 11:02 -0800, David Miller wrote:
>>>> From: Tom Herbert<therbert@google.com>
>>>> Date: Mon, 3 Jan 2011 10:47:20 -0800
>>>>
>>>>> 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.
>>>
>>
>> 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.

>
>> 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

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.

>> 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.
>

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

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[Tom Herbert]

>> 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
>
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.

>> 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.

Re: [RFC PATCH 0/3] Simplified 16 bit Toeplitz hash algorithm

[Ben Hutchings]

On Mon, 2011-01-03 at 19:25 -0800, Tom Herbert wrote:
> >> 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
> >
> 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.

> 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.

-- 
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.