Add a Mark-and-Sweep GC to Your VM

Topic Overview

Mark-and-Sweep Collection

Heap objects outlive stack slots. Mark-and-sweep finds unreachable objects by graph traversal from roots, then frees everything unmarked. Lua's collector and CPython's cycle-breaking GC both extend this family of algorithms.

Phases and Root Set

Every heap object carries a mark bit. Collection runs in two passes:

1. Mark: starting from roots (globals, frame locals, operand stack), recursively mark reachable objects
2. Sweep: free unmarked objects, clear marks on survivors

Roots are anything the running program can still reach without loading from the heap. Missing a root means collecting live data; scanning too much means extra pause time.

For example, allocate three string objects, drop two references, run GC, and only the still-referenced string survives.

```c void collect_garbage() { mark_roots(); sweep(); } ```

Trigger collection when allocation fails or crosses a threshold. Print heap stats before and after to see bytes reclaimed.

Design Notes

Treat the operand stack, every frame's locals, and any global roots as scan starting points. Missing one root frees live objects; scanning too much only costs time. Log object counts before and after collection to verify unreachable nodes actually disappear.

For This Exercise

This exercise asks you to add a mark-and-sweep collector to your object-allocating VM. You will implement `mark_roots`, recursive `mark_object`, and `sweep` over an allocation linked list.

Your Task

Give the VM a heap and a mark-and-sweep garbage collector. Objects (ints, strings, pairs) are allocated on demand. Roots are the operand stack and the globals. Collection marks everything reachable from the roots (following pair links, including cycles), then sweeps away the rest. Like clox and Lua, collect automatically when the live-object count reaches a threshold, and double the threshold if a collection frees nothing useful.

Input

cCopy
Loading…

Rules

• Objects get ids #1, #2, … and ids are never reused. nil is not an object.
• Allocation. Before every allocation, if live >= threshold, collect (heap full). If live is still >= threshold, double the threshold and print gc: still full, threshold raised to T. The operands of pair are still on the stack during that collection, so they survive.
• Marking starts from every stack slot and every global and follows car/cdr. It must terminate on cycles.
• Collection output: gc (heap full|explicit): marked M, freed #a #b ..., live L, listing the freed ids in increasing order (or nothing).
• dump prints the stack bottom to top, the globals in order of creation, and the live objects in id order (int V, str "S", pair(#a, nil)).
• stats: allocated A, live L, collections C, threshold T.
• Errors: pair: need two values, pop: stack empty, dup: stack empty, setg: stack empty, getg NAME: undefined global, setcar: need a pair and a value / setcdr: ..., setcar: not a pair / setcdr: not a pair, and threshold: 1..512.

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Mark with an explicit worklist and a mark bit, so a cycle is visited once and deep lists cannot overflow the C stack.
2. Clear the mark bits of survivors during the sweep, ready for the next collection.

Hidden tests cover a long list built with repeated pair while automatic collections raise the threshold, moving a structure between globals, overwriting a global, and every error message.