18 Regions — where values live, and memory reclaimed all at once

18.1 Three places values live#

A stored value lives in one of three places.

What are usually called the stack and the heap correspond to local and obtained. The different names are because in this language they are properties of values, not the structure of the machine. And where a value lives is written in the source; the processor does not move things behind your back.

There are two roots memory is obtained from, carved and rewound separately.

The fixed window works even on machines without an operating system. There the window is the space between two bounds set by the linker (chapter 20).

18.2 Opening a region and obtaining space#

A region is opened with region <name> <kind> do … end. Inside the block, alloc_bytes <region> capacity <n> asks that region for n bytes.

module scratch .
rem run: main

proc fill_count input n u64 . output u64 . effects alloc .
do
  region work arena do
    let g option mut slice u8 be alloc_bytes work capacity n .
    guard is_some g . else return 0 .
    let buf mut slice u8 be some_value g .
    var i u64 be 0 .
    while lt i (len buf) . do
      set (index buf i) 7 .
      set i (add i 1) .
    end
    var s u64 be 0 .
    for b buf do
      set s (add s (widen u64 b)) .
    end
    return s .
  end
  return 0 .
end

proc main input al cap allocator . output u8 . effects alloc .
do
  return narrow u8 (fill_count 10) .
end

$ lowentc --run main scratch.low
main() = 70

• region work arena do … end opens a region. arena is the kind meaning “carve from the front and give back all at once”.
• alloc_bytes work capacity n gives an option mut slice u8. If there is not enough space, it is none. Running out of memory is a value too.
• fill_count’s head has effects alloc. Obtaining space is an effect; a pure fn cannot use a region.
• On every path out of the block — reaching the end, return, break or continue of an enclosing loop — the region is rewound. Even leaving with return s . reclaims the buffer. There is no code that gives it back piece by piece.

main receives cap allocator. The alloc effect of fill_count spreads up to it, so a capability authorising that effect is needed (chapter 16). A region block is entitlement to obtain space inside the op that opened it, but the effect still spreads to the caller.

A region’s kind is one of a closed eight — stack, frame, arena, static, heap, mmap, disk, device. Any other word is rejected.

module kinds .
rem run: carve_stack
rem run: carve_static

rem the kind word says what the region is for; in this edition only heap carves from the growing root, the rest from the fixed window
proc carve_stack output u64 . effects alloc .
do
  var n u64 be 0 .
  region r stack do
    let g option mut slice u8 . . be alloc_bytes r capacity 32 .
    if is_some g . do
      set n (len (some_value g)) .
    end
  end
  return n .
end

proc carve_static output u64 . effects alloc .
do
  var n u64 be 0 .
  region r static do
    let g option mut slice u8 . . be alloc_bytes r capacity 64 .
    if is_some g . do
      set n (len (some_value g)) .
    end
  end
  return n .
end

$ lowentc --run carve_stack kinds.low
carve_stack() = 32
$ lowentc --run carve_static kinds.low
carve_static() = 64

A kind word leaves in the code what the region is for. In this edition only heap actually behaves differently — it carves from the growing root. The other seven all carve and rewind in the fixed window, so carve_stack and carve_static get 32 and 64 the same way. The kind is still written, and the list kept closed, for two reasons: the code need not change when the realisation is later tailored to a machine, and a word that could be anything would say nothing. Someone reading region t arena knows “carve from the front, give back all at once”.

fixed window:
    [ a 16 ][ b 32 ][ c 8 ][ ··········· empty ··········· ]
                           ▲ cursor --- the next alloc_bytes carves from here
on reaching end:
    [ ···················································· ]
    ▲ the cursor rewinds to where the region opened --- a · b · c vanish at once

This picture is why nothing leaks even though no value is given back one by one: giving back is moving one cursor.

18.3 Receiving a region#

A region can also be passed as an argument. It is received as input <name> region <type> ., and the type is the name by which that region is called.

module param .
rem run: main

type scratch u64 .

proc sum_squares input temp region scratch . input n u64 . output u64 . effects alloc .
  requires le n 100 .
do
  let g option mut slice u8 be alloc_bytes temp capacity n .
  guard is_some g . else return 0 .
  let buf mut slice u8 be some_value g .
  var i u64 be 0 .
  var s u64 be 0 .
  while lt i n . do
    set s (add s (mul i i)) .
    set i (add i 1) .
  end
  return s .
