Crate parking_lot [−] [src]
This library provides implementations of Mutex
, RwLock
, Condvar
and
Once
that are smaller, faster and more flexible than those in the Rust
standard library. It also exposes a low-level API for creating your own
efficient synchronization primitives.
When tested on x86_64 Linux, parking_lot::Mutex
was found to be 1.5x
faster than std::sync::Mutex
when uncontended, and up to 5x faster when
contended from multiple threads. The numbers for RwLock
vary depending on
the number of reader and writer threads, but are almost always faster than
the standard library RwLock
, and even up to 50x faster in some cases.
Features
The primitives provided by this library have several advantages over those in the Rust standard library:
Mutex
andOnce
only require 1 byte of storage space, whileCondvar
andRwLock
only requires 1 word of storage space. On the other hand the standard library primitives require a dynamically allocatedBox
to hold OS-specific synchronization primitives. The small size ofMutex
in particular encourages the use of fine-grained locks to increase parallelism.- Since they consist of just a single atomic variable, have constant
initializers and don't need destructors, these primitives can be used as
static
global variables. The standard library primitives require dynamic initialization and thus need to be lazily initialized withlazy_static!
. - Uncontended lock acquisition and release is done through fast inline paths which only require a single atomic operation.
- Microcontention (a contended lock with a short critical section) is efficiently handled by spinning a few times while trying to acquire a lock.
- The locks are adaptive and will suspend a thread after a few failed spin attempts. This makes the locks suitable for both long and short critical sections.
Condvar
,RwLock
andOnce
work on Windows XP, unlike the standard library versions of those types.RwLock
takes advantage of hardware lock elision on processors that support it, which can lead to huge performance wins with many readers.MutexGuard
(and theRwLock
equivalents) isSend
, which means it can be unlocked by a different thread than the one that locked it.RwLock
will prefer writers, whereas the standard library version makes no guarantees as to whether readers or writers are given priority.Condvar
is guaranteed not to produce spurious wakeups. A thread will only be woken up if it timed out or it was woken up by a notification.Condvar::notify_all
will only wake up a single thread and requeue the rest to wait on the associatedMutex
. This avoids a thundering herd problem where all threads try to acquire the lock at the same time.RwLock
supports atomically downgrading a write lock into a read lock.Mutex<()>
andRwLock<()>
allow raw locking and unlocking without a RAII guard object.
The parking lot
To keep these primitives small, all thread queuing and suspending
functionality is offloaded to the parking lot. The idea behind this is
based on the Webkit WTF::ParkingLot
class, which essentially
consists of a hash table mapping of lock addresses to queues of parked
(sleeping) threads. The Webkit parking lot was itself inspired by Linux
futexes, but it is more
powerful since it allows invoking callbacks while holding a queue lock.
Parking refers to suspending the thread while simultaneously enqueuing it on a queue keyed by some address. Unparking refers to dequeuing a thread from a queue keyed by some address and resuming it. The parking lot API consists of just 4 functions:
unsafe fn park(key: usize, validate: &mut FnMut() -> bool, before_sleep: &mut FnMut(), timed_out: &mut FnMut(usize, UnparkResult), timeout: Option<Instant>) -> bool
This function performs the following steps:
- Lock the queue associated with
key
. - Call
validate
, if it returnsfalse
, unlock the queue and return. - Add the current thread to the queue.
- Unlock the queue.
- Call
before_sleep
. - Sleep until we are unparked or
timeout
is reached. - If the park timed out, call
timed_out
. - Return
true
if we were unparked by another thread,false
otherwise.
unsafe fn unpark_one(key: usize, callback: &mut FnMut(UnparkResult)) -> UnparkResult
This function will unpark a single thread from the queue associated with
key
. The callback
function is invoked while holding the queue lock but
before the thread is unparked. The UnparkResult
indicates whether the
queue was empty and, if not, whether there are still threads remaining in
the queue.
unsafe fn unpark_all(key: usize) -> usize
This function will unpark all threads in the queue associated with key
. It
returns the number of threads that were unparked.
unsafe fn unpark_requeue(key_from: usize, key_to: usize, validate: &mut FnMut() -> RequeueOp, callback: &mut FnMut(RequeueOp, usize)) -> usize
This function will remove all threads from the queue associated with
key_from
, optionally unpark the first one and move the rest to the queue
associated with key_to
. The validate
function is invoked while holding
both queue locks and can choose whether to abort the operation and whether
to unpark one thread from the queue. The callback
function is then called
with the result of validate
and the number of threads that were in the
original queue.
Building custom synchronization primitives
Building custom synchronization primitives is very simple since
parking_lot
takes care of all the hard parts for you. The most commmon
case for a custom primitive would be to integrate a Mutex
inside another
data type. Since a mutex only requires 2 bits, it can share space with other
data. For example, one could create an ArcMutex
type that combines the
atomic reference count and the two mutex bits in the same atomic word.
Structs
Condvar |
A Condition Variable |
Mutex |
A mutual exclusion primitive useful for protecting shared data |
MutexGuard |
An RAII implementation of a "scoped lock" of a mutex. When this structure is dropped (falls out of scope), the lock will be unlocked. |
Once |
A synchronization primitive which can be used to run a one-time initialization. Useful for one-time initialization for globals, FFI or related functionality. |
OnceState |
State yielded to the |
RwLock |
A reader-writer lock |
RwLockReadGuard |
RAII structure used to release the shared read access of a lock when dropped. |
RwLockWriteGuard |
RAII structure used to release the exclusive write access of a lock when dropped. |
WaitTimeoutResult |
A type indicating whether a timed wait on a condition variable returned due to a time out or not. |
Enums
RequeueOp |
Operation that |
UnparkResult |
Result of an |
Constants
ONCE_INIT |
Initialization value for static |
Functions
park |
Parks the current thread in the queue associated with the given key. |
unpark_all |
Unparks all threads in the queue associated with the given key. |
unpark_one |
Unparks one thread from the queue associated with the given key. |
unpark_requeue |
Removes all threads from the queue associated with |