1 //! Strategies for protecting the reference counts. 2 //! 3 //! There are multiple algorithms how to protect the reference counts while they're being updated 4 //! by multiple threads, each with its own set of pros and cons. The [`DefaultStrategy`] is used by 5 //! default and should generally be the least surprising option. It is possible to pick a different 6 //! strategy. 7 //! 8 //! For now, the traits in here are sealed and don't expose any methods to the users of the crate. 9 //! This is because we are not confident about the details just yet. In the future it may be 10 //! possible for downstream users to implement their own, but for now it is only so users can 11 //! choose one of the provided. 12 //! 13 //! It is expected that future strategies would come with different capabilities and limitations. 14 //! In particular, some that are not "tight" in the cleanup (delay the cleanup) or not support the 15 //! compare and swap operations. 16 //! 17 //! Currently, we have these strategies: 18 //! 19 //! * [`DefaultStrategy`] (this one is used implicitly) 20 //! * [`RwLock<()>`][std::sync::RwLock] 21 //! 22 //! # Testing 23 //! 24 //! Formally, the [`RwLock<()>`][std::sync::RwLock] may be used as a strategy too. It doesn't have 25 //! the performance characteristics or lock-free guarantees of the others, but it is much simpler 26 //! and contains less `unsafe` code (actually, less code altogether). Therefore, it can be used for 27 //! testing purposes and cross-checking. 28 //! 29 //! Note that generally, using [`RwLock<Arc<T>>`][std::sync::RwLock] is likely to be better 30 //! performance wise. So if the goal is to not use third-party unsafe code, only the one in 31 //! [`std`], that is the better option. This is provided mostly for investigation and testing of 32 //! [`ArcSwap`] itself or algorithms written to use [`ArcSwap`]. 33 //! 34 //! *This is not meant to be used in production code*. 35 //! 36 //! [`ArcSwap`]: crate::ArcSwap 37 //! [`load`]: crate::ArcSwapAny::load 38 39 use core::borrow::Borrow; 40 use core::sync::atomic::AtomicPtr; 41 42 use crate::ref_cnt::RefCnt; 43 44 pub(crate) mod hybrid; 45 46 #[cfg(all( 47 feature = "internal-test-strategies", 48 feature = "experimental-thread-local" 49 ))] 50 compile_error!("experimental-thread-local is incompatible with internal-test-strategies as it enables #[no_std]"); 51 52 #[cfg(feature = "internal-test-strategies")] 53 mod rw_lock; 54 // Do not use from outside of the crate. 55 #[cfg(feature = "internal-test-strategies")] 56 #[doc(hidden)] 57 pub mod test_strategies; 58 59 use self::hybrid::{DefaultConfig, HybridStrategy}; 60 61 /// The default strategy. 62 /// 63 /// It is used by the type aliases [`ArcSwap`][crate::ArcSwap] and 64 /// [`ArcSwapOption`][crate::ArcSwapOption]. Only the other strategies need to be used explicitly. 65 /// 66 /// # Performance characteristics 67 /// 68 /// * It is optimized for read-heavy situations, with possibly many concurrent read accesses from 69 /// multiple threads. Readers don't contend each other at all. 70 /// * Readers are wait-free (with the exception of at most once in `usize::MAX / 4` accesses, which 71 /// is only lock-free). 72 /// * Writers are lock-free. 73 /// * Reclamation is exact ‒ the resource is released as soon as possible (works like RAII, not 74 /// like a traditional garbage collector; can contain non-`'static` data). 75 /// 76 /// Each thread has a limited number of fast slots (currently 8, but the exact number is not 77 /// guaranteed). If it holds at most that many [`Guard`]s at once, acquiring them is fast. Once 78 /// these slots are used up (by holding to these many [`Guard`]s), acquiring more of them will be 79 /// slightly slower, but still wait-free. 80 /// 81 /// If you expect to hold a lot of "handles" to the data around, or hold onto it for a long time, 82 /// you may want to prefer the [`load_full`][crate::ArcSwapAny::load_full] method. 83 /// 84 /// The speed of the fast slots is in the ballpark of locking an *uncontented* mutex. The advantage 85 /// over the mutex is the stability of speed in the face of contention from other threads ‒ while 86 /// the performance of mutex goes rapidly down, the slowdown of running out of held slots or heavy 87 /// concurrent writer thread in the area of single-digit multiples. 88 /// 89 /// The ballpark benchmark figures (my older computer) are around these, but you're welcome to run 90 /// the benchmarks in the git repository or write your own. 91 /// 92 /// * Load (both uncontented and contented by other loads): ~30ns 93 /// * `load_full`: ~50ns uncontented, goes up a bit with other `load_full` in other threads on the 94 /// same `Arc` value (~80-100ns). 95 /// * Loads after running out of the slots ‒ about 10-20ns slower than `load_full`. 96 /// * Stores: Dependent on number of threads, but generally low microseconds. 97 /// * Loads with heavy concurrent writer (to the same `ArcSwap`): ~250ns. 98 /// 99 /// [`load`]: crate::ArcSwapAny::load 100 /// [`Guard`]: crate::Guard 101 pub type DefaultStrategy = HybridStrategy<DefaultConfig>; 102 103 /// Strategy for isolating instances. 104 /// 105 /// It is similar to [`DefaultStrategy`], however the spin lock is not sharded (therefore multiple 106 /// concurrent threads might get bigger hit when multiple threads have to fall back). Nevertheless, 107 /// each instance has a private spin lock, not influencing the other instances. That also makes 108 /// them bigger in memory. 109 /// 110 /// The hazard pointers are still shared between all instances. 111 /// 112 /// The purpose of this strategy is meant for cases where a single instance is going to be 113 /// "tortured" a lot, so it should not overflow to other instances. 114 /// 115 /// This too may be changed for something else (but with at least as good guarantees, primarily 116 /// that other instances won't get influenced by the "torture"). 117 // Testing if the DefaultStrategy is good enough to replace it fully and then deprecate. 118 #[doc(hidden)] 119 pub type IndependentStrategy = DefaultStrategy; 120 121 // TODO: When we are ready to un-seal, should these traits become unsafe? 122 123 pub(crate) mod sealed { 124 use super::*; 125 use crate::as_raw::AsRaw; 126 127 pub trait Protected<T>: Borrow<T> { into_inner(self) -> T128 fn into_inner(self) -> T; from_inner(ptr: T) -> Self129 fn from_inner(ptr: T) -> Self; 130 } 131 132 pub trait InnerStrategy<T: RefCnt> { 133 // Drop „unlocks“ 134 type Protected: Protected<T>; load(&self, storage: &AtomicPtr<T::Base>) -> Self::Protected135 unsafe fn load(&self, storage: &AtomicPtr<T::Base>) -> Self::Protected; wait_for_readers(&self, old: *const T::Base, storage: &AtomicPtr<T::Base>)136 unsafe fn wait_for_readers(&self, old: *const T::Base, storage: &AtomicPtr<T::Base>); 137 } 138 139 pub trait CaS<T: RefCnt>: InnerStrategy<T> { compare_and_swap<C: AsRaw<T::Base>>( &self, storage: &AtomicPtr<T::Base>, current: C, new: T, ) -> Self::Protected140 unsafe fn compare_and_swap<C: AsRaw<T::Base>>( 141 &self, 142 storage: &AtomicPtr<T::Base>, 143 current: C, 144 new: T, 145 ) -> Self::Protected; 146 } 147 } 148 149 /// A strategy for protecting the reference counted pointer `T`. 150 /// 151 /// This chooses the algorithm for how the reference counts are protected. Note that the user of 152 /// the crate can't implement the trait and can't access any method; this is hopefully temporary 153 /// measure to make sure the interface is not part of the stability guarantees of the crate. Once 154 /// enough experience is gained with implementing various strategies, it will be un-sealed and 155 /// users will be able to provide their own implementation. 156 /// 157 /// For now, the trait works only as a bound to talk about the types that represent strategies. 158 pub trait Strategy<T: RefCnt>: sealed::InnerStrategy<T> {} 159 impl<T: RefCnt, S: sealed::InnerStrategy<T>> Strategy<T> for S {} 160 161 /// An extension of the [`Strategy`], allowing for compare and swap operation. 162 /// 163 /// The compare and swap operation is "advanced" and not all strategies need to support them. 164 /// Therefore, it is a separate trait. 165 /// 166 /// Similarly, it is not yet made publicly usable or implementable and works only as a bound. 167 pub trait CaS<T: RefCnt>: sealed::CaS<T> {} 168 impl<T: RefCnt, S: sealed::CaS<T>> CaS<T> for S {} 169