Techniques or crates for reference counting mutually cyclic data?

The usual advice for dealing with cycles when relying in reference counting is to break the cycles with Weak. This works well for "back references" (e.g. parents in a tree) where there is a privileged participant in the cycle, which will always be referenced external to the cycle as long as the whole cycle should stay alive.

However this strategy doesn't work when you can't be sure which cycle participant(s) will have external references. In the simplest case, you have two objects, each referencing each other, and you want a reference to either to keep the pair alive.

Intuitively it seems I want something like Rc::new_cyclic, which supports allocating a dynamically sized group of objects which all share a common (strong) reference count, with weak counts for any references between themselves. (This would obviously require a custom type not std::rc::Rc.)

The data I'm interested in is immutable, so I don't need to worry about creating cycles after initialization. An even more powerful (precise) idea, at the expense of performance, would be to using a tracing trait to do a one-time cycle detection pass and find exactly all the cycles in some set of co-created objects.

I searched crates.io for something like this and was kind of shocked not to find something. Is everyone just using indices into an owning Vec and doing manual cleanup for this, or is it more obscure a problem than I think? Maybe there are other strategies I haven't thought of.

https://crates.io/crates/gcmodule or https://crates.io/crates/rcgc maybe?

1 Like

Hmm… sounds reasonable enough. In terms of API / use-case… Do you only need to add new values to the group during creation, or also at a later point?

On second thought… alright. Implementation-wise this sounds like one might just want multiple Rc to share their reference-count. Kind of like

// the “G” stands for “group(ed)”
struct GRc<T>(…);
impl<T> GRc<T> {
    fn new(x: T) -> Self { … }
    fn new_grouped<S>(x: T, other: &GRc<S>) -> Self { … }
    fn downgrade(&self) -> GWeak<T> { … }
}
impl<T> Clone for GRc<T> { … }
impl<T> Deref for GRc<T> {
    type Target = T;
    fn deref(&self) -> &T { … }
}

struct GWeak<T>(…);
impl<T> Clone for GWeak<T> { … }
impl<T> GWeak<T> {
    fn upgrade(&self) -> Option<GRc<T>> { … }
}

and new_grouped makes the new GRc shared the reference count(s) with the old one.

Writing a safe-Rust mock-implementation for this API reveals a few more restrictions:

  • since GRc<T> will also logically be able to own a lot of other GRc<S> of differing types, in particular drop them when the count goes to zero, lifetimes are problematic. We need to restrict GRc<T: 'static>; or alternatively / more generally, we could have a single lifetime bound that can be non-'static, like GRc<'a, T: 'a>.
  • if we think GArc<T>, too, that type could be sent to other threads and dropped there. Hence it would need to unconditionally require T: Send bounds

The safe reference-implementation could then look as follows.

(untested)

use std::cell::RefCell;
use std::rc::Rc;
use std::rc::Weak;

// trait like `Any`, but we don’t need the downcasting
trait Any_ {}
impl<T: 'static> Any_ for T {}

pub struct GRc<T>(Rc<T>, Rc<RefCell<Vec<Rc<dyn Any_>>>>);
impl<T> Clone for GRc<T> {
    fn clone(&self) -> Self {
        Self(self.0.clone(), self.1.clone())
    }
}
impl<T: 'static> GRc<T> {
    pub fn new(x: T) -> Self {
        let this = Rc::new(x);
        let group = Rc::new(RefCell::new(vec![Rc::clone(&this) as _]));
        Self(this, group)
    }
    pub fn new_grouped<S>(x: T, other: &GRc<S>) -> Self {
        let this = Rc::new(x);
        let group = Rc::clone(&other.1);
        group.borrow_mut().push(Rc::clone(&this) as _);
        Self(this, group)
    }
}
impl<T> GRc<T> {
    pub fn downgrade(&self) -> GWeak<T> {
        GWeak(Rc::downgrade(&self.0), Rc::downgrade(&self.1))
    }
}
impl<T> std::ops::Deref for GRc<T> {
    type Target = T;
    fn deref(&self) -> &T {
        &self.0
    }
}

pub struct GWeak<T>(Weak<T>, Weak<RefCell<Vec<Rc<dyn Any_>>>>);
impl<T> Clone for GWeak<T> {
    fn clone(&self) -> Self {
        Self(self.0.clone(), self.1.clone())
    }
}
impl<T> GWeak<T> {
    pub fn upgrade(&self) -> Option<GRc<T>> {
        Some(GRc(self.0.upgrade()?, self.1.upgrade()?))
    }
}

