Garbage Collector Implementation

This project implements a simple garbage collector using the Mark-and-Sweep Algorithm. The garbage collector is written in C and demonstrates key concepts of memory management, including marking reachable objects and sweeping unreachable ones.

Features

• Mark-and-Sweep Algorithm: Automatically frees memory that is no longer reachable.
• Object Management: Supports two object types: integers and pairs.
• Cycle Detection: Handles cyclic references correctly.
• Adaptive Threshold: Dynamically adjusts the garbage collection threshold based on the number of objects.

File Structure

• vm.h: Header file containing type definitions and function declarations.
• vm.c: Implementation of the garbage collector and related functions.
• tests.c: Test cases to validate the garbage collector's functionality.

How It Works

1. Mark Phase: Starting from root objects (global variables and stack), marks all reachable objects.
2. Sweep Phase: Frees all unmarked objects.

Example

[Root] -> [A] -> [B]
           |
           v
          [C]    [D] (unreachable)

After marking: A, B, C are marked
After sweeping: D is freed

Compilation and Execution

To compile the project, use the following command:

gcc -o garbage_collector vm.c tests.c

Run the compiled program:

./garbage_collector

Test Cases

The project includes several test cases:

1. Test 1: Ensures objects on the stack are preserved.
2. Test 2: Verifies that unreachable objects are collected.
3. Test 3: Tests nested object references.
4. Test 4: Handles cyclic references.

Output Example

Test 1: Objects on stack are preserved.
Collected 0 objects, 2 remaining.
Collected 2 objects, 0 remaining.

Test 2: Unreached objects are collected.
Collected 2 objects, 0 remaining.

Test 3: Reach nested objects.
Collected 0 objects, 7 remaining.
Collected 7 objects, 0 remaining.

Test 4: Handle cycles.
Collected 0 objects, 6 remaining.
Collected 6 objects, 0 remaining.

Advanced Topics

Generational GC

Divides the heap into generations to optimize garbage collection for objects with different lifetimes.

Incremental GC

Spreads garbage collection work across multiple program steps to reduce pause times.

Concurrent GC

Runs garbage collection in parallel with the program to minimize interruptions.

Limitations

• Stop-the-World: The program pauses during garbage collection.
• Stack Overflow: Deeply nested structures may cause stack overflow during the mark phase.

License

This project is licensed under the MIT License. See the LICENSE file for details.