Cone Language Reference

Custom Allocators

On this page

Note: The alloc declaration is not implemented.

Although Cone provides a rich collection of standard allocators, there are times that other allocators can prove valuable. For example: Rc allocators that use tracing to break cycles or multi-threaded garbage collectors that use tracing for intrathread memory management and ref counting for inter-thread memory management (Pony's Orca).

This is why Cone supports the creation and use of custom allocators. Definition of a new allocator looks and acts very much like a struct with methods.

An allocator is a struct that declares RegionRef#

A custom allocator is written as a struct declaring is RegionRef, which is how the core package's Rc and So are written. The struct's fields are the bookkeeping the allocator keeps with every value it allocates (a count, say), and the compiler calls its methods at the events described below, each method optional. A value is then allocated in it by naming it in a new: new Counted[mut, Note](7).

import stdio use *;
import libc;

// A reference-counting allocator: 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 {
  imm a = new Counted[mut, Note](7);
  {
    imm 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

This prints owners 2, 7, owners 1, end of main, owners 0, final 7 and freed, one to a line.

The methods the compiler calls#

The methods are invoked automatically by the compiler based on key events in the lifetime of an owning reference. Each is handed the bookkeeping data, not the value. An absent method's operation does not happen. Allocator methods are not trust blocks.

alloc#

fn alloc(size usize) *u8 is for allocate, and static. It is invoked whenever a new owning reference is created with new, after the value initializer's arguments are evaluated. The compiler supplies the sizeof the appropriate type of value to be stored in the allocated memory. This size is expanded to include runtime bookkeeping data for the allocator (e.g., the count) and permission, and null fails. After alloc, the compiler will also initialize any runtime permission's fields, if needed. The compiler's final step is to adjust the pointer to point at the value's data (past the runtime bookkeeping data), and then to initialize its value based on the literal, initializer or a copy of another similar value.

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 allocator can later finalize a value of any type itself; an owning slice's is its element type's).

init#

fn init(self &new) is an initializer, run right after alloc on the bookkeeping, which it fills in place: *self = new Rc(1usize).

aliasRef and dealiasRef#

fn aliasRef(self &uni R) is invoked whenever a new shared copy is made of the reference. fn dealiasRef(self &uni R) bool is invoked whenever an owning reference is destroyed, typically when the variable holding the reference reaches the end of its lexical lifetime. It can also happen when overwriting a reference held by an existing variable or field. It answers whether the last owner is gone rather than calling free itself.

free#

fn free(self &uni R) is invoked whenever the allocator determines 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 obtained by the owning reference.

Single owner, shared, and counted#

Single ownership is declared rather than read off a missing aliasRef. An allocator whose struct declares the built-in trait Move (struct So is RegionRef, Move) is single-owner, and may not also have aliasRef. Any allocator which declares the built-in Move trait (e.g., the 'So' allocator) ensures single-owner move semantics, as it prevents multiple copies of the reference from being created. The single-owner reference is moved instead of being copied. This restriction also constrains the permissions on borrowed references, effectively disallowing mut and all other shared mutable permissions.

import stdio use *;
import libc;

// A single-owner allocator: 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 {
  imm 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.

An allocator may declare neither Move nor the aliasRef method (e.g., the Gc allocator). In this case, multiple, sharable references to the same value become possible, and copying one costs nothing; it needs no aliasRef method 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 allocators#

An allocator whose struct 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, and 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.

import stdio use *;
import libc;

// A traced allocator: 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 {
    imm 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 {
  imm l = new Heapy[mut, Leaf](1);
  imm r = new Heapy[mut, Leaf](2);
  imm 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 allocator allocated, or behind what a trace passes through. A trace passes through a Rc or So reference to the traced references its value holds (once for each collection: a count-owning allocator 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), and 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 one held in a global, or in memory placed by mem.writeRaw from a type that declares no GcTraceElements; one held by an allocator a trace cannot pass through, among them a traced allocator that declares writeBarrier (below), whose collector would not hear of a reference stored behind an owner; and a local, a parameter or a traced allocator'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 allocator's value holding a borrowed reference, a traced virtual reference, and a permission that takes room. A traced value may hold Rc and So 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 allocator'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 thread-local chain of frames, one for each thread.

The write barrier#

A traced allocator 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 that exist#

One collector is built, as library code: the collector package's Gc allocator (import collector; then new Gc[mut, T](...)), an incremental mark and sweep that works a bounded step at a time inside alloc once the heap passes its trigger, and whole on Gc.collect(). Run generationally (Gc.setGenerational(true)), what survives a collection is old, and the collections after it are minor: they mark and sweep only the young values, the barrier staying on between them so that an old value's new young child is found. It runs a dead value's finalizer one collection before it frees the value, so a finalizer may still read the Gc values it holds. A finalizer runs some time after its value became unreachable, when a collection's step reaches it, not at a moment the program chooses. Gc.step(work) runs some collection work on demand, and Gc.setStress(true) a step at every allocation, for testing. It is single threaded (see concurrency), and for use outside actors only. It is discouraged: it is likely to be replaced, nothing else in Cone's packages depends on it, and new code does not build on it.

The other is an actor's own: the actors package's ActorGc, a copying collector run between that actor's messages (Its own region), which declares the built-in trait ActorLocal (provisional) beside Traced: its references stay in one actor, no stack is scanned for its roots, and it declares no writeBarrier, so a reference behind an Rc is traced. The compiler refuses a traced allocator's reference inside an actor or a parallel each unless the allocator declares ActorLocal, and there a read-only reference counts as Shareable and none may be made.

The planned alloc declaration#

The compiler does not yet recognize an alloc declaration. It is meant to read like this, a struct whose methods are named for the events above:

// A simple reference counting allocator
alloc Rc {
  refcnt usize;

  fn allocate(size usize) *uni Rc {
    imm rcref = malloc(size) as *uni Rc;
    rcref.refcnt = 1;
    rcref;
  }
  fn aliasRef(self *mutx Rc) {
    .refcnt += 1;
  }
  fn dealiasRef(self *mutx Rc) {
    .refcnt -= 1;
    if .refcnt == 0 {
      .free();
    }
  }
  fn free(self *mutx Rc) {
    free(self as *u8);
  }
}

Notice also that allocators work with pointers (which have no assigned allocator). In that form all allocator methods would be considered wrapped as trust blocks, which allows the use of pointers as well as trusted functions like malloc() and free(). The pointers are automatically and correctly cast by the compiler back and forth from the correct pointer to the correct reference.