Crate surelock 

Surelock: Deadlock-Free Locks for Rust

Surelock prevents deadlocks by breaking the circular-wait Coffman condition via two complementary mechanisms:

1. LockSet – granular atomic acquisition of multiple locks at the same level, sorted by a monotonic LockId assigned at creation. Safe by construction, infallible.
2. Levels – coarse types declaring a compile-time ordering via LockAfter trait bounds. A consumed-and-re-emitted MutexKey tracks the current level as a type parameter. Wrong-order acquisition is a compile error, not a runtime failure.

Every lock call is infallible or doesn’t compile. No Result, no Option, no panic on any lock acquisition path.

Quick Start

use surelock::{key::lock_scope, mutex::Mutex};

let counter: Mutex<u32> = Mutex::new(0);

lock_scope(|key| {
    let (mut guard, _key) = key.lock(&counter);
    *guard += 1;
});

Usage Guide

Locking a Single Mutex

Claim a KeyHandle, then use scope to enter a scope. Inside the scope, lock acquires the mutex via a closure:

use surelock::{key_handle::KeyHandle, mutex::Mutex};

let counter: Mutex<u32> = Mutex::new(0);

let mut handle = KeyHandle::claim();
handle.scope(|key| {
    let (val, _key) = key.lock_with(&counter, |mut guard| {
        *guard += 1;
        *guard
    });
    assert_eq!(val, 1);
});

Locking Multiple Mutexes Atomically

Use a LockSet to acquire multiple locks at once, sorted by LockId. This prevents deadlocks by construction – the order is always consistent:

use surelock::{key_handle::KeyHandle, mutex::Mutex, set::LockSet};

let a: Mutex<u32> = Mutex::new(10);
let b: Mutex<u32> = Mutex::new(20);

let set = LockSet::new((&a, &b));

let mut handle = KeyHandle::claim();
handle.scope(|key| {
    let ((ga, gb), _key) = key.lock(&set);
    assert_eq!(*ga + *gb, 30);
});

Cross-Level Incremental Acquisition

Use Mutex::new_higher to create mutexes at incrementing levels. The MutexKey tracks the current level and the compiler rejects wrong-order acquisition:

use surelock::{key_handle::KeyHandle, level::Level, mutex::Mutex};

let config: Mutex<u32> = Mutex::new(42);
let account: Mutex<u32, Level<1>> = Mutex::new_higher(100u32, &config);

let mut handle = KeyHandle::claim();
handle.scope(|key| {
    // Read config first (Level<0>)
    let (cfg_val, key) = key.lock_with(&config, |g| *g);

    // Then lock account (Level<1>)
    let ((), _key) = key.lock_with(&account, |mut acct| {
        *acct += cfg_val;
    });
});

Nested Scopes

Use subscope to create a nested locking context within an existing scope. The inner key inherits the outer key’s level, and the outer key is consumed for the duration (preventing concurrent use):

use surelock::{key_handle::KeyHandle, mutex::Mutex};

let config: Mutex<u32> = Mutex::new(10);
let account = Mutex::new_higher(0u32, &config);

let mut handle = KeyHandle::claim();
handle.scope(|key| {
    let (val, key) = key.lock_with(&config, |g| *g);

    let (result, _key) = key.subscope(|inner_key| {
        let (r, _) = inner_key.lock_with(&account, |mut acct| {
            *acct = val;
            *acct
        });
        r
    });
    assert_eq!(result, 10);
});

Type Lifecycle

┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
│ Explicit multi-core
                      │
│      Locksmith
        (forge)       │   ┌ ─ ─ ─ ─ ─ ─ ─ ┐
│          │              │ std (default)
           ▼          │                   │
│     KeyVoucher          │   KeyHandle
      (deliver)       │        (claim)    │
└ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ┘   └ ─ ─ ─ ┼ ─ ─ ─ ┘
          │                       │
          └────────────┬──────────┘
                       │
                       ▼
                    MutexKey
                    (scope)
                       │
                       ├───▶ MutexGuard(s)
                       │      (access)
                       ▼
                    MutexKey
                   (subscope)
                       │
                       ├───▶ MutexGuard(s)
                       │      (access)
                       ▼
                      ...

