Understanding RCU: Lock-Free Reads

1. The Problem with Locks in Read-Mostly Scenarios

Imagine a data structure, like a network routing table, that is read thousands of times per second but only updated once every few minutes. Using a traditional reader-writer lock or a spinlock means that every one of those thousands of readers must pay a synchronization price (like an atomic instruction or cache coherency traffic) just for the rare possibility that a writer might be active.

As the number of CPU cores increases, this contention becomes a significant bottleneck, preventing the system from scaling.

RCU's philosophy is simple but powerful: make the common case—reading—as fast as possible, effectively free, and shift the complexity to the uncommon case—writing.

2. The RCU Philosophy: Separating Update from Reclamation

The fundamental concept of RCU is to split an update operation into two distinct phases: removal and reclamation. Instead of modifying data in-place, a writer creates a copy, updates it, and then defers the destruction of the old data.

Let's break this down:

1. Read: The writer reads the current state of the data it intends to modify.
2. Copy: It creates a new copy of the data structure.
3. Update: It modifies this new copy. All of this happens "offline," invisible to any current readers.
4. Publish: The writer atomically updates the pointer that points to the shared data to now point to the new, updated copy. Modern CPUs guarantee that this pointer write is atomic, so readers will see either the old pointer or the new one, never a corrupted state.
5. Reclaim (Deferred): The writer cannot free the old data immediately, because readers that were active before the pointer swap might still be accessing it. The writer must wait for all such pre-existing readers to complete. This waiting period is known as a grace period. After the grace period ends, it is safe to free the old data.

The official Linux kernel documentation provides an excellent overview of this core idea.

This timeline diagram provides a clear visual of the process:

3. The RCU API in Practice

The Linux kernel provides a small, elegant API to implement this pattern. Let's look at the core functions for the reader and the writer.

The Reader's Side: Extremely Lightweight

A reader simply needs to announce the start and end of its critical section.

• rcu_read_lock(): Marks the beginning of an RCU read-side critical section. On many architectures and kernel configurations, this can be as cheap as disabling preemption or, in some cases, compiling to nothing. It does not take a lock.
• rcu_read_unlock(): Marks the end of the critical section.
• rcu_dereference(p): Used to fetch an RCU-protected pointer p. This macro ensures the compiler doesn't perform unsafe optimizations and inserts necessary memory barriers on architectures that need them (like Alpha).

The Writer's Side: Handling the Update and Reclamation

A writer performs the update and manages the grace period.

• rcu_assign_pointer(p, v): Publishes the update by assigning a new pointer v to the RCU-protected pointer p. This macro handles the necessary memory barriers to ensure the new data is fully visible before the pointer is updated.
• synchronize_rcu(): This is a blocking function that waits for one grace period to complete. Once it returns, the writer knows that all readers who were active before synchronize_rcu() was called are finished, and it's now safe to free the old data.
• call_rcu(head, func): A non-blocking alternative. It registers a callback function func to be invoked on the head structure after a grace period has elapsed. This is essential for contexts where blocking is not allowed (like in an interrupt handler).

The following article provides a well-commented code example that puts all these pieces together.

4. Interview Deep Dive: How RCU Works

A common interview question is: "How does synchronize_rcu know when all readers are done, especially if rcu_read_lock is so cheap?"

The answer lies in the concept of a quiescent state. A CPU is considered to be in a quiescent state if it is in a state where it is known not to be holding an RCU read-side critical section. Examples include:

• Being in the idle loop.
• Executing in user space.
• Going through a context switch in the scheduler.

A grace period ends when every CPU in the system has passed through at least one quiescent state. This guarantees that any reader critical section that was active on any CPU at the start of thegrace period must have completed.

The implementation can get quite complex (using generation counters, per-CPU data, etc.), but this core principle is what you need to explain. For a more detailed look at the mechanics, including how an epoch/generation-based system works, the following video is an excellent resource.

5. Use Cases and Trade-offs

Understanding when and when not to use RCU is critical for system design questions.

Ideal Use Cases for RCU:

• Read-mostly data structures: The benefit of RCU is directly proportional to the read-to-write ratio.
• High-performance networking: Kernel routing tables and connection tracking are classic examples.
• Filesystem caches: The dentry cache uses RCU to allow fast lookups while handling file creation/deletion.
• Anywhere you need lock-free, scalable reads.

When to Avoid RCU:

• Write-heavy workloads: The overhead of copying data and waiting for grace periods makes RCU inefficient if writes are frequent.
• Large data structures: The cost of copying a very large object for every update can be prohibitive.
• When readers need to modify the data: RCU readers are expected to be read-only. If readers also need to write, you need a different mechanism.

Key Trade-offs:

• Performance: Unparalleled read-side performance vs. higher write-side overhead.
• Memory: RCU can temporarily increase memory usage as old and new data versions coexist during a grace period.
• Write Latency: synchronize_rcu() can block the writer for a noticeable duration. Long-running readers can extend grace periods, delaying memory reclamation and potentially leading to memory pressure if updates are rapid.

Conclusion

You've now explored the fundamental principles of RCU, a powerful synchronization technique that prioritizes read-side performance above all else. Its "separate removal from reclamation" strategy is a key enabler of scalability in multi-core systems.

Key Takeaways:

• RCU is optimized for read-mostly scenarios, offering near-zero overhead for readers.
• Writers perform updates by copying the data, modifying the copy, and atomically publishing a pointer to it.
• Old data is reclaimed only after a grace period, which is a wait for all pre-existing readers to finish their critical sections.
• The API consists of lightweight rcu_read_lock/unlock for readers and publishing/synchronization primitives (rcu_assign_pointer, synchronize_rcu, call_rcu) for writers.
• RCU's primary trade-off is excellent read performance for higher writer overhead and temporary memory consumption.

Preview of the Next Lesson:

We've now seen how to use high-level primitives like spinlocks and RCU. However, underlying these are even more fundamental concepts of memory ordering. What really happens when you use volatile? What is a memory barrier, and how does it differ from a compiler barrier? In our next lesson, we will dive into these low-level but critically important concepts, addressing compiler barriers, volatile semantics, and explicit hardware memory barriers.