1use core::{
4 cell::UnsafeCell,
5 marker::PhantomData,
6 ops::{Deref, DerefMut},
7 panic::Location,
8 ptr,
9 sync::atomic::{AtomicPtr, AtomicU64, Ordering},
10};
11
12pub(crate) trait MutexRuntimeOps {
14 fn might_sleep(caller: &'static Location<'static>);
16
17 fn current_task_id() -> u64;
19
20 fn wait_until_unlocked(wait_queue: &AtomicPtr<()>, owner_id: &AtomicU64);
22
23 fn wake_one(wait_queue: &AtomicPtr<()>);
25
26 fn drop_wait_queue(wait_queue: *mut ());
33}
34
35#[cfg(all(feature = "host-test", not(target_os = "none")))]
36use host::HostMutexRuntimeOps as ActiveMutexOps;
37#[cfg(not(all(feature = "host-test", not(target_os = "none"))))]
38use native::NativeMutexRuntimeOps as ActiveMutexOps;
39
40pub(crate) fn runtime_might_sleep(caller: &'static Location<'static>) {
41 ActiveMutexOps::might_sleep(caller);
42}
43
44pub(crate) fn runtime_current_task_id() -> u64 {
45 ActiveMutexOps::current_task_id()
46}
47
48pub(crate) fn runtime_wait_until_unlocked(wait_queue: &AtomicPtr<()>, owner_id: &AtomicU64) {
49 ActiveMutexOps::wait_until_unlocked(wait_queue, owner_id);
50}
51
52pub(crate) fn runtime_wake_one(wait_queue: &AtomicPtr<()>) {
53 ActiveMutexOps::wake_one(wait_queue);
54}
55
56pub(crate) fn runtime_drop_wait_queue(wait_queue: *mut ()) {
57 ActiveMutexOps::drop_wait_queue(wait_queue);
58}
59
60#[cfg(not(feature = "lockdep"))]
61pub type LockSubclass = u32;
63
64#[cfg(feature = "lockdep")]
65use crate::sync::lockdep::LockSubclass;
66
67pub struct RawMutex {
69 wait_queue: AtomicPtr<()>,
70 owner_id: AtomicU64,
71 #[cfg(feature = "lockdep")]
72 pub(crate) lockdep: crate::sync::spin::lockdep::LockdepMap,
73}
74
75impl RawMutex {
76 #[track_caller]
78 pub const fn new() -> Self {
79 Self {
80 wait_queue: AtomicPtr::new(ptr::null_mut()),
81 owner_id: AtomicU64::new(0),
82 #[cfg(feature = "lockdep")]
83 lockdep: crate::sync::spin::lockdep::LockdepMap::new(),
84 }
85 }
86
87 #[inline(always)]
88 fn current_task_id() -> u64 {
89 let task_id = ActiveMutexOps::current_task_id();
90 assert_ne!(task_id, 0, "mutex runtime returned the reserved owner id 0");
91 task_id
92 }
93
94 #[inline(always)]
95 fn is_owner(&self, owner_id: u64) -> bool {
96 self.owner_id.load(Ordering::Acquire) == owner_id
97 }
98
99 pub fn is_owned_by_current(&self) -> bool {
101 self.is_owner(Self::current_task_id())
102 }
103
104 pub fn is_locked(&self) -> bool {
106 self.owner_id.load(Ordering::Acquire) != 0
107 }
108
109 #[inline(always)]
110 #[track_caller]
111 fn lock(&self) {
112 #[cfg(feature = "lockdep")]
113 self.lock_nested(crate::sync::spin::lockdep::DEFAULT_LOCK_SUBCLASS);
114
115 #[cfg(not(feature = "lockdep"))]
116 self.lock_plain();
117 }
118
119 #[inline(always)]
120 #[track_caller]
121 #[cfg(not(feature = "lockdep"))]
122 fn lock_plain(&self) {
123 ActiveMutexOps::might_sleep(Location::caller());
124 self.lock_after_prepare(Self::current_task_id());
125 }
126
127 #[inline(always)]
128 #[track_caller]
129 #[cfg(feature = "lockdep")]
130 fn lock_nested(&self, subclass: LockSubclass) {
131 ActiveMutexOps::might_sleep(Location::caller());
132 let current_id = Self::current_task_id();
133 let lockdep =
134 crate::sync::lockdep::mutex::LockdepAcquire::prepare_nested(self, false, subclass);
135 self.lock_after_prepare(current_id);
136 lockdep.finish(true);
137 }
138
139 #[inline(always)]
140 fn lock_after_prepare(&self, current_id: u64) {
141 loop {
142 match self.owner_id.compare_exchange_weak(
143 0,
144 current_id,
145 Ordering::Acquire,
146 Ordering::Relaxed,
147 ) {
148 Ok(_) => return,
149 Err(owner_id) => {
150 assert_ne!(
151 owner_id, current_id,
152 "task {current_id} tried to recursively acquire a mutex"
153 );
154 ActiveMutexOps::wait_until_unlocked(&self.wait_queue, &self.owner_id);
155 }
156 }
157 }
158 }
159
160 #[inline(always)]
161 #[track_caller]
162 fn try_lock(&self) -> bool {
163 let current_id = Self::current_task_id();
164
165 #[cfg(feature = "lockdep")]
166 let lockdep = crate::sync::lockdep::mutex::LockdepAcquire::prepare_nested(
167 self,
168 true,
169 crate::sync::spin::lockdep::DEFAULT_LOCK_SUBCLASS,
170 );
171
172 let acquired = self
173 .owner_id
174 .compare_exchange(0, current_id, Ordering::Acquire, Ordering::Relaxed)
175 .is_ok();
176
177 #[cfg(feature = "lockdep")]
178 lockdep.finish(acquired);
179
180 acquired
181 }
182
183 #[inline(always)]
184 unsafe fn unlock(&self) {
185 let owner_id = self.owner_id.load(Ordering::Acquire);
186 let current_id = Self::current_task_id();
187 assert_eq!(
188 owner_id, current_id,
189 "task {current_id} tried to release a mutex owned by task {owner_id}"
190 );
191
192 #[cfg(feature = "lockdep")]
193 crate::sync::lockdep::mutex::release(self);
194
195 self.owner_id.store(0, Ordering::Release);
196 ActiveMutexOps::wake_one(&self.wait_queue);
197 }
198
199 #[doc(hidden)]
207 pub unsafe fn force_unlock(&self) {
208 unsafe { self.unlock() };
209 }
210}
211
212impl Default for RawMutex {
213 fn default() -> Self {
214 Self::new()
215 }
216}
217
218impl Drop for RawMutex {
219 fn drop(&mut self) {
220 assert_eq!(
221 self.owner_id.load(Ordering::Acquire),
222 0,
223 "dropping a locked mutex"
224 );
225 let wait_queue = self.wait_queue.swap(ptr::null_mut(), Ordering::AcqRel);
226 if !wait_queue.is_null() {
227 ActiveMutexOps::drop_wait_queue(wait_queue);
230 }
231 }
232}
233
234pub struct Mutex<T: ?Sized> {
239 raw: RawMutex,
240 data: UnsafeCell<T>,
241}
242
243unsafe impl<T: ?Sized + Send> Send for Mutex<T> {}
244unsafe impl<T: ?Sized + Send> Sync for Mutex<T> {}
245
246impl<T> Mutex<T> {
247 #[track_caller]
249 pub const fn new(value: T) -> Self {
250 Self {
251 raw: RawMutex::new(),
252 data: UnsafeCell::new(value),
253 }
254 }
255
256 pub fn into_inner(self) -> T {
258 let Self { raw, data } = self;
259 drop(raw);
260 data.into_inner()
261 }
262}
263
264impl<T: ?Sized> Mutex<T> {
265 #[inline(always)]
267 #[track_caller]
268 pub fn lock(&self) -> MutexGuard<'_, T> {
269 self.raw.lock();
270 MutexGuard::new(self)
271 }
272
273 #[inline(always)]
275 #[track_caller]
276 pub fn try_lock(&self) -> Option<MutexGuard<'_, T>> {
277 self.raw.try_lock().then(|| MutexGuard::new(self))
278 }
279
280 #[doc(hidden)]
288 pub unsafe fn force_unlock(&self) {
289 unsafe { self.raw.force_unlock() };
290 }
291
292 pub fn is_locked(&self) -> bool {
294 self.raw.is_locked()
295 }
296
297 pub fn get_mut(&mut self) -> &mut T {
299 self.data.get_mut()
300 }
301
302 #[doc(hidden)]
309 pub unsafe fn raw(&self) -> &RawMutex {
310 &self.raw
311 }
312}
313
314impl<T: Default> Default for Mutex<T> {
315 fn default() -> Self {
316 Self::new(T::default())
317 }
318}
319
320pub struct MutexGuard<'a, T: ?Sized> {
327 mutex: &'a Mutex<T>,
328 not_send: PhantomData<*mut ()>,
329}
330
331impl<'a, T: ?Sized> MutexGuard<'a, T> {
332 fn new(mutex: &'a Mutex<T>) -> Self {
333 Self {
334 mutex,
335 not_send: PhantomData,
336 }
337 }
338}
339
340impl<T: ?Sized> Deref for MutexGuard<'_, T> {
341 type Target = T;
342
343 fn deref(&self) -> &Self::Target {
344 unsafe { &*self.mutex.data.get() }
346 }
347}
348
349impl<T: ?Sized> DerefMut for MutexGuard<'_, T> {
350 fn deref_mut(&mut self) -> &mut Self::Target {
351 unsafe { &mut *self.mutex.data.get() }
353 }
354}
355
356impl<T: ?Sized> Drop for MutexGuard<'_, T> {
357 fn drop(&mut self) {
358 unsafe { self.mutex.raw.unlock() };
360 }
361}
362
363pub trait LockdepMutexExt<T: ?Sized> {
365 fn lock_nested(&self, subclass: LockSubclass) -> MutexGuard<'_, T>;
367}
368
369impl<T: ?Sized> LockdepMutexExt<T> for Mutex<T> {
370 #[inline(always)]
371 #[track_caller]
372 fn lock_nested(&self, subclass: LockSubclass) -> MutexGuard<'_, T> {
373 #[cfg(not(feature = "lockdep"))]
374 {
375 let _ = subclass;
376 self.lock()
377 }
378
379 #[cfg(feature = "lockdep")]
380 {
381 self.raw.lock_nested(subclass);
382 MutexGuard::new(self)
383 }
384 }
385}
386
387#[cfg(all(feature = "host-test", not(target_os = "none")))]
388mod host {
389 #[cfg(test)]
390 use core::sync::atomic::AtomicBool;
391 use core::{
392 panic::Location,
393 sync::atomic::{AtomicPtr, AtomicU64, AtomicUsize, Ordering},
394 };
395 use std::{
396 boxed::Box,
397 cell::Cell,
398 sync::{Condvar, Mutex as StdMutex},
399 };
400
401 use super::MutexRuntimeOps;
402
403 struct HostWaitQueue {
404 state: StdMutex<()>,
405 condvar: Condvar,
406 waiters: AtomicUsize,
407 }
408
409 impl HostWaitQueue {
410 fn new() -> Self {
411 Self {
412 state: StdMutex::new(()),
413 condvar: Condvar::new(),
414 waiters: AtomicUsize::new(0),
415 }
416 }
417 }
418
419 static NEXT_TASK_ID: AtomicU64 = AtomicU64::new(1);
420 #[cfg(test)]
421 static WAIT_BOUNDARY_OWNER: AtomicUsize = AtomicUsize::new(0);
422 #[cfg(test)]
423 static WAIT_BOUNDARY_REACHED: AtomicBool = AtomicBool::new(false);
424 #[cfg(test)]
425 static WAIT_BOUNDARY_CONTINUE: AtomicBool = AtomicBool::new(false);
426
427 std::thread_local! {
428 static TASK_ID: Cell<u64> = const { Cell::new(0) };
429 static MIGHT_SLEEP_CALLS: Cell<usize> = const { Cell::new(0) };
430 static LAST_MIGHT_SLEEP_CALLER: Cell<Option<&'static Location<'static>>> = const {
431 Cell::new(None)
432 };
433 }
434
435 pub(super) struct HostMutexRuntimeOps;
436
437 impl MutexRuntimeOps for HostMutexRuntimeOps {
438 fn might_sleep(caller: &'static Location<'static>) {
439 MIGHT_SLEEP_CALLS.set(MIGHT_SLEEP_CALLS.get() + 1);
440 LAST_MIGHT_SLEEP_CALLER.set(Some(caller));
441 assert_eq!(
442 crate::sync::host_preempt_depth(),
443 0,
444 "sleeping mutex acquired with preemption disabled at {caller}"
445 );
446 }
447
448 fn current_task_id() -> u64 {
449 TASK_ID.with(|task_id| match task_id.get() {
450 0 => {
451 let id = NEXT_TASK_ID.fetch_add(1, Ordering::Relaxed);
452 task_id.set(id);
453 id
454 }
455 id => id,
456 })
457 }
458
459 fn wait_until_unlocked(wait_queue: &AtomicPtr<()>, owner_id: &AtomicU64) {
460 let queue = ensure_wait_queue(wait_queue);
461 queue.waiters.fetch_add(1, Ordering::AcqRel);
462 #[cfg(test)]
463 if WAIT_BOUNDARY_OWNER.load(Ordering::Acquire) == core::ptr::from_ref(owner_id) as usize
464 {
465 WAIT_BOUNDARY_REACHED.store(true, Ordering::Release);
466 while !WAIT_BOUNDARY_CONTINUE.load(Ordering::Acquire) {
467 std::thread::yield_now();
468 }
469 }
470 let mut state = queue.state.lock().expect("host wait queue poisoned");
471 while owner_id.load(Ordering::Acquire) != 0 {
472 state = queue
473 .condvar
474 .wait(state)
475 .expect("host wait queue poisoned while waiting");
476 }
477 queue.waiters.fetch_sub(1, Ordering::AcqRel);
478 }
479
480 fn wake_one(wait_queue: &AtomicPtr<()>) {
481 let queue = wait_queue.load(Ordering::Acquire).cast::<HostWaitQueue>();
482 if !queue.is_null() {
483 let queue = unsafe { &*queue };
486 let _state = queue.state.lock().expect("host wait queue poisoned");
487 queue.condvar.notify_one();
488 }
489 }
490
491 fn drop_wait_queue(wait_queue: *mut ()) {
492 let queue = wait_queue.cast::<HostWaitQueue>();
493 let queue = unsafe { Box::from_raw(queue) };
495 assert_eq!(
496 queue.waiters.load(Ordering::Acquire),
497 0,
498 "dropping a host wait queue with active waiters"
499 );
500 }
501 }
502
503 fn ensure_wait_queue(slot: &AtomicPtr<()>) -> &HostWaitQueue {
504 let existing = slot.load(Ordering::Acquire).cast::<HostWaitQueue>();
505 if !existing.is_null() {
506 return unsafe { &*existing };
508 }
509
510 let candidate = Box::into_raw(Box::new(HostWaitQueue::new()));
511 match slot.compare_exchange(
512 core::ptr::null_mut(),
513 ptr_to_unit(candidate),
514 Ordering::AcqRel,
515 Ordering::Acquire,
516 ) {
517 Ok(_) => {
518 unsafe { &*candidate }
520 }
521 Err(installed) => {
522 unsafe { drop(Box::from_raw(candidate)) };
524 unsafe { &*installed.cast::<HostWaitQueue>() }
526 }
527 }
528 }
529
530 const fn ptr_to_unit(pointer: *mut HostWaitQueue) -> *mut () {
531 pointer.cast::<()>()
532 }
533
534 #[cfg(test)]
535 pub(super) fn reset_might_sleep_calls() {
536 MIGHT_SLEEP_CALLS.set(0);
537 LAST_MIGHT_SLEEP_CALLER.set(None);
538 }
539
540 #[cfg(test)]
541 pub(super) fn might_sleep_calls() -> usize {
542 MIGHT_SLEEP_CALLS.get()
543 }
544
545 #[cfg(test)]
546 pub(super) fn last_might_sleep_caller() -> Option<&'static Location<'static>> {
547 LAST_MIGHT_SLEEP_CALLER.get()
548 }
549
550 #[cfg(test)]
551 pub(super) fn pause_waiter_before_registration(owner_id: &AtomicU64) {
552 WAIT_BOUNDARY_REACHED.store(false, Ordering::Release);
553 WAIT_BOUNDARY_CONTINUE.store(false, Ordering::Release);
554 WAIT_BOUNDARY_OWNER.store(core::ptr::from_ref(owner_id) as usize, Ordering::Release);
555 }
556
557 #[cfg(test)]
558 pub(super) fn wait_for_registration_boundary() {
559 while !WAIT_BOUNDARY_REACHED.load(Ordering::Acquire) {
560 std::thread::yield_now();
561 }
562 }
563
564 #[cfg(test)]
565 pub(super) fn resume_waiter_after_registration_boundary() {
566 WAIT_BOUNDARY_CONTINUE.store(true, Ordering::Release);
567 WAIT_BOUNDARY_OWNER.store(0, Ordering::Release);
568 }
569}
570
571#[cfg(not(all(feature = "host-test", not(target_os = "none"))))]
572mod native {
573 use alloc::boxed::Box;
574 use core::{
575 panic::Location,
576 sync::atomic::{AtomicPtr, AtomicU64, Ordering},
577 };
578
579 use super::MutexRuntimeOps;
580
581 pub(super) struct NativeMutexRuntimeOps;
582
583 impl MutexRuntimeOps for NativeMutexRuntimeOps {
584 fn might_sleep(caller: &'static Location<'static>) {
585 crate::might_sleep_at(caller);
586 }
587
588 fn current_task_id() -> u64 {
589 crate::current().id().as_u64()
590 }
591
592 fn wait_until_unlocked(wait_queue: &AtomicPtr<()>, owner_id: &AtomicU64) {
593 let wait_queue = ensure_wait_queue(wait_queue);
594 wait_queue.wait_until(|| owner_id.load(Ordering::Acquire) == 0);
595 }
596
597 fn wake_one(wait_queue: &AtomicPtr<()>) {
598 let wait_queue = wait_queue
599 .load(Ordering::Acquire)
600 .cast::<crate::WaitQueue>();
601 if !wait_queue.is_null() {
602 unsafe { &*wait_queue }.notify_one(true);
606 }
607 }
608
609 fn drop_wait_queue(wait_queue: *mut ()) {
610 let wait_queue = unsafe { Box::from_raw(wait_queue.cast::<crate::WaitQueue>()) };
613 assert!(
614 wait_queue.is_empty(),
615 "dropping a mutex wait queue with blocked tasks"
616 );
617 }
618 }
619
620 fn ensure_wait_queue(slot: &AtomicPtr<()>) -> &crate::WaitQueue {
621 let existing = slot.load(Ordering::Acquire).cast::<crate::WaitQueue>();
622 if !existing.is_null() {
623 return unsafe { &*existing };
625 }
626
627 let candidate = Box::into_raw(Box::new(crate::WaitQueue::new()));
628 match slot.compare_exchange(
629 core::ptr::null_mut(),
630 candidate.cast::<()>(),
631 Ordering::AcqRel,
632 Ordering::Acquire,
633 ) {
634 Ok(_) => {
635 unsafe { &*candidate }
637 }
638 Err(installed) => {
639 unsafe { drop(Box::from_raw(candidate)) };
641 unsafe { &*installed.cast::<crate::WaitQueue>() }
643 }
644 }
645 }
646}
647
648#[cfg(all(test, feature = "host-test", not(target_os = "none")))]
649mod tests {
650 use std::{sync::Arc, thread};
651
652 use super::{Mutex, host};
653 use crate::sync::SpinLock;
654
655 #[test]
656 fn lock_rejects_preemption_disabled_context() {
657 let spin = SpinLock::new(());
658 let mutex = Mutex::new(());
659 let result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
660 let _spin_guard = spin.lock();
661 let _mutex_guard = mutex.lock();
662 }));
663 assert!(result.is_err());
664 }
665
666 #[test]
667 fn contended_mutex_wakes_waiters_without_lost_wakeups() {
668 const THREADS: usize = 8;
669 const ITERATIONS: usize = 2_000;
670 let value = Arc::new(Mutex::new(0usize));
671 let mut workers = Vec::new();
672
673 for _ in 0..THREADS {
674 let value = value.clone();
675 workers.push(thread::spawn(move || {
676 for _ in 0..ITERATIONS {
677 *value.lock() += 1;
678 }
679 }));
680 }
681
682 for worker in workers {
683 worker.join().expect("mutex worker panicked");
684 }
685 assert_eq!(*value.lock(), THREADS * ITERATIONS);
686 }
687
688 #[test]
689 fn unlock_before_waiter_registration_does_not_lose_wakeup() {
690 let value = Arc::new(Mutex::new(0usize));
691 let guard = value.lock();
692 host::pause_waiter_before_registration(&value.raw.owner_id);
693 let waiter_value = value.clone();
694 let waiter = thread::spawn(move || {
695 *waiter_value.lock() = 1;
696 });
697
698 host::wait_for_registration_boundary();
699 drop(guard);
700 host::resume_waiter_after_registration_boundary();
701 waiter.join().expect("boundary waiter panicked");
702 assert_eq!(*value.lock(), 1);
703 }
704
705 #[test]
706 fn try_lock_is_nonblocking() {
707 let mutex = Mutex::new(1usize);
708 host::reset_might_sleep_calls();
709 assert!(
710 mutex
711 .raw
712 .wait_queue
713 .load(core::sync::atomic::Ordering::Acquire)
714 .is_null()
715 );
716 let guard = mutex.try_lock().expect("uncontended try_lock failed");
717 assert_eq!(host::might_sleep_calls(), 0);
718 assert!(
719 mutex
720 .raw
721 .wait_queue
722 .load(core::sync::atomic::Ordering::Acquire)
723 .is_null()
724 );
725 #[cfg(feature = "lockdep")]
726 assert!(
727 std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| mutex.try_lock())).is_err()
728 );
729 #[cfg(not(feature = "lockdep"))]
730 assert!(mutex.try_lock().is_none());
731 drop(guard);
732 assert!(mutex.try_lock().is_some());
733 assert_eq!(host::might_sleep_calls(), 0);
734 assert!(
735 mutex
736 .raw
737 .wait_queue
738 .load(core::sync::atomic::Ordering::Acquire)
739 .is_null()
740 );
741 }
742
743 #[test]
744 fn lock_reports_the_external_call_site_to_the_runtime() {
745 let mutex = Mutex::new(());
746 host::reset_might_sleep_calls();
747 let expected_line = line!() + 1;
748 drop(mutex.lock());
749 let caller = host::last_might_sleep_caller().expect("missing might_sleep caller");
750 assert_eq!(caller.file(), file!());
751 assert_eq!(caller.line(), expected_line);
752 }
753
754 #[test]
755 fn leaked_guard_can_be_released_by_owner_wrapper() {
756 let mutex = Mutex::new(());
757 core::mem::forget(mutex.lock());
758
759 unsafe { mutex.force_unlock() };
762 assert!(mutex.try_lock().is_some());
763 }
764
765 #[test]
766 fn wrong_owner_force_unlock_is_rejected() {
767 let mutex = Arc::new(Mutex::new(()));
768 let guard = mutex.lock();
769 let other = mutex.clone();
770 let result = thread::spawn(move || {
771 std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
772 unsafe { other.force_unlock() };
775 }))
776 })
777 .join()
778 .expect("owner diagnostic thread panicked outside catch_unwind");
779
780 assert!(result.is_err());
781 drop(guard);
782 }
783}