Will these code produce a deadlock using Rust Dashmap?

Question

Will code like these ever produce a deadlock using a DashMap in Rust?

// snippet_1
let a = DashMap::new();
let b = DashMap::new();

// thread1
for v in a.iter(){
   xxx
}
for v in b.iter(){
   xxx
}

//thread2
for v in b.iter(){
   xxx
}
for v in a.iter(){
   xxx
}

// snippet_2
let a = DashMap::new();
let b = DashMap::new();

// thread1
for v in a.iter(){
   xxx
}
for v in b.iter(){
   xxx
}

//thread2
for v in b.iter(){
   xxx
   for v in a.iter() {
      xxx
   }
   xxx
}

// snippet_3
let a = DashMap::new();
let b = DashMap::new();

// thread1
for v in a.iter(){
   xxx
}
for v in b.iter(){
   xxx
}

//thread2
for v in b.iter(){
   xxx
   let Some(v) = a.get_mut(key){
      xxx
   }
   xxx
}

Also, inserting into a dashmap when iterate it in the same thread will produce a deadlock. However, inserting into a dashmap from another thread will not produce a deadlock. Is that true?

Helbonna

Answer 1

None of the examples will produce a deadlock.

From the documentation:

insert(): Inserts a key and a value into the map. Returns the old value associated with the key if there was one.
Locking behaviour: May deadlock if called when holding any sort of reference into the map.

iter(): Creates an iterator over a DashMap yielding immutable references.
Locking behaviour: May deadlock if called when holding a mutable reference into the map.

get_mut(): Get a mutable reference to an entry in the map
Locking behaviour: May deadlock if called when holding any sort of reference into the map.

Explanation:

In your first two examples, only iter() is used, so as long as no other operations that take mutable references into the maps are used, there will be no deadlocks.

In your third example, DashMap b is only ever used with iter() again, so no deadlocks there. For DashMap a there are two possible execution flows:

1. If thread 1 reaches a.iter() first, then thread 2 will have to wait at a.get_mut(key), but once thread 1 has finished iterating over a thread 2 will be able to continue, so there will be no deadlock.
2. If thread 2 reaches a.get_mut(key) first, then thread 1 will have to wait at a.iter() but once thread 2 has finished it will be able to continue and there will be no deadlock.

Additional questions:

Inserting into a DashMap when iterating over it in the same thread will produce a deadlock.

Example:

for v in a.iter() { // This takes a reference into `a`
    a.insert(...) // Will deadlock because you hold a reference into `a`
}

Inserting into a DashMap from one thread while iterating over it in another will not produce a deadlock, one of them will just wait for the other.

Example:

//thread1
for v in a.iter(){ //If thread2 reaches `insert()` first, this will wait until it has finished.
    xxx
}

//thread2
for i in 1..1000 {
    a.insert(i, i); // If thread1 reaches `iter()` first, this will wait until it has finished.
}

It is important to note that in the last example and in the 3rd example from the question, insert() and iter() may not wait for the whole loop to complete before starting, instead the execution of the two loops will be interleaved but they will never execute at the exact same time.

Glasgow

"instead the execution of the two loops will be interleaved", you mean that in thread1, each for loop will hold and release the lock, and in the interval, thread2 can insert some value into a, and then later thread1 may iter the value just inserted? – Helbonna

I mean that in the final example, thread1 and thread2 may alternate holding the lock and execute different number of iterations before pasing the lock to the other thread, instead of either thread completing all of its iterations before the other has a chance to run. And yes, this would mean that thread2 can insert something in the map and thread1 can read it after that. – Glasgow