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 lock(&self) {
 179         loop {
 180             let mut guard = self.inner.lock();
 181             if guard.locked == false {
 182                 guard.locked = true;
 183                 return;
 184             } else {
 185                 let prio = abi::get_priority();
 186                 let id = abi::getpid();
 187
 188                 guard.blocked_task.push(prio, id);
 189                 abi::block_current_task();
 190                 drop(guard);
 191                 abi::yield_now();
 192             }
 193         }
 194     }
 195
 196     #[inline]
 197     pub unsafe fn unlock(&self) {
 198         let mut guard = self.inner.lock();
 199         guard.locked = false;
 200         if let Some(tid) = guard.blocked_task.pop() {
 201             abi::wakeup_task(tid);
 202         }
 203     }
 204
 205     #[inline]
 206     pub unsafe fn try_lock(&self) -> bool {
 207         let mut guard = self.inner.lock();
 208         if guard.locked == false {
 209             guard.locked = true;
 210         }
 211         guard.locked
 212     }
 213 }