User-space Read-Copy Update (URCU) namespace. More...
|Reclamation thread for |
|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...|
|User-space general-purpose RCU with deferred (buffered) reclamation. More...|
|User-space general-purpose RCU with deferred (buffered) reclamation (stripped version) More...|
|Tag for general_buffered URCU. More...|
|User-space general-purpose RCU with immediate reclamation. More...|
|User-space general-purpose RCU with immediate reclamation (stripped version) More...|
|Tag for general_instant URCU. More...|
|General-purpose URCU type. More...|
|User-space general-purpose RCU with deferred threaded reclamation. More...|
|User-space general-purpose RCU with deferred threaded reclamation (stripped version) More...|
|Tag for general_threaded URCU. More...|
|Raw pointer to node of RCU-based container. More...|
|Exception "RCU deadlock detected". More...|
|User-space signal-handled RCU with deferred (buffered) reclamation. More...|
|User-space signal-handled RCU with deferred (buffered) reclamation (stripped version) More...|
|Tag for signal_buffered URCU. More...|
|Signal-handling URCU type. More...|
|User-space signal-handled RCU with deferred threaded reclamation. More...|
|User-space signal-handled RCU with deferred threaded reclamation (stripped version) More...|
|Tag for signal_threaded URCU. More...|
|Pointer to function to free (destruct and deallocate) retired pointer of specific type. |
User-space Read-Copy Update (URCU) namespace.
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
libcds these primitives are the methods of GC class and are usually called
access_unlock respectively). Read-side critical sections can be nested. The performance benefits of RCU are due to the fact that
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:
libcdscontains several implementations of general-purpose RCU: general_instant, general_buffered, general_threaded.
libcdscontains several implementations if signal-handling RCU: signal_buffered, signal_threaded.
There are several internal implementation of RCU (all declared in
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
Any RCU-related container in
libcds expects that its
RCU template parameter is one of those wrapper.
As a result of our experiments we can range above RCU implementation in such order, from high to low performance:
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.
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.
signal_threadedRCU in your application simultaneously, you should specify different signal number for each signal-handled RCU type on construction time, for example,
SIGUSR2respectively. By default, both signal-handled RCU implementation share
SIGUSR1signal and cannot be applied together.
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:
Each thread that deals with RCU-based container should be initialized first:
|typedef cds::gc::details::retired_ptr cds::urcu::retired_ptr|