RCU (read-copy-update)

Deep dive

How it works

In: a shared pointer to read; a new version to publish · Out: wait-free reads of an old or new version; the old version freed after a grace period · State: the pointer, a grace-period counter, one quiescent counter per reader · Cost: read = one acquire load, no shared writes; update = copy plus one grace period (order of ms in the kernel)

writer:  new = copy(old); modify(new); publish(ptr = new); synchronize(); free(old)
reader:  p = ptr (acquire / dependency);  use *p;  ...  quiescent state
time ->  [reader A uses old]--Q          [reader B uses new]
         publish ------------- grace period ends once A passed Q ---- free(old)

1. Publish: ptr.store(new, Release) (kernel rcu_assign_pointer) so the contents are visible before the pointer.
2. Read: ptr.load(Acquire) (kernel rcu_dereference, relying on address dependency ordering) inside a read-side section.
3. Grace period: wait until each thread has been quiescent at least once after the publish. In QSBR (quiescent-state-based), threads announce quiescent states explicitly; in the kernel, a context switch, idle, or user-mode execution is one.
4. Reclaim: free the old version, or queue it with call_rcu(old, free) to free in batches after a later grace period.
5. Multiple writers serialize among themselves with a lock; RCU only coordinates writers with readers.

Code

User-space QSBR (the liburcu-qsbr scheme) for a single pointer.

use std::sync::atomic::{fence, AtomicPtr, AtomicU64, Ordering::{AcqRel, Acquire, Relaxed, Release, SeqCst}};
use std::sync::Mutex;

const MAX_READERS: usize = 64;
const FREE: u64 = u64::MAX; // slot unused
const OFFLINE: u64 = 0;     // registered, not reading (counter values start at 1)

#[repr(align(128))]
struct Pad<T>(T);

pub struct Rcu<T> { ptr: AtomicPtr<T>, gp: AtomicU64, slots: [Pad<AtomicU64>; MAX_READERS], writer: Mutex<()> }
unsafe impl<T: Send + Sync> Sync for Rcu<T> {}
unsafe impl<T: Send + Sync> Send for Rcu<T> {}

pub struct Reader<'a, T> { r: &'a Rcu<T>, i: usize }

impl<T> Rcu<T> {
    pub fn new(v: T) -> Self {
        Rcu { ptr: AtomicPtr::new(Box::into_raw(Box::new(v))), gp: AtomicU64::new(1),
              slots: std::array::from_fn(|_| Pad(AtomicU64::new(FREE))), writer: Mutex::new(()) }
    }

    pub fn register(&self) -> Reader<'_, T> {
        let i = (0..MAX_READERS)
            .find(|&i| self.slots[i].0.compare_exchange(FREE, OFFLINE, Relaxed, Relaxed).is_ok())
            .expect("too many readers");
        let r = Reader { r: self, i };
        r.mark_quiescent(); // comes online
        r
    }

    /// Publish a new version, wait for a grace period, free the old one.
    pub fn update(&self, new: T) {
        let _w = self.writer.lock().unwrap();
        let old = self.ptr.swap(Box::into_raw(Box::new(new)), AcqRel);
        let target = self.gp.fetch_add(1, SeqCst) + 1;
        fence(SeqCst); // pairs with the reader's fence between its slot store and its next pointer load
        for s in &self.slots {
            loop {
                let c = s.0.load(Acquire); // Acquire: the reader's earlier reads of `old` are finished
                if c == FREE || c == OFFLINE || c >= target { break; }
                std::thread::yield_now(); // production: futex wait / batched call_rcu instead
            }
        }
        unsafe { drop(Box::from_raw(old)) }
    }
}

impl<T> Reader<'_, T> {
    /// The reference stays valid until the next `&mut self` call (quiescent/offline).
    pub fn read(&self) -> &T { unsafe { &*self.r.ptr.load(Acquire) } }

    fn mark_quiescent(&self) {
        fence(SeqCst); // earlier reads complete before announcing
        self.r.slots[self.i].0.store(self.r.gp.load(Relaxed), Relaxed);
        fence(SeqCst); // announcement visible before later pointer loads
    }
    /// Call between operations, e.g. once per event-loop iteration.
    pub fn quiescent(&mut self) { self.mark_quiescent(); }
    /// Call before blocking for a long time, so writers need not wait for us.
    pub fn offline(&mut self) { self.r.slots[self.i].0.store(OFFLINE, Release); }
    pub fn online(&mut self) { self.mark_quiescent(); }
}

