Implement a Simple GC for Your Mini-JVM

Topic Overview

GC for Your Mini-JVM

Your toy JVM allocates objects on a simple heap. A mark-and-sweep pass reclaims those unreachable from roots: operand stacks, static fields, and thread-local roots in a real JVM.

Mark-and-Sweep on the Heap

Algorithm:

1. Mark every object reachable from roots (stacks, statics, JNI handles in production)
2. Sweep the object list, freeing unmarked entries
3. Optionally compact to fight fragmentation

Object headers need a mark bit and a link for the allocation list. Reference fields in objects must be traced during mark.

For example, allocate strings and arrays in \`main\`, drop references, run GC, and print freed versus live counts.

This mirrors the algorithm family behind older stop-the-world JVM collectors before regional designs like G1.

Design Notes

Compacting is optional in your toy collector but fragmentation will show up if you allocate variable-size objects repeatedly. Mark-and-sweep alone is enough to learn root scanning discipline.

For This Exercise

This exercise asks you to add mark-and-sweep to your mini-JVM's heap. You will implement root scanning from interpreter stacks and statics, then sweep unreachable objects between bytecode runs.

You will use the same mental model here when reading production interpreter source later in the track. Sketch one concrete input on paper, predict the outcome, then confirm with code. That discipline catches logic errors early and makes debugging far faster when you extend the implementation in follow-on tasks.

Your Task

Add a mark-and-sweep garbage collector to a mini-JVM. The interpreter allocates objects in a fixed-size heap with first-fit placement. When no hole is big enough, it runs the collector. The collector marks from the roots, which are every frame's local variables and operand stack, then sweeps the unmarked objects. It never moves objects, so the heap can fragment. If the collection doesn't free a big enough hole, the program dies with OutOfMemoryError.

Input

# starts a comment.

cCopy
Loading…

Instructions

Locals start as null. Object ids count from 1 in each run.

Rules

• Allocation: take the lowest address where 1 + F consecutive slots are free. If there is none, run a GC (allocation failure) and retry. If it still fails, throw java.lang.OutOfMemoryError: Java heap space (FREE free slots, largest hole H, need S), or … (FREE free slots, need S) when even the total is too small.
• GC: mark everything reachable from all frames' locals and stacks, free the unmarked objects, and print GC #N (REASON): marked M, freed K object(s) (S slot(s)), heap USED/SIZE. The reason is allocation failure or System.gc().
• Exceptions: java.lang.NullPointerException (a field access on null) and java.lang.StackOverflowError (a call when 64 frames exist).
  • Print Exception in thread "main" X, then \tat FUNC(pc P) per frame, innermost first, where P is the instruction index (the call, for callers).
  • Print at most 6 frames, then \t... N more.
• VerifyErrors:
  • VerifyError: stack underflow at FUNC PC (OP)
  • VerifyError: CLASS#ID has no field K
  • VerifyError: no function X
  • VerifyError: FUNC falls off the end
  • VerifyError: stack overflow in FUNC (16 values)
  • VerifyError: FUNC has only N locals (a call passing too many arguments)

Output

cCopy
Loading…

• heapdump: prints @ADDR CLASS#ID [fields], with the fields as #id or null, or (empty heap).
• Success: the entry function's return prints NAME returned after N GC(s); heap USED/SIZE.
• Errors (lines are quoted without surrounding blanks):
  • heap: SLOTS (1-1024)
  • func: NAME locals N (0-8)
  • FUNC: bad instruction: LINE
  • run: no function X
  • unexpected line: LINE

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. The roots are exactly the frames' locals and operand stacks. Values held only by a caller's stack must survive a GC that runs inside a callee.
2. Marking must terminate on cycles, and sweeping must free unreachable cycles.

Hidden tests cover a GC inside nested calls that must keep the callers' objects, an unreachable cycle, an OutOfMemoryError caused by fragmentation, a null dereference, runaway recursion, and verify and parse errors.