std: move locks to `sys` on xous

6 files changed, 342 insertions, 1 deletions

diff --git a/library/std/src/sys/locks/condvar/mod.rs b/library/std/src/sys/locks/condvar/mod.rs
index 889fcbaaaf1..425b88c1bf0 100644
--- a/library/std/src/sys/locks/condvar/mod.rs
+++ b/library/std/src/sys/locks/condvar/mod.rs
@@ -26,5 +26,8 @@ cfg_if::cfg_if! {
     } else if #[cfg(target_os = "teeos")] {
         mod teeos;
         pub use teeos::Condvar;
+    } else if #[cfg(target_os = "xous")] {
+        mod xous;
+        pub use xous::Condvar;
     }
 }
diff --git a/library/std/src/sys/locks/condvar/xous.rs b/library/std/src/sys/locks/condvar/xous.rs
new file mode 100644
index 00000000000..0e51449e0af
--- /dev/null
+++ b/library/std/src/sys/locks/condvar/xous.rs
@@ -0,0 +1,148 @@
+use crate::os::xous::ffi::{blocking_scalar, scalar};
+use crate::os::xous::services::{ticktimer_server, TicktimerScalar};
+use crate::sys::locks::Mutex;
+use crate::time::Duration;
+use core::sync::atomic::{AtomicUsize, Ordering};
+
+// The implementation is inspired by Andrew D. Birrell's paper
+// "Implementing Condition Variables with Semaphores"
+
+const NOTIFY_TRIES: usize = 3;
+
+pub struct Condvar {
+    counter: AtomicUsize,
+    timed_out: AtomicUsize,
+}
+
+unsafe impl Send for Condvar {}
+unsafe impl Sync for Condvar {}
+
+impl Condvar {
+    #[inline]
+    #[rustc_const_stable(feature = "const_locks", since = "1.63.0")]
+    pub const fn new() -> Condvar {
+        Condvar { counter: AtomicUsize::new(0), timed_out: AtomicUsize::new(0) }
+    }
+
+    fn notify_some(&self, to_notify: usize) {
+        // Assumption: The Mutex protecting this condvar is locked throughout the
+        // entirety of this call, preventing calls to `wait` and `wait_timeout`.
+
+        // Logic check: Ensure that there aren't any missing waiters. Remove any that
+        // timed-out, ensuring the counter doesn't underflow.
+        assert!(self.timed_out.load(Ordering::Relaxed) <= self.counter.load(Ordering::Relaxed));
+        self.counter.fetch_sub(self.timed_out.swap(0, Ordering::Relaxed), Ordering::Relaxed);
+
+        // Figure out how many threads to notify. Note that it is impossible for `counter`
+        // to increase during this operation because Mutex is locked. However, it is
+        // possible for `counter` to decrease due to a condvar timing out, in which
+        // case the corresponding `timed_out` will increase accordingly.
+        let Ok(waiter_count) =
+            self.counter.fetch_update(Ordering::Relaxed, Ordering::Relaxed, |counter| {
+                if counter == 0 {
+                    return None;
+                } else {
+                    Some(counter - counter.min(to_notify))
+                }
+            })
+        else {
+            // No threads are waiting on this condvar
+            return;
+        };
+
+        let mut remaining_to_wake = waiter_count.min(to_notify);
+        if remaining_to_wake == 0 {
+            return;
+        }
+        for _wake_tries in 0..NOTIFY_TRIES {
+            let result = blocking_scalar(
+                ticktimer_server(),
+                TicktimerScalar::NotifyCondition(self.index(), remaining_to_wake).into(),
+            )
+            .expect("failure to send NotifyCondition command");
+
+            // Remove the list of waiters that were notified
+            remaining_to_wake -= result[0];
+
+            // Also remove the number of waiters that timed out. Clamp it to 0 in order to
+            // ensure we don't wait forever in case the waiter woke up between the time
+            // we counted the remaining waiters and now.
+            remaining_to_wake =
+                remaining_to_wake.saturating_sub(self.timed_out.swap(0, Ordering::Relaxed));
+            if remaining_to_wake == 0 {
+                return;
+            }
+            crate::thread::yield_now();
+        }
+    }
+
+    pub fn notify_one(&self) {
+        self.notify_some(1)
+    }
+
+    pub fn notify_all(&self) {
+        self.notify_some(self.counter.load(Ordering::Relaxed))
+    }
+
+    fn index(&self) -> usize {
+        core::ptr::from_ref(self).addr()
+    }
+
+    /// Unlock the given Mutex and wait for the notification. Wait at most
+    /// `ms` milliseconds, or pass `0` to wait forever.
+    ///
+    /// Returns `true` if the condition was received, `false` if it timed out
+    fn wait_ms(&self, mutex: &Mutex, ms: usize) -> bool {
+        self.counter.fetch_add(1, Ordering::Relaxed);
+        unsafe { mutex.unlock() };
+
+        // Threading concern: There is a chance that the `notify` thread wakes up here before
+        // we have a chance to wait for the condition. This is fine because we've recorded
+        // the fact that we're waiting by incrementing the counter.
+        let result = blocking_scalar(
+            ticktimer_server(),
+            TicktimerScalar::WaitForCondition(self.index(), ms).into(),
+        );
+        let awoken = result.expect("Ticktimer: failure to send WaitForCondition command")[0] == 0;
+
+        // If we awoke due to a timeout, increment the `timed_out` counter so that the
+        // main loop of `notify` knows there's a timeout.
+        //
+        // This is done with the Mutex still unlocked, because the Mutex might still
+        // be locked by the `notify` process above.
+        if !awoken {
+            self.timed_out.fetch_add(1, Ordering::Relaxed);
+        }
+
+        unsafe { mutex.lock() };
+        awoken
+    }
+
+    pub unsafe fn wait(&self, mutex: &Mutex) {
+        // Wait for 0 ms, which is a special case to "wait forever"
+        self.wait_ms(mutex, 0);
+    }
+
+    pub unsafe fn wait_timeout(&self, mutex: &Mutex, dur: Duration) -> bool {
+        let mut millis = dur.as_millis() as usize;
+        // Ensure we don't wait for 0 ms, which would cause us to wait forever
+        if millis == 0 {
+            millis = 1;
+        }
+        self.wait_ms(mutex, millis)
+    }
+}
+
+impl Drop for Condvar {
+    fn drop(&mut self) {
+        let remaining_count = self.counter.load(Ordering::Relaxed);
+        let timed_out = self.timed_out.load(Ordering::Relaxed);
+        assert!(
+            remaining_count - timed_out == 0,
+            "counter was {} and timed_out was {} not 0",
+            remaining_count,
+            timed_out
+        );
+        scalar(ticktimer_server(), TicktimerScalar::FreeCondition(self.index()).into()).ok();
+    }
+}
diff --git a/library/std/src/sys/locks/mutex/mod.rs b/library/std/src/sys/locks/mutex/mod.rs
index 2c4c2f4ef48..cb229d50e55 100644
--- a/library/std/src/sys/locks/mutex/mod.rs
+++ b/library/std/src/sys/locks/mutex/mod.rs
@@ -27,6 +27,9 @@ cfg_if::cfg_if! {
         pub use sgx::Mutex;
     } else if #[cfg(target_os = "solid_asp3")] {
         mod itron;
