#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use std::cell::UnsafeCell;
use std::mem::MaybeUninit;
use std::ptr::{self, NonNull};
use crate::key::AsBytes;
use crate::latch::{ChainGuard, ChainLock};
use crate::raw::LeafNode;
use crate::sync::atomic::{AtomicPtr, AtomicU8, Ordering};
const SUPERSEDED: usize = 0b001;
const TOMBSTONE: usize = 0b010;
const INLINE: usize = 0b100;
const FLAGS: usize = SUPERSEDED | TOMBSTONE | INLINE;
#[repr(C, align(8))]
pub(crate) struct VersionNode<V> {
pub(crate) version: u64,
next: AtomicPtr<VersionNode<V>>,
value: MaybeUninit<V>,
}
impl<V> VersionNode<V> {
fn new(version: u64, value: Option<V>, inline: bool) -> Self {
let (value, tombstone) = match value {
Some(v) => (MaybeUninit::new(v), false),
None => (MaybeUninit::uninit(), true),
};
let flags = if tombstone { TOMBSTONE } else { 0 } | if inline { INLINE } else { 0 };
Self {
version,
next: AtomicPtr::new(ptr::without_provenance_mut(flags)),
value,
}
}
#[inline]
fn flags(&self) -> usize {
self.next.load(Ordering::Relaxed).addr() & FLAGS
}
#[inline]
pub(crate) fn is_tombstone(&self) -> bool {
self.flags() & TOMBSTONE != 0
}
#[inline]
pub(crate) fn is_inline(&self) -> bool {
self.flags() & INLINE != 0
}
#[inline]
pub(crate) fn value(&self) -> Option<&V> {
(!self.is_tombstone()).then(|| unsafe { self.value.assume_init_ref() })
}
#[inline]
pub(crate) fn next(&self) -> *mut VersionNode<V> {
self.next.load(Ordering::Acquire).map_addr(|a| a & !FLAGS)
}
#[inline]
pub(crate) fn is_superseded(&self) -> bool {
self.next.load(Ordering::Acquire).addr() & SUPERSEDED != 0
}
#[inline]
fn store_next(&self, next: *mut VersionNode<V>, order: Ordering) {
debug_assert_eq!(next.addr() & FLAGS, 0, "version nodes are 8-aligned");
let flags = self.next.load(Ordering::Relaxed).addr() & FLAGS;
self.next.store(next.map_addr(|a| a | flags), order);
}
#[inline]
pub(crate) fn set_next(&self, _w: &ChainGuard<'_>, next: *mut VersionNode<V>) {
self.store_next(next, Ordering::Release);
}
#[inline]
pub(crate) fn init_next(&self, next: *mut VersionNode<V>) {
self.store_next(next, Ordering::Relaxed);
}
#[inline]
pub(crate) fn mark_superseded(&self, _w: &ChainGuard<'_>) {
let cur = self.next.load(Ordering::Relaxed);
self.next
.store(cur.map_addr(|a| a | SUPERSEDED), Ordering::Release);
}
}
impl<V> Drop for VersionNode<V> {
fn drop(&mut self) {
if !self.is_tombstone() {
unsafe { self.value.assume_init_drop() };
}
}
}
const SLOT0: u8 = 0b01;
const SLOT1: u8 = 0b10;
#[repr(C, align(8))]
pub(crate) struct VersionedLeaf<K, V> {
pub(crate) key: K,
head: AtomicPtr<VersionNode<V>>,
slot0: UnsafeCell<MaybeUninit<VersionNode<V>>>,
slot1: UnsafeCell<MaybeUninit<VersionNode<V>>>,
pub(crate) chain_latch: ChainLock,
slots_init: AtomicU8,
}
unsafe impl<K: Send, V: Send> Send for VersionedLeaf<K, V> {}
unsafe impl<K: Sync + Send, V: Sync + Send> Sync for VersionedLeaf<K, V> {}
impl<K, V> VersionedLeaf<K, V> {
pub(crate) fn new_boxed(key: K, version: u64, value: Option<V>) -> NonNull<Self> {
let leaf = Box::into_raw(Box::new(Self {
key,
head: AtomicPtr::new(ptr::null_mut()),
slot0: UnsafeCell::new(MaybeUninit::new(VersionNode::new(version, value, true))),
slot1: UnsafeCell::new(MaybeUninit::uninit()),
chain_latch: ChainLock::new(),
slots_init: AtomicU8::new(SLOT0),
}));
unsafe {
let head = UnsafeCell::raw_get(ptr::addr_of!((*leaf).slot0)).cast::<VersionNode<V>>();
(*leaf).head.store(head, Ordering::Relaxed);
NonNull::new_unchecked(leaf)
}
}
#[inline]
pub(crate) fn head(&self) -> &VersionNode<V> {
unsafe { &*self.head.load(Ordering::Acquire) }
}
#[inline]
pub(crate) fn set_head(&self, w: &ChainGuard<'_>, node: *mut VersionNode<V>) {
debug_assert!(w.holds(&self.chain_latch));
self.head.store(node, Ordering::Release);
}
#[inline]
pub(crate) fn head_ptr(&self) -> *mut VersionNode<V> {
self.head.load(Ordering::Acquire)
}
pub(crate) fn alloc_version(
&self,
w: &ChainGuard<'_>,
version: u64,
value: Option<V>,
) -> *mut VersionNode<V> {
debug_assert!(w.holds(&self.chain_latch));
if self.slots_init.load(Ordering::Relaxed) & SLOT1 == 0 {
let p = self.slot1.get().cast::<VersionNode<V>>();
unsafe { p.write(VersionNode::new(version, value, true)) };
self.slots_init.store(
self.slots_init.load(Ordering::Relaxed) | SLOT1,
Ordering::Relaxed,
);
p
} else {
let mut b = Box::<VersionNode<V>>::new_uninit();
b.write(VersionNode::new(version, value, false));
Box::into_raw(unsafe { b.assume_init() })
}
}
pub(crate) unsafe fn take_first(this: NonNull<Self>) -> (u64, Option<V>) {
unsafe {
let leaf = this.as_ptr();
let slot0 = (*leaf).slot0.get().cast::<VersionNode<V>>();
let version = (*slot0).version;
let value = if (*slot0).is_tombstone() {
None
} else {
Some(ptr::read((*slot0).value.as_ptr()))
};
(*leaf).slots_init.store(0, Ordering::Relaxed);
(version, value)
}
}
}
impl<K, V> Drop for VersionedLeaf<K, V> {
fn drop(&mut self) {
let slot0 = self.slot0.get().cast::<VersionNode<V>>();
let slot1 = self.slot1.get().cast::<VersionNode<V>>();
let mut cur = self.head.load(Ordering::Relaxed);
while !cur.is_null() {
let at = if cur.addr() == slot0.addr() {
slot0
} else if cur.addr() == slot1.addr() {
slot1
} else {
cur
};
let (next, inline) = unsafe { ((*at).next(), (*at).is_inline()) };
if !inline {
drop(unsafe { Box::from_raw(cur) });
}
cur = next;
}
let init = self.slots_init.load(Ordering::Relaxed);
if init & SLOT0 != 0 {
unsafe { self.slot0.get_mut().assume_init_drop() };
}
if init & SLOT1 != 0 {
unsafe { self.slot1.get_mut().assume_init_drop() };
}
}
}
impl<K: AsBytes, V> LeafNode for VersionedLeaf<K, V> {
#[inline(always)]
fn key_bytes(&self) -> &[u8] {
self.key.as_bytes()
}
#[inline]
fn mark_removed(&self) {}
}
#[cfg(all(test, not(loom)))]
mod tests {
use super::*;
use std::sync::atomic::AtomicUsize;
use std::sync::Arc;
struct D(Arc<AtomicUsize>);
impl Drop for D {
fn drop(&mut self) {
self.0.fetch_add(1, Ordering::SeqCst);
}
}
#[test]
fn inline_slots_and_heap_nodes_drop_once() {
let n = Arc::new(AtomicUsize::new(0));
let leaf = VersionedLeaf::<String, D>::new_boxed("k".into(), 10, Some(D(Arc::clone(&n))));
{
let l = unsafe { leaf.as_ref() };
let w = l.chain_latch.lock();
let v20 = l.alloc_version(&w, 20, Some(D(Arc::clone(&n))));
assert!(unsafe { (*v20).is_inline() }, "second version takes slot1");
let v30 = l.alloc_version(&w, 30, Some(D(Arc::clone(&n))));
let spilled = !unsafe { (*v30).is_inline() };
assert!(spilled, "third version spills to the heap");
unsafe {
(*v20).init_next(l.head_ptr());
(*v30).init_next(v20);
}
l.set_head(&w, v30);
drop(w);
assert_eq!(l.head().version, 30);
}
assert_eq!(n.load(Ordering::SeqCst), 0);
drop(unsafe { Box::from_raw(leaf.as_ptr()) });
assert_eq!(
n.load(Ordering::SeqCst),
3,
"every value dropped exactly once"
);
}
#[test]
fn take_first_moves_the_value_out() {
let n = Arc::new(AtomicUsize::new(0));
let leaf = VersionedLeaf::<String, D>::new_boxed("k".into(), 7, Some(D(Arc::clone(&n))));
let (v, value) = unsafe { VersionedLeaf::take_first(leaf) };
assert_eq!(v, 7);
drop(unsafe { Box::from_raw(leaf.as_ptr()) });
assert_eq!(
n.load(Ordering::SeqCst),
0,
"the husk does not drop the moved value"
);
drop(value);
assert_eq!(n.load(Ordering::SeqCst), 1);
}
#[test]
#[cfg(target_pointer_width = "64")]
fn version_nodes_stay_compact() {
assert_eq!(std::mem::size_of::<VersionNode<u64>>(), 24);
assert_eq!(std::mem::size_of::<VersionedLeaf<[u8; 8], u64>>(), 72);
}
#[test]
fn flags_survive_next_updates() {
let leaf = VersionedLeaf::<u8, u8>::new_boxed(1, 1, None);
let l = unsafe { leaf.as_ref() };
let head = l.head();
assert!(head.is_tombstone() && head.is_inline() && !head.is_superseded());
assert!(head.next().is_null());
let w = l.chain_latch.lock();
let v2 = l.alloc_version(&w, 2, Some(7));
let n = unsafe { &*v2 };
assert!(!n.is_tombstone() && n.is_inline());
n.init_next(l.head_ptr());
assert_eq!(n.next(), l.head_ptr(), "the link is untagged");
head.mark_superseded(&w);
assert!(head.is_superseded() && head.is_tombstone() && head.is_inline());
assert!(head.next().is_null());
n.set_next(&w, std::ptr::null_mut());
assert!(!n.is_tombstone() && n.is_inline() && !n.is_superseded());
assert_eq!(n.value(), Some(&7));
drop(w);
drop(unsafe { Box::from_raw(leaf.as_ptr()) });
}
#[test]
fn tombstones_are_values_of_none() {
let leaf = VersionedLeaf::<u8, u8>::new_boxed(1, 1, None);
let l = unsafe { leaf.as_ref() };
assert!(l.head().is_tombstone());
assert!(!l.head().is_superseded());
drop(unsafe { Box::from_raw(leaf.as_ptr()) });
}
}