Expand description
The per-task mark-and-sweep collector.
The Language Card says memory is managed by a precise, non-moving mark-and-sweep collector, and ADR 0011 narrows that to a heap per task over the values a task owns. This module is that heap.
ADR 0008 gives each spawned task a thread and an crate::interp::Interpreter
of its own, so a heap belongs to one interpreter and is reached only from
the thread running it. That is what makes “per task” more than a
convention: a task’s objects are unreachable from any other thread, so a
collection needs no safepoint from anyone else and takes no lock.
§What the heap owns
Rc reclaims a value the moment nothing points at it, which is correct for
every Cove value that is built once and never altered — a string, an array,
a map, a set, a closure, a struct, an enum case. None of those can be made
to point back at something that points at them, because each is built from
values that already exist. The one exception is
crate::value::VectorStorage: a vector’s elements are behind a
RefCell, so v.push(v) is a cycle, and Rc alone will never free it.
The heap therefore tracks exactly the objects that can form a cycle. Rc
remains the allocation handle and still reclaims everything acyclic on its
own; the collector exists for what Rc cannot do.
The heap holds a Weak handle to each object rather than a strong one.
That is not an optimisation: freeze() consumes uniquely owned vector
storage and asks Rc::strong_count whether the caller holds the only
handle, so a heap holding a strong reference would make freeze() fail on
every vector. A Weak keeps the collector out of the language’s own
uniqueness rule, and it costs nothing — a cycle keeps itself alive, so a
Weak to a member of one always upgrades.
§Roots, and why reference counts are part of them
ADR 0011 is explicit that the roots are the interpreter’s own structures
rather than a machine stack, so there are no stack maps here. Roots is a
trait naming something that can drive a walk of one task’s roots, and
SlotRoots is its one implementor now: every binding the interpreter
creates is a crate::interp Place, whose slot is an
Rc<RefCell<Value>> registered in a SlotRoots list with the same
push-and-truncate discipline the environment chain already has; the
collector borrows each cell as it walks, so what it sees is what the slot
holds now rather than what it held when the binding was made.
Before ADR 0034 there was a second implementor: the predecessor VM had no
such cells, and put every binding into one contiguous Vec<Value>
instead, precisely so a call on that backend would allocate nothing. A
collector that demanded the interpreter’s shape would have made that VM
build a cell per binding and give back what the arrangement bought; one
that demanded the VM’s would have made the interpreter snapshot its
bindings into a vector, which is both a copy and a lie, since the
snapshot would be of the values as they were rather than as they are. A
walk rather than a structure is what let the collector work over both
shapes without asking either one to give back what it was for.
The linear-memory backend does not implement this trait at all. Its heap
belongs to the run rather than to a task, and it finds its roots from a
frame’s static reference map instead — crate::vm::mem’s own Roots
describes that on its own terms. Adding that backend cost this module
nothing, which is the walk-not-a-list design paying for itself a second
time: the point was never only the two shapes that existed when it was
written.
A walk is asked for twice, once to count and once to mark, so an implementation must be re-walkable and must yield the same values both times. Nothing here consumes it.
The walk covers what the program has named. It does not cover a value the
interpreter is holding in a Rust local while it is mid-evaluation — the
left operand of a + whose right operand is still being evaluated. Those
are the values ADR 0011 calls “values being evaluated,” and a tree walker
has no list of them by construction. The linear-memory backend has no
such gap to close: a value it is computing already lives in a frame slot
the static reference map already covers, and an object allocated before
its fields are written is zeroed rather than left holding whatever
preceded it, so there is nothing mid-evaluation for its collector to
miss the way this one can.
The collector finds them exactly, without scanning anything: it counts the
references it can see. For every shared allocation it walks — a vector, an
array, a map, a struct, a closure, a trait object, a task, a task scope —
it sums the references reachable from the walked roots and from the
objects it manages, and compares that with Rc::strong_count. A shortfall
is a reference held somewhere the collector cannot read — a Rust local it
has not walked — so that allocation, and everything it holds, is a root.
This is the rule that makes a safepoint safe rather than merely well-chosen. A value in a Rust local is itself a reference, so a value the collector cannot see is a value whose count does not add up; there is no arrangement of locals the interpreter can reach a safepoint in that hides one. What the interpreter has to get right is therefore narrower than “have everything on a stack”: it has to not walk anything twice, because a reference counted twice is a shortfall concealed. The linear-memory backend answers the same demand — a safepoint must not reach a value its collector cannot find — without this counting trick: a static reference map leaves nothing held off to the side to count.
Counting the containers as well as the objects is what makes this sound rather than merely plausible. An array can hold the only reference to a vector while being held itself by a garbage cycle and by a temporary; if only the vector were counted, every reference to it would look accounted for — by the garbage — and the sweep would empty something the program can still reach.
This is precise in the sense ADR 0001 asks for: no word is guessed to be a pointer, and no integer is ever mistaken for one. It is also the invariant that makes every other awkward case safe. A slot the interpreter has mutably borrowed cannot be read, so its references go unseen, so whatever it holds is treated as a root.
§What it does not do
No finalizers, no compaction, no generations, no concurrent or incremental collection, no weak references in the language. Each is out of scope in ADR 0001 and remains so in ADR 0011.
§Shared
ADR 0011 says a Shared<T> cell owns its contents rather than any task’s
heap, and collects them with the cell. That is what happens, and it needs
no collector at all.
A crate::shared::SharedCell holds a crate::task::Transfer, not a
Value, and Transfer::of refuses a Vector. A cell therefore cannot
hold a collectable object, so there is nothing in one for a heap to own and
no way for a cycle among a task’s objects to run through one. The Arc
frees the contents with the cell, which is exactly what the ADR asks for. Each lock materialises
a fresh Value for the locking task, and that copy is an ordinary value
in that task’s heap, collected there like any other.
So the collector treats a Shared as a leaf: it never takes the cell’s
lock. That is not only unnecessary, it is required. lock holds the mutex
for the whole of the closure it is given, that closure runs Cove code, and
Cove code reaches safepoints — so a collector that locked a cell would
sooner or later wait for a lock the collecting thread already holds.
One thing this does not reach: a cell may hold another cell, including
itself, and that is an Arc cycle no heap here can see. Cells are
reachable from every task that was given one and outlive all of them, so
collecting cycles among them would need a collector that stops every
thread — which ADR 0011 rules out under “no concurrent collection”. It is
a real leak, and the ADR now says so under “What this leaves uncollected”.
Structs§
- Collection
- What one collection did.
- Heap
Stats - What a run’s heaps did in total.