-        pub use itron::Condvar;
+        pub use itron::Mutex;
+    } else if #[cfg(target_os = "xous")] {
+        mod xous;
+        pub use xous::Mutex;
     }
 }
diff --git a/library/std/src/sys/locks/mutex/xous.rs b/library/std/src/sys/locks/mutex/xous.rs
new file mode 100644
index 00000000000..a8c9518ff0b
--- /dev/null
+++ b/library/std/src/sys/locks/mutex/xous.rs
@@ -0,0 +1,110 @@
+use crate::os::xous::ffi::{blocking_scalar, do_yield};
+use crate::os::xous::services::{ticktimer_server, TicktimerScalar};
+use crate::sync::atomic::{AtomicBool, AtomicUsize, Ordering::Relaxed, Ordering::SeqCst};
+
+pub struct Mutex {
+    /// The "locked" value indicates how many threads are waiting on this
+    /// Mutex. Possible values are:
+    ///     0: The lock is unlocked
+    ///     1: The lock is locked and uncontended
+    ///   >=2: The lock is locked and contended
+    ///
+    /// A lock is "contended" when there is more than one thread waiting
+    /// for a lock, or it is locked for long periods of time. Rather than
+    /// spinning, these locks send a Message to the ticktimer server
+    /// requesting that they be woken up when a lock is unlocked.
+    locked: AtomicUsize,
+
+    /// Whether this Mutex ever was contended, and therefore made a trip
+    /// to the ticktimer server. If this was never set, then we were never
+    /// on the slow path and can skip deregistering the mutex.
+    contended: AtomicBool,
+}
+
+impl Mutex {
+    #[inline]
+    #[rustc_const_stable(feature = "const_locks", since = "1.63.0")]
+    pub const fn new() -> Mutex {
+        Mutex { locked: AtomicUsize::new(0), contended: AtomicBool::new(false) }
+    }
+
+    fn index(&self) -> usize {
+        core::ptr::from_ref(self).addr()
+    }
+
+    #[inline]
+    pub unsafe fn lock(&self) {
+        // Try multiple times to acquire the lock without resorting to the ticktimer
+        // server. For locks that are held for a short amount of time, this will
+        // result in the ticktimer server never getting invoked. The `locked` value
+        // will be either 0 or 1.
+        for _attempts in 0..3 {
+            if unsafe { self.try_lock() } {
+                return;
+            }
+            do_yield();
+        }
+
+        // Try one more time to lock. If the lock is released between the previous code and
+        // here, then the inner `locked` value will be 1 at the end of this. If it was not
+        // locked, then the value will be more than 1, for example if there are multiple other
+        // threads waiting on this lock.
+        if unsafe { self.try_lock_or_poison() } {
+            return;
+        }
+
+        // When this mutex is dropped, we will need to deregister it with the server.
+        self.contended.store(true, Relaxed);
+
+        // The lock is now "contended". When the lock is released, a Message will get sent to the
+        // ticktimer server to wake it up. Note that this may already have happened, so the actual
+        // value of `lock` may be anything (0, 1, 2, ...).
+        blocking_scalar(
+            ticktimer_server(),
+            crate::os::xous::services::TicktimerScalar::LockMutex(self.index()).into(),
+        )
+        .expect("failure to send LockMutex command");
+    }
+
+    #[inline]
+    pub unsafe fn unlock(&self) {
+        let prev = self.locked.fetch_sub(1, SeqCst);
+
+        // If the previous value was 1, then this was a "fast path" unlock, so no
+        // need to involve the Ticktimer server
+        if prev == 1 {
+            return;
+        }
+
+        // If it was 0, then something has gone seriously wrong and the counter
+        // has just wrapped around.
+        if prev == 0 {
+            panic!("mutex lock count underflowed");
+        }
+
+        // Unblock one thread that is waiting on this message.
+        blocking_scalar(ticktimer_server(), TicktimerScalar::UnlockMutex(self.index()).into())
+            .expect("failure to send UnlockMutex command");
+    }
+
+    #[inline]
+    pub unsafe fn try_lock(&self) -> bool {
+        self.locked.compare_exchange(0, 1, SeqCst, SeqCst).is_ok()
+    }
+
+    #[inline]
+    pub unsafe fn try_lock_or_poison(&self) -> bool {
+        self.locked.fetch_add(1, SeqCst) == 0
+    }
+}
+
+impl Drop for Mutex {
+    fn drop(&mut self) {
+        // If there was Mutex contention, then we involved the ticktimer. Free
+        // the resources associated with this Mutex as it is deallocated.
+        if self.contended.load(Relaxed) {
+            blocking_scalar(ticktimer_server(), TicktimerScalar::FreeMutex(self.index()).into())
+                .ok();
+        }
+    }
+}
diff --git a/library/std/src/sys/locks/rwlock/mod.rs b/library/std/src/sys/locks/rwlock/mod.rs
index 35fff36c25d..9d656e57bb3 100644
--- a/library/std/src/sys/locks/rwlock/mod.rs
+++ b/library/std/src/sys/locks/rwlock/mod.rs
@@ -26,5 +26,8 @@ cfg_if::cfg_if! {
     } else if #[cfg(target_os = "teeos")] {
         mod teeos;
         pub use teeos::RwLock;