impl<T> Drop for Reader<'_, T> {
    fn drop(&mut self) { self.r.slots[self.i].0.store(FREE, Release); }
}
impl<T> Drop for Rcu<T> {
    fn drop(&mut self) { unsafe { drop(Box::from_raw(*self.ptr.get_mut())) } }
}

Complexity and constants

• Read: one acquire load (plain mov on x86; ldar or a dependent ldr on ARM). Quiescent report: two fences + one store, done once per loop iteration, not per read.
• Kernel grace period: order of a few ms to tens of ms depending on HZ and load; synchronize_rcu_expedited() uses IPIs to finish in order of tens to hundreds of µs at a cost to every CPU.
• call_rcu overhead: a callback enqueue, order of tens of ns; callbacks are processed in batches.
• Memory: one old version per pending update until its grace period ends; with call_rcu, bounded by update rate × grace-period length.

Efficiency

• Cost: a read is one acquire load (a plain mov on x86), with zero shared writes. A quiescent report is two fences plus one store, once per loop iteration. An update costs a copy plus one grace period: order of a few ms to tens of ms in the kernel, order of tens to hundreds of µs when expedited (at a cost to every CPU). call_rcu is order of tens of ns per callback. Memory: one old version per pending update. Bound: grace-period latency on the write side.
• Levers:
  • call_rcu batching instead of synchronize_rcu per update — one grace period per batch of frees — frequent updates
  • QSBR flavour with explicit quiescent states — cheapest read side (Desnoyers et al.) — when you own the thread loops
  • expedited grace periods — order of tens to hundreds of µs, IPIs on every CPU — rare latency-critical updates
  • update in place for lists (list_add_rcu, list_del_rcu) — no copy of the structure — insert and delete only
  • go offline before blocking — writers stop waiting for idle readers — threads that sleep
• Naive → standard → state of the art:
  • reader-writer lock · every reader writes the lock word, which bounces between cores
  • reference-counted pointer swap (arc-swap) · simpler API, no quiescent-state discipline
  • RCU/QSBR with batched reclamation · zero shared writes on reads

Implementation notes

• liburcu flavours: QSBR (fastest, explicit quiescent states, as above), memb (read-side counter + membarrier for the writer), bp (no registration, slower). Choose QSBR when you own the thread loops.
• Use call_rcu-style deferred reclamation: writers queue (old, deleter) and a background thread runs one grace period per batch.
• Updating a structure in place (list insert/delete) works without copying: readers see the node either linked or not. Only multi-field changes need copy-then-swap.
• Kernel list primitives (list_add_rcu, list_del_rcu, hlist_*_rcu) publish with the right barriers; deleted nodes keep their next pointer so concurrent readers can continue.
• In Rust, arc-swap gives similar ergonomics with reference counts and no quiescent-state discipline; left-right keeps two copies and swaps them.

Pitfalls

• A reader that never calls quiescent() (or blocks while online) makes every writer wait forever. Go offline before blocking.
• Calling update (or synchronize_rcu) from a thread whose own reader is online: it waits for itself forever. Go offline first.
• Holding the &T from read() across a quiescent point (the borrow checker above prevents it; C code does not).
• Reading the pointer twice in one section and assuming both reads give the same version.
• Publishing with a relaxed store: readers may see the pointer before the initialized contents.
• synchronize_rcu() in a hot path or under a lock that readers need: deadlock or latency spikes.
• Kernel: sleeping inside rcu_read_lock() is forbidden in non-preemptible RCU; use SRCU for sleepable readers.

Variants and alternatives

In production

OS kernels: the Linux kernel (routing tables, dcache, module and process lists, thousands of call sites). Network and storage servers: userspace RCU (liburcu), the initial user of which is the LTTng userspace tracer, and which Knot DNS, ISC BIND, gdnsd, GlusterFS, Netsniff-ng and xfsprogs also use. Networking stacks: DPDK rte_rcu_qsbr. Language libraries: Folly rcu, Rust arc-swap and left-right for the same read-mostly pattern.

Implementations

Sources

• Paul E. McKenney, John D. Slingwine, Read-Copy Update: Using Execution History to Solve Concurrency Problems, PDCS 1998.
• Mathieu Desnoyers, Paul E. McKenney, Alan S. Stern, Michel R. Dagenais, Jonathan Walpole, User-Level Implementations of Read-Copy Update, IEEE Transactions on Parallel and Distributed Systems 23(2), 2012. paper · code
• Paul E. McKenney, Is Parallel Programming Hard, And, If So, What Can You Do About It?, chapter "Deferred Processing". book
• Linux kernel documentation, Documentation/RCU/whatisRCU.rst. docs