# RunMat GC

`runmat-gc` implements a production-oriented, generational mark-and-sweep garbage collector for RunMat. The design prioritizes correctness and predictable semantics for a dynamic language runtime, while keeping performance and simplicity at the forefront. It exposes a stable, handle-based API via `GcPtr<T>` to avoid raw-pointer hazards and to keep integration with the interpreter straightforward.

Key properties:
- Non-moving, generational allocation by default (young/old generations)
- Mark-and-sweep collection with promotion based on survival counts
- Explicit root management (stack, globals, persistents, test roots)
- Write barrier and remembered-set tracking for old→young references
- Centralized statistics (`GcStats`) and configurable policies (`GcConfig`)
- Stable handle type (`GcPtr<Value>`) re-exported from `runmat-gc-api`


## Architecture

The GC is composed of the following subsystems:

- HighPerformanceGC: Top-level façade that unifies configuration, allocator, collector, roots, 
  and write-barrier state. Provides public API (allocate, collect, stats, configure, root ops).

- GenerationalAllocator: Owns heap memory across generations. Tracks young allocations, survivors, 
  and promotion thresholds. Supports fast young-generation allocation and statistics query.

- MarkSweepCollector: Implements the marking from explicit roots and sweeping of unmarked objects, 
  including promotion decisions for survivors.

- RootScanner and Root Registry: Centralizes explicit roots registered at runtime (e.g., VM stack, 
  globals, persistents, test harness roots). During a collection, the collector queries the root 
  registry to seed the mark phase.

- WriteBarrierManager + CardTable: Records old→young references at mutation sites so that minor 
  collections can scan remembered-set entries instead of all old-gen objects.

- Stats and Configuration: `GcStats` exposes running counters (allocations, collections, promotions, 
  etc.). `GcConfig` governs thresholds (minor trigger ratio, young generation sizing, and more).


## Handle model (`GcPtr`)

`GcPtr<T>` is a thin, stable handle to GC-managed objects. In the current implementation:

- Allocation is non-moving, so the pointer remains stable for the object's lifetime.
- `GcPtr<T>` implements `Deref`/`DerefMut` to provide `&T`/`&mut T`. The only `unsafe` required by 
  the system lives inside those trait impls; user code should not write any `unsafe` for dereferencing.
- `GcPtr<T>` is `Copy + Clone`-like via a trivial bitwise copy (we implement `Clone`), so APIs that need 
  to retain a handle should explicitly clone it when passing ownership to a registry. Tests were updated 
  to clone when adding/removing roots to avoid moves.

Note on moving/compaction: If a future configuration introduces object moving/compaction, we will add a 
forwarding/indirection layer so that existing `GcPtr` values remain valid without changing embeddings.


## Roots

The collector discovers live objects by scanning registered roots. The system supports:

- Stack roots: The interpreter maintains a vector of live `Value` slots; a VM-specific adapter 
  registers these with the root scanner for the duration of interpretation.
- Global/persistent roots: Long-lived dictionaries for MATLAB `global` and `persistent` variables are 
  registered as global roots for the lifetime of the VM.
- Variable-array roots: For temporary arrays of locals.
- Test roots: Unit tests can call `gc_add_root`/`gc_remove_root` to pin values across collections.

During collection, the GC merges explicit roots with remembered-set derived minor roots.


## Write barriers and remembered set

A write barrier must run whenever an old-generation object gets a reference to a young-generation object. 
The VM calls `gc_record_write(old, new)` at mutation sites (e.g., cell element writes, struct field 
updates, object property updates). The barrier system stores card/slot metadata in `WriteBarrierManager` 
so that minor collections only scan a compact set of remembered locations rather than the entire old gen.


## Generational mark-and-sweep

Collections come in two flavors:

- Minor (young-only):
  1) Mark: From explicit roots and remembered-set entries (old→young), traverse and mark reachable young objects.
  2) Sweep: Iterate over young allocations; free unmarked, retain survivors.
  3) Promotion: Survivors are tracked and promoted to old generation based on survival counts.

- Major (all generations): Mark & sweep across all generations; clears remembered-set state.

## Promotion policy

