• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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_rwlock::RawRwLock;
9 use 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 (requires the `const_fn` nightly feature).
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 /// ```
89 pub 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.
const_rwlock<T>(val: T) -> RwLock<T>94 pub 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.
100 pub 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.
104 pub 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.
113 pub 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.
122 pub 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.
126 pub type RwLockUpgradableReadGuard<'a, T> = lock_api::RwLockUpgradableReadGuard<'a, RawRwLock, T>;
127 
128 #[cfg(test)]
129 mod 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]
smoke()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]
frob()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]
test_rw_arc_no_poison_wr()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]
test_rw_arc_no_poison_ww()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]
test_rw_arc_no_poison_rr()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]
test_rw_arc_no_poison_rw()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]
test_ruw_arc()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]
test_rw_arc()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]
test_rw_arc_access_in_unwind()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]
test_rwlock_unsized()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]
test_rwlock_try_read()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]
test_rwlock_try_write()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 
412             drop(read_guard);
413         }
414         {
415             let upgrade_guard = lock.upgradable_read();
416 
417             let write_result = lock.try_write();
418             assert!(
419                 write_result.is_none(),
420                 "try_write should fail while upgrade_guard is in scope"
421             );
422 
423             drop(upgrade_guard);
424         }
425         {
426             let write_guard = lock.write();
427 
428             let write_result = lock.try_write();
429             assert!(
430                 write_result.is_none(),
431                 "try_write should fail while write_guard is in scope"
432             );
433 
434             drop(write_guard);
435         }
436     }
437 
438     #[test]
test_rwlock_try_upgrade()439     fn test_rwlock_try_upgrade() {
440         let lock = RwLock::new(0isize);
441         {
442             let read_guard = lock.read();
443 
444             let upgrade_result = lock.try_upgradable_read();
445             assert!(
446                 upgrade_result.is_some(),
447                 "try_upgradable_read should succeed while read_guard is in scope"
448             );
449 
450             drop(read_guard);
451         }
452         {
453             let upgrade_guard = lock.upgradable_read();
454 
455             let upgrade_result = lock.try_upgradable_read();
456             assert!(
457                 upgrade_result.is_none(),
458                 "try_upgradable_read should fail while upgrade_guard is in scope"
459             );
460 
461             drop(upgrade_guard);
462         }
463         {
464             let write_guard = lock.write();
465 
466             let upgrade_result = lock.try_upgradable_read();
467             assert!(
468                 upgrade_result.is_none(),
469                 "try_upgradable should fail while write_guard is in scope"
470             );
471 
472             drop(write_guard);
473         }
474     }
475 
476     #[test]
test_into_inner()477     fn test_into_inner() {
478         let m = RwLock::new(NonCopy(10));
479         assert_eq!(m.into_inner(), NonCopy(10));
480     }
481 
482     #[test]
test_into_inner_drop()483     fn test_into_inner_drop() {
484         struct Foo(Arc<AtomicUsize>);
485         impl Drop for Foo {
486             fn drop(&mut self) {
487                 self.0.fetch_add(1, Ordering::SeqCst);
488             }
489         }
490         let num_drops = Arc::new(AtomicUsize::new(0));
491         let m = RwLock::new(Foo(num_drops.clone()));
492         assert_eq!(num_drops.load(Ordering::SeqCst), 0);
493         {
494             let _inner = m.into_inner();
495             assert_eq!(num_drops.load(Ordering::SeqCst), 0);
496         }
497         assert_eq!(num_drops.load(Ordering::SeqCst), 1);
498     }
499 
500     #[test]
test_get_mut()501     fn test_get_mut() {
502         let mut m = RwLock::new(NonCopy(10));
503         *m.get_mut() = NonCopy(20);
504         assert_eq!(m.into_inner(), NonCopy(20));
505     }
506 
507     #[test]
test_rwlockguard_sync()508     fn test_rwlockguard_sync() {
509         fn sync<T: Sync>(_: T) {}
510 
511         let rwlock = RwLock::new(());
512         sync(rwlock.read());
513         sync(rwlock.write());
514     }
515 
516     #[test]
test_rwlock_downgrade()517     fn test_rwlock_downgrade() {
518         let x = Arc::new(RwLock::new(0));
519         let mut handles = Vec::new();
520         for _ in 0..8 {
521             let x = x.clone();
522             handles.push(thread::spawn(move || {
523                 for _ in 0..100 {
524                     let mut writer = x.write();
525                     *writer += 1;
526                     let cur_val = *writer;
527                     let reader = RwLockWriteGuard::downgrade(writer);
528                     assert_eq!(cur_val, *reader);
529                 }
530             }));
531         }
532         for handle in handles {
533             handle.join().unwrap()
534         }
535         assert_eq!(*x.read(), 800);
536     }
537 
538     #[test]
test_rwlock_recursive()539     fn test_rwlock_recursive() {
540         let arc = Arc::new(RwLock::new(1));
541         let arc2 = arc.clone();
542         let lock1 = arc.read();
543         let t = thread::spawn(move || {
544             let _lock = arc2.write();
545         });
546 
547         if cfg!(not(all(target_env = "sgx", target_vendor = "fortanix"))) {
548             thread::sleep(Duration::from_millis(100));
549         } else {
550             // FIXME: https://github.com/fortanix/rust-sgx/issues/31
551             for _ in 0..100 {
552                 thread::yield_now();
553             }
554         }
555 
556         // A normal read would block here since there is a pending writer
557         let lock2 = arc.read_recursive();
558 
559         // Unblock the thread and join it.
560         drop(lock1);
561         drop(lock2);
562         t.join().unwrap();
563     }
564 
565     #[test]
test_rwlock_debug()566     fn test_rwlock_debug() {
567         let x = RwLock::new(vec![0u8, 10]);
568 
569         assert_eq!(format!("{:?}", x), "RwLock { data: [0, 10] }");
570         let _lock = x.write();
571         assert_eq!(format!("{:?}", x), "RwLock { data: <locked> }");
572     }
573 
574     #[test]
test_clone()575     fn test_clone() {
576         let rwlock = RwLock::new(Arc::new(1));
577         let a = rwlock.read_recursive();
578         let b = a.clone();
579         assert_eq!(Arc::strong_count(&b), 2);
580     }
581 
582     #[cfg(feature = "serde")]
583     #[test]
test_serde()584     fn test_serde() {
585         let contents: Vec<u8> = vec![0, 1, 2];
586         let mutex = RwLock::new(contents.clone());
587 
588         let serialized = serialize(&mutex).unwrap();
589         let deserialized: RwLock<Vec<u8>> = deserialize(&serialized).unwrap();
590 
591         assert_eq!(*(mutex.read()), *(deserialized.read()));
592         assert_eq!(contents, *(deserialized.read()));
593     }
594 
595     #[test]
test_issue_203()596     fn test_issue_203() {
597         struct Bar(RwLock<()>);
598 
599         impl Drop for Bar {
600             fn drop(&mut self) {
601                 let _n = self.0.write();
602             }
603         }
604 
605         thread_local! {
606             static B: Bar = Bar(RwLock::new(()));
607         }
608 
609         thread::spawn(|| {
610             B.with(|_| ());
611 
612             let a = RwLock::new(());
613             let _a = a.read();
614         })
615         .join()
616         .unwrap();
617     }
618 }
619