netdev - RE: [PATCH 2/6] rhashtable: Use a single bucket lock for sibling buckets

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] [day] [month] [year] [list]

Date:	Thu, 26 Feb 2015 14:38:47 +0000
From:	David Laight <David.Laight@...LAB.COM>
To:	'Thomas Graf' <tgraf@...g.ch>,
	"davem@...emloft.net" <davem@...emloft.net>
CC:	"netdev@...r.kernel.org" <netdev@...r.kernel.org>,
	"herbert@...dor.apana.org.au" <herbert@...dor.apana.org.au>,
	"ying.xue@...driver.com" <ying.xue@...driver.com>
Subject: RE: [PATCH 2/6] rhashtable: Use a single bucket lock for sibling
 buckets

From: Thomas Graf
> Sent: 05 February 2015 01:04
> rhashtable currently allows to use a bucket lock per bucket. This
> requires multiple levels of complicated nested locking because when
> resizing, a single bucket of the smaller table will map to two
> buckets in the larger table. So far rhashtable has explicitly locked
> both buckets in the larger table.

> By excluding the highest bit of the hash from the bucket lock map and
> thus only allowing locks to buckets in a ratio of 1:2, the locking

Surely you mean 1:2^n ??

> can be simplified a lot without losing the benefits of multiple locks.
> Larger tables which benefit from multiple locks will not have a single
> lock per bucket anyway.

I'd presume that for a very large table the number of locks required
is related to the number of cpus rather than the table size itself.
Once the hash chains are short the lock is less likely to be contended
anyway. My brain can't think through the cache implications though.

This makes me think that you never really need to increase the number
of locks (which is probably quite tricky), and definitely don't need
to reduce the number of locks (probably harder).
This would mean that the table can't get smaller than the number of locks.
This in itself isn't really an issue.

	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