Read-Copy-Update

A routing table read millions of times a second and updated once a minute.

A mutex makes every reader pay for a writer that almost never comes. A read-write lock is better, but readers still take an atomic operation each, and that atomic bounces a cache line between every core in the machine — so reads get slower as you add cores, which is the opposite of what you wanted.

The idea

Never modify data that a reader might be looking at. Instead:

1. Read the current version.
2. Copy it.
3. Update the copy.
4. Publish the new version with one atomic pointer store.
5. Free the old version only after every pre-existing reader has finished.

The grace period

The only hard part is step 5. When is it safe to free the old copy?

RCU’s answer relies on a rule: a reader may not sleep or block inside a read-side critical section. Given that, once every CPU has passed through a context switch, no reader can still be holding a pointer to the old version.

That interval is the grace period. synchronize_rcu() waits for it — often milliseconds, which is fine because writes are rare — or call_rcu() registers a callback so the writer does not block at all.

What it costs

Writers are expensive and serialised. Copy the structure, wait a grace period. Two writers still need a lock between them — RCU does nothing for write-write conflicts.

Readers can see stale data. A reader that started before the update sees the old version, and that is by design. RCU gives you a consistent snapshot, not the latest value.

Memory doubles during an update, and freeing lags.

The read-side rules are strict. In the kernel, sleeping inside rcu_read_lock() is a bug that corrupts memory rather than throwing. This is also why RCU is hard to offer as a general library.

Where it is used

The Linux kernel, extensively — dentry cache, routing tables, module lists, namespaces. It is one of the reasons Linux scales to hundreds of cores.

The userspace equivalents you will actually reach for:

// Java: the pointer store is the publish; the GC is the grace period.
private volatile Map<String, Route> routes = Map.of();

void update(String key, Route route) {
  var copy = new HashMap<>(routes);      // copy
  copy.put(key, route);                  // update
  routes = Map.copyOf(copy);             // publish, atomically
}

Readers just read routes. No lock, no atomic, and the volatile supplies the happens-before edge so a reader cannot see a half-built map.

CopyOnWriteArrayList is the same pattern packaged, and it is the right choice for a listener list — read constantly, written at startup. It is the wrong choice for anything written in a loop, since every write copies the whole array.