Recursive Drop causes stack overflow even for object trees

[slaymaker1907]

The issue seems to be that the way Drop is currently compiled is fatally flawed for recursive data structures.

The following code doesn't seem to have an fundamental issues that would cause it to fail, but it ends up causing a stack overflow, even for the version which uses Box instead of CustomBox.

use std::alloc::{alloc, dealloc, Layout, handle_alloc_error};
use std::ptr::{NonNull, drop_in_place, write};
use std::mem::drop;
use std::borrow::Borrow;

struct CustomBox<T> {
    wrapped: NonNull<T>
}

impl<T> CustomBox<T> {
    fn new(data: T) -> CustomBox<T> {
        let wrapped = unsafe {
            let layout = Layout::new::<T>();
            let memory = alloc(layout);
            if memory.is_null() {
                handle_alloc_error(layout);
            }
            let result = NonNull::new_unchecked(memory as *mut T);
            write(result.as_ptr(), data);
            result
        };
        CustomBox {
            wrapped
        }
    }

    fn borrow(&self) -> &T {
        unsafe {
            self.wrapped.as_ref()
        }
    }
}

impl<T> Drop for CustomBox<T> {
    fn drop(&mut self) {
        let layout = Layout::new::<T>();
        unsafe {
            drop_in_place(self.wrapped.as_ptr());
            dealloc(self.wrapped.as_ptr() as *mut u8, layout);
        }
    }
}

macro_rules! create_linked_list {
    ($name:ident, $box_type:ident) => {
        struct $name {
            data: u32,
            next: Option<$box_type<$name>>
        }

        impl $name {
            fn new(size: usize) -> Option<$box_type<$name>> {
                let mut result: Option<$box_type<$name>> = None;
                for i in 0..size {
                    let new_node = $box_type::new($name {
                        data: i as u32,
                        next: result.take()
                    });

                    result = Some(new_node);
                }

                result
            }

            fn sum(mut list: &Option<$box_type<$name>>) -> u64 {
                let mut result = 0;
                while let Some(node) = list.as_ref() {
                    let node_ref: &$name = node.borrow();
                    result += node_ref.data as u64;
                    list = &node_ref.next;
                }
                result
            }
        }
    };
}

create_linked_list!(LinkedList, CustomBox);
create_linked_list!(BoxLinkedList, Box);

fn main() {
    let list = BoxLinkedList::new(10_000_000);
    println!("{}", BoxLinkedList::sum(&list));
    println!("Trying to drop normal Box");
    drop(list);
    println!("Dropped successfully.");

    let list = LinkedList::new(10_000_000);
    println!("{}", LinkedList::sum(&list));
    println!("Trying to drop CustomBox");
    drop(list);
    println!("Dropped successfully.");
}

I expected to see this happen: It should have run this code sample and printed each println.

Instead, this happened: It crashes when drop(list) is called the first time.

Currently, the LinkedList implementation in std::collections seems to explicitly deal with deallocating nodes without recursion so it is not affected.

I'm not sure if this was an intentional design decision or not, but if it it was intentional, it should be better documented, there isn't much indication in the official docs that dropping is actually done as non-tail call recursive functions.

One way to potentially fix this could be to make a lazy_drop_in_place macro which has the same signature as drop_in_place, except that instead of immediately dropping that item, it instead saves these pointers at the top of the stack (which is why this should be a macro instead of a function) in a static sized buffer.

This API would not allow variable size deallocations, but it would solve the problem since then then the compiler could avoid recursion for things like linked lists.

Meta

rustc --version --verbose:

rustc 1.33.0-nightly (e2f221c75 2019-01-15)
binary: rustc
commit-hash: e2f221c75932de7a29845c8d6f1f73536ad00c41
commit-date: 2019-01-15
host: x86_64-pc-windows-msvc
release: 1.33.0-nightly
LLVM version: 8.0

Backtrace:

   Compiling large-stack-drop v0.1.0 (C:\codedump\alloc-serialize\large-stack-drop)
    Finished release [optimized] target(s) in 0.43s
     Running `target\release\large-stack-drop.exe`
49999995000000
Trying to drop normal Box

thread 'main' has overflowed its stack
error: process didn't exit successfully: `target\release\large-stack-drop.exe` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)

[steveklabnik]

As far as I know, this is intended an intentional, and changes here would require an RFC. I'll let @rust-lang/lang decide that though.

