HeapLab: Finalizers, Generations and a Write Barrier

HeapLab: A Teaching Garbage Collector That Has to Grow Up

You've joined Runtime Education, the team behind HeapLab: a simulated managed heap that instructors use to teach garbage collection, and that the "why is my program leaking?" explainer is built on. HeapLab models objects, references, roots, a heap limit and a collector. It is a teaching tool, so the output has to be exactly right: students compare it against what they work out by hand.

The collector shipped in a hurry and four tickets have come in. After those are closed, the roadmap asks for finalizers, then a generational collector, then speed. Each Part builds on the previous one, and everything earlier Parts specify must keep working unless a later Part says otherwise.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh heap and returns one result per operation. Every operation is [name, *args]. Errors are returned as "error: <code>" strings, never raised, and a failed operation changes nothing unless its row says otherwise.

The object model. An object has a numeric id (shown as "o1", "o2", ... in allocation order, never reused), a size in bytes, and any number of named fields, each holding null or the id of another object. A field that was never set reads as null. *Garbage* (an object nothing reaches) stays in the heap, and stays readable and writable, until a collection frees it. used_bytes is the total size of every object still in the heap, garbage included.

References. A reference argument is either null or an id string. Anything that is not the id of an object that was ever allocated ("oops", "o01", 7, "o999") is error: unknown object. The id of an object that was allocated and later freed is error: object freed. Ids sort numerically: o9 comes before o10 everywhere a list of ids is returned.

• A size, count, or limit is an integer > 0 (true/false are not integers here). A field or variable name is a non-empty string.
• copy_field stores src.src_field into dst.dst_field. swap_fields exchanges two slots; a slot that was never set counts as null.
• chain n size allocates n objects of size bytes, each linked to the next through its next field, and returns the first. It allocates like alloc does (so everything below about the heap limit applies to every node), and while it runs the head of the chain is kept alive, so a collection triggered halfway cannot free the nodes already built.
• An unknown operation name is error: unknown operation. A wrong number of arguments, or an operation that is not a non-empty list starting with a string, is error: invalid arguments.
• A failed alloc does not use up an id. get_global of a name that was never set is null.

---

Part 1 - Close the four incident tickets

Four tickets are open against the collector, and the tests/ directory already contains failing tests. Find the causes and fix them. The desired behavior:

• INC-4417 "Lab 7 builds a 10,000-element linked list and collect crashes."
• INC-4421 "After I pop a frame, the objects only it referenced are never freed. If I then push a new frame, those objects are still alive."
• INC-4430 "A second collect frees nothing, even though I dropped the only reference to a big structure. Worse: objects I attached to a survivor after the first collection get freed while still reachable."
• INC-4433 "My lab sets a limit of 100 bytes, keeps 10 bytes alive, and still gets out of memory. stats.bytes never goes down after a collection, either."

The rules (the first three are the ground truth the collector is measured against):

1. Roots are every global variable, every local variable in every frame *currently on the stack*, and nothing else. An object is *reachable* if a root references it, directly or through any chain of fields (cycles are fine, a chain can be tens of thousands of objects long). Everything else is garbage.
2. collect frees exactly the garbage and returns its ids ascending. Each freed object returns its bytes to used_bytes and counts once in stats.freed. Survivors are untouched, and collecting again later must work exactly as the first time.
3. Popping a frame discards its locals. A frame pushed later starts with no locals at all.
4. Heap limit. limit sets (or with null removes) a cap on used_bytes; setting it never collects. alloc size when a limit L is set:

• size > L -> out of memory immediately, nothing is collected.
• otherwise, if used_bytes + size > L, run one collection (exactly what collect does, counted in stats.collections). If used_bytes + size still exceeds L, out of memory.
• otherwise (it fits, used_bytes + size == L is allowed) just allocate.

1. stats: objects is the number of objects in the heap (garbage included), bytes is used_bytes, collections counts every collection run so far (explicit or triggered by alloc), freed is the total number of objects freed so far.

Worked example 1

[["alloc", 16], ["alloc", 8], ["alloc", 24],
 ["set_field", "o1", "next", "o2"],
 ["set_global", "head", "o1"],
 ["collect"],
 ["stats"]]