Edit: Looking at this API, it still doesn’t support building anything cyclic, without interior mutability. I’ll think about new_cyclic-equivalent API some time later.

1 Like

Alright… the API possible design space here seems absolutely huge. I’ll try something that should be useful enough, even if it’s not necessarily the “nicest” API

struct CyclicBuilder(…);
impl Clone for CyclicBuilder { … }

impl<T> GRc<T> {
    fn grouped_cyclic_builder(&self) -> CyclicBuilder { … }
    fn new_grouped_slot<S>(&self) -> (GSlot<S>, GWeak<S>) { … }
}

impl CyclicBuilder {
    fn new() -> Self { … }
    fn new_slot<T>(&self) -> (GSlot<T>, GWeak<T>) { … }
}

struct GSlot<T>(…);
impl<T> GSlot<T> {
    fn fill(self, x: T) -> GRc<T> { … }
}

For the reference-implementation, using OnceCell should be straightforward.

Here’s the updated code. Minor changes to add the OnceCells; the new stuff is at the bottom.

use std::cell::OnceCell;
use std::cell::RefCell;
use std::rc::Rc;
use std::rc::Weak;

// trait like `Any`, but we don’t need the downcasting
trait Any_ {}
impl<T: 'static> Any_ for T {}

pub struct GRc<T>(Rc<OnceCell<T>>, Rc<RefCell<Vec<Rc<dyn Any_>>>>);
impl<T> Clone for GRc<T> {
    fn clone(&self) -> Self {
        Self(self.0.clone(), self.1.clone())
    }
}
impl<T: 'static> GRc<T> {
    pub fn new(x: T) -> Self {
        let this = Rc::new(OnceCell::from(x));
        let group = Rc::new(RefCell::new(vec![Rc::clone(&this) as _]));
        Self(this, group)
    }
    pub fn new_grouped<S>(x: T, other: &GRc<S>) -> Self {
        let this = Rc::new(OnceCell::from(x));
        let group = Rc::clone(&other.1);
        group.borrow_mut().push(Rc::clone(&this) as _);
        Self(this, group)
    }
}
impl<T> GRc<T> {
    pub fn downgrade(&self) -> GWeak<T> {
        GWeak(Rc::downgrade(&self.0), Rc::downgrade(&self.1))
    }
}
impl<T> std::ops::Deref for GRc<T> {
    type Target = T;
    fn deref(&self) -> &T {
        self.0.get().unwrap()
    }
}

pub struct GWeak<T>(Weak<OnceCell<T>>, Weak<RefCell<Vec<Rc<dyn Any_>>>>);
impl<T> Clone for GWeak<T> {
    fn clone(&self) -> Self {
        Self(self.0.clone(), self.1.clone())
    }
}
impl<T> GWeak<T> {
    pub fn upgrade(&self) -> Option<GRc<T>> {
        let group = self.1.upgrade()?;
        let this = self.0.upgrade().unwrap();
        this.get()?;
        Some(GRc(this, group))
    }
}

#[derive(Clone)]
pub struct CyclicBuilder(Rc<RefCell<Vec<Rc<dyn Any_>>>>);

impl<T> GRc<T> {
    pub fn grouped_cyclic_builder(&self) -> CyclicBuilder {
        CyclicBuilder(Rc::clone(&self.1))
    }
    pub fn new_grouped_slot<S>(&self) -> (GSlot<S>, GWeak<S>) {
        self.grouped_cyclic_builder().new_slot()
    }
}

impl CyclicBuilder {
    pub fn new() -> Self {
        Self(Default::default())
    }
    pub fn new_slot<T>(&self) -> (GSlot<T>, GWeak<T>) {
        let slot = GSlot(Rc::new(OnceCell::new()), Rc::clone(&self.0));
        let weak = GWeak(Rc::downgrade(&slot.0), Rc::downgrade(&slot.1));
        (slot, weak)
    }
}

