use crate::set_data_ptr; use crate::trace::Trace; use std::alloc::{alloc, dealloc, Layout}; use std::cell::{Cell, RefCell}; use std::mem; use std::ptr::{self, NonNull}; #[cfg(feature = "nightly")] use std::marker::Unsize; struct GcState { stats: GcStats, config: GcConfig, boxes_start: Option>>, } impl Drop for GcState { fn drop(&mut self) { if !self.config.leak_on_drop { collect_garbage(self); } // We have no choice but to leak any remaining nodes that // might be referenced from other thread-local variables. } } // Whether or not the thread is currently in the sweep phase of garbage collection. // During this phase, attempts to dereference a `Gc` pointer will trigger a panic. thread_local!(pub static GC_DROPPING: Cell = const { Cell::new(false) }); struct DropGuard; impl DropGuard { fn new() -> DropGuard { GC_DROPPING.with(|dropping| dropping.set(true)); DropGuard } } impl Drop for DropGuard { fn drop(&mut self) { GC_DROPPING.with(|dropping| dropping.set(false)); } } #[must_use] pub fn finalizer_safe() -> bool { GC_DROPPING.with(|dropping| !dropping.get()) } // The garbage collector's internal state. thread_local!(static GC_STATE: RefCell = RefCell::new(GcState { stats: GcStats::default(), config: GcConfig::default(), boxes_start: None, })); const MARK_MASK: usize = 1 << (usize::BITS - 1); const ROOTS_MASK: usize = !MARK_MASK; const ROOTS_MAX: usize = ROOTS_MASK; // max allowed value of roots pub(crate) struct GcBoxHeader { roots: Cell, // high bit is used as mark flag next: Cell>>>, // mentat: this box as a `dyn Trace` box pointer, set in `insert_gcbox`, so // marking can queue a box without knowing its concrete type. this: Cell>>>, } impl GcBoxHeader { #[inline] pub fn new() -> Self { GcBoxHeader { roots: Cell::new(1), // unmarked and roots count = 1 next: Cell::new(None), this: Cell::new(None), } } #[inline] pub fn roots(&self) -> usize { self.roots.get() & ROOTS_MASK } #[inline] pub fn inc_roots(&self) { let roots = self.roots.get(); // abort if the count overflows to prevent `mem::forget` loops // that could otherwise lead to erroneous drops if (roots & ROOTS_MASK) < ROOTS_MAX { self.roots.set(roots + 1); // we checked that this wont affect the high bit } else { panic!("roots counter overflow"); } } #[inline] pub fn dec_roots(&self) { self.roots.set(self.roots.get() - 1); // no underflow check } #[inline] pub fn is_marked(&self) -> bool { self.roots.get() & MARK_MASK != 0 } #[inline] pub fn mark(&self) { self.roots.set(self.roots.get() | MARK_MASK); } #[inline] pub fn unmark(&self) { self.roots.set(self.roots.get() & !MARK_MASK); } } #[repr(C)] // to justify the layout computations in GcBox::from_box, Gc::from_raw pub(crate) struct GcBox { header: GcBoxHeader, data: T, } impl GcBox { /// Allocates a garbage collected `GcBox` on the heap, /// and appends it to the thread-local `GcBox` chain. This might /// trigger a collection. /// /// A `GcBox` allocated this way starts its life rooted. pub(crate) fn new(value: T) -> NonNull { let gcbox = NonNull::from(Box::leak(Box::new(GcBox { header: GcBoxHeader::new(), data: value, }))); unsafe { insert_gcbox(gcbox) }; gcbox } } impl< #[cfg(not(feature = "nightly"))] T: Trace, #[cfg(feature = "nightly")] T: Trace + Unsize + ?Sized, > GcBox { /// Consumes a `Box`, moving the value inside into a new `GcBox` /// on the heap. Adds the new `GcBox` to the thread-local `GcBox` /// chain. This might trigger a collection. /// /// A `GcBox` allocated this way starts its life rooted. pub(crate) fn from_box(value: Box) -> NonNull { let header_layout = Layout::new::(); let value_layout = Layout::for_value::(&*value); // This relies on GcBox being #[repr(C)]. let gcbox_layout = header_layout.extend(value_layout).unwrap().0.pad_to_align(); unsafe { // Allocate the GcBox in a way that's compatible with Box, // since the collector will deallocate it via // Box::from_raw. let gcbox_addr = alloc(gcbox_layout); // Since we're not allowed to move the value out of an // active Box, and we will need to deallocate the Box // without calling the destructor, convert it to a raw // pointer first. let value = Box::into_raw(value); // Create a pointer with the metadata of value and the // address and provenance of the GcBox. let gcbox = set_data_ptr(value as *mut GcBox, gcbox_addr); // Move the data. ptr::addr_of_mut!((*gcbox).header).write(GcBoxHeader::new()); ptr::addr_of_mut!((*gcbox).data) .cast::() .copy_from_nonoverlapping(value.cast::(), value_layout.size()); // Deallocate the former Box. (Box only allocates for size // != 0.) if value_layout.size() != 0 { dealloc(value.cast::(), value_layout); } // Add the new GcBox to the chain and return it. let gcbox = NonNull::new_unchecked(gcbox); insert_gcbox(gcbox); gcbox } } } /// Add a new `GcBox` to the current thread's `GcBox` chain. This /// might trigger a collection first if enough bytes have been /// allocated since the previous collection. /// /// # Safety /// /// `gcbox` must point to a valid `GcBox` that is not yet in a `GcBox` /// chain. unsafe fn insert_gcbox(gcbox: NonNull>) { GC_STATE.with(|st| { let mut st = st.borrow_mut(); // XXX We should probably be more clever about collecting if st.stats.bytes_allocated > st.config.threshold { collect_garbage(&mut st); if st.stats.bytes_allocated as f64 > st.config.threshold as f64 * st.config.used_space_ratio { // we didn't collect enough, so increase the // threshold for next time, to avoid thrashing the // collector too much/behaving quadratically. st.config.threshold = (st.stats.bytes_allocated as f64 / st.config.used_space_ratio) as usize; } } let next = st.boxes_start.replace(gcbox); gcbox.as_ref().header.next.set(next); gcbox.as_ref().header.this.set(Some(gcbox)); // We allocated some bytes! Let's record it st.stats.bytes_allocated += mem::size_of_val::>(gcbox.as_ref()); }); } impl GcBox { /// Returns `true` if the two references refer to the same `GcBox`. pub(crate) fn ptr_eq(this: &GcBox, other: &GcBox) -> bool { // Use .header to ignore fat pointer vtables, to work around // https://github.com/rust-lang/rust/issues/46139 ptr::eq(&this.header, &other.header) } } // mentat modification (see ../../CHANGES.md): iterative marking. // // Upstream marks recursively: `trace_inner` marks a box, then traces its data, // which calls `trace_inner` on every child `Gc`. Marking a chain of N boxes // therefore used N nested Rust frames, and a long list or deeply nested // structure overflowed the stack during a collection (in a debug build, a list // of ~6,000 cons cells on a 2 MB stack). // // Now, while a mark pass is running, `trace_inner` only marks the box and // pushes it on `MARK_STACK`; `mark_from` traces the pushed boxes one at a time // in a loop. The recursion depth of a collection is bounded by the nesting // *within a single box's data* (a Vec of Gcs traced in one call), not by the // length of the object graph. Outside a mark pass (a `Trace` impl called // directly) the old recursive behaviour is kept. thread_local! { // Boxes marked but not yet traced. `None` outside a mark pass. static MARK_STACK: RefCell>>>> = const { RefCell::new(None) }; } /// Trace everything reachable from the box at `root` without recursing on the /// Rust stack once per `Gc` edge. unsafe fn mark_from(root: NonNull>) { if root.as_ref().header.is_marked() { return; } root.as_ref().header.mark(); MARK_STACK.with(|s| *s.borrow_mut() = Some(Vec::new())); let mut next = Some(root); while let Some(node) = next { // Tracing the data calls `trace_inner` on each child `Gc`, which // (because MARK_STACK is Some) marks and queues it instead of // recursing. node.as_ref().data.trace(); next = MARK_STACK.with(|s| s.borrow_mut().as_mut().and_then(Vec::pop)); } MARK_STACK.with(|s| *s.borrow_mut() = None); } impl GcBox { /// Marks this `GcBox` and marks through its data. pub(crate) unsafe fn trace_inner(&self) { if self.header.is_marked() { return; } self.header.mark(); // During a mark pass, queue this box (by the `dyn Trace` pointer to // itself that every box in the chain records in its header) instead of // tracing into it here. Outside a pass, trace directly as upstream did. let queued = MARK_STACK.with( |s| match (s.borrow_mut().as_mut(), self.header.this.get()) { (Some(stack), Some(this)) => { stack.push(this); true } _ => false, }, ); if !queued { self.data.trace(); } } } impl GcBox { /// Increases the root count on this `GcBox`. /// Roots prevent the `GcBox` from being destroyed by the garbage collector. pub(crate) unsafe fn root_inner(&self) { self.header.inc_roots(); } /// Decreases the root count on this `GcBox`. /// Roots prevent the `GcBox` from being destroyed by the garbage collector. pub(crate) unsafe fn unroot_inner(&self) { self.header.dec_roots(); } /// Returns a pointer to the `GcBox`'s value, without dereferencing it. pub(crate) fn value_ptr(this: *const GcBox) -> *const T { unsafe { ptr::addr_of!((*this).data) } } /// Returns a reference to the `GcBox`'s value. pub(crate) fn value(&self) -> &T { &self.data } } /// Collects garbage. fn collect_garbage(st: &mut GcState) { struct Unmarked<'a> { incoming: &'a Cell>>>, this: NonNull>, } unsafe fn mark(head: &Cell>>>) -> Vec> { // Walk the tree, tracing and marking the nodes let mut mark_head = head.get(); while let Some(node) = mark_head { if node.as_ref().header.roots() > 0 { mark_from(node); } mark_head = node.as_ref().header.next.get(); } // Collect a vector of all of the nodes which were not marked, // and unmark the ones which were. let mut unmarked = Vec::new(); let mut unmark_head = head; while let Some(node) = unmark_head.get() { if node.as_ref().header.is_marked() { node.as_ref().header.unmark(); } else { unmarked.push(Unmarked { incoming: unmark_head, this: node, }); } unmark_head = &node.as_ref().header.next; } unmarked } unsafe fn sweep(finalized: Vec>, bytes_allocated: &mut usize) { let _guard = DropGuard::new(); for node in finalized.into_iter().rev() { if node.this.as_ref().header.is_marked() { continue; } let incoming = node.incoming; let node = Box::from_raw(node.this.as_ptr()); *bytes_allocated -= mem::size_of_val::>(&*node); incoming.set(node.header.next.take()); } } st.stats.collections_performed += 1; unsafe { let head = Cell::from_mut(&mut st.boxes_start); let unmarked = mark(head); if unmarked.is_empty() { return; } for node in &unmarked { Trace::finalize_glue(&node.this.as_ref().data); } mark(head); sweep(unmarked, &mut st.stats.bytes_allocated); } } /// Immediately triggers a garbage collection on the current thread. /// /// This will panic if executed while a collection is currently in progress pub fn force_collect() { GC_STATE.with(|st| { let mut st = st.borrow_mut(); collect_garbage(&mut st); }); } pub struct GcConfig { pub threshold: usize, /// after collection we want the the ratio of used/total to be no /// greater than this (the threshold grows exponentially, to avoid /// quadratic behavior when the heap is growing linearly with the /// number of `new` calls): pub used_space_ratio: f64, /// For short-running processes it is not always appropriate to run /// GC, sometimes it is better to let system free the resources pub leak_on_drop: bool, } impl Default for GcConfig { fn default() -> Self { Self { used_space_ratio: 0.7, threshold: 100, leak_on_drop: false, } } } #[allow(dead_code)] pub fn configure(configurer: impl FnOnce(&mut GcConfig)) { GC_STATE.with(|st| { let mut st = st.borrow_mut(); configurer(&mut st.config); }); } #[derive(Clone, Default)] pub struct GcStats { pub bytes_allocated: usize, pub collections_performed: usize, } #[allow(dead_code)] #[must_use] pub fn stats() -> GcStats { GC_STATE.with(|st| st.borrow().stats.clone()) }