Unsoundness in Ref::value

[ray-kast]

I encountered an issue in a crate I was working on using a DashMap, where hitting the map with a highly concurrent load in a release build caused a segfault when a value borrowed from a DashMap disappeared from memory. After some digging, it seems the error is related to my use of the Ref::value method, which produces a reference that can outlive the Ref and thus escape the lock.

I constructed a small example below that did not segfault, but does exhibit the same underlying undefined behavior:

use dashmap::DashMap;

fn main() {
    let x = DashMap::new();

    x.insert(1, 1);

    let one: &i32 = {
        let borrow = x.get(&1).unwrap();
        let val = borrow.value();
        std::mem::drop(borrow); // !!!
        val
    };

    println!("{}", one); // Prints `1`

    for i in 0..100 {
        x.insert(i, i + 1);
    }

    println!("{}", one); // Prints `2`!
}

After further testing, if the 100 is increased to a sufficiently high value such that the shard one is located in is reallocated, the second println! will begin to print arbitrary and inconsistent values.

System info:
rustc 1.57.0 (f1edd0429 2021-11-29)
toolchain: stable-x86_64-unknown-linux-gnu
dashmap version used: 5.0.0

[ray-kast]

At a glance, the fix for this issue seems easy enough, all Ref-like structs return &'a T references with no bounds on the lifetime of &self. Checking the docs for RwLockReadGuard, it seems like the solution may just be to return &T for &self to enforce borrowing from the Ref for the lifetime of the return value.

Additionally it seems that every accessor of every Ref struct in the crate likely has the same unsoundness. I can try to whip up a PR draft with a resolution when I have some free time later.

[ray-kast]

Couple updates - first is that the above example does still exhibit UB if value() is replaced with key() and the value for 100 is replaced with a significantly large integer. Second is that I forked and drafted a quick attempt at a fix in #168 - the MVE above no longer compiles when using the fork, but I'm not sure if the lifetimes I specified break the API in an undesirable way (in which case I suppose this would be part of a larger design consideration).

[LeSeulArtichaut]

I'm not sure if the lifetimes I specified break the API in an undesirable way (in which case I suppose this would be part of a larger design consideration)

This issue can be traced back to this unsafe block:

dashmap/src/lib.rs

Lines 766 to 772 in e8e5e86

	unsafe {
	let kptr = util::change_lifetime_const(kptr);
	let vptr = util::change_lifetime_const(vptr);
	Some(Ref::new(shard, kptr, vptr.get()))
	}

where we bypass the borrow checker by changing the lifetime of the key/value references and promise to not let the references outlive the guard. To uphold this contract, the longest possible lifetime of the references returned in Ref::key and Ref::value is the lifetime of self which owns the guard, and any longer lifetime would be unsound.

[ray-kast]

@LeSeulArtichaut Yeah, I saw that while tracing the issue through a segfault stack trace. Only problem seemed to be that either the return value of Ref::key and Ref::value or the corresponding &self for each method were annotated with the wrong lifetime in a couple spots…

[LeSeulArtichaut]

For reference, you don't need to force a reallocation to cause UB

use dashmap::DashMap;

fn main() {
    let x = DashMap::new();

    x.insert(1, 1);

    let borrow = x.get(&1).unwrap();
    let val = borrow.value();
    std::mem::drop(borrow);
    let mut borrow_mut = x.get_mut(&1).unwrap();
    let val_mut = borrow_mut.value_mut(); // non-exclusive mutable reference!!!
    println!("{}", val);
}

Miri error

error: Undefined Behavior: trying to reborrow for SharedReadOnly at alloc4483+0x4, but parent tag <11418> does not have an appropriate item in the borrow stack
    --> /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/fmt/mod.rs:2097:1
     |
2097 | fmt_refs! { Debug, Display, Octal, Binary, LowerHex, UpperHex, LowerExp, UpperExp }
     | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ trying to reborrow for SharedReadOnly at alloc4483+0x4, but parent tag <11418> does not have an appropriate item in the borrow stack
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
             
     = note: inside `<&i32 as std::fmt::Display>::fmt` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/fmt/mod.rs:2087:71
     = note: inside `std::fmt::write` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/fmt/mod.rs:1149:17
     = note: inside `<std::io::StdoutLock as std::io::Write>::write_fmt` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/io/mod.rs:1660:15
     = note: inside `<&std::io::Stdout as std::io::Write>::write_fmt` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/io/stdio.rs:844:9
     = note: inside `<std::io::Stdout as std::io::Write>::write_fmt` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/io/stdio.rs:818:9
     = note: inside `std::io::stdio::print_to::<std::io::Stdout>` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/io/stdio.rs:1186:21
     = note: inside `std::io::_print` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/io/stdio.rs:1199:5
note: inside `main` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/macros.rs:97:9
    --> src/main.rs:13:5
     |
13   |     println!("{}", val);
     |     ^^^^^^^^^^^^^^^^^^^
     = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
     = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:123:18
     = note: inside closure at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:145:18
     = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
     = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:406:40
     = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:370:19
     = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:133:14
     = note: inside closure at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:128:48
     = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:406:40
     = note: inside `std::panicking::r#try::<isize, [closure@std::rt::lang_start_internal::{closure#2}]>` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:370:19
     = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:133:14
     = note: inside `std::rt::lang_start_internal` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:128:20
     = note: inside `std::rt::lang_start::<()>` at /home/leo/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:144:17
     = note: this error originates in the macro `fmt_refs` (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to previous error; 1 warning emitted

[ray-kast]

By the way, you don't need to force a reallocation to cause UB

Yeah, the code example above is already UB since the immutable borrow of 1 changes to 2. The reallocate and arbitrary memory just makes it more exciting 😉

Thanks for the MIRI error, I wanted to get one myself but I couldn’t get past num_cpus opening a file handle on linux…

[LeSeulArtichaut]

Thanks for the MIRI error, I wanted to get one myself but I couldn’t get past num_cpus opening a file handle on linux…

You apparently need to set MIRIFLAGS='-Zmiri-disable-isolation' for this

[Qwaz]

This issue looks rather dangerous to me. Would it make sense to yank the affected version from crates.io until the issue is fixed?

[xacrimon]

Yep, yanked. I want to put out a fix but that will happen when it happens since I don't get paid to develop dashmap and my time is finite. Thanks for the understanding.

[xacrimon]

I will keep this issue open until a new unaffected patch release for v5 is put out, but in the meantime, cargo won't break any more projects.

[xacrimon]

Patch is open, point release with fix will be released 6 Feb 2022 CEST.