Memory: regions and references
Every program has to decide when a piece of memory can be reused. C hands you malloc and free and trusts you to pair them correctly. Java, Go and Python run a garbage collector, a part of the runtime that periodically scans memory to find values nothing refers to any more and frees them. Rust uses a borrow checker: a compiler pass that tracks which variable owns each value and how long every reference to it lives. kola takes a fourth path: memory is grouped into regions, and the compiler checks the lifetime of a region as a whole rather than the lifetime of each value. There is no garbage collector and no borrow checker.
The idea underneath is the arena: a chunk of memory that allocations draw from by bumping a pointer, and that is freed in one step. Nothing is freed out of an arena individually. Game engines and compilers have used arenas for decades; kola makes them the only way to allocate, and makes their use checkable.
A region: a block with its own arena
Here is the smallest useful region, holding one counter. Hover over the highlighted pieces:
use std::log;
struct Acc { hits: u32, misses: u32 }
fn main() -> u8 !{alloc(heap), log} {
region r {
let acc: &r mut Acc = alloc in r mut Acc { hits: 0, misses: 0 };
acc.hits = acc.hits + 1;
log::info(f"hits={acc.hits} misses={acc.misses}");
}
0
}Everything you do with memory in kola is a variation on this: open a region, allocate in it with alloc in r ..., work through the reference &r T you get back, and let the closing brace free it.
Why this is safe, and what it costs
Without a collector or a borrow checker, what keeps this memory-safe? It helps to name the classic bugs first. A use-after-free reads or writes memory after it has been freed and possibly handed to someone else. A double free releases the same block twice and corrupts the allocator. A data race happens when two threads touch the same memory at the same time and at least one of them writes. Use-after-free is ruled out because the only way to free memory is to close a region, and the region is written into every reference's type, so no reference can outlive it (the next section shows the error). Double free is ruled out because there is no free. Stack values (the local variables of a function, which disappear when it returns) live in a built-in region called 'local under the same rule. Every index carries a bounds contract that is proven or checked, never skipped (Contracts, traps, and tests). And references never cross a thread boundary, so a region is reachable from one thread only (Threads and channels).
There are two costs. Memory stays allocated until its region ends, even if a value was only needed at the start, so peak usage is higher than with precise free calls; you control it by choosing where regions begin and end. And inside a live region two references may point at the same value and both may write through it, because kola has no general rule that a &mut is unique. Since references stay on one thread, this is neither undefined behaviour nor a race. What the compiler will not catch is the logic bug of writing through one reference and being surprised by the change through the other. The exclusivity rule kola does have is local to a single call, and it comes up below.
The rule: a reference does not outlive its region
Every memory error the compiler reports comes down to one thing: carrying a &r T past the end of region r, either by returning it or by storing it somewhere typed with a longer-lived region. Here a reference from a short region is stored into a variable that belongs to heap:
struct Acc { hits: u32, misses: u32 }
fn main() -> u8 !{alloc(heap)} {
let mut keep: &heap Acc = alloc in heap Acc { hits: 0, misses: 0 };
region r {
let acc: &r Acc = alloc in r Acc { hits: 3, misses: 0 };
keep = acc; // r ends before keep does
}
0
}error[card §2]: region mismatch: `heap` vs `'r1`
--> escape.kl:7:16
|
7 | keep = acc; // r ends before keep does
| ^^^The repair is to copy the data out instead of the reference. Plain data such as a u32 copies freely. If the region is the last statement of a function that returns a value, the region's tail becomes the function's return value, which is often the neatest way to do it:
struct Acc { hits: u32, misses: u32 }
fn tally() -> u32 !{} {
region r {
let acc: &r mut Acc = alloc in r mut Acc { hits: 0, misses: 0 };
acc.hits = acc.hits + 3;
acc.hits // a u32, copied out as the function's result
}
}
test tally_copies_the_data_out {
assert tally() == 3;
}The escape rule still applies to that tail: returning acc itself would be a type error. Anywhere else a region is a statement, not an expression: let x = region r { ... }; is refused, and the help suggests assigning an outer let mut binding inside the block instead. Regions nest, and references into an outer region stay usable inside an inner one; only the inside-out direction is forbidden.
heap is a region too
heap is a built-in region that lasts for the whole program: its closing brace is the process exit. No collector hides behind the name, and alloc in heap ... works like allocation in any other region. Use it for what really must live that long, and give temporary work its own region so the memory comes back at the brace.
String literals show the difference between static and allocated data. A plain "..." literal is static program data, so it allocates nothing and fits any region; with nothing asking for less, its type is &heap str. The same is true of a byte string behind a reference, &b"...", which is &heap [u8].
An interpolated string is different. f"n={n}" is rendered at run time, so it allocates, and the compiler needs to know where. It takes the region named by the destination if there is one (let s: &r str = f"...", a -> &r str return type, a &heap str field); otherwise the innermost open region; otherwise the literal is refused. A string never lands in heap silently, because a daemon rendering one message per request into heap would keep every one of them forever; when you mean program lifetime, write heap at the destination. An f-string passed straight to a call, as in log::info(f"x {n}"), mints nothing: it is built in a stack buffer for that call. f64::to_str and the network operations that return an address follow the same rule, and a parameter that only reads a string should be the call-scoped &str described below.
Functions over any region: [r]
A function that takes a reference usually does not care which region it came from. For that, the region becomes a parameter, a lowercase name in square brackets:
fn first_byte[r](bytes: &r [u8]) -> Option[u8] !{} {
if bytes.len == 0 { None } else { Some(bytes[0]) }
}
// A struct that holds a reference carries a region parameter.
struct Header[r] { body: &r [u8] }
test first_byte_in_any_region {
region q {
let data = alloc in q [7u8, 8u8, 9u8];
let b = first_byte(data); // r is inferred as q
assert b == Some(7u8);
}
}A call never spells a region. You may write type and const arguments (f[u64](x)), but the region is always inferred from the arguments, the destination or the enclosing region block. A region-generic type, on the other hand, keeps its region argument wherever the type is written: Header[r], never a bare Header in a type position.
A function that allocates into r must mention r in a parameter or in its return type. A signature like fn f[r](n: u64) -> u64 !{alloc(r)} gives no caller any way to bind r, and the checker flags it. If the caller is meant to own the memory, pass it in: fn f[r](out: &r mut Vec[u8], ...). If the memory is only scratch for the call, open a region inside the function.
Returning &r T for a region parameter is allowed, because the region belongs to the caller and outlives the call. This is how kola parses without copying. Here a frame's first byte is a length and the rest is the payload; body returns the payload as a slice of the same buffer:
// Frame: [len, payload...]. Return the payload without copying it.
fn body[r](frame: &r [u8]) -> &r [u8] !{}
req frame.len >= 1
{
frame[1..]
}
test zero_copy_body {
region r {
let f = alloc in r [3u8, 10u8, 20u8, 30u8];
let b = body(f); // b points into the same buffer
assert b.len == 3;
assert b[0] == 10;
}
}In the escape example a reference tried to outlive its own region; here it goes back into the region it came from, and the types alone tell the compiler which is which.
Call-scoped references: &T and &mut T
A reference without a region name, &T or &mut T, exists only as a parameter type. The function may use it for the duration of the call, but can neither store nor return it. In exchange, such a parameter accepts anything: a stack variable, a value in any region, a field of a struct. That is why count_even(xs: &[u64]) in Basics worked with an array on the stack.
Write &T by default, and &r T only when the function stores or returns the reference, as body does. The region name promises the callee that the data outlives the call, and &T accepts strictly more callers. A stack value lives in 'local and can never satisfy &r T, so if you see region mismatch: 'local vs 'r, change the parameter first, not the allocation.
struct Gauge { level: u32 }
// Read for the duration of the call.
fn is_high(g: &Gauge) -> bool !{} {
g.level > 100
}
// Modify in place. The caller keeps ownership.
fn raise(g: &mut Gauge, by: u32) !{} {
g.level = g.level +% by;
}
test call_scoped_refs {
// A stack variable.
let mut a = Gauge { level: 40 };
raise(&mut a, 70);
let hi = is_high(&a);
assert hi; // 110 > 100
// A value in a region. The same parameters accept it.
region r {
let g: &r mut Gauge = alloc in r mut Gauge { level: 5 };
raise(g, 3);
let lo = is_high(g);
assert lo == false; // 8 is not > 100
}
}Returning a call-scoped reference is an error at the signature:
struct Gauge { level: u32 }
fn leak(g: &Gauge) -> &Gauge !{} {
g
}error[card §5]: call-scoped `&T` exists only as a parameter type
--> leak.kl:3:4
|
3 | fn leak(g: &Gauge) -> &Gauge !{} {
| ^^^^
= help: to store or return a reference, give it a region: &r TTwo rules keep call-scoped views sound. A &mut argument to a call may not overlap any other &mut argument, or any shared & argument, of the same call; two shared borrows may alias each other freely. And while a view into a place is still in use (a reference, a subslice, a for loop walking a Vec), that place is not written, grown, shrunk or moved through any other name. The usual repair is to finish reading first, copy the value out (let x = v[i];), or keep the index and read the place again after the change.
A third kind of reference goes into a region and has its own keyword: a view of a resource, let v: &r Buf = lend buf in r;. It freezes buf until the region closes, and it belongs with linearity, so Resources and linearity covers it.
Arrays, vectors and slices
There are three ways to hold a sequence:
An array
[T; N]has a fixed length known at compile time and can live on the stack:let a = [1u64, 2u64, 3u64];.A
Vec[T]grows. It can be region-backed (alloc in r mut Vec::new()), in which casepushandinsertallocate intorand carry!{alloc(r)}. Or it can be owned, a bareVec::new()held by value, in which case its storage isheapwherever theVecitself lives and growing it is!{alloc(heap)}.Vec::new()itself allocates nothing.A slice
&[T]is a view into either of the other two. Functions that read a sequence almost always take one.
A Vec has push, insert(i, x), pop, truncate(n), clear(), swap(i, j), .len and indexing, plus the bulk methods extend_from_slice, resize and copy_from_slice. Only the ones that can grow it allocate.
An owned Vec is a small header over a buffer, so copying it would give two headers one buffer. Instead it moves: passing it by value, binding it with let or storing it in a field hands it over, and the old name cannot be read afterwards. The same holds for any value carrying an owned Vec, such as a struct with a Vec field. To keep using a Vec, borrow it: &Vec[T] to read, &mut Vec[T] to write.
fn sum(xs: &[u64]) -> u64 !{} {
let mut s: u64 = 0;
for x in xs {
s = s +% x;
}
s
}
// Grows an owned Vec, so the row says alloc(heap).
fn fill(out: &mut Vec[u64], n: u64) !{alloc(heap)} {
for i in 0..n {
out.push(i);
}
}
test vec_array_slice {
region r {
let v: &r mut Vec[u64] = alloc in r mut Vec::new();
v.push(1u64);
v.push(2u64);
assert sum(v) == 3; // a region Vec coerces to a slice
}
let mut owned: Vec[u64] = Vec::new();
fill(&mut owned, 4); // borrowed, so still ours
assert sum(&owned) == 6;
let moved = owned; // moved: `owned` is no longer readable
assert moved.len == 4;
let a = [5u64, 6u64, 7u64];
assert sum(&a) == 18; // an array behind a reference is a slice
assert sum(&a[1..3]) == 13; // a sub-slice: elements 1 and 2
}Reading owned after let moved = owned; is refused as a use after a by-value pass, and the help text suggests borrowing instead.
Seeing what a region holds: kola test --sim
kola test --sim prints each region's high-water mark: the largest amount of memory the region ever held. Two things are charged to a region: the value at each alloc in r ... site, and the growth of a container's backing buffer. When a Vec doubles under push, the new buffer is charged and the old one stays counted, because an arena does not free individual items. Reuse is free: clear(), truncate(n) and pop() only move .len.
test region_watermark {
region r {
// An array: its size is known at the alloc site (24 bytes).
let arr: &r mut [u64; 3] = alloc in r mut [5u64, 6u64, 7u64];
// A Vec: empty at the alloc site, grown by push.
let v: &r mut Vec[u64] = alloc in r mut Vec::new();
v.push(5u64);
v.push(6u64);
v.push(7u64);
// Reuse: clear keeps the capacity, so this push charges nothing.
v.clear();
v.push(8u64);
let ok = arr[0] == 5u64;
assert ok;
let n = v.len;
assert n == 1;
}
}Run it with kola test --sim --interp and the result line is followed by the region's figure:
w.kl: test region_watermark ... ok
region r: 88 bytes region-charged high-water (arena-faithful)24 of those bytes are the array and the rest is the vector's growth. Delete the three push calls and the figure drops to 24. Delete clear() and the push after it, and it stays at 88: that is the reuse rule at work.
The number only goes up, like the arena it models: it answers "how large did this region get", not "how much is live now". Under the interpreter it is a simulated byte count, while a native build charges the real arena's requested bytes, with its own alignment and padding. The two agree on whether a budget is exceeded at a comfortable margin, not on the exact byte where it would flip.
Memory budgets
The same accounting enforces budgets. region r from m backs the arena with a memory budget m carved from the Mem capability (see Effects and capabilities), and every charge is checked against it. A push that grows a vector past the budget traps at the push (a trap stops the program deterministically at that point, with a message naming the line):
fn main(mut sys: Sys) -> u8 !{io, block, alloc(heap)} {
let m: Mem = sys.mem.split(4096);
region r from m {
let v: &r mut Vec[u64] = alloc in r mut Vec::new();
let mut i: usize = 0;
while i < 1000 {
v.push(1u64); // every doubling is charged to m
i = i + 1;
}
}
sys.mem.absorb(m);
0
}$ kola run budget.kl
trap: error[card §7]: memory budget exceeded in region
--> budget.kl:7:13
|
7 | v.push(1u64); // every doubling is charged to m
| ^^^^^^^^^^^^A region refunds everything it was charged when it closes, on every exit path, so a budgeted region inside a loop does not slowly drain its budget. The region holds m until its closing brace, and sys.mem.absorb(m) inside the block is refused. A plain region r with no from is unbounded, and a plain region nested inside a budgeted one draws from the same budget.
Long-lived data that dies piece by piece: Pool
A lexical region does not suit long-lived state whose objects come and go in no particular order: caches, session tables, object graphs. A structure that is rebuilt rather than appended to would keep every old version until the region closed. For that there is Pool[T], a slot allocator with per-slot freeing. Pool is built into the compiler, so it is not defined under std/; STD-CARD lists its full surface.
struct Session { id: u64 }
test pool_generations {
region r {
let p: &r mut Pool[Session] = alloc in r mut Pool::new(8);
let h1 = p.insert(Session { id: 1 });
let h2 = p.insert(Session { id: 2 });
match p.get(h1) {
Some(s) => { assert s.id == 1; }
None => { assert false; }
}
assert p.len == 2; // live occupancy, not capacity
p.remove(h1); // the slot can be reused
assert p.len == 1;
assert p.get(h1).is_none();
match p.get(h2) {
Some(s) => { assert s.id == 2; }
None => { assert false; }
}
}
}Each slot carries a generation number, and a Gen[T] handle remembers the generation it was issued for. remove advances the slot's generation, so every old handle goes stale at once and get on it returns None. A pointer to a dead object becomes an ordinary None you have to handle.
A handle also records which pool issued it, so using it on another pool is a deterministic miss, even on a pool created later in the same memory. Without that, two pools of the same type would hand out identical first handles, and a lookup in the wrong table (say, the session pool of a different peer) would quietly succeed against the wrong element.
Capacity is part of the interface. insert on a full pool is a trap (of kind Capacity), which is the right answer when your own code decides how many things exist. When an untrusted party drives the count, such as a peer opening sessions, a trap would be a remote denial of service. Use try_insert(v) -> Result[Gen[T], T] instead. Its Err carries the element back to you, because T may be a resource and a refusal that swallowed it would lose it. A full pool does not stay full: after a remove, the next try_insert succeeds.
A reference from get or get_mut must be finished with before remove or anything else that changes the pool. If you need the element after a change, keep its Gen and look it up again, or copy the data out first.
Pools of resources
A pool of resources follows stricter rules. Regions are erased at run time, so a pool living in a region could disappear with its elements still inside, and a resource may never be lost silently. A pool whose T is a resource must therefore be an owned local, let mut p: Pool[Conn] = Pool::new(n);, and the pool itself becomes linear. You empty it, then finish it with p.fin(), which traps if anything is left. drain_next() removes one arbitrary element per call and hands it back with its handle, so teardown is a single loop the compiler can check:
resource struct Link { id: u64 }
impl Link {
pub fn close(self: Link) -> u64 !{} {
let Link { id } = self;
id
}
}
test drain_a_pool_of_resources {
let mut p: Pool[Link] = Pool::new(4);
let _a = p.insert(Link { id: 1 });
let _b = p.insert(Link { id: 2 });
let mut sum: u64 = 0;
loop {
match p.drain_next() {
Some((_g, l)) => { sum = sum + l.close(); }
None => { break; }
}
}
p.fin(); // nothing left, so this cannot trap
assert sum == 3;
}insert needs to know the pool is owned, so inserting a resource through a &mut Pool parameter is refused: the pool's placement is unknown there. The help text names the two repairs: pass the pool by value (take Pool[T] and return it), or wrap it in a resource struct and take &mut of that, since a resource struct is never region-allocated. get, get_mut and remove work through a &mut Pool parameter.
A Pool cannot cross to another thread. A pool of data is copyable, so two threads would end up holding the same slots; own it in one thread and reach it by message (see Threads and channels). A pool also cannot list its live handles. drain_next empties it, but if you need to walk the population without removing it, keep the handles in a Vec[Gen[T]] beside the pool.
The normative reference is SPEC-CARD §4 and §5 (kola help spec-card), with Vec and Pool in STD-CARD.