Lock ordering enforcement at compile time

This library contains types and traits to ensure, at compile time, that locks are acquired in the correct order.

Credits

Inspired by Fuchsia's lock-ordering and lock-sequence libraries.

lib.rs:

Lock ordering enforcement at compile time

This library contains types and traits to ensure that locks that are held at the same time are acquired in the correct order. This lets code authors verify, at compile time, that their code is free of deadlock opportunities.

The way this works is by using traits in the [relation] module to define orderings between marker types that represent different lock-levels. The core logic lives in the LockedAt type; it uses trait bounds to ensure that any acquisition of locks respects these orderings.

How it works

This crate combines two ideas:

1. acquiring and holding locks can be represented as mutable borrowing; and
2. a correct lock ordering can be modeled as a directed graph of pairwise before/after relationships.

Representing locking using mutable state

Within any call tree, a (non-reentrant) lock cannot be acquired more than once at a time. Doing otherwise would lead to deadlock.

To visualize this, look at the following code:

let mutex = std::sync::Mutex::new(false);

{
    // in a function somewhere
    let guard = mutex.lock().unwrap();
    // do something with the value
    drop(guard);
}

For every call tree we assign each lock some mutable state and pair every acquisition of a lock with a mutable borrow of that state. What that looks like here:

{
    let mut state = ();

    let (guard, borrow) = (mutex.lock().unwrap(), &mut state);
    // do something
    drop((guard, borrow));
}

Now we can take advantage of Rust's enforcement of exclusivity for mutable borrows. This lets us prevent at compile time what would otherwise be a run time deadlock!

{
  let mut state = ();

  let (guard, borrow) = (mutex.lock().unwrap(), &mut state);
  {
    // This fails to compile because `state` is already mutably borrowed.
    let (second_guard, second_borrow) = (mutex.lock().unwrap(), &mut state);
    drop((second_guard, second_borrow));
  }
  drop((guard, borrow));
}

This only works so long as we make sure that the borrows of our mutable marker state last as long as the actual borrows of the locked state. We can enforce that in the type system by tying the two lifetimes together.

fn lock_with_marker_state<'a, T>(
    mutex: &'a std::sync::Mutex<T>,
    borrow: &'a mut (),
) -> (std::sync::MutexGuard<'a, T>, &'a mut ()) {
}

Modeling lock ordering as a directed graph of orderings

In order for a program to follow a consistent lock ordering, it must be ensured that for any two locks held at the same time, they are acquired in the same order in every possible tree of function calls. One way to achieve this is to assign every lock an ordered "level". Then we ensure that at each point in the code we only acquire locks with a higher level than the highest currently held.

Since we're using Rust, we can use marker types to represent levels and traits to represent the ordering between them. That might look something like this:

trait LockedBefore<L> {}

struct Unlocked;
struct FirstLevel;
struct SecondLevel;

impl LockedBefore<FirstLevel> for Unlocked {}
impl LockedBefore<SecondLevel> for Unlocked {}
impl LockedBefore<SecondLevel> for FirstLevel {}

That's not enough on its own, but we can define functions whose trait bounds enforce our lock ordering:

struct HeldLockLevel<L>(std::marker::PhantomData<L>);

fn acquire_lock<'a, CurrentLevel, L, T>(
    lock: &'a (std::sync::Mutex<T>, std::marker::PhantomData<L>),
    current_level: &'a mut HeldLockLevel<CurrentLevel>,
) -> (std::sync::MutexGuard<'a, T>, &'a mut HeldLockLevel<L>)
where
    CurrentLevel: LockedBefore<L>,
{
    // ...
}

These can prevent us from acquiring locks out of order. With the following shared state:

let first_mutex = (
    std::sync::Mutex::new(true),
    std::marker::PhantomData::<FirstLevel>,
);
let second_mutex = (
    std::sync::Mutex::new('a'),
    std::marker::PhantomData::<SecondLevel>,
);

This works:

let mut current_level = HeldLockLevel::<Unlocked>(std::marker::PhantomData);

let (mut first_guard, mut current_level) = acquire_lock(&first_mutex, &mut current_level);
let (mut second_guard, mut current_level) = acquire_lock(&second_mutex, &mut current_level);

Attempting to access locks out of order fails:

let mut current_level = HeldLockLevel::<Unlocked>(std::marker::PhantomData);

let (mut second_guard, mut current_level) = acquire_lock(&second_mutex, &mut current_level);
// This will fail to compile because SecondLevel does not implement LockedBefore<FirstLevel>
let (mut first_guard, mut current_level) = acquire_lock(&first_mutex, &mut current_level);

It's worth noting that this only works so long as we ensure our LockedBefore trait implementations are consistent. There's no language-level feature that prevents us from introducing a cycle in our trait implementations and defining an invalid lock ordering!

How to use this crate

You'll need to define a marker type for each "level" in your lock ordering hierarchy, then implement LockLevel for each of them. Then carefully implement relation::LockBefore to express the order in which pairs of locks can be acquired. The relation::impl_transitive_lock_order macro can help with this by providing transitive implementations of LockBefore.

Next, you'll need to specify the acquisition method for each lock by implementing one of crate::lock::MutexLock, crate::lock::RwLock, or their async counterparts.

Lastly, ensure that every call tree in your code constructs at most one LockedAt. "Root" functions that are only called externally can construct one using LockedAt::new, but any non-root function that acquires a lock should take a &mut LockedAt<'_, L> as an argument. Make sure you consider the full call graph! A function invoked as a callback, for example, is not a root function, and so should not construct a LockedAt unless the callback invocation code doesn't acquire any locks.

See the examples for more details.