How to prevent a stack overflow from a recursive deallocation when using Rc in Rust?

Question

Is there a good way to prevent a stack overflow from a recursive deallocation when using Rc in Rust? In my case, I have a kind of graph that can grow to be pretty large. When part of the graph is no longer used, I expect it to be freed. However, that can create a cascade of deallocations that eventually overflow the stack. As an example, consider the code:

// This is a test to see how long of a DAG that we can make before we have a 
// problem freeing the graph due to a stack overflow from the memory frees.

// External libraries
use std::rc::Rc;              

// Graph that contains integers
struct MyGraph {    

    // Random data
    data : u32,               

    // Previous link                                  
    previous : Option <Rc <MyGraph>>,            
} 

// Show that we're freeing    
impl Drop for MyGraph {
    fn drop(&mut self) {
        println!("{}",self.data);
    }   
}   


// Create a long graph of things
fn main() {

    // Set the size of the problem.  This should crash things.
    let m:u32 = 100000;      

    // Create the first node
    let mut node = Rc::new(MyGraph {                           
        data : 0,                              
        previous : None});

    // Add a bunch of additional nodes
    for i in 1..m {             
        node = Rc::new(MyGraph {            
            data : i,                                   
            previous : Some(node.clone())});            
    }

    // Zip through the nodes to make sure we created the graph
    {   
        let mut node_p = node.clone();           
        while node_p.previous.is_some() {
            print!("{} ",node_p.data);    
            node_p = node_p.previous.as_ref().unwrap().clone()
        }
    }
    println!("");

    // Free the memory in the graph by constructing a new single element
    node = Rc::new(MyGraph {                
        data : 0,    
        previous : None});    

    // Denote we finished  
    println!("Fin");
}   

It may depend on the underlying computer, but on mine it eventually crashes with

52418
52417

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Aborted

If the size of the graph was smaller, say 3, the program would return

2 1 
2
1
0
Fin
0

Now, this isn't unexpected. The exact same thing happens in C++. In C++, I can work around this problem by implementing my own kind of reference counting that deallocates iteratively. My question is whether there's a better option in Rust for handling these deallocations.

Answer 1

You can prevent the stack overflow by switching from recursive deallocation to iterative deallocation. In your concrete example, use this Drop impl instead:

// Show that we're freeing
impl Drop for MyGraph {
    fn drop(&mut self) {
        let mut prev = self.previous.take();

        while let Some(rc) = prev {
            if let Ok(mut graph) = Rc::try_unwrap(rc) {
                prev = graph.previous.take();
            } else {
                break;
            }
        }
    }
}

That is, drop every previous graph that can be freed (only has one reference) but before dropping it set its previous field to None (that's what previous.take() does) and proceed to drop the one returned by previous.take().

I recommend you to take a look to the tutorial Learn Rust With Entirely Too Many Linked Lists if you haven't, it touches the common hazards with linked structures including this one of recursive deallocation.