[PATCH] Make simple TX hash little endian safe.

[PATCH] Make simple TX hash little endian safe.

[Andi Kleen]

From: Andi Kleen <andi@basil.nowhere.org>

Currently it will not use the lower
bits at all on big endian system, mapping e.g. all connections to a single
queue on a local network which only differs in the low bits.

Also fold the upper 16 bits always in the lower 16bits.

Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 net/core/dev.c |    7 +++++--
 1 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/net/core/dev.c b/net/core/dev.c
index 2eed17b..c35fefc 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -1694,8 +1694,11 @@ static u16 simple_tx_hash(struct net_device *dev, struct sk_buff *skb)
 	ports = (u32 *) (skb_network_header(skb) + (ihl * 4));
 
 	hash = 0;
-	while (alen--)
-		hash ^= *addr++;
+	while (alen--) {
+		hash ^= ntohl(*addr); 
+		addr++;
+	}
+	hash ^= hash >> 16; /* More folding needed? */
 
 	switch (ip_proto) {
 	case IPPROTO_TCP:
-- 
1.5.6

[PATCH] Add a statistics counter for tx hash miss

[Andi Kleen]

From: Andi Kleen <andi@basil.nowhere.org>

Add a counter for the case when the TX hash function doesn't work.

Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 include/linux/snmp.h |    1 +
 net/core/dev.c       |    3 +++
 net/ipv4/proc.c      |    1 +
 3 files changed, 5 insertions(+), 0 deletions(-)

diff --git a/include/linux/snmp.h b/include/linux/snmp.h
index 5df62ef..c4d69b7 100644
--- a/include/linux/snmp.h
+++ b/include/linux/snmp.h
@@ -214,6 +214,7 @@ enum
 	LINUX_MIB_TCPDSACKIGNOREDOLD,		/* TCPSACKIgnoredOld */
 	LINUX_MIB_TCPDSACKIGNOREDNOUNDO,	/* TCPSACKIgnoredNoUndo */
 	LINUX_MIB_TCPSPURIOUSRTOS,		/* TCPSpuriousRTOs */
+	LINUX_MIB_TXHASHMISS,			/* TxHashMiss */
 	__LINUX_MIB_MAX
 };
 
diff --git a/net/core/dev.c b/net/core/dev.c
index c35fefc..cc45878 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -124,6 +124,7 @@
 #include <linux/ip.h>
 #include <linux/ipv6.h>
 #include <linux/in.h>
+#include <net/ip.h>
 
 #include "net-sysfs.h"
 
@@ -1688,6 +1689,7 @@ static u16 simple_tx_hash(struct net_device *dev, struct sk_buff *skb)
 		alen = 8;
 		break;
 	default:
+		NET_INC_STATS_BH(dev_net(dev), LINUX_MIB_TXHASHMISS);
 		return 0;
 	}
 
@@ -1712,6 +1714,7 @@ static u16 simple_tx_hash(struct net_device *dev, struct sk_buff *skb)
 		break;
 
 	default:
+		NET_INC_STATS_BH(dev_net(dev), LINUX_MIB_TXHASHMISS);
 		break;
 	}
 
diff --git a/net/ipv4/proc.c b/net/ipv4/proc.c
index 834356e..f621b87 100644
--- a/net/ipv4/proc.c
+++ b/net/ipv4/proc.c
@@ -232,6 +232,7 @@ static const struct snmp_mib snmp4_net_list[] = {
 	SNMP_MIB_ITEM("TCPDSACKIgnoredOld", LINUX_MIB_TCPDSACKIGNOREDOLD),
 	SNMP_MIB_ITEM("TCPDSACKIgnoredNoUndo", LINUX_MIB_TCPDSACKIGNOREDNOUNDO),
 	SNMP_MIB_ITEM("TCPSpuriousRTOs", LINUX_MIB_TCPSPURIOUSRTOS),
+	SNMP_MIB_ITEM("TxHashMiss", LINUX_MIB_TXHASHMISS),
 	SNMP_MIB_SENTINEL
 };
 
-- 
1.5.6

Re: [PATCH] Add a statistics counter for tx hash miss

[David Miller]

From: Andi Kleen <andi@firstfloor.org>
Date: Mon, 21 Jul 2008 10:48:08 +0200

> Add a counter for the case when the TX hash function doesn't work.
> 
> Signed-off-by: Andi Kleen <ak@linux.intel.com>

This is very much not an IPV4 protocol statistic.

