Re: [Xen-devel] [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing

[Paul Durrant]

> -Original Message-
> From: Tom Herbert [mailto:t...@herbertland.com]
> Sent: 14 February 2016 22:02
> To: Paul Durrant
> Cc: David Miller; net...@vger.kernel.org; xen-de...@lists.xenproject.org
> Subject: Re: [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing
> 
> On Fri, Feb 12, 2016 at 5:59 PM, Paul Durrant 
> wrote:
> >> -Original Message-
> >> From: David Miller [mailto:da...@davemloft.net]
> >> Sent: 12 February 2016 16:42
> >> To: Paul Durrant
> >> Cc: net...@vger.kernel.org; xen-de...@lists.xenproject.org
> >> Subject: Re: [PATCH net-next v1 0/8] xen-netback: support toeplitz
> hashing
> >>
> >> From: Paul Durrant 
> >> Date: Fri, 12 Feb 2016 11:07:50 +
> >>
> >> > Windows *requires* use of Teoplitz so your position completely rules
> >> > out being able to support receive side scaling in Windows PV
> >> > frontends on Linux kernel backends, not only for Xen but for any
> >> > other hypervisor, which I think is totally unreasonable.
> >>
> >> We have strong reason to believe that Toeplitz has properties that
> >> make it very weak if not exploitable, therefore doing software RSS
> >> with Jenkins is superior.
> >
> > I don't disagree, but there is really no choice of algorithm where a Windows
> frontend is concerned. My patches only add Toeplitz hashing into xen-
> netback according to the specification in xen's netif.h; the algorithm is not
> exposed for use by any other part of the kernel.
> 
> You are touching struct sk_buff for this. Changing such a core
> networking data structure just to satisfy a requirement of Windows
> seems like a long shot to me...

The patch to sk_buff is nothing to do with Toeplitz hashing. It's merely 
because I noticed that sk_buff was unable to store complete hash type 
information at the moment and that seems suboptimal. I've re-worded and resent 
that patch separately.

> 
> > If it would help I can add a module parameter to xen-netback to control
> advertising the option of the hash to frontends so that it can be globally
> disabled if it is deployed on host where there are no Windows guests.
> 
> Toeplitz is dog-slow to compute in software. Comparing your
> implementation to Jenkins hash (hash) it's about 12x slower (102 nsecs
> versus 8 nsecs for IPv4 on my system). Doing this for every packet
> seems like a non-starter to me. I suspect the majority use case for
> receive is simple uniform load balancing across the virtual queues in
> which case jhash will be perfectly fine. The case where it probably
> matters is if the Windows OS is trying to configure some non-uniform
> distribution (isolating a single flow for instance). To handle this
> case, you could implement a simple look up flow table to map a
> skb->hash to a Toeplitz hash, so that the Toeplitz hash only needs to
> be calculated one time for a flow (recomputed with some periodic
> timeout). This would be probabilistic though, so if really Windows
> requires the hash to be set correctly 100% of the time it won't work.
> 

I agree that Toeplitz is dog-slow to calculation in s/w. Keeping a cache of the 
N most recent flows and flushing it if the key changes (which is the only thing 
that's going to cause the hash to change) sounds like a good optimization. I'll 
certainly add that.

  Paul

> Tom
> 
> >
> >   Paul
___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing

[Tom Herbert]

On Fri, Feb 12, 2016 at 5:59 PM, Paul Durrant  wrote:
>> -Original Message-
>> From: David Miller [mailto:da...@davemloft.net]
>> Sent: 12 February 2016 16:42
>> To: Paul Durrant
>> Cc: net...@vger.kernel.org; xen-de...@lists.xenproject.org
>> Subject: Re: [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing
>>
>> From: Paul Durrant 
>> Date: Fri, 12 Feb 2016 11:07:50 +
>>
>> > Windows *requires* use of Teoplitz so your position completely rules
>> > out being able to support receive side scaling in Windows PV
>> > frontends on Linux kernel backends, not only for Xen but for any
>> > other hypervisor, which I think is totally unreasonable.
>>
>> We have strong reason to believe that Toeplitz has properties that
>> make it very weak if not exploitable, therefore doing software RSS
>> with Jenkins is superior.
>
> I don't disagree, but there is really no choice of algorithm where a Windows 
> frontend is concerned. My patches only add Toeplitz hashing into xen-netback 
> according to the specification in xen's netif.h; the algorithm is not exposed 
> for use by any other part of the kernel.

You are touching struct sk_buff for this. Changing such a core
networking data structure just to satisfy a requirement of Windows
seems like a long shot to me...

> If it would help I can add a module parameter to xen-netback to control 
> advertising the option of the hash to frontends so that it can be globally 
> disabled if it is deployed on host where there are no Windows guests.

Toeplitz is dog-slow to compute in software. Comparing your
implementation to Jenkins hash (hash) it's about 12x slower (102 nsecs
versus 8 nsecs for IPv4 on my system). Doing this for every packet
seems like a non-starter to me. I suspect the majority use case for
receive is simple uniform load balancing across the virtual queues in
which case jhash will be perfectly fine. The case where it probably
matters is if the Windows OS is trying to configure some non-uniform
distribution (isolating a single flow for instance). To handle this
case, you could implement a simple look up flow table to map a
skb->hash to a Toeplitz hash, so that the Toeplitz hash only needs to
be calculated one time for a flow (recomputed with some periodic
timeout). This would be probabilistic though, so if really Windows
requires the hash to be set correctly 100% of the time it won't work.

Tom

>
>   Paul

___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing

[David Miller]

From: Paul Durrant 
Date: Fri, 12 Feb 2016 10:13:17 +

> This patch series adds support for frontend-configurable toeplitz hashing
> in xen-netback (on the guest receive side). This support has been testing
> against a Windows frontend and has proven to be sufficient to pass the
> Microsoft HCK NDIS RSS tests.

We want less Toeplitz users, not more of them.  It is a more unsuitable
hash than jhash2.

I'm not applying these patches, sorry.

___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing

[Paul Durrant]

> -Original Message-
> From: netdev-ow...@vger.kernel.org [mailto:netdev-
> ow...@vger.kernel.org] On Behalf Of David Miller
> Sent: 12 February 2016 10:54
> To: Paul Durrant
> Cc: net...@vger.kernel.org; xen-de...@lists.xenproject.org
> Subject: Re: [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing
> 
> From: Paul Durrant 
> Date: Fri, 12 Feb 2016 10:13:17 +
> 
> > This patch series adds support for frontend-configurable toeplitz hashing
> > in xen-netback (on the guest receive side). This support has been testing
> > against a Windows frontend and has proven to be sufficient to pass the
> > Microsoft HCK NDIS RSS tests.
> 
> We want less Toeplitz users, not more of them.  It is a more unsuitable
> hash than jhash2.
> 
> I'm not applying these patches, sorry.

Windows *requires* use of Teoplitz so your position completely rules out being 
able to support receive side scaling in Windows PV frontends on Linux kernel 
backends, not only for Xen but for any other hypervisor, which I think is 
totally unreasonable.

  Paul

___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

[Xen-devel] [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing

[Paul Durrant]

This patch series adds support for frontend-configurable toeplitz hashing
in xen-netback (on the guest receive side). This support has been testing
against a Windows frontend and has proven to be sufficient to pass the
Microsoft HCK NDIS RSS tests.

For convenience my development branch is available at 
http://xenbits.xen.org/gitweb/?p=people/pauldu/linux.git;a=shortlog;h=refs/heads/rss18.

Patch #1 contains a small modification to struct sk_buff to use one more
bit's worth of space to enable full hasf information to be stored (as
opposed to simply whether a calculated hash is L4 or not).

Patch #2 re-imports the canonical netif.h from the Xen master branch at
git://xenbits.xen.org/xen.git. To minimize the diff it was post-processed
as detailed in the commit message.

Patch #3 fixes a short-coming in netback so that it can actually cope with
multiple extra_info fragments being passed from the frontend on the
guest transmit side.

Patch #4 is a trivial patch to reduce log spam from netback.

Patch #5 adds support for a new shared ring for control messages between
frontend and backend as detailed in the updated netif.h.

Patch #6 builds on patch #5 and adds support for messages passed from the
frontend to configure a toeplitz hash of packets on the guest receive side.

Patch #7 adds code to pass the hash calculated by netback to the frontend

Patch #8 adds code to take hashes calculated by the guest on its transmit
side and set the approprate values in the constructed socket buffer.

___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing

[Paul Durrant]

> -Original Message-
> From: David Miller [mailto:da...@davemloft.net]
> Sent: 12 February 2016 16:42
> To: Paul Durrant
> Cc: net...@vger.kernel.org; xen-de...@lists.xenproject.org
> Subject: Re: [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing
> 
> From: Paul Durrant 
> Date: Fri, 12 Feb 2016 11:07:50 +
> 
> > Windows *requires* use of Teoplitz so your position completely rules
> > out being able to support receive side scaling in Windows PV
> > frontends on Linux kernel backends, not only for Xen but for any
> > other hypervisor, which I think is totally unreasonable.
> 
> We have strong reason to believe that Toeplitz has properties that
> make it very weak if not exploitable, therefore doing software RSS
> with Jenkins is superior.

I don't disagree, but there is really no choice of algorithm where a Windows 
frontend is concerned. My patches only add Toeplitz hashing into xen-netback 
according to the specification in xen's netif.h; the algorithm is not exposed 
for use by any other part of the kernel.
If it would help I can add a module parameter to xen-netback to control 
advertising the option of the hash to frontends so that it can be globally 
disabled if it is deployed on host where there are no Windows guests.

  Paul

___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

Re: [Xen-devel] [PATCH net-next v1 0/8] xen-netback: support toeplitz hashing

[David Miller]

From: Paul Durrant 
Date: Fri, 12 Feb 2016 11:07:50 +

> Windows *requires* use of Teoplitz so your position completely rules
> out being able to support receive side scaling in Windows PV
> frontends on Linux kernel backends, not only for Xen but for any
> other hypervisor, which I think is totally unreasonable.

We have strong reason to believe that Toeplitz has properties that
make it very weak if not exploitable, therefore doing software RSS
with Jenkins is superior.

___
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel