This library provides implementations of
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.
The primitives provided by this library have several advantages over those in the Rust standard library:
Onceonly require 1 byte of storage space, and
RwLockonly requires 1 word of storage space. On the other hand the standard library primitives require a dynamically allocated
Boxto hold OS-specific synchronization primitives. The small size of
Mutexin 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
staticglobal variables. The standard library primitives require dynamic initialization and thus need to be lazily initialized with
- 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.
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 [
(https://webkit.org/blog/6161/locking-in-webkit/) 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 3 functions:
unsafe fn park(key: usize, validate: &mut FnMut() -> bool, before_sleep: &mut FnMut(), timeout: Option<Instant>) -> bool
This function performs the following steps:
- Lock the queue associated with
validate, if it returns
false, unlock the queue and return.
- Add the current thread to the queue.
- Unlock the queue.
- Sleep until we are unparked or
trueif we were unparked by another thread,
unsafe fn unpark_one(key: usize, callback: &mut FnMut(UnparkResult)) -> UnparkResult
This function will unpark a single thread from the queue associated with
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
unsafe fn unpark_all(key: usize) -> usize
This function will unpark all threads in the queue associated with
returns the number of threads that were unparked.
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.
This crate currently requires a nightly Rust compiler.
Add this to your
[dependencies] parking_lot = "0.1"
and this to your crate root:
extern crate parking_lot;
Licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.