Re: Userspace RCU+rtth hack (was Re: [patch 3/3] radix-tree: RCU lockless readside)

["Paul E. McKenney" <paulmck@us.ibm.com>]

On Thu, Jun 22, 2006 at 08:23:43PM +0200, Nick Piggin wrote:
> 
> Just out of interest, attached is my userspace RCU implementation
> and RCU radix-tree concurrent tests for Andrew Morton's radix-tree
> test harness.
> 
> The RCU implementation is only 100 lines. Awful performance, of
> course, but I've stretched the rcu_read_lock/unlock over large
> periods so that we can get full concurrency at the cost of a
> bit of memory build up. And it still seems to catch use-after
> RCU-freed errors pretty easily.

Interesting approach!  One caution -- this approach can result in
RCU callbacks being invoked in the context of either call_rcu() or
rcu_read_unlock().  In some legitimate uses of RCU, this can result
in deadlock.  See Documentation/RCU/UP.txt for more info.

One solution is to have some other context (perhaps just a separate
pthread, given that performance is not critical) to invoke the callbacks.

Another user-level RCU implementation is available here:

	http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz

Tom and his major prof unfortunately felt the need to rename
everything.  Here is a decoder ring:

	Linux Name			perflab name

	rcupdate.c			qsbr.c
	rcupdate.h			qsbr.h
	call_rcu()			free_node_later()
	rcu_read_lock()			N/A
	rcu_read_unlock()		N/A

The perflab package invokes callbacks from the quiescent state
(called quiescent_state(), appropriately enough).

FWIW, "QSBR" stands for quiescent-state-based reclamation.

I have a few user-mode implementations myself, but the lawyers won't
let me release them.  :-(

> Question - our kernel's call_rcu implies a smp_wmb, right? Because
> that did catch me out initially, because I initially had no barrier
> to prevent the freeing of the object becoming visible before
> removal of its last reference becoming visible (fixed by adding
> smp_wmb() in my call_rcu).

No and yes...  The kernel's call_rcu() itself does not have an smp_wmb(),
but the Classic RCU grace-period mechanism forces a memory barrier on each
CPU as part of grace-period detection -- which is why rcu_read_lock()
and rcu_read_unlock() don't need memory barriers.  Looks like your need
for an smp_wmb() in call_rcu() itself is due to the fact that you can
execute callbacks in the context of the call_rcu() itself.

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