pub struct GSlot<T>(Rc<OnceCell<T>>, Rc<RefCell<Vec<Rc<dyn Any_>>>>);
impl<T: 'static> GSlot<T> {
    pub fn fill(self, x: T) -> GRc<T> {
        self.0.set(x).unwrap_or_else(|_| panic!("logic error"));
        self.1.borrow_mut().push(Rc::clone(&self.0) as _);
        GRc(self.0, self.1)
    }
}

Here’s a test-case

struct Foo {
    field: i32,
    bar: GWeak<Bar>,
}

struct Bar {
    flag: bool,
    foo: GWeak<Foo>,
}

fn foobar(field: i32, flag: bool) -> (GRc<Foo>, GRc<Bar>) {
    let b = CyclicBuilder::new();
    let (foo, foo_weak) = b.new_slot();
    let (bar, bar_weak) = b.new_slot();
    let foo = foo.fill(Foo {
        field,
        bar: bar_weak,
    });
    let bar = bar.fill(Bar {
        flag,
        foo: foo_weak,
    });
    (foo, bar)
}

impl Drop for Foo {
    fn drop(&mut self) {
        println!("dropped Foo {{ field: {} }}", self.field);
    }
}
impl Drop for Bar {
    fn drop(&mut self) {
        println!("dropped Bar {{ flag: {} }}", self.flag);
    }
}

fn main() {
    let (f1, b1) = foobar(42, false);
    println!("b1 flag through f1: {}", f1.bar.upgrade().unwrap().flag);
    println!("f1 flag through b1: {}", b1.foo.upgrade().unwrap().field);
    println!("f1 drop");
    drop(f1);
    println!("f1 flag through b1: {}", b1.foo.upgrade().unwrap().field);
    println!("b1 drop");
    drop(b1);

    let (f2, b2) = foobar(1337, true);
    println!("b2 drop");
    drop(b2);
    println!("f2 drop");
    drop(f2);
}
b1 flag through f1: false
f1 flag through b1: 42
f1 drop
f1 flag through b1: 42
b1 drop
dropped Foo { field: 42 }
dropped Bar { flag: false }
b2 drop
f2 drop
dropped Foo { field: 1337 }
dropped Bar { flag: true }

Rust Playground

1 Like

I'm in the final phases of building my own concurrent garbage collection library with an easy-to-use API, planning on publishing hopefully later this week. As part of that, I ended up testing and benchmarking a number of different GC crates.

gcmodule may or may not work for this application, but it crashed on my benchmark due to segfaults and stack overflows, probably because I asked it to clean up literally millions of allocations. rcgc's API requires referring to a single "master" object which makes it harder to integrate into an API.

As far as drop-in replacement GC libraries go, the fastest single-threaded one is bacon-rajan-cc. However, users must manually trigger cleanup operations (cleanup doesn't happen automatically in the background).

There are no concurrent GCs out there with an drop-in-replacement API for Arc (at least, that I know of, and pending when I get around to publishing my own library) except for shredder, which is good but also extremely slow (think 70x slower than bacon-rajan-cc and 100x slower than Arc).

Peeking at the API of sync::Gc, you might be missing some restriction to T: Send? I assume the thread where Gc::new is called may be different from the one where the T is dropped. A typical Sync + !Send type is MutexGuard, which even implements your Collectable trait. Haven’t tested anything further, just glanced at the generated rustdoc, but feel free to take a look whether or not there’s a problem :wink:

Correct me if I'm wrong, but it should be acceptable to store a Sync type in a shared allocation. In my implementation, a Gc<T> can only be coerced to &T (and the internal value can never be moved out of the allocation), and &MutexGuard is perfectly fine to share between threads, so I think it all works out. I don't expose any functions like Arc::into_inner which might result in T being sent across threads.

Just after writing that, I found a counterexample which proves why everything has to be Send, due to my ancient foe, replace.

struct Foo; // assume it is !Send

impl std::ops::Drop for Foo {
    fn drop(&mut self) {
        let _foo = std::mem::replace(self, Foo);
    }
}

If Foo were stored in a Gc, we would be able to remove it from behind the reference in its Drop implementation, yielding undefined behavior. Thank you!

1 Like

Or, as mentioned MutexGuard, whose !Send implementation is motivated by the fact that the OS mutex of some platforms requires the unlocking thread to the same as the one that locked the mutex - so it's all about Drop in that case :wink:

That being said, it's rather the exception. Most Sync types are also Send, so at least the additional Send bound is not much of an additional restriction for the users.