arctic/concurrent/
smr.rs

1//! Implementations of [`Smr`].
2//!
3//! By default, [`ConcurrentMap`][crate::concurrent::Map] uses [seize](https://docs.rs/seize/0.5.1/seize/)
4//! for safe memory reclamation. Support for
5//! [crossbeam-epoch](https://docs.rs/crossbeam-epoch/0.9.18/crossbeam_epoch/)
6//! and hazard keys can be enabled with the
7//! `smr-seize` and `smr-hazard` Cargo features, respectively.
8//! Downstream users can also implement [`Smr`] and [`Guard`]
9//! to provide their own SMR backends.
10
11#[cfg(feature = "smr-epoch")]
12mod epoch;
13/// Auxiliary types for use with hazard keys.
14#[cfg(feature = "smr-hazard")]
15pub mod hazard;
16/// Auxiliary types for use with no-op SMR.
17pub mod no_op;
18#[cfg(feature = "smr-seize")]
19mod seize;
20
21use core::num::NonZeroU64;
22
23#[cfg(feature = "smr-epoch")]
24pub use epoch::Epoch;
25#[doc(inline)]
26#[cfg(feature = "smr-hazard")]
27pub use hazard::Hazard;
28pub use no_op::NoOp;
29#[cfg(feature = "smr-seize")]
30pub use seize::Seize;
31
32cfg_select! {
33    feature = "smr-seize" => {
34        /// Default [`Smr`] backend.
35        pub type Default = Seize;
36    }
37    _ => {
38        /// Default [`Smr`] backend.
39        pub type Default = NoOp;
40    }
41}
42
43use crate::Key;
44use crate::concurrent::Value;
45use crate::stat;
46
47/// Provides [safe memory reclamation](https://arxiv.org/abs/2509.02457) for the
48/// given key and value type.
49pub trait Smr<K: Key, V: Value> {
50    /// Guard type that protects nodes and values during its lifetime,
51    /// can be used to retire allocations, and unprotects when it is dropped.
52    type Guard<'g>: Guard<V>
53    where
54        V: 'g,
55        Self: 'g;
56
57    /// Construct a [`Guard`] that protects nodes and values associated with `prefix`.
58    fn guard<'g>(&'g self, prefix: K::Read<'_>) -> Self::Guard<'g>
59    where
60        V: 'g;
61
62    /// Estimate the peak number of unreclaimed allocations.
63    fn garbage(&self) -> u32 {
64        0
65    }
66}
67
68/// Protects allocations from deallocation, and allows allocations to be retired.
69///
70/// External implementations may call [`deallocate_node`] and [`deallocate_value`]
71/// to deallocate nodes and values
72/// (passed via [`Guard::retire_node`] and [`Guard::retire_value`]) when they
73/// can determine there are no live references.
74pub trait Guard<V: Value> {
75    /// Retire an internal node with prefix length `bits`.
76    ///
77    /// # Safety
78    ///
79    /// Caller must guarantee `node` is a valid node pointer.
80    unsafe fn retire_node(&mut self, bits: usize, node: NonZeroU64);
81
82    /// Retire a value.
83    ///
84    /// # Safety
85    ///
86    /// Caller must guarantee `value` is a valid value pointer.
87    unsafe fn retire_value(&mut self, value: u64);
88}
89
90/// Deallocate a previously retired node.
91///
92/// # Safety
93///
94/// Caller must guarantee there are no live references to `node`,
95/// and that `node` was previously retired via [`Guard::retire_node`].
96pub unsafe fn deallocate_node(node: NonZeroU64) {
97    stat::increment(stat::Counter::FreeRetire);
98    unsafe { ribbit::Packed::<crate::raw::node::Ptr>::from_raw_unchecked(node).deallocate() }
99}
100
101/// Deallocate a previously retired value.
102///
103/// # Safety
104///
105/// Caller must guarantee there are no live references to `value`,
106/// and that `value` was previously retired via [`Guard::<V>::retire_value`][`Guard::retire_value`].
107pub unsafe fn deallocate_value<V: Value>(value: u64) {
108    stat::increment(stat::Counter::FreeRetire);
109    drop(unsafe { V::from_raw_unchecked(value) })
110}
arctic/concurrent/smr.rs

arctic/concurrent/
smr.rs