end

proc main input al cap allocator . output u8 . effects alloc .
do
  region r arena do
    let v u64 be sum_squares r 5 .
    return narrow u8 v .
  end
  return 1 .
end

$ lowentc --run main param.low
main() = 30

sum_squares opens no region itself; it carves inside the region r the caller opened. So the lifetime of the buffer it received is decided by the caller’s region. What is obtained from a region cannot outlive the region; when the region ends, what came from it ends too.

18.4 Nothing is carried out of a region#

Putting bytes obtained from a region into a name outside the region is rejected.

module escape .
rem expect: E-REGION-ESCAPE

proc leak output u64 . effects alloc .
do
  var keep mut slice u8 be subslice "abcd" 0 0 .
  region r arena do
    let g option mut slice u8 be alloc_bytes r capacity 16 .
    if is_some g . do
      set keep (some_value g) .
    end
  end
  return len keep .
end

$ lowentc --check escape.low
escape.low:10:0 E-REGION-ESCAPE: this value was allocated inside a `region` block and is being carried OUT of it. The block RECLAIMS its memory at `end` (SPEC-004 §4.5: the lifetime IS the scope — that is why there is no `free`), so the value would point at bytes the next allocation hands to somebody else. Copy what you need into memory that outlives the block, or move the block outward so it covers every use

When the region closes at end, those bytes are rewound, and keep outside would point at nothing. The places that carry things out are return, assignment to a name outside the region, and assignment to a field or element of such a name. Values that do not carry the region’s bytes — integers and booleans such as len buf or a sum — may be carried out. That is what fill_count did when it returned a sum.

18.5 One cursor per root#

Carving with the name of an outer region while a region of the same root is open inside is rejected.

module nested .
rem expect: E-ALLOC-NESTED

proc f output u64 . effects alloc .
do
  region outer arena do
    region inner arena do
      let g option mut slice u8 be alloc_bytes outer capacity 8 .
    end
  end
  return 0 .
end

$ lowentc --check nested.low
nested.low:8:0 E-ALLOC-NESTED: this allocation names an OUTER source while a region of the SAME root is open inside it. Each root (the fixed window, the heap) has ONE cursor, so the inner region's `end` rewinds past these bytes and hands them to the next allocation — the value would silently change under you (RFC-0112 D4). Allocate from the innermost region, move this allocation outside the inner block, or open the inner region on the other root

The fixed window has a single place it carves from (a cursor). When the inner region ends and rewinds the cursor, bytes obtained in between with the outer name would be rewound with it. A different root — carving with a fixed-window capability inside a heap region — has its own cursor and is fine.

            ▼ where outer opened
                        ▼ where inner opened
            [ a ][ ··· ][ b ][ ✘ c ]
                        ▲ when inner ends the cursor rewinds to here → c vanishes too
   a = outer's · b = inner's · c = carved under the outer name while inner was open (✘ E-ALLOC-NESTED)

For the same reason, an op spawned as a task cannot obtain memory directly from a root (E-ALLOC-TASK), because a cursor is not shared between flows. Sharing an allocator between flows needs an allocator that moves its cursor atomically (chapter 27).

18.6 The growing root#

region <name> heap carves from the growing root.

module heap .
rem run: main

proc grow_twice output u64 . effects heap .
do
  region big heap do
    let a option mut slice u8 be alloc_bytes big capacity 4096 .
    let b option mut slice u8 be alloc_bytes big capacity 4096 .
    guard is_some a . else return 0 .
    guard is_some b . else return 0 .
    return add (len (some_value a)) (len (some_value b)) .
  end
  return 0 .
end

proc main input h cap heap . output u8 . effects heap .
do
  let n u64 be grow_twice .
  guard eq n 8192 . else return 1 .
  return 0 .
end

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

The effect is heap, not alloc, and its partner capability is cap heap. A heap region is also reclaimed all at once when the block is left; it never moves bytes it has already handed out.

When building for a machine without an operating system, the heap cannot be requested through any door.

module heap_mcu .
rem flags: --target cortex_m
rem expect: E-HEAP-NOHOST

proc grow input h cap heap . output u64 . effects heap .
do
  let a option mut slice u8 be alloc_bytes h capacity 4096 .
  guard is_some a . else return 0 .
  return len (some_value a) .
