From 7f26adeac19f78f0277637d1e798439d8f89b853 Mon Sep 17 00:00:00 2001
From: Mara Bos <m-ou.se@m-ou.se>
Date: Thu, 17 Mar 2022 12:29:07 +0100
Subject: [PATCH] Replace Linux Mutex and Condvar with futex based ones.

---
 library/std/src/sys/unix/locks/futex.rs | 125 ++++++++++++++++++++++++
 library/std/src/sys/unix/locks/mod.rs   |  32 ++++--
 2 files changed, 149 insertions(+), 8 deletions(-)
 create mode 100644 library/std/src/sys/unix/locks/futex.rs

diff --git a/library/std/src/sys/unix/locks/futex.rs b/library/std/src/sys/unix/locks/futex.rs
new file mode 100644
index 00000000000..48d800341a3
--- /dev/null
+++ b/library/std/src/sys/unix/locks/futex.rs
@@ -0,0 +1,125 @@
+use crate::sync::atomic::{
+    AtomicI32,
+    Ordering::{Acquire, Relaxed, Release},
+};
+use crate::sys::futex::{futex_wait, futex_wake, futex_wake_all};
+use crate::time::Duration;
+
+pub type MovableMutex = Mutex;
+pub type MovableCondvar = Condvar;
+
+pub struct Mutex {
+    /// 0: unlocked
+    /// 1: locked, no other threads waiting
+    /// 2: locked, and other threads waiting (contended)
+    futex: AtomicI32,
+}
+
+impl Mutex {
+    pub const fn new() -> Self {
+        Self { futex: AtomicI32::new(0) }
+    }
+
+    #[inline]
+    pub unsafe fn init(&mut self) {}
+
+    #[inline]
+    pub unsafe fn destroy(&self) {}
+
+    #[inline]
+    pub unsafe fn try_lock(&self) -> bool {
+        self.futex.compare_exchange(0, 1, Acquire, Relaxed).is_ok()
+    }
+
+    #[inline]
+    pub unsafe fn lock(&self) {
+        if self.futex.compare_exchange(0, 1, Acquire, Relaxed).is_err() {
+            self.lock_contended();
+        }
+    }
+
+    fn lock_contended(&self) {
+        loop {
+            // Put the lock in contended state, if it wasn't already.
+            if self.futex.swap(2, Acquire) == 0 {
+                // It was unlocked, so we just locked it.
+                return;
+            }
+            // Wait for the futex to change state.
+            futex_wait(&self.futex, 2, None);
+        }
+    }
+
+    #[inline]
+    pub unsafe fn unlock(&self) {
+        if self.futex.swap(0, Release) == 2 {
+            // We only wake up one thread. When that thread locks the mutex, it
+            // will mark the mutex as contended (2) (see lock_contended above),
+            // which makes sure that any other waiting threads will also be
+            // woken up eventually.
+            futex_wake(&self.futex);
+        }
+    }
+}
+
+pub struct Condvar {
+    // The value of this atomic is simply incremented on every notification.
+    // This is used by `.wait()` to not miss any notifications after
+    // unlocking the mutex and before waiting for notifications.
+    futex: AtomicI32,
+}
+
+impl Condvar {
+    #[inline]
+    pub const fn new() -> Self {
+        Self { futex: AtomicI32::new(0) }
+    }
+
+    #[inline]
+    pub unsafe fn init(&mut self) {}
+
+    #[inline]
+    pub unsafe fn destroy(&self) {}
+
+    // All the memory orderings here are `Relaxed`,
+    // because synchronization is done by unlocking and locking the mutex.
+
+    #[inline]
+    pub unsafe fn notify_one(&self) {
+        self.futex.fetch_add(1, Relaxed);
+        futex_wake(&self.futex);
+    }
+
+    #[inline]
+    pub unsafe fn notify_all(&self) {
+        self.futex.fetch_add(1, Relaxed);
+        futex_wake_all(&self.futex);
+    }
+
+    #[inline]
+    pub unsafe fn wait(&self, mutex: &Mutex) {
+        self.wait_optional_timeout(mutex, None);
+    }
+
+    #[inline]
+    pub unsafe fn wait_timeout(&self, mutex: &Mutex, timeout: Duration) -> bool {
+        self.wait_optional_timeout(mutex, Some(timeout))
+    }
+
+    unsafe fn wait_optional_timeout(&self, mutex: &Mutex, timeout: Option<Duration>) -> bool {
+        // Check the notification counter before we unlock the mutex.
+        let futex_value = self.futex.load(Relaxed);
+
+        // Unlock the mutex before going to sleep.
+        mutex.unlock();
+
+        // Wait, but only if there hasn't been any
+        // notification since we unlocked the mutex.
+        let r = futex_wait(&self.futex, futex_value, timeout);
+
+        // Lock the mutex again.
+        mutex.lock();
+
+        r
+    }
+}
diff --git a/library/std/src/sys/unix/locks/mod.rs b/library/std/src/sys/unix/locks/mod.rs
index f07a9f93b79..30e9f407eec 100644
--- a/library/std/src/sys/unix/locks/mod.rs
+++ b/library/std/src/sys/unix/locks/mod.rs
@@ -1,8 +1,24 @@
-mod pthread_condvar;
-mod pthread_mutex;
-mod pthread_remutex;
-mod pthread_rwlock;
-pub use pthread_condvar::{Condvar, MovableCondvar};
-pub use pthread_mutex::{MovableMutex, Mutex};
-pub use pthread_remutex::ReentrantMutex;
-pub use pthread_rwlock::{MovableRWLock, RWLock};
+cfg_if::cfg_if! {
+    if #[cfg(any(
+        target_os = "linux",
+        target_os = "android",
+    ))] {
+        mod futex;
+        #[allow(dead_code)]
+        mod pthread_mutex; // Only used for PthreadMutexAttr, needed by pthread_remutex.
+        mod pthread_remutex; // FIXME: Implement this using a futex
+        mod pthread_rwlock; // FIXME: Implement this using a futex
+        pub use futex::{Mutex, MovableMutex, Condvar, MovableCondvar};
+        pub use pthread_remutex::ReentrantMutex;
+        pub use pthread_rwlock::{RWLock, MovableRWLock};
+    } else {
+        mod pthread_mutex;
+        mod pthread_remutex;
+        mod pthread_rwlock;
+        mod pthread_condvar;
+        pub use pthread_mutex::{Mutex, MovableMutex};
+        pub use pthread_remutex::ReentrantMutex;
+        pub use pthread_rwlock::{RWLock, MovableRWLock};
+        pub use pthread_condvar::{Condvar, MovableCondvar};
+    }
+}
-- 
2.44.0