Read-copy-update (RCU)

Read-copy-update is strong in multithreading environments where a data structure is read almost exclusively but rarely written.

First of all, what is RCU? The excellent Wikipedia page on Read-copy-update provides a good introduction:

In computer science, read-copy-update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structures (e.g., linked lists, trees, hash tables).^[1]

Whenever a thread is inserting or deleting elements of data structures in shared memory, all readers are guaranteed to see and traverse either the older or the new structure, therefore avoiding inconsistencies (e.g., dereferencing null pointers).^[1]

It is used when performance of reads is crucial and is an example of space–time tradeoff, enabling fast operations at the cost of more space. This makes all readers proceed as if there were no synchronization involved, hence they will be fast, but also making updates more difficult.

The name RCU was coined by the writer’s workflow. It first reads the current data, copies it to the new data, and then updates the current data.

Proposal P2545R4 provides three use cases for RCU, comparing them with reader-writer locks.

Three Use Cases

The three use cases compare reader-writer locks. with intrusive, non-intrusive, and synchronous RCU.

Intrusive RCU

Non-Intrusive RCU

Synchronous RCU

The main difference between intrusive and non-intrusive RCU is that in the intrusive case, Data is derived directly from the class struct Data : std::rcu_obj_base<Data>. This technique, in which a template has itself as a parameter, is known as the Curiously Recurring Template Pattern (CRTP). On the reader side, std::scoped_lock l(std::rcu_default_domain()) is used. On the writer side, either retire() or std::rcu_synchronize() is used.

This raises the question: when should similar techniques such as atomic shared pointers, read-write locks, hazard pointers, and RCU be used? The Proposal P2545R4 provides a simple rule: As a very rough rule of thumb, Hazard Pointers can be considered to be a scalable replacement for reference counters and RCU can be considered to be a scalable replacement for reader-writer locking. A high-level comparison of reference counting, Hazard Pointers, and RCU is displayed in Table 1.

Here is Table 1:

To conclude this article, here is the interface of RCU.

Interface

The interface consists of two classes, rcu_obj_base and rcu_domain and four functions, rcu_default_domain, rcu_synchronize, rcu_barrier, and rcu_retire.

cppreference provides a concise description:

Classes

• rcu_obj_base: allows an object to be protected by RCU
• rcu_domain: provides regions of RCU protection

Functions

• rcu_default_domain: returns a reference to a static-duration object of type std::rcu_domain
• rcu_synchronize: blocks until a protection region unlocks on a RCU domain
• rcu_barrier: may evaluate scheduled operations on a RCU domain and blocks until all preceding evaluations are complete
• rcu_retire: schedules the evaluation of a specified function on a RCU domain, potentially allocating memory, and invoking scheduled evaluations

What’s next?

The Data-parallel types (SIMD) library provides data-parallel types and operations on them. I will take a closer look at this library in my next article.