1 /// A simple queue implementation for synchronization primitives.
3 /// This queue is used to implement condition variable and mutexes.
5 /// Users of this API are expected to use the `WaitVariable<T>` type. Since
6 /// that type is not `Sync`, it needs to be protected by e.g., a `SpinMutex` to
7 /// allow shared access.
9 /// Since userspace may send spurious wake-ups, the wakeup event state is
10 /// recorded in the enclave. The wakeup event state is protected by a spinlock.
11 /// The queue and associated wait state are stored in a `WaitVariable`.
13 use crate::ops::{Deref, DerefMut};
14 use crate::num::NonZeroUsize;
16 use fortanix_sgx_abi::{Tcs, EV_UNPARK, WAIT_INDEFINITE};
17 use super::abi::usercalls;
18 use super::abi::thread;
20 use self::unsafe_list::{UnsafeList, UnsafeListEntry};
21 pub use self::spin_mutex::{SpinMutex, SpinMutexGuard, try_lock_or_false};
23 /// An queue entry in a `WaitQueue`.
25 /// TCS address of the thread that is waiting
27 /// Whether this thread has been notified to be awoken
31 /// Data stored with a `WaitQueue` alongside it. This ensures accesses to the
32 /// queue and the data are synchronized, since the type itself is not `Sync`.
34 /// Consumers of this API should use a synchronization primitive for shared
35 /// access, such as `SpinMutex`.
37 pub struct WaitVariable<T> {
42 impl<T> WaitVariable<T> {
43 pub const fn new(var: T) -> Self {
45 queue: WaitQueue::new(),
50 pub fn queue_empty(&self) -> bool {
54 pub fn lock_var(&self) -> &T {
58 pub fn lock_var_mut(&mut self) -> &mut T {
63 #[derive(Copy, Clone)]
64 pub enum NotifiedTcs {
66 All { count: NonZeroUsize }
69 /// An RAII guard that will notify a set of target threads as well as unlock
71 pub struct WaitGuard<'a, T: 'a> {
72 mutex_guard: Option<SpinMutexGuard<'a, WaitVariable<T>>>,
73 notified_tcs: NotifiedTcs
76 /// A queue of threads that are waiting on some synchronization primitive.
78 /// `UnsafeList` entries are allocated on the waiting thread's stack. This
79 /// avoids any global locking that might happen in the heap allocator. This is
80 /// safe because the waiting thread will not return from that stack frame until
81 /// after it is notified. The notifying thread ensures to clean up any
82 /// references to the list entries before sending the wakeup event.
83 pub struct WaitQueue {
84 // We use an inner Mutex here to protect the data in the face of spurious
86 inner: UnsafeList<SpinMutex<WaitEntry>>,
88 unsafe impl Send for WaitQueue {}
90 impl Default for WaitQueue {
91 fn default() -> Self {
96 impl<'a, T> WaitGuard<'a, T> {
97 /// Returns which TCSes will be notified when this guard drops.
98 pub fn notified_tcs(&self) -> NotifiedTcs {
103 impl<'a, T> Deref for WaitGuard<'a, T> {
104 type Target = SpinMutexGuard<'a, WaitVariable<T>>;
106 fn deref(&self) -> &Self::Target {
107 self.mutex_guard.as_ref().unwrap()
111 impl<'a, T> DerefMut for WaitGuard<'a, T> {
112 fn deref_mut(&mut self) -> &mut Self::Target {
113 self.mutex_guard.as_mut().unwrap()
117 impl<'a, T> Drop for WaitGuard<'a, T> {
119 drop(self.mutex_guard.take());
120 let target_tcs = match self.notified_tcs {
121 NotifiedTcs::Single(tcs) => Some(tcs),
122 NotifiedTcs::All { .. } => None
124 usercalls::send(EV_UNPARK, target_tcs).unwrap();
129 pub const fn new() -> Self {
131 inner: UnsafeList::new()
135 pub fn is_empty(&self) -> bool {
136 self.inner.is_empty()
139 /// Adds the calling thread to the `WaitVariable`'s wait queue, then wait
140 /// until a wakeup event.
142 /// This function does not return until this thread has been awoken.
143 pub fn wait<T>(mut guard: SpinMutexGuard<'_, WaitVariable<T>>) {
145 let mut entry = UnsafeListEntry::new(SpinMutex::new(WaitEntry {
146 tcs: thread::current(),
149 let entry = guard.queue.inner.push(&mut entry);
151 while !entry.lock().wake {
153 usercalls::wait(EV_UNPARK, WAIT_INDEFINITE).unwrap() & EV_UNPARK,
160 /// Either find the next waiter on the wait queue, or return the mutex
163 /// If a waiter is found, a `WaitGuard` is returned which will notify the
164 /// waiter when it is dropped.
165 pub fn notify_one<T>(mut guard: SpinMutexGuard<'_, WaitVariable<T>>)
166 -> Result<WaitGuard<'_, T>, SpinMutexGuard<'_, WaitVariable<T>>>
169 if let Some(entry) = guard.queue.inner.pop() {
170 let mut entry_guard = entry.lock();
171 let tcs = entry_guard.tcs;
172 entry_guard.wake = true;
175 mutex_guard: Some(guard),
176 notified_tcs: NotifiedTcs::Single(tcs)
184 /// Either find any and all waiters on the wait queue, or return the mutex
187 /// If at least one waiter is found, a `WaitGuard` is returned which will
188 /// notify all waiters when it is dropped.
189 pub fn notify_all<T>(mut guard: SpinMutexGuard<'_, WaitVariable<T>>)
190 -> Result<WaitGuard<'_, T>, SpinMutexGuard<'_, WaitVariable<T>>>
194 while let Some(entry) = guard.queue.inner.pop() {
196 let mut entry_guard = entry.lock();
197 entry_guard.wake = true;
199 if let Some(count) = NonZeroUsize::new(count) {
201 mutex_guard: Some(guard),
202 notified_tcs: NotifiedTcs::All { count }
211 /// A doubly-linked list where callers are in charge of memory allocation
212 /// of the nodes in the list.
214 use crate::ptr::NonNull;
217 pub struct UnsafeListEntry<T> {
218 next: NonNull<UnsafeListEntry<T>>,
219 prev: NonNull<UnsafeListEntry<T>>,
223 impl<T> UnsafeListEntry<T> {
226 next: NonNull::dangling(),
227 prev: NonNull::dangling(),
232 pub fn new(value: T) -> Self {
240 pub struct UnsafeList<T> {
241 head_tail: NonNull<UnsafeListEntry<T>>,
242 head_tail_entry: Option<UnsafeListEntry<T>>,
245 impl<T> UnsafeList<T> {
246 pub const fn new() -> Self {
249 head_tail: NonNull::new_unchecked(1 as _),
250 head_tail_entry: None
255 unsafe fn init(&mut self) {
256 if self.head_tail_entry.is_none() {
257 self.head_tail_entry = Some(UnsafeListEntry::dummy());
258 self.head_tail = NonNull::new_unchecked(self.head_tail_entry.as_mut().unwrap());
259 self.head_tail.as_mut().next = self.head_tail;
260 self.head_tail.as_mut().prev = self.head_tail;
264 pub fn is_empty(&self) -> bool {
266 if self.head_tail_entry.is_some() {
267 let first = self.head_tail.as_ref().next;
268 if first == self.head_tail {
269 // ,-------> /---------\ next ---,
271 // `--- prev \---------/ <-------`
272 assert_eq!(self.head_tail.as_ref().prev, first);
283 /// Pushes an entry onto the back of the list.
287 /// The entry must remain allocated until the entry is removed from the
288 /// list AND the caller who popped is done using the entry.
289 pub unsafe fn push<'a>(&mut self, entry: &'a mut UnsafeListEntry<T>) -> &'a T {
293 // /---------\ next ---> /---------\
294 // ... |prev_tail| |head_tail| ...
295 // \---------/ <--- prev \---------/
298 // /---------\ next ---> /-----\ next ---> /---------\
299 // ... |prev_tail| |entry| |head_tail| ...
300 // \---------/ <--- prev \-----/ <--- prev \---------/
301 let mut entry = NonNull::new_unchecked(entry);
302 let mut prev_tail = mem::replace(&mut self.head_tail.as_mut().prev, entry);
303 entry.as_mut().prev = prev_tail;
304 entry.as_mut().next = self.head_tail;
305 prev_tail.as_mut().next = entry;
306 (*entry.as_ptr()).value.as_ref().unwrap()
309 /// Pops an entry from the front of the list.
313 /// The caller must make sure to synchronize ending the borrow of the
314 /// return value and deallocation of the containing entry.
315 pub unsafe fn pop<'a>(&mut self) -> Option<&'a T> {
322 // /---------\ next ---> /-----\ next ---> /------\
323 // ... |head_tail| |first| |second| ...
324 // \---------/ <--- prev \-----/ <--- prev \------/
327 // /---------\ next ---> /------\
328 // ... |head_tail| |second| ...
329 // \---------/ <--- prev \------/
330 let mut first = self.head_tail.as_mut().next;
331 let mut second = first.as_mut().next;
332 self.head_tail.as_mut().next = second;
333 second.as_mut().prev = self.head_tail;
334 first.as_mut().next = NonNull::dangling();
335 first.as_mut().prev = NonNull::dangling();
336 Some((*first.as_ptr()).value.as_ref().unwrap())
344 use crate::cell::Cell;
346 unsafe fn assert_empty<T>(list: &mut UnsafeList<T>) {
347 assert!(list.pop().is_none(), "assertion failed: list is not empty");
353 assert_empty(&mut UnsafeList::<i32>::new());
360 let mut node = UnsafeListEntry::new(1234);
361 let mut list = UnsafeList::new();
362 assert_eq!(list.push(&mut node), &1234);
363 assert_eq!(list.pop().unwrap(), &1234);
364 assert_empty(&mut list);
369 fn complex_pushes_pops() {
371 let mut node1 = UnsafeListEntry::new(1234);
372 let mut node2 = UnsafeListEntry::new(4567);
373 let mut node3 = UnsafeListEntry::new(9999);
374 let mut node4 = UnsafeListEntry::new(8642);
375 let mut list = UnsafeList::new();
376 list.push(&mut node1);
377 list.push(&mut node2);
378 assert_eq!(list.pop().unwrap(), &1234);
379 list.push(&mut node3);
380 assert_eq!(list.pop().unwrap(), &4567);
381 assert_eq!(list.pop().unwrap(), &9999);
382 assert_empty(&mut list);
383 list.push(&mut node4);
384 assert_eq!(list.pop().unwrap(), &8642);
385 assert_empty(&mut list);
392 let mut node = UnsafeListEntry::new(Cell::new(0));
393 let mut list = UnsafeList::new();
394 let noderef = list.push(&mut node);
395 assert_eq!(noderef.get(), 0);
396 list.pop().unwrap().set(1);
397 assert_empty(&mut list);
398 assert_eq!(noderef.get(), 1);
404 /// Trivial spinlock-based implementation of `sync::Mutex`.
405 // FIXME: Perhaps use Intel TSX to avoid locking?
407 use crate::cell::UnsafeCell;
408 use crate::sync::atomic::{AtomicBool, Ordering, spin_loop_hint};
409 use crate::ops::{Deref, DerefMut};
412 pub struct SpinMutex<T> {
413 value: UnsafeCell<T>,
417 unsafe impl<T: Send> Send for SpinMutex<T> {}
418 unsafe impl<T: Send> Sync for SpinMutex<T> {}
420 pub struct SpinMutexGuard<'a, T: 'a> {
421 mutex: &'a SpinMutex<T>,
424 impl<'a, T> !Send for SpinMutexGuard<'a, T> {}
425 unsafe impl<'a, T: Sync> Sync for SpinMutexGuard<'a, T> {}
427 impl<T> SpinMutex<T> {
428 pub const fn new(value: T) -> Self {
430 value: UnsafeCell::new(value),
431 lock: AtomicBool::new(false)
436 pub fn lock(&self) -> SpinMutexGuard<'_, T> {
438 match self.try_lock() {
439 None => while self.lock.load(Ordering::Relaxed) {
442 Some(guard) => return guard
448 pub fn try_lock(&self) -> Option<SpinMutexGuard<'_, T>> {
449 if !self.lock.compare_and_swap(false, true, Ordering::Acquire) {
450 Some(SpinMutexGuard {
459 /// Lock the Mutex or return false.
460 pub macro try_lock_or_false {
462 if let Some(v) = $e.try_lock() {
470 impl<'a, T> Deref for SpinMutexGuard<'a, T> {
473 fn deref(&self) -> &T {
475 &*self.mutex.value.get()
480 impl<'a, T> DerefMut for SpinMutexGuard<'a, T> {
481 fn deref_mut(&mut self) -> &mut T {
483 &mut*self.mutex.value.get()
488 impl<'a, T> Drop for SpinMutexGuard<'a, T> {
490 self.mutex.lock.store(false, Ordering::Release)
496 #![allow(deprecated)]
499 use crate::sync::Arc;
501 use crate::time::{SystemTime, Duration};
505 let mutex = Arc::new(SpinMutex::<i32>::default());
506 let mutex2 = mutex.clone();
507 let guard = mutex.lock();
508 let t1 = thread::spawn(move || {
513 // FIXME: https://github.com/fortanix/rust-sgx/issues/31
514 let start = SystemTime::now();
515 let max = Duration::from_millis(50);
516 while start.elapsed().unwrap() < max {}
518 assert_eq!(*guard, 0);
521 assert_eq!(*mutex.lock(), 1);
529 use crate::sync::Arc;
534 let wq = Arc::new(SpinMutex::<WaitVariable<()>>::default());
535 let wq2 = wq.clone();
537 let locked = wq.lock();
539 let t1 = thread::spawn(move || {
540 // if we obtain the lock, the main thread should be waiting
541 assert!(WaitQueue::notify_one(wq2.lock()).is_ok());
544 WaitQueue::wait(locked);