v0.4.0
Memory · Lesson 15.9

Allocator

Source
Allocate through the Allocator interface with SystemAllocator, handling an AllocError before the block is ever used.

Alloc and Free always go to the same place, and they report failure with a null that is easy to forget. An allocator fixes both. It turns "where memory comes from" into a value you can pass around, and it reports failure as a real error that has to be handled before there is any address to misuse.

This lesson uses the simplest allocator, SystemAllocator. Later lessons in this part swap in others — an arena, a fixed buffer, a pool — without changing how they are called.

The Allocator interface

Allocator, from the Allocator package, is an interface. It promises three operations, and any type that keeps those promises can stand behind it:

OperationDoesDeclared as
Allocate(layout)takes storage that matches the layout-> *var opaque throws AllocError
Deallocate(block, layout)gives the storage backthrows AllocError, with no value
Reallocate(block, oldLayout, newLayout)grows or shrinks a block-> *var opaque throws AllocError

A function written against the interface works with whichever allocator its caller passes in:

func SumOfSquares(allocator: Allocator, count: uint) -> int64 throws AllocError {
flowchart LR
    f["`SumOfSquares`"] -- "`Allocate(layout)`" --> i{{"`Allocator`"}}
    i --> s["`SystemAllocator`"]
    s -- "asks for pages" --> os[("the operating<br/>system")]
    i -- "an address,<br/>or an `AllocError`" --> f

A request is a Layout

Alloc took a byte count. Allocate takes a Layout: a size and an alignment together, so the two always travel as a pair. Layout::ForArray<T>(count) builds one for count values of T:

let layout = Layout::ForArray<int64>(count) ?? throw AllocError::Unsupported;

It returns Layout? — none when count elements could not even be described, because the size would overflow. Here ?? turns that into an AllocError, as in Absence to error. Layout::ForValue<T>() describes a single value and cannot fail; you will meet it in the next lessons.

Failure is an error, not a null

Allocate throws an AllocError when it cannot serve the request, so an address only ever comes back when there is real storage behind it. Here try passes a refusal on to the caller:

let block = try allocator.Allocate(layout);

Past this line, block is real storage. The release is registered at once, with the same layout the block was asked for with:

defer try allocator.Deallocate(block, layout) catch { _ => {} };

Deallocate can throw too, but an error cannot leave a deferred statement: the scope is already being left when it runs. A refused release here could only be the allocator's own bug, and there is nobody to report it to, so try … catch { _ => {} } discards it on purpose.

Turning the block into something usable is the one step the compiler cannot check — that the storage really holds count int64s at their alignment — so the cast and the slice sit in unsafe, as in Pointer slice:

// Safety: `block` is a live allocation of `layout`, which holds `count` `int64`s at their
// alignment, and it stays allocated until the deferred release at the end of this function.
let numbers = unsafe { (block as *var int64)[..count] };

From there on, numbers is an ordinary checked slice.

The failure itself says why it happened:

AllocErrorMeans
Unsupportedthis allocator cannot serve the request at all; asking again will not help
OutOfMemorythere is no storage left right now
InvalidBlocka release named a block or a layout this allocator did not hand out

Getting an Allocator

Main builds the concrete allocator and passes it wherever an Allocator is wanted:

let allocator = SystemAllocator();

An Allocator value is a handle: the address of an allocator and a note of which type it is, copying nothing. SystemAllocator carries no state of its own — it asks the operating system for whole pages every time — so there is nothing for a handle to point at, and it converts to one anywhere, valid for the whole program. That is fine for a few large requests like these, and wasteful for many small ones — which is what the arena and the pool, later in this part, are for.

The refused request

The last call asks for a billion billion int64s. ForArray can still describe that many, but no machine can provide them, so the allocator refuses, and the try { } catch { } block in Try prints the reason. Which reason you see depends on how the operating system answers, which is why the output note says it may differ.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

Src/Main.rux
// `Alloc` and `Free` always go to the same place. An allocator turns "where memory comes from"
// into a value: the `Allocator` interface promises three operations, and any type that keeps
// those promises can stand behind it. A function written against the interface works with
// whichever allocator its caller passes in.
//
// This lesson uses `SystemAllocator`, which asks the operating system. The next lessons swap in
// others without changing how they are called.
//
// Two things differ from `Alloc`. A request is a `Layout`, a size and an alignment together,
// built here by `Layout::ForArray<T>(count)`. And failure is a real error, not a `null`:
// `Allocate` is declared `-> *var opaque throws AllocError`, so there is no address to misuse
// until the failure has been handled. A block must go back through `Deallocate` with the same
// layout it was asked for with.
import Allocator::{ AllocError, Allocator, Layout, SystemAllocator };
import Io::PrintLine;

// Borrows `count` numbers' worth of memory, uses it, and gives it back.
func SumOfSquares(allocator: Allocator, count: uint) -> int64 throws AllocError {
    // `ForArray` is `none` when `count` elements could not even be described.
    let layout = Layout::ForArray<int64>(count) ?? throw AllocError::Unsupported;

    // `try` passes a refusal on to the caller. Past this line, `block` is real storage.
    let block = try allocator.Allocate(layout);

    // Registered at once, so every path out returns the block with its layout. A refused release
    // here would be the allocator's own bug, and there is nobody to report it to.
    defer try allocator.Deallocate(block, layout) catch { _ => {} };

    // Safety: `block` is a live allocation of `layout`, which holds `count` `int64`s at their
    // alignment, and it stays allocated until the deferred release at the end of this function.
    let numbers = unsafe { (block as *var int64)[..count] };
    var total: int64 = 0;
    for i in 0..count {
        numbers[i] = (i * i) as int64;
        total += numbers[i];
    }
    return total;
}

func Reason(error: AllocError) -> char8[..] {
    return match error {
        .Unsupported => "the request cannot be served",
        .OutOfMemory => "there is not enough memory",
        .InvalidBlock => "the block was not from this allocator"
    };
}

func Try(allocator: Allocator, count: uint) {
    try {
        let total = try SumOfSquares(allocator, count);
        PrintLine("{} squares add up to {}", count, total);
    } catch {
        error => PrintLine("{} squares: refused, {}", count, Reason(error))
    }
}

func Main() -> int {
    // `SystemAllocator` holds no state, so it converts to an `Allocator` handle wherever one is
    // wanted, and the handle stays valid for the whole program.
    let allocator = SystemAllocator();

    Try(allocator, 10);
    Try(allocator, 1000);

    // Eight bytes times this count is far more memory than any machine has.
    Try(allocator, 1000000000000000000);
    return 0;
}

Besides Io, its Rux.toml lists Allocator under [Dependencies].

Run it

cd Examples/Memory/Allocator
rux run
10 squares add up to 285
1000 squares add up to 332833500
1000000000000000000 squares: refused, the request cannot be served

The reason given on the last line comes from the operating system's answer, so it can differ between systems.

Common mistakes

Try it yourself

  1. Add Try(allocator, 0);. What does a zero-element request give back, and does it still need releasing?
  2. Make Try also print error.IsTransient(), which is true only for OutOfMemory — the one failure that might go away if you ask again later.
  3. Write SumOfCubes against the same interface and call it with the same allocator.

Learn more

  • Interface value — how a concrete value stands behind an interface type
  • Propagate and Absence to error — the try and ?? throw used here
  • Box — the next lesson, which stops you from having to call Deallocate at all