Can the Rust type system prevent deadlocks?

Would you trust me with a mutex? No, I thought not.

I don’t trust myself either. Deadlocks lurk around every corner, when you’re least expecting it. Can we avoid them at compile time using the Rust type system? That is, can prove at compile-time that there are no deadlocks?

Let’s say we have two mutexes (or mutices, if that’s your bag) M1 and M2.

A deadlock can occur if a thread T1 holds M1 but wishes to claim M2; while meanwhile thread T2 has M2 and wishes to claim M1.

Several patterns can avoid that:

• Never claim more than one of M1 and M2 simultaneously
• Never claim M2 unless we already hold M1 (or vice-versa)

It feels like we might be able to encode these invariants in the Rust type system.

First, we need a token that can’t move between threads. Something like the following zero-sized type (ZST):

#![feature(negative_impls)] // bah

pub struct MutexPermissionToken(PhantomData<()>);

impl !Send for MutexPermissionToken {}

(The PhantomData ensures that the token can’t be created outside the current mod, by having a private field).

Let’s look at the two patterns. In each case, let’s assume we’re making a new wrapper for Mutex and MutexGuard .

“Never claim more than one of M1 and M2 simultaneously”:

To do this, we need to make sure that exactly one such “mutex permission token” exists per thread. In the same file, we say:

thread_local! {
   pub static MUTEX_PERMISSION_TOKEN: Cell<Option<MutexPermissionToken>> 
     = Cell::new(Some(MutexPermissionToken(PhantomData));
}

A caller can get that MutexPermissionToken out — exactly once per thread. The caller should expect to store that somewhere, as it will need it pretty often. But that’s OK! — it’s zero-sized, so this is just book-keeping, not actual real code.

Our new mutex wrapper has a modified lock() method which takes the MutexPermissionToken and stores it within the modified MutexGuard :

impl<T> DeadlockProofMutex<T> {
  fn lock(&self, permission: MutexPermissionToken) -> LockResult<DeadlockProofMutexGuard<T>> {
    // calls through to underlying mutex.lock()
    // wraps the result in a newtype wrapper containing the
    // (zero-sized) MutexPermissionToken
  }
}

The mutex guard requires a little more work. Currently it unlocks in its Drop impl. We’d want to add an explicit unlock() method which retrieves the MutexPermissionToken :

impl<T> DeadlockProofMutexGuard<T> {
  fn unlock(self) -> MutexPermissionToken {
    // unlock the underlying mutex
    // return the MutexPermissionToken
  }
}

And there we have it. If both M1 and M2 are of type DeadlockProofMutex, the compiler will prevent callers claiming both at once, hence no deadlock.

In theory, as the MutexPermissionToken is zero-sized, none of this should make any difference to the compiled code or runtime activity.

Is this ergonomic for the caller? Well, taking care of the precious MutexPermissionToken may require the caller to build a state machine — but we know they’re pretty pain-free using Rust enums, especially with compile-time deadlock prevention.

“Never claim M2 unless we already hold M1”. Let’s assume for simplicity that we have two mutex types — DeadlockProofMutex and DeadlockProofOuterMutex . The former is exactly as we already described — it requires you to possess a MutexPermissionToken to be able to claim its lock.

But this time, the MutexPermissionToken is issued by the outer mutex. (We remove the previous MUTEX_PERMISSION_TOKEN). Specifically, you get one when you lock it, and return it when you unlock it.

impl<T> DeadlockProofOuterMutex<T> {
  fn lock(&self) -> LockResult<(DeadlockProofOuterMutexGuard<T>, MutexPermissionToken> {
     // returns the thread's MutexPermissionToken if lock succeeds.
  }
}

impl<T> DeadlockProofOuterMutexGuard<T> {
  fn unlock(self, token: MutexPermissionToken) {
    // ...
  }
}

We don’t need to do any fancy tracking here. Thanks to the nature of a mutex, only one MutexPermissionToken can be in circulation at any time.

Only if the outer mutex is locked can anyone attempt to claim the inner mutex. Deadlock prevented.

The tricky bit here is that we don’t want to implement Drop for DeadlockProofOuterMutexGuard . We don’t want it to be possible to unlock the outer mutex without returning the MutexPermissionToken . We can just panic! inside the Drop , or we can possibly even use #[inline] and const to prove at compile time that dropis never called (something like this, though thanks to lilasta for pointing out that this can’t be made to work reliably because drop code is instantiated in more places than we expect).

I’ve experimented with some of these ideas here (sample client code here).

Of course, in practice there might well be better ways to express your program than to use a bunch of mutexes. Nevertheless, it’s interesting to me that Rust’s type system can be used to solve classes of difficult bug (deadlock) totally unrelated to memory safety. The general theory here is that some of these Rust facilities can act as a Substructural Type System.

Thanks to Chris Palmer for edits on this post!