[ltt-dev] [rp-private] [RFC] Lock-free RCU queue for userspace RCU library

[Paul E. McKenney]

On Fri, Jul 16, 2010 at 05:04:39PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:

[ . . . ]

> > Given the above implementation, the code for S2 must do something
> > like the following:
> > 
> > 	for (;;) {
> > 		while (np = rcu_lfq_dequeue(&Q1, freenode)) {
> > 			do_something_with(np);
> > 			np1 = copy_node(np);
> > 			rcu_lfq_enqueue(&Q2, np1);
> > 			urcu_ref_put(np);
> > 		}
> > 	}
> > 
> > Yes, you can reduce the copy overhead by having np and np1 reference
> > bare nodes with a pointer to the real data, so only a minimal amount
> > of data need be copied.
> 
> This is where I'd like to come up with a clever scheme to handle cascading
> through cascaded refcounting rather than do the copy. I think it might be
> doable. But it does not come to my mind at this very moment, which is busy
> packing and organising my vacation! ;) I'll be offline for 2 weeks starting this
> evening, back on August 2nd.

That would be very interesting!  I know of the following schemes, each
with restrictions:

o	Use a circular array of pointers to the messages.  This works
	quite well, but handles only concurrency between a single
	enqueuer and a single dequeuer.

o	Put all of the nodes in a big array, and use indexes in place
	of pointers.  Then keep a generation number with the pointer,
	and adapt the usual DCAS algorithms.  This works as long as
	the generation number cannot overflow -- perhaps due to forcing
	a wait for grace period upon overflow.

o	Just use locks on both ends with priority boosting.  If you
	have FIFO locks and priority boosting, it works fairly well
	for real-time use, even though it isn't lock-free.  Or even
	obstruction-free.

There are probably others, but these come to mind immediately.

							Thanx, Paul