diff options
Diffstat (limited to 'library/std/src/sys/sgx/waitqueue')
| -rw-r--r-- | library/std/src/sys/sgx/waitqueue/spin_mutex.rs | 76 | ||||
| -rw-r--r-- | library/std/src/sys/sgx/waitqueue/spin_mutex/tests.rs | 23 | ||||
| -rw-r--r-- | library/std/src/sys/sgx/waitqueue/tests.rs | 20 | ||||
| -rw-r--r-- | library/std/src/sys/sgx/waitqueue/unsafe_list.rs | 146 | ||||
| -rw-r--r-- | library/std/src/sys/sgx/waitqueue/unsafe_list/tests.rs | 103 |
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); + } +} |