rcu-mutation

name	rcu-mutation
description	Correct discipline for mutating an RCU / lock-free pointer-based data structure (trie, tree, list, graph) that has concurrent readers — build a new node cluster invisibly, publish it, then reclaim the old nodes after a grace period. Use when writing or reviewing any mutator on a structure read concurrently under RCU (or any publish/consume scheme), especially one with allocation-failure paths.

RCU mutation: build-invisible → publish → reclaim

The safe shape for a structural mutation with concurrent RCU readers is three phases. Get the phase boundaries right and most correctness questions dissolve.

The three phases

1. Build (may fail). Allocate and fully wire the new node cluster. Touch only new nodes and their fields. The cluster must be reachable by a concurrent reader from neither direction (see "Observability"). On allocation failure, free the new nodes immediately (they were never observable — no grace period) and return; the old structure is untouched, so there is nothing to roll back.
2. Publish (must not fail). With the cluster fully built, perform the minimal set of stores that link it into the live structure. After the first such store the cluster is observable, so no failure is permitted past this point — do all fallible work (allocations) in phase 1.
3. Reclaim. Free the old nodes, deferred (call_rcu / synchronize_rcu / grace period). They were observable, so a reader may still hold a reference.

Observability — the core concept

A node is observable the moment a concurrent reader can reach it from the roots. Enumerate every channel readers traverse; in a doubly-linked structure there are usually two:

• Forward: a reachable node's child/next slot points to it (the descent).
• Backward: a reachable node's parent/prev back-pointer points to it, if readers follow back-pointers (up-walks, ordered traversal, lazy node recovery from a compressed/skip encoding).
• Sideways: a secondary reader-traversable index — an ordered sibling/cell list, a hash chain, a cached min/max endpoint — that reaches the node independently of the tree. Each such index is its own channel: a node is observable while any channel can reach it, and "unreachable through the tree" proves nothing about the index.

A write publishes (crosses into observable) the instant it links a new node into any channel of an already-reachable node. Writes that only touch a brand-new node's own fields, or links between new nodes, are internal / non-observable — do as many of those as you like in phase 1.

The classic trap: a line that looks like "set up the new node" is actually a publish because its target is a reachable node. E.g. set_parent(old_child, new_node) publishes new_node through the back channel, because old_child is still reachable via the old structure.

Rules that fall out

