use core::sync::atomic::{AtomicPtr, AtomicU64, AtomicUsize, Ordering};
pub struct HazardDomain<T, const READERS: usize, const RETIRED: usize> {
published: [AtomicPtr<T>; READERS],
retired: [AtomicPtr<T>; RETIRED],
next_reader: AtomicUsize,
spilled: AtomicU64,
}
impl<T, const READERS: usize, const RETIRED: usize> HazardDomain<T, READERS, RETIRED> {
pub const fn new() -> Self {
Self {
published: [const { AtomicPtr::new(core::ptr::null_mut()) }; READERS],
retired: [const { AtomicPtr::new(core::ptr::null_mut()) }; RETIRED],
next_reader: AtomicUsize::new(0),
spilled: AtomicU64::new(0),
}
}
pub fn claim_reader(&self) -> usize {
let slot = self.next_reader.fetch_add(1, Ordering::AcqRel);
assert!(
slot < READERS,
"hazard domain sized for {READERS} readers, thread {slot} asked for a slot"
);
slot
}
pub fn protect<'d>(
&'d self,
reader: usize,
source: &AtomicPtr<T>,
) -> HazardGuard<'d, T, READERS, RETIRED> {
loop {
let candidate = source.load(Ordering::Acquire);
self.published[reader].store(candidate, Ordering::SeqCst);
if source.load(Ordering::SeqCst) == candidate {
return HazardGuard {
domain: self,
reader,
ptr: candidate,
};
}
}
}
pub unsafe fn retire(&self, ptr: *mut T) {
if ptr.is_null() {
return;
}
self.sweep();
for slot in self.retired.iter() {
if slot
.compare_exchange(
core::ptr::null_mut(),
ptr,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
{
self.sweep();
return;
}
}
self.spilled.fetch_add(1, Ordering::Relaxed);
}
pub fn sweep(&self) {
for slot in self.retired.iter() {
let candidate = slot.load(Ordering::Acquire);
if candidate.is_null() || self.is_published(candidate) {
continue;
}
if slot
.compare_exchange(
candidate,
core::ptr::null_mut(),
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
{
drop(unsafe { Box::from_raw(candidate) });
}
}
}
fn is_published(&self, ptr: *mut T) -> bool {
self.published
.iter()
.any(|p| p.load(Ordering::SeqCst) == ptr)
}
pub fn spilled(&self) -> u64 {
self.spilled.load(Ordering::Relaxed)
}
}
impl<T, const READERS: usize, const RETIRED: usize> Default
for HazardDomain<T, READERS, RETIRED>
{
fn default() -> Self {
Self::new()
}
}
pub struct HazardGuard<'d, T, const READERS: usize, const RETIRED: usize> {
domain: &'d HazardDomain<T, READERS, RETIRED>,
reader: usize,
ptr: *mut T,
}
impl<T, const READERS: usize, const RETIRED: usize> HazardGuard<'_, T, READERS, RETIRED> {
pub fn get(&self) -> Option<&T> {
if self.ptr.is_null() {
return None;
}
Some(unsafe { &*self.ptr })
}
}
impl<T, const READERS: usize, const RETIRED: usize> Drop for HazardGuard<'_, T, READERS, RETIRED> {
fn drop(&mut self) {
self.domain.published[self.reader].store(core::ptr::null_mut(), Ordering::SeqCst);
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::AtomicBool;
type Domain = HazardDomain<u64, 8, 16>;
#[test]
fn a_guard_reads_what_the_source_holds() {
let domain = Domain::new();
let reader = domain.claim_reader();
let source = AtomicPtr::new(Box::into_raw(Box::new(7u64)));
let guard = domain.protect(reader, &source);
assert_eq!(guard.get().copied(), Some(7));
drop(guard);
unsafe { domain.retire(source.swap(core::ptr::null_mut(), Ordering::SeqCst)) };
}
#[test]
fn an_empty_source_reads_as_nothing() {
let domain = Domain::new();
let reader = domain.claim_reader();
let source: AtomicPtr<u64> = AtomicPtr::new(core::ptr::null_mut());
let guard = domain.protect(reader, &source);
assert!(guard.get().is_none());
}
#[test]
fn a_retired_pointer_is_held_while_a_reader_publishes_it() {
let domain = Domain::new();
let reader = domain.claim_reader();
let source = AtomicPtr::new(Box::into_raw(Box::new(11u64)));
let guard = domain.protect(reader, &source);
let removed = source.swap(core::ptr::null_mut(), Ordering::SeqCst);
unsafe { domain.retire(removed) };
assert_eq!(guard.get().copied(), Some(11));
drop(guard);
domain.sweep();
assert_eq!(domain.spilled(), 0, "the retire array had room");
}
#[test]
fn replacing_under_readers_frees_every_generation() {
let domain: Arc<HazardDomain<u64, 8, 16>> = Arc::new(HazardDomain::new());
let source = Arc::new(AtomicPtr::new(Box::into_raw(Box::new(0u64))));
let stop = Arc::new(AtomicBool::new(false));
let mut readers = Vec::new();
for _ in 0..4 {
let domain = Arc::clone(&domain);
let source = Arc::clone(&source);
let stop = Arc::clone(&stop);
readers.push(std::thread::spawn(move || {
let slot = domain.claim_reader();
let mut seen = 0u64;
while !stop.load(Ordering::Relaxed) {
let guard = domain.protect(slot, &source);
if let Some(v) = guard.get() {
seen = seen.wrapping_add(*v);
}
}
seen
}));
}
for round in 1..=200u64 {
let fresh = Box::into_raw(Box::new(round));
let previous = source.swap(fresh, Ordering::SeqCst);
unsafe { domain.retire(previous) };
}
stop.store(true, Ordering::Relaxed);
for r in readers {
r.join().expect("reader thread panicked");
}
let last = source.swap(core::ptr::null_mut(), Ordering::SeqCst);
unsafe { domain.retire(last) };
domain.sweep();
assert_eq!(
domain.spilled(),
0,
"16 retire slots served 4 readers over 200 replacements"
);
}
#[test]
fn a_domain_refuses_more_readers_than_it_is_sized_for() {
let domain: HazardDomain<u64, 2, 4> = HazardDomain::new();
assert_eq!(domain.claim_reader(), 0);
assert_eq!(domain.claim_reader(), 1);
let over = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
domain.claim_reader();
}));
assert!(over.is_err(), "a third reader must not get a silent slot");
}
}