Understanding RCU: Benefits and Use Cases

1. The Problem: Scalability of Traditional Locks

With traditional reader-writer locks, readers can access data concurrently. However, a writer must wait for all readers to finish, and all subsequent readers must wait for the writer to finish. In a system with many CPUs and many readers, this can become a significant bottleneck, as the writer blocks all readers.

RCU's primary goal is to make the read path as fast and scalable as possible—ideally, with zero synchronization overhead.

To understand the motivation and performance implications, let's watch a segment of a talk that introduces the problem RCU is designed to solve.

The key takeaway is that for read-mostly data, we want reader performance to be unaffected by the infrequent writes. RCU achieves this by allowing readers to operate without acquiring any locks, even while a write is in progress.

2. The RCU Philosophy: Read, Copy, Update

The name "Read-Copy-Update" describes the updater's workflow. Since readers don't use locks, the writer cannot modify the data in place. Instead, it follows a strict protocol.

A foundational paper on RCU, "What is RCU, Fundamentally?", breaks the mechanism into three core components.

As the paper states, the three mechanisms are:

1. Publish-Subscribe Mechanism (Insertion/Update): The writer (updater) creates a copy of the data, modifies this private copy, and then "publishes" it by atomically updating a pointer to make it visible to new readers.
2. Wait For Pre-Existing RCU Readers to Complete (Deletion/Reclamation): After an update, the writer must wait until all readers that might have seen the old data have finished their work before it can be safely freed.
3. Maintain Multiple Versions: For a short time, multiple versions of the data exist simultaneously. Old readers see the old version, and new readers see the new version.

This "copy-then-publish" dance is the core of how writers can modify data without interfering with concurrent lock-free readers.

3. The Crucial Part: Safe Memory Reclamation

The most challenging part of RCU is not the update itself, but safely freeing the old data. If a writer frees the old data immediately, a concurrent reader that is still traversing it could suffer a use-after-free bug.

RCU solves this with a cooperative protocol built on the concepts of RCU read-side critical sections, quiescent states, and grace periods.

Let's solidify those key definitions:

• RCU Read-Side Critical Section: A section of code starting with rcu_read_lock() and ending with rcu_read_unlock(). Crucially, these functions do not acquire a lock. They typically disable preemption or serve as compiler barriers, simply notifying the RCU subsystem that a thread is reading shared data. A thread inside this section must not sleep.
• Quiescent State: A state where a thread is known not to be in an RCU read-side critical section. For example, a CPU executing a context switch or idling is in a quiescent state.
• Grace Period: A duration of time during which every CPU in the system has passed through at least one quiescent state. Once a grace period has elapsed, the RCU subsystem knows that any reader that began its critical section before the grace period started must now be finished.

The synchronize_rcu() function simply blocks until one full grace period has passed, thereby guaranteeing that it is safe to free the old data.

4. RCU in Action: A Kernel Module Example

Now let's see how these concepts translate into kernel code. We'll use a practical guide that starts from a familiar mutex-based solution and refactors it to use RCU, highlighting the exact scenarios where RCU is beneficial.

The code demonstrates the complete RCU flow:

1. The Reader (dbg_read):

   • Calls rcu_read_lock() to enter the critical section.
   • Uses rcu_dereference(ptr) to safely get the current pointer. This is crucial as it ensures the compiler/CPU doesn't perform unsafe reordering and includes necessary memory barriers.
   • Reads the data.
   • Calls rcu_read_unlock() to exit the critical section.

2. The Writer (update_data):

   • Allocates memory for a new copy (newloc).
   • Copies the old data to the new location.
   • Modifies the new location.
   • Calls rcu_assign_pointer(ptr, newloc) to atomically "publish" the new data. From this point on, new readers will see newloc.
   • Calls synchronize_rcu() to wait for a grace period to end.
   • After synchronize_rcu() returns, it safely kfree()s the old data.

5. Asynchronous Freeing with call_rcu()

A key detail in the writer's path is that synchronize_rcu() blocks. Waiting for every CPU in the system to take a context switch can be a long time (milliseconds), which is often unacceptable in a performance-critical write path.

The preferred method is to perform the cleanup asynchronously using call_rcu(). This function takes a pointer to a struct rcu_head embedded in your data structure and a callback function. It returns immediately, and the RCU subsystem will invoke your callback function with that structure as an argument after a grace period has passed.

The linked-list example in the same article demonstrates this perfectly.

6. Interview Scenario: The Danger of Mismatched Flavors

For interview preparation, it's essential to understand not just how to use an API, but how it can fail. A subtle but critical source of bugs is using mismatched "flavors" of RCU. The Linux kernel has several RCU variants (e.g., rcu_preempt, rcu_sched, rcu_bh). The read-side and update-side primitives must match.

Let's analyze a real-world, exploitable bug that RCU maintainer Paul McKenney presented.

Your Analysis:
The core of the problem is that synchronize_rcu() only guarantees that grace periods for the "plain" RCU flavor have completed. It knows nothing about rcu_sched. Therefore, it does not wait for readers inside an rcu_read_lock_sched() / rcu_read_unlock_sched() critical section.

The fix is consistency:

• If readers use rcu_read_lock(), the updater must use synchronize_rcu() or call_rcu().
• If readers use rcu_read_lock_sched(), the updater must use synchronize_rcu_sched() or call_rcu_sched().

This demonstrates a critical principle in kernel development: APIs have strict contracts, and violating them, even in subtle ways, can lead to severe security vulnerabilities.

Conclusion

In this lesson, we've dived into the powerful world of RCU, moving beyond traditional locking to a more scalable synchronization paradigm for read-mostly data.

Key Takeaways:

• When to use RCU: It is the preferred mechanism for data structures that are read far more often than they are written, especially in highly parallel, multi-core environments.
• How it Works: Writers create a copy, update it, and atomically publish it. Readers access the data without locks, making their path extremely fast.
• Safe Reclamation: The core of RCU's safety lies in the grace period. Writers use synchronize_rcu() (blocking) or call_rcu() (non-blocking) to wait for one grace period before freeing old data, guaranteeing no readers are still using it.
• API Discipline: You must use RCU primitives correctly. Readers mark critical sections with rcu_read_lock/unlock, access pointers with rcu_dereference, and updaters publish with rcu_assign_pointer. Consistency between RCU flavors is non-negotiable.

RCU is a deep topic, but you now have a solid foundation in its principles and practical application. In our next lesson, we will explore other lock-free techniques, using atomic operations and per-CPU variables to avoid locking overhead in performance-critical paths, which often complement RCU-based designs.