All of lore.kernel.org
 help / color / mirror / Atom feed
* [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn().
@ 2023-07-21 22:24 Kuniyuki Iwashima
  2023-07-22  0:07 ` Amit Klein
                   ` (2 more replies)
  0 siblings, 3 replies; 7+ messages in thread
From: Kuniyuki Iwashima @ 2023-07-21 22:24 UTC (permalink / raw)
  To: David S. Miller, Eric Dumazet, Jakub Kicinski, Paolo Abeni, David Ahern
  Cc: Amit Klein, Benjamin Herrenschmidt, Kuniyuki Iwashima,
	Kuniyuki Iwashima, netdev, Stewart Smith, Samuel Mendoza-Jonas

From: Stewart Smith <trawets@amazon.com>

For both IPv4 and IPv6 incoming TCP connections are tracked in a hash
table with a hash over the source & destination addresses and ports.
However, the IPv6 hash is insufficient and can lead to a high rate of
collisions.

The IPv6 hash used an XOR to fit everything into the 96 bits for the
fast jenkins hash, meaning it is possible for an external entity to
ensure the hash collides, thus falling back to a linear search in the
bucket, which is slow.

We take the approach of hash the full length of IPv6 address in
__ipv6_addr_jhash() so that all users can benefit from a more secure
version.

While this may look like it adds overhead, the reality of modern CPUs
means that this is unmeasurable in real world scenarios.

In simulating with llvm-mca, the increase in cycles for the hashing
code was ~16 cycles on Skylake (from a base of ~155), and an extra ~9
on Nehalem (base of ~173).

In commit dd6d2910c5e0 ("netfilter: conntrack: switch to siphash")
netfilter switched from a jenkins hash to a siphash, but even the faster
hsiphash is a more significant overhead (~20-30%) in some preliminary
testing.  So, in this patch, we keep to the more conservative approach to
ensure we don't add much overhead per SYN.

In testing, this results in a consistently even spread across the
connection buckets.  In both testing and real-world scenarios, we have
not found any measurable performance impact.

Fixes: 08dcdbf6a7b9 ("ipv6: use a stronger hash for tcp")
Signed-off-by: Stewart Smith <trawets@amazon.com>
Signed-off-by: Samuel Mendoza-Jonas <samjonas@amazon.com>
Suggested-by: Eric Dumazet <edumazet@google.com>
Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.com>
---
v2:
  * Hash all IPv6 bytes once in __ipv6_addr_jhash() instead of reusing
    some bytes twice.

v1: https://lore.kernel.org/netdev/20230629015844.800280-1-samjonas@amazon.com/
---
 include/net/ipv6.h | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)

diff --git a/include/net/ipv6.h b/include/net/ipv6.h
index 7332296eca44..2acc4c808d45 100644
--- a/include/net/ipv6.h
+++ b/include/net/ipv6.h
@@ -752,12 +752,8 @@ static inline u32 ipv6_addr_hash(const struct in6_addr *a)
 /* more secured version of ipv6_addr_hash() */
 static inline u32 __ipv6_addr_jhash(const struct in6_addr *a, const u32 initval)
 {
-	u32 v = (__force u32)a->s6_addr32[0] ^ (__force u32)a->s6_addr32[1];
-
-	return jhash_3words(v,
-			    (__force u32)a->s6_addr32[2],
-			    (__force u32)a->s6_addr32[3],
-			    initval);
+	return jhash2((__force const u32 *)a->s6_addr32,
+		      ARRAY_SIZE(a->s6_addr32), initval);
 }
 
 static inline bool ipv6_addr_loopback(const struct in6_addr *a)
-- 
2.30.2


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

