Skip to content
LEARN MINIUnderstand Mini memory 16 of 26About 40 min

16. Allocators and arenas ​

In Managed code every Foo(...) allocates with reference counting. To decide where objects come from, you put an allocator in scope and the compiler uses it for every allocation site inside.

These cells are Check cells

Programs that use allocator objects are checked by the compiler today, and native code generation for them is still in progress (see the roadmap). So the cells in this chapter and the next have a Check button instead of Run: it runs the same memory checker as minic check, in your browser.

By the end: distinguish allocation strategy from memory-checking mode, read an allocator context and explain why an arena object cannot escape its region. A value copied out of an object and a reference to that object have different lifetime requirements.

Allocators are ordinary classes ​

They live in mini.memory:

AllocatorFreesNotes
Heapobject by object, with free()malloc and free
Arenaeverything at once, when it is closedbump allocator, the cheapest
Pool<T>(capacity)object by object, T blocks onlyfixed-size free list
Rcautomaticallythe Managed default

Allocators are context parameters ​

An allocator is not a hidden global: it is a context parameter. A function declares which allocator it allocates from, and the caller decides.

kotlin
@file:MemoryMode(Mode.Strict)

import mini.memory.*

class Node(val value: Int, val next: Node?)

// The allocator is a context parameter: the caller decides where the nodes live.
context(a: Arena)
fun range(n: Int): Node? {
    var head: Node? = null
    for (i in n downTo 1) head = Node(i, head)
    return head
}

fun sum(list: Node?): Int {
    var total = 0
    @Borrowed var cur = list
    while (cur != null) {
        total += cur.value
        cur = cur.next
    }
    return total
}

fun main() {
    Arena().use { arena ->
        context(arena) {
            println(sum(range(4)))
        }
    }
}

range is declared context(a: Arena). It builds a linked list in whichever arena its caller provides. main creates the arena, use {} closes it at the end of the block, and context(arena) { ... } puts it in scope. Press Check: the checker accepts the program (it prints 10 when run on the JVM).

A context(...) { } block can also name an allocator directly, which is how a Heap is used:

kotlin
@file:MemoryMode(Mode.Strict)

import mini.memory.*

class Box(val v: Int)

fun main() {
    context(Heap()) {          // allocations in this block come from the Heap
        val b = Box(41)        // b owns the allocation
        println(b.v + 1)
        b.free()               // ownership ends here; forgetting this is error M0102
    }
}

Box(41) inside the block allocates from the Heap, so b owns it, and b.free() ends the ownership. Delete the b.free() line, press Edit and then Check to see what happens. That is the subject of the next chapter.

Arenas ​

An Arena allocates by bumping a pointer and frees everything when it closes. There is nothing to forget and nothing to double free. In return there is a lifetime rule: an object allocated in an arena must not outlive it.

kotlin
@file:MemoryMode(Mode.Strict)

import mini.memory.*

class Point(val x: Int, val y: Int)

context(a: Arena)
fun diagonal(n: Int): Point = Point(n, n)

fun main() {
    // The Int leaves the arena scope; the Points do not. That is allowed.
    val total = Arena().use { arena ->
        context(arena) {
            var t = 0
            for (i in 1..3) t += diagonal(i).x + diagonal(i).y
            t
        }
    }
    println(total)
}

The Int leaves the arena block, the Points do not. The checker accepts that. This is the program that breaks the rule:

kotlin
@file:MemoryMode(Mode.Strict)

import mini.memory.*

class Box(val v: Int)

fun build(): Box {
    Arena().use { arena ->
        context(arena) {
            return Box(1)      // the Box lives in `arena`, which is gone after the return
        }
    }
}

fun main() {
    println(build().v)
}

M0105: the Box lives in arena, which is gone when build returns. Without the checker this would be a dangling pointer. Allowed: passing arena objects inward, copying out values that need no allocation, and a context(a: Arena) function returning arena objects to its caller (the region is then the caller's).

Pools and @AllocatedBy ​

A Pool hands out blocks of one class from a free list. @AllocatedBy(Pool::class) says that a class can only be allocated from one:

kotlin
@file:MemoryMode(Mode.Strict)

import mini.memory.*

@AllocatedBy(Pool::class)      // instances of Item must come from a Pool in scope
class Item(val id: Int)

fun main() {
    Pool<Item>(2).use { pool ->
        context(pool) {
            val a = Item(1)
            val b = Item(2)
            println(a.id + b.id)
            a.free()           // pool objects are freed one by one
            b.free()
        }
    }
}

A warning, not an error ​

Allocating in a loop inside an arena is legal, but nothing is reclaimed before the arena closes. The checker tells you with the warning M0202:

kotlin
@file:MemoryMode(Mode.Strict)

import mini.memory.*

class Box(val v: Int)

fun main() {
    var total = 0
    Arena().use { arena ->
        context(arena) {
            for (i in 0 until 3) {
                val b = Box(i)     // a new arena object per iteration: nothing is freed until the end
                total += b.v
            }
        }
    }
    println(total)
}

Warnings do not fail a build unless you pass -Werror.

Checkpoint ​

Who decides the lifetime of objects returned by a function requiring context(a: Arena)? Why is returning point.x different from returning point?

Reasoning

The caller supplies the arena and its region. Returning a primitive coordinate copies a value that does not depend on the arena; returning the point keeps a reference into that region. An arena created and closed inside the function cannot supply a valid escaping object.

Exercise ​

Exercise: keep the arena object inside

This function returns an object that lives in an arena that is closed by then, error M0105. Change it so the checker accepts it: return the plain Int instead of the Box.

kotlin
@file:MemoryMode(Mode.Strict)

import mini.memory.*

class Box(val v: Int)

fun build(): Box {
    Arena().use { arena ->
        context(arena) {
            return Box(7)
        }
    }
}

fun main() {
    println(build().v)
}
Show solution
kotlin
@file:MemoryMode(Mode.Strict)

import mini.memory.*

class Box(val v: Int)

fun build(): Int {
    Arena().use { arena ->
        context(arena) {
            return Box(7).v      // an Int may leave the arena, the Box may not
        }
    }
}

fun main() {
    println(build())
}

Released under the Apache License 2.0.