advanced24 min studyLesson 158 in Engineering

Read-copy-update principles

Separate publication, removal, grace-period detection, and reclamation in read-mostly concurrent structures.

On this page

What you’ll understand

  • Trace an old object through publication of its replacement and eventual reclamation.
  • Explain why a grace period concerns relevant pre-existing readers.
  • Identify synchronization responsibilities that RCU does not provide.

A routing table may be read millions of times between updates. Making every reader acquire the same lock can move synchronization work onto the hottest path. Read-copy-update, or RCU, offers a different arrangement: prepare a replacement privately, publish it using the appropriate pointer API, and defer destruction of the old object until earlier readers can no longer use it. Readers may temporarily observe different valid versions. That arrangement is useful only when the application defines which version differences are acceptable and protects each version’s lifetime.

Replace first, reclaim after the grace period

Consider a published pointer to an immutable configuration. A writer allocates and initializes a new configuration, then publishes that pointer using the matching RCU API. A reader enters a read-side critical section and obtains the pointer using the matching dereference API. Publication ordering prevents that reader from observing an incompletely initialized replacement. A reader that already obtained the old pointer may continue using the old configuration within its protected section; publication does not abruptly invalidate the earlier version.

After removing the old object from the reachable structure, the writer requests a grace period before reclaiming it. The grace-period mechanism establishes that relevant pre-existing read-side critical sections have completed. It does not require every future reader to stop arriving, nor a global instant at which no reader exists. It is also not a fixed sleep duration. The actual implementation detects progress and may conservatively wait longer than the latest old reader’s completion; the application must wait for its API’s completion signal.

tfree≥tgrace complete≥tremovet_{\mathrm{free}}\ge t_{\mathrm{grace\ complete}}\ge t_{\mathrm{remove}}
All three values are times in the same units. This ordering is necessary after removal; the chosen RCU flavor determines what establishes a valid completed grace period.↔ Scroll wide equations horizontally.

An RCU lifetime is not a writer lock

Two writers can still race while deriving and publishing replacements. RCU does not automatically serialize those updates, prevent lost changes, or make arbitrary in-place field mutation safe. A writer mutex or another proven update protocol commonly handles that responsibility. Similarly, a reader must not save a raw object pointer, exit its read-side critical section, and use the pointer later. Copy the needed value while protected or obtain a separately managed ownership reference that explicitly extends the lifetime.

Choose the RCU flavor before reasoning about allowed blocking. Ordinary kernel RCU read-side rules differ from SRCU and other specialized variants; an example written for one is not an implementation recipe for another. The synchronous synchronize_rcu path waits for a grace period. The asynchronous call_rcu path schedules a callback after an appropriate grace period, but may accumulate deferred callbacks if writers run ahead. Callback context and allocation rules also matter. Faster publication does not imply that reclamation backlog is bounded.

Version freshness and retention need separate budgets

An application should state what a read promises. Obtaining one pointer and reading immutable fields from that object gives a coherent version of those fields. Independently loading two changing pointers may combine versions unless the data structure supplies a stronger snapshot mechanism. RCU alone does not turn a multi-object operation into a transaction. Ask whether a stale routing decision is acceptable, whether related fields belong in the same replacement object, and how long a reader is permitted to retain its protected access.

Long readers and rapid replacement can increase retained memory. Rate times grace-period delay gives a rough steady-flow estimate, excluding bursts, allocator overhead, and callback execution delay. Use the queue lab as a backlog analogy, with arrival representing version retirement and service reclamation. For each separate fixed-rate run choose Reset, explicitly set both rates, predict, then Play or Step. Compare arrival two and service three with a fresh Reset followed by arrival two and service one; the second grows from four initial versions. Editing a rate retains elapsed time and recomputes the model from its initial four versions, rather than preserving a live backlog through a service change. The fluid model does not implement RCU or detect a grace period. A displayed stable queue is therefore no evidence that a reader’s pointer is safe to free.

Mretained≈u D bM_{\mathrm{retained}}\approx u\,D\,b
For a steady-flow estimate, u is retired versions per second, D is mean retention delay in seconds, and b is bytes per version. The result is bytes, not a worst-case safety bound.↔ Scroll wide equations horizontally.

An old reader and a later reader

Times are milliseconds. Reader A holds the old immutable object from time 1 to 9; B holds it from 2 to 7. At time 4 a writer publishes a replacement and removes the old object. Reader C starts at 5, obtains only the replacement, and ends at 20. Assume no escaped references.

  1. At removal time 4, A and B can still hold old references. Their protected intervals must finish before the old object can be reclaimed. B finishes at 7 but A remains active.

  2. The latest of those old readers finishes at max(9,7)=9. Time 9 is an earliest reader-based lower bound, not a promise that the implementation has already reported a completed grace period.

  3. C started after replacement and, by the stated assumptions, cannot obtain the removed object. Its ending at 20 does not by itself require the old object to remain allocated until 20. Reclaim only after the actual matching grace-period completion.

The result

The writer must wait for the relevant old readers and the API’s grace-period completion, rather than sleeping a guessed interval or waiting for all future readers.

Explore the model

Interactive lab

Interactive lab · queue

Deferred versions accumulate

Interpret arrival as retired immutable versions and service as reclamation throughput. Compare separate fixed-rate runs with Reset → explicitly set both rates → predict → Play or Step. Use (2,3), then Reset and (2,1). Rate edits retain elapsed t and recompute from four initial versions; they do not preserve an earlier backlog under a new rate.

Deferred versions accumulateFluid backlog starts at 4 and follows max(0, 4 + (λ − μ)t). The separate M/M/1 residence-time formula assumes Poisson arrivals, exponential service and λ < μ. Current readings: Fluid backlog: 4; Net rate · λ − μ: −1 /s; M/M/1 mean residence: 1 s. All parameters are adjustable with the labeled controls below.02.557.51001.534.56Elapsed time · sFluid backlogλ < μ
Fluid backlogCurrent time
Fluid backlog
4
Net rate · λ − μ
−1 /s
M/M/1 mean residence
1 s
t = 0 s

Fluid backlog starts at 4 and follows max(0, 4 + (λ − μ)t). The separate M/M/1 residence-time formula assumes Poisson arrivals, exponential service and λ < μ. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forThe fluid backlog illustrates pressure on deferred storage. It contains no read-side sections, grace-period detector, or pointer-publication proof.

Check your understanding

Which task is normally still the update-side design’s responsibility when using RCU?

Try it yourself

A service replaces 2 KiB immutable versions 500 times per second. Its approximate mean retention delay rises from 0.01 to 0.2 seconds. Estimate retained version bytes at both delays and explain what the estimate cannot prove.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Multiply update rate by delay to estimate the number of pending versions. One KiB is 1,024 bytes.

Compare with the solution

The estimates are five versions or 10,240 bytes at 0.01 seconds, and 100 versions or 204,800 bytes at 0.2 seconds. Retention grows twentyfold under these steady-flow assumptions. The arithmetic cannot establish a valid grace period, a maximum delay, or a worst-case memory bound; bursty updates and delayed callbacks can retain more.

Take it with you

  • Publication can coexist with readers of an older valid version.
  • Reclaim only after the matching grace-period mechanism establishes safety.
  • RCU does not replace writer coordination or application snapshot semantics.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.