Module wgpu_core::lock::ranked

Lock types that enforce well-ranked lock acquisition order.

This module’s Mutex and [RwLock types are instrumented to check that wgpu-core acquires locks according to their rank, to prevent deadlocks. To use it, put --cfg wgpu_validate_locks in RUSTFLAGS.

The LockRank constants in the lock::rank module describe edges in a directed graph of lock acquisitions: each lock’s rank says, if this is the most recently acquired lock that you are still holding, then these are the locks you are allowed to acquire next.

As long as this graph doesn’t have cycles, any number of threads can acquire locks along paths through the graph without deadlock:

• Assume that if a thread is holding a lock, then it will either release it, or block trying to acquire another one. No thread just sits on its locks forever for unrelated reasons. If it did, then that would be a source of deadlock “outside the system” that we can’t do anything about.

• This module asserts that threads acquire and release locks in a stack-like order: a lock is dropped only when it is the most recently acquired lock still held - call this the “youngest” lock. This stack-like ordering isn’t a Rust requirement; Rust lets you drop guards in any order you like. This is a restriction we impose.

• Consider the directed graph whose nodes are locks, and whose edges go from each lock to its permitted followers, the locks in its LockRank::followers set. The definition of the lock::rank module’s LockRank constants ensures that this graph has no cycles, including trivial cycles from a node to itself.

• This module then asserts that each thread attempts to acquire a lock only if it is among its youngest lock’s permitted followers. Thus, as a thread acquires locks, it must be traversing a path through the graph along its edges.

• Because there are no cycles in the graph, whenever one thread is blocked waiting to acquire a lock, that lock must be held by a different thread: if you were allowed to acquire a lock you already hold, that would be a cycle in the graph.

• Furthermore, because the graph has no cycles, as we work our way from each thread to the thread it is blocked waiting for, we must eventually reach an end point: there must be some thread that is able to acquire its next lock, or that is about to release a lock.

Thus, the system as a whole is always able to make progress: it is free of deadlocks.

Note that this validation only monitors each thread’s behavior in isolation: there’s only thread-local state, nothing communicated between threads. So we don’t detect deadlocks, per se, only the potential to cause deadlocks. This means that the validation is conservative, but more reproducible, since it’s not dependent on any particular interleaving of execution.

Structs

• LockState 🔒
  Per-thread state for the deadlock checker.
• LockStateGuard 🔒
  A container that restores a LockState when dropped.
• Mutex
  A Mutex instrumented for deadlock prevention.
• MutexGuard
  A guard produced by locking Mutex.
• RwLock
  An RwLock instrumented for deadlock prevention.
• RwLockReadGuard
  A read guard produced by locking RwLock for reading.
• RwLockWriteGuard
  A write guard produced by locking RwLock for writing.

Constants

• LOCK_STATE 🔒

Functions

• acquire 🔒
  Check and record the acquisition of a lock with new_rank.
• release 🔒
  Record the release of a lock whose saved state was saved.