library/std/src/sys/hermit/mutex.rs

   1 use crate::cell::UnsafeCell;
   2 use crate::collections::VecDeque;
   3 use crate::ffi::c_void;
   4 use crate::hint;
   5 use crate::ops::{Deref, DerefMut, Drop};
   6 use crate::ptr;
   7 use crate::sync::atomic::{AtomicUsize, Ordering};
   8 use crate::sys::hermit::abi;
   9
  10 /// This type provides a lock based on busy waiting to realize mutual exclusion
  11 ///
  12 /// # Description
  13 ///
  14 /// This structure behaves a lot like a common mutex. There are some differences:
  15 ///
  16 /// - By using busy waiting, it can be used outside the runtime.
  17 /// - It is a so called ticket lock and is completly fair.
  18 #[cfg_attr(target_arch = "x86_64", repr(align(128)))]
  19 #[cfg_attr(not(target_arch = "x86_64"), repr(align(64)))]
  20 struct Spinlock<T: ?Sized> {
  21     queue: AtomicUsize,
  22     dequeue: AtomicUsize,
  23     data: UnsafeCell<T>,
  24 }
  25
  26 unsafe impl<T: ?Sized + Send> Sync for Spinlock<T> {}
  27 unsafe impl<T: ?Sized + Send> Send for Spinlock<T> {}
  28
  29 /// A guard to which the protected data can be accessed
  30 ///
  31 /// When the guard falls out of scope it will release the lock.
  32 struct SpinlockGuard<'a, T: ?Sized + 'a> {
  33     dequeue: &'a AtomicUsize,
  34     data: &'a mut T,
  35 }
  36
  37 impl<T> Spinlock<T> {
  38     pub const fn new(user_data: T) -> Spinlock<T> {
  39         Spinlock {
  40             queue: AtomicUsize::new(0),
  41             dequeue: AtomicUsize::new(1),
  42             data: UnsafeCell::new(user_data),
  43         }
  44     }
  45
  46     #[inline]
  47     fn obtain_lock(&self) {
  48         let ticket = self.queue.fetch_add(1, Ordering::SeqCst) + 1;
  49         while self.dequeue.load(Ordering::SeqCst) != ticket {
  50             hint::spin_loop();
  51         }
  52     }
  53
  54     #[inline]
  55     pub unsafe fn lock(&self) -> SpinlockGuard<'_, T> {
  56         self.obtain_lock();
  57         SpinlockGuard { dequeue: &self.dequeue, data: &mut *self.data.get() }
  58     }
  59 }
  60
  61 impl<T: ?Sized + Default> Default for Spinlock<T> {
  62     fn default() -> Spinlock<T> {
  63         Spinlock::new(Default::default())
  64     }
  65 }
  66
  67 impl<'a, T: ?Sized> Deref for SpinlockGuard<'a, T> {
  68     type Target = T;
  69     fn deref(&self) -> &T {
  70         &*self.data
  71     }
  72 }
  73
  74 impl<'a, T: ?Sized> DerefMut for SpinlockGuard<'a, T> {
  75     fn deref_mut(&mut self) -> &mut T {
  76         &mut *self.data
  77     }
  78 }
  79
  80 impl<'a, T: ?Sized> Drop for SpinlockGuard<'a, T> {
  81     /// The dropping of the SpinlockGuard will release the lock it was created from.
  82     fn drop(&mut self) {
  83         self.dequeue.fetch_add(1, Ordering::SeqCst);
  84     }
  85 }
  86
  87 /// Realize a priority queue for tasks
  88 struct PriorityQueue {
  89     queues: [Option<VecDeque<abi::Tid>>; abi::NO_PRIORITIES],
  90     prio_bitmap: u64,
  91 }
  92
  93 impl PriorityQueue {
  94     pub const fn new() -> PriorityQueue {
  95         PriorityQueue {
  96             queues: [
  97                 None, None, None, None, None, None, None, None, None, None, None, None, None, None,
  98                 None, None, None, None, None, None, None, None, None, None, None, None, None, None,
  99                 None, None, None,
 100             ],
 101             prio_bitmap: 0,
 102         }
 103     }
 104
 105     /// Add a task id by its priority to the queue
 106     pub fn push(&mut self, prio: abi::Priority, id: abi::Tid) {
 107         let i: usize = prio.into().into();
 108         self.prio_bitmap |= (1 << i) as u64;
 109         if let Some(queue) = &mut self.queues[i] {
 110             queue.push_back(id);
 111         } else {
 112             let mut queue = VecDeque::new();
 113             queue.push_back(id);
 114             self.queues[i] = Some(queue);
 115         }
 116     }
 117
 118     fn pop_from_queue(&mut self, queue_index: usize) -> Option<abi::Tid> {
 119         if let Some(queue) = &mut self.queues[queue_index] {
 120             let id = queue.pop_front();
 121
 122             if queue.is_empty() {
 123                 self.prio_bitmap &= !(1 << queue_index as u64);
 124             }
 125
 126             id
 127         } else {
 128             None
 129         }
 130     }
 131
 132     /// Pop the task handle with the highest priority from the queue
 133     pub fn pop(&mut self) -> Option<abi::Tid> {
 134         for i in 0..abi::NO_PRIORITIES {
 135             if self.prio_bitmap & (1 << i) != 0 {
 136                 return self.pop_from_queue(i);
 137             }
 138         }
 139
 140         None
 141     }
 142 }
 143
 144 struct MutexInner {
 145     locked: bool,
 146     blocked_task: PriorityQueue,
 147 }
 148
 149 impl MutexInner {
 150     pub const fn new() -> MutexInner {
 151         MutexInner { locked: false, blocked_task: PriorityQueue::new() }
 152     }
 153 }
 154
 155 pub struct Mutex {
 156     inner: Spinlock<MutexInner>,
 157 }
 158
 159 pub type MovableMutex = Box<Mutex>;
 160
 161 unsafe impl Send for Mutex {}
 162 unsafe impl Sync for Mutex {}
 163
 164 impl Mutex {
 165     pub const fn new() -> Mutex {
 166         Mutex { inner: Spinlock::new(MutexInner::new()) }
 167     }
 168
 169     #[inline]
 170     pub unsafe fn init(&mut self) {
 171         self.inner = Spinlock::new(MutexInner::new());
 172     }
 173
 174     #[inline]
 175     pub unsafe fn lock(&self) {
 176         loop {
 177             let mut guard = self.inner.lock();
 178             if guard.locked == false {
 179                 guard.locked = true;
 180                 return;
 181             } else {
 182                 let prio = abi::get_priority();
 183                 let id = abi::getpid();
 184
 185                 guard.blocked_task.push(prio, id);
 186                 abi::block_current_task();
 187                 drop(guard);
 188                 abi::yield_now();
 189             }
 190         }
 191     }
 192
 193     #[inline]
 194     pub unsafe fn unlock(&self) {
 195         let mut guard = self.inner.lock();
 196         guard.locked = false;
 197         if let Some(tid) = guard.blocked_task.pop() {
 198             abi::wakeup_task(tid);
 199         }
 200     }
 201
 202     #[inline]
 203     pub unsafe fn try_lock(&self) -> bool {
 204         let mut guard = self.inner.lock();
 205         if guard.locked == false {
 206             guard.locked = true;
 207         }
 208         guard.locked
 209     }
 210
 211     #[inline]
 212     pub unsafe fn destroy(&self) {}
 213 }
 214
 215 pub struct ReentrantMutex {
 216     inner: *const c_void,
 217 }
 218
 219 impl ReentrantMutex {
 220     pub const unsafe fn uninitialized() -> ReentrantMutex {
 221         ReentrantMutex { inner: ptr::null() }
 222     }
 223
 224     #[inline]
 225     pub unsafe fn init(&self) {
 226         let _ = abi::recmutex_init(&self.inner as *const *const c_void as *mut _);
 227     }
 228
 229     #[inline]
 230     pub unsafe fn lock(&self) {
 231         let _ = abi::recmutex_lock(self.inner);
 232     }
 233
 234     #[inline]
 235     pub unsafe fn try_lock(&self) -> bool {
 236         true
 237     }
 238
 239     #[inline]
 240     pub unsafe fn unlock(&self) {
 241         let _ = abi::recmutex_unlock(self.inner);
 242     }
 243
 244     #[inline]
 245     pub unsafe fn destroy(&self) {
 246         let _ = abi::recmutex_destroy(self.inner);
 247     }
 248 }