Deadlock Issues in Rust’s DashMap: A Practical Case Study

Rust’s DashMap is a highly appreciated multi-threaded concurrent and lock-free HashMap variant. It is generally efficient and its API is straightforward to use, but sometimes, it presents us with tricky scenarios like deadlocks. In this article, I will guide you through a deadlock issue caused by DashMap in a Rust code and show you how I resolved it.

Let us consider a piece of code in a plane old Rust index structure:

pub struct Index {
...
  memory_segments_map: DashMap<u32, Segment>,
...
}

I experienced a deadlock when calling self.memory_segments_map.remove(&segment_number);in the following function:

...
  let segment_ref = self
    .memory_segments_map
    .get(&segment_number)
    ...
  *lock = thread::current().id();
  ...
    match delete_result {
    ...
    } else {
      self.memory_segments_map.remove(&segment_number);
    }
...

The reason for this deadlock lies in how DashMap works internally. It operates by locking on a bucket — once a reference to a certain key’s bucket is taken, it leads to a wait state for the bucket to release before any modification can be made to that bucket. As a result, deadlocks occur. This is what the documentation for remove function says

/// Removes an entry from the map, returning the key and value if they existed in the map.
///
/// **Locking behaviour:** May deadlock if called when holding any sort of reference into the map.
pub fn remove<Q>(&self, key: &Q) -> Option<(K, V)>
where
    K: Borrow<Q>,
    Q: Hash + Eq + ?Sized,
{
    self._remove(key)
}

Specifically, I had a reference to the map via segment_ref, and then attempted to remove an item from the same locked bucket ( self.memory_segments_map.remove(&segment_number))).

Addressing this issue required ensuring that segment_ref was not locking the bucket when self.memory_segments_map.remove(&segment_number)) was called. This could be achieved by either wrapping segment_ref within a block (ensuring it gets dropped and releases its lock before the remove operation), or setting it to None.
Here’s an example of wrapping segment_refin a block:

pub async fn delete_segment(&self, segment_number: u32) -> Result<(), CoreDBError> {
 {
 let segment_ref = self
 .memory_segments_map
 .get(&segment_number)
 …
 …
 } // Here, segment_ref gets dropped, releasing its lock
 …
 self.memory_segments_map.remove(&segment_number);
 …
}

Applying these changes will release the DashMap lock held by segment_refbefore attempting the remove, thereby preventing the deadlock.

In summary, this experience underscores the importance of a nuanced understanding of the internal workings of DashMapand other concurrent data structures. Fine control over the life cycle and scope of mutable references in concurrent programming can be fundamental to avoiding fraught scenarios like deadlocks. It’s also a reminder of Rust’s power and efficacy in developing reliable, concurrent applications, given its tools and explicitness around memory management and concurrency.