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}