I understand your desire to export this information, but
as easy as this method is it's not the right way.

Re: [PATCH] Add a statistics counter for tx hash miss

[Andi Kleen]

On Mon, Jul 21, 2008 at 09:33:30AM -0700, David Miller wrote:
> From: Andi Kleen <andi@firstfloor.org>
> Date: Mon, 21 Jul 2008 10:48:08 +0200
> 
> > Add a counter for the case when the TX hash function doesn't work.
> > 
> > Signed-off-by: Andi Kleen <ak@linux.intel.com>
> 
> This is very much not an IPV4 protocol statistic.
> 
> I understand your desire to export this information, but
> as easy as this method is it's not the right way.

It's IPv4 and IPv6 and netstat contains Ipv4 and ipv6 information
(e.g. all the TCP counters) and even some completely protocol independent 
counters like ArpFilter.

-Andi

Re: [PATCH] Add a statistics counter for tx hash miss

[David Miller]

From: Andi Kleen <andi@firstfloor.org>
Date: Mon, 21 Jul 2008 18:44:07 +0200

> On Mon, Jul 21, 2008 at 09:33:30AM -0700, David Miller wrote:
> > From: Andi Kleen <andi@firstfloor.org>
> > Date: Mon, 21 Jul 2008 10:48:08 +0200
> > 
> > > Add a counter for the case when the TX hash function doesn't work.
> > > 
> > > Signed-off-by: Andi Kleen <ak@linux.intel.com>
> > 
> > This is very much not an IPV4 protocol statistic.
> > 
> > I understand your desire to export this information, but
> > as easy as this method is it's not the right way.
> 
> It's IPv4 and IPv6 and netstat contains Ipv4 and ipv6 information
> (e.g. all the TCP counters) and even some completely protocol independent 
> counters like ArpFilter.

You're logging when we don't hit ipv4 or ipv6 :-)

Re: [PATCH] Make simple TX hash little endian safe.

[Jarek Poplawski]

On 21-07-2008 10:48, Andi Kleen wrote:
> From: Andi Kleen <andi@basil.nowhere.org>
> 
> Currently it will not use the lower
> bits at all on big endian system, mapping e.g. all connections to a single
> queue on a local network which only differs in the low bits.

It seems ports could be treated similarly, btw?

Jarek P.

