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
varof 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.
Build a program from an earlier chapter with
--no-collector. What does it refuse, and how do you fix it?Build
buffer.zenowith the pool size from its report, then with one byte less, and run each.Replace the
list[int or none]above with an enumReadingwith a caseMissing, and build it.