Cross-shard deadlock when holding Ref guard and calling insert() on a different key
Summary
Holding a Ref (read guard) from DashMap::get() while calling DashMap::insert() with a key that maps to a different shard can cause a deadlock when another thread performs the reverse operation.
This is a known pattern but there is no compile-time or runtime warning, and the documentation does not explicitly warn about cross-shard deadlock with mixed read/write operations.
Reproduction
use dashmap::DashMap;
use std::sync::Arc;
use std::thread;
fn main() {
let map = Arc::new(DashMap::new());
map.insert("alpha".to_string(), 1);
map.insert("beta".to_string(), 2);
let m1 = map.clone();
let m2 = map.clone();
// Thread 0: read("alpha") [shard A] → insert("beta") [shard B]
let t0 = thread::spawn(move || {
let ref_a = m1.get("alpha").unwrap(); // read lock shard A
m1.insert("beta".to_string(), 10); // write lock shard B
drop(ref_a);
});
// Thread 1: read("beta") [shard B] → insert("alpha") [shard A]
let t1 = thread::spawn(move || {
let ref_b = m2.get("beta").unwrap(); // read lock shard B
m2.insert("alpha".to_string(), 20); // write lock shard A
drop(ref_b);
});
t0.join().unwrap();
t1.join().unwrap();
}In this example, "alpha" and "beta" hash to different shards. Under certain scheduling, both threads simultaneously hold read locks on different shards and attempt write locks on each other's shard, resulting in a deadlock cycle.
Analysis
DashMap uses per-shard RwLock for concurrent access. Each get() returns a Ref that holds a read lock on the target shard. The lock is held for the lifetime of the Ref.
When a Ref from shard A is alive and insert() targets shard B, the calling thread holds read(A) and requests write(B). If another thread simultaneously holds read(B) and requests write(A), neither can proceed:
Thread 0: read(shard_A) held → write(shard_B) blocked
Thread 1: read(shard_B) held → write(shard_A) blocked
→ Deadlock cycle: [Thread 0, Thread 1]
This was detected automatically using Ki-DPOR (Dynamic Partial Order Reduction) exhaustive interleaving exploration. The tool found the deadlock cycle in 8 lock events within 0.01 seconds.
DPOR Event Trace
Event 0: RwLockReadAcquired { thread: 0, resource: shard_19 } // get("alpha")
Event 1: RwLockWriteAcquired { thread: 0, resource: shard_28 } // insert("beta")
Event 2: RwLockWriteReleased { thread: 0, resource: shard_28 }
Event 3: RwLockReadReleased { thread: 0, resource: shard_19 }
Event 4: RwLockReadAcquired { thread: 1, resource: shard_28 } // get("beta")
Event 5: RwLockWriteAcquired { thread: 1, resource: shard_19 } // insert("alpha")
Event 6: RwLockWriteReleased { thread: 1, resource: shard_19 }
Event 7: RwLockReadReleased { thread: 1, resource: shard_28 }
DPOR explores the interleaving where events 0 and 4 execute before events 1 and 5, creating the deadlock cycle.
Impact
This affects any code that:
- Calls
get() or get_mut() to obtain a Ref/RefMut guard
- While the guard is alive, calls
insert(), remove(), or any mutating operation on a different key (that may map to a different shard)
- Another thread performs the reverse pattern concurrently
The probability of deadlock depends on:
- Whether the keys map to different shards (hash-dependent)
- Whether the threads interleave at the critical window
- The number of shards (more shards = higher chance of cross-shard access)
Suggestion
Consider adding a documentation note to DashMap::get() and Ref warning about this pattern:
Warning: Holding a Ref guard while performing mutating operations (insert, remove, alter) on other keys may cause a deadlock if the keys map to different internal shards. Drop the Ref before mutating other entries, or use entry() API for atomic read-modify-write patterns.
Example of safe pattern:
// Unsafe: holding Ref while inserting another key
let ref_a = map.get("alpha").unwrap();
map.insert("beta".to_string(), *ref_a + 1); // potential deadlock!
drop(ref_a);
// Safe: read value, drop guard, then insert
let value = *map.get("alpha").unwrap(); // Ref dropped at end of statement
map.insert("beta".to_string(), value + 1); // no guard heldEnvironment
- DashMap version: 6.1.0
- Rust version: stable
- Detection tool: Ki-DPOR (Laplace Framework) — exhaustive dynamic partial order reduction
- Detection method: Automatic interleaving exploration with TrackedRwLock instrumentation
Cross-shard deadlock when holding
Refguard and callinginsert()on a different keySummary
Holding a
Ref(read guard) fromDashMap::get()while callingDashMap::insert()with a key that maps to a different shard can cause a deadlock when another thread performs the reverse operation.This is a known pattern but there is no compile-time or runtime warning, and the documentation does not explicitly warn about cross-shard deadlock with mixed read/write operations.
Reproduction
In this example,
"alpha"and"beta"hash to different shards. Under certain scheduling, both threads simultaneously hold read locks on different shards and attempt write locks on each other's shard, resulting in a deadlock cycle.Analysis
DashMap uses per-shard
RwLockfor concurrent access. Eachget()returns aRefthat holds a read lock on the target shard. The lock is held for the lifetime of theRef.When a
Reffrom shard A is alive andinsert()targets shard B, the calling thread holdsread(A)and requestswrite(B). If another thread simultaneously holdsread(B)and requestswrite(A), neither can proceed:This was detected automatically using Ki-DPOR (Dynamic Partial Order Reduction) exhaustive interleaving exploration. The tool found the deadlock cycle in 8 lock events within 0.01 seconds.
DPOR Event Trace
DPOR explores the interleaving where events 0 and 4 execute before events 1 and 5, creating the deadlock cycle.
Impact
This affects any code that:
get()orget_mut()to obtain aRef/RefMutguardinsert(),remove(), or any mutating operation on a different key (that may map to a different shard)The probability of deadlock depends on:
Suggestion
Consider adding a documentation note to
DashMap::get()andRefwarning about this pattern:Example of safe pattern:
Environment