The Zeno Book Zeno 0.1 zeno-lang.org

32 Building with No Collector

zeno build --no-collector compiles a program to C that has no garbage collector in it. Not a collector that is switched off: the code is not in the file. Nor is malloc: memory comes from a pool of a fixed size that is part of the program. Every block the program takes is given back at a line that can be found in the C. This is the build for a microcontroller that must run for years.

32.1 Why

The collector is the right default (Memory). It also has three habits that firmware cannot always live with:

  • it pauses the program, for a time that depends on how much memory is in use, and a control loop with a deadline cannot plan for that;

  • it reads the C stack to find what is in use, which no C standard describes;

  • nobody can say when a block will be freed, so nobody can say how much memory the program needs at worst.

Owned values answer all three for the values that are owned (Ownership). This build is what you get when every value is.

32.2 Every list and object has one owner

With no collector, there is nothing to free a shared value with. So the build follows one rule by itself:

With no collector, every list and every object has one owner: whoever received it.

In this build list[int] means owned list[int], and class Task means owned class Task, with no word written. The rules of ownership apply to all of them, and the one that matters day to day is that giving a list to another name moves it:

moved.zeno

let a = [1, 2, 3]
let b = a
print(a)
$ zeno check --no-collector moved.zeno
error: `a` was given away on line 2 and holds nothing now. Use it before it goes, or give it only to what looks: a parameter without `take`
 --> moved.zeno:3:7
  |
3 | print(a)
  |       ^

1 error found. Nothing was run.

zeno check --no-collector checks as the build would, without building. A parameter only looks, unless it says take, so passing a list to an ordinary function moves nothing.

The same file must mean the same thing under zeno run, zeno build and zeno build --no-collector. This build adds refusals and nothing else: a program it accepts never gives a value two owners, and for such a program "one owner" and "shared" cannot be told apart from what it prints. Fewer programs, never different ones. (Decision 5.15.)

32.3 An ordinary program, built so

Most programs need no change at all:

names.zeno

let names = "ada,grace,alan".split(",")
var lengths: list[int] = []
for name in names {
    lengths.append(len(name))
}
print(names, lengths)
print(f"the longest is {max(lengths)} letters")
$ zeno build --no-collector --memory names.zeno
Wrote names.c
Built names. Run it with ./names
$ ./names
["ada", "grace", "alan"] [3, 5, 4]
the longest is 5 letters
memory: 12 blocks made (190 bytes), at most 190 bytes in use at once, no collector, 0 blocks left at the end
pool: 384 bytes taken, in a pool of 32768
text: at most 49 bytes in use at once, in a room of 1024

The report has three lines now. The first says how many blocks were made and that none was left at the end. The second is the pool, and the third the text room, both below.

32.4 Where memory comes from

What Lives in Given back
a list or an object the pool when its owner’s block ends
an enum value that carries something the pool when its owner’s block ends
a list made and given to nobody the pool when its statement is over
text built while the program runs the text room when its statement is over
text that is kept the pool when its keeper is done with it
an error the pool when the except that caught it ends
allocate the pool at free, and not before

Numbers, bools, quantities, enum cases with nothing in them, and text written in the program need no memory at all.

The pool

The pool is one array whose size is fixed when the C is compiled, 32 768 bytes unless you say otherwise. It hands out blocks of a few fixed sizes, and keeps a list of spare blocks of each size, so a block given back is used again for the next of its size and the pool cannot break up into pieces too small to use. The report says how much of the pool a run used, exactly, and that is the number to give the C compiler for the board:

$ zeno build --no-collector --memory buffer.zeno
$ ./buffer | grep pool
pool: 25384 bytes taken, in a pool of 32768
$ cc -O2 -DZENO_POOL=25384 -o buffer buffer.c -lm

It is exact for that run. A program whose lists depend on its input needs the report from its worst input, and some room on top. A full pool is a fault: the program stops with the memory pool is full.

The text room

Firmware prints, and print(f"sent {count} samples") builds text that must live somewhere for a moment. It lives in the text room, one more fixed array. Building text writes at the top of the room; when the statement is over, the top goes back to where it was. So a statement takes text room only for as long as it runs, and the report says the most any statement needed. Text that is kept, in a variable, a field or a list, is copied into the pool and kept there.

32.5 What is refused

Each of these would make memory that no line gives back, so the build refuses it, with the line and what to write instead:

  • a list, object or enum value used after it was given away;

  • a function that uses a var of the function around it, because the two would share it;

  • keeping a function that uses a list or object from outside it;

  • a list or object as what a type parameter stands for, and a list of int or none, which are limits of version 0.1.

items.zeno

var readings: list[int or none] = [1, none, 3]
$ zeno build --no-collector items.zeno
error: a list of numbers that may be `none` keeps each item in a small block of its own, and `zeno build --no-collector` leaves the collector out, so nothing would free them. Make it a list of an enum that has one case for a missing value and one case that carries the number, say `Missing` and `Value(n: int)`. docs/no-collector.md lists what such a build accepts
 --> items.zeno:1:35
  |
1 | var readings: list[int or none] = [1, none, 3]
  |                                   ^

The answer the message gives is an enum with a case for the missing value, which costs nothing for the case that carries nothing.

That is the whole idea of the build. It does not find leaks while the program runs. It refuses to build a program that could have one.

32.6 The tour

buffer.zeno from Ownership, built with no collector:

$ zeno build --no-collector --memory buffer.zeno > /dev/null
$ ./buffer
sent 44400 samples, skipped 13 quiet frames
refused 33 frames, the first on channel 84
[3, 3, 3, 3]
4
memory: 1691 blocks made (2646563 bytes), at most 13336 bytes in use at once, no collector, 0 blocks left at the end
pool: 25384 bytes taken, in a pool of 32768
text: at most 53 bytes in use at once, in a room of 1024

It made over 1600 blocks and gave every one back. Search the C for zeno_collect, setjmp or malloc: none is there. --no-collector turns --firmware on by itself.

32.7 What this does not claim

Memory is still taken and given back while the program runs, from a fixed pool and not from the heap. That meets MISRA’s rule against malloc and free, though not its wider advice against dynamic memory of any kind. The build does not bound memory for you: a loop that appends to a list for ever fills the pool. The rest of the list in Firmware stands.

--no-collector leaves the collector and malloc out. Every list and object has one owner, whoever received it, and is freed where that owner’s block ends. Memory comes from a fixed pool, sized with -DZENO_POOL from the --memory report, and built text from a text room that each statement gives back. Whatever could leak is refused at build time.

  1. Build a program from an earlier chapter with --no-collector. What does it refuse, and how do you fix it?

  2. Build buffer.zeno with the pool size from its report, then with one byte less, and run each.

  3. Replace the list[int or none] above with an enum Reading with a case Missing, and build it.