#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::cell::Cell;
use std::ptr::NonNull;
use crate::guard::{retire, Retired};
use crate::key::AsBytes;
use crate::latch::{AbortOnUnwind, ChainGuard, SpinBackoff};
use crate::raw::heap::HeapStorage;
use crate::raw::{Mode, Outcome, RawTree, Unpublished};
use crate::versioned::node::{VersionNode, VersionedLeaf};
pub(crate) type Storage<K, V> = HeapStorage<VersionedLeaf<K, V>>;
pub(crate) type RemovedHead<K, V> = (NonNull<VersionedLeaf<K, V>>, NonNull<VersionNode<V>>);
pub(crate) struct VersionedTree<K, V> {
pub(crate) raw: RawTree<Storage<K, V>>,
}
impl<K, V> VersionedTree<K, V> {
crate::sync::const_fn_unless_loom! {
pub(crate) fn new() -> Self {
Self {
raw: RawTree::new_in(HeapStorage::new()),
}
}
}
#[inline]
pub(crate) fn len(&self) -> usize {
self.raw.len()
}
}
impl<K, V> Drop for VersionedTree<K, V> {
fn drop(&mut self) {
unsafe { self.raw.destroy() }
}
}
#[inline]
pub(crate) fn find_le<V>(head: &VersionNode<V>, max: u64) -> Option<&VersionNode<V>> {
let mut cur: *const VersionNode<V> = head;
while !cur.is_null() {
let n = unsafe { &*cur };
if n.version <= max {
return Some(n);
}
cur = n.next();
}
None
}
fn find_le_ptr<V>(head: *mut VersionNode<V>, max: u64) -> Option<*mut VersionNode<V>> {
let mut cur = head;
while !cur.is_null() {
let n = unsafe { &*cur };
if n.version <= max {
return Some(cur);
}
cur = n.next();
}
None
}
pub(crate) fn chain<V>(head: &VersionNode<V>) -> impl Iterator<Item = &VersionNode<V>> {
let mut cur: *const VersionNode<V> = head;
std::iter::from_fn(move || {
if cur.is_null() {
return None;
}
let n = unsafe { &*cur };
cur = n.next();
Some(n)
})
}
pub(crate) enum Unlinked {
Done(usize),
Refused,
Missing,
}
impl<K: AsBytes + Send + 'static, V: Send + 'static> VersionedTree<K, V> {
pub(crate) fn insert(
&self,
key: K,
version: u64,
value: Option<V>,
guard: &crossbeam_epoch::Guard,
) -> isize {
let mut backoff = SpinBackoff::new();
while let Some(leaf) = self.raw.get(key.as_bytes()) {
let l = unsafe { leaf.as_ref() };
let Some(w) = l.chain_latch.lock() else {
backoff.spin();
continue;
};
let delta = self.apply_locked(l, version, value, w, guard);
drop(key);
return delta;
}
let count = isize::from(value.is_some());
let leaf = VersionedLeaf::new_boxed(key, version, value);
let owner = unsafe { Unpublished::new(&self.raw.storage, leaf) };
let key_bytes = unsafe { leaf.as_ref() }.key.as_bytes();
loop {
let outcome =
match self
.raw
.insert(&owner, key_bytes, Mode::InsertIfAbsent, count, guard)
{
Ok(o) => o,
Err(never) => match never {},
};
match outcome {
Outcome::Inserted(_) => return count,
Outcome::Existing(existing) => {
let e = unsafe { existing.as_ref() };
let Some(w) = e.chain_latch.lock() else {
backoff.spin();
continue;
};
let (version, value) = unsafe { VersionedLeaf::take_first(owner.ptr()) };
return self.apply_locked(e, version, value, w, guard);
}
Outcome::Replaced(_) => unreachable!("InsertIfAbsent never replaces"),
}
}
}
fn apply_locked(
&self,
leaf: &VersionedLeaf<K, V>,
version: u64,
value: Option<V>,
w: ChainGuard<'_>,
guard: &crossbeam_epoch::Guard,
) -> isize {
let head = leaf.head_ptr();
let old_live = !unsafe { &*head }.is_tombstone();
let at = |p: *mut VersionNode<V>| -> Option<&VersionNode<V>> {
unsafe { p.as_ref() }
};
let mut prev: *mut VersionNode<V> = std::ptr::null_mut();
let mut cur = head;
while let Some(n) = at(cur).filter(|n| n.version > version) {
prev = cur;
cur = n.next();
}
let node = leaf.alloc_version(&w, version, value);
let replaced = at(cur).is_some_and(|n| n.version == version);
unsafe {
(*node).init_next(if replaced { (*cur).next() } else { cur });
}
let bomb = AbortOnUnwind;
if prev.is_null() {
leaf.set_head(&w, node);
} else {
unsafe { (*prev).set_next(&w, node) };
}
if replaced {
unsafe { (*cur).mark_superseded(&w) };
}
let new_head = leaf.head_ptr();
let new_live = !unsafe { &*new_head }.is_tombstone();
let delta = isize::from(new_live) - isize::from(old_live);
self.raw.len_add(delta);
bomb.defuse();
drop(w);
if replaced {
unsafe { retire_version(cur, guard) };
}
delta
}
pub(crate) fn remove_head(
&self,
key: &[u8],
guard: &crossbeam_epoch::Guard,
) -> Option<RemovedHead<K, V>> {
let mut backoff = SpinBackoff::new();
loop {
let leaf_ptr = self.raw.get(key)?;
let leaf = unsafe { leaf_ptr.as_ref() };
let Some(w) = leaf.chain_latch.lock() else {
backoff.spin();
continue;
};
let head = leaf.head_ptr();
let h = unsafe { &*head };
if h.is_tombstone() {
return None;
}
let tomb = leaf.alloc_version(&w, h.version, None);
unsafe { (*tomb).init_next(h.next()) };
let bomb = AbortOnUnwind;
leaf.set_head(&w, tomb);
h.mark_superseded(&w);
self.raw.len_add(-1);
bomb.defuse();
drop(w);
unsafe { retire_version(head, guard) };
return Some((leaf_ptr, unsafe { NonNull::new_unchecked(head) }));
}
}
fn unlink_leaf(
&self,
leaf: NonNull<VersionedLeaf<K, V>>,
check: impl Fn(&VersionedLeaf<K, V>) -> bool,
guard: &crossbeam_epoch::Guard,
) -> Unlinked {
let key = unsafe { leaf.as_ref() }.key.as_bytes();
let seen: Cell<Option<Option<usize>>> = Cell::new(None);
let removed = self.raw.remove_confirmed(
key,
|c| c == leaf,
|c| {
seen.set(Some(None));
let l = unsafe { c.as_ref() };
let w = l.chain_latch.lock()?;
if !check(l) {
return None;
}
seen.set(Some(Some(chain(l.head()).count())));
let live = !l.head().is_tombstone();
w.kill();
Some(isize::from(live))
},
guard,
);
match (removed, seen.get()) {
(Some(_), Some(Some(n))) => Unlinked::Done(n),
(Some(_), _) => unreachable!("confirm accepted without counting"),
(None, Some(_)) => Unlinked::Refused,
(None, None) if unsafe { leaf.as_ref() }.chain_latch.is_dead() => Unlinked::Refused,
(None, None) => Unlinked::Missing,
}
}
pub(crate) fn prune_leaf<F: Fn(&V) -> bool>(
&self,
leaf_ptr: NonNull<VersionedLeaf<K, V>>,
min_version: u64,
is_tombstone: &F,
guard: &crossbeam_epoch::Guard,
) -> usize {
let leaf = unsafe { leaf_ptr.as_ref() };
for _attempt in 0..64 {
let head = leaf.head_ptr();
let Some(t_ptr) = find_le_ptr(head, min_version) else {
return 0;
};
let t = unsafe { &*t_ptr };
if t_ptr == head && t.value().is_none_or(is_tombstone) {
match self.unlink_leaf(leaf_ptr, |l| l.head_ptr() == t_ptr, guard) {
Unlinked::Done(n) => return n,
Unlinked::Refused if leaf.chain_latch.is_dead() => return 0,
Unlinked::Refused => continue,
Unlinked::Missing => {}
}
}
let Some(w) = leaf.chain_latch.lock() else {
return 0;
};
let head_now = leaf.head_ptr();
if find_le_ptr(head_now, min_version) != Some(t_ptr) || t.is_superseded() {
drop(w);
continue;
}
let bomb = AbortOnUnwind;
let mut unlinked: Vec<*mut VersionNode<V>> = Vec::new();
let mut cur = t.next();
t.set_next(&w, std::ptr::null_mut());
while !cur.is_null() {
let n = unsafe { &*cur };
n.mark_superseded(&w);
unlinked.push(cur);
cur = n.next();
}
bomb.defuse();
drop(w);
let count = unlinked.len();
for n in unlinked {
unsafe { retire_version(n, guard) };
}
return count;
}
0
}
pub(crate) fn remove_key(&self, key: &[u8], guard: &crossbeam_epoch::Guard) -> bool {
let mut backoff = SpinBackoff::new();
loop {
let Some(leaf) = self.raw.get(key) else {
return false;
};
match self.unlink_leaf(leaf, |_| true, guard) {
Unlinked::Done(_) => return true,
Unlinked::Missing => return false,
Unlinked::Refused => backoff.spin(),
}
}
}
pub(crate) fn remove_version(
&self,
key: &[u8],
version: u64,
guard: &crossbeam_epoch::Guard,
) -> bool {
let only = |l: &VersionedLeaf<K, V>| {
let h = l.head();
h.version == version && h.next().is_null()
};
let mut backoff = SpinBackoff::new();
loop {
let Some(leaf_ptr) = self.raw.get(key) else {
return false;
};
let leaf = unsafe { leaf_ptr.as_ref() };
if only(leaf) {
match self.unlink_leaf(leaf_ptr, only, guard) {
Unlinked::Done(_) => return true,
Unlinked::Missing => return false,
Unlinked::Refused if leaf.chain_latch.is_dead() => {
backoff.spin();
continue;
}
Unlinked::Refused => {}
}
}
let Some(w) = leaf.chain_latch.lock() else {
backoff.spin();
continue;
};
let head = leaf.head_ptr();
let at = |p: *mut VersionNode<V>| -> Option<&VersionNode<V>> {
unsafe { p.as_ref() }
};
let mut prev: *mut VersionNode<V> = std::ptr::null_mut();
let mut cur = head;
while let Some(n) = at(cur).filter(|n| n.version > version) {
prev = cur;
cur = n.next();
}
let Some(n) = at(cur).filter(|n| n.version == version) else {
return false;
};
if prev.is_null() && n.next().is_null() {
drop(w);
continue;
}
let old_live = !unsafe { &*head }.is_tombstone();
let bomb = AbortOnUnwind;
if prev.is_null() {
leaf.set_head(&w, n.next());
} else {
unsafe { (*prev).set_next(&w, n.next()) };
}
n.mark_superseded(&w);
let new_live = !leaf.head().is_tombstone();
self.raw
.len_add(isize::from(new_live) - isize::from(old_live));
bomb.defuse();
drop(w);
unsafe { retire_version(cur, guard) };
return true;
}
}
pub(crate) fn clear(&self, guard: &crossbeam_epoch::Guard) {
self.raw.clear_counting(guard, |l| {
let l = unsafe { l.as_ref() };
let Some(w) = l.chain_latch.lock() else {
debug_assert!(false, "only its node's latch holder kills a chain");
return 0;
};
let live = !l.head().is_tombstone();
w.kill();
isize::from(live)
});
}
pub(crate) fn validate(&mut self) {
self.raw.validate_counting(|l| {
usize::from(!unsafe { l.as_ref() }.head().is_tombstone())
});
}
}
unsafe fn retire_version<V: Send + 'static>(
n: *mut VersionNode<V>,
guard: &crossbeam_epoch::Guard,
) {
if unsafe { (*n).is_inline() } {
return;
}
retire(guard, unsafe {
Retired::from_non_null(NonNull::new_unchecked(n))
});
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::Arc;
#[test]
fn transient_len_never_negative() {
let t = Arc::new(VersionedTree::<Vec<u8>, u64>::new());
let stop = Arc::new(AtomicBool::new(false));
let writer = {
let (t, stop) = (Arc::clone(&t), Arc::clone(&stop));
std::thread::spawn(move || {
let n = if cfg!(miri) { 20 } else { 100_000 };
let mut v = 1u64;
while !stop.load(Ordering::Relaxed) && v < n {
let g = crate::guard::pin();
t.insert(vec![7], v, Some(v), &g);
t.insert(vec![7], v + 1, None, &g);
v += 2;
}
})
};
let polls = if cfg!(miri) { 50 } else { 200_000 };
for _ in 0..polls {
let len = t.raw.raw_len();
assert!((0..=1).contains(&len), "raw len {len} out of range");
}
stop.store(true, Ordering::Relaxed);
writer.join().unwrap();
assert_eq!(t.raw.raw_len(), 0);
}
}