Heapless routines

Some code must never touch the heap. A control loop on a board with no allocator at all, a routine on a path that must finish in bounded time, a routine a C library runs on its own terms: for each of them one hidden allocation is a defect, and in ordinary code allocations hide well — a string built for a log line, a copy of a value that owns storage, a cleanup registered for later.

A Mica routine can say so on its heading, and the compiler holds it to the word.

The word

program Levels;

imp
    WriteLn : std;

type
    Samples = array[0..7] of int64;

    Meter = record
        peak : int64;
        count : int64;
    end;

var
    samples : Samples;
    meter : Meter;
    i : int64;

heapless procedure Observe(m : pointer Meter, level : int64);
begin
    m.count := m.count + 1;
    if level > m.peak then
        m.peak := level;
end;

heapless function Average(xs : Samples) : int64;
var
    k : int64;
    total : int64;
begin
    total := 0;
    for k := 0 to 7 do
        total := total + xs[k];
    Average := total / 8;
end;

begin
    for i := 0 to 7 do begin
        samples[i] := i * i;
        Observe(address meter, samples[i]);
    end;
    WriteLn("peak %lld over %lld samples, average %lld", meter.peak, meter.count, Average(samples));
end.

Saved as Levels.mica, it runs with one command:

mica Levels.mica

peak 49 over 8 samples, average 17

heapless stands in front of procedure, function or callback, and it is a promise about the routine, written where a reader meets it: the routine never allocates heap memory and never releases any. The word changes what the compiler accepts, not what the routine computes. Everything a program works out with plain values stays available — arithmetic, records and fixed arrays, fields written through a pointer, strings measured, indexed and compared.

The word is claimed only in that position, the way task and generator are, so a program may still name a value heapless.

What the compiler refuses

Inside a heapless routine, every construct whose meaning allocates or releases is refused at its own line, with a sentence that names what it does:

program Refusals;

imp
    WriteLn, Length : std;

function Describe(level : int64) : string;
begin
    Describe := "level";
end;

heapless function Label(level : int64) : int64;
var
    text : string;
begin
    text := "level " + "high";
    Label := Length(text) + level;
end;

heapless procedure Report(level : int64);
begin
    WriteLn("level %lld", level);
end;

heapless function Named(level : int64) : int64;
begin
    Named := Length(Describe(level));
end;

heapless procedure Kept(cell : owning pointer int64);
begin
    dispose cell;
end;

begin
    WriteLn("%lld %lld", Label(1), Named(2));
    Report(3);
end.

Four routines, four refusals. Two of them are about the body:

analyzer error 5549: 'Label' promises never to use the heap, and concatenating
strings allocates here: keep the routine to plain values, pointers and
fixed-size storage, or take 'heapless' off its heading

analyzer error 5549: 'Kept' promises never to use the heap, and 'dispose'
releases heap memory here: keep the routine to plain values, pointers and
fixed-size storage, or take 'heapless' off its heading

A routine that releases memory breaks the promise as surely as one that allocates: releasing enters the same allocator, and code without a heap has nothing to release.

Calls keep the promise

A heapless routine calls only routines that make the same promise. The rule is stated, not inferred: each routine’s promise is checked once, in its own body, and every caller trusts the heading. The other two refusals above are calls:

analyzer error 5550: 'Named' promises never to use the heap, and it calls
'Describe', which makes no such promise: give 'Describe' the 'heapless' word
if it keeps one, or call a routine that does

analyzer error 5552: 'Report' promises never to use the heap, and it calls
'WriteLn', whose contract from 'std' states no such promise: the compiler
cannot see into a library's code, so the promise comes from the contract's
'heapless' attribute alone

Built-ins are judged by what each one states about itself: Length reads a string and is admitted, Append grows an array and is refused. A few operations read plain in the source and reach the heap only in the code they lower to — a matrix product splits large work into parallel bands — and the compiler judges that code as well, refusing the construct at its own position.

A generic heapless routine keeps its promise in every specialization: each concrete body is judged on its own.

Tasks and generators

Neither kind can make the promise, because creating one allocates the frame it runs on:

analyzer error 5551: 'Spinner' is a task, and creating one allocates a frame
of its own, so it cannot carry 'heapless': put the word on the routines it
calls instead

Across units and contracts

An exported routine carries its promise into its contract. exp heapless function writes "heapless": true into the routine’s contract row, and a heapless routine in the importing unit may call it. The export mark comes first; the other order is refused with the fix:

parser error 2072: the export mark stands in front of the promise: write
'exp heapless' ahead of the routine heading

A C function is a different case, because no compiler sees into C code. A heapless routine may call one only when the function’s contract states "heapless": true, the contract author’s promise, beside the parameter types the author states the same way — see the contract fields. Hover shows the word on every routine that carries it.

Callbacks

A heapless routine that hands a callback to a C function has the callback run on its behalf, so the callback must make the same promise — heapless callback:

analyzer error 5553: 'Handed' promises never to use the heap, and it hands the
callback 'Loud' to 'EachNumber', which runs it on this routine's behalf: give
'Loud' the 'heapless' word so it keeps the same promise

Signal handlers

The hardest place a routine can run is a signal handler. The kernel stops the program between any two instructions — halfway through an allocation, while a lock is held — and runs the handler on top of whatever was happening. SignalHandle from posix installs a callback as the handler of one signal, and its slot admits only a heapless callback:

program Tally;

imp
    WriteLn : std;
    Kill, GetPid, SignalHandle, SIGUSR1, SIGSEGV : posix;

var
    hits : int64;
    rc : int32;
    chosen : int32;

heapless callback OnUser(signal : int32);
begin
    hits := hits + 1;
end;

begin
    rc := SignalHandle(SIGUSR1, OnUser) on fail use -1;
    rc := Kill(GetPid(), SIGUSR1) on fail use -1;
    rc := Kill(GetPid(), SIGUSR1) on fail use -1;
    WriteLn("hits %lld", hits);
    chosen := SIGSEGV;
    rc := SignalHandle(chosen, OnUser) on fail use -1;
    WriteLn("SIGSEGV answers %d", rc);
end.

mica Tally.mica

hits 2
SIGSEGV answers -1

The handler writes a plain root variable, and the program sees every write once the signal has been handled. Seven signals are refused, because a handler for them cannot work: SIGKILL and SIGSTOP cannot be handled at all, SIGSEGV, SIGBUS and SIGPIPE belong to the runtime, and a handler that returns from SIGILL or SIGFPE runs the faulting instruction again. Written as a constant, such a signal is refused by the compiler at the call; a signal held in a variable is refused when the call runs, and the call fails. The program above passes SIGSEGV through chosen to show that answer. SignalDefault puts a signal’s default back.

A callback without the word is refused where it is handed over:

analyzer error 5554: the parameter 'handler' is a signal callback slot, and the
kernel runs 'Loud' between any two instructions, an allocation's among them:
give 'Loud' the 'heapless' word

Being heapless is not enough. The code a signal interrupts may hold a lock or be in the middle of a wait, and a handler that took the same lock or waited would stop behind it for good. Inside a handler the compiler also refuses:

analyzer error 5555: 'Marked' runs as a signal handler, and the 'synchronized'
mark takes a lock, which can stop the handler behind the code it interrupted:
keep the handler to plain values and root variables, and let it wake a task
with 'SignalWake' for the rest

The real work belongs to a task. SignalWake writes one byte to a descriptor and never waits — when the pipe is already full, the byte waiting there does the job — so a task parked in Read on the pipe’s other end wakes and takes it from there. The descriptor is the write end of a pipe made with Pipe, which the runtime switches to non-blocking mode for the write; any other descriptor must already be non-blocking. One that is blocking, or not open, could never take a wake, so it is refused by its number, and the program ends with one sentence naming it:

mica runtime: SignalWake was handed the descriptor 0, which is in blocking mode and was not made by Pipe, so a signal handler cannot write the wake to it without the risk of waiting: create the pipe with Pipe, or set the descriptor non-blocking before a signal can arrive

Around the handler the runtime keeps errno as the interrupted code left it, runs the handler on a stack of its own, and lets a read or a write the signal interrupted carry on.

Try it

The container’s Heapless example keeps a ring window of readings, smooths it, and compares strings, all in heapless routines — and each routine’s comment names a one-line change and the refusal it earns:

make -C mica-container/examples/Heapless run

The SignalHandling example installs a handler for SIGTERM that counts the shutdown request and wakes a task waiting in Read:

make -C mica-container/examples/SignalHandling run