search

dermesser / leveldb-rs

A reimplementation of LevelDB in Rust (no bindings).
Other
515 stars 60 forks source link

skipmap: the drop operation of skipmap may cause stackoverflow #20

Closed cfzjywxk closed 1 year ago

cfzjywxk commented 1 year ago

The drop operation of the skipmap may cause stack overflow as the tail recursion optimization could not work in this case, for example, writing many keys into the skipmap.

thread '<unknown>' has overflowed its stack
fatal runtime error: stack overflow
Aborted (core dumped)

From the stack

#0  0x00005555555c89ed in core::alloc::layout::Layout::max_size_for_align () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/alloc/layout.rs:93
#1  core::alloc::layout::Layout::array::inner (element_size=16, align=..., n=4) at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/alloc/layout.rs:438
#2  0x00005555555c1890 in core::alloc::layout::Layout::array () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/alloc/layout.rs:428
#3  alloc::raw_vec::RawVec<T,A>::current_memory (self=0x7ffff02127d0) at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/alloc/src/raw_vec.rs:247
#4  0x000055555558deac in <alloc::raw_vec::RawVec<T,A> as core::ops::drop::Drop>::drop (self=0x7ffff02127d0) at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/alloc/src/raw_vec.rs:478
#5  0x000055555558844b in core::ptr::drop_in_place<alloc::raw_vec::RawVec<core::option::Option<*mut rusty_leveldb::skipmap::Node>>> ()
    at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#6  0x0000555555587fe4 in core::ptr::drop_in_place<alloc::vec::Vec<core::option::Option<*mut rusty_leveldb::skipmap::Node>>> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#7  0x0000555555589407 in core::ptr::drop_in_place<rusty_leveldb::skipmap::Node> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#8  0x000055555558ae2a in core::ptr::drop_in_place<alloc::boxed::Box<rusty_leveldb::skipmap::Node>> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#9  0x0000555555587ca3 in core::ptr::drop_in_place<core::option::Option<alloc::boxed::Box<rusty_leveldb::skipmap::Node>>> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#10 0x000055555558943f in core::ptr::drop_in_place<rusty_leveldb::skipmap::Node> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#11 0x000055555558ae2a in core::ptr::drop_in_place<alloc::boxed::Box<rusty_leveldb::skipmap::Node>> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#12 0x0000555555587ca3 in core::ptr::drop_in_place<core::option::Option<alloc::boxed::Box<rusty_leveldb::skipmap::Node>>> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#13 0x000055555558943f in core::ptr::drop_in_place<rusty_leveldb::skipmap::Node> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#14 0x000055555558ae2a in core::ptr::drop_in_place<alloc::boxed::Box<rusty_leveldb::skipmap::Node>> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#15 0x0000555555587ca3 in core::ptr::drop_in_place<core::option::Option<alloc::boxed::Box<rusty_leveldb::skipmap::Node>>> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490
#16 0x000055555558943f in core::ptr::drop_in_place<rusty_leveldb::skipmap::Node> () at /rustc/69f9c33d71c871fc16ac445211281c6e7a340943/library/core/src/ptr/mod.rs:490

This seems to be a common issue easily encountered in the rust list implementation, a possible optimization is to implement the drop trait for the list explicitly to avoid function calls.