16. Region transfer: fearless messaging
Chapter 12 sent a region through a channel and said that chapter 16 was where the trick became a technique. Two questions were left open. The first is how big the graph is allowed to be, and the answer is the one chapter 8 gave about cycles: it does not matter, because the region is the unit and the region moves whole.
Here is the ring from §8.4 — three documents, each pointing at the one after it and the one before it, the ends met — handed to a proc that never allocated any of it:
struct Doc { title: str, words: int, newer: handle Doc, older: handle Doc }
fn walker(inbox: channel[region], out: channel[str], docs: Pool[Doc], head: handle Doc) -> int {
let store = inbox.recv() else |_| { return 1 }
var cur = head
var line = ""
in store {
for _ in 0..4 { line = "{line}{docs[cur].title} "; cur = docs[cur].newer }
}
out.send(line)
0
}
fn main() -> !int {
let inbox = channel[region](1)
let out = channel[str](1)
let store = region(pool(Doc))
var docs = in store { Pool[Doc]() }
var hs = in store {
var h = List[handle Doc]()
for _ in 0..3 { (mut h).push((mut docs).reserve()) }
h
}
in store {
var titles = List[str]()
(mut titles).push("regions")
(mut titles).push("moves")
(mut titles).push("errors")
for i in 0..3 {
(mut docs).init(hs[i], Doc {
title: copy titles[i],
words: (i + 1) * 100,
newer: hs[(i + 1) % 3],
older: hs[(i + 2) % 3],
})
}
}
let w = spawn proc walker(inbox, out, docs, hs[0])
inbox.send(move store)
print(out.recv() else |_| { return 1 })
0
}
$ lupin ring.lu
regions moves errors regions
16.1 ch.send(move r)
Four documents printed from a three-document ring, which is how you know the walk went round. Everything interesting about that program is in one line:
inbox.send(move store)
The region changes owner. Not the documents — the region, one value, and with it every object inside it, every string inside those, and every edge between them, including the two that point backwards and the one that closes the loop. The send moves one word. There is no traversal to serialize the graph, no pass to fix up pointers on the other side, and no step whose cost depends on how many documents the shelf holds. A million documents and three move at the same price, because the price is the region’s.
The safety argument is equally short, and it is not new. A region has one
owner (§8.3). move transfers the owner (chapter 7). After the send, the
sender’s store is empty and the language enforces that with the trap
chapter 12 printed — use-after-move, citing [mem.tier0.move.2], the
same clause as a moved string field. So at every instant exactly one
proc can reach the graph, and “who else is touching this?” is not a
question the program can ask, because it has no way to spell a second
reacher.
Notice what crosses besides the region. docs and hs[0] are
parameters of walker: a pool and a handle, which are an offset table
and an index-plus-generation. They are Copy-shaped values, which is
why they cross a signature under the rule §12.1 gave for channel
payloads, and they are meaningless without the region — a handle into a
region you do not own resolves to nothing. That is the shape of a moved
graph in wolf: the addresses are indices, so they survive the move, and
the memory they index arrives under new ownership in the same message.
Two procs, one word
The receiver above is a proc rather than a task, and the substitution
cost nothing: spawn proc walker(...) where chapter 12 wrote
spawn(fn() { ... }). That is worth pausing on, because it is the claim
the whole part has been building toward. A failure domain boundary and a
task boundary are the same boundary as far as data is concerned. The
rules that make a send safe are the memory model’s, they were fixed in
Part 2, and adding fault isolation on top of them required no new rule
about data at all.
Which means a design can move procs around late. Start with tasks in one scope because the work is a pipeline; discover that one stage corrupts its own state and should die alone; promote that stage to a proc. The data path does not change, the channel does not change, and the payload rule does not change.
When inference merges what you know is disjoint
One honest cost of a granule this size. Region inference (§8.1) puts allocations in the region the surrounding code is using, and it is conservative: two collections built in the same window live in the same region, so moving one moves both, and the send that should have handed over a batch hands over the batch and the scratch space it was built with.
The ladder out of that has three rungs and you should climb them in order.
Restructure. Build the thing you are going to send in its own
window. let batch = region() and in batch { … } around the part that
travels is not a workaround; it is the same act as choosing which
variables are locals of which function, and it reads that way afterwards.
Most merges dissolve here.
Annotate. When the two lifetimes genuinely interleave in one function, name both regions and open them explicitly — §8.6’s two open windows, checked disjoint by the compiler, with the border rule doing the policing. The cost is two names and a brace; the benefit is that the disjointness is now a claim the compiler is holding you to rather than a comment.
Reach for unsafe. Last, rarely, and with chapter 9’s discipline:
one door, a # Safety note that says which region the pointer belongs
to, and an audit surface that a reviewer can grep. If you find yourself
here for a messaging problem, the shape is almost always wrong — the
first two rungs handle the cases that arise from real programs, and this
one is for the cases that arise from libraries.
Exercise 16-1 (comprehension · lupin) — The sender builds a list
inside a region — two pushes — and sends the region. Predict: does the
receiver’s in r2 { … } block run before or after both pushes are
visible, and what synchronization made that true?
fn main() -> !int {
let ch = channel[region](1)
var got = 0
scope s {
s.spawn(fn() {
let r = region()
let xs = in r {
var v = List[int]()
(mut v).push(41)
(mut v).push(1)
v
}
ch.send(move r)
})
let r2 = ch.recv() else |_| { return 1 }
got = in r2 { 42 }
}
print("received {got}")
0
}
Exercise 16-2 (fingers · lupin) — Make the transfer carry real
freight: build a two-element list in main, send the region to a
receiving task, and have the receiver sum the list it never built.
Print the sum from the receiver’s side.
Exercise 16-3 (extension (break-it-on-purpose) · lupin) — Construct
the smallest program in which a sender touches a region after sending
it with move. Predict the exact trap kind before running — it is one
you met in chapter 7, not a new one.
16.2 Freeze, then share
move is the wrong verb when the answer is “everybody, forever.” Two
shards both want the published shelf, neither writes to it, and there is
nothing to hand over:
struct Doc { title: str, words: int }
fn reader(store: List[Doc], out: channel[int]) -> int {
var sum = 0
for d in store { sum += d.words }
out.send(sum)
0
}
fn main() -> !int {
let out = channel[int](2)
let store = freeze region {
var docs = List[Doc]()
(mut docs).push(Doc { title: "regions", words: 900 })
(mut docs).push(Doc { title: "moves", words: 640 })
docs
}
let a = spawn proc reader(store, out)
let b = spawn proc reader(store, out)
let x = out.recv() else |_| { return 1 }
let y = out.recv() else |_| { return 1 }
print("two procs read one snapshot: {x} and {y}")
0
}
$ lupin published.lu
two procs read one snapshot: 1540 and 1540
One shelf, two failure domains reading it at once, no lock, and no copy:
store crossed both signatures by reference because it is imm, and
imm data has no writers to race with. That is §8.5’s cadence doing
concurrency work — freeze was irreversible for memory-model reasons in
Part 2, and irreversibility is exactly what makes it safe to hand to a
proc that might die while reading, because there is nothing a dying
reader can leave half-done.
The two verbs divide the world cleanly enough to make a decision table that fits in four lines:
shape of the data verb what the receiver gets
one consumer, will mutate it move the only reference there is
many readers, nobody writes freeze a reference, no copy, no lock
many readers, rebuilt periodically freeze a new edition each rebuild
two writers neither redesign: one owner per datum
The third row is the one people miss. freeze does not mean forever —
it means immutable for the life of that region. A routing table rebuilt
every thirty seconds is built mutable in a fresh region, frozen, and
published; readers holding the old edition keep reading it until they
pick up the new one, and the old region dies when its last reader lets
go. Immutable-per-edition is the pattern; there is no need for a lock at
any point in it, and no reader ever sees a half-built table.
The fourth row is not a gap. Two writers to one datum is a design with
no owner for the datum, and the language’s answer is to make you pick
one: give it one owner and send messages to it (§14.3’s
mailbox), or split it so each writer owns a piece. Mutex and when
(§12.4) exist for the residue where genuinely shared mutable state is the
right answer, and the residue is smaller than most codebases assume.
Exercise 16-4 (comprehension · lupin) — Ten squares are frozen into
table; two tasks each read one entry and send it back. Predict the
printed number, and answer precisely: how many copies of the table exist
while both tasks read it?
Exercise 16-5 (design) — For each payload, choose move or
freeze and defend it in one sentence: (a) a parsed configuration read by
every worker for the process lifetime; (b) a request’s parse tree handed
from parser to executor; (c) a routing table rebuilt every 30 seconds and
read constantly; (d) a 2 GB index segment consulted by eight shards.
16.3 The honest lineup
Four languages, one workload: a producer builds a graph, a consumer walks it. Each of these designs is in production at a scale wolf has not approached, and each pays for message-passing safety at a different moment. The comparison is about when the bill arrives.
Erlang copies. A send deep-copies the message into the receiver’s
heap, so the receiver reads private memory and no coordination exists to
get wrong. The bill arrives at the send, in full, proportional to the
size of the graph. For small messages it is invisible; for a
million-node tree it is the program’s dominant cost, and the standard
remedy — a binary large enough to be reference-counted instead of
copied — is a special case in the runtime rather than a general answer.
What the copy buys is worth stating plainly, because it is something no
move can: the same send works to a process on another machine, with the
same semantics. Erlang bought distribution, and paid for it here.
Go shares. A channel of pointers costs one word, exactly as wolf’s region does, and nothing in the type system says the sender has stopped writing. The convention is that it has; the enforcement is the race detector, which finds what the test happens to execute. A multiword value written while another goroutine reads it can also tear — Go’s memory model documents this — so the failure mode is not only stale data but data that never existed. Go’s answer is discipline and tooling, and it works at enormous scale, with the caveat that “we forgot the convention here” is a bug class rather than a compile error.
Rust locks. The safe spelling for a shared mutable graph is an
Arc<Mutex<T>>, and it is real code that compiles:
pub fn shared_mutable(docs: Vec<Doc>) -> u32 {
let shelf = Arc::new(Mutex::new(docs));
let mut handles = Vec::new();
for _ in 0..2 {
let shelf = Arc::clone(&shelf);
handles.push(thread::spawn(move || {
let guard = shelf.lock().expect("the shelf's lock is poisoned");
guard.iter().map(|d| d.words).sum::<u32>()
}));
}
handles
.into_iter()
.map(|h| h.join().expect("a reader panicked"))
.sum()
}The bill arrives on every access: a refcount at the clone, a lock and an
unlock per read, and a poisoned-lock case to handle in code that never
writes. Rust’s own answer to that is to drop the Mutex when nothing
writes —
let shelf = Arc::clone(&shelf);
handles.push(thread::spawn(move || {
shelf.iter().map(|d| d.words).sum::<u32>()
}));— which is the same program as §16.2’s frozen shelf, spelled by hand in the type. That is the fairest thing to say about the comparison: Rust can express both of wolf’s answers, and requires the programmer to know which one this data is, encode it in a type, and rewrite the type when the answer changes.
Wolf moves the region. The bill arrives at compile time, and it is the move check. What the receiver pays to read is nothing.
The one place wolf’s answer is structurally harder than the others is the cyclic graph, and it is instructive to see what the others do with it. Rust cannot make the ring out of references, so it makes it out of indices:
pub struct Node {
pub title: &'static str,
pub newer: usize,
pub older: usize,
}That is an arena, hand-rolled, with usize where a pointer wanted to be
and no check that an index belongs to the arena it is used with. The
program in §16.1 is the same idea with the arena in the language and the
index carrying a generation, which is what turns a stale reference from
an exploit into a trap (§8.7). So the honest summary of the cyclic case
is not that wolf can do something Rust cannot; it is that both do the
same thing, and one of them checks it.
Where wolf pays and the others do not: distribution. move is an
in-process transfer of ownership over memory that is not going anywhere,
and it does not become a network protocol by adding a keyword. Erlang’s
copy is expensive because it is a serialization, and a serialization is
what crosses a machine boundary. That trade is decided (v1 procs are
in-process) rather than pending, and a wolf program that needs to talk to
another machine writes a protocol, like a C or Rust or Go program does.
Exercise 16-6 (design) — The same workload — a producer builds a
million-node tree, a consumer walks it — in four systems: Erlang (copying
send), Go (send a pointer), Rust (Arc<Mutex<Tree>>), wolf
(ch.send(move r)). For each, name what the transfer costs at the moment
of send, and what it costs the receiver to be safe while reading. One
of the four pays at a different time than the others — which?
Exercise 16-7 (extension · lupin) — A maze is a graph, and a graph is a region’s favorite payload. Carve a 5×5 maze with a seeded generator (per-cell wall bitmasks: 1=N 2=E 4=S 8=W, depth-first carve, a small linear-congruential step for direction choice), building the wall table inside a region. Send the region to a solver task; the solver breadth-first-searches it in place and prints the shortest-path distance from corner to corner. Seed 1: run it. Before you do, answer: how many times is the wall table copied between carver and solver?
Exercise 16-8 (comprehension + schedule play · lupin) — Change the
carve seed to 2 and run the program three times, including once under
lupin run … --seed=7. Predict: which of the two seeds in play changes
the printed distance, and which cannot — and why does this program print
the same distance under every scheduler seed?
Exercise 16-9 (comprehension · wolf + lupin) — This program declares
a channel of bare List[int] — not Copy, not imm, not a region, not
sync:
fn main() -> !int {
let ch = channel[List[int]](1)
0
}
Predict the verdict this program earns and the rule behind it, and explain
why each of the four admitted payload classes is safe where a bare List
is not.