Managing the lifetimes of garbage-collected objects

Garbage CollectionRustAllocationLifetime

Garbage Collection Problem Overview


I am making a simplistic mark-and-compact garbage collector. Without going too much into details, the API it exposes is like this:

/// Describes the internal structure of a managed object.
pub struct Tag { ... }

/// An unmanaged pointer to a managed object.
pub type Pointer = *mut usize;

/// Mapping from old to new locations.
pub type Adjust = BTreeMap<usize, Pointer>;

/// Mark this object and anything it points to as non-garbage.
pub unsafe fn survive(ptr: Pointer);

pub struct Heap { ... }

impl Heap {
    pub fn new() -> Heap;
    
    // Allocate an object with the specified structure.
    pub fn allocate(&mut self, tag: Tag) -> Pointer;
    
    /// Move all live objects from `heap` into `self`.
    pub unsafe fn reallocate(&mut self, heap: Heap) -> Adjust;
}

This API is obviously fundamentally unsafe. I would like to rework the API (without changing the internals, which are just fine!) to account for the following facts:

  1. All Pointers to (objects allocated in) a Heap become invalid when the heap is merged into another heap.

  2. merge returns an Adjust whose values are valid Pointers to (objects allocated in) self.

I have the following tentative solution:

// Replaces Pointer.
#[derive(Copy, Clone)]
pub struct Object<'a> {
    ptr: *mut AtomicUsize,
    mark: PhantomData<&'a usize>
}

impl<'a> Object<'a> {
    pub fn survive(self); // Now supposed to be perfectly safe!
}

pub type Adjust<'a> = BTreeMap<usize, Object<'a>>;

pub struct Heap { ... }
pub struct Allocator<'a> { ... }

impl Heap {
    fn allocator(&'a self) -> Allocator<'a>;
    // The following doesn't work:
    // 
    //  fn allocate(&'a mut self) -> Object<'a>;
    //  fn reallocate(&'a mut self, heap: Heap) -> Adjust<'a>;
    // 
    // Because it doesn't allow the user to allocate more
    // than one `Object` at a time (!) in a `Heap`.
}

impl<'a> Allocator<'a> {
    // Note that the resulting `Object`s are tied to the `Heap`,
    // but not to the allocator itself.
    fn allocate(&mut self, tag: Tag) -> Object<'a>;
    fn reallocate(&mut self, heap: Heap) -> Adjust<'a>;
}

Is this design correct? If not, what needs to be changed?

Garbage Collection Solutions


Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionpyonView Question on Stackoverflow