runmat_gc/
lib.rs

1//! RunMat High-Performance Generational Garbage Collector
2//!
3//! A production-quality, thread-safe generational garbage collector designed for
4//! high-performance interpreters. Features safe object management with handle-based
5//! access instead of raw pointers to avoid undefined behavior.
6
7use parking_lot::{Mutex, RwLock};
8// Use a local trait-alias shim to avoid compile-time dependency ordering issues.
9// Downstream crates in the workspace provide runmat_builtins; during GC unit tests, we provide a minimal Value.
10use runmat_builtins::Value;
11use std::collections::HashSet;
12use std::sync::atomic::{AtomicBool, Ordering};
13use std::sync::Arc;
14use std::time::Instant;
15use thiserror::Error;
16
17pub mod allocator;
18pub mod barriers;
19pub mod collector;
20pub mod config;
21pub mod gc_ptr;
22pub use runmat_gc_api::GcPtr;
23pub mod generations;
24pub mod roots;
25pub mod stats;
26
27// Finalizer support
28use std::collections::HashMap;
29
30/// A finalizer that runs when a GC-managed Value is collected.
31///
32/// Finalizers must be fast, non-panicking, and avoid allocating.
33pub trait GcFinalizer: Send + Sync {
34    fn finalize(&self);
35}
36
37static FINALIZERS: once_cell::sync::Lazy<
38    parking_lot::Mutex<HashMap<usize, std::sync::Arc<dyn GcFinalizer>>>,
39> = once_cell::sync::Lazy::new(|| parking_lot::Mutex::new(HashMap::new()));
40
41/// Register a finalizer for the provided GC pointer.
42pub fn gc_register_finalizer(ptr: GcPtr<Value>, f: std::sync::Arc<dyn GcFinalizer>) -> Result<()> {
43    let addr = unsafe { ptr.as_raw() } as usize;
44    if addr == 0 {
45        return Ok(());
46    }
47    FINALIZERS.lock().insert(addr, f);
48    Ok(())
49}
50
51/// Remove any registered finalizer for the provided GC pointer.
52pub fn gc_unregister_finalizer(ptr: GcPtr<Value>) -> Result<()> {
53    let addr = unsafe { ptr.as_raw() } as usize;
54    if addr == 0 {
55        return Ok(());
56    }
57    FINALIZERS.lock().remove(&addr);
58    Ok(())
59}
60
61/// Internal: run and remove finalizer for an address if present.
62pub(crate) fn gc_run_finalizer_for_addr(addr: usize) {
63    if let Some(f) = FINALIZERS.lock().remove(&addr) {
64        // Run finalizer; avoid panicking across GC boundaries
65        f.finalize();
66    }
67}
68
69#[cfg(feature = "pointer-compression")]
70pub mod compression;
71
72pub use allocator::{AllocatorStats, GenerationalAllocator, SizeClass};
73use barriers::WriteBarrierManager;
74pub use barriers::{CardTable, WriteBarrier};
75pub use collector::MarkSweepCollector;
76pub use config::{GcConfig, GcConfigBuilder};
77// Re-export unified handle from API crate
78pub use generations::{Generation, GenerationStats, GenerationalHeap, GenerationalHeapStats};
79pub use roots::{GcRoot, GlobalRoot, RootId, RootScanner, StackRoot, VariableArrayRoot};
80pub use stats::{CollectionEvent, CollectionType, GcStats};
81
82#[cfg(feature = "pointer-compression")]
83pub use compression::*;
84
85/// Errors that can occur during garbage collection
86#[derive(Error, Debug)]
87pub enum GcError {
88    #[error("Out of memory: {0}")]
89    OutOfMemory(String),
90
91    #[error("Invalid GC pointer: {0}")]
92    InvalidPointer(String),
93
94    #[error("Collection failed: {0}")]
95    CollectionFailed(String),
96
97    #[error("Root registration failed: {0}")]
98    RootRegistrationFailed(String),
99
100    #[error("Configuration error: {0}")]
101    ConfigError(String),
102
103    #[error("Thread synchronization error: {0}")]
104    SyncError(String),
105}
106
107pub type Result<T> = std::result::Result<T, GcError>;
108
109// Legacy handle/object table removed in favor of allocator-backed pointers and address-keyed maps
110
111/// High-performance garbage collector with safe handle-based design
112pub struct HighPerformanceGC {
113    /// Configuration
114    config: Arc<RwLock<GcConfig>>,
115
116    /// Generational allocator (owns heap memory)
117    allocator: Mutex<GenerationalAllocator>,
118
119    /// Mark-and-sweep collector
120    collector: Mutex<MarkSweepCollector>,
121
122    /// Explicit roots stored as raw addresses (address-keyed)
123    root_ptrs: Arc<Mutex<HashSet<usize>>>,
124
125    /// Collection state
126    collection_in_progress: AtomicBool,
127
128    /// Statistics
129    stats: Arc<GcStats>,
130}
131
132impl HighPerformanceGC {
133    pub fn new() -> Result<Self> {
134        Self::with_config(GcConfig::default())
135    }
136
137    pub fn with_config(config: GcConfig) -> Result<Self> {
138        let allocator = GenerationalAllocator::new(&config);
139        let collector = MarkSweepCollector::new(&config);
140
141        Ok(Self {
142            config: Arc::new(RwLock::new(config)),
143            allocator: Mutex::new(allocator),
144            collector: Mutex::new(collector),
145            root_ptrs: Arc::new(Mutex::new(HashSet::new())),
146            collection_in_progress: AtomicBool::new(false),
147            stats: Arc::new(GcStats::new()),
148        })
149    }
150
151    /// Allocate a new Value object
152    pub fn allocate(&self, value: Value) -> Result<GcPtr<Value>> {
153        // Check if collection is needed
154        if self.should_collect() {
155            let _ = self.collect_minor();
156        }
157
158        // Capture GPU handle if present to attach a finalizer after allocation
159        let gpu_handle: Option<runmat_accelerate_api::GpuTensorHandle> =
160            if let Value::GpuTensor(h) = &value {
161                Some(h.clone())
162            } else {
163                None
164            };
165
166        let mut allocator = self.allocator.lock();
167        let ptr = allocator.allocate(value, &self.stats)?;
168        let usage = allocator.young_generation_usage();
169        let alloc_count = allocator.young_allocations_count();
170        let cfg = self.config.read().clone();
171        drop(allocator);
172
173        // Register finalizer for GPU tensors so buffers are freed on collection
174        if let Some(handle) = gpu_handle {
175            struct GpuTensorFinalizer {
176                handle: runmat_accelerate_api::GpuTensorHandle,
177            }
178            impl GcFinalizer for GpuTensorFinalizer {
179                fn finalize(&self) {
180                    if let Some(p) = runmat_accelerate_api::provider() {
181                        let _ = p.free(&self.handle);
182                        runmat_accelerate_api::clear_handle_logical(&self.handle);
183                    }
184                }
185            }
186            let fin = std::sync::Arc::new(GpuTensorFinalizer { handle });
187            let _ = gc_register_finalizer(ptr.clone(), fin);
188        }
189
190        // Heuristic triggers:
191        // - Utilization threshold
192        // - Aggressive mode: periodic minor GC by allocation count to satisfy stress configs
193        if usage > cfg.minor_gc_threshold
194            || (cfg.minor_gc_threshold <= 0.35 && alloc_count > 0 && alloc_count.is_multiple_of(32))
195        {
196            let _ = self.collect_minor();
197        }
198        Ok(ptr)
199    }
200
201    // get_value by handle removed in favor of direct GcPtr usage
202
203    /// Check if collection should be triggered
204    fn should_collect(&self) -> bool {
205        if self.collection_in_progress.load(Ordering::Acquire) {
206            return false;
207        }
208
209        let threshold = self.config.read().minor_gc_threshold;
210        let allocator = self.allocator.lock();
211        let utilization = allocator.young_generation_usage();
212        utilization > threshold
213    }
214
215    /// Perform minor collection (young generation)
216    pub fn collect_minor(&self) -> Result<usize> {
217        if self
218            .collection_in_progress
219            .compare_exchange(false, true, Ordering::AcqRel, Ordering::Relaxed)
220            .is_err()
221        {
222            return Ok(0);
223        }
224
225        let start_time = Instant::now();
226
227        // Build combined roots: explicit + external (root scanner + barriers)
228        let mut combined_roots: Vec<GcPtr<Value>> = Vec::new();
229        {
230            let roots = self.root_ptrs.lock();
231            combined_roots.extend(
232                roots
233                    .iter()
234                    .map(|&addr| unsafe { GcPtr::from_raw(addr as *const Value) }),
235            );
236        }
237        // External roots
238        if let Ok(mut ext) = ROOT_SCANNER.scan_roots() {
239            combined_roots.append(&mut ext);
240        }
241        combined_roots.extend(gc_barrier_minor_roots());
242
243        // Collect young generation via unified collector/allocator
244        let mut allocator = self.allocator.lock();
245        let mut collector = self.collector.lock();
246        let collected_count =
247            collector.collect_young_generation(&mut allocator, &combined_roots, &self.stats)?;
248
249        // Clear dirty cards; keep remembered set for next minor cycle
250        WRITE_BARRIERS.clear_after_minor_gc();
251
252        let duration = start_time.elapsed();
253        self.stats
254            .record_minor_collection(collected_count, duration);
255
256        self.collection_in_progress.store(false, Ordering::Release);
257
258        log::info!("Minor GC: collected {collected_count} objects in {duration:?}");
259
260        Ok(collected_count)
261    }
262
263    // /// Get object by handle
264    // Address-keyed design: object table lookup removed
265
266    // /// Mark objects transitively (follow references)
267    // Transitive marking handled by collector over allocator-backed objects
268
269    // /// Find the GcObject that contains a specific Value
270    // Value-equality scans removed in favor of address-keyed marking
271
272    /// Perform major collection (all generations)
273    pub fn collect_major(&self) -> Result<usize> {
274        if self
275            .collection_in_progress
276            .compare_exchange(false, true, Ordering::AcqRel, Ordering::Relaxed)
277            .is_err()
278        {
279            return Ok(0);
280        }
281
282        let start_time = Instant::now();
283
284        // Build combined roots: explicit + external
285        let mut combined_roots: Vec<GcPtr<Value>> = Vec::new();
286        {
287            let roots = self.root_ptrs.lock();
288            combined_roots.extend(
289                roots
290                    .iter()
291                    .map(|&addr| unsafe { GcPtr::from_raw(addr as *const Value) }),
292            );
293        }
294        if let Ok(mut ext) = ROOT_SCANNER.scan_roots() {
295            combined_roots.append(&mut ext);
296        }
297        combined_roots.extend(gc_barrier_minor_roots());
298
299        let mut allocator = self.allocator.lock();
300        let mut collector = self.collector.lock();
301        let collected_count =
302            collector.collect_all_generations(&mut allocator, &combined_roots, &self.stats)?;
303
304        // Clear all barriers after major GC
305        WRITE_BARRIERS.clear_after_major_gc();
306        allocator.clear_promotion_state();
307
308        let duration = start_time.elapsed();
309        self.stats
310            .record_major_collection(collected_count, duration);
311
312        self.collection_in_progress.store(false, Ordering::Release);
313
314        log::info!("Major GC: collected {collected_count} objects in {duration:?}");
315
316        Ok(collected_count)
317    }
318
319    /// Add a root to protect an object from collection
320    pub fn add_root(&self, root: GcPtr<Value>) -> Result<()> {
321        let value_ptr = unsafe { root.as_raw() } as usize;
322        if value_ptr == 0 {
323            return Ok(());
324        }
325        self.root_ptrs.lock().insert(value_ptr);
326        Ok(())
327    }
328
329    /// Remove a root
330    pub fn remove_root(&self, root: GcPtr<Value>) -> Result<()> {
331        let value_ptr = unsafe { root.as_raw() } as usize;
332        if value_ptr == 0 {
333            return Ok(());
334        }
335        self.root_ptrs.lock().remove(&value_ptr);
336        Ok(())
337    }
338
339    // /// Find the handle for an object that contains the given value pointer
340    // Address-keyed roots: no handle lookup needed
341    /// Get GC statistics
342    pub fn stats(&self) -> GcStats {
343        self.stats.as_ref().clone()
344    }
345
346    /// Configure the GC
347    pub fn configure(&self, config: GcConfig) -> Result<()> {
348        *self.config.write() = config.clone();
349        {
350            // Rebuild allocator to support changes like num_generations and sizes
351            let mut allocator = self.allocator.lock();
352            *allocator = GenerationalAllocator::new(&config);
353        }
354        {
355            let mut collector = self.collector.lock();
356            collector.reconfigure(&config)?;
357        }
358        Ok(())
359    }
360
361    /// Get the current GC configuration
362    pub fn get_config(&self) -> GcConfig {
363        self.config.read().clone()
364    }
365}
366
367// Safety: All shared data is protected by proper synchronization
368unsafe impl Send for HighPerformanceGC {}
369unsafe impl Sync for HighPerformanceGC {}
370
371/// Global garbage collector instance
372static GC: once_cell::sync::Lazy<Arc<HighPerformanceGC>> =
373    once_cell::sync::Lazy::new(|| Arc::new(HighPerformanceGC::new().expect("Failed to create GC")));
374static ROOT_SCANNER: once_cell::sync::Lazy<Arc<RootScanner>> =
375    once_cell::sync::Lazy::new(|| Arc::new(RootScanner::new()));
376
377/// Global write barrier manager
378static WRITE_BARRIERS: once_cell::sync::Lazy<Arc<WriteBarrierManager>> =
379    once_cell::sync::Lazy::new(|| Arc::new(WriteBarrierManager::new(true, false)));
380
381/// Helper function to dereference a GcPtr safely (now just uses normal dereferencing)
382pub fn gc_deref(ptr: GcPtr<Value>) -> Value {
383    (*ptr).clone()
384}
385
386/// Global GC functions for easy access
387pub fn gc_allocate(value: Value) -> Result<GcPtr<Value>> {
388    GC.allocate(value)
389}
390
391pub fn gc_collect_minor() -> Result<usize> {
392    // Stage external roots inside GC and perform unified minor collection
393    GC.collect_minor()
394}
395
396pub fn gc_collect_major() -> Result<usize> {
397    GC.collect_major()
398}
399
400pub fn gc_add_root(root: GcPtr<Value>) -> Result<()> {
401    GC.add_root(root)
402}
403
404pub fn gc_remove_root(root: GcPtr<Value>) -> Result<()> {
405    GC.remove_root(root)
406}
407
408pub fn gc_stats() -> GcStats {
409    GC.stats()
410}
411
412pub fn gc_configure(config: GcConfig) -> Result<()> {
413    GC.configure(config)
414}
415
416pub fn gc_get_config() -> GcConfig {
417    GC.get_config()
418}
419
420/// Simplified root registration for backwards compatibility
421pub fn gc_register_root(root: Box<dyn GcRoot>) -> Result<RootId> {
422    ROOT_SCANNER.register_root(root)
423}
424
425pub fn gc_unregister_root(root_id: RootId) -> Result<()> {
426    ROOT_SCANNER.unregister_root(root_id)
427}
428
429/// Record a write for GC barriers (approximate old->young tracking)
430pub fn gc_record_write(old: &Value, new: &Value) {
431    // Generation-aware barrier: record only if old is logically old and new is young
432    let old_ptr = old as *const Value as *const u8;
433    let young_ptr = new as *const Value as *const u8;
434    // Query allocator logical generations
435    let alloc = GC.allocator.lock();
436    let old_gen = alloc.logical_generation(old_ptr).unwrap_or(0);
437    let new_gen = alloc.logical_generation(young_ptr).unwrap_or(0);
438    drop(alloc);
439    if old_gen > new_gen {
440        WRITE_BARRIERS.record_reference(old_ptr, young_ptr);
441    }
442}
443
444/// Get barrier-derived roots for minor GC
445pub fn gc_barrier_minor_roots() -> Vec<GcPtr<Value>> {
446    WRITE_BARRIERS
447        .get_minor_gc_roots()
448        .into_iter()
449        .map(|p| unsafe { GcPtr::from_raw(p as *const Value) })
450        .collect()
451}
452
453/// Force a garbage collection for testing/debugging
454#[cfg(any(test, feature = "debug-gc"))]
455pub fn gc_force_collect() -> Result<usize> {
456    gc_collect_major()
457}
458
459/// Reset GC for testing - always available
460pub fn gc_reset_for_test() -> Result<()> {
461    // Reset statistics
462    GC.stats.reset();
463
464    // Reset allocator/collector and roots
465    {
466        let config = GcConfig::default();
467        *GC.config.write() = config.clone();
468        let mut alloc = GC.allocator.lock();
469        *alloc = GenerationalAllocator::new(&config);
470        let mut coll = GC.collector.lock();
471        *coll = MarkSweepCollector::new(&config);
472    }
473
474    {
475        let mut roots = GC.root_ptrs.lock();
476        roots.clear();
477    }
478
479    // Ensure collection is not in progress
480    GC.collection_in_progress.store(false, Ordering::Relaxed);
481
482    // Configure with default settings
483    gc_configure(GcConfig::default())?;
484
485    Ok(())
486}
487
488/// Create an isolated test context with clean GC state
489pub fn gc_test_context<F, R>(test_fn: F) -> R
490where
491    F: FnOnce() -> R,
492{
493    // Use a global test mutex to ensure tests run sequentially when needed
494    static TEST_MUTEX: std::sync::Mutex<()> = std::sync::Mutex::new(());
495
496    // Handle poisoned mutex gracefully
497    let _guard = match TEST_MUTEX.lock() {
498        Ok(guard) => guard,
499        Err(poisoned) => {
500            // Clear the poison and continue
501            poisoned.into_inner()
502        }
503    };
504
505    // Reset GC to clean state
506    gc_reset_for_test().expect("GC reset should succeed");
507
508    // Run the test
509    let result = test_fn();
510
511    // Clean up after test (optional, but good practice)
512    let _ = gc_reset_for_test();
513
514    result
515}
516
517#[cfg(test)]
518mod tests {
519    use super::*;
520
521    #[test]
522    fn test_basic_allocation() {
523        gc_test_context(|| {
524            let value = Value::Num(42.0);
525            let ptr = gc_allocate(value).expect("allocation failed");
526            assert_eq!(*ptr, Value::Num(42.0));
527        });
528    }
529
530    #[test]
531    fn test_collection() {
532        gc_test_context(|| {
533            let mut _ptrs = Vec::new();
534            for i in 0..100 {
535                let ptr = gc_allocate(Value::Num(i as f64)).expect("allocation failed");
536                _ptrs.push(ptr);
537            }
538
539            let _collected = gc_collect_minor().expect("collection failed");
540            drop(_ptrs);
541        });
542    }
543
544    #[test]
545    fn test_thread_safety() {
546        use std::thread;
547
548        gc_test_context(|| {
549            let handles: Vec<_> = (0..4)
550                .map(|i| {
551                    thread::spawn(move || {
552                        let mut ptrs = Vec::new();
553                        for j in 0..100 {
554                            let value = Value::Num((i * 100 + j) as f64);
555                            let ptr = gc_allocate(value).expect("allocation failed");
556                            ptrs.push(ptr);
557                        }
558                        ptrs
559                    })
560                })
561                .collect();
562
563            for handle in handles {
564                let _ptrs = handle.join().expect("thread failed");
565            }
566
567            let _ = gc_collect_major();
568        });
569    }
570
571    #[test]
572    fn test_root_protection() {
573        gc_test_context(|| {
574            let protected = gc_allocate(Value::Num(42.0)).expect("allocation failed");
575            gc_add_root(protected.clone()).expect("root registration failed");
576
577            for i in 0..60 {
578                let _ = gc_allocate(Value::String(format!("garbage_{i}")));
579            }
580
581            let _ = gc_collect_minor().expect("collection failed");
582            assert_eq!(*protected, Value::Num(42.0));
583
584            gc_remove_root(protected).expect("root removal failed");
585        });
586    }
587
588    #[test]
589    fn test_gc_allocation_and_roots() {
590        gc_test_context(|| {
591            let v = gc_allocate(Value::Num(7.0)).expect("allocation failed");
592            assert_eq!(*v, Value::Num(7.0));
593
594            gc_add_root(v.clone()).expect("root add failed");
595            let _ = gc_collect_minor().expect("collection failed");
596            assert_eq!(*v, Value::Num(7.0));
597
598            gc_remove_root(v).expect("root remove failed");
599        });
600    }
601}
runmat_gc/lib.rs

runmat_gc/
lib.rs