Type	Role	Created by
Locksmith	Factory, issues vouchers (singleton)	Locksmith::new
KeyVoucher	Transferable token (Send)	Locksmith::issue
KeyHandle	Per-thread scope creator (!Send)	KeyHandle::claim or KeyVoucher::redeem
MutexKey	Per-scope lock token, consumed/re-emitted	handle.scope
MutexGuard	RAII access to protected data	key.lock or key.lock_with

Key Patterns

// Enter a scope
handle.scope(|key| { ... });

// Lock (single mutex or LockSet, guards returned)
let (guard, key) = key.lock(&mutex);
let ((ga, gb), key) = key.lock(&set);

// Lock with closure (one-shot, sorts inline)
let (val, key) = key.lock_with(&mutex, |guard| *guard);

// Nested sub-scope
let (result, key) = key.subscope(|inner_key| { ... });

Construction

Mutex::new(data)                     // Level<0>, default backend
Mutex::new_higher(data, &parent)      // parent.level + 1
Mutex::new_higher(data, (&a, &b))     // max(levels) + 1

// Method syntax (also works with Arc, Rc, Box)
parent.new_higher(data)               // parent.level + 1, inherits backend
(&a, &b).new_higher(data)             // max(levels) + 1

Levels

Locks are ordered by Level<N>, a const-generic type. Create semantic aliases for your domain:

use surelock::level::Level;

type Database = Level<0>;
type Table = Level<1>;
type Row = Level<2>;

Use Mutex::new_higher to chain levels automatically:

use surelock::mutex::Mutex;

let db: Mutex<String> = Mutex::new("mydb".into());
let table = Mutex::new_higher("users".to_string(), &db);  // Level<1>
let row = Mutex::new_higher(42u64, &table);                 // Level<2>

Backend Agnostic

Mutex<T, Lvl, R> is generic over any RawMutex implementation. Lvl defaults to Base (= Level<0>) and R defaults to StdMutex on std. Specify just the level to use the default backend: Mutex<u32, Level<3>>. For no_std, enable the lock-api feature and use spin, parking_lot, or any other lock_api::RawMutex backend directly.

Scope Entry

There are two ways to enter a lock scope:

• Ambient: lock_scope / try_lock_scope – convenient, runtime nesting check on std (panic / None).
• Capability-based: KeyHandle::scope – static nesting prevention via &mut self (compile error). Works on no_std without thread_local!.

On no_std, the ambient entry points are not available. KeyHandle is the only entry mechanism, providing static nesting prevention via &mut self. See MutexKey::subscope for safe nesting within an existing scope on all targets.

For a comprehensive guide to no_std usage, see NO_STD_GUIDE.md in the repository.

Prior Art

Surelock builds on ideas from two libraries:

• happylock (botahamec, CC0-1.0) – introduced the LockCollection pattern: a capability token (ThreadKey) combined with sorted multi-lock acquisition. Surelock borrows this pattern, replacing address-based ordering with a stable monotonic LockId counter, dropping the std requirement, and removing unsafe from the public API.

• lock_tree (Google Fuchsia, BSD) – introduced LockAfter<A> traits for compile-time ordering of lock categories, enforced via witness-token consumption. Surelock extends this with same-level multi-lock via LockSet and makes levels opt-in with a Base default.

Neither library alone covers both dynamic multi-lock and static ordering. The combination – with stable IDs and no_std throughout – is surelock’s contribution.

Grounded in Coffman, Elphick, and Shoshani’s System Deadlocks (1971).

For detailed comparisons, see the design/comparison/ directory in the repository.

Modules

acquirable

Internal trait for types that can be locked atomically. See Acquirable. Most users do not need to interact with this trait directly.

id

Monotonic lock identity.

key

Scope token for ordered lock acquisition.

key_handle

Per-thread capability for lock scope creation. See KeyHandle.

key_voucher

Transferable token redeemable for a KeyHandle.

level

Lock levels and ordering traits.

locksmith

Factory for distributing KeyVouchers across execution contexts.

mutex

Deadlock-free mutex, generic over lock level and backend.

raw_mutex

Backend trait for raw mutex implementations.

set

Pre-sorted lock collection.