08-memory-model.md

08: Memory Model

Polyscript manages memory with reference counting, inserted by the compiler. There is no garbage collector and no lifetime annotation to write. This chapter describes which values are counted, how they are laid out, and when they are released.

Two Categories of Value

Every type belongs to one of two categories, and the category determines how its values are stored, passed, and released.

Category	Types	Behavior
Copy	int, float, bool, char, str, void, never, every enum, every function type	Held directly. Assigning copies the value. Never counted, never released.
Heap	Every struct	Held on the heap behind a counted reference. Assigning shares the value. Released when the last reference goes.

The rule worth remembering is that structs are shared and enums are copied.

struct Counter { n: int; }

let a = Counter { n: 0 };
let b = a;   // `a` and `b` name the same value.
b.n = 5;
// `a.n` is 5.

enum Level { Easy, Hard }

let x = Level.Easy;
let y = x;   // `y` is an independent copy.

This is also why an instance method can change its receiver even though self is an ordinary parameter: what gets passed is a reference to the shared value.

struct Scalar { inner: int; }

impl Scalar {
    fn set(self, inner: int) {
        self.inner = inner; // The caller sees this.
    }
}

Layout of a Heap Value

A heap value is one allocation holding a header followed by the data.

┌───────────────────────────────┬──────────────────┐
│            header             │       data       │
├────────────────┬──────────────┤                  │
│   ref_count    │ deallocate   │  the struct's    │
│     (i64)      │   (pointer)  │     fields       │
└────────────────┴──────────────┴──────────────────┘

ref_count starts at 1. deallocate points at a function generated for that specific type, which is what lets a single release routine work for every type without knowing which one it holds.

Sharing and Releasing

Two operations maintain the count.

Incrementing happens whenever a value gains another holder — an assignment, a field of a struct literal, an argument to a call, a closure capture.

Decrementing happens whenever a holder gives the value up — a binding is overwritten, or a value is discarded. Decrementing to zero releases the value:

1. The type's deallocate function is called.
2. The allocation is freed.

The generated deallocate function does two things in order:

1. If the type implements Drop, its drop method runs.
2. Every field that is itself a heap value is decremented.

Step 2 is what makes release recursive. Letting go of the last reference to a struct lets go of its fields, which lets go of theirs, down the whole tree. Fields are visited in declaration order.

A matching function is generated for duplication, which increments every heap field of a value that is being copied, so that a copy never leaves the original's fields under-counted.

Drop

Drop exists for types that hold something the counter does not know about — most often a raw allocation the type made itself. Its drop method runs at the moment the value's count reaches zero, before the memory is reclaimed.

struct Connection {
    private handle: int;
    private open: bool;
}

impl Drop for Connection {
    fn drop(self) {
        if (self.open) {
            self.handle = 0;
            self.open = false;
        }
    }
}

Since release is recursive, a type only needs a Drop implementation for resources it manages directly. Ordinary fields are handled without one.

Writing Generic Code That Releases Values

A generic function does not know whether its parameter will be a copy type or a heap type, and the two are released differently: a heap value is decremented, a copy value is dropped outright. The #IS_REFCOUNTED# directive from Generics chooses between them.

// From a container in the standard library.
fn release_slot<T>(address: int) {
    if #IS_REFCOUNTED#{T} {
        decref(address);              // T is a heap type.
    } else {
        drop(deref(address as T));    // T is a copy type.
    };
}

Each generated instantiation keeps only the branch that applies to it. The intrinsics it calls are available to the standard library, which is where containers like Vec<T> are written; see Modules.

Raw Memory

Polyscript has no pointer type. An address is an ordinary int, and the operations that produce and consume addresses are intrinsics.

Intrinsic	Purpose
calloc(count, size): int	Allocate zeroed memory and return its address.
realloc(address, size): int	Resize an allocation.
memcpy(dst, src, n)	Copy n bytes between separate regions.
memmove(dst, src, n)	Copy n bytes between possibly overlapping regions.
free(address)	Release an allocation.
ref(value): int	Take the address of a value.
deref(address): T	Read a value out of an address.
incref(address)	Increment a reference count.
decref(address)	Decrement a reference count.
drop(value)	Release a value directly.

There is no null literal, so the address zero is given a name by convention:

const nullptr: int = 0x0;

These intrinsics come from the @intrinsics module, whose availability is described in Modules.

sizeof

sizeof T is the size of a type in bytes. It is an expression, and it accepts a generic parameter, resolving once that parameter is concrete — which is what lets a generic container size its own allocations.

struct Buffer<T> {
    private element_size: int;
    private data: int;
}

impl<T> Buffer<T> {
    fn new(): Self {
        Buffer {
            element_size: sizeof T,
            data: nullptr
        }
    }
}

Arithmetic Safety

Integer arithmetic is checked. Signed overflow, division by zero, and modulo by zero each stop the program with a diagnostic rather than producing a meaningless value.