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
8use crate::raw_rwlock::RawRwLock;
9use lock_api;
10
11/// A reader-writer lock
12///
13/// This type of lock allows a number of readers or at most one writer at any
14/// point in time. The write portion of this lock typically allows modification
15/// of the underlying data (exclusive access) and the read portion of this lock
16/// typically allows for read-only access (shared access).
17///
18/// This lock uses a task-fair locking policy which avoids both reader and
19/// writer starvation. This means that readers trying to acquire the lock will
20/// block even if the lock is unlocked when there are writers waiting to acquire
21/// the lock. Because of this, attempts to recursively acquire a read lock
22/// within a single thread may result in a deadlock.
23///
24/// The type parameter `T` represents the data that this lock protects. It is
25/// required that `T` satisfies `Send` to be shared across threads and `Sync` to
26/// allow concurrent access through readers. The RAII guards returned from the
27/// locking methods implement `Deref` (and `DerefMut` for the `write` methods)
28/// to allow access to the contained of the lock.
29///
30/// # Fairness
31///
32/// A typical unfair lock can often end up in a situation where a single thread
33/// quickly acquires and releases the same lock in succession, which can starve
34/// other threads waiting to acquire the rwlock. While this improves throughput
35/// because it doesn't force a context switch when a thread tries to re-acquire
36/// a rwlock it has just released, this can starve other threads.
37///
38/// This rwlock uses [eventual fairness](https://trac.webkit.org/changeset/203350)
39/// to ensure that the lock will be fair on average without sacrificing
40/// throughput. This is done by forcing a fair unlock on average every 0.5ms,
41/// which will force the lock to go to the next thread waiting for the rwlock.
42///
43/// Additionally, any critical section longer than 1ms will always use a fair
44/// unlock, which has a negligible impact on throughput considering the length
45/// of the critical section.
46///
47/// You can also force a fair unlock by calling `RwLockReadGuard::unlock_fair`
48/// or `RwLockWriteGuard::unlock_fair` when unlocking a mutex instead of simply
49/// dropping the guard.
50///
51/// # Differences from the standard library `RwLock`
52///
53/// - Supports atomically downgrading a write lock into a read lock.
54/// - Task-fair locking policy instead of an unspecified platform default.
55/// - No poisoning, the lock is released normally on panic.
56/// - Only requires 1 word of space, whereas the standard library boxes the
57/// `RwLock` due to platform limitations.
58/// - Can be statically constructed.
59/// - Does not require any drop glue when dropped.
60/// - Inline fast path for the uncontended case.
61/// - Efficient handling of micro-contention using adaptive spinning.
62/// - Allows raw locking & unlocking without a guard.
63/// - Supports eventual fairness so that the rwlock is fair on average.
64/// - Optionally allows making the rwlock fair by calling
65/// `RwLockReadGuard::unlock_fair` and `RwLockWriteGuard::unlock_fair`.
66///
67/// # Examples
68///
69/// ```
70/// use parking_lot::RwLock;
71///
72/// let lock = RwLock::new(5);
73///
74/// // many reader locks can be held at once
75/// {
76/// let r1 = lock.read();
77/// let r2 = lock.read();
78/// assert_eq!(*r1, 5);
79/// assert_eq!(*r2, 5);
80/// } // read locks are dropped at this point
81///
82/// // only one write lock may be held, however
83/// {
84/// let mut w = lock.write();
85/// *w += 1;
86/// assert_eq!(*w, 6);
87/// } // write lock is dropped here
88/// ```
89pub type RwLock<T> = lock_api::RwLock<RawRwLock, T>;
90
91/// Creates a new instance of an `RwLock<T>` which is unlocked.
92///
93/// This allows creating a `RwLock<T>` in a constant context on stable Rust.
94pub const fn const_rwlock<T>(val: T) -> RwLock<T> {
95 RwLock::const_new(<RawRwLock as lock_api::RawRwLock>::INIT, val)
96}
97
98/// RAII structure used to release the shared read access of a lock when
99/// dropped.
100pub type RwLockReadGuard<'a, T> = lock_api::RwLockReadGuard<'a, RawRwLock, T>;
101
102/// RAII structure used to release the exclusive write access of a lock when
103/// dropped.
104pub type RwLockWriteGuard<'a, T> = lock_api::RwLockWriteGuard<'a, RawRwLock, T>;
105
106/// An RAII read lock guard returned by `RwLockReadGuard::map`, which can point to a
107/// subfield of the protected data.
108///
109/// The main difference between `MappedRwLockReadGuard` and `RwLockReadGuard` is that the
110/// former doesn't support temporarily unlocking and re-locking, since that
111/// could introduce soundness issues if the locked object is modified by another
112/// thread.
113pub type MappedRwLockReadGuard<'a, T> = lock_api::MappedRwLockReadGuard<'a, RawRwLock, T>;
114
115/// An RAII write lock guard returned by `RwLockWriteGuard::map`, which can point to a
116/// subfield of the protected data.
117///
118/// The main difference between `MappedRwLockWriteGuard` and `RwLockWriteGuard` is that the
119/// former doesn't support temporarily unlocking and re-locking, since that
120/// could introduce soundness issues if the locked object is modified by another
121/// thread.
122pub type MappedRwLockWriteGuard<'a, T> = lock_api::MappedRwLockWriteGuard<'a, RawRwLock, T>;
123
124/// RAII structure used to release the upgradable read access of a lock when
125/// dropped.
126pub type RwLockUpgradableReadGuard<'a, T> = lock_api::RwLockUpgradableReadGuard<'a, RawRwLock, T>;
127
128#[cfg(test)]
129mod tests {
130 use crate::{RwLock, RwLockUpgradableReadGuard, RwLockWriteGuard};
131 use rand::Rng;
132 use std::sync::atomic::{AtomicUsize, Ordering};
133 use std::sync::mpsc::channel;
134 use std::sync::Arc;
135 use std::thread;
136 use std::time::Duration;
137
138 #[cfg(feature = "serde")]
139 use bincode::{deserialize, serialize};
140
141 #[derive(Eq, PartialEq, Debug)]
142 struct NonCopy(i32);
143
144 #[test]
145 fn smoke() {
146 let l = RwLock::new(());
147 drop(l.read());
148 drop(l.write());
149 drop(l.upgradable_read());
150 drop((l.read(), l.read()));
151 drop((l.read(), l.upgradable_read()));
152 drop(l.write());
153 }
154
155 #[test]
156 fn frob() {
157 const N: u32 = 10;
158 const M: u32 = 1000;
159
160 let r = Arc::new(RwLock::new(()));
161
162 let (tx, rx) = channel::<()>();
163 for _ in 0..N {
164 let tx = tx.clone();
165 let r = r.clone();
166 thread::spawn(move || {
167 let mut rng = rand::thread_rng();
168 for _ in 0..M {
169 if rng.gen_bool(1.0 / N as f64) {
170 drop(r.write());
171 } else {
172 drop(r.read());
173 }
174 }
175 drop(tx);
176 });
177 }
178 drop(tx);
179 let _ = rx.recv();
180 }
181
182 #[test]
183 fn test_rw_arc_no_poison_wr() {
184 let arc = Arc::new(RwLock::new(1));
185 let arc2 = arc.clone();
186 let _: Result<(), _> = thread::spawn(move || {
187 let _lock = arc2.write();
188 panic!();
189 })
190 .join();
191 let lock = arc.read();
192 assert_eq!(*lock, 1);
193 }
194
195 #[test]
196 fn test_rw_arc_no_poison_ww() {
197 let arc = Arc::new(RwLock::new(1));
198 let arc2 = arc.clone();
199 let _: Result<(), _> = thread::spawn(move || {
200 let _lock = arc2.write();
201 panic!();
202 })
203 .join();
204 let lock = arc.write();
205 assert_eq!(*lock, 1);
206 }
207
208 #[test]
209 fn test_rw_arc_no_poison_rr() {
210 let arc = Arc::new(RwLock::new(1));
211 let arc2 = arc.clone();
212 let _: Result<(), _> = thread::spawn(move || {
213 let _lock = arc2.read();
214 panic!();
215 })
216 .join();
217 let lock = arc.read();
218 assert_eq!(*lock, 1);
219 }
220
221 #[test]
222 fn test_rw_arc_no_poison_rw() {
223 let arc = Arc::new(RwLock::new(1));
224 let arc2 = arc.clone();
225 let _: Result<(), _> = thread::spawn(move || {
226 let _lock = arc2.read();
227 panic!()
228 })
229 .join();
230 let lock = arc.write();
231 assert_eq!(*lock, 1);
232 }
233
234 #[test]
235 fn test_ruw_arc() {
236 let arc = Arc::new(RwLock::new(0));
237 let arc2 = arc.clone();
238 let (tx, rx) = channel();
239
240 thread::spawn(move || {
241 for _ in 0..10 {
242 let mut lock = arc2.write();
243 let tmp = *lock;
244 *lock = -1;
245 thread::yield_now();
246 *lock = tmp + 1;
247 }
248 tx.send(()).unwrap();
249 });
250
251 let mut children = Vec::new();
252
253 // Upgradable readers try to catch the writer in the act and also
254 // try to touch the value
255 for _ in 0..5 {
256 let arc3 = arc.clone();
257 children.push(thread::spawn(move || {
258 let lock = arc3.upgradable_read();
259 let tmp = *lock;
260 assert!(tmp >= 0);
261 thread::yield_now();
262 let mut lock = RwLockUpgradableReadGuard::upgrade(lock);
263 assert_eq!(tmp, *lock);
264 *lock = -1;
265 thread::yield_now();
266 *lock = tmp + 1;
267 }));
268 }
269
270 // Readers try to catch the writers in the act
271 for _ in 0..5 {
272 let arc4 = arc.clone();
273 children.push(thread::spawn(move || {
274 let lock = arc4.read();
275 assert!(*lock >= 0);
276 }));
277 }
278
279 // Wait for children to pass their asserts
280 for r in children {
281 assert!(r.join().is_ok());
282 }
283
284 // Wait for writer to finish
285 rx.recv().unwrap();
286 let lock = arc.read();
287 assert_eq!(*lock, 15);
288 }
289
290 #[test]
291 fn test_rw_arc() {
292 let arc = Arc::new(RwLock::new(0));
293 let arc2 = arc.clone();
294 let (tx, rx) = channel();
295
296 thread::spawn(move || {
297 let mut lock = arc2.write();
298 for _ in 0..10 {
299 let tmp = *lock;
300 *lock = -1;
301 thread::yield_now();
302 *lock = tmp + 1;
303 }
304 tx.send(()).unwrap();
305 });
306
307 // Readers try to catch the writer in the act
308 let mut children = Vec::new();
309 for _ in 0..5 {
310 let arc3 = arc.clone();
311 children.push(thread::spawn(move || {
312 let lock = arc3.read();
313 assert!(*lock >= 0);
314 }));
315 }
316
317 // Wait for children to pass their asserts
318 for r in children {
319 assert!(r.join().is_ok());
320 }
321
322 // Wait for writer to finish
323 rx.recv().unwrap();
324 let lock = arc.read();
325 assert_eq!(*lock, 10);
326 }
327
328 #[test]
329 fn test_rw_arc_access_in_unwind() {
330 let arc = Arc::new(RwLock::new(1));
331 let arc2 = arc.clone();
332 let _ = thread::spawn(move || {
333 struct Unwinder {
334 i: Arc<RwLock<isize>>,
335 }
336 impl Drop for Unwinder {
337 fn drop(&mut self) {
338 let mut lock = self.i.write();
339 *lock += 1;
340 }
341 }
342 let _u = Unwinder { i: arc2 };
343 panic!();
344 })
345 .join();
346 let lock = arc.read();
347 assert_eq!(*lock, 2);
348 }
349
350 #[test]
351 fn test_rwlock_unsized() {
352 let rw: &RwLock<[i32]> = &RwLock::new([1, 2, 3]);
353 {
354 let b = &mut *rw.write();
355 b[0] = 4;
356 b[2] = 5;
357 }
358 let comp: &[i32] = &[4, 2, 5];
359 assert_eq!(&*rw.read(), comp);
360 }
361
362 #[test]
363 fn test_rwlock_try_read() {
364 let lock = RwLock::new(0isize);
365 {
366 let read_guard = lock.read();
367
368 let read_result = lock.try_read();
369 assert!(
370 read_result.is_some(),
371 "try_read should succeed while read_guard is in scope"
372 );
373
374 drop(read_guard);
375 }
376 {
377 let upgrade_guard = lock.upgradable_read();
378
379 let read_result = lock.try_read();
380 assert!(
381 read_result.is_some(),
382 "try_read should succeed while upgrade_guard is in scope"
383 );
384
385 drop(upgrade_guard);
386 }
387 {
388 let write_guard = lock.write();
389
390 let read_result = lock.try_read();
391 assert!(
392 read_result.is_none(),
393 "try_read should fail while write_guard is in scope"
394 );
395
396 drop(write_guard);
397 }
398 }
399
400 #[test]
401 fn test_rwlock_try_write() {
402 let lock = RwLock::new(0isize);
403 {
404 let read_guard = lock.read();
405
406 let write_result = lock.try_write();
407 assert!(
408 write_result.is_none(),
409 "try_write should fail while read_guard is in scope"
410 );
411 assert!(lock.is_locked());
412 assert!(!lock.is_locked_exclusive());
413
414 drop(read_guard);
415 }
416 {
417 let upgrade_guard = lock.upgradable_read();
418
419 let write_result = lock.try_write();
420 assert!(
421 write_result.is_none(),
422 "try_write should fail while upgrade_guard is in scope"
423 );
424 assert!(lock.is_locked());
425 assert!(!lock.is_locked_exclusive());
426
427 drop(upgrade_guard);
428 }
429 {
430 let write_guard = lock.write();
431
432 let write_result = lock.try_write();
433 assert!(
434 write_result.is_none(),
435 "try_write should fail while write_guard is in scope"
436 );
437 assert!(lock.is_locked());
438 assert!(lock.is_locked_exclusive());
439
440 drop(write_guard);
441 }
442 }
443
444 #[test]
445 fn test_rwlock_try_upgrade() {
446 let lock = RwLock::new(0isize);
447 {
448 let read_guard = lock.read();
449
450 let upgrade_result = lock.try_upgradable_read();
451 assert!(
452 upgrade_result.is_some(),
453 "try_upgradable_read should succeed while read_guard is in scope"
454 );
455
456 drop(read_guard);
457 }
458 {
459 let upgrade_guard = lock.upgradable_read();
460
461 let upgrade_result = lock.try_upgradable_read();
462 assert!(
463 upgrade_result.is_none(),
464 "try_upgradable_read should fail while upgrade_guard is in scope"
465 );
466
467 drop(upgrade_guard);
468 }
469 {
470 let write_guard = lock.write();
471
472 let upgrade_result = lock.try_upgradable_read();
473 assert!(
474 upgrade_result.is_none(),
475 "try_upgradable should fail while write_guard is in scope"
476 );
477
478 drop(write_guard);
479 }
480 }
481
482 #[test]
483 fn test_into_inner() {
484 let m = RwLock::new(NonCopy(10));
485 assert_eq!(m.into_inner(), NonCopy(10));
486 }
487
488 #[test]
489 fn test_into_inner_drop() {
490 struct Foo(Arc<AtomicUsize>);
491 impl Drop for Foo {
492 fn drop(&mut self) {
493 self.0.fetch_add(1, Ordering::SeqCst);
494 }
495 }
496 let num_drops = Arc::new(AtomicUsize::new(0));
497 let m = RwLock::new(Foo(num_drops.clone()));
498 assert_eq!(num_drops.load(Ordering::SeqCst), 0);
499 {
500 let _inner = m.into_inner();
501 assert_eq!(num_drops.load(Ordering::SeqCst), 0);
502 }
503 assert_eq!(num_drops.load(Ordering::SeqCst), 1);
504 }
505
506 #[test]
507 fn test_get_mut() {
508 let mut m = RwLock::new(NonCopy(10));
509 *m.get_mut() = NonCopy(20);
510 assert_eq!(m.into_inner(), NonCopy(20));
511 }
512
513 #[test]
514 fn test_rwlockguard_sync() {
515 fn sync<T: Sync>(_: T) {}
516
517 let rwlock = RwLock::new(());
518 sync(rwlock.read());
519 sync(rwlock.write());
520 }
521
522 #[test]
523 fn test_rwlock_downgrade() {
524 let x = Arc::new(RwLock::new(0));
525 let mut handles = Vec::new();
526 for _ in 0..8 {
527 let x = x.clone();
528 handles.push(thread::spawn(move || {
529 for _ in 0..100 {
530 let mut writer = x.write();
531 *writer += 1;
532 let cur_val = *writer;
533 let reader = RwLockWriteGuard::downgrade(writer);
534 assert_eq!(cur_val, *reader);
535 }
536 }));
537 }
538 for handle in handles {
539 handle.join().unwrap()
540 }
541 assert_eq!(*x.read(), 800);
542 }
543
544 #[test]
545 fn test_rwlock_recursive() {
546 let arc = Arc::new(RwLock::new(1));
547 let arc2 = arc.clone();
548 let lock1 = arc.read();
549 let t = thread::spawn(move || {
550 let _lock = arc2.write();
551 });
552
553 if cfg!(not(all(target_env = "sgx", target_vendor = "fortanix"))) {
554 thread::sleep(Duration::from_millis(100));
555 } else {
556 // FIXME: https://github.com/fortanix/rust-sgx/issues/31
557 for _ in 0..100 {
558 thread::yield_now();
559 }
560 }
561
562 // A normal read would block here since there is a pending writer
563 let lock2 = arc.read_recursive();
564
565 // Unblock the thread and join it.
566 drop(lock1);
567 drop(lock2);
568 t.join().unwrap();
569 }
570
571 #[test]
572 fn test_rwlock_debug() {
573 let x = RwLock::new(vec![0u8, 10]);
574
575 assert_eq!(format!("{:?}", x), "RwLock { data: [0, 10] }");
576 let _lock = x.write();
577 assert_eq!(format!("{:?}", x), "RwLock { data: <locked> }");
578 }
579
580 #[test]
581 fn test_clone() {
582 let rwlock = RwLock::new(Arc::new(1));
583 let a = rwlock.read_recursive();
584 let b = a.clone();
585 assert_eq!(Arc::strong_count(&b), 2);
586 }
587
588 #[cfg(feature = "serde")]
589 #[test]
590 fn test_serde() {
591 let contents: Vec<u8> = vec![0, 1, 2];
592 let mutex = RwLock::new(contents.clone());
593
594 let serialized = serialize(&mutex).unwrap();
595 let deserialized: RwLock<Vec<u8>> = deserialize(&serialized).unwrap();
596
597 assert_eq!(*(mutex.read()), *(deserialized.read()));
598 assert_eq!(contents, *(deserialized.read()));
599 }
600
601 #[test]
602 fn test_issue_203() {
603 struct Bar(RwLock<()>);
604
605 impl Drop for Bar {
606 fn drop(&mut self) {
607 let _n = self.0.write();
608 }
609 }
610
611 thread_local! {
612 static B: Bar = Bar(RwLock::new(()));
613 }
614
615 thread::spawn(|| {
616 B.with(|_| ());
617
618 let a = RwLock::new(());
619 let _a = a.read();
620 })
621 .join()
622 .unwrap();
623 }
624
625 #[test]
626 fn test_rw_write_is_locked() {
627 let lock = RwLock::new(0isize);
628 {
629 let _read_guard = lock.read();
630
631 assert!(lock.is_locked());
632 assert!(!lock.is_locked_exclusive());
633 }
634
635 {
636 let _write_guard = lock.write();
637
638 assert!(lock.is_locked());
639 assert!(lock.is_locked_exclusive());
640 }
641 }
642}
643