linux-kernel - Re: [PATCH] add b+tree library

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:	Mon, 12 Jan 2009 08:20:32 -0800
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Jörn Engel <joern@...fs.org>
Cc:	Peter Zijlstra <peterz@...radead.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Theodore Tso <tytso@....edu>, Andi Kleen <andi@...stfloor.org>,
	Johannes Berg <johannes@...solutions.net>,
	KOSAKI Motohiro <kosaki.motohiro@...fujitsu.com>,
	Linux Kernel list <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] add b+tree library

On Sun, Jan 11, 2009 at 09:30:34AM +0100, Jörn Engel wrote:
> On Sun, 11 January 2009 00:57:20 +0100, Peter Zijlstra wrote:
> > 
> > B-tree's however have one thing over RB-trees, B-trees can be made
> > RCU-safe whereas RB-trees cannot be -- the only problem is that Joern's
> > doesn't do that.
> 
> And yours doesn't support multiple key sizes afaics.  I don't mind
> using your version as a basis, so long as my^Wboth requirements get
> fulfilled. ;)
> 
> Do you see a problem combining rcu with keys being an array of unsigned
> long?

There is a theory vs. practice issue here.  In theory, you could make any
dynamically allocated search structure RCU-searchable by copy-updating
the entire structure on each update.  In many cases, you only have to
replace a fairly small part.  In practice, the question is whether your
read-to-update ratio is large enough to make it a win.

The main potential issue with keys being an array of unsigned long is
that it is no longer possible to atomically rewrite a given key in place.
The usual ways to work around this are:

1.	Replace each key entry with a pointer to the array of unsigned
	longs, so that you can atomically rewrite the pointer.  The
	downside of this approach is the extra cache line accessed per
	key scanned.  The upside of this approach is that you might
	be able to share code with Peter's tree by using a comparison
	function (if NULL, just compare the entries directly) or some
	other similar trick.

2.	Place the array of unsigned longs directly in the structure, but
	copy-update the entire node rather than rewriting keys in place.
	This has better cache locality, but makes it more difficult to
	share code with the small-key variant.

There are probably other tricks as well.

							Thanx, Paul
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/