use std::sync::atomic::{AtomicU64, Ordering};
#[derive(Debug, Default)]
pub(crate) struct HostContention {
counts: AtomicU64,
}
const IN_FLIGHT: u64 = 1;
const BEGUN: u64 = 1 << 32;
impl HostContention {
pub(crate) fn enter(&self) -> Visit<'_> {
let before = self.counts.fetch_add(BEGUN + IN_FLIGHT, Ordering::SeqCst);
Visit {
host: self,
company: before % BEGUN,
ticket: before / BEGUN,
}
}
fn begun(&self) -> u64 {
self.counts.load(Ordering::SeqCst) / BEGUN
}
}
#[derive(Debug)]
pub(crate) struct Visit<'h> {
host: &'h HostContention,
company: u64,
ticket: u64,
}
impl Visit<'_> {
pub(crate) fn leave(self) -> bool {
let since = self.host.begun().wrapping_sub(self.ticket) % BEGUN;
self.company == 0 && since == 1
}
}
impl Drop for Visit<'_> {
fn drop(&mut self) {
self.host.counts.fetch_sub(IN_FLIGHT, Ordering::SeqCst);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_visit_is_alone_only_when_nothing_overlapped_it() {
let host = HostContention::default();
assert!(
host.enter().leave(),
"a conversation with nothing beside it"
);
let first = host.enter();
let second = host.enter();
assert!(!second.leave(), "one begun while another was running");
assert!(!first.leave(), "one another began and ended within");
let dropped = host.enter();
drop(dropped);
assert!(
host.enter().leave(),
"a conversation dropped unleft still counted as in flight"
);
}
#[test]
fn conversations_begun_side_by_side_are_never_alone() {
const RACES: usize = 500_000;
let host = HostContention::default();
let both_begun = std::sync::Barrier::new(2);
let read_alone = std::sync::atomic::AtomicUsize::new(0);
std::thread::scope(|scope| {
for _ in 0..2 {
scope.spawn(|| {
for _ in 0..RACES {
let visit = host.enter();
both_begun.wait();
if visit.leave() {
read_alone.fetch_add(1, Ordering::Relaxed);
}
both_begun.wait();
}
});
}
});
assert_eq!(
read_alone.load(Ordering::Relaxed),
0,
"a conversation that overlapped another was read as alone"
);
}
}