[withoutboats]

worth clarifying this in the reference or API docs as to how drop glue works. we dont have any kind of TCO.

[497e0bdf29873]

I am also currently getting in debug mode a stack overflow in core::ptr::drop_in_place (the stack trace shows mod.rs:487 and rc.rs:1559). I am not using any custom recursive data structures, just an Rc tree. There's no problem in release mode.

This is on nightly, I cannot test on stable, as my code requires several nightly features.

[497e0bdf29873]

To add to my case, this one crashes even on stable (stable-aarch64-apple-darwin) without optimisations:

use std::rc::Rc;

enum Foo {
    Branch(Rc<Foo>),
    Leaf(usize),
}

fn deeper(p : Foo) -> Foo {
    Foo::Branch(Rc::new(p))
}

fn main() {
    let mut p = Foo::Leaf(1);

    for _ in 0..100000 {
        p = deeper(p)
    }
}

$  rustup run stable rustc -O rccrash.rs 
$ ./rccrash 
$  rustup run stable rustc  rccrash.rs 
$ ./rccrash 

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
Abort trap: 6

[androxylo]

Do you know any simple fix of the code in comment 497e0bdf29873 right above to avoid recursive delete, without fixing the Rust itself?

[slaymaker1907]

@androxylo you could have a custom drop implementation and a wrapper, it's just kind of clunky. In the drop implementation for the wrapper, iterate through the linked list in a loop and avoid recursive drops by replacing the Branch(Rc) reference with Leaf(usize). Basically, pretend the inner part is an Option instead of Foo and use Option::take to avoid recursive drops.

It seems like there should be a warning or something through clippy/the compiler when mutually recursive drops are detected.

[497e0bdf29873]

@slaymaker1907 I wonder how practical it would be to do at least a derive-type macro for automatic implementation of recursive drop. It will need to be slightly more complicated than the simple replacement above for more complex structures. My current implementation for a proper tree with multiple branches additionally uses a Vec “drop buffer”. That should take care of any structure—you just need to be slightly careful with what elements of the structure to insert there—but perhaps can be optimised somewhat. Having to do allocations during a drop is not exactly ideal!

[slaymaker1907]

@497e0bdf29873 it would be very difficult to make an abstract pattern out of this. As you can see, it relies on having a cheap version to copy that is not recursive.

use std::rc::Rc;
use std::mem;

pub enum InnerFoo {
    Branch(Rc<InnerFoo>),
    Leaf(usize),
}

pub struct Foo(InnerFoo);

impl Drop for Foo {
    fn drop(&mut self) {
        let mut current = InnerFoo::Leaf(0);
        mem::swap(&mut self.0, &mut current);
        loop {
            if let InnerFoo::Branch(mut next) = current {
                current = InnerFoo::Leaf(0);
                mem::swap(&mut current, Rc::get_mut(&mut next).unwrap());
            } else {
                break;
            }
        }
    }
}

pub fn deeper(mut p : Foo) -> Foo {
    let mut current = InnerFoo::Leaf(0);
    mem::swap(&mut p.0, &mut current);
    p.0 = InnerFoo::Branch(Rc::new(current));
    return p;
}

pub fn main() {
    let mut p = Foo(InnerFoo::Leaf(1));

    for _ in 0..100000 {
        p = deeper(p)
    }
}

[497e0bdf29873]

@slaymaker I would imagine that it should be possible to “deconstruct” a struct into a corresponding n-tuple and then lift each element of the n-tuple into an Option that can be easily swapped. Serde and all do analysis and deconstruction of structs all the time, so that should not be an issue. The trickier part is the intelligence to decide which elements actually need this treatment, and whether a “drop queue” is needed to deal with structures with a higher branching factor.

Addendum: this probably wouldn't even need the Option or the tuple. After you pattern match the struct in a macro-constructed Drop implementation, you can drop the elements individually. The real issue is dealing with branching.

Oh wait, we only get &mut self instead of self in Drop. That really complicates things. On the other hand, in most cases the troublesome elements should be Boxes, Rcs, etc., that could theoretically be turned into null pointers with appropriate support. But perhaps the most appropriate approach would be to add to the Drop trait the “real” dropper (analogous to drop()) that gets to consume self. Then it should be possible to just pattern match the struct in a macro-constructed implementation.