Document single-threaded deadlock behavior

[kazimuth]

This code:

let map = DashMap::<i32, i32>::new();
map.insert(1, 2);
let a = map.get_mut(&1);
let b = map.get(&1);

will deadlock. The shard containing 1 gets write-locked, nothing else can access it. This is reasonable behavior but I think it should be documented.

Perhaps more surprising is that this code:

let map = DashMap::<i32, i32>::new();

for i in 0..100 {
    map.insert(i, 0);
}

let mut refs = vec![];
for i in 0..100 {
    refs.push(map.get_mut(&i))
}

Will also deadlock. Even though you're not getting the same slot twice, you're still trying to lock certain chunks twice, since some slots are colocated. This isn't very realistic code though. Something less artificial might look like:

let a = map.get_mut(a);
let b = map.get_mut(b);

This code can still deadlock! But it's more sporadic. It only deadlocks with probability 1/shard_count^2; if the two entries happen to be colocated.

Basically, if your thread is holding a RefMut, it's not deadlock-safe to do any other operations to the map. This behavior surprised me a little, so I think it would be worth documenting.

[kazimuth]

Also, I think I've come up with an API that could prevent this issue. It's a pretty big change from the stdlib API though.

struct DashMap {
    // ...
    viewed: ThreadLocal<bool>
}

impl DashMap {
    fn new() -> DashMap { /* ... */ }

    fn view(&self) -> Option<View> {
        if self.viewed {
            None
        } else {
            *self.viewed = True;
            View(self)
        }
    }

    // no other API
}

struct View<'a>(&'a DashMap);
unsafe impl !Send for View {}
unsafe impl !Sync for View {} 

impl View {
    fn get_mut(&mut self, key: K) -> Option<RefMut<K,V>> { /* ... */ }
    fn get(&self, key: K) -> Option<Ref<K,V>> { /* ... */ }

    // ...rest of the DashMap API...
}

Basically, you only allow 1 View per thread to created of the DashMap, and you require all operations to use a View instead of the underlying map. Then you use Rust's normal borrowing stuff to prevent creating more than one RefMut on a thread at a time, which prevents deadlock.

This is a pretty big change though, totally understand if you'd rather just document the constraint. Could be worth spinning out into its own crate.

[xacrimon]

Heyo! Thanks for pointing out the docs issue. I do have a fix for this in the next major version which is currently in development on the acrimon/experimental branch. I am currently tight on time and would be grateful if I could get a small docs pr. Otherwise I will open an issue and do it when I can.

[rrnewton]

I ran into this as well. It would be great if the docs could mention the locking behavior for each method. I mostly use lock-free APIs, and it wasn't 100% obvious to me what would retain a lock and for how long.

Especially when I went through swapping HashMap for Dashmap in async/await code, I quickly introduced deadlocks by accident.

[xacrimon]

I will make a patch release in a few hours to update the documentation. The larger goal is to get 4.0 out which gets rid of the locks.

[xacrimon]

If you want you can use the 4.0 rc4 prerelease.

[xacrimon]

v3.11.3 released with doc updates.