#order #locks #deadlock #parallelism #locking #compile-time

no-std lock_tree

Prevent deadlocks at compile time. A standalone republication of the netstack3 lock-ordering crate, part of Google's Fuchsia OS.

1 unstable release

0.1.0 Jan 9, 2025

#471 in Concurrency

Download history 125/week @ 2025-01-08

125 downloads per month

Custom license

64KB
1K SLoC

lock_tree

A standalone republication of the netstack3 lock-ordering crate, part of Google's Fuchsia OS. This crate was named lock_tree due to a crates.io conflict.

lock_tree empowers you to prevent deadlocks at compile time, providing traits that enforce lock ordering statically.

All credit (and indeed the copyright) for this work belongs to the Fuchsia team – see the LICENSE for details.


lib.rs:

Tools for describing and enforcing lock acquisition order.

Using code defines lock levels with types and then implements traits from this crate, like relation::LockAfter to describe how those locks can be acquired. A separate set of traits in lock implement locked access for your type. A complete example:

use std::sync::Mutex;
use lock_tree::{impl_lock_after, lock::LockFor, relation::LockAfter, Locked, Unlocked};

#[derive(Default)]
struct HoldsLocks {
    a: Mutex<u8>,
    b: Mutex<u32>,
}

enum LockA {}
enum LockB {}

impl LockFor<LockA> for HoldsLocks {
    type Data = u8;
    type Guard<'l> = std::sync::MutexGuard<'l, u8>
        where Self: 'l;
    fn lock(&self) -> Self::Guard<'_> {
        self.a.lock().unwrap()
    }
}

impl LockFor<LockB> for HoldsLocks {
    type Data = u32;
    type Guard<'l> = std::sync::MutexGuard<'l, u32>
        where Self: 'l;
    fn lock(&self) -> Self::Guard<'_> {
        self.b.lock().unwrap()
    }
}

// LockA is the top of the lock hierarchy.
impl LockAfter<Unlocked> for LockA {}
// LockA can be acquired before LockB.
impl_lock_after!(LockA => LockB);

// Accessing locked state looks like this:

let state = HoldsLocks::default();
// Create a new lock session with the "root" lock level (empty tuple).
let mut locked = Locked::new(&state);
// Access locked state.
let (a, mut locked_a) = locked.lock_and::<LockA>();
let b = locked_a.lock::<LockB>();

The methods on Locked prevent out-of-order locking according to the specified lock relationships.

This won't compile because LockB does not implement LockBefore<LockA>:

#
#
#
#
#
#
#
let state = HoldsLocks::default();
let mut locked = Locked::new(&state);

// Locking B without A is fine, but locking A after B is not.
let (b, mut locked_b) = locked.lock_and::<LockB>();
// compile error: LockB does not implement LockBefore<LockA>
let a = locked_b.lock::<LockA>();

Even if the lock guard goes out of scope, the new Locked instance returned by Locked::lock_and will prevent the original one from being used to access state. This doesn't work:

#
#
#
#
#
#
#
let state = HoldsLocks::default();
let mut locked = Locked::new(&state);

let (b, mut locked_b) = locked.lock_and::<LockB>();
drop(b);
let b = locked_b.lock::<LockB>();
// Won't work; `locked` is mutably borrowed by `locked_b`.
let a = locked.lock::<LockA>();

The impl_lock_after macro provides implementations of LockAfter for a pair of locks. The complete lock ordering tree can be spelled out by calling impl_lock_after for each parent and child in the hierarchy. One of the upsides to using impl_lock_after is that it also prevents accidental lock ordering inversion. This won't compile:

enum LockA {}
enum LockB {}

impl_lock_after(LockA => LockB);
impl_lock_after(LockB => LockA);

Lock ordering tree: A -> B -> {C, D}

No runtime deps