1 // Copyright 2016 Amanieu d'Antras
2 //
3 // Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4 // http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5 // http://opensource.org/licenses/MIT>, at your option. This file may not be
6 // copied, modified, or distributed except according to those terms.
7
8 use crate::raw_fair_mutex::RawFairMutex;
9 use lock_api;
10
11 /// A mutual exclusive primitive that is always fair, useful for protecting shared data
12 ///
13 /// This mutex will block threads waiting for the lock to become available. The
14 /// mutex can also be statically initialized or created via a `new`
15 /// constructor. Each mutex has a type parameter which represents the data that
16 /// it is protecting. The data can only be accessed through the RAII guards
17 /// returned from `lock` and `try_lock`, which guarantees that the data is only
18 /// ever accessed when the mutex is locked.
19 ///
20 /// The regular mutex provided by `parking_lot` uses eventual locking fairness
21 /// (after some time it will default to the fair algorithm), but eventual
22 /// fairness does not provide the same garantees a always fair method would.
23 /// Fair mutexes are generally slower, but sometimes needed. This wrapper was
24 /// created to avoid using a unfair protocol when it's forbidden by mistake.
25 ///
26 /// In a fair mutex the lock is provided to whichever thread asked first,
27 /// they form a queue and always follow the first-in first-out order. This
28 /// means some thread in the queue won't be able to steal the lock and use it fast
29 /// to increase throughput, at the cost of latency. Since the response time will grow
30 /// for some threads that are waiting for the lock and losing to faster but later ones,
31 /// but it may make sending more responses possible.
32 ///
33 /// A fair mutex may not be interesting if threads have different priorities (this is known as
34 /// priority inversion).
35 ///
36 /// # Differences from the standard library `Mutex`
37 ///
38 /// - No poisoning, the lock is released normally on panic.
39 /// - Only requires 1 byte of space, whereas the standard library boxes the
40 /// `FairMutex` due to platform limitations.
41 /// - Can be statically constructed (requires the `const_fn` nightly feature).
42 /// - Does not require any drop glue when dropped.
43 /// - Inline fast path for the uncontended case.
44 /// - Efficient handling of micro-contention using adaptive spinning.
45 /// - Allows raw locking & unlocking without a guard.
46 ///
47 /// # Examples
48 ///
49 /// ```
50 /// use parking_lot::FairMutex;
51 /// use std::sync::{Arc, mpsc::channel};
52 /// use std::thread;
53 ///
54 /// const N: usize = 10;
55 ///
56 /// // Spawn a few threads to increment a shared variable (non-atomically), and
57 /// // let the main thread know once all increments are done.
58 /// //
59 /// // Here we're using an Arc to share memory among threads, and the data inside
60 /// // the Arc is protected with a mutex.
61 /// let data = Arc::new(FairMutex::new(0));
62 ///
63 /// let (tx, rx) = channel();
64 /// for _ in 0..10 {
65 /// let (data, tx) = (Arc::clone(&data), tx.clone());
66 /// thread::spawn(move || {
67 /// // The shared state can only be accessed once the lock is held.
68 /// // Our non-atomic increment is safe because we're the only thread
69 /// // which can access the shared state when the lock is held.
70 /// let mut data = data.lock();
71 /// *data += 1;
72 /// if *data == N {
73 /// tx.send(()).unwrap();
74 /// }
75 /// // the lock is unlocked here when `data` goes out of scope.
76 /// });
77 /// }
78 ///
79 /// rx.recv().unwrap();
80 /// ```
81 pub type FairMutex<T> = lock_api::Mutex<RawFairMutex, T>;
82
83 /// Creates a new fair mutex in an unlocked state ready for use.
84 ///
85 /// This allows creating a fair mutex in a constant context on stable Rust.
const_fair_mutex<T>(val: T) -> FairMutex<T>86 pub const fn const_fair_mutex<T>(val: T) -> FairMutex<T> {
87 FairMutex::const_new(<RawFairMutex as lock_api::RawMutex>::INIT, val)
88 }
89
90 /// An RAII implementation of a "scoped lock" of a mutex. When this structure is
91 /// dropped (falls out of scope), the lock will be unlocked.
92 ///
93 /// The data protected by the mutex can be accessed through this guard via its
94 /// `Deref` and `DerefMut` implementations.
95 pub type FairMutexGuard<'a, T> = lock_api::MutexGuard<'a, RawFairMutex, T>;
96
97 /// An RAII mutex guard returned by `FairMutexGuard::map`, which can point to a
98 /// subfield of the protected data.
99 ///
100 /// The main difference between `MappedFairMutexGuard` and `FairMutexGuard` is that the
101 /// former doesn't support temporarily unlocking and re-locking, since that
102 /// could introduce soundness issues if the locked object is modified by another
103 /// thread.
104 pub type MappedFairMutexGuard<'a, T> = lock_api::MappedMutexGuard<'a, RawFairMutex, T>;
105
106 #[cfg(test)]
107 mod tests {
108 use crate::FairMutex;
109 use std::sync::atomic::{AtomicUsize, Ordering};
110 use std::sync::mpsc::channel;
111 use std::sync::Arc;
112 use std::thread;
113
114 #[cfg(feature = "serde")]
115 use bincode::{deserialize, serialize};
116
117 #[derive(Eq, PartialEq, Debug)]
118 struct NonCopy(i32);
119
120 #[test]
smoke()121 fn smoke() {
122 let m = FairMutex::new(());
123 drop(m.lock());
124 drop(m.lock());
125 }
126
127 #[test]
lots_and_lots()128 fn lots_and_lots() {
129 const J: u32 = 1000;
130 const K: u32 = 3;
131
132 let m = Arc::new(FairMutex::new(0));
133
134 fn inc(m: &FairMutex<u32>) {
135 for _ in 0..J {
136 *m.lock() += 1;
137 }
138 }
139
140 let (tx, rx) = channel();
141 for _ in 0..K {
142 let tx2 = tx.clone();
143 let m2 = m.clone();
144 thread::spawn(move || {
145 inc(&m2);
146 tx2.send(()).unwrap();
147 });
148 let tx2 = tx.clone();
149 let m2 = m.clone();
150 thread::spawn(move || {
151 inc(&m2);
152 tx2.send(()).unwrap();
153 });
154 }
155
156 drop(tx);
157 for _ in 0..2 * K {
158 rx.recv().unwrap();
159 }
160 assert_eq!(*m.lock(), J * K * 2);
161 }
162
163 #[test]
try_lock()164 fn try_lock() {
165 let m = FairMutex::new(());
166 *m.try_lock().unwrap() = ();
167 }
168
169 #[test]
test_into_inner()170 fn test_into_inner() {
171 let m = FairMutex::new(NonCopy(10));
172 assert_eq!(m.into_inner(), NonCopy(10));
173 }
174
175 #[test]
test_into_inner_drop()176 fn test_into_inner_drop() {
177 struct Foo(Arc<AtomicUsize>);
178 impl Drop for Foo {
179 fn drop(&mut self) {
180 self.0.fetch_add(1, Ordering::SeqCst);
181 }
182 }
183 let num_drops = Arc::new(AtomicUsize::new(0));
184 let m = FairMutex::new(Foo(num_drops.clone()));
185 assert_eq!(num_drops.load(Ordering::SeqCst), 0);
186 {
187 let _inner = m.into_inner();
188 assert_eq!(num_drops.load(Ordering::SeqCst), 0);
189 }
190 assert_eq!(num_drops.load(Ordering::SeqCst), 1);
191 }
192
193 #[test]
test_get_mut()194 fn test_get_mut() {
195 let mut m = FairMutex::new(NonCopy(10));
196 *m.get_mut() = NonCopy(20);
197 assert_eq!(m.into_inner(), NonCopy(20));
198 }
199
200 #[test]
test_mutex_arc_nested()201 fn test_mutex_arc_nested() {
202 // Tests nested mutexes and access
203 // to underlying data.
204 let arc = Arc::new(FairMutex::new(1));
205 let arc2 = Arc::new(FairMutex::new(arc));
206 let (tx, rx) = channel();
207 let _t = thread::spawn(move || {
208 let lock = arc2.lock();
209 let lock2 = lock.lock();
210 assert_eq!(*lock2, 1);
211 tx.send(()).unwrap();
212 });
213 rx.recv().unwrap();
214 }
215
216 #[test]
test_mutex_arc_access_in_unwind()217 fn test_mutex_arc_access_in_unwind() {
218 let arc = Arc::new(FairMutex::new(1));
219 let arc2 = arc.clone();
220 let _ = thread::spawn(move || {
221 struct Unwinder {
222 i: Arc<FairMutex<i32>>,
223 }
224 impl Drop for Unwinder {
225 fn drop(&mut self) {
226 *self.i.lock() += 1;
227 }
228 }
229 let _u = Unwinder { i: arc2 };
230 panic!();
231 })
232 .join();
233 let lock = arc.lock();
234 assert_eq!(*lock, 2);
235 }
236
237 #[test]
test_mutex_unsized()238 fn test_mutex_unsized() {
239 let mutex: &FairMutex<[i32]> = &FairMutex::new([1, 2, 3]);
240 {
241 let b = &mut *mutex.lock();
242 b[0] = 4;
243 b[2] = 5;
244 }
245 let comp: &[i32] = &[4, 2, 5];
246 assert_eq!(&*mutex.lock(), comp);
247 }
248
249 #[test]
test_mutexguard_sync()250 fn test_mutexguard_sync() {
251 fn sync<T: Sync>(_: T) {}
252
253 let mutex = FairMutex::new(());
254 sync(mutex.lock());
255 }
256
257 #[test]
test_mutex_debug()258 fn test_mutex_debug() {
259 let mutex = FairMutex::new(vec![0u8, 10]);
260
261 assert_eq!(format!("{:?}", mutex), "Mutex { data: [0, 10] }");
262 let _lock = mutex.lock();
263 assert_eq!(format!("{:?}", mutex), "Mutex { data: <locked> }");
264 }
265
266 #[cfg(feature = "serde")]
267 #[test]
test_serde()268 fn test_serde() {
269 let contents: Vec<u8> = vec![0, 1, 2];
270 let mutex = FairMutex::new(contents.clone());
271
272 let serialized = serialize(&mutex).unwrap();
273 let deserialized: FairMutex<Vec<u8>> = deserialize(&serialized).unwrap();
274
275 assert_eq!(*(mutex.lock()), *(deserialized.lock()));
276 assert_eq!(contents, *(deserialized.lock()));
277 }
278 }
279