> 
> Also fold the upper 16 bits always in the lower 16bits.
> 
> Signed-off-by: Andi Kleen <ak@linux.intel.com>
> ---
>  net/core/dev.c |    7 +++++--
>  1 files changed, 5 insertions(+), 2 deletions(-)
> 
> diff --git a/net/core/dev.c b/net/core/dev.c
> index 2eed17b..c35fefc 100644
> --- a/net/core/dev.c
> +++ b/net/core/dev.c
> @@ -1694,8 +1694,11 @@ static u16 simple_tx_hash(struct net_device *dev, struct sk_buff *skb)
>  	ports = (u32 *) (skb_network_header(skb) + (ihl * 4));
>  
>  	hash = 0;
> -	while (alen--)
> -		hash ^= *addr++;
> +	while (alen--) {
> +		hash ^= ntohl(*addr); 
> +		addr++;
> +	}
> +	hash ^= hash >> 16; /* More folding needed? */
>  
>  	switch (ip_proto) {
>  	case IPPROTO_TCP:

Re: [PATCH] Make simple TX hash little endian safe.

[Andi Kleen]

On Mon, Jul 21, 2008 at 12:32:15PM +0000, Jarek Poplawski wrote:
> On 21-07-2008 10:48, Andi Kleen wrote:
> > From: Andi Kleen <andi@basil.nowhere.org>
> > 
> > Currently it will not use the lower
> > bits at all on big endian system, mapping e.g. all connections to a single
> > queue on a local network which only differs in the low bits.
> 
> It seems ports could be treated similarly, btw?

Ports should be normally better distributed because they tend
to be more uniform than IP addresses due to the way they are
generated, so there will hopefully not be too many endian artifacts. 
But yes at least least folding them too might be a good idea.

-Andi

Re: [PATCH] Make simple TX hash little endian safe.

[David Miller]

From: Andi Kleen <andi@firstfloor.org>
Date: Mon, 21 Jul 2008 10:48:07 +0200

> Currently it will not use the lower
> bits at all on big endian system, mapping e.g. all connections to a single
> queue on a local network which only differs in the low bits.
> 
> Also fold the upper 16 bits always in the lower 16bits.
> 
> Signed-off-by: Andi Kleen <ak@linux.intel.com>

I plan to make this use jhash plus a reciprocol multiply
to fix the hash effectiveness as well as get rid of the
modulus and make the hash not attackable.

Something like the patch below.

Thanks.

diff --git a/net/core/dev.c b/net/core/dev.c
index 2eed17b..7e2d527 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -124,6 +124,8 @@
 #include <linux/ip.h>
 #include <linux/ipv6.h>
 #include <linux/in.h>
+#include <linux/jhash.h>
+#include <linux/random.h>
 
 #include "net-sysfs.h"
 
@@ -1668,34 +1670,37 @@ out_kfree_skb:
  *          --BLG
  */
 
+static u32 simple_tx_hashrnd;
+static int simple_tx_hashrnd_initialized = 0;
+
 static u16 simple_tx_hash(struct net_device *dev, struct sk_buff *skb)
 {
-	u32 *addr, *ports, hash, ihl;
+	u32 addr1, addr2, ports;
+	u32 hash, ihl;
 	u8 ip_proto;
-	int alen;
+
+	if (unlikely(!simple_tx_hashrnd_initialized)) {
+		get_random_bytes(&simple_tx_hashrnd, 4);
+		simple_tx_hashrnd_initialized = 1;
+	}
 
 	switch (skb->protocol) {
 	case __constant_htons(ETH_P_IP):
 		ip_proto = ip_hdr(skb)->protocol;
-		addr = &ip_hdr(skb)->saddr;
+		addr1 = ip_hdr(skb)->saddr;
+		addr2 = ip_hdr(skb)->daddr;
 		ihl = ip_hdr(skb)->ihl;
-		alen = 2;
 		break;
 	case __constant_htons(ETH_P_IPV6):
 		ip_proto = ipv6_hdr(skb)->nexthdr;
-		addr = &ipv6_hdr(skb)->saddr.s6_addr32[0];
+		addr1 = ipv6_hdr(skb)->saddr.s6_addr32[3];
+		addr2 = ipv6_hdr(skb)->daddr.s6_addr32[3];
 		ihl = (40 >> 2);
-		alen = 8;
 		break;
 	default:
 		return 0;
 	}
 
-	ports = (u32 *) (skb_network_header(skb) + (ihl * 4));
-
-	hash = 0;
-	while (alen--)
-		hash ^= *addr++;
 
 	switch (ip_proto) {
 	case IPPROTO_TCP:
@@ -1705,14 +1710,17 @@ static u16 simple_tx_hash(struct net_device *dev, struct sk_buff *skb)
 	case IPPROTO_AH:
 	case IPPROTO_SCTP:
 	case IPPROTO_UDPLITE:
-		hash ^= *ports;
+		ports = *((u32 *) (skb_network_header(skb) + (ihl * 4)));
 		break;
 
 	default:
+		ports = 0;
 		break;
 	}
 
-	return hash % dev->real_num_tx_queues;
+	hash = jhash_3words(addr1, addr2, ports, simple_tx_hashrnd);
+
+	return (u16) (((u64) hash * dev->real_num_tx_queues) >> 32);
 }
 
 static struct netdev_queue *dev_pick_tx(struct net_device *dev,

Re: [PATCH] Make simple TX hash little endian safe.

[Andi Kleen]

On Mon, Jul 21, 2008 at 09:44:33AM -0700, David Miller wrote:
> From: Andi Kleen <andi@firstfloor.org>
> Date: Mon, 21 Jul 2008 10:48:07 +0200
> 
> > Currently it will not use the lower
> > bits at all on big endian system, mapping e.g. all connections to a single
> > queue on a local network which only differs in the low bits.
> > 
> > Also fold the upper 16 bits always in the lower 16bits.
> > 
> > Signed-off-by: Andi Kleen <ak@linux.intel.com>
> 
> I plan to make this use jhash plus a reciprocol multiply
> to fix the hash effectiveness as well as get rid of the
> modulus and make the hash not attackable.

Ok makes sense to use jhash and also the multiplication.

Hmm but randomizations means it won't be stable on benchmarks, will it?
Is attacking such a hash really a problem? Having stable performance
on benchmarks might be preferable.

The other thing (one of my favourite pet peeves) is that
get_random_bytes() on reasonably early kernel boot
is not very random because there will be hardly any entropy in the pool.
So I'm not sure it is actually particularly non predictible,
at least on systems who transmit packets early.

-Andi