20 Allocators and fixed memory

20.1 The three parts of an allocator#

The byte_allocator trait of the standard library’s allocs requires three ops. reserve n cuts off n bytes and gives an option, grow enlarges the last piece in place, and used answers how much has been used. An actor (chapter 25) is an object that holds its own state and is spoken to only with send. Here it is enough to know that it is made with spawn actor and called with send a reserve 3.

20.2 Cutting borrowed bytes#

The simplest allocator is a bump allocator. It keeps one cursor, cuts off as much as requested, and pushes the cursor forward.

    buf (8 bytes)
    [ a  a  a │ b  b │ ·  ·  · ]
      └ the piece reserve 3 gave
                └ the piece reserve 2 gave
                       ▲ cursor (used = 5) --- the next reserve cuts from here

asking reserve 4: only 3 bytes are left → none (running short is a value too)

module borrowed .
rem run: carve [0,0,0,0,0,0,0,0]

use allocs .

proc carve input buf mut slice u8 . output u64 . effects state .
do
  var a allocs.bump_bytes be spawn actor allocs.bump_bytes .
  let room u64 be send a init buf .
  let p option mut slice u8 be send a reserve 3 .
  guard is_some p . else return 91 .
  let pv mut slice u8 be some_value p .
  set (index pv 0) 65 .
  let q option mut slice u8 be send a reserve 99 .
  guard not (is_some q) . else return 92 .
  return send a used .
end

$ lowentc --run carve borrowed.low [0,0,0,0,0,0,0,0]
carve([65,0,0,0,0,0,0,0]) = 3
  arg0 (written) = [65,0,0,0,0,0,0,0]

• spawn actor allocs.bump_bytes makes the allocator, and send a init buf hands it the bytes to cut. This allocator cannot make memory by itself — the discipline of never allocating secretly.
• send a reserve 3 cuts off 3 bytes. What comes back is not a copy but a slice pointing at part of the original, so set (index pv 0) 65 . changes the first byte of the caller’s buf. The argument [65,0,…] the VM shows is the trace.
• send a reserve 99 gives none because there is not enough space. Not a trap. Running out of memory is a value, and the caller checks it.

This op’s head has neither cap allocator nor alloc; its effect is only state. The caller lent the bytes, and the allocator merely hands them out. The capability draws the line — code without an allocation capability can still allocate fully on bytes someone gave it.

20.3 Swapping allocators#

Code that uses an allocator need not know which implementation it is. It takes the allocator’s type as a translation-time parameter and its value with a using clause.

