The limits of reference counting - Circular datastructures
Reference counting is quite powerful, but it also has its limits. The most well-known limitation is that it can't deal well with circular references. Circular references occur every time where two (or more) values hold references to each other, either directly or indirectly. Here is a small example of a circular reference:
use std::rc::Rc; use std::cell::RefCell; struct A { ref_to_b: Option<Rc<RefCell<B>>>, } impl Drop for A { fn drop(&mut self) { println!("A was cleaned up"); } } struct B { ref_to_a: Option<Rc<RefCell<A>>>, } impl Drop for B { fn drop(&mut self) { println!("B was cleaned up"); } } pub fn main() { let mut a = Rc::new(RefCell::new(A { ref_to_b: None, })); let mut b = Rc::new(RefCell::new(B { ref_to_a: Some(a.clone()) })); a.borrow_mut().ref_to_b = Some(b.clone()); }
It is a bit hard to set up circular references in Rust, but with Rc<RefCell<T>> we can get the job done and end up with two types A and B that point to instances of each other. This example produces a memory leak! Both references hold on to each other, so neither can be cleaned up before the other. This leaves the whole system in a state where a waits on b to release its shared reference to a, and b waits on a to release its shared reference on b. We can manually break this cycle:
pub fn main() { let mut a = Rc::new(RefCell::new(A { ref_to_b: None, })); let mut b = Rc::new(RefCell::new(B { ref_to_a: Some(a.clone()) })); a.borrow_mut().ref_to_b = Some(b.clone()); //We have to manually break the cycle! b.borrow_mut().ref_to_a = None; }
From an ownership-perspective, such a circular reference situation means: A owns B, but B owns A, so A is its own owner. So A only gets cleaned up once A gets cleaned up, which of course can't happen.
Besides manually breaking these cycles, the way to resolve this is by introducing a second reference counting type called a weak pointer. A weak pointer is like a shared pointer (e.g. Rc<T>), but it does not affect the reference count. As such, a weak pointer might be alive while the corresponding Rcs have all been destroyed. To prevent the weak pointer to point into invalid memory, it has dedicated methods that try to obtain a reference to the pointed-to value but can fail if the underlying value has already been destroyed.
Adding weak pointers to the equation requires some small changes to the implementation of the corresponding smart pointers. In particular, the reference count has to stay on the heap until either the last smart pointer or the last weak pointer goes out of scope, whichever comes latest. For that reason, two reference counts are typically used, one for the number of shared references (Rc<T> instances) pointing to the value, and one for the number of weak pointers pointing to the value:
#![allow(unused)] fn main() { /// An adjusted reference count block that supports weak pointers struct RefCountAndT<T> { strong_references: usize, weak_references: usize, obj: T, } }
With the adjusted reference count block (sometimes called a control block), we can implement a weak pointer:
#![allow(unused)] fn main() { struct WeakPtr<T> { control_block: *mut RefCountAndT<T>, } impl <T> WeakPtr<T> { pub fn to_rc(&self) -> Option<Rc<T>> { todo!() } } impl <T> Drop for WeakPtr<T> { fn drop(&mut self) { todo!() } } impl <T> Rc<T> { pub fn as_weak(&self) -> WeakPtr<T> { todo!() } } }
Dereferencing the weak pointer directly is not possible, so instead we provide a method to_rc(), which tries to convert the weak pointer into a shared pointer (Rc<T>). This method either returns the Rc<T>, if the weak pointer still points to valid memory, or it returns a special None value, indicating that the weak pointer is not valid anymore. We also implement Drop of course, as well as a method on Rc<T> to obtain a weak pointer from the Rc. Let's look at the Drop implementation first:
#![allow(unused)] fn main() { impl <T> Drop for WeakPtr<T> { fn drop(&mut self) { unsafe { let ref_count_and_t = self.control_block.as_mut().unwrap(); ref_count_and_t.weak_references -= 1; if ref_count_and_t.has_no_remaining_references() { let _as_box = Box::from_raw(self.control_block); } } } } }
Here we decrement the number of weak references and then check if the reference count for both strong and weak references is zero (using a convencience method has_no_remaining_references()). If that is the case, we delete the reference count block together with the value of T.
Let's do the conversion from WeakPtr<T> to Rc<T> next:
#![allow(unused)] fn main() { impl <T> WeakPtr<T> { pub fn to_rc(&self) -> Option<Rc<T>> { unsafe { let ref_count_and_t = self.control_block.as_mut().unwrap(); if ref_count_and_t.strong_references == 0 { return None; } ref_count_and_t.strong_references += 1; Some(Rc::<T> { ref_count_and_t, }) } } } }
Here we can look at the strong reference count to figure out if the conversion is valid. If there are no strong references, we can't convert to Rc<T>, but if there are, we increment the number of strong references and create a new Rc<T> directly from the control block. Writing Some(...) is just special syntax with the Option<T> type that indicates that there is a value, as opposed to None which indicates no value.
The conversion from Rc<T> to WeakPtr<T> is quite similar:
#![allow(unused)] fn main() { impl <T> Rc<T> { pub fn as_weak(&self) -> WeakPtr<T> { unsafe { let ref_count_and_t = self.ref_count_and_t.as_mut().unwrap(); ref_count_and_t.weak_references += 1; } WeakPtr::<T> { control_block: self.ref_count_and_t, } } } }
Here, we know that this conversion is always valid, so we don't need the Option<T> type. We increment the number of weak references and create a new WeakPtr<T> from the control block.
As a final step, we have to adjust the Drop implementation of Rc<T>, because it must not destroy the control block if there are still weak references. It must however destroy the instance of T as soon as the last Rc<T> goes out of scope. This is a bit tricky, because the instance is stored within the control block:
#![allow(unused)] fn main() { impl <T> Drop for Rc<T> { fn drop(&mut self) { unsafe { let ref_count_and_t = self.ref_count_and_t.as_mut().unwrap(); ref_count_and_t.strong_references -= 1; // If this was the last strong reference, we have to drop the value of `T`! This is the // guarantee of a smart pointer: Once the last smart pointer goes out of scope, the pointed-to // instance is destroyed. It's a bit tricky to do so, because our value is part of the control // block... if ref_count_and_t.has_no_strong_references() { // We have to use this 'drop_in_place' method, which effectively calls the destructor of the value // but does not deallocate its memory std::ptr::drop_in_place(&mut ref_count_and_t.obj); } // Only drop the control block if there are neither strong nor weak references! if ref_count_and_t.has_no_remaining_references() { let _as_box = Box::from_raw(self.ref_count_and_t); } } } } }
We can then use our WeakPtr<T> type like so:
pub fn main() { let strong1 = Rc::new(42); let weak1 = strong1.as_weak(); println!("Strong: {}", strong1.get()); println!("Weak: {}", weak1.to_rc().unwrap().get()); drop(strong1); println!("Weak pointer still valid after last Rc<T> dropped? {}", weak1.to_rc().is_some()); }
The Rust standard library implementation is called Weak<T> and is quite similar to our WeakPtr<T> type. We can use it to break cycles in circular reference situations:
use std::rc::Rc; use std::rc::Weak; use std::cell::RefCell; struct A { ref_to_b: Option<Weak<RefCell<B>>>, } impl Drop for A { fn drop(&mut self) { println!("A was cleaned up"); } } struct B { ref_to_a: Option<Rc<RefCell<A>>>, } impl Drop for B { fn drop(&mut self) { println!("B was cleaned up"); } } pub fn main() { let mut a = Rc::new(RefCell::new(A { ref_to_b: None, })); let mut b = Rc::new(RefCell::new(B { ref_to_a: Some(a.clone()) })); a.borrow_mut().ref_to_b = Some(Rc::downgrade(&b)); }
As a closing remark, similar types are also available in C++: std::shared_ptr<T> is the equivalent of Rc<T> and std::weak_ptr<T> is the equivalent of Weak<T>.