• Never reclaim a node that became observable without a grace period. And never make a node observable during phase 1 only to free it on the error path — that needs a grace period and leans on fragile reader-side consistency heuristics during the window. Keep the build invisible instead.
• In phase 1, wire back-pointers directly from the pointers you hold. Do NOT recover a cluster node via the read-side recovery machinery (the same code a reader uses to chase a back-pointer / decode a compressed pointer). During the build that machinery follows a back-pointer that still points at the old structure, so it returns the wrong node and you corrupt it. The mutator holds every new node directly — use that, not recovery.
• Track / free cluster nodes by an identity that does NOT need recovery. This is the same rule applied to the abort path. If your scheme has an encoding that resolves a node via a back-pointer (a skip/indirect pointer recovered through its child's parent link), do not record cluster nodes in that encoded form: the abort/free walk will resolve each tracked node to free it, and that back-pointer is still deferred (stale) → it resolves to the wrong, live node and frees it. Track the direct/plain form; if the published slot wants the encoded form, write the encoded value into the (still-private) slot just before publish, but keep the tracking/free/back-pointer-record in the plain form. (Builder helpers should therefore return the plain flag and let the caller re-encode the slot, not return the encoded one.)
• Publish ordering matters for reader consistency (not for failure). Publish the channel that stops readers from reaching about-to-be-freed nodes first. (In a re-parent: set the surviving child's new back-pointer before swinging the top forward slot, so an up-walk from that child enters the new cluster before the new cluster becomes forward-reachable and the old node is freed.) The brief 2-store window between is the normal mutation window your readers' retry/validate logic already handles.
• When several children's back-pointers are deferred together, wire them fresh-before-live. A cluster-leaf (see the realloc rule below) defers all its children's back-pointers to publish, and those children are often a mix of fresh (new, reachable only through the cluster) and live (re-parented from the old structure). Setting a live child's back-pointer is itself the back-channel publish: the instant it lands, a reader up-walking from that still-reachable child enters the cluster and can scan the cluster's other slots — including fresh siblings. So wire the cluster's own upward link and every fresh child's back-pointer , and the re-parent edge (immediately before the forward publish). Backwards, a reader enters via the live edge and reaches a fresh sibling whose parent is not yet set — and this is a transient window the reader retries past: the reader's data-dependency (consume) chain is at the live back-pointer it loaded, so a fresh-parent store sequenced that load has to the reader. It observes the stale (often NULL) parent at later wall-clock time. (Diagnosing exactly this — a parent set microseconds earlier yet read NULL — is the worked example in the lttng-tracing-root-cause-analysis skill. The single-surviving-child re-parent in the rule above is the degenerate case with no fresh siblings to strand.)

Anti-patterns (and why)

• Mutate-in-place then roll back on error. Tempting and localized, but if the mutated pointer was observable, rollback alone is a use-after-free (a reader grabbed the transient target); you must add a grace period before freeing, and the in-window correctness depends on a reader-side heuristic (e.g. "the lengths won't match so the reader retries") that is an emergent, non-local invariant, not a guarantee. Prefer build-invisible: there is no window and nothing to roll back.
• Using the published-tree insert/link API to wire an unpublished cluster. Those APIs set back-pointers via read-side recovery (see the rule above) and assume the slot is already consistent. Wire the cluster with direct field stores.

Composing build-invisible steps into a transaction

A build-invisible step is only as safe as the transaction around it.

• Propagate the step's failure; don't let a dispatch layer swallow it. When a descent/dispatch routine calls your mutation and treats its allocation failure like an ordinary "stop" (e.g. returns the same "done" signal on both success and OOM), the caller proceeds on un-built / stale state and corrupts the structure anyway — the build-invisible step's clean OOM is wasted. Thread the failure out and abort the whole transaction before any irreversible publish (before the point of no return, so there is nothing to roll back). A (void)-cast or ignored return on a fallible mutation is a red flag.
• Never publish an incomplete intermediate that a later, fallible step completes. A transaction that publishes a deliberately-partial structure (e.g. a branch holding one of its eventual two children, meant to be finished by a subsequent allocating step) is not atomic: an OOM in the later step leaves the partial structure live — often a verify-invalid / non-canonical node rather than a dangling pointer, so it's a subtler corruption that exact lookups miss. Either build the whole cluster (every step's output) invisibly and publish once, or accept that the later step's failure must roll back the earlier publish — usually impractical once the replaced node is freed. If you can only fix the first step now, say so explicitly and scope the transaction-atomicity of the rest as separate work.
• Error paths must report failure faithfully and reset out-params. Mapping an allocation failure to a benign status (NOT_FOUND, or a "duplicate found" success) tells the caller the operation didn't happen — or worse, that it did. And if an out-param was set optimistically before the fallible step (e.g. *result = removed chain, under a contract of "caller reclaims it after a grace period"), the error path MUST reset it to NULL: a caller that keys reclamation off the non-NULL out-param frees live data. Decide each error exit's (status, out-params, structure state) triple together; an error status paired with a success-shaped out-param is as dangerous as the reverse. Where a distinct out-of-memory status exists, use it — the caller's retry decision depends on distinguishing "absent" from "failed".

Worked example (userspace-rcu fractal trie compressed-split)

Splitting compressed node cn("ABCDE", child C) under parent P on insert of "ABXYZ": build cluster P→(skip "AB")→branch{ 'C'→sfx"DE"→C , 'X'→nb"YZ"→leaf }.

• Phase 1: alloc sfx/nb/branch/prefix; wire forward slots and set every new node's back-pointer directly; set the branch→sfx slot to its final skip value even though it only becomes recoverable once C->parent flips — no reader sees it yet, and the mutator never recovers through it. Never touch C or P's slot. (Install sfx with its plain flag so the API recovers it directly, then overwrite the slot with the skip value — never install the skip flag, which would recover sfx through C->parent = still cn.)
• OOM in phase 1: free sfx/nb/branch/prefix immediately; C, cn, P untouched.
• Phase 2: C->parent = sfx (back), then P.slot = skip(branch,2) (forward).
• Phase 3: free cn deferred.

"Skip-encoded" is a publication property: a skip pointer encodes the compressed node's child + length and recovers the node via that child's back-pointer, so it only resolves once that back-pointer is published. Setting the value early in an unobserved slot is fine; resolving it is a reader concern.