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

Date:	Mon, 23 Feb 2015 10:49:04 -0800
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	alexei.starovoitov@...il.com, herbert@...dor.apana.org.au,
	tgraf@...g.ch, kaber@...sh.net, davem@...emloft.net,
	ying.xue@...driver.com
Cc:	netdev@...r.kernel.org, netfilter-devel@...r.kernel.org,
	josh@...htriplett.org
Subject: Ottawa and slow hash-table resize

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.

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.

This should allow the table to take arbitrarily large numbers of updates
during a resize operation.  There are some other possibilities if this
approach does not work out.

Thoughts?

							Thanx, Paul

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