use super::code::{Bytecode, Coro, GFn, Lambda, Stay};
use super::collections::{Arr, DequeOps, Str, Tab};
use super::class::{Class, Obj};
use super::engine::{ACTIVE_ENGINE_ID, glsp, GStore, RData, RFn, Span, Sym, with_heap};
use super::error::{GResult};
use super::iter::{GIter, GIterState};
use super::val::{Hashable, Val};
use super::wrap::{ToVal};
use std::{f32};
use std::borrow::{Borrow};
use std::cell::{Cell, RefCell, RefMut};
use std::cmp::{max};
use std::fmt::{self, Debug};
use std::hash::{Hash, Hasher};
use std::mem::{size_of};
use std::ops::{Deref};
use std::process::{abort};
#[cfg(not(feature = "unsafe-internals"))]
use std::rc::Rc;
#[doc(hidden)]
#[cfg(not(feature = "unsafe-internals"))]
pub struct Gc<T: Allocate> {
rc: Rc<T>
}
#[cfg(not(feature = "unsafe-internals"))]
impl<T: Allocate> Gc<T> {
fn new(t: T) -> Gc<T> {
Gc {
rc: Rc::new(t)
}
}
pub(crate) fn ptr_eq(gc0: &Gc<T>, gc1: &Gc<T>) -> bool {
Rc::ptr_eq(&gc0.rc, &gc1.rc)
}
fn as_usize(&self) -> usize {
&(*self.rc) as *const T as usize
}
fn free(&self) {
self.clear_gcs()
}
}
#[cfg(not(feature = "unsafe-internals"))]
impl<T: Allocate> Clone for Gc<T> {
fn clone(&self) -> Gc<T> {
Gc {
rc: Rc::clone(&self.rc)
}
}
}
#[cfg(not(feature = "unsafe-internals"))]
impl<T: Allocate> Deref for Gc<T> {
type Target = T;
fn deref(&self) -> &T {
&*self.rc
}
}
#[cfg(feature = "unsafe-internals")]
use std::ptr::NonNull;
#[doc(hidden)]
#[cfg(feature = "unsafe-internals")]
pub struct Gc<T: Allocate> {
ptr: NonNull<T>
}
#[cfg(feature = "unsafe-internals")]
impl<T: Allocate> Gc<T> {
fn new(t: T) -> Gc<T> {
Gc {
ptr: NonNull::new(Box::into_raw(Box::new(t))).unwrap()
}
}
pub(crate) fn ptr_eq(gc0: &Gc<T>, gc1: &Gc<T>) -> bool {
gc0.ptr == gc1.ptr
}
fn as_usize(&self) -> usize {
self.ptr.as_ptr() as usize
}
fn free(&self) {
unsafe {
drop(Box::from_raw(self.ptr.as_ptr()))
}
}
}
#[cfg(feature = "unsafe-internals")]
impl<T: Allocate> Clone for Gc<T> {
fn clone(&self) -> Gc<T> {
Gc {
ptr: self.ptr
}
}
}
#[cfg(feature = "unsafe-internals")]
impl<T: Allocate> Deref for Gc<T> {
type Target = T;
fn deref(&self) -> &T {
unsafe {
&*self.ptr.as_ptr()
}
}
}
impl<T: Allocate> Gc<T> {
pub(crate) fn from_root(root: &Root<T>) -> Gc<T> {
let engine_id = ACTIVE_ENGINE_ID.with(|id| id.get().unwrap());
if engine_id != root.header().engine_id() {
eprintln!("attempted to move a Root to another Runtime - aborting process");
abort()
}
root.gc.clone()
}
pub(crate) fn root(&self) -> Root<T> {
Root::new(self.clone())
}
pub(crate) fn into_root(self) -> Root<T> {
Root::new(self)
}
fn header(&self) -> &GcHeader {
(**self).header()
}
}
impl<T: Allocate> PartialEq for Gc<T> {
fn eq(&self, other: &Gc<T>) -> bool {
self.as_usize() == other.as_usize()
}
}
impl<T: Allocate> Eq for Gc<T> { }
impl<T: Allocate> Hash for Gc<T> {
fn hash<H: Hasher>(&self, state: &mut H) {
self.as_usize().hash(state)
}
}
macro_rules! erased_types {
($($type_name:ident),+) => (
#[doc(hidden)]
pub trait Erase {
fn erase_gc(gc: Gc<Self>) -> ErasedGc where Self: Allocate;
}
$(impl Erase for $type_name {
#[inline(always)]
fn erase_gc(gc: Gc<$type_name>) -> ErasedGc {
ErasedGc::$type_name(gc)
}
})+
#[doc(hidden)]
#[derive(Clone)]
pub enum ErasedGc {
$($type_name(Gc<$type_name>)),+
}
impl ErasedGc {
fn header(&self) -> &GcHeader {
match *self {
$(ErasedGc::$type_name(ref gc) => &gc.header()),+
}
}
}
impl Debug for ErasedGc {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match *self {
$(
ErasedGc::$type_name(ref gc) => {
write!(f, "ErasedGc::{}(0x{:x})", stringify!($type_name),
(&**gc) as *const $type_name as usize)
}
)+
}
}
}
macro_rules! with_erased_gc {
($erased:expr, $gc_ident:ident, $body:expr) => (
match $erased {
$(ErasedGc::$type_name(ref $gc_ident) => $body),+
}
);
}
);
}
erased_types!(
Arr,
Str,
Tab,
GIter,
Obj,
Class,
GFn,
Stay,
Coro,
RData,
Bytecode,
Lambda
);
pub struct Root<T: Allocate> {
pub(crate) gc: Gc<T>
}
struct RootEntry {
gc: ErasedGc,
root_count: usize
}
impl<T: Allocate> Root<T> {
fn new(gc: Gc<T>) -> Root<T> {
let header = gc.header();
let engine_id = ACTIVE_ENGINE_ID.with(|id| id.get().unwrap());
if engine_id != header.engine_id() {
eprintln!("attempted to create a Root for an inactive Runtime - aborting process");
abort()
}
with_heap(|heap| {
if header.rooted() {
let root_index = header.root_index();
let mut roots = heap.roots.borrow_mut();
roots[root_index].root_count += 1;
} else {
let mut roots = heap.roots.borrow_mut();
roots.push(RootEntry {
gc: T::erase_gc(gc.clone()),
root_count: 1
});
header.set_root_index(roots.len() - 1);
}
});
Root {
gc
}
}
pub(crate) fn as_gc(&self) -> &Gc<T> {
&self.gc
}
pub(crate) fn to_gc(&self) -> Gc<T> {
Gc::from_root(self)
}
#[doc(hidden)]
pub fn into_gc(self) -> Gc<T> {
Gc::from_root(&self)
}
pub fn ptr_eq(root0: &Root<T>, root1: &Root<T>) -> bool {
Gc::ptr_eq(&root0.gc, &root1.gc)
}
}
impl<T: Allocate> Borrow<T> for Root<T> {
fn borrow(&self) -> &T {
&**self
}
}
impl<T: Allocate> AsRef<T> for Root<T> {
fn as_ref(&self) -> &T {
&**self
}
}
impl<T: Allocate + PartialEq<T>> PartialEq<Root<T>> for Root<T> {
fn eq(&self, other: &Root<T>) -> bool {
**self == **other
}
}
impl<T: Allocate> Clone for Root<T> {
fn clone(&self) -> Root<T> {
let header = self.gc.header();
let root_index = header.root_index();
let engine_id = ACTIVE_ENGINE_ID.with(|id| id.get().unwrap());
if engine_id != header.engine_id() {
eprintln!("attempted to clone a Root for an inactive Runtime - aborting process");
abort()
}
with_heap(|heap| {
heap.roots.borrow_mut()[root_index].root_count += 1;
});
Root {
gc: self.gc.clone()
}
}
}
impl<T: Allocate> Deref for Root<T> {
type Target = T;
fn deref(&self) -> &T {
&self.gc
}
}
impl<T: Allocate> Drop for Root<T> {
#[inline]
fn drop(&mut self) {
let header = self.gc.header();
let root_index = header.root_index();
let engine_id = ACTIVE_ENGINE_ID.with(|id| id.get().unwrap());
if engine_id != header.engine_id() {
eprintln!("attempted to drop a Root for an inactive Runtime - aborting process");
abort()
}
with_heap(|heap| {
let mut roots = heap.roots.borrow_mut();
if roots[root_index].root_count == 1 {
roots.swap_remove(root_index);
header.unroot();
if root_index < roots.len() {
roots[root_index].gc.header().set_root_index(root_index);
}
} else {
roots[root_index].root_count -= 1;
}
});
}
}
#[doc(hidden)]
#[derive(Clone)]
pub enum Slot {
Nil,
Int(i32),
Flo(f32),
Char(char),
Bool(bool),
Sym(Sym),
RFn(RFn),
Arr(Gc<Arr>),
Str(Gc<Str>),
Tab(Gc<Tab>),
GIter(Gc<GIter>),
Obj(Gc<Obj>),
Class(Gc<Class>),
GFn(Gc<GFn>),
Coro(Gc<Coro>),
RData(Gc<RData>)
}
impl Slot {
pub(crate) fn from_val(val: &Val) -> Slot {
match *val {
Val::Nil => Slot::Nil,
Val::Int(i) => Slot::Int(i),
Val::Char(c) => Slot::Char(c),
Val::Flo(f) => Slot::Flo(f),
Val::Bool(b) => Slot::Bool(b),
Val::Sym(s) => Slot::Sym(s),
Val::RFn(r) => Slot::RFn(r),
Val::Arr(ref a) => Slot::Arr(Gc::from_root(a)),
Val::Str(ref s) => Slot::Str(Gc::from_root(s)),
Val::Tab(ref t) => Slot::Tab(Gc::from_root(t)),
Val::GIter(ref g) => Slot::GIter(Gc::from_root(g)),
Val::Obj(ref o) => Slot::Obj(Gc::from_root(o)),
Val::Class(ref c) => Slot::Class(Gc::from_root(c)),
Val::GFn(ref g) => Slot::GFn(Gc::from_root(g)),
Val::Coro(ref c) => Slot::Coro(Gc::from_root(c)),
Val::RData(ref r) => Slot::RData(Gc::from_root(r))
}
}
pub(crate) fn root(&self) -> Val {
match *self {
Slot::Nil => Val::Nil,
Slot::Int(i) => Val::Int(i),
Slot::Char(c) => Val::Char(c),
Slot::Flo(f) => Val::Flo(f),
Slot::Bool(b) => Val::Bool(b),
Slot::Sym(s) => Val::Sym(s),
Slot::RFn(r) => Val::RFn(r),
Slot::Arr(ref a) => Val::Arr(a.root()),
Slot::Str(ref s) => Val::Str(s.root()),
Slot::Tab(ref t) => Val::Tab(t.root()),
Slot::GIter(ref g) => Val::GIter(g.root()),
Slot::Obj(ref o) => Val::Obj(o.root()),
Slot::Class(ref c) => Val::Class(c.root()),
Slot::GFn(ref c) => Val::GFn(c.root()),
Slot::Coro(ref c) => Val::Coro(c.root()),
Slot::RData(ref r) => Val::RData(r.root()),
}
}
pub(crate) fn into_root(self) -> Val {
match self {
Slot::Nil => Val::Nil,
Slot::Int(i) => Val::Int(i),
Slot::Char(c) => Val::Char(c),
Slot::Flo(f) => Val::Flo(f),
Slot::Bool(b) => Val::Bool(b),
Slot::Sym(s) => Val::Sym(s),
Slot::RFn(r) => Val::RFn(r),
Slot::Arr(a) => Val::Arr(a.into_root()),
Slot::Str(s) => Val::Str(s.into_root()),
Slot::Tab(t) => Val::Tab(t.into_root()),
Slot::GIter(g) => Val::GIter(g.into_root()),
Slot::Obj(o) => Val::Obj(o.into_root()),
Slot::Class(c) => Val::Class(c.into_root()),
Slot::GFn(c) => Val::GFn(c.into_root()),
Slot::Coro(c) => Val::Coro(c.into_root()),
Slot::RData(r) => Val::RData(r.into_root()),
}
}
pub fn type_name(&self) -> &'static str {
self.root().type_name()
}
pub fn a_type_name(&self) -> &'static str {
self.root().a_type_name()
}
}
impl PartialEq<Slot> for Slot {
fn eq(&self, other: &Slot) -> bool {
self.root().keys_eqv(&other.root())
}
}
impl Eq for Slot { }
impl Hash for Slot {
fn hash<H: Hasher>(&self, state: &mut H) {
match *self {
Slot::Nil => Hashable(Val::Nil).hash(state),
Slot::Int(i) => Hashable(Val::Int(i)).hash(state),
Slot::Flo(f) => Hashable(Val::Flo(f)).hash(state),
Slot::Char(c) => Hashable(Val::Char(c)).hash(state),
Slot::Bool(b) => Hashable(Val::Bool(b)).hash(state),
Slot::Sym(s) => Hashable(Val::Sym(s)).hash(state),
Slot::RFn(f) => Hashable(Val::RFn(f)).hash(state),
Slot::Arr(ref gc) => (**gc).hash(state),
Slot::Str(ref gc) => (**gc).hash(state),
Slot::Tab(ref gc) => (&**gc as *const _ as usize).hash(state),
Slot::GIter(ref gc) => (&**gc as *const _ as usize).hash(state),
Slot::Obj(ref gc) => (&**gc as *const _ as usize).hash(state),
Slot::Class(ref gc) => (&**gc as *const _ as usize).hash(state),
Slot::GFn(ref gc) => (&**gc as *const _ as usize).hash(state),
Slot::Coro(ref gc) => (&**gc as *const _ as usize).hash(state),
Slot::RData(ref gc) => (&**gc as *const _ as usize).hash(state)
}
}
}
const ENGINE_ID_SHIFT: u32 = 24;
const ENGINE_ID_MASK: u32 = 0xff << 24;
const FROZEN_BIT: u32 = 0x1 << 23;
const ROOT_INDEX_MASK: u32 = !(ENGINE_ID_MASK | FROZEN_BIT);
const UNROOTED_BITS: u32 = ROOT_INDEX_MASK;
const MAX_ROOT_INDEX: usize = (ROOT_INDEX_MASK - 1) as usize;
const MARKED_YOUNG_BITS: u32 = 0x_ffff_ffff;
const UNMARKED_YOUNG_BITS: u32 = 0x_ffff_fffe;
const COLOR_SHIFT: u32 = 30;
const COLOR_MASK: u32 = 0x3 << 30;
const OLD_INDEX_MASK: u32 = !COLOR_MASK;
const MAX_OLD_INDEX: usize = (OLD_INDEX_MASK - 2) as usize;
#[doc(hidden)]
#[derive(Clone)]
pub struct GcHeader {
hi: Cell<u32>,
lo: Cell<u32>
}
impl GcHeader {
pub(crate) fn new() -> GcHeader {
let engine_id = ACTIVE_ENGINE_ID.with(|id| id.get().unwrap()) as u32;
GcHeader {
hi: Cell::new((engine_id << ENGINE_ID_SHIFT) | UNROOTED_BITS),
lo: Cell::new(UNMARKED_YOUNG_BITS)
}
}
fn reset(&self) {
let engine_id = ACTIVE_ENGINE_ID.with(|id| id.get().unwrap()) as u32;
self.hi.set((engine_id << ENGINE_ID_SHIFT) | UNROOTED_BITS);
self.lo.set(UNMARKED_YOUNG_BITS);
}
fn engine_id(&self) -> u8 {
(self.hi.get() >> ENGINE_ID_SHIFT) as u8
}
pub(crate) fn frozen(&self) -> bool {
(self.hi.get() & FROZEN_BIT) != 0
}
pub(crate) fn freeze(&self) {
self.hi.set(self.hi.get() | FROZEN_BIT);
}
fn rooted(&self) -> bool {
(self.hi.get() & ROOT_INDEX_MASK) != UNROOTED_BITS
}
fn unroot(&self) {
self.hi.set(self.hi.get() | UNROOTED_BITS);
}
fn root_index(&self) -> usize {
(self.hi.get() & ROOT_INDEX_MASK) as usize
}
fn set_root_index(&self, root_index: usize) {
debug_assert!(root_index <= MAX_ROOT_INDEX);
self.hi.set((self.hi.get() & !ROOT_INDEX_MASK) | (root_index as u32));
}
fn young(&self) -> bool {
self.lo.get() >= UNMARKED_YOUNG_BITS
}
fn marked(&self) -> bool {
debug_assert!(self.young());
self.lo.get() == MARKED_YOUNG_BITS
}
fn mark(&self) {
debug_assert!(self.young() && !self.marked());
self.lo.set(MARKED_YOUNG_BITS)
}
fn promote(&self, color_index: usize, old_index: usize) {
debug_assert!(self.young() && color_index <= 3 && old_index <= MAX_OLD_INDEX);
self.lo.set(((color_index as u32) << COLOR_SHIFT) | (old_index as u32));
}
fn color_index(&self) -> usize {
debug_assert!(!self.young());
(self.lo.get() >> COLOR_SHIFT) as usize
}
fn set_color_index(&self, color_index: usize) {
debug_assert!(!self.young());
debug_assert!(color_index <= 3);
self.lo.set((self.lo.get() & !COLOR_MASK) | ((color_index as u32) << COLOR_SHIFT));
}
fn old_index(&self) -> usize {
debug_assert!(!self.young());
(self.lo.get() & OLD_INDEX_MASK) as usize
}
fn set_old_index(&self, old_index: usize) {
debug_assert!(!self.young() && old_index <= MAX_OLD_INDEX);
self.lo.set((self.lo.get() & !OLD_INDEX_MASK) | (old_index as u32));
}
}
#[doc(hidden)]
pub trait Visitor {
fn visit_gc<T: Allocate>(&mut self, rc: &Gc<T>);
fn visit_slot(&mut self, slot: &Slot) {
match *slot {
Slot::Nil | Slot::Int(_) | Slot::Char(_) | Slot::Flo(_) |
Slot::Bool(_) | Slot::Sym(_) | Slot::RFn(_) => (),
Slot::Arr(ref a) => self.visit_gc(a),
Slot::Str(ref s) => self.visit_gc(s),
Slot::Tab(ref t) => self.visit_gc(t),
Slot::GIter(ref g) => self.visit_gc(g),
Slot::Obj(ref o) => self.visit_gc(o),
Slot::Class(ref c) => self.visit_gc(c),
Slot::GFn(ref g) => self.visit_gc(g),
Slot::Coro(ref c) => self.visit_gc(c),
Slot::RData(ref r) => self.visit_gc(r)
}
}
}
struct MarkingVisitor<'a, 'b> {
heap: &'a Heap,
marking_stack: &'b mut RefMut<'a, Vec<ErasedGc>>,
old_objects: &'b mut [RefMut<'a, Vec<ErasedGc>>; 4],
old_only: bool
}
impl<'a, 'b> MarkingVisitor<'a, 'b> {
fn new(
heap: &'a Heap,
marking_stack: &'b mut RefMut<'a, Vec<ErasedGc>>,
old_objects: &'b mut [RefMut<'a, Vec<ErasedGc>>; 4],
old_only: bool
) -> MarkingVisitor<'a, 'b>
{
MarkingVisitor {
heap,
marking_stack,
old_objects,
old_only
}
}
}
impl<'a, 'b> Visitor for MarkingVisitor<'a, 'b> {
fn visit_gc<T: Allocate>(&mut self, gc: &Gc<T>) {
let header = gc.header();
if header.young() {
debug_assert!(!self.old_only);
if !header.marked() {
header.mark();
self.marking_stack.push(T::erase_gc(gc.clone()));
}
} else {
if header.color_index() == self.heap.white_index.get() {
self.heap.change_color(gc, self.heap.gray_index.get(), self.old_objects);
}
}
}
}
#[doc(hidden)]
pub trait Allocate: Sized + GStore + Erase {
fn visit_gcs<V: Visitor>(&self, visitor: &mut V);
fn clear_gcs(&self);
fn header(&self) -> &GcHeader;
fn owned_memory_usage(&self) -> usize;
fn memory_usage(&self) -> usize {
size_of::<Self>() + self.owned_memory_usage()
}
}
const MIN_SURVIVING_BYTES: usize = 1024 * 1024;
const INITIAL_U: f32 = 1.5;
const INITIAL_R: f32 = 2.0 / (INITIAL_U - 1.0);
const INITIAL_W: Option<f32> = None;
pub const GC_MIN_RATIO: f32 = 1.2;
pub const GC_DEFAULT_RATIO: f32 = INITIAL_U;
pub(crate) struct Heap {
pub(crate) recycler: Recycler,
young_objects: RefCell<Vec<ErasedGc>>,
young_bytes: Cell<usize>,
marking_stack: RefCell<Vec<ErasedGc>>,
old_objects: [RefCell<Vec<ErasedGc>>; 4],
old_bytes: [Cell<usize>; 4],
white_index: Cell<usize>,
gray_index: Cell<usize>,
black_index: Cell<usize>,
ghost_index: Cell<usize>,
roots: RefCell<Vec<RootEntry>>,
black_target: Cell<usize>,
ghost_target: Cell<usize>,
ratio_u: Cell<f32>,
ratio_r: Cell<f32>,
ratio_w: Cell<Option<f32>>,
}
impl Drop for Heap {
fn drop(&mut self) {
if self.roots.get_mut().len() > 0 {
eprintln!("a Root has outlived its originating Runtime - aborting process");
abort()
}
}
}
impl Heap {
pub(crate) fn new() -> Heap {
Heap {
recycler: Recycler::new(),
young_objects: RefCell::new(Vec::new()),
young_bytes: Cell::new(0),
marking_stack: RefCell::new(Vec::new()),
old_objects: [RefCell::new(Vec::new()), RefCell::new(Vec::new()),
RefCell::new(Vec::new()), RefCell::new(Vec::new())],
old_bytes: [Cell::new(0), Cell::new(0), Cell::new(0), Cell::new(0)],
white_index: Cell::new(0),
gray_index: Cell::new(1),
black_index: Cell::new(2),
ghost_index: Cell::new(3),
roots: RefCell::new(Vec::new()),
black_target: Cell::new(0),
ghost_target: Cell::new(0),
ratio_u: Cell::new(INITIAL_U),
ratio_r: Cell::new(INITIAL_R),
ratio_w: Cell::new(INITIAL_W)
}
}
#[allow(dead_code)]
pub(crate) fn clear(&self) {
for erased in self.young_objects.borrow_mut().drain(..) {
with_erased_gc!(erased, gc, gc.free())
}
self.young_bytes.set(0);
self.marking_stack.borrow_mut().clear();
for i in 0..4 {
for erased in self.old_objects[i].borrow_mut().drain(..) {
with_erased_gc!(erased, gc, gc.free())
}
self.old_bytes[i].set(0);
}
self.black_target.set(0);
self.ghost_target.set(0);
self.ratio_u.set(INITIAL_U);
self.ratio_r.set(INITIAL_R);
self.ratio_w.set(INITIAL_W);
}
pub(crate) fn ratio(&self) -> f32 {
self.ratio_u.get()
}
pub(crate) fn set_ratio(&self, ratio: f32) {
let ratio = f32::min(f32::max(GC_MIN_RATIO, ratio), 10.0);
self.ratio_u.set(ratio);
self.ratio_r.set(2.0 / (ratio - 1.0));
}
#[inline]
pub(crate) fn alloc<T: Allocate>(&self, init: T) -> Root<T> {
Root::new(self.alloc_gc(init))
}
pub(crate) fn alloc_gc<T: Allocate>(&self, init: T) -> Gc<T> {
let gc = Gc::new(init);
self.register_young(gc.clone());
gc
}
fn register_young<T: Allocate>(&self, gc: Gc<T>) {
let header = gc.header();
debug_assert!(header.young() && !header.marked());
self.young_bytes.set(self.young_bytes.get() + gc.memory_usage());
self.young_objects.borrow_mut().push(T::erase_gc(gc));
}
fn promote<T: Allocate>(
&self,
gc: &Gc<T>,
old_objects: &mut [RefMut<Vec<ErasedGc>>; 4]
) -> usize {
debug_assert!(gc.header().young());
let black_index = self.black_index.get();
old_objects[black_index].push(T::erase_gc(gc.clone()));
gc.header().promote(black_index, old_objects[black_index].len() - 1);
let memory_usage = gc.memory_usage();
self.old_bytes[black_index].set(self.old_bytes[black_index].get() + memory_usage);
memory_usage
}
fn change_color<T: Allocate>(
&self,
gc: &Gc<T>,
new_color_index: usize,
old_objects: &mut [RefMut<Vec<ErasedGc>>; 4]
) {
let header = gc.header();
debug_assert!(!header.young());
let prev_color_index = header.color_index();
debug_assert!(prev_color_index != new_color_index);
let prev_i = header.old_index();
let erased = old_objects[prev_color_index].swap_remove(prev_i);
if prev_i < old_objects[prev_color_index].len() {
old_objects[prev_color_index][prev_i].header().set_old_index(prev_i);
}
old_objects[new_color_index].push(erased);
header.set_old_index(old_objects[new_color_index].len() - 1);
header.set_color_index(new_color_index);
let usage = gc.memory_usage();
self.old_bytes[prev_color_index].set(self.old_bytes[prev_color_index].get() - usage);
self.old_bytes[new_color_index].set(self.old_bytes[new_color_index].get() + usage);
}
pub(crate) fn step(&self) {
let mut young_objects = self.young_objects.borrow_mut();
let mut old_objects = [
self.old_objects[0].borrow_mut(),
self.old_objects[1].borrow_mut(),
self.old_objects[2].borrow_mut(),
self.old_objects[3].borrow_mut()
];
let mut marking_stack = self.marking_stack.borrow_mut();
let white_index = self.white_index.get();
let gray_index = self.gray_index.get();
let black_index = self.black_index.get();
let ghost_index = self.ghost_index.get();
for root_entry in self.roots.borrow().iter() {
with_erased_gc!(root_entry.gc, gc, {
let mut visitor = MarkingVisitor::new(self, &mut marking_stack,
&mut old_objects, false);
visitor.visit_gc(gc);
})
}
while let Some(erased) = marking_stack.pop() {
with_erased_gc!(erased, gc, {
let mut visitor = MarkingVisitor::new(self, &mut marking_stack,
&mut old_objects, false);
gc.visit_gcs(&mut visitor);
})
}
let mut promoted_bytes: usize = 0;
for erased in young_objects.drain(..) {
with_erased_gc!(erased, gc, {
let header = gc.header();
if header.marked() {
promoted_bytes += self.promote(gc, &mut old_objects);
} else {
self.recycler.free(erased);
}
})
}
self.young_bytes.set(0);
let target_incr = ((self.ratio_r.get() + 1.0) * promoted_bytes as f32).ceil() as usize;
self.black_target.set(self.black_target.get() + target_incr);
while self.old_bytes[black_index].get() < self.black_target.get() &&
!old_objects[gray_index].is_empty() {
let erased = old_objects[gray_index].last().unwrap().clone();
with_erased_gc!(erased, gc, {
self.change_color(gc, black_index, &mut old_objects);
let mut visitor = MarkingVisitor::new(self, &mut marking_stack,
&mut old_objects, true);
gc.visit_gcs(&mut visitor);
})
}
if let Some(ratio_w) = self.ratio_w.get() {
let bytes_to_free = (ratio_w * target_incr as f32).ceil() as usize;
self.ghost_target.set(self.ghost_target.get().saturating_sub(bytes_to_free));
while self.old_bytes[ghost_index].get() > self.ghost_target.get() {
let erased = old_objects[ghost_index].pop().unwrap();
with_erased_gc!(erased, gc, {
let memory_usage = gc.memory_usage();
self.old_bytes[ghost_index].set(self.old_bytes[ghost_index].get() -
memory_usage);
gc.free();
})
}
} else {
debug_assert!(old_objects[ghost_index].is_empty());
}
if old_objects[gray_index].is_empty() &&
self.old_bytes[black_index].get() >= MIN_SURVIVING_BYTES {
while let Some(erased) = old_objects[ghost_index].pop() {
old_objects[white_index].push(erased.clone());
let header = erased.header();
header.set_color_index(white_index);
header.set_old_index(old_objects[white_index].len() - 1);
}
self.old_bytes[white_index].set(
self.old_bytes[white_index].get() + self.old_bytes[ghost_index].get()
);
self.old_bytes[ghost_index].set(0);
let prev_white_index = self.white_index.get();
let prev_black_index = self.black_index.get();
let prev_ghost_index = self.ghost_index.get();
self.white_index.set(prev_black_index);
self.black_index.set(prev_ghost_index);
self.ghost_index.set(prev_white_index);
self.ghost_target.set(self.old_bytes[self.ghost_index.get()].get());
self.black_target.set(0);
let ghost_bytes = self.old_bytes[self.ghost_index.get()].get();
if ghost_bytes > 0 {
let surviving_bytes = self.old_bytes[self.white_index.get()].get();
let denominator = max(surviving_bytes, MIN_SURVIVING_BYTES);
let w = (ghost_bytes as f32) / (denominator as f32);
self.ratio_w.set(Some(w));
} else {
self.ratio_w.set(None);
}
}
}
pub(crate) fn young_memory_usage(&self) -> usize {
self.young_bytes.get()
}
pub(crate) fn old_memory_usage(&self) -> usize {
self.old_bytes[self.white_index.get()].get() +
self.old_bytes[self.gray_index.get()].get() +
self.old_bytes[self.black_index.get()].get()
}
pub(crate) fn ghost_memory_usage(&self) -> usize {
self.old_bytes[self.ghost_index.get()].get()
}
pub(crate) fn traverse_stack_slot(&self, dst: &Slot) {
match *dst {
Slot::Nil | Slot::Int(_) | Slot::Char(_) | Slot::Flo(_) |
Slot::Bool(_) | Slot::Sym(_) | Slot::RFn(_) => (),
Slot::Arr(ref gc) => self.traverse_stack_gc(gc),
Slot::Str(ref gc) => self.traverse_stack_gc(gc),
Slot::Tab(ref gc) => self.traverse_stack_gc(gc),
Slot::GIter(ref gc) => self.traverse_stack_gc(gc),
Slot::Obj(ref gc) => self.traverse_stack_gc(gc),
Slot::Class(ref gc) => self.traverse_stack_gc(gc),
Slot::GFn(ref gc) => self.traverse_stack_gc(gc),
Slot::Coro(ref gc) => self.traverse_stack_gc(gc),
Slot::RData(ref gc) => self.traverse_stack_gc(gc)
}
}
pub(crate) fn traverse_stack_gc<T: Allocate>(&self, dst: &Gc<T>) {
let header = dst.header();
let engine_id = ACTIVE_ENGINE_ID.with(|id| id.get().unwrap());
if engine_id != header.engine_id() {
eprintln!("attempted to move a Root to another Runtime - aborting process");
abort()
}
if header.young() {
if !header.marked() {
self.marking_stack.borrow_mut().push(T::erase_gc(dst.clone()));
header.mark();
}
} else {
if header.color_index() == self.white_index.get() {
let mut old_objects = [
self.old_objects[0].borrow_mut(),
self.old_objects[1].borrow_mut(),
self.old_objects[2].borrow_mut(),
self.old_objects[3].borrow_mut()
];
self.change_color(dst, self.gray_index.get(), &mut old_objects);
}
}
}
pub(crate) fn write_barrier_val<T: Allocate>(&self, src: &T, dst: &Val) {
match *dst {
Val::Nil | Val::Int(_) | Val::Char(_) | Val::Flo(_) |
Val::Bool(_) | Val::Sym(_) | Val::RFn(_) => (),
Val::Arr(ref root) => self.write_barrier(src, &root.to_gc()),
Val::Str(ref root) => self.write_barrier(src, &root.to_gc()),
Val::Tab(ref root) => self.write_barrier(src, &root.to_gc()),
Val::GIter(ref root) => self.write_barrier(src, &root.to_gc()),
Val::Obj(ref root) => self.write_barrier(src, &root.to_gc()),
Val::Class(ref root) => self.write_barrier(src, &root.to_gc()),
Val::GFn(ref root) => self.write_barrier(src, &root.to_gc()),
Val::Coro(ref root) => self.write_barrier(src, &root.to_gc()),
Val::RData(ref root) => self.write_barrier(src, &root.to_gc())
}
}
pub(crate) fn write_barrier_slot<T: Allocate>(&self, src: &T, dst: &Slot) {
match *dst {
Slot::Nil | Slot::Int(_) | Slot::Char(_) | Slot::Flo(_) |
Slot::Bool(_) | Slot::Sym(_) | Slot::RFn(_) => (),
Slot::Arr(ref gc) => self.write_barrier(src, gc),
Slot::Str(ref gc) => self.write_barrier(src, gc),
Slot::Tab(ref gc) => self.write_barrier(src, gc),
Slot::GIter(ref gc) => self.write_barrier(src, gc),
Slot::Obj(ref gc) => self.write_barrier(src, gc),
Slot::Class(ref gc) => self.write_barrier(src, gc),
Slot::GFn(ref gc) => self.write_barrier(src, gc),
Slot::Coro(ref gc) => self.write_barrier(src, gc),
Slot::RData(ref gc) => self.write_barrier(src, gc)
}
}
pub(crate) fn write_barrier<T, U>(&self, src: &T, dst: &Gc<U>)
where
T: Allocate,
U: Allocate
{
let src_header = src.header();
let dst_header = dst.header();
if src_header.engine_id() != dst_header.engine_id() {
eprintln!("attempted to move a Root to another Runtime - aborting process");
abort()
}
if !src_header.young() {
if dst_header.young() {
if !dst_header.marked() {
self.marking_stack.borrow_mut().push(U::erase_gc(dst.clone()));
dst_header.mark();
}
} else {
if dst_header.color_index() == self.white_index.get() &&
src_header.color_index() == self.black_index.get() {
let mut old_objects = [
self.old_objects[0].borrow_mut(),
self.old_objects[1].borrow_mut(),
self.old_objects[2].borrow_mut(),
self.old_objects[3].borrow_mut()
];
self.change_color(dst, self.gray_index.get(), &mut old_objects);
}
}
}
}
pub(crate) fn memory_usage_barrier<T>(&self, src: &T, prev_usage: usize, cur_usage: usize)
where
T: Allocate
{
let header = src.header();
if header.young() {
let current = self.young_bytes.get();
let new = (current + cur_usage) - prev_usage;
self.young_bytes.set(new);
} else {
let i = header.color_index();
let current = self.old_bytes[i].get();
let new = (current + cur_usage) - prev_usage;
self.old_bytes[i].set(new);
}
}
}
const MAX_ARR_CAPACITY: usize = 16;
pub(crate) struct Recycler {
arrs: Vec<RefCell<Vec<Gc<Arr>>>>,
giters: RefCell<Vec<Gc<GIter>>>
}
impl Recycler {
fn new() -> Recycler {
Recycler {
arrs: vec![RefCell::new(Vec::new()); 32],
giters: RefCell::new(Vec::new())
}
}
fn free(&self, erased: ErasedGc) {
match erased {
ErasedGc::Arr(arr) => {
let cap = arr.capacity();
if cap < MAX_ARR_CAPACITY {
let header = arr.header();
debug_assert!(!header.rooted());
header.reset();
arr.clear().unwrap();
arr.set_span(Span::default());
self.arrs[cap].borrow_mut().push(arr);
} else {
arr.free();
}
}
ErasedGc::GIter(giter) => {
let header = giter.header();
debug_assert!(!header.rooted());
header.reset();
giter.clear_gcs();
self.giters.borrow_mut().push(giter);
}
ErasedGc::Str(gc) => gc.free(),
ErasedGc::Tab(gc) => gc.free(),
ErasedGc::Obj(gc) => gc.free(),
ErasedGc::Class(gc) => gc.free(),
ErasedGc::GFn(gc) => gc.free(),
ErasedGc::Stay(gc) => gc.free(),
ErasedGc::Coro(gc) => gc.free(),
ErasedGc::RData(gc) => gc.free(),
ErasedGc::Bytecode(gc) => gc.free(),
ErasedGc::Lambda(gc) => gc.free()
}
}
pub(crate) fn arr(&self) -> Root<Arr> {
for arrs in &self.arrs {
let mut arrs = arrs.borrow_mut();
if !arrs.is_empty() {
let arr = arrs.pop().unwrap().into_root();
drop(arrs);
with_heap(|heap| heap.register_young(arr.to_gc()));
return arr
}
}
glsp::alloc(Arr::new())
}
pub(crate) fn arr_with_capacity(&self, capacity: usize) -> Root<Arr> {
for i in capacity .. MAX_ARR_CAPACITY {
let mut arrs = self.arrs[i].borrow_mut();
if !arrs.is_empty() {
let arr = arrs.pop().unwrap().into_root();
drop(arrs);
with_heap(|heap| heap.register_young(arr.to_gc()));
return arr
}
}
glsp::alloc(Arr::with_capacity(capacity))
}
pub(crate) fn arr_from_elem<V: ToVal>(
&self,
elem: V,
reps: usize
) -> GResult<Root<Arr>> {
for i in reps .. MAX_ARR_CAPACITY {
let mut arrs = self.arrs[i].borrow_mut();
if !arrs.is_empty() {
let arr = arrs.pop().unwrap().into_root();
drop(arrs);
with_heap(|heap| heap.register_young(arr.to_gc()));
for _ in 0 .. reps {
arr.push(elem.to_slot()?)?;
}
return Ok(arr)
}
}
Ok(glsp::alloc(Arr::from_elem(elem, reps)?))
}
pub(crate) fn arr_from_iter<T, V>(&self, source: T) -> GResult<Root<Arr>>
where
T: IntoIterator<Item = V>,
V: ToVal
{
let iter = source.into_iter();
let (min_size, max_size) = iter.size_hint();
if max_size.is_some() && min_size == max_size.unwrap() {
let capacity = min_size;
for i in capacity .. MAX_ARR_CAPACITY {
let mut arrs = self.arrs[i].borrow_mut();
if !arrs.is_empty() {
let arr = arrs.pop().unwrap().into_root();
drop(arrs);
with_heap(|heap| heap.register_young(arr.to_gc()));
for item in iter {
arr.push(item.to_slot()?)?;
}
return Ok(arr)
}
}
}
Ok(glsp::alloc(Arr::from_iter(iter)?))
}
pub(crate) fn giter(&self, state: GIterState) -> Root<GIter> {
if let Some(gc) = self.giters.borrow_mut().pop() {
let giter = gc.root();
with_heap(|heap| heap.register_young(gc));
*giter.state.borrow_mut() = state;
giter
} else {
glsp::alloc(GIter::new(state))
}
}
}