1 files changed, 108 insertions, 0 deletions
diff --git a/library/std/src/sys/sync/mutex/futex.rs b/library/std/src/sys/sync/mutex/futex.rs
new file mode 100644
index 00000000000..7427cae94d6
--- /dev/null
+++ b/library/std/src/sys/sync/mutex/futex.rs
@@ -0,0 +1,108 @@
+use crate::sync::atomic::{
+    self,
+    Ordering::{Acquire, Relaxed, Release},
+};
+use crate::sys::futex::{futex_wait, futex_wake};
+
+cfg_if::cfg_if! {
+if #[cfg(windows)] {
+    // On Windows we can have a smol futex
+    type Atomic = atomic::AtomicU8;
+    type State = u8;
+} else {
+    type Atomic = atomic::AtomicU32;
+    type State = u32;
+}
+}
+
+pub struct Mutex {
+    futex: Atomic,
+}
+
+const UNLOCKED: State = 0;
+const LOCKED: State = 1; // locked, no other threads waiting
+const CONTENDED: State = 2; // locked, and other threads waiting (contended)
+
+impl Mutex {
+    #[inline]
+    pub const fn new() -> Self {
+        Self { futex: Atomic::new(UNLOCKED) }
+    }
+
+    #[inline]
+    pub fn try_lock(&self) -> bool {
+        self.futex.compare_exchange(UNLOCKED, LOCKED, Acquire, Relaxed).is_ok()
+    }
+
+    #[inline]
+    pub fn lock(&self) {
+        if self.futex.compare_exchange(UNLOCKED, LOCKED, Acquire, Relaxed).is_err() {
+            self.lock_contended();
+        }
+    }
+
+    #[cold]
+    fn lock_contended(&self) {
+        // Spin first to speed things up if the lock is released quickly.
+        let mut state = self.spin();
+
+        // If it's unlocked now, attempt to take the lock
+        // without marking it as contended.
+        if state == UNLOCKED {
+            match self.futex.compare_exchange(UNLOCKED, LOCKED, Acquire, Relaxed) {
+                Ok(_) => return, // Locked!
+                Err(s) => state = s,
+            }
+        }
+
+        loop {
+            // Put the lock in contended state.
+            // We avoid an unnecessary write if it as already set to CONTENDED,
+            // to be friendlier for the caches.
+            if state != CONTENDED && self.futex.swap(CONTENDED, Acquire) == UNLOCKED {
+                // We changed it from UNLOCKED to CONTENDED, so we just successfully locked it.
+                return;
+            }
+
+            // Wait for the futex to change state, assuming it is still CONTENDED.
+            futex_wait(&self.futex, CONTENDED, None);
+
+            // Spin again after waking up.
+            state = self.spin();
+        }
+    }
+
+    fn spin(&self) -> State {
+        let mut spin = 100;
+        loop {
+            // We only use `load` (and not `swap` or `compare_exchange`)
+            // while spinning, to be easier on the caches.
+            let state = self.futex.load(Relaxed);
+
+            // We stop spinning when the mutex is UNLOCKED,
+            // but also when it's CONTENDED.
+            if state != LOCKED || spin == 0 {
+                return state;
+            }
+
+            crate::hint::spin_loop();
+            spin -= 1;
+        }
+    }
+
+    #[inline]
+    pub unsafe fn unlock(&self) {
+        if self.futex.swap(UNLOCKED, Release) == CONTENDED {
+            // We only wake up one thread. When that thread locks the mutex, it
+            // will mark the mutex as CONTENDED (see lock_contended above),
+            // which makes sure that any other waiting threads will also be
+            // woken up eventually.
+            self.wake();
+        }
+    }
+
+    #[cold]
+    fn wake(&self) {
+        futex_wake(&self.futex);
+    }
+}