Add a Mark-and-Sweep GC to Your VM

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:

Mark: starting from roots (globals, frame locals, operand stack), recursively mark reachable objects
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.

Add a mark-and-sweep garbage collector to your VM in C.

Requirements:

Define an Obj struct with type, mark bit, size, next pointer (for allocation list), and a union for data (strings, closures, or lists)
Implement allocate_object() that allocates from a fixed-size heap or via malloc, adding the object to an allocation list
Implement mark_object() that sets an object's mark bit and recursively marks any objects it references
Implement mark_roots() that marks all objects reachable from the operand stack, all call frame locals, and global variables
Implement sweep() that iterates the allocation list, frees unmarked objects, and clears marks on live objects
Implement collect_garbage() that runs mark_roots() then sweep(), printing heap stats
Demonstrate allocating several objects, letting some become unreachable, and running GC
Show heap stats: total objects, bytes allocated, bytes freed, bytes remaining

Test:

Show GC running
Show mark phase identifying live objects
Show sweep phase freeing dead objects
Show heap statistics before and after collection

Mark-and-Sweep Collection

Phases and Root Set

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

Mark: starting from roots (globals, frame locals, operand stack), recursively mark reachable objects
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

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.

Add a mark-and-sweep garbage collector to your VM in C.

Requirements:

Define an Obj struct with type, mark bit, size, next pointer (for allocation list), and a union for data (strings, closures, or lists)
Implement allocate_object() that allocates from a fixed-size heap or via malloc, adding the object to an allocation list
Implement mark_object() that sets an object's mark bit and recursively marks any objects it references
Implement mark_roots() that marks all objects reachable from the operand stack, all call frame locals, and global variables
Implement sweep() that iterates the allocation list, frees unmarked objects, and clears marks on live objects
Implement collect_garbage() that runs mark_roots() then sweep(), printing heap stats
Demonstrate allocating several objects, letting some become unreachable, and running GC
Show heap stats: total objects, bytes allocated, bytes freed, bytes remaining

Test:

Show GC running
Show mark phase identifying live objects
Show sweep phase freeing dead objects
Show heap statistics before and after collection

Topic Overview

Mark-and-Sweep Collection

Phases and Root Set

Design Notes

For This Exercise

Implementation Task

Progressive Hints

Resources

Open Source

Add a Mark-and-Sweep GC to Your VM

Topic Overview

Mark-and-Sweep Collection

Phases and Root Set

Design Notes

For This Exercise

Implementation Task

Progressive Hints

Resources

Open Source