cds::urcu Namespace Reference

User-space Read-Copy Update (URCU) namespace. More...

Data Structures
class	dispose_thread
	Reclamation thread for general_threaded URCU. More...
class	exempt_ptr
	Exempt pointer for RCU. More...
class	gc< general_buffered< Buffer, Lock, Backoff > >
	User-space general-purpose RCU with deferred buffered reclamation. More...
class	gc< general_instant< Lock, Backoff > >
	User-space general-purpose RCU with immediate reclamation. More...
class	gc< general_threaded< Buffer, Lock, DisposerThread, Backoff > >
	User-space general-purpose RCU with special thread for deferred reclamation. More...
class	gc< signal_buffered< Buffer, Lock, Backoff > >
	User-space signal-handled RCU with deferred buffered reclamation. More...
class	general_buffered
	User-space general-purpose RCU with deferred (buffered) reclamation. More...
class	general_buffered_stripped
	User-space general-purpose RCU with deferred (buffered) reclamation (stripped version) More...
struct	general_buffered_tag
	Tag for general_buffered URCU. More...
class	general_instant
	User-space general-purpose RCU with immediate reclamation. More...
class	general_instant_stripped
	User-space general-purpose RCU with immediate reclamation (stripped version) More...
struct	general_instant_tag
	Tag for general_instant URCU. More...
struct	general_purpose_rcu
	General-purpose URCU type. More...
class	general_threaded
	User-space general-purpose RCU with deferred threaded reclamation. More...
class	general_threaded_stripped
	User-space general-purpose RCU with deferred threaded reclamation (stripped version) More...
struct	general_threaded_tag
	Tag for general_threaded URCU. More...
class	raw_ptr
	Raw pointer to node of RCU-based container. More...
class	rcu_deadlock
	Exception "RCU deadlock detected". More...
class	signal_buffered
	User-space signal-handled RCU with deferred (buffered) reclamation. More...
class	signal_buffered_stripped
	User-space signal-handled RCU with deferred (buffered) reclamation (stripped version) More...
struct	signal_buffered_tag
	Tag for signal_buffered URCU. More...
struct	signal_handling_rcu
	Signal-handling URCU type. More...

Typedefs
typedef cds::gc::details::retired_ptr	retired_ptr
typedef cds::gc::details::free_retired_ptr_func	free_retired_ptr_func
	Pointer to function to free (destruct and deallocate) retired pointer of specific type.

Detailed Description

User-space Read-Copy Update (URCU) namespace.

This namespace contains declarations for different types of Read-Copy Update (RCU) synchronization primitive and data structures developed for RCU. In libcds RCU is used as garbage collector.

Source papers:

• [2009] M.Desnoyers "Low-Impact Operating System Tracing" PhD Thesis, Chapter 6 "User-Level Implementations of Read-Copy Update"
• [2011] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "User-Level Implementations of Read-Copy Update"
• [2012] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "Supplementary Material for User-Level Implementations of Read-Copy Update"

Informal introduction to user-space RCU

