parking_lot_core/parking_lot.rs
1use crate::thread_parker::{ThreadParker, ThreadParkerT, UnparkHandleT};
2use crate::word_lock::WordLock;
3use core::{
4 cell::{Cell, UnsafeCell},
5 mem,
6 ptr::{self, NonNull},
7 sync::atomic::{AtomicPtr, AtomicUsize, Ordering},
8};
9use smallvec::SmallVec;
10use std::time::Instant;
11
12static NUM_THREADS: AtomicUsize = AtomicUsize::new(0);
13
14/// Aborts the process if it is dropped while unwinding.
15///
16/// Parking-lot operations manipulate shared intrusive state without unwind
17/// guards. Once an operation has started, unwinding could leave bucket locks
18/// held, queue links inconsistent, or a transferred `ThreadData` inaccessible.
19struct AbortOnPanic;
20
21impl AbortOnPanic {
22 /// Prevents the guard from being dropped after a successful operation.
23 #[inline]
24 fn disarm(self) {
25 mem::forget(self);
26 }
27}
28
29impl Drop for AbortOnPanic {
30 fn drop(&mut self) {
31 panic!("aborting due to panic in parking lot");
32 }
33}
34
35/// Holds the pointer to the currently active `HashTable`.
36///
37/// # Safety
38///
39/// Except for the initial value of null, it must always point to a valid `HashTable` instance.
40/// Any `HashTable` this global static has ever pointed to must never be freed.
41static HASHTABLE: AtomicPtr<HashTable> = AtomicPtr::new(ptr::null_mut());
42
43// Even with 3x more buckets than threads, the memory overhead per thread is
44// still only a few hundred bytes per thread.
45const LOAD_FACTOR: usize = 3;
46
47struct HashTable {
48 // Hash buckets for the table
49 entries: Box<[Bucket]>,
50
51 // Number of bits used for the hash function
52 hash_bits: u32,
53
54 // Previous table. This is only kept to keep leak detectors happy.
55 _prev: Option<NonNull<HashTable>>,
56}
57
58impl HashTable {
59 #[inline]
60 fn new(num_threads: usize, prev: Option<NonNull<HashTable>>) -> Box<HashTable> {
61 let new_size = (num_threads * LOAD_FACTOR).next_power_of_two();
62 let hash_bits = 0usize.leading_zeros() - new_size.leading_zeros() - 1;
63
64 let mut entries = Vec::with_capacity(new_size);
65 for _ in 0..new_size {
66 entries.push(Bucket::new());
67 }
68
69 Box::new(HashTable {
70 entries: entries.into_boxed_slice(),
71 hash_bits,
72 _prev: prev,
73 })
74 }
75}
76
77#[repr(align(64))]
78struct Bucket {
79 // Lock protecting the queue
80 mutex: WordLock,
81
82 // Linked list of threads waiting on this bucket
83 queue_head: Cell<Option<NonNull<ThreadData>>>,
84 queue_tail: Cell<Option<NonNull<ThreadData>>>,
85}
86
87impl Bucket {
88 #[inline]
89 pub fn new() -> Self {
90 Self {
91 mutex: WordLock::new(),
92 queue_head: Cell::new(None),
93 queue_tail: Cell::new(None),
94 }
95 }
96}
97
98// A ThreadData has two stable ownership states:
99//
100// * While it is not linked into a bucket queue, it is owned by its thread and
101// its non-atomic fields are unshared.
102// * While it is linked into a bucket queue, it is owned by the parking lot. Its
103// queue fields and lifetime are protected by the lock of the bucket that
104// currently contains it.
105//
106// To transfer ownership to the parking lot, the local thread initializes the
107// queue fields and prepares the parker while holding the destination bucket
108// lock, then links the ThreadData into the queue. Once linked, the local thread
109// must not access fields owned by the parking lot.
110//
111// To transfer ownership back, an unparker removes the ThreadData from the queue,
112// writes the result fields, and calls `unpark_lock` while still holding the
113// bucket lock. It must not access the ThreadData after `unpark_lock`, since the
114// parked thread may immediately resume and destroy it. The returned
115// UnparkHandle remains usable without access to the ThreadData. A successful
116// return from `park` or `park_until` completes the transfer back to the local
117// thread and synchronizes with the unparker's preceding writes.
118//
119// A timeout does not by itself transfer ownership back. The local thread must
120// use the atomic key to find and lock the current bucket, resolve any concurrent
121// unpark or requeue, and remove itself from the queue before it again owns the
122// ThreadData.
123struct ThreadData {
124 // Accessed concurrently through the ThreadParker protocol rather than the
125 // bucket lock.
126 parker: ThreadParker,
127
128 // Written by the parking lot under the bucket lock. This is atomic because
129 // a timing-out local thread must read it before regaining ownership, and a
130 // concurrent requeue may change it.
131 key: AtomicUsize,
132
133 // Fields transferred between local ownership and parking-lot ownership as
134 // described above.
135 state: UnsafeCell<ThreadDataState>,
136}
137
138struct ThreadDataState {
139 // Linked list of parked threads. Accessed only while holding the lock of
140 // the bucket that contains this ThreadData.
141 next_in_queue: Option<NonNull<ThreadData>>,
142
143 // Written by the parking lot before `unpark_lock` and read locally only
144 // after a successful return from the parker.
145 unpark_token: UnparkToken,
146
147 // Initialized before linking and subsequently read only under the bucket
148 // lock.
149 park_token: ParkToken,
150
151 // Deadlock detector fields governed by the same ownership rules.
152 #[cfg(feature = "deadlock_detection")]
153 deadlock_data: deadlock::DeadlockData,
154}
155
156impl ThreadData {
157 fn new() -> ThreadData {
158 // Keep track of the total number of live ThreadData objects and resize
159 // the hash table accordingly.
160 let num_threads = NUM_THREADS.fetch_add(1, Ordering::Relaxed) + 1;
161 grow_hashtable(num_threads);
162
163 ThreadData {
164 parker: ThreadParker::new(),
165 key: AtomicUsize::new(0),
166 state: UnsafeCell::new(ThreadDataState {
167 next_in_queue: None,
168 unpark_token: DEFAULT_UNPARK_TOKEN,
169 park_token: DEFAULT_PARK_TOKEN,
170 #[cfg(feature = "deadlock_detection")]
171 deadlock_data: deadlock::DeadlockData::new(),
172 }),
173 }
174 }
175
176 /// Returns the state under the ownership model described above.
177 ///
178 /// # Safety
179 ///
180 /// The caller must have exclusive access to the state. Either the current
181 /// thread must own this `ThreadData`, or the parking lot must own it and the
182 /// caller must hold the lock that protects it.
183 #[inline]
184 #[allow(clippy::mut_from_ref)]
185 unsafe fn state(&self) -> &mut ThreadDataState {
186 unsafe { self.state.get().as_mut_unchecked() }
187 }
188}
189
190// Invokes the given closure with a reference to the current thread `ThreadData`.
191#[inline(always)]
192fn with_thread_data<T>(f: impl FnOnce(&ThreadData) -> T) -> T {
193 // Unlike word_lock::ThreadData, parking_lot::ThreadData is always expensive
194 // to construct. Try to use a thread-local version if possible. Otherwise just
195 // create a ThreadData on the stack
196 let mut thread_data_storage = None;
197 thread_local!(static THREAD_DATA: ThreadData = ThreadData::new());
198 let thread_data = THREAD_DATA
199 .try_with(|thread_data| NonNull::from(thread_data))
200 .unwrap_or_else(|_| NonNull::from(thread_data_storage.get_or_insert_with(ThreadData::new)));
201
202 f(unsafe { thread_data.as_ref() })
203}
204
205impl Drop for ThreadData {
206 fn drop(&mut self) {
207 NUM_THREADS.fetch_sub(1, Ordering::Relaxed);
208 }
209}
210
211/// Returns a reference to the latest hash table, creating one if it doesn't exist yet.
212/// The reference is valid forever. However, the `HashTable` it references might become stale
213/// at any point. Meaning it still exists, but it is not the instance in active use.
214#[inline]
215fn get_hashtable() -> &'static HashTable {
216 let table = HASHTABLE.load(Ordering::Acquire);
217
218 // If there is no table, create one
219 if table.is_null() {
220 create_hashtable()
221 } else {
222 // SAFETY: when not null, `HASHTABLE` always points to a `HashTable` that is never freed.
223 unsafe { table.as_ref_unchecked() }
224 }
225}
226
227/// Returns a reference to the latest hash table, creating one if it doesn't exist yet.
228/// The reference is valid forever. However, the `HashTable` it references might become stale
229/// at any point. Meaning it still exists, but it is not the instance in active use.
230#[cold]
231fn create_hashtable() -> &'static HashTable {
232 let new_table = Box::into_raw(HashTable::new(LOAD_FACTOR, None));
233
234 // If this fails then it means some other thread created the hash table first.
235 let table = match HASHTABLE.compare_exchange(
236 ptr::null_mut(),
237 new_table,
238 Ordering::AcqRel,
239 Ordering::Acquire,
240 ) {
241 Ok(_) => new_table,
242 Err(old_table) => {
243 // Free the table we created
244 // SAFETY: `new_table` is created from `Box::into_raw` above and only freed here.
245 unsafe {
246 let _ = Box::from_raw(new_table);
247 }
248 old_table
249 }
250 };
251 // SAFETY: The `HashTable` behind `table` is never freed. It is either the table pointer we
252 // created here, or it is one loaded from `HASHTABLE`.
253 unsafe { table.as_ref_unchecked() }
254}
255
256// Grow the hash table so that it is big enough for the given number of threads.
257// This isn't performance-critical since it is only done when a ThreadData is
258// created, which only happens once per thread.
259fn grow_hashtable(num_threads: usize) {
260 // Lock all buckets in the existing table and get a reference to it
261 let old_table = loop {
262 let table = get_hashtable();
263
264 // Check if we need to resize the existing table
265 if table.entries.len() >= LOAD_FACTOR * num_threads {
266 return;
267 }
268
269 // Lock all buckets in the old table
270 for bucket in &table.entries[..] {
271 bucket.mutex.lock();
272 }
273
274 // Now check if our table is still the latest one. Another thread could
275 // have grown the hash table between us reading HASHTABLE and locking
276 // the buckets.
277 if ptr::eq(HASHTABLE.load(Ordering::Relaxed), table) {
278 break table;
279 }
280
281 // Unlock buckets and try again
282 for bucket in &table.entries[..] {
283 // SAFETY: We hold the lock here, as required
284 unsafe { bucket.mutex.unlock() };
285 }
286 };
287
288 // Create the new table
289 let mut new_table = HashTable::new(num_threads, Some(NonNull::from(old_table)));
290
291 // Move the entries from the old table to the new one
292 for bucket in &old_table.entries[..] {
293 // SAFETY: Parking-lot operations maintain correctly linked queues. A
294 // `ThreadData` remains valid for as long as it is linked in a queue.
295 unsafe { rehash_bucket_into(bucket, &mut new_table) };
296 }
297
298 // Publish the new table. No races are possible at this point because
299 // any other thread trying to grow the hash table is blocked on the bucket
300 // locks in the old table.
301 HASHTABLE.store(Box::into_raw(new_table), Ordering::Release);
302
303 // Unlock all buckets in the old table
304 for bucket in &old_table.entries[..] {
305 // SAFETY: We hold the lock here, as required
306 unsafe { bucket.mutex.unlock() };
307 }
308}
309
310/// Iterates through all `ThreadData` objects in the bucket and inserts them
311/// into the buckets corresponding to their keys in the given table.
312///
313/// # Safety
314///
315/// The given `bucket` must have a correctly constructed linked list under `queue_head`, containing
316/// `ThreadData` instances that must stay valid at least as long as the given `table` is in use.
317///
318/// The given `table` must only contain buckets with correctly constructed linked lists.
319unsafe fn rehash_bucket_into(bucket: &'static Bucket, table: &mut HashTable) {
320 let mut current = bucket.queue_head.get();
321 while let Some(current_ptr) = current {
322 let current_ref = unsafe { current_ptr.as_ref() };
323 let next = unsafe { current_ref.state() }.next_in_queue;
324 let hash = hash(current_ref.key.load(Ordering::Relaxed), table.hash_bits);
325 if let Some(tail) = table.entries[hash].queue_tail.get() {
326 unsafe { tail.as_ref().state() }.next_in_queue = Some(current_ptr);
327 } else {
328 table.entries[hash].queue_head.set(Some(current_ptr));
329 }
330 table.entries[hash].queue_tail.set(Some(current_ptr));
331 unsafe { current_ref.state() }.next_in_queue = None;
332 current = next;
333 }
334}
335
336// Hash function for addresses
337#[cfg(target_pointer_width = "32")]
338#[inline]
339fn hash(key: usize, bits: u32) -> usize {
340 key.wrapping_mul(0x9E3779B9) >> (32 - bits)
341}
342#[cfg(target_pointer_width = "64")]
343#[inline]
344fn hash(key: usize, bits: u32) -> usize {
345 key.wrapping_mul(0x9E3779B97F4A7C15) >> (64 - bits)
346}
347
348/// Locks the bucket for the given key and returns a reference to it.
349/// The returned bucket must be unlocked again in order to not cause deadlocks.
350#[inline]
351fn lock_bucket(key: usize) -> &'static Bucket {
352 loop {
353 let hashtable = get_hashtable();
354
355 let hash = hash(key, hashtable.hash_bits);
356 let bucket = &hashtable.entries[hash];
357
358 // Lock the bucket
359 bucket.mutex.lock();
360
361 // If no other thread has rehashed the table before we grabbed the lock
362 // then we are good to go! The lock we grabbed prevents any rehashes.
363 if ptr::eq(HASHTABLE.load(Ordering::Relaxed), hashtable) {
364 return bucket;
365 }
366
367 // Unlock the bucket and try again
368 // SAFETY: We hold the lock here, as required
369 unsafe { bucket.mutex.unlock() };
370 }
371}
372
373/// Locks the bucket for the given key and returns a reference to it. But checks that the key
374/// hasn't been changed in the meantime due to a requeue.
375/// The returned bucket must be unlocked again in order to not cause deadlocks.
376#[inline]
377fn lock_bucket_checked(key: &AtomicUsize) -> (usize, &'static Bucket) {
378 loop {
379 let hashtable = get_hashtable();
380 let current_key = key.load(Ordering::Relaxed);
381
382 let hash = hash(current_key, hashtable.hash_bits);
383 let bucket = &hashtable.entries[hash];
384
385 // Lock the bucket
386 bucket.mutex.lock();
387
388 // Check that both the hash table and key are correct while the bucket
389 // is locked. Note that the key can't change once we locked the proper
390 // bucket for it, so we just keep trying until we have the correct key.
391 if ptr::eq(HASHTABLE.load(Ordering::Relaxed), hashtable)
392 && key.load(Ordering::Relaxed) == current_key
393 {
394 return (current_key, bucket);
395 }
396
397 // Unlock the bucket and try again
398 // SAFETY: We hold the lock here, as required
399 unsafe { bucket.mutex.unlock() };
400 }
401}
402
403/// Locks the two buckets for the given pair of keys and returns references to them.
404/// The returned buckets must be unlocked again in order to not cause deadlocks.
405///
406/// If both keys hash to the same value, both returned references will be to the same bucket. Be
407/// careful to only unlock it once in this case, always use `unlock_bucket_pair`.
408#[inline]
409fn lock_bucket_pair(key1: usize, key2: usize) -> (&'static Bucket, &'static Bucket) {
410 loop {
411 let hashtable = get_hashtable();
412
413 let hash1 = hash(key1, hashtable.hash_bits);
414 let hash2 = hash(key2, hashtable.hash_bits);
415
416 // Get the bucket at the lowest hash/index first
417 let bucket1 = if hash1 <= hash2 {
418 &hashtable.entries[hash1]
419 } else {
420 &hashtable.entries[hash2]
421 };
422
423 // Lock the first bucket
424 bucket1.mutex.lock();
425
426 // If no other thread has rehashed the table before we grabbed the lock
427 // then we are good to go! The lock we grabbed prevents any rehashes.
428 if ptr::eq(HASHTABLE.load(Ordering::Relaxed), hashtable) {
429 // Now lock the second bucket and return the two buckets
430 if hash1 == hash2 {
431 return (bucket1, bucket1);
432 } else if hash1 < hash2 {
433 let bucket2 = &hashtable.entries[hash2];
434 bucket2.mutex.lock();
435 return (bucket1, bucket2);
436 } else {
437 let bucket2 = &hashtable.entries[hash1];
438 bucket2.mutex.lock();
439 return (bucket2, bucket1);
440 }
441 }
442
443 // Unlock the bucket and try again
444 // SAFETY: We hold the lock here, as required
445 unsafe { bucket1.mutex.unlock() };
446 }
447}
448
449/// Unlocks a pair of buckets.
450///
451/// # Safety
452///
453/// Both buckets must be locked.
454#[inline]
455unsafe fn unlock_bucket_pair(bucket1: &Bucket, bucket2: &Bucket) {
456 unsafe { bucket1.mutex.unlock() };
457 if !ptr::eq(bucket1, bucket2) {
458 unsafe { bucket2.mutex.unlock() };
459 }
460}
461
462/// Result of a park operation.
463#[derive(Copy, Clone, Eq, PartialEq, Debug)]
464pub enum ParkResult {
465 /// We were unparked by another thread with the given token.
466 Unparked(UnparkToken),
467
468 /// The validation callback returned false.
469 Invalid,
470
471 /// The timeout expired.
472 TimedOut,
473}
474
475impl ParkResult {
476 /// Returns true if we were unparked by another thread.
477 #[inline]
478 pub const fn is_unparked(self) -> bool {
479 matches!(self, ParkResult::Unparked(_))
480 }
481}
482
483/// Result of an unpark operation.
484#[derive(Copy, Clone, Default, Eq, PartialEq, Debug)]
485#[non_exhaustive]
486pub struct UnparkResult {
487 /// The number of threads that were unparked.
488 pub unparked_threads: usize,
489
490 /// The number of threads that were requeued.
491 pub requeued_threads: usize,
492
493 /// Whether any threads remain parked with the original key after the
494 /// operation.
495 ///
496 /// This is `false` if the operation was aborted before the queue was
497 /// inspected.
498 pub have_more_threads: bool,
499}
500
501/// Operation that `unpark_requeue` should perform.
502#[derive(Copy, Clone, Eq, PartialEq, Debug)]
503pub enum RequeueOp {
504 /// Abort the operation without doing anything.
505 Abort,
506
507 /// Unpark one thread and requeue the rest onto the target queue.
508 UnparkOneRequeueRest,
509
510 /// Requeue all threads onto the target queue.
511 RequeueAll,
512
513 /// Unpark one thread and leave the rest parked. No requeuing is done.
514 UnparkOne,
515
516 /// Requeue one thread and leave the rest parked on the original queue.
517 RequeueOne,
518}
519
520/// Operation that `unpark_filter` should perform for each thread.
521#[derive(Copy, Clone, Eq, PartialEq, Debug)]
522pub enum FilterOp {
523 /// Unpark the thread and continue scanning the list of parked threads.
524 Unpark,
525
526 /// Don't unpark the thread and continue scanning the list of parked threads.
527 Skip,
528
529 /// Don't unpark the thread and stop scanning the list of parked threads.
530 Stop,
531}
532
533/// A value which is passed from an unparker to a parked thread.
534#[derive(Copy, Clone, Eq, PartialEq, Debug)]
535pub struct UnparkToken(pub usize);
536
537/// A value associated with a parked thread which can be used by `unpark_filter`.
538#[derive(Copy, Clone, Eq, PartialEq, Debug)]
539pub struct ParkToken(pub usize);
540
541/// A default unpark token to use.
542pub const DEFAULT_UNPARK_TOKEN: UnparkToken = UnparkToken(0);
543
544/// A default park token to use.
545pub const DEFAULT_PARK_TOKEN: ParkToken = ParkToken(0);
546
547/// Parks the current thread in the queue associated with the given key.
548///
549/// The `validate` function is called while the queue is locked and can abort
550/// the operation by returning false. If `validate` returns true then the
551/// current thread is appended to the queue and the queue is unlocked.
552///
553/// The `before_sleep` function is called after the queue is unlocked but before
554/// the thread is put to sleep. The thread will then sleep until it is unparked
555/// or the given timeout is reached.
556///
557/// The `timed_out` function is also called while the queue is locked, but only
558/// if the timeout was reached. It is passed the key of the queue it was in when
559/// it timed out, which may be different from the original key if
560/// `unpark_requeue` was called. It is also passed a bool which indicates
561/// whether it was the last thread in the queue.
562///
563/// A timeout is the earliest point at which this function may return
564/// [`ParkResult::TimedOut`]. Scheduling and platform-specific behavior may
565/// delay the actual return.
566///
567/// # Safety
568///
569/// You should only call this function with an address that you control, since
570/// you could otherwise interfere with the operation of other synchronization
571/// primitives.
572///
573/// The `validate` and `timed_out` functions are called while the queue is
574/// locked and must not unwind or call into any function in `parking_lot`.
575///
576/// The `before_sleep` function is called outside the queue lock and is allowed
577/// to call `unpark_one`, `unpark_all`, `unpark_requeue` or `unpark_filter`, but
578/// it is not allowed to call `park` or unwind.
579///
580/// The parking-lot functions are not reentrant. Calling this function from an
581/// asynchronous signal handler may cause undefined behavior, including
582/// internal-state corruption or deadlock.
583#[inline]
584pub unsafe fn park(
585 key: usize,
586 validate: impl FnOnce() -> bool,
587 before_sleep: impl FnOnce(),
588 timed_out: impl FnOnce(usize, bool),
589 park_token: ParkToken,
590 timeout: Option<Instant>,
591) -> ParkResult {
592 let abort_on_panic = AbortOnPanic;
593
594 // Grab our thread data, this also ensures that the hash table exists
595 let result = with_thread_data(|thread_data| {
596 // Lock the bucket for the given key
597 let bucket = lock_bucket(key);
598
599 // If the validation function fails, just return
600 if !validate() {
601 // SAFETY: We hold the lock here, as required
602 unsafe { bucket.mutex.unlock() };
603 return ParkResult::Invalid;
604 }
605
606 // Append our thread data to the queue and unlock the bucket
607 let thread_data_ptr = NonNull::from(thread_data);
608 let state = unsafe { thread_data.state() };
609 state.next_in_queue = None;
610 state.park_token = park_token;
611 #[cfg(feature = "deadlock_detection")]
612 {
613 state.deadlock_data.parked_with_timeout = timeout.is_some();
614 }
615 thread_data.key.store(key, Ordering::Relaxed);
616 unsafe { thread_data.parker.prepare_park() };
617 if let Some(tail) = bucket.queue_tail.get() {
618 unsafe { tail.as_ref().state() }.next_in_queue = Some(thread_data_ptr);
619 } else {
620 bucket.queue_head.set(Some(thread_data_ptr));
621 }
622 bucket.queue_tail.set(Some(thread_data_ptr));
623 // SAFETY: We hold the lock here, as required
624 unsafe { bucket.mutex.unlock() };
625
626 // Invoke the pre-sleep callback
627 before_sleep();
628
629 // Park our thread and determine whether we were woken up by an unpark
630 // or by our timeout. Note that this isn't precise: we can still be
631 // unparked since we are still in the queue.
632 let unparked = match timeout {
633 Some(timeout) => unsafe { thread_data.parker.park_until(timeout) },
634 None => {
635 unsafe { thread_data.parker.park() };
636 // Handle a pending deadlock-detector backtrace request.
637 unsafe { deadlock::on_unpark(thread_data) };
638 true
639 }
640 };
641
642 // If we were unparked, return now
643 if unparked {
644 return ParkResult::Unparked(unsafe { thread_data.state() }.unpark_token);
645 }
646
647 // Lock our bucket again. Note that the hashtable may have been rehashed in
648 // the meantime. Our key may also have changed if we were requeued.
649 let (key, bucket) = lock_bucket_checked(&thread_data.key);
650
651 // Now we need to check again if we were unparked or timed out. Unlike the
652 // last check this is precise because we hold the bucket lock.
653 if !unsafe { thread_data.parker.timed_out() } {
654 // SAFETY: We hold the lock here, as required
655 unsafe { bucket.mutex.unlock() };
656 return ParkResult::Unparked(unsafe { thread_data.state() }.unpark_token);
657 }
658
659 // We timed out, so we now need to remove our thread from the queue
660 let mut current = bucket.queue_head.get();
661 let mut previous: Option<NonNull<ThreadData>> = None;
662 let mut was_last_thread = true;
663 while let Some(current_ptr) = current {
664 let current_ref = unsafe { current_ptr.as_ref() };
665 let next = unsafe { current_ref.state() }.next_in_queue;
666 if current_ptr == thread_data_ptr {
667 if let Some(previous) = previous {
668 unsafe { previous.as_ref().state() }.next_in_queue = next;
669 } else {
670 bucket.queue_head.set(next);
671 }
672 if bucket.queue_tail.get() == Some(current_ptr) {
673 bucket.queue_tail.set(previous);
674 } else {
675 // Scan the rest of the queue to see if there are any other
676 // entries with the given key.
677 let mut scan = next;
678 while let Some(scan_ptr) = scan {
679 let scan_ref = unsafe { scan_ptr.as_ref() };
680 if scan_ref.key.load(Ordering::Relaxed) == key {
681 was_last_thread = false;
682 break;
683 }
684 scan = unsafe { scan_ref.state() }.next_in_queue;
685 }
686 }
687
688 // Callback to indicate that we timed out, and whether we were the
689 // last thread on the queue.
690 timed_out(key, was_last_thread);
691 break;
692 } else {
693 if current_ref.key.load(Ordering::Relaxed) == key {
694 was_last_thread = false;
695 }
696 previous = Some(current_ptr);
697 current = next;
698 }
699 }
700
701 // There should be no way for our thread to have been removed from the queue
702 // if we timed out.
703 debug_assert!(current.is_some());
704
705 // Unlock the bucket, we are done
706 // SAFETY: We hold the lock here, as required
707 unsafe { bucket.mutex.unlock() };
708 ParkResult::TimedOut
709 });
710
711 abort_on_panic.disarm();
712 result
713}
714
715/// Unparks one thread from the queue associated with the given key.
716///
717/// The `callback` function is called while the queue is locked and before the
718/// target thread is woken up. The `UnparkResult` argument to the function
719/// indicates whether a thread was found in the queue and whether this was the
720/// last thread in the queue. This value is also returned by `unpark_one`.
721///
722/// The `callback` function should return an `UnparkToken` value which will be
723/// passed to the thread that is unparked. If no thread is unparked then the
724/// returned value is ignored.
725///
726/// # Safety
727///
728/// You should only call this function with an address that you control, since
729/// you could otherwise interfere with the operation of other synchronization
730/// primitives.
731///
732/// The `callback` function is called while the queue is locked and must not
733/// unwind or call into any function in `parking_lot`.
734///
735/// The parking-lot functions are not reentrant. Calling this function from an
736/// asynchronous signal handler may cause undefined behavior, including
737/// internal-state corruption or deadlock.
738#[inline]
739pub unsafe fn unpark_one(
740 key: usize,
741 callback: impl FnOnce(UnparkResult) -> UnparkToken,
742) -> UnparkResult {
743 let abort_on_panic = AbortOnPanic;
744
745 // Lock the bucket for the given key
746 let bucket = lock_bucket(key);
747
748 // Find a thread with a matching key and remove it from the queue
749 let mut current = bucket.queue_head.get();
750 let mut previous: Option<NonNull<ThreadData>> = None;
751 let mut result = UnparkResult::default();
752 while let Some(current_ptr) = current {
753 let current_ref = unsafe { current_ptr.as_ref() };
754 let next = unsafe { current_ref.state() }.next_in_queue;
755 if current_ref.key.load(Ordering::Relaxed) == key {
756 // Remove the thread from the queue
757 if let Some(previous) = previous {
758 unsafe { previous.as_ref().state() }.next_in_queue = next;
759 } else {
760 bucket.queue_head.set(next);
761 }
762 if bucket.queue_tail.get() == Some(current_ptr) {
763 bucket.queue_tail.set(previous);
764 } else {
765 // Scan the rest of the queue to see if there are any other
766 // entries with the given key.
767 let mut scan = next;
768 while let Some(scan_ptr) = scan {
769 let scan_ref = unsafe { scan_ptr.as_ref() };
770 if scan_ref.key.load(Ordering::Relaxed) == key {
771 result.have_more_threads = true;
772 break;
773 }
774 scan = unsafe { scan_ref.state() }.next_in_queue;
775 }
776 }
777
778 // Invoke the callback before waking up the thread
779 result.unparked_threads = 1;
780 let token = callback(result);
781
782 // Set the token for the target thread
783 unsafe { current_ref.state() }.unpark_token = token;
784
785 // Commit the unpark before unlocking the queue. The target may now
786 // destroy its ThreadData, but the handle remains valid for the
787 // deferred wake.
788 let handle = unsafe { current_ref.parker.unpark_lock() };
789 // SAFETY: We hold the lock here, as required
790 unsafe { bucket.mutex.unlock() };
791 unsafe { handle.unpark() };
792
793 abort_on_panic.disarm();
794 return result;
795 } else {
796 previous = Some(current_ptr);
797 current = next;
798 }
799 }
800
801 // No threads with a matching key were found in the bucket
802 callback(result);
803 // SAFETY: We hold the lock here, as required
804 unsafe { bucket.mutex.unlock() };
805
806 abort_on_panic.disarm();
807 result
808}
809
810/// Unparks all threads in the queue associated with the given key.
811///
812/// The given `UnparkToken` is passed to all unparked threads.
813///
814/// This function returns the number of threads that were unparked.
815///
816/// # Safety
817///
818/// You should only call this function with an address that you control, since
819/// you could otherwise interfere with the operation of other synchronization
820/// primitives.
821///
822/// The parking-lot functions are not reentrant. Calling this function from an
823/// asynchronous signal handler may cause undefined behavior, including
824/// internal-state corruption or deadlock.
825#[inline]
826pub unsafe fn unpark_all(key: usize, unpark_token: UnparkToken) -> usize {
827 let abort_on_panic = AbortOnPanic;
828
829 // Lock the bucket for the given key
830 let bucket = lock_bucket(key);
831
832 // Remove all threads with the given key in the bucket
833 let mut current = bucket.queue_head.get();
834 let mut previous: Option<NonNull<ThreadData>> = None;
835 let mut threads = SmallVec::<[_; 8]>::new();
836 while let Some(current_ptr) = current {
837 let current_ref = unsafe { current_ptr.as_ref() };
838 let next = unsafe { current_ref.state() }.next_in_queue;
839 if current_ref.key.load(Ordering::Relaxed) == key {
840 // Remove the thread from the queue
841 if let Some(previous) = previous {
842 unsafe { previous.as_ref().state() }.next_in_queue = next;
843 } else {
844 bucket.queue_head.set(next);
845 }
846 if bucket.queue_tail.get() == Some(current_ptr) {
847 bucket.queue_tail.set(previous);
848 }
849
850 // Set the token for the target thread
851 unsafe { current_ref.state() }.unpark_token = unpark_token;
852
853 // Commit the unpark now and defer the wake until the queue is unlocked.
854 threads.push(unsafe { current_ref.parker.unpark_lock() });
855 current = next;
856 } else {
857 previous = Some(current_ptr);
858 current = next;
859 }
860 }
861
862 // Unlock the bucket
863 // SAFETY: We hold the lock here, as required
864 unsafe { bucket.mutex.unlock() };
865
866 // Now that we are outside the lock, wake up all the threads that we removed
867 // from the queue.
868 let num_threads = threads.len();
869 for handle in threads.into_iter() {
870 unsafe { handle.unpark() };
871 }
872
873 abort_on_panic.disarm();
874 num_threads
875}
876
877/// Removes all threads from the queue associated with `key_from`, optionally
878/// unparks the first one and requeues the rest onto the queue associated with
879/// `key_to`.
880///
881/// The `validate` function is called while both queues are locked. Its return
882/// value will determine which operation is performed, or whether the operation
883/// should be aborted. See `RequeueOp` for details about the different possible
884/// return values.
885///
886/// If `validate` returns [`RequeueOp::Abort`], the queues are left unchanged,
887/// `callback` is not called, and a default [`UnparkResult`] is returned.
888/// Otherwise, `callback` is called while both queues are locked. It is passed
889/// the `RequeueOp` returned by `validate` and an `UnparkResult` indicating
890/// whether a thread was unparked and whether threads remain parked with
891/// `key_from`. Threads requeued to `key_to` are not included. This
892/// `UnparkResult` value is also returned by `unpark_requeue`.
893///
894/// The `callback` function should return an `UnparkToken` value which will be
895/// passed to the thread that is unparked. If no thread is unparked then the
896/// returned value is ignored.
897///
898/// # Safety
899///
900/// You should only call this function with an address that you control, since
901/// you could otherwise interfere with the operation of other synchronization
902/// primitives.
903///
904/// The `validate` and `callback` functions are called while both queues are locked
905/// and must not unwind or call into any function in `parking_lot`.
906///
907/// The parking-lot functions are not reentrant. Calling this function from an
908/// asynchronous signal handler may cause undefined behavior, including
909/// internal-state corruption or deadlock.
910#[inline]
911pub unsafe fn unpark_requeue(
912 key_from: usize,
913 key_to: usize,
914 validate: impl FnOnce() -> RequeueOp,
915 callback: impl FnOnce(RequeueOp, UnparkResult) -> UnparkToken,
916) -> UnparkResult {
917 let abort_on_panic = AbortOnPanic;
918
919 // Lock the two buckets for the given key
920 let (bucket_from, bucket_to) = lock_bucket_pair(key_from, key_to);
921
922 // If the validation function fails, just return
923 let mut result = UnparkResult::default();
924 let op = validate();
925 if op == RequeueOp::Abort {
926 // SAFETY: Both buckets are locked, as required.
927 unsafe { unlock_bucket_pair(bucket_from, bucket_to) };
928 abort_on_panic.disarm();
929 return result;
930 }
931
932 // Remove all threads with the given key in the source bucket
933 let mut current = bucket_from.queue_head.get();
934 let mut previous: Option<NonNull<ThreadData>> = None;
935 let mut requeue_threads: Option<NonNull<ThreadData>> = None;
936 let mut requeue_threads_tail: Option<NonNull<ThreadData>> = None;
937 let mut wakeup_thread = None;
938 while let Some(current_ptr) = current {
939 let current_ref = unsafe { current_ptr.as_ref() };
940 let next = unsafe { current_ref.state() }.next_in_queue;
941 if current_ref.key.load(Ordering::Relaxed) == key_from {
942 // Remove the thread from the queue
943 if let Some(previous) = previous {
944 unsafe { previous.as_ref().state() }.next_in_queue = next;
945 } else {
946 bucket_from.queue_head.set(next);
947 }
948 if bucket_from.queue_tail.get() == Some(current_ptr) {
949 bucket_from.queue_tail.set(previous);
950 }
951
952 // Prepare the first thread for wakeup and requeue the rest.
953 if (op == RequeueOp::UnparkOneRequeueRest || op == RequeueOp::UnparkOne)
954 && wakeup_thread.is_none()
955 {
956 wakeup_thread = Some(current_ptr);
957 result.unparked_threads = 1;
958 } else {
959 if let Some(tail) = requeue_threads_tail {
960 unsafe { tail.as_ref().state() }.next_in_queue = Some(current_ptr);
961 } else {
962 requeue_threads = Some(current_ptr);
963 }
964 requeue_threads_tail = Some(current_ptr);
965 current_ref.key.store(key_to, Ordering::Relaxed);
966 result.requeued_threads += 1;
967 }
968 if op == RequeueOp::UnparkOne || op == RequeueOp::RequeueOne {
969 // Scan the rest of the queue to see if there are any other
970 // entries with the given key.
971 let mut scan = next;
972 while let Some(scan_ptr) = scan {
973 let scan_ref = unsafe { scan_ptr.as_ref() };
974 if scan_ref.key.load(Ordering::Relaxed) == key_from {
975 result.have_more_threads = true;
976 break;
977 }
978 scan = unsafe { scan_ref.state() }.next_in_queue;
979 }
980 break;
981 }
982 current = next;
983 } else {
984 previous = Some(current_ptr);
985 current = next;
986 }
987 }
988
989 // Add the requeued threads to the destination bucket
990 if let Some(requeue_threads) = requeue_threads {
991 let requeue_threads_tail = requeue_threads_tail.unwrap();
992 unsafe { requeue_threads_tail.as_ref().state() }.next_in_queue = None;
993 if let Some(tail) = bucket_to.queue_tail.get() {
994 unsafe { tail.as_ref().state() }.next_in_queue = Some(requeue_threads);
995 } else {
996 bucket_to.queue_head.set(Some(requeue_threads));
997 }
998 bucket_to.queue_tail.set(Some(requeue_threads_tail));
999 }
1000
1001 // Invoke the callback before waking up the thread
1002 let token = callback(op, result);
1003
1004 // Commit the unpark before unlocking the queues, then perform the wake.
1005 if let Some(wakeup_thread) = wakeup_thread {
1006 let wakeup_thread = unsafe { wakeup_thread.as_ref() };
1007 unsafe { wakeup_thread.state() }.unpark_token = token;
1008 let handle = unsafe { wakeup_thread.parker.unpark_lock() };
1009 // SAFETY: Both buckets are locked, as required.
1010 unsafe { unlock_bucket_pair(bucket_from, bucket_to) };
1011 unsafe { handle.unpark() };
1012 } else {
1013 // SAFETY: Both buckets are locked, as required.
1014 unsafe { unlock_bucket_pair(bucket_from, bucket_to) };
1015 }
1016
1017 abort_on_panic.disarm();
1018 result
1019}
1020
1021/// Unparks a number of threads from the front of the queue associated with
1022/// `key` depending on the results of a filter function which inspects the
1023/// `ParkToken` associated with each thread.
1024///
1025/// The `filter` function is called for each thread in the queue or until
1026/// `FilterOp::Stop` is returned. This function is passed the `ParkToken`
1027/// associated with a particular thread, which is unparked if `FilterOp::Unpark`
1028/// is returned.
1029///
1030/// The `callback` function is also called while the queue is locked. It is
1031/// passed an `UnparkResult` indicating the number of threads that were unparked
1032/// and whether there are still parked threads in the queue. This `UnparkResult`
1033/// value is also returned by `unpark_filter`.
1034///
1035/// The `callback` function should return an `UnparkToken` value which will be
1036/// passed to all threads that are unparked. If no thread is unparked then the
1037/// returned value is ignored.
1038///
1039/// # Safety
1040///
1041/// You should only call this function with an address that you control, since
1042/// you could otherwise interfere with the operation of other synchronization
1043/// primitives.
1044///
1045/// The `filter` and `callback` functions are called while the queue is locked
1046/// and must not unwind or call into any function in `parking_lot`.
1047///
1048/// The parking-lot functions are not reentrant. Calling this function from an
1049/// asynchronous signal handler may cause undefined behavior, including
1050/// internal-state corruption or deadlock.
1051#[inline]
1052pub unsafe fn unpark_filter(
1053 key: usize,
1054 filter: impl FnMut(ParkToken) -> FilterOp,
1055 callback: impl FnOnce(UnparkResult) -> UnparkToken,
1056) -> UnparkResult {
1057 let abort_on_panic = AbortOnPanic;
1058 let mut filter = filter;
1059
1060 // Lock the bucket for the given key
1061 let bucket = lock_bucket(key);
1062
1063 // Go through the queue looking for threads with a matching key
1064 let mut current = bucket.queue_head.get();
1065 let mut previous: Option<NonNull<ThreadData>> = None;
1066 let mut threads = SmallVec::<[_; 8]>::new();
1067 let mut result = UnparkResult::default();
1068 while let Some(current_ptr) = current {
1069 let current_ref = unsafe { current_ptr.as_ref() };
1070 let next = unsafe { current_ref.state() }.next_in_queue;
1071 if current_ref.key.load(Ordering::Relaxed) == key {
1072 // Call the filter function with the thread's ParkToken
1073 match filter(unsafe { current_ref.state() }.park_token) {
1074 FilterOp::Unpark => {
1075 // Remove the thread from the queue
1076 if let Some(previous) = previous {
1077 unsafe { previous.as_ref().state() }.next_in_queue = next;
1078 } else {
1079 bucket.queue_head.set(next);
1080 }
1081 if bucket.queue_tail.get() == Some(current_ptr) {
1082 bucket.queue_tail.set(previous);
1083 }
1084
1085 // Add the thread to our list of threads to unpark
1086 threads.push((current_ptr, None));
1087
1088 current = next;
1089 }
1090 FilterOp::Skip => {
1091 result.have_more_threads = true;
1092 previous = Some(current_ptr);
1093 current = next;
1094 }
1095 FilterOp::Stop => {
1096 result.have_more_threads = true;
1097 break;
1098 }
1099 }
1100 } else {
1101 previous = Some(current_ptr);
1102 current = next;
1103 }
1104 }
1105
1106 // Invoke the callback before waking up the threads
1107 result.unparked_threads = threads.len();
1108 let token = callback(result);
1109
1110 // Pass the token to all threads that are going to be unparked and prepare
1111 // them for unparking.
1112 for t in threads.iter_mut() {
1113 let thread = unsafe { t.0.as_ref() };
1114 unsafe { thread.state() }.unpark_token = token;
1115 t.1 = Some(unsafe { thread.parker.unpark_lock() });
1116 }
1117
1118 // SAFETY: We hold the lock here, as required
1119 unsafe { bucket.mutex.unlock() };
1120
1121 // Now that we are outside the lock, wake up all the threads that we removed
1122 // from the queue.
1123 for (_, handle) in threads.into_iter() {
1124 unsafe { handle.unwrap_unchecked().unpark() };
1125 }
1126
1127 abort_on_panic.disarm();
1128 result
1129}
1130
1131/// \[Experimental\] Deadlock detection
1132///
1133/// Enabled via the `deadlock_detection` feature flag.
1134pub mod deadlock {
1135 #[cfg(feature = "deadlock_detection")]
1136 use super::deadlock_impl;
1137
1138 #[cfg(feature = "deadlock_detection")]
1139 pub(super) use super::deadlock_impl::DeadlockData;
1140
1141 /// Records that the current thread owns the resource identified by `key`.
1142 ///
1143 /// This is a no-op if the `deadlock_detection` feature is not enabled.
1144 /// Each recorded acquisition should be paired with a call to
1145 /// [`release_resource`] using the same key. The same key may be recorded
1146 /// more than once if a resource is acquired repeatedly by the same thread.
1147 /// Call this after the resource has been acquired.
1148 ///
1149 /// # Safety
1150 ///
1151 /// This must not be called from a callback passed to a parking-lot
1152 /// function.
1153 #[inline]
1154 pub unsafe fn acquire_resource(_key: usize) {
1155 let abort_on_panic = super::AbortOnPanic;
1156
1157 #[cfg(feature = "deadlock_detection")]
1158 unsafe {
1159 deadlock_impl::acquire_resource(_key);
1160 }
1161
1162 abort_on_panic.disarm();
1163 }
1164
1165 /// Stops recording one acquisition of the resource identified by `key` by
1166 /// the current thread.
1167 ///
1168 /// This is a no-op if the `deadlock_detection` feature is not enabled.
1169 /// The key should match an acquisition previously recorded by this thread.
1170 /// The bookkeeping may be removed before the underlying resource is
1171 /// physically released.
1172 ///
1173 /// # Safety
1174 ///
1175 /// This must not be called from a callback passed to a parking-lot
1176 /// function.
1177 #[inline]
1178 pub unsafe fn release_resource(_key: usize) {
1179 let abort_on_panic = super::AbortOnPanic;
1180
1181 #[cfg(feature = "deadlock_detection")]
1182 unsafe {
1183 deadlock_impl::release_resource(_key);
1184 }
1185
1186 abort_on_panic.disarm();
1187 }
1188
1189 /// Detects and returns all currently deadlocked thread components.
1190 ///
1191 /// Each inner vector contains the threads in one mutually deadlocked
1192 /// component.
1193 ///
1194 /// Waits with a deadline are excluded because they can resolve by timing
1195 /// out.
1196 ///
1197 /// Reporting a component removes its threads from the parking queues. Each
1198 /// thread captures its backtrace and then remains blocked permanently.
1199 #[cfg(feature = "deadlock_detection")]
1200 #[inline]
1201 pub fn check_deadlock() -> Vec<Vec<deadlock_impl::DeadlockedThread>> {
1202 let abort_on_panic = super::AbortOnPanic;
1203 let result = deadlock_impl::check_deadlock();
1204 abort_on_panic.disarm();
1205 result
1206 }
1207
1208 #[inline]
1209 pub(super) unsafe fn on_unpark(_td: &super::ThreadData) {
1210 let abort_on_panic = super::AbortOnPanic;
1211
1212 #[cfg(feature = "deadlock_detection")]
1213 unsafe {
1214 deadlock_impl::on_unpark(_td);
1215 }
1216
1217 abort_on_panic.disarm();
1218 }
1219}
1220
1221#[cfg(feature = "deadlock_detection")]
1222mod deadlock_impl {
1223 use super::{HASHTABLE, NUM_THREADS, ThreadData, get_hashtable, with_thread_data};
1224 use crate::thread_parker::{ThreadParkerT, UnparkHandleT};
1225 use crate::word_lock::WordLock;
1226 use backtrace::Backtrace;
1227 use petgraph::graphmap::DiGraphMap;
1228 use std::collections::HashMap;
1229 use std::ptr::NonNull;
1230 use std::sync::atomic::Ordering;
1231 use std::sync::mpsc;
1232 use std::thread::ThreadId;
1233
1234 /// Representation of a deadlocked thread.
1235 pub struct DeadlockedThread {
1236 thread_id: ThreadId,
1237 backtrace: Backtrace,
1238 }
1239
1240 impl DeadlockedThread {
1241 /// The identifier of the deadlocked thread.
1242 pub fn thread_id(&self) -> ThreadId {
1243 self.thread_id
1244 }
1245
1246 /// The backtrace captured on the deadlocked thread.
1247 pub fn backtrace(&self) -> &Backtrace {
1248 &self.backtrace
1249 }
1250 }
1251
1252 pub struct DeadlockData {
1253 // Resource keys currently recorded as owned by this thread.
1254 resources: Vec<usize>,
1255
1256 // Set before linking to indicate whether the current wait has a
1257 // deadline, then read by the detector under the bucket lock.
1258 pub(super) parked_with_timeout: bool,
1259
1260 // Installed by the detector while the ThreadData is owned by the
1261 // parking lot and taken locally only after the parker returns.
1262 deadlock_backtrace: Option<mpsc::Sender<DeadlockedThread>>,
1263
1264 // Immutable after construction.
1265 thread_id: ThreadId,
1266 }
1267
1268 impl DeadlockData {
1269 pub fn new() -> Self {
1270 DeadlockData {
1271 resources: Vec::new(),
1272 parked_with_timeout: false,
1273 deadlock_backtrace: None,
1274 thread_id: std::thread::current().id(),
1275 }
1276 }
1277 }
1278
1279 pub(super) unsafe fn on_unpark(td: &ThreadData) {
1280 let state = unsafe { td.state() };
1281 if let Some(sender) = state.deadlock_data.deadlock_backtrace.take() {
1282 sender
1283 .send(DeadlockedThread {
1284 thread_id: state.deadlock_data.thread_id,
1285 backtrace: Backtrace::new(),
1286 })
1287 .unwrap();
1288 // Drop the sender before parking permanently so that the detector
1289 // observes the channel closing.
1290 drop(sender);
1291
1292 // This ThreadData has been removed from its queue and cannot be
1293 // reached by another parking-lot wake operation. Park permanently
1294 // after reporting the backtrace.
1295 unsafe { td.parker.prepare_park() };
1296 unsafe { td.parker.park() };
1297 unreachable!("unparked deadlocked thread!");
1298 }
1299 }
1300
1301 pub unsafe fn acquire_resource(key: usize) {
1302 with_thread_data(|thread_data| {
1303 unsafe { thread_data.state() }
1304 .deadlock_data
1305 .resources
1306 .push(key);
1307 });
1308 }
1309
1310 pub unsafe fn release_resource(key: usize) {
1311 with_thread_data(|thread_data| {
1312 let resources = &mut unsafe { thread_data.state() }.deadlock_data.resources;
1313
1314 // During TLS destruction the original ThreadData may no longer be
1315 // accessible, in which case with_thread_data supplies a temporary
1316 // empty ThreadData. There is no bookkeeping left to update.
1317 if let Some(p) = resources.iter().rposition(|x| *x == key) {
1318 resources.swap_remove(p);
1319 }
1320 });
1321 }
1322
1323 pub fn check_deadlock() -> Vec<Vec<DeadlockedThread>> {
1324 // First use an approximate snapshot to avoid the precise scan in the
1325 // common case where no cycle is observed.
1326 if unsafe { check_wait_graph_fast() } {
1327 // Verify the result using a consistent snapshot.
1328 unsafe { check_wait_graph_slow() }
1329 } else {
1330 Vec::new()
1331 }
1332 }
1333
1334 // Build an approximate wait graph while locking one bucket at a time. The
1335 // resulting snapshot may combine states from different points in time, so
1336 // a cycle only triggers the precise slow check.
1337 unsafe fn check_wait_graph_fast() -> bool {
1338 'retry: loop {
1339 let table = get_hashtable();
1340 let thread_count = NUM_THREADS.load(Ordering::Relaxed);
1341 let mut graph =
1342 DiGraphMap::<usize, ()>::with_capacity(thread_count * 2, thread_count * 2);
1343
1344 for b in &table.entries[..] {
1345 b.mutex.lock();
1346
1347 // Hash-table growth may have moved this bucket's queue while
1348 // we were waiting for its lock. Restart with the current table
1349 // rather than traversing queue links no longer protected by
1350 // this bucket.
1351 if !core::ptr::eq(HASHTABLE.load(Ordering::Relaxed), table) {
1352 unsafe { b.mutex.unlock() };
1353 continue 'retry;
1354 }
1355
1356 let mut current = b.queue_head.get();
1357 while let Some(current_ptr) = current {
1358 let thread_data = unsafe { current_ptr.as_ref() };
1359 let state = unsafe { thread_data.state() };
1360 // Exclude timed waits because they can eventually resolve
1361 // without being unparked by another thread.
1362 if !state.deadlock_data.parked_with_timeout {
1363 let thread = current_ptr.as_ptr().addr();
1364 // Each owned resource points to its owning thread.
1365 for &resource in &state.deadlock_data.resources {
1366 graph.add_edge(resource, thread, ());
1367 }
1368 // The thread points to the queue key on which it is parked.
1369 graph.add_edge(thread, thread_data.key.load(Ordering::Relaxed), ());
1370 }
1371 current = state.next_in_queue;
1372 }
1373 // SAFETY: We hold the lock here, as required
1374 unsafe { b.mutex.unlock() };
1375 }
1376
1377 return petgraph::algo::is_cyclic_directed(&graph);
1378 }
1379 }
1380
1381 #[derive(Hash, PartialEq, Eq, PartialOrd, Ord, Copy, Clone)]
1382 enum WaitGraphNode {
1383 Thread(NonNull<ThreadData>),
1384 Resource(usize),
1385 }
1386
1387 use self::WaitGraphNode::*;
1388
1389 // Unlike the fast check, this locks every bucket while constructing the
1390 // wait graph and selecting deadlocked components. Reported threads are
1391 // removed from their queues before the buckets are unlocked.
1392 unsafe fn check_wait_graph_slow() -> Vec<Vec<DeadlockedThread>> {
1393 // Reporting mutates the global queues, so only one slow check may run
1394 // at a time.
1395 static DEADLOCK_DETECTION_LOCK: WordLock = WordLock::new();
1396 DEADLOCK_DETECTION_LOCK.lock();
1397
1398 let mut table = get_hashtable();
1399 loop {
1400 // Lock all buckets in the candidate table.
1401 for b in &table.entries[..] {
1402 b.mutex.lock();
1403 }
1404
1405 // Another thread may have replaced the hash table while its
1406 // buckets were being locked. In that case, retry with the current
1407 // table.
1408 let new_table = get_hashtable();
1409 if core::ptr::eq(new_table, table) {
1410 break;
1411 }
1412
1413 // Unlock the candidate table's buckets and try again.
1414 for b in &table.entries[..] {
1415 // SAFETY: We hold the lock here, as required
1416 unsafe { b.mutex.unlock() };
1417 }
1418
1419 table = new_table;
1420 }
1421
1422 let thread_count = NUM_THREADS.load(Ordering::Relaxed);
1423 let mut graph =
1424 DiGraphMap::<WaitGraphNode, ()>::with_capacity(thread_count * 2, thread_count * 2);
1425
1426 for b in &table.entries[..] {
1427 let mut current = b.queue_head.get();
1428 while let Some(current_ptr) = current {
1429 let thread_data = unsafe { current_ptr.as_ref() };
1430 let state = unsafe { thread_data.state() };
1431 // Exclude timed waits because they can eventually resolve
1432 // without being unparked by another thread.
1433 if !state.deadlock_data.parked_with_timeout {
1434 // Each owned resource points to its owning thread.
1435 for &resource in &state.deadlock_data.resources {
1436 graph.add_edge(Resource(resource), Thread(current_ptr), ());
1437 }
1438 // The thread points to the queue key on which it is parked.
1439 graph.add_edge(
1440 Thread(current_ptr),
1441 Resource(thread_data.key.load(Ordering::Relaxed)),
1442 (),
1443 );
1444 }
1445 current = state.next_in_queue;
1446 }
1447 }
1448
1449 let components = graph_components(&graph);
1450 let deadlocked_thread_count = components.iter().map(Vec::len).sum();
1451 let mut senders = HashMap::with_capacity(deadlocked_thread_count);
1452 let mut receivers = Vec::with_capacity(components.len());
1453 // Use one channel per component, with one sender stored in each thread
1454 // that must report a backtrace.
1455 for component in components {
1456 let (sender, receiver) = mpsc::channel();
1457 for thread in component {
1458 let previous = senders.insert(thread, sender.clone());
1459 debug_assert!(previous.is_none());
1460 }
1461 // Drop the detector's sender so only the per-thread copies keep
1462 // the channel open.
1463 drop(sender);
1464 receivers.push(receiver);
1465 }
1466
1467 // The components contain raw ThreadData pointers. Keeping every bucket
1468 // locked preserves each queued ThreadData until it has been unlinked
1469 // and passed to unpark_lock.
1470 let mut handles = Vec::with_capacity(deadlocked_thread_count);
1471 for bucket in &table.entries[..] {
1472 let mut current = bucket.queue_head.get();
1473 let mut previous: Option<NonNull<ThreadData>> = None;
1474 while let Some(current_ptr) = current {
1475 let thread_data = unsafe { current_ptr.as_ref() };
1476 let state = unsafe { thread_data.state() };
1477 let next = state.next_in_queue;
1478 if let Some(sender) = senders.remove(¤t_ptr) {
1479 if let Some(previous) = previous {
1480 unsafe { previous.as_ref().state() }.next_in_queue = next;
1481 } else {
1482 bucket.queue_head.set(next);
1483 }
1484 if bucket.queue_tail.get() == Some(current_ptr) {
1485 bucket.queue_tail.set(previous);
1486 }
1487
1488 // The reporting thread parks permanently after capturing
1489 // its backtrace, so it must no longer be visible to normal
1490 // queue operations.
1491 state.next_in_queue = None;
1492 state.deadlock_data.deadlock_backtrace = Some(sender);
1493 handles.push(unsafe { thread_data.parker.unpark_lock() });
1494 } else {
1495 previous = Some(current_ptr);
1496 }
1497 current = next;
1498 }
1499 }
1500 debug_assert!(senders.is_empty());
1501
1502 for b in &table.entries[..] {
1503 // SAFETY: We hold the lock here, as required
1504 unsafe { b.mutex.unlock() };
1505 }
1506
1507 // Platform wake operations may block, so perform them only after all
1508 // bucket locks have been released.
1509 for handle in handles {
1510 unsafe { handle.unpark() };
1511 }
1512
1513 // Collect until every per-thread sender for the component is dropped.
1514 let results = receivers
1515 .into_iter()
1516 .map(|receiver| receiver.iter().collect())
1517 .collect();
1518
1519 unsafe { DEADLOCK_DETECTION_LOCK.unlock() };
1520
1521 results
1522 }
1523
1524 // Returns the thread nodes in each nontrivial strongly connected component.
1525 fn graph_components(g: &DiGraphMap<WaitGraphNode, ()>) -> Vec<Vec<NonNull<ThreadData>>> {
1526 petgraph::algo::kosaraju_scc(g)
1527 .into_iter()
1528 .filter(|component| component.len() > 1)
1529 .filter_map(|component| {
1530 let threads = component
1531 .into_iter()
1532 .filter_map(|node| match node {
1533 Thread(thread) => Some(thread),
1534 Resource(_) => None,
1535 })
1536 .collect::<Vec<_>>();
1537 (!threads.is_empty()).then_some(threads)
1538 })
1539 .collect()
1540 }
1541
1542 #[cfg(test)]
1543 mod tests {
1544 use super::*;
1545
1546 #[test]
1547 fn overlapping_cycles_form_one_component() {
1548 let storage = [0u8; 3];
1549 let thread1 = NonNull::from(&storage[0]).cast::<ThreadData>();
1550 let thread2 = NonNull::from(&storage[1]).cast::<ThreadData>();
1551 let thread3 = NonNull::from(&storage[2]).cast::<ThreadData>();
1552 let mut graph = DiGraphMap::new();
1553
1554 graph.add_edge(Thread(thread1), Resource(1), ());
1555 graph.add_edge(Resource(1), Thread(thread2), ());
1556 graph.add_edge(Thread(thread2), Resource(2), ());
1557 graph.add_edge(Resource(2), Thread(thread1), ());
1558
1559 graph.add_edge(Thread(thread2), Resource(3), ());
1560 graph.add_edge(Resource(3), Thread(thread3), ());
1561 graph.add_edge(Thread(thread3), Resource(4), ());
1562 graph.add_edge(Resource(4), Thread(thread2), ());
1563
1564 let mut components = graph_components(&graph);
1565 assert_eq!(components.len(), 1);
1566 components[0].sort_unstable();
1567
1568 let mut expected = vec![thread1, thread2, thread3];
1569 expected.sort_unstable();
1570 assert_eq!(components[0], expected);
1571 }
1572 }
1573}
1574
1575#[cfg(test)]
1576mod tests {
1577 use super::{DEFAULT_PARK_TOKEN, DEFAULT_UNPARK_TOKEN, ThreadData};
1578 use std::{
1579 ptr,
1580 sync::{
1581 Arc,
1582 atomic::{AtomicIsize, AtomicPtr, AtomicUsize, Ordering},
1583 },
1584 thread,
1585 time::Duration,
1586 };
1587
1588 /// Calls a closure for every `ThreadData` currently parked on a given key
1589 fn for_each(key: usize, mut f: impl FnMut(&ThreadData)) {
1590 let bucket = super::lock_bucket(key);
1591
1592 let mut current = bucket.queue_head.get();
1593 while let Some(current_ptr) = current {
1594 let current_ref = unsafe { current_ptr.as_ref() };
1595 if current_ref.key.load(Ordering::Relaxed) == key {
1596 f(current_ref);
1597 }
1598 current = unsafe { current_ref.state() }.next_in_queue;
1599 }
1600
1601 // SAFETY: We hold the lock here, as required
1602 unsafe { bucket.mutex.unlock() };
1603 }
1604
1605 macro_rules! test {
1606 ( $( $name:ident(
1607 repeats: $repeats:expr,
1608 latches: $latches:expr,
1609 delay: $delay:expr,
1610 threads: $threads:expr,
1611 single_unparks: $single_unparks:expr);
1612 )* ) => {
1613 $(#[test]
1614 fn $name() {
1615 let delay = Duration::from_micros($delay);
1616 for _ in 0..$repeats {
1617 run_parking_test($latches, delay, $threads, $single_unparks);
1618 }
1619 })*
1620 };
1621 }
1622
1623 test! {
1624 unpark_all_one_fast(
1625 repeats: 1000, latches: 1, delay: 0, threads: 1, single_unparks: 0
1626 );
1627 unpark_all_hundred_fast(
1628 repeats: 100, latches: 1, delay: 0, threads: 100, single_unparks: 0
1629 );
1630 unpark_one_one_fast(
1631 repeats: 1000, latches: 1, delay: 0, threads: 1, single_unparks: 1
1632 );
1633 unpark_one_hundred_fast(
1634 repeats: 20, latches: 1, delay: 0, threads: 100, single_unparks: 100
1635 );
1636 unpark_one_fifty_then_fifty_all_fast(
1637 repeats: 50, latches: 1, delay: 0, threads: 100, single_unparks: 50
1638 );
1639 unpark_all_one(
1640 repeats: 100, latches: 1, delay: 10000, threads: 1, single_unparks: 0
1641 );
1642 unpark_all_hundred(
1643 repeats: 100, latches: 1, delay: 10000, threads: 100, single_unparks: 0
1644 );
1645 unpark_one_one(
1646 repeats: 10, latches: 1, delay: 10000, threads: 1, single_unparks: 1
1647 );
1648 unpark_one_fifty(
1649 repeats: 1, latches: 1, delay: 10000, threads: 50, single_unparks: 50
1650 );
1651 unpark_one_fifty_then_fifty_all(
1652 repeats: 2, latches: 1, delay: 10000, threads: 100, single_unparks: 50
1653 );
1654 hundred_unpark_all_one_fast(
1655 repeats: 100, latches: 100, delay: 0, threads: 1, single_unparks: 0
1656 );
1657 hundred_unpark_all_one(
1658 repeats: 1, latches: 100, delay: 10000, threads: 1, single_unparks: 0
1659 );
1660 }
1661
1662 fn run_parking_test(
1663 num_latches: usize,
1664 delay: Duration,
1665 num_threads: usize,
1666 num_single_unparks: usize,
1667 ) {
1668 let mut tests = Vec::with_capacity(num_latches);
1669
1670 for _ in 0..num_latches {
1671 let test = Arc::new(SingleLatchTest::new(num_threads));
1672 let mut threads = Vec::with_capacity(num_threads);
1673 for _ in 0..num_threads {
1674 let test = test.clone();
1675 threads.push(thread::spawn(move || test.run()));
1676 }
1677 tests.push((test, threads));
1678 }
1679
1680 for unpark_index in 0..num_single_unparks {
1681 thread::sleep(delay);
1682 for (test, _) in &tests {
1683 test.unpark_one(unpark_index);
1684 }
1685 }
1686
1687 for (test, threads) in tests {
1688 test.finish(num_single_unparks);
1689 for thread in threads {
1690 thread.join().expect("Test thread panic");
1691 }
1692 }
1693 }
1694
1695 struct SingleLatchTest {
1696 semaphore: AtomicIsize,
1697 num_awake: AtomicUsize,
1698 /// Holds the pointer to the last *unprocessed* woken up thread.
1699 last_awoken: AtomicPtr<ThreadData>,
1700 /// Total number of threads participating in this test.
1701 num_threads: usize,
1702 }
1703
1704 impl SingleLatchTest {
1705 pub fn new(num_threads: usize) -> Self {
1706 Self {
1707 // This implements a fair (FIFO) semaphore, and it starts out unavailable.
1708 semaphore: AtomicIsize::new(0),
1709 num_awake: AtomicUsize::new(0),
1710 last_awoken: AtomicPtr::new(ptr::null_mut()),
1711 num_threads,
1712 }
1713 }
1714
1715 pub fn run(&self) {
1716 // Get one slot from the semaphore
1717 self.down();
1718
1719 // Report back to the test verification code that this thread woke up
1720 let this_thread_ptr = super::with_thread_data(|t| t as *const _ as *mut _);
1721 self.last_awoken.store(this_thread_ptr, Ordering::SeqCst);
1722 self.num_awake.fetch_add(1, Ordering::SeqCst);
1723 }
1724
1725 pub fn unpark_one(&self, single_unpark_index: usize) {
1726 // last_awoken should be null at all times except between self.up() and at the bottom
1727 // of this method where it's reset to null again
1728 assert!(self.last_awoken.load(Ordering::SeqCst).is_null());
1729
1730 let mut queue: Vec<*mut ThreadData> = Vec::with_capacity(self.num_threads);
1731 for_each(self.semaphore_addr(), |thread_data| {
1732 queue.push(thread_data as *const _ as *mut _);
1733 });
1734 assert!(queue.len() <= self.num_threads - single_unpark_index);
1735
1736 let num_awake_before_up = self.num_awake.load(Ordering::SeqCst);
1737
1738 self.up();
1739
1740 // Wait for a parked thread to wake up and update num_awake + last_awoken.
1741 while self.num_awake.load(Ordering::SeqCst) != num_awake_before_up + 1 {
1742 thread::yield_now();
1743 }
1744
1745 // At this point the other thread should have set last_awoken inside the run() method
1746 let last_awoken = self.last_awoken.load(Ordering::SeqCst);
1747 assert!(!last_awoken.is_null());
1748 if !queue.is_empty() && queue[0] != last_awoken {
1749 panic!(
1750 "Woke up wrong thread:\n\tqueue: {:?}\n\tlast awoken: {:?}",
1751 queue, last_awoken
1752 );
1753 }
1754 self.last_awoken.store(ptr::null_mut(), Ordering::SeqCst);
1755 }
1756
1757 pub fn finish(&self, num_single_unparks: usize) {
1758 // The amount of threads not unparked via unpark_one
1759 let mut num_threads_left = self.num_threads.checked_sub(num_single_unparks).unwrap();
1760
1761 // Wake remaining threads up with unpark_all. Has to be in a loop, because there might
1762 // still be threads that has not yet parked.
1763 while num_threads_left > 0 {
1764 let mut num_waiting_on_address = 0;
1765 for_each(self.semaphore_addr(), |_thread_data| {
1766 num_waiting_on_address += 1;
1767 });
1768 assert!(num_waiting_on_address <= num_threads_left);
1769
1770 let num_awake_before_unpark = self.num_awake.load(Ordering::SeqCst);
1771
1772 let num_unparked =
1773 unsafe { super::unpark_all(self.semaphore_addr(), DEFAULT_UNPARK_TOKEN) };
1774 assert!(num_unparked >= num_waiting_on_address);
1775 assert!(num_unparked <= num_threads_left);
1776
1777 // Wait for all unparked threads to wake up and update num_awake + last_awoken.
1778 while self.num_awake.load(Ordering::SeqCst)
1779 != num_awake_before_unpark + num_unparked
1780 {
1781 thread::yield_now()
1782 }
1783
1784 num_threads_left = num_threads_left.checked_sub(num_unparked).unwrap();
1785 }
1786 // By now, all threads should have been woken up
1787 assert_eq!(self.num_awake.load(Ordering::SeqCst), self.num_threads);
1788
1789 // Make sure no thread is parked on our semaphore address
1790 let mut num_waiting_on_address = 0;
1791 for_each(self.semaphore_addr(), |_thread_data| {
1792 num_waiting_on_address += 1;
1793 });
1794 assert_eq!(num_waiting_on_address, 0);
1795 }
1796
1797 pub fn down(&self) {
1798 let old_semaphore_value = self.semaphore.fetch_sub(1, Ordering::SeqCst);
1799
1800 if old_semaphore_value > 0 {
1801 // We acquired the semaphore. Done.
1802 return;
1803 }
1804
1805 // We need to wait.
1806 let validate = || true;
1807 let before_sleep = || {};
1808 let timed_out = |_, _| {};
1809 unsafe {
1810 super::park(
1811 self.semaphore_addr(),
1812 validate,
1813 before_sleep,
1814 timed_out,
1815 DEFAULT_PARK_TOKEN,
1816 None,
1817 );
1818 }
1819 }
1820
1821 pub fn up(&self) {
1822 let old_semaphore_value = self.semaphore.fetch_add(1, Ordering::SeqCst);
1823
1824 // Check if anyone was waiting on the semaphore. If they were, then pass ownership to them.
1825 if old_semaphore_value < 0 {
1826 // We need to continue until we have actually unparked someone. It might be that
1827 // the thread we want to pass ownership to has decremented the semaphore counter,
1828 // but not yet parked.
1829 loop {
1830 match unsafe {
1831 super::unpark_one(self.semaphore_addr(), |_| DEFAULT_UNPARK_TOKEN)
1832 .unparked_threads
1833 } {
1834 1 => break,
1835 0 => (),
1836 i => panic!("Should not wake up {} threads", i),
1837 }
1838 }
1839 }
1840 }
1841
1842 fn semaphore_addr(&self) -> usize {
1843 core::ptr::from_ref(&self.semaphore).addr()
1844 }
1845 }
1846}