Stack overflow with large lists

[tkriik]

I was playing around this library when I encountered a stack overflow when allocating large lists (>100k elements).

Here is the diff in list tests which reproduces the error:

diff --git a/src/list/test.rs b/src/list/test.rs
index 7cbbcc0..a6315d5 100644
--- a/src/list/test.rs
+++ b/src/list/test.rs
@@ -10,7 +10,7 @@ mod iter {
 
     #[test]
     fn test_iter() {
-        let limit = 1024;
+        let limit = 1024 * 1024;
         let mut list = List::new();
         let mut left = limit;

With the modification above, we get:

$ cargo test list::test::iter::test_iter
    Finished dev [unoptimized + debuginfo] target(s) in 0.06s                                                       
     Running target/debug/deps/rpds-eca271399800c9ae

running 2 tests
test list::test::iter::test_iter_size_hint ... ok

thread 'list::test::iter::test_iter' has overflowed its stack
fatal runtime error: stack overflow

Some GDB backtrace output (continues very long):

#0  0x00005555557a1c31 in <core::ptr::NonNull<T>>::as_ref (self=0x7fffeb111090)
    at /checkout/src/libcore/ptr.rs:2915
#1  0x0000555555759343 in <alloc::sync::Arc<T>>::inner (self=0x7fffeb111090) at /checkout/src/liballoc/sync.rs:520
#2  0x000055555576fc63 in <alloc::sync::Arc<T> as core::ops::drop::Drop>::drop (self=0x7fffeb111090)
    at /checkout/src/liballoc/sync.rs:946
#3  0x00005555556071ce in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#4  0x0000555555609311 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#5  0x00005555557619d9 in <alloc::sync::Arc<T>>::drop_slow (self=0x7fffeb1110d8)
    at /checkout/src/liballoc/sync.rs:528
#6  0x0000555555770b28 in <alloc::sync::Arc<T> as core::ops::drop::Drop>::drop (self=0x7fffeb1110d8)
    at /checkout/src/liballoc/sync.rs:981
#7  0x00005555556040ce in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#8  0x0000555555607e2d in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#9  0x0000555555609346 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#10 0x00005555557619d9 in <alloc::sync::Arc<T>>::drop_slow (self=0x7fffeb111118)
    at /checkout/src/liballoc/sync.rs:528
#11 0x0000555555770b28 in <alloc::sync::Arc<T> as core::ops::drop::Drop>::drop (self=0x7fffeb111118)
    at /checkout/src/liballoc/sync.rs:981
#12 0x00005555556040ce in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#13 0x0000555555607e2d in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#14 0x0000555555609346 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#15 0x00005555557619d9 in <alloc::sync::Arc<T>>::drop_slow (self=0x7fffeb111158)
    at /checkout/src/liballoc/sync.rs:528
#16 0x0000555555770b28 in <alloc::sync::Arc<T> as core::ops::drop::Drop>::drop (self=0x7fffeb111158)
    at /checkout/src/liballoc/sync.rs:981
#17 0x00005555556040ce in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#18 0x0000555555607e2d in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#19 0x0000555555609346 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#20 0x00005555557619d9 in <alloc::sync::Arc<T>>::drop_slow (self=0x7fffeb111198)
    at /checkout/src/liballoc/sync.rs:528
#21 0x0000555555770b28 in <alloc::sync::Arc<T> as core::ops::drop::Drop>::drop (self=0x7fffeb111198)
    at /checkout/src/liballoc/sync.rs:981
#22 0x00005555556040ce in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#23 0x0000555555607e2d in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#24 0x0000555555609346 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#25 0x00005555557619d9 in <alloc::sync::Arc<T>>::drop_slow (self=0x7fffeb1111d8)
    at /checkout/src/liballoc/sync.rs:528
#26 0x0000555555770b28 in <alloc::sync::Arc<T> as core::ops::drop::Drop>::drop (self=0x7fffeb1111d8)
    at /checkout/src/liballoc/sync.rs:981
#27 0x00005555556040ce in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#28 0x0000555555607e2d in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#29 0x0000555555609346 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#30 0x00005555557619d9 in <alloc::sync::Arc<T>>::drop_slow (self=0x7fffeb111218)
    at /checkout/src/liballoc/sync.rs:528
#31 0x0000555555770b28 in <alloc::sync::Arc<T> as core::ops::drop::Drop>::drop (self=0x7fffeb111218)
    at /checkout/src/liballoc/sync.rs:981
#32 0x00005555556040ce in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#33 0x0000555555607e2d in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#34 0x0000555555609346 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#35 0x00005555557619d9 in <alloc::sync::Arc<T>>::drop_slow (self=0x7fffeb111258)
    at /checkout/src/liballoc/sync.rs:528
#36 0x0000555555770b28 in <alloc::sync::Arc<T> as core::ops::drop::Drop>::drop (self=0x7fffeb111258)
    at /checkout/src/liballoc/sync.rs:981
#37 0x00005555556040ce in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#38 0x0000555555607e2d in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#39 0x0000555555609346 in core::ptr::drop_in_place () at /checkout/src/libcore/ptr.rs:59
#40 0x00005555557619d9 in <alloc::sync::Arc<T>>::drop_slow (self=0x7fffeb111298)
    at /checkout/src/liballoc/sync.rs:528
...

It seems that the internal routines in Rust for managing Arc references work recursively, in which case this might not be easy to fix.

[orium]

This is due to the way rust drops things that are not longer used, since there is a big chain of Arc links the recursive calls can stack overflow. See rust-lang/rfcs#686.

Unfortunately there is not much we can do.