tiny_std/sync/
mutex.rs

1//! Mutex implementation essentially copied from std.
2//! Thus the license for it is this:
3//! ---
4//!
5//! Permission is hereby granted, free of charge, to any
6//! person obtaining a copy of this software and associated
7//! documentation files (the "Software"), to deal in the
8//! Software without restriction, including without
9//! limitation the rights to use, copy, modify, merge,
10//! publish, distribute, sublicense, and/or sell copies of
11//! the Software, and to permit persons to whom the Software
12//! is furnished to do so, subject to the following
13//! conditions:
14//!
15//! The above copyright notice and this permission notice
16//! shall be included in all copies or substantial portions
17//! of the Software.
18//!
19//! THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
20//! ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
21//! TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
22//! PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
23//! SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
24//! CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25//! OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
26//! IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27//! DEALINGS IN THE SOFTWARE.
28//!
29//! ---
30//! Lifted from at [Rusts github](https://github.com/rust-lang/rust) `77e24f90f599070af2d8051ef9adad7fe528dd78`
31use crate::sync::{futex_wait_fast, NotSend};
32use core::cell::UnsafeCell;
33use core::fmt;
34use core::sync::atomic::{
35    AtomicU32,
36    Ordering::{Acquire, Relaxed, Release},
37};
38use rusl::futex::futex_wake;
39
40struct InnerMutex {
41    /// 0: unlocked
42    /// 1: locked, no other threads waiting
43    /// 2: locked, and other threads waiting (contended)
44    futex: AtomicU32,
45}
46
47impl InnerMutex {
48    #[inline]
49    const fn new() -> Self {
50        Self {
51            futex: AtomicU32::new(0),
52        }
53    }
54
55    #[inline]
56    fn try_lock(&self) -> bool {
57        self.futex.compare_exchange(0, 1, Acquire, Relaxed).is_ok()
58    }
59
60    #[inline]
61    fn lock(&self) {
62        if self.futex.compare_exchange(0, 1, Acquire, Relaxed).is_err() {
63            self.lock_contended();
64        }
65    }
66
67    #[cold]
68    fn lock_contended(&self) {
69        // Spin first to speed things up if the lock is released quickly.
70        let mut state = self.spin();
71
72        // If it's unlocked now, attempt to take the lock
73        // without marking it as contended.
74        if state == 0 {
75            match self.futex.compare_exchange(0, 1, Acquire, Relaxed) {
76                Ok(_) => return, // Locked!
77                Err(s) => state = s,
78            }
79        }
80
81        loop {
82            // Put the lock in contended state.
83            // We avoid an unnecessary write if it as already set to 2,
84            // to be friendlier for the caches.
85            if state != 2 && self.futex.swap(2, Acquire) == 0 {
86                // We changed it from 0 to 2, so we just successfully locked it.
87                return;
88            }
89
90            // Wait for the futex to change state, assuming it is still 2.
91            futex_wait_fast(&self.futex, 2);
92
93            // Spin again after waking up.
94            state = self.spin();
95        }
96    }
97
98    fn spin(&self) -> u32 {
99        let mut spin = 100;
100        loop {
101            // We only use `load` (and not `swap` or `compare_exchange`)
102            // while spinning, to be easier on the caches.
103            let state = self.futex.load(Relaxed);
104
105            // We stop spinning when the mutex is unlocked (0),
106            // but also when it's contended (2).
107            if state != 1 || spin == 0 {
108                return state;
109            }
110
111            core::hint::spin_loop();
112            spin -= 1;
113        }
114    }
115
116    #[inline]
117    unsafe fn unlock(&self) {
118        if self.futex.swap(0, Release) == 2 {
119            // We only wake up one thread. When that thread locks the mutex, it
120            // will mark the mutex as contended (2) (see lock_contended above),
121            // which makes sure that any other waiting threads will also be
122            // woken up eventually.
123            self.wake();
124        }
125    }
126
127    #[cold]
128    fn wake(&self) {
129        let _ = futex_wake(&self.futex, 1);
130    }
131}
132
133pub struct Mutex<T: ?Sized> {
134    inner: InnerMutex,
135    data: UnsafeCell<T>,
136}
137
138// these are the only places where `T: Send` matters; all other
139// functionality works fine on a single thread.
140unsafe impl<T: ?Sized + Send> Send for Mutex<T> {}
141unsafe impl<T: ?Sized + Send> Sync for Mutex<T> {}
142
143#[must_use = "if unused the Mutex will immediately unlock"]
144#[clippy::has_significant_drop]
145pub struct MutexGuard<'a, T: ?Sized + 'a> {
146    lock: &'a Mutex<T>,
147    _not_send: NotSend,
148}
149
150unsafe impl<T: ?Sized + Sync> Sync for MutexGuard<'_, T> {}
151
152impl<T> Mutex<T> {
153    #[inline]
154    pub const fn new(t: T) -> Mutex<T> {
155        Mutex {
156            inner: InnerMutex::new(),
157            data: UnsafeCell::new(t),
158        }
159    }
160}
161
162impl<T: ?Sized> Mutex<T> {
163    pub fn lock(&self) -> MutexGuard<'_, T> {
164        unsafe {
165            self.inner.lock();
166            MutexGuard::new(self)
167        }
168    }
169
170    pub fn try_lock(&self) -> Option<MutexGuard<'_, T>> {
171        unsafe {
172            if self.inner.try_lock() {
173                Some(MutexGuard::new(self))
174            } else {
175                None
176            }
177        }
178    }
179
180    #[inline]
181    pub fn into_inner(self) -> T
182    where
183        T: Sized,
184    {
185        self.data.into_inner()
186    }
187
188    #[inline]
189    pub fn get_mut(&mut self) -> &mut T {
190        self.data.get_mut()
191    }
192}
193
194impl<T: Default> Default for Mutex<T> {
195    /// Creates a `Mutex<T>`, with the `Default` value for T.
196    fn default() -> Mutex<T> {
197        Mutex::new(Default::default())
198    }
199}
200
201impl<T: ?Sized + fmt::Debug> fmt::Debug for Mutex<T> {
202    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
203        let mut d = f.debug_struct("Mutex");
204        if let Some(guard) = self.try_lock() {
205            d.field("data", &&*guard);
206        } else {
207            struct LockedPlaceholder;
208            impl fmt::Debug for LockedPlaceholder {
209                fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
210                    f.write_str("<locked>")
211                }
212            }
213            d.field("data", &LockedPlaceholder);
214        }
215        d.finish_non_exhaustive()
216    }
217}
218
219impl<'mutex, T: ?Sized> MutexGuard<'mutex, T> {
220    unsafe fn new(lock: &'mutex Mutex<T>) -> MutexGuard<'mutex, T> {
221        MutexGuard {
222            lock,
223            _not_send: NotSend::new(),
224        }
225    }
226}
227
228impl<T: ?Sized> core::ops::Deref for MutexGuard<'_, T> {
229    type Target = T;
230
231    fn deref(&self) -> &T {
232        unsafe { &*self.lock.data.get() }
233    }
234}
235
236impl<T: ?Sized> core::ops::DerefMut for MutexGuard<'_, T> {
237    fn deref_mut(&mut self) -> &mut T {
238        unsafe { &mut *self.lock.data.get() }
239    }
240}
241
242impl<T: ?Sized> Drop for MutexGuard<'_, T> {
243    #[inline]
244    fn drop(&mut self) {
245        unsafe {
246            self.lock.inner.unlock();
247        }
248    }
249}
250
251impl<T: ?Sized + fmt::Debug> fmt::Debug for MutexGuard<'_, T> {
252    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
253        fmt::Debug::fmt(&**self, f)
254    }
255}
256
257#[cfg(test)]
258mod tests {
259    use crate::sync::Mutex;
260    use core::time::Duration;
261
262    #[test]
263    fn lock_threaded_mutex() {
264        let count = std::sync::Arc::new(Mutex::new(0));
265        let mut handles = std::vec::Vec::new();
266        for _i in 0..15 {
267            let count_c = count.clone();
268            let handle = std::thread::spawn(move || {
269                // Try to create some contention
270                let mut guard = count_c.lock();
271                std::thread::sleep(Duration::from_millis(1));
272                *guard += 1;
273            });
274            handles.push(handle);
275        }
276        for h in handles {
277            h.join().unwrap();
278        }
279        assert_eq!(15, *count.lock());
280    }
281
282    #[test]
283    fn try_lock_threaded_mutex() {
284        let val = std::sync::Arc::new(Mutex::new(0));
285        let val_c = val.clone();
286        assert_eq!(0, *val_c.try_lock().unwrap());
287        std::thread::spawn(move || {
288            let _guard = val_c.lock();
289            std::thread::sleep(Duration::from_millis(2000));
290        });
291        // ... Timing
292        std::thread::sleep(Duration::from_millis(100));
293        assert!(val.try_lock().is_none());
294    }
295}
tiny_std/sync/mutex.rs

tiny_std/sync/
mutex.rs
