crossbeam icon indicating copy to clipboard operation
crossbeam copied to clipboard
verified publisher icon crossbeam-rs

skiplist: Memory leak in SkipList

Open taiki-e opened this issue 5 years ago • 2 comments

Run the following command on crossbeam-skiplist:

RUSTFLAGS='-Z sanitizer=address' \
cargo test --release --target x86_64-unknown-linux-gnu --test base

AddressSanitizer reports memory leak:

output 
+ RUSTFLAGS='-Z sanitizer=address'
+ cargo test --release --target x86_64-unknown-linux-gnu --test base
   Compiling autocfg v1.0.1
   Compiling libc v0.2.81
   Compiling getrandom v0.1.15
   Compiling cfg-if v0.1.10
   Compiling lazy_static v1.4.0
   Compiling cfg-if v1.0.0
   Compiling ppv-lite86 v0.2.10
   Compiling scopeguard v1.1.0
   Compiling memoffset v0.6.1
   Compiling crossbeam-utils v0.8.1 (/home/runner/work/crossbeam/crossbeam/crossbeam-utils)
   Compiling rand_core v0.5.1
   Compiling crossbeam-epoch v0.9.1 (/home/runner/work/crossbeam/crossbeam/crossbeam-epoch)
   Compiling rand_chacha v0.2.2
   Compiling crossbeam-skiplist v0.0.0 (/home/runner/work/crossbeam/crossbeam/crossbeam-skiplist)
   Compiling rand v0.7.3
    Finished release [optimized] target(s) in 14.27s
     Running /home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd

running 20 tests
test clear ... ok
test drops ... ok
test entry ... ok
test entry_remove ... ok
test entry_reposition ... ok
test front_and_back ... ok
test get ... ok
test get_next_prev ... ok
test get_or_insert ... ok
test insert ... ok
test insert_and_remove ... ok
test into_iter ... ok
test is_empty ... ok
test iter ... ok
test iter_range ... ok
test len ... ok
test lower_bound ... ok
test new ... ok
test remove ... ok
test upper_bound ... ok

test result: ok. 20 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.01s


=================================================================
==4419==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 120 byte(s) in 5 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2cde29  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xc2e29)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 104 byte(s) in 4 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2d3dbb  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xc8dbb)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 56 byte(s) in 2 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2da652  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xcf652)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 48 byte(s) in 2 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2cab5b  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xbfb5b)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 40 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2bf896  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xb4896)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 40 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2da749  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xcf749)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 32 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2bf6a5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xb46a5)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2d5451  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xca451)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2d541b  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xca41b)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2dbda9  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xd0da9)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2bf4b4  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xb44b4)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2be4b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xb34b5)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2da7c5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xcf7c5)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2be4e9  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xb34e9)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2be501  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xb3501)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Direct leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2d115a  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xc615a)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Indirect leak of 128 byte(s) in 5 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2cab5b  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xbfb5b)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Indirect leak of 56 byte(s) in 2 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2cde29  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xc2e29)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Indirect leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2d546c  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xca46c)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Indirect leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2bfa87  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xb4a87)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Indirect leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2be519  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xb3519)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

Indirect leak of 24 byte(s) in 1 object(s) allocated from:
    #0 0x5636fa29a7ed  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x8f7ed)
    #1 0x5636fa3042b5  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xf92b5)
    #2 0x5636fa2be4d1  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0xb34d1)
    #3 0x5636fa338ad2  (/home/runner/work/crossbeam/crossbeam/target/x86_64-unknown-linux-gnu/release/deps/base-83127d336c549fdd+0x12dad2)

SUMMARY: AddressSanitizer: 936 byte(s) leaked in 36 allocation(s).
error: test failed, to rerun pass '--test base'

Found in #591 (https://github.com/crossbeam-rs/crossbeam/runs/1524623353?check_suite_focus=true)

taiki-e avatar Dec 09 '20 14:12 taiki-e

This seems to be related to base::RefEntry not implementing Drop (https://github.com/crossbeam-rs/crossbeam/pull/337).

Also, this only happens with SkipList, and SkipMap and SkipSet don't seem to have this problem. (https://github.com/crossbeam-rs/crossbeam/pull/674)

taiki-e avatar Apr 18 '21 14:04 taiki-e

FYI: Entry for SkipMap and SkipSet implements Drop, which in turn calls release_with_pin so these two types don't suffer from memory leak.

I don't necessarily think this is a bug as the doc comment on RefEntry explicitly states about this behavior, just that it is easier to shoot yourself in the foot than a typical Rust API. Of course not great, but a necessary evil when dealing with lock-free stuff IMHO.

Concerning the 0.1 release, is it feasible to make SkipList private as it is prone to misuse? Personally, it feels unnecessary to expose SkipList when we already have SkipMap and SkipSet.

topecongiro avatar Aug 20 '21 15:08 topecongiro