std: move "mod tests/benches" to separate files

Also doing fmt inplace as requested.

5 files changed, 368 insertions, 0 deletions

diff --git a/library/std/src/sys/sgx/waitqueue/spin_mutex.rs b/library/std/src/sys/sgx/waitqueue/spin_mutex.rs
new file mode 100644
index 00000000000..d99ce895da5
--- /dev/null
+++ b/library/std/src/sys/sgx/waitqueue/spin_mutex.rs
@@ -0,0 +1,76 @@
+#[cfg(test)]
+mod tests;
+
+use crate::cell::UnsafeCell;
+use crate::ops::{Deref, DerefMut};
+use crate::sync::atomic::{spin_loop_hint, AtomicBool, Ordering};
+
+#[derive(Default)]
+pub struct SpinMutex<T> {
+    value: UnsafeCell<T>,
+    lock: AtomicBool,
+}
+
+unsafe impl<T: Send> Send for SpinMutex<T> {}
+unsafe impl<T: Send> Sync for SpinMutex<T> {}
+
+pub struct SpinMutexGuard<'a, T: 'a> {
+    mutex: &'a SpinMutex<T>,
+}
+
+impl<'a, T> !Send for SpinMutexGuard<'a, T> {}
+unsafe impl<'a, T: Sync> Sync for SpinMutexGuard<'a, T> {}
+
+impl<T> SpinMutex<T> {
+    pub const fn new(value: T) -> Self {
+        SpinMutex { value: UnsafeCell::new(value), lock: AtomicBool::new(false) }
+    }
+
+    #[inline(always)]
+    pub fn lock(&self) -> SpinMutexGuard<'_, T> {
+        loop {
+            match self.try_lock() {
+                None => {
+                    while self.lock.load(Ordering::Relaxed) {
+                        spin_loop_hint()
+                    }
+                }
+                Some(guard) => return guard,
+            }
+        }
+    }
+
+    #[inline(always)]
+    pub fn try_lock(&self) -> Option<SpinMutexGuard<'_, T>> {
+        if !self.lock.compare_and_swap(false, true, Ordering::Acquire) {
+            Some(SpinMutexGuard { mutex: self })
+        } else {
+            None
+        }
+    }
+}
+
+/// Lock the Mutex or return false.
+pub macro try_lock_or_false($e:expr) {
+    if let Some(v) = $e.try_lock() { v } else { return false }
+}
+
+impl<'a, T> Deref for SpinMutexGuard<'a, T> {
+    type Target = T;
+
+    fn deref(&self) -> &T {
+        unsafe { &*self.mutex.value.get() }
+    }
+}
+
+impl<'a, T> DerefMut for SpinMutexGuard<'a, T> {
+    fn deref_mut(&mut self) -> &mut T {
+        unsafe { &mut *self.mutex.value.get() }
+    }
+}
+
+impl<'a, T> Drop for SpinMutexGuard<'a, T> {
+    fn drop(&mut self) {
+        self.mutex.lock.store(false, Ordering::Release)
+    }
+}
diff --git a/library/std/src/sys/sgx/waitqueue/spin_mutex/tests.rs b/library/std/src/sys/sgx/waitqueue/spin_mutex/tests.rs
new file mode 100644
index 00000000000..4c5994bea61
--- /dev/null
+++ b/library/std/src/sys/sgx/waitqueue/spin_mutex/tests.rs
@@ -0,0 +1,23 @@
+#![allow(deprecated)]
+
+use super::*;
+use crate::sync::Arc;
+use crate::thread;
+use crate::time::Duration;
+
+#[test]
+fn sleep() {
+    let mutex = Arc::new(SpinMutex::<i32>::default());
+    let mutex2 = mutex.clone();
+    let guard = mutex.lock();
+    let t1 = thread::spawn(move || {
+        *mutex2.lock() = 1;
+    });
+
+    thread::sleep(Duration::from_millis(50));
+
+    assert_eq!(*guard, 0);
+    drop(guard);
+    t1.join().unwrap();
+    assert_eq!(*mutex.lock(), 1);
+}
diff --git a/library/std/src/sys/sgx/waitqueue/tests.rs b/library/std/src/sys/sgx/waitqueue/tests.rs
new file mode 100644
index 00000000000..bf91fdd08ed
--- /dev/null
+++ b/library/std/src/sys/sgx/waitqueue/tests.rs
@@ -0,0 +1,20 @@
+use super::*;
+use crate::sync::Arc;
+use crate::thread;
+
+#[test]
+fn queue() {
+    let wq = Arc::new(SpinMutex::<WaitVariable<()>>::default());
+    let wq2 = wq.clone();
+
+    let locked = wq.lock();
+
+    let t1 = thread::spawn(move || {
+        // if we obtain the lock, the main thread should be waiting
+        assert!(WaitQueue::notify_one(wq2.lock()).is_ok());
+    });
+
+    WaitQueue::wait(locked, || {});
+
+    t1.join().unwrap();
+}
diff --git a/library/std/src/sys/sgx/waitqueue/unsafe_list.rs b/library/std/src/sys/sgx/waitqueue/unsafe_list.rs
new file mode 100644
index 00000000000..7a246542739
--- /dev/null
+++ b/library/std/src/sys/sgx/waitqueue/unsafe_list.rs
@@ -0,0 +1,146 @@
+#[cfg(test)]
+mod tests;
+
+use crate::mem;
+use crate::ptr::NonNull;
+
+pub struct UnsafeListEntry<T> {
+    next: NonNull<UnsafeListEntry<T>>,
+    prev: NonNull<UnsafeListEntry<T>>,
+    value: Option<T>,
+}
+
+impl<T> UnsafeListEntry<T> {
+    fn dummy() -> Self {
+        UnsafeListEntry { next: NonNull::dangling(), prev: NonNull::dangling(), value: None }
+    }
+
+    pub fn new(value: T) -> Self {
+        UnsafeListEntry { value: Some(value), ..Self::dummy() }
+    }
+}
+
+pub struct UnsafeList<T> {
+    head_tail: NonNull<UnsafeListEntry<T>>,
+    head_tail_entry: Option<UnsafeListEntry<T>>,
+}
+
+impl<T> UnsafeList<T> {
+    pub const fn new() -> Self {
+        unsafe { UnsafeList { head_tail: NonNull::new_unchecked(1 as _), head_tail_entry: None } }
+    }
+
+    unsafe fn init(&mut self) {
+        if self.head_tail_entry.is_none() {
+            self.head_tail_entry = Some(UnsafeListEntry::dummy());
+            self.head_tail = NonNull::new_unchecked(self.head_tail_entry.as_mut().unwrap());
+            self.head_tail.as_mut().next = self.head_tail;
+            self.head_tail.as_mut().prev = self.head_tail;
+        }
+    }
+
+    pub fn is_empty(&self) -> bool {
+        unsafe {
+            if self.head_tail_entry.is_some() {
+                let first = self.head_tail.as_ref().next;
+                if first == self.head_tail {
+                    // ,-------> /---------\ next ---,
+                    // |         |head_tail|         |
+                    // `--- prev \---------/ <-------`
+                    rtassert!(self.head_tail.as_ref().prev == first);
+                    true
+                } else {
+                    false
+                }
+            } else {
+                true
+            }
+        }
+    }
+
+    /// Pushes an entry onto the back of the list.
+    ///
+    /// # Safety
+    ///
+    /// The entry must remain allocated until the entry is removed from the
+    /// list AND the caller who popped is done using the entry. Special
+    /// care must be taken in the caller of `push` to ensure unwinding does
+    /// not destroy the stack frame containing the entry.
+    pub unsafe fn push<'a>(&mut self, entry: &'a mut UnsafeListEntry<T>) -> &'a T {
+        self.init();
+
+        // BEFORE:
+        //     /---------\ next ---> /---------\
+        // ... |prev_tail|           |head_tail| ...
+        //     \---------/ <--- prev \---------/
+        //
+        // AFTER:
+        //     /---------\ next ---> /-----\ next ---> /---------\
+        // ... |prev_tail|           |entry|           |head_tail| ...
+        //     \---------/ <--- prev \-----/ <--- prev \---------/
+        let mut entry = NonNull::new_unchecked(entry);
+        let mut prev_tail = mem::replace(&mut self.head_tail.as_mut().prev, entry);
+        entry.as_mut().prev = prev_tail;
+        entry.as_mut().next = self.head_tail;
+        prev_tail.as_mut().next = entry;
+        // unwrap ok: always `Some` on non-dummy entries
+        (*entry.as_ptr()).value.as_ref().unwrap()
+    }
+
+    /// Pops an entry from the front of the list.
+    ///
+    /// # Safety
+    ///
+    /// The caller must make sure to synchronize ending the borrow of the
+    /// return value and deallocation of the containing entry.
+    pub unsafe fn pop<'a>(&mut self) -> Option<&'a T> {
+        self.init();
+
+        if self.is_empty() {
+            None
+        } else {
+            // BEFORE:
+            //     /---------\ next ---> /-----\ next ---> /------\
+            // ... |head_tail|           |first|           |second| ...
+            //     \---------/ <--- prev \-----/ <--- prev \------/
+            //
+            // AFTER:
+            //     /---------\ next ---> /------\
+            // ... |head_tail|           |second| ...
+            //     \---------/ <--- prev \------/
+            let mut first = self.head_tail.as_mut().next;
+            let mut second = first.as_mut().next;
+            self.head_tail.as_mut().next = second;
+            second.as_mut().prev = self.head_tail;
+            first.as_mut().next = NonNull::dangling();
+            first.as_mut().prev = NonNull::dangling();
+            // unwrap ok: always `Some` on non-dummy entries
+            Some((*first.as_ptr()).value.as_ref().unwrap())
+        }
+    }
+
+    /// Removes an entry from the list.
+    ///
+    /// # Safety
+    ///
+    /// The caller must ensure that `entry` has been pushed onto `self`
+    /// prior to this call and has not moved since then.
+    pub unsafe fn remove(&mut self, entry: &mut UnsafeListEntry<T>) {
+        rtassert!(!self.is_empty());
+        // BEFORE:
+        //     /----\ next ---> /-----\ next ---> /----\
+        // ... |prev|           |entry|           |next| ...
+        //     \----/ <--- prev \-----/ <--- prev \----/
+        //
+        // AFTER:
+        //     /----\ next ---> /----\
+        // ... |prev|           |next| ...
+        //     \----/ <--- prev \----/
+        let mut prev = entry.prev;
+        let mut next = entry.next;
+        prev.as_mut().next = next;
+        next.as_mut().prev = prev;
+        entry.next = NonNull::dangling();
+        entry.prev = NonNull::dangling();
+    }
+}
diff --git a/library/std/src/sys/sgx/waitqueue/unsafe_list/tests.rs b/library/std/src/sys/sgx/waitqueue/unsafe_list/tests.rs
new file mode 100644
index 00000000000..1f031ed1959
--- /dev/null
+++ b/library/std/src/sys/sgx/waitqueue/unsafe_list/tests.rs
@@ -0,0 +1,103 @@
+use super::*;
+use crate::cell::Cell;
+
+unsafe fn assert_empty<T>(list: &mut UnsafeList<T>) {
+    assert!(list.pop().is_none(), "assertion failed: list is not empty");
+}
+
+#[test]
+fn init_empty() {
+    unsafe {
+        assert_empty(&mut UnsafeList::<i32>::new());
+    }
+}
+
+#[test]
+fn push_pop() {
+    unsafe {
+        let mut node = UnsafeListEntry::new(1234);
+        let mut list = UnsafeList::new();
+        assert_eq!(list.push(&mut node), &1234);
+        assert_eq!(list.pop().unwrap(), &1234);
+        assert_empty(&mut list);
+    }
+}
+
+#[test]
+fn push_remove() {
+    unsafe {
+        let mut node = UnsafeListEntry::new(1234);
+        let mut list = UnsafeList::new();
+        assert_eq!(list.push(&mut node), &1234);
+        list.remove(&mut node);
+        assert_empty(&mut list);
+    }
+}
+
+#[test]
+fn push_remove_pop() {
+    unsafe {
+        let mut node1 = UnsafeListEntry::new(11);
+        let mut node2 = UnsafeListEntry::new(12);
+        let mut node3 = UnsafeListEntry::new(13);
+        let mut node4 = UnsafeListEntry::new(14);
+        let mut node5 = UnsafeListEntry::new(15);
+        let mut list = UnsafeList::new();
+        assert_eq!(list.push(&mut node1), &11);
+        assert_eq!(list.push(&mut node2), &12);
+        assert_eq!(list.push(&mut node3), &13);
+        assert_eq!(list.push(&mut node4), &14);
+        assert_eq!(list.push(&mut node5), &15);
+
+        list.remove(&mut node1);
+        assert_eq!(list.pop().unwrap(), &12);
+        list.remove(&mut node3);
+        assert_eq!(list.pop().unwrap(), &14);
+        list.remove(&mut node5);
+        assert_empty(&mut list);
+
+        assert_eq!(list.push(&mut node1), &11);
+        assert_eq!(list.pop().unwrap(), &11);
+        assert_empty(&mut list);
+
+        assert_eq!(list.push(&mut node3), &13);
+        assert_eq!(list.push(&mut node4), &14);
+        list.remove(&mut node3);
+        list.remove(&mut node4);
+        assert_empty(&mut list);
+    }
+}
+
+#[test]
+fn complex_pushes_pops() {
+    unsafe {
+        let mut node1 = UnsafeListEntry::new(1234);
+        let mut node2 = UnsafeListEntry::new(4567);
+        let mut node3 = UnsafeListEntry::new(9999);
+        let mut node4 = UnsafeListEntry::new(8642);
+        let mut list = UnsafeList::new();
+        list.push(&mut node1);
+        list.push(&mut node2);
+        assert_eq!(list.pop().unwrap(), &1234);
+        list.push(&mut node3);
+        assert_eq!(list.pop().unwrap(), &4567);
+        assert_eq!(list.pop().unwrap(), &9999);
+        assert_empty(&mut list);
+        list.push(&mut node4);
+        assert_eq!(list.pop().unwrap(), &8642);
+        assert_empty(&mut list);
+    }
+}
+
+#[test]
+fn cell() {
+    unsafe {
+        let mut node = UnsafeListEntry::new(Cell::new(0));
+        let mut list = UnsafeList::new();
+        let noderef = list.push(&mut node);
+        assert_eq!(noderef.get(), 0);
+        list.pop().unwrap().set(1);
+        assert_empty(&mut list);
+        assert_eq!(noderef.get(), 1);
+    }
+}