end

$ lowentc --check --target cortex_m heap_mcu.low
heap_mcu.low:5:0 E-HEAP-NOHOST: this op asks for the GROWING root — the `heap` effect, a `cap heap` input or a `region <name> heap` block — but the build target is FREESTANDING (`machine.no_heap`, e.g. cortex_m). A bare-metal board has no allocator that can hand out more memory at run time. What it DOES have is the fixed window its linker script reserves: carve from that with `cap allocator` / `effects alloc` or any other region kind (RFC-0112 D2 · RFC-0038 — the gate is on what the MACHINE cannot do, and only that)

--target cortex_m is a microcontroller without an operating system. The heap effect, cap heap inputs and region … heap blocks are all rejected. On the same machine, alloc carving from the fixed window is still available. Which root code stands on is written in its head, so whether a library runs on a machine without an operating system is answered by translation.

18.7 A stack on a region#

A region hands out more than bytes. stack_new <region> capacity <n> makes a stack of n elements in that region. Use it for “take out what went in last first”, as when walking a tree or graph with a loop.

module stack_demo .
rem run: main

type scratch u64 .

rem take a stack from the region and pile up the digits --- the last one in comes out first
proc reverse_digits input temp region scratch . input n u64 . output u64 . effects alloc .
  requires le n 1000000 .
do
  let work stack u64 be stack_new temp capacity 8 .
  var v u64 be n .
  while gt v 0 . do
    push work (mod v 10) .
    set v (div v 10) .
  end
  var out u64 be 0 .
  var place u64 be 1 .
  while pop work into d . do
    set out (add out (mul d place)) .
    set place (mul place 10) .
  end
  return out .
end

proc main input al cap allocator . output u8 . effects alloc .
do
  region r arena do
    return narrow u8 (reverse_digits r 47) .
  end
  return 0 .
end

$ lowentc --run main stack.low
main() = 74

• let work stack u64 be stack_new temp capacity 8 . makes the stack. It takes space from the region, so it is effects alloc.
• push work x . puts a value in.
• while pop work into d . do … end takes values out one at a time, binding each to d, as long as there is one. When the stack is empty the loop ends — the grammar has no way to stop by popping an empty stack.

Putting in the digits 7 and 4 of 47 brings them out as 4 and 7, giving 74. The stack is reclaimed together with the region, so there is no code to give it back.

18.8 Common mistakes#

module mistake_nocheck .
rem run: buf_len 16
rem trap: buf_len 1000000

proc buf_len input n u64 . output u64 . effects alloc .
do
  region work arena do
    rem ✘ takes it out without asking whether space was granted --- if the window is too small it stops taking out `none`
    let buf mut slice u8 be some_value (alloc_bytes work capacity n) .
    return len buf .
  end
  return 0 .
end

$ lowentc --run buf_len mistake_nocheck.low 16
buf_len(16) = 16
$ lowentc --run buf_len mistake_nocheck.low 1000000
== ir diagnostics (1) ==
0:0 E-VM-NONE: some_value of none (panic)

module mistake_returnbuf .
rem expect: E-REGION-ESCAPE

proc make_buf input n u64 . output mut slice u8 . effects alloc .
do
  region work arena do
    let g option mut slice u8 be alloc_bytes work capacity n .
    guard is_some g . else return subslice "" 0 0 .
    rem ✘ returns bytes that are reclaimed when this block ends
    return some_value g .
  end
  return subslice "" 0 0 .
end

$ lowentc --check mistake_returnbuf.low
mistake_returnbuf.low:10:0 E-REGION-ESCAPE: this value was allocated inside a `region` block and is being carried OUT of it. The block RECLAIMS its memory at `end` (SPEC-004 §4.5: the lifetime IS the scope — that is why there is no `free`), so the value would point at bytes the next allocation hands to somebody else. Copy what you need into memory that outlives the block, or move the block outward so it covers every use
mistake_returnbuf.low:12:0 E-TYPE-RETMUT: this op declares a MUTABLE output (`mut slice`/`mut_ref`) but RETURNS a read-only place — a shared parameter, a `let` without `mut`, a `ref X`, or a subslice/index/field of one. The caller would receive a mutable alias of storage that is only held read-only, and could write through it — laundering the shared / fn-purity guarantee (measured: a pure fn mutated its shared input via such a return). Return a mutable place — a fresh allocation, a `mut`/`owned` parameter, or a `var`/`mut` local — or drop `mut` from the output type

