Read-copy-update
Read-copy-update (RCU) is a synchronization mechanism optimized for multi-threaded environments where read operations vastly outnumber updates, allowing concurrent readers to access shared data structures without acquiring locks or blocking writers.[1] In RCU, readers demarcate their critical sections using lightweight primitives like rcu_read_lock() and rcu_read_unlock(), which impose minimal overhead, often none beyond compiler barriers.[2] Writers, in contrast, copy the affected data structure, apply modifications to the copy, and use atomic operations such as rcu_assign_pointer() to update references to the new version, while deferring reclamation of the old version until a "grace period" elapses—ensuring all pre-existing readers have completed.[1] This approach splits updates into removal and reclamation phases, enabling high scalability and performance in read-mostly workloads.[2]
RCU was co-invented by Paul E. McKenney and John D. Slingwine in the mid-1990s as a solution to concurrency problems in shared-memory systems, with its foundational concepts detailed in early publications exploring execution history for synchronization.[3] It was integrated into the Linux kernel during the 2.5 development series around 2002, initially to enhance efficiency in components like the directory-entry cache (dcache).[1] Since then, RCU has evolved into a core kernel facility, maintained primarily by McKenney, and is now used across diverse subsystems including the virtual file system (VFS), networking stack, and scheduler.[4] Implementations extend beyond the kernel to user-space libraries, such as Userspace RCU (URCU), which provide similar semantics for application-level synchronization.[5]
Key advantages of RCU over traditional methods like reader-writer locks or reference counting include drastically reduced contention for readers, as they avoid synchronization primitives entirely in many cases, and better throughput in scenarios with thousands of concurrent readers.[2] It enforces strict guarantees, such as grace-period completion before memory reclamation and memory ordering via barriers, to prevent issues like use-after-free or data races across CPUs.[2] However, RCU requires careful usage, as readers must not sleep (in non-sleepable variants) and updates can introduce memory overhead from deferred reclamation.[1]
The Linux kernel offers multiple RCU flavors to suit different needs: preemptible RCU for low-latency real-time systems, RCU-bh for bottom-half softirq contexts, Sleepable RCU (SRCU) for code that may block or sleep, and Tasks RCU variants for process-level synchronization without explicit reader locking.[2] These adaptations have made RCU indispensable for high-performance computing, embedded systems, and cloud infrastructure, where it protects critical data structures like routing tables and notifier chains.[6] Ongoing research and development continue to refine RCU for emerging architectures, including heterogeneous and real-time environments, with recent API enhancements such as polling for grace periods as of 2024.[4][7]
Introduction
Overview
Read-copy-update (RCU) is a lock-free synchronization mechanism designed to allow multiple concurrent readers to access shared data structures without acquiring locks or incurring significant overhead, while updaters create copies of the data for safe modifications.[1][8] This technique enables efficient concurrent execution in environments where reads greatly outnumber updates, such as multiprocessor systems.[1]
The basic RCU process involves an updater copying the target data structure, applying modifications to the copy, and then atomically replacing the pointer to the original structure with one pointing to the updated version.[8] Following this replacement, the updater waits for a grace period—a mechanism ensuring that all pre-existing readers have completed their access to the old version—before reclaiming and freeing the obsolete structure.[1][8]
RCU's core goal is to minimize synchronization overhead for read-mostly workloads, thereby improving scalability and performance in high-concurrency settings.[1] It was initially motivated by the challenges of handling read-heavy scenarios in operating system kernels, where traditional locking mechanisms introduce excessive contention and complexity.[8]
Key Terminology
In Read-Copy Update (RCU), a quiescent state refers to any point in time during which a given CPU or thread is not executing within an RCU read-side critical section, such as during a context switch, idle loop execution, or user-mode operation.[9] This state allows the RCU mechanism to progress grace periods by confirming that no ongoing reads from that CPU are accessing old versions of protected data.[9] In non-preemptive kernels, quiescent states are typically detected at scheduler boundaries, including voluntary context switches and transitions to or from interrupt handlers.[9]
A grace period is the time interval starting from an update invocation during which every pre-existing RCU read-side critical section on all CPUs must complete, ensuring that updaters can safely reclaim memory previously protected by RCU.[9] This period ends only after each CPU has passed through at least one quiescent state since the grace period began, guaranteeing that no lingering reads hold references to outdated data structures.[9] Grace periods provide the core synchronization guarantee of RCU, allowing concurrent readers to proceed without blocking updaters once the period concludes.[9]
The read-side critical section encompasses the code region delimited by calls to RCU read-acquisition primitives, such as rcu_read_lock() and rcu_read_unlock(), within which shared data structures are accessed for reading.[9] These sections must avoid blocking operations like sleeping or yielding in classic RCU to prevent indefinite grace-period delays, though they may contain nested locks or preemptions in modern variants.[9] Readers within such sections observe a consistent view of the data, typically via pointer indirection, without acquiring locks.[9]
An updater is the code or thread responsible for modifying RCU-protected data structures, typically by creating a copy of the structure, applying changes to the copy, and then atomically replacing the pointer to the old structure with one to the new version using primitives like rcu_assign_pointer().[9] Updaters invoke grace-period-waiting functions, such as synchronize_rcu(), to ensure that all pre-existing read-side critical sections have completed before freeing the old data copy.[9] This approach enables non-blocking reads while allowing updates to proceed after a bounded delay.[9]
Terminology in RCU distinguishes classic RCU, which assumes non-preemptive kernels where read-side critical sections incur zero runtime overhead and quiescent states rely on voluntary context switches or interrupts, from modern variants like preemptible RCU, which support kernel preemption within read-side sections and require additional mechanisms to track potentially preempted readers.[10] In classic RCU, terms like "quiescent state" emphasize non-preemptive boundaries, whereas modern implementations extend these concepts to handle scheduling events that could prolong read-side execution.[11]
RCU Fundamentals
Read-Side Primitives
In Read-Copy Update (RCU), read-side primitives enable efficient, lock-free access to shared data structures by readers, allowing them to traverse data without blocking updaters. The primary primitives are rcu_read_lock() and rcu_read_unlock(), which delimit RCU read-side critical sections. These markers ensure that readers complete their sections before updaters can free old data versions, typically detected via a grace period mechanism.[10][12]
Within a read-side critical section, rcu_read_lock() prevents voluntary preemption in non-preemptive kernel environments, such as older Linux kernels, by disabling context switches until the matching rcu_read_unlock() is invoked. In preemptible kernels, these primitives instead track the reader's progress to allow safe preemption while ensuring the critical section's integrity. These primitives can nest arbitrarily, with each rcu_read_lock() requiring a corresponding rcu_read_unlock() to properly exit.[13][12]
RCU guarantees that during a read-side critical section, readers observe a consistent view of the data structure—either the pre-update version or the fully updated version—without intermediate states that could lead to inconsistencies. To safely dereference RCU-protected pointers within such sections, readers must use the rcu_dereference() primitive, which provides volatile-qualified access to prevent compiler optimizations from reordering loads that might violate RCU's memory model. This ensures that the pointer retrieved remains valid for the duration of the critical section.[10][14]
In certain configurations, such as non-preemptive kernels without debugging overhead, RCU read-side primitives impose zero runtime overhead, as they compile to no-ops and invoke no locking mechanisms, enabling readers to access data as efficiently as with plain pointer dereferences outside critical sections. However, in preemptible environments, additional lightweight tracking (e.g., per-CPU counters) may introduce minimal overhead to handle potential preemptions.[13][12]
Update-Side Primitives
In read-copy-update (RCU), update-side operations enable safe modifications to shared data structures by allowing concurrent readers uninterrupted access to consistent views of the data, without requiring locks on the read path.[15] A common approach in RCU updates is to copy the relevant part of the data structure when modifications to its contents are needed, such as a node in a linked list, to isolate changes from ongoing reads. However, structural updates like insertions and deletions often use direct atomic pointer updates without copying. Once copied (if applicable), the updater modifies this new version—for instance, changing a field value or adjusting pointers—while the original remains accessible to active readers.[16][15] To publish the modified copy or new pointer, the updater employs the rcu_assign_pointer() primitive, which performs an atomic pointer assignment with appropriate memory barriers to guarantee that readers see a fully initialized structure.[16] This primitive is essential for RCU-protected pointers, ensuring store-release ordering that synchronizes the update with subsequent read-side accesses.[14]
After installing the new version, the updater must wait for a grace period to elapse before reclaiming the old data, as this period guarantees the completion of all prior RCU read-side critical sections.[16] The synchronize_rcu() function implements this blocking wait, allowing the updater to safely free or repurpose the obsolete structure once it returns.[14] For non-blocking updates, particularly in scenarios where the updater cannot afford to wait, the call_rcu() primitive registers a callback function to be invoked asynchronously after the grace period, deferring reclamation without halting the update thread.[16] This asynchronous mechanism is widely used in the Linux kernel for scalable updates in high-throughput environments.[17]
RCU updates handle insertions, deletions, and modifications through these primitives, often tailored to data structures like singly linked lists. For an insertion, the updater copies the target node if needed, creates a new node with the desired data, adjusts pointers in the copy or new node, and uses rcu_assign_pointer() to link it into the list atomically, followed by synchronize_rcu() or call_rcu() to reclaim any displaced elements.[16] In deletions, the updater identifies the node to remove, updates surrounding pointers via rcu_assign_pointer() to bypass it (potentially copying nodes for complex traversals), and then waits for the grace period before freeing the deleted node.[15] Modifications follow a similar pattern: copy the node, apply changes to the copy (e.g., updating a value), assign the new pointer with rcu_assign_pointer(), and defer old node reclamation, ensuring readers traversing the list see consistent entries.[14] These operations maintain list integrity under concurrent reads, with the Linux kernel providing specialized helpers like list_add_rcu() and list_del_rcu() to encapsulate the pointer assignments for list-specific updates.[16]
Grace Periods
In read-copy-update (RCU), a grace period is the interval during which all pre-existing RCU read-side critical sections must complete before an updater can safely reclaim memory associated with replaced data structures.[18] This mechanism is necessary for memory reclamation because RCU readers may hold references to old versions of data without acquiring locks, requiring updaters to wait until no such references remain active to avoid use-after-free errors.[19] The grace period ensures that destructive operations, such as freeing memory, occur only after all potentially referencing readers have passed through a point where their access is guaranteed to have ended.[18]
Grace periods are detected through quiescent states, which are points in time when a CPU is not executing within an RCU read-side critical section.[18] Examples of quiescent states include CPU idle periods, voluntary context switches, and transitions to user mode, as these indicate that no RCU-protected data is being accessed on that CPU.[19] In non-preemptive kernels, quiescent states are directly detected at scheduler entry points, such as during context switches, allowing RCU to track when each CPU has ceased RCU read-side activity without the need for additional instrumentation.[18]
Algorithms for grace period expiration rely on monitoring these quiescent states across all CPUs to confirm that pre-existing readers have finished.[19] Once every CPU has reported at least one quiescent state following the start of the grace period—typically invoked via primitives like synchronize_rcu()—the period expires, permitting memory reclamation.[18] In multiprocessor systems, expiration algorithms must aggregate state reports efficiently to handle contention, ensuring that the grace period completes only after all CPUs, including those handling interrupts or offline transitions, have quiesced.[19]
Expedited grace periods provide a mechanism to shorten these wait times by actively forcing quiescent states, at the expense of higher overhead.[20] For instance, they may use interprocessor interrupts (IPIs) to prompt context switches or check for active critical sections directly, reducing latency from milliseconds to tens of microseconds on small systems, though this increases CPU disturbance and power consumption.[18] Such expediting is useful for latency-sensitive updates but trades off the low-overhead nature of normal grace periods.[18]
Challenges in multiprocessor systems arise from coordinating quiescent state detection across numerous CPUs, where delays in any single CPU—due to heavy loads, long-running critical sections, or offline states—can prolong the grace period.[19] Ensuring all CPUs reach quiescence requires robust tracking mechanisms, such as priority boosting for blocked tasks after timeouts like 500 milliseconds, to prevent indefinite stalls while maintaining scalability up to thousands of CPUs.[18]
Implementations and Variants
Basic Implementation
The basic implementation of Read-Copy-Update (RCU) can be illustrated through a simplified toy model suitable for a non-preemptive kernel environment, featuring a single updater and multiple concurrent readers. This model uses a global atomic counter to track the number of active readers, enabling the updater to detect when a grace period has elapsed without requiring locks on the read side.
Reader Pseudocode
Readers access shared data without acquiring locks, relying on the absence of preemption to ensure they complete promptly.
rcu_read_lock() {
atomic_inc(&rcu_counter); // Increment global counter atomically
}
rcu_read_unlock() {
atomic_dec(&rcu_counter); // Decrement global counter atomically
}
// Example read-side critical section
void reader_example(struct data **gp) {
struct data *p;
rcu_read_lock();
p = *gp; // Direct pointer access (assumes atomic load)
if (p != [NULL](/page/Null)) {
do_something_with(p->field); // Read data fields
}
rcu_read_unlock();
}
rcu_read_lock() {
atomic_inc(&rcu_counter); // Increment global counter atomically
}
rcu_read_unlock() {
atomic_dec(&rcu_counter); // Decrement global counter atomically
}
// Example read-side critical section
void reader_example(struct data **gp) {
struct data *p;
rcu_read_lock();
p = *gp; // Direct pointer access (assumes atomic load)
if (p != [NULL](/page/Null)) {
do_something_with(p->field); // Read data fields
}
rcu_read_unlock();
}
[22][19]
Updater Pseudocode
The updater creates a copy of the data structure, modifies it, publishes the new version atomically, waits for a grace period (when no readers are active), and then frees the old version.
synchronize_rcu() {
while (atomic_read(&rcu_counter) != 0) {
; // Spin until no active readers ([grace period](/page/Grace_period))
}
smp_mb(); // [Memory barrier](/page/Memory_barrier) to ensure ordering
}
void updater_example(struct data **gp) {
struct data *new_data, *old_data;
new_data = malloc(sizeof(struct data)); // Allocate and copy old data
memcpy(new_data, *gp, sizeof(struct data));
new_data->field = updated_value; // Modify the copy
old_data = *gp;
*gp = new_data; // Atomic pointer replacement (e.g., via atomic exchange)
synchronize_rcu(); // Wait for [grace period](/page/Grace_period)
free(old_data); // Safe to free old data now
}
synchronize_rcu() {
while (atomic_read(&rcu_counter) != 0) {
; // Spin until no active readers ([grace period](/page/Grace_period))
}
smp_mb(); // [Memory barrier](/page/Memory_barrier) to ensure ordering
}
void updater_example(struct data **gp) {
struct data *new_data, *old_data;
new_data = malloc(sizeof(struct data)); // Allocate and copy old data
memcpy(new_data, *gp, sizeof(struct data));
new_data->field = updated_value; // Modify the copy
old_data = *gp;
*gp = new_data; // Atomic pointer replacement (e.g., via atomic exchange)
synchronize_rcu(); // Wait for [grace period](/page/Grace_period)
free(old_data); // Safe to free old data now
}
[22][19]
This pseudocode demonstrates the core read-side and update-side primitives of RCU in a minimal form. Readers simply adjust the global counter to mark their critical sections, allowing lock-free traversal of shared data. The updater, after publishing the updated structure, invokes a grace period wait via the counter to guarantee that all pre-existing readers have completed before reclaiming memory.[22]
The model assumes a non-preemptive kernel where threads run to completion or block only outside RCU critical sections, and quiescent states (points where readers are not active) are directly tracked via the counter without needing per-CPU mechanisms.[22][19]
However, this simple model has limitations, such as no support for reader preemption, which could leave the counter incremented indefinitely if a reader is preempted within its critical section; it also lacks handling for multiple updaters or CPU hotplug events.[22][19]
Sample Kernel Interface
The Read-Copy Update (RCU) API in the Linux kernel provides a standardized interface for implementing RCU synchronization, enabling efficient read-mostly access patterns while ensuring safe updates. This API consists of lightweight primitives for readers and more involved mechanisms for updaters, with built-in support for nesting and preemption in certain configurations.[23][24]
On the read side, the core functions are rcu_read_lock() and rcu_read_unlock(), which delimit RCU read-side critical sections. The function signatures are void rcu_read_lock(void) to enter a critical section and void rcu_read_unlock(void) to exit it. These calls are extremely lightweight, typically involving no locking, and are designed to protect traversals of RCU-protected data structures, such as linked lists. For example, to safely traverse a list, code would invoke rcu_read_lock(), use a macro like list_for_each_entry_rcu() to iterate entries while dereferencing pointers with rcu_dereference(), and then call rcu_read_unlock(). The dereference function, rcu_dereference(p), with signature typeof(p) rcu_dereference(p), safely acquires an RCU-protected pointer within a read-side section, ensuring the reader sees a consistent view without immediate invalidation by concurrent updates.[23][24]
For updates, the API includes rcu_assign_pointer() to safely publish new values and synchronization primitives to wait for grace periods. The assignment function has the signature rcu_assign_pointer(p, v), where p is the pointer and v is the new value, ensuring that readers will only see fully initialized data. To wait for a grace period—during which all pre-existing read-side critical sections complete—updaters use synchronize_rcu(), with signature void synchronize_rcu(void), which blocks until the grace period ends. For non-blocking updates, call_rcu() registers a callback for deferred execution after a grace period, with signature void call_rcu(struct rcu_head *head, rcu_callback_t func), commonly used for freeing removed elements, such as in list deletions via list_del_rcu() followed by callback registration on the freed structure. A typical pattern for deferred work is to remove an item from an RCU-protected list with rcu_assign_pointer()-based updates, then invoke call_rcu() on its rcu_head member to schedule reclamation.[23][24]
RCU read-side critical sections support nesting, allowing multiple rcu_read_lock() calls without deadlock as long as they are properly balanced with corresponding rcu_read_unlock() invocations; this enables safe recursion in traversal code. To avoid deadlocks and ensure correctness, readers must not block or sleep within critical sections unless using a preemptible RCU variant, as blocking could indefinitely delay grace periods. Error handling emphasizes validating pointer assignments and dereferences to prevent use-after-free issues, often by assigning dereferenced values to local variables for repeated access within a section. The kernel configuration option CONFIG_PREEMPT_RCU enables a preemptible flavor of RCU, allowing voluntary preemption in read-side sections while tracking them via task structures, which is useful for low-latency real-time systems but adds slight overhead compared to the non-preemptible variant.[23][24]
Advanced Variants
Hierarchical RCU addresses scalability challenges in NUMA systems with large numbers of CPUs by organizing them into a tree structure of rcu_node hierarchies, where leaf nodes pair CPUs and root nodes cover the entire system.[25] This partitioning reduces lock contention significantly—for instance, on a 4,096-CPU system, it limits contention to 64 CPUs per leaf lock compared to all CPUs contending for a single global lock in classic RCU.[25] By avoiding unnecessary wakeups of idle CPUs, hierarchical RCU also improves energy efficiency while maintaining correct grace-period detection.[25]
Tree RCU extends this hierarchy for preemptible kernels, employing per-CPU rcu_data structures with counters like gp_seq to track local grace-period states and quiescent states without global synchronization overhead.[26] The rcu_state structure interconnects the tree of rcu_node and rcu_data elements, supporting up to millions of CPUs across multiple levels and managing blocked tasks during preemption.[26] This design enhances scalability in environments where tasks can be preempted, differing from non-preemptible variants by distributing callback queuing and state propagation across CPUs.[26]
Expedited RCU provides faster grace periods through functions like synchronize_rcu_expedited(), which sends inter-processor interrupts (IPIs) to non-idle, online CPUs to force immediate quiescent states.[20] In RCU-preempt mode, it sets flags checked at rcu_read_unlock() to report quiescence, while in RCU-sched, it triggers context switches via rescheduling flags.[20] Batching multiple requests using sequence counters reduces IPI overhead, though this variant trades higher disturbance for latencies as low as tens of microseconds on small systems.[20]
Preemptible RCU (PREEMPT_RCU) allows read-side critical sections to be preempted or blocked, using per-CPU rcu_flipctr arrays to track reader counts across multi-stage grace periods without memory barriers in lock/unlock primitives.[11] Primitives like rcu_read_lock() increment counters under IRQ disablement, while rcu_read_unlock() decrements them and supports priority boosting to prevent indefinite blocking in real-time scenarios.[11] This variant integrates with priority inheritance mechanisms, extending grace periods until all pre-existing readers complete despite preemption.[11]
In real-time kernels like PREEMPT_RT, preemptible RCU is employed to ensure low-latency operation, with RCU processing confined to dedicated threads and removed from intermediate kernel paths to minimize jitter.[27] This configuration requires enabling full preemption and uses preemptible mechanisms to handle synchronization without compromising real-time guarantees.[27]
Userspace adaptations like liburcu port kernel RCU concepts to application-level code, providing lock-free data structures such as hash tables and queues with read-side scaling linear to the number of cores.[28] It offers flavors including QSBR for zero-overhead reads requiring explicit quiescent-state calls, and memory-barrier (MB) for faster grace periods at the cost of read performance.[28] Other variants like signal-based or bullet-proof handle thread registration automatically, adapting kernel-style rcu_read_lock()/synchronize_rcu() for concurrent userspace environments without kernel privileges.[29]
Applications
In the Linux Kernel
Read-copy-update (RCU) was integrated into the Linux kernel during the 2.5 development series, with initial commits appearing in October 2002, marking a key milestone in enhancing synchronization for read-heavy workloads.[19] This addition allowed the kernel to handle concurrent reads and updates more efficiently without traditional locking overhead, paving the way for its widespread adoption across core subsystems.[1]
As of Linux kernel v6.10 (July 2024), there are over 21,000 invocations of the RCU API, reflecting its deep entrenchment in the codebase and evolution from earlier implementations.[30] By v6.17 (September 2025), this has grown to over 23,000.[30] In networking, RCU protects structures like IP routing tables, where frequent reads tolerate brief staleness while updates propagate without blocking readers, using primitives such as rcu_read_lock_bh().[31] For file systems, it manages the directory entry (dentry) cache through deferred reclamation, separating data removal from memory freeing to support high-concurrency lookups.[1] In the scheduler, RCU safeguards runqueue structures and task lists, enabling safe access during operations like NMI handlers via rcu_read_lock_sched() and synchronize_sched().[31]
RCU's design contributes significantly to the Linux kernel's scalability on multi-core servers and in cloud environments, where it minimizes contention in read-dominated paths across hundreds of CPUs.[31] For instance, kernel developers leverage RCU's API—such as rcu_read_lock() for read-side critical sections—to maintain performance in large-scale deployments without the bottlenecks of reader-writer locks.[1]
In Other Operating Systems
DragonFly BSD incorporates RCU support, including in subsystems like the Direct Rendering Manager (DRM) for graphics, with implementations added starting in 2018.[32] This approach supports efficient read-mostly access in kernel subsystems, differing from Linux by integrating with its token-based synchronization model to reduce overhead.[32] Ongoing enhancements are evident in areas like the DRM and broader lockless algorithm discussions.[33]
Research kernels such as K42 have integrated RCU principles through mechanisms like deferred object deletion, enabling scalable synchronization for cache-coherent non-uniform memory access (ccNUMA) architectures without traditional locking overhead.[34] In K42, this RCU-like technique facilitates high-performance access to shared data structures in a research environment focused on kernel extensibility and Linux API compatibility.[35]
Experimental adaptations of RCU extend to embedded and real-time systems, where modifications address latency concerns by allowing preemption of RCU read-side critical sections and reducing grace period overheads in resource-constrained environments.[36] These enhancements enable RCU to meet deterministic timing requirements in multiprocessor setups, such as those in automotive or avionics applications, by minimizing callback queuing delays and supporting voluntary quiescent states during idle periods.[36]
User-Space Implementations
Userspace RCU implementations enable read-mostly synchronization in application-level code, outside of kernel environments, by providing libraries that adapt RCU primitives to user-space constraints. The primary such library is liburcu, an LGPLv2.1-licensed userspace RCU implementation developed by Mathieu Desnoyers, which offers read-side critical sections that scale linearly with the number of CPU cores while minimizing overhead.[28][5] Liburcu's API closely mirrors the Linux kernel's RCU interface, including functions like rcu_read_lock() and rcu_read_unlock() for read-side protection, synchronize_rcu() for waiting on grace periods, and thread registration calls such as rcu_register_thread() to handle user-space threading models.[29] This design allows developers to port kernel-style RCU usage to applications with minimal changes, supporting multiple flavors like quiescient-state-based (QSBR), memory-barrier-free, and signal-based variants to suit different performance needs.[5]
Key challenges in user-space RCU arise from the lack of kernel-level control over scheduling and interrupts. Signal handling requires careful management, as signal-based flavors use a dedicated POSIX signal like SIGUSR1 to detect quiescent states, potentially conflicting with application signals unless masked appropriately.[29] Thread preemption is addressed through explicit thread registration, which informs the library of active threads to ensure accurate grace-period detection, but this adds setup overhead compared to kernel RCU.[5] Integration with POSIX threads (pthreads) is seamless, as liburcu supports multi-threaded environments by tracking thread states during reads and updates, enabling lock-free access in concurrent programs without blocking writers on readers.[29]
Liburcu finds applications in high-performance databases and distributed storage systems, such as Sheepdog, where it facilitates scalable updates to shared data structures under heavy read loads.[29] In web servers and DNS resolvers like Knot DNS and gdnsd, it optimizes read-mostly operations such as cache lookups, reducing latency in query-heavy scenarios.[29] Parallel libraries benefit from liburcu's concurrent data structures (CDS) module, which includes RCU-protected hash tables, queues, and lists suitable for cloud workloads involving dynamic key-value stores and in-memory processing.[28] These structures enable resizable, lock-free hash tables that maintain constant-time performance during resizing, as demonstrated in relativistic programming approaches for user-space concurrency.[37] In modern containerized environments, such as those orchestrated by Docker, liburcu powers tracing tools like LTTng-UST and networking applications, ensuring efficient synchronization across isolated processes in cloud-native deployments.[29]
Advantages
Read-copy-update (RCU) provides extremely low overhead on the read side, often approaching zero in non-preemptive kernels where read-side primitives such as rcu_read_lock() and rcu_read_unlock() compile to empty statements on most architectures.[1] This absence of locks, atomic instructions, or memory barriers during reads enables exceptionally high throughput in read-heavy workloads, where readers vastly outnumber updaters, such as in routing tables or file descriptors.[8] Grace periods in RCU further contribute to this low overhead by deferring update completion until all pre-existing reads have finished, without requiring readers to synchronize directly with updaters.[1]
RCU scales effectively to thousands of CPUs, supporting configurations up to 8192 in the Linux kernel through hierarchical tree-based designs that minimize global operations and contention.[9] Unlike traditional locks, RCU avoids cacheline bouncing and contention on shared variables, allowing concurrent reads and batched updates to proceed without blocking, which maintains performance as CPU counts increase in large-scale shared-memory systems.[3]
RCU exhibits strong composability, interoperating seamlessly with other synchronization primitives like spinlocks, sequence locks, atomic operations, and reference counters within read-side critical sections.[9] This modularity allows developers to integrate RCU into existing codebases for read-mostly data structures while leveraging complementary mechanisms for other needs, fostering scalable and maintainable designs.[38]
In real-time and cloud computing environments, RCU reduces latency through features like preemptible variants with sub-100-microsecond budgets and polled grace periods introduced in 2024, enabling predictable response times without excessive synchronization costs.[9] Recent kernel optimizations, including dynamic callback offloading to dedicated kthreads, further enhance scalability and latency control for high-performance computing and hyperscale workloads by adapting to varying CPU loads.[7]
RCU promotes energy efficiency, particularly in mobile and embedded devices, by avoiding unnecessary awakenings of idle CPUs and implementing lazy grace periods that delay non-urgent callbacks, yielding over 10% power savings on battery-powered platforms like Android.[7] These mechanisms track idle states and batch operations to minimize interrupts, aligning with the demands of power-constrained systems.[9]
Disadvantages and Limitations
One significant limitation of Read-Copy Update (RCU) is the high latency associated with updates, as they must wait for a grace period to complete before old data versions can be safely reclaimed. This grace period ensures that all pre-existing RCU read-side critical sections have finished, but in large systems or under heavy load, it can extend to seconds, with the Linux kernel's default stall warning threshold set at 21 seconds. In virtualized environments, invoking synchronize_rcu() can cause latency spikes of several seconds on overcommitted hosts due to preempted RCU readers. Such delays make RCU unsuitable for scenarios requiring low-latency updates, as the updater blocks until the grace period ends.
RCU also imposes memory overhead by retaining old versions of data structures throughout the grace period, preventing immediate reclamation and increasing the overall memory footprint. This retention is necessary to allow concurrent readers uninterrupted access, but it results in larger cache footprints and potential out-of-memory conditions during prolonged grace periods. In systems with frequent updates, this overhead accumulates, exacerbating memory pressure compared to traditional locking mechanisms that permit quicker cleanup.
RCU is optimized for read-mostly workloads and performs poorly in write-heavy environments, leading to scalability issues and higher overhead than alternatives like reader-writer locks. For short-lived data structures, frequent updates cause rapid accumulation of obsolete versions, amplifying memory consumption without proportional benefits, as the grace period delays do not align with the data's transient nature.
Debugging RCU implementations presents challenges due to the non-deterministic nature of grace periods, which depend on CPU scheduling and quiescent states, making reproduction of issues like stalls difficult. RCU stall warnings help detect excessively long grace periods, but diagnosing root causes—such as CPU starvation or preemption problems—requires specialized tools and can be complex in production systems.
To mitigate these limitations, expedited grace period variants reduce update latency by actively forcing quiescent states, though at the cost of increased CPU overhead. In real-time kernels as of 2024, approaches like workqueue-driven expedited grace periods and hybrid combinations with locks (e.g., in percpu reader-writer semaphores) address latency in critical paths while preserving RCU's read-side efficiency.
Comparisons
With Reader-Writer Locks
Read-copy-update (RCU) enables an unbounded number of concurrent readers to access shared data structures without any serialization, in contrast to reader-writer locks, which require readers to either queue or spin when a writer holds the lock.[39] This difference arises because RCU readers use lightweight primitives like rcu_read_lock() and rcu_read_unlock(), which impose negligible overhead and allow parallel execution even during updates, whereas reader-writer locks enforce mutual exclusion through acquire and release operations that can serialize access.[39][40]
In terms of update handling, RCU updaters must wait for a grace period—a quiescent state where all pre-existing readers have completed—before freeing old data versions, but this does not block new readers from starting.[39] Reader-writer locks, however, block all new readers (and writers) during the write phase to ensure consistency, potentially leading to contention under high read loads.[39] For example, in a doubly-linked list traversal, RCU replaces read-side locking with RCU read-side critical sections, allowing readers to proceed uninterrupted while updaters use callbacks like call_rcu() for deferred reclamation.[39]
RCU's read-side overhead is near-zero, typically involving only compiler barriers, but updates incur costs from copying data structures and waiting for grace periods.[8] Reader-writer locks, by comparison, impose acquire and release costs on every read and write operation, which can accumulate in systems with frequent reads.[40] Performance evaluations, such as those on System V IPC implementations, show RCU outperforming reader-writer locks by factors of up to 10 in read-heavy workloads due to reduced synchronization overhead.[40]
RCU is particularly suited for read-mostly workloads where reads vastly outnumber writes, such as in routing tables or file-system directories, while reader-writer locks are more appropriate for scenarios with balanced read-write ratios requiring strict serialization.[39][8] This divergence stems from RCU's tolerance for temporary inconsistencies during updates, which reader-writer locks avoid through immediate exclusion.[39]
With Other Synchronization Mechanisms
Read-copy-update (RCU) differs from seqlocks in its approach to ensuring reader consistency without requiring retries. Seqlocks employ sequence counters to detect concurrent writes, allowing lockless readers to proceed but potentially forcing them to spin or retry if a writer intervenes during the read, which can introduce variable latency under contention.[41] In contrast, RCU guarantees a consistent snapshot for readers via grace periods, enabling non-blocking, wait-free reads without retries, though at the cost of deferred updates.[42] Seqlocks are lighter-weight for simple, read-mostly data where occasional reader retries are tolerable, but RCU is preferred when consistent, low-latency reads are critical without spinning.[42]
Compared to hazard pointers and epoch-based reclamation, RCU is particularly optimized for kernel environments through its use of quiescent-state-based grace periods, which efficiently detect when all readers have completed access to old data versions. Hazard pointers, a pointer-based safe memory reclamation (SMR) technique, allow threads to announce specific objects they are accessing, enabling immediate reclamation once unprotected, but incur higher overhead from per-access announcements and scans across all threads' pointers.[43] Epoch-based reclamation (EBR), by contrast, uses global epochs to batch reclamations, assuming no long-held pointers across operations, which simplifies implementation but limits flexibility for data structures retaining references.[44] RCU's quiescent-state approach provides bounded protection durations tailored to kernel workloads, making it more scalable for system-wide use, whereas hazard pointers and EBR offer greater generality for user-space lock-free data structures.[43][44]
RCU also contrasts with software transactional memory (STM) by eschewing speculative execution in favor of explicit versioning and copying. STM encapsulates updates in atomic transactions that may abort and retry on conflicts, incurring speculation overhead from buffering changes and conflict detection.[45] RCU, however, requires manual copying of data structures for updates, allowing concurrent readers to access unchanged versions without aborts, thus avoiding STM's rollback costs but demanding more programmer effort for versioning.[45] While STM simplifies complex concurrent modifications through atomicity, RCU suits scenarios with infrequent, non-conflicting updates where speculation is unnecessary.[45]
RCU is typically chosen over these alternatives in kernel contexts for its low read-side overhead and integration with system scheduling for grace periods, enabling efficient protection of read-mostly data like configuration structures.[43] In user space, seqlocks, hazard pointers, or EBR may be favored for lightweight lock-free implementations, while STM is selected for applications needing automatic conflict resolution despite higher costs.[44][45]
History and Intellectual Property
Historical Development
The origins of read-copy-update (RCU) trace back to early ideas in concurrent data structure management from the 1980s. In 1980, H. T. Kung and Philip L. Lehman introduced concepts resembling RCU in their work on concurrent manipulation of binary search trees, where they described techniques for deferring updates and using garbage collection to allow safe concurrent reads without immediate synchronization.[46] These ideas laid foundational principles of procrastination in synchronization, influencing later developments in scalable concurrency mechanisms.
During the 1990s, Paul E. McKenney advanced these concepts while working at Sequent Computer Systems (later acquired by IBM), initially developing RCU prototypes for the DYNIX/ptx operating system around 1993–1994 to address scalability issues in multiprocessor environments.[19] McKenney, collaborating with John D. Slingwine, formalized RCU in their 1998 paper "Read-Copy Update: Using Execution History to Solve Concurrency Problems," which described leveraging execution history to permit concurrent reads during updates without locks, targeting linked data structures in systems like IBM's research-oriented K42 kernel.
RCU's integration into the Linux kernel occurred in version 2.5.43 in October 2002, driven by McKenney and implemented by Rusty Russell, who contributed the efficient rcu-sched variant using per-CPU counters to minimize update overhead.[38] This marked RCU's transition to a widely adopted open-source synchronization primitive, despite originating from proprietary Sequent research, amid broader industry shifts toward open-source software following high-profile intellectual property disputes like the SCO Group lawsuits against IBM and Linux contributors, which ultimately bolstered community-driven adoption by affirming contributions' legitimacy.[47]
Key evolutionary milestones followed in the mid-2000s to enhance RCU's suitability for diverse workloads. Hierarchical RCU was introduced in 2008 to improve scalability on large systems by organizing grace periods across CPU hierarchies, reducing contention in multi-level cache environments.[25] Preemptible RCU arrived in 2007 with Linux kernel 2.6.24, allowing read-side critical sections to be safely preempted, which was crucial for real-time and low-latency applications by mitigating priority inversion issues.[11] Tree RCU emerged in 2009 as an extension of the hierarchical variant, employing a tree-based structure for more efficient grace-period detection on systems with thousands of CPUs, further solidifying RCU's role in high-performance computing.[48]
Paul E. McKenney has served as the primary maintainer of RCU in the Linux kernel since its inception, overseeing its refinements and ensuring compatibility with evolving hardware and workloads through 2025.[49]
Patents
The primary patents covering read-copy-update (RCU) mechanisms originated from work at Sequent Computer Systems, later acquired by IBM, and focused on methods for achieving low-overhead mutual exclusion and data coherency in multiprocessor systems through thread activity summaries and quiescent state detection.[50] The foundational U.S. Patent 5,442,758, issued on August 15, 1995, to Sequent (assigned to IBM), describes an apparatus for concurrent reading and updating of shared data using execution history to track quiescent states, enabling zero-overhead mutual exclusion.[50] This was followed by U.S. Patent 5,608,893, issued on March 4, 1997, to IBM, which extends coherency maintenance using thread activity summaries to detect when updates can safely proceed without blocking readers.[51] Subsequent patents include U.S. Patent 6,219,690, issued on April 17, 2001, to IBM, detailing efficient implementations of read-copy-update for reduced overhead in multiprocessor environments.[52] U.S. Patent 6,886,162, issued on April 26, 2005, to Sequent and IBM, addresses high-speed thread activity summarization across multiple nodes using hierarchical bit masks to minimize remote memory operations during grace period detection.[53] These patents broadly cover copy-update synchronization techniques that allow readers to access data structures without locks while updaters create new versions and defer reclamation until safe.
The RCU patents became a point of contention in the SCO Group v. International Business Machines Corp. lawsuit, filed in March 2003, where SCO alleged that IBM improperly contributed RCU code—derived from Sequent's proprietary Unix implementations—to Linux, infringing on SCO's Unix licensing rights.[54] The case, which spanned from 2003 to 2007 before administrative closure due to SCO's bankruptcy and later dismissal of remaining claims in 2016, scrutinized RCU among other technologies but resulted in no findings of infringement or restrictions on RCU's use in open-source software.[54]
All major RCU-related patents had expired by 2010, with the core ones lapsing between 2009 and 2012 due to their 17- or 20-year terms from filing or issuance.[55] As of 2025, no active patents on fundamental RCU mechanisms remain, allowing unrestricted adoption and implementation in open-source kernels like Linux without intellectual property barriers.[55] This expiration has facilitated widespread integration of RCU variants across operating systems, enhancing scalability in concurrent environments without licensing concerns.[55]