| lib.rs |
Implements a container type providing RefCell-like semantics for objects
shared across threads.
RwLock is traditionally considered to be the |Sync| analogue of RefCell.
However, for consumers that can guarantee that they will never mutably
borrow the contents concurrently with immutable borrows, an RwLock is
overkill, and has key disadvantages:
* Performance: Even the fastest existing implementation of RwLock (that of
parking_lot) performs at least two atomic operations during immutable
borrows. This makes mutable borrows significantly cheaper than immutable
borrows, leading to weird incentives when writing performance-critical
code.
* Features: Implementing AtomicRefCell on top of RwLock makes it impossible
to implement useful things like AtomicRef{,Mut}::map.
As such, we re-implement RefCell semantics from scratch with a single atomic
reference count. The primary complication of this scheme relates to keeping
things in a consistent state when one thread performs an illegal borrow and
panics. Since an AtomicRefCell can be accessed by multiple threads, and since
panics are recoverable, we need to ensure that an illegal (panicking) access by
one thread does not lead to undefined behavior on other, still-running threads.
So we represent things as follows:
* Any value with the high bit set (so half the total refcount space) indicates
a mutable borrow.
* Mutable borrows perform an atomic compare-and-swap, swapping in the high bit
if the current value is zero. If the current value is non-zero, the thread
panics and the value is left undisturbed.
* Immutable borrows perform an atomic increment. If the new value has the high
bit set, the thread panics. The incremented refcount is left as-is, since it
still represents a valid mutable borrow. When the mutable borrow is released,
the refcount is set unconditionally to zero, clearing any stray increments by
panicked threads.
There are a few additional purely-academic complications to handle overflow,
which are documented in the implementation.
The rest of this module is mostly derived by copy-pasting the implementation of
RefCell and fixing things up as appropriate. Certain non-threadsafe methods
have been removed. We segment the concurrency logic from the rest of the code to
keep the tricky parts small and easy to audit. |
15789 |