Mark-Sweep Garbage Collector for Bytecode VM

This project implements a Stop-the-World Mark-Sweep Garbage Collector integrated into a stack-based virtual machine. It ensures memory safety by automatically reclaiming unreachable heap objects.

Features

• Heap Allocation: Dynamic support for Pairs, Functions, and Closures
• Root Discovery: Scans the VM operand stack for live references
• Cycle Handling: Correctly marks circular data structures (e.g., circular linked lists)
• Safety: Typed stack values (VAL_INT vs VAL_OBJ) prevent invalid memory access

Prerequisites & Platform Support

Supported Platforms

This project is written in standard C99 and is designed to be cross-platform. It has been tested on:

• Linux (Ubuntu/Debian, Fedora)
• macOS (via Terminal)
• Windows (via WSL, MinGW, or Cygwin)

Build Requirements

To compile the project, you need the following installed on your system:

• C Compiler: gcc (GNU Compiler Collection) or clang.
• Build Tool: make (GNU Make).

Verify Installation:

gcc --version
make --version

Build Instructions

1. Build the System

make all

This produces two executables:

• assembler: Converts .asm source files to .bin bytecode
• vm: The virtual machine with garbage collection support

2. Clean Build Artifacts

make clean

Usage

Running Assembly Programs

1. Assemble

   ./assembler tests/test1.asm

2. Execute

   ./vm a.bin -verbose

   The -verbose flag prints the stack state after every instruction.

Triggering the Garbage Collector

The GC is triggered automatically when the heap limit (512 objects) is exceeded. You can also explicitly trigger a collection in assembly:

PUSH 0
PUSH 0
NEW_PAIR    ; Allocate object
POP         ; Make it unreachable
GC          ; Explicitly trigger collection

Testing & Benchmarks

1. Functional Verification (Unit Tests)

A C-based test suite verifies GC logic such as reachability, cycles, and deep object graphs.

make test

Expected Output:

=== All Tests Passed ===

2. Integration Tests

Run all assembly scripts in the tests/ folder:

make test_asm

3. Performance Benchmarks

CPU Throughput

./assembler tests/stress_test.asm
time ./vm a.bin

Result: ~71 MIPS on standard hardware

GC Stress Test

./assembler tests/gc_benchmark.asm
time ./vm a.bin

Result: ~50,000 allocations handled in < 0.03s

Project Structure

• src/: Source code (vm.c, gc.c, assembler.c, etc.)
• tests/: Assembly tests (.asm) and C test suite (test_gc.c)
• docs/: Documentation
• Makefile: Build scripts