cds  2.2.0
cds::urcu Namespace Reference

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

Data Structures

class  dispose_thread
 Reclamation thread for general_threaded and signal_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  gc< signal_threaded< Buffer, Lock, DisposerThread, Backoff > >
 User-space signal-handled RCU with special thread for deferred 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...
 
class  signal_threaded
 User-space signal-handled RCU with deferred threaded reclamation. More...
 
class  signal_threaded_stripped
 User-space signal-handled RCU with deferred threaded reclamation (stripped version) More...
 
struct  signal_threaded_tag
 Tag for signal_threaded URCU. 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"

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.
  • 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. The libcds contains several implementations if signal-handling RCU: signal_buffered, signal_threaded.
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):

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>
  • gc<signal_threaded> - signal-handling RCU with special reclamation thread include file <cds/urcu/signal_threaded.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):

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<signal_threaded>
  • 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.

Note
If you want to use signal_buffered and signal_threaded RCU in your application simultaneously, you should specify different signal number for each signal-handled RCU type on construction time, for example, SIGUSR1 and SIGUSR2 respectively. By default, both signal-handled RCU implementation share SIGUSR1 signal and cannot be applied together.

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

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


cds 2.2.0 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Wed Jan 4 2017 08:50:07 by Doxygen 1.8.12