module returnbuf_fixed .
rem run: main

type scratch u64 .

rem the op that receives the region carves from it --- the caller's block decides how long the buffer lives
proc filled_sum input temp region scratch . input n u64 . output u64 . effects alloc .
  requires le n 100 .
do
  let g option mut slice u8 be alloc_bytes temp capacity n .
  guard is_some g . else return 0 .
  let buf mut slice u8 be some_value g .
  var s u64 be 0 .
  for b buf do
    set s (add s (widen u64 b)) .
  end
  return add s (len buf) .
end

proc main input al cap allocator . output u8 . effects alloc .
do
  region r arena do
    let v u64 be filled_sum r 5 .
    return narrow u8 v .
  end
  return 1 .
end

$ lowentc --run main returnbuf_fixed.low
main() = 5

module mistake_fnregion .
rem expect: E-EFFECT-CALC

rem ✘ written as a `fn` on the idea that nothing is left outside, since everything is returned at once
fn scratch_len input n u64 . output u64 .
do
  region work arena do
    let g option mut slice u8 be alloc_bytes work capacity n .
    guard is_some g . else return 0 .
    return len (some_value g) .
  end
  return 0 .
end

$ lowentc --check mistake_fnregion.low
mistake_fnregion.low:6:1 E-EFFECT-CALC: this fn is declared pure but performs `alloc` — make it a `proc` with `effects …`, or remove the effect

module mistake_outlives .
rem expect: E-ALLOC-OUTLIVES

use allocs .

proc carve_inside output u64 . effects alloc state .
do
  var a allocs.bump_bytes be spawn actor allocs.bump_bytes .
  region r arena do
    let g option mut slice u8 . . be alloc_bytes r capacity 16 .
    if is_some g . do
      rem ✘ handing region bytes to an actor born outside the region
      let c u64 be send a init (some_value g) .
    end
  end
  return 0 .
end

$ lowentc --check mistake_outlives.low
mistake_outlives.low:13:0 E-ALLOC-OUTLIVES: this hands bytes from a `region` block to an actor that was born OUTSIDE the block. The actor outlives the region, and nothing here can see whether it keeps the slice — if it does, it will read bytes the region's `end` gave to somebody else (RFC-0112 D5). Create the actor inside the region, or give it memory that outlives it

module outlives_fixed .
rem run: carve_inside

use allocs .

proc carve_inside output u64 . effects alloc state .
do
  var n u64 be 0 .
  region r arena do
    let g option mut slice u8 . . be alloc_bytes r capacity 16 .
    if is_some g . do
      rem the actor is born inside the region too, so both go away together
      var a allocs.bump_bytes be spawn actor allocs.bump_bytes .
      let c u64 be send a init (some_value g) .
      let p option mut slice u8 . . be send a reserve 10 .
      if is_some p . do
        set n (send a used) .
      end
    end
  end
  return n .
end

$ lowentc --run carve_inside outlives_fixed.low
carve_inside() = 10

module loop_region .
rem run: count_outer
rem run: count_inner

rem the region is outside the loop --- the 4096 bytes taken each round pile up until the block ends
proc count_outer output u64 . effects alloc .
do
  var got u64 be 0 .
  region work arena do
    var i u64 be 0 .
    while lt i 100 . do
      let g option mut slice u8 be alloc_bytes work capacity 4096 .
      if is_some g . do set got (add got 1) . end
      set i (add i 1) .
    end
  end
  return got .
end

rem the region is opened inside the loop --- it is rewound at the end of every round
proc count_inner output u64 . effects alloc .
do
  var got u64 be 0 .
  var i u64 be 0 .
  while lt i 100 . do
    region work arena do
      let g option mut slice u8 be alloc_bytes work capacity 4096 .
      if is_some g . do set got (add got 1) . end
    end
    set i (add i 1) .
  end
  return got .
end

$ lowentc --run count_outer loop_region.low
count_outer() = 16
$ lowentc --run count_inner loop_region.low
count_inner() = 100

18.9 This chapter’s syntax at a glance#