+    } else if #[cfg(target_os = "xous")] {
+        mod xous;
+        pub use xous::RwLock;
     }
 }
diff --git a/library/std/src/sys/locks/rwlock/xous.rs b/library/std/src/sys/locks/rwlock/xous.rs
new file mode 100644
index 00000000000..ab45b33e1f6
--- /dev/null
+++ b/library/std/src/sys/locks/rwlock/xous.rs
@@ -0,0 +1,74 @@
+use crate::sync::atomic::{AtomicIsize, Ordering::Acquire};
+use crate::thread::yield_now;
+
+pub struct RwLock {
+    /// The "mode" value indicates how many threads are waiting on this
+    /// Mutex. Possible values are:
+    ///    -1: The lock is locked for writing
+    ///     0: The lock is unlocked
+    ///   >=1: The lock is locked for reading
+    ///
+    /// This currently spins waiting for the lock to be freed. An
+    /// optimization would be to involve the ticktimer server to
+    /// coordinate unlocks.
+    mode: AtomicIsize,
+}
+
+const RWLOCK_WRITING: isize = -1;
+const RWLOCK_FREE: isize = 0;
+
+unsafe impl Send for RwLock {}
+unsafe impl Sync for RwLock {}
+
+impl RwLock {
+    #[inline]
+    #[rustc_const_stable(feature = "const_locks", since = "1.63.0")]
+    pub const fn new() -> RwLock {
+        RwLock { mode: AtomicIsize::new(RWLOCK_FREE) }
+    }
+
+    #[inline]
+    pub unsafe fn read(&self) {
+        while !unsafe { self.try_read() } {
+            yield_now();
+        }
+    }
+
+    #[inline]
+    pub unsafe fn try_read(&self) -> bool {
+        self.mode
+            .fetch_update(
+                Acquire,
+                Acquire,
+                |v| if v == RWLOCK_WRITING { None } else { Some(v + 1) },
+            )
+            .is_ok()
+    }
+
+    #[inline]
+    pub unsafe fn write(&self) {
+        while !unsafe { self.try_write() } {
+            yield_now();
+        }
+    }
+
+    #[inline]
+    pub unsafe fn try_write(&self) -> bool {
+        self.mode.compare_exchange(RWLOCK_FREE, RWLOCK_WRITING, Acquire, Acquire).is_ok()
+    }
+
+    #[inline]
+    pub unsafe fn read_unlock(&self) {
+        let previous = self.mode.fetch_sub(1, Acquire);
+        assert!(previous != RWLOCK_FREE);
+        assert!(previous != RWLOCK_WRITING);
+    }
+
+    #[inline]
+    pub unsafe fn write_unlock(&self) {
+        assert_eq!(
+            self.mode.compare_exchange(RWLOCK_WRITING, RWLOCK_FREE, Acquire, Acquire),
+            Ok(RWLOCK_WRITING)
+        );
+    }
+}