src/strategy/mod.rs

//! Strategies for protecting the reference counts.
//!
//! There are multiple algorithms how to protect the reference counts while they're being updated
//! by multiple threads, each with its own set of pros and cons. The [`DefaultStrategy`] is used by
//! default and should generally be the least surprising option. It is possible to pick a different
//! strategy.
//!
//! For now, the traits in here are sealed and don't expose any methods to the users of the crate.
//! This is because we are not confident about the details just yet. In the future it may be
//! possible for downstream users to implement their own, but for now it is only so users can
//! choose one of the provided.
//!
//! It is expected that future strategies would come with different capabilities and limitations.
//! In particular, some that are not "tight" in the cleanup (delay the cleanup) or not support the
//! compare and swap operations.
//!
//! Currently, we have these strategies:
//!
//! * [`DefaultStrategy`] (this one is used implicitly)
//! * [`RwLock<()>`][std::sync::RwLock]
//!
//! # Testing
//!
//! Formally, the [`RwLock<()>`][std::sync::RwLock] may be used as a strategy too. It doesn't have
//! the performance characteristics or lock-free guarantees of the others, but it is much simpler
//! and contains less `unsafe` code (actually, less code altogether). Therefore, it can be used for
//! testing purposes and cross-checking.
//!
//! Note that generally, using [`RwLock<Arc<T>>`][std::sync::RwLock] is likely to be better
//! performance wise. So if the goal is to not use third-party unsafe code, only the one in
//! [`std`], that is the better option. This is provided mostly for investigation and testing of
//! [`ArcSwap`] itself or algorithms written to use [`ArcSwap`].
//!
//! *This is not meant to be used in production code*.
//!
//! [`ArcSwap`]: crate::ArcSwap
//! [`load`]: crate::ArcSwapAny::load

use std::borrow::Borrow;
use std::sync::atomic::AtomicPtr;

use crate::ref_cnt::RefCnt;

pub(crate) mod hybrid;
mod rw_lock;
// Do not use from outside of the crate.
#[cfg(feature = "internal-test-strategies")]
#[doc(hidden)]
pub mod test_strategies;

use self::hybrid::{DefaultConfig, HybridStrategy};

/// The default strategy.
///
/// It is used by the type aliases [`ArcSwap`][crate::ArcSwap] and
/// [`ArcSwapOption`][crate::ArcSwapOption]. Only the other strategies need to be used explicitly.
///
/// # Performance characteristics
///
/// * It is optimized for read-heavy situations, with possibly many concurrent read accesses from
///   multiple threads. Readers don't contend each other at all.
/// * Readers are wait-free (with the exception of at most once in `usize::MAX / 4` accesses, which
///   is only lock-free).
/// * Writers are lock-free.
/// * Reclamation is exact ‒ the resource is released as soon as possible (works like RAII, not
///   like a traditional garbage collector; can contain non-`'static` data).
///
/// Each thread has a limited number of fast slots (currently 8, but the exact number is not
/// guaranteed). If it holds at most that many [`Guard`]s at once, acquiring them is fast. Once
/// these slots are used up (by holding to these many [`Guard`]s), acquiring more of them will be
/// slightly slower, but still wait-free.
///
/// If you expect to hold a lot of "handles" to the data around, or hold onto it for a long time,
/// you may want to prefer the [`load_full`][crate::ArcSwapAny::load_full] method.
///
/// The speed of the fast slots is in the ballpark of locking an *uncontented* mutex. The advantage
/// over the mutex is the stability of speed in the face of contention from other threads ‒ while
/// the performance of mutex goes rapidly down, the slowdown of running out of held slots or heavy
/// concurrent writer thread in the area of single-digit multiples.
///
/// The ballpark benchmark figures (my older computer) are around these, but you're welcome to run
/// the benchmarks in the git repository or write your own.
///
/// * Load (both uncontented and contented by other loads): ~30ns
/// * `load_full`: ~50ns uncontented, goes up a bit with other `load_full` in other threads on the
///   same `Arc` value (~80-100ns).
/// * Loads after running out of the slots ‒ about 10-20ns slower than `load_full`.
/// * Stores: Dependent on number of threads, but generally low microseconds.
/// * Loads with heavy concurrent writer (to the same `ArcSwap`): ~250ns.
///
/// [`load`]: crate::ArcSwapAny::load
/// [`Guard`]: crate::Guard
pub type DefaultStrategy = HybridStrategy<DefaultConfig>;

/// Strategy for isolating instances.
///
/// It is similar to [`DefaultStrategy`], however the spin lock is not sharded (therefore multiple
/// concurrent threads might get bigger hit when multiple threads have to fall back). Nevertheless,
/// each instance has a private spin lock, not influencing the other instances. That also makes
/// them bigger in memory.
///
/// The hazard pointers are still shared between all instances.
///
/// The purpose of this strategy is meant for cases where a single instance is going to be
/// "tortured" a lot, so it should not overflow to other instances.
///
/// This too may be changed for something else (but with at least as good guarantees, primarily
/// that other instances won't get influenced by the "torture").
// Testing if the DefaultStrategy is good enough to replace it fully and then deprecate.
#[doc(hidden)]
pub type IndependentStrategy = DefaultStrategy;

// TODO: When we are ready to un-seal, should these traits become unsafe?

pub(crate) mod sealed {
    use super::*;
    use crate::as_raw::AsRaw;

    pub trait Protected<T>: Borrow<T> {
        fn into_inner(self) -> T;
        fn from_inner(ptr: T) -> Self;
    }

    pub trait InnerStrategy<T: RefCnt> {
        // Drop „unlocks“
        type Protected: Protected<T>;
        unsafe fn load(&self, storage: &AtomicPtr<T::Base>) -> Self::Protected;
        unsafe fn wait_for_readers(&self, old: *const T::Base, storage: &AtomicPtr<T::Base>);
    }

    pub trait CaS<T: RefCnt>: InnerStrategy<T> {
        unsafe fn compare_and_swap<C: AsRaw<T::Base>>(
            &self,
            storage: &AtomicPtr<T::Base>,
            current: C,
            new: T,
        ) -> Self::Protected;
    }
}

/// A strategy for protecting the reference counted pointer `T`.
///
/// This chooses the algorithm for how the reference counts are protected. Note that the user of
/// the crate can't implement the trait and can't access any method; this is hopefully temporary
/// measure to make sure the interface is not part of the stability guarantees of the crate. Once
/// enough experience is gained with implementing various strategies, it will be un-sealed and
/// users will be able to provide their own implementation.
///
/// For now, the trait works only as a bound to talk about the types that represent strategies.
pub trait Strategy<T: RefCnt>: sealed::InnerStrategy<T> {}
impl<T: RefCnt, S: sealed::InnerStrategy<T>> Strategy<T> for S {}

/// An extension of the [`Strategy`], allowing for compare and swap operation.
///
/// The compare and swap operation is "advanced" and not all strategies need to support them.
/// Therefore, it is a separate trait.
///
/// Similarly, it is not yet made publicly usable or implementable and works only as a bound.
pub trait CaS<T: RefCnt>: sealed::CaS<T> {}
impl<T: RefCnt, S: sealed::CaS<T>> CaS<T> for S {}