323

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?

isekaijin
  • 19,076
  • 18
  • 85
  • 153
  • 78
    this is quite a bit wider than the usual scope of SO questions. I would suggest you try [users.rust-lang.org](https://users.rust-lang.org/) instead – Paolo Falabella May 20 '15 at 09:54
  • 37
    Out of interest, why would you self manage garbage collection? It seems like your fighting the way Rust is built to add a feature that isn't needed. Is it just a coding exercise? If you wanted to keep a note of stuff on the heap, a Vector of Boxes would be much safer wouldn't it? – DanielM Apr 13 '18 at 11:09
  • 29
    @DanielM: This is in order to implement a runtime system for another language. This language, unlike Rust, has a tendency to make lots of very small allocations, which will quickly fragment the heap if a mark-compact collector is not used. – isekaijin Apr 13 '18 at 16:20
  • The interface itself doesn't look unsafe, are you sure you can't wrap just the unsafe lines in an unsafe block? – DanielM Apr 15 '18 at 12:42
  • 35
    An interesting read for you might be withoutboats' blog series on the garbage collector he wrote in rust. Here's a link to the frist one. https://boats.gitlab.io/blog/post/shifgrethor-i/ – Russell Greene Dec 17 '18 at 20:46
  • @pyon why bust your back to make it safe when it's going to be used from a runtime? (which is its own kind of safe interface) If you do give up on safety, why switch to C, even then? – mako May 08 '19 at 23:29
  • 14
    @mako: Runtimes are safe from the point of view of the user, in the sense that “if it breaks, it's someone else's problem”. But they are unsafe from the point of view of the implementor. – isekaijin Jun 07 '19 at 10:59
  • 2
    Also you might want to check out Google's malloc() just made public -- high performance heap management through segregation. – David G. Pickett Jun 04 '20 at 19:45
  • I believe this question may work better on [programmers.se] or [codereview.se], due to how questions about code design tend to draw in opinionated answers, which are not allowed here. See https://meta.stackoverflow.com/questions/256663/is-a-question-about-design-patterns-too-opinionated-for-stack-overflow – spicy.dll Oct 14 '21 at 21:34
  • @pyon an interesting topic for you. `Lifetime constraints to model scoped garbage collection` – Nadeem Taj Oct 24 '21 at 18:50
  • 5
    I think the problem here is that you're asking "is this design correct?" without really having an objective definition of correct for us to operate off of. This is a large problem and SO is made for smaller problems. – Alex W Nov 07 '21 at 03:19

0 Answers0