returns

["o1", "o2", "o3", true, true, ["o3"],
 {"objects": 2, "bytes": 24, "collections": 1, "freed": 1}]

o1 is a global's target and o2 hangs off it; o3 is garbage.

Worked example 2

[["limit", 64], ["push_frame"], ["alloc", 32], ["set_local", "tmp", "o1"], ["alloc", 32],
 ["pop_frame"], ["alloc", 16], ["live"], ["stats"]]

returns

[true, 1, "o1", true, "o2", 0, "o3", ["o3"],
 {"objects": 1, "bytes": 16, "collections": 1, "freed": 2}]

The second 32-byte object brings used_bytes to exactly 64, which is allowed. After the frame is popped nothing is rooted, so the 16-byte allocation triggers a collection that frees both.

---

Part 2 - Finalizers

Some lab objects own something that must be cleaned up (an open file in the demo). Add finalizers: an object can be allocated with a finalizer, and when the collector finds it unreachable it gets one chance to run it before the object is really freed. A finalizer is allowed to *resurrect* its object by storing it into a global.

1. alloc size [finalizer] takes an optional second argument: null or omitted means no finalizer, "log" means a finalizer that only records that it ran, "revive:NAME" (a non-empty NAME) means a finalizer that stores the object itself into global NAME, overwriting whatever the global held. Anything else is error: invalid finalizer. Check order for alloc: invalid size, invalid finalizer, then the heap-limit rules.
2. A collection proceeds in these steps (for explicit collect and for collections started by alloc alike):
3. Mark everything reachable from the roots.
4. The candidates are the unmarked objects that have a finalizer that has not run yet.
5. Everything reachable from any candidate (candidates included, so a candidate that is only reachable from another candidate is still a candidate) is kept alive for this collection.
6. Sweep: everything still unmarked is freed. The returned list contains only those objects, never a candidate or something a candidate reaches.
7. Run the candidates' finalizers in ascending numeric id order.
8. Running a finalizer marks the object *finalized* (its finalizer never runs again, whatever happens to it later), appends its id to the finalizer log, and, for "revive:NAME", performs the global store. Finalizers run after the sweep, so a store they perform is only seen by the *next* collection.
9. A finalized object is a perfectly ordinary object afterwards: if it is unreachable at a later collection it is freed without running anything.
10. A reachable object is never a candidate, whatever finalizer it has.
11. finalizer_log returns the ids of every finalizer run so far, in the order they ran.

Worked example

[["alloc", 8, "log"], ["alloc", 8, "revive:saved"], ["alloc", 8],
 ["set_field", "o2", "peer", "o3"],
 ["collect"], ["finalizer_log"], ["get_global", "saved"],
 ["collect"], ["live"], ["finalizer_log"]]

returns

["o1", "o2", "o3", true,
 [], ["o1", "o2"], "o2",
 ["o1"], ["o2", "o3"], ["o1", "o2"]]

First collection: nothing is reachable, so o1 and o2 are candidates, o3 survives through o2, and nothing is freed. Both finalizers run (o2 stores itself into saved). Second collection: o2 is reachable again (and so is o3); o1 is unreachable and already finalized, so it is simply freed.

---

Part 3 - A generational collector (requirements change)

Course labs now run allocation-heavy programs, and a full mark of the whole heap on every collection is what students complain about. The team is moving HeapLab to a generational design. Parts 1 and 2 keep describing what a *major* collection does; this Part adds the cheaper *minor* collection and changes what happens under heap pressure.

1. Every new object starts young (in the nursery) with age 0. Objects that are not young are old. Young and old objects live in one id space and may reference each other freely.
2. collect is a major collection: the whole heap, exactly as in Parts 1 and 2. Afterwards every survivor, including objects resurrected by finalizers, is old, and the nursery is empty.
3. minor runs a minor collection and returns the ids it freed, ascending. It only reclaims young objects and never looks at old ones:

