Re: rcu-refcount stacker performance

[Joe Seigh <jseigh_02@xemaps.com>]

serue@us.ibm.com wrote:
> Quoting Paul E. McKenney (paulmck@us.ibm.com):
> > OK, but in the above case, "do something" cannot be sleeping, since
> > it is under rcu_read_lock().
>
>
> Oh, but that's not quite what the code is doing, rather it is doing:
>
> 	rcu_read_lock
> 	while get next element from list
> 		inc element.refcount
> 		rcu_read_unlock
> 		do something
> 		rcu_read_lock
> 		dec refcount
> 	rcu_read_unlock

I've been experimenting with various lock-free methods in user space, which
is preemptive.   Stuff like RCU, RCU+SMR which I've mentioned before,
and some atomically thread-safe reference counting.  I have a proxy
GC based on the latter called APPC (atomic pointer proxy collector).
Basically you use a proxy refcounted object for the whole list
rather than every element in the list.  Before you access the list,
you increment the refcount of the proxy object, and afterwards you
decrement it.  One interlocked instruction for each so performance
wise it looks like a reader lock which never blocks.

Writers enqueue deleted nodes on the collector object and then
push a new collector object in place.

The collector objects look like


   proxy_anchor -> c_obj <- c_obj <- c_obj
                                      ^
                                      | reader

The previous collector objects are back linked so when a reader
thread releases it, all unreference collector objects have
deallocation performed on them and attached nodes.

A bit sketchy.  You can see a working example of this using
C++ refcounted pointers (which can't be used in the kernel
naturally, you'll have to implement your own) at
http://atomic-ptr-plus.sourceforge.net/

--
Joe Seigh

-
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/