Karan's Notes

gc-rust

4 min read

https://manishearth.github.io/blog/2015/09/01/designing-a-gc-in-rust/ https://github.com/Manishearth/rust-gc/

lxr: https://arxiv.org/pdf/2210.17175

other implementation:

https://github.com/fitzgen/bacon-rajan-cc

https://github.com/asajeffrey/josephine/

https://github.com/withoutboats/shifgrethor

https://gist.github.com/Manishearth/70856e2f01e18935681c

they forked the thing:

https://soft-dev.org/pubs/html/hughes_tratt__garbage_collection_for_rust_the_finalizer_frontier/

GC-fuzz: Build it as a testing harness crate, not as a GC crate. That keeps scope sane and makes the “Antithesis in spirit” part explicit: perturb, assert, replay, shrink.

Shape Call it something like gc-fuzz, gc-schedule, or gc-check.

Split it into four pieces:

  1. event Defines the observable moments in a collector or mutator:

    pub enum GcEvent { Alloc { bytes: usize, object_id: u64 }, RootAdded { root_id: u64 }, RootRemoved { root_id: u64 }, WriteBarrier { from: u64, to: u64 }, Safepoint, CollectionStart, CollectionEnd, }

  2. schedule Decides what perturbation to apply:

    pub enum Decision { Noop, CollectNow, VerifyHeap, PoisonFreed, }

    pub trait Schedule { fn on_event(&mut self, event: &GcEvent) → Decision; }

  3. recorder Logs decisions so failures are reproducible:

    pub struct TraceStep { pub event_index: u64, pub event: GcEvent, pub decision: Decision, }

    pub trait Recorder { fn record(&mut self, step: &TraceStep); }

  4. oracle Verifies invariants:

    pub trait HeapOracle { type Error;

    fn verify_pre_gc(&self) -> Result<(), Self::Error>;
fn verify_post_gc(&self) -> Result<(), Self::Error>;

    }

Minimal API Your collector integrates at safepoints:

pub trait HarnessHost { type Error;

  fn collect_now(&mut self) -> Result<(), Self::Error>;
  fn verify_heap(&mut self) -> Result<(), Self::Error>;
  fn poison_freed(&mut self) -> Result<(), Self::Error>;

}

Then the harness itself is just:

pub struct Harness<S, R> { schedule: S, recorder: R, event_index: u64, }

impl<S: Schedule, R: Recorder> Harness<S, R> { pub fn on_event<H: HarnessHost>( &mut self, host: &mut H, event: GcEvent, ) → Result<(), H::Error> { let decision = self.schedule.on_event(&event); self.recorder.record(&TraceStep { event_index: self.event_index, event, decision, }); self.event_index += 1;

      match decision {
          Decision::Noop => Ok(()),
          Decision::CollectNow => host.collect_now(),
          Decision::VerifyHeap => host.verify_heap(),
          Decision::PoisonFreed => host.poison_freed(),
      }
  }

}

That is the right abstraction boundary. The harness decides when to perturb. The GC still owns how collection works.

First three scheduler modes These are enough for v1:

  • Stress Trigger CollectNow on every alloc and safepoint.
  • Seeded Deterministic PRNG, decisions derived from seed plus event count.
  • Replay Read a previously recorded TraceStep sequence and emit exactly the same decisions.

Do not start with “adaptive”. That is a production policy problem, not a testing tool problem.

The feature that actually matters Add a trace shrinker. Given a failing replay trace, minimize it.

Representation:

pub struct DecisionTrace(pub Vec);

pub struct DecisionPoint { pub event_index: u64, pub decision: Decision, }

Shrinking strategy:

  1. Remove half the decision points, replay.
  2. If still fails, keep the smaller half.
  3. If not, restore and try smaller chunks.
  4. Once coarse minimization finishes, try dropping single points.
  5. Report the minimal failing schedule.

This is just delta debugging, boring in the good way. That is the part that feels most “Antithesis”.

What properties to check For a non-moving mark/sweep collector, start with these:

  • Every root points to a live object after collection.
  • Every reachable object remains allocated after collection.
  • No edge points to freed memory.
  • Running GC twice with no mutation yields the same live set.
  • Freed objects are not reachable from any root.
  • Finalizers run at most once.

For a moving collector, add later:

  • Every forwarded pointer resolves to a valid to-space object.
  • No stale from-space pointer survives in roots or fields.
  • Barrier invariants hold before and after each phase.

How to test the harness Do not mock the world into nonsense. Build a tiny real heap model:

  • object arena as Vec
  • object fields as Vec
  • real root set
  • simple mark/sweep implementation
  • intentionally buggy variants behind test cfg

Then write end-to-end tests:

  1. stress_finds_missing_root_bug Simulate a root registration bug that only fails if collection lands between alloc and root_add.
  2. seed_reproduces_failure Save failing seed, rerun, assert same failure.
  3. replay_reproduces_failure Record a trace, replay it, assert identical failure.
  4. shrink_reduces_trace Start from a long failing trace, shrink it, assert the smaller one still fails.

That gives you real proof, not brochureware.

Two-week plan Week 1:

  1. Implement GcEvent, Decision, Schedule, Recorder, HarnessHost.
  2. Add Stress, Seeded, and in-memory Recorder.
  3. Build the tiny reference mark/sweep heap.
  4. Write one intentionally buggy scenario and make Stress catch it.

Week 2:

  1. Add Replay.
  2. Add trace serialization with serde if you want CLI ergonomics.
  3. Implement delta-debug style shrinking.
  4. Write one post: “A failing GC schedule, recorded and minimized”.

What not to do

  • Do not start with concurrent GC.
  • Do not start with a brand new algorithm.
  • Do not start by integrating five runtimes.
  • Do not oversell “determinism” if allocator layout and threads are still nondeterministic.

Best framing Pitch it like this:

“A property-driven GC testing harness for Rust collectors. It forces collections at hostile times, records the schedule, replays failures exactly, and shrinks failing schedules to minimal repros.”

Graph View