Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# RCU
**RCU** (Read-Copy-Update) is a synchronization scheme that lets readers access shared data with no locking overhead at all, no atomic instructions, no memory barriers, by pushing all the cost onto writers instead. It was developed for and is heavily used inside the Linux kernel, in situations with many frequent readers and comparatively rare writers, where a [[lock]] would force every reader to pay synchronization overhead just to protect against writes that almost never happen.

## The core trick

A writer never modifies shared data in place. Instead, it copies the data structure, modifies the copy, and then atomically swaps a single pointer so that new readers see the updated version. Readers that grabbed the old pointer *before* the swap keep running against the old version, completely unaware a write happened, and it's still perfectly valid data, just stale.

```c
struct data *old_ptr = atomic_load(&global_ptr);
struct data *new_ptr = copy_and_modify(old_ptr);
atomic_store(&global_ptr, new_ptr);      // publish: new readers see new_ptr
/* old_ptr is not freed yet - some reader may still be using it */
```

Because a reader's access is just a plain pointer load, with no lock and no atomic read-modify-write, readers never block, never contend with each other, and never contend with the writer either. The writer pays all the cost: making the copy, and waiting to reclaim the old version.

## The hard part: knowing when it's safe to free

The old copy can't be freed the instant the pointer is swapped, since a reader that loaded the old pointer just before the swap might still be using it. RCU solves this with the concept of a **grace period**: the writer waits until every reader that could possibly have seen the old pointer has finished (in the kernel, this typically means every CPU has passed through a context switch, since RCU readers are not allowed to sleep while holding a reference). Only after the grace period elapses is it safe to free the old copy.

```
writer: swap pointer -> wait for grace period -> free old copy
readers: never block, never know a write is in progress
```

## Tradeoffs

RCU trades write cost and memory for essentially free reads: writers are more expensive (a full copy plus waiting for a grace period) and memory usage temporarily doubles for a modified structure (old and new versions coexist until reclamation). This is a clear win when reads vastly outnumber writes, and a poor fit when writes are frequent or the protected structure is large enough that copying it on every write is itself expensive. This is the same underlying design goal as [[hazard-pointer|hazard pointers]], safely reclaiming memory that concurrent readers might still be using, but RCU trades hazard pointers' per-object tracking for a coarser, cheaper "wait for everyone to pass a checkpoint" scheme.