Skip to contentSkip to conversation

Make simple TX hash little endian safe.

PATCH In review Andi Kleen 3 participants 9 messages Jul 21, 2008

Subsystems (2)
Networking Network drivers
lore
Share & tools
lore

Andi Kleen

author
#0 lore raw

PATCH 1/1 Make simple TX hash little endian safe.

From: Andi Kleen <[email protected]>

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 <[email protected]>
---
 net/core/dev.c |    7 +++++--
 1 files changed, 5 insertions(+), 2 deletions(-)
net/core/dev.c +5 -2
index 2eed17b..c35fefc 100644
@@ -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:
Signature · 1 line
1.5.6
author
#1 lore raw

PATCH 1/1 Add a statistics counter for tx hash miss

From: Andi Kleen <[email protected]>

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

Signed-off-by Andi Kleen <[email protected]>
---
 include/linux/snmp.h |    1 +
 net/core/dev.c       |    3 +++
 net/ipv4/proc.c      |    1 +
 3 files changed, 5 insertions(+), 0 deletions(-)
include/linux/snmp.h +1 -0
index 5df62ef..c4d69b7 100644
@@ -214,6 +214,7 @@ enum
 	LINUX_MIB_TCPDSACKIGNOREDOLD,		/* TCPSACKIgnoredOld */
 	LINUX_MIB_TCPDSACKIGNOREDNOUNDO,	/* TCPSACKIgnoredNoUndo */
 	LINUX_MIB_TCPSPURIOUSRTOS,		/* TCPSpuriousRTOs */
+	LINUX_MIB_TXHASHMISS,			/* TxHashMiss */
 	__LINUX_MIB_MAX
 };
net/core/dev.c +3 -0
index c35fefc..cc45878 100644
@@ -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;
 	}
net/ipv4/proc.c +1 -0
index 834356e..f621b87 100644
@@ -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
 };
Signature · 1 line
1.5.6
maintainer
#2 lore raw

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

From: Andi Kleen <[email protected]>
Date: Mon, 21 Jul 2008 10:48:08 +0200

Quoted 3 lines

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

Signed-off-by Andi Kleen <[email protected]>

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.

author
#3 lore raw

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

Quoted 11 lines · David Miller

From: Andi Kleen <[email protected]>
Date: Mon, 21 Jul 2008 10:48:08 +0200

Quoted 3 lines

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

Signed-off-by Andi Kleen <[email protected]>

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

maintainer
#4 lore raw

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

From: Andi Kleen <[email protected]>
Date: Mon, 21 Jul 2008 18:44:07 +0200

Quoted 8 lines · David Miller
Quoted 7 lines

From: Andi Kleen <[email protected]>
Date: Mon, 21 Jul 2008 10:48:08 +0200

Quoted 3 lines

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

Signed-off-by Andi Kleen <[email protected]>
Quoted 8 lines
Quoted 4 lines

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

#5 lore raw
In reply to Andi Kleen
Quoted 5 lines · Andi Kleen

From: Andi Kleen <[email protected]>

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.

Quoted 26 lines

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

Signed-off-by Andi Kleen <[email protected]>
---
 net/core/dev.c |    7 +++++--
 1 files changed, 5 insertions(+), 2 deletions(-)
net/core/dev.c +5 -2
index 2eed17b..c35fefc 100644
@@ -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:
author
#6 lore raw
Quoted 8 lines · Jarek Poplawski
Quoted 5 lines · Andi Kleen

From: Andi Kleen <[email protected]>

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

maintainer
#7 lore raw
In reply to Andi Kleen

From: Andi Kleen <[email protected]>
Date: Mon, 21 Jul 2008 10:48:07 +0200

Quoted 7 lines

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 <[email protected]>

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.

net/core/dev.c +21 -13
index 2eed17b..7e2d527 100644
@@ -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,
author
#8 lore raw
Quoted 7 lines · David Miller

From: Andi Kleen <[email protected]>
Date: Mon, 21 Jul 2008 10:48:07 +0200

Quoted 4 lines

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.

Quoted 7 lines
Quoted 3 lines

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

Signed-off-by Andi Kleen <[email protected]>

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