Write and delivery path¶
Scope: the dispatch structure of the C++23 reference implementation under
core/ and what it costs on one host. Not the standard, and not
normative — the obligations any implementation must meet are in
../../reference/15-concurrency-and-scaling.md.
The read half of the runtime is 00-scaling-and-serialization.md;
the failure semantics of a dropped allocation are
../allocation-and-backpressure.md.
A write is the more expensive half of the runtime. A read touches one vertex; a write stores a value and then delivers it to every edge on that vertex and on every ancestor that has a listener, through three legs with different costs. This page describes that machinery: which lock each stage takes, where the buffers come from, and what the delivery legs copy.
1. Write path¶
write_impl (core/src/graph.cpp:graph_t::write_impl) is the one body behind every write overload. It takes
no map lock. The stages, in order:
stage |
what it does |
|---|---|
ACL gate |
|
branch fork |
a POINT payload with the branch bit set decomposes through |
store |
|
deliver |
|
The handle overload is the whole of write(vertex_handle_t, rope_t, caller)
(graph.cpp:graph_t::write(vertex_handle_t v,) — a call straight into write_impl. A path-addressed write resolves
first, and find_ptr takes map_mutex_ in shared mode (graph.cpp:graph_t::find_ptr), so the path overload
(graph.cpp:graph_t::write(const path_t& path,) pays one shared map hold that the handle overload does not.
One allocation-shaped detail on the store leg, and it used to be two. Every role delivers
without recloning. The retaining roles deliver the exact pointer store_value handed back
(graph.cpp:graph_t::write_impl). A HANDLER has no such pointer — the user handler consumes the value
and nothing is published — and until #1505 it built a nothrow try_clone_rope before storing
and delivered from that. It does not now: handler_write_deliver builds one value on its
own frame by moving the writer’s links in (a block only past kUnstoredInline links, taken
before the handler runs), hands it to on_write by reference (RFC-0028 D10) and then to
deliver_vertex (graph.cpp:graph_t::handler_write_deliver). dispatch_edge_target’s per-edge clone is gone too
(RFC-0028 slices 4 and 7): a stored target adopts the published block through the adopting
store_value overload — one retain, no allocation — a HANDLER target is handed that same
block by reference, and a nothrow value_t::try_rope clone is left only for caller-owned
storage delivered to a stored target.
1.1 Write versus retire¶
Because write_impl takes no map lock while retire mutates the vertex under the unique one,
the two can overlap. Serialising them is the calling plane’s responsibility, not the graph’s
(#1477) — the doctrine is stated at the handle overload (graph.cpp:graph_t::write(vertex_handle_t v,). A map lock on the
write path was refused as a hot-path tax on the leg ADR-0019/#1431 made branch-free, and a
stateful “the caller holds a guard” assert was refused because the graph cannot name the guard.
What the graph does owe is that the overlap is well-defined rather than UB: every member a
lock-free reader touches here is atomic — the LKV slot, edges_, ext_ and its value seam, the
subscriber counters, flags_, retire_gen_, delivery_mode_ (#895) and, since #1477, role_
(core/include/libtracer/vertex.hpp:vertex_t::role_). write_impl snapshots the role once per frame
rather than re-reading it at each fork, so a write that overlaps a retire acts on one coherent
answer — the retiring occupant’s role or the placeholder default — and never on a mix.
The transport plane shows what a plane’s own fence looks like: ctl_txn_t’s ops_m_ (#492 S6)
is held across both phases of its decide-then-act seam, which is what makes its window
unreachable. Any future two-phase scheme un-masks the same window and owes itself the same fence.
2. Edge snapshot¶
Delivery runs outside the vertex lock, because a callback or a re-dispatch may re-enter the
graph. The edge list therefore has to be copied out first. fan_out (graph.cpp:graph_t::fan_out) does that
in one call to snapshot_edges (core/include/libtracer/vertex.hpp:vertex_t::snapshot_edges), which takes no
lock at all (#635): it copies the vertex’s PUBLISHED, immutable-after-publish edge array
(subscriber.hpp:edge_pub_t) into one of two buffers under a bounded per-participant edge pin
(core/include/libtracer/edge_pin.hpp:pin_t), and releases the pin before the caller’s first
dispatch_edge. The stripe mutex used to be taken here, which serialized the publishes of
every vertex that merely hashed to the same stripe — ×16.6 at twenty-four threads
(ADR-0075). It
still serializes writer-vs-writer on the control plane, where a mutation builds the new array
and swaps it in (vertex.hpp:vertex_t::try_publish_edges); the displaced array is scanned and freed on the mutator’s
own thread, outside the lock, once no participant announces it (subscriber.hpp:scan_retired_edges).
It reaches that call only when something subscribes here. fan_out opens on
own_subs_ordered() == 0 ⇒ return (#635), so an unobserved write — and every placeholder
ancestor a bubble_up walks past — never touches the stripe at all. That gate is why the
count is read seq_cst where a delivery is skipped and relaxed everywhere else: it decides
whether the vertex’s own fan-out happens, so it has to be ordered against a subscribe taking
ADR-0049’s latch, or a write racing the subscribe reaches neither leg. mark_pending is the
deferred half of the same decision and reads the same ordered count
(#1140): its skip omits the sweep
mark, so the vertex enters no sweep set and only a later write can re-mark it — omitted work,
not deferred work, and the same lost delivery a skipped fan-out would be. Both are the near
axis, the vertex’s OWN count, where the publisher writes the very LKV the racing subscriber’s
latch reads.
The ancestor gate is the other axis and stays relaxed: deliver_vertex and
mark_pending both read listeners_above() relaxed, and it needs no ordered twin
(#854, measured and REFUTED): the latch a
subtree subscribe takes snapshots the subscribed ancestor’s own LKV, never a descendant’s, so a
stale zero at that gate is indistinguishable from the write linearizing before the subscribe.
Neither near-axis pairing can be exercised by any x86-64 test: a seq_cst store there lowers
to a locked xchg, so even a relaxed later load of zero is ordered in hardware and the
anomaly cannot appear. The coverage is the weakly-ordered ubuntu-24.04-arm CI leg
(core-ci build-test-arm64), which is the same memory model the shipped rv32 targets have;
the host guards in graph_test pin the program-order half only, and say so.
The two-buffer split is the point. fan_out chooses which pair of buffers to hand in from the
lock-free own_subs() count:
shape |
call |
overflow buffer |
|---|---|---|
wide, |
|
a persistent |
small, or a nested wide fan-out |
|
an empty local vector that never allocates unless the snapshot spills |
inline_buf is an edge_snapshot_t, a raw byte array placement-constructed into, so a small
fan-out neither allocates nor pays the zeroing a default-constructed edge_view_t array would
(subscriber.hpp:edge_snapshot_t). Its width is kInlineFanout — the no-heap small-fan-out snapshot width,
edge_snapshot_t::kCapacity, 8 (vertex.hpp:vertex_t::kInlineFanout, subscriber.hpp:edge_snapshot_t::kCapacity). A warm wide publish reuses the
thread-local vector’s capacity and so allocates nothing either.
own_subs() is read without the lock, so the width it reports can be stale.
That costs nothing but a re-read: snapshot_edges re-checks the width against the published
array (graph.cpp:graph_t::fan_out, vertex.hpp:const bool use_heap =), so a subscriber added between the count and
the copy costs at most one fallback allocation on the small path and never a wrong answer. Re-entrancy is
handled by a tls_busy flag: a subscriber callback that re-publishes takes the local-buffer
path, so the outer fan-out’s thread-local buffer is never aliased, and the flag resets on scope
exit (graph.cpp:graph_t::fan_out).
Both allocations inside the snapshot are nothrow. An unreservable overflow vector degrades the
snapshot to the first kInlineFanout views and drops the rest of that delivery; an edge whose
owning copies cannot be cloned is skipped, dropping that one delivery (vertex.hpp:vertex_t::copy_published).
Neither can abort. A thread that cannot claim a pin cell — more concurrent publishers than
kEdgePinSlots — copies the current array under the stripe mutex instead, which is the
pre-#635 path for those threads and nobody else; correctness never depends on the constant.
3. Dispatch tree¶
Declared in core/include/libtracer/graph.hpp, all private:
function |
declaration |
role |
|---|---|---|
|
|
the per-vertex delivery unit both |
|
|
return at once if nothing subscribes here; else snapshot under the stripe lock, then |
|
|
the one dispatch of an edge’s three legs, shared by |
|
|
the local re-dispatch leg — a delivery into another vertex |
|
|
the remote leg — a |
|
|
vertical fan-out to every registered ancestor’s subscribers |
dispatch_edge is always_inline (graph.cpp:graph_t::dispatch_edge) precisely so its body stays in the
fan-out loop; the target and remote legs are split into noinline helpers to keep that body’s
inline estimate small, because the in-process callback leg is the hot case. The three legs are
independent and any subset may fire for one edge: a callback pointer, a target key, and a
non-empty link name.
bubble_up (graph.cpp:graph_t::bubble_up, entered only when listeners_above() > 0, graph.cpp:graph_t::deliver_vertex) walks parent pointers, which
are immutable once linked, and so takes no lock at all; a placeholder ancestor holds no edges
and its fan_out is a no-op. An idle write — nobody subscribed above — pays one relaxed load.
The subscriber gate is what makes the paragraph above true, and nothing else does.
snapshot_edgesused to take the vertex stripe mutex before it looked at anything, and a stripe is shared bykVertexLockStripes-many unrelated vertices. Reach it unconditionally and an unobserved write took a lock it shares with vertices it has nothing to do with, and every ancestor abubble_upvisits took another — which is whyfan_outopens onown_subs_ordered() == 0 ⇒ returnand why the idle write costs one load and no lock. That load isseq_cstrather than relaxed because its skip has to be ordered against a subscribe taking ADR-0049’s latch;vertex_t::own_subs_orderedcarries the pairing that requires it (the ancestor gatelisteners_above()stays relaxed by ruling — #854). The rationale and the measurements behind the gate are ADR-0064’s.The gate is still what makes an idle write free, but it is no longer the only thing standing between a fan-1 write and the stripe:
snapshot_edgesnow reads a published, immutable edge array under an edge pin and takes no lock at all (ADR-0075).
4. Delivery termination¶
A delivery landing on a target applies exactly the target-local effects of a write — store,
await wake, and the target’s own handler reaction, all inside store_value — and never
re-dispatches to the target’s own :subscribers[] and never bubbles (graph.cpp:graph_t::dispatch_edge_target).
Propagation past a target is the target’s own logic: a controller re-emits on its execution, a
handler re-emits when it chooses.
The consequence is structural rather than defensive. A dispatch-level subscription cycle cannot
form, so there is no depth cap, no dedup, and no drain queue, and nothing to size. The former
kMaxDispatchDepth is deleted with nothing replacing it (graph.hpp:There is no in-process). An application that
wants pure relay subscribes the consumer directly.
Rejected alternative: a depth counter threaded through dispatch. It would bound a recursion that the termination rule makes impossible, and its constant would be a synthetic limit with no resource behind it.
Cited: ADR-0051 — Delivery terminates at target, no dispatch limits, RFC-0007 — Delivery terminates at target.
5. Remote delivery legs¶
fwd_router_t::deliver_remote (core/src/fwd_router.cpp:fwd_router_t::deliver_remote) is the sink the remote leg calls.
It has two legs, and only one of them copies payload bytes.
The default full-route leg copies nothing. It emits
FWD{ op=WRITE, dst=<stored return route>, src=<empty PATH>, payload=<VALUE> } as a
retained send (RFC-0028 §6.9): three head spans on the stack (a fresh header, the stored route,
an empty src) and the value by reference, handed to transport_t::send(head, value)
(fwd_router.cpp:fwd_router_t::deliver_remote). The header is a stack_writer_t<16> — the FWD header of at
most 6 bytes plus the 5-byte op TLV — and both constant TLVs are constexpr arrays with no
runtime construction (fwd_router.cpp:fwd_router_t::deliver_remote). The route bytes were copied once at subscribe
time, so a delivery re-uses them by reference; a multi-link value crosses as its own segments,
with no flatten. The link lowers head ++ value.links() through its own 8-entry inline table,
drawing an overflow block from its egress source only past five links; a link that QUEUES the
frame keeps one reference to the value and copies only the head, so the payload is never
gathered into a queue slot.
Until slice 9 this leg drew the iov table itself, as a mem::block_array_t over the graph’s
injected ctl block_source_t, and a refused reservation dropped the delivery. That container
replaced std::vector + tr::detail::try_reserve in
#981, because that helper answers by value
only where the growth throws (core/include/libtracer/mem_heap.hpp:try_grow): under
-fno-exceptions it can only probe the global heap, free the probe block and then run the throwing
reserve, so a writer-thread context switch in that window makes the reserve abort() the node
(#850, the residual
#923 could not reach). The link-side
table keeps that property — iov_table_t grows by one refusable try_alloc with no second step —
and the delivery itself no longer allocates at all. The try_* sites whose element types cannot
ride that relocation keep the residual, tabulated in
../allocation-and-backpressure.md and stated at each site.
The COMPACT leg is the one that flattens. value.try_materialize(*flat_)
(fwd_router.cpp:fwd_router_t::deliver_remote) precedes the compact encode, because a COMPACT wraps a contiguous
payload. Single-link — the common case — that materialize is a zero-copy adopt; a multi-link
value pays one flatten per delivery, out of the router’s INJECTED byte backend rather than the
global heap. A REFUSED flatten drops the delivery (fwd_router.cpp:fwd_router_t::deliver_remote) — since #917 that is a
test on the named refusal, so a legitimately empty value is delivered rather than swept up with
the OOM by an empty() guess.
Auto-promotion advertises the label once per flow and then streams
compact frames; a dropped fresh ADVERTISE self-heals through the peer’s HANDLE_NACK
(RFC-0004 — Remote operation
addressing
§E.1).
So delivery compaction trades a per-delivery flatten on multi-link values for a smaller frame. On single-link values it costs nothing; on roped values it is the one place the delivery path copies payload.
6. Delivery drops¶
Three conditions make a target-edge delivery impossible, and all three drop that one delivery
rather than failing the write — the write itself succeeded and the other legs still ran. Two
more sheds happen further up, before an edge is ever dispatched. Two more again come from the
net plane, which performs deliveries the graph never sees. What is counted is the drop
(graph.hpp:graph_t::delivery_drops_t):
struct delivery_drops_t {
std::uint64_t no_target = 0;
std::uint64_t denied = 0;
std::uint64_t out_of_memory = 0;
std::uint64_t fan_out_truncated = 0;
};
counter |
condition |
site |
|---|---|---|
|
the target PATH resolved to no live vertex — retired, or never created |
|
|
a subscription edge’s delivery was refused by the target’s |
|
|
a WRITE was refused at the graph’s own gate — the API write, the |
|
|
a net-plane route resolved to no vertex ( |
|
|
a |
|
|
a target delivery’s store was declined — the slot publish, the receiving ring’s admission, or the clone a HANDLER target still takes |
|
|
the wide-fan-out overflow buffer could not be reserved, so every edge past the inline prefix was abandoned |
|
Two out_of_memory sites used to sit in this table and no longer can, both removed the same
way — by deleting the allocation rather than the report.
An edge whose owning link/caller copies could not be allocated was skipped by the snapshot. #1448: the dispatch snapshot now holds a refcount share of the immutable cold half and copies no bytes, so the per-edge snapshot has no allocation left to fail and
snapshot_drops_tcarries onlytruncated.A HANDLER write whose notify clone failed shed the vertex’s whole fan-out, counted one per subscriber — the widest drop in the graph. #1505:
store_value’s HANDLER leg only reads the value and returns the null “consumed” sentinel, so the caller’s rope is still live and is delivered directly. There is no clone, so there is nothing to fail — the shed is impossible, not narrower.graph_oom_softfail_testpins both as inverted assertions: the same pinpoint injection that used to produce the shed now produces a full fan-out and a flat counter.
OUT_OF_MEMORY remains reachable, so the reason code is not dead: mark_pending’s shed pending
mark still raises it at own-subs width, and dispatch_edge_target’s declined store at width 1.
#854’s own-subs-wide ruling is annotated
by #1505, not overturned — the width rule is unchanged, one of its legs simply became
structurally unreachable.
The handler shed and the snapshot sheds were uncounted until #896, and the handler one is
why that mattered: it sheds
every subscriber of the vertex and still returns success, so delivery_drops() — the only thing
that could say so — read zero while a whole fan-out evaporated. The unit of every counter is
therefore a delivery, not an event: a shed fan-out of N counts N, which is why the
remaining snapshot shed is tallied inside vertex_t::snapshot_edges (vertex.hpp:vertex_t::snapshot_drops_t, its
snapshot_drops_t) and folded by fan_out (graph.cpp:graph_t::fan_out) through
count_snapshot_drops (graph.cpp:graph_t::count_snapshot_drops) rather than counted as one at the caller. Every site on
this plane goes through one door, count_drop (graph.cpp:graph_t::count_drop), so a path here that abandons an
admitted delivery without counting it is a visible omission.
The net plane reaches that door through exactly one public method, count_external_drop
(graph.hpp:graph_t::count_external_drop, graph.cpp:graph_t::count_external_drop), which maps its two causes onto count_drop and adds no
second counting mechanism (#1068). It is a method rather than a friendship because the
counters are a published surface while the internal drop sites are not: a deliverer needs to
add to the numbers, not to reach into the machinery that maintains them. denied is absent
from it on purpose — a refusal is counted at the WRITE gate, on every plane, so a router that
also counted the PERMISSION_DENIED it discards would report one refusal twice.
The two sheds that happen before the fan-out went through this door in #1003, and the plane
boundary that used to qualify this section is gone. A STREAM ring-append refused under
allocation pressure abandons the write’s whole fan-out without ever reaching a dispatch site —
for a STREAM the ring drain is the fan-out, so the skipped entry is a delivery every
subscriber loses, and the eager delivery then drains zero and returns before one edge is
snapshotted. A mark_pending OOM leg is the same loss deferred: an unmarked vertex rides no
sweep, so with no later write to re-mark it the assigned value is never delivered at all.
Both now count at the same one-per-subscriber width as the handler leg. The write still
answers SUCCESS in both cases — the value publish landed, and a stream’s history is
bounded-lossy by contract (RFC-0008 §E) — which is precisely why the counter has to carry the
loss instead. vertex_t::store reports its shed by reference (store_drops_t, the shape
snapshot_drops_t uses) because the storage layer owns no counters; store_value passes the
tally on as a required out-parameter, so a graph write path cannot abandon a delivery by
forgetting to ask. Whether a shed cost a delivery stays the caller’s call: a branch notify
fans its slice out eagerly and flushes the drain cursor, so its shed costs history rather than
a delivery and is deliberately not counted.
Read delivery_drops() as what the vertex shed, with one documented exclusion: the ancestor
legs a bubble would also have served are not counted, because #854’s close ruling dropped
ancestor-leg drop instrumentation outright.
delivery_drops() (graph.hpp:graph_t::delivery_drops, graph.cpp:graph_t::delivery_drops) is the only record that any of this
happened. Without it, a node whose target was retired, or whose fan-in gate denies the edge’s
stored caller, drops every delivery for the rest of its life with nothing anywhere to say so.
Two properties of the counters are deliberate. They are counted, never enforced — nothing in the library reads them, so a deployment chooses whether to alarm. And the loads are individually relaxed rather than one atomic snapshot, so a reader racing a delivering thread can see a torn total: making it coherent would put a lock on the drop path to serve a diagnostic, and the useful reading of a monotonic counter is “is this growing”, not an instant.
The out_of_memory cause is where this page meets allocation policy. What a nothrow clone
failure means, which resource it drew from, and why exhaustion is a value rather than an abort
are in ../allocation-and-backpressure.md.
Cited: ADR-0026 — Consumer-initiated subscription is a client write for the fan-in gate.
7. Cost¶
Every figure below carries its conditions from the record named beside it. Nothing here is re-derived, and no figure appears without its shape.
The delivery stripe lock. Instrument bench/bench_lkv_slot in graph mode, ablation by
deleting the lock, fan-1 writes, median of 3 runs, 24-thread host:
T |
lock in place |
lock removed |
|
|---|---|---|---|
1 |
11.25 M/s |
11.21 M/s |
×1.00 |
4 |
7.56 M/s |
22.58 M/s |
×2.99 |
8 |
4.58 M/s |
34.26 M/s |
×7.47 |
16 |
4.61 M/s |
57.97 M/s |
×12.56 |
24 |
4.75 M/s |
78.73 M/s |
×16.59 |
This is the adversarial shape: T writers on T distinct vertices deliberately chosen to
collide on one stripe. The two halves belong together, because the second is what stops the
first from justifying work. On the realistic shape — writers that do not collide on one stripe
— removing the same lock is 1.02×. The ×16.6 arm carries its full T sweep, run count and
host; the 1.02× carries its shape and no run count or spread, so it settles the direction and
not the magnitude. ×1.00 at T=1 is the same measurement’s own control: the lock genuinely is
free where it sits, for one thread. Source: ADR-0064 — LKV publish is waiterless and the slot
becomes
lock-free,
tracked at #635. Deleting the lock was
never the fix — snapshot_edges copies the edge list, and a concurrent add_edge /
clear_edge would race.
Landed (2026-08-03, ADR-0075). What replaced the lock is a published immutable edge array read under a bounded edge pin, so the copy is race-free without excluding anybody. Re-measured against the same arm on the same host under the #807 protocol (15 interleaved pairs, medians, disjoint ranges): ×3.59 at T=4, ×9.21 at T=8, ×16.17 at T=16, ×19.35 at T=24, with aggregate throughput monotonically non-decreasing across that sweep — the negative scaling is gone. The distinct-stripe control stays at unity, and the single-threaded arm, pinned, is ×1.13 faster.
The write path’s absence of a map lock, as a control arm. The has_registered_child
ablation that removed the map lock from every read is a 1.00× no-op on the write path:
spread-fan0 writes at T=8 run 35.4 M/s stock and 35.4 M/s ablated, three runs, medians, host
AMD Ryzen AI 9 HX PRO 375 (12 physical cores / 24 SMT threads, Release -O3, GCC 14,
libstdc++). A control arm at 1.00× is the evidence that write_impl never took the lock; the
read side of the same table is in 00-scaling-and-serialization.md §3.
The per-slot name digest on the forward demux mount scan. Instrument
bench/bench_forward_demux, 8 alternating rounds across two builds. The scan’s marginal cost
over a fixed-position hop falls 35 ns to ~0 at 8 links, 86 to 2 at 16, and 333 to 17 at 64
links (95% removed), with the fixed-position hop itself unchanged within ±2 ns
(core/CHANGELOG.md:1509-1513). The digest is a filter and never a decision — live() and the full
compare still gate every answer — and the two digest functions are pinned against each other
directly by test_digest_paths_agree
(core/tests/registry_teardown_test.cpp:test_digest_paths_agree), because a disagreement would throw nothing and
break no obvious test; the registry would simply stop resolving the affected name, which reads
as a routing bug arbitrarily far away. Tracked at
#660. The record for this figure names its
instrument and round count but not its host.
A digest’s fixed cost is part of its measurement. The first mount digest removed 91% of the scan cost and added ~30 ns — a fifth of a whole forward hop — to every lookup. Measuring only the axis being improved hides that completely, and any further filter on this path carries the same risk.
8. How measurement goes wrong here¶
A plausible claim |
What checking shows |
The check that decides it |
|---|---|---|
The |
True at T=1 and only at T=1. From T=2 it is the dominant term on the write path: ×16.59 at T=24 on distinct vertices sharing one stripe |
Re-run the ablation across the whole thread sweep. A single-thread result generalized to all thread counts is not a result about a lock |
The stripe lock is the residual on the read path |
|
Read the call graph before attributing a cost to a lock |
A digest that removes 91% of a scan is a win |
It also added ~30 ns to every lookup — a fifth of a forward hop — which the improved axis does not show |
Measure the axis not being improved, on the same binary |
A ×16.6 lock removal describes the workload |
×16.6 is the shape built to collide on one stripe; the shape that does not collide measures 1.02× |
Run the adversarial and the realistic shape in the same session, and quote both |
A zero-subscriber write skips the delivery machinery |
It does since #635 and did not before — |
Bench the fan-0 topology, not only fan-1 — and when a doc states a cost model, check the code keeps it |
Removing a lock cannot make a shape slower |
On the ONE-shared-vertex fan-0 arm, removing the stripe lock from the idle path made it slower: the mutex was accidental admission control in front of libstdc++’s spin-locked |
Keep a true-sharing arm alongside the false-sharing one; a change that helps one can hurt the other |
A wide fan-out allocates per publish |
A warm wide publish reuses the thread-local buffer’s capacity; a cold one, and a nested re-entrant one, allocate |
Time the second publish and the first separately; a re-entrant callback puts you on the local-buffer path |