The allocator tracks survivor counts and performs promotion once an object survives a configurable 
number of minor GCs. Promotion stats are reported via `GcStats` to tune policies.


## Configuration and statistics

`GcConfig` parameters:
- `young_generation_size`: target size for young generation (bytes)
- `minor_gc_threshold`: utilization ratio to trigger a minor GC
- Room for future knobs (promotion thresholds, card sizes, etc.)

`GcStats` counters:
- `total_allocations`, `minor_collections`, `major_collections`
- `objects_promoted`, `collections_performed`, `total_objects_collected`
- Other allocator/collector internal counters may be surfaced as needed


## Public API (selected)

- Allocation: `gc_allocate(value: Value) -> Result<GcPtr<Value>>`
- Collection: `gc_collect_minor()`, `gc_collect_major()`
- Roots: `gc_add_root(handle: GcPtr<Value>)`, `gc_remove_root(handle: GcPtr<Value>)`
- Configuration: `gc_configure(config: GcConfig)`, `gc_get_config()`
- Stats: `gc_stats() -> GcStats`
- Barrier: `gc_record_write(old: &Value, new: &Value)`

Example (pinning a value across collections):
```rust
use runmat_builtins::Value;
use runmat_gc::*;

let v = gc_allocate(Value::Num(42.0)).unwrap();
gc_add_root(v.clone()).unwrap();     // pin
let _ = gc_collect_minor().unwrap(); // safe; v is alive
assert_eq!(*v, Value::Num(42.0));
gc_remove_root(v).unwrap();          // unpin when done
```


## Safety model

- The only `unsafe` lives inside `GcPtr<T>` deref implementations. All external usage goes through 
  safe APIs.
- Non-moving allocation makes `GcPtr` addresses stable. The VM and runtime can store them without fear 
  of relocation.
- The interpreter is single-threaded with stop-the-world GCs; shared global state (`WriteBarrierManager`, 
  root registry) is synchronized and marked `Send/Sync` where appropriate.
- Barriers must be called at every mutation site that may introduce an old→young edge. The VM includes 
  barrier calls in:
  - Cell element writes
  - Struct field writes
  - Object property writes


## Testing

The repository includes a broad test suite:
- Allocator/collector unit tests: allocation, freeing, promotion, stats accuracy
- Stress tests: large allocation cycles, nested cells/structs, interpreter integration under load
- Rooting tests: explicit root add/remove; global/persistent lifetime; remembered-set scan correctness
- VM integration tests: N-D gather/scatter loops, cell/struct/object updates under barriered writes

All tests can be run single-threaded for deterministic behavior:
```bash
cargo test --workspace -- --test-threads=1
```


## Integration with the interpreter (VM)

- The VM uses `GcPtr<Value>` throughout aggregates (e.g., `CellArray` stores `Vec<GcPtr<Value>>`).
- All expansion and slice-assignment paths dereference `GcPtr` to read `Value` and write through handles 
  on mutation, with barrier calls at each write site.
- The VM runtime registers long-lived maps (globals/persistents) as roots for the duration of 
  execution.


## Current status

Implemented:
- Generational allocator with promotion accounting
- Mark-and-sweep collector over young/all generations
- Root scanner and explicit root API
- Write barriers and remembered set for old→young edges
- Stable handle type re-exported from `runmat-gc-api`
- Integration in the interpreter and runtime, with passing test suites


## Future work (optimizations and completeness)

The following items are not required for correctness today but are desirable for performance, 
observability, and long-run robustness:

- Barrier coverage audit and dedicated remembered-set test harness
- Promotion policy tuning and survival-count decay after promotion
- Extended telemetry: per-collection pause time, freed bytes, RS size, survivor/tenured histograms
- Optional compaction (semi-space for young, sliding compaction for old) to reduce fragmentation
- Fuzzing harness combining deep recursion, randomized allocation patterns, and mixed update/write paths
- API polish: consider `gc_add_root_ref(&GcPtr<Value>)` to reduce accidental moves in user code
- Configurable card sizes / RS structures for high-churn workloads


## Contributing

Contributions that improve performance, observability, or add new tests are welcome. Please keep changes 
focused and include benchmarks or tests where applicable.