• A young object *survives* if it is reachable from a root through young objects, or it is referenced by any old object (reachable or not, the minor collection must not care), or it is reachable from either of those through young objects.
• Finalizers: a young unreachable object with a pending finalizer is a candidate and works as in Part 2, with "reachable" meaning as above and only young objects considered. Finalizers run after the sweep in ascending id order.
• All other young objects are freed.
• A minor collection therefore defers to the next major collection: old garbage, finalizers of old objects, and young objects whose only referrer is a dead old object.
• It never frees anything a major collection run at that moment would have kept.

1. After a minor collection every young survivor's age goes up by 1, and one whose age has reached PROMOTE_AGE (2, see config.py) becomes old. An object must survive two minors to be promoted.
2. Every way a reference gets stored must be accounted for, because an old object that points at a young one is the only thing keeping that young object alive across a minor collection. References are stored by set_field, copy_field (into the destination) and swap_fields (into both slots), by churn below, and, less obviously, by promotion: a young object that becomes old may point at survivors that stay young.
3. Heap pressure changes (this replaces the middle bullet of Part 1 rule 4): when used_bytes + size > L and size <= L, alloc first runs a minor collection. If the object still does not fit it runs a major one. If it still does not fit: out of memory. The two collections each count in stats.collections. The rest of Part 1 rule 4 is unchanged.
4. gen ref returns "nursery" or "old" (errors as for any reference). gen_stats returns:

The behavior a program can observe is unchanged: whichever minors run, an object a program can still reach is never freed, and after a major collection the survivors are exactly what Parts 1 and 2 define. Existing Part 1 and Part 2 behavior for heaps whose garbage is all young is identical.

Worked example

[["alloc", 8], ["set_global", "cache", "o1"], ["collect"],
 ["alloc", 8], ["set_field", "o1", "slot", "o2"],
 ["minor"],
 ["set_global", "cache", null],
 ["alloc", 8], ["minor"],
 ["gen", "o2"], ["live"], ["collect"]]

returns

["o1", true, [],
 "o2", true,
 [],
 true,
 "o3", ["o3"],
 "old", ["o1", "o2"], ["o1", "o2"]]

The major collection made o1 old. o2 is young but referenced by o1, so the first minor keeps it (age 1). Once cache is cleared o1 is garbage, but the next minor can't know that: o2 survives again and reaches age 2, so it is promoted, while the unreferenced young o3 is freed. Only the next major collection frees the two old objects.

---

Part 4 - Fast under allocation pressure

The instructor labs for the new collector are *allocation churn* programs: a big long-lived structure sits in the heap, a tight limit is set, and a loop creates short-lived objects while one old object keeps pointing at the latest result. Add that loop as an operation, and make it fast.

• churn n size keep holder field: the object currently held by global holder is the *holder*. For i = 1..n, allocate an object of size bytes exactly like alloc (including the heap-limit rules and everything they trigger), and if i is a multiple of keep, store the new object in holder.field exactly like set_field. Returns the id of the last object stored, or null if none was. Errors, in order: invalid count (n), invalid size, invalid count (keep), invalid name, invalid field, then unknown object if the global is unset or null. If an allocation fails with out of memory, churn stops and returns that error; the objects allocated so far stay.
• The hidden tests build old generations of tens of thousands of objects (with chain, then collect) and run tens of thousands of allocations behind a limit that leaves only a few hundred bytes of headroom, so minor collections run constantly. The cost of a minor collection must depend on the number of young objects and the number of old objects that point at young ones, not on the size of the heap, and allocation must stay cheap too. Results must not change: the same ids, the same gen_stats and stats.

Worked example

[["alloc", 8], ["set_global", "cache", "o1"], ["collect"],
 ["limit", 40],
 ["churn", 10, 8, 3, "cache", "slot"],
 ["get_field", "o1", "slot"], ["gen_stats"], ["stats"]]

returns

["o1", true, [], true, "o10", "o10",
 {"young_objects": 4, "young_bytes": 32, "old_objects": 1, "old_bytes": 8,
  "minor_collections": 2, "major_collections": 1, "remembered": 1},
 {"objects": 5, "bytes": 40, "collections": 3, "freed": 6}]

The third, sixth and ninth churned objects (o4, o7, o10) are stored into o1.slot; two minor collections are triggered by pressure (when o6 and o9 are allocated) and free the churned garbage while keeping the one object o1 points at.