use std::cell::{Cell, RefCell};
use std::mem;
use std::ptr::Shared;
use trace::Trace;
const INITIAL_THRESHOLD: usize = 100;
// 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):
const USED_SPACE_RATIO: f64 = 0.7;
struct GcState {
bytes_allocated: usize,
threshold: usize,
boxes_start: Option<Shared<GcBox<Trace>>>,
}
impl Drop for GcState {
fn drop(&mut self) {
unsafe {
GC_SWEEPING.with(|collecting| collecting.set(true));
while let Some(node) = self.boxes_start {
let node = Box::from_raw(*node);
self.boxes_start = node.header.next;
}
}
}
}
/// Whether or not the thread is currently in the sweep phase of garbage collection.
/// During this phase, attempts to dereference a `Gc<T>` pointer will trigger a panic.
thread_local!(pub static GC_SWEEPING: Cell<bool> = Cell::new(false));
/// The garbage collector's internal state.
thread_local!(static GC_STATE: RefCell<GcState> = RefCell::new(GcState {
bytes_allocated: 0,
threshold: INITIAL_THRESHOLD,
boxes_start: None,
}));
pub struct GcBoxHeader {
// XXX This is horribly space inefficient - not sure if we care
// We are using a word word bool - there is a full 63 bits of unused data :(
roots: Cell<usize>,
next: Option<Shared<GcBox<Trace>>>,
marked: Cell<bool>,
}
pub struct GcBox<T: Trace + ?Sized + 'static> {
header: GcBoxHeader,
data: T,
}
impl<T: Trace> GcBox<T> {
/// Allocates a garbage collected `GcBox` on the heap,
/// and appends it to the thread-local `GcBox` chain.
///
/// A `GcBox` allocated this way starts its life rooted.
pub fn new(value: T) -> Shared<Self> {
GC_STATE.with(|st| {
let mut st = st.borrow_mut();
// XXX We should probably be more clever about collecting
if st.bytes_allocated > st.threshold {
collect_garbage(&mut *st);
if st.bytes_allocated as f64 > st.threshold as f64 * 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.threshold = (st.bytes_allocated as f64 / USED_SPACE_RATIO) as usize
}
}
let gcbox = unsafe {
Shared::new(Box::into_raw(Box::new(GcBox {
header: GcBoxHeader {
roots: Cell::new(1),
marked: Cell::new(false),
next: st.boxes_start.take(),
},
data: value,
})))
};
st.boxes_start = Some(gcbox);
// We allocated some bytes! Let's record it
st.bytes_allocated += mem::size_of::<GcBox<T>>();
// Return the pointer to the newly allocated data
gcbox
})
}
}
impl<T: Trace + ?Sized> GcBox<T> {
/// Marks this `GcBox` and traces through its data.
pub unsafe fn trace_inner(&self) {
let marked = self.header.marked.get();
if !marked {
self.header.marked.set(true);
self.data.trace();
}
}
/// Increases the root count on this `GcBox`.
/// Roots prevent the `GcBox` from being destroyed by the garbage collector.
pub unsafe fn root_inner(&self) {
// abort if the count overflows to prevent `mem::forget` loops that could otherwise lead to
// erroneous drops
self.header.roots.set(self.header.roots.get()
.checked_add(1).unwrap_or_else(|| ::std::intrinsics::abort()));
}
/// Decreases the root count on this `GcBox`.
/// Roots prevent the `GcBox` from being destroyed by the garbage collector.
pub unsafe fn unroot_inner(&self) {
self.header.roots.set(self.header.roots.get() - 1);
}
/// Returns a reference to the `GcBox`'s value.
pub fn value(&self) -> &T {
&self.data
}
fn size_of(&self) -> usize { mem::size_of_val(self) }
}
/// Collects garbage.
fn collect_garbage(st: &mut GcState) {
unsafe fn mark(mut head: Option<Shared<GcBox<Trace>>>) {
while let Some(node) = head {
if (**node).header.roots.get() > 0 {
(**node).trace_inner();
}
head = (**node).header.next;
}
}
unsafe fn sweep(mut head: &mut Option<Shared<GcBox<Trace>>>, bytes_allocated: &mut usize) {
GC_SWEEPING.with(|collecting| collecting.set(true));
while let Some(node) = *head {
if (**node).header.marked.get() {
// This node has already been marked - we're done!
(**node).header.marked.set(false);
head = &mut (**node).header.next;
} else {
// The node wasn't marked - we need to delete it
let mut node = Box::from_raw(*node);
*bytes_allocated -= node.size_of();
*head = node.header.next.take();
}
}
// XXX This should probably be done with some kind of finally guard
GC_SWEEPING.with(|collecting| collecting.set(false));
}
unsafe {
mark(st.boxes_start);
sweep(&mut st.boxes_start, &mut st.bytes_allocated);
}
}
/// Immediately triggers a garbage collection on the current thread.
pub fn force_collect() {
GC_STATE.with(|st| {
let mut st = st.borrow_mut();
collect_garbage(&mut *st);
});
}