* [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* Re: [PATCH 2/2] net: Use Toeplitz for IPv4 and IPv6 connection hashing
2013-09-23 22:44 [PATCH 2/2] net: Use Toeplitz for IPv4 and IPv6 connection hashing Tom Herbert
@ 2013-09-23 23:11 ` Stephen Hemminger
2013-09-23 23:26 ` Tom Herbert
2013-09-23 23:17 ` Hannes Frederic Sowa
1 sibling, 1 reply; 4+ messages in thread
From: Stephen Hemminger @ 2013-09-23 23:11 UTC (permalink / raw)
To: Tom Herbert; +Cc: davem, netdev, jesse.brandeburg
On Mon, 23 Sep 2013 15:44:51 -0700 (PDT)
Tom Herbert <therbert@google.com> wrote:
> 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
It looks slower and more complex than Jhash, what is the benefit?
Have you investigated using Murmur instead?
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH 2/2] net: Use Toeplitz for IPv4 and IPv6 connection hashing
2013-09-23 23:11 ` Stephen Hemminger
@ 2013-09-23 23:26 ` Tom Herbert
0 siblings, 0 replies; 4+ messages in thread
From: Tom Herbert @ 2013-09-23 23:26 UTC (permalink / raw)
To: Stephen Hemminger; +Cc: David Miller, Linux Netdev List, Brandeburg, Jesse
On Mon, Sep 23, 2013 at 4:11 PM, Stephen Hemminger
<stephen@networkplumber.org> wrote:
> On Mon, 23 Sep 2013 15:44:51 -0700 (PDT)
> Tom Herbert <therbert@google.com> wrote:
>
>> 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
>
> It looks slower and more complex than Jhash, what is the benefit?
> Have you investigated using Murmur instead?
Benefit would be to leverage and be compatible HW hash computation...
perhaps this is just an intellectual curiosity :-)
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH 2/2] net: Use Toeplitz for IPv4 and IPv6 connection hashing
2013-09-23 22:44 [PATCH 2/2] net: Use Toeplitz for IPv4 and IPv6 connection hashing Tom Herbert
2013-09-23 23:11 ` Stephen Hemminger
@ 2013-09-23 23:17 ` Hannes Frederic Sowa
1 sibling, 0 replies; 4+ messages in thread
From: Hannes Frederic Sowa @ 2013-09-23 23:17 UTC (permalink / raw)
To: Tom Herbert; +Cc: davem, netdev, jesse.brandeburg
On Mon, Sep 23, 2013 at 03:44:51PM -0700, Tom Herbert wrote:
> 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
You seem to discard the secret inputs. This should make the hashing
considerable more insecure.
I always believed the reason for choosing linear feedback shift register
based hash functions was because of the parallelism a pure hardware
based implementation could exploit. This does not matter for the kernel.
IMHO jhash should be considered more secure just because of its wider usage.
;)
Greetings,
Hannes
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2013-09-23 23:26 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2013-09-23 22:44 [PATCH 2/2] net: Use Toeplitz for IPv4 and IPv6 connection hashing Tom Herbert
2013-09-23 23:11 ` Stephen Hemminger
2013-09-23 23:26 ` Tom Herbert
2013-09-23 23:17 ` Hannes Frederic Sowa
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox