Making your own region
On this page
Every region in this part, Uni, Rc, Arc, the collectors, is written in Cone, and none is built into the compiler. So a strategy the library lacks can be added the same way: reference counting that traces now and then to break its cycles, say, or a collector that traces within a thread and counts between threads. This page covers how a region ref is written, the methods the compiler calls and when, single and counted ownership, traced regions for collectors, and a value that leads to a region. Afterwards you can write a memory management strategy of your own and use it with new:
mod counted;
import stdio use *;
import libc;
// A reference-counting region ref: the count lives in the bookkeeping
struct Counted is RegionRef {
owners usize;
fn alloc(size usize) *u8 { libc.malloc(size); }
fn init(self &new) { *self = new Counted(1usize); }
fn aliasRef(self &uni Counted) {
owners = owners + 1usize;
print <- "owners ";
print <- owners;
print <- "\n";
}
fn dealiasRef(self &uni Counted) bool {
owners = owners - 1usize;
print <- "owners ";
print <- owners;
print <- "\n";
owners == 0usize; // true: that was the last owner
}
fn free(self &uni Counted) {
print <- "freed\n";
libc.free(self as *u8);
}
}
struct Note {
pub n i64;
fn final(self &uni) { print <- "final "; print <- n; print <- "\n"; }
}
fn main() i32 {
let a = new Counted[mut, Note](7);
{
let b = a; // another owner: aliasRef
print <- b.n;
print <- "\n";
} // b goes: dealiasRef
print <- "end of main\n";
0i32;
} // a goes: dealiasRef, then the finalizer, then free
It prints owners 2, 7, owners 1, end of main, owners 0, final 7 and freed, one to a line.
How a region ref is written#
A region ref is a struct that declares the built-in trait RegionRef; there is no separate declaration for one. Its fields are the bookkeeping kept with every value the region allocates (a count, say), and its methods are the ones the compiler calls when a value is allocated, when an owning reference is copied or goes away, and when a value is freed. It is named in a new like any other region, new Counted[mut, Note](7). Every method is optional, an absent method's operation does not happen, and what a region ref leaves out says what it does:
- fn alloc(size usize) *u8 gets the memory. It answers null for a failure, rather than an Option. The regions in the core package get it from core's raw blocks layer (RawBlocks), the one place the heap's bytes come from, which today forwards to C's malloc, realloc and free (The heap's region and the raw blocks layer).
- fn free(self &uni R) gives the block back.
- A region ref that declares the built-in trait Move is single-owner: a copy of its reference is a move.
- A region ref that adds a count is a counted one: an init that sets the count to one, an aliasRef that adds one when a reference is copied, and a dealiasRef that answers whether the count reached zero when a reference goes away. It does not declare Move, and the compiler refuses a region ref that declares both Move and aliasRef.
- A region ref that declares neither aliasRef nor Move shares its references freely. With no dealiasRef either, a reference going away does nothing and the compiler never frees the value: that is the shape of a tracing collector, which frees a value once nothing reaches it, and of an arena.
The region decides when a value dies; the compiler runs the death, since only it knows the value's type. When a region frees a value, the value is finalized first: its final, then its fields, then the region ref's free.
The methods the compiler calls#
The compiler calls these methods at key events in the life of an owning reference. Each is handed the bookkeeping, not the value. A region ref's methods are ordinary Cone code, not trusted code.
fn alloc(size usize) *u8, static, is called whenever new makes an owning reference, after the value initializer's arguments are evaluated. The compiler supplies the size of the value to be stored, enlarged to include the region's bookkeeping (the count, say) and a lock permission's, and a null answer fails. After alloc, the compiler initializes any lock permission's fields, then moves the pointer past the bookkeeping to the value, and fills the value from its initializer, a finished value or contents (The order of an allocation). The other form, fn alloc(size usize, ty *TypeRecord) *u8, is also handed the allocated value's type record: its size, alignment, finalizer and trace, so the region can later finalize a value of any type itself (an owning slice's is its element type's).
fn init(self &new) is an initializer, run right after alloc on the bookkeeping, which it fills in place: *self = new Counted(1usize).
fn aliasRef(self &uni R) is called whenever a new shared copy of the reference is made. fn dealiasRef(self &uni R) bool is called whenever an owning reference is destroyed, usually when the variable holding it reaches the end of its scope, and also when a reference held by a variable or field is overwritten. It answers whether the last owner is gone, rather than calling free itself.
fn free(self &uni R) is called when the region has decided the value is safe to free. When the last owner goes, the compiler runs the value's finalizer before calling free, which disposes of any resources the value holds.
Constructing in a region#
The value's own initializer runs in the region too. new Counted[mut, Node](1) runs Node's initializer on the memory the region allocated, after the region's own init has filled its bookkeeping. One given a finished Node instead, new Counted[mut, Node](done), moves it in and runs no initializer (a construction fills its value in place):
mod inregion;
import stdio use *;
import libc;
struct Counted is RegionRef {
owners usize;
fn alloc(size usize) *u8 { libc.malloc(size); }
fn init(self &new) {
print <- "region init\n";
*self = new Counted(1usize);
}
fn aliasRef(self &uni Counted) { owners = owners + 1usize; }
fn dealiasRef(self &uni Counted) bool {
owners = owners - 1usize;
owners == 0usize;
}
fn free(self &uni Counted) {
print <- "free\n";
libc.free(self as *u8);
}
}
struct Node {
pub n i32;
pub fn init(self &new, k i32) {
print <- "node init\n";
*self = new Node(n: k * 10);
}
fn final(self &uni) { print <- "node final "; print <- n; print <- "\n"; }
}
fn main() i32 {
{
let a = new Counted[mut, Node](1); // Node's initializer runs, on the region's memory
print <- a.n;
print <- "\n";
}
{
let done = new Node(5);
let b = new Counted[mut, Node](done); // a finished Node moves in: no initializer runs
print <- "moved in\n";
}
0i32;
}
The first block prints region init, node init, 10, node final 10 and free. The second prints node init (for new Node(5)), region init, moved in, node final 50 and free.
Single owner, shared, and counted#
Single ownership is declared, not read off a missing aliasRef. A region ref declaring the built-in trait Move (struct Uni is RegionRef, Move) is single-owner, and may not also have aliasRef. Its reference is moved instead of copied, so no second owner can be made, which is what lets it free its value the moment its owner goes:
mod unique;
import stdio use *;
import libc;
// A single-owner region ref: Move means a copy of the reference is a move
struct Unique is RegionRef, Move {
fn alloc(size usize) *u8 {
print <- "alloc\n";
libc.malloc(size);
}
fn free(self &uni Unique) {
print <- "free\n";
libc.free(self as *u8);
}
}
struct Point { pub x i32; pub y i32; }
fn consume(p Unique[mut, Point]) {
print <- p.x + p.y;
print <- "\n";
} // the owner ends here
fn main() i32 {
let p = new Unique[mut, Point](3, 4);
consume(p); // moved: p may not be used again
print <- "after\n";
0i32;
}
This prints alloc, 7, free and after.
A region ref may declare neither Move nor aliasRef, as Gc's does. Then several shareable references to one value are possible, and copying one costs nothing; it needs no aliasRef that does nothing. With no dealiasRef either, an owner going away does nothing and the compiler never frees the value: a collector does, as Gc's does (below). One with aliasRef but no dealiasRef never frees a value by count.
Traced regions, for collectors#
A region ref that also declares the built-in trait Traced (struct Gc is RegionRef, Traced) has its references traced. It declares fn mark(self &uni R, slot *usize), or fn mark(self &uni R, slot *usize, perm u32, mode u32) to be told each reference's permission and the mode it was traced in. Every type record's trace (and mem.trace) hands it the bookkeeping of each of its references a value holds, and the slot the reference is stored in (its first word is the address of the value), which a collector that moves values rewrites. It may not be Move:
mod heapy;
import stdio use *;
import libc;
// A traced region ref: it declares Traced and a mark method. A collector built on it
// is told, through mark, each reference a value holds, and the slot it is stored in.
struct Heapy is RegionRef, Traced {
seen usize;
fn alloc(size usize) *u8 {
let p = malloc(size);
mem.writeRaw(p as *Heapy, new Heapy(0usize));
p;
}
fn mark(self &uni Heapy, slot *usize) {
seen = seen + 1usize;
print <- "marked\n";
}
}
struct Leaf { pub n i64; }
struct Pair { pub left Heapy[mut, Leaf]; pub right Heapy[mut, Leaf]; }
fn main() i32 {
let l = new Heapy[mut, Leaf](1);
let r = new Heapy[mut, Leaf](2);
let pair = new Pair(l, r);
print <- pair.left.n + pair.right.n;
print <- "\n";
0i32;
}
Nothing here collects, so mark is never called, and this prints 3.
Where a traced reference may be held#
A traced reference may be held only where a collector can find it: in a local, a parameter, a temporary, a value held in one of those, a value a traced region allocated, or behind what a trace passes through. A trace passes through an Rc or Uni reference to the traced references its value holds, once for each collection: a counted region ref declares fn visit(self &uni R, mode u32) bool, which answers whether this is the first time its value was reached in the collection whose epoch the trace's mode names, so a value several owners hold, or one round a cycle, is traced once; one that declares neither Move nor visit cannot be passed through. A trace also passes through a collection, a pool or an arena: a type that declares the built-in trait GcTraceElements and a method fn gcTraceElements(self &mut) I, I a cursor declaring is Iterator[&mut E], a writable reference to each value it holds.
So the compiler refuses a traced reference held in a global, or in memory placed by mem.writeRaw from a type that declares no GcTraceElements; one held by a region a trace cannot pass through, among them a traced region that declares writeBarrier (below), whose collector would not hear of a reference stored behind an owner; and a local, a parameter or a traced region's value whose type holds a raw pointer to a value that holds one, declaring no GcTraceElements, which no trace can follow. It refuses a traced region's value holding a borrowed reference, a traced virtual reference, and a permission that takes room. A traced value may hold Rc and Uni references, which its finalizer releases.
Finding the roots#
The traced references on the stack are found: mem.traceRoots(mode) hands each one every running function holds, in its locals, its parameters and the temporaries it is making, to its region ref's mark, which is what a collector starts from. A traced allocation evaluates its initializer's arguments before it calls alloc, so a collection inside alloc finds them; and as soon as alloc returns, before any initializer runs, the new value is held as a root and reads as empty (its references null) until it is filled, so a collection during an initializer that allocates finds it, and nothing half made. The roots are a chain of frames local to each thread.
The write barrier#
A traced region ref may also declare fn writeBarrier(self &uni R): every store of one of its references into memory that is not a local (a field, an element or a dereference reached through any reference, a borrow included; a swap; :=) then hands it the bookkeeping of what was stored, just after the store. It is told nothing of where the reference went. Stores into locals, and a new value's contents stored whole, get none, so a collector that marks while the program runs traces the stacks again before it finishes marking. The collectors built this way, Gc and an actor's ActorGc, are described with Garbage collection.
A value that leads to a region#
A dynamic region, such as an arena, is a value rather than a module, and a new can name the value in place of a type: new a[Node](1, 2) allocates in that value's region. The compiler reads it as a.alloc(new Node(1, 2)), so what comes back is what that call returns (an arena returns a borrowed &mut reference to the value). The head of such a new must be a region value, or a value that leads to one:
- A region value is a value whose type is a struct whose first field is a public *MemRegion, as an Arena's and a DynArena's are.
- A value that leads to one has a type with an allocRegion method giving the region value, and new x[T](...) is x.allocRegion().alloc(new T(...)). The head's call is made again to hand the region to a type that gets its memory from one, so it should lend nothing still borrowed when it is called again.
Any other head is refused. An actor's state leads to the actor's own garbage-collected region (ActorGc), which is how new self[T](...) allocates there. A struct of your own can lead to an arena it holds:
mod scene;
import stdio use *;
import arena use *;
struct Node { pub a i64; pub b i64; }
struct Scene {
pub ar Arena;
pub fn allocRegion(self &mut) &mut Arena { &mut ar; }
}
fn main() i32 {
var s = new Scene(Arena.empty());
let n = new s[Node](1, 2); // s.allocRegion().alloc(new Node(1, 2))
printInt(n.b); // 2
printStr("\n");
0i32;
}
Not settled: the allocRegion method's name and shape are provisional, and how a value is allocated in a dynamic region such as an arena or a pool is an open design question. The packages allocate with a.alloc(value), new a[T](...) and p.add(value), and no other spelling is read.
You can now write a memory management strategy as a region ref, single, shared, counted or traced, and allocate with it as with any built-in one; and with that, choose and build the memory management each part of a program needs. Next comes Concurrency, which builds on the permissions this part introduced.