#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::ptr::NonNull;
use std::sync::Arc;
use crate::arena::node::{VersionNode, VersionedLeaf};
use crate::arena::storage::{ArenaLeaf, ArenaStorage};
use crate::arena::tree::InserterCache;
use crate::arena::Arena;
use crate::key::AsBytes;
use crate::latch::AbortOnUnwind;
use crate::raw::{Mode, Outcome, RawTree, Unpublished};
use crate::sync::atomic::{AtomicU32, Ordering};
pub(crate) type Storage<K, V> = ArenaStorage<VersionedLeaf<K, V>>;
pub(crate) type RemovedHead<K, V> = Result<Option<(NonNull<VersionedLeaf<K, V>>, u32)>, ()>;
pub(crate) struct ArenaVersionedTree<K, V> {
pub(crate) raw: RawTree<Storage<K, V>>,
retired_versions: AtomicU32,
}
pub(crate) fn find_le<'a, V: 'a>(
arena: &'a Arena,
head: u32,
max: u64,
) -> Option<&'a VersionNode<V>> {
let mut off = head;
while off != 0 {
let n = unsafe { arena.ptr::<VersionNode<V>>(off).as_ref() };
if n.version <= max {
return Some(n);
}
off = n.next();
}
None
}
pub(crate) fn chain<'a, V: 'a>(
arena: &'a Arena,
head: u32,
) -> impl Iterator<Item = &'a VersionNode<V>> + 'a {
let mut off = head;
std::iter::from_fn(move || {
if off == 0 {
return None;
}
let n = unsafe { arena.ptr::<VersionNode<V>>(off).as_ref() };
off = n.next();
Some(n)
})
}
impl<K, V> ArenaVersionedTree<K, V> {
pub(crate) fn new(arena: Arc<Arena>) -> Self {
Self {
raw: RawTree::new_in(ArenaStorage::new(arena)),
retired_versions: AtomicU32::new(0),
}
}
#[inline]
pub(crate) fn arena(&self) -> &Arc<Arena> {
&self.raw.storage.arena
}
#[inline]
pub(crate) fn len(&self) -> usize {
self.raw.len()
}
fn retire_version(&self, off: u32) {
let n = unsafe { self.arena().ptr::<VersionNode<V>>(off).as_ref() };
let mut head = self.retired_versions.load(Ordering::Relaxed);
loop {
n.next_retired.store(head, Ordering::Relaxed);
match self.retired_versions.compare_exchange_weak(
head,
off,
Ordering::Release,
Ordering::Relaxed,
) {
Ok(_) => return,
Err(h) => head = h,
}
}
}
fn alloc_version(&self, version: u64, value: Option<V>) -> Result<u32, Option<V>> {
match self
.raw
.storage
.alloc_value(VersionNode::new(version, value))
{
Ok(p) => Ok(self.arena().offset_of(p)),
Err((_, n)) => Err(n.into_value()),
}
}
}
impl<K, V> Drop for ArenaVersionedTree<K, V> {
fn drop(&mut self) {
if !VersionedLeaf::<K, V>::NEEDS_DROP {
return;
}
unsafe { self.raw.destroy() };
let mut off = self.retired_versions.load(Ordering::Relaxed);
while off != 0 {
let n = unsafe { self.arena().ptr::<VersionNode<V>>(off) };
let next = unsafe { n.as_ref() }.next_retired.load(Ordering::Relaxed);
unsafe { n.drop_in_place() };
off = next;
}
}
}
impl<K: AsBytes, V> ArenaVersionedTree<K, V> {
pub(crate) fn insert(
&self,
key: K,
version: u64,
value: Option<V>,
cache: Option<&mut InserterCache>,
) -> Result<isize, (K, Option<V>)> {
if let Some(leaf) = self.raw.get(key.as_bytes()) {
return match self.alloc_version(version, value) {
Ok(node) => Ok(self.apply(leaf, node)),
Err(v) => Err((key, v)),
};
}
let count = isize::from(value.is_some());
let node = match self.alloc_version(version, value) {
Ok(node) => node,
Err(v) => return Err((key, v)),
};
let leaf = match self.raw.storage.alloc_value(VersionedLeaf::new(key, node)) {
Ok(l) => l,
Err((_, l)) => {
let n = unsafe { self.arena().ptr::<VersionNode<V>>(node).read() };
return Err((l.key, n.into_value()));
}
};
let owner = unsafe { Unpublished::new(&self.raw.storage, leaf) };
let key_bytes = unsafe { leaf.as_ref() }.key.as_bytes();
let mut cache = cache;
if let Some(c) = cache.as_deref_mut() {
if let Some(r) = c.try_fast(&self.raw, &owner, key_bytes, count) {
return Ok(match r {
Outcome::Inserted(_) => count,
_ => unreachable!("the fast path only inserts"),
});
}
}
let mut hint = None;
match self.raw.insert_hinted(
&owner,
key_bytes,
Mode::InsertIfAbsent,
count,
&(),
&mut hint,
) {
Ok(Outcome::Inserted(_)) => {
if let Some(c) = cache {
c.remember(hint, key_bytes);
}
Ok(count)
}
Ok(Outcome::Existing(existing)) => {
unsafe { leaf.as_ref().detach_head_unpublished() };
Ok(self.apply(existing, node))
}
Ok(Outcome::Replaced(_)) => unreachable!("InsertIfAbsent never replaces"),
Err(_) => {
owner.disarm();
let (l, n) =
unsafe { (leaf.read(), self.arena().ptr::<VersionNode<V>>(node).read()) };
Err((l.key, n.into_value()))
}
}
}
fn apply(&self, leaf: NonNull<VersionedLeaf<K, V>>, node: u32) -> isize {
let arena = &**self.arena();
let leaf = unsafe { leaf.as_ref() };
let at = |off: u32| -> Option<&VersionNode<V>> {
(off != 0).then(|| unsafe { arena.ptr::<VersionNode<V>>(off).as_ref() })
};
let new = unsafe { arena.ptr::<VersionNode<V>>(node).as_ref() };
let version = new.version;
let lock = || leaf.chain_latch.lock();
#[cfg(loom)]
let unlatched = crate::latch::mutants::CHAIN_POSITION_UNLATCHED.with(|m| m.get());
#[cfg(not(loom))]
let unlatched = false;
let early = (!unlatched).then(lock);
let head = leaf.head();
let old_live = at(head).is_some_and(|h| !h.is_tombstone());
let mut prev = 0u32;
let mut cur = head;
while let Some(n) = at(cur).filter(|n| n.version > version) {
prev = cur;
cur = n.next();
}
let w = early.unwrap_or_else(lock);
let replaced = at(cur).is_some_and(|n| n.version == version);
new.init_next(match (replaced, at(cur)) {
(true, Some(c)) => c.next(),
_ => cur,
});
let bomb = AbortOnUnwind;
match at(prev) {
None => leaf.set_head(&w, node),
Some(p) => p.set_next(&w, node),
}
if replaced {
if let Some(c) = at(cur) {
c.mark_superseded(&w);
}
}
let new_live = at(leaf.head()).is_some_and(|h| !h.is_tombstone());
let delta = isize::from(new_live) - isize::from(old_live);
self.raw.len_add(delta);
bomb.defuse();
drop(w);
if replaced {
self.retire_version(cur);
}
delta
}
pub(crate) fn remove_head(&self, key: &[u8]) -> RemovedHead<K, V> {
let Some(leaf_ptr) = self.raw.get(key) else {
return Ok(None);
};
let tomb = self.alloc_version(0, None).map_err(|_| ())?;
let arena = &**self.arena();
let leaf = unsafe { leaf_ptr.as_ref() };
let w = leaf.chain_latch.lock();
let head = leaf.head();
let h = unsafe { arena.ptr::<VersionNode<V>>(head).as_ref() };
if h.is_tombstone() {
return Ok(None);
}
unsafe {
let t = arena.ptr::<VersionNode<V>>(tomb).as_ptr();
(*t).version = h.version;
(*t).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);
self.retire_version(head);
Ok(Some((leaf_ptr, head)))
}
}
#[cfg(all(test, not(loom)))]
mod tests {
use super::*;
use crate::arena::tree::FAST_PATH_HITS;
fn hits() -> usize {
FAST_PATH_HITS.with(|n| n.get())
}
#[test]
fn versioned_inserter_fast_path_hits_for_sequential_keys() {
let t = ArenaVersionedTree::<Vec<u8>, u64>::new(Arena::with_capacity(8 << 20));
let mut cache = InserterCache::new();
let before = hits();
for i in 0..200u8 {
t.insert(vec![b'k', i], 1, Some(i as u64), Some(&mut cache))
.ok()
.unwrap();
}
let hit = hits() - before;
assert!(
hit >= 190,
"only {hit} of 200 sequential inserts used the fast path"
);
for i in 0..200u8 {
assert!(t.raw.get(&[b'k', i]).is_some());
}
}
}