1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315
//! A simple implementation of Hazard-Pointers, that also supports having
//! multiple Hazard-Pointer-Domains
//!
//! # Reference:
//! * [Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects](https://www.eecg.utoronto.ca/~amza/ece1747h/papers/hazard_pointers.pdf)
// TODO
// Add better reuse of Hazard-Pointers, mainly that if a Domain instance is
// dropped, it should mark all of its entries to be reused by other Domains
mod record;
use crate::sync::atomic;
use std::{cell::RefCell, fmt::Debug, sync::Arc};
use record::Record;
mod retire_node;
mod domain;
use domain::{DomainGlobal, TLDomain};
mod guard;
pub use guard::Guard;
use crate::thread_data::ThreadData;
mod global {
use std::sync::Arc;
use lazy_static::lazy_static;
use super::Domain;
// static ref GLOBAL: Domain = Domain::new(64);
lazy_static! {
static ref GLOBAL: Arc<Domain> = Arc::new(Domain::new(64));
}
/// Returns an Arc for the Global Shared Hazard-Pointer Domain
pub fn get_global_domain() -> Arc<Domain> {
GLOBAL.clone()
}
}
pub use global::*;
/// A Hazard-Pointer-Domain that can be used either globally as a shared Domain
/// or as a per Object Domain to seperate the Domains of different Instances of
/// Objects.
///
/// # What is a Hazard-Pointer-Domain
/// A Hazard-Pointer-Domain is a collection of Hazard-Pointers and allows you
/// to seperate different Parts of a System, where you know that they dont need
/// access to the Hazard-Pointers of other Parts.
/// This could lead to performance improvements as all the Parts only check the
/// Hazard-Pointers that are actually relevant for them.
///
/// # Where to use a different Hazard-Pointer-Domain
/// Like previously mentioned different Domains are useful to seperate an
/// entire System into smaller Parts, however there are also other cases where
/// having a custom Domain can be useful.
/// ## Seperating Datastructure Instances
/// Having seperate Domains for individual Datastructures can help with
/// Performance, because for example if you have two Lists and they were to
/// share a single Domain, List 1 has to check the Hazard-Pointers for List 2
/// everytime it needs to work with Hazard-Pointers although they are not
/// relevant in that Case.
#[derive(Clone)]
pub struct Domain {
global: Arc<DomainGlobal>,
local: Arc<ThreadData<RefCell<TLDomain>>>,
reclaim_threshold: usize,
}
impl Debug for Domain {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
f,
"LocalDomain (reclaim_threshold: {})",
self.reclaim_threshold
)
}
}
impl Domain {
/// Creates a new Hazard-Pointer-Domain
///
/// # Params
/// `reclaim_threshold`: The Threshold for waiting Items before attempting
/// to reclaim Memory
pub fn new(reclaim_threshold: usize) -> Self {
Self {
global: Arc::new(DomainGlobal::new()),
local: Arc::new(ThreadData::default()),
reclaim_threshold,
}
}
fn get_local(&self) -> &RefCell<TLDomain> {
self.local.get_or(|| {
let global = self.global.clone();
RefCell::new(TLDomain::new(global, self.reclaim_threshold))
})
}
/// Reads the Data from the given AtomicPtr and protects it using a Hazard-
/// Ptr.
/// Returns you a Guard through which you can interact with the Data loaded
/// from the AtomicPtr and as long as the Guard lives, the Data is safe
/// to access and use
///
/// # Example
/// ```rust
/// # use nolock::hazard_ptr;
/// # use std::sync::atomic;
/// let domain = hazard_ptr::Domain::new(10);
///
/// // Create an AtomicPtr with some Value
/// let ptr = Box::into_raw(Box::new(13));
/// let atom_ptr = atomic::AtomicPtr::new(ptr);
///
/// // Get protected Access to the Value pointed to
/// let guarded = domain.protect(&atom_ptr, atomic::Ordering::SeqCst);
/// // Access the inner Value
/// assert_eq!(13, *guarded);
///
/// unsafe {
/// // Retire/"Free" the Data
/// domain.retire(ptr, |p| { unsafe { Box::from_raw(p) }; });
/// }
///
/// // As long as we still have the Guard, the Data will not actually be
/// // reclaimed and can still be used safely
/// assert_eq!(13, *guarded);
/// ```
pub fn protect<T>(
&self,
atom_ptr: &atomic::AtomicPtr<T>,
load_order: atomic::Ordering,
) -> Guard<T> {
let local = self.get_local();
let mut shared = local.borrow_mut();
shared.protect(atom_ptr, load_order)
}
/// Creates a new empty Guard, that can then be used to protect any sort of
/// Data behind an AtomicPtr.
pub fn empty_guard<T>(&self) -> Guard<T> {
let local = self.get_local();
let mut shared = local.borrow_mut();
shared.empty_guard()
}
/// Marks the given Ptr as retired and once no more Hazard-Ptrs protect
/// the same Ptr, the given `retire_fn` function will be called to
/// properly clean up the Data.
///
/// # Note
/// There is no garantue as to when the given Ptr will actually be retired
/// using the given function, because the Hazard-Pointer that protects the
/// Data may be stored somewhere or the Thread that was responsible for it
/// crashed/wont respond/is not running again and therefore can not mark it
/// as unused anymore.
///
/// # Safety
/// The given Pointer must not be reachable anymore, meaning that it can
/// not be loaded anymore or any new Guards pointing to it can be created.
/// However it is okay to have outstanding Guards pointing to it that may
/// still be used and those are still valid.
///
/// This garantue is already held up by most algorithms as they first swap
/// out the Pointer from any shared references and then perform a call to
/// retire, which is valid in this case as the pointer can not be loaded
/// anymore from the shared reference.
pub unsafe fn retire<T, F>(&self, ptr: *mut T, retire_fn: F)
where
F: Fn(*mut T) + 'static,
{
let local = self.get_local();
let mut shared = local.borrow_mut();
shared.retire_node(ptr as *mut (), move |raw_ptr| retire_fn(raw_ptr as *mut T));
}
/// Forces a reclaimation cycle, however this does not garantue that any
/// Nodes/Ptrs will actually be reclaimed, as they might all still be
/// protected/in use
///
/// # Use Cases
/// This might be useful in a very performance sensitive application, where
/// you want to avoid running the Reclaimation while in a Hot-Path.
/// In these Cases, you can set the reclaimation threshold to a very large
/// Value when creating the Domain, as to avoid triggering it by accident,
/// and then call this function manually outside of the Hot-Path.
pub fn reclaim(&self) {
let local = self.get_local();
let mut shared = local.borrow_mut();
shared.reclaim();
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::sync::atomic;
#[derive(Debug, Clone)]
struct DropCheck {
d_count: Arc<atomic::AtomicU64>,
}
impl DropCheck {
pub fn new() -> Self {
Self {
d_count: Arc::new(atomic::AtomicU64::new(0)),
}
}
pub fn drop_count(&self) -> u64 {
self.d_count.load(atomic::Ordering::SeqCst)
}
}
impl Drop for DropCheck {
fn drop(&mut self) {
self.d_count.fetch_add(1, atomic::Ordering::SeqCst);
}
}
#[test]
#[ignore = "Hazard-Pointers are currently not working"]
fn local_domain_protect() {
let drop_chk = DropCheck::new();
let domain = Arc::new(Domain::new(10));
let raw_ptr = Box::into_raw(Box::new(drop_chk.clone()));
let shared_ptr = atomic::AtomicPtr::new(raw_ptr);
let guard = domain.protect(&shared_ptr, atomic::Ordering::SeqCst);
assert_eq!(0, guard.drop_count());
unsafe {
domain.retire(raw_ptr, |ptr| {
let boxed: Box<DropCheck> = Box::from_raw(ptr);
drop(boxed);
});
}
domain.reclaim();
assert_eq!(0, guard.drop_count());
drop(guard);
let second_drop_chk = DropCheck::new();
let other_raw_ptr = Box::into_raw(Box::new(second_drop_chk.clone()));
shared_ptr.store(other_raw_ptr, atomic::Ordering::SeqCst);
unsafe {
domain.retire(other_raw_ptr, |ptr| {
let boxed = Box::from_raw(ptr);
drop(boxed);
});
}
domain.reclaim();
assert_eq!(1, drop_chk.drop_count());
assert_eq!(1, second_drop_chk.drop_count());
}
}
#[cfg(loom)]
mod loom_tests {
use super::*;
use loom::thread;
use std::sync::Arc;
#[test]
fn swap_remove() {
loom::model(|| {
let og_domain = Arc::new(Domain::new(0));
let initial_boxed = Box::new(13usize);
let shared_ptr = Arc::new(atomic::AtomicPtr::new(Box::into_raw(initial_boxed)));
{
let domain = og_domain.clone();
let shared = shared_ptr.clone();
thread::spawn(move || {
let previous = shared.swap(core::ptr::null_mut(), atomic::Ordering::SeqCst);
unsafe {
domain.retire(previous, |ptr| {
let _ = unsafe { Box::from_raw(ptr) };
});
}
});
}
{
let domain = og_domain.clone();
let shared = shared_ptr.clone();
thread::spawn(move || {
let mut empty_guard: Guard<usize> = domain.empty_guard();
empty_guard.protect(&shared_ptr, atomic::Ordering::SeqCst);
});
}
core::mem::forget(og_domain);
});
}
}