Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Recursive Drop causes stack overflow even for object trees #58068

Open
slaymaker1907 opened this issue Feb 2, 2019 · 2 comments

Comments

@slaymaker1907
Copy link

commented Feb 2, 2019

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)

@slaymaker1907 slaymaker1907 changed the title Drop Recursive Drop causes stack overflow even for object trees Feb 2, 2019

@steveklabnik

This comment has been minimized.

Copy link
Member

commented Feb 4, 2019

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

This comment has been minimized.

Copy link
Contributor

commented Feb 4, 2019

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants
You can’t perform that action at this time.