[From Desnoyer's papers] RCU is a synchronization mechanism that was added to the Linux kernel in October of 2002. RCU achieves scalability improvements by allowing reads to occur concurrently with updates. In contrast to conventional locking primitives that ensure mutual exclusion among concurrent threads regardless of whether they be readers or updaters, or with reader-writer locks that allow concurrent reads but not in the presence of updates, RCU supports concurrency between multiple updaters and multiple readers. RCU ensures that data are not freed up until all pre-existing critical sections complete. RCU defines and uses efficient and scalable mechanisms for deferring reclamation of old data. These mechanisms distribute the work among read and update paths in such a way as to make read paths extremely fast.

RCU readers execute within RCU read-side critical sections. Each such critical section begins with rcu_read_lock(), ends with rcu_read_unlock() (in libcds these primitives are the methods of GC class and are usually called access_lock and access_unlock respectively). Read-side critical sections can be nested. The performance benefits of RCU are due to the fact that rcu_read_lock() and rcu_read_unlock() are exceedingly fast.

When a thread is not in an RCU read-side critical section, it is in a quiescent state. A quiescent state that persists for a significant time period is an extended quiescent state. Any time period during which every thread has been in at least one quiescent state is a grace period; this implies that every RCU read-side critical section that starts before a grace period must end before that grace period does. Distinct grace periods may overlap, either partially or completely. Any time period that includes a grace period is by definition itself a grace period. Each grace period is guaranteed to complete as long as all read-side critical sections are finite in duration; thus even a constant flow of such critical sections is unable to extend an RCU grace period indefinitely.

Suppose that readers enclose each of their data-structure traversals in an RCU read-side critical section. If an updater first removes an element from such a data structure and then waits for a grace period, there can be no more readers accessing that element. The updater can then carry out destructive operations, for example freeing the element, without disturbing any readers.

The RCU update is split into two phases, a removal phase and a reclamation phase. These two phases must be separated by a grace period, for example via the synchronize_rcu() primitive, which initiates a grace period and waits for it to finish. During the removal phase, the RCU update removes elements from a shared data structure. The removed data elements will only be accessible to read-side critical sections that ran concurrently with the removal phase, which are guaranteed to complete before the grace period ends. Therefore the reclamation phase can safely free the data elements removed by the removal phase.

Desnoyers describes several classes of user-space RCU implementations:

• The Quiescent-State-Based Reclamation (QSBR) RCU implementation offers the best possible read-side performance, but requires that each thread periodically calls a function to announce that it is in a quiescent state, thus strongly constraining the application design. This type of RCU is not implemented in libcds.
• The general-purpose RCU implementation places almost no constraints on the application's design, thus being appropriate for use within a general-purpose library, but it has relatively higher read-side overhead. The libcds contains several implementations of general-purpose RCU: general_instant, general_buffered, general_threaded.
• signal_buffered: the signal-handling RCU presents an implementation having low read-side overhead and requiring only that the application give up one POSIX signal to RCU update processing.

Note

The signal-handled RCU is defined only for UNIX-like systems, not for Windows.

RCU implementation type

There are several internal implementation of RCU (all declared in cds::urcu namespace):

• general_instant - general purpose RCU with immediate reclamation
• general_buffered - general purpose RCU with deferred (buffered) reclamation
• general_threaded - general purpose RCU with special reclamation thread
• signal_buffered - signal-handling RCU with deferred (buffered) reclamation

You cannot create an object of any of those classes directly. Instead, you should use wrapper classes. The wrapper simplifies creation and usage of RCU singleton objects and has the reacher interface that combines interfaces of wrapped class i.e. RCU global part like synchronize, and corresponding RCU thread-specific interface like access_lock, access_unlock and retire_ptr.

There are several wrapper classes (all declared in cds::urcu namespace)

• gc<general_instant> - general purpose RCU with immediate reclamation, include file <cds/urcu/general_instant.h>
• gc<general_buffered> - general purpose RCU with deferred (buffered) reclamation, include file <cds/urcu/general_buffered.h>
• gc<general_threaded> - general purpose RCU with special reclamation thread include file <cds/urcu/general_threaded.h>
• gc<signal_buffered> - signal-handling RCU with deferred (buffered) reclamation include file <cds/urcu/signal_buffered.h>

Any RCU-related container in libcds expects that its RCU template parameter is one of those wrapper.

For simplicity, in some algorithms instead of using RCU implementation type you should specify corresponding RCU tags (all declared in cds::urcu namespace):

• general_instant_tag - for general_instant
• general_buffered_tag - for general_buffered
• general_threaded_tag - for general_threaded
• signal_buffered_tag - for signal_buffered

Performance

As a result of our experiments we can range above RCU implementation in such order, from high to low performance:

• gc<general_buffered> - high
• gc<general_threaded>
• gc<signal_buffered>
• gc<general_instant> - low

This estimation is very rough and depends on many factors: type of payload - mostly read-only (seeking) or read-write (inserting and deleting), - a hardware, your application, and so on.

How to use

Usually, in your application you use only one type of RCU that is the best for your needs. However, the library allows to apply several RCU singleton in one application. The only limitation is that only one object of each RCU type can be instantiated. Since each RCU type is a template class the creation of two object of one RCU type class with different template arguments is an error and is not supported. However, it is correct when your RCU objects relates to different RCU types.

In libcds, many GC-based ordered list, set and map template classes have RCU-related specializations that hide the RCU specific details.

RCU GC is initialized in usual way: you should declare an object of type cds::urcu::gc< RCU_type >, for example:

#include <cds/urcu/general_buffered.h>

typedef cds::urcu::gc< cds::urcu::general_buffered<> >    rcu_gpb;

int main() {
    // Initialize libcds
    cds::Initialize();
    {
        // Initialize general_buffered RCU
        rcu_gpb   gpbRCU;

        // If main thread uses lock-free containers
        // the main thread should be attached to libcds infrastructure
        cds::threading::Manager::attachThread();

        // Now you can use RCU-based containers in the main thread
        //...
    }
    // Terminate libcds
    cds::Terminate();
}

Each thread that deals with RCU-based container should be initialized first:

#include <cds/urcu/general_buffered.h>
int myThreadEntryPoint(void *)
{
    // Attach the thread to libcds infrastructure
    cds::threading::Manager::attachThread();

    // Now you can use RCU-based containers in the thread
    //...

    // Detach thread when terminating
    cds::threading::Manager::detachThread();
}

Typedef Documentation

retired_ptr

typedef cds::gc::details::retired_ptr cds::urcu::retired_ptr

Retired pointer, i.e. pointer that ready for reclamation