lock-ordering#

Compile-time deadlock prevention for Rust. Declare a partial order over your locks and the type system refuses to compile any acquisition that violates it.

Motivation#

Deadlock is one of the few classes of bug Rust does not catch. Two threads each hold a lock the other needs, neither can make progress, and the program hangs in production at 3am.

The standard fix is to pick a global acquisition order and enforce it by code review — fragile, easy to regress, and invisible at the call site. This crate turns that convention into a type-level invariant: every lock is tagged with a level, the levels form a DAG, and acquiring a lock consumes a proof token that records your current position in the DAG. Acquiring out of order is a type error, not a runtime hang.

A complementary runtime mode handles the case the type system cannot — dynamic collections like HashMap<String, Mutex<T>> where the acquisition order is known only at runtime. There, ascending keys are checked on each acquisition.

Features#

Compile-time lock levels#

Declare the lock hierarchy as a DAG. A -> B means: while holding A, you may acquire B. Both A and B can also be the first lock acquired.

use lock_ordering::{define_lock_levels, LockedAt, LockLevel, MutualExclusion};
use lock_ordering::lock::MutexLockLevel;
use std::sync::Mutex;

define_lock_levels! {
    ConfigCache -> MetricsCounter,
}

impl LockLevel for ConfigCache { type Method = MutualExclusion; }
impl MutexLockLevel for ConfigCache { type Mutex = Mutex<String>; }

impl LockLevel for MetricsCounter { type Method = MutualExclusion; }
impl MutexLockLevel for MetricsCounter { type Mutex = Mutex<u64>; }

let config = Mutex::new(String::from("v1"));
let counter = Mutex::new(0u64);

// SAFETY: no other LockedAt live on this thread.
let locked = unsafe { LockedAt::new() };

let guard_cfg = locked.with_lock::<ConfigCache>(&config).unwrap();
let locked_cfg = LockedAt::from_guard(&guard_cfg);
let mut guard_ctr = locked_cfg.with_lock::<MetricsCounter>(&counter).unwrap();
*guard_ctr += 1;

let _ = guard_ctr.release();
let _ = guard_cfg.release();

Acquiring MetricsCounter before ConfigCache is rejected at compile time — the required LockBefore bound is not satisfied.

Strict ordering with `=>`#

A -> B makes B acquirable both standalone and after A. Use => when a level must only ever be acquired underneath a specific parent:

define_lock_levels! {
    Session -> Transaction,    // both are roots
    Transaction => Row,        // Row REQUIRES Transaction — never a root
}

Acquiring Row as the first lock in a thread is a compile error.

Cycle detection in the macro#

define_lock_levels! {
    A -> B,
    B -> A,
}
// error: cycle detected: A -> B -> A

RwLock support#

use lock_ordering::{LockLevel, ReadWrite};
use lock_ordering::lock::RwLockLevel;

impl LockLevel for CacheIndex { type Method = ReadWrite; }
impl RwLockLevel for CacheIndex { type RwLock = std::sync::RwLock<Vec<u32>>; }

let read_guard = locked.with_read_lock::<CacheIndex>(&rwlock).unwrap();
let write_guard = locked.with_write_lock::<CacheIndex>(&rwlock).unwrap();

Async (tokio)#

Enable the async feature. wait_for_lock / wait_for_read / wait_for_write mirror their sync counterparts and yield instead of blocking.

let guard_a = locked.wait_for_lock::<AsyncLockA>(&mutex_a).await;
let locked_a = LockedAt::from_guard(&guard_a);
let guard_b = locked_a.wait_for_lock::<AsyncLockB>(&mutex_b).await;

Runtime ordered acquisition#

For HashMap<K, Mutex<V>> and similar collections, the levels are all the same — the order has to come from the keys at runtime. OrderedLock pairs a lock with an ordering key, and OrderedAt enforces strictly-ascending keys at each acquisition:

use lock_ordering::ordered::{OrderedAt, OrderedLock};

let apple  = OrderedLock { key: "apple",  lock: Mutex::new(1u32) };
let banana = OrderedLock { key: "banana", lock: Mutex::new(2u32) };
let cherry = OrderedLock { key: "cherry", lock: Mutex::new(3u32) };

let locked = unsafe { LockedAt::new() };
let g_a = locked.with_ordered_lock::<MapLevel, _>(&apple).unwrap();

let ord_a = OrderedAt::from_guard(&g_a);
let g_b = ord_a.with_lock::<MapLevel>(&banana).unwrap();

let ord_b = OrderedAt::from_guard(&g_b);
let g_c = ord_b.with_lock::<MapLevel>(&cherry).unwrap();
// Acquiring a key <= the previous one panics.

Opt in to same-level chaining with impl LockAfter<MapLevel> for MapLevel {}, or leave it out to disallow it. OrderedAt::into_locked_at() exits ordered mode and recovers the compile-time token.

`mem::forget` soundness#

LockedAt::from_guard(&guard) borrows the guard for the lifetime of the derived token, so the borrow checker rejects mem::forget(guard) while a child token is live. This closes the soundness gap described in akonradi/lock-ordering#2.

Acknowledgements#

The core design — typed lock levels, LockedAt, and the LockAfter / LockBefore relation — is adapted from akonradi/lock-ordering by Alex Bakon (MIT). This crate diverges in three ways:

LockedAt::new is unsafe, making the "one token per thread" invariant an explicit obligation on the caller rather than an implicit assumption.
with_lock consumes the token by value and a new one is recovered through from_guard, which borrows the guard — preventing the mem::forget unsoundness in the original. The borrow-the-guard approach is inspired by the discussion in akonradi/lock-ordering#2.
A define_lock_levels! proc-macro generates the full transitive LockAfter closure and runs cycle detection, replacing the manual impl_transitive_lock_order! declarative macro.

The runtime ordered acquisition system (OrderedLock / OrderedAt) is new.

Configure Feed