Heavy Cell - atomic refcells and reference-counted atomic refcells and borrows

AtomicRefCell and ArcCell types plus associated guard/borrow types. Based on the atomic_refcellcrate.

License

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.

Contribution

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.

lib.rs:

A no_std port of the atomic_refcell crate, with added functionality for Arc-wrapped AtomicRefCells.

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.