1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
// Copyright 2016 Amanieu d'Antras // // Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or // http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or // http://opensource.org/licenses/MIT>, at your option. This file may not be // copied, modified, or distributed except according to those terms. //! This library provides the `SeqLock` type, which is a form of reader-writer //! lock that is heavily optimized for readers. //! //! In certain situations, `SeqLock` can be two orders of magnitude faster than //! the standard library `RwLock` type. Another advantage is that readers cannot //! starve writers: a writer will never block even if there are readers //! currently accessing the `SeqLock`. //! //! The only downside of `SeqLock` is that it only works on types that are //! `Copy`. This means that it is unsuitable for types that contains pointers //! to owned data. //! //! You should instead use `RwLock` from the //! [parking_lot](https://github.com/Amanieu/parking_lot) crate if you need //! a reader-writer lock for types that are not `Copy`. //! //! # Implementation //! //! The implementation is based on the [Linux seqlock type](http://lxr.free-electrons.com/source/include/linux/seqlock.h). //! Each `SeqLock` contains a sequence counter which tracks modifications to the //! locked data. The basic idea is that a reader will perform the following //! operations: //! //! 1. Read the sequence counter. //! 2. Read the data in the lock. //! 3. Read the sequence counter again. //! 4. If the two sequence counter values differ, loop back and try again. //! 5. Otherwise return the data that was read in step 2. //! //! Similarly, a writer will increment the sequence counter before and after //! writing to the data in the lock. Once a reader sees that the sequence //! counter has not changed while it was reading the data, it can safely return //! that data to the caller since it is known to be in a consistent state. //! //! # Examples //! //! ``` //! use seqlock::SeqLock; //! //! let lock = SeqLock::new(5); //! //! { //! // Writing to the data involves a lock //! let mut w = lock.lock_write(); //! *w += 1; //! assert_eq!(*w, 6); //! } //! //! { //! // Reading the data is a very fast operation //! let r = lock.read(); //! assert_eq!(r, 6); //! } //! ``` #![warn(missing_docs)] #![cfg_attr(feature = "nightly", feature(const_fn))] extern crate parking_lot; use std::sync::atomic::{AtomicUsize, Ordering, fence}; use std::cell::UnsafeCell; use std::ptr; use std::fmt; use std::ops::{Deref, DerefMut}; use std::thread; use parking_lot::{Mutex, MutexGuard}; /// A sequential lock pub struct SeqLock<T: Copy> { seq: AtomicUsize, data: UnsafeCell<T>, mutex: Mutex<()>, } unsafe impl<T: Copy + Send> Send for SeqLock<T> {} unsafe impl<T: Copy + Send> Sync for SeqLock<T> {} /// RAII structure used to release the exclusive write access of a `SeqLock` /// when dropped. pub struct SeqLockGuard<'a, T: Copy + 'a> { _guard: MutexGuard<'a, ()>, seqlock: &'a SeqLock<T>, seq: usize, } impl<T: Copy> SeqLock<T> { /// Creates a new SeqLock with the given initial value. #[cfg(feature = "nightly")] #[inline] pub const fn new(val: T) -> SeqLock<T> { SeqLock { seq: AtomicUsize::new(0), data: UnsafeCell::new(val), mutex: Mutex::new(()), } } /// Creates a new SeqLock with the given initial value. #[cfg(not(feature = "nightly"))] #[inline] pub fn new(val: T) -> SeqLock<T> { SeqLock { seq: AtomicUsize::new(0), data: UnsafeCell::new(val), mutex: Mutex::new(()), } } /// Reads the value protected by the `SeqLock`. /// /// This operation is extremely fast since it only reads the `SeqLock`, /// which allows multiple readers to read the value without interfering with /// each other. /// /// If a writer is currently modifying the contained value then the calling /// thread will block until the writer thread releases the lock. /// /// Attempting to read from a `SeqLock` while already holding a write lock /// in the current thread will result in a deadlock. #[inline] pub fn read(&self) -> T { loop { // Load the first sequence number. The acquire ordering ensures that // this is done before reading the data. let seq1 = self.seq.load(Ordering::Acquire); // If the sequence number is odd then it means a writer is currently // modifying the value. if seq1 & 1 != 0 { // Yield to give the writer a chance to finish. Writing is // expected to be relatively rare anyways so this isn't too // performance critical. thread::yield_now(); continue; } // We need to use a volatile read here because the data may be // concurrently modified by a writer. let result = unsafe { ptr::read_volatile(self.data.get()) }; // Make sure the seq2 read occurs after reading the data. What we // ideally want is a load(Release), but the Release ordering is not // available on loads. fence(Ordering::Acquire); // If the sequence number is the same then the data wasn't modified // while we were reading it, and can be returned. let seq2 = self.seq.load(Ordering::Relaxed); if seq1 == seq2 { return result; } } } #[inline] fn begin_write(&self) -> usize { // Increment the sequence number. At this point, the number will be odd, // which will force readers to spin until we finish writing. let seq = self.seq.load(Ordering::Relaxed).wrapping_add(1); self.seq.store(seq, Ordering::Relaxed); // Make sure any writes to the data happen after incrementing the // sequence number. What we ideally want is a store(Acquire), but the // Acquire ordering is not available on stores. fence(Ordering::Release); seq } #[inline] fn end_write(&self, seq: usize) { // Increment the sequence number again, which will make it even and // allow readers to access the data. The release ordering ensures that // all writes to the data are done before writing the sequence number. self.seq.store(seq.wrapping_add(1), Ordering::Release); } #[inline] fn lock_guard<'a>(&'a self, guard: MutexGuard<'a, ()>,) -> SeqLockGuard<'a, T> { let seq = self.begin_write(); SeqLockGuard { _guard: guard, seqlock: self, seq: seq, } } /// Locks this `SeqLock` with exclusive write access, blocking the current /// thread until it can be acquired. /// /// This function does not block while waiting for concurrent readers. /// Instead, readers will detect the concurrent write and retry the read. /// /// Returns an RAII guard which will drop the write access of this `SeqLock` /// when dropped. #[inline] pub fn lock_write(&self) -> SeqLockGuard<T> { self.lock_guard(self.mutex.lock()) } /// Attempts to lock this `SeqLock` with exclusive write access. /// /// If the lock could not be acquired at this time, then `None` is returned. /// Otherwise, an RAII guard is returned which will release the lock when /// it is dropped. /// /// This function does not block. #[inline] pub fn try_lock_write(&self) -> Option<SeqLockGuard<T>> { self.mutex.try_lock().map(|g| self.lock_guard(g)) } /// Consumes this `SeqLock`, returning the underlying data. #[inline] pub fn into_inner(self) -> T { unsafe { self.data.into_inner() } } /// Returns a mutable reference to the underlying data. /// /// Since this call borrows the `SeqLock` mutably, no actual locking needs /// to take place---the mutable borrow statically guarantees no locks exist. #[inline] pub fn get_mut(&mut self) -> &mut T { unsafe { &mut *self.data.get() } } } impl<T: Copy + Default> Default for SeqLock<T> { #[inline] fn default() -> SeqLock<T> { SeqLock::new(Default::default()) } } impl<T: Copy + fmt::Debug> fmt::Debug for SeqLock<T> { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "SeqLock {{ data: {:?} }}", &self.read()) } } impl<'a, T: Copy + 'a> Deref for SeqLockGuard<'a, T> { type Target = T; #[inline] fn deref(&self) -> &T { unsafe { &*self.seqlock.data.get() } } } impl<'a, T: Copy + 'a> DerefMut for SeqLockGuard<'a, T> { #[inline] fn deref_mut(&mut self) -> &mut T { unsafe { &mut *self.seqlock.data.get() } } } impl<'a, T: Copy + 'a> Drop for SeqLockGuard<'a, T> { #[inline] fn drop(&mut self) { self.seqlock.end_write(self.seq); } }