* Re: [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn().
  2023-07-21 22:24 [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn() Kuniyuki Iwashima
@ 2023-07-22  0:07 ` Amit Klein
  2023-07-22  1:39   ` Kuniyuki Iwashima
  2023-07-24  9:41 ` Eric Dumazet
  2023-07-25  0:20 ` patchwork-bot+netdevbpf
  2 siblings, 1 reply; 7+ messages in thread
From: Amit Klein @ 2023-07-22  0:07 UTC (permalink / raw)
  To: Kuniyuki Iwashima
  Cc: David S. Miller, Eric Dumazet, Jakub Kicinski, Paolo Abeni,
	David Ahern, Benjamin Herrenschmidt, Kuniyuki Iwashima, netdev,
	Stewart Smith, Samuel Mendoza-Jonas

Resending because some recipients require plaintext email. Sorry.
Original message:

This is certainly better than the original code.

Two remarks:

1. In general, using SipHash is more secure, even if only for its
longer key (128 bits, cf. jhash's 32 bits), which renders simple
enumeration attacks infeasible. I understand that in a different
context, switching from jhash to siphash incurred some overhead, but
maybe here it won't.

2. Taking a more holistic approach to __ipv6_addr_jhash(), I surveyed
where and how it's used. In most cases, it is used for hashing
together the IPv6 local address, foreign address and optionally some
more data (e.g. layer 4 protocol number, layer 4 ports).
Security-wise, it makes more sense to hash all data together once, and
not piecewise as it's done today (i.e. today it's
jhash(....,jhash(faddr),...), which cases the faddr into 32 bits,
whereas the recommended way is to hash all items in their entirety,
i.e. jhash(...,faddr,...)). This requires scrutinizing all 6
invocations of __ipv6_addr_jhash() one by one and modifying the
calling code accordingly.

Thanks,
-Amit

On Sat, Jul 22, 2023 at 1:24 AM Kuniyuki Iwashima <kuniyu@amazon.com> wrote:
>
> From: Stewart Smith <trawets@amazon.com>
>
> For both IPv4 and IPv6 incoming TCP connections are tracked in a hash
> table with a hash over the source & destination addresses and ports.
> However, the IPv6 hash is insufficient and can lead to a high rate of
> collisions.
>
> The IPv6 hash used an XOR to fit everything into the 96 bits for the
> fast jenkins hash, meaning it is possible for an external entity to
> ensure the hash collides, thus falling back to a linear search in the
> bucket, which is slow.
>
> We take the approach of hash the full length of IPv6 address in
> __ipv6_addr_jhash() so that all users can benefit from a more secure
> version.
>
> While this may look like it adds overhead, the reality of modern CPUs
> means that this is unmeasurable in real world scenarios.
>
> In simulating with llvm-mca, the increase in cycles for the hashing
> code was ~16 cycles on Skylake (from a base of ~155), and an extra ~9
> on Nehalem (base of ~173).
>
> In commit dd6d2910c5e0 ("netfilter: conntrack: switch to siphash")
> netfilter switched from a jenkins hash to a siphash, but even the faster
> hsiphash is a more significant overhead (~20-30%) in some preliminary
> testing.  So, in this patch, we keep to the more conservative approach to
> ensure we don't add much overhead per SYN.
>
> In testing, this results in a consistently even spread across the
> connection buckets.  In both testing and real-world scenarios, we have
> not found any measurable performance impact.
>
> Fixes: 08dcdbf6a7b9 ("ipv6: use a stronger hash for tcp")
> Signed-off-by: Stewart Smith <trawets@amazon.com>
> Signed-off-by: Samuel Mendoza-Jonas <samjonas@amazon.com>
> Suggested-by: Eric Dumazet <edumazet@google.com>
> Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.com>
> ---
> v2:
>   * Hash all IPv6 bytes once in __ipv6_addr_jhash() instead of reusing
>     some bytes twice.
>
> v1: https://lore.kernel.org/netdev/20230629015844.800280-1-samjonas@amazon.com/
> ---
>  include/net/ipv6.h | 8 ++------
>  1 file changed, 2 insertions(+), 6 deletions(-)
>
> diff --git a/include/net/ipv6.h b/include/net/ipv6.h
> index 7332296eca44..2acc4c808d45 100644
> --- a/include/net/ipv6.h
> +++ b/include/net/ipv6.h
> @@ -752,12 +752,8 @@ static inline u32 ipv6_addr_hash(const struct in6_addr *a)
>  /* more secured version of ipv6_addr_hash() */
>  static inline u32 __ipv6_addr_jhash(const struct in6_addr *a, const u32 initval)
>  {
> -       u32 v = (__force u32)a->s6_addr32[0] ^ (__force u32)a->s6_addr32[1];
> -
> -       return jhash_3words(v,
> -                           (__force u32)a->s6_addr32[2],
> -                           (__force u32)a->s6_addr32[3],
> -                           initval);
> +       return jhash2((__force const u32 *)a->s6_addr32,
> +                     ARRAY_SIZE(a->s6_addr32), initval);
>  }
>
>  static inline bool ipv6_addr_loopback(const struct in6_addr *a)
> --
> 2.30.2
>

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

* Re: [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn().
  2023-07-22  0:07 ` Amit Klein
@ 2023-07-22  1:39   ` Kuniyuki Iwashima
  2023-07-22  3:17     ` Smith, Stewart
  0 siblings, 1 reply; 7+ messages in thread
From: Kuniyuki Iwashima @ 2023-07-22  1:39 UTC (permalink / raw)
  To: aksecurity
  Cc: benh, davem, dsahern, edumazet, kuba, kuni1840, kuniyu, netdev,
	pabeni, samjonas, trawets

From: Amit Klein <aksecurity@gmail.com>
Date: Sat, 22 Jul 2023 03:07:49 +0300
> Resending because some recipients require plaintext email. Sorry.
> Original message:
> 
> This is certainly better than the original code.

Thanks for reviewing!


> 
> Two remarks:
> 
> 1. In general, using SipHash is more secure, even if only for its
> longer key (128 bits, cf. jhash's 32 bits), which renders simple
> enumeration attacks infeasible. I understand that in a different
> context, switching from jhash to siphash incurred some overhead, but
> maybe here it won't.

I see.  Stewart tested hsiphash and observed more overhead as
noted in the changelog, but let me give another shot to SipHash
and HSiphash.

I'll report back here next week.


> 
> 2. Taking a more holistic approach to __ipv6_addr_jhash(), I surveyed
> where and how it's used. In most cases, it is used for hashing
> together the IPv6 local address, foreign address and optionally some
> more data (e.g. layer 4 protocol number, layer 4 ports).
> Security-wise, it makes more sense to hash all data together once, and
> not piecewise as it's done today (i.e. today it's
> jhash(....,jhash(faddr),...), which cases the faddr into 32 bits,
> whereas the recommended way is to hash all items in their entirety,
> i.e. jhash(...,faddr,...)).

Agree.


> This requires scrutinizing all 6
> invocations of __ipv6_addr_jhash() one by one and modifying the
> calling code accordingly.

At a glance, only rds_conn_bucket() seems a little bit tricky
as it uses v4 hash function later.

But I'll take a deeper look.

Thanks!


> 
> Thanks,
> -Amit
> 
> On Sat, Jul 22, 2023 at 1:24 AM Kuniyuki Iwashima <kuniyu@amazon.com> wrote:
> >
> > From: Stewart Smith <trawets@amazon.com>
> >
> > For both IPv4 and IPv6 incoming TCP connections are tracked in a hash
> > table with a hash over the source & destination addresses and ports.
> > However, the IPv6 hash is insufficient and can lead to a high rate of
> > collisions.
> >
> > The IPv6 hash used an XOR to fit everything into the 96 bits for the
> > fast jenkins hash, meaning it is possible for an external entity to
> > ensure the hash collides, thus falling back to a linear search in the
> > bucket, which is slow.
> >
> > We take the approach of hash the full length of IPv6 address in
> > __ipv6_addr_jhash() so that all users can benefit from a more secure
> > version.
> >
> > While this may look like it adds overhead, the reality of modern CPUs
> > means that this is unmeasurable in real world scenarios.
> >
> > In simulating with llvm-mca, the increase in cycles for the hashing
> > code was ~16 cycles on Skylake (from a base of ~155), and an extra ~9
> > on Nehalem (base of ~173).
> >
> > In commit dd6d2910c5e0 ("netfilter: conntrack: switch to siphash")
> > netfilter switched from a jenkins hash to a siphash, but even the faster
> > hsiphash is a more significant overhead (~20-30%) in some preliminary
> > testing.  So, in this patch, we keep to the more conservative approach to
> > ensure we don't add much overhead per SYN.
> >
> > In testing, this results in a consistently even spread across the
> > connection buckets.  In both testing and real-world scenarios, we have
> > not found any measurable performance impact.
> >
> > Fixes: 08dcdbf6a7b9 ("ipv6: use a stronger hash for tcp")
> > Signed-off-by: Stewart Smith <trawets@amazon.com>
> > Signed-off-by: Samuel Mendoza-Jonas <samjonas@amazon.com>
> > Suggested-by: Eric Dumazet <edumazet@google.com>
> > Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.com>
> > ---
> > v2:
> >   * Hash all IPv6 bytes once in __ipv6_addr_jhash() instead of reusing
> >     some bytes twice.
> >
> > v1: https://lore.kernel.org/netdev/20230629015844.800280-1-samjonas@amazon.com/
> > ---
> >  include/net/ipv6.h | 8 ++------
> >  1 file changed, 2 insertions(+), 6 deletions(-)
> >
> > diff --git a/include/net/ipv6.h b/include/net/ipv6.h
> > index 7332296eca44..2acc4c808d45 100644
> > --- a/include/net/ipv6.h
> > +++ b/include/net/ipv6.h
> > @@ -752,12 +752,8 @@ static inline u32 ipv6_addr_hash(const struct in6_addr *a)
> >  /* more secured version of ipv6_addr_hash() */
> >  static inline u32 __ipv6_addr_jhash(const struct in6_addr *a, const u32 initval)
> >  {
> > -       u32 v = (__force u32)a->s6_addr32[0] ^ (__force u32)a->s6_addr32[1];
> > -
> > -       return jhash_3words(v,
> > -                           (__force u32)a->s6_addr32[2],
> > -                           (__force u32)a->s6_addr32[3],
> > -                           initval);
> > +       return jhash2((__force const u32 *)a->s6_addr32,
> > +                     ARRAY_SIZE(a->s6_addr32), initval);
> >  }
> >
> >  static inline bool ipv6_addr_loopback(const struct in6_addr *a)
> > --
> > 2.30.2


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

* Re: [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn().
  2023-07-22  1:39   ` Kuniyuki Iwashima
@ 2023-07-22  3:17     ` Smith, Stewart
  2023-07-24 19:58       ` Kuniyuki Iwashima
  0 siblings, 1 reply; 7+ messages in thread
From: Smith, Stewart @ 2023-07-22  3:17 UTC (permalink / raw)
  To: Iwashima, Kuniyuki
  Cc: aksecurity, Herrenschmidt, Benjamin, David S . Miller,
	David Ahern, Eric Dumazet, Jakub Kicinski, kuni1840, Iwashima,
	Kuniyuki, netdev, Paolo Abeni, Mendoza-Jonas, Samuel

On Jul 21, 2023, at 6:39 PM, Iwashima, Kuniyuki <kuniyu@amazon.co.jp> wrote:
> 
> From: Amit Klein <aksecurity@gmail.com>
> Date: Sat, 22 Jul 2023 03:07:49 +0300
>> Resending because some recipients require plaintext email. Sorry.
>> Original message:
>> 
>> This is certainly better than the original code.
> 
> Thanks for reviewing!
> 
> 
>> 
>> Two remarks:
>> 
>> 1. In general, using SipHash is more secure, even if only for its
>> longer key (128 bits, cf. jhash's 32 bits), which renders simple
>> enumeration attacks infeasible. I understand that in a different
>> context, switching from jhash to siphash incurred some overhead, but
>> maybe here it won't.
> 
> I see.  Stewart tested hsiphash and observed more overhead as
> noted in the changelog, but let me give another shot to SipHash
> and HSiphash.

When originally looking at what to do for the collisions, it did seem like siphash would be the better hash, but I did have some concern around what the real-world performance impact could be, and wanted to have something that would alleviate the issue at hand that nobody could even *possibly* remotely contemplate complaining was a problem to apply the patch to their systems because of “performance”.. which was why keeping jhash but with modifications was where we started.

Two things about siphash/hsiphash that I had open questions about:
- is the extra overhead of the hash calculation going to be noticeable at all in any regular workload
- all the jhash stuff gets inlined nicely and the compiler does wonderful things, but it’s possible that siphash will end up always with a jump, which would add more to the extra overhead (and that llvm-mca doesn’t really model well, so it was harder to prove in sim). Again, not quite sure the real world impact to real world workloads.

> 
> I'll report back here next week.
> 
> 
>> 
>> 2. Taking a more holistic approach to __ipv6_addr_jhash(), I surveyed
>> where and how it's used. In most cases, it is used for hashing
>> together the IPv6 local address, foreign address and optionally some
>> more data (e.g. layer 4 protocol number, layer 4 ports).
>> Security-wise, it makes more sense to hash all data together once, and
>> not piecewise as it's done today (i.e. today it's
>> jhash(....,jhash(faddr),...), which cases the faddr into 32 bits,
>> whereas the recommended way is to hash all items in their entirety,
>> i.e. jhash(...,faddr,...)).
> 
> Agree.

When looking at this originally, I was trying to work out what was intentional for some reason I wasn’t smart enough to understand and what had just grown over the past (eep.. nearly 3 decades I think) and could do with a bit of a rethink.

>> This requires scrutinizing all 6
>> invocations of __ipv6_addr_jhash() one by one and modifying the
>> calling code accordingly.
> 
> At a glance, only rds_conn_bucket() seems a little bit tricky
> as it uses v4 hash function later.
> 
> But I'll take a deeper look.


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

* Re: [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn().
  2023-07-21 22:24 [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn() Kuniyuki Iwashima
  2023-07-22  0:07 ` Amit Klein
@ 2023-07-24  9:41 ` Eric Dumazet
  2023-07-25  0:20 ` patchwork-bot+netdevbpf
  2 siblings, 0 replies; 7+ messages in thread
From: Eric Dumazet @ 2023-07-24  9:41 UTC (permalink / raw)
  To: Kuniyuki Iwashima
  Cc: David S. Miller, Jakub Kicinski, Paolo Abeni, David Ahern,
	Amit Klein, Benjamin Herrenschmidt, Kuniyuki Iwashima, netdev,
	Stewart Smith, Samuel Mendoza-Jonas

On Sat, Jul 22, 2023 at 12:24 AM Kuniyuki Iwashima <kuniyu@amazon.com> wrote:
>
> From: Stewart Smith <trawets@amazon.com>
>
> For both IPv4 and IPv6 incoming TCP connections are tracked in a hash
> table with a hash over the source & destination addresses and ports.
> However, the IPv6 hash is insufficient and can lead to a high rate of
> collisions.
>
> The IPv6 hash used an XOR to fit everything into the 96 bits for the
> fast jenkins hash, meaning it is possible for an external entity to
> ensure the hash collides, thus falling back to a linear search in the
> bucket, which is slow.
>
> We take the approach of hash the full length of IPv6 address in
> __ipv6_addr_jhash() so that all users can benefit from a more secure
> version.
>
> While this may look like it adds overhead, the reality of modern CPUs
> means that this is unmeasurable in real world scenarios.
>
> In simulating with llvm-mca, the increase in cycles for the hashing
> code was ~16 cycles on Skylake (from a base of ~155), and an extra ~9
> on Nehalem (base of ~173).
>
> In commit dd6d2910c5e0 ("netfilter: conntrack: switch to siphash")
> netfilter switched from a jenkins hash to a siphash, but even the faster
> hsiphash is a more significant overhead (~20-30%) in some preliminary
> testing.  So, in this patch, we keep to the more conservative approach to
> ensure we don't add much overhead per SYN.
>
> In testing, this results in a consistently even spread across the
> connection buckets.  In both testing and real-world scenarios, we have
> not found any measurable performance impact.
>
> Fixes: 08dcdbf6a7b9 ("ipv6: use a stronger hash for tcp")
> Signed-off-by: Stewart Smith <trawets@amazon.com>
> Signed-off-by: Samuel Mendoza-Jonas <samjonas@amazon.com>
> Suggested-by: Eric Dumazet <edumazet@google.com>
> Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.com>
> ---
> v2:
>   * Hash all IPv6 bytes once in __ipv6_addr_jhash() instead of reusing
>     some bytes twice.

Thanks, I think we should merge this patch as is, and think about
further improvements later.

Reviewed-by: Eric Dumazet <edumazet@google.com>

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

* Re: [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn().
  2023-07-22  3:17     ` Smith, Stewart
@ 2023-07-24 19:58       ` Kuniyuki Iwashima
  0 siblings, 0 replies; 7+ messages in thread
From: Kuniyuki Iwashima @ 2023-07-24 19:58 UTC (permalink / raw)
  To: trawets
  Cc: aksecurity, benh, davem, dsahern, edumazet, kuba, kuni1840,
	kuniyu, netdev, pabeni, samjonas

From: "Smith, Stewart" <trawets@amazon.com>
Date: Sat, 22 Jul 2023 03:17:53 +0000
> On Jul 21, 2023, at 6:39 PM, Iwashima, Kuniyuki <kuniyu@amazon.co.jp> wrote:
> > 
> > From: Amit Klein <aksecurity@gmail.com>
> > Date: Sat, 22 Jul 2023 03:07:49 +0300
> >> Resending because some recipients require plaintext email. Sorry.
> >> Original message:
> >> 
> >> This is certainly better than the original code.
> > 
> > Thanks for reviewing!
> > 
> > 
> >> 
> >> Two remarks:
> >> 
> >> 1. In general, using SipHash is more secure, even if only for its
> >> longer key (128 bits, cf. jhash's 32 bits), which renders simple
> >> enumeration attacks infeasible. I understand that in a different
> >> context, switching from jhash to siphash incurred some overhead, but
> >> maybe here it won't.
> > 
> > I see.  Stewart tested hsiphash and observed more overhead as
> > noted in the changelog, but let me give another shot to SipHash
> > and HSiphash.
> 
> When originally looking at what to do for the collisions, it did seem
> like siphash would be the better hash, but I did have some concern around
> what the real-world performance impact could be, and wanted to have
> something that would alleviate the issue at hand that nobody could even
> *possibly* remotely contemplate complaining was a problem to apply the
> patch to their systems because of “performance”.. which was why keeping
> jhash but with modifications was where we started.
> 
> Two things about siphash/hsiphash that I had open questions about:
> - is the extra overhead of the hash calculation going to be noticeable at
>   all in any regular workload
> - all the jhash stuff gets inlined nicely and the compiler does wonderful
>   things, but it’s possible that siphash will end up always with a jump,
>   which would add more to the extra overhead (and that llvm-mca doesn’t
>   really model well, so it was harder to prove in sim). Again, not quite
>   sure the real world impact to real world workloads.

Here is the llvm-mca result.  Base commit is 1671bcfd76fd.
In Total Cycles, siphash is much slower than others.

  On Skylake: jhash2: +10%, hsiphash +8%, siphash: +23%
  On Nehalem: jahsh2: +5%,  hsiphash +9%, siphash: +26%

  Skylake             	base		jhash2                  hsiphash                siphash                 
  Iterations          	  1.00		  1.00 (100.00)		  1.00 (100.00)		  1.00 (100.00)		
  Instructions        	104.00		137.00 (131.73)		166.00 (159.62)		222.00 (213.46)		
  Total Cycles        	155.00		171.00 (110.32)		168.00 (108.39)		191.00 (123.23)		
  Total uOps          	132.00		166.00 (125.76)		192.00 (145.45)		248.00 (187.88)		
  Dispatch Width      	  6.00		  6.00 (100.00)		  6.00 (100.00)		  6.00 (100.00)		
  uOps Per Cycle      	  0.85		  0.97 (114.12)		  1.14 (134.12)		  1.30 (152.94)		
  IPC                 	  0.67		  0.80 (119.40)		  0.99 (147.76)		  1.16 (173.13)		

  Nehalem             	base		jhash2                  hsiphash                siphash                 
  Iterations          	  1.00		  1.00 (100.00)		  1.00 (100.00)		  1.00 (100.00)		
  Instructions        	104.00		137.00 (131.73)		166.00 (159.62)		222.00 (213.46)		
  Total Cycles        	173.00		182.00 (105.20)		190.00 (109.83)		218.00 (126.01)		
  Total uOps          	130.00		170.00 (130.77)		215.00 (165.38)		295.00 (226.92)		
  Dispatch Width      	  4.00		  4.00 (100.00)		  4.00 (100.00)		  4.00 (100.00)		
  uOps Per Cycle      	  0.75		  0.93 (124.00)		  1.13 (150.67)		  1.35 (180.00)		
  IPC                 	  0.60		  0.75 (125.00)		  0.87 (145.00)		  1.02 (170.00)	


However, inet6_ehashfn() is not dominant in the fast path, and there
seems to be not so big impact during benchmarking with super_netperf.

  for i in $(seq 1 5);
  do
      for i in 64 128 256 512 1024 2048 4096;
      do
  	printf "%4d: " $i;
  	./super_netperf 32 -H ::1 -l 60 -- -m $i -M $i;
      done
  done

Average of 5 run:

  $i    10^6 bps
  size	base		jhash2                  hsiphash                siphash                 
  64	20735.80	20419.96 (98.48)	20335.60 (98.07)	20404.08 (98.40)	
  128	40450.40	40167.66 (99.30)	39957.32 (98.78)	40222.06 (99.44)	
  256	73740.84	74219.26 (100.65)	73625.76 (99.84)	74081.52 (100.46)	
  512	142075.60	142461.80 (100.27)	141237.00 (99.41)	141789.60 (99.80)	
  1024	254391.00	253553.20 (99.67)	252751.00 (99.36)	253718.00 (99.74)	
  2048	421221.20	421175.60 (99.99)	420142.80 (99.74)	418189.20 (99.28)	
  4096	599158.20	597958.20 (99.80)	594472.20 (99.22)	598591.00 (99.91)


Also, in the kernel with hsiphash/siphash, there is call op as
hsiphash_4u32() and siphash_2u64() are exposed to modules, but
both functions did not have jumps.

hsiphash:
  $ gdb -batch -ex 'file vmlinux' -ex 'disassemble inet6_ehashfn' | grep hsiphash
     0xffffffff81de5bcc <+92>:	call   0xffffffff81f637e0 <hsiphash_4u32>
  $ gdb -batch -ex 'file vmlinux' -ex 'disassemble hsiphash_4u32' | grep j
     0xffffffff81f63970 <+400>:	jmp    0xffffffff81f85ec0 <__x86_return_thunk>

siphash:
  $ gdb -batch -ex 'file vmlinux' -ex 'disassemble inet6_ehashfn' | grep siphash
     0xffffffff81de5bc4 <+84>:	call   0xffffffff81f625e0 <siphash_2u64>
  $ gdb -batch -ex 'file vmlinux' -ex 'disassemble siphash_2u64' | grep j
     0xffffffff81f62837 <+599>:	jmp    0xffffffff81f85ec0 <__x86_return_thunk>


All of the data above are uploaded here.
https://github.com/q2ven/inet6_ehashfn

Thanks!

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

* Re: [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn().
  2023-07-21 22:24 [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn() Kuniyuki Iwashima
  2023-07-22  0:07 ` Amit Klein
  2023-07-24  9:41 ` Eric Dumazet
@ 2023-07-25  0:20 ` patchwork-bot+netdevbpf
  2 siblings, 0 replies; 7+ messages in thread
From: patchwork-bot+netdevbpf @ 2023-07-25  0:20 UTC (permalink / raw)
  To: Kuniyuki Iwashima
  Cc: davem, edumazet, kuba, pabeni, dsahern, aksecurity, benh,
	kuni1840, netdev, trawets, samjonas

Hello:

This patch was applied to netdev/net.git (main)
by Jakub Kicinski <kuba@kernel.org>:

On Fri, 21 Jul 2023 15:24:10 -0700 you wrote:
> From: Stewart Smith <trawets@amazon.com>
> 
> For both IPv4 and IPv6 incoming TCP connections are tracked in a hash
> table with a hash over the source & destination addresses and ports.
> However, the IPv6 hash is insufficient and can lead to a high rate of
> collisions.
> 
> [...]

Here is the summary with links:
  - [v2,net] tcp: Reduce chance of collisions in inet6_hashfn().
    https://git.kernel.org/netdev/net/c/d11b0df7ddf1

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html



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

end of thread, other threads:[~2023-07-25  0:20 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-07-21 22:24 [PATCH v2 net] tcp: Reduce chance of collisions in inet6_hashfn() Kuniyuki Iwashima
2023-07-22  0:07 ` Amit Klein
2023-07-22  1:39   ` Kuniyuki Iwashima
2023-07-22  3:17     ` Smith, Stewart
2023-07-24 19:58       ` Kuniyuki Iwashima
2023-07-24  9:41 ` Eric Dumazet
2023-07-25  0:20 ` patchwork-bot+netdevbpf

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.