[PATCH 2/2] net: Use Toeplitz for IPv4 and IPv6 connection hashing

* [PATCH 2/2] net: Use Toeplitz for IPv4 and IPv6 connection hashing
@ 2013-09-23 22:44 Tom Herbert
  2013-09-23 23:11 ` Stephen Hemminger
  2013-09-23 23:17 ` Hannes Frederic Sowa
  0 siblings, 2 replies; 4+ messages in thread
From: Tom Herbert @ 2013-09-23 22:44 UTC (permalink / raw)
  To: davem; +Cc: netdev, jesse.brandeburg

Add a config option to specify which hash to use for IPv4 and IPv6
established connection hashing. The alternative option is original
jhash method (this patch sets Toeplitz to default).

Toeplitz is a little more heavy weight than jhash method.  For IPv4
the difference seems to be negligible, for IPv6 there is some
performance regression due mostly to the fact that Toeplitz hashes
over all the bits in the IPv6 address whereas Jhash doesn't (this
implies that Toeplitz might be more secure).

Some performance numbers using 200 netperf TCP_RR clients:

Toeplitz
  IPv4
    58.72% CPU utilization
    110/146/198 90/95/99% latencies
    1.72549e+06 tps
  IPv6
    72.38% CPU utilization
    117/168/255 90/95/99% latencies
    1.58545e+06 tps

Jhash
  IPv4
    57.67% CPU utilization
    111/146/196 90/95/99% latencies
    1.71574e+06 tps
  IPv6
    71.84% CPU utilization
    117/166/248 90/95/99% latencies
    1.59359e+06 tps

Standalone performance measurement:

Toeplitz
  IPv4
    40 nsecs/hash
  IPv6
    105 nsecs/hash
Jhash
  IPv4
    39 nsecs/hash
  IPv6
    77 nsecs/hash

Signed-off-by: Tom Herbert <therbert@google.com>
---
 include/net/inet6_hashtables.h | 16 ++++++++++++++++
 include/net/inet_sock.h        | 16 ++++++++++++++++
 net/ipv4/Kconfig               | 14 ++++++++++++++
 3 files changed, 46 insertions(+)

diff --git a/include/net/inet6_hashtables.h b/include/net/inet6_hashtables.h
index f52fa88..492a45b 100644
--- a/include/net/inet6_hashtables.h
+++ b/include/net/inet6_hashtables.h
@@ -32,12 +32,28 @@ static inline unsigned int inet6_ehashfn(struct net *net,
 				const struct in6_addr *laddr, const u16 lport,
 				const struct in6_addr *faddr, const __be16 fport)
 {
+#if IS_ENABLED(CONFIG_IP_HASH_TOEPLITZ)
+	struct {
+		struct in6_addr saddr;
+		struct in6_addr daddr;
+		u16 sport;
+		u16 dport;
+	} input;
+
+        input.daddr = *laddr;
+        input.saddr = *faddr;
+        input.sport = htons(lport);
+        input.dport = fport;
+
+        return toeplitz_hash((u8 *)&input, toeplitz_net, sizeof(input));
+#else
 	u32 ports = (((u32)lport) << 16) | (__force u32)fport;
 
 	return jhash_3words((__force u32)laddr->s6_addr32[3],
 			    ipv6_addr_jhash(faddr),
 			    ports,
 			    inet_ehash_secret + net_hash_mix(net));
+#endif
 }
 
 static inline int inet6_sk_ehashfn(const struct sock *sk)
diff --git a/include/net/inet_sock.h b/include/net/inet_sock.h
index 636d203..02e2ee2 100644
--- a/include/net/inet_sock.h
+++ b/include/net/inet_sock.h
@@ -209,10 +209,26 @@ static inline unsigned int inet_ehashfn(struct net *net,
 					const __be32 laddr, const __u16 lport,
 					const __be32 faddr, const __be16 fport)
 {
+#if IS_ENABLED(CONFIG_IP_HASH_TOEPLITZ)
+	struct {
+		u32 saddr;
+		u32 daddr;
+		u16 sport;
+		u16 dport;
+	} input;
+
+	input.saddr = faddr;
+	input.daddr = laddr;
+	input.sport = fport;
+	input.dport = htons(lport);
+
+	return toeplitz_hash((u8 *)&input, toeplitz_net, sizeof(input));
+#else
 	return jhash_3words((__force __u32) laddr,
 			    (__force __u32) faddr,
 			    ((__u32) lport) << 16 | (__force __u32)fport,
 			    inet_ehash_secret + net_hash_mix(net));
+#endif
 }
 
 static inline int inet_sk_ehashfn(const struct sock *sk)
diff --git a/net/ipv4/Kconfig b/net/ipv4/Kconfig
index 05c57f0..c9a533f 100644
--- a/net/ipv4/Kconfig
+++ b/net/ipv4/Kconfig
@@ -104,6 +104,20 @@ config IP_ROUTE_VERBOSE
 config IP_ROUTE_CLASSID
 	bool
 
+choice
+	prompt "IP: connection hashing algorithm"
+	default IP_HASH_TOEPLITZ
+	help
+	  Select the default hashing algortihm for IP connections
+
+	config IP_HASH_JHASH
+		bool "Jhash"
+
+	config IP_HASH_TOEPLITZ
+		bool "Toeplitz"
+		select NET_TOEPLITZ
+endchoice
+
 config IP_PNP
 	bool "IP: kernel level autoconfiguration"
 	help
-- 
1.8.4

^ permalink raw reply related	[flat|nested] 4+ messages in thread