Skip to main content

wgpu_core/lock/
ranked.rs

1//! Lock types that enforce well-ranked lock acquisition order.
2//!
3//! This module's [`Mutex`] and [`RwLock` types are instrumented to check that
4//! `wgpu-core` acquires locks according to their rank, to prevent deadlocks. To
5//! use it, put `--cfg wgpu_validate_locks` in `RUSTFLAGS`.
6//!
7//! The [`LockRank`] constants in the [`lock::rank`] module describe edges in a
8//! directed graph of lock acquisitions: each lock's rank says, if this is the most
9//! recently acquired lock that you are still holding, then these are the locks you
10//! are allowed to acquire next.
11//!
12//! As long as this graph doesn't have cycles, any number of threads can acquire
13//! locks along paths through the graph without deadlock:
14//!
15//! - Assume that if a thread is holding a lock, then it will either release it,
16//!   or block trying to acquire another one. No thread just sits on its locks
17//!   forever for unrelated reasons. If it did, then that would be a source of
18//!   deadlock "outside the system" that we can't do anything about.
19//!
20//! - This module asserts that threads acquire and release locks in a stack-like
21//!   order: a lock is dropped only when it is the *most recently acquired* lock
22//!   *still held* - call this the "youngest" lock. This stack-like ordering
23//!   isn't a Rust requirement; Rust lets you drop guards in any order you like.
24//!   This is a restriction we impose.
25//!
26//! - Consider the directed graph whose nodes are locks, and whose edges go from
27//!   each lock to its permitted followers, the locks in its [`LockRank::followers`]
28//!   set. The definition of the [`lock::rank`] module's [`LockRank`] constants
29//!   ensures that this graph has no cycles, including trivial cycles from a node to
30//!   itself.
31//!
32//! - This module then asserts that each thread attempts to acquire a lock only if
33//!   it is among its youngest lock's permitted followers. Thus, as a thread
34//!   acquires locks, it must be traversing a path through the graph along its
35//!   edges.
36//!
37//! - Because there are no cycles in the graph, whenever one thread is blocked
38//!   waiting to acquire a lock, that lock must be held by a different thread: if
39//!   you were allowed to acquire a lock you already hold, that would be a cycle in
40//!   the graph.
41//!
42//! - Furthermore, because the graph has no cycles, as we work our way from each
43//!   thread to the thread it is blocked waiting for, we must eventually reach an
44//!   end point: there must be some thread that is able to acquire its next lock, or
45//!   that is about to release a lock.
46//!
47//! Thus, the system as a whole is always able to make progress: it is free of
48//! deadlocks.
49//!
50//! Note that this validation only monitors each thread's behavior in isolation:
51//! there's only thread-local state, nothing communicated between threads. So we
52//! don't detect deadlocks, per se, only the potential to cause deadlocks. This
53//! means that the validation is conservative, but more reproducible, since it's not
54//! dependent on any particular interleaving of execution.
55//!
56//! [`lock::rank`]: crate::lock::rank
57
58use core::{cell::Cell, fmt, ops, panic::Location};
59
60use super::rank::LockRank;
61
62pub use LockState as RankData;
63
64/// A `Mutex` instrumented for deadlock prevention.
65///
66/// This is just a wrapper around a [`wgpu_sync::Mutex`], along with
67/// its rank in the `wgpu_core` lock ordering.
68///
69/// For details, see [the module documentation][self].
70pub struct Mutex<T> {
71    inner: wgpu_sync::Mutex<T>,
72    rank: LockRank,
73}
74
75/// A guard produced by locking [`Mutex`].
76///
77/// This is just a wrapper around a [`wgpu_sync::MutexGuard`], along
78/// with the state needed to track lock acquisition.
79///
80/// For details, see [the module documentation][self].
81pub struct MutexGuard<'a, T> {
82    inner: wgpu_sync::MutexGuard<'a, T>,
83    // Never read, but `Drop` has important side effects.
84    #[cfg_attr(all(wgpu_validate_locks, not(miri)), expect(unused))]
85    saved: LockStateGuard,
86}
87
88std::thread_local! {
89    static LOCK_STATE: Cell<LockState> = const { Cell::new(LockState::INITIAL) };
90}
91
92/// Per-thread state for the deadlock checker.
93#[derive(Debug, Copy, Clone)]
94pub struct LockState {
95    /// The last lock we acquired, and where.
96    last_acquired: Option<(LockRank, &'static Location<'static>)>,
97
98    /// The number of locks currently held.
99    ///
100    /// This is used to enforce stack-like lock acquisition and release.
101    depth: u32,
102}
103
104impl LockState {
105    const INITIAL: LockState = LockState {
106        last_acquired: None,
107        depth: 0,
108    };
109}
110
111/// A container that restores a [`LockState`] when dropped.
112///
113/// This type serves two purposes:
114///
115/// - Operations would like to be able to destructure lock guards and
116///   reassemble their pieces into new guards, but if the guard type
117///   itself implements `Drop`, we can't destructure it without unsafe
118///   code or pointless `Option`s whose state is almost always statically
119///   known.
120///
121/// - We can just implement `Drop` for this type once, and then use it in lock
122///   guards, rather than implementing `Drop` separately for each guard type.
123struct LockStateGuard(LockState);
124
125impl Drop for LockStateGuard {
126    fn drop(&mut self) {
127        release(self.0)
128    }
129}
130
131/// Check and record the acquisition of a lock with `new_rank`.
132///
133/// Check that acquiring a lock with `new_rank` is permitted at this point, and
134/// update the per-thread state accordingly.
135///
136/// Return the `LockState` that must be restored when this thread is released.
137fn acquire(new_rank: LockRank, location: &'static Location<'static>) -> LockState {
138    let result = LOCK_STATE.try_with(|cell| {
139        let state = cell.get();
140        // Initially, it's fine to acquire any lock. So we only
141        // need to check when `last_acquired` is `Some`.
142        if let Some((ref last_rank, ref last_location)) = state.last_acquired {
143            assert!(
144                last_rank.followers.contains(new_rank.bit),
145                "Attempt to acquire nested mutexes in wrong order:\n\
146                 last locked {:<35} at {}\n\
147                 now locking {:<35} at {}\n\
148                 Locking {} after locking {} is not permitted.",
149                last_rank.bit.member_name(),
150                last_location,
151                new_rank.bit.member_name(),
152                location,
153                new_rank.bit.member_name(),
154                last_rank.bit.member_name(),
155            );
156        }
157        cell.set(LockState {
158            last_acquired: Some((new_rank, location)),
159            depth: state.depth + 1,
160        });
161        state
162    });
163    result.unwrap_or(LockState::INITIAL)
164}
165
166/// Record the release of a lock whose saved state was `saved`.
167///
168/// Check that locks are being acquired in stacking order, and update the
169/// per-thread state accordingly.
170fn release(saved: LockState) {
171    let _ = LOCK_STATE.try_with(|cell| {
172        let saved_info = saved.last_acquired;
173
174        let prior = cell.replace(saved);
175
176        let (prior_rank, prior_location) = prior
177            .last_acquired
178            .expect("Releasing a lock, but no acquisition recorded");
179
180        // Although Rust allows mutex guards to be dropped in any
181        // order, this analysis requires that locks be acquired and
182        // released in stack order: the next lock to be released must be
183        // the most recently acquired lock still held.
184
185        match (saved.depth, saved_info) {
186            (saved_depth @ 0, None) => {
187                assert_eq!(
188                    prior.depth,
189                    saved_depth + 1,
190                    "Lock not released in stacking order\n\
191                released {:<35} locked at {:?}\n\
192                when not expecting any locks to be held\n",
193                    prior_rank.bit.member_name(),
194                    prior_location,
195                );
196            }
197            (0, Some(_)) => {
198                panic!("Found previous lock acquisition information, but saved.depth = 0");
199            }
200            (saved_depth, Some((saved_rank, saved_location))) => {
201                assert_eq!(
202                    prior.depth,
203                    saved_depth + 1,
204                    "Lock not released in stacking order\n\
205                expecting release of {:<35} locked at {:?}\n\
206                but instead released {:<35} locked at {:?}\n",
207                    saved_rank.bit.member_name(),
208                    saved_location,
209                    prior_rank.bit.member_name(),
210                    prior_location,
211                );
212            }
213            (saved_depth, None) => {
214                panic!(
215                "Found saved.depth = {saved_depth}, but no previous lock acquisition information"
216            );
217            }
218        }
219    });
220}
221
222impl<T> Mutex<T> {
223    pub fn new(rank: LockRank, value: T) -> Mutex<T> {
224        Mutex {
225            inner: wgpu_sync::Mutex::new(value),
226            rank,
227        }
228    }
229
230    #[track_caller]
231    pub fn lock(&self) -> MutexGuard<'_, T> {
232        let saved = acquire(self.rank, Location::caller());
233        MutexGuard {
234            inner: self.inner.lock(),
235            saved: LockStateGuard(saved),
236        }
237    }
238
239    pub fn into_inner(self) -> T {
240        self.inner.into_inner()
241    }
242}
243
244impl<'a, T> ops::Deref for MutexGuard<'a, T> {
245    type Target = T;
246
247    fn deref(&self) -> &Self::Target {
248        self.inner.deref()
249    }
250}
251
252impl<'a, T> ops::DerefMut for MutexGuard<'a, T> {
253    fn deref_mut(&mut self) -> &mut Self::Target {
254        self.inner.deref_mut()
255    }
256}
257
258impl<T: fmt::Debug> fmt::Debug for Mutex<T> {
259    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
260        self.inner.fmt(f)
261    }
262}
263
264/// An `RwLock` instrumented for deadlock prevention.
265///
266/// This is just a wrapper around a [`wgpu_sync::RwLock`], along with
267/// its rank in the `wgpu_core` lock ordering.
268///
269/// For details, see [the module documentation][self].
270pub struct RwLock<T> {
271    inner: wgpu_sync::RwLock<T>,
272    rank: LockRank,
273}
274
275/// A read guard produced by locking [`RwLock`] for reading.
276///
277/// This is just a wrapper around a [`wgpu_sync::RwLockReadGuard`], along with
278/// the state needed to track lock acquisition.
279///
280/// For details, see [the module documentation][self].
281pub struct RwLockReadGuard<'a, T> {
282    inner: wgpu_sync::RwLockReadGuard<'a, T>,
283    saved: LockStateGuard,
284}
285
286/// A write guard produced by locking [`RwLock`] for writing.
287///
288/// This is just a wrapper around a [`wgpu_sync::RwLockWriteGuard`], along
289/// with the state needed to track lock acquisition.
290///
291/// For details, see [the module documentation][self].
292pub struct RwLockWriteGuard<'a, T> {
293    inner: wgpu_sync::RwLockWriteGuard<'a, T>,
294    // Never read, but `Drop` has important side effects.
295    #[cfg_attr(all(wgpu_validate_locks, not(miri)), expect(unused))]
296    saved: LockStateGuard,
297}
298
299impl<T> RwLock<T> {
300    pub fn new(rank: LockRank, value: T) -> RwLock<T> {
301        RwLock {
302            inner: wgpu_sync::RwLock::new(value),
303            rank,
304        }
305    }
306
307    #[track_caller]
308    pub fn read(&self) -> RwLockReadGuard<'_, T> {
309        let saved = acquire(self.rank, Location::caller());
310        RwLockReadGuard {
311            inner: self.inner.read(),
312            saved: LockStateGuard(saved),
313        }
314    }
315
316    #[track_caller]
317    pub fn write(&self) -> RwLockWriteGuard<'_, T> {
318        let saved = acquire(self.rank, Location::caller());
319        RwLockWriteGuard {
320            inner: self.inner.write(),
321            saved: LockStateGuard(saved),
322        }
323    }
324
325    /// Force an read-unlock operation on this lock.
326    ///
327    /// Safety:
328    /// - A read lock must be held which is not held by a guard.
329    pub unsafe fn force_unlock_read(&self, data: RankData) {
330        release(data);
331        unsafe { self.inner.force_unlock_read() };
332    }
333
334    /// Returns a reference to the underlying [`wgpu_sync::RwLock`].
335    ///
336    /// Marked as unsafe because it allows bypassing the rank system,
337    /// defeating the purpose of this type.
338    pub unsafe fn underlying(&self) -> &wgpu_sync::RwLock<T> {
339        &self.inner
340    }
341}
342
343impl<'a, T> RwLockReadGuard<'a, T> {
344    // Forget the read guard, leaving the lock in a locked state with no guard.
345    //
346    // Equivalent to std::mem::forget, but preserves the information about the lock
347    // rank.
348    pub fn forget(this: Self) -> RankData {
349        // Skip `Drop` for both the actual lock guard (`this.inner`) and the
350        // rank-checking state guard (`this.saved`)
351        let saved = core::mem::ManuallyDrop::new(this.saved);
352        core::mem::forget(this.inner);
353
354        // Return the `RankData` so the caller can pass it to `force_unlock_read`.
355        saved.0
356    }
357}
358
359impl<T: fmt::Debug> fmt::Debug for RwLock<T> {
360    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
361        self.inner.fmt(f)
362    }
363}
364
365impl<'a, T> ops::Deref for RwLockReadGuard<'a, T> {
366    type Target = T;
367
368    fn deref(&self) -> &Self::Target {
369        self.inner.deref()
370    }
371}
372
373impl<'a, T> ops::Deref for RwLockWriteGuard<'a, T> {
374    type Target = T;
375
376    fn deref(&self) -> &Self::Target {
377        self.inner.deref()
378    }
379}
380
381impl<'a, T> ops::DerefMut for RwLockWriteGuard<'a, T> {
382    fn deref_mut(&mut self) -> &mut Self::Target {
383        self.inner.deref_mut()
384    }
385}
386
387#[cfg(test)]
388mod tests {
389    use super::Mutex;
390    use crate::lock::rank;
391
392    /// Locks can be acquired in the order indicated by their ranks.
393    #[test]
394    fn permitted() {
395        let lock1 = Mutex::new(rank::PAWN, ());
396        let lock2 = Mutex::new(rank::ROOK, ());
397
398        let _guard1 = lock1.lock();
399        let _guard2 = lock2.lock();
400    }
401
402    /// Locks can only be acquired in the order indicated by their ranks.
403    #[test]
404    #[should_panic(expected = "Locking pawn after locking rook")]
405    fn forbidden_unrelated() {
406        let lock1 = Mutex::new(rank::ROOK, ());
407        let lock2 = Mutex::new(rank::PAWN, ());
408
409        let _guard1 = lock1.lock();
410        let _guard2 = lock2.lock();
411    }
412
413    /// Lock acquisitions can't skip ranks.
414    ///
415    /// These two locks *could* be acquired in this order, but only if other locks
416    /// are acquired in between them. Skipping ranks isn't allowed.
417    #[test]
418    #[should_panic(expected = "Locking knight after locking pawn")]
419    fn forbidden_skip() {
420        let lock1 = Mutex::new(rank::PAWN, ());
421        let lock2 = Mutex::new(rank::KNIGHT, ());
422
423        let _guard1 = lock1.lock();
424        let _guard2 = lock2.lock();
425    }
426
427    /// Locks can be acquired and released in a stack-like order.
428    #[test]
429    fn stack_like() {
430        let lock1 = Mutex::new(rank::PAWN, ());
431        let lock2 = Mutex::new(rank::ROOK, ());
432        let lock3 = Mutex::new(rank::BISHOP, ());
433
434        let guard1 = lock1.lock();
435        let guard2 = lock2.lock();
436        drop(guard2);
437
438        let guard3 = lock3.lock();
439        drop(guard3);
440        drop(guard1);
441    }
442
443    /// Locks can only be acquired and released in a stack-like order.
444    #[test]
445    #[should_panic(expected = "Lock not released in stacking order")]
446    fn non_stack_like() {
447        let lock1 = Mutex::new(rank::PAWN, ());
448        let lock2 = Mutex::new(rank::ROOK, ());
449
450        let guard1 = lock1.lock();
451        let guard2 = lock2.lock();
452
453        // Avoid a double panic from dropping this while unwinding due to the panic
454        // we're testing for.
455        core::mem::forget(guard2);
456
457        drop(guard1);
458    }
459}