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

[Mathieu Desnoyers]

* Paolo Bonzini (pbonzini at redhat.com) wrote:
> On 07/12/2010 06:32 AM, Mathieu Desnoyers wrote:
>> So, I think I found a neat way to handle lock-free rcu queues with
>> reference counting instead. Note that the "dummy" node is really
>> needed, otherwise we end up in situations where the "empty" queue is
>> hard to deal with racelessly. FYI, the ABA problem is dealt with by
>> using rcu read locks. Comments on the code below are very welcome.
>
> There is a problem with reference counting: the neat part of my  
> implementation was that I only needed to do a grace period after a few  
> thousands allocations.  As it is now, the implementation of urcu_ref.h  
> would synchronize on every allocation, which obviously kills performance.

Nope, we don't need to do that :-) Thanks to the defer_rcu() mechanism, we can
batch grace periods. So the typical use-case is:

release_fct(struct urcu_ref *ref)
{
        struct rcu_lfq_node *node = container_of(ref, struct rcu_lfq_node, ref);
        defer_rcu(free, node);
}

enqueuer:
  node = malloc()
  enqueue(q, node)

dequeuer:
  node = dequeue(q, release_fct);
  use node...
  urcu_ref_put(&node->ref, release_fct);

Typically, defer_rcu() will do a synchronize_rcu() only once every 4096
invocations from a given thread, or each 100ms (whichever comes first).

>
> So, maybe a page-slicing allocator can be bundled with URCU that layers  
> my technique on top of some other allocator.  Being on vacation I won't  
> do that for a couple of weeks, but I can do that if there is interest.
>
> Otherwise, it looks great.

Thanks for taking time to look into that. Enjoy your vacation!

Mathieu

>
> Paolo

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com