use crate::{
cast,
gc::{
array::ArrayHeader, Array as GcArray, Event, GcPtr, GcRuntime, Observer, RawGcPtr, Stats,
TypeTrace,
},
mapping::{self, resolve_struct_to_struct_edit, Action, FieldMapping, MemoryMapper},
r#type::Type,
TypeKind,
};
use mapping::{Mapping, StructMapping};
use parking_lot::RwLock;
use std::{
alloc::{Layout, LayoutError},
borrow::Cow,
collections::{HashMap, VecDeque},
ops::{Deref, DerefMut},
pin::Pin,
ptr::NonNull,
};
pub struct Trace {
stack: VecDeque<CompositeTrace>,
}
impl Trace {
fn new(obj: NonNull<ObjectInfo>) -> Trace {
let mut trace = Trace {
stack: Default::default(),
};
let obj_ref = unsafe { obj.as_ref() };
match obj_ref.ty.kind() {
TypeKind::Primitive(_) | TypeKind::Pointer(_) => {}
TypeKind::Struct(_) => {
trace.stack.push_back(CompositeTrace::Struct(StructTrace {
struct_ptr: unsafe { obj_ref.data.ptr },
struct_type: obj_ref.ty.clone(),
field_index: 0,
}));
}
TypeKind::Array(arr) => {
let array_handle = ArrayHandle { obj };
trace.stack.push_back(CompositeTrace::Array(ArrayTrace {
iter: array_handle.elements(),
element_ty: arr.element_type(),
}));
}
}
trace
}
}
impl Iterator for Trace {
type Item = GcPtr;
fn next(&mut self) -> Option<Self::Item> {
loop {
let top_stack = self.stack.back_mut()?;
let event = match top_stack {
CompositeTrace::Struct(s) => s.next(),
CompositeTrace::Array(a) => a.next(),
};
match event {
None => {
self.stack.pop_back();
}
Some(TraceEvent::Reference(r)) => return Some(r.into()),
Some(TraceEvent::InlineStruct(s)) => {
self.stack.push_back(CompositeTrace::Struct(s))
}
}
}
}
}
enum CompositeTrace {
Struct(StructTrace),
Array(ArrayTrace),
}
enum TraceEvent {
Reference(NonNull<ObjectInfo>),
InlineStruct(StructTrace),
}
impl TraceEvent {
pub fn new(ptr: NonNull<u8>, ty: Cow<'_, Type>) -> Option<TraceEvent> {
match ty.kind() {
TypeKind::Primitive(_) | TypeKind::Pointer(_) => None,
TypeKind::Struct(s) => {
return if s.is_gc_struct() {
let deref_ptr = unsafe { ptr.cast::<NonNull<ObjectInfo>>().as_ref() };
Some(TraceEvent::Reference(*deref_ptr))
} else {
Some(TraceEvent::InlineStruct(StructTrace {
struct_ptr: ptr.cast(),
struct_type: ty.into_owned(),
field_index: 0,
}))
}
}
TypeKind::Array(_) => Some(TraceEvent::Reference(ptr.cast())),
}
}
}
struct StructTrace {
struct_ptr: NonNull<u8>,
struct_type: Type,
field_index: usize,
}
impl Iterator for StructTrace {
type Item = TraceEvent;
fn next(&mut self) -> Option<Self::Item> {
let struct_ty = self.struct_type.as_struct()?;
let fields = struct_ty.fields();
let field_count = fields.len();
while self.field_index < field_count {
let index = self.field_index;
self.field_index += 1;
let field = fields.get(index).unwrap();
let field_ty = field.ty();
let field_ptr =
unsafe { NonNull::new_unchecked(self.struct_ptr.as_ptr().add(field.offset())) };
if let Some(event) = TraceEvent::new(field_ptr, Cow::Owned(field_ty)) {
return Some(event);
}
}
None
}
}
struct ArrayTrace {
iter: ArrayHandleIter,
element_ty: Type,
}
impl Iterator for ArrayTrace {
type Item = TraceEvent;
fn next(&mut self) -> Option<Self::Item> {
loop {
if let Some(event) = TraceEvent::new(self.iter.next()?, Cow::Borrowed(&self.element_ty))
{
break Some(event);
}
}
}
}
impl TypeTrace for Type {
type Trace = Trace;
fn trace(&self, obj: GcPtr) -> Self::Trace {
let obj = NonNull::new(obj.as_ptr() as *mut ObjectInfo).expect("invalid gc ptr");
Trace::new(obj)
}
}
pub struct MarkSweep<O>
where
O: Observer<Event = Event>,
{
objects: RwLock<HashMap<GcPtr, Pin<Box<ObjectInfo>>>>,
observer: O,
stats: RwLock<Stats>,
}
impl<O> Default for MarkSweep<O>
where
O: Observer<Event = Event> + Default,
{
fn default() -> Self {
MarkSweep {
objects: RwLock::new(HashMap::new()),
observer: O::default(),
stats: RwLock::new(Stats::default()),
}
}
}
impl<O> MarkSweep<O>
where
O: Observer<Event = Event>,
{
pub fn with_observer(observer: O) -> Self {
Self {
objects: RwLock::new(HashMap::new()),
observer,
stats: RwLock::new(Stats::default()),
}
}
fn log_alloc(&self, handle: GcPtr, size: usize) {
{
let mut stats = self.stats.write();
stats.allocated_memory += size;
}
self.observer.event(Event::Allocation(handle));
}
pub fn observer(&self) -> &O {
&self.observer
}
}
fn alloc_obj(ty: Type) -> Pin<Box<ObjectInfo>> {
let ptr = NonNull::new(unsafe { std::alloc::alloc_zeroed(ty.value_layout()) })
.expect("failed to allocate memory for new object");
Box::pin(ObjectInfo {
data: ObjectInfoData { ptr },
ty,
roots: 0,
color: Color::White,
})
}
#[derive(Debug)]
pub enum MemoryLayoutError {
OutOfBounds,
LayoutError(LayoutError),
}
impl From<LayoutError> for MemoryLayoutError {
fn from(err: LayoutError) -> Self {
MemoryLayoutError::LayoutError(err)
}
}
pub struct ArrayHandle {
obj: NonNull<ObjectInfo>,
}
impl ArrayHandle {
pub fn header(&self) -> &ArrayHeader {
unsafe { self.obj.as_ref().data.array.as_ref() }
}
pub unsafe fn set_length(&mut self, length: usize) {
let header = self.obj.as_mut().data.array.as_mut();
debug_assert!(header.capacity >= length);
header.length = length;
}
pub fn element_layout(&self) -> Layout {
self.element_type().reference_layout()
}
pub fn element_stride(&self) -> usize {
self.element_layout().pad_to_align().size()
}
pub fn data(&self) -> NonNull<u8> {
let element_layout = self.element_layout();
let header_layout = Layout::new::<ArrayHeader>();
let (_, padded_header_size) = header_layout
.extend(element_layout)
.expect("error creating combined layout of header and element");
unsafe {
NonNull::new_unchecked(
(self.obj.as_ref().data.array.as_ptr().cast::<u8>() as *mut u8)
.add(padded_header_size),
)
}
}
}
impl GcArray for ArrayHandle {
type Iterator = ArrayHandleIter;
fn as_raw(&self) -> GcPtr {
self.obj.into()
}
fn element_type(&self) -> Type {
let array_ty = &unsafe { self.obj.as_ref() }.ty;
array_ty
.as_array()
.expect("unable to determine element_type, type is not an array")
.element_type()
}
fn length(&self) -> usize {
self.header().length
}
fn capacity(&self) -> usize {
self.header().capacity
}
fn elements(&self) -> Self::Iterator {
let length = self.length();
let next = self.data();
let element_ty = self.element_type();
let element_layout = element_ty.reference_layout();
ArrayHandleIter {
remaining: length,
next,
stride: element_layout.pad_to_align().size(),
}
}
}
pub struct ArrayHandleIter {
next: NonNull<u8>,
remaining: usize,
stride: usize,
}
impl Iterator for ArrayHandleIter {
type Item = NonNull<u8>;
fn next(&mut self) -> Option<Self::Item> {
if self.remaining > 0 {
let element = self.next;
self.remaining -= 1;
self.next = unsafe { NonNull::new_unchecked(self.next.as_ptr().add(self.stride)) };
Some(element)
} else {
None
}
}
}
fn repeat_layout(layout: Layout, n: usize) -> Result<Layout, MemoryLayoutError> {
let len_rounded_up = layout.size().wrapping_add(layout.align()).wrapping_sub(1)
& !layout.align().wrapping_sub(1);
let padded_size = layout.size() + len_rounded_up.wrapping_sub(layout.align());
let alloc_size = padded_size
.checked_mul(n)
.ok_or(MemoryLayoutError::OutOfBounds)?;
Layout::from_size_align(alloc_size, layout.align()).map_err(Into::into)
}
fn alloc_array(ty: Type, length: usize) -> Pin<Box<ObjectInfo>> {
Box::pin(ObjectInfo {
data: ObjectInfoData {
array: array_header(&ty, length),
},
ty,
roots: 0,
color: Color::White,
})
}
fn array_header(ty: &Type, length: usize) -> NonNull<ArrayHeader> {
let array_ty = ty
.as_array()
.expect("array type doesnt have an element type");
let header_layout = Layout::new::<ArrayHeader>();
let element_ty_layout = array_ty.element_type().reference_layout();
let elements_layout = repeat_layout(element_ty_layout, length)
.expect("unable to create a memory layout for array elemets");
let (layout, _) = header_layout
.extend(elements_layout)
.expect("unable to create memory layout for array");
let mut array_header: NonNull<ArrayHeader> =
NonNull::new(unsafe { std::alloc::alloc_zeroed(layout).cast() })
.expect("error allocating memory for array");
let array = unsafe { array_header.as_mut() };
array.length = length;
array.capacity = length;
array_header
}
impl<O> GcRuntime for MarkSweep<O>
where
O: Observer<Event = Event>,
{
type Array = ArrayHandle;
fn alloc(&self, ty: &Type) -> GcPtr {
assert!(ty.is_concrete());
let object = alloc_obj(ty.clone());
let size = object.layout().size();
let handle = (object.as_ref().deref() as *const _ as RawGcPtr).into();
{
let mut objects = self.objects.write();
objects.insert(handle, object);
}
self.log_alloc(handle, size);
handle
}
fn alloc_array(&self, ty: &Type, n: usize) -> Self::Array {
let object = alloc_array(ty.clone(), n);
let size = object.layout().size();
let handle = (object.as_ref().deref() as *const _ as RawGcPtr).into();
{
let mut objects = self.objects.write();
objects.insert(handle, object);
}
self.log_alloc(handle, size);
ArrayHandle {
obj: unsafe { NonNull::new_unchecked(handle.into()) },
}
}
fn ptr_type(&self, handle: GcPtr) -> Type {
let _lock = self.objects.read();
let object_info: *const ObjectInfo = handle.into();
unsafe { (*object_info).ty.clone() }
}
fn array(&self, handle: GcPtr) -> Option<Self::Array> {
let _lock = self.objects.read();
let obj: NonNull<ObjectInfo> =
NonNull::new(handle.into()).expect("cannot have a null handle here");
unsafe {
if !obj.as_ref().ty.is_array() {
return None;
}
}
Some(ArrayHandle { obj })
}
fn root(&self, handle: GcPtr) {
let _lock = self.objects.write();
let object_info: *mut ObjectInfo = handle.into();
unsafe { (*object_info).roots += 1 };
}
fn unroot(&self, handle: GcPtr) {
let _lock = self.objects.write();
let object_info: *mut ObjectInfo = handle.into();
unsafe { (*object_info).roots -= 1 };
}
fn stats(&self) -> Stats {
self.stats.read().clone()
}
}
impl<O> MarkSweep<O>
where
O: Observer<Event = Event>,
{
pub fn collect(&self) -> bool {
self.observer.event(Event::Start);
let mut objects = self.objects.write();
let mut roots = objects
.iter()
.filter_map(|(_, obj)| {
if obj.roots > 0 {
Some(obj.as_ref().get_ref() as *const _ as *mut ObjectInfo)
} else {
None
}
})
.collect::<VecDeque<_>>();
while let Some(next) = roots.pop_front() {
let handle = (next as *const _ as RawGcPtr).into();
for reference in unsafe { (*next).ty.trace(handle) } {
let ref_ptr = objects
.get_mut(&reference)
.expect("found invalid reference");
if ref_ptr.color == Color::White {
let ptr = ref_ptr.as_ref().get_ref() as *const _ as *mut ObjectInfo;
unsafe { (*ptr).color = Color::Gray };
roots.push_back(ptr);
}
}
unsafe {
(*next).color = Color::Black;
}
}
let size_before = objects.len();
objects.retain(|h, obj| {
if obj.color == Color::Black {
unsafe {
obj.as_mut().get_unchecked_mut().color = Color::White;
}
true
} else {
let value_memory_layout = obj.layout();
unsafe { std::alloc::dealloc(obj.data.ptr.as_mut(), value_memory_layout) };
self.observer.event(Event::Deallocation(*h));
{
let mut stats = self.stats.write();
stats.allocated_memory -= value_memory_layout.size();
}
false
}
});
let size_after = objects.len();
self.observer.event(Event::End);
size_before != size_after
}
}
impl<O> MemoryMapper for MarkSweep<O>
where
O: Observer<Event = Event>,
{
fn map_memory(&self, mapping: Mapping) -> Vec<GcPtr> {
let mut objects = self.objects.write();
let deleted = objects
.iter()
.filter_map(|(ptr, object_info)| {
if mapping.deletions.contains(&object_info.ty) {
Some(*ptr)
} else {
None
}
})
.collect();
for (old_ty, new_ty) in mapping.identical {
for object_info in objects.values_mut() {
if object_info.ty == old_ty {
object_info.set(ObjectInfo {
data: ObjectInfoData {
ptr: unsafe { object_info.data.ptr },
},
roots: object_info.roots,
color: object_info.color,
ty: new_ty.clone(),
});
}
}
}
let mut new_allocations = Vec::new();
objects
.values_mut()
.filter(|object_info| object_info.ty.is_struct())
.for_each(|object_info| {
if let Some(conversion) = mapping.struct_mappings.get(&object_info.ty) {
let old_layout = object_info.ty.value_layout();
let src = unsafe { object_info.data.ptr };
let dest = unsafe {
NonNull::new_unchecked(std::alloc::alloc_zeroed(
conversion.new_ty.value_layout(),
))
};
map_struct(
&mut new_allocations,
&mapping.struct_mappings,
&conversion.field_mapping,
src,
dest,
);
unsafe { std::alloc::dealloc(src.as_ptr(), old_layout) };
object_info.set(ObjectInfo {
data: ObjectInfoData { ptr: dest },
roots: object_info.roots,
color: object_info.color,
ty: conversion.new_ty.clone(),
});
}
});
objects
.values_mut()
.filter(|object_info| object_info.ty.is_array())
.for_each(|object_info| {
let mut ty = object_info.ty.clone();
let mut stack = Vec::new();
while let Some(array) = ty.as_array() {
stack.push(ty.clone());
ty = array.element_type();
}
let old_element_ty = ty;
if let Some(conversion) = mapping.struct_mappings.get(&old_element_ty) {
let mut new_ty = conversion.new_ty.clone();
while stack.pop().is_some() {
new_ty = new_ty.array_type();
}
let new_element_ty = new_ty.as_array().unwrap().element_type();
if new_element_ty.is_struct() {
assert!(old_element_ty.is_struct());
let element_action =
resolve_struct_to_struct_edit(&old_element_ty, &new_element_ty, 0);
map_array(
&mut new_allocations,
&mapping.struct_mappings,
unsafe {
NonNull::new_unchecked(
object_info.as_mut().deref_mut() as *mut ObjectInfo
)
},
&element_action,
&new_ty,
);
} else {
object_info.as_mut().ty = conversion.new_ty.clone();
}
}
});
for object in new_allocations {
let size = object.layout().size();
let handle = (object.as_ref().deref() as *const _ as RawGcPtr).into();
objects.insert(handle, object);
self.log_alloc(handle, size);
}
return deleted;
unsafe fn get_field_ptr(struct_ptr: NonNull<u8>, offset: usize) -> NonNull<u8> {
let mut ptr = struct_ptr.as_ptr() as usize;
ptr += offset;
NonNull::new_unchecked(ptr as *mut u8)
}
fn map_array(
new_allocations: &mut Vec<Pin<Box<ObjectInfo>>>,
conversions: &HashMap<Type, StructMapping>,
mut src_object: NonNull<ObjectInfo>,
element_action: &Action,
new_ty: &Type,
) {
let src_array = ArrayHandle { obj: src_object };
let new_header = array_header(new_ty, src_array.length());
let mut dest_obj = ObjectInfo {
data: ObjectInfoData { array: new_header },
roots: unsafe { src_object.as_ref().roots },
color: unsafe { src_object.as_ref().color },
ty: new_ty.clone(),
};
let dest_array = ArrayHandle {
obj: unsafe { NonNull::new_unchecked(&mut dest_obj as *mut ObjectInfo) },
};
src_array
.elements()
.zip(dest_array.elements())
.for_each(|(src, dest)| {
map_type(
new_allocations,
conversions,
src,
dest,
element_action,
&new_ty.as_array().expect("Must be an array.").element_type(),
)
});
unsafe {
let src_obj = src_object.as_mut();
std::alloc::dealloc(src_obj.data.ptr.as_mut(), src_obj.layout());
*src_obj = dest_obj;
};
}
fn map_type(
new_allocations: &mut Vec<Pin<Box<ObjectInfo>>>,
conversions: &HashMap<Type, StructMapping>,
src: NonNull<u8>,
dest: NonNull<u8>,
action: &mapping::Action,
new_ty: &Type,
) {
match action {
mapping::Action::ArrayAlloc => {
let object = alloc_array(new_ty.clone(), 0);
let handle = (object.as_ref().deref() as *const _ as RawGcPtr).into();
let mut dest_handle = dest.cast::<GcPtr>();
unsafe { *dest_handle.as_mut() = handle };
new_allocations.push(object);
}
mapping::Action::ArrayFromValue {
element_action,
old_offset,
} => {
let mut object = alloc_array(new_ty.clone(), 1);
let array_handle = ArrayHandle {
obj: unsafe {
NonNull::new_unchecked(object.as_mut().deref_mut() as *mut ObjectInfo)
},
};
map_type(
new_allocations,
conversions,
unsafe { get_field_ptr(src, *old_offset) },
array_handle.data(),
element_action,
&new_ty.as_array().expect("Must be an array.").element_type(),
);
let handle = (object.as_ref().deref() as *const _ as RawGcPtr).into();
let mut dest_handle = dest.cast::<GcPtr>();
unsafe { *dest_handle.as_mut() = handle };
new_allocations.push(object);
}
mapping::Action::ArrayMap {
element_action,
old_offset,
} => {
let src_ptr = unsafe { get_field_ptr(src, *old_offset) };
let src_obj = unsafe { *src_ptr.cast::<NonNull<ObjectInfo>>().as_ref() };
map_array(
new_allocations,
conversions,
src_obj,
element_action,
new_ty,
);
unsafe {
std::ptr::copy_nonoverlapping(
src_ptr.as_ptr(),
dest.as_ptr(),
std::mem::size_of::<GcPtr>(),
)
};
}
mapping::Action::Cast { old_offset, old_ty } => {
if !cast::try_cast_from_to(
old_ty.clone(),
new_ty.clone(),
unsafe { get_field_ptr(src, *old_offset) },
dest,
) {
}
}
mapping::Action::Copy {
old_offset,
size: size_in_bytes,
} => {
unsafe {
std::ptr::copy_nonoverlapping(
get_field_ptr(src, *old_offset).as_ptr(),
dest.as_ptr(),
*size_in_bytes,
)
};
}
mapping::Action::ElementFromArray {
element_action,
old_offset,
} => {
let obj = unsafe {
*get_field_ptr(src, *old_offset)
.cast::<NonNull<ObjectInfo>>()
.as_ref()
};
let array_handle = ArrayHandle { obj };
if array_handle.header().length > 0 {
map_type(
new_allocations,
conversions,
array_handle.data(),
dest,
element_action,
new_ty,
)
} else {
}
}
mapping::Action::StructAlloc => {
let object = alloc_obj(new_ty.clone());
let handle = (object.as_ref().deref() as *const _ as RawGcPtr).into();
let mut dest_handle = dest.cast::<GcPtr>();
unsafe { *dest_handle.as_mut() = handle };
new_allocations.push(object);
}
mapping::Action::StructMapFromGc { old_ty, old_offset } => {
let conversion = conversions.get(old_ty).unwrap_or_else(|| {
panic!(
"If the struct changed, there must also be a conversion for type: {:#?}.",
old_ty,
)
});
let object = unsafe {
*get_field_ptr(src, *old_offset)
.cast::<NonNull<ObjectInfo>>()
.as_ref()
};
map_struct(
new_allocations,
conversions,
&conversion.field_mapping,
unsafe { object.as_ref().data.ptr },
dest,
);
}
mapping::Action::StructMapFromValue { old_ty, old_offset } => {
let object = alloc_obj(new_ty.clone());
let conversion = conversions.get(old_ty).unwrap_or_else(|| {
panic!(
"If the struct changed, there must also be a conversion for type: {:#?}.",
old_ty,
)
});
map_struct(
new_allocations,
conversions,
&conversion.field_mapping,
unsafe { get_field_ptr(src, *old_offset) },
unsafe { object.as_ref().data.ptr },
);
let handle = (object.as_ref().deref() as *const _ as RawGcPtr).into();
let mut dest_handle = dest.cast::<GcPtr>();
unsafe { *dest_handle.as_mut() = handle };
new_allocations.push(object);
}
mapping::Action::StructMapInPlace { old_ty, old_offset } => {
let conversion = conversions.get(old_ty).unwrap_or_else(|| {
panic!(
"If the struct changed, there must also be a conversion for type: {:#?}.",
old_ty,
)
});
map_struct(
new_allocations,
conversions,
&conversion.field_mapping,
unsafe { get_field_ptr(src, *old_offset) },
dest,
);
}
mapping::Action::ZeroInitialize => {
}
}
}
#[allow(clippy::mutable_key_type)]
fn map_struct(
new_allocations: &mut Vec<Pin<Box<ObjectInfo>>>,
conversions: &HashMap<Type, StructMapping>,
mapping: &[FieldMapping],
src: NonNull<u8>,
dest: NonNull<u8>,
) {
for FieldMapping {
new_ty,
new_offset,
action,
} in mapping.iter()
{
let field_dest = unsafe { get_field_ptr(dest, *new_offset) };
map_type(
new_allocations,
conversions,
src,
field_dest,
action,
new_ty,
);
}
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Color {
White,
Gray,
Black,
}
#[repr(C)]
struct ObjectInfo {
pub data: ObjectInfoData,
pub roots: u32,
pub color: Color,
pub ty: Type,
}
#[repr(C)]
union ObjectInfoData {
pub ptr: NonNull<u8>,
pub array: NonNull<ArrayHeader>,
}
unsafe impl Send for ObjectInfo {}
unsafe impl Sync for ObjectInfo {}
impl From<GcPtr> for *const ObjectInfo {
fn from(ptr: GcPtr) -> Self {
ptr.as_ptr() as Self
}
}
impl From<GcPtr> for *mut ObjectInfo {
fn from(ptr: GcPtr) -> Self {
ptr.as_ptr() as Self
}
}
impl From<*const ObjectInfo> for GcPtr {
fn from(info: *const ObjectInfo) -> Self {
(info as RawGcPtr).into()
}
}
impl From<*mut ObjectInfo> for GcPtr {
fn from(info: *mut ObjectInfo) -> Self {
(info as RawGcPtr).into()
}
}
impl From<NonNull<ObjectInfo>> for GcPtr {
fn from(info: NonNull<ObjectInfo>) -> Self {
(info.as_ptr() as RawGcPtr).into()
}
}
impl ObjectInfo {
pub fn layout(&self) -> Layout {
match self.ty.kind() {
TypeKind::Struct(_) | TypeKind::Primitive(_) | TypeKind::Pointer(_) => {
self.ty.value_layout()
}
TypeKind::Array(array) => {
let elem_count = unsafe { self.data.array.as_ref().capacity };
let elem_layout = repeat_layout(array.element_type().value_layout(), elem_count)
.expect("unable to determine layout of array elements");
let (layout, _) = Layout::new::<ArrayHeader>()
.extend(elem_layout)
.expect("unable to determine layout of array");
layout
}
}
}
}