[ltt-dev] Userspace RCU TODO list

[Josh Triplett]

On Fri, Jun 18, 2010 at 02:53:31PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > I do have a few
> > simple RCU-protected stack/queue things.
> 
> Yep, that would be useful. Ideally if we can use read locks to deal with ABA
> problems, thus being able to enqueue and dequeue locklessly, that would be
> ideal. I have a lock-free queue implementation from Paolo Bonzini around. I'll
> push it in a urcu repo branch: "lflist".

That sounds quite interesting; we haven't combined non-blocking
operations with RCU before.

> > Josh Triplett has done some
> > resizable hash-table work, as has Herbert Xu.
> 
> Yep, that would be interesting to add. I just wonder about their use of
> spinlocks in there for updates (as far as I remember Josh did use locks for
> updates). I think hash tables could benefit from using the read lock on the
> update-side to deal with ABA without locking.

My work definitely doesn't do lockless updates, just lockless reads.  It
does, however, manage to resize with concurrent readers.

> The urcu/ht branch implements some of these ideas. Again, this is a development
> branch, so don't use it for production yet! In this scheme, resizes are
> protected with mutexes (and when resize are ongoing, all updates are waiting),
> but in the general case, an ABA-safe lockless scheme is used for insertion,
> steal and delete.

OK, so resize still blocks resizes and updates, and your lockless
algorithm just applies to updates.  That makes sense.

I've given some thought to resizing with concurrent updates, but
"thought" doesn't quite translate to "algorithm" yet. :)

> (Note: Josh, I am not sure my emails from @efficios.com will get to the
> rp-private mailing list. Can you add an exception ? Thanks!)

Done.