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

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