Pools for Lifetimes That Don't Nest

Everything so far has relied on lifetimes that nest. A value is created in a scope and dies when that scope ends, and anything created after it dies before it. Most data really is like that, which is why data stacks work so well.

Some data is not. Patients join a waiting list and leave in any order. Entries in a cache are evicted by age, not by when they were added. Files in a directory tree are created and deleted at will. For data like this, Goose has the reusable pool: a grow-only array whose slots can be handed back and handed out again. This chapter shows how pools work, and why the safety story still holds when you use them.

#A pool of slots14.1

Declare a grow-only array of fixed-size elements reusable, and the compiler pairs it with a hidden list of free slots:

struct Egg { day: i32, grams: f32 }

fn main() {
    reusable var tray: Egg[>..] = [];
    let a = tray.alloc_index(Egg { 1, 60.0 });
    let b = tray.alloc_index(Egg { 2, 61.0 });
    tray.free(a);
    let c = tray.alloc_index(Egg { 3, 70.0 });      // takes slot a back
    print(a, " ", b, " ", c, ", ", tray.len, " slots");
}

0 1 0, 2 slots

That looks like an allocator. The important thing is what free does not do.

#Freeing frees nothing14.2

free does not release memory, end a lifetime or invalidate anything. It adds an index to the free list, and that is all. The freed slot still holds a valid value of the element type, and it still belongs to the pool, which still lives until its scope ends.

So a reference to a slot that has been freed and reused is not a dangling pointer. It reads the slot's new occupant: a perfectly valid value of the right type, just not the one you were thinking of.

struct Egg { day: i32, grams: f32 }

fn main() {
    reusable var tray: Egg[>..] = [];
    let first = tray.alloc_index(Egg { 1, 60.0 });
    let old .= tray[first];
    tray.free(first);
    tray.alloc_index(Egg { 3, 70.0 });
    print(old);                                      // the slot's new egg
}

Egg { 3, 70.0 }

This is a logic bug, of exactly the same kind as keeping an index into an array after you have overwritten that element. It is not a memory-safety bug. Nothing is read at the wrong type, nothing goes out of bounds, and nothing is read after it was freed, because nothing ever is. That is the whole extent of the unsafety a pool adds, and it is confined to the data you chose to put in one.

To keep this guarantee, a pool only allows what keeps every slot a valid value forever. Its elements must be fixed-size, and it can never shrink:

struct Egg { day: i32 }

fn main() {
    reusable var tray: Egg[>..] = [];
    tray.alloc_index(Egg { 1 });
    tray.pop();
}

error: cannot pop reusable pool tray: its slots stay live for the freelist (§5.4)

#A waiting list14.3

Here is a pool used for what pools are best at: a structure that is edited in arbitrary order. Geese wait to see the vet in a circular doubly linked list. The list has a sentinel node, head, which is allocated before main runs. Because of the sentinel, no link is ever null, and adding or removing a patient is the same four stores whatever the position.

struct Patient { name: u8[..8], prev: Patient&<u32 in queue>, next: Patient&<u32 in queue> }

reusable var queue: Patient[>..] = [];
let head = queue.alloc_index(Patient { name: "", prev: self, next: self });

fn arrive(name: u8[:]) -> Patient& {
    let tail .= queue[head].prev;
    let p .= queue.alloc_ref(Patient { name: name, prev: tail, next: queue[head] });
    tail.next .= p;
    queue[head].prev .= p;
    return p;
}

fn leave(p: Patient&) {
    p.prev.next .= p.next;
    p.next.prev .= p.prev;
    queue.free(queue.index_of(p));
}

fn show() {
    var out: u8[>..] = [];
    var cur .= queue[head].next;
    while cur .!= queue[head] { format(out, cur.name, " "); cur .= cur.next; }
    print(out, "(", queue.len, " slots)");
}

fn main() {
    arrive("Ada");
    let bea .= arrive("Bea");
    arrive("Cleo");
    let dot .= arrive("Dot");
    show();
    leave(bea);
    leave(dot);
    show();
    arrive("Eve");
    arrive("Fern");
    show();
}

Ada Bea Cleo Dot (5 slots)
Ada Cleo (5 slots)
Ada Cleo Eve Fern (5 slots)

When Bea and Dot leave, their slots go on the free list, and Eve and Fern take them over. The pool never grows past five slots, however long the program runs, as long as at most four geese are waiting at a time.

Look at the .= in let bea .= arrive("Bea"). A Patient is fixed-size, so a plain let bea = arrive("Bea") would copy the patient out of the pool, and leave(bea) would then be asked to unlink a copy. The compiler rejects that, because index_of needs a reference it can prove points into queue. With .=, bea is the patient in the pool.

#Local pools and pool parameters14.4

A pool does not have to be global. A local reusable var works the same way, and lives as long as its scope. A parameter of type T[>..]& bound to a pool carries the free list with it, so a function can allocate from and free into a pool that it is handed:

struct Egg { day: i32, grams: f32 }

fn hatch(tray: Egg[>..]&, slot: i64) { tray.free(slot); }

fn main() {
    reusable var tray: Egg[>..] = [];
    let a = tray.alloc_index(Egg { 1, 60.0 });
    tray.alloc_index(Egg { 2, 61.0 });
    hatch(tray, a);
    print(tray.alloc_index(Egg { 3, 59.0 }), " ", tray.len);
}

0 2

#Slice pools14.5

A plain pool hands out single slots. A reusable[] pool hands out runs of consecutive elements instead, which suits things like the child lists of nodes in a tree, where each node's children should be one contiguous slice:

fn main() {
    reusable[] var pens: i64[>..] = [];
    let a = pens.alloc_slice(3);
    a[0] = 1; a[1] = 2; a[2] = 3;
    let b = pens.alloc_slice(2);
    b[0] = 7; b[1] = 8;
    pens.free_slice(a);
    let c = pens.alloc_slice(2);           // reuses the start of a's run
    let d = pens.realloc_slice(b, 4);      // b ends the array, so it grows in place
    print(c, " ", d, " ", pens);
}

[0, 0] [7, 8, 0, 0] [0, 0, 3, 7, 8, 0, 0]

The 3 left in the middle of the array belongs to the free remainder of a's old run. Like a single-slot pool, a slice pool never frees memory and never shrinks, so every element is always a valid value.

#When to use a pool14.6

Reach for a pool when data is created and destroyed in an order that does not follow the structure of your code: caches, queues of things that leave in any order, graphs that are edited, game entities that are spawned and removed. If the data's lifetime matches a scope, even a long one, you do not need a pool. A plain grow-only array owned by that scope is simpler and faster.

#Exercises14.7

1. Extend the waiting list with a function jump_queue(p: Patient&) that moves a patient to the front of the list. You only need to unlink it and link it back in after head; the slot does not change.

2. Write a program that allocates 1000 eggs from a pool, freeing each one straight after it is allocated. How long is the pool at the end? What if you free only every other egg?

3. Explain why it is safe to keep a reference to a freed slot, but not to keep a reference into a grow-shrink array across a pop.