linux-kernel - Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct flow

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CALx6S35PbTHF7nY0ugtxCUkc5kUmMYAyuy6ZM34bZ9v42nDudg@mail.gmail.com>
Date:	Thu, 14 Jan 2016 09:14:12 -0800
From:	Tom Herbert <tom@...bertland.com>
To:	Haiyang Zhang <haiyangz@...rosoft.com>
Cc:	David Miller <davem@...emloft.net>,
	"vkuznets@...hat.com" <vkuznets@...hat.com>,
	"netdev@...r.kernel.org" <netdev@...r.kernel.org>,
	KY Srinivasan <kys@...rosoft.com>,
	"devel@...uxdriverproject.org" <devel@...uxdriverproject.org>,
	"linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
	"eric.dumazet@...il.com" <eric.dumazet@...il.com>
Subject: Re: [PATCH net-next] hv_netvsc: don't make assumptions on struct
 flow_keys layout

> I have done a comparison of the Toeplitz v.s. Jenkins Hash algorithms,
> and found that the Toeplitz provides much better distribution of the
> connections into send-indirection-table entries. See the data below --
> showing how many TCP connections are distributed into each of the
> sixteen table entries. The Toeplitz hash distributes the connections
> almost perfectly evenly, but the Jenkins hash distributes them unevenly.
> For example, in case of 64 connections, some entries are 0 or 1, some
> other entries are 8. This could cause too many connections in one VMBus
> channel and slow down the throughput. This is consistent to our test
> which showing slower performance while using the generic skb_get_hash
> (Jenkins) than using Toeplitz hash (see perf numbers below).
>
>
> #connections:32:
> Toeplitz:2,2,2,2,2,1,2,2,2,2,2,3,2,2,2,2,
> Jenkins:3,2,2,4,1,1,0,2,1,1,4,3,2,5,1,0,
> #connections:64:
> Toeplitz:4,4,5,4,4,3,4,4,4,4,4,4,4,4,4,4,
> Jenkins:4,5,4,6,3,5,0,6,1,2,8,3,6,8,2,1,
> #connections:128:
> Toeplitz:8,8,8,8,8,7,9,8,8,8,8,8,8,8,8,8,
> Jenkins:8,12,10,9,7,8,3,10,6,8,9,8,10,11,6,3,
>
These results for Toeplitz are not plausible. Given random input you
cannot expect any hash function to produce such uniform results. I
suspect either your input data is biased or how your applying the hash
is.

When I run 64 random IPv4 3-tuples through Toeplitz and Jenkins I get
something more reasonable:

Toeplitz
Buckets: 3 7 4 5 3 6 2 6 2 4 4 5 4 3 2 4

Jenkins
Buckets: 6 7 4 4 3 2 6 3 1 4 3 5 5 4 4 3

> Throughput (Gbps) comparison:
> #conn           Toeplitz        Jenkins
> 32              26.6            23.2
> 64              32.1            23.4
> 128             29.1            24.1
>
> For long term solution, I think we should put the Toeplitz hash as
> another option to the generic hash function in kernel... But, for the
> time being, can you accept this patch to fix the assumptions on
> struct flow_keys layout?
>
Toeplitz is about a 100x more expensive to compute in the CPU than
Jenkins, we can get that down to 50x by precomputing a bunch of lookup
tables for a given key but that is at the expense of memory. Besides
that, there is a fair amount of analysis already showing that Jenkins
hash provides a good distribution and has good enough (though not
great) Avalanche effect. Probably the only reason we would need
Toeplitz in SW is if we wanted to match a computation being done by
HW.

One hash that might be better than Jenkins is CRC. This seems to have
good uniformity and Avalanche effect, and by using crc32 instruction
it seems be a little faster than running Jenkins hash.

Tom

> Thanks,
> - Haiyang
>