Cycle via Rc<RefCell<_>> is not dropped?


#1

I thought it was not possible in safe Rust code to create a memory leak, but what about the following code:

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

struct Node {
    next: Option<Rc<RefCell<Node>>>
}

impl Drop for Node {
    fn drop(&mut self) {
        println!("Dropping!");
    }
}

fn main() {
    let first = Rc::new(RefCell::new(Node { next: None }));
    let second = Rc::new(RefCell::new(Node { next: Some(first.clone()) }));

    first.borrow_mut().next = Some(second.clone());
}

If you run this code, there is no output.

If you comment out the last line of the main function, the output is:

Dropping!
Dropping!

#2

Yeah circular references are allowed, and are not freed. There was a bug opened and closed about it.

The compiler will determine when an object is no longer referable and free it but circular references are left to the programmer to deal with.


#3

Rust’s memory safety guarantees mean no dangling pointers, no writes to memory you don’t hold exclusive access to.

Memory leaks are not in this category. They are in fact much harder to define; for example, if you spawn a thread, give it ownership of a set of objects, and the thread spins indefinitely (uselessly?), is that a memory leak?

From the perspective of rust’s type system, putting a value into a reference cycle and then disposing of the original handle of it looks the same as passing away a value to a thread that you never again join.

Rust does not either protect you from the out of memory errors that are mentioned in the article; you can have a program crash due to stack exhaustion or out of memory errors.


#4

It is very well possible to leak memory in safe Rust. There is a (now) safe function that does just that. Rust simply tries to prevent leaks on a best-effort basis: all stdlib datastructures free their allocations when dropped, and types wrapping system primitives like File and Mutex release their resources on-drop as well. Third-party types are also encouraged to use Drop to cleanup resources.

However, types that rely on their destructors being called to prevent undefined behavior, like the old scoped threads API, are inherently unsound as it is unfeasible to eliminate all routes for leaking values in safe Rust. It was just easier to make mem::forget() safe and discourage people from relying on destructors being run for safety or sanity purposes.

If you want to create cycles with Rc without it leaking, you’ll want to use std::rc::Weak:


use std::rc::{Rc, Weak};

fn main() {
    let strong = Rc::new("hello");
    // These methods are static to avoid interfering with calling similarly named methods on the contained object
    let weak = Rc::downgrade(&strong);
    // `Weak` can't be dereferenced, so we have to get an `Rc` back from it, which could fail if there are no more strong references.
    let strong2 = weak.upgrade().unwrap();
}

That way, when you go to store an Rc to your head node in your tail node, use Weak instead so the cycle doesn’t prevent the datastructure from being collected.


#5

Thank you for your detailed answers.

What would be the best practice to model such a circular linked list? Every Node is the same, so I can not use Weak<_> somewhere.


Another similar scenario: I have a Round that owns Actions. The Actions should be able to point at each other.

pub struct Round<'b> {
    pub actions: Vec<Action<'b>>
}

pub struct Action<'a> {
    pub dependency: Option<&'a Action<'a>>
}

fn main() {
    let mut round = Round { actions: Vec::new() };

    round.actions.push(Action { dependency: None });
    round.actions.push(Action { dependency: None });

    round.actions[0].dependency = Some(&round.actions[1]); // error: cannot borrow `round.actions` as mutable because it is also borrowed as immutable
}

I assume that this is not possible without using Rc<_>?


#6

I’m guessing what you would want to do is make the object that contains the circular linked list “manually” destroy each object in the list when it is destroyed.

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

struct Node {
    next: Option<Rc<RefCell<Node>>>,
}

struct List {
    head: Option<Rc<RefCell<Node>>>,
}

impl Drop for List {
    fn drop(&mut self) {
        let mut current = self.head.take();

        while let Some(elem) = current {
            current = elem.into_inner().next.take();
        }
    }
}

I think something like this would work.


#7

To answer your first question, you probably want your next value of Node to be an enum, maybe combined with Option::None to make matching easier:

use std::cell::RefCell;
use std::rc::{Rc, Weak};

enum Next {
    Head(Weak<RefCell<Node>>),
    Node(Rc<RefCell<Node>>),
    End,
}

impl Next {
    fn to_rc(&self) -> Option<Rc<RefCell<Node>>> {
        use self::Next::*;
         match *self {
             Head(ref weak) => weak.upgrade(),
             Node(ref next) => Some(next.clone()),
             End => None,
         }
    }
}   

struct Node {
    next: Next,
}

impl Drop for Node {
    fn drop(&mut self) {
        println!("Dropping!");
    }
}

fn main() {
    let first = Rc::new(RefCell::new(Node { next: Next::End }));
    let second = Rc::new(RefCell::new(Node { next: Next::Head(Rc::downgrade(&first)) }));

    first.borrow_mut().next = Next::Node(second.clone());
}

This prints the expected output:

Dropping!
Dropping!

For your second question, Rust doesn’t support internal references like this because they can be invalidated. If you push to Round::actions and it ends up reallocating, the references of every dependency field of every Action will end up as dangling pointers, which cause undefined behavior when dereferenced. Rust recognizes this and refuses to compile the program.

What you can do instead is change Action::dependency to be an index into Round::actions, so storing and fetching the dependency is memory-safe. Naturally, you’ll have to make sure these indices stay correct, but it’s no more difficult than ensuring all pointers remain valid if you store references instead. On the upside, you don’t have to update them when you add an element to the end like you would have to with pointers; you only have to update them if you insert or remove an element in the middle (shifting the elements to the right of it).

Rc will also work, but it’s extra indirection and requires RefCell to mutate Action if you need that.