netdev - RE: [v1 PATCH 1/14] rhashtable: Remove shift from bucket

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]

Date:	Tue, 17 Mar 2015 12:13:42 +0000
From:	David Laight <David.Laight@...LAB.COM>
To:	"'tgraf@...g.ch'" <tgraf@...g.ch>,
	Herbert Xu <herbert@...dor.apana.org.au>
CC:	David Miller <davem@...emloft.net>,
	"netdev@...r.kernel.org" <netdev@...r.kernel.org>,
	Eric Dumazet <eric.dumazet@...il.com>
Subject: RE: [v1 PATCH 1/14] rhashtable: Remove shift from bucket_table

From: Thomas Graf 
> Sent: 17 March 2015 11:58
...
> > Do you really want to double the table size when 0.1% of the buckets
> > have a chain length > 4 but still < 16?
> 
> If we constantly hit that bucket because we are handling just a few
> TCP flows it would be worth to double the size & rehash to avoid the
> additional cache misses of the linked list.
> 
> Although a limit of 4 would be too high. Ideally we should resize and
> rehash when we add the 2nd entry to a bucket to stay < 100% utilization.
> It seems likely though that we'll always have a bucket with >=2
> entries so we would end up constantly doubling and rehashing. This is
> the only thing that speaks for a table wide nelems counters in my
> opinion.

I think you are seriously overestimating the 'efficiency' of the hash function.
And not doing the 'birthday paradox' maths at all.

The only way you'll get a 'hash' that good is if you can pick the input
value in order to generate a perfect hash.
However you aren't going to manage that for inbound TCP connections since
none of the inputs to the hash can be chosen by the listening system
(unless IPv6 has something than can help you).

You may have to live with a few % of the items being on long chains.
Maybe count the number of items on chains longer than (say) 4 and
rehash or increase the table size if this exceeds a few % of the
table size.
(Or count the number of items that are further than 4 from the start
of the hash chain.)

	David

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html