[cpp-threads] Alternatives to SC

[Paul E. McKenney]

On Sun, Jan 14, 2007 at 11:00:12AM -0500, Doug Lea wrote:
> Peter Dimov wrote:
> >Doug Lea wrote:
> >Speaking of hazard pointers... as an aside, the two main problems with
> >turning an academic paper into a real C++ implementations are that (1)
> >most papers assume SC when giving the pseudocode, (2) most papers either
> >assume garbage collection, or don't mention the issue of memory
> >management at all. Even given SC atomics, the second problem remains.
> >Yet the discussion doesn't mention it at all. Do the proponents of "SC
> >atomics for the masses" also assume that they will only be usable in a
> >GC environment? :-) I simply don't see how a non-expert can reasonably
> >handle the memory management of a typical lock-free container, no matter
> >how sequentially consistent the atomics are.
> 
> Continuing your aside-mode: I agree that for C++, it would be great
> to have a pre-supplied library component or two to handle hazard
> pointers, because they are very hard to program. And secondarily
> because vendors might be able to supply special versions that exploit
> platform-level tricks (like cheats relying on pointer representations).
> Maybe you could propose a little API for these?

When I was beating my head against the wall attempting to construct an
RCU implementation suitable for Ingo Molnar's realtime Linux patchset,
one of the things I tried was hazard pointers.  This came pretty close
to working, and might actually work in other environments.  Here was the
mapping:

	rcu_read_lock() -- create a new context for hazard-pointer lifetime.

	rcu_dereference() -- allocate and point a hazard pointer at the
		referenced object.

	rcu_read_unlock() -- free up all hazard pointers created since
		the matching rcu_read_lock().

	call_rcu() -- queue the object for destruction once no hazard
		pointers reference it (perhaps destroy immediately).

	synchronize_rcu() -- wait for all current hazard pointers to
		be freed up.  This was needed in the Linux kernel, but
		might be possible to just leave out of a new API.

But this ran aground, and I eventually came up with the current per-CPU
counters approach.  Why did it run aground?

1.	Hazard pointers would have artificially long lifetimes, since
	they cannot be freed until the enclosing rcu_read_unlock() is
	reached.  This was a showstopper for small-memory embedded
	uses of Linux.

	In application space, one might be able to provide an
	rcu_donereference() or some such that frees individual hazard
	pointers, doing so would have posed ugly software-engineering
	problems in the kernel.  (I just removed this node from a
	global list and, in common code, am putting it onto another
	list.  Do I keep the hazard pointer?  Well, that depends on
	whether the destination list is public or private -- and that
	means that the public/private nature of the list must be wound
	down through multiple layers of code.  It just got too ugly.

2.	What if the hazard-pointer allocation in rcu_dereference() fails?
	Having rcu_dereference() be able to return an error instead
	of the pointer would greatly complicate code using RCU, so I
	rejected this approach.  One might instead require the caller
	to pass in the memory be be used to record the hazard pointer,
	but there are places where dynamic allocation is absolutely
	necessary -- and then the caller is once again stuck with handling
	memory-allocation failure.

3.	The hazard pointers themselves require memory, hence would not
	bring joy to the hearts of those running Linux on
	memory-constrained systems.

It is possible that some application environments may permit different
choices.

For whatever it is worth!!!

						Thanx, Paul