vendor/parking_lot/README.md

   1 parking_lot
   2 ============
   3
   4 ![Rust](https://github.com/Amanieu/parking_lot/workflows/Rust/badge.svg)
   5 [![Crates.io](https://img.shields.io/crates/v/parking_lot.svg)](https://crates.io/crates/parking_lot)
   6
   7 [Documentation (synchronization primitives)](https://docs.rs/parking_lot/)
   8
   9 [Documentation (core parking lot API)](https://docs.rs/parking_lot_core/)
  10
  11 [Documentation (type-safe lock API)](https://docs.rs/lock_api/)
  12
  13 This library provides implementations of `Mutex`, `RwLock`, `Condvar` and
  14 `Once` that are smaller, faster and more flexible than those in the Rust
  15 standard library, as well as a `ReentrantMutex` type which supports recursive
  16 locking. It also exposes a low-level API for creating your own efficient
  17 synchronization primitives.
  18
  19 When tested on x86_64 Linux, `parking_lot::Mutex` was found to be 1.5x
  20 faster than `std::sync::Mutex` when uncontended, and up to 5x faster when
  21 contended from multiple threads. The numbers for `RwLock` vary depending on
  22 the number of reader and writer threads, but are almost always faster than
  23 the standard library `RwLock`, and even up to 50x faster in some cases.
  24
  25 ## Features
  26
  27 The primitives provided by this library have several advantages over those
  28 in the Rust standard library:
  29
  30 1. `Mutex` and `Once` only require 1 byte of storage space, while `Condvar`
  31    and `RwLock` only require 1 word of storage space. On the other hand the
  32    standard library primitives require a dynamically allocated `Box` to hold
  33    OS-specific synchronization primitives. The small size of `Mutex` in
  34    particular encourages the use of fine-grained locks to increase
  35    parallelism.
  36 2. Since they consist of just a single atomic variable, have constant
  37    initializers and don't need destructors, these primitives can be used as
  38    `static` global variables. The standard library primitives require
  39    dynamic initialization and thus need to be lazily initialized with
  40    `lazy_static!`.
  41 3. Uncontended lock acquisition and release is done through fast inline
  42    paths which only require a single atomic operation.
  43 4. Microcontention (a contended lock with a short critical section) is
  44    efficiently handled by spinning a few times while trying to acquire a
  45    lock.
  46 5. The locks are adaptive and will suspend a thread after a few failed spin
  47    attempts. This makes the locks suitable for both long and short critical
  48    sections.
  49 6. `Condvar`, `RwLock` and `Once` work on Windows XP, unlike the standard
  50    library versions of those types.
  51 7. `RwLock` takes advantage of hardware lock elision on processors that
  52    support it, which can lead to huge performance wins with many readers.
  53    This must be enabled with the `hardware-lock-elision` feature.
  54 8. `RwLock` uses a task-fair locking policy, which avoids reader and writer
  55    starvation, whereas the standard library version makes no guarantees.
  56 9. `Condvar` is guaranteed not to produce spurious wakeups. A thread will
  57     only be woken up if it timed out or it was woken up by a notification.
  58 10. `Condvar::notify_all` will only wake up a single thread and requeue the
  59     rest to wait on the associated `Mutex`. This avoids a thundering herd
  60     problem where all threads try to acquire the lock at the same time.
  61 11. `RwLock` supports atomically downgrading a write lock into a read lock.
  62 12. `Mutex` and `RwLock` allow raw unlocking without a RAII guard object.
  63 13. `Mutex<()>` and `RwLock<()>` allow raw locking without a RAII guard
  64     object.
  65 14. `Mutex` and `RwLock` support [eventual fairness](https://trac.webkit.org/changeset/203350)
  66     which allows them to be fair on average without sacrificing performance.
  67 15. A `ReentrantMutex` type which supports recursive locking.
  68 16. An *experimental* deadlock detector that works for `Mutex`,
  69     `RwLock` and `ReentrantMutex`. This feature is disabled by default and
  70     can be enabled via the `deadlock_detection` feature.
  71 17. `RwLock` supports atomically upgrading an "upgradable" read lock into a
  72     write lock.
  73 18. Optional support for [serde](https://docs.serde.rs/serde/).  Enable via the
  74     feature `serde`.  **NOTE!** this support is for `Mutex`, `ReentrantMutex`,
  75     and `RwLock` only; `Condvar` and `Once` are not currently supported.
  76 19. Lock guards can be sent to other threads when the `send_guard` feature is
  77     enabled.
  78
  79 ## The parking lot
  80
  81 To keep these primitives small, all thread queuing and suspending
  82 functionality is offloaded to the *parking lot*. The idea behind this is
  83 based on the Webkit [`WTF::ParkingLot`](https://webkit.org/blog/6161/locking-in-webkit/)
  84 class, which essentially consists of a hash table mapping of lock addresses
  85 to queues of parked (sleeping) threads. The Webkit parking lot was itself
  86 inspired by Linux [futexes](http://man7.org/linux/man-pages/man2/futex.2.html),
  87 but it is more powerful since it allows invoking callbacks while holding a queue
  88 lock.
  89
  90 ## Nightly vs stable
  91
  92 There are a few restrictions when using this library on stable Rust:
  93
  94 - You will have to use the `const_*` functions (e.g. `const_mutex(val)`) to
  95   statically initialize the locking primitives. Using e.g. `Mutex::new(val)`
  96   does not work on stable Rust yet.
  97 - The `wasm32-unknown-unknown` target is only supported on nightly and requires
  98   `-C target-feature=+atomics` in `RUSTFLAGS`.
  99
 100 To enable nightly-only functionality, you need to enable the `nightly` feature
 101 in Cargo (see below).
 102
 103 ## Usage
 104
 105 Add this to your `Cargo.toml`:
 106
 107 ```toml
 108 [dependencies]
 109 parking_lot = "0.11"
 110 ```
 111
 112 To enable nightly-only features, add this to your `Cargo.toml` instead:
 113
 114 ```toml
 115 [dependencies]
 116 parking_lot = { version = "0.11", features = ["nightly"] }
 117 ```
 118
 119 The experimental deadlock detector can be enabled with the
 120 `deadlock_detection` Cargo feature.
 121
 122 To allow sending `MutexGuard`s and `RwLock*Guard`s to other threads, enable the
 123 `send_guard` option.
 124
 125 Note that the `deadlock_detection` and `send_guard` features are incompatible
 126 and cannot be used together.
 127
 128 Hardware lock elision support for x86 can be enabled with the
 129 `hardware-lock-elision` feature. This requires Rust 1.59 due to the use of
 130 inline assembly.
 131
 132 The core parking lot API is provided by the `parking_lot_core` crate. It is
 133 separate from the synchronization primitives in the `parking_lot` crate so that
 134 changes to the core API do not cause breaking changes for users of `parking_lot`.
 135
 136 ## Minimum Rust version
 137
 138 The current minimum required Rust version is 1.49. Any change to this is
 139 considered a breaking change and will require a major version bump.
 140
 141 ## License
 142
 143 Licensed under either of
 144
 145  * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
 146  * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
 147
 148 at your option.
 149
 150 ### Contribution
 151
 152 Unless you explicitly state otherwise, any contribution intentionally submitted
 153 for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any
 154 additional terms or conditions.