New crate: dumpster, a concurrent garbage collector

announcements
1

Hi, all!

Some time ago, I was frustrated with the state of garbage collection libraries for Rust. Every library out there is either slow, single-threaded, or requires conformance to a picky API. I've tried to fix that by making my own garbage collector library from scratch. The goal was to make something concurrent, fast, and easy to use.

I'll include an example below to show how it's used. I'm pretty happy with how it all came out!

use dumpster::{unsync::Gc, Collectable};

// Collectable types must implement `Collectable`.
// Otherwise, you can use `Gc` just like `Rc`.
#[derive(Collectable)]
struct Foo(RefCell<Option<Foo>>);

let foo = Gc::new(Foo(RefCell::new(None));

 // even though there's a cyclic reference, foo will still be cleaned up (eventually)
*foo.0.borrow_mut() = foo.clone();

drop(foo); // foo is not guaranteed to be cleaned up here

If you've noticed me asking some odd questions, this is why. Thank you all for providing lots of help.

You can download dumpster now from crates.io or just read my blog post explaining how it works.

4 Likes
2

While reading your blog post, in particular the section on dropping, I wondered what happens when you drop the actual contents of the Gc. If there are cycles then one might get access to the contents of another Gc that was dropped earlier, and it doesn't matter in which order you drop them because they are cyclic. I tried implementing this and I got a use after free bug:

use dumpster::unsync::Gc;
use dumpster::Collectable;
use std::cell::RefCell;

#[derive(Collectable)]
struct Bad {
    s: String,
    cycle: RefCell<Option<Gc<Bad>>>,
}

impl Drop for Bad {
    fn drop(&mut self) {
        // The second time this `print` is executed it will try to
        // print a `String` that has already been dropped.
        println!("{}", self.cycle.borrow().as_ref().unwrap().s)
    }
}

fn main() {
    let foo = Gc::new(Bad {
        s: "foo".to_string(),
        cycle: RefCell::new(None),
    });

    let bar = Gc::new(Bad {
        s: "bar".to_string(),
        cycle: RefCell::new(Some(foo.clone())),
    });

    *foo.cycle.borrow_mut() = Some(bar.clone());
}

The same bug happens with dumpster::sync::Gc when RefCell is replaced with Mutex.

2 Likes
3

Thanks for pointing that out. I'll change the behavior to panic on dereferencing while dropping references to already-dropped allocations in the newest patch.

2 Likes
4

More crates should turn on --generate-link-to-definition on docs.rs, like you did… it’s so useful!

Unrelated:

I’m mildly concerned about finding a comment talking about cases the number might be zero, on a field of NonZeroUsize type :sweat_smile: – might be out of date though – or maybe “the stored reference count” refers to something entirely different.

#[repr(C)]
/// The underlying heap allocation for a [`Gc`].
struct GcBox<T: Collectable + ?Sized> {
    /// The number of extant references to this garbage-collected data.
    /// If the stored reference count is zero, then this value is a "zombie" - in the process of
    /// being dropped - and should not be dropped again.
    ref_count: Cell<NonZeroUsize>,
    /// The stored value inside this garbage-collected box.
    value: T,
}

I haven’t looked at the blog post yet, by the way; will read that another day.

1 Like
5

Yep, that's a holdover from a previous revision. I'll need to patch that - thanks for the find.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.