module generic .
rem run: with_bump [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
rem run: with_aligned [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

use allocs .

proc two_from
  input comptime a type .
  using al a .
  output u64 .
  effects state via a .
  requires allocs.byte_allocator a .
do
  let p option mut slice u8 be send al reserve 3 .
  guard is_some p . else return 91 .
  let q option mut slice u8 be send al reserve 5 .
  guard is_some q . else return 92 .
  return send al used .
end

proc with_bump input buf mut slice u8 . output u64 . effects state .
do
  var b allocs.bump_bytes be spawn actor allocs.bump_bytes .
  let c u64 be send b init buf .
  let n u64 using b be two_from .
  return n .
end

proc with_aligned input buf mut slice u8 . output u64 . effects state .
do
  var b allocs.bump_aligned be spawn actor allocs.bump_aligned .
  let c u64 be send b init buf .
  let n u64 using b be two_from .
  return n .
end

$ lowentc --run with_bump generic.low [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
with_bump([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]) = 8
  arg0 (written) = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
$ lowentc --run with_aligned generic.low [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
with_aligned([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]) = 13
  arg0 (written) = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

• input comptime a type . is the allocator’s type, fixed to a concrete type at translation (chapter 22).
• using al a . receives the allocator value of that type under the name al. using is not an input. The caller does not write it in an argument position but in the binding, as let n u64 using b be two_from ..
• requires allocs.byte_allocator a . is the condition that a satisfies the trait (chapter 23).
• effects state via a . means the effects of the allocator’s reserve are this op’s effects.

Given bump_bytes, the same two_from uses 3 + 5 = 8; given bump_aligned, which aligns start positions to multiples of 8, the second piece starts at 8 and it uses 13. Because the type is fixed at translation, there is no virtual function table and no indirect call. Swapping costs nothing at run time.

If no source is written, a default is chosen: the binding’s using, the op’s own using name, and otherwise the input or binding of matching type if there is only one. With two or more it does not guess and asks you to write it with E-ALLOC-AMBIGUOUS. Defaults do not cross op boundaries — an allocator from the caller never flows in on its own, so there is no global allocator.

Fields are not counted. If an allocator hidden inside a struct were used silently, reading the code would not tell you which buffer shrinks.

With no source at all, the call is refused.

module nosource .
rem expect: E-ALLOC-NOSOURCE

use allocs .

proc one_from
  input comptime a type .
  using al a .
  output u64 .
  effects state via a .
  requires allocs.byte_allocator a .
do
  let p option mut slice u8 be send al reserve 3 .
  guard is_some p . else return 91 .
  return send al used .
end

proc caller output u64 . effects state .
do
  rem ✘ there is no allocator at all in this op to draw from
  let n u64 be one_from .
  return n .
end

$ lowentc --check nosource.low
21:16 E-ALLOC-NOSOURCE: this call draws from an allocator, but NO value of a fitting type is visible in this op — no input, no binding, no `using` clause. There is no global allocator: take one as an input, create one here, or declare `using <name> <type> .` on this op (RFC-0112 D8(4))
nosource.low:19:1 W-EFFECT-OVER: this op DECLARES `state` but never PERFORMS it. A declared effect is a cost the caller must budget for (a pure caller cannot call an `io` op). Drop it, or — if a future version will perform it — say so (RFC-0007)

caller has no input, no spawned actor and no using clause. In another language a global heap would quietly step in here. Lowent asks you to take an allocator as an input, create one here, or write a using clause. Because the call is refused, caller never really uses state either, so W-EFFECT-OVER comes along. It goes away once the first error is fixed.

The other way round, writing using on a call that draws from no allocator is refused too.

module usingunused .
rem expect: E-ALLOC-USING-UNUSED

use allocs .

fn twice input x u64 . output u64 . do
  return mul x 2 .
end

proc caller input buf mut slice u8 . output u64 . effects state .
do
  var b allocs.bump_bytes be spawn actor allocs.bump_bytes .
  let c u64 be send b init buf .
  rem ✘ twice draws from no allocator, yet the binding picks one with using
  let n u64 using b be twice 4 .
  return n .
end

$ lowentc --check usingunused.low
15:19 E-ALLOC-USING-UNUSED: this binding says which allocator to use, but the call it initialises does not draw from one (no `using` clause on that op). An object that already carries its allocator — like `vecgen.append` on a vector — does not take the caller's choice (RFC-0112 D8(5))

twice only doubles a number and takes no allocator. A choice that will never be used misleads the reader into thinking twice uses memory. So whatever you write must be used.

20.4 Default allocators that carve straight from a root#

allocs also provides two allocators that carve straight from a root, under the same trait.

module fixed .
rem run: main

use allocs .

proc main input al cap allocator . output u8 . effects alloc state .
do
  var fb allocs.fixed_bytes be spawn actor allocs.fixed_bytes .
  let a option mut slice u8 be send fb reserve 64 .
  guard is_some a . else return 1 .
  let b option mut slice u8 be send fb reserve 64 .
  guard is_some b . else return 2 .
  return narrow u8 (send fb used) .
end

$ lowentc --run main fixed.low
main() = 128

fixed_bytes’s state has a capability field. A capability is not a run-time value, so the field has no size. Instead a rule comes with it: an actor with a capability field can be spawned only from an op that holds a capability of the same kind.

module forge .
rem expect: E-CAP-FORGE

use allocs .

proc sneaky output u64 . effects heap state .
do
  var hb allocs.heap_bytes be spawn actor allocs.heap_bytes .
  return send hb used .
end

$ lowentc --check forge.low
forge.low:8:0 E-CAP-FORGE: this spawns an actor whose state HOLDS a capability (`cap allocator` / `cap heap`), but the op spawning it holds no capability of that kind. A capability field means nothing at run time — it is only real because the place that creates the actor already had the right. Without that, one `spawn` would forge authority out of thin air (RFC-0112 D6). Take the capability as an input of this op
forge.low:7:1 W-EFFECT-OVER: this op DECLARES `heap` but never PERFORMS it. A declared effect is a cost the caller must budget for (a pure caller cannot call an `io` op). Drop it, or — if a future version will perform it — say so (RFC-0007)

sneaky tried to spawn heap_bytes without receiving cap heap. If that were allowed, a heap could be conjured in one line where there is no capability. Capabilities are handed over, not picked up.

Receive the capability and the same thing works.

module heapbytes .
rem run: main

use allocs .

proc main input h cap heap . output u8 . effects heap state .
do
  var hb allocs.heap_bytes be spawn actor allocs.heap_bytes .
  rem the heap hands out 100000 bytes, more than the fixed window (64 KiB by default) holds
  let a option mut slice u8 be send hb reserve 100000 .
  guard is_some a . else return 1 .
  rem return 2 if the amount used is not 100000, and 0 if it is
  guard eq (send hb used) 100000 . else return 2 .
  return 0 .
end

$ lowentc --run main heapbytes.low
main() = 0

main receives cap heap and writes heap in its effects line. So it may spawn heap_bytes, and it gets 100000 bytes, more than the fixed window holds. When the heap runs short it chains another chunk. Built for a machine without an operating system, this file is refused with E-HEAP-NOHOST (chapter 18).

20.5 Growing and returning a piece — grow and release#

A bump allocator only moves forward. Even so, the piece it handed out last is safe to take back, because nobody has received a place after it. grow enlarges that piece in place, and release (trait freeing_allocator) takes it back.

module growrelease .
rem run: regrow [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

use allocs .

proc regrow input buf mut slice u8 . output u64 . effects state .
do
  var b allocs.bump_bytes be spawn actor allocs.bump_bytes .
  let c u64 be send b init buf .
  let p option mut slice u8 be send b reserve 4 .
  guard is_some p . else return 91 .
  let pv mut slice u8 be some_value p .
  rem grow the piece just received from 4 to 6 bytes in place
  let g option mut slice u8 be send b grow pv 6 .
  guard is_some g . else return 92 .
  let gv mut slice u8 be some_value g .
  let q option mut slice u8 be send b reserve 2 .
  guard is_some q . else return 93 .
  let qv mut slice u8 be some_value q .
  rem gv is not the last piece (qv comes after it), so it is not taken back
  let back1 bool be send b release gv .
  rem qv is the last piece, so it is taken back
  let back2 bool be send b release qv .
  let u u64 be send b used .
  var d1 u64 be 0 .
  if back1 . do
    set d1 1 .
  end
  var d2 u64 be 0 .
  if back2 . do
    set d2 1 .
  end
  rem pack the amount used, the first answer and the second answer into one three-digit number
  return add (mul u 100) (add (mul d1 10) d2) .
end

$ lowentc --run regrow growrelease.low [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
regrow([0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]) = 601
  arg0 (written) = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

• send b grow pv 6 grows pv from 4 bytes to 6. What it grows is the piece itself, not a size. The implementation checks with the builtin same_slice a b (same start address and same length?) that pv is exactly the bytes it just handed out. Pass someone else’s buffer of the same length and the answer is none. Recognising a piece by size alone would let two containers overlap without a sound.
• After qv is handed out, gv is no longer the last piece. So release gv is false and changes nothing.
• release qv is true. The cursor goes back to 6, so used is 6. The answer 601 reads “used 6 · first answer false · second answer true”.

Both ops are an optimisation, not a promise. If a piece cannot grow, the caller receives a new one and copies, and the answer must be the same. For fixed_bytes and heap_bytes, which carve straight from a root, grow is always none. A root does not know whose piece came last.

20.6 Where the three layers sit in the standard library#

Only the two actors that reach a root hold a capability. Everything else works on bytes someone handed over. So library code that received no capability can still build and grow containers, and to find the code that brings new memory into the program you only look at the ops that received a capability.

20.7 Who sets the size of the fixed window?#

On a machine without an operating system, the fixed window is the memory between two symbols set by the linker. Its size is not baked into the executable. The compiler emits a linker-script fragment, and only the size in that fragment changes per board.

$ lowentc --emit-ldscript --fixed-bytes 4096 fixed.low
.lw_fixed (NOLOAD) : ALIGN(8)
{
    __lw_fixed_start = .;
    . = . + 4096;
    __lw_fixed_end = .;
}

To imitate another board on the host, give the VM a window size. fixed.low asks for 64 bytes twice, so shrinking the window to 100 bytes with lowentc --fixed-bytes 100 --run main fixed.low makes the second reserve return none and prints main() = 2. You can see on your development machine where a small machine runs out of memory.

20.8 Same bits, different reading#

Reading the same bytes as a different type comes in two kinds. view, which lays a struct layout over a byte slice, was seen in chapter 13. Keeping the bit pattern between two scalars of the same width and changing only how it is read is bit_cast.

module bitcast .
rem run: reinterpret -1
rem run: float_bits 1.0

fn reinterpret input x i32 . output u32 .
do
  return bit_cast u32 x .
end

fn float_bits input f f64 . output u64 .
do
  return bit_cast u64 f .
end

$ lowentc --run reinterpret bitcast.low -1
reinterpret(-1) = 4294967295
$ lowentc --run float_bits bitcast.low 1.0
float_bits(1.0) = 4607182418800017408

The −1 of an i32 has every bit set, so read as a u32 it is 4294967295. Reading the f64 1.0 as a u64 shows its IEEE 754 representation as is. Unlike cast, it does not move the value, so it never stops.

The target type must be one where every bit pattern is a valid value. bool and enum are not.

module bitcast_bool .
rem expect: E-TYPE-BITCAST

fn truthy input a u8 . output bool .
do
  return bit_cast bool a .
end

$ lowentc --check bitcast_bool.low
bitcast_bool.low:6:0 E-TYPE-BITCAST: bit_cast's target must be a `plain` scalar type — every bit pattern valid, no padding (SPEC-004 §190). bool/enum have trap representations and are NOT plain, so they are outside safe punning

Reading the u8 value 2 as a bool would give a value that is neither true nor false. The path that creates such values is closed.

20.9 Common mistakes#

module mistake_noinit .
rem expect: E-ACTOR-UNINIT

use allocs .

proc carve input buf mut slice u8 . output u64 . effects state .
do
  var a allocs.bump_bytes be spawn actor allocs.bump_bytes .
  rem ✘ `send a init buf` is missing --- asks an allocator that has no bytes to hand out
  let p option mut slice u8 be send a reserve 3 .
  guard is_some p . else return 91 .
  return send a used .
end

$ lowentc --check mistake_noinit.low
mistake_noinit.low:10:0 E-ACTOR-UNINIT: this is the FIRST message sent to an actor that was just spawned, and the handler READS a state field that holds a slice without setting it. A fresh actor's state is all zeroes, and zero is not a slice: the VM stops (`len needs a slice`) while native quietly answers `none` — the two back ends disagree, which means one of them is lying. Send the message that sets it up first (the one whose handler `set`s that field, typically `init`)

module mistake_sharedbuf .
rem expect: E-EXCL

use allocs .

proc twice input buf mut slice u8 . output u8 . effects state .
do
  var a allocs.bump_bytes be spawn actor allocs.bump_bytes .
  var b allocs.bump_bytes be spawn actor allocs.bump_bytes .
  rem ✘ the same bytes are given to two allocators --- both hand out the same place
  let c1 u64 be send a init buf .
  let c2 u64 be send b init buf .
  let p option mut slice u8 be send a reserve 3 .
  let q option mut slice u8 be send b reserve 3 .
  guard is_some p . else return 91 .
  guard is_some q . else return 92 .
  let pv mut slice u8 be some_value p .
  let qv mut slice u8 be some_value q .
  set (index pv 0) 65 .
  set (index qv 0) 66 .
  rem 65 was written, yet 66 comes back
  return index pv 0 .
end

$ lowentc --check mistake_sharedbuf.low
mistake_sharedbuf.low:12:0 E-EXCL: the same WRITABLE place was handed to a SECOND actor. A write borrow is exclusive (§8.4): two actors holding the same bytes both hand them out, so two containers silently overlap and a write through one is read through the other (measured: 65 written, 66 read back). Give each actor its own bytes — `subslice` the buffer into pieces that do not overlap

module mistake_ambiguous .
rem expect: E-ALLOC-AMBIGUOUS

use allocs .

proc two_from
  input comptime a type .
  using al a .
  output u64 .
  effects state via a .
  requires allocs.byte_allocator a .
do
  let p option mut slice u8 be send al reserve 3 .
  guard is_some p . else return 91 .
  return send al used .
end

proc with_two input small mut slice u8 . input big mut slice u8 . output u64 . effects state .
do
  var s allocs.bump_bytes be spawn actor allocs.bump_bytes .
  var g allocs.bump_bytes be spawn actor allocs.bump_bytes .
  let x u64 be send s init small .
  let y u64 be send g init big .
  rem ✘ two allocators of a fitting type are in scope, and the call does not say which
  let n u64 be two_from .
  return n .
end

$ lowentc --check mistake_ambiguous.low
25:16 E-ALLOC-AMBIGUOUS: this call draws from an allocator, and MORE THAN ONE value of a fitting type is in scope — the tool will not guess which one you meant. Say it on the binding: `let <name> <type> using <allocator> be …` (RFC-0112 D8(4))

module ambiguous_fixed .
rem run: with_two [0,0,0,0] [0,0,0,0,0,0,0,0]

use allocs .

proc two_from
  input comptime a type .
  using al a .
  output u64 .
  effects state via a .
  requires allocs.byte_allocator a .
do
  let p option mut slice u8 be send al reserve 3 .
  guard is_some p . else return 91 .
  return send al used .
end

proc with_two input small mut slice u8 . input big mut slice u8 . output u64 . effects state .
do
  var s allocs.bump_bytes be spawn actor allocs.bump_bytes .
  var g allocs.bump_bytes be spawn actor allocs.bump_bytes .
  let x u64 be send s init small .
  let y u64 be send g init big .
  rem name the source on the binding with `using`
  let n u64 using g be two_from .
  let m u64 using g be two_from .
  return m .
end

$ lowentc --run with_two ambiguous_fixed.low [0,0,0,0] [0,0,0,0,0,0,0,0]
with_two([0,0,0,0], [0,0,0,0,0,0,0,0]) = 6
  arg0 (written) = [0,0,0,0]
  arg1 (written) = [0,0,0,0,0,0,0,0]

module mistake_novia .
rem expect: E-EFFECT

use allocs .

proc one_from
  input comptime a type .
  using al a .
  output u64 .
  rem ✘ no `via a` --- the `alloc` the allocator performs is not part of this op's declaration
  effects state .
  requires allocs.byte_allocator a .
do
  let p option mut slice u8 be send al reserve 3 .
  guard is_some p . else return 91 .
  return send al used .
end

proc with_fixed input al cap allocator . output u64 . effects alloc state .
do
  var fb allocs.fixed_bytes be spawn actor allocs.fixed_bytes .
  let n u64 using fb be one_from .
  return n .
end

$ lowentc --check mistake_novia.low
mistake_novia.low:13:1 E-EFFECT: this op performs `alloc`, which its `effects` clause does not declare — add it to `effects …`, or stop calling what needs it
mistake_novia.low:20:1 W-EFFECT-OVER: this op DECLARES `alloc` but never PERFORMS it. A declared effect is a cost the caller must budget for (a pure caller cannot call an `io` op). Drop it, or — if a future version will perform it — say so (RFC-0007)

module shared_window .
rem run: main

use allocs .

proc main input al cap allocator . output u8 . effects alloc state .
do
  rem two allocators, but only one fixed window
  var f1 allocs.fixed_bytes be spawn actor allocs.fixed_bytes .
  var f2 allocs.fixed_bytes be spawn actor allocs.fixed_bytes .
  let a option mut slice u8 be send f1 reserve 40000 .
  guard is_some a . else return 1 .
  rem `f2` has used nothing yet, but the window has too little room left
  let b option mut slice u8 be send f2 reserve 40000 .
  guard is_some b . else return 2 .
  return 0 .
end

$ lowentc --run main shared_window.low
main() = 2

20.10 This chapter’s syntax at a glance#