netdev - Re: Ottawa and slow hash-table resize

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: <20150223191201.GA4355@cloud>
Date:	Mon, 23 Feb 2015 11:12:01 -0800
From:	josh@...htriplett.org
To:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Cc:	alexei.starovoitov@...il.com, herbert@...dor.apana.org.au,
	tgraf@...g.ch, kaber@...sh.net, davem@...emloft.net,
	ying.xue@...driver.com, netdev@...r.kernel.org,
	netfilter-devel@...r.kernel.org
Subject: Re: Ottawa and slow hash-table resize

On Mon, Feb 23, 2015 at 10:49:04AM -0800, Paul E. McKenney wrote:
> Hello!
> 
> Alexei mentioned that there was some excitement a couple of weeks ago in
> Ottawa, something about the resizing taking forever when there were large
> numbers of concurrent additions.  One approach comes to mind:
> 
> o	Currently, the hash table does not allow additions concurrently
> 	with resize operations.  One way to allow this would be to
> 	have the addition operations add to the new hash table at the
> 	head of the lists.  This would clearly require also updating the
> 	pointers used to control the unzip operation.

In theory, resizes should only take the locks for the buckets they're
currently unzipping, and adds should take those same locks.  Neither one
should take a whole-table lock, other than resize excluding concurrent
resizes.  Is that still insufficient?

> o	Count the number of entries added during the resize operation.
> 	Then, at the end of the resize operation, if enough entries have
> 	been added, do a resize, but by multiple factors of two if
> 	need be.

Yeah, the add/remove statistics used for tracking would need some
special handling to avoid being a table-wide bottleneck